radix_tree: take radix_tree_path off stack

PATCH In review Hugh Dickins 4 participants 13 messages Dec 19, 2011 – Dec 22, 2011

Subsystems (2)

Memory management Library code

lore

Share & tools

lore

Hugh Dickins

author

2011-12-19 06:41 UTC #0 lore raw

PATCH 1/1 radix_tree: take radix_tree_path off stack

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 <[email protected]>

----

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

lib/radix-tree.c +70 ~~-78~~

@@ -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 [email protected]. 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:"[email protected]"> [email protected] </a>

nai.xia

2011-12-19 08:20 UTC #1 lore raw

Quoted 12 lines · 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.)

Quoted 4 lines

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.

Quoted 363 lines

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.

Signed-off-by Hugh Dickins<[email protected]>

----

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

lib/radix-tree.c +70 ~~-79~~

@@ -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;
 
--

Quoted 5 lines

To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. 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:"[email protected]"> [email protected]</a>

Nai Xia

2011-12-19 09:37 UTC #2 lore raw

T24gTW9uLCBEZWMgMTksIDIwMTEgYXQgNDoyMCBQTSwgbmFpLnhpYSA8bmFpLnhpYUBnbWFpbC5j b20+IHdyb3RlOgo+Cj4KPiBPbiAyMDEx5bm0MTLmnIgxOeaXpSAxNDo0MSwgSHVnaCBEaWNraW5z IHdyb3RlOgo+Pgo+PiBEb3duLCBkb3duIGluIHRoZSBkZWVwZXN0IGRlcHRocyBvZiBHRlBfTk9J TyBwYWdlIHJlY2xhaW0sIHdlIGhhdmUKPj4gc2hyaW5rX3BhZ2VfbGlzdCgpIGNhbGxpbmcgX19y ZW1vdmVfbWFwcGluZygpIGNhbGxpbmcgX19kZWxldGVfZnJvbV8KPj4gc3dhcF9jYWNoZSgpIG9y IF9fZGVsZXRlX2Zyb21fcGFnZV9jYWNoZSgpLgo+Pgo+PiBZb3Ugd291bGQgbm90IGV4cGVjdCB0 aG9zZSB0byBuZWVkIG11Y2ggc3RhY2ssIGJ1dCBpbiBmYWN0IHRoZXkgY2FsbAo+PiByYWRpeF90 cmVlX2RlbGV0ZSgpOiB3aGljaCBkZWNsYXJlcyBhIDE5Mi1ieXRlIHJhZGl4X3RyZWVfcGF0aCBh cnJheQo+PiBvbiBpdHMgc3RhY2sgKHRvIHJlY29yZCB0aGUgbm9kZSxvZmZzZXRzIGl0IHZpc2l0 cyB3aGVuIGRlc2NlbmRpbmcsCj4+IGluIGNhc2UgaXQgbmVlZHMgdG8gYXNjZW5kIHRvIHVwZGF0 ZSB0aGVtKS4gwqBBbmQgaWYgYW55IHRhZyBpcyBzdGlsbAo+PiBzZXQgWzFdLCB0aGF0IGNhbGxz IHJhZGl4X3RyZWVfdGFnX2NsZWFyKCksIHdoaWNoIGRlY2xhcmVzIGEgZnVydGhlcgo+PiBzdWNo IDE5Mi1ieXRlIHJhZGl4X3RyZWVfcGF0aCBhcnJheSBvbiB0aGUgc3RhY2suIMKgKEF0IGxlYXN0 IHdlIGhhdmUKPj4gaW50ZXJydXB0cyBkaXNhYmxlZCBoZXJlLCBzbyB3b24ndCB0aGVuIGJlIHB1 c2hpbmcgcmVnaXN0ZXJzIHRvby4pCj4+Cj4+IFRoYXQgd2FzIHByb2JhYmx5IGEgZ29vZCBjaG9p Y2Ugd2hlbiBtb3N0IHVzZXJzIHdlcmUgMzItYml0IChhcnJheQo+PiBvZiBoYWxmIHRoZSBzaXpl KSwgYW5kIGFkZGluZyBmaWVsZHMgdG8gcmFkaXhfdHJlZV9ub2RlIHdvdWxkIGhhdmUKPj4gYmxv YXRlZCBpdCB1bm5lY2Vzc2FyaWx5LiDCoEJ1dCBub3dhZGF5cyBtYW55IGFyZSA2NC1iaXQsIGFu ZCBlYWNoCj4+IHJhZGl4X3RyZWVfbm9kZSBjb250YWlucyBhIHN0cnVjdCByY3VfaGVhZCwgd2hp Y2ggaXMgb25seSB1c2VkIHdoZW4KPgo+Cj4gQ2FuIHJjdV9oZWFkIGluIHNvbWV3YXkgdW5pb25p emVkIHdpdGggcmFkaXhfdHJlZV9ub2RlLT5oZWlnaHQKPiBhbmQgcmFkaXhfdHJlZV9ub2RlLT5j b3VudD8gY291bnQgaXMgYWx3YXlzIHJlZmVyZW5jZWQgdW5kZXIgbG9jawo+IGFuZCBvbmx5IHRo ZSBmaXJzdCBub2RlJ3MgaGVpZ2h0IGlzIHJlZmVyZW5jZWQgZHVyaW5nIGxvb2t1cC4KPiBTZWVt cyBsaWtlIGlmIHdlIGF0b21pY2FsbHkgc2V0IHJvb3QtPnJub2RlIHRvIE5VTEwsIGJlZm9yZQo+ IGZyZWVpbmcgdGhlIGxhc3Qgbm9kZSwgd2UgY2FuIGVuc3VyZSBhIHZhbGlkIHJlYWQgb2YgdGhl Cj4gcmFkaXhfdHJlZV9ub2RlLT5oZWlnaHQgd2hlbiBsb29rdXAgYnkgZm9sbG93aW5nIGl0IHdp dGgKPiBhIHJvb3QtPnJub2RlID09IE5VTEwgdGVzdC4KPgo+IEkgYW0gbm90IHZlcnkgc3VyZSBv ZiBjb3Vyc2UsIGp1c3QgYSBuYWl2ZSBmZWVsaW5nLgoKQW5kIGJlc2lkZXMsIEkgdGhpbmsgbWF5 YmUgdGhlcmUgd2VyZSBhbm90aGVyIGZldyB3YXlzIGlmCndlIHJlYWxseSBjYXJlIGFib3V0IHRo ZSBzdGFjayB1c2FnZSBvZiByYWRpeF90cmVlX3BhdGgsCmUuZy4KMS4gV2UgY2FuIG1ha2UgcmFk aXhfdHJlZV9wYXRoLm9mZnNldCBjb21wYWN0IHRvIHU4CndoaWNoIGlzIGVub3VnaCB0byBpbmRl eCBpbnNpZGUgYSBub2RlLgoKMi4gV2UgY2FuIHVzZSBkeW5hbWljIGFycmF5IG9uIHN0YWNrIGlu c3RlYWQgb2YKUkFESVhfVFJFRV9NQVhfUEFUSCwgSSB0aGluayBmb3IgbW9zdCBjYXNlcwp0aGlz IG1heSBzYXZlIGhhbGYgb2YgdGhlIHNwYWNlCgozLiBUYWtlIGJlbmVmaXQgb2YgcmFkaXhfdHJl ZV9wYXRoIGFycmF5IGFscmVhZHkKdHJhdmVsZWQgZG93biB0byBjbGVhciB0aGUgdGFncyBpbnN0 ZWFkIG9mIGNhbGxpbmcKYSByYWRpeF90cmVlX3RhZ19jbGVhciB3aXRoIGZ1bGwgYXJyYXkuCgpJ IGFtIG5vdCBzcGVha2luZyBvZiB0aGUgbmVnYXRpdmVzIG9mIHlvdXIgcGF0Y2gKLCBqdXN0IHNv bWUgYWx0ZXJuYXRpdmVzIGZvciB5b3VyIHJlZmVyZW5jZS4KCkFuZCBmb3JnaXZlIG15IHBvc3Np YmxlIHNlbGZpc2huZXNzLCBJIGp1c3QgY3JlYXRlZCBhIGhvbWUKbWFkZSByYWRpeCB0cmVlIHRy YXZlbGVyIGJhc2VkIG9uIHJhZGl4X3RyZWVfcGF0aCBhcnJheSB0bwpzaW11bGF0ZSByZWN1cnNp dmUgY2FsbHMsIG5vdCByZWFkeSB0byBpdHMgdmFuaXNoaW5nLi4uCgoKVGhhbmtzLAoKTmFpCgo+ Cj4KPj4gZnJlZWluZzsgd2hlcmVhcyB0aGUgcmFkaXhfdHJlZV9wYXRoIGluZm8gaXMgb25seSB1 c2VkIGZvciB1cGRhdGluZwo+PiB0aGUgdHJlZSAoZGVsZXRpbmcsIGNsZWFyaW5nIHRhZ3Mgb3Ig c2V0dGluZyB0YWdzIGlmIHRhZ2dlZCkgd2hlbiBhCj4+IGxvY2sgbXVzdCBiZSBoZWxkLCBvZiBu byBpbnRlcmVzdCB3aGVuIGFjY2Vzc2luZyB0aGUgdHJlZSBsb2NrbGVzc2x5Lgo+Pgo+PiBTbyBh ZGQgYSBwYXJlbnQgcG9pbnRlciB0byB0aGUgcmFkaXhfdHJlZV9ub2RlLCBpbiB1bmlvbiB3aXRo IHRoZQo+PiByY3VfaGVhZCwgYW5kIHJlbW92ZSBhbGwgdXNlcyBvZiB0aGUgcmFkaXhfdHJlZV9w YXRoLiDCoFRoZXJlIHdvdWxkCj4+IGJlIHNwYWNlIGluIHRoYXQgdW5pb24gdG8gc2F2ZSB0aGUg b2Zmc2V0IHdoZW4gZGVzY2VuZGluZyBhcyBiZWZvcmUKPj4gKHdlIGNhbiBhcmd1ZSB0aGF0IGEg bG9jayBtdXN0IGFscmVhZHkgYmUgaGVsZCB0byBleGNsdWRlIG90aGVyIHVzZXJzKSwKPj4gYnV0 IHJlY2FsY3VsYXRpbmcgaXQgd2hlbiBhc2NlbmRpbmcgaXMgYm90aCBlYXN5IChhIGNvbnN0YW50 IHNoaWZ0IGFuZAo+PiBhIGNvbnN0YW50IG1hc2spIGFuZCB1bmNvbW1vbiwgc28gaXQgc2VlbXMg YmV0dGVyIGp1c3QgdG8gZG8gdGhhdC4KPj4KPj4gVHdvIGxpdHRsZSBvcHRpbWl6YXRpb25zOiBu byBuZWVkIHRvIGRlY3JlbWVudCBoZWlnaHQgd2hlbiBkZXNjZW5kaW5nLAo+PiBhZGp1c3Rpbmcg c2hpZnQgaXMgZW5vdWdoOyBhbmQgb25jZSByYWRpeF90cmVlX3RhZ19pZl90YWdnZWQoKSBoYXMg c2V0Cj4+IHRhZyBvbiBhIG5vZGUgYW5kIGl0cyBhbmNlc3RvcnMsIGl0IG5lZWQgbm90IGFzY2Vu ZCBmcm9tIHRoYXQgbm9kZSBhZ2Fpbi4KPj4KPj4gcGVyZiBvbiB0aGUgcmFkaXggdHJlZSB0ZXN0 IGhhcm5lc3MgcmVwb3J0cyByYWRpeF90cmVlX2luc2VydCgpIGFzIDIlCj4+IHNsb3dlciAobm93 IGhhdmluZyB0byBzZXQgcGFyZW50KSwgYnV0IHJhZGl4X3RyZWVfZGVsZXRlKCkgMjQlIGZhc3Rl ci4KPj4gU3VyZWx5IHRoYXQncyBhbiBleGFnZ2VyYXRpb24gZnJvbSBydHRoJ3MgYXJ0aWZpY2lh bGx5IGxvdyBtYXAgc2hpZnQgMywKPj4gYnV0IGZvcmNpbmcgaXQgYmFjayB0byA2IHN0aWxsIHJh dGVzIHJhZGl4X3RyZWVfZGVsZXRlKCkgOCUgZmFzdGVyLgo+Pgo+PiBbMV0gQ2FuIGEgcGFnZWNh Y2hlIHRhZyAoZGlydHksIHdyaXRlYmFjayBvciB0b3dyaXRlKSBhY3R1YWxseSBzdGlsbCBiZQo+ PiBzZXQgYXQgdGhlIHRpbWUgb2YgcmFkaXhfdHJlZV9kZWxldGUoKT8gwqBQZXJoYXBzIG5vdCBp ZiB0aGUgZmlsZXN5c3RlbQo+PiBpcyB3ZWxsLWJlaGF2ZWQuIMKgQnV0IGFsdGhvdWdoIEkndmUg bm90IHRyYWNrZWQgYW55IHN0YWNrIG92ZXJmbG93IGRvd24KPj4gdG8gdGhpcyBjYXVzZSwgSSBo YXZlIG9ic2VydmVkIGEgY3VyaW91cyBjYXNlIGluIHdoaWNoIGEgZGlydHkgdGFnIGlzCj4+IHNl dCBhbmQgbGVmdCBzZXQgb24gdG1wZnM6IHBhZ2UgbWlncmF0aW9uJ3MgbWlncmF0ZV9wYWdlX2Nv cHkoKSBoYXBwZW5zCj4+IHRvIHVzZSBfX3NldF9wYWdlX2RpcnR5X25vYnVmZmVycygpIHRvIHNl dCBQYWdlRGlydHkgb24gdGhlIG5ld3BhZ2UsCj4+IGFuZCB0aGF0IHNldHMgUEFHRUNBQ0hFX1RB R19ESVJUWSBhcyBhIHNpZGUtZWZmZWN0IC0gaGFybWxlc3MgdG8gYQo+PiBmaWxlc3lzdGVtIHdo aWNoIGRvZXNuJ3QgdXNlIHRhZ3MsIGV4Y2VwdCBmb3IgdGhpcyBzdGFjayBkZXB0aCBpc3N1ZS4K Pj4KPj4gU2lnbmVkLW9mZi1ieTogSHVnaCBEaWNraW5zPGh1Z2hkQGdvb2dsZS5jb20+Cj4+IC0t LS0KPj4KPj4gwqBsaWIvcmFkaXgtdHJlZS5jIHwgwqAxNDggKysrKysrKysrKysrKysrKysrKysr LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCj4+IMKgMSBmaWxlIGNoYW5nZWQsIDcwIGluc2VydGlv bnMoKyksIDc4IGRlbGV0aW9ucygtKQo+Pgo+PiAtLS0gMy4yLXJjNi9saWIvcmFkaXgtdHJlZS5j IMKgIMKgMjAxMS0xMS0wNyAxOToyNDo1My4zNDI0MTg1NzkgLTA4MDAKPj4gKysrIGxpbnV4L2xp Yi9yYWRpeC10cmVlLmMgwqAgwqAgwqAyMDExLTEyLTE2IDIwOjQwOjI2LjE1Mjc1ODQ4NSAtMDgw MAo+PiBAQCAtNDgsMTYgKzQ4LDE0IEBACj4+IMKgc3RydWN0IHJhZGl4X3RyZWVfbm9kZSB7Cj4+ IMKgIMKgIMKgIMKgdW5zaWduZWQgaW50IMKgIMKgaGVpZ2h0OyDCoCDCoCDCoCDCoCAvKiBIZWln aHQgZnJvbSB0aGUgYm90dG9tICovCj4+IMKgIMKgIMKgIMKgdW5zaWduZWQgaW50IMKgIMKgY291 bnQ7Cj4+IC0gwqAgwqAgwqAgc3RydWN0IHJjdV9oZWFkIHJjdV9oZWFkOwo+PiArIMKgIMKgIMKg IHVuaW9uIHsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCBzdHJ1Y3QgcmFkaXhfdHJlZV9ub2Rl ICpwYXJlbnQ7IC8qIFVzZWQgd2hlbiBhc2NlbmRpbmcKPj4gdHJlZSAqLwo+PiArIMKgIMKgIMKg IMKgIMKgIMKgIMKgIHN0cnVjdCByY3VfaGVhZCByY3VfaGVhZDsgwqAgwqAgwqAgLyogVXNlZCB3 aGVuIGZyZWVpbmcgbm9kZQo+PiAqLwo+PiArIMKgIMKgIMKgIH07Cj4+IMKgIMKgIMKgIMKgdm9p ZCBfX3JjdSDCoCDCoCDCoCpzbG90c1tSQURJWF9UUkVFX01BUF9TSVpFXTsKPj4gwqAgwqAgwqAg wqB1bnNpZ25lZCBsb25nIMKgIHRhZ3NbUkFESVhfVFJFRV9NQVhfVEFHU11bUkFESVhfVFJFRV9U QUdfTE9OR1NdOwo+PiDCoH07Cj4+Cj4+IC1zdHJ1Y3QgcmFkaXhfdHJlZV9wYXRoIHsKPj4gLSDC oCDCoCDCoCBzdHJ1Y3QgcmFkaXhfdHJlZV9ub2RlICpub2RlOwo+PiAtIMKgIMKgIMKgIGludCBv ZmZzZXQ7Cj4+IC19Owo+PiAtCj4+IMKgI2RlZmluZSBSQURJWF9UUkVFX0lOREVYX0JJVFMgwqAo OCAvKiBDSEFSX0JJVCAqLyAqIHNpemVvZih1bnNpZ25lZCBsb25nKSkKPj4gwqAjZGVmaW5lIFJB RElYX1RSRUVfTUFYX1BBVEggKERJVl9ST1VORF9VUChSQURJWF9UUkVFX0lOREVYX0JJVFMsIFwK Pj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqBSQURJWF9UUkVFX01BUF9TSElGVCkpCj4+IEBAIC0yNTYsNiArMjU0LDcgQEAgc3Rh dGljIGlubGluZSB1bnNpZ25lZCBsb25nIHJhZGl4X3RyZWVfbQo+PiDCoHN0YXRpYyBpbnQgcmFk aXhfdHJlZV9leHRlbmQoc3RydWN0IHJhZGl4X3RyZWVfcm9vdCAqcm9vdCwgdW5zaWduZWQgbG9u Zwo+PiBpbmRleCkKPj4gwqB7Cj4+IMKgIMKgIMKgIMKgc3RydWN0IHJhZGl4X3RyZWVfbm9kZSAq bm9kZTsKPj4gKyDCoCDCoCDCoCBzdHJ1Y3QgcmFkaXhfdHJlZV9ub2RlICpzbG90Owo+PiDCoCDC oCDCoCDCoHVuc2lnbmVkIGludCBoZWlnaHQ7Cj4+IMKgIMKgIMKgIMKgaW50IHRhZzsKPj4KPj4g QEAgLTI3NCwxOCArMjczLDIzIEBAIHN0YXRpYyBpbnQgcmFkaXhfdHJlZV9leHRlbmQoc3RydWN0 IHJhZGkKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBpZiAoIShub2RlID0gcmFkaXhfdHJlZV9u b2RlX2FsbG9jKHJvb3QpKSkKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBy ZXR1cm4gLUVOT01FTTsKPj4KPj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCAvKiBJbmNyZWFzZSB0 aGUgaGVpZ2h0LiDCoCovCj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgbm9kZS0+c2xvdHNbMF0g PSBpbmRpcmVjdF90b19wdHIocm9vdC0+cm5vZGUpOwo+PiAtCj4+IMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgLyogUHJvcGFnYXRlIHRoZSBhZ2dyZWdhdGVkIHRhZyBpbmZvIGludG8gdGhlIG5ldyBy b290ICovCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgZm9yICh0YWcgPSAwOyB0YWc8IMKgUkFE SVhfVFJFRV9NQVhfVEFHUzsgdGFnKyspIHsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqBpZiAocm9vdF90YWdfZ2V0KHJvb3QsIHRhZykpCj4+IMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgdGFnX3NldChub2RlLCB0YWcsIDApOwo+PiDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoH0KPj4KPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCAvKiBJ bmNyZWFzZSB0aGUgaGVpZ2h0LiDCoCovCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgbmV3aGVp Z2h0ID0gcm9vdC0+aGVpZ2h0KzE7Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgbm9kZS0+aGVp Z2h0ID0gbmV3aGVpZ2h0Owo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoG5vZGUtPmNvdW50ID0g MTsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCBub2RlLT5wYXJlbnQgPSBOVUxMOwo+PiArIMKg IMKgIMKgIMKgIMKgIMKgIMKgIHNsb3QgPSByb290LT5ybm9kZTsKPj4gKyDCoCDCoCDCoCDCoCDC oCDCoCDCoCBpZiAobmV3aGVpZ2h0PiDCoDEpIHsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCBzbG90ID0gaW5kaXJlY3RfdG9fcHRyKHNsb3QpOwo+PiArIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIHNsb3QtPnBhcmVudCA9IG5vZGU7Cj4+ICsgwqAgwqAgwqAg wqAgwqAgwqAgwqAgfQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIG5vZGUtPnNsb3RzWzBdID0g c2xvdDsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBub2RlID0gcHRyX3RvX2luZGlyZWN0KG5v ZGUpOwo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoHJjdV9hc3NpZ25fcG9pbnRlcihyb290LT5y bm9kZSwgbm9kZSk7Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgcm9vdC0+aGVpZ2h0ID0gbmV3 aGVpZ2h0Owo+PiBAQCAtMzMxLDYgKzMzNSw3IEBAIGludCByYWRpeF90cmVlX2luc2VydChzdHJ1 Y3QgcmFkaXhfdHJlZV8KPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBpZiAo IShzbG90ID0gcmFkaXhfdHJlZV9ub2RlX2FsbG9jKHJvb3QpKSkKPj4gwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqByZXR1cm4gLUVOT01FTTsKPj4gwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBzbG90LT5oZWlnaHQgPSBoZWlnaHQ7Cj4+ICsg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgc2xvdC0+cGFyZW50ID0gbm9kZTsKPj4g wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBpZiAobm9kZSkgewo+PiDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoHJjdV9hc3NpZ25fcG9pbnRl cihub2RlLT5zbG90c1tvZmZzZXRdLAo+PiBzbG90KTsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBub2RlLT5jb3VudCsrOwo+PiBAQCAtNTA0LDQ3ICs1 MDksNDEgQEAgRVhQT1JUX1NZTUJPTChyYWRpeF90cmVlX3RhZ19zZXQpOwo+PiDCoHZvaWQgKnJh ZGl4X3RyZWVfdGFnX2NsZWFyKHN0cnVjdCByYWRpeF90cmVlX3Jvb3QgKnJvb3QsCj4+IMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgdW5zaWduZWQgbG9uZyBpbmRleCwgdW5zaWdu ZWQgaW50IHRhZykKPj4gwqB7Cj4+IC0gwqAgwqAgwqAgLyoKPj4gLSDCoCDCoCDCoCDCoCogVGhl IHJhZGl4IHRyZWUgcGF0aCBuZWVkcyB0byBiZSBvbmUgbG9uZ2VyIHRoYW4gdGhlIG1heGltdW0K Pj4gcGF0aAo+PiAtIMKgIMKgIMKgIMKgKiBzaW5jZSB0aGUgImxpc3QiIGlzIG51bGwgdGVybWlu YXRlZC4KPj4gLSDCoCDCoCDCoCDCoCovCj4+IC0gwqAgwqAgwqAgc3RydWN0IHJhZGl4X3RyZWVf cGF0aCBwYXRoW1JBRElYX1RSRUVfTUFYX1BBVEggKyAxXSwgKnBhdGhwID0KPj4gcGF0aDsKPj4g KyDCoCDCoCDCoCBzdHJ1Y3QgcmFkaXhfdHJlZV9ub2RlICpub2RlID0gTlVMTDsKPj4gwqAgwqAg wqAgwqBzdHJ1Y3QgcmFkaXhfdHJlZV9ub2RlICpzbG90ID0gTlVMTDsKPj4gwqAgwqAgwqAgwqB1 bnNpZ25lZCBpbnQgaGVpZ2h0LCBzaGlmdDsKPj4gKyDCoCDCoCDCoCBpbnQgdW5pbml0aWFsaXpl ZF92YXIob2Zmc2V0KTsKPj4KPj4gwqAgwqAgwqAgwqBoZWlnaHQgPSByb290LT5oZWlnaHQ7Cj4+ IMKgIMKgIMKgIMKgaWYgKGluZGV4PiDCoHJhZGl4X3RyZWVfbWF4aW5kZXgoaGVpZ2h0KSkKPj4g wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBnb3RvIG91dDsKPj4KPj4gLSDCoCDCoCDCoCBzaGlmdCA9 IChoZWlnaHQgLSAxKSAqIFJBRElYX1RSRUVfTUFQX1NISUZUOwo+PiAtIMKgIMKgIMKgIHBhdGhw LT5ub2RlID0gTlVMTDsKPj4gKyDCoCDCoCDCoCBzaGlmdCA9IGhlaWdodCAqIFJBRElYX1RSRUVf TUFQX1NISUZUOwo+PiDCoCDCoCDCoCDCoHNsb3QgPSBpbmRpcmVjdF90b19wdHIocm9vdC0+cm5v ZGUpOwo+Pgo+PiAtIMKgIMKgIMKgIHdoaWxlIChoZWlnaHQ+IMKgMCkgewo+PiAtIMKgIMKgIMKg IMKgIMKgIMKgIMKgIGludCBvZmZzZXQ7Cj4+IC0KPj4gKyDCoCDCoCDCoCB3aGlsZSAoc2hpZnQp IHsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBpZiAoc2xvdCA9PSBOVUxMKQo+PiDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoGdvdG8gb3V0Owo+Pgo+PiArIMKgIMKgIMKgIMKg IMKgIMKgIMKgIHNoaWZ0IC09IFJBRElYX1RSRUVfTUFQX1NISUZUOwo+PiDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoG9mZnNldCA9IChpbmRleD4+IMKgc2hpZnQpJiDCoFJBRElYX1RSRUVfTUFQX01B U0s7Cj4+Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgcGF0aHBbMV0ub2Zmc2V0ID0gb2Zmc2V0 Owo+PiAtIMKgIMKgIMKgIMKgIMKgIMKgIMKgIHBhdGhwWzFdLm5vZGUgPSBzbG90Owo+PiArIMKg IMKgIMKgIMKgIMKgIMKgIMKgIG5vZGUgPSBzbG90Owo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oHNsb3QgPSBzbG90LT5zbG90c1tvZmZzZXRdOwo+PiAtIMKgIMKgIMKgIMKgIMKgIMKgIMKgIHBh dGhwKys7Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgc2hpZnQgLT0gUkFESVhfVFJFRV9NQVBf U0hJRlQ7Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgaGVpZ2h0LS07Cj4+IMKgIMKgIMKgIMKg fQo+Pgo+PiDCoCDCoCDCoCDCoGlmIChzbG90ID09IE5VTEwpCj4+IMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgZ290byBvdXQ7Cj4+Cj4+IC0gwqAgwqAgwqAgd2hpbGUgKHBhdGhwLT5ub2RlKSB7Cj4+ IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgaWYgKCF0YWdfZ2V0KHBhdGhwLT5ub2RlLCB0YWcsIHBh dGhwLT5vZmZzZXQpKQo+PiArIMKgIMKgIMKgIHdoaWxlIChub2RlKSB7Cj4+ICsgwqAgwqAgwqAg wqAgwqAgwqAgwqAgaWYgKCF0YWdfZ2V0KG5vZGUsIHRhZywgb2Zmc2V0KSkKPj4gwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBnb3RvIG91dDsKPj4gLSDCoCDCoCDCoCDCoCDCoCDC oCDCoCB0YWdfY2xlYXIocGF0aHAtPm5vZGUsIHRhZywgcGF0aHAtPm9mZnNldCk7Cj4+IC0gwqAg wqAgwqAgwqAgwqAgwqAgwqAgaWYgKGFueV90YWdfc2V0KHBhdGhwLT5ub2RlLCB0YWcpKQo+PiAr IMKgIMKgIMKgIMKgIMKgIMKgIMKgIHRhZ19jbGVhcihub2RlLCB0YWcsIG9mZnNldCk7Cj4+ICsg wqAgwqAgwqAgwqAgwqAgwqAgwqAgaWYgKGFueV90YWdfc2V0KG5vZGUsIHRhZykpCj4+IMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgZ290byBvdXQ7Cj4+IC0gwqAgwqAgwqAgwqAg wqAgwqAgwqAgcGF0aHAtLTsKPj4gKwo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIGluZGV4Pj49 IFJBRElYX1RSRUVfTUFQX1NISUZUOwo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIG9mZnNldCA9 IGluZGV4JiDCoFJBRElYX1RSRUVfTUFQX01BU0s7Cj4+Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAg wqAgbm9kZSA9IG5vZGUtPnBhcmVudDsKPj4gwqAgwqAgwqAgwqB9Cj4+Cj4+IMKgIMKgIMKgIMKg LyogY2xlYXIgdGhlIHJvb3QncyB0YWcgYml0ICovCj4+IEBAIC02NDYsOCArNjQ1LDcgQEAgdW5z aWduZWQgbG9uZyByYWRpeF90cmVlX3JhbmdlX3RhZ19pZl90YQo+PiDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoHVuc2lnbmVkIGludCBpZnRhZywgdW5zaWduZWQgaW50IHNldHRhZykKPj4gwqB7Cj4+ IMKgIMKgIMKgIMKgdW5zaWduZWQgaW50IGhlaWdodCA9IHJvb3QtPmhlaWdodDsKPj4gLSDCoCDC oCDCoCBzdHJ1Y3QgcmFkaXhfdHJlZV9wYXRoIHBhdGhbaGVpZ2h0XTsKPj4gLSDCoCDCoCDCoCBz dHJ1Y3QgcmFkaXhfdHJlZV9wYXRoICpwYXRocCA9IHBhdGg7Cj4+ICsgwqAgwqAgwqAgc3RydWN0 IHJhZGl4X3RyZWVfbm9kZSAqbm9kZSA9IE5VTEw7Cj4+IMKgIMKgIMKgIMKgc3RydWN0IHJhZGl4 X3RyZWVfbm9kZSAqc2xvdDsKPj4gwqAgwqAgwqAgwqB1bnNpZ25lZCBpbnQgc2hpZnQ7Cj4+IMKg IMKgIMKgIMKgdW5zaWduZWQgbG9uZyB0YWdnZWQgPSAwOwo+PiBAQCAtNjcxLDE0ICs2NjksOCBA QCB1bnNpZ25lZCBsb25nIHJhZGl4X3RyZWVfcmFuZ2VfdGFnX2lmX3RhCj4+IMKgIMKgIMKgIMKg c2hpZnQgPSAoaGVpZ2h0IC0gMSkgKiBSQURJWF9UUkVFX01BUF9TSElGVDsKPj4gwqAgwqAgwqAg wqBzbG90ID0gaW5kaXJlY3RfdG9fcHRyKHJvb3QtPnJub2RlKTsKPj4KPj4gLSDCoCDCoCDCoCAv Kgo+PiAtIMKgIMKgIMKgIMKgKiB3ZSBmaWxsIHRoZSBwYXRoIGZyb20gKHJvb3QtPmhlaWdodCAt IDIpIHRvIDAsIGxlYXZpbmcgdGhlCj4+IGluZGV4IGF0Cj4+IC0gwqAgwqAgwqAgwqAqIChyb290 LT5oZWlnaHQgLSAxKSBhcyBhIHRlcm1pbmF0b3IuIFplcm8gdGhlIG5vZGUgaW4gdGhlCj4+IHRl cm1pbmF0b3IKPj4gLSDCoCDCoCDCoCDCoCogc28gdGhhdCB3ZSBjYW4gdXNlIHRoaXMgdG8gZW5k IHdhbGsgbG9vcHMgYmFjayB1cCB0aGUgcGF0aC4KPj4gLSDCoCDCoCDCoCDCoCovCj4+IC0gwqAg wqAgwqAgcGF0aFtoZWlnaHQgLSAxXS5ub2RlID0gTlVMTDsKPj4gLQo+PiDCoCDCoCDCoCDCoGZv ciAoOzspIHsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCB1bnNpZ25lZCBsb25nIHVwaW5kZXg7 Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgaW50IG9mZnNldDsKPj4KPj4gwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqBvZmZzZXQgPSAoaW5kZXg+PiDCoHNoaWZ0KSYgwqBSQURJWF9UUkVFX01BUF9N QVNLOwo+Pgo+PiBAQCAtNjg2LDEyICs2NzgsMTAgQEAgdW5zaWduZWQgbG9uZyByYWRpeF90cmVl X3JhbmdlX3RhZ19pZl90YQo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoGdv dG8gbmV4dDsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBpZiAoIXRhZ19nZXQoc2xvdCwgaWZ0 YWcsIG9mZnNldCkpCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgZ290byBu ZXh0Owo+PiAtIMKgIMKgIMKgIMKgIMKgIMKgIMKgIGlmIChoZWlnaHQ+IMKgMSkgewo+PiArIMKg IMKgIMKgIMKgIMKgIMKgIMKgIGlmIChzaGlmdCkgewo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoC8qIEdvIGRvd24gb25lIGxldmVsICovCj4+IC0gwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgaGVpZ2h0LS07Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgc2hpZnQgLT0gUkFESVhfVFJFRV9NQVBfU0hJRlQ7Cj4+IC0gwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgcGF0aFtoZWlnaHQgLSAxXS5ub2RlID0gc2xvdDsKPj4gLSDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBwYXRoW2hlaWdodCAtIDFdLm9mZnNldCA9 IG9mZnNldDsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBub2RlID0gc2xv dDsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBzbG90ID0gc2xvdC0+c2xv dHNbb2Zmc2V0XTsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBjb250aW51 ZTsKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqB9Cj4+IEBAIC03MDEsMTUgKzY5MSwyMSBAQCB1 bnNpZ25lZCBsb25nIHJhZGl4X3RyZWVfcmFuZ2VfdGFnX2lmX3RhCj4+IMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgdGFnX3NldChzbG90LCBzZXR0YWcsIG9mZnNldCk7Cj4+Cj4+IMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgLyogd2FsayBiYWNrIHVwIHRoZSBwYXRoIHRhZ2dpbmcgaW50ZXJpb3Igbm9k ZXMgKi8KPj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCBwYXRocCA9JnBhdGhbMF07Cj4+Cj4+IC0g wqAgwqAgwqAgwqAgwqAgwqAgwqAgd2hpbGUgKHBhdGhwLT5ub2RlKSB7Cj4+ICsgwqAgwqAgwqAg wqAgwqAgwqAgwqAgdXBpbmRleCA9IGluZGV4Owo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIHdo aWxlIChub2RlKSB7Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgdXBpbmRl eD4+PSBSQURJWF9UUkVFX01BUF9TSElGVDsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCBvZmZzZXQgPSB1cGluZGV4JiDCoFJBRElYX1RSRUVfTUFQX01BU0s7Cj4+Cj4+ICsK Pj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAvKiBzdG9wIGlmIHdlIGZpbmQg YSBub2RlIHdpdGggdGhlIHRhZyBhbHJlYWR5IHNldAo+PiAqLwo+PiAtIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIGlmICh0YWdfZ2V0KHBhdGhwLT5ub2RlLCBzZXR0YWcsIHBhdGhw LT5vZmZzZXQpKQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIGlmICh0YWdf Z2V0KG5vZGUsIHNldHRhZywgb2Zmc2V0KSkKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqBicmVhazsKPj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCB0YWdfc2V0KHBhdGhwLT5ub2RlLCBzZXR0YWcsIHBhdGhwLT5vZmZzZXQpOwo+PiAt IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIHBhdGhwKys7Cj4+ICsgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgdGFnX3NldChub2RlLCBzZXR0YWcsIG9mZnNldCk7Cj4+ ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgbm9kZSA9IG5vZGUtPnBhcmVudDsK Pj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqB9Cj4+Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAg Lyogb3B0aW1pemF0aW9uOiBubyBuZWVkIHRvIHdhbGsgdXAgZnJvbSB0aGlzIG5vZGUgYWdhaW4K Pj4gKi8KPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCBub2RlID0gTlVMTDsKPj4gKwo+PiDCoG5l eHQ6Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgLyogR28gdG8gbmV4dCBpdGVtIGF0IGxldmVs IGRldGVybWluZWQgYnkgJ3NoaWZ0JyAqLwo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoGluZGV4 ID0gKChpbmRleD4+IMKgc2hpZnQpICsgMSk8PCDCoHNoaWZ0Owo+PiBAQCAtNzI0LDggKzcyMCw3 IEBAIG5leHQ6Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgICogbGFzdF9p bmRleCBpcyBndWFyYW50ZWVkIHRvIGJlIGluIHRoZSB0cmVlLCB3aGF0Cj4+IMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgICogd2UgZG8gYmVsb3cgY2Fubm90IHdhbmRlciBhc3Ry YXkuCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgICovCj4+IC0gwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgc2xvdCA9IHBhdGhbaGVpZ2h0IC0gMV0ubm9kZTsK Pj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBoZWlnaHQrKzsKPj4gKyDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBzbG90ID0gc2xvdC0+cGFyZW50Owo+PiDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoHNoaWZ0ICs9IFJBRElYX1RSRUVfTUFQX1NI SUZUOwo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoH0KPj4gwqAgwqAgwqAgwqB9Cj4+IEBAIC0x Mjk5LDcgKzEyOTQsNyBAQCBzdGF0aWMgaW5saW5lIHZvaWQgcmFkaXhfdHJlZV9zaHJpbmsoc3Ry Cj4+IMKgIMKgIMKgIMKgLyogdHJ5IHRvIHNocmluayB0cmVlIGhlaWdodCAqLwo+PiDCoCDCoCDC oCDCoHdoaWxlIChyb290LT5oZWlnaHQ+IMKgMCkgewo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oHN0cnVjdCByYWRpeF90cmVlX25vZGUgKnRvX2ZyZWUgPSByb290LT5ybm9kZTsKPj4gLSDCoCDC oCDCoCDCoCDCoCDCoCDCoCB2b2lkICpuZXdwdHI7Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAg c3RydWN0IHJhZGl4X3RyZWVfbm9kZSAqc2xvdDsKPj4KPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqBCVUdfT04oIXJhZGl4X3RyZWVfaXNfaW5kaXJlY3RfcHRyKHRvX2ZyZWUpKTsKPj4gwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqB0b19mcmVlID0gaW5kaXJlY3RfdG9fcHRyKHRvX2ZyZWUpOwo+PiBA QCAtMTMyMCwxMCArMTMxNSwxMiBAQCBzdGF0aWMgaW5saW5lIHZvaWQgcmFkaXhfdHJlZV9zaHJp bmsoc3RyCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgICogKHRvX2ZyZWUtPnNsb3RzWzBdKSwg aXQgd2lsbCBiZSBzYWZlIHRvIGRlcmVmZXJlbmNlIHRoZQo+PiBuZXcKPj4gwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgKiBvbmUgKHJvb3QtPnJub2RlKSBhcyBmYXIgYXMgZGVwZW5kZW50IHJlYWQg YmFycmllcnMgZ28uCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgICovCj4+IC0gwqAgwqAgwqAg wqAgwqAgwqAgwqAgbmV3cHRyID0gdG9fZnJlZS0+c2xvdHNbMF07Cj4+IC0gwqAgwqAgwqAgwqAg wqAgwqAgwqAgaWYgKHJvb3QtPmhlaWdodD4gwqAxKQo+PiAtIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIG5ld3B0ciA9IHB0cl90b19pbmRpcmVjdChuZXdwdHIpOwo+PiAtIMKgIMKg IMKgIMKgIMKgIMKgIMKgIHJvb3QtPnJub2RlID0gbmV3cHRyOwo+PiArIMKgIMKgIMKgIMKgIMKg IMKgIMKgIHNsb3QgPSB0b19mcmVlLT5zbG90c1swXTsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDC oCBpZiAocm9vdC0+aGVpZ2h0PiDCoDEpIHsKPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCBzbG90LT5wYXJlbnQgPSBOVUxMOwo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIHNsb3QgPSBwdHJfdG9faW5kaXJlY3Qoc2xvdCk7Cj4+ICsgwqAgwqAgwqAgwqAg wqAgwqAgwqAgfQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIHJvb3QtPnJub2RlID0gc2xvdDsK Pj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqByb290LT5oZWlnaHQtLTsKPj4KPj4gwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAvKgo+PiBAQCAtMTM2MywxNiArMTM2MCwxMiBAQCBzdGF0aWMgaW5saW5l IHZvaWQgcmFkaXhfdHJlZV9zaHJpbmsoc3RyCj4+IMKgICovCj4+IMKgdm9pZCAqcmFkaXhfdHJl ZV9kZWxldGUoc3RydWN0IHJhZGl4X3RyZWVfcm9vdCAqcm9vdCwgdW5zaWduZWQgbG9uZwo+PiBp bmRleCkKPj4gwqB7Cj4+IC0gwqAgwqAgwqAgLyoKPj4gLSDCoCDCoCDCoCDCoCogVGhlIHJhZGl4 IHRyZWUgcGF0aCBuZWVkcyB0byBiZSBvbmUgbG9uZ2VyIHRoYW4gdGhlIG1heGltdW0KPj4gcGF0 aAo+PiAtIMKgIMKgIMKgIMKgKiBzaW5jZSB0aGUgImxpc3QiIGlzIG51bGwgdGVybWluYXRlZC4K Pj4gLSDCoCDCoCDCoCDCoCovCj4+IC0gwqAgwqAgwqAgc3RydWN0IHJhZGl4X3RyZWVfcGF0aCBw YXRoW1JBRElYX1RSRUVfTUFYX1BBVEggKyAxXSwgKnBhdGhwID0KPj4gcGF0aDsKPj4gKyDCoCDC oCDCoCBzdHJ1Y3QgcmFkaXhfdHJlZV9ub2RlICpub2RlID0gTlVMTDsKPj4gwqAgwqAgwqAgwqBz dHJ1Y3QgcmFkaXhfdHJlZV9ub2RlICpzbG90ID0gTlVMTDsKPj4gwqAgwqAgwqAgwqBzdHJ1Y3Qg cmFkaXhfdHJlZV9ub2RlICp0b19mcmVlOwo+PiDCoCDCoCDCoCDCoHVuc2lnbmVkIGludCBoZWln aHQsIHNoaWZ0Owo+PiDCoCDCoCDCoCDCoGludCB0YWc7Cj4+IC0gwqAgwqAgwqAgaW50IG9mZnNl dDsKPj4gKyDCoCDCoCDCoCBpbnQgdW5pbml0aWFsaXplZF92YXIob2Zmc2V0KTsKPj4KPj4gwqAg wqAgwqAgwqBoZWlnaHQgPSByb290LT5oZWlnaHQ7Cj4+IMKgIMKgIMKgIMKgaWYgKGluZGV4PiDC oHJhZGl4X3RyZWVfbWF4aW5kZXgoaGVpZ2h0KSkKPj4gQEAgLTEzODUsMzkgKzEzNzgsMzUgQEAg dm9pZCAqcmFkaXhfdHJlZV9kZWxldGUoc3RydWN0IHJhZGl4X3RyZQo+PiDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoGdvdG8gb3V0Owo+PiDCoCDCoCDCoCDCoH0KPj4gwqAgwqAgwqAgwqBzbG90ID0g aW5kaXJlY3RfdG9fcHRyKHNsb3QpOwo+PiAtCj4+IC0gwqAgwqAgwqAgc2hpZnQgPSAoaGVpZ2h0 IC0gMSkgKiBSQURJWF9UUkVFX01BUF9TSElGVDsKPj4gLSDCoCDCoCDCoCBwYXRocC0+bm9kZSA9 IE5VTEw7Cj4+ICsgwqAgwqAgwqAgc2hpZnQgPSBoZWlnaHQgKiBSQURJWF9UUkVFX01BUF9TSElG VDsKPj4KPj4gwqAgwqAgwqAgwqBkbyB7Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgaWYgKHNs b3QgPT0gTlVMTCkKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqBnb3RvIG91 dDsKPj4KPj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCBwYXRocCsrOwo+PiArIMKgIMKgIMKgIMKg IMKgIMKgIMKgIHNoaWZ0IC09IFJBRElYX1RSRUVfTUFQX1NISUZUOwo+PiDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoG9mZnNldCA9IChpbmRleD4+IMKgc2hpZnQpJiDCoFJBRElYX1RSRUVfTUFQX01B U0s7Cj4+Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgcGF0aHAtPm9mZnNldCA9IG9mZnNldDsK Pj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCBwYXRocC0+bm9kZSA9IHNsb3Q7Cj4+ICsgwqAgwqAg wqAgwqAgwqAgwqAgwqAgbm9kZSA9IHNsb3Q7Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgc2xv dCA9IHNsb3QtPnNsb3RzW29mZnNldF07Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgc2hpZnQg LT0gUkFESVhfVFJFRV9NQVBfU0hJRlQ7Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgaGVpZ2h0 LS07Cj4+IC0gwqAgwqAgwqAgfSB3aGlsZSAoaGVpZ2h0PiDCoDApOwo+PiArIMKgIMKgIMKgIH0g d2hpbGUgKHNoaWZ0KTsKPj4KPj4gwqAgwqAgwqAgwqBpZiAoc2xvdCA9PSBOVUxMKQo+PiDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoGdvdG8gb3V0Owo+Pgo+PiDCoCDCoCDCoCDCoC8qCj4+IC0gwqAg wqAgwqAgwqAqIENsZWFyIGFsbCB0YWdzIGFzc29jaWF0ZWQgd2l0aCB0aGUganVzdC1kZWxldGVk IGl0ZW0KPj4gKyDCoCDCoCDCoCDCoCogQ2xlYXIgYWxsIHRhZ3MgYXNzb2NpYXRlZCB3aXRoIHRo ZSBpdGVtIHRvIGJlIGRlbGV0ZWQuCj4+ICsgwqAgwqAgwqAgwqAqIFRoaXMgd2F5IG9mIGRvaW5n IGl0IHdvdWxkIGJlIGluZWZmaWNpZW50LCBidXQgc2VsZG9tIGlzIGFueQo+PiBzZXQuCj4+IMKg IMKgIMKgIMKgICovCj4+IMKgIMKgIMKgIMKgZm9yICh0YWcgPSAwOyB0YWc8IMKgUkFESVhfVFJF RV9NQVhfVEFHUzsgdGFnKyspIHsKPj4gLSDCoCDCoCDCoCDCoCDCoCDCoCDCoCBpZiAodGFnX2dl dChwYXRocC0+bm9kZSwgdGFnLCBwYXRocC0+b2Zmc2V0KSkKPj4gKyDCoCDCoCDCoCDCoCDCoCDC oCDCoCBpZiAodGFnX2dldChub2RlLCB0YWcsIG9mZnNldCkpCj4+IMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgcmFkaXhfdHJlZV90YWdfY2xlYXIocm9vdCwgaW5kZXgsIHRhZyk7 Cj4+IMKgIMKgIMKgIMKgfQo+Pgo+PiDCoCDCoCDCoCDCoHRvX2ZyZWUgPSBOVUxMOwo+PiDCoCDC oCDCoCDCoC8qIE5vdyBmcmVlIHRoZSBub2RlcyB3ZSBkbyBub3QgbmVlZCBhbnltb3JlICovCj4+ IC0gwqAgwqAgwqAgd2hpbGUgKHBhdGhwLT5ub2RlKSB7Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAg wqAgcGF0aHAtPm5vZGUtPnNsb3RzW3BhdGhwLT5vZmZzZXRdID0gTlVMTDsKPj4gLSDCoCDCoCDC oCDCoCDCoCDCoCDCoCBwYXRocC0+bm9kZS0+Y291bnQtLTsKPj4gKyDCoCDCoCDCoCB3aGlsZSAo bm9kZSkgewo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIG5vZGUtPnNsb3RzW29mZnNldF0gPSBO VUxMOwo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIG5vZGUtPmNvdW50LS07Cj4+IMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgLyoKPj4gwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgKiBRdWV1ZSB0aGUg bm9kZSBmb3IgZGVmZXJyZWQgZnJlZWluZyBhZnRlciB0aGUKPj4gwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgKiBsYXN0IHJlZmVyZW5jZSB0byBpdCBkaXNhcHBlYXJzIChzZXQgTlVMTCwgYWJvdmUp Lgo+PiBAQCAtMTQyNSwxNyArMTQxNCwyMCBAQCB2b2lkICpyYWRpeF90cmVlX2RlbGV0ZShzdHJ1 Y3QgcmFkaXhfdHJlCj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgaWYgKHRvX2ZyZWUpCj4+IMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgcmFkaXhfdHJlZV9ub2RlX2ZyZWUodG9f ZnJlZSk7Cj4+Cj4+IC0gwqAgwqAgwqAgwqAgwqAgwqAgwqAgaWYgKHBhdGhwLT5ub2RlLT5jb3Vu dCkgewo+PiAtIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIGlmIChwYXRocC0+bm9k ZSA9PSBpbmRpcmVjdF90b19wdHIocm9vdC0+cm5vZGUpKQo+PiArIMKgIMKgIMKgIMKgIMKgIMKg IMKgIGlmIChub2RlLT5jb3VudCkgewo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIGlmIChub2RlID09IGluZGlyZWN0X3RvX3B0cihyb290LT5ybm9kZSkpCj4+IMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgcmFkaXhfdHJlZV9zaHJpbmso cm9vdCk7Cj4+IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgZ290byBvdXQ7Cj4+ IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgfQo+Pgo+PiDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoC8q IE5vZGUgd2l0aCB6ZXJvIHNsb3RzIGluIHVzZSBzbyBmcmVlIGl0ICovCj4+IC0gwqAgwqAgwqAg wqAgwqAgwqAgwqAgdG9fZnJlZSA9IHBhdGhwLT5ub2RlOwo+PiAtIMKgIMKgIMKgIMKgIMKgIMKg IMKgIHBhdGhwLS07Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAgdG9fZnJlZSA9IG5vZGU7Cj4+ Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAgaW5kZXg+Pj0gUkFESVhfVFJFRV9NQVBfU0hJRlQ7 Cj4+ICsgwqAgwqAgwqAgwqAgwqAgwqAgwqAgb2Zmc2V0ID0gaW5kZXgmIMKgUkFESVhfVFJFRV9N QVBfTUFTSzsKPj4KPj4gKyDCoCDCoCDCoCDCoCDCoCDCoCDCoCBub2RlID0gbm9kZS0+cGFyZW50 Owo+PiDCoCDCoCDCoCDCoH0KPj4gKwo+PiDCoCDCoCDCoCDCoHJvb3RfdGFnX2NsZWFyX2FsbChy b290KTsKPj4gwqAgwqAgwqAgwqByb290LT5oZWlnaHQgPSAwOwo+PiDCoCDCoCDCoCDCoHJvb3Qt PnJub2RlID0gTlVMTDsKPj4KPj4gLS0KPj4gVG8gdW5zdWJzY3JpYmUsIHNlbmQgYSBtZXNzYWdl IHdpdGggJ3Vuc3Vic2NyaWJlIGxpbnV4LW1tJyBpbgo+PiB0aGUgYm9keSB0byBtYWpvcmRvbW9A a3ZhY2sub3JnLiDCoEZvciBtb3JlIGluZm8gb24gTGludXggTU0sCj4+IHNlZTogaHR0cDovL3d3 dy5saW51eC1tbS5vcmcvIC4KPj4gRmlnaHQgdW5mYWlyIHRlbGVjb20gaW50ZXJuZXQgY2hhcmdl cyBpbiBDYW5hZGE6IHNpZ24KPj4gaHR0cDovL3N0b3B0aGVtZXRlci5jYS8KPj4gRG9uJ3QgZW1h aWw6PGEgaHJlZj1tYWlsdG86ImRvbnRAa3ZhY2sub3JnIj4gwqBlbWFpbEBrdmFjay5vcmc8L2E+ Cg==

Hugh Dickins

author

2011-12-19 20:13 UTC #3 lore raw

Quoted 11 lines · Nai Xia

Quoted 10 lines · nai.xia
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.

Quoted 6 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

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".

Quoted 7 lines

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

Dave Chinner

2011-12-21 05:07 UTC #4 lore raw

In reply to Hugh Dickins

Quoted 20 lines · 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.

Quoted 6 lines

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.

Quoted 2 lines

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

*nod*

Quoted 2 lines

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....

Quoted 4 lines

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.

Quoted 8 lines

[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.

Quoted 5 lines

lib/radix-tree.c +0 -1

@@ -274,18 +273,23 @@ static int radix_tree_extend(struct radi
 		if (!(node = radix_tree_node_alloc(root)))
 			return -ENOMEM;
 
-		/* Increase the height.  */

lib/radix-tree.c static int radix_tree_extend(struct radi · line 283

Quoted 10 lines

lib/radix-tree.c +1 -2

-		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.

lib/radix-tree.c static int radix_tree_extend(struct radi · line 292

Quoted 9 lines

lib/radix-tree.c +7 -0

 		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;

Quoted 13 lines

lib/radix-tree.c +5 -3

@@ -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))

lib/radix-tree.c unsigned long radix_tree_range_tag_if_ta · line 707

Quoted 10 lines

lib/radix-tree.c +5 -2

+			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.

Signature · 9 lines

Dave Chinner
[email protected]

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  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:"[email protected]"> [email protected] </a>

Hugh Dickins

author

2011-12-21 06:53 UTC #5 lore raw

Quoted 9 lines · Dave Chinner

Quoted 2 lines · Hugh Dickins
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...

Quoted 7 lines

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.

Quoted 16 lines

Couple more comments below.

Quoted 13 lines

lib/radix-tree.c +0 -3

@@ -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);
 		}

Quoted 5 lines

lib/radix-tree.c static int radix_tree_extend(struct radi · line 283
Quoted 2 lines
lib/radix-tree.c +1 -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.

Quoted 14 lines

lib/radix-tree.c static int radix_tree_extend(struct radi · line 292
Quoted 10 lines
lib/radix-tree.c +7 -0
 		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:

Quoted 8 lines

		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.

Quoted 22 lines

lib/radix-tree.c +8 -5

@@ -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;
 		}

Quoted 5 lines

lib/radix-tree.c unsigned long radix_tree_range_tag_if_ta · line 707
Quoted 2 lines
lib/radix-tree.c +2 -0
+		/* 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

Dave Chinner

2011-12-21 22:15 UTC #6 lore raw

Quoted 2 lines · Hugh Dickins

Quoted 1 line · Dave Chinner
On Sun, Dec 18, 2011 at 10:41:39PM -0800, Hugh Dickins wrote:

.....

Quoted 12 lines

lib/radix-tree.c +0 -3

 		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);
 		}

Quoted 8 lines

Quoted 5 lines
lib/radix-tree.c static int radix_tree_extend(struct radi · line 283
Quoted 2 lines
lib/radix-tree.c +1 -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.

Quoted 22 lines

Quoted 13 lines
lib/radix-tree.c static int radix_tree_extend(struct radi · line 292
Quoted 9 lines
lib/radix-tree.c +7 -0
 		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:
Quoted 8 lines
		if (newheight > 1) {
			slot = indirect_to_ptr(root->rnode);
			slot->parent = node;
		} else {
			slot = root->rnode;
			node->parent = NULL;
		}
		node->slots[0] = slot;

Quoted 4 lines

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...

Quoted 33 lines

Quoted 21 lines
Quoted 21 lines
lib/radix-tree.c +8 -5
@@ -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;
 		}
 
Quoted 5 lines
lib/radix-tree.c unsigned long radix_tree_range_tag_if_ta · line 707
Quoted 2 lines
lib/radix-tree.c +2 -0
+		/* 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.

Quoted 6 lines

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.

Signature · 9 lines

Dave Chinner
[email protected]

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  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:"[email protected]"> [email protected] </a>

Hugh Dickins

author

2011-12-21 23:55 UTC #7 lore raw

Quoted 8 lines · Dave Chinner

Quoted 6 lines · Hugh Dickins
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.

Quoted 5 lines

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.

Quoted 15 lines

Quoted 6 lines
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.
Quoted 6 lines
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:

Quoted 8 lines

/*
* 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

Hugh Dickins

author

2011-12-21 23:57 UTC #8 lore raw

PATCH 1/1 radix_tree: expand comment on optimization

In reply to Dave Chinner

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

Signed-off-by Hugh Dickins <[email protected]>

---
And with -p2, this patch will also apply to the rtth tree.

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

lib/radix-tree.c +7 -1

@@ -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:

Dave Chinner

2011-12-22 00:17 UTC #9 lore raw

Re: [PATCH] radix_tree: expand comment on optimization

Quoted 15 lines · 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 <[email protected]>
---
And with -p2, this patch will also apply to the rtth tree.
 lib/radix-tree.c |    8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)
lib/radix-tree.c +0 -0
@@ -703,7 +703,13 @@ unsigned long radix_tree_range_tag_if_ta
 			node = node->parent;
 		}

lib/radix-tree.c unsigned long radix_tree_range_tag_if_ta · line 713

Quoted 10 lines

lib/radix-tree.c +7 -1

 
-		/* 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.

Signature · 9 lines

Dave Chinner
[email protected]

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  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:"[email protected]"> [email protected] </a>

nai.xia

2011-12-22 03:16 UTC #10 lore raw

PATCH 1/1 radix_tree: delete orphaned macro radix_tree_indirect_to_ptr

In reply to Hugh Dickins

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

Signed-off-by Nai Xia <[email protected]>

---
 include/linux/radix-tree.h |    3 ---
 1 files changed, 0 insertions(+), 3 deletions(-)

include/linux/radix-tree.h +0 -3

@@ -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);

Li Zefan

2011-12-22 03:27 UTC #11 lore raw

Re: [PATCH] radix_tree: delete orphaned macro radix_tree_indirect_to_ptr

Quoted 3 lines · nai.xia

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

Quoted 8 lines

Signed-off-by Nai Xia <[email protected]>
---
 include/linux/radix-tree.h |    3 ---
 1 files changed, 0 insertions(+), 3 deletions(-)

include/linux/radix-tree.h line 54

Quoted 9 lines

include/linux/radix-tree.h +0 -3

@@ -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);

Nai Xia

2011-12-22 03:36 UTC #12 lore raw

Re: [PATCH] radix_tree: delete orphaned macro radix_tree_indirect_to_ptr

Quoted 8 lines · Li Zefan

Quoted 3 lines · nai.xia
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. :)

Quoted 12 lines

Quoted 12 lines
Signed-off-by Nai Xia <[email protected]>
---
include/linux/radix-tree.h | 3 ---
 1 files changed, 0 insertions(+), 3 deletions(-)
include/linux/radix-tree.h +0 -0
@@ -49,9 +49,6 @@
  #define RADIX_TREE_EXCEPTIONAL_ENTRY    2
  #define RADIX_TREE_EXCEPTIONAL_SHIFT    2
 

Quoted 13 lines

include/linux/radix-tree.h line 54
Quoted 6 lines
include/linux/radix-tree.h +0 -3
-#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 [email protected]. 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:"[email protected]"> [email protected] </a>