brintos / linux-shallow public Read only

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