4 * Complete reimplementation
5 * (C) 1997 Thomas Schoebel-Theuer,
6 * with heavy changes by Linus Torvalds
10 * Notes on the allocation strategy:
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.
17 #include <linux/config.h>
18 #include <linux/string.h>
21 #include <linux/slab.h>
22 #include <linux/init.h>
23 #include <linux/smp_lock.h>
24 #include <linux/cache.h>
25 #include <linux/module.h>
27 #include <asm/uaccess.h>
29 #define DCACHE_PARANOIA 1
30 /* #define DCACHE_DEBUG 1 */
32 spinlock_t dcache_lock __cacheline_aligned_in_smp
= SPIN_LOCK_UNLOCKED
;
33 rwlock_t dparent_lock __cacheline_aligned_in_smp
= RW_LOCK_UNLOCKED
;
35 static kmem_cache_t
*dentry_cache
;
38 * This is the single most critical data structure when it comes
39 * to the dcache: the hashtable for lookups. Somebody should try
40 * to make this good - I've just made it work.
42 * This hash-function tries to avoid losing too many bits of hash
43 * information, yet avoid using a prime hash-size or similar.
45 #define D_HASHBITS d_hash_shift
46 #define D_HASHMASK d_hash_mask
48 static unsigned int d_hash_mask
;
49 static unsigned int d_hash_shift
;
50 static struct list_head
*dentry_hashtable
;
51 static LIST_HEAD(dentry_unused
);
53 /* Statistics gathering. */
54 struct dentry_stat_t dentry_stat
= {
58 /* no dcache_lock, please */
59 static inline void d_free(struct dentry
*dentry
)
61 if (dentry
->d_op
&& dentry
->d_op
->d_release
)
62 dentry
->d_op
->d_release(dentry
);
63 if (dname_external(dentry
))
64 kfree(dentry
->d_name
.name
);
65 kmem_cache_free(dentry_cache
, dentry
);
66 dentry_stat
.nr_dentry
--;
70 * Release the dentry's inode, using the filesystem
71 * d_iput() operation if defined.
72 * Called with dcache_lock held, drops it.
74 static inline void dentry_iput(struct dentry
* dentry
)
76 struct inode
*inode
= dentry
->d_inode
;
78 dentry
->d_inode
= NULL
;
79 list_del_init(&dentry
->d_alias
);
80 spin_unlock(&dcache_lock
);
81 if (dentry
->d_op
&& dentry
->d_op
->d_iput
)
82 dentry
->d_op
->d_iput(dentry
, inode
);
86 spin_unlock(&dcache_lock
);
92 * This is complicated by the fact that we do not want to put
93 * dentries that are no longer on any hash chain on the unused
94 * list: we'd much rather just get rid of them immediately.
96 * However, that implies that we have to traverse the dentry
97 * tree upwards to the parents which might _also_ now be
98 * scheduled for deletion (it may have been only waiting for
99 * its last child to go away).
101 * This tail recursion is done by hand as we don't want to depend
102 * on the compiler to always get this right (gcc generally doesn't).
103 * Real recursion would eat up our stack space.
107 * dput - release a dentry
108 * @dentry: dentry to release
110 * Release a dentry. This will drop the usage count and if appropriate
111 * call the dentry unlink method as well as removing it from the queues and
112 * releasing its resources. If the parent dentries were scheduled for release
113 * they too may now get deleted.
115 * no dcache lock, please.
118 void dput(struct dentry
*dentry
)
124 if (!atomic_dec_and_lock(&dentry
->d_count
, &dcache_lock
))
127 /* dput on a free dentry? */
128 if (!list_empty(&dentry
->d_lru
))
131 * AV: ->d_delete() is _NOT_ allowed to block now.
133 if (dentry
->d_op
&& dentry
->d_op
->d_delete
) {
134 if (dentry
->d_op
->d_delete(dentry
))
137 /* Unreachable? Get rid of it */
138 if (list_empty(&dentry
->d_hash
))
140 list_add(&dentry
->d_lru
, &dentry_unused
);
141 dentry_stat
.nr_unused
++;
142 dentry
->d_vfs_flags
|= DCACHE_REFERENCED
;
143 spin_unlock(&dcache_lock
);
147 list_del_init(&dentry
->d_hash
);
150 struct dentry
*parent
;
151 list_del(&dentry
->d_child
);
152 /* drops the lock, at that point nobody can reach this dentry */
154 parent
= dentry
->d_parent
;
156 if (dentry
== parent
)
164 * d_invalidate - invalidate a dentry
165 * @dentry: dentry to invalidate
167 * Try to invalidate the dentry if it turns out to be
168 * possible. If there are other dentries that can be
169 * reached through this one we can't delete it and we
170 * return -EBUSY. On success we return 0.
175 int d_invalidate(struct dentry
* dentry
)
178 * If it's already been dropped, return OK.
180 spin_lock(&dcache_lock
);
181 if (list_empty(&dentry
->d_hash
)) {
182 spin_unlock(&dcache_lock
);
186 * Check whether to do a partial shrink_dcache
187 * to get rid of unused child entries.
189 if (!list_empty(&dentry
->d_subdirs
)) {
190 spin_unlock(&dcache_lock
);
191 shrink_dcache_parent(dentry
);
192 spin_lock(&dcache_lock
);
196 * Somebody else still using it?
198 * If it's a directory, we can't drop it
199 * for fear of somebody re-populating it
200 * with children (even though dropping it
201 * would make it unreachable from the root,
202 * we might still populate it if it was a
203 * working directory or similar).
205 if (atomic_read(&dentry
->d_count
) > 1) {
206 if (dentry
->d_inode
&& S_ISDIR(dentry
->d_inode
->i_mode
)) {
207 spin_unlock(&dcache_lock
);
212 list_del_init(&dentry
->d_hash
);
213 spin_unlock(&dcache_lock
);
217 /* This should be called _only_ with dcache_lock held */
219 static inline struct dentry
* __dget_locked(struct dentry
*dentry
)
221 atomic_inc(&dentry
->d_count
);
222 if (atomic_read(&dentry
->d_count
) == 1) {
223 dentry_stat
.nr_unused
--;
224 list_del_init(&dentry
->d_lru
);
229 struct dentry
* dget_locked(struct dentry
*dentry
)
231 return __dget_locked(dentry
);
235 * d_find_alias - grab a hashed alias of inode
236 * @inode: inode in question
238 * If inode has a hashed alias - acquire the reference to alias and
239 * return it. Otherwise return NULL. Notice that if inode is a directory
240 * there can be only one alias and it can be unhashed only if it has
243 * If the inode has a DCACHE_DISCONNECTED alias, then prefer
244 * any other hashed alias over that one.
247 struct dentry
* d_find_alias(struct inode
*inode
)
249 struct list_head
*head
, *next
, *tmp
;
250 struct dentry
*alias
, *discon_alias
=NULL
;
252 spin_lock(&dcache_lock
);
253 head
= &inode
->i_dentry
;
254 next
= inode
->i_dentry
.next
;
255 while (next
!= head
) {
258 alias
= list_entry(tmp
, struct dentry
, d_alias
);
259 if (!list_empty(&alias
->d_hash
)) {
260 if (alias
->d_flags
& DCACHE_DISCONNECTED
)
261 discon_alias
= alias
;
263 __dget_locked(alias
);
264 spin_unlock(&dcache_lock
);
270 __dget_locked(discon_alias
);
271 spin_unlock(&dcache_lock
);
276 * Try to kill dentries associated with this inode.
277 * WARNING: you must own a reference to inode.
279 void d_prune_aliases(struct inode
*inode
)
281 struct list_head
*tmp
, *head
= &inode
->i_dentry
;
283 spin_lock(&dcache_lock
);
285 while ((tmp
= tmp
->next
) != head
) {
286 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_alias
);
287 if (!atomic_read(&dentry
->d_count
)) {
288 __dget_locked(dentry
);
289 spin_unlock(&dcache_lock
);
295 spin_unlock(&dcache_lock
);
299 * Throw away a dentry - free the inode, dput the parent.
300 * This requires that the LRU list has already been
302 * Called with dcache_lock, drops it and then regains.
304 static inline void prune_one_dentry(struct dentry
* dentry
)
306 struct dentry
* parent
;
308 list_del_init(&dentry
->d_hash
);
309 list_del(&dentry
->d_child
);
311 parent
= dentry
->d_parent
;
313 if (parent
!= dentry
)
315 spin_lock(&dcache_lock
);
319 * prune_dcache - shrink the dcache
320 * @count: number of entries to try and free
322 * Shrink the dcache. This is done when we need
323 * more memory, or simply when we need to unmount
324 * something (at which point we need to unuse
327 * This function may fail to free any resources if
328 * all the dentries are in use.
331 static void prune_dcache(int count
)
333 spin_lock(&dcache_lock
);
334 for (; count
; count
--) {
335 struct dentry
*dentry
;
336 struct list_head
*tmp
;
338 tmp
= dentry_unused
.prev
;
339 if (tmp
== &dentry_unused
)
342 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
344 /* If the dentry was recently referenced, don't free it. */
345 if (dentry
->d_vfs_flags
& DCACHE_REFERENCED
) {
346 dentry
->d_vfs_flags
&= ~DCACHE_REFERENCED
;
347 list_add(&dentry
->d_lru
, &dentry_unused
);
350 dentry_stat
.nr_unused
--;
352 /* Unused dentry with a count? */
353 BUG_ON(atomic_read(&dentry
->d_count
));
354 prune_one_dentry(dentry
);
356 spin_unlock(&dcache_lock
);
360 * Shrink the dcache for the specified super block.
361 * This allows us to unmount a device without disturbing
362 * the dcache for the other devices.
364 * This implementation makes just two traversals of the
365 * unused list. On the first pass we move the selected
366 * dentries to the most recent end, and on the second
367 * pass we free them. The second pass must restart after
368 * each dput(), but since the target dentries are all at
369 * the end, it's really just a single traversal.
373 * shrink_dcache_sb - shrink dcache for a superblock
376 * Shrink the dcache for the specified super block. This
377 * is used to free the dcache before unmounting a file
381 void shrink_dcache_sb(struct super_block
* sb
)
383 struct list_head
*tmp
, *next
;
384 struct dentry
*dentry
;
387 * Pass one ... move the dentries for the specified
388 * superblock to the most recent end of the unused list.
390 spin_lock(&dcache_lock
);
391 next
= dentry_unused
.next
;
392 while (next
!= &dentry_unused
) {
395 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
396 if (dentry
->d_sb
!= sb
)
399 list_add(tmp
, &dentry_unused
);
403 * Pass two ... free the dentries for this superblock.
406 next
= dentry_unused
.next
;
407 while (next
!= &dentry_unused
) {
410 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
411 if (dentry
->d_sb
!= sb
)
413 if (atomic_read(&dentry
->d_count
))
415 dentry_stat
.nr_unused
--;
417 prune_one_dentry(dentry
);
420 spin_unlock(&dcache_lock
);
424 * Search for at least 1 mount point in the dentry's subdirs.
425 * We descend to the next level whenever the d_subdirs
426 * list is non-empty and continue searching.
430 * have_submounts - check for mounts over a dentry
431 * @parent: dentry to check.
433 * Return true if the parent or its subdirectories contain
437 int have_submounts(struct dentry
*parent
)
439 struct dentry
*this_parent
= parent
;
440 struct list_head
*next
;
442 spin_lock(&dcache_lock
);
443 if (d_mountpoint(parent
))
446 next
= this_parent
->d_subdirs
.next
;
448 while (next
!= &this_parent
->d_subdirs
) {
449 struct list_head
*tmp
= next
;
450 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
452 /* Have we found a mount point ? */
453 if (d_mountpoint(dentry
))
455 if (!list_empty(&dentry
->d_subdirs
)) {
456 this_parent
= dentry
;
461 * All done at this level ... ascend and resume the search.
463 if (this_parent
!= parent
) {
464 next
= this_parent
->d_child
.next
;
465 this_parent
= this_parent
->d_parent
;
468 spin_unlock(&dcache_lock
);
469 return 0; /* No mount points found in tree */
471 spin_unlock(&dcache_lock
);
476 * Search the dentry child list for the specified parent,
477 * and move any unused dentries to the end of the unused
478 * list for prune_dcache(). We descend to the next level
479 * whenever the d_subdirs list is non-empty and continue
482 static int select_parent(struct dentry
* parent
)
484 struct dentry
*this_parent
= parent
;
485 struct list_head
*next
;
488 spin_lock(&dcache_lock
);
490 next
= this_parent
->d_subdirs
.next
;
492 while (next
!= &this_parent
->d_subdirs
) {
493 struct list_head
*tmp
= next
;
494 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
496 if (!atomic_read(&dentry
->d_count
)) {
497 list_del(&dentry
->d_lru
);
498 list_add(&dentry
->d_lru
, dentry_unused
.prev
);
502 * Descend a level if the d_subdirs list is non-empty.
504 if (!list_empty(&dentry
->d_subdirs
)) {
505 this_parent
= dentry
;
507 printk(KERN_DEBUG
"select_parent: descending to %s/%s, found=%d\n",
508 dentry
->d_parent
->d_name
.name
, dentry
->d_name
.name
, found
);
514 * All done at this level ... ascend and resume the search.
516 if (this_parent
!= parent
) {
517 next
= this_parent
->d_child
.next
;
518 this_parent
= this_parent
->d_parent
;
520 printk(KERN_DEBUG
"select_parent: ascending to %s/%s, found=%d\n",
521 this_parent
->d_parent
->d_name
.name
, this_parent
->d_name
.name
, found
);
525 spin_unlock(&dcache_lock
);
530 * shrink_dcache_parent - prune dcache
531 * @parent: parent of entries to prune
533 * Prune the dcache to remove unused children of the parent dentry.
536 void shrink_dcache_parent(struct dentry
* parent
)
540 while ((found
= select_parent(parent
)) != 0)
545 * shrink_dcache_anon - further prune the cache
546 * @head: head of d_hash list of dentries to prune
548 * Prune the dentries that are anonymous
551 void shrink_dcache_anon(struct list_head
*head
)
553 struct list_head
*lp
;
557 spin_lock(&dcache_lock
);
558 list_for_each(lp
, head
) {
559 struct dentry
*this = list_entry(lp
, struct dentry
, d_hash
);
560 if (!atomic_read(&this->d_count
)) {
561 list_del(&this->d_lru
);
562 list_add_tail(&this->d_lru
, &dentry_unused
);
566 spin_unlock(&dcache_lock
);
572 * This is called from kswapd when we think we need some
575 static int shrink_dcache_memory(int nr
, unsigned int gfp_mask
)
579 * Nasty deadlock avoidance.
581 * ext2_new_block->getblk->GFP->shrink_dcache_memory->
582 * prune_dcache->prune_one_dentry->dput->dentry_iput->iput->
583 * inode->i_sb->s_op->put_inode->ext2_discard_prealloc->
584 * ext2_free_blocks->lock_super->DEADLOCK.
586 * We should make sure we don't hold the superblock lock over
587 * block allocations, but for now:
589 if (gfp_mask
& __GFP_FS
)
592 return dentry_stat
.nr_dentry
;
595 #define NAME_ALLOC_LEN(len) ((len+16) & ~15)
598 * d_alloc - allocate a dcache entry
599 * @parent: parent of entry to allocate
600 * @name: qstr of the name
602 * Allocates a dentry. It returns %NULL if there is insufficient memory
603 * available. On a success the dentry is returned. The name passed in is
604 * copied and the copy passed in may be reused after this call.
607 struct dentry
* d_alloc(struct dentry
* parent
, const struct qstr
*name
)
610 struct dentry
*dentry
;
612 dentry
= kmem_cache_alloc(dentry_cache
, GFP_KERNEL
);
616 if (name
->len
> DNAME_INLINE_LEN
-1) {
617 str
= kmalloc(NAME_ALLOC_LEN(name
->len
), GFP_KERNEL
);
619 kmem_cache_free(dentry_cache
, dentry
);
623 str
= dentry
->d_iname
;
625 memcpy(str
, name
->name
, name
->len
);
628 atomic_set(&dentry
->d_count
, 1);
629 dentry
->d_vfs_flags
= 0;
631 dentry
->d_inode
= NULL
;
632 dentry
->d_parent
= NULL
;
634 dentry
->d_name
.name
= str
;
635 dentry
->d_name
.len
= name
->len
;
636 dentry
->d_name
.hash
= name
->hash
;
638 dentry
->d_fsdata
= NULL
;
639 dentry
->d_mounted
= 0;
640 dentry
->d_cookie
= NULL
;
641 INIT_LIST_HEAD(&dentry
->d_hash
);
642 INIT_LIST_HEAD(&dentry
->d_lru
);
643 INIT_LIST_HEAD(&dentry
->d_subdirs
);
644 INIT_LIST_HEAD(&dentry
->d_alias
);
646 dentry
->d_parent
= dget(parent
);
647 dentry
->d_sb
= parent
->d_sb
;
648 spin_lock(&dcache_lock
);
649 list_add(&dentry
->d_child
, &parent
->d_subdirs
);
650 spin_unlock(&dcache_lock
);
652 INIT_LIST_HEAD(&dentry
->d_child
);
654 dentry_stat
.nr_dentry
++;
659 * d_instantiate - fill in inode information for a dentry
660 * @entry: dentry to complete
661 * @inode: inode to attach to this dentry
663 * Fill in inode information in the entry.
665 * This turns negative dentries into productive full members
668 * NOTE! This assumes that the inode count has been incremented
669 * (or otherwise set) by the caller to indicate that it is now
670 * in use by the dcache.
673 void d_instantiate(struct dentry
*entry
, struct inode
* inode
)
675 if (!list_empty(&entry
->d_alias
)) BUG();
676 spin_lock(&dcache_lock
);
678 list_add(&entry
->d_alias
, &inode
->i_dentry
);
679 entry
->d_inode
= inode
;
680 spin_unlock(&dcache_lock
);
684 * d_alloc_root - allocate root dentry
685 * @root_inode: inode to allocate the root for
687 * Allocate a root ("/") dentry for the inode given. The inode is
688 * instantiated and returned. %NULL is returned if there is insufficient
689 * memory or the inode passed is %NULL.
692 struct dentry
* d_alloc_root(struct inode
* root_inode
)
694 struct dentry
*res
= NULL
;
697 res
= d_alloc(NULL
, &(const struct qstr
) { "/", 1, 0 });
699 res
->d_sb
= root_inode
->i_sb
;
701 d_instantiate(res
, root_inode
);
707 static inline struct list_head
* d_hash(struct dentry
* parent
, unsigned long hash
)
709 hash
+= (unsigned long) parent
/ L1_CACHE_BYTES
;
710 hash
= hash
^ (hash
>> D_HASHBITS
);
711 return dentry_hashtable
+ (hash
& D_HASHMASK
);
715 * d_alloc_anon - allocate an anonymous dentry
716 * @inode: inode to allocate the dentry for
718 * This is similar to d_alloc_root. It is used by filesystems when
719 * creating a dentry for a given inode, often in the process of
720 * mapping a filehandle to a dentry. The returned dentry may be
721 * anonymous, or may have a full name (if the inode was already
722 * in the cache). The file system may need to make further
723 * efforts to connect this dentry into the dcache properly.
725 * When called on a directory inode, we must ensure that
726 * the inode only ever has one dentry. If a dentry is
727 * found, that is returned instead of allocating a new one.
729 * On successful return, the reference to the inode has been transferred
730 * to the dentry. If %NULL is returned (indicating kmalloc failure),
731 * the reference on the inode has not been released.
734 struct dentry
* d_alloc_anon(struct inode
*inode
)
739 if ((res
= d_find_alias(inode
))) {
744 tmp
= d_alloc(NULL
, &(const struct qstr
) {"",0,0});
748 tmp
->d_parent
= tmp
; /* make sure dput doesn't croak */
750 spin_lock(&dcache_lock
);
751 if (S_ISDIR(inode
->i_mode
) && !list_empty(&inode
->i_dentry
)) {
752 /* A directory can only have one dentry.
753 * This (now) has one, so use it.
755 res
= list_entry(inode
->i_dentry
.next
, struct dentry
, d_alias
);
758 /* attach a disconnected dentry */
762 res
->d_sb
= inode
->i_sb
;
764 res
->d_inode
= inode
;
765 res
->d_flags
|= DCACHE_DISCONNECTED
;
766 list_add(&res
->d_alias
, &inode
->i_dentry
);
767 list_add(&res
->d_hash
, &inode
->i_sb
->s_anon
);
769 inode
= NULL
; /* don't drop reference */
771 spin_unlock(&dcache_lock
);
782 * d_splice_alias - splice a disconnected dentry into the tree if one exists
783 * @inode: the inode which may have a disconnected dentry
784 * @dentry: a negative dentry which we want to point to the inode.
786 * If inode is a directory and has a 'disconnected' dentry (i.e. IS_ROOT and
787 * DCACHE_DISCONNECTED), then d_move that in place of the given dentry
788 * and return it, else simply d_add the inode to the dentry and return NULL.
790 * This is (will be) needed in the lookup routine of any filesystem that is exportable
791 * (via knfsd) so that we can build dcache paths to directories effectively.
793 * If a dentry was found and moved, then it is returned. Otherwise NULL
794 * is returned. This matches the expected return value of ->lookup.
797 struct dentry
*d_splice_alias(struct inode
*inode
, struct dentry
*dentry
)
799 struct dentry
*new = NULL
;
801 if (inode
&& S_ISDIR(inode
->i_mode
)) {
802 spin_lock(&dcache_lock
);
803 if (!list_empty(&inode
->i_dentry
)) {
804 new = list_entry(inode
->i_dentry
.next
, struct dentry
, d_alias
);
806 spin_unlock(&dcache_lock
);
811 /* d_instantiate takes dcache_lock, so we do it by hand */
812 list_add(&dentry
->d_alias
, &inode
->i_dentry
);
813 dentry
->d_inode
= inode
;
814 spin_unlock(&dcache_lock
);
818 d_add(dentry
, inode
);
824 * d_lookup - search for a dentry
825 * @parent: parent dentry
826 * @name: qstr of name we wish to find
828 * Searches the children of the parent dentry for the name in question. If
829 * the dentry is found its reference count is incremented and the dentry
830 * is returned. The caller must use d_put to free the entry when it has
831 * finished using it. %NULL is returned on failure.
834 struct dentry
* d_lookup(struct dentry
* parent
, struct qstr
* name
)
836 struct dentry
* dentry
;
837 spin_lock(&dcache_lock
);
838 dentry
= __d_lookup(parent
,name
);
840 __dget_locked(dentry
);
841 spin_unlock(&dcache_lock
);
845 struct dentry
* __d_lookup(struct dentry
* parent
, struct qstr
* name
)
848 unsigned int len
= name
->len
;
849 unsigned int hash
= name
->hash
;
850 const unsigned char *str
= name
->name
;
851 struct list_head
*head
= d_hash(parent
,hash
);
852 struct list_head
*tmp
;
856 struct dentry
* dentry
= list_entry(tmp
, struct dentry
, d_hash
);
860 if (dentry
->d_name
.hash
!= hash
)
862 if (dentry
->d_parent
!= parent
)
864 if (parent
->d_op
&& parent
->d_op
->d_compare
) {
865 if (parent
->d_op
->d_compare(parent
, &dentry
->d_name
, name
))
868 if (dentry
->d_name
.len
!= len
)
870 if (memcmp(dentry
->d_name
.name
, str
, len
))
879 * d_validate - verify dentry provided from insecure source
880 * @dentry: The dentry alleged to be valid child of @dparent
881 * @dparent: The parent dentry (known to be valid)
882 * @hash: Hash of the dentry
883 * @len: Length of the name
885 * An insecure source has sent us a dentry, here we verify it and dget() it.
886 * This is used by ncpfs in its readdir implementation.
887 * Zero is returned in the dentry is invalid.
890 int d_validate(struct dentry
*dentry
, struct dentry
*dparent
)
892 unsigned long dent_addr
= (unsigned long) dentry
;
893 unsigned long min_addr
= PAGE_OFFSET
;
894 unsigned long align_mask
= 0x0F;
895 struct list_head
*base
, *lhp
;
897 if (dent_addr
< min_addr
)
899 if (dent_addr
> (unsigned long)high_memory
- sizeof(struct dentry
))
901 if (dent_addr
& align_mask
)
903 if ((!kern_addr_valid(dent_addr
)) || (!kern_addr_valid(dent_addr
-1 +
904 sizeof(struct dentry
))))
907 if (dentry
->d_parent
!= dparent
)
910 spin_lock(&dcache_lock
);
911 lhp
= base
= d_hash(dparent
, dentry
->d_name
.hash
);
912 while ((lhp
= lhp
->next
) != base
) {
913 if (dentry
== list_entry(lhp
, struct dentry
, d_hash
)) {
914 __dget_locked(dentry
);
915 spin_unlock(&dcache_lock
);
919 spin_unlock(&dcache_lock
);
925 * When a file is deleted, we have two options:
926 * - turn this dentry into a negative dentry
927 * - unhash this dentry and free it.
929 * Usually, we want to just turn this into
930 * a negative dentry, but if anybody else is
931 * currently using the dentry or the inode
932 * we can't do that and we fall back on removing
933 * it from the hash queues and waiting for
934 * it to be deleted later when it has no users
938 * d_delete - delete a dentry
939 * @dentry: The dentry to delete
941 * Turn the dentry into a negative dentry if possible, otherwise
942 * remove it from the hash queues so it can be deleted later
945 void d_delete(struct dentry
* dentry
)
948 * Are we the only user?
950 spin_lock(&dcache_lock
);
951 if (atomic_read(&dentry
->d_count
) == 1) {
955 spin_unlock(&dcache_lock
);
958 * If not, just drop the dentry and let dput
965 * d_rehash - add an entry back to the hash
966 * @entry: dentry to add to the hash
968 * Adds a dentry to the hash according to its name.
971 void d_rehash(struct dentry
* entry
)
973 struct list_head
*list
= d_hash(entry
->d_parent
, entry
->d_name
.hash
);
974 if (!list_empty(&entry
->d_hash
)) BUG();
975 spin_lock(&dcache_lock
);
976 list_add(&entry
->d_hash
, list
);
977 spin_unlock(&dcache_lock
);
980 #define do_switch(x,y) do { \
981 __typeof__ (x) __tmp = x; \
982 x = y; y = __tmp; } while (0)
985 * When switching names, the actual string doesn't strictly have to
986 * be preserved in the target - because we're dropping the target
987 * anyway. As such, we can just do a simple memcpy() to copy over
988 * the new name before we switch.
990 * Note that we have to be a lot more careful about getting the hash
991 * switched - we have to switch the hash value properly even if it
992 * then no longer matches the actual (corrupted) string of the target.
993 * The hash value has to match the hash queue that the dentry is on..
995 static inline void switch_names(struct dentry
* dentry
, struct dentry
* target
)
997 const unsigned char *old_name
, *new_name
;
999 memcpy(dentry
->d_iname
, target
->d_iname
, DNAME_INLINE_LEN
);
1000 old_name
= target
->d_name
.name
;
1001 new_name
= dentry
->d_name
.name
;
1002 if (old_name
== target
->d_iname
)
1003 old_name
= dentry
->d_iname
;
1004 if (new_name
== dentry
->d_iname
)
1005 new_name
= target
->d_iname
;
1006 target
->d_name
.name
= new_name
;
1007 dentry
->d_name
.name
= old_name
;
1011 * We cannibalize "target" when moving dentry on top of it,
1012 * because it's going to be thrown away anyway. We could be more
1013 * polite about it, though.
1015 * This forceful removal will result in ugly /proc output if
1016 * somebody holds a file open that got deleted due to a rename.
1017 * We could be nicer about the deleted file, and let it show
1018 * up under the name it got deleted rather than the name that
1021 * Careful with the hash switch. The hash switch depends on
1022 * the fact that any list-entry can be a head of the list.
1027 * d_move - move a dentry
1028 * @dentry: entry to move
1029 * @target: new dentry
1031 * Update the dcache to reflect the move of a file name. Negative
1032 * dcache entries should not be moved in this way.
1035 void d_move(struct dentry
* dentry
, struct dentry
* target
)
1037 if (!dentry
->d_inode
)
1038 printk(KERN_WARNING
"VFS: moving negative dcache entry\n");
1040 spin_lock(&dcache_lock
);
1041 /* Move the dentry to the target hash queue */
1042 list_del(&dentry
->d_hash
);
1043 list_add(&dentry
->d_hash
, &target
->d_hash
);
1045 /* Unhash the target: dput() will then get rid of it */
1046 list_del_init(&target
->d_hash
);
1048 list_del(&dentry
->d_child
);
1049 list_del(&target
->d_child
);
1051 /* Switch the names.. */
1052 switch_names(dentry
, target
);
1053 do_switch(dentry
->d_name
.len
, target
->d_name
.len
);
1054 do_switch(dentry
->d_name
.hash
, target
->d_name
.hash
);
1055 /* ... and switch the parents */
1056 write_lock(&dparent_lock
);
1057 if (IS_ROOT(dentry
)) {
1058 dentry
->d_parent
= target
->d_parent
;
1059 target
->d_parent
= target
;
1060 INIT_LIST_HEAD(&target
->d_child
);
1062 do_switch(dentry
->d_parent
, target
->d_parent
);
1064 /* And add them back to the (new) parent lists */
1065 list_add(&target
->d_child
, &target
->d_parent
->d_subdirs
);
1067 write_unlock(&dparent_lock
);
1069 list_add(&dentry
->d_child
, &dentry
->d_parent
->d_subdirs
);
1070 spin_unlock(&dcache_lock
);
1074 * d_path - return the path of a dentry
1075 * @dentry: dentry to report
1076 * @vfsmnt: vfsmnt to which the dentry belongs
1077 * @root: root dentry
1078 * @rootmnt: vfsmnt to which the root dentry belongs
1079 * @buffer: buffer to return value in
1080 * @buflen: buffer length
1082 * Convert a dentry into an ASCII path name. If the entry has been deleted
1083 * the string " (deleted)" is appended. Note that this is ambiguous. Returns
1086 * "buflen" should be %PAGE_SIZE or more. Caller holds the dcache_lock.
1088 char * __d_path(struct dentry
*dentry
, struct vfsmount
*vfsmnt
,
1089 struct dentry
*root
, struct vfsmount
*rootmnt
,
1090 char *buffer
, int buflen
)
1092 char * end
= buffer
+buflen
;
1098 if (!IS_ROOT(dentry
) && list_empty(&dentry
->d_hash
)) {
1101 memcpy(end
, " (deleted)", 10);
1109 struct dentry
* parent
;
1111 if (dentry
== root
&& vfsmnt
== rootmnt
)
1113 if (dentry
== vfsmnt
->mnt_root
|| IS_ROOT(dentry
)) {
1115 if (vfsmnt
->mnt_parent
== vfsmnt
)
1117 dentry
= vfsmnt
->mnt_mountpoint
;
1118 vfsmnt
= vfsmnt
->mnt_parent
;
1121 parent
= dentry
->d_parent
;
1122 namelen
= dentry
->d_name
.len
;
1123 buflen
-= namelen
+ 1;
1127 memcpy(end
, dentry
->d_name
.name
, namelen
);
1134 namelen
= dentry
->d_name
.len
;
1137 retval
-= namelen
-1; /* hit the slash */
1138 memcpy(retval
, dentry
->d_name
.name
, namelen
);
1144 * NOTE! The user-level library version returns a
1145 * character pointer. The kernel system call just
1146 * returns the length of the buffer filled (which
1147 * includes the ending '\0' character), or a negative
1148 * error value. So libc would do something like
1150 * char *getcwd(char * buf, size_t size)
1154 * retval = sys_getcwd(buf, size);
1161 asmlinkage
long sys_getcwd(char *buf
, unsigned long size
)
1164 struct vfsmount
*pwdmnt
, *rootmnt
;
1165 struct dentry
*pwd
, *root
;
1166 char *page
= (char *) __get_free_page(GFP_USER
);
1171 read_lock(¤t
->fs
->lock
);
1172 pwdmnt
= mntget(current
->fs
->pwdmnt
);
1173 pwd
= dget(current
->fs
->pwd
);
1174 rootmnt
= mntget(current
->fs
->rootmnt
);
1175 root
= dget(current
->fs
->root
);
1176 read_unlock(¤t
->fs
->lock
);
1179 /* Has the current directory has been unlinked? */
1180 spin_lock(&dcache_lock
);
1181 if (pwd
->d_parent
== pwd
|| !list_empty(&pwd
->d_hash
)) {
1185 cwd
= __d_path(pwd
, pwdmnt
, root
, rootmnt
, page
, PAGE_SIZE
);
1186 spin_unlock(&dcache_lock
);
1189 len
= PAGE_SIZE
+ page
- cwd
;
1192 if (copy_to_user(buf
, cwd
, len
))
1196 spin_unlock(&dcache_lock
);
1201 free_page((unsigned long) page
);
1206 * Test whether new_dentry is a subdirectory of old_dentry.
1208 * Trivially implemented using the dcache structure
1212 * is_subdir - is new dentry a subdirectory of old_dentry
1213 * @new_dentry: new dentry
1214 * @old_dentry: old dentry
1216 * Returns 1 if new_dentry is a subdirectory of the parent (at any depth).
1217 * Returns 0 otherwise.
1220 int is_subdir(struct dentry
* new_dentry
, struct dentry
* old_dentry
)
1226 if (new_dentry
!= old_dentry
) {
1227 struct dentry
* parent
= new_dentry
->d_parent
;
1228 if (parent
== new_dentry
)
1230 new_dentry
= parent
;
1239 void d_genocide(struct dentry
*root
)
1241 struct dentry
*this_parent
= root
;
1242 struct list_head
*next
;
1244 spin_lock(&dcache_lock
);
1246 next
= this_parent
->d_subdirs
.next
;
1248 while (next
!= &this_parent
->d_subdirs
) {
1249 struct list_head
*tmp
= next
;
1250 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
1252 if (d_unhashed(dentry
)||!dentry
->d_inode
)
1254 if (!list_empty(&dentry
->d_subdirs
)) {
1255 this_parent
= dentry
;
1258 atomic_dec(&dentry
->d_count
);
1260 if (this_parent
!= root
) {
1261 next
= this_parent
->d_child
.next
;
1262 atomic_dec(&this_parent
->d_count
);
1263 this_parent
= this_parent
->d_parent
;
1266 spin_unlock(&dcache_lock
);
1270 * find_inode_number - check for dentry with name
1271 * @dir: directory to check
1272 * @name: Name to find.
1274 * Check whether a dentry already exists for the given name,
1275 * and return the inode number if it has an inode. Otherwise
1278 * This routine is used to post-process directory listings for
1279 * filesystems using synthetic inode numbers, and is necessary
1280 * to keep getcwd() working.
1283 ino_t
find_inode_number(struct dentry
*dir
, struct qstr
*name
)
1285 struct dentry
* dentry
;
1289 * Check for a fs-specific hash function. Note that we must
1290 * calculate the standard hash first, as the d_op->d_hash()
1291 * routine may choose to leave the hash value unchanged.
1293 name
->hash
= full_name_hash(name
->name
, name
->len
);
1294 if (dir
->d_op
&& dir
->d_op
->d_hash
)
1296 if (dir
->d_op
->d_hash(dir
, name
) != 0)
1300 dentry
= d_lookup(dir
, name
);
1303 if (dentry
->d_inode
)
1304 ino
= dentry
->d_inode
->i_ino
;
1311 static void __init
dcache_init(unsigned long mempages
)
1313 struct list_head
*d
;
1314 unsigned long order
;
1315 unsigned int nr_hash
;
1319 * A constructor could be added for stable state like the lists,
1320 * but it is probably not worth it because of the cache nature
1322 * If fragmentation is too bad then the SLAB_HWCACHE_ALIGN
1323 * flag could be removed here, to hint to the allocator that
1324 * it should not try to get multiple page regions.
1326 dentry_cache
= kmem_cache_create("dentry_cache",
1327 sizeof(struct dentry
),
1332 panic("Cannot create dentry cache");
1334 set_shrinker(DEFAULT_SEEKS
, shrink_dcache_memory
);
1337 mempages
>>= (13 - PAGE_SHIFT
);
1339 mempages
*= sizeof(struct list_head
);
1340 for (order
= 0; ((1UL << order
) << PAGE_SHIFT
) < mempages
; order
++)
1346 nr_hash
= (1UL << order
) * PAGE_SIZE
/
1347 sizeof(struct list_head
);
1348 d_hash_mask
= (nr_hash
- 1);
1352 while ((tmp
>>= 1UL) != 0UL)
1355 dentry_hashtable
= (struct list_head
*)
1356 __get_free_pages(GFP_ATOMIC
, order
);
1357 } while (dentry_hashtable
== NULL
&& --order
>= 0);
1359 printk(KERN_INFO
"Dentry cache hash table entries: %d (order: %ld, %ld bytes)\n",
1360 nr_hash
, order
, (PAGE_SIZE
<< order
));
1362 if (!dentry_hashtable
)
1363 panic("Failed to allocate dcache hash table\n");
1365 d
= dentry_hashtable
;
1374 /* SLAB cache for __getname() consumers */
1375 kmem_cache_t
*names_cachep
;
1377 /* SLAB cache for file structures */
1378 kmem_cache_t
*filp_cachep
;
1380 EXPORT_SYMBOL(d_genocide
);
1382 extern void bdev_cache_init(void);
1383 extern void cdev_cache_init(void);
1385 void __init
vfs_caches_init(unsigned long mempages
)
1387 names_cachep
= kmem_cache_create("names_cache",
1389 SLAB_HWCACHE_ALIGN
, NULL
, NULL
);
1391 panic("Cannot create names SLAB cache");
1393 filp_cachep
= kmem_cache_create("filp",
1394 sizeof(struct file
), 0,
1395 SLAB_HWCACHE_ALIGN
, NULL
, NULL
);
1397 panic("Cannot create filp SLAB cache");
1399 dcache_init(mempages
);
1400 inode_init(mempages
);
1401 files_init(mempages
);