Path walking and name lookup locking

경로 탐색과 동기화 방식의 역사

경로 해석은 pathname 문자열을 따라가 그 경로에 대응하는 dentry를 찾는 작업이다. `open()`, `stat()` 같은 호출이 들어오면, 커널은 root나 cwd처럼 이미 dentry를 알고 있는 첫 위치에서 시작해 문자열의 다음 component와 같은 이름을 가진 자식 dentry를 찾고, 그 자식을 새 부모로 삼아 이 과정을 반복한다.

다중 사용자 환경과 웹 서버처럼 경로 조회가 매우 빈번한 부하에서는 이 코드의 비용이 전체 성능을 좌우한다. Linux 2.5.10 이전에는 dcache hash lookup을 수행하는 `d_lookup`이 `dcache_lock`을 잡았으므로 모든 component마다 잠금 획득이 필요했다. 2.5.10의 fast-walk는 시작할 때 잠금을 한 번 잡고 cache된 component를 가능한 한 많이 걸어 잠금 횟수를 줄였지만, 잠금 유지 시간이 길어져 대형 SMP 시스템의 확장성을 해쳤다.

2.5.62부터 dcache lookup 자체는 RCU를 이용하는 lock-free 모델로 바뀌었다. 그러나 당시의 알고리즘도 다음 component의 기반으로 쓸 dentry에 lock과 reference count를 취해야 했다. root `/`나 cwd처럼 여러 작업이 공유하는 dentry에서 atomic operation과 cacheline 경합이 집중되므로, 이 방식은 component 수에 비례해 비효율적이고 병렬 부하에 잘 확장되지 않았다.

2.6.38부터는 dcache 조회를 포함한 경로 탐색의 상당 부분을 공용 dentry cacheline에 lock, atomic operation, store를 수행하지 않는 방식으로 처리한다. 이 문서가 이를 `rcu-walk` pathname walking이라 부른다. 여기서 store-free는 공용 경로 객체에 흔적을 남기지 않는다는 설계 목표를 뜻한다.

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

Path walking 개요

이름 문자열은 시작 위치(root directory, cwd 또는 fd-relative 위치)와 `/`로 구분된 directory entry 이름의 연속을 지정한다. namespace 안의 경로는 `(dentry, vfsmount)` 튜플로 표현된다.

이름 조회는 보통 최종 element 자체 또는 그 부모를 찾는다. 커널은 `current->fs->cwd`, `current->fs->root`처럼 미리 아는 시작 path를 첫 부모로 삼고, 각 name element에 해당하는 자식을 반복해 찾는다. 목적 entry가 아니면 그 자식이 다음 lookup의 부모가 된다. 부모는 반드시 directory여야 하며, 그 inode 안으로 들어갈 적절한 권한도 있어야 한다.

자식을 다음 부모로 바꾸는 과정에는 추가 절차가 따른다. symbolic link는 이름 문자열의 해당 부분을 link target으로 치환하므로 재귀적인 경로 탐색이 필요하다. mount point를 만나면 mount point path에서 mounted `vfsmount`의 root로 전환하고, 이후 component는 새 mount를 기준으로 해석한다. 구체적인 동작은 path walking flag에 따라 달라진다.

따라서 경로 탐색은 시작점을 정하고, inode 권한과 유효성을 검사하며, `(parent, name element)`를 dcache hash에서 찾고, mount point와 symbolic link를 통과하며, cache에 없는 경로 일부를 필요할 때 조회하거나 생성해야 한다.

=====================

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

Store-free dcache hash lookup

dcache에서 `(parent, name)` 튜플을 찾을 때는 이 튜플의 hash로 bucket을 고른 뒤 bucket의 entry 목록을 걸으며 각 entry를 완전히 비교한다. hash list는 RCU로 보호되므로 조회 중의 list traversal은 동시 insertion이나 deletion과 직렬화되지 않는다. rename을 제외하면 전형적인 RCU list 사용법이다.

dentry의 parent와 name, dcache hash membership, inode는 dentry별 `d_lock` spinlock이 보호한다. refcount 기반 조회에서는 `d_lock` 아래에서 이 필드들을 확인한 뒤 dentry reference를 얻는다. 그러면 `d_inode` pointer와 실제 inode가 안정되어 다음 path-walk 단계의 기반으로 사용할 수 있다.

같은 필드들은 `d_seq` seqlock의 보호도 받는다. 다만 `d_seq`는 읽기 전용 일관성만 제공하고 결과를 지속적으로 고정하지 않는다. 그러므로 seqcount 기반 조회에서는 snapshot을 사용한 작업이 끝난 뒤 sequence를 다시 확인해야 한다.

============================================

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).

Rename과 RCU hash list 진입 문제

일반적인 RCU 보호 list에서는 객체가 삽입되고 나중에 제거되며, RCU grace period가 끝날 때까지 객체를 재사용하지 않는다. 이 규칙 덕분에 동시 list walker가 제거된 객체를 지나더라도 안전하다.

그러나 dentry를 rename하면 hash 값이 달라져 다른 hash list로 옮겨야 할 수 있다. 새 alias를 할당해 삽입하는 것은 비싸고 directory dentry에는 문제를 일으킨다. 이전 bucket에서 제거한 뒤 grace period가 끝날 때까지 기다렸다가 새 bucket에 삽입하는 지연도 허용하기 어렵다. 그래서 실제 구현은 제거한 dentry를 새 list에 즉시 삽입한다.

grace period 전에 dentry의 list pointer를 새 list의 객체를 가리키도록 바꾸면, 이전 list를 걷던 동시 RCU lookup이 잘못된 새 list로 빠질 수 있다. 다른 list를 걷는 것 자체는 비교가 일치하지 않으므로 치명적이지 않지만, 원래 list 뒤쪽의 일치하는 dentry를 건너뛰는 것은 치명적이다. rename seqlock은 이 변화를 감지해 lookup 전체를 재시도하게 한다.

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.

삭제 pointer, 재삽입, rename 원자성

표준 RCU list deletion은 삭제한 객체의 pointer를 그대로 남긴다. 따라서 dentry 2를 보고 있던 동시 walker는 2가 list에서 제거된 뒤에도 다음 pointer를 따라 원래의 dentry 3으로 정확히 진행할 수 있다. 그림에서 길어진 pointer는 현대 CPU에서 측정할 만한 성능 부담을 만들지 않는다고 원문은 덧붙인다.

문제는 dentry 2를 새 list에 삽입할 때 생긴다. grace period를 기다리지 않았으므로 아직 2에 머무는 이전 lookup이 있을 수 있다. 재삽입으로 2의 `next` pointer가 새 list를 가리키면 이 lookup은 dentry 3을 검사하지 않은 채 다른 list로 이탈한다.

이와 별개로 rename과 lookup 사이에는 이름의 원자성 문제가 있다. 파일 이름이 `A`에서 `B`로 바뀌면 lookup은 `A` 또는 `B` 중 하나로만 파일을 찾아야 한다. `A` lookup이 `NULL`이었다면 그 뒤의 `B` lookup은 성공해야 한다. 반대 순서는 보장할 필요가 없다.

옛 hash list에서 삭제한 순간과 새 list에 삽입하는 순간 사이에는 어느 이름으로도 dentry를 찾지 못할 수 있다. 같은 rename seqlock이 이 경쟁도 덮는다. negative lookup 동안 rename이 진행됐음을 발견하면 결과를 확정하지 않고 재시도한다.

         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 기반 lookup

refcount 기반 dcache lookup은 `d_lock`으로 dentry 접근을 직렬화한다. lock 아래에서 name과 parent를 비교하고 reference count를 얻으면, 그 reference가 다음 경로 단계의 안정된 출발점을 제공한다.

중간 dentry마다 lock과 reference를 얻지 않기 위해 RCU 방식은 dentry별 seqlock인 `d_seq`로 name, parent, inode의 일관된 snapshot을 취한다. snapshot을 읽을 때 필요한 member를 처음에 모두 load하고 그 pointer를 계속 사용해야 한다. 나중에 dentry에서 다시 읽으면 unlink 때문에 `d_inode`가 그 사이 `NULL`이 되는 상황이 생길 수 있다.

이 구간에서는 공용 데이터에 비원자 store를 하는 파괴적 동작을 피하고, 작업이 끝났을 때 seqcount를 재검사한다. sequence가 일치하지 않으면 재시도하거나 중단한다. 상태를 바꾸지 않았기 때문에 실패 경로를 쉽게 되돌릴 수 있다.

호출자가 RCU read-side lock으로 dentry 객체의 수명을 보호하면 refcount를 올리거나 dentry에 쓰지 않고 seqcount 기반 lookup을 수행할 수 있다. 반환된 dentry를 이용한 작업이 끝난 뒤 `d_seq`를 다시 확인해야 한다. inode도 RCU 이후에 해제되므로 이 snapshot의 inode를 권한 검사에 사용할 수 있다. 객체 수명 보호와 snapshot 검증을 결합하면 dentry element에 lock이나 refcount를 취하지 않고 경로를 찾을 수 있다.

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.

REF-walk와 RCU-walk 설계

경로 탐색에는 `ref-walk`와 `rcu-walk`라는 두 mode가 있다. 전통적인 ref-walk는 `d_lock`으로 dentry의 동시 변경을 직렬화하고 reference count를 얻는다. 구조가 명확하고 component를 처리하는 동안 sleep하거나 다른 lock을 잡을 수 있다. rcu-walk는 seqcount 기반 lookup으로 중간 dentry나 inode의 공용 데이터에 쓰지 않는다. filesystem이 sleep하거나 복잡한 작업을 수행해야 하면 rcu-walk에서 ref-walk로 전환해야 한다.

각주가 설명하듯 ref-walk도 dentry hash lookup 자체에는 RCU를 사용하지만, 전체 path walk를 RCU 방식으로 수행하는 것은 아니다. ref-walk가 reference로 고정된 `parent`를 이용한다면 rcu-walk는 `d_seq`가 보호하는 parent snapshot을 이용한다.

자식 dentry를 찾을 때는 parent의 `d_seq` critical section을 닫기 전에 child의 `d_seq` critical section을 연다. 이렇게 snapshot이 서로 맞물리는 사다리를 만들어 경로 아래로 내려간다.

예시의 process 101은 command `vi`, `fs.root`의 dentry0, `fs.cwd`의 dentry2를 가진다. `open("/home/npiggin/test.c", O_RDWR)`는 고정된 `current->fs->root`에서 시작하고, `./test.c`는 cwd에서 시작한다. process 101의 context에서는 두 이름이 같은 path를 가리킨다. 뒤의 원문 도식이 최종 이름을 `a.c`로 표기하는 차이도 원문 그대로 보존한다.

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 snapshot과 dropping RCU

rcu-walk는 dentry0 `/`에서 `d_seq`를 기록하고 inode 권한을 검사한 뒤 `home`을 찾는다. hash lookup으로 dentry1 `home`을 찾으면 child의 `d_seq`를 기록하고 name과 parent pointer를 비교한다. 일치한 뒤에는 dentry0의 `d_seq`를 재검사하고, dentry1 inode를 검사해 다음 element `npiggin`을 찾는다.

dentry2 `npiggin`까지 내려온 뒤 dentry0가 변경되더라도 현재 lookup이 반드시 무효인 것은 아니다. 따라서 직전 parent만 `d_seq` 검증용으로 유지하면 되고 grandparent snapshot은 버릴 수 있다. 목적지 dentry3에 도착하면 `d_lock`을 잡고 그 dentry의 `d_seq`를 검증한 다음, lock을 쥔 상태에서 refcount를 증가시킨다.

rcu-walk에서 `d_lock`을 잡고 `d_seq`를 재확인한 뒤 dentry refcount를 얻는 절차를 `dropping rcu`, 즉 rcu-walk에서 ref-walk로 내려간다고 부른다.

parent snapshot 검증이 실패하면 이미 grandparent의 `d_seq` section을 닫았으므로 의지할 이전 snapshot이 남지 않는다. 이때는 path walk 전체를 ref-walk mode로 다시 시작해 livelock을 피한다. 전체 재시작은 비싸지만 실제로는 드물다.

sleep이 필요하거나 filesystem callout이 ref-walk를 요구하는 경우에는 전체를 재시작하는 대신 마지막으로 확인된 정상 dentry에서 RCU를 drop한다. create와 unlink 같은 blocking operation은 흔하므로, 정상 지점까지의 빠른 탐색을 보존하는 것이 성능과 확장성에 중요하다.

     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.

RCU-walk의 상세 규칙과 한계

`nd->flags`의 `LOOKUP_RCU`가 rcu-walk와 ref-walk를 구분한다. 시작 path(root, cwd 또는 fd-path)를 얻을 때부터 전체 path walk 동안 RCU lock을 유지하므로 dentry의 존속을 위한 refcount가 필요 없다. filesystem unregister 시 `synchronize_rcu`를 호출하므로 rcu-walk에서 `d_ops`와 `i_ops`에도 접근할 수 있다.

문서가 설명하는 설계에서는 전체 walk 동안 vfsmount lock도 유지한다. 따라서 mount의 존속을 위한 `mnt` refcount 없이 mount lookup을 수행하고, 경로 위아래의 dentry mount point와 mount root가 안정되어 있다고 가정할 수 있다.

dentry별 seqlock은 name, parent, inode 튜플을 원자적인 snapshot으로 읽고 변경 여부를 확인하게 한다. `(parent, candidate string)`으로 child를 찾은 뒤에는 lookup 도중 parent가 바뀌지 않았는지 parent sequence를 재검사한다. inode도 RCU 보호를 받으므로 `d_inode`를 load해 제한적으로 사용할 수 있고, `i_mode`, `i_uid`, `i_gid`로 실행 권한을 검사하며 `i_op`도 읽을 수 있다.

목적지 dentry에서는 `d_lock`을 잡고 `d_seq`를 확인한 뒤 refcount를 올려 RCU를 drop한다. 어느 지점에서든 seqlock 검증이 실패하면 ref-walk로 전체 path lookup을 재시작한다. 이 문서는 적합한 errno가 마땅치 않아 rcu-walk 실패 신호로 흔히 `-ECHILD`를 사용한다고 설명한다.

이 역사 문서가 기록한 구현에서 rcu-walk가 계속될 수 없는 경우는 `NULL` dentry, 즉 cache되지 않은 path element와 symbolic link traversal이다. cache miss는 적어도 `i_mutex`를 잡고 객체를 할당해야 하므로 ref-walk 전환이 필수다. link follow도 언젠가 RCU-aware하게 만들 수 있다고 당시의 가능성을 적었다. 최신 동작은 같은 디렉터리의 `path-lookup.rst`를 기준으로 보아야 한다.

store-free path walking이 문자 그대로 store가 전혀 없다는 뜻은 아니다. vfsmount lock과 refcount를 사용하고, CPU-local에 가까운 stack에는 저장하며, 최종 dentry에는 lock과 reference를 취한다. 핵심은 가능한 곳에서 여러 CPU가 공유하는 데이터를 lock하거나 수정하지 않는 것이다. 이것이 path resolution의 성능과 확장성을 크게 개선한다.

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.

RCU lookup 실측 통계

표는 2 socket, 12 core, 24 thread Westmere와 그래픽 환경이 없는 Debian 시스템에서 몇 가지 간단한 workload를 측정한 결과다. `restart`는 RCU를 drop하려다 `d_seq` 검증에 실패해 path lookup 전체를 다시 시작한 횟수다. `nodentry`, `link`, `revalidate`, `permission`은 각각 최종 element 이전에 ref-walk 전환이 필요했던 cache miss, symlink traversal, filesystem revalidation, 권한 검사 횟수다.

결과는 ref-walk로 전체 재시작하는 rcu-walk 실패가 매우 드물다는 점을 보여 준다. rename, mkdir, rmdir, create, unlink 등의 경쟁을 의도적으로 일으킨 `vfstest`조차 약 2,419만 번의 lookup 중 restart가 4,945번뿐이다.

rcu-walk에서 ref-walk로 drop한다는 것은 어떤 이유로 dentry reference가 필요해졌다는 뜻이다. 정상적으로 목적지에 도착했거나 rcu-walk만으로 해결할 수 없는 조건을 만났을 수 있다. 이상적인 경우에는 목적 dentry에서만 drop하므로, 표의 다른 열은 그보다 일찍 전환한 이유를 나타낸다.

dentry가 존재하지 않아 정상적으로 RCU를 drop하는 흔한 경우도 rcu-walk 설계의 실패라고 볼 수 없다. 그 지점 전까지 여러 component를 rcu-walk로 처리했을 수 있기 때문이다. cwd나 root 같은 공통 경로에서 멀어질수록 dentry 경합 가능성은 낮아지고, 공통 경로에 가까울수록 dentry cache에 존재할 가능성이 높다. 따라서 가장 경합이 큰 앞부분을 RCU로 빠르게 통과하는 것만으로도 이득이 크다.

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.

Dcache locking 참고 문헌

추가 자료로 Linux Journal의 `Scaling dcache with RCU`, LSE의 dcache locking 문서, 그리고 같은 디렉터리의 `path-lookup.rst`를 제시한다.

이 `.txt` 문서는 RCU path walking 도입기의 설계와 초기 통계를 보존하는 역사 자료다. 현재 kernel의 세부 구현과 flag, symbolic link 처리 방식은 함께 언급된 최신 `path-lookup.rst` 전문 번역에서 교차 확인하는 것이 적절하다.

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

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

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

3. path-lookup.rst in this directory.