Re: Expected getdents behaviour

[Dave Kleikamp <shaggy@austin.ibm.com>]

On Thu, 2005-09-15 at 23:39 -0400, Theodore Ts'o wrote:
> JFS also uses a b-tree (or more than one b-tree) to index its
> directory, and also gives the same guarantee, but it implements it in
> an entirely different way.

Here are the detail of jfs's implementation.  Each directory entry is
assigned sequential "index" when it is created, which is stored in the
directory entry in the dtree (the primary directory data structure).  In
addition, an entry is created in the "index table", which is an array
keyed on the index.  Initially, this table can be stored directly in the
inode, but as it grows, the table is stored in other blocks, and is
addressed by a b-tree anchored in the inode.  For an existing entry, the
table stores the address of the dtree page, and the offset within the
page.  This table is updated whenever a change to the directory moves
the entry.  When an entry is deleted, the table contains the index of
the next existing entry in dtree-order.

Resuming a search means getting the table element for the index,
checking a flag whether it exists or has been deleted, following the
chain of "next" indices until an existing one is found, and getting the
dtree page address and offset of the entry.

The disadvantages are the need to update the directory table as entries
are moved, and the fact that the index table does not shrink as entries
are removed.  (The table is completely truncated if all entries are
removed from a directory, but that isn't typically going to happen.)

> Two different filesystems; two different strategies; both implement
> this guarantee without needing to lock the directory against
> modifications during the readdir() scan.  Take a look at the
> implementations closely.
> 
> (Hint: both involve walking the b-tree and returning readdir() entries
> in tree order.  The details though of which b-tree, how the b-tree is
> indexed, how the index is stored in file descriptor offset, and how
> telldir/seekdir are implemented are different in the two filesystems,
> however.)

-- 
David Kleikamp
IBM Linux Technology Center