File Systems 257z Three timestamps: time of last access to the file (shown by ls –lu), time of last
modification of the file (the default time shown by ls –l), and time of last status
change (last change to i-node information, shown by ls –lc). As on other UNIX
implementations, it is notable that most Linux file systems don’t record the
creation time of a file.
z Number of hard links to the file.
z Size of the file in bytes.
z Number of blocks actually allocated to the file, measured in units of 512-byte
blocks. There may not be a simple correspondence between this number and
the size of the file in bytes, since a file can contain holes (Section 4.7), and thus
require fewer allocated blocks than would be expected according to its nomi-
nal size in bytes.
z Pointers to the data blocks of the file.
I-nodes and data block pointers in ext2
Like most UNIX file systems, the ext2 file system doesn’t store the data blocks of a
file contiguously or even in sequential order (though it does attempt to store them
close to one another). To locate the file data blocks, the kernel maintains a set of
pointers in the i-node. The system used for doing this on the ext2 file system is
shown in Figure 14-2.
Removing the need to store the blocks of a file contiguously allows the file
system to use space in an efficient way. In particular, it reduces the incidence
of fragmentation of free disk space—the wastage created by the existence of
numerous pieces of noncontiguous free space, all of which are too small to
use. Put conversely, we could say that the advantage of efficiently using the
free disk space is paid for by fragmenting files in the filled disk space.Under ext2, each i-node contains 15 pointers. The first 12 of these pointers (num-
bered 0 to 11 in Figure 14-2) point to the location in the file system of the first 12 blocks
of the file. The next pointer is a pointer to a block of pointers that give the locations of
the thirteenth and subsequent data blocks of the file. The number of pointers in
this block depends on the block size of the file system. Each pointer requires 4 bytes,
so there may be from 256 pointers (for a 1024-byte block size) to 1024 pointers (for
a 4096-byte block size). This allows for quite large files. For even larger files, the
fourteenth pointer (numbered 13 in the diagram) is a double indirect pointer—it points
to blocks of pointers that in turn point to blocks of pointers that in turn point to
data blocks of the file. And should the need for a truly enormous file arise, there is
a further level of indirection: the last pointer in the i-node is a triple-indirect pointer.
This seemingly complex system is designed to satisfy a number of require-
ments. To begin with, it allows the i-node structure to be a fixed size, while at the
same time allowing for files of an arbitrary size. Additionally, it allows the file sys-
tem to store the blocks of a file noncontiguously, while also allowing the data to be
accessed randomly via lseek(); the kernel just needs to calculate which pointer(s) to
follow. Finally, for small files, which form the overwhelming majority of files on
most systems, this scheme allows the file data blocks to be accessed rapidly via the
direct pointers of the i-node.