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