fs/dcache.c

   1 /*
   2  * fs/dcache.c
   3  *
   4  * Complete reimplementation
   5  * (C) 1997 Thomas Schoebel-Theuer
   6  */
   7
   8 /*
   9  * Notes on the allocation strategy:
  10  *
  11  * The dcache is a master of the icache - whenever a dcache entry
  12  * exists, the inode will always exist. "iput()" is done either when
  13  * the dcache entry is deleted or garbage collected.
  14  */
  15
  16 #include <linux/string.h>
  17 #include <linux/mm.h>
  18 #include <linux/fs.h>
  19 #include <linux/malloc.h>
  20 #include <linux/init.h>
  21
  22 #define DCACHE_PARANOIA 1
  23 /* #define DCACHE_DEBUG 1 */
  24
  25 /* For managing the dcache */
  26 extern unsigned long num_physpages, page_cache_size;
  27 extern int inodes_stat[];
  28 #define nr_inodes (inodes_stat[0])
  29
  30 /*
  31  * This is the single most critical data structure when it comes
  32  * to the dcache: the hashtable for lookups. Somebody should try
  33  * to make this good - I've just made it work.
  34  *
  35  * This hash-function tries to avoid losing too many bits of hash
  36  * information, yet avoid using a prime hash-size or similar.
  37  */
  38 #define D_HASHBITS     10
  39 #define D_HASHSIZE     (1UL << D_HASHBITS)
  40 #define D_HASHMASK     (D_HASHSIZE-1)
  41
  42 static struct list_head dentry_hashtable[D_HASHSIZE];
  43 static LIST_HEAD(dentry_unused);
  44
  45 struct {
  46         int nr_dentry;
  47         int nr_unused;
  48         int age_limit;          /* age in seconds */
  49         int want_pages;         /* pages requested by system */
  50         int dummy[2];
  51 } dentry_stat = {0, 0, 45, 0,};
  52
  53 static inline void d_free(struct dentry *dentry)
  54 {
  55         if (dentry->d_op && dentry->d_op->d_release)
  56                 dentry->d_op->d_release(dentry);
  57         kfree(dentry->d_name.name);
  58         kfree(dentry);
  59 }
  60
  61 /*
  62  * Release the dentry's inode, using the fileystem
  63  * d_iput() operation if defined.
  64  */
  65 static inline void dentry_iput(struct dentry * dentry)
  66 {
  67         struct inode *inode = dentry->d_inode;
  68         if (inode) {
  69                 dentry->d_inode = NULL;
  70                 list_del(&dentry->d_alias);
  71                 INIT_LIST_HEAD(&dentry->d_alias);
  72                 if (dentry->d_op && dentry->d_op->d_iput)
  73                         dentry->d_op->d_iput(dentry, inode);
  74                 else
  75                         iput(inode);
  76         }
  77 }
  78
  79 /*
  80  * dput()
  81  *
  82  * This is complicated by the fact that we do not want to put
  83  * dentries that are no longer on any hash chain on the unused
  84  * list: we'd much rather just get rid of them immediately.
  85  *
  86  * However, that implies that we have to traverse the dentry
  87  * tree upwards to the parents which might _also_ now be
  88  * scheduled for deletion (it may have been only waiting for
  89  * its last child to go away).
  90  *
  91  * This tail recursion is done by hand as we don't want to depend
  92  * on the compiler to always get this right (gcc generally doesn't).
  93  * Real recursion would eat up our stack space.
  94  */
  95 void dput(struct dentry *dentry)
  96 {
  97         int count;
  98
  99         if (!dentry)
 100                 return;
 101
 102 repeat:
 103         count = dentry->d_count - 1;
 104         if (count != 0)
 105                 goto out;
 106
 107         /*
 108          * Note that if d_op->d_delete blocks,
 109          * the dentry could go back in use.
 110          * Each fs will have to watch for this.
 111          */
 112         if (dentry->d_op && dentry->d_op->d_delete) {
 113                 dentry->d_op->d_delete(dentry);
 114
 115                 count = dentry->d_count - 1;
 116                 if (count != 0)
 117                         goto out;
 118         }
 119
 120         if (!list_empty(&dentry->d_lru)) {
 121                 dentry_stat.nr_unused--;
 122                 list_del(&dentry->d_lru);
 123         }
 124         if (list_empty(&dentry->d_hash)) {
 125                 struct dentry * parent;
 126
 127                 list_del(&dentry->d_child);
 128                 dentry_iput(dentry);
 129                 parent = dentry->d_parent;
 130                 d_free(dentry);
 131                 if (dentry == parent)
 132                         return;
 133                 dentry = parent;
 134                 goto repeat;
 135         }
 136         list_add(&dentry->d_lru, &dentry_unused);
 137         dentry_stat.nr_unused++;
 138         /*
 139          * Update the timestamp
 140          */
 141         dentry->d_reftime = jiffies;
 142
 143 out:
 144         if (count >= 0) {
 145                 dentry->d_count = count;
 146                 return;
 147         }
 148
 149         printk(KERN_CRIT "Negative d_count (%d) for %s/%s\n",
 150                 count,
 151                 dentry->d_parent->d_name.name,
 152                 dentry->d_name.name);
 153         *(int *)0 = 0;
 154 }
 155
 156 /*
 157  * Try to invalidate the dentry if it turns out to be
 158  * possible. If there are other users of the dentry we
 159  * can't invalidate it.
 160  */
 161 int d_invalidate(struct dentry * dentry)
 162 {
 163         /* Check whether to do a partial shrink_dcache */
 164         if (!list_empty(&dentry->d_subdirs))
 165                 shrink_dcache_parent(dentry);
 166
 167         if (dentry->d_count != 1)
 168                 return -EBUSY;
 169
 170         d_drop(dentry);
 171         return 0;
 172 }
 173
 174 /*
 175  * Select less valuable dentries to be pruned when we need
 176  * inodes or memory. The selected dentries are moved to the
 177  * old end of the list where prune_dcache() can find them.
 178  *
 179  * Negative dentries are included in the selection so that
 180  * they don't accumulate at the end of the list. The count
 181  * returned is the total number of dentries selected, which
 182  * may be much larger than the requested number of inodes.
 183  */
 184 int select_dcache(int inode_count, int page_count)
 185 {
 186         struct list_head *next, *tail = &dentry_unused;
 187         int found = 0, forward = 0, young = 8;
 188         int depth = dentry_stat.nr_unused >> 1;
 189         unsigned long min_value = 0, max_value = 4;
 190
 191         if (page_count)
 192                 max_value = -1;
 193
 194         next = tail->prev;
 195         while (next != &dentry_unused && depth--) {
 196                 struct list_head *tmp = next;
 197                 struct dentry *dentry = list_entry(tmp, struct dentry, d_lru);
 198                 struct inode *inode = dentry->d_inode;
 199                 unsigned long value = 0;
 200
 201                 next = tmp->prev;
 202                 if (forward)
 203                         next = tmp->next;
 204                 if (dentry->d_count) {
 205                         dentry_stat.nr_unused--;
 206                         list_del(tmp);
 207                         INIT_LIST_HEAD(tmp);
 208                         continue;
 209                 }
 210                 /*
 211                  * Check the dentry's age to see whether to change direction.
 212                  */
 213                 if (!forward) {
 214                         int age = (jiffies - dentry->d_reftime) / HZ;
 215                         if (age < dentry_stat.age_limit) {
 216                                 if (!--young) {
 217                                         forward = 1;
 218                                         next = dentry_unused.next;
 219                                         /*
 220                                          * Update the limits -- we don't want
 221                                          * files with too few or too many pages.
 222                                          */
 223                                         if (page_count) {
 224                                                 min_value = 3;
 225                                                 max_value = 15;
 226                                         }
 227 #ifdef DCACHE_DEBUG
 228 printk("select_dcache: %s/%s age=%d, scanning forward\n",
 229 dentry->d_parent->d_name.name, dentry->d_name.name, age);
 230 #endif
 231                                 }
 232                                 continue;
 233                         }
 234                 }
 235
 236                 /*
 237                  * Select dentries based on the page cache count ...
 238                  * should factor in number of uses as well. We take
 239                  * all negative dentries so that they don't accumulate.
 240                  * (We skip inodes that aren't immediately available.)
 241                  */
 242                 if (inode) {
 243                         value = inode->i_nrpages;
 244                         if (value >= max_value || value < min_value)
 245                                 continue;
 246                         if (inode->i_state || inode->i_count > 1)
 247                                 continue;
 248                 }
 249
 250                 /*
 251                  * Move the selected dentries behind the tail.
 252                  */
 253                 if (tmp != tail->prev) {
 254                         list_del(tmp);
 255                         list_add(tmp, tail->prev);
 256                 }
 257                 tail = tmp;
 258                 found++;
 259                 if (inode && --inode_count <= 0)
 260                         break;
 261                 if (page_count && (page_count -= value) <= 0)
 262                         break;
 263         }
 264         return found;
 265 }
 266
 267 /*
 268  * Throw away a dentry - free the inode, dput the parent.
 269  * This requires that the LRU list has already been
 270  * removed.
 271  */
 272 static inline void prune_one_dentry(struct dentry * dentry)
 273 {
 274         struct dentry * parent;
 275
 276         list_del(&dentry->d_hash);
 277         list_del(&dentry->d_child);
 278         dentry_iput(dentry);
 279         parent = dentry->d_parent;
 280         d_free(dentry);
 281         dput(parent);
 282 }
 283
 284 /*
 285  * Shrink the dcache. This is done when we need
 286  * more memory, or simply when we need to unmount
 287  * something (at which point we need to unuse
 288  * all dentries).
 289  */
 290 void prune_dcache(int count)
 291 {
 292         for (;;) {
 293                 struct dentry *dentry;
 294                 struct list_head *tmp = dentry_unused.prev;
 295
 296                 if (tmp == &dentry_unused)
 297                         break;
 298                 dentry_stat.nr_unused--;
 299                 list_del(tmp);
 300                 INIT_LIST_HEAD(tmp);
 301                 dentry = list_entry(tmp, struct dentry, d_lru);
 302                 if (!dentry->d_count) {
 303                         prune_one_dentry(dentry);
 304                         if (!--count)
 305                                 break;
 306                 }
 307         }
 308 }
 309
 310 /*
 311  * Shrink the dcache for the specified super block.
 312  * This allows us to unmount a device without disturbing
 313  * the dcache for the other devices.
 314  *
 315  * This implementation makes just two traversals of the
 316  * unused list.  On the first pass we move the selected
 317  * dentries to the most recent end, and on the second
 318  * pass we free them.  The second pass must restart after
 319  * each dput(), but since the target dentries are all at
 320  * the end, it's really just a single traversal.
 321  */
 322 void shrink_dcache_sb(struct super_block * sb)
 323 {
 324         struct list_head *tmp, *next;
 325         struct dentry *dentry;
 326
 327         /*
 328          * Pass one ... move the dentries for the specified
 329          * superblock to the most recent end of the unused list.
 330          */
 331         next = dentry_unused.next;
 332         while (next != &dentry_unused) {
 333                 tmp = next;
 334                 next = tmp->next;
 335                 dentry = list_entry(tmp, struct dentry, d_lru);
 336                 if (dentry->d_sb != sb)
 337                         continue;
 338                 list_del(tmp);
 339                 list_add(tmp, &dentry_unused);
 340         }
 341
 342         /*
 343          * Pass two ... free the dentries for this superblock.
 344          */
 345 repeat:
 346         next = dentry_unused.next;
 347         while (next != &dentry_unused) {
 348                 tmp = next;
 349                 next = tmp->next;
 350                 dentry = list_entry(tmp, struct dentry, d_lru);
 351                 if (dentry->d_sb != sb)
 352                         continue;
 353                 if (dentry->d_count)
 354                         continue;
 355                 dentry_stat.nr_unused--;
 356                 list_del(tmp);
 357                 INIT_LIST_HEAD(tmp);
 358                 prune_one_dentry(dentry);
 359                 goto repeat;
 360         }
 361 }
 362
 363 /*
 364  * Search the dentry child list for the specified parent,
 365  * and move any unused dentries to the end of the unused
 366  * list for prune_dcache(). We descend to the next level
 367  * whenever the d_subdirs list is non-empty and continue
 368  * searching.
 369  */
 370 static int select_parent(struct dentry * parent)
 371 {
 372         struct dentry *this_parent = parent;
 373         struct list_head *next;
 374         int found = 0;
 375
 376 repeat:
 377         next = this_parent->d_subdirs.next;
 378 resume:
 379         while (next != &this_parent->d_subdirs) {
 380                 struct list_head *tmp = next;
 381                 struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
 382                 next = tmp->next;
 383                 if (!dentry->d_count) {
 384                         list_del(&dentry->d_lru);
 385                         list_add(&dentry->d_lru, dentry_unused.prev);
 386                         found++;
 387                 }
 388                 /*
 389                  * Descend a level if the d_subdirs list is non-empty.
 390                  */
 391                 if (!list_empty(&dentry->d_subdirs)) {
 392                         this_parent = dentry;
 393 #ifdef DCACHE_DEBUG
 394 printk(KERN_DEBUG "select_parent: descending to %s/%s, found=%d\n",
 395 dentry->d_parent->d_name.name, dentry->d_name.name, found);
 396 #endif
 397                         goto repeat;
 398                 }
 399         }
 400         /*
 401          * All done at this level ... ascend and resume the search.
 402          */
 403         if (this_parent != parent) {
 404                 next = this_parent->d_child.next;
 405                 this_parent = this_parent->d_parent;
 406 #ifdef DCACHE_DEBUG
 407 printk(KERN_DEBUG "select_parent: ascending to %s/%s, found=%d\n",
 408 this_parent->d_parent->d_name.name, this_parent->d_name.name, found);
 409 #endif
 410                 goto resume;
 411         }
 412         return found;
 413 }
 414
 415 /*
 416  * Prune the dcache to remove unused children of the parent dentry.
 417  */
 418 void shrink_dcache_parent(struct dentry * parent)
 419 {
 420         int found;
 421
 422         while ((found = select_parent(parent)) != 0)
 423                 prune_dcache(found);
 424 }
 425
 426 /*
 427  * This is called from do_try_to_free_page() to indicate
 428  * that we should reduce the dcache and inode cache memory.
 429  */
 430 void shrink_dcache_memory()
 431 {
 432         dentry_stat.want_pages++;
 433 }
 434
 435 /*
 436  * This carries out the request received by the above routine.
 437  */
 438 void check_dcache_memory()
 439 {
 440         if (dentry_stat.want_pages) {
 441                 unsigned int count, goal = 0;
 442                 /*
 443                  * Set the page goal.  We don't necessarily need to trim
 444                  * the dcache just because the system needs memory ...
 445                  */
 446                 if (page_cache_size > (num_physpages >> 1))
 447                         goal = (dentry_stat.want_pages * page_cache_size)
 448                                 / num_physpages;
 449                 dentry_stat.want_pages = 0;
 450                 if (goal) {
 451                         if (goal > 50)
 452                                 goal = 50;
 453                         count = select_dcache(32, goal);
 454 #ifdef DCACHE_DEBUG
 455 printk(KERN_DEBUG "check_dcache_memory: goal=%d, count=%d\n", goal, count);
 456 #endif
 457                         if (count) {
 458                                 prune_dcache(count);
 459                                 free_inode_memory(count);
 460                         }
 461                 }
 462         }
 463 }
 464
 465 #define NAME_ALLOC_LEN(len)     ((len+16) & ~15)
 466
 467 struct dentry * d_alloc(struct dentry * parent, const struct qstr *name)
 468 {
 469         char * str;
 470         struct dentry *dentry;
 471
 472         /*
 473          * Prune the dcache if there are too many unused dentries.
 474          */
 475         if (dentry_stat.nr_unused > 3*(nr_inodes >> 1)) {
 476 #ifdef DCACHE_DEBUG
 477 printk("d_alloc: %d unused, pruning dcache\n", dentry_stat.nr_unused);
 478 #endif
 479                 prune_dcache(8);
 480                 free_inode_memory(8);
 481         }
 482
 483         dentry = kmalloc(sizeof(struct dentry), GFP_KERNEL);
 484         if (!dentry)
 485                 return NULL;
 486
 487         str = kmalloc(NAME_ALLOC_LEN(name->len), GFP_KERNEL);
 488         if (!str) {
 489                 kfree(dentry);
 490                 return NULL;
 491         }
 492
 493         memcpy(str, name->name, name->len);
 494         str[name->len] = 0;
 495
 496         dentry->d_count = 1;
 497         dentry->d_flags = 0;
 498         dentry->d_inode = NULL;
 499         dentry->d_parent = NULL;
 500         dentry->d_sb = NULL;
 501         if (parent) {
 502                 dentry->d_parent = dget(parent);
 503                 dentry->d_sb = parent->d_sb;
 504                 list_add(&dentry->d_child, &parent->d_subdirs);
 505         } else
 506                 INIT_LIST_HEAD(&dentry->d_child);
 507
 508         dentry->d_mounts = dentry;
 509         dentry->d_covers = dentry;
 510         INIT_LIST_HEAD(&dentry->d_hash);
 511         INIT_LIST_HEAD(&dentry->d_lru);
 512         INIT_LIST_HEAD(&dentry->d_subdirs);
 513         INIT_LIST_HEAD(&dentry->d_alias);
 514
 515         dentry->d_name.name = str;
 516         dentry->d_name.len = name->len;
 517         dentry->d_name.hash = name->hash;
 518         dentry->d_op = NULL;
 519         dentry->d_fsdata = NULL;
 520         return dentry;
 521 }
 522
 523 /*
 524  * Fill in inode information in the entry.
 525  *
 526  * This turns negative dentries into productive full members
 527  * of society.
 528  *
 529  * NOTE! This assumes that the inode count has been incremented
 530  * (or otherwise set) by the caller to indicate that it is now
 531  * in use by the dcache..
 532  */
 533 void d_instantiate(struct dentry *entry, struct inode * inode)
 534 {
 535         if (inode)
 536                 list_add(&entry->d_alias, &inode->i_dentry);
 537         entry->d_inode = inode;
 538 }
 539
 540 struct dentry * d_alloc_root(struct inode * root_inode, struct dentry *old_root)
 541 {
 542         struct dentry *res = NULL;
 543
 544         if (root_inode) {
 545                 res = d_alloc(NULL, &(const struct qstr) { "/", 1, 0 });
 546                 if (res) {
 547                         res->d_sb = root_inode->i_sb;
 548                         res->d_parent = res;
 549                         d_instantiate(res, root_inode);
 550                 }
 551         }
 552         return res;
 553 }
 554
 555 static inline struct list_head * d_hash(struct dentry * parent, unsigned long hash)
 556 {
 557         hash += (unsigned long) parent;
 558         hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);
 559         return dentry_hashtable + (hash & D_HASHMASK);
 560 }
 561
 562 struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
 563 {
 564         unsigned int len = name->len;
 565         unsigned int hash = name->hash;
 566         const unsigned char *str = name->name;
 567         struct list_head *head = d_hash(parent,hash);
 568         struct list_head *tmp = head->next;
 569
 570         while (tmp != head) {
 571                 struct dentry * dentry = list_entry(tmp, struct dentry, d_hash);
 572
 573                 tmp = tmp->next;
 574                 if (dentry->d_name.hash != hash)
 575                         continue;
 576                 if (dentry->d_parent != parent)
 577                         continue;
 578                 if (parent->d_op && parent->d_op->d_compare) {
 579                         if (parent->d_op->d_compare(parent, &dentry->d_name, name))
 580                                 continue;
 581                 } else {
 582                         if (dentry->d_name.len != len)
 583                                 continue;
 584                         if (memcmp(dentry->d_name.name, str, len))
 585                                 continue;
 586                 }
 587                 return dget(dentry);
 588         }
 589         return NULL;
 590 }
 591
 592 /*
 593  * An insecure source has sent us a dentry, here we verify it.
 594  *
 595  * This is just to make knfsd able to have the dentry pointer
 596  * in the NFS file handle.
 597  *
 598  * NOTE! Do _not_ dereference the pointers before we have
 599  * validated them. We can test the pointer values, but we
 600  * must not actually use them until we have found a valid
 601  * copy of the pointer in kernel space..
 602  */
 603 int d_validate(struct dentry *dentry, struct dentry *dparent,
 604                unsigned int hash, unsigned int len)
 605 {
 606         struct list_head *base, *lhp;
 607         int valid = 1;
 608
 609         if (dentry != dparent) {
 610                 base = d_hash(dparent, hash);
 611                 lhp = base;
 612                 while ((lhp = lhp->next) != base) {
 613                         if (dentry == list_entry(lhp, struct dentry, d_hash))
 614                                 goto out;
 615                 }
 616         } else {
 617                 /*
 618                  * Special case: local mount points don't live in
 619                  * the hashes, so we search the super blocks.
 620                  */
 621                 struct super_block *sb = super_blocks + 0;
 622
 623                 for (; sb < super_blocks + NR_SUPER; sb++) {
 624                         if (!sb->s_dev)
 625                                 continue;
 626                         if (sb->s_root == dentry)
 627                                 goto out;
 628                 }
 629         }
 630         valid = 0;
 631 out:
 632         return valid;
 633 }
 634
 635 /*
 636  * When a file is deleted, we have two options:
 637  * - turn this dentry into a negative dentry
 638  * - unhash this dentry and free it.
 639  *
 640  * Usually, we want to just turn this into
 641  * a negative dentry, but if anybody else is
 642  * currently using the dentry or the inode
 643  * we can't do that and we fall back on removing
 644  * it from the hash queues and waiting for
 645  * it to be deleted later when it has no users
 646  */
 647 void d_delete(struct dentry * dentry)
 648 {
 649         /*
 650          * Are we the only user?
 651          */
 652         if (dentry->d_count == 1) {
 653                 dentry_iput(dentry);
 654                 return;
 655         }
 656
 657         /*
 658          * If not, just drop the dentry and let dput
 659          * pick up the tab..
 660          */
 661         d_drop(dentry);
 662 }
 663
 664 void d_add(struct dentry * entry, struct inode * inode)
 665 {
 666         struct dentry * parent = entry->d_parent;
 667
 668         list_add(&entry->d_hash, d_hash(parent, entry->d_name.hash));
 669         d_instantiate(entry, inode);
 670 }
 671
 672 #define switch(x,y) do { \
 673         __typeof__ (x) __tmp = x; \
 674         x = y; y = __tmp; } while (0)
 675
 676 /*
 677  * We cannibalize "target" when moving dentry on top of it,
 678  * because it's going to be thrown away anyway. We could be more
 679  * polite about it, though.
 680  *
 681  * This forceful removal will result in ugly /proc output if
 682  * somebody holds a file open that got deleted due to a rename.
 683  * We could be nicer about the deleted file, and let it show
 684  * up under the name it got deleted rather than the name that
 685  * deleted it.
 686  *
 687  * Careful with the hash switch. The hash switch depends on
 688  * the fact that any list-entry can be a head of the list.
 689  * Think about it.
 690  */
 691 void d_move(struct dentry * dentry, struct dentry * target)
 692 {
 693         if (!dentry->d_inode)
 694                 printk(KERN_WARNING "VFS: moving negative dcache entry\n");
 695
 696         /* Move the dentry to the target hash queue */
 697         list_del(&dentry->d_hash);
 698         list_add(&dentry->d_hash, &target->d_hash);
 699
 700         /* Unhash the target: dput() will then get rid of it */
 701         list_del(&target->d_hash);
 702         INIT_LIST_HEAD(&target->d_hash);
 703
 704         list_del(&dentry->d_child);
 705         list_del(&target->d_child);
 706
 707         /* Switch the parents and the names.. */
 708         switch(dentry->d_parent, target->d_parent);
 709         switch(dentry->d_name.name, target->d_name.name);
 710         switch(dentry->d_name.len, target->d_name.len);
 711         switch(dentry->d_name.hash, target->d_name.hash);
 712         list_add(&target->d_child, &target->d_parent->d_subdirs);
 713         list_add(&dentry->d_child, &dentry->d_parent->d_subdirs);
 714 }
 715
 716 /*
 717  * "buflen" should be PAGE_SIZE or more.
 718  */
 719 char * d_path(struct dentry *dentry, char *buffer, int buflen)
 720 {
 721         char * end = buffer+buflen;
 722         char * retval;
 723         struct dentry * root = current->fs->root;
 724
 725         *--end = '\0';
 726         buflen--;
 727         if (dentry->d_parent != dentry && list_empty(&dentry->d_hash)) {
 728                 buflen -= 10;
 729                 end -= 10;
 730                 memcpy(end, " (deleted)", 10);
 731         }
 732
 733         /* Get '/' right */
 734         retval = end-1;
 735         *retval = '/';
 736
 737         for (;;) {
 738                 struct dentry * parent;
 739                 int namelen;
 740
 741                 if (dentry == root)
 742                         break;
 743                 dentry = dentry->d_covers;
 744                 parent = dentry->d_parent;
 745                 if (dentry == parent)
 746                         break;
 747                 namelen = dentry->d_name.len;
 748                 buflen -= namelen + 1;
 749                 if (buflen < 0)
 750                         break;
 751                 end -= namelen;
 752                 memcpy(end, dentry->d_name.name, namelen);
 753                 *--end = '/';
 754                 retval = end;
 755                 dentry = parent;
 756         }
 757         return retval;
 758 }
 759
 760 /*
 761  * Check whether a dentry already exists for the given name,
 762  * and return the inode number if it has an inode.
 763  *
 764  * This routine is used to post-process directory listings for
 765  * filesystems using synthetic inode numbers, and is necessary
 766  * to keep getcwd() working.
 767  */
 768 ino_t find_inode_number(struct dentry *dir, struct qstr *name)
 769 {
 770         struct dentry * dentry;
 771         ino_t ino = 0;
 772
 773         /*
 774          * Check for a fs-specific hash function. Note that we must
 775          * calculate the standard hash first, as the d_op->d_hash()
 776          * routine may choose to leave the hash value unchanged.
 777          */
 778         name->hash = full_name_hash(name->name, name->len);
 779         if (dir->d_op && dir->d_op->d_hash)
 780         {
 781                 if (dir->d_op->d_hash(dir, name) != 0)
 782                         goto out;
 783         }
 784
 785         dentry = d_lookup(dir, name);
 786         if (dentry)
 787         {
 788                 if (dentry->d_inode)
 789                         ino = dentry->d_inode->i_ino;
 790                 dput(dentry);
 791         }
 792 out:
 793         return ino;
 794 }
 795
 796 __initfunc(void dcache_init(void))
 797 {
 798         int i;
 799         struct list_head *d = dentry_hashtable;
 800
 801         i = D_HASHSIZE;
 802         do {
 803                 INIT_LIST_HEAD(d);
 804                 d++;
 805                 i--;
 806         } while (i);
 807 }