/* 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 *);

 // 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);

         uint32 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() {

         while (current_ && current_ != top_) {

             Object *obj = reinterpret_cast<Object *>(current_);

             size_t size = evaluator_(obj, obj->map());

             current_ += size;

             if (current_ == chunk_->end()) {

                 chunk_ = chunk_->next();

                 current_ = chunk_ ? chunk_->first() : NULL;

             }

             if (obj->is(MapKind_FreeRegion))

                 continue;

         }

         return NULL;

     }

 };

 class FreedObject

 {

     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_