From: Wang Wensheng wangwensheng4@huawei.com
This algorithm is something alike to the algorithm that used for vm_area alloc in vmalloc and mmap.
Use the augmented rb_tree to organize all the free block.
Signed-off-by: Wang Wensheng wangwensheng4@huawei.com --- include/uapi/linux/xshmem_framework.h | 1 + lib/xshmem/Makefile | 2 +- lib/xshmem/xshmem_framework.c | 2 + lib/xshmem/xshmem_vma.c | 343 ++++++++++++++++++++++++++++++++++ 4 files changed, 347 insertions(+), 1 deletion(-) create mode 100644 lib/xshmem/xshmem_vma.c
diff --git a/include/uapi/linux/xshmem_framework.h b/include/uapi/linux/xshmem_framework.h index 205c928..63b8c3b 100644 --- a/include/uapi/linux/xshmem_framework.h +++ b/include/uapi/linux/xshmem_framework.h @@ -34,6 +34,7 @@ struct xshm_block_arg { #define XSHMEM_ALGO_EMPTY -1 #define XSHMEM_ALGO_BLOCK 0 #define XSHMEM_ALGO_FSC 1 +#define XSHMEM_ALGO_VMA 2
#define XSHMEM_POOL_STATUS_DELETE 0 #define XSHMEM_POOL_STATUS_EXIST 1 diff --git a/lib/xshmem/Makefile b/lib/xshmem/Makefile index b7cf800..42637d4 100644 --- a/lib/xshmem/Makefile +++ b/lib/xshmem/Makefile @@ -1,2 +1,2 @@ obj-m+=xshmem.o -xshmem-objs+=xshmem_fsc.o xshmem_framework.o xshmem_blk.o +xshmem-objs+=xshmem_fsc.o xshmem_framework.o xshmem_blk.o xshmem_vma.o diff --git a/lib/xshmem/xshmem_framework.c b/lib/xshmem/xshmem_framework.c index cf8f91e..cd09aca 100644 --- a/lib/xshmem/xshmem_framework.c +++ b/lib/xshmem/xshmem_framework.c @@ -866,6 +866,7 @@ static struct xshm_pool_algo empty_algo = { .xshm_block_free = empty_algo_block_free, };
+extern struct xshm_pool_algo vma_algo; extern struct xshm_pool_algo fsc_algo; extern struct xshm_pool_algo blk_algo;
@@ -883,6 +884,7 @@ static int __init xshmem_init(void) return ret; }
+ xshmem_register_algo(&vma_algo); xshmem_register_algo(&fsc_algo); xshmem_register_algo(&blk_algo); xshmem_register_algo(&empty_algo); diff --git a/lib/xshmem/xshmem_vma.c b/lib/xshmem/xshmem_vma.c new file mode 100644 index 0000000..bb8de95 --- /dev/null +++ b/lib/xshmem/xshmem_vma.c @@ -0,0 +1,343 @@ +/* + * Copyright (C) Huawei Technologies Co., Ltd. 2021. All rights reserved. + * Author: Huawei OS Kernel Lab + * Create: Mon Jul 19 07:01:42 2021 + */ +#include <asm-generic/ioctl.h> +#define pr_fmt(fmt) "XSHMEM_VMA: " fmt + +#include <linux/types.h> +#include <linux/printk.h> +#include <linux/slab.h> +#include <linux/module.h> +#include <linux/rbtree_augmented.h> + +#include "xshmem_framework.h" + +#define XSHMEM_VMA_ALIGN 16U + +struct vma_ctrl { + unsigned long total_size; + unsigned long free_size; + unsigned long alloc_block_cnt; + + struct rb_root free_block_root; +}; + +struct vma_block { + struct rb_node rb_node; + + unsigned long start; + unsigned long size; + unsigned long subtree_max_size; +}; + +static struct vma_block *to_vma_block(struct rb_node *node) +{ + return rb_entry(node, struct vma_block, rb_node); +} + +static unsigned long subtree_max_size(struct rb_node *node) +{ + return node ? to_vma_block(node)->subtree_max_size : 0; +} + +static unsigned long compute_subtree_max_size(struct vma_block *block) +{ + return max3(block->size, subtree_max_size(block->rb_node.rb_left), + subtree_max_size(block->rb_node.rb_right)); +} + +RB_DECLARE_CALLBACKS(static, vma_block_subtree_max_size_cb, struct vma_block, rb_node, + unsigned long, subtree_max_size, compute_subtree_max_size); + +static void block_update_subtree_max_size(struct vma_block *block) +{ + vma_block_subtree_max_size_cb_propagate(&block->rb_node, NULL); +} + +static bool vma_algo_pool_same(struct xshm_pool *xp, struct xshm_reg_arg *arg) +{ + struct vma_ctrl *ctrl = xp->private; + + return ctrl->total_size == arg->pool_size; +} + +static int vma_algo_pool_init(struct xshm_pool *xp, struct xshm_reg_arg *arg) +{ + struct vma_ctrl *ctrl = NULL; + struct vma_block *block = NULL; + + if (!IS_ALIGNED(arg->pool_size, XSHMEM_VMA_ALIGN) || !arg->pool_size) { + pr_err("input xshm_pool size invalid\n"); + return -EINVAL; + } + + ctrl = kmalloc(sizeof(*ctrl), GFP_KERNEL); + block = kmalloc(sizeof(*block), GFP_KERNEL); + if (unlikely(ctrl == NULL || block == NULL)) { + kfree(ctrl); + kfree(block); + return -ENOMEM; + } + + ctrl->total_size = arg->pool_size; + ctrl->free_size = arg->pool_size; + ctrl->alloc_block_cnt = 0; + ctrl->free_block_root.rb_node = NULL; + + block->start = 0; + block->size = arg->pool_size; + block->subtree_max_size = arg->pool_size; + rb_link_node(&block->rb_node, NULL, &ctrl->free_block_root.rb_node); + rb_insert_color(&block->rb_node, &ctrl->free_block_root); + + xp->private = ctrl; + + return 0; +} + +#ifdef DEBUG_XSHMEM_VMA +static void block_dump(struct vma_block *block) +{ + pr_info("block: start: %#lx, size: %#lx, subtree_max_size: %#lx\n", + block->start, block->size, block->subtree_max_size); +} + +static void pool_dump(struct vma_ctrl *ctrl) +{ + struct vma_block *block, *tmp; + + rbtree_postorder_for_each_entry_safe(block, tmp, &ctrl->free_block_root, rb_node) + block_dump(block); +} +#else +static void pool_dump(struct vma_ctrl *ctrl) {} +#endif + +static int vma_algo_pool_free(struct xshm_pool *xp) +{ + struct vma_ctrl *ctrl = xp->private; + struct vma_block *block = to_vma_block(ctrl->free_block_root.rb_node); + + WARN(ctrl->total_size != ctrl->free_size, "not all block freed\n"); + WARN(ctrl->total_size != block->size, "not all block freed\n"); + WARN(ctrl->total_size != block->subtree_max_size, "not all block freed\n"); + + pool_dump(ctrl); + + kfree(block); + kfree(ctrl); + + return 0; +} + +static struct vma_block *find_first_proper_block(struct rb_root *root, unsigned long size) +{ + struct rb_node *node = root->rb_node; + + while (node) { + struct vma_block *block = to_vma_block(node); + + if (subtree_max_size(block->rb_node.rb_left) >= size) { + node = block->rb_node.rb_left; + continue; + } + + if (block->size >= size) + return block; + + if (subtree_max_size(block->rb_node.rb_right) >= size) + node = block->rb_node.rb_right; + else + return NULL; + } + + return NULL; +} + +static long vma_alloc_block(struct rb_root *root, unsigned long size) +{ + long start; + struct vma_block *block = NULL; + + block = find_first_proper_block(root, size); + if (block == NULL) + return -ENOSPC; + + start = block->start; + if (block->size == size) { + rb_erase_augmented(&block->rb_node, root, &vma_block_subtree_max_size_cb); + kfree(block); + } else { + block->start += size; + block->size -= size; + block_update_subtree_max_size(block); + } + + return start; +} + +static int vma_algo_block_alloc(struct xshm_pool *xp, struct xshm_block *blk) +{ + long offset; + unsigned long real_size; + struct vma_ctrl *ctrl = xp->private; + + if (!blk->alloc_size) { + pr_err("alloc size invalid\n"); + return -EINVAL; + } + + real_size = ALIGN(blk->alloc_size, XSHMEM_VMA_ALIGN); + if (real_size < blk->alloc_size) + return -EOVERFLOW; + + if (real_size > ctrl->free_size) + return -ENOSPC; + + offset = vma_alloc_block(&ctrl->free_block_root, real_size); + if (offset < 0) { + pr_err("vma_alloc_block failed, %ld\n", offset); + return (int)offset; + } + + ctrl->free_size -= real_size; + ctrl->alloc_block_cnt++; + + blk->real_size = real_size; + blk->offset = offset; + + return 0; +} + +static struct vma_block *prev_block(struct rb_node *parent, struct rb_node **link) +{ + if (parent == NULL) + return NULL; + + if (link == &parent->rb_right) + return to_vma_block(parent); + else + /* the prev node should always exist */ + return to_vma_block(rb_prev(parent)); +} + +static struct vma_block *next_block(struct rb_node *parent, struct rb_node **link) +{ + if (parent == NULL) + return NULL; + + if (link == &parent->rb_left) + return to_vma_block(parent); + else + /* the next node should always exist */ + return to_vma_block(rb_next(parent)); +} + +/* two intervals overlapped ? [l1, h1), [l2, h2) */ +#define is_overlap(l1, h1, l2, h2) (((l1) < (h2)) && ((l2) < (h1))) + +static int vma_free_block(struct rb_root *root, unsigned long start, unsigned long size) +{ + bool merged = false; + struct vma_block *block = NULL, *prev = NULL; + struct rb_node *parent = NULL; + struct rb_node **link = &root->rb_node; + + while (*link) { + parent = *link; + block = to_vma_block(*link); + + if (start < block->start) + link = &parent->rb_left; + else if (start > block->start) + link = &parent->rb_right; + else { + pr_err("double free a block\n"); + return -EFAULT; + } + } + + prev = prev_block(parent, link); + if (prev) { + if (prev->start + prev->size == start) { + prev->size += size; + block_update_subtree_max_size(prev); + merged = true; + } else if (is_overlap(start, start + size, prev->start, prev->start + prev->size)) { + pr_err("prev-node overlap detected\n"); + return -EINVAL; + } + } + + block = next_block(parent, link); + if (block) { + if (start + size == block->start) { + if (merged) { + rb_erase_augmented(&block->rb_node, root, &vma_block_subtree_max_size_cb); + prev->size += block->size; + kfree(block); + block = prev; + } else { + block->start -= size; + block->size += size; + } + + block_update_subtree_max_size(block); + merged = true; + } else if (is_overlap(start, start + size, block->start, block->start + block->size)) { + pr_err("next-node overlap detected\n"); + return -EINVAL; + } + } + + if (!merged) { + block = kmalloc(sizeof(*block), GFP_KERNEL); + if (unlikely(block == NULL)) { + pr_err("alloc new free block memroy failed\n"); + return -ENOMEM; + } + + block->start = start; + block->size = size; + block->subtree_max_size = size; + + rb_link_node(&block->rb_node, parent, link); + rb_insert_augmented(&block->rb_node, root, &vma_block_subtree_max_size_cb); + } + + return 0; +} + +static int vma_algo_block_free(struct xshm_pool *xp, struct xshm_block *blk) +{ + int ret; + struct vma_ctrl *ctrl = xp->private; + + ret = vma_free_block(&ctrl->free_block_root, blk->offset, blk->real_size); + + ctrl->alloc_block_cnt--; + ctrl->free_size += blk->real_size; + + return ret; +} + +static void vma_algo_pool_show(struct xshm_pool *xp, struct seq_file *seq) +{ + struct vma_ctrl *ctrl = xp->private; + + seq_printf(seq, " total_size: %#lx, free_size: %#lx, alloc_block_cnt: %ld\n", + ctrl->total_size, ctrl->free_size, ctrl->alloc_block_cnt); +} + +struct xshm_pool_algo vma_algo = { + .num = XSHMEM_ALGO_VMA, + .name = "vma_algo", + .xshm_pool_same = vma_algo_pool_same, + .xshm_pool_init = vma_algo_pool_init, + .xshm_pool_free = vma_algo_pool_free, + .xshm_pool_show = vma_algo_pool_show, + .xshm_block_alloc = vma_algo_block_alloc, + .xshm_block_free = vma_algo_block_free, +};