[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [UNIKRAFT PATCH v5 2/5] lib/ukallocpool: LIFO pool implementation



All good.

Reviewed-by: Razvan Deaconescu <razvan.deaconescu@xxxxxxxxx>

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.
>
> Signed-off-by: Simon Kuenzer <simon.kuenzer@xxxxxxxxx>
> ---
>  lib/ukallocpool/Makefile.uk            |   2 +
>  lib/ukallocpool/exportsyms.uk          |   5 +
>  lib/ukallocpool/include/uk/allocpool.h | 113 +++++++++++++++
>  lib/ukallocpool/pool.c                 | 186 +++++++++++++++++++++++++
>  4 files changed, 306 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..94f487de
> --- /dev/null
> +++ b/lib/ukallocpool/include/uk/allocpool.h
> @@ -0,0 +1,113 @@
> +/* 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.
> + * @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..b6839b68
> --- /dev/null
> +++ b/lib/ukallocpool/pool.c
> @@ -0,0 +1,186 @@
> +/* 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;
> +     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));
> +
> +     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;
> +}



 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.