46
4
T H E D AT A S T R U C T U R E S O F B F S
It is important to realize that the file system block size is independent of
the size of the disk (unlike the Macintosh HFS). The choice of file system
block size should be made based on the types of files to be stored on the disk:
lots of small files would waste considerable space if the block size were 8K;
a file system with very large files benefits from larger block sizes instead of
very small blocks.
4.2
How to Manage Disk Blocks
There are several different approaches to managing free space on a disk. The
most common (and simplest) method is a bitmap scheme. Other methods are
extent based and B+trees (XFS). BFS uses a bitmap scheme for simplicity.
The bitmap scheme represents each disk block as 1 bit, and the file system
views the entire disk as an array of these bits. If a bit is on (i.e., a one), the
corresponding block is allocated. The formula for the amount of space (in
bytes) required for a block bitmap is
disk size in bytes
file system block size
8
Thus, the bitmap for a 1 GB disk with 1K blocks requires 128K of space.
The main disadvantage to the bitmap allocation scheme is that searching
for large contiguous sections of free space requires searching linearly through
the entire bitmap. There are also those who think that another disadvantage
to the bitmap scheme is that as the disk fills up, searching the bitmap will
become more expensive. However, it can be proven mathematically that the
cost of finding a free bit in a bitmap stays constant regardless of how full the
bitmap is. This fact, coupled with the ease of implementation, is why BFS
uses a bitmap allocation scheme (although in retrospect I wish there had been
time to experiment with other allocation schemes).
The bitmap data structure is simply stored on disk as a contiguous ar-
ray of bytes (rounded up to be a multiple of the block size). BFS stores the
bitmap starting at block one (the superblock is block zero). When creating
the file system, the blocks consumed by the superblock and the bitmap are
preallocated.
4.3
Allocation Groups
Allocation groups are purely logical structures. Allocation groups have no
real
struct
associated with them. BFS divides the array of blocks that make
up a file system into equal-sized chunks, which we call "allocation groups."
BFS uses the notion of allocation groups to spread data around the disk.
Practical File System Design:The Be File System
, Dominic Giampaolo
page 46