///-*-C++-*-//////////////////////////////////////////////////////////////////
//
// Hoard: A Fast, Scalable, and Memory-Efficient Allocator
//        for Shared-Memory Multiprocessors
// Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
//
// Copyright (c) 1998-2000, The University of Texas at Austin.
//
// This library is free software; you can redistribute it and/or modify
// it under the terms of the GNU Library General Public License as
// published by the Free Software Foundation, http://www.fsf.org.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Library General Public License for more details.
//
//////////////////////////////////////////////////////////////////////////////

#include "arch-specific.h"
#include "heap.h"

#include <OS.h>
#include <Debug.h>
#include <syscalls.h>

#include <libroot_private.h>

#include <stdlib.h>
#include <unistd.h>

//#define TRACE_CHUNKS
#ifdef TRACE_CHUNKS
#       define CTRACE(x) debug_printf x
#else
#       define CTRACE(x) ;
#endif

using namespace BPrivate;

struct free_chunk {
        free_chunk      *next;
        size_t          size;
};


static const size_t kInitialHeapSize = 64 * B_PAGE_SIZE;
        // that's about what hoard allocates anyway (should be kHeapIncrement
        // aligned)

static const size_t kHeapIncrement = 16 * B_PAGE_SIZE;
        // the steps in which to increase the heap size (must be a power of 2)

#if B_HAIKU_64_BIT
static const addr_t kHeapReservationBase = 0x100100000000;
static const addr_t kHeapReservationSize = 0x1000000000;
#else
static const addr_t kHeapReservationBase = 0x18000000;
static const addr_t kHeapReservationSize = 0x48000000;
#endif

static area_id sHeapArea;
static hoardLockType sHeapLock;
static void *sHeapBase;
static addr_t sFreeHeapBase;
static size_t sFreeHeapSize, sHeapAreaSize;
static free_chunk *sFreeChunks;


void
__init_after_fork(void)
{
        // find the heap area
        sHeapArea = area_for((void*)sFreeHeapBase);
        if (sHeapArea < 0) {
                // Where is it gone?
                debug_printf("hoard: init_after_fork(): thread %" B_PRId32 ", Heap "
                        "area not found! Base address: %p\n", find_thread(NULL),
                        sHeapBase);
                exit(1);
        }
}


extern "C" status_t
__init_heap(void)
{
        hoardHeap::initNumProcs();

        // This will locate the heap base at 384 MB and reserve the next 1152 MB
        // for it. They may get reclaimed by other areas, though, but the maximum
        // size of the heap is guaranteed until the space is really needed.
        sHeapBase = (void *)kHeapReservationBase;
        status_t status = _kern_reserve_address_range((addr_t *)&sHeapBase,
                B_RANDOMIZED_BASE_ADDRESS, kHeapReservationSize);
        if (status != B_OK)
                sHeapBase = NULL;

        uint32 protection = B_READ_AREA | B_WRITE_AREA;
        if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
                protection |= B_EXECUTE_AREA;
        sHeapArea = create_area("heap", (void **)&sHeapBase,
                status == B_OK ? B_EXACT_ADDRESS : B_RANDOMIZED_BASE_ADDRESS,
                kInitialHeapSize, B_NO_LOCK, protection);
        if (sHeapArea < B_OK)
                return sHeapArea;

        sFreeHeapBase = (addr_t)sHeapBase;
        sHeapAreaSize = kInitialHeapSize;

        hoardLockInit(sHeapLock, "heap");

        return B_OK;
}


extern "C" void
__heap_terminate_after()
{
        // nothing to do
}


static void
insert_chunk(free_chunk *newChunk)
{
        free_chunk *chunk = (free_chunk *)sFreeChunks, *smaller = NULL;
        for (; chunk != NULL; chunk = chunk->next) {
                if (chunk->size < newChunk->size)
                        smaller = chunk;
                else
                        break;
        }

        if (smaller) {
                newChunk->next = smaller->next;
                smaller->next = newChunk;
        } else {
                newChunk->next = sFreeChunks;
                sFreeChunks = newChunk;
        }
}


namespace BPrivate {

void *
hoardSbrk(long size)
{
        assert(size > 0);
        CTRACE(("sbrk: size = %ld\n", size));

        // align size request
        size = (size + hoardHeap::ALIGNMENT - 1) & ~(hoardHeap::ALIGNMENT - 1);

        // choose correct protection flags
        uint32 protection = B_READ_AREA | B_WRITE_AREA;
        if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
                protection |= B_EXECUTE_AREA;

        hoardLock(sHeapLock);

        // find chunk in free list
        free_chunk *chunk = sFreeChunks, *last = NULL;
        for (; chunk != NULL; chunk = chunk->next) {
                CTRACE(("  chunk %p (%ld)\n", chunk, chunk->size));

                if (chunk->size < (size_t)size) {
                        last = chunk;
                        continue;
                }

                // this chunk is large enough to satisfy the request

                SERIAL_PRINT(("HEAP-%" B_PRId32 ": "
                        "found free chunk to hold %ld bytes\n", find_thread(NULL), size));

                void *address = (void *)chunk;

                if (chunk->size > (size_t)size + sizeof(free_chunk)) {
                        // divide this chunk into smaller bits
                        size_t newSize = chunk->size - size;
                        free_chunk *next = chunk->next;

                        chunk = (free_chunk *)((addr_t)chunk + size);
                        chunk->next = next;
                        chunk->size = newSize;

                        if (last != NULL) {
                                last->next = next;
                                insert_chunk(chunk);
                        } else
                                sFreeChunks = chunk;
                } else {
                        chunk = chunk->next;

                        if (last != NULL)
                                last->next = chunk;
                        else
                                sFreeChunks = chunk;
                }

                hoardUnlock(sHeapLock);
                return address;
        }

        // There was no chunk, let's see if the area is large enough

        size_t oldHeapSize = sFreeHeapSize;
        sFreeHeapSize += size;

        // round to next heap increment aligned size
        size_t incrementAlignedSize = (sFreeHeapSize + kHeapIncrement - 1)
                & ~(kHeapIncrement - 1);

        if (incrementAlignedSize <= sHeapAreaSize) {
                SERIAL_PRINT(("HEAP-%" B_PRId32 ": heap area large enough for %ld\n",
                        find_thread(NULL), size));
                // the area is large enough already
                hoardUnlock(sHeapLock);
                return (void *)(sFreeHeapBase + oldHeapSize);
        }

        // We need to grow the area

        SERIAL_PRINT(("HEAP-%" B_PRId32 ": need to resize heap area to %ld "
                "(%ld requested)\n", find_thread(NULL), incrementAlignedSize, size));

        status_t status = resize_area(sHeapArea, incrementAlignedSize);
        if (status != B_OK) {
                // Either the system is out of memory or another area is in the way and
                // prevents ours from being resized. As a special case of the latter
                // the user might have mmap()ed something over malloc()ed memory. This
                // splits the heap area in two, the first one retaining the original
                // area ID. In either case, if there's still memory, it is a good idea
                // to try and allocate a new area.
                sFreeHeapSize = oldHeapSize;

                if (status == B_NO_MEMORY) {
                        hoardUnlock(sHeapLock);
                        return NULL;
                }

                size_t newHeapSize = (size + kHeapIncrement - 1) / kHeapIncrement
                        * kHeapIncrement;

                // First try at the location directly after the current heap area, if
                // that is still in the reserved memory region.
                void* base = (void*)(sFreeHeapBase + sHeapAreaSize);
                area_id area = -1;
                if (sHeapBase != NULL
                        && base >= sHeapBase
                        && (addr_t)base + newHeapSize
                                <= (addr_t)sHeapBase + kHeapReservationSize) {
                        area = create_area("heap", &base, B_EXACT_ADDRESS, newHeapSize,
                                B_NO_LOCK, protection);

                        if (area == B_NO_MEMORY) {
                                hoardUnlock(sHeapLock);
                                return NULL;
                        }
                }

                // If we don't have an area yet, try again with a free location
                // allocation.
                if (area < 0) {
                        base = (void*)(sFreeHeapBase + sHeapAreaSize);
                        area = create_area("heap", &base, B_RANDOMIZED_BASE_ADDRESS,
                                newHeapSize, B_NO_LOCK, protection);
                }

                if (area < 0) {
                        hoardUnlock(sHeapLock);
                        return NULL;
                }

                // We have a new area, so make it the new heap area.
                sHeapArea = area;
                sFreeHeapBase = (addr_t)base;
                sHeapAreaSize = newHeapSize;
                sFreeHeapSize = size;
                oldHeapSize = 0;
        } else
                sHeapAreaSize = incrementAlignedSize;

        hoardUnlock(sHeapLock);
        return (void *)(sFreeHeapBase + oldHeapSize);
}


void
hoardUnsbrk(void *ptr, long size)
{
        CTRACE(("unsbrk: %p, %ld!\n", ptr, size));

        hoardLock(sHeapLock);

        // TODO: hoard always allocates and frees in typical sizes, so we could
        //      save a lot of effort if we just had a similar mechanism

        // We add this chunk to our free list - first, try to find an adjacent
        // chunk, so that we can merge them together

        free_chunk *chunk = (free_chunk *)sFreeChunks, *last = NULL, *smaller = NULL;
        for (; chunk != NULL; chunk = chunk->next) {
                if ((addr_t)chunk + chunk->size == (addr_t)ptr
                        || (addr_t)ptr + size == (addr_t)chunk) {
                        // chunks are adjacent - merge them

                        CTRACE(("  found adjacent chunks: %p, %ld\n", chunk, chunk->size));
                        if (last)
                                last->next = chunk->next;
                        else
                                sFreeChunks = chunk->next;

                        if ((addr_t)chunk < (addr_t)ptr)
                                chunk->size += size;
                        else {
                                free_chunk *newChunk = (free_chunk *)ptr;
                                newChunk->next = chunk->next;
                                newChunk->size = size + chunk->size;
                                chunk = newChunk;
                        }

                        insert_chunk(chunk);
                        hoardUnlock(sHeapLock);
                        return;
                }

                last = chunk;

                if (chunk->size < (size_t)size)
                        smaller = chunk;
        }

        // we didn't find an adjacent chunk, so insert the new chunk into the list

        free_chunk *newChunk = (free_chunk *)ptr;
        newChunk->size = size;
        if (smaller) {
                newChunk->next = smaller->next;
                smaller->next = newChunk;
        } else {
                newChunk->next = sFreeChunks;
                sFreeChunks = newChunk;
        }

        hoardUnlock(sHeapLock);
}


void
hoardLockInit(hoardLockType &lock, const char *name)
{
        mutex_init_etc(&lock, name, MUTEX_FLAG_ADAPTIVE);
}


void
hoardLock(hoardLockType &lock)
{
        mutex_lock(&lock);
}


void
hoardUnlock(hoardLockType &lock)
{
        mutex_unlock(&lock);
}


void
hoardYield(void)
{
        _kern_thread_yield();
}

}       // namespace BPrivate