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