1.1 --- a/jitcraft/Heap.cpp Sat Jul 07 01:45:33 2012 -0400
1.2 +++ b/jitcraft/Heap.cpp Sat Jul 07 17:11:31 2012 -0700
1.3 @@ -29,7 +29,9 @@
1.4
1.5 Heap::Heap(Zone *zone)
1.6 : zone_(zone),
1.7 - markStack_(NULL)
1.8 + markStack_(NULL),
1.9 + oldSpace_(zone),
1.10 + mapSpace_(zone)
1.11 {
1.12 }
1.13
1.14 @@ -122,6 +124,7 @@
1.15 }
1.16
1.17 void pushBlack(Object *ptr) {
1.18 + assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(ptr)));
1.19 if (top_ >= end_) {
1.20 MarkBit bit = HeapChunk::GetMarkBit(ptr);
1.21 HeapChunk::BlackToGrey(bit);
1.22 @@ -135,14 +138,16 @@
1.23 assert(!empty());
1.24 return *--top_;
1.25 }
1.26 -
1.27 bool overflowed() const {
1.28 return overflowed_;
1.29 }
1.30 -
1.31 bool empty() const {
1.32 return base_ == top_;
1.33 }
1.34 + void reset() {
1.35 + assert(empty());
1.36 + overflowed_ = true;
1.37 + }
1.38 };
1.39 } // namespace jc
1.40
1.41 @@ -211,14 +216,58 @@
1.42 }
1.43 };
1.44
1.45 +typedef ChunkObjectIteratorBase<ObjectSizeEvaluator> ChunkObjectIterator;
1.46 +
1.47 +static inline bool
1.48 +EnqueueGreyObject(MarkStack &stack, Object *obj)
1.49 +{
1.50 + assert(!stack.overflowed());
1.51 + MarkBit bit = HeapChunk::GetMarkBit(obj);
1.52 + if (HeapChunk::IsGrey(bit)) {
1.53 + HeapChunk::GreyToBlack(bit);
1.54 + stack.pushBlack(obj);
1.55 + return !stack.overflowed();
1.56 + }
1.57 + return true;
1.58 +}
1.59 +
1.60 static void
1.61 -EnqueueGreyObjectsInChunks(MarkStack &stack, HeapChunk *chunk)
1.62 +EnqueueGreyObjectsInChunks(MarkStack &stack, ChunkObjectIterator iter)
1.63 {
1.64 + for (Object *obj = iter.next(); obj; obj = iter.next()) {
1.65 + if (!EnqueueGreyObject(stack, obj))
1.66 + return;
1.67 + }
1.68 +}
1.69 +
1.70 +static void
1.71 +EnqueueGreyObjectsInLargeChunks(MarkStack &stack, HeapChunk *first)
1.72 +{
1.73 + for (HeapChunk *chunk = first; chunk; chunk = chunk->next()) {
1.74 + Object *obj = reinterpret_cast<Object *>(chunk->first());
1.75 + if (!EnqueueGreyObject(stack, obj))
1.76 + return;
1.77 + }
1.78 }
1.79
1.80 void
1.81 Heap::findGreyObjects(MarkStack &stack)
1.82 {
1.83 + EnqueueGreyObjectsInChunks(stack, lifoSpace_.begin(ObjectSizeEvaluator()));
1.84 + if (stack.overflowed())
1.85 + return;
1.86 +
1.87 + EnqueueGreyObjectsInChunks(stack, mapSpace_.begin(ObjectSizeEvaluator()));
1.88 + if (stack.overflowed())
1.89 + return;
1.90 +
1.91 + EnqueueGreyObjectsInChunks(stack, oldSpace_.begin(ObjectSizeEvaluator()));
1.92 + if (stack.overflowed())
1.93 + return;
1.94 +
1.95 + EnqueueGreyObjectsInLargeChunks(stack, largeSpace_.first());
1.96 + if (stack.overflowed())
1.97 + return;
1.98 }
1.99
1.100 void
1.101 @@ -234,13 +283,83 @@
1.102 assert(stack.empty());
1.103
1.104 // If the stack overflowed, we need to look through the entire heap for
1.105 - // grey objects to rescan.
1.106 - //
1.107 + // grey objects to rescan. We keep doing this until there are no grey
1.108 + // objects left.
1.109 + while (stack.overflowed()) {
1.110 + stack.reset();
1.111 + findGreyObjects(stack);
1.112 + ProcessMarkStack(stack);
1.113 + }
1.114 +}
1.115 +
1.116 +// Use the mark bits to scan for live objects, and mark the regions in
1.117 +// between them as free.
1.118 +static void
1.119 +SweepOldSpaceChunk(OldSpace *space, HeapChunk *chunk)
1.120 +{
1.121 + uint32 *markbits = chunk->markBits();
1.122 + uint32 *markbitsEnd = markbits + HeapChunk::kMarkWords;
1.123 + Address freeStart = chunk->first();
1.124 +
1.125 + // Scoot up to the first usable markword. Since memory is reserved for
1.126 + // mark bits, not all addresses are allocatable, so quite a few of the
1.127 + // initial mark bits are wasted. (1KB of mark bytes on x86.)
1.128 + markbits = HeapChunk::GetMarkBit(reinterpret_cast<Object *>(chunk->first())).word();
1.129 +
1.130 + uint32 bits = *markbits;
1.131 + for (;;) {
1.132 + while (bits) {
1.133 + uint32 bit = FindRightmostBit(bits);
1.134 + Address object = HeapChunk::FromMarkBit(chunk, markbits, bit);
1.135 + if (freeStart != object)
1.136 + space->markRegionFree(freeStart, object - freeStart);
1.137 + Object *obj = reinterpret_cast<Object *>(object);
1.138 + freeStart = object + SizeOfObject(obj, obj->map());
1.139 +
1.140 + bits &= ~(1 << bit);
1.141 + if (bits == HeapChunk::kMarkBitsPerWord - 1) {
1.142 + // This bit is the last bit on this word, so bump up to the
1.143 + // next word and exclude the first bit.
1.144 + markbits++;
1.145 + assert(markbits < markbitsEnd);
1.146 + bits = *markbits & ~(1 << 0);
1.147 + }
1.148 + }
1.149 + markbits++;
1.150 + bits = *markbits;
1.151 + if (markbits >= markbitsEnd)
1.152 + break;
1.153 + }
1.154 +
1.155 + if (freeStart == chunk->base())
1.156 + chunk->setEmpty();
1.157 + else if (freeStart != chunk->end())
1.158 + space->markRegionFree(freeStart, chunk->end() - freeStart);
1.159 +}
1.160 +
1.161 +static void
1.162 +SweepOldSpace(OldSpace *space)
1.163 +{
1.164 + space->resetFreeList();
1.165 + for (HeapChunk *chunk = space->first(); chunk; chunk = chunk->next()) {
1.166 + SweepOldSpaceChunk(space, chunk);
1.167 + chunk->resetMarkBits();
1.168 + }
1.169 + space->freeUnusedPages();
1.170 +}
1.171 +
1.172 +void
1.173 +Heap::sweep()
1.174 +{
1.175 + // Note: we don't bother sweeping the LIFO space.
1.176 + SweepOldSpace(&mapSpace_);
1.177 + SweepOldSpace(&oldSpace_);
1.178 + largeSpace_.sweep();
1.179 }
1.180
1.181 void
1.182 Heap::reclaim()
1.183 {
1.184 - // Full memory reclamation.
1.185 + mark();
1.186 + sweep();
1.187 }
1.188 -
