1 Path walking and name lookup locking 1 Path walking and name lookup locking
2 ==================================== 2 ====================================
3 3
4 Path resolution is the finding a dentry corres 4 Path resolution is the finding a dentry corresponding to a path name string, by
5 performing a path walk. Typically, for every o 5 performing a path walk. Typically, for every open(), stat() etc., the path name
6 will be resolved. Paths are resolved by walkin 6 will be resolved. Paths are resolved by walking the namespace tree, starting
7 with the first component of the pathname (eg. 7 with the first component of the pathname (eg. root or cwd) with a known dentry,
8 then finding the child of that dentry, which i 8 then finding the child of that dentry, which is named the next component in the
9 path string. Then repeating the lookup from th 9 path string. Then repeating the lookup from the child dentry and finding its
10 child with the next element, and so on. 10 child with the next element, and so on.
11 11
12 Since it is a frequent operation for workloads 12 Since it is a frequent operation for workloads like multiuser environments and
13 web servers, it is important to optimize this 13 web servers, it is important to optimize this code.
14 14
15 Path walking synchronisation history: 15 Path walking synchronisation history:
16 Prior to 2.5.10, dcache_lock was acquired in d 16 Prior to 2.5.10, dcache_lock was acquired in d_lookup (dcache hash lookup) and
17 thus in every component during path look-up. S 17 thus in every component during path look-up. Since 2.5.10 onwards, fast-walk
18 algorithm changed this by holding the dcache_l 18 algorithm changed this by holding the dcache_lock at the beginning and walking
19 as many cached path component dentries as poss 19 as many cached path component dentries as possible. This significantly
20 decreases the number of acquisition of dcache_ 20 decreases the number of acquisition of dcache_lock. However it also increases
21 the lock hold time significantly and affects p 21 the lock hold time significantly and affects performance in large SMP machines.
22 Since 2.5.62 kernel, dcache has been using a n 22 Since 2.5.62 kernel, dcache has been using a new locking model that uses RCU to
23 make dcache look-up lock-free. 23 make dcache look-up lock-free.
24 24
25 All the above algorithms required taking a loc 25 All the above algorithms required taking a lock and reference count on the
26 dentry that was looked up, so that may be used 26 dentry that was looked up, so that may be used as the basis for walking the
27 next path element. This is inefficient and uns 27 next path element. This is inefficient and unscalable. It is inefficient
28 because of the locks and atomic operations req 28 because of the locks and atomic operations required for every dentry element
29 slows things down. It is not scalable because 29 slows things down. It is not scalable because many parallel applications that
30 are path-walk intensive tend to do path lookup 30 are path-walk intensive tend to do path lookups starting from a common dentry
31 (usually, the root "/" or current working dire 31 (usually, the root "/" or current working directory). So contention on these
32 common path elements causes lock and cacheline 32 common path elements causes lock and cacheline queueing.
33 33
34 Since 2.6.38, RCU is used to make a significan 34 Since 2.6.38, RCU is used to make a significant part of the entire path walk
35 (including dcache look-up) completely "store-f 35 (including dcache look-up) completely "store-free" (so, no locks, atomics, or
36 even stores into cachelines of common dentries 36 even stores into cachelines of common dentries). This is known as "rcu-walk"
37 path walking. 37 path walking.
38 38
39 Path walking overview 39 Path walking overview
40 ===================== 40 =====================
41 41
42 A name string specifies a start (root director 42 A name string specifies a start (root directory, cwd, fd-relative) and a
43 sequence of elements (directory entry names), 43 sequence of elements (directory entry names), which together refer to a path in
44 the namespace. A path is represented as a (den 44 the namespace. A path is represented as a (dentry, vfsmount) tuple. The name
45 elements are sub-strings, separated by '/'. 45 elements are sub-strings, separated by '/'.
46 46
47 Name lookups will want to find a particular pa 47 Name lookups will want to find a particular path that a name string refers to
48 (usually the final element, or parent of final 48 (usually the final element, or parent of final element). This is done by taking
49 the path given by the name's starting point (w 49 the path given by the name's starting point (which we know in advance -- eg.
50 current->fs->cwd or current->fs->root) as the 50 current->fs->cwd or current->fs->root) as the first parent of the lookup. Then
51 iteratively for each subsequent name element, 51 iteratively for each subsequent name element, look up the child of the current
52 parent with the given name and if it is not th 52 parent with the given name and if it is not the desired entry, make it the
53 parent for the next lookup. 53 parent for the next lookup.
54 54
55 A parent, of course, must be a directory, and 55 A parent, of course, must be a directory, and we must have appropriate
56 permissions on the parent inode to be able to 56 permissions on the parent inode to be able to walk into it.
57 57
58 Turning the child into a parent for the next l 58 Turning the child into a parent for the next lookup requires more checks and
59 procedures. Symlinks essentially substitute th 59 procedures. Symlinks essentially substitute the symlink name for the target
60 name in the name string, and require some recu 60 name in the name string, and require some recursive path walking. Mount points
61 must be followed into (thus changing the vfsmo 61 must be followed into (thus changing the vfsmount that subsequent path elements
62 refer to), switching from the mount point path 62 refer to), switching from the mount point path to the root of the particular
63 mounted vfsmount. These behaviours are various 63 mounted vfsmount. These behaviours are variously modified depending on the
64 exact path walking flags. 64 exact path walking flags.
65 65
66 Path walking then must, broadly, do several pa 66 Path walking then must, broadly, do several particular things:
67 - find the start point of the walk; 67 - find the start point of the walk;
68 - perform permissions and validity checks on i 68 - perform permissions and validity checks on inodes;
69 - perform dcache hash name lookups on (parent, 69 - perform dcache hash name lookups on (parent, name element) tuples;
70 - traverse mount points; 70 - traverse mount points;
71 - traverse symlinks; 71 - traverse symlinks;
72 - lookup and create missing parts of the path 72 - lookup and create missing parts of the path on demand.
73 73
74 Safe store-free look-up of dcache hash table 74 Safe store-free look-up of dcache hash table
75 ============================================ 75 ============================================
76 76
77 Dcache name lookup 77 Dcache name lookup
78 ------------------ 78 ------------------
79 In order to lookup a dcache (parent, name) tup 79 In order to lookup a dcache (parent, name) tuple, we take a hash on the tuple
80 and use that to select a bucket in the dcache- 80 and use that to select a bucket in the dcache-hash table. The list of entries
81 in that bucket is then walked, and we do a ful 81 in that bucket is then walked, and we do a full comparison of each entry
82 against our (parent, name) tuple. 82 against our (parent, name) tuple.
83 83
84 The hash lists are RCU protected, so list walk 84 The hash lists are RCU protected, so list walking is not serialised with
85 concurrent updates (insertion, deletion from t 85 concurrent updates (insertion, deletion from the hash). This is a standard RCU
86 list application with the exception of renames 86 list application with the exception of renames, which will be covered below.
87 87
88 Parent and name members of a dentry, as well a 88 Parent and name members of a dentry, as well as its membership in the dcache
89 hash, and its inode are protected by the per-d 89 hash, and its inode are protected by the per-dentry d_lock spinlock. A
90 reference is taken on the dentry (while the fi 90 reference is taken on the dentry (while the fields are verified under d_lock),
91 and this stabilises its d_inode pointer and ac 91 and this stabilises its d_inode pointer and actual inode. This gives a stable
92 point to perform the next step of our path wal 92 point to perform the next step of our path walk against.
93 93
94 These members are also protected by d_seq seql 94 These members are also protected by d_seq seqlock, although this offers
95 read-only protection and no durability of resu 95 read-only protection and no durability of results, so care must be taken when
96 using d_seq for synchronisation (see seqcount 96 using d_seq for synchronisation (see seqcount based lookups, below).
97 97
98 Renames 98 Renames
99 ------- 99 -------
100 Back to the rename case. In usual RCU protecte 100 Back to the rename case. In usual RCU protected lists, the only operations that
101 will happen to an object is insertion, and the 101 will happen to an object is insertion, and then eventually removal from the
102 list. The object will not be reused until an R 102 list. The object will not be reused until an RCU grace period is complete.
103 This ensures the RCU list traversal primitives 103 This ensures the RCU list traversal primitives can run over the object without
104 problems (see RCU documentation for how this w 104 problems (see RCU documentation for how this works).
105 105
106 However when a dentry is renamed, its hash val 106 However when a dentry is renamed, its hash value can change, requiring it to be
107 moved to a new hash list. Allocating and inser 107 moved to a new hash list. Allocating and inserting a new alias would be
108 expensive and also problematic for directory d 108 expensive and also problematic for directory dentries. Latency would be far to
109 high to wait for a grace period after removing 109 high to wait for a grace period after removing the dentry and before inserting
110 it in the new hash bucket. So what is done is 110 it in the new hash bucket. So what is done is to insert the dentry into the
111 new list immediately. 111 new list immediately.
112 112
113 However, when the dentry's list pointers are u 113 However, when the dentry's list pointers are updated to point to objects in the
114 new list before waiting for a grace period, th 114 new list before waiting for a grace period, this can result in a concurrent RCU
115 lookup of the old list veering off into the ne 115 lookup of the old list veering off into the new (incorrect) list and missing
116 the remaining dentries on the list. 116 the remaining dentries on the list.
117 117
118 There is no fundamental problem with walking d 118 There is no fundamental problem with walking down the wrong list, because the
119 dentry comparisons will never match. However i 119 dentry comparisons will never match. However it is fatal to miss a matching
120 dentry. So a seqlock is used to detect when a 120 dentry. So a seqlock is used to detect when a rename has occurred, and so the
121 lookup can be retried. 121 lookup can be retried.
122 122
123 1 2 3 123 1 2 3
124 +---+ +---+ +---+ 124 +---+ +---+ +---+
125 hlist-->| N-+->| N-+->| N-+-> 125 hlist-->| N-+->| N-+->| N-+->
126 head <--+-P |<-+-P |<-+-P | 126 head <--+-P |<-+-P |<-+-P |
127 +---+ +---+ +---+ 127 +---+ +---+ +---+
128 128
129 Rename of dentry 2 may require it deleted from 129 Rename of dentry 2 may require it deleted from the above list, and inserted
130 into a new list. Deleting 2 gives the followin 130 into a new list. Deleting 2 gives the following list.
131 131
132 1 3 132 1 3
133 +---+ +---+ (don't worry, 133 +---+ +---+ (don't worry, the longer pointers do not
134 hlist-->| N-+-------->| N-+-> impose a meas 134 hlist-->| N-+-------->| N-+-> impose a measurable performance overhead
135 head <--+-P |<--------+-P | on modern CPU 135 head <--+-P |<--------+-P | on modern CPUs)
136 +---+ +---+ 136 +---+ +---+
137 ^ 2 ^ 137 ^ 2 ^
138 | +---+ | 138 | +---+ |
139 | | N-+----+ 139 | | N-+----+
140 +----+-P | 140 +----+-P |
141 +---+ 141 +---+
142 142
143 This is a standard RCU-list deletion, which le 143 This is a standard RCU-list deletion, which leaves the deleted object's
144 pointers intact, so a concurrent list walker t 144 pointers intact, so a concurrent list walker that is currently looking at
145 object 2 will correctly continue to object 3 w 145 object 2 will correctly continue to object 3 when it is time to traverse the
146 next object. 146 next object.
147 147
148 However, when inserting object 2 onto a new li 148 However, when inserting object 2 onto a new list, we end up with this:
149 149
150 1 3 150 1 3
151 +---+ +---+ 151 +---+ +---+
152 hlist-->| N-+-------->| N-+-> 152 hlist-->| N-+-------->| N-+->
153 head <--+-P |<--------+-P | 153 head <--+-P |<--------+-P |
154 +---+ +---+ 154 +---+ +---+
155 2 155 2
156 +---+ 156 +---+
157 | N-+----> 157 | N-+---->
158 <----+-P | 158 <----+-P |
159 +---+ 159 +---+
160 160
161 Because we didn't wait for a grace period, the 161 Because we didn't wait for a grace period, there may be a concurrent lookup
162 still at 2. Now when it follows 2's 'next' poi 162 still at 2. Now when it follows 2's 'next' pointer, it will walk off into
163 another list without ever having checked objec 163 another list without ever having checked object 3.
164 164
165 A related, but distinctly different, issue is 165 A related, but distinctly different, issue is that of rename atomicity versus
166 lookup operations. If a file is renamed from ' 166 lookup operations. If a file is renamed from 'A' to 'B', a lookup must only
167 find either 'A' or 'B'. So if a lookup of 'A' 167 find either 'A' or 'B'. So if a lookup of 'A' returns NULL, a subsequent lookup
168 of 'B' must succeed (note the reverse is not t 168 of 'B' must succeed (note the reverse is not true).
169 169
170 Between deleting the dentry from the old hash 170 Between deleting the dentry from the old hash list, and inserting it on the new
171 hash list, a lookup may find neither 'A' nor ' 171 hash list, a lookup may find neither 'A' nor 'B' matching the dentry. The same
172 rename seqlock is also used to cover this race 172 rename seqlock is also used to cover this race in much the same way, by
173 retrying a negative lookup result if a rename 173 retrying a negative lookup result if a rename was in progress.
174 174
175 Seqcount based lookups 175 Seqcount based lookups
176 ---------------------- 176 ----------------------
177 In refcount based dcache lookups, d_lock is us 177 In refcount based dcache lookups, d_lock is used to serialise access to
178 the dentry, stabilising it while comparing its 178 the dentry, stabilising it while comparing its name and parent and then
179 taking a reference count (the reference count 179 taking a reference count (the reference count then gives a stable place to
180 start the next part of the path walk from). 180 start the next part of the path walk from).
181 181
182 As explained above, we would like to do path w 182 As explained above, we would like to do path walking without taking locks or
183 reference counts on intermediate dentries alon 183 reference counts on intermediate dentries along the path. To do this, a per
184 dentry seqlock (d_seq) is used to take a "cohe 184 dentry seqlock (d_seq) is used to take a "coherent snapshot" of what the dentry
185 looks like (its name, parent, and inode). That 185 looks like (its name, parent, and inode). That snapshot is then used to start
186 the next part of the path walk. When loading t 186 the next part of the path walk. When loading the coherent snapshot under d_seq,
187 care must be taken to load the members up-fron 187 care must be taken to load the members up-front, and use those pointers rather
188 than reloading from the dentry later on (other 188 than reloading from the dentry later on (otherwise we'd have interesting things
189 like d_inode going NULL underneath us, if the 189 like d_inode going NULL underneath us, if the name was unlinked).
190 190
191 Also important is to avoid performing any dest 191 Also important is to avoid performing any destructive operations (pretty much:
192 no non-atomic stores to shared data), and to r 192 no non-atomic stores to shared data), and to recheck the seqcount when we are
193 "done" with the operation. Retry or abort if t 193 "done" with the operation. Retry or abort if the seqcount does not match.
194 Avoiding destructive or changing operations me 194 Avoiding destructive or changing operations means we can easily unwind from
195 failure. 195 failure.
196 196
197 What this means is that a caller, provided the 197 What this means is that a caller, provided they are holding RCU lock to
198 protect the dentry object from disappearing, c 198 protect the dentry object from disappearing, can perform a seqcount based
199 lookup which does not increment the refcount o 199 lookup which does not increment the refcount on the dentry or write to
200 it in any way. This returned dentry can be use 200 it in any way. This returned dentry can be used for subsequent operations,
201 provided that d_seq is rechecked after that op 201 provided that d_seq is rechecked after that operation is complete.
202 202
203 Inodes are also rcu freed, so the seqcount loo 203 Inodes are also rcu freed, so the seqcount lookup dentry's inode may also be
204 queried for permissions. 204 queried for permissions.
205 205
206 With this two parts of the puzzle, we can do p 206 With this two parts of the puzzle, we can do path lookups without taking
207 locks or refcounts on dentry elements. 207 locks or refcounts on dentry elements.
208 208
209 RCU-walk path walking design 209 RCU-walk path walking design
210 ============================ 210 ============================
211 211
212 Path walking code now has two distinct modes, 212 Path walking code now has two distinct modes, ref-walk and rcu-walk. ref-walk
213 is the traditional[*] way of performing dcache 213 is the traditional[*] way of performing dcache lookups using d_lock to
214 serialise concurrent modifications to the dent 214 serialise concurrent modifications to the dentry and take a reference count on
215 it. ref-walk is simple and obvious, and may sl 215 it. ref-walk is simple and obvious, and may sleep, take locks, etc while path
216 walking is operating on each dentry. rcu-walk 216 walking is operating on each dentry. rcu-walk uses seqcount based dentry
217 lookups, and can perform lookup of intermediat 217 lookups, and can perform lookup of intermediate elements without any stores to
218 shared data in the dentry or inode. rcu-walk c 218 shared data in the dentry or inode. rcu-walk can not be applied to all cases,
219 eg. if the filesystem must sleep or perform no 219 eg. if the filesystem must sleep or perform non trivial operations, rcu-walk
220 must be switched to ref-walk mode. 220 must be switched to ref-walk mode.
221 221
222 [*] RCU is still used for the dentry hash look 222 [*] RCU is still used for the dentry hash lookup in ref-walk, but not the full
223 path walk. 223 path walk.
224 224
225 Where ref-walk uses a stable, refcounted ``par 225 Where ref-walk uses a stable, refcounted ``parent'' to walk the remaining
226 path string, rcu-walk uses a d_seq protected s 226 path string, rcu-walk uses a d_seq protected snapshot. When looking up a
227 child of this parent snapshot, we open d_seq c 227 child of this parent snapshot, we open d_seq critical section on the child
228 before closing d_seq critical section on the p 228 before closing d_seq critical section on the parent. This gives an interlocking
229 ladder of snapshots to walk down. 229 ladder of snapshots to walk down.
230 230
231 231
232 proc 101 232 proc 101
233 /----------------\ 233 /----------------\
234 / comm: "vi" \ 234 / comm: "vi" \
235 / fs.root: dentry0 \ 235 / fs.root: dentry0 \
236 \ fs.cwd: dentry2 / 236 \ fs.cwd: dentry2 /
237 \ / 237 \ /
238 \----------------/ 238 \----------------/
239 239
240 So when vi wants to open("/home/npiggin/test.c 240 So when vi wants to open("/home/npiggin/test.c", O_RDWR), then it will
241 start from current->fs->root, which is a pinne 241 start from current->fs->root, which is a pinned dentry. Alternatively,
242 "./test.c" would start from cwd; both names re 242 "./test.c" would start from cwd; both names refer to the same path in
243 the context of proc101. 243 the context of proc101.
244 244
245 dentry 0 245 dentry 0
246 +---------------------+ rcu-walk begins 246 +---------------------+ rcu-walk begins here, we note d_seq, check the
247 | name: "/" | inode's permissi 247 | name: "/" | inode's permission, and then look up the next
248 | inode: 10 | path element whi 248 | inode: 10 | path element which is "home"...
249 | children:"home", ...| 249 | children:"home", ...|
250 +---------------------+ 250 +---------------------+
251 | 251 |
252 dentry 1 V 252 dentry 1 V
253 +---------------------+ ... which brings 253 +---------------------+ ... which brings us here. We find dentry1 via
254 | name: "home" | hash lookup, the 254 | name: "home" | hash lookup, then note d_seq and compare name
255 | inode: 678 | string and paren 255 | inode: 678 | string and parent pointer. When we have a match,
256 | children:"npiggin" | we now recheck t 256 | children:"npiggin" | we now recheck the d_seq of dentry0. Then we
257 +---------------------+ check inode and 257 +---------------------+ check inode and look up the next element.
258 | 258 |
259 dentry2 V 259 dentry2 V
260 +---------------------+ Note: if dentry0 260 +---------------------+ Note: if dentry0 is now modified, lookup is
261 | name: "npiggin" | not necessarily 261 | name: "npiggin" | not necessarily invalid, so we need only keep a
262 | inode: 543 | parent for d_seq 262 | inode: 543 | parent for d_seq verification, and grandparents
263 | children:"a.c", ... | can be forgotten 263 | children:"a.c", ... | can be forgotten.
264 +---------------------+ 264 +---------------------+
265 | 265 |
266 dentry3 V 266 dentry3 V
267 +---------------------+ At this point we 267 +---------------------+ At this point we have our destination dentry.
268 | name: "a.c" | We now take its 268 | name: "a.c" | We now take its d_lock, verify d_seq of this
269 | inode: 14221 | dentry. If that 269 | inode: 14221 | dentry. If that checks out, we can increment
270 | children:NULL | its refcount bec 270 | children:NULL | its refcount because we're holding d_lock.
271 +---------------------+ 271 +---------------------+
272 272
273 Taking a refcount on a dentry from rcu-walk mo 273 Taking a refcount on a dentry from rcu-walk mode, by taking its d_lock,
274 re-checking its d_seq, and then incrementing i 274 re-checking its d_seq, and then incrementing its refcount is called
275 "dropping rcu" or dropping from rcu-walk into 275 "dropping rcu" or dropping from rcu-walk into ref-walk mode.
276 276
277 It is, in some sense, a bit of a house of card 277 It is, in some sense, a bit of a house of cards. If the seqcount check of the
278 parent snapshot fails, the house comes down, b 278 parent snapshot fails, the house comes down, because we had closed the d_seq
279 section on the grandparent, so we have nothing 279 section on the grandparent, so we have nothing left to stand on. In that case,
280 the path walk must be fully restarted (which w 280 the path walk must be fully restarted (which we do in ref-walk mode, to avoid
281 live locks). It is costly to have a full resta 281 live locks). It is costly to have a full restart, but fortunately they are
282 quite rare. 282 quite rare.
283 283
284 When we reach a point where sleeping is requir 284 When we reach a point where sleeping is required, or a filesystem callout
285 requires ref-walk, then instead of restarting 285 requires ref-walk, then instead of restarting the walk, we attempt to drop rcu
286 at the last known good dentry we have. Avoidin 286 at the last known good dentry we have. Avoiding a full restart in ref-walk in
287 these cases is fundamental for performance and 287 these cases is fundamental for performance and scalability because blocking
288 operations such as creates and unlinks are not 288 operations such as creates and unlinks are not uncommon.
289 289
290 The detailed design for rcu-walk is like this: 290 The detailed design for rcu-walk is like this:
291 * LOOKUP_RCU is set in nd->flags, which distin 291 * LOOKUP_RCU is set in nd->flags, which distinguishes rcu-walk from ref-walk.
292 * Take the RCU lock for the entire path walk, 292 * Take the RCU lock for the entire path walk, starting with the acquiring
293 of the starting path (eg. root/cwd/fd-path). 293 of the starting path (eg. root/cwd/fd-path). So now dentry refcounts are
294 not required for dentry persistence. 294 not required for dentry persistence.
295 * synchronize_rcu is called when unregistering 295 * synchronize_rcu is called when unregistering a filesystem, so we can
296 access d_ops and i_ops during rcu-walk. 296 access d_ops and i_ops during rcu-walk.
297 * Similarly take the vfsmount lock for the ent 297 * Similarly take the vfsmount lock for the entire path walk. So now mnt
298 refcounts are not required for persistence. 298 refcounts are not required for persistence. Also we are free to perform mount
299 lookups, and to assume dentry mount points a 299 lookups, and to assume dentry mount points and mount roots are stable up and
300 down the path. 300 down the path.
301 * Have a per-dentry seqlock to protect the den 301 * Have a per-dentry seqlock to protect the dentry name, parent, and inode,
302 so we can load this tuple atomically, and al 302 so we can load this tuple atomically, and also check whether any of its
303 members have changed. 303 members have changed.
304 * Dentry lookups (based on parent, candidate s 304 * Dentry lookups (based on parent, candidate string tuple) recheck the parent
305 sequence after the child is found in case an 305 sequence after the child is found in case anything changed in the parent
306 during the path walk. 306 during the path walk.
307 * inode is also RCU protected so we can load d 307 * inode is also RCU protected so we can load d_inode and use the inode for
308 limited things. 308 limited things.
309 * i_mode, i_uid, i_gid can be tested for exec 309 * i_mode, i_uid, i_gid can be tested for exec permissions during path walk.
310 * i_op can be loaded. 310 * i_op can be loaded.
311 * When the destination dentry is reached, drop 311 * When the destination dentry is reached, drop rcu there (ie. take d_lock,
312 verify d_seq, increment refcount). 312 verify d_seq, increment refcount).
313 * If seqlock verification fails anywhere along 313 * If seqlock verification fails anywhere along the path, do a full restart
314 of the path lookup in ref-walk mode. -ECHILD 314 of the path lookup in ref-walk mode. -ECHILD tends to be used (for want of
315 a better errno) to signal an rcu-walk failur 315 a better errno) to signal an rcu-walk failure.
316 316
317 The cases where rcu-walk cannot continue are: 317 The cases where rcu-walk cannot continue are:
318 * NULL dentry (ie. any uncached path element) 318 * NULL dentry (ie. any uncached path element)
319 * Following links 319 * Following links
320 320
321 It may be possible eventually to make followin 321 It may be possible eventually to make following links rcu-walk aware.
322 322
323 Uncached path elements will always require dro 323 Uncached path elements will always require dropping to ref-walk mode, at the
324 very least because i_mutex needs to be grabbed 324 very least because i_mutex needs to be grabbed, and objects allocated.
325 325
326 Final note: 326 Final note:
327 "store-free" path walking is not strictly stor 327 "store-free" path walking is not strictly store free. We take vfsmount lock
328 and refcounts (both of which can be made per-c 328 and refcounts (both of which can be made per-cpu), and we also store to the
329 stack (which is essentially CPU-local), and we 329 stack (which is essentially CPU-local), and we also have to take locks and
330 refcount on final dentry. 330 refcount on final dentry.
331 331
332 The point is that shared data, where practical 332 The point is that shared data, where practically possible, is not locked
333 or stored into. The result is massive improvem 333 or stored into. The result is massive improvements in performance and
334 scalability of path resolution. 334 scalability of path resolution.
335 335
336 336
337 Interesting statistics 337 Interesting statistics
338 ====================== 338 ======================
339 339
340 The following table gives rcu lookup statistic 340 The following table gives rcu lookup statistics for a few simple workloads
341 (2s12c24t Westmere, debian non-graphical syste 341 (2s12c24t Westmere, debian non-graphical system). Ungraceful are attempts to
342 drop rcu that fail due to d_seq failure and re 342 drop rcu that fail due to d_seq failure and requiring the entire path lookup
343 again. Other cases are successful rcu-drops th 343 again. Other cases are successful rcu-drops that are required before the final
344 element, nodentry for missing dentry, revalida 344 element, nodentry for missing dentry, revalidate for filesystem revalidate
345 routine requiring rcu drop, permission for per 345 routine requiring rcu drop, permission for permission check requiring drop,
346 and link for symlink traversal requiring drop. 346 and link for symlink traversal requiring drop.
347 347
348 rcu-lookups restart nodentry 348 rcu-lookups restart nodentry link revalidate permission
349 bootup 47121 0 4624 349 bootup 47121 0 4624 1010 10283 7852
350 dbench 25386793 0 6778659(26.7%) 350 dbench 25386793 0 6778659(26.7%) 55 549 1156
351 kbuild 2696672 10 64442(2.3%) 351 kbuild 2696672 10 64442(2.3%) 108764(4.0%) 1 1590
352 git diff 39605 0 28 352 git diff 39605 0 28 2 0 106
353 vfstest 24185492 4945 708725(2.9%) 1 353 vfstest 24185492 4945 708725(2.9%) 1076136(4.4%) 0 2651
354 354
355 What this shows is that failed rcu-walk lookup 355 What this shows is that failed rcu-walk lookups, ie. ones that are restarted
356 entirely with ref-walk, are quite rare. Even t 356 entirely with ref-walk, are quite rare. Even the "vfstest" case which
357 specifically has concurrent renames/mkdir/rmdi 357 specifically has concurrent renames/mkdir/rmdir/ creat/unlink/etc to exercise
358 such races is not showing a huge amount of res 358 such races is not showing a huge amount of restarts.
359 359
360 Dropping from rcu-walk to ref-walk mean that w 360 Dropping from rcu-walk to ref-walk mean that we have encountered a dentry where
361 the reference count needs to be taken for some 361 the reference count needs to be taken for some reason. This is either because
362 we have reached the target of the path walk, o 362 we have reached the target of the path walk, or because we have encountered a
363 condition that can't be resolved in rcu-walk m 363 condition that can't be resolved in rcu-walk mode. Ideally, we drop rcu-walk
364 only when we have reached the target dentry, s 364 only when we have reached the target dentry, so the other statistics show where
365 this does not happen. 365 this does not happen.
366 366
367 Note that a graceful drop from rcu-walk mode d 367 Note that a graceful drop from rcu-walk mode due to something such as the
368 dentry not existing (which can be common) is n 368 dentry not existing (which can be common) is not necessarily a failure of
369 rcu-walk scheme, because some elements of the 369 rcu-walk scheme, because some elements of the path may have been walked in
370 rcu-walk mode. The further we get from common 370 rcu-walk mode. The further we get from common path elements (such as cwd or
371 root), the less contended the dentry is likely 371 root), the less contended the dentry is likely to be. The closer we are to
372 common path elements, the more likely they wil 372 common path elements, the more likely they will exist in dentry cache.
373 373
374 374
375 Papers and other documentation on dcache locki 375 Papers and other documentation on dcache locking
376 ============================================== 376 ================================================
377 377
378 1. Scaling dcache with RCU (https://linuxjourn 378 1. Scaling dcache with RCU (https://linuxjournal.com/article.php?sid=7124).
379 379
380 2. http://lse.sourceforge.net/locking/dcache/d 380 2. http://lse.sourceforge.net/locking/dcache/dcache.html
381 381
382 3. path-lookup.md in this directory. 382 3. path-lookup.md in this directory.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.