On Fri, May 11, 2018 at 07:40:26AM +0200, Dmitry Vyukov wrote: > On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini <pbonzini@xxxxxxxxxx> wrote: > > On 10/05/2018 21:16, Roman Kagan wrote: > >> If an IDR contains a single entry at index==0, the underlying radix tree > >> has a single item in its root node, in which case > >> __radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in > >> addition to returning NULL). > >> > >> However, the tree itself is not empty, i.e. the tree root doesn't have > >> IDR_FREE tag. > >> > >> As a result, on an attempt to remove an index!=0 entry from such an IDR, > >> radix_tree_delete_item doesn't return early and calls > >> __radix_tree_delete with invalid parameters which are then dereferenced. > >> > >> Reported-by: syzbot+35666cba7f0a337e2e79@xxxxxxxxxxxxxxxxxxxxxxxxx > >> Signed-off-by: Roman Kagan <rkagan@xxxxxxxxxxxxx> > >> --- > >> lib/radix-tree.c | 5 +++-- > >> 1 file changed, 3 insertions(+), 2 deletions(-) > >> > >> diff --git a/lib/radix-tree.c b/lib/radix-tree.c > >> index da9e10c827df..10ff1bfae952 100644 > >> --- a/lib/radix-tree.c > >> +++ b/lib/radix-tree.c > >> @@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root, > >> void *entry; > >> > >> entry = __radix_tree_lookup(root, index, &node, &slot); > >> - if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, > >> - get_slot_offset(node, slot)))) > >> + if (!entry && (!is_idr(root) || !node || > >> + node_tag_get(root, node, IDR_FREE, > >> + get_slot_offset(node, slot)))) > >> return NULL; > >> > >> if (item && entry != item) > >> > > > > I cannot really vouch for the patch, but if it is correct it's > > definitely stuff for stable. The KVM testcase is only for 4.17-rc but > > this is a really nasty bug in a core data structure. > > > > Cc: stable@xxxxxxxxxxxxxxx > > > > Should radix-tree be compilable in userspace, so that we can add unit > > tests for it?... > > Good point. > > For my education, what/where are the tests that run as user-space code? Actually there are userspace tests for it under tools/tests/radix-tree, but I didn't manage to get them to build. Looks like the recent introduction of a spin_lock in the radix_tree structure (for XArray work?) broke them. Roman.
