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