dcache.c 95.3 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 36
#include <linux/bit_spinlock.h>
#include <linux/rculist_bl.h>
37
#include <linux/prefetch.h>
38
#include <linux/ratelimit.h>
39
#include <linux/list_lru.h>
40
#include "internal.h"
41
#include "mount.h"
Linus Torvalds's avatar
Linus Torvalds committed
42

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

Al Viro's avatar
Al Viro committed
84
__cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
Linus Torvalds's avatar
Linus Torvalds committed
85

86
EXPORT_SYMBOL(rename_lock);
Linus Torvalds's avatar
Linus Torvalds committed
87

88
static struct kmem_cache *dentry_cache __read_mostly;
Linus Torvalds's avatar
Linus Torvalds committed
89

David Howells's avatar
David Howells committed
90 91 92 93 94
const struct qstr empty_name = QSTR_INIT("", 0);
EXPORT_SYMBOL(empty_name);
const struct qstr slash_name = QSTR_INIT("/", 1);
EXPORT_SYMBOL(slash_name);

Linus Torvalds's avatar
Linus Torvalds committed
95 96 97 98 99 100 101 102 103
/*
 * 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.
 */

104
static unsigned int d_hash_shift __read_mostly;
105

106
static struct hlist_bl_head *dentry_hashtable __read_mostly;
107

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

Al Viro's avatar
Al Viro committed
113 114 115 116 117 118 119 120 121 122 123
#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
124 125 126 127 128
/* Statistics gathering. */
struct dentry_stat_t dentry_stat = {
	.age_limit = 45,
};

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

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

/*
 * 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.
 */
146
static long get_nr_dentry(void)
147 148
{
	int i;
149
	long sum = 0;
150 151 152 153 154
	for_each_possible_cpu(i)
		sum += per_cpu(nr_dentry, i);
	return sum < 0 ? 0 : sum;
}

155 156 157 158 159 160 161 162 163
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;
}

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

173 174 175 176
/*
 * Compare 2 name strings, return 0 if they match, otherwise non-zero.
 * The strings are both count bytes long, and count is non-zero.
 */
177 178 179 180 181 182 183 184 185 186 187 188
#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.
 */
189
static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
190
{
191 192 193
	unsigned long a,b,mask;

	for (;;) {
194
		a = read_word_at_a_time(cs);
195
		b = load_unaligned_zeropad(ct);
196 197 198 199 200 201 202 203 204 205
		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;
	}
206
	mask = bytemask_from_count(tcount);
207
	return unlikely(!!((a ^ b) & mask));
208 209
}

210
#else
211

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

224 225
#endif

226 227 228 229
static inline int dentry_cmp(const struct dentry *dentry, const unsigned char *ct, unsigned tcount)
{
	/*
	 * Be careful about RCU walk racing with rename:
230
	 * use 'READ_ONCE' to fetch the name pointer.
231 232 233 234 235 236 237 238 239 240 241 242 243
	 *
	 * 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)
	 */
244
	const unsigned char *cs = READ_ONCE(dentry->d_name.name);
245

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

249 250 251 252 253 254 255 256 257 258 259 260 261
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
262
static void __d_free(struct rcu_head *head)
Linus Torvalds's avatar
Linus Torvalds committed
263
{
Christoph Hellwig's avatar
Christoph Hellwig committed
264 265
	struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);

266 267 268 269 270 271 272
	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
273 274 275
	kmem_cache_free(dentry_cache, dentry); 
}

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

Al Viro's avatar
Al Viro committed
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 307
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);

308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
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
330 331
static void dentry_free(struct dentry *dentry)
{
332
	WARN_ON(!hlist_unhashed(&dentry->d_u.d_alias));
333 334 335 336 337 338 339
	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
340 341 342 343 344 345 346
	/* 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
347 348
/*
 * Release the dentry's inode, using the filesystem
349
 * d_iput() operation if defined.
Nick Piggin's avatar
Nick Piggin committed
350 351 352
 */
static void dentry_unlink_inode(struct dentry * dentry)
	__releases(dentry->d_lock)
353
	__releases(dentry->d_inode->i_lock)
Nick Piggin's avatar
Nick Piggin committed
354 355
{
	struct inode *inode = dentry->d_inode;
356
	bool hashed = !d_unhashed(dentry);
357

358 359
	if (hashed)
		raw_write_seqcount_begin(&dentry->d_seq);
360
	__d_clear_type_and_inode(dentry);
361
	hlist_del_init(&dentry->d_u.d_alias);
362 363
	if (hashed)
		raw_write_seqcount_end(&dentry->d_seq);
Nick Piggin's avatar
Nick Piggin committed
364
	spin_unlock(&dentry->d_lock);
365
	spin_unlock(&inode->i_lock);
Nick Piggin's avatar
Nick Piggin committed
366 367 368 369 370 371 372 373
	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);
}

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 426
/*
 * 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.
 */
427
static void d_lru_isolate(struct list_lru_one *lru, struct dentry *dentry)
428 429 430 431
{
	D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
	dentry->d_flags &= ~DCACHE_LRU_LIST;
	this_cpu_dec(nr_dentry_unused);
432
	list_lru_isolate(lru, &dentry->d_lru);
433 434
}

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

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

Nick Piggin's avatar
Nick Piggin committed
454 455 456 457 458 459 460 461 462 463 464 465 466
/**
 * 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).
 *
467 468 469
 * __d_drop requires dentry->d_lock
 * ___d_drop doesn't mark dentry as "unhashed"
 *   (dentry->d_hash.pprev will be LIST_POISON2, not NULL).
Nick Piggin's avatar
Nick Piggin committed
470
 */
471
static void ___d_drop(struct dentry *dentry)
Nick Piggin's avatar
Nick Piggin committed
472
{
473
	if (!d_unhashed(dentry)) {
474
		struct hlist_bl_head *b;
475 476 477
		/*
		 * Hashed dentries are normally on the dentry hashtable,
		 * with the exception of those newly allocated by
478
		 * d_obtain_root, which are always IS_ROOT:
479 480
		 */
		if (unlikely(IS_ROOT(dentry)))
481
			b = &dentry->d_sb->s_roots;
482
		else
483
			b = d_hash(dentry->d_name.hash);
484 485 486 487

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

void __d_drop(struct dentry *dentry)
{
	___d_drop(dentry);
	dentry->d_hash.pprev = NULL;
}
Nick Piggin's avatar
Nick Piggin committed
498 499 500 501 502 503 504 505 506 507
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
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 538 539 540 541 542 543 544 545
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
546
static void __dentry_kill(struct dentry *dentry)
547
{
548 549 550
	struct dentry *parent = NULL;
	bool can_free = true;
	if (!IS_ROOT(dentry))
551
		parent = dentry->d_parent;
Nick Piggin's avatar
Nick Piggin committed
552

553 554 555 556 557
	/*
	 * The dentry is now unrecoverably dead to the world.
	 */
	lockref_mark_dead(&dentry->d_lockref);

Sage Weil's avatar
Sage Weil committed
558 559 560 561
	/*
	 * inform the fs via d_prune that this dentry is about to be
	 * unhashed and destroyed.
	 */
562
	if (dentry->d_flags & DCACHE_OP_PRUNE)
Yan, Zheng's avatar
Yan, Zheng committed
563 564
		dentry->d_op->d_prune(dentry);

565 566 567 568
	if (dentry->d_flags & DCACHE_LRU_LIST) {
		if (!(dentry->d_flags & DCACHE_SHRINK_LIST))
			d_lru_del(dentry);
	}
569 570
	/* if it was on the hash then remove it */
	__d_drop(dentry);
Al Viro's avatar
Al Viro committed
571
	dentry_unlist(dentry, parent);
Al Viro's avatar
Al Viro committed
572 573
	if (parent)
		spin_unlock(&parent->d_lock);
574 575 576 577
	if (dentry->d_inode)
		dentry_unlink_inode(dentry);
	else
		spin_unlock(&dentry->d_lock);
Al Viro's avatar
Al Viro committed
578 579 580 581
	this_cpu_dec(nr_dentry);
	if (dentry->d_op && dentry->d_op->d_release)
		dentry->d_op->d_release(dentry);

582 583 584 585 586 587 588 589
	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
590 591 592 593 594 595 596 597
}

/*
 * 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.
 */
598
static struct dentry *dentry_kill(struct dentry *dentry)
Al Viro's avatar
Al Viro committed
599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616
	__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
617
	return parent;
Al Viro's avatar
Al Viro committed
618 619

failed:
620
	spin_unlock(&dentry->d_lock);
Al Viro's avatar
Al Viro committed
621
	return dentry; /* try again with same dentry */
622 623
}

624 625 626 627 628
static inline struct dentry *lock_parent(struct dentry *dentry)
{
	struct dentry *parent = dentry->d_parent;
	if (IS_ROOT(dentry))
		return NULL;
629
	if (unlikely(dentry->d_lockref.count < 0))
630
		return NULL;
631 632 633
	if (likely(spin_trylock(&parent->d_lock)))
		return parent;
	rcu_read_lock();
634
	spin_unlock(&dentry->d_lock);
635
again:
636
	parent = READ_ONCE(dentry->d_parent);
637 638 639 640 641 642 643 644 645 646 647 648 649
	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;
	}
650
	if (parent != dentry) {
651
		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
652 653 654 655 656
		if (unlikely(dentry->d_lockref.count < 0)) {
			spin_unlock(&parent->d_lock);
			parent = NULL;
		}
	} else {
657
		parent = NULL;
658 659
	}
	rcu_read_unlock();
660 661 662
	return parent;
}

663 664 665 666 667 668 669 670 671 672 673 674 675 676 677
/*
 * 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
678
	 * let the dentry count go to zero, so use "put_or_lock".
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 720 721 722 723 724 725 726 727 728 729 730 731
	 */
	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();
732
	d_flags = READ_ONCE(dentry->d_flags);
733
	d_flags &= DCACHE_REFERENCED | DCACHE_LRU_LIST | DCACHE_DISCONNECTED;
734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766

	/* 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
767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794
/* 
 * 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)
{
795
	if (unlikely(!dentry))
Linus Torvalds's avatar
Linus Torvalds committed
796 797 798
		return;

repeat:
799 800
	might_sleep();

801 802 803
	rcu_read_lock();
	if (likely(fast_dput(dentry))) {
		rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
804
		return;
805 806 807 808
	}

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

810 811
	WARN_ON(d_in_lookup(dentry));

812 813 814 815
	/* Unreachable? Get rid of it */
	if (unlikely(d_unhashed(dentry)))
		goto kill_it;

816 817 818
	if (unlikely(dentry->d_flags & DCACHE_DISCONNECTED))
		goto kill_it;

819
	if (unlikely(dentry->d_flags & DCACHE_OP_DELETE)) {
Linus Torvalds's avatar
Linus Torvalds committed
820
		if (dentry->d_op->d_delete(dentry))
Nick Piggin's avatar
Nick Piggin committed
821
			goto kill_it;
Linus Torvalds's avatar
Linus Torvalds committed
822
	}
823

824
	dentry_lru_add(dentry);
825

826
	dentry->d_lockref.count--;
Nick Piggin's avatar
Nick Piggin committed
827
	spin_unlock(&dentry->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
828 829
	return;

830
kill_it:
831
	dentry = dentry_kill(dentry);
832 833
	if (dentry) {
		cond_resched();
834
		goto repeat;
835
	}
Linus Torvalds's avatar
Linus Torvalds committed
836
}
837
EXPORT_SYMBOL(dput);
Linus Torvalds's avatar
Linus Torvalds committed
838 839


Nick Piggin's avatar
Nick Piggin committed
840
/* This must be called with d_lock held */
841
static inline void __dget_dlock(struct dentry *dentry)
Nick Piggin's avatar
Nick Piggin committed
842
{
843
	dentry->d_lockref.count++;
Nick Piggin's avatar
Nick Piggin committed
844 845
}

846
static inline void __dget(struct dentry *dentry)
Linus Torvalds's avatar
Linus Torvalds committed
847
{
848
	lockref_get(&dentry->d_lockref);
Linus Torvalds's avatar
Linus Torvalds committed
849 850
}

Nick Piggin's avatar
Nick Piggin committed
851 852
struct dentry *dget_parent(struct dentry *dentry)
{
853
	int gotref;
Nick Piggin's avatar
Nick Piggin committed
854 855
	struct dentry *ret;

856 857 858 859 860
	/*
	 * Do optimistic parent lookup without any
	 * locking.
	 */
	rcu_read_lock();
861
	ret = READ_ONCE(dentry->d_parent);
862 863 864
	gotref = lockref_get_not_zero(&ret->d_lockref);
	rcu_read_unlock();
	if (likely(gotref)) {
865
		if (likely(ret == READ_ONCE(dentry->d_parent)))
866 867 868 869
			return ret;
		dput(ret);
	}

Nick Piggin's avatar
Nick Piggin committed
870
repeat:
871 872 873 874 875
	/*
	 * Don't need rcu_dereference because we re-check it was correct under
	 * the lock.
	 */
	rcu_read_lock();
Nick Piggin's avatar
Nick Piggin committed
876
	ret = dentry->d_parent;
877 878 879 880
	spin_lock(&ret->d_lock);
	if (unlikely(ret != dentry->d_parent)) {
		spin_unlock(&ret->d_lock);
		rcu_read_unlock();
Nick Piggin's avatar
Nick Piggin committed
881 882
		goto repeat;
	}
883
	rcu_read_unlock();
884 885
	BUG_ON(!ret->d_lockref.count);
	ret->d_lockref.count++;
Nick Piggin's avatar
Nick Piggin committed
886 887 888 889 890
	spin_unlock(&ret->d_lock);
	return ret;
}
EXPORT_SYMBOL(dget_parent);

Linus Torvalds's avatar
Linus Torvalds committed
891 892 893 894 895 896 897 898
/**
 * 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
899 900
 * 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
901
 *
902
 * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
903
 * any other hashed alias over that one.
Linus Torvalds's avatar
Linus Torvalds committed
904
 */
905
static struct dentry *__d_find_alias(struct inode *inode)
Linus Torvalds's avatar
Linus Torvalds committed
906
{
Nick Piggin's avatar
Nick Piggin committed
907
	struct dentry *alias, *discon_alias;
Linus Torvalds's avatar
Linus Torvalds committed
908

Nick Piggin's avatar
Nick Piggin committed
909 910
again:
	discon_alias = NULL;
911
	hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
Nick Piggin's avatar
Nick Piggin committed
912
		spin_lock(&alias->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
913
 		if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
914
			if (IS_ROOT(alias) &&
Nick Piggin's avatar
Nick Piggin committed
915
			    (alias->d_flags & DCACHE_DISCONNECTED)) {
Linus Torvalds's avatar
Linus Torvalds committed
916
				discon_alias = alias;
917
			} else {
918
				__dget_dlock(alias);
Nick Piggin's avatar
Nick Piggin committed
919 920 921 922 923 924 925 926 927 928
				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)) {
929 930 931
			__dget_dlock(alias);
			spin_unlock(&alias->d_lock);
			return alias;
Linus Torvalds's avatar
Linus Torvalds committed
932
		}
Nick Piggin's avatar
Nick Piggin committed
933 934
		spin_unlock(&alias->d_lock);
		goto again;
Linus Torvalds's avatar
Linus Torvalds committed
935
	}
Nick Piggin's avatar
Nick Piggin committed
936
	return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
937 938
}

Nick Piggin's avatar
Nick Piggin committed
939
struct dentry *d_find_alias(struct inode *inode)
Linus Torvalds's avatar
Linus Torvalds committed
940
{
941 942
	struct dentry *de = NULL;

943
	if (!hlist_empty(&inode->i_dentry)) {
944
		spin_lock(&inode->i_lock);
945
		de = __d_find_alias(inode);
946
		spin_unlock(&inode->i_lock);
947
	}
Linus Torvalds's avatar
Linus Torvalds committed
948 949
	return de;
}
950
EXPORT_SYMBOL(d_find_alias);
Linus Torvalds's avatar
Linus Torvalds committed
951 952 953 954 955 956 957

/*
 *	Try to kill dentries associated with this inode.
 * WARNING: you must own a reference to inode.
 */
void d_prune_aliases(struct inode *inode)
{
958
	struct dentry *dentry;
Linus Torvalds's avatar
Linus Torvalds committed
959
restart:
960
	spin_lock(&inode->i_lock);
961
	hlist_for_each_entry(dentry, &inode->i_dentry, d_u.d_alias) {
Linus Torvalds's avatar
Linus Torvalds committed
962
		spin_lock(&dentry->d_lock);
963
		if (!dentry->d_lockref.count) {
964 965 966
			struct dentry *parent = lock_parent(dentry);
			if (likely(!dentry->d_lockref.count)) {
				__dentry_kill(dentry);
967
				dput(parent);
968 969 970 971
				goto restart;
			}
			if (parent)
				spin_unlock(&parent->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
972 973 974
		}
		spin_unlock(&dentry->d_lock);
	}
975
	spin_unlock(&inode->i_lock);
Linus Torvalds's avatar
Linus Torvalds committed
976
}
977
EXPORT_SYMBOL(d_prune_aliases);
Linus Torvalds's avatar
Linus Torvalds committed
978

979
static void shrink_dentry_list(struct list_head *list)
Linus Torvalds's avatar
Linus Torvalds committed
980
{
Al Viro's avatar
Al Viro committed
981
	struct dentry *dentry, *parent;
982

983
	while (!list_empty(list)) {
984
		struct inode *inode;
985
		dentry = list_entry(list->prev, struct dentry, d_lru);
986
		spin_lock(&dentry->d_lock);
987 988
		parent = lock_parent(dentry);

989 990 991 992 993
		/*
		 * 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.
		 */
994
		d_shrink_del(dentry);
995

Linus Torvalds's avatar
Linus Torvalds committed
996 997
		/*
		 * We found an inuse dentry which was not removed from
998
		 * the LRU because of laziness during lookup. Do not free it.
Linus Torvalds's avatar
Linus Torvalds committed
999
		 */
1000
		if (dentry->d_lockref.count > 0) {
1001
			spin_unlock(&dentry->d_lock);
1002 1003
			if (parent)
				spin_unlock(&parent->d_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1004 1005
			continue;
		}
1006

1007 1008 1009 1010

		if (unlikely(dentry->d_flags & DCACHE_DENTRY_KILLED)) {
			bool can_free = dentry->d_flags & DCACHE_MAY_FREE;
			spin_unlock(&dentry->d_lock);
1011 1012
			if (parent)
				spin_unlock(&parent->d_lock);
1013 1014 1015 1016 1017
			if (can_free)
				dentry_free(dentry);
			continue;
		}

1018 1019
		inode = dentry->d_inode;
		if (inode && unlikely(!spin_trylock(&inode->i_lock))) {
1020
			d_shrink_add(dentry, list);
1021
			spin_unlock(&dentry->d_lock);
1022 1023
			if (parent)
				spin_unlock(&parent->d_lock);
Al Viro's avatar
Al Viro committed
1024
			continue;
1025
		}
1026 1027

		__dentry_kill(dentry);
1028

Al Viro's avatar
Al Viro committed
1029 1030 1031 1032 1033 1034 1035
		/*
		 * 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;
1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055
		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;
		}
1056
	}
1057 1058
}

1059 1060
static enum lru_status dentry_lru_isolate(struct list_head *item,
		struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079
{
	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) {
1080
		d_lru_isolate(lru, dentry);
1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110
		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.