Chapter 9: The Extended Filesystem Family
Several steps are involved in searchingfor a new block. A search is first made for agoalblock; from the
perspective of the filesystem, this block is the ideal candidate for allocation. The search for a global block
is based on general principles only and does not take account of the actual situation in the filesystem. The
ext2_find_goalfunction is invoked to search for the best new block. When searching is performed, it is
necessary to distinguish between two situations:❑ When the block to be allocated logically immediately follows the block last allocated in the file
(in other words, data are to be written contiguously), the filesystem tries to write to the next
physical block on the hard disk. This is obvious — if data are stored sequentially in a file, they
should if at all possible be stored contiguously on the hard disk.
❑ If the position of the new logical block is not immediately after the last allocated block, the
ext2_find_nearfunction is invoked to find the most suitable new block. Depending on the
specific situation, it finds a block close to the indirection block or at least in the same cylinder
group. I won’t bother with the details here.Once it has these two pieces of information (the position in the indirection chain in which there are no
further data blocks, and the desired address of the new block), the kernel sets about reserving a block on
the hard disk. Of course, there is no guarantee that the desired address is really free, so the kernel may
have to be satisfied with poorer alternatives, which unavoidably entails data fragmentation.Not only might new data blocks be required — it can also be the case that some blocks are required to
hold indirection information.ext2_blks_to_allocatecomputes thetotalnumber of new blocks, that is,
the sum of data and (single, double, and triple) indirection blocks. The allocation proper is then done
byext2_alloc_branch. The parameters passed to this function include the desired address of the new
block, information on the last incomplete part of theindirection chain, and the number of indirection
levels still missing up to the new data block. Expressed differently, the function returns a linked list of
indirection and data blocks that can be added to the existing indirection list of the filesystem. Last but
not least,ext2_slice_branchadds the resulting hierarchy (or, in the simplest case, the new data block)
to the existing network and performs several relatively unimportant updates on Ext2 data structures.Block Allocation
ext2_alloc_branchis responsible to allocate the required blocks for a given new path and set up
the chain that connects them. At a first glance, this seems an easy task, as the code flow diagram in
Figure 9-12 might suggest.The function callsext2_alloc_blocks,which,inturnreliesonext2_new_blocksto reserve the required
new blocks. Since the function always allocates consecutive blocks, one single call might not be sufficient
to obtain the total number of required blocks. If the filesystem becomes fragmented, it can be that no such
consecutive region is available. However, this is no problem:ext2_new_blockis called multiple times
until at least the number of blocks that is required for the indirection mechanism has been allocated. The
surplus blocks can be used as data blocks.Finally,ext2_alloc_branchneed only set up theIndirectinstances for the indirection blocks, and it is
done.Obviously, the hard work is hidden inext2_new_blocks. The code flow diagram in Figure 9-13 proves
that this is really the case!