OILS / mycpp / gc_obj.h View on Github | oilshell.org

185 lines, 92 significant
1#ifndef MYCPP_GC_OBJ_H
2#define MYCPP_GC_OBJ_H
3
4#include <stdint.h> // uint8_t
5
6#include "mycpp/common.h"
7
8namespace HeapTag {
9const int Global = 0; // Don't mark or sweep.
10const int Opaque = 1; // e.g. List<int>, BigStr
11 // Mark and sweep, but don't trace children
12const int FixedSize = 2; // Consult field_mask for children
13const int Scanned = 3; // Scan a contiguous range of children
14}; // namespace HeapTag
15
16// These tags are mainly for debugging. Oils is a statically typed program, so
17// we don't need runtime types in general.
18// This "enum" starts from the end of the valid type_tag range.
19// asdl/gen_cpp.py starts from 1 for variants, or 64 for shared variants.
20namespace TypeTag {
21const int OtherClass = 127; // non-ASDL class
22const int BigStr = 126; // asserted in dynamic StrFormat()
23const int Slab = 125;
24const int Tuple = 124;
25const int List = 123;
26const int Dict = 122;
27}; // namespace TypeTag
28
29const int kNotInPool = 0;
30const int kInPool = 1;
31
32const unsigned kZeroMask = 0; // for types with no pointers
33
34const int kMaxObjId = (1 << 28) - 1; // 28 bits means 512 Mi objects per pool
35const int kIsGlobal = kMaxObjId; // for debugging, not strictly needed
36
37const int kUndefinedId = 0; // Uninitialized object ID
38
39// Every GC-managed object is preceded in memory by an ObjHeader.
40// TODO: ./configure could detect endian-ness, and reorder the fields in
41// ObjHeader. See mycpp/demo/gc_header.cc.
42struct ObjHeader {
43 unsigned type_tag : 8; // TypeTag, ASDL variant / shared variant
44 // Depending on heap_tag, up to 24 fields or 2**24 = 16 Mi pointers to scan
45 unsigned u_mask_npointers : 24;
46
47 unsigned heap_tag : 2; // HeapTag::Opaque, etc.
48 unsigned pool_id : 2; // 0 for malloc(), or 1 2 3 for fixed sized pools
49 unsigned obj_id : 28; // 1 Gi unique objects
50
51 // Returns the address of the GC managed object associated with this header.
52 // Note: this relies on there being no padding between the header and the
53 // object. See Alloc<T>() and GcGlobal<T> for relevant static_assert()s.
54 void* ObjectAddress() {
55 return reinterpret_cast<void*>(reinterpret_cast<char*>(this) +
56 sizeof(ObjHeader));
57 }
58
59 // Returns the header for the given GC managed object.
60 // Note: this relies on there being no padding between the header and the
61 // object. See Alloc<T>() and GcGlobal<T> for relevant static_assert()s.
62 static ObjHeader* FromObject(const void* obj) {
63 return reinterpret_cast<ObjHeader*>(
64 static_cast<char*>(const_cast<void*>(obj)) - sizeof(ObjHeader));
65 }
66
67 // Used by hand-written and generated classes
68 static constexpr ObjHeader ClassFixed(uint32_t field_mask, uint32_t obj_len) {
69 return {TypeTag::OtherClass, field_mask, HeapTag::FixedSize, kNotInPool,
70 kUndefinedId};
71 }
72
73 // For ASDL - tagged subtypes of List<T> and Dict<K, V>
74 static constexpr ObjHeader TaggedSubtype(uint8_t type_tag,
75 uint32_t field_mask) {
76 return {type_tag, field_mask, HeapTag::FixedSize, kNotInPool, kUndefinedId};
77 }
78
79 // Classes with no inheritance (e.g. used by mycpp)
80 static constexpr ObjHeader ClassScanned(uint32_t num_pointers,
81 uint32_t obj_len) {
82 return {TypeTag::OtherClass, num_pointers, HeapTag::Scanned, kNotInPool,
83 kUndefinedId};
84 }
85
86 // Used by frontend/flag_gen.py. TODO: Sort fields and use GC_CLASS_SCANNED
87 static constexpr ObjHeader Class(uint8_t heap_tag, uint32_t field_mask,
88 uint32_t obj_len) {
89 return {TypeTag::OtherClass, field_mask, heap_tag, kNotInPool,
90 kUndefinedId};
91 }
92
93 // Used by ASDL.
94 static constexpr ObjHeader AsdlClass(uint8_t type_tag,
95 uint32_t num_pointers) {
96 return {type_tag, num_pointers, HeapTag::Scanned, kNotInPool, kUndefinedId};
97 }
98
99 static constexpr ObjHeader BigStr() {
100 return {TypeTag::BigStr, kZeroMask, HeapTag::Opaque, kNotInPool,
101 kUndefinedId};
102 }
103
104 static constexpr ObjHeader Slab(uint8_t heap_tag, uint32_t num_pointers) {
105 return {TypeTag::Slab, num_pointers, heap_tag, kNotInPool, kUndefinedId};
106 }
107
108 static constexpr ObjHeader Tuple(uint32_t field_mask, uint32_t obj_len) {
109 return {TypeTag::Tuple, field_mask, HeapTag::FixedSize, kNotInPool,
110 kUndefinedId};
111 }
112
113 // Used by GLOBAL_STR, GLOBAL_LIST, GLOBAL_DICT
114 static constexpr ObjHeader Global(uint8_t type_tag) {
115 return {type_tag, kZeroMask, HeapTag::Global, kNotInPool, kIsGlobal};
116 }
117};
118
119inline int ObjectId(void* obj) {
120 ObjHeader* h = ObjHeader::FromObject(obj);
121
122 // pool_id is 2 bits, so shift the 28 bit obj_id past it.
123 return (h->obj_id << 2) + h->pool_id;
124}
125
126#define FIELD_MASK(header) (header).u_mask_npointers
127#define NUM_POINTERS(header) (header).u_mask_npointers
128
129// A RawObject* is like a void*. We use it to represent GC managed objects.
130struct RawObject;
131
132//
133// Compile-time computation of GC field masks.
134//
135
136// maskbit(field_offset) returns a bit in mask that you can bitwise-or (|) with
137// other bits.
138//
139// - Note that we only call maskbit() on offsets of pointer fields, which must
140// be POINTER-ALIGNED.
141
142constexpr int maskbit(size_t offset) {
143 return 1 << (offset / sizeof(void*));
144}
145
146// A wrapper for a GC object and its header. For creating global GC objects,
147// like GlobalStr.
148// TODO: Make this more ergonomic by automatically initializing header
149// with T::obj_header() and providing a forwarding constructor for obj.
150template <typename T>
151class GcGlobalImpl {
152 public:
153 ObjHeader header;
154 T obj;
155
156 // This class only exists to write the static_assert. If you try to put the
157 // static_assert directly in the outer class you get a compiler error that
158 // taking the offsets is an 'invalid use of incomplete type'. Doing it this
159 // way means the type gets completed before the assert.
160 struct Internal {
161 using type = GcGlobalImpl<T>;
162 static_assert(offsetof(type, obj) - sizeof(ObjHeader) ==
163 offsetof(type, header),
164 "ObjHeader doesn't fit");
165 };
166
167 DISALLOW_COPY_AND_ASSIGN(GcGlobalImpl);
168};
169
170// Refer to `Internal::type` to force Internal to be instantiated.
171template <typename T>
172using GcGlobal = typename GcGlobalImpl<T>::Internal::type;
173
174// The "homogeneous" layout of objects with HeapTag::FixedSize. LayoutFixed is
175// for casting; it isn't a real type.
176
177// TODO: we could determine the max of all objects statically!
178const int kFieldMaskBits = 24;
179
180struct LayoutFixed {
181 // only the entries denoted in field_mask will be valid
182 RawObject* children_[kFieldMaskBits];
183};
184
185#endif // MYCPP_GC_OBJ_H