linux-kernel - Bug in radix tree gang lookup?

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]

Date:	Fri, 22 Jan 2016 08:40:12 -0500
From:	Matthew Wilcox <willy@...ux.intel.com>
To:	linux-kernel@...r.kernel.org,
	Konstantin Khlebnikov <khlebnikov@...nvz.org>,
	Hugh Dickins <hughd@...gle.com>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Bug in radix tree gang lookup?

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.