Structure Overview

Let's first take a bird's eye view of the C structures used to manage data to get a clear picture of the functions of the individual components and the interplay among them. Figure 9-2 shows the contents of a block group, a central element of the Ext2 filesystem.

A block group is the basic element that accommodates the further structures of the filesystem. Each filesystem consists of a very large number of block groups arranged one after the other on the hard disk as shown in Figure 9-3.

3''Not used'' is not strictly accurate because a diluted form of this scheme that, to a certain extent, allows the use of a single block to hold several small files is under development and may be included as standard in future versions of the Ext2/3 filesystem. Although the basic infrastructure for such fragments is included in the code, it is not yet implemented.

Super

Group

Data

Inode

Inode

Data blocks

block

descriptors

bitmap

bitmap

tables

1 Block k Blocks 1 Block 1 Block n Blocks m Blocks

Figure 9-2: Block group of the Second Extended Filesystem.

1 Block k Blocks 1 Block 1 Block n Blocks m Blocks

Figure 9-2: Block group of the Second Extended Filesystem.

Boot block

Block group 0

Block group 1

• * *

Block group n

Figure 9-3: Boot sector and block groups on a hard disk.

Figure 9-3: Boot sector and block groups on a hard disk.

The boot sector is a hard disk area whose contents are automatically loaded by the BIOS and executed when the system is powered up. It includes a boot loader4 that permits selection of one of the systems installed on the computer and is also responsible for continuing the boot process. Obviously, this area must not be filled with filesystem data. Boot loaders are not needed on all systems. On systems where they are, they are usually located at the beginning of the hard disk so that later partitions are not affected.

The remaining space on the disk is occupied by successive block groups that store filesystem metadata and the useful data of the individual files. As Figure 9-2 clearly illustrates, each block group contains a great deal of redundant information. Why does the Ext2 filesystem accept this waste of space? There are two reasons why the additional space is justified:

□ If the superblock is destroyed by a system crash, all information on filesystem structure and contents is lost. This information can be recovered only with great difficulty (perhaps not at all by most users) if redundant copies are available.

□ By keeping file and management data closer together, the number of movements and associated travel of the read/write head are reduced, and this improves filesystem performance.

In practice, data are not duplicated in each block group, and the kernel works only with the first copy of the superblock; generally, this is sufficient. When a filesystem check is performed, the data of the first superblock are spread over the remaining superblocks, where it can be read in an emergency. Because this method also consumes a large amount of storage space, later versions of Ext2 adopt the sparse superblock technique. Superblocks are no longer kept in each block group of the filesystem but are written only to groups 0 and 1 as well as to all other groups whose ID can be represented as a power of 3, 5, and 7.

The superblock data are cached in memory so that the kernel is not forced to repeatedly read this information from hard disk — this is, of course, much faster. The second point made above is also no longer relevant because seeks between the individual superblock entries are no longer necessary.

Although it was assumed when designing the Ext2 filesystem that the two issues above would have a strong impact on filesystem performance and security, it was later discovered that this is not the case. The modifications described above were made for this reason.

4LILO on IA-32, MILO on Alpha, SILO on Sparc, and so on.

What is the purpose of the individual structures in the block groups? Before answering this question, it is best to briefly summarize their meaning:

□ The superblock is the central structure for storing meta-information on the filesystem itself. It includes information on the number of free and used blocks, block size, current filesystem status (needed when booting the system in order to detect a previous crash), and various time stamps (e.g., time of last filesystem mount, time of last write operation). It also includes a magic number so that the mount routine can establish whether the filesystem is of the correct type.

The kernel uses only the superblock of the first block group to read filesystem meta-information, even if there are superblock objects in several block groups.

□ The group descriptors contain information that reflects the status of the individual block groups of the filesystem, for instance, information on the number of free blocks and inodes of the group. Each block group includes group descriptors for all block groups of the filesystem.

□ Data block and inode bitmaps are used to hold long bit strings. These structures contain exactly 1 bit for each data block and each inode to indicate whether the block or inode is free or in use.

□ The inode table contains all block group inodes that hold all metadata associated with the individual files and directories of the filesystem.

□ As the name suggests, the data block section contains the useful data of the files in the filesystem.

Whereas inodes and block bitmaps always occupy an entire block, the remaining elements consist of several blocks. The exact number depends not only on the options selected when creating the filesystem but also on the size of the storage medium.

The similarity of these structures with the elements of the virtual filesystem (and the general concept of Unix filesystems as discussed in Chapter 8) is unmistakable. Even though many problems, such as directory representation, are solved by adopting this structure, the Ext2 filesystem still needs to address several tricky issues.

A key problem in filesystem implementation is the fact that the individual files may differ drastically — in terms of their size and purpose. While files with multimedia contents (e.g., videos) or large databases can easily consume hundreds of megabytes or even gigabytes, small configuration files often take up just a handful of bytes. There are also different types of meta-information. For example, the information stored for device files differs from that for directories, regular files, or named pipes.

If filesystem contents are manipulated in memory only, these problems are not as serious as when data are stored on slow external media. High-speed RAM is able to set up, scan, and modify the required structures in no time at all, whereas the same operations are much slower and much more costly on hard disk.

The structures used to store data must be designed to optimally satisfy all filesystem requirements — not always an easy task on hard disks, particularly with regard to capacity utilization and access speed. The Second Extended Filesystem therefore resorts to the tricks and dodges described below.

Continue reading here: Indirection

Was this article helpful?

0 0