picolibc malloc benchmark suite: linked list vs skip list (PR #1369), RV64

README.md

Gists are flat, so directory paths are encoded with @ in the file names. Run sh unpack.sh to restore the tree (pico/, src/, tools/), then follow the quick start below. The results@* files are the data set the PR comment quotes.

picolibc malloc benchmark suite (RV64)

Compares picolibc's singly linked free list against the skip list from PR #1369, plus a few proposed fixes, on an RV64 Linux target. The allocator sources are picolibc's own; the only delta is local.patch.

Reports and result sets live outside this directory. The suite produces a CSV; tools/report.py turns it into tables.

Where things run

Three machines, and nothing is built on the one you drive it from:

	role
workstation	drives the tools, holds the sources, talks adb to the target
build host	cross-compiles with riscv64-unknown-linux-gnu-gcc; pick it with HOST
RV64 target	runs the binaries, reached over adb shell

Binaries are static, so the target needs only a kernel and a writable /tmp. Developed against a Spacemit Keystone K3 board (X100, RV64GCV, 8 cores, 64 KiB L1D, 4 MiB L2, no L3).

Quick start

./tools/build.sh                    # sync -> build host -> cross-build -> adb push
./tools/check.sh                    # randomized correctness check on target
./tools/env.sh    > env.txt         # target and toolchain facts
./tools/run.sh    > results.csv     # sweep on target
python3 tools/report.py results.csv > tables.md
ssh "$HOST" "cd $REMOTE && make sizes"       # code size + memory constants

Short sweep, or a single number:

NS="64 1024 16384" ./tools/run.sh > results.csv
NS=65536 WORKLOAD=churn VARIANTS="skip skip-fast" ./tools/run.sh

Overrides: HOST, REMOTE (build host), DEV_DIR (target directory), EXEC, BINDIR (run somewhere other than adb), NS, SIZES, PIN, WORKLOAD, VARIANTS. Build knobs: make TRIALS=n, make LTO=1.

How the extraction works

pico/ holds malloc.c, free.c, realloc.c, malloc-skip.c, local-malloc.h and malloc-skip.h copied straight from libc/stdlib/, with local.patch applied on top. src/shim.h supplies the picolibc internals the sources expect (__align_up, __strong_reference, __LIBC_LOCK, picolibc's random() LCG), and src/sys/lock.h is a no-op lock. sbrk is a bump pointer over a pre-faulted 512 MiB mmap region (src/arena.c), so page faults stay out of the measurements and the heap can be reset between trials. The public entry points are renamed with -Dmalloc=__pico_malloc and friends, so the C library's own allocator is untouched.

To refresh against a newer picolibc:

./extract.sh /path/to/picolibc      # re-copy + re-apply local.patch
./extract.sh -r /path/to/picolibc   # regenerate local.patch after editing pico/

local.patch contains exactly three things: the BENCH_STEP() counters, MALLOC_SKIP_FASTSCAN, and MALLOC_SKIP_TOP. All are #ifdef-guarded, so list and skip build unmodified upstream behaviour.

Variants

name	what it is
list	upstream singly linked, address-ordered free list
skip	PR #1369 as posted
skip-fast	+ first-fit scan does not maintain prev[]; one _ms_find() once a chunk wins
skip-top	+ _ms_find() starts at the highest populated level instead of MS_MAX_LEVEL
skip-fast-top	both fixes
list-scan, skip-scan	the same scan change expressed through the free-list abstraction, so one loop serves both designs
skip-lvl	PR with the #ifdef __MALLOC_SKIP_LIST__ typo fixed, so that block compiles
*-b512	as above with -Dmalloc-small-bucket=512

Variants live in one place, the VARIANTS list in the Makefile; the tools read it back with make -s print-variants. To add one, add a name and a <name>_DEF line.

Each variant builds three binaries: bench-* (timing), count-* (same plus free-list pointer-chase counters, which would perturb the timings) and check-* (correctness).

Workloads

All start from the same state: 2N chunks allocated back to back, every other one freed. The live chunks in between stop coalescing, so the free list really holds N entries -- that is the length both designs have to search.

workload	what it measures
free_rand	the N frees in random address order
free_asc	ascending address order (worst case for the sorted list)
free_desc	descending, i.e. LIFO -- the common real pattern
malloc_miss	allocations too big for any hole: pure first-fit scan
churn	steady-state random alloc/free against the fragmented heap
realloc_grow	repeated growth; each call must locate the neighbouring chunk

Per operation the CSV reports median nanoseconds, the spread across trials, free-list steps, heap high-water and the resulting free-list length.

What is done to keep the comparison fair

• Every variant is the same source built with the same flags; only -D differs. No LTO by default, because picolibc does not use it -- which means upstream's linked-list helpers inline from local-malloc.h while the skip-list ones stay out of line in malloc-skip.c. That asymmetry is upstream's, not the harness's; make LTO=1 measures how much of it matters.
• Variants run back to back for each (N, size), on the same pinned core, from the same RNG seed, so they see identical workloads.
• Reported time is the median of 5 trials, and the spread between the fastest and slowest trial travels with it. tools/report.py marks any cell that varied by more than 20%. A minimum would look sharper and hide exactly the cases where the machine, not the allocator, decided the result.
• Each trial starts the heap at a different offset inside the arena (HEAP_STRIDE in src/arena.c). All trials in a process share one mapping, so without this they would inherit one physical page layout and its cache colouring would bias every trial of that variant the same way. The offset sequence is deterministic and identical across variants.
• malloc_miss requests a size above any small-bucket threshold, so the bucket variants walk the general free list too, instead of answering from a bucket and turning the comparison into list-walk versus linked-list pop.
• The step counters count one pointer touch each, in both designs: one per node for the linked list, one per level for the skip list's _ms_step and _ms_find. Counting a 16-level prev[] update as a single step would flatter the skip list.
• count-* binaries run a single trial, since step counts are deterministic, and their timings are ignored by tools/report.py.

What is not controlled, and shows up as spread: DRAM refresh, other load on the target, and the arena's absolute physical placement. tools/env.sh records the governor and clock so a result set says what it was measured on. The reference target runs the userspace governor at a fixed 2.2 GHz.

Two things the harness deliberately does not equalize, because they are properties of the designs and not of the measurement:

• MALLOC_SPLIT_MIN differs (16 vs 144 bytes on LP64), so the two allocators make different splitting decisions and end up with slightly different free-list lengths for the same workload. The CSV reports free_len so this is visible rather than assumed away.
• picolibc's malloc() zeroes every allocation. That cost is in both variants and dominates at large payloads, which is why the default sweep uses 32-byte payloads.

extract.sh

#!/bin/sh
# Re-extract the allocator from a picolibc checkout into pico/ and
# re-apply the local delta (instrumentation + the proposed variants).
#
#   ./extract.sh [picolibc-dir]        refresh pico/ from upstream
#   ./extract.sh -r [picolibc-dir]     regenerate local.patch from pico/
#
# Everything in pico/ is upstream code plus local.patch. Nothing else in
# this suite touches picolibc sources.
set -e
cd "$(dirname "$0")"

REGEN=no
if [ "$1" = "-r" ]; then REGEN=yes; shift; fi
SRC=${1:-..}
FILES="local-malloc.h malloc.c free.c realloc.c malloc-skip.c malloc-skip.h"

for f in $FILES; do
    test -f "$SRC/libc/stdlib/$f" || { echo "not a picolibc tree: $SRC" >&2; exit 1; }
done

if [ $REGEN = yes ]; then
    rm -rf .orig; mkdir .orig
    for f in $FILES; do cp "$SRC/libc/stdlib/$f" .orig/$f; done
    diff -ur .orig pico > local.patch || true
    rm -rf .orig
    echo "regenerated local.patch ($(grep -c '^@@' local.patch) hunks)"
else
    for f in $FILES; do cp "$SRC/libc/stdlib/$f" pico/$f; done
    patch -p1 -d pico < local.patch
fi

local.patch

diff -ur .orig/local-malloc.h pico/local-malloc.h
--- .orig/local-malloc.h	2026-08-17 16:17:00.125453125 +0800
+++ pico/local-malloc.h	2026-08-17 15:15:27.279127996 +0800
@@ -148,6 +148,7 @@
 static inline void
 _ms_step(chunk_t *c, malloc_prev_t *prev)
 {
+    BENCH_STEP();
     *prev = &c->next;
 }
 
diff -ur .orig/malloc-skip.c pico/malloc-skip.c
--- .orig/malloc-skip.c	2026-08-17 16:17:00.144177683 +0800
+++ pico/malloc-skip.c	2026-08-17 16:13:02.696953547 +0800
@@ -51,6 +51,10 @@
     return level;
 }
 
+#ifdef MALLOC_SKIP_TOP
+size_t __malloc_skip_top;
+#endif
+
 static void
 _ms_init(chunk_t *ms)
 {
@@ -73,10 +77,10 @@
     chunk_t  *next;
     chunk_t **p;
 
-    p = &__malloc_skip_list.next[MS_MAX_LEVEL];
+    p = &__malloc_skip_list.next[_ms_top()];
 
     /* For all levels */
-    for (o = MS_MAX_LEVEL;; o--) {
+    for (o = _ms_top();; o--) {
 
         /* Search at this level for the insertion point */
         while ((next = _ms_ref(*p)) != NULL) {
@@ -85,6 +89,7 @@
             if (!_ms_greater(template, next))
                 break;
 
+            BENCH_STEP();
             p = &next->next[o];
         }
 
@@ -109,11 +114,20 @@
     _ms_init(ms);
     /* Insert into all levels for the new object */
     for (o = 0;; o++) {
-        _ms_set_ref(&ms->next[o], _ms_ref(*prev->prev[o]));
-        _ms_set_ref(prev->prev[o], ms);
+#ifdef MALLOC_SKIP_TOP
+        chunk_t **p = o <= __malloc_skip_top ? prev->prev[o] : &__malloc_skip_list.next[o];
+#else
+        chunk_t **p = prev->prev[o];
+#endif
+        _ms_set_ref(&ms->next[o], _ms_ref(*p));
+        _ms_set_ref(p, ms);
         if (_ms_is_last(ms->next[o]))
             break;
     }
+#ifdef MALLOC_SKIP_TOP
+    if (o > __malloc_skip_top)
+        __malloc_skip_top = o;
+#endif
 }
 
 /* Remove 'ms' from lists at position prev */
@@ -129,6 +143,10 @@
         if (_ms_is_last(ref))
             break;
     }
+#ifdef MALLOC_SKIP_TOP
+    while (__malloc_skip_top > 0 && __malloc_skip_list.next[__malloc_skip_top] == NULL)
+        __malloc_skip_top--;
+#endif
 }
 
 /* Step forward one object, updating all of the prev pointers */
@@ -145,6 +163,7 @@
     n = ms->next;
     p = prev->prev;
     for (;;) {
+        BENCH_STEP();
         *p = n;
         if (_ms_is_last(*n))
             break;
diff -ur .orig/malloc-skip.h pico/malloc-skip.h
--- .orig/malloc-skip.h	2026-08-17 16:17:00.148915865 +0800
+++ pico/malloc-skip.h	2026-08-17 15:15:27.281181142 +0800
@@ -54,6 +54,15 @@
 
 extern malloc_head_t __malloc_skip_list;
 
+#ifdef MALLOC_SKIP_TOP
+/* Highest level any live chunk currently occupies. Searches start here
+ * instead of MS_MAX_LEVEL, so a short free list costs a short descent. */
+extern size_t __malloc_skip_top;
+#define _ms_top() __malloc_skip_top
+#else
+#define _ms_top() ((size_t)MS_MAX_LEVEL)
+#endif
+
 static inline size_t
 _ms_size(size_t level)
 {
@@ -97,7 +106,7 @@
 {
     size_t o;
 
-    for (o = 0; o <= MS_MAX_LEVEL; o++)
+    for (o = 0; o <= _ms_top(); o++)
         prev->prev[o] = &__malloc_skip_list.next[o];
 }
 
diff -ur .orig/malloc.c pico/malloc.c
--- .orig/malloc.c	2026-08-17 16:17:00.131676338 +0800
+++ pico/malloc.c	2026-08-17 15:15:27.282250444 +0800
@@ -163,6 +163,57 @@
             *p = __next_bucket(c);
     } else
 #endif
+#if defined(__MALLOC_SKIP_LIST) && defined(MALLOC_SKIP_FASTSCAN)
+    /*
+     * First-fit is a level-0 walk no matter what the free list looks
+     * like, so don't pay _ms_step's per-level prev[] maintenance for
+     * every chunk we reject. Scan with a plain next pointer and rebuild
+     * prev[] with a single O(log N) _ms_find once we have a winner.
+     */
+    {
+        malloc_prev_t prev;
+        bool          grown = false;
+
+        for (c = _ms_ref(__malloc_skip_list.next[0]); c != NULL; c = _ms_next(c)) {
+            BENCH_STEP();
+            if (_size(c) >= alloc_size)
+                break;
+            if (!_ms_next(c) && __malloc_grow_chunk(c, alloc_size)) {
+                grown = true;
+                break;
+            }
+        }
+
+        if (c != NULL) {
+            size_t rem = _size(c) - alloc_size;
+
+            _ms_find(c, &prev);
+
+            if (!grown && rem >= MALLOC_SPLIT_MIN) {
+                _ms_clip_out(c, &prev);
+
+                chunk_t *s = (chunk_t *)((char *)c + alloc_size);
+                _set_size(c, alloc_size);
+                _set_size(s, rem);
+                _mark_free(s);
+
+#if __MALLOC_SMALL_BUCKET
+                int    bucket = BUCKET_NUM(rem);
+                if (rem > MALLOC_MAX_BUCKET || rem != BUCKET_SIZE(bucket)) {
+                    _ms_clip_in(s, &prev);
+                } else {
+                    __next_bucket(s) = __malloc_bucket_list[bucket];
+                    __malloc_bucket_list[bucket] = s;
+                }
+#else
+                _ms_clip_in(s, &prev);
+#endif
+            } else {
+                _ms_clip_out(c, &prev);
+            }
+        }
+    }
+#else
     {
         malloc_prev_t prev;
         for (_ms_step_init(&prev); (c = _ms_this(&prev)) != NULL; _ms_step(c, &prev)) {
@@ -217,11 +268,12 @@
             }
         }
     }
+#endif
 
     /* Failed to find a appropriate chunk_t. Ask for more memory */
     if (c == NULL) {
 
-#ifdef __MALLOC_SKIP_LIST__
+#if defined(__MALLOC_SKIP_LIST) && defined(MALLOC_SKIP_LEVELUP)
         /*
          * Avoid a large number of tiny allocations making our skip list
          * too flat by randomly increasing chunk sizes using our skip

Makefile

# Standalone benchmark suite for picolibc's malloc: singly linked free
# list versus skip list (PR #1369), plus proposed fixes.
#
# Cross build only. This Makefile runs on the build host with the RV64
# toolchain; the binaries run on the RV64 target over adb. Drive the
# whole thing from tools/build.sh, tools/check.sh, tools/run.sh.
#
#   make            build every variant (static RV64)
#   make sizes      target code size + memory constants per variant
#   make LTO=1      same, with link-time optimization

TOOLDIR ?= $(HOME)/riscv/toolchain/bin
CROSS   ?= riscv64-unknown-linux-gnu-
# `CC ?=` would lose to make's built-in default of `cc` and silently
# build for the host, so override the default origin explicitly.
ifeq ($(origin CC),default)
CC := $(TOOLDIR)/$(CROSS)gcc
endif
SIZE    ?= $(TOOLDIR)/$(CROSS)size
NM      ?= $(TOOLDIR)/$(CROSS)nm

# Static: the target's glibc is newer than the toolchain's, and it keeps
# the host libc's allocator out of the picture entirely.
CFLAGS  ?= -O2 -g -Wall
LDFLAGS ?= -static

# Upstream inlines the linked-list helpers from local-malloc.h but calls
# the skip-list ones out of line in malloc-skip.c. That is how picolibc
# builds, so it is the default here; LTO=1 removes the asymmetry if you
# want to know how much of a difference it makes.
ifeq ($(LTO),1)
CFLAGS  += -flto
LDFLAGS += -flto
endif

# Trials per measurement; the timing binaries report the median.
ifdef TRIALS
CFLAGS  += -DTRIALS=$(TRIALS)
endif
BASE     = $(CFLAGS) -D_GNU_SOURCE -I. -Isrc -include src/shim.h \
	   -Dmalloc=__pico_malloc -Dfree=__pico_free -Dcfree=__pico_cfree \
	   -Drealloc=__pico_realloc -Dsbrk=__pico_sbrk -Drandom=__pico_random \
	   -fno-builtin -Wno-builtin-declaration-mismatch

ALLOC    = pico/malloc.c pico/free.c pico/realloc.c pico/malloc-skip.c
SRC      = $(ALLOC) src/arena.c

# The one place variants are defined. The tools read this list back out
# with `make -s print-variants`.
VARIANTS = list skip skip-fast skip-top skip-fast-top skip-lvl \
	   list-scan skip-scan \
	   list-b512 skip-b512 skip-fast-b512

list_DEF           =
skip_DEF           = -D__MALLOC_SKIP_LIST
skip-fast_DEF      = -D__MALLOC_SKIP_LIST -DMALLOC_SKIP_FASTSCAN
skip-top_DEF       = -D__MALLOC_SKIP_LIST -DMALLOC_SKIP_TOP
skip-fast-top_DEF  = -D__MALLOC_SKIP_LIST -DMALLOC_SKIP_FASTSCAN -DMALLOC_SKIP_TOP
skip-lvl_DEF       = -D__MALLOC_SKIP_LIST -DMALLOC_SKIP_LEVELUP
list-scan_DEF      = -DMALLOC_SCAN_MACRO
skip-scan_DEF      = -D__MALLOC_SKIP_LIST -DMALLOC_SCAN_MACRO
list-b512_DEF      = -D__MALLOC_SMALL_BUCKET=512
skip-b512_DEF      = -D__MALLOC_SKIP_LIST -D__MALLOC_SMALL_BUCKET=512
skip-fast-b512_DEF = -D__MALLOC_SKIP_LIST -DMALLOC_SKIP_FASTSCAN -D__MALLOC_SMALL_BUCKET=512

BINS = $(VARIANTS:%=bench-%) $(VARIANTS:%=count-%) $(VARIANTS:%=check-%)

all: $(BINS)

# bench-* time the workloads; count-* additionally tally free-list
# pointer chases, which would perturb the timings.
bench-%: $(SRC) src/bench.c Makefile src/shim.h
	$(CC) $(BASE) $($*_DEF) $(LDFLAGS) -o $@ $(SRC) src/bench.c

count-%: $(SRC) src/bench.c Makefile src/shim.h
	$(CC) $(BASE) $($*_DEF) -DBENCH_COUNT $(LDFLAGS) -o $@ $(SRC) src/bench.c

check-%: $(SRC) src/check.c Makefile src/shim.h
	$(CC) $(BASE) $($*_DEF) $(LDFLAGS) -o $@ $(SRC) src/check.c

sizes:
	@CC="$(CC)" SIZE="$(SIZE)" NM="$(NM)" ./tools/sizes.sh

print-variants:
	@echo $(VARIANTS)

print-cc:
	@echo $(CC)

print-def-%:
	@echo $($*_DEF)

clean:
	rm -f $(BINS); rm -rf obj

.PHONY: all sizes print-variants clean

pico@free.c

/*
 * Copyright (c) 2012, 2013 ARM Ltd
 * 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. The name of the company may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``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 ARM LTD 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 "local-malloc.h"

/*
 * Algorithm:
 *  Maintain a global free chunk_t single link list, headed by global
 *  variable __malloc_free_list.
 *  When free, insert the to-be-freed chunk_t into free list. The place to
 *  insert should make sure all chunks are sorted by address from low to
 *  high.  Then merge with neighbor chunks if adjacent.
 */

void __disable_sanitizer
__malloc_free(void *free_p)
{
    chunk_t *p_to_free;
    chunk_t *c;

    if (free_p == NULL)
        return;

    p_to_free = ptr_to_chunk(free_p);

    if (!_check_busy(p_to_free, "free: double free\n"))
        return;

#ifdef __MALLOC_CLEAR_FREED
    memset(p_to_free, 0, chunk_usable(p_to_free));
#else
#ifndef __MALLOC_SKIP_LIST
    p_to_free->next = NULL;
#endif
#endif

#if MALLOC_DEBUG
    __malloc_validate_chunk(p_to_free);
#endif

    _mark_free(p_to_free);

    MALLOC_LOCK;

#if __MALLOC_SMALL_BUCKET
    size_t s = _size(p_to_free);
    if (s <= MALLOC_MAX_BUCKET) {
        int    bucket = BUCKET_NUM(s);
        size_t expect = BUCKET_SIZE(bucket);
        if (s == expect) {
            chunk_t **p;
            p = &__malloc_bucket_list[bucket];
            __next_bucket(p_to_free) = *p;
            *p = p_to_free;
            goto unlock;
        }
    }
#endif

    malloc_prev_t prev;
#ifdef __MALLOC_SKIP_LIST
    _ms_find(p_to_free, &prev);

    c = _ms_this(&prev);

    /* Check for double free */
    if (c == p_to_free) {
        errno = ENOMEM;
        goto unlock;
    }

    /* Add the next block to this block if they're adjacent */
    if (chunk_after(p_to_free) == c) {
        *_size_ref(p_to_free) += _size(c);
        _ms_clip_out(c, &prev);
    }

    /* prev[0] points at the *reference* to the next chunk,
     * which is the same as the address of the previous chunk
     */
    chunk_t *prior = (chunk_t *)prev.prev[0];

    /* Add this block to the prior block if they're adjacent */
    if (prior != (chunk_t *)&__malloc_skip_list && chunk_after(prior) == p_to_free) {
        *_size_ref(prior) += _size(p_to_free);
#if __MALLOC_SMALL_BUCKET
        p_to_free = prior;
        _ms_find(p_to_free, &prev);
#endif
    } else {
        _ms_clip_in(p_to_free, &prev);
    }

#else
    for (_ms_step_init(&prev); (c = _ms_this(&prev)) != NULL; _ms_step(c, &prev)) {
        /* Insert in address order */
        if (p_to_free <= c) {

            /* Check for double free */
            if (p_to_free == c) {
                errno = ENOMEM;
                goto unlock;
            }

            break;
        }

        /* Merge blocks together */
        if (chunk_after(c) == p_to_free) {
            *_size_ref(c) += _size(p_to_free);
            p_to_free = c;
            c = c->next;
            goto no_insert;
        }
    }

    _ms_clip_in(p_to_free, &prev);

no_insert:

    /* Merge blocks together */
    if (chunk_after(p_to_free) == c) {
#ifdef __GNUCLIKE_PRAGMA_DIAGNOSTIC
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wanalyzer-null-dereference"
#endif
        *_size_ref(p_to_free) += _size(c);
#ifdef __GNUCLIKE_PRAGMA_DIAGNOSTIC
#pragma GCC diagnostic pop
#endif
        p_to_free->next = c->next;
    }
#endif

#if __MALLOC_SMALL_BUCKET
    s = _size(p_to_free);
    if (s <= MALLOC_MAX_BUCKET) {
        int    bucket = BUCKET_NUM(s);
        size_t bucket_size = BUCKET_SIZE(bucket);

        /* Move from general free list to bucket */
        if (s == bucket_size) {
#ifdef MALLOC_DEBUG
            assert(_ms_this(&prev) == p_to_free);
#endif
            /* unlink from general list */
            _ms_clip_out(p_to_free, &prev);

            /* link to bucket list */
            __next_bucket(p_to_free) = __malloc_bucket_list[bucket];
            __malloc_bucket_list[bucket] = p_to_free;
        }
    }
#endif

unlock:
    MALLOC_UNLOCK;
}

#ifdef __strong_reference
#if defined(__GNUCLIKE_PRAGMA_DIAGNOSTIC) && !defined(__clang__)
#pragma GCC diagnostic ignored "-Wmissing-attributes"
#endif
__strong_reference(__malloc_free, free);
__strong_reference(__malloc_free, cfree);
#else
void
cfree(void *ptr)
{
    free(ptr);
}
#endif

pico@local-malloc.h

/*
 * Copyright (c) 2012, 2013 ARM Ltd
 * 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. The name of the company may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``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 ARM LTD 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.
 */

/* Implementation of <<malloc>> <<free>> <<calloc>> <<realloc>>
 *
 * Interface documentation refer to malloc.c.
 */

#define _DEFAULT_SOURCE
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <errno.h>
#include <malloc.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/lock.h>
#include <sys/param.h>
#include <stdint.h>

#define _UP_POT(x, val, next) (((x) <= 1UL << (val)) ? (val) : (next))
#define _UP_POT1024(x)        _UP_POT(x, 10, 0)
#define _UP_POT512(x)         _UP_POT(x, 9, _UP_POT1024(x))
#define _UP_POT256(x)         _UP_POT(x, 8, _UP_POT512(x))
#define _UP_POT128(x)         _UP_POT(x, 7, _UP_POT256(x))
#define _UP_POT64(x)          _UP_POT(x, 6, _UP_POT128(x))
#define _UP_POT32(x)          _UP_POT(x, 5, _UP_POT64(x))
#define _UP_POT16(x)          _UP_POT(x, 4, _UP_POT32(x))
#define UP_POT(x)             _UP_POT16(x)

/*
 * Allocations smaller than this will get rounded up to the next power
 * of two.  When allocations of these sizes are freed, they are placed
 * in unsorted per-size free lists.
 */

#if __MALLOC_SMALL_BUCKET
#define MALLOC_MAX_BUCKET_POT UP_POT(__MALLOC_SMALL_BUCKET)
#if MALLOC_MAX_BUCKET_POT == 0
#error __MALLOC_SMALL_BUCKET too large
#endif
#endif

// #define MALLOC_DEBUG 1

#if __STDC_VERSION__ >= 201112L
typedef max_align_t align_chunk_t;
#else
typedef union {
    void       *p;
    double      d;
    long long   ll;
    size_t      s;
    long double ld;
} align_chunk_t;
#endif

/*          --------------------------------------
 *    (head)| chunk size                         |
 *   chunk->| When allocated: data               |
 *          | When freed: pointer to next free   |
 *          | chunk                              |
 *          --------------------------------------
 *
 * mem_ptr is aligned to MALLOC_CHUNK_ALIGN. That means that the
 * address of 'size' may not be aligned to MALLOC_CHUNK_ALIGN. But it
 * will be aligned to MALLOC_HEAD_ALIGN.
 *
 * size is set so that a chunk starting at chunk+size will be
 * aligned correctly
 *
 * We can't use a single struct containing both size and next as that
 * may insert padding between the size and pointer fields when
 * pointers are larger than size_t.
 */

typedef struct malloc_head {
    size_t size;
} head_t;

typedef struct malloc_chunk {
#ifdef __MALLOC_SKIP_LIST
    struct {
    } empty; /* C doesn't allow a struct with only a flex-array member */
    struct malloc_chunk *next[];
#else
    struct malloc_chunk *next;
#endif
} chunk_t;

#ifdef __MALLOC_SKIP_LIST
#include "malloc-skip.h"

extern malloc_head_t __malloc_skip_list;

#define __malloc_free_list (__malloc_skip_list.next[0])
#define __next_chunk(c)    _ms_next(c)
#define __next_bucket(c)   ((c)->next[0])

/* Scan hooks: walk level 0 without maintaining prev[], and materialize
 * prev[] only for the chunk that wins. */
#define _ms_scan_first(prev)   _ms_ref(__malloc_skip_list.next[0])
#define _ms_scan_next(c, prev) (BENCH_STEP(), _ms_next(c))
#define _ms_locate(c, prev)    _ms_find(c, prev)

#else

extern chunk_t   *__malloc_free_list;

#define __next_chunk(c)  ((c)->next)
#define __next_bucket(c) ((c)->next)

/* The linked list already tracks prev during the walk, so locating the
 * winner costs nothing. */
#define _ms_scan_first(prev)   (*(prev) = &__malloc_free_list, __malloc_free_list)
#define _ms_scan_next(c, prev) (BENCH_STEP(), *(prev) = &(c)->next, (c)->next)
#define _ms_locate(c, prev)    ((void)0)

typedef chunk_t **malloc_prev_t;

static inline void
_ms_step_init(malloc_prev_t *prev)
{
    *prev = &__malloc_free_list;
}

static inline chunk_t *
_ms_this(malloc_prev_t *prev)
{
    return **prev;
}

static inline void
_ms_step(chunk_t *c, malloc_prev_t *prev)
{
    BENCH_STEP();
    *prev = &c->next;
}

static inline void
_ms_clip_out(chunk_t *c, malloc_prev_t *prev)
{
    **prev = c->next;
}

static inline void
_ms_clip_in(chunk_t *c, malloc_prev_t *prev)
{
    c->next = **prev;
    **prev = c;
}
#endif

/* Alignment of allocated chunk. Compute the alignment required from a
 * range of types */
#define MALLOC_CHUNK_ALIGN _Alignof(align_chunk_t)

/* Alignment of the header. Never larger than MALLOC_CHUNK_ALIGN, but
 * may be smaller on some targets when size_t is smaller than
 * align_chunk_t.
 */
#define MALLOC_HEAD_ALIGN  _Alignof(head_t)

#define MALLOC_ALIGN_EXTRA (MALLOC_CHUNK_ALIGN - MALLOC_HEAD_ALIGN)

#define MALLOC_HEAD_SIZE   sizeof(head_t)

#define MALLOC_CHUNK_SIZE  sizeof(chunk_t *)

/* nominal "page size" */
#define MALLOC_PAGE_ALIGN (0x1000)

/* Minimum chunk size */
#define MALLOC_CHUNK_MIN __align_up(MALLOC_CHUNK_SIZE + MALLOC_HEAD_SIZE, MALLOC_CHUNK_ALIGN)

/* Minimum chunk split size */
#ifdef __MALLOC_SKIP_LIST
#define MALLOC_SPLIT_PTRS (MS_MAX_LEVEL + 1)
#else
#define MALLOC_SPLIT_PTRS 1
#endif

#define MALLOC_SPLIT_MIN                                                                    \
    __align_up(MALLOC_CHUNK_SIZE *MALLOC_SPLIT_PTRS + MALLOC_HEAD_SIZE, MALLOC_CHUNK_ALIGN)

/* Maximum chunk size */
#define MALLOC_CHUNK_MAX (SIZE_MAX - 2 * MAX(MALLOC_CHUNK_SIZE, MALLOC_CHUNK_ALIGN))

/* Maximum allocation size */
#define MALLOC_ALLOC_MAX (MALLOC_CHUNK_MAX - MALLOC_HEAD_SIZE)

static inline size_t *
_size_ref(chunk_t *chunk)
{
    return (size_t *)((char *)chunk - MALLOC_HEAD_SIZE);
}

static inline void
_mark_free(chunk_t *c)
{
    *_size_ref(c) |= 1;
}

static inline void
_mark_busy(chunk_t *c)
{
    *_size_ref(c) &= ~(size_t)1;
}

static inline bool
_is_free(chunk_t *c)
{
    return *_size_ref(c) & 1;
}

static inline size_t
_size(chunk_t *chunk)
{
    return *_size_ref(chunk) & ~(size_t)1;
}

static inline void
_set_size(chunk_t *chunk, size_t size)
{
    *_size_ref(chunk) = size;
}

#ifdef __MALLOC_ERROR_ABORT
__noreturn bool __malloc_error(const char *msg);
#define _check_busy(c, msg) (_is_free(c) ? __malloc_error(msg) : true)
#define _check_free(c, msg) (!_is_free(c) ? __malloc_error(msg) : true)
#else
#define _check_busy(c, msg) (!_is_free(c) ? true : (errno = ENOMEM, false))
#define _check_free(c, msg) (_is_free(c) ? true : (errno = ENOMEM, false))
#endif

#if MALLOC_DEBUG
void __malloc_validate(void);
void __malloc_validate_chunk(chunk_t *c);
#define MALLOC_LOCK          \
    do {                     \
        __LIBC_LOCK();       \
        __malloc_validate(); \
    } while (0)
#define MALLOC_UNLOCK        \
    do {                     \
        __malloc_validate(); \
        __LIBC_UNLOCK();     \
    } while (0)
#else
#define __malloc_validate()
#define __malloc_validate_chunk(c)
#define MALLOC_LOCK   __LIBC_LOCK()
#define MALLOC_UNLOCK __LIBC_UNLOCK()
#endif

extern char *__malloc_sbrk_start;
extern char *__malloc_sbrk_top;

#ifdef MALLOC_MAX_BUCKET_POT

/* Every power-of-two bucket gets padded by this amount */
#define BUCKET_EXTRA        __align_up(MALLOC_HEAD_SIZE, MALLOC_CHUNK_ALIGN)

#define BUCKET_SIZE(bucket) (((size_t)1 << ((bucket) + MIN_BUCKET_POT)) + BUCKET_EXTRA)

#define MALLOC_MAX_BUCKET   (BUCKET_SIZE(MALLOC_MAX_BUCKET_POT - MIN_BUCKET_POT))

#define MIN_BUCKET_POT      (UP_POT(MALLOC_CHUNK_MIN))
#define MAX_BUCKET_POT      MALLOC_MAX_BUCKET_POT
#define NUM_BUCKET_POT      (MAX_BUCKET_POT - MIN_BUCKET_POT + 1)

#define BUCKET_NUM(s)       (UP_POT(s - BUCKET_EXTRA) - MIN_BUCKET_POT)

extern chunk_t *__malloc_bucket_list[NUM_BUCKET_POT];
#endif

bool __malloc_grow_chunk(chunk_t *c, size_t new_size);

/* Work around compiler optimizing away stores to 'size' field before
 * call to free.
 */
#ifdef __strong_reference
void  __malloc_free(void *);
void *__malloc_malloc(size_t);
#else
#define __malloc_free(x)   free(x)
#define __malloc_malloc(x) malloc(x)
#endif

/* convert storage pointer to chunk */
static inline chunk_t *
ptr_to_chunk(void *ptr)
{
    return (chunk_t *)ptr;
}

/* convert chunk to storage pointer */
static inline void *
chunk_to_ptr(chunk_t *c)
{
    return c;
}

/* Convert address of chunk region to chunk pointer */
static inline chunk_t * __disable_sanitizer
blob_to_chunk(void *blob)
{
    return (chunk_t *)((char *)blob + MALLOC_HEAD_SIZE);
}

/* Convert chunk pointer to address of chunk region */
static inline void * __disable_sanitizer
chunk_to_blob(chunk_t *c)
{
    return (void *)((char *)c - MALLOC_HEAD_SIZE);
}

/* end of chunk -- address of first byte past chunk storage */
static inline void * __disable_sanitizer
chunk_end(chunk_t *c)
{
    size_t *s = _size_ref(c);
    return (char *)s + (*s & ~(size_t)1);
}

/* next chunk in memory -- address of chunk header past this chunk */
static inline __disable_sanitizer chunk_t *
chunk_after(chunk_t *c)
{
    return (chunk_t *)((char *)c + _size(c));
}

/* chunk size needed to hold 'malloc_size' bytes */
static inline size_t
chunk_size(size_t malloc_size)
{
    /* Make space for the header */
    malloc_size += MALLOC_HEAD_SIZE;

    /* Align */
    malloc_size = __align_up(malloc_size, MALLOC_CHUNK_ALIGN);

    /* At least MALLOC_CHUNK_MIN bytes */
    malloc_size = MAX(MALLOC_CHUNK_MIN, malloc_size);

    return malloc_size;
}

/* Usable bytes out of a chunk */
static inline size_t
malloc_size(size_t chunk_size)
{
    return chunk_size - MALLOC_HEAD_SIZE;
}

/* available storage in chunk */
static inline size_t
chunk_usable(chunk_t *c)
{
    return malloc_size(_size(c));
}

/* assign 'size' to the specified chunk and return it to the free
 * pool */
static inline void
make_free_chunk(chunk_t *c, size_t size)
{
    _set_size(c, size);
    __malloc_free(chunk_to_ptr(c));
}

pico@malloc-skip.c

/*
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright © 2026 Keith Packard
 *
 * 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 "local-malloc.h"

#ifdef __MALLOC_SKIP_LIST

static inline size_t
_ms_new_level(size_t size)
{
    long   bits = random();
    size_t level = 0;

    while (!(bits & MS_LEVEL_MASK) && level < MS_MAX_LEVEL
           && malloc_size(size) >= _ms_size(level + 1)) {
        level++;
        bits >>= MS_LEVEL_BITS;
    }
    return level;
}

#ifdef MALLOC_SKIP_TOP
size_t __malloc_skip_top;
#endif

static void
_ms_init(chunk_t *ms)
{
    size_t level = _ms_new_level(_size(ms));
    size_t o;
    for (o = 0; o < level; o++)
        ms->next[o] = (chunk_t *)((uintptr_t)1);
    ms->next[o] = NULL;
}

/*
 * Find the position for 'template'. Return pointers to the pointer
 * at each level; this allows simple list modification for both
 * insert and delete
 */
void
_ms_find(const chunk_t *template, malloc_prev_t *prev)
{
    size_t    o;
    chunk_t  *next;
    chunk_t **p;

    p = &__malloc_skip_list.next[_ms_top()];

    /* For all levels */
    for (o = _ms_top();; o--) {

        /* Search at this level for the insertion point */
        while ((next = _ms_ref(*p)) != NULL) {

            /* Stop when template doesn't follow next */
            if (!_ms_greater(template, next))
                break;

            BENCH_STEP();
            p = &next->next[o];
        }

        /* Save this position */
        prev->prev[o] = p;

        /* all done ? */
        if (o == 0)
            break;

        /* Step to the previous reference */
        p--;
    }
}

/* Insert 'ms' into lists at position prev */
void
_ms_clip_in(chunk_t *ms, malloc_prev_t *prev)
{
    size_t o;

    _ms_init(ms);
    /* Insert into all levels for the new object */
    for (o = 0;; o++) {
#ifdef MALLOC_SKIP_TOP
        chunk_t **p = o <= __malloc_skip_top ? prev->prev[o] : &__malloc_skip_list.next[o];
#else
        chunk_t **p = prev->prev[o];
#endif
        _ms_set_ref(&ms->next[o], _ms_ref(*p));
        _ms_set_ref(p, ms);
        if (_ms_is_last(ms->next[o]))
            break;
    }
#ifdef MALLOC_SKIP_TOP
    if (o > __malloc_skip_top)
        __malloc_skip_top = o;
#endif
}

/* Remove 'ms' from lists at position prev */
void
_ms_clip_out(chunk_t *ms, malloc_prev_t *prev)
{
    size_t o;

    /* Delete from all levels for the old object */
    for (o = 0;; o++) {
        chunk_t *ref = ms->next[o];
        _ms_set_ref(prev->prev[o], _ms_ref(ref));
        if (_ms_is_last(ref))
            break;
    }
#ifdef MALLOC_SKIP_TOP
    while (__malloc_skip_top > 0 && __malloc_skip_list.next[__malloc_skip_top] == NULL)
        __malloc_skip_top--;
#endif
}

/* Step forward one object, updating all of the prev pointers */
void
_ms_step(chunk_t *ms, malloc_prev_t *prev)
{
    chunk_t ***p;
    chunk_t  **n;

    /*
     * Update the 'prev' pointer array to reference the current
     * object for all levels it contains.
     */
    n = ms->next;
    p = prev->prev;
    for (;;) {
        BENCH_STEP();
        *p = n;
        if (_ms_is_last(*n))
            break;
        p++;
        n++;
    }
}

#ifdef MALLOC_SKIP_API

/* This higher level API is unused by malloc */

void
_ms_insert(chunk_t *new)
{
    malloc_prev_t prev;

    _ms_find(new, &prev);
    _ms_clip_in(new, &prev);
}

bool
_ms_delete(chunk_t *old)
{
    malloc_prev_t prev;

    _ms_find(old, &prev);

    if (_ms_this(&prev) != old)
        return false;

    _ms_clip_out(old, &prev);
    return true;
}

chunk_t *
_ms_search(chunk_t *pattern)
{
    malloc_prev_t prev;
    chunk_t      *found;

    _ms_find(pattern, &prev);

    found = _ms_this(&prev);
    if (found && _ms_greater(pattern, found))
        found = NULL;
    return found;
}
#endif

#ifdef MALLOC_DEBUG
void
_ms_dump(void)
{
    chunk_t      *ms;
    malloc_prev_t prev;
    size_t        o;

    _ms_step_init(&prev);

    printf("##########\n");
    for (_ms_step_init(&prev); (ms = _ms_this(&prev)) != NULL; _ms_step(ms, &prev)) {
        printf("%p(%6zd):", ms, _size((chunk_t *)ms));

        bool pass_through = false;

        for (o = 0; o <= MS_MAX_LEVEL; o++) {
            if (pass_through)
                printf("  |  ");
            else {
                if (_ms_ref(*prev.prev[o]) != ms)
                    printf("--?--");
                else
                    printf("--+--");
                if (_ms_is_last(ms->next[o]))
                    pass_through = true;
            }
        }
        printf("\n");
    }
    printf("##########\n");
}

void
_ms_validate(void)
{
    size_t   o;
    chunk_t *ms, *next, *down;
    size_t   prev_count = 0;
    size_t   count;

    for (o = MS_MAX_LEVEL;; o--) {

        count = 0;
        /* Make sure that this chain is in order */
        for (ms = __malloc_skip_list.next[o]; ms; ms = next) {

            count++;

            next = _ms_ref(ms->next[o]);

            assert(!next || !_ms_greater(ms, next));

            if (o != 0) {
                /* Make sure we find 'next' on the next chain down */
                for (down = ms;; down = _ms_ref(down->next[o - 1])) {
                    if (down == next)
                        break;
                    assert(down != NULL);
                }
            }
        }
        /*
         * Make sure the counts are "reasonable", increasing at about
         * 4x per level
         */
        if (count >= 32) {
            if ((count && count < prev_count * 2) || (prev_count && count > prev_count * 32)) {
                printf("level %zd: %zd level %zd %zd\n", o, count, o + 1, prev_count);
            }
        }

        prev_count = count;

        if (o == 0)
            break;
    }
}
#endif /* MALLOC_DEBUG */

#endif /* __MALLOC_SKIP_LIST */

pico@malloc-skip.h

/*
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright © 2026 Keith Packard
 *
 * 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 _MALLOC_SKIP_H_
#define _MALLOC_SKIP_H_

#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>

#define MS_LEVEL_BITS 2
#define MS_LEVEL_MASK ((1 << MS_LEVEL_BITS) - 1)
#define MS_MAX_LEVEL  (30 / MS_LEVEL_BITS)

typedef struct {
    chunk_t *next[MS_MAX_LEVEL + 1];
} malloc_head_t;

typedef struct {
    chunk_t **prev[MS_MAX_LEVEL + 1];
} malloc_prev_t;

extern malloc_head_t __malloc_skip_list;

#ifdef MALLOC_SKIP_TOP
/* Highest level any live chunk currently occupies. Searches start here
 * instead of MS_MAX_LEVEL, so a short free list costs a short descent. */
extern size_t __malloc_skip_top;
#define _ms_top() __malloc_skip_top
#else
#define _ms_top() ((size_t)MS_MAX_LEVEL)
#endif

static inline size_t
_ms_size(size_t level)
{
    return (level + 1) * sizeof(chunk_t *);
}

/* Mask off the low bit from a pointer */
static inline chunk_t *
_ms_ref(chunk_t *ptr)
{
    return (chunk_t *)((uintptr_t)ptr & ~1);
}

static inline bool
_ms_greater(const chunk_t *a, const chunk_t *b)
{
    return (uintptr_t)a > (uintptr_t)b;
}

/* Store a pointer while preserving the low bit in the destination */
static inline void
_ms_set_ref(chunk_t **ref, chunk_t *ptr)
{
    *ref = (chunk_t *)(((uintptr_t)*ref & 1) | (uintptr_t)ptr);
}

static inline chunk_t *
_ms_next(chunk_t *ms)
{
    return _ms_ref(ms->next[0]);
}

static inline bool
_ms_is_last(chunk_t *ms)
{
    return ((uintptr_t)ms & 1) == 0;
}

static inline void
_ms_step_init(malloc_prev_t *prev)
{
    size_t o;

    for (o = 0; o <= _ms_top(); o++)
        prev->prev[o] = &__malloc_skip_list.next[o];
}

static inline chunk_t *
_ms_this(malloc_prev_t *prev)
{
    return _ms_ref(*prev->prev[0]);
}

void _ms_clip_in(chunk_t *ms, malloc_prev_t *prev);
void _ms_clip_out(chunk_t *ms, malloc_prev_t *prev);

void _ms_find(const chunk_t *template, malloc_prev_t *prev);
void _ms_step(chunk_t *ms, malloc_prev_t *prev);

#ifdef MALLOC_SKIP_API
/* This higher level API is unused by malloc */
void     _ms_insert(chunk_t *new);
bool     _ms_delete(chunk_t *old);
chunk_t *_ms_search(chunk_t *pattern);
#endif

#ifdef MALLOC_DEBUG
void _ms_validate(void);
void _ms_dump(void);
#else
static inline void
_ms_validate(void)
{
}
static inline void
_ms_dump(void)
{
}
#endif

#endif /* _MALLOC_SKIP_H_ */

pico@malloc.c

/*
 * Copyright (c) 2012, 2013 ARM Ltd
 * 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. The name of the company may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``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 ARM LTD 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 "local-malloc.h"

/* List header of free chunks */
#ifdef __MALLOC_SKIP_LIST
malloc_head_t __malloc_skip_list;
#else
chunk_t *__malloc_free_list;
#endif

#if __MALLOC_SMALL_BUCKET
chunk_t *__malloc_bucket_list[NUM_BUCKET_POT];
#endif

/* Starting point of memory allocated from system */
char *__malloc_sbrk_start;
char *__malloc_sbrk_top;

/*
 * Algorithm:
 *   Use sbrk() to obtain more memory and ensure the storage is
 *   MALLOC_CHUNK_ALIGN aligned. Optimise for the case that it is
 *   already aligned - only ask for extra padding after we know we
 *   need it
 */
static void *
__malloc_sbrk_aligned(size_t s)
{
    char *p, *align_p;

#ifdef __APPLE__
    /* Mac OS X 'emulates' sbrk, but the
     * parameter is int, not intptr_t or ptrdiff_t,
     */
    int d = (int)s;
    if (d < 0 || (size_t)d != s)
        return (void *)-1;
#else
    intptr_t d = (intptr_t)s;

    if (d < 0)
        return (void *)-1;
#endif
    p = sbrk(d);

    /* sbrk returns -1 if fail to allocate */
    if (p == (void *)-1)
        return p;

    __malloc_sbrk_top = (char *)((uintptr_t)p + s);

    /* Adjust returned space so that the storage area
     * is MALLOC_CHUNK_ALIGN aligned and the head is
     * MALLOC_HEAD_ALIGN aligned.
     */
    chunk_t *c = (chunk_t *)__align_up((uintptr_t)p + MALLOC_HEAD_SIZE, MALLOC_CHUNK_ALIGN);

    /* And convert back to where the head will be */
    align_p = chunk_to_blob(c);

    if (align_p != p) {
        /* p is not aligned, ask for a few more bytes so that we have
         * s bytes reserved from align_p. This should only occur for
         * the first sbrk in a chunk of memory as all others should be
         * aligned to the right value as chunk sizes are selected to
         * make them abut in memory
         */
        intptr_t adjust = align_p - p;
        char    *extra = sbrk(adjust);
        if (extra != (char *)((uintptr_t)p + s))
            return (void *)-1;
        __malloc_sbrk_top = extra + adjust;
    }
    if (__malloc_sbrk_start == NULL)
        __malloc_sbrk_start = align_p;

    return align_p;
}

bool
__malloc_grow_chunk(chunk_t *c, size_t new_size)
{
    char *chunk_e = chunk_end(c);

    if (chunk_e != __malloc_sbrk_top)
        return false;
    size_t add_size = MAX(MALLOC_SPLIT_MIN, new_size - _size(c));

    /* Ask for the extra memory needed */
    char  *heap = __malloc_sbrk_aligned(add_size);

    /* Check if we got what we wanted */
    if (heap == chunk_e) {
        /* Set size and return */
        *_size_ref(c) += add_size;
        return true;
    }

    if (heap != (char *)-1) {
        /* sbrk returned unexpected memory, free it */
        make_free_chunk(blob_to_chunk(heap), add_size);
    }
    return false;
}

/** Function malloc
 * Algorithm:
 *   Walk through the free list to find the first match. If fails to find
 *   one, call sbrk to allocate a new chunk_t.
 */
void * __disable_sanitizer
malloc(size_t s)
{
    chunk_t *c;
    char    *ptr;
    size_t   alloc_size;

    if (s > MALLOC_ALLOC_MAX) {
        errno = ENOMEM;
        return NULL;
    }

    alloc_size = chunk_size(s);

    MALLOC_LOCK;

#if __MALLOC_SMALL_BUCKET
    /* Small allocations use the bucket allocator */
    if (alloc_size <= MALLOC_MAX_BUCKET) {
        int       bucket = BUCKET_NUM(alloc_size);
        chunk_t **p;

        alloc_size = BUCKET_SIZE(bucket);
        p = &__malloc_bucket_list[bucket];
        if ((c = *p) != NULL)
            *p = __next_bucket(c);
    } else
#endif
#if defined(MALLOC_SCAN_MACRO)
    /*
     * Same idea as MALLOC_SKIP_FASTSCAN, expressed through the free-list
     * abstraction so one loop serves both designs: the scan does not
     * maintain prev[], and _ms_locate() materializes it for the winner
     * (a no-op for the linked list, which tracked it along the way).
     */
    {
        malloc_prev_t prev;

        for (c = _ms_scan_first(&prev); c != NULL; c = _ms_scan_next(c, &prev)) {
            if (_size(c) >= alloc_size) {
                size_t rem = _size(c) - alloc_size;

                _ms_locate(c, &prev);

                if (rem >= MALLOC_SPLIT_MIN) {
                    _ms_clip_out(c, &prev);

                    chunk_t *s = (chunk_t *)((char *)c + alloc_size);
                    _set_size(c, alloc_size);
                    _set_size(s, rem);
                    _mark_free(s);

#if __MALLOC_SMALL_BUCKET
                    if (rem <= MALLOC_MAX_BUCKET) {
                        int    bucket = BUCKET_NUM(rem);
                        size_t bucket_size = BUCKET_SIZE(bucket);
                        if (rem == bucket_size) {
                            __next_bucket(s) = __malloc_bucket_list[bucket];
                            __malloc_bucket_list[bucket] = s;
                            break;
                        }
                    }
#endif
                    _ms_clip_in(s, &prev);
                } else {
                    _ms_clip_out(c, &prev);
                }
                break;
            }
            if (!__next_chunk(c) && __malloc_grow_chunk(c, alloc_size)) {
                _ms_locate(c, &prev);
                _ms_clip_out(c, &prev);
                break;
            }
        }
    }
#elif defined(__MALLOC_SKIP_LIST) && defined(MALLOC_SKIP_FASTSCAN)
    /*
     * First-fit is a level-0 walk no matter what the free list looks
     * like, so don't pay _ms_step's per-level prev[] maintenance for
     * every chunk we reject. Scan with a plain next pointer and rebuild
     * prev[] with a single O(log N) _ms_find once we have a winner.
     */
    {
        malloc_prev_t prev;
        bool          grown = false;

        for (c = _ms_ref(__malloc_skip_list.next[0]); c != NULL; c = _ms_next(c)) {
            BENCH_STEP();
            if (_size(c) >= alloc_size)
                break;
            if (!_ms_next(c) && __malloc_grow_chunk(c, alloc_size)) {
                grown = true;
                break;
            }
        }

        if (c != NULL) {
            size_t rem = _size(c) - alloc_size;

            _ms_find(c, &prev);

            if (!grown && rem >= MALLOC_SPLIT_MIN) {
                _ms_clip_out(c, &prev);

                chunk_t *s = (chunk_t *)((char *)c + alloc_size);
                _set_size(c, alloc_size);
                _set_size(s, rem);
                _mark_free(s);

#if __MALLOC_SMALL_BUCKET
                int    bucket = BUCKET_NUM(rem);
                if (rem > MALLOC_MAX_BUCKET || rem != BUCKET_SIZE(bucket)) {
                    _ms_clip_in(s, &prev);
                } else {
                    __next_bucket(s) = __malloc_bucket_list[bucket];
                    __malloc_bucket_list[bucket] = s;
                }
#else
                _ms_clip_in(s, &prev);
#endif
            } else {
                _ms_clip_out(c, &prev);
            }
        }
    }
#else
    {
        malloc_prev_t prev;
        for (_ms_step_init(&prev); (c = _ms_this(&prev)) != NULL; _ms_step(c, &prev)) {
            if (_size(c) >= alloc_size) {
                size_t rem = _size(c) - alloc_size;

                if (rem >= MALLOC_SPLIT_MIN) {
                    /* Find a chunk_t that much larger than required size, break
                     * it into two chunks and return the first one
                     */

                    _ms_clip_out(c, &prev);

                    chunk_t *s = (chunk_t *)((char *)c + alloc_size);
                    _set_size(c, alloc_size);
                    _set_size(s, rem);
                    _mark_free(s);

#if __MALLOC_SMALL_BUCKET
                    /*
                     * If the remainder fits a bucket, link it there
                     * rather than into the general list
                     */
                    if (rem <= MALLOC_MAX_BUCKET) {
                        int    bucket = BUCKET_NUM(rem);
                        size_t bucket_size = BUCKET_SIZE(bucket);
                        if (rem == bucket_size) {
                            /* insert into bucket list */
                            __next_bucket(s) = __malloc_bucket_list[bucket];
                            __malloc_bucket_list[bucket] = s;
                            break;
                        }
                    }
#endif

                    _ms_clip_in(s, &prev);
                } else {
                    /* Find a chunk_t that is exactly the size or slightly bigger
                     * than requested size, just return this chunk_t
                     */
                    _ms_clip_out(c, &prev);
                }
                break;
            }
            if (!__next_chunk(c) && __malloc_grow_chunk(c, alloc_size)) {
                /*
                 * Grew the last chunk in memory to the requested size,
                 * just return it
                 */
                _ms_clip_out(c, &prev);
                break;
            }
        }
    }
#endif

    /* Failed to find a appropriate chunk_t. Ask for more memory */
    if (c == NULL) {

#if defined(__MALLOC_SKIP_LIST) && defined(MALLOC_SKIP_LEVELUP)
        /*
         * Avoid a large number of tiny allocations making our skip list
         * too flat by randomly increasing chunk sizes using our skip
         * list allocation scheme
         */
        size_t need_size = chunk_size(_ms_size(MS_MAX_LEVEL));
        if (alloc_size < need_size) {
            long   bits = random();
            size_t level = 0;
            while (!(bits & MS_LEVEL_MASK) && level < MS_MAX_LEVEL) {
                level++;
                bits >>= MS_LEVEL_BITS;
            }
            size_t need_size = chunk_size(_ms_size(level));
            if (alloc_size < need_size)
                alloc_size = need_size;
        }
#endif
        void *blob = __malloc_sbrk_aligned(alloc_size);

        /* sbrk returns -1 if fail to allocate */
        if (blob == (void *)-1) {
            errno = ENOMEM;
            MALLOC_UNLOCK;
            return NULL;
        }
        c = blob_to_chunk(blob);
        _set_size(c, alloc_size);
    }

    MALLOC_UNLOCK;

    _mark_busy(c);

    ptr = chunk_to_ptr(c);

    memset(ptr, '\0', alloc_size - MALLOC_HEAD_SIZE);

    return ptr;
}

#ifdef __strong_reference
#if defined(__GNUCLIKE_PRAGMA_DIAGNOSTIC) && !defined(__clang__)
#pragma GCC diagnostic ignored "-Wmissing-attributes"
#endif
__strong_reference(malloc, __malloc_malloc);
#endif

#if MALLOC_DEBUG

#include <assert.h>

void
__malloc_validate_chunk(chunk_t *c)
{
    assert(__align_up(chunk_to_ptr(c), MALLOC_CHUNK_ALIGN) == chunk_to_ptr(c));
    assert(__align_up(c, MALLOC_HEAD_ALIGN) == c);
    assert(_size(c) >= MALLOC_CHUNK_MIN);
    assert(_size(c) < MALLOC_CHUNK_MAX);
    assert(__align_up(_size(c), MALLOC_HEAD_ALIGN) == _size(c));
}

void
__malloc_validate(void)
{
    chunk_t *c;

    for (c = __malloc_free_list; c; c = __next_chunk(c)) {
        assert(_is_free(c));
        __malloc_validate_chunk(c);
#if __MALLOC_SMALL_BUCKET
        size_t s = _size(c);
        size_t max_bucket = MALLOC_MAX_BUCKET;
        int    bucket = BUCKET_NUM(s);
        size_t bucket_size = BUCKET_SIZE(bucket);
        assert(s > max_bucket || s != bucket_size);
#endif
        assert(__next_chunk(c) == NULL || chunk_after(c) <= __next_chunk(c));
    }
#if __MALLOC_SMALL_BUCKET
    size_t b;

    for (b = 0; b < NUM_BUCKET_POT; b++) {
        for (c = __malloc_bucket_list[b]; c; c = __next_bucket(c)) {
            assert(_is_free(c));
            __malloc_validate_chunk(c);
            assert(_size(c) == BUCKET_SIZE(b));
        }
    }
#endif
#ifdef __MALLOC_SKIP_LIST
    _ms_validate();
#endif
}

#endif

pico@realloc.c

/*
 * Copyright (c) 2012, 2013 ARM Ltd
 * 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. The name of the company may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``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 ARM LTD 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 "local-malloc.h"

/*
 * Implement either by merging adjacent free memory
 * or by calling malloc/memcpy
 */
void * __disable_sanitizer
realloc(void *ptr, size_t size)
{
    void *mem;

    if (ptr == NULL)
        return malloc(size);

    if (size == 0) {
        free(ptr);
        return NULL;
    }

    if (size > MALLOC_ALLOC_MAX) {
        errno = ENOMEM;
        return NULL;
    }

    if (!_check_busy(ptr, "realloc: already freed\n"))
        return NULL;

    size_t   new_size = chunk_size(size);

    chunk_t *p_to_realloc = ptr_to_chunk(ptr);

#if MALLOC_DEBUG
    assert(!_is_free(p_to_realloc));
    __malloc_validate_chunk(p_to_realloc);
#endif

    size_t old_size = _size(p_to_realloc);

#if __MALLOC_SMALL_BUCKET
    bool is_bucket;
    is_bucket = (old_size <= MALLOC_MAX_BUCKET && old_size == BUCKET_SIZE(BUCKET_NUM(old_size)));
#else
#define is_bucket 0
#endif

    /* See if we can avoid allocating new memory
     * when increasing the size
     */
    if (!is_bucket && new_size > old_size) {
        void *chunk_e = chunk_end(p_to_realloc);

        MALLOC_LOCK;

        if (__malloc_grow_chunk(p_to_realloc, new_size)) {
            /* clear new memory */
            memset(chunk_e, '\0', new_size - old_size);
            /* update size */
            old_size = _size(p_to_realloc);
        } else {
            /*
             * Check to see if there's a chunk_t of free space just
             * past the current chunk, merge it in in case that's
             * useful
             */
            chunk_t      *c;
            malloc_prev_t prev;
#ifdef __MALLOC_SKIP_LIST
            _ms_find(p_to_realloc, &prev);
            c = _ms_this(&prev);
#else
            for (_ms_step_init(&prev); (c = _ms_this(&prev)) != NULL; _ms_step(c, &prev)) {
                if (p_to_realloc < c)
                    break;
            }
#endif
            if (c && chunk_to_blob(c) == chunk_e) {
                size_t c_size = _size(c);
                if (old_size + c_size >= new_size) {

                    /* Remove c from the free list */
                    _ms_clip_out(c, &prev);

                    /* clear the memory from c */
                    memset(chunk_to_blob(c), 0, new_size - old_size);

                    /* add it's size to our chunk */
                    old_size += c_size;
                    _set_size(p_to_realloc, old_size);
                    MALLOC_UNLOCK;
                    goto add_leftover;
                }
            }
        }

        MALLOC_UNLOCK;
    }

    if (new_size <= old_size) {

#ifdef __MALLOC_CLEAR_FREED
        memset((char *)ptr + size, 0, old_size - size);
#endif

    add_leftover:;
        /* If there's enough space left over, split it out
         * and free it
         */
        size_t extra = old_size - new_size;

        if (!is_bucket && extra >= MALLOC_SPLIT_MIN) {
            _set_size(p_to_realloc, new_size);
            make_free_chunk(chunk_after(p_to_realloc), extra);
        }
        return ptr;
    }
    /* No short cuts, allocate new memory and copy */

    mem = malloc(size);
    if (!mem)
        return NULL;

    memcpy(mem, ptr, malloc_size(old_size));
    free(ptr);

    return mem;
}

results@env.txt

# toolchain
/home/jserv/riscv/toolchain/bin/riscv64-unknown-linux-gnu-gcc
riscv64-unknown-linux-gnu-gcc (g04696df09) 14.2.0

# target
Linux 6.18.3-generic
model name	: Spacemit(R) X100
isa		: rv64imafdcvh_zicbom_zicbop_zicboz_zicntr_zicond_zicsr_zifencei_zihintntl_zihintpause_zihpm_zimop_zaamo_zalrsc_zawrs_zfa_zfh_zfhmin_zca_zcb_zcd_zcmop_zba_zbb_zbc_zbs_zkt_zvbb_zvbc_zve32f_zve32x_zve64d_zve64f_zve64x_zvfh_zvfhmin_zvkb_zvkg_zvkned_zvknha_zvknhb_zvksed_zvksh_zvkt_smaia_smstateen_ssaia_sscofpmf_sstc_svinval_svnapot_svpbmt_sdtrig
cpus: 8
MemTotal:       16355032 kB
L1 Instruction 64K
L1 Data 64K
L2 Unified 4096K
governor: userspace @ 2200000 kHz

results@results.csv

results@scan-variants.csv

results@tables.md

Cells marked * varied by more than 20% across trials.

payload 32 B

free_rand: ns/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	72*	222	875	7,071	30,593	268,899
skip	193	207	250	269	306*	750
skip-fast	202	196*	245	264	300*	738
skip-top	139*	163	194	248	280*	715
skip-fast-top	123*	164	205	274	299*	713
skip-lvl	187	198*	232	242	286	731
list-b512	44*	52*	64	70	64*	92
skip-b512	40*	54*	64*	72	64*	92
skip-fast-b512	42*	51*	62*	72*	66*	94

free_rand: free-list steps/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	14.9	63.4	257.7	1,021.5	4,089.3	16,353.6
skip	5.0	8.4	11.5	14.7	26.0	72.9
skip-fast	5.0	8.4	11.5	14.7	26.0	72.9
skip-top	5.0	8.4	11.5	14.7	26.0	72.9
skip-fast-top	5.0	8.4	11.5	14.7	26.0	72.9
skip-lvl	4.0	5.6	10.7	14.9	25.6	76.9
list-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast-b512	0.0	0.0	0.0	0.0	0.0	0.0

free_rand: heap KiB

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	6	24	96	384	1,536	6,144
skip	6	24	96	384	1,536	6,144
skip-fast	6	24	96	384	1,536	6,144
skip-top	6	24	96	384	1,536	6,144
skip-fast-top	6	24	96	384	1,536	6,144
skip-lvl	6	24	96	384	1,536	6,146
list-b512	6	24	96	384	1,536	6,144
skip-b512	6	24	96	384	1,536	6,144
skip-fast-b512	6	24	96	384	1,536	6,144

free_asc: ns/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	111*	308*	1,528	8,150	35,961	330,339
skip	130*	148*	121*	153	234*	665
skip-fast	117*	120*	129*	141*	211*	633
skip-top	97*	102*	95*	115	197	628
skip-fast-top	102*	102*	91*	143*	187*	618
skip-lvl	167*	108*	119*	149	225	607*
list-b512	18*	20*	25*	28*	23*	32
skip-b512	20*	20*	28*	30*	24*	33
skip-fast-b512	20*	22*	29*	30*	24*	32

free_asc: free-list steps/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	31.5	127.5	511.5	2,047.5	8,191.5	32,767.5
skip	7.1	13.6	12.2	19.8	51.0	145.2
skip-fast	7.1	13.6	12.2	19.8	51.0	145.2
skip-top	7.1	13.6	12.2	19.8	51.0	145.2
skip-fast-top	7.1	13.6	12.2	19.8	51.0	145.2
skip-lvl	6.5	9.2	12.8	21.8	46.5	155.5
list-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast-b512	0.0	0.0	0.0	0.0	0.0	0.0

free_asc: heap KiB

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	6	24	96	384	1,536	6,144
skip	6	24	96	384	1,536	6,144
skip-fast	6	24	96	384	1,536	6,144
skip-top	6	24	96	384	1,536	6,144
skip-fast-top	6	24	96	384	1,536	6,144
skip-lvl	6	24	96	384	1,536	6,146
list-b512	6	24	96	384	1,536	6,144
skip-b512	6	24	96	384	1,536	6,144
skip-fast-b512	6	24	96	384	1,536	6,144

free_desc: ns/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	6*	6*	7	16*	20	25*
skip	66*	59	61	63	63	63
skip-fast	55	54	55	54	54	54
skip-top	43*	38	34	36	36*	36*
skip-fast-top	45*	41	43	44*	45	43*
skip-lvl	59	57	58	60	63	65
list-b512	8*	8	8	19*	23	33*
skip-b512	8*	8	7	20*	23	34
skip-fast-b512	8	8	8	16*	23	32*

free_desc: free-list steps/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	0.0	0.0	0.0	0.0	0.0	0.0
skip	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast	0.0	0.0	0.0	0.0	0.0	0.0
skip-top	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast-top	0.0	0.0	0.0	0.0	0.0	0.0
skip-lvl	0.0	0.0	0.0	0.0	0.0	0.0
list-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast-b512	0.0	0.0	0.0	0.0	0.0	0.0

free_desc: heap KiB

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	6	24	96	384	1,536	6,144
skip	6	24	96	384	1,536	6,144
skip-fast	6	24	96	384	1,536	6,144
skip-top	6	24	96	384	1,536	6,144
skip-fast-top	6	24	96	384	1,536	6,144
skip-lvl	6	24	96	384	1,536	6,146
list-b512	6	24	96	384	1,536	6,144
skip-b512	6	24	96	384	1,536	6,144
skip-fast-b512	6	24	96	384	1,536	6,144

malloc_miss: ns/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	284*	650	5,496*	30,094	135,451	1,060,568*
skip	520	1,628	7,258	33,251	139,411	942,297
skip-fast	299*	706	4,414*	13,962*	67,851	927,972*
skip-top	469	1,488	6,890	32,229	133,749	1,064,412*
skip-fast-top	303	720	4,355*	13,976	58,032	948,450*
skip-lvl	525	1,613	7,215	37,266	159,109	1,309,922
list-b512	169*	160	157	159	158	160
skip-b512	172*	165	164	168	165	165
skip-fast-b512	162*	156	155	154	157	156

malloc_miss: free-list steps/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	63.0	255.0	1,023.0	4,095.0	16,383.0	65,535.0
skip	77.0	323.0	1,349.0	5,410.0	21,881.0	87,341.0
skip-fast	63.2	255.0	1,023.0	4,095.0	16,383.0	65,535.1
skip-top	77.0	323.0	1,349.0	5,410.0	21,881.0	87,341.0
skip-fast-top	63.2	255.0	1,023.0	4,095.0	16,383.0	65,535.1
skip-lvl	88.0	329.0	1,349.0	5,320.0	21,813.0	87,138.0
list-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast-b512	0.0	0.0	0.0	0.0	0.0	0.0

malloc_miss: heap KiB

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	150	603	2,415	4,915	6,067	10,675
skip	150	603	2,415	4,915	6,067	10,675
skip-fast	150	603	2,415	4,915	6,067	10,675
skip-top	150	603	2,415	4,915	6,067	10,675
skip-fast-top	150	603	2,415	4,915	6,067	10,675
skip-lvl	150	603	2,415	4,915	6,067	10,677
list-b512	151	604	2,416	4,915	6,067	10,675
skip-b512	151	604	2,416	4,915	6,067	10,675
skip-fast-b512	151	604	2,416	4,915	6,067	10,675

churn: ns/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	107	319	3,066	14,373	65,859	1,178,878
skip	167	429	1,781	8,586	51,309	439,442
skip-fast	127	258	1,088	5,145	21,446	569,063
skip-top	149	386	1,724	8,316	48,763	442,702
skip-fast-top	114	249	1,048	4,964	21,969	598,204
skip-lvl	165	428	1,784	9,036	56,956	603,921
list-b512	30	30	31	35	58*	102
skip-b512	30	30	31	35	58*	102
skip-fast-b512	30	31	31	35	58	102

churn: free-list steps/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	36.3	145.4	578.5	2,300.6	9,463.4	38,949.0
skip	23.9	87.2	345.9	1,351.0	7,973.8	44,027.2
skip-fast	21.5	75.4	263.3	1,039.4	6,044.1	33,085.4
skip-top	23.9	87.2	345.9	1,351.0	7,973.8	44,027.2
skip-fast-top	21.5	75.4	263.3	1,039.4	6,044.1	33,085.4
skip-lvl	24.2	83.0	335.7	1,370.9	8,005.4	43,875.7
list-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-b512	0.0	0.0	0.0	0.0	0.0	0.0
skip-fast-b512	0.0	0.0	0.0	0.0	0.0	0.0

churn: heap KiB

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	8	32	124	489	1,880	6,827
skip	9	36	137	523	1,883	6,827
skip-fast	9	36	137	523	1,883	6,827
skip-top	9	36	137	523	1,883	6,827
skip-fast-top	9	36	137	523	1,883	6,827
skip-lvl	9	36	137	523	1,883	6,825
list-b512	10	35	134	523	1,969	7,020
skip-b512	10	35	134	523	1,969	7,020
skip-fast-b512	10	35	134	523	1,969	7,020

realloc_grow: ns/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	559	1,549	12,908	59,391	250,682	2,846,225
skip	424	824	2,910	12,457	51,698	307,858
skip-fast	311	495	1,788	5,761	22,248	493,316*
skip-top	372	743	2,786	12,083	49,041	325,223
skip-fast-top	280	461	2,060	5,602	24,256	513,746
skip-lvl	414	822	2,947	14,035	57,218	468,207
list-b512	562	568	573	573	567	575
skip-b512	472	478	475	477	477	484
skip-fast-b512	421	421	423	425	422	424

realloc_grow: free-list steps/op

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	213.3	765.7	2,968.3	11,778.5	47,019.5	187,983.5
skip	52.3	151.8	522.0	2,014.4	8,005.8	32,203.2
skip-fast	46.0	123.4	404.7	1,533.3	6,092.8	24,288.3
skip-top	52.3	151.8	522.0	2,014.4	8,005.8	32,203.2
skip-fast-top	46.0	123.4	404.7	1,533.3	6,092.8	24,288.3
skip-lvl	55.7	148.8	526.0	2,011.8	8,001.7	35,126.0
list-b512	141.2	141.2	141.2	141.2	141.2	141.2
skip-b512	64.3	64.3	64.3	64.3	64.3	64.3
skip-fast-b512	55.7	55.7	55.7	55.7	55.7	55.7

realloc_grow: heap KiB

variant	N=64	N=256	N=1024	N=4096	N=16384	N=65536
list	171	188	260	548	1,700	6,308
skip	187	213	285	573	1,725	6,333
skip-fast	187	213	285	573	1,725	6,333
skip-top	187	213	285	573	1,725	6,333
skip-fast-top	187	213	285	573	1,725	6,333
skip-lvl	187	213	285	573	1,725	6,328
list-b512	426	444	516	804	1,956	6,564
skip-b512	428	446	518	806	1,958	6,566
skip-fast-b512	428	446	518	806	1,958	6,566

src@arena.c

/* Backing store for the extracted picolibc allocator: a pre-faulted
 * mmap region handed out by a bump-pointer sbrk, plus heap reset so the
 * same process can run many trials from a clean heap.
 */
#include <sys/mman.h>
#include <stdio.h>
#include <string.h>
#include "pico/local-malloc.h"

#define ARENA_SZ (512UL << 20)

static char *arena_base, *arena_cur, *arena_end;
static size_t reset_count;

/* Successive heaps start at different offsets in the arena. All trials
 * in a process share one mapping, so without this they would all inherit
 * the same physical page layout, and its cache colouring would bias
 * every trial of that variant the same way. */
#define HEAP_STRIDE (1UL << 20)
#define HEAP_SLOTS  8

#ifdef BENCH_COUNT
unsigned long bench_steps;
#endif

long
__pico_random(void)
{
    static uint64_t next = 1;
    next = next * 6364136223846793005ULL + 1;
    return (long)((next >> 32) & 0x7fffffffL);
}

void *
__pico_sbrk(intptr_t inc)
{
    char *old = arena_cur;

    if (inc < 0 || (size_t)(arena_end - arena_cur) < (size_t)inc)
        return (void *)-1;
    arena_cur = old + inc;
    return old;
}

void
heap_reset(void)
{
    if (!arena_base) {
        arena_base = mmap(NULL, ARENA_SZ, PROT_READ | PROT_WRITE,
                          MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE, -1, 0);
        if (arena_base == MAP_FAILED) {
            perror("mmap");
            exit(1);
        }
        arena_end = arena_base + ARENA_SZ;
    }
    arena_cur = arena_base + (reset_count++ % HEAP_SLOTS) * HEAP_STRIDE;
    __malloc_sbrk_start = NULL;
    __malloc_sbrk_top = NULL;
#ifdef __MALLOC_SKIP_LIST
    memset(&__malloc_skip_list, 0, sizeof(__malloc_skip_list));
#else
    __malloc_free_list = NULL;
#endif
#if __MALLOC_SMALL_BUCKET
    memset(__malloc_bucket_list, 0, sizeof(__malloc_bucket_list));
#endif
}

size_t
heap_used(void)
{
    if (__malloc_sbrk_start == NULL)
        return 0;
    return (size_t)(arena_cur - __malloc_sbrk_start);
}

/* Free-list length at level 0 -- the list both variants must walk on
 * a first-fit malloc. */
size_t
heap_free_count(void)
{
    size_t   n = 0;
    chunk_t *c;

    for (c = __malloc_free_list; c; c = __next_chunk(c))
        n++;
    return n;
}

src@bench.c

/* Benchmark driver for the extracted picolibc allocator.
 *
 * usage: bench <variant-name> <N> <payload-size> [workload]
 * emits CSV: variant,workload,n,size,ns_per_op,spread_pct,steps_per_op,heap_kb,free_len
 *
 * All workloads build the same starting state: 2N chunks allocated back
 * to back, every other one freed. The live chunks stop coalescing, so the
 * free list really does hold N entries -- that is the length both the
 * linked list and the skip list have to search.
 *
 * Reported time is the median of TRIALS, with the spread between the
 * fastest and slowest trial alongside it: at heap sizes past last-level
 * cache the physical page layout of the arena moves the result more than
 * the allocator does, and hiding that behind a minimum would make the
 * comparison look sharper than it is.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>

void  *__pico_malloc(size_t);
void   __pico_free(void *);
void  *__pico_realloc(void *, size_t);
void   heap_reset(void);
size_t heap_used(void);
size_t heap_free_count(void);

#ifdef BENCH_COUNT
extern unsigned long bench_steps;
#else
static unsigned long bench_steps;
#endif

#ifndef TRIALS
#ifdef BENCH_COUNT
/* Step counts are deterministic; repeating them buys nothing. */
#define TRIALS 1
#else
#define TRIALS 5
#endif
#endif

#define MAX_N (1 << 17)

static void  *blk[2 * MAX_N];
static void  *live[MAX_N];
static size_t order[MAX_N];

static uint64_t rng_state;

static void
rng_seed(uint64_t s)
{
    rng_state = s ? s : 1;
}

static uint32_t
rnd(void)
{
    rng_state ^= rng_state << 13;
    rng_state ^= rng_state >> 7;
    rng_state ^= rng_state << 17;
    return (uint32_t)(rng_state >> 32);
}

static double
now_ns(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1e9 + ts.tv_nsec;
}

/* Allocate 2N chunks; blk[] holds them all, the odd ones are the
 * to-be-freed holes in the order given by order[]. */
static void
build(size_t n, size_t size)
{
    size_t i;

    heap_reset();
    for (i = 0; i < 2 * n; i++)
        blk[i] = __pico_malloc(size);
    for (i = 0; i < n; i++)
        order[i] = 2 * i + 1;
}

static void
shuffle(size_t n)
{
    size_t i, j, t;

    for (i = n; i > 1; i--) {
        j = rnd() % i;
        t = order[i - 1];
        order[i - 1] = order[j];
        order[j] = t;
    }
}

static void
reverse(size_t n)
{
    size_t i, t;

    for (i = 0; i < n / 2; i++) {
        t = order[i];
        order[i] = order[n - 1 - i];
        order[n - 1 - i] = t;
    }
}

struct result {
    double sample[TRIALS];
    int    nsample;
    double ns;     /* per op, median of the trials */
    double spread; /* (slowest - fastest) / median, percent */
    double steps;  /* per op */
    size_t heap;
    size_t len;
};

static void
add_sample(struct result *r, double ns_per_op)
{
    r->sample[r->nsample++] = ns_per_op;
}

static void
summarize(struct result *r)
{
    int i, j;

    for (i = 1; i < TRIALS && i < r->nsample; i++) { /* insertion sort, nsample is tiny */
        double v = r->sample[i];
        for (j = i - 1; j >= 0 && r->sample[j] > v; j--)
            r->sample[j + 1] = r->sample[j];
        r->sample[j + 1] = v;
    }
    r->ns = r->sample[r->nsample / 2];
    r->spread = r->ns > 0 ? (r->sample[r->nsample - 1] - r->sample[0]) / r->ns * 100.0 : 0.0;
}

static void
report(const char *variant, const char *what, size_t n, size_t size, struct result *r)
{
    summarize(r);
    printf("%s,%s,%zu,%zu,%.1f,%.1f,%.2f,%zu,%zu\n", variant, what, n, size, r->ns, r->spread,
           r->steps, r->heap / 1024, r->len);
    fflush(stdout);
}

/* Time the N frees that build the hole pattern, in the given order. */
static struct result
bench_free(size_t n, size_t size, int mode)
{
    struct result r = { 0 };
    int           t;

    for (t = 0; t < TRIALS; t++) {
        size_t i;

        build(n, size);
        rng_seed(12345);
        if (mode == 0)
            shuffle(n);
        else if (mode == 2)
            reverse(n);

        bench_steps = 0;
        double t0 = now_ns();
        for (i = 0; i < n; i++)
            __pico_free(blk[order[i]]);
        add_sample(&r, (now_ns() - t0) / (double)n);

        r.steps = (double)bench_steps / (double)n;
        r.heap = heap_used();
        r.len = heap_free_count();
    }
    return r;
}

/* Prepare the fragmented heap every scanning workload starts from. */
static void
build_holes(size_t n, size_t size)
{
    size_t i;

    build(n, size);
    rng_seed(12345);
    shuffle(n);
    for (i = 0; i < n; i++)
        __pico_free(blk[order[i]]);
}

/* First-fit misses: every hole is too small, so malloc walks the whole
 * free list before falling back to sbrk.
 *
 * The request has to clear the small-bucket threshold as well, or the
 * bucket variants would answer it from a bucket and this would compare
 * a list walk against a linked-list pop. MALLOC_MAX_BUCKET tops out at
 * 1024 + header in picolibc's configuration space.
 */
#define MISS_SIZE(size) ((size) * 8 + 2048)

static struct result
bench_malloc_miss(size_t n, size_t size)
{
    struct result r = { 0 };
    size_t        k = n < 2000 ? n : 2000;
    int           t;

    for (t = 0; t < TRIALS; t++) {
        size_t i;

        build_holes(n, size);

        bench_steps = 0;
        double t0 = now_ns();
        for (i = 0; i < k; i++)
            live[i] = __pico_malloc(MISS_SIZE(size));
        add_sample(&r, (now_ns() - t0) / (double)k);

        r.steps = (double)bench_steps / (double)k;
        r.heap = heap_used();
        r.len = heap_free_count();
    }
    return r;
}

/* Steady-state churn against a fragmented heap. */
static struct result
bench_churn(size_t n, size_t size)
{
    struct result r = { 0 };
    size_t        m = n <= 4096 ? 200000 : 20000;
    int           t;

    for (t = 0; t < TRIALS; t++) {
        size_t i;

        build_holes(n, size);
        for (i = 0; i < n; i++)
            live[i] = NULL;

        bench_steps = 0;
        double t0 = now_ns();
        for (i = 0; i < m; i++) {
            size_t s = rnd() % n;
            if (live[s]) {
                __pico_free(live[s]);
                live[s] = NULL;
            } else {
                live[s] = __pico_malloc(16 + (rnd() % (size * 2)));
            }
        }
        add_sample(&r, (now_ns() - t0) / (double)m);

        r.steps = (double)bench_steps / (double)m;
        r.heap = heap_used();
        r.len = heap_free_count();
    }
    return r;
}

/* realloc growth against a fragmented heap: each call has to locate the
 * neighbouring free chunk. */
static struct result
bench_realloc(size_t n, size_t size)
{
    struct result r = { 0 };
    size_t        objs = 64;
    size_t        steps = 64;
    int           t;

    for (t = 0; t < TRIALS; t++) {
        size_t i, j;

        build_holes(n, size);
        for (i = 0; i < objs; i++)
            live[i] = __pico_malloc(32);

        bench_steps = 0;
        double t0 = now_ns();
        for (j = 1; j <= steps; j++)
            for (i = 0; i < objs; i++)
                live[i] = __pico_realloc(live[i], 32 + j * 32);
        add_sample(&r, (now_ns() - t0) / (double)(objs * steps));

        r.steps = (double)bench_steps / (double)(objs * steps);
        r.heap = heap_used();
        r.len = heap_free_count();
    }
    return r;
}

int
main(int argc, char **argv)
{
    const char   *variant = argc > 1 ? argv[1] : "unknown";
    size_t        n = argc > 2 ? strtoul(argv[2], NULL, 0) : 4096;
    size_t        size = argc > 3 ? strtoul(argv[3], NULL, 0) : 32;
    const char   *only = argc > 4 ? argv[4] : "all";
    struct result r;

    if (n > MAX_N) {
        fprintf(stderr, "N too large\n");
        return 1;
    }

#define WANT(w) (!strcmp(only, "all") || !strcmp(only, w))
    if (WANT("free_rand")) {
        r = bench_free(n, size, 0);
        report(variant, "free_rand", n, size, &r);
    }
    if (WANT("free_asc")) {
        r = bench_free(n, size, 1);
        report(variant, "free_asc", n, size, &r);
    }
    if (WANT("free_desc")) {
        r = bench_free(n, size, 2);
        report(variant, "free_desc", n, size, &r);
    }
    if (WANT("malloc_miss")) {
        r = bench_malloc_miss(n, size);
        report(variant, "malloc_miss", n, size, &r);
    }
    if (WANT("churn")) {
        r = bench_churn(n, size);
        report(variant, "churn", n, size, &r);
    }
    if (WANT("realloc_grow")) {
        r = bench_realloc(n, size);
        report(variant, "realloc_grow", n, size, &r);
    }
    return 0;
}

src@check.c

/* Randomized correctness check for the extracted allocator.
 * Catches overlapping allocations, lost zeroing, and realloc that fails
 * to preserve contents -- the ways a broken free-list walk shows up.
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stddef.h>

void  *__pico_malloc(size_t);
void   __pico_free(void *);
void  *__pico_realloc(void *, size_t);
void   heap_reset(void);
size_t heap_used(void);

#define SLOTS 512
#define OPS   2000000

static unsigned char *p[SLOTS];
static size_t         sz[SLOTS];
static uint64_t       st = 88172645463325252ULL;
static long           stale;

static uint32_t
rnd(void)
{
    st ^= st << 13;
    st ^= st >> 7;
    st ^= st << 17;
    return (uint32_t)(st >> 32);
}

static unsigned char
tag(int i)
{
    return (unsigned char)(i * 7 + 1);
}

static void
verify(int i)
{
    size_t j;

    for (j = 0; j < sz[i]; j++)
        if (p[i][j] != tag(i)) {
            fprintf(stderr, "corrupt slot %d at %zu: %02x != %02x\n", i, j, p[i][j], tag(i));
            abort();
        }
}

int
main(void)
{
    long i;

    heap_reset();

    for (i = 0; i < OPS; i++) {
        int    s = rnd() % SLOTS;
        size_t n;

        switch (rnd() % 4) {
        case 0: /* alloc */
            if (p[s])
                break;
            n = 1 + rnd() % 700;
            p[s] = __pico_malloc(n);
            assert(p[s] != NULL);
            assert(((uintptr_t)p[s] & (_Alignof(max_align_t) - 1)) == 0);
            for (size_t j = 0; j < n; j++)
                assert(p[s][j] == 0); /* picolibc malloc zeroes */
            memset(p[s], tag(s), n);
            sz[s] = n;
            break;
        case 1: /* free */
            if (!p[s])
                break;
            verify(s);
            __pico_free(p[s]);
            p[s] = NULL;
            sz[s] = 0;
            break;
        case 2: /* realloc */
            if (!p[s])
                break;
            verify(s);
            n = 1 + rnd() % 700;
            p[s] = __pico_realloc(p[s], n);
            assert(p[s] != NULL);
            if (n > sz[s]) {
                /* realloc's new bytes are indeterminate per C, but this
                 * allocator zeroes everywhere else -- count the leaks. */
                for (size_t j = sz[s]; j < n; j++)
                    if (p[s][j] != 0) {
                        stale++;
                        break;
                    }
                memset(p[s] + sz[s], tag(s), n - sz[s]);
            }
            sz[s] = n;
            verify(s);
            break;
        case 3: /* touch */
            if (p[s])
                verify(s);
            break;
        }
    }

    for (i = 0; i < SLOTS; i++)
        if (p[i]) {
            verify(i);
            __pico_free(p[i]);
        }

    printf("ok, heap %zu KiB, stale-on-grow %ld\n", heap_used() / 1024, stale);
    return 0;
}

src@consts.c

/* Expose the size constants that differ between the two free-list
 * designs, so they can be read out of the object file for any target. */
#include "pico/local-malloc.h"

char pico_chunk_min[MALLOC_CHUNK_MIN];
char pico_split_min[MALLOC_SPLIT_MIN];
char pico_prev_frame[sizeof(malloc_prev_t)];
#ifdef __MALLOC_SKIP_LIST
char pico_list_head[sizeof(malloc_head_t)];
#else
char pico_list_head[sizeof(chunk_t *)];
#endif

src@shim.h

/* Force-included before every picolibc malloc source.
 * Supplies the picolibc-internal macros that the allocator needs so the
 * sources compile unmodified against a hosted glibc toolchain.
 */
#ifndef _PICO_SHIM_H_
#define _PICO_SHIM_H_

#include <stdint.h>
#include <stddef.h>

#define __align_up(x, y) \
    ((__typeof__(x))(((uintptr_t)(x) + ((y) - 1)) & (~((uintptr_t)(y) - 1))))
#define __align_down(x, y) ((__typeof__(x))((uintptr_t)(x) & (~((uintptr_t)(y) - 1))))

#define __disable_sanitizer
#define __noreturn __attribute__((__noreturn__))

/* newlib/glibc <sys/cdefs.h> may define __strong_reference with a bare
 * #sym, which stringizes before the -Dmalloc=... rename is applied.
 * Pull it in first, then override with a two-step stringize. */
#include <sys/cdefs.h>
#undef __strong_reference
#define __PICO_STR1(x) #x
#define __PICO_STR(x)  __PICO_STR1(x)
#define __strong_reference(sym, aliassym) \
    extern __typeof(sym) aliassym __attribute__((__alias__(__PICO_STR(sym))))
#define __GNUCLIKE_PRAGMA_DIAGNOSTIC 1

/* picolibc's random(): plain LCG, no lock. glibc's would add a lock and
 * unfairly penalize the skip list, so use the real thing. */
long __pico_random(void);

/* Step counter: one increment per free-list pointer chase. Only compiled
 * into the -DBENCH_COUNT binaries so timing runs stay clean. */
#ifdef BENCH_COUNT
extern unsigned long bench_steps;
#define BENCH_STEP() (bench_steps++)
#else
#define BENCH_STEP() ((void)0)
#endif

/* The libc headers pulled in above set _DEFAULT_SOURCE; local-malloc.h
 * defines it again with a different value. Clear it so that is not a
 * redefinition. */
#undef _DEFAULT_SOURCE

#endif /* _PICO_SHIM_H_ */

src@sys@lock.h

/* Single-threaded benchmark: picolibc's default no-op lock. */
#ifndef _SYS_LOCK_H_
#define _SYS_LOCK_H_
typedef int _LOCK_T;
typedef int _LOCK_RECURSIVE_T;
#define __LOCK_INIT(class, lock) static int lock = 0;
#define __LOCK_INIT_RECURSIVE(class, lock) static int lock = 0;
#define __LIBC_LOCK()   ((void)0)
#define __LIBC_UNLOCK() ((void)0)
#endif

tools@build.sh

#!/bin/sh
# Ship the suite to the build host, cross-compile for RV64, bring the
# binaries back and push them to the target over adb.
#
#   HOST     ssh host with the RV64 toolchain   (default node11)
#   REMOTE   build directory on that host       (default bench-malloc)
#   DEV_DIR  directory on the RV64 target       (default /tmp/bench-malloc)
#
# Nothing is compiled on the machine running this script.
set -e
cd "$(dirname "$0")/.."

HOST=${HOST:-node11}
REMOTE=${REMOTE:-bench-malloc}
DEV_DIR=${DEV_DIR:-/tmp/bench-malloc}

echo "==> sync -> $HOST:$REMOTE"
tar czf - --exclude build --exclude obj --exclude './bench-*' \
    --exclude './count-*' --exclude './check-*' . |
    ssh "$HOST" "rm -rf $REMOTE && mkdir -p $REMOTE && tar xzf - -C $REMOTE"

echo "==> build on $HOST"
ssh "$HOST" "cd $REMOTE && make -j\$(nproc) $*"

echo "==> fetch binaries"
rm -rf build && mkdir build
ssh "$HOST" "cd $REMOTE && tar cf - bench-* count-* check-*" | tar xf - -C build

# e_machine at offset 18 must be EM_RISCV (0xf3). Getting host binaries
# here once was enough.
mach=$(od -An -tx1 -j18 -N2 build/bench-list | tr -d ' \n')
if [ "$mach" != "f300" ]; then
    echo "not RV64 binaries (e_machine=$mach) -- check CC in the Makefile" >&2
    exit 1
fi

echo "==> push -> target:$DEV_DIR"
adb shell "rm -rf $DEV_DIR && mkdir -p $DEV_DIR"
adb push build/. "$DEV_DIR" > /dev/null
adb shell "chmod +x $DEV_DIR/*"
adb shell "ls $DEV_DIR | wc -l" | tr -d '\r' | sed 's/^/    /;s/$/ binaries on target/'

tools@check.sh

#!/bin/sh
# Randomized correctness check on the RV64 target: 2M malloc/free/realloc
# ops per variant with content, alignment and zeroing verification.
set -e
cd "$(dirname "$0")/.."

EXEC="${EXEC:-adb shell}"
BINDIR="${BINDIR:-/tmp/bench-malloc}"
VARIANTS="${VARIANTS:-$(make -s print-variants)}"

for v in $VARIANTS; do
    printf '%-16s ' "$v"
    $EXEC "$BINDIR/check-$v" | tr -d '\r'
done

tools@env.sh

#!/bin/sh
# Print the target and toolchain environment. Save this next to a results
# file: the numbers only mean something together with the core, the cache
# sizes and the clock they were taken on.
set -e
cd "$(dirname "$0")/.."

HOST=${HOST:-node11}
REMOTE=${REMOTE:-bench-malloc}
EXEC="${EXEC:-adb shell}"

echo "# toolchain"
ssh "$HOST" "cd $REMOTE && cc=\$(make -s print-cc) && echo \$cc && \$cc --version | head -1"

echo
echo "# target"
$EXEC "uname -sr; \
       grep -m1 'model name' /proc/cpuinfo; \
       grep -m1 '^isa' /proc/cpuinfo; \
       nproc | sed 's/^/cpus: /'; \
       grep MemTotal /proc/meminfo; \
       for d in /sys/devices/system/cpu/cpu0/cache/index*; do \
           printf 'L%s %s %s\n' \$(cat \$d/level) \$(cat \$d/type) \$(cat \$d/size); \
       done; \
       printf 'governor: %s @ %s kHz\n' \
           \$(cat /sys/devices/system/cpu/cpu3/cpufreq/scaling_governor) \
           \$(cat /sys/devices/system/cpu/cpu3/cpufreq/scaling_cur_freq)" | tr -d '\r'

tools@report.py

#!/usr/bin/env python3
"""Pivot results.csv into per-workload tables: ns/op, list steps/op, heap KiB.

A cell marked * had more than 20% spread between the fastest and slowest
trial, i.e. the machine moved more than the allocator did.
"""
import csv
import sys
from collections import defaultdict

SPREAD_LIMIT = 20.0

path = sys.argv[1] if len(sys.argv) > 1 else "results.csv"
rows = list(csv.DictReader(open(path)))
data = defaultdict(dict)  # ((workload,size),metric) -> {(variant,n): value}
for r in rows:
    v, w, n, s = r["variant"], r["workload"], int(r["n"]), int(r["size"])
    counting = v.startswith("count-")
    v = v[6:] if counting else v
    key = (w, s)
    if counting:
        data[(key, "steps")][(v, n)] = float(r["steps_per_op"])
    else:
        data[(key, "ns")][(v, n)] = (float(r["ns_per_op"]), float(r["spread_pct"]))
        data[(key, "heap")][(v, n)] = int(r["heap_kb"])

variants = list(dict.fromkeys(
    r["variant"][6:] if r["variant"].startswith("count-") else r["variant"] for r in rows))
ns_all = sorted({int(r["n"]) for r in rows})
sizes = sorted({int(r["size"]) for r in rows})
workloads = ["free_rand", "free_asc", "free_desc", "malloc_miss", "churn", "realloc_grow"]


def fmt_ns(cell):
    ns, spread = cell
    return f"{ns:,.0f}" + ("*" if spread > SPREAD_LIMIT else "")


def table(title, tbl, fmt):
    have = [v for v in variants if any((v, n) in tbl for n in ns_all)]
    if not have:
        return
    print(f"\n### {title}")
    print("| variant | " + " | ".join(f"N={n}" for n in ns_all) + " |")
    print("|---" * (len(ns_all) + 1) + "|")
    for v in have:
        cells = [fmt(tbl[(v, n)]) if (v, n) in tbl else "-" for n in ns_all]
        print(f"| {v} | " + " | ".join(cells) + " |")


print(f"Cells marked * varied by more than {SPREAD_LIMIT:.0f}% across trials.")
for s in sizes:
    print(f"\n## payload {s} B")
    for w in workloads:
        table(f"{w}: ns/op", data.get(((w, s), "ns"), {}), fmt_ns)
        table(f"{w}: free-list steps/op", data.get(((w, s), "steps"), {}), lambda x: f"{x:,.1f}")
        table(f"{w}: heap KiB", data.get(((w, s), "heap"), {}), lambda x: f"{x:,d}")

tools@run.sh

#!/bin/sh
# Sweep free-list length and payload size across every variant, on the
# RV64 target.
#
#   NS        free-list lengths to test
#   SIZES     payload sizes
#   PIN       core pinning on the target
#   EXEC      how to reach the target      (default: adb shell)
#   BINDIR    binary directory on target   (default: /tmp/bench-malloc)
#   WORKLOAD  a single workload name, or all (default)
#   VARIANTS  override the list from the Makefile
#
# Runs all variants back to back for each (N, size) so machine noise hits
# them alike. The count-* binaries are only run at the smallest payload;
# the step counts do not depend on payload.
set -e
cd "$(dirname "$0")/.."

NS="${NS:-64 256 1024 4096 16384 65536}"
SIZES="${SIZES:-32}"
PIN="${PIN:-taskset -c 3}"
EXEC="${EXEC:-adb shell}"
BINDIR="${BINDIR:-/tmp/bench-malloc}"
VARIANTS="${VARIANTS:-$(make -s print-variants)}"
COUNT_SIZE=$(set -- $SIZES; echo "$1")

# adb shell hands back CRLF; strip it or the CSV grows carriage returns.
WORKLOAD="${WORKLOAD:-all}"
run() { $EXEC $PIN "$BINDIR/$1" "$2" "$3" "$4" "$WORKLOAD" | tr -d '\r'; }

echo "variant,workload,n,size,ns_per_op,spread_pct,steps_per_op,heap_kb,free_len"
for s in $SIZES; do
    for n in $NS; do
        for v in $VARIANTS; do
            run "bench-$v" "$v" "$n" "$s"
            if [ "$s" = "$COUNT_SIZE" ]; then
                run "count-$v" "count-$v" "$n" "$s"
            fi
        done
    done
done

tools@sizes.sh

#!/bin/sh
# RV64 code size and the memory constants that differ between the two
# free-list designs. Runs on the build host; nothing is executed.
set -e
cd "$(dirname "$0")/.."

TOOLDIR=${TOOLDIR:-$HOME/riscv/toolchain/bin}
CROSS=${CROSS:-riscv64-unknown-linux-gnu-}
CC=${CC:-$TOOLDIR/${CROSS}gcc}
SIZE=${SIZE:-$TOOLDIR/${CROSS}size}
NM=${NM:-$TOOLDIR/${CROSS}nm}
VARIANTS="${VARIANTS:-$(make -s print-variants)}"

BASE="${OPT:--Os} -I. -Isrc -include src/shim.h -Dmalloc=__pico_malloc -Dfree=__pico_free \
-Dcfree=__pico_cfree -Drealloc=__pico_realloc -Dsbrk=__pico_sbrk -Drandom=__pico_random"
ALLOC="pico/malloc.c pico/free.c pico/realloc.c pico/malloc-skip.c"

for v in $VARIANTS; do
    def=$(make -s print-def-$v)
    out=obj/size-$v
    rm -rf $out; mkdir -p $out
    for f in $ALLOC; do
        $CC $BASE $def -c -o $out/$(basename $f .c).o $f
    done
    text=$($SIZE -t $out/*.o | tail -1 | awk '{print $1}')
    ram=$($SIZE -t $out/*.o | tail -1 | awk '{print $2+$3}')

    # Read the constants out of an object file so they are exact for the
    # target ABI rather than guessed from the host's.
    $CC $BASE $def -c -o $out/consts.o src/consts.c
    consts=$($NM --print-size --size-sort $out/consts.o |
        while read -r a sz ty nm; do printf '%s=%d ' "${nm#pico_}" "$((0x$sz))"; done)

    printf '%-16s text=%-5s data+bss=%-4s %s\n' "$v" "$text" "$ram" "$consts"
done

unpack.sh

#!/bin/sh
# Gists are flat, so paths were encoded with '@'. Restore the tree:
#   sh unpack.sh && make -s print-variants
set -e
for f in *@*; do
    p=$(echo "$f" | tr '@' '/')
    mkdir -p "$(dirname "$p")"
    mv "$f" "$p"
done
chmod +x extract.sh tools/*.sh 2>/dev/null || true
echo "unpacked; see README.md"