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