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