4 * Complete reimplementation
5 * (C) 1997 Thomas Schoebel-Theuer
9 * Notes on the allocation strategy:
11 * The dcache is a master of the icache - whenever a dcache entry
12 * exists, the inode will always exist. "iput()" is done either when
13 * the dcache entry is deleted or garbage collected.
16 #include <linux/string.h>
19 #include <linux/malloc.h>
20 #include <linux/slab.h>
21 #include <linux/init.h>
23 #include <asm/uaccess.h>
25 #define DCACHE_PARANOIA 1
26 /* #define DCACHE_DEBUG 1 */
28 /* For managing the dcache */
29 extern unsigned long num_physpages
, page_cache_size
;
30 extern int inodes_stat
[];
31 #define nr_inodes (inodes_stat[0])
33 kmem_cache_t
*dentry_cache
;
36 * This is the single most critical data structure when it comes
37 * to the dcache: the hashtable for lookups. Somebody should try
38 * to make this good - I've just made it work.
40 * This hash-function tries to avoid losing too many bits of hash
41 * information, yet avoid using a prime hash-size or similar.
44 #define D_HASHSIZE (1UL << D_HASHBITS)
45 #define D_HASHMASK (D_HASHSIZE-1)
47 static struct list_head dentry_hashtable
[D_HASHSIZE
];
48 static LIST_HEAD(dentry_unused
);
53 int age_limit
; /* age in seconds */
54 int want_pages
; /* pages requested by system */
56 } dentry_stat
= {0, 0, 45, 0,};
58 static inline void d_free(struct dentry
*dentry
)
60 if (dentry
->d_op
&& dentry
->d_op
->d_release
)
61 dentry
->d_op
->d_release(dentry
);
62 if (dname_external(dentry
))
63 kfree(dentry
->d_name
.name
);
64 kmem_cache_free(dentry_cache
, dentry
);
68 * Release the dentry's inode, using the fileystem
69 * d_iput() operation if defined.
71 static inline void dentry_iput(struct dentry
* dentry
)
73 struct inode
*inode
= dentry
->d_inode
;
75 dentry
->d_inode
= NULL
;
76 list_del(&dentry
->d_alias
);
77 INIT_LIST_HEAD(&dentry
->d_alias
);
78 if (dentry
->d_op
&& dentry
->d_op
->d_iput
)
79 dentry
->d_op
->d_iput(dentry
, inode
);
88 * This is complicated by the fact that we do not want to put
89 * dentries that are no longer on any hash chain on the unused
90 * list: we'd much rather just get rid of them immediately.
92 * However, that implies that we have to traverse the dentry
93 * tree upwards to the parents which might _also_ now be
94 * scheduled for deletion (it may have been only waiting for
95 * its last child to go away).
97 * This tail recursion is done by hand as we don't want to depend
98 * on the compiler to always get this right (gcc generally doesn't).
99 * Real recursion would eat up our stack space.
101 void dput(struct dentry
*dentry
)
109 count
= dentry
->d_count
- 1;
114 * Note that if d_op->d_delete blocks,
115 * the dentry could go back in use.
116 * Each fs will have to watch for this.
118 if (dentry
->d_op
&& dentry
->d_op
->d_delete
) {
119 dentry
->d_op
->d_delete(dentry
);
121 count
= dentry
->d_count
- 1;
126 if (!list_empty(&dentry
->d_lru
)) {
127 dentry_stat
.nr_unused
--;
128 list_del(&dentry
->d_lru
);
130 if (list_empty(&dentry
->d_hash
)) {
131 struct dentry
* parent
;
133 list_del(&dentry
->d_child
);
135 parent
= dentry
->d_parent
;
137 if (dentry
== parent
)
142 list_add(&dentry
->d_lru
, &dentry_unused
);
143 dentry_stat
.nr_unused
++;
145 * Update the timestamp
147 dentry
->d_reftime
= jiffies
;
151 dentry
->d_count
= count
;
155 printk(KERN_CRIT
"Negative d_count (%d) for %s/%s\n",
157 dentry
->d_parent
->d_name
.name
,
158 dentry
->d_name
.name
);
163 * Try to invalidate the dentry if it turns out to be
164 * possible. If there are other dentries that can be
165 * reached through this one we can't delete it.
167 int d_invalidate(struct dentry
* dentry
)
170 * Check whether to do a partial shrink_dcache
171 * to get rid of unused child entries.
173 if (!list_empty(&dentry
->d_subdirs
)) {
174 shrink_dcache_parent(dentry
);
178 * Somebody else still using it?
180 * If it's a directory, we can't drop it
181 * for fear of somebody re-populating it
182 * with children (even though dropping it
183 * would make it unreachable from the root,
184 * we might still populate it if it was a
185 * working directory or similar).
187 if (dentry
->d_count
> 1) {
188 if (dentry
->d_inode
&& S_ISDIR(dentry
->d_inode
->i_mode
))
197 * Select less valuable dentries to be pruned when we need
198 * inodes or memory. The selected dentries are moved to the
199 * old end of the list where prune_dcache() can find them.
201 * Negative dentries are included in the selection so that
202 * they don't accumulate at the end of the list. The count
203 * returned is the total number of dentries selected, which
204 * may be much larger than the requested number of inodes.
206 int select_dcache(int inode_count
, int page_count
)
208 struct list_head
*next
, *tail
= &dentry_unused
;
210 int depth
= dentry_stat
.nr_unused
>> 1;
211 unsigned long max_value
= 4;
217 while (next
!= &dentry_unused
&& depth
--) {
218 struct list_head
*tmp
= next
;
219 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_lru
);
220 struct inode
*inode
= dentry
->d_inode
;
221 unsigned long value
= 0;
224 if (dentry
->d_count
) {
225 dentry_stat
.nr_unused
--;
232 * Select dentries based on the page cache count ...
233 * should factor in number of uses as well. We take
234 * all negative dentries so that they don't accumulate.
235 * (We skip inodes that aren't immediately available.)
238 value
= inode
->i_nrpages
;
239 if (value
>= max_value
)
241 if (inode
->i_state
|| inode
->i_count
> 1)
246 * Move the selected dentries behind the tail.
248 if (tmp
!= tail
->prev
) {
250 list_add(tmp
, tail
->prev
);
254 if (inode
&& --inode_count
<= 0)
256 if (page_count
&& (page_count
-= value
) <= 0)
263 * Throw away a dentry - free the inode, dput the parent.
264 * This requires that the LRU list has already been
267 static inline void prune_one_dentry(struct dentry
* dentry
)
269 struct dentry
* parent
;
271 list_del(&dentry
->d_hash
);
272 list_del(&dentry
->d_child
);
274 parent
= dentry
->d_parent
;
280 * Shrink the dcache. This is done when we need
281 * more memory, or simply when we need to unmount
282 * something (at which point we need to unuse
285 void prune_dcache(int count
)
288 struct dentry
*dentry
;
289 struct list_head
*tmp
= dentry_unused
.prev
;
291 if (tmp
== &dentry_unused
)
293 dentry_stat
.nr_unused
--;
296 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
297 if (!dentry
->d_count
) {
298 prune_one_dentry(dentry
);
306 * Shrink the dcache for the specified super block.
307 * This allows us to unmount a device without disturbing
308 * the dcache for the other devices.
310 * This implementation makes just two traversals of the
311 * unused list. On the first pass we move the selected
312 * dentries to the most recent end, and on the second
313 * pass we free them. The second pass must restart after
314 * each dput(), but since the target dentries are all at
315 * the end, it's really just a single traversal.
317 void shrink_dcache_sb(struct super_block
* sb
)
319 struct list_head
*tmp
, *next
;
320 struct dentry
*dentry
;
323 * Pass one ... move the dentries for the specified
324 * superblock to the most recent end of the unused list.
326 next
= dentry_unused
.next
;
327 while (next
!= &dentry_unused
) {
330 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
331 if (dentry
->d_sb
!= sb
)
334 list_add(tmp
, &dentry_unused
);
338 * Pass two ... free the dentries for this superblock.
341 next
= dentry_unused
.next
;
342 while (next
!= &dentry_unused
) {
345 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
346 if (dentry
->d_sb
!= sb
)
350 dentry_stat
.nr_unused
--;
353 prune_one_dentry(dentry
);
359 * Check whether a root dentry would be in use if all of its
360 * child dentries were freed. This allows a non-destructive
361 * test for unmounting a device.
363 int is_root_busy(struct dentry
*root
)
365 struct dentry
*this_parent
= root
;
366 struct list_head
*next
;
367 int count
= root
->d_count
;
370 next
= this_parent
->d_subdirs
.next
;
372 while (next
!= &this_parent
->d_subdirs
) {
373 struct list_head
*tmp
= next
;
374 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
376 /* Decrement count for unused children */
377 count
+= (dentry
->d_count
- 1);
378 if (!list_empty(&dentry
->d_subdirs
)) {
379 this_parent
= dentry
;
382 /* root is busy if any leaf is busy */
387 * All done at this level ... ascend and resume the search.
389 if (this_parent
!= root
) {
390 next
= this_parent
->d_child
.next
;
391 this_parent
= this_parent
->d_parent
;
394 return (count
> 1); /* remaining users? */
398 * Search the dentry child list for the specified parent,
399 * and move any unused dentries to the end of the unused
400 * list for prune_dcache(). We descend to the next level
401 * whenever the d_subdirs list is non-empty and continue
404 static int select_parent(struct dentry
* parent
)
406 struct dentry
*this_parent
= parent
;
407 struct list_head
*next
;
411 next
= this_parent
->d_subdirs
.next
;
413 while (next
!= &this_parent
->d_subdirs
) {
414 struct list_head
*tmp
= next
;
415 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
417 if (!dentry
->d_count
) {
418 list_del(&dentry
->d_lru
);
419 list_add(&dentry
->d_lru
, dentry_unused
.prev
);
423 * Descend a level if the d_subdirs list is non-empty.
425 if (!list_empty(&dentry
->d_subdirs
)) {
426 this_parent
= dentry
;
428 printk(KERN_DEBUG
"select_parent: descending to %s/%s, found=%d\n",
429 dentry
->d_parent
->d_name
.name
, dentry
->d_name
.name
, found
);
435 * All done at this level ... ascend and resume the search.
437 if (this_parent
!= parent
) {
438 next
= this_parent
->d_child
.next
;
439 this_parent
= this_parent
->d_parent
;
441 printk(KERN_DEBUG
"select_parent: ascending to %s/%s, found=%d\n",
442 this_parent
->d_parent
->d_name
.name
, this_parent
->d_name
.name
, found
);
450 * Prune the dcache to remove unused children of the parent dentry.
452 void shrink_dcache_parent(struct dentry
* parent
)
456 while ((found
= select_parent(parent
)) != 0)
461 * This is called from kswapd when we think we need some
462 * more memory, but aren't really sure how much. So we
463 * carefully try to free a _bit_ of our dcache, but not
467 * 0 - very urgent: shrink everything
469 * 6 - base-level: try to shrink a bit.
471 void shrink_dcache_memory(int priority
, unsigned int gfp_mask
)
476 #define NAME_ALLOC_LEN(len) ((len+16) & ~15)
478 struct dentry
* d_alloc(struct dentry
* parent
, const struct qstr
*name
)
481 struct dentry
*dentry
;
483 dentry
= kmem_cache_alloc(dentry_cache
, GFP_KERNEL
);
487 if (name
->len
> DNAME_INLINE_LEN
-1) {
488 str
= kmalloc(NAME_ALLOC_LEN(name
->len
), GFP_KERNEL
);
490 kmem_cache_free(dentry_cache
, dentry
);
494 str
= dentry
->d_iname
;
496 memcpy(str
, name
->name
, name
->len
);
501 dentry
->d_inode
= NULL
;
502 dentry
->d_parent
= NULL
;
505 dentry
->d_parent
= dget(parent
);
506 dentry
->d_sb
= parent
->d_sb
;
507 list_add(&dentry
->d_child
, &parent
->d_subdirs
);
509 INIT_LIST_HEAD(&dentry
->d_child
);
511 dentry
->d_mounts
= dentry
;
512 dentry
->d_covers
= dentry
;
513 INIT_LIST_HEAD(&dentry
->d_hash
);
514 INIT_LIST_HEAD(&dentry
->d_lru
);
515 INIT_LIST_HEAD(&dentry
->d_subdirs
);
516 INIT_LIST_HEAD(&dentry
->d_alias
);
518 dentry
->d_name
.name
= str
;
519 dentry
->d_name
.len
= name
->len
;
520 dentry
->d_name
.hash
= name
->hash
;
522 dentry
->d_fsdata
= NULL
;
527 * Fill in inode information in the entry.
529 * This turns negative dentries into productive full members
532 * NOTE! This assumes that the inode count has been incremented
533 * (or otherwise set) by the caller to indicate that it is now
534 * in use by the dcache..
536 void d_instantiate(struct dentry
*entry
, struct inode
* inode
)
539 list_add(&entry
->d_alias
, &inode
->i_dentry
);
540 entry
->d_inode
= inode
;
543 struct dentry
* d_alloc_root(struct inode
* root_inode
, struct dentry
*old_root
)
545 struct dentry
*res
= NULL
;
548 res
= d_alloc(NULL
, &(const struct qstr
) { "/", 1, 0 });
550 res
->d_sb
= root_inode
->i_sb
;
552 d_instantiate(res
, root_inode
);
558 static inline struct list_head
* d_hash(struct dentry
* parent
, unsigned long hash
)
560 hash
+= (unsigned long) parent
;
561 hash
= hash
^ (hash
>> D_HASHBITS
) ^ (hash
>> D_HASHBITS
*2);
562 return dentry_hashtable
+ (hash
& D_HASHMASK
);
565 struct dentry
* d_lookup(struct dentry
* parent
, struct qstr
* name
)
567 unsigned int len
= name
->len
;
568 unsigned int hash
= name
->hash
;
569 const unsigned char *str
= name
->name
;
570 struct list_head
*head
= d_hash(parent
,hash
);
571 struct list_head
*tmp
= head
->next
;
574 struct dentry
* dentry
= list_entry(tmp
, struct dentry
, d_hash
);
578 if (dentry
->d_name
.hash
!= hash
)
580 if (dentry
->d_parent
!= parent
)
582 if (parent
->d_op
&& parent
->d_op
->d_compare
) {
583 if (parent
->d_op
->d_compare(parent
, &dentry
->d_name
, name
))
586 if (dentry
->d_name
.len
!= len
)
588 if (memcmp(dentry
->d_name
.name
, str
, len
))
597 * An insecure source has sent us a dentry, here we verify it.
599 * This is just to make knfsd able to have the dentry pointer
600 * in the NFS file handle.
602 * NOTE! Do _not_ dereference the pointers before we have
603 * validated them. We can test the pointer values, but we
604 * must not actually use them until we have found a valid
605 * copy of the pointer in kernel space..
607 int d_validate(struct dentry
*dentry
, struct dentry
*dparent
,
608 unsigned int hash
, unsigned int len
)
610 struct list_head
*base
, *lhp
;
613 if (dentry
!= dparent
) {
614 base
= d_hash(dparent
, hash
);
616 while ((lhp
= lhp
->next
) != base
) {
617 if (dentry
== list_entry(lhp
, struct dentry
, d_hash
))
622 * Special case: local mount points don't live in
623 * the hashes, so we search the super blocks.
625 struct super_block
*sb
= sb_entry(super_blocks
.next
);
627 for (; sb
!= sb_entry(&super_blocks
);
628 sb
= sb_entry(sb
->s_list
.next
)) {
631 if (sb
->s_root
== dentry
)
641 * When a file is deleted, we have two options:
642 * - turn this dentry into a negative dentry
643 * - unhash this dentry and free it.
645 * Usually, we want to just turn this into
646 * a negative dentry, but if anybody else is
647 * currently using the dentry or the inode
648 * we can't do that and we fall back on removing
649 * it from the hash queues and waiting for
650 * it to be deleted later when it has no users
652 void d_delete(struct dentry
* dentry
)
655 * Are we the only user?
657 if (dentry
->d_count
== 1) {
663 * If not, just drop the dentry and let dput
669 void d_rehash(struct dentry
* entry
)
671 struct dentry
* parent
= entry
->d_parent
;
673 list_add(&entry
->d_hash
, d_hash(parent
, entry
->d_name
.hash
));
676 #define do_switch(x,y) do { \
677 __typeof__ (x) __tmp = x; \
678 x = y; y = __tmp; } while (0)
681 * When switching names, the actual string doesn't strictly have to
682 * be preserved in the target - because we're dropping the target
683 * anyway. As such, we can just do a simple memcpy() to copy over
684 * the new name before we switch.
686 * Note that we have to be a lot more careful about getting the hash
687 * switched - we have to switch the hash value properly even if it
688 * then no longer matches the actual (corrupted) string of the target.
689 * The has value has to match the hash queue that the dentry is on..
691 static inline void switch_names(struct dentry
* dentry
, struct dentry
* target
)
693 const unsigned char *old_name
, *new_name
;
695 memcpy(dentry
->d_iname
, target
->d_iname
, DNAME_INLINE_LEN
);
696 old_name
= target
->d_name
.name
;
697 new_name
= dentry
->d_name
.name
;
698 if (old_name
== target
->d_iname
)
699 old_name
= dentry
->d_iname
;
700 if (new_name
== dentry
->d_iname
)
701 new_name
= target
->d_iname
;
702 target
->d_name
.name
= new_name
;
703 dentry
->d_name
.name
= old_name
;
707 * We cannibalize "target" when moving dentry on top of it,
708 * because it's going to be thrown away anyway. We could be more
709 * polite about it, though.
711 * This forceful removal will result in ugly /proc output if
712 * somebody holds a file open that got deleted due to a rename.
713 * We could be nicer about the deleted file, and let it show
714 * up under the name it got deleted rather than the name that
717 * Careful with the hash switch. The hash switch depends on
718 * the fact that any list-entry can be a head of the list.
721 void d_move(struct dentry
* dentry
, struct dentry
* target
)
723 if (!dentry
->d_inode
)
724 printk(KERN_WARNING
"VFS: moving negative dcache entry\n");
726 /* Move the dentry to the target hash queue */
727 list_del(&dentry
->d_hash
);
728 list_add(&dentry
->d_hash
, &target
->d_hash
);
730 /* Unhash the target: dput() will then get rid of it */
731 list_del(&target
->d_hash
);
732 INIT_LIST_HEAD(&target
->d_hash
);
734 list_del(&dentry
->d_child
);
735 list_del(&target
->d_child
);
737 /* Switch the parents and the names.. */
738 switch_names(dentry
, target
);
739 do_switch(dentry
->d_parent
, target
->d_parent
);
740 do_switch(dentry
->d_name
.len
, target
->d_name
.len
);
741 do_switch(dentry
->d_name
.hash
, target
->d_name
.hash
);
743 /* And add them back to the (new) parent lists */
744 list_add(&target
->d_child
, &target
->d_parent
->d_subdirs
);
745 list_add(&dentry
->d_child
, &dentry
->d_parent
->d_subdirs
);
749 * "buflen" should be PAGE_SIZE or more.
751 char * d_path(struct dentry
*dentry
, char *buffer
, int buflen
)
753 char * end
= buffer
+buflen
;
755 struct dentry
* root
= current
->fs
->root
;
759 if (dentry
->d_parent
!= dentry
&& list_empty(&dentry
->d_hash
)) {
762 memcpy(end
, " (deleted)", 10);
770 struct dentry
* parent
;
775 dentry
= dentry
->d_covers
;
776 parent
= dentry
->d_parent
;
777 if (dentry
== parent
)
779 namelen
= dentry
->d_name
.len
;
780 buflen
-= namelen
+ 1;
784 memcpy(end
, dentry
->d_name
.name
, namelen
);
793 * NOTE! The user-level library version returns a
794 * character pointer. The kernel system call just
795 * returns the length of the buffer filled (which
796 * includes the ending '\0' character), or a negative
797 * error value. So libc would do something like
799 * char *getcwd(char * buf, size_t size)
803 * retval = sys_getcwd(buf, size);
810 asmlinkage
int sys_getcwd(char *buf
, unsigned long size
)
813 struct dentry
*pwd
= current
->fs
->pwd
;
816 /* Has the current directory has been unlinked? */
817 if (pwd
->d_parent
== pwd
|| !list_empty(&pwd
->d_hash
)) {
818 char *page
= (char *) __get_free_page(GFP_USER
);
822 char * cwd
= d_path(pwd
, page
, PAGE_SIZE
);
825 len
= PAGE_SIZE
+ page
- cwd
;
828 if (copy_to_user(buf
, cwd
, len
))
831 free_page((unsigned long) page
);
838 * Test whether new_dentry is a subdirectory of old_dentry.
840 * Trivially implemented using the dcache structure
842 int is_subdir(struct dentry
* new_dentry
, struct dentry
* old_dentry
)
848 if (new_dentry
!= old_dentry
) {
849 struct dentry
* parent
= new_dentry
->d_parent
;
850 if (parent
== new_dentry
)
862 * Check whether a dentry already exists for the given name,
863 * and return the inode number if it has an inode.
865 * This routine is used to post-process directory listings for
866 * filesystems using synthetic inode numbers, and is necessary
867 * to keep getcwd() working.
869 ino_t
find_inode_number(struct dentry
*dir
, struct qstr
*name
)
871 struct dentry
* dentry
;
875 * Check for a fs-specific hash function. Note that we must
876 * calculate the standard hash first, as the d_op->d_hash()
877 * routine may choose to leave the hash value unchanged.
879 name
->hash
= full_name_hash(name
->name
, name
->len
);
880 if (dir
->d_op
&& dir
->d_op
->d_hash
)
882 if (dir
->d_op
->d_hash(dir
, name
) != 0)
886 dentry
= d_lookup(dir
, name
);
890 ino
= dentry
->d_inode
->i_ino
;
897 void __init
dcache_init(void)
900 struct list_head
*d
= dentry_hashtable
;
903 * A constructor could be added for stable state like the lists,
904 * but it is probably not worth it because of the cache nature
906 * If fragmentation is too bad then the SLAB_HWCACHE_ALIGN
907 * flag could be removed here, to hint to the allocator that
908 * it should not try to get multiple page regions.
910 dentry_cache
= kmem_cache_create("dentry_cache",
911 sizeof(struct dentry
),
916 panic("Cannot create dentry cache");