Jonathan Corbet | 4064174 | 2019-02-20 15:29:36 -0700 | [diff] [blame] | 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. |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 16 | - ``openat2()`` resolution restriction flags. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 17 | |
| 18 | Introduction to pathname lookup |
| 19 | =============================== |
| 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 | |
| 37 | .. _openat: http://man7.org/linux/man-pages/man2/openat.2.html |
| 38 | |
| 39 | Pathnames (sometimes "file names"), used to identify objects in the |
| 40 | filesystem, will be familiar to most readers. They contain two sorts |
| 41 | of elements: "slashes" that are sequences of one or more "``/``" |
| 42 | characters, and "components" that are sequences of one or more |
| 43 | non-"``/``" characters. These form two kinds of paths. Those that |
| 44 | start with slashes are "absolute" and start from the filesystem root. |
| 45 | The others are "relative" and start from the current directory, or |
Vegard Nossum | 87b92d4 | 2020-07-27 14:15:24 +0200 | [diff] [blame] | 46 | from some other location specified by a file descriptor given to |
| 47 | "``*at()``" system calls such as `openat() <openat_>`_. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 48 | |
| 49 | .. _execveat: http://man7.org/linux/man-pages/man2/execveat.2.html |
| 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 |
Vegard Nossum | 87b92d4 | 2020-07-27 14:15:24 +0200 | [diff] [blame] | 54 | generally forbidden in POSIX, but some of those "``*at()``" system calls |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 55 | in Linux permit it when the ``AT_EMPTY_PATH`` flag is given. For |
| 56 | example, if you have an open file descriptor on an executable file you |
| 57 | can execute it by calling `execveat() <execveat_>`_ passing |
| 58 | the file descriptor, an empty path, and the ``AT_EMPTY_PATH`` flag. |
| 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 |
| 63 | such as ``ENOENT`` or ``ENOTDIR`` will be reported. |
| 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 |
| 69 | exist, it could be "``.``" or "``..``" which are handled quite differently |
| 70 | from other components. |
| 71 | |
Alexander A. Klimov | c69f22f2 | 2020-06-21 15:35:52 +0200 | [diff] [blame] | 72 | .. _POSIX: https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_12 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 73 | |
| 74 | If a pathname ends with a slash, such as "``/tmp/foo/``" it might be |
| 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 |
| 77 | particular, ``mkdir()`` and ``rmdir()`` each create or remove a directory named |
| 78 | by the final component, and they are required to work with pathnames |
Vegard Nossum | ad551a2 | 2020-07-27 13:45:27 +0200 | [diff] [blame] | 79 | ending in "``/``". According to POSIX_: |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 80 | |
Vegard Nossum | ad551a2 | 2020-07-27 13:45:27 +0200 | [diff] [blame] | 81 | A pathname that contains at least one non-<slash> character and |
| 82 | that ends with one or more trailing <slash> characters shall not |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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. |
| 87 | |
| 88 | The Linux pathname walking code (mostly in ``fs/namei.c``) deals with |
| 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 | |
| 105 | More than just a cache |
| 106 | ---------------------- |
| 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 |
| 113 | the given name. The inode pointer can be ``NULL`` indicating that the |
| 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 |
| 140 | ``DCACHE_OP_REVALIDATE`` flag being set in the dentry. |
| 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 |
| 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``" |
| 151 | (indicating the use of RCU-walk) is set. |
| 152 | |
| 153 | .. _Meet the Lockers: https://lwn.net/Articles/453685/ |
| 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 |
| 160 | as in `Meet the Lockers`_. |
| 161 | |
| 162 | The locking mechanisms used by REF-walk include: |
| 163 | |
| 164 | dentry->d_lockref |
| 165 | ~~~~~~~~~~~~~~~~~ |
| 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 |
| 174 | will behave as expected. It also protects the ``->d_inode`` reference |
| 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 |
| 180 | initially be negative (i.e. ``d_inode`` is ``NULL``), and will be assigned |
| 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 |
| 184 | setting ``d_inode`` to ``NULL``, or by removing it from the hash table |
| 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 |
| 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 |
| 191 | very common case. |
| 192 | |
| 193 | So as long as a counted reference is held to a dentry, a non-``NULL`` ``->d_inode`` |
| 194 | value will never be changed. |
| 195 | |
| 196 | dentry->d_lock |
| 197 | ~~~~~~~~~~~~~~ |
| 198 | |
| 199 | ``d_lock`` is a synonym for the spinlock that is part of ``d_lockref`` above. |
| 200 | For our purposes, holding this lock protects against the dentry being |
| 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 |
| 203 | dentry hash table. |
| 204 | |
| 205 | When looking for a name in a directory, REF-walk takes ``d_lock`` on |
| 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 | |
| 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``, |
| 212 | but it first tries a more lightweight approach. As seen in |
| 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 |
| 215 | no need to actually take the lock on the child. |
| 216 | |
| 217 | rename_lock |
| 218 | ~~~~~~~~~~~ |
| 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 | |
Vegard Nossum | 286b7e2 | 2020-07-27 14:15:25 +0200 | [diff] [blame] | 232 | The name-lookup process (``d_lookup()``) does *not* try to prevent this |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 233 | from happening, but only to detect when it happens. |
| 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 |
| 236 | unsuccessfully scanned a chain in the hash table, it simply tries |
| 237 | again. |
| 238 | |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 | |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 246 | inode->i_rwsem |
| 247 | ~~~~~~~~~~~~~~ |
| 248 | |
| 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()`` |
| 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 |
| 253 | currently in the dcache or, optionally, when the list of entries in a |
| 254 | directory is being retrieved with ``readdir()``. |
| 255 | |
| 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`` |
| 258 | on a name protects just one name in a directory. Most changes to the |
| 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 |
| 261 | exception is when idle dentries are removed from the dcache due to |
| 262 | memory pressure. This uses ``d_lock``, but ``i_rwsem`` plays no role. |
| 263 | |
| 264 | The semaphore affects pathname lookup in two distinct ways. Firstly it |
| 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 |
| 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 |
| 274 | sometimes need to take an exclusive lock on ``i_rwsem`` before performing the last lookup so |
| 275 | that the required exclusion can be achieved. How path lookup chooses |
| 276 | to take, or not take, ``i_rwsem`` is one of the |
| 277 | issues addressed in a subsequent section. |
| 278 | |
| 279 | If two threads attempt to look up the same name at the same time - a |
| 280 | name that is not yet in the dcache - the shared lock on ``i_rwsem`` will |
| 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, |
| 283 | based around a secondary hash table (``in_lookup_hashtable``) and a |
| 284 | per-dentry flag bit (``DCACHE_PAR_LOOKUP``). |
| 285 | |
| 286 | To add a new dentry to the cache while only holding a shared lock on |
| 287 | ``i_rwsem``, a thread must call ``d_alloc_parallel()``. This allocates a |
| 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 |
| 291 | hash table, with ``DCACHE_PAR_LOOKUP`` set. |
| 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 |
| 297 | detect this from the presence of ``DCACHE_PAR_LOOKUP``. In this case it |
| 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 |
| 300 | the lookup is complete, it must call ``d_lookup_done()`` which clears |
| 301 | the flag and does some other house keeping, including removing the |
| 302 | dentry from the secondary hash table - it will normally have been |
| 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 |
| 306 | in scope. |
| 307 | |
| 308 | If a matching dentry is found in the secondary hash table, |
| 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 |
| 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 |
| 317 | ``d_splice_alias()``. In any case, ``d_alloc_parallel()`` repeats all the |
| 318 | look ups from the start and will normally return something from the |
| 319 | primary hash table. |
| 320 | |
| 321 | mnt->mnt_count |
| 322 | ~~~~~~~~~~~~~~ |
| 323 | |
| 324 | ``mnt_count`` is a per-CPU reference counter on "``mount``" structures. |
| 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 |
| 327 | it needs to check with every CPU. Taking a ``mnt_count`` reference |
| 328 | prevents the mount structure from disappearing as the result of regular |
| 329 | unmount operations, but does not prevent a "lazy" unmount. So holding |
| 330 | ``mnt_count`` doesn't ensure that the mount remains in the namespace and, |
| 331 | in particular, doesn't stabilize the link to the mounted-on dentry. It |
| 332 | does, however, ensure that the ``mount`` data structure remains coherent, |
| 333 | and it provides a reference to the root dentry of the mounted |
| 334 | filesystem. So a reference through ``->mnt_count`` provides a stable |
| 335 | reference to the mounted dentry, but not the mounted-on dentry. |
| 336 | |
| 337 | mount_lock |
| 338 | ~~~~~~~~~~ |
| 339 | |
| 340 | ``mount_lock`` is a global seqlock, a bit like ``rename_lock``. It can be used to |
| 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 |
| 347 | the ``mnt_count``. Finally the value in ``mount_lock`` is checked against |
| 348 | the old value. If there is no change, then the crossing was safe. If there |
| 349 | was a change, the ``mnt_count`` is decremented and the whole process is |
| 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 | |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 | |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 366 | RCU |
| 367 | ~~~ |
| 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 | |
| 376 | Bringing it together with ``struct nameidata`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 377 | ---------------------------------------------- |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 378 | |
Alexander A. Klimov | c69f22f2 | 2020-06-21 15:35:52 +0200 | [diff] [blame] | 379 | .. _First edition Unix: https://minnie.tuhs.org/cgi-bin/utree.pl?file=V1/u2.s |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 380 | |
| 381 | Throughout the process of walking a path, the current status is stored |
| 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 |
| 385 | other fields): |
| 386 | |
| 387 | ``struct path path`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 388 | ~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 389 | |
| 390 | A ``path`` contains a ``struct vfsmount`` (which is |
| 391 | embedded in a ``struct mount``) and a ``struct dentry``. Together these |
| 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 |
| 395 | step. A reference through ``d_lockref`` and ``mnt_count`` is always |
| 396 | held. |
| 397 | |
| 398 | ``struct qstr last`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 399 | ~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 400 | |
Vegard Nossum | 286b7e2 | 2020-07-27 14:15:25 +0200 | [diff] [blame] | 401 | This is a string together with a length (i.e. *not* ``nul`` terminated) |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 402 | that is the "next" component in the pathname. |
| 403 | |
| 404 | ``int last_type`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 405 | ~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 406 | |
Al Viro | b4c0353 | 2020-01-19 11:44:51 -0500 | [diff] [blame] | 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``. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 409 | |
| 410 | ``struct path root`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 411 | ~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 |
| 416 | is requested. Keeping a reference in the ``nameidata`` ensures that |
| 417 | only one root is in effect for the entire path walk, even if it races |
| 418 | with a ``chroot()`` system call. |
| 419 | |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 | |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 424 | The root is needed when either of two conditions holds: (1) either the |
| 425 | pathname or a symbolic link starts with a "'/'", or (2) a "``..``" |
| 426 | component is being handled, since "``..``" from the root must always stay |
| 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 |
| 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 |
| 431 | specific part of the filesystem, and the lookup must not be allowed to |
| 432 | escape that subtree. It works a bit like a local ``chroot()``. |
| 433 | |
| 434 | Ignoring the handling of symbolic links, we can now describe the |
| 435 | "``link_path_walk()``" function, which handles the lookup of everything |
| 436 | except the final component as: |
| 437 | |
| 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. |
| 443 | |
| 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 |
| 448 | filesystem to revalidate the result if it is that sort of filesystem. |
| 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 |
Fox Chen | 993b892 | 2021-05-27 17:16:06 +0800 | [diff] [blame] | 451 | to find a definitive answer. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 452 | |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 453 | As the last step of walk_component(), step_into() will be called either |
Fox Chen | 993b892 | 2021-05-27 17:16:06 +0800 | [diff] [blame] | 454 | directly from walk_component() or from handle_dots(). It calls |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 455 | handle_mounts(), to check and handle mount points, in which a new |
Fox Chen | 084c868 | 2021-05-27 17:16:07 +0800 | [diff] [blame] | 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 |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 459 | a symbolic link, step_into() calls pick_link() to deal with it, |
Fox Chen | 084c868 | 2021-05-27 17:16:07 +0800 | [diff] [blame] | 460 | otherwise it installs the new ``struct path`` in the ``struct nameidata``, and |
| 461 | drops the unneeded references. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 | |
| 468 | Handling the final component |
| 469 | ---------------------------- |
| 470 | |
| 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 |
| 474 | component remains for the caller to sort out. Those callers are |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 475 | path_lookupat(), path_parentat() and |
| 476 | path_openat() each of which handles the differing requirements of |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 477 | different system calls. |
| 478 | |
| 479 | ``path_parentat()`` is clearly the simplest - it just wraps a little bit |
| 480 | of housekeeping around ``link_path_walk()`` and returns the parent |
| 481 | directory and final component to the caller. The caller will be either |
| 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 |
| 485 | perform their operation. |
| 486 | |
| 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. |
Fox Chen | 8593d2c | 2021-05-27 17:16:08 +0800 | [diff] [blame] | 491 | It is worth noting that when flag ``LOOKUP_MOUNTPOINT`` is set, |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 492 | path_lookupat() will unset LOOKUP_JUMPED in nameidata so that in the |
| 493 | subsequent path traversal d_weak_revalidate() won't be called. |
Fox Chen | 8593d2c | 2021-05-27 17:16:08 +0800 | [diff] [blame] | 494 | This is important when unmounting a filesystem that is inaccessible, such as |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 495 | one provided by a dead NFS server. |
| 496 | |
| 497 | Finally ``path_openat()`` is used for the ``open()`` system call; it |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 498 | contains, in support functions starting with "open_last_lookups()", all the |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 499 | complexity needed to handle the different subtleties of O_CREAT (with |
| 500 | or without O_EXCL), final "``/``" characters, and trailing symbolic |
| 501 | links. We will revisit this in the final part of this series, which |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 502 | focuses on those symbolic links. "open_last_lookups()" will sometimes, but |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 503 | not always, take ``i_rwsem``, depending on what it finds. |
| 504 | |
| 505 | Each of these, or the functions which call them, need to be alert to |
| 506 | the possibility that the final component is not ``LAST_NORM``. If the |
| 507 | goal of the lookup is to create something, then any value for |
| 508 | ``last_type`` other than ``LAST_NORM`` will result in an error. For |
| 509 | example if ``path_parentat()`` reports ``LAST_DOTDOT``, then the caller |
| 510 | won't try to create that name. They also check for trailing slashes |
| 511 | by testing ``last.name[last.len]``. If there is any character beyond |
| 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 |
| 522 | ``->d_revalidate()`` dentry method to ensure that the cached information |
| 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 |
| 527 | path is aborted and retried with the "``LOOKUP_REVAL``" flag set. This |
| 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 |
| 534 | covered in greater detail in autofs.txt in the Linux documentation |
| 535 | tree, but a few notes specifically related to path lookup are in order |
| 536 | here. |
| 537 | |
Fox Chen | 993b892 | 2021-05-27 17:16:06 +0800 | [diff] [blame] | 538 | The Linux VFS has a concept of "managed" dentries. There are three |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 539 | potentially interesting things about these dentries corresponding |
| 540 | to three different flags that might be set in ``dentry->d_flags``: |
| 541 | |
| 542 | ``DCACHE_MANAGE_TRANSIT`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 543 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 544 | |
| 545 | If this flag has been set, then the filesystem has requested that the |
| 546 | ``d_manage()`` dentry operation be called before handling any possible |
| 547 | mount point. This can perform two particular services: |
| 548 | |
| 549 | It can block to avoid races. If an automount point is being |
| 550 | unmounted, the ``d_manage()`` function will usually wait for that |
| 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 |
| 557 | processing. That server process can identify itself to the ``autofs`` |
| 558 | filesystem, which will then give it a special pass through |
| 559 | ``d_manage()`` by returning ``-EISDIR``. |
| 560 | |
| 561 | ``DCACHE_MOUNTED`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 562 | ~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 | |
| 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). |
| 573 | |
| 574 | ``DCACHE_NEED_AUTOMOUNT`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 575 | ~~~~~~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 576 | |
| 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 |
| 579 | operation to be called. |
| 580 | |
| 581 | The ``d_automount()`` operation can be arbitrarily complex and may |
| 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 |
| 584 | should provide an updated ``struct path`` with new ``dentry`` and ``vfsmount``. |
| 585 | |
| 586 | In the latter case, ``finish_automount()`` will be called to safely |
| 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 |
| 643 | ``vfsmount`` and ``dentry``, and ensuring that these are still valid - |
| 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 |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 654 | clearly seen in functions like filename_lookup(), |
| 655 | filename_parentat(), |
| 656 | do_filp_open(), and do_file_open_root(). These four |
Fox Chen | 34ef75e | 2021-05-27 17:16:10 +0800 | [diff] [blame] | 657 | correspond roughly to the three ``path_*()`` functions we met earlier, |
Vegard Nossum | 87b92d4 | 2020-07-27 14:15:24 +0200 | [diff] [blame] | 658 | each of which calls ``link_path_walk()``. The ``path_*()`` functions are |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 659 | called using different mode flags until a mode is found which works. |
| 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 |
| 662 | special flag to request "REF-walk". If either of those report the |
| 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 |
| 665 | revalidated - normally entries are only revalidated if the filesystem |
| 666 | determines that they are too old to trust. |
| 667 | |
| 668 | The ``LOOKUP_RCU`` attempt may drop that flag internally and switch to |
| 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 |
| 678 | ``rcu_read_lock()`` is held for the entire time that RCU-walk is walking |
| 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 |
| 690 | sometimes takes the ``d_lock`` spinlock. These references and locks are |
| 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 |
| 700 | samples the status of a seqlock using ``read_seqcount_begin()`` or a |
| 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 |
| 703 | ``read_seqcount_retry()`` or similar. |
| 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 |
| 710 | use ``read_seqcount_retry()`` to validate that copy. |
| 711 | |
| 712 | ``read_seqcount_retry()`` not only checks the sequence number, but also |
| 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 |
| 716 | ``slow_dentry_cmp()`` which, for filesystems which do not use simple |
| 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 |
| 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 |
Vegard Nossum | 286b7e2 | 2020-07-27 14:15:25 +0200 | [diff] [blame] | 722 | instead. Notably it does *not* use ``read_seqcount_retry()``, but |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 723 | instead has a large comment explaining why the consistency guarantee |
| 724 | isn't necessary. A subsequent ``read_seqcount_retry()`` will be |
| 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 | |
| 730 | ``mount_lock`` and ``nd->m_seq`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 731 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 732 | |
| 733 | We already met the ``mount_lock`` seqlock when REF-walk used it to |
| 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 | |
| 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 |
| 739 | start of the walk and stores this initial sequence number in the |
| 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``, |
| 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 | |
| 746 | ``m_seq`` is checked (using ``read_seqretry()``) at the end of an RCU-walk |
| 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 |
| 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 |
| 751 | whole RCU-walk sequence is aborted and the path is processed again by |
| 752 | REF-walk. |
| 753 | |
| 754 | If RCU-walk finds that ``mount_lock`` hasn't changed then it can be sure |
| 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 | |
| 759 | ``dentry->d_seq`` and ``nd->seq`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 760 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 761 | |
| 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 |
| 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 |
| 770 | only accessed in ``follow_dotdot_rcu()`` which fairly trivially follows |
| 771 | the required pattern, though it does so for three different cases. |
| 772 | |
| 773 | When not at a mount point, ``d_parent`` is followed and its ``d_seq`` is |
| 774 | collected. When we are at a mount point, we instead follow the |
| 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 |
| 777 | check if we have landed on a mount point and, if so, must find that |
| 778 | mount point and follow the ``mnt->mnt_root`` link. This would imply a |
| 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 | |
| 783 | The inode pointer, stored in ``->d_inode``, is a little more |
| 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 |
| 788 | access and it is stored in the ``inode`` field of ``nameidata`` from where |
| 789 | it can be safely accessed without further validation. |
| 790 | |
| 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 |
| 794 | of the current dentry. |
| 795 | |
| 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 |
| 803 | getting a counted reference to the new dentry before dropping that for |
| 804 | the old dentry which we saw in REF-walk. |
| 805 | |
| 806 | No ``inode->i_rwsem`` or even ``rename_lock`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 807 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 808 | |
| 809 | A semaphore is a fairly heavyweight lock that can only be taken when it is |
| 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 |
| 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 |
| 815 | ``read_seqretry()`` won't validate. In either case it will drop down to |
| 816 | REF-walk mode which can take whatever locks are needed. |
| 817 | |
| 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 |
| 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 | |
| 828 | ``unlazy walk()`` and ``complete_walk()`` |
Randy Dunlap | 9f63df2 | 2019-01-06 19:19:29 -0800 | [diff] [blame] | 829 | ----------------------------------------- |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 830 | |
| 831 | That "dropping down to REF-walk" typically involves a call to |
| 832 | ``unlazy_walk()``, so named because "RCU-walk" is also sometimes |
| 833 | referred to as "lazy walk". ``unlazy_walk()`` is called when |
| 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 |
| 838 | the ``rcu_read_lock()`` is held (which forbids sleeping), if an |
| 839 | automount point is found, or in a couple of cases involving symlinks. |
| 840 | It is also called from ``complete_walk()`` when the lookup has reached |
| 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 |
| 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`` |
| 847 | seqlocks reporting a change. In these cases the relevant function |
| 848 | will return ``-ECHILD`` which will percolate up until it triggers a new |
| 849 | attempt from the top using REF-walk. |
| 850 | |
| 851 | For those cases where ``unlazy_walk()`` is an option, it essentially |
| 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, |
| 855 | it, too, aborts with ``-ECHILD``, otherwise the transition to REF-walk |
| 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 |
| 862 | all. For ``dentry->d_lockref``, it is safe to increment the reference |
| 863 | counter to get a reference unless it has been explicitly marked as |
| 864 | "dead" which involves setting the counter to ``-128``. |
| 865 | ``lockref_get_not_dead()`` achieves this. |
| 866 | |
| 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 |
| 869 | validation fails, it may *not* be safe to just drop that reference in |
| 870 | the standard way of calling ``mnt_put()`` - an unmount may have |
| 871 | progressed too far. So the code in ``legitimize_mnt()``, when it |
| 872 | finds that the reference it got might not be safe, checks the |
| 873 | ``MNT_SYNC_UMOUNT`` flag to determine if a simple ``mnt_put()`` is |
| 874 | correct, or if it should just decrement the count and pretend none of |
| 875 | this ever happened. |
| 876 | |
| 877 | Taking care in filesystems |
| 878 | -------------------------- |
| 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 |
| 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 |
| 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 |
| 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 |
| 896 | similar. |
| 897 | |
| 898 | .. _READ_ONCE: https://lwn.net/Articles/624126/ |
| 899 | |
| 900 | If the filesystem may need to revalidate dcache entries, then |
| 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 |
| 904 | when accessing fields in the dentry. This "extra care" typically |
| 905 | involves using `READ_ONCE() <READ_ONCE_>`_ to access fields, and verifying the |
| 906 | result is not NULL before using it. This pattern can be seen in |
| 907 | ``nfs_lookup_revalidate()``. |
| 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 |
| 918 | then trying REF-walk, and in places where ``unlazy_walk()`` is used to |
| 919 | switch to REF-walk for the rest of the path. We also saw it earlier |
| 920 | in ``dget_parent()`` when following a "``..``" link. It tries a quick way |
| 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 |
| 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 - |
| 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 |
Vegard Nossum | 286b7e2 | 2020-07-27 14:15:25 +0200 | [diff] [blame] | 930 | "try quickly *and carefully*, then check". The fact that checking is |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 |
| 961 | "``readlink -f``" command does, though it also edits out "``.``" and |
| 962 | "``..``" components. |
| 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 |
| 978 | successfully - the error ``ELOOP`` must be returned. Loops can be |
| 979 | detected without imposing limits, but limits are the simplest solution |
| 980 | and, given the second reason for restriction, quite sufficient. |
| 981 | |
| 982 | .. _outlined recently: http://thread.gmane.org/gmane.linux.kernel/1934390/focus=1934550 |
| 983 | |
| 984 | The second reason was `outlined recently`_ by Linus: |
| 985 | |
| 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. |
| 989 | |
| 990 | Linux imposes a limit on the length of any pathname: ``PATH_MAX``, which |
| 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 |
Fox Chen | d2d3dd5 | 2021-05-27 17:16:11 +0800 | [diff] [blame] | 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 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 997 | raised to 40 when a separate stack was implemented, so there is now |
| 998 | just the one limit. |
| 999 | |
| 1000 | The ``nameidata`` structure that we met in an earlier article contains a |
| 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 | |
| 1020 | .. _object-oriented design pattern: https://lwn.net/Articles/446317/ |
| 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 |
| 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 |
| 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, |
| 1041 | the ``i_link`` pointer in the inode is set to point to wherever the |
| 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 |
| 1047 | inode, and even an ``rcu_read_lock()`` is not sufficient to ensure that |
| 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 |
| 1057 | space to copy the symlink into can use ``GFP_ATOMIC`` to often successfully |
| 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 |
| 1060 | must return ``-ECHILD`` and ``unlazy_walk()`` will be called to return to |
| 1061 | REF-walk mode in which the filesystem is allowed to sleep. |
| 1062 | |
Fox Chen | 4a00e4b | 2021-05-27 17:16:12 +0800 | [diff] [blame] | 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 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1068 | all the data structures it references are safe to be accessed while |
Fox Chen | 671f733 | 2021-05-27 17:16:13 +0800 | [diff] [blame] | 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 |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 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. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 | |
Fox Chen | 671f733 | 2021-05-27 17:16:13 +0800 | [diff] [blame] | 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 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1081 | - the ``seq`` to allow the path to be safely switched from RCU-walk to REF-walk |
Fox Chen | 671f733 | 2021-05-27 17:16:13 +0800 | [diff] [blame] | 1082 | - the ``struct delayed_call`` for later invocation. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 | |
| 1091 | Note that, in a given stack frame, the path remnant (``name``) is not |
| 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 | |
| 1098 | The main loop in ``link_path_walk()`` iterates seamlessly over all |
| 1099 | components in the path and all of the non-final symlinks. As symlinks |
| 1100 | are processed, the ``name`` pointer is adjusted to point to a new |
| 1101 | symlink, or is restored from the stack, so that much of the loop |
| 1102 | doesn't need to notice. Getting this ``name`` variable on and off the |
| 1103 | stack is very straightforward; pushing and popping the references is |
| 1104 | a little more complex. |
| 1105 | |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1106 | When a symlink is found, walk_component() calls pick_link() via step_into() |
Fox Chen | 18edb95 | 2021-05-27 17:16:14 +0800 | [diff] [blame] | 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 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1110 | the path is found (i.e. ``*name`` is ``'\0'``) the old ``name`` is restored |
| 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 |
| 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 |
| 1123 | old symlink as it walks that last component. So it is quite |
| 1124 | convenient for ``walk_component()`` to release the old symlink and pop |
| 1125 | the references just before pushing the reference information for the |
Fox Chen | de9414a | 2021-05-27 17:16:15 +0800 | [diff] [blame] | 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. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1133 | |
| 1134 | Symlinks with no final component |
| 1135 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 1136 | |
| 1137 | A pair of special-case symlinks deserve a little further explanation. |
| 1138 | Both result in a new ``struct path`` (with mount and dentry) being set |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1139 | up in the ``nameidata``, and result in pick_link() returning ``NULL``. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1140 | |
| 1141 | The more obvious case is a symlink to "``/``". All symlinks starting |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1142 | with "``/``" are detected in pick_link() which resets the ``nameidata`` |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1143 | to point to the effective filesystem root. If the symlink only |
| 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 |
| 1146 | the stack frame discarded. |
| 1147 | |
| 1148 | The other case involves things in ``/proc`` that look like symlinks but |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 1149 | aren't really (and are therefore commonly referred to as "magic-links"):: |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1150 | |
| 1151 | $ ls -l /proc/self/fd/1 |
| 1152 | lrwx------ 1 neilb neilb 64 Jun 13 10:19 /proc/self/fd/1 -> /dev/pts/4 |
| 1153 | |
| 1154 | Every open file descriptor in any process is represented in ``/proc`` by |
| 1155 | something that looks like a symlink. It is really a reference to the |
| 1156 | target file, not just the name of it. When you ``readlink`` these |
| 1157 | objects you get a name that might refer to the same file - unless it |
| 1158 | has been unlinked or mounted over. When ``walk_component()`` follows |
Fox Chen | 3c1be84 | 2021-05-27 17:16:16 +0800 | [diff] [blame] | 1159 | one of these, the ``->get_link()`` method in "procfs" doesn't return |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1160 | a string name, but instead calls nd_jump_link() which updates the |
Fox Chen | 3c1be84 | 2021-05-27 17:16:16 +0800 | [diff] [blame] | 1161 | ``nameidata`` in place to point to that target. ``->get_link()`` then |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1162 | returns ``NULL``. Again there is no final component and pick_link() |
Fox Chen | 3c1be84 | 2021-05-27 17:16:16 +0800 | [diff] [blame] | 1163 | returns ``NULL``. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1164 | |
| 1165 | Following the symlink in the final component |
| 1166 | -------------------------------------------- |
| 1167 | |
| 1168 | All this leads to ``link_path_walk()`` walking down every component, and |
| 1169 | following all symbolic links it finds, until it reaches the final |
| 1170 | component. This is just returned in the ``last`` field of ``nameidata``. |
| 1171 | For some callers, this is all they need; they want to create that |
| 1172 | ``last`` name if it doesn't exist or give an error if it does. Other |
| 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 |
| 1176 | potentially need to call ``link_path_walk()`` again and again on |
| 1177 | successive symlinks until one is found that doesn't point to another |
| 1178 | symlink. |
| 1179 | |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 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 |
Fox Chen | 71e0a67 | 2021-05-27 17:16:09 +0800 | [diff] [blame] | 1185 | return the path so that the loop repeats, calling |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1186 | link_path_walk() again. This could loop as many as 40 times if the last |
Fox Chen | 71e0a67 | 2021-05-27 17:16:09 +0800 | [diff] [blame] | 1187 | component of each symlink is another symlink. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1188 | |
Fox Chen | 71e0a67 | 2021-05-27 17:16:09 +0800 | [diff] [blame] | 1189 | Of the various functions that examine the final component, |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 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(). |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1193 | |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1194 | Explaining open_last_lookups() and do_open() completely is beyond the scope |
Fox Chen | 71e0a67 | 2021-05-27 17:16:09 +0800 | [diff] [blame] | 1195 | of this article, but a few highlights should help those interested in exploring |
| 1196 | the code. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1197 | |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1198 | 1. Rather than just finding the target file, do_open() is used after |
| 1199 | open_last_lookup() to open |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 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 |
Fox Chen | ef4aa53 | 2021-05-27 17:16:17 +0800 | [diff] [blame] | 1203 | will perform the separate ``i_op->lookup()`` and ``i_op->create()`` steps |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1204 | directly. In the later case the actual "open" of this newly found or |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1205 | created file will be performed by vfs_open(), just as if the name |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1206 | were found in the dcache. |
| 1207 | |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 1208 | 2. vfs_open() can fail with ``-EOPENSTALE`` if the cached information |
Fox Chen | ef4aa53 | 2021-05-27 17:16:17 +0800 | [diff] [blame] | 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. |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1212 | |
| 1213 | 3. An open with O_CREAT **does** follow a symlink in the final component, |
| 1214 | unlike other creation system calls (like ``mkdir``). So the sequence:: |
| 1215 | |
| 1216 | ln -s bar /tmp/foo |
| 1217 | echo hello > /tmp/foo |
| 1218 | |
| 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 |
Fox Chen | 8943474 | 2021-05-27 17:16:18 +0800 | [diff] [blame] | 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 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1223 | open process continues on the symlink that was found. |
| 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 |
| 1237 | time", or "``atime``". Passing through a directory to access a file |
| 1238 | within is not considered to be an access for the purposes of |
| 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()``) |
| 1241 | and looking up a symlink on the way to some other destination can |
| 1242 | update the atime on that symlink. |
| 1243 | |
Alexander A. Klimov | c69f22f2 | 2020-06-21 15:35:52 +0200 | [diff] [blame] | 1244 | .. _clearest statement: https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_08 |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1245 | |
| 1246 | It is not clear why this is the case; POSIX has little to say on the |
| 1247 | subject. The `clearest statement`_ is that, if a particular implementation |
| 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 | |
| 1253 | .. _Linux 1.3.87: https://git.kernel.org/cgit/linux/kernel/git/history/history.git/diff/fs/ext2/symlink.c?id=f806c6db77b8eaa6e00dcfb6b567706feae8dbb8 |
| 1254 | |
| 1255 | An examination of history shows that prior to `Linux 1.3.87`_, the ext2 |
| 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 |
| 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 |
| 1265 | being changed (and symlinks never change once created). Even without |
| 1266 | ``relatime``, many filesystems record ``atime`` with a one-second |
| 1267 | granularity, so only one update per second is required. |
| 1268 | |
| 1269 | It is easy to test if an ``atime`` update is needed while in RCU-walk |
| 1270 | mode and, if it isn't, the update can be skipped and RCU-walk mode |
| 1271 | continues. Only when an ``atime`` update is actually required does the |
| 1272 | path walk drop down to REF-walk. All of this is handled in the |
| 1273 | ``get_link()`` function. |
| 1274 | |
| 1275 | A few flags |
| 1276 | ----------- |
| 1277 | |
| 1278 | A suitable way to wrap up this tour of pathname walking is to list |
| 1279 | the various flags that can be stored in the ``nameidata`` to guide the |
| 1280 | lookup process. Many of these are only meaningful on the final |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 | |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1284 | And then there is ``LOOKUP_EMPTY``, which doesn't fit conceptually with |
| 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 | |
| 1289 | Global state flags |
| 1290 | ~~~~~~~~~~~~~~~~~~ |
| 1291 | |
| 1292 | We have already met two global state flags: ``LOOKUP_RCU`` and |
| 1293 | ``LOOKUP_REVAL``. These select between one of three overall approaches |
| 1294 | to lookup: RCU-walk, REF-walk, and REF-walk with forced revalidation. |
| 1295 | |
| 1296 | ``LOOKUP_PARENT`` indicates that the final component hasn't been reached |
| 1297 | yet. This is primarily used to tell the audit subsystem the full |
| 1298 | context of a particular access being audited. |
| 1299 | |
Al Viro | bcba1e7 | 2021-04-01 22:03:41 -0400 | [diff] [blame] | 1300 | ``ND_ROOT_PRESET`` indicates that the ``root`` field in the ``nameidata`` was |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1301 | provided by the caller, so it shouldn't be released when it is no |
| 1302 | longer needed. |
| 1303 | |
Al Viro | bcba1e7 | 2021-04-01 22:03:41 -0400 | [diff] [blame] | 1304 | ``ND_JUMPED`` means that the current dentry was chosen not because |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1305 | it had the right name but for some other reason. This happens when |
| 1306 | following "``..``", following a symlink to ``/``, crossing a mount point |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 |
Al Viro | bcba1e7 | 2021-04-01 22:03:41 -0400 | [diff] [blame] | 1311 | ``ND_JUMPED`` is set when the look completes - which may be at the |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1312 | final component or, when creating, unlinking, or renaming, at the penultimate component. |
| 1313 | |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 |
Randy Dunlap | 9b12355 | 2020-07-03 14:43:23 -0700 | [diff] [blame] | 1344 | were the filesystem root. ``nd_jump_root()`` brings the resolution back to |
Aleksa Sarai | b55eef8 | 2019-12-07 01:13:38 +1100 | [diff] [blame] | 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 | |
NeilBrown | 7bbfd9a | 2018-12-05 10:02:51 +1100 | [diff] [blame] | 1349 | Final-component flags |
| 1350 | ~~~~~~~~~~~~~~~~~~~~~ |
| 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 | |
| 1356 | ``LOOKUP_AUTOMOUNT`` ensures that, if the final component is an automount |
| 1357 | point, then the mount is triggered. Some operations would trigger it |
| 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``". |
| 1362 | |
| 1363 | ``LOOKUP_FOLLOW`` has a similar function to ``LOOKUP_AUTOMOUNT`` but for |
| 1364 | symlinks. Some system calls set or clear it implicitly, while |
| 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. |
| 1368 | |
| 1369 | ``LOOKUP_DIRECTORY`` insists that the final component is a directory. |
| 1370 | Various callers set this and it is also set when the final component |
| 1371 | is found to be followed by a slash. |
| 1372 | |
| 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()`` |
| 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. |
| 1378 | These flags were previously useful for ``->lookup()`` too but with the |
| 1379 | introduction of ``->atomic_open()`` they are less relevant there. |
| 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. |