GNU Linux-libre 4.19.211-gnu1
[releases.git] / fs / hfsplus / bitmap.c
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  *  linux/fs/hfsplus/bitmap.c
4  *
5  * Copyright (C) 2001
6  * Brad Boyer (flar@allandria.com)
7  * (C) 2003 Ardis Technologies <roman@ardistech.com>
8  *
9  * Handling of allocation file
10  */
11
12 #include <linux/pagemap.h>
13
14 #include "hfsplus_fs.h"
15 #include "hfsplus_raw.h"
16
17 #define PAGE_CACHE_BITS (PAGE_SIZE * 8)
18
19 int hfsplus_block_allocate(struct super_block *sb, u32 size,
20                 u32 offset, u32 *max)
21 {
22         struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
23         struct page *page;
24         struct address_space *mapping;
25         __be32 *pptr, *curr, *end;
26         u32 mask, start, len, n;
27         __be32 val;
28         int i;
29
30         len = *max;
31         if (!len)
32                 return size;
33
34         hfs_dbg(BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
35         mutex_lock(&sbi->alloc_mutex);
36         mapping = sbi->alloc_file->i_mapping;
37         page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
38         if (IS_ERR(page)) {
39                 start = size;
40                 goto out;
41         }
42         pptr = kmap(page);
43         curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
44         i = offset % 32;
45         offset &= ~(PAGE_CACHE_BITS - 1);
46         if ((size ^ offset) / PAGE_CACHE_BITS)
47                 end = pptr + PAGE_CACHE_BITS / 32;
48         else
49                 end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
50
51         /* scan the first partial u32 for zero bits */
52         val = *curr;
53         if (~val) {
54                 n = be32_to_cpu(val);
55                 mask = (1U << 31) >> i;
56                 for (; i < 32; mask >>= 1, i++) {
57                         if (!(n & mask))
58                                 goto found;
59                 }
60         }
61         curr++;
62
63         /* scan complete u32s for the first zero bit */
64         while (1) {
65                 while (curr < end) {
66                         val = *curr;
67                         if (~val) {
68                                 n = be32_to_cpu(val);
69                                 mask = 1 << 31;
70                                 for (i = 0; i < 32; mask >>= 1, i++) {
71                                         if (!(n & mask))
72                                                 goto found;
73                                 }
74                         }
75                         curr++;
76                 }
77                 kunmap(page);
78                 offset += PAGE_CACHE_BITS;
79                 if (offset >= size)
80                         break;
81                 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
82                                          NULL);
83                 if (IS_ERR(page)) {
84                         start = size;
85                         goto out;
86                 }
87                 curr = pptr = kmap(page);
88                 if ((size ^ offset) / PAGE_CACHE_BITS)
89                         end = pptr + PAGE_CACHE_BITS / 32;
90                 else
91                         end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
92         }
93         hfs_dbg(BITMAP, "bitmap full\n");
94         start = size;
95         goto out;
96
97 found:
98         start = offset + (curr - pptr) * 32 + i;
99         if (start >= size) {
100                 hfs_dbg(BITMAP, "bitmap full\n");
101                 goto out;
102         }
103         /* do any partial u32 at the start */
104         len = min(size - start, len);
105         while (1) {
106                 n |= mask;
107                 if (++i >= 32)
108                         break;
109                 mask >>= 1;
110                 if (!--len || n & mask)
111                         goto done;
112         }
113         if (!--len)
114                 goto done;
115         *curr++ = cpu_to_be32(n);
116         /* do full u32s */
117         while (1) {
118                 while (curr < end) {
119                         n = be32_to_cpu(*curr);
120                         if (len < 32)
121                                 goto last;
122                         if (n) {
123                                 len = 32;
124                                 goto last;
125                         }
126                         *curr++ = cpu_to_be32(0xffffffff);
127                         len -= 32;
128                 }
129                 set_page_dirty(page);
130                 kunmap(page);
131                 offset += PAGE_CACHE_BITS;
132                 page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
133                                          NULL);
134                 if (IS_ERR(page)) {
135                         start = size;
136                         goto out;
137                 }
138                 pptr = kmap(page);
139                 curr = pptr;
140                 end = pptr + PAGE_CACHE_BITS / 32;
141         }
142 last:
143         /* do any partial u32 at end */
144         mask = 1U << 31;
145         for (i = 0; i < len; i++) {
146                 if (n & mask)
147                         break;
148                 n |= mask;
149                 mask >>= 1;
150         }
151 done:
152         *curr = cpu_to_be32(n);
153         set_page_dirty(page);
154         kunmap(page);
155         *max = offset + (curr - pptr) * 32 + i - start;
156         sbi->free_blocks -= *max;
157         hfsplus_mark_mdb_dirty(sb);
158         hfs_dbg(BITMAP, "-> %u,%u\n", start, *max);
159 out:
160         mutex_unlock(&sbi->alloc_mutex);
161         return start;
162 }
163
164 int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
165 {
166         struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
167         struct page *page;
168         struct address_space *mapping;
169         __be32 *pptr, *curr, *end;
170         u32 mask, len, pnr;
171         int i;
172
173         /* is there any actual work to be done? */
174         if (!count)
175                 return 0;
176
177         hfs_dbg(BITMAP, "block_free: %u,%u\n", offset, count);
178         /* are all of the bits in range? */
179         if ((offset + count) > sbi->total_blocks)
180                 return -ENOENT;
181
182         mutex_lock(&sbi->alloc_mutex);
183         mapping = sbi->alloc_file->i_mapping;
184         pnr = offset / PAGE_CACHE_BITS;
185         page = read_mapping_page(mapping, pnr, NULL);
186         if (IS_ERR(page))
187                 goto kaboom;
188         pptr = kmap(page);
189         curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
190         end = pptr + PAGE_CACHE_BITS / 32;
191         len = count;
192
193         /* do any partial u32 at the start */
194         i = offset % 32;
195         if (i) {
196                 int j = 32 - i;
197                 mask = 0xffffffffU << j;
198                 if (j > count) {
199                         mask |= 0xffffffffU >> (i + count);
200                         *curr++ &= cpu_to_be32(mask);
201                         goto out;
202                 }
203                 *curr++ &= cpu_to_be32(mask);
204                 count -= j;
205         }
206
207         /* do full u32s */
208         while (1) {
209                 while (curr < end) {
210                         if (count < 32)
211                                 goto done;
212                         *curr++ = 0;
213                         count -= 32;
214                 }
215                 if (!count)
216                         break;
217                 set_page_dirty(page);
218                 kunmap(page);
219                 page = read_mapping_page(mapping, ++pnr, NULL);
220                 if (IS_ERR(page))
221                         goto kaboom;
222                 pptr = kmap(page);
223                 curr = pptr;
224                 end = pptr + PAGE_CACHE_BITS / 32;
225         }
226 done:
227         /* do any partial u32 at end */
228         if (count) {
229                 mask = 0xffffffffU >> count;
230                 *curr &= cpu_to_be32(mask);
231         }
232 out:
233         set_page_dirty(page);
234         kunmap(page);
235         sbi->free_blocks += len;
236         hfsplus_mark_mdb_dirty(sb);
237         mutex_unlock(&sbi->alloc_mutex);
238
239         return 0;
240
241 kaboom:
242         pr_crit("unable to mark blocks free: error %ld\n", PTR_ERR(page));
243         mutex_unlock(&sbi->alloc_mutex);
244
245         return -EIO;
246 }