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/string.h>
20 #include <linux/malloc.h>
21 #include <linux/slab.h>
22 #include <linux/init.h>
24 #include <asm/uaccess.h>
26 #define DCACHE_PARANOIA 1
27 /* #define DCACHE_DEBUG 1 */
29 /* For managing the dcache */
30 extern unsigned long num_physpages
, page_cache_size
;
31 extern int inodes_stat
[];
32 #define nr_inodes (inodes_stat[0])
34 kmem_cache_t
*dentry_cache
;
37 * This is the single most critical data structure when it comes
38 * to the dcache: the hashtable for lookups. Somebody should try
39 * to make this good - I've just made it work.
41 * This hash-function tries to avoid losing too many bits of hash
42 * information, yet avoid using a prime hash-size or similar.
45 #define D_HASHSIZE (1UL << D_HASHBITS)
46 #define D_HASHMASK (D_HASHSIZE-1)
48 static struct list_head dentry_hashtable
[D_HASHSIZE
];
49 static LIST_HEAD(dentry_unused
);
54 int age_limit
; /* age in seconds */
55 int want_pages
; /* pages requested by system */
57 } dentry_stat
= {0, 0, 45, 0,};
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
);
69 * Release the dentry's inode, using the fileystem
70 * d_iput() operation if defined.
72 static inline void dentry_iput(struct dentry
* dentry
)
74 struct inode
*inode
= dentry
->d_inode
;
76 dentry
->d_inode
= NULL
;
77 list_del(&dentry
->d_alias
);
78 INIT_LIST_HEAD(&dentry
->d_alias
);
79 if (dentry
->d_op
&& dentry
->d_op
->d_iput
)
80 dentry
->d_op
->d_iput(dentry
, inode
);
89 * This is complicated by the fact that we do not want to put
90 * dentries that are no longer on any hash chain on the unused
91 * list: we'd much rather just get rid of them immediately.
93 * However, that implies that we have to traverse the dentry
94 * tree upwards to the parents which might _also_ now be
95 * scheduled for deletion (it may have been only waiting for
96 * its last child to go away).
98 * This tail recursion is done by hand as we don't want to depend
99 * on the compiler to always get this right (gcc generally doesn't).
100 * Real recursion would eat up our stack space.
102 void dput(struct dentry
*dentry
)
110 count
= dentry
->d_count
- 1;
115 * Note that if d_op->d_delete blocks,
116 * the dentry could go back in use.
117 * Each fs will have to watch for this.
119 if (dentry
->d_op
&& dentry
->d_op
->d_delete
) {
120 dentry
->d_op
->d_delete(dentry
);
122 count
= dentry
->d_count
- 1;
127 if (!list_empty(&dentry
->d_lru
)) {
128 dentry_stat
.nr_unused
--;
129 list_del(&dentry
->d_lru
);
131 if (list_empty(&dentry
->d_hash
)) {
132 struct dentry
* parent
;
134 list_del(&dentry
->d_child
);
136 parent
= dentry
->d_parent
;
138 if (dentry
== parent
)
143 list_add(&dentry
->d_lru
, &dentry_unused
);
144 dentry_stat
.nr_unused
++;
146 * Update the timestamp
148 dentry
->d_reftime
= jiffies
;
152 dentry
->d_count
= count
;
156 printk(KERN_CRIT
"Negative d_count (%d) for %s/%s\n",
158 dentry
->d_parent
->d_name
.name
,
159 dentry
->d_name
.name
);
164 * Try to invalidate the dentry if it turns out to be
165 * possible. If there are other dentries that can be
166 * reached through this one we can't delete it.
168 int d_invalidate(struct dentry
* dentry
)
171 * Check whether to do a partial shrink_dcache
172 * to get rid of unused child entries.
174 if (!list_empty(&dentry
->d_subdirs
)) {
175 shrink_dcache_parent(dentry
);
179 * Somebody else still using it?
181 * If it's a directory, we can't drop it
182 * for fear of somebody re-populating it
183 * with children (even though dropping it
184 * would make it unreachable from the root,
185 * we might still populate it if it was a
186 * working directory or similar).
188 if (dentry
->d_count
> 1) {
189 if (dentry
->d_inode
&& S_ISDIR(dentry
->d_inode
->i_mode
))
198 * Select less valuable dentries to be pruned when we need
199 * inodes or memory. The selected dentries are moved to the
200 * old end of the list where prune_dcache() can find them.
202 * Negative dentries are included in the selection so that
203 * they don't accumulate at the end of the list. The count
204 * returned is the total number of dentries selected, which
205 * may be much larger than the requested number of inodes.
207 int select_dcache(int inode_count
, int page_count
)
209 struct list_head
*next
, *tail
= &dentry_unused
;
211 int depth
= dentry_stat
.nr_unused
>> 1;
212 unsigned long max_value
= 4;
218 while (next
!= &dentry_unused
&& depth
--) {
219 struct list_head
*tmp
= next
;
220 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_lru
);
221 struct inode
*inode
= dentry
->d_inode
;
222 unsigned long value
= 0;
225 if (dentry
->d_count
) {
226 dentry_stat
.nr_unused
--;
233 * Select dentries based on the page cache count ...
234 * should factor in number of uses as well. We take
235 * all negative dentries so that they don't accumulate.
236 * (We skip inodes that aren't immediately available.)
239 value
= inode
->i_nrpages
;
240 if (value
>= max_value
)
242 if (inode
->i_state
|| inode
->i_count
> 1)
247 * Move the selected dentries behind the tail.
249 if (tmp
!= tail
->prev
) {
251 list_add(tmp
, tail
->prev
);
255 if (inode
&& --inode_count
<= 0)
257 if (page_count
&& (page_count
-= value
) <= 0)
264 * Throw away a dentry - free the inode, dput the parent.
265 * This requires that the LRU list has already been
268 static inline void prune_one_dentry(struct dentry
* dentry
)
270 struct dentry
* parent
;
272 list_del(&dentry
->d_hash
);
273 list_del(&dentry
->d_child
);
275 parent
= dentry
->d_parent
;
281 * Shrink the dcache. This is done when we need
282 * more memory, or simply when we need to unmount
283 * something (at which point we need to unuse
286 void prune_dcache(int count
)
289 struct dentry
*dentry
;
290 struct list_head
*tmp
= dentry_unused
.prev
;
292 if (tmp
== &dentry_unused
)
294 dentry_stat
.nr_unused
--;
297 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
298 if (!dentry
->d_count
) {
299 prune_one_dentry(dentry
);
307 * Shrink the dcache for the specified super block.
308 * This allows us to unmount a device without disturbing
309 * the dcache for the other devices.
311 * This implementation makes just two traversals of the
312 * unused list. On the first pass we move the selected
313 * dentries to the most recent end, and on the second
314 * pass we free them. The second pass must restart after
315 * each dput(), but since the target dentries are all at
316 * the end, it's really just a single traversal.
318 void shrink_dcache_sb(struct super_block
* sb
)
320 struct list_head
*tmp
, *next
;
321 struct dentry
*dentry
;
324 * Pass one ... move the dentries for the specified
325 * superblock to the most recent end of the unused list.
327 next
= dentry_unused
.next
;
328 while (next
!= &dentry_unused
) {
331 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
332 if (dentry
->d_sb
!= sb
)
335 list_add(tmp
, &dentry_unused
);
339 * Pass two ... free the dentries for this superblock.
342 next
= dentry_unused
.next
;
343 while (next
!= &dentry_unused
) {
346 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
347 if (dentry
->d_sb
!= sb
)
351 dentry_stat
.nr_unused
--;
354 prune_one_dentry(dentry
);
360 * Check whether a root dentry would be in use if all of its
361 * child dentries were freed. This allows a non-destructive
362 * test for unmounting a device.
364 int is_root_busy(struct dentry
*root
)
366 struct dentry
*this_parent
= root
;
367 struct list_head
*next
;
368 int count
= root
->d_count
;
371 next
= this_parent
->d_subdirs
.next
;
373 while (next
!= &this_parent
->d_subdirs
) {
374 struct list_head
*tmp
= next
;
375 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
377 /* Decrement count for unused children */
378 count
+= (dentry
->d_count
- 1);
379 if (!list_empty(&dentry
->d_subdirs
)) {
380 this_parent
= dentry
;
383 /* root is busy if any leaf is busy */
388 * All done at this level ... ascend and resume the search.
390 if (this_parent
!= root
) {
391 next
= this_parent
->d_child
.next
;
392 this_parent
= this_parent
->d_parent
;
395 return (count
> 1); /* remaining users? */
399 * Search the dentry child list for the specified parent,
400 * and move any unused dentries to the end of the unused
401 * list for prune_dcache(). We descend to the next level
402 * whenever the d_subdirs list is non-empty and continue
405 static int select_parent(struct dentry
* parent
)
407 struct dentry
*this_parent
= parent
;
408 struct list_head
*next
;
412 next
= this_parent
->d_subdirs
.next
;
414 while (next
!= &this_parent
->d_subdirs
) {
415 struct list_head
*tmp
= next
;
416 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
418 if (!dentry
->d_count
) {
419 list_del(&dentry
->d_lru
);
420 list_add(&dentry
->d_lru
, dentry_unused
.prev
);
424 * Descend a level if the d_subdirs list is non-empty.
426 if (!list_empty(&dentry
->d_subdirs
)) {
427 this_parent
= dentry
;
429 printk(KERN_DEBUG
"select_parent: descending to %s/%s, found=%d\n",
430 dentry
->d_parent
->d_name
.name
, dentry
->d_name
.name
, found
);
436 * All done at this level ... ascend and resume the search.
438 if (this_parent
!= parent
) {
439 next
= this_parent
->d_child
.next
;
440 this_parent
= this_parent
->d_parent
;
442 printk(KERN_DEBUG
"select_parent: ascending to %s/%s, found=%d\n",
443 this_parent
->d_parent
->d_name
.name
, this_parent
->d_name
.name
, found
);
451 * Prune the dcache to remove unused children of the parent dentry.
453 void shrink_dcache_parent(struct dentry
* parent
)
457 while ((found
= select_parent(parent
)) != 0)
462 * This is called from kswapd when we think we need some
463 * more memory, but aren't really sure how much. So we
464 * carefully try to free a _bit_ of our dcache, but not
468 * 0 - very urgent: shrink everything
470 * 6 - base-level: try to shrink a bit.
472 void shrink_dcache_memory(int priority
, unsigned int gfp_mask
)
474 if (gfp_mask
& __GFP_IO
) {
477 count
= dentry_stat
.nr_unused
/ priority
;
482 #define NAME_ALLOC_LEN(len) ((len+16) & ~15)
484 struct dentry
* d_alloc(struct dentry
* parent
, const struct qstr
*name
)
487 struct dentry
*dentry
;
489 dentry
= kmem_cache_alloc(dentry_cache
, GFP_KERNEL
);
493 if (name
->len
> DNAME_INLINE_LEN
-1) {
494 str
= kmalloc(NAME_ALLOC_LEN(name
->len
), GFP_KERNEL
);
496 kmem_cache_free(dentry_cache
, dentry
);
500 str
= dentry
->d_iname
;
502 memcpy(str
, name
->name
, name
->len
);
507 dentry
->d_inode
= NULL
;
508 dentry
->d_parent
= NULL
;
511 dentry
->d_parent
= dget(parent
);
512 dentry
->d_sb
= parent
->d_sb
;
513 list_add(&dentry
->d_child
, &parent
->d_subdirs
);
515 INIT_LIST_HEAD(&dentry
->d_child
);
517 dentry
->d_mounts
= dentry
;
518 dentry
->d_covers
= dentry
;
519 INIT_LIST_HEAD(&dentry
->d_hash
);
520 INIT_LIST_HEAD(&dentry
->d_lru
);
521 INIT_LIST_HEAD(&dentry
->d_subdirs
);
522 INIT_LIST_HEAD(&dentry
->d_alias
);
524 dentry
->d_name
.name
= str
;
525 dentry
->d_name
.len
= name
->len
;
526 dentry
->d_name
.hash
= name
->hash
;
528 dentry
->d_fsdata
= NULL
;
533 * Fill in inode information in the entry.
535 * This turns negative dentries into productive full members
538 * NOTE! This assumes that the inode count has been incremented
539 * (or otherwise set) by the caller to indicate that it is now
540 * in use by the dcache..
542 void d_instantiate(struct dentry
*entry
, struct inode
* inode
)
545 list_add(&entry
->d_alias
, &inode
->i_dentry
);
546 entry
->d_inode
= inode
;
549 struct dentry
* d_alloc_root(struct inode
* root_inode
)
551 struct dentry
*res
= NULL
;
554 res
= d_alloc(NULL
, &(const struct qstr
) { "/", 1, 0 });
556 res
->d_sb
= root_inode
->i_sb
;
558 d_instantiate(res
, root_inode
);
564 static inline struct list_head
* d_hash(struct dentry
* parent
, unsigned long hash
)
566 hash
+= (unsigned long) parent
;
567 hash
= hash
^ (hash
>> D_HASHBITS
) ^ (hash
>> D_HASHBITS
*2);
568 return dentry_hashtable
+ (hash
& D_HASHMASK
);
571 struct dentry
* d_lookup(struct dentry
* parent
, struct qstr
* name
)
573 unsigned int len
= name
->len
;
574 unsigned int hash
= name
->hash
;
575 const unsigned char *str
= name
->name
;
576 struct list_head
*head
= d_hash(parent
,hash
);
577 struct list_head
*tmp
= head
->next
;
580 struct dentry
* dentry
= list_entry(tmp
, struct dentry
, d_hash
);
584 if (dentry
->d_name
.hash
!= hash
)
586 if (dentry
->d_parent
!= parent
)
588 if (parent
->d_op
&& parent
->d_op
->d_compare
) {
589 if (parent
->d_op
->d_compare(parent
, &dentry
->d_name
, name
))
592 if (dentry
->d_name
.len
!= len
)
594 if (memcmp(dentry
->d_name
.name
, str
, len
))
603 * An insecure source has sent us a dentry, here we verify it.
605 * This is just to make knfsd able to have the dentry pointer
606 * in the NFS file handle.
608 * NOTE! Do _not_ dereference the pointers before we have
609 * validated them. We can test the pointer values, but we
610 * must not actually use them until we have found a valid
611 * copy of the pointer in kernel space..
613 int d_validate(struct dentry
*dentry
, struct dentry
*dparent
,
614 unsigned int hash
, unsigned int len
)
616 struct list_head
*base
, *lhp
;
619 if (dentry
!= dparent
) {
620 base
= d_hash(dparent
, hash
);
622 while ((lhp
= lhp
->next
) != base
) {
623 if (dentry
== list_entry(lhp
, struct dentry
, d_hash
))
628 * Special case: local mount points don't live in
629 * the hashes, so we search the super blocks.
631 struct super_block
*sb
= sb_entry(super_blocks
.next
);
633 for (; sb
!= sb_entry(&super_blocks
);
634 sb
= sb_entry(sb
->s_list
.next
)) {
637 if (sb
->s_root
== dentry
)
647 * When a file is deleted, we have two options:
648 * - turn this dentry into a negative dentry
649 * - unhash this dentry and free it.
651 * Usually, we want to just turn this into
652 * a negative dentry, but if anybody else is
653 * currently using the dentry or the inode
654 * we can't do that and we fall back on removing
655 * it from the hash queues and waiting for
656 * it to be deleted later when it has no users
658 void d_delete(struct dentry
* dentry
)
661 * Are we the only user?
663 if (dentry
->d_count
== 1) {
669 * If not, just drop the dentry and let dput
675 void d_rehash(struct dentry
* entry
)
677 struct dentry
* parent
= entry
->d_parent
;
679 list_add(&entry
->d_hash
, d_hash(parent
, entry
->d_name
.hash
));
682 #define do_switch(x,y) do { \
683 __typeof__ (x) __tmp = x; \
684 x = y; y = __tmp; } while (0)
687 * When switching names, the actual string doesn't strictly have to
688 * be preserved in the target - because we're dropping the target
689 * anyway. As such, we can just do a simple memcpy() to copy over
690 * the new name before we switch.
692 * Note that we have to be a lot more careful about getting the hash
693 * switched - we have to switch the hash value properly even if it
694 * then no longer matches the actual (corrupted) string of the target.
695 * The has value has to match the hash queue that the dentry is on..
697 static inline void switch_names(struct dentry
* dentry
, struct dentry
* target
)
699 const unsigned char *old_name
, *new_name
;
701 memcpy(dentry
->d_iname
, target
->d_iname
, DNAME_INLINE_LEN
);
702 old_name
= target
->d_name
.name
;
703 new_name
= dentry
->d_name
.name
;
704 if (old_name
== target
->d_iname
)
705 old_name
= dentry
->d_iname
;
706 if (new_name
== dentry
->d_iname
)
707 new_name
= target
->d_iname
;
708 target
->d_name
.name
= new_name
;
709 dentry
->d_name
.name
= old_name
;
713 * We cannibalize "target" when moving dentry on top of it,
714 * because it's going to be thrown away anyway. We could be more
715 * polite about it, though.
717 * This forceful removal will result in ugly /proc output if
718 * somebody holds a file open that got deleted due to a rename.
719 * We could be nicer about the deleted file, and let it show
720 * up under the name it got deleted rather than the name that
723 * Careful with the hash switch. The hash switch depends on
724 * the fact that any list-entry can be a head of the list.
727 void d_move(struct dentry
* dentry
, struct dentry
* target
)
729 if (!dentry
->d_inode
)
730 printk(KERN_WARNING
"VFS: moving negative dcache entry\n");
732 /* Move the dentry to the target hash queue */
733 list_del(&dentry
->d_hash
);
734 list_add(&dentry
->d_hash
, &target
->d_hash
);
736 /* Unhash the target: dput() will then get rid of it */
737 list_del(&target
->d_hash
);
738 INIT_LIST_HEAD(&target
->d_hash
);
740 list_del(&dentry
->d_child
);
741 list_del(&target
->d_child
);
743 /* Switch the parents and the names.. */
744 switch_names(dentry
, target
);
745 do_switch(dentry
->d_parent
, target
->d_parent
);
746 do_switch(dentry
->d_name
.len
, target
->d_name
.len
);
747 do_switch(dentry
->d_name
.hash
, target
->d_name
.hash
);
749 /* And add them back to the (new) parent lists */
750 list_add(&target
->d_child
, &target
->d_parent
->d_subdirs
);
751 list_add(&dentry
->d_child
, &dentry
->d_parent
->d_subdirs
);
755 * "buflen" should be PAGE_SIZE or more.
757 char * d_path(struct dentry
*dentry
, char *buffer
, int buflen
)
759 char * end
= buffer
+buflen
;
761 struct dentry
* root
= current
->fs
->root
;
765 if (dentry
->d_parent
!= dentry
&& list_empty(&dentry
->d_hash
)) {
768 memcpy(end
, " (deleted)", 10);
776 struct dentry
* parent
;
781 dentry
= dentry
->d_covers
;
782 parent
= dentry
->d_parent
;
783 if (dentry
== parent
)
785 namelen
= dentry
->d_name
.len
;
786 buflen
-= namelen
+ 1;
790 memcpy(end
, dentry
->d_name
.name
, namelen
);
799 * NOTE! The user-level library version returns a
800 * character pointer. The kernel system call just
801 * returns the length of the buffer filled (which
802 * includes the ending '\0' character), or a negative
803 * error value. So libc would do something like
805 * char *getcwd(char * buf, size_t size)
809 * retval = sys_getcwd(buf, size);
816 asmlinkage
int sys_getcwd(char *buf
, unsigned long size
)
819 struct dentry
*pwd
= current
->fs
->pwd
;
822 /* Has the current directory has been unlinked? */
823 if (pwd
->d_parent
== pwd
|| !list_empty(&pwd
->d_hash
)) {
824 char *page
= (char *) __get_free_page(GFP_USER
);
828 char * cwd
= d_path(pwd
, page
, PAGE_SIZE
);
831 len
= PAGE_SIZE
+ page
- cwd
;
834 if (copy_to_user(buf
, cwd
, len
))
837 free_page((unsigned long) page
);
844 * Test whether new_dentry is a subdirectory of old_dentry.
846 * Trivially implemented using the dcache structure
848 int is_subdir(struct dentry
* new_dentry
, struct dentry
* old_dentry
)
854 if (new_dentry
!= old_dentry
) {
855 struct dentry
* parent
= new_dentry
->d_parent
;
856 if (parent
== new_dentry
)
868 * Check whether a dentry already exists for the given name,
869 * and return the inode number if it has an inode.
871 * This routine is used to post-process directory listings for
872 * filesystems using synthetic inode numbers, and is necessary
873 * to keep getcwd() working.
875 ino_t
find_inode_number(struct dentry
*dir
, struct qstr
*name
)
877 struct dentry
* dentry
;
881 * Check for a fs-specific hash function. Note that we must
882 * calculate the standard hash first, as the d_op->d_hash()
883 * routine may choose to leave the hash value unchanged.
885 name
->hash
= full_name_hash(name
->name
, name
->len
);
886 if (dir
->d_op
&& dir
->d_op
->d_hash
)
888 if (dir
->d_op
->d_hash(dir
, name
) != 0)
892 dentry
= d_lookup(dir
, name
);
896 ino
= dentry
->d_inode
->i_ino
;
903 void __init
dcache_init(void)
906 struct list_head
*d
= dentry_hashtable
;
909 * A constructor could be added for stable state like the lists,
910 * but it is probably not worth it because of the cache nature
912 * If fragmentation is too bad then the SLAB_HWCACHE_ALIGN
913 * flag could be removed here, to hint to the allocator that
914 * it should not try to get multiple page regions.
916 dentry_cache
= kmem_cache_create("dentry_cache",
917 sizeof(struct dentry
),
922 panic("Cannot create dentry cache");