/* vim: set ts=4 sw=4 tw=99 et:
 *
 * Copyright (C) 2012 David Anderson
 *
 * This file is part of JITCraft.
 *
 * JITCraft is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 * 
 * Foobar 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * JITCraft. If not, see http://www.gnu.org/licenses/.
 */
#include <string.h>
#include "Zone.h"
#include "Spaces.h"
#include "Platform.h"
#include "Spaces-inl.h"
#include "Heap-inl.h"

using namespace ke;

HeapStack::HeapStack()
  : chunk_(NULL),
    cursor_(NULL)
{
}

HeapStack::~HeapStack()
{
    if (chunk_)
        HeapChunk::Destroy(chunk_);
}

bool
HeapStack::initialize()
{
    chunk_ = HeapChunk::New(NULL, kStackSize);
    cursor_ = chunk_->first();
    return true;
}

HeapChunk *
HeapChunk::New(HeapChunk *prev, size_t size)
{
    OS::AlignableMapping map = 
        OS::MapAlignedMemory(size, HeapChunk::kAlignment, OS::Map_Commit);

    if (!map.base())
        return NULL;

    HeapChunk *chunk = reinterpret_cast<HeapChunk *>(map.aligned());
    chunk->base_ = map.base();
    chunk->end_ = map.base() + map.size();
    if (prev)
        prev->next_ = chunk;

    return chunk;
}

void
HeapChunk::Destroy(HeapChunk *chunk)
{
    OS::UnmapAlignedMemory(chunk->base(), chunk->size());
}

void
HeapChunk::resetMarkBits()
{
    memset(markBits(), 0, kMarkBytes);
}

FreeList::FreeList()
  : small_objects_(NULL),
    medium_objects_(NULL),
    large_objects_(NULL),
    huge_objects_(NULL)
{
}

void
FreeList::add(FreedObject *obj)
{
    if (obj->size() < kMinObjectSize) 
        return;

    FreedObject **list;
    if (obj->size() < kMaxSmallObject)
        list = &small_objects_;
    else if (obj->size() < kMaxMediumObject)
        list = &medium_objects_;
    else if (obj->size() < kMaxLargeObject)
        list = &large_objects_;
    else
        list = &huge_objects_;

    if (*list)
        (*list)->setNext(obj);
    *list = obj;
}

FreedObject *
FreeList::pick(size_t size)
{
    if (size < kMinObjectSize && small_objects_) {
        FreedObject *obj = small_objects_;
        small_objects_ = small_objects_->next();
        return obj;
    }
    if (size < kMaxSmallObject && medium_objects_) {
        FreedObject *obj = medium_objects_;
        medium_objects_ = medium_objects_->next();
        return obj;
    }
    if (size < kMaxMediumObject && large_objects_) {
        FreedObject *obj = large_objects_;
        large_objects_ = large_objects_->next();
        return obj;
    }
    if (huge_objects_) {
        FreedObject *obj = huge_objects_;
        huge_objects_ = huge_objects_->next();
        return obj;
    }
    return NULL;
}

void
FreeList::reset()
{
    small_objects_ = NULL;
    medium_objects_ = NULL;
    large_objects_ = NULL;
    huge_objects_ = NULL;
}

OldSpace::OldSpace(Zone *zone)
  : zone_(zone),
    first_(NULL),
    last_(NULL)
{
}

bool
OldSpace::initialize()
{
    first_ = HeapChunk::New(first_, HeapChunk::kDefaultSize);
    last_ = first_;
    cursor_ = first_->first();

    return !!first_;
}

OldSpace::~OldSpace()
{
    while (first_) {
        HeapChunk *temp = first_->next();
        HeapChunk::Destroy(first_);
        first_ = temp;
    }
}

Address
OldSpace::allocateSlow(size_t nbytes)
{
    if (FreedObject *obj = freelist_.pick(nbytes)) {
        Address address = reinterpret_cast<Address>(obj);
        size_t actual = obj->size();
        assert(actual >= nbytes);
        if (actual != nbytes)
            markRegionFree(address + nbytes, actual - nbytes);

        return address;
    }

    // Free unused stuff at the end of the current chunk.
    if (cursor_ != last_->end())
        markRegionFree(cursor_, last_->end() - cursor_);

    HeapChunk *chunk;
    if (last_->next()) {
        // The next chunk is guaranteed to be empty.
        chunk = last_->next();
    } else {
        chunk = HeapChunk::New(last_, HeapChunk::kDefaultSize);
        if (!chunk)
            return NULL;
    }

    last_ = chunk;
    cursor_ = chunk->first();

    assert(cursor_ + nbytes <= chunk->end());

    Address address = cursor_;
    cursor_ += nbytes;
    return address;
}

void
OldSpace::markRegionFree(Address start, size_t length)
{
    FreedObject *obj = reinterpret_cast<FreedObject *>(start);
    new (obj) FreedObject(zone_->getMap(MapKind_FreeRegion), length);

    if (length < sizeof(FreedObject)) {
        // Can't encode a list in this object, but it's marked free, so we're done.
        return;
    }

    freelist_.add(obj);
}

void
OldSpace::freeUnusedPages()
{
    HeapChunk **prev = &first_;
    HeapChunk *empty = NULL;
    while (*prev) {
        HeapChunk *chunk = *prev;
        if (chunk->isEmpty()) {
            *prev = chunk->next();
            if (empty) {
                // Remove this chunk.
                HeapChunk::Destroy(chunk);
                continue;
            }
            empty = chunk;                
        }
        prev = chunk->nextp();
    }

    if (empty) {
        *empty->nextp() = NULL;
        *last_->nextp() = empty;
    }
}

void
OldSpace::resetFreeList()
{
    freelist_.reset();
}

LargeObjectSpace::LargeObjectSpace()
  : first_(NULL),
    last_(NULL)
{
}

LargeObjectSpace::~LargeObjectSpace()
{
    while (first_) {
        HeapChunk *temp = first_->next();
        HeapChunk::Destroy(first_);
        first_ = temp;
    }
}

bool
LargeObjectSpace::initialize()
{
    return true;
}

Address
LargeObjectSpace::allocate(size_t nbytes)
{
    assert(IsAligned(nbytes, kObjectAlignment));

    // Always allocate a new chunk for large objects.
    HeapChunk *chunk = HeapChunk::New(last_, nbytes);
    if (!chunk)
        return NULL;

    if (!first_)
        first_ = chunk;
    last_ = chunk;

    return chunk->first();
}

void
LargeObjectSpace::sweep()
{
    if (!first_)
        return;

    HeapChunk **pprev = &first_;
    do {
        HeapChunk *chunk = *pprev;
        Object *obj = reinterpret_cast<Object *>(chunk->first());
        MarkBit bit = HeapChunk::GetMarkBit(obj);
        if (HeapChunk::IsWhite(bit)) {
            *pprev = chunk->next();
            HeapChunk::Destroy(chunk);
        } else {
            assert(HeapChunk::IsBlack(bit));
            HeapChunk::Clear(bit);
            pprev = chunk->nextp();
            last_ = chunk;
        }
    } while (*pprev);
}