[bug] radix_tree_gang_lookup_tag_slot() looping endlessly

[Dave Chinner]

Folks,

I'm seeing a livelock with the new writeback sync livelock avoidance
code. The problem is that the radix tree lookup via
pagevec_lookup_tag()->find_get_pages_tag() is getting stuck in
radix_tree_gang_lookup_tag_slot() and never exitting.

The reproducer I'm running is xfstests 013 on 2.6.35-rc1 with some
pending XFS changes available here:

git://git.kernel.org/pub/scm/linux/kernel/git/dgc/xfsdev.git for-oss

It's 100% reproducable, and a regression against 2.6.35 patched wth exactly
the same extra XFS commits as the above branch.

I tried applying Nick's recent indirect pointer fixup patch for the
radix tree, but that didn't fix the problem. I applied the patch
below on top of that to detect when __lookup_tag is not making
progress and the livelock has gone away. Someone who knows the how
the radix tree code is supposed to work might be able to pinpoint
the problem exactly from this.

Cheers,

Dave.
-- 
Dave Chinner
david@xxxxxxxxxxxxx

---
 lib/radix-tree.c |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 9eeb9f3..5d2872c 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1077,6 +1077,11 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
 			break;
 		slots_found = __lookup_tag(node, (void ***)results + ret,
 				cur_index, max_items - ret, &next_index, tag);
+
+		/* livelock avoidance */
+		if (slots_found == 0 && cur_index == next_index)
+			break;
+
 		nr_found = 0;
 		for (i = 0; i < slots_found; i++) {
 			struct radix_tree_node *slot;
@@ -1147,6 +1152,9 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
 			break;
 		slots_found = __lookup_tag(node, results + ret,
 				cur_index, max_items - ret, &next_index, tag);
+		/* livelock avoidance */
+		if (slots_found == 0 && cur_index == next_index)
+			break;
 		ret += slots_found;
 		if (next_index == 0)
 			break;
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/