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