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/module.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 "internal.h"
  37
  38int sysctl_vfs_cache_pressure __read_mostly = 100;
  39EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);
  40
  41 __cacheline_aligned_in_smp DEFINE_SPINLOCK(dcache_lock);
  42__cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
  43
  44EXPORT_SYMBOL(dcache_lock);
  45
  46static struct kmem_cache *dentry_cache __read_mostly;
  47
  48#define DNAME_INLINE_LEN (sizeof(struct dentry)-offsetof(struct dentry,d_iname))
  49
  50/*
  51 * This is the single most critical data structure when it comes
  52 * to the dcache: the hashtable for lookups. Somebody should try
  53 * to make this good - I've just made it work.
  54 *
  55 * This hash-function tries to avoid losing too many bits of hash
  56 * information, yet avoid using a prime hash-size or similar.
  57 */
  58#define D_HASHBITS     d_hash_shift
  59#define D_HASHMASK     d_hash_mask
  60
  61static unsigned int d_hash_mask __read_mostly;
  62static unsigned int d_hash_shift __read_mostly;
  63static struct hlist_head *dentry_hashtable __read_mostly;
  64
  65/* Statistics gathering. */
  66struct dentry_stat_t dentry_stat = {
  67        .age_limit = 45,
  68};
  69
  70static void __d_free(struct dentry *dentry)
  71{
  72        WARN_ON(!list_empty(&dentry->d_alias));
  73        if (dname_external(dentry))
  74                kfree(dentry->d_name.name);
  75        kmem_cache_free(dentry_cache, dentry); 
  76}
  77
  78static void d_callback(struct rcu_head *head)
  79{
  80        struct dentry * dentry = container_of(head, struct dentry, d_u.d_rcu);
  81        __d_free(dentry);
  82}
  83
  84/*
  85 * no dcache_lock, please.  The caller must decrement dentry_stat.nr_dentry
  86 * inside dcache_lock.
  87 */
  88static void d_free(struct dentry *dentry)
  89{
  90        if (dentry->d_op && dentry->d_op->d_release)
  91                dentry->d_op->d_release(dentry);
  92        /* if dentry was never inserted into hash, immediate free is OK */
  93        if (hlist_unhashed(&dentry->d_hash))
  94                __d_free(dentry);
  95        else
  96                call_rcu(&dentry->d_u.d_rcu, d_callback);
  97}
  98
  99/*
 100 * Release the dentry's inode, using the filesystem
 101 * d_iput() operation if defined.
 102 */
 103static void dentry_iput(struct dentry * dentry)
 104        __releases(dentry->d_lock)
 105        __releases(dcache_lock)
 106{
 107        struct inode *inode = dentry->d_inode;
 108        if (inode) {
 109                dentry->d_inode = NULL;
 110                list_del_init(&dentry->d_alias);
 111                spin_unlock(&dentry->d_lock);
 112                spin_unlock(&dcache_lock);
 113                if (!inode->i_nlink)
 114                        fsnotify_inoderemove(inode);
 115                if (dentry->d_op && dentry->d_op->d_iput)
 116                        dentry->d_op->d_iput(dentry, inode);
 117                else
 118                        iput(inode);
 119        } else {
 120                spin_unlock(&dentry->d_lock);
 121                spin_unlock(&dcache_lock);
 122        }
 123}
 124
 125/*
 126 * dentry_lru_(add|add_tail|del|del_init) must be called with dcache_lock held.
 127 */
 128static void dentry_lru_add(struct dentry *dentry)
 129{
 130        list_add(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
 131        dentry->d_sb->s_nr_dentry_unused++;
 132        dentry_stat.nr_unused++;
 133}
 134
 135static void dentry_lru_add_tail(struct dentry *dentry)
 136{
 137        list_add_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
 138        dentry->d_sb->s_nr_dentry_unused++;
 139        dentry_stat.nr_unused++;
 140}
 141
 142static void dentry_lru_del(struct dentry *dentry)
 143{
 144        if (!list_empty(&dentry->d_lru)) {
 145                list_del(&dentry->d_lru);
 146                dentry->d_sb->s_nr_dentry_unused--;
 147                dentry_stat.nr_unused--;
 148        }
 149}
 150
 151static void dentry_lru_del_init(struct dentry *dentry)
 152{
 153        if (likely(!list_empty(&dentry->d_lru))) {
 154                list_del_init(&dentry->d_lru);
 155                dentry->d_sb->s_nr_dentry_unused--;
 156                dentry_stat.nr_unused--;
 157        }
 158}
 159
 160/**
 161 * d_kill - kill dentry and return parent
 162 * @dentry: dentry to kill
 163 *
 164 * The dentry must already be unhashed and removed from the LRU.
 165 *
 166 * If this is the root of the dentry tree, return NULL.
 167 */
 168static struct dentry *d_kill(struct dentry *dentry)
 169        __releases(dentry->d_lock)
 170        __releases(dcache_lock)
 171{
 172        struct dentry *parent;
 173
 174        list_del(&dentry->d_u.d_child);
 175        dentry_stat.nr_dentry--;        /* For d_free, below */
 176        /*drops the locks, at that point nobody can reach this dentry */
 177        dentry_iput(dentry);
 178        if (IS_ROOT(dentry))
 179                parent = NULL;
 180        else
 181                parent = dentry->d_parent;
 182        d_free(dentry);
 183        return parent;
 184}
 185
 186/* 
 187 * This is dput
 188 *
 189 * This is complicated by the fact that we do not want to put
 190 * dentries that are no longer on any hash chain on the unused
 191 * list: we'd much rather just get rid of them immediately.
 192 *
 193 * However, that implies that we have to traverse the dentry
 194 * tree upwards to the parents which might _also_ now be
 195 * scheduled for deletion (it may have been only waiting for
 196 * its last child to go away).
 197 *
 198 * This tail recursion is done by hand as we don't want to depend
 199 * on the compiler to always get this right (gcc generally doesn't).
 200 * Real recursion would eat up our stack space.
 201 */
 202
 203/*
 204 * dput - release a dentry
 205 * @dentry: dentry to release 
 206 *
 207 * Release a dentry. This will drop the usage count and if appropriate
 208 * call the dentry unlink method as well as removing it from the queues and
 209 * releasing its resources. If the parent dentries were scheduled for release
 210 * they too may now get deleted.
 211 *
 212 * no dcache lock, please.
 213 */
 214
 215void dput(struct dentry *dentry)
 216{
 217        if (!dentry)
 218                return;
 219
 220repeat:
 221        if (atomic_read(&dentry->d_count) == 1)
 222                might_sleep();
 223        if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
 224                return;
 225
 226        spin_lock(&dentry->d_lock);
 227        if (atomic_read(&dentry->d_count)) {
 228                spin_unlock(&dentry->d_lock);
 229                spin_unlock(&dcache_lock);
 230                return;
 231        }
 232
 233        /*
 234         * AV: ->d_delete() is _NOT_ allowed to block now.
 235         */
 236        if (dentry->d_op && dentry->d_op->d_delete) {
 237                if (dentry->d_op->d_delete(dentry))
 238                        goto unhash_it;
 239        }
 240        /* Unreachable? Get rid of it */
 241        if (d_unhashed(dentry))
 242                goto kill_it;
 243        if (list_empty(&dentry->d_lru)) {
 244                dentry->d_flags |= DCACHE_REFERENCED;
 245                dentry_lru_add(dentry);
 246        }
 247        spin_unlock(&dentry->d_lock);
 248        spin_unlock(&dcache_lock);
 249        return;
 250
 251unhash_it:
 252        __d_drop(dentry);
 253kill_it:
 254        /* if dentry was on the d_lru list delete it from there */
 255        dentry_lru_del(dentry);
 256        dentry = d_kill(dentry);
 257        if (dentry)
 258                goto repeat;
 259}
 260EXPORT_SYMBOL(dput);
 261
 262/**
 263 * d_invalidate - invalidate a dentry
 264 * @dentry: dentry to invalidate
 265 *
 266 * Try to invalidate the dentry if it turns out to be
 267 * possible. If there are other dentries that can be
 268 * reached through this one we can't delete it and we
 269 * return -EBUSY. On success we return 0.
 270 *
 271 * no dcache lock.
 272 */
 273 
 274int d_invalidate(struct dentry * dentry)
 275{
 276        /*
 277         * If it's already been dropped, return OK.
 278         */
 279        spin_lock(&dcache_lock);
 280        if (d_unhashed(dentry)) {
 281                spin_unlock(&dcache_lock);
 282                return 0;
 283        }
 284        /*
 285         * Check whether to do a partial shrink_dcache
 286         * to get rid of unused child entries.
 287         */
 288        if (!list_empty(&dentry->d_subdirs)) {
 289                spin_unlock(&dcache_lock);
 290                shrink_dcache_parent(dentry);
 291                spin_lock(&dcache_lock);
 292        }
 293
 294        /*
 295         * Somebody else still using it?
 296         *
 297         * If it's a directory, we can't drop it
 298         * for fear of somebody re-populating it
 299         * with children (even though dropping it
 300         * would make it unreachable from the root,
 301         * we might still populate it if it was a
 302         * working directory or similar).
 303         */
 304        spin_lock(&dentry->d_lock);
 305        if (atomic_read(&dentry->d_count) > 1) {
 306                if (dentry->d_inode && S_ISDIR(dentry->d_inode->i_mode)) {
 307                        spin_unlock(&dentry->d_lock);
 308                        spin_unlock(&dcache_lock);
 309                        return -EBUSY;
 310                }
 311        }
 312
 313        __d_drop(dentry);
 314        spin_unlock(&dentry->d_lock);
 315        spin_unlock(&dcache_lock);
 316        return 0;
 317}
 318EXPORT_SYMBOL(d_invalidate);
 319
 320/* This should be called _only_ with dcache_lock held */
 321
 322static inline struct dentry * __dget_locked(struct dentry *dentry)
 323{
 324        atomic_inc(&dentry->d_count);
 325        dentry_lru_del_init(dentry);
 326        return dentry;
 327}
 328
 329struct dentry * dget_locked(struct dentry *dentry)
 330{
 331        return __dget_locked(dentry);
 332}
 333EXPORT_SYMBOL(dget_locked);
 334
 335/**
 336 * d_find_alias - grab a hashed alias of inode
 337 * @inode: inode in question
 338 * @want_discon:  flag, used by d_splice_alias, to request
 339 *          that only a DISCONNECTED alias be returned.
 340 *
 341 * If inode has a hashed alias, or is a directory and has any alias,
 342 * acquire the reference to alias and return it. Otherwise return NULL.
 343 * Notice that if inode is a directory there can be only one alias and
 344 * it can be unhashed only if it has no children, or if it is the root
 345 * of a filesystem.
 346 *
 347 * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
 348 * any other hashed alias over that one unless @want_discon is set,
 349 * in which case only return an IS_ROOT, DCACHE_DISCONNECTED alias.
 350 */
 351
 352static struct dentry * __d_find_alias(struct inode *inode, int want_discon)
 353{
 354        struct list_head *head, *next, *tmp;
 355        struct dentry *alias, *discon_alias=NULL;
 356
 357        head = &inode->i_dentry;
 358        next = inode->i_dentry.next;
 359        while (next != head) {
 360                tmp = next;
 361                next = tmp->next;
 362                prefetch(next);
 363                alias = list_entry(tmp, struct dentry, d_alias);
 364                if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
 365                        if (IS_ROOT(alias) &&
 366                            (alias->d_flags & DCACHE_DISCONNECTED))
 367                                discon_alias = alias;
 368                        else if (!want_discon) {
 369                                __dget_locked(alias);
 370                                return alias;
 371                        }
 372                }
 373        }
 374        if (discon_alias)
 375                __dget_locked(discon_alias);
 376        return discon_alias;
 377}
 378
 379struct dentry * d_find_alias(struct inode *inode)
 380{
 381        struct dentry *de = NULL;
 382
 383        if (!list_empty(&inode->i_dentry)) {
 384                spin_lock(&dcache_lock);
 385                de = __d_find_alias(inode, 0);
 386                spin_unlock(&dcache_lock);
 387        }
 388        return de;
 389}
 390EXPORT_SYMBOL(d_find_alias);
 391
 392/*
 393 *      Try to kill dentries associated with this inode.
 394 * WARNING: you must own a reference to inode.
 395 */
 396void d_prune_aliases(struct inode *inode)
 397{
 398        struct dentry *dentry;
 399restart:
 400        spin_lock(&dcache_lock);
 401        list_for_each_entry(dentry, &inode->i_dentry, d_alias) {
 402                spin_lock(&dentry->d_lock);
 403                if (!atomic_read(&dentry->d_count)) {
 404                        __dget_locked(dentry);
 405                        __d_drop(dentry);
 406                        spin_unlock(&dentry->d_lock);
 407                        spin_unlock(&dcache_lock);
 408                        dput(dentry);
 409                        goto restart;
 410                }
 411                spin_unlock(&dentry->d_lock);
 412        }
 413        spin_unlock(&dcache_lock);
 414}
 415EXPORT_SYMBOL(d_prune_aliases);
 416
 417/*
 418 * Throw away a dentry - free the inode, dput the parent.  This requires that
 419 * the LRU list has already been removed.
 420 *
 421 * Try to prune ancestors as well.  This is necessary to prevent
 422 * quadratic behavior of shrink_dcache_parent(), but is also expected
 423 * to be beneficial in reducing dentry cache fragmentation.
 424 */
 425static void prune_one_dentry(struct dentry * dentry)
 426        __releases(dentry->d_lock)
 427        __releases(dcache_lock)
 428        __acquires(dcache_lock)
 429{
 430        __d_drop(dentry);
 431        dentry = d_kill(dentry);
 432
 433        /*
 434         * Prune ancestors.  Locking is simpler than in dput(),
 435         * because dcache_lock needs to be taken anyway.
 436         */
 437        spin_lock(&dcache_lock);
 438        while (dentry) {
 439                if (!atomic_dec_and_lock(&dentry->d_count, &dentry->d_lock))
 440                        return;
 441
 442                if (dentry->d_op && dentry->d_op->d_delete)
 443                        dentry->d_op->d_delete(dentry);
 444                dentry_lru_del_init(dentry);
 445                __d_drop(dentry);
 446                dentry = d_kill(dentry);
 447                spin_lock(&dcache_lock);
 448        }
 449}
 450
 451/*
 452 * Shrink the dentry LRU on a given superblock.
 453 * @sb   : superblock to shrink dentry LRU.
 454 * @count: If count is NULL, we prune all dentries on superblock.
 455 * @flags: If flags is non-zero, we need to do special processing based on
 456 * which flags are set. This means we don't need to maintain multiple
 457 * similar copies of this loop.
 458 */
 459static void __shrink_dcache_sb(struct super_block *sb, int *count, int flags)
 460{
 461        LIST_HEAD(referenced);
 462        LIST_HEAD(tmp);
 463        struct dentry *dentry;
 464        int cnt = 0;
 465
 466        BUG_ON(!sb);
 467        BUG_ON((flags & DCACHE_REFERENCED) && count == NULL);
 468        spin_lock(&dcache_lock);
 469        if (count != NULL)
 470                /* called from prune_dcache() and shrink_dcache_parent() */
 471                cnt = *count;
 472restart:
 473        if (count == NULL)
 474                list_splice_init(&sb->s_dentry_lru, &tmp);
 475        else {
 476                while (!list_empty(&sb->s_dentry_lru)) {
 477                        dentry = list_entry(sb->s_dentry_lru.prev,
 478                                        struct dentry, d_lru);
 479                        BUG_ON(dentry->d_sb != sb);
 480
 481                        spin_lock(&dentry->d_lock);
 482                        /*
 483                         * If we are honouring the DCACHE_REFERENCED flag and
 484                         * the dentry has this flag set, don't free it. Clear
 485                         * the flag and put it back on the LRU.
 486                         */
 487                        if ((flags & DCACHE_REFERENCED)
 488                                && (dentry->d_flags & DCACHE_REFERENCED)) {
 489                                dentry->d_flags &= ~DCACHE_REFERENCED;
 490                                list_move(&dentry->d_lru, &referenced);
 491                                spin_unlock(&dentry->d_lock);
 492                        } else {
 493                                list_move_tail(&dentry->d_lru, &tmp);
 494                                spin_unlock(&dentry->d_lock);
 495                                cnt--;
 496                                if (!cnt)
 497                                        break;
 498                        }
 499                        cond_resched_lock(&dcache_lock);
 500                }
 501        }
 502        while (!list_empty(&tmp)) {
 503                dentry = list_entry(tmp.prev, struct dentry, d_lru);
 504                dentry_lru_del_init(dentry);
 505                spin_lock(&dentry->d_lock);
 506                /*
 507                 * We found an inuse dentry which was not removed from
 508                 * the LRU because of laziness during lookup.  Do not free
 509                 * it - just keep it off the LRU list.
 510                 */
 511                if (atomic_read(&dentry->d_count)) {
 512                        spin_unlock(&dentry->d_lock);
 513                        continue;
 514                }
 515                prune_one_dentry(dentry);
 516                /* dentry->d_lock was dropped in prune_one_dentry() */
 517                cond_resched_lock(&dcache_lock);
 518        }
 519        if (count == NULL && !list_empty(&sb->s_dentry_lru))
 520                goto restart;
 521        if (count != NULL)
 522                *count = cnt;
 523        if (!list_empty(&referenced))
 524                list_splice(&referenced, &sb->s_dentry_lru);
 525        spin_unlock(&dcache_lock);
 526}
 527
 528/**
 529 * prune_dcache - shrink the dcache
 530 * @count: number of entries to try to free
 531 *
 532 * Shrink the dcache. This is done when we need more memory, or simply when we
 533 * need to unmount something (at which point we need to unuse all dentries).
 534 *
 535 * This function may fail to free any resources if all the dentries are in use.
 536 */
 537static void prune_dcache(int count)
 538{
 539        struct super_block *sb, *n;
 540        int w_count;
 541        int unused = dentry_stat.nr_unused;
 542        int prune_ratio;
 543        int pruned;
 544
 545        if (unused == 0 || count == 0)
 546                return;
 547        spin_lock(&dcache_lock);
 548        if (count >= unused)
 549                prune_ratio = 1;
 550        else
 551                prune_ratio = unused / count;
 552        spin_lock(&sb_lock);
 553        list_for_each_entry_safe(sb, n, &super_blocks, s_list) {
 554                if (list_empty(&sb->s_instances))
 555                        continue;
 556                if (sb->s_nr_dentry_unused == 0)
 557                        continue;
 558                sb->s_count++;
 559                /* Now, we reclaim unused dentrins with fairness.
 560                 * We reclaim them same percentage from each superblock.
 561                 * We calculate number of dentries to scan on this sb
 562                 * as follows, but the implementation is arranged to avoid
 563                 * overflows:
 564                 * number of dentries to scan on this sb =
 565                 * count * (number of dentries on this sb /
 566                 * number of dentries in the machine)
 567                 */
 568                spin_unlock(&sb_lock);
 569                if (prune_ratio != 1)
 570                        w_count = (sb->s_nr_dentry_unused / prune_ratio) + 1;
 571                else
 572                        w_count = sb->s_nr_dentry_unused;
 573                pruned = w_count;
 574                /*
 575                 * We need to be sure this filesystem isn't being unmounted,
 576                 * otherwise we could race with generic_shutdown_super(), and
 577                 * end up holding a reference to an inode while the filesystem
 578                 * is unmounted.  So we try to get s_umount, and make sure
 579                 * s_root isn't NULL.
 580                 */
 581                if (down_read_trylock(&sb->s_umount)) {
 582                        if ((sb->s_root != NULL) &&
 583                            (!list_empty(&sb->s_dentry_lru))) {
 584                                spin_unlock(&dcache_lock);
 585                                __shrink_dcache_sb(sb, &w_count,
 586                                                DCACHE_REFERENCED);
 587                                pruned -= w_count;
 588                                spin_lock(&dcache_lock);
 589                        }
 590                        up_read(&sb->s_umount);
 591                }
 592                spin_lock(&sb_lock);
 593                /* lock was dropped, must reset next */
 594                list_safe_reset_next(sb, n, s_list);
 595                count -= pruned;
 596                __put_super(sb);
 597                /* more work left to do? */
 598                if (count <= 0)
 599                        break;
 600        }
 601        spin_unlock(&sb_lock);
 602        spin_unlock(&dcache_lock);
 603}
 604
 605/**
 606 * shrink_dcache_sb - shrink dcache for a superblock
 607 * @sb: superblock
 608 *
 609 * Shrink the dcache for the specified super block. This
 610 * is used to free the dcache before unmounting a file
 611 * system
 612 */
 613void shrink_dcache_sb(struct super_block * sb)
 614{
 615        __shrink_dcache_sb(sb, NULL, 0);
 616}
 617EXPORT_SYMBOL(shrink_dcache_sb);
 618
 619/*
 620 * destroy a single subtree of dentries for unmount
 621 * - see the comments on shrink_dcache_for_umount() for a description of the
 622 *   locking
 623 */
 624static void shrink_dcache_for_umount_subtree(struct dentry *dentry)
 625{
 626        struct dentry *parent;
 627        unsigned detached = 0;
 628
 629        BUG_ON(!IS_ROOT(dentry));
 630
 631        /* detach this root from the system */
 632        spin_lock(&dcache_lock);
 633        dentry_lru_del_init(dentry);
 634        __d_drop(dentry);
 635        spin_unlock(&dcache_lock);
 636
 637        for (;;) {
 638                /* descend to the first leaf in the current subtree */
 639                while (!list_empty(&dentry->d_subdirs)) {
 640                        struct dentry *loop;
 641
 642                        /* this is a branch with children - detach all of them
 643                         * from the system in one go */
 644                        spin_lock(&dcache_lock);
 645                        list_for_each_entry(loop, &dentry->d_subdirs,
 646                                            d_u.d_child) {
 647                                dentry_lru_del_init(loop);
 648                                __d_drop(loop);
 649                                cond_resched_lock(&dcache_lock);
 650                        }
 651                        spin_unlock(&dcache_lock);
 652
 653                        /* move to the first child */
 654                        dentry = list_entry(dentry->d_subdirs.next,
 655                                            struct dentry, d_u.d_child);
 656                }
 657
 658                /* consume the dentries from this leaf up through its parents
 659                 * until we find one with children or run out altogether */
 660                do {
 661                        struct inode *inode;
 662
 663                        if (atomic_read(&dentry->d_count) != 0) {
 664                                printk(KERN_ERR
 665                                       "BUG: Dentry %p{i=%lx,n=%s}"
 666                                       " still in use (%d)"
 667                                       " [unmount of %s %s]\n",
 668                                       dentry,
 669                                       dentry->d_inode ?
 670                                       dentry->d_inode->i_ino : 0UL,
 671                                       dentry->d_name.name,
 672                                       atomic_read(&dentry->d_count),
 673                                       dentry->d_sb->s_type->name,
 674                                       dentry->d_sb->s_id);
 675                                BUG();
 676                        }
 677
 678                        if (IS_ROOT(dentry))
 679                                parent = NULL;
 680                        else {
 681                                parent = dentry->d_parent;
 682                                atomic_dec(&parent->d_count);
 683                        }
 684
 685                        list_del(&dentry->d_u.d_child);
 686                        detached++;
 687
 688                        inode = dentry->d_inode;
 689                        if (inode) {
 690                                dentry->d_inode = NULL;
 691                                list_del_init(&dentry->d_alias);
 692                                if (dentry->d_op && dentry->d_op->d_iput)
 693                                        dentry->d_op->d_iput(dentry, inode);
 694                                else
 695                                        iput(inode);
 696                        }
 697
 698                        d_free(dentry);
 699
 700                        /* finished when we fall off the top of the tree,
 701                         * otherwise we ascend to the parent and move to the
 702                         * next sibling if there is one */
 703                        if (!parent)
 704                                goto out;
 705
 706                        dentry = parent;
 707
 708                } while (list_empty(&dentry->d_subdirs));
 709
 710                dentry = list_entry(dentry->d_subdirs.next,
 711                                    struct dentry, d_u.d_child);
 712        }
 713out:
 714        /* several dentries were freed, need to correct nr_dentry */
 715        spin_lock(&dcache_lock);
 716        dentry_stat.nr_dentry -= detached;
 717        spin_unlock(&dcache_lock);
 718}
 719
 720/*
 721 * destroy the dentries attached to a superblock on unmounting
 722 * - we don't need to use dentry->d_lock, and only need dcache_lock when
 723 *   removing the dentry from the system lists and hashes because:
 724 *   - the superblock is detached from all mountings and open files, so the
 725 *     dentry trees will not be rearranged by the VFS
 726 *   - s_umount is write-locked, so the memory pressure shrinker will ignore
 727 *     any dentries belonging to this superblock that it comes across
 728 *   - the filesystem itself is no longer permitted to rearrange the dentries
 729 *     in this superblock
 730 */
 731void shrink_dcache_for_umount(struct super_block *sb)
 732{
 733        struct dentry *dentry;
 734
 735        if (down_read_trylock(&sb->s_umount))
 736                BUG();
 737
 738        dentry = sb->s_root;
 739        sb->s_root = NULL;
 740        atomic_dec(&dentry->d_count);
 741        shrink_dcache_for_umount_subtree(dentry);
 742
 743        while (!hlist_empty(&sb->s_anon)) {
 744                dentry = hlist_entry(sb->s_anon.first, struct dentry, d_hash);
 745                shrink_dcache_for_umount_subtree(dentry);
 746        }
 747}
 748
 749/*
 750 * Search for at least 1 mount point in the dentry's subdirs.
 751 * We descend to the next level whenever the d_subdirs
 752 * list is non-empty and continue searching.
 753 */
 754 
 755/**
 756 * have_submounts - check for mounts over a dentry
 757 * @parent: dentry to check.
 758 *
 759 * Return true if the parent or its subdirectories contain
 760 * a mount point
 761 */
 762 
 763int have_submounts(struct dentry *parent)
 764{
 765        struct dentry *this_parent = parent;
 766        struct list_head *next;
 767
 768        spin_lock(&dcache_lock);
 769        if (d_mountpoint(parent))
 770                goto positive;
 771repeat:
 772        next = this_parent->d_subdirs.next;
 773resume:
 774        while (next != &this_parent->d_subdirs) {
 775                struct list_head *tmp = next;
 776                struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
 777                next = tmp->next;
 778                /* Have we found a mount point ? */
 779                if (d_mountpoint(dentry))
 780                        goto positive;
 781                if (!list_empty(&dentry->d_subdirs)) {
 782                        this_parent = dentry;
 783                        goto repeat;
 784                }
 785        }
 786        /*
 787         * All done at this level ... ascend and resume the search.
 788         */
 789        if (this_parent != parent) {
 790                next = this_parent->d_u.d_child.next;
 791                this_parent = this_parent->d_parent;
 792                goto resume;
 793        }
 794        spin_unlock(&dcache_lock);
 795        return 0; /* No mount points found in tree */
 796positive:
 797        spin_unlock(&dcache_lock);
 798        return 1;
 799}
 800EXPORT_SYMBOL(have_submounts);
 801
 802/*
 803 * Search the dentry child list for the specified parent,
 804 * and move any unused dentries to the end of the unused
 805 * list for prune_dcache(). We descend to the next level
 806 * whenever the d_subdirs list is non-empty and continue
 807 * searching.
 808 *
 809 * It returns zero iff there are no unused children,
 810 * otherwise  it returns the number of children moved to
 811 * the end of the unused list. This may not be the total
 812 * number of unused children, because select_parent can
 813 * drop the lock and return early due to latency
 814 * constraints.
 815 */
 816static int select_parent(struct dentry * parent)
 817{
 818        struct dentry *this_parent = parent;
 819        struct list_head *next;
 820        int found = 0;
 821
 822        spin_lock(&dcache_lock);
 823repeat:
 824        next = this_parent->d_subdirs.next;
 825resume:
 826        while (next != &this_parent->d_subdirs) {
 827                struct list_head *tmp = next;
 828                struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
 829                next = tmp->next;
 830
 831                dentry_lru_del_init(dentry);
 832                /* 
 833                 * move only zero ref count dentries to the end 
 834                 * of the unused list for prune_dcache
 835                 */
 836                if (!atomic_read(&dentry->d_count)) {
 837                        dentry_lru_add_tail(dentry);
 838                        found++;
 839                }
 840
 841                /*
 842                 * We can return to the caller if we have found some (this
 843                 * ensures forward progress). We'll be coming back to find
 844                 * the rest.
 845                 */
 846                if (found && need_resched())
 847                        goto out;
 848
 849                /*
 850                 * Descend a level if the d_subdirs list is non-empty.
 851                 */
 852                if (!list_empty(&dentry->d_subdirs)) {
 853                        this_parent = dentry;
 854                        goto repeat;
 855                }
 856        }
 857        /*
 858         * All done at this level ... ascend and resume the search.
 859         */
 860        if (this_parent != parent) {
 861                next = this_parent->d_u.d_child.next;
 862                this_parent = this_parent->d_parent;
 863                goto resume;
 864        }
 865out:
 866        spin_unlock(&dcache_lock);
 867        return found;
 868}
 869
 870/**
 871 * shrink_dcache_parent - prune dcache
 872 * @parent: parent of entries to prune
 873 *
 874 * Prune the dcache to remove unused children of the parent dentry.
 875 */
 876 
 877void shrink_dcache_parent(struct dentry * parent)
 878{
 879        struct super_block *sb = parent->d_sb;
 880        int found;
 881
 882        while ((found = select_parent(parent)) != 0)
 883                __shrink_dcache_sb(sb, &found, 0);
 884}
 885EXPORT_SYMBOL(shrink_dcache_parent);
 886
 887/*
 888 * Scan `nr' dentries and return the number which remain.
 889 *
 890 * We need to avoid reentering the filesystem if the caller is performing a
 891 * GFP_NOFS allocation attempt.  One example deadlock is:
 892 *
 893 * ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
 894 * prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->put_inode->
 895 * ext2_discard_prealloc->ext2_free_blocks->lock_super->DEADLOCK.
 896 *
 897 * In this case we return -1 to tell the caller that we baled.
 898 */
 899static int shrink_dcache_memory(struct shrinker *shrink, int nr, gfp_t gfp_mask)
 900{
 901        if (nr) {
 902                if (!(gfp_mask & __GFP_FS))
 903                        return -1;
 904                prune_dcache(nr);
 905        }
 906        return (dentry_stat.nr_unused / 100) * sysctl_vfs_cache_pressure;
 907}
 908
 909static struct shrinker dcache_shrinker = {
 910        .shrink = shrink_dcache_memory,
 911        .seeks = DEFAULT_SEEKS,
 912};
 913
 914/**
 915 * d_alloc      -       allocate a dcache entry
 916 * @parent: parent of entry to allocate
 917 * @name: qstr of the name
 918 *
 919 * Allocates a dentry. It returns %NULL if there is insufficient memory
 920 * available. On a success the dentry is returned. The name passed in is
 921 * copied and the copy passed in may be reused after this call.
 922 */
 923 
 924struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
 925{
 926        struct dentry *dentry;
 927        char *dname;
 928
 929        dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
 930        if (!dentry)
 931                return NULL;
 932
 933        if (name->len > DNAME_INLINE_LEN-1) {
 934                dname = kmalloc(name->len + 1, GFP_KERNEL);
 935                if (!dname) {
 936                        kmem_cache_free(dentry_cache, dentry); 
 937                        return NULL;
 938                }
 939        } else  {
 940                dname = dentry->d_iname;
 941        }       
 942        dentry->d_name.name = dname;
 943
 944        dentry->d_name.len = name->len;
 945        dentry->d_name.hash = name->hash;
 946        memcpy(dname, name->name, name->len);
 947        dname[name->len] = 0;
 948
 949        atomic_set(&dentry->d_count, 1);
 950        dentry->d_flags = DCACHE_UNHASHED;
 951        spin_lock_init(&dentry->d_lock);
 952        dentry->d_inode = NULL;
 953        dentry->d_parent = NULL;
 954        dentry->d_sb = NULL;
 955        dentry->d_op = NULL;
 956        dentry->d_fsdata = NULL;
 957        dentry->d_mounted = 0;
 958        INIT_HLIST_NODE(&dentry->d_hash);
 959        INIT_LIST_HEAD(&dentry->d_lru);
 960        INIT_LIST_HEAD(&dentry->d_subdirs);
 961        INIT_LIST_HEAD(&dentry->d_alias);
 962
 963        if (parent) {
 964                dentry->d_parent = dget(parent);
 965                dentry->d_sb = parent->d_sb;
 966        } else {
 967                INIT_LIST_HEAD(&dentry->d_u.d_child);
 968        }
 969
 970        spin_lock(&dcache_lock);
 971        if (parent)
 972                list_add(&dentry->d_u.d_child, &parent->d_subdirs);
 973        dentry_stat.nr_dentry++;
 974        spin_unlock(&dcache_lock);
 975
 976        return dentry;
 977}
 978EXPORT_SYMBOL(d_alloc);
 979
 980struct dentry *d_alloc_name(struct dentry *parent, const char *name)
 981{
 982        struct qstr q;
 983
 984        q.name = name;
 985        q.len = strlen(name);
 986        q.hash = full_name_hash(q.name, q.len);
 987        return d_alloc(parent, &q);
 988}
 989EXPORT_SYMBOL(d_alloc_name);
 990
 991/* the caller must hold dcache_lock */
 992static void __d_instantiate(struct dentry *dentry, struct inode *inode)
 993{
 994        if (inode)
 995                list_add(&dentry->d_alias, &inode->i_dentry);
 996        dentry->d_inode = inode;
 997        fsnotify_d_instantiate(dentry, inode);
 998}
 999
1000/**
1001 * d_instantiate - fill in inode information for a dentry
1002 * @entry: dentry to complete
1003 * @inode: inode to attach to this dentry
1004 *
1005 * Fill in inode information in the entry.
1006 *
1007 * This turns negative dentries into productive full members
1008 * of society.
1009 *
1010 * NOTE! This assumes that the inode count has been incremented
1011 * (or otherwise set) by the caller to indicate that it is now
1012 * in use by the dcache.
1013 */
1014 
1015void d_instantiate(struct dentry *entry, struct inode * inode)
1016{
1017        BUG_ON(!list_empty(&entry->d_alias));
1018        spin_lock(&dcache_lock);
1019        __d_instantiate(entry, inode);
1020        spin_unlock(&dcache_lock);
1021        security_d_instantiate(entry, inode);
1022}
1023EXPORT_SYMBOL(d_instantiate);
1024
1025/**
1026 * d_instantiate_unique - instantiate a non-aliased dentry
1027 * @entry: dentry to instantiate
1028 * @inode: inode to attach to this dentry
1029 *
1030 * Fill in inode information in the entry. On success, it returns NULL.
1031 * If an unhashed alias of "entry" already exists, then we return the
1032 * aliased dentry instead and drop one reference to inode.
1033 *
1034 * Note that in order to avoid conflicts with rename() etc, the caller
1035 * had better be holding the parent directory semaphore.
1036 *
1037 * This also assumes that the inode count has been incremented
1038 * (or otherwise set) by the caller to indicate that it is now
1039 * in use by the dcache.
1040 */
1041static struct dentry *__d_instantiate_unique(struct dentry *entry,
1042                                             struct inode *inode)
1043{
1044        struct dentry *alias;
1045        int len = entry->d_name.len;
1046        const char *name = entry->d_name.name;
1047        unsigned int hash = entry->d_name.hash;
1048
1049        if (!inode) {
1050                __d_instantiate(entry, NULL);
1051                return NULL;
1052        }
1053
1054        list_for_each_entry(alias, &inode->i_dentry, d_alias) {
1055                struct qstr *qstr = &alias->d_name;
1056
1057                if (qstr->hash != hash)
1058                        continue;
1059                if (alias->d_parent != entry->d_parent)
1060                        continue;
1061                if (qstr->len != len)
1062                        continue;
1063                if (memcmp(qstr->name, name, len))
1064                        continue;
1065                dget_locked(alias);
1066                return alias;
1067        }
1068
1069        __d_instantiate(entry, inode);
1070        return NULL;
1071}
1072
1073struct dentry *d_instantiate_unique(struct dentry *entry, struct inode *inode)
1074{
1075        struct dentry *result;
1076
1077        BUG_ON(!list_empty(&entry->d_alias));
1078
1079        spin_lock(&dcache_lock);
1080        result = __d_instantiate_unique(entry, inode);
1081        spin_unlock(&dcache_lock);
1082
1083        if (!result) {
1084                security_d_instantiate(entry, inode);
1085                return NULL;
1086        }
1087
1088        BUG_ON(!d_unhashed(result));
1089        iput(inode);
1090        return result;
1091}
1092
1093EXPORT_SYMBOL(d_instantiate_unique);
1094
1095/**
1096 * d_alloc_root - allocate root dentry
1097 * @root_inode: inode to allocate the root for
1098 *
1099 * Allocate a root ("/") dentry for the inode given. The inode is
1100 * instantiated and returned. %NULL is returned if there is insufficient
1101 * memory or the inode passed is %NULL.
1102 */
1103 
1104struct dentry * d_alloc_root(struct inode * root_inode)
1105{
1106        struct dentry *res = NULL;
1107
1108        if (root_inode) {
1109                static const struct qstr name = { .name = "/", .len = 1 };
1110
1111                res = d_alloc(NULL, &name);
1112                if (res) {
1113                        res->d_sb = root_inode->i_sb;
1114                        res->d_parent = res;
1115                        d_instantiate(res, root_inode);
1116                }
1117        }
1118        return res;
1119}
1120EXPORT_SYMBOL(d_alloc_root);
1121
1122static inline struct hlist_head *d_hash(struct dentry *parent,
1123                                        unsigned long hash)
1124{
1125        hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
1126        hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
1127        return dentry_hashtable + (hash & D_HASHMASK);
1128}
1129
1130/**
1131 * d_obtain_alias - find or allocate a dentry for a given inode
1132 * @inode: inode to allocate the dentry for
1133 *
1134 * Obtain a dentry for an inode resulting from NFS filehandle conversion or
1135 * similar open by handle operations.  The returned dentry may be anonymous,
1136 * or may have a full name (if the inode was already in the cache).
1137 *
1138 * When called on a directory inode, we must ensure that the inode only ever
1139 * has one dentry.  If a dentry is found, that is returned instead of
1140 * allocating a new one.
1141 *
1142 * On successful return, the reference to the inode has been transferred
1143 * to the dentry.  In case of an error the reference on the inode is released.
1144 * To make it easier to use in export operations a %NULL or IS_ERR inode may
1145 * be passed in and will be the error will be propagate to the return value,
1146 * with a %NULL @inode replaced by ERR_PTR(-ESTALE).
1147 */
1148struct dentry *d_obtain_alias(struct inode *inode)
1149{
1150        static const struct qstr anonstring = { .name = "" };
1151        struct dentry *tmp;
1152        struct dentry *res;
1153
1154        if (!inode)
1155                return ERR_PTR(-ESTALE);
1156        if (IS_ERR(inode))
1157                return ERR_CAST(inode);
1158
1159        res = d_find_alias(inode);
1160        if (res)
1161                goto out_iput;
1162
1163        tmp = d_alloc(NULL, &anonstring);
1164        if (!tmp) {
1165                res = ERR_PTR(-ENOMEM);
1166                goto out_iput;
1167        }
1168        tmp->d_parent = tmp; /* make sure dput doesn't croak */
1169
1170        spin_lock(&dcache_lock);
1171        res = __d_find_alias(inode, 0);
1172        if (res) {
1173                spin_unlock(&dcache_lock);
1174                dput(tmp);
1175                goto out_iput;
1176        }
1177
1178        /* attach a disconnected dentry */
1179        spin_lock(&tmp->d_lock);
1180        tmp->d_sb = inode->i_sb;
1181        tmp->d_inode = inode;
1182        tmp->d_flags |= DCACHE_DISCONNECTED;
1183        tmp->d_flags &= ~DCACHE_UNHASHED;
1184        list_add(&tmp->d_alias, &inode->i_dentry);
1185        hlist_add_head(&tmp->d_hash, &inode->i_sb->s_anon);
1186        spin_unlock(&tmp->d_lock);
1187
1188        spin_unlock(&dcache_lock);
1189        return tmp;
1190
1191 out_iput:
1192        iput(inode);
1193        return res;
1194}
1195EXPORT_SYMBOL(d_obtain_alias);
1196
1197/**
1198 * d_splice_alias - splice a disconnected dentry into the tree if one exists
1199 * @inode:  the inode which may have a disconnected dentry
1200 * @dentry: a negative dentry which we want to point to the inode.
1201 *
1202 * If inode is a directory and has a 'disconnected' dentry (i.e. IS_ROOT and
1203 * DCACHE_DISCONNECTED), then d_move that in place of the given dentry
1204 * and return it, else simply d_add the inode to the dentry and return NULL.
1205 *
1206 * This is needed in the lookup routine of any filesystem that is exportable
1207 * (via knfsd) so that we can build dcache paths to directories effectively.
1208 *
1209 * If a dentry was found and moved, then it is returned.  Otherwise NULL
1210 * is returned.  This matches the expected return value of ->lookup.
1211 *
1212 */
1213struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
1214{
1215        struct dentry *new = NULL;
1216
1217        if (inode && S_ISDIR(inode->i_mode)) {
1218                spin_lock(&dcache_lock);
1219                new = __d_find_alias(inode, 1);
1220                if (new) {
1221                        BUG_ON(!(new->d_flags & DCACHE_DISCONNECTED));
1222                        spin_unlock(&dcache_lock);
1223                        security_d_instantiate(new, inode);
1224                        d_move(new, dentry);
1225                        iput(inode);
1226                } else {
1227                        /* already taking dcache_lock, so d_add() by hand */
1228                        __d_instantiate(dentry, inode);
1229                        spin_unlock(&dcache_lock);
1230                        security_d_instantiate(dentry, inode);
1231                        d_rehash(dentry);
1232                }
1233        } else
1234                d_add(dentry, inode);
1235        return new;
1236}
1237EXPORT_SYMBOL(d_splice_alias);
1238
1239/**
1240 * d_add_ci - lookup or allocate new dentry with case-exact name
1241 * @inode:  the inode case-insensitive lookup has found
1242 * @dentry: the negative dentry that was passed to the parent's lookup func
1243 * @name:   the case-exact name to be associated with the returned dentry
1244 *
1245 * This is to avoid filling the dcache with case-insensitive names to the
1246 * same inode, only the actual correct case is stored in the dcache for
1247 * case-insensitive filesystems.
1248 *
1249 * For a case-insensitive lookup match and if the the case-exact dentry
1250 * already exists in in the dcache, use it and return it.
1251 *
1252 * If no entry exists with the exact case name, allocate new dentry with
1253 * the exact case, and return the spliced entry.
1254 */
1255struct dentry *d_add_ci(struct dentry *dentry, struct inode *inode,
1256                        struct qstr *name)
1257{
1258        int error;
1259        struct dentry *found;
1260        struct dentry *new;
1261
1262        /*
1263         * First check if a dentry matching the name already exists,
1264         * if not go ahead and create it now.
1265         */
1266        found = d_hash_and_lookup(dentry->d_parent, name);
1267        if (!found) {
1268                new = d_alloc(dentry->d_parent, name);
1269                if (!new) {
1270                        error = -ENOMEM;
1271                        goto err_out;
1272                }
1273
1274                found = d_splice_alias(inode, new);
1275                if (found) {
1276                        dput(new);
1277                        return found;
1278                }
1279                return new;
1280        }
1281
1282        /*
1283         * If a matching dentry exists, and it's not negative use it.
1284         *
1285         * Decrement the reference count to balance the iget() done
1286         * earlier on.
1287         */
1288        if (found->d_inode) {
1289                if (unlikely(found->d_inode != inode)) {
1290                        /* This can't happen because bad inodes are unhashed. */
1291                        BUG_ON(!is_bad_inode(inode));
1292                        BUG_ON(!is_bad_inode(found->d_inode));
1293                }
1294                iput(inode);
1295                return found;
1296        }
1297
1298        /*
1299         * Negative dentry: instantiate it unless the inode is a directory and
1300         * already has a dentry.
1301         */
1302        spin_lock(&dcache_lock);
1303        if (!S_ISDIR(inode->i_mode) || list_empty(&inode->i_dentry)) {
1304                __d_instantiate(found, inode);
1305                spin_unlock(&dcache_lock);
1306                security_d_instantiate(found, inode);
1307                return found;
1308        }
1309
1310        /*
1311         * In case a directory already has a (disconnected) entry grab a
1312         * reference to it, move it in place and use it.
1313         */
1314        new = list_entry(inode->i_dentry.next, struct dentry, d_alias);
1315        dget_locked(new);
1316        spin_unlock(&dcache_lock);
1317        security_d_instantiate(found, inode);
1318        d_move(new, found);
1319        iput(inode);
1320        dput(found);
1321        return new;
1322
1323err_out:
1324        iput(inode);
1325        return ERR_PTR(error);
1326}
1327EXPORT_SYMBOL(d_add_ci);
1328
1329/**
1330 * d_lookup - search for a dentry
1331 * @parent: parent dentry
1332 * @name: qstr of name we wish to find
1333 *
1334 * Searches the children of the parent dentry for the name in question. If
1335 * the dentry is found its reference count is incremented and the dentry
1336 * is returned. The caller must use dput to free the entry when it has
1337 * finished using it. %NULL is returned on failure.
1338 *
1339 * __d_lookup is dcache_lock free. The hash list is protected using RCU.
1340 * Memory barriers are used while updating and doing lockless traversal. 
1341 * To avoid races with d_move while rename is happening, d_lock is used.
1342 *
1343 * Overflows in memcmp(), while d_move, are avoided by keeping the length
1344 * and name pointer in one structure pointed by d_qstr.
1345 *
1346 * rcu_read_lock() and rcu_read_unlock() are used to disable preemption while
1347 * lookup is going on.
1348 *
1349 * The dentry unused LRU is not updated even if lookup finds the required dentry
1350 * in there. It is updated in places such as prune_dcache, shrink_dcache_sb,
1351 * select_parent and __dget_locked. This laziness saves lookup from dcache_lock
1352 * acquisition.
1353 *
1354 * d_lookup() is protected against the concurrent renames in some unrelated
1355 * directory using the seqlockt_t rename_lock.
1356 */
1357
1358struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
1359{
1360        struct dentry * dentry = NULL;
1361        unsigned long seq;
1362
1363        do {
1364                seq = read_seqbegin(&rename_lock);
1365                dentry = __d_lookup(parent, name);
1366                if (dentry)
1367                        break;
1368        } while (read_seqretry(&rename_lock, seq));
1369        return dentry;
1370}
1371EXPORT_SYMBOL(d_lookup);
1372
1373struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
1374{
1375        unsigned int len = name->len;
1376        unsigned int hash = name->hash;
1377        const unsigned char *str = name->name;
1378        struct hlist_head *head = d_hash(parent,hash);
1379        struct dentry *found = NULL;
1380        struct hlist_node *node;
1381        struct dentry *dentry;
1382
1383        rcu_read_lock();
1384        
1385        hlist_for_each_entry_rcu(dentry, node, head, d_hash) {
1386                struct qstr *qstr;
1387
1388                if (dentry->d_name.hash != hash)
1389                        continue;
1390                if (dentry->d_parent != parent)
1391                        continue;
1392
1393                spin_lock(&dentry->d_lock);
1394
1395                /*
1396                 * Recheck the dentry after taking the lock - d_move may have
1397                 * changed things.  Don't bother checking the hash because we're
1398                 * about to compare the whole name anyway.
1399                 */
1400                if (dentry->d_parent != parent)
1401                        goto next;
1402
1403                /* non-existing due to RCU? */
1404                if (d_unhashed(dentry))
1405                        goto next;
1406
1407                /*
1408                 * It is safe to compare names since d_move() cannot
1409                 * change the qstr (protected by d_lock).
1410                 */
1411                qstr = &dentry->d_name;
1412                if (parent->d_op && parent->d_op->d_compare) {
1413                        if (parent->d_op->d_compare(parent, qstr, name))
1414                                goto next;
1415                } else {
1416                        if (qstr->len != len)
1417                                goto next;
1418                        if (memcmp(qstr->name, str, len))
1419                                goto next;
1420                }
1421
1422                atomic_inc(&dentry->d_count);
1423                found = dentry;
1424                spin_unlock(&dentry->d_lock);
1425                break;
1426next:
1427                spin_unlock(&dentry->d_lock);
1428        }
1429        rcu_read_unlock();
1430
1431        return found;
1432}
1433
1434/**
1435 * d_hash_and_lookup - hash the qstr then search for a dentry
1436 * @dir: Directory to search in
1437 * @name: qstr of name we wish to find
1438 *
1439 * On hash failure or on lookup failure NULL is returned.
1440 */
1441struct dentry *d_hash_and_lookup(struct dentry *dir, struct qstr *name)
1442{
1443        struct dentry *dentry = NULL;
1444
1445        /*
1446         * Check for a fs-specific hash function. Note that we must
1447         * calculate the standard hash first, as the d_op->d_hash()
1448         * routine may choose to leave the hash value unchanged.
1449         */
1450        name->hash = full_name_hash(name->name, name->len);
1451        if (dir->d_op && dir->d_op->d_hash) {
1452                if (dir->d_op->d_hash(dir, name) < 0)
1453                        goto out;
1454        }
1455        dentry = d_lookup(dir, name);
1456out:
1457        return dentry;
1458}
1459
1460/**
1461 * d_validate - verify dentry provided from insecure source
1462 * @dentry: The dentry alleged to be valid child of @dparent
1463 * @dparent: The parent dentry (known to be valid)
1464 *
1465 * An insecure source has sent us a dentry, here we verify it and dget() it.
1466 * This is used by ncpfs in its readdir implementation.
1467 * Zero is returned in the dentry is invalid.
1468 */
1469 
1470int d_validate(struct dentry *dentry, struct dentry *dparent)
1471{
1472        struct hlist_head *base;
1473        struct hlist_node *lhp;
1474
1475        /* Check whether the ptr might be valid at all.. */
1476        if (!kmem_ptr_validate(dentry_cache, dentry))
1477                goto out;
1478
1479        if (dentry->d_parent != dparent)
1480                goto out;
1481
1482        spin_lock(&dcache_lock);
1483        base = d_hash(dparent, dentry->d_name.hash);
1484        hlist_for_each(lhp,base) { 
1485                /* hlist_for_each_entry_rcu() not required for d_hash list
1486                 * as it is parsed under dcache_lock
1487                 */
1488                if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
1489                        __dget_locked(dentry);
1490                        spin_unlock(&dcache_lock);
1491                        return 1;
1492                }
1493        }
1494        spin_unlock(&dcache_lock);
1495out:
1496        return 0;
1497}
1498EXPORT_SYMBOL(d_validate);
1499
1500/*
1501 * When a file is deleted, we have two options:
1502 * - turn this dentry into a negative dentry
1503 * - unhash this dentry and free it.
1504 *
1505 * Usually, we want to just turn this into
1506 * a negative dentry, but if anybody else is
1507 * currently using the dentry or the inode
1508 * we can't do that and we fall back on removing
1509 * it from the hash queues and waiting for
1510 * it to be deleted later when it has no users
1511 */
1512 
1513/**
1514 * d_delete - delete a dentry
1515 * @dentry: The dentry to delete
1516 *
1517 * Turn the dentry into a negative dentry if possible, otherwise
1518 * remove it from the hash queues so it can be deleted later
1519 */
1520 
1521void d_delete(struct dentry * dentry)
1522{
1523        int isdir = 0;
1524        /*
1525         * Are we the only user?
1526         */
1527        spin_lock(&dcache_lock);
1528        spin_lock(&dentry->d_lock);
1529        isdir = S_ISDIR(dentry->d_inode->i_mode);
1530        if (atomic_read(&dentry->d_count) == 1) {
1531                dentry->d_flags &= ~DCACHE_CANT_MOUNT;
1532                dentry_iput(dentry);
1533                fsnotify_nameremove(dentry, isdir);
1534                return;
1535        }
1536
1537        if (!d_unhashed(dentry))
1538                __d_drop(dentry);
1539
1540        spin_unlock(&dentry->d_lock);
1541        spin_unlock(&dcache_lock);
1542
1543        fsnotify_nameremove(dentry, isdir);
1544}
1545EXPORT_SYMBOL(d_delete);
1546
1547static void __d_rehash(struct dentry * entry, struct hlist_head *list)
1548{
1549
1550        entry->d_flags &= ~DCACHE_UNHASHED;
1551        hlist_add_head_rcu(&entry->d_hash, list);
1552}
1553
1554static void _d_rehash(struct dentry * entry)
1555{
1556        __d_rehash(entry, d_hash(entry->d_parent, entry->d_name.hash));
1557}
1558
1559/**
1560 * d_rehash     - add an entry back to the hash
1561 * @entry: dentry to add to the hash
1562 *
1563 * Adds a dentry to the hash according to its name.
1564 */
1565 
1566void d_rehash(struct dentry * entry)
1567{
1568        spin_lock(&dcache_lock);
1569        spin_lock(&entry->d_lock);
1570        _d_rehash(entry);
1571        spin_unlock(&entry->d_lock);
1572        spin_unlock(&dcache_lock);
1573}
1574EXPORT_SYMBOL(d_rehash);
1575
1576/*
1577 * When switching names, the actual string doesn't strictly have to
1578 * be preserved in the target - because we're dropping the target
1579 * anyway. As such, we can just do a simple memcpy() to copy over
1580 * the new name before we switch.
1581 *
1582 * Note that we have to be a lot more careful about getting the hash
1583 * switched - we have to switch the hash value properly even if it
1584 * then no longer matches the actual (corrupted) string of the target.
1585 * The hash value has to match the hash queue that the dentry is on..
1586 */
1587static void switch_names(struct dentry *dentry, struct dentry *target)
1588{
1589        if (dname_external(target)) {
1590                if (dname_external(dentry)) {
1591                        /*
1592                         * Both external: swap the pointers
1593                         */
1594                        swap(target->d_name.name, dentry->d_name.name);
1595                } else {
1596                        /*
1597                         * dentry:internal, target:external.  Steal target's
1598                         * storage and make target internal.
1599                         */
1600                        memcpy(target->d_iname, dentry->d_name.name,
1601                                        dentry->d_name.len + 1);
1602                        dentry->d_name.name = target->d_name.name;
1603                        target->d_name.name = target->d_iname;
1604                }
1605        } else {
1606                if (dname_external(dentry)) {
1607                        /*
1608                         * dentry:external, target:internal.  Give dentry's
1609                         * storage to target and make dentry internal
1610                         */
1611                        memcpy(dentry->d_iname, target->d_name.name,
1612                                        target->d_name.len + 1);
1613                        target->d_name.name = dentry->d_name.name;
1614                        dentry->d_name.name = dentry->d_iname;
1615                } else {
1616                        /*
1617                         * Both are internal.  Just copy target to dentry
1618                         */
1619                        memcpy(dentry->d_iname, target->d_name.name,
1620                                        target->d_name.len + 1);
1621                        dentry->d_name.len = target->d_name.len;
1622                        return;
1623                }
1624        }
1625        swap(dentry->d_name.len, target->d_name.len);
1626}
1627
1628/*
1629 * We cannibalize "target" when moving dentry on top of it,
1630 * because it's going to be thrown away anyway. We could be more
1631 * polite about it, though.
1632 *
1633 * This forceful removal will result in ugly /proc output if
1634 * somebody holds a file open that got deleted due to a rename.
1635 * We could be nicer about the deleted file, and let it show
1636 * up under the name it had before it was deleted rather than
1637 * under the original name of the file that was moved on top of it.
1638 */
1639 
1640/*
1641 * d_move_locked - move a dentry
1642 * @dentry: entry to move
1643 * @target: new dentry
1644 *
1645 * Update the dcache to reflect the move of a file name. Negative
1646 * dcache entries should not be moved in this way.
1647 */
1648static void d_move_locked(struct dentry * dentry, struct dentry * target)
1649{
1650        struct hlist_head *list;
1651
1652        if (!dentry->d_inode)
1653                printk(KERN_WARNING "VFS: moving negative dcache entry\n");
1654
1655        write_seqlock(&rename_lock);
1656        /*
1657         * XXXX: do we really need to take target->d_lock?
1658         */
1659        if (target < dentry) {
1660                spin_lock(&target->d_lock);
1661                spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
1662        } else {
1663                spin_lock(&dentry->d_lock);
1664                spin_lock_nested(&target->d_lock, DENTRY_D_LOCK_NESTED);
1665        }
1666
1667        /* Move the dentry to the target hash queue, if on different bucket */
1668        if (d_unhashed(dentry))
1669                goto already_unhashed;
1670
1671        hlist_del_rcu(&dentry->d_hash);
1672
1673already_unhashed:
1674        list = d_hash(target->d_parent, target->d_name.hash);
1675        __d_rehash(dentry, list);
1676
1677        /* Unhash the target: dput() will then get rid of it */
1678        __d_drop(target);
1679
1680        list_del(&dentry->d_u.d_child);
1681        list_del(&target->d_u.d_child);
1682
1683        /* Switch the names.. */
1684        switch_names(dentry, target);
1685        swap(dentry->d_name.hash, target->d_name.hash);
1686
1687        /* ... and switch the parents */
1688        if (IS_ROOT(dentry)) {
1689                dentry->d_parent = target->d_parent;
1690                target->d_parent = target;
1691                INIT_LIST_HEAD(&target->d_u.d_child);
1692        } else {
1693                swap(dentry->d_parent, target->d_parent);
1694
1695                /* And add them back to the (new) parent lists */
1696                list_add(&target->d_u.d_child, &target->d_parent->d_subdirs);
1697        }
1698
1699        list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
1700        spin_unlock(&target->d_lock);
1701        fsnotify_d_move(dentry);
1702        spin_unlock(&dentry->d_lock);
1703        write_sequnlock(&rename_lock);
1704}
1705
1706/**
1707 * d_move - move a dentry
1708 * @dentry: entry to move
1709 * @target: new dentry
1710 *
1711 * Update the dcache to reflect the move of a file name. Negative
1712 * dcache entries should not be moved in this way.
1713 */
1714
1715void d_move(struct dentry * dentry, struct dentry * target)
1716{
1717        spin_lock(&dcache_lock);
1718        d_move_locked(dentry, target);
1719        spin_unlock(&dcache_lock);
1720}
1721EXPORT_SYMBOL(d_move);
1722
1723/**
1724 * d_ancestor - search for an ancestor
1725 * @p1: ancestor dentry
1726 * @p2: child dentry
1727 *
1728 * Returns the ancestor dentry of p2 which is a child of p1, if p1 is
1729 * an ancestor of p2, else NULL.
1730 */
1731struct dentry *d_ancestor(struct dentry *p1, struct dentry *p2)
1732{
1733        struct dentry *p;
1734
1735        for (p = p2; !IS_ROOT(p); p = p->d_parent) {
1736                if (p->d_parent == p1)
1737                        return p;
1738        }
1739        return NULL;
1740}
1741
1742/*
1743 * This helper attempts to cope with remotely renamed directories
1744 *
1745 * It assumes that the caller is already holding
1746 * dentry->d_parent->d_inode->i_mutex and the dcache_lock
1747 *
1748 * Note: If ever the locking in lock_rename() changes, then please
1749 * remember to update this too...
1750 */
1751static struct dentry *__d_unalias(struct dentry *dentry, struct dentry *alias)
1752        __releases(dcache_lock)
1753{
1754        struct mutex *m1 = NULL, *m2 = NULL;
1755        struct dentry *ret;
1756
1757        /* If alias and dentry share a parent, then no extra locks required */
1758        if (alias->d_parent == dentry->d_parent)
1759                goto out_unalias;
1760
1761        /* Check for loops */
1762        ret = ERR_PTR(-ELOOP);
1763        if (d_ancestor(alias, dentry))
1764                goto out_err;
1765
1766        /* See lock_rename() */
1767        ret = ERR_PTR(-EBUSY);
1768        if (!mutex_trylock(&dentry->d_sb->s_vfs_rename_mutex))
1769                goto out_err;
1770        m1 = &dentry->d_sb->s_vfs_rename_mutex;
1771        if (!mutex_trylock(&alias->d_parent->d_inode->i_mutex))
1772                goto out_err;
1773        m2 = &alias->d_parent->d_inode->i_mutex;
1774out_unalias:
1775        d_move_locked(alias, dentry);
1776        ret = alias;
1777out_err:
1778        spin_unlock(&dcache_lock);
1779        if (m2)
1780                mutex_unlock(m2);
1781        if (m1)
1782                mutex_unlock(m1);
1783        return ret;
1784}
1785
1786/*
1787 * Prepare an anonymous dentry for life in the superblock's dentry tree as a
1788 * named dentry in place of the dentry to be replaced.
1789 */
1790static void __d_materialise_dentry(struct dentry *dentry, struct dentry *anon)
1791{
1792        struct dentry *dparent, *aparent;
1793
1794        switch_names(dentry, anon);
1795        swap(dentry->d_name.hash, anon->d_name.hash);
1796
1797        dparent = dentry->d_parent;
1798        aparent = anon->d_parent;
1799
1800        dentry->d_parent = (aparent == anon) ? dentry : aparent;
1801        list_del(&dentry->d_u.d_child);
1802        if (!IS_ROOT(dentry))
1803                list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
1804        else
1805                INIT_LIST_HEAD(&dentry->d_u.d_child);
1806
1807        anon->d_parent = (dparent == dentry) ? anon : dparent;
1808        list_del(&anon->d_u.d_child);
1809        if (!IS_ROOT(anon))
1810                list_add(&anon->d_u.d_child, &anon->d_parent->d_subdirs);
1811        else
1812                INIT_LIST_HEAD(&anon->d_u.d_child);
1813
1814        anon->d_flags &= ~DCACHE_DISCONNECTED;
1815}
1816
1817/**
1818 * d_materialise_unique - introduce an inode into the tree
1819 * @dentry: candidate dentry
1820 * @inode: inode to bind to the dentry, to which aliases may be attached
1821 *
1822 * Introduces an dentry into the tree, substituting an extant disconnected
1823 * root directory alias in its place if there is one
1824 */
1825struct dentry *d_materialise_unique(struct dentry *dentry, struct inode *inode)
1826{
1827        struct dentry *actual;
1828
1829        BUG_ON(!d_unhashed(dentry));
1830
1831        spin_lock(&dcache_lock);
1832
1833        if (!inode) {
1834                actual = dentry;
1835                __d_instantiate(dentry, NULL);
1836                goto found_lock;
1837        }
1838
1839        if (S_ISDIR(inode->i_mode)) {
1840                struct dentry *alias;
1841
1842                /* Does an aliased dentry already exist? */
1843                alias = __d_find_alias(inode, 0);
1844                if (alias) {
1845                        actual = alias;
1846                        /* Is this an anonymous mountpoint that we could splice
1847                         * into our tree? */
1848                        if (IS_ROOT(alias)) {
1849                                spin_lock(&alias->d_lock);
1850                                __d_materialise_dentry(dentry, alias);
1851                                __d_drop(alias);
1852                                goto found;
1853                        }
1854                        /* Nope, but we must(!) avoid directory aliasing */
1855                        actual = __d_unalias(dentry, alias);
1856                        if (IS_ERR(actual))
1857                                dput(alias);
1858                        goto out_nolock;
1859                }
1860        }
1861
1862        /* Add a unique reference */
1863        actual = __d_instantiate_unique(dentry, inode);
1864        if (!actual)
1865                actual = dentry;
1866        else if (unlikely(!d_unhashed(actual)))
1867                goto shouldnt_be_hashed;
1868
1869found_lock:
1870        spin_lock(&actual->d_lock);
1871found:
1872        _d_rehash(actual);
1873        spin_unlock(&actual->d_lock);
1874        spin_unlock(&dcache_lock);
1875out_nolock:
1876        if (actual == dentry) {
1877                security_d_instantiate(dentry, inode);
1878                return NULL;
1879        }
1880
1881        iput(inode);
1882        return actual;
1883
1884shouldnt_be_hashed:
1885        spin_unlock(&dcache_lock);
1886        BUG();
1887}
1888EXPORT_SYMBOL_GPL(d_materialise_unique);
1889
1890static int prepend(char **buffer, int *buflen, const char *str, int namelen)
1891{
1892        *buflen -= namelen;
1893        if (*buflen < 0)
1894                return -ENAMETOOLONG;
1895        *buffer -= namelen;
1896        memcpy(*buffer, str, namelen);
1897        return 0;
1898}
1899
1900static int prepend_name(char **buffer, int *buflen, struct qstr *name)
1901{
1902        return prepend(buffer, buflen, name->name, name->len);
1903}
1904
1905/**
1906 * __d_path - return the path of a dentry
1907 * @path: the dentry/vfsmount to report
1908 * @root: root vfsmnt/dentry (may be modified by this function)
1909 * @buffer: buffer to return value in
1910 * @buflen: buffer length
1911 *
1912 * Convert a dentry into an ASCII path name. If the entry has been deleted
1913 * the string " (deleted)" is appended. Note that this is ambiguous.
1914 *
1915 * Returns a pointer into the buffer or an error code if the
1916 * path was too long.
1917 *
1918 * "buflen" should be positive. Caller holds the dcache_lock.
1919 *
1920 * If path is not reachable from the supplied root, then the value of
1921 * root is changed (without modifying refcounts).
1922 */
1923char *__d_path(const struct path *path, struct path *root,
1924               char *buffer, int buflen)
1925{
1926        struct dentry *dentry = path->dentry;
1927        struct vfsmount *vfsmnt = path->mnt;
1928        char *end = buffer + buflen;
1929        char *retval;
1930
1931        spin_lock(&vfsmount_lock);
1932        prepend(&end, &buflen, "\0", 1);
1933        if (d_unlinked(dentry) &&
1934                (prepend(&end, &buflen, " (deleted)", 10) != 0))
1935                        goto Elong;
1936
1937        if (buflen < 1)
1938                goto Elong;
1939        /* Get '/' right */
1940        retval = end-1;
1941        *retval = '/';
1942
1943        for (;;) {
1944                struct dentry * parent;
1945
1946                if (dentry == root->dentry && vfsmnt == root->mnt)
1947                        break;
1948                if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
1949                        /* Global root? */
1950                        if (vfsmnt->mnt_parent == vfsmnt) {
1951                                goto global_root;
1952                        }
1953                        dentry = vfsmnt->mnt_mountpoint;
1954                        vfsmnt = vfsmnt->mnt_parent;
1955                        continue;
1956                }
1957                parent = dentry->d_parent;
1958                prefetch(parent);
1959                if ((prepend_name(&end, &buflen, &dentry->d_name) != 0) ||
1960                    (prepend(&end, &buflen, "/", 1) != 0))
1961                        goto Elong;
1962                retval = end;
1963                dentry = parent;
1964        }
1965
1966out:
1967        spin_unlock(&vfsmount_lock);
1968        return retval;
1969
1970global_root:
1971        retval += 1;    /* hit the slash */
1972        if (prepend_name(&retval, &buflen, &dentry->d_name) != 0)
1973                goto Elong;
1974        root->mnt = vfsmnt;
1975        root->dentry = dentry;
1976        goto out;
1977
1978Elong:
1979        retval = ERR_PTR(-ENAMETOOLONG);
1980        goto out;
1981}
1982
1983/**
1984 * d_path - return the path of a dentry
1985 * @path: path to report
1986 * @buf: buffer to return value in
1987 * @buflen: buffer length
1988 *
1989 * Convert a dentry into an ASCII path name. If the entry has been deleted
1990 * the string " (deleted)" is appended. Note that this is ambiguous.
1991 *
1992 * Returns a pointer into the buffer or an error code if the path was
1993 * too long. Note: Callers should use the returned pointer, not the passed
1994 * in buffer, to use the name! The implementation often starts at an offset
1995 * into the buffer, and may leave 0 bytes at the start.
1996 *
1997 * "buflen" should be positive.
1998 */
1999char *d_path(const struct path *path, char *buf, int buflen)
2000{
2001        char *res;
2002        struct path root;
2003        struct path tmp;
2004
2005        /*
2006         * We have various synthetic filesystems that never get mounted.  On
2007         * these filesystems dentries are never used for lookup purposes, and
2008         * thus don't need to be hashed.  They also don't need a name until a
2009         * user wants to identify the object in /proc/pid/fd/.  The little hack
2010         * below allows us to generate a name for these objects on demand:
2011         */
2012        if (path->dentry->d_op && path->dentry->d_op->d_dname)
2013                return path->dentry->d_op->d_dname(path->dentry, buf, buflen);
2014
2015        read_lock(&current->fs->lock);
2016        root = current->fs->root;
2017        path_get(&root);
2018        read_unlock(&current->fs->lock);
2019        spin_lock(&dcache_lock);
2020        tmp = root;
2021        res = __d_path(path, &tmp, buf, buflen);
2022        spin_unlock(&dcache_lock);
2023        path_put(&root);
2024        return res;
2025}
2026EXPORT_SYMBOL(d_path);
2027
2028/*
2029 * Helper function for dentry_operations.d_dname() members
2030 */
2031char *dynamic_dname(struct dentry *dentry, char *buffer, int buflen,
2032                        const char *fmt, ...)
2033{
2034        va_list args;
2035        char temp[64];
2036        int sz;
2037
2038        va_start(args, fmt);
2039        sz = vsnprintf(temp, sizeof(temp), fmt, args) + 1;
2040        va_end(args);
2041
2042        if (sz > sizeof(temp) || sz > buflen)
2043                return ERR_PTR(-ENAMETOOLONG);
2044
2045        buffer += buflen - sz;
2046        return memcpy(buffer, temp, sz);
2047}
2048
2049/*
2050 * Write full pathname from the root of the filesystem into the buffer.
2051 */
2052char *dentry_path(struct dentry *dentry, char *buf, int buflen)
2053{
2054        char *end = buf + buflen;
2055        char *retval;
2056
2057        spin_lock(&dcache_lock);
2058        prepend(&end, &buflen, "\0", 1);
2059        if (d_unlinked(dentry) &&
2060                (prepend(&end, &buflen, "//deleted", 9) != 0))
2061                        goto Elong;
2062        if (buflen < 1)
2063                goto Elong;
2064        /* Get '/' right */
2065        retval = end-1;
2066        *retval = '/';
2067
2068        while (!IS_ROOT(dentry)) {
2069                struct dentry *parent = dentry->d_parent;
2070
2071                prefetch(parent);
2072                if ((prepend_name(&end, &buflen, &dentry->d_name) != 0) ||
2073                    (prepend(&end, &buflen, "/", 1) != 0))
2074                        goto Elong;
2075
2076                retval = end;
2077                dentry = parent;
2078        }
2079        spin_unlock(&dcache_lock);
2080        return retval;
2081Elong:
2082        spin_unlock(&dcache_lock);
2083        return ERR_PTR(-ENAMETOOLONG);
2084}
2085
2086/*
2087 * NOTE! The user-level library version returns a
2088 * character pointer. The kernel system call just
2089 * returns the length of the buffer filled (which
2090 * includes the ending '\0' character), or a negative
2091 * error value. So libc would do something like
2092 *
2093 *      char *getcwd(char * buf, size_t size)
2094 *      {
2095 *              int retval;
2096 *
2097 *              retval = sys_getcwd(buf, size);
2098 *              if (retval >= 0)
2099 *                      return buf;
2100 *              errno = -retval;
2101 *              return NULL;
2102 *      }
2103 */
2104SYSCALL_DEFINE2(getcwd, char __user *, buf, unsigned long, size)
2105{
2106        int error;
2107        struct path pwd, root;
2108        char *page = (char *) __get_free_page(GFP_USER);
2109
2110        if (!page)
2111                return -ENOMEM;
2112
2113        read_lock(&current->fs->lock);
2114        pwd = current->fs->pwd;
2115        path_get(&pwd);
2116        root = current->fs->root;
2117        path_get(&root);
2118        read_unlock(&current->fs->lock);
2119
2120        error = -ENOENT;
2121        spin_lock(&dcache_lock);
2122        if (!d_unlinked(pwd.dentry)) {
2123                unsigned long len;
2124                struct path tmp = root;
2125                char * cwd;
2126
2127                cwd = __d_path(&pwd, &tmp, page, PAGE_SIZE);
2128                spin_unlock(&dcache_lock);
2129
2130                error = PTR_ERR(cwd);
2131                if (IS_ERR(cwd))
2132                        goto out;
2133
2134                error = -ERANGE;
2135                len = PAGE_SIZE + page - cwd;
2136                if (len <= size) {
2137                        error = len;
2138                        if (copy_to_user(buf, cwd, len))
2139                                error = -EFAULT;
2140                }
2141        } else
2142                spin_unlock(&dcache_lock);
2143
2144out:
2145        path_put(&pwd);
2146        path_put(&root);
2147        free_page((unsigned long) page);
2148        return error;
2149}
2150
2151/*
2152 * Test whether new_dentry is a subdirectory of old_dentry.
2153 *
2154 * Trivially implemented using the dcache structure
2155 */
2156
2157/**
2158 * is_subdir - is new dentry a subdirectory of old_dentry
2159 * @new_dentry: new dentry
2160 * @old_dentry: old dentry
2161 *
2162 * Returns 1 if new_dentry is a subdirectory of the parent (at any depth).
2163 * Returns 0 otherwise.
2164 * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
2165 */
2166  
2167int is_subdir(struct dentry *new_dentry, struct dentry *old_dentry)
2168{
2169        int result;
2170        unsigned long seq;
2171
2172        if (new_dentry == old_dentry)
2173                return 1;
2174
2175        /*
2176         * Need rcu_readlock to protect against the d_parent trashing
2177         * due to d_move
2178         */
2179        rcu_read_lock();
2180        do {
2181                /* for restarting inner loop in case of seq retry */
2182                seq = read_seqbegin(&rename_lock);
2183                if (d_ancestor(old_dentry, new_dentry))
2184                        result = 1;
2185                else
2186                        result = 0;
2187        } while (read_seqretry(&rename_lock, seq));
2188        rcu_read_unlock();
2189
2190        return result;
2191}
2192
2193int path_is_under(struct path *path1, struct path *path2)
2194{
2195        struct vfsmount *mnt = path1->mnt;
2196        struct dentry *dentry = path1->dentry;
2197        int res;
2198        spin_lock(&vfsmount_lock);
2199        if (mnt != path2->mnt) {
2200                for (;;) {
2201                        if (mnt->mnt_parent == mnt) {
2202                                spin_unlock(&vfsmount_lock);
2203                                return 0;
2204                        }
2205                        if (mnt->mnt_parent == path2->mnt)
2206                                break;
2207                        mnt = mnt->mnt_parent;
2208                }
2209                dentry = mnt->mnt_mountpoint;
2210        }
2211        res = is_subdir(dentry, path2->dentry);
2212        spin_unlock(&vfsmount_lock);
2213        return res;
2214}
2215EXPORT_SYMBOL(path_is_under);
2216
2217void d_genocide(struct dentry *root)
2218{
2219        struct dentry *this_parent = root;
2220        struct list_head *next;
2221
2222        spin_lock(&dcache_lock);
2223repeat:
2224        next = this_parent->d_subdirs.next;
2225resume:
2226        while (next != &this_parent->d_subdirs) {
2227                struct list_head *tmp = next;
2228                struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
2229                next = tmp->next;
2230                if (d_unhashed(dentry)||!dentry->d_inode)
2231                        continue;
2232                if (!list_empty(&dentry->d_subdirs)) {
2233                        this_parent = dentry;
2234                        goto repeat;
2235                }
2236                atomic_dec(&dentry->d_count);
2237        }
2238        if (this_parent != root) {
2239                next = this_parent->d_u.d_child.next;
2240                atomic_dec(&this_parent->d_count);
2241                this_parent = this_parent->d_parent;
2242                goto resume;
2243        }
2244        spin_unlock(&dcache_lock);
2245}
2246
2247/**
2248 * find_inode_number - check for dentry with name
2249 * @dir: directory to check
2250 * @name: Name to find.
2251 *
2252 * Check whether a dentry already exists for the given name,
2253 * and return the inode number if it has an inode. Otherwise
2254 * 0 is returned.
2255 *
2256 * This routine is used to post-process directory listings for
2257 * filesystems using synthetic inode numbers, and is necessary
2258 * to keep getcwd() working.
2259 */
2260 
2261ino_t find_inode_number(struct dentry *dir, struct qstr *name)
2262{
2263        struct dentry * dentry;
2264        ino_t ino = 0;
2265
2266        dentry = d_hash_and_lookup(dir, name);
2267        if (dentry) {
2268                if (dentry->d_inode)
2269                        ino = dentry->d_inode->i_ino;
2270                dput(dentry);
2271        }
2272        return ino;
2273}
2274EXPORT_SYMBOL(find_inode_number);
2275
2276static __initdata unsigned long dhash_entries;
2277static int __init set_dhash_entries(char *str)
2278{
2279        if (!str)
2280                return 0;
2281        dhash_entries = simple_strtoul(str, &str, 0);
2282        return 1;
2283}
2284__setup("dhash_entries=", set_dhash_entries);
2285
2286static void __init dcache_init_early(void)
2287{
2288        int loop;
2289
2290        /* If hashes are distributed across NUMA nodes, defer
2291         * hash allocation until vmalloc space is available.
2292         */
2293        if (hashdist)
2294                return;
2295
2296        dentry_hashtable =
2297                alloc_large_system_hash("Dentry cache",
2298                                        sizeof(struct hlist_head),
2299                                        dhash_entries,
2300                                        13,
2301                                        HASH_EARLY,
2302                                        &d_hash_shift,
2303                                        &d_hash_mask,
2304                                        0);
2305
2306        for (loop = 0; loop < (1 << d_hash_shift); loop++)
2307                INIT_HLIST_HEAD(&dentry_hashtable[loop]);
2308}
2309
2310static void __init dcache_init(void)
2311{
2312        int loop;
2313
2314        /* 
2315         * A constructor could be added for stable state like the lists,
2316         * but it is probably not worth it because of the cache nature
2317         * of the dcache. 
2318         */
2319        dentry_cache = KMEM_CACHE(dentry,
2320                SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD);
2321        
2322        register_shrinker(&dcache_shrinker);
2323
2324        /* Hash may have been set up in dcache_init_early */
2325        if (!hashdist)
2326                return;
2327
2328        dentry_hashtable =
2329                alloc_large_system_hash("Dentry cache",
2330                                        sizeof(struct hlist_head),
2331                                        dhash_entries,
2332                                        13,
2333                                        0,
2334                                        &d_hash_shift,
2335                                        &d_hash_mask,
2336                                        0);
2337
2338        for (loop = 0; loop < (1 << d_hash_shift); loop++)
2339                INIT_HLIST_HEAD(&dentry_hashtable[loop]);
2340}
2341
2342/* SLAB cache for __getname() consumers */
2343struct kmem_cache *names_cachep __read_mostly;
2344EXPORT_SYMBOL(names_cachep);
2345
2346EXPORT_SYMBOL(d_genocide);
2347
2348void __init vfs_caches_init_early(void)
2349{
2350        dcache_init_early();
2351        inode_init_early();
2352}
2353
2354void __init vfs_caches_init(unsigned long mempages)
2355{
2356        unsigned long reserve;
2357
2358        /* Base hash sizes on available memory, with a reserve equal to
2359           150% of current kernel size */
2360
2361        reserve = min((mempages - nr_free_pages()) * 3/2, mempages - 1);
2362        mempages -= reserve;
2363
2364        names_cachep = kmem_cache_create("names_cache", PATH_MAX, 0,
2365                        SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
2366
2367        dcache_init();
2368        inode_init();
2369        files_init(mempages);
2370        mnt_init();
2371        bdev_cache_init();
2372        chrdev_init();
2373}
2374
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.