diff -r 22b67b4cf067 -r 13bd3a8df334 jitcraft/Heap.cpp
--- a/jitcraft/Heap.cpp	Sat Jul 07 01:45:33 2012 -0400
+++ b/jitcraft/Heap.cpp	Sat Jul 07 17:11:31 2012 -0700
@@ -29,7 +29,9 @@
 
 Heap::Heap(Zone *zone)
   : zone_(zone),
-    markStack_(NULL)
+    markStack_(NULL),
+    oldSpace_(zone),
+    mapSpace_(zone)
 {
 }
 
@@ -122,6 +124,7 @@
     }
 
     void pushBlack(Object *ptr) {
+        assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(ptr)));
         if (top_ >= end_) {
             MarkBit bit = HeapChunk::GetMarkBit(ptr);
             HeapChunk::BlackToGrey(bit);
@@ -135,14 +138,16 @@
         assert(!empty());
         return *--top_;
     }
-
     bool overflowed() const {
         return overflowed_;
     }
-
     bool empty() const {
         return base_ == top_;
     }
+    void reset() {
+        assert(empty());
+        overflowed_ = true;
+    }
 };
 } // namespace jc
 
@@ -211,14 +216,58 @@
     }
 };
 
+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, HeapChunk *chunk)
+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
@@ -234,13 +283,83 @@
     assert(stack.empty());
 
     // If the stack overflowed, we need to look through the entire heap for
-    // grey objects to rescan.
-    //
+    // 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);
+            if (freeStart != object)
+                space->markRegionFree(freeStart, object - freeStart);
+            Object *obj = reinterpret_cast<Object *>(object);
+            freeStart = object + SizeOfObject(obj, obj->map());
+
+            bits &= ~(1 << bit);
+            if (bits == HeapChunk::kMarkBitsPerWord - 1) {
+                // This bit is the last bit on this word, so bump up to the
+                // next word and exclude the first bit.
+                markbits++;
+                assert(markbits < markbitsEnd);
+                bits = *markbits & ~(1 << 0);
+            }
+        }
+        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()
+{
+    // Note: we don't bother sweeping the LIFO space.
+    SweepOldSpace(&mapSpace_);
+    SweepOldSpace(&oldSpace_);
+    largeSpace_.sweep();
 }
 
 void
 Heap::reclaim()
 {
-    // Full memory reclamation.
+    mark();
+    sweep();
 }
-