dvander@49: /* vim: set ts=4 sw=4 tw=99 et:
dvander@49:  *
dvander@49:  * Copyright (C) 2012 David Anderson
dvander@49:  *
dvander@49:  * This file is part of JITCraft.
dvander@49:  *
dvander@49:  * JITCraft is free software: you can redistribute it and/or modify it under
dvander@49:  * the terms of the GNU General Public License as published by the Free
dvander@49:  * Software Foundation, either version 3 of the License, or (at your option)
dvander@49:  * any later version.
dvander@49:  * 
dvander@49:  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@49:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@49:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@49:  *
dvander@49:  * You should have received a copy of the GNU General Public License along with
dvander@49:  * JITCraft. If not, see http://www.gnu.org/licenses/.
dvander@49:  */
dvander@49: #ifndef _include_jitcraft_spaces_h_
dvander@49: #define _include_jitcraft_spaces_h_
dvander@49: 
dvander@49: #include <limits.h>
dvander@49: #include "Utility.h"
dvander@49: #include "Platform.h"
dvander@49: 
dvander@59: namespace ke {
dvander@49: 
dvander@53: class Zone;
dvander@49: class Object;
dvander@53: class Map;
dvander@49: 
dvander@52: static const size_t kObjectAlignment = sizeof(Object *);
dvander@52: 
dvander@52: // Every object gets two successive mark bits. These bits represent various
dvander@52: // states during garbage collection:
dvander@52: //
dvander@52: //  WHITE (00): The object is dead or unmarked.
dvander@52: //  GREY  (11): The object is live but its children have not been marked.
dvander@52: //  BLACK (10): The object and all its children have been marked.
dvander@52: //
dvander@52: // These colors assist in maintaining the "tri-color invariant", explained
dvander@52: // in Heap.h. The bits are organized such that transitioning an object from
dvander@52: // White to Black requires one bit change, and Black to Grey requires another.
dvander@52: class MarkBit
dvander@52: {
dvander@52:     uint32 *word_;
dvander@52:     uint32 bit_;
dvander@52: 
dvander@52:   public:
dvander@52:     MarkBit(uint32 *word, uint32 bit)
dvander@52:       : word_(word),
dvander@52:         bit_(bit)
dvander@52:     {
dvander@52:         assert(bit_ < sizeof(*word_) * 8);
dvander@52:     }
dvander@52: 
dvander@52:     bool isSet() const {
dvander@52:         return !!(*word_ & (1 << bit_));
dvander@52:     }
dvander@52:     void set() {
dvander@52:         *word_ |= (1 << bit_);
dvander@52:     }
dvander@53:     void unset() {
dvander@53:         *word_ &= ~(1 << bit_);
dvander@53:     }
dvander@53:     uint32 *word() {
dvander@53:         return word_;
dvander@53:     }
dvander@52:     MarkBit next() const {
dvander@52:         if (bit_ == (sizeof(*word_) * 8) - 1)
dvander@52:             return MarkBit(word_ + 1, 0);
dvander@52:         return MarkBit(word_, bit_ + 1);
dvander@52:     }
dvander@52: };
dvander@49: 
dvander@11: class HeapChunk
dvander@11: {
dvander@11:     HeapChunk *next_;
dvander@11: 
dvander@11:     // Base address, from OS::AlignableMapping.
dvander@11:     Address base_;
dvander@11: 
dvander@11:     // End of the allocated region.
dvander@11:     Address end_;
dvander@11: 
dvander@51:     uintptr_t flags_;
dvander@51: 
dvander@51:   public:
dvander@51:     enum Flag {
dvander@53:         HAS_OVERFLOWED_OBJECT = (1 << 0),
dvander@53:         EMPTY = (1 << 1)
dvander@51:     };
dvander@11: 
dvander@11:   public:
dvander@49:     static const size_t kDefaultSize = 1 * kMB;
dvander@49:     static const size_t kAlignment = 1 * kMB;
dvander@49: 
dvander@49:     // Maximum size of an object that will fit in a page. We limit this
dvander@49:     // specifically to help JITs: the computation of a[i] has a special
dvander@49:     // instruction form on most CPUs, but the index might not be sign-
dvander@49:     // extended on 64-bit architectures. We limit the size such that:
dvander@49:     //
dvander@49:     //    index * sizeof(Object *)
dvander@49:     //
dvander@49:     // Is guaranteed to not overflow a signed 32-bit integer.
dvander@49:     static const size_t kMaxObjectSize = INT_MAX / sizeof(Object *);
dvander@49: 
dvander@49:     // Size of a HeapChunk header.
dvander@49:     static const size_t kHeaderSize =
dvander@49:         sizeof(HeapChunk *) +
dvander@49:         sizeof(Address) +
dvander@49:         sizeof(Address) +
dvander@49:         sizeof(Address);
dvander@11: 
dvander@11:     // All objects must be allocated in the first kAlignment bytes of the
dvander@52:     // chunk. We need two mark bits for every allocatable object, since there
dvander@52:     // are three possible states: White (00), Black (11), and Grey (10). These
dvander@52:     // bits are stored immediately after the HeapChunk header, and before the
dvander@52:     // first allocatable object.
dvander@52:     //
dvander@52:     // Although object alignment is only at word boundaries, we guarantee that
dvander@52:     // every object is at least two words. This means we don't need to reserve
dvander@52:     // two mark bits for every object, just one mark bit for every allocatable
dvander@52:     // address. That also means a pair of mark bits can cross a byte boundary.
dvander@52:     //
dvander@52:     // --- Math ---
dvander@11:     //
dvander@11:     // The number of mark bits needed is:
dvander@11:     //
dvander@52:     // MaxObjectsPerChunk = (kAlignment / kObjectAlignment)
dvander@52:     //                    -> 256KB (128KB on 64-bit)
dvander@11:     //
dvander@11:     // The number of bytes needed for these mark bits is:
dvander@11:     //
dvander@11:     // NumMarkBytes       = MaxObjectsPerChunk / 8
dvander@52:     //                    = 32KB (16KB on 64-bit)
dvander@11:     //
dvander@11:     // The number of uint32s needed to store these bytes is:
dvander@11:     //
dvander@11:     // NumMarkWords       = NumMarkBytes / sizeof(uint32)
dvander@52:     //                    = 8KB (4KB on 64-bit)
dvander@52:     //
dvander@11:     static const size_t kMaxObjectsPerChunk = kAlignment / kObjectAlignment;
dvander@11:     static const size_t kMarkBits = kMaxObjectsPerChunk;
dvander@11:     static const size_t kMarkBytes = kMarkBits / 8;
dvander@11:     static const size_t kMarkWords = kMarkBytes / sizeof(uint32);
dvander@52:     static const size_t kMarkBitsPerWord = sizeof(uint32) * 8;
dvander@11: 
dvander@49:     static const size_t kMarkBitsOffset = kHeaderSize;
dvander@49:     static const size_t kFirstObject = kMarkBitsOffset + kMarkBytes;
dvander@11: 
dvander@49:     // Threshold for allocating an object in the large object space.
dvander@49:     static const size_t kLargeObjectThreshold = kAlignment - kFirstObject;
dvander@49: 
dvander@49:     static inline void StaticAsserts() {
dvander@49:         STATIC_ASSERT(kHeaderSize == sizeof(HeapChunk));
dvander@49:         STATIC_ASSERT(IS_ALIGNED(kHeaderSize, kObjectAlignment));
dvander@49:         STATIC_ASSERT(IS_ALIGNED(kFirstObject, kObjectAlignment));
dvander@11:     }
dvander@11: 
dvander@11:   public:
dvander@11:     static HeapChunk *New(HeapChunk *prev, size_t size);
dvander@11:     static void Destroy(HeapChunk *chunk);
dvander@11: 
dvander@11:   public:
dvander@11:     HeapChunk *next() {
dvander@11:         return next_;
dvander@11:     }
dvander@11:     Address base() {
dvander@11:         return base_;
dvander@11:     }
dvander@53:     Address address() {
dvander@53:         return reinterpret_cast<Address>(this);
dvander@53:     }
dvander@11:     Address end() {
dvander@11:         return end_;
dvander@11:     }
dvander@11:     size_t size() {
dvander@11:         return end() - base();
dvander@11:     }
dvander@11:     Address first() {
dvander@49:         return reinterpret_cast<Address>(this) + kFirstObject;
dvander@11:     }
dvander@53:     HeapChunk **nextp() {
dvander@53:         return &next_;
dvander@53:     }
dvander@53:     uint32 *markBits() {
dvander@53:         return reinterpret_cast<uint32 *>(reinterpret_cast<Address>(this) + kMarkBitsOffset);
dvander@53:     }
dvander@53:     void resetMarkBits();
dvander@52: 
dvander@52:     // Marking functions.
dvander@52:     static inline MarkBit GetMarkBit(Object *obj) {
dvander@52:         uintptr_t address = reinterpret_cast<uintptr_t>(obj);
dvander@52: 
dvander@52:         HeapChunk *chunk = reinterpret_cast<HeapChunk *>(address & ~(kAlignment - 1));
dvander@52:         assert(Address(obj) >= chunk->first() && Address(obj) < chunk->end());
dvander@52: 
dvander@52:         size_t index = (address & (kAlignment - 1)) / kObjectAlignment;
dvander@52:         assert(index < kMaxObjectsPerChunk);
dvander@52: 
dvander@52:         uint32 *word = chunk->markBits() + (index / kMarkBitsPerWord);
dvander@52:         uint32 bit = index & (kMarkBitsPerWord - 1);
dvander@52:         return MarkBit(word, bit);
dvander@52:     }
dvander@53:     static inline Address FromMarkBit(HeapChunk *chunk, uint32 *word, uint32 bit) {
dvander@53:         // word = bits + (index / kMarkBitsPerWord)
dvander@53:         // word - bits = index / kMarkBitsPerWord
dvander@53:         // (word - bits) * kMarkBitsPerWord = index
dvander@53:         assert(word >= chunk->markBits() && word < chunk->markBits() + kMarkWords);
dvander@53:         uint32 index = ((word - chunk->markBits()) * kMarkBitsPerWord) + bit;
dvander@53:         return chunk->address() + (index * kObjectAlignment);
dvander@53:     }
dvander@52:     static inline bool IsWhite(const MarkBit &bit) {
dvander@52:         assert(bit.isSet() || !bit.next().isSet());
dvander@52:         return !bit.isSet();
dvander@52:     }
dvander@52:     static inline bool IsBlack(const MarkBit &bit) {
dvander@52:         return bit.isSet() && !bit.next().isSet();
dvander@52:     }
dvander@52:     static inline bool IsGrey(const MarkBit &bit) {
dvander@52:         return bit.isSet() && bit.next().isSet();
dvander@52:     }
dvander@52:     static inline bool IsBlackOrGrey(const MarkBit &bit) {
dvander@52:         return bit.isSet();
dvander@52:     }
dvander@52:     static inline void WhiteToBlack(MarkBit &bit) {
dvander@52:         assert(IsWhite(bit));
dvander@52:         bit.set();
dvander@52:     }
dvander@52:     static inline void BlackToGrey(MarkBit &bit) {
dvander@53:         assert(IsBlack(bit));
dvander@53:         bit.next().set();
dvander@53:     }
dvander@53:     static inline void GreyToBlack(MarkBit &bit) {
dvander@52:         assert(IsGrey(bit));
dvander@53:         bit.next().unset();
dvander@53:     }
dvander@53:     static inline void Clear(MarkBit &bit) {
dvander@53:         bit.unset();
dvander@53:         bit.next().unset();
dvander@11:     }
dvander@51: 
dvander@51:     bool hasOverflowedObject() {
dvander@51:         return !!(flags_ & HAS_OVERFLOWED_OBJECT);
dvander@51:     }
dvander@51:     void setHasOverflowedObject() {
dvander@51:         flags_ |= HAS_OVERFLOWED_OBJECT;
dvander@51:     }
dvander@53:     bool isEmpty() {
dvander@53:         return !!(flags_ & EMPTY);
dvander@53:     }
dvander@53:     void setEmpty() {
dvander@53:         flags_ |= EMPTY;
dvander@53:     }
dvander@53: };
dvander@53: 
dvander@53: template <typename SizeEvaluator>
dvander@53: class ChunkObjectIteratorBase
dvander@53: {
dvander@53:     HeapChunk *chunk_;
dvander@53:     Address top_;
dvander@53:     SizeEvaluator evaluator_;
dvander@53:     Address current_;
dvander@53: 
dvander@53:   public:
dvander@53:     ChunkObjectIteratorBase(HeapChunk *start, Address top, const SizeEvaluator &evaluator)
dvander@53:       : chunk_(start),
dvander@53:         top_(top),
dvander@53:         evaluator_(evaluator),
dvander@53:         current_(start ? start->first() : NULL)
dvander@53:     {
dvander@53:     }
dvander@53: 
dvander@53:     Object *next() {
dvander@53:         while (current_ && current_ != top_) {
dvander@53:             Object *obj = reinterpret_cast<Object *>(current_);
dvander@53:             size_t size = evaluator_(obj, obj->map());
dvander@53:             current_ += size;
dvander@53:             if (current_ == chunk_->end()) {
dvander@53:                 chunk_ = chunk_->next();
dvander@53:                 current_ = chunk_ ? chunk_->first() : NULL;
dvander@53:             }
dvander@53:             if (obj->is(MapKind_FreeRegion))
dvander@53:                 continue;
dvander@53:         }
dvander@53:         return NULL;
dvander@53:     }
dvander@11: };
dvander@11: 
dvander@53: class FreedObject
dvander@52: {
dvander@53:     Map *map_;
dvander@53:     size_t bytes_;
dvander@53:     FreedObject *next_;
dvander@53: 
dvander@53:   public:
dvander@53:     FreedObject(Map *map, size_t bytes)
dvander@53:       : map_(map),
dvander@53:         bytes_(bytes)
dvander@53:     {
dvander@53:         assert(bytes_ >= sizeof(Map *) + sizeof(size_t));
dvander@53:         if (bytes_ >= sizeof(FreedObject))
dvander@53:             next_ = NULL;
dvander@53:     }
dvander@53: 
dvander@53:     void setNext(FreedObject *obj) {
dvander@53:         assert(bytes_ >= sizeof(FreedObject));
dvander@53:         next_ = obj;
dvander@53:     }
dvander@53:     FreedObject *next() {
dvander@53:         assert(bytes_ >= sizeof(FreedObject));
dvander@53:         return next_;
dvander@53:     }
dvander@53:     size_t size() {
dvander@53:         return bytes_;
dvander@53:     }
dvander@53: };
dvander@53: 
dvander@53: // Free-region list used in old spaces. Based on V8's. Each object pool
dvander@53: // is used to allocate objects of the previous pool's size. For example,
dvander@53: // the medium object pool is used to allocate small objects.
dvander@53: class FreeList
dvander@53: {
dvander@53:   private:
dvander@53:     static const size_t kMinObjectSize = 32;
dvander@53:     static const size_t kMaxSmallObject = 255;
dvander@53:     static const size_t kMaxMediumObject = (2 * kKB) - 1;
dvander@53:     static const size_t kMaxLargeObject = (16 * kKB) - 1;
dvander@53: 
dvander@53:   public:
dvander@53:     FreeList();
dvander@53: 
dvander@53:   public:
dvander@53:     void add(FreedObject *obj);
dvander@53:     FreedObject *pick(size_t size);
dvander@53:     void reset();
dvander@53: 
dvander@53:   private:
dvander@53:     FreedObject *small_objects_;
dvander@53:     FreedObject *medium_objects_;
dvander@53:     FreedObject *large_objects_;
dvander@53:     FreedObject *huge_objects_;
dvander@52: };
dvander@52: 
dvander@51: // The heap stack is designed for structures which are known to not escape the
dvander@51: // program stack, and can thus be quickly allocated in a LIFO manner.
dvander@51: // 
dvander@51: class HeapStack
dvander@51: {
dvander@51:     OS::AlignableMapping map_;
dvander@51:     HeapChunk *chunk_;
dvander@51:     Address cursor_;
dvander@51:     uintptr_t mask_;
dvander@51: 
dvander@51:   private:
dvander@51:     static const size_t kStackSize = 1024 * 1024;
dvander@51: 
dvander@51:   public:
dvander@51:     HeapStack();
dvander@51:     ~HeapStack();
dvander@51:     bool initialize();
dvander@51: 
dvander@51:   public:
dvander@51:     Address position() const {
dvander@51:         return cursor_;
dvander@51:     }
dvander@51:     inline Address allocate(size_t nbytes);
dvander@51:     inline void unwind(Address to);
dvander@51: 
dvander@51:     inline bool contains(Object *obj) {
dvander@51:         return (reinterpret_cast<uintptr_t>(obj) & mask_) == reinterpret_cast<uintptr_t>(chunk_);
dvander@51:     }
dvander@53: 
dvander@53:     template <typename Evaluator>
dvander@53:     ChunkObjectIteratorBase<Evaluator> begin(const Evaluator &evaluator) {
dvander@53:         return ChunkObjectIteratorBase<Evaluator>(chunk_, cursor_, evaluator);
dvander@53:     }
dvander@51: };
dvander@51: 
dvander@11: class OldSpace
dvander@11: {
dvander@53:     Zone *zone_;
dvander@11:     HeapChunk *first_;
dvander@11:     HeapChunk *last_;
dvander@51:     Address cursor_;
dvander@53:     FreeList freelist_;
dvander@11: 
dvander@11:   public:
dvander@53:     OldSpace(Zone *zone);
dvander@11:     ~OldSpace();
dvander@11: 
dvander@11:     bool initialize();
dvander@11: 
dvander@11:   public:
dvander@11:     inline Address allocate(size_t nbytes);
dvander@11:     Address allocateSlow(size_t nbytes);
dvander@53:     void markRegionFree(Address start, size_t size);
dvander@53:     void freeUnusedPages();
dvander@53: 
dvander@53:     template <typename Evaluator>
dvander@53:     ChunkObjectIteratorBase<Evaluator> begin(const Evaluator &evaluator) {
dvander@53:         return ChunkObjectIteratorBase<Evaluator>(first_, cursor_, evaluator);
dvander@53:     }
dvander@53: 
dvander@53:     HeapChunk *first() {
dvander@53:         return first_;
dvander@53:     }
dvander@53:     void resetFreeList();
dvander@49: };
dvander@49: 
dvander@49: class LargeObjectSpace
dvander@49: {
dvander@49:     HeapChunk *first_;
dvander@49:     HeapChunk *last_;
dvander@49: 
dvander@49:   public:
dvander@49:     LargeObjectSpace();
dvander@49:     ~LargeObjectSpace();
dvander@49: 
dvander@49:     bool initialize();
dvander@49: 
dvander@49:   public:
dvander@49:     Address allocate(size_t nbytes);
dvander@53: 
dvander@53:     HeapChunk *first() {
dvander@53:         return first_;
dvander@53:     }
dvander@53:     void sweep();
dvander@49: };
dvander@49: 
dvander@49: }
dvander@49: 
dvander@49: #endif // _include_jitcraft_spaces_h_