From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751753AbcA0EEP (ORCPT ); Tue, 26 Jan 2016 23:04:15 -0500 Received: from mail-pf0-f182.google.com ([209.85.192.182]:36130 "EHLO mail-pf0-f182.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750785AbcA0EEM (ORCPT ); Tue, 26 Jan 2016 23:04:12 -0500 Date: Tue, 26 Jan 2016 20:04:02 -0800 (PST) From: Hugh Dickins X-X-Sender: hugh@eggly.anvils To: Matthew Wilcox cc: linux-kernel@vger.kernel.org, Konstantin Khlebnikov , Hugh Dickins , Andrew Morton Subject: Re: Bug in radix tree gang lookup? In-Reply-To: <20160122134012.GC2948@linux.intel.com> Message-ID: References: <20160122134012.GC2948@linux.intel.com> User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, 22 Jan 2016, Matthew Wilcox wrote: > > I think there's a race in radix_tree_gang_lookup() (and > related functions). I was trying to understand why we need the > 'indirect_to_ptr()' call here: > > radix_tree_for_each_slot(slot, root, &iter, first_index) { > results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); > if (!results[ret]) > continue; > if (++ret == max_items) > break; > } > > The slots returned are supposed to be leaf nodes, so why would they ever > have the indirect bit set? > > The only two cases I can think of where we'd see a slot with the indirect > bit set is if we're calling radix_tree_gang_lookup() under the RCU read > lock and simultaneously growing / shrinking the tree. When the tree > transitions from height 0 to height 1, the 'slot' that was returned is now > an internal pointer, so simply knocking off the 'indirect_to_ptr()' bit > is the wrong thing to do; instead of returning a struct page pointer, we > return a pointer to a radix_tree_node, which isn't good. When shrinking > the tree from height 1 to height 0, we may end up looking at a pointer > in to-be-freed memory, but it's still a valid pointer to a struct page, > so I think we're OK in the shrink case. > > The lockless page cache shows how to handle this correctly; when we > see an indirect bit come back in a slot, we should retry the lookup. > I think that's the right thing to do in this case, but I'd like someone > to check my reasoning before I propose a patch. I think you're right, in all you say above. And I think the last paragraph of comment above the one-level-of-indirection-different radix_tree_gang_lookup_slot() is making the same point, though its language hasn't been updated for years (it ought to say something like "radix_tree_deref_retry may require a retry"). Hugh