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, index: offset / PAGE_CACHE_BITS, NULL); |
38 | if (IS_ERR(ptr: page)) { |
39 | start = size; |
40 | goto out; |
41 | } |
42 | pptr = kmap_local_page(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_local(pptr); |
78 | offset += PAGE_CACHE_BITS; |
79 | if (offset >= size) |
80 | break; |
81 | page = read_mapping_page(mapping, index: offset / PAGE_CACHE_BITS, |
82 | NULL); |
83 | if (IS_ERR(ptr: page)) { |
84 | start = size; |
85 | goto out; |
86 | } |
87 | curr = pptr = kmap_local_page(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_local(pptr); |
131 | offset += PAGE_CACHE_BITS; |
132 | page = read_mapping_page(mapping, index: offset / PAGE_CACHE_BITS, |
133 | NULL); |
134 | if (IS_ERR(ptr: page)) { |
135 | start = size; |
136 | goto out; |
137 | } |
138 | pptr = kmap_local_page(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_local(pptr); |
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(lock: &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, index: pnr, NULL); |
186 | if (IS_ERR(ptr: page)) |
187 | goto kaboom; |
188 | pptr = kmap_local_page(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_local(pptr); |
219 | page = read_mapping_page(mapping, index: ++pnr, NULL); |
220 | if (IS_ERR(ptr: page)) |
221 | goto kaboom; |
222 | pptr = kmap_local_page(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_local(pptr); |
235 | sbi->free_blocks += len; |
236 | hfsplus_mark_mdb_dirty(sb); |
237 | mutex_unlock(lock: &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(lock: &sbi->alloc_mutex); |
244 | |
245 | return -EIO; |
246 | } |
247 | |