OILS / mycpp / mark_sweep_heap.h View on Github | oils.pub

349 lines, 215 significant
1#ifndef MARKSWEEP_HEAP_H
2#define MARKSWEEP_HEAP_H
3
4#include <stdlib.h>
5
6#include <vector>
7
8#include "mycpp/common.h"
9#include "mycpp/gc_obj.h"
10
11#if GC_ALWAYS
12 #define VALIDATE_ROOTS 1
13#else
14 #define VALIDATE_ROOTS 0 // flip this manually to diagnose bugs
15#endif
16
17#if VALIDATE_ROOTS
18static void ValidateRoot(const RawObject* obj) {
19 if (obj == nullptr) {
20 return;
21 }
22
23 // Assuming 64-bit == 8 byte alignment
24 if (reinterpret_cast<uintptr_t>(obj) & 0x3) {
25 log("Misaligned object %p", obj);
26 FAIL(kShouldNotGetHere);
27 return;
28 }
29
30 ObjHeader* header = ObjHeader::FromObject(obj);
31 // log("obj %p header %p", obj, header);
32
33 if (reinterpret_cast<uintptr_t>(header) & 0x3) {
34 log("Misaligned header %p", header);
35 FAIL(kShouldNotGetHere);
36 return;
37 }
38
39 switch (header->heap_tag) {
40 case HeapTag::Global:
41 case HeapTag::Opaque:
42 case HeapTag::Scanned:
43 case HeapTag::FixedSize:
44 break;
45
46 default:
47 log("root %p heap %d type %d mask %d len %d", obj, header->heap_tag,
48 header->type_tag, header->u_mask_npointers);
49 FAIL(kShouldNotGetHere);
50 break;
51 }
52}
53#endif
54
55class MarkSet {
56 public:
57 MarkSet() : bits_() {
58 }
59
60 // ReInit() must be called at the start of MarkObjects(). Allocate() should
61 // keep track of the maximum object ID.
62 void ReInit(int max_obj_id) {
63 // https://stackoverflow.com/questions/8848575/fastest-way-to-reset-every-value-of-stdvectorint-to-0
64 std::fill(bits_.begin(), bits_.end(), 0);
65 int max_byte_index = (max_obj_id >> 3) + 1; // round up
66 // log("ReInit max_byte_index %d", max_byte_index);
67 bits_.resize(max_byte_index);
68 }
69
70 // Called by MarkObjects()
71 void Mark(int obj_id) {
72 DCHECK(obj_id >= 0);
73 // log("obj id %d", obj_id);
74 DCHECK(!IsMarked(obj_id));
75 int byte_index = obj_id >> 3; // 8 bits per byte
76 int bit_index = obj_id & 0b111;
77 // log("byte_index %d %d", byte_index, bit_index);
78 bits_[byte_index] |= (1 << bit_index);
79 }
80
81 // Called by Sweep()
82 bool IsMarked(int obj_id) {
83 DCHECK(obj_id >= 0);
84 int byte_index = obj_id >> 3;
85 int bit_index = obj_id & 0b111;
86 return bits_[byte_index] & (1 << bit_index);
87 }
88
89 void Debug() {
90 int n = bits_.size();
91 dprintf(2, "[ ");
92 for (int i = 0; i < n; ++i) {
93 dprintf(2, "%02x ", bits_[i]);
94 }
95 dprintf(2, "] (%d bytes) \n", n);
96 dprintf(2, "[ ");
97 int num_bits = 0;
98 for (int i = 0; i < n; ++i) {
99 for (int j = 0; j < 8; ++j) {
100 int bit = (bits_[i] & (1 << j)) != 0;
101 dprintf(2, "%d", bit);
102 num_bits += bit;
103 }
104 }
105 dprintf(2, " ] (%d bits set)\n", num_bits);
106 }
107
108 std::vector<uint8_t> bits_; // bit vector indexed by obj_id
109};
110
111// A simple Pool allocator for allocating small objects. It maintains an ever
112// growing number of Blocks each consisting of a number of fixed size Cells.
113// Memory is handed out one Cell at a time.
114// Note: within the context of the Pool allocator we refer to object IDs as cell
115// IDs because in addition to identifying an object they're also used to index
116// into the Cell storage.
117template <int CellsPerBlock, size_t CellSize>
118class Pool {
119 public:
120 static constexpr size_t kMaxObjSize = CellSize;
121 static constexpr int kBlockSize = CellSize * CellsPerBlock;
122
123 Pool() = default;
124
125 void* Allocate(int* obj_id) {
126 num_allocated_++;
127
128 if (!free_list_) {
129 // Allocate a new Block and add every new Cell to the free list.
130 Block* block = static_cast<Block*>(malloc(sizeof(Block)));
131 blocks_.push_back(block);
132 bytes_allocated_ += kBlockSize;
133 num_free_ += CellsPerBlock;
134
135 // The starting cell_id for Cells in this block.
136 int cell_id = (blocks_.size() - 1) * CellsPerBlock;
137 for (Cell& cell : block->cells) {
138 FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell);
139 free_cell->id = cell_id++;
140 free_cell->next = free_list_;
141 free_list_ = free_cell;
142 }
143 }
144
145 FreeCell* cell = free_list_;
146 free_list_ = free_list_->next;
147 num_free_--;
148 *obj_id = cell->id;
149 return cell;
150 }
151
152 void PrepareForGc() {
153 DCHECK(!gc_underway_);
154 gc_underway_ = true;
155 mark_set_.ReInit(blocks_.size() * CellsPerBlock);
156 }
157
158 bool IsMarked(int cell_id) {
159 DCHECK(gc_underway_);
160 return mark_set_.IsMarked(cell_id);
161 }
162
163 void Mark(int cell_id) {
164 DCHECK(gc_underway_);
165 mark_set_.Mark(cell_id);
166 }
167
168 void Sweep() {
169 DCHECK(gc_underway_);
170 // Iterate over every Cell linking the free ones into a new free list.
171 num_free_ = 0;
172 free_list_ = nullptr;
173 int cell_id = 0;
174 for (Block* block : blocks_) {
175 for (Cell& cell : block->cells) {
176 if (!mark_set_.IsMarked(cell_id)) {
177 num_free_++;
178 FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell);
179 free_cell->id = cell_id;
180 free_cell->next = free_list_;
181 free_list_ = free_cell;
182 }
183 cell_id++;
184 }
185 }
186 gc_underway_ = false;
187 }
188
189 void Free() {
190 for (Block* block : blocks_) {
191 free(block);
192 }
193 blocks_.clear();
194 num_free_ = 0;
195 }
196
197 int num_allocated() {
198 return num_allocated_;
199 }
200
201 int64_t bytes_allocated() {
202 return bytes_allocated_;
203 }
204
205 int num_live() {
206#ifndef OPTIMIZED
207 int capacity = blocks_.size() * CellsPerBlock;
208 // log("Pool capacity = %d", capacity);
209 // log("Pool num_free_ = %d", num_free_);
210 DCHECK(num_free_ <= capacity);
211#endif
212 return blocks_.size() * CellsPerBlock - num_free_;
213 }
214
215 private:
216 using Cell = uint8_t[CellSize];
217
218 struct Block {
219 Cell cells[CellsPerBlock];
220 };
221
222 // Unused/free cells are tracked via a linked list of FreeCells. The FreeCells
223 // are stored in the unused Cells, so it takes no extra memory to track them.
224 struct FreeCell {
225 int id;
226 FreeCell* next;
227 };
228 static_assert(CellSize >= sizeof(FreeCell), "CellSize is too small");
229
230 // Whether a GC is underway, for asserting that calls are in order.
231 bool gc_underway_ = false;
232
233 FreeCell* free_list_ = nullptr;
234 int num_free_ = 0;
235 int num_allocated_ = 0;
236 int64_t bytes_allocated_ = 0;
237 std::vector<Block*> blocks_;
238 MarkSet mark_set_;
239
240 DISALLOW_COPY_AND_ASSIGN(Pool);
241};
242
243class MarkSweepHeap {
244 public:
245 // reserve 32 frames to start
246 MarkSweepHeap() {
247 }
248
249 void Init(); // use default threshold
250 void Init(int gc_threshold);
251
252 void PushRoot(RawObject** p) {
253#if VALIDATE_ROOTS
254 ValidateRoot(*p);
255#endif
256 roots_.push_back(p);
257 }
258
259 void PopRoot() {
260 roots_.pop_back();
261 }
262
263 void RootGlobalVar(void* root) {
264 global_roots_.push_back(reinterpret_cast<RawObject*>(root));
265 }
266
267 void* Allocate(size_t num_bytes, int* obj_id, int* pool_id);
268
269#if 0
270 void* Reallocate(void* p, size_t num_bytes);
271#endif
272 int MaybeCollect();
273 int Collect();
274
275 void MaybeMarkAndPush(RawObject* obj);
276 void TraceChildren();
277
278 void Sweep();
279
280 void PrintStats(int fd); // public for testing
281 void PrintShortStats();
282
283 void CleanProcessExit(); // do one last GC, used in unit tests
284 void ProcessExit(); // main() lets OS clean up, except ASAN variant
285
286 int num_live() {
287 return num_live_
288#ifndef NO_POOL_ALLOC
289 + pool1_.num_live() + pool2_.num_live()
290#endif
291 ;
292 }
293
294 bool is_initialized_ = true; // mark/sweep doesn't need to be initialized
295
296 // Runtime params
297
298 // Threshold is a number of live objects, since we aren't keeping track of
299 // total bytes
300 int gc_threshold_;
301
302 // Show debug logging
303 bool gc_verbose_ = false;
304
305 // Current stats
306 int num_live_ = 0;
307 // Should we keep track of sizes?
308 // int64_t bytes_live_ = 0;
309
310 // Cumulative stats
311 int max_survived_ = 0; // max # live after a collection
312 int num_allocated_ = 0;
313 int64_t bytes_allocated_ = 0; // avoid overflow
314 int num_gc_points_ = 0; // manual collection points
315 int num_collections_ = 0;
316 int num_growths_;
317 double max_gc_millis_ = 0.0;
318 double total_gc_millis_ = 0.0;
319
320#ifndef NO_POOL_ALLOC
321 // 16,384 / 24 bytes = 682 cells (rounded), 16,368 bytes
322 // 16,384 / 48 bytes = 341 cells (rounded), 16,368 bytes
323 // Conveniently, the glibc malloc header is 16 bytes, giving exactly 16 Ki
324 // differences
325 Pool<682, 24> pool1_;
326 Pool<341, 48> pool2_;
327#endif
328
329 std::vector<RawObject**> roots_;
330 std::vector<RawObject*> global_roots_;
331
332 // Allocate() appends live objects, and Sweep() compacts it
333 std::vector<ObjHeader*> live_objs_;
334 // Allocate lazily frees these, and Sweep() replenishes it
335 std::vector<ObjHeader*> to_free_;
336
337 std::vector<ObjHeader*> gray_stack_;
338 MarkSet mark_set_;
339
340 int greatest_obj_id_ = 0;
341
342 private:
343 void FreeEverything();
344 void MaybePrintStats();
345
346 DISALLOW_COPY_AND_ASSIGN(MarkSweepHeap);
347};
348
349#endif // MARKSWEEP_HEAP_H