linux-kernel - Re: [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-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 18 Aug 2010 19:37:09 +0200
From:	Jan Kara <jack@...e.cz>
To:	Dave Chinner <david@...morbit.com>
Cc:	linux-kernel@...r.kernel.org, linux-fsdevel@...r.kernel.org,
	npiggin@...nel.dk, a.p.zijlstra@...llo.nl, jack@...e.cz
Subject: Re: [bug] radix_tree_gang_lookup_tag_slot() looping endlessly

  Hi,

On Wed 18-08-10 23:56:51, Dave Chinner wrote:
> 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.
  Is this pagevec_lookup_tag() from write_cache_pages() which was called
for fsync() or so? 

> 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.
  Hmm, what HW config do you have? I didn't hit the livelock and I've been
running xfstests several times with the livelock avoidance patch. Hmm,
looking at the code maybe what you describe could happen if we remove the
page from page cache but leave a dangling tag in the radix tree... But
remove_from_page_cache() is called with tree_lock held and it removes all
tags from the index we just remove so it shouldn't really happen. Could
you dump more info about the inode this happens on? Like the i_size, the
index we stall at... Thanks.

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

								Honza
> ---
>  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;
-- 
Jan Kara <jack@...e.cz>
SUSE Labs, CR
--
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/