Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1490433

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

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

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 \

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH 0/2] Fix radix_tree_lookup_slot() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-09-22 19:10 +0200
  [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-09-22 19:10 +0200
    Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-22 20:20 +0200
      RE: [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-23 22:20 +0200
        Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-24 22:30 +0200
          Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-24 22:50 +0200
          Re: [PATCH 2/2] radix-tree: Fix optimisation problem "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> - 2016-09-24 23:10 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 01:00 +0200
    Re: [PATCH 2/2] radix-tree: Fix optimisation problem Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-24 10:40 +0200
    Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 01:40 +0200
      Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 02:20 +0200
        Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 20:00 +0200
          Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 21:10 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 21:50 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 22:00 +0200
              RE: [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-26 23:30 +0200
                Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-26 23:50 +0200
  [PATCH 1/2] radix tree test suite: Test radix_tree_replace_slot() for multiorder entries Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-09-22 19:10 +0200

csiph-web