Re: [UNIKRAFT/LIBTLSF PATCH v2] Initial port of TLSF to Unikraft

[Razvan Deaconescu <razvan.deaconescu@xxxxxxxxx>]

Hi, Hugo.

It works, I tested on KVM and linuxu.

I only have the comment I made for libtinyalloc:
---
When selecting tinyalloc in the configuration screen, the malloc
compatibility interface should also be automatically selected. It's not
obvious it has to be selected and one may miss it.
---

Other than that, all good.

Razvan

Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx> writes:
> Signed-off-by: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
> ---
>  Config.uk                                          |  20 +++
>  Makefile.uk                                        |  77 ++++++++++
>  README.md                                          |  12 ++
>  glue.c                                             |  77 ++++++++++
>  include/uk/tlsf.h                                  |  48 +++++++
>  main-tree.patch                                    |  42 ++++++
>  ...onfig-vars-and-parametrize-tlsf-interface.patch | 160 
> +++++++++++++++++++++
>  7 files changed, 436 insertions(+)
>  create mode 100644 Config.uk
>  create mode 100644 Makefile.uk
>  create mode 100644 README.md
>  create mode 100644 glue.c
>  create mode 100644 include/uk/tlsf.h
>  create mode 100644 main-tree.patch
>  create mode 100644 patches/config-vars-and-parametrize-tlsf-interface.patch
>
> diff --git a/Config.uk b/Config.uk
> new file mode 100644
> index 0000000..29732d0
> --- /dev/null
> +++ b/Config.uk
> @@ -0,0 +1,20 @@
> +menuconfig LIBTLSF
> +        bool "TLSF - real-time dynamic memory allocator"
> +        select LIBUKALLOC_IFMALLOC
> +        default n
> +
> +if LIBTLSF
> +     config TLSF_LOG2_SLI
> +             int "log2 of second level index (SLI)"
> +             default 5
> +             help
> +                     The Second Level Index subdivides linearily the first 
> level lists.
> +
> +                     The SLI has to be a power of two and is here 
> represented as log2
> +                     of the number of second level divisions.
> +
> +                     For instance, TLSF_LOG2_SLI = 5 implies 32 second level 
> divisions.
> +
> +                     Higher values of SLI imply less fragmentation, at the 
> cost of an
> +                     increased space overhead of metadata.
> +endif
> diff --git a/Makefile.uk b/Makefile.uk
> new file mode 100644
> index 0000000..373181e
> --- /dev/null
> +++ b/Makefile.uk
> @@ -0,0 +1,77 @@
> +#  libtlsf Makefile.uk
> +#
> +#  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.
> +
> +################################################################################
> +# Library registration
> +################################################################################
> +$(eval $(call addlib_s,libtlsf,$(CONFIG_LIBTLSF)))
> +
> +################################################################################
> +# Sources
> +################################################################################
> +LIBTLSF_VERSION=2.4.6
> +LIBTLSF_URL=http://wks.gii.upv.es/tlsf/files/src/TLSF-$(LIBTLSF_VERSION).tbz2
> +LIBTLSF_DIR=TLSF-$(LIBTLSF_VERSION)
> +
> +LIBTLSF_PATCHDIR=$(LIBTLSF_BASE)/patches
> +$(eval $(call fetch,libtlsf,$(LIBTLSF_URL),TLSF-$(LIBTLSF_VERSION).tbz2))
> +$(eval $(call patch,libtlsf,$(LIBTLSF_PATCHDIR),$(LIBTLSF_DIR)))
> +
> +################################################################################
> +# Helpers
> +################################################################################
> +LIBTLSF=$(LIBTLSF_ORIGIN)/$(LIBTLSF_DIR)
> +
> +################################################################################
> +# Library includes
> +################################################################################
> +
> +CINCLUDES-$(CONFIG_LIBTLSF) +=       -I$(LIBTLSF_BASE)               \
> +                             -I$(LIBTLSF_BASE)/include       \
> +                             -I$(LIBTLSF)/src
> +
> +################################################################################
> +# Global flags
> +################################################################################
> +
> +# no locks, no sbrk, no mmap
> +CFLAGS-$(CONFIG_LIBTLSF) +=  -DTLSF_USE_LOCKS=0 -DUSE_MMAP=0 -DUSE_SBRK=0
> +
> +################################################################################
> +# Glue code
> +################################################################################
> +LIBTLSF_SRCS-y += $(LIBTLSF_BASE)/glue.c
> +
> +################################################################################
> +# Sources
> +################################################################################
> +LIBTLSF_SRCS-y += $(LIBTLSF)/src/tlsf.c
> diff --git a/README.md b/README.md
> new file mode 100644
> index 0000000..2e665a3
> --- /dev/null
> +++ b/README.md
> @@ -0,0 +1,12 @@
> +TLSF for Unikraft
> +=================
> +
> +This is the port of the TLSF [0] general-purpose memory allocator for 
> Unikraft
> +as an external library.
> +
> +How to use this allocator in your unikernel application:
> +
> +- apply main-tree.patch to the main tree
> +- select "TLSF" in `ukboot > Default memory allocator`
> +
> +[0] http://www.gii.upv.es/tlsf/
> diff --git a/glue.c b/glue.c
> new file mode 100644
> index 0000000..8becfe9
> --- /dev/null
> +++ b/glue.c
> @@ -0,0 +1,77 @@
> +/* 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.
> + */
> +
> +#include <uk/tlsf.h>
> +#include <uk/alloc_impl.h>
> +#include <tlsf.h>
> +
> +/* malloc interface */
> +
> +static void *uk_tlsf_malloc(struct uk_alloc *a, size_t size)
> +{
> +     return tlsf_malloc(size, (void *)((uintptr_t) a +
> +                                     sizeof(struct uk_alloc)));
> +}
> +
> +static void uk_tlsf_free(struct uk_alloc *a, void *ptr)
> +{
> +     tlsf_free(ptr, (void *)((uintptr_t) a + sizeof(struct uk_alloc)));
> +}
> +
> +/* initialization */
> +
> +struct uk_alloc *uk_tlsf_init(void *base, size_t len)
> +{
> +     struct uk_alloc *a;
> +     size_t res;
> +
> +     /* enough space for allocator available? */
> +     if (sizeof(*a) > len) {
> +             uk_pr_err("Not enough space for allocator: %" __PRIsz
> +                       " B required but only %" __PRIuptr" B usable\n",
> +                       sizeof(*a), len);
> +             return NULL;
> +     }
> +
> +     /* store allocator metadata on the heap, just before the memory pool */
> +     a = (struct uk_alloc *)base;
> +     uk_pr_info("Initialize tlsf allocator @ 0x%" __PRIuptr ", len %"
> +                     __PRIsz"\n", (uintptr_t)a, len);
> +
> +     res = init_memory_pool(len - sizeof(*a), base + sizeof(*a));
> +     if (res == (size_t)-1)
> +             return NULL;
> +
> +     uk_alloc_init_malloc_ifmalloc(a, uk_tlsf_malloc, uk_tlsf_free, NULL);
> +
> +     return a;
> +}
> diff --git a/include/uk/tlsf.h b/include/uk/tlsf.h
> new file mode 100644
> index 0000000..3e3482a
> --- /dev/null
> +++ b/include/uk/tlsf.h
> @@ -0,0 +1,48 @@
> +/* 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 __LIBTLSF_H__
> +#define __LIBTLSF_H__
> +
> +#include <uk/alloc.h>
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +struct uk_alloc *uk_tlsf_init(void *base, size_t len);
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* __LIBTLSF_H__ */
> diff --git a/main-tree.patch b/main-tree.patch
> new file mode 100644
> index 0000000..ca66278
> --- /dev/null
> +++ b/main-tree.patch
> @@ -0,0 +1,42 @@
> +From: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
> +Subject: Add TLSF entry to the menuconfig and initialize it
> +diff --git a/lib/ukboot/Config.uk b/lib/ukboot/Config.uk
> +index a888bc1c..b79b370e 100644
> +--- a/lib/ukboot/Config.uk
> ++++ b/lib/ukboot/Config.uk
> +@@ -32,6 +32,13 @@ if LIBUKBOOT
> +               Satisfy allocation as fast as possible. No support for free().
> +               Refer to help in ukallocregion for more information.
> + 
> ++            config LIBUKBOOT_INITTLSF
> ++            bool "TLSF"
> ++            select LIBTLSF
> ++            help
> ++              Real-time allocator. Bounded fragmentation, allocation, and
> ++              deallocation.
> ++
> +             config LIBUKBOOT_NOALLOC
> +             bool "No memory allocator"
> + 
> +diff --git a/lib/ukboot/boot.c b/lib/ukboot/boot.c
> +index 4e749aa5..37aafd70 100644
> +--- a/lib/ukboot/boot.c
> ++++ b/lib/ukboot/boot.c
> +@@ -45,6 +45,8 @@
> + #include <uk/allocbbuddy.h>
> + #elif CONFIG_LIBUKBOOT_INITREGION
> + #include <uk/allocregion.h>
> ++#elif CONFIG_LIBUKBOOT_INITTLSF
> ++#include <uk/tlsf.h>
> + #endif
> + #if CONFIG_LIBUKSCHED
> + #include <uk/sched.h>
> +@@ -233,6 +235,8 @@ void ukplat_entry(int argc, char *argv[])
> +                     a = uk_allocbbuddy_init(md.base, md.len);
> + #elif CONFIG_LIBUKBOOT_INITREGION
> +                     a = uk_allocregion_init(md.base, md.len);
> ++#elif CONFIG_LIBUKBOOT_INITTLSF
> ++                    a = uk_tlsf_init(md.base, md.len);
> + #endif
> +             } else {
> +                     uk_alloc_addmem(a, md.base, md.len);
> diff --git a/patches/config-vars-and-parametrize-tlsf-interface.patch 
> b/patches/config-vars-and-parametrize-tlsf-interface.patch
> new file mode 100644
> index 0000000..e77cf56
> --- /dev/null
> +++ b/patches/config-vars-and-parametrize-tlsf-interface.patch
> @@ -0,0 +1,160 @@
> +From: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
> +Subject: Adapt TLSF interface to Unikraft
> + - expose MAX_LOG2_SLI, users might want to modify this
> + - do not rely on static metadata; pass it as argument to the allocation
> +   interface
> +diff -urNp TLSF-2.4.6/src/tlsf.c TLSF-patched/src/tlsf.c
> +--- TLSF-2.4.6/src/tlsf.c    2009-10-06 11:25:15.000000000 +0200
> ++++ TLSF-patched/src/tlsf.c  2020-06-26 13:49:03.231027270 +0200
> +@@ -74,7 +74,6 @@
> + #define     USE_SBRK        (0)
> + #endif
> + 
> +-
> + #if TLSF_USE_LOCKS
> + #include "target.h"
> + #else
> +@@ -129,7 +128,7 @@
> + #define BLOCK_ALIGN (sizeof(void *) * 2)
> + 
> + #define MAX_FLI             (30)
> +-#define MAX_LOG2_SLI        (5)
> ++#define MAX_LOG2_SLI        CONFIG_TLSF_LOG2_SLI
> + #define MAX_SLI             (1 << MAX_LOG2_SLI)     /* MAX_SLI = 
> 2^MAX_LOG2_SLI */
> + 
> + #define FLI_OFFSET  (6)     /* tlsf structure just will manage blocks 
> bigger */
> +@@ -451,8 +450,6 @@ static __inline__ bhdr_t *process_area(v
> + /******************** Begin of the allocator code *****************/
> + /******************************************************************/
> + 
> +-static char *mp = NULL;         /* Default memory pool. */
> +-
> + /******************************************************************/
> + size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
> + {
> +@@ -472,13 +469,10 @@ size_t init_memory_pool(size_t mem_pool_
> +     tlsf = (tlsf_t *) mem_pool;
> +     /* Check if already initialised */
> +     if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
> +-        mp = mem_pool;
> +-        b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
> ++        b = GET_NEXT_BLOCK(mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t)));
> +         return b->size & BLOCK_SIZE;
> +     }
> + 
> +-    mp = mem_pool;
> +-
> +     /* Zeroing the memory pool */
> +     memset(mem_pool, 0, sizeof(tlsf_t));
> + 
> +@@ -615,13 +609,13 @@ void destroy_memory_pool(void *mem_pool)
> + 
> + 
> + /******************************************************************/
> +-void *tlsf_malloc(size_t size)
> ++void *tlsf_malloc(size_t size, void *mem_pool)
> + {
> + /******************************************************************/
> +     void *ret;
> + 
> + #if USE_MMAP || USE_SBRK
> +-    if (!mp) {
> ++    if (!mem_pool) {
> +         size_t area_size;
> +         void *area;
> + 
> +@@ -634,60 +628,60 @@ void *tlsf_malloc(size_t size)
> +     }
> + #endif
> + 
> +-    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +-    ret = malloc_ex(size, mp);
> ++    ret = malloc_ex(size, mem_pool);
> + 
> +-    TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_RELEASE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +     return ret;
> + }
> + 
> + /******************************************************************/
> +-void tlsf_free(void *ptr)
> ++void tlsf_free(void *ptr, void *mem_pool)
> + {
> + /******************************************************************/
> + 
> +-    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +-    free_ex(ptr, mp);
> ++    free_ex(ptr, mem_pool);
> + 
> +-    TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_RELEASE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> + }
> + 
> + /******************************************************************/
> +-void *tlsf_realloc(void *ptr, size_t size)
> ++void *tlsf_realloc(void *ptr, size_t size, void *mem_pool)
> + {
> + /******************************************************************/
> +     void *ret;
> + 
> + #if USE_MMAP || USE_SBRK
> +-    if (!mp) {
> +-            return tlsf_malloc(size);
> ++    if (!mem_pool) {
> ++            return tlsf_malloc(size, mem_pool);
> +     }
> + #endif
> + 
> +-    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +-    ret = realloc_ex(ptr, size, mp);
> ++    ret = realloc_ex(ptr, size, mem_pool);
> + 
> +-    TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_RELEASE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +     return ret;
> + }
> + 
> + /******************************************************************/
> +-void *tlsf_calloc(size_t nelem, size_t elem_size)
> ++void *tlsf_calloc(size_t nelem, size_t elem_size, void *mem_pool)
> + {
> + /******************************************************************/
> +     void *ret;
> + 
> +-    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_ACQUIRE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +-    ret = calloc_ex(nelem, elem_size, mp);
> ++    ret = calloc_ex(nelem, elem_size, mem_pool);
> + 
> +-    TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
> ++    TLSF_RELEASE_LOCK(&((tlsf_t *)mem_pool)->lock);
> + 
> +     return ret;
> + }
> +diff -urNp TLSF-2.4.6/src/tlsf.h TLSF-patched/src/tlsf.h
> +--- TLSF-2.4.6/src/tlsf.h    2009-10-06 11:25:22.000000000 +0200
> ++++ TLSF-patched/src/tlsf.h  2020-06-26 09:24:01.159699745 +0200
> +@@ -31,9 +31,9 @@ extern void free_ex(void *, void *);
> + extern void *realloc_ex(void *, size_t, void *);
> + extern void *calloc_ex(size_t, size_t, void *);
> + 
> +-extern void *tlsf_malloc(size_t size);
> +-extern void tlsf_free(void *ptr);
> +-extern void *tlsf_realloc(void *ptr, size_t size);
> +-extern void *tlsf_calloc(size_t nelem, size_t elem_size);
> ++extern void *tlsf_malloc(size_t size, void *);
> ++extern void tlsf_free(void *ptr, void *);
> ++extern void *tlsf_realloc(void *ptr, size_t size, void *);
> ++extern void *tlsf_calloc(size_t nelem, size_t elem_size, void *);
> + 
> + #endif