vfs: dcache: fix deadlock in tree traversal

From: Miklos Szeredi <[email protected]>

IBM reported a deadlock in select_parent(). This was found to be caused by taking rename_lock when already locked when restarting the tree traversal.

There are two cases when the traversal needs to be restarted:

1) concurrent d_move(); this can only happen when not already locked, since taking rename_lock protects against concurrent d_move().

2) racing with final d_put() on child just at the moment of ascending to parent; rename_lock doesn't protect against this rare race, so it can happen when already locked.

Because of case 2. we need to be able to handle restarting the traversal when rename_lock is already held. This patch fixes all three callers of try_to_ascend().

IBM reported that the deadlock is gone with this patch. However, there's still a soft lockup which is addressed by the next patch.

---
 fs/dcache.c |   19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

Index: linux-2.6/fs/dcache.c
===================================================================
@@ -1134,8 +1134,10 @@ int have_submounts(struct dentry *parent
 	return 1;
 
 rename_retry:
-	locked = 1;
-	write_seqlock(&rename_lock);
+	if (!locked) {
+		locked = 1;
+		write_seqlock(&rename_lock);
+	}
 	goto again;
 }
 EXPORT_SYMBOL(have_submounts);

@@ -1236,8 +1238,10 @@ static int select_parent(struct dentry *
 rename_retry:
 	if (found)
 		return found;
-	locked = 1;
-	write_seqlock(&rename_lock);
+	if (!locked) {
+		locked = 1;
+		write_seqlock(&rename_lock);
+	}
 	goto again;
 }
 

@@ -3035,8 +3039,11 @@ void d_genocide(struct dentry *root)
 	return;
 
 rename_retry:
-	locked = 1;
-	write_seqlock(&rename_lock);
+	if (!locked) {
+		locked = 1;
+		write_seqlock(&rename_lock);
+
+	}
 	goto again;
 }
 

From: Miklos Szeredi <[email protected]>

IBM reported a soft lockup after applying the fix for the rename_lock deadlock. Commit c83ce989 ("VFS: Fix the nfs sillyrename regression in kernel 2.6.38") was found to be the culprit.

The nfs sillyrename fix used DCACHE_DISCONNECTED to indicate that the dentry was killed. This flag can be set on non-killed dentries too, which results in infinite retries when trying to traverse the dentry tree.

This patch introduces a separate flag: DCACHE_DENTRY_KILLED, which is only set in d_kill() and makes try_to_ascend() test only this flag.

IBM reported successful test results with this patch.

---
 fs/dcache.c            |    4 ++--
 include/linux/dcache.h |    2 ++
 2 files changed, 4 insertions(+), 2 deletions(-)

Index: linux-2.6/fs/dcache.c
===================================================================
@@ -389,7 +389,7 @@ static struct dentry *d_kill(struct dent
 	 * Inform try_to_ascend() that we are no longer attached to the
 	 * dentry tree
 	 */
-	dentry->d_flags |= DCACHE_DISCONNECTED;
+	dentry->d_flags |= DCACHE_DENTRY_KILLED;
 	if (parent)
 		spin_unlock(&parent->d_lock);
 	dentry_iput(dentry);

@@ -1048,7 +1048,7 @@ static struct dentry *try_to_ascend(stru
 	 * or deletion
 	 */
 	if (new != old->d_parent ||
-		 (old->d_flags & DCACHE_DISCONNECTED) ||
+		 (old->d_flags & DCACHE_DENTRY_KILLED) ||
 		 (!locked && read_seqretry(&rename_lock, seq))) {
 		spin_unlock(&new->d_lock);
 		new = NULL;

Index: linux-2.6/include/linux/dcache.h
===================================================================
@@ -206,6 +206,8 @@ struct dentry_operations {
 #define DCACHE_MANAGED_DENTRY \
 	(DCACHE_MOUNTED|DCACHE_NEED_AUTOMOUNT|DCACHE_MANAGE_TRANSIT)
 
+#define DCACHE_DENTRY_KILLED	0x100000
+
 extern seqlock_t rename_lock;
 
 static inline int dname_external(struct dentry *dentry)

Egads... The problem is real and analysis, AFAICS, is correct, but result is extremely ugly ;-/ Let me try to come up with something saner; I'll push that one to Linus if nothing better comes to mind, but I'd really prefer to avoid adding to ugliness in fs/dcache.c - we already have too much of that...

Agreed.

The problem (or at least one *part* of the problem) is that the "goto rename_retry" case is done for two different entities entirely:

- the "try_to_ascend()" failure path, which can happen even when
renamelock is held for writing.

- the "if we weren't write-locked before, and the read-lock failed"
case (which obviously cannot happen if we already held things for writing)

That said, I'm not sure why/how that try_to_ascend() could even fail when we're holding things locked. I guess it's the DCACHE_DISCONNECTED case that triggers.

So I'll ignore this series for now, hoping that Al will send a nicer version. Al, Miklos, please make sure this issue doesn't get dropped by mistake.

Linus

Yes, with the test cases that IBM were using it is DCACHE_DISCONNECTED case that triggers the double-lock. Trond was misusing DCACHE_DISCONNECTED and this made the failure in try_to_ascend() much more likely (and bogus). But there is a case, which is triggered rarely if ever, when try_to_ascend() failure with rename_lock held is perfectly valid.

try_to_ascend() does an ellaborate locking dance that aims to ensure that child remains valid after having ascended to parent. It nees a valid child because it needs the next sibling to continue tree traversal. If the child becomes invalid (final dput()) then the whole tree traversal needs to be restarted since we don't know where we left off. So we basically do

1. take the RCU lock
2. unlock child
3. lock parent
4. check whether child has been freed, if yes restart traversal
5. release RCU
6. find next sibling (child->d_child.next)
7. lock new child

It is step 4. that needs the RCU guarantees so we can check child's dentry flag (DCACHE_DISCONNECTED flag presently). After that d_lock on parent will protect "child" from going away (d_kill or d_move) and we can get hold of the next sibling.

Thanks,
Miklos

Ok. The whole DCACHE_DISCONNECTED logic there is clearly bogus and results in endless loops if that case then ever triggers, but you fix that in the second patch.

HOWEVER. Why introduce that new DCACHE_KILLED flag at all? Wouldn't it be much better to just check whether the dentry is hashed instead of introducing a new flag for this case? Couldn't we just check for "d_unhashed()"?

Anyway, I don't hate the 2/2 thing, but these are clearly related, and I'd like to understand why we had that odd DCACHE_DISCONNECTED test in the first place when there *seems* to be more straightforward approaches to it?

Linus

Not good, because an unhashed dentry can stay around and that would mean that we'd need to restart the walk until the last ref to the dentry is dropped (which can be an arbitrary long time).

Look at commit c83ce989. Before that patch try_to_ascend() was using old->d_parent != NULL (implicit in the "new != old->d_parent" test) to test for the dentry being killed. I think we need to keep that logic, and using a dentry flag for that looks simple enough.

Thanks,
Miklos

Ok, fair enough.

I'll apply your second patch as obviously fixing one issue, and wait for Al to hopefully come up with something nicer for the first one.

Linus

"Search list for X" sounds like you're trying to find X on a list.

---

(And I went to look at select_parent() and got tripped up for a few moments on this comment. Arguably my reading comprehension is just bad.)--b.

index 8086636..a0b8d65 100644
@@ -1141,7 +1141,7 @@ rename_retry:
 EXPORT_SYMBOL(have_submounts);
 
 /*
- * Search the dentry child list for the specified parent,
+ * Search the dentry child list of the specified parent,
  * and move any unused dentries to the end of the unused
  * list for prune_dcache(). We descend to the next level
  * whenever the d_subdirs list is non-empty and continue