From 4886e5d652eb7fe1164f4f47dd8e88c646e6a52e Mon Sep 17 00:00:00 2001 From: Matthew Wilcox 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 --- include/linux/maple_tree.h | 4 ++ lib/maple_tree.c | 53 +++++++++++++++++++++++---- tools/testing/radix-tree/linux.c | 30 +++++++++------ tools/testing/radix-tree/linux/slab.h | 2 +- tools/testing/radix-tree/maple.c | 7 ++-- 5 files changed, 73 insertions(+), 23 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 +#include + +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/linux.c b/tools/testing/radix-tree/linux.c index 44a0d1ad4408..4128aab15b13 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -19,37 +19,44 @@ int test_verbose; struct kmem_cache { pthread_mutex_t lock; - int size; + unsigned int size; + unsigned int align; int nr_objs; void *objs; void (*ctor)(void *); }; -void *kmem_cache_alloc(struct kmem_cache *cachep, int flags) +void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp) { - struct radix_tree_node *node; + void *p; - if (!(flags & __GFP_DIRECT_RECLAIM)) + if (!(gfp & __GFP_DIRECT_RECLAIM)) return NULL; pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs) { + struct radix_tree_node *node = cachep->objs; cachep->nr_objs--; - node = cachep->objs; cachep->objs = node->parent; pthread_mutex_unlock(&cachep->lock); node->parent = NULL; + p = node; } else { pthread_mutex_unlock(&cachep->lock); - node = malloc(cachep->size); + if (cachep->align) + posix_memalign(&p, cachep->align, cachep->size); + else + p = malloc(cachep->size); if (cachep->ctor) - cachep->ctor(node); + cachep->ctor(p); + else if (gfp & __GFP_ZERO) + memset(p, 0, cachep->size); } uatomic_inc(&nr_allocated); if (kmalloc_verbose) - printf("Allocating %p from slab\n", node); - return node; + printf("Allocating %p from slab\n", p); + return p; } void kmem_cache_free(struct kmem_cache *cachep, void *objp) @@ -59,7 +66,7 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp) if (kmalloc_verbose) printf("Freeing %p to slab\n", objp); pthread_mutex_lock(&cachep->lock); - if (cachep->nr_objs > 10) { + if (cachep->nr_objs > 10 || cachep->align) { memset(objp, POISON_FREE, cachep->size); free(objp); } else { @@ -98,13 +105,14 @@ void kfree(void *p) } struct kmem_cache * -kmem_cache_create(const char *name, size_t size, size_t offset, +kmem_cache_create(const char *name, unsigned int size, unsigned int align, unsigned long flags, void (*ctor)(void *)) { struct kmem_cache *ret = malloc(sizeof(*ret)); pthread_mutex_init(&ret->lock, NULL); ret->size = size; + ret->align = align; ret->nr_objs = 0; ret->objs = NULL; ret->ctor = ctor; diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h index a037def0dec6..e749e68c1d1c 100644 --- a/tools/testing/radix-tree/linux/slab.h +++ b/tools/testing/radix-tree/linux/slab.h @@ -21,7 +21,7 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, int flags); void kmem_cache_free(struct kmem_cache *cachep, void *objp); struct kmem_cache * -kmem_cache_create(const char *name, size_t size, size_t offset, +kmem_cache_create(const char *name, unsigned int size, unsigned int align, unsigned long flags, void (*ctor)(void *)); #endif /* SLAB_H */ 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