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