I had written this answer for a number of related questions on Quora. I think the topic is worth a small article.
An inode for a file maintains the complete information about physical layout of file data. This information is stored in the form of a multi-level block map. Taking the example of a Unix Inode as explained in the “Design of Unix Operating System by Maurice Bach”, two types of data block pointers are kept within this block map.
When I mean block pointers, I basically mean data block numbers. Please note that these are always the logical block numbers and not the physical block numbers.
1. Direct block pointers – The block# contained in every direct block pointer is for the actual data block that contains the file data.
2. Indirect block pointers – These are very different from the direct data block pointers. Like a direct data block pointer, this also has a block#, but this block doesn’t contain the real file data. Instead, it has a set of direct data block numbers. Hence, they are termed as “indirect”.
Indirect block pointers can be usually classified as:
2.1 Single indirect pointer: One-level indirection implying the indirect block will contain a set of (limited by the size of block) of direct data block numbers.
2.2 Double indirect pointer: Two-level indirection implying the indirect block will contain a set of single indirect block numbers. Each of these single indirect blocks will have a set of direct data block numbers.
2.3 Triple indirect pointer: Three-level indirection implying the indirect block will contain a set of double indirect block numbers. Each double indirect block will have a set of single indirect block numbers and each indirect block will have a set of direct data block numbers.
Let’s understand this with the help of below diagram. For the discussion, assume the file system block size is 4K (4096 bytes), and a logical block number is 4 bytes. This implies that each indirect block (whether single, double or any level of indirection) can contain 1024 block pointers.
4096/4 = 1024 number of block pointers within each indirect block.
In the below diagram:
D1, D2, D3….D10 are direct block pointers where each individual pointer contains a block# for a direct data block — 23, 30, 25 etc. These are the file data blocks.
SI Block is a single indirect block pointer to an indirect block (block# 100). This single indirect block 100 is read first to get the list of 1024 direct data block numbers — 55, 82, 80 etc. These are the file data blocks.
Below shown is a DI Block pointer in inode. It contains the block# 103 which is a double indirect block consisting of 1024 single indirect block numbers, and rest is explained in the diagram.
For example, if a file is 1 GB in size implying file data is spread over 262144 blocks as the block size is 4K. If we plan to maintain this block map in a linear data structure, it will require us to maintain 262144 block pointers within inode which is indeed a lot. Inodes should be kept compact.
What if the file size grows to 2GB or 10 GB or 20 GB ? The size of inode will keep growing as the file size grows and hence the data structure used to maintain the block map will not scale well with the growth in file size.
Now, let’s see how does the multi level block map helps us.
As shown above, the inode has total 13 block pointers (Please note just 13 !!)
10 direct, 1 single indirect, 1 double indirect, and 1 triple indirect.
What size of file can be mapped using this sort of structure ?
For direct block pointers: 10 * 4K = 40KB
For a SI block pointer: 1024 *4K = 4MB
For a DI block pointer: 1024 *1024*4K = 4GB
For a TI block pointer: 1024 *1024*1024*4K = 4 TB
An inode with 10 direct block pointer with a SI block pointer maps the data layout for a file of about 4MB in size (4MB + 40KB).
An inode with 10 direct block pointer with SI, and DI block pointers maps the data layout for a file of about 4GB in size (4GB + 4MB + 40KB).
An inode with 10 direct block pointer with a SI, DI, and TI block pointers maps the data layout for a file of about 4TB in size (4TB + 4GB+ 4MB + 40KB).
Note that indirection comes at the cost of an additional block read of the indirect block(s) before reading the file data block. The level of indirection in the inode is dependent on the requirements of file system. If the file system has to support of files max 4GB in size, then the inode design can do away with 10 direct block pointers and each of SI and DI block pointers. So, it really depends on the requirements. Also, the number of direct data block pointers (10 in this case) can vary from one file system to another.
Loonytek - Delving into Tech 
Leave a Reply