RE: [PATCH 2/2] radix-tree: Fix optimisation problem

From: Matthew Wilcox
Date: Fri Sep 23 2016 - 16:16:34 EST


From: linus971@xxxxxxxxx [mailto:linus971@xxxxxxxxx] On Behalf Of Linus Torvalds
> On Thu, Sep 22, 2016 at 11:53 AM, Matthew Wilcox
> <mawilcox@xxxxxxxxxxxxxxxxx> wrote:
> >
> > Change the test suite to compile with -O2, and
> > fix the optimisation problem by passing 'entry' through entry_to_node()
> > so gcc knows this isn't a plain pointer.
>
> Ugh. I really don't like this patch very much.
>
> Wouldn't it be cleaner to just fix "get_slot_offset()" instead? As it
> is, looking at the code, I suspect that it's really hard to convince
> people that there isn't some other place this might happen. Because
> the "pointer subtraction followed by pointer addition" pattern is all
> hidden in these inline functions.
>
> Or at least add a big comment about why this is the only such case.
>
> Because without that, the code now looks very bad.

That's fair. I looked at all the other callers of get_slot_offset, and all the others are using a real slot pointer. radix_tree_descend() really is the outlier here. I think the real problem is that the types in the tree are wrong; instead of storing void *, we should be storing uintptr_t. But fixing that is a little beyond the scope of -rc8. Here's a slightly better version which asserts that the passed pointer really is a pointer.

(attached as well, I have no idea whether this patch will get mangled)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1b7bf73..368f641 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -91,9 +91,15 @@ static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
}
#endif

+/*
+ * The slot pointer must be a real pointer as GCC will optimise
+ * through inlined functions and may deduce that
+ * parent->slots + get_slot_offset(parent, slot) == slot
+ */
static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
void **slot)
{
+ BUG_ON(radix_tree_exception(slot));
return slot - parent->slots;
}

@@ -101,11 +107,12 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
struct radix_tree_node **nodep, unsigned long index)
{
unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
- void **entry = rcu_dereference_raw(parent->slots[offset]);
+ void *entry = rcu_dereference_raw(parent->slots[offset]);

#ifdef CONFIG_RADIX_TREE_MULTIORDER
if (radix_tree_is_internal_node(entry)) {
- unsigned long siboff = get_slot_offset(parent, entry);
+ unsigned long siboff = get_slot_offset(parent,
+ (void **)entry_to_node(entry));
if (siboff < RADIX_TREE_MAP_SIZE) {
offset = siboff;
entry = rcu_dereference_raw(parent->slots[offset]);
@@ -113,7 +120,7 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
}
#endif

- *nodep = (void *)entry;
+ *nodep = entry;
return offset;
}

diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 3b53046..9d0919ed 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -1,5 +1,5 @@

-CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
+CFLAGS += -I. -g -O2 -Wall -D_LGPL_SOURCE
LDFLAGS += -lpthread -lurcu
TARGETS = main
OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \

Attachment: for-linus.diff
Description: for-linus.diff