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

Commit Message

Linus Torvalds Sept. 25, 2016, 7:04 p.m. UTC

On Sun, Sep 25, 2016 at 11:04 AM, Linus Torvalds
<[e-mail]> wrote:
>
> The more I look at that particular piece of code, the less I like it. It's
> buggy shit. It needs to be rewritten entirely too actually check for sibling
> entries, not that ad-hoc arithmetic crap.

Here's my attempt at cleaning the mess up.

I'm not claiming it's perfect, but I think it's better. It gets rid of
the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
be inside the is_sibling_entry() logic instead. Which got renamed and
made to actually return the main sibling. So now there is at least
only *one* piece of code that does that range comparison, and I don't
think there is any huge need to explain what's going on, because the
"magic" is unconditional.

Willy?

                 Linus

Comments

Cedric Blancher Sept. 25, 2016, 7:40 p.m. UTC | #1

LGTM, except that #define is_sibling_entry should be IS_SIBLING_ENTRY

Ced

On 25 September 2016 at 21:04, Linus Torvalds
<[e-mail]> wrote:
> On Sun, Sep 25, 2016 at 11:04 AM, Linus Torvalds
> <[e-mail]> wrote:
>>
>> The more I look at that particular piece of code, the less I like it. It's
>> buggy shit. It needs to be rewritten entirely too actually check for sibling
>> entries, not that ad-hoc arithmetic crap.
>
> Here's my attempt at cleaning the mess up.
>
> I'm not claiming it's perfect, but I think it's better. It gets rid of
> the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
> be inside the is_sibling_entry() logic instead. Which got renamed and
> made to actually return the main sibling. So now there is at least
> only *one* piece of code that does that range comparison, and I don't
> think there is any huge need to explain what's going on, because the
> "magic" is unconditional.
>
> Willy?
>
>                  Linus

Patch

 lib/radix-tree.c | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1b7bf7314141..210709b07759 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -78,18 +78,20 @@  static inline void *node_to_entry(void *ptr)
 
 #ifdef CONFIG_RADIX_TREE_MULTIORDER
 /* Sibling slots point directly to another slot in the same node */
-static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
+static inline void **get_sibling_entry(struct radix_tree_node *parent, void *node)
 {
-	void **ptr = node;
-	return (parent->slots <= ptr) &&
-			(ptr < parent->slots + RADIX_TREE_MAP_SIZE);
+	void **ptr = (void **) entry_to_node(node);
+	if ((parent->slots <= ptr) && (ptr < parent->slots + RADIX_TREE_MAP_SIZE))
+		return ptr;
+	return NULL;
 }
 #else
-static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
+static inline void **get_sibling_entry(struct radix_tree_node *parent, void *node)
 {
-	return false;
+	return NULL;
 }
 #endif
+#define is_sibling_entry(parent, node) (get_sibling_entry(parent,node) != NULL)
 
 static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
 						 void **slot)
@@ -105,10 +107,10 @@  static unsigned int radix_tree_descend(struct radix_tree_node *parent,
 
 #ifdef CONFIG_RADIX_TREE_MULTIORDER
 	if (radix_tree_is_internal_node(entry)) {
-		unsigned long siboff = get_slot_offset(parent, entry);
-		if (siboff < RADIX_TREE_MAP_SIZE) {
-			offset = siboff;
-			entry = rcu_dereference_raw(parent->slots[offset]);
+		void **sibentry = get_sibling_entry(parent, entry);
+		if (sibentry) {
+			offset = get_slot_offset(parent, sibentry);
+			entry = rcu_dereference_raw(*sibentry);
 		}
 	}
 #endif