include/lang/GC.h

   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 #ifndef _GC_
  28 #define _GC_
  29
  30 #include "PyrObject.h"
  31 #include "VMGlobals.h"
  32 #include "AdvancingAllocPool.h"
  33 #include "function_attributes.h"
  34
  35 void DumpSimpleBackTrace(VMGlobals *g);
  36
  37 const int kMaxPoolSet = 7;
  38 const int kNumGCSizeClasses = 28;
  39 const int kFinalizerSet = kNumGCSizeClasses;
  40 const int kNumGCSets = kNumGCSizeClasses + 1;
  41 const int kScanThreshold =  256;
  42
  43
  44 class GCSet
  45 {
  46 public:
  47         GCSet() {}
  48         void Init(int inSizeClass);
  49
  50         bool HasFree() { return mFree != &mBlack; }
  51
  52 private:
  53         friend class PyrGC;
  54
  55         void MajorFlip();
  56         void MinorFlip();
  57
  58         PyrObjectHdr mBlack;
  59         PyrObjectHdr mWhite;
  60         PyrObjectHdr* mFree;
  61 };
  62
  63 struct SlotRef {
  64         SlotRef(PyrObject* inObj, int32 inIndex) : obj(inObj), slotIndex(inIndex) {}
  65
  66         PyrObject *obj;
  67         int32 slotIndex;
  68 };
  69
  70 class PyrGC
  71 {
  72         static const int kLazyCollectThreshold = 1024;
  73
  74 public:
  75         PyrGC(VMGlobals *g, AllocPool *inPool, PyrClass *mainProcessClass, long poolSize);
  76
  77         MALLOC PyrObject* New(size_t inNumBytes, long inFlags, long inFormat, bool inCollect);
  78         MALLOC PyrObject* NewFrame(size_t inNumBytes, long inFlags, long inFormat, bool inAccount);
  79
  80         MALLOC static PyrObject* NewPermanent(size_t inNumBytes,
  81                                                 long inFlags, long inFormat);
  82
  83         MALLOC PyrObject* NewFinalizer(ObjFuncPtr finalizeFunc, PyrObject *inObject, bool inCollect);
  84
  85         bool IsBlack(PyrObjectHdr* inObj)  { return inObj->gc_color == mBlackColor; }
  86         bool IsWhite(PyrObjectHdr* inObj)  { return inObj->gc_color == mWhiteColor; }
  87         bool IsGrey(PyrObjectHdr* inObj)   { return inObj->gc_color == mGreyColor; }
  88         static bool IsMarker(PyrObjectHdr* inObj) { return inObj->gc_color == obj_gcmarker; }
  89         bool IsFree(PyrObjectHdr* inObj)   { return (!(IsMarker(inObj) ||
  90                                                                                                         inObj->IsPermanent() ||
  91                                                                                                         IsBlack(inObj) ||
  92                                                                                                         IsWhite(inObj) ||
  93                                                                                                         IsGrey(inObj))); }
  94
  95         bool ObjIsBlack(PyrObjectHdr* inObj) { return IsBlack(inObj); }
  96         bool ObjIsGrey(PyrObjectHdr* inObj) { return IsGrey(inObj); }
  97         bool ObjIsFree(PyrObjectHdr* inObj) { return IsFree(inObj); }
  98
  99
 100         // general purpose write barriers:
 101         void GCWrite(PyrObjectHdr* inParent, PyrSlot* inSlot)
 102                 {
 103                         if (IsBlack(inParent) && IsObj(inSlot) && IsWhite(slotRawObject(inSlot))) {
 104                                 ToGrey(slotRawObject(inSlot));
 105                         }
 106                 }
 107         void GCWrite(PyrObjectHdr* inParent, PyrObjectHdr* inChild)
 108                 {
 109                         if (IsBlack(inParent) && IsWhite(inChild)) {
 110                                 ToGrey(inChild);
 111                         }
 112                 }
 113         // when you know the parent is black:
 114         void GCWriteBlack(PyrSlot* inSlot)
 115                 {
 116                         if (IsObj(inSlot)) {
 117                                 if (IsWhite(slotRawObject(inSlot))) {
 118                                         ToGrey(slotRawObject(inSlot));
 119                                 }
 120                         }
 121                 }
 122         void GCWriteBlack(PyrObjectHdr* inChild)
 123                 {
 124                         if (IsWhite(inChild)) {
 125                                 ToGrey(inChild);
 126                         }
 127                 }
 128         // when you know the child is white
 129         void GCWriteNew(PyrObjectHdr* inParent, PyrObjectHdr* inChild)
 130                 {
 131                         if (IsBlack(inParent)) {
 132                                 ToGrey(inChild);
 133                         }
 134                 }
 135
 136 // users should not call anything below.
 137
 138         void Collect();
 139         void Collect(int32 inNumToScan);
 140         void LazyCollect()
 141         {
 142                 if (mUncollectedAllocations > kLazyCollectThreshold)
 143                         Collect();
 144         }
 145         void FullCollection();
 146         void ScanFinalizers();
 147         GCSet* GetGCSet(PyrObjectHdr* inObj);
 148         void CompletePartialScan(PyrObject *obj);
 149
 150         inline void ToGrey(PyrObjectHdr* inObj);
 151         inline void ToGrey2(PyrObjectHdr* inObj);
 152         void ToBlack(PyrObjectHdr* inObj);
 153         void ToWhite(PyrObjectHdr *inObj);
 154         void Free(PyrObjectHdr* inObj);
 155
 156
 157         int32 StackDepth() { return mVMGlobals->sp - mStack->slots + 1; }
 158         PyrObject* Stack() { return mStack; }
 159         void SetStack(PyrObject* inStack) { mStack = inStack; }
 160
 161         bool SanityCheck();
 162         bool SanityCheck2();
 163         bool LinkSanity();
 164         bool ListSanity();
 165         bool BlackToWhiteCheck(PyrObject *objA);
 166         bool SanityMarkObj(PyrObject *objA, PyrObject *fromObj, int level);
 167         bool SanityClearObj(PyrObject *objA, int level);
 168         void DumpInfo();
 169         void DumpGrey();
 170         void DumpSet(int set);
 171
 172         void BecomePermanent(PyrObject *inObject);
 173         void BecomeImmutable(PyrObject *inObject);
 174
 175         bool IsPartialScanObject(PyrObject* inObject) const { return inObject == mPartialScanObj; }
 176         int32 GetPartialScanIndex() const { return mPartialScanSlot; }
 177
 178 private:
 179         inline PyrObject * Allocate(size_t inNumBytes, int32 sizeclass, bool inCollect);
 180         static void throwMemfailed(size_t inNumBytes);
 181
 182         void ScanSlots(PyrSlot *inSlots, long inNumToScan);
 183         void SweepBigObjects();
 184         void DoPartialScan(int32 inObjSize);
 185         bool ScanOneObj();
 186         void Flip();
 187         void ScanStack();
 188         void ScanFrames();
 189         void DLRemove(PyrObjectHdr *obj);
 190         void DLInsertAfter(PyrObjectHdr *after, PyrObjectHdr *obj);
 191         void DLInsertBefore(PyrObjectHdr *before, PyrObjectHdr *obj);
 192
 193         void ClearMarks();
 194         void Finalize(PyrObject *obj);
 195
 196         void beginPause();
 197         void endPause();
 198         void reportPause();
 199
 200         VMGlobals *mVMGlobals;
 201         AllocPool *mPool;
 202         AdvancingAllocPool mNewPool;
 203         GCSet mSets[kNumGCSets];
 204         PyrProcess *mProcess; // the root is the pyrprocess which contains this struct
 205         PyrObject *mStack;
 206         PyrObject *mPartialScanObj;
 207         PyrObjectHdr mGrey;
 208
 209         int32 mPartialScanSlot;
 210         int32 mNumToScan;
 211         int32 mNumGrey;
 212         int32 mCurSet;
 213
 214         int32 mFlips, mCollects, mAllocTotal, mScans, mNumAllocs, mStackScans, mNumPartialScans, mSlotsScanned, mUncollectedAllocations;
 215
 216         unsigned char mBlackColor, mGreyColor, mWhiteColor, mFreeColor;
 217         bool mCanSweep;
 218         bool mRunning;
 219 };
 220
 221 inline void PyrGC::DLRemove(PyrObjectHdr *obj)
 222 {
 223         obj->next->prev = obj->prev;
 224         obj->prev->next = obj->next;
 225 }
 226
 227 inline void PyrGC::DLInsertAfter(PyrObjectHdr *after, PyrObjectHdr *obj)
 228 {
 229         obj->next = after->next;
 230         obj->prev = after;
 231         after->next->prev = obj;
 232         after->next = obj;
 233 }
 234
 235 inline void PyrGC::DLInsertBefore(PyrObjectHdr *before, PyrObjectHdr *obj)
 236 {
 237         obj->prev = before->prev;
 238         obj->next = before;
 239         before->prev->next = obj;
 240         before->prev = obj;
 241 }
 242
 243 inline GCSet* PyrGC::GetGCSet(PyrObjectHdr* inObj)
 244 {
 245         return mSets + (inObj->classptr == class_finalizer ? kFinalizerSet : inObj->obj_sizeclass);
 246 }
 247
 248 inline void PyrGC::ToBlack(PyrObjectHdr *obj)
 249 {
 250         if (IsGrey(obj)) {
 251                 mNumGrey--;
 252                 //post("ToBlack %d\n", mNumGrey);
 253         }
 254
 255         DLRemove(obj);
 256
 257         GCSet *gcs = GetGCSet(obj);
 258         DLInsertAfter(&gcs->mBlack, obj);
 259
 260         obj->gc_color = mBlackColor;
 261 }
 262
 263 inline void PyrGC::ToWhite(PyrObjectHdr *obj)
 264 {
 265         if (IsGrey(obj)) {
 266                 mNumGrey--;
 267                 //post("ToWhite %d\n", mNumGrey);
 268         }
 269
 270         DLRemove(obj);
 271
 272         GCSet *gcs = GetGCSet(obj);
 273         DLInsertAfter(&gcs->mWhite, obj);
 274
 275         obj->gc_color = mWhiteColor;
 276 }
 277
 278 inline void PyrGC::Free(PyrObjectHdr* obj)
 279 {
 280         if (IsGrey(obj)) {
 281                 mNumGrey--;
 282                 //post("ToWhite %d\n", mNumGrey);
 283         }
 284
 285         DLRemove(obj);
 286
 287         GCSet *gcs = GetGCSet(obj);
 288         DLInsertBefore(gcs->mFree, obj);
 289         gcs->mFree = obj;
 290
 291         obj->gc_color = mFreeColor;
 292         obj->size = 0;
 293 }
 294
 295 inline void PyrGC::ToGrey(PyrObjectHdr* obj)
 296 {
 297         /* move obj from white to grey */
 298         /* link around object */
 299         DLRemove(obj);
 300
 301         /* link in new place */
 302         DLInsertAfter(&mGrey, obj);
 303
 304         /* set grey list pointer to obj */
 305         obj->gc_color = mGreyColor;
 306         mNumGrey ++ ;
 307         mNumToScan += 1L << obj->obj_sizeclass;
 308 }
 309
 310 inline void PyrGC::ToGrey2(PyrObjectHdr* obj)
 311 {
 312         /* move obj from white to grey */
 313         /* link around object */
 314         DLRemove(obj);
 315
 316         /* link in new place */
 317         DLInsertAfter(&mGrey, obj);
 318
 319         /* set grey list pointer to obj */
 320         obj->gc_color = mGreyColor;
 321         mNumGrey ++ ;
 322 }
 323
 324 inline PyrObject * PyrGC::Allocate(size_t inNumBytes, int32 sizeclass, bool inCollect)
 325 {
 326         if (inCollect && mNumToScan >= kScanThreshold)
 327                 Collect();
 328         else {
 329                 if (inCollect)
 330                         mUncollectedAllocations = 0;
 331                 else
 332                         ++mUncollectedAllocations;
 333         }
 334
 335         GCSet *gcs = mSets + sizeclass;
 336
 337         PyrObject * obj = (PyrObject*)gcs->mFree;
 338         if (!IsMarker(obj)) {
 339                 // from free list
 340                 gcs->mFree = obj->next;
 341                 assert(obj->obj_sizeclass == sizeclass);
 342         } else {
 343                 if (sizeclass > kMaxPoolSet) {
 344                         SweepBigObjects();
 345                         int32 allocSize = sizeof(PyrObjectHdr) + (sizeof(PyrSlot) << sizeclass);
 346                         obj = (PyrObject*)mPool->Alloc(allocSize);
 347                 } else {
 348                         int32 allocSize = sizeof(PyrObjectHdr) + (sizeof(PyrSlot) << sizeclass);
 349                         obj = (PyrObject*)mNewPool.Alloc(allocSize);
 350                 }
 351                 if (!obj)
 352                         throwMemfailed(inNumBytes);
 353                 DLInsertAfter(&gcs->mWhite, obj);
 354                 obj->obj_sizeclass = sizeclass;
 355         }
 356         return obj;
 357 }
 358
 359 #endif