clinuxfileunixext2

ext2 directory entry list: Where is the end?

ext2 directory entry is persisted as a linked list. Quote from 1:

A directory file is a linked list of directory entry structures. Each structure contains the name of the entry, the inode associated with the data of this entry, and the distance within the directory file to the next entry.

But it doesn't say there is a terminator in the inode. Also, there isn't any field that tells how many entries there are in a directory inode.

So the question is: When you read the inode data structure, how do you know when it reaches the end of the list?

Example: Assume an empty root directory "/". So the command ls should print out something like this: 

drwxr-xr-x 4 junji junji  4096 Mar 23 10:33 .
drwxr-xr-x 7 junji junji  4096 Mar 23 10:27 ..
drwxr-xr-x 7 junji junji  4096 Mar 23 10:27 lost+found

When implementing ls, you have read the root inode struct from the disk, and then follow the i_blocks and try to get all the directory entries. At the disk, the entry list is actually stored like: 

{inode = 2, rec_len = 12, name_len = 1, name = .}
{inode = 2, rec_len = 12, name_len = 2, name = ..}
{inode = 12, rec_len = 1000, name_len = 6, name = lost+found}   
{inode = 12, rec_len = 12, name_len = 1, name = .}
{inode = 2, rec_len = 32, name_len = 2, name = ..}
...

There is another entry right next to the 3rd "lost+found" entry.

Clearly the program should stop at "lost+found" entry, because the next entry i.e., "." belongs to another directory. But how do we let our program know that? When do we know it's the end of the directory entry list?

Thanks!

EDIT:

The inode list has a little inconsitency. Specially, the rec_len of lost+found entry is 1000 instead of 980. I corrected it.

Solution

  • I figured it out. All entries of a directory should be fit into a data block whose size is fixed. For ext2, a data block is 1024.

    In the example above, the root inode only points to a single data block (i.e., i_blocks array has only one non-zero element). All entries in that data block belong to root. Beyond that, it is some other dirs'. 

    {inode = 2, rec_len = 12, name_len = 1, name = .}
{inode = 2, rec_len = 12, name_len = 2, name = ..}
{inode = 12, rec_len = 1000, name_len = 6, name = lost+found}
{inode = 12, rec_len = 12, name_len = 1, name = .}
{inode = 2, rec_len = 32, name_len = 2, name = ..}

    If you sum up all the rec_len value of the first 3 entries, 12+12+1000=1024, then it is already a data block size. That's the sentinel signal I was looking for. Beyond that, it is in another data block of another directory.