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