|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [UNIKRAFT PATCH 1/2] lib/ukallocregion: add region-based allocator
Hi Simon,
it looks like region.c is missing an #include (inline).
We might want to fix this with a v2 after your review (or while
upstreaming).
regards,
Hugo
On Mon, 2020-06-22 at 16:23 +0200, 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 | 13 +++
> lib/ukallocregion/Makefile.uk | 6 +
> lib/ukallocregion/exportsyms.uk | 1 +
> lib/ukallocregion/include/uk/allocregion.h | 49 +++++++++
> lib/ukallocregion/region.c | 169
> +++++++++++++++++++++++++++++
> 6 files changed, 239 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..0bbc69f
> --- /dev/null
> +++ b/lib/ukallocregion/Config.uk
> @@ -0,0 +1,13 @@
> +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. Note that this allocator does not provide optimal
> locality of
> + reference.
> 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..1fc12db
> --- /dev/null
> +++ b/lib/ukallocregion/include/uk/allocregion.h
> @@ -0,0 +1,49 @@
> +/* SPDX-License-Identifier: BSD-3-Clause */
> +/*
> + * Authors: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
> + *
> + * Copyright (c) 2020, NEC Europe Ltd., 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..6760b4c
> --- /dev/null
> +++ b/lib/ukallocregion/region.c
> @@ -0,0 +1,169 @@
> +/* SPDX-License-Identifier: BSD-3-Clause */
> +/*
> + * Authors: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
> + *
> + * Copyright (c) 2020, NEC Europe Ltd., 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()
#include <limits.h> is needed for __PAGE_SIZE.
> +
> +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
> + */
> + newbase = (void *) ALIGN_UP(((uintptr_t) b->heap_base +
> size),
> + (uintptr_t) sizeof(void *));
> + prevbase = b->heap_base;
> +
> + 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)
> + 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;
> +}
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |