dcache.c 95.3 KB
Newer Older
L
Linus Torvalds 已提交
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>
L
Linus Torvalds 已提交
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>
L
Linus Torvalds 已提交
27 28
#include <linux/mount.h>
#include <linux/file.h>
29
#include <linux/uaccess.h>
L
Linus Torvalds 已提交
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"
L
Linus Torvalds 已提交
42

N
Nick Piggin 已提交
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)
D
Dave Chinner 已提交
51
 * dentry->d_sb->s_dentry_lru_lock protects:
N
Nick Piggin 已提交
52 53 54 55 56
 *   - the dcache lru lists and counters
 * d_lock protects:
 *   - d_flags
 *   - d_name
 *   - d_lru
N
Nick Piggin 已提交
57
 *   - d_count
N
Nick Piggin 已提交
58
 *   - d_unhashed()
N
Nick Piggin 已提交
59 60
 *   - d_parent and d_subdirs
 *   - childrens' d_child and d_parent
61
 *   - d_u.d_alias, d_inode
N
Nick Piggin 已提交
62 63
 *
 * Ordering:
64
 * dentry->d_inode->i_lock
N
Nick Piggin 已提交
65
 *   dentry->d_lock
D
Dave Chinner 已提交
66
 *     dentry->d_sb->s_dentry_lru_lock
67
 *     dcache_hash_bucket lock
68
 *     s_roots lock
N
Nick Piggin 已提交
69
 *
N
Nick Piggin 已提交
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:
N
Nick Piggin 已提交
77 78 79 80
 * if (dentry1 < dentry2)
 *   dentry1->d_lock
 *     dentry2->d_lock
 */
81
int sysctl_vfs_cache_pressure __read_mostly = 100;
L
Linus Torvalds 已提交
82 83
EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);

A
Al Viro 已提交
84
__cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
L
Linus Torvalds 已提交
85

86
EXPORT_SYMBOL(rename_lock);
L
Linus Torvalds 已提交
87

88
static struct kmem_cache *dentry_cache __read_mostly;
L
Linus Torvalds 已提交
89

D
David Howells 已提交
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);

L
Linus Torvalds 已提交
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
}

A
Al Viro 已提交
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);
}


L
Linus Torvalds 已提交
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]);
}

C
Christoph Hellwig 已提交
262
static void __d_free(struct rcu_head *head)
L
Linus Torvalds 已提交
263
{
C
Christoph Hellwig 已提交
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));
L
Linus Torvalds 已提交
273 274 275
	kmem_cache_free(dentry_cache, dentry); 
}

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

A
Al Viro 已提交
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;
}

A
Al Viro 已提交
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;
		}
	}
A
Al Viro 已提交
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);
}

L
Linus Torvalds 已提交
347 348
/*
 * Release the dentry's inode, using the filesystem
349
 * d_iput() operation if defined.
N
Nick Piggin 已提交
350 351 352
 */
static void dentry_unlink_inode(struct dentry * dentry)
	__releases(dentry->d_lock)
353
	__releases(dentry->d_inode->i_lock)
N
Nick Piggin 已提交
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);
N
Nick Piggin 已提交
364
	spin_unlock(&dentry->d_lock);
365
	spin_unlock(&inode->i_lock);
N
Nick Piggin 已提交
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
}

N
Nick Piggin 已提交
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).
N
Nick Piggin 已提交
470
 */
471
static void ___d_drop(struct dentry *dentry)
N
Nick Piggin 已提交
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);
N
Nick Piggin 已提交
490 491
	}
}
492 493 494 495 496 497

void __d_drop(struct dentry *dentry)
{
	___d_drop(dentry);
	dentry->d_hash.pprev = NULL;
}
N
Nick Piggin 已提交
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);

A
Al Viro 已提交
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;
	}
}

A
Al Viro 已提交
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;
N
Nick Piggin 已提交
552

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

S
Sage Weil 已提交
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)
Y
Yan, Zheng 已提交
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);
A
Al Viro 已提交
571
	dentry_unlist(dentry, parent);
A
Al Viro 已提交
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);
A
Al Viro 已提交
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);
A
Al Viro 已提交
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)
A
Al Viro 已提交
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);
A
Al Viro 已提交
617
	return parent;
A
Al Viro 已提交
618 619

failed:
620
	spin_unlock(&dentry->d_lock);
A
Al Viro 已提交
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;
}


L
Linus Torvalds 已提交
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))
L
Linus Torvalds 已提交
796 797 798
		return;

repeat:
799 800
	might_sleep();

801 802 803
	rcu_read_lock();
	if (likely(fast_dput(dentry))) {
		rcu_read_unlock();
L
Linus Torvalds 已提交
804
		return;
805 806 807 808
	}

	/* Slow case: now with the dentry lock held */
	rcu_read_unlock();
L
Linus Torvalds 已提交
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)) {
L
Linus Torvalds 已提交
820
		if (dentry->d_op->d_delete(dentry))
N
Nick Piggin 已提交
821
			goto kill_it;
L
Linus Torvalds 已提交
822
	}
N
Nick Piggin 已提交
823

824
	dentry_lru_add(dentry);
N
Nick Piggin 已提交
825

826
	dentry->d_lockref.count--;
N
Nick Piggin 已提交
827
	spin_unlock(&dentry->d_lock);
L
Linus Torvalds 已提交
828 829
	return;

830
kill_it:
831
	dentry = dentry_kill(dentry);
832 833
	if (dentry) {
		cond_resched();
834
		goto repeat;
835
	}
L
Linus Torvalds 已提交
836
}
837
EXPORT_SYMBOL(dput);
L
Linus Torvalds 已提交
838 839


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

846
static inline void __dget(struct dentry *dentry)
L
Linus Torvalds 已提交
847
{
848
	lockref_get(&dentry->d_lockref);
L
Linus Torvalds 已提交
849 850
}

N
Nick Piggin 已提交
851 852
struct dentry *dget_parent(struct dentry *dentry)
{
853
	int gotref;
N
Nick Piggin 已提交
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);
	}

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

L
Linus Torvalds 已提交
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.
L
Linus Torvalds 已提交
901
 *
902
 * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
903
 * any other hashed alias over that one.
L
Linus Torvalds 已提交
904
 */
905
static struct dentry *__d_find_alias(struct inode *inode)
L
Linus Torvalds 已提交
906
{
N
Nick Piggin 已提交
907
	struct dentry *alias, *discon_alias;
L
Linus Torvalds 已提交
908

N
Nick Piggin 已提交
909 910
again:
	discon_alias = NULL;
911
	hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
N
Nick Piggin 已提交
912
		spin_lock(&alias->d_lock);
L
Linus Torvalds 已提交
913
 		if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
914
			if (IS_ROOT(alias) &&
N
Nick Piggin 已提交
915
			    (alias->d_flags & DCACHE_DISCONNECTED)) {
L
Linus Torvalds 已提交
916
				discon_alias = alias;
917
			} else {
918
				__dget_dlock(alias);
N
Nick Piggin 已提交
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;
L
Linus Torvalds 已提交
932
		}
N
Nick Piggin 已提交
933 934
		spin_unlock(&alias->d_lock);
		goto again;
L
Linus Torvalds 已提交
935
	}
N
Nick Piggin 已提交
936
	return NULL;
L
Linus Torvalds 已提交
937 938
}

N
Nick Piggin 已提交
939
struct dentry *d_find_alias(struct inode *inode)
L
Linus Torvalds 已提交
940
{
D
David Howells 已提交
941 942
	struct dentry *de = NULL;

A
Al Viro 已提交
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);
D
David Howells 已提交
947
	}
L
Linus Torvalds 已提交
948 949
	return de;
}
950
EXPORT_SYMBOL(d_find_alias);
L
Linus Torvalds 已提交
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;
L
Linus Torvalds 已提交
959
restart:
960
	spin_lock(&inode->i_lock);
961
	hlist_for_each_entry(dentry, &inode->i_dentry, d_u.d_alias) {
L
Linus Torvalds 已提交
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);
L
Linus Torvalds 已提交
972 973 974
		}
		spin_unlock(&dentry->d_lock);
	}
975
	spin_unlock(&inode->i_lock);
L
Linus Torvalds 已提交
976
}
977
EXPORT_SYMBOL(d_prune_aliases);
L
Linus Torvalds 已提交
978

C
Christoph Hellwig 已提交
979
static void shrink_dentry_list(struct list_head *list)
L
Linus Torvalds 已提交
980
{
A
Al Viro 已提交
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

L
Linus Torvalds 已提交
996 997
		/*
		 * We found an inuse dentry which was not removed from
998
		 * the LRU because of laziness during lookup. Do not free it.
L
Linus Torvalds 已提交
999
		 */
1000
		if (dentry->d_lockref.count > 0) {
1001
			spin_unlock(&dentry->d_lock);
1002 1003
			if (parent)
				spin_unlock(&parent->d_lock);
L
Linus Torvalds 已提交
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);
A
Al Viro 已提交
1024
			continue;
1025
		}
1026 1027

		__dentry_kill(dentry);
1028

A
Al Viro 已提交
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
	}
C
Christoph Hellwig 已提交
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.
		 */
		return LRU_ROTATE;
	}

1111
	d_lru_shrink_move(lru, dentry, freeable);
1112 1113 1114 1115 1116
	spin_unlock(&dentry->d_lock);

	return LRU_REMOVED;
}

C
Christoph Hellwig 已提交
1117
/**
1118 1119
 * prune_dcache_sb - shrink the dcache
 * @sb: superblock
1120
 * @sc: shrink control, passed to list_lru_shrink_walk()
1121
 *
1122 1123
 * 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
1124
 * function.
C
Christoph Hellwig 已提交
1125
 *
1126 1127
 * This function may fail to free any resources if all the dentries are in
 * use.
C
Christoph Hellwig 已提交
1128
 */
1129
long prune_dcache_sb(struct super_block *sb, struct shrink_control *sc)
C
Christoph Hellwig 已提交
1130
{
1131 1132
	LIST_HEAD(dispose);
	long freed;
C
Christoph Hellwig 已提交
1133

1134 1135
	freed = list_lru_shrink_walk(&sb->s_dentry_lru, sc,
				     dentry_lru_isolate, &dispose);
1136
	shrink_dentry_list(&dispose);
1137
	return freed;
1138
}
N
Nick Piggin 已提交
1139

1140
static enum lru_status dentry_lru_isolate_shrink(struct list_head *item,
1141
		struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1142
{
1143 1144
	struct list_head *freeable = arg;
	struct dentry	*dentry = container_of(item, struct dentry, d_lru);
1145

1146 1147 1148 1149 1150 1151 1152 1153
	/*
	 * 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;

1154
	d_lru_shrink_move(lru, dentry, freeable);
1155
	spin_unlock(&dentry->d_lock);
1156

1157
	return LRU_REMOVED;
1158 1159
}

1160

L
Linus Torvalds 已提交
1161 1162 1163 1164
/**
 * shrink_dcache_sb - shrink dcache for a superblock
 * @sb: superblock
 *
C
Christoph Hellwig 已提交
1165 1166
 * Shrink the dcache for the specified super block. This is used to free
 * the dcache before unmounting a file system.
L
Linus Torvalds 已提交
1167
 */
C
Christoph Hellwig 已提交
1168
void shrink_dcache_sb(struct super_block *sb)
L
Linus Torvalds 已提交
1169
{
1170 1171 1172 1173 1174 1175
	long freed;

	do {
		LIST_HEAD(dispose);

		freed = list_lru_walk(&sb->s_dentry_lru,
1176
			dentry_lru_isolate_shrink, &dispose, 1024);
C
Christoph Hellwig 已提交
1177

1178 1179
		this_cpu_sub(nr_dentry_unused, freed);
		shrink_dentry_list(&dispose);
1180 1181
		cond_resched();
	} while (list_lru_count(&sb->s_dentry_lru) > 0);
L
Linus Torvalds 已提交
1182
}
1183
EXPORT_SYMBOL(shrink_dcache_sb);
L
Linus Torvalds 已提交
1184

M
Miklos Szeredi 已提交
1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197
/**
 * 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,
};
1198

L
Linus Torvalds 已提交
1199
/**
M
Miklos Szeredi 已提交
1200 1201 1202 1203 1204
 * 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
L
Linus Torvalds 已提交
1205
 *
M
Miklos Szeredi 已提交
1206
 * The @enter() and @finish() callbacks are called with d_lock held.
L
Linus Torvalds 已提交
1207
 */
M
Miklos Szeredi 已提交
1208 1209 1210
static void d_walk(struct dentry *parent, void *data,
		   enum d_walk_ret (*enter)(void *, struct dentry *),
		   void (*finish)(void *))
L
Linus Torvalds 已提交
1211
{
1212
	struct dentry *this_parent;
L
Linus Torvalds 已提交
1213
	struct list_head *next;
1214
	unsigned seq = 0;
M
Miklos Szeredi 已提交
1215 1216
	enum d_walk_ret ret;
	bool retry = true;
1217

1218
again:
1219
	read_seqbegin_or_lock(&rename_lock, &seq);
1220
	this_parent = parent;
N
Nick Piggin 已提交
1221
	spin_lock(&this_parent->d_lock);
M
Miklos Szeredi 已提交
1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233

	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;
	}
L
Linus Torvalds 已提交
1234 1235 1236 1237 1238
repeat:
	next = this_parent->d_subdirs.next;
resume:
	while (next != &this_parent->d_subdirs) {
		struct list_head *tmp = next;
1239
		struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
L
Linus Torvalds 已提交
1240
		next = tmp->next;
N
Nick Piggin 已提交
1241

A
Al Viro 已提交
1242 1243 1244
		if (unlikely(dentry->d_flags & DCACHE_DENTRY_CURSOR))
			continue;

N
Nick Piggin 已提交
1245
		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
M
Miklos Szeredi 已提交
1246 1247 1248 1249 1250 1251

		ret = enter(data, dentry);
		switch (ret) {
		case D_WALK_CONTINUE:
			break;
		case D_WALK_QUIT:
N
Nick Piggin 已提交
1252
			spin_unlock(&dentry->d_lock);
M
Miklos Szeredi 已提交
1253 1254 1255 1256 1257 1258 1259
			goto out_unlock;
		case D_WALK_NORETRY:
			retry = false;
			break;
		case D_WALK_SKIP:
			spin_unlock(&dentry->d_lock);
			continue;
N
Nick Piggin 已提交
1260
		}
M
Miklos Szeredi 已提交
1261

L
Linus Torvalds 已提交
1262
		if (!list_empty(&dentry->d_subdirs)) {
N
Nick Piggin 已提交
1263 1264
			spin_unlock(&this_parent->d_lock);
			spin_release(&dentry->d_lock.dep_map, 1, _RET_IP_);
L
Linus Torvalds 已提交
1265
			this_parent = dentry;
N
Nick Piggin 已提交
1266
			spin_acquire(&this_parent->d_lock.dep_map, 0, 1, _RET_IP_);
L
Linus Torvalds 已提交
1267 1268
			goto repeat;
		}
N
Nick Piggin 已提交
1269
		spin_unlock(&dentry->d_lock);
L
Linus Torvalds 已提交
1270 1271 1272 1273
	}
	/*
	 * All done at this level ... ascend and resume the search.
	 */
A
Al Viro 已提交
1274 1275
	rcu_read_lock();
ascend:
L
Linus Torvalds 已提交
1276
	if (this_parent != parent) {
1277
		struct dentry *child = this_parent;
1278 1279 1280 1281 1282
		this_parent = child->d_parent;

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

A
Al Viro 已提交
1283 1284
		/* might go back up the wrong parent if we have had a rename. */
		if (need_seqretry(&rename_lock, seq))
1285
			goto rename_retry;
A
Al Viro 已提交
1286 1287 1288
		/* go into the first sibling still alive */
		do {
			next = child->d_child.next;
A
Al Viro 已提交
1289 1290 1291
			if (next == &this_parent->d_subdirs)
				goto ascend;
			child = list_entry(next, struct dentry, d_child);
A
Al Viro 已提交
1292
		} while (unlikely(child->d_flags & DCACHE_DENTRY_KILLED));
1293
		rcu_read_unlock();
L
Linus Torvalds 已提交
1294 1295
		goto resume;
	}
A
Al Viro 已提交
1296
	if (need_seqretry(&rename_lock, seq))
1297
		goto rename_retry;
A
Al Viro 已提交
1298
	rcu_read_unlock();
M
Miklos Szeredi 已提交
1299 1300 1301 1302 1303
	if (finish)
		finish(data);

out_unlock:
	spin_unlock(&this_parent->d_lock);
1304
	done_seqretry(&rename_lock, seq);
M
Miklos Szeredi 已提交
1305
	return;
1306 1307

rename_retry:
A
Al Viro 已提交
1308 1309 1310
	spin_unlock(&this_parent->d_lock);
	rcu_read_unlock();
	BUG_ON(seq & 1);
M
Miklos Szeredi 已提交
1311 1312
	if (!retry)
		return;
1313
	seq = 1;
1314
	goto again;
L
Linus Torvalds 已提交
1315
}
M
Miklos Szeredi 已提交
1316

I
Ian Kent 已提交
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 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355
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);

1356 1357 1358 1359 1360
/*
 * 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).
 *
1361
 * Only one of d_invalidate() and d_set_mounted() must succeed.  For
1362 1363 1364 1365 1366 1367 1368 1369
 * 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) {
1370
		/* Need exclusion wrt. d_invalidate() */
1371 1372 1373 1374 1375 1376 1377 1378 1379
		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)) {
1380 1381 1382 1383 1384
		ret = -EBUSY;
		if (!d_mountpoint(dentry)) {
			dentry->d_flags |= DCACHE_MOUNTED;
			ret = 0;
		}
1385 1386 1387 1388 1389 1390 1391
	}
 	spin_unlock(&dentry->d_lock);
out:
	write_sequnlock(&rename_lock);
	return ret;
}

L
Linus Torvalds 已提交
1392
/*
1393
 * Search the dentry child list of the specified parent,
L
Linus Torvalds 已提交
1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406
 * and move any unused dentries to the end of the unused
 * list for prune_dcache(). We descend to the next level
 * whenever the d_subdirs list is non-empty and continue
 * searching.
 *
 * It returns zero iff there are no unused children,
 * otherwise  it returns the number of children moved to
 * the end of the unused list. This may not be the total
 * number of unused children, because select_parent can
 * drop the lock and return early due to latency
 * constraints.
 */

M
Miklos Szeredi 已提交
1407 1408 1409 1410 1411
struct select_data {
	struct dentry *start;
	struct list_head dispose;
	int found;
};
N
Nick Piggin 已提交
1412

M
Miklos Szeredi 已提交
1413 1414 1415 1416
static enum d_walk_ret select_collect(void *_data, struct dentry *dentry)
{
	struct select_data *data = _data;
	enum d_walk_ret ret = D_WALK_CONTINUE;
L
Linus Torvalds 已提交
1417

M
Miklos Szeredi 已提交
1418 1419
	if (data->start == dentry)
		goto out;
N
Nick Piggin 已提交
1420

1421
	if (dentry->d_flags & DCACHE_SHRINK_LIST) {
M
Miklos Szeredi 已提交
1422
		data->found++;
1423 1424 1425 1426 1427 1428 1429
	} else {
		if (dentry->d_flags & DCACHE_LRU_LIST)
			d_lru_del(dentry);
		if (!dentry->d_lockref.count) {
			d_shrink_add(dentry, &data->dispose);
			data->found++;
		}
L
Linus Torvalds 已提交
1430
	}
M
Miklos Szeredi 已提交
1431 1432 1433 1434 1435
	/*
	 * We can return to the caller if we have found some (this
	 * ensures forward progress). We'll be coming back to find
	 * the rest.
	 */
1436 1437
	if (!list_empty(&data->dispose))
		ret = need_resched() ? D_WALK_QUIT : D_WALK_NORETRY;
L
Linus Torvalds 已提交
1438
out:
M
Miklos Szeredi 已提交
1439
	return ret;
L
Linus Torvalds 已提交
1440 1441 1442 1443 1444 1445 1446 1447
}

/**
 * shrink_dcache_parent - prune dcache
 * @parent: parent of entries to prune
 *
 * Prune the dcache to remove unused children of the parent dentry.
 */
M
Miklos Szeredi 已提交
1448
void shrink_dcache_parent(struct dentry *parent)
L
Linus Torvalds 已提交
1449
{
M
Miklos Szeredi 已提交
1450 1451
	for (;;) {
		struct select_data data;
L
Linus Torvalds 已提交
1452

M
Miklos Szeredi 已提交
1453 1454 1455 1456 1457 1458 1459 1460 1461
		INIT_LIST_HEAD(&data.dispose);
		data.start = parent;
		data.found = 0;

		d_walk(parent, &data, select_collect, NULL);
		if (!data.found)
			break;

		shrink_dentry_list(&data.dispose);
1462 1463
		cond_resched();
	}
L
Linus Torvalds 已提交
1464
}
1465
EXPORT_SYMBOL(shrink_dcache_parent);
L
Linus Torvalds 已提交
1466

1467
static enum d_walk_ret umount_check(void *_data, struct dentry *dentry)
1468
{
1469 1470 1471
	/* it has busy descendents; complain about those instead */
	if (!list_empty(&dentry->d_subdirs))
		return D_WALK_CONTINUE;
1472

1473 1474 1475 1476 1477 1478
	/* root with refcount 1 is fine */
	if (dentry == _data && dentry->d_lockref.count == 1)
		return D_WALK_CONTINUE;

	printk(KERN_ERR "BUG: Dentry %p{i=%lx,n=%pd} "
			" still in use (%d) [unmount of %s %s]\n",
1479 1480 1481
		       dentry,
		       dentry->d_inode ?
		       dentry->d_inode->i_ino : 0UL,
1482
		       dentry,
1483 1484 1485
		       dentry->d_lockref.count,
		       dentry->d_sb->s_type->name,
		       dentry->d_sb->s_id);
1486 1487 1488 1489 1490 1491 1492 1493 1494 1495
	WARN_ON(1);
	return D_WALK_CONTINUE;
}

static void do_one_tree(struct dentry *dentry)
{
	shrink_dcache_parent(dentry);
	d_walk(dentry, dentry, umount_check, NULL);
	d_drop(dentry);
	dput(dentry);
1496 1497 1498 1499 1500 1501 1502 1503 1504
}

/*
 * destroy the dentries attached to a superblock on unmounting
 */
void shrink_dcache_for_umount(struct super_block *sb)
{
	struct dentry *dentry;

1505
	WARN(down_read_trylock(&sb->s_umount), "s_umount should've been locked");
1506 1507 1508

	dentry = sb->s_root;
	sb->s_root = NULL;
1509
	do_one_tree(dentry);
1510

1511 1512
	while (!hlist_bl_empty(&sb->s_roots)) {
		dentry = dget(hlist_bl_entry(hlist_bl_first(&sb->s_roots), struct dentry, d_hash));
1513
		do_one_tree(dentry);
1514 1515 1516
	}
}

1517 1518 1519 1520 1521
struct detach_data {
	struct select_data select;
	struct dentry *mountpoint;
};
static enum d_walk_ret detach_and_collect(void *_data, struct dentry *dentry)
1522
{
1523
	struct detach_data *data = _data;
1524 1525

	if (d_mountpoint(dentry)) {
1526 1527
		__dget_dlock(dentry);
		data->mountpoint = dentry;
1528 1529 1530
		return D_WALK_QUIT;
	}

1531
	return select_collect(&data->select, dentry);
1532 1533 1534 1535
}

static void check_and_drop(void *_data)
{
1536
	struct detach_data *data = _data;
1537

1538
	if (!data->mountpoint && list_empty(&data->select.dispose))
1539
		__d_drop(data->select.start);
1540 1541 1542
}

/**
1543 1544 1545 1546
 * d_invalidate - detach submounts, prune dcache, and drop
 * @dentry: dentry to invalidate (aka detach, prune and drop)
 *
 * no dcache lock.
1547
 *
1548 1549 1550
 * The final d_drop is done as an atomic operation relative to
 * rename_lock ensuring there are no races with d_set_mounted.  This
 * ensures there are no unhashed dentries on the path to a mountpoint.
1551
 */
1552
void d_invalidate(struct dentry *dentry)
1553
{
1554 1555 1556 1557 1558 1559
	/*
	 * If it's already been dropped, return OK.
	 */
	spin_lock(&dentry->d_lock);
	if (d_unhashed(dentry)) {
		spin_unlock(&dentry->d_lock);
1560
		return;
1561 1562 1563
	}
	spin_unlock(&dentry->d_lock);

1564 1565 1566
	/* Negative dentries can be dropped without further checks */
	if (!dentry->d_inode) {
		d_drop(dentry);
1567
		return;
1568 1569 1570
	}

	for (;;) {
1571
		struct detach_data data;
1572

1573 1574 1575 1576 1577 1578
		data.mountpoint = NULL;
		INIT_LIST_HEAD(&data.select.dispose);
		data.select.start = dentry;
		data.select.found = 0;

		d_walk(dentry, &data, detach_and_collect, check_and_drop);
1579

1580
		if (!list_empty(&data.select.dispose))
1581
			shrink_dentry_list(&data.select.dispose);
1582 1583
		else if (!data.mountpoint)
			return;
1584

1585 1586 1587 1588
		if (data.mountpoint) {
			detach_mounts(data.mountpoint);
			dput(data.mountpoint);
		}
1589 1590 1591
		cond_resched();
	}
}
1592
EXPORT_SYMBOL(d_invalidate);
1593

L
Linus Torvalds 已提交
1594
/**
1595 1596
 * __d_alloc	-	allocate a dcache entry
 * @sb: filesystem it will belong to
L
Linus Torvalds 已提交
1597 1598 1599 1600 1601 1602 1603
 * @name: qstr of the name
 *
 * Allocates a dentry. It returns %NULL if there is insufficient memory
 * available. On a success the dentry is returned. The name passed in is
 * copied and the copy passed in may be reused after this call.
 */
 
1604
struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
L
Linus Torvalds 已提交
1605 1606 1607
{
	struct dentry *dentry;
	char *dname;
M
Miklos Szeredi 已提交
1608
	int err;
L
Linus Torvalds 已提交
1609

1610
	dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
L
Linus Torvalds 已提交
1611 1612 1613
	if (!dentry)
		return NULL;

1614 1615 1616 1617 1618 1619 1620
	/*
	 * We guarantee that the inline name is always NUL-terminated.
	 * This way the memcpy() done by the name switching in rename
	 * will still always have a NUL at the end, even if we might
	 * be overwriting an internal NUL character
	 */
	dentry->d_iname[DNAME_INLINE_LEN-1] = 0;
1621
	if (unlikely(!name)) {
D
David Howells 已提交
1622
		name = &slash_name;
1623 1624
		dname = dentry->d_iname;
	} else if (name->len > DNAME_INLINE_LEN-1) {
1625
		size_t size = offsetof(struct external_name, name[1]);
1626 1627
		struct external_name *p = kmalloc(size + name->len,
						  GFP_KERNEL_ACCOUNT);
1628
		if (!p) {
L
Linus Torvalds 已提交
1629 1630 1631
			kmem_cache_free(dentry_cache, dentry); 
			return NULL;
		}
1632 1633
		atomic_set(&p->u.count, 1);
		dname = p->name;
L
Linus Torvalds 已提交
1634 1635 1636 1637 1638 1639 1640 1641 1642
	} else  {
		dname = dentry->d_iname;
	}	

	dentry->d_name.len = name->len;
	dentry->d_name.hash = name->hash;
	memcpy(dname, name->name, name->len);
	dname[name->len] = 0;

1643
	/* Make sure we always see the terminating NUL character */
1644
	smp_store_release(&dentry->d_name.name, dname); /* ^^^ */
1645

1646
	dentry->d_lockref.count = 1;
1647
	dentry->d_flags = 0;
L
Linus Torvalds 已提交
1648
	spin_lock_init(&dentry->d_lock);
N
Nick Piggin 已提交
1649
	seqcount_init(&dentry->d_seq);
L
Linus Torvalds 已提交
1650
	dentry->d_inode = NULL;
1651 1652
	dentry->d_parent = dentry;
	dentry->d_sb = sb;
L
Linus Torvalds 已提交
1653 1654
	dentry->d_op = NULL;
	dentry->d_fsdata = NULL;
1655
	INIT_HLIST_BL_NODE(&dentry->d_hash);
L
Linus Torvalds 已提交
1656 1657
	INIT_LIST_HEAD(&dentry->d_lru);
	INIT_LIST_HEAD(&dentry->d_subdirs);
1658 1659
	INIT_HLIST_NODE(&dentry->d_u.d_alias);
	INIT_LIST_HEAD(&dentry->d_child);
1660
	d_set_d_op(dentry, dentry->d_sb->s_d_op);
L
Linus Torvalds 已提交
1661

M
Miklos Szeredi 已提交
1662 1663 1664 1665 1666 1667 1668 1669 1670 1671
	if (dentry->d_op && dentry->d_op->d_init) {
		err = dentry->d_op->d_init(dentry);
		if (err) {
			if (dname_external(dentry))
				kfree(external_name(dentry));
			kmem_cache_free(dentry_cache, dentry);
			return NULL;
		}
	}

1672
	this_cpu_inc(nr_dentry);
1673

L
Linus Torvalds 已提交
1674 1675
	return dentry;
}
1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690

/**
 * d_alloc	-	allocate a dcache entry
 * @parent: parent of entry to allocate
 * @name: qstr of the name
 *
 * Allocates a dentry. It returns %NULL if there is insufficient memory
 * available. On a success the dentry is returned. The name passed in is
 * copied and the copy passed in may be reused after this call.
 */
struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
{
	struct dentry *dentry = __d_alloc(parent->d_sb, name);
	if (!dentry)
		return NULL;
1691
	dentry->d_flags |= DCACHE_RCUACCESS;
1692 1693 1694 1695 1696 1697 1698
	spin_lock(&parent->d_lock);
	/*
	 * don't need child lock because it is not subject
	 * to concurrency here
	 */
	__dget_dlock(parent);
	dentry->d_parent = parent;
1699
	list_add(&dentry->d_child, &parent->d_subdirs);
1700 1701 1702 1703
	spin_unlock(&parent->d_lock);

	return dentry;
}
1704
EXPORT_SYMBOL(d_alloc);
L
Linus Torvalds 已提交
1705

1706 1707 1708 1709 1710 1711
struct dentry *d_alloc_anon(struct super_block *sb)
{
	return __d_alloc(sb, NULL);
}
EXPORT_SYMBOL(d_alloc_anon);

A
Al Viro 已提交
1712 1713
struct dentry *d_alloc_cursor(struct dentry * parent)
{
1714
	struct dentry *dentry = d_alloc_anon(parent->d_sb);
A
Al Viro 已提交
1715 1716 1717 1718 1719 1720 1721
	if (dentry) {
		dentry->d_flags |= DCACHE_RCUACCESS | DCACHE_DENTRY_CURSOR;
		dentry->d_parent = dget(parent);
	}
	return dentry;
}

1722 1723 1724 1725 1726 1727 1728 1729
/**
 * d_alloc_pseudo - allocate a dentry (for lookup-less filesystems)
 * @sb: the superblock
 * @name: qstr of the name
 *
 * For a filesystem that just pins its dentries in memory and never
 * performs lookups at all, return an unhashed IS_ROOT dentry.
 */
1730 1731
struct dentry *d_alloc_pseudo(struct super_block *sb, const struct qstr *name)
{
1732
	return __d_alloc(sb, name);
1733 1734 1735
}
EXPORT_SYMBOL(d_alloc_pseudo);

L
Linus Torvalds 已提交
1736 1737 1738 1739 1740
struct dentry *d_alloc_name(struct dentry *parent, const char *name)
{
	struct qstr q;

	q.name = name;
1741
	q.hash_len = hashlen_string(parent, name);
L
Linus Torvalds 已提交
1742 1743
	return d_alloc(parent, &q);
}
1744
EXPORT_SYMBOL(d_alloc_name);
L
Linus Torvalds 已提交
1745

1746 1747
void d_set_d_op(struct dentry *dentry, const struct dentry_operations *op)
{
1748 1749
	WARN_ON_ONCE(dentry->d_op);
	WARN_ON_ONCE(dentry->d_flags & (DCACHE_OP_HASH	|
1750 1751
				DCACHE_OP_COMPARE	|
				DCACHE_OP_REVALIDATE	|
1752
				DCACHE_OP_WEAK_REVALIDATE	|
1753
				DCACHE_OP_DELETE	|
M
Miklos Szeredi 已提交
1754
				DCACHE_OP_REAL));
1755 1756 1757 1758 1759 1760 1761 1762 1763
	dentry->d_op = op;
	if (!op)
		return;
	if (op->d_hash)
		dentry->d_flags |= DCACHE_OP_HASH;
	if (op->d_compare)
		dentry->d_flags |= DCACHE_OP_COMPARE;
	if (op->d_revalidate)
		dentry->d_flags |= DCACHE_OP_REVALIDATE;
1764 1765
	if (op->d_weak_revalidate)
		dentry->d_flags |= DCACHE_OP_WEAK_REVALIDATE;
1766 1767
	if (op->d_delete)
		dentry->d_flags |= DCACHE_OP_DELETE;
S
Sage Weil 已提交
1768 1769
	if (op->d_prune)
		dentry->d_flags |= DCACHE_OP_PRUNE;
M
Miklos Szeredi 已提交
1770 1771
	if (op->d_real)
		dentry->d_flags |= DCACHE_OP_REAL;
1772 1773 1774 1775

}
EXPORT_SYMBOL(d_set_d_op);

1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791

/*
 * d_set_fallthru - Mark a dentry as falling through to a lower layer
 * @dentry - The dentry to mark
 *
 * Mark a dentry as falling through to the lower layer (as set with
 * d_pin_lower()).  This flag may be recorded on the medium.
 */
void d_set_fallthru(struct dentry *dentry)
{
	spin_lock(&dentry->d_lock);
	dentry->d_flags |= DCACHE_FALLTHRU;
	spin_unlock(&dentry->d_lock);
}
EXPORT_SYMBOL(d_set_fallthru);

1792 1793
static unsigned d_flags_for_inode(struct inode *inode)
{
1794
	unsigned add_flags = DCACHE_REGULAR_TYPE;
1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806

	if (!inode)
		return DCACHE_MISS_TYPE;

	if (S_ISDIR(inode->i_mode)) {
		add_flags = DCACHE_DIRECTORY_TYPE;
		if (unlikely(!(inode->i_opflags & IOP_LOOKUP))) {
			if (unlikely(!inode->i_op->lookup))
				add_flags = DCACHE_AUTODIR_TYPE;
			else
				inode->i_opflags |= IOP_LOOKUP;
		}
1807 1808 1809 1810
		goto type_determined;
	}

	if (unlikely(!(inode->i_opflags & IOP_NOFOLLOW))) {
1811
		if (unlikely(inode->i_op->get_link)) {
1812
			add_flags = DCACHE_SYMLINK_TYPE;
1813 1814 1815
			goto type_determined;
		}
		inode->i_opflags |= IOP_NOFOLLOW;
1816 1817
	}

1818 1819 1820 1821
	if (unlikely(!S_ISREG(inode->i_mode)))
		add_flags = DCACHE_SPECIAL_TYPE;

type_determined:
1822 1823 1824 1825 1826
	if (unlikely(IS_AUTOMOUNT(inode)))
		add_flags |= DCACHE_NEED_AUTOMOUNT;
	return add_flags;
}

1827 1828
static void __d_instantiate(struct dentry *dentry, struct inode *inode)
{
1829
	unsigned add_flags = d_flags_for_inode(inode);
1830
	WARN_ON(d_in_lookup(dentry));
1831

N
Nick Piggin 已提交
1832
	spin_lock(&dentry->d_lock);
1833
	hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
1834
	raw_write_seqcount_begin(&dentry->d_seq);
1835
	__d_set_inode_and_type(dentry, inode, add_flags);
1836
	raw_write_seqcount_end(&dentry->d_seq);
A
Al Viro 已提交
1837
	fsnotify_update_flags(dentry);
N
Nick Piggin 已提交
1838
	spin_unlock(&dentry->d_lock);
1839 1840
}

L
Linus Torvalds 已提交
1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857
/**
 * d_instantiate - fill in inode information for a dentry
 * @entry: dentry to complete
 * @inode: inode to attach to this dentry
 *
 * Fill in inode information in the entry.
 *
 * This turns negative dentries into productive full members
 * of society.
 *
 * NOTE! This assumes that the inode count has been incremented
 * (or otherwise set) by the caller to indicate that it is now
 * in use by the dcache.
 */
 
void d_instantiate(struct dentry *entry, struct inode * inode)
{
1858
	BUG_ON(!hlist_unhashed(&entry->d_u.d_alias));
1859
	if (inode) {
1860
		security_d_instantiate(entry, inode);
1861
		spin_lock(&inode->i_lock);
1862
		__d_instantiate(entry, inode);
1863
		spin_unlock(&inode->i_lock);
1864
	}
L
Linus Torvalds 已提交
1865
}
1866
EXPORT_SYMBOL(d_instantiate);
L
Linus Torvalds 已提交
1867

1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878
/**
 * d_instantiate_no_diralias - instantiate a non-aliased dentry
 * @entry: dentry to complete
 * @inode: inode to attach to this dentry
 *
 * Fill in inode information in the entry.  If a directory alias is found, then
 * return an error (and drop inode).  Together with d_materialise_unique() this
 * guarantees that a directory inode may never have more than one alias.
 */
int d_instantiate_no_diralias(struct dentry *entry, struct inode *inode)
{
1879
	BUG_ON(!hlist_unhashed(&entry->d_u.d_alias));
1880

1881
	security_d_instantiate(entry, inode);
1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894
	spin_lock(&inode->i_lock);
	if (S_ISDIR(inode->i_mode) && !hlist_empty(&inode->i_dentry)) {
		spin_unlock(&inode->i_lock);
		iput(inode);
		return -EBUSY;
	}
	__d_instantiate(entry, inode);
	spin_unlock(&inode->i_lock);

	return 0;
}
EXPORT_SYMBOL(d_instantiate_no_diralias);

A
Al Viro 已提交
1895 1896 1897 1898 1899
struct dentry *d_make_root(struct inode *root_inode)
{
	struct dentry *res = NULL;

	if (root_inode) {
1900
		res = d_alloc_anon(root_inode->i_sb);
A
Al Viro 已提交
1901 1902 1903 1904 1905 1906 1907 1908 1909
		if (res)
			d_instantiate(res, root_inode);
		else
			iput(root_inode);
	}
	return res;
}
EXPORT_SYMBOL(d_make_root);

1910 1911 1912 1913
static struct dentry * __d_find_any_alias(struct inode *inode)
{
	struct dentry *alias;

A
Al Viro 已提交
1914
	if (hlist_empty(&inode->i_dentry))
1915
		return NULL;
1916
	alias = hlist_entry(inode->i_dentry.first, struct dentry, d_u.d_alias);
1917 1918 1919 1920
	__dget(alias);
	return alias;
}

1921 1922 1923 1924 1925 1926 1927 1928
/**
 * d_find_any_alias - find any alias for a given inode
 * @inode: inode to find an alias for
 *
 * If any aliases exist for the given inode, take and return a
 * reference for one of them.  If no aliases exist, return %NULL.
 */
struct dentry *d_find_any_alias(struct inode *inode)
1929 1930 1931 1932 1933 1934 1935 1936
{
	struct dentry *de;

	spin_lock(&inode->i_lock);
	de = __d_find_any_alias(inode);
	spin_unlock(&inode->i_lock);
	return de;
}
1937
EXPORT_SYMBOL(d_find_any_alias);
1938

1939 1940 1941
static struct dentry *__d_instantiate_anon(struct dentry *dentry,
					   struct inode *inode,
					   bool disconnected)
1942
{
C
Christoph Hellwig 已提交
1943
	struct dentry *res;
1944
	unsigned add_flags;
1945

1946
	security_d_instantiate(dentry, inode);
1947
	spin_lock(&inode->i_lock);
1948
	res = __d_find_any_alias(inode);
C
Christoph Hellwig 已提交
1949
	if (res) {
1950
		spin_unlock(&inode->i_lock);
1951
		dput(dentry);
C
Christoph Hellwig 已提交
1952 1953 1954 1955
		goto out_iput;
	}

	/* attach a disconnected dentry */
1956 1957 1958 1959
	add_flags = d_flags_for_inode(inode);

	if (disconnected)
		add_flags |= DCACHE_DISCONNECTED;
1960

1961 1962 1963
	spin_lock(&dentry->d_lock);
	__d_set_inode_and_type(dentry, inode, add_flags);
	hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
1964
	if (!disconnected) {
1965 1966 1967
		hlist_bl_lock(&dentry->d_sb->s_roots);
		hlist_bl_add_head(&dentry->d_hash, &dentry->d_sb->s_roots);
		hlist_bl_unlock(&dentry->d_sb->s_roots);
1968
	}
1969
	spin_unlock(&dentry->d_lock);
1970
	spin_unlock(&inode->i_lock);
C
Christoph Hellwig 已提交
1971

1972
	return dentry;
C
Christoph Hellwig 已提交
1973 1974 1975 1976

 out_iput:
	iput(inode);
	return res;
1977
}
1978

1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011
struct dentry *d_instantiate_anon(struct dentry *dentry, struct inode *inode)
{
	return __d_instantiate_anon(dentry, inode, true);
}
EXPORT_SYMBOL(d_instantiate_anon);

static struct dentry *__d_obtain_alias(struct inode *inode, bool disconnected)
{
	struct dentry *tmp;
	struct dentry *res;

	if (!inode)
		return ERR_PTR(-ESTALE);
	if (IS_ERR(inode))
		return ERR_CAST(inode);

	res = d_find_any_alias(inode);
	if (res)
		goto out_iput;

	tmp = d_alloc_anon(inode->i_sb);
	if (!tmp) {
		res = ERR_PTR(-ENOMEM);
		goto out_iput;
	}

	return __d_instantiate_anon(tmp, inode, disconnected);

out_iput:
	iput(inode);
	return res;
}

2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031
/**
 * d_obtain_alias - find or allocate a DISCONNECTED dentry for a given inode
 * @inode: inode to allocate the dentry for
 *
 * Obtain a dentry for an inode resulting from NFS filehandle conversion or
 * similar open by handle operations.  The returned dentry may be anonymous,
 * or may have a full name (if the inode was already in the cache).
 *
 * When called on a directory inode, we must ensure that the inode only ever
 * has one dentry.  If a dentry is found, that is returned instead of
 * allocating a new one.
 *
 * On successful return, the reference to the inode has been transferred
 * to the dentry.  In case of an error the reference on the inode is released.
 * To make it easier to use in export operations a %NULL or IS_ERR inode may
 * be passed in and the error will be propagated to the return value,
 * with a %NULL @inode replaced by ERR_PTR(-ESTALE).
 */
struct dentry *d_obtain_alias(struct inode *inode)
{
2032
	return __d_obtain_alias(inode, true);
2033
}
2034
EXPORT_SYMBOL(d_obtain_alias);
L
Linus Torvalds 已提交
2035

2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052
/**
 * d_obtain_root - find or allocate a dentry for a given inode
 * @inode: inode to allocate the dentry for
 *
 * Obtain an IS_ROOT dentry for the root of a filesystem.
 *
 * We must ensure that directory inodes only ever have one dentry.  If a
 * dentry is found, that is returned instead of allocating a new one.
 *
 * On successful return, the reference to the inode has been transferred
 * to the dentry.  In case of an error the reference on the inode is
 * released.  A %NULL or IS_ERR inode may be passed in and will be the
 * error will be propagate to the return value, with a %NULL @inode
 * replaced by ERR_PTR(-ESTALE).
 */
struct dentry *d_obtain_root(struct inode *inode)
{
2053
	return __d_obtain_alias(inode, false);
2054 2055 2056
}
EXPORT_SYMBOL(d_obtain_root);

2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072
/**
 * d_add_ci - lookup or allocate new dentry with case-exact name
 * @inode:  the inode case-insensitive lookup has found
 * @dentry: the negative dentry that was passed to the parent's lookup func
 * @name:   the case-exact name to be associated with the returned dentry
 *
 * This is to avoid filling the dcache with case-insensitive names to the
 * same inode, only the actual correct case is stored in the dcache for
 * case-insensitive filesystems.
 *
 * For a case-insensitive lookup match and if the the case-exact dentry
 * already exists in in the dcache, use it and return it.
 *
 * If no entry exists with the exact case name, allocate new dentry with
 * the exact case, and return the spliced entry.
 */
2073
struct dentry *d_add_ci(struct dentry *dentry, struct inode *inode,
2074 2075
			struct qstr *name)
{
2076
	struct dentry *found, *res;
2077

C
Christoph Hellwig 已提交
2078 2079 2080 2081
	/*
	 * First check if a dentry matching the name already exists,
	 * if not go ahead and create it now.
	 */
2082
	found = d_hash_and_lookup(dentry->d_parent, name);
2083 2084 2085 2086 2087 2088 2089 2090 2091 2092
	if (found) {
		iput(inode);
		return found;
	}
	if (d_in_lookup(dentry)) {
		found = d_alloc_parallel(dentry->d_parent, name,
					dentry->d_wait);
		if (IS_ERR(found) || !d_in_lookup(found)) {
			iput(inode);
			return found;
2093
		}
2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104
	} else {
		found = d_alloc(dentry->d_parent, name);
		if (!found) {
			iput(inode);
			return ERR_PTR(-ENOMEM);
		} 
	}
	res = d_splice_alias(inode, found);
	if (res) {
		dput(found);
		return res;
2105
	}
2106
	return found;
2107
}
2108
EXPORT_SYMBOL(d_add_ci);
L
Linus Torvalds 已提交
2109

2110

A
Al Viro 已提交
2111 2112 2113
static inline bool d_same_name(const struct dentry *dentry,
				const struct dentry *parent,
				const struct qstr *name)
2114
{
A
Al Viro 已提交
2115 2116 2117 2118
	if (likely(!(parent->d_flags & DCACHE_OP_COMPARE))) {
		if (dentry->d_name.len != name->len)
			return false;
		return dentry_cmp(dentry, name->name, name->len) == 0;
2119
	}
2120
	return parent->d_op->d_compare(dentry,
A
Al Viro 已提交
2121 2122
				       dentry->d_name.len, dentry->d_name.name,
				       name) == 0;
2123 2124
}

N
Nick Piggin 已提交
2125 2126 2127 2128
/**
 * __d_lookup_rcu - search for a dentry (racy, store-free)
 * @parent: parent dentry
 * @name: qstr of name we wish to find
2129
 * @seqp: returns d_seq value at the point where the dentry was found
N
Nick Piggin 已提交
2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142
 * Returns: dentry, or NULL
 *
 * __d_lookup_rcu is the dcache lookup function for rcu-walk name
 * resolution (store-free path walking) design described in
 * Documentation/filesystems/path-lookup.txt.
 *
 * This is not to be used outside core vfs.
 *
 * __d_lookup_rcu must only be used in rcu-walk mode, ie. with vfsmount lock
 * held, and rcu_read_lock held. The returned dentry must not be stored into
 * without taking d_lock and checking d_seq sequence count against @seq
 * returned here.
 *
2143
 * A refcount may be taken on the found dentry with the d_rcu_to_refcount
N
Nick Piggin 已提交
2144 2145 2146 2147 2148 2149
 * function.
 *
 * Alternatively, __d_lookup_rcu may be called again to look up the child of
 * the returned dentry, so long as its parent's seqlock is checked after the
 * child is looked up. Thus, an interlocking stepping of sequence lock checks
 * is formed, giving integrity down the path walk.
2150 2151 2152
 *
 * NOTE! The caller *has* to check the resulting dentry against the sequence
 * number we've returned before using any of the resulting dentry state!
N
Nick Piggin 已提交
2153
 */
2154 2155
struct dentry *__d_lookup_rcu(const struct dentry *parent,
				const struct qstr *name,
2156
				unsigned *seqp)
N
Nick Piggin 已提交
2157
{
2158
	u64 hashlen = name->hash_len;
N
Nick Piggin 已提交
2159
	const unsigned char *str = name->name;
2160
	struct hlist_bl_head *b = d_hash(hashlen_hash(hashlen));
2161
	struct hlist_bl_node *node;
N
Nick Piggin 已提交
2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181
	struct dentry *dentry;

	/*
	 * Note: There is significant duplication with __d_lookup_rcu which is
	 * required to prevent single threaded performance regressions
	 * especially on architectures where smp_rmb (in seqcounts) are costly.
	 * Keep the two functions in sync.
	 */

	/*
	 * The hash list is protected using RCU.
	 *
	 * Carefully use d_seq when comparing a candidate dentry, to avoid
	 * races with d_move().
	 *
	 * It is possible that concurrent renames can mess up our list
	 * walk here and result in missing our dentry, resulting in the
	 * false-negative result. d_lookup() protects against concurrent
	 * renames using rename_lock seqlock.
	 *
2182
	 * See Documentation/filesystems/path-lookup.txt for more details.
N
Nick Piggin 已提交
2183
	 */
2184
	hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
2185
		unsigned seq;
N
Nick Piggin 已提交
2186 2187

seqretry:
2188 2189
		/*
		 * The dentry sequence count protects us from concurrent
2190
		 * renames, and thus protects parent and name fields.
2191 2192
		 *
		 * The caller must perform a seqcount check in order
2193
		 * to do anything useful with the returned dentry.
2194 2195 2196 2197 2198 2199 2200
		 *
		 * NOTE! We do a "raw" seqcount_begin here. That means that
		 * we don't wait for the sequence count to stabilize if it
		 * is in the middle of a sequence change. If we do the slow
		 * dentry compare, we will do seqretries until it is stable,
		 * and if we end up with a successful lookup, we actually
		 * want to exit RCU lookup anyway.
A
Al Viro 已提交
2201 2202 2203
		 *
		 * Note that raw_seqcount_begin still *does* smp_rmb(), so
		 * we are still guaranteed NUL-termination of ->d_name.name.
2204 2205
		 */
		seq = raw_seqcount_begin(&dentry->d_seq);
N
Nick Piggin 已提交
2206 2207
		if (dentry->d_parent != parent)
			continue;
2208 2209
		if (d_unhashed(dentry))
			continue;
2210

2211
		if (unlikely(parent->d_flags & DCACHE_OP_COMPARE)) {
A
Al Viro 已提交
2212 2213
			int tlen;
			const char *tname;
2214 2215
			if (dentry->d_name.hash != hashlen_hash(hashlen))
				continue;
A
Al Viro 已提交
2216 2217 2218 2219 2220
			tlen = dentry->d_name.len;
			tname = dentry->d_name.name;
			/* we want a consistent (name,len) pair */
			if (read_seqcount_retry(&dentry->d_seq, seq)) {
				cpu_relax();
2221 2222
				goto seqretry;
			}
2223
			if (parent->d_op->d_compare(dentry,
A
Al Viro 已提交
2224 2225 2226 2227 2228 2229 2230
						    tlen, tname, name) != 0)
				continue;
		} else {
			if (dentry->d_name.hash_len != hashlen)
				continue;
			if (dentry_cmp(dentry, str, hashlen_len(hashlen)) != 0)
				continue;
N
Nick Piggin 已提交
2231
		}
2232
		*seqp = seq;
A
Al Viro 已提交
2233
		return dentry;
N
Nick Piggin 已提交
2234 2235 2236 2237
	}
	return NULL;
}

L
Linus Torvalds 已提交
2238 2239 2240 2241
/**
 * d_lookup - search for a dentry
 * @parent: parent dentry
 * @name: qstr of name we wish to find
2242
 * Returns: dentry, or NULL
L
Linus Torvalds 已提交
2243
 *
2244 2245 2246 2247
 * d_lookup searches the children of the parent dentry for the name in
 * question. If the dentry is found its reference count is incremented and the
 * dentry is returned. The caller must use dput to free the entry when it has
 * finished using it. %NULL is returned if the dentry does not exist.
L
Linus Torvalds 已提交
2248
 */
A
Al Viro 已提交
2249
struct dentry *d_lookup(const struct dentry *parent, const struct qstr *name)
L
Linus Torvalds 已提交
2250
{
N
Nick Piggin 已提交
2251
	struct dentry *dentry;
2252
	unsigned seq;
L
Linus Torvalds 已提交
2253

2254 2255 2256 2257
	do {
		seq = read_seqbegin(&rename_lock);
		dentry = __d_lookup(parent, name);
		if (dentry)
L
Linus Torvalds 已提交
2258 2259 2260 2261
			break;
	} while (read_seqretry(&rename_lock, seq));
	return dentry;
}
2262
EXPORT_SYMBOL(d_lookup);
L
Linus Torvalds 已提交
2263

N
Nick Piggin 已提交
2264
/**
2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278
 * __d_lookup - search for a dentry (racy)
 * @parent: parent dentry
 * @name: qstr of name we wish to find
 * Returns: dentry, or NULL
 *
 * __d_lookup is like d_lookup, however it may (rarely) return a
 * false-negative result due to unrelated rename activity.
 *
 * __d_lookup is slightly faster by avoiding rename_lock read seqlock,
 * however it must be used carefully, eg. with a following d_lookup in
 * the case of failure.
 *
 * __d_lookup callers must be commented.
 */
A
Al Viro 已提交
2279
struct dentry *__d_lookup(const struct dentry *parent, const struct qstr *name)
L
Linus Torvalds 已提交
2280 2281
{
	unsigned int hash = name->hash;
2282
	struct hlist_bl_head *b = d_hash(hash);
2283
	struct hlist_bl_node *node;
N
Nick Piggin 已提交
2284
	struct dentry *found = NULL;
2285
	struct dentry *dentry;
L
Linus Torvalds 已提交
2286

N
Nick Piggin 已提交
2287 2288 2289 2290 2291 2292 2293
	/*
	 * Note: There is significant duplication with __d_lookup_rcu which is
	 * required to prevent single threaded performance regressions
	 * especially on architectures where smp_rmb (in seqcounts) are costly.
	 * Keep the two functions in sync.
	 */

2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304
	/*
	 * The hash list is protected using RCU.
	 *
	 * Take d_lock when comparing a candidate dentry, to avoid races
	 * with d_move().
	 *
	 * It is possible that concurrent renames can mess up our list
	 * walk here and result in missing our dentry, resulting in the
	 * false-negative result. d_lookup() protects against concurrent
	 * renames using rename_lock seqlock.
	 *
2305
	 * See Documentation/filesystems/path-lookup.txt for more details.
2306
	 */
L
Linus Torvalds 已提交
2307 2308
	rcu_read_lock();
	
2309
	hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
L
Linus Torvalds 已提交
2310 2311 2312 2313 2314 2315 2316

		if (dentry->d_name.hash != hash)
			continue;

		spin_lock(&dentry->d_lock);
		if (dentry->d_parent != parent)
			goto next;
2317 2318 2319
		if (d_unhashed(dentry))
			goto next;

A
Al Viro 已提交
2320 2321
		if (!d_same_name(dentry, parent, name))
			goto next;
L
Linus Torvalds 已提交
2322

2323
		dentry->d_lockref.count++;
2324
		found = dentry;
L
Linus Torvalds 已提交
2325 2326 2327 2328 2329 2330 2331 2332 2333 2334
		spin_unlock(&dentry->d_lock);
		break;
next:
		spin_unlock(&dentry->d_lock);
 	}
 	rcu_read_unlock();

 	return found;
}

2335 2336 2337 2338 2339
/**
 * d_hash_and_lookup - hash the qstr then search for a dentry
 * @dir: Directory to search in
 * @name: qstr of name we wish to find
 *
2340
 * On lookup failure NULL is returned; on bad name - ERR_PTR(-error)
2341 2342 2343 2344 2345 2346 2347 2348
 */
struct dentry *d_hash_and_lookup(struct dentry *dir, struct qstr *name)
{
	/*
	 * Check for a fs-specific hash function. Note that we must
	 * calculate the standard hash first, as the d_op->d_hash()
	 * routine may choose to leave the hash value unchanged.
	 */
2349
	name->hash = full_name_hash(dir, name->name, name->len);
2350
	if (dir->d_flags & DCACHE_OP_HASH) {
2351
		int err = dir->d_op->d_hash(dir, name);
2352 2353
		if (unlikely(err < 0))
			return ERR_PTR(err);
2354
	}
2355
	return d_lookup(dir, name);
2356
}
2357
EXPORT_SYMBOL(d_hash_and_lookup);
2358

L
Linus Torvalds 已提交
2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381
/*
 * When a file is deleted, we have two options:
 * - turn this dentry into a negative dentry
 * - unhash this dentry and free it.
 *
 * Usually, we want to just turn this into
 * a negative dentry, but if anybody else is
 * currently using the dentry or the inode
 * we can't do that and we fall back on removing
 * it from the hash queues and waiting for
 * it to be deleted later when it has no users
 */
 
/**
 * d_delete - delete a dentry
 * @dentry: The dentry to delete
 *
 * Turn the dentry into a negative dentry if possible, otherwise
 * remove it from the hash queues so it can be deleted later
 */
 
void d_delete(struct dentry * dentry)
{
2382
	struct inode *inode;
2383
	int isdir = 0;
L
Linus Torvalds 已提交
2384 2385 2386
	/*
	 * Are we the only user?
	 */
2387
again:
L
Linus Torvalds 已提交
2388
	spin_lock(&dentry->d_lock);
2389 2390
	inode = dentry->d_inode;
	isdir = S_ISDIR(inode->i_mode);
2391
	if (dentry->d_lockref.count == 1) {
A
Alan Cox 已提交
2392
		if (!spin_trylock(&inode->i_lock)) {
2393 2394 2395 2396
			spin_unlock(&dentry->d_lock);
			cpu_relax();
			goto again;
		}
A
Al Viro 已提交
2397
		dentry->d_flags &= ~DCACHE_CANT_MOUNT;
N
Nick Piggin 已提交
2398
		dentry_unlink_inode(dentry);
2399
		fsnotify_nameremove(dentry, isdir);
L
Linus Torvalds 已提交
2400 2401 2402 2403 2404 2405 2406
		return;
	}

	if (!d_unhashed(dentry))
		__d_drop(dentry);

	spin_unlock(&dentry->d_lock);
2407 2408

	fsnotify_nameremove(dentry, isdir);
L
Linus Torvalds 已提交
2409
}
2410
EXPORT_SYMBOL(d_delete);
L
Linus Torvalds 已提交
2411

2412
static void __d_rehash(struct dentry *entry)
L
Linus Torvalds 已提交
2413
{
2414
	struct hlist_bl_head *b = d_hash(entry->d_name.hash);
2415

2416
	hlist_bl_lock(b);
2417
	hlist_bl_add_head_rcu(&entry->d_hash, b);
2418
	hlist_bl_unlock(b);
L
Linus Torvalds 已提交
2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430
}

/**
 * d_rehash	- add an entry back to the hash
 * @entry: dentry to add to the hash
 *
 * Adds a dentry to the hash according to its name.
 */
 
void d_rehash(struct dentry * entry)
{
	spin_lock(&entry->d_lock);
2431
	__d_rehash(entry);
L
Linus Torvalds 已提交
2432 2433
	spin_unlock(&entry->d_lock);
}
2434
EXPORT_SYMBOL(d_rehash);
L
Linus Torvalds 已提交
2435

A
Al Viro 已提交
2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451
static inline unsigned start_dir_add(struct inode *dir)
{

	for (;;) {
		unsigned n = dir->i_dir_seq;
		if (!(n & 1) && cmpxchg(&dir->i_dir_seq, n, n + 1) == n)
			return n;
		cpu_relax();
	}
}

static inline void end_dir_add(struct inode *dir, unsigned n)
{
	smp_store_release(&dir->i_dir_seq, n + 2);
}

2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465
static void d_wait_lookup(struct dentry *dentry)
{
	if (d_in_lookup(dentry)) {
		DECLARE_WAITQUEUE(wait, current);
		add_wait_queue(dentry->d_wait, &wait);
		do {
			set_current_state(TASK_UNINTERRUPTIBLE);
			spin_unlock(&dentry->d_lock);
			schedule();
			spin_lock(&dentry->d_lock);
		} while (d_in_lookup(dentry));
	}
}

A
Al Viro 已提交
2466
struct dentry *d_alloc_parallel(struct dentry *parent,
2467 2468
				const struct qstr *name,
				wait_queue_head_t *wq)
A
Al Viro 已提交
2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481
{
	unsigned int hash = name->hash;
	struct hlist_bl_head *b = in_lookup_hash(parent, hash);
	struct hlist_bl_node *node;
	struct dentry *new = d_alloc(parent, name);
	struct dentry *dentry;
	unsigned seq, r_seq, d_seq;

	if (unlikely(!new))
		return ERR_PTR(-ENOMEM);

retry:
	rcu_read_lock();
2482
	seq = smp_load_acquire(&parent->d_inode->i_dir_seq);
A
Al Viro 已提交
2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502
	r_seq = read_seqbegin(&rename_lock);
	dentry = __d_lookup_rcu(parent, name, &d_seq);
	if (unlikely(dentry)) {
		if (!lockref_get_not_dead(&dentry->d_lockref)) {
			rcu_read_unlock();
			goto retry;
		}
		if (read_seqcount_retry(&dentry->d_seq, d_seq)) {
			rcu_read_unlock();
			dput(dentry);
			goto retry;
		}
		rcu_read_unlock();
		dput(new);
		return dentry;
	}
	if (unlikely(read_seqretry(&rename_lock, r_seq))) {
		rcu_read_unlock();
		goto retry;
	}
2503 2504 2505 2506 2507 2508

	if (unlikely(seq & 1)) {
		rcu_read_unlock();
		goto retry;
	}

A
Al Viro 已提交
2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526
	hlist_bl_lock(b);
	if (unlikely(parent->d_inode->i_dir_seq != seq)) {
		hlist_bl_unlock(b);
		rcu_read_unlock();
		goto retry;
	}
	/*
	 * No changes for the parent since the beginning of d_lookup().
	 * Since all removals from the chain happen with hlist_bl_lock(),
	 * any potential in-lookup matches are going to stay here until
	 * we unlock the chain.  All fields are stable in everything
	 * we encounter.
	 */
	hlist_bl_for_each_entry(dentry, node, b, d_u.d_in_lookup_hash) {
		if (dentry->d_name.hash != hash)
			continue;
		if (dentry->d_parent != parent)
			continue;
A
Al Viro 已提交
2527 2528
		if (!d_same_name(dentry, parent, name))
			continue;
A
Al Viro 已提交
2529
		hlist_bl_unlock(b);
2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540
		/* now we can try to grab a reference */
		if (!lockref_get_not_dead(&dentry->d_lockref)) {
			rcu_read_unlock();
			goto retry;
		}

		rcu_read_unlock();
		/*
		 * somebody is likely to be still doing lookup for it;
		 * wait for them to finish
		 */
2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554
		spin_lock(&dentry->d_lock);
		d_wait_lookup(dentry);
		/*
		 * it's not in-lookup anymore; in principle we should repeat
		 * everything from dcache lookup, but it's likely to be what
		 * d_lookup() would've found anyway.  If it is, just return it;
		 * otherwise we really have to repeat the whole thing.
		 */
		if (unlikely(dentry->d_name.hash != hash))
			goto mismatch;
		if (unlikely(dentry->d_parent != parent))
			goto mismatch;
		if (unlikely(d_unhashed(dentry)))
			goto mismatch;
A
Al Viro 已提交
2555 2556
		if (unlikely(!d_same_name(dentry, parent, name)))
			goto mismatch;
2557 2558
		/* OK, it *is* a hashed match; return it */
		spin_unlock(&dentry->d_lock);
A
Al Viro 已提交
2559 2560 2561
		dput(new);
		return dentry;
	}
2562
	rcu_read_unlock();
A
Al Viro 已提交
2563 2564
	/* we can't take ->d_lock here; it's OK, though. */
	new->d_flags |= DCACHE_PAR_LOOKUP;
2565
	new->d_wait = wq;
A
Al Viro 已提交
2566 2567 2568
	hlist_bl_add_head_rcu(&new->d_u.d_in_lookup_hash, b);
	hlist_bl_unlock(b);
	return new;
2569 2570 2571 2572
mismatch:
	spin_unlock(&dentry->d_lock);
	dput(dentry);
	goto retry;
A
Al Viro 已提交
2573 2574 2575
}
EXPORT_SYMBOL(d_alloc_parallel);

2576 2577
void __d_lookup_done(struct dentry *dentry)
{
A
Al Viro 已提交
2578 2579 2580
	struct hlist_bl_head *b = in_lookup_hash(dentry->d_parent,
						 dentry->d_name.hash);
	hlist_bl_lock(b);
2581
	dentry->d_flags &= ~DCACHE_PAR_LOOKUP;
A
Al Viro 已提交
2582
	__hlist_bl_del(&dentry->d_u.d_in_lookup_hash);
2583 2584
	wake_up_all(dentry->d_wait);
	dentry->d_wait = NULL;
A
Al Viro 已提交
2585 2586
	hlist_bl_unlock(b);
	INIT_HLIST_NODE(&dentry->d_u.d_alias);
2587
	INIT_LIST_HEAD(&dentry->d_lru);
2588 2589
}
EXPORT_SYMBOL(__d_lookup_done);
A
Al Viro 已提交
2590 2591 2592 2593 2594

/* inode->i_lock held if inode is non-NULL */

static inline void __d_add(struct dentry *dentry, struct inode *inode)
{
A
Al Viro 已提交
2595 2596
	struct inode *dir = NULL;
	unsigned n;
A
Al Viro 已提交
2597
	spin_lock(&dentry->d_lock);
A
Al Viro 已提交
2598 2599 2600
	if (unlikely(d_in_lookup(dentry))) {
		dir = dentry->d_parent->d_inode;
		n = start_dir_add(dir);
2601
		__d_lookup_done(dentry);
A
Al Viro 已提交
2602
	}
A
Al Viro 已提交
2603
	if (inode) {
A
Al Viro 已提交
2604 2605 2606 2607 2608
		unsigned add_flags = d_flags_for_inode(inode);
		hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
		raw_write_seqcount_begin(&dentry->d_seq);
		__d_set_inode_and_type(dentry, inode, add_flags);
		raw_write_seqcount_end(&dentry->d_seq);
A
Al Viro 已提交
2609
		fsnotify_update_flags(dentry);
A
Al Viro 已提交
2610
	}
2611
	__d_rehash(dentry);
A
Al Viro 已提交
2612 2613
	if (dir)
		end_dir_add(dir, n);
A
Al Viro 已提交
2614 2615 2616
	spin_unlock(&dentry->d_lock);
	if (inode)
		spin_unlock(&inode->i_lock);
A
Al Viro 已提交
2617 2618
}

A
Al Viro 已提交
2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629
/**
 * d_add - add dentry to hash queues
 * @entry: dentry to add
 * @inode: The inode to attach to this dentry
 *
 * This adds the entry to the hash queues and initializes @inode.
 * The entry was actually filled in earlier during d_alloc().
 */

void d_add(struct dentry *entry, struct inode *inode)
{
2630 2631
	if (inode) {
		security_d_instantiate(entry, inode);
A
Al Viro 已提交
2632
		spin_lock(&inode->i_lock);
2633
	}
A
Al Viro 已提交
2634
	__d_add(entry, inode);
A
Al Viro 已提交
2635 2636 2637
}
EXPORT_SYMBOL(d_add);

2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664
/**
 * d_exact_alias - find and hash an exact unhashed alias
 * @entry: dentry to add
 * @inode: The inode to go with this dentry
 *
 * If an unhashed dentry with the same name/parent and desired
 * inode already exists, hash and return it.  Otherwise, return
 * NULL.
 *
 * Parent directory should be locked.
 */
struct dentry *d_exact_alias(struct dentry *entry, struct inode *inode)
{
	struct dentry *alias;
	unsigned int hash = entry->d_name.hash;

	spin_lock(&inode->i_lock);
	hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
		/*
		 * Don't need alias->d_lock here, because aliases with
		 * d_parent == entry->d_parent are not subject to name or
		 * parent changes, because the parent inode i_mutex is held.
		 */
		if (alias->d_name.hash != hash)
			continue;
		if (alias->d_parent != entry->d_parent)
			continue;
A
Al Viro 已提交
2665
		if (!d_same_name(alias, entry->d_parent, &entry->d_name))
2666 2667 2668 2669 2670 2671 2672
			continue;
		spin_lock(&alias->d_lock);
		if (!d_unhashed(alias)) {
			spin_unlock(&alias->d_lock);
			alias = NULL;
		} else {
			__dget_dlock(alias);
2673
			__d_rehash(alias);
2674 2675 2676 2677 2678 2679 2680 2681 2682 2683
			spin_unlock(&alias->d_lock);
		}
		spin_unlock(&inode->i_lock);
		return alias;
	}
	spin_unlock(&inode->i_lock);
	return NULL;
}
EXPORT_SYMBOL(d_exact_alias);

N
Nick Piggin 已提交
2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697
/**
 * dentry_update_name_case - update case insensitive dentry with a new name
 * @dentry: dentry to be updated
 * @name: new name
 *
 * Update a case insensitive dentry with new case of name.
 *
 * dentry must have been returned by d_lookup with name @name. Old and new
 * name lengths must match (ie. no d_compare which allows mismatched name
 * lengths).
 *
 * Parent inode i_mutex must be held over d_lookup and into this call (to
 * keep renames and concurrent inserts, and readdir(2) away).
 */
A
Al Viro 已提交
2698
void dentry_update_name_case(struct dentry *dentry, const struct qstr *name)
N
Nick Piggin 已提交
2699
{
A
Al Viro 已提交
2700
	BUG_ON(!inode_is_locked(dentry->d_parent->d_inode));
N
Nick Piggin 已提交
2701 2702 2703
	BUG_ON(dentry->d_name.len != name->len); /* d_lookup gives this */

	spin_lock(&dentry->d_lock);
N
Nick Piggin 已提交
2704
	write_seqcount_begin(&dentry->d_seq);
N
Nick Piggin 已提交
2705
	memcpy((unsigned char *)dentry->d_name.name, name->name, name->len);
N
Nick Piggin 已提交
2706
	write_seqcount_end(&dentry->d_seq);
N
Nick Piggin 已提交
2707 2708 2709 2710
	spin_unlock(&dentry->d_lock);
}
EXPORT_SYMBOL(dentry_update_name_case);

2711
static void swap_names(struct dentry *dentry, struct dentry *target)
L
Linus Torvalds 已提交
2712
{
2713 2714
	if (unlikely(dname_external(target))) {
		if (unlikely(dname_external(dentry))) {
L
Linus Torvalds 已提交
2715 2716 2717
			/*
			 * Both external: swap the pointers
			 */
2718
			swap(target->d_name.name, dentry->d_name.name);
L
Linus Torvalds 已提交
2719 2720 2721 2722 2723
		} else {
			/*
			 * dentry:internal, target:external.  Steal target's
			 * storage and make target internal.
			 */
2724 2725
			memcpy(target->d_iname, dentry->d_name.name,
					dentry->d_name.len + 1);
L
Linus Torvalds 已提交
2726 2727 2728 2729
			dentry->d_name.name = target->d_name.name;
			target->d_name.name = target->d_iname;
		}
	} else {
2730
		if (unlikely(dname_external(dentry))) {
L
Linus Torvalds 已提交
2731 2732 2733 2734 2735 2736 2737 2738 2739 2740
			/*
			 * dentry:external, target:internal.  Give dentry's
			 * storage to target and make dentry internal
			 */
			memcpy(dentry->d_iname, target->d_name.name,
					target->d_name.len + 1);
			target->d_name.name = dentry->d_name.name;
			dentry->d_name.name = dentry->d_iname;
		} else {
			/*
M
Miklos Szeredi 已提交
2741
			 * Both are internal.
L
Linus Torvalds 已提交
2742
			 */
M
Miklos Szeredi 已提交
2743 2744 2745 2746 2747 2748
			unsigned int i;
			BUILD_BUG_ON(!IS_ALIGNED(DNAME_INLINE_LEN, sizeof(long)));
			for (i = 0; i < DNAME_INLINE_LEN / sizeof(long); i++) {
				swap(((long *) &dentry->d_iname)[i],
				     ((long *) &target->d_iname)[i]);
			}
L
Linus Torvalds 已提交
2749 2750
		}
	}
2751
	swap(dentry->d_name.hash_len, target->d_name.hash_len);
L
Linus Torvalds 已提交
2752 2753
}

2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771
static void copy_name(struct dentry *dentry, struct dentry *target)
{
	struct external_name *old_name = NULL;
	if (unlikely(dname_external(dentry)))
		old_name = external_name(dentry);
	if (unlikely(dname_external(target))) {
		atomic_inc(&external_name(target)->u.count);
		dentry->d_name = target->d_name;
	} else {
		memcpy(dentry->d_iname, target->d_name.name,
				target->d_name.len + 1);
		dentry->d_name.name = dentry->d_iname;
		dentry->d_name.hash_len = target->d_name.hash_len;
	}
	if (old_name && likely(atomic_dec_and_test(&old_name->u.count)))
		kfree_rcu(old_name, u.head);
}

N
Nick Piggin 已提交
2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798
static void dentry_lock_for_move(struct dentry *dentry, struct dentry *target)
{
	/*
	 * XXXX: do we really need to take target->d_lock?
	 */
	if (IS_ROOT(dentry) || dentry->d_parent == target->d_parent)
		spin_lock(&target->d_parent->d_lock);
	else {
		if (d_ancestor(dentry->d_parent, target->d_parent)) {
			spin_lock(&dentry->d_parent->d_lock);
			spin_lock_nested(&target->d_parent->d_lock,
						DENTRY_D_LOCK_NESTED);
		} else {
			spin_lock(&target->d_parent->d_lock);
			spin_lock_nested(&dentry->d_parent->d_lock,
						DENTRY_D_LOCK_NESTED);
		}
	}
	if (target < dentry) {
		spin_lock_nested(&target->d_lock, 2);
		spin_lock_nested(&dentry->d_lock, 3);
	} else {
		spin_lock_nested(&dentry->d_lock, 2);
		spin_lock_nested(&target->d_lock, 3);
	}
}

2799
static void dentry_unlock_for_move(struct dentry *dentry, struct dentry *target)
N
Nick Piggin 已提交
2800 2801 2802 2803 2804
{
	if (target->d_parent != dentry->d_parent)
		spin_unlock(&dentry->d_parent->d_lock);
	if (target->d_parent != target)
		spin_unlock(&target->d_parent->d_lock);
2805 2806
	spin_unlock(&target->d_lock);
	spin_unlock(&dentry->d_lock);
N
Nick Piggin 已提交
2807 2808
}

L
Linus Torvalds 已提交
2809
/*
N
Nick Piggin 已提交
2810 2811 2812
 * When switching names, the actual string doesn't strictly have to
 * be preserved in the target - because we're dropping the target
 * anyway. As such, we can just do a simple memcpy() to copy over
2813 2814 2815 2816 2817 2818 2819 2820 2821
 * the new name before we switch, unless we are going to rehash
 * it.  Note that if we *do* unhash the target, we are not allowed
 * to rehash it without giving it a new name/hash key - whether
 * we swap or overwrite the names here, resulting name won't match
 * the reality in filesystem; it's only there for d_path() purposes.
 * Note that all of this is happening under rename_lock, so the
 * any hash lookup seeing it in the middle of manipulations will
 * be discarded anyway.  So we do not care what happens to the hash
 * key in that case.
L
Linus Torvalds 已提交
2822
 */
2823
/*
2824
 * __d_move - move a dentry
L
Linus Torvalds 已提交
2825 2826
 * @dentry: entry to move
 * @target: new dentry
M
Miklos Szeredi 已提交
2827
 * @exchange: exchange the two dentries
L
Linus Torvalds 已提交
2828 2829
 *
 * Update the dcache to reflect the move of a file name. Negative
2830 2831 2832
 * dcache entries should not be moved in this way. Caller must hold
 * rename_lock, the i_mutex of the source and target directories,
 * and the sb->s_vfs_rename_mutex if they differ. See lock_rename().
L
Linus Torvalds 已提交
2833
 */
M
Miklos Szeredi 已提交
2834 2835
static void __d_move(struct dentry *dentry, struct dentry *target,
		     bool exchange)
L
Linus Torvalds 已提交
2836
{
A
Al Viro 已提交
2837 2838
	struct inode *dir = NULL;
	unsigned n;
L
Linus Torvalds 已提交
2839 2840 2841
	if (!dentry->d_inode)
		printk(KERN_WARNING "VFS: moving negative dcache entry\n");

N
Nick Piggin 已提交
2842 2843 2844 2845
	BUG_ON(d_ancestor(dentry, target));
	BUG_ON(d_ancestor(target, dentry));

	dentry_lock_for_move(dentry, target);
A
Al Viro 已提交
2846 2847 2848
	if (unlikely(d_in_lookup(target))) {
		dir = target->d_parent->d_inode;
		n = start_dir_add(dir);
2849
		__d_lookup_done(target);
A
Al Viro 已提交
2850
	}
L
Linus Torvalds 已提交
2851

N
Nick Piggin 已提交
2852
	write_seqcount_begin(&dentry->d_seq);
2853
	write_seqcount_begin_nested(&target->d_seq, DENTRY_D_LOCK_NESTED);
N
Nick Piggin 已提交
2854

2855
	/* unhash both */
2856 2857 2858
	/* ___d_drop does write_seqcount_barrier, but they're OK to nest. */
	___d_drop(dentry);
	___d_drop(target);
L
Linus Torvalds 已提交
2859 2860

	/* Switch the names.. */
2861 2862 2863 2864
	if (exchange)
		swap_names(dentry, target);
	else
		copy_name(dentry, target);
L
Linus Torvalds 已提交
2865

2866 2867 2868 2869
	/* rehash in new place(s) */
	__d_rehash(dentry);
	if (exchange)
		__d_rehash(target);
2870 2871
	else
		target->d_hash.pprev = NULL;
2872

A
Al Viro 已提交
2873
	/* ... and switch them in the tree */
L
Linus Torvalds 已提交
2874
	if (IS_ROOT(dentry)) {
A
Al Viro 已提交
2875
		/* splicing a tree */
2876
		dentry->d_flags |= DCACHE_RCUACCESS;
L
Linus Torvalds 已提交
2877 2878
		dentry->d_parent = target->d_parent;
		target->d_parent = target;
2879 2880
		list_del_init(&target->d_child);
		list_move(&dentry->d_child, &dentry->d_parent->d_subdirs);
L
Linus Torvalds 已提交
2881
	} else {
A
Al Viro 已提交
2882
		/* swapping two dentries */
2883
		swap(dentry->d_parent, target->d_parent);
2884 2885
		list_move(&target->d_child, &target->d_parent->d_subdirs);
		list_move(&dentry->d_child, &dentry->d_parent->d_subdirs);
A
Al Viro 已提交
2886
		if (exchange)
A
Al Viro 已提交
2887 2888
			fsnotify_update_flags(target);
		fsnotify_update_flags(dentry);
L
Linus Torvalds 已提交
2889 2890
	}

N
Nick Piggin 已提交
2891 2892 2893
	write_seqcount_end(&target->d_seq);
	write_seqcount_end(&dentry->d_seq);

A
Al Viro 已提交
2894 2895
	if (dir)
		end_dir_add(dir, n);
2896
	dentry_unlock_for_move(dentry, target);
2897 2898 2899 2900 2901 2902 2903 2904
}

/*
 * d_move - move a dentry
 * @dentry: entry to move
 * @target: new dentry
 *
 * Update the dcache to reflect the move of a file name. Negative
2905 2906
 * dcache entries should not be moved in this way. See the locking
 * requirements for __d_move.
2907 2908 2909 2910
 */
void d_move(struct dentry *dentry, struct dentry *target)
{
	write_seqlock(&rename_lock);
M
Miklos Szeredi 已提交
2911
	__d_move(dentry, target, false);
L
Linus Torvalds 已提交
2912
	write_sequnlock(&rename_lock);
2913
}
2914
EXPORT_SYMBOL(d_move);
L
Linus Torvalds 已提交
2915

M
Miklos Szeredi 已提交
2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934
/*
 * d_exchange - exchange two dentries
 * @dentry1: first dentry
 * @dentry2: second dentry
 */
void d_exchange(struct dentry *dentry1, struct dentry *dentry2)
{
	write_seqlock(&rename_lock);

	WARN_ON(!dentry1->d_inode);
	WARN_ON(!dentry2->d_inode);
	WARN_ON(IS_ROOT(dentry1));
	WARN_ON(IS_ROOT(dentry2));

	__d_move(dentry1, dentry2, true);

	write_sequnlock(&rename_lock);
}

2935 2936 2937 2938 2939 2940 2941
/**
 * d_ancestor - search for an ancestor
 * @p1: ancestor dentry
 * @p2: child dentry
 *
 * Returns the ancestor dentry of p2 which is a child of p1, if p1 is
 * an ancestor of p2, else NULL.
2942
 */
2943
struct dentry *d_ancestor(struct dentry *p1, struct dentry *p2)
2944 2945 2946
{
	struct dentry *p;

2947
	for (p = p2; !IS_ROOT(p); p = p->d_parent) {
2948
		if (p->d_parent == p1)
2949
			return p;
2950
	}
2951
	return NULL;
2952 2953 2954 2955 2956 2957
}

/*
 * This helper attempts to cope with remotely renamed directories
 *
 * It assumes that the caller is already holding
2958
 * dentry->d_parent->d_inode->i_mutex, and rename_lock
2959 2960 2961 2962
 *
 * Note: If ever the locking in lock_rename() changes, then please
 * remember to update this too...
 */
2963
static int __d_unalias(struct inode *inode,
2964
		struct dentry *dentry, struct dentry *alias)
2965
{
2966 2967
	struct mutex *m1 = NULL;
	struct rw_semaphore *m2 = NULL;
2968
	int ret = -ESTALE;
2969 2970 2971 2972 2973 2974 2975 2976 2977

	/* If alias and dentry share a parent, then no extra locks required */
	if (alias->d_parent == dentry->d_parent)
		goto out_unalias;

	/* See lock_rename() */
	if (!mutex_trylock(&dentry->d_sb->s_vfs_rename_mutex))
		goto out_err;
	m1 = &dentry->d_sb->s_vfs_rename_mutex;
2978
	if (!inode_trylock_shared(alias->d_parent->d_inode))
2979
		goto out_err;
2980
	m2 = &alias->d_parent->d_inode->i_rwsem;
2981
out_unalias:
2982
	__d_move(alias, dentry, false);
2983
	ret = 0;
2984 2985
out_err:
	if (m2)
2986
		up_read(m2);
2987 2988 2989 2990 2991
	if (m1)
		mutex_unlock(m1);
	return ret;
}

J
J. Bruce Fields 已提交
2992 2993 2994 2995 2996
/**
 * d_splice_alias - splice a disconnected dentry into the tree if one exists
 * @inode:  the inode which may have a disconnected dentry
 * @dentry: a negative dentry which we want to point to the inode.
 *
2997 2998 2999
 * If inode is a directory and has an IS_ROOT alias, then d_move that in
 * place of the given dentry and return it, else simply d_add the inode
 * to the dentry and return NULL.
J
J. Bruce Fields 已提交
3000
 *
3001 3002 3003
 * If a non-IS_ROOT directory is found, the filesystem is corrupt, and
 * we should error out: directories can't have multiple aliases.
 *
J
J. Bruce Fields 已提交
3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019
 * This is needed in the lookup routine of any filesystem that is exportable
 * (via knfsd) so that we can build dcache paths to directories effectively.
 *
 * If a dentry was found and moved, then it is returned.  Otherwise NULL
 * is returned.  This matches the expected return value of ->lookup.
 *
 * Cluster filesystems may call this function with a negative, hashed dentry.
 * In that case, we know that the inode will be a regular file, and also this
 * will only occur during atomic_open. So we need to check for the dentry
 * being already hashed only in the final case.
 */
struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
{
	if (IS_ERR(inode))
		return ERR_CAST(inode);

3020 3021
	BUG_ON(!d_unhashed(dentry));

3022
	if (!inode)
3023
		goto out;
3024

3025
	security_d_instantiate(dentry, inode);
3026
	spin_lock(&inode->i_lock);
3027
	if (S_ISDIR(inode->i_mode)) {
3028 3029
		struct dentry *new = __d_find_any_alias(inode);
		if (unlikely(new)) {
3030 3031
			/* The reference to new ensures it remains an alias */
			spin_unlock(&inode->i_lock);
3032
			write_seqlock(&rename_lock);
3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044
			if (unlikely(d_ancestor(new, dentry))) {
				write_sequnlock(&rename_lock);
				dput(new);
				new = ERR_PTR(-ELOOP);
				pr_warn_ratelimited(
					"VFS: Lookup of '%s' in %s %s"
					" would have caused loop\n",
					dentry->d_name.name,
					inode->i_sb->s_type->name,
					inode->i_sb->s_id);
			} else if (!IS_ROOT(new)) {
				int err = __d_unalias(inode, dentry, new);
3045
				write_sequnlock(&rename_lock);
3046 3047 3048 3049
				if (err) {
					dput(new);
					new = ERR_PTR(err);
				}
3050
			} else {
3051 3052
				__d_move(new, dentry, false);
				write_sequnlock(&rename_lock);
3053
			}
3054 3055
			iput(inode);
			return new;
3056
		}
3057
	}
3058
out:
A
Al Viro 已提交
3059
	__d_add(dentry, inode);
3060
	return NULL;
3061
}
3062
EXPORT_SYMBOL(d_splice_alias);
3063

3064
static int prepend(char **buffer, int *buflen, const char *str, int namelen)
3065 3066 3067 3068 3069 3070 3071 3072 3073
{
	*buflen -= namelen;
	if (*buflen < 0)
		return -ENAMETOOLONG;
	*buffer -= namelen;
	memcpy(*buffer, str, namelen);
	return 0;
}

3074 3075
/**
 * prepend_name - prepend a pathname in front of current buffer pointer
3076 3077 3078
 * @buffer: buffer pointer
 * @buflen: allocated length of the buffer
 * @name:   name string and length qstr structure
3079
 *
3080
 * With RCU path tracing, it may race with d_move(). Use READ_ONCE() to
3081 3082 3083 3084 3085 3086 3087
 * make sure that either the old or the new name pointer and length are
 * fetched. However, there may be mismatch between length and pointer.
 * The length cannot be trusted, we need to copy it byte-by-byte until
 * the length is reached or a null byte is found. It also prepends "/" at
 * the beginning of the name. The sequence number check at the caller will
 * retry it again when a d_move() does happen. So any garbage in the buffer
 * due to mismatched pointer and length will be discarded.
3088
 *
3089
 * Load acquire is needed to make sure that we see that terminating NUL.
3090
 */
A
Al Viro 已提交
3091
static int prepend_name(char **buffer, int *buflen, const struct qstr *name)
3092
{
3093
	const char *dname = smp_load_acquire(&name->name); /* ^^^ */
3094
	u32 dlen = READ_ONCE(name->len);
3095 3096 3097
	char *p;

	*buflen -= dlen + 1;
3098 3099
	if (*buflen < 0)
		return -ENAMETOOLONG;
3100 3101 3102 3103 3104 3105 3106 3107 3108
	p = *buffer -= dlen + 1;
	*p++ = '/';
	while (dlen--) {
		char c = *dname++;
		if (!c)
			break;
		*p++ = c;
	}
	return 0;
3109 3110
}

L
Linus Torvalds 已提交
3111
/**
3112
 * prepend_path - Prepend path string to a buffer
3113
 * @path: the dentry/vfsmount to report
3114
 * @root: root vfsmnt/dentry
M
Miklos Szeredi 已提交
3115 3116
 * @buffer: pointer to the end of the buffer
 * @buflen: pointer to buffer length
3117
 *
3118 3119 3120 3121 3122 3123 3124 3125 3126
 * The function will first try to write out the pathname without taking any
 * lock other than the RCU read lock to make sure that dentries won't go away.
 * It only checks the sequence number of the global rename_lock as any change
 * in the dentry's d_seq will be preceded by changes in the rename_lock
 * sequence number. If the sequence number had been changed, it will restart
 * the whole pathname back-tracing sequence again by taking the rename_lock.
 * In this case, there is no need to take the RCU read lock as the recursive
 * parent pointer references will keep the dentry chain alive as long as no
 * rename operation is performed.
L
Linus Torvalds 已提交
3127
 */
3128 3129
static int prepend_path(const struct path *path,
			const struct path *root,
M
Miklos Szeredi 已提交
3130
			char **buffer, int *buflen)
L
Linus Torvalds 已提交
3131
{
3132 3133 3134
	struct dentry *dentry;
	struct vfsmount *vfsmnt;
	struct mount *mnt;
M
Miklos Szeredi 已提交
3135
	int error = 0;
A
Al Viro 已提交
3136
	unsigned seq, m_seq = 0;
3137 3138
	char *bptr;
	int blen;
3139

3140
	rcu_read_lock();
A
Al Viro 已提交
3141 3142 3143
restart_mnt:
	read_seqbegin_or_lock(&mount_lock, &m_seq);
	seq = 0;
L
Li Zhong 已提交
3144
	rcu_read_lock();
3145 3146 3147
restart:
	bptr = *buffer;
	blen = *buflen;
A
Al Viro 已提交
3148
	error = 0;
3149 3150 3151
	dentry = path->dentry;
	vfsmnt = path->mnt;
	mnt = real_mount(vfsmnt);
3152
	read_seqbegin_or_lock(&rename_lock, &seq);
M
Miklos Szeredi 已提交
3153
	while (dentry != root->dentry || vfsmnt != root->mnt) {
L
Linus Torvalds 已提交
3154 3155 3156
		struct dentry * parent;

		if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
3157
			struct mount *parent = READ_ONCE(mnt->mnt_parent);
3158 3159 3160 3161 3162 3163 3164
			/* Escaped? */
			if (dentry != vfsmnt->mnt_root) {
				bptr = *buffer;
				blen = *buflen;
				error = 3;
				break;
			}
3165
			/* Global root? */
A
Al Viro 已提交
3166
			if (mnt != parent) {
3167
				dentry = READ_ONCE(mnt->mnt_mountpoint);
A
Al Viro 已提交
3168
				mnt = parent;
3169 3170 3171 3172 3173 3174
				vfsmnt = &mnt->mnt;
				continue;
			}
			if (!error)
				error = is_mounted(vfsmnt) ? 1 : 2;
			break;
L
Linus Torvalds 已提交
3175 3176 3177
		}
		parent = dentry->d_parent;
		prefetch(parent);
3178
		error = prepend_name(&bptr, &blen, &dentry->d_name);
M
Miklos Szeredi 已提交
3179 3180 3181
		if (error)
			break;

L
Linus Torvalds 已提交
3182 3183
		dentry = parent;
	}
3184 3185 3186 3187
	if (!(seq & 1))
		rcu_read_unlock();
	if (need_seqretry(&rename_lock, seq)) {
		seq = 1;
3188
		goto restart;
3189 3190
	}
	done_seqretry(&rename_lock, seq);
L
Li Zhong 已提交
3191 3192 3193

	if (!(m_seq & 1))
		rcu_read_unlock();
A
Al Viro 已提交
3194 3195 3196 3197 3198
	if (need_seqretry(&mount_lock, m_seq)) {
		m_seq = 1;
		goto restart_mnt;
	}
	done_seqretry(&mount_lock, m_seq);
L
Linus Torvalds 已提交
3199

3200 3201 3202 3203 3204 3205 3206 3207
	if (error >= 0 && bptr == *buffer) {
		if (--blen < 0)
			error = -ENAMETOOLONG;
		else
			*--bptr = '/';
	}
	*buffer = bptr;
	*buflen = blen;
A
Al Viro 已提交
3208
	return error;
M
Miklos Szeredi 已提交
3209
}
3210

M
Miklos Szeredi 已提交
3211 3212 3213
/**
 * __d_path - return the path of a dentry
 * @path: the dentry/vfsmount to report
3214
 * @root: root vfsmnt/dentry
3215
 * @buf: buffer to return value in
M
Miklos Szeredi 已提交
3216 3217
 * @buflen: buffer length
 *
3218
 * Convert a dentry into an ASCII path name.
M
Miklos Szeredi 已提交
3219 3220 3221 3222
 *
 * Returns a pointer into the buffer or an error code if the
 * path was too long.
 *
3223
 * "buflen" should be positive.
M
Miklos Szeredi 已提交
3224
 *
3225
 * If the path is not reachable from the supplied root, return %NULL.
M
Miklos Szeredi 已提交
3226
 */
3227 3228
char *__d_path(const struct path *path,
	       const struct path *root,
M
Miklos Szeredi 已提交
3229 3230 3231 3232 3233 3234 3235
	       char *buf, int buflen)
{
	char *res = buf + buflen;
	int error;

	prepend(&res, &buflen, "\0", 1);
	error = prepend_path(path, root, &res, &buflen);
3236

3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256
	if (error < 0)
		return ERR_PTR(error);
	if (error > 0)
		return NULL;
	return res;
}

char *d_absolute_path(const struct path *path,
	       char *buf, int buflen)
{
	struct path root = {};
	char *res = buf + buflen;
	int error;

	prepend(&res, &buflen, "\0", 1);
	error = prepend_path(path, &root, &res, &buflen);

	if (error > 1)
		error = -EINVAL;
	if (error < 0)
M
Miklos Szeredi 已提交
3257 3258
		return ERR_PTR(error);
	return res;
L
Linus Torvalds 已提交
3259 3260
}

3261 3262 3263
/*
 * same as __d_path but appends "(deleted)" for unlinked files.
 */
3264 3265 3266
static int path_with_deleted(const struct path *path,
			     const struct path *root,
			     char **buf, int *buflen)
3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277
{
	prepend(buf, buflen, "\0", 1);
	if (d_unlinked(path->dentry)) {
		int error = prepend(buf, buflen, " (deleted)", 10);
		if (error)
			return error;
	}

	return prepend_path(path, root, buf, buflen);
}

3278 3279 3280 3281 3282
static int prepend_unreachable(char **buffer, int *buflen)
{
	return prepend(buffer, buflen, "(unreachable)", 13);
}

3283 3284 3285 3286 3287 3288 3289 3290 3291 3292
static void get_fs_root_rcu(struct fs_struct *fs, struct path *root)
{
	unsigned seq;

	do {
		seq = read_seqcount_begin(&fs->seq);
		*root = fs->root;
	} while (read_seqcount_retry(&fs->seq, seq));
}

J
Jan Blunck 已提交
3293 3294
/**
 * d_path - return the path of a dentry
3295
 * @path: path to report
J
Jan Blunck 已提交
3296 3297 3298 3299 3300 3301
 * @buf: buffer to return value in
 * @buflen: buffer length
 *
 * Convert a dentry into an ASCII path name. If the entry has been deleted
 * the string " (deleted)" is appended. Note that this is ambiguous.
 *
3302 3303 3304 3305
 * Returns a pointer into the buffer or an error code if the path was
 * too long. Note: Callers should use the returned pointer, not the passed
 * in buffer, to use the name! The implementation often starts at an offset
 * into the buffer, and may leave 0 bytes at the start.
J
Jan Blunck 已提交
3306
 *
3307
 * "buflen" should be positive.
J
Jan Blunck 已提交
3308
 */
3309
char *d_path(const struct path *path, char *buf, int buflen)
L
Linus Torvalds 已提交
3310
{
3311
	char *res = buf + buflen;
J
Jan Blunck 已提交
3312
	struct path root;
3313
	int error;
L
Linus Torvalds 已提交
3314

3315 3316 3317 3318 3319 3320
	/*
	 * We have various synthetic filesystems that never get mounted.  On
	 * these filesystems dentries are never used for lookup purposes, and
	 * thus don't need to be hashed.  They also don't need a name until a
	 * user wants to identify the object in /proc/pid/fd/.  The little hack
	 * below allows us to generate a name for these objects on demand:
3321 3322 3323 3324
	 *
	 * Some pseudo inodes are mountable.  When they are mounted
	 * path->dentry == path->mnt->mnt_root.  In that case don't call d_dname
	 * and instead have d_path return the mounted path.
3325
	 */
3326 3327
	if (path->dentry->d_op && path->dentry->d_op->d_dname &&
	    (!IS_ROOT(path->dentry) || path->dentry != path->mnt->mnt_root))
3328
		return path->dentry->d_op->d_dname(path->dentry, buf, buflen);
3329

3330 3331
	rcu_read_lock();
	get_fs_root_rcu(current->fs, &root);
3332
	error = path_with_deleted(path, &root, &res, &buflen);
3333 3334
	rcu_read_unlock();

3335
	if (error < 0)
3336
		res = ERR_PTR(error);
L
Linus Torvalds 已提交
3337 3338
	return res;
}
3339
EXPORT_SYMBOL(d_path);
L
Linus Torvalds 已提交
3340

3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361
/*
 * Helper function for dentry_operations.d_dname() members
 */
char *dynamic_dname(struct dentry *dentry, char *buffer, int buflen,
			const char *fmt, ...)
{
	va_list args;
	char temp[64];
	int sz;

	va_start(args, fmt);
	sz = vsnprintf(temp, sizeof(temp), fmt, args) + 1;
	va_end(args);

	if (sz > sizeof(temp) || sz > buflen)
		return ERR_PTR(-ENAMETOOLONG);

	buffer += buflen - sz;
	return memcpy(buffer, temp, sz);
}

3362 3363 3364 3365 3366
char *simple_dname(struct dentry *dentry, char *buffer, int buflen)
{
	char *end = buffer + buflen;
	/* these dentries are never renamed, so d_lock is not needed */
	if (prepend(&end, &buflen, " (deleted)", 11) ||
3367
	    prepend(&end, &buflen, dentry->d_name.name, dentry->d_name.len) ||
3368 3369
	    prepend(&end, &buflen, "/", 1))  
		end = ERR_PTR(-ENAMETOOLONG);
3370
	return end;
3371
}
3372
EXPORT_SYMBOL(simple_dname);
3373

3374 3375 3376
/*
 * Write full pathname from the root of the filesystem into the buffer.
 */
A
Al Viro 已提交
3377
static char *__dentry_path(struct dentry *d, char *buf, int buflen)
3378
{
A
Al Viro 已提交
3379
	struct dentry *dentry;
3380 3381 3382
	char *end, *retval;
	int len, seq = 0;
	int error = 0;
3383

A
Al Viro 已提交
3384 3385 3386
	if (buflen < 2)
		goto Elong;

3387
	rcu_read_lock();
3388
restart:
A
Al Viro 已提交
3389
	dentry = d;
3390 3391 3392
	end = buf + buflen;
	len = buflen;
	prepend(&end, &len, "\0", 1);
3393 3394 3395
	/* Get '/' right */
	retval = end-1;
	*retval = '/';
3396
	read_seqbegin_or_lock(&rename_lock, &seq);
3397 3398
	while (!IS_ROOT(dentry)) {
		struct dentry *parent = dentry->d_parent;
3399 3400

		prefetch(parent);
3401 3402 3403
		error = prepend_name(&end, &len, &dentry->d_name);
		if (error)
			break;
3404 3405 3406 3407

		retval = end;
		dentry = parent;
	}
3408 3409 3410 3411
	if (!(seq & 1))
		rcu_read_unlock();
	if (need_seqretry(&rename_lock, seq)) {
		seq = 1;
3412
		goto restart;
3413 3414
	}
	done_seqretry(&rename_lock, seq);
3415 3416
	if (error)
		goto Elong;
A
Al Viro 已提交
3417 3418 3419 3420
	return retval;
Elong:
	return ERR_PTR(-ENAMETOOLONG);
}
N
Nick Piggin 已提交
3421 3422 3423

char *dentry_path_raw(struct dentry *dentry, char *buf, int buflen)
{
3424
	return __dentry_path(dentry, buf, buflen);
N
Nick Piggin 已提交
3425 3426
}
EXPORT_SYMBOL(dentry_path_raw);
A
Al Viro 已提交
3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441

char *dentry_path(struct dentry *dentry, char *buf, int buflen)
{
	char *p = NULL;
	char *retval;

	if (d_unlinked(dentry)) {
		p = buf + buflen;
		if (prepend(&p, &buflen, "//deleted", 10) != 0)
			goto Elong;
		buflen++;
	}
	retval = __dentry_path(dentry, buf, buflen);
	if (!IS_ERR(retval) && p)
		*p = '/';	/* restore '/' overriden with '\0' */
3442 3443 3444 3445 3446
	return retval;
Elong:
	return ERR_PTR(-ENAMETOOLONG);
}

3447 3448
static void get_fs_root_and_pwd_rcu(struct fs_struct *fs, struct path *root,
				    struct path *pwd)
3449
{
3450 3451 3452 3453 3454 3455 3456
	unsigned seq;

	do {
		seq = read_seqcount_begin(&fs->seq);
		*root = fs->root;
		*pwd = fs->pwd;
	} while (read_seqcount_retry(&fs->seq, seq));
3457 3458
}

L
Linus Torvalds 已提交
3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476
/*
 * NOTE! The user-level library version returns a
 * character pointer. The kernel system call just
 * returns the length of the buffer filled (which
 * includes the ending '\0' character), or a negative
 * error value. So libc would do something like
 *
 *	char *getcwd(char * buf, size_t size)
 *	{
 *		int retval;
 *
 *		retval = sys_getcwd(buf, size);
 *		if (retval >= 0)
 *			return buf;
 *		errno = -retval;
 *		return NULL;
 *	}
 */
3477
SYSCALL_DEFINE2(getcwd, char __user *, buf, unsigned long, size)
L
Linus Torvalds 已提交
3478
{
3479
	int error;
J
Jan Blunck 已提交
3480
	struct path pwd, root;
3481
	char *page = __getname();
L
Linus Torvalds 已提交
3482 3483 3484 3485

	if (!page)
		return -ENOMEM;

3486 3487
	rcu_read_lock();
	get_fs_root_and_pwd_rcu(current->fs, &root, &pwd);
L
Linus Torvalds 已提交
3488

3489
	error = -ENOENT;
3490
	if (!d_unlinked(pwd.dentry)) {
3491
		unsigned long len;
3492 3493
		char *cwd = page + PATH_MAX;
		int buflen = PATH_MAX;
L
Linus Torvalds 已提交
3494

3495
		prepend(&cwd, &buflen, "\0", 1);
3496
		error = prepend_path(&pwd, &root, &cwd, &buflen);
3497
		rcu_read_unlock();
3498

3499
		if (error < 0)
3500 3501
			goto out;

3502
		/* Unreachable from current root */
3503
		if (error > 0) {
3504 3505 3506 3507 3508
			error = prepend_unreachable(&cwd, &buflen);
			if (error)
				goto out;
		}

3509
		error = -ERANGE;
3510
		len = PATH_MAX + page - cwd;
3511 3512 3513 3514 3515
		if (len <= size) {
			error = len;
			if (copy_to_user(buf, cwd, len))
				error = -EFAULT;
		}
3516
	} else {
3517
		rcu_read_unlock();
3518
	}
L
Linus Torvalds 已提交
3519 3520

out:
3521
	__putname(page);
L
Linus Torvalds 已提交
3522 3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535
	return error;
}

/*
 * Test whether new_dentry is a subdirectory of old_dentry.
 *
 * Trivially implemented using the dcache structure
 */

/**
 * is_subdir - is new dentry a subdirectory of old_dentry
 * @new_dentry: new dentry
 * @old_dentry: old dentry
 *
Y
Yaowei Bai 已提交
3536 3537
 * Returns true if new_dentry is a subdirectory of the parent (at any depth).
 * Returns false otherwise.
L
Linus Torvalds 已提交
3538 3539 3540
 * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
 */
  
Y
Yaowei Bai 已提交
3541
bool is_subdir(struct dentry *new_dentry, struct dentry *old_dentry)
L
Linus Torvalds 已提交
3542
{
Y
Yaowei Bai 已提交
3543
	bool result;
3544
	unsigned seq;
L
Linus Torvalds 已提交
3545

3546
	if (new_dentry == old_dentry)
Y
Yaowei Bai 已提交
3547
		return true;
3548 3549

	do {
L
Linus Torvalds 已提交
3550 3551
		/* for restarting inner loop in case of seq retry */
		seq = read_seqbegin(&rename_lock);
3552 3553 3554 3555 3556
		/*
		 * Need rcu_readlock to protect against the d_parent trashing
		 * due to d_move
		 */
		rcu_read_lock();
3557
		if (d_ancestor(old_dentry, new_dentry))
Y
Yaowei Bai 已提交
3558
			result = true;
3559
		else
Y
Yaowei Bai 已提交
3560
			result = false;
3561
		rcu_read_unlock();
L
Linus Torvalds 已提交
3562 3563 3564 3565
	} while (read_seqretry(&rename_lock, seq));

	return result;
}
3566
EXPORT_SYMBOL(is_subdir);
L
Linus Torvalds 已提交
3567

M
Miklos Szeredi 已提交
3568
static enum d_walk_ret d_genocide_kill(void *data, struct dentry *dentry)
L
Linus Torvalds 已提交
3569
{
M
Miklos Szeredi 已提交
3570 3571 3572 3573
	struct dentry *root = data;
	if (dentry != root) {
		if (d_unhashed(dentry) || !dentry->d_inode)
			return D_WALK_SKIP;
L
Linus Torvalds 已提交
3574

M
Miklos Szeredi 已提交
3575 3576 3577 3578
		if (!(dentry->d_flags & DCACHE_GENOCIDE)) {
			dentry->d_flags |= DCACHE_GENOCIDE;
			dentry->d_lockref.count--;
		}
L
Linus Torvalds 已提交
3579
	}
M
Miklos Szeredi 已提交
3580 3581
	return D_WALK_CONTINUE;
}
3582

M
Miklos Szeredi 已提交
3583 3584 3585
void d_genocide(struct dentry *parent)
{
	d_walk(parent, parent, d_genocide_kill, NULL);
L
Linus Torvalds 已提交
3586 3587
}

3588
void d_tmpfile(struct dentry *dentry, struct inode *inode)
L
Linus Torvalds 已提交
3589
{
3590 3591
	inode_dec_link_count(inode);
	BUG_ON(dentry->d_name.name != dentry->d_iname ||
3592
		!hlist_unhashed(&dentry->d_u.d_alias) ||
3593 3594 3595 3596 3597 3598 3599 3600
		!d_unlinked(dentry));
	spin_lock(&dentry->d_parent->d_lock);
	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
	dentry->d_name.len = sprintf(dentry->d_iname, "#%llu",
				(unsigned long long)inode->i_ino);
	spin_unlock(&dentry->d_lock);
	spin_unlock(&dentry->d_parent->d_lock);
	d_instantiate(dentry, inode);
L
Linus Torvalds 已提交
3601
}
3602
EXPORT_SYMBOL(d_tmpfile);
L
Linus Torvalds 已提交
3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623

static __initdata unsigned long dhash_entries;
static int __init set_dhash_entries(char *str)
{
	if (!str)
		return 0;
	dhash_entries = simple_strtoul(str, &str, 0);
	return 1;
}
__setup("dhash_entries=", set_dhash_entries);

static void __init dcache_init_early(void)
{
	/* If hashes are distributed across NUMA nodes, defer
	 * hash allocation until vmalloc space is available.
	 */
	if (hashdist)
		return;

	dentry_hashtable =
		alloc_large_system_hash("Dentry cache",
3624
					sizeof(struct hlist_bl_head),
L
Linus Torvalds 已提交
3625 3626
					dhash_entries,
					13,
3627
					HASH_EARLY | HASH_ZERO,
L
Linus Torvalds 已提交
3628
					&d_hash_shift,
3629
					NULL,
3630
					0,
L
Linus Torvalds 已提交
3631
					0);
3632
	d_hash_shift = 32 - d_hash_shift;
L
Linus Torvalds 已提交
3633 3634
}

3635
static void __init dcache_init(void)
L
Linus Torvalds 已提交
3636
{
3637
	/*
L
Linus Torvalds 已提交
3638 3639
	 * A constructor could be added for stable state like the lists,
	 * but it is probably not worth it because of the cache nature
3640
	 * of the dcache.
L
Linus Torvalds 已提交
3641
	 */
3642 3643 3644
	dentry_cache = KMEM_CACHE_USERCOPY(dentry,
		SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD|SLAB_ACCOUNT,
		d_iname);
L
Linus Torvalds 已提交
3645 3646 3647 3648 3649 3650 3651

	/* Hash may have been set up in dcache_init_early */
	if (!hashdist)
		return;

	dentry_hashtable =
		alloc_large_system_hash("Dentry cache",
3652
					sizeof(struct hlist_bl_head),
L
Linus Torvalds 已提交
3653 3654
					dhash_entries,
					13,
3655
					HASH_ZERO,
L
Linus Torvalds 已提交
3656
					&d_hash_shift,
3657
					NULL,
3658
					0,
L
Linus Torvalds 已提交
3659
					0);
3660
	d_hash_shift = 32 - d_hash_shift;
L
Linus Torvalds 已提交
3661 3662 3663
}

/* SLAB cache for __getname() consumers */
3664
struct kmem_cache *names_cachep __read_mostly;
3665
EXPORT_SYMBOL(names_cachep);
L
Linus Torvalds 已提交
3666 3667 3668 3669 3670

EXPORT_SYMBOL(d_genocide);

void __init vfs_caches_init_early(void)
{
3671 3672 3673 3674 3675
	int i;

	for (i = 0; i < ARRAY_SIZE(in_lookup_hashtable); i++)
		INIT_HLIST_BL_HEAD(&in_lookup_hashtable[i]);

L
Linus Torvalds 已提交
3676 3677 3678 3679
	dcache_init_early();
	inode_init_early();
}

3680
void __init vfs_caches_init(void)
L
Linus Torvalds 已提交
3681
{
3682 3683
	names_cachep = kmem_cache_create_usercopy("names_cache", PATH_MAX, 0,
			SLAB_HWCACHE_ALIGN|SLAB_PANIC, 0, PATH_MAX, NULL);
L
Linus Torvalds 已提交
3684

3685 3686
	dcache_init();
	inode_init();
3687 3688
	files_init();
	files_maxfiles_init();
3689
	mnt_init();
L
Linus Torvalds 已提交
3690 3691 3692
	bdev_cache_init();
	chrdev_init();
}