[UNIKRAFT/LIBTINYALLOC PATCH] Initial port of tinyalloc to Unikraft

[Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>]

Signed-off-by: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
---
 Config.uk                                          |  32 +++
 Makefile.uk                                        |  73 +++++
 glue.c                                             | 101 +++++++
 include/uk/tinyalloc.h                             |  48 ++++
 main-tree.patch                                    |  45 +++
 .../0001-do-not-store-heap-info-statically.patch   | 312 +++++++++++++++++++++
 6 files changed, 611 insertions(+)
 create mode 100644 Config.uk
 create mode 100644 Makefile.uk
 create mode 100644 glue.c
 create mode 100644 include/uk/tinyalloc.h
 create mode 100644 main-tree.patch
 create mode 100644 patches/0001-do-not-store-heap-info-statically.patch

diff --git a/Config.uk b/Config.uk
new file mode 100644
index 0000000..4b9d127
--- /dev/null
+++ b/Config.uk
@@ -0,0 +1,32 @@
+menuconfig LIBTINYALLOC
+          bool "tinyalloc - sequential fit, linked list based tiny allocator"
+          default y
+
+if LIBTINYALLOC
+       config LIBTINYALLOC_DISABLE_SPLIT
+               bool "Disable block splitting"
+               default n
+               help
+                       If splitting is enabled, split blocks according to split
+                       threshold.
+
+       config LIBTINYALLOC_DISABLE_COMPACT
+               bool "Disable block compaction"
+               default n
+               help
+                       If compaction is enabled, sort blocks into the free
+                       list, merge if appropriate. Otherwise blocks are just
+                       added as new head of the free list.
+
+       config LIBTINYALLOC_HEAP_BLOCKS
+               int "Number of available heap blocks"
+               default 2048
+
+       config LIBTINYALLOC_SPLIT_THRESH
+               int "Split threshold, in bytes"
+               default 16
+
+       config LIBTINYALLOC_ALIGNMENT
+               int "Standard allocation alignment, in bytes"
+               default 8
+endif
diff --git a/Makefile.uk b/Makefile.uk
new file mode 100644
index 0000000..21aa8fe
--- /dev/null
+++ b/Makefile.uk
@@ -0,0 +1,73 @@
+#  libtinyalloc Makefile.uc
+#
+#  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,libtinyalloc,$(CONFIG_LIBTINYALLOC)))
+
+################################################################################
+# Sources
+################################################################################
+LIBTINYALLOC_VERSION=96450f32d80fe7d23f6aa5426046143e57801bc4
+LIBTINYALLOC_URL=https://github.com/thi-ng/tinyalloc/archive/$(LIBTINYALLOC_VERSION).zip
+LIBTINYALLOC_DIR=tinyalloc-$(LIBTINYALLOC_VERSION)
+
+LIBTINYALLOC_PATCHDIR=$(LIBTINYALLOC_BASE)/patches
+$(eval $(call 
fetch,libtinyalloc,$(LIBTINYALLOC_URL),$(LIBTINYALLOC_VERSION).zip))
+$(eval $(call patch,libtinyalloc,$(LIBTINYALLOC_PATCHDIR),$(LIBTINYALLOC_DIR)))
+
+################################################################################
+# Helpers
+################################################################################
+LIBTINYALLOC=$(LIBTINYALLOC_ORIGIN)/$(LIBTINYALLOC_DIR)
+
+################################################################################
+# Library includes
+################################################################################
+CINCLUDES-$(CONFIG_LIBTINYALLOC) += -I$(LIBTINYALLOC_BASE)     \
+                                    -I$(LIBTINYALLOC_BASE)/include \
+                                   -I$(LIBTINYALLOC)
+
+################################################################################
+# Global flags
+################################################################################
+#LIBTINYALLOC_CFLAGS-y += -D_POSIX_SOURCE -D_GNU_SOURCE -D__GNU__
+
+################################################################################
+# Glue code
+################################################################################
+LIBTINYALLOC_SRCS-y += $(LIBTINYALLOC_BASE)/glue.c
+
+################################################################################
+# Sources
+################################################################################
+LIBTINYALLOC_SRCS-y += $(LIBTINYALLOC)/tinyalloc.c
diff --git a/glue.c b/glue.c
new file mode 100644
index 0000000..9266e92
--- /dev/null
+++ b/glue.c
@@ -0,0 +1,101 @@
+/* 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/tinyalloc.h>
+#include <uk/alloc_impl.h>
+#include <string.h> /* for memset */
+#include <tinyalloc.h>
+
+static void *uk_tinyalloc_malloc(struct uk_alloc *a, size_t size)
+{
+       struct tinyalloc *b;
+
+       b = (struct tinyalloc *)&a->priv;
+       return ta_alloc(b, size);
+}
+
+static void uk_tinyalloc_free(struct uk_alloc *a, void *ptr)
+{
+       struct tinyalloc *b;
+
+       b = (struct tinyalloc *)&a->priv;
+       ta_free(b, ptr);
+}
+
+/* initialization */
+
+struct uk_alloc *uk_tinyalloc_init(void *base, size_t len)
+{
+       struct uk_alloc *a;
+       struct tinyalloc *b;
+       size_t metalen;
+
+       /* TODO: This port 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;
+
+       /* Allocate space for allocator descriptor */
+       metalen = sizeof(*a) + sizeof(*b);
+
+       /* 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 tinyalloc *)&a->priv;
+       memset(a, 0, metalen);
+
+       uk_pr_info("Initialize tinyalloc allocator @ 0x%" __PRIuptr ", len %"
+                       __PRIsz"\n", (uintptr_t)a, len);
+
+       ta_init(b, base + metalen, base + len, CONFIG_LIBTINYALLOC_HEAP_BLOCKS,
+               CONFIG_LIBTINYALLOC_SPLIT_THRESH,
+               CONFIG_LIBTINYALLOC_ALIGNMENT);
+
+       if (!a) {
+               uk_pr_err("Failed to allocate memory for uk_alloc 
structure!\n");
+               return NULL;
+       }
+
+       uk_alloc_init_malloc_ifmalloc(a, uk_tinyalloc_malloc,
+                                        uk_tinyalloc_free, NULL);
+
+       return a;
+}
diff --git a/include/uk/tinyalloc.h b/include/uk/tinyalloc.h
new file mode 100644
index 0000000..87290ed
--- /dev/null
+++ b/include/uk/tinyalloc.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 __LIBTINYALLOC_H__
+#define __LIBTINYALLOC_H__
+
+#include <uk/alloc.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct uk_alloc *uk_tinyalloc_init(void *base, size_t len);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __LIBTINYALLOC_H__ */
diff --git a/main-tree.patch b/main-tree.patch
new file mode 100644
index 0000000..40bb096
--- /dev/null
+++ b/main-tree.patch
@@ -0,0 +1,45 @@
+From: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
+Subject: Add tinyalloc entry to the menuconfig and initialize it
+diff --git a/lib/ukboot/Config.uk b/lib/ukboot/Config.uk
+index a888bc1c..694762fa 100644
+--- a/lib/ukboot/Config.uk
++++ b/lib/ukboot/Config.uk
+@@ -32,6 +32,16 @@ if LIBUKBOOT
+                 Satisfy allocation as fast as possible. No support for free().
+                 Refer to help in ukallocregion for more information.
+ 
++              config LIBUKBOOT_INITTINYALLOC
++              bool "tinyalloc"
++              select LIBTINYALLOC
++              help
++                Minimalist allocator implementation, meant for use in systems
++                with unmanaged linear memory such as WebAssembly or embedded
++                systems. tinyalloc is highly configurable and offers high
++                performance and reasonable memory usage when used and
++                configured appropriately.
++
+               config LIBUKBOOT_NOALLOC
+               bool "No memory allocator"
+ 
+diff --git a/lib/ukboot/boot.c b/lib/ukboot/boot.c
+index 4e749aa5..b8bf0a20 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_INITTINYALLOC
++#include <uk/tinyalloc.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_INITTINYALLOC
++                      a = uk_tinyalloc_init(md.base, md.len);
+ #endif
+               } else {
+                       uk_alloc_addmem(a, md.base, md.len);
diff --git a/patches/0001-do-not-store-heap-info-statically.patch 
b/patches/0001-do-not-store-heap-info-statically.patch
new file mode 100644
index 0000000..fd7b953
--- /dev/null
+++ b/patches/0001-do-not-store-heap-info-statically.patch
@@ -0,0 +1,312 @@
+From: Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx>
+Subject: Adapt tinyalloc interface to Unikraft
+ - avoid statics: create a struct tinyalloc to store allocator metadata
+ - pass struct metadata as argument to allocation functions
+diff -urNp tinyalloc-orig/tinyalloc.c tinyalloc-patched/tinyalloc.c
+--- tinyalloc-orig/tinyalloc.c 2019-08-17 23:56:45.000000000 +0200
++++ tinyalloc-patched/tinyalloc.c      2020-06-30 10:34:24.945558078 +0200
+@@ -9,36 +9,16 @@ extern void print_i(size_t);
+ #define print_i(X)
+ #endif
+ 
+-typedef struct Block Block;
+-
+-struct Block {
+-    void *addr;
+-    Block *next;
+-    size_t size;
+-};
+-
+-typedef struct {
+-    Block *free;   // first free block
+-    Block *used;   // first used block
+-    Block *fresh;  // first available blank block
+-    size_t top;    // top free addr
+-    Block *blocks;
+-} Heap;
+-
+-static Heap *heap = NULL;
+-static void *heap_limit = NULL;
+-static size_t heap_split_thresh;
+-static size_t heap_alignment;
+-static size_t heap_max_blocks;
+-
+ /**
+  * If compaction is enabled, inserts block
+  * into free list, sorted by addr.
+  * If disabled, add block has new head of
+  * the free list.
+  */
+-static void insert_block(Block *block) {
+-#ifndef TA_DISABLE_COMPACT
++static void insert_block(struct tinyalloc *a, Block *block) {
++    Heap *heap = a->heap;
++
++#ifndef CONFIG_LIBTINYALLOC_DISABLE_COMPACT
+     Block *ptr  = heap->free;
+     Block *prev = NULL;
+     while (ptr != NULL) {
+@@ -66,8 +46,10 @@ static void insert_block(Block *block) {
+ #endif
+ }
+ 
+-#ifndef TA_DISABLE_COMPACT
+-static void release_blocks(Block *scan, Block *to) {
++#ifndef CONFIG_LIBTINYALLOC_DISABLE_COMPACT
++static void release_blocks(struct tinyalloc *a, Block *scan, Block *to) {
++    Heap *heap = a->heap;
++
+     Block *scan_next;
+     while (scan != to) {
+         print_s("release");
+@@ -81,7 +63,9 @@ static void release_blocks(Block *scan,
+     }
+ }
+ 
+-static void compact() {
++static void compact(struct tinyalloc *a) {
++    Heap *heap = a->heap;
++
+     Block *ptr = heap->free;
+     Block *prev;
+     Block *scan;
+@@ -103,7 +87,7 @@ static void compact() {
+             ptr->size   = new_size;
+             Block *next = prev->next;
+             // make merged blocks available
+-            release_blocks(ptr->next, prev->next);
++            release_blocks(a, ptr->next, prev->next);
+             // relink
+             ptr->next = next;
+         }
+@@ -112,30 +96,36 @@ static void compact() {
+ }
+ #endif
+ 
+-bool ta_init(const void *base, const void *limit, const size_t heap_blocks, 
const size_t split_thresh, const size_t alignment) {
+-    heap = (Heap *)base;
+-    heap_limit = limit;
+-    heap_split_thresh = split_thresh;
+-    heap_alignment = alignment;
+-    heap_max_blocks = heap_blocks;
++void ta_init(struct tinyalloc *a, const void *base, const void *limit,
++             const size_t heap_blocks, const size_t split_thresh,
++             const size_t alignment) {
++    Heap *heap;
++
++    a->heap = (Heap *)base;
++    a->heap_limit = limit;
++    a->heap_split_thresh = split_thresh;
++    a->heap_alignment = alignment;
++    a->heap_max_blocks = heap_blocks;
+ 
++    heap = a->heap;
+     heap->free   = NULL;
+     heap->used   = NULL;
++    heap->blocks = (Block*) ((size_t)base + sizeof(Heap));
+     heap->fresh  = heap->blocks;
+     heap->top    = (size_t)base + sizeof(Heap) + heap_blocks * sizeof(Block);
+-    heap->blocks = base + sizeof(Heap);
+ 
+     Block *block = heap->blocks;
+-    size_t i     = heap_max_blocks - 1;
++    size_t i     = a->heap_max_blocks - 1;
+     while (i--) {
+         block->next = block + 1;
+         block++;
+     }
+     block->next = NULL;
+-    return true;
+ }
+ 
+-bool ta_free(void *free) {
++void ta_free(struct tinyalloc *a, void *free) {
++    Heap *heap = a->heap;
++
+     Block *block = heap->used;
+     Block *prev  = NULL;
+     while (block != NULL) {
+@@ -145,25 +135,28 @@ bool ta_free(void *free) {
+             } else {
+                 heap->used = block->next;
+             }
+-            insert_block(block);
+-#ifndef TA_DISABLE_COMPACT
+-            compact();
++            insert_block(a, block);
++#ifndef CONFIG_LIBTINYALLOC_DISABLE_COMPACT
++            compact(a);
+ #endif
+-            return true;
++            return;
+         }
+         prev  = block;
+         block = block->next;
+     }
+-    return false;
++    return;
+ }
+ 
+-static Block *alloc_block(size_t num) {
++static Block *alloc_block(struct tinyalloc *a, size_t num) {
++    Heap *heap = a->heap;
++
+     Block *ptr  = heap->free;
+     Block *prev = NULL;
+     size_t top  = heap->top;
+-    num         = (num + heap_alignment - 1) & -heap_alignment;
++    num         = (num + a->heap_alignment - 1) & - a->heap_alignment;
+     while (ptr != NULL) {
+-        const int is_top = ((size_t)ptr->addr + ptr->size >= top) && 
((size_t)ptr->addr + num <= heap_limit);
++        const int is_top = ((size_t)ptr->addr + ptr->size >= top)
++                      && ((size_t)ptr->addr + num <= a->heap_limit);
+         if (is_top || ptr->size >= num) {
+             if (prev != NULL) {
+                 prev->next = ptr->next;
+@@ -176,10 +169,10 @@ static Block *alloc_block(size_t num) {
+                 print_s("resize top block");
+                 ptr->size = num;
+                 heap->top = (size_t)ptr->addr + num;
+-#ifndef TA_DISABLE_SPLIT
++#ifndef CONFIG_LIBTINYALLOC_DISABLE_SPLIT
+             } else if (heap->fresh != NULL) {
+                 size_t excess = ptr->size - num;
+-                if (excess >= heap_split_thresh) {
++                if (excess >= a->heap_split_thresh) {
+                     ptr->size    = num;
+                     Block *split = heap->fresh;
+                     heap->fresh  = split->next;
+@@ -187,9 +180,9 @@ static Block *alloc_block(size_t num) {
+                     print_s("split");
+                     print_i((size_t)split->addr);
+                     split->size = excess;
+-                    insert_block(split);
+-#ifndef TA_DISABLE_COMPACT
+-                    compact();
++                    insert_block(a, split);
++#ifndef CONFIG_LIBTINYALLOC_DISABLE_COMPACT
++                    compact(a);
+ #endif
+                 }
+ #endif
+@@ -199,10 +192,11 @@ static Block *alloc_block(size_t num) {
+         prev = ptr;
+         ptr  = ptr->next;
+     }
++
+     // no matching free blocks
+     // see if any other blocks available
+     size_t new_top = top + num;
+-    if (heap->fresh != NULL && new_top <= heap_limit) {
++    if (heap->fresh != NULL && new_top <= (size_t)a->heap_limit) {
+         ptr         = heap->fresh;
+         heap->fresh = ptr->next;
+         ptr->addr   = (void *)top;
+@@ -212,11 +206,12 @@ static Block *alloc_block(size_t num) {
+         heap->top   = new_top;
+         return ptr;
+     }
++
+     return NULL;
+ }
+ 
+-void *ta_alloc(size_t num) {
+-    Block *block = alloc_block(num);
++void *ta_alloc(struct tinyalloc *a, size_t num) {
++    Block *block = alloc_block(a, num);
+     if (block != NULL) {
+         return block->addr;
+     }
+@@ -236,9 +231,9 @@ static void memclear(void *ptr, size_t n
+     }
+ }
+ 
+-void *ta_calloc(size_t num, size_t size) {
++void *ta_calloc(struct tinyalloc *a, size_t num, size_t size) {
+     num *= size;
+-    Block *block = alloc_block(num);
++    Block *block = alloc_block(a, num);
+     if (block != NULL) {
+         memclear(block->addr, num);
+         return block->addr;
+@@ -255,18 +250,21 @@ static size_t count_blocks(Block *ptr) {
+     return num;
+ }
+ 
+-size_t ta_num_free() {
++size_t ta_num_free(struct tinyalloc *a) {
++    Heap *heap = a->heap;
+     return count_blocks(heap->free);
+ }
+ 
+-size_t ta_num_used() {
++size_t ta_num_used(struct tinyalloc *a) {
++    Heap *heap = a->heap;
+     return count_blocks(heap->used);
+ }
+ 
+-size_t ta_num_fresh() {
++size_t ta_num_fresh(struct tinyalloc *a) {
++    Heap *heap = a->heap;
+     return count_blocks(heap->fresh);
+ }
+ 
+-bool ta_check() {
+-    return heap_max_blocks == ta_num_free() + ta_num_used() + ta_num_fresh();
++bool ta_check(struct tinyalloc *a) {
++    return a->heap_max_blocks == ta_num_free(a) + ta_num_used(a) + 
ta_num_fresh(a);
+ }
+diff -urNp tinyalloc-orig/tinyalloc.h tinyalloc-patched/tinyalloc.h
+--- tinyalloc-orig/tinyalloc.h 2019-08-17 23:56:45.000000000 +0200
++++ tinyalloc-patched/tinyalloc.h      2020-06-30 10:38:59.734724059 +0200
+@@ -1,12 +1,41 @@
+ #include <stdbool.h>
+ #include <stddef.h>
+ 
+-bool ta_init(const void *base, const void *limit, const size_t heap_blocks, 
const size_t split_thresh, const size_t alignment);
+-void *ta_alloc(size_t num);
+-void *ta_calloc(size_t num, size_t size);
+-bool ta_free(void *ptr);
+-
+-size_t ta_num_free();
+-size_t ta_num_used();
+-size_t ta_num_fresh();
+-bool ta_check();
++typedef struct Block Block;
++
++struct Block {
++    void *addr;
++    Block *next;
++    size_t size;
++};
++
++typedef struct {
++    Block *free;   // first free block
++    Block *used;   // first used block
++    Block *fresh;  // first available blank block
++    size_t top;    // top free addr
++    Block *blocks;
++} Heap;
++
++struct tinyalloc {
++    Heap *heap;
++    void *heap_limit;
++    size_t heap_split_thresh;
++    size_t heap_alignment;
++    size_t heap_max_blocks;
++};
++
++void ta_init(struct tinyalloc *a, const void *base, const void *limit,
++             const size_t heap_blocks, const size_t split_thresh,
++             const size_t alignment);
++
++void *ta_alloc(struct tinyalloc *a, size_t num);
++void *ta_calloc(struct tinyalloc *a, size_t num, size_t size);
++void  ta_free(struct tinyalloc *a, void *ptr);
++int   ta_posix_memalign(struct tinyalloc *a, void **memptr, size_t align,
++                      size_t size);
++
++size_t ta_num_free(struct tinyalloc *a);
++size_t ta_num_used(struct tinyalloc *a);
++size_t ta_num_fresh(struct tinyalloc *a);
++bool   ta_check(struct tinyalloc *a);
-- 
2.7.4