14
2
W H AT I S A F I L E S Y S T E M ?
to is the same as the number of data blocks an indirect block can refer to.
That is, the number of block addresses in a double-indirect block is the file
system block size divided by the disk block address size. In the example we
gave above, a 1024-byte block file system with 8-byte (64-bit) block addresses,
a double-indirect block could contain references to 128 indirect blocks. Each
of the indirect blocks referred to can, of course, refer to the same number of
data blocks. Thus, using the numbers we've given, the amount of data that a
double-indirect block allows us to map is
128 indirect blocks
128 data blocks per indirect block = 16,384 data blocks
that is, 16 MB with 1K file system blocks.
This is a more reasonable amount of data to map but may still not be
sufficient. In that case triple-indirect blocks may be necessary, but this is
quite rare. In many existing systems the block size is usually larger, and the
size of a block address smaller, which enables mapping considerably larger
amounts of data. For example, a 4096-byte block file system with 4-byte
(32-bit) block addresses could map 4 GB of disk space (4096
=
4 = 1024 block
addresses per block; one double-indirect block maps 1024 indirect blocks,
which each map 1024 data blocks of 4096 bytes each). The double- (or triple-)
indirect blocks generally map the most significant amount of data in a file.
In the list-of-blocks approach, mapping from a file position to a disk block
address is simple. The file position is taken as an index into the file block
list. Since the amount of space that direct, indirect, double-indirect, and even
triple-indirect blocks can map is fixed, the file system always knows exactly
where to look to find the address of the data block that corresponds to a file
position.
The pseudocode for mapping from a file position that is in the double-
indirect range to the address of a data block is shown in Listing 2-1.
Using the
dbl_indirect_index
and
indirect_index
values, the file system
can load the appropriate double-indirect and indirect blocks to find the ad-
dress of the data block that corresponds to the file position. After loading the
data block, the
block_offset
value would let us index to the exact byte offset
that corresponds to the original file position. If the file position is only in the
indirect or direct range of a file, the algorithm is similar but much simpler.
As a concrete example, let us consider a file system that has eight direct
blocks, a 1K file system block size, and 4-byte disk addresses. These param-
eters imply that an indirect or double-indirect block can map 256 blocks. If
we want to locate the data block associated with file position 786769, the
pseudocode in Listing 2-1 would look like it does in Listing 2-2.
With the above calculations completed, the file system would retrieve the
double-indirect block and use the double-indirect index to get the address of
the indirect block. Next the file system would use that address to load the
indirect block. Then, using the indirect index, it would get the address of the
Practical File System Design:The Be File System
, Dominic Giampaolo
page 14