2 * linux/fs/hfs/bitmap.c
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.
8 * Based on GPLed code Copyright (C) 1995 Michael Dreher
10 * This file contains the code to modify the volume bitmap:
11 * search/set/clear bits.
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)
24 * Returns >= 'size' if no zero bits are found in the range.
26 * Accesses memory in 32-bit aligned chunks of 32-bits and thus
27 * may read beyond the 'size'th bit.
29 static u32 hfs_find_set_zero_bits(u32 *bitmap, u32 size, u32 offset, u32 *max)
32 u32 val, mask, start, len;
39 curr = bitmap + (offset / 32);
40 end = bitmap + ((size + 31) / 32);
42 /* scan the first partial u32 for zero bits */
45 val = be32_to_cpu(val);
47 mask = (1U << 31) >> i;
48 for (; i < 32; mask >>= 1, i++) {
54 /* scan complete u32s for the first zero bit */
55 while (++curr < end) {
58 val = be32_to_cpu(val);
60 for (i = 0; i < 32; mask >>= 1, i++) {
69 start = (curr - bitmap) * 32 + i;
72 /* do any partial u32 at the start */
73 len = min(size - start, len);
79 if (!--len || val & mask)
84 *curr++ = cpu_to_be32(val);
87 val = be32_to_cpu(*curr);
94 *curr++ = 0xffffffffU;
97 /* do any partial u32 at end */
99 for (i = 0; i < len; i++) {
106 *curr = cpu_to_be32(val);
107 *max = (curr - bitmap) * 32 + i - start;
112 * hfs_vbm_search_free()
115 * Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
116 * the hfs MDB. 'mdb' had better be locked or the returned range
117 * may be no longer free, when this functions returns!
118 * XXX Currently the search starts from bit 0, but it should start with
119 * the bit number stored in 's_alloc_ptr' of the MDB.
121 * struct hfs_mdb *mdb: Pointer to the hfs MDB
122 * u16 *num_bits: Pointer to the number of cleared bits
124 * Output Variable(s):
125 * u16 *num_bits: The number of consecutive clear bits of the
126 * returned range. If the bitmap is fragmented, this will be less than
127 * requested and it will be zero, when the disk is full.
129 * The number of the first bit of the range of cleared bits which has been
130 * found. When 'num_bits' is zero, this is invalid!
132 * 'mdb' points to a "valid" (struct hfs_mdb).
133 * 'num_bits' points to a variable of type (u16), which contains
134 * the number of cleared bits to find.
136 * 'num_bits' is set to the length of the found sequence.
138 u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
143 /* make sure we have actual work to perform */
147 down(&HFS_SB(sb)->bitmap_lock);
148 bitmap = HFS_SB(sb)->bitmap;
150 pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
151 if (pos >= HFS_SB(sb)->fs_ablocks) {
153 pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
154 if (pos >= HFS_SB(sb)->fs_ablocks) {
160 dprint(DBG_BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
161 HFS_SB(sb)->free_ablocks -= *num_bits;
162 hfs_bitmap_dirty(sb);
164 up(&HFS_SB(sb)->bitmap_lock);
170 * hfs_clear_vbm_bits()
173 * Clear the requested bits in the volume bitmap of the hfs filesystem
175 * struct hfs_mdb *mdb: Pointer to the hfs MDB
176 * u16 start: The offset of the first bit
177 * u16 count: The number of bits
178 * Output Variable(s):
182 * -1: One of the bits was already clear. This is a strange
183 * error and when it happens, the filesystem must be repaired!
184 * -2: One or more of the bits are out of range of the bitmap.
186 * 'mdb' points to a "valid" (struct hfs_mdb).
188 * Starting with bit number 'start', 'count' bits in the volume bitmap
189 * are cleared. The affected bitmap blocks are marked "dirty", the free
190 * block count of the MDB is updated and the MDB is marked dirty.
192 int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
198 /* is there any actual work to be done? */
202 dprint(DBG_BITMAP, "clear_bits: %u,%u\n", start, count);
203 /* are all of the bits in range? */
204 if ((start + count) > HFS_SB(sb)->fs_ablocks)
207 down(&HFS_SB(sb)->bitmap_lock);
208 /* bitmap is always on a 32-bit boundary */
209 curr = HFS_SB(sb)->bitmap + (start / 32);
212 /* do any partial u32 at the start */
216 mask = 0xffffffffU << j;
218 mask |= 0xffffffffU >> (i + count);
219 *curr &= cpu_to_be32(mask);
222 *curr++ &= cpu_to_be32(mask);
227 while (count >= 32) {
231 /* do any partial u32 at end */
233 mask = 0xffffffffU >> count;
234 *curr &= cpu_to_be32(mask);
237 HFS_SB(sb)->free_ablocks += len;
238 up(&HFS_SB(sb)->bitmap_lock);
239 hfs_bitmap_dirty(sb);