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