1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/Heap.h Tue Jul 24 23:53:34 2012 -0700
1.3 @@ -0,0 +1,143 @@
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 +#ifndef _include_jitcraft_heap_h_
1.23 +#define _include_jitcraft_heap_h_
1.24 +
1.25 +#include "Utility.h"
1.26 +#include "Spaces.h"
1.27 +#include "Barriers.h"
1.28 +#include "Objects.h"
1.29 +#include "Handles.h"
1.30 +
1.31 +namespace ke {
1.32 +
1.33 +class Zone;
1.34 +class MarkStack;
1.35 +
1.36 +// Heap-allocated objects go here. Heaps are thread-local. The heap contains
1.37 +// four spaces:
1.38 +//
1.39 +// LIFO Space: Used for objects that may be stack-allocated.
1.40 +// Old Space: Used for objects that are expected to be long-lived, or that
1.41 +// survive one collection.
1.42 +// Large Space: Used for objects that are so large they should never be
1.43 +// moved between spaces.
1.44 +//
1.45 +// ALLOCATING AN OBJECT DOES NOT ZERO ITS MEMORY.
1.46 +// ALLOCATING AN OBJECT DOES NOT ZERO ITS MEMORY!
1.47 +//
1.48 +// ---------------------------------------------------------------------------
1.49 +//
1.50 +// The following is a high-level overview of how garbage collection works in
1.51 +// Keima. Detailed notes are present in Heap.cpp.
1.52 +//
1.53 +// THE TRI-COLOR INVARIANT: Via an object's mark bits, we maintain the
1.54 +// property that an object that has been fully marked may never reference a
1.55 +// dead object. Objects exist in three states during collection: unmarked
1.56 +// (white), scheduled for marking (grey), and fully marked (black).
1.57 +//
1.58 +// When initiating collection, all objects are white. Objects in the root
1.59 +// set are made grey. The marking process takes grey objects and marks that
1.60 +// each child object is live: if the child is white, it becomes grey. Once
1.61 +// all children are grey or black, the parent grey object can become black,
1.62 +// as it has been fully traversed.
1.63 +//
1.64 +// The result of this process is that when there are no more grey objects,
1.65 +// then we are guaranteed that all black objects are live, and all white
1.66 +// objects are dead.
1.67 +//
1.68 +// MAJOR COLLECTIONS are performed periodically, when either a given memory
1.69 +// threshold has been reached, or when requested by the host application.
1.70 +// They are also performed if no memory can be allocated.
1.71 +//
1.72 +// Major collections are extremely slow; they require full heap traversal,
1.73 +// which can take more than a second on very large heaps. However, they
1.74 +// have the greatest chance at reclaiming all syntactically dead objects.
1.75 +//
1.76 +// SWEEPING is performed after major collections. The free space in between
1.77 +// live objects is added to a free list. Tenured allocations are then
1.78 +// performed in the free space, if possible.
1.79 +//
1.80 +class Heap
1.81 +{
1.82 + Zone *zone_;
1.83 + HeapStack lifoSpace_;
1.84 + OldSpace mapSpace_;
1.85 + OldSpace oldSpace_;
1.86 + LargeObjectSpace largeSpace_;
1.87 +
1.88 + Map *metaMap_;
1.89 +
1.90 + // This is a big hunk o' memory used for marking iteratively. Eventually,
1.91 + // this will be replaced by the inactive semispace in the nursery.
1.92 + void *markStack_;
1.93 +
1.94 + public:
1.95 + enum Tenure {
1.96 + // Default, objects go into the nursery.
1.97 + Tenure_Default,
1.98 +
1.99 + // If objects are proven to not escape the stack, they can go into
1.100 + // a LIFO arena. Allocation on the LIFO arena is not guaranteed to
1.101 + // succeed; thus, objects may still be allocated in other arenas.
1.102 + Tenure_Stack,
1.103 +
1.104 + // Objects that should not go into the nursery (i.e. are expected
1.105 + // to be long-living) go here.
1.106 + Tenure_Old
1.107 + };
1.108 +
1.109 + private:
1.110 + inline Address newLargeObject(size_t bytes);
1.111 + inline Address newOldObject(size_t bytes);
1.112 + inline Address newStackObject(size_t bytes);
1.113 + inline Address newObject(size_t bytes, Tenure pretenure);
1.114 +
1.115 + private:
1.116 + void findGreyObjects(MarkStack &stack);
1.117 + void mark();
1.118 + void sweep();
1.119 +
1.120 + void reportOutOfMemory();
1.121 +
1.122 + public:
1.123 + Heap(Zone *zone);
1.124 + ~Heap();
1.125 + bool initialize();
1.126 +
1.127 + inline Object *allocate(Handle<Map> map, size_t byes, Tenure pretenure);
1.128 + Map *allocateMap(MapKind kind, size_t bytes);
1.129 +
1.130 + Map *metaMap() {
1.131 + return metaMap_;
1.132 + }
1.133 + inline Address lifoPosition() const {
1.134 + return lifoSpace_.position();
1.135 + }
1.136 + inline void unwindLifo(Address to) {
1.137 + lifoSpace_.unwind(to);
1.138 + }
1.139 +
1.140 + // Perform a full garbage collection.
1.141 + void reclaim();
1.142 +};
1.143 +
1.144 +}
1.145 +
1.146 +#endif //_include_jitcraft_heap_h_
