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