possible badness in prune_dcache()
Hello list,
When investigation livelock in RHEL3, i found possible badness in prune_dcache, which exist in 2.6.24 also.
situation - system has ~6 mounted filesystem, at 5 FS do some io, and one FS start umount.shrink_dcache_parent - collect unused dentries after call select_parent() and put these dentries into end of LRU for kill. but between exit from select_parent() and enter to prune_dcache(,sb) some processed add more unused dentries and put to end lru also. prune_dcache start skip some dentiries in loop
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
while (skip && tmp != &dentry_unused &&
list_entry(tmp, struct dentry,
d_lru)->d_sb != sb) {
skip--;
tmp = tmp->prev;
}Quoted 1 line
Quoted 1 line
Quoted 1 line
but not found correct dentry for superblock.
later condition
if (tmp == &dentry_unused)
break;not hit - because LRU has additional dentry, and prune_dcache(,sb) kill dentry not related to submitted superblock.
(this first stranges - for me)
but this not all, because count != 0 prune_dcache run in loop and kill all dentries not related to submited sb, with can be need many time (in my situation ~15min for ~200k dentries).
after exit from prune_dcache - shrink_dcache_parent() do loop and try again destroy dentries - which also need some time.
my tests - show changing condition, from
if (tmp == &dentry_unused)
break;
to
if (tmp == &dentry_unused) || (sb && (list_entry(tmp,
struct dentry, d_lru)->d_sb != sb))
break;help with live lock - because prune_dcache exit from loop early and move required dentries to end of LRU - for easy kill.
Please comment this investigation.
PS. please send copy to me, i not subscribed to list.
Signature · 2 lines
Alex Lyashkov <[email protected]> Lustre Group, Sun Microsystems
Quoted 2 lines
When investigation livelock in RHEL3, i found possible badness in
prune_dcache, which exist in 2.6.24 also.
Have you actually tested with 2.6.24? shrink_dcache_parent() isn't called from umount anymore. I think this is the commit responsible for fixing the issue:
commit c636ebdb186bf37f98d3839f69293597723edb36
Author: David Howells <[email protected]> Date: Wed Oct 11 01:22:19 2006 -0700
[PATCH] VFS: Destroy the dentries contributed by a superblock on unmounting
Miklos
Quoted 55 lines
situation - system has ~6 mounted filesystem, at 5 FS do some io, and one FS start umount.
shrink_dcache_parent- collect unused dentries after callselect_parent()and put these dentries into end of LRU for kill. but between exit fromselect_parent()and enter toprune_dcache(,sb)some processed add more unused dentries and put to end lru also.prune_dcachestart skip some dentiries in loopQuoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
while (skip && tmp !=
&dentry_unused&&
list_entry(tmp, struct dentry,d_lru)->d_sb != sb) { skip--; tmp = tmp->prev; }Quoted 1 line
Quoted 1 line
Quoted 1 line
but not found correct dentry for superblock.
later conditionif (tmp == &dentry_unused) break;not hit - because LRU has additional dentry, and
prune_dcache(,sb)kill dentry not related to submitted superblock.
(this first stranges - for me)but this not all, because count != 0
prune_dcacherun in loop and kill all dentries not related to submited sb, with can be need many time (in my situation ~15min for ~200k dentries).after exit from
prune_dcache-shrink_dcache_parent()do loop and try again destroy dentries - which also need some time.my tests - show changing condition, from
if (tmp == &dentry_unused) break; to if (tmp == &dentry_unused) || (sb && (list_entry(tmp, struct dentry, d_lru)->d_sb != sb)) break;help with live lock - because
prune_dcacheexit from loop early and move required dentries to end of LRU - for easy kill.Please comment this investigation.
PS. please send copy to me, i not subscribed to list.
Signature · 7 lines
Alex Lyashkov <[email protected]> Lustre Group, Sun Microsystems -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Thanks for answer,
Yes this commit - fix issue with umount, but not resolve main question:
why prune_dcache kill dentry with diffrent super block? this produce long loop with skip loop instead of early exit and move dentry from select_parent again to end of list.
Quoted 15 lines · Miklos Szeredi
Quoted 2 lines
When investigation livelock in RHEL3, i found possible badness in
prune_dcache, which exist in 2.6.24 also.Have you actually tested with 2.6.24?
shrink_dcache_parent()isn't called from umount anymore. I think this is the commit responsible for fixing the issue:commit
c636ebdb186bf37f98d3839f69293597723edb36Author: David Howells <[email protected]> Date: Wed Oct 11 01:22:19 2006 -0700[PATCH] VFS: Destroy the dentries contributed by a superblock on unmounting
Miklos
Quoted 7 lines · Alex Lyashkov
Thanks for answer,
Yes this commit - fix issue with umount, but not resolve main question:
whyprune_dcachekill dentry with diffrent super block? this produce long loop with skip loop instead of early exit and move dentry fromselect_parentagain to end of list.
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving prune_dcache to only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list to prune_dcache that way we didn't spend all this time looping. I will see what can be done for upstream.
Josef
Quoted 23 lines · Miklos Szeredi
Quoted 7 lines
Quoted 2 lines
When investigation livelock in RHEL3, i found possible badness in
prune_dcache, which exist in 2.6.24 also.Have you actually tested with 2.6.24?
shrink_dcache_parent()isn't called from umount anymore. I think this is the commit responsible for fixing the issue:Quoted 8 lines
commit
c636ebdb186bf37f98d3839f69293597723edb36Author: David Howells <[email protected]> Date: Wed Oct 11 01:22:19 2006 -0700[PATCH] VFS: Destroy the dentries contributed by a superblock on unmounting
Miklos
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 9 lines · Josef Bacik
Quoted 7 lines · Alex Lyashkov
Thanks for answer,
Yes this commit - fix issue with umount, but not resolve main question:
whyprune_dcachekill dentry with diffrent super block? this produce long loop with skip loop instead of early exit and move dentry fromselect_parentagain to end of list.
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.
If you would like to test the current upstream I have a patch that does what I described above. I only compile tested it, so who knows what it will do :).
fs/dcache.c +36 -38
@@ -413,8 +413,8 @@ static void prune_one_dentry(struct dentry * dentry)/** * 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. +* @dispose_list: if given, remove dentries from this +* list instead of from the dentry_unused list. * * Shrink the dcache. This is done when we need * more memory, or simply when we need to unmount
@@ -425,8 +425,15 @@ static void prune_one_dentry(struct dentry * dentry)* all the dentries are in use. */ -static void prune_dcache (int count,struct super_block *sb) +static void prune_dcache (int count,struct list_head *dispose_list) { +struct list_head *list; + +if (dispose_list) + list = dispose_list; +else + list = &dentry_unused; +spin_lock (&dcache_lock);for (; count ; count--) {struct dentry *dentry;
@@ -435,23 +442,11 @@ static void prune_dcache(int count, struct super_block *sb)cond_resched_lock (&dcache_lock); - 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 -*/ -int skip = count; -while (skip && tmp != &dentry_unused && - list_entry(tmp, struct dentry, d_lru)->d_sb != sb) { - skip--; - tmp = tmp->prev; - } - } -if (tmp == &dentry_unused) + tmp = list->prev; +if (tmp == list)break ;list_del_init (tmp); -prefetch (dentry_unused.prev); +prefetch (list->prev); dentry_stat.nr_unused--; dentry = list_entry(tmp, struct dentry, d_lru);
@@ -468,26 +463,16 @@ static void prune_dcache(int count, struct super_block *sb)/* 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); +list_add (&dentry->d_lru, list); dentry_stat.nr_unused++;spin_unlock (&dentry->d_lock);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). +* to remove it from the dcache */ -if (sb && dentry->d_sb == sb) { -prune_one_dentry (dentry); -continue ; - } +/* * ...otherwise we need to be sure this filesystem isn't being * unmounted, otherwise we could race with
@@ -505,13 +490,20 @@ static void prune_dcache(int count, struct super_block *sb)continue ; }up_read (s_umount); + }else if (dispose_list) { +/* +* if we're shrinking dcache for an unmounting fs +* just go ahead and exit +*/ +spin_unlock (&dentry->d_lock); +break ; }spin_unlock (&dentry->d_lock);/* * Insert dentry at the head of the list as inserting at the * tail leads to a cycle. */ -list_add (&dentry->d_lru, &dentry_unused); +list_add (&dentry->d_lru, list); dentry_stat.nr_unused++; }spin_unlock (&dcache_lock);
@@ -761,19 +753,20 @@ positive:/* * Search the dentry child list for the specified parent, -* and move any unused dentries to the end of the unused +* and move any unused dentries to the end of the dispose * list for prune_dcache(). We descend to the next level * whenever the d_subdirs list is non-empty and continue * searching. * * It returns zero iff there are no unused children, * otherwise it returns the number of children moved to -* the end of the unused list. This may not be the total +* the end of the dispose list. This may not be the total * number of unused children, because select_parent can * drop the lock and return early due to latency * constraints. */ -static int select_parent (struct dentry * parent) +static int select_parent (struct dentry * parent, +struct list_head *dispose_list) {struct dentry *this_parent = parent;struct list_head *next;
@@ -794,7 +787,7 @@ resume:* of the unused list for prune_dcache */ if (!atomic_read (&dentry->d_count)) { -list_add_tail (&dentry->d_lru, &dentry_unused); +list_add_tail (&dentry->d_lru, dispose_list); dentry_stat.nr_unused++; found++; }
@@ -838,9 +831,14 @@ out:void shrink_dcache_parent (struct dentry * parent) {int found; +LIST_HEAD (dispose_list); -while ((found =select_parent (parent)) !=0 ) -prune_dcache (found, parent->d_sb); +/* +* select_parent will populate dispose_list with the +* dentry's that we are removing +*/ +while ((found =select_parent (parent, &dispose_list)) !=0 ) +prune_dcache (found, &dispose_list); }/*
Quoted 8 lines
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.
Which sounds racy with umount. A hashed dentry must either have a refcount greater than one, or be on dentry_unused list. This patch breaks that assumption.
Miklos
Quoted 9 lines · Miklos Szeredi
Quoted 8 lines
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.
Quoted 4 lines
Which sounds racy with umount. A hashed dentry must either have a refcount greater than one, or be on
dentry_unusedlist. This patch breaks that assumption.
It should be racy with umount, if we notice that we're being unmounted we just break, as the unmount will free the dentry's itself through another means. I guess I could fix it so that prune_dcache will go through and add all the dentry's still on the dispose_list to the dentry_unused list at the end, but I don't see much of a reason for this since dentry_unused is just used to help keep track of what dentries can be flushed.
Josef
Quoted 15 lines · Josef Bacik
Quoted 9 lines · Miklos Szeredi
Quoted 8 lines
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.Quoted 4 lines
Which sounds racy with umount. A hashed dentry must either have a refcount greater than one, or be on
dentry_unusedlist. This patch breaks that assumption.
Quoted 7 lines
It should be racy with umount, if we notice that we're being unmounted we just break, as the unmount will free the dentry's itself through another means. I guess I could fix it so that
prune_dcachewill go through and add all the dentry's still on thedispose_listto thedentry_unusedlist at the end, but I don't see much of a reason for this sincedentry_unusedis just used to help keep track of what dentries can be flushed.
Hmm, thats shouldn't, not should.
Josef
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.
Quoted 8 lines
Quoted 4 lines
Which sounds racy with umount. A hashed dentry must either have a refcount greater than one, or be on
dentry_unusedlist. This patch breaks that assumption.It should be racy with umount, if we notice that we're being unmounted we just break, as the unmount will free the dentry's itself through another means.
But unmount could have already finished by then. And now you are dereferencing a super block, that no longer exists. Not good.
This separate list thing can't work, unfortunately. On the other hand we should probably split prune_dcache() into two separate functions:
the garbage collector one (with sb == NULL argument) and the sb specific shrinker. It should I think be possible to share the second one with shrink_dcache_sb().
Miklos
Quoted 18 lines · Miklos Szeredi
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.Quoted 8 lines
Quoted 4 lines
Which sounds racy with umount. A hashed dentry must either have a refcount greater than one, or be on
dentry_unusedlist. This patch breaks that assumption.It should be racy with umount, if we notice that we're being unmounted we just break, as the unmount will free the dentry's itself through another means.
Quoted 9 lines
But unmount could have already finished by then. And now you are dereferencing a super block, that no longer exists. Not good.
This separate list thing can't work, unfortunately. On the other hand we should probably split
prune_dcache()into two separate functions:
the garbage collector one (with sb == NULL argument) and the sb specific shrinker. It should I think be possible to share the second one withshrink_dcache_sb().
Hmm good point. How bout this? Keeps us from doing the skip thing and keeps the garbage collector path a little cleaner. Thanks much,
Josef
fs/dcache.c +5 -30
@@ -413,8 +413,6 @@ static void prune_one_dentry(struct dentry * dentry)/** * 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
@@ -425,7 +423,7 @@ static void prune_one_dentry(struct dentry * dentry)* all the dentries are in use. */ -static void prune_dcache (int count,struct super_block *sb) +static void prune_dcache (int count) {spin_lock (&dcache_lock);for (; count ; count--) {
@@ -436,18 +434,6 @@ static void prune_dcache(int count, struct super_block *sb)cond_resched_lock (&dcache_lock); 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 -*/ -int skip = count; -while (skip && tmp != &dentry_unused && - list_entry(tmp, struct dentry, d_lru)->d_sb != sb) { - skip--; - tmp = tmp->prev; - } - }if (tmp == &dentry_unused)break ;list_del_init (tmp);
@@ -475,21 +461,10 @@ static void prune_dcache(int count, struct super_block *sb) }/* * 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. +* to remove it from the dcache */ /* -* If this dentry is for "my" filesystem, then I can prune it -* without taking the s_umount lock (I already hold it). -*/ -if (sb && dentry->d_sb == sb) { -prune_one_dentry (dentry); -continue ; - } -/* -* ...otherwise we need to be sure this filesystem isn't being +* 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.
@@ -840,7 +815,7 @@ void shrink_dcache_parent(struct dentry * parent)int found;while ((found =select_parent (parent)) !=0 ) -prune_dcache (found, parent->d_sb); +shrink_dcache_sb (parent->d_sb); }/*
@@ -860,7 +835,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; }
Quoted 2 lines
Hmm good point. How bout this? Keeps us from doing the skip thing and keeps the garbage collector path a little cleaner. Thanks much,
Well yeah, something like that.
Only shrink_dcache_sb() is way overkill for shrink_dcache_parent(). We definitelty don't want to do that.
But if you remove the garbage collection parts from prune_dcache() and compare that to the second pass of shrink_dcache_sb(), they look eerily similar, except one of them removes all dentries belonging to the sb, the other one only removes 'count' number of dentries. But they could possibly be merged into a common function.
Miklos
Quoted 18 lines · Miklos Szeredi
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 8 lines
probably worth looking at doing something different in the case of shrinking the dcache on the parent, and leaving
prune_dcacheto only be called in the case of trying to free up dcache under memory pressure, where the superblock doesn't actually matter. For the RHEL3 issue you are reffering to I fixed it by creating a private list when we shrunk the parent, and submitting that list toprune_dcachethat way we didn't spend all this time looping. I will see what can be done for upstream.Quoted 8 lines
Quoted 4 lines
Which sounds racy with umount. A hashed dentry must either have a refcount greater than one, or be on
dentry_unusedlist. This patch breaks that assumption.It should be racy with umount, if we notice that we're being unmounted we just break, as the unmount will free the dentry's itself through another means.
Quoted 9 lines
But unmount could have already finished by then. And now you are dereferencing a super block, that no longer exists. Not good.
This separate list thing can't work, unfortunately. On the other hand we should probably split
prune_dcache()into two separate functions:
the garbage collector one (with sb == NULL argument) and the sb specific shrinker. It should I think be possible to share the second one withshrink_dcache_sb().
Hi.
As another reply, there is a patch David Chinner you list below.
Per-superblock unused dentry LRU
http://lwn.net/Articles/185465/
There is an article below as the recent argument which it is related.
http://lkml.org/lkml/2008/3/5/590
I think that the idea of per superblock unusued LRUs is rational.
Thanks
Quoted 15 lines · Alex Lyashkov
Thanks for answer,
Yes this commit - fix issue with umount, but not resolve main question:
whyprune_dcachekill dentry with diffrent super block? this produce long loop with skip loop instead of early exit and move dentry fromselect_parentagain to end of list.Quoted 6 lines · Miklos Szeredi
Quoted 2 lines
When investigation livelock in RHEL3, i found possible badness in
prune_dcache, which exist in 2.6.24 also.Have you actually tested with 2.6.24?
shrink_dcache_parent()isn't called from umount anymore. I think this is the commit responsible for fixing the issue:
Am I missing part of the first part of this conversation?
David