xref: /linux/fs/dcache.c (revision 6af91e3d2cfc8bb579b1aa2d22cd91f8c34acdf6)
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * fs/dcache.c
4  *
5  * Complete reimplementation
6  * (C) 1997 Thomas Schoebel-Theuer,
7  * with heavy changes by Linus Torvalds
8  */
9 
10 /*
11  * Notes on the allocation strategy:
12  *
13  * The dcache is a master of the icache - whenever a dcache entry
14  * exists, the inode will always exist. "iput()" is done either when
15  * the dcache entry is deleted or garbage collected.
16  */
17 
18 #include <linux/ratelimit.h>
19 #include <linux/string.h>
20 #include <linux/mm.h>
21 #include <linux/fs.h>
22 #include <linux/fscrypt.h>
23 #include <linux/fsnotify.h>
24 #include <linux/slab.h>
25 #include <linux/init.h>
26 #include <linux/hash.h>
27 #include <linux/cache.h>
28 #include <linux/export.h>
29 #include <linux/security.h>
30 #include <linux/seqlock.h>
31 #include <linux/memblock.h>
32 #include <linux/bit_spinlock.h>
33 #include <linux/rculist_bl.h>
34 #include <linux/list_lru.h>
35 #include "internal.h"
36 #include "mount.h"
37 
38 #include <asm/runtime-const.h>
39 
40 /*
41  * Usage:
42  * dcache->d_inode->i_lock protects:
43  *   - i_dentry, d_u.d_alias, d_inode of aliases
44  * dcache_hash_bucket lock protects:
45  *   - the dcache hash table
46  * s_roots bl list spinlock protects:
47  *   - the s_roots list (see __d_drop)
48  * dentry->d_sb->s_dentry_lru_lock protects:
49  *   - the dcache lru lists and counters
50  * d_lock protects:
51  *   - d_flags
52  *   - d_name
53  *   - d_lru
54  *   - d_count
55  *   - d_unhashed()
56  *   - d_parent and d_chilren
57  *   - childrens' d_sib and d_parent
58  *   - d_u.d_alias, d_inode
59  *
60  * Ordering:
61  * dentry->d_inode->i_lock
62  *   dentry->d_lock
63  *     dentry->d_sb->s_dentry_lru_lock
64  *     dcache_hash_bucket lock
65  *     s_roots lock
66  *
67  * If there is an ancestor relationship:
68  * dentry->d_parent->...->d_parent->d_lock
69  *   ...
70  *     dentry->d_parent->d_lock
71  *       dentry->d_lock
72  *
73  * If no ancestor relationship:
74  * arbitrary, since it's serialized on rename_lock
75  */
76 int sysctl_vfs_cache_pressure __read_mostly = 100;
77 EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);
78 
79 __cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
80 
81 EXPORT_SYMBOL(rename_lock);
82 
83 static struct kmem_cache *dentry_cache __ro_after_init;
84 
85 const struct qstr empty_name = QSTR_INIT("", 0);
86 EXPORT_SYMBOL(empty_name);
87 const struct qstr slash_name = QSTR_INIT("/", 1);
88 EXPORT_SYMBOL(slash_name);
89 const struct qstr dotdot_name = QSTR_INIT("..", 2);
90 EXPORT_SYMBOL(dotdot_name);
91 
92 /*
93  * This is the single most critical data structure when it comes
94  * to the dcache: the hashtable for lookups. Somebody should try
95  * to make this good - I've just made it work.
96  *
97  * This hash-function tries to avoid losing too many bits of hash
98  * information, yet avoid using a prime hash-size or similar.
99  */
100 
101 static unsigned int d_hash_shift __ro_after_init;
102 
103 static struct hlist_bl_head *dentry_hashtable __ro_after_init;
104 
105 static inline struct hlist_bl_head *d_hash(unsigned long hashlen)
106 {
107 	return runtime_const_ptr(dentry_hashtable) +
108 		runtime_const_shift_right_32(hashlen, d_hash_shift);
109 }
110 
111 #define IN_LOOKUP_SHIFT 10
112 static struct hlist_bl_head in_lookup_hashtable[1 << IN_LOOKUP_SHIFT];
113 
114 static inline struct hlist_bl_head *in_lookup_hash(const struct dentry *parent,
115 					unsigned int hash)
116 {
117 	hash += (unsigned long) parent / L1_CACHE_BYTES;
118 	return in_lookup_hashtable + hash_32(hash, IN_LOOKUP_SHIFT);
119 }
120 
121 struct dentry_stat_t {
122 	long nr_dentry;
123 	long nr_unused;
124 	long age_limit;		/* age in seconds */
125 	long want_pages;	/* pages requested by system */
126 	long nr_negative;	/* # of unused negative dentries */
127 	long dummy;		/* Reserved for future use */
128 };
129 
130 static DEFINE_PER_CPU(long, nr_dentry);
131 static DEFINE_PER_CPU(long, nr_dentry_unused);
132 static DEFINE_PER_CPU(long, nr_dentry_negative);
133 
134 #if defined(CONFIG_SYSCTL) && defined(CONFIG_PROC_FS)
135 /* Statistics gathering. */
136 static struct dentry_stat_t dentry_stat = {
137 	.age_limit = 45,
138 };
139 
140 /*
141  * Here we resort to our own counters instead of using generic per-cpu counters
142  * for consistency with what the vfs inode code does. We are expected to harvest
143  * better code and performance by having our own specialized counters.
144  *
145  * Please note that the loop is done over all possible CPUs, not over all online
146  * CPUs. The reason for this is that we don't want to play games with CPUs going
147  * on and off. If one of them goes off, we will just keep their counters.
148  *
149  * glommer: See cffbc8a for details, and if you ever intend to change this,
150  * please update all vfs counters to match.
151  */
152 static long get_nr_dentry(void)
153 {
154 	int i;
155 	long sum = 0;
156 	for_each_possible_cpu(i)
157 		sum += per_cpu(nr_dentry, i);
158 	return sum < 0 ? 0 : sum;
159 }
160 
161 static long get_nr_dentry_unused(void)
162 {
163 	int i;
164 	long sum = 0;
165 	for_each_possible_cpu(i)
166 		sum += per_cpu(nr_dentry_unused, i);
167 	return sum < 0 ? 0 : sum;
168 }
169 
170 static long get_nr_dentry_negative(void)
171 {
172 	int i;
173 	long sum = 0;
174 
175 	for_each_possible_cpu(i)
176 		sum += per_cpu(nr_dentry_negative, i);
177 	return sum < 0 ? 0 : sum;
178 }
179 
180 static int proc_nr_dentry(const struct ctl_table *table, int write, void *buffer,
181 			  size_t *lenp, loff_t *ppos)
182 {
183 	dentry_stat.nr_dentry = get_nr_dentry();
184 	dentry_stat.nr_unused = get_nr_dentry_unused();
185 	dentry_stat.nr_negative = get_nr_dentry_negative();
186 	return proc_doulongvec_minmax(table, write, buffer, lenp, ppos);
187 }
188 
189 static struct ctl_table fs_dcache_sysctls[] = {
190 	{
191 		.procname	= "dentry-state",
192 		.data		= &dentry_stat,
193 		.maxlen		= 6*sizeof(long),
194 		.mode		= 0444,
195 		.proc_handler	= proc_nr_dentry,
196 	},
197 };
198 
199 static int __init init_fs_dcache_sysctls(void)
200 {
201 	register_sysctl_init("fs", fs_dcache_sysctls);
202 	return 0;
203 }
204 fs_initcall(init_fs_dcache_sysctls);
205 #endif
206 
207 /*
208  * Compare 2 name strings, return 0 if they match, otherwise non-zero.
209  * The strings are both count bytes long, and count is non-zero.
210  */
211 #ifdef CONFIG_DCACHE_WORD_ACCESS
212 
213 #include <asm/word-at-a-time.h>
214 /*
215  * NOTE! 'cs' and 'scount' come from a dentry, so it has a
216  * aligned allocation for this particular component. We don't
217  * strictly need the load_unaligned_zeropad() safety, but it
218  * doesn't hurt either.
219  *
220  * In contrast, 'ct' and 'tcount' can be from a pathname, and do
221  * need the careful unaligned handling.
222  */
223 static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
224 {
225 	unsigned long a,b,mask;
226 
227 	for (;;) {
228 		a = read_word_at_a_time(cs);
229 		b = load_unaligned_zeropad(ct);
230 		if (tcount < sizeof(unsigned long))
231 			break;
232 		if (unlikely(a != b))
233 			return 1;
234 		cs += sizeof(unsigned long);
235 		ct += sizeof(unsigned long);
236 		tcount -= sizeof(unsigned long);
237 		if (!tcount)
238 			return 0;
239 	}
240 	mask = bytemask_from_count(tcount);
241 	return unlikely(!!((a ^ b) & mask));
242 }
243 
244 #else
245 
246 static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
247 {
248 	do {
249 		if (*cs != *ct)
250 			return 1;
251 		cs++;
252 		ct++;
253 		tcount--;
254 	} while (tcount);
255 	return 0;
256 }
257 
258 #endif
259 
260 static inline int dentry_cmp(const struct dentry *dentry, const unsigned char *ct, unsigned tcount)
261 {
262 	/*
263 	 * Be careful about RCU walk racing with rename:
264 	 * use 'READ_ONCE' to fetch the name pointer.
265 	 *
266 	 * NOTE! Even if a rename will mean that the length
267 	 * was not loaded atomically, we don't care. The
268 	 * RCU walk will check the sequence count eventually,
269 	 * and catch it. And we won't overrun the buffer,
270 	 * because we're reading the name pointer atomically,
271 	 * and a dentry name is guaranteed to be properly
272 	 * terminated with a NUL byte.
273 	 *
274 	 * End result: even if 'len' is wrong, we'll exit
275 	 * early because the data cannot match (there can
276 	 * be no NUL in the ct/tcount data)
277 	 */
278 	const unsigned char *cs = READ_ONCE(dentry->d_name.name);
279 
280 	return dentry_string_cmp(cs, ct, tcount);
281 }
282 
283 struct external_name {
284 	union {
285 		atomic_t count;
286 		struct rcu_head head;
287 	} u;
288 	unsigned char name[];
289 };
290 
291 static inline struct external_name *external_name(struct dentry *dentry)
292 {
293 	return container_of(dentry->d_name.name, struct external_name, name[0]);
294 }
295 
296 static void __d_free(struct rcu_head *head)
297 {
298 	struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);
299 
300 	kmem_cache_free(dentry_cache, dentry);
301 }
302 
303 static void __d_free_external(struct rcu_head *head)
304 {
305 	struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);
306 	kfree(external_name(dentry));
307 	kmem_cache_free(dentry_cache, dentry);
308 }
309 
310 static inline int dname_external(const struct dentry *dentry)
311 {
312 	return dentry->d_name.name != dentry->d_iname;
313 }
314 
315 void take_dentry_name_snapshot(struct name_snapshot *name, struct dentry *dentry)
316 {
317 	spin_lock(&dentry->d_lock);
318 	name->name = dentry->d_name;
319 	if (unlikely(dname_external(dentry))) {
320 		atomic_inc(&external_name(dentry)->u.count);
321 	} else {
322 		memcpy(name->inline_name, dentry->d_iname,
323 		       dentry->d_name.len + 1);
324 		name->name.name = name->inline_name;
325 	}
326 	spin_unlock(&dentry->d_lock);
327 }
328 EXPORT_SYMBOL(take_dentry_name_snapshot);
329 
330 void release_dentry_name_snapshot(struct name_snapshot *name)
331 {
332 	if (unlikely(name->name.name != name->inline_name)) {
333 		struct external_name *p;
334 		p = container_of(name->name.name, struct external_name, name[0]);
335 		if (unlikely(atomic_dec_and_test(&p->u.count)))
336 			kfree_rcu(p, u.head);
337 	}
338 }
339 EXPORT_SYMBOL(release_dentry_name_snapshot);
340 
341 static inline void __d_set_inode_and_type(struct dentry *dentry,
342 					  struct inode *inode,
343 					  unsigned type_flags)
344 {
345 	unsigned flags;
346 
347 	dentry->d_inode = inode;
348 	flags = READ_ONCE(dentry->d_flags);
349 	flags &= ~DCACHE_ENTRY_TYPE;
350 	flags |= type_flags;
351 	smp_store_release(&dentry->d_flags, flags);
352 }
353 
354 static inline void __d_clear_type_and_inode(struct dentry *dentry)
355 {
356 	unsigned flags = READ_ONCE(dentry->d_flags);
357 
358 	flags &= ~DCACHE_ENTRY_TYPE;
359 	WRITE_ONCE(dentry->d_flags, flags);
360 	dentry->d_inode = NULL;
361 	/*
362 	 * The negative counter only tracks dentries on the LRU. Don't inc if
363 	 * d_lru is on another list.
364 	 */
365 	if ((flags & (DCACHE_LRU_LIST|DCACHE_SHRINK_LIST)) == DCACHE_LRU_LIST)
366 		this_cpu_inc(nr_dentry_negative);
367 }
368 
369 static void dentry_free(struct dentry *dentry)
370 {
371 	WARN_ON(!hlist_unhashed(&dentry->d_u.d_alias));
372 	if (unlikely(dname_external(dentry))) {
373 		struct external_name *p = external_name(dentry);
374 		if (likely(atomic_dec_and_test(&p->u.count))) {
375 			call_rcu(&dentry->d_u.d_rcu, __d_free_external);
376 			return;
377 		}
378 	}
379 	/* if dentry was never visible to RCU, immediate free is OK */
380 	if (dentry->d_flags & DCACHE_NORCU)
381 		__d_free(&dentry->d_u.d_rcu);
382 	else
383 		call_rcu(&dentry->d_u.d_rcu, __d_free);
384 }
385 
386 /*
387  * Release the dentry's inode, using the filesystem
388  * d_iput() operation if defined.
389  */
390 static void dentry_unlink_inode(struct dentry * dentry)
391 	__releases(dentry->d_lock)
392 	__releases(dentry->d_inode->i_lock)
393 {
394 	struct inode *inode = dentry->d_inode;
395 
396 	raw_write_seqcount_begin(&dentry->d_seq);
397 	__d_clear_type_and_inode(dentry);
398 	hlist_del_init(&dentry->d_u.d_alias);
399 	raw_write_seqcount_end(&dentry->d_seq);
400 	spin_unlock(&dentry->d_lock);
401 	spin_unlock(&inode->i_lock);
402 	if (!inode->i_nlink)
403 		fsnotify_inoderemove(inode);
404 	if (dentry->d_op && dentry->d_op->d_iput)
405 		dentry->d_op->d_iput(dentry, inode);
406 	else
407 		iput(inode);
408 }
409 
410 /*
411  * The DCACHE_LRU_LIST bit is set whenever the 'd_lru' entry
412  * is in use - which includes both the "real" per-superblock
413  * LRU list _and_ the DCACHE_SHRINK_LIST use.
414  *
415  * The DCACHE_SHRINK_LIST bit is set whenever the dentry is
416  * on the shrink list (ie not on the superblock LRU list).
417  *
418  * The per-cpu "nr_dentry_unused" counters are updated with
419  * the DCACHE_LRU_LIST bit.
420  *
421  * The per-cpu "nr_dentry_negative" counters are only updated
422  * when deleted from or added to the per-superblock LRU list, not
423  * from/to the shrink list. That is to avoid an unneeded dec/inc
424  * pair when moving from LRU to shrink list in select_collect().
425  *
426  * These helper functions make sure we always follow the
427  * rules. d_lock must be held by the caller.
428  */
429 #define D_FLAG_VERIFY(dentry,x) WARN_ON_ONCE(((dentry)->d_flags & (DCACHE_LRU_LIST | DCACHE_SHRINK_LIST)) != (x))
430 static void d_lru_add(struct dentry *dentry)
431 {
432 	D_FLAG_VERIFY(dentry, 0);
433 	dentry->d_flags |= DCACHE_LRU_LIST;
434 	this_cpu_inc(nr_dentry_unused);
435 	if (d_is_negative(dentry))
436 		this_cpu_inc(nr_dentry_negative);
437 	WARN_ON_ONCE(!list_lru_add_obj(
438 			&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
439 }
440 
441 static void d_lru_del(struct dentry *dentry)
442 {
443 	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
444 	dentry->d_flags &= ~DCACHE_LRU_LIST;
445 	this_cpu_dec(nr_dentry_unused);
446 	if (d_is_negative(dentry))
447 		this_cpu_dec(nr_dentry_negative);
448 	WARN_ON_ONCE(!list_lru_del_obj(
449 			&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
450 }
451 
452 static void d_shrink_del(struct dentry *dentry)
453 {
454 	D_FLAG_VERIFY(dentry, DCACHE_SHRINK_LIST | DCACHE_LRU_LIST);
455 	list_del_init(&dentry->d_lru);
456 	dentry->d_flags &= ~(DCACHE_SHRINK_LIST | DCACHE_LRU_LIST);
457 	this_cpu_dec(nr_dentry_unused);
458 }
459 
460 static void d_shrink_add(struct dentry *dentry, struct list_head *list)
461 {
462 	D_FLAG_VERIFY(dentry, 0);
463 	list_add(&dentry->d_lru, list);
464 	dentry->d_flags |= DCACHE_SHRINK_LIST | DCACHE_LRU_LIST;
465 	this_cpu_inc(nr_dentry_unused);
466 }
467 
468 /*
469  * These can only be called under the global LRU lock, ie during the
470  * callback for freeing the LRU list. "isolate" removes it from the
471  * LRU lists entirely, while shrink_move moves it to the indicated
472  * private list.
473  */
474 static void d_lru_isolate(struct list_lru_one *lru, struct dentry *dentry)
475 {
476 	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
477 	dentry->d_flags &= ~DCACHE_LRU_LIST;
478 	this_cpu_dec(nr_dentry_unused);
479 	if (d_is_negative(dentry))
480 		this_cpu_dec(nr_dentry_negative);
481 	list_lru_isolate(lru, &dentry->d_lru);
482 }
483 
484 static void d_lru_shrink_move(struct list_lru_one *lru, struct dentry *dentry,
485 			      struct list_head *list)
486 {
487 	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
488 	dentry->d_flags |= DCACHE_SHRINK_LIST;
489 	if (d_is_negative(dentry))
490 		this_cpu_dec(nr_dentry_negative);
491 	list_lru_isolate_move(lru, &dentry->d_lru, list);
492 }
493 
494 static void ___d_drop(struct dentry *dentry)
495 {
496 	struct hlist_bl_head *b;
497 	/*
498 	 * Hashed dentries are normally on the dentry hashtable,
499 	 * with the exception of those newly allocated by
500 	 * d_obtain_root, which are always IS_ROOT:
501 	 */
502 	if (unlikely(IS_ROOT(dentry)))
503 		b = &dentry->d_sb->s_roots;
504 	else
505 		b = d_hash(dentry->d_name.hash);
506 
507 	hlist_bl_lock(b);
508 	__hlist_bl_del(&dentry->d_hash);
509 	hlist_bl_unlock(b);
510 }
511 
512 void __d_drop(struct dentry *dentry)
513 {
514 	if (!d_unhashed(dentry)) {
515 		___d_drop(dentry);
516 		dentry->d_hash.pprev = NULL;
517 		write_seqcount_invalidate(&dentry->d_seq);
518 	}
519 }
520 EXPORT_SYMBOL(__d_drop);
521 
522 /**
523  * d_drop - drop a dentry
524  * @dentry: dentry to drop
525  *
526  * d_drop() unhashes the entry from the parent dentry hashes, so that it won't
527  * be found through a VFS lookup any more. Note that this is different from
528  * deleting the dentry - d_delete will try to mark the dentry negative if
529  * possible, giving a successful _negative_ lookup, while d_drop will
530  * just make the cache lookup fail.
531  *
532  * d_drop() is used mainly for stuff that wants to invalidate a dentry for some
533  * reason (NFS timeouts or autofs deletes).
534  *
535  * __d_drop requires dentry->d_lock
536  *
537  * ___d_drop doesn't mark dentry as "unhashed"
538  * (dentry->d_hash.pprev will be LIST_POISON2, not NULL).
539  */
540 void d_drop(struct dentry *dentry)
541 {
542 	spin_lock(&dentry->d_lock);
543 	__d_drop(dentry);
544 	spin_unlock(&dentry->d_lock);
545 }
546 EXPORT_SYMBOL(d_drop);
547 
548 static inline void dentry_unlist(struct dentry *dentry)
549 {
550 	struct dentry *next;
551 	/*
552 	 * Inform d_walk() and shrink_dentry_list() that we are no longer
553 	 * attached to the dentry tree
554 	 */
555 	dentry->d_flags |= DCACHE_DENTRY_KILLED;
556 	if (unlikely(hlist_unhashed(&dentry->d_sib)))
557 		return;
558 	__hlist_del(&dentry->d_sib);
559 	/*
560 	 * Cursors can move around the list of children.  While we'd been
561 	 * a normal list member, it didn't matter - ->d_sib.next would've
562 	 * been updated.  However, from now on it won't be and for the
563 	 * things like d_walk() it might end up with a nasty surprise.
564 	 * Normally d_walk() doesn't care about cursors moving around -
565 	 * ->d_lock on parent prevents that and since a cursor has no children
566 	 * of its own, we get through it without ever unlocking the parent.
567 	 * There is one exception, though - if we ascend from a child that
568 	 * gets killed as soon as we unlock it, the next sibling is found
569 	 * using the value left in its ->d_sib.next.  And if _that_
570 	 * pointed to a cursor, and cursor got moved (e.g. by lseek())
571 	 * before d_walk() regains parent->d_lock, we'll end up skipping
572 	 * everything the cursor had been moved past.
573 	 *
574 	 * Solution: make sure that the pointer left behind in ->d_sib.next
575 	 * points to something that won't be moving around.  I.e. skip the
576 	 * cursors.
577 	 */
578 	while (dentry->d_sib.next) {
579 		next = hlist_entry(dentry->d_sib.next, struct dentry, d_sib);
580 		if (likely(!(next->d_flags & DCACHE_DENTRY_CURSOR)))
581 			break;
582 		dentry->d_sib.next = next->d_sib.next;
583 	}
584 }
585 
586 static struct dentry *__dentry_kill(struct dentry *dentry)
587 {
588 	struct dentry *parent = NULL;
589 	bool can_free = true;
590 
591 	/*
592 	 * The dentry is now unrecoverably dead to the world.
593 	 */
594 	lockref_mark_dead(&dentry->d_lockref);
595 
596 	/*
597 	 * inform the fs via d_prune that this dentry is about to be
598 	 * unhashed and destroyed.
599 	 */
600 	if (dentry->d_flags & DCACHE_OP_PRUNE)
601 		dentry->d_op->d_prune(dentry);
602 
603 	if (dentry->d_flags & DCACHE_LRU_LIST) {
604 		if (!(dentry->d_flags & DCACHE_SHRINK_LIST))
605 			d_lru_del(dentry);
606 	}
607 	/* if it was on the hash then remove it */
608 	__d_drop(dentry);
609 	if (dentry->d_inode)
610 		dentry_unlink_inode(dentry);
611 	else
612 		spin_unlock(&dentry->d_lock);
613 	this_cpu_dec(nr_dentry);
614 	if (dentry->d_op && dentry->d_op->d_release)
615 		dentry->d_op->d_release(dentry);
616 
617 	cond_resched();
618 	/* now that it's negative, ->d_parent is stable */
619 	if (!IS_ROOT(dentry)) {
620 		parent = dentry->d_parent;
621 		spin_lock(&parent->d_lock);
622 	}
623 	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
624 	dentry_unlist(dentry);
625 	if (dentry->d_flags & DCACHE_SHRINK_LIST)
626 		can_free = false;
627 	spin_unlock(&dentry->d_lock);
628 	if (likely(can_free))
629 		dentry_free(dentry);
630 	if (parent && --parent->d_lockref.count) {
631 		spin_unlock(&parent->d_lock);
632 		return NULL;
633 	}
634 	return parent;
635 }
636 
637 /*
638  * Lock a dentry for feeding it to __dentry_kill().
639  * Called under rcu_read_lock() and dentry->d_lock; the former
640  * guarantees that nothing we access will be freed under us.
641  * Note that dentry is *not* protected from concurrent dentry_kill(),
642  * d_delete(), etc.
643  *
644  * Return false if dentry is busy.  Otherwise, return true and have
645  * that dentry's inode locked.
646  */
647 
648 static bool lock_for_kill(struct dentry *dentry)
649 {
650 	struct inode *inode = dentry->d_inode;
651 
652 	if (unlikely(dentry->d_lockref.count))
653 		return false;
654 
655 	if (!inode || likely(spin_trylock(&inode->i_lock)))
656 		return true;
657 
658 	do {
659 		spin_unlock(&dentry->d_lock);
660 		spin_lock(&inode->i_lock);
661 		spin_lock(&dentry->d_lock);
662 		if (likely(inode == dentry->d_inode))
663 			break;
664 		spin_unlock(&inode->i_lock);
665 		inode = dentry->d_inode;
666 	} while (inode);
667 	if (likely(!dentry->d_lockref.count))
668 		return true;
669 	if (inode)
670 		spin_unlock(&inode->i_lock);
671 	return false;
672 }
673 
674 /*
675  * Decide if dentry is worth retaining.  Usually this is called with dentry
676  * locked; if not locked, we are more limited and might not be able to tell
677  * without a lock.  False in this case means "punt to locked path and recheck".
678  *
679  * In case we aren't locked, these predicates are not "stable". However, it is
680  * sufficient that at some point after we dropped the reference the dentry was
681  * hashed and the flags had the proper value. Other dentry users may have
682  * re-gotten a reference to the dentry and change that, but our work is done -
683  * we can leave the dentry around with a zero refcount.
684  */
685 static inline bool retain_dentry(struct dentry *dentry, bool locked)
686 {
687 	unsigned int d_flags;
688 
689 	smp_rmb();
690 	d_flags = READ_ONCE(dentry->d_flags);
691 
692 	// Unreachable? Nobody would be able to look it up, no point retaining
693 	if (unlikely(d_unhashed(dentry)))
694 		return false;
695 
696 	// Same if it's disconnected
697 	if (unlikely(d_flags & DCACHE_DISCONNECTED))
698 		return false;
699 
700 	// ->d_delete() might tell us not to bother, but that requires
701 	// ->d_lock; can't decide without it
702 	if (unlikely(d_flags & DCACHE_OP_DELETE)) {
703 		if (!locked || dentry->d_op->d_delete(dentry))
704 			return false;
705 	}
706 
707 	// Explicitly told not to bother
708 	if (unlikely(d_flags & DCACHE_DONTCACHE))
709 		return false;
710 
711 	// At this point it looks like we ought to keep it.  We also might
712 	// need to do something - put it on LRU if it wasn't there already
713 	// and mark it referenced if it was on LRU, but not marked yet.
714 	// Unfortunately, both actions require ->d_lock, so in lockless
715 	// case we'd have to punt rather than doing those.
716 	if (unlikely(!(d_flags & DCACHE_LRU_LIST))) {
717 		if (!locked)
718 			return false;
719 		d_lru_add(dentry);
720 	} else if (unlikely(!(d_flags & DCACHE_REFERENCED))) {
721 		if (!locked)
722 			return false;
723 		dentry->d_flags |= DCACHE_REFERENCED;
724 	}
725 	return true;
726 }
727 
728 void d_mark_dontcache(struct inode *inode)
729 {
730 	struct dentry *de;
731 
732 	spin_lock(&inode->i_lock);
733 	hlist_for_each_entry(de, &inode->i_dentry, d_u.d_alias) {
734 		spin_lock(&de->d_lock);
735 		de->d_flags |= DCACHE_DONTCACHE;
736 		spin_unlock(&de->d_lock);
737 	}
738 	inode->i_state |= I_DONTCACHE;
739 	spin_unlock(&inode->i_lock);
740 }
741 EXPORT_SYMBOL(d_mark_dontcache);
742 
743 /*
744  * Try to do a lockless dput(), and return whether that was successful.
745  *
746  * If unsuccessful, we return false, having already taken the dentry lock.
747  * In that case refcount is guaranteed to be zero and we have already
748  * decided that it's not worth keeping around.
749  *
750  * The caller needs to hold the RCU read lock, so that the dentry is
751  * guaranteed to stay around even if the refcount goes down to zero!
752  */
753 static inline bool fast_dput(struct dentry *dentry)
754 {
755 	int ret;
756 
757 	/*
758 	 * try to decrement the lockref optimistically.
759 	 */
760 	ret = lockref_put_return(&dentry->d_lockref);
761 
762 	/*
763 	 * If the lockref_put_return() failed due to the lock being held
764 	 * by somebody else, the fast path has failed. We will need to
765 	 * get the lock, and then check the count again.
766 	 */
767 	if (unlikely(ret < 0)) {
768 		spin_lock(&dentry->d_lock);
769 		if (WARN_ON_ONCE(dentry->d_lockref.count <= 0)) {
770 			spin_unlock(&dentry->d_lock);
771 			return true;
772 		}
773 		dentry->d_lockref.count--;
774 		goto locked;
775 	}
776 
777 	/*
778 	 * If we weren't the last ref, we're done.
779 	 */
780 	if (ret)
781 		return true;
782 
783 	/*
784 	 * Can we decide that decrement of refcount is all we needed without
785 	 * taking the lock?  There's a very common case when it's all we need -
786 	 * dentry looks like it ought to be retained and there's nothing else
787 	 * to do.
788 	 */
789 	if (retain_dentry(dentry, false))
790 		return true;
791 
792 	/*
793 	 * Either not worth retaining or we can't tell without the lock.
794 	 * Get the lock, then.  We've already decremented the refcount to 0,
795 	 * but we'll need to re-check the situation after getting the lock.
796 	 */
797 	spin_lock(&dentry->d_lock);
798 
799 	/*
800 	 * Did somebody else grab a reference to it in the meantime, and
801 	 * we're no longer the last user after all? Alternatively, somebody
802 	 * else could have killed it and marked it dead. Either way, we
803 	 * don't need to do anything else.
804 	 */
805 locked:
806 	if (dentry->d_lockref.count || retain_dentry(dentry, true)) {
807 		spin_unlock(&dentry->d_lock);
808 		return true;
809 	}
810 	return false;
811 }
812 
813 
814 /*
815  * This is dput
816  *
817  * This is complicated by the fact that we do not want to put
818  * dentries that are no longer on any hash chain on the unused
819  * list: we'd much rather just get rid of them immediately.
820  *
821  * However, that implies that we have to traverse the dentry
822  * tree upwards to the parents which might _also_ now be
823  * scheduled for deletion (it may have been only waiting for
824  * its last child to go away).
825  *
826  * This tail recursion is done by hand as we don't want to depend
827  * on the compiler to always get this right (gcc generally doesn't).
828  * Real recursion would eat up our stack space.
829  */
830 
831 /*
832  * dput - release a dentry
833  * @dentry: dentry to release
834  *
835  * Release a dentry. This will drop the usage count and if appropriate
836  * call the dentry unlink method as well as removing it from the queues and
837  * releasing its resources. If the parent dentries were scheduled for release
838  * they too may now get deleted.
839  */
840 void dput(struct dentry *dentry)
841 {
842 	if (!dentry)
843 		return;
844 	might_sleep();
845 	rcu_read_lock();
846 	if (likely(fast_dput(dentry))) {
847 		rcu_read_unlock();
848 		return;
849 	}
850 	while (lock_for_kill(dentry)) {
851 		rcu_read_unlock();
852 		dentry = __dentry_kill(dentry);
853 		if (!dentry)
854 			return;
855 		if (retain_dentry(dentry, true)) {
856 			spin_unlock(&dentry->d_lock);
857 			return;
858 		}
859 		rcu_read_lock();
860 	}
861 	rcu_read_unlock();
862 	spin_unlock(&dentry->d_lock);
863 }
864 EXPORT_SYMBOL(dput);
865 
866 static void to_shrink_list(struct dentry *dentry, struct list_head *list)
867 __must_hold(&dentry->d_lock)
868 {
869 	if (!(dentry->d_flags & DCACHE_SHRINK_LIST)) {
870 		if (dentry->d_flags & DCACHE_LRU_LIST)
871 			d_lru_del(dentry);
872 		d_shrink_add(dentry, list);
873 	}
874 }
875 
876 void dput_to_list(struct dentry *dentry, struct list_head *list)
877 {
878 	rcu_read_lock();
879 	if (likely(fast_dput(dentry))) {
880 		rcu_read_unlock();
881 		return;
882 	}
883 	rcu_read_unlock();
884 	to_shrink_list(dentry, list);
885 	spin_unlock(&dentry->d_lock);
886 }
887 
888 struct dentry *dget_parent(struct dentry *dentry)
889 {
890 	int gotref;
891 	struct dentry *ret;
892 	unsigned seq;
893 
894 	/*
895 	 * Do optimistic parent lookup without any
896 	 * locking.
897 	 */
898 	rcu_read_lock();
899 	seq = raw_seqcount_begin(&dentry->d_seq);
900 	ret = READ_ONCE(dentry->d_parent);
901 	gotref = lockref_get_not_zero(&ret->d_lockref);
902 	rcu_read_unlock();
903 	if (likely(gotref)) {
904 		if (!read_seqcount_retry(&dentry->d_seq, seq))
905 			return ret;
906 		dput(ret);
907 	}
908 
909 repeat:
910 	/*
911 	 * Don't need rcu_dereference because we re-check it was correct under
912 	 * the lock.
913 	 */
914 	rcu_read_lock();
915 	ret = dentry->d_parent;
916 	spin_lock(&ret->d_lock);
917 	if (unlikely(ret != dentry->d_parent)) {
918 		spin_unlock(&ret->d_lock);
919 		rcu_read_unlock();
920 		goto repeat;
921 	}
922 	rcu_read_unlock();
923 	BUG_ON(!ret->d_lockref.count);
924 	ret->d_lockref.count++;
925 	spin_unlock(&ret->d_lock);
926 	return ret;
927 }
928 EXPORT_SYMBOL(dget_parent);
929 
930 static struct dentry * __d_find_any_alias(struct inode *inode)
931 {
932 	struct dentry *alias;
933 
934 	if (hlist_empty(&inode->i_dentry))
935 		return NULL;
936 	alias = hlist_entry(inode->i_dentry.first, struct dentry, d_u.d_alias);
937 	lockref_get(&alias->d_lockref);
938 	return alias;
939 }
940 
941 /**
942  * d_find_any_alias - find any alias for a given inode
943  * @inode: inode to find an alias for
944  *
945  * If any aliases exist for the given inode, take and return a
946  * reference for one of them.  If no aliases exist, return %NULL.
947  */
948 struct dentry *d_find_any_alias(struct inode *inode)
949 {
950 	struct dentry *de;
951 
952 	spin_lock(&inode->i_lock);
953 	de = __d_find_any_alias(inode);
954 	spin_unlock(&inode->i_lock);
955 	return de;
956 }
957 EXPORT_SYMBOL(d_find_any_alias);
958 
959 static struct dentry *__d_find_alias(struct inode *inode)
960 {
961 	struct dentry *alias;
962 
963 	if (S_ISDIR(inode->i_mode))
964 		return __d_find_any_alias(inode);
965 
966 	hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
967 		spin_lock(&alias->d_lock);
968  		if (!d_unhashed(alias)) {
969 			dget_dlock(alias);
970 			spin_unlock(&alias->d_lock);
971 			return alias;
972 		}
973 		spin_unlock(&alias->d_lock);
974 	}
975 	return NULL;
976 }
977 
978 /**
979  * d_find_alias - grab a hashed alias of inode
980  * @inode: inode in question
981  *
982  * If inode has a hashed alias, or is a directory and has any alias,
983  * acquire the reference to alias and return it. Otherwise return NULL.
984  * Notice that if inode is a directory there can be only one alias and
985  * it can be unhashed only if it has no children, or if it is the root
986  * of a filesystem, or if the directory was renamed and d_revalidate
987  * was the first vfs operation to notice.
988  *
989  * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
990  * any other hashed alias over that one.
991  */
992 struct dentry *d_find_alias(struct inode *inode)
993 {
994 	struct dentry *de = NULL;
995 
996 	if (!hlist_empty(&inode->i_dentry)) {
997 		spin_lock(&inode->i_lock);
998 		de = __d_find_alias(inode);
999 		spin_unlock(&inode->i_lock);
1000 	}
1001 	return de;
1002 }
1003 EXPORT_SYMBOL(d_find_alias);
1004 
1005 /*
1006  *  Caller MUST be holding rcu_read_lock() and be guaranteed
1007  *  that inode won't get freed until rcu_read_unlock().
1008  */
1009 struct dentry *d_find_alias_rcu(struct inode *inode)
1010 {
1011 	struct hlist_head *l = &inode->i_dentry;
1012 	struct dentry *de = NULL;
1013 
1014 	spin_lock(&inode->i_lock);
1015 	// ->i_dentry and ->i_rcu are colocated, but the latter won't be
1016 	// used without having I_FREEING set, which means no aliases left
1017 	if (likely(!(inode->i_state & I_FREEING) && !hlist_empty(l))) {
1018 		if (S_ISDIR(inode->i_mode)) {
1019 			de = hlist_entry(l->first, struct dentry, d_u.d_alias);
1020 		} else {
1021 			hlist_for_each_entry(de, l, d_u.d_alias)
1022 				if (!d_unhashed(de))
1023 					break;
1024 		}
1025 	}
1026 	spin_unlock(&inode->i_lock);
1027 	return de;
1028 }
1029 
1030 /*
1031  *	Try to kill dentries associated with this inode.
1032  * WARNING: you must own a reference to inode.
1033  */
1034 void d_prune_aliases(struct inode *inode)
1035 {
1036 	LIST_HEAD(dispose);
1037 	struct dentry *dentry;
1038 
1039 	spin_lock(&inode->i_lock);
1040 	hlist_for_each_entry(dentry, &inode->i_dentry, d_u.d_alias) {
1041 		spin_lock(&dentry->d_lock);
1042 		if (!dentry->d_lockref.count)
1043 			to_shrink_list(dentry, &dispose);
1044 		spin_unlock(&dentry->d_lock);
1045 	}
1046 	spin_unlock(&inode->i_lock);
1047 	shrink_dentry_list(&dispose);
1048 }
1049 EXPORT_SYMBOL(d_prune_aliases);
1050 
1051 static inline void shrink_kill(struct dentry *victim)
1052 {
1053 	do {
1054 		rcu_read_unlock();
1055 		victim = __dentry_kill(victim);
1056 		rcu_read_lock();
1057 	} while (victim && lock_for_kill(victim));
1058 	rcu_read_unlock();
1059 	if (victim)
1060 		spin_unlock(&victim->d_lock);
1061 }
1062 
1063 void shrink_dentry_list(struct list_head *list)
1064 {
1065 	while (!list_empty(list)) {
1066 		struct dentry *dentry;
1067 
1068 		dentry = list_entry(list->prev, struct dentry, d_lru);
1069 		spin_lock(&dentry->d_lock);
1070 		rcu_read_lock();
1071 		if (!lock_for_kill(dentry)) {
1072 			bool can_free;
1073 			rcu_read_unlock();
1074 			d_shrink_del(dentry);
1075 			can_free = dentry->d_flags & DCACHE_DENTRY_KILLED;
1076 			spin_unlock(&dentry->d_lock);
1077 			if (can_free)
1078 				dentry_free(dentry);
1079 			continue;
1080 		}
1081 		d_shrink_del(dentry);
1082 		shrink_kill(dentry);
1083 	}
1084 }
1085 
1086 static enum lru_status dentry_lru_isolate(struct list_head *item,
1087 		struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1088 {
1089 	struct list_head *freeable = arg;
1090 	struct dentry	*dentry = container_of(item, struct dentry, d_lru);
1091 
1092 
1093 	/*
1094 	 * we are inverting the lru lock/dentry->d_lock here,
1095 	 * so use a trylock. If we fail to get the lock, just skip
1096 	 * it
1097 	 */
1098 	if (!spin_trylock(&dentry->d_lock))
1099 		return LRU_SKIP;
1100 
1101 	/*
1102 	 * Referenced dentries are still in use. If they have active
1103 	 * counts, just remove them from the LRU. Otherwise give them
1104 	 * another pass through the LRU.
1105 	 */
1106 	if (dentry->d_lockref.count) {
1107 		d_lru_isolate(lru, dentry);
1108 		spin_unlock(&dentry->d_lock);
1109 		return LRU_REMOVED;
1110 	}
1111 
1112 	if (dentry->d_flags & DCACHE_REFERENCED) {
1113 		dentry->d_flags &= ~DCACHE_REFERENCED;
1114 		spin_unlock(&dentry->d_lock);
1115 
1116 		/*
1117 		 * The list move itself will be made by the common LRU code. At
1118 		 * this point, we've dropped the dentry->d_lock but keep the
1119 		 * lru lock. This is safe to do, since every list movement is
1120 		 * protected by the lru lock even if both locks are held.
1121 		 *
1122 		 * This is guaranteed by the fact that all LRU management
1123 		 * functions are intermediated by the LRU API calls like
1124 		 * list_lru_add_obj and list_lru_del_obj. List movement in this file
1125 		 * only ever occur through this functions or through callbacks
1126 		 * like this one, that are called from the LRU API.
1127 		 *
1128 		 * The only exceptions to this are functions like
1129 		 * shrink_dentry_list, and code that first checks for the
1130 		 * DCACHE_SHRINK_LIST flag.  Those are guaranteed to be
1131 		 * operating only with stack provided lists after they are
1132 		 * properly isolated from the main list.  It is thus, always a
1133 		 * local access.
1134 		 */
1135 		return LRU_ROTATE;
1136 	}
1137 
1138 	d_lru_shrink_move(lru, dentry, freeable);
1139 	spin_unlock(&dentry->d_lock);
1140 
1141 	return LRU_REMOVED;
1142 }
1143 
1144 /**
1145  * prune_dcache_sb - shrink the dcache
1146  * @sb: superblock
1147  * @sc: shrink control, passed to list_lru_shrink_walk()
1148  *
1149  * Attempt to shrink the superblock dcache LRU by @sc->nr_to_scan entries. This
1150  * is done when we need more memory and called from the superblock shrinker
1151  * function.
1152  *
1153  * This function may fail to free any resources if all the dentries are in
1154  * use.
1155  */
1156 long prune_dcache_sb(struct super_block *sb, struct shrink_control *sc)
1157 {
1158 	LIST_HEAD(dispose);
1159 	long freed;
1160 
1161 	freed = list_lru_shrink_walk(&sb->s_dentry_lru, sc,
1162 				     dentry_lru_isolate, &dispose);
1163 	shrink_dentry_list(&dispose);
1164 	return freed;
1165 }
1166 
1167 static enum lru_status dentry_lru_isolate_shrink(struct list_head *item,
1168 		struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1169 {
1170 	struct list_head *freeable = arg;
1171 	struct dentry	*dentry = container_of(item, struct dentry, d_lru);
1172 
1173 	/*
1174 	 * we are inverting the lru lock/dentry->d_lock here,
1175 	 * so use a trylock. If we fail to get the lock, just skip
1176 	 * it
1177 	 */
1178 	if (!spin_trylock(&dentry->d_lock))
1179 		return LRU_SKIP;
1180 
1181 	d_lru_shrink_move(lru, dentry, freeable);
1182 	spin_unlock(&dentry->d_lock);
1183 
1184 	return LRU_REMOVED;
1185 }
1186 
1187 
1188 /**
1189  * shrink_dcache_sb - shrink dcache for a superblock
1190  * @sb: superblock
1191  *
1192  * Shrink the dcache for the specified super block. This is used to free
1193  * the dcache before unmounting a file system.
1194  */
1195 void shrink_dcache_sb(struct super_block *sb)
1196 {
1197 	do {
1198 		LIST_HEAD(dispose);
1199 
1200 		list_lru_walk(&sb->s_dentry_lru,
1201 			dentry_lru_isolate_shrink, &dispose, 1024);
1202 		shrink_dentry_list(&dispose);
1203 	} while (list_lru_count(&sb->s_dentry_lru) > 0);
1204 }
1205 EXPORT_SYMBOL(shrink_dcache_sb);
1206 
1207 /**
1208  * enum d_walk_ret - action to talke during tree walk
1209  * @D_WALK_CONTINUE:	contrinue walk
1210  * @D_WALK_QUIT:	quit walk
1211  * @D_WALK_NORETRY:	quit when retry is needed
1212  * @D_WALK_SKIP:	skip this dentry and its children
1213  */
1214 enum d_walk_ret {
1215 	D_WALK_CONTINUE,
1216 	D_WALK_QUIT,
1217 	D_WALK_NORETRY,
1218 	D_WALK_SKIP,
1219 };
1220 
1221 /**
1222  * d_walk - walk the dentry tree
1223  * @parent:	start of walk
1224  * @data:	data passed to @enter() and @finish()
1225  * @enter:	callback when first entering the dentry
1226  *
1227  * The @enter() callbacks are called with d_lock held.
1228  */
1229 static void d_walk(struct dentry *parent, void *data,
1230 		   enum d_walk_ret (*enter)(void *, struct dentry *))
1231 {
1232 	struct dentry *this_parent, *dentry;
1233 	unsigned seq = 0;
1234 	enum d_walk_ret ret;
1235 	bool retry = true;
1236 
1237 again:
1238 	read_seqbegin_or_lock(&rename_lock, &seq);
1239 	this_parent = parent;
1240 	spin_lock(&this_parent->d_lock);
1241 
1242 	ret = enter(data, this_parent);
1243 	switch (ret) {
1244 	case D_WALK_CONTINUE:
1245 		break;
1246 	case D_WALK_QUIT:
1247 	case D_WALK_SKIP:
1248 		goto out_unlock;
1249 	case D_WALK_NORETRY:
1250 		retry = false;
1251 		break;
1252 	}
1253 repeat:
1254 	dentry = d_first_child(this_parent);
1255 resume:
1256 	hlist_for_each_entry_from(dentry, d_sib) {
1257 		if (unlikely(dentry->d_flags & DCACHE_DENTRY_CURSOR))
1258 			continue;
1259 
1260 		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
1261 
1262 		ret = enter(data, dentry);
1263 		switch (ret) {
1264 		case D_WALK_CONTINUE:
1265 			break;
1266 		case D_WALK_QUIT:
1267 			spin_unlock(&dentry->d_lock);
1268 			goto out_unlock;
1269 		case D_WALK_NORETRY:
1270 			retry = false;
1271 			break;
1272 		case D_WALK_SKIP:
1273 			spin_unlock(&dentry->d_lock);
1274 			continue;
1275 		}
1276 
1277 		if (!hlist_empty(&dentry->d_children)) {
1278 			spin_unlock(&this_parent->d_lock);
1279 			spin_release(&dentry->d_lock.dep_map, _RET_IP_);
1280 			this_parent = dentry;
1281 			spin_acquire(&this_parent->d_lock.dep_map, 0, 1, _RET_IP_);
1282 			goto repeat;
1283 		}
1284 		spin_unlock(&dentry->d_lock);
1285 	}
1286 	/*
1287 	 * All done at this level ... ascend and resume the search.
1288 	 */
1289 	rcu_read_lock();
1290 ascend:
1291 	if (this_parent != parent) {
1292 		dentry = this_parent;
1293 		this_parent = dentry->d_parent;
1294 
1295 		spin_unlock(&dentry->d_lock);
1296 		spin_lock(&this_parent->d_lock);
1297 
1298 		/* might go back up the wrong parent if we have had a rename. */
1299 		if (need_seqretry(&rename_lock, seq))
1300 			goto rename_retry;
1301 		/* go into the first sibling still alive */
1302 		hlist_for_each_entry_continue(dentry, d_sib) {
1303 			if (likely(!(dentry->d_flags & DCACHE_DENTRY_KILLED))) {
1304 				rcu_read_unlock();
1305 				goto resume;
1306 			}
1307 		}
1308 		goto ascend;
1309 	}
1310 	if (need_seqretry(&rename_lock, seq))
1311 		goto rename_retry;
1312 	rcu_read_unlock();
1313 
1314 out_unlock:
1315 	spin_unlock(&this_parent->d_lock);
1316 	done_seqretry(&rename_lock, seq);
1317 	return;
1318 
1319 rename_retry:
1320 	spin_unlock(&this_parent->d_lock);
1321 	rcu_read_unlock();
1322 	BUG_ON(seq & 1);
1323 	if (!retry)
1324 		return;
1325 	seq = 1;
1326 	goto again;
1327 }
1328 
1329 struct check_mount {
1330 	struct vfsmount *mnt;
1331 	unsigned int mounted;
1332 };
1333 
1334 static enum d_walk_ret path_check_mount(void *data, struct dentry *dentry)
1335 {
1336 	struct check_mount *info = data;
1337 	struct path path = { .mnt = info->mnt, .dentry = dentry };
1338 
1339 	if (likely(!d_mountpoint(dentry)))
1340 		return D_WALK_CONTINUE;
1341 	if (__path_is_mountpoint(&path)) {
1342 		info->mounted = 1;
1343 		return D_WALK_QUIT;
1344 	}
1345 	return D_WALK_CONTINUE;
1346 }
1347 
1348 /**
1349  * path_has_submounts - check for mounts over a dentry in the
1350  *                      current namespace.
1351  * @parent: path to check.
1352  *
1353  * Return true if the parent or its subdirectories contain
1354  * a mount point in the current namespace.
1355  */
1356 int path_has_submounts(const struct path *parent)
1357 {
1358 	struct check_mount data = { .mnt = parent->mnt, .mounted = 0 };
1359 
1360 	read_seqlock_excl(&mount_lock);
1361 	d_walk(parent->dentry, &data, path_check_mount);
1362 	read_sequnlock_excl(&mount_lock);
1363 
1364 	return data.mounted;
1365 }
1366 EXPORT_SYMBOL(path_has_submounts);
1367 
1368 /*
1369  * Called by mount code to set a mountpoint and check if the mountpoint is
1370  * reachable (e.g. NFS can unhash a directory dentry and then the complete
1371  * subtree can become unreachable).
1372  *
1373  * Only one of d_invalidate() and d_set_mounted() must succeed.  For
1374  * this reason take rename_lock and d_lock on dentry and ancestors.
1375  */
1376 int d_set_mounted(struct dentry *dentry)
1377 {
1378 	struct dentry *p;
1379 	int ret = -ENOENT;
1380 	write_seqlock(&rename_lock);
1381 	for (p = dentry->d_parent; !IS_ROOT(p); p = p->d_parent) {
1382 		/* Need exclusion wrt. d_invalidate() */
1383 		spin_lock(&p->d_lock);
1384 		if (unlikely(d_unhashed(p))) {
1385 			spin_unlock(&p->d_lock);
1386 			goto out;
1387 		}
1388 		spin_unlock(&p->d_lock);
1389 	}
1390 	spin_lock(&dentry->d_lock);
1391 	if (!d_unlinked(dentry)) {
1392 		ret = -EBUSY;
1393 		if (!d_mountpoint(dentry)) {
1394 			dentry->d_flags |= DCACHE_MOUNTED;
1395 			ret = 0;
1396 		}
1397 	}
1398  	spin_unlock(&dentry->d_lock);
1399 out:
1400 	write_sequnlock(&rename_lock);
1401 	return ret;
1402 }
1403 
1404 /*
1405  * Search the dentry child list of the specified parent,
1406  * and move any unused dentries to the end of the unused
1407  * list for prune_dcache(). We descend to the next level
1408  * whenever the d_children list is non-empty and continue
1409  * searching.
1410  *
1411  * It returns zero iff there are no unused children,
1412  * otherwise  it returns the number of children moved to
1413  * the end of the unused list. This may not be the total
1414  * number of unused children, because select_parent can
1415  * drop the lock and return early due to latency
1416  * constraints.
1417  */
1418 
1419 struct select_data {
1420 	struct dentry *start;
1421 	union {
1422 		long found;
1423 		struct dentry *victim;
1424 	};
1425 	struct list_head dispose;
1426 };
1427 
1428 static enum d_walk_ret select_collect(void *_data, struct dentry *dentry)
1429 {
1430 	struct select_data *data = _data;
1431 	enum d_walk_ret ret = D_WALK_CONTINUE;
1432 
1433 	if (data->start == dentry)
1434 		goto out;
1435 
1436 	if (dentry->d_flags & DCACHE_SHRINK_LIST) {
1437 		data->found++;
1438 	} else if (!dentry->d_lockref.count) {
1439 		to_shrink_list(dentry, &data->dispose);
1440 		data->found++;
1441 	} else if (dentry->d_lockref.count < 0) {
1442 		data->found++;
1443 	}
1444 	/*
1445 	 * We can return to the caller if we have found some (this
1446 	 * ensures forward progress). We'll be coming back to find
1447 	 * the rest.
1448 	 */
1449 	if (!list_empty(&data->dispose))
1450 		ret = need_resched() ? D_WALK_QUIT : D_WALK_NORETRY;
1451 out:
1452 	return ret;
1453 }
1454 
1455 static enum d_walk_ret select_collect2(void *_data, struct dentry *dentry)
1456 {
1457 	struct select_data *data = _data;
1458 	enum d_walk_ret ret = D_WALK_CONTINUE;
1459 
1460 	if (data->start == dentry)
1461 		goto out;
1462 
1463 	if (!dentry->d_lockref.count) {
1464 		if (dentry->d_flags & DCACHE_SHRINK_LIST) {
1465 			rcu_read_lock();
1466 			data->victim = dentry;
1467 			return D_WALK_QUIT;
1468 		}
1469 		to_shrink_list(dentry, &data->dispose);
1470 	}
1471 	/*
1472 	 * We can return to the caller if we have found some (this
1473 	 * ensures forward progress). We'll be coming back to find
1474 	 * the rest.
1475 	 */
1476 	if (!list_empty(&data->dispose))
1477 		ret = need_resched() ? D_WALK_QUIT : D_WALK_NORETRY;
1478 out:
1479 	return ret;
1480 }
1481 
1482 /**
1483  * shrink_dcache_parent - prune dcache
1484  * @parent: parent of entries to prune
1485  *
1486  * Prune the dcache to remove unused children of the parent dentry.
1487  */
1488 void shrink_dcache_parent(struct dentry *parent)
1489 {
1490 	for (;;) {
1491 		struct select_data data = {.start = parent};
1492 
1493 		INIT_LIST_HEAD(&data.dispose);
1494 		d_walk(parent, &data, select_collect);
1495 
1496 		if (!list_empty(&data.dispose)) {
1497 			shrink_dentry_list(&data.dispose);
1498 			continue;
1499 		}
1500 
1501 		cond_resched();
1502 		if (!data.found)
1503 			break;
1504 		data.victim = NULL;
1505 		d_walk(parent, &data, select_collect2);
1506 		if (data.victim) {
1507 			spin_lock(&data.victim->d_lock);
1508 			if (!lock_for_kill(data.victim)) {
1509 				spin_unlock(&data.victim->d_lock);
1510 				rcu_read_unlock();
1511 			} else {
1512 				shrink_kill(data.victim);
1513 			}
1514 		}
1515 		if (!list_empty(&data.dispose))
1516 			shrink_dentry_list(&data.dispose);
1517 	}
1518 }
1519 EXPORT_SYMBOL(shrink_dcache_parent);
1520 
1521 static enum d_walk_ret umount_check(void *_data, struct dentry *dentry)
1522 {
1523 	/* it has busy descendents; complain about those instead */
1524 	if (!hlist_empty(&dentry->d_children))
1525 		return D_WALK_CONTINUE;
1526 
1527 	/* root with refcount 1 is fine */
1528 	if (dentry == _data && dentry->d_lockref.count == 1)
1529 		return D_WALK_CONTINUE;
1530 
1531 	WARN(1, "BUG: Dentry %p{i=%lx,n=%pd} "
1532 			" still in use (%d) [unmount of %s %s]\n",
1533 		       dentry,
1534 		       dentry->d_inode ?
1535 		       dentry->d_inode->i_ino : 0UL,
1536 		       dentry,
1537 		       dentry->d_lockref.count,
1538 		       dentry->d_sb->s_type->name,
1539 		       dentry->d_sb->s_id);
1540 	return D_WALK_CONTINUE;
1541 }
1542 
1543 static void do_one_tree(struct dentry *dentry)
1544 {
1545 	shrink_dcache_parent(dentry);
1546 	d_walk(dentry, dentry, umount_check);
1547 	d_drop(dentry);
1548 	dput(dentry);
1549 }
1550 
1551 /*
1552  * destroy the dentries attached to a superblock on unmounting
1553  */
1554 void shrink_dcache_for_umount(struct super_block *sb)
1555 {
1556 	struct dentry *dentry;
1557 
1558 	rwsem_assert_held_write(&sb->s_umount);
1559 
1560 	dentry = sb->s_root;
1561 	sb->s_root = NULL;
1562 	do_one_tree(dentry);
1563 
1564 	while (!hlist_bl_empty(&sb->s_roots)) {
1565 		dentry = dget(hlist_bl_entry(hlist_bl_first(&sb->s_roots), struct dentry, d_hash));
1566 		do_one_tree(dentry);
1567 	}
1568 }
1569 
1570 static enum d_walk_ret find_submount(void *_data, struct dentry *dentry)
1571 {
1572 	struct dentry **victim = _data;
1573 	if (d_mountpoint(dentry)) {
1574 		*victim = dget_dlock(dentry);
1575 		return D_WALK_QUIT;
1576 	}
1577 	return D_WALK_CONTINUE;
1578 }
1579 
1580 /**
1581  * d_invalidate - detach submounts, prune dcache, and drop
1582  * @dentry: dentry to invalidate (aka detach, prune and drop)
1583  */
1584 void d_invalidate(struct dentry *dentry)
1585 {
1586 	bool had_submounts = false;
1587 	spin_lock(&dentry->d_lock);
1588 	if (d_unhashed(dentry)) {
1589 		spin_unlock(&dentry->d_lock);
1590 		return;
1591 	}
1592 	__d_drop(dentry);
1593 	spin_unlock(&dentry->d_lock);
1594 
1595 	/* Negative dentries can be dropped without further checks */
1596 	if (!dentry->d_inode)
1597 		return;
1598 
1599 	shrink_dcache_parent(dentry);
1600 	for (;;) {
1601 		struct dentry *victim = NULL;
1602 		d_walk(dentry, &victim, find_submount);
1603 		if (!victim) {
1604 			if (had_submounts)
1605 				shrink_dcache_parent(dentry);
1606 			return;
1607 		}
1608 		had_submounts = true;
1609 		detach_mounts(victim);
1610 		dput(victim);
1611 	}
1612 }
1613 EXPORT_SYMBOL(d_invalidate);
1614 
1615 /**
1616  * __d_alloc	-	allocate a dcache entry
1617  * @sb: filesystem it will belong to
1618  * @name: qstr of the name
1619  *
1620  * Allocates a dentry. It returns %NULL if there is insufficient memory
1621  * available. On a success the dentry is returned. The name passed in is
1622  * copied and the copy passed in may be reused after this call.
1623  */
1624 
1625 static struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
1626 {
1627 	struct dentry *dentry;
1628 	char *dname;
1629 	int err;
1630 
1631 	dentry = kmem_cache_alloc_lru(dentry_cache, &sb->s_dentry_lru,
1632 				      GFP_KERNEL);
1633 	if (!dentry)
1634 		return NULL;
1635 
1636 	/*
1637 	 * We guarantee that the inline name is always NUL-terminated.
1638 	 * This way the memcpy() done by the name switching in rename
1639 	 * will still always have a NUL at the end, even if we might
1640 	 * be overwriting an internal NUL character
1641 	 */
1642 	dentry->d_iname[DNAME_INLINE_LEN-1] = 0;
1643 	if (unlikely(!name)) {
1644 		name = &slash_name;
1645 		dname = dentry->d_iname;
1646 	} else if (name->len > DNAME_INLINE_LEN-1) {
1647 		size_t size = offsetof(struct external_name, name[1]);
1648 		struct external_name *p = kmalloc(size + name->len,
1649 						  GFP_KERNEL_ACCOUNT |
1650 						  __GFP_RECLAIMABLE);
1651 		if (!p) {
1652 			kmem_cache_free(dentry_cache, dentry);
1653 			return NULL;
1654 		}
1655 		atomic_set(&p->u.count, 1);
1656 		dname = p->name;
1657 	} else  {
1658 		dname = dentry->d_iname;
1659 	}
1660 
1661 	dentry->d_name.len = name->len;
1662 	dentry->d_name.hash = name->hash;
1663 	memcpy(dname, name->name, name->len);
1664 	dname[name->len] = 0;
1665 
1666 	/* Make sure we always see the terminating NUL character */
1667 	smp_store_release(&dentry->d_name.name, dname); /* ^^^ */
1668 
1669 	dentry->d_lockref.count = 1;
1670 	dentry->d_flags = 0;
1671 	spin_lock_init(&dentry->d_lock);
1672 	seqcount_spinlock_init(&dentry->d_seq, &dentry->d_lock);
1673 	dentry->d_inode = NULL;
1674 	dentry->d_parent = dentry;
1675 	dentry->d_sb = sb;
1676 	dentry->d_op = NULL;
1677 	dentry->d_fsdata = NULL;
1678 	INIT_HLIST_BL_NODE(&dentry->d_hash);
1679 	INIT_LIST_HEAD(&dentry->d_lru);
1680 	INIT_HLIST_HEAD(&dentry->d_children);
1681 	INIT_HLIST_NODE(&dentry->d_u.d_alias);
1682 	INIT_HLIST_NODE(&dentry->d_sib);
1683 	d_set_d_op(dentry, dentry->d_sb->s_d_op);
1684 
1685 	if (dentry->d_op && dentry->d_op->d_init) {
1686 		err = dentry->d_op->d_init(dentry);
1687 		if (err) {
1688 			if (dname_external(dentry))
1689 				kfree(external_name(dentry));
1690 			kmem_cache_free(dentry_cache, dentry);
1691 			return NULL;
1692 		}
1693 	}
1694 
1695 	this_cpu_inc(nr_dentry);
1696 
1697 	return dentry;
1698 }
1699 
1700 /**
1701  * d_alloc	-	allocate a dcache entry
1702  * @parent: parent of entry to allocate
1703  * @name: qstr of the name
1704  *
1705  * Allocates a dentry. It returns %NULL if there is insufficient memory
1706  * available. On a success the dentry is returned. The name passed in is
1707  * copied and the copy passed in may be reused after this call.
1708  */
1709 struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
1710 {
1711 	struct dentry *dentry = __d_alloc(parent->d_sb, name);
1712 	if (!dentry)
1713 		return NULL;
1714 	spin_lock(&parent->d_lock);
1715 	/*
1716 	 * don't need child lock because it is not subject
1717 	 * to concurrency here
1718 	 */
1719 	dentry->d_parent = dget_dlock(parent);
1720 	hlist_add_head(&dentry->d_sib, &parent->d_children);
1721 	spin_unlock(&parent->d_lock);
1722 
1723 	return dentry;
1724 }
1725 EXPORT_SYMBOL(d_alloc);
1726 
1727 struct dentry *d_alloc_anon(struct super_block *sb)
1728 {
1729 	return __d_alloc(sb, NULL);
1730 }
1731 EXPORT_SYMBOL(d_alloc_anon);
1732 
1733 struct dentry *d_alloc_cursor(struct dentry * parent)
1734 {
1735 	struct dentry *dentry = d_alloc_anon(parent->d_sb);
1736 	if (dentry) {
1737 		dentry->d_flags |= DCACHE_DENTRY_CURSOR;
1738 		dentry->d_parent = dget(parent);
1739 	}
1740 	return dentry;
1741 }
1742 
1743 /**
1744  * d_alloc_pseudo - allocate a dentry (for lookup-less filesystems)
1745  * @sb: the superblock
1746  * @name: qstr of the name
1747  *
1748  * For a filesystem that just pins its dentries in memory and never
1749  * performs lookups at all, return an unhashed IS_ROOT dentry.
1750  * This is used for pipes, sockets et.al. - the stuff that should
1751  * never be anyone's children or parents.  Unlike all other
1752  * dentries, these will not have RCU delay between dropping the
1753  * last reference and freeing them.
1754  *
1755  * The only user is alloc_file_pseudo() and that's what should
1756  * be considered a public interface.  Don't use directly.
1757  */
1758 struct dentry *d_alloc_pseudo(struct super_block *sb, const struct qstr *name)
1759 {
1760 	static const struct dentry_operations anon_ops = {
1761 		.d_dname = simple_dname
1762 	};
1763 	struct dentry *dentry = __d_alloc(sb, name);
1764 	if (likely(dentry)) {
1765 		dentry->d_flags |= DCACHE_NORCU;
1766 		if (!sb->s_d_op)
1767 			d_set_d_op(dentry, &anon_ops);
1768 	}
1769 	return dentry;
1770 }
1771 
1772 struct dentry *d_alloc_name(struct dentry *parent, const char *name)
1773 {
1774 	struct qstr q;
1775 
1776 	q.name = name;
1777 	q.hash_len = hashlen_string(parent, name);
1778 	return d_alloc(parent, &q);
1779 }
1780 EXPORT_SYMBOL(d_alloc_name);
1781 
1782 void d_set_d_op(struct dentry *dentry, const struct dentry_operations *op)
1783 {
1784 	WARN_ON_ONCE(dentry->d_op);
1785 	WARN_ON_ONCE(dentry->d_flags & (DCACHE_OP_HASH	|
1786 				DCACHE_OP_COMPARE	|
1787 				DCACHE_OP_REVALIDATE	|
1788 				DCACHE_OP_WEAK_REVALIDATE	|
1789 				DCACHE_OP_DELETE	|
1790 				DCACHE_OP_REAL));
1791 	dentry->d_op = op;
1792 	if (!op)
1793 		return;
1794 	if (op->d_hash)
1795 		dentry->d_flags |= DCACHE_OP_HASH;
1796 	if (op->d_compare)
1797 		dentry->d_flags |= DCACHE_OP_COMPARE;
1798 	if (op->d_revalidate)
1799 		dentry->d_flags |= DCACHE_OP_REVALIDATE;
1800 	if (op->d_weak_revalidate)
1801 		dentry->d_flags |= DCACHE_OP_WEAK_REVALIDATE;
1802 	if (op->d_delete)
1803 		dentry->d_flags |= DCACHE_OP_DELETE;
1804 	if (op->d_prune)
1805 		dentry->d_flags |= DCACHE_OP_PRUNE;
1806 	if (op->d_real)
1807 		dentry->d_flags |= DCACHE_OP_REAL;
1808 
1809 }
1810 EXPORT_SYMBOL(d_set_d_op);
1811 
1812 static unsigned d_flags_for_inode(struct inode *inode)
1813 {
1814 	unsigned add_flags = DCACHE_REGULAR_TYPE;
1815 
1816 	if (!inode)
1817 		return DCACHE_MISS_TYPE;
1818 
1819 	if (S_ISDIR(inode->i_mode)) {
1820 		add_flags = DCACHE_DIRECTORY_TYPE;
1821 		if (unlikely(!(inode->i_opflags & IOP_LOOKUP))) {
1822 			if (unlikely(!inode->i_op->lookup))
1823 				add_flags = DCACHE_AUTODIR_TYPE;
1824 			else
1825 				inode->i_opflags |= IOP_LOOKUP;
1826 		}
1827 		goto type_determined;
1828 	}
1829 
1830 	if (unlikely(!(inode->i_opflags & IOP_NOFOLLOW))) {
1831 		if (unlikely(inode->i_op->get_link)) {
1832 			add_flags = DCACHE_SYMLINK_TYPE;
1833 			goto type_determined;
1834 		}
1835 		inode->i_opflags |= IOP_NOFOLLOW;
1836 	}
1837 
1838 	if (unlikely(!S_ISREG(inode->i_mode)))
1839 		add_flags = DCACHE_SPECIAL_TYPE;
1840 
1841 type_determined:
1842 	if (unlikely(IS_AUTOMOUNT(inode)))
1843 		add_flags |= DCACHE_NEED_AUTOMOUNT;
1844 	return add_flags;
1845 }
1846 
1847 static void __d_instantiate(struct dentry *dentry, struct inode *inode)
1848 {
1849 	unsigned add_flags = d_flags_for_inode(inode);
1850 	WARN_ON(d_in_lookup(dentry));
1851 
1852 	spin_lock(&dentry->d_lock);
1853 	/*
1854 	 * The negative counter only tracks dentries on the LRU. Don't dec if
1855 	 * d_lru is on another list.
1856 	 */
1857 	if ((dentry->d_flags &
1858 	     (DCACHE_LRU_LIST|DCACHE_SHRINK_LIST)) == DCACHE_LRU_LIST)
1859 		this_cpu_dec(nr_dentry_negative);
1860 	hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
1861 	raw_write_seqcount_begin(&dentry->d_seq);
1862 	__d_set_inode_and_type(dentry, inode, add_flags);
1863 	raw_write_seqcount_end(&dentry->d_seq);
1864 	fsnotify_update_flags(dentry);
1865 	spin_unlock(&dentry->d_lock);
1866 }
1867 
1868 /**
1869  * d_instantiate - fill in inode information for a dentry
1870  * @entry: dentry to complete
1871  * @inode: inode to attach to this dentry
1872  *
1873  * Fill in inode information in the entry.
1874  *
1875  * This turns negative dentries into productive full members
1876  * of society.
1877  *
1878  * NOTE! This assumes that the inode count has been incremented
1879  * (or otherwise set) by the caller to indicate that it is now
1880  * in use by the dcache.
1881  */
1882 
1883 void d_instantiate(struct dentry *entry, struct inode * inode)
1884 {
1885 	BUG_ON(!hlist_unhashed(&entry->d_u.d_alias));
1886 	if (inode) {
1887 		security_d_instantiate(entry, inode);
1888 		spin_lock(&inode->i_lock);
1889 		__d_instantiate(entry, inode);
1890 		spin_unlock(&inode->i_lock);
1891 	}
1892 }
1893 EXPORT_SYMBOL(d_instantiate);
1894 
1895 /*
1896  * This should be equivalent to d_instantiate() + unlock_new_inode(),
1897  * with lockdep-related part of unlock_new_inode() done before
1898  * anything else.  Use that instead of open-coding d_instantiate()/
1899  * unlock_new_inode() combinations.
1900  */
1901 void d_instantiate_new(struct dentry *entry, struct inode *inode)
1902 {
1903 	BUG_ON(!hlist_unhashed(&entry->d_u.d_alias));
1904 	BUG_ON(!inode);
1905 	lockdep_annotate_inode_mutex_key(inode);
1906 	security_d_instantiate(entry, inode);
1907 	spin_lock(&inode->i_lock);
1908 	__d_instantiate(entry, inode);
1909 	WARN_ON(!(inode->i_state & I_NEW));
1910 	inode->i_state &= ~I_NEW & ~I_CREATING;
1911 	smp_mb();
1912 	wake_up_bit(&inode->i_state, __I_NEW);
1913 	spin_unlock(&inode->i_lock);
1914 }
1915 EXPORT_SYMBOL(d_instantiate_new);
1916 
1917 struct dentry *d_make_root(struct inode *root_inode)
1918 {
1919 	struct dentry *res = NULL;
1920 
1921 	if (root_inode) {
1922 		res = d_alloc_anon(root_inode->i_sb);
1923 		if (res)
1924 			d_instantiate(res, root_inode);
1925 		else
1926 			iput(root_inode);
1927 	}
1928 	return res;
1929 }
1930 EXPORT_SYMBOL(d_make_root);
1931 
1932 static struct dentry *__d_obtain_alias(struct inode *inode, bool disconnected)
1933 {
1934 	struct super_block *sb;
1935 	struct dentry *new, *res;
1936 
1937 	if (!inode)
1938 		return ERR_PTR(-ESTALE);
1939 	if (IS_ERR(inode))
1940 		return ERR_CAST(inode);
1941 
1942 	sb = inode->i_sb;
1943 
1944 	res = d_find_any_alias(inode); /* existing alias? */
1945 	if (res)
1946 		goto out;
1947 
1948 	new = d_alloc_anon(sb);
1949 	if (!new) {
1950 		res = ERR_PTR(-ENOMEM);
1951 		goto out;
1952 	}
1953 
1954 	security_d_instantiate(new, inode);
1955 	spin_lock(&inode->i_lock);
1956 	res = __d_find_any_alias(inode); /* recheck under lock */
1957 	if (likely(!res)) { /* still no alias, attach a disconnected dentry */
1958 		unsigned add_flags = d_flags_for_inode(inode);
1959 
1960 		if (disconnected)
1961 			add_flags |= DCACHE_DISCONNECTED;
1962 
1963 		spin_lock(&new->d_lock);
1964 		__d_set_inode_and_type(new, inode, add_flags);
1965 		hlist_add_head(&new->d_u.d_alias, &inode->i_dentry);
1966 		if (!disconnected) {
1967 			hlist_bl_lock(&sb->s_roots);
1968 			hlist_bl_add_head(&new->d_hash, &sb->s_roots);
1969 			hlist_bl_unlock(&sb->s_roots);
1970 		}
1971 		spin_unlock(&new->d_lock);
1972 		spin_unlock(&inode->i_lock);
1973 		inode = NULL; /* consumed by new->d_inode */
1974 		res = new;
1975 	} else {
1976 		spin_unlock(&inode->i_lock);
1977 		dput(new);
1978 	}
1979 
1980  out:
1981 	iput(inode);
1982 	return res;
1983 }
1984 
1985 /**
1986  * d_obtain_alias - find or allocate a DISCONNECTED dentry for a given inode
1987  * @inode: inode to allocate the dentry for
1988  *
1989  * Obtain a dentry for an inode resulting from NFS filehandle conversion or
1990  * similar open by handle operations.  The returned dentry may be anonymous,
1991  * or may have a full name (if the inode was already in the cache).
1992  *
1993  * When called on a directory inode, we must ensure that the inode only ever
1994  * has one dentry.  If a dentry is found, that is returned instead of
1995  * allocating a new one.
1996  *
1997  * On successful return, the reference to the inode has been transferred
1998  * to the dentry.  In case of an error the reference on the inode is released.
1999  * To make it easier to use in export operations a %NULL or IS_ERR inode may
2000  * be passed in and the error will be propagated to the return value,
2001  * with a %NULL @inode replaced by ERR_PTR(-ESTALE).
2002  */
2003 struct dentry *d_obtain_alias(struct inode *inode)
2004 {
2005 	return __d_obtain_alias(inode, true);
2006 }
2007 EXPORT_SYMBOL(d_obtain_alias);
2008 
2009 /**
2010  * d_obtain_root - find or allocate a dentry for a given inode
2011  * @inode: inode to allocate the dentry for
2012  *
2013  * Obtain an IS_ROOT dentry for the root of a filesystem.
2014  *
2015  * We must ensure that directory inodes only ever have one dentry.  If a
2016  * dentry is found, that is returned instead of allocating a new one.
2017  *
2018  * On successful return, the reference to the inode has been transferred
2019  * to the dentry.  In case of an error the reference on the inode is
2020  * released.  A %NULL or IS_ERR inode may be passed in and will be the
2021  * error will be propagate to the return value, with a %NULL @inode
2022  * replaced by ERR_PTR(-ESTALE).
2023  */
2024 struct dentry *d_obtain_root(struct inode *inode)
2025 {
2026 	return __d_obtain_alias(inode, false);
2027 }
2028 EXPORT_SYMBOL(d_obtain_root);
2029 
2030 /**
2031  * d_add_ci - lookup or allocate new dentry with case-exact name
2032  * @inode:  the inode case-insensitive lookup has found
2033  * @dentry: the negative dentry that was passed to the parent's lookup func
2034  * @name:   the case-exact name to be associated with the returned dentry
2035  *
2036  * This is to avoid filling the dcache with case-insensitive names to the
2037  * same inode, only the actual correct case is stored in the dcache for
2038  * case-insensitive filesystems.
2039  *
2040  * For a case-insensitive lookup match and if the case-exact dentry
2041  * already exists in the dcache, use it and return it.
2042  *
2043  * If no entry exists with the exact case name, allocate new dentry with
2044  * the exact case, and return the spliced entry.
2045  */
2046 struct dentry *d_add_ci(struct dentry *dentry, struct inode *inode,
2047 			struct qstr *name)
2048 {
2049 	struct dentry *found, *res;
2050 
2051 	/*
2052 	 * First check if a dentry matching the name already exists,
2053 	 * if not go ahead and create it now.
2054 	 */
2055 	found = d_hash_and_lookup(dentry->d_parent, name);
2056 	if (found) {
2057 		iput(inode);
2058 		return found;
2059 	}
2060 	if (d_in_lookup(dentry)) {
2061 		found = d_alloc_parallel(dentry->d_parent, name,
2062 					dentry->d_wait);
2063 		if (IS_ERR(found) || !d_in_lookup(found)) {
2064 			iput(inode);
2065 			return found;
2066 		}
2067 	} else {
2068 		found = d_alloc(dentry->d_parent, name);
2069 		if (!found) {
2070 			iput(inode);
2071 			return ERR_PTR(-ENOMEM);
2072 		}
2073 	}
2074 	res = d_splice_alias(inode, found);
2075 	if (res) {
2076 		d_lookup_done(found);
2077 		dput(found);
2078 		return res;
2079 	}
2080 	return found;
2081 }
2082 EXPORT_SYMBOL(d_add_ci);
2083 
2084 /**
2085  * d_same_name - compare dentry name with case-exact name
2086  * @parent: parent dentry
2087  * @dentry: the negative dentry that was passed to the parent's lookup func
2088  * @name:   the case-exact name to be associated with the returned dentry
2089  *
2090  * Return: true if names are same, or false
2091  */
2092 bool d_same_name(const struct dentry *dentry, const struct dentry *parent,
2093 		 const struct qstr *name)
2094 {
2095 	if (likely(!(parent->d_flags & DCACHE_OP_COMPARE))) {
2096 		if (dentry->d_name.len != name->len)
2097 			return false;
2098 		return dentry_cmp(dentry, name->name, name->len) == 0;
2099 	}
2100 	return parent->d_op->d_compare(dentry,
2101 				       dentry->d_name.len, dentry->d_name.name,
2102 				       name) == 0;
2103 }
2104 EXPORT_SYMBOL_GPL(d_same_name);
2105 
2106 /*
2107  * This is __d_lookup_rcu() when the parent dentry has
2108  * DCACHE_OP_COMPARE, which makes things much nastier.
2109  */
2110 static noinline struct dentry *__d_lookup_rcu_op_compare(
2111 	const struct dentry *parent,
2112 	const struct qstr *name,
2113 	unsigned *seqp)
2114 {
2115 	u64 hashlen = name->hash_len;
2116 	struct hlist_bl_head *b = d_hash(hashlen);
2117 	struct hlist_bl_node *node;
2118 	struct dentry *dentry;
2119 
2120 	hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
2121 		int tlen;
2122 		const char *tname;
2123 		unsigned seq;
2124 
2125 seqretry:
2126 		seq = raw_seqcount_begin(&dentry->d_seq);
2127 		if (dentry->d_parent != parent)
2128 			continue;
2129 		if (d_unhashed(dentry))
2130 			continue;
2131 		if (dentry->d_name.hash != hashlen_hash(hashlen))
2132 			continue;
2133 		tlen = dentry->d_name.len;
2134 		tname = dentry->d_name.name;
2135 		/* we want a consistent (name,len) pair */
2136 		if (read_seqcount_retry(&dentry->d_seq, seq)) {
2137 			cpu_relax();
2138 			goto seqretry;
2139 		}
2140 		if (parent->d_op->d_compare(dentry, tlen, tname, name) != 0)
2141 			continue;
2142 		*seqp = seq;
2143 		return dentry;
2144 	}
2145 	return NULL;
2146 }
2147 
2148 /**
2149  * __d_lookup_rcu - search for a dentry (racy, store-free)
2150  * @parent: parent dentry
2151  * @name: qstr of name we wish to find
2152  * @seqp: returns d_seq value at the point where the dentry was found
2153  * Returns: dentry, or NULL
2154  *
2155  * __d_lookup_rcu is the dcache lookup function for rcu-walk name
2156  * resolution (store-free path walking) design described in
2157  * Documentation/filesystems/path-lookup.txt.
2158  *
2159  * This is not to be used outside core vfs.
2160  *
2161  * __d_lookup_rcu must only be used in rcu-walk mode, ie. with vfsmount lock
2162  * held, and rcu_read_lock held. The returned dentry must not be stored into
2163  * without taking d_lock and checking d_seq sequence count against @seq
2164  * returned here.
2165  *
2166  * A refcount may be taken on the found dentry with the d_rcu_to_refcount
2167  * function.
2168  *
2169  * Alternatively, __d_lookup_rcu may be called again to look up the child of
2170  * the returned dentry, so long as its parent's seqlock is checked after the
2171  * child is looked up. Thus, an interlocking stepping of sequence lock checks
2172  * is formed, giving integrity down the path walk.
2173  *
2174  * NOTE! The caller *has* to check the resulting dentry against the sequence
2175  * number we've returned before using any of the resulting dentry state!
2176  */
2177 struct dentry *__d_lookup_rcu(const struct dentry *parent,
2178 				const struct qstr *name,
2179 				unsigned *seqp)
2180 {
2181 	u64 hashlen = name->hash_len;
2182 	const unsigned char *str = name->name;
2183 	struct hlist_bl_head *b = d_hash(hashlen);
2184 	struct hlist_bl_node *node;
2185 	struct dentry *dentry;
2186 
2187 	/*
2188 	 * Note: There is significant duplication with __d_lookup_rcu which is
2189 	 * required to prevent single threaded performance regressions
2190 	 * especially on architectures where smp_rmb (in seqcounts) are costly.
2191 	 * Keep the two functions in sync.
2192 	 */
2193 
2194 	if (unlikely(parent->d_flags & DCACHE_OP_COMPARE))
2195 		return __d_lookup_rcu_op_compare(parent, name, seqp);
2196 
2197 	/*
2198 	 * The hash list is protected using RCU.
2199 	 *
2200 	 * Carefully use d_seq when comparing a candidate dentry, to avoid
2201 	 * races with d_move().
2202 	 *
2203 	 * It is possible that concurrent renames can mess up our list
2204 	 * walk here and result in missing our dentry, resulting in the
2205 	 * false-negative result. d_lookup() protects against concurrent
2206 	 * renames using rename_lock seqlock.
2207 	 *
2208 	 * See Documentation/filesystems/path-lookup.txt for more details.
2209 	 */
2210 	hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
2211 		unsigned seq;
2212 
2213 		/*
2214 		 * The dentry sequence count protects us from concurrent
2215 		 * renames, and thus protects parent and name fields.
2216 		 *
2217 		 * The caller must perform a seqcount check in order
2218 		 * to do anything useful with the returned dentry.
2219 		 *
2220 		 * NOTE! We do a "raw" seqcount_begin here. That means that
2221 		 * we don't wait for the sequence count to stabilize if it
2222 		 * is in the middle of a sequence change. If we do the slow
2223 		 * dentry compare, we will do seqretries until it is stable,
2224 		 * and if we end up with a successful lookup, we actually
2225 		 * want to exit RCU lookup anyway.
2226 		 *
2227 		 * Note that raw_seqcount_begin still *does* smp_rmb(), so
2228 		 * we are still guaranteed NUL-termination of ->d_name.name.
2229 		 */
2230 		seq = raw_seqcount_begin(&dentry->d_seq);
2231 		if (dentry->d_parent != parent)
2232 			continue;
2233 		if (d_unhashed(dentry))
2234 			continue;
2235 		if (dentry->d_name.hash_len != hashlen)
2236 			continue;
2237 		if (dentry_cmp(dentry, str, hashlen_len(hashlen)) != 0)
2238 			continue;
2239 		*seqp = seq;
2240 		return dentry;
2241 	}
2242 	return NULL;
2243 }
2244 
2245 /**
2246  * d_lookup - search for a dentry
2247  * @parent: parent dentry
2248  * @name: qstr of name we wish to find
2249  * Returns: dentry, or NULL
2250  *
2251  * d_lookup searches the children of the parent dentry for the name in
2252  * question. If the dentry is found its reference count is incremented and the
2253  * dentry is returned. The caller must use dput to free the entry when it has
2254  * finished using it. %NULL is returned if the dentry does not exist.
2255  */
2256 struct dentry *d_lookup(const struct dentry *parent, const struct qstr *name)
2257 {
2258 	struct dentry *dentry;
2259 	unsigned seq;
2260 
2261 	do {
2262 		seq = read_seqbegin(&rename_lock);
2263 		dentry = __d_lookup(parent, name);
2264 		if (dentry)
2265 			break;
2266 	} while (read_seqretry(&rename_lock, seq));
2267 	return dentry;
2268 }
2269 EXPORT_SYMBOL(d_lookup);
2270 
2271 /**
2272  * __d_lookup - search for a dentry (racy)
2273  * @parent: parent dentry
2274  * @name: qstr of name we wish to find
2275  * Returns: dentry, or NULL
2276  *
2277  * __d_lookup is like d_lookup, however it may (rarely) return a
2278  * false-negative result due to unrelated rename activity.
2279  *
2280  * __d_lookup is slightly faster by avoiding rename_lock read seqlock,
2281  * however it must be used carefully, eg. with a following d_lookup in
2282  * the case of failure.
2283  *
2284  * __d_lookup callers must be commented.
2285  */
2286 struct dentry *__d_lookup(const struct dentry *parent, const struct qstr *name)
2287 {
2288 	unsigned int hash = name->hash;
2289 	struct hlist_bl_head *b = d_hash(hash);
2290 	struct hlist_bl_node *node;
2291 	struct dentry *found = NULL;
2292 	struct dentry *dentry;
2293 
2294 	/*
2295 	 * Note: There is significant duplication with __d_lookup_rcu which is
2296 	 * required to prevent single threaded performance regressions
2297 	 * especially on architectures where smp_rmb (in seqcounts) are costly.
2298 	 * Keep the two functions in sync.
2299 	 */
2300 
2301 	/*
2302 	 * The hash list is protected using RCU.
2303 	 *
2304 	 * Take d_lock when comparing a candidate dentry, to avoid races
2305 	 * with d_move().
2306 	 *
2307 	 * It is possible that concurrent renames can mess up our list
2308 	 * walk here and result in missing our dentry, resulting in the
2309 	 * false-negative result. d_lookup() protects against concurrent
2310 	 * renames using rename_lock seqlock.
2311 	 *
2312 	 * See Documentation/filesystems/path-lookup.txt for more details.
2313 	 */
2314 	rcu_read_lock();
2315 
2316 	hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
2317 
2318 		if (dentry->d_name.hash != hash)
2319 			continue;
2320 
2321 		spin_lock(&dentry->d_lock);
2322 		if (dentry->d_parent != parent)
2323 			goto next;
2324 		if (d_unhashed(dentry))
2325 			goto next;
2326 
2327 		if (!d_same_name(dentry, parent, name))
2328 			goto next;
2329 
2330 		dentry->d_lockref.count++;
2331 		found = dentry;
2332 		spin_unlock(&dentry->d_lock);
2333 		break;
2334 next:
2335 		spin_unlock(&dentry->d_lock);
2336  	}
2337  	rcu_read_unlock();
2338 
2339  	return found;
2340 }
2341 
2342 /**
2343  * d_hash_and_lookup - hash the qstr then search for a dentry
2344  * @dir: Directory to search in
2345  * @name: qstr of name we wish to find
2346  *
2347  * On lookup failure NULL is returned; on bad name - ERR_PTR(-error)
2348  */
2349 struct dentry *d_hash_and_lookup(struct dentry *dir, struct qstr *name)
2350 {
2351 	/*
2352 	 * Check for a fs-specific hash function. Note that we must
2353 	 * calculate the standard hash first, as the d_op->d_hash()
2354 	 * routine may choose to leave the hash value unchanged.
2355 	 */
2356 	name->hash = full_name_hash(dir, name->name, name->len);
2357 	if (dir->d_flags & DCACHE_OP_HASH) {
2358 		int err = dir->d_op->d_hash(dir, name);
2359 		if (unlikely(err < 0))
2360 			return ERR_PTR(err);
2361 	}
2362 	return d_lookup(dir, name);
2363 }
2364 EXPORT_SYMBOL(d_hash_and_lookup);
2365 
2366 /*
2367  * When a file is deleted, we have two options:
2368  * - turn this dentry into a negative dentry
2369  * - unhash this dentry and free it.
2370  *
2371  * Usually, we want to just turn this into
2372  * a negative dentry, but if anybody else is
2373  * currently using the dentry or the inode
2374  * we can't do that and we fall back on removing
2375  * it from the hash queues and waiting for
2376  * it to be deleted later when it has no users
2377  */
2378 
2379 /**
2380  * d_delete - delete a dentry
2381  * @dentry: The dentry to delete
2382  *
2383  * Turn the dentry into a negative dentry if possible, otherwise
2384  * remove it from the hash queues so it can be deleted later
2385  */
2386 
2387 void d_delete(struct dentry * dentry)
2388 {
2389 	struct inode *inode = dentry->d_inode;
2390 
2391 	spin_lock(&inode->i_lock);
2392 	spin_lock(&dentry->d_lock);
2393 	/*
2394 	 * Are we the only user?
2395 	 */
2396 	if (dentry->d_lockref.count == 1) {
2397 		dentry->d_flags &= ~DCACHE_CANT_MOUNT;
2398 		dentry_unlink_inode(dentry);
2399 	} else {
2400 		__d_drop(dentry);
2401 		spin_unlock(&dentry->d_lock);
2402 		spin_unlock(&inode->i_lock);
2403 	}
2404 }
2405 EXPORT_SYMBOL(d_delete);
2406 
2407 static void __d_rehash(struct dentry *entry)
2408 {
2409 	struct hlist_bl_head *b = d_hash(entry->d_name.hash);
2410 
2411 	hlist_bl_lock(b);
2412 	hlist_bl_add_head_rcu(&entry->d_hash, b);
2413 	hlist_bl_unlock(b);
2414 }
2415 
2416 /**
2417  * d_rehash	- add an entry back to the hash
2418  * @entry: dentry to add to the hash
2419  *
2420  * Adds a dentry to the hash according to its name.
2421  */
2422 
2423 void d_rehash(struct dentry * entry)
2424 {
2425 	spin_lock(&entry->d_lock);
2426 	__d_rehash(entry);
2427 	spin_unlock(&entry->d_lock);
2428 }
2429 EXPORT_SYMBOL(d_rehash);
2430 
2431 static inline unsigned start_dir_add(struct inode *dir)
2432 {
2433 	preempt_disable_nested();
2434 	for (;;) {
2435 		unsigned n = dir->i_dir_seq;
2436 		if (!(n & 1) && cmpxchg(&dir->i_dir_seq, n, n + 1) == n)
2437 			return n;
2438 		cpu_relax();
2439 	}
2440 }
2441 
2442 static inline void end_dir_add(struct inode *dir, unsigned int n,
2443 			       wait_queue_head_t *d_wait)
2444 {
2445 	smp_store_release(&dir->i_dir_seq, n + 2);
2446 	preempt_enable_nested();
2447 	wake_up_all(d_wait);
2448 }
2449 
2450 static void d_wait_lookup(struct dentry *dentry)
2451 {
2452 	if (d_in_lookup(dentry)) {
2453 		DECLARE_WAITQUEUE(wait, current);
2454 		add_wait_queue(dentry->d_wait, &wait);
2455 		do {
2456 			set_current_state(TASK_UNINTERRUPTIBLE);
2457 			spin_unlock(&dentry->d_lock);
2458 			schedule();
2459 			spin_lock(&dentry->d_lock);
2460 		} while (d_in_lookup(dentry));
2461 	}
2462 }
2463 
2464 struct dentry *d_alloc_parallel(struct dentry *parent,
2465 				const struct qstr *name,
2466 				wait_queue_head_t *wq)
2467 {
2468 	unsigned int hash = name->hash;
2469 	struct hlist_bl_head *b = in_lookup_hash(parent, hash);
2470 	struct hlist_bl_node *node;
2471 	struct dentry *new = d_alloc(parent, name);
2472 	struct dentry *dentry;
2473 	unsigned seq, r_seq, d_seq;
2474 
2475 	if (unlikely(!new))
2476 		return ERR_PTR(-ENOMEM);
2477 
2478 retry:
2479 	rcu_read_lock();
2480 	seq = smp_load_acquire(&parent->d_inode->i_dir_seq);
2481 	r_seq = read_seqbegin(&rename_lock);
2482 	dentry = __d_lookup_rcu(parent, name, &d_seq);
2483 	if (unlikely(dentry)) {
2484 		if (!lockref_get_not_dead(&dentry->d_lockref)) {
2485 			rcu_read_unlock();
2486 			goto retry;
2487 		}
2488 		if (read_seqcount_retry(&dentry->d_seq, d_seq)) {
2489 			rcu_read_unlock();
2490 			dput(dentry);
2491 			goto retry;
2492 		}
2493 		rcu_read_unlock();
2494 		dput(new);
2495 		return dentry;
2496 	}
2497 	if (unlikely(read_seqretry(&rename_lock, r_seq))) {
2498 		rcu_read_unlock();
2499 		goto retry;
2500 	}
2501 
2502 	if (unlikely(seq & 1)) {
2503 		rcu_read_unlock();
2504 		goto retry;
2505 	}
2506 
2507 	hlist_bl_lock(b);
2508 	if (unlikely(READ_ONCE(parent->d_inode->i_dir_seq) != seq)) {
2509 		hlist_bl_unlock(b);
2510 		rcu_read_unlock();
2511 		goto retry;
2512 	}
2513 	/*
2514 	 * No changes for the parent since the beginning of d_lookup().
2515 	 * Since all removals from the chain happen with hlist_bl_lock(),
2516 	 * any potential in-lookup matches are going to stay here until
2517 	 * we unlock the chain.  All fields are stable in everything
2518 	 * we encounter.
2519 	 */
2520 	hlist_bl_for_each_entry(dentry, node, b, d_u.d_in_lookup_hash) {
2521 		if (dentry->d_name.hash != hash)
2522 			continue;
2523 		if (dentry->d_parent != parent)
2524 			continue;
2525 		if (!d_same_name(dentry, parent, name))
2526 			continue;
2527 		hlist_bl_unlock(b);
2528 		/* now we can try to grab a reference */
2529 		if (!lockref_get_not_dead(&dentry->d_lockref)) {
2530 			rcu_read_unlock();
2531 			goto retry;
2532 		}
2533 
2534 		rcu_read_unlock();
2535 		/*
2536 		 * somebody is likely to be still doing lookup for it;
2537 		 * wait for them to finish
2538 		 */
2539 		spin_lock(&dentry->d_lock);
2540 		d_wait_lookup(dentry);
2541 		/*
2542 		 * it's not in-lookup anymore; in principle we should repeat
2543 		 * everything from dcache lookup, but it's likely to be what
2544 		 * d_lookup() would've found anyway.  If it is, just return it;
2545 		 * otherwise we really have to repeat the whole thing.
2546 		 */
2547 		if (unlikely(dentry->d_name.hash != hash))
2548 			goto mismatch;
2549 		if (unlikely(dentry->d_parent != parent))
2550 			goto mismatch;
2551 		if (unlikely(d_unhashed(dentry)))
2552 			goto mismatch;
2553 		if (unlikely(!d_same_name(dentry, parent, name)))
2554 			goto mismatch;
2555 		/* OK, it *is* a hashed match; return it */
2556 		spin_unlock(&dentry->d_lock);
2557 		dput(new);
2558 		return dentry;
2559 	}
2560 	rcu_read_unlock();
2561 	/* we can't take ->d_lock here; it's OK, though. */
2562 	new->d_flags |= DCACHE_PAR_LOOKUP;
2563 	new->d_wait = wq;
2564 	hlist_bl_add_head(&new->d_u.d_in_lookup_hash, b);
2565 	hlist_bl_unlock(b);
2566 	return new;
2567 mismatch:
2568 	spin_unlock(&dentry->d_lock);
2569 	dput(dentry);
2570 	goto retry;
2571 }
2572 EXPORT_SYMBOL(d_alloc_parallel);
2573 
2574 /*
2575  * - Unhash the dentry
2576  * - Retrieve and clear the waitqueue head in dentry
2577  * - Return the waitqueue head
2578  */
2579 static wait_queue_head_t *__d_lookup_unhash(struct dentry *dentry)
2580 {
2581 	wait_queue_head_t *d_wait;
2582 	struct hlist_bl_head *b;
2583 
2584 	lockdep_assert_held(&dentry->d_lock);
2585 
2586 	b = in_lookup_hash(dentry->d_parent, dentry->d_name.hash);
2587 	hlist_bl_lock(b);
2588 	dentry->d_flags &= ~DCACHE_PAR_LOOKUP;
2589 	__hlist_bl_del(&dentry->d_u.d_in_lookup_hash);
2590 	d_wait = dentry->d_wait;
2591 	dentry->d_wait = NULL;
2592 	hlist_bl_unlock(b);
2593 	INIT_HLIST_NODE(&dentry->d_u.d_alias);
2594 	INIT_LIST_HEAD(&dentry->d_lru);
2595 	return d_wait;
2596 }
2597 
2598 void __d_lookup_unhash_wake(struct dentry *dentry)
2599 {
2600 	spin_lock(&dentry->d_lock);
2601 	wake_up_all(__d_lookup_unhash(dentry));
2602 	spin_unlock(&dentry->d_lock);
2603 }
2604 EXPORT_SYMBOL(__d_lookup_unhash_wake);
2605 
2606 /* inode->i_lock held if inode is non-NULL */
2607 
2608 static inline void __d_add(struct dentry *dentry, struct inode *inode)
2609 {
2610 	wait_queue_head_t *d_wait;
2611 	struct inode *dir = NULL;
2612 	unsigned n;
2613 	spin_lock(&dentry->d_lock);
2614 	if (unlikely(d_in_lookup(dentry))) {
2615 		dir = dentry->d_parent->d_inode;
2616 		n = start_dir_add(dir);
2617 		d_wait = __d_lookup_unhash(dentry);
2618 	}
2619 	if (inode) {
2620 		unsigned add_flags = d_flags_for_inode(inode);
2621 		hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
2622 		raw_write_seqcount_begin(&dentry->d_seq);
2623 		__d_set_inode_and_type(dentry, inode, add_flags);
2624 		raw_write_seqcount_end(&dentry->d_seq);
2625 		fsnotify_update_flags(dentry);
2626 	}
2627 	__d_rehash(dentry);
2628 	if (dir)
2629 		end_dir_add(dir, n, d_wait);
2630 	spin_unlock(&dentry->d_lock);
2631 	if (inode)
2632 		spin_unlock(&inode->i_lock);
2633 }
2634 
2635 /**
2636  * d_add - add dentry to hash queues
2637  * @entry: dentry to add
2638  * @inode: The inode to attach to this dentry
2639  *
2640  * This adds the entry to the hash queues and initializes @inode.
2641  * The entry was actually filled in earlier during d_alloc().
2642  */
2643 
2644 void d_add(struct dentry *entry, struct inode *inode)
2645 {
2646 	if (inode) {
2647 		security_d_instantiate(entry, inode);
2648 		spin_lock(&inode->i_lock);
2649 	}
2650 	__d_add(entry, inode);
2651 }
2652 EXPORT_SYMBOL(d_add);
2653 
2654 /**
2655  * d_exact_alias - find and hash an exact unhashed alias
2656  * @entry: dentry to add
2657  * @inode: The inode to go with this dentry
2658  *
2659  * If an unhashed dentry with the same name/parent and desired
2660  * inode already exists, hash and return it.  Otherwise, return
2661  * NULL.
2662  *
2663  * Parent directory should be locked.
2664  */
2665 struct dentry *d_exact_alias(struct dentry *entry, struct inode *inode)
2666 {
2667 	struct dentry *alias;
2668 	unsigned int hash = entry->d_name.hash;
2669 
2670 	spin_lock(&inode->i_lock);
2671 	hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
2672 		/*
2673 		 * Don't need alias->d_lock here, because aliases with
2674 		 * d_parent == entry->d_parent are not subject to name or
2675 		 * parent changes, because the parent inode i_mutex is held.
2676 		 */
2677 		if (alias->d_name.hash != hash)
2678 			continue;
2679 		if (alias->d_parent != entry->d_parent)
2680 			continue;
2681 		if (!d_same_name(alias, entry->d_parent, &entry->d_name))
2682 			continue;
2683 		spin_lock(&alias->d_lock);
2684 		if (!d_unhashed(alias)) {
2685 			spin_unlock(&alias->d_lock);
2686 			alias = NULL;
2687 		} else {
2688 			dget_dlock(alias);
2689 			__d_rehash(alias);
2690 			spin_unlock(&alias->d_lock);
2691 		}
2692 		spin_unlock(&inode->i_lock);
2693 		return alias;
2694 	}
2695 	spin_unlock(&inode->i_lock);
2696 	return NULL;
2697 }
2698 EXPORT_SYMBOL(d_exact_alias);
2699 
2700 static void swap_names(struct dentry *dentry, struct dentry *target)
2701 {
2702 	if (unlikely(dname_external(target))) {
2703 		if (unlikely(dname_external(dentry))) {
2704 			/*
2705 			 * Both external: swap the pointers
2706 			 */
2707 			swap(target->d_name.name, dentry->d_name.name);
2708 		} else {
2709 			/*
2710 			 * dentry:internal, target:external.  Steal target's
2711 			 * storage and make target internal.
2712 			 */
2713 			memcpy(target->d_iname, dentry->d_name.name,
2714 					dentry->d_name.len + 1);
2715 			dentry->d_name.name = target->d_name.name;
2716 			target->d_name.name = target->d_iname;
2717 		}
2718 	} else {
2719 		if (unlikely(dname_external(dentry))) {
2720 			/*
2721 			 * dentry:external, target:internal.  Give dentry's
2722 			 * storage to target and make dentry internal
2723 			 */
2724 			memcpy(dentry->d_iname, target->d_name.name,
2725 					target->d_name.len + 1);
2726 			target->d_name.name = dentry->d_name.name;
2727 			dentry->d_name.name = dentry->d_iname;
2728 		} else {
2729 			/*
2730 			 * Both are internal.
2731 			 */
2732 			unsigned int i;
2733 			BUILD_BUG_ON(!IS_ALIGNED(DNAME_INLINE_LEN, sizeof(long)));
2734 			for (i = 0; i < DNAME_INLINE_LEN / sizeof(long); i++) {
2735 				swap(((long *) &dentry->d_iname)[i],
2736 				     ((long *) &target->d_iname)[i]);
2737 			}
2738 		}
2739 	}
2740 	swap(dentry->d_name.hash_len, target->d_name.hash_len);
2741 }
2742 
2743 static void copy_name(struct dentry *dentry, struct dentry *target)
2744 {
2745 	struct external_name *old_name = NULL;
2746 	if (unlikely(dname_external(dentry)))
2747 		old_name = external_name(dentry);
2748 	if (unlikely(dname_external(target))) {
2749 		atomic_inc(&external_name(target)->u.count);
2750 		dentry->d_name = target->d_name;
2751 	} else {
2752 		memcpy(dentry->d_iname, target->d_name.name,
2753 				target->d_name.len + 1);
2754 		dentry->d_name.name = dentry->d_iname;
2755 		dentry->d_name.hash_len = target->d_name.hash_len;
2756 	}
2757 	if (old_name && likely(atomic_dec_and_test(&old_name->u.count)))
2758 		kfree_rcu(old_name, u.head);
2759 }
2760 
2761 /*
2762  * __d_move - move a dentry
2763  * @dentry: entry to move
2764  * @target: new dentry
2765  * @exchange: exchange the two dentries
2766  *
2767  * Update the dcache to reflect the move of a file name. Negative
2768  * dcache entries should not be moved in this way. Caller must hold
2769  * rename_lock, the i_mutex of the source and target directories,
2770  * and the sb->s_vfs_rename_mutex if they differ. See lock_rename().
2771  */
2772 static void __d_move(struct dentry *dentry, struct dentry *target,
2773 		     bool exchange)
2774 {
2775 	struct dentry *old_parent, *p;
2776 	wait_queue_head_t *d_wait;
2777 	struct inode *dir = NULL;
2778 	unsigned n;
2779 
2780 	WARN_ON(!dentry->d_inode);
2781 	if (WARN_ON(dentry == target))
2782 		return;
2783 
2784 	BUG_ON(d_ancestor(target, dentry));
2785 	old_parent = dentry->d_parent;
2786 	p = d_ancestor(old_parent, target);
2787 	if (IS_ROOT(dentry)) {
2788 		BUG_ON(p);
2789 		spin_lock(&target->d_parent->d_lock);
2790 	} else if (!p) {
2791 		/* target is not a descendent of dentry->d_parent */
2792 		spin_lock(&target->d_parent->d_lock);
2793 		spin_lock_nested(&old_parent->d_lock, DENTRY_D_LOCK_NESTED);
2794 	} else {
2795 		BUG_ON(p == dentry);
2796 		spin_lock(&old_parent->d_lock);
2797 		if (p != target)
2798 			spin_lock_nested(&target->d_parent->d_lock,
2799 					DENTRY_D_LOCK_NESTED);
2800 	}
2801 	spin_lock_nested(&dentry->d_lock, 2);
2802 	spin_lock_nested(&target->d_lock, 3);
2803 
2804 	if (unlikely(d_in_lookup(target))) {
2805 		dir = target->d_parent->d_inode;
2806 		n = start_dir_add(dir);
2807 		d_wait = __d_lookup_unhash(target);
2808 	}
2809 
2810 	write_seqcount_begin(&dentry->d_seq);
2811 	write_seqcount_begin_nested(&target->d_seq, DENTRY_D_LOCK_NESTED);
2812 
2813 	/* unhash both */
2814 	if (!d_unhashed(dentry))
2815 		___d_drop(dentry);
2816 	if (!d_unhashed(target))
2817 		___d_drop(target);
2818 
2819 	/* ... and switch them in the tree */
2820 	dentry->d_parent = target->d_parent;
2821 	if (!exchange) {
2822 		copy_name(dentry, target);
2823 		target->d_hash.pprev = NULL;
2824 		dentry->d_parent->d_lockref.count++;
2825 		if (dentry != old_parent) /* wasn't IS_ROOT */
2826 			WARN_ON(!--old_parent->d_lockref.count);
2827 	} else {
2828 		target->d_parent = old_parent;
2829 		swap_names(dentry, target);
2830 		if (!hlist_unhashed(&target->d_sib))
2831 			__hlist_del(&target->d_sib);
2832 		hlist_add_head(&target->d_sib, &target->d_parent->d_children);
2833 		__d_rehash(target);
2834 		fsnotify_update_flags(target);
2835 	}
2836 	if (!hlist_unhashed(&dentry->d_sib))
2837 		__hlist_del(&dentry->d_sib);
2838 	hlist_add_head(&dentry->d_sib, &dentry->d_parent->d_children);
2839 	__d_rehash(dentry);
2840 	fsnotify_update_flags(dentry);
2841 	fscrypt_handle_d_move(dentry);
2842 
2843 	write_seqcount_end(&target->d_seq);
2844 	write_seqcount_end(&dentry->d_seq);
2845 
2846 	if (dir)
2847 		end_dir_add(dir, n, d_wait);
2848 
2849 	if (dentry->d_parent != old_parent)
2850 		spin_unlock(&dentry->d_parent->d_lock);
2851 	if (dentry != old_parent)
2852 		spin_unlock(&old_parent->d_lock);
2853 	spin_unlock(&target->d_lock);
2854 	spin_unlock(&dentry->d_lock);
2855 }
2856 
2857 /*
2858  * d_move - move a dentry
2859  * @dentry: entry to move
2860  * @target: new dentry
2861  *
2862  * Update the dcache to reflect the move of a file name. Negative
2863  * dcache entries should not be moved in this way. See the locking
2864  * requirements for __d_move.
2865  */
2866 void d_move(struct dentry *dentry, struct dentry *target)
2867 {
2868 	write_seqlock(&rename_lock);
2869 	__d_move(dentry, target, false);
2870 	write_sequnlock(&rename_lock);
2871 }
2872 EXPORT_SYMBOL(d_move);
2873 
2874 /*
2875  * d_exchange - exchange two dentries
2876  * @dentry1: first dentry
2877  * @dentry2: second dentry
2878  */
2879 void d_exchange(struct dentry *dentry1, struct dentry *dentry2)
2880 {
2881 	write_seqlock(&rename_lock);
2882 
2883 	WARN_ON(!dentry1->d_inode);
2884 	WARN_ON(!dentry2->d_inode);
2885 	WARN_ON(IS_ROOT(dentry1));
2886 	WARN_ON(IS_ROOT(dentry2));
2887 
2888 	__d_move(dentry1, dentry2, true);
2889 
2890 	write_sequnlock(&rename_lock);
2891 }
2892 
2893 /**
2894  * d_ancestor - search for an ancestor
2895  * @p1: ancestor dentry
2896  * @p2: child dentry
2897  *
2898  * Returns the ancestor dentry of p2 which is a child of p1, if p1 is
2899  * an ancestor of p2, else NULL.
2900  */
2901 struct dentry *d_ancestor(struct dentry *p1, struct dentry *p2)
2902 {
2903 	struct dentry *p;
2904 
2905 	for (p = p2; !IS_ROOT(p); p = p->d_parent) {
2906 		if (p->d_parent == p1)
2907 			return p;
2908 	}
2909 	return NULL;
2910 }
2911 
2912 /*
2913  * This helper attempts to cope with remotely renamed directories
2914  *
2915  * It assumes that the caller is already holding
2916  * dentry->d_parent->d_inode->i_mutex, and rename_lock
2917  *
2918  * Note: If ever the locking in lock_rename() changes, then please
2919  * remember to update this too...
2920  */
2921 static int __d_unalias(struct dentry *dentry, struct dentry *alias)
2922 {
2923 	struct mutex *m1 = NULL;
2924 	struct rw_semaphore *m2 = NULL;
2925 	int ret = -ESTALE;
2926 
2927 	/* If alias and dentry share a parent, then no extra locks required */
2928 	if (alias->d_parent == dentry->d_parent)
2929 		goto out_unalias;
2930 
2931 	/* See lock_rename() */
2932 	if (!mutex_trylock(&dentry->d_sb->s_vfs_rename_mutex))
2933 		goto out_err;
2934 	m1 = &dentry->d_sb->s_vfs_rename_mutex;
2935 	if (!inode_trylock_shared(alias->d_parent->d_inode))
2936 		goto out_err;
2937 	m2 = &alias->d_parent->d_inode->i_rwsem;
2938 out_unalias:
2939 	__d_move(alias, dentry, false);
2940 	ret = 0;
2941 out_err:
2942 	if (m2)
2943 		up_read(m2);
2944 	if (m1)
2945 		mutex_unlock(m1);
2946 	return ret;
2947 }
2948 
2949 /**
2950  * d_splice_alias - splice a disconnected dentry into the tree if one exists
2951  * @inode:  the inode which may have a disconnected dentry
2952  * @dentry: a negative dentry which we want to point to the inode.
2953  *
2954  * If inode is a directory and has an IS_ROOT alias, then d_move that in
2955  * place of the given dentry and return it, else simply d_add the inode
2956  * to the dentry and return NULL.
2957  *
2958  * If a non-IS_ROOT directory is found, the filesystem is corrupt, and
2959  * we should error out: directories can't have multiple aliases.
2960  *
2961  * This is needed in the lookup routine of any filesystem that is exportable
2962  * (via knfsd) so that we can build dcache paths to directories effectively.
2963  *
2964  * If a dentry was found and moved, then it is returned.  Otherwise NULL
2965  * is returned.  This matches the expected return value of ->lookup.
2966  *
2967  * Cluster filesystems may call this function with a negative, hashed dentry.
2968  * In that case, we know that the inode will be a regular file, and also this
2969  * will only occur during atomic_open. So we need to check for the dentry
2970  * being already hashed only in the final case.
2971  */
2972 struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
2973 {
2974 	if (IS_ERR(inode))
2975 		return ERR_CAST(inode);
2976 
2977 	BUG_ON(!d_unhashed(dentry));
2978 
2979 	if (!inode)
2980 		goto out;
2981 
2982 	security_d_instantiate(dentry, inode);
2983 	spin_lock(&inode->i_lock);
2984 	if (S_ISDIR(inode->i_mode)) {
2985 		struct dentry *new = __d_find_any_alias(inode);
2986 		if (unlikely(new)) {
2987 			/* The reference to new ensures it remains an alias */
2988 			spin_unlock(&inode->i_lock);
2989 			write_seqlock(&rename_lock);
2990 			if (unlikely(d_ancestor(new, dentry))) {
2991 				write_sequnlock(&rename_lock);
2992 				dput(new);
2993 				new = ERR_PTR(-ELOOP);
2994 				pr_warn_ratelimited(
2995 					"VFS: Lookup of '%s' in %s %s"
2996 					" would have caused loop\n",
2997 					dentry->d_name.name,
2998 					inode->i_sb->s_type->name,
2999 					inode->i_sb->s_id);
3000 			} else if (!IS_ROOT(new)) {
3001 				struct dentry *old_parent = dget(new->d_parent);
3002 				int err = __d_unalias(dentry, new);
3003 				write_sequnlock(&rename_lock);
3004 				if (err) {
3005 					dput(new);
3006 					new = ERR_PTR(err);
3007 				}
3008 				dput(old_parent);
3009 			} else {
3010 				__d_move(new, dentry, false);
3011 				write_sequnlock(&rename_lock);
3012 			}
3013 			iput(inode);
3014 			return new;
3015 		}
3016 	}
3017 out:
3018 	__d_add(dentry, inode);
3019 	return NULL;
3020 }
3021 EXPORT_SYMBOL(d_splice_alias);
3022 
3023 /*
3024  * Test whether new_dentry is a subdirectory of old_dentry.
3025  *
3026  * Trivially implemented using the dcache structure
3027  */
3028 
3029 /**
3030  * is_subdir - is new dentry a subdirectory of old_dentry
3031  * @new_dentry: new dentry
3032  * @old_dentry: old dentry
3033  *
3034  * Returns true if new_dentry is a subdirectory of the parent (at any depth).
3035  * Returns false otherwise.
3036  * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
3037  */
3038 
3039 bool is_subdir(struct dentry *new_dentry, struct dentry *old_dentry)
3040 {
3041 	bool subdir;
3042 	unsigned seq;
3043 
3044 	if (new_dentry == old_dentry)
3045 		return true;
3046 
3047 	/* Access d_parent under rcu as d_move() may change it. */
3048 	rcu_read_lock();
3049 	seq = read_seqbegin(&rename_lock);
3050 	subdir = d_ancestor(old_dentry, new_dentry);
3051 	 /* Try lockless once... */
3052 	if (read_seqretry(&rename_lock, seq)) {
3053 		/* ...else acquire lock for progress even on deep chains. */
3054 		read_seqlock_excl(&rename_lock);
3055 		subdir = d_ancestor(old_dentry, new_dentry);
3056 		read_sequnlock_excl(&rename_lock);
3057 	}
3058 	rcu_read_unlock();
3059 	return subdir;
3060 }
3061 EXPORT_SYMBOL(is_subdir);
3062 
3063 static enum d_walk_ret d_genocide_kill(void *data, struct dentry *dentry)
3064 {
3065 	struct dentry *root = data;
3066 	if (dentry != root) {
3067 		if (d_unhashed(dentry) || !dentry->d_inode)
3068 			return D_WALK_SKIP;
3069 
3070 		if (!(dentry->d_flags & DCACHE_GENOCIDE)) {
3071 			dentry->d_flags |= DCACHE_GENOCIDE;
3072 			dentry->d_lockref.count--;
3073 		}
3074 	}
3075 	return D_WALK_CONTINUE;
3076 }
3077 
3078 void d_genocide(struct dentry *parent)
3079 {
3080 	d_walk(parent, parent, d_genocide_kill);
3081 }
3082 
3083 void d_mark_tmpfile(struct file *file, struct inode *inode)
3084 {
3085 	struct dentry *dentry = file->f_path.dentry;
3086 
3087 	BUG_ON(dentry->d_name.name != dentry->d_iname ||
3088 		!hlist_unhashed(&dentry->d_u.d_alias) ||
3089 		!d_unlinked(dentry));
3090 	spin_lock(&dentry->d_parent->d_lock);
3091 	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
3092 	dentry->d_name.len = sprintf(dentry->d_iname, "#%llu",
3093 				(unsigned long long)inode->i_ino);
3094 	spin_unlock(&dentry->d_lock);
3095 	spin_unlock(&dentry->d_parent->d_lock);
3096 }
3097 EXPORT_SYMBOL(d_mark_tmpfile);
3098 
3099 void d_tmpfile(struct file *file, struct inode *inode)
3100 {
3101 	struct dentry *dentry = file->f_path.dentry;
3102 
3103 	inode_dec_link_count(inode);
3104 	d_mark_tmpfile(file, inode);
3105 	d_instantiate(dentry, inode);
3106 }
3107 EXPORT_SYMBOL(d_tmpfile);
3108 
3109 /*
3110  * Obtain inode number of the parent dentry.
3111  */
3112 ino_t d_parent_ino(struct dentry *dentry)
3113 {
3114 	struct dentry *parent;
3115 	struct inode *iparent;
3116 	unsigned seq;
3117 	ino_t ret;
3118 
3119 	scoped_guard(rcu) {
3120 		seq = raw_seqcount_begin(&dentry->d_seq);
3121 		parent = READ_ONCE(dentry->d_parent);
3122 		iparent = d_inode_rcu(parent);
3123 		if (likely(iparent)) {
3124 			ret = iparent->i_ino;
3125 			if (!read_seqcount_retry(&dentry->d_seq, seq))
3126 				return ret;
3127 		}
3128 	}
3129 
3130 	spin_lock(&dentry->d_lock);
3131 	ret = dentry->d_parent->d_inode->i_ino;
3132 	spin_unlock(&dentry->d_lock);
3133 	return ret;
3134 }
3135 EXPORT_SYMBOL(d_parent_ino);
3136 
3137 static __initdata unsigned long dhash_entries;
3138 static int __init set_dhash_entries(char *str)
3139 {
3140 	if (!str)
3141 		return 0;
3142 	dhash_entries = simple_strtoul(str, &str, 0);
3143 	return 1;
3144 }
3145 __setup("dhash_entries=", set_dhash_entries);
3146 
3147 static void __init dcache_init_early(void)
3148 {
3149 	/* If hashes are distributed across NUMA nodes, defer
3150 	 * hash allocation until vmalloc space is available.
3151 	 */
3152 	if (hashdist)
3153 		return;
3154 
3155 	dentry_hashtable =
3156 		alloc_large_system_hash("Dentry cache",
3157 					sizeof(struct hlist_bl_head),
3158 					dhash_entries,
3159 					13,
3160 					HASH_EARLY | HASH_ZERO,
3161 					&d_hash_shift,
3162 					NULL,
3163 					0,
3164 					0);
3165 	d_hash_shift = 32 - d_hash_shift;
3166 
3167 	runtime_const_init(shift, d_hash_shift);
3168 	runtime_const_init(ptr, dentry_hashtable);
3169 }
3170 
3171 static void __init dcache_init(void)
3172 {
3173 	/*
3174 	 * A constructor could be added for stable state like the lists,
3175 	 * but it is probably not worth it because of the cache nature
3176 	 * of the dcache.
3177 	 */
3178 	dentry_cache = KMEM_CACHE_USERCOPY(dentry,
3179 		SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_ACCOUNT,
3180 		d_iname);
3181 
3182 	/* Hash may have been set up in dcache_init_early */
3183 	if (!hashdist)
3184 		return;
3185 
3186 	dentry_hashtable =
3187 		alloc_large_system_hash("Dentry cache",
3188 					sizeof(struct hlist_bl_head),
3189 					dhash_entries,
3190 					13,
3191 					HASH_ZERO,
3192 					&d_hash_shift,
3193 					NULL,
3194 					0,
3195 					0);
3196 	d_hash_shift = 32 - d_hash_shift;
3197 
3198 	runtime_const_init(shift, d_hash_shift);
3199 	runtime_const_init(ptr, dentry_hashtable);
3200 }
3201 
3202 /* SLAB cache for __getname() consumers */
3203 struct kmem_cache *names_cachep __ro_after_init;
3204 EXPORT_SYMBOL(names_cachep);
3205 
3206 void __init vfs_caches_init_early(void)
3207 {
3208 	int i;
3209 
3210 	for (i = 0; i < ARRAY_SIZE(in_lookup_hashtable); i++)
3211 		INIT_HLIST_BL_HEAD(&in_lookup_hashtable[i]);
3212 
3213 	dcache_init_early();
3214 	inode_init_early();
3215 }
3216 
3217 void __init vfs_caches_init(void)
3218 {
3219 	names_cachep = kmem_cache_create_usercopy("names_cache", PATH_MAX, 0,
3220 			SLAB_HWCACHE_ALIGN|SLAB_PANIC, 0, PATH_MAX, NULL);
3221 
3222 	dcache_init();
3223 	inode_init();
3224 	files_init();
3225 	files_maxfiles_init();
3226 	mnt_init();
3227 	bdev_cache_init();
3228 	chrdev_init();
3229 }
3230