dcache.c 94.8 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/*
 * fs/dcache.c
 *
 * Complete reimplementation
 * (C) 1997 Thomas Schoebel-Theuer,
 * with heavy changes by Linus Torvalds
 */

/*
 * Notes on the allocation strategy:
 *
 * The dcache is a master of the icache - whenever a dcache entry
 * exists, the inode will always exist. "iput()" is done either when
 * the dcache entry is deleted or garbage collected.
 */

#include <linux/syscalls.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/fs.h>
21
#include <linux/fsnotify.h>
Linus Torvalds's avatar
Linus Torvalds committed
22 23 24 25
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/hash.h>
#include <linux/cache.h>
26
#include <linux/export.h>
Linus Torvalds's avatar
Linus Torvalds committed
27 28
#include <linux/mount.h>
#include <linux/file.h>
29
#include <linux/uaccess.h>
Linus Torvalds's avatar
Linus Torvalds committed
30 31 32 33
#include <linux/security.h>
#include <linux/seqlock.h>
#include <linux/swap.h>
#include <linux/bootmem.h>
34
#include <linux/fs_struct.h>
35
#include <linux/hardirq.h>
36 37
#include <linux/bit_spinlock.h>
#include <linux/rculist_bl.h>
38
#include <linux/prefetch.h>
39
#include <linux/ratelimit.h>
40
#include <linux/list_lru.h>
41 42
#include <linux/kasan.h>

43
#include "internal.h"
44
#include "mount.h"
Linus Torvalds's avatar
Linus Torvalds committed
45

Nick Piggin's avatar
Nick Piggin committed
46 47
/*
 * Usage:
48
 * dcache->d_inode->i_lock protects:
49
 *   - i_dentry, d_u.d_alias, d_inode of aliases
50 51 52 53
 * dcache_hash_bucket lock protects:
 *   - the dcache hash table
 * s_anon bl list spinlock protects:
 *   - the s_anon list (see __d_drop)
54
 * dentry->d_sb->s_dentry_lru_lock protects:
Nick Piggin's avatar
Nick Piggin committed
55 56 57 58 59
 *   - the dcache lru lists and counters
 * d_lock protects:
 *   - d_flags
 *   - d_name
 *   - d_lru
60
 *   - d_count
Nick Piggin's avatar
Nick Piggin committed
61
 *   - d_unhashed()
Nick Piggin's avatar
Nick Piggin committed
62 63
 *   - d_parent and d_subdirs
 *   - childrens' d_child and d_parent
64
 *   - d_u.d_alias, d_inode
Nick Piggin's avatar
Nick Piggin committed
65 66
 *
 * Ordering:
67
 * dentry->d_inode->i_lock
Nick Piggin's avatar
Nick Piggin committed
68
 *   dentry->d_lock
69
 *     dentry->d_sb->s_dentry_lru_lock
70 71
 *     dcache_hash_bucket lock
 *     s_anon lock
Nick Piggin's avatar
Nick Piggin committed
72
 *
Nick Piggin's avatar
Nick Piggin committed
73 74 75 76 77 78 79
 * If there is an ancestor relationship:
 * dentry->d_parent->...->d_parent->d_lock
 *   ...
 *     dentry->d_parent->d_lock
 *       dentry->d_lock
 *
 * If no ancestor relationship:
Nick Piggin's avatar
Nick Piggin committed
80 81 82 83
 * if (dentry1 < dentry2)
 *   dentry1->d_lock
 *     dentry2->d_lock
 */
84
int sysctl_vfs_cache_pressure __read_mostly = 100;
Linus Torvalds's avatar
Linus Torvalds committed
85 86
EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);

Al Viro's avatar
Al Viro committed
87
__cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
Linus Torvalds's avatar
Linus Torvalds committed
88

89
EXPORT_SYMBOL(rename_lock);
Linus Torvalds's avatar
Linus Torvalds committed
90

91
static struct kmem_cache *dentry_cache __read_mostly;
Linus Torvalds's avatar
Linus Torvalds committed
92 93 94 95 96 97 98 99 100 101

/*
 * This is the single most critical data structure when it comes
 * to the dcache: the hashtable for lookups. Somebody should try
 * to make this good - I've just made it work.
 *
 * This hash-function tries to avoid losing too many bits of hash
 * information, yet avoid using a prime hash-size or similar.
 */

102 103
static unsigned int d_hash_mask __read_mostly;
static unsigned int d_hash_shift __read_mostly;
104

105
static struct hlist_bl_head *dentry_hashtable __read_mostly;
106

107
static inline struct hlist_bl_head *d_hash(unsigned int hash)
108
{
109
	return dentry_hashtable + (hash >> (32 - d_hash_shift));
110 111
}

Al Viro's avatar
Al Viro committed
112 113 114 115 116 117 118 119 120 121 122
#define IN_LOOKUP_SHIFT 10
static struct hlist_bl_head in_lookup_hashtable[1 << IN_LOOKUP_SHIFT];

static inline struct hlist_bl_head *in_lookup_hash(const struct dentry *parent,
					unsigned int hash)
{
	hash += (unsigned long) parent / L1_CACHE_BYTES;
	return in_lookup_hashtable + hash_32(hash, IN_LOOKUP_SHIFT);
}


Linus Torvalds's avatar
Linus Torvalds committed
123 124 125 126 127
/* Statistics gathering. */
struct dentry_stat_t dentry_stat = {
	.age_limit = 45,
};

128
static DEFINE_PER_CPU(long, nr_dentry);
129
static DEFINE_PER_CPU(long, nr_dentry_unused);
130 131

#if defined(CONFIG_SYSCTL) && defined(CONFIG_PROC_FS)
132 133 134 135 136 137 138 139 140 141 142 143 144

/*
 * Here we resort to our own counters instead of using generic per-cpu counters
 * for consistency with what the vfs inode code does. We are expected to harvest
 * better code and performance by having our own specialized counters.
 *
 * Please note that the loop is done over all possible CPUs, not over all online
 * CPUs. The reason for this is that we don't want to play games with CPUs going
 * on and off. If one of them goes off, we will just keep their counters.
 *
 * glommer: See cffbc8a for details, and if you ever intend to change this,
 * please update all vfs counters to match.
 */
145
static long get_nr_dentry(void)
146 147
{
	int i;
148
	long sum = 0;
149 150 151 152 153
	for_each_possible_cpu(i)
		sum += per_cpu(nr_dentry, i);
	return sum < 0 ? 0 : sum;
}

154 155 156 157 158 159 160 161 162
static long get_nr_dentry_unused(void)
{
	int i;
	long sum = 0;
	for_each_possible_cpu(i)
		sum += per_cpu(nr_dentry_unused, i);
	return sum < 0 ? 0 : sum;
}

163
int proc_nr_dentry(struct ctl_table *table, int write, void __user *buffer,
164 165
		   size_t *lenp, loff_t *ppos)
{
166
	dentry_stat.nr_dentry = get_nr_dentry();
167
	dentry_stat.nr_unused = get_nr_dentry_unused();
168
	return proc_doulongvec_minmax(table, write, buffer, lenp, ppos);
169 170 171
}
#endif

172 173 174 175
/*
 * Compare 2 name strings, return 0 if they match, otherwise non-zero.
 * The strings are both count bytes long, and count is non-zero.
 */
176 177 178 179 180 181 182 183 184 185 186 187
#ifdef CONFIG_DCACHE_WORD_ACCESS

#include <asm/word-at-a-time.h>
/*
 * NOTE! 'cs' and 'scount' come from a dentry, so it has a
 * aligned allocation for this particular component. We don't
 * strictly need the load_unaligned_zeropad() safety, but it
 * doesn't hurt either.
 *
 * In contrast, 'ct' and 'tcount' can be from a pathname, and do
 * need the careful unaligned handling.
 */
188
static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
189
{
190 191 192
	unsigned long a,b,mask;

	for (;;) {
193
		a = *(unsigned long *)cs;
194
		b = load_unaligned_zeropad(ct);
195 196 197 198 199 200 201 202 203 204
		if (tcount < sizeof(unsigned long))
			break;
		if (unlikely(a != b))
			return 1;
		cs += sizeof(unsigned long);
		ct += sizeof(unsigned long);
		tcount -= sizeof(unsigned long);
		if (!tcount)
			return 0;
	}
205
	mask = bytemask_from_count(tcount);
206
	return unlikely(!!((a ^ b) & mask));
207 208
}

209
#else
210

211
static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
212
{
213 214 215 216 217 218 219 220 221 222
	do {
		if (*cs != *ct)
			return 1;
		cs++;
		ct++;
		tcount--;
	} while (tcount);
	return 0;
}

223 224
#endif

225 226 227 228
static inline int dentry_cmp(const struct dentry *dentry, const unsigned char *ct, unsigned tcount)
{
	/*
	 * Be careful about RCU walk racing with rename:
229
	 * use 'lockless_dereference' to fetch the name pointer.
230 231 232 233 234 235 236 237 238 239 240 241 242
	 *
	 * NOTE! Even if a rename will mean that the length
	 * was not loaded atomically, we don't care. The
	 * RCU walk will check the sequence count eventually,
	 * and catch it. And we won't overrun the buffer,
	 * because we're reading the name pointer atomically,
	 * and a dentry name is guaranteed to be properly
	 * terminated with a NUL byte.
	 *
	 * End result: even if 'len' is wrong, we'll exit
	 * early because the data cannot match (there can
	 * be no NUL in the ct/tcount data)
	 */
243 244
	const unsigned char *cs = lockless_dereference(dentry->d_name.name);

245
	return dentry_string_cmp(cs, ct, tcount);
246 247
}

248 249 250 251 252 253 254 255 256 257 258 259 260
struct external_name {
	union {
		atomic_t count;
		struct rcu_head head;
	} u;
	unsigned char name[];
};

static inline struct external_name *external_name(struct dentry *dentry)
{
	return container_of(dentry->d_name.name, struct external_name, name[0]);
}

Christoph Hellwig's avatar
Christoph Hellwig committed
261
static void __d_free(struct rcu_head *head)
Linus Torvalds's avatar
Linus Torvalds committed
262
{
Christoph Hellwig's avatar
Christoph Hellwig committed
263 264
	struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);

265 266 267 268 269 270 271
	kmem_cache_free(dentry_cache, dentry); 
}

static void __d_free_external(struct rcu_head *head)
{
	struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);
	kfree(external_name(dentry));
Linus Torvalds's avatar
Linus Torvalds committed
272 273 274
	kmem_cache_free(dentry_cache, dentry); 
}

275 276 277 278 279
static inline int dname_external(const struct dentry *dentry)
{
	return dentry->d_name.name != dentry->d_iname;
}

Al Viro's avatar
Al Viro committed
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
void take_dentry_name_snapshot(struct name_snapshot *name, struct dentry *dentry)
{
	spin_lock(&dentry->d_lock);
	if (unlikely(dname_external(dentry))) {
		struct external_name *p = external_name(dentry);
		atomic_inc(&p->u.count);
		spin_unlock(&dentry->d_lock);
		name->name = p->name;
	} else {
		memcpy(name->inline_name, dentry->d_iname, DNAME_INLINE_LEN);
		spin_unlock(&dentry->d_lock);
		name->name = name->inline_name;
	}
}
EXPORT_SYMBOL(take_dentry_name_snapshot);

void release_dentry_name_snapshot(struct name_snapshot *name)
{
	if (unlikely(name->name != name->inline_name)) {
		struct external_name *p;
		p = container_of(name->name, struct external_name, name[0]);
		if (unlikely(atomic_dec_and_test(&p->u.count)))
			kfree_rcu(p, u.head);
	}
}
EXPORT_SYMBOL(release_dentry_name_snapshot);

307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
static inline void __d_set_inode_and_type(struct dentry *dentry,
					  struct inode *inode,
					  unsigned type_flags)
{
	unsigned flags;

	dentry->d_inode = inode;
	flags = READ_ONCE(dentry->d_flags);
	flags &= ~(DCACHE_ENTRY_TYPE | DCACHE_FALLTHRU);
	flags |= type_flags;
	WRITE_ONCE(dentry->d_flags, flags);
}

static inline void __d_clear_type_and_inode(struct dentry *dentry)
{
	unsigned flags = READ_ONCE(dentry->d_flags);

	flags &= ~(DCACHE_ENTRY_TYPE | DCACHE_FALLTHRU);
	WRITE_ONCE(dentry->d_flags, flags);
	dentry->d_inode = NULL;
}

Al Viro's avatar
Al Viro committed
329 330
static void dentry_free(struct dentry *dentry)
{
331
	WARN_ON(!hlist_unhashed(&dentry->d_u.d_alias));
332 333 334 335 336 337 338
	if (unlikely(dname_external(dentry))) {
		struct external_name *p = external_name(dentry);
		if (likely(atomic_dec_and_test(&p->u.count))) {
			call_rcu(&dentry->d_u.d_rcu, __d_free_external);
			return;
		}
	}
Al Viro's avatar
Al Viro committed
339 340 341 342 343 344 345
	/* if dentry was never visible to RCU, immediate free is OK */
	if (!(dentry->d_flags & DCACHE_RCUACCESS))
		__d_free(&dentry->d_u.d_rcu);
	else
		call_rcu(&dentry->d_u.d_rcu, __d_free);
}

Linus Torvalds's avatar
Linus Torvalds committed
346 347
/*
 * Release the dentry's inode, using the filesystem
348
 * d_iput() operation if defined.
Nick Piggin's avatar
Nick Piggin committed
349 350 351
 */
static void dentry_unlink_inode(struct dentry * dentry)
	__releases(dentry->d_lock)
352
	__releases(dentry->d_inode->i_lock)
Nick Piggin's avatar
Nick Piggin committed
353 354
{
	struct inode *inode = dentry->d_inode;
355
	bool hashed = !d_unhashed(dentry);
356

357 358
	if (hashed)
		raw_write_seqcount_begin(&dentry->d_seq);
359
	__d_clear_type_and_inode(dentry);
360
	hlist_del_init(&dentry->d_u.d_alias);
361 362
	if (hashed)
		raw_write_seqcount_end(&dentry->d_seq);
Nick Piggin's avatar
Nick Piggin committed
363
	spin_unlock(&dentry->d_lock);
364
	spin_unlock(&inode->i_lock);
Nick Piggin's avatar
Nick Piggin committed
365 366 367 368 369 370 371 372
	if (!inode->i_nlink)
		fsnotify_inoderemove(inode);
	if (dentry->d_op && dentry->d_op->d_iput)
		dentry->d_op->d_iput(dentry, inode);
	else
		iput(inode);
}

373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425
/*
 * The DCACHE_LRU_LIST bit is set whenever the 'd_lru' entry
 * is in use - which includes both the "real" per-superblock
 * LRU list _and_ the DCACHE_SHRINK_LIST use.
 *
 * The DCACHE_SHRINK_LIST bit is set whenever the dentry is
 * on the shrink list (ie not on the superblock LRU list).
 *
 * The per-cpu "nr_dentry_unused" counters are updated with
 * the DCACHE_LRU_LIST bit.
 *
 * These helper functions make sure we always follow the
 * rules. d_lock must be held by the caller.
 */
#define D_FLAG_VERIFY(dentry,x) WARN_ON_ONCE(((dentry)->d_flags & (DCACHE_LRU_LIST | DCACHE_SHRINK_LIST)) != (x))
static void d_lru_add(struct dentry *dentry)
{
	D_FLAG_VERIFY(dentry, 0);
	dentry->d_flags |= DCACHE_LRU_LIST;
	this_cpu_inc(nr_dentry_unused);
	WARN_ON_ONCE(!list_lru_add(&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
}

static void d_lru_del(struct dentry *dentry)
{
	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
	dentry->d_flags &= ~DCACHE_LRU_LIST;
	this_cpu_dec(nr_dentry_unused);
	WARN_ON_ONCE(!list_lru_del(&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
}

static void d_shrink_del(struct dentry *dentry)
{
	D_FLAG_VERIFY(dentry, DCACHE_SHRINK_LIST | DCACHE_LRU_LIST);
	list_del_init(&dentry->d_lru);
	dentry->d_flags &= ~(DCACHE_SHRINK_LIST | DCACHE_LRU_LIST);
	this_cpu_dec(nr_dentry_unused);
}

static void d_shrink_add(struct dentry *dentry, struct list_head *list)
{
	D_FLAG_VERIFY(dentry, 0);
	list_add(&dentry->d_lru, list);
	dentry->d_flags |= DCACHE_SHRINK_LIST | DCACHE_LRU_LIST;
	this_cpu_inc(nr_dentry_unused);
}

/*
 * These can only be called under the global LRU lock, ie during the
 * callback for freeing the LRU list. "isolate" removes it from the
 * LRU lists entirely, while shrink_move moves it to the indicated
 * private list.
 */
426
static void d_lru_isolate(struct list_lru_one *lru, struct dentry *dentry)
427 428 429 430
{
	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
	dentry->d_flags &= ~DCACHE_LRU_LIST;
	this_cpu_dec(nr_dentry_unused);
431
	list_lru_isolate(lru, &dentry->d_lru);
432 433
}

434 435
static void d_lru_shrink_move(struct list_lru_one *lru, struct dentry *dentry,
			      struct list_head *list)
436 437 438
{
	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
	dentry->d_flags |= DCACHE_SHRINK_LIST;
439
	list_lru_isolate_move(lru, &dentry->d_lru, list);
440 441
}

442
/*
443
 * dentry_lru_(add|del)_list) must be called with d_lock held.
444 445 446
 */
static void dentry_lru_add(struct dentry *dentry)
{
447 448
	if (unlikely(!(dentry->d_flags & DCACHE_LRU_LIST)))
		d_lru_add(dentry);
449 450
	else if (unlikely(!(dentry->d_flags & DCACHE_REFERENCED)))
		dentry->d_flags |= DCACHE_REFERENCED;
451 452
}

Nick Piggin's avatar
Nick Piggin committed
453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469
/**
 * d_drop - drop a dentry
 * @dentry: dentry to drop
 *
 * d_drop() unhashes the entry from the parent dentry hashes, so that it won't
 * be found through a VFS lookup any more. Note that this is different from
 * deleting the dentry - d_delete will try to mark the dentry negative if
 * possible, giving a successful _negative_ lookup, while d_drop will
 * just make the cache lookup fail.
 *
 * d_drop() is used mainly for stuff that wants to invalidate a dentry for some
 * reason (NFS timeouts or autofs deletes).
 *
 * __d_drop requires dentry->d_lock.
 */
void __d_drop(struct dentry *dentry)
{
470
	if (!d_unhashed(dentry)) {
471
		struct hlist_bl_head *b;
472 473 474 475 476 477
		/*
		 * Hashed dentries are normally on the dentry hashtable,
		 * with the exception of those newly allocated by
		 * d_obtain_alias, which are always IS_ROOT:
		 */
		if (unlikely(IS_ROOT(dentry)))
478 479
			b = &dentry->d_sb->s_anon;
		else
480
			b = d_hash(dentry->d_name.hash);
481 482 483 484 485

		hlist_bl_lock(b);
		__hlist_bl_del(&dentry->d_hash);
		dentry->d_hash.pprev = NULL;
		hlist_bl_unlock(b);
486 487
		/* After this call, in-progress rcu-walk path lookup will fail. */
		write_seqcount_invalidate(&dentry->d_seq);
Nick Piggin's avatar
Nick Piggin committed
488 489 490 491 492 493 494 495 496 497 498 499
	}
}
EXPORT_SYMBOL(__d_drop);

void d_drop(struct dentry *dentry)
{
	spin_lock(&dentry->d_lock);
	__d_drop(dentry);
	spin_unlock(&dentry->d_lock);
}
EXPORT_SYMBOL(d_drop);

Al Viro's avatar
Al Viro committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537
static inline void dentry_unlist(struct dentry *dentry, struct dentry *parent)
{
	struct dentry *next;
	/*
	 * Inform d_walk() and shrink_dentry_list() that we are no longer
	 * attached to the dentry tree
	 */
	dentry->d_flags |= DCACHE_DENTRY_KILLED;
	if (unlikely(list_empty(&dentry->d_child)))
		return;
	__list_del_entry(&dentry->d_child);
	/*
	 * Cursors can move around the list of children.  While we'd been
	 * a normal list member, it didn't matter - ->d_child.next would've
	 * been updated.  However, from now on it won't be and for the
	 * things like d_walk() it might end up with a nasty surprise.
	 * Normally d_walk() doesn't care about cursors moving around -
	 * ->d_lock on parent prevents that and since a cursor has no children
	 * of its own, we get through it without ever unlocking the parent.
	 * There is one exception, though - if we ascend from a child that
	 * gets killed as soon as we unlock it, the next sibling is found
	 * using the value left in its ->d_child.next.  And if _that_
	 * pointed to a cursor, and cursor got moved (e.g. by lseek())
	 * before d_walk() regains parent->d_lock, we'll end up skipping
	 * everything the cursor had been moved past.
	 *
	 * Solution: make sure that the pointer left behind in ->d_child.next
	 * points to something that won't be moving around.  I.e. skip the
	 * cursors.
	 */
	while (dentry->d_child.next != &parent->d_subdirs) {
		next = list_entry(dentry->d_child.next, struct dentry, d_child);
		if (likely(!(next->d_flags & DCACHE_DENTRY_CURSOR)))
			break;
		dentry->d_child.next = next->d_child.next;
	}
}

Al Viro's avatar
Al Viro committed
538
static void __dentry_kill(struct dentry *dentry)
539
{
540 541 542
	struct dentry *parent = NULL;
	bool can_free = true;
	if (!IS_ROOT(dentry))
543
		parent = dentry->d_parent;
Nick Piggin's avatar
Nick Piggin committed
544

545 546 547 548 549
	/*
	 * The dentry is now unrecoverably dead to the world.
	 */
	lockref_mark_dead(&dentry->d_lockref);

550 551 552 553
	/*
	 * inform the fs via d_prune that this dentry is about to be
	 * unhashed and destroyed.
	 */
554
	if (dentry->d_flags & DCACHE_OP_PRUNE)
Yan, Zheng's avatar
Yan, Zheng committed
555 556
		dentry->d_op->d_prune(dentry);

557 558 559 560
	if (dentry->d_flags & DCACHE_LRU_LIST) {
		if (!(dentry->d_flags & DCACHE_SHRINK_LIST))
			d_lru_del(dentry);
	}
561 562
	/* if it was on the hash then remove it */
	__d_drop(dentry);
Al Viro's avatar
Al Viro committed
563
	dentry_unlist(dentry, parent);
Al Viro's avatar
Al Viro committed
564 565
	if (parent)
		spin_unlock(&parent->d_lock);
566 567 568 569
	if (dentry->d_inode)
		dentry_unlink_inode(dentry);
	else
		spin_unlock(&dentry->d_lock);
Al Viro's avatar
Al Viro committed
570 571 572 573
	this_cpu_dec(nr_dentry);
	if (dentry->d_op && dentry->d_op->d_release)
		dentry->d_op->d_release(dentry);

574 575 576 577 578 579 580 581
	spin_lock(&dentry->d_lock);
	if (dentry->d_flags & DCACHE_SHRINK_LIST) {
		dentry->d_flags |= DCACHE_MAY_FREE;
		can_free = false;
	}
	spin_unlock(&dentry->d_lock);
	if (likely(can_free))
		dentry_free(dentry);
Al Viro's avatar
Al Viro committed
582 583 584 585 586 587 588 589
}

/*
 * Finish off a dentry we've decided to kill.
 * dentry->d_lock must be held, returns with it unlocked.
 * If ref is non-zero, then decrement the refcount too.
 * Returns dentry requiring refcount drop, or NULL if we're done.
 */
590
static struct dentry *dentry_kill(struct dentry *dentry)
Al Viro's avatar
Al Viro committed
591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608
	__releases(dentry->d_lock)
{
	struct inode *inode = dentry->d_inode;
	struct dentry *parent = NULL;

	if (inode && unlikely(!spin_trylock(&inode->i_lock)))
		goto failed;

	if (!IS_ROOT(dentry)) {
		parent = dentry->d_parent;
		if (unlikely(!spin_trylock(&parent->d_lock))) {
			if (inode)
				spin_unlock(&inode->i_lock);
			goto failed;
		}
	}

	__dentry_kill(dentry);
Al Viro's avatar
Al Viro committed
609
	return parent;
Al Viro's avatar
Al Viro committed
610 611

failed:
612
	spin_unlock(&dentry->d_lock);
Al Viro's avatar
Al Viro committed
613
	return dentry; /* try again with same dentry */
614 615
}

616 617 618 619 620
static inline struct dentry *lock_parent(struct dentry *dentry)
{
	struct dentry *parent = dentry->d_parent;
	if (IS_ROOT(dentry))
		return NULL;
621
	if (unlikely(dentry->d_lockref.count < 0))
622
		return NULL;
623 624 625
	if (likely(spin_trylock(&parent->d_lock)))
		return parent;
	rcu_read_lock();
626
	spin_unlock(&dentry->d_lock);
627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
again:
	parent = ACCESS_ONCE(dentry->d_parent);
	spin_lock(&parent->d_lock);
	/*
	 * We can't blindly lock dentry until we are sure
	 * that we won't violate the locking order.
	 * Any changes of dentry->d_parent must have
	 * been done with parent->d_lock held, so
	 * spin_lock() above is enough of a barrier
	 * for checking if it's still our child.
	 */
	if (unlikely(parent != dentry->d_parent)) {
		spin_unlock(&parent->d_lock);
		goto again;
	}
	rcu_read_unlock();
	if (parent != dentry)
644
		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
645 646 647 648 649
	else
		parent = NULL;
	return parent;
}

650 651 652 653 654 655 656 657 658 659 660 661 662 663 664
/*
 * Try to do a lockless dput(), and return whether that was successful.
 *
 * If unsuccessful, we return false, having already taken the dentry lock.
 *
 * The caller needs to hold the RCU read lock, so that the dentry is
 * guaranteed to stay around even if the refcount goes down to zero!
 */
static inline bool fast_dput(struct dentry *dentry)
{
	int ret;
	unsigned int d_flags;

	/*
	 * If we have a d_op->d_delete() operation, we sould not
665
	 * let the dentry count go to zero, so use "put_or_lock".
666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719
	 */
	if (unlikely(dentry->d_flags & DCACHE_OP_DELETE))
		return lockref_put_or_lock(&dentry->d_lockref);

	/*
	 * .. otherwise, we can try to just decrement the
	 * lockref optimistically.
	 */
	ret = lockref_put_return(&dentry->d_lockref);

	/*
	 * If the lockref_put_return() failed due to the lock being held
	 * by somebody else, the fast path has failed. We will need to
	 * get the lock, and then check the count again.
	 */
	if (unlikely(ret < 0)) {
		spin_lock(&dentry->d_lock);
		if (dentry->d_lockref.count > 1) {
			dentry->d_lockref.count--;
			spin_unlock(&dentry->d_lock);
			return 1;
		}
		return 0;
	}

	/*
	 * If we weren't the last ref, we're done.
	 */
	if (ret)
		return 1;

	/*
	 * Careful, careful. The reference count went down
	 * to zero, but we don't hold the dentry lock, so
	 * somebody else could get it again, and do another
	 * dput(), and we need to not race with that.
	 *
	 * However, there is a very special and common case
	 * where we don't care, because there is nothing to
	 * do: the dentry is still hashed, it does not have
	 * a 'delete' op, and it's referenced and already on
	 * the LRU list.
	 *
	 * NOTE! Since we aren't locked, these values are
	 * not "stable". However, it is sufficient that at
	 * some point after we dropped the reference the
	 * dentry was hashed and the flags had the proper
	 * value. Other dentry users may have re-gotten
	 * a reference to the dentry and change that, but
	 * our work is done - we can leave the dentry
	 * around with a zero refcount.
	 */
	smp_rmb();
	d_flags = ACCESS_ONCE(dentry->d_flags);
720
	d_flags &= DCACHE_REFERENCED | DCACHE_LRU_LIST | DCACHE_DISCONNECTED;
721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753

	/* Nothing to do? Dropping the reference was all we needed? */
	if (d_flags == (DCACHE_REFERENCED | DCACHE_LRU_LIST) && !d_unhashed(dentry))
		return 1;

	/*
	 * Not the fast normal case? Get the lock. We've already decremented
	 * the refcount, but we'll need to re-check the situation after
	 * getting the lock.
	 */
	spin_lock(&dentry->d_lock);

	/*
	 * Did somebody else grab a reference to it in the meantime, and
	 * we're no longer the last user after all? Alternatively, somebody
	 * else could have killed it and marked it dead. Either way, we
	 * don't need to do anything else.
	 */
	if (dentry->d_lockref.count) {
		spin_unlock(&dentry->d_lock);
		return 1;
	}

	/*
	 * Re-get the reference we optimistically dropped. We hold the
	 * lock, and we just tested that it was zero, so we can just
	 * set it to 1.
	 */
	dentry->d_lockref.count = 1;
	return 0;
}


Linus Torvalds's avatar
Linus Torvalds committed
754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781
/* 
 * This is dput
 *
 * This is complicated by the fact that we do not want to put
 * dentries that are no longer on any hash chain on the unused
 * list: we'd much rather just get rid of them immediately.
 *
 * However, that implies that we have to traverse the dentry
 * tree upwards to the parents which might _also_ now be
 * scheduled for deletion (it may have been only waiting for
 * its last child to go away).
 *
 * This tail recursion is done by hand as we don't want to depend
 * on the compiler to always get this right (gcc generally doesn't).
 * Real recursion would eat up our stack space.
 */

/*
 * dput - release a dentry
 * @dentry: dentry to release 
 *
 * Release a dentry. This will drop the usage count and if appropriate
 * call the dentry unlink method as well as removing it from the queues and
 * releasing its resources. If the parent dentries were scheduled for release
 * they too may now get deleted.
 */
void dput(struct dentry *dentry)
{
782
	if (unlikely(!dentry))
Linus Torvalds's avatar
Linus Torvalds committed
783 784 785
		return;

repeat:
786 787
	might_sleep();

788 789 790
	rcu_read_lock();
	if (likely(fast_dput(dentry))) {
		rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
791
		return;
792 793 794 795
	}

	/* Slow case: now with the dentry lock held */
	rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
796

797 798
	WARN_ON(d_in_lookup(dentry));

799 800 801 802
	/* Unreachable? Get rid of it */
	if (unlikely(d_unhashed(dentry)))
		goto kill_it;

803 804 805
	if (unlikely(dentry->d_flags & DCACHE_DISCONNECTED))
		goto kill_it;

806
	if (unlikely(dentry->d_flags & DCACHE_OP_DELETE)) {
Linus Torvalds's avatar
Linus Torvalds committed
807
		if (dentry->d_op->d_delete(dentry))
Nick Piggin's avatar
Nick Piggin committed
808
			goto kill_it;
Linus Torvalds's avatar
Linus Torvalds committed
809
	}
810

811
	dentry_lru_add(dentry);
812

813
	dentry->d_lockref.count--;
Nick Piggin's avatar
Nick Piggin committed
814
	spin_unlock(&dentry->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
815 816
	return;

817
kill_it:
818
	dentry = dentry_kill(dentry);
819 820
	if (dentry) {
		cond_resched();
821
		goto repeat;
822
	}
Linus Torvalds's avatar
Linus Torvalds committed
823
}
824
EXPORT_SYMBOL(dput);
Linus Torvalds's avatar
Linus Torvalds committed
825 826


Nick Piggin's avatar
Nick Piggin committed
827
/* This must be called with d_lock held */
828
static inline void __dget_dlock(struct dentry *dentry)
Nick Piggin's avatar
Nick Piggin committed
829
{
830
	dentry->d_lockref.count++;
Nick Piggin's avatar
Nick Piggin committed
831 832
}

833
static inline void __dget(struct dentry *dentry)
Linus Torvalds's avatar
Linus Torvalds committed
834
{
835
	lockref_get(&dentry->d_lockref);
Linus Torvalds's avatar
Linus Torvalds committed
836 837
}

838 839
struct dentry *dget_parent(struct dentry *dentry)
{
840
	int gotref;
841 842
	struct dentry *ret;

843 844 845 846 847 848 849 850 851 852 853 854 855 856
	/*
	 * Do optimistic parent lookup without any
	 * locking.
	 */
	rcu_read_lock();
	ret = ACCESS_ONCE(dentry->d_parent);
	gotref = lockref_get_not_zero(&ret->d_lockref);
	rcu_read_unlock();
	if (likely(gotref)) {
		if (likely(ret == ACCESS_ONCE(dentry->d_parent)))
			return ret;
		dput(ret);
	}

857
repeat:
858 859 860 861 862
	/*
	 * Don't need rcu_dereference because we re-check it was correct under
	 * the lock.
	 */
	rcu_read_lock();
863
	ret = dentry->d_parent;
864 865 866 867
	spin_lock(&ret->d_lock);
	if (unlikely(ret != dentry->d_parent)) {
		spin_unlock(&ret->d_lock);
		rcu_read_unlock();
868 869
		goto repeat;
	}
870
	rcu_read_unlock();
871 872
	BUG_ON(!ret->d_lockref.count);
	ret->d_lockref.count++;
873 874 875 876 877
	spin_unlock(&ret->d_lock);
	return ret;
}
EXPORT_SYMBOL(dget_parent);

Linus Torvalds's avatar
Linus Torvalds committed
878 879 880 881 882 883 884 885
/**
 * d_find_alias - grab a hashed alias of inode
 * @inode: inode in question
 *
 * If inode has a hashed alias, or is a directory and has any alias,
 * acquire the reference to alias and return it. Otherwise return NULL.
 * Notice that if inode is a directory there can be only one alias and
 * it can be unhashed only if it has no children, or if it is the root
886 887
 * of a filesystem, or if the directory was renamed and d_revalidate
 * was the first vfs operation to notice.
Linus Torvalds's avatar
Linus Torvalds committed
888
 *
889
 * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
890
 * any other hashed alias over that one.
Linus Torvalds's avatar
Linus Torvalds committed
891
 */
892
static struct dentry *__d_find_alias(struct inode *inode)
Linus Torvalds's avatar
Linus Torvalds committed
893
{
Nick Piggin's avatar
Nick Piggin committed
894
	struct dentry *alias, *discon_alias;
Linus Torvalds's avatar
Linus Torvalds committed
895

Nick Piggin's avatar
Nick Piggin committed
896 897
again:
	discon_alias = NULL;
898
	hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
Nick Piggin's avatar
Nick Piggin committed
899
		spin_lock(&alias->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
900
 		if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
901
			if (IS_ROOT(alias) &&
Nick Piggin's avatar
Nick Piggin committed
902
			    (alias->d_flags & DCACHE_DISCONNECTED)) {
Linus Torvalds's avatar
Linus Torvalds committed
903
				discon_alias = alias;
904
			} else {
905
				__dget_dlock(alias);
Nick Piggin's avatar
Nick Piggin committed
906 907 908 909 910 911 912 913 914 915
				spin_unlock(&alias->d_lock);
				return alias;
			}
		}
		spin_unlock(&alias->d_lock);
	}
	if (discon_alias) {
		alias = discon_alias;
		spin_lock(&alias->d_lock);
		if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
916 917 918
			__dget_dlock(alias);
			spin_unlock(&alias->d_lock);
			return alias;
Linus Torvalds's avatar
Linus Torvalds committed
919
		}
Nick Piggin's avatar
Nick Piggin committed
920 921
		spin_unlock(&alias->d_lock);
		goto again;
Linus Torvalds's avatar
Linus Torvalds committed
922
	}
Nick Piggin's avatar
Nick Piggin committed
923
	return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
924 925
}

Nick Piggin's avatar
Nick Piggin committed
926
struct dentry *d_find_alias(struct inode *inode)
Linus Torvalds's avatar
Linus Torvalds committed
927
{
928 929
	struct dentry *de = NULL;

930
	if (!hlist_empty(&inode->i_dentry)) {
931
		spin_lock(&inode->i_lock);
932
		de = __d_find_alias(inode);
933
		spin_unlock(&inode->i_lock);
934
	}
Linus Torvalds's avatar
Linus Torvalds committed
935 936
	return de;
}
937
EXPORT_SYMBOL(d_find_alias);
Linus Torvalds's avatar
Linus Torvalds committed
938 939 940 941 942 943 944

/*
 *	Try to kill dentries associated with this inode.
 * WARNING: you must own a reference to inode.
 */
void d_prune_aliases(struct inode *inode)
{
945
	struct dentry *dentry;
Linus Torvalds's avatar
Linus Torvalds committed
946
restart:
947
	spin_lock(&inode->i_lock);
948
	hlist_for_each_entry(dentry, &inode->i_dentry, d_u.d_alias) {
Linus Torvalds's avatar
Linus Torvalds committed
949
		spin_lock(&dentry->d_lock);
950
		if (!dentry->d_lockref.count) {
951 952 953
			struct dentry *parent = lock_parent(dentry);
			if (likely(!dentry->d_lockref.count)) {
				__dentry_kill(dentry);
954
				dput(parent);
955 956 957 958
				goto restart;
			}
			if (parent)
				spin_unlock(&parent->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
959 960 961
		}
		spin_unlock(&dentry->d_lock);
	}
962
	spin_unlock(&inode->i_lock);
Linus Torvalds's avatar
Linus Torvalds committed
963
}
964
EXPORT_SYMBOL(d_prune_aliases);
Linus Torvalds's avatar
Linus Torvalds committed
965

966
static void shrink_dentry_list(struct list_head *list)
Linus Torvalds's avatar
Linus Torvalds committed
967
{
Al Viro's avatar
Al Viro committed
968
	struct dentry *dentry, *parent;
969

970
	while (!list_empty(list)) {
971
		struct inode *inode;
972
		dentry = list_entry(list->prev, struct dentry, d_lru);
973
		spin_lock(&dentry->d_lock);
974 975
		parent = lock_parent(dentry);

976 977 978 979 980
		/*
		 * The dispose list is isolated and dentries are not accounted
		 * to the LRU here, so we can simply remove it from the list
		 * here regardless of whether it is referenced or not.
		 */
981
		d_shrink_del(dentry);
982

Linus Torvalds's avatar
Linus Torvalds committed
983 984
		/*
		 * We found an inuse dentry which was not removed from
985
		 * the LRU because of laziness during lookup. Do not free it.
Linus Torvalds's avatar
Linus Torvalds committed
986
		 */
987
		if (dentry->d_lockref.count > 0) {
988
			spin_unlock(&dentry->d_lock);
989 990
			if (parent)
				spin_unlock(&parent->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
991 992
			continue;
		}
993

994 995 996 997

		if (unlikely(dentry->d_flags & DCACHE_DENTRY_KILLED)) {
			bool can_free = dentry->d_flags & DCACHE_MAY_FREE;
			spin_unlock(&dentry->d_lock);
998 999
			if (parent)
				spin_unlock(&parent->d_lock);
1000 1001 1002 1003 1004
			if (can_free)
				dentry_free(dentry);
			continue;
		}

1005 1006
		inode = dentry->d_inode;
		if (inode && unlikely(!spin_trylock(&inode->i_lock))) {
1007
			d_shrink_add(dentry, list);
1008
			spin_unlock(&dentry->d_lock);
1009 1010
			if (parent)
				spin_unlock(&parent->d_lock);
Al Viro's avatar
Al Viro committed
1011
			continue;
1012
		}
1013 1014

		__dentry_kill(dentry);
1015

Al Viro's avatar
Al Viro committed
1016 1017 1018 1019 1020 1021 1022
		/*
		 * We need to prune ancestors too. This is necessary to prevent
		 * quadratic behavior of shrink_dcache_parent(), but is also
		 * expected to be beneficial in reducing dentry cache
		 * fragmentation.
		 */
		dentry = parent;
1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042
		while (dentry && !lockref_put_or_lock(&dentry->d_lockref)) {
			parent = lock_parent(dentry);
			if (dentry->d_lockref.count != 1) {
				dentry->d_lockref.count--;
				spin_unlock(&dentry->d_lock);
				if (parent)
					spin_unlock(&parent->d_lock);
				break;
			}
			inode = dentry->d_inode;	/* can't be NULL */
			if (unlikely(!spin_trylock(&inode->i_lock))) {
				spin_unlock(&dentry->d_lock);
				if (parent)
					spin_unlock(&parent->d_lock);
				cpu_relax();
				continue;
			}
			__dentry_kill(dentry);
			dentry = parent;
		}
1043
	}
1044 1045
}

1046 1047
static enum lru_status dentry_lru_isolate(struct list_head *item,
		struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066
{
	struct list_head *freeable = arg;
	struct dentry	*dentry = container_of(item, struct dentry, d_lru);


	/*
	 * we are inverting the lru lock/dentry->d_lock here,
	 * so use a trylock. If we fail to get the lock, just skip
	 * it
	 */
	if (!spin_trylock(&dentry->d_lock))
		return LRU_SKIP;

	/*
	 * Referenced dentries are still in use. If they have active
	 * counts, just remove them from the LRU. Otherwise give them
	 * another pass through the LRU.
	 */
	if (dentry->d_lockref.count) {
1067
		d_lru_isolate(lru, dentry);
1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097
		spin_unlock(&dentry->d_lock);
		return LRU_REMOVED;
	}

	if (dentry->d_flags & DCACHE_REFERENCED) {
		dentry->d_flags &= ~DCACHE_REFERENCED;
		spin_unlock(&dentry->d_lock);

		/*
		 * The list move itself will be made by the common LRU code. At
		 * this point, we've dropped the dentry->d_lock but keep the
		 * lru lock. This is safe to do, since every list movement is
		 * protected by the lru lock even if both locks are held.
		 *
		 * This is guaranteed by the fact that all LRU management
		 * functions are intermediated by the LRU API calls like
		 * list_lru_add and list_lru_del. List movement in this file
		 * only ever occur through this functions or through callbacks
		 * like this one, that are called from the LRU API.
		 *
		 * The only exceptions to this are functions like
		 * shrink_dentry_list, and code that first checks for the
		 * DCACHE_SHRINK_LIST flag.  Those are guaranteed to be
		 * operating only with stack provided lists after they are
		 * properly isolated from the main list.  It is thus, always a
		 * local access.
		 */
		return LRU_ROTATE;
	}

1098
	d_lru_shrink_move(lru, dentry, freeable);
1099 1100 1101 1102 1103
	spin_unlock(&dentry->d_lock);

	return LRU_REMOVED;
}

1104
/**
1105 1106
 * prune_dcache_sb - shrink the dcache
 * @sb: superblock
1107
 * @sc: shrink control, passed to list_lru_shrink_walk()
1108
 *
1109 1110
 * Attempt to shrink the superblock dcache LRU by @sc->nr_to_scan entries. This
 * is done when we need more memory and called from the superblock shrinker
1111
 * function.
1112
 *
1113 1114
 * This function may fail to free any resources if all the dentries are in
 * use.
1115
 */
1116
long prune_dcache_sb(struct super_block *sb, struct shrink_control *sc)
1117
{
1118 1119
	LIST_HEAD(dispose);
	long freed;
1120

1121 1122
	freed = list_lru_shrink_walk(&sb->s_dentry_lru, sc,
				     dentry_lru_isolate, &dispose);
1123
	shrink_dentry_list(&dispose);
1124
	return freed;
1125
}
Nick Piggin's avatar
Nick Piggin committed
1126

1127
static enum lru_status dentry_lru_isolate_shrink(struct list_head *item,
1128
		struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1129
{
1130 1131
	struct list_head *freeable = arg;
	struct dentry	*dentry = container_of(item, struct dentry, d_lru);
1132

1133 1134 1135 1136 1137 1138 1139 1140
	/*
	 * we are inverting the lru lock/dentry->d_lock here,
	 * so use a trylock. If we fail to get the lock, just skip
	 * it
	 */
	if (!spin_trylock(&dentry->d_lock))
		return LRU_SKIP;

1141
	d_lru_shrink_move(lru, dentry, freeable);
1142
	spin_unlock(&dentry->d_lock);
1143

1144
	return LRU_REMOVED;
1145 1146
}

1147

Linus Torvalds's avatar
Linus Torvalds committed
1148 1149 1150 1151
/**
 * shrink_dcache_sb - shrink dcache for a superblock
 * @sb: superblock
 *
1152 1153
 * Shrink the dcache for the specified super block. This is used to free
 * the dcache before unmounting a file system.
Linus Torvalds's avatar
Linus Torvalds committed
1154
 */
1155
void shrink_dcache_sb(struct super_block *sb)
Linus Torvalds's avatar
Linus Torvalds committed
1156
{
1157 1158 1159 1160 1161 1162 1163
	long freed;

	do {
		LIST_HEAD(dispose);

		freed = list_lru_walk(&sb->s_dentry_lru,
			dentry_lru_isolate_shrink, &dispose, UINT_MAX);
1164

1165 1166 1167
		this_cpu_sub(nr_dentry_unused, freed);
		shrink_dentry_list(&dispose);
	} while (freed > 0);
Linus Torvalds's avatar
Linus Torvalds committed
1168
}
1169
EXPORT_SYMBOL(shrink_dcache_sb);
Linus Torvalds's avatar
Linus Torvalds committed
1170

Miklos Szeredi's avatar
Miklos Szeredi committed
1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183
/**
 * enum d_walk_ret - action to talke during tree walk
 * @D_WALK_CONTINUE:	contrinue walk
 * @D_WALK_QUIT:	quit walk
 * @D_WALK_NORETRY:	quit when retry is needed
 * @D_WALK_SKIP:	skip this dentry and its children
 */
enum d_walk_ret {
	D_WALK_CONTINUE,
	D_WALK_QUIT,
	D_WALK_NORETRY,
	D_WALK_SKIP,
};
1184

Linus Torvalds's avatar
Linus Torvalds committed
1185
/**
Miklos Szeredi's avatar
Miklos Szeredi committed
1186 1187 1188 1189 1190
 * d_walk - walk the dentry tree
 * @parent:	start of walk
 * @data:	data passed to @enter() and @finish()
 * @enter:	callback when first entering the dentry
 * @finish:	callback when successfully finished the walk
Linus Torvalds's avatar
Linus Torvalds committed
1191
 *
Miklos Szeredi's avatar
Miklos Szeredi committed
1192
 * The @enter() and @finish() callbacks are called with d_lock held.
Linus Torvalds's avatar
Linus Torvalds committed
1193
 */
Miklos Szeredi's avatar
Miklos Szeredi committed
1194 1195 1196
static void d_walk(struct dentry *parent, void *data,
		   enum d_walk_ret (*enter)(void *, struct dentry *),
		   void (*finish)(void *))
Linus Torvalds's avatar
Linus Torvalds committed
1197
{
1198
	struct dentry *this_parent;
Linus Torvalds's avatar
Linus Torvalds committed
1199
	struct list_head *next;
1200
	unsigned seq = 0;
Miklos Szeredi's avatar
Miklos Szeredi committed
1201 1202
	enum d_walk_ret ret;
	bool retry = true;
1203

1204
again:
1205
	read_seqbegin_or_lock(&rename_lock, &seq);
1206
	this_parent = parent;
Nick Piggin's avatar
Nick Piggin committed
1207
	spin_lock(&this_parent->d_lock);
Miklos Szeredi's avatar
Miklos Szeredi committed
1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219

	ret = enter(data, this_parent);
	switch (ret) {
	case D_WALK_CONTINUE:
		break;
	case D_WALK_QUIT:
	case D_WALK_SKIP:
		goto out_unlock;
	case D_WALK_NORETRY:
		retry = false;
		break;
	}
Linus Torvalds's avatar
Linus Torvalds committed
1220 1221 1222 1223 1224
repeat:
	next = this_parent->d_subdirs.next;
resume:
	while (next != &this_parent->d_subdirs) {
		struct list_head *tmp = next;
1225
		struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
Linus Torvalds's avatar
Linus Torvalds committed
1226
		next = tmp->next;
Nick Piggin's avatar
Nick Piggin committed
1227

Al Viro's avatar
Al Viro committed
1228 1229 1230
		if (unlikely(dentry->d_flags & DCACHE_DENTRY_CURSOR))
			continue;

Nick Piggin's avatar
Nick Piggin committed
1231
		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
Miklos Szeredi's avatar
Miklos Szeredi committed
1232 1233 1234 1235 1236 1237

		ret = enter(data, dentry);
		switch (ret) {
		case D_WALK_CONTINUE:
			break;
		case D_WALK_QUIT:
Nick Piggin's avatar
Nick Piggin committed
1238
			spin_unlock(&dentry->d_lock);
Miklos Szeredi's avatar
Miklos Szeredi committed
1239 1240 1241 1242 1243 1244 1245
			goto out_unlock;
		case D_WALK_NORETRY:
			retry = false;
			break;
		case D_WALK_SKIP:
			spin_unlock(&dentry->d_lock);
			continue;
Nick Piggin's avatar
Nick Piggin committed
1246
		}
Miklos Szeredi's avatar
Miklos Szeredi committed
1247

Linus Torvalds's avatar
Linus Torvalds committed
1248
		if (!list_empty(&dentry->d_subdirs)) {
Nick Piggin's avatar
Nick Piggin committed
1249 1250
			spin_unlock(&this_parent->d_lock);
			spin_release(&dentry->d_lock.dep_map, 1, _RET_IP_);
Linus Torvalds's avatar
Linus Torvalds committed
1251
			this_parent = dentry;
Nick Piggin's avatar
Nick Piggin committed
1252
			spin_acquire(&this_parent->d_lock.dep_map, 0, 1, _RET_IP_);
Linus Torvalds's avatar
Linus Torvalds committed
1253 1254
			goto repeat;
		}
Nick Piggin's avatar
Nick Piggin committed
1255
		spin_unlock(&dentry->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1256 1257 1258 1259
	}
	/*
	 * All done at this level ... ascend and resume the search.
	 */
Al Viro's avatar
Al Viro committed
1260 1261
	rcu_read_lock();
ascend:
Linus Torvalds's avatar
Linus Torvalds committed
1262
	if (this_parent != parent) {
1263
		struct dentry *child = this_parent;
1264 1265 1266 1267 1268
		this_parent = child->d_parent;

		spin_unlock(&child->d_lock);
		spin_lock(&this_parent->d_lock);

Al Viro's avatar
Al Viro committed
1269 1270
		/* might go back up the wrong parent if we have had a rename. */
		if (need_seqretry(&rename_lock, seq))
1271
			goto rename_retry;
Al Viro's avatar
Al Viro committed
1272 1273 1274
		/* go into the first sibling still alive */
		do {
			next = child->d_child.next;
Al Viro's avatar
Al Viro committed
1275 1276 1277
			if (next == &this_parent->d_subdirs)
				goto ascend;
			child = list_entry(next, struct dentry, d_child);
Al Viro's avatar
Al Viro committed
1278
		} while (unlikely(child->d_flags & DCACHE_DENTRY_KILLED));
1279
		rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
1280 1281
		goto resume;
	}
Al Viro's avatar
Al Viro committed
1282
	if (need_seqretry(&rename_lock, seq))
1283
		goto rename_retry;
Al Viro's avatar
Al Viro committed
1284
	rcu_read_unlock();
Miklos Szeredi's avatar
Miklos Szeredi committed
1285 1286 1287 1288 1289
	if (finish)
		finish(data);

out_unlock:
	spin_unlock(&this_parent->d_lock);
1290
	done_seqretry(&rename_lock, seq);
Miklos Szeredi's avatar
Miklos Szeredi committed
1291
	return;
1292 1293

rename_retry:
Al Viro's avatar
Al Viro committed
1294 1295 1296
	spin_unlock(&this_parent->d_lock);
	rcu_read_unlock();
	BUG_ON(seq & 1);
Miklos Szeredi's avatar
Miklos Szeredi committed
1297 1298
	if (!retry)
		return;
1299
	seq = 1;
1300
	goto again;
Linus Torvalds's avatar
Linus Torvalds committed
1301
}
Miklos Szeredi's avatar
Miklos Szeredi committed
1302

Ian Kent's avatar
Ian Kent committed
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341
struct check_mount {
	struct vfsmount *mnt;
	unsigned int mounted;
};

static enum d_walk_ret path_check_mount(void *data, struct dentry *dentry)
{
	struct check_mount *info = data;
	struct path path = { .mnt = info->mnt, .dentry = dentry };

	if (likely(!d_mountpoint(dentry)))
		return D_WALK_CONTINUE;
	if (__path_is_mountpoint(&path)) {
		info->mounted = 1;
		return D_WALK_QUIT;
	}
	return D_WALK_CONTINUE;
}

/**
 * path_has_submounts - check for mounts over a dentry in the
 *                      current namespace.
 * @parent: path to check.
 *
 * Return true if the parent or its subdirectories contain
 * a mount point in the current namespace.
 */
int path_has_submounts(const struct path *parent)
{
	struct check_mount data = { .mnt = parent->mnt, .mounted = 0 };

	read_seqlock_excl(&mount_lock);
	d_walk(parent->dentry, &data, path_check_mount, NULL);
	read_sequnlock_excl(&mount_lock);

	return data.mounted;
}
EXPORT_SYMBOL(path_has_submounts);

1342 1343 1344 1345 1346
/*
 * Called by mount code to set a mountpoint and check if the mountpoint is
 * reachable (e.g. NFS can unhash a directory dentry and then the complete
 * subtree can become unreachable).
 *
1347
 * Only one of d_invalidate() and d_set_mounted() must succeed.  For
1348 1349 1350 1351 1352 1353 1354 1355
 * this reason take rename_lock and d_lock on dentry and ancestors.
 */
int d_set_mounted(struct dentry *dentry)
{
	struct dentry *p;
	int ret = -ENOENT;
	write_seqlock(&rename_lock);
	for (p = dentry->d_parent; !IS_ROOT(p); p = p->d_parent) {
1356
		/* Need exclusion wrt. d_invalidate() */
1357 1358 1359 1360 1361 1362 1363 1364 1365
		spin_lock(&p->d_lock);
		if (unlikely(d_unhashed(p))) {
			spin_unlock(&p->d_lock);
			goto out;
		}
		spin_unlock(&p->d_lock);
	}
	spin_lock(&dentry->d_lock);
	if (!d_unlinked(dentry)) {
1366 1367 1368 1369 1370
		ret = -EBUSY;
		if (!d_mountpoint(dentry)) {
			dentry->d_flags |= DCACHE_MOUNTED;
			ret = 0;
		}
1371 1372 1373 1374 1375 1376 1377
	}
 	spin_unlock(&dentry->d_lock);
out:
	write_sequnlock(&rename_lock);
	return ret;
}

Linus Torvalds's avatar
Linus Torvalds committed
1378
/*
1379
 * Search the dentry child list of the specified parent,
Linus Torvalds's avatar
Linus Torvalds committed
1380 1381 1382