Files do not necessarily occupy successive data blocks although this would be desirable for performance reasons but are spread over the entire hard disk

A closer examination of this concept quickly reveals a problem. Maximum file size is limited by the number of block numbers that can be held in the inode structure. If this number is too small, less space is needed to manage the inode structures, but, at the same time, only small-sized files can be represented.

Increasing the number of blocks in the inode structure does not solve the problem, as the following quick calculation proves. The size of a data block is 4 KiB. To hold a file comprising 700 MiB, the filesystem would need approximately 175,000 data blocks. If a data block can be uniquely identified by a 4-byte number, the inode would need 175,000 x 4 bytes to store the information on all data blocks — this is impracticable because a large portion of disk space would be given over to storing inode information. What's more, most of this space would not be needed by most files, whose average size would be less than 700 MiB.

This is, of course, an age-old problem and is not Linux-specific. Fortunately, all Unix filesystems including Ext2 feature a proven solution known as indirection.5

With indirection, only a few bytes of the inode hold pointers to blocks — just enough to ensure that an average small-size file can be represented. With larger files, pointers to the individual data blocks are stored indirectly, as illustrated graphically in Figure 9-4.

Inode Indirection Data blocks

Inode Indirection Data blocks

5 Even the relatively primitive Minix filesystem supports indirection.

This approach permits the flexible storage of large and small files because the size of the area in which data block pointers is stored can be varied dynamically as a function of the actual size of the file. The inode itself is always of a fixed size, and additional data blocks needed for purposes of indirection are allocated dynamically.

Let's first take a look at the situation with a small file. The pointers stored directly in the inode are sufficient to identify all data blocks, and the inode structure occupies little hard disk space because it contains just a few pointers.

Indirection is used if the file is bigger and there aren't enough primary pointers for all blocks. The filesystem reserves a data block on the hard disk — not for file data but for additional block pointers. This block is referred to as a single indirect block and can accept hundreds of additional block pointers (the actual number varies according to the size of the block; Table 9-1 lists possible values for Ext2). The inode must include a pointer to the first indirection block so that it can be accessed. Figure 9-4 shows that in our example this pointer immediately follows the direct block pointers. The size of the inode always remains constant; the space needed for the additional pointer block is of some consequence with larger files but represents no additional overhead for small files.

Table 9-1: Block and File Sizes in the Second Extended Filesystem

Block size

Maximum file size

1,024

16 GiB

2,048

256 GiB

4,096

2 TiB

The further progress of indirection is evident from the illustration. Adding to available space by means of indirection must also come up against its limits when files get larger and larger. The next logical step is therefore to use double indirection. Again, a hard disk block is reserved to store pointers to data blocks. However, the latter do not store useful data but are arrays that hold pointers to other data blocks that, in turn, store the useful file data.

Using double indirection dramatically increases manageable space per file. If a data block holds pointers to 1,000 other data blocks, double indirection enables 1,000 x 1,000 data blocks to be addressed. Of course, the method has a downside because access to large files is more costly. The filesystem must first find the address of the indirection block, read a further indirection entry, look for the relevant block, and find the pointer to the data block address. There is therefore a trade-off between the ability to handle files of varying sizes and the associated reduction in speed (the larger the file, the slower the speed).

As Figure 9-4 shows, double indirection is not the end of the road. The kernel offers triple indirection to represent really gigantic files. This is an extension of the principle of simple and double indirection and is not discussed here.

Triple indirection takes maximum file size to such heights that other kernel-side problems crop up, particularly on 32-bit architectures. Because the standard library uses long variables with a length of

32 bits to address positions within a file, this restricts maximum file size to 232 bits, which corresponds to 2 GiB and is less than can be managed with triple indirection in the Ext2 filesystem. To cope with this drawback, a special scheme was introduced to access large files; this not only has an impact on the routines of the standard library, but must also be taken into account in the kernel sources.

Continue reading here: Fragmentation

Was this article helpful?

0 0