[lkml]   [1999]   [Jan]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: dcache problems with vfat
    From: "Steven N. Hirsch" <>

On 6 Jan 1999, Magnus Ahltorp wrote:

> > Oh, crap. The list_empty(&dentry->d_subdirs) test in d_invalidate() should
> > be a test for d_children, not d_subdirs!

[Nice to see d_children used intuitively here - I wrote the same independently]

> Are these lists only documented in code, or are they documented
> somewhere else? It's not very easy to get hold of what all these lists
> do when you see them for the first time.

I couldn't agree more.

Please find some notes below that I wrote yesterday or so to get
a feeling how this dentry stuff works. Roughly speaking the code
is a pleasure to read, but some vfat and nfs stuff is very ugly,
and the rename code in various filesystems is bad as well.
Anyway - some fragments of text below. Enjoy (or complain about
mistakes or misunderstandings). Maybe I can find time to write
part two one of these days.


Some dcache details

A traditional Unix system has inodes (`index nodes') as in-core
descriptors of files. An inode refers to the actual file, not
to a directory entry naming it. Linux v2.1.43 introduced dentries
(`directory entries') as in-core descriptors of file names.

The entire purpose of dentries is to make the map
filename -> inode fast. An interesting side effect
is that the kernel knows what name was used to open a file
and that a system call getcwd() is possible.

Thus, the central part of the dcache code are the lines
dentry = reserved_lookup(base, &this);
if (!dentry) {
dentry = cached_lookup(base, &this);
if (!dentry)
dentry = real_lookup(base, &this);
in namei.c. The reserved_lookup() takes care of . and ..;
the cached_lookup() is what we have the dcache for,
and the real_lookup() goes to the filesystem.

The cached_lookup() returns the value of d_lookup(),
but does a d_revalidate() before returning, and if that fails
and the dentry has no children, it returns NULL.
[This is a rather obscure part. The d_revalidate()
is allowed to fail for any reason - for example,
autofs uses a timeout to make d_revalidate fail -
which means that the final dentry we come up with
need not be the dentry that d_lookup() found.
This causes bugs in the vfat filesystem.
Moreover, if d_revalidate(D) fails but D still has
children, then D is used anyway.
This also causes bugs in the vfat filesystem.
I think also nfs has problems.]

A struct dentry has five members of type struct list_head:
struct list_head d_hash; /* lookup hash list */
struct list_head d_lru; /* d_count = 0 LRU list */
struct list_head d_child; /* child of parent list */
struct list_head d_subdirs; /* our children */
struct list_head d_alias; /* inode alias list */

[Some of these names were very badly chosen, and lead
to confusion all the time. We should do a global replace
changing d_subdirs into d_children and d_child into d_sister.]

1. d_hash

The d_hash field of a dentry links the dentry into
the list of dentries for filenames with a given hash value
with list head dentry_hashtable[hashvalue] defined in dcache.c.
This list is used in d_lookup() to find a dentry with given name
and parent. It is used in d_validate() to find a dentry with
known hash and parent.
[The present code takes the parent into account when
computing a hash. Not doing this would make the code
simpler and faster, possibly at the expense of a few
more collisions. Has anyone investigated this?]
The d_hash field is an empty list when the file is a mount point
(cf. d_validate) or has been deleted, or when the dentry was
dropped for some other reason.

d_add(D,I) will put D into its hash chain and provide it
with the inode I. It is called by all filesystem lookup routines.

d_drop(D) will remove D from its hash chain. A dentry is called
`unhashed' when its d_hash field is an empty list.
Sometimes dentries are dropped temporarily to make sure
no lookup will find them. The general routine vfs_rmdir(I,D)
will drop D if d_count=2, so that all filesystem rmdir()
routines can return -EBUSY when D still occurs in the hash list.
The filesystem routines for unlink and rmdir call d_delete()
which again calls d_drop().

[The d_hash field is referred to in many places that should
not know about its existence, in the phrase
if (list_empty(&dentry->d_hash)) ...
No doubt there should be a line
#define unhashed(d) (list_empty(&(d)->d_hash))
in dcache.h, together with a comment describing the semantics
of being unhashed. Then all these occurrences of d_hash can
be removed. Next, d_drop() should be renamed d_unhash().]

The dentry for the root of a mounted filesystem is returned by
d_alloc_root() and is unhashed.

2. d_lru
The simplest list is the one joining the d_lru fields of
dentries that had d_count = 0 at some point in time.
The list head is the variable dentry_unused defined in dcache.c.
The number of elements in this list is dentry_stat.nr_unused.
There are no references to the d_lru field outside dcache.[ch].

Note that d_count is incremented by dget(), invoked by d_lookup(),
without removing the dentry from the LRU list. Thus, anyone hoping
to find unused dentries on this list must first check d_count.
If a dentry is not on the LRU list, its d_lru field is an
empty list (initialized by d_alloc()).

dput(D) tries to get rid of D altogether when d_count = 0, but
puts D at the head of the LRU list if it is still on the hash list.
Thus, every D with d_count = 0 will be on the LRU list.

select_dcache(ict,pct) removes D with d_count > 0 from the
LRU list, and moves D that are ready to be sacrificed for memory
to the end of the list. (If ict and/or pct is given, then we are
satisfied when the selected D's involve ict inodes or pct pages.)

prune_dcache(ct) removes D with d_count > 0 from the LRU list,
and frees unused D, stopping when ct of them have been freed.

shrink_dcache_sb(sb) removes all unused D with given superblock
from the LRU list.

select_parent(D) move all unused descendants of D to the end
of the LRU list.

3. d_child and d_subdirs
As already noted, the names are terrible. The d_child field
does not refer to a child but to a sibling, and the d_subdirs
field does not refer to a subdirectory but to a child, directory
or not. These two fields form a threaded tree: the d_subdirs field
points to the first child, and the d_child field is member of the
circularly linked list of all children of one parent.

To be more precise: this circularly linked list of all children
of one parent P passes through the d_child fields of all children
and through the d_subdirs field of the parent P.

4. d_alias
Somewhat similar to the above, where we had a circularly linked list
with one special element, we here have a circularly linked list
passing through the d_alias field of all dentries that are aliases
of one inode, and through the i_dentry field of the inode.

The dentry is added to this list by d_instantiate().
It is removed again by dentry_iput() which is called by dput()
and d_delete().

So far about the lists in the dentry structure.
Some of the routines in dcache.c have been mentioned already.
Let me describe one of the more obscure ones.

d_move(D,T) is the routine called by the filesystem code
just before finishing the rename(D,T) call. Since both
dentries D and T may be busy we cannot just throw one away.
Instead they are partially interchanged:
D and T interchange names, and D is put into T's hash queue,
and T is unhashed; D and T interchange parents, and are put
on the list of children of their new parent.
The result is that the file D that got renamed is now in perfect
shape again - it has been renamed. T, if it existed, lost its
name string, if it was short, but perhaps this is harmless -
let us hope no-one will ever ask for T's name anymore.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:49    [W:0.048 / U:10.384 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site