/*
 * kido-alloc.c — Kido first-fit allocator with coalescing.
 *
 * Design (deliberations/2026-10-14-kido-alloc-design.md):
 *  P1 first-fit free-list, address-ordered, coalesce-on-free.
 *  P2 explicit region list (no hidden kido-mem coupling).
 *  P3 loud exhaustion: status codes, never silent NULL.
 *  P4 magic-checked free: double/invalid/NULL free is EARLY_ENV.
 *  P5 reservation carve-out implemented (image bounds wire later).
 *  P6 identity-map assumption declared (MMU module revisits).
 *
 * Block layout: [32-byte header][payload]. The header stays at the
 * block start; only the payload is aligned up, so alignment waste is
 * bounded by (align-1) per alloc with no leading fragment to manage.
 *
 * TESTING: KIDO_HOSTED_TEST + KIDO_ALLOC_SELFTEST builds the harness.
 *  gcc -std=c11 -Wall -Wextra -Werror -DKIDO_HOSTED_TEST \
 *      -DKIDO_ALLOC_SELFTEST modules/kido-alloc.c -o /tmp/kido-alloc-test
 */

#include "kido-alloc.h"

/* ------------------------------------------------------------------ */
/* Block header: 32 bytes, so payloads are 16-alignable.               */
/* ------------------------------------------------------------------ */
typedef struct kido_alloc_block {
    uint64_t size;   /* usable payload bytes after this header */
    uint32_t magic;  /* ALLOC_MAGIC (live) or FREE_MAGIC       */
    uint32_t _pad0;
    struct kido_alloc_block *next;  /* free-list link, valid iff free */
    uint64_t _pad1;
} kido_alloc_block_t;

#define KIDO_ALLOC_HDR_SIZE 32u
#define KIDO_ALLOC_MAGIC      0xA110C47EU
#define KIDO_ALLOC_FREE_MAGIC 0xF4EE0001U
/* Smallest trailing fragment worth keeping as a free block. */
#define KIDO_ALLOC_MIN_SPLIT (KIDO_ALLOC_HDR_SIZE + 32u)
/* Sanity ceiling: requests at/above this cannot fit any real region. */
#define KIDO_ALLOC_SIZE_CAP (1ULL << 48)

#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
_Static_assert(sizeof(kido_alloc_block_t) == KIDO_ALLOC_HDR_SIZE,
               "kido-alloc: header must be exactly 32 bytes");
#endif

/* ------------------------------------------------------------------ */
/* Static state. Uniprocessor: no locking (see kido-sched.h SMP law).  */
/* ------------------------------------------------------------------ */
static kido_alloc_block_t *alloc_free_head;
static kido_mem_region_t   alloc_regions[KIDO_MEM_MAX_REGIONS];
static size_t              alloc_region_count;
static uint8_t             alloc_ready;
static uint64_t            alloc_total_bytes;
static uint64_t            alloc_allocated_bytes;
static uint64_t            alloc_free_bytes;
static uint64_t            alloc_count;
static uint64_t            alloc_free_count;

/* Insert [addr, addr+size) as a free block, address-ordered, merging
 * with neighbors when adjacent. size must be >= KIDO_ALLOC_MIN_SPLIT. */
static void alloc_insert_free(uint64_t addr, uint64_t size)
{
    kido_alloc_block_t *nb = (kido_alloc_block_t *)(uintptr_t)addr;
    kido_alloc_block_t *prev = NULL;
    kido_alloc_block_t *cur = alloc_free_head;
    uint64_t na, ne;

    nb->size  = size - KIDO_ALLOC_HDR_SIZE;
    nb->magic = KIDO_ALLOC_FREE_MAGIC;
    nb->next  = NULL;
    nb->_pad0 = 0;
    nb->_pad1 = 0;
    na = addr;
    ne = addr + size;

    while (cur != NULL && (uint64_t)(uintptr_t)cur < na) {
        prev = cur;
        cur = cur->next;
    }
    /* Merge with previous when adjacent. */
    if (prev != NULL) {
        uint64_t pa = (uint64_t)(uintptr_t)prev;
        if (pa + KIDO_ALLOC_HDR_SIZE + prev->size == na) {
            prev->size += KIDO_ALLOC_HDR_SIZE + nb->size;
            nb = prev;
            na = pa;
            ne = pa + KIDO_ALLOC_HDR_SIZE + prev->size;
            /* prev stays linked; fall through to next-merge check */
        } else {
            prev->next = nb;
        }
    } else {
        alloc_free_head = nb;
    }
    /* Merge with next when adjacent. */
    if (cur != NULL && ne == (uint64_t)(uintptr_t)cur) {
        nb->size += KIDO_ALLOC_HDR_SIZE + cur->size;
        nb->next = cur->next;
    } else {
        nb->next = cur;
    }
    alloc_free_bytes += size;
}

/* ------------------------------------------------------------------ */
kido_status_t kido_alloc_init(const kido_mem_region_t *regions, size_t n,
                              uint64_t reserve_base, uint64_t reserve_size)
{
    size_t i;
    uint64_t re;

    if (regions == NULL || n == 0 || n > KIDO_MEM_MAX_REGIONS)
        return KIDO_ERR_EARLY_ENV;
    if (reserve_size != 0) {
        re = reserve_base + reserve_size;
        if (re < reserve_base)
            return KIDO_ERR_EARLY_ENV;  /* reservation overflow: loud */
    }

    alloc_region_count = 0;
    for (i = 0; i < n; i++) {
        uint64_t b = regions[i].base;
        uint64_t s = regions[i].size;
        uint64_t e = b + s;
        if (s == 0)
            continue;
        if (e < b)
            return KIDO_ERR_EARLY_ENV;  /* region overflow: loud */
        alloc_regions[alloc_region_count].base = b;
        alloc_regions[alloc_region_count].size = s;
        alloc_region_count++;
    }
    if (alloc_region_count == 0)
        return KIDO_ERR_NO_MEMORY;

    /* Fresh free list. */
    alloc_free_head       = NULL;
    alloc_total_bytes     = 0;
    alloc_allocated_bytes = 0;
    alloc_free_bytes      = 0;
    alloc_count           = 0;
    alloc_free_count      = 0;

    for (i = 0; i < alloc_region_count; i++) {
        uint64_t b = alloc_regions[i].base;
        uint64_t e = b + alloc_regions[i].size;
        /* Carve the reservation out: up to two surviving pieces. */
        uint64_t p1b = b, p1e = e, p2b = e, p2e = e;
        if (reserve_size != 0 && reserve_base < e && re > b) {
            p1e = (reserve_base > b) ? reserve_base : b;
            p2b = (re < e) ? re : e;
        }
        if (p1e > p1b && p1e - p1b >= KIDO_ALLOC_MIN_SPLIT) {
            alloc_insert_free(p1b, p1e - p1b);
            alloc_total_bytes += p1e - p1b;
        }
        if (p2e > p2b && p2e - p2b >= KIDO_ALLOC_MIN_SPLIT) {
            alloc_insert_free(p2b, p2e - p2b);
            alloc_total_bytes += p2e - p2b;
        }
    }

    if (alloc_free_head == NULL)
        return KIDO_ERR_NO_MEMORY;  /* nothing usable survived */
    alloc_ready = 1;
    return KIDO_OK;
}

/* ------------------------------------------------------------------ */
kido_status_t kido_alloc(uint64_t size, uint64_t align, void **out)
{
    kido_alloc_block_t *prev = NULL;
    kido_alloc_block_t *b;
    uint64_t eff;

    if (out == NULL)
        return KIDO_ERR_EARLY_ENV;
    *out = NULL;
    if (!alloc_ready)
        return KIDO_ERR_EARLY_ENV;
    if (size == 0 || align == 0)
        return KIDO_ERR_EARLY_ENV;
    if ((align & (align - 1)) != 0)
        return KIDO_ERR_EARLY_ENV;  /* not a power of two: loud */
    if (size >= KIDO_ALLOC_SIZE_CAP)
        return KIDO_ERR_NO_MEMORY;
    eff = (align < KIDO_ALLOC_MIN_ALIGN) ? KIDO_ALLOC_MIN_ALIGN : align;

    for (b = alloc_free_head; b != NULL; prev = b, b = b->next) {
        uint64_t ba = (uint64_t)(uintptr_t)b;
        uint64_t block_end = ba + KIDO_ALLOC_HDR_SIZE + b->size;
        uint64_t aligned_base, payload, need_end;
        if (block_end < ba)
            continue;  /* corrupt free list entry: skip, don't trust */
        aligned_base = ba + KIDO_ALLOC_HDR_SIZE;
        if (aligned_base < ba || eff - 1 > (uint64_t)-1 - aligned_base)
            continue;  /* alignment arithmetic would overflow */
        payload = (aligned_base + eff - 1) & ~(eff - 1);
        need_end = payload + size;
        if (need_end < payload)
            continue;  /* overflow: cannot fit here */
        if (need_end > block_end)
            continue;  /* first-fit: keep looking */
        /* Fits: unlink the free block. */
        if (prev == NULL)
            alloc_free_head = b->next;
        else
            prev->next = b->next;
        alloc_free_bytes -= (KIDO_ALLOC_HDR_SIZE + b->size);
        {
            kido_alloc_block_t *nb =
                (kido_alloc_block_t *)(uintptr_t)(payload - KIDO_ALLOC_HDR_SIZE);
            uint64_t trailing = block_end - need_end;
            nb->size  = need_end - payload; /* requested span only; the
                                            * trailing fragment is a
                                            * separate free block below */
            nb->magic = KIDO_ALLOC_MAGIC;
            nb->next  = NULL;
            nb->_pad0 = 0;
            nb->_pad1 = 0;
            if (trailing >= KIDO_ALLOC_MIN_SPLIT)
                alloc_insert_free(need_end, trailing);
            alloc_allocated_bytes += nb->size;
            alloc_count++;
            *out = (void *)(uintptr_t)payload;
            return KIDO_OK;
        }
    }
    return KIDO_ERR_NO_MEMORY;  /* loud exhaustion, *out stays NULL */
}

/* ------------------------------------------------------------------ */
kido_status_t kido_free(void *ptr)
{
    uint64_t pa, ha;
    kido_alloc_block_t *h;
    size_t i;
    int in_region = 0;

    if (ptr == NULL)
        return KIDO_ERR_EARLY_ENV;
    if (!alloc_ready)
        return KIDO_ERR_EARLY_ENV;
    pa = (uint64_t)(uintptr_t)ptr;
    if (pa < KIDO_ALLOC_HDR_SIZE)
        return KIDO_ERR_EARLY_ENV;
    ha = pa - KIDO_ALLOC_HDR_SIZE;

    for (i = 0; i < alloc_region_count; i++) {
        uint64_t b = alloc_regions[i].base;
        uint64_t e = b + alloc_regions[i].size;
        if (ha >= b && pa <= e) {
            in_region = 1;
            break;
        }
    }
    if (!in_region)
        return KIDO_ERR_EARLY_ENV;  /* never issued here: loud */

    h = (kido_alloc_block_t *)(uintptr_t)ha;
    if (h->magic == KIDO_ALLOC_FREE_MAGIC)
        return KIDO_ERR_EARLY_ENV;  /* double free: loud */
    if (h->magic != KIDO_ALLOC_MAGIC)
        return KIDO_ERR_EARLY_ENV;  /* corrupt/foreign pointer: loud */

    h->magic = KIDO_ALLOC_FREE_MAGIC;
    alloc_allocated_bytes -= h->size;
    alloc_free_count++;
    /* Reinsert whole block (header included); coalescing merges it. */
    alloc_insert_free(ha, KIDO_ALLOC_HDR_SIZE + h->size);
    return KIDO_OK;
}

/* ------------------------------------------------------------------ */
kido_status_t kido_alloc_stats(kido_alloc_stats_t *out)
{
    kido_alloc_block_t *b;
    uint64_t largest = 0;

    if (out == NULL || !alloc_ready)
        return KIDO_ERR_EARLY_ENV;
    for (b = alloc_free_head; b != NULL; b = b->next) {
        if (b->size > largest)
            largest = b->size;
    }
    out->total_bytes     = alloc_total_bytes;
    out->allocated_bytes = alloc_allocated_bytes;
    out->free_bytes      = alloc_free_bytes;
    out->largest_free    = largest;
    out->allocs          = alloc_count;
    out->frees           = alloc_free_count;
    return KIDO_OK;
}

/* ================================================================== */
/* Hosted self-test.                                                  */
/* ================================================================== */
#ifdef KIDO_ALLOC_SELFTEST
#ifndef KIDO_HOSTED_TEST
#error "KIDO_ALLOC_SELFTEST needs KIDO_HOSTED_TEST."
#endif

#include <stdio.h>

static int test_failures = 0;
static int test_count = 0;
#define CHECK(cond, label) do { \
    test_count++; \
    if (cond) { printf("[ ok ] %s\n", label); } \
    else { printf("[FAIL] %s\n", label); test_failures++; } \
} while (0)

/* 1 MiB static arena: the hosted stand-in for firmware regions. */
static uint8_t alloc_test_arena[1024u * 1024u] __attribute__((aligned(16)));

static int ptr_in_arena(const void *p, uint64_t size)
{
    uint64_t a = (uint64_t)(uintptr_t)p;
    uint64_t lo = (uint64_t)(uintptr_t)&alloc_test_arena[0];
    uint64_t hi = lo + sizeof(alloc_test_arena);
    return a >= lo && a + size <= hi && a + size >= a;
}

int main(void)
{
    kido_mem_region_t regs[2];
    kido_mem_region_t bad[1];
    kido_alloc_stats_t st;
    void *p1 = NULL, *p2 = NULL, *p3 = NULL;
    kido_status_t rc;
    uint64_t lo = (uint64_t)(uintptr_t)&alloc_test_arena[0];

    printf("== kido-alloc self-test (hosted) ==\n");

    regs[0].base = lo;
    regs[0].size = 768u * 1024u;
    regs[1].base = lo + 768u * 1024u;
    regs[1].size = 256u * 1024u;

    /* 1-4: init guards */
    CHECK(kido_alloc_init(NULL, 1, 0, 0) == KIDO_ERR_EARLY_ENV, "init NULL regions -> EARLY_ENV");
    CHECK(kido_alloc_init(regs, 0, 0, 0) == KIDO_ERR_EARLY_ENV, "init n=0 -> EARLY_ENV");
    bad[0].base = (uint64_t)-1; bad[0].size = 2;
    CHECK(kido_alloc_init(bad, 1, 0, 0) == KIDO_ERR_EARLY_ENV, "init overflow region -> EARLY_ENV");
    CHECK(kido_alloc_init(regs, 2, 0, 0) == KIDO_OK, "init two regions -> OK");

    /* 5: stats after init */
    CHECK(kido_alloc_stats(&st) == KIDO_OK && st.total_bytes == 1024u * 1024u &&
          st.allocated_bytes == 0 && st.allocs == 0, "stats: 1 MiB total, nothing allocated");

    /* 6-9: basic alloc */
    rc = kido_alloc(64, 16, &p1);
    CHECK(rc == KIDO_OK && p1 != NULL, "alloc 64 -> OK");
    CHECK(((uint64_t)(uintptr_t)p1 & 15u) == 0, "alloc 16-aligned");
    CHECK(ptr_in_arena(p1, 64), "alloc inside arena");

    /* 10-12: arg guards (p1 stays live) */
    CHECK(kido_alloc(0, 16, &p2) == KIDO_ERR_EARLY_ENV, "alloc size 0 -> EARLY_ENV");
    CHECK(kido_alloc(64, 0, &p2) == KIDO_ERR_EARLY_ENV, "alloc align 0 -> EARLY_ENV");
    CHECK(kido_alloc(64, 24, &p2) == KIDO_ERR_EARLY_ENV, "alloc align 24 (non-pow2) -> EARLY_ENV");

    /* 13-14: large alignment + cap */
    rc = kido_alloc(128, 64, &p2);
    CHECK(rc == KIDO_OK && ((uint64_t)(uintptr_t)p2 & 63u) == 0, "alloc 128 align 64 -> 64-aligned");
    CHECK(kido_alloc(KIDO_ALLOC_SIZE_CAP, 16, &p3) == KIDO_ERR_NO_MEMORY && p3 == NULL,
          "alloc at size cap -> NO_MEMORY, out NULL");

    /* 15-16: free + reuse accounting. allocated_bytes tracks live block
     * spans (need_end - payload == requested size): after freeing p1,
     * exactly p2's 128-byte block remains. */
    CHECK(kido_free(p1) == KIDO_OK, "free p1 -> OK");
    CHECK(kido_alloc_stats(&st) == KIDO_OK && st.allocated_bytes == 128 &&
          st.frees == 1, "stats: only p2's 128-byte block live, one free counted");

    /* 17-19: loud free failures */
    CHECK(kido_free(p1) == KIDO_ERR_EARLY_ENV, "double free p1 -> EARLY_ENV (loud)");
    CHECK(kido_free(NULL) == KIDO_ERR_EARLY_ENV, "free NULL -> EARLY_ENV");
    {
        int stack_var = 0;
        CHECK(kido_free(&stack_var) == KIDO_ERR_EARLY_ENV, "free foreign pointer -> EARLY_ENV");
    }

    /* 20: free p2. The alignment gap [lo+96, p2-32) is bounded internal
     * waste (deliberation C2: < align bytes, documented, never a free
     * fragment) — so full single-block coalescing is impossible by
     * design. Pin the bound instead: total == free + waste. */
    CHECK(kido_free(p2) == KIDO_OK, "free p2 -> OK");
    {
        uint64_t waste = ((uint64_t)(uintptr_t)p2 - KIDO_ALLOC_HDR_SIZE) - (lo + 96);
        CHECK(kido_alloc_stats(&st) == KIDO_OK && st.allocated_bytes == 0 &&
              st.free_bytes == st.total_bytes - waste && waste < 64,
              "accounting balances: total == free + bounded (<64) align waste");
    }

    /* 21: exhaustion is loud and countable */
    {
        void *v[4096];
        uint64_t got = 0;
        kido_status_t last = KIDO_OK;
        while (got < 4096) {
            last = kido_alloc(256, 16, &v[got]);
            if (last != KIDO_OK)
                break;
            got++;
        }
        CHECK(last == KIDO_ERR_NO_MEMORY && got > 100, "exhaustion -> NO_MEMORY after many allocs");
        /* free half, allocate again: allocator recovers */
        for (uint64_t i = 0; i < got; i += 2)
            kido_free(v[i]);
        rc = kido_alloc(256, 16, &p3);
        CHECK(rc == KIDO_OK && p3 != NULL, "alloc succeeds after partial free");
        for (uint64_t i = 1; i < got; i += 2)
            kido_free(v[i]);
        kido_free(p3);
    }

    /* 22: reservation carve-out */
    {
        uint64_t rbase = lo + 256u * 1024u;
        uint64_t rsize = 128u * 1024u;
        CHECK(kido_alloc_init(regs, 2, rbase, rsize) == KIDO_OK, "re-init with 128 KiB reservation -> OK");
        CHECK(kido_alloc_stats(&st) == KIDO_OK &&
              st.total_bytes == 1024u * 1024u - 128u * 1024u, "stats: total reduced by reservation");
        rc = kido_alloc(4096, 16, &p1);
        CHECK(rc == KIDO_OK, "alloc works with reservation carved");
        {
            uint64_t a = (uint64_t)(uintptr_t)p1;
            int inside = (a >= rbase && a < rbase + rsize);
            CHECK(!inside, "no allocation inside the reservation");
        }
        /* every further alloc also avoids it */
        {
            int ok = 1;
            void *v[64];
            uint64_t i;
            for (i = 0; i < 64; i++) {
                if (kido_alloc(8192, 16, &v[i]) != KIDO_OK) break;
                {
                    uint64_t a = (uint64_t)(uintptr_t)v[i];
                    if (a >= rbase && a < rbase + rsize) ok = 0;
                }
            }
            for (uint64_t j = 0; j < i; j++) kido_free(v[j]);
            CHECK(ok, "64 allocs: none inside reservation");
        }
        kido_free(p1);
    }

    /* 23: alignment stress 1..256 */
    {
        int ok = 1;
        void *v[9];
        uint64_t al;
        int k = 0;
        CHECK(kido_alloc_init(regs, 2, 0, 0) == KIDO_OK, "re-init clean for align stress");
        for (al = 1; al <= 256; al <<= 1, k++) {
            if (kido_alloc(100, al, &v[k]) != KIDO_OK) { ok = 0; break; }
            if (((uint64_t)(uintptr_t)v[k] & (al - 1)) != 0) ok = 0;
        }
        for (int j = 0; j < k; j++) kido_free(v[j]);
        CHECK(ok && k == 9, "align 1..256 all honored");
    }

    /* 24: region bounds never exceeded across churn (120 mixed allocs,
     * ~650 KiB total: fits the 1 MiB arena deterministically). */
    {
        int ok = 1;
        void *v[120];
        uint64_t i, n = 0;
        uint64_t sizes[4] = { 32, 1000, 4096, 16384 };
        for (i = 0; i < 120; i++) {
            if (kido_alloc(sizes[i % 4], 16, &v[n]) != KIDO_OK)
                break;
            if (!ptr_in_arena(v[n], sizes[i % 4])) ok = 0;
            n++;
        }
        for (uint64_t j = 0; j < n; j++) kido_free(v[j]);
        CHECK(ok && n == 120, "120 churn allocs all inside arena");
        CHECK(kido_alloc_stats(&st) == KIDO_OK && st.allocated_bytes == 0,
              "after churn: nothing allocated");
    }

    printf("== %d checks, %d failures ==\n", test_count, test_failures);
    return test_failures == 0 ? 0 : 1;
}
#endif /* KIDO_ALLOC_SELFTEST */
