fs/dcache.c

   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/config.h>
  18 #include <linux/string.h>
  19 #include <linux/mm.h>
  20 #include <linux/fs.h>
  21 #include <linux/slab.h>
  22 #include <linux/init.h>
  23 #include <linux/smp_lock.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
  35 /* #define DCACHE_DEBUG 1 */
  36
  37 int sysctl_vfs_cache_pressure = 100;
  38
  39 spinlock_t dcache_lock __cacheline_aligned_in_smp = SPIN_LOCK_UNLOCKED;
  40 seqlock_t rename_lock __cacheline_aligned_in_smp = SEQLOCK_UNLOCKED;
  41
  42 EXPORT_SYMBOL(dcache_lock);
  43
  44 static kmem_cache_t *dentry_cache;
  45
  46 #define DNAME_INLINE_LEN (sizeof(struct dentry)-offsetof(struct dentry,d_iname))
  47
  48 /*
  49  * This is the single most critical data structure when it comes
  50  * to the dcache: the hashtable for lookups. Somebody should try
  51  * to make this good - I've just made it work.
  52  *
  53  * This hash-function tries to avoid losing too many bits of hash
  54  * information, yet avoid using a prime hash-size or similar.
  55  */
  56 #define D_HASHBITS     d_hash_shift
  57 #define D_HASHMASK     d_hash_mask
  58
  59 static unsigned int d_hash_mask;
  60 static unsigned int d_hash_shift;
  61 static struct hlist_head *dentry_hashtable;
  62 static LIST_HEAD(dentry_unused);
  63
  64 /* Statistics gathering. */
  65 struct dentry_stat_t dentry_stat = {
  66         .age_limit = 45,
  67 };
  68
  69 static void d_callback(struct rcu_head *head)
  70 {
  71         struct dentry * dentry = container_of(head, struct dentry, d_rcu);
  72
  73         if (dname_external(dentry))
  74                 kfree(dentry->d_name.name);
  75         kmem_cache_free(dentry_cache, dentry);
  76 }
  77
  78 /*
  79  * no dcache_lock, please.  The caller must decrement dentry_stat.nr_dentry
  80  * inside dcache_lock.
  81  */
  82 static void d_free(struct dentry *dentry)
  83 {
  84         if (dentry->d_op && dentry->d_op->d_release)
  85                 dentry->d_op->d_release(dentry);
  86         call_rcu(&dentry->d_rcu, d_callback);
  87 }
  88
  89 /*
  90  * Release the dentry's inode, using the filesystem
  91  * d_iput() operation if defined.
  92  * Called with dcache_lock and per dentry lock held, drops both.
  93  */
  94 static inline void dentry_iput(struct dentry * dentry)
  95 {
  96         struct inode *inode = dentry->d_inode;
  97         if (inode) {
  98                 dentry->d_inode = NULL;
  99                 list_del_init(&dentry->d_alias);
 100                 spin_unlock(&dentry->d_lock);
 101                 spin_unlock(&dcache_lock);
 102                 if (dentry->d_op && dentry->d_op->d_iput)
 103                         dentry->d_op->d_iput(dentry, inode);
 104                 else
 105                         iput(inode);
 106         } else {
 107                 spin_unlock(&dentry->d_lock);
 108                 spin_unlock(&dcache_lock);
 109         }
 110 }
 111
 112 /*
 113  * This is dput
 114  *
 115  * This is complicated by the fact that we do not want to put
 116  * dentries that are no longer on any hash chain on the unused
 117  * list: we'd much rather just get rid of them immediately.
 118  *
 119  * However, that implies that we have to traverse the dentry
 120  * tree upwards to the parents which might _also_ now be
 121  * scheduled for deletion (it may have been only waiting for
 122  * its last child to go away).
 123  *
 124  * This tail recursion is done by hand as we don't want to depend
 125  * on the compiler to always get this right (gcc generally doesn't).
 126  * Real recursion would eat up our stack space.
 127  */
 128
 129 /*
 130  * dput - release a dentry
 131  * @dentry: dentry to release
 132  *
 133  * Release a dentry. This will drop the usage count and if appropriate
 134  * call the dentry unlink method as well as removing it from the queues and
 135  * releasing its resources. If the parent dentries were scheduled for release
 136  * they too may now get deleted.
 137  *
 138  * no dcache lock, please.
 139  */
 140
 141 void dput(struct dentry *dentry)
 142 {
 143         if (!dentry)
 144                 return;
 145
 146 repeat:
 147         if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
 148                 return;
 149
 150         spin_lock(&dentry->d_lock);
 151         if (atomic_read(&dentry->d_count)) {
 152                 spin_unlock(&dentry->d_lock);
 153                 spin_unlock(&dcache_lock);
 154                 return;
 155         }
 156
 157         /*
 158          * AV: ->d_delete() is _NOT_ allowed to block now.
 159          */
 160         if (dentry->d_op && dentry->d_op->d_delete) {
 161                 if (dentry->d_op->d_delete(dentry))
 162                         goto unhash_it;
 163         }
 164         /* Unreachable? Get rid of it */
 165         if (d_unhashed(dentry))
 166                 goto kill_it;
 167         if (list_empty(&dentry->d_lru)) {
 168                 dentry->d_flags |= DCACHE_REFERENCED;
 169                 list_add(&dentry->d_lru, &dentry_unused);
 170                 dentry_stat.nr_unused++;
 171         }
 172         spin_unlock(&dentry->d_lock);
 173         spin_unlock(&dcache_lock);
 174         return;
 175
 176 unhash_it:
 177         __d_drop(dentry);
 178
 179 kill_it: {
 180                 struct dentry *parent;
 181
 182                 /* If dentry was on d_lru list
 183                  * delete it from there
 184                  */
 185                 if (!list_empty(&dentry->d_lru)) {
 186                         list_del(&dentry->d_lru);
 187                         dentry_stat.nr_unused--;
 188                 }
 189                 list_del(&dentry->d_child);
 190                 dentry_stat.nr_dentry--;        /* For d_free, below */
 191                 /*drops the locks, at that point nobody can reach this dentry */
 192                 dentry_iput(dentry);
 193                 parent = dentry->d_parent;
 194                 d_free(dentry);
 195                 if (dentry == parent)
 196                         return;
 197                 dentry = parent;
 198                 goto repeat;
 199         }
 200 }
 201
 202 /**
 203  * d_invalidate - invalidate a dentry
 204  * @dentry: dentry to invalidate
 205  *
 206  * Try to invalidate the dentry if it turns out to be
 207  * possible. If there are other dentries that can be
 208  * reached through this one we can't delete it and we
 209  * return -EBUSY. On success we return 0.
 210  *
 211  * no dcache lock.
 212  */
 213
 214 int d_invalidate(struct dentry * dentry)
 215 {
 216         /*
 217          * If it's already been dropped, return OK.
 218          */
 219         spin_lock(&dcache_lock);
 220         if (d_unhashed(dentry)) {
 221                 spin_unlock(&dcache_lock);
 222                 return 0;
 223         }
 224         /*
 225          * Check whether to do a partial shrink_dcache
 226          * to get rid of unused child entries.
 227          */
 228         if (!list_empty(&dentry->d_subdirs)) {
 229                 spin_unlock(&dcache_lock);
 230                 shrink_dcache_parent(dentry);
 231                 spin_lock(&dcache_lock);
 232         }
 233
 234         /*
 235          * Somebody else still using it?
 236          *
 237          * If it's a directory, we can't drop it
 238          * for fear of somebody re-populating it
 239          * with children (even though dropping it
 240          * would make it unreachable from the root,
 241          * we might still populate it if it was a
 242          * working directory or similar).
 243          */
 244         spin_lock(&dentry->d_lock);
 245         if (atomic_read(&dentry->d_count) > 1) {
 246                 if (dentry->d_inode && S_ISDIR(dentry->d_inode->i_mode)) {
 247                         spin_unlock(&dentry->d_lock);
 248                         spin_unlock(&dcache_lock);
 249                         return -EBUSY;
 250                 }
 251         }
 252
 253         __d_drop(dentry);
 254         spin_unlock(&dentry->d_lock);
 255         spin_unlock(&dcache_lock);
 256         return 0;
 257 }
 258
 259 /* This should be called _only_ with dcache_lock held */
 260
 261 static inline struct dentry * __dget_locked(struct dentry *dentry)
 262 {
 263         atomic_inc(&dentry->d_count);
 264         if (!list_empty(&dentry->d_lru)) {
 265                 dentry_stat.nr_unused--;
 266                 list_del_init(&dentry->d_lru);
 267         }
 268         return dentry;
 269 }
 270
 271 struct dentry * dget_locked(struct dentry *dentry)
 272 {
 273         return __dget_locked(dentry);
 274 }
 275
 276 /**
 277  * d_find_alias - grab a hashed alias of inode
 278  * @inode: inode in question
 279  *
 280  * If inode has a hashed alias - acquire the reference to alias and
 281  * return it. Otherwise return NULL. Notice that if inode is a directory
 282  * there can be only one alias and it can be unhashed only if it has
 283  * no children.
 284  *
 285  * If the inode has a DCACHE_DISCONNECTED alias, then prefer
 286  * any other hashed alias over that one.
 287  */
 288
 289 struct dentry * d_find_alias(struct inode *inode)
 290 {
 291         struct list_head *head, *next, *tmp;
 292         struct dentry *alias, *discon_alias=NULL;
 293
 294         spin_lock(&dcache_lock);
 295         head = &inode->i_dentry;
 296         next = inode->i_dentry.next;
 297         while (next != head) {
 298                 tmp = next;
 299                 next = tmp->next;
 300                 prefetch(next);
 301                 alias = list_entry(tmp, struct dentry, d_alias);
 302                 if (!d_unhashed(alias)) {
 303                         if (alias->d_flags & DCACHE_DISCONNECTED)
 304                                 discon_alias = alias;
 305                         else {
 306                                 __dget_locked(alias);
 307                                 spin_unlock(&dcache_lock);
 308                                 return alias;
 309                         }
 310                 }
 311         }
 312         if (discon_alias)
 313                 __dget_locked(discon_alias);
 314         spin_unlock(&dcache_lock);
 315         return discon_alias;
 316 }
 317
 318 /*
 319  *      Try to kill dentries associated with this inode.
 320  * WARNING: you must own a reference to inode.
 321  */
 322 void d_prune_aliases(struct inode *inode)
 323 {
 324         struct list_head *tmp, *head = &inode->i_dentry;
 325 restart:
 326         spin_lock(&dcache_lock);
 327         tmp = head;
 328         while ((tmp = tmp->next) != head) {
 329                 struct dentry *dentry = list_entry(tmp, struct dentry, d_alias);
 330                 if (!atomic_read(&dentry->d_count)) {
 331                         __dget_locked(dentry);
 332                         __d_drop(dentry);
 333                         spin_unlock(&dcache_lock);
 334                         dput(dentry);
 335                         goto restart;
 336                 }
 337         }
 338         spin_unlock(&dcache_lock);
 339 }
 340
 341 /*
 342  * Throw away a dentry - free the inode, dput the parent.
 343  * This requires that the LRU list has already been
 344  * removed.
 345  * Called with dcache_lock, drops it and then regains.
 346  */
 347 static inline void prune_one_dentry(struct dentry * dentry)
 348 {
 349         struct dentry * parent;
 350
 351         __d_drop(dentry);
 352         list_del(&dentry->d_child);
 353         dentry_stat.nr_dentry--;        /* For d_free, below */
 354         dentry_iput(dentry);
 355         parent = dentry->d_parent;
 356         d_free(dentry);
 357         if (parent != dentry)
 358                 dput(parent);
 359         spin_lock(&dcache_lock);
 360 }
 361
 362 /**
 363  * prune_dcache - shrink the dcache
 364  * @count: number of entries to try and free
 365  *
 366  * Shrink the dcache. This is done when we need
 367  * more memory, or simply when we need to unmount
 368  * something (at which point we need to unuse
 369  * all dentries).
 370  *
 371  * This function may fail to free any resources if
 372  * all the dentries are in use.
 373  */
 374
 375 static void prune_dcache(int count)
 376 {
 377         spin_lock(&dcache_lock);
 378         for (; count ; count--) {
 379                 struct dentry *dentry;
 380                 struct list_head *tmp;
 381
 382                 tmp = dentry_unused.prev;
 383                 if (tmp == &dentry_unused)
 384                         break;
 385                 list_del_init(tmp);
 386                 prefetch(dentry_unused.prev);
 387                 dentry_stat.nr_unused--;
 388                 dentry = list_entry(tmp, struct dentry, d_lru);
 389
 390                 spin_lock(&dentry->d_lock);
 391                 /*
 392                  * We found an inuse dentry which was not removed from
 393                  * dentry_unused because of laziness during lookup.  Do not free
 394                  * it - just keep it off the dentry_unused list.
 395                  */
 396                 if (atomic_read(&dentry->d_count)) {
 397                         spin_unlock(&dentry->d_lock);
 398                         continue;
 399                 }
 400                 /* If the dentry was recently referenced, don't free it. */
 401                 if (dentry->d_flags & DCACHE_REFERENCED) {
 402                         dentry->d_flags &= ~DCACHE_REFERENCED;
 403                         list_add(&dentry->d_lru, &dentry_unused);
 404                         dentry_stat.nr_unused++;
 405                         spin_unlock(&dentry->d_lock);
 406                         continue;
 407                 }
 408                 prune_one_dentry(dentry);
 409         }
 410         spin_unlock(&dcache_lock);
 411 }
 412
 413 /*
 414  * Shrink the dcache for the specified super block.
 415  * This allows us to unmount a device without disturbing
 416  * the dcache for the other devices.
 417  *
 418  * This implementation makes just two traversals of the
 419  * unused list.  On the first pass we move the selected
 420  * dentries to the most recent end, and on the second
 421  * pass we free them.  The second pass must restart after
 422  * each dput(), but since the target dentries are all at
 423  * the end, it's really just a single traversal.
 424  */
 425
 426 /**
 427  * shrink_dcache_sb - shrink dcache for a superblock
 428  * @sb: superblock
 429  *
 430  * Shrink the dcache for the specified super block. This
 431  * is used to free the dcache before unmounting a file
 432  * system
 433  */
 434
 435 void shrink_dcache_sb(struct super_block * sb)
 436 {
 437         struct list_head *tmp, *next;
 438         struct dentry *dentry;
 439
 440         /*
 441          * Pass one ... move the dentries for the specified
 442          * superblock to the most recent end of the unused list.
 443          */
 444         spin_lock(&dcache_lock);
 445         next = dentry_unused.next;
 446         while (next != &dentry_unused) {
 447                 tmp = next;
 448                 next = tmp->next;
 449                 dentry = list_entry(tmp, struct dentry, d_lru);
 450                 if (dentry->d_sb != sb)
 451                         continue;
 452                 list_del(tmp);
 453                 list_add(tmp, &dentry_unused);
 454         }
 455
 456         /*
 457          * Pass two ... free the dentries for this superblock.
 458          */
 459 repeat:
 460         next = dentry_unused.next;
 461         while (next != &dentry_unused) {
 462                 tmp = next;
 463                 next = tmp->next;
 464                 dentry = list_entry(tmp, struct dentry, d_lru);
 465                 if (dentry->d_sb != sb)
 466                         continue;
 467                 dentry_stat.nr_unused--;
 468                 list_del_init(tmp);
 469                 spin_lock(&dentry->d_lock);
 470                 if (atomic_read(&dentry->d_count)) {
 471                         spin_unlock(&dentry->d_lock);
 472                         continue;
 473                 }
 474                 prune_one_dentry(dentry);
 475                 goto repeat;
 476         }
 477         spin_unlock(&dcache_lock);
 478 }
 479
 480 /*
 481  * Search for at least 1 mount point in the dentry's subdirs.
 482  * We descend to the next level whenever the d_subdirs
 483  * list is non-empty and continue searching.
 484  */
 485
 486 /**
 487  * have_submounts - check for mounts over a dentry
 488  * @parent: dentry to check.
 489  *
 490  * Return true if the parent or its subdirectories contain
 491  * a mount point
 492  */
 493
 494 int have_submounts(struct dentry *parent)
 495 {
 496         struct dentry *this_parent = parent;
 497         struct list_head *next;
 498
 499         spin_lock(&dcache_lock);
 500         if (d_mountpoint(parent))
 501                 goto positive;
 502 repeat:
 503         next = this_parent->d_subdirs.next;
 504 resume:
 505         while (next != &this_parent->d_subdirs) {
 506                 struct list_head *tmp = next;
 507                 struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
 508                 next = tmp->next;
 509                 /* Have we found a mount point ? */
 510                 if (d_mountpoint(dentry))
 511                         goto positive;
 512                 if (!list_empty(&dentry->d_subdirs)) {
 513                         this_parent = dentry;
 514                         goto repeat;
 515                 }
 516         }
 517         /*
 518          * All done at this level ... ascend and resume the search.
 519          */
 520         if (this_parent != parent) {
 521                 next = this_parent->d_child.next;
 522                 this_parent = this_parent->d_parent;
 523                 goto resume;
 524         }
 525         spin_unlock(&dcache_lock);
 526         return 0; /* No mount points found in tree */
 527 positive:
 528         spin_unlock(&dcache_lock);
 529         return 1;
 530 }
 531
 532 /*
 533  * Search the dentry child list for the specified parent,
 534  * and move any unused dentries to the end of the unused
 535  * list for prune_dcache(). We descend to the next level
 536  * whenever the d_subdirs list is non-empty and continue
 537  * searching.
 538  */
 539 static int select_parent(struct dentry * parent)
 540 {
 541         struct dentry *this_parent = parent;
 542         struct list_head *next;
 543         int found = 0;
 544
 545         spin_lock(&dcache_lock);
 546 repeat:
 547         next = this_parent->d_subdirs.next;
 548 resume:
 549         while (next != &this_parent->d_subdirs) {
 550                 struct list_head *tmp = next;
 551                 struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
 552                 next = tmp->next;
 553
 554                 if (!list_empty(&dentry->d_lru)) {
 555                         dentry_stat.nr_unused--;
 556                         list_del_init(&dentry->d_lru);
 557                 }
 558                 /*
 559                  * move only zero ref count dentries to the end
 560                  * of the unused list for prune_dcache
 561                  */
 562                 if (!atomic_read(&dentry->d_count)) {
 563                         list_add(&dentry->d_lru, dentry_unused.prev);
 564                         dentry_stat.nr_unused++;
 565                         found++;
 566                 }
 567                 /*
 568                  * Descend a level if the d_subdirs list is non-empty.
 569                  */
 570                 if (!list_empty(&dentry->d_subdirs)) {
 571                         this_parent = dentry;
 572 #ifdef DCACHE_DEBUG
 573 printk(KERN_DEBUG "select_parent: descending to %s/%s, found=%d\n",
 574 dentry->d_parent->d_name.name, dentry->d_name.name, found);
 575 #endif
 576                         goto repeat;
 577                 }
 578         }
 579         /*
 580          * All done at this level ... ascend and resume the search.
 581          */
 582         if (this_parent != parent) {
 583                 next = this_parent->d_child.next;
 584                 this_parent = this_parent->d_parent;
 585 #ifdef DCACHE_DEBUG
 586 printk(KERN_DEBUG "select_parent: ascending to %s/%s, found=%d\n",
 587 this_parent->d_parent->d_name.name, this_parent->d_name.name, found);
 588 #endif
 589                 goto resume;
 590         }
 591         spin_unlock(&dcache_lock);
 592         return found;
 593 }
 594
 595 /**
 596  * shrink_dcache_parent - prune dcache
 597  * @parent: parent of entries to prune
 598  *
 599  * Prune the dcache to remove unused children of the parent dentry.
 600  */
 601
 602 void shrink_dcache_parent(struct dentry * parent)
 603 {
 604         int found;
 605
 606         while ((found = select_parent(parent)) != 0)
 607                 prune_dcache(found);
 608 }
 609
 610 /**
 611  * shrink_dcache_anon - further prune the cache
 612  * @head: head of d_hash list of dentries to prune
 613  *
 614  * Prune the dentries that are anonymous
 615  *
 616  * parsing d_hash list does not read_barrier_depends() as it
 617  * done under dcache_lock.
 618  *
 619  */
 620 void shrink_dcache_anon(struct hlist_head *head)
 621 {
 622         struct hlist_node *lp;
 623         int found;
 624         do {
 625                 found = 0;
 626                 spin_lock(&dcache_lock);
 627                 hlist_for_each(lp, head) {
 628                         struct dentry *this = hlist_entry(lp, struct dentry, d_hash);
 629                         if (!list_empty(&this->d_lru)) {
 630                                 dentry_stat.nr_unused--;
 631                                 list_del_init(&this->d_lru);
 632                         }
 633
 634                         /*
 635                          * move only zero ref count dentries to the end
 636                          * of the unused list for prune_dcache
 637                          */
 638                         if (!atomic_read(&this->d_count)) {
 639                                 list_add_tail(&this->d_lru, &dentry_unused);
 640                                 dentry_stat.nr_unused++;
 641                                 found++;
 642                         }
 643                 }
 644                 spin_unlock(&dcache_lock);
 645                 prune_dcache(found);
 646         } while(found);
 647 }
 648
 649 /*
 650  * Scan `nr' dentries and return the number which remain.
 651  *
 652  * We need to avoid reentering the filesystem if the caller is performing a
 653  * GFP_NOFS allocation attempt.  One example deadlock is:
 654  *
 655  * ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
 656  * prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->put_inode->
 657  * ext2_discard_prealloc->ext2_free_blocks->lock_super->DEADLOCK.
 658  *
 659  * In this case we return -1 to tell the caller that we baled.
 660  */
 661 static int shrink_dcache_memory(int nr, unsigned int gfp_mask)
 662 {
 663         if (nr) {
 664                 if (!(gfp_mask & __GFP_FS))
 665                         return -1;
 666                 prune_dcache(nr);
 667         }
 668         return (dentry_stat.nr_unused / 100) * sysctl_vfs_cache_pressure;
 669 }
 670
 671 /**
 672  * d_alloc      -       allocate a dcache entry
 673  * @parent: parent of entry to allocate
 674  * @name: qstr of the name
 675  *
 676  * Allocates a dentry. It returns %NULL if there is insufficient memory
 677  * available. On a success the dentry is returned. The name passed in is
 678  * copied and the copy passed in may be reused after this call.
 679  */
 680
 681 struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
 682 {
 683         struct dentry *dentry;
 684         char *dname;
 685
 686         dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
 687         if (!dentry)
 688                 return NULL;
 689
 690         if (name->len > DNAME_INLINE_LEN-1) {
 691                 dname = kmalloc(name->len + 1, GFP_KERNEL);
 692                 if (!dname) {
 693                         kmem_cache_free(dentry_cache, dentry);
 694                         return NULL;
 695                 }
 696         } else  {
 697                 dname = dentry->d_iname;
 698         }
 699         dentry->d_name.name = dname;
 700
 701         dentry->d_name.len = name->len;
 702         dentry->d_name.hash = name->hash;
 703         memcpy(dname, name->name, name->len);
 704         dname[name->len] = 0;
 705
 706         atomic_set(&dentry->d_count, 1);
 707         dentry->d_flags = DCACHE_UNHASHED;
 708         dentry->d_lock = SPIN_LOCK_UNLOCKED;
 709         dentry->d_inode = NULL;
 710         dentry->d_parent = NULL;
 711         dentry->d_sb = NULL;
 712         dentry->d_op = NULL;
 713         dentry->d_fsdata = NULL;
 714         dentry->d_mounted = 0;
 715         dentry->d_cookie = NULL;
 716         dentry->d_bucket = NULL;
 717         INIT_HLIST_NODE(&dentry->d_hash);
 718         INIT_LIST_HEAD(&dentry->d_lru);
 719         INIT_LIST_HEAD(&dentry->d_subdirs);
 720         INIT_LIST_HEAD(&dentry->d_alias);
 721
 722         if (parent) {
 723                 dentry->d_parent = dget(parent);
 724                 dentry->d_sb = parent->d_sb;
 725         } else {
 726                 INIT_LIST_HEAD(&dentry->d_child);
 727         }
 728
 729         spin_lock(&dcache_lock);
 730         if (parent)
 731                 list_add(&dentry->d_child, &parent->d_subdirs);
 732         dentry_stat.nr_dentry++;
 733         spin_unlock(&dcache_lock);
 734
 735         return dentry;
 736 }
 737
 738 /**
 739  * d_instantiate - fill in inode information for a dentry
 740  * @entry: dentry to complete
 741  * @inode: inode to attach to this dentry
 742  *
 743  * Fill in inode information in the entry.
 744  *
 745  * This turns negative dentries into productive full members
 746  * of society.
 747  *
 748  * NOTE! This assumes that the inode count has been incremented
 749  * (or otherwise set) by the caller to indicate that it is now
 750  * in use by the dcache.
 751  */
 752
 753 void d_instantiate(struct dentry *entry, struct inode * inode)
 754 {
 755         if (!list_empty(&entry->d_alias)) BUG();
 756         spin_lock(&dcache_lock);
 757         if (inode)
 758                 list_add(&entry->d_alias, &inode->i_dentry);
 759         entry->d_inode = inode;
 760         spin_unlock(&dcache_lock);
 761         security_d_instantiate(entry, inode);
 762 }
 763
 764 /**
 765  * d_alloc_root - allocate root dentry
 766  * @root_inode: inode to allocate the root for
 767  *
 768  * Allocate a root ("/") dentry for the inode given. The inode is
 769  * instantiated and returned. %NULL is returned if there is insufficient
 770  * memory or the inode passed is %NULL.
 771  */
 772
 773 struct dentry * d_alloc_root(struct inode * root_inode)
 774 {
 775         struct dentry *res = NULL;
 776
 777         if (root_inode) {
 778                 static const struct qstr name = { .name = "/", .len = 1 };
 779
 780                 res = d_alloc(NULL, &name);
 781                 if (res) {
 782                         res->d_sb = root_inode->i_sb;
 783                         res->d_parent = res;
 784                         d_instantiate(res, root_inode);
 785                 }
 786         }
 787         return res;
 788 }
 789
 790 static inline struct hlist_head *d_hash(struct dentry *parent,
 791                                         unsigned long hash)
 792 {
 793         hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
 794         hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
 795         return dentry_hashtable + (hash & D_HASHMASK);
 796 }
 797
 798 /**
 799  * d_alloc_anon - allocate an anonymous dentry
 800  * @inode: inode to allocate the dentry for
 801  *
 802  * This is similar to d_alloc_root.  It is used by filesystems when
 803  * creating a dentry for a given inode, often in the process of
 804  * mapping a filehandle to a dentry.  The returned dentry may be
 805  * anonymous, or may have a full name (if the inode was already
 806  * in the cache).  The file system may need to make further
 807  * efforts to connect this dentry into the dcache properly.
 808  *
 809  * When called on a directory inode, we must ensure that
 810  * the inode only ever has one dentry.  If a dentry is
 811  * found, that is returned instead of allocating a new one.
 812  *
 813  * On successful return, the reference to the inode has been transferred
 814  * to the dentry.  If %NULL is returned (indicating kmalloc failure),
 815  * the reference on the inode has not been released.
 816  */
 817
 818 struct dentry * d_alloc_anon(struct inode *inode)
 819 {
 820         static const struct qstr anonstring = { .name = "" };
 821         struct dentry *tmp;
 822         struct dentry *res;
 823
 824         if ((res = d_find_alias(inode))) {
 825                 iput(inode);
 826                 return res;
 827         }
 828
 829         tmp = d_alloc(NULL, &anonstring);
 830         if (!tmp)
 831                 return NULL;
 832
 833         tmp->d_parent = tmp; /* make sure dput doesn't croak */
 834
 835         spin_lock(&dcache_lock);
 836         if (S_ISDIR(inode->i_mode) && !list_empty(&inode->i_dentry)) {
 837                 /* A directory can only have one dentry.
 838                  * This (now) has one, so use it.
 839                  */
 840                 res = list_entry(inode->i_dentry.next, struct dentry, d_alias);
 841                 __dget_locked(res);
 842         } else {
 843                 /* attach a disconnected dentry */
 844                 res = tmp;
 845                 tmp = NULL;
 846                 if (res) {
 847                         spin_lock(&res->d_lock);
 848                         res->d_sb = inode->i_sb;
 849                         res->d_parent = res;
 850                         res->d_inode = inode;
 851
 852                         /*
 853                          * Set d_bucket to an "impossible" bucket address so
 854                          * that d_move() doesn't get a false positive
 855                          */
 856                         res->d_bucket = NULL;
 857                         res->d_flags |= DCACHE_DISCONNECTED;
 858                         res->d_flags &= ~DCACHE_UNHASHED;
 859                         list_add(&res->d_alias, &inode->i_dentry);
 860                         hlist_add_head(&res->d_hash, &inode->i_sb->s_anon);
 861                         spin_unlock(&res->d_lock);
 862                 }
 863                 inode = NULL; /* don't drop reference */
 864         }
 865         spin_unlock(&dcache_lock);
 866
 867         if (inode)
 868                 iput(inode);
 869         if (tmp)
 870                 dput(tmp);
 871         return res;
 872 }
 873
 874
 875 /**
 876  * d_splice_alias - splice a disconnected dentry into the tree if one exists
 877  * @inode:  the inode which may have a disconnected dentry
 878  * @dentry: a negative dentry which we want to point to the inode.
 879  *
 880  * If inode is a directory and has a 'disconnected' dentry (i.e. IS_ROOT and
 881  * DCACHE_DISCONNECTED), then d_move that in place of the given dentry
 882  * and return it, else simply d_add the inode to the dentry and return NULL.
 883  *
 884  * This is (will be) needed in the lookup routine of any filesystem that is exportable
 885  * (via knfsd) so that we can build dcache paths to directories effectively.
 886  *
 887  * If a dentry was found and moved, then it is returned.  Otherwise NULL
 888  * is returned.  This matches the expected return value of ->lookup.
 889  *
 890  */
 891 struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
 892 {
 893         struct dentry *new = NULL;
 894
 895         if (inode && S_ISDIR(inode->i_mode)) {
 896                 spin_lock(&dcache_lock);
 897                 if (!list_empty(&inode->i_dentry)) {
 898                         new = list_entry(inode->i_dentry.next, struct dentry, d_alias);
 899                         __dget_locked(new);
 900                         spin_unlock(&dcache_lock);
 901                         security_d_instantiate(new, inode);
 902                         d_rehash(dentry);
 903                         d_move(new, dentry);
 904                         iput(inode);
 905                 } else {
 906                         /* d_instantiate takes dcache_lock, so we do it by hand */
 907                         list_add(&dentry->d_alias, &inode->i_dentry);
 908                         dentry->d_inode = inode;
 909                         spin_unlock(&dcache_lock);
 910                         security_d_instantiate(dentry, inode);
 911                         d_rehash(dentry);
 912                 }
 913         } else
 914                 d_add(dentry, inode);
 915         return new;
 916 }
 917
 918
 919 /**
 920  * d_lookup - search for a dentry
 921  * @parent: parent dentry
 922  * @name: qstr of name we wish to find
 923  *
 924  * Searches the children of the parent dentry for the name in question. If
 925  * the dentry is found its reference count is incremented and the dentry
 926  * is returned. The caller must use d_put to free the entry when it has
 927  * finished using it. %NULL is returned on failure.
 928  *
 929  * __d_lookup is dcache_lock free. The hash list is protected using RCU.
 930  * Memory barriers are used while updating and doing lockless traversal.
 931  * To avoid races with d_move while rename is happening, d_lock is used.
 932  *
 933  * Overflows in memcmp(), while d_move, are avoided by keeping the length
 934  * and name pointer in one structure pointed by d_qstr.
 935  *
 936  * rcu_read_lock() and rcu_read_unlock() are used to disable preemption while
 937  * lookup is going on.
 938  *
 939  * dentry_unused list is not updated even if lookup finds the required dentry
 940  * in there. It is updated in places such as prune_dcache, shrink_dcache_sb,
 941  * select_parent and __dget_locked. This laziness saves lookup from dcache_lock
 942  * acquisition.
 943  *
 944  * d_lookup() is protected against the concurrent renames in some unrelated
 945  * directory using the seqlockt_t rename_lock.
 946  */
 947
 948 struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
 949 {
 950         struct dentry * dentry = NULL;
 951         unsigned long seq;
 952
 953         do {
 954                 seq = read_seqbegin(&rename_lock);
 955                 dentry = __d_lookup(parent, name);
 956                 if (dentry)
 957                         break;
 958         } while (read_seqretry(&rename_lock, seq));
 959         return dentry;
 960 }
 961
 962 struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
 963 {
 964         unsigned int len = name->len;
 965         unsigned int hash = name->hash;
 966         const unsigned char *str = name->name;
 967         struct hlist_head *head = d_hash(parent,hash);
 968         struct dentry *found = NULL;
 969         struct hlist_node *node;
 970
 971         rcu_read_lock();
 972
 973         hlist_for_each (node, head) {
 974                 struct dentry *dentry;
 975                 struct qstr *qstr;
 976
 977                 smp_read_barrier_depends();
 978                 dentry = hlist_entry(node, struct dentry, d_hash);
 979
 980                 smp_rmb();
 981
 982                 if (dentry->d_name.hash != hash)
 983                         continue;
 984                 if (dentry->d_parent != parent)
 985                         continue;
 986
 987                 spin_lock(&dentry->d_lock);
 988
 989                 /*
 990                  * If lookup ends up in a different bucket due to concurrent
 991                  * rename, fail it
 992                  */
 993                 if (unlikely(dentry->d_bucket != head))
 994                         goto terminate;
 995
 996                 /*
 997                  * Recheck the dentry after taking the lock - d_move may have
 998                  * changed things.  Don't bother checking the hash because we're
 999                  * about to compare the whole name anyway.
1000                  */
1001                 if (dentry->d_parent != parent)
1002                         goto next;
1003
1004                 qstr = &dentry->d_name;
1005                 smp_read_barrier_depends();
1006                 if (parent->d_op && parent->d_op->d_compare) {
1007                         if (parent->d_op->d_compare(parent, qstr, name))
1008                                 goto next;
1009                 } else {
1010                         if (qstr->len != len)
1011                                 goto next;
1012                         if (memcmp(qstr->name, str, len))
1013                                 goto next;
1014                 }
1015
1016                 if (!d_unhashed(dentry)) {
1017                         atomic_inc(&dentry->d_count);
1018                         found = dentry;
1019                 }
1020 terminate:
1021                 spin_unlock(&dentry->d_lock);
1022                 break;
1023 next:
1024                 spin_unlock(&dentry->d_lock);
1025         }
1026         rcu_read_unlock();
1027
1028         return found;
1029 }
1030
1031 /**
1032  * d_validate - verify dentry provided from insecure source
1033  * @dentry: The dentry alleged to be valid child of @dparent
1034  * @dparent: The parent dentry (known to be valid)
1035  * @hash: Hash of the dentry
1036  * @len: Length of the name
1037  *
1038  * An insecure source has sent us a dentry, here we verify it and dget() it.
1039  * This is used by ncpfs in its readdir implementation.
1040  * Zero is returned in the dentry is invalid.
1041  */
1042
1043 int d_validate(struct dentry *dentry, struct dentry *dparent)
1044 {
1045         struct hlist_head *base;
1046         struct hlist_node *lhp;
1047
1048         /* Check whether the ptr might be valid at all.. */
1049         if (!kmem_ptr_validate(dentry_cache, dentry))
1050                 goto out;
1051
1052         if (dentry->d_parent != dparent)
1053                 goto out;
1054
1055         spin_lock(&dcache_lock);
1056         base = d_hash(dparent, dentry->d_name.hash);
1057         hlist_for_each(lhp,base) {
1058                 /* read_barrier_depends() not required for d_hash list
1059                  * as it is parsed under dcache_lock
1060                  */
1061                 if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
1062                         __dget_locked(dentry);
1063                         spin_unlock(&dcache_lock);
1064                         return 1;
1065                 }
1066         }
1067         spin_unlock(&dcache_lock);
1068 out:
1069         return 0;
1070 }
1071
1072 /*
1073  * When a file is deleted, we have two options:
1074  * - turn this dentry into a negative dentry
1075  * - unhash this dentry and free it.
1076  *
1077  * Usually, we want to just turn this into
1078  * a negative dentry, but if anybody else is
1079  * currently using the dentry or the inode
1080  * we can't do that and we fall back on removing
1081  * it from the hash queues and waiting for
1082  * it to be deleted later when it has no users
1083  */
1084
1085 /**
1086  * d_delete - delete a dentry
1087  * @dentry: The dentry to delete
1088  *
1089  * Turn the dentry into a negative dentry if possible, otherwise
1090  * remove it from the hash queues so it can be deleted later
1091  */
1092
1093 void d_delete(struct dentry * dentry)
1094 {
1095         /*
1096          * Are we the only user?
1097          */
1098         spin_lock(&dcache_lock);
1099         spin_lock(&dentry->d_lock);
1100         if (atomic_read(&dentry->d_count) == 1) {
1101                 dentry_iput(dentry);
1102                 return;
1103         }
1104
1105         if (!d_unhashed(dentry))
1106                 __d_drop(dentry);
1107
1108         spin_unlock(&dentry->d_lock);
1109         spin_unlock(&dcache_lock);
1110 }
1111
1112 /**
1113  * d_rehash     - add an entry back to the hash
1114  * @entry: dentry to add to the hash
1115  *
1116  * Adds a dentry to the hash according to its name.
1117  */
1118
1119 void d_rehash(struct dentry * entry)
1120 {
1121         struct hlist_head *list = d_hash(entry->d_parent, entry->d_name.hash);
1122
1123         spin_lock(&dcache_lock);
1124         spin_lock(&entry->d_lock);
1125         entry->d_flags &= ~DCACHE_UNHASHED;
1126         spin_unlock(&entry->d_lock);
1127         entry->d_bucket = list;
1128         hlist_add_head_rcu(&entry->d_hash, list);
1129         spin_unlock(&dcache_lock);
1130 }
1131
1132 #define do_switch(x,y) do { \
1133         __typeof__ (x) __tmp = x; \
1134         x = y; y = __tmp; } while (0)
1135
1136 /*
1137  * When switching names, the actual string doesn't strictly have to
1138  * be preserved in the target - because we're dropping the target
1139  * anyway. As such, we can just do a simple memcpy() to copy over
1140  * the new name before we switch.
1141  *
1142  * Note that we have to be a lot more careful about getting the hash
1143  * switched - we have to switch the hash value properly even if it
1144  * then no longer matches the actual (corrupted) string of the target.
1145  * The hash value has to match the hash queue that the dentry is on..
1146  */
1147 static void switch_names(struct dentry *dentry, struct dentry *target)
1148 {
1149         if (dname_external(target)) {
1150                 if (dname_external(dentry)) {
1151                         /*
1152                          * Both external: swap the pointers
1153                          */
1154                         do_switch(target->d_name.name, dentry->d_name.name);
1155                 } else {
1156                         /*
1157                          * dentry:internal, target:external.  Steal target's
1158                          * storage and make target internal.
1159                          */
1160                         dentry->d_name.name = target->d_name.name;
1161                         target->d_name.name = target->d_iname;
1162                 }
1163         } else {
1164                 if (dname_external(dentry)) {
1165                         /*
1166                          * dentry:external, target:internal.  Give dentry's
1167                          * storage to target and make dentry internal
1168                          */
1169                         memcpy(dentry->d_iname, target->d_name.name,
1170                                         target->d_name.len + 1);
1171                         target->d_name.name = dentry->d_name.name;
1172                         dentry->d_name.name = dentry->d_iname;
1173                 } else {
1174                         /*
1175                          * Both are internal.  Just copy target to dentry
1176                          */
1177                         memcpy(dentry->d_iname, target->d_name.name,
1178                                         target->d_name.len + 1);
1179                 }
1180         }
1181 }
1182
1183 /*
1184  * We cannibalize "target" when moving dentry on top of it,
1185  * because it's going to be thrown away anyway. We could be more
1186  * polite about it, though.
1187  *
1188  * This forceful removal will result in ugly /proc output if
1189  * somebody holds a file open that got deleted due to a rename.
1190  * We could be nicer about the deleted file, and let it show
1191  * up under the name it got deleted rather than the name that
1192  * deleted it.
1193  */
1194
1195 /**
1196  * d_move - move a dentry
1197  * @dentry: entry to move
1198  * @target: new dentry
1199  *
1200  * Update the dcache to reflect the move of a file name. Negative
1201  * dcache entries should not be moved in this way.
1202  */
1203
1204 void d_move(struct dentry * dentry, struct dentry * target)
1205 {
1206         if (!dentry->d_inode)
1207                 printk(KERN_WARNING "VFS: moving negative dcache entry\n");
1208
1209         spin_lock(&dcache_lock);
1210         write_seqlock(&rename_lock);
1211         /*
1212          * XXXX: do we really need to take target->d_lock?
1213          */
1214         if (target < dentry) {
1215                 spin_lock(&target->d_lock);
1216                 spin_lock(&dentry->d_lock);
1217         } else {
1218                 spin_lock(&dentry->d_lock);
1219                 spin_lock(&target->d_lock);
1220         }
1221
1222         /* Move the dentry to the target hash queue, if on different bucket */
1223         if (dentry->d_flags & DCACHE_UNHASHED)
1224                 goto already_unhashed;
1225         if (dentry->d_bucket != target->d_bucket) {
1226                 hlist_del_rcu(&dentry->d_hash);
1227 already_unhashed:
1228                 dentry->d_bucket = target->d_bucket;
1229                 hlist_add_head_rcu(&dentry->d_hash, target->d_bucket);
1230                 dentry->d_flags &= ~DCACHE_UNHASHED;
1231         }
1232
1233         /* Unhash the target: dput() will then get rid of it */
1234         __d_drop(target);
1235
1236         list_del(&dentry->d_child);
1237         list_del(&target->d_child);
1238
1239         /* Switch the names.. */
1240         switch_names(dentry, target);
1241         smp_wmb();
1242         do_switch(dentry->d_name.len, target->d_name.len);
1243         do_switch(dentry->d_name.hash, target->d_name.hash);
1244
1245         /* ... and switch the parents */
1246         if (IS_ROOT(dentry)) {
1247                 dentry->d_parent = target->d_parent;
1248                 target->d_parent = target;
1249                 INIT_LIST_HEAD(&target->d_child);
1250         } else {
1251                 do_switch(dentry->d_parent, target->d_parent);
1252
1253                 /* And add them back to the (new) parent lists */
1254                 list_add(&target->d_child, &target->d_parent->d_subdirs);
1255         }
1256
1257         list_add(&dentry->d_child, &dentry->d_parent->d_subdirs);
1258         spin_unlock(&target->d_lock);
1259         spin_unlock(&dentry->d_lock);
1260         write_sequnlock(&rename_lock);
1261         spin_unlock(&dcache_lock);
1262 }
1263
1264 /**
1265  * d_path - return the path of a dentry
1266  * @dentry: dentry to report
1267  * @vfsmnt: vfsmnt to which the dentry belongs
1268  * @root: root dentry
1269  * @rootmnt: vfsmnt to which the root dentry belongs
1270  * @buffer: buffer to return value in
1271  * @buflen: buffer length
1272  *
1273  * Convert a dentry into an ASCII path name. If the entry has been deleted
1274  * the string " (deleted)" is appended. Note that this is ambiguous.
1275  *
1276  * Returns the buffer or an error code if the path was too long.
1277  *
1278  * "buflen" should be positive. Caller holds the dcache_lock.
1279  */
1280 static char * __d_path( struct dentry *dentry, struct vfsmount *vfsmnt,
1281                         struct dentry *root, struct vfsmount *rootmnt,
1282                         char *buffer, int buflen)
1283 {
1284         char * end = buffer+buflen;
1285         char * retval;
1286         int namelen;
1287
1288         *--end = '\0';
1289         buflen--;
1290         if (!IS_ROOT(dentry) && d_unhashed(dentry)) {
1291                 buflen -= 10;
1292                 end -= 10;
1293                 if (buflen < 0)
1294                         goto Elong;
1295                 memcpy(end, " (deleted)", 10);
1296         }
1297
1298         if (buflen < 1)
1299                 goto Elong;
1300         /* Get '/' right */
1301         retval = end-1;
1302         *retval = '/';
1303
1304         for (;;) {
1305                 struct dentry * parent;
1306
1307                 if (dentry == root && vfsmnt == rootmnt)
1308                         break;
1309                 if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
1310                         /* Global root? */
1311                         spin_lock(&vfsmount_lock);
1312                         if (vfsmnt->mnt_parent == vfsmnt) {
1313                                 spin_unlock(&vfsmount_lock);
1314                                 goto global_root;
1315                         }
1316                         dentry = vfsmnt->mnt_mountpoint;
1317                         vfsmnt = vfsmnt->mnt_parent;
1318                         spin_unlock(&vfsmount_lock);
1319                         continue;
1320                 }
1321                 parent = dentry->d_parent;
1322                 prefetch(parent);
1323                 namelen = dentry->d_name.len;
1324                 buflen -= namelen + 1;
1325                 if (buflen < 0)
1326                         goto Elong;
1327                 end -= namelen;
1328                 memcpy(end, dentry->d_name.name, namelen);
1329                 *--end = '/';
1330                 retval = end;
1331                 dentry = parent;
1332         }
1333
1334         return retval;
1335
1336 global_root:
1337         namelen = dentry->d_name.len;
1338         buflen -= namelen;
1339         if (buflen < 0)
1340                 goto Elong;
1341         retval -= namelen-1;    /* hit the slash */
1342         memcpy(retval, dentry->d_name.name, namelen);
1343         return retval;
1344 Elong:
1345         return ERR_PTR(-ENAMETOOLONG);
1346 }
1347
1348 /* write full pathname into buffer and return start of pathname */
1349 char * d_path(struct dentry *dentry, struct vfsmount *vfsmnt,
1350                                 char *buf, int buflen)
1351 {
1352         char *res;
1353         struct vfsmount *rootmnt;
1354         struct dentry *root;
1355
1356         read_lock(&current->fs->lock);
1357         rootmnt = mntget(current->fs->rootmnt);
1358         root = dget(current->fs->root);
1359         read_unlock(&current->fs->lock);
1360         spin_lock(&dcache_lock);
1361         res = __d_path(dentry, vfsmnt, root, rootmnt, buf, buflen);
1362         spin_unlock(&dcache_lock);
1363         dput(root);
1364         mntput(rootmnt);
1365         return res;
1366 }
1367
1368 /*
1369  * NOTE! The user-level library version returns a
1370  * character pointer. The kernel system call just
1371  * returns the length of the buffer filled (which
1372  * includes the ending '\0' character), or a negative
1373  * error value. So libc would do something like
1374  *
1375  *      char *getcwd(char * buf, size_t size)
1376  *      {
1377  *              int retval;
1378  *
1379  *              retval = sys_getcwd(buf, size);
1380  *              if (retval >= 0)
1381  *                      return buf;
1382  *              errno = -retval;
1383  *              return NULL;
1384  *      }
1385  */
1386 asmlinkage long sys_getcwd(char __user *buf, unsigned long size)
1387 {
1388         int error;
1389         struct vfsmount *pwdmnt, *rootmnt;
1390         struct dentry *pwd, *root;
1391         char *page = (char *) __get_free_page(GFP_USER);
1392
1393         if (!page)
1394                 return -ENOMEM;
1395
1396         read_lock(&current->fs->lock);
1397         pwdmnt = mntget(current->fs->pwdmnt);
1398         pwd = dget(current->fs->pwd);
1399         rootmnt = mntget(current->fs->rootmnt);
1400         root = dget(current->fs->root);
1401         read_unlock(&current->fs->lock);
1402
1403         error = -ENOENT;
1404         /* Has the current directory has been unlinked? */
1405         spin_lock(&dcache_lock);
1406         if (pwd->d_parent == pwd || !d_unhashed(pwd)) {
1407                 unsigned long len;
1408                 char * cwd;
1409
1410                 cwd = __d_path(pwd, pwdmnt, root, rootmnt, page, PAGE_SIZE);
1411                 spin_unlock(&dcache_lock);
1412
1413                 error = PTR_ERR(cwd);
1414                 if (IS_ERR(cwd))
1415                         goto out;
1416
1417                 error = -ERANGE;
1418                 len = PAGE_SIZE + page - cwd;
1419                 if (len <= size) {
1420                         error = len;
1421                         if (copy_to_user(buf, cwd, len))
1422                                 error = -EFAULT;
1423                 }
1424         } else
1425                 spin_unlock(&dcache_lock);
1426
1427 out:
1428         dput(pwd);
1429         mntput(pwdmnt);
1430         dput(root);
1431         mntput(rootmnt);
1432         free_page((unsigned long) page);
1433         return error;
1434 }
1435
1436 /*
1437  * Test whether new_dentry is a subdirectory of old_dentry.
1438  *
1439  * Trivially implemented using the dcache structure
1440  */
1441
1442 /**
1443  * is_subdir - is new dentry a subdirectory of old_dentry
1444  * @new_dentry: new dentry
1445  * @old_dentry: old dentry
1446  *
1447  * Returns 1 if new_dentry is a subdirectory of the parent (at any depth).
1448  * Returns 0 otherwise.
1449  * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
1450  */
1451
1452 int is_subdir(struct dentry * new_dentry, struct dentry * old_dentry)
1453 {
1454         int result;
1455         struct dentry * saved = new_dentry;
1456         unsigned long seq;
1457
1458         result = 0;
1459         /* need rcu_readlock to protect against the d_parent trashing due to
1460          * d_move
1461          */
1462         rcu_read_lock();
1463         do {
1464                 /* for restarting inner loop in case of seq retry */
1465                 new_dentry = saved;
1466                 seq = read_seqbegin(&rename_lock);
1467                 for (;;) {
1468                         if (new_dentry != old_dentry) {
1469                                 struct dentry * parent = new_dentry->d_parent;
1470                                 if (parent == new_dentry)
1471                                         break;
1472                                 new_dentry = parent;
1473                                 continue;
1474                         }
1475                         result = 1;
1476                         break;
1477                 }
1478         } while (read_seqretry(&rename_lock, seq));
1479         rcu_read_unlock();
1480
1481         return result;
1482 }
1483
1484 void d_genocide(struct dentry *root)
1485 {
1486         struct dentry *this_parent = root;
1487         struct list_head *next;
1488
1489         spin_lock(&dcache_lock);
1490 repeat:
1491         next = this_parent->d_subdirs.next;
1492 resume:
1493         while (next != &this_parent->d_subdirs) {
1494                 struct list_head *tmp = next;
1495                 struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
1496                 next = tmp->next;
1497                 if (d_unhashed(dentry)||!dentry->d_inode)
1498                         continue;
1499                 if (!list_empty(&dentry->d_subdirs)) {
1500                         this_parent = dentry;
1501                         goto repeat;
1502                 }
1503                 atomic_dec(&dentry->d_count);
1504         }
1505         if (this_parent != root) {
1506                 next = this_parent->d_child.next;
1507                 atomic_dec(&this_parent->d_count);
1508                 this_parent = this_parent->d_parent;
1509                 goto resume;
1510         }
1511         spin_unlock(&dcache_lock);
1512 }
1513
1514 /**
1515  * find_inode_number - check for dentry with name
1516  * @dir: directory to check
1517  * @name: Name to find.
1518  *
1519  * Check whether a dentry already exists for the given name,
1520  * and return the inode number if it has an inode. Otherwise
1521  * 0 is returned.
1522  *
1523  * This routine is used to post-process directory listings for
1524  * filesystems using synthetic inode numbers, and is necessary
1525  * to keep getcwd() working.
1526  */
1527
1528 ino_t find_inode_number(struct dentry *dir, struct qstr *name)
1529 {
1530         struct dentry * dentry;
1531         ino_t ino = 0;
1532
1533         /*
1534          * Check for a fs-specific hash function. Note that we must
1535          * calculate the standard hash first, as the d_op->d_hash()
1536          * routine may choose to leave the hash value unchanged.
1537          */
1538         name->hash = full_name_hash(name->name, name->len);
1539         if (dir->d_op && dir->d_op->d_hash)
1540         {
1541                 if (dir->d_op->d_hash(dir, name) != 0)
1542                         goto out;
1543         }
1544
1545         dentry = d_lookup(dir, name);
1546         if (dentry)
1547         {
1548                 if (dentry->d_inode)
1549                         ino = dentry->d_inode->i_ino;
1550                 dput(dentry);
1551         }
1552 out:
1553         return ino;
1554 }
1555
1556 static __initdata unsigned long dhash_entries;
1557 static int __init set_dhash_entries(char *str)
1558 {
1559         if (!str)
1560                 return 0;
1561         dhash_entries = simple_strtoul(str, &str, 0);
1562         return 1;
1563 }
1564 __setup("dhash_entries=", set_dhash_entries);
1565
1566 static void __init dcache_init_early(void)
1567 {
1568         int loop;
1569
1570         dentry_hashtable =
1571                 alloc_large_system_hash("Dentry cache",
1572                                         sizeof(struct hlist_head),
1573                                         dhash_entries,
1574                                         13,
1575                                         0,
1576                                         &d_hash_shift,
1577                                         &d_hash_mask);
1578
1579         for (loop = 0; loop < (1 << d_hash_shift); loop++)
1580                 INIT_HLIST_HEAD(&dentry_hashtable[loop]);
1581 }
1582
1583 static void __init dcache_init(unsigned long mempages)
1584 {
1585         /*
1586          * A constructor could be added for stable state like the lists,
1587          * but it is probably not worth it because of the cache nature
1588          * of the dcache.
1589          */
1590         dentry_cache = kmem_cache_create("dentry_cache",
1591                                          sizeof(struct dentry),
1592                                          0,
1593                                          SLAB_RECLAIM_ACCOUNT|SLAB_PANIC,
1594                                          NULL, NULL);
1595
1596         set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
1597 }
1598
1599 /* SLAB cache for __getname() consumers */
1600 kmem_cache_t *names_cachep;
1601
1602 /* SLAB cache for file structures */
1603 kmem_cache_t *filp_cachep;
1604
1605 EXPORT_SYMBOL(d_genocide);
1606
1607 extern void bdev_cache_init(void);
1608 extern void chrdev_init(void);
1609
1610 void __init vfs_caches_init_early(void)
1611 {
1612         dcache_init_early();
1613         inode_init_early();
1614 }
1615
1616 void __init vfs_caches_init(unsigned long mempages)
1617 {
1618         unsigned long reserve;
1619
1620         /* Base hash sizes on available memory, with a reserve equal to
1621            150% of current kernel size */
1622
1623         reserve = min((mempages - nr_free_pages()) * 3/2, mempages - 1);
1624         mempages -= reserve;
1625
1626         names_cachep = kmem_cache_create("names_cache", PATH_MAX, 0,
1627                         SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL, NULL);
1628
1629         filp_cachep = kmem_cache_create("filp", sizeof(struct file), 0,
1630                         SLAB_HWCACHE_ALIGN|SLAB_PANIC, filp_ctor, filp_dtor);
1631
1632         dcache_init(mempages);
1633         inode_init(mempages);
1634         files_init(mempages);
1635         mnt_init(mempages);
1636         bdev_cache_init();
1637         chrdev_init();
1638 }
1639
1640 EXPORT_SYMBOL(d_alloc);
1641 EXPORT_SYMBOL(d_alloc_anon);
1642 EXPORT_SYMBOL(d_alloc_root);
1643 EXPORT_SYMBOL(d_delete);
1644 EXPORT_SYMBOL(d_find_alias);
1645 EXPORT_SYMBOL(d_instantiate);
1646 EXPORT_SYMBOL(d_invalidate);
1647 EXPORT_SYMBOL(d_lookup);
1648 EXPORT_SYMBOL(d_move);
1649 EXPORT_SYMBOL(d_path);
1650 EXPORT_SYMBOL(d_prune_aliases);
1651 EXPORT_SYMBOL(d_rehash);
1652 EXPORT_SYMBOL(d_splice_alias);
1653 EXPORT_SYMBOL(d_validate);
1654 EXPORT_SYMBOL(dget_locked);
1655 EXPORT_SYMBOL(dput);
1656 EXPORT_SYMBOL(find_inode_number);
1657 EXPORT_SYMBOL(have_submounts);
1658 EXPORT_SYMBOL(is_subdir);
1659 EXPORT_SYMBOL(names_cachep);
1660 EXPORT_SYMBOL(shrink_dcache_anon);
1661 EXPORT_SYMBOL(shrink_dcache_parent);
1662 EXPORT_SYMBOL(shrink_dcache_sb);