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