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