[PATCH] radix_tree: take radix_tree_path off stack

[PATCH] radix_tree: take radix_tree_path off stack

[Hugh Dickins]

Down, down in the deepest depths of GFP_NOIO page reclaim, we have
shrink_page_list() calling __remove_mapping() calling __delete_from_
swap_cache() or __delete_from_page_cache().

You would not expect those to need much stack, but in fact they call
radix_tree_delete(): which declares a 192-byte radix_tree_path array
on its stack (to record the node,offsets it visits when descending,
in case it needs to ascend to update them).  And if any tag is still
set [1], that calls radix_tree_tag_clear(), which declares a further
such 192-byte radix_tree_path array on the stack.  (At least we have
interrupts disabled here, so won't then be pushing registers too.)

That was probably a good choice when most users were 32-bit (array
of half the size), and adding fields to radix_tree_node would have
bloated it unnecessarily.  But nowadays many are 64-bit, and each
radix_tree_node contains a struct rcu_head, which is only used when
freeing; whereas the radix_tree_path info is only used for updating
the tree (deleting, clearing tags or setting tags if tagged) when a
lock must be held, of no interest when accessing the tree locklessly.

So add a parent pointer to the radix_tree_node, in union with the
rcu_head, and remove all uses of the radix_tree_path.  There would
be space in that union to save the offset when descending as before
(we can argue that a lock must already be held to exclude other users),
but recalculating it when ascending is both easy (a constant shift and
a constant mask) and uncommon, so it seems better just to do that.

Two little optimizations: no need to decrement height when descending,
adjusting shift is enough; and once radix_tree_tag_if_tagged() has set
tag on a node and its ancestors, it need not ascend from that node again.

perf on the radix tree test harness reports radix_tree_insert() as 2%
slower (now having to set parent), but radix_tree_delete() 24% faster.
Surely that's an exaggeration from rtth's artificially low map shift 3,
but forcing it back to 6 still rates radix_tree_delete() 8% faster.

[1] Can a pagecache tag (dirty, writeback or towrite) actually still be
set at the time of radix_tree_delete()?  Perhaps not if the filesystem
is well-behaved.  But although I've not tracked any stack overflow down
to this cause, I have observed a curious case in which a dirty tag is
set and left set on tmpfs: page migration's migrate_page_copy() happens
to use __set_page_dirty_nobuffers() to set PageDirty on the newpage,
and that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
filesystem which doesn't use tags, except for this stack depth issue.

Signed-off-by: Hugh Dickins <hughd@google.com>
----

 lib/radix-tree.c |  148 +++++++++++++++++++++------------------------
 1 file changed, 70 insertions(+), 78 deletions(-)

--- 3.2-rc6/lib/radix-tree.c	2011-11-07 19:24:53.342418579 -0800
+++ linux/lib/radix-tree.c	2011-12-16 20:40:26.152758485 -0800
@@ -48,16 +48,14 @@
 struct radix_tree_node {
 	unsigned int	height;		/* Height from the bottom */
 	unsigned int	count;
-	struct rcu_head	rcu_head;
+	union {
+		struct radix_tree_node *parent;	/* Used when ascending tree */
+		struct rcu_head	rcu_head;	/* Used when freeing node */
+	};
 	void __rcu	*slots[RADIX_TREE_MAP_SIZE];
 	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
 };
 
-struct radix_tree_path {
-	struct radix_tree_node *node;
-	int offset;
-};
-
 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
 					  RADIX_TREE_MAP_SHIFT))
@@ -256,6 +254,7 @@ static inline unsigned long radix_tree_m
 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
 {
 	struct radix_tree_node *node;
+	struct radix_tree_node *slot;
 	unsigned int height;
 	int tag;
 
@@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
 		if (!(node = radix_tree_node_alloc(root)))
 			return -ENOMEM;
 
-		/* Increase the height.  */
-		node->slots[0] = indirect_to_ptr(root->rnode);
-
 		/* Propagate the aggregated tag info into the new root */
 		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
 			if (root_tag_get(root, tag))
 				tag_set(node, tag, 0);
 		}
 
+		/* Increase the height.  */
 		newheight = root->height+1;
 		node->height = newheight;
 		node->count = 1;
+		node->parent = NULL;
+		slot = root->rnode;
+		if (newheight > 1) {
+			slot = indirect_to_ptr(slot);
+			slot->parent = node;
+		}
+		node->slots[0] = slot;
 		node = ptr_to_indirect(node);
 		rcu_assign_pointer(root->rnode, node);
 		root->height = newheight;
@@ -331,6 +335,7 @@ int radix_tree_insert(struct radix_tree_
 			if (!(slot = radix_tree_node_alloc(root)))
 				return -ENOMEM;
 			slot->height = height;
+			slot->parent = node;
 			if (node) {
 				rcu_assign_pointer(node->slots[offset], slot);
 				node->count++;
@@ -504,47 +509,41 @@ EXPORT_SYMBOL(radix_tree_tag_set);
 void *radix_tree_tag_clear(struct radix_tree_root *root,
 			unsigned long index, unsigned int tag)
 {
-	/*
-	 * The radix tree path needs to be one longer than the maximum path
-	 * since the "list" is null terminated.
-	 */
-	struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
+	struct radix_tree_node *node = NULL;
 	struct radix_tree_node *slot = NULL;
 	unsigned int height, shift;
+	int uninitialized_var(offset);
 
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
 		goto out;
 
-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-	pathp->node = NULL;
+	shift = height * RADIX_TREE_MAP_SHIFT;
 	slot = indirect_to_ptr(root->rnode);
 
-	while (height > 0) {
-		int offset;
-
+	while (shift) {
 		if (slot == NULL)
 			goto out;
 
+		shift -= RADIX_TREE_MAP_SHIFT;
 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-		pathp[1].offset = offset;
-		pathp[1].node = slot;
+		node = slot;
 		slot = slot->slots[offset];
-		pathp++;
-		shift -= RADIX_TREE_MAP_SHIFT;
-		height--;
 	}
 
 	if (slot == NULL)
 		goto out;
 
-	while (pathp->node) {
-		if (!tag_get(pathp->node, tag, pathp->offset))
+	while (node) {
+		if (!tag_get(node, tag, offset))
 			goto out;
-		tag_clear(pathp->node, tag, pathp->offset);
-		if (any_tag_set(pathp->node, tag))
+		tag_clear(node, tag, offset);
+		if (any_tag_set(node, tag))
 			goto out;
-		pathp--;
+
+		index >>= RADIX_TREE_MAP_SHIFT;
+		offset = index & RADIX_TREE_MAP_MASK;
+		node = node->parent;
 	}
 
 	/* clear the root's tag bit */
@@ -646,8 +645,7 @@ unsigned long radix_tree_range_tag_if_ta
 		unsigned int iftag, unsigned int settag)
 {
 	unsigned int height = root->height;
-	struct radix_tree_path path[height];
-	struct radix_tree_path *pathp = path;
+	struct radix_tree_node *node = NULL;
 	struct radix_tree_node *slot;
 	unsigned int shift;
 	unsigned long tagged = 0;
@@ -671,14 +669,8 @@ unsigned long radix_tree_range_tag_if_ta
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 	slot = indirect_to_ptr(root->rnode);
 
-	/*
-	 * we fill the path from (root->height - 2) to 0, leaving the index at
-	 * (root->height - 1) as a terminator. Zero the node in the terminator
-	 * so that we can use this to end walk loops back up the path.
-	 */
-	path[height - 1].node = NULL;
-
 	for (;;) {
+		unsigned long upindex;
 		int offset;
 
 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
@@ -686,12 +678,10 @@ unsigned long radix_tree_range_tag_if_ta
 			goto next;
 		if (!tag_get(slot, iftag, offset))
 			goto next;
-		if (height > 1) {
+		if (shift) {
 			/* Go down one level */
-			height--;
 			shift -= RADIX_TREE_MAP_SHIFT;
-			path[height - 1].node = slot;
-			path[height - 1].offset = offset;
+			node = slot;
 			slot = slot->slots[offset];
 			continue;
 		}
@@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
 		tag_set(slot, settag, offset);
 
 		/* walk back up the path tagging interior nodes */
-		pathp = &path[0];
-		while (pathp->node) {
+		upindex = index;
+		while (node) {
+			upindex >>= RADIX_TREE_MAP_SHIFT;
+			offset = upindex & RADIX_TREE_MAP_MASK;
+
 			/* stop if we find a node with the tag already set */
-			if (tag_get(pathp->node, settag, pathp->offset))
+			if (tag_get(node, settag, offset))
 				break;
-			tag_set(pathp->node, settag, pathp->offset);
-			pathp++;
+			tag_set(node, settag, offset);
+			node = node->parent;
 		}
 
+		/* optimization: no need to walk up from this node again */
+		node = NULL;
+
 next:
 		/* Go to next item at level determined by 'shift' */
 		index = ((index >> shift) + 1) << shift;
@@ -724,8 +720,7 @@ next:
 			 * last_index is guaranteed to be in the tree, what
 			 * we do below cannot wander astray.
 			 */
-			slot = path[height - 1].node;
-			height++;
+			slot = slot->parent;
 			shift += RADIX_TREE_MAP_SHIFT;
 		}
 	}
@@ -1299,7 +1294,7 @@ static inline void radix_tree_shrink(str
 	/* try to shrink tree height */
 	while (root->height > 0) {
 		struct radix_tree_node *to_free = root->rnode;
-		void *newptr;
+		struct radix_tree_node *slot;
 
 		BUG_ON(!radix_tree_is_indirect_ptr(to_free));
 		to_free = indirect_to_ptr(to_free);
@@ -1320,10 +1315,12 @@ static inline void radix_tree_shrink(str
 		 * (to_free->slots[0]), it will be safe to dereference the new
 		 * one (root->rnode) as far as dependent read barriers go.
 		 */
-		newptr = to_free->slots[0];
-		if (root->height > 1)
-			newptr = ptr_to_indirect(newptr);
-		root->rnode = newptr;
+		slot = to_free->slots[0];
+		if (root->height > 1) {
+			slot->parent = NULL;
+			slot = ptr_to_indirect(slot);
+		}
+		root->rnode = slot;
 		root->height--;
 
 		/*
@@ -1363,16 +1360,12 @@ static inline void radix_tree_shrink(str
  */
 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 {
-	/*
-	 * The radix tree path needs to be one longer than the maximum path
-	 * since the "list" is null terminated.
-	 */
-	struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
+	struct radix_tree_node *node = NULL;
 	struct radix_tree_node *slot = NULL;
 	struct radix_tree_node *to_free;
 	unsigned int height, shift;
 	int tag;
-	int offset;
+	int uninitialized_var(offset);
 
 	height = root->height;
 	if (index > radix_tree_maxindex(height))
@@ -1385,39 +1378,35 @@ void *radix_tree_delete(struct radix_tre
 		goto out;
 	}
 	slot = indirect_to_ptr(slot);
-
-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-	pathp->node = NULL;
+	shift = height * RADIX_TREE_MAP_SHIFT;
 
 	do {
 		if (slot == NULL)
 			goto out;
 
-		pathp++;
+		shift -= RADIX_TREE_MAP_SHIFT;
 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-		pathp->offset = offset;
-		pathp->node = slot;
+		node = slot;
 		slot = slot->slots[offset];
-		shift -= RADIX_TREE_MAP_SHIFT;
-		height--;
-	} while (height > 0);
+	} while (shift);
 
 	if (slot == NULL)
 		goto out;
 
 	/*
-	 * Clear all tags associated with the just-deleted item
+	 * Clear all tags associated with the item to be deleted.
+	 * This way of doing it would be inefficient, but seldom is any set.
 	 */
 	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
-		if (tag_get(pathp->node, tag, pathp->offset))
+		if (tag_get(node, tag, offset))
 			radix_tree_tag_clear(root, index, tag);
 	}
 
 	to_free = NULL;
 	/* Now free the nodes we do not need anymore */
-	while (pathp->node) {
-		pathp->node->slots[pathp->offset] = NULL;
-		pathp->node->count--;
+	while (node) {
+		node->slots[offset] = NULL;
+		node->count--;
 		/*
 		 * Queue the node for deferred freeing after the
 		 * last reference to it disappears (set NULL, above).
@@ -1425,17 +1414,20 @@ void *radix_tree_delete(struct radix_tre
 		if (to_free)
 			radix_tree_node_free(to_free);
 
-		if (pathp->node->count) {
-			if (pathp->node == indirect_to_ptr(root->rnode))
+		if (node->count) {
+			if (node == indirect_to_ptr(root->rnode))
 				radix_tree_shrink(root);
 			goto out;
 		}
 
 		/* Node with zero slots in use so free it */
-		to_free = pathp->node;
-		pathp--;
+		to_free = node;
 
+		index >>= RADIX_TREE_MAP_SHIFT;
+		offset = index & RADIX_TREE_MAP_MASK;
+		node = node->parent;
 	}
+
 	root_tag_clear_all(root);
 	root->height = 0;
 	root->rnode = NULL;

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[nai.xia]

On 2011a1'12ae??19ae?JPY 14:41, Hugh Dickins wrote:
> Down, down in the deepest depths of GFP_NOIO page reclaim, we have
> shrink_page_list() calling __remove_mapping() calling __delete_from_
> swap_cache() or __delete_from_page_cache().
>
> You would not expect those to need much stack, but in fact they call
> radix_tree_delete(): which declares a 192-byte radix_tree_path array
> on its stack (to record the node,offsets it visits when descending,
> in case it needs to ascend to update them).  And if any tag is still
> set [1], that calls radix_tree_tag_clear(), which declares a further
> such 192-byte radix_tree_path array on the stack.  (At least we have
> interrupts disabled here, so won't then be pushing registers too.)
>
> That was probably a good choice when most users were 32-bit (array
> of half the size), and adding fields to radix_tree_node would have
> bloated it unnecessarily.  But nowadays many are 64-bit, and each
> radix_tree_node contains a struct rcu_head, which is only used when

Can rcu_head in someway unionized with radix_tree_node->height
and radix_tree_node->count? count is always referenced under lock
and only the first node's height is referenced during lookup.
Seems like if we atomically set root->rnode to NULL, before
freeing the last node, we can ensure a valid read of the
radix_tree_node->height when lookup by following it with
a root->rnode == NULL test.

I am not very sure of course, just a naive feeling.


> freeing; whereas the radix_tree_path info is only used for updating
> the tree (deleting, clearing tags or setting tags if tagged) when a
> lock must be held, of no interest when accessing the tree locklessly.
>
> So add a parent pointer to the radix_tree_node, in union with the
> rcu_head, and remove all uses of the radix_tree_path.  There would
> be space in that union to save the offset when descending as before
> (we can argue that a lock must already be held to exclude other users),
> but recalculating it when ascending is both easy (a constant shift and
> a constant mask) and uncommon, so it seems better just to do that.
>
> Two little optimizations: no need to decrement height when descending,
> adjusting shift is enough; and once radix_tree_tag_if_tagged() has set
> tag on a node and its ancestors, it need not ascend from that node again.
>
> perf on the radix tree test harness reports radix_tree_insert() as 2%
> slower (now having to set parent), but radix_tree_delete() 24% faster.
> Surely that's an exaggeration from rtth's artificially low map shift 3,
> but forcing it back to 6 still rates radix_tree_delete() 8% faster.
>
> [1] Can a pagecache tag (dirty, writeback or towrite) actually still be
> set at the time of radix_tree_delete()?  Perhaps not if the filesystem
> is well-behaved.  But although I've not tracked any stack overflow down
> to this cause, I have observed a curious case in which a dirty tag is
> set and left set on tmpfs: page migration's migrate_page_copy() happens
> to use __set_page_dirty_nobuffers() to set PageDirty on the newpage,
> and that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
> filesystem which doesn't use tags, except for this stack depth issue.
>
> Signed-off-by: Hugh Dickins<hughd@google.com>
> ----
>
>   lib/radix-tree.c |  148 +++++++++++++++++++++------------------------
>   1 file changed, 70 insertions(+), 78 deletions(-)
>
> --- 3.2-rc6/lib/radix-tree.c	2011-11-07 19:24:53.342418579 -0800
> +++ linux/lib/radix-tree.c	2011-12-16 20:40:26.152758485 -0800
> @@ -48,16 +48,14 @@
>   struct radix_tree_node {
>   	unsigned int	height;		/* Height from the bottom */
>   	unsigned int	count;
> -	struct rcu_head	rcu_head;
> +	union {
> +		struct radix_tree_node *parent;	/* Used when ascending tree */
> +		struct rcu_head	rcu_head;	/* Used when freeing node */
> +	};
>   	void __rcu	*slots[RADIX_TREE_MAP_SIZE];
>   	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
>   };
>
> -struct radix_tree_path {
> -	struct radix_tree_node *node;
> -	int offset;
> -};
> -
>   #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
>   #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
>   					  RADIX_TREE_MAP_SHIFT))
> @@ -256,6 +254,7 @@ static inline unsigned long radix_tree_m
>   static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
>   {
>   	struct radix_tree_node *node;
> +	struct radix_tree_node *slot;
>   	unsigned int height;
>   	int tag;
>
> @@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
>   		if (!(node = radix_tree_node_alloc(root)))
>   			return -ENOMEM;
>
> -		/* Increase the height.  */
> -		node->slots[0] = indirect_to_ptr(root->rnode);
> -
>   		/* Propagate the aggregated tag info into the new root */
>   		for (tag = 0; tag<  RADIX_TREE_MAX_TAGS; tag++) {
>   			if (root_tag_get(root, tag))
>   				tag_set(node, tag, 0);
>   		}
>
> +		/* Increase the height.  */
>   		newheight = root->height+1;
>   		node->height = newheight;
>   		node->count = 1;
> +		node->parent = NULL;
> +		slot = root->rnode;
> +		if (newheight>  1) {
> +			slot = indirect_to_ptr(slot);
> +			slot->parent = node;
> +		}
> +		node->slots[0] = slot;
>   		node = ptr_to_indirect(node);
>   		rcu_assign_pointer(root->rnode, node);
>   		root->height = newheight;
> @@ -331,6 +335,7 @@ int radix_tree_insert(struct radix_tree_
>   			if (!(slot = radix_tree_node_alloc(root)))
>   				return -ENOMEM;
>   			slot->height = height;
> +			slot->parent = node;
>   			if (node) {
>   				rcu_assign_pointer(node->slots[offset], slot);
>   				node->count++;
> @@ -504,47 +509,41 @@ EXPORT_SYMBOL(radix_tree_tag_set);
>   void *radix_tree_tag_clear(struct radix_tree_root *root,
>   			unsigned long index, unsigned int tag)
>   {
> -	/*
> -	 * The radix tree path needs to be one longer than the maximum path
> -	 * since the "list" is null terminated.
> -	 */
> -	struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
> +	struct radix_tree_node *node = NULL;
>   	struct radix_tree_node *slot = NULL;
>   	unsigned int height, shift;
> +	int uninitialized_var(offset);
>
>   	height = root->height;
>   	if (index>  radix_tree_maxindex(height))
>   		goto out;
>
> -	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
> -	pathp->node = NULL;
> +	shift = height * RADIX_TREE_MAP_SHIFT;
>   	slot = indirect_to_ptr(root->rnode);
>
> -	while (height>  0) {
> -		int offset;
> -
> +	while (shift) {
>   		if (slot == NULL)
>   			goto out;
>
> +		shift -= RADIX_TREE_MAP_SHIFT;
>   		offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
> -		pathp[1].offset = offset;
> -		pathp[1].node = slot;
> +		node = slot;
>   		slot = slot->slots[offset];
> -		pathp++;
> -		shift -= RADIX_TREE_MAP_SHIFT;
> -		height--;
>   	}
>
>   	if (slot == NULL)
>   		goto out;
>
> -	while (pathp->node) {
> -		if (!tag_get(pathp->node, tag, pathp->offset))
> +	while (node) {
> +		if (!tag_get(node, tag, offset))
>   			goto out;
> -		tag_clear(pathp->node, tag, pathp->offset);
> -		if (any_tag_set(pathp->node, tag))
> +		tag_clear(node, tag, offset);
> +		if (any_tag_set(node, tag))
>   			goto out;
> -		pathp--;
> +
> +		index>>= RADIX_TREE_MAP_SHIFT;
> +		offset = index&  RADIX_TREE_MAP_MASK;
> +		node = node->parent;
>   	}
>
>   	/* clear the root's tag bit */
> @@ -646,8 +645,7 @@ unsigned long radix_tree_range_tag_if_ta
>   		unsigned int iftag, unsigned int settag)
>   {
>   	unsigned int height = root->height;
> -	struct radix_tree_path path[height];
> -	struct radix_tree_path *pathp = path;
> +	struct radix_tree_node *node = NULL;
>   	struct radix_tree_node *slot;
>   	unsigned int shift;
>   	unsigned long tagged = 0;
> @@ -671,14 +669,8 @@ unsigned long radix_tree_range_tag_if_ta
>   	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
>   	slot = indirect_to_ptr(root->rnode);
>
> -	/*
> -	 * we fill the path from (root->height - 2) to 0, leaving the index at
> -	 * (root->height - 1) as a terminator. Zero the node in the terminator
> -	 * so that we can use this to end walk loops back up the path.
> -	 */
> -	path[height - 1].node = NULL;
> -
>   	for (;;) {
> +		unsigned long upindex;
>   		int offset;
>
>   		offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
> @@ -686,12 +678,10 @@ unsigned long radix_tree_range_tag_if_ta
>   			goto next;
>   		if (!tag_get(slot, iftag, offset))
>   			goto next;
> -		if (height>  1) {
> +		if (shift) {
>   			/* Go down one level */
> -			height--;
>   			shift -= RADIX_TREE_MAP_SHIFT;
> -			path[height - 1].node = slot;
> -			path[height - 1].offset = offset;
> +			node = slot;
>   			slot = slot->slots[offset];
>   			continue;
>   		}
> @@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
>   		tag_set(slot, settag, offset);
>
>   		/* walk back up the path tagging interior nodes */
> -		pathp =&path[0];
> -		while (pathp->node) {
> +		upindex = index;
> +		while (node) {
> +			upindex>>= RADIX_TREE_MAP_SHIFT;
> +			offset = upindex&  RADIX_TREE_MAP_MASK;
> +
>   			/* stop if we find a node with the tag already set */
> -			if (tag_get(pathp->node, settag, pathp->offset))
> +			if (tag_get(node, settag, offset))
>   				break;
> -			tag_set(pathp->node, settag, pathp->offset);
> -			pathp++;
> +			tag_set(node, settag, offset);
> +			node = node->parent;
>   		}
>
> +		/* optimization: no need to walk up from this node again */
> +		node = NULL;
> +
>   next:
>   		/* Go to next item at level determined by 'shift' */
>   		index = ((index>>  shift) + 1)<<  shift;
> @@ -724,8 +720,7 @@ next:
>   			 * last_index is guaranteed to be in the tree, what
>   			 * we do below cannot wander astray.
>   			 */
> -			slot = path[height - 1].node;
> -			height++;
> +			slot = slot->parent;
>   			shift += RADIX_TREE_MAP_SHIFT;
>   		}
>   	}
> @@ -1299,7 +1294,7 @@ static inline void radix_tree_shrink(str
>   	/* try to shrink tree height */
>   	while (root->height>  0) {
>   		struct radix_tree_node *to_free = root->rnode;
> -		void *newptr;
> +		struct radix_tree_node *slot;
>
>   		BUG_ON(!radix_tree_is_indirect_ptr(to_free));
>   		to_free = indirect_to_ptr(to_free);
> @@ -1320,10 +1315,12 @@ static inline void radix_tree_shrink(str
>   		 * (to_free->slots[0]), it will be safe to dereference the new
>   		 * one (root->rnode) as far as dependent read barriers go.
>   		 */
> -		newptr = to_free->slots[0];
> -		if (root->height>  1)
> -			newptr = ptr_to_indirect(newptr);
> -		root->rnode = newptr;
> +		slot = to_free->slots[0];
> +		if (root->height>  1) {
> +			slot->parent = NULL;
> +			slot = ptr_to_indirect(slot);
> +		}
> +		root->rnode = slot;
>   		root->height--;
>
>   		/*
> @@ -1363,16 +1360,12 @@ static inline void radix_tree_shrink(str
>    */
>   void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
>   {
> -	/*
> -	 * The radix tree path needs to be one longer than the maximum path
> -	 * since the "list" is null terminated.
> -	 */
> -	struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
> +	struct radix_tree_node *node = NULL;
>   	struct radix_tree_node *slot = NULL;
>   	struct radix_tree_node *to_free;
>   	unsigned int height, shift;
>   	int tag;
> -	int offset;
> +	int uninitialized_var(offset);
>
>   	height = root->height;
>   	if (index>  radix_tree_maxindex(height))
> @@ -1385,39 +1378,35 @@ void *radix_tree_delete(struct radix_tre
>   		goto out;
>   	}
>   	slot = indirect_to_ptr(slot);
> -
> -	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
> -	pathp->node = NULL;
> +	shift = height * RADIX_TREE_MAP_SHIFT;
>
>   	do {
>   		if (slot == NULL)
>   			goto out;
>
> -		pathp++;
> +		shift -= RADIX_TREE_MAP_SHIFT;
>   		offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
> -		pathp->offset = offset;
> -		pathp->node = slot;
> +		node = slot;
>   		slot = slot->slots[offset];
> -		shift -= RADIX_TREE_MAP_SHIFT;
> -		height--;
> -	} while (height>  0);
> +	} while (shift);
>
>   	if (slot == NULL)
>   		goto out;
>
>   	/*
> -	 * Clear all tags associated with the just-deleted item
> +	 * Clear all tags associated with the item to be deleted.
> +	 * This way of doing it would be inefficient, but seldom is any set.
>   	 */
>   	for (tag = 0; tag<  RADIX_TREE_MAX_TAGS; tag++) {
> -		if (tag_get(pathp->node, tag, pathp->offset))
> +		if (tag_get(node, tag, offset))
>   			radix_tree_tag_clear(root, index, tag);
>   	}
>
>   	to_free = NULL;
>   	/* Now free the nodes we do not need anymore */
> -	while (pathp->node) {
> -		pathp->node->slots[pathp->offset] = NULL;
> -		pathp->node->count--;
> +	while (node) {
> +		node->slots[offset] = NULL;
> +		node->count--;
>   		/*
>   		 * Queue the node for deferred freeing after the
>   		 * last reference to it disappears (set NULL, above).
> @@ -1425,17 +1414,20 @@ void *radix_tree_delete(struct radix_tre
>   		if (to_free)
>   			radix_tree_node_free(to_free);
>
> -		if (pathp->node->count) {
> -			if (pathp->node == indirect_to_ptr(root->rnode))
> +		if (node->count) {
> +			if (node == indirect_to_ptr(root->rnode))
>   				radix_tree_shrink(root);
>   			goto out;
>   		}
>
>   		/* Node with zero slots in use so free it */
> -		to_free = pathp->node;
> -		pathp--;
> +		to_free = node;
>
> +		index>>= RADIX_TREE_MAP_SHIFT;
> +		offset = index&  RADIX_TREE_MAP_MASK;
> +		node = node->parent;
>   	}
> +
>   	root_tag_clear_all(root);
>   	root->height = 0;
>   	root->rnode = NULL;
>
> --
> 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/ .
> Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
> Don't email:<a href=mailto:"dont@kvack.org">  email@kvack.org</a>

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[Nai Xia]

On Mon, Dec 19, 2011 at 4:20 PM, nai.xia <nai.xia@gmail.com> wrote:
>
>
> On 2011年12月19日 14:41, Hugh Dickins wrote:
>>
>> Down, down in the deepest depths of GFP_NOIO page reclaim, we have
>> shrink_page_list() calling __remove_mapping() calling __delete_from_
>> swap_cache() or __delete_from_page_cache().
>>
>> You would not expect those to need much stack, but in fact they call
>> radix_tree_delete(): which declares a 192-byte radix_tree_path array
>> on its stack (to record the node,offsets it visits when descending,
>> in case it needs to ascend to update them).  And if any tag is still
>> set [1], that calls radix_tree_tag_clear(), which declares a further
>> such 192-byte radix_tree_path array on the stack.  (At least we have
>> interrupts disabled here, so won't then be pushing registers too.)
>>
>> That was probably a good choice when most users were 32-bit (array
>> of half the size), and adding fields to radix_tree_node would have
>> bloated it unnecessarily.  But nowadays many are 64-bit, and each
>> radix_tree_node contains a struct rcu_head, which is only used when
>
>
> Can rcu_head in someway unionized with radix_tree_node->height
> and radix_tree_node->count? count is always referenced under lock
> and only the first node's height is referenced during lookup.
> Seems like if we atomically set root->rnode to NULL, before
> freeing the last node, we can ensure a valid read of the
> radix_tree_node->height when lookup by following it with
> a root->rnode == NULL test.
>
> I am not very sure of course, just a naive feeling.

And besides, I think maybe there were another few ways if
we really care about the stack usage of radix_tree_path,
e.g.
1. We can make radix_tree_path.offset compact to u8
which is enough to index inside a node.

2. We can use dynamic array on stack instead of
RADIX_TREE_MAX_PATH, I think for most cases
this may save half of the space

3. Take benefit of radix_tree_path array already
traveled down to clear the tags instead of calling
a radix_tree_tag_clear with full array.

I am not speaking of the negatives of your patch
, just some alternatives for your reference.

And forgive my possible selfishness, I just created a home
made radix tree traveler based on radix_tree_path array to
simulate recursive calls, not ready to its vanishing...


Thanks,

Nai

>
>
>> freeing; whereas the radix_tree_path info is only used for updating
>> the tree (deleting, clearing tags or setting tags if tagged) when a
>> lock must be held, of no interest when accessing the tree locklessly.
>>
>> So add a parent pointer to the radix_tree_node, in union with the
>> rcu_head, and remove all uses of the radix_tree_path.  There would
>> be space in that union to save the offset when descending as before
>> (we can argue that a lock must already be held to exclude other users),
>> but recalculating it when ascending is both easy (a constant shift and
>> a constant mask) and uncommon, so it seems better just to do that.
>>
>> Two little optimizations: no need to decrement height when descending,
>> adjusting shift is enough; and once radix_tree_tag_if_tagged() has set
>> tag on a node and its ancestors, it need not ascend from that node again.
>>
>> perf on the radix tree test harness reports radix_tree_insert() as 2%
>> slower (now having to set parent), but radix_tree_delete() 24% faster.
>> Surely that's an exaggeration from rtth's artificially low map shift 3,
>> but forcing it back to 6 still rates radix_tree_delete() 8% faster.
>>
>> [1] Can a pagecache tag (dirty, writeback or towrite) actually still be
>> set at the time of radix_tree_delete()?  Perhaps not if the filesystem
>> is well-behaved.  But although I've not tracked any stack overflow down
>> to this cause, I have observed a curious case in which a dirty tag is
>> set and left set on tmpfs: page migration's migrate_page_copy() happens
>> to use __set_page_dirty_nobuffers() to set PageDirty on the newpage,
>> and that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
>> filesystem which doesn't use tags, except for this stack depth issue.
>>
>> Signed-off-by: Hugh Dickins<hughd@google.com>
>> ----
>>
>>  lib/radix-tree.c |  148 +++++++++++++++++++++------------------------
>>  1 file changed, 70 insertions(+), 78 deletions(-)
>>
>> --- 3.2-rc6/lib/radix-tree.c    2011-11-07 19:24:53.342418579 -0800
>> +++ linux/lib/radix-tree.c      2011-12-16 20:40:26.152758485 -0800
>> @@ -48,16 +48,14 @@
>>  struct radix_tree_node {
>>        unsigned int    height;         /* Height from the bottom */
>>        unsigned int    count;
>> -       struct rcu_head rcu_head;
>> +       union {
>> +               struct radix_tree_node *parent; /* Used when ascending
>> tree */
>> +               struct rcu_head rcu_head;       /* Used when freeing node
>> */
>> +       };
>>        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
>>        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
>>  };
>>
>> -struct radix_tree_path {
>> -       struct radix_tree_node *node;
>> -       int offset;
>> -};
>> -
>>  #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
>>  #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
>>                                          RADIX_TREE_MAP_SHIFT))
>> @@ -256,6 +254,7 @@ static inline unsigned long radix_tree_m
>>  static int radix_tree_extend(struct radix_tree_root *root, unsigned long
>> index)
>>  {
>>        struct radix_tree_node *node;
>> +       struct radix_tree_node *slot;
>>        unsigned int height;
>>        int tag;
>>
>> @@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
>>                if (!(node = radix_tree_node_alloc(root)))
>>                        return -ENOMEM;
>>
>> -               /* Increase the height.  */
>> -               node->slots[0] = indirect_to_ptr(root->rnode);
>> -
>>                /* Propagate the aggregated tag info into the new root */
>>                for (tag = 0; tag<  RADIX_TREE_MAX_TAGS; tag++) {
>>                        if (root_tag_get(root, tag))
>>                                tag_set(node, tag, 0);
>>                }
>>
>> +               /* Increase the height.  */
>>                newheight = root->height+1;
>>                node->height = newheight;
>>                node->count = 1;
>> +               node->parent = NULL;
>> +               slot = root->rnode;
>> +               if (newheight>  1) {
>> +                       slot = indirect_to_ptr(slot);
>> +                       slot->parent = node;
>> +               }
>> +               node->slots[0] = slot;
>>                node = ptr_to_indirect(node);
>>                rcu_assign_pointer(root->rnode, node);
>>                root->height = newheight;
>> @@ -331,6 +335,7 @@ int radix_tree_insert(struct radix_tree_
>>                        if (!(slot = radix_tree_node_alloc(root)))
>>                                return -ENOMEM;
>>                        slot->height = height;
>> +                       slot->parent = node;
>>                        if (node) {
>>                                rcu_assign_pointer(node->slots[offset],
>> slot);
>>                                node->count++;
>> @@ -504,47 +509,41 @@ EXPORT_SYMBOL(radix_tree_tag_set);
>>  void *radix_tree_tag_clear(struct radix_tree_root *root,
>>                        unsigned long index, unsigned int tag)
>>  {
>> -       /*
>> -        * The radix tree path needs to be one longer than the maximum
>> path
>> -        * since the "list" is null terminated.
>> -        */
>> -       struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp =
>> path;
>> +       struct radix_tree_node *node = NULL;
>>        struct radix_tree_node *slot = NULL;
>>        unsigned int height, shift;
>> +       int uninitialized_var(offset);
>>
>>        height = root->height;
>>        if (index>  radix_tree_maxindex(height))
>>                goto out;
>>
>> -       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
>> -       pathp->node = NULL;
>> +       shift = height * RADIX_TREE_MAP_SHIFT;
>>        slot = indirect_to_ptr(root->rnode);
>>
>> -       while (height>  0) {
>> -               int offset;
>> -
>> +       while (shift) {
>>                if (slot == NULL)
>>                        goto out;
>>
>> +               shift -= RADIX_TREE_MAP_SHIFT;
>>                offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
>>
>> -               pathp[1].offset = offset;
>> -               pathp[1].node = slot;
>> +               node = slot;
>>                slot = slot->slots[offset];
>> -               pathp++;
>> -               shift -= RADIX_TREE_MAP_SHIFT;
>> -               height--;
>>        }
>>
>>        if (slot == NULL)
>>                goto out;
>>
>> -       while (pathp->node) {
>> -               if (!tag_get(pathp->node, tag, pathp->offset))
>> +       while (node) {
>> +               if (!tag_get(node, tag, offset))
>>                        goto out;
>> -               tag_clear(pathp->node, tag, pathp->offset);
>> -               if (any_tag_set(pathp->node, tag))
>> +               tag_clear(node, tag, offset);
>> +               if (any_tag_set(node, tag))
>>                        goto out;
>> -               pathp--;
>> +
>> +               index>>= RADIX_TREE_MAP_SHIFT;
>> +               offset = index&  RADIX_TREE_MAP_MASK;
>>
>> +               node = node->parent;
>>        }
>>
>>        /* clear the root's tag bit */
>> @@ -646,8 +645,7 @@ unsigned long radix_tree_range_tag_if_ta
>>                unsigned int iftag, unsigned int settag)
>>  {
>>        unsigned int height = root->height;
>> -       struct radix_tree_path path[height];
>> -       struct radix_tree_path *pathp = path;
>> +       struct radix_tree_node *node = NULL;
>>        struct radix_tree_node *slot;
>>        unsigned int shift;
>>        unsigned long tagged = 0;
>> @@ -671,14 +669,8 @@ unsigned long radix_tree_range_tag_if_ta
>>        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
>>        slot = indirect_to_ptr(root->rnode);
>>
>> -       /*
>> -        * we fill the path from (root->height - 2) to 0, leaving the
>> index at
>> -        * (root->height - 1) as a terminator. Zero the node in the
>> terminator
>> -        * so that we can use this to end walk loops back up the path.
>> -        */
>> -       path[height - 1].node = NULL;
>> -
>>        for (;;) {
>> +               unsigned long upindex;
>>                int offset;
>>
>>                offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
>>
>> @@ -686,12 +678,10 @@ unsigned long radix_tree_range_tag_if_ta
>>                        goto next;
>>                if (!tag_get(slot, iftag, offset))
>>                        goto next;
>> -               if (height>  1) {
>> +               if (shift) {
>>                        /* Go down one level */
>> -                       height--;
>>                        shift -= RADIX_TREE_MAP_SHIFT;
>> -                       path[height - 1].node = slot;
>> -                       path[height - 1].offset = offset;
>> +                       node = slot;
>>                        slot = slot->slots[offset];
>>                        continue;
>>                }
>> @@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
>>                tag_set(slot, settag, offset);
>>
>>                /* walk back up the path tagging interior nodes */
>> -               pathp =&path[0];
>>
>> -               while (pathp->node) {
>> +               upindex = index;
>> +               while (node) {
>> +                       upindex>>= RADIX_TREE_MAP_SHIFT;
>> +                       offset = upindex&  RADIX_TREE_MAP_MASK;
>>
>> +
>>                        /* stop if we find a node with the tag already set
>> */
>> -                       if (tag_get(pathp->node, settag, pathp->offset))
>> +                       if (tag_get(node, settag, offset))
>>                                break;
>> -                       tag_set(pathp->node, settag, pathp->offset);
>> -                       pathp++;
>> +                       tag_set(node, settag, offset);
>> +                       node = node->parent;
>>                }
>>
>> +               /* optimization: no need to walk up from this node again
>> */
>> +               node = NULL;
>> +
>>  next:
>>                /* Go to next item at level determined by 'shift' */
>>                index = ((index>>  shift) + 1)<<  shift;
>> @@ -724,8 +720,7 @@ next:
>>                         * last_index is guaranteed to be in the tree, what
>>                         * we do below cannot wander astray.
>>                         */
>> -                       slot = path[height - 1].node;
>> -                       height++;
>> +                       slot = slot->parent;
>>                        shift += RADIX_TREE_MAP_SHIFT;
>>                }
>>        }
>> @@ -1299,7 +1294,7 @@ static inline void radix_tree_shrink(str
>>        /* try to shrink tree height */
>>        while (root->height>  0) {
>>                struct radix_tree_node *to_free = root->rnode;
>> -               void *newptr;
>> +               struct radix_tree_node *slot;
>>
>>                BUG_ON(!radix_tree_is_indirect_ptr(to_free));
>>                to_free = indirect_to_ptr(to_free);
>> @@ -1320,10 +1315,12 @@ static inline void radix_tree_shrink(str
>>                 * (to_free->slots[0]), it will be safe to dereference the
>> new
>>                 * one (root->rnode) as far as dependent read barriers go.
>>                 */
>> -               newptr = to_free->slots[0];
>> -               if (root->height>  1)
>> -                       newptr = ptr_to_indirect(newptr);
>> -               root->rnode = newptr;
>> +               slot = to_free->slots[0];
>> +               if (root->height>  1) {
>> +                       slot->parent = NULL;
>> +                       slot = ptr_to_indirect(slot);
>> +               }
>> +               root->rnode = slot;
>>                root->height--;
>>
>>                /*
>> @@ -1363,16 +1360,12 @@ static inline void radix_tree_shrink(str
>>   */
>>  void *radix_tree_delete(struct radix_tree_root *root, unsigned long
>> index)
>>  {
>> -       /*
>> -        * The radix tree path needs to be one longer than the maximum
>> path
>> -        * since the "list" is null terminated.
>> -        */
>> -       struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp =
>> path;
>> +       struct radix_tree_node *node = NULL;
>>        struct radix_tree_node *slot = NULL;
>>        struct radix_tree_node *to_free;
>>        unsigned int height, shift;
>>        int tag;
>> -       int offset;
>> +       int uninitialized_var(offset);
>>
>>        height = root->height;
>>        if (index>  radix_tree_maxindex(height))
>> @@ -1385,39 +1378,35 @@ void *radix_tree_delete(struct radix_tre
>>                goto out;
>>        }
>>        slot = indirect_to_ptr(slot);
>> -
>> -       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
>> -       pathp->node = NULL;
>> +       shift = height * RADIX_TREE_MAP_SHIFT;
>>
>>        do {
>>                if (slot == NULL)
>>                        goto out;
>>
>> -               pathp++;
>> +               shift -= RADIX_TREE_MAP_SHIFT;
>>                offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
>>
>> -               pathp->offset = offset;
>> -               pathp->node = slot;
>> +               node = slot;
>>                slot = slot->slots[offset];
>> -               shift -= RADIX_TREE_MAP_SHIFT;
>> -               height--;
>> -       } while (height>  0);
>> +       } while (shift);
>>
>>        if (slot == NULL)
>>                goto out;
>>
>>        /*
>> -        * Clear all tags associated with the just-deleted item
>> +        * Clear all tags associated with the item to be deleted.
>> +        * This way of doing it would be inefficient, but seldom is any
>> set.
>>         */
>>        for (tag = 0; tag<  RADIX_TREE_MAX_TAGS; tag++) {
>> -               if (tag_get(pathp->node, tag, pathp->offset))
>> +               if (tag_get(node, tag, offset))
>>                        radix_tree_tag_clear(root, index, tag);
>>        }
>>
>>        to_free = NULL;
>>        /* Now free the nodes we do not need anymore */
>> -       while (pathp->node) {
>> -               pathp->node->slots[pathp->offset] = NULL;
>> -               pathp->node->count--;
>> +       while (node) {
>> +               node->slots[offset] = NULL;
>> +               node->count--;
>>                /*
>>                 * Queue the node for deferred freeing after the
>>                 * last reference to it disappears (set NULL, above).
>> @@ -1425,17 +1414,20 @@ void *radix_tree_delete(struct radix_tre
>>                if (to_free)
>>                        radix_tree_node_free(to_free);
>>
>> -               if (pathp->node->count) {
>> -                       if (pathp->node == indirect_to_ptr(root->rnode))
>> +               if (node->count) {
>> +                       if (node == indirect_to_ptr(root->rnode))
>>                                radix_tree_shrink(root);
>>                        goto out;
>>                }
>>
>>                /* Node with zero slots in use so free it */
>> -               to_free = pathp->node;
>> -               pathp--;
>> +               to_free = node;
>>
>> +               index>>= RADIX_TREE_MAP_SHIFT;
>> +               offset = index&  RADIX_TREE_MAP_MASK;
>>
>> +               node = node->parent;
>>        }
>> +
>>        root_tag_clear_all(root);
>>        root->height = 0;
>>        root->rnode = NULL;
>>
>> --
>> 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/ .
>> Fight unfair telecom internet charges in Canada: sign
>> http://stopthemeter.ca/
>> Don't email:<a href=mailto:"dont@kvack.org">  email@kvack.org</a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[Hugh Dickins]

On Mon, 19 Dec 2011, Nai Xia wrote:
> On Mon, Dec 19, 2011 at 4:20 PM, nai.xia <nai.xia@gmail.com> wrote:
> >
> > Can rcu_head in someway unionized with radix_tree_node->height
> > and radix_tree_node->count? count is always referenced under lock
> > and only the first node's height is referenced during lookup.
> > Seems like if we atomically set root->rnode to NULL, before
> > freeing the last node, we can ensure a valid read of the
> > radix_tree_node->height when lookup by following it with
> > a root->rnode == NULL test.
> >
> > I am not very sure of course, just a naive feeling.

I think you are right about radix_tree_node->count (only used under
lock, of no interest when lockless), but I'm not so sure about
radix_tree_node->height.

If you're right, then radix_tree_node->height shouldn't be needed
at all, we could work from radix_tree_root->height throughout.
And many places do so, but lockless (rcu locked) ones are relying
on radix_tree_node->height.

Caution tells me that it's intimately a part of the way we can
safely look up locklessly while the tree is being expanded or shrunk:
notice how a node never changes its height.  But perhaps it could be
reduced to a flag bit, saying whether node is a leafnode or not.

But I wouldn't risk making any such change without spending time to
think it through, time I must spend on other tasks now.  Please play
with it yourself if you've a mind to.

> 
> And besides, I think maybe there were another few ways if
> we really care about the stack usage of radix_tree_path,
> e.g.
> 1. We can make radix_tree_path.offset compact to u8
> which is enough to index inside a node.

Well, I could have halved the usage with a patch just recalculating
the offset when ascending; but I'd rather get rid of the whole array.

> 
> 2. We can use dynamic array on stack instead of
> RADIX_TREE_MAX_PATH, I think for most cases
> this may save half of the space

tag_if_tagged() was using a dynamic array on stack: that came as a
surprise to me, we usually forbid that in kernel.  It becomes hard
to estimate stack usage, so may cause nasty surprises in rare cases.

> 
> 3. Take benefit of radix_tree_path array already
> traveled down to clear the tags instead of calling
> a radix_tree_tag_clear with full array.

There must be a more efficient way of doing that, yes; but it's such a
very rare path that it's not worth extra code, I just added the comment
"This way of doing it would be inefficient, but seldom is any set".

> 
> I am not speaking of the negatives of your patch
> , just some alternatives for your reference.
> 
> And forgive my possible selfishness, I just created a home
> made radix tree traveler based on radix_tree_path array to
> simulate recursive calls, not ready to its vanishing...

I did remove
struct radix_tree_path {
	struct radix_tree_node *node;
	int offset;
};
but it's easy enough for you to add back if you have good use for it.

Hugh

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[Dave Chinner]

On Sun, Dec 18, 2011 at 10:41:39PM -0800, Hugh Dickins wrote:
> Down, down in the deepest depths of GFP_NOIO page reclaim, we have
> shrink_page_list() calling __remove_mapping() calling __delete_from_
> swap_cache() or __delete_from_page_cache().
> 
> You would not expect those to need much stack, but in fact they call
> radix_tree_delete(): which declares a 192-byte radix_tree_path array
> on its stack (to record the node,offsets it visits when descending,
> in case it needs to ascend to update them).  And if any tag is still
> set [1], that calls radix_tree_tag_clear(), which declares a further
> such 192-byte radix_tree_path array on the stack.  (At least we have
> interrupts disabled here, so won't then be pushing registers too.)
> 
> That was probably a good choice when most users were 32-bit (array
> of half the size), and adding fields to radix_tree_node would have
> bloated it unnecessarily.  But nowadays many are 64-bit, and each
> radix_tree_node contains a struct rcu_head, which is only used when
> freeing; whereas the radix_tree_path info is only used for updating
> the tree (deleting, clearing tags or setting tags if tagged) when a
> lock must be held, of no interest when accessing the tree locklessly.
> 
> So add a parent pointer to the radix_tree_node, in union with the
> rcu_head, and remove all uses of the radix_tree_path.  There would
> be space in that union to save the offset when descending as before
> (we can argue that a lock must already be held to exclude other users),
> but recalculating it when ascending is both easy (a constant shift and
> a constant mask) and uncommon, so it seems better just to do that.

Seems sane - any modification of the tree contents or tag has to be
done under a lock, so we can maintain parent pointers safely. And we
don't reda them under RCU conditions, so we don't need any special
handling there, either.

> Two little optimizations: no need to decrement height when descending,
> adjusting shift is enough;

*nod*

> and once radix_tree_tag_if_tagged() has set
> tag on a node and its ancestors, it need not ascend from that node again.

I'm not sure I really follow this. I think I know what you mean, but
I can't quite get it straight and the comment in the code doesn't
help me get it straight. Can you describe it a bit more - I think
I'm just being dense at the moment....

> perf on the radix tree test harness reports radix_tree_insert() as 2%
> slower (now having to set parent), but radix_tree_delete() 24% faster.
> Surely that's an exaggeration from rtth's artificially low map shift 3,
> but forcing it back to 6 still rates radix_tree_delete() 8% faster.

Nice.

> [1] Can a pagecache tag (dirty, writeback or towrite) actually still be
> set at the time of radix_tree_delete()?  Perhaps not if the filesystem
> is well-behaved.  But although I've not tracked any stack overflow down
> to this cause, I have observed a curious case in which a dirty tag is
> set and left set on tmpfs: page migration's migrate_page_copy() happens
> to use __set_page_dirty_nobuffers() to set PageDirty on the newpage,
> and that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
> filesystem which doesn't use tags, except for this stack depth issue.

Not sure about the page cache, but other users of the radix tree
definitely do delete objects with tags still set. For example, when
XFS is reclaiming inodes it will delete the inode from it's internal
radix trees with the reclaim tag still set on the index. This
happens for every single inode that is reclaimed, so it's anything
but seldom and should really be considered a common operation....

Couple more comments below.

> @@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
>  		if (!(node = radix_tree_node_alloc(root)))
>  			return -ENOMEM;
>  
> -		/* Increase the height.  */
> -		node->slots[0] = indirect_to_ptr(root->rnode);
> -
>  		/* Propagate the aggregated tag info into the new root */
>  		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
>  			if (root_tag_get(root, tag))
>  				tag_set(node, tag, 0);
>  		}
>  
> +		/* Increase the height.  */
>  		newheight = root->height+1;

While touching this code, fixing the adjacent whitespace damage
would be good.

>  		node->height = newheight;
>  		node->count = 1;
> +		node->parent = NULL;
> +		slot = root->rnode;
> +		if (newheight > 1) {
> +			slot = indirect_to_ptr(slot);
> +			slot->parent = node;
> +		}
> +		node->slots[0] = slot;

This would be much more obvious in function if it separated the two
different cases completely:

		if (newheight > 1) {
			slot = indirect_to_ptr(root->rnode);
			slot->parent = node;
		} else {
			slot = root->rnode;
			node->parent = NULL;
		}
		node->slots[0] = slot;

> @@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
>  		tag_set(slot, settag, offset);
>  
>  		/* walk back up the path tagging interior nodes */
> -		pathp = &path[0];
> -		while (pathp->node) {
> +		upindex = index;
> +		while (node) {
> +			upindex >>= RADIX_TREE_MAP_SHIFT;
> +			offset = upindex & RADIX_TREE_MAP_MASK;
> +
>  			/* stop if we find a node with the tag already set */
> -			if (tag_get(pathp->node, settag, pathp->offset))
> +			if (tag_get(node, settag, offset))
>  				break;
> -			tag_set(pathp->node, settag, pathp->offset);
> -			pathp++;
> +			tag_set(node, settag, offset);
> +			node = node->parent;
>  		}
>  
> +		/* optimization: no need to walk up from this node again */
> +		node = NULL;

As per my query above: why? That's the question the comment needs to
answer....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[Hugh Dickins]

On Wed, 21 Dec 2011, Dave Chinner wrote:
> On Sun, Dec 18, 2011 at 10:41:39PM -0800, Hugh Dickins wrote:
> 
> > and once radix_tree_tag_if_tagged() has set
> > tag on a node and its ancestors, it need not ascend from that node again.
> 
> I'm not sure I really follow this. I think I know what you mean, but
> I can't quite get it straight and the comment in the code doesn't
> help me get it straight. Can you describe it a bit more - I think
> I'm just being dense at the moment....

Below...

> 
> Not sure about the page cache, but other users of the radix tree
> definitely do delete objects with tags still set. For example, when
> XFS is reclaiming inodes it will delete the inode from it's internal
> radix trees with the reclaim tag still set on the index. This
> happens for every single inode that is reclaimed, so it's anything
> but seldom and should really be considered a common operation....

Thanks for that info: it was the pagecache case's deep stack that
was worrying me, and I'm only dimly aware of its other uses.

> 
> Couple more comments below.
> 
> > @@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
> >  		if (!(node = radix_tree_node_alloc(root)))
> >  			return -ENOMEM;
> >  
> > -		/* Increase the height.  */
> > -		node->slots[0] = indirect_to_ptr(root->rnode);
> > -
> >  		/* Propagate the aggregated tag info into the new root */
> >  		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
> >  			if (root_tag_get(root, tag))
> >  				tag_set(node, tag, 0);
> >  		}
> >  
> > +		/* Increase the height.  */
> >  		newheight = root->height+1;
> 
> While touching this code, fixing the adjacent whitespace damage
> would be good.

I didn't notice any: do you mean "root->height+1" instead of
"root->height + 1"?  I don't care much, and checkpatch didn't complain.

> 
> >  		node->height = newheight;
> >  		node->count = 1;
> > +		node->parent = NULL;
> > +		slot = root->rnode;
> > +		if (newheight > 1) {
> > +			slot = indirect_to_ptr(slot);
> > +			slot->parent = node;
> > +		}
> > +		node->slots[0] = slot;
> 
> This would be much more obvious in function if it separated the two
> different cases completely:
> 
> 		if (newheight > 1) {
> 			slot = indirect_to_ptr(root->rnode);
> 			slot->parent = node;
> 		} else {
> 			slot = root->rnode;
> 			node->parent = NULL;
> 		}
> 		node->slots[0] = slot;

We do need to set node->parent NULL in all cases (and cannot clear
it when freeing).  I chose the "slot = blah(slot)" style to follow the
"newptr = blah(newptr)" over in radix_tree_shrink(), thought it helped
to keep those blocks alike.

> 
> > @@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
> >  		tag_set(slot, settag, offset);
> >  
> >  		/* walk back up the path tagging interior nodes */
> > -		pathp = &path[0];
> > -		while (pathp->node) {
> > +		upindex = index;
> > +		while (node) {
> > +			upindex >>= RADIX_TREE_MAP_SHIFT;
> > +			offset = upindex & RADIX_TREE_MAP_MASK;
> > +
> >  			/* stop if we find a node with the tag already set */
> > -			if (tag_get(pathp->node, settag, pathp->offset))
> > +			if (tag_get(node, settag, offset))
> >  				break;
> > -			tag_set(pathp->node, settag, pathp->offset);
> > -			pathp++;
> > +			tag_set(node, settag, offset);
> > +			node = node->parent;
> >  		}
> >  
> > +		/* optimization: no need to walk up from this node again */
> > +		node = NULL;
> 
> As per my query above: why? That's the question the comment needs to
> answer....

At the top of the hunk, we can see the tag_set(slot, settag, offset)
where it sets the tag in the leafnode "slot"; then it loops up to parent
"node" of slot, to parent of parent, etc, setting tag in those, but
breaking as soon as it finds the tag already set - it can be sure that
the tag must already be set on all nodes above.

If afterwards it comes to set tag at another offset (most likely the
very next) in this same leafnode, we know that it has already set tag
on the parent, the parent's parent etc., so need not bother to tag_get
from the level above to discover that.  And since we happen to have a
variable "node" which stops the loop when it's NULL, let's set it to
NULL now to stop the loop immediately in future.

Hugh

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[Dave Chinner]

On Tue, Dec 20, 2011 at 10:53:17PM -0800, Hugh Dickins wrote:
> On Wed, 21 Dec 2011, Dave Chinner wrote:
> > On Sun, Dec 18, 2011 at 10:41:39PM -0800, Hugh Dickins wrote:
.....
> > >  		if (!(node = radix_tree_node_alloc(root)))
> > >  			return -ENOMEM;
> > >  
> > > -		/* Increase the height.  */
> > > -		node->slots[0] = indirect_to_ptr(root->rnode);
> > > -
> > >  		/* Propagate the aggregated tag info into the new root */
> > >  		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
> > >  			if (root_tag_get(root, tag))
> > >  				tag_set(node, tag, 0);
> > >  		}
> > >  
> > > +		/* Increase the height.  */
> > >  		newheight = root->height+1;
> > 
> > While touching this code, fixing the adjacent whitespace damage
> > would be good.
> 
> I didn't notice any: do you mean "root->height+1" instead of
> "root->height + 1"?  I don't care much, and checkpatch didn't complain.

Yeah, that was what I was refering to.

> > >  		node->height = newheight;
> > >  		node->count = 1;
> > > +		node->parent = NULL;
> > > +		slot = root->rnode;
> > > +		if (newheight > 1) {
> > > +			slot = indirect_to_ptr(slot);
> > > +			slot->parent = node;
> > > +		}
> > > +		node->slots[0] = slot;
> > 
> > This would be much more obvious in function if it separated the two
> > different cases completely:
> > 
> > 		if (newheight > 1) {
> > 			slot = indirect_to_ptr(root->rnode);
> > 			slot->parent = node;
> > 		} else {
> > 			slot = root->rnode;
> > 			node->parent = NULL;
> > 		}
> > 		node->slots[0] = slot;
> 
> We do need to set node->parent NULL in all cases (and cannot clear
> it when freeing).  I chose the "slot = blah(slot)" style to follow the
> "newptr = blah(newptr)" over in radix_tree_shrink(), thought it helped
> to keep those blocks alike.

You're right. I really was being dense yesterday. To tell the truth,
though, I found the "newptr" style easier to follow because it was
obvious which was the object being initialised. I think that it not
being obvious which object needed full initialisation contribted to
my mix up of node and slot parent pointers in my above comment...

> > > @@ -701,15 +691,21 @@ unsigned long radix_tree_range_tag_if_ta
> > >  		tag_set(slot, settag, offset);
> > >  
> > >  		/* walk back up the path tagging interior nodes */
> > > -		pathp = &path[0];
> > > -		while (pathp->node) {
> > > +		upindex = index;
> > > +		while (node) {
> > > +			upindex >>= RADIX_TREE_MAP_SHIFT;
> > > +			offset = upindex & RADIX_TREE_MAP_MASK;
> > > +
> > >  			/* stop if we find a node with the tag already set */
> > > -			if (tag_get(pathp->node, settag, pathp->offset))
> > > +			if (tag_get(node, settag, offset))
> > >  				break;
> > > -			tag_set(pathp->node, settag, pathp->offset);
> > > -			pathp++;
> > > +			tag_set(node, settag, offset);
> > > +			node = node->parent;
> > >  		}
> > >  
> > > +		/* optimization: no need to walk up from this node again */
> > > +		node = NULL;
> > 
> > As per my query above: why? That's the question the comment needs to
> > answer....
> 
> At the top of the hunk, we can see the tag_set(slot, settag, offset)
> where it sets the tag in the leafnode "slot"; then it loops up to parent
> "node" of slot, to parent of parent, etc, setting tag in those, but
> breaking as soon as it finds the tag already set - it can be sure that
> the tag must already be set on all nodes above.
> 
> If afterwards it comes to set tag at another offset (most likely the
> very next) in this same leafnode, we know that it has already set tag
> on the parent, the parent's parent etc., so need not bother to tag_get
> from the level above to discover that.  And since we happen to have a
> variable "node" which stops the loop when it's NULL, let's set it to
> NULL now to stop the loop immediately in future.

Ok, gotcha. perhaps a more expansive comment along the lines of:

/*
 * we can clear the node pointer now as all it's ancestors have the
 * tage set due to setting it on the slot above. Hence we have no
 * need to walk back up the tree to set tags if there is no further
 * tags to set.
 */

is in order to remind me in a few months time why it this was done?

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: take radix_tree_path off stack

[Hugh Dickins]

On Thu, 22 Dec 2011, Dave Chinner wrote:
> On Tue, Dec 20, 2011 at 10:53:17PM -0800, Hugh Dickins wrote:
> > On Wed, 21 Dec 2011, Dave Chinner wrote:
> > 
> > We do need to set node->parent NULL in all cases (and cannot clear
> > it when freeing).  I chose the "slot = blah(slot)" style to follow the
> > "newptr = blah(newptr)" over in radix_tree_shrink(), thought it helped
> > to keep those blocks alike.
> 
> You're right. I really was being dense yesterday. To tell the truth,
> though, I found the "newptr" style easier to follow because it was
> obvious which was the object being initialised. I think that it not
> being obvious which object needed full initialisation contribted to
> my mix up of node and slot parent pointers in my above comment...

Yes, I too get confused between parent and child and node and slot,
slot being a node which contains an array of slots.  I did experiment
with saying "parent" instead of "node" in several of the places touched,
or "child" instead of "slot", but didn't end up with anything that
satisfied me very much; so stuck with the bland node and slot.

> > At the top of the hunk, we can see the tag_set(slot, settag, offset)
> > where it sets the tag in the leafnode "slot"; then it loops up to parent
> > "node" of slot, to parent of parent, etc, setting tag in those, but
> > breaking as soon as it finds the tag already set - it can be sure that
> > the tag must already be set on all nodes above.
> > 
> > If afterwards it comes to set tag at another offset (most likely the
> > very next) in this same leafnode, we know that it has already set tag
> > on the parent, the parent's parent etc., so need not bother to tag_get
> > from the level above to discover that.  And since we happen to have a
> > variable "node" which stops the loop when it's NULL, let's set it to
> > NULL now to stop the loop immediately in future.
> 
> Ok, gotcha. perhaps a more expansive comment along the lines of:
> 
> /*
>  * we can clear the node pointer now as all it's ancestors have the
>  * tage set due to setting it on the slot above. Hence we have no
>  * need to walk back up the tree to set tags if there is no further
>  * tags to set.
>  */
> 
> is in order to remind me in a few months time why it this was done?

I've plagiarized your wording, but changed it enough that I cannot
honestly cite you as the Author.  Incremental patch to akpm follows
in a moment.

Hugh

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH] radix_tree: expand comment on optimization

[Hugh Dickins]

Expand comment on optimization in radix_tree_range_tag_if_tagged(),
along the lines proposed by Dave Chinner.

Signed-off-by: Hugh Dickins <hughd@google.com>
---
And with -p2, this patch will also apply to the rtth tree.

 lib/radix-tree.c |    8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

--- mmotm/lib/radix-tree.c	2011-12-16 20:40:26.152758485 -0800
+++ linux/lib/radix-tree.c	2011-12-21 14:57:20.073657540 -0800
@@ -703,7 +703,13 @@ unsigned long radix_tree_range_tag_if_ta
 			node = node->parent;
 		}
 
-		/* optimization: no need to walk up from this node again */
+		/*
+		 * Small optimization: now clear that node pointer.
+		 * Since all of this slot's ancestors now have the tag set
+		 * from setting it above, we have no further need to walk
+		 * back up the tree setting tags, until we update slot to
+		 * point to another radix_tree_node.
+		 */
 		node = NULL;
 
 next:

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: expand comment on optimization

[Dave Chinner]

On Wed, Dec 21, 2011 at 03:57:16PM -0800, Hugh Dickins wrote:
> Expand comment on optimization in radix_tree_range_tag_if_tagged(),
> along the lines proposed by Dave Chinner.
> 
> Signed-off-by: Hugh Dickins <hughd@google.com>
> ---
> And with -p2, this patch will also apply to the rtth tree.
> 
>  lib/radix-tree.c |    8 +++++++-
>  1 file changed, 7 insertions(+), 1 deletion(-)
> 
> --- mmotm/lib/radix-tree.c	2011-12-16 20:40:26.152758485 -0800
> +++ linux/lib/radix-tree.c	2011-12-21 14:57:20.073657540 -0800
> @@ -703,7 +703,13 @@ unsigned long radix_tree_range_tag_if_ta
>  			node = node->parent;
>  		}
>  
> -		/* optimization: no need to walk up from this node again */
> +		/*
> +		 * Small optimization: now clear that node pointer.
> +		 * Since all of this slot's ancestors now have the tag set
> +		 * from setting it above, we have no further need to walk
> +		 * back up the tree setting tags, until we update slot to
> +		 * point to another radix_tree_node.
> +		 */
>  		node = NULL;

Looks good. I might remember why it was done now ;)

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH] radix_tree: delete orphaned macro radix_tree_indirect_to_ptr

[nai.xia]

Seems nobody has been using the macro radix_tree_indirect_to_ptr()
since long time ago. Delete it.

Signed-off-by: Nai Xia <nai.xia@gmail.com>
---
  include/linux/radix-tree.h |    3 ---
  1 files changed, 0 insertions(+), 3 deletions(-)

--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -49,9 +49,6 @@
  #define RADIX_TREE_EXCEPTIONAL_ENTRY	2
  #define RADIX_TREE_EXCEPTIONAL_SHIFT	2

-#define radix_tree_indirect_to_ptr(ptr) \
-	radix_tree_indirect_to_ptr((void __force *)(ptr))
-
  static inline int radix_tree_is_indirect_ptr(void *ptr)
  {
  	return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: delete orphaned macro radix_tree_indirect_to_ptr

[Li Zefan]

nai.xia wrote:
> Seems nobody has been using the macro radix_tree_indirect_to_ptr()
> since long time ago. Delete it.
> 

Someone else has already posted the same patch.

https://lkml.org/lkml/2011/12/16/118

> Signed-off-by: Nai Xia <nai.xia@gmail.com>
> ---
>  include/linux/radix-tree.h |    3 ---
>  1 files changed, 0 insertions(+), 3 deletions(-)
> 
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -49,9 +49,6 @@
>  #define RADIX_TREE_EXCEPTIONAL_ENTRY    2
>  #define RADIX_TREE_EXCEPTIONAL_SHIFT    2
> 
> -#define radix_tree_indirect_to_ptr(ptr) \
> -    radix_tree_indirect_to_ptr((void __force *)(ptr))
> -
>  static inline int radix_tree_is_indirect_ptr(void *ptr)
>  {
>      return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix_tree: delete orphaned macro radix_tree_indirect_to_ptr

[Nai Xia]

On Thu, Dec 22, 2011 at 11:29 AM, Li Zefan <lizf@cn.fujitsu.com> wrote:
> nai.xia wrote:
>> Seems nobody has been using the macro radix_tree_indirect_to_ptr()
>> since long time ago. Delete it.
>>
>
> Someone else has already posted the same patch.
>
> https://lkml.org/lkml/2011/12/16/118

Oh,yes!  This thread just suddenly reminds me of that long time
noop line. I should have searched recent patch submission. :)

>
>> Signed-off-by: Nai Xia <nai.xia@gmail.com>
>> ---
>>  include/linux/radix-tree.h |    3 ---
>>  1 files changed, 0 insertions(+), 3 deletions(-)
>>
>> --- a/include/linux/radix-tree.h
>> +++ b/include/linux/radix-tree.h
>> @@ -49,9 +49,6 @@
>>  #define RADIX_TREE_EXCEPTIONAL_ENTRY    2
>>  #define RADIX_TREE_EXCEPTIONAL_SHIFT    2
>>
>> -#define radix_tree_indirect_to_ptr(ptr) \
>> -    radix_tree_indirect_to_ptr((void __force *)(ptr))
>> -
>>  static inline int radix_tree_is_indirect_ptr(void *ptr)
>>  {
>>      return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
>
> --
> 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/ .
> Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>