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: #include "Heap.h"
dvander@49: #include "Heap-inl.h"
dvander@49: #include "Spaces-inl.h"
dvander@52: #include "VirtualObjectVisitor.h"
dvander@52: #include "ObjectVisitor.h"
dvander@52: #include "Zone.h"
dvander@54: #include "StringPool.h"
dvander@49: 
dvander@59: using namespace ke;
dvander@49: 
dvander@52: static const size_t kMarkStackSize = 256 * kKB;
dvander@52: 
dvander@49: Heap::Heap(Zone *zone)
dvander@52:   : zone_(zone),
dvander@53:     markStack_(NULL),
dvander@53:     oldSpace_(zone),
dvander@53:     mapSpace_(zone)
dvander@49: {
dvander@49: }
dvander@49: 
dvander@49: bool
dvander@49: Heap::initialize()
dvander@49: {
dvander@49:     if (!lifoSpace_.initialize())
dvander@49:         return false;
dvander@49:     if (!oldSpace_.initialize())
dvander@49:         return false;
dvander@49:     if (!mapSpace_.initialize())
dvander@49:         return false;
dvander@49:     if (!largeSpace_.initialize())
dvander@49:         return false;
dvander@49: 
dvander@52:     markStack_ = malloc(kMarkStackSize);
dvander@52:     if (!markStack_)
dvander@52:         return false;
dvander@52: 
dvander@49:     if ((metaMap_ = allocateMap(MapKind_Meta, sizeof(Map))) == NULL)
dvander@49:         return false;
dvander@49:     metaMap_->init(metaMap_);
dvander@49: 
dvander@49:     return true;
dvander@49: }
dvander@49: 
dvander@52: Heap::~Heap()
dvander@52: {
dvander@52:     free(markStack_);
dvander@52: }
dvander@52: 
dvander@49: Map *
dvander@49: Heap::allocateMap(MapKind kind, size_t bytes)
dvander@49: {
dvander@11:     size_t actualBytes = Align(bytes, kObjectAlignment);
dvander@11: 
dvander@11:     Address addr = mapSpace_.allocate(actualBytes);
dvander@11:     if (!addr) {
dvander@69:         reportOutOfMemory();
dvander@11:         return NULL;
dvander@11:     }
dvander@11: 
dvander@11:     // Note that we use a NULL type initially, and reinterpret-cast to get
dvander@11:     // the Type pointer, so we can allocate the self-referencing meta type.
dvander@11:     Object *obj = InitAddressIntoObject(addr, NULL);
dvander@11:     Map *map = reinterpret_cast<Map *>(obj);
dvander@11:     map->setKind(kind);
dvander@49:     return map;
dvander@49: }
dvander@49: 
dvander@52: // To avoid marking recursively, we use a worklist to manage the marking
dvander@52: // process. Algorithm:
dvander@52: //
dvander@52: // (1) While the mark stack is not empty:
dvander@52: //  (a) Remove object |o| from the mark stack.
dvander@52: //  (b) For each reference |p| in object |o|,
dvander@52: //   (i)  Mark |p| as Black.
dvander@52: //   (ii) Push |p| onto the mark stack.
dvander@52: //   (iv) If the mark stack overflowde, mark |p| as Grey.
dvander@52: //
dvander@52: // We run this algorithm after pushing every root object onto the mark stack.
dvander@52: // After all roots have been processed, it may be that the mark stack
dvander@52: // overflowed. In this case, we use the following algorithm:
dvander@52: //
dvander@52: //  (1) while the mark stack has overflowed:
dvander@52: //   (a) Search the heap for grey objects, adding as many as possible to the
dvander@52: //       mark stack.
dvander@52: //   (b) Run the mark-stack-emptying algorithm above.
dvander@52: //
dvander@52: // This algorithm is guaranteed to terminate, because even if there are more
dvander@52: // grey objects than mark stack capacity, we eventually all objects will
dvander@52: // become grey, and grey objects are not re-pushed onto the mark stack. Thus,
dvander@52: // eventually, all objects will become black.
dvander@52: //
dvander@59: namespace ke {
dvander@52: class MarkStack
dvander@52: {
dvander@52:     Object **base_;
dvander@52:     Object **top_;
dvander@52:     Object **end_;
dvander@52:     bool overflowed_;
dvander@52: 
dvander@52:   public:
dvander@52:     MarkStack(Object **base, Object **end)
dvander@52:       : base_(base),
dvander@52:         top_(base),
dvander@52:         end_(end),
dvander@52:         overflowed_(false)
dvander@52:     {
dvander@52:     }
dvander@52: 
dvander@52:     void pushBlack(Object *ptr) {
dvander@53:         assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(ptr)));
dvander@52:         if (top_ >= end_) {
dvander@52:             MarkBit bit = HeapChunk::GetMarkBit(ptr);
dvander@52:             HeapChunk::BlackToGrey(bit);
dvander@52:             overflowed_ = true;
dvander@52:             return;
dvander@52:         }
dvander@52:         *top_++ = ptr;
dvander@52:     }
dvander@52: 
dvander@52:     Object *pop() {
dvander@52:         assert(!empty());
dvander@52:         return *--top_;
dvander@52:     }
dvander@52:     bool overflowed() const {
dvander@52:         return overflowed_;
dvander@52:     }
dvander@52:     bool empty() const {
dvander@52:         return base_ == top_;
dvander@52:     }
dvander@53:     void reset() {
dvander@53:         assert(empty());
dvander@53:         overflowed_ = true;
dvander@53:     }
dvander@52: };
dvander@59: } // namespace ke
dvander@52: 
dvander@52: // Iterates over an object's body, pushing its referenced objects onto the
dvander@52: // mark stack.
dvander@52: class MarkingVisitor : public ObjectVisitor<VirtualObjectVisitor>
dvander@52: {
dvander@52:     MarkStack &stack_;
dvander@52: 
dvander@52:   public:
dvander@52:     MarkingVisitor(MarkStack &stack)
dvander@52:       : stack_(stack)
dvander@52:     {
dvander@52:     }
dvander@52: 
dvander@52:     void visit(Object **ptr) {
dvander@52:         if (!*ptr)
dvander@52:             return;
dvander@52: 
dvander@52:         Object *obj = *ptr;
dvander@52: 
dvander@52:         // If the object is grey, we'll find it later when searching the heap.
dvander@52:         // If the object is black, it's already been scsanned.
dvander@52:         MarkBit bit = HeapChunk::GetMarkBit(obj);
dvander@52:         if (HeapChunk::IsBlackOrGrey(bit))
dvander@52:             return;
dvander@52: 
dvander@52:         // Place the object in the stack and optimistically mark it black. If
dvander@52:         // the stack overflows, it'll become grey instead.
dvander@52:         HeapChunk::WhiteToBlack(bit);
dvander@52:         stack_.pushBlack(obj);
dvander@52:     }
dvander@52: };
dvander@52: 
dvander@52: static void
dvander@52: ProcessMarkStack(MarkStack &stack)
dvander@52: {
dvander@52:     MarkingVisitor visitor(stack);
dvander@52: 
dvander@52:     while (!stack.empty()) {
dvander@52:         Object *obj = stack.pop();
dvander@52:         assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(obj)));
dvander@52: 
dvander@52:         visitor.iterate(obj);
dvander@52:     }
dvander@52: }
dvander@52: 
dvander@52: class RootMarkingVisitor : public VirtualObjectVisitor
dvander@52: {
dvander@52:     MarkStack &stack_;
dvander@52:     MarkingVisitor visitor_;
dvander@52: 
dvander@52:   public:
dvander@52:     RootMarkingVisitor(MarkStack &stack)
dvander@52:       : stack_(stack),
dvander@52:         visitor_(stack)
dvander@52:     {
dvander@52:     }
dvander@52: 
dvander@52:     void visit(Object **ptr) {
dvander@52:         // Flush the stack after every new root. Note that the root gets pushed
dvander@52:         // as black; that's okay. If the mark stack overflows, its children are
dvander@52:         // guaranteed to be at least grey.
dvander@52:         visitor_.visit(ptr);
dvander@52:         ProcessMarkStack(stack_);
dvander@52:     }
dvander@52: };
dvander@52: 
dvander@53: typedef ChunkObjectIteratorBase<ObjectSizeEvaluator> ChunkObjectIterator;
dvander@53: 
dvander@53: static inline bool
dvander@53: EnqueueGreyObject(MarkStack &stack, Object *obj)
dvander@53: {
dvander@53:     assert(!stack.overflowed());
dvander@53:     MarkBit bit = HeapChunk::GetMarkBit(obj);
dvander@53:     if (HeapChunk::IsGrey(bit)) {
dvander@53:         HeapChunk::GreyToBlack(bit);
dvander@53:         stack.pushBlack(obj);
dvander@53:         return !stack.overflowed();
dvander@53:     }
dvander@53:     return true;
dvander@53: }
dvander@53: 
dvander@52: static void
dvander@53: EnqueueGreyObjectsInChunks(MarkStack &stack, ChunkObjectIterator iter)
dvander@52: {
dvander@53:     for (Object *obj = iter.next(); obj; obj = iter.next()) {
dvander@53:         if (!EnqueueGreyObject(stack, obj))
dvander@53:             return;
dvander@53:     }
dvander@53: }
dvander@53: 
dvander@53: static void
dvander@53: EnqueueGreyObjectsInLargeChunks(MarkStack &stack, HeapChunk *first)
dvander@53: {
dvander@53:     for (HeapChunk *chunk = first; chunk; chunk = chunk->next()) {
dvander@53:         Object *obj = reinterpret_cast<Object *>(chunk->first());
dvander@53:         if (!EnqueueGreyObject(stack, obj))
dvander@53:             return;
dvander@53:     }
dvander@52: }
dvander@52: 
dvander@52: void
dvander@52: Heap::findGreyObjects(MarkStack &stack)
dvander@52: {
dvander@53:     EnqueueGreyObjectsInChunks(stack, lifoSpace_.begin(ObjectSizeEvaluator()));
dvander@53:     if (stack.overflowed())
dvander@53:         return;
dvander@53: 
dvander@53:     EnqueueGreyObjectsInChunks(stack, mapSpace_.begin(ObjectSizeEvaluator()));
dvander@53:     if (stack.overflowed())
dvander@53:         return;
dvander@53:     
dvander@53:     EnqueueGreyObjectsInChunks(stack, oldSpace_.begin(ObjectSizeEvaluator()));
dvander@53:     if (stack.overflowed())
dvander@53:         return;
dvander@53: 
dvander@53:     EnqueueGreyObjectsInLargeChunks(stack, largeSpace_.first());
dvander@53:     if (stack.overflowed())
dvander@53:         return;
dvander@52: }
dvander@52: 
dvander@49: void
dvander@51: Heap::mark()
dvander@49: {
dvander@52:     Object **qbase = reinterpret_cast<Object **>(markStack_);
dvander@52:     Object **qend = qbase + (kMarkStackSize / sizeof(Object *));
dvander@52:     MarkStack stack(qbase, qend);
dvander@52:     RootMarkingVisitor visitor(stack);
dvander@52: 
dvander@52:     // Attempt to mark all objects reachable from the root set.
dvander@52:     zone_->accept(&visitor);
dvander@52:     assert(stack.empty());
dvander@52: 
dvander@52:     // If the stack overflowed, we need to look through the entire heap for
dvander@53:     // grey objects to rescan. We keep doing this until there are no grey
dvander@53:     // objects left.
dvander@53:     while (stack.overflowed()) {
dvander@53:         stack.reset();
dvander@53:         findGreyObjects(stack);
dvander@53:         ProcessMarkStack(stack);
dvander@53:     }
dvander@53: }
dvander@53: 
dvander@53: // Use the mark bits to scan for live objects, and mark the regions in
dvander@53: // between them as free.
dvander@53: static void
dvander@53: SweepOldSpaceChunk(OldSpace *space, HeapChunk *chunk)
dvander@53: {
dvander@53:     uint32 *markbits = chunk->markBits();
dvander@53:     uint32 *markbitsEnd = markbits + HeapChunk::kMarkWords;
dvander@53:     Address freeStart = chunk->first();
dvander@53: 
dvander@53:     // Scoot up to the first usable markword. Since memory is reserved for
dvander@53:     // mark bits, not all addresses are allocatable, so quite a few of the
dvander@53:     // initial mark bits are wasted. (1KB of mark bytes on x86.)
dvander@53:     markbits = HeapChunk::GetMarkBit(reinterpret_cast<Object *>(chunk->first())).word();
dvander@53: 
dvander@53:     uint32 bits = *markbits;
dvander@53:     for (;;) {
dvander@53:         while (bits) {
dvander@53:             uint32 bit = FindRightmostBit(bits);
dvander@53:             Address object = HeapChunk::FromMarkBit(chunk, markbits, bit);
dvander@72: 
dvander@72:             assert(object >= freeStart);
dvander@53:             if (freeStart != object)
dvander@53:                 space->markRegionFree(freeStart, object - freeStart);
dvander@72: 
dvander@53:             Object *obj = reinterpret_cast<Object *>(object);
dvander@53:             freeStart = object + SizeOfObject(obj, obj->map());
dvander@53: 
dvander@72:             // Since black is 10, we never need to clear the next bit.
dvander@53:             bits &= ~(1 << bit);
dvander@53:         }
dvander@53:         markbits++;
dvander@53:         bits = *markbits;
dvander@53:         if (markbits >= markbitsEnd)
dvander@53:             break;
dvander@53:     }
dvander@53: 
dvander@53:     if (freeStart == chunk->base())
dvander@53:         chunk->setEmpty();
dvander@53:     else if (freeStart != chunk->end())
dvander@53:         space->markRegionFree(freeStart, chunk->end() - freeStart);
dvander@53: }
dvander@53: 
dvander@53: static void
dvander@53: SweepOldSpace(OldSpace *space)
dvander@53: {
dvander@53:     space->resetFreeList();
dvander@53:     for (HeapChunk *chunk = space->first(); chunk; chunk = chunk->next()) {
dvander@53:         SweepOldSpaceChunk(space, chunk);
dvander@53:         chunk->resetMarkBits();
dvander@53:     }
dvander@53:     space->freeUnusedPages();
dvander@53: }
dvander@53: 
dvander@53: void
dvander@53: Heap::sweep()
dvander@53: {
dvander@54:     // Before destroying mark bits, sweep weak roots.
dvander@54:     zone_->symbols()->sweep();
dvander@54: 
dvander@53:     // Note: we don't bother sweeping the LIFO space.
dvander@53:     SweepOldSpace(&mapSpace_);
dvander@53:     SweepOldSpace(&oldSpace_);
dvander@53:     largeSpace_.sweep();
dvander@49: }
dvander@49: 
dvander@51: void
dvander@51: Heap::reclaim()
dvander@51: {
dvander@53:     mark();
dvander@53:     sweep();
dvander@51: }
dvander@69: 
dvander@69: void
dvander@69: Heap::reportOutOfMemory()
dvander@69: {
dvander@69:     zone_->reportOutOfMemory();
dvander@69: }