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

[Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>]

---
 Config.uk                                          |  20 +++
 Makefile.uk                                        |  77 ++++++++++
 README.md                                          |  12 ++
 glue.c                                             |  75 ++++++++++
 include/uk/tlsf.h                                  |  48 +++++++
 main-tree.patch                                    |  42 ++++++
 ...onfig-vars-and-parametrize-tlsf-interface.patch | 160 +++++++++++++++++++++
 7 files changed, 434 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..d4eb43b
--- /dev/null
+++ b/glue.c
@@ -0,0 +1,75 @@
+/* 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;
+
+       /* 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);
+
+       size_t 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..c33f828
--- /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 __UKTLSF_H__
+#define __UKTLSF_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 /* __UKTLSF_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
-- 
2.7.4