Temporary checkin.
1.1 --- a/jitcraft/Heap-inl.h Fri Jul 06 19:24:22 2012 -0400
1.2 +++ b/jitcraft/Heap-inl.h Sat Jul 07 01:45:33 2012 -0400
1.3 @@ -71,6 +71,10 @@
1.4 Heap::allocate(Handle<Map> map, size_t bytes, Tenure age)
1.5 {
1.6 size_t actualBytes = Align(bytes, kObjectAlignment);
1.7 +
1.8 + // All objects must be at least two words.
1.9 + assert(actualBytes >= sizeof(Object *) * 2);
1.10 +
1.11 Address address = newObject(actualBytes, age);
1.12 if (!address) {
1.13 assert(false);
2.1 --- a/jitcraft/Heap.cpp Fri Jul 06 19:24:22 2012 -0400
2.2 +++ b/jitcraft/Heap.cpp Sat Jul 07 01:45:33 2012 -0400
2.3 @@ -19,11 +19,17 @@
2.4 #include "Heap.h"
2.5 #include "Heap-inl.h"
2.6 #include "Spaces-inl.h"
2.7 +#include "VirtualObjectVisitor.h"
2.8 +#include "ObjectVisitor.h"
2.9 +#include "Zone.h"
2.10
2.11 using namespace jc;
2.12
2.13 +static const size_t kMarkStackSize = 256 * kKB;
2.14 +
2.15 Heap::Heap(Zone *zone)
2.16 - : zone_(zone)
2.17 + : zone_(zone),
2.18 + markStack_(NULL)
2.19 {
2.20 }
2.21
2.22 @@ -39,6 +45,10 @@
2.23 if (!largeSpace_.initialize())
2.24 return false;
2.25
2.26 + markStack_ = malloc(kMarkStackSize);
2.27 + if (!markStack_)
2.28 + return false;
2.29 +
2.30 if ((metaMap_ = allocateMap(MapKind_Meta, sizeof(Map))) == NULL)
2.31 return false;
2.32 metaMap_->init(metaMap_);
2.33 @@ -46,6 +56,11 @@
2.34 return true;
2.35 }
2.36
2.37 +Heap::~Heap()
2.38 +{
2.39 + free(markStack_);
2.40 +}
2.41 +
2.42 Map *
2.43 Heap::allocateMap(MapKind kind, size_t bytes)
2.44 {
2.45 @@ -65,9 +80,162 @@
2.46 return map;
2.47 }
2.48
2.49 +// To avoid marking recursively, we use a worklist to manage the marking
2.50 +// process. Algorithm:
2.51 +//
2.52 +// (1) While the mark stack is not empty:
2.53 +// (a) Remove object |o| from the mark stack.
2.54 +// (b) For each reference |p| in object |o|,
2.55 +// (i) Mark |p| as Black.
2.56 +// (ii) Push |p| onto the mark stack.
2.57 +// (iv) If the mark stack overflowde, mark |p| as Grey.
2.58 +//
2.59 +// We run this algorithm after pushing every root object onto the mark stack.
2.60 +// After all roots have been processed, it may be that the mark stack
2.61 +// overflowed. In this case, we use the following algorithm:
2.62 +//
2.63 +// (1) while the mark stack has overflowed:
2.64 +// (a) Search the heap for grey objects, adding as many as possible to the
2.65 +// mark stack.
2.66 +// (b) Run the mark-stack-emptying algorithm above.
2.67 +//
2.68 +// This algorithm is guaranteed to terminate, because even if there are more
2.69 +// grey objects than mark stack capacity, we eventually all objects will
2.70 +// become grey, and grey objects are not re-pushed onto the mark stack. Thus,
2.71 +// eventually, all objects will become black.
2.72 +//
2.73 +namespace jc {
2.74 +class MarkStack
2.75 +{
2.76 + Object **base_;
2.77 + Object **top_;
2.78 + Object **end_;
2.79 + bool overflowed_;
2.80 +
2.81 + public:
2.82 + MarkStack(Object **base, Object **end)
2.83 + : base_(base),
2.84 + top_(base),
2.85 + end_(end),
2.86 + overflowed_(false)
2.87 + {
2.88 + }
2.89 +
2.90 + void pushBlack(Object *ptr) {
2.91 + if (top_ >= end_) {
2.92 + MarkBit bit = HeapChunk::GetMarkBit(ptr);
2.93 + HeapChunk::BlackToGrey(bit);
2.94 + overflowed_ = true;
2.95 + return;
2.96 + }
2.97 + *top_++ = ptr;
2.98 + }
2.99 +
2.100 + Object *pop() {
2.101 + assert(!empty());
2.102 + return *--top_;
2.103 + }
2.104 +
2.105 + bool overflowed() const {
2.106 + return overflowed_;
2.107 + }
2.108 +
2.109 + bool empty() const {
2.110 + return base_ == top_;
2.111 + }
2.112 +};
2.113 +} // namespace jc
2.114 +
2.115 +// Iterates over an object's body, pushing its referenced objects onto the
2.116 +// mark stack.
2.117 +class MarkingVisitor : public ObjectVisitor<VirtualObjectVisitor>
2.118 +{
2.119 + MarkStack &stack_;
2.120 +
2.121 + public:
2.122 + MarkingVisitor(MarkStack &stack)
2.123 + : stack_(stack)
2.124 + {
2.125 + }
2.126 +
2.127 + void visit(Object **ptr) {
2.128 + if (!*ptr)
2.129 + return;
2.130 +
2.131 + Object *obj = *ptr;
2.132 +
2.133 + // If the object is grey, we'll find it later when searching the heap.
2.134 + // If the object is black, it's already been scsanned.
2.135 + MarkBit bit = HeapChunk::GetMarkBit(obj);
2.136 + if (HeapChunk::IsBlackOrGrey(bit))
2.137 + return;
2.138 +
2.139 + // Place the object in the stack and optimistically mark it black. If
2.140 + // the stack overflows, it'll become grey instead.
2.141 + HeapChunk::WhiteToBlack(bit);
2.142 + stack_.pushBlack(obj);
2.143 + }
2.144 +};
2.145 +
2.146 +static void
2.147 +ProcessMarkStack(MarkStack &stack)
2.148 +{
2.149 + MarkingVisitor visitor(stack);
2.150 +
2.151 + while (!stack.empty()) {
2.152 + Object *obj = stack.pop();
2.153 + assert(HeapChunk::IsBlack(HeapChunk::GetMarkBit(obj)));
2.154 +
2.155 + visitor.iterate(obj);
2.156 + }
2.157 +}
2.158 +
2.159 +class RootMarkingVisitor : public VirtualObjectVisitor
2.160 +{
2.161 + MarkStack &stack_;
2.162 + MarkingVisitor visitor_;
2.163 +
2.164 + public:
2.165 + RootMarkingVisitor(MarkStack &stack)
2.166 + : stack_(stack),
2.167 + visitor_(stack)
2.168 + {
2.169 + }
2.170 +
2.171 + void visit(Object **ptr) {
2.172 + // Flush the stack after every new root. Note that the root gets pushed
2.173 + // as black; that's okay. If the mark stack overflows, its children are
2.174 + // guaranteed to be at least grey.
2.175 + visitor_.visit(ptr);
2.176 + ProcessMarkStack(stack_);
2.177 + }
2.178 +};
2.179 +
2.180 +static void
2.181 +EnqueueGreyObjectsInChunks(MarkStack &stack, HeapChunk *chunk)
2.182 +{
2.183 +}
2.184 +
2.185 +void
2.186 +Heap::findGreyObjects(MarkStack &stack)
2.187 +{
2.188 +}
2.189 +
2.190 void
2.191 Heap::mark()
2.192 {
2.193 + Object **qbase = reinterpret_cast<Object **>(markStack_);
2.194 + Object **qend = qbase + (kMarkStackSize / sizeof(Object *));
2.195 + MarkStack stack(qbase, qend);
2.196 + RootMarkingVisitor visitor(stack);
2.197 +
2.198 + // Attempt to mark all objects reachable from the root set.
2.199 + zone_->accept(&visitor);
2.200 + assert(stack.empty());
2.201 +
2.202 + // If the stack overflowed, we need to look through the entire heap for
2.203 + // grey objects to rescan.
2.204 + //
2.205 }
2.206
2.207 void
3.1 --- a/jitcraft/Heap.h Fri Jul 06 19:24:22 2012 -0400
3.2 +++ b/jitcraft/Heap.h Sat Jul 07 01:45:33 2012 -0400
3.3 @@ -28,6 +28,7 @@
3.4 namespace jc {
3.5
3.6 class Zone;
3.7 +class MarkStack;
3.8
3.9 // Heap-allocated objects go here. Heaps are thread-local. The heap contains
3.10 // four spaces:
3.11 @@ -39,10 +40,23 @@
3.12 // Large Space: Used for objects that are so large they should never be
3.13 // moved between spaces.
3.14 //
3.15 -// The garbage collector is both incremental and generational. Marking is
3.16 -// performed incrementally, interleaved with program execution. Minor
3.17 -// collections are also performed to mitigate the potential necessity of
3.18 -// major collections.
3.19 +// The following is a high-level overview of how garbage collection works in
3.20 +// Keima. Detailed notes are present in Heap.cpp.
3.21 +//
3.22 +// THE TRI-COLOR INVARIANT: Via an object's mark bits, we maintain the property
3.23 +// that an object that has been fully marked may never reference a dead object.
3.24 +// Objects exist in three states during collection: unmarked (white), scheduled
3.25 +// for marking (grey), and fully marked (black).
3.26 +//
3.27 +// When initiating collection, all objects are white. Objects in the root set
3.28 +// are made grey. The marking process takes grey objects and marks that each
3.29 +// child object is live: if the child is white, it becomes grey. Once all
3.30 +// children are grey or black, the parent grey object can become black, as it
3.31 +// has been fully traversed.
3.32 +//
3.33 +// The result of this process is that when there are no more grey objects,
3.34 +// then we are guaranteed that all black objects are live, and all white
3.35 +// objects are dead.
3.36 //
3.37 // MINOR COLLECTIONS (also called "scavenges") are usually performed when the
3.38 // new space reaches maximum capacity. During a minor collection, all live
3.39 @@ -93,6 +107,10 @@
3.40
3.41 Map *metaMap_;
3.42
3.43 + // This is a big hunk o' memory used for marking iteratively. Eventually,
3.44 + // this will be replaced by the inactive semispace in the nursery.
3.45 + void *markStack_;
3.46 +
3.47 public:
3.48 enum Tenure {
3.49 // Default, objects go into the nursery.
3.50 @@ -115,9 +133,11 @@
3.51 inline Address newObject(size_t bytes, Tenure pretenure);
3.52
3.53 void mark();
3.54 + void findGreyObjects(MarkStack &stack);
3.55
3.56 public:
3.57 Heap(Zone *zone);
3.58 + ~Heap();
3.59 bool initialize();
3.60
3.61 inline Object *allocate(Handle<Map> map, size_t byes, Tenure pretenure);
4.1 --- a/jitcraft/ObjectVisitor.h Fri Jul 06 19:24:22 2012 -0400
4.2 +++ b/jitcraft/ObjectVisitor.h Sat Jul 07 01:45:33 2012 -0400
4.3 @@ -79,9 +79,9 @@
4.4 }
4.5
4.6 size_t iterateFunction(Object *obj) {
4.7 - visitField(obj, Module::offsetOfModule());
4.8 - visitField(obj, Module::offsetOfCode());
4.9 - visitField(obj, Module::offsetOfType());
4.10 + visitField(obj, Function::offsetOfModule());
4.11 + visitField(obj, Function::offsetOfCode());
4.12 + visitField(obj, Function::offsetOfType());
4.13 return sizeof(Function);
4.14 }
4.15
4.16 @@ -96,12 +96,17 @@
4.17 }
4.18
4.19 size_t iterateArrayMap(ArrayMap *map) {
4.20 - visitField(obj, ArrayMap::offsetOfType());
4.21 - visitFIeld(obj, ArrayMap::offsetOfContained());
4.22 + visitField(map, ArrayMap::offsetOfType());
4.23 + visitField(map, ArrayMap::offsetOfContained());
4.24 return sizeof(ArrayMap);
4.25 }
4.26
4.27 public:
4.28 + size_t iterate(Object *obj) {
4.29 + visitField(obj, Object::offsetOfMap());
4.30 + return iterate(obj, obj->map());
4.31 + }
4.32 +
4.33 size_t iterate(Object *obj, Map *map) {
4.34 switch (map->kind()) {
4.35 case MapKind_Type:
4.36 @@ -129,11 +134,11 @@
4.37 return iterateArray(Array::cast(obj), ArrayMap::cast(map));
4.38
4.39 case MapKind_MetaArray:
4.40 - return iterateArrayMap(obj);
4.41 + return iterateArrayMap(ArrayMap::cast(obj));
4.42
4.43 default:
4.44 assert(map->kind() == MapKind_Meta);
4.45 - break;
4.46 + return sizeof(Map);
4.47 }
4.48 }
4.49 };
5.1 --- a/jitcraft/Objects.h Fri Jul 06 19:24:22 2012 -0400
5.2 +++ b/jitcraft/Objects.h Sat Jul 07 01:45:33 2012 -0400
5.3 @@ -1,4 +1,5 @@
5.4 -/*
5.5 +/* vim: set ts=4 sw=4 tw=99 et:
5.6 + *
5.7 * Copyright (C) 2012 David Anderson
5.8 *
5.9 * This file is part of JITCraft.
5.10 @@ -76,6 +77,11 @@
5.11 inline bool is(MapKind map);
5.12
5.13 inline void write(Zone *zone, Object **ptr, Object *value);
5.14 +
5.15 + static inline size_t offsetOfMap() {
5.16 + // Wtf? Clang won't accept offsetof(Object, map_) here...
5.17 + return 0;
5.18 + }
5.19 };
5.20
5.21 // Maps describe the layout of GCObjects. Every GCObject requires a map.
6.1 --- a/jitcraft/Spaces.h Fri Jul 06 19:24:22 2012 -0400
6.2 +++ b/jitcraft/Spaces.h Sat Jul 07 01:45:33 2012 -0400
6.3 @@ -27,7 +27,43 @@
6.4
6.5 class Object;
6.6
6.7 -static const size_t kObjectAlignment = 8;
6.8 +static const size_t kObjectAlignment = sizeof(Object *);
6.9 +
6.10 +// Every object gets two successive mark bits. These bits represent various
6.11 +// states during garbage collection:
6.12 +//
6.13 +// WHITE (00): The object is dead or unmarked.
6.14 +// GREY (11): The object is live but its children have not been marked.
6.15 +// BLACK (10): The object and all its children have been marked.
6.16 +//
6.17 +// These colors assist in maintaining the "tri-color invariant", explained
6.18 +// in Heap.h. The bits are organized such that transitioning an object from
6.19 +// White to Black requires one bit change, and Black to Grey requires another.
6.20 +class MarkBit
6.21 +{
6.22 + uint32 *word_;
6.23 + uint32 bit_;
6.24 +
6.25 + public:
6.26 + MarkBit(uint32 *word, uint32 bit)
6.27 + : word_(word),
6.28 + bit_(bit)
6.29 + {
6.30 + assert(bit_ < sizeof(*word_) * 8);
6.31 + }
6.32 +
6.33 + bool isSet() const {
6.34 + return !!(*word_ & (1 << bit_));
6.35 + }
6.36 + void set() {
6.37 + *word_ |= (1 << bit_);
6.38 + }
6.39 + MarkBit next() const {
6.40 + if (bit_ == (sizeof(*word_) * 8) - 1)
6.41 + return MarkBit(word_ + 1, 0);
6.42 + return MarkBit(word_, bit_ + 1);
6.43 + }
6.44 +};
6.45
6.46 class HeapChunk
6.47 {
6.48 @@ -41,6 +77,11 @@
6.49
6.50 uintptr_t flags_;
6.51
6.52 + private:
6.53 + uint32 *markBits() {
6.54 + return reinterpret_cast<uint32 *>(reinterpret_cast<Address>(this) + kMarkBitsOffset);
6.55 + }
6.56 +
6.57 public:
6.58 enum Flag {
6.59 HAS_OVERFLOWED_OBJECT = (1 << 0)
6.60 @@ -68,28 +109,38 @@
6.61 sizeof(Address);
6.62
6.63 // All objects must be allocated in the first kAlignment bytes of the
6.64 - // chunk. Every object is at least 8 bytes (kPointerAlignment), so we
6.65 - // reserve one mark bit for every possible object address in the chunk
6.66 - // (including, for simplicity, unallocatable addresses at the start).
6.67 + // chunk. We need two mark bits for every allocatable object, since there
6.68 + // are three possible states: White (00), Black (11), and Grey (10). These
6.69 + // bits are stored immediately after the HeapChunk header, and before the
6.70 + // first allocatable object.
6.71 + //
6.72 + // Although object alignment is only at word boundaries, we guarantee that
6.73 + // every object is at least two words. This means we don't need to reserve
6.74 + // two mark bits for every object, just one mark bit for every allocatable
6.75 + // address. That also means a pair of mark bits can cross a byte boundary.
6.76 + //
6.77 + // --- Math ---
6.78 //
6.79 // The number of mark bits needed is:
6.80 //
6.81 - // MaxObjectsPerChunk = kAlignment / kPointerAlignment
6.82 - // = 32KB
6.83 + // MaxObjectsPerChunk = (kAlignment / kObjectAlignment)
6.84 + // -> 256KB (128KB on 64-bit)
6.85 //
6.86 // The number of bytes needed for these mark bits is:
6.87 //
6.88 // NumMarkBytes = MaxObjectsPerChunk / 8
6.89 - // = 4KB
6.90 + // = 32KB (16KB on 64-bit)
6.91 //
6.92 // The number of uint32s needed to store these bytes is:
6.93 //
6.94 // NumMarkWords = NumMarkBytes / sizeof(uint32)
6.95 - // = 1024
6.96 + // = 8KB (4KB on 64-bit)
6.97 + //
6.98 static const size_t kMaxObjectsPerChunk = kAlignment / kObjectAlignment;
6.99 static const size_t kMarkBits = kMaxObjectsPerChunk;
6.100 static const size_t kMarkBytes = kMarkBits / 8;
6.101 static const size_t kMarkWords = kMarkBytes / sizeof(uint32);
6.102 + static const size_t kMarkBitsPerWord = sizeof(uint32) * 8;
6.103
6.104 static const size_t kMarkBitsOffset = kHeaderSize;
6.105 static const size_t kFirstObject = kMarkBitsOffset + kMarkBytes;
6.106 @@ -123,8 +174,41 @@
6.107 Address first() {
6.108 return reinterpret_cast<Address>(this) + kFirstObject;
6.109 }
6.110 - uint32 *markBits() {
6.111 - return reinterpret_cast<uint32 *>(reinterpret_cast<Address>(this) + kMarkBitsOffset);
6.112 +
6.113 + // Marking functions.
6.114 + static inline MarkBit GetMarkBit(Object *obj) {
6.115 + uintptr_t address = reinterpret_cast<uintptr_t>(obj);
6.116 +
6.117 + HeapChunk *chunk = reinterpret_cast<HeapChunk *>(address & ~(kAlignment - 1));
6.118 + assert(Address(obj) >= chunk->first() && Address(obj) < chunk->end());
6.119 +
6.120 + size_t index = (address & (kAlignment - 1)) / kObjectAlignment;
6.121 + assert(index < kMaxObjectsPerChunk);
6.122 +
6.123 + uint32 *word = chunk->markBits() + (index / kMarkBitsPerWord);
6.124 + uint32 bit = index & (kMarkBitsPerWord - 1);
6.125 + return MarkBit(word, bit);
6.126 + }
6.127 + static inline bool IsWhite(const MarkBit &bit) {
6.128 + assert(bit.isSet() || !bit.next().isSet());
6.129 + return !bit.isSet();
6.130 + }
6.131 + static inline bool IsBlack(const MarkBit &bit) {
6.132 + return bit.isSet() && !bit.next().isSet();
6.133 + }
6.134 + static inline bool IsGrey(const MarkBit &bit) {
6.135 + return bit.isSet() && bit.next().isSet();
6.136 + }
6.137 + static inline bool IsBlackOrGrey(const MarkBit &bit) {
6.138 + return bit.isSet();
6.139 + }
6.140 + static inline void WhiteToBlack(MarkBit &bit) {
6.141 + assert(IsWhite(bit));
6.142 + bit.set();
6.143 + }
6.144 + static inline void BlackToGrey(MarkBit &bit) {
6.145 + assert(IsGrey(bit));
6.146 + bit.next().set();
6.147 }
6.148
6.149 bool hasOverflowedObject() {
6.150 @@ -135,6 +219,12 @@
6.151 }
6.152 };
6.153
6.154 +class ChunkObjectIterator
6.155 +{
6.156 + HeapChunk *start_;
6.157 + Address top_;
6.158 +};
6.159 +
6.160 // The heap stack is designed for structures which are known to not escape the
6.161 // program stack, and can thus be quickly allocated in a LIFO manner.
6.162 //
6.163 @@ -165,7 +255,6 @@
6.164 }
6.165 };
6.166
6.167 -
6.168 class OldSpace
6.169 {
6.170 HeapChunk *first_;
7.1 --- a/jitcraft/VirtualObjectVisitor.h Fri Jul 06 19:24:22 2012 -0400
7.2 +++ b/jitcraft/VirtualObjectVisitor.h Sat Jul 07 01:45:33 2012 -0400
7.3 @@ -16,8 +16,8 @@
7.4 * You should have received a copy of the GNU General Public License along with
7.5 * JITCraft. If not, see http://www.gnu.org/licenses/.
7.6 */
7.7 -#ifndef _include_jc_object_visitor_h_
7.8 -#define _include_jc_object_visitor_h_
7.9 +#ifndef _include_jc_virtual_object_visitor_h_
7.10 +#define _include_jc_virtual_object_visitor_h_
7.11
7.12 namespace jc {
7.13
7.14 @@ -31,4 +31,4 @@
7.15
7.16 }
7.17
7.18 -#endif // _include_jc_object_visitor_h_
7.19 +#endif // _include_jc_virtual_object_visitor_h_
