I get the same confusion in multi-level paging as well. For inodes, we have direct and indirect pointers that point to data blocks. However, for small files we prefer to use indirect pointers since they can store a lot more pointers for our purpose.

However, why is it more data-consuming to store direct pointers in sequence at one level and less so if we use indirect pointers? Surely the pointers all must exist at some place in the filesystem, and incur the same amount of space, don't they? Where does this extra space come from?

Here is an example of what I think: If I have 10 direct pointers and 2 indirect pointers, each of which lead to 128 and 128^2 pointers respectively, will the total size consumed be the same as having 10 + 128 + 128^2 direct pointers? If not, how is the space saving done?

As a side question, what is the typical size of an inode and why do the sizes of inode vary?


The original hierarchy of the inodes levels works roughly like this:

You can store one or a few block numbers directly in the inode. This means you use a few bytes more for the inode, but for small files, you don't have to allocate a complete block, which is mostly empty.

The next level is one indirection: You allocate a block to store the block pointers. Only the address of this indirect block is stored in the inode. This doesn't use somehow "less space", and most filesystems, even early ones, worked like that (have a pointer near the inode/filename which points to a block, which stores the block numbers of the file).

But what do you do when the space in this block runs out? You have to allocate another block, but where do you store the reference to this block? You could just add those references to the inode, but to store largers files, the inode would get large. And you want small inodes, so as many as possible inodes can fit into a single block (less disk access to read more inodes).

So you use a two-level indirect block: You just add one pointer to the inode, then you have a whole block to store pointers to indirect blocks, and the indirect blocks store the block address of the file itself.

And so on, you can add higher-level indirect blocks, or stop at some stage, until you reach the maximal size of a file possible with the structure you want.

So the point is not "use up less space in total", but "use a scheme that uses blocks efficiently for the expected distribution a files wrt. to size, i.e. many small files, some larger files, and very few huge files".

Page tables on the other hand work very differently.


To answer the questions in the comment:

Data blocks are of fixed sizes (originally 512 bytes, IIRC), which is a multiple of the block size of the underlying harddisks. So data block size can't "decrease".

As I tried to describe above, the whole point of having the inodes not use up too much space is to make inode access faster (or, alternatively, make caching inodes use up less memory - back then when the unix file system with inodes was invented, computers had a lot less memory than today). It's not about somehow saving space in total. As you say yourself, everything has to be stored somewhere, and if it doesn't use up space at location X, it will use up space at location Y.

Just adding a variable number of block pointers to the inode is not practical, because the inode must take up a fixed amount of space - you want to use the inode number to calculate the block address and the offset inside the block where the inode information is stored. You can't do that if every inode has a different size. So there must be some form of indirection.

Page tables work differently because hardware implements them differently - that's just how it is. The hierarchy has a fixed depth, always the same (though sometimes configurable. And while reading a block from disk is slow, that doesn't matter for page tables. So the design issues are completely different.

  • Thanks for your answer. So does that mean in a disk partition made up of 1) a super block, 2) inode table and 3) data blocks, having more inode pointers mean the inode table size will increase, causing the data blocks size to decrease? Also, if there's no "less space" consumed, why do people not use direct pointers immediately then? Why do page tables work very differently? – oldselflearner1959 Mar 21 '18 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.