Historical perspective to Linux Filesystems

Question

Jonathan Leffler's comment in the question "How can I find the Size of some specified files?" is thought-provoking. I will break it into parts for analysis.

1. -- files are stored on pages;

2. you normally end up with more space being used than that calculation gives because a 1 byte file (often) occupies one page (of maybe 512 bytes).

3. The exact values vary - it was easier in the days of the 7th Edition Unix file system (though not trivial even then

4-5. if you wanted to take account of indirect blocks referenced by the inode as well as the raw data blocks).

Questions about the parts

1. What is the definition of "page"?
2. Why is the word "maybe" in the after-thought "one page (of maybe 512 bytes)"?
3. Why was it easier to measure exact sizes in the "7th Edition Unix file system"?
4. What is the definition of "indirect block"?
5. How can you have references by two things: "the inode" and "the raw data blocks"?

Historical Questions Emerged

I. What is the historical context Leffler is speaking about?

II. Have the definitions changed over time?

Answer 1

As usual for Wikipedia pages, Block (data storage) is informative despite being far too exuberant about linking all keywords.

In computing (specifically data transmission and data storage), a block is a sequence of bytes or bits, having a nominal length (a block size). Data thus structured is said to be blocked. The process of putting data into blocks is called blocking. Blocking is used to facilitate the handling of the data-stream by the computer program receiving the data. Blocked data is normally read a whole block at a time. Blocking is almost universally employed when storing data to 9-track magnetic tape, to rotating media such as floppy disks, hard disks, optical discs and to NAND flash memory.

Most file systems are based on a block device, which is a level of abstraction for the hardware responsible for storing and retrieving specified blocks of data, though the block size in file systems may be a multiple of the physical block size. In classical file systems, a single block may only contain a part of a single file. This leads to space inefficiency due to internal fragmentation, since file lengths are often not multiples of block size, and thus the last block of files will remain partially empty. This will create slack space, which averages half a block per file. Some newer file systems attempt to solve this through techniques called block suballocation and tail merging.

There's also a reasonable overview of the classical Unix File System.

Traditionally, hard disk geometry (the layout of blocks on the disk itself) has been CHS.

• Head: the magnetic reader/writer on each (side of a) platter; can move in and out to access different cylinders
• Cylinder: a track that passes under a head as the platter rotates
• Sector: a constant-sized amount of data stored contiguously on a portion the cylinder; the smallest unit of data that the drive can deal with

CHS isn't used much these days, as

• Hard disks no longer use a constant number of sectors per cylinder. More data is squeezed onto a platter by using a constant arclength per sector rather than a constant rotational angle, so there are more sectors on the outer cylinders than there are on the inner cylinders.
• By the ATA specification, a drive may have no more than 2¹⁶ cylinders per head, 2⁴ heads, and 2⁸ sectors per cylinder; with 512B sectors, this is a limit of 128GB. Through BIOS INT13, it is not possible to access anything beyond 7.88GB through CHS anyways.
• For backwards-compatibility, larger drives still claim to have a CHS geometry (otherwise DOS wouldn't be able to boot), but getting to any of the higher data requires using LBA addressing.
• CHS doesn't even make sense on RAID or non-rotational media.

but for historical reasons, this has affected block sizes: because sector sizes were almost always 512B, filesystem block sizes have always been multiples of 512B. (There is a movement afoot to introduce drives with 1kB and 4kB sector sizes, but compatibility looks rather painful.)

Generally speaking, smaller filesystem block sizes result in less wasted space when storing many small files (unless advanced techniques like tail merging are in use), while larger block sizes reduce external fragmentation and have lower overhead on large disks. The filesystem block size is usually a power of 2, is limited below by the block device's sector size, and is often limited above by the OS's page size.

The page size varies by OS and platform (and, in the case of Linux, can vary by configuration as well). Like block size, smaller block sizes reduce internal fragmentation but require more administrative overhead. 4kB page sizes on 32-bit platforms is common.

Now, on to describe indirect blocks. In the UFS design,

• An inode describes a file.
• In the UFS design, the number of pointers to data blocks that an inode could hold is very limited (less than 16). The specific number appears to vary in derived implementations.
• For small files, the pointers can directly point to the data blocks that compose a file.
• For larger files, there must be indirect pointers, which point to a block which only contains more pointers to blocks. These may be direct pointers to data blocks belonging to the file, or if the file is very large, they may be even more indirect pointers.

Thus the amount of storage required for a file may be greater than just the blocks containing its data, when indirect pointers are in use.

Not all filesystems use this method for keeping track of the data blocks belong to a file. FAT simply uses a single file allocation table which is effectively a gigantic series of linked lists, and many modern filesystems use extents.

Answer 2

1. I think he means block instead of page, a block being the minimum addressable unit on the filesystem.

2. block sizes can vary

3. Not sure why but perhaps it the filesystem interface exposed api's allowing a more exact measurement.

4. An indirect block is a block referenced by a pointer

5. The inode occupies space (blocks) just as the raw data does. This is what the author meant.