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

[Razvan Deaconescu <razvan.deaconescu@xxxxxxxxx>]

Hi, Hugo.

I tested tinyalloc on linuxu and KVM, it works.

Why did you name the structure "struct tinyalloc", without the uk_
prefix as is the case with the other allocators (i.e. "struct
uk_bbpalloc" and "struct uk_allocregion").

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.

There's another comment inline.

Razvan

Hugo Lefeuvre <hugo.lefeuvre@xxxxxxxxx> writes:
> 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;
> +     }

Shouldn't this be if (!b)?

> +     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);