linux-kernel - [bug] radix_tree_gang_lookup_tag

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20100818135651.GK7362@dastard>
Date:	Wed, 18 Aug 2010 23:56:51 +1000
From:	Dave Chinner <david@...morbit.com>
To:	linux-kernel@...r.kernel.org
Cc:	linux-fsdevel@...r.kernel.org, npiggin@...nel.dk,
	a.p.zijlstra@...llo.nl, jack@...e.cz
Subject: [bug] radix_tree_gang_lookup_tag_slot() looping endlessly

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@...morbit.com

---
 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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/