1 /*
2 SuperCollider real time audio synthesis system
3 Copyright (c) 2002 James McCartney. All rights reserved.
4 http://www.audiosynth.com
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20 /*
21
22 The garbage collector for SuperCollider.
23 Based on Wilson and Johnstone's real time collector and the Baker treadmill.
24
25 */
26
27 #pragma once
28
29 #include "PyrObject.h"
30 #include "VMGlobals.h"
31 #include "AdvancingAllocPool.h"
32 #include "function_attributes.h"
33
34 void DumpSimpleBackTrace(VMGlobals* g);
35
36 const int kMaxPoolSet = 7;
37 const int kNumGCSizeClasses = 28;
38 const int kFinalizerSet = kNumGCSizeClasses;
39 const int kNumGCSets = kNumGCSizeClasses + 1;
40 const int kScanThreshold = 256;
41
42
43 class GCSet {
44 public:
GCSet()45 GCSet() {}
46 void Init(int inSizeClass);
47
HasFree()48 bool HasFree() { return mFree != &mBlack; }
49
50 private:
51 friend class PyrGC;
52
53 void MajorFlip();
54 void MinorFlip();
55
56 PyrObjectHdr mBlack;
57 PyrObjectHdr mWhite;
58 PyrObjectHdr* mFree;
59 };
60
61 struct SlotRef {
SlotRefSlotRef62 SlotRef(PyrObject* inObj, int32 inIndex): obj(inObj), slotIndex(inIndex) {}
63
64 PyrObject* obj;
65 int32 slotIndex;
66 };
67
68 class PyrGC {
69 static const int kLazyCollectThreshold = 1024;
70
71 public:
72 PyrGC(VMGlobals* g, AllocPool* inPool, PyrClass* mainProcessClass, long poolSize);
73
74 MALLOC PyrObject* New(size_t inNumBytes, long inFlags, long inFormat, bool inCollect);
75 MALLOC PyrObject* NewFrame(size_t inNumBytes, long inFlags, long inFormat, bool inAccount);
76
77 MALLOC static PyrObject* NewPermanent(size_t inNumBytes, long inFlags, long inFormat);
78
79 MALLOC PyrObject* NewFinalizer(ObjFuncPtr finalizeFunc, PyrObject* inObject, bool inCollect);
80
IsBlack(PyrObjectHdr * inObj)81 bool IsBlack(PyrObjectHdr* inObj) { return inObj->gc_color == mBlackColor; }
IsWhite(PyrObjectHdr * inObj)82 bool IsWhite(PyrObjectHdr* inObj) { return inObj->gc_color == mWhiteColor; }
IsGrey(PyrObjectHdr * inObj)83 bool IsGrey(PyrObjectHdr* inObj) { return inObj->gc_color == mGreyColor; }
IsMarker(PyrObjectHdr * inObj)84 static bool IsMarker(PyrObjectHdr* inObj) { return inObj->gc_color == obj_gcmarker; }
IsFree(PyrObjectHdr * inObj)85 bool IsFree(PyrObjectHdr* inObj) {
86 return (!(IsMarker(inObj) || inObj->IsPermanent() || IsBlack(inObj) || IsWhite(inObj) || IsGrey(inObj)));
87 }
88
ObjIsBlack(PyrObjectHdr * inObj)89 bool ObjIsBlack(PyrObjectHdr* inObj) { return IsBlack(inObj); }
ObjIsGrey(PyrObjectHdr * inObj)90 bool ObjIsGrey(PyrObjectHdr* inObj) { return IsGrey(inObj); }
ObjIsFree(PyrObjectHdr * inObj)91 bool ObjIsFree(PyrObjectHdr* inObj) { return IsFree(inObj); }
92
93
94 // general purpose write barriers:
GCWrite(PyrObjectHdr * inParent,PyrSlot * inSlot)95 void GCWrite(PyrObjectHdr* inParent, PyrSlot* inSlot) {
96 if (IsBlack(inParent) && IsObj(inSlot) && IsWhite(slotRawObject(inSlot))) {
97 ToGrey(slotRawObject(inSlot));
98 }
99 }
GCWrite(PyrObjectHdr * inParent,PyrObjectHdr * inChild)100 void GCWrite(PyrObjectHdr* inParent, PyrObjectHdr* inChild) {
101 if (IsBlack(inParent) && IsWhite(inChild)) {
102 ToGrey(inChild);
103 }
104 }
105 // when you know the parent is black:
GCWriteBlack(PyrSlot * inSlot)106 void GCWriteBlack(PyrSlot* inSlot) {
107 if (IsObj(inSlot)) {
108 if (IsWhite(slotRawObject(inSlot))) {
109 ToGrey(slotRawObject(inSlot));
110 }
111 }
112 }
GCWriteBlack(PyrObjectHdr * inChild)113 void GCWriteBlack(PyrObjectHdr* inChild) {
114 if (IsWhite(inChild)) {
115 ToGrey(inChild);
116 }
117 }
118 // when you know the child is white
GCWriteNew(PyrObjectHdr * inParent,PyrObjectHdr * inChild)119 void GCWriteNew(PyrObjectHdr* inParent, PyrObjectHdr* inChild) {
120 assert(IsWhite(inChild));
121 if (IsBlack(inParent)) {
122 ToGrey(inChild);
123 }
124 }
125
126 // users should not call anything below.
127
128 void Collect();
129 void Collect(int32 inNumToScan);
LazyCollect()130 void LazyCollect() {
131 if (mUncollectedAllocations > kLazyCollectThreshold)
132 Collect();
133 }
134 void FullCollection();
135 void ScanFinalizers();
136 void RunAllFinalizers();
137 GCSet* GetGCSet(PyrObjectHdr* inObj);
138 void CompletePartialScan(PyrObject* obj);
139
140 inline void ToGrey(PyrObjectHdr* inObj);
141 inline void ToGrey2(PyrObjectHdr* inObj);
142 void ToBlack(PyrObjectHdr* inObj);
143 void ToWhite(PyrObjectHdr* inObj);
144 void Free(PyrObjectHdr* inObj);
145
146
StackDepth()147 long StackDepth() { return mVMGlobals->sp - mStack->slots + 1; }
Stack()148 PyrObject* Stack() { return mStack; }
SetStack(PyrObject * inStack)149 void SetStack(PyrObject* inStack) { mStack = inStack; }
150
151 bool SanityCheck();
152 bool SanityCheck2();
153 bool LinkSanity();
154 bool ListSanity();
155 bool BlackToWhiteCheck(PyrObject* objA);
156 bool SanityMarkObj(PyrObject* objA, PyrObject* fromObj, int level);
157 bool SanityClearObj(PyrObject* objA, int level);
158 void DumpInfo();
159 void DumpGrey();
160 void DumpSet(int set);
161
162 void BecomePermanent(PyrObject* inObject);
163 void BecomeImmutable(PyrObject* inObject);
164
IsPartialScanObject(PyrObject * inObject)165 bool IsPartialScanObject(PyrObject* inObject) const { return inObject == mPartialScanObj; }
GetPartialScanIndex()166 int32 GetPartialScanIndex() const { return mPartialScanSlot; }
167
168 private:
169 inline PyrObject* Allocate(size_t inNumBytes, int32 sizeclass, bool inCollect);
170 static void throwMemfailed(size_t inNumBytes);
171
172 void ScanSlots(PyrSlot* inSlots, long inNumToScan);
173 void SweepBigObjects();
174 void DoPartialScan(int32 inObjSize);
175 bool ScanOneObj();
176 void Flip();
177 void ScanStack();
178 void ScanFrames();
179 void DLRemove(PyrObjectHdr* obj);
180 void DLInsertAfter(PyrObjectHdr* after, PyrObjectHdr* obj);
181 void DLInsertBefore(PyrObjectHdr* before, PyrObjectHdr* obj);
182
183 void ClearMarks();
184 void Finalize(PyrObject* obj);
185
186 void beginPause();
187 void endPause();
188 void reportPause();
189
190 VMGlobals* mVMGlobals;
191 AllocPool* mPool;
192 AdvancingAllocPool mNewPool;
193 GCSet mSets[kNumGCSets];
194 PyrProcess* mProcess; // the root is the pyrprocess which contains this struct
195 PyrObject* mStack;
196 PyrObject* mPartialScanObj;
197 PyrObjectHdr mGrey;
198
199 int32 mPartialScanSlot;
200 int32 mNumToScan;
201 int32 mNumGrey;
202
203 int32 mFlips, mCollects, mAllocTotal, mScans, mNumAllocs, mStackScans, mNumPartialScans, mSlotsScanned,
204 mUncollectedAllocations;
205
206 unsigned char mBlackColor, mGreyColor, mWhiteColor, mFreeColor;
207 bool mCanSweep;
208 bool mRunning;
209 };
210
DLRemove(PyrObjectHdr * obj)211 inline void PyrGC::DLRemove(PyrObjectHdr* obj) {
212 obj->next->prev = obj->prev;
213 obj->prev->next = obj->next;
214 }
215
DLInsertAfter(PyrObjectHdr * after,PyrObjectHdr * obj)216 inline void PyrGC::DLInsertAfter(PyrObjectHdr* after, PyrObjectHdr* obj) {
217 obj->next = after->next;
218 obj->prev = after;
219 after->next->prev = obj;
220 after->next = obj;
221 }
222
DLInsertBefore(PyrObjectHdr * before,PyrObjectHdr * obj)223 inline void PyrGC::DLInsertBefore(PyrObjectHdr* before, PyrObjectHdr* obj) {
224 obj->prev = before->prev;
225 obj->next = before;
226 before->prev->next = obj;
227 before->prev = obj;
228 }
229
GetGCSet(PyrObjectHdr * inObj)230 inline GCSet* PyrGC::GetGCSet(PyrObjectHdr* inObj) {
231 return mSets + (inObj->classptr == class_finalizer ? kFinalizerSet : inObj->obj_sizeclass);
232 }
233
ToBlack(PyrObjectHdr * obj)234 inline void PyrGC::ToBlack(PyrObjectHdr* obj) {
235 if (IsGrey(obj)) {
236 mNumGrey--;
237 // post("ToBlack %d\n", mNumGrey);
238 }
239
240 DLRemove(obj);
241
242 GCSet* gcs = GetGCSet(obj);
243 DLInsertAfter(&gcs->mBlack, obj);
244
245 obj->gc_color = mBlackColor;
246 }
247
ToWhite(PyrObjectHdr * obj)248 inline void PyrGC::ToWhite(PyrObjectHdr* obj) {
249 if (IsGrey(obj)) {
250 mNumGrey--;
251 // post("ToWhite %d\n", mNumGrey);
252 }
253
254 DLRemove(obj);
255
256 GCSet* gcs = GetGCSet(obj);
257 DLInsertAfter(&gcs->mWhite, obj);
258
259 obj->gc_color = mWhiteColor;
260 }
261
Free(PyrObjectHdr * obj)262 inline void PyrGC::Free(PyrObjectHdr* obj) {
263 if (IsGrey(obj)) {
264 mNumGrey--;
265 // post("ToWhite %d\n", mNumGrey);
266 }
267
268 DLRemove(obj);
269
270 GCSet* gcs = GetGCSet(obj);
271 DLInsertBefore(gcs->mFree, obj);
272 gcs->mFree = obj;
273
274 obj->gc_color = mFreeColor;
275 obj->size = 0;
276 }
277
ToGrey(PyrObjectHdr * obj)278 inline void PyrGC::ToGrey(PyrObjectHdr* obj) {
279 /* move obj from white to grey */
280 /* link around object */
281 DLRemove(obj);
282
283 /* link in new place */
284 DLInsertAfter(&mGrey, obj);
285
286 /* set grey list pointer to obj */
287 obj->gc_color = mGreyColor;
288 mNumGrey++;
289 mNumToScan += 1L << obj->obj_sizeclass;
290 }
291
ToGrey2(PyrObjectHdr * obj)292 inline void PyrGC::ToGrey2(PyrObjectHdr* obj) {
293 /* move obj from white to grey */
294 /* link around object */
295 DLRemove(obj);
296
297 /* link in new place */
298 DLInsertAfter(&mGrey, obj);
299
300 /* set grey list pointer to obj */
301 obj->gc_color = mGreyColor;
302 mNumGrey++;
303 }
304
Allocate(size_t inNumBytes,int32 sizeclass,bool inRunCollection)305 inline PyrObject* PyrGC::Allocate(size_t inNumBytes, int32 sizeclass, bool inRunCollection) {
306 if (inRunCollection && mNumToScan >= kScanThreshold)
307 Collect();
308 else {
309 if (inRunCollection)
310 mUncollectedAllocations = 0;
311 else
312 ++mUncollectedAllocations;
313 }
314
315 GCSet* gcs = mSets + sizeclass;
316
317 PyrObject* obj = (PyrObject*)gcs->mFree;
318 if (!IsMarker(obj)) {
319 // from free list
320 gcs->mFree = obj->next;
321 assert(obj->obj_sizeclass == sizeclass);
322 } else {
323 if (sizeclass > kMaxPoolSet) {
324 SweepBigObjects();
325 size_t allocSize = sizeof(PyrObjectHdr) + (sizeof(PyrSlot) << sizeclass);
326 obj = (PyrObject*)mPool->Alloc(allocSize);
327 } else {
328 size_t allocSize = sizeof(PyrObjectHdr) + (sizeof(PyrSlot) << sizeclass);
329 obj = (PyrObject*)mNewPool.Alloc(allocSize);
330 }
331 if (!obj)
332 throwMemfailed(inNumBytes);
333 DLInsertAfter(&gcs->mWhite, obj);
334 obj->obj_sizeclass = sizeclass;
335 }
336 return obj;
337 }
338