Skip to contentSkip to conversation

possible badness in prune_dcache()

RFC Alex Lyashkov 5 participants 13 messages Apr 4, 2008 – Apr 7, 2008 VFS

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw
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 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 · 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
#2 lore raw

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 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

#3 lore raw
Quoted 7 lines · Alex Lyashkov

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.

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 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

--
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

#4 lore raw
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:
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 8 lines

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.

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
index 4345577..564df98 100644
@@ -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);
 }
 
 /*
#5 lore raw
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_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.

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

#6 lore raw
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_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.

Quoted 4 lines

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.

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

#7 lore raw
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_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.

Quoted 4 lines

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.

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_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.

Hmm, thats shouldn't, not should.

Josef

#8 lore raw
In reply to Josef Bacik
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_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.

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_unused list. 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

#9 lore raw
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_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.

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_unused list. 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 with shrink_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
index 4345577..2d22176 100644
@@ -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;
 }
#10 lore raw
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

#11 lore raw
In reply to Josef Bacik
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_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.

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_unused list. 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 with shrink_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

#12 lore raw
In reply to Alex Lyashkov
Quoted 15 lines · Alex Lyashkov

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 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