/* 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/.

 */

#ifndef _include_jitcraft_spaces_h_

#define _include_jitcraft_spaces_h_

#include <limits.h>

#include "Utility.h"

#include "Platform.h"

namespace ke {

class Zone;

class Object;

class Map;

static const size_t kObjectAlignment = sizeof(Object *);

static const size_t kMinObjectSize   = sizeof(Object *) * 2;

// Every object gets two successive mark bits. These bits represent various

// states during garbage collection:

//

//  WHITE (00): The object is dead or unmarked.

//  GREY  (11): The object is live but its children have not been marked.

//  BLACK (10): The object and all its children have been marked.

//

// These colors assist in maintaining the "tri-color invariant", explained

// in Heap.h. The bits are organized such that transitioning an object from

// White to Black requires one bit change, and Black to Grey requires another.

class MarkBit

{

    uint32 *word_;

    uint32 bit_;

  public:

    MarkBit(uint32 *word, uint32 bit)

      : word_(word),

        bit_(bit)

    {

        assert(bit_ < sizeof(*word_) * 8);

    }

    bool isSet() const {

        return !!(*word_ & (1 << bit_));

    }

    void set() {

        *word_ |= (1 << bit_);

    }

    void unset() {

        *word_ &= ~(1 << bit_);

    }

    uint32 *word() {

        return word_;

    }

    MarkBit next() const {

        if (bit_ == (sizeof(*word_) * 8) - 1)

            return MarkBit(word_ + 1, 0);

        return MarkBit(word_, bit_ + 1);

    }

};

class HeapChunk

{

    HeapChunk *next_;

    // Base address, from OS::AlignableMapping.

    Address base_;

    // End of the allocated region.

    Address end_;

    uintptr_t flags_;

  public:

    enum Flag {

        HAS_OVERFLOWED_OBJECT = (1 << 0),

        EMPTY = (1 << 1)

    };

  public:

    static const size_t kDefaultSize = 1 * kMB;

    static const size_t kAlignment = 1 * kMB;

    // Maximum size of an object that will fit in a page. We limit this

    // specifically to help JITs: the computation of a[i] has a special

    // instruction form on most CPUs, but the index might not be sign-

    // extended on 64-bit architectures. We limit the size such that:

    //

    //    index * sizeof(Object *)

    //

    // Is guaranteed to not overflow a signed 32-bit integer.

    static const size_t kMaxObjectSize = INT_MAX / sizeof(Object *);

    // Size of a HeapChunk header.

    static const size_t kHeaderSize =

        sizeof(HeapChunk *) +

        sizeof(Address) +

        sizeof(Address) +

        sizeof(Address);

    // All objects must be allocated in the first kAlignment bytes of the

    // chunk. We need two mark bits for every allocatable object, since there

    // are three possible states: White (00), Black (11), and Grey (10). These

    // bits are stored immediately after the HeapChunk header, and before the

    // first allocatable object.

    //

    // Although object alignment is only at word boundaries, we guarantee that

    // every object is at least two words. This means we don't need to reserve

    // two mark bits for every object, just one mark bit for every allocatable

    // address. That also means a pair of mark bits can cross a byte boundary.

    //

    // --- Math ---

    //

    // The number of mark bits needed is:

    //

    // MaxObjectsPerChunk = (kAlignment / kObjectAlignment)

    //                    -> 256KB (128KB on 64-bit)

    //

    // The number of bytes needed for these mark bits is:

    //

    // NumMarkBytes       = MaxObjectsPerChunk / 8

    //                    = 32KB (16KB on 64-bit)

    //

    // The number of uint32s needed to store these bytes is:

    //

    // NumMarkWords       = NumMarkBytes / sizeof(uint32)

    //                    = 8KB (4KB on 64-bit)

    //

    static const size_t kMaxObjectsPerChunk = kAlignment / kObjectAlignment;

    static const size_t kMarkBits = kMaxObjectsPerChunk;

    static const size_t kMarkBytes = kMarkBits / 8;

    static const size_t kMarkWords = kMarkBytes / sizeof(uint32);

    static const size_t kMarkBitsPerWord = sizeof(uint32) * 8;

    static const size_t kMarkBitsOffset = kHeaderSize;

    static const size_t kFirstObject = kMarkBitsOffset + kMarkBytes;

    // Threshold for allocating an object in the large object space.

    static const size_t kLargeObjectThreshold = kAlignment - kFirstObject;

    static inline void StaticAsserts() {

        STATIC_ASSERT(kHeaderSize == sizeof(HeapChunk));

        STATIC_ASSERT(IS_ALIGNED(kHeaderSize, kObjectAlignment));

        STATIC_ASSERT(IS_ALIGNED(kFirstObject, kObjectAlignment));

    }

  public:

    static HeapChunk *New(HeapChunk *prev, size_t size);

    static void Destroy(HeapChunk *chunk);

  public:

    HeapChunk *next() {

        return next_;

    }

    Address base() {

        return base_;

    }

    Address address() {

        return reinterpret_cast<Address>(this);

    }

    Address end() {

        return end_;

    }

    size_t size() {

        return end() - base();

    }

    Address first() {

        return reinterpret_cast<Address>(this) + kFirstObject;

    }

    HeapChunk **nextp() {

        return &next_;

    }

    uint32 *markBits() {

        return reinterpret_cast<uint32 *>(reinterpret_cast<Address>(this) + kMarkBitsOffset);

    }

    void resetMarkBits();

    // Marking functions.

    static inline MarkBit GetMarkBit(Object *obj) {

        uintptr_t address = reinterpret_cast<uintptr_t>(obj);

        HeapChunk *chunk = reinterpret_cast<HeapChunk *>(address & ~(kAlignment - 1));

        assert(Address(obj) >= chunk->first() && Address(obj) < chunk->end());

        size_t index = (address & (kAlignment - 1)) / kObjectAlignment;

        assert(index < kMaxObjectsPerChunk);

        uint32 *word = chunk->markBits() + (index / kMarkBitsPerWord);

        uint32 bit = index & (kMarkBitsPerWord - 1);

        return MarkBit(word, bit);

    }

    static inline Address FromMarkBit(HeapChunk *chunk, uint32 *word, uint32 bit) {

        // word = bits + (index / kMarkBitsPerWord)

        // word - bits = index / kMarkBitsPerWord

        // (word - bits) * kMarkBitsPerWord = index

        assert(word >= chunk->markBits() && word < chunk->markBits() + kMarkWords);

        size_t index = ((word - chunk->markBits()) * kMarkBitsPerWord) + bit;

        return chunk->address() + (index * kObjectAlignment);

    }

    static inline bool IsWhite(const MarkBit &bit) {

        assert(bit.isSet() || !bit.next().isSet());

        return !bit.isSet();

    }

    static inline bool IsBlack(const MarkBit &bit) {

        return bit.isSet() && !bit.next().isSet();

    }

    static inline bool IsGrey(const MarkBit &bit) {

        return bit.isSet() && bit.next().isSet();

    }

    static inline bool IsBlackOrGrey(const MarkBit &bit) {

        return bit.isSet();

    }

    static inline void WhiteToBlack(MarkBit &bit) {

        assert(IsWhite(bit));

        bit.set();

    }

    static inline void BlackToGrey(MarkBit &bit) {

        assert(IsBlack(bit));

        bit.next().set();

    }

    static inline void GreyToBlack(MarkBit &bit) {

        assert(IsGrey(bit));

        bit.next().unset();

    }

    static inline void Clear(MarkBit &bit) {

        bit.unset();

        bit.next().unset();

    }

    bool hasOverflowedObject() {

        return !!(flags_ & HAS_OVERFLOWED_OBJECT);

    }

    void setHasOverflowedObject() {

        flags_ |= HAS_OVERFLOWED_OBJECT;

    }

    bool isEmpty() {

        return !!(flags_ & EMPTY);

    }

    void setEmpty() {

        flags_ |= EMPTY;

    }

};

template <typename SizeEvaluator>

class ChunkObjectIteratorBase

{

    HeapChunk *chunk_;

    Address top_;

    SizeEvaluator evaluator_;

    Address current_;

  public:

    ChunkObjectIteratorBase(HeapChunk *start, Address top, const SizeEvaluator &evaluator)

      : chunk_(start),

        top_(top),

        evaluator_(evaluator),

        current_(start ? start->first() : NULL)

    {

    }

    Object *next();

};

class FreedObject

{

  protected:

    Map *map_;

    size_t bytes_;

    FreedObject *next_;

  public:

    FreedObject(Map *map, size_t bytes)

      : map_(map),

        bytes_(bytes)

    {

        assert(bytes_ >= sizeof(Map *) + sizeof(size_t));

        if (bytes_ >= sizeof(FreedObject))

            next_ = NULL;

    }

    void setNext(FreedObject *obj) {

        assert(bytes_ >= sizeof(FreedObject));

        next_ = obj;

    }

    FreedObject *next() {

        assert(bytes_ >= sizeof(FreedObject));

        return next_;

    }

    size_t size() {

        return bytes_;

    }

};

// Free-region list used in old spaces. Based on V8's. Each object pool

// is used to allocate objects of the previous pool's size. For example,

// the medium object pool is used to allocate small objects.

class FreeList

{

  private:

    static const size_t kMinObjectSize = 32;

    static const size_t kMaxSmallObject = 255;

    static const size_t kMaxMediumObject = (2 * kKB) - 1;

    static const size_t kMaxLargeObject = (16 * kKB) - 1;

  public:

    FreeList();

  public:

    void add(FreedObject *obj);

    FreedObject *pick(size_t size);

    void reset();

  private:

    FreedObject *small_objects_;

    FreedObject *medium_objects_;

    FreedObject *large_objects_;

    FreedObject *huge_objects_;

};

// The heap stack is designed for structures which are known to not escape the

// program stack, and can thus be quickly allocated in a LIFO manner.

// 

class HeapStack

{

    OS::AlignableMapping map_;

    HeapChunk *chunk_;

    Address cursor_;

    uintptr_t mask_;

  private:

    static const size_t kStackSize = 1024 * 1024;

  public:

    HeapStack();

    ~HeapStack();

    bool initialize();

  public:

    Address position() const {

        return cursor_;

    }

    inline Address allocate(size_t nbytes);

    inline void unwind(Address to);

    inline bool contains(Object *obj) {

        return (reinterpret_cast<uintptr_t>(obj) & mask_) == reinterpret_cast<uintptr_t>(chunk_);

    }

    template <typename Evaluator>

    ChunkObjectIteratorBase<Evaluator> begin(const Evaluator &evaluator) {

        return ChunkObjectIteratorBase<Evaluator>(chunk_, cursor_, evaluator);

    }

};

class OldSpace

{

    Zone *zone_;

    HeapChunk *first_;

    HeapChunk *last_;

    Address cursor_;

    FreeList freelist_;

  public:

    OldSpace(Zone *zone);

    ~OldSpace();

    bool initialize();

  public:

    inline Address allocate(size_t nbytes);

    Address allocateSlow(size_t nbytes);

    void markRegionFree(Address start, size_t size);

    void freeUnusedPages();

    template <typename Evaluator>

    ChunkObjectIteratorBase<Evaluator> begin(const Evaluator &evaluator) {

        return ChunkObjectIteratorBase<Evaluator>(first_, cursor_, evaluator);

    }

    HeapChunk *first() {

        return first_;

    }

    void resetFreeList();

};

class LargeObjectSpace

{

    HeapChunk *first_;

    HeapChunk *last_;

  public:

    LargeObjectSpace();

    ~LargeObjectSpace();

    bool initialize();

  public:

    Address allocate(size_t nbytes);

    HeapChunk *first() {

        return first_;

    }

    void sweep();

};

}

#endif // _include_jitcraft_spaces_h_