Re: [UNIKRAFT PATCH 1/2] lib/ukallocregion: add region-based allocator

[Simon Kuenzer <simon.kuenzer@xxxxxxxxx>]

Hi Hugo,

thanks a lot for your work. I have few comments inline. If you address 
them I am happy to take the allocator upstream. Really useful...
Thanks,

Simon

On 27.07.20 16:21, Hugo Lefeuvre wrote:
> Hi Simon,
>
> it looks like region.c is missing an #include (inline).
I think the problem should be actually fixed within page.h header. I 
sent out a patch for this. The page.h header should not use undefined 
things and should actually be self-contained and include its dependencies.
> 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"
Use a ":" instead of a "-". This is to make it inline with the other 
menu items. I am going to do it while upstreaming.
> > +       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.
I think the last sentence can be removed. It probably confused more than 
it helps. bbuddy is also not considering locality and it somehow also 
depends how you allocator is initialized.
> > 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.
Oh... this is an old header. It should say "NEC Laboratories Europe 
GmbH" instead of "NEC Europe Ltd.". Please check all your headers.
> > + *
> > + * 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()
checkpatch did not complain because of "//" comments? ;-)

> #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;
Hum, I was thinking a while how to solve the problem that prevbase can 
be unaligned (e.g., first malloc call or malloc call after 
posix_memalign). First I thought, posix_memalign and allocregion_init 
need to be adopted to leave heap_base always aligned. But actually, the 
easier way is to align prevbase instead of newbase (similar to 
posix_memalign). This way all three behave the same: They will leave 
b->heap_base (not unaligned. What do you think?
> > +
> > +       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;
> > +}