1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/Heap.cpp Tue Jul 24 23:53:34 2012 -0700
1.3 @@ -0,0 +1,372 @@
1.4 +/* vim: set ts=4 sw=4 tw=99 et:
1.5 + *
1.6 + * Copyright (C) 2012 David Anderson
1.7 + *
1.8 + * This file is part of JITCraft.
1.9 + *
1.10 + * JITCraft is free software: you can redistribute it and/or modify it under
1.11 + * the terms of the GNU General Public License as published by the Free
1.12 + * Software Foundation, either version 3 of the License, or (at your option)
1.13 + * any later version.
1.14 + *
1.15 + * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
1.16 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License along with
1.20 + * JITCraft. If not, see http://www.gnu.org/licenses/.
1.21 + */
1.22 +#include "Heap.h"
1.23 +#include "Heap-inl.h"
1.24 +#include "Spaces-inl.h"
1.25 +#include "VirtualObjectVisitor.h"
1.26 +#include "ObjectVisitor.h"
1.27 +#include "Zone.h"
1.28 +#include "StringPool.h"
1.29 +
1.30 +using namespace ke;
1.31 +
1.32 +static const size_t kMarkStackSize = 256 * kKB;
1.33 +
1.34 +Heap::Heap(Zone *zone)
1.35 + : zone_(zone),
1.36 + markStack_(NULL),
1.37 + oldSpace_(zone),
1.38 + mapSpace_(zone)
1.39 +{
1.40 +}
1.41 +
1.42 +bool
1.43 +Heap::initialize()
1.44 +{
1.45 + if (!lifoSpace_.initialize())
1.46 + return false;
1.47 + if (!oldSpace_.initialize())
1.48 + return false;
1.49 + if (!mapSpace_.initialize())
1.50 + return false;
1.51 + if (!largeSpace_.initialize())
1.52 + return false;
1.53 +
1.54 + markStack_ = malloc(kMarkStackSize);
1.55 + if (!markStack_)
1.56 + return false;
1.57 +
1.58 + if ((metaMap_ = allocateMap(MapKind_Meta, sizeof(Map))) == NULL)
1.59 + return false;
1.60 + metaMap_->init(metaMap_);
1.61 +
1.62 + return true;
1.63 +}
1.64 +
1.65 +Heap::~Heap()
1.66 +{
1.67 + free(markStack_);
1.68 +}
1.69 +
1.70 +Map *
1.71 +Heap::allocateMap(MapKind kind, size_t bytes)
1.72 +{
1.73 + size_t actualBytes = Align(bytes, kObjectAlignment);
1.74 +
1.75 + Address addr = mapSpace_.allocate(actualBytes);
1.76 + if (!addr) {
1.77 + reportOutOfMemory();
1.78 + return NULL;
1.79 + }
1.80 +
1.81 + // Note that we use a NULL type initially, and reinterpret-cast to get
1.82 + // the Type pointer, so we can allocate the self-referencing meta type.
1.83 + Object *obj = InitAddressIntoObject(addr, NULL);
1.84 + Map *map = reinterpret_cast<Map *>(obj);
1.85 + map->setKind(kind);
1.86 + return map;
1.87 +}
1.88 +
1.89 +// To avoid marking recursively, we use a worklist to manage the marking
1.90 +// process. Algorithm:
1.91 +//
1.92 +// (1) While the mark stack is not empty:
1.93 +// (a) Remove object |o| from the mark stack.
1.94 +// (b) For each reference |p| in object |o|,
1.95 +// (i) Mark |p| as Black.
1.96 +// (ii) Push |p| onto the mark stack.
1.97 +// (iv) If the mark stack overflowde, mark |p| as Grey.
1.98 +//
1.99 +// We run this algorithm after pushing every root object onto the mark stack.
1.100 +// After all roots have been processed, it may be that the mark stack
1.101 +// overflowed. In this case, we use the following algorithm:
1.102 +//
1.103 +// (1) while the mark stack has overflowed:
1.104 +// (a) Search the heap for grey objects, adding as many as possible to the
1.105 +// mark stack.
1.106 +// (b) Run the mark-stack-emptying algorithm above.
1.107 +//
1.108 +// This algorithm is guaranteed to terminate, because even if there are more
1.109 +// grey objects than mark stack capacity, we eventually all objects will
1.110 +// become grey, and grey objects are not re-pushed onto the mark stack. Thus,
1.111 +// eventually, all objects will become black.
1.112 +//
1.113 +namespace ke {
1.114 +class MarkStack
1.115 +{
1.116 + Object **base_;
1.117 + Object **top_;
1.118 + Object **end_;
1.119 + bool overflowed_;
1.120 +
1.121 + public:
1.122 + MarkStack(Object **base, Object **end)
1.123 + : base_(base),
1.124 + top_(base),
1.125 + end_(end),
1.126 + overflowed_(false)
1.127 + {
1.128 + }
1.129 +
1.130 + void pushBlack(Object *ptr) {
1.131 + assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(ptr)));
1.132 + if (top_ >= end_) {
1.133 + MarkBit bit = HeapChunk::GetMarkBit(ptr);
1.134 + HeapChunk::BlackToGrey(bit);
1.135 + overflowed_ = true;
1.136 + return;
1.137 + }
1.138 + *top_++ = ptr;
1.139 + }
1.140 +
1.141 + Object *pop() {
1.142 + assert(!empty());
1.143 + return *--top_;
1.144 + }
1.145 + bool overflowed() const {
1.146 + return overflowed_;
1.147 + }
1.148 + bool empty() const {
1.149 + return base_ == top_;
1.150 + }
1.151 + void reset() {
1.152 + assert(empty());
1.153 + overflowed_ = true;
1.154 + }
1.155 +};
1.156 +} // namespace ke
1.157 +
1.158 +// Iterates over an object's body, pushing its referenced objects onto the
1.159 +// mark stack.
1.160 +class MarkingVisitor : public ObjectVisitor<VirtualObjectVisitor>
1.161 +{
1.162 + MarkStack &stack_;
1.163 +
1.164 + public:
1.165 + MarkingVisitor(MarkStack &stack)
1.166 + : stack_(stack)
1.167 + {
1.168 + }
1.169 +
1.170 + void visit(Object **ptr) {
1.171 + if (!*ptr)
1.172 + return;
1.173 +
1.174 + Object *obj = *ptr;
1.175 +
1.176 + // If the object is grey, we'll find it later when searching the heap.
1.177 + // If the object is black, it's already been scsanned.
1.178 + MarkBit bit = HeapChunk::GetMarkBit(obj);
1.179 + if (HeapChunk::IsBlackOrGrey(bit))
1.180 + return;
1.181 +
1.182 + // Place the object in the stack and optimistically mark it black. If
1.183 + // the stack overflows, it'll become grey instead.
1.184 + HeapChunk::WhiteToBlack(bit);
1.185 + stack_.pushBlack(obj);
1.186 + }
1.187 +};
1.188 +
1.189 +static void
1.190 +ProcessMarkStack(MarkStack &stack)
1.191 +{
1.192 + MarkingVisitor visitor(stack);
1.193 +
1.194 + while (!stack.empty()) {
1.195 + Object *obj = stack.pop();
1.196 + assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(obj)));
1.197 +
1.198 + visitor.iterate(obj);
1.199 + }
1.200 +}
1.201 +
1.202 +class RootMarkingVisitor : public VirtualObjectVisitor
1.203 +{
1.204 + MarkStack &stack_;
1.205 + MarkingVisitor visitor_;
1.206 +
1.207 + public:
1.208 + RootMarkingVisitor(MarkStack &stack)
1.209 + : stack_(stack),
1.210 + visitor_(stack)
1.211 + {
1.212 + }
1.213 +
1.214 + void visit(Object **ptr) {
1.215 + // Flush the stack after every new root. Note that the root gets pushed
1.216 + // as black; that's okay. If the mark stack overflows, its children are
1.217 + // guaranteed to be at least grey.
1.218 + visitor_.visit(ptr);
1.219 + ProcessMarkStack(stack_);
1.220 + }
1.221 +};
1.222 +
1.223 +typedef ChunkObjectIteratorBase<ObjectSizeEvaluator> ChunkObjectIterator;
1.224 +
1.225 +static inline bool
1.226 +EnqueueGreyObject(MarkStack &stack, Object *obj)
1.227 +{
1.228 + assert(!stack.overflowed());
1.229 + MarkBit bit = HeapChunk::GetMarkBit(obj);
1.230 + if (HeapChunk::IsGrey(bit)) {
1.231 + HeapChunk::GreyToBlack(bit);
1.232 + stack.pushBlack(obj);
1.233 + return !stack.overflowed();
1.234 + }
1.235 + return true;
1.236 +}
1.237 +
1.238 +static void
1.239 +EnqueueGreyObjectsInChunks(MarkStack &stack, ChunkObjectIterator iter)
1.240 +{
1.241 + for (Object *obj = iter.next(); obj; obj = iter.next()) {
1.242 + if (!EnqueueGreyObject(stack, obj))
1.243 + return;
1.244 + }
1.245 +}
1.246 +
1.247 +static void
1.248 +EnqueueGreyObjectsInLargeChunks(MarkStack &stack, HeapChunk *first)
1.249 +{
1.250 + for (HeapChunk *chunk = first; chunk; chunk = chunk->next()) {
1.251 + Object *obj = reinterpret_cast<Object *>(chunk->first());
1.252 + if (!EnqueueGreyObject(stack, obj))
1.253 + return;
1.254 + }
1.255 +}
1.256 +
1.257 +void
1.258 +Heap::findGreyObjects(MarkStack &stack)
1.259 +{
1.260 + EnqueueGreyObjectsInChunks(stack, lifoSpace_.begin(ObjectSizeEvaluator()));
1.261 + if (stack.overflowed())
1.262 + return;
1.263 +
1.264 + EnqueueGreyObjectsInChunks(stack, mapSpace_.begin(ObjectSizeEvaluator()));
1.265 + if (stack.overflowed())
1.266 + return;
1.267 +
1.268 + EnqueueGreyObjectsInChunks(stack, oldSpace_.begin(ObjectSizeEvaluator()));
1.269 + if (stack.overflowed())
1.270 + return;
1.271 +
1.272 + EnqueueGreyObjectsInLargeChunks(stack, largeSpace_.first());
1.273 + if (stack.overflowed())
1.274 + return;
1.275 +}
1.276 +
1.277 +void
1.278 +Heap::mark()
1.279 +{
1.280 + Object **qbase = reinterpret_cast<Object **>(markStack_);
1.281 + Object **qend = qbase + (kMarkStackSize / sizeof(Object *));
1.282 + MarkStack stack(qbase, qend);
1.283 + RootMarkingVisitor visitor(stack);
1.284 +
1.285 + // Attempt to mark all objects reachable from the root set.
1.286 + zone_->accept(&visitor);
1.287 + assert(stack.empty());
1.288 +
1.289 + // If the stack overflowed, we need to look through the entire heap for
1.290 + // grey objects to rescan. We keep doing this until there are no grey
1.291 + // objects left.
1.292 + while (stack.overflowed()) {
1.293 + stack.reset();
1.294 + findGreyObjects(stack);
1.295 + ProcessMarkStack(stack);
1.296 + }
1.297 +}
1.298 +
1.299 +// Use the mark bits to scan for live objects, and mark the regions in
1.300 +// between them as free.
1.301 +static void
1.302 +SweepOldSpaceChunk(OldSpace *space, HeapChunk *chunk)
1.303 +{
1.304 + uint32 *markbits = chunk->markBits();
1.305 + uint32 *markbitsEnd = markbits + HeapChunk::kMarkWords;
1.306 + Address freeStart = chunk->first();
1.307 +
1.308 + // Scoot up to the first usable markword. Since memory is reserved for
1.309 + // mark bits, not all addresses are allocatable, so quite a few of the
1.310 + // initial mark bits are wasted. (1KB of mark bytes on x86.)
1.311 + markbits = HeapChunk::GetMarkBit(reinterpret_cast<Object *>(chunk->first())).word();
1.312 +
1.313 + uint32 bits = *markbits;
1.314 + for (;;) {
1.315 + while (bits) {
1.316 + uint32 bit = FindRightmostBit(bits);
1.317 + Address object = HeapChunk::FromMarkBit(chunk, markbits, bit);
1.318 +
1.319 + assert(object >= freeStart);
1.320 + if (freeStart != object)
1.321 + space->markRegionFree(freeStart, object - freeStart);
1.322 +
1.323 + Object *obj = reinterpret_cast<Object *>(object);
1.324 + freeStart = object + SizeOfObject(obj, obj->map());
1.325 +
1.326 + // Since black is 10, we never need to clear the next bit.
1.327 + bits &= ~(1 << bit);
1.328 + }
1.329 + markbits++;
1.330 + bits = *markbits;
1.331 + if (markbits >= markbitsEnd)
1.332 + break;
1.333 + }
1.334 +
1.335 + if (freeStart == chunk->base())
1.336 + chunk->setEmpty();
1.337 + else if (freeStart != chunk->end())
1.338 + space->markRegionFree(freeStart, chunk->end() - freeStart);
1.339 +}
1.340 +
1.341 +static void
1.342 +SweepOldSpace(OldSpace *space)
1.343 +{
1.344 + space->resetFreeList();
1.345 + for (HeapChunk *chunk = space->first(); chunk; chunk = chunk->next()) {
1.346 + SweepOldSpaceChunk(space, chunk);
1.347 + chunk->resetMarkBits();
1.348 + }
1.349 + space->freeUnusedPages();
1.350 +}
1.351 +
1.352 +void
1.353 +Heap::sweep()
1.354 +{
1.355 + // Before destroying mark bits, sweep weak roots.
1.356 + zone_->symbols()->sweep();
1.357 +
1.358 + // Note: we don't bother sweeping the LIFO space.
1.359 + SweepOldSpace(&mapSpace_);
1.360 + SweepOldSpace(&oldSpace_);
1.361 + largeSpace_.sweep();
1.362 +}
1.363 +
1.364 +void
1.365 +Heap::reclaim()
1.366 +{
1.367 + mark();
1.368 + sweep();
1.369 +}
1.370 +
1.371 +void
1.372 +Heap::reportOutOfMemory()
1.373 +{
1.374 + zone_->reportOutOfMemory();
1.375 +}
