cpp

Coverage Report

Created: 2023-03-07 20:24

/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 <vector>
5
6
#include "mycpp/common.h"
7
#include "mycpp/gc_obj.h"
8
9
class MarkSet {
10
 public:
11
58
  MarkSet() : bits_() {
12
58
  }
13
14
  // ReInit() must be called at the start of MarkObjects().  Allocate() should
15
  // keep track of the maximum object ID.
16
116
  void ReInit(int max_obj_id) {
17
    // https://stackoverflow.com/questions/8848575/fastest-way-to-reset-every-value-of-stdvectorint-to-0
18
116
    std::fill(bits_.begin(), bits_.end(), 0);
19
116
    int max_byte_index = (max_obj_id >> 3) + 1;  // round up
20
    // log("ReInit max_byte_index %d", max_byte_index);
21
116
    bits_.resize(max_byte_index);
22
116
  }
23
24
  // Called by MarkObjects()
25
126
  void Mark(int obj_id) {
26
126
    DCHECK(obj_id >= 0);
27
    // log("obj id %d", obj_id);
28
126
    DCHECK(!IsMarked(obj_id));
29
0
    int byte_index = obj_id >> 3;  // 8 bits per byte
30
126
    int bit_index = obj_id & 0b111;
31
    // log("byte_index %d %d", byte_index, bit_index);
32
126
    bits_[byte_index] |= (1 << bit_index);
33
126
  }
34
35
  // Called by Sweep()
36
8.83k
  bool IsMarked(int obj_id) {
37
8.83k
    DCHECK(obj_id >= 0);
38
0
    int byte_index = obj_id >> 3;
39
8.83k
    int bit_index = obj_id & 0b111;
40
8.83k
    return bits_[byte_index] & (1 << bit_index);
41
8.83k
  }
42
43
2
  void Debug() {
44
2
    int n = bits_.size();
45
2
    dprintf(2, "[ ");
46
8
    for (int i = 0; i < n; ++i) {
47
6
      dprintf(2, "%02x ", bits_[i]);
48
6
    }
49
2
    dprintf(2, "] (%d bytes) \n", n);
50
2
    dprintf(2, "[ ");
51
2
    int num_bits = 0;
52
8
    for (int i = 0; i < n; ++i) {
53
54
      for (int j = 0; j < 8; ++j) {
54
48
        int bit = (bits_[i] & (1 << j)) != 0;
55
48
        dprintf(2, "%d", bit);
56
48
        num_bits += bit;
57
48
      }
58
6
    }
59
2
    dprintf(2, " ] (%d bits set)\n", num_bits);
60
2
  }
61
62
  std::vector<uint8_t> bits_;  // bit vector indexed by obj_id
63
};
64
65
class MarkSweepHeap {
66
 public:
67
  // reserve 32 frames to start
68
56
  MarkSweepHeap() {
69
56
  }
70
71
  void Init();  // use default threshold
72
  void Init(int gc_threshold);
73
74
110k
  void PushRoot(RawObject** p) {
75
110k
    roots_.push_back(p);
76
110k
  }
77
78
110k
  void PopRoot() {
79
110k
    roots_.pop_back();
80
110k
  }
81
82
8
  void RootGlobalVar(void* root) {
83
8
    global_roots_.push_back(reinterpret_cast<RawObject*>(root));
84
8
  }
85
86
  void* Allocate(size_t num_bytes);
87
8.15k
  int UnusedObjectId() {
88
    // Allocate() sets this
89
    // log("  unused -> %d", obj_id_after_allocate_);
90
8.15k
    return obj_id_after_allocate_;
91
8.15k
  }
92
93
#if 0
94
  void* Reallocate(void* p, size_t num_bytes);
95
#endif
96
  int MaybeCollect();
97
  int Collect();
98
99
  void MaybeMarkAndPush(RawObject* obj);
100
  void TraceChildren();
101
102
  void Sweep();
103
104
  void PrintStats(int fd);  // public for testing
105
106
  void EagerFree();         // for remaining ASAN clean
107
  void CleanProcessExit();  // do one last GC so ASAN passes
108
  void FastProcessExit();   // let the OS clean up
109
110
  bool is_initialized_ = true;  // mark/sweep doesn't need to be initialized
111
112
  // Runtime params
113
114
  // Threshold is a number of live objects, since we aren't keeping track of
115
  // total bytes
116
  int gc_threshold_;
117
118
  // Show debug logging
119
  bool gc_verbose_ = false;
120
121
  // Current stats
122
  int num_live_ = 0;
123
  // Should we keep track of sizes?
124
  // int64_t bytes_live_ = 0;
125
126
  // Cumulative stats
127
  int max_survived_ = 0;  // max # live after a collection
128
  int num_allocated_ = 0;
129
  int64_t bytes_allocated_ = 0;  // avoid overflow
130
  int num_gc_points_ = 0;        // manual collection points
131
  int num_collections_ = 0;
132
  int num_growths_;
133
  double max_gc_millis_ = 0.0;
134
  double total_gc_millis_ = 0.0;
135
136
  std::vector<RawObject**> roots_;
137
  std::vector<RawObject*> global_roots_;
138
139
  // Allocate() appends live objects, and Sweep() compacts it
140
  std::vector<RawObject*> live_objs_;
141
  // Allocate lazily frees these, and Sweep() replenishes it
142
  std::vector<RawObject*> to_free_;
143
144
  std::vector<ObjHeader*> gray_stack_;
145
  MarkSet mark_set_;
146
147
  int greatest_obj_id_ = 0;
148
  int obj_id_after_allocate_ = 0;
149
150
 private:
151
  void DoProcessExit(bool fast_exit);
152
153
  DISALLOW_COPY_AND_ASSIGN(MarkSweepHeap);
154
};
155
156
#endif  // MARKSWEEP_HEAP_H