fs: change d_compare for rcu-walk
[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                 dentry_lru_del(dentry);
457                 __d_drop(dentry);
458                 dentry = d_kill(dentry);
459                 spin_lock(&dcache_lock);
460         }
461 }
462
463 static void shrink_dentry_list(struct list_head *list)
464 {
465         struct dentry *dentry;
466
467         while (!list_empty(list)) {
468                 dentry = list_entry(list->prev, struct dentry, d_lru);
469                 dentry_lru_del(dentry);
470
471                 /*
472                  * We found an inuse dentry which was not removed from
473                  * the LRU because of laziness during lookup.  Do not free
474                  * it - just keep it off the LRU list.
475                  */
476                 spin_lock(&dentry->d_lock);
477                 if (atomic_read(&dentry->d_count)) {
478                         spin_unlock(&dentry->d_lock);
479                         continue;
480                 }
481                 prune_one_dentry(dentry);
482                 /* dentry->d_lock was dropped in prune_one_dentry() */
483                 cond_resched_lock(&dcache_lock);
484         }
485 }
486
487 /**
488  * __shrink_dcache_sb - shrink the dentry LRU on a given superblock
489  * @sb:         superblock to shrink dentry LRU.
490  * @count:      number of entries to prune
491  * @flags:      flags to control the dentry processing
492  *
493  * If flags contains DCACHE_REFERENCED reference dentries will not be pruned.
494  */
495 static void __shrink_dcache_sb(struct super_block *sb, int *count, int flags)
496 {
497         /* called from prune_dcache() and shrink_dcache_parent() */
498         struct dentry *dentry;
499         LIST_HEAD(referenced);
500         LIST_HEAD(tmp);
501         int cnt = *count;
502
503         spin_lock(&dcache_lock);
504         while (!list_empty(&sb->s_dentry_lru)) {
505                 dentry = list_entry(sb->s_dentry_lru.prev,
506                                 struct dentry, d_lru);
507                 BUG_ON(dentry->d_sb != sb);
508
509                 /*
510                  * If we are honouring the DCACHE_REFERENCED flag and the
511                  * dentry has this flag set, don't free it.  Clear the flag
512                  * and put it back on the LRU.
513                  */
514                 if (flags & DCACHE_REFERENCED) {
515                         spin_lock(&dentry->d_lock);
516                         if (dentry->d_flags & DCACHE_REFERENCED) {
517                                 dentry->d_flags &= ~DCACHE_REFERENCED;
518                                 list_move(&dentry->d_lru, &referenced);
519                                 spin_unlock(&dentry->d_lock);
520                                 cond_resched_lock(&dcache_lock);
521                                 continue;
522                         }
523                         spin_unlock(&dentry->d_lock);
524                 }
525
526                 list_move_tail(&dentry->d_lru, &tmp);
527                 if (!--cnt)
528                         break;
529                 cond_resched_lock(&dcache_lock);
530         }
531
532         *count = cnt;
533         shrink_dentry_list(&tmp);
534
535         if (!list_empty(&referenced))
536                 list_splice(&referenced, &sb->s_dentry_lru);
537         spin_unlock(&dcache_lock);
538
539 }
540
541 /**
542  * prune_dcache - shrink the dcache
543  * @count: number of entries to try to free
544  *
545  * Shrink the dcache. This is done when we need more memory, or simply when we
546  * need to unmount something (at which point we need to unuse all dentries).
547  *
548  * This function may fail to free any resources if all the dentries are in use.
549  */
550 static void prune_dcache(int count)
551 {
552         struct super_block *sb, *p = NULL;
553         int w_count;
554         int unused = dentry_stat.nr_unused;
555         int prune_ratio;
556         int pruned;
557
558         if (unused == 0 || count == 0)
559                 return;
560         spin_lock(&dcache_lock);
561         if (count >= unused)
562                 prune_ratio = 1;
563         else
564                 prune_ratio = unused / count;
565         spin_lock(&sb_lock);
566         list_for_each_entry(sb, &super_blocks, s_list) {
567                 if (list_empty(&sb->s_instances))
568                         continue;
569                 if (sb->s_nr_dentry_unused == 0)
570                         continue;
571                 sb->s_count++;
572                 /* Now, we reclaim unused dentrins with fairness.
573                  * We reclaim them same percentage from each superblock.
574                  * We calculate number of dentries to scan on this sb
575                  * as follows, but the implementation is arranged to avoid
576                  * overflows:
577                  * number of dentries to scan on this sb =
578                  * count * (number of dentries on this sb /
579                  * number of dentries in the machine)
580                  */
581                 spin_unlock(&sb_lock);
582                 if (prune_ratio != 1)
583                         w_count = (sb->s_nr_dentry_unused / prune_ratio) + 1;
584                 else
585                         w_count = sb->s_nr_dentry_unused;
586                 pruned = w_count;
587                 /*
588                  * We need to be sure this filesystem isn't being unmounted,
589                  * otherwise we could race with generic_shutdown_super(), and
590                  * end up holding a reference to an inode while the filesystem
591                  * is unmounted.  So we try to get s_umount, and make sure
592                  * s_root isn't NULL.
593                  */
594                 if (down_read_trylock(&sb->s_umount)) {
595                         if ((sb->s_root != NULL) &&
596                             (!list_empty(&sb->s_dentry_lru))) {
597                                 spin_unlock(&dcache_lock);
598                                 __shrink_dcache_sb(sb, &w_count,
599                                                 DCACHE_REFERENCED);
600                                 pruned -= w_count;
601                                 spin_lock(&dcache_lock);
602                         }
603                         up_read(&sb->s_umount);
604                 }
605                 spin_lock(&sb_lock);
606                 if (p)
607                         __put_super(p);
608                 count -= pruned;
609                 p = sb;
610                 /* more work left to do? */
611                 if (count <= 0)
612                         break;
613         }
614         if (p)
615                 __put_super(p);
616         spin_unlock(&sb_lock);
617         spin_unlock(&dcache_lock);
618 }
619
620 /**
621  * shrink_dcache_sb - shrink dcache for a superblock
622  * @sb: superblock
623  *
624  * Shrink the dcache for the specified super block. This is used to free
625  * the dcache before unmounting a file system.
626  */
627 void shrink_dcache_sb(struct super_block *sb)
628 {
629         LIST_HEAD(tmp);
630
631         spin_lock(&dcache_lock);
632         while (!list_empty(&sb->s_dentry_lru)) {
633                 list_splice_init(&sb->s_dentry_lru, &tmp);
634                 shrink_dentry_list(&tmp);
635         }
636         spin_unlock(&dcache_lock);
637 }
638 EXPORT_SYMBOL(shrink_dcache_sb);
639
640 /*
641  * destroy a single subtree of dentries for unmount
642  * - see the comments on shrink_dcache_for_umount() for a description of the
643  *   locking
644  */
645 static void shrink_dcache_for_umount_subtree(struct dentry *dentry)
646 {
647         struct dentry *parent;
648         unsigned detached = 0;
649
650         BUG_ON(!IS_ROOT(dentry));
651
652         /* detach this root from the system */
653         spin_lock(&dcache_lock);
654         dentry_lru_del(dentry);
655         __d_drop(dentry);
656         spin_unlock(&dcache_lock);
657
658         for (;;) {
659                 /* descend to the first leaf in the current subtree */
660                 while (!list_empty(&dentry->d_subdirs)) {
661                         struct dentry *loop;
662
663                         /* this is a branch with children - detach all of them
664                          * from the system in one go */
665                         spin_lock(&dcache_lock);
666                         list_for_each_entry(loop, &dentry->d_subdirs,
667                                             d_u.d_child) {
668                                 dentry_lru_del(loop);
669                                 __d_drop(loop);
670                                 cond_resched_lock(&dcache_lock);
671                         }
672                         spin_unlock(&dcache_lock);
673
674                         /* move to the first child */
675                         dentry = list_entry(dentry->d_subdirs.next,
676                                             struct dentry, d_u.d_child);
677                 }
678
679                 /* consume the dentries from this leaf up through its parents
680                  * until we find one with children or run out altogether */
681                 do {
682                         struct inode *inode;
683
684                         if (atomic_read(&dentry->d_count) != 0) {
685                                 printk(KERN_ERR
686                                        "BUG: Dentry %p{i=%lx,n=%s}"
687                                        " still in use (%d)"
688                                        " [unmount of %s %s]\n",
689                                        dentry,
690                                        dentry->d_inode ?
691                                        dentry->d_inode->i_ino : 0UL,
692                                        dentry->d_name.name,
693                                        atomic_read(&dentry->d_count),
694                                        dentry->d_sb->s_type->name,
695                                        dentry->d_sb->s_id);
696                                 BUG();
697                         }
698
699                         if (IS_ROOT(dentry))
700                                 parent = NULL;
701                         else {
702                                 parent = dentry->d_parent;
703                                 atomic_dec(&parent->d_count);
704                         }
705
706                         list_del(&dentry->d_u.d_child);
707                         detached++;
708
709                         inode = dentry->d_inode;
710                         if (inode) {
711                                 dentry->d_inode = NULL;
712                                 list_del_init(&dentry->d_alias);
713                                 if (dentry->d_op && dentry->d_op->d_iput)
714                                         dentry->d_op->d_iput(dentry, inode);
715                                 else
716                                         iput(inode);
717                         }
718
719                         d_free(dentry);
720
721                         /* finished when we fall off the top of the tree,
722                          * otherwise we ascend to the parent and move to the
723                          * next sibling if there is one */
724                         if (!parent)
725                                 return;
726                         dentry = parent;
727                 } while (list_empty(&dentry->d_subdirs));
728
729                 dentry = list_entry(dentry->d_subdirs.next,
730                                     struct dentry, d_u.d_child);
731         }
732 }
733
734 /*
735  * destroy the dentries attached to a superblock on unmounting
736  * - we don't need to use dentry->d_lock, and only need dcache_lock when
737  *   removing the dentry from the system lists and hashes because:
738  *   - the superblock is detached from all mountings and open files, so the
739  *     dentry trees will not be rearranged by the VFS
740  *   - s_umount is write-locked, so the memory pressure shrinker will ignore
741  *     any dentries belonging to this superblock that it comes across
742  *   - the filesystem itself is no longer permitted to rearrange the dentries
743  *     in this superblock
744  */
745 void shrink_dcache_for_umount(struct super_block *sb)
746 {
747         struct dentry *dentry;
748
749         if (down_read_trylock(&sb->s_umount))
750                 BUG();
751
752         dentry = sb->s_root;
753         sb->s_root = NULL;
754         atomic_dec(&dentry->d_count);
755         shrink_dcache_for_umount_subtree(dentry);
756
757         while (!hlist_empty(&sb->s_anon)) {
758                 dentry = hlist_entry(sb->s_anon.first, struct dentry, d_hash);
759                 shrink_dcache_for_umount_subtree(dentry);
760         }
761 }
762
763 /*
764  * Search for at least 1 mount point in the dentry's subdirs.
765  * We descend to the next level whenever the d_subdirs
766  * list is non-empty and continue searching.
767  */
768  
769 /**
770  * have_submounts - check for mounts over a dentry
771  * @parent: dentry to check.
772  *
773  * Return true if the parent or its subdirectories contain
774  * a mount point
775  */
776  
777 int have_submounts(struct dentry *parent)
778 {
779         struct dentry *this_parent = parent;
780         struct list_head *next;
781
782         spin_lock(&dcache_lock);
783         if (d_mountpoint(parent))
784                 goto positive;
785 repeat:
786         next = this_parent->d_subdirs.next;
787 resume:
788         while (next != &this_parent->d_subdirs) {
789                 struct list_head *tmp = next;
790                 struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
791                 next = tmp->next;
792                 /* Have we found a mount point ? */
793                 if (d_mountpoint(dentry))
794                         goto positive;
795                 if (!list_empty(&dentry->d_subdirs)) {
796                         this_parent = dentry;
797                         goto repeat;
798                 }
799         }
800         /*
801          * All done at this level ... ascend and resume the search.
802          */
803         if (this_parent != parent) {
804                 next = this_parent->d_u.d_child.next;
805                 this_parent = this_parent->d_parent;
806                 goto resume;
807         }
808         spin_unlock(&dcache_lock);
809         return 0; /* No mount points found in tree */
810 positive:
811         spin_unlock(&dcache_lock);
812         return 1;
813 }
814 EXPORT_SYMBOL(have_submounts);
815
816 /*
817  * Search the dentry child list for the specified parent,
818  * and move any unused dentries to the end of the unused
819  * list for prune_dcache(). We descend to the next level
820  * whenever the d_subdirs list is non-empty and continue
821  * searching.
822  *
823  * It returns zero iff there are no unused children,
824  * otherwise  it returns the number of children moved to
825  * the end of the unused list. This may not be the total
826  * number of unused children, because select_parent can
827  * drop the lock and return early due to latency
828  * constraints.
829  */
830 static int select_parent(struct dentry * parent)
831 {
832         struct dentry *this_parent = parent;
833         struct list_head *next;
834         int found = 0;
835
836         spin_lock(&dcache_lock);
837 repeat:
838         next = this_parent->d_subdirs.next;
839 resume:
840         while (next != &this_parent->d_subdirs) {
841                 struct list_head *tmp = next;
842                 struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
843                 next = tmp->next;
844
845                 /* 
846                  * move only zero ref count dentries to the end 
847                  * of the unused list for prune_dcache
848                  */
849                 if (!atomic_read(&dentry->d_count)) {
850                         dentry_lru_move_tail(dentry);
851                         found++;
852                 } else {
853                         dentry_lru_del(dentry);
854                 }
855
856                 /*
857                  * We can return to the caller if we have found some (this
858                  * ensures forward progress). We'll be coming back to find
859                  * the rest.
860                  */
861                 if (found && need_resched())
862                         goto out;
863
864                 /*
865                  * Descend a level if the d_subdirs list is non-empty.
866                  */
867                 if (!list_empty(&dentry->d_subdirs)) {
868                         this_parent = dentry;
869                         goto repeat;
870                 }
871         }
872         /*
873          * All done at this level ... ascend and resume the search.
874          */
875         if (this_parent != parent) {
876                 next = this_parent->d_u.d_child.next;
877                 this_parent = this_parent->d_parent;
878                 goto resume;
879         }
880 out:
881         spin_unlock(&dcache_lock);
882         return found;
883 }
884
885 /**
886  * shrink_dcache_parent - prune dcache
887  * @parent: parent of entries to prune
888  *
889  * Prune the dcache to remove unused children of the parent dentry.
890  */
891  
892 void shrink_dcache_parent(struct dentry * parent)
893 {
894         struct super_block *sb = parent->d_sb;
895         int found;
896
897         while ((found = select_parent(parent)) != 0)
898                 __shrink_dcache_sb(sb, &found, 0);
899 }
900 EXPORT_SYMBOL(shrink_dcache_parent);
901
902 /*
903  * Scan `nr' dentries and return the number which remain.
904  *
905  * We need to avoid reentering the filesystem if the caller is performing a
906  * GFP_NOFS allocation attempt.  One example deadlock is:
907  *
908  * ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
909  * prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->put_inode->
910  * ext2_discard_prealloc->ext2_free_blocks->lock_super->DEADLOCK.
911  *
912  * In this case we return -1 to tell the caller that we baled.
913  */
914 static int shrink_dcache_memory(struct shrinker *shrink, int nr, gfp_t gfp_mask)
915 {
916         if (nr) {
917                 if (!(gfp_mask & __GFP_FS))
918                         return -1;
919                 prune_dcache(nr);
920         }
921
922         return (dentry_stat.nr_unused / 100) * sysctl_vfs_cache_pressure;
923 }
924
925 static struct shrinker dcache_shrinker = {
926         .shrink = shrink_dcache_memory,
927         .seeks = DEFAULT_SEEKS,
928 };
929
930 /**
931  * d_alloc      -       allocate a dcache entry
932  * @parent: parent of entry to allocate
933  * @name: qstr of the name
934  *
935  * Allocates a dentry. It returns %NULL if there is insufficient memory
936  * available. On a success the dentry is returned. The name passed in is
937  * copied and the copy passed in may be reused after this call.
938  */
939  
940 struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
941 {
942         struct dentry *dentry;
943         char *dname;
944
945         dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
946         if (!dentry)
947                 return NULL;
948
949         if (name->len > DNAME_INLINE_LEN-1) {
950                 dname = kmalloc(name->len + 1, GFP_KERNEL);
951                 if (!dname) {
952                         kmem_cache_free(dentry_cache, dentry); 
953                         return NULL;
954                 }
955         } else  {
956                 dname = dentry->d_iname;
957         }       
958         dentry->d_name.name = dname;
959
960         dentry->d_name.len = name->len;
961         dentry->d_name.hash = name->hash;
962         memcpy(dname, name->name, name->len);
963         dname[name->len] = 0;
964
965         atomic_set(&dentry->d_count, 1);
966         dentry->d_flags = DCACHE_UNHASHED;
967         spin_lock_init(&dentry->d_lock);
968         dentry->d_inode = NULL;
969         dentry->d_parent = NULL;
970         dentry->d_sb = NULL;
971         dentry->d_op = NULL;
972         dentry->d_fsdata = NULL;
973         dentry->d_mounted = 0;
974         INIT_HLIST_NODE(&dentry->d_hash);
975         INIT_LIST_HEAD(&dentry->d_lru);
976         INIT_LIST_HEAD(&dentry->d_subdirs);
977         INIT_LIST_HEAD(&dentry->d_alias);
978
979         if (parent) {
980                 dentry->d_parent = dget(parent);
981                 dentry->d_sb = parent->d_sb;
982         } else {
983                 INIT_LIST_HEAD(&dentry->d_u.d_child);
984         }
985
986         spin_lock(&dcache_lock);
987         if (parent)
988                 list_add(&dentry->d_u.d_child, &parent->d_subdirs);
989         spin_unlock(&dcache_lock);
990
991         this_cpu_inc(nr_dentry);
992
993         return dentry;
994 }
995 EXPORT_SYMBOL(d_alloc);
996
997 struct dentry *d_alloc_name(struct dentry *parent, const char *name)
998 {
999         struct qstr q;
1000
1001         q.name = name;
1002         q.len = strlen(name);
1003         q.hash = full_name_hash(q.name, q.len);
1004         return d_alloc(parent, &q);
1005 }
1006 EXPORT_SYMBOL(d_alloc_name);
1007
1008 /* the caller must hold dcache_lock */
1009 static void __d_instantiate(struct dentry *dentry, struct inode *inode)
1010 {
1011         if (inode)
1012                 list_add(&dentry->d_alias, &inode->i_dentry);
1013         dentry->d_inode = inode;
1014         fsnotify_d_instantiate(dentry, inode);
1015 }
1016
1017 /**
1018  * d_instantiate - fill in inode information for a dentry
1019  * @entry: dentry to complete
1020  * @inode: inode to attach to this dentry
1021  *
1022  * Fill in inode information in the entry.
1023  *
1024  * This turns negative dentries into productive full members
1025  * of society.
1026  *
1027  * NOTE! This assumes that the inode count has been incremented
1028  * (or otherwise set) by the caller to indicate that it is now
1029  * in use by the dcache.
1030  */
1031  
1032 void d_instantiate(struct dentry *entry, struct inode * inode)
1033 {
1034         BUG_ON(!list_empty(&entry->d_alias));
1035         spin_lock(&dcache_lock);
1036         __d_instantiate(entry, inode);
1037         spin_unlock(&dcache_lock);
1038         security_d_instantiate(entry, inode);
1039 }
1040 EXPORT_SYMBOL(d_instantiate);
1041
1042 /**
1043  * d_instantiate_unique - instantiate a non-aliased dentry
1044  * @entry: dentry to instantiate
1045  * @inode: inode to attach to this dentry
1046  *
1047  * Fill in inode information in the entry. On success, it returns NULL.
1048  * If an unhashed alias of "entry" already exists, then we return the
1049  * aliased dentry instead and drop one reference to inode.
1050  *
1051  * Note that in order to avoid conflicts with rename() etc, the caller
1052  * had better be holding the parent directory semaphore.
1053  *
1054  * This also assumes that the inode count has been incremented
1055  * (or otherwise set) by the caller to indicate that it is now
1056  * in use by the dcache.
1057  */
1058 static struct dentry *__d_instantiate_unique(struct dentry *entry,
1059                                              struct inode *inode)
1060 {
1061         struct dentry *alias;
1062         int len = entry->d_name.len;
1063         const char *name = entry->d_name.name;
1064         unsigned int hash = entry->d_name.hash;
1065
1066         if (!inode) {
1067                 __d_instantiate(entry, NULL);
1068                 return NULL;
1069         }
1070
1071         list_for_each_entry(alias, &inode->i_dentry, d_alias) {
1072                 struct qstr *qstr = &alias->d_name;
1073
1074                 if (qstr->hash != hash)
1075                         continue;
1076                 if (alias->d_parent != entry->d_parent)
1077                         continue;
1078                 if (qstr->len != len)
1079                         continue;
1080                 if (memcmp(qstr->name, name, len))
1081                         continue;
1082                 dget_locked(alias);
1083                 return alias;
1084         }
1085
1086         __d_instantiate(entry, inode);
1087         return NULL;
1088 }
1089
1090 struct dentry *d_instantiate_unique(struct dentry *entry, struct inode *inode)
1091 {
1092         struct dentry *result;
1093
1094         BUG_ON(!list_empty(&entry->d_alias));
1095
1096         spin_lock(&dcache_lock);
1097         result = __d_instantiate_unique(entry, inode);
1098         spin_unlock(&dcache_lock);
1099
1100         if (!result) {
1101                 security_d_instantiate(entry, inode);
1102                 return NULL;
1103         }
1104
1105         BUG_ON(!d_unhashed(result));
1106         iput(inode);
1107         return result;
1108 }
1109
1110 EXPORT_SYMBOL(d_instantiate_unique);
1111
1112 /**
1113  * d_alloc_root - allocate root dentry
1114  * @root_inode: inode to allocate the root for
1115  *
1116  * Allocate a root ("/") dentry for the inode given. The inode is
1117  * instantiated and returned. %NULL is returned if there is insufficient
1118  * memory or the inode passed is %NULL.
1119  */
1120  
1121 struct dentry * d_alloc_root(struct inode * root_inode)
1122 {
1123         struct dentry *res = NULL;
1124
1125         if (root_inode) {
1126                 static const struct qstr name = { .name = "/", .len = 1 };
1127
1128                 res = d_alloc(NULL, &name);
1129                 if (res) {
1130                         res->d_sb = root_inode->i_sb;
1131                         res->d_parent = res;
1132                         d_instantiate(res, root_inode);
1133                 }
1134         }
1135         return res;
1136 }
1137 EXPORT_SYMBOL(d_alloc_root);
1138
1139 static inline struct hlist_head *d_hash(struct dentry *parent,
1140                                         unsigned long hash)
1141 {
1142         hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
1143         hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
1144         return dentry_hashtable + (hash & D_HASHMASK);
1145 }
1146
1147 /**
1148  * d_obtain_alias - find or allocate a dentry for a given inode
1149  * @inode: inode to allocate the dentry for
1150  *
1151  * Obtain a dentry for an inode resulting from NFS filehandle conversion or
1152  * similar open by handle operations.  The returned dentry may be anonymous,
1153  * or may have a full name (if the inode was already in the cache).
1154  *
1155  * When called on a directory inode, we must ensure that the inode only ever
1156  * has one dentry.  If a dentry is found, that is returned instead of
1157  * allocating a new one.
1158  *
1159  * On successful return, the reference to the inode has been transferred
1160  * to the dentry.  In case of an error the reference on the inode is released.
1161  * To make it easier to use in export operations a %NULL or IS_ERR inode may
1162  * be passed in and will be the error will be propagate to the return value,
1163  * with a %NULL @inode replaced by ERR_PTR(-ESTALE).
1164  */
1165 struct dentry *d_obtain_alias(struct inode *inode)
1166 {
1167         static const struct qstr anonstring = { .name = "" };
1168         struct dentry *tmp;
1169         struct dentry *res;
1170
1171         if (!inode)
1172                 return ERR_PTR(-ESTALE);
1173         if (IS_ERR(inode))
1174                 return ERR_CAST(inode);
1175
1176         res = d_find_alias(inode);
1177         if (res)
1178                 goto out_iput;
1179
1180         tmp = d_alloc(NULL, &anonstring);
1181         if (!tmp) {
1182                 res = ERR_PTR(-ENOMEM);
1183                 goto out_iput;
1184         }
1185         tmp->d_parent = tmp; /* make sure dput doesn't croak */
1186
1187         spin_lock(&dcache_lock);
1188         res = __d_find_alias(inode, 0);
1189         if (res) {
1190                 spin_unlock(&dcache_lock);
1191                 dput(tmp);
1192                 goto out_iput;
1193         }
1194
1195         /* attach a disconnected dentry */
1196         spin_lock(&tmp->d_lock);
1197         tmp->d_sb = inode->i_sb;
1198         tmp->d_inode = inode;
1199         tmp->d_flags |= DCACHE_DISCONNECTED;
1200         tmp->d_flags &= ~DCACHE_UNHASHED;
1201         list_add(&tmp->d_alias, &inode->i_dentry);
1202         hlist_add_head(&tmp->d_hash, &inode->i_sb->s_anon);
1203         spin_unlock(&tmp->d_lock);
1204
1205         spin_unlock(&dcache_lock);
1206         return tmp;
1207
1208  out_iput:
1209         iput(inode);
1210         return res;
1211 }
1212 EXPORT_SYMBOL(d_obtain_alias);
1213
1214 /**
1215  * d_splice_alias - splice a disconnected dentry into the tree if one exists
1216  * @inode:  the inode which may have a disconnected dentry
1217  * @dentry: a negative dentry which we want to point to the inode.
1218  *
1219  * If inode is a directory and has a 'disconnected' dentry (i.e. IS_ROOT and
1220  * DCACHE_DISCONNECTED), then d_move that in place of the given dentry
1221  * and return it, else simply d_add the inode to the dentry and return NULL.
1222  *
1223  * This is needed in the lookup routine of any filesystem that is exportable
1224  * (via knfsd) so that we can build dcache paths to directories effectively.
1225  *
1226  * If a dentry was found and moved, then it is returned.  Otherwise NULL
1227  * is returned.  This matches the expected return value of ->lookup.
1228  *
1229  */
1230 struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
1231 {
1232         struct dentry *new = NULL;
1233
1234         if (inode && S_ISDIR(inode->i_mode)) {
1235                 spin_lock(&dcache_lock);
1236                 new = __d_find_alias(inode, 1);
1237                 if (new) {
1238                         BUG_ON(!(new->d_flags & DCACHE_DISCONNECTED));
1239                         spin_unlock(&dcache_lock);
1240                         security_d_instantiate(new, inode);
1241                         d_move(new, dentry);
1242                         iput(inode);
1243                 } else {
1244                         /* already taking dcache_lock, so d_add() by hand */
1245                         __d_instantiate(dentry, inode);
1246                         spin_unlock(&dcache_lock);
1247                         security_d_instantiate(dentry, inode);
1248                         d_rehash(dentry);
1249                 }
1250         } else
1251                 d_add(dentry, inode);
1252         return new;
1253 }
1254 EXPORT_SYMBOL(d_splice_alias);
1255
1256 /**
1257  * d_add_ci - lookup or allocate new dentry with case-exact name
1258  * @inode:  the inode case-insensitive lookup has found
1259  * @dentry: the negative dentry that was passed to the parent's lookup func
1260  * @name:   the case-exact name to be associated with the returned dentry
1261  *
1262  * This is to avoid filling the dcache with case-insensitive names to the
1263  * same inode, only the actual correct case is stored in the dcache for
1264  * case-insensitive filesystems.
1265  *
1266  * For a case-insensitive lookup match and if the the case-exact dentry
1267  * already exists in in the dcache, use it and return it.
1268  *
1269  * If no entry exists with the exact case name, allocate new dentry with
1270  * the exact case, and return the spliced entry.
1271  */
1272 struct dentry *d_add_ci(struct dentry *dentry, struct inode *inode,
1273                         struct qstr *name)
1274 {
1275         int error;
1276         struct dentry *found;
1277         struct dentry *new;
1278
1279         /*
1280          * First check if a dentry matching the name already exists,
1281          * if not go ahead and create it now.
1282          */
1283         found = d_hash_and_lookup(dentry->d_parent, name);
1284         if (!found) {
1285                 new = d_alloc(dentry->d_parent, name);
1286                 if (!new) {
1287                         error = -ENOMEM;
1288                         goto err_out;
1289                 }
1290
1291                 found = d_splice_alias(inode, new);
1292                 if (found) {
1293                         dput(new);
1294                         return found;
1295                 }
1296                 return new;
1297         }
1298
1299         /*
1300          * If a matching dentry exists, and it's not negative use it.
1301          *
1302          * Decrement the reference count to balance the iget() done
1303          * earlier on.
1304          */
1305         if (found->d_inode) {
1306                 if (unlikely(found->d_inode != inode)) {
1307                         /* This can't happen because bad inodes are unhashed. */
1308                         BUG_ON(!is_bad_inode(inode));
1309                         BUG_ON(!is_bad_inode(found->d_inode));
1310                 }
1311                 iput(inode);
1312                 return found;
1313         }
1314
1315         /*
1316          * Negative dentry: instantiate it unless the inode is a directory and
1317          * already has a dentry.
1318          */
1319         spin_lock(&dcache_lock);
1320         if (!S_ISDIR(inode->i_mode) || list_empty(&inode->i_dentry)) {
1321                 __d_instantiate(found, inode);
1322                 spin_unlock(&dcache_lock);
1323                 security_d_instantiate(found, inode);
1324                 return found;
1325         }
1326
1327         /*
1328          * In case a directory already has a (disconnected) entry grab a
1329          * reference to it, move it in place and use it.
1330          */
1331         new = list_entry(inode->i_dentry.next, struct dentry, d_alias);
1332         dget_locked(new);
1333         spin_unlock(&dcache_lock);
1334         security_d_instantiate(found, inode);
1335         d_move(new, found);
1336         iput(inode);
1337         dput(found);
1338         return new;
1339
1340 err_out:
1341         iput(inode);
1342         return ERR_PTR(error);
1343 }
1344 EXPORT_SYMBOL(d_add_ci);
1345
1346 /**
1347  * d_lookup - search for a dentry
1348  * @parent: parent dentry
1349  * @name: qstr of name we wish to find
1350  * Returns: dentry, or NULL
1351  *
1352  * d_lookup searches the children of the parent dentry for the name in
1353  * question. If the dentry is found its reference count is incremented and the
1354  * dentry is returned. The caller must use dput to free the entry when it has
1355  * finished using it. %NULL is returned if the dentry does not exist.
1356  */
1357 struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
1358 {
1359         struct dentry * dentry = NULL;
1360         unsigned long seq;
1361
1362         do {
1363                 seq = read_seqbegin(&rename_lock);
1364                 dentry = __d_lookup(parent, name);
1365                 if (dentry)
1366                         break;
1367         } while (read_seqretry(&rename_lock, seq));
1368         return dentry;
1369 }
1370 EXPORT_SYMBOL(d_lookup);
1371
1372 /*
1373  * __d_lookup - search for a dentry (racy)
1374  * @parent: parent dentry
1375  * @name: qstr of name we wish to find
1376  * Returns: dentry, or NULL
1377  *
1378  * __d_lookup is like d_lookup, however it may (rarely) return a
1379  * false-negative result due to unrelated rename activity.
1380  *
1381  * __d_lookup is slightly faster by avoiding rename_lock read seqlock,
1382  * however it must be used carefully, eg. with a following d_lookup in
1383  * the case of failure.
1384  *
1385  * __d_lookup callers must be commented.
1386  */
1387 struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
1388 {
1389         unsigned int len = name->len;
1390         unsigned int hash = name->hash;
1391         const unsigned char *str = name->name;
1392         struct hlist_head *head = d_hash(parent,hash);
1393         struct dentry *found = NULL;
1394         struct hlist_node *node;
1395         struct dentry *dentry;
1396
1397         /*
1398          * The hash list is protected using RCU.
1399          *
1400          * Take d_lock when comparing a candidate dentry, to avoid races
1401          * with d_move().
1402          *
1403          * It is possible that concurrent renames can mess up our list
1404          * walk here and result in missing our dentry, resulting in the
1405          * false-negative result. d_lookup() protects against concurrent
1406          * renames using rename_lock seqlock.
1407          *
1408          * See Documentation/vfs/dcache-locking.txt for more details.
1409          */
1410         rcu_read_lock();
1411         
1412         hlist_for_each_entry_rcu(dentry, node, head, d_hash) {
1413                 struct qstr *qstr;
1414
1415                 if (dentry->d_name.hash != hash)
1416                         continue;
1417                 if (dentry->d_parent != parent)
1418                         continue;
1419
1420                 spin_lock(&dentry->d_lock);
1421
1422                 /*
1423                  * Recheck the dentry after taking the lock - d_move may have
1424                  * changed things. Don't bother checking the hash because
1425                  * we're about to compare the whole name anyway.
1426                  */
1427                 if (dentry->d_parent != parent)
1428                         goto next;
1429
1430                 /* non-existing due to RCU? */
1431                 if (d_unhashed(dentry))
1432                         goto next;
1433
1434                 /*
1435                  * It is safe to compare names since d_move() cannot
1436                  * change the qstr (protected by d_lock).
1437                  */
1438                 qstr = &dentry->d_name;
1439                 if (parent->d_op && parent->d_op->d_compare) {
1440                         if (parent->d_op->d_compare(parent, parent->d_inode,
1441                                                 dentry, dentry->d_inode,
1442                                                 qstr->len, qstr->name, 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  * dentry_update_name_case - update case insensitive dentry with a new name
1596  * @dentry: dentry to be updated
1597  * @name: new name
1598  *
1599  * Update a case insensitive dentry with new case of name.
1600  *
1601  * dentry must have been returned by d_lookup with name @name. Old and new
1602  * name lengths must match (ie. no d_compare which allows mismatched name
1603  * lengths).
1604  *
1605  * Parent inode i_mutex must be held over d_lookup and into this call (to
1606  * keep renames and concurrent inserts, and readdir(2) away).
1607  */
1608 void dentry_update_name_case(struct dentry *dentry, struct qstr *name)
1609 {
1610         BUG_ON(!mutex_is_locked(&dentry->d_inode->i_mutex));
1611         BUG_ON(dentry->d_name.len != name->len); /* d_lookup gives this */
1612
1613         spin_lock(&dcache_lock);
1614         spin_lock(&dentry->d_lock);
1615         memcpy((unsigned char *)dentry->d_name.name, name->name, name->len);
1616         spin_unlock(&dentry->d_lock);
1617         spin_unlock(&dcache_lock);
1618 }
1619 EXPORT_SYMBOL(dentry_update_name_case);
1620
1621 /*
1622  * When switching names, the actual string doesn't strictly have to
1623  * be preserved in the target - because we're dropping the target
1624  * anyway. As such, we can just do a simple memcpy() to copy over
1625  * the new name before we switch.
1626  *
1627  * Note that we have to be a lot more careful about getting the hash
1628  * switched - we have to switch the hash value properly even if it
1629  * then no longer matches the actual (corrupted) string of the target.
1630  * The hash value has to match the hash queue that the dentry is on..
1631  */
1632 static void switch_names(struct dentry *dentry, struct dentry *target)
1633 {
1634         if (dname_external(target)) {
1635                 if (dname_external(dentry)) {
1636                         /*
1637                          * Both external: swap the pointers
1638                          */
1639                         swap(target->d_name.name, dentry->d_name.name);
1640                 } else {
1641                         /*
1642                          * dentry:internal, target:external.  Steal target's
1643                          * storage and make target internal.
1644                          */
1645                         memcpy(target->d_iname, dentry->d_name.name,
1646                                         dentry->d_name.len + 1);
1647                         dentry->d_name.name = target->d_name.name;
1648                         target->d_name.name = target->d_iname;
1649                 }
1650         } else {
1651                 if (dname_external(dentry)) {
1652                         /*
1653                          * dentry:external, target:internal.  Give dentry's
1654                          * storage to target and make dentry internal
1655                          */
1656                         memcpy(dentry->d_iname, target->d_name.name,
1657                                         target->d_name.len + 1);
1658                         target->d_name.name = dentry->d_name.name;
1659                         dentry->d_name.name = dentry->d_iname;
1660                 } else {
1661                         /*
1662                          * Both are internal.  Just copy target to dentry
1663                          */
1664                         memcpy(dentry->d_iname, target->d_name.name,
1665                                         target->d_name.len + 1);
1666                         dentry->d_name.len = target->d_name.len;
1667                         return;
1668                 }
1669         }
1670         swap(dentry->d_name.len, target->d_name.len);
1671 }
1672
1673 /*
1674  * We cannibalize "target" when moving dentry on top of it,
1675  * because it's going to be thrown away anyway. We could be more
1676  * polite about it, though.
1677  *
1678  * This forceful removal will result in ugly /proc output if
1679  * somebody holds a file open that got deleted due to a rename.
1680  * We could be nicer about the deleted file, and let it show
1681  * up under the name it had before it was deleted rather than
1682  * under the original name of the file that was moved on top of it.
1683  */
1684  
1685 /*
1686  * d_move_locked - move a dentry
1687  * @dentry: entry to move
1688  * @target: new dentry
1689  *
1690  * Update the dcache to reflect the move of a file name. Negative
1691  * dcache entries should not be moved in this way.
1692  */
1693 static void d_move_locked(struct dentry * dentry, struct dentry * target)
1694 {
1695         struct hlist_head *list;
1696
1697         if (!dentry->d_inode)
1698                 printk(KERN_WARNING "VFS: moving negative dcache entry\n");
1699
1700         write_seqlock(&rename_lock);
1701         /*
1702          * XXXX: do we really need to take target->d_lock?
1703          */
1704         if (target < dentry) {
1705                 spin_lock(&target->d_lock);
1706                 spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
1707         } else {
1708                 spin_lock(&dentry->d_lock);
1709                 spin_lock_nested(&target->d_lock, DENTRY_D_LOCK_NESTED);
1710         }
1711
1712         /* Move the dentry to the target hash queue, if on different bucket */
1713         if (d_unhashed(dentry))
1714                 goto already_unhashed;
1715
1716         hlist_del_rcu(&dentry->d_hash);
1717
1718 already_unhashed:
1719         list = d_hash(target->d_parent, target->d_name.hash);
1720         __d_rehash(dentry, list);
1721
1722         /* Unhash the target: dput() will then get rid of it */
1723         __d_drop(target);
1724
1725         list_del(&dentry->d_u.d_child);
1726         list_del(&target->d_u.d_child);
1727
1728         /* Switch the names.. */
1729         switch_names(dentry, target);
1730         swap(dentry->d_name.hash, target->d_name.hash);
1731
1732         /* ... and switch the parents */
1733         if (IS_ROOT(dentry)) {
1734                 dentry->d_parent = target->d_parent;
1735                 target->d_parent = target;
1736                 INIT_LIST_HEAD(&target->d_u.d_child);
1737         } else {
1738                 swap(dentry->d_parent, target->d_parent);
1739
1740                 /* And add them back to the (new) parent lists */
1741                 list_add(&target->d_u.d_child, &target->d_parent->d_subdirs);
1742         }
1743
1744         list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
1745         spin_unlock(&target->d_lock);
1746         fsnotify_d_move(dentry);
1747         spin_unlock(&dentry->d_lock);
1748         write_sequnlock(&rename_lock);
1749 }
1750
1751 /**
1752  * d_move - move a dentry
1753  * @dentry: entry to move
1754  * @target: new dentry
1755  *
1756  * Update the dcache to reflect the move of a file name. Negative
1757  * dcache entries should not be moved in this way.
1758  */
1759
1760 void d_move(struct dentry * dentry, struct dentry * target)
1761 {
1762         spin_lock(&dcache_lock);
1763         d_move_locked(dentry, target);
1764         spin_unlock(&dcache_lock);
1765 }
1766 EXPORT_SYMBOL(d_move);
1767
1768 /**
1769  * d_ancestor - search for an ancestor
1770  * @p1: ancestor dentry
1771  * @p2: child dentry
1772  *
1773  * Returns the ancestor dentry of p2 which is a child of p1, if p1 is
1774  * an ancestor of p2, else NULL.
1775  */
1776 struct dentry *d_ancestor(struct dentry *p1, struct dentry *p2)
1777 {
1778         struct dentry *p;
1779
1780         for (p = p2; !IS_ROOT(p); p = p->d_parent) {
1781                 if (p->d_parent == p1)
1782                         return p;
1783         }
1784         return NULL;
1785 }
1786
1787 /*
1788  * This helper attempts to cope with remotely renamed directories
1789  *
1790  * It assumes that the caller is already holding
1791  * dentry->d_parent->d_inode->i_mutex and the dcache_lock
1792  *
1793  * Note: If ever the locking in lock_rename() changes, then please
1794  * remember to update this too...
1795  */
1796 static struct dentry *__d_unalias(struct dentry *dentry, struct dentry *alias)
1797         __releases(dcache_lock)
1798 {
1799         struct mutex *m1 = NULL, *m2 = NULL;
1800         struct dentry *ret;
1801
1802         /* If alias and dentry share a parent, then no extra locks required */
1803         if (alias->d_parent == dentry->d_parent)
1804                 goto out_unalias;
1805
1806         /* Check for loops */
1807         ret = ERR_PTR(-ELOOP);
1808         if (d_ancestor(alias, dentry))
1809                 goto out_err;
1810
1811         /* See lock_rename() */
1812         ret = ERR_PTR(-EBUSY);
1813         if (!mutex_trylock(&dentry->d_sb->s_vfs_rename_mutex))
1814                 goto out_err;
1815         m1 = &dentry->d_sb->s_vfs_rename_mutex;
1816         if (!mutex_trylock(&alias->d_parent->d_inode->i_mutex))
1817                 goto out_err;
1818         m2 = &alias->d_parent->d_inode->i_mutex;
1819 out_unalias:
1820         d_move_locked(alias, dentry);
1821         ret = alias;
1822 out_err:
1823         spin_unlock(&dcache_lock);
1824         if (m2)
1825                 mutex_unlock(m2);
1826         if (m1)
1827                 mutex_unlock(m1);
1828         return ret;
1829 }
1830
1831 /*
1832  * Prepare an anonymous dentry for life in the superblock's dentry tree as a
1833  * named dentry in place of the dentry to be replaced.
1834  */
1835 static void __d_materialise_dentry(struct dentry *dentry, struct dentry *anon)
1836 {
1837         struct dentry *dparent, *aparent;
1838
1839         switch_names(dentry, anon);
1840         swap(dentry->d_name.hash, anon->d_name.hash);
1841
1842         dparent = dentry->d_parent;
1843         aparent = anon->d_parent;
1844
1845         dentry->d_parent = (aparent == anon) ? dentry : aparent;
1846         list_del(&dentry->d_u.d_child);
1847         if (!IS_ROOT(dentry))
1848                 list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
1849         else
1850                 INIT_LIST_HEAD(&dentry->d_u.d_child);
1851
1852         anon->d_parent = (dparent == dentry) ? anon : dparent;
1853         list_del(&anon->d_u.d_child);
1854         if (!IS_ROOT(anon))
1855                 list_add(&anon->d_u.d_child, &anon->d_parent->d_subdirs);
1856         else
1857                 INIT_LIST_HEAD(&anon->d_u.d_child);
1858
1859         anon->d_flags &= ~DCACHE_DISCONNECTED;
1860 }
1861
1862 /**
1863  * d_materialise_unique - introduce an inode into the tree
1864  * @dentry: candidate dentry
1865  * @inode: inode to bind to the dentry, to which aliases may be attached
1866  *
1867  * Introduces an dentry into the tree, substituting an extant disconnected
1868  * root directory alias in its place if there is one
1869  */
1870 struct dentry *d_materialise_unique(struct dentry *dentry, struct inode *inode)
1871 {
1872         struct dentry *actual;
1873
1874         BUG_ON(!d_unhashed(dentry));
1875
1876         spin_lock(&dcache_lock);
1877
1878         if (!inode) {
1879                 actual = dentry;
1880                 __d_instantiate(dentry, NULL);
1881                 goto found_lock;
1882         }
1883
1884         if (S_ISDIR(inode->i_mode)) {
1885                 struct dentry *alias;
1886
1887                 /* Does an aliased dentry already exist? */
1888                 alias = __d_find_alias(inode, 0);
1889                 if (alias) {
1890                         actual = alias;
1891                         /* Is this an anonymous mountpoint that we could splice
1892                          * into our tree? */
1893                         if (IS_ROOT(alias)) {
1894                                 spin_lock(&alias->d_lock);
1895                                 __d_materialise_dentry(dentry, alias);
1896                                 __d_drop(alias);
1897                                 goto found;
1898                         }
1899                         /* Nope, but we must(!) avoid directory aliasing */
1900                         actual = __d_unalias(dentry, alias);
1901                         if (IS_ERR(actual))
1902                                 dput(alias);
1903                         goto out_nolock;
1904                 }
1905         }
1906
1907         /* Add a unique reference */
1908         actual = __d_instantiate_unique(dentry, inode);
1909         if (!actual)
1910                 actual = dentry;
1911         else if (unlikely(!d_unhashed(actual)))
1912                 goto shouldnt_be_hashed;
1913
1914 found_lock:
1915         spin_lock(&actual->d_lock);
1916 found:
1917         _d_rehash(actual);
1918         spin_unlock(&actual->d_lock);
1919         spin_unlock(&dcache_lock);
1920 out_nolock:
1921         if (actual == dentry) {
1922                 security_d_instantiate(dentry, inode);
1923                 return NULL;
1924         }
1925
1926         iput(inode);
1927         return actual;
1928
1929 shouldnt_be_hashed:
1930         spin_unlock(&dcache_lock);
1931         BUG();
1932 }
1933 EXPORT_SYMBOL_GPL(d_materialise_unique);
1934
1935 static int prepend(char **buffer, int *buflen, const char *str, int namelen)
1936 {
1937         *buflen -= namelen;
1938         if (*buflen < 0)
1939                 return -ENAMETOOLONG;
1940         *buffer -= namelen;
1941         memcpy(*buffer, str, namelen);
1942         return 0;
1943 }
1944
1945 static int prepend_name(char **buffer, int *buflen, struct qstr *name)
1946 {
1947         return prepend(buffer, buflen, name->name, name->len);
1948 }
1949
1950 /**
1951  * Prepend path string to a buffer
1952  *
1953  * @path: the dentry/vfsmount to report
1954  * @root: root vfsmnt/dentry (may be modified by this function)
1955  * @buffer: pointer to the end of the buffer
1956  * @buflen: pointer to buffer length
1957  *
1958  * Caller holds the dcache_lock.
1959  *
1960  * If path is not reachable from the supplied root, then the value of
1961  * root is changed (without modifying refcounts).
1962  */
1963 static int prepend_path(const struct path *path, struct path *root,
1964                         char **buffer, int *buflen)
1965 {
1966         struct dentry *dentry = path->dentry;
1967         struct vfsmount *vfsmnt = path->mnt;
1968         bool slash = false;
1969         int error = 0;
1970
1971         br_read_lock(vfsmount_lock);
1972         while (dentry != root->dentry || vfsmnt != root->mnt) {
1973                 struct dentry * parent;
1974
1975                 if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
1976                         /* Global root? */
1977                         if (vfsmnt->mnt_parent == vfsmnt) {
1978                                 goto global_root;
1979                         }
1980                         dentry = vfsmnt->mnt_mountpoint;
1981                         vfsmnt = vfsmnt->mnt_parent;
1982                         continue;
1983                 }
1984                 parent = dentry->d_parent;
1985                 prefetch(parent);
1986                 error = prepend_name(buffer, buflen, &dentry->d_name);
1987                 if (!error)
1988                         error = prepend(buffer, buflen, "/", 1);
1989                 if (error)
1990                         break;
1991
1992                 slash = true;
1993                 dentry = parent;
1994         }
1995
1996 out:
1997         if (!error && !slash)
1998                 error = prepend(buffer, buflen, "/", 1);
1999
2000         br_read_unlock(vfsmount_lock);
2001         return error;
2002
2003 global_root:
2004         /*
2005          * Filesystems needing to implement special "root names"
2006          * should do so with ->d_dname()
2007          */
2008         if (IS_ROOT(dentry) &&
2009             (dentry->d_name.len != 1 || dentry->d_name.name[0] != '/')) {
2010                 WARN(1, "Root dentry has weird name <%.*s>\n",
2011                      (int) dentry->d_name.len, dentry->d_name.name);
2012         }
2013         root->mnt = vfsmnt;
2014         root->dentry = dentry;
2015         goto out;
2016 }
2017
2018 /**
2019  * __d_path - return the path of a dentry
2020  * @path: the dentry/vfsmount to report
2021  * @root: root vfsmnt/dentry (may be modified by this function)
2022  * @buf: buffer to return value in
2023  * @buflen: buffer length
2024  *
2025  * Convert a dentry into an ASCII path name.
2026  *
2027  * Returns a pointer into the buffer or an error code if the
2028  * path was too long.
2029  *
2030  * "buflen" should be positive.
2031  *
2032  * If path is not reachable from the supplied root, then the value of
2033  * root is changed (without modifying refcounts).
2034  */
2035 char *__d_path(const struct path *path, struct path *root,
2036                char *buf, int buflen)
2037 {
2038         char *res = buf + buflen;
2039         int error;
2040
2041         prepend(&res, &buflen, "\0", 1);
2042         spin_lock(&dcache_lock);
2043         error = prepend_path(path, root, &res, &buflen);
2044         spin_unlock(&dcache_lock);
2045
2046         if (error)
2047                 return ERR_PTR(error);
2048         return res;
2049 }
2050
2051 /*
2052  * same as __d_path but appends "(deleted)" for unlinked files.
2053  */
2054 static int path_with_deleted(const struct path *path, struct path *root,
2055                                  char **buf, int *buflen)
2056 {
2057         prepend(buf, buflen, "\0", 1);
2058         if (d_unlinked(path->dentry)) {
2059                 int error = prepend(buf, buflen, " (deleted)", 10);
2060                 if (error)
2061                         return error;
2062         }
2063
2064         return prepend_path(path, root, buf, buflen);
2065 }
2066
2067 static int prepend_unreachable(char **buffer, int *buflen)
2068 {
2069         return prepend(buffer, buflen, "(unreachable)", 13);
2070 }
2071
2072 /**
2073  * d_path - return the path of a dentry
2074  * @path: path to report
2075  * @buf: buffer to return value in
2076  * @buflen: buffer length
2077  *
2078  * Convert a dentry into an ASCII path name. If the entry has been deleted
2079  * the string " (deleted)" is appended. Note that this is ambiguous.
2080  *
2081  * Returns a pointer into the buffer or an error code if the path was
2082  * too long. Note: Callers should use the returned pointer, not the passed
2083  * in buffer, to use the name! The implementation often starts at an offset
2084  * into the buffer, and may leave 0 bytes at the start.
2085  *
2086  * "buflen" should be positive.
2087  */
2088 char *d_path(const struct path *path, char *buf, int buflen)
2089 {
2090         char *res = buf + buflen;
2091         struct path root;
2092         struct path tmp;
2093         int error;
2094
2095         /*
2096          * We have various synthetic filesystems that never get mounted.  On
2097          * these filesystems dentries are never used for lookup purposes, and
2098          * thus don't need to be hashed.  They also don't need a name until a
2099          * user wants to identify the object in /proc/pid/fd/.  The little hack
2100          * below allows us to generate a name for these objects on demand:
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)
2110                 res = ERR_PTR(error);
2111         spin_unlock(&dcache_lock);
2112         path_put(&root);
2113         return res;
2114 }
2115 EXPORT_SYMBOL(d_path);
2116
2117 /**
2118  * d_path_with_unreachable - return the path of a dentry
2119  * @path: path to report
2120  * @buf: buffer to return value in
2121  * @buflen: buffer length
2122  *
2123  * The difference from d_path() is that this prepends "(unreachable)"
2124  * to paths which are unreachable from the current process' root.
2125  */
2126 char *d_path_with_unreachable(const struct path *path, char *buf, int buflen)
2127 {
2128         char *res = buf + buflen;
2129         struct path root;
2130         struct path tmp;
2131         int error;
2132
2133         if (path->dentry->d_op && path->dentry->d_op->d_dname)
2134                 return path->dentry->d_op->d_dname(path->dentry, buf, buflen);
2135
2136         get_fs_root(current->fs, &root);
2137         spin_lock(&dcache_lock);
2138         tmp = root;
2139         error = path_with_deleted(path, &tmp, &res, &buflen);
2140         if (!error && !path_equal(&tmp, &root))
2141                 error = prepend_unreachable(&res, &buflen);
2142         spin_unlock(&dcache_lock);
2143         path_put(&root);
2144         if (error)
2145                 res =  ERR_PTR(error);
2146
2147         return res;
2148 }
2149
2150 /*
2151  * Helper function for dentry_operations.d_dname() members
2152  */
2153 char *dynamic_dname(struct dentry *dentry, char *buffer, int buflen,
2154                         const char *fmt, ...)
2155 {
2156         va_list args;
2157         char temp[64];
2158         int sz;
2159
2160         va_start(args, fmt);
2161         sz = vsnprintf(temp, sizeof(temp), fmt, args) + 1;
2162         va_end(args);
2163
2164         if (sz > sizeof(temp) || sz > buflen)
2165                 return ERR_PTR(-ENAMETOOLONG);
2166
2167         buffer += buflen - sz;
2168         return memcpy(buffer, temp, sz);
2169 }
2170
2171 /*
2172  * Write full pathname from the root of the filesystem into the buffer.
2173  */
2174 char *__dentry_path(struct dentry *dentry, char *buf, int buflen)
2175 {
2176         char *end = buf + buflen;
2177         char *retval;
2178
2179         prepend(&end, &buflen, "\0", 1);
2180         if (buflen < 1)
2181                 goto Elong;
2182         /* Get '/' right */
2183         retval = end-1;
2184         *retval = '/';
2185
2186         while (!IS_ROOT(dentry)) {
2187                 struct dentry *parent = dentry->d_parent;
2188
2189                 prefetch(parent);
2190                 if ((prepend_name(&end, &buflen, &dentry->d_name) != 0) ||
2191                     (prepend(&end, &buflen, "/", 1) != 0))
2192                         goto Elong;
2193
2194                 retval = end;
2195                 dentry = parent;
2196         }
2197         return retval;
2198 Elong:
2199         return ERR_PTR(-ENAMETOOLONG);
2200 }
2201 EXPORT_SYMBOL(__dentry_path);
2202
2203 char *dentry_path(struct dentry *dentry, char *buf, int buflen)
2204 {
2205         char *p = NULL;
2206         char *retval;
2207
2208         spin_lock(&dcache_lock);
2209         if (d_unlinked(dentry)) {
2210                 p = buf + buflen;
2211                 if (prepend(&p, &buflen, "//deleted", 10) != 0)
2212                         goto Elong;
2213                 buflen++;
2214         }
2215         retval = __dentry_path(dentry, buf, buflen);
2216         spin_unlock(&dcache_lock);
2217         if (!IS_ERR(retval) && p)
2218                 *p = '/';       /* restore '/' overriden with '\0' */
2219         return retval;
2220 Elong:
2221         spin_unlock(&dcache_lock);
2222         return ERR_PTR(-ENAMETOOLONG);
2223 }
2224
2225 /*
2226  * NOTE! The user-level library version returns a
2227  * character pointer. The kernel system call just
2228  * returns the length of the buffer filled (which
2229  * includes the ending '\0' character), or a negative
2230  * error value. So libc would do something like
2231  *
2232  *      char *getcwd(char * buf, size_t size)
2233  *      {
2234  *              int retval;
2235  *
2236  *              retval = sys_getcwd(buf, size);
2237  *              if (retval >= 0)
2238  *                      return buf;
2239  *              errno = -retval;
2240  *              return NULL;
2241  *      }
2242  */
2243 SYSCALL_DEFINE2(getcwd, char __user *, buf, unsigned long, size)
2244 {
2245         int error;
2246         struct path pwd, root;
2247         char *page = (char *) __get_free_page(GFP_USER);
2248
2249         if (!page)
2250                 return -ENOMEM;
2251
2252         get_fs_root_and_pwd(current->fs, &root, &pwd);
2253
2254         error = -ENOENT;
2255         spin_lock(&dcache_lock);
2256         if (!d_unlinked(pwd.dentry)) {
2257                 unsigned long len;
2258                 struct path tmp = root;
2259                 char *cwd = page + PAGE_SIZE;
2260                 int buflen = PAGE_SIZE;
2261
2262                 prepend(&cwd, &buflen, "\0", 1);
2263                 error = prepend_path(&pwd, &tmp, &cwd, &buflen);
2264                 spin_unlock(&dcache_lock);
2265
2266                 if (error)
2267                         goto out;
2268
2269                 /* Unreachable from current root */
2270                 if (!path_equal(&tmp, &root)) {
2271                         error = prepend_unreachable(&cwd, &buflen);
2272                         if (error)
2273                                 goto out;
2274                 }
2275
2276                 error = -ERANGE;
2277                 len = PAGE_SIZE + page - cwd;
2278                 if (len <= size) {
2279                         error = len;
2280                         if (copy_to_user(buf, cwd, len))
2281                                 error = -EFAULT;
2282                 }
2283         } else
2284                 spin_unlock(&dcache_lock);
2285
2286 out:
2287         path_put(&pwd);
2288         path_put(&root);
2289         free_page((unsigned long) page);
2290         return error;
2291 }
2292
2293 /*
2294  * Test whether new_dentry is a subdirectory of old_dentry.
2295  *
2296  * Trivially implemented using the dcache structure
2297  */
2298
2299 /**
2300  * is_subdir - is new dentry a subdirectory of old_dentry
2301  * @new_dentry: new dentry
2302  * @old_dentry: old dentry
2303  *
2304  * Returns 1 if new_dentry is a subdirectory of the parent (at any depth).
2305  * Returns 0 otherwise.
2306  * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
2307  */
2308   
2309 int is_subdir(struct dentry *new_dentry, struct dentry *old_dentry)
2310 {
2311         int result;
2312         unsigned long seq;
2313
2314         if (new_dentry == old_dentry)
2315                 return 1;
2316
2317         /*
2318          * Need rcu_readlock to protect against the d_parent trashing
2319          * due to d_move
2320          */
2321         rcu_read_lock();
2322         do {
2323                 /* for restarting inner loop in case of seq retry */
2324                 seq = read_seqbegin(&rename_lock);
2325                 if (d_ancestor(old_dentry, new_dentry))
2326                         result = 1;
2327                 else
2328                         result = 0;
2329         } while (read_seqretry(&rename_lock, seq));
2330         rcu_read_unlock();
2331
2332         return result;
2333 }
2334
2335 int path_is_under(struct path *path1, struct path *path2)
2336 {
2337         struct vfsmount *mnt = path1->mnt;
2338         struct dentry *dentry = path1->dentry;
2339         int res;
2340
2341         br_read_lock(vfsmount_lock);
2342         if (mnt != path2->mnt) {
2343                 for (;;) {
2344                         if (mnt->mnt_parent == mnt) {
2345                                 br_read_unlock(vfsmount_lock);
2346                                 return 0;
2347                         }
2348                         if (mnt->mnt_parent == path2->mnt)
2349                                 break;
2350                         mnt = mnt->mnt_parent;
2351                 }
2352                 dentry = mnt->mnt_mountpoint;
2353         }
2354         res = is_subdir(dentry, path2->dentry);
2355         br_read_unlock(vfsmount_lock);
2356         return res;
2357 }
2358 EXPORT_SYMBOL(path_is_under);
2359
2360 void d_genocide(struct dentry *root)
2361 {
2362         struct dentry *this_parent = root;
2363         struct list_head *next;
2364
2365         spin_lock(&dcache_lock);
2366 repeat:
2367         next = this_parent->d_subdirs.next;
2368 resume:
2369         while (next != &this_parent->d_subdirs) {
2370                 struct list_head *tmp = next;
2371                 struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
2372                 next = tmp->next;
2373                 if (d_unhashed(dentry)||!dentry->d_inode)
2374                         continue;
2375                 if (!list_empty(&dentry->d_subdirs)) {
2376                         this_parent = dentry;
2377                         goto repeat;
2378                 }
2379                 atomic_dec(&dentry->d_count);
2380         }
2381         if (this_parent != root) {
2382                 next = this_parent->d_u.d_child.next;
2383                 atomic_dec(&this_parent->d_count);
2384                 this_parent = this_parent->d_parent;
2385                 goto resume;
2386         }
2387         spin_unlock(&dcache_lock);
2388 }
2389
2390 /**
2391  * find_inode_number - check for dentry with name
2392  * @dir: directory to check
2393  * @name: Name to find.
2394  *
2395  * Check whether a dentry already exists for the given name,
2396  * and return the inode number if it has an inode. Otherwise
2397  * 0 is returned.
2398  *
2399  * This routine is used to post-process directory listings for
2400  * filesystems using synthetic inode numbers, and is necessary
2401  * to keep getcwd() working.
2402  */
2403  
2404 ino_t find_inode_number(struct dentry *dir, struct qstr *name)
2405 {
2406         struct dentry * dentry;
2407         ino_t ino = 0;
2408
2409         dentry = d_hash_and_lookup(dir, name);
2410         if (dentry) {
2411                 if (dentry->d_inode)
2412                         ino = dentry->d_inode->i_ino;
2413                 dput(dentry);
2414         }
2415         return ino;
2416 }
2417 EXPORT_SYMBOL(find_inode_number);
2418
2419 static __initdata unsigned long dhash_entries;
2420 static int __init set_dhash_entries(char *str)
2421 {
2422         if (!str)
2423                 return 0;
2424         dhash_entries = simple_strtoul(str, &str, 0);
2425         return 1;
2426 }
2427 __setup("dhash_entries=", set_dhash_entries);
2428
2429 static void __init dcache_init_early(void)
2430 {
2431         int loop;
2432
2433         /* If hashes are distributed across NUMA nodes, defer
2434          * hash allocation until vmalloc space is available.
2435          */
2436         if (hashdist)
2437                 return;
2438
2439         dentry_hashtable =
2440                 alloc_large_system_hash("Dentry cache",
2441                                         sizeof(struct hlist_head),
2442                                         dhash_entries,
2443                                         13,
2444                                         HASH_EARLY,
2445                                         &d_hash_shift,
2446                                         &d_hash_mask,
2447                                         0);
2448
2449         for (loop = 0; loop < (1 << d_hash_shift); loop++)
2450                 INIT_HLIST_HEAD(&dentry_hashtable[loop]);
2451 }
2452
2453 static void __init dcache_init(void)
2454 {
2455         int loop;
2456
2457         /* 
2458          * A constructor could be added for stable state like the lists,
2459          * but it is probably not worth it because of the cache nature
2460          * of the dcache. 
2461          */
2462         dentry_cache = KMEM_CACHE(dentry,
2463                 SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD);
2464         
2465         register_shrinker(&dcache_shrinker);
2466
2467         /* Hash may have been set up in dcache_init_early */
2468         if (!hashdist)
2469                 return;
2470
2471         dentry_hashtable =
2472                 alloc_large_system_hash("Dentry cache",
2473                                         sizeof(struct hlist_head),
2474                                         dhash_entries,
2475                                         13,
2476                                         0,
2477                                         &d_hash_shift,
2478                                         &d_hash_mask,
2479                                         0);
2480
2481         for (loop = 0; loop < (1 << d_hash_shift); loop++)
2482                 INIT_HLIST_HEAD(&dentry_hashtable[loop]);
2483 }
2484
2485 /* SLAB cache for __getname() consumers */
2486 struct kmem_cache *names_cachep __read_mostly;
2487 EXPORT_SYMBOL(names_cachep);
2488
2489 EXPORT_SYMBOL(d_genocide);
2490
2491 void __init vfs_caches_init_early(void)
2492 {
2493         dcache_init_early();
2494         inode_init_early();
2495 }
2496
2497 void __init vfs_caches_init(unsigned long mempages)
2498 {
2499         unsigned long reserve;
2500
2501         /* Base hash sizes on available memory, with a reserve equal to
2502            150% of current kernel size */
2503
2504         reserve = min((mempages - nr_free_pages()) * 3/2, mempages - 1);
2505         mempages -= reserve;
2506
2507         names_cachep = kmem_cache_create("names_cache", PATH_MAX, 0,
2508                         SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
2509
2510         dcache_init();
2511         inode_init();
2512         files_init(mempages);
2513         mnt_init();
2514         bdev_cache_init();
2515         chrdev_init();
2516 }