4

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.

Junji Zhi
  • 1,382
  • 1
  • 14
  • 22
  • Fromfs/ext2/dir.c : `/* * ext2_delete_entry deletes a directory entry by merging it with the * previous entry. Page is up-to-date. Releases the page. */` So you should use rec_len as an offset to to add to get to the new directory entry (which is at absolute offset 1004, so it will probably be an end-sentinel entry. – joop Mar 23 '15 at 15:38
  • You are right. rec_len is a signal. I will post my answer below. Thanks joop. – Junji Zhi Mar 23 '15 at 19:07
  • Well if rec_len = 1000, it adds up to 1024, meaning that the next entry would be on the next disk page (if any) – joop Mar 23 '15 at 19:19
  • You should (at least) post the code here that you used to obtain your resultst. crystal balls are scarse these days ... – wildplasser Mar 23 '15 at 23:25

1 Answers1

2

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.

Junji Zhi
  • 1,382
  • 1
  • 14
  • 22
  • This probably relates to the note in your link 'Since this value cannot be negative, when a file is removed the previous record within the block has to be modified to point to the next valid record within the block or _to the end of the block when no other directory entry is present_.' They probably should have said that explicitly rather than implying it in a note. – Samuel Edwin Ward Mar 24 '15 at 14:58