linux-kernel - [RFC] radix_tree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 16 Dec 2010 08:27:41 -0800 (PST)
From:	Dan Magenheimer <dan.magenheimer@...cle.com>
To:	linux-mm@...ck.org, linux-kernel@...r.kernel.org
Cc:	dan.magenheimer@...cle.com
Subject: [RFC] radix_tree_destroy?

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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/