[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [UNIKRAFT PATCH v2 1/2] lib/ukallocregion: add region-based allocator
Hi Hugo,
two comment to malloc and posix_memalign. Otherwise, the patch is fine.
Thanks,
Simon
On 29.07.20 10:55, Hugo Lefeuvre wrote:
Add ukallocregion, a minimalist region-based allocator.
Note that deallocation is not supported. This makes sense because regions
only allow for deallocation at region-granularity. In our case, this would
imply the freeing of the entire heap, which is generally not possible.
Obviously, the lack of deallocation support makes ukallocregion a fairly
bad general-purpose allocator. This allocator is interesting in that it
offers maximum speed allocation and deallocation (bounded O(1), no
bookkeeping). It can be used as a baseline for measurements (e.g., boot
time) or as a first-level allocator in a nested context.
Refer to Gay & Aiken, `Memory management with explicit regions' (PLDI'98)
for an introduction to region-based memory management.
Signed-off-by: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
---
lib/Makefile.uk | 1 +
lib/ukallocregion/Config.uk | 12 ++
lib/ukallocregion/Makefile.uk | 6 +
lib/ukallocregion/exportsyms.uk | 1 +
lib/ukallocregion/include/uk/allocregion.h | 50 +++++++++
lib/ukallocregion/region.c | 172 +++++++++++++++++++++++++++++
6 files changed, 242 insertions(+)
create mode 100644 lib/ukallocregion/Config.uk
create mode 100644 lib/ukallocregion/Makefile.uk
create mode 100644 lib/ukallocregion/exportsyms.uk
create mode 100644 lib/ukallocregion/include/uk/allocregion.h
create mode 100644 lib/ukallocregion/region.c
diff --git a/lib/Makefile.uk b/lib/Makefile.uk
index aa7e730..1f223d2 100644
--- a/lib/Makefile.uk
+++ b/lib/Makefile.uk
@@ -14,6 +14,7 @@ $(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/uktimeconv))
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/nolibc))
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukalloc))
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukallocbbuddy))
+$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukallocregion))
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/uksched))
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukschedcoop))
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/fdt))
diff --git a/lib/ukallocregion/Config.uk b/lib/ukallocregion/Config.uk
new file mode 100644
index 0000000..0012677
--- /dev/null
+++ b/lib/ukallocregion/Config.uk
@@ -0,0 +1,12 @@
+config LIBUKALLOCREGION
+ bool "ukallocregion: Region-based allocator"
+ default n
+ select LIBNOLIBC if !HAVE_LIBC
+ select LIBUKDEBUG
+ select LIBUKALLOC
+ help
+ Satisfy allocations as fast as possible, without bookkeeping. No
+ support for free(): when the end of the allocation pool is reached,
+ the allocator runs out-of-memory. This allocator is useful for
+ experimentation, as baseline, or as first-level allocator in a nested
+ context.
diff --git a/lib/ukallocregion/Makefile.uk b/lib/ukallocregion/Makefile.uk
new file mode 100644
index 0000000..05a3d67
--- /dev/null
+++ b/lib/ukallocregion/Makefile.uk
@@ -0,0 +1,6 @@
+$(eval $(call addlib_s,libukallocregion,$(CONFIG_LIBUKALLOCREGION)))
+
+CINCLUDES-$(CONFIG_LIBUKALLOCREGION) += -I$(LIBUKALLOCREGION_BASE)/include
+CXXINCLUDES-$(CONFIG_LIBUKALLOCREGION) += -I$(LIBUKALLOCREGION_BASE)/include
+
+LIBUKALLOCREGION_SRCS-y += $(LIBUKALLOCREGION_BASE)/region.c
diff --git a/lib/ukallocregion/exportsyms.uk b/lib/ukallocregion/exportsyms.uk
new file mode 100644
index 0000000..481bc10
--- /dev/null
+++ b/lib/ukallocregion/exportsyms.uk
@@ -0,0 +1 @@
+uk_allocregion_init
diff --git a/lib/ukallocregion/include/uk/allocregion.h
b/lib/ukallocregion/include/uk/allocregion.h
new file mode 100644
index 0000000..863ef6c
--- /dev/null
+++ b/lib/ukallocregion/include/uk/allocregion.h
@@ -0,0 +1,50 @@
+/* SPDX-License-Identifier: BSD-3-Clause */
+/*
+ * Authors: Hugo Lefeuvre <hugo.lefeuvre@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 __LIBUKALLOCREGION_H__
+#define __LIBUKALLOCREGION_H__
+
+#include <uk/alloc.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* allocator initialization */
+struct uk_alloc *uk_allocregion_init(void *base, size_t len);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __LIBUKALLOCREGION_H__ */
diff --git a/lib/ukallocregion/region.c b/lib/ukallocregion/region.c
new file mode 100644
index 0000000..8d2baec
--- /dev/null
+++ b/lib/ukallocregion/region.c
@@ -0,0 +1,172 @@
+/* SPDX-License-Identifier: BSD-3-Clause */
+/*
+ * Authors: Hugo Lefeuvre <hugo.lefeuvre@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.
+ */
+
+/* ukallocregion is a minimalist region implementation.
+ *
+ * Note that deallocation is not supported. This makes sense because regions
+ * only allow for deallocation at region-granularity. In our case, this would
+ * imply the freeing of the entire heap, which is generally not possible.
+ *
+ * Obviously, the lack of deallocation support makes ukallocregion a fairly bad
+ * general-purpose allocator. This allocator is interesting in that it offers
+ * maximum speed allocation and deallocation (no bookkeeping). It can be used
as
+ * a baseline for measurements (e.g., boot time) or as a first-level allocator
+ * in a nested context.
+ *
+ * Refer to Gay & Aiken, `Memory management with explicit regions' (PLDI'98)
for
+ * an introduction to region-based memory management.
+ */
+
+#include <uk/allocregion.h>
+#include <uk/alloc_impl.h>
+#include <uk/page.h> /* round_pgup() */
+
+struct uk_allocregion {
+ void *heap_top;
+ void *heap_base;
+};
+
+void *uk_allocregion_malloc(struct uk_alloc *a, size_t size)
+{
+ struct uk_allocregion *b;
+ void *newbase, *prevbase;
+
+ UK_ASSERT(a != NULL);
+
+ b = (struct uk_allocregion *)&a->priv;
+
+ /* return aligned pointers: this is a requirement for some
+ * embedded systems archs, and more generally good for performance
+ */
Please check if there is space left when doing the alignment and return
NULL otherwise. I would actually change the rest of the function to the
follwing (I also call the variable now intptr, like you do with
posix_memalign;... less touching of struct fields):
/* ... */
intptr = ALIGN_UP(((uintptr_t) b->heap_base)
(uintptr_t) sizeof(void *));
if (intptr > b->heap_top
|| intptr + size > b->heap_top)
return NULL; /* ENOMEM */
b->heap_base = (void *) (intptr + size)
return intptr;
}
> + b->heap_base = (void *) ALIGN_UP(((uintptr_t) b->heap_base),
> + (uintptr_t) sizeof(void *));
+
+ prevbase = b->heap_base;
+ newbase = (void *) ((uintptr_t) b->heap_base + size);
+
+ UK_ASSERT(newbase >= b->heap_base);
+ UK_ASSERT(newbase <= b->heap_top);
+
+ b->heap_base = newbase;
+
+ return prevbase;
+}
+
+int uk_allocregion_posix_memalign(struct uk_alloc *a, void **memptr,
+ size_t align, size_t size)
+{
+ struct uk_allocregion *b;
+ uintptr_t intptr;
+
+ UK_ASSERT(a != NULL);
+
+ b = (struct uk_allocregion *)&a->priv;
+
+ /* align must be a power of two */
+ UK_ASSERT(((align - 1) & align) == 0);
+
+ /* align must be larger than pointer size */
+ UK_ASSERT((align % sizeof(void *)) == 0);
+
+ if (!size) {
+ *memptr = NULL;
+ return EINVAL;
+ }
+
+ intptr = ALIGN_UP((uintptr_t) b->heap_base, (uintptr_t) align);
+
+ if (intptr > (uintptr_t) b->heap_top)
This if condition should actually include the requested size:
if (intptr + size > (uintptr_t) b->heap_top
+ return ENOMEM; /* out-of-memory * > +
+ *memptr = (void *)intptr;
+ b->heap_base = (void *)(intptr + size);
+
+ return 0;
+}
+
+void uk_allocregion_free(struct uk_alloc *a __unused, void *ptr __unused)
+{
+ uk_pr_debug("%p: Releasing of memory is not supported by "
+ "ukallocregion\n", a);
+}
+
+int uk_allocregion_addmem(struct uk_alloc *a __unused, void *base __unused,
+ size_t size __unused)
+{
+ /* TODO: support multiple regions */
+ uk_pr_debug("%p: ukallocregion does not support multiple memory "
+ "regions\n", a);
+ return 0;
+}
+
+struct uk_alloc *uk_allocregion_init(void *base, size_t len)
+{
+ struct uk_alloc *a;
+ struct uk_allocregion *b;
+ size_t metalen = sizeof(*a) + sizeof(*b);
+
+ /* TODO: ukallocregion does not support multiple memory regions yet.
+ * Because of the multiboot layout, the first region might be a single
+ * page, so we simply ignore it.
+ */
+ if (len <= __PAGE_SIZE)
+ return NULL;
+
+ /* enough space for allocator available? */
+ if (metalen > len) {
+ uk_pr_err("Not enough space for allocator: %"__PRIsz
+ " B required but only %"__PRIuptr" B usable\n",
+ metalen, len);
+ return NULL;
+ }
+
+ /* store allocator metadata on the heap, just before the memory pool */
+ a = (struct uk_alloc *)base;
+ b = (struct uk_allocregion *)&a->priv;
+
+ uk_pr_info("Initialize allocregion allocator @ 0x%"
+ __PRIuptr ", len %"__PRIsz"\n", (uintptr_t)a, len);
+
+ b->heap_top = (void *)((uintptr_t) base + len);
+ b->heap_base = (void *)((uintptr_t) base + metalen);
+
+ /* use exclusively "compat" wrappers for calloc, realloc, memalign,
+ * palloc and pfree as those do not add additional metadata.
+ */
+ uk_alloc_init_malloc(a, uk_allocregion_malloc, uk_calloc_compat,
+ uk_realloc_compat, uk_allocregion_free,
+ uk_allocregion_posix_memalign,
+ uk_memalign_compat, NULL);
+
+ return a;
+}
|
