Lines Matching +full:look +full:- +full:up
17 thus in every component during path look-up. Since 2.5.10 onwards, fast-walk
23 make dcache look-up lock-free.
26 dentry that was looked up, so that may be used as the basis for walking the
30 are path-walk intensive tend to do path lookups starting from a common dentry
35 (including dcache look-up) completely "store-free" (so, no locks, atomics, or
36 even stores into cachelines of common dentries). This is known as "rcu-walk"
42 A name string specifies a start (root directory, cwd, fd-relative) and a
45 elements are sub-strings, separated by '/'.
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 first parent of the lookup. Then
51 iteratively for each subsequent name element, look up the child of the current
67 - find the start point of the walk;
68 - perform permissions and validity checks on inodes;
69 - perform dcache hash name lookups on (parent, name element) tuples;
70 - traverse mount points;
71 - traverse symlinks;
72 - lookup and create missing parts of the path on demand.
74 Safe store-free look-up of dcache hash table
78 ------------------
80 and use that to select a bucket in the dcache-hash table. The list of entries
89 hash, and its inode are protected by the per-dentry d_lock spinlock. A
95 read-only protection and no durability of results, so care must be taken when
99 -------
124 +---+ +---+ +---+
125 hlist-->| N-+->| N-+->| N-+->
126 head <--+-P |<-+-P |<-+-P |
127 +---+ +---+ +---+
133 +---+ +---+ (don't worry, the longer pointers do not
134 hlist-->| N-+-------->| N-+-> impose a measurable performance overhead
135 head <--+-P |<--------+-P | on modern CPUs)
136 +---+ +---+
138 | +---+ |
139 | | N-+----+
140 +----+-P |
141 +---+
143 This is a standard RCU-list deletion, which leaves the deleted object's
148 However, when inserting object 2 onto a new list, we end up with this:
151 +---+ +---+
152 hlist-->| N-+-------->| N-+->
153 head <--+-P |<--------+-P |
154 +---+ +---+
156 +---+
157 | N-+---->
158 <----+-P |
159 +---+
176 ----------------------
187 care must be taken to load the members up-front, and use those pointers rather
192 no non-atomic stores to shared data), and to recheck the seqcount when we are
209 RCU-walk path walking design
212 Path walking code now has two distinct modes, ref-walk and rcu-walk. ref-walk
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 uses seqcount based dentry
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 non trivial operations, rcu-walk
220 must be switched to ref-walk mode.
222 [*] RCU is still used for the dentry hash lookup in ref-walk, but not the full
225 Where ref-walk uses a stable, refcounted ``parent'' to walk the remaining
226 path string, rcu-walk uses a d_seq protected snapshot. When looking up a
233 /----------------\
238 \----------------/
241 start from current->fs->root, which is a pinned dentry. Alternatively,
246 +---------------------+ rcu-walk begins here, we note d_seq, check the
247 | name: "/" | inode's permission, and then look up the next
250 +---------------------+
253 +---------------------+ ... which brings us here. We find dentry1 via
257 +---------------------+ check inode and look up the next element.
260 +---------------------+ Note: if dentry0 is now modified, lookup is
264 +---------------------+
267 +---------------------+ At this point we have our destination dentry.
271 +---------------------+
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 its refcount is called
275 "dropping rcu" or dropping from rcu-walk into ref-walk mode.
280 the path walk must be fully restarted (which we do in ref-walk mode, to avoid
285 requires ref-walk, then instead of restarting the walk, we attempt to drop rcu
286 at the last known good dentry we have. Avoiding a full restart in ref-walk in
290 The detailed design for rcu-walk is like this:
291 * LOOKUP_RCU is set in nd->flags, which distinguishes rcu-walk from ref-walk.
293 of the starting path (eg. root/cwd/fd-path). So now dentry refcounts are
296 access d_ops and i_ops during rcu-walk.
299 lookups, and to assume dentry mount points and mount roots are stable up and
301 * Have a per-dentry seqlock to protect the dentry name, parent, and inode,
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 failure.
317 The cases where rcu-walk cannot continue are:
321 It may be possible eventually to make following links rcu-walk aware.
323 Uncached path elements will always require dropping to ref-walk mode, at the
327 "store-free" path walking is not strictly store free. We take vfsmount lock
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 also have to take locks and
341 (2s12c24t Westmere, debian non-graphical system). Ungraceful are attempts to
343 again. Other cases are successful rcu-drops that are required before the final
348 rcu-lookups restart nodentry link revalidate permission
355 What this shows is that failed rcu-walk lookups, ie. ones that are restarted
356 entirely with ref-walk, are quite rare. Even the "vfstest" case which
360 Dropping from rcu-walk to ref-walk mean that we have encountered a dentry where
363 condition that can't be resolved in rcu-walk mode. Ideally, we drop rcu-walk
367 Note that a graceful drop from rcu-walk mode due to something such as 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 path elements (such as cwd or
382 3. path-lookup.md in this directory.