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