From 6aa359c4578a71b01540ec1a69da8f7eefde6c7a Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 24 Dec 2018 12:31:00 -0500
Subject: [PATCH] maple_tree: Add kmem_cache

Allocate nodes from a kmem cache, making the necessary changes to the
slab emulation to support alignment.  Free nodes through RCU.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 include/linux/maple_tree.h       |  4 +++
 lib/maple_tree.c                 | 53 +++++++++++++++++++++++++++-----
 tools/testing/radix-tree/maple.c |  7 +++--
 3 files changed, 53 insertions(+), 11 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 431d1f10757f..3c04426d9f59 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -104,6 +104,10 @@ struct maple_node {
 			struct maple_node *parent;
 			void __rcu *slot[MAPLE_NODE_SLOTS];
 		};
+		struct {
+			void *pad;
+			struct rcu_head rcu;
+		};
 		struct maple_range_64 mr64;
 		struct maple_range_32 mr32;
 		struct maple_range_16 mr16;
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d308f6b5708a..304a6c067bf8 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7,6 +7,26 @@
  */
 
 #include <linux/maple_tree.h>
+#include <linux/slab.h>
+
+static struct kmem_cache *maple_node_cache;
+
+static struct maple_node *mt_alloc_one(gfp_t gfp)
+{
+	return kmem_cache_alloc(maple_node_cache, gfp | __GFP_ZERO);
+}
+
+static void mt_free_rcu(struct rcu_head *head)
+{
+	struct maple_node *node = container_of(head, struct maple_node, rcu);
+	kmem_cache_free(maple_node_cache, node);
+}
+
+static void mt_free(struct maple_node *node)
+{
+	node->parent = node;
+	call_rcu(&node->rcu, mt_free_rcu);
+}
 
 static inline enum maple_type mt_node_type(const void *entry)
 {
@@ -18,7 +38,7 @@ static inline bool mt_is_leaf(const void *entry)
 	return mt_node_type(entry) < maple_range_16;
 }
 
-static inline bool ma_is_reserved(const void *entry)
+static inline bool mt_is_reserved(const void *entry)
 {
 	return ((unsigned long)entry < 4096) && xa_is_internal(entry);
 }
@@ -41,26 +61,43 @@ void *mt_mk_node(const struct maple_node *node, enum maple_type type)
 	return (void *)((unsigned long)node | (type << 3) | 2);
 }
 
-void mtree_init(struct maple_tree *mt) {
+void mtree_init(struct maple_tree *mt)
+{
 	spin_lock_init(&mt->ma_lock);
 	mt->ma_flags = 0;
 	mt->ma_root = NULL;
 }
-void *mtree_load(struct maple_tree *mt, unsigned long index) {
+
+void *mtree_load(struct maple_tree *mt, unsigned long index)
+{
 	return NULL;
 }
-int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp) {
+
+int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp)
+{
 	return -EINVAL;
 }
+
 int mtree_insert_range(struct maple_tree *mt, unsigned long first,
-		unsigned long last, void *entry, gfp_t gfp) {
+		unsigned long last, void *entry, gfp_t gfp)
+{
 	return -EINVAL;
 }
-int mtree_erase(struct maple_tree *mt, unsigned long index) {
+
+int mtree_erase(struct maple_tree *mt, unsigned long index)
+{
 	return -EINVAL;
 }
 
-void mtree_destroy(struct maple_tree *mt) {
+void mtree_destroy(struct maple_tree *mt)
+{
+}
+
+void __init maple_tree_init(void)
+{
+	maple_node_cache = kmem_cache_create("maple node",
+			sizeof(struct maple_node), sizeof(struct maple_node),
+			SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, NULL);
 }
 
 #ifdef MT_DEBUG
@@ -81,7 +118,7 @@ void mt_dump_entry(void *entry, unsigned long min, unsigned long max)
 				xa_to_value(entry), entry);
 	else if (xa_is_zero(entry))
 		pr_cont("zero (%ld)\n", xa_to_internal(entry));
-	else if (ma_is_reserved(entry))
+	else if (mt_is_reserved(entry))
 		pr_cont("UNKNOWN ENTRY (%p)\n", entry);
 	else
 		pr_cont("%p\n", entry);
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 7ec885eca802..ba7c3c46b595 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -26,7 +26,7 @@ void farmer_tests(void)
 	tree.ma_root = xa_mk_value(0);
 	mt_dump(&tree);
 
-	posix_memalign(&node, 128, 128);
+	node = mt_alloc_one(GFP_KERNEL);
 	node->parent = (void *)((unsigned long)(&tree) | 1);
 	node->slot[0] = xa_mk_value(0);
 	node->slot[1] = xa_mk_value(1);
@@ -35,6 +35,8 @@ void farmer_tests(void)
 	node->mr64.pivot[2] = 0;
 	tree.ma_root = mt_mk_node(node, maple_leaf_64);
 	mt_dump(&tree);
+
+	mt_free(node);
 }
 
 void maple_tree_tests(void)
@@ -46,9 +48,8 @@ void maple_tree_tests(void)
 
 int __weak main(void)
 {
-	radix_tree_init();
+	maple_tree_init();
 	maple_tree_tests();
-	radix_tree_cpu_dead(1);
 	rcu_barrier();
 	if (nr_allocated)
 		printf("nr_allocated = %d\n", nr_allocated);
-- 
2.50.1