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