]>
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 | |
46 | from some other location specified by a file descriptor given to a | |
7bbfd9ad | 47 | "``XXXat``" system call 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 | |
7bbfd9ad N |
54 | generally forbidden in POSIX, but some of those "xxx``at``" system calls |
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 | ||
7bbfd9ad | 72 | .. _POSIX: http://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 |
7bbfd9ad | 79 | ending in "``/``". According to POSIX_ |
3ce96239 | 80 | |
7bbfd9ad N |
81 | A pathname that contains at least one non- <slash> character and |
82 | that ends with one or more trailing <slash> characters shall not | |
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 | ||
7bbfd9ad | 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 | |
7bbfd9ad | 379 | .. _First edition Unix: http://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 | |
7bbfd9ad | 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 | |
3ce96239 | 451 | to find a definitive answer. Each of these will call |
7bbfd9ad | 452 | ``follow_managed()`` (as described below) to handle any mount points. |
3ce96239 | 453 | |
7bbfd9ad N |
454 | In the absence of symbolic links, ``walk_component()`` creates a new |
455 | ``struct path`` containing a counted reference to the new dentry and a | |
456 | reference to the new ``vfsmount`` which is only counted if it is | |
457 | different from the previous ``vfsmount``. It then calls | |
458 | ``path_to_nameidata()`` to install the new ``struct path`` in the | |
459 | ``struct nameidata`` and drop the unneeded references. | |
3ce96239 NB |
460 | |
461 | This "hand-over-hand" sequencing of getting a reference to the new | |
462 | dentry before dropping the reference to the previous dentry may | |
463 | seem obvious, but is worth pointing out so that we will recognize its | |
464 | analogue in the "RCU-walk" version. | |
465 | ||
7bbfd9ad N |
466 | Handling the final component |
467 | ---------------------------- | |
3ce96239 | 468 | |
7bbfd9ad N |
469 | ``link_path_walk()`` only walks as far as setting ``nd->last`` and |
470 | ``nd->last_type`` to refer to the final component of the path. It does | |
471 | not call ``walk_component()`` that last time. Handling that final | |
3ce96239 | 472 | component remains for the caller to sort out. Those callers are |
7bbfd9ad N |
473 | ``path_lookupat()``, ``path_parentat()``, ``path_mountpoint()`` and |
474 | ``path_openat()`` each of which handles the differing requirements of | |
3ce96239 NB |
475 | different system calls. |
476 | ||
7bbfd9ad N |
477 | ``path_parentat()`` is clearly the simplest - it just wraps a little bit |
478 | of housekeeping around ``link_path_walk()`` and returns the parent | |
3ce96239 | 479 | directory and final component to the caller. The caller will be either |
7bbfd9ad N |
480 | aiming to create a name (via ``filename_create()``) or remove or rename |
481 | a name (in which case ``user_path_parent()`` is used). They will use | |
482 | ``i_rwsem`` to exclude other changes while they validate and then | |
3ce96239 NB |
483 | perform their operation. |
484 | ||
7bbfd9ad N |
485 | ``path_lookupat()`` is nearly as simple - it is used when an existing |
486 | object is wanted such as by ``stat()`` or ``chmod()``. It essentially just | |
487 | calls ``walk_component()`` on the final component through a call to | |
488 | ``lookup_last()``. ``path_lookupat()`` returns just the final dentry. | |
3ce96239 | 489 | |
7bbfd9ad | 490 | ``path_mountpoint()`` handles the special case of unmounting which must |
3ce96239 | 491 | not try to revalidate the mounted filesystem. It effectively |
7bbfd9ad N |
492 | contains, through a call to ``mountpoint_last()``, an alternate |
493 | implementation of ``lookup_slow()`` which skips that step. This is | |
3ce96239 NB |
494 | important when unmounting a filesystem that is inaccessible, such as |
495 | one provided by a dead NFS server. | |
496 | ||
7bbfd9ad N |
497 | Finally ``path_openat()`` is used for the ``open()`` system call; it |
498 | contains, in support functions starting with "``do_last()``", 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 |
7bbfd9ad N |
502 | focuses on those symbolic links. "``do_last()``" will sometimes, but |
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 | ||
538 | The Linux VFS has a concept of "managed" dentries which is reflected | |
7bbfd9ad | 539 | in function names such as "``follow_managed()``". There are three |
3ce96239 | 540 | potentially interesting things about these dentries corresponding |
7bbfd9ad | 541 | to three different flags that might be set in ``dentry->d_flags``: |
3ce96239 | 542 | |
7bbfd9ad | 543 | ``DCACHE_MANAGE_TRANSIT`` |
9f63df26 | 544 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 NB |
545 | |
546 | If this flag has been set, then the filesystem has requested that the | |
7bbfd9ad | 547 | ``d_manage()`` dentry operation be called before handling any possible |
3ce96239 NB |
548 | mount point. This can perform two particular services: |
549 | ||
550 | It can block to avoid races. If an automount point is being | |
7bbfd9ad | 551 | unmounted, the ``d_manage()`` function will usually wait for that |
3ce96239 NB |
552 | process to complete before letting the new lookup proceed and possibly |
553 | trigger a new automount. | |
554 | ||
555 | It can selectively allow only some processes to transit through a | |
556 | mount point. When a server process is managing automounts, it may | |
557 | need to access a directory without triggering normal automount | |
7bbfd9ad | 558 | processing. That server process can identify itself to the ``autofs`` |
3ce96239 | 559 | filesystem, which will then give it a special pass through |
7bbfd9ad | 560 | ``d_manage()`` by returning ``-EISDIR``. |
3ce96239 | 561 | |
7bbfd9ad | 562 | ``DCACHE_MOUNTED`` |
9f63df26 | 563 | ~~~~~~~~~~~~~~~~~~ |
3ce96239 NB |
564 | |
565 | This flag is set on every dentry that is mounted on. As Linux | |
566 | supports multiple filesystem namespaces, it is possible that the | |
567 | dentry may not be mounted on in *this* namespace, just in some | |
568 | other. So this flag is seen as a hint, not a promise. | |
569 | ||
7bbfd9ad N |
570 | If this flag is set, and ``d_manage()`` didn't return ``-EISDIR``, |
571 | ``lookup_mnt()`` is called to examine the mount hash table (honoring the | |
572 | ``mount_lock`` described earlier) and possibly return a new ``vfsmount`` | |
573 | and a new ``dentry`` (both with counted references). | |
3ce96239 | 574 | |
7bbfd9ad | 575 | ``DCACHE_NEED_AUTOMOUNT`` |
9f63df26 | 576 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 577 | |
7bbfd9ad N |
578 | If ``d_manage()`` allowed us to get this far, and ``lookup_mnt()`` didn't |
579 | find a mount point, then this flag causes the ``d_automount()`` dentry | |
3ce96239 NB |
580 | operation to be called. |
581 | ||
7bbfd9ad | 582 | The ``d_automount()`` operation can be arbitrarily complex and may |
3ce96239 NB |
583 | communicate with server processes etc. but it should ultimately either |
584 | report that there was an error, that there was nothing to mount, or | |
7bbfd9ad | 585 | should provide an updated ``struct path`` with new ``dentry`` and ``vfsmount``. |
3ce96239 | 586 | |
7bbfd9ad | 587 | In the latter case, ``finish_automount()`` will be called to safely |
3ce96239 NB |
588 | install the new mount point into the mount table. |
589 | ||
590 | There is no new locking of import here and it is important that no | |
591 | locks (only counted references) are held over this processing due to | |
592 | the very real possibility of extended delays. | |
593 | This will become more important next time when we examine RCU-walk | |
594 | which is particularly sensitive to delays. | |
595 | ||
596 | RCU-walk - faster pathname lookup in Linux | |
597 | ========================================== | |
598 | ||
599 | RCU-walk is another algorithm for performing pathname lookup in Linux. | |
600 | It is in many ways similar to REF-walk and the two share quite a bit | |
601 | of code. The significant difference in RCU-walk is how it allows for | |
602 | the possibility of concurrent access. | |
603 | ||
604 | We noted that REF-walk is complex because there are numerous details | |
605 | and special cases. RCU-walk reduces this complexity by simply | |
606 | refusing to handle a number of cases -- it instead falls back to | |
607 | REF-walk. The difficulty with RCU-walk comes from a different | |
608 | direction: unfamiliarity. The locking rules when depending on RCU are | |
609 | quite different from traditional locking, so we will spend a little extra | |
610 | time when we come to those. | |
611 | ||
612 | Clear demarcation of roles | |
613 | -------------------------- | |
614 | ||
615 | The easiest way to manage concurrency is to forcibly stop any other | |
616 | thread from changing the data structures that a given thread is | |
617 | looking at. In cases where no other thread would even think of | |
618 | changing the data and lots of different threads want to read at the | |
619 | same time, this can be very costly. Even when using locks that permit | |
620 | multiple concurrent readers, the simple act of updating the count of | |
621 | the number of current readers can impose an unwanted cost. So the | |
622 | goal when reading a shared data structure that no other process is | |
623 | changing is to avoid writing anything to memory at all. Take no | |
624 | locks, increment no counts, leave no footprints. | |
625 | ||
626 | The REF-walk mechanism already described certainly doesn't follow this | |
627 | principle, but then it is really designed to work when there may well | |
628 | be other threads modifying the data. RCU-walk, in contrast, is | |
629 | designed for the common situation where there are lots of frequent | |
630 | readers and only occasional writers. This may not be common in all | |
631 | parts of the filesystem tree, but in many parts it will be. For the | |
632 | other parts it is important that RCU-walk can quickly fall back to | |
633 | using REF-walk. | |
634 | ||
635 | Pathname lookup always starts in RCU-walk mode but only remains there | |
636 | as long as what it is looking for is in the cache and is stable. It | |
637 | dances lightly down the cached filesystem image, leaving no footprints | |
638 | and carefully watching where it is, to be sure it doesn't trip. If it | |
639 | notices that something has changed or is changing, or if something | |
640 | isn't in the cache, then it tries to stop gracefully and switch to | |
641 | REF-walk. | |
642 | ||
643 | This stopping requires getting a counted reference on the current | |
7bbfd9ad | 644 | ``vfsmount`` and ``dentry``, and ensuring that these are still valid - |
3ce96239 NB |
645 | that a path walk with REF-walk would have found the same entries. |
646 | This is an invariant that RCU-walk must guarantee. It can only make | |
647 | decisions, such as selecting the next step, that are decisions which | |
648 | REF-walk could also have made if it were walking down the tree at the | |
649 | same time. If the graceful stop succeeds, the rest of the path is | |
650 | processed with the reliable, if slightly sluggish, REF-walk. If | |
651 | RCU-walk finds it cannot stop gracefully, it simply gives up and | |
652 | restarts from the top with REF-walk. | |
653 | ||
654 | This pattern of "try RCU-walk, if that fails try REF-walk" can be | |
7bbfd9ad N |
655 | clearly seen in functions like ``filename_lookup()``, |
656 | ``filename_parentat()``, ``filename_mountpoint()``, | |
657 | ``do_filp_open()``, and ``do_file_open_root()``. These five | |
658 | correspond roughly to the four ``path_``* functions we met earlier, | |
659 | each of which calls ``link_path_walk()``. The ``path_*`` functions are | |
3ce96239 | 660 | called using different mode flags until a mode is found which works. |
7bbfd9ad N |
661 | They are first called with ``LOOKUP_RCU`` set to request "RCU-walk". If |
662 | that fails with the error ``ECHILD`` they are called again with no | |
3ce96239 | 663 | special flag to request "REF-walk". If either of those report the |
7bbfd9ad N |
664 | error ``ESTALE`` a final attempt is made with ``LOOKUP_REVAL`` set (and no |
665 | ``LOOKUP_RCU``) to ensure that entries found in the cache are forcibly | |
3ce96239 NB |
666 | revalidated - normally entries are only revalidated if the filesystem |
667 | determines that they are too old to trust. | |
668 | ||
7bbfd9ad | 669 | The ``LOOKUP_RCU`` attempt may drop that flag internally and switch to |
3ce96239 NB |
670 | REF-walk, but will never then try to switch back to RCU-walk. Places |
671 | that trip up RCU-walk are much more likely to be near the leaves and | |
672 | so it is very unlikely that there will be much, if any, benefit from | |
673 | switching back. | |
674 | ||
675 | RCU and seqlocks: fast and light | |
676 | -------------------------------- | |
677 | ||
678 | RCU is, unsurprisingly, critical to RCU-walk mode. The | |
7bbfd9ad | 679 | ``rcu_read_lock()`` is held for the entire time that RCU-walk is walking |
3ce96239 NB |
680 | down a path. The particular guarantee it provides is that the key |
681 | data structures - dentries, inodes, super_blocks, and mounts - will | |
682 | not be freed while the lock is held. They might be unlinked or | |
683 | invalidated in one way or another, but the memory will not be | |
684 | repurposed so values in various fields will still be meaningful. This | |
685 | is the only guarantee that RCU provides; everything else is done using | |
686 | seqlocks. | |
687 | ||
688 | As we saw above, REF-walk holds a counted reference to the current | |
689 | dentry and the current vfsmount, and does not release those references | |
690 | before taking references to the "next" dentry or vfsmount. It also | |
7bbfd9ad | 691 | sometimes takes the ``d_lock`` spinlock. These references and locks are |
3ce96239 NB |
692 | taken to prevent certain changes from happening. RCU-walk must not |
693 | take those references or locks and so cannot prevent such changes. | |
694 | Instead, it checks to see if a change has been made, and aborts or | |
695 | retries if it has. | |
696 | ||
697 | To preserve the invariant mentioned above (that RCU-walk may only make | |
698 | decisions that REF-walk could have made), it must make the checks at | |
699 | or near the same places that REF-walk holds the references. So, when | |
700 | REF-walk increments a reference count or takes a spinlock, RCU-walk | |
7bbfd9ad | 701 | samples the status of a seqlock using ``read_seqcount_begin()`` or a |
3ce96239 NB |
702 | similar function. When REF-walk decrements the count or drops the |
703 | lock, RCU-walk checks if the sampled status is still valid using | |
7bbfd9ad | 704 | ``read_seqcount_retry()`` or similar. |
3ce96239 NB |
705 | |
706 | However, there is a little bit more to seqlocks than that. If | |
707 | RCU-walk accesses two different fields in a seqlock-protected | |
708 | structure, or accesses the same field twice, there is no a priori | |
709 | guarantee of any consistency between those accesses. When consistency | |
710 | is needed - which it usually is - RCU-walk must take a copy and then | |
7bbfd9ad | 711 | use ``read_seqcount_retry()`` to validate that copy. |
3ce96239 | 712 | |
7bbfd9ad | 713 | ``read_seqcount_retry()`` not only checks the sequence number, but also |
3ce96239 NB |
714 | imposes a memory barrier so that no memory-read instruction from |
715 | *before* the call can be delayed until *after* the call, either by the | |
716 | CPU or by the compiler. A simple example of this can be seen in | |
7bbfd9ad | 717 | ``slow_dentry_cmp()`` which, for filesystems which do not use simple |
3ce96239 NB |
718 | byte-wise name equality, calls into the filesystem to compare a name |
719 | against a dentry. The length and name pointer are copied into local | |
7bbfd9ad N |
720 | variables, then ``read_seqcount_retry()`` is called to confirm the two |
721 | are consistent, and only then is ``->d_compare()`` called. When | |
722 | standard filename comparison is used, ``dentry_cmp()`` is called | |
723 | instead. Notably it does _not_ use ``read_seqcount_retry()``, but | |
3ce96239 | 724 | instead has a large comment explaining why the consistency guarantee |
7bbfd9ad | 725 | isn't necessary. A subsequent ``read_seqcount_retry()`` will be |
3ce96239 NB |
726 | sufficient to catch any problem that could occur at this point. |
727 | ||
728 | With that little refresher on seqlocks out of the way we can look at | |
729 | the bigger picture of how RCU-walk uses seqlocks. | |
730 | ||
7bbfd9ad | 731 | ``mount_lock`` and ``nd->m_seq`` |
9f63df26 | 732 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 733 | |
7bbfd9ad | 734 | We already met the ``mount_lock`` seqlock when REF-walk used it to |
3ce96239 NB |
735 | ensure that crossing a mount point is performed safely. RCU-walk uses |
736 | it for that too, but for quite a bit more. | |
737 | ||
7bbfd9ad N |
738 | Instead of taking a counted reference to each ``vfsmount`` as it |
739 | descends the tree, RCU-walk samples the state of ``mount_lock`` at the | |
3ce96239 | 740 | start of the walk and stores this initial sequence number in the |
7bbfd9ad N |
741 | ``struct nameidata`` in the ``m_seq`` field. This one lock and one |
742 | sequence number are used to validate all accesses to all ``vfsmounts``, | |
3ce96239 NB |
743 | and all mount point crossings. As changes to the mount table are |
744 | relatively rare, it is reasonable to fall back on REF-walk any time | |
745 | that any "mount" or "unmount" happens. | |
746 | ||
7bbfd9ad | 747 | ``m_seq`` is checked (using ``read_seqretry()``) at the end of an RCU-walk |
3ce96239 NB |
748 | sequence, whether switching to REF-walk for the rest of the path or |
749 | when the end of the path is reached. It is also checked when stepping | |
7bbfd9ad N |
750 | down over a mount point (in ``__follow_mount_rcu()``) or up (in |
751 | ``follow_dotdot_rcu()``). If it is ever found to have changed, the | |
3ce96239 NB |
752 | whole RCU-walk sequence is aborted and the path is processed again by |
753 | REF-walk. | |
754 | ||
7bbfd9ad | 755 | If RCU-walk finds that ``mount_lock`` hasn't changed then it can be sure |
3ce96239 NB |
756 | that, had REF-walk taken counted references on each vfsmount, the |
757 | results would have been the same. This ensures the invariant holds, | |
758 | at least for vfsmount structures. | |
759 | ||
7bbfd9ad | 760 | ``dentry->d_seq`` and ``nd->seq`` |
9f63df26 | 761 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 762 | |
7bbfd9ad N |
763 | In place of taking a count or lock on ``d_reflock``, RCU-walk samples |
764 | the per-dentry ``d_seq`` seqlock, and stores the sequence number in the | |
765 | ``seq`` field of the nameidata structure, so ``nd->seq`` should always be | |
766 | the current sequence number of ``nd->dentry``. This number needs to be | |
3ce96239 NB |
767 | revalidated after copying, and before using, the name, parent, or |
768 | inode of the dentry. | |
769 | ||
770 | The handling of the name we have already looked at, and the parent is | |
7bbfd9ad | 771 | only accessed in ``follow_dotdot_rcu()`` which fairly trivially follows |
3ce96239 NB |
772 | the required pattern, though it does so for three different cases. |
773 | ||
7bbfd9ad | 774 | When not at a mount point, ``d_parent`` is followed and its ``d_seq`` is |
3ce96239 | 775 | collected. When we are at a mount point, we instead follow the |
7bbfd9ad N |
776 | ``mnt->mnt_mountpoint`` link to get a new dentry and collect its |
777 | ``d_seq``. Then, after finally finding a ``d_parent`` to follow, we must | |
3ce96239 | 778 | check if we have landed on a mount point and, if so, must find that |
7bbfd9ad | 779 | mount point and follow the ``mnt->mnt_root`` link. This would imply a |
3ce96239 NB |
780 | somewhat unusual, but certainly possible, circumstance where the |
781 | starting point of the path lookup was in part of the filesystem that | |
782 | was mounted on, and so not visible from the root. | |
783 | ||
7bbfd9ad | 784 | The inode pointer, stored in ``->d_inode``, is a little more |
3ce96239 NB |
785 | interesting. The inode will always need to be accessed at least |
786 | twice, once to determine if it is NULL and once to verify access | |
787 | permissions. Symlink handling requires a validated inode pointer too. | |
788 | Rather than revalidating on each access, a copy is made on the first | |
7bbfd9ad | 789 | access and it is stored in the ``inode`` field of ``nameidata`` from where |
3ce96239 NB |
790 | it can be safely accessed without further validation. |
791 | ||
7bbfd9ad N |
792 | ``lookup_fast()`` is the only lookup routine that is used in RCU-mode, |
793 | ``lookup_slow()`` being too slow and requiring locks. It is in | |
794 | ``lookup_fast()`` that we find the important "hand over hand" tracking | |
3ce96239 NB |
795 | of the current dentry. |
796 | ||
7bbfd9ad N |
797 | The current ``dentry`` and current ``seq`` number are passed to |
798 | ``__d_lookup_rcu()`` which, on success, returns a new ``dentry`` and a | |
799 | new ``seq`` number. ``lookup_fast()`` then copies the inode pointer and | |
800 | revalidates the new ``seq`` number. It then validates the old ``dentry`` | |
801 | with the old ``seq`` number one last time and only then continues. This | |
802 | process of getting the ``seq`` number of the new dentry and then | |
803 | checking the ``seq`` number of the old exactly mirrors the process of | |
3ce96239 NB |
804 | getting a counted reference to the new dentry before dropping that for |
805 | the old dentry which we saw in REF-walk. | |
806 | ||
7bbfd9ad | 807 | No ``inode->i_rwsem`` or even ``rename_lock`` |
9f63df26 | 808 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
3ce96239 | 809 | |
1428cc0e | 810 | A semaphore is a fairly heavyweight lock that can only be taken when it is |
7bbfd9ad N |
811 | permissible to sleep. As ``rcu_read_lock()`` forbids sleeping, |
812 | ``inode->i_rwsem`` plays no role in RCU-walk. If some other thread does | |
813 | take ``i_rwsem`` and modifies the directory in a way that RCU-walk needs | |
3ce96239 NB |
814 | to notice, the result will be either that RCU-walk fails to find the |
815 | dentry that it is looking for, or it will find a dentry which | |
7bbfd9ad | 816 | ``read_seqretry()`` won't validate. In either case it will drop down to |
3ce96239 NB |
817 | REF-walk mode which can take whatever locks are needed. |
818 | ||
7bbfd9ad N |
819 | Though ``rename_lock`` could be used by RCU-walk as it doesn't require |
820 | any sleeping, RCU-walk doesn't bother. REF-walk uses ``rename_lock`` to | |
3ce96239 NB |
821 | protect against the possibility of hash chains in the dcache changing |
822 | while they are being searched. This can result in failing to find | |
823 | something that actually is there. When RCU-walk fails to find | |
824 | something in the dentry cache, whether it is really there or not, it | |
825 | already drops down to REF-walk and tries again with appropriate | |
826 | locking. This neatly handles all cases, so adding extra checks on | |
827 | rename_lock would bring no significant value. | |
828 | ||
7bbfd9ad | 829 | ``unlazy walk()`` and ``complete_walk()`` |
9f63df26 | 830 | ----------------------------------------- |
3ce96239 NB |
831 | |
832 | That "dropping down to REF-walk" typically involves a call to | |
7bbfd9ad N |
833 | ``unlazy_walk()``, so named because "RCU-walk" is also sometimes |
834 | referred to as "lazy walk". ``unlazy_walk()`` is called when | |
3ce96239 NB |
835 | following the path down to the current vfsmount/dentry pair seems to |
836 | have proceeded successfully, but the next step is problematic. This | |
837 | can happen if the next name cannot be found in the dcache, if | |
838 | permission checking or name revalidation couldn't be achieved while | |
7bbfd9ad | 839 | the ``rcu_read_lock()`` is held (which forbids sleeping), if an |
3ce96239 | 840 | automount point is found, or in a couple of cases involving symlinks. |
7bbfd9ad | 841 | It is also called from ``complete_walk()`` when the lookup has reached |
3ce96239 NB |
842 | the final component, or the very end of the path, depending on which |
843 | particular flavor of lookup is used. | |
844 | ||
845 | Other reasons for dropping out of RCU-walk that do not trigger a call | |
7bbfd9ad N |
846 | to ``unlazy_walk()`` are when some inconsistency is found that cannot be |
847 | handled immediately, such as ``mount_lock`` or one of the ``d_seq`` | |
3ce96239 | 848 | seqlocks reporting a change. In these cases the relevant function |
7bbfd9ad | 849 | will return ``-ECHILD`` which will percolate up until it triggers a new |
3ce96239 NB |
850 | attempt from the top using REF-walk. |
851 | ||
7bbfd9ad | 852 | For those cases where ``unlazy_walk()`` is an option, it essentially |
3ce96239 NB |
853 | takes a reference on each of the pointers that it holds (vfsmount, |
854 | dentry, and possibly some symbolic links) and then verifies that the | |
855 | relevant seqlocks have not been changed. If there have been changes, | |
7bbfd9ad | 856 | it, too, aborts with ``-ECHILD``, otherwise the transition to REF-walk |
3ce96239 NB |
857 | has been a success and the lookup process continues. |
858 | ||
859 | Taking a reference on those pointers is not quite as simple as just | |
860 | incrementing a counter. That works to take a second reference if you | |
861 | already have one (often indirectly through another object), but it | |
862 | isn't sufficient if you don't actually have a counted reference at | |
7bbfd9ad | 863 | all. For ``dentry->d_lockref``, it is safe to increment the reference |
3ce96239 | 864 | counter to get a reference unless it has been explicitly marked as |
7bbfd9ad N |
865 | "dead" which involves setting the counter to ``-128``. |
866 | ``lockref_get_not_dead()`` achieves this. | |
3ce96239 | 867 | |
7bbfd9ad N |
868 | For ``mnt->mnt_count`` it is safe to take a reference as long as |
869 | ``mount_lock`` is then used to validate the reference. If that | |
3ce96239 | 870 | validation fails, it may *not* be safe to just drop that reference in |
7bbfd9ad N |
871 | the standard way of calling ``mnt_put()`` - an unmount may have |
872 | progressed too far. So the code in ``legitimize_mnt()``, when it | |
3ce96239 | 873 | finds that the reference it got might not be safe, checks the |
7bbfd9ad | 874 | ``MNT_SYNC_UMOUNT`` flag to determine if a simple ``mnt_put()`` is |
3ce96239 NB |
875 | correct, or if it should just decrement the count and pretend none of |
876 | this ever happened. | |
877 | ||
878 | Taking care in filesystems | |
7bbfd9ad | 879 | -------------------------- |
3ce96239 NB |
880 | |
881 | RCU-walk depends almost entirely on cached information and often will | |
882 | not call into the filesystem at all. However there are two places, | |
883 | besides the already-mentioned component-name comparison, where the | |
884 | file system might be included in RCU-walk, and it must know to be | |
885 | careful. | |
886 | ||
887 | If the filesystem has non-standard permission-checking requirements - | |
888 | such as a networked filesystem which may need to check with the server | |
7bbfd9ad N |
889 | - the ``i_op->permission`` interface might be called during RCU-walk. |
890 | In this case an extra "``MAY_NOT_BLOCK``" flag is passed so that it | |
891 | knows not to sleep, but to return ``-ECHILD`` if it cannot complete | |
892 | promptly. ``i_op->permission`` is given the inode pointer, not the | |
3ce96239 NB |
893 | dentry, so it doesn't need to worry about further consistency checks. |
894 | However if it accesses any other filesystem data structures, it must | |
7bbfd9ad N |
895 | ensure they are safe to be accessed with only the ``rcu_read_lock()`` |
896 | held. This typically means they must be freed using ``kfree_rcu()`` or | |
3ce96239 NB |
897 | similar. |
898 | ||
7bbfd9ad | 899 | .. _READ_ONCE: https://lwn.net/Articles/624126/ |
3ce96239 NB |
900 | |
901 | If the filesystem may need to revalidate dcache entries, then | |
7bbfd9ad N |
902 | ``d_op->d_revalidate`` may be called in RCU-walk too. This interface |
903 | *is* passed the dentry but does not have access to the ``inode`` or the | |
904 | ``seq`` number from the ``nameidata``, so it needs to be extra careful | |
3ce96239 | 905 | when accessing fields in the dentry. This "extra care" typically |
7bbfd9ad | 906 | involves using `READ_ONCE() <READ_ONCE_>`_ to access fields, and verifying the |
3587679d | 907 | result is not NULL before using it. This pattern can be seen in |
7bbfd9ad | 908 | ``nfs_lookup_revalidate()``. |
3ce96239 NB |
909 | |
910 | A pair of patterns | |
911 | ------------------ | |
912 | ||
913 | In various places in the details of REF-walk and RCU-walk, and also in | |
914 | the big picture, there are a couple of related patterns that are worth | |
915 | being aware of. | |
916 | ||
917 | The first is "try quickly and check, if that fails try slowly". We | |
918 | can see that in the high-level approach of first trying RCU-walk and | |
7bbfd9ad | 919 | then trying REF-walk, and in places where ``unlazy_walk()`` is used to |
3ce96239 | 920 | switch to REF-walk for the rest of the path. We also saw it earlier |
7bbfd9ad | 921 | in ``dget_parent()`` when following a "``..``" link. It tries a quick way |
3ce96239 NB |
922 | to get a reference, then falls back to taking locks if needed. |
923 | ||
924 | The second pattern is "try quickly and check, if that fails try | |
7bbfd9ad N |
925 | again - repeatedly". This is seen with the use of ``rename_lock`` and |
926 | ``mount_lock`` in REF-walk. RCU-walk doesn't make use of this pattern - | |
3ce96239 NB |
927 | if anything goes wrong it is much safer to just abort and try a more |
928 | sedate approach. | |
929 | ||
930 | The emphasis here is "try quickly and check". It should probably be | |
931 | "try quickly _and carefully,_ then check". The fact that checking is | |
932 | needed is a reminder that the system is dynamic and only a limited | |
933 | number of things are safe at all. The most likely cause of errors in | |
934 | this whole process is assuming something is safe when in reality it | |
935 | isn't. Careful consideration of what exactly guarantees the safety of | |
936 | each access is sometimes necessary. | |
937 | ||
938 | A walk among the symlinks | |
939 | ========================= | |
940 | ||
941 | There are several basic issues that we will examine to understand the | |
942 | handling of symbolic links: the symlink stack, together with cache | |
943 | lifetimes, will help us understand the overall recursive handling of | |
944 | symlinks and lead to the special care needed for the final component. | |
945 | Then a consideration of access-time updates and summary of the various | |
946 | flags controlling lookup will finish the story. | |
947 | ||
948 | The symlink stack | |
949 | ----------------- | |
950 | ||
951 | There are only two sorts of filesystem objects that can usefully | |
952 | appear in a path prior to the final component: directories and symlinks. | |
953 | Handling directories is quite straightforward: the new directory | |
954 | simply becomes the starting point at which to interpret the next | |
955 | component on the path. Handling symbolic links requires a bit more | |
956 | work. | |
957 | ||
958 | Conceptually, symbolic links could be handled by editing the path. If | |
959 | a component name refers to a symbolic link, then that component is | |
960 | replaced by the body of the link and, if that body starts with a '/', | |
961 | then all preceding parts of the path are discarded. This is what the | |
7bbfd9ad N |
962 | "``readlink -f``" command does, though it also edits out "``.``" and |
963 | "``..``" components. | |
3ce96239 NB |
964 | |
965 | Directly editing the path string is not really necessary when looking | |
966 | up a path, and discarding early components is pointless as they aren't | |
967 | looked at anyway. Keeping track of all remaining components is | |
968 | important, but they can of course be kept separately; there is no need | |
969 | to concatenate them. As one symlink may easily refer to another, | |
970 | which in turn can refer to a third, we may need to keep the remaining | |
971 | components of several paths, each to be processed when the preceding | |
972 | ones are completed. These path remnants are kept on a stack of | |
973 | limited size. | |
974 | ||
975 | There are two reasons for placing limits on how many symlinks can | |
976 | occur in a single path lookup. The most obvious is to avoid loops. | |
977 | If a symlink referred to itself either directly or through | |
978 | intermediaries, then following the symlink can never complete | |
7bbfd9ad | 979 | successfully - the error ``ELOOP`` must be returned. Loops can be |
3ce96239 NB |
980 | detected without imposing limits, but limits are the simplest solution |
981 | and, given the second reason for restriction, quite sufficient. | |
982 | ||
7bbfd9ad | 983 | .. _outlined recently: http://thread.gmane.org/gmane.linux.kernel/1934390/focus=1934550 |
3ce96239 | 984 | |
7bbfd9ad | 985 | The second reason was `outlined recently`_ by Linus: |
3ce96239 | 986 | |
7bbfd9ad N |
987 | Because it's a latency and DoS issue too. We need to react well to |
988 | true loops, but also to "very deep" non-loops. It's not about memory | |
989 | use, it's about users triggering unreasonable CPU resources. | |
3ce96239 | 990 | |
7bbfd9ad | 991 | Linux imposes a limit on the length of any pathname: ``PATH_MAX``, which |
3ce96239 NB |
992 | is 4096. There are a number of reasons for this limit; not letting the |
993 | kernel spend too much time on just one path is one of them. With | |
994 | symbolic links you can effectively generate much longer paths so some | |
995 | sort of limit is needed for the same reason. Linux imposes a limit of | |
996 | at most 40 symlinks in any one path lookup. It previously imposed a | |
997 | further limit of eight on the maximum depth of recursion, but that was | |
998 | raised to 40 when a separate stack was implemented, so there is now | |
999 | just the one limit. | |
1000 | ||
7bbfd9ad | 1001 | The ``nameidata`` structure that we met in an earlier article contains a |
3ce96239 NB |
1002 | small stack that can be used to store the remaining part of up to two |
1003 | symlinks. In many cases this will be sufficient. If it isn't, a | |
1004 | separate stack is allocated with room for 40 symlinks. Pathname | |
1005 | lookup will never exceed that stack as, once the 40th symlink is | |
1006 | detected, an error is returned. | |
1007 | ||
1008 | It might seem that the name remnants are all that needs to be stored on | |
1009 | this stack, but we need a bit more. To see that, we need to move on to | |
1010 | cache lifetimes. | |
1011 | ||
1012 | Storage and lifetime of cached symlinks | |
1013 | --------------------------------------- | |
1014 | ||
1015 | Like other filesystem resources, such as inodes and directory | |
1016 | entries, symlinks are cached by Linux to avoid repeated costly access | |
1017 | to external storage. It is particularly important for RCU-walk to be | |
1018 | able to find and temporarily hold onto these cached entries, so that | |
1019 | it doesn't need to drop down into REF-walk. | |
1020 | ||
7bbfd9ad | 1021 | .. _object-oriented design pattern: https://lwn.net/Articles/446317/ |
3ce96239 NB |
1022 | |
1023 | While each filesystem is free to make its own choice, symlinks are | |
1024 | typically stored in one of two places. Short symlinks are often | |
7bbfd9ad N |
1025 | stored directly in the inode. When a filesystem allocates a ``struct |
1026 | inode`` it typically allocates extra space to store private data (a | |
1027 | common `object-oriented design pattern`_ in the kernel). This will | |
3ce96239 NB |
1028 | sometimes include space for a symlink. The other common location is |
1029 | in the page cache, which normally stores the content of files. The | |
1030 | pathname in a symlink can be seen as the content of that symlink and | |
1031 | can easily be stored in the page cache just like file content. | |
1032 | ||
1033 | When neither of these is suitable, the next most likely scenario is | |
1034 | that the filesystem will allocate some temporary memory and copy or | |
1035 | construct the symlink content into that memory whenever it is needed. | |
1036 | ||
1037 | When the symlink is stored in the inode, it has the same lifetime as | |
1038 | the inode which, itself, is protected by RCU or by a counted reference | |
1039 | on the dentry. This means that the mechanisms that pathname lookup | |
1040 | uses to access the dcache and icache (inode cache) safely are quite | |
1041 | sufficient for accessing some cached symlinks safely. In these cases, | |
7bbfd9ad | 1042 | the ``i_link`` pointer in the inode is set to point to wherever the |
3ce96239 NB |
1043 | symlink is stored and it can be accessed directly whenever needed. |
1044 | ||
1045 | When the symlink is stored in the page cache or elsewhere, the | |
1046 | situation is not so straightforward. A reference on a dentry or even | |
1047 | on an inode does not imply any reference on cached pages of that | |
7bbfd9ad | 1048 | inode, and even an ``rcu_read_lock()`` is not sufficient to ensure that |
3ce96239 NB |
1049 | a page will not disappear. So for these symlinks the pathname lookup |
1050 | code needs to ask the filesystem to provide a stable reference and, | |
1051 | significantly, needs to release that reference when it is finished | |
1052 | with it. | |
1053 | ||
1054 | Taking a reference to a cache page is often possible even in RCU-walk | |
1055 | mode. It does require making changes to memory, which is best avoided, | |
1056 | but that isn't necessarily a big cost and it is better than dropping | |
1057 | out of RCU-walk mode completely. Even filesystems that allocate | |
7bbfd9ad | 1058 | space to copy the symlink into can use ``GFP_ATOMIC`` to often successfully |
3ce96239 NB |
1059 | allocate memory without the need to drop out of RCU-walk. If a |
1060 | filesystem cannot successfully get a reference in RCU-walk mode, it | |
7bbfd9ad | 1061 | must return ``-ECHILD`` and ``unlazy_walk()`` will be called to return to |
3ce96239 NB |
1062 | REF-walk mode in which the filesystem is allowed to sleep. |
1063 | ||
7bbfd9ad | 1064 | The place for all this to happen is the ``i_op->follow_link()`` inode |
3ce96239 NB |
1065 | method. In the present mainline code this is never actually called in |
1066 | RCU-walk mode as the rewrite is not quite complete. It is likely that | |
7bbfd9ad | 1067 | in a future release this method will be passed an ``inode`` pointer when |
3ce96239 | 1068 | called in RCU-walk mode so it both (1) knows to be careful, and (2) has the |
7bbfd9ad N |
1069 | validated pointer. Much like the ``i_op->permission()`` method we |
1070 | looked at previously, ``->follow_link()`` would need to be careful that | |
3ce96239 NB |
1071 | all the data structures it references are safe to be accessed while |
1072 | holding no counted reference, only the RCU lock. Though getting a | |
7bbfd9ad | 1073 | reference with ``->follow_link()`` is not yet done in RCU-walk mode, the |
3ce96239 NB |
1074 | code is ready to release the reference when that does happen. |
1075 | ||
1076 | This need to drop the reference to a symlink adds significant | |
1077 | complexity. It requires a reference to the inode so that the | |
7bbfd9ad | 1078 | ``i_op->put_link()`` inode operation can be called. In REF-walk, that |
3ce96239 | 1079 | reference is kept implicitly through a reference to the dentry, so |
7bbfd9ad | 1080 | keeping the ``struct path`` of the symlink is easiest. For RCU-walk, |
3ce96239 NB |
1081 | the pointer to the inode is kept separately. To allow switching from |
1082 | RCU-walk back to REF-walk in the middle of processing nested symlinks | |
1083 | we also need the seq number for the dentry so we can confirm that | |
1084 | switching back was safe. | |
1085 | ||
1086 | Finally, when providing a reference to a symlink, the filesystem also | |
7bbfd9ad | 1087 | provides an opaque "cookie" that must be passed to ``->put_link()`` so that it |
3ce96239 | 1088 | knows what to free. This might be the allocated memory area, or a |
7bbfd9ad | 1089 | pointer to the ``struct page`` in the page cache, or something else |
3ce96239 NB |
1090 | completely. Only the filesystem knows what it is. |
1091 | ||
1092 | In order for the reference to each symlink to be dropped when the walk completes, | |
1093 | whether in RCU-walk or REF-walk, the symlink stack needs to contain, | |
1094 | along with the path remnants: | |
1095 | ||
7bbfd9ad N |
1096 | - the ``struct path`` to provide a reference to the inode in REF-walk |
1097 | - the ``struct inode *`` to provide a reference to the inode in RCU-walk | |
1098 | - the ``seq`` to allow the path to be safely switched from RCU-walk to REF-walk | |
1099 | - the ``cookie`` that tells ``->put_path()`` what to put. | |
3ce96239 NB |
1100 | |
1101 | This means that each entry in the symlink stack needs to hold five | |
1102 | pointers and an integer instead of just one pointer (the path | |
1103 | remnant). On a 64-bit system, this is about 40 bytes per entry; | |
1104 | with 40 entries it adds up to 1600 bytes total, which is less than | |
1105 | half a page. So it might seem like a lot, but is by no means | |
1106 | excessive. | |
1107 | ||
7bbfd9ad | 1108 | Note that, in a given stack frame, the path remnant (``name``) is not |
3ce96239 NB |
1109 | part of the symlink that the other fields refer to. It is the remnant |
1110 | to be followed once that symlink has been fully parsed. | |
1111 | ||
1112 | Following the symlink | |
1113 | --------------------- | |
1114 | ||
7bbfd9ad | 1115 | The main loop in ``link_path_walk()`` iterates seamlessly over all |
3ce96239 | 1116 | components in the path and all of the non-final symlinks. As symlinks |
7bbfd9ad | 1117 | are processed, the ``name`` pointer is adjusted to point to a new |
3ce96239 | 1118 | symlink, or is restored from the stack, so that much of the loop |
7bbfd9ad | 1119 | doesn't need to notice. Getting this ``name`` variable on and off the |
3ce96239 NB |
1120 | stack is very straightforward; pushing and popping the references is |
1121 | a little more complex. | |
1122 | ||
7bbfd9ad N |
1123 | When a symlink is found, ``walk_component()`` returns the value ``1`` |
1124 | (``0`` is returned for any other sort of success, and a negative number | |
1125 | is, as usual, an error indicator). This causes ``get_link()`` to be | |
3ce96239 | 1126 | called; it then gets the link from the filesystem. Providing that |
7bbfd9ad N |
1127 | operation is successful, the old path ``name`` is placed on the stack, |
1128 | and the new value is used as the ``name`` for a while. When the end of | |
1129 | the path is found (i.e. ``*name`` is ``'\0'``) the old ``name`` is restored | |
3ce96239 NB |
1130 | off the stack and path walking continues. |
1131 | ||
1132 | Pushing and popping the reference pointers (inode, cookie, etc.) is more | |
1133 | complex in part because of the desire to handle tail recursion. When | |
1134 | the last component of a symlink itself points to a symlink, we | |
1135 | want to pop the symlink-just-completed off the stack before pushing | |
1136 | the symlink-just-found to avoid leaving empty path remnants that would | |
1137 | just get in the way. | |
1138 | ||
1139 | It is most convenient to push the new symlink references onto the | |
7bbfd9ad N |
1140 | stack in ``walk_component()`` immediately when the symlink is found; |
1141 | ``walk_component()`` is also the last piece of code that needs to look at the | |
3ce96239 | 1142 | old symlink as it walks that last component. So it is quite |
7bbfd9ad | 1143 | convenient for ``walk_component()`` to release the old symlink and pop |
3ce96239 | 1144 | the references just before pushing the reference information for the |
7bbfd9ad | 1145 | new symlink. It is guided in this by two flags; ``WALK_GET``, which |
3ce96239 | 1146 | gives it permission to follow a symlink if it finds one, and |
7bbfd9ad N |
1147 | ``WALK_PUT``, which tells it to release the current symlink after it has been |
1148 | followed. ``WALK_PUT`` is tested first, leading to a call to | |
1149 | ``put_link()``. ``WALK_GET`` is tested subsequently (by | |
1150 | ``should_follow_link()``) leading to a call to ``pick_link()`` which sets | |
3ce96239 NB |
1151 | up the stack frame. |
1152 | ||
7bbfd9ad N |
1153 | Symlinks with no final component |
1154 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
3ce96239 NB |
1155 | |
1156 | A pair of special-case symlinks deserve a little further explanation. | |
7bbfd9ad N |
1157 | Both result in a new ``struct path`` (with mount and dentry) being set |
1158 | up in the ``nameidata``, and result in ``get_link()`` returning ``NULL``. | |
3ce96239 | 1159 | |
7bbfd9ad N |
1160 | The more obvious case is a symlink to "``/``". All symlinks starting |
1161 | with "``/``" are detected in ``get_link()`` which resets the ``nameidata`` | |
3ce96239 | 1162 | to point to the effective filesystem root. If the symlink only |
7bbfd9ad N |
1163 | contains "``/``" then there is nothing more to do, no components at all, |
1164 | so ``NULL`` is returned to indicate that the symlink can be released and | |
3ce96239 NB |
1165 | the stack frame discarded. |
1166 | ||
7bbfd9ad | 1167 | The other case involves things in ``/proc`` that look like symlinks but |
b55eef87 | 1168 | aren't really (and are therefore commonly referred to as "magic-links"):: |
3ce96239 | 1169 | |
7bbfd9ad N |
1170 | $ ls -l /proc/self/fd/1 |
1171 | lrwx------ 1 neilb neilb 64 Jun 13 10:19 /proc/self/fd/1 -> /dev/pts/4 | |
3ce96239 | 1172 | |
7bbfd9ad | 1173 | Every open file descriptor in any process is represented in ``/proc`` by |
3ce96239 | 1174 | something that looks like a symlink. It is really a reference to the |
7bbfd9ad | 1175 | target file, not just the name of it. When you ``readlink`` these |
3ce96239 | 1176 | objects you get a name that might refer to the same file - unless it |
7bbfd9ad N |
1177 | has been unlinked or mounted over. When ``walk_component()`` follows |
1178 | one of these, the ``->follow_link()`` method in "procfs" doesn't return | |
1179 | a string name, but instead calls ``nd_jump_link()`` which updates the | |
1180 | ``nameidata`` in place to point to that target. ``->follow_link()`` then | |
1181 | returns ``NULL``. Again there is no final component and ``get_link()`` | |
1182 | reports this by leaving the ``last_type`` field of ``nameidata`` as | |
1183 | ``LAST_BIND``. | |
3ce96239 NB |
1184 | |
1185 | Following the symlink in the final component | |
1186 | -------------------------------------------- | |
1187 | ||
7bbfd9ad | 1188 | All this leads to ``link_path_walk()`` walking down every component, and |
3ce96239 | 1189 | following all symbolic links it finds, until it reaches the final |
7bbfd9ad | 1190 | component. This is just returned in the ``last`` field of ``nameidata``. |
3ce96239 | 1191 | For some callers, this is all they need; they want to create that |
7bbfd9ad | 1192 | ``last`` name if it doesn't exist or give an error if it does. Other |
3ce96239 NB |
1193 | callers will want to follow a symlink if one is found, and possibly |
1194 | apply special handling to the last component of that symlink, rather | |
1195 | than just the last component of the original file name. These callers | |
7bbfd9ad | 1196 | potentially need to call ``link_path_walk()`` again and again on |
3ce96239 NB |
1197 | successive symlinks until one is found that doesn't point to another |
1198 | symlink. | |
1199 | ||
7bbfd9ad N |
1200 | This case is handled by the relevant caller of ``link_path_walk()``, such as |
1201 | ``path_lookupat()`` using a loop that calls ``link_path_walk()``, and then | |
3ce96239 | 1202 | handles the final component. If the final component is a symlink |
7bbfd9ad N |
1203 | that needs to be followed, then ``trailing_symlink()`` is called to set |
1204 | things up properly and the loop repeats, calling ``link_path_walk()`` | |
3ce96239 NB |
1205 | again. This could loop as many as 40 times if the last component of |
1206 | each symlink is another symlink. | |
1207 | ||
1208 | The various functions that examine the final component and possibly | |
7bbfd9ad N |
1209 | report that it is a symlink are ``lookup_last()``, ``mountpoint_last()`` |
1210 | and ``do_last()``, each of which use the same convention as | |
1211 | ``walk_component()`` of returning ``1`` if a symlink was found that needs | |
3ce96239 NB |
1212 | to be followed. |
1213 | ||
7bbfd9ad N |
1214 | Of these, ``do_last()`` is the most interesting as it is used for |
1215 | opening a file. Part of ``do_last()`` runs with ``i_rwsem`` held and this | |
1216 | part is in a separate function: ``lookup_open()``. | |
3ce96239 | 1217 | |
7bbfd9ad | 1218 | Explaining ``do_last()`` completely is beyond the scope of this article, |
3ce96239 NB |
1219 | but a few highlights should help those interested in exploring the |
1220 | code. | |
1221 | ||
7bbfd9ad N |
1222 | 1. Rather than just finding the target file, ``do_last()`` needs to open |
1223 | it. If the file was found in the dcache, then ``vfs_open()`` is used for | |
1224 | this. If not, then ``lookup_open()`` will either call ``atomic_open()`` (if | |
1225 | the filesystem provides it) to combine the final lookup with the open, or | |
1226 | will perform the separate ``lookup_real()`` and ``vfs_create()`` steps | |
1227 | directly. In the later case the actual "open" of this newly found or | |
1228 | created file will be performed by ``vfs_open()``, just as if the name | |
1229 | were found in the dcache. | |
1230 | ||
1231 | 2. ``vfs_open()`` can fail with ``-EOPENSTALE`` if the cached information | |
1232 | wasn't quite current enough. Rather than restarting the lookup from | |
1233 | the top with ``LOOKUP_REVAL`` set, ``lookup_open()`` is called instead, | |
1234 | giving the filesystem a chance to resolve small inconsistencies. | |
1235 | If that doesn't work, only then is the lookup restarted from the top. | |
3ce96239 NB |
1236 | |
1237 | 3. An open with O_CREAT **does** follow a symlink in the final component, | |
7bbfd9ad | 1238 | unlike other creation system calls (like ``mkdir``). So the sequence:: |
3ce96239 | 1239 | |
7bbfd9ad N |
1240 | ln -s bar /tmp/foo |
1241 | echo hello > /tmp/foo | |
3ce96239 | 1242 | |
7bbfd9ad N |
1243 | will create a file called ``/tmp/bar``. This is not permitted if |
1244 | ``O_EXCL`` is set but otherwise is handled for an O_CREAT open much | |
1245 | like for a non-creating open: ``should_follow_link()`` returns ``1``, and | |
1246 | so does ``do_last()`` so that ``trailing_symlink()`` gets called and the | |
1247 | open process continues on the symlink that was found. | |
3ce96239 NB |
1248 | |
1249 | Updating the access time | |
1250 | ------------------------ | |
1251 | ||
1252 | We previously said of RCU-walk that it would "take no locks, increment | |
1253 | no counts, leave no footprints." We have since seen that some | |
1254 | "footprints" can be needed when handling symlinks as a counted | |
1255 | reference (or even a memory allocation) may be needed. But these | |
1256 | footprints are best kept to a minimum. | |
1257 | ||
1258 | One other place where walking down a symlink can involve leaving | |
1259 | footprints in a way that doesn't affect directories is in updating access times. | |
1260 | In Unix (and Linux) every filesystem object has a "last accessed | |
7bbfd9ad | 1261 | time", or "``atime``". Passing through a directory to access a file |
3ce96239 | 1262 | within is not considered to be an access for the purposes of |
7bbfd9ad N |
1263 | ``atime``; only listing the contents of a directory can update its ``atime``. |
1264 | Symlinks are different it seems. Both reading a symlink (with ``readlink()``) | |
3ce96239 NB |
1265 | and looking up a symlink on the way to some other destination can |
1266 | update the atime on that symlink. | |
1267 | ||
7bbfd9ad | 1268 | .. _clearest statement: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_08 |
3ce96239 NB |
1269 | |
1270 | It is not clear why this is the case; POSIX has little to say on the | |
7bbfd9ad | 1271 | subject. The `clearest statement`_ is that, if a particular implementation |
3ce96239 NB |
1272 | updates a timestamp in a place not specified by POSIX, this must be |
1273 | documented "except that any changes caused by pathname resolution need | |
1274 | not be documented". This seems to imply that POSIX doesn't really | |
1275 | care about access-time updates during pathname lookup. | |
1276 | ||
7bbfd9ad | 1277 | .. _Linux 1.3.87: https://git.kernel.org/cgit/linux/kernel/git/history/history.git/diff/fs/ext2/symlink.c?id=f806c6db77b8eaa6e00dcfb6b567706feae8dbb8 |
3ce96239 | 1278 | |
7bbfd9ad | 1279 | An examination of history shows that prior to `Linux 1.3.87`_, the ext2 |
3ce96239 NB |
1280 | filesystem, at least, didn't update atime when following a link. |
1281 | Unfortunately we have no record of why that behavior was changed. | |
1282 | ||
1283 | In any case, access time must now be updated and that operation can be | |
1284 | quite complex. Trying to stay in RCU-walk while doing it is best | |
7bbfd9ad N |
1285 | avoided. Fortunately it is often permitted to skip the ``atime`` |
1286 | update. Because ``atime`` updates cause performance problems in various | |
1287 | areas, Linux supports the ``relatime`` mount option, which generally | |
1288 | limits the updates of ``atime`` to once per day on files that aren't | |
3ce96239 | 1289 | being changed (and symlinks never change once created). Even without |
7bbfd9ad | 1290 | ``relatime``, many filesystems record ``atime`` with a one-second |
3ce96239 NB |
1291 | granularity, so only one update per second is required. |
1292 | ||
7bbfd9ad | 1293 | It is easy to test if an ``atime`` update is needed while in RCU-walk |
3ce96239 | 1294 | mode and, if it isn't, the update can be skipped and RCU-walk mode |
7bbfd9ad | 1295 | continues. Only when an ``atime`` update is actually required does the |
3ce96239 | 1296 | path walk drop down to REF-walk. All of this is handled in the |
7bbfd9ad | 1297 | ``get_link()`` function. |
3ce96239 NB |
1298 | |
1299 | A few flags | |
1300 | ----------- | |
1301 | ||
1302 | A suitable way to wrap up this tour of pathname walking is to list | |
7bbfd9ad | 1303 | the various flags that can be stored in the ``nameidata`` to guide the |
3ce96239 | 1304 | lookup process. Many of these are only meaningful on the final |
b55eef87 AS |
1305 | component, others reflect the current state of the pathname lookup, and some |
1306 | apply restrictions to all path components encountered in the path lookup. | |
1307 | ||
7bbfd9ad | 1308 | And then there is ``LOOKUP_EMPTY``, which doesn't fit conceptually with |
3ce96239 NB |
1309 | the others. If this is not set, an empty pathname causes an error |
1310 | very early on. If it is set, empty pathnames are not considered to be | |
1311 | an error. | |
1312 | ||
7bbfd9ad N |
1313 | Global state flags |
1314 | ~~~~~~~~~~~~~~~~~~ | |
3ce96239 | 1315 | |
7bbfd9ad N |
1316 | We have already met two global state flags: ``LOOKUP_RCU`` and |
1317 | ``LOOKUP_REVAL``. These select between one of three overall approaches | |
3ce96239 NB |
1318 | to lookup: RCU-walk, REF-walk, and REF-walk with forced revalidation. |
1319 | ||
7bbfd9ad | 1320 | ``LOOKUP_PARENT`` indicates that the final component hasn't been reached |
3ce96239 NB |
1321 | yet. This is primarily used to tell the audit subsystem the full |
1322 | context of a particular access being audited. | |
1323 | ||
7bbfd9ad | 1324 | ``LOOKUP_ROOT`` indicates that the ``root`` field in the ``nameidata`` was |
3ce96239 NB |
1325 | provided by the caller, so it shouldn't be released when it is no |
1326 | longer needed. | |
1327 | ||
7bbfd9ad | 1328 | ``LOOKUP_JUMPED`` means that the current dentry was chosen not because |
3ce96239 | 1329 | it had the right name but for some other reason. This happens when |
7bbfd9ad | 1330 | following "``..``", following a symlink to ``/``, crossing a mount point |
b55eef87 AS |
1331 | or accessing a "``/proc/$PID/fd/$FD``" symlink (also known as a "magic |
1332 | link"). In this case the filesystem has not been asked to revalidate the | |
1333 | name (with ``d_revalidate()``). In such cases the inode may still need | |
1334 | to be revalidated, so ``d_op->d_weak_revalidate()`` is called if | |
7bbfd9ad | 1335 | ``LOOKUP_JUMPED`` is set when the look completes - which may be at the |
3ce96239 NB |
1336 | final component or, when creating, unlinking, or renaming, at the penultimate component. |
1337 | ||
b55eef87 AS |
1338 | Resolution-restriction flags |
1339 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
1340 | ||
1341 | In order to allow userspace to protect itself against certain race conditions | |
1342 | and attack scenarios involving changing path components, a series of flags are | |
1343 | available which apply restrictions to all path components encountered during | |
1344 | path lookup. These flags are exposed through ``openat2()``'s ``resolve`` field. | |
1345 | ||
1346 | ``LOOKUP_NO_SYMLINKS`` blocks all symlink traversals (including magic-links). | |
1347 | This is distinctly different from ``LOOKUP_FOLLOW``, because the latter only | |
1348 | relates to restricting the following of trailing symlinks. | |
1349 | ||
1350 | ``LOOKUP_NO_MAGICLINKS`` blocks all magic-link traversals. Filesystems must | |
1351 | ensure that they return errors from ``nd_jump_link()``, because that is how | |
1352 | ``LOOKUP_NO_MAGICLINKS`` and other magic-link restrictions are implemented. | |
1353 | ||
1354 | ``LOOKUP_NO_XDEV`` blocks all ``vfsmount`` traversals (this includes both | |
1355 | bind-mounts and ordinary mounts). Note that the ``vfsmount`` which contains the | |
1356 | lookup is determined by the first mountpoint the path lookup reaches -- | |
1357 | absolute paths start with the ``vfsmount`` of ``/``, and relative paths start | |
1358 | with the ``dfd``'s ``vfsmount``. Magic-links are only permitted if the | |
1359 | ``vfsmount`` of the path is unchanged. | |
1360 | ||
1361 | ``LOOKUP_BENEATH`` blocks any path components which resolve outside the | |
1362 | starting point of the resolution. This is done by blocking ``nd_jump_root()`` | |
1363 | as well as blocking ".." if it would jump outside the starting point. | |
1364 | ``rename_lock`` and ``mount_lock`` are used to detect attacks against the | |
1365 | resolution of "..". Magic-links are also blocked. | |
1366 | ||
1367 | ``LOOKUP_IN_ROOT`` resolves all path components as though the starting point | |
1368 | were the filesystem root. ``nd_jump_root()`` brings the resolution back to to | |
1369 | the starting point, and ".." at the starting point will act as a no-op. As with | |
1370 | ``LOOKUP_BENEATH``, ``rename_lock`` and ``mount_lock`` are used to detect | |
1371 | attacks against ".." resolution. Magic-links are also blocked. | |
1372 | ||
7bbfd9ad N |
1373 | Final-component flags |
1374 | ~~~~~~~~~~~~~~~~~~~~~ | |
3ce96239 NB |
1375 | |
1376 | Some of these flags are only set when the final component is being | |
1377 | considered. Others are only checked for when considering that final | |
1378 | component. | |
1379 | ||
7bbfd9ad | 1380 | ``LOOKUP_AUTOMOUNT`` ensures that, if the final component is an automount |
3ce96239 | 1381 | point, then the mount is triggered. Some operations would trigger it |
7bbfd9ad N |
1382 | anyway, but operations like ``stat()`` deliberately don't. ``statfs()`` |
1383 | needs to trigger the mount but otherwise behaves a lot like ``stat()``, so | |
1384 | it sets ``LOOKUP_AUTOMOUNT``, as does "``quotactl()``" and the handling of | |
1385 | "``mount --bind``". | |
3ce96239 | 1386 | |
7bbfd9ad | 1387 | ``LOOKUP_FOLLOW`` has a similar function to ``LOOKUP_AUTOMOUNT`` but for |
3ce96239 | 1388 | symlinks. Some system calls set or clear it implicitly, while |
7bbfd9ad N |
1389 | others have API flags such as ``AT_SYMLINK_FOLLOW`` and |
1390 | ``UMOUNT_NOFOLLOW`` to control it. Its effect is similar to | |
1391 | ``WALK_GET`` that we already met, but it is used in a different way. | |
3ce96239 | 1392 | |
7bbfd9ad | 1393 | ``LOOKUP_DIRECTORY`` insists that the final component is a directory. |
3ce96239 NB |
1394 | Various callers set this and it is also set when the final component |
1395 | is found to be followed by a slash. | |
1396 | ||
7bbfd9ad N |
1397 | Finally ``LOOKUP_OPEN``, ``LOOKUP_CREATE``, ``LOOKUP_EXCL``, and |
1398 | ``LOOKUP_RENAME_TARGET`` are not used directly by the VFS but are made | |
1399 | available to the filesystem and particularly the ``->d_revalidate()`` | |
3ce96239 NB |
1400 | method. A filesystem can choose not to bother revalidating too hard |
1401 | if it knows that it will be asked to open or create the file soon. | |
7bbfd9ad N |
1402 | These flags were previously useful for ``->lookup()`` too but with the |
1403 | introduction of ``->atomic_open()`` they are less relevant there. | |
3ce96239 NB |
1404 | |
1405 | End of the road | |
1406 | --------------- | |
1407 | ||
1408 | Despite its complexity, all this pathname lookup code appears to be | |
1409 | in good shape - various parts are certainly easier to understand now | |
1410 | than even a couple of releases ago. But that doesn't mean it is | |
1411 | "finished". As already mentioned, RCU-walk currently only follows | |
1412 | symlinks that are stored in the inode so, while it handles many ext4 | |
1413 | symlinks, it doesn't help with NFS, XFS, or Btrfs. That support | |
1414 | is not likely to be long delayed. |