Re: [bug] radix_tree_gang_lookup_tag_slot() looping endlessly

[Dave Chinner <david@fromorbit.com>]

On Thu, Aug 19, 2010 at 09:29:17AM +1000, Dave Chinner wrote:
> On Wed, Aug 18, 2010 at 07:37:09PM +0200, Jan Kara wrote:
> >   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.

[snip]

> 
> > 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.
> 
> This might be a stupid question, but here goes anyway. I know the
> slot contents are protected on lookup by rcu_read_lock() and
> rcu_dereference_raw(), but what protects the tags on read? AFAICT,
> they are being looked up without any locking, memory barriers, etc
> w.r.t. deletion. i.e. I cannot see how a tag lookup is prevented
> from racing with the propagation of a tag removal back up the tree
> (which is done under the tree lock). What am I missing?

Definitely looks like corrupted tags:

[   97.301618] lookup ino 9283137, size 2106992, mapping pages 146, root 0xffff880073d83e20, index 497, nr_pages 14, tag 1
[   97.301711] lookup ino 9283137, size 2106992, mapping pages 9, root 0xffff880073d83e20, index 75, nr_pages 14, tag 2
[   97.301713] livelock @ root 0xffff880073d83e20, index 256, first 75
[   97.301715] height 2
[   97.301716] shift 6
[   97.301717] tag_get 0xffff8800769f5b40, 4
[   97.301718] height 1
[   97.301719] shift 0
[   97.301720] no more slots 4
[   97.301721] livelock @ root 0xffff880073d83e20, index 256, first 75

The slot (#4) has the tag set, but the actual slot is empty and so
the lookup aborts without changing the index, and as such we have an
endless loop. In this case, it apears to have occurred directly
after the mapping was almost entirely invalidated....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com