/home/andy/git/oilshell/oil/mycpp/mark_sweep_heap.h
Line | Count | Source (jump to first uncovered line) |
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 | | class MarkSet { |
12 | | public: |
13 | 185 | MarkSet() : bits_() { |
14 | 185 | } |
15 | | |
16 | | // ReInit() must be called at the start of MarkObjects(). Allocate() should |
17 | | // keep track of the maximum object ID. |
18 | 343 | void ReInit(int max_obj_id) { |
19 | | // https://stackoverflow.com/questions/8848575/fastest-way-to-reset-every-value-of-stdvectorint-to-0 |
20 | 343 | std::fill(bits_.begin(), bits_.end(), 0); |
21 | 343 | int max_byte_index = (max_obj_id >> 3) + 1; // round up |
22 | | // log("ReInit max_byte_index %d", max_byte_index); |
23 | 343 | bits_.resize(max_byte_index); |
24 | 343 | } |
25 | | |
26 | | // Called by MarkObjects() |
27 | 118 | void Mark(int obj_id) { |
28 | 118 | DCHECK(obj_id >= 0); |
29 | | // log("obj id %d", obj_id); |
30 | 118 | DCHECK(!IsMarked(obj_id)); |
31 | 0 | int byte_index = obj_id >> 3; // 8 bits per byte |
32 | 118 | int bit_index = obj_id & 0b111; |
33 | | // log("byte_index %d %d", byte_index, bit_index); |
34 | 118 | bits_[byte_index] |= (1 << bit_index); |
35 | 118 | } |
36 | | |
37 | | // Called by Sweep() |
38 | 111k | bool IsMarked(int obj_id) { |
39 | 111k | DCHECK(obj_id >= 0); |
40 | 0 | int byte_index = obj_id >> 3; |
41 | 111k | int bit_index = obj_id & 0b111; |
42 | 111k | return bits_[byte_index] & (1 << bit_index); |
43 | 111k | } |
44 | | |
45 | 2 | void Debug() { |
46 | 2 | int n = bits_.size(); |
47 | 2 | dprintf(2, "[ "); |
48 | 8 | for (int i = 0; i < n; ++i) { |
49 | 6 | dprintf(2, "%02x ", bits_[i]); |
50 | 6 | } |
51 | 2 | dprintf(2, "] (%d bytes) \n", n); |
52 | 2 | dprintf(2, "[ "); |
53 | 2 | int num_bits = 0; |
54 | 8 | for (int i = 0; i < n; ++i) { |
55 | 54 | for (int j = 0; j < 8; ++j) { |
56 | 48 | int bit = (bits_[i] & (1 << j)) != 0; |
57 | 48 | dprintf(2, "%d", bit); |
58 | 48 | num_bits += bit; |
59 | 48 | } |
60 | 6 | } |
61 | 2 | dprintf(2, " ] (%d bits set)\n", num_bits); |
62 | 2 | } |
63 | | |
64 | | std::vector<uint8_t> bits_; // bit vector indexed by obj_id |
65 | | }; |
66 | | |
67 | | // A simple Pool allocator for allocating small objects. It maintains an ever |
68 | | // growing number of Blocks each consisting of a number of fixed size Cells. |
69 | | // Memory is handed out one Cell at a time. |
70 | | // Note: within the context of the Pool allocator we refer to object IDs as cell |
71 | | // IDs because in addition to identifying an object they're also used to index |
72 | | // into the Cell storage. |
73 | | template <int CellsPerBlock, size_t CellSize> |
74 | | class Pool { |
75 | | public: |
76 | | static constexpr size_t kMaxObjSize = CellSize; |
77 | | static constexpr int kBlockSize = CellSize * CellsPerBlock; |
78 | | |
79 | 124 | Pool() = default; _ZN4PoolILi682ELm24EEC2Ev Line | Count | Source | 79 | 59 | Pool() = default; |
_ZN4PoolILi341ELm48EEC2Ev Line | Count | Source | 79 | 59 | Pool() = default; |
Line | Count | Source | 79 | 4 | Pool() = default; |
Line | Count | Source | 79 | 2 | Pool() = default; |
|
80 | | |
81 | 7.75k | void* Allocate(int* obj_id) { |
82 | 7.75k | num_allocated_++; |
83 | | |
84 | 7.75k | if (!free_list_) { |
85 | | // Allocate a new Block and add every new Cell to the free list. |
86 | 119 | Block* block = static_cast<Block*>(malloc(sizeof(Block))); |
87 | 119 | blocks_.push_back(block); |
88 | 119 | bytes_allocated_ += kBlockSize; |
89 | 119 | num_free_ += CellsPerBlock; |
90 | | |
91 | | // The starting cell_id for Cells in this block. |
92 | 119 | int cell_id = (blocks_.size() - 1) * CellsPerBlock; |
93 | 55.5k | for (Cell& cell : block->cells) { |
94 | 55.5k | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); |
95 | 55.5k | free_cell->id = cell_id++; |
96 | 55.5k | free_cell->next = free_list_; |
97 | 55.5k | free_list_ = free_cell; |
98 | 55.5k | } |
99 | 119 | } |
100 | | |
101 | 7.75k | FreeCell* cell = free_list_; |
102 | 7.75k | free_list_ = free_list_->next; |
103 | 7.75k | num_free_--; |
104 | 7.75k | *obj_id = cell->id; |
105 | 7.75k | return cell; |
106 | 7.75k | } _ZN4PoolILi682ELm24EE8AllocateEPi Line | Count | Source | 81 | 5.27k | void* Allocate(int* obj_id) { | 82 | 5.27k | num_allocated_++; | 83 | | | 84 | 5.27k | if (!free_list_) { | 85 | | // Allocate a new Block and add every new Cell to the free list. | 86 | 54 | Block* block = static_cast<Block*>(malloc(sizeof(Block))); | 87 | 54 | blocks_.push_back(block); | 88 | 54 | bytes_allocated_ += kBlockSize; | 89 | 54 | num_free_ += CellsPerBlock; | 90 | | | 91 | | // The starting cell_id for Cells in this block. | 92 | 54 | int cell_id = (blocks_.size() - 1) * CellsPerBlock; | 93 | 36.8k | for (Cell& cell : block->cells) { | 94 | 36.8k | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 95 | 36.8k | free_cell->id = cell_id++; | 96 | 36.8k | free_cell->next = free_list_; | 97 | 36.8k | free_list_ = free_cell; | 98 | 36.8k | } | 99 | 54 | } | 100 | | | 101 | 5.27k | FreeCell* cell = free_list_; | 102 | 5.27k | free_list_ = free_list_->next; | 103 | 5.27k | num_free_--; | 104 | 5.27k | *obj_id = cell->id; | 105 | 5.27k | return cell; | 106 | 5.27k | } |
_ZN4PoolILi341ELm48EE8AllocateEPi Line | Count | Source | 81 | 2.46k | void* Allocate(int* obj_id) { | 82 | 2.46k | num_allocated_++; | 83 | | | 84 | 2.46k | if (!free_list_) { | 85 | | // Allocate a new Block and add every new Cell to the free list. | 86 | 55 | Block* block = static_cast<Block*>(malloc(sizeof(Block))); | 87 | 55 | blocks_.push_back(block); | 88 | 55 | bytes_allocated_ += kBlockSize; | 89 | 55 | num_free_ += CellsPerBlock; | 90 | | | 91 | | // The starting cell_id for Cells in this block. | 92 | 55 | int cell_id = (blocks_.size() - 1) * CellsPerBlock; | 93 | 18.7k | for (Cell& cell : block->cells) { | 94 | 18.7k | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 95 | 18.7k | free_cell->id = cell_id++; | 96 | 18.7k | free_cell->next = free_list_; | 97 | 18.7k | free_list_ = free_cell; | 98 | 18.7k | } | 99 | 55 | } | 100 | | | 101 | 2.46k | FreeCell* cell = free_list_; | 102 | 2.46k | free_list_ = free_list_->next; | 103 | 2.46k | num_free_--; | 104 | 2.46k | *obj_id = cell->id; | 105 | 2.46k | return cell; | 106 | 2.46k | } |
_ZN4PoolILi2ELm32EE8AllocateEPi Line | Count | Source | 81 | 14 | void* Allocate(int* obj_id) { | 82 | 14 | num_allocated_++; | 83 | | | 84 | 14 | if (!free_list_) { | 85 | | // Allocate a new Block and add every new Cell to the free list. | 86 | 6 | Block* block = static_cast<Block*>(malloc(sizeof(Block))); | 87 | 6 | blocks_.push_back(block); | 88 | 6 | bytes_allocated_ += kBlockSize; | 89 | 6 | num_free_ += CellsPerBlock; | 90 | | | 91 | | // The starting cell_id for Cells in this block. | 92 | 6 | int cell_id = (blocks_.size() - 1) * CellsPerBlock; | 93 | 12 | for (Cell& cell : block->cells) { | 94 | 12 | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 95 | 12 | free_cell->id = cell_id++; | 96 | 12 | free_cell->next = free_list_; | 97 | 12 | free_list_ = free_cell; | 98 | 12 | } | 99 | 6 | } | 100 | | | 101 | 14 | FreeCell* cell = free_list_; | 102 | 14 | free_list_ = free_list_->next; | 103 | 14 | num_free_--; | 104 | 14 | *obj_id = cell->id; | 105 | 14 | return cell; | 106 | 14 | } |
_ZN4PoolILi1ELm32EE8AllocateEPi Line | Count | Source | 81 | 4 | void* Allocate(int* obj_id) { | 82 | 4 | num_allocated_++; | 83 | | | 84 | 4 | if (!free_list_) { | 85 | | // Allocate a new Block and add every new Cell to the free list. | 86 | 4 | Block* block = static_cast<Block*>(malloc(sizeof(Block))); | 87 | 4 | blocks_.push_back(block); | 88 | 4 | bytes_allocated_ += kBlockSize; | 89 | 4 | num_free_ += CellsPerBlock; | 90 | | | 91 | | // The starting cell_id for Cells in this block. | 92 | 4 | int cell_id = (blocks_.size() - 1) * CellsPerBlock; | 93 | 4 | for (Cell& cell : block->cells) { | 94 | 4 | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 95 | 4 | free_cell->id = cell_id++; | 96 | 4 | free_cell->next = free_list_; | 97 | 4 | free_list_ = free_cell; | 98 | 4 | } | 99 | 4 | } | 100 | | | 101 | 4 | FreeCell* cell = free_list_; | 102 | 4 | free_list_ = free_list_->next; | 103 | 4 | num_free_--; | 104 | 4 | *obj_id = cell->id; | 105 | 4 | return cell; | 106 | 4 | } |
|
107 | | |
108 | 228 | void PrepareForGc() { |
109 | 228 | DCHECK(!gc_underway_); |
110 | 0 | gc_underway_ = true; |
111 | 228 | mark_set_.ReInit(blocks_.size() * CellsPerBlock); |
112 | 228 | } _ZN4PoolILi682ELm24EE12PrepareForGcEv Line | Count | Source | 108 | 111 | void PrepareForGc() { | 109 | 111 | DCHECK(!gc_underway_); | 110 | 0 | gc_underway_ = true; | 111 | 111 | mark_set_.ReInit(blocks_.size() * CellsPerBlock); | 112 | 111 | } |
_ZN4PoolILi341ELm48EE12PrepareForGcEv Line | Count | Source | 108 | 111 | void PrepareForGc() { | 109 | 111 | DCHECK(!gc_underway_); | 110 | 0 | gc_underway_ = true; | 111 | 111 | mark_set_.ReInit(blocks_.size() * CellsPerBlock); | 112 | 111 | } |
_ZN4PoolILi2ELm32EE12PrepareForGcEv Line | Count | Source | 108 | 4 | void PrepareForGc() { | 109 | 4 | DCHECK(!gc_underway_); | 110 | 0 | gc_underway_ = true; | 111 | 4 | mark_set_.ReInit(blocks_.size() * CellsPerBlock); | 112 | 4 | } |
_ZN4PoolILi1ELm32EE12PrepareForGcEv Line | Count | Source | 108 | 2 | void PrepareForGc() { | 109 | 2 | DCHECK(!gc_underway_); | 110 | 0 | gc_underway_ = true; | 111 | 2 | mark_set_.ReInit(blocks_.size() * CellsPerBlock); | 112 | 2 | } |
|
113 | | |
114 | 122 | bool IsMarked(int cell_id) { |
115 | 122 | DCHECK(gc_underway_); |
116 | 0 | return mark_set_.IsMarked(cell_id); |
117 | 122 | } _ZN4PoolILi682ELm24EE8IsMarkedEi Line | Count | Source | 114 | 112 | bool IsMarked(int cell_id) { | 115 | 112 | DCHECK(gc_underway_); | 116 | 0 | return mark_set_.IsMarked(cell_id); | 117 | 112 | } |
_ZN4PoolILi341ELm48EE8IsMarkedEi Line | Count | Source | 114 | 10 | bool IsMarked(int cell_id) { | 115 | 10 | DCHECK(gc_underway_); | 116 | 0 | return mark_set_.IsMarked(cell_id); | 117 | 10 | } |
|
118 | | |
119 | 96 | void Mark(int cell_id) { |
120 | 96 | DCHECK(gc_underway_); |
121 | 0 | mark_set_.Mark(cell_id); |
122 | 96 | } _ZN4PoolILi682ELm24EE4MarkEi Line | Count | Source | 119 | 84 | void Mark(int cell_id) { | 120 | 84 | DCHECK(gc_underway_); | 121 | 0 | mark_set_.Mark(cell_id); | 122 | 84 | } |
_ZN4PoolILi341ELm48EE4MarkEi Line | Count | Source | 119 | 10 | void Mark(int cell_id) { | 120 | 10 | DCHECK(gc_underway_); | 121 | 0 | mark_set_.Mark(cell_id); | 122 | 10 | } |
_ZN4PoolILi1ELm32EE4MarkEi Line | Count | Source | 119 | 2 | void Mark(int cell_id) { | 120 | 2 | DCHECK(gc_underway_); | 121 | 0 | mark_set_.Mark(cell_id); | 122 | 2 | } |
|
123 | | |
124 | 228 | void Sweep() { |
125 | 228 | DCHECK(gc_underway_); |
126 | | // Iterate over every Cell linking the free ones into a new free list. |
127 | 0 | num_free_ = 0; |
128 | 228 | free_list_ = nullptr; |
129 | 228 | int cell_id = 0; |
130 | 228 | for (Block* block : blocks_) { |
131 | 110k | for (Cell& cell : block->cells) { |
132 | 110k | if (!mark_set_.IsMarked(cell_id)) { |
133 | 110k | num_free_++; |
134 | 110k | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); |
135 | 110k | free_cell->id = cell_id; |
136 | 110k | free_cell->next = free_list_; |
137 | 110k | free_list_ = free_cell; |
138 | 110k | } |
139 | 110k | cell_id++; |
140 | 110k | } |
141 | 221 | } |
142 | 228 | gc_underway_ = false; |
143 | 228 | } _ZN4PoolILi682ELm24EE5SweepEv Line | Count | Source | 124 | 111 | void Sweep() { | 125 | 111 | DCHECK(gc_underway_); | 126 | | // Iterate over every Cell linking the free ones into a new free list. | 127 | 0 | num_free_ = 0; | 128 | 111 | free_list_ = nullptr; | 129 | 111 | int cell_id = 0; | 130 | 111 | for (Block* block : blocks_) { | 131 | 73.6k | for (Cell& cell : block->cells) { | 132 | 73.6k | if (!mark_set_.IsMarked(cell_id)) { | 133 | 73.5k | num_free_++; | 134 | 73.5k | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 135 | 73.5k | free_cell->id = cell_id; | 136 | 73.5k | free_cell->next = free_list_; | 137 | 73.5k | free_list_ = free_cell; | 138 | 73.5k | } | 139 | 73.6k | cell_id++; | 140 | 73.6k | } | 141 | 108 | } | 142 | 111 | gc_underway_ = false; | 143 | 111 | } |
_ZN4PoolILi341ELm48EE5SweepEv Line | Count | Source | 124 | 111 | void Sweep() { | 125 | 111 | DCHECK(gc_underway_); | 126 | | // Iterate over every Cell linking the free ones into a new free list. | 127 | 0 | num_free_ = 0; | 128 | 111 | free_list_ = nullptr; | 129 | 111 | int cell_id = 0; | 130 | 111 | for (Block* block : blocks_) { | 131 | 36.4k | for (Cell& cell : block->cells) { | 132 | 36.4k | if (!mark_set_.IsMarked(cell_id)) { | 133 | 36.4k | num_free_++; | 134 | 36.4k | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 135 | 36.4k | free_cell->id = cell_id; | 136 | 36.4k | free_cell->next = free_list_; | 137 | 36.4k | free_list_ = free_cell; | 138 | 36.4k | } | 139 | 36.4k | cell_id++; | 140 | 36.4k | } | 141 | 107 | } | 142 | 111 | gc_underway_ = false; | 143 | 111 | } |
_ZN4PoolILi2ELm32EE5SweepEv Line | Count | Source | 124 | 4 | void Sweep() { | 125 | 4 | DCHECK(gc_underway_); | 126 | | // Iterate over every Cell linking the free ones into a new free list. | 127 | 0 | num_free_ = 0; | 128 | 4 | free_list_ = nullptr; | 129 | 4 | int cell_id = 0; | 130 | 4 | for (Block* block : blocks_) { | 131 | 4 | for (Cell& cell : block->cells) { | 132 | 4 | if (!mark_set_.IsMarked(cell_id)) { | 133 | 4 | num_free_++; | 134 | 4 | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 135 | 4 | free_cell->id = cell_id; | 136 | 4 | free_cell->next = free_list_; | 137 | 4 | free_list_ = free_cell; | 138 | 4 | } | 139 | 4 | cell_id++; | 140 | 4 | } | 141 | 2 | } | 142 | 4 | gc_underway_ = false; | 143 | 4 | } |
_ZN4PoolILi1ELm32EE5SweepEv Line | Count | Source | 124 | 2 | void Sweep() { | 125 | 2 | DCHECK(gc_underway_); | 126 | | // Iterate over every Cell linking the free ones into a new free list. | 127 | 0 | num_free_ = 0; | 128 | 2 | free_list_ = nullptr; | 129 | 2 | int cell_id = 0; | 130 | 4 | for (Block* block : blocks_) { | 131 | 4 | for (Cell& cell : block->cells) { | 132 | 4 | if (!mark_set_.IsMarked(cell_id)) { | 133 | 2 | num_free_++; | 134 | 2 | FreeCell* free_cell = reinterpret_cast<FreeCell*>(cell); | 135 | 2 | free_cell->id = cell_id; | 136 | 2 | free_cell->next = free_list_; | 137 | 2 | free_list_ = free_cell; | 138 | 2 | } | 139 | 4 | cell_id++; | 140 | 4 | } | 141 | 4 | } | 142 | 2 | gc_underway_ = false; | 143 | 2 | } |
|
144 | | |
145 | 120 | void Free() { |
146 | 120 | for (Block* block : blocks_) { |
147 | 119 | free(block); |
148 | 119 | } |
149 | 120 | blocks_.clear(); |
150 | 120 | } _ZN4PoolILi682ELm24EE4FreeEv Line | Count | Source | 145 | 57 | void Free() { | 146 | 57 | for (Block* block : blocks_) { | 147 | 54 | free(block); | 148 | 54 | } | 149 | 57 | blocks_.clear(); | 150 | 57 | } |
_ZN4PoolILi341ELm48EE4FreeEv Line | Count | Source | 145 | 57 | void Free() { | 146 | 57 | for (Block* block : blocks_) { | 147 | 55 | free(block); | 148 | 55 | } | 149 | 57 | blocks_.clear(); | 150 | 57 | } |
_ZN4PoolILi2ELm32EE4FreeEv Line | Count | Source | 145 | 4 | void Free() { | 146 | 6 | for (Block* block : blocks_) { | 147 | 6 | free(block); | 148 | 6 | } | 149 | 4 | blocks_.clear(); | 150 | 4 | } |
_ZN4PoolILi1ELm32EE4FreeEv Line | Count | Source | 145 | 2 | void Free() { | 146 | 4 | for (Block* block : blocks_) { | 147 | 4 | free(block); | 148 | 4 | } | 149 | 2 | blocks_.clear(); | 150 | 2 | } |
|
151 | | |
152 | 28 | int num_allocated() { |
153 | 28 | return num_allocated_; |
154 | 28 | } _ZN4PoolILi682ELm24EE13num_allocatedEv Line | Count | Source | 152 | 12 | int num_allocated() { | 153 | 12 | return num_allocated_; | 154 | 12 | } |
_ZN4PoolILi341ELm48EE13num_allocatedEv Line | Count | Source | 152 | 12 | int num_allocated() { | 153 | 12 | return num_allocated_; | 154 | 12 | } |
_ZN4PoolILi2ELm32EE13num_allocatedEv Line | Count | Source | 152 | 4 | int num_allocated() { | 153 | 4 | return num_allocated_; | 154 | 4 | } |
|
155 | | |
156 | 16 | int64_t bytes_allocated() { |
157 | 16 | return bytes_allocated_; |
158 | 16 | } _ZN4PoolILi682ELm24EE15bytes_allocatedEv Line | Count | Source | 156 | 6 | int64_t bytes_allocated() { | 157 | 6 | return bytes_allocated_; | 158 | 6 | } |
_ZN4PoolILi341ELm48EE15bytes_allocatedEv Line | Count | Source | 156 | 6 | int64_t bytes_allocated() { | 157 | 6 | return bytes_allocated_; | 158 | 6 | } |
_ZN4PoolILi2ELm32EE15bytes_allocatedEv Line | Count | Source | 156 | 4 | int64_t bytes_allocated() { | 157 | 4 | return bytes_allocated_; | 158 | 4 | } |
|
159 | | |
160 | 818 | int num_live() { |
161 | 818 | return blocks_.size() * CellsPerBlock - num_free_; |
162 | 818 | } _ZN4PoolILi682ELm24EE8num_liveEv Line | Count | Source | 160 | 405 | int num_live() { | 161 | 405 | return blocks_.size() * CellsPerBlock - num_free_; | 162 | 405 | } |
_ZN4PoolILi341ELm48EE8num_liveEv Line | Count | Source | 160 | 405 | int num_live() { | 161 | 405 | return blocks_.size() * CellsPerBlock - num_free_; | 162 | 405 | } |
_ZN4PoolILi2ELm32EE8num_liveEv Line | Count | Source | 160 | 6 | int num_live() { | 161 | 6 | return blocks_.size() * CellsPerBlock - num_free_; | 162 | 6 | } |
_ZN4PoolILi1ELm32EE8num_liveEv Line | Count | Source | 160 | 2 | int num_live() { | 161 | 2 | return blocks_.size() * CellsPerBlock - num_free_; | 162 | 2 | } |
|
163 | | |
164 | | private: |
165 | | using Cell = uint8_t[CellSize]; |
166 | | |
167 | | struct Block { |
168 | | Cell cells[CellsPerBlock]; |
169 | | }; |
170 | | |
171 | | // Unused/free cells are tracked via a linked list of FreeCells. The FreeCells |
172 | | // are stored in the unused Cells, so it takes no extra memory to track them. |
173 | | struct FreeCell { |
174 | | int id; |
175 | | FreeCell* next; |
176 | | }; |
177 | | static_assert(CellSize >= sizeof(FreeCell), "CellSize is too small"); |
178 | | |
179 | | // Whether a GC is underway, for asserting that calls are in order. |
180 | | bool gc_underway_ = false; |
181 | | |
182 | | FreeCell* free_list_ = nullptr; |
183 | | int num_free_ = 0; |
184 | | int num_allocated_ = 0; |
185 | | int64_t bytes_allocated_ = 0; |
186 | | std::vector<Block*> blocks_; |
187 | | MarkSet mark_set_; |
188 | | |
189 | | DISALLOW_COPY_AND_ASSIGN(Pool<CellsPerBlock COMMA CellSize>); |
190 | | }; |
191 | | |
192 | | class MarkSweepHeap { |
193 | | public: |
194 | | // reserve 32 frames to start |
195 | 59 | MarkSweepHeap() { |
196 | 59 | } |
197 | | |
198 | | void Init(); // use default threshold |
199 | | void Init(int gc_threshold); |
200 | | |
201 | 110k | void PushRoot(RawObject** p) { |
202 | 110k | roots_.push_back(p); |
203 | 110k | } |
204 | | |
205 | 110k | void PopRoot() { |
206 | 110k | roots_.pop_back(); |
207 | 110k | } |
208 | | |
209 | 8 | void RootGlobalVar(void* root) { |
210 | 8 | global_roots_.push_back(reinterpret_cast<RawObject*>(root)); |
211 | 8 | } |
212 | | |
213 | | void* Allocate(size_t num_bytes, int* obj_id, int* pool_id); |
214 | | |
215 | | #if 0 |
216 | | void* Reallocate(void* p, size_t num_bytes); |
217 | | #endif |
218 | | int MaybeCollect(); |
219 | | int Collect(); |
220 | | |
221 | | void MaybeMarkAndPush(RawObject* obj); |
222 | | void TraceChildren(); |
223 | | |
224 | | void Sweep(); |
225 | | |
226 | | void PrintStats(int fd); // public for testing |
227 | | |
228 | | void CleanProcessExit(); // do one last GC, used in unit tests |
229 | | void ProcessExit(); // main() lets OS clean up, except ASAN variant |
230 | | |
231 | 405 | int num_live() { |
232 | 405 | return num_live_ |
233 | 405 | #ifndef NO_POOL_ALLOC |
234 | 405 | + pool1_.num_live() + pool2_.num_live() |
235 | 405 | #endif |
236 | 405 | ; |
237 | 405 | } |
238 | | |
239 | | bool is_initialized_ = true; // mark/sweep doesn't need to be initialized |
240 | | |
241 | | // Runtime params |
242 | | |
243 | | // Threshold is a number of live objects, since we aren't keeping track of |
244 | | // total bytes |
245 | | int gc_threshold_; |
246 | | |
247 | | // Show debug logging |
248 | | bool gc_verbose_ = false; |
249 | | |
250 | | // Current stats |
251 | | int num_live_ = 0; |
252 | | // Should we keep track of sizes? |
253 | | // int64_t bytes_live_ = 0; |
254 | | |
255 | | // Cumulative stats |
256 | | int max_survived_ = 0; // max # live after a collection |
257 | | int num_allocated_ = 0; |
258 | | int64_t bytes_allocated_ = 0; // avoid overflow |
259 | | int num_gc_points_ = 0; // manual collection points |
260 | | int num_collections_ = 0; |
261 | | int num_growths_; |
262 | | double max_gc_millis_ = 0.0; |
263 | | double total_gc_millis_ = 0.0; |
264 | | |
265 | | #ifndef NO_POOL_ALLOC |
266 | | // 16,384 / 24 bytes = 682 cells (rounded), 16,368 bytes |
267 | | // 16,384 / 48 bytes = 341 cells (rounded), 16,368 bytes |
268 | | // Conveniently, the glibc malloc header is 16 bytes, giving exactly 16 Ki |
269 | | // differences |
270 | | Pool<682, 24> pool1_; |
271 | | Pool<341, 48> pool2_; |
272 | | #endif |
273 | | |
274 | | std::vector<RawObject**> roots_; |
275 | | std::vector<RawObject*> global_roots_; |
276 | | |
277 | | // Allocate() appends live objects, and Sweep() compacts it |
278 | | std::vector<ObjHeader*> live_objs_; |
279 | | // Allocate lazily frees these, and Sweep() replenishes it |
280 | | std::vector<ObjHeader*> to_free_; |
281 | | |
282 | | std::vector<ObjHeader*> gray_stack_; |
283 | | MarkSet mark_set_; |
284 | | |
285 | | int greatest_obj_id_ = 0; |
286 | | |
287 | | private: |
288 | | void FreeEverything(); |
289 | | void MaybePrintStats(); |
290 | | |
291 | | DISALLOW_COPY_AND_ASSIGN(MarkSweepHeap); |
292 | | }; |
293 | | |
294 | | #endif // MARKSWEEP_HEAP_H |