[PATCH] lib : do code optimization for radix_tree_lookup() and radix_tree_lookup_slot()

[PATCH] lib : do code optimization for radix_tree_lookup() and radix_tree_lookup_slot()

[Huang Shijie]

 I think radix_tree_lookup() and radix_tree_lookup_slot() have too much 
same code except the return value.
 I introduce the function radix_tree_lookup_element() to do the real work.

/*
 * is_slot == 1 : search for the slot.
 * is_slot == 0 : search for the node.
 */
  static void * radix_tree_lookup_element(struct radix_tree_root *root, 
unsigned long index, int is_slot);

Signed-off-by: Huang Shijie <shijie8@gmail.com>

----

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 4bb42a0..176fd96 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -351,20 +351,12 @@ int radix_tree_insert(struct radix_tree_root *root,
 }
 EXPORT_SYMBOL(radix_tree_insert);
 
-/**
- *    radix_tree_lookup_slot    -    lookup a slot in a radix tree
- *    @root:        radix tree root
- *    @index:        index key
- *
- *    Returns:  the slot corresponding to the position @index in the
- *    radix tree @root. This is useful for update-if-exists operations.
- *
- *    This function can be called under rcu_read_lock iff the slot is not
- *    modified by radix_tree_replace_slot, otherwise it must be called
- *    exclusive from other writers. Any dereference of the slot must be 
done
- *    using radix_tree_deref_slot.
+/*
+ * is_slot == 1 : search for the slot.
+ * is_slot == 0 : search for the node.
  */
-void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned 
long index)
+static void * radix_tree_lookup_element(struct radix_tree_root *root,
+                    unsigned long index, int is_slot)
 {
     unsigned int height, shift;
     struct radix_tree_node *node, **slot;
@@ -376,7 +368,7 @@ void **radix_tree_lookup_slot(struct radix_tree_root 
*root, unsigned long index)
     if (!radix_tree_is_indirect_ptr(node)) {
         if (index > 0)
             return NULL;
-        return (void **)&root->rnode;
+        return is_slot ? (void *)&root->rnode : node;
     }
     node = radix_tree_indirect_to_ptr(node);
 
@@ -397,7 +389,25 @@ void **radix_tree_lookup_slot(struct 
radix_tree_root *root, unsigned long index)
         height--;
     } while (height > 0);
 
-    return (void **)slot;
+    return is_slot ? (void *)slot : node;
+}
+
+/**
+ *    radix_tree_lookup_slot    -    lookup a slot in a radix tree
+ *    @root:        radix tree root
+ *    @index:        index key
+ *
+ *    Returns:  the slot corresponding to the position @index in the
+ *    radix tree @root. This is useful for update-if-exists operations.
+ *
+ *    This function can be called under rcu_read_lock iff the slot is not
+ *    modified by radix_tree_replace_slot, otherwise it must be called
+ *    exclusive from other writers. Any dereference of the slot must be 
done
+ *    using radix_tree_deref_slot.
+ */
+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned 
long index)
+{
+    return (void**)radix_tree_lookup_element(root, index, 1);
 }
 EXPORT_SYMBOL(radix_tree_lookup_slot);
 
@@ -415,38 +425,7 @@ EXPORT_SYMBOL(radix_tree_lookup_slot);
  */
 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 {
-    unsigned int height, shift;
-    struct radix_tree_node *node, **slot;
-
-    node = rcu_dereference(root->rnode);
-    if (node == NULL)
-        return NULL;
-
-    if (!radix_tree_is_indirect_ptr(node)) {
-        if (index > 0)
-            return NULL;
-        return node;
-    }
-    node = radix_tree_indirect_to_ptr(node);
-
-    height = node->height;
-    if (index > radix_tree_maxindex(height))
-        return NULL;
-
-    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
-    do {
-        slot = (struct radix_tree_node **)
-            (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
-        node = rcu_dereference(*slot);
-        if (node == NULL)
-            return NULL;
-
-        shift -= RADIX_TREE_MAP_SHIFT;
-        height--;
-    } while (height > 0);
-
-    return node;
+    return radix_tree_lookup_element(root, index, 0);
 }
 EXPORT_SYMBOL(radix_tree_lookup);
 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] lib : do code optimization for radix_tree_lookup() and radix_tree_lookup_slot()

[Andrew Morton]

On Mon, 11 May 2009 10:04:37 +0800
Huang Shijie <shijie8@gmail.com> wrote:

>  I think radix_tree_lookup() and radix_tree_lookup_slot() have too much 
> same code except the return value.
>  I introduce the function radix_tree_lookup_element() to do the real work.

Fair enough.

The patch was badly wordwrapped and had all its tabs replaced with
spaces.  Please fix your email client before sending any further
patches.

Please also use scripts/checkpatch.pl to check for small stylistic
errors.  This patch introduced several of them.

> --- a/lib/radix-tree.c~lib-do-code-optimization-for-radix_tree_lookup-and-radix_tree_lookup_slot
> +++ a/lib/radix-tree.c
> @@ -351,20 +351,12 @@ int radix_tree_insert(struct radix_tree_
>  }
>  EXPORT_SYMBOL(radix_tree_insert);
>  
> -/**
> - *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
> - *	@root:		radix tree root
> - *	@index:		index key
> - *
> - *	Returns:  the slot corresponding to the position @index in the
> - *	radix tree @root. This is useful for update-if-exists operations.
> - *
> - *	This function can be called under rcu_read_lock iff the slot is not
> - *	modified by radix_tree_replace_slot, otherwise it must be called
> - *	exclusive from other writers. Any dereference of the slot must be done
> - *	using radix_tree_deref_slot.
> +/*
> + * is_slot == 1 : search for the slot.
> + * is_slot == 0 : search for the node.
>   */
> -void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
> +static void * radix_tree_lookup_element(struct radix_tree_root *root,
> +					unsigned long index, int is_slot)
>  {
>  	unsigned int height, shift;
>  	struct radix_tree_node *node, **slot;
> @@ -376,7 +368,7 @@ void **radix_tree_lookup_slot(struct rad
>  	if (!radix_tree_is_indirect_ptr(node)) {
>  		if (index > 0)
>  			return NULL;
> -		return (void **)&root->rnode;
> +		return is_slot ? (void *)&root->rnode : node;
>  	}
>  	node = radix_tree_indirect_to_ptr(node);
>  
> @@ -397,7 +389,25 @@ void **radix_tree_lookup_slot(struct rad
>  		height--;
>  	} while (height > 0);
>  
> -	return (void **)slot;
> +	return is_slot ? (void *)slot : node;

hm, yes, the cast is needed to prevent "warning: pointer type mismatch
in conditional expression".  Stupid gcc.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] lib : do code optimization for radix_tree_lookup() and radix_tree_lookup_slot()

[Huang Shijie]

Andrew Morton a??e??:
> On Mon, 11 May 2009 10:04:37 +0800
> Huang Shijie <shijie8@gmail.com> wrote:
>
>   
>>  I think radix_tree_lookup() and radix_tree_lookup_slot() have too much 
>> same code except the return value.
>>  I introduce the function radix_tree_lookup_element() to do the real work.
>>     
>
> Fair enough.
>
> The patch was badly wordwrapped and had all its tabs replaced with
> spaces.  Please fix your email client before sending any further
> patches.
>
> Please also use scripts/checkpatch.pl to check for small stylistic
> errors.  This patch introduced several of them.
>
>   
Thanks. I changed the patch ,and resend the patch as below .

Signed-off-by: Huang Shijie <shijie8@gmail.com>

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 4bb42a0..defba9b 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -351,20 +351,12 @@ int radix_tree_insert(struct radix_tree_root *root,
 }
 EXPORT_SYMBOL(radix_tree_insert);
 
-/**
- *    radix_tree_lookup_slot    -    lookup a slot in a radix tree
- *    @root:        radix tree root
- *    @index:        index key
- *
- *    Returns:  the slot corresponding to the position @index in the
- *    radix tree @root. This is useful for update-if-exists operations.
- *
- *    This function can be called under rcu_read_lock iff the slot is not
- *    modified by radix_tree_replace_slot, otherwise it must be called
- *    exclusive from other writers. Any dereference of the slot must be 
done
- *    using radix_tree_deref_slot.
+/*
+ * is_slot == 1 : search for the slot.
+ * is_slot == 0 : search for the node.
  */
-void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned 
long index)
+static void *radix_tree_lookup_element(struct radix_tree_root *root,
+                unsigned long index, int is_slot)
 {
     unsigned int height, shift;
     struct radix_tree_node *node, **slot;
@@ -376,7 +368,7 @@ void **radix_tree_lookup_slot(struct radix_tree_root 
*root, unsigned long index)
     if (!radix_tree_is_indirect_ptr(node)) {
         if (index > 0)
             return NULL;
-        return (void **)&root->rnode;
+        return is_slot ? (void *)&root->rnode : node;
     }
     node = radix_tree_indirect_to_ptr(node);
 
@@ -397,7 +389,25 @@ void **radix_tree_lookup_slot(struct 
radix_tree_root *root, unsigned long index)
         height--;
     } while (height > 0);
 
-    return (void **)slot;
+    return is_slot ? (void *)slot:node;
+}
+
+/**
+ *    radix_tree_lookup_slot    -    lookup a slot in a radix tree
+ *    @root:        radix tree root
+ *    @index:        index key
+ *
+ *    Returns:  the slot corresponding to the position @index in the
+ *    radix tree @root. This is useful for update-if-exists operations.
+ *
+ *    This function can be called under rcu_read_lock iff the slot is not
+ *    modified by radix_tree_replace_slot, otherwise it must be called
+ *    exclusive from other writers. Any dereference of the slot must be 
done
+ *    using radix_tree_deref_slot.
+ */
+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned 
long index)
+{
+    return (void **)radix_tree_lookup_element(root, index, 1);
 }
 EXPORT_SYMBOL(radix_tree_lookup_slot);
 
@@ -415,38 +425,7 @@ EXPORT_SYMBOL(radix_tree_lookup_slot);
  */
 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 {
-    unsigned int height, shift;
-    struct radix_tree_node *node, **slot;
-
-    node = rcu_dereference(root->rnode);
-    if (node == NULL)
-        return NULL;
-
-    if (!radix_tree_is_indirect_ptr(node)) {
-        if (index > 0)
-            return NULL;
-        return node;
-    }
-    node = radix_tree_indirect_to_ptr(node);
-
-    height = node->height;
-    if (index > radix_tree_maxindex(height))
-        return NULL;
-
-    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
-    do {
-        slot = (struct radix_tree_node **)
-            (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
-        node = rcu_dereference(*slot);
-        if (node == NULL)
-            return NULL;
-
-        shift -= RADIX_TREE_MAP_SHIFT;
-        height--;
-    } while (height > 0);
-
-    return node;
+    return radix_tree_lookup_element(root, index, 0);
 }
 EXPORT_SYMBOL(radix_tree_lookup);
 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] lib : do code optimization for radix_tree_lookup() and radix_tree_lookup_slot()

[Huang Shijie]

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

Andrew Morton a??e??:
> On Mon, 11 May 2009 10:04:37 +0800
> Huang Shijie <shijie8@gmail.com> wrote:
>
>   
>>  I think radix_tree_lookup() and radix_tree_lookup_slot() have too much 
>> same code except the return value.
>>  I introduce the function radix_tree_lookup_element() to do the real work.
>>     
>
> Fair enough.
>
> The patch was badly wordwrapped and had all its tabs replaced with
> spaces.  Please fix your email client before sending any further
> patches.
>
> Please also use scripts/checkpatch.pl to check for small stylistic
> errors.  This patch introduced several of them.
>
>   
I feel embararssed to find  that my second patch still has  probloms 
with my email client(thunderbird).

I put the patch  within the attachment.

Sorry to waste your time. I will send patch with "git-send-email" in future.

thanks.


 

[-- Attachment #2: radix_tree.patch --]
[-- Type: text/x-patch, Size: 3312 bytes --]

Signed-off-by: Huang Shijie <shijie8@gmail.com>
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 4bb42a0..defba9b 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -351,20 +351,12 @@ int radix_tree_insert(struct radix_tree_root *root,
 }
 EXPORT_SYMBOL(radix_tree_insert);
 
-/**
- *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
- *	@root:		radix tree root
- *	@index:		index key
- *
- *	Returns:  the slot corresponding to the position @index in the
- *	radix tree @root. This is useful for update-if-exists operations.
- *
- *	This function can be called under rcu_read_lock iff the slot is not
- *	modified by radix_tree_replace_slot, otherwise it must be called
- *	exclusive from other writers. Any dereference of the slot must be done
- *	using radix_tree_deref_slot.
+/*
+ * is_slot == 1 : search for the slot.
+ * is_slot == 0 : search for the node.
  */
-void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
+static void *radix_tree_lookup_element(struct radix_tree_root *root,
+				unsigned long index, int is_slot)
 {
 	unsigned int height, shift;
 	struct radix_tree_node *node, **slot;
@@ -376,7 +368,7 @@ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
 	if (!radix_tree_is_indirect_ptr(node)) {
 		if (index > 0)
 			return NULL;
-		return (void **)&root->rnode;
+		return is_slot ? (void *)&root->rnode : node;
 	}
 	node = radix_tree_indirect_to_ptr(node);
 
@@ -397,7 +389,25 @@ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
 		height--;
 	} while (height > 0);
 
-	return (void **)slot;
+	return is_slot ? (void *)slot:node;
+}
+
+/**
+ *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
+ *	@root:		radix tree root
+ *	@index:		index key
+ *
+ *	Returns:  the slot corresponding to the position @index in the
+ *	radix tree @root. This is useful for update-if-exists operations.
+ *
+ *	This function can be called under rcu_read_lock iff the slot is not
+ *	modified by radix_tree_replace_slot, otherwise it must be called
+ *	exclusive from other writers. Any dereference of the slot must be done
+ *	using radix_tree_deref_slot.
+ */
+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
+{
+	return (void **)radix_tree_lookup_element(root, index, 1);
 }
 EXPORT_SYMBOL(radix_tree_lookup_slot);
 
@@ -415,38 +425,7 @@ EXPORT_SYMBOL(radix_tree_lookup_slot);
  */
 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 {
-	unsigned int height, shift;
-	struct radix_tree_node *node, **slot;
-
-	node = rcu_dereference(root->rnode);
-	if (node == NULL)
-		return NULL;
-
-	if (!radix_tree_is_indirect_ptr(node)) {
-		if (index > 0)
-			return NULL;
-		return node;
-	}
-	node = radix_tree_indirect_to_ptr(node);
-
-	height = node->height;
-	if (index > radix_tree_maxindex(height))
-		return NULL;
-
-	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
-	do {
-		slot = (struct radix_tree_node **)
-			(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
-		node = rcu_dereference(*slot);
-		if (node == NULL)
-			return NULL;
-
-		shift -= RADIX_TREE_MAP_SHIFT;
-		height--;
-	} while (height > 0);
-
-	return node;
+	return radix_tree_lookup_element(root, index, 0);
 }
 EXPORT_SYMBOL(radix_tree_lookup);