[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [UNIKRAFT PATCH v4 2/5] lib/ukallocpool: LIFO pool implementation
Initial implementation of a memory pool (same-sized and fixed-sized object allocator) following LIFO principle by using a single list to keep track of free objects. LIFO is chosen to potentially better utilize hardware caches. Signed-off-by: Simon Kuenzer <simon.kuenzer@xxxxxxxxx> --- lib/ukallocpool/Makefile.uk | 2 + lib/ukallocpool/exportsyms.uk | 5 + lib/ukallocpool/include/uk/allocpool.h | 117 +++++++++++++++ lib/ukallocpool/pool.c | 188 +++++++++++++++++++++++++ 4 files changed, 312 insertions(+) create mode 100644 lib/ukallocpool/exportsyms.uk create mode 100644 lib/ukallocpool/include/uk/allocpool.h create mode 100644 lib/ukallocpool/pool.c diff --git a/lib/ukallocpool/Makefile.uk b/lib/ukallocpool/Makefile.uk index c71c9764..63c24dc1 100644 --- a/lib/ukallocpool/Makefile.uk +++ b/lib/ukallocpool/Makefile.uk @@ -2,3 +2,5 @@ $(eval $(call addlib_s,libukallocpool,$(CONFIG_LIBUKALLOCPOOL))) CINCLUDES-$(CONFIG_LIBUKALLOCPOOL) += -I$(LIBUKALLOCPOOL_BASE)/include CXXINCLUDES-$(CONFIG_LIBUKALLOCPOOL) += -I$(LIBUKALLOCPOOL_BASE)/include + +LIBUKALLOCPOOL_SRCS-y += $(LIBUKALLOCPOOL_BASE)/pool.c diff --git a/lib/ukallocpool/exportsyms.uk b/lib/ukallocpool/exportsyms.uk new file mode 100644 index 00000000..9d47d615 --- /dev/null +++ b/lib/ukallocpool/exportsyms.uk @@ -0,0 +1,5 @@ +uk_allocpool_init +uk_allocpool_availcount +uk_allocpool_objlen +uk_allocpool_take +uk_allocpool_return diff --git a/lib/ukallocpool/include/uk/allocpool.h b/lib/ukallocpool/include/uk/allocpool.h new file mode 100644 index 00000000..60a47482 --- /dev/null +++ b/lib/ukallocpool/include/uk/allocpool.h @@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: BSD-3-Clause */ +/* + * Simple memory pool using LIFO principle + * + * Authors: Simon Kuenzer <simon.kuenzer@xxxxxxxxx> + * + * + * Copyright (c) 2020, NEC Laboratories Europe GmbH, NEC Corporation, + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the copyright holder nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __LIBUKALLOCPOOL_H__ +#define __LIBUKALLOCPOOL_H__ + +#include <uk/alloc.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef void (*uk_allocpool_obj_init_t)(void *obj, size_t len, void *cookie); + +struct uk_allocpool; + +/** + * Initializes a memory pool on a given memory range. + * + * @param base + * Base address of memory range + * @param len + * Length of memory range (bytes) + * @param obj_len + * Size of one object (bytes) + * @param obj_align + * Alignment requirement for each pool object + * @param obj_init + * Function pointer to object initialization + * @param obj_init_cookie + * Cookie that is hand-over to object initialization + * @return + * - (NULL): Not enough memory for pool + * - pointer to initializes pool + */ +struct uk_allocpool *uk_allocpool_init(void *base, size_t len, + size_t obj_len, size_t obj_align); + +/** + * Return the number of current available (free) objects + * + * @param p + * Pointer to memory pool. + * @return + * Number of free objects in the pool. + */ +unsigned int uk_allocpool_availcount(struct uk_allocpool *p); + +/** + * Return the size of an object + * + * @param p + * Pointer to memory pool. + * @return + * Size of an object + */ +size_t uk_allocpool_objlen(struct uk_allocpool *p); + +/** + * Get one object from a pool + * + * @param p + * Pointer to memory pool. + * @return + * - (NULL): No more free objects available + * - Pointer to object. + */ +void *uk_allocpool_take(struct uk_allocpool *p); + +/** + * Return one object back to a pool + * + * @param p + * Pointer to memory pool. + * @param obj + * Pointer to object that should be returned. + */ +void uk_allocpool_return(struct uk_allocpool *p, void *obj); + +#ifdef __cplusplus +} +#endif + +#endif /* __LIBUKALLOCPOOL_H__ */ diff --git a/lib/ukallocpool/pool.c b/lib/ukallocpool/pool.c new file mode 100644 index 00000000..5d5ddbde --- /dev/null +++ b/lib/ukallocpool/pool.c @@ -0,0 +1,188 @@ +/* SPDX-License-Identifier: BSD-3-Clause */ +/* + * Simple memory pool using LIFO principle + * + * Authors: Simon Kuenzer <simon.kuenzer@xxxxxxxxx> + * + * + * Copyright (c) 2020, NEC Laboratories Europe GmbH, NEC Corporation, + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the copyright holder nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <uk/essentials.h> +#include <uk/alloc_impl.h> +#include <uk/allocpool.h> +#include <uk/list.h> +#include <string.h> +#include <stddef.h> +#include <stdint.h> +#include <sys/types.h> +#include <errno.h> + +/* + * POOL: MEMORY LAYOUT + * + * ++---------------------++ + * || struct uk_allocpool || + * || || + * ++---------------------++ + * | // padding // | + * +=======================+ + * | OBJECT 1 | + * +=======================+ + * | OBJECT 2 | + * +=======================+ + * | OBJECT 3 | + * +=======================+ + * | ... | + * v v + */ + +#define MIN_OBJ_ALIGN sizeof(void *) +#define MIN_OBJ_LEN sizeof(struct uk_list_head) + +struct uk_allocpool { + struct uk_list_head free_obj; + unsigned int free_obj_count; + + size_t obj_align; + size_t obj_len; + unsigned int obj_count; +}; + +struct free_obj { + struct uk_list_head list; +}; + +static inline void _prepend_free_obj(struct uk_allocpool *p, void *obj) +{ + struct uk_list_head *entry; + + UK_ASSERT(p); + UK_ASSERT(obj); + UK_ASSERT(p->free_obj_count < p->obj_count); + + entry = &((struct free_obj *) obj)->list; + uk_list_add(entry, &p->free_obj); + p->free_obj_count++; +} + +static inline void *_take_free_obj(struct uk_allocpool *p) +{ + struct free_obj *obj; + + UK_ASSERT(p); + UK_ASSERT(p->free_obj_count > 0); + + /* get object from list head */ + obj = uk_list_first_entry(&p->free_obj, struct free_obj, list); + uk_list_del(&obj->list); + p->free_obj_count--; + return (void *) obj; +} + +void *uk_allocpool_take(struct uk_allocpool *p) +{ + UK_ASSERT(p); + + if (unlikely(uk_list_empty(&p->free_obj))) + return NULL; + + return _take_free_obj(p); +} + +void uk_allocpool_return(struct uk_allocpool *p, void *obj) +{ + UK_ASSERT(p); + + _prepend_free_obj(p, obj); +} + +unsigned int uk_allocpool_availcount(struct uk_allocpool *p) +{ + return p->free_obj_count; +} + +size_t uk_allocpool_objlen(struct uk_allocpool *p) +{ + return p->obj_len; +} + +struct uk_allocpool *uk_allocpool_init(void *base, size_t len, + size_t obj_len, size_t obj_align) +{ + struct uk_allocpool *p; + struct uk_alloc *a; + size_t obj_alen; + size_t left; + void *obj_ptr; + + UK_ASSERT(POWER_OF_2(obj_align)); + + if (!base || sizeof(struct uk_allocpool) > len) { + errno = ENOSPC; + return NULL; + } + + /* apply minimum requirements */ + obj_len = MAX(obj_len, MIN_OBJ_LEN); + obj_align = MAX(obj_align, MIN_OBJ_ALIGN); + + p = (struct uk_allocpool *) base; + memset(p, 0, sizeof(*p)); + a = uk_allocpool2alloc(p); + + obj_alen = ALIGN_UP(obj_len, obj_align); + obj_ptr = (void *) ALIGN_UP((uintptr_t) base + sizeof(*p), + obj_align); + if ((uintptr_t) obj_ptr > (uintptr_t) base + len) { + uk_pr_debug("%p: Empty pool: Not enough space for allocating objects\n", + p); + goto out; + } + + left = len - ((uintptr_t) obj_ptr - (uintptr_t) base); + + p->obj_count = 0; + p->free_obj_count = 0; + UK_INIT_LIST_HEAD(&p->free_obj); + while (left >= obj_alen) { + ++p->obj_count; + _prepend_free_obj(p, obj_ptr); + obj_ptr = (void *) ((uintptr_t) obj_ptr + obj_alen); + left -= obj_alen; + } + +out: + p->obj_len = obj_alen; + p->obj_align = obj_align; + + uk_pr_debug("%p: Pool created (%"__PRIsz" B): %u objs of %"__PRIsz" B, aligned to %"__PRIsz" B\n", + p, len, p->obj_count, p->obj_len, p->obj_align); + return p; +} -- 2.20.1
|
![]() |
Lists.xenproject.org is hosted with RackSpace, monitoring our |