Re: readdir hypothesis on struct dirent ino_t value

[Eric Blake <ebb9 at byu dot net>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to xavier Guerin on 9/23/2008 7:25 AM:
> Hi guys,
> 
> I've a question related to the implementation of the readdir () function
> in the POSIX sub-folder.
> File readdir.c, line 95, the function assume that if dp -> p_ino is
> equal to 0, then the entry need to be skipped.
> 
> However, I've seen no behavior hypothesis concerning the value of the dp
> -> p_ino value either in the man 2 readdir,
> the man 2 getdents, or the in the readdir page in the opengroup website.
> 
> Can anyone explain why newlib's readdir behaves this way ?

This goes back to the olden days, when a directory was literally a
sequence of struct dirent objects, and unlink() was implemented by zeroing
the inode value within the appropriate dirent.  Additionally, a directory
with less than 512/sizeof(struct dirent) entries would have unused entries
at the end of the block, so the file system could be more efficient by
reading a block at a time, then determining which struct dirent locations
within the block were valid.  The assumption is that no valid file will
ever have an inode of 0, so 0 can be used as the special case of a
placeholder slot rather than a real entry.  And on file systems where
inodes are merely an index into physical disk locations, then this
assumption holds true - the first inode in a formatted disk holds the
superblock information about the disk formatting structure, so there is
never a valid file occupying that inode.

These days, though, most OS's now treat directories as opaque structures,
and readdir does some translation from that opaque structure into struct
dirent.  The assumption generally still holds that you will never see a
valid file at inode 0.  And the code in readdir() to skip 0 entries is now
dead code, since the OS will never return such an entry in the first place.

Meanwhile, there is research suggesting that recursive traversal is still
benefitted on many (but not all) file system types by sorting the
directory entries in inode order before statting any of the entries.  The
trick becomes determining which systems it helps (such as ext3) and which
it hurts (such as tmpfs).

- --
Don't work too hard, make some time for fun as well!

Eric Blake             ebb9@byu.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkjZjx4ACgkQ84KuGfSFAYA5LgCffPSU4UzjOgUacImpx0kDJrhz
ZWkAoLw+qrqb6dHahIkFKcwJBuUsWAN3
=Lo5X
-----END PGP SIGNATURE-----