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