/*
 * regional.c -- region based memory allocator.
 *
 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 * 
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * 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.
 * 
 * Neither the name of the NLNET LABS 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.
 */

/**
 * \file
 * Regional allocator. Allocates small portions of of larger chunks.
 */

#include "config.h"
#include "util/log.h"
#include "util/regional.h"

#ifdef ALIGNMENT
#  undef ALIGNMENT
#endif
/** increase size until it fits alignment of s bytes */
#define ALIGN_UP(x, s)     (((x) + s - 1) & (~(s - 1)))
/** what size to align on; make sure a char* fits in it. */
#define ALIGNMENT          (sizeof(uint64_t))

/** Default reasonable size for chunks */
#define REGIONAL_CHUNK_SIZE         8192
#ifdef UNBOUND_ALLOC_NONREGIONAL
/** All objects allocated outside of chunks, for debug */
#define REGIONAL_LARGE_OBJECT_SIZE  0
#else
/** Default size for large objects - allocated outside of chunks. */
#define REGIONAL_LARGE_OBJECT_SIZE  2048
#endif

struct regional* 
regional_create(void)
{
        return regional_create_custom(REGIONAL_CHUNK_SIZE);
}

/** init regional struct with first block */
static void
regional_init(struct regional* r)
{
        size_t a = ALIGN_UP(sizeof(struct regional), ALIGNMENT);
        r->data = (char*)r + a;
        r->available = r->first_size - a;
        r->next = NULL;
        r->large_list = NULL;
        r->total_large = 0;
}

/**
 * Create a new region, with custom first block and large-object sizes.
 * @param size: length of first block.
 * @param large_object_size: outside of chunk allocation threshold.
 * @return: newly allocated regional.
 */
static struct regional*
regional_create_custom_large_object(size_t size, size_t large_object_size)
{
        struct regional* r;
        size = ALIGN_UP(size, ALIGNMENT);
        r = (struct regional*)malloc(size);
        log_assert(sizeof(struct regional) <= size);
        if(!r) return NULL;
        r->first_size = size;
        r->large_object_size = large_object_size;
        regional_init(r);
        return r;
}

struct regional*
regional_create_custom(size_t size)
{
        if(size < sizeof(struct regional))
                size = sizeof(struct regional);
        return regional_create_custom_large_object(size,
                REGIONAL_LARGE_OBJECT_SIZE);
}

struct regional*
regional_create_nochunk(size_t size)
{
        return regional_create_custom_large_object(size, 0);
}

void 
regional_free_all(struct regional *r)
{
        char* p = r->next, *np;
        while(p) {
                np = *(char**)p;
                free(p);
                p = np;
        }
        p = r->large_list;
        while(p) {
                np = *(char**)p;
                free(p);
                p = np;
        }
        regional_init(r);
}

void 
regional_destroy(struct regional *r)
{
        if(!r) return;
        regional_free_all(r);
        free(r);
}

void *
regional_alloc(struct regional *r, size_t size)
{
        size_t a;
        void *s;
        if(
#if SIZEOF_SIZE_T == 8
                (unsigned long long)size >= 0xffffffffffffff00ULL
#else
                (unsigned)size >= (unsigned)0xffffff00UL
#endif
                )
                return NULL; /* protect against integer overflow in
                        malloc and ALIGN_UP */
        a = ALIGN_UP(size, ALIGNMENT);
        /* large objects */
        if(a > r->large_object_size) {
                s = malloc(ALIGNMENT + size);
                if(!s) return NULL;
                r->total_large += ALIGNMENT+size;
                *(char**)s = r->large_list;
                r->large_list = (char*)s;
                return (char*)s+ALIGNMENT;
        }
        /* create a new chunk */
        if(a > r->available) {
                s = malloc(REGIONAL_CHUNK_SIZE);
                if(!s) return NULL;
                *(char**)s = r->next;
                r->next = (char*)s;
                r->data = (char*)s + ALIGNMENT;
                r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT;
        }
        /* put in this chunk */
        r->available -= a;
        s = r->data;
        r->data += a;
        return s;
}

void *
regional_alloc_init(struct regional* r, const void *init, size_t size)
{
        void *s = regional_alloc(r, size);
        if(!s) return NULL;
        memmove(s, init, size);
        return s;
}

void *
regional_alloc_zero(struct regional *r, size_t size)
{
        void *s = regional_alloc(r, size);
        if(!s) return NULL;
        memset(s, 0, size);
        return s;
}

char *
regional_strdup(struct regional *r, const char *string)
{
        return (char*)regional_alloc_init(r, string, strlen(string)+1);
}

/**
 * reasonably slow, but stats and get_mem are not supposed to be fast
 * count the number of chunks in use
 */
static size_t
count_chunks(struct regional* r)
{
        size_t c = 1;
        char* p = r->next;
        while(p) {
                c++;
                p = *(char**)p;
        }
        return c;
}

/**
 * also reasonably slow, counts the number of large objects
 */
static size_t
count_large(struct regional* r)
{
        size_t c = 0;
        char* p = r->large_list;
        while(p) {
                c++;
                p = *(char**)p;
        }
        return c;
}

void 
regional_log_stats(struct regional *r)
{
        /* some basic assertions put here (non time critical code) */
        log_assert(ALIGNMENT >= sizeof(char*));
        log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT);
        log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > r->large_object_size);
        log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional));
        /* debug print */
        log_info("regional %u chunks, %u large",
                (unsigned)count_chunks(r), (unsigned)count_large(r));
}

size_t 
regional_get_mem(struct regional* r)
{
        return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE 
                + r->total_large;
}