[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 |