1 | /* |
2 | * linux/fs/hfs/bitmap.c |
3 | * |
4 | * Copyright (C) 1996-1997 Paul H. Hargrove |
5 | * (C) 2003 Ardis Technologies <roman@ardistech.com> |
6 | * This file may be distributed under the terms of the GNU General Public License. |
7 | * |
8 | * Based on GPLed code Copyright (C) 1995 Michael Dreher |
9 | * |
10 | * This file contains the code to modify the volume bitmap: |
11 | * search/set/clear bits. |
12 | */ |
13 | |
14 | #include "hfs_fs.h" |
15 | |
16 | /* |
17 | * hfs_find_zero_bit() |
18 | * |
19 | * Description: |
20 | * Given a block of memory, its length in bits, and a starting bit number, |
21 | * determine the number of the first zero bits (in left-to-right ordering) |
22 | * in that range. |
23 | * |
24 | * Returns >= 'size' if no zero bits are found in the range. |
25 | * |
26 | * Accesses memory in 32-bit aligned chunks of 32-bits and thus |
27 | * may read beyond the 'size'th bit. |
28 | */ |
29 | static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max) |
30 | { |
31 | __be32 *curr, *end; |
32 | u32 mask, start, len, n; |
33 | __be32 val; |
34 | int i; |
35 | |
36 | len = *max; |
37 | if (!len) |
38 | return size; |
39 | |
40 | curr = bitmap + (offset / 32); |
41 | end = bitmap + ((size + 31) / 32); |
42 | |
43 | /* scan the first partial u32 for zero bits */ |
44 | val = *curr; |
45 | if (~val) { |
46 | n = be32_to_cpu(val); |
47 | i = offset % 32; |
48 | mask = (1U << 31) >> i; |
49 | for (; i < 32; mask >>= 1, i++) { |
50 | if (!(n & mask)) |
51 | goto found; |
52 | } |
53 | } |
54 | |
55 | /* scan complete u32s for the first zero bit */ |
56 | while (++curr < end) { |
57 | val = *curr; |
58 | if (~val) { |
59 | n = be32_to_cpu(val); |
60 | mask = 1 << 31; |
61 | for (i = 0; i < 32; mask >>= 1, i++) { |
62 | if (!(n & mask)) |
63 | goto found; |
64 | } |
65 | } |
66 | } |
67 | return size; |
68 | |
69 | found: |
70 | start = (curr - bitmap) * 32 + i; |
71 | if (start >= size) |
72 | return start; |
73 | /* do any partial u32 at the start */ |
74 | len = min(size - start, len); |
75 | while (1) { |
76 | n |= mask; |
77 | if (++i >= 32) |
78 | break; |
79 | mask >>= 1; |
80 | if (!--len || n & mask) |
81 | goto done; |
82 | } |
83 | if (!--len) |
84 | goto done; |
85 | *curr++ = cpu_to_be32(n); |
86 | /* do full u32s */ |
87 | while (1) { |
88 | n = be32_to_cpu(*curr); |
89 | if (len < 32) |
90 | break; |
91 | if (n) { |
92 | len = 32; |
93 | break; |
94 | } |
95 | *curr++ = cpu_to_be32(0xffffffff); |
96 | len -= 32; |
97 | } |
98 | /* do any partial u32 at end */ |
99 | mask = 1U << 31; |
100 | for (i = 0; i < len; i++) { |
101 | if (n & mask) |
102 | break; |
103 | n |= mask; |
104 | mask >>= 1; |
105 | } |
106 | done: |
107 | *curr = cpu_to_be32(n); |
108 | *max = (curr - bitmap) * 32 + i - start; |
109 | return start; |
110 | } |
111 | |
112 | /* |
113 | * hfs_vbm_search_free() |
114 | * |
115 | * Description: |
116 | * Search for 'num_bits' consecutive cleared bits in the bitmap blocks of |
117 | * the hfs MDB. 'mdb' had better be locked or the returned range |
118 | * may be no longer free, when this functions returns! |
119 | * XXX Currently the search starts from bit 0, but it should start with |
120 | * the bit number stored in 's_alloc_ptr' of the MDB. |
121 | * Input Variable(s): |
122 | * struct hfs_mdb *mdb: Pointer to the hfs MDB |
123 | * u16 *num_bits: Pointer to the number of cleared bits |
124 | * to search for |
125 | * Output Variable(s): |
126 | * u16 *num_bits: The number of consecutive clear bits of the |
127 | * returned range. If the bitmap is fragmented, this will be less than |
128 | * requested and it will be zero, when the disk is full. |
129 | * Returns: |
130 | * The number of the first bit of the range of cleared bits which has been |
131 | * found. When 'num_bits' is zero, this is invalid! |
132 | * Preconditions: |
133 | * 'mdb' points to a "valid" (struct hfs_mdb). |
134 | * 'num_bits' points to a variable of type (u16), which contains |
135 | * the number of cleared bits to find. |
136 | * Postconditions: |
137 | * 'num_bits' is set to the length of the found sequence. |
138 | */ |
139 | u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits) |
140 | { |
141 | void *bitmap; |
142 | u32 pos; |
143 | |
144 | /* make sure we have actual work to perform */ |
145 | if (!*num_bits) |
146 | return 0; |
147 | |
148 | mutex_lock(&HFS_SB(sb)->bitmap_lock); |
149 | bitmap = HFS_SB(sb)->bitmap; |
150 | |
151 | pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, offset: goal, max: num_bits); |
152 | if (pos >= HFS_SB(sb)->fs_ablocks) { |
153 | if (goal) |
154 | pos = hfs_find_set_zero_bits(bitmap, size: goal, offset: 0, max: num_bits); |
155 | if (pos >= HFS_SB(sb)->fs_ablocks) { |
156 | *num_bits = pos = 0; |
157 | goto out; |
158 | } |
159 | } |
160 | |
161 | hfs_dbg(BITMAP, "alloc_bits: %u,%u\n" , pos, *num_bits); |
162 | HFS_SB(sb)->free_ablocks -= *num_bits; |
163 | hfs_bitmap_dirty(sb); |
164 | out: |
165 | mutex_unlock(lock: &HFS_SB(sb)->bitmap_lock); |
166 | return pos; |
167 | } |
168 | |
169 | |
170 | /* |
171 | * hfs_clear_vbm_bits() |
172 | * |
173 | * Description: |
174 | * Clear the requested bits in the volume bitmap of the hfs filesystem |
175 | * Input Variable(s): |
176 | * struct hfs_mdb *mdb: Pointer to the hfs MDB |
177 | * u16 start: The offset of the first bit |
178 | * u16 count: The number of bits |
179 | * Output Variable(s): |
180 | * None |
181 | * Returns: |
182 | * 0: no error |
183 | * -1: One of the bits was already clear. This is a strange |
184 | * error and when it happens, the filesystem must be repaired! |
185 | * -2: One or more of the bits are out of range of the bitmap. |
186 | * Preconditions: |
187 | * 'mdb' points to a "valid" (struct hfs_mdb). |
188 | * Postconditions: |
189 | * Starting with bit number 'start', 'count' bits in the volume bitmap |
190 | * are cleared. The affected bitmap blocks are marked "dirty", the free |
191 | * block count of the MDB is updated and the MDB is marked dirty. |
192 | */ |
193 | int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count) |
194 | { |
195 | __be32 *curr; |
196 | u32 mask; |
197 | int i, len; |
198 | |
199 | /* is there any actual work to be done? */ |
200 | if (!count) |
201 | return 0; |
202 | |
203 | hfs_dbg(BITMAP, "clear_bits: %u,%u\n" , start, count); |
204 | /* are all of the bits in range? */ |
205 | if ((start + count) > HFS_SB(sb)->fs_ablocks) |
206 | return -2; |
207 | |
208 | mutex_lock(&HFS_SB(sb)->bitmap_lock); |
209 | /* bitmap is always on a 32-bit boundary */ |
210 | curr = HFS_SB(sb)->bitmap + (start / 32); |
211 | len = count; |
212 | |
213 | /* do any partial u32 at the start */ |
214 | i = start % 32; |
215 | if (i) { |
216 | int j = 32 - i; |
217 | mask = 0xffffffffU << j; |
218 | if (j > count) { |
219 | mask |= 0xffffffffU >> (i + count); |
220 | *curr &= cpu_to_be32(mask); |
221 | goto out; |
222 | } |
223 | *curr++ &= cpu_to_be32(mask); |
224 | count -= j; |
225 | } |
226 | |
227 | /* do full u32s */ |
228 | while (count >= 32) { |
229 | *curr++ = 0; |
230 | count -= 32; |
231 | } |
232 | /* do any partial u32 at end */ |
233 | if (count) { |
234 | mask = 0xffffffffU >> count; |
235 | *curr &= cpu_to_be32(mask); |
236 | } |
237 | out: |
238 | HFS_SB(sb)->free_ablocks += len; |
239 | mutex_unlock(lock: &HFS_SB(sb)->bitmap_lock); |
240 | hfs_bitmap_dirty(sb); |
241 | |
242 | return 0; |
243 | } |
244 | |