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/init.h>
22 #include <asm/uaccess.h>
24 #define DCACHE_PARANOIA 1
25 /* #define DCACHE_DEBUG 1 */
27 /* For managing the dcache */
28 extern unsigned long num_physpages
, page_cache_size
;
29 extern int inodes_stat
[];
30 #define nr_inodes (inodes_stat[0])
33 * This is the single most critical data structure when it comes
34 * to the dcache: the hashtable for lookups. Somebody should try
35 * to make this good - I've just made it work.
37 * This hash-function tries to avoid losing too many bits of hash
38 * information, yet avoid using a prime hash-size or similar.
41 #define D_HASHSIZE (1UL << D_HASHBITS)
42 #define D_HASHMASK (D_HASHSIZE-1)
44 static struct list_head dentry_hashtable
[D_HASHSIZE
];
45 static LIST_HEAD(dentry_unused
);
50 int age_limit
; /* age in seconds */
51 int want_pages
; /* pages requested by system */
53 } dentry_stat
= {0, 0, 45, 0,};
55 static inline void d_free(struct dentry
*dentry
)
57 if (dentry
->d_op
&& dentry
->d_op
->d_release
)
58 dentry
->d_op
->d_release(dentry
);
59 kfree(dentry
->d_name
.name
);
64 * Release the dentry's inode, using the fileystem
65 * d_iput() operation if defined.
67 static inline void dentry_iput(struct dentry
* dentry
)
69 struct inode
*inode
= dentry
->d_inode
;
71 dentry
->d_inode
= NULL
;
72 list_del(&dentry
->d_alias
);
73 INIT_LIST_HEAD(&dentry
->d_alias
);
74 if (dentry
->d_op
&& dentry
->d_op
->d_iput
)
75 dentry
->d_op
->d_iput(dentry
, inode
);
84 * This is complicated by the fact that we do not want to put
85 * dentries that are no longer on any hash chain on the unused
86 * list: we'd much rather just get rid of them immediately.
88 * However, that implies that we have to traverse the dentry
89 * tree upwards to the parents which might _also_ now be
90 * scheduled for deletion (it may have been only waiting for
91 * its last child to go away).
93 * This tail recursion is done by hand as we don't want to depend
94 * on the compiler to always get this right (gcc generally doesn't).
95 * Real recursion would eat up our stack space.
97 void dput(struct dentry
*dentry
)
105 count
= dentry
->d_count
- 1;
110 * Note that if d_op->d_delete blocks,
111 * the dentry could go back in use.
112 * Each fs will have to watch for this.
114 if (dentry
->d_op
&& dentry
->d_op
->d_delete
) {
115 dentry
->d_op
->d_delete(dentry
);
117 count
= dentry
->d_count
- 1;
122 if (!list_empty(&dentry
->d_lru
)) {
123 dentry_stat
.nr_unused
--;
124 list_del(&dentry
->d_lru
);
126 if (list_empty(&dentry
->d_hash
)) {
127 struct dentry
* parent
;
129 list_del(&dentry
->d_child
);
131 parent
= dentry
->d_parent
;
133 if (dentry
== parent
)
138 list_add(&dentry
->d_lru
, &dentry_unused
);
139 dentry_stat
.nr_unused
++;
141 * Update the timestamp
143 dentry
->d_reftime
= jiffies
;
147 dentry
->d_count
= count
;
151 printk(KERN_CRIT
"Negative d_count (%d) for %s/%s\n",
153 dentry
->d_parent
->d_name
.name
,
154 dentry
->d_name
.name
);
159 * Try to invalidate the dentry if it turns out to be
160 * possible. If there are other users of the dentry we
161 * can't invalidate it.
163 int d_invalidate(struct dentry
* dentry
)
165 /* Check whether to do a partial shrink_dcache */
166 if (!list_empty(&dentry
->d_subdirs
))
167 shrink_dcache_parent(dentry
);
169 if (dentry
->d_count
!= 1)
177 * Select less valuable dentries to be pruned when we need
178 * inodes or memory. The selected dentries are moved to the
179 * old end of the list where prune_dcache() can find them.
181 * Negative dentries are included in the selection so that
182 * they don't accumulate at the end of the list. The count
183 * returned is the total number of dentries selected, which
184 * may be much larger than the requested number of inodes.
186 int select_dcache(int inode_count
, int page_count
)
188 struct list_head
*next
, *tail
= &dentry_unused
;
189 int found
= 0, forward
= 0, young
= 8;
190 int depth
= dentry_stat
.nr_unused
>> 1;
191 unsigned long min_value
= 0, max_value
= 4;
197 while (next
!= &dentry_unused
&& depth
--) {
198 struct list_head
*tmp
= next
;
199 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_lru
);
200 struct inode
*inode
= dentry
->d_inode
;
201 unsigned long value
= 0;
206 if (dentry
->d_count
) {
207 dentry_stat
.nr_unused
--;
213 * Check the dentry's age to see whether to change direction.
216 int age
= (jiffies
- dentry
->d_reftime
) / HZ
;
217 if (age
< dentry_stat
.age_limit
) {
220 next
= dentry_unused
.next
;
222 * Update the limits -- we don't want
223 * files with too few or too many pages.
230 printk("select_dcache: %s/%s age=%d, scanning forward\n",
231 dentry
->d_parent
->d_name
.name
, dentry
->d_name
.name
, age
);
239 * Select dentries based on the page cache count ...
240 * should factor in number of uses as well. We take
241 * all negative dentries so that they don't accumulate.
242 * (We skip inodes that aren't immediately available.)
245 value
= inode
->i_nrpages
;
246 if (value
>= max_value
|| value
< min_value
)
248 if (inode
->i_state
|| inode
->i_count
> 1)
253 * Move the selected dentries behind the tail.
255 if (tmp
!= tail
->prev
) {
257 list_add(tmp
, tail
->prev
);
261 if (inode
&& --inode_count
<= 0)
263 if (page_count
&& (page_count
-= value
) <= 0)
270 * Throw away a dentry - free the inode, dput the parent.
271 * This requires that the LRU list has already been
274 static inline void prune_one_dentry(struct dentry
* dentry
)
276 struct dentry
* parent
;
278 list_del(&dentry
->d_hash
);
279 list_del(&dentry
->d_child
);
281 parent
= dentry
->d_parent
;
287 * Shrink the dcache. This is done when we need
288 * more memory, or simply when we need to unmount
289 * something (at which point we need to unuse
292 void prune_dcache(int count
)
295 struct dentry
*dentry
;
296 struct list_head
*tmp
= dentry_unused
.prev
;
298 if (tmp
== &dentry_unused
)
300 dentry_stat
.nr_unused
--;
303 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
304 if (!dentry
->d_count
) {
305 prune_one_dentry(dentry
);
313 * Shrink the dcache for the specified super block.
314 * This allows us to unmount a device without disturbing
315 * the dcache for the other devices.
317 * This implementation makes just two traversals of the
318 * unused list. On the first pass we move the selected
319 * dentries to the most recent end, and on the second
320 * pass we free them. The second pass must restart after
321 * each dput(), but since the target dentries are all at
322 * the end, it's really just a single traversal.
324 void shrink_dcache_sb(struct super_block
* sb
)
326 struct list_head
*tmp
, *next
;
327 struct dentry
*dentry
;
330 * Pass one ... move the dentries for the specified
331 * superblock to the most recent end of the unused list.
333 next
= dentry_unused
.next
;
334 while (next
!= &dentry_unused
) {
337 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
338 if (dentry
->d_sb
!= sb
)
341 list_add(tmp
, &dentry_unused
);
345 * Pass two ... free the dentries for this superblock.
348 next
= dentry_unused
.next
;
349 while (next
!= &dentry_unused
) {
352 dentry
= list_entry(tmp
, struct dentry
, d_lru
);
353 if (dentry
->d_sb
!= sb
)
357 dentry_stat
.nr_unused
--;
360 prune_one_dentry(dentry
);
366 * Check whether a root dentry would be in use if all of its
367 * child dentries were freed. This allows a non-destructive
368 * test for unmounting a device.
370 int is_root_busy(struct dentry
*root
)
372 struct dentry
*this_parent
= root
;
373 struct list_head
*next
;
374 int count
= root
->d_count
;
377 next
= this_parent
->d_subdirs
.next
;
379 while (next
!= &this_parent
->d_subdirs
) {
380 struct list_head
*tmp
= next
;
381 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
383 /* Decrement count for unused children */
384 count
+= (dentry
->d_count
- 1);
385 if (!list_empty(&dentry
->d_subdirs
)) {
386 this_parent
= dentry
;
389 /* root is busy if any leaf is busy */
394 * All done at this level ... ascend and resume the search.
396 if (this_parent
!= root
) {
397 next
= this_parent
->d_child
.next
;
398 this_parent
= this_parent
->d_parent
;
401 return (count
== 1); /* one remaining use count? */
405 * Search the dentry child list for the specified parent,
406 * and move any unused dentries to the end of the unused
407 * list for prune_dcache(). We descend to the next level
408 * whenever the d_subdirs list is non-empty and continue
411 static int select_parent(struct dentry
* parent
)
413 struct dentry
*this_parent
= parent
;
414 struct list_head
*next
;
418 next
= this_parent
->d_subdirs
.next
;
420 while (next
!= &this_parent
->d_subdirs
) {
421 struct list_head
*tmp
= next
;
422 struct dentry
*dentry
= list_entry(tmp
, struct dentry
, d_child
);
424 if (!dentry
->d_count
) {
425 list_del(&dentry
->d_lru
);
426 list_add(&dentry
->d_lru
, dentry_unused
.prev
);
430 * Descend a level if the d_subdirs list is non-empty.
432 if (!list_empty(&dentry
->d_subdirs
)) {
433 this_parent
= dentry
;
435 printk(KERN_DEBUG
"select_parent: descending to %s/%s, found=%d\n",
436 dentry
->d_parent
->d_name
.name
, dentry
->d_name
.name
, found
);
442 * All done at this level ... ascend and resume the search.
444 if (this_parent
!= parent
) {
445 next
= this_parent
->d_child
.next
;
446 this_parent
= this_parent
->d_parent
;
448 printk(KERN_DEBUG
"select_parent: ascending to %s/%s, found=%d\n",
449 this_parent
->d_parent
->d_name
.name
, this_parent
->d_name
.name
, found
);
457 * Prune the dcache to remove unused children of the parent dentry.
459 void shrink_dcache_parent(struct dentry
* parent
)
463 while ((found
= select_parent(parent
)) != 0)
468 * This is called from kswapd when we think we need some
469 * more memory, but aren't really sure how much. So we
470 * carefully try to free a _bit_ of our dcache, but not
474 * 0 - very urgent: schrink everything
476 * 6 - base-level: try to shrink a bit.
478 void shrink_dcache_memory(int priority
, unsigned int gfp_mask
)
483 #define NAME_ALLOC_LEN(len) ((len+16) & ~15)
485 struct dentry
* d_alloc(struct dentry
* parent
, const struct qstr
*name
)
488 struct dentry
*dentry
;
491 * Prune the dcache if there are too many unused dentries.
493 if (dentry_stat
.nr_unused
> 3*(nr_inodes
>> 1)) {
495 printk("d_alloc: %d unused, pruning dcache\n", dentry_stat
.nr_unused
);
498 free_inode_memory(8);
501 dentry
= kmalloc(sizeof(struct dentry
), GFP_KERNEL
);
505 str
= kmalloc(NAME_ALLOC_LEN(name
->len
), GFP_KERNEL
);
511 memcpy(str
, name
->name
, name
->len
);
516 dentry
->d_inode
= NULL
;
517 dentry
->d_parent
= NULL
;
520 dentry
->d_parent
= dget(parent
);
521 dentry
->d_sb
= parent
->d_sb
;
522 list_add(&dentry
->d_child
, &parent
->d_subdirs
);
524 INIT_LIST_HEAD(&dentry
->d_child
);
526 dentry
->d_mounts
= dentry
;
527 dentry
->d_covers
= dentry
;
528 INIT_LIST_HEAD(&dentry
->d_hash
);
529 INIT_LIST_HEAD(&dentry
->d_lru
);
530 INIT_LIST_HEAD(&dentry
->d_subdirs
);
531 INIT_LIST_HEAD(&dentry
->d_alias
);
533 dentry
->d_name
.name
= str
;
534 dentry
->d_name
.len
= name
->len
;
535 dentry
->d_name
.hash
= name
->hash
;
537 dentry
->d_fsdata
= NULL
;
542 * Fill in inode information in the entry.
544 * This turns negative dentries into productive full members
547 * NOTE! This assumes that the inode count has been incremented
548 * (or otherwise set) by the caller to indicate that it is now
549 * in use by the dcache..
551 void d_instantiate(struct dentry
*entry
, struct inode
* inode
)
554 list_add(&entry
->d_alias
, &inode
->i_dentry
);
555 entry
->d_inode
= inode
;
558 struct dentry
* d_alloc_root(struct inode
* root_inode
, struct dentry
*old_root
)
560 struct dentry
*res
= NULL
;
563 res
= d_alloc(NULL
, &(const struct qstr
) { "/", 1, 0 });
565 res
->d_sb
= root_inode
->i_sb
;
567 d_instantiate(res
, root_inode
);
573 static inline struct list_head
* d_hash(struct dentry
* parent
, unsigned long hash
)
575 hash
+= (unsigned long) parent
;
576 hash
= hash
^ (hash
>> D_HASHBITS
) ^ (hash
>> D_HASHBITS
*2);
577 return dentry_hashtable
+ (hash
& D_HASHMASK
);
580 struct dentry
* d_lookup(struct dentry
* parent
, struct qstr
* name
)
582 unsigned int len
= name
->len
;
583 unsigned int hash
= name
->hash
;
584 const unsigned char *str
= name
->name
;
585 struct list_head
*head
= d_hash(parent
,hash
);
586 struct list_head
*tmp
= head
->next
;
588 while (tmp
!= head
) {
589 struct dentry
* dentry
= list_entry(tmp
, struct dentry
, d_hash
);
592 if (dentry
->d_name
.hash
!= hash
)
594 if (dentry
->d_parent
!= parent
)
596 if (parent
->d_op
&& parent
->d_op
->d_compare
) {
597 if (parent
->d_op
->d_compare(parent
, &dentry
->d_name
, name
))
600 if (dentry
->d_name
.len
!= len
)
602 if (memcmp(dentry
->d_name
.name
, str
, len
))
611 * An insecure source has sent us a dentry, here we verify it.
613 * This is just to make knfsd able to have the dentry pointer
614 * in the NFS file handle.
616 * NOTE! Do _not_ dereference the pointers before we have
617 * validated them. We can test the pointer values, but we
618 * must not actually use them until we have found a valid
619 * copy of the pointer in kernel space..
621 int d_validate(struct dentry
*dentry
, struct dentry
*dparent
,
622 unsigned int hash
, unsigned int len
)
624 struct list_head
*base
, *lhp
;
627 if (dentry
!= dparent
) {
628 base
= d_hash(dparent
, hash
);
630 while ((lhp
= lhp
->next
) != base
) {
631 if (dentry
== list_entry(lhp
, struct dentry
, d_hash
))
636 * Special case: local mount points don't live in
637 * the hashes, so we search the super blocks.
639 struct super_block
*sb
= super_blocks
+ 0;
641 for (; sb
< super_blocks
+ NR_SUPER
; sb
++) {
644 if (sb
->s_root
== dentry
)
654 * When a file is deleted, we have two options:
655 * - turn this dentry into a negative dentry
656 * - unhash this dentry and free it.
658 * Usually, we want to just turn this into
659 * a negative dentry, but if anybody else is
660 * currently using the dentry or the inode
661 * we can't do that and we fall back on removing
662 * it from the hash queues and waiting for
663 * it to be deleted later when it has no users
665 void d_delete(struct dentry
* dentry
)
668 * Are we the only user?
670 if (dentry
->d_count
== 1) {
676 * If not, just drop the dentry and let dput
682 void d_add(struct dentry
* entry
, struct inode
* inode
)
684 struct dentry
* parent
= entry
->d_parent
;
686 list_add(&entry
->d_hash
, d_hash(parent
, entry
->d_name
.hash
));
687 d_instantiate(entry
, inode
);
690 #define do_switch(x,y) do { \
691 __typeof__ (x) __tmp = x; \
692 x = y; y = __tmp; } while (0)
695 * We cannibalize "target" when moving dentry on top of it,
696 * because it's going to be thrown away anyway. We could be more
697 * polite about it, though.
699 * This forceful removal will result in ugly /proc output if
700 * somebody holds a file open that got deleted due to a rename.
701 * We could be nicer about the deleted file, and let it show
702 * up under the name it got deleted rather than the name that
705 * Careful with the hash switch. The hash switch depends on
706 * the fact that any list-entry can be a head of the list.
709 void d_move(struct dentry
* dentry
, struct dentry
* target
)
711 if (!dentry
->d_inode
)
712 printk(KERN_WARNING
"VFS: moving negative dcache entry\n");
714 /* Move the dentry to the target hash queue */
715 list_del(&dentry
->d_hash
);
716 list_add(&dentry
->d_hash
, &target
->d_hash
);
718 /* Unhash the target: dput() will then get rid of it */
719 list_del(&target
->d_hash
);
720 INIT_LIST_HEAD(&target
->d_hash
);
722 list_del(&dentry
->d_child
);
723 list_del(&target
->d_child
);
725 /* Switch the parents and the names.. */
726 do_switch(dentry
->d_parent
, target
->d_parent
);
727 do_switch(dentry
->d_name
.name
, target
->d_name
.name
);
728 do_switch(dentry
->d_name
.len
, target
->d_name
.len
);
729 do_switch(dentry
->d_name
.hash
, target
->d_name
.hash
);
730 list_add(&target
->d_child
, &target
->d_parent
->d_subdirs
);
731 list_add(&dentry
->d_child
, &dentry
->d_parent
->d_subdirs
);
735 * "buflen" should be PAGE_SIZE or more.
737 char * d_path(struct dentry
*dentry
, char *buffer
, int buflen
)
739 char * end
= buffer
+buflen
;
741 struct dentry
* root
= current
->fs
->root
;
745 if (dentry
->d_parent
!= dentry
&& list_empty(&dentry
->d_hash
)) {
748 memcpy(end
, " (deleted)", 10);
756 struct dentry
* parent
;
761 dentry
= dentry
->d_covers
;
762 parent
= dentry
->d_parent
;
763 if (dentry
== parent
)
765 namelen
= dentry
->d_name
.len
;
766 buflen
-= namelen
+ 1;
770 memcpy(end
, dentry
->d_name
.name
, namelen
);
779 * NOTE! The user-level library version returns a
780 * character pointer. The kernel system call just
781 * returns the length of the buffer filled (which
782 * includes the ending '\0' character), or a negative
783 * error value. So libc would do something like
785 * char *getcwd(char * buf, size_t size)
789 * retval = sys_getcwd(buf, size);
796 asmlinkage
int sys_getcwd(char *buf
, unsigned long size
)
799 struct dentry
*pwd
= current
->fs
->pwd
;
802 /* Has the current directory has been unlinked? */
803 if (pwd
->d_parent
== pwd
|| !list_empty(&pwd
->d_hash
)) {
804 char *page
= (char *) __get_free_page(GFP_USER
);
808 char * cwd
= d_path(pwd
, page
, PAGE_SIZE
);
811 len
= PAGE_SIZE
+ page
- cwd
;
814 if (copy_to_user(buf
, cwd
, len
))
817 free_page((unsigned long) page
);
824 * Test whether new_dentry is a subdirectory of old_dentry.
826 * Trivially implemented using the dcache structure
828 int is_subdir(struct dentry
* new_dentry
, struct dentry
* old_dentry
)
834 if (new_dentry
!= old_dentry
) {
835 struct dentry
* parent
= new_dentry
->d_parent
;
836 if (parent
== new_dentry
)
848 * Check whether a dentry already exists for the given name,
849 * and return the inode number if it has an inode.
851 * This routine is used to post-process directory listings for
852 * filesystems using synthetic inode numbers, and is necessary
853 * to keep getcwd() working.
855 ino_t
find_inode_number(struct dentry
*dir
, struct qstr
*name
)
857 struct dentry
* dentry
;
861 * Check for a fs-specific hash function. Note that we must
862 * calculate the standard hash first, as the d_op->d_hash()
863 * routine may choose to leave the hash value unchanged.
865 name
->hash
= full_name_hash(name
->name
, name
->len
);
866 if (dir
->d_op
&& dir
->d_op
->d_hash
)
868 if (dir
->d_op
->d_hash(dir
, name
) != 0)
872 dentry
= d_lookup(dir
, name
);
876 ino
= dentry
->d_inode
->i_ino
;
883 __initfunc(void dcache_init(void))
886 struct list_head
*d
= dentry_hashtable
;