Commit | Line | Data |
---|---|---|
4064174b JC |
1 | =============== |
2 | Pathname lookup | |
3 | =============== | |
4 | ||
5 | This write-up is based on three articles published at lwn.net: | |
6 | ||
7 | - <https://lwn.net/Articles/649115/> Pathname lookup in Linux | |
8 | - <https://lwn.net/Articles/649729/> RCU-walk: faster pathname lookup in Linux | |
9 | - <https://lwn.net/Articles/650786/> A walk among the symlinks | |
10 | ||
11 | Written by Neil Brown with help from Al Viro and Jon Corbet. | |
12 | It has subsequently been updated to reflect changes in the kernel | |
13 | including: | |
14 | ||
15 | - per-directory parallel name lookup. | |
3ce96239 | 16 | |
7bbfd9ad N |
17 | Introduction to pathname lookup |
18 | =============================== | |
3ce96239 NB |
19 | |
20 | The most obvious aspect of pathname lookup, which very little | |
21 | exploration is needed to discover, is that it is complex. There are | |
22 | many rules, special cases, and implementation alternatives that all | |
23 | combine to confuse the unwary reader. Computer science has long been | |
24 | acquainted with such complexity and has tools to help manage it. One | |
25 | tool that we will make extensive use of is "divide and conquer". For | |
26 | the early parts of the analysis we will divide off symlinks - leaving | |
27 | them until the final part. Well before we get to symlinks we have | |
28 | another major division based on the VFS's approach to locking which | |
29 | will allow us to review "REF-walk" and "RCU-walk" separately. But we | |
30 | are getting ahead of ourselves. There are some important low level | |
31 | distinctions we need to clarify first. | |
32 | ||
33 | There are two sorts of ... | |
34 | -------------------------- | |
35 | ||
7bbfd9ad | 36 | .. _openat: http://man7.org/linux/man-pages/man2/openat.2.html |
3ce96239 NB |
37 | |
38 | Pathnames (sometimes "file names"), used to identify objects in the | |
39 | filesystem, will be familiar to most readers. They contain two sorts | |
7bbfd9ad | 40 | of elements: "slashes" that are sequences of one or more "``/``" |
3ce96239 | 41 | characters, and "components" that are sequences of one or more |
7bbfd9ad | 42 | non-"``/``" characters. These form two kinds of paths. Those that |
3ce96239 NB |
43 | start with slashes are "absolute" and start from the filesystem root. |
44 | The others are "relative" and start from the current directory, or | |
45 | from some other location specified by a file descriptor given to a | |
7bbfd9ad | 46 | "``XXXat``" system call such as `openat() <openat_>`_. |
3ce96239 | 47 | |
7bbfd9ad | 48 | .. _execveat: http://man7.org/linux/man-pages/man2/execveat.2.html |
3ce96239 NB |
49 | |
50 | It is tempting to describe the second kind as starting with a | |
51 | component, but that isn't always accurate: a pathname can lack both | |
52 | slashes and components, it can be empty, in other words. This is | |
7bbfd9ad N |
53 | generally forbidden in POSIX, but some of those "xxx``at``" system calls |
54 | in Linux permit it when the ``AT_EMPTY_PATH`` flag is given. For | |
3ce96239 | 55 | example, if you have an open file descriptor on an executable file you |
7bbfd9ad N |
56 | can execute it by calling `execveat() <execveat_>`_ passing |
57 | the file descriptor, an empty path, and the ``AT_EMPTY_PATH`` flag. | |
3ce96239 NB |
58 | |
59 | These paths can be divided into two sections: the final component and | |
60 | everything else. The "everything else" is the easy bit. In all cases | |
61 | it must identify a directory that already exists, otherwise an error | |
7bbfd9ad | 62 | such as ``ENOENT`` or ``ENOTDIR`` will be reported. |
3ce96239 NB |
63 | |
64 | The final component is not so simple. Not only do different system | |
65 | calls interpret it quite differently (e.g. some create it, some do | |
66 | not), but it might not even exist: neither the empty pathname nor the | |
67 | pathname that is just slashes have a final component. If it does | |
7bbfd9ad | 68 | exist, it could be "``.``" or "``..``" which are handled quite differently |
3ce96239 NB |
69 | from other components. |
70 | ||
7bbfd9ad | 71 | .. _POSIX: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_12 |
3ce96239 | 72 | |
7bbfd9ad | 73 | If a pathname ends with a slash, such as "``/tmp/foo/``" it might be |
3ce96239 NB |
74 | tempting to consider that to have an empty final component. In many |
75 | ways that would lead to correct results, but not always. In | |
7bbfd9ad | 76 | particular, ``mkdir()`` and ``rmdir()`` each create or remove a directory named |
3ce96239 | 77 | by the final component, and they are required to work with pathnames |
7bbfd9ad | 78 | ending in "``/``". According to POSIX_ |
3ce96239 | 79 | |
7bbfd9ad N |
80 | A pathname that contains at least one non- <slash> character and |
81 | that ends with one or more trailing <slash> characters shall not | |
82 | be resolved successfully unless the last pathname component before | |
83 | the trailing <slash> characters names an existing directory or a | |
84 | directory entry that is to be created for a directory immediately | |
85 | after the pathname is resolved. | |
3ce96239 | 86 | |
7bbfd9ad | 87 | The Linux pathname walking code (mostly in ``fs/namei.c``) deals with |
3ce96239 NB |
88 | all of these issues: breaking the path into components, handling the |
89 | "everything else" quite separately from the final component, and | |
90 | checking that the trailing slash is not used where it isn't | |
91 | permitted. It also addresses the important issue of concurrent | |
92 | access. | |
93 | ||
94 | While one process is looking up a pathname, another might be making | |
95 | changes that affect that lookup. One fairly extreme case is that if | |
96 | "a/b" were renamed to "a/c/b" while another process were looking up | |
97 | "a/b/..", that process might successfully resolve on "a/c". | |
98 | Most races are much more subtle, and a big part of the task of | |
99 | pathname lookup is to prevent them from having damaging effects. Many | |
100 | of the possible races are seen most clearly in the context of the | |
101 | "dcache" and an understanding of that is central to understanding | |
102 | pathname lookup. | |
103 | ||
7bbfd9ad N |
104 | More than just a cache |
105 | ---------------------- | |
3ce96239 NB |
106 | |
107 | The "dcache" caches information about names in each filesystem to | |
108 | make them quickly available for lookup. Each entry (known as a | |
109 | "dentry") contains three significant fields: a component name, a | |
110 | pointer to a parent dentry, and a pointer to the "inode" which | |
111 | contains further information about the object in that parent with | |
7bbfd9ad | 112 | the given name. The inode pointer can be ``NULL`` indicating that the |
3ce96239 NB |
113 | name doesn't exist in the parent. While there can be linkage in the |
114 | dentry of a directory to the dentries of the children, that linkage is | |
115 | not used for pathname lookup, and so will not be considered here. | |
116 | ||
117 | The dcache has a number of uses apart from accelerating lookup. One | |
118 | that will be particularly relevant is that it is closely integrated | |
119 | with the mount table that records which filesystem is mounted where. | |
120 | What the mount table actually stores is which dentry is mounted on top | |
121 | of which other dentry. | |
122 | ||
123 | When considering the dcache, we have another of our "two types" | |
124 | distinctions: there are two types of filesystems. | |
125 | ||
126 | Some filesystems ensure that the information in the dcache is always | |
127 | completely accurate (though not necessarily complete). This can allow | |
128 | the VFS to determine if a particular file does or doesn't exist | |
129 | without checking with the filesystem, and means that the VFS can | |
130 | protect the filesystem against certain races and other problems. | |
131 | These are typically "local" filesystems such as ext3, XFS, and Btrfs. | |
132 | ||
133 | Other filesystems don't provide that guarantee because they cannot. | |
134 | These are typically filesystems that are shared across a network, | |
135 | whether remote filesystems like NFS and 9P, or cluster filesystems | |
136 | like ocfs2 or cephfs. These filesystems allow the VFS to revalidate | |
137 | cached information, and must provide their own protection against | |
138 | awkward races. The VFS can detect these filesystems by the | |
7bbfd9ad | 139 | ``DCACHE_OP_REVALIDATE`` flag being set in the dentry. |
3ce96239 NB |
140 | |
141 | REF-walk: simple concurrency management with refcounts and spinlocks | |
142 | -------------------------------------------------------------------- | |
143 | ||
144 | With all of those divisions carefully classified, we can now start | |
145 | looking at the actual process of walking along a path. In particular | |
146 | we will start with the handling of the "everything else" part of a | |
147 | pathname, and focus on the "REF-walk" approach to concurrency | |
7bbfd9ad N |
148 | management. This code is found in the ``link_path_walk()`` function, if |
149 | you ignore all the places that only run when "``LOOKUP_RCU``" | |
3ce96239 NB |
150 | (indicating the use of RCU-walk) is set. |
151 | ||
7bbfd9ad | 152 | .. _Meet the Lockers: https://lwn.net/Articles/453685/ |
3ce96239 NB |
153 | |
154 | REF-walk is fairly heavy-handed with locks and reference counts. Not | |
155 | as heavy-handed as in the old "big kernel lock" days, but certainly not | |
156 | afraid of taking a lock when one is needed. It uses a variety of | |
157 | different concurrency controls. A background understanding of the | |
158 | various primitives is assumed, or can be gleaned from elsewhere such | |
7bbfd9ad | 159 | as in `Meet the Lockers`_. |
3ce96239 NB |
160 | |
161 | The locking mechanisms used by REF-walk include: | |
162 | ||
7bbfd9ad N |
163 | dentry->d_lockref |
164 | ~~~~~~~~~~~~~~~~~ | |
3ce96239 NB |
165 | |
166 | This uses the lockref primitive to provide both a spinlock and a | |
167 | reference count. The special-sauce of this primitive is that the | |
168 | conceptual sequence "lock; inc_ref; unlock;" can often be performed | |
169 | with a single atomic memory operation. | |
170 | ||
171 | Holding a reference on a dentry ensures that the dentry won't suddenly | |
172 | be freed and used for something else, so the values in various fields | |
7bbfd9ad | 173 | will behave as expected. It also protects the ``->d_inode`` reference |
3ce96239 NB |
174 | to the inode to some extent. |
175 | ||
176 | The association between a dentry and its inode is fairly permanent. | |
177 | For example, when a file is renamed, the dentry and inode move | |
178 | together to the new location. When a file is created the dentry will | |
7bbfd9ad | 179 | initially be negative (i.e. ``d_inode`` is ``NULL``), and will be assigned |
3ce96239 NB |
180 | to the new inode as part of the act of creation. |
181 | ||
182 | When a file is deleted, this can be reflected in the cache either by | |
7bbfd9ad | 183 | setting ``d_inode`` to ``NULL``, or by removing it from the hash table |
3ce96239 NB |
184 | (described shortly) used to look up the name in the parent directory. |
185 | If the dentry is still in use the second option is used as it is | |
186 | perfectly legal to keep using an open file after it has been deleted | |
187 | and having the dentry around helps. If the dentry is not otherwise in | |
7bbfd9ad N |
188 | use (i.e. if the refcount in ``d_lockref`` is one), only then will |
189 | ``d_inode`` be set to ``NULL``. Doing it this way is more efficient for a | |
3ce96239 NB |
190 | very common case. |
191 | ||
7bbfd9ad | 192 | So as long as a counted reference is held to a dentry, a non-``NULL`` ``->d_inode`` |
3ce96239 NB |
193 | value will never be changed. |
194 | ||
7bbfd9ad N |
195 | dentry->d_lock |
196 | ~~~~~~~~~~~~~~ | |
3ce96239 | 197 | |
7bbfd9ad | 198 | ``d_lock`` is a synonym for the spinlock that is part of ``d_lockref`` above. |
3ce96239 | 199 | For our purposes, holding this lock protects against the dentry being |
7bbfd9ad N |
200 | renamed or unlinked. In particular, its parent (``d_parent``), and its |
201 | name (``d_name``) cannot be changed, and it cannot be removed from the | |
3ce96239 NB |
202 | dentry hash table. |
203 | ||
7bbfd9ad | 204 | When looking for a name in a directory, REF-walk takes ``d_lock`` on |
3ce96239 NB |
205 | each candidate dentry that it finds in the hash table and then checks |
206 | that the parent and name are correct. So it doesn't lock the parent | |
207 | while searching in the cache; it only locks children. | |
208 | ||
7bbfd9ad N |
209 | When looking for the parent for a given name (to handle "``..``"), |
210 | REF-walk can take ``d_lock`` to get a stable reference to ``d_parent``, | |
3ce96239 | 211 | but it first tries a more lightweight approach. As seen in |
7bbfd9ad N |
212 | ``dget_parent()``, if a reference can be claimed on the parent, and if |
213 | subsequently ``d_parent`` can be seen to have not changed, then there is | |
3ce96239 NB |
214 | no need to actually take the lock on the child. |
215 | ||
7bbfd9ad N |
216 | rename_lock |
217 | ~~~~~~~~~~~ | |
3ce96239 NB |
218 | |
219 | Looking up a given name in a given directory involves computing a hash | |
220 | from the two values (the name and the dentry of the directory), | |
221 | accessing that slot in a hash table, and searching the linked list | |
222 | that is found there. | |
223 | ||
224 | When a dentry is renamed, the name and the parent dentry can both | |
225 | change so the hash will almost certainly change too. This would move the | |
226 | dentry to a different chain in the hash table. If a filename search | |
227 | happened to be looking at a dentry that was moved in this way, | |
228 | it might end up continuing the search down the wrong chain, | |
229 | and so miss out on part of the correct chain. | |
230 | ||
7bbfd9ad | 231 | The name-lookup process (``d_lookup()``) does _not_ try to prevent this |
3ce96239 | 232 | from happening, but only to detect when it happens. |
7bbfd9ad N |
233 | ``rename_lock`` is a seqlock that is updated whenever any dentry is |
234 | renamed. If ``d_lookup`` finds that a rename happened while it | |
3ce96239 NB |
235 | unsuccessfully scanned a chain in the hash table, it simply tries |
236 | again. | |
237 | ||
7bbfd9ad N |
238 | inode->i_rwsem |
239 | ~~~~~~~~~~~~~~ | |
3ce96239 | 240 | |
7bbfd9ad N |
241 | ``i_rwsem`` is a read/write semaphore that serializes all changes to a particular |
242 | directory. This ensures that, for example, an ``unlink()`` and a ``rename()`` | |
3ce96239 NB |
243 | cannot both happen at the same time. It also keeps the directory |
244 | stable while the filesystem is asked to look up a name that is not | |
1428cc0e | 245 | currently in the dcache or, optionally, when the list of entries in a |
7bbfd9ad | 246 | directory is being retrieved with ``readdir()``. |
3ce96239 | 247 | |
7bbfd9ad N |
248 | This has a complementary role to that of ``d_lock``: ``i_rwsem`` on a |
249 | directory protects all of the names in that directory, while ``d_lock`` | |
3ce96239 | 250 | on a name protects just one name in a directory. Most changes to the |
7bbfd9ad N |
251 | dcache hold ``i_rwsem`` on the relevant directory inode and briefly take |
252 | ``d_lock`` on one or more the dentries while the change happens. One | |
3ce96239 | 253 | exception is when idle dentries are removed from the dcache due to |
7bbfd9ad | 254 | memory pressure. This uses ``d_lock``, but ``i_rwsem`` plays no role. |
3ce96239 | 255 | |
1428cc0e | 256 | The semaphore affects pathname lookup in two distinct ways. Firstly it |
7bbfd9ad N |
257 | prevents changes during lookup of a name in a directory. ``walk_component()`` uses |
258 | ``lookup_fast()`` first which, in turn, checks to see if the name is in the cache, | |
259 | using only ``d_lock`` locking. If the name isn't found, then ``walk_component()`` | |
260 | falls back to ``lookup_slow()`` which takes a shared lock on ``i_rwsem``, checks again that | |
3ce96239 NB |
261 | the name isn't in the cache, and then calls in to the filesystem to get a |
262 | definitive answer. A new dentry will be added to the cache regardless of | |
263 | the result. | |
264 | ||
265 | Secondly, when pathname lookup reaches the final component, it will | |
7bbfd9ad | 266 | sometimes need to take an exclusive lock on ``i_rwsem`` before performing the last lookup so |
3ce96239 | 267 | that the required exclusion can be achieved. How path lookup chooses |
7bbfd9ad | 268 | to take, or not take, ``i_rwsem`` is one of the |
3ce96239 NB |
269 | issues addressed in a subsequent section. |
270 | ||
1428cc0e | 271 | If two threads attempt to look up the same name at the same time - a |
7bbfd9ad | 272 | name that is not yet in the dcache - the shared lock on ``i_rwsem`` will |
1428cc0e N |
273 | not prevent them both adding new dentries with the same name. As this |
274 | would result in confusion an extra level of interlocking is used, | |
7bbfd9ad N |
275 | based around a secondary hash table (``in_lookup_hashtable``) and a |
276 | per-dentry flag bit (``DCACHE_PAR_LOOKUP``). | |
1428cc0e N |
277 | |
278 | To add a new dentry to the cache while only holding a shared lock on | |
7bbfd9ad | 279 | ``i_rwsem``, a thread must call ``d_alloc_parallel()``. This allocates a |
1428cc0e N |
280 | dentry, stores the required name and parent in it, checks if there |
281 | is already a matching dentry in the primary or secondary hash | |
282 | tables, and if not, stores the newly allocated dentry in the secondary | |
7bbfd9ad | 283 | hash table, with ``DCACHE_PAR_LOOKUP`` set. |
1428cc0e N |
284 | |
285 | If a matching dentry was found in the primary hash table then that is | |
286 | returned and the caller can know that it lost a race with some other | |
287 | thread adding the entry. If no matching dentry is found in either | |
288 | cache, the newly allocated dentry is returned and the caller can | |
7bbfd9ad | 289 | detect this from the presence of ``DCACHE_PAR_LOOKUP``. In this case it |
1428cc0e N |
290 | knows that it has won any race and now is responsible for asking the |
291 | filesystem to perform the lookup and find the matching inode. When | |
7bbfd9ad | 292 | the lookup is complete, it must call ``d_lookup_done()`` which clears |
1428cc0e N |
293 | the flag and does some other house keeping, including removing the |
294 | dentry from the secondary hash table - it will normally have been | |
7bbfd9ad N |
295 | added to the primary hash table already. Note that a ``struct |
296 | waitqueue_head`` is passed to ``d_alloc_parallel()``, and | |
297 | ``d_lookup_done()`` must be called while this ``waitqueue_head`` is still | |
1428cc0e N |
298 | in scope. |
299 | ||
300 | If a matching dentry is found in the secondary hash table, | |
7bbfd9ad N |
301 | ``d_alloc_parallel()`` has a little more work to do. It first waits for |
302 | ``DCACHE_PAR_LOOKUP`` to be cleared, using a wait_queue that was passed | |
303 | to the instance of ``d_alloc_parallel()`` that won the race and that | |
304 | will be woken by the call to ``d_lookup_done()``. It then checks to see | |
1428cc0e N |
305 | if the dentry has now been added to the primary hash table. If it |
306 | has, the dentry is returned and the caller just sees that it lost any | |
307 | race. If it hasn't been added to the primary hash table, the most | |
308 | likely explanation is that some other dentry was added instead using | |
7bbfd9ad | 309 | ``d_splice_alias()``. In any case, ``d_alloc_parallel()`` repeats all the |
1428cc0e N |
310 | look ups from the start and will normally return something from the |
311 | primary hash table. | |
312 | ||
7bbfd9ad N |
313 | mnt->mnt_count |
314 | ~~~~~~~~~~~~~~ | |
3ce96239 | 315 | |
7bbfd9ad | 316 | ``mnt_count`` is a per-CPU reference counter on "``mount``" structures. |
3ce96239 NB |
317 | Per-CPU here means that incrementing the count is cheap as it only |
318 | uses CPU-local memory, but checking if the count is zero is expensive as | |
7bbfd9ad | 319 | it needs to check with every CPU. Taking a ``mnt_count`` reference |
3ce96239 NB |
320 | prevents the mount structure from disappearing as the result of regular |
321 | unmount operations, but does not prevent a "lazy" unmount. So holding | |
7bbfd9ad | 322 | ``mnt_count`` doesn't ensure that the mount remains in the namespace and, |
3ce96239 | 323 | in particular, doesn't stabilize the link to the mounted-on dentry. It |
7bbfd9ad | 324 | does, however, ensure that the ``mount`` data structure remains coherent, |
3ce96239 | 325 | and it provides a reference to the root dentry of the mounted |
7bbfd9ad | 326 | filesystem. So a reference through ``->mnt_count`` provides a stable |
3ce96239 NB |
327 | reference to the mounted dentry, but not the mounted-on dentry. |
328 | ||
7bbfd9ad N |
329 | mount_lock |
330 | ~~~~~~~~~~ | |
3ce96239 | 331 | |
7bbfd9ad | 332 | ``mount_lock`` is a global seqlock, a bit like ``rename_lock``. It can be used to |
3ce96239 NB |
333 | check if any change has been made to any mount points. |
334 | ||
335 | While walking down the tree (away from the root) this lock is used when | |
336 | crossing a mount point to check that the crossing was safe. That is, | |
337 | the value in the seqlock is read, then the code finds the mount that | |
338 | is mounted on the current directory, if there is one, and increments | |
7bbfd9ad | 339 | the ``mnt_count``. Finally the value in ``mount_lock`` is checked against |
3ce96239 | 340 | the old value. If there is no change, then the crossing was safe. If there |
7bbfd9ad | 341 | was a change, the ``mnt_count`` is decremented and the whole process is |
3ce96239 NB |
342 | retried. |
343 | ||
344 | When walking up the tree (towards the root) by following a ".." link, | |
345 | a little more care is needed. In this case the seqlock (which | |
346 | contains both a counter and a spinlock) is fully locked to prevent | |
347 | any changes to any mount points while stepping up. This locking is | |
348 | needed to stabilize the link to the mounted-on dentry, which the | |
349 | refcount on the mount itself doesn't ensure. | |
350 | ||
7bbfd9ad N |
351 | RCU |
352 | ~~~ | |
3ce96239 NB |
353 | |
354 | Finally the global (but extremely lightweight) RCU read lock is held | |
355 | from time to time to ensure certain data structures don't get freed | |
356 | unexpectedly. | |
357 | ||
358 | In particular it is held while scanning chains in the dcache hash | |
359 | table, and the mount point hash table. | |
360 | ||
7bbfd9ad | 361 | Bringing it together with ``struct nameidata`` |
9f63df26 | 362 | ---------------------------------------------- |
3ce96239 | 363 | |
7bbfd9ad | 364 | .. _First edition Unix: http://minnie.tuhs.org/cgi-bin/utree.pl?file=V1/u2.s |
3ce96239 NB |
365 | |
366 | Throughout the process of walking a path, the current status is stored | |
7bbfd9ad N |
367 | in a ``struct nameidata``, "namei" being the traditional name - dating |
368 | all the way back to `First Edition Unix`_ - of the function that | |
369 | converts a "name" to an "inode". ``struct nameidata`` contains (among | |
3ce96239 NB |
370 | other fields): |
371 | ||
7bbfd9ad | 372 | ``struct path path`` |
9f63df26 | 373 | ~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 374 | |
7bbfd9ad N |
375 | A ``path`` contains a ``struct vfsmount`` (which is |
376 | embedded in a ``struct mount``) and a ``struct dentry``. Together these | |
3ce96239 NB |
377 | record the current status of the walk. They start out referring to the |
378 | starting point (the current working directory, the root directory, or some other | |
379 | directory identified by a file descriptor), and are updated on each | |
7bbfd9ad | 380 | step. A reference through ``d_lockref`` and ``mnt_count`` is always |
3ce96239 NB |
381 | held. |
382 | ||
7bbfd9ad | 383 | ``struct qstr last`` |
9f63df26 | 384 | ~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 385 | |
7bbfd9ad | 386 | This is a string together with a length (i.e. _not_ ``nul`` terminated) |
3ce96239 NB |
387 | that is the "next" component in the pathname. |
388 | ||
7bbfd9ad | 389 | ``int last_type`` |
9f63df26 | 390 | ~~~~~~~~~~~~~~~~~ |
3ce96239 | 391 | |
7bbfd9ad N |
392 | This is one of ``LAST_NORM``, ``LAST_ROOT``, ``LAST_DOT``, ``LAST_DOTDOT``, or |
393 | ``LAST_BIND``. The ``last`` field is only valid if the type is | |
394 | ``LAST_NORM``. ``LAST_BIND`` is used when following a symlink and no | |
3ce96239 NB |
395 | components of the symlink have been processed yet. Others should be |
396 | fairly self-explanatory. | |
397 | ||
7bbfd9ad | 398 | ``struct path root`` |
9f63df26 | 399 | ~~~~~~~~~~~~~~~~~~~~ |
3ce96239 NB |
400 | |
401 | This is used to hold a reference to the effective root of the | |
402 | filesystem. Often that reference won't be needed, so this field is | |
403 | only assigned the first time it is used, or when a non-standard root | |
7bbfd9ad | 404 | is requested. Keeping a reference in the ``nameidata`` ensures that |
3ce96239 | 405 | only one root is in effect for the entire path walk, even if it races |
7bbfd9ad | 406 | with a ``chroot()`` system call. |
3ce96239 NB |
407 | |
408 | The root is needed when either of two conditions holds: (1) either the | |
7bbfd9ad N |
409 | pathname or a symbolic link starts with a "'/'", or (2) a "``..``" |
410 | component is being handled, since "``..``" from the root must always stay | |
3ce96239 NB |
411 | at the root. The value used is usually the current root directory of |
412 | the calling process. An alternate root can be provided as when | |
7bbfd9ad N |
413 | ``sysctl()`` calls ``file_open_root()``, and when NFSv4 or Btrfs call |
414 | ``mount_subtree()``. In each case a pathname is being looked up in a very | |
3ce96239 | 415 | specific part of the filesystem, and the lookup must not be allowed to |
7bbfd9ad | 416 | escape that subtree. It works a bit like a local ``chroot()``. |
3ce96239 NB |
417 | |
418 | Ignoring the handling of symbolic links, we can now describe the | |
7bbfd9ad | 419 | "``link_path_walk()``" function, which handles the lookup of everything |
3ce96239 NB |
420 | except the final component as: |
421 | ||
7bbfd9ad N |
422 | Given a path (``name``) and a nameidata structure (``nd``), check that the |
423 | current directory has execute permission and then advance ``name`` | |
424 | over one component while updating ``last_type`` and ``last``. If that | |
425 | was the final component, then return, otherwise call | |
426 | ``walk_component()`` and repeat from the top. | |
3ce96239 | 427 | |
7bbfd9ad N |
428 | ``walk_component()`` is even easier. If the component is ``LAST_DOTS``, |
429 | it calls ``handle_dots()`` which does the necessary locking as already | |
430 | described. If it finds a ``LAST_NORM`` component it first calls | |
431 | "``lookup_fast()``" which only looks in the dcache, but will ask the | |
3ce96239 | 432 | filesystem to revalidate the result if it is that sort of filesystem. |
7bbfd9ad N |
433 | If that doesn't get a good result, it calls "``lookup_slow()``" which |
434 | takes ``i_rwsem``, rechecks the cache, and then asks the filesystem | |
3ce96239 | 435 | to find a definitive answer. Each of these will call |
7bbfd9ad | 436 | ``follow_managed()`` (as described below) to handle any mount points. |
3ce96239 | 437 | |
7bbfd9ad N |
438 | In the absence of symbolic links, ``walk_component()`` creates a new |
439 | ``struct path`` containing a counted reference to the new dentry and a | |
440 | reference to the new ``vfsmount`` which is only counted if it is | |
441 | different from the previous ``vfsmount``. It then calls | |
442 | ``path_to_nameidata()`` to install the new ``struct path`` in the | |
443 | ``struct nameidata`` and drop the unneeded references. | |
3ce96239 NB |
444 | |
445 | This "hand-over-hand" sequencing of getting a reference to the new | |
446 | dentry before dropping the reference to the previous dentry may | |
447 | seem obvious, but is worth pointing out so that we will recognize its | |
448 | analogue in the "RCU-walk" version. | |
449 | ||
7bbfd9ad N |
450 | Handling the final component |
451 | ---------------------------- | |
3ce96239 | 452 | |
7bbfd9ad N |
453 | ``link_path_walk()`` only walks as far as setting ``nd->last`` and |
454 | ``nd->last_type`` to refer to the final component of the path. It does | |
455 | not call ``walk_component()`` that last time. Handling that final | |
3ce96239 | 456 | component remains for the caller to sort out. Those callers are |
7bbfd9ad N |
457 | ``path_lookupat()``, ``path_parentat()``, ``path_mountpoint()`` and |
458 | ``path_openat()`` each of which handles the differing requirements of | |
3ce96239 NB |
459 | different system calls. |
460 | ||
7bbfd9ad N |
461 | ``path_parentat()`` is clearly the simplest - it just wraps a little bit |
462 | of housekeeping around ``link_path_walk()`` and returns the parent | |
3ce96239 | 463 | directory and final component to the caller. The caller will be either |
7bbfd9ad N |
464 | aiming to create a name (via ``filename_create()``) or remove or rename |
465 | a name (in which case ``user_path_parent()`` is used). They will use | |
466 | ``i_rwsem`` to exclude other changes while they validate and then | |
3ce96239 NB |
467 | perform their operation. |
468 | ||
7bbfd9ad N |
469 | ``path_lookupat()`` is nearly as simple - it is used when an existing |
470 | object is wanted such as by ``stat()`` or ``chmod()``. It essentially just | |
471 | calls ``walk_component()`` on the final component through a call to | |
472 | ``lookup_last()``. ``path_lookupat()`` returns just the final dentry. | |
3ce96239 | 473 | |
7bbfd9ad | 474 | ``path_mountpoint()`` handles the special case of unmounting which must |
3ce96239 | 475 | not try to revalidate the mounted filesystem. It effectively |
7bbfd9ad N |
476 | contains, through a call to ``mountpoint_last()``, an alternate |
477 | implementation of ``lookup_slow()`` which skips that step. This is | |
3ce96239 NB |
478 | important when unmounting a filesystem that is inaccessible, such as |
479 | one provided by a dead NFS server. | |
480 | ||
7bbfd9ad N |
481 | Finally ``path_openat()`` is used for the ``open()`` system call; it |
482 | contains, in support functions starting with "``do_last()``", all the | |
3ce96239 | 483 | complexity needed to handle the different subtleties of O_CREAT (with |
7bbfd9ad | 484 | or without O_EXCL), final "``/``" characters, and trailing symbolic |
3ce96239 | 485 | links. We will revisit this in the final part of this series, which |
7bbfd9ad N |
486 | focuses on those symbolic links. "``do_last()``" will sometimes, but |
487 | not always, take ``i_rwsem``, depending on what it finds. | |
3ce96239 NB |
488 | |
489 | Each of these, or the functions which call them, need to be alert to | |
7bbfd9ad | 490 | the possibility that the final component is not ``LAST_NORM``. If the |
3ce96239 | 491 | goal of the lookup is to create something, then any value for |
7bbfd9ad N |
492 | ``last_type`` other than ``LAST_NORM`` will result in an error. For |
493 | example if ``path_parentat()`` reports ``LAST_DOTDOT``, then the caller | |
3ce96239 | 494 | won't try to create that name. They also check for trailing slashes |
7bbfd9ad | 495 | by testing ``last.name[last.len]``. If there is any character beyond |
3ce96239 NB |
496 | the final component, it must be a trailing slash. |
497 | ||
498 | Revalidation and automounts | |
499 | --------------------------- | |
500 | ||
501 | Apart from symbolic links, there are only two parts of the "REF-walk" | |
502 | process not yet covered. One is the handling of stale cache entries | |
503 | and the other is automounts. | |
504 | ||
505 | On filesystems that require it, the lookup routines will call the | |
7bbfd9ad | 506 | ``->d_revalidate()`` dentry method to ensure that the cached information |
3ce96239 NB |
507 | is current. This will often confirm validity or update a few details |
508 | from a server. In some cases it may find that there has been change | |
509 | further up the path and that something that was thought to be valid | |
510 | previously isn't really. When this happens the lookup of the whole | |
7bbfd9ad | 511 | path is aborted and retried with the "``LOOKUP_REVAL``" flag set. This |
3ce96239 NB |
512 | forces revalidation to be more thorough. We will see more details of |
513 | this retry process in the next article. | |
514 | ||
515 | Automount points are locations in the filesystem where an attempt to | |
516 | lookup a name can trigger changes to how that lookup should be | |
517 | handled, in particular by mounting a filesystem there. These are | |
b6bb226a | 518 | covered in greater detail in autofs.txt in the Linux documentation |
3ce96239 NB |
519 | tree, but a few notes specifically related to path lookup are in order |
520 | here. | |
521 | ||
522 | The Linux VFS has a concept of "managed" dentries which is reflected | |
7bbfd9ad | 523 | in function names such as "``follow_managed()``". There are three |
3ce96239 | 524 | potentially interesting things about these dentries corresponding |
7bbfd9ad | 525 | to three different flags that might be set in ``dentry->d_flags``: |
3ce96239 | 526 | |
7bbfd9ad | 527 | ``DCACHE_MANAGE_TRANSIT`` |
9f63df26 | 528 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 NB |
529 | |
530 | If this flag has been set, then the filesystem has requested that the | |
7bbfd9ad | 531 | ``d_manage()`` dentry operation be called before handling any possible |
3ce96239 NB |
532 | mount point. This can perform two particular services: |
533 | ||
534 | It can block to avoid races. If an automount point is being | |
7bbfd9ad | 535 | unmounted, the ``d_manage()`` function will usually wait for that |
3ce96239 NB |
536 | process to complete before letting the new lookup proceed and possibly |
537 | trigger a new automount. | |
538 | ||
539 | It can selectively allow only some processes to transit through a | |
540 | mount point. When a server process is managing automounts, it may | |
541 | need to access a directory without triggering normal automount | |
7bbfd9ad | 542 | processing. That server process can identify itself to the ``autofs`` |
3ce96239 | 543 | filesystem, which will then give it a special pass through |
7bbfd9ad | 544 | ``d_manage()`` by returning ``-EISDIR``. |
3ce96239 | 545 | |
7bbfd9ad | 546 | ``DCACHE_MOUNTED`` |
9f63df26 | 547 | ~~~~~~~~~~~~~~~~~~ |
3ce96239 NB |
548 | |
549 | This flag is set on every dentry that is mounted on. As Linux | |
550 | supports multiple filesystem namespaces, it is possible that the | |
551 | dentry may not be mounted on in *this* namespace, just in some | |
552 | other. So this flag is seen as a hint, not a promise. | |
553 | ||
7bbfd9ad N |
554 | If this flag is set, and ``d_manage()`` didn't return ``-EISDIR``, |
555 | ``lookup_mnt()`` is called to examine the mount hash table (honoring the | |
556 | ``mount_lock`` described earlier) and possibly return a new ``vfsmount`` | |
557 | and a new ``dentry`` (both with counted references). | |
3ce96239 | 558 | |
7bbfd9ad | 559 | ``DCACHE_NEED_AUTOMOUNT`` |
9f63df26 | 560 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 561 | |
7bbfd9ad N |
562 | If ``d_manage()`` allowed us to get this far, and ``lookup_mnt()`` didn't |
563 | find a mount point, then this flag causes the ``d_automount()`` dentry | |
3ce96239 NB |
564 | operation to be called. |
565 | ||
7bbfd9ad | 566 | The ``d_automount()`` operation can be arbitrarily complex and may |
3ce96239 NB |
567 | communicate with server processes etc. but it should ultimately either |
568 | report that there was an error, that there was nothing to mount, or | |
7bbfd9ad | 569 | should provide an updated ``struct path`` with new ``dentry`` and ``vfsmount``. |
3ce96239 | 570 | |
7bbfd9ad | 571 | In the latter case, ``finish_automount()`` will be called to safely |
3ce96239 NB |
572 | install the new mount point into the mount table. |
573 | ||
574 | There is no new locking of import here and it is important that no | |
575 | locks (only counted references) are held over this processing due to | |
576 | the very real possibility of extended delays. | |
577 | This will become more important next time when we examine RCU-walk | |
578 | which is particularly sensitive to delays. | |
579 | ||
580 | RCU-walk - faster pathname lookup in Linux | |
581 | ========================================== | |
582 | ||
583 | RCU-walk is another algorithm for performing pathname lookup in Linux. | |
584 | It is in many ways similar to REF-walk and the two share quite a bit | |
585 | of code. The significant difference in RCU-walk is how it allows for | |
586 | the possibility of concurrent access. | |
587 | ||
588 | We noted that REF-walk is complex because there are numerous details | |
589 | and special cases. RCU-walk reduces this complexity by simply | |
590 | refusing to handle a number of cases -- it instead falls back to | |
591 | REF-walk. The difficulty with RCU-walk comes from a different | |
592 | direction: unfamiliarity. The locking rules when depending on RCU are | |
593 | quite different from traditional locking, so we will spend a little extra | |
594 | time when we come to those. | |
595 | ||
596 | Clear demarcation of roles | |
597 | -------------------------- | |
598 | ||
599 | The easiest way to manage concurrency is to forcibly stop any other | |
600 | thread from changing the data structures that a given thread is | |
601 | looking at. In cases where no other thread would even think of | |
602 | changing the data and lots of different threads want to read at the | |
603 | same time, this can be very costly. Even when using locks that permit | |
604 | multiple concurrent readers, the simple act of updating the count of | |
605 | the number of current readers can impose an unwanted cost. So the | |
606 | goal when reading a shared data structure that no other process is | |
607 | changing is to avoid writing anything to memory at all. Take no | |
608 | locks, increment no counts, leave no footprints. | |
609 | ||
610 | The REF-walk mechanism already described certainly doesn't follow this | |
611 | principle, but then it is really designed to work when there may well | |
612 | be other threads modifying the data. RCU-walk, in contrast, is | |
613 | designed for the common situation where there are lots of frequent | |
614 | readers and only occasional writers. This may not be common in all | |
615 | parts of the filesystem tree, but in many parts it will be. For the | |
616 | other parts it is important that RCU-walk can quickly fall back to | |
617 | using REF-walk. | |
618 | ||
619 | Pathname lookup always starts in RCU-walk mode but only remains there | |
620 | as long as what it is looking for is in the cache and is stable. It | |
621 | dances lightly down the cached filesystem image, leaving no footprints | |
622 | and carefully watching where it is, to be sure it doesn't trip. If it | |
623 | notices that something has changed or is changing, or if something | |
624 | isn't in the cache, then it tries to stop gracefully and switch to | |
625 | REF-walk. | |
626 | ||
627 | This stopping requires getting a counted reference on the current | |
7bbfd9ad | 628 | ``vfsmount`` and ``dentry``, and ensuring that these are still valid - |
3ce96239 NB |
629 | that a path walk with REF-walk would have found the same entries. |
630 | This is an invariant that RCU-walk must guarantee. It can only make | |
631 | decisions, such as selecting the next step, that are decisions which | |
632 | REF-walk could also have made if it were walking down the tree at the | |
633 | same time. If the graceful stop succeeds, the rest of the path is | |
634 | processed with the reliable, if slightly sluggish, REF-walk. If | |
635 | RCU-walk finds it cannot stop gracefully, it simply gives up and | |
636 | restarts from the top with REF-walk. | |
637 | ||
638 | This pattern of "try RCU-walk, if that fails try REF-walk" can be | |
7bbfd9ad N |
639 | clearly seen in functions like ``filename_lookup()``, |
640 | ``filename_parentat()``, ``filename_mountpoint()``, | |
641 | ``do_filp_open()``, and ``do_file_open_root()``. These five | |
642 | correspond roughly to the four ``path_``* functions we met earlier, | |
643 | each of which calls ``link_path_walk()``. The ``path_*`` functions are | |
3ce96239 | 644 | called using different mode flags until a mode is found which works. |
7bbfd9ad N |
645 | They are first called with ``LOOKUP_RCU`` set to request "RCU-walk". If |
646 | that fails with the error ``ECHILD`` they are called again with no | |
3ce96239 | 647 | special flag to request "REF-walk". If either of those report the |
7bbfd9ad N |
648 | error ``ESTALE`` a final attempt is made with ``LOOKUP_REVAL`` set (and no |
649 | ``LOOKUP_RCU``) to ensure that entries found in the cache are forcibly | |
3ce96239 NB |
650 | revalidated - normally entries are only revalidated if the filesystem |
651 | determines that they are too old to trust. | |
652 | ||
7bbfd9ad | 653 | The ``LOOKUP_RCU`` attempt may drop that flag internally and switch to |
3ce96239 NB |
654 | REF-walk, but will never then try to switch back to RCU-walk. Places |
655 | that trip up RCU-walk are much more likely to be near the leaves and | |
656 | so it is very unlikely that there will be much, if any, benefit from | |
657 | switching back. | |
658 | ||
659 | RCU and seqlocks: fast and light | |
660 | -------------------------------- | |
661 | ||
662 | RCU is, unsurprisingly, critical to RCU-walk mode. The | |
7bbfd9ad | 663 | ``rcu_read_lock()`` is held for the entire time that RCU-walk is walking |
3ce96239 NB |
664 | down a path. The particular guarantee it provides is that the key |
665 | data structures - dentries, inodes, super_blocks, and mounts - will | |
666 | not be freed while the lock is held. They might be unlinked or | |
667 | invalidated in one way or another, but the memory will not be | |
668 | repurposed so values in various fields will still be meaningful. This | |
669 | is the only guarantee that RCU provides; everything else is done using | |
670 | seqlocks. | |
671 | ||
672 | As we saw above, REF-walk holds a counted reference to the current | |
673 | dentry and the current vfsmount, and does not release those references | |
674 | before taking references to the "next" dentry or vfsmount. It also | |
7bbfd9ad | 675 | sometimes takes the ``d_lock`` spinlock. These references and locks are |
3ce96239 NB |
676 | taken to prevent certain changes from happening. RCU-walk must not |
677 | take those references or locks and so cannot prevent such changes. | |
678 | Instead, it checks to see if a change has been made, and aborts or | |
679 | retries if it has. | |
680 | ||
681 | To preserve the invariant mentioned above (that RCU-walk may only make | |
682 | decisions that REF-walk could have made), it must make the checks at | |
683 | or near the same places that REF-walk holds the references. So, when | |
684 | REF-walk increments a reference count or takes a spinlock, RCU-walk | |
7bbfd9ad | 685 | samples the status of a seqlock using ``read_seqcount_begin()`` or a |
3ce96239 NB |
686 | similar function. When REF-walk decrements the count or drops the |
687 | lock, RCU-walk checks if the sampled status is still valid using | |
7bbfd9ad | 688 | ``read_seqcount_retry()`` or similar. |
3ce96239 NB |
689 | |
690 | However, there is a little bit more to seqlocks than that. If | |
691 | RCU-walk accesses two different fields in a seqlock-protected | |
692 | structure, or accesses the same field twice, there is no a priori | |
693 | guarantee of any consistency between those accesses. When consistency | |
694 | is needed - which it usually is - RCU-walk must take a copy and then | |
7bbfd9ad | 695 | use ``read_seqcount_retry()`` to validate that copy. |
3ce96239 | 696 | |
7bbfd9ad | 697 | ``read_seqcount_retry()`` not only checks the sequence number, but also |
3ce96239 NB |
698 | imposes a memory barrier so that no memory-read instruction from |
699 | *before* the call can be delayed until *after* the call, either by the | |
700 | CPU or by the compiler. A simple example of this can be seen in | |
7bbfd9ad | 701 | ``slow_dentry_cmp()`` which, for filesystems which do not use simple |
3ce96239 NB |
702 | byte-wise name equality, calls into the filesystem to compare a name |
703 | against a dentry. The length and name pointer are copied into local | |
7bbfd9ad N |
704 | variables, then ``read_seqcount_retry()`` is called to confirm the two |
705 | are consistent, and only then is ``->d_compare()`` called. When | |
706 | standard filename comparison is used, ``dentry_cmp()`` is called | |
707 | instead. Notably it does _not_ use ``read_seqcount_retry()``, but | |
3ce96239 | 708 | instead has a large comment explaining why the consistency guarantee |
7bbfd9ad | 709 | isn't necessary. A subsequent ``read_seqcount_retry()`` will be |
3ce96239 NB |
710 | sufficient to catch any problem that could occur at this point. |
711 | ||
712 | With that little refresher on seqlocks out of the way we can look at | |
713 | the bigger picture of how RCU-walk uses seqlocks. | |
714 | ||
7bbfd9ad | 715 | ``mount_lock`` and ``nd->m_seq`` |
9f63df26 | 716 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 717 | |
7bbfd9ad | 718 | We already met the ``mount_lock`` seqlock when REF-walk used it to |
3ce96239 NB |
719 | ensure that crossing a mount point is performed safely. RCU-walk uses |
720 | it for that too, but for quite a bit more. | |
721 | ||
7bbfd9ad N |
722 | Instead of taking a counted reference to each ``vfsmount`` as it |
723 | descends the tree, RCU-walk samples the state of ``mount_lock`` at the | |
3ce96239 | 724 | start of the walk and stores this initial sequence number in the |
7bbfd9ad N |
725 | ``struct nameidata`` in the ``m_seq`` field. This one lock and one |
726 | sequence number are used to validate all accesses to all ``vfsmounts``, | |
3ce96239 NB |
727 | and all mount point crossings. As changes to the mount table are |
728 | relatively rare, it is reasonable to fall back on REF-walk any time | |
729 | that any "mount" or "unmount" happens. | |
730 | ||
7bbfd9ad | 731 | ``m_seq`` is checked (using ``read_seqretry()``) at the end of an RCU-walk |
3ce96239 NB |
732 | sequence, whether switching to REF-walk for the rest of the path or |
733 | when the end of the path is reached. It is also checked when stepping | |
7bbfd9ad N |
734 | down over a mount point (in ``__follow_mount_rcu()``) or up (in |
735 | ``follow_dotdot_rcu()``). If it is ever found to have changed, the | |
3ce96239 NB |
736 | whole RCU-walk sequence is aborted and the path is processed again by |
737 | REF-walk. | |
738 | ||
7bbfd9ad | 739 | If RCU-walk finds that ``mount_lock`` hasn't changed then it can be sure |
3ce96239 NB |
740 | that, had REF-walk taken counted references on each vfsmount, the |
741 | results would have been the same. This ensures the invariant holds, | |
742 | at least for vfsmount structures. | |
743 | ||
7bbfd9ad | 744 | ``dentry->d_seq`` and ``nd->seq`` |
9f63df26 | 745 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 746 | |
7bbfd9ad N |
747 | In place of taking a count or lock on ``d_reflock``, RCU-walk samples |
748 | the per-dentry ``d_seq`` seqlock, and stores the sequence number in the | |
749 | ``seq`` field of the nameidata structure, so ``nd->seq`` should always be | |
750 | the current sequence number of ``nd->dentry``. This number needs to be | |
3ce96239 NB |
751 | revalidated after copying, and before using, the name, parent, or |
752 | inode of the dentry. | |
753 | ||
754 | The handling of the name we have already looked at, and the parent is | |
7bbfd9ad | 755 | only accessed in ``follow_dotdot_rcu()`` which fairly trivially follows |
3ce96239 NB |
756 | the required pattern, though it does so for three different cases. |
757 | ||
7bbfd9ad | 758 | When not at a mount point, ``d_parent`` is followed and its ``d_seq`` is |
3ce96239 | 759 | collected. When we are at a mount point, we instead follow the |
7bbfd9ad N |
760 | ``mnt->mnt_mountpoint`` link to get a new dentry and collect its |
761 | ``d_seq``. Then, after finally finding a ``d_parent`` to follow, we must | |
3ce96239 | 762 | check if we have landed on a mount point and, if so, must find that |
7bbfd9ad | 763 | mount point and follow the ``mnt->mnt_root`` link. This would imply a |
3ce96239 NB |
764 | somewhat unusual, but certainly possible, circumstance where the |
765 | starting point of the path lookup was in part of the filesystem that | |
766 | was mounted on, and so not visible from the root. | |
767 | ||
7bbfd9ad | 768 | The inode pointer, stored in ``->d_inode``, is a little more |
3ce96239 NB |
769 | interesting. The inode will always need to be accessed at least |
770 | twice, once to determine if it is NULL and once to verify access | |
771 | permissions. Symlink handling requires a validated inode pointer too. | |
772 | Rather than revalidating on each access, a copy is made on the first | |
7bbfd9ad | 773 | access and it is stored in the ``inode`` field of ``nameidata`` from where |
3ce96239 NB |
774 | it can be safely accessed without further validation. |
775 | ||
7bbfd9ad N |
776 | ``lookup_fast()`` is the only lookup routine that is used in RCU-mode, |
777 | ``lookup_slow()`` being too slow and requiring locks. It is in | |
778 | ``lookup_fast()`` that we find the important "hand over hand" tracking | |
3ce96239 NB |
779 | of the current dentry. |
780 | ||
7bbfd9ad N |
781 | The current ``dentry`` and current ``seq`` number are passed to |
782 | ``__d_lookup_rcu()`` which, on success, returns a new ``dentry`` and a | |
783 | new ``seq`` number. ``lookup_fast()`` then copies the inode pointer and | |
784 | revalidates the new ``seq`` number. It then validates the old ``dentry`` | |
785 | with the old ``seq`` number one last time and only then continues. This | |
786 | process of getting the ``seq`` number of the new dentry and then | |
787 | checking the ``seq`` number of the old exactly mirrors the process of | |
3ce96239 NB |
788 | getting a counted reference to the new dentry before dropping that for |
789 | the old dentry which we saw in REF-walk. | |
790 | ||
7bbfd9ad | 791 | No ``inode->i_rwsem`` or even ``rename_lock`` |
9f63df26 | 792 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 793 | |
1428cc0e | 794 | A semaphore is a fairly heavyweight lock that can only be taken when it is |
7bbfd9ad N |
795 | permissible to sleep. As ``rcu_read_lock()`` forbids sleeping, |
796 | ``inode->i_rwsem`` plays no role in RCU-walk. If some other thread does | |
797 | take ``i_rwsem`` and modifies the directory in a way that RCU-walk needs | |
3ce96239 NB |
798 | to notice, the result will be either that RCU-walk fails to find the |
799 | dentry that it is looking for, or it will find a dentry which | |
7bbfd9ad | 800 | ``read_seqretry()`` won't validate. In either case it will drop down to |
3ce96239 NB |
801 | REF-walk mode which can take whatever locks are needed. |
802 | ||
7bbfd9ad N |
803 | Though ``rename_lock`` could be used by RCU-walk as it doesn't require |
804 | any sleeping, RCU-walk doesn't bother. REF-walk uses ``rename_lock`` to | |
3ce96239 NB |
805 | protect against the possibility of hash chains in the dcache changing |
806 | while they are being searched. This can result in failing to find | |
807 | something that actually is there. When RCU-walk fails to find | |
808 | something in the dentry cache, whether it is really there or not, it | |
809 | already drops down to REF-walk and tries again with appropriate | |
810 | locking. This neatly handles all cases, so adding extra checks on | |
811 | rename_lock would bring no significant value. | |
812 | ||
7bbfd9ad | 813 | ``unlazy walk()`` and ``complete_walk()`` |
9f63df26 | 814 | ----------------------------------------- |
3ce96239 NB |
815 | |
816 | That "dropping down to REF-walk" typically involves a call to | |
7bbfd9ad N |
817 | ``unlazy_walk()``, so named because "RCU-walk" is also sometimes |
818 | referred to as "lazy walk". ``unlazy_walk()`` is called when | |
3ce96239 NB |
819 | following the path down to the current vfsmount/dentry pair seems to |
820 | have proceeded successfully, but the next step is problematic. This | |
821 | can happen if the next name cannot be found in the dcache, if | |
822 | permission checking or name revalidation couldn't be achieved while | |
7bbfd9ad | 823 | the ``rcu_read_lock()`` is held (which forbids sleeping), if an |
3ce96239 | 824 | automount point is found, or in a couple of cases involving symlinks. |
7bbfd9ad | 825 | It is also called from ``complete_walk()`` when the lookup has reached |
3ce96239 NB |
826 | the final component, or the very end of the path, depending on which |
827 | particular flavor of lookup is used. | |
828 | ||
829 | Other reasons for dropping out of RCU-walk that do not trigger a call | |
7bbfd9ad N |
830 | to ``unlazy_walk()`` are when some inconsistency is found that cannot be |
831 | handled immediately, such as ``mount_lock`` or one of the ``d_seq`` | |
3ce96239 | 832 | seqlocks reporting a change. In these cases the relevant function |
7bbfd9ad | 833 | will return ``-ECHILD`` which will percolate up until it triggers a new |
3ce96239 NB |
834 | attempt from the top using REF-walk. |
835 | ||
7bbfd9ad | 836 | For those cases where ``unlazy_walk()`` is an option, it essentially |
3ce96239 NB |
837 | takes a reference on each of the pointers that it holds (vfsmount, |
838 | dentry, and possibly some symbolic links) and then verifies that the | |
839 | relevant seqlocks have not been changed. If there have been changes, | |
7bbfd9ad | 840 | it, too, aborts with ``-ECHILD``, otherwise the transition to REF-walk |
3ce96239 NB |
841 | has been a success and the lookup process continues. |
842 | ||
843 | Taking a reference on those pointers is not quite as simple as just | |
844 | incrementing a counter. That works to take a second reference if you | |
845 | already have one (often indirectly through another object), but it | |
846 | isn't sufficient if you don't actually have a counted reference at | |
7bbfd9ad | 847 | all. For ``dentry->d_lockref``, it is safe to increment the reference |
3ce96239 | 848 | counter to get a reference unless it has been explicitly marked as |
7bbfd9ad N |
849 | "dead" which involves setting the counter to ``-128``. |
850 | ``lockref_get_not_dead()`` achieves this. | |
3ce96239 | 851 | |
7bbfd9ad N |
852 | For ``mnt->mnt_count`` it is safe to take a reference as long as |
853 | ``mount_lock`` is then used to validate the reference. If that | |
3ce96239 | 854 | validation fails, it may *not* be safe to just drop that reference in |
7bbfd9ad N |
855 | the standard way of calling ``mnt_put()`` - an unmount may have |
856 | progressed too far. So the code in ``legitimize_mnt()``, when it | |
3ce96239 | 857 | finds that the reference it got might not be safe, checks the |
7bbfd9ad | 858 | ``MNT_SYNC_UMOUNT`` flag to determine if a simple ``mnt_put()`` is |
3ce96239 NB |
859 | correct, or if it should just decrement the count and pretend none of |
860 | this ever happened. | |
861 | ||
862 | Taking care in filesystems | |
7bbfd9ad | 863 | -------------------------- |
3ce96239 NB |
864 | |
865 | RCU-walk depends almost entirely on cached information and often will | |
866 | not call into the filesystem at all. However there are two places, | |
867 | besides the already-mentioned component-name comparison, where the | |
868 | file system might be included in RCU-walk, and it must know to be | |
869 | careful. | |
870 | ||
871 | If the filesystem has non-standard permission-checking requirements - | |
872 | such as a networked filesystem which may need to check with the server | |
7bbfd9ad N |
873 | - the ``i_op->permission`` interface might be called during RCU-walk. |
874 | In this case an extra "``MAY_NOT_BLOCK``" flag is passed so that it | |
875 | knows not to sleep, but to return ``-ECHILD`` if it cannot complete | |
876 | promptly. ``i_op->permission`` is given the inode pointer, not the | |
3ce96239 NB |
877 | dentry, so it doesn't need to worry about further consistency checks. |
878 | However if it accesses any other filesystem data structures, it must | |
7bbfd9ad N |
879 | ensure they are safe to be accessed with only the ``rcu_read_lock()`` |
880 | held. This typically means they must be freed using ``kfree_rcu()`` or | |
3ce96239 NB |
881 | similar. |
882 | ||
7bbfd9ad | 883 | .. _READ_ONCE: https://lwn.net/Articles/624126/ |
3ce96239 NB |
884 | |
885 | If the filesystem may need to revalidate dcache entries, then | |
7bbfd9ad N |
886 | ``d_op->d_revalidate`` may be called in RCU-walk too. This interface |
887 | *is* passed the dentry but does not have access to the ``inode`` or the | |
888 | ``seq`` number from the ``nameidata``, so it needs to be extra careful | |
3ce96239 | 889 | when accessing fields in the dentry. This "extra care" typically |
7bbfd9ad | 890 | involves using `READ_ONCE() <READ_ONCE_>`_ to access fields, and verifying the |
3587679d | 891 | result is not NULL before using it. This pattern can be seen in |
7bbfd9ad | 892 | ``nfs_lookup_revalidate()``. |
3ce96239 NB |
893 | |
894 | A pair of patterns | |
895 | ------------------ | |
896 | ||
897 | In various places in the details of REF-walk and RCU-walk, and also in | |
898 | the big picture, there are a couple of related patterns that are worth | |
899 | being aware of. | |
900 | ||
901 | The first is "try quickly and check, if that fails try slowly". We | |
902 | can see that in the high-level approach of first trying RCU-walk and | |
7bbfd9ad | 903 | then trying REF-walk, and in places where ``unlazy_walk()`` is used to |
3ce96239 | 904 | switch to REF-walk for the rest of the path. We also saw it earlier |
7bbfd9ad | 905 | in ``dget_parent()`` when following a "``..``" link. It tries a quick way |
3ce96239 NB |
906 | to get a reference, then falls back to taking locks if needed. |
907 | ||
908 | The second pattern is "try quickly and check, if that fails try | |
7bbfd9ad N |
909 | again - repeatedly". This is seen with the use of ``rename_lock`` and |
910 | ``mount_lock`` in REF-walk. RCU-walk doesn't make use of this pattern - | |
3ce96239 NB |
911 | if anything goes wrong it is much safer to just abort and try a more |
912 | sedate approach. | |
913 | ||
914 | The emphasis here is "try quickly and check". It should probably be | |
915 | "try quickly _and carefully,_ then check". The fact that checking is | |
916 | needed is a reminder that the system is dynamic and only a limited | |
917 | number of things are safe at all. The most likely cause of errors in | |
918 | this whole process is assuming something is safe when in reality it | |
919 | isn't. Careful consideration of what exactly guarantees the safety of | |
920 | each access is sometimes necessary. | |
921 | ||
922 | A walk among the symlinks | |
923 | ========================= | |
924 | ||
925 | There are several basic issues that we will examine to understand the | |
926 | handling of symbolic links: the symlink stack, together with cache | |
927 | lifetimes, will help us understand the overall recursive handling of | |
928 | symlinks and lead to the special care needed for the final component. | |
929 | Then a consideration of access-time updates and summary of the various | |
930 | flags controlling lookup will finish the story. | |
931 | ||
932 | The symlink stack | |
933 | ----------------- | |
934 | ||
935 | There are only two sorts of filesystem objects that can usefully | |
936 | appear in a path prior to the final component: directories and symlinks. | |
937 | Handling directories is quite straightforward: the new directory | |
938 | simply becomes the starting point at which to interpret the next | |
939 | component on the path. Handling symbolic links requires a bit more | |
940 | work. | |
941 | ||
942 | Conceptually, symbolic links could be handled by editing the path. If | |
943 | a component name refers to a symbolic link, then that component is | |
944 | replaced by the body of the link and, if that body starts with a '/', | |
945 | then all preceding parts of the path are discarded. This is what the | |
7bbfd9ad N |
946 | "``readlink -f``" command does, though it also edits out "``.``" and |
947 | "``..``" components. | |
3ce96239 NB |
948 | |
949 | Directly editing the path string is not really necessary when looking | |
950 | up a path, and discarding early components is pointless as they aren't | |
951 | looked at anyway. Keeping track of all remaining components is | |
952 | important, but they can of course be kept separately; there is no need | |
953 | to concatenate them. As one symlink may easily refer to another, | |
954 | which in turn can refer to a third, we may need to keep the remaining | |
955 | components of several paths, each to be processed when the preceding | |
956 | ones are completed. These path remnants are kept on a stack of | |
957 | limited size. | |
958 | ||
959 | There are two reasons for placing limits on how many symlinks can | |
960 | occur in a single path lookup. The most obvious is to avoid loops. | |
961 | If a symlink referred to itself either directly or through | |
962 | intermediaries, then following the symlink can never complete | |
7bbfd9ad | 963 | successfully - the error ``ELOOP`` must be returned. Loops can be |
3ce96239 NB |
964 | detected without imposing limits, but limits are the simplest solution |
965 | and, given the second reason for restriction, quite sufficient. | |
966 | ||
7bbfd9ad | 967 | .. _outlined recently: http://thread.gmane.org/gmane.linux.kernel/1934390/focus=1934550 |
3ce96239 | 968 | |
7bbfd9ad | 969 | The second reason was `outlined recently`_ by Linus: |
3ce96239 | 970 | |
7bbfd9ad N |
971 | Because it's a latency and DoS issue too. We need to react well to |
972 | true loops, but also to "very deep" non-loops. It's not about memory | |
973 | use, it's about users triggering unreasonable CPU resources. | |
3ce96239 | 974 | |
7bbfd9ad | 975 | Linux imposes a limit on the length of any pathname: ``PATH_MAX``, which |
3ce96239 NB |
976 | is 4096. There are a number of reasons for this limit; not letting the |
977 | kernel spend too much time on just one path is one of them. With | |
978 | symbolic links you can effectively generate much longer paths so some | |
979 | sort of limit is needed for the same reason. Linux imposes a limit of | |
980 | at most 40 symlinks in any one path lookup. It previously imposed a | |
981 | further limit of eight on the maximum depth of recursion, but that was | |
982 | raised to 40 when a separate stack was implemented, so there is now | |
983 | just the one limit. | |
984 | ||
7bbfd9ad | 985 | The ``nameidata`` structure that we met in an earlier article contains a |
3ce96239 NB |
986 | small stack that can be used to store the remaining part of up to two |
987 | symlinks. In many cases this will be sufficient. If it isn't, a | |
988 | separate stack is allocated with room for 40 symlinks. Pathname | |
989 | lookup will never exceed that stack as, once the 40th symlink is | |
990 | detected, an error is returned. | |
991 | ||
992 | It might seem that the name remnants are all that needs to be stored on | |
993 | this stack, but we need a bit more. To see that, we need to move on to | |
994 | cache lifetimes. | |
995 | ||
996 | Storage and lifetime of cached symlinks | |
997 | --------------------------------------- | |
998 | ||
999 | Like other filesystem resources, such as inodes and directory | |
1000 | entries, symlinks are cached by Linux to avoid repeated costly access | |
1001 | to external storage. It is particularly important for RCU-walk to be | |
1002 | able to find and temporarily hold onto these cached entries, so that | |
1003 | it doesn't need to drop down into REF-walk. | |
1004 | ||
7bbfd9ad | 1005 | .. _object-oriented design pattern: https://lwn.net/Articles/446317/ |
3ce96239 NB |
1006 | |
1007 | While each filesystem is free to make its own choice, symlinks are | |
1008 | typically stored in one of two places. Short symlinks are often | |
7bbfd9ad N |
1009 | stored directly in the inode. When a filesystem allocates a ``struct |
1010 | inode`` it typically allocates extra space to store private data (a | |
1011 | common `object-oriented design pattern`_ in the kernel). This will | |
3ce96239 NB |
1012 | sometimes include space for a symlink. The other common location is |
1013 | in the page cache, which normally stores the content of files. The | |
1014 | pathname in a symlink can be seen as the content of that symlink and | |
1015 | can easily be stored in the page cache just like file content. | |
1016 | ||
1017 | When neither of these is suitable, the next most likely scenario is | |
1018 | that the filesystem will allocate some temporary memory and copy or | |
1019 | construct the symlink content into that memory whenever it is needed. | |
1020 | ||
1021 | When the symlink is stored in the inode, it has the same lifetime as | |
1022 | the inode which, itself, is protected by RCU or by a counted reference | |
1023 | on the dentry. This means that the mechanisms that pathname lookup | |
1024 | uses to access the dcache and icache (inode cache) safely are quite | |
1025 | sufficient for accessing some cached symlinks safely. In these cases, | |
7bbfd9ad | 1026 | the ``i_link`` pointer in the inode is set to point to wherever the |
3ce96239 NB |
1027 | symlink is stored and it can be accessed directly whenever needed. |
1028 | ||
1029 | When the symlink is stored in the page cache or elsewhere, the | |
1030 | situation is not so straightforward. A reference on a dentry or even | |
1031 | on an inode does not imply any reference on cached pages of that | |
7bbfd9ad | 1032 | inode, and even an ``rcu_read_lock()`` is not sufficient to ensure that |
3ce96239 NB |
1033 | a page will not disappear. So for these symlinks the pathname lookup |
1034 | code needs to ask the filesystem to provide a stable reference and, | |
1035 | significantly, needs to release that reference when it is finished | |
1036 | with it. | |
1037 | ||
1038 | Taking a reference to a cache page is often possible even in RCU-walk | |
1039 | mode. It does require making changes to memory, which is best avoided, | |
1040 | but that isn't necessarily a big cost and it is better than dropping | |
1041 | out of RCU-walk mode completely. Even filesystems that allocate | |
7bbfd9ad | 1042 | space to copy the symlink into can use ``GFP_ATOMIC`` to often successfully |
3ce96239 NB |
1043 | allocate memory without the need to drop out of RCU-walk. If a |
1044 | filesystem cannot successfully get a reference in RCU-walk mode, it | |
7bbfd9ad | 1045 | must return ``-ECHILD`` and ``unlazy_walk()`` will be called to return to |
3ce96239 NB |
1046 | REF-walk mode in which the filesystem is allowed to sleep. |
1047 | ||
7bbfd9ad | 1048 | The place for all this to happen is the ``i_op->follow_link()`` inode |
3ce96239 NB |
1049 | method. In the present mainline code this is never actually called in |
1050 | RCU-walk mode as the rewrite is not quite complete. It is likely that | |
7bbfd9ad | 1051 | in a future release this method will be passed an ``inode`` pointer when |
3ce96239 | 1052 | called in RCU-walk mode so it both (1) knows to be careful, and (2) has the |
7bbfd9ad N |
1053 | validated pointer. Much like the ``i_op->permission()`` method we |
1054 | looked at previously, ``->follow_link()`` would need to be careful that | |
3ce96239 NB |
1055 | all the data structures it references are safe to be accessed while |
1056 | holding no counted reference, only the RCU lock. Though getting a | |
7bbfd9ad | 1057 | reference with ``->follow_link()`` is not yet done in RCU-walk mode, the |
3ce96239 NB |
1058 | code is ready to release the reference when that does happen. |
1059 | ||
1060 | This need to drop the reference to a symlink adds significant | |
1061 | complexity. It requires a reference to the inode so that the | |
7bbfd9ad | 1062 | ``i_op->put_link()`` inode operation can be called. In REF-walk, that |
3ce96239 | 1063 | reference is kept implicitly through a reference to the dentry, so |
7bbfd9ad | 1064 | keeping the ``struct path`` of the symlink is easiest. For RCU-walk, |
3ce96239 NB |
1065 | the pointer to the inode is kept separately. To allow switching from |
1066 | RCU-walk back to REF-walk in the middle of processing nested symlinks | |
1067 | we also need the seq number for the dentry so we can confirm that | |
1068 | switching back was safe. | |
1069 | ||
1070 | Finally, when providing a reference to a symlink, the filesystem also | |
7bbfd9ad | 1071 | provides an opaque "cookie" that must be passed to ``->put_link()`` so that it |
3ce96239 | 1072 | knows what to free. This might be the allocated memory area, or a |
7bbfd9ad | 1073 | pointer to the ``struct page`` in the page cache, or something else |
3ce96239 NB |
1074 | completely. Only the filesystem knows what it is. |
1075 | ||
1076 | In order for the reference to each symlink to be dropped when the walk completes, | |
1077 | whether in RCU-walk or REF-walk, the symlink stack needs to contain, | |
1078 | along with the path remnants: | |
1079 | ||
7bbfd9ad N |
1080 | - the ``struct path`` to provide a reference to the inode in REF-walk |
1081 | - the ``struct inode *`` to provide a reference to the inode in RCU-walk | |
1082 | - the ``seq`` to allow the path to be safely switched from RCU-walk to REF-walk | |
1083 | - the ``cookie`` that tells ``->put_path()`` what to put. | |
3ce96239 NB |
1084 | |
1085 | This means that each entry in the symlink stack needs to hold five | |
1086 | pointers and an integer instead of just one pointer (the path | |
1087 | remnant). On a 64-bit system, this is about 40 bytes per entry; | |
1088 | with 40 entries it adds up to 1600 bytes total, which is less than | |
1089 | half a page. So it might seem like a lot, but is by no means | |
1090 | excessive. | |
1091 | ||
7bbfd9ad | 1092 | Note that, in a given stack frame, the path remnant (``name``) is not |
3ce96239 NB |
1093 | part of the symlink that the other fields refer to. It is the remnant |
1094 | to be followed once that symlink has been fully parsed. | |
1095 | ||
1096 | Following the symlink | |
1097 | --------------------- | |
1098 | ||
7bbfd9ad | 1099 | The main loop in ``link_path_walk()`` iterates seamlessly over all |
3ce96239 | 1100 | components in the path and all of the non-final symlinks. As symlinks |
7bbfd9ad | 1101 | are processed, the ``name`` pointer is adjusted to point to a new |
3ce96239 | 1102 | symlink, or is restored from the stack, so that much of the loop |
7bbfd9ad | 1103 | doesn't need to notice. Getting this ``name`` variable on and off the |
3ce96239 NB |
1104 | stack is very straightforward; pushing and popping the references is |
1105 | a little more complex. | |
1106 | ||
7bbfd9ad N |
1107 | When a symlink is found, ``walk_component()`` returns the value ``1`` |
1108 | (``0`` is returned for any other sort of success, and a negative number | |
1109 | is, as usual, an error indicator). This causes ``get_link()`` to be | |
3ce96239 | 1110 | called; it then gets the link from the filesystem. Providing that |
7bbfd9ad N |
1111 | operation is successful, the old path ``name`` is placed on the stack, |
1112 | and the new value is used as the ``name`` for a while. When the end of | |
1113 | the path is found (i.e. ``*name`` is ``'\0'``) the old ``name`` is restored | |
3ce96239 NB |
1114 | off the stack and path walking continues. |
1115 | ||
1116 | Pushing and popping the reference pointers (inode, cookie, etc.) is more | |
1117 | complex in part because of the desire to handle tail recursion. When | |
1118 | the last component of a symlink itself points to a symlink, we | |
1119 | want to pop the symlink-just-completed off the stack before pushing | |
1120 | the symlink-just-found to avoid leaving empty path remnants that would | |
1121 | just get in the way. | |
1122 | ||
1123 | It is most convenient to push the new symlink references onto the | |
7bbfd9ad N |
1124 | stack in ``walk_component()`` immediately when the symlink is found; |
1125 | ``walk_component()`` is also the last piece of code that needs to look at the | |
3ce96239 | 1126 | old symlink as it walks that last component. So it is quite |
7bbfd9ad | 1127 | convenient for ``walk_component()`` to release the old symlink and pop |
3ce96239 | 1128 | the references just before pushing the reference information for the |
7bbfd9ad | 1129 | new symlink. It is guided in this by two flags; ``WALK_GET``, which |
3ce96239 | 1130 | gives it permission to follow a symlink if it finds one, and |
7bbfd9ad N |
1131 | ``WALK_PUT``, which tells it to release the current symlink after it has been |
1132 | followed. ``WALK_PUT`` is tested first, leading to a call to | |
1133 | ``put_link()``. ``WALK_GET`` is tested subsequently (by | |
1134 | ``should_follow_link()``) leading to a call to ``pick_link()`` which sets | |
3ce96239 NB |
1135 | up the stack frame. |
1136 | ||
7bbfd9ad N |
1137 | Symlinks with no final component |
1138 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
3ce96239 NB |
1139 | |
1140 | A pair of special-case symlinks deserve a little further explanation. | |
7bbfd9ad N |
1141 | Both result in a new ``struct path`` (with mount and dentry) being set |
1142 | up in the ``nameidata``, and result in ``get_link()`` returning ``NULL``. | |
3ce96239 | 1143 | |
7bbfd9ad N |
1144 | The more obvious case is a symlink to "``/``". All symlinks starting |
1145 | with "``/``" are detected in ``get_link()`` which resets the ``nameidata`` | |
3ce96239 | 1146 | to point to the effective filesystem root. If the symlink only |
7bbfd9ad N |
1147 | contains "``/``" then there is nothing more to do, no components at all, |
1148 | so ``NULL`` is returned to indicate that the symlink can be released and | |
3ce96239 NB |
1149 | the stack frame discarded. |
1150 | ||
7bbfd9ad N |
1151 | The other case involves things in ``/proc`` that look like symlinks but |
1152 | aren't really:: | |
3ce96239 | 1153 | |
7bbfd9ad N |
1154 | $ ls -l /proc/self/fd/1 |
1155 | lrwx------ 1 neilb neilb 64 Jun 13 10:19 /proc/self/fd/1 -> /dev/pts/4 | |
3ce96239 | 1156 | |
7bbfd9ad | 1157 | Every open file descriptor in any process is represented in ``/proc`` by |
3ce96239 | 1158 | something that looks like a symlink. It is really a reference to the |
7bbfd9ad | 1159 | target file, not just the name of it. When you ``readlink`` these |
3ce96239 | 1160 | objects you get a name that might refer to the same file - unless it |
7bbfd9ad N |
1161 | has been unlinked or mounted over. When ``walk_component()`` follows |
1162 | one of these, the ``->follow_link()`` method in "procfs" doesn't return | |
1163 | a string name, but instead calls ``nd_jump_link()`` which updates the | |
1164 | ``nameidata`` in place to point to that target. ``->follow_link()`` then | |
1165 | returns ``NULL``. Again there is no final component and ``get_link()`` | |
1166 | reports this by leaving the ``last_type`` field of ``nameidata`` as | |
1167 | ``LAST_BIND``. | |
3ce96239 NB |
1168 | |
1169 | Following the symlink in the final component | |
1170 | -------------------------------------------- | |
1171 | ||
7bbfd9ad | 1172 | All this leads to ``link_path_walk()`` walking down every component, and |
3ce96239 | 1173 | following all symbolic links it finds, until it reaches the final |
7bbfd9ad | 1174 | component. This is just returned in the ``last`` field of ``nameidata``. |
3ce96239 | 1175 | For some callers, this is all they need; they want to create that |
7bbfd9ad | 1176 | ``last`` name if it doesn't exist or give an error if it does. Other |
3ce96239 NB |
1177 | callers will want to follow a symlink if one is found, and possibly |
1178 | apply special handling to the last component of that symlink, rather | |
1179 | than just the last component of the original file name. These callers | |
7bbfd9ad | 1180 | potentially need to call ``link_path_walk()`` again and again on |
3ce96239 NB |
1181 | successive symlinks until one is found that doesn't point to another |
1182 | symlink. | |
1183 | ||
7bbfd9ad N |
1184 | This case is handled by the relevant caller of ``link_path_walk()``, such as |
1185 | ``path_lookupat()`` using a loop that calls ``link_path_walk()``, and then | |
3ce96239 | 1186 | handles the final component. If the final component is a symlink |
7bbfd9ad N |
1187 | that needs to be followed, then ``trailing_symlink()`` is called to set |
1188 | things up properly and the loop repeats, calling ``link_path_walk()`` | |
3ce96239 NB |
1189 | again. This could loop as many as 40 times if the last component of |
1190 | each symlink is another symlink. | |
1191 | ||
1192 | The various functions that examine the final component and possibly | |
7bbfd9ad N |
1193 | report that it is a symlink are ``lookup_last()``, ``mountpoint_last()`` |
1194 | and ``do_last()``, each of which use the same convention as | |
1195 | ``walk_component()`` of returning ``1`` if a symlink was found that needs | |
3ce96239 NB |
1196 | to be followed. |
1197 | ||
7bbfd9ad N |
1198 | Of these, ``do_last()`` is the most interesting as it is used for |
1199 | opening a file. Part of ``do_last()`` runs with ``i_rwsem`` held and this | |
1200 | part is in a separate function: ``lookup_open()``. | |
3ce96239 | 1201 | |
7bbfd9ad | 1202 | Explaining ``do_last()`` completely is beyond the scope of this article, |
3ce96239 NB |
1203 | but a few highlights should help those interested in exploring the |
1204 | code. | |
1205 | ||
7bbfd9ad N |
1206 | 1. Rather than just finding the target file, ``do_last()`` needs to open |
1207 | it. If the file was found in the dcache, then ``vfs_open()`` is used for | |
1208 | this. If not, then ``lookup_open()`` will either call ``atomic_open()`` (if | |
1209 | the filesystem provides it) to combine the final lookup with the open, or | |
1210 | will perform the separate ``lookup_real()`` and ``vfs_create()`` steps | |
1211 | directly. In the later case the actual "open" of this newly found or | |
1212 | created file will be performed by ``vfs_open()``, just as if the name | |
1213 | were found in the dcache. | |
1214 | ||
1215 | 2. ``vfs_open()`` can fail with ``-EOPENSTALE`` if the cached information | |
1216 | wasn't quite current enough. Rather than restarting the lookup from | |
1217 | the top with ``LOOKUP_REVAL`` set, ``lookup_open()`` is called instead, | |
1218 | giving the filesystem a chance to resolve small inconsistencies. | |
1219 | If that doesn't work, only then is the lookup restarted from the top. | |
3ce96239 NB |
1220 | |
1221 | 3. An open with O_CREAT **does** follow a symlink in the final component, | |
7bbfd9ad | 1222 | unlike other creation system calls (like ``mkdir``). So the sequence:: |
3ce96239 | 1223 | |
7bbfd9ad N |
1224 | ln -s bar /tmp/foo |
1225 | echo hello > /tmp/foo | |
3ce96239 | 1226 | |
7bbfd9ad N |
1227 | will create a file called ``/tmp/bar``. This is not permitted if |
1228 | ``O_EXCL`` is set but otherwise is handled for an O_CREAT open much | |
1229 | like for a non-creating open: ``should_follow_link()`` returns ``1``, and | |
1230 | so does ``do_last()`` so that ``trailing_symlink()`` gets called and the | |
1231 | open process continues on the symlink that was found. | |
3ce96239 NB |
1232 | |
1233 | Updating the access time | |
1234 | ------------------------ | |
1235 | ||
1236 | We previously said of RCU-walk that it would "take no locks, increment | |
1237 | no counts, leave no footprints." We have since seen that some | |
1238 | "footprints" can be needed when handling symlinks as a counted | |
1239 | reference (or even a memory allocation) may be needed. But these | |
1240 | footprints are best kept to a minimum. | |
1241 | ||
1242 | One other place where walking down a symlink can involve leaving | |
1243 | footprints in a way that doesn't affect directories is in updating access times. | |
1244 | In Unix (and Linux) every filesystem object has a "last accessed | |
7bbfd9ad | 1245 | time", or "``atime``". Passing through a directory to access a file |
3ce96239 | 1246 | within is not considered to be an access for the purposes of |
7bbfd9ad N |
1247 | ``atime``; only listing the contents of a directory can update its ``atime``. |
1248 | Symlinks are different it seems. Both reading a symlink (with ``readlink()``) | |
3ce96239 NB |
1249 | and looking up a symlink on the way to some other destination can |
1250 | update the atime on that symlink. | |
1251 | ||
7bbfd9ad | 1252 | .. _clearest statement: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_08 |
3ce96239 NB |
1253 | |
1254 | It is not clear why this is the case; POSIX has little to say on the | |
7bbfd9ad | 1255 | subject. The `clearest statement`_ is that, if a particular implementation |
3ce96239 NB |
1256 | updates a timestamp in a place not specified by POSIX, this must be |
1257 | documented "except that any changes caused by pathname resolution need | |
1258 | not be documented". This seems to imply that POSIX doesn't really | |
1259 | care about access-time updates during pathname lookup. | |
1260 | ||
7bbfd9ad | 1261 | .. _Linux 1.3.87: https://git.kernel.org/cgit/linux/kernel/git/history/history.git/diff/fs/ext2/symlink.c?id=f806c6db77b8eaa6e00dcfb6b567706feae8dbb8 |
3ce96239 | 1262 | |
7bbfd9ad | 1263 | An examination of history shows that prior to `Linux 1.3.87`_, the ext2 |
3ce96239 NB |
1264 | filesystem, at least, didn't update atime when following a link. |
1265 | Unfortunately we have no record of why that behavior was changed. | |
1266 | ||
1267 | In any case, access time must now be updated and that operation can be | |
1268 | quite complex. Trying to stay in RCU-walk while doing it is best | |
7bbfd9ad N |
1269 | avoided. Fortunately it is often permitted to skip the ``atime`` |
1270 | update. Because ``atime`` updates cause performance problems in various | |
1271 | areas, Linux supports the ``relatime`` mount option, which generally | |
1272 | limits the updates of ``atime`` to once per day on files that aren't | |
3ce96239 | 1273 | being changed (and symlinks never change once created). Even without |
7bbfd9ad | 1274 | ``relatime``, many filesystems record ``atime`` with a one-second |
3ce96239 NB |
1275 | granularity, so only one update per second is required. |
1276 | ||
7bbfd9ad | 1277 | It is easy to test if an ``atime`` update is needed while in RCU-walk |
3ce96239 | 1278 | mode and, if it isn't, the update can be skipped and RCU-walk mode |
7bbfd9ad | 1279 | continues. Only when an ``atime`` update is actually required does the |
3ce96239 | 1280 | path walk drop down to REF-walk. All of this is handled in the |
7bbfd9ad | 1281 | ``get_link()`` function. |
3ce96239 NB |
1282 | |
1283 | A few flags | |
1284 | ----------- | |
1285 | ||
1286 | A suitable way to wrap up this tour of pathname walking is to list | |
7bbfd9ad | 1287 | the various flags that can be stored in the ``nameidata`` to guide the |
3ce96239 NB |
1288 | lookup process. Many of these are only meaningful on the final |
1289 | component, others reflect the current state of the pathname lookup. | |
7bbfd9ad | 1290 | And then there is ``LOOKUP_EMPTY``, which doesn't fit conceptually with |
3ce96239 NB |
1291 | the others. If this is not set, an empty pathname causes an error |
1292 | very early on. If it is set, empty pathnames are not considered to be | |
1293 | an error. | |
1294 | ||
7bbfd9ad N |
1295 | Global state flags |
1296 | ~~~~~~~~~~~~~~~~~~ | |
3ce96239 | 1297 | |
7bbfd9ad N |
1298 | We have already met two global state flags: ``LOOKUP_RCU`` and |
1299 | ``LOOKUP_REVAL``. These select between one of three overall approaches | |
3ce96239 NB |
1300 | to lookup: RCU-walk, REF-walk, and REF-walk with forced revalidation. |
1301 | ||
7bbfd9ad | 1302 | ``LOOKUP_PARENT`` indicates that the final component hasn't been reached |
3ce96239 NB |
1303 | yet. This is primarily used to tell the audit subsystem the full |
1304 | context of a particular access being audited. | |
1305 | ||
7bbfd9ad | 1306 | ``LOOKUP_ROOT`` indicates that the ``root`` field in the ``nameidata`` was |
3ce96239 NB |
1307 | provided by the caller, so it shouldn't be released when it is no |
1308 | longer needed. | |
1309 | ||
7bbfd9ad | 1310 | ``LOOKUP_JUMPED`` means that the current dentry was chosen not because |
3ce96239 | 1311 | it had the right name but for some other reason. This happens when |
7bbfd9ad N |
1312 | following "``..``", following a symlink to ``/``, crossing a mount point |
1313 | or accessing a "``/proc/$PID/fd/$FD``" symlink. In this case the | |
3ce96239 | 1314 | filesystem has not been asked to revalidate the name (with |
7bbfd9ad N |
1315 | ``d_revalidate()``). In such cases the inode may still need to be |
1316 | revalidated, so ``d_op->d_weak_revalidate()`` is called if | |
1317 | ``LOOKUP_JUMPED`` is set when the look completes - which may be at the | |
3ce96239 NB |
1318 | final component or, when creating, unlinking, or renaming, at the penultimate component. |
1319 | ||
7bbfd9ad N |
1320 | Final-component flags |
1321 | ~~~~~~~~~~~~~~~~~~~~~ | |
3ce96239 NB |
1322 | |
1323 | Some of these flags are only set when the final component is being | |
1324 | considered. Others are only checked for when considering that final | |
1325 | component. | |
1326 | ||
7bbfd9ad | 1327 | ``LOOKUP_AUTOMOUNT`` ensures that, if the final component is an automount |
3ce96239 | 1328 | point, then the mount is triggered. Some operations would trigger it |
7bbfd9ad N |
1329 | anyway, but operations like ``stat()`` deliberately don't. ``statfs()`` |
1330 | needs to trigger the mount but otherwise behaves a lot like ``stat()``, so | |
1331 | it sets ``LOOKUP_AUTOMOUNT``, as does "``quotactl()``" and the handling of | |
1332 | "``mount --bind``". | |
3ce96239 | 1333 | |
7bbfd9ad | 1334 | ``LOOKUP_FOLLOW`` has a similar function to ``LOOKUP_AUTOMOUNT`` but for |
3ce96239 | 1335 | symlinks. Some system calls set or clear it implicitly, while |
7bbfd9ad N |
1336 | others have API flags such as ``AT_SYMLINK_FOLLOW`` and |
1337 | ``UMOUNT_NOFOLLOW`` to control it. Its effect is similar to | |
1338 | ``WALK_GET`` that we already met, but it is used in a different way. | |
3ce96239 | 1339 | |
7bbfd9ad | 1340 | ``LOOKUP_DIRECTORY`` insists that the final component is a directory. |
3ce96239 NB |
1341 | Various callers set this and it is also set when the final component |
1342 | is found to be followed by a slash. | |
1343 | ||
7bbfd9ad N |
1344 | Finally ``LOOKUP_OPEN``, ``LOOKUP_CREATE``, ``LOOKUP_EXCL``, and |
1345 | ``LOOKUP_RENAME_TARGET`` are not used directly by the VFS but are made | |
1346 | available to the filesystem and particularly the ``->d_revalidate()`` | |
3ce96239 NB |
1347 | method. A filesystem can choose not to bother revalidating too hard |
1348 | if it knows that it will be asked to open or create the file soon. | |
7bbfd9ad N |
1349 | These flags were previously useful for ``->lookup()`` too but with the |
1350 | introduction of ``->atomic_open()`` they are less relevant there. | |
3ce96239 NB |
1351 | |
1352 | End of the road | |
1353 | --------------- | |
1354 | ||
1355 | Despite its complexity, all this pathname lookup code appears to be | |
1356 | in good shape - various parts are certainly easier to understand now | |
1357 | than even a couple of releases ago. But that doesn't mean it is | |
1358 | "finished". As already mentioned, RCU-walk currently only follows | |
1359 | symlinks that are stored in the inode so, while it handles many ext4 | |
1360 | symlinks, it doesn't help with NFS, XFS, or Btrfs. That support | |
1361 | is not likely to be long delayed. |