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(__be32
*bitmap
, u32 size
, u32 offset
, u32
*max
)
32 u32 mask
, start
, len
, n
;
40 curr
= bitmap
+ (offset
/ 32);
41 end
= bitmap
+ ((size
+ 31) / 32);
43 /* scan the first partial u32 for zero bits */
48 mask
= (1U << 31) >> i
;
49 for (; i
< 32; mask
>>= 1, i
++) {
55 /* scan complete u32s for the first zero bit */
56 while (++curr
< end
) {
61 for (i
= 0; i
< 32; mask
>>= 1, i
++) {
70 start
= (curr
- bitmap
) * 32 + i
;
73 /* do any partial u32 at the start */
74 len
= min(size
- start
, len
);
80 if (!--len
|| n
& mask
)
85 *curr
++ = cpu_to_be32(n
);
88 n
= be32_to_cpu(*curr
);
95 *curr
++ = cpu_to_be32(0xffffffff);
98 /* do any partial u32 at end */
100 for (i
= 0; i
< len
; i
++) {
107 *curr
= cpu_to_be32(n
);
108 *max
= (curr
- bitmap
) * 32 + i
- start
;
112 u32
hfs_vbm_search_free(struct super_block
*sb
, u32 goal
, u32
*num_bits
)
117 /* make sure we have actual work to perform */
121 mutex_lock(&HFS_SB(sb
)->bitmap_lock
);
122 bitmap
= HFS_SB(sb
)->bitmap
;
124 pos
= hfs_find_set_zero_bits(bitmap
, HFS_SB(sb
)->fs_ablocks
, goal
, num_bits
);
125 if (pos
>= HFS_SB(sb
)->fs_ablocks
) {
127 pos
= hfs_find_set_zero_bits(bitmap
, goal
, 0, num_bits
);
128 if (pos
>= HFS_SB(sb
)->fs_ablocks
) {
134 dprint(DBG_BITMAP
, "alloc_bits: %u,%u\n", pos
, *num_bits
);
135 HFS_SB(sb
)->free_ablocks
-= *num_bits
;
136 hfs_bitmap_dirty(sb
);
138 mutex_unlock(&HFS_SB(sb
)->bitmap_lock
);
144 * hfs_clear_vbm_bits()
147 * Clear the requested bits in the volume bitmap of the hfs filesystem
149 * struct hfs_mdb *mdb: Pointer to the hfs MDB
150 * u16 start: The offset of the first bit
151 * u16 count: The number of bits
152 * Output Variable(s):
156 * -1: One of the bits was already clear. This is a strange
157 * error and when it happens, the filesystem must be repaired!
158 * -2: One or more of the bits are out of range of the bitmap.
160 * 'mdb' points to a "valid" (struct hfs_mdb).
162 * Starting with bit number 'start', 'count' bits in the volume bitmap
163 * are cleared. The affected bitmap blocks are marked "dirty", the free
164 * block count of the MDB is updated and the MDB is marked dirty.
166 int hfs_clear_vbm_bits(struct super_block
*sb
, u16 start
, u16 count
)
172 /* is there any actual work to be done? */
176 dprint(DBG_BITMAP
, "clear_bits: %u,%u\n", start
, count
);
177 /* are all of the bits in range? */
178 if ((start
+ count
) > HFS_SB(sb
)->fs_ablocks
)
181 mutex_lock(&HFS_SB(sb
)->bitmap_lock
);
182 /* bitmap is always on a 32-bit boundary */
183 curr
= HFS_SB(sb
)->bitmap
+ (start
/ 32);
186 /* do any partial u32 at the start */
190 mask
= 0xffffffffU
<< j
;
192 mask
|= 0xffffffffU
>> (i
+ count
);
193 *curr
&= cpu_to_be32(mask
);
196 *curr
++ &= cpu_to_be32(mask
);
201 while (count
>= 32) {
205 /* do any partial u32 at end */
207 mask
= 0xffffffffU
>> count
;
208 *curr
&= cpu_to_be32(mask
);
211 HFS_SB(sb
)->free_ablocks
+= len
;
212 mutex_unlock(&HFS_SB(sb
)->bitmap_lock
);
213 hfs_bitmap_dirty(sb
);