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