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
;
113 * hfs_vbm_search_free()
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.
122 * struct hfs_mdb *mdb: Pointer to the hfs MDB
123 * u16 *num_bits: Pointer to the number of cleared bits
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.
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!
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.
137 * 'num_bits' is set to the length of the found sequence.
139 u32
hfs_vbm_search_free(struct super_block
*sb
, u32 goal
, u32
*num_bits
)
144 /* make sure we have actual work to perform */
148 mutex_lock(&HFS_SB(sb
)->bitmap_lock
);
149 bitmap
= HFS_SB(sb
)->bitmap
;
151 pos
= hfs_find_set_zero_bits(bitmap
, HFS_SB(sb
)->fs_ablocks
, goal
, num_bits
);
152 if (pos
>= HFS_SB(sb
)->fs_ablocks
) {
154 pos
= hfs_find_set_zero_bits(bitmap
, goal
, 0, num_bits
);
155 if (pos
>= HFS_SB(sb
)->fs_ablocks
) {
161 dprint(DBG_BITMAP
, "alloc_bits: %u,%u\n", pos
, *num_bits
);
162 HFS_SB(sb
)->free_ablocks
-= *num_bits
;
163 hfs_bitmap_dirty(sb
);
165 mutex_unlock(&HFS_SB(sb
)->bitmap_lock
);
171 * hfs_clear_vbm_bits()
174 * Clear the requested bits in the volume bitmap of the hfs filesystem
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):
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.
187 * 'mdb' points to a "valid" (struct hfs_mdb).
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.
193 int hfs_clear_vbm_bits(struct super_block
*sb
, u16 start
, u16 count
)
199 /* is there any actual work to be done? */
203 dprint(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
)
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);
213 /* do any partial u32 at the start */
217 mask
= 0xffffffffU
<< j
;
219 mask
|= 0xffffffffU
>> (i
+ count
);
220 *curr
&= cpu_to_be32(mask
);
223 *curr
++ &= cpu_to_be32(mask
);
228 while (count
>= 32) {
232 /* do any partial u32 at end */
234 mask
= 0xffffffffU
>> count
;
235 *curr
&= cpu_to_be32(mask
);
238 HFS_SB(sb
)->free_ablocks
+= len
;
239 mutex_unlock(&HFS_SB(sb
)->bitmap_lock
);
240 hfs_bitmap_dirty(sb
);
This page took 0.034542 seconds and 5 git commands to generate.