cpp

Coverage Report

Created: 2023-03-07 20:24

/home/andy/git/oilshell/oil/mycpp/gc_obj.h
Line
Count
Source (jump to first uncovered line)
1
#ifndef MYCPP_GC_OBJ_H
2
#define MYCPP_GC_OBJ_H
3
4
#include <stdint.h>  // uint8_t
5
6
namespace HeapTag {
7
const int Global = 0;     // Don't mark or sweep.
8
                          // Cheney: Don't copy or scan.
9
const int Opaque = 1;     // e.g. List<int>, Str
10
                          // Mark and sweep, but don't trace children
11
                          // Cheney: Copy, but don't scan.
12
const int FixedSize = 2;  // Consult field_mask for children
13
const int Scanned = 3;    // Scan a contiguous range of children
14
15
const int Forwarded = 4;  // For the Cheney algorithm.
16
};                        // namespace HeapTag
17
18
// These tags are mainly for debugging.  Oil is a statically typed
19
// program, so we don't need runtime types in general.
20
// This "enum" starts from the end of the valid type_tag range.
21
// asdl/gen_cpp.py starts from 1 for variants, or 64 for shared variants.
22
namespace TypeTag {
23
const int OtherClass = 127;  // non-ASDL class
24
const int Str = 126;         // asserted in dynamic StrFormat()
25
const int Slab = 125;
26
const int Tuple = 124;
27
};  // namespace TypeTag
28
29
const int kIsHeader = 1;  // for is_header bit
30
31
const unsigned kZeroMask = 0;  // for types with no pointers
32
33
const int kMaxObjId = (1 << 30) - 1;  // 30 bit object ID
34
const int kIsGlobal = kMaxObjId;      // for debugging, not strictly needed
35
36
const int kUndefinedId = 0;  // Unitialized object ID
37
38
// The first member of every GC-managed object is 'ObjHeader header_'.
39
// (There's no inheritance!)
40
struct ObjHeader {
41
  unsigned is_header : 1;  // To distinguish from vtable pointer
42
                           // Overlaps with RawObject::points_to_header
43
  unsigned type_tag : 7;   // TypeTag, ASDL variant / shared variant
44
#if defined(MARK_SWEEP) || defined(BUMP_LEAK)
45
  // Depending on heap_tag, up to 24 fields or 2**24 = 16 Mi pointers to scan
46
  unsigned u_mask_npointers : 24;
47
#else
48
  unsigned field_mask : 24;  // Cheney needs field_maks AND obj_len
49
#endif
50
51
#if defined(MARK_SWEEP) || defined(BUMP_LEAK)
52
  unsigned heap_tag : 2;  // HeapTag::Opaque, etc.
53
  unsigned obj_id : 30;   // 1 Gi unique objects
54
#else
55
  unsigned heap_tag : 3;     // Cheney also needs HeapTag::Forwarded
56
  unsigned obj_len : 29;     // Cheney: number of bytes to copy
57
#endif
58
59
  // Used by hand-written and generated classes
60
1.27k
  static constexpr ObjHeader ClassFixed(uint16_t field_mask, uint32_t obj_len) {
61
1.27k
    return {kIsHeader, TypeTag::OtherClass, field_mask, HeapTag::FixedSize,
62
1.27k
            kUndefinedId};
63
1.27k
  }
64
65
  // Classes with no inheritance (e.g. used by mycpp)
66
  static constexpr ObjHeader ClassScanned(uint32_t num_pointers,
67
69
                                          uint32_t obj_len) {
68
69
    return {kIsHeader, TypeTag::OtherClass, num_pointers, HeapTag::Scanned,
69
69
            kUndefinedId};
70
69
  }
71
72
  // Used by frontend/flag_gen.py.  TODO: Sort fields and use GC_CLASS_SCANNED
73
  static constexpr ObjHeader Class(uint8_t heap_tag, uint16_t field_mask,
74
0
                                   uint32_t obj_len) {
75
0
    return {kIsHeader, TypeTag::OtherClass, field_mask, heap_tag, kUndefinedId};
76
0
  }
77
78
  // Used by ASDL.
79
  static constexpr ObjHeader AsdlClass(uint8_t type_tag,
80
209
                                       uint32_t num_pointers) {
81
209
    return {kIsHeader, type_tag, num_pointers, HeapTag::Scanned, kUndefinedId};
82
209
  }
83
84
5.41k
  static constexpr ObjHeader Str() {
85
5.41k
    return {kIsHeader, TypeTag::Str, kZeroMask, HeapTag::Opaque, kUndefinedId};
86
5.41k
  }
87
88
1.17k
  static constexpr ObjHeader Slab(uint8_t heap_tag, uint32_t num_pointers) {
89
1.17k
    return {kIsHeader, TypeTag::Slab, num_pointers, heap_tag, kUndefinedId};
90
1.17k
  }
91
92
211
  static constexpr ObjHeader Tuple(uint16_t field_mask, uint32_t obj_len) {
93
211
    return {kIsHeader, TypeTag::Tuple, field_mask, HeapTag::FixedSize,
94
211
            kUndefinedId};
95
211
  }
96
};
97
98
// TODO: we could determine the max of all objects statically!
99
const int kFieldMaskBits = 16;
100
101
#if defined(MARK_SWEEP) || defined(BUMP_LEAK)
102
150
  #define FIELD_MASK(header) (header).u_mask_npointers
103
10
  #define NUM_POINTERS(header) (header).u_mask_npointers
104
105
#else
106
  #define FIELD_MASK(header) (header).field_mask
107
                             // TODO: derive from obj_len
108
  #define NUM_POINTERS(header) \
109
    ((header.obj_len - kSlabHeaderSize) / sizeof(void*))
110
#endif
111
112
// A RawObject* is like a void* -- it can point to any C++ object.  The object
113
// may start with either ObjHeader, or vtable pointer then an ObjHeader.
114
struct RawObject {
115
  unsigned points_to_header : 1;  // same as ObjHeader::is_header
116
  unsigned pad : 31;
117
};
118
119
// TODO: ./configure could detect endian-ness, and reorder the fields in
120
// ObjHeader.  See mycpp/demo/gc_header.cc.
121
122
// Used by hand-written and generated classes
123
#define GC_CLASS_FIXED(header_, field_mask, obj_len)                \
124
  header_ {                                                         \
125
    kIsHeader, TypeTag::OtherClass, field_mask, HeapTag::FixedSize, \
126
        kUndefinedId                                                \
127
  }
128
129
// Classes with no inheritance (e.g. used by mycpp)
130
#define GC_CLASS_SCANNED(header_, num_pointers, obj_len)            \
131
  header_ {                                                         \
132
    kIsHeader, TypeTag::OtherClass, num_pointers, HeapTag::Scanned, \
133
        kUndefinedId                                                \
134
  }
135
136
// Used by frontend/flag_gen.py.  TODO: Sort fields and use GC_CLASS_SCANNED
137
#define GC_CLASS(header_, heap_tag, field_mask, obj_len)               \
138
  header_ {                                                            \
139
    kIsHeader, TypeTag::OtherClass, field_mask, heap_tag, kUndefinedId \
140
  }
141
142
// Used by ASDL.
143
#define GC_ASDL_CLASS(header_, type_tag, num_pointers)                \
144
  header_ {                                                           \
145
    kIsHeader, type_tag, num_pointers, HeapTag::Scanned, kUndefinedId \
146
  }
147
148
#define GC_STR(header_)                                               \
149
  header_ {                                                           \
150
    kIsHeader, TypeTag::Str, kZeroMask, HeapTag::Opaque, kUndefinedId \
151
  }
152
153
#define GC_SLAB(header_, heap_tag, num_pointers)                   \
154
  header_ {                                                        \
155
    kIsHeader, TypeTag::Slab, num_pointers, heap_tag, kUndefinedId \
156
  }
157
158
#define GC_TUPLE(header_, field_mask, obj_len)                              \
159
  header_ {                                                                 \
160
    kIsHeader, TypeTag::Tuple, field_mask, HeapTag::FixedSize, kUndefinedId \
161
  }
162
163
// TODO: could omit this in BUMP_LEAK mode
164
#define GC_OBJ(var_name) ObjHeader var_name
165
166
//
167
// Compile-time computation of GC field masks.
168
//
169
170
class _DummyObj {  // For maskbit()
171
 public:
172
  ObjHeader header_;
173
  int first_field_;
174
};
175
176
// maskbit(field_offset) returns a bit in mask that you can bitwise-or (|) with
177
// other bits.
178
//
179
// - Note that we only call maskbit() on offsets of pointer fields, which must
180
//   be POINTER-ALIGNED.
181
// - _DummyObj is used in case ObjHeader requires padding, then
182
//   sizeof(ObjHeader) != offsetof(_DummyObj, first_field_)
183
184
1.44k
constexpr int maskbit(int offset) {
185
1.44k
  return 1 << ((offset - offsetof(_DummyObj, first_field_)) / sizeof(void*));
186
1.44k
}
187
188
class _DummyObj_v {  // For maskbit_v()
189
 public:
190
  void* vtable;  // how the compiler does dynamic dispatch
191
  ObjHeader header_;
192
  int first_field_;
193
};
194
195
// maskbit_v(field_offset) is like maskbit(), but accounts for the vtable
196
// pointer.
197
198
134
constexpr int maskbit_v(int offset) {
199
134
  return 1 << ((offset - offsetof(_DummyObj_v, first_field_)) / sizeof(void*));
200
134
}
201
202
10.0k
inline ObjHeader* FindObjHeader(RawObject* obj) {
203
10.0k
  if (obj->points_to_header) {
204
9.75k
    return reinterpret_cast<ObjHeader*>(obj);
205
9.75k
  } else {
206
    // We saw a vtable pointer, so return the ObjHeader* header that
207
    // immediately follows.
208
299
    return reinterpret_cast<ObjHeader*>(reinterpret_cast<char*>(obj) +
209
299
                                        sizeof(void*));
210
299
  }
211
10.0k
}
212
213
// The "homogeneous" layout of objects with HeapTag::FixedSize.  LayoutFixed is
214
// for casting; it isn't a real type.
215
216
class LayoutFixed {
217
 public:
218
  ObjHeader header_;
219
  // only the entries denoted in field_mask will be valid
220
  RawObject* children_[kFieldMaskBits];
221
};
222
223
#endif  // MYCPP_GC_OBJ_H