path-lookup.txt

Path walking and name lookup locking
====================================

On many workloads, the most common operation on dcache is to look up a dentry,
given a parent dentry and the name of the child. Typically, for every open(),
stat() etc., the dentry corresponding to the pathname will be looked up by
walking the tree starting with the first component of the pathname and using
that dentry along with the next component to look up the next level and so on.
Since it is a frequent operation for workloads like multiuser environments and
web servers, it is important to optimize this path.

Prior to 2.5.10, dcache_lock was acquired in d_lookup and thus in every
component during path look-up. Since 2.5.10 onwards, fast-walk algorithm
changed this by holding the dcache_lock at the beginning and walking as many
cached path component dentries as possible. This significantly decreases the
number of acquisition of dcache_lock. However it also increases the lock hold
time significantly and affects performance in large SMP machines. Since 2.5.62
kernel, dcache has been using a new locking model that uses RCU to make dcache
look-up lock-free. Since 2.6.XXX, RCU is used to make dcache look-up and a
significant part of the path walk completely "store-free" (so no atomics or
cacheline bouncing on common dentries).

Path walking overview
=====================

A name string specifies a start (root directory, cwd, fd-relative) and a
sequence of elements (directory entry names), which together refer to a path in
the namespace. The elements are strings seperated by '/'.

Name lookups will want to find a particular path that a name string refers to
(usually the path of the final element, or parent of final element). This is
done by taking the path given by the name's starting point (which we know in
advance -- eg.  current->fs->cwd) as the first parent of the lookup. Then
iteratively for each name element, look up the child of the current parent with
the given name and if it is not the final entry, make it the parent for the
next lookup.

The parent must of course be a directory, and we must have appropriate
permissions on the parent inode to be able to walk into it.

Making the child a parent for the next lookup requires more checks and
procedures. Symlinks essentially substitute the symlink name for the target
name in the name string, and require some recursive path walking.  Mount points
must be followed into, switching from the mount point path to the root of the
particular mounted vfsmount.

Safe store-free look-up of dcache hash table
============================================

Path walking then must, broadly, do several particular things:
- perform directory entry name lookups on (parent, name element) tuples;
- find the start point of the walk;
- perform permissions and validity checks on inodes;
- traverse mount points;
- traverse symlinks;
- lookup and create missing parts of the path on demand.

Dcache name lookup
------------------
In order to lookup a dcache (parent, name) tuple, we take a hash on the tuple
use that to select a bucket in the dcache-hash table, and then compare entries
on the hash list with our tuple.

The hash lists are RCU protected, so list walking is not serialised with
concurrent updates (insertion, deletion from the hash). This is a standard RCU
list application with the exception of renames which will be covered below.

Parent and name members of a dentry, as well as its membership in the dcache
hash, are protected by the per-dentry d_lock spinlock. Parent, name, and inode
members are also protected by d_seq seqlock, although this offers read-only
protection and no durability of results so care must be taken when using d_seq
for synchronisation.

So when walking the dcache hash list, we can lock each dentry in turn, which
then stabilises the entry, and then we can compare the parent and full name
string without races. If there is a match, the refcount is incremented and the
dentry can be unlocked and returned.

All other operations on the dentry such as removal from the hash table must be
performed under d_lock, so they are excluded until we have completed the
comparison and have a valid refcount.

Renames

Back to the rename case. In usual RCU protected lists, the only operations that
will happen to an object is insertion then removal from the list.  The object
will not be reused until an RCU grace period is complete. This ensures the RCU
list traversal primitives can run over the object without problems (see RCU
documentation for how this works).

However when a dentry is renamed, its hash value can change, requiring it to be
moved to a new hash list. Latency would be far to high to wait for a grace
period after removing the dentry and before inserting it in the new hash
bucket, so the dentry is inserted on the new list right away. When the dentry's
list pointers are updated to point to objects in the new list, this can result
in a concurrent RCU lookup of the old list veering off into the new (incorrect)
list and missing the remaining dentries on the list.

It is no problem to walk the wrong list, because the dentry comparisons will
not match. However it is fatal to miss a matching dentry. So a seqlock is used
to detect when a rename has occurred, and so the lookup can be retried.

         1      2      3
        +---+  +---+  +---+
hlist-->| N-+->| N-+->| N-+->
head <--+-P |<-+-P |<-+-P |
        +---+  +---+  +---+

Rename of dentry 2 may require it deleted from the above list, and inserted
into a new list. Deleting 2 gives the following list.

         1             3
        +---+         +---+     (don't worry, the longer pointers do not
hlist-->| N-+-------->| N-+->    impose a measurable performance overhead
head <--+-P |<--------+-P |      on modern CPUs)
        +---+         +---+
          ^      2      ^
          |    +---+    |
          |    | N-+----+
          +----+-P |
               +---+

This is a standard RCU-list deletion, which leaves the deleted object's
pointers intact, so a concurrent list walker that is currently looking at
object 2 will correctly continue to object 3 when it is time to traverse the
next object.

However, when inserting object 2 onto a new list, we end up with this:

         1             3
        +---+         +---+
hlist-->| N-+-------->| N-+->
head <--+-P |<--------+-P |
        +---+         +---+
                 2
               +---+
               | N-+---->
          <----+-P |
               +---+

Because we didn't wait for a grace period, there may be a concurrent lookup
still at 2. Now when it follows 2's 'next' pointer, it will walk off into
another list without ever having checked object 3.

A related, but distinctly different, issue is that of rename atomicity versus
lookup operations. If a file is renamed from 'A' to 'B', a lookup must only
find either 'A' or 'B'. So if a lookup of 'A' returns NULL, a subsequent lookup
of 'B' must succeed (note the reverse is not true).

Between deleting the dentry from the old hash list, and inserting it on the new
hash list, a lookup may find neither 'A' nor 'B' matching the dentry. The same
rename seqlock is also used to cover this race in much the same way, by
retrying a negative lookup result if a rename was in progress.

Seqcount based lookups

Instead of using d_lock to serialise concurrent access to the dentry while
performing the lookup, it is possible to use d_seq. d_seq protects all the
dentry members of interest, however they may be changed concurrently. Care must
be taken to load the members up-front, and not perform any destructive
operations (pretty much: no non-atomic stores to shared data), and to recheck
the seqcount when we are "done" with the operation. Retry or abort if the
seqcount does not match.

What this means is that a caller, provided they are holding RCU lock to
protect the dentry object from disappearing, can perform a seqcount based
lookup which does not increment the refcount on the dentry or write to
it in any way. This returned dentry can be used for subsequent operations
provided that d_seq is rechecked.

This is useful to perform dentry lookups of intermediate path elements without
any cacheline bouncing or lock contention. The returned dentries can be used
to perform subsequent dcache lookups, or we can take a refcount on them by
taking their d_lock, rechecking d_seq, and then incrementing their refcount.

RCU-walk path walking design
============================

Path walking code has two distinct modes, ref-walk and rcu-walk. ref-walk
is the traditional[*] way of performing dcache lookups using d_lock to
serialise concurrent modifications to the dentry and take a reference count
on it. ref-walk is simple and obvious, and may sleep, take locks, etc while
path walking is operating on each dentry. rcu-walk uses seqcount based
dentry lookups and can perform lookup of intermediate elements without
performing any stores to shared data in the dentry or inode. rcu-walk can
not be applied to all cases, eg. if the filesystem must sleep or perform
non trivial operations, rcu-walk must be switched to ref-walk.

[*] RCU is still used for the dentry hash lookup, but not the full path walk.

The overall design is like this:
* LOOKUP_RCU is set in nd->flags, which distinguishes rcu-walk from ref-walk.
* Take the RCU lock for the entire path walk, starting with the acquiring
  of the starting path (eg. root/cwd/fd-path). So now dentry refcounts are
  not required for dentry persistence.
* synchronize_rcu is called when unregistering a filesystem, so we can
  access d_ops and i_ops during rcu-walk.
* Similarly take the vfsmount lock for the entire path walk. So now mnt
  refcounts are not required for persistence. Also we are free to perform mount
  lookups, and to assume dentry mount points and mount roots are stable up and
  down the path.
* Have a per-dentry seqlock to protect the dentry name, parent, and inode,
  so we can load this tuple atomically, and also check whether any of its
  members have changed.
* Dentry lookups (based on parent, candidate string tuple) recheck the parent
  sequence after the child is found in case anything changed in the parent
  during the path walk.
* inode is also RCU protected so we can load d_inode and use the inode for
  limited things.
* i_mode, i_uid, i_gid can be tested for exec permissions during path walk.
* i_op can be loaded.

When we reach the destination dentry, we lock it, recheck lookup sequence,
and increment its refcount and mountpoint refcount. RCU and vfsmount locks
are dropped. This is termed "dropping rcu-walk". If the dentry seqcount does
not match, we can not drop rcu-walk gracefully at the current point in the
lokup, so instead return -ECHILD (for want of a better errno). This signals the
path walking code to re-do the entire lookup with a ref-walk.

Aside from the final dentry, there are other situations that may be encounted
where we cannot continue rcu-walk. In that case, we drop rcu-walk (ie. take
a reference on the last good dentry) and continue with a ref-walk. Again, if
we can drop rcu-walk gracefully, we return -ECHILD and do the whole lookup
using ref-walk. But it is very important that we can continue with ref-walk
for most cases, particularly to avoid the overhead of double lookups, and to
gain the scalability advantages on common path elements (like cwd and root).

The cases where rcu-walk cannot continue are:
* NULL dentry (ie. creat or negative lookup)
* parent with ->d_op->d_hash
* parent with d_inode->i_op->permission or ACLs
* Following links
* Dentry with ->d_op->d_revalidate

Apart from the first, it may be possible to make most of these cases RCU
walked. Though that would require a bit more poking into filesystems, so it
would be better to wait until the base infrastructure is converted.

Papers and other documentation on dcache locking
================================================

1. Scaling dcache with RCU (http://linuxjournal.com/article.php?sid=7124).

2. http://lse.sourceforge.net/locking/dcache/dcache.html