From da3bbdd4632c0171406b2677e31494afa5bde2f8 Mon Sep 17 00:00:00 2001 From: Kentaro Makita Date: Wed, 23 Jul 2008 21:27:13 -0700 Subject: fix soft lock up at NFS mount via per-SB LRU-list of unused dentries [Summary] Split LRU-list of unused dentries to one per superblock to avoid soft lock up during NFS mounts and remounting of any filesystem. Previously I posted here: http://lkml.org/lkml/2008/3/5/590 [Descriptions] - background dentry_unused is a list of dentries which are not referenced. dentry_unused grows up when references on directories or files are released. This list can be very long if there is huge free memory. - the problem When shrink_dcache_sb() is called, it scans all dentry_unused linearly under spin_lock(), and if dentry->d_sb is differnt from given superblock, scan next dentry. This scan costs very much if there are many entries, and very ineffective if there are many superblocks. IOW, When we need to shrink unused dentries on one dentry, but scans unused dentries on all superblocks in the system. For example, we scan 500 dentries to unmount a filesystem, but scans 1,000,000 or more unused dentries on other superblocks. In our case , At mounting NFS*, shrink_dcache_sb() is called to shrink unused dentries on NFS, but scans 100,000,000 unused dentries on superblocks in the system such as local ext3 filesystems. I hear NFS mounting took 1 min on some system in use. * : NFS uses virtual filesystem in rpc layer, so NFS is affected by this problem. 100,000,000 is possible number on large systems. Per-superblock LRU of unused dentried can reduce the cost in reasonable manner. - How to fix I found this problem is solved by David Chinner's "Per-superblock unused dentry LRU lists V3"(1), so I rebase it and add some fix to reclaim with fairness, which is in Andrew Morton's comments(2). 1) http://lkml.org/lkml/2006/5/25/318 2) http://lkml.org/lkml/2006/5/25/320 Split LRU-list of unused dentries to each superblocks. Then, NFS mounting will check dentries under a superblock instead of all. But this spliting will break LRU of dentry-unused. So, I've attempted to make reclaim unused dentrins with fairness by calculate number of dentries to scan on this sb based on following way number of dentries to scan on this sb = count * (number of dentries on this sb / number of dentries in the machine) - ToDo - I have to measuring performance number and do stress tests. - When unmount occurs during prune_dcache(), scanning on same superblock, It is unable to reach next superblock because it is gone away. We restart scannig superblock from first one, it causes unfairness of reclaim unused dentries on first superblock. But I think this happens very rarely. - Test Results Result on 6GB boxes with excessive unused dentries. Without patch: $ cat /proc/sys/fs/dentry-state 10181835 10180203 45 0 0 0 # mount -t nfs 10.124.60.70:/work/kernel-src nfs real 0m1.830s user 0m0.001s sys 0m1.653s With this patch: $ cat /proc/sys/fs/dentry-state 10236610 10234751 45 0 0 0 # mount -t nfs 10.124.60.70:/work/kernel-src nfs real 0m0.106s user 0m0.002s sys 0m0.032s [akpm@linux-foundation.org: fix comments] Signed-off-by: Kentaro Makita Cc: Neil Brown Cc: Trond Myklebust Cc: David Chinner Cc: "J. Bruce Fields" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- fs/dcache.c | 335 ++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 180 insertions(+), 155 deletions(-) (limited to 'fs/dcache.c') diff --git a/fs/dcache.c b/fs/dcache.c index 6068c25b393c..3818d6ab76ca 100644 --- a/fs/dcache.c +++ b/fs/dcache.c @@ -61,7 +61,6 @@ static struct kmem_cache *dentry_cache __read_mostly; static unsigned int d_hash_mask __read_mostly; static unsigned int d_hash_shift __read_mostly; static struct hlist_head *dentry_hashtable __read_mostly; -static LIST_HEAD(dentry_unused); /* Statistics gathering. */ struct dentry_stat_t dentry_stat = { @@ -96,14 +95,6 @@ static void d_free(struct dentry *dentry) call_rcu(&dentry->d_u.d_rcu, d_callback); } -static void dentry_lru_remove(struct dentry *dentry) -{ - if (!list_empty(&dentry->d_lru)) { - list_del_init(&dentry->d_lru); - dentry_stat.nr_unused--; - } -} - /* * Release the dentry's inode, using the filesystem * d_iput() operation if defined. @@ -130,6 +121,41 @@ static void dentry_iput(struct dentry * dentry) } } +/* + * dentry_lru_(add|add_tail|del|del_init) must be called with dcache_lock held. + */ +static void dentry_lru_add(struct dentry *dentry) +{ + list_add(&dentry->d_lru, &dentry->d_sb->s_dentry_lru); + dentry->d_sb->s_nr_dentry_unused++; + dentry_stat.nr_unused++; +} + +static void dentry_lru_add_tail(struct dentry *dentry) +{ + list_add_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru); + dentry->d_sb->s_nr_dentry_unused++; + dentry_stat.nr_unused++; +} + +static void dentry_lru_del(struct dentry *dentry) +{ + if (!list_empty(&dentry->d_lru)) { + list_del(&dentry->d_lru); + dentry->d_sb->s_nr_dentry_unused--; + dentry_stat.nr_unused--; + } +} + +static void dentry_lru_del_init(struct dentry *dentry) +{ + if (likely(!list_empty(&dentry->d_lru))) { + list_del_init(&dentry->d_lru); + dentry->d_sb->s_nr_dentry_unused--; + dentry_stat.nr_unused--; + } +} + /** * d_kill - kill dentry and return parent * @dentry: dentry to kill @@ -212,8 +238,7 @@ repeat: goto kill_it; if (list_empty(&dentry->d_lru)) { dentry->d_flags |= DCACHE_REFERENCED; - list_add(&dentry->d_lru, &dentry_unused); - dentry_stat.nr_unused++; + dentry_lru_add(dentry); } spin_unlock(&dentry->d_lock); spin_unlock(&dcache_lock); @@ -222,7 +247,8 @@ repeat: unhash_it: __d_drop(dentry); kill_it: - dentry_lru_remove(dentry); + /* if dentry was on the d_lru list delete it from there */ + dentry_lru_del(dentry); dentry = d_kill(dentry); if (dentry) goto repeat; @@ -290,7 +316,7 @@ int d_invalidate(struct dentry * dentry) static inline struct dentry * __dget_locked(struct dentry *dentry) { atomic_inc(&dentry->d_count); - dentry_lru_remove(dentry); + dentry_lru_del_init(dentry); return dentry; } @@ -406,133 +432,167 @@ static void prune_one_dentry(struct dentry * dentry) if (dentry->d_op && dentry->d_op->d_delete) dentry->d_op->d_delete(dentry); - dentry_lru_remove(dentry); + dentry_lru_del_init(dentry); __d_drop(dentry); dentry = d_kill(dentry); spin_lock(&dcache_lock); } } -/** - * prune_dcache - shrink the dcache - * @count: number of entries to try and free - * @sb: if given, ignore dentries for other superblocks - * which are being unmounted. - * - * Shrink the dcache. This is done when we need - * more memory, or simply when we need to unmount - * something (at which point we need to unuse - * all dentries). - * - * This function may fail to free any resources if - * all the dentries are in use. +/* + * Shrink the dentry LRU on a given superblock. + * @sb : superblock to shrink dentry LRU. + * @count: If count is NULL, we prune all dentries on superblock. + * @flags: If flags is non-zero, we need to do special processing based on + * which flags are set. This means we don't need to maintain multiple + * similar copies of this loop. */ - -static void prune_dcache(int count, struct super_block *sb) +static void __shrink_dcache_sb(struct super_block *sb, int *count, int flags) { - spin_lock(&dcache_lock); - for (; count ; count--) { - struct dentry *dentry; - struct list_head *tmp; - struct rw_semaphore *s_umount; - - cond_resched_lock(&dcache_lock); + LIST_HEAD(referenced); + LIST_HEAD(tmp); + struct dentry *dentry; + int cnt = 0; - tmp = dentry_unused.prev; - if (sb) { - /* Try to find a dentry for this sb, but don't try - * too hard, if they aren't near the tail they will - * be moved down again soon + BUG_ON(!sb); + BUG_ON((flags & DCACHE_REFERENCED) && count == NULL); + spin_lock(&dcache_lock); + if (count != NULL) + /* called from prune_dcache() and shrink_dcache_parent() */ + cnt = *count; +restart: + if (count == NULL) + list_splice_init(&sb->s_dentry_lru, &tmp); + else { + while (!list_empty(&sb->s_dentry_lru)) { + dentry = list_entry(sb->s_dentry_lru.prev, + struct dentry, d_lru); + BUG_ON(dentry->d_sb != sb); + + spin_lock(&dentry->d_lock); + /* + * If we are honouring the DCACHE_REFERENCED flag and + * the dentry has this flag set, don't free it. Clear + * the flag and put it back on the LRU. */ - int skip = count; - while (skip && tmp != &dentry_unused && - list_entry(tmp, struct dentry, d_lru)->d_sb != sb) { - skip--; - tmp = tmp->prev; + if ((flags & DCACHE_REFERENCED) + && (dentry->d_flags & DCACHE_REFERENCED)) { + dentry->d_flags &= ~DCACHE_REFERENCED; + list_move_tail(&dentry->d_lru, &referenced); + spin_unlock(&dentry->d_lock); + } else { + list_move_tail(&dentry->d_lru, &tmp); + spin_unlock(&dentry->d_lock); + cnt--; + if (!cnt) + break; } } - if (tmp == &dentry_unused) - break; - list_del_init(tmp); - prefetch(dentry_unused.prev); - dentry_stat.nr_unused--; - dentry = list_entry(tmp, struct dentry, d_lru); - - spin_lock(&dentry->d_lock); + } + while (!list_empty(&tmp)) { + dentry = list_entry(tmp.prev, struct dentry, d_lru); + dentry_lru_del_init(dentry); + spin_lock(&dentry->d_lock); /* * We found an inuse dentry which was not removed from - * dentry_unused because of laziness during lookup. Do not free - * it - just keep it off the dentry_unused list. + * the LRU because of laziness during lookup. Do not free + * it - just keep it off the LRU list. */ - if (atomic_read(&dentry->d_count)) { - spin_unlock(&dentry->d_lock); + if (atomic_read(&dentry->d_count)) { + spin_unlock(&dentry->d_lock); continue; } - /* If the dentry was recently referenced, don't free it. */ - if (dentry->d_flags & DCACHE_REFERENCED) { - dentry->d_flags &= ~DCACHE_REFERENCED; - list_add(&dentry->d_lru, &dentry_unused); - dentry_stat.nr_unused++; - spin_unlock(&dentry->d_lock); + prune_one_dentry(dentry); + /* dentry->d_lock was dropped in prune_one_dentry() */ + cond_resched_lock(&dcache_lock); + } + if (count == NULL && !list_empty(&sb->s_dentry_lru)) + goto restart; + if (count != NULL) + *count = cnt; + if (!list_empty(&referenced)) + list_splice(&referenced, &sb->s_dentry_lru); + spin_unlock(&dcache_lock); +} + +/** + * prune_dcache - shrink the dcache + * @count: number of entries to try to free + * + * Shrink the dcache. This is done when we need more memory, or simply when we + * need to unmount something (at which point we need to unuse all dentries). + * + * This function may fail to free any resources if all the dentries are in use. + */ +static void prune_dcache(int count) +{ + struct super_block *sb; + int w_count; + int unused = dentry_stat.nr_unused; + int prune_ratio; + int pruned; + + if (unused == 0 || count == 0) + return; + spin_lock(&dcache_lock); +restart: + if (count >= unused) + prune_ratio = 1; + else + prune_ratio = unused / count; + spin_lock(&sb_lock); + list_for_each_entry(sb, &super_blocks, s_list) { + if (sb->s_nr_dentry_unused == 0) continue; - } - /* - * If the dentry is not DCACHED_REFERENCED, it is time - * to remove it from the dcache, provided the super block is - * NULL (which means we are trying to reclaim memory) - * or this dentry belongs to the same super block that - * we want to shrink. - */ - /* - * If this dentry is for "my" filesystem, then I can prune it - * without taking the s_umount lock (I already hold it). + sb->s_count++; + /* Now, we reclaim unused dentrins with fairness. + * We reclaim them same percentage from each superblock. + * We calculate number of dentries to scan on this sb + * as follows, but the implementation is arranged to avoid + * overflows: + * number of dentries to scan on this sb = + * count * (number of dentries on this sb / + * number of dentries in the machine) */ - if (sb && dentry->d_sb == sb) { - prune_one_dentry(dentry); - continue; - } + spin_unlock(&sb_lock); + if (prune_ratio != 1) + w_count = (sb->s_nr_dentry_unused / prune_ratio) + 1; + else + w_count = sb->s_nr_dentry_unused; + pruned = w_count; /* - * ...otherwise we need to be sure this filesystem isn't being - * unmounted, otherwise we could race with - * generic_shutdown_super(), and end up holding a reference to - * an inode while the filesystem is unmounted. - * So we try to get s_umount, and make sure s_root isn't NULL. - * (Take a local copy of s_umount to avoid a use-after-free of - * `dentry'). + * We need to be sure this filesystem isn't being unmounted, + * otherwise we could race with generic_shutdown_super(), and + * end up holding a reference to an inode while the filesystem + * is unmounted. So we try to get s_umount, and make sure + * s_root isn't NULL. */ - s_umount = &dentry->d_sb->s_umount; - if (down_read_trylock(s_umount)) { - if (dentry->d_sb->s_root != NULL) { - prune_one_dentry(dentry); - up_read(s_umount); - continue; + if (down_read_trylock(&sb->s_umount)) { + if ((sb->s_root != NULL) && + (!list_empty(&sb->s_dentry_lru))) { + spin_unlock(&dcache_lock); + __shrink_dcache_sb(sb, &w_count, + DCACHE_REFERENCED); + pruned -= w_count; + spin_lock(&dcache_lock); } - up_read(s_umount); + up_read(&sb->s_umount); } - spin_unlock(&dentry->d_lock); + spin_lock(&sb_lock); + count -= pruned; /* - * Insert dentry at the head of the list as inserting at the - * tail leads to a cycle. + * restart only when sb is no longer on the list and + * we have more work to do. */ - list_add(&dentry->d_lru, &dentry_unused); - dentry_stat.nr_unused++; + if (__put_super_and_need_restart(sb) && count > 0) { + spin_unlock(&sb_lock); + goto restart; + } } + spin_unlock(&sb_lock); spin_unlock(&dcache_lock); } -/* - * Shrink the dcache for the specified super block. - * This allows us to unmount a device without disturbing - * the dcache for the other devices. - * - * This implementation makes just two traversals of the - * unused list. On the first pass we move the selected - * dentries to the most recent end, and on the second - * pass we free them. The second pass must restart after - * each dput(), but since the target dentries are all at - * the end, it's really just a single traversal. - */ - /** * shrink_dcache_sb - shrink dcache for a superblock * @sb: superblock @@ -541,44 +601,9 @@ static void prune_dcache(int count, struct super_block *sb) * is used to free the dcache before unmounting a file * system */ - void shrink_dcache_sb(struct super_block * sb) { - struct list_head *tmp, *next; - struct dentry *dentry; - - /* - * Pass one ... move the dentries for the specified - * superblock to the most recent end of the unused list. - */ - spin_lock(&dcache_lock); - list_for_each_prev_safe(tmp, next, &dentry_unused) { - dentry = list_entry(tmp, struct dentry, d_lru); - if (dentry->d_sb != sb) - continue; - list_move_tail(tmp, &dentry_unused); - } - - /* - * Pass two ... free the dentries for this superblock. - */ -repeat: - list_for_each_prev_safe(tmp, next, &dentry_unused) { - dentry = list_entry(tmp, struct dentry, d_lru); - if (dentry->d_sb != sb) - continue; - dentry_stat.nr_unused--; - list_del_init(tmp); - spin_lock(&dentry->d_lock); - if (atomic_read(&dentry->d_count)) { - spin_unlock(&dentry->d_lock); - continue; - } - prune_one_dentry(dentry); - cond_resched_lock(&dcache_lock); - goto repeat; - } - spin_unlock(&dcache_lock); + __shrink_dcache_sb(sb, NULL, 0); } /* @@ -595,7 +620,7 @@ static void shrink_dcache_for_umount_subtree(struct dentry *dentry) /* detach this root from the system */ spin_lock(&dcache_lock); - dentry_lru_remove(dentry); + dentry_lru_del_init(dentry); __d_drop(dentry); spin_unlock(&dcache_lock); @@ -609,7 +634,7 @@ static void shrink_dcache_for_umount_subtree(struct dentry *dentry) spin_lock(&dcache_lock); list_for_each_entry(loop, &dentry->d_subdirs, d_u.d_child) { - dentry_lru_remove(loop); + dentry_lru_del_init(loop); __d_drop(loop); cond_resched_lock(&dcache_lock); } @@ -791,14 +816,13 @@ resume: struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child); next = tmp->next; - dentry_lru_remove(dentry); + dentry_lru_del_init(dentry); /* * move only zero ref count dentries to the end * of the unused list for prune_dcache */ if (!atomic_read(&dentry->d_count)) { - list_add_tail(&dentry->d_lru, &dentry_unused); - dentry_stat.nr_unused++; + dentry_lru_add_tail(dentry); found++; } @@ -840,10 +864,11 @@ out: void shrink_dcache_parent(struct dentry * parent) { + struct super_block *sb = parent->d_sb; int found; while ((found = select_parent(parent)) != 0) - prune_dcache(found, parent->d_sb); + __shrink_dcache_sb(sb, &found, 0); } /* @@ -863,7 +888,7 @@ static int shrink_dcache_memory(int nr, gfp_t gfp_mask) if (nr) { if (!(gfp_mask & __GFP_FS)) return -1; - prune_dcache(nr, NULL); + prune_dcache(nr); } return (dentry_stat.nr_unused / 100) * sysctl_vfs_cache_pressure; } @@ -1215,7 +1240,7 @@ struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry) * rcu_read_lock() and rcu_read_unlock() are used to disable preemption while * lookup is going on. * - * dentry_unused list is not updated even if lookup finds the required dentry + * The dentry unused LRU is not updated even if lookup finds the required dentry * in there. It is updated in places such as prune_dcache, shrink_dcache_sb, * select_parent and __dget_locked. This laziness saves lookup from dcache_lock * acquisition. -- cgit From f3c6ba986ab4527b6dfacf9f3b9e40f72466a8b2 Mon Sep 17 00:00:00 2001 From: Kentaro Makita Date: Fri, 25 Jul 2008 19:44:40 -0700 Subject: vfs: add cond_resched_lock while scanning dentry LRU lists Add cond_resched_lock(&dcache_lock) while scanning LRU lists on superblocks in __shrink_dcache_sb() Signed-off-by: Kentaro Makita Cc: Al Viro Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- fs/dcache.c | 1 + 1 file changed, 1 insertion(+) (limited to 'fs/dcache.c') diff --git a/fs/dcache.c b/fs/dcache.c index 3818d6ab76ca..f2584d22cb45 100644 --- a/fs/dcache.c +++ b/fs/dcache.c @@ -487,6 +487,7 @@ restart: if (!cnt) break; } + cond_resched_lock(&dcache_lock); } } while (!list_empty(&tmp)) { -- cgit From 9403540c0653122ca34884a180439ddbfcbcb524 Mon Sep 17 00:00:00 2001 From: Barry Naujok Date: Wed, 21 May 2008 16:50:46 +1000 Subject: dcache: Add case-insensitive support d_ci_add() routine This add a dcache entry to the dcache for lookup, but changing the name that is associated with the entry rather than the one passed in to the lookup routine. First, it sees if the case-exact match already exists in the dcache and uses it if one exists. Otherwise, it allocates a new node with the new name and splices it into the dcache. Original code from ntfs_lookup in fs/ntfs/namei.c by Anton Altaparmakov. Signed-off-by: Barry Naujok Signed-off-by: Anton Altaparmakov Acked-by: Christoph Hellwig --- fs/dcache.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) (limited to 'fs/dcache.c') diff --git a/fs/dcache.c b/fs/dcache.c index f2584d22cb45..101663d15e9f 100644 --- a/fs/dcache.c +++ b/fs/dcache.c @@ -1220,6 +1220,107 @@ struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry) return new; } +/** + * d_add_ci - lookup or allocate new dentry with case-exact name + * @inode: the inode case-insensitive lookup has found + * @dentry: the negative dentry that was passed to the parent's lookup func + * @name: the case-exact name to be associated with the returned dentry + * + * This is to avoid filling the dcache with case-insensitive names to the + * same inode, only the actual correct case is stored in the dcache for + * case-insensitive filesystems. + * + * For a case-insensitive lookup match and if the the case-exact dentry + * already exists in in the dcache, use it and return it. + * + * If no entry exists with the exact case name, allocate new dentry with + * the exact case, and return the spliced entry. + */ +struct dentry *d_add_ci(struct inode *inode, struct dentry *dentry, + struct qstr *name) +{ + int error; + struct dentry *found; + struct dentry *new; + + /* Does a dentry matching the name exist already? */ + found = d_hash_and_lookup(dentry->d_parent, name); + /* If not, create it now and return */ + if (!found) { + new = d_alloc(dentry->d_parent, name); + if (!new) { + error = -ENOMEM; + goto err_out; + } + found = d_splice_alias(inode, new); + if (found) { + dput(new); + return found; + } + return new; + } + /* Matching dentry exists, check if it is negative. */ + if (found->d_inode) { + if (unlikely(found->d_inode != inode)) { + /* This can't happen because bad inodes are unhashed. */ + BUG_ON(!is_bad_inode(inode)); + BUG_ON(!is_bad_inode(found->d_inode)); + } + /* + * Already have the inode and the dentry attached, decrement + * the reference count to balance the iget() done + * earlier on. We found the dentry using d_lookup() so it + * cannot be disconnected and thus we do not need to worry + * about any NFS/disconnectedness issues here. + */ + iput(inode); + return found; + } + /* + * Negative dentry: instantiate it unless the inode is a directory and + * has a 'disconnected' dentry (i.e. IS_ROOT and DCACHE_DISCONNECTED), + * in which case d_move() that in place of the found dentry. + */ + if (!S_ISDIR(inode->i_mode)) { + /* Not a directory; everything is easy. */ + d_instantiate(found, inode); + return found; + } + spin_lock(&dcache_lock); + if (list_empty(&inode->i_dentry)) { + /* + * Directory without a 'disconnected' dentry; we need to do + * d_instantiate() by hand because it takes dcache_lock which + * we already hold. + */ + list_add(&found->d_alias, &inode->i_dentry); + found->d_inode = inode; + spin_unlock(&dcache_lock); + security_d_instantiate(found, inode); + return found; + } + /* + * Directory with a 'disconnected' dentry; get a reference to the + * 'disconnected' dentry. + */ + new = list_entry(inode->i_dentry.next, struct dentry, d_alias); + dget_locked(new); + spin_unlock(&dcache_lock); + /* Do security vodoo. */ + security_d_instantiate(found, inode); + /* Move new in place of found. */ + d_move(new, found); + /* Balance the iget() we did above. */ + iput(inode); + /* Throw away found. */ + dput(found); + /* Use new as the actual dentry. */ + return new; + +err_out: + iput(inode); + return ERR_PTR(error); +} /** * d_lookup - search for a dentry @@ -2254,6 +2355,7 @@ EXPORT_SYMBOL(d_path); EXPORT_SYMBOL(d_prune_aliases); EXPORT_SYMBOL(d_rehash); EXPORT_SYMBOL(d_splice_alias); +EXPORT_SYMBOL(d_add_ci); EXPORT_SYMBOL(d_validate); EXPORT_SYMBOL(dget_locked); EXPORT_SYMBOL(dput); -- cgit