Documentation/filesystems/path-lookup.txt - linux - Git at Google

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

 Path resolution is the finding a dentry corresponding to a path name string, by
 performing a path walk. Typically, for every open(), stat() etc., the path name
 will be resolved. Paths are resolved by walking the namespace tree, starting
 with the first component of the pathname (eg. root or cwd) with a known dentry,
 then finding the child of that dentry, which is named the next component in the
 path string. Then repeating the lookup from the child dentry and finding its
 child with the next element, and so on.

 Since it is a frequent operation for workloads like multiuser environments and
 web servers, it is important to optimize this code.

 Path walking synchronisation history:
 Prior to 2.5.10, dcache_lock was acquired in d_lookup (dcache hash 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.

 All the above algorithms required taking a lock and reference count on the
 dentry that was looked up, so that may be used as the basis for walking the
 next path element. This is inefficient and unscalable. It is inefficient
 because of the locks and atomic operations required for every dentry element
 slows things down. It is not scalable because many parallel applications that
 are path-walk intensive tend to do path lookups starting from a common dentry
 (usually, the root "/" or current working directory). So contention on these
 common path elements causes lock and cacheline queueing.

 Since 2.6.38, RCU is used to make a significant part of the entire path walk
 (including dcache look-up) completely "store-free" (so, no locks, atomics, or
 even stores into cachelines of common dentries). This is known as "rcu-walk"
 path walking.

 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. A path is represented as a (dentry, vfsmount) tuple. The name
 elements are sub-strings, separated by '/'.

 Name lookups will want to find a particular path that a name string refers to
 (usually 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 or current->fs->root) as the first parent of the lookup. Then
 iteratively for each subsequent name element, look up the child of the current
 parent with the given name and if it is not the desired entry, make it the
 parent for the next lookup.

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

 Turning the child into 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 (thus changing the vfsmount that subsequent path elements
 refer to), switching from the mount point path to the root of the particular
 mounted vfsmount. These behaviours are variously modified depending on the
 exact path walking flags.

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

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

 Dcache name lookup
 ------------------
 In order to lookup a dcache (parent, name) tuple, we take a hash on the tuple
 and use that to select a bucket in the dcache-hash table. The list of entries
 in that bucket is then walked, and we do a full comparison of each entry
 against our (parent, name) 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, and its inode are protected by the per-dentry d_lock spinlock. A
 reference is taken on the dentry (while the fields are verified under d_lock),
 and this stabilises its d_inode pointer and actual inode. This gives a stable
 point to perform the next step of our path walk against.

 These 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 (see seqcount based lookups, below).

 Renames
 -------
 Back to the rename case. In usual RCU protected lists, the only operations that
 will happen to an object is insertion, and then eventually 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. Allocating and inserting a new alias would be
 expensive and also problematic for directory dentries. 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 what is done is to insert the dentry into the
 new list immediately.

 However, when the dentry's list pointers are updated to point to objects in the
 new list before waiting for a grace period, 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.

 There is no fundamental problem with walking down the wrong list, because the
 dentry comparisons will never 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
 ----------------------
 In refcount based dcache lookups, d_lock is used to serialise access to
 the dentry, stabilising it while comparing its name and parent and then
 taking a reference count (the reference count then gives a stable place to
 start the next part of the path walk from).

 As explained above, we would like to do path walking without taking locks or
 reference counts on intermediate dentries along the path. To do this, a per
 dentry seqlock (d_seq) is used to take a "coherent snapshot" of what the dentry
 looks like (its name, parent, and inode). That snapshot is then used to start
 the next part of the path walk. When loading the coherent snapshot under d_seq,
 care must be taken to load the members up-front, and use those pointers rather
 than reloading from the dentry later on (otherwise we'd have interesting things
 like d_inode going NULL underneath us, if the name was unlinked).

 Also important is to avoid performing 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.
 Avoiding destructive or changing operations means we can easily unwind from
 failure.

 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 after that operation is complete.

 Inodes are also rcu freed, so the seqcount lookup dentry's inode may also be
 queried for permissions.

 With this two parts of the puzzle, we can do path lookups without taking
 locks or refcounts on dentry elements.

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

 Path walking code now 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 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 mode.

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

 Where ref-walk uses a stable, refcounted ``parent'' to walk the remaining
 path string, rcu-walk uses a d_seq protected snapshot. When looking up a
 child of this parent snapshot, we open d_seq critical section on the child
 before closing d_seq critical section on the parent. This gives an interlocking
 ladder of snapshots to walk down.


      proc 101
       /----------------\
      / comm:    "vi"    \
     /  fs.root: dentry0  \
     \  fs.cwd:  dentry2  /
      \                  /
       \----------------/

 So when vi wants to open("/home/npiggin/test.c", O_RDWR), then it will
 start from current->fs->root, which is a pinned dentry. Alternatively,
 "./test.c" would start from cwd; both names refer to the same path in
 the context of proc101.

      dentry 0
     +---------------------+   rcu-walk begins here, we note d_seq, check the
     | name:    "/"        |   inode's permission, and then look up the next
     | inode:   10         |   path element which is "home"...
     | children:"home", ...|
     +---------------------+
               |
      dentry 1 V
     +---------------------+   ... which brings us here. We find dentry1 via
     | name:    "home"     |   hash lookup, then note d_seq and compare name
     | inode:   678        |   string and parent pointer. When we have a match,
     | children:"npiggin"  |   we now recheck the d_seq of dentry0. Then we
     +---------------------+   check inode and look up the next element.
               |
      dentry2  V
     +---------------------+   Note: if dentry0 is now modified, lookup is
     | name:    "npiggin"  |   not necessarily invalid, so we need only keep a
     | inode:   543        |   parent for d_seq verification, and grandparents
     | children:"a.c", ... |   can be forgotten.
     +---------------------+
               |
      dentry3  V
     +---------------------+   At this point we have our destination dentry.
     | name:    "a.c"      |   We now take its d_lock, verify d_seq of this
     | inode:   14221      |   dentry. If that checks out, we can increment
     | children:NULL       |   its refcount because we're holding d_lock.
     +---------------------+

 Taking a refcount on a dentry from rcu-walk mode, by taking its d_lock,
 re-checking its d_seq, and then incrementing its refcount is called
 "dropping rcu" or dropping from rcu-walk into ref-walk mode.

 It is, in some sense, a bit of a house of cards. If the seqcount check of the
 parent snapshot fails, the house comes down, because we had closed the d_seq
 section on the grandparent, so we have nothing left to stand on. In that case,
 the path walk must be fully restarted (which we do in ref-walk mode, to avoid
 live locks). It is costly to have a full restart, but fortunately they are
 quite rare.

 When we reach a point where sleeping is required, or a filesystem callout
 requires ref-walk, then instead of restarting the walk, we attempt to drop rcu
 at the last known good dentry we have. Avoiding a full restart in ref-walk in
 these cases is fundamental for performance and scalability because blocking
 operations such as creates and unlinks are not uncommon.

 The detailed design for rcu-walk 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 the destination dentry is reached, drop rcu there (ie. take d_lock,
   verify d_seq, increment refcount).
 * If seqlock verification fails anywhere along the path, do a full restart
   of the path lookup in ref-walk mode. -ECHILD tends to be used (for want of
   a better errno) to signal an rcu-walk failure.

 The cases where rcu-walk cannot continue are:
 * NULL dentry (ie. any uncached path element)
 * Following links

 It may be possible eventually to make following links rcu-walk aware.

 Uncached path elements will always require dropping to ref-walk mode, at the
 very least because i_mutex needs to be grabbed, and objects allocated.

 Final note:
 "store-free" path walking is not strictly store free. We take vfsmount lock
 and refcounts (both of which can be made per-cpu), and we also store to the
 stack (which is essentially CPU-local), and we also have to take locks and
 refcount on final dentry.

 The point is that shared data, where practically possible, is not locked
 or stored into. The result is massive improvements in performance and
 scalability of path resolution.


 Interesting statistics
 ======================

 The following table gives rcu lookup statistics for a few simple workloads
 (2s12c24t Westmere, debian non-graphical system). Ungraceful are attempts to
 drop rcu that fail due to d_seq failure and requiring the entire path lookup
 again. Other cases are successful rcu-drops that are required before the final
 element, nodentry for missing dentry, revalidate for filesystem revalidate
 routine requiring rcu drop, permission for permission check requiring drop,
 and link for symlink traversal requiring drop.

      rcu-lookups     restart  nodentry          link  revalidate  permission
 bootup     47121           0      4624          1010       10283        7852
 dbench  25386793           0   6778659(26.7%)     55         549        1156
 kbuild   2696672          10     64442(2.3%)  108764(4.0%)     1        1590
 git diff   39605           0        28             2           0         106
 vfstest 24185492        4945    708725(2.9%) 1076136(4.4%)     0        2651

 What this shows is that failed rcu-walk lookups, ie. ones that are restarted
 entirely with ref-walk, are quite rare. Even the "vfstest" case which
 specifically has concurrent renames/mkdir/rmdir/ creat/unlink/etc to exercise
 such races is not showing a huge amount of restarts.

 Dropping from rcu-walk to ref-walk mean that we have encountered a dentry where
 the reference count needs to be taken for some reason. This is either because
 we have reached the target of the path walk, or because we have encountered a
 condition that can't be resolved in rcu-walk mode.  Ideally, we drop rcu-walk
 only when we have reached the target dentry, so the other statistics show where
 this does not happen.

 Note that a graceful drop from rcu-walk mode due to something such as the
 dentry not existing (which can be common) is not necessarily a failure of
 rcu-walk scheme, because some elements of the path may have been walked in
 rcu-walk mode. The further we get from common path elements (such as cwd or
 root), the less contended the dentry is likely to be. The closer we are to
 common path elements, the more likely they will exist in dentry cache.


 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

 3. path-lookup.md in this directory.
	Path walking and name lookup locking
	====================================

	Path resolution is the finding a dentry corresponding to a path name string, by
	performing a path walk. Typically, for every open(), stat() etc., the path name
	will be resolved. Paths are resolved by walking the namespace tree, starting
	with the first component of the pathname (eg. root or cwd) with a known dentry,
	then finding the child of that dentry, which is named the next component in the
	path string. Then repeating the lookup from the child dentry and finding its
	child with the next element, and so on.

	Since it is a frequent operation for workloads like multiuser environments and
	web servers, it is important to optimize this code.

	Path walking synchronisation history:
	Prior to 2.5.10, dcache_lock was acquired in d_lookup (dcache hash 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.

	All the above algorithms required taking a lock and reference count on the
	dentry that was looked up, so that may be used as the basis for walking the
	next path element. This is inefficient and unscalable. It is inefficient
	because of the locks and atomic operations required for every dentry element
	slows things down. It is not scalable because many parallel applications that
	are path-walk intensive tend to do path lookups starting from a common dentry
	(usually, the root "/" or current working directory). So contention on these
	common path elements causes lock and cacheline queueing.

	Since 2.6.38, RCU is used to make a significant part of the entire path walk
	(including dcache look-up) completely "store-free" (so, no locks, atomics, or
	even stores into cachelines of common dentries). This is known as "rcu-walk"
	path walking.

	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. A path is represented as a (dentry, vfsmount) tuple. The name
	elements are sub-strings, separated by '/'.

	Name lookups will want to find a particular path that a name string refers to
	(usually 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 or current->fs->root) as the first parent of the lookup. Then
	iteratively for each subsequent name element, look up the child of the current
	parent with the given name and if it is not the desired entry, make it the
	parent for the next lookup.

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

	Turning the child into 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 (thus changing the vfsmount that subsequent path elements
	refer to), switching from the mount point path to the root of the particular
	mounted vfsmount. These behaviours are variously modified depending on the
	exact path walking flags.

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

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

	Dcache name lookup
	------------------
	In order to lookup a dcache (parent, name) tuple, we take a hash on the tuple
	and use that to select a bucket in the dcache-hash table. The list of entries
	in that bucket is then walked, and we do a full comparison of each entry
	against our (parent, name) 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, and its inode are protected by the per-dentry d_lock spinlock. A
	reference is taken on the dentry (while the fields are verified under d_lock),
	and this stabilises its d_inode pointer and actual inode. This gives a stable
	point to perform the next step of our path walk against.

	These 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 (see seqcount based lookups, below).

	Renames
	-------
	Back to the rename case. In usual RCU protected lists, the only operations that
	will happen to an object is insertion, and then eventually 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. Allocating and inserting a new alias would be
	expensive and also problematic for directory dentries. 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 what is done is to insert the dentry into the
	new list immediately.

	However, when the dentry's list pointers are updated to point to objects in the
	new list before waiting for a grace period, 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.

	There is no fundamental problem with walking down the wrong list, because the
	dentry comparisons will never 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
	----------------------
	In refcount based dcache lookups, d_lock is used to serialise access to
	the dentry, stabilising it while comparing its name and parent and then
	taking a reference count (the reference count then gives a stable place to
	start the next part of the path walk from).

	As explained above, we would like to do path walking without taking locks or
	reference counts on intermediate dentries along the path. To do this, a per
	dentry seqlock (d_seq) is used to take a "coherent snapshot" of what the dentry
	looks like (its name, parent, and inode). That snapshot is then used to start
	the next part of the path walk. When loading the coherent snapshot under d_seq,
	care must be taken to load the members up-front, and use those pointers rather
	than reloading from the dentry later on (otherwise we'd have interesting things
	like d_inode going NULL underneath us, if the name was unlinked).

	Also important is to avoid performing 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.
	Avoiding destructive or changing operations means we can easily unwind from
	failure.

	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 after that operation is complete.

	Inodes are also rcu freed, so the seqcount lookup dentry's inode may also be
	queried for permissions.

	With this two parts of the puzzle, we can do path lookups without taking
	locks or refcounts on dentry elements.

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

	Path walking code now 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 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 mode.

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

	Where ref-walk uses a stable, refcounted ``parent'' to walk the remaining
	path string, rcu-walk uses a d_seq protected snapshot. When looking up a
	child of this parent snapshot, we open d_seq critical section on the child
	before closing d_seq critical section on the parent. This gives an interlocking
	ladder of snapshots to walk down.


	proc 101
	/----------------\
	/ comm: "vi" \
	/ fs.root: dentry0 \
	\ fs.cwd: dentry2 /
	\ /
	\----------------/

	So when vi wants to open("/home/npiggin/test.c", O_RDWR), then it will
	start from current->fs->root, which is a pinned dentry. Alternatively,
	"./test.c" would start from cwd; both names refer to the same path in
	the context of proc101.

	dentry 0
	+---------------------+ rcu-walk begins here, we note d_seq, check the
	\| name: "/" \| inode's permission, and then look up the next
	\| inode: 10 \| path element which is "home"...
	\| children:"home", ...\|
	+---------------------+
	\|
	dentry 1 V
	+---------------------+ ... which brings us here. We find dentry1 via
	\| name: "home" \| hash lookup, then note d_seq and compare name
	\| inode: 678 \| string and parent pointer. When we have a match,
	\| children:"npiggin" \| we now recheck the d_seq of dentry0. Then we
	+---------------------+ check inode and look up the next element.
	\|
	dentry2 V
	+---------------------+ Note: if dentry0 is now modified, lookup is
	\| name: "npiggin" \| not necessarily invalid, so we need only keep a
	\| inode: 543 \| parent for d_seq verification, and grandparents
	\| children:"a.c", ... \| can be forgotten.
	+---------------------+
	\|
	dentry3 V
	+---------------------+ At this point we have our destination dentry.
	\| name: "a.c" \| We now take its d_lock, verify d_seq of this
	\| inode: 14221 \| dentry. If that checks out, we can increment
	\| children:NULL \| its refcount because we're holding d_lock.
	+---------------------+

	Taking a refcount on a dentry from rcu-walk mode, by taking its d_lock,
	re-checking its d_seq, and then incrementing its refcount is called
	"dropping rcu" or dropping from rcu-walk into ref-walk mode.

	It is, in some sense, a bit of a house of cards. If the seqcount check of the
	parent snapshot fails, the house comes down, because we had closed the d_seq
	section on the grandparent, so we have nothing left to stand on. In that case,
	the path walk must be fully restarted (which we do in ref-walk mode, to avoid
	live locks). It is costly to have a full restart, but fortunately they are
	quite rare.

	When we reach a point where sleeping is required, or a filesystem callout
	requires ref-walk, then instead of restarting the walk, we attempt to drop rcu
	at the last known good dentry we have. Avoiding a full restart in ref-walk in
	these cases is fundamental for performance and scalability because blocking
	operations such as creates and unlinks are not uncommon.

	The detailed design for rcu-walk 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 the destination dentry is reached, drop rcu there (ie. take d_lock,
	verify d_seq, increment refcount).
	* If seqlock verification fails anywhere along the path, do a full restart
	of the path lookup in ref-walk mode. -ECHILD tends to be used (for want of
	a better errno) to signal an rcu-walk failure.

	The cases where rcu-walk cannot continue are:
	* NULL dentry (ie. any uncached path element)
	* Following links

	It may be possible eventually to make following links rcu-walk aware.

	Uncached path elements will always require dropping to ref-walk mode, at the
	very least because i_mutex needs to be grabbed, and objects allocated.

	Final note:
	"store-free" path walking is not strictly store free. We take vfsmount lock
	and refcounts (both of which can be made per-cpu), and we also store to the
	stack (which is essentially CPU-local), and we also have to take locks and
	refcount on final dentry.

	The point is that shared data, where practically possible, is not locked
	or stored into. The result is massive improvements in performance and
	scalability of path resolution.


	Interesting statistics
	======================

	The following table gives rcu lookup statistics for a few simple workloads
	(2s12c24t Westmere, debian non-graphical system). Ungraceful are attempts to
	drop rcu that fail due to d_seq failure and requiring the entire path lookup
	again. Other cases are successful rcu-drops that are required before the final
	element, nodentry for missing dentry, revalidate for filesystem revalidate
	routine requiring rcu drop, permission for permission check requiring drop,
	and link for symlink traversal requiring drop.

	rcu-lookups restart nodentry link revalidate permission
	bootup 47121 0 4624 1010 10283 7852
	dbench 25386793 0 6778659(26.7%) 55 549 1156
	kbuild 2696672 10 64442(2.3%) 108764(4.0%) 1 1590
	git diff 39605 0 28 2 0 106
	vfstest 24185492 4945 708725(2.9%) 1076136(4.4%) 0 2651

	What this shows is that failed rcu-walk lookups, ie. ones that are restarted
	entirely with ref-walk, are quite rare. Even the "vfstest" case which
	specifically has concurrent renames/mkdir/rmdir/ creat/unlink/etc to exercise
	such races is not showing a huge amount of restarts.

	Dropping from rcu-walk to ref-walk mean that we have encountered a dentry where
	the reference count needs to be taken for some reason. This is either because
	we have reached the target of the path walk, or because we have encountered a
	condition that can't be resolved in rcu-walk mode. Ideally, we drop rcu-walk
	only when we have reached the target dentry, so the other statistics show where
	this does not happen.

	Note that a graceful drop from rcu-walk mode due to something such as the
	dentry not existing (which can be common) is not necessarily a failure of
	rcu-walk scheme, because some elements of the path may have been walked in
	rcu-walk mode. The further we get from common path elements (such as cwd or
	root), the less contended the dentry is likely to be. The closer we are to
	common path elements, the more likely they will exist in dentry cache.


	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

	3. path-lookup.md in this directory.