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

[Matthew Wilcox <mawilcox@microsoft.com>]

[-- Attachment #1: Type: text/plain, Size: 3327 bytes --]

From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus Torvalds
> On Thu, Sep 22, 2016 at 11:53 AM, Matthew Wilcox
> <mawilcox@linuxonhyperv.com> 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 #2: for-linus.diff --]
[-- Type: application/octet-stream, Size: 1871 bytes --]

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 \