[RFC] radix_tree_destroy?

[RFC] radix_tree_destroy?

[Dan Magenheimer]

I am in need of a radix-tree routine that will efficiently
"destroy" an entire radix tree, but make callbacks to free the
slots.  Is it possible to do that (efficiently) with existing
radix-tree code?  If so, I'd appreciate some guidance.

If not, I'm thinking about submitting a patch (as part of a
larger patchset) that would look something like the patch below.
I'm uncertain of the rcu implications however... because
of the mass destruction, perhaps there could just be a
requirement that the caller must lock the entire tree
prior to the call?

Another option would be for me to do this outside of
radix-tree.c, but then I would need to move some defines and
the definition of the struct radix_tree_node from
radix-tree.c to radix-tree.h

Thanks for any advice!
Dan

P.S. I will be offline for an extended period over the holidays,
so apologies in advance if I am unable to respond quickly.

--- radix-tree.c	2010-10-20 14:30:22.000000000 -0600
+++ radix-tree.patch.c	2010-12-16 16:13:32.672039108 -0700
@@ -1318,6 +1318,42 @@ out:
 }
 EXPORT_SYMBOL(radix_tree_delete);
 
+static void
+radix_tree_node_destroy(struct radix_tree_node *node, unsigned int height,
+			void (*slot_free)(void *))
+{
+	int i;
+
+	if (height == 0)
+		return;
+	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
+		if (node->slots[i]) {
+			if (height > 1) {
+				radix_tree_node_destroy(node->slots[i],
+					height-1, slot_free);
+				radix_tree_node_free(node->slots[i]);
+				node->slots[i] = NULL;
+			} else
+				slot_free(node->slots[i]);
+		}
+	}
+}
+
+void radix_tree_destroy(struct radix_tree_root *root, void (*slot_free)(void *))
+{
+	if (root->rnode == NULL)
+		return;
+	if (root->height == 0)
+		slot_free(root->rnode);
+	else {
+		radix_tree_node_destroy(root->rnode, root->height, slot_free);
+		radix_tree_node_free(root->rnode);
+		root->height = 0;
+	}
+	root->rnode = NULL;
+}
+EXPORT_SYMBOL(radix_tree_destroy);
+
 /**
  *	radix_tree_tagged - test whether any items in the tree are tagged
  *	@root:		radix tree root

Re: [RFC] radix_tree_destroy?

[Paul Mundt]

On Thu, Dec 16, 2010 at 08:27:41AM -0800, Dan Magenheimer wrote:
> +static void
> +radix_tree_node_destroy(struct radix_tree_node *node, unsigned int height,
> +			void (*slot_free)(void *))
> +{
> +	int i;
> +
> +	if (height == 0)
> +		return;
> +	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
> +		if (node->slots[i]) {
> +			if (height > 1) {
> +				radix_tree_node_destroy(node->slots[i],
> +					height-1, slot_free);
> +				radix_tree_node_free(node->slots[i]);
> +				node->slots[i] = NULL;
> +			} else
> +				slot_free(node->slots[i]);
> +		}
> +	}
> +}
> +
> +void radix_tree_destroy(struct radix_tree_root *root, void (*slot_free)(void *))
> +{
> +	if (root->rnode == NULL)
> +		return;
> +	if (root->height == 0)
> +		slot_free(root->rnode);

Don't you want indirect_to_ptr(root->rnode) here? You probably also don't
want the callback in the !radix_tree_is_indirect_ptr() case.

> +	else {
> +		radix_tree_node_destroy(root->rnode, root->height, slot_free);
> +		radix_tree_node_free(root->rnode);
> +		root->height = 0;
> +	}
> +	root->rnode = NULL;
> +}

The above will handle the nodes, but what about the root? It looks like
you're at least going to leak tags on the root, so at the very least
you'd still want a root_tag_clear_all() here.

RE: [RFC] radix_tree_destroy?

[Dan Magenheimer]

> > +void radix_tree_destroy(struct radix_tree_root *root, void
> (*slot_free)(void *))
> > +{
> > +	if (root->rnode == NULL)
> > +		return;
> > +	if (root->height == 0)
> > +		slot_free(root->rnode);
> 
> Don't you want indirect_to_ptr(root->rnode) here? You probably also
> don't
> want the callback in the !radix_tree_is_indirect_ptr() case.
> 
> > +	else {
> > +		radix_tree_node_destroy(root->rnode, root->height,
> slot_free);
> > +		radix_tree_node_free(root->rnode);
> > +		root->height = 0;
> > +	}
> > +	root->rnode = NULL;
> > +}
> 
> The above will handle the nodes, but what about the root? It looks like
> you're at least going to leak tags on the root, so at the very least
> you'd still want a root_tag_clear_all() here.

Thanks for your help.  Will do both.  My use model doesn't require
tags or rcu, so my hacked version of radix_tree_destroy missed those
subtleties.

So my assumption was correct?  There is no way to efficiently
destroy an entire radix tree without adding this new routine?

Thanks,
Dan

Re: [RFC] radix_tree_destroy?

[Paul Mundt]

On Fri, Dec 17, 2010 at 10:44:06AM -0800, Dan Magenheimer wrote:
> > > +void radix_tree_destroy(struct radix_tree_root *root, void
> > (*slot_free)(void *))
> > > +{
> > > +	if (root->rnode == NULL)
> > > +		return;
> > > +	if (root->height == 0)
> > > +		slot_free(root->rnode);
> > 
> > Don't you want indirect_to_ptr(root->rnode) here? You probably also
> > don't
> > want the callback in the !radix_tree_is_indirect_ptr() case.
> > 
> > > +	else {
> > > +		radix_tree_node_destroy(root->rnode, root->height,
> > slot_free);
> > > +		radix_tree_node_free(root->rnode);
> > > +		root->height = 0;
> > > +	}
> > > +	root->rnode = NULL;
> > > +}
> > 
> > The above will handle the nodes, but what about the root? It looks like
> > you're at least going to leak tags on the root, so at the very least
> > you'd still want a root_tag_clear_all() here.
> 
> Thanks for your help.  Will do both.  My use model doesn't require
> tags or rcu, so my hacked version of radix_tree_destroy missed those
> subtleties.
> 
> So my assumption was correct?  There is no way to efficiently
> destroy an entire radix tree without adding this new routine?
> 
Not that I'm specifically aware of, no. Most of the in-tree radix users
bury the tree pointer under some other data structure that is separately
accounted and then manually balanced with the insert/remove pair. I
suppose your use case is modular and you wish to tear down the root
completely on exit. In that case, if you have items you need to iterate
over to clean up after for a clean exit anyways then simply wrapping in
to radix_tree_delete() at that point for node-at-a-time freeing would be
consistent with in-tree usage today. It'd be interesting to know what
precisely your use case is and why the existing node-at-a-time delete
semantics are sub-optimal for you, though.