RE: [PATCH 2/2] radix-tree: Fix optimisation problem
From: Matthew Wilcox <hidden>
Date: 2016-09-23 20:16:26
Also in:
linux-fsdevel, lkml
Subsystem:
library code, the rest · Maintainers:
Andrew Morton, Linus Torvalds
From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus Torvalds
On Thu, Sep 22, 2016 at 11:53 AM, Matthew Wilcox [off-list ref] wrote:quoted
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 \
Attachments
- for-linus.diff [application/octet-stream] 1871 bytes · preview