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

[Razvan Deaconescu <razvan.deaconescu@xxxxxxxxx>]

I added Hugo with his non-NEC e-mail address.

Razvan

Razvan Deaconescu <razvan.deaconescu@xxxxxxxxx> writes:
> 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);