UFS file system space allocation policy

Users coming from other systems don't usually know it (and probably don't care, in today's environment of multi-TB drives), but UFS has a rather interesting approach to space allocation which is different from the "usual suspects" like ext2/3, NTFS and FAT(32). Though it sometimes feels "interesting" in the sense of the Chinese proverb, it's time-tested to work.

I'm talking about clustering, blocks and fragments.


As in more common file systems like ext2/3, NTFS and FAT/FAT32, there is a concept of a "block" or a "cluster" of sectors. Typically, 8 sectors of 512 bytes are clustered together to form a block of 4 kB in size - with time this has become the "traditional" cluster size and is used by default on ext2/3, NTFS and, if drive sizes permit, FAT/FAT32.

This form of clustering means the operating system must maintain less data about what blocks are allocated and where. Since average file size is certainly larger than the sector size (which is the absolute minimum size allocatable on the drive), it makes sense to use a bigger amount of space and consider it "atomic". This has two obvious consequences: first, a 1-byte file takes 1 block of space, e.g. 4 kB and there is nothing to be done about it. Second, all "normal" files usually have some padding at their end to fit on a 4 kB boundary. Even if the operating system records that a file is exactly 5000 bytes in size, it will internally consider this file to take 2 blocks (8 kB). The space between the logical end of the file (5000 bytes) and the accounted space (8 kB) is irrevocably wasted. All usable file systems have variable block sizes; some file systems like FAT and FAT32 have built-in limitations that dictate minimum block (cluster) sizes depending on the drive size - a FAT32 file system of 64 GB will have to use a minimum cluster size of 32 kB to avoid memory and performance problems, meaning up to 32 kB is wasted on small files and there is usually large padding space at the files' ends.

The UFS as implemented in FreeBSD (and other BSDs) has a default block size of 16 kB. In a more common file system, this would mean up to 16 kB of space wasted per file. Fortunately, the "block" is not the smallest allocatable amount of space. Or actually, it normally is, but in special circumstances it isn't.

The very nice invention in UFS is the concept of "fragments". Blocks can be either used whole or they can be subdivided into fragments. By default, with 16 kB blocks, fragments' size is 2 kB. There are very specific rules when this can happen, which boil down to: fragments can be used only at files' ends. This means that a file of 1 byte will allocate 2 kB of space (with almost 2 kB wasted), and random regular files can (but not necessarily must) have up to 2 kB of space wasted.

Fragments are not really directly addressible - this is why they are not considered "blocks" in the usual sense. The "blocks" of 16 kB are "real blocks" corresponding to the concept in similar file systems. The 16/2 kB division is not by accident - 16/2=8, the number of bits in a byte describing blocks as whole or subdivided. It is possible to create a 4096/512 file system in which the block size would be 4 kB and fragment size would be 512 bytes, but over the years the larger configuration (16/2) has proven to be near-optimum and so it is the default. After all, it wastes twice as less space than the other common file systems.


#1 Re: UFS file system space allocation policy

Added on 2009-09-05T18:14 by MyAzhax

i'm waiting for zfs coming 8.0-release

#2 Re: UFS file system space allocation policy

Added on 2009-11-29T15:11 by

Interesting reading.

#3 Re: UFS file system space allocation policy

Added on 2011-03-11T19:49 by Dave

Cool. Just what I was looking for. Thanks!

#4 Re: UFS file system space allocation policy

Added on 2011-04-06T21:50 by Pedro Giffuni

The fact that certain other common filesystem doesn't support fragments limits the size of the blocksize, which also limits the ultimate performance, especially in sync mode.


It would be interesting to see how Solaris has evolved in this aspect and how some of FreeBSD's improvements (dirpref changes, reallocblks) may apply.

Comments !

blogroll

social