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

Archive Download this file



interactive