[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



 


Rackspace

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