/*

  arena.c -- Arena allocator

  Copyright © 2020-2024 Samuel Lidén Borell <samuel@kodafritt.se>

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  THE SOFTWARE.

*/

#include "internal.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define INTERR_ARENA(errnum) MAKE_INTERR(errnum, INTERRBASE_ARENA)

#ifndef ARENA_SIZE
#define ARENA_SIZE 4096
#endif

struct ArenaBlock {
    unsigned char *data, *free, *end;
};

struct ArenaHolder {
    struct ArenaHolder *prev;
    size_t capacity;
    struct ArenaBlock *blocks;
    struct ArenaBlock *last;
    struct ArenaBlock *last_capacity;

#ifdef ENABLE_STRUCTTYPE_PROTECTION
    unsigned num_trailers;
    unsigned *trailers[MAX_TRACKED_TRAILERS];
    unsigned trailer_types[MAX_TRACKED_TRAILERS];
#endif
};

static void *large_alloc(struct CSlul *ctx, size_t size);
static int grow_arena_list(struct CSlul *ctx);

/*
  As an optimization, we could keep buckets of arenas
  with <=8, <=16, <=32, ... <=4096 bytes free

  We could also track arena alignment, so we can allocate small-alignment
  structures in lesser aligned arenas.

  We should also add an environment variable for adding "bad" padding
  between allocations for Valgrind etc.

  TODO Add First-in-Last-out allocation?
*/

int arena_new(struct CSlul *ctx)
{
    struct ArenaHolder *hld = lowlvl_alloc(
                ctx->cfg, sizeof(struct ArenaHolder));
    if (!hld) goto outofmem;
    hld->capacity = 16;
    hld->blocks = lowlvl_alloc(
                ctx->cfg, hld->capacity*sizeof(struct ArenaBlock));
    if (!hld->blocks) goto outofmem;
    hld->last = hld->blocks; /* first block */
    hld->last_capacity = &hld->blocks[hld->capacity];
    hld->prev = ctx->arenas;
    ctx->arenas = hld;

#ifdef ENABLE_STRUCTTYPE_PROTECTION
    {
        int i;
        for (i = 0; i < MAX_TRACKED_TRAILERS; i++) {
            hld->trailers[i] = NULL;
        }
        hld->num_trailers = 0;
    }
#endif
    return 1;
  outofmem:
    ctx_outofmem(ctx);
    if (hld) lowlvl_free(ctx->cfg, hld);
    return 0;
}

void arena_free(struct CSlul *ctx)
{
    struct ArenaHolder *hld = ctx->arenas;
    struct ArenaBlock *block;
    assert(hld != NULL);
#ifdef ENABLE_STRUCTTYPE_PROTECTION
    {
        int i;
        for (i = 0; i < MAX_TRACKED_TRAILERS; i++) {
            if (hld->trailers[i] != NULL) {
                /* An assertion failure here means that there has been a
                   type confusion; A struct has been allocated as
                   and then overwritten by some other type (or garbage).

                   *hld->trailers[i] is the trailer at the end of the struct.

                   hld->trailer_types[i] is the expected type, i.e. the
                   type that the struct was originally allocated as. */
                assert(*hld->trailers[i] == hld->trailer_types[i]);
            }
        }
    }
#endif
    ctx->arenas = hld->prev;
    for (block = hld->blocks; block < hld->last; block++) {
        lowlvl_free(ctx->cfg, block->data);
    }
    lowlvl_free(ctx->cfg, hld->blocks);
    lowlvl_free(ctx->cfg, hld);
}

/* align must be a power of 2 */
#define ALIGN(ptr, align) ((((uintptr)ptr)+((align)-1)) & ~((uintptr)(align)-1))
#define NOT_EMPTY(hld) ((hld)->blocks != (hld)->last)

#ifdef TEST_AALLOC
void *real_aalloc(struct CSlul *ctx, size_t size, size_t align)
#else
void *aalloc(struct CSlul *ctx, size_t size, size_t align)
#endif
{
    struct ArenaHolder *hld = ctx->arenas;
    struct ArenaBlock *block, *lastarena;
    void *p;
    uintptr aligned;
    assert(size != 0);
    assert(align != 0);
    assert(hld != NULL);

    if (LIKELY(NOT_EMPTY(hld))) {
        /* Check if the last block has free space */
        block = hld->last-1;
        assert(block->free != NULL);
        aligned = ALIGN(block->free, align);
        if (LIKELY(aligned+size <= (uintptr)block->end)) {
            /* Found space */
            block->free = (void*)(aligned+size);
            return (void*)aligned;
        }
    }

    /* For large allocations, allocate its own arena */
    if (size > (ARENA_SIZE/4)*3) return large_alloc(ctx, size);

    /* No arena exists. Grab a blank one and allocate.

       Possible improvement: It would be nice to be able to
       reuse unused space at the end of existing blocks. */
    p = lowlvl_alloc(ctx->cfg, ARENA_SIZE);
    if (!p) goto outofmem;
    if (hld->last == hld->last_capacity) {
        if (!grow_arena_list(ctx)) {
            lowlvl_free(ctx->cfg, p);
            return NULL;
        }
    }
    lastarena = hld->last++;
    lastarena->data = p;
    lastarena->end = lastarena->data + ARENA_SIZE;
    lastarena->free = lastarena->data + size;
    return lastarena->data;
  outofmem:
    ctx_outofmem(ctx);
    return NULL;
}

static void *large_alloc(struct CSlul *ctx, size_t size)
{
    struct ArenaHolder *hld = ctx->arenas;
    struct ArenaBlock *lastarena;
    void *p = lowlvl_alloc(ctx->cfg, size);
    if (!p) goto outofmem;
    if (hld->last == hld->last_capacity) {
        if (!grow_arena_list(ctx)) {
            lowlvl_free(ctx->cfg, p);
            return NULL;
        }
    }
    lastarena = hld->last++;
    lastarena->data = p;
    lastarena->free = lastarena->end = lastarena->data + size;
    return lastarena->data;
  outofmem:
    ctx_outofmem(ctx);
    return NULL;
}

/** Grows the list of arena blocks. */
static int grow_arena_list(struct CSlul *ctx)
{
    struct ArenaHolder *hld = ctx->arenas;
    size_t size = (size_t)(hld->last - hld->blocks);
    size_t newcapa = hld->capacity*2;
    struct ArenaBlock *newblocks = lowlvl_realloc(
            ctx->cfg, hld->blocks, newcapa*sizeof(struct ArenaBlock));
    if (!newblocks) goto outofmem;
    hld->blocks = newblocks;
    hld->capacity = newcapa;
    hld->last = &hld->blocks[size];
    hld->last_capacity = &hld->blocks[newcapa];
    return 1;
  outofmem:
    ctx_outofmem(ctx);
    return 0;
}

/**
 * Duplicates a string of known length (not necessarily null-terminated).
 * The returned string is null-terminated.
 */
char *aalloc_memzdup(struct CSlul *ctx, const char *s, size_t size)
{
    char *dup = aalloc(ctx, size+1, 1);
    if (!dup) return NULL;
    memcpy(dup, s, size);
    dup[size] = '\0';
    return dup;
}

#ifdef ENABLE_STRUCTTYPE_PROTECTION
/**
 * Registers the type of the struct, so overwrites with another struct type
 * can be detected.
 */
void register_trailer(struct CSlul *ctx, unsigned *trailer_ptr, unsigned type)
{
    struct ArenaHolder *hld = ctx->arenas;
    unsigned num_trailers = hld->num_trailers;
    unsigned **destptr = &hld->trailers[num_trailers];
    unsigned *desttype = &hld->trailer_types[num_trailers];
    if (*destptr) {
        assert(**destptr == *desttype);
    }
    *trailer_ptr = type;
    *destptr = trailer_ptr;
    *desttype = type;
    hld->num_trailers = (num_trailers+1) % MAX_TRACKED_TRAILERS;
    if (!hld->num_trailers) {
        static int warned_once = 0;
        if (!warned_once) {
            fprintf(stderr,
                "Debug: struct-type protection buffer has overflowed.\n"
                "Debug: Raise MAX_TRACKED_TRAILERS in src-cslul/internal.h\n");
            warned_once = 1;
        }
    }
}
#endif