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