Chapter 9: The Extended Filesystem Family
If no free bit is found near the desired goal, the search is not performed bitwise, but bytewise to increase
performance. A free byte corresponds to eight successive zeros or eight free file blocks. If a free byte
is found, the address of the first bit is returned. As a last resort, a bitwise scan over the whole range is
performed. This equates to searching for a single, isolated free block and is, of course, the worst-case
scenario, which, unfortunately, cannot always be avoided.Let us go back toext2_try_to_allocate. Since the bit might originate from a bytewise search, the
last seven preceding bits are scanned for a free area. (A larger number of preceding bits is not possi-
ble because the kernel would then have found a freebyte in the previous step.) The newly allocated
block is always shifted as far to the left as possible to ensure that the free area to its right is as large as
possible.What now remains to be done is a simple bitwise traversal of the block bitmap. In each step, a block is
added to the allocation if the bit is not set. Recall that allocating a block is equivalent to setting the corre-
sponding bit in the block bitmap to one. The traversal stops when either an occupied block is encountered
or a sufficient number of blocks has been allocated.fs/ext2/balloc.c
if (ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group), grp_goal,
bitmap_bh->b_data)) {
/*
* The block was allocated by another thread, or it was
* allocated and then freed by another thread
*/
start++;
grp_goal++;
if (start >= end)
goto fail_access;
goto repeat;
}
num++;
grp_goal++;
while (num < *count && grp_goal < end
&& !ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group),
grp_goal, bitmap_bh->b_data)) {
num++;
grp_goal++;
}
*count = num;
return grp_goal - num;
fail_access:
*count = num;
return -1;
}The only complication stems from the fact that the initial bit might have been allocated by another process
between the time it was chosen and when the kernel tries to allocate it. In this case, both the starting
position and group goal are increased by 1, and the search started again.Creating New Reservations
Above, it was mentioned thatalloc_new_reservationis employed to create new reservation windows.
This is an important task now discussed in detail. An overview of the function is presented in Figure 9-17.