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