include/common/SC_AllocPool.h

   1
   2 /*
   3         SuperCollider real time audio synthesis system
   4     Copyright (c) 2002 James McCartney. All rights reserved.
   5         http://www.audiosynth.com
   6
   7     This program is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     This program is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with this program; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  20 */
  21 /*
  22 This is based on Doug Lea's allocator but rewritten so I can read and understand it...
  23 also features of free all-at-once pools are added.
  24 Now uses 16 byte alignment, which does increase the minimum allocation size to 32 bytes
  25 including the overhead.
  26 Improved bit block scanning by using a count leading zeroes instruction.
  27
  28 */
  29
  30 #ifndef _AllocPool_
  31 #define _AllocPool_
  32
  33 #include "SC_List.h"
  34 #include "clz.h"
  35 #include <stdlib.h>
  36
  37 const int kNumAllocBins = 128;
  38 const int kNumSmallBins = 64;
  39 const int kMaxSmallBin = kNumSmallBins - 1;
  40 const int kBinWidth = 8;
  41 const int kMaxSmallBinSize = kNumSmallBins * kBinWidth;
  42 const int kBinBlockWidth = 4;
  43 const int kBinBlockMask = kBinBlockWidth - 1;
  44
  45 const size_t kAlign = 64;
  46 const size_t kAlignMask = kAlign - 1;
  47 const size_t kChunkFree = 0;
  48 const size_t kChunkInUse = 1;
  49 const size_t kSizeBits = ~kChunkInUse;
  50
  51 class AllocChunk;
  52 class AllocPool;
  53 typedef AllocChunk *AllocChunkPtr;
  54 typedef Link<AllocChunk> AllocBin;
  55 typedef AllocBin* AllocBinPtr;
  56
  57 class AllocChunk : public Link<AllocChunk>
  58 {
  59         friend class AllocPool;
  60
  61         size_t Size()
  62                 { return mSize & kSizeBits; }
  63
  64         size_t PrevSize()
  65                 { return mPrevSize & kSizeBits; }
  66
  67         AllocChunkPtr ChunkAtOffset(long inSize)
  68                 { return AllocChunkPtr((char*)this + inSize); }
  69
  70         AllocChunkPtr NextChunk()
  71                 { return ChunkAtOffset(Size()); }
  72
  73         AllocChunkPtr PrevChunk()
  74                 { return ChunkAtOffset(-(long)PrevSize()); }
  75
  76         bool InUse()
  77                 { return (bool)(mSize & kChunkInUse); }
  78
  79         bool PrevInUse()
  80                 { return (bool)(mPrevSize & kChunkInUse); }
  81
  82         void SetSizeFree(size_t inSize)
  83                 { mSize = ChunkAtOffset(inSize)->mPrevSize = inSize; }
  84
  85         void SetSizeInUse(size_t inSize)
  86                 { mSize = ChunkAtOffset(inSize)->mPrevSize = inSize | kChunkInUse; }
  87
  88         void SetNeighborsInUse(size_t inOffset)
  89                 { mPrevSize = ChunkAtOffset(inOffset)->mSize = kChunkInUse; }
  90
  91         bool IsArea()
  92                 { return mPrevSize == kChunkInUse && NextChunk()->mSize == kChunkInUse; }
  93
  94         void* ToPtr()
  95                 { return (void*)((char*)this + sizeof(AllocChunk)); }
  96
  97         size_t mPrevSize;
  98         size_t mSize;
  99 };
 100
 101 class AllocArea;
 102 typedef AllocArea* AllocAreaPtr;
 103
 104 class AllocAreaHdr /* for size calculations */
 105 {
 106 protected:
 107         friend class AllocPool;
 108
 109         AllocAreaPtr mPrev, mNext;
 110         size_t mSize;
 111         void *mUnalignedPointerToThis;
 112 };
 113
 114 class AllocArea : public AllocAreaHdr
 115 {
 116 public:
 117         void SanityCheck();
 118
 119 private:
 120         friend class AllocPool;
 121
 122         AllocChunk mChunk;
 123 };
 124
 125 const size_t kMinAllocSize = 2 * kAlign;
 126 const size_t kAreaOverhead = sizeof(AllocAreaHdr) + 2 * sizeof(AllocChunk) + kAlign;
 127
 128 typedef void* (*NewAreaFunc)(size_t size);
 129 typedef void (*FreeAreaFunc)(void *);
 130
 131 class AllocPool
 132 {
 133 public:
 134         AllocPool(NewAreaFunc allocArea, FreeAreaFunc freeArea,
 135                                         size_t areaInitSize, size_t areaMoreSize);
 136         ~AllocPool();
 137
 138         void Reinit();
 139
 140         void *Alloc(size_t inBytes);
 141         void *Realloc(void* inPtr, size_t inBytes);
 142         void Free(void* inPtr);
 143         void FreeAll();
 144         void FreeAllInternal();
 145
 146         // debugging
 147         size_t TotalFree();
 148         size_t LargestFreeChunk();
 149
 150         void DoCheckPool();
 151         void DoCheckInUseChunk(AllocChunkPtr p);
 152
 153         static AllocChunkPtr MemToChunk(void *inPtr)
 154                 { return (AllocChunkPtr)((char*)(inPtr) - sizeof(AllocChunk)); }
 155
 156 private:
 157         void InitAlloc();
 158         void InitBins();
 159         AllocAreaPtr NewArea(size_t inAreaSize);
 160         void FreeArea(AllocChunkPtr chunk);
 161
 162         // debugging
 163         void DoCheckArea(AllocAreaPtr area);
 164         void DoCheckBin(AllocChunkPtr bin, long idx);
 165         void DoCheckChunk(AllocChunkPtr p);
 166         void DoCheckFreeChunk(AllocChunkPtr p);
 167         void DoCheckAllocedChunk(AllocChunkPtr p, size_t s);
 168         void DoGarbageFill(AllocChunkPtr p);
 169         void DoGarbageFill(AllocChunkPtr p, long size);
 170
 171         // inlines
 172
 173         static size_t RequestToSize(size_t inReqSize)
 174         {
 175                 size_t sizePlusOverhead = inReqSize + sizeof(AllocChunk);
 176                 if (sizePlusOverhead <= kMinAllocSize) return kMinAllocSize;
 177                 else return (sizePlusOverhead + kAlignMask) & ~kAlignMask;
 178         }
 179
 180         static int SmallBinIndex(size_t inSize)
 181                 { return inSize >> 4; }
 182
 183         static int BinIndex2(size_t inSize)
 184         {
 185                 return
 186                 ((inSize <   1024) ?       (inSize>>4):
 187                  (inSize <   2048) ?  56 + (inSize>>7):
 188                  (inSize <   4096) ?  64 + (inSize>>8):
 189                  (inSize <   8192) ?  72 + (inSize>>9):
 190                  (inSize <  16384) ?  80 + (inSize>>10):
 191                  (inSize <  32768) ?  88 + (inSize>>11):
 192                  (inSize <  65536) ?  96 + (inSize>>12):
 193                  (inSize < 131072) ? 104 + (inSize>>13):
 194                  (inSize < 262144) ? 112 + (inSize>>14):127);
 195         }
 196
 197         static int BinIndex(size_t inSize)
 198         {
 199                 if (inSize < 1024) return inSize >> 4;
 200                 if (inSize >= 262144) return 127;
 201                 int bits = 28 - CLZ(inSize);
 202                 return (bits << 3) + (inSize >> bits) ;
 203         }
 204
 205         void MarkBinBlock(int inIndex)
 206                 {
 207                         unsigned long word = inIndex >> 5;
 208                         unsigned long bitPosition = inIndex & 31;
 209                         unsigned long bitValue = 1L << bitPosition;
 210                         mBinBlocks[word] |= bitValue;
 211                 }
 212
 213         void ClearBinBlock(int inIndex)
 214                 {
 215                         unsigned long word = inIndex >> 5;
 216                         unsigned long bitPosition = inIndex & 31;
 217                         unsigned long bitValue = 1L << bitPosition;
 218                         mBinBlocks[word] &= ~bitValue;
 219                 }
 220
 221         int NextFullBin(int inStartingBinIndex)
 222                 {
 223                         if (inStartingBinIndex >= 128) return -1;
 224                         int word = inStartingBinIndex >> 5;
 225                         int bitPosition = inStartingBinIndex & 31;
 226                         unsigned long bitValue = 1L << bitPosition;
 227                         unsigned long binBits = mBinBlocks[word];
 228
 229                         if (binBits >= bitValue) {
 230                                 binBits = (~(bitValue - 1) & binBits);
 231                         } else {
 232                                 for (++word; word<4 && !mBinBlocks[word]; ++word) {}
 233                                 if (word==4) return -1;
 234                                 binBits = mBinBlocks[word];
 235                         }
 236                         bitPosition = CTZ((int32)binBits);
 237
 238                         return (word << 5) + bitPosition;
 239                 }
 240
 241         void LinkFree(AllocChunkPtr inChunk);
 242         /*
 243                 {
 244                         size_t size = inChunk->Size();
 245                         int index = BinIndex(size);
 246
 247                         AllocChunkPtr bin = mBins + index;
 248
 249                         if (index < kNumSmallBins || bin->IsEmpty()) {
 250                                 inChunk->InsertAfter(bin);
 251                                 MarkBinBlock(index);
 252                         } else {
 253                                 AllocChunkPtr link = bin->Next();
 254                                 while (link != bin && size < link->Size()) link = link->Next();
 255                                 inChunk->InsertBefore(link);
 256                         }
 257                 }
 258         */
 259
 260         void UnlinkFree(AllocChunkPtr inChunk)
 261                 {
 262                         inChunk->RemoveLeaveDangling();
 263                         size_t size = inChunk->Size();
 264                         int index = BinIndex(size);
 265                         AllocChunkPtr bin = mBins + index;
 266                         if (bin->IsEmpty()) ClearBinBlock(index);
 267                 }
 268
 269         AllocChunk mBins[kNumAllocBins];
 270         AllocAreaPtr mAreas;
 271         NewAreaFunc mAllocArea;
 272         FreeAreaFunc mFreeArea;
 273         size_t mAreaInitSize, mAreaMoreSize;
 274         unsigned long mBinBlocks[4];
 275 };
 276
 277 #endif