|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [UNIKRAFT PATCH v4 2/5] lib/ukallocpool: LIFO pool implementation
Simon Kuenzer <simon.kuenzer@xxxxxxxxx> writes:
> 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.
See inline. I'll reply with another e-mail for a more in-depth review.
> 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
> + */
There are two extra arguments in the function-level comment: obj_init
and obj_init_cookie.
> +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;
> +}
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |