1 /* 2 Title: memmgr.h Memory segment manager 3 4 Copyright (c) 2006-8, 2010-12, 2016-18, 2020 David C. J. Matthews 5 6 This library is free software; you can redistribute it and/or 7 modify it under the terms of the GNU Lesser General Public 8 License version 2.1 as published by the Free Software Foundation. 9 10 This library is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 Lesser General Public License for more details. 14 15 You should have received a copy of the GNU Lesser General Public 16 License along with this library; if not, write to the Free Software 17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 18 19 */ 20 21 #ifndef MEMMGR_H 22 #define MEMMGR_H 23 24 #include "bitmap.h" 25 #include "locking.h" 26 #include "osmem.h" 27 #include <vector> 28 29 // utility conversion macros 30 #define Words_to_K(w) (w*sizeof(PolyWord))/1024 31 #define Words_to_M(w) (w*sizeof(PolyWord))/(1<<20) 32 #define B_to_M(b) (b/(1<<20)) 33 34 class ScanAddress; 35 class GCTaskId; 36 class TaskData; 37 38 typedef enum { 39 ST_PERMANENT, // Permanent areas are part of the object code 40 // Also loaded saved state. 41 ST_LOCAL, // Local heaps contain volatile data 42 ST_EXPORT, // Temporary export area 43 ST_STACK, // ML Stack for a thread 44 ST_CODE // Code created in the current run 45 } SpaceType; 46 47 48 // B-tree used in SpaceForAddress. Leaves are MemSpaces. 49 class SpaceTree 50 { 51 public: SpaceTree(bool is)52 SpaceTree(bool is): isSpace(is) { } ~SpaceTree()53 virtual ~SpaceTree() {} 54 55 bool isSpace; 56 }; 57 58 // A non-leaf node in the B-tree 59 class SpaceTreeTree: public SpaceTree 60 { 61 public: 62 SpaceTreeTree(); 63 virtual ~SpaceTreeTree(); 64 65 SpaceTree *tree[256]; 66 }; 67 68 // Base class for the various memory spaces. 69 class MemSpace: public SpaceTree 70 { 71 protected: 72 MemSpace(OSMem *alloc); 73 virtual ~MemSpace(); 74 75 public: 76 SpaceType spaceType; 77 bool isMutable; 78 bool isCode; 79 80 PolyWord *bottom; // Bottom of area 81 PolyWord *top; // Top of area. 82 OSMem *allocator; // Used to free the area. May be null. 83 84 PolyWord *shadowSpace; // Extra writable area for code if necessary 85 spaceSize(void)86 uintptr_t spaceSize(void)const { return top-bottom; } // No of words 87 88 // These next two are used in the GC to limit scanning for 89 // weak refs. 90 PolyWord *lowestWeak, *highestWeak; 91 92 // Used when printing debugging info spaceTypeString()93 virtual const char *spaceTypeString() { return isMutable ? "mutable" : "immutable"; } 94 95 // Return the writeable address if this is in read-only code. writeAble(byte * p)96 byte* writeAble(byte* p) { 97 if (shadowSpace != 0) 98 return (p - (byte*)bottom + (byte*)shadowSpace); 99 else return p; 100 } 101 writeAble(PolyWord * p)102 PolyWord* writeAble(PolyWord* p) { 103 if (shadowSpace != 0) 104 return (p - bottom + shadowSpace); 105 else return p; 106 } 107 writeAble(PolyObject * p)108 PolyObject* writeAble(PolyObject* p) { 109 return (PolyObject*)writeAble((PolyWord *) p); 110 } 111 112 friend class MemMgr; 113 }; 114 115 // Permanent memory space. Either linked into the executable program or 116 // loaded from a saved state file. 117 class PermanentMemSpace: public MemSpace 118 { 119 protected: PermanentMemSpace(OSMem * alloc)120 PermanentMemSpace(OSMem *alloc): MemSpace(alloc), index(0), hierarchy(0), noOverwrite(false), 121 byteOnly(false), topPointer(0) {} 122 123 public: 124 unsigned index; // An identifier for the space. Used when saving and loading. 125 unsigned hierarchy; // The hierarchy number: 0=from executable, 1=top level saved state, ... 126 bool noOverwrite; // Don't save this in deeper hierarchies. 127 bool byteOnly; // Only contains byte data - no need to scan for addresses. 128 129 // When exporting or saving state we copy data into a new area. 130 // This area grows upwards unlike the local areas that grow down. 131 PolyWord *topPointer; 132 133 Bitmap shareBitmap; // Used in sharedata 134 Bitmap profileCode; // Used when profiling 135 136 friend class MemMgr; 137 }; 138 139 #define NSTARTS 10 140 141 // Markable spaces are used as the base class for local heap 142 // spaces and code spaces. 143 class MarkableSpace: public MemSpace 144 { 145 protected: 146 MarkableSpace(OSMem *alloc); ~MarkableSpace()147 virtual ~MarkableSpace() {} 148 public: 149 PolyWord *fullGCRescanStart; // Upper and lower limits for rescan during mark phase. 150 PolyWord *fullGCRescanEnd; 151 PLock spaceLock; // Lock used to protect forwarding pointers 152 }; 153 154 // Local areas can be garbage collected. 155 class LocalMemSpace: public MarkableSpace 156 { 157 protected: 158 LocalMemSpace(OSMem *alloc); ~LocalMemSpace()159 virtual ~LocalMemSpace() {} 160 bool InitSpace(PolyWord *heapPtr, uintptr_t size, bool mut); 161 162 public: 163 // Allocation. The minor GC allocates at the bottom of the areas while the 164 // major GC and initial allocations are made at the top. The reason for this 165 // is that it's only possible to scan objects from the bottom up and the minor 166 // GC combines scanning with allocation whereas the major GC compacts from the 167 // bottom into the top of an area. 168 PolyWord *upperAllocPtr; // Allocation pointer. Objects are allocated AFTER this. 169 PolyWord *lowerAllocPtr; // Allocation pointer. Objects are allocated BEFORE this. 170 171 PolyWord *fullGCLowerLimit;// Lowest object in area before copying. 172 PolyWord *partialGCTop; // Value of upperAllocPtr before the current partial GC. 173 PolyWord *partialGCScan; // Scan pointer used in minor GC 174 PolyWord *partialGCRootBase; // Start of the root objects. 175 PolyWord *partialGCRootTop;// Value of lowerAllocPtr after the roots have been copied. 176 GCTaskId *spaceOwner; // The thread that "owns" this space during a GC. 177 178 Bitmap bitmap; /* bitmap with one bit for each word in the GC area. */ 179 PLock bitmapLock; // Lock used in GC sharing pass. 180 bool allocationSpace; // True if this is (mutable) space for initial allocation 181 uintptr_t start[NSTARTS]; /* starting points for bit searches. */ 182 unsigned start_index; /* last index used to index start array */ 183 uintptr_t i_marked; /* count of immutable words marked. */ 184 uintptr_t m_marked; /* count of mutable words marked. */ 185 uintptr_t updated; /* count of words updated. */ 186 allocatedSpace(void)187 uintptr_t allocatedSpace(void)const // Words allocated 188 { return (top-upperAllocPtr) + (lowerAllocPtr-bottom); } freeSpace(void)189 uintptr_t freeSpace(void)const // Words free 190 { return upperAllocPtr-lowerAllocPtr; } 191 192 #ifdef POLYML32IN64 193 // We will generally set a zero cell for alignment. isEmpty(void)194 bool isEmpty(void)const { return allocatedSpace() <= 1; } 195 #else isEmpty(void)196 bool isEmpty(void)const { return allocatedSpace() == 0; } 197 #endif 198 spaceTypeString()199 virtual const char *spaceTypeString() 200 { return allocationSpace ? "allocation" : MemSpace::spaceTypeString(); } 201 202 // Used when converting to and from bit positions in the bitmap wordNo(PolyWord * pt)203 uintptr_t wordNo(PolyWord *pt) { return pt - bottom; } wordAddr(uintptr_t bitno)204 PolyWord *wordAddr(uintptr_t bitno) { return bottom + bitno; } 205 206 friend class MemMgr; 207 }; 208 209 class StackObject; // Abstract - Architecture specific 210 211 // Stack spaces. These are managed by the thread module 212 class StackSpace: public MemSpace 213 { 214 public: StackSpace(OSMem * alloc)215 StackSpace(OSMem *alloc): MemSpace(alloc) { } 216 stack()217 StackObject *stack()const { return (StackObject *)bottom; } 218 }; 219 220 // Code Space. These contain local code created by the compiler. 221 class CodeSpace: public MarkableSpace 222 { 223 public: 224 CodeSpace(PolyWord *start, PolyWord *shadow, uintptr_t spaceSize, OSMem *alloc); 225 226 Bitmap headerMap; // Map to find the headers during GC or profiling. 227 uintptr_t largestFree; // The largest free space in the area 228 PolyWord *firstFree; // The start of the first free space in the area. 229 }; 230 231 class MemMgr 232 { 233 public: 234 MemMgr(); 235 ~MemMgr(); 236 bool Initialise(); 237 238 // Create a local space for initial allocation. 239 LocalMemSpace *CreateAllocationSpace(uintptr_t size); 240 // Create and initialise a new local space and add it to the table. 241 LocalMemSpace *NewLocalSpace(uintptr_t size, bool mut); 242 // Create an entry for a permanent space. 243 PermanentMemSpace *NewPermanentSpace(PolyWord *base, uintptr_t words, 244 unsigned flags, unsigned index, unsigned hierarchy = 0); 245 246 // Create a permanent space but allocate memory for it. 247 // Sets bottom and top to the actual memory size. 248 PermanentMemSpace *AllocateNewPermanentSpace(uintptr_t byteSize, unsigned flags, 249 unsigned index, unsigned hierarchy = 0); 250 // Called after an allocated permanent area has been filled in. 251 bool CompletePermanentSpaceAllocation(PermanentMemSpace *space); 252 253 // Delete a local space. Takes the iterator position in lSpaces and returns the 254 // iterator after deletion. 255 void DeleteLocalSpace(std::vector<LocalMemSpace*>::iterator &iter); 256 257 // Allocate an area of the heap of at least minWords and at most maxWords. 258 // This is used both when allocating single objects (when minWords and maxWords 259 // are the same) and when allocating heap segments. If there is insufficient 260 // space to satisfy the minimum it will return 0. Updates "maxWords" with 261 // the space actually allocated 262 PolyWord *AllocHeapSpace(uintptr_t minWords, uintptr_t &maxWords, bool doAllocation = true); AllocHeapSpace(uintptr_t words)263 PolyWord *AllocHeapSpace(uintptr_t words) 264 { uintptr_t allocated = words; return AllocHeapSpace(words, allocated); } 265 266 CodeSpace *NewCodeSpace(uintptr_t size); 267 // Allocate space for code. This is initially mutable to allow the code to be built. 268 PolyObject *AllocCodeSpace(POLYUNSIGNED size); 269 270 // Check that a subsequent allocation will succeed. Called from the GC to ensure 271 bool CheckForAllocation(uintptr_t words); 272 273 // If an allocation space has a lot of data left in it, particularly a single 274 // large object we should turn it into a local area. 275 void ConvertAllocationSpaceToLocal(LocalMemSpace *space); 276 277 // Allocate space for the initial stack for a thread. The caller must 278 // initialise the new stack. Returns 0 if allocation fails. 279 StackSpace *NewStackSpace(uintptr_t size); 280 281 // Adjust the space for a stack. Returns true if it succeeded. If it failed 282 // it leaves the stack untouched. 283 bool GrowOrShrinkStack(TaskData *taskData, uintptr_t newSize); 284 285 // Delete a stack when a thread has finished. 286 bool DeleteStackSpace(StackSpace *space); 287 288 // Create and delete export spaces 289 PermanentMemSpace *NewExportSpace(uintptr_t size, bool mut, bool noOv, bool code); 290 void DeleteExportSpaces(void); 291 bool PromoteExportSpaces(unsigned hierarchy); // Turn export spaces into permanent spaces. 292 bool DemoteImportSpaces(void); // Turn previously imported spaces into local. 293 294 PermanentMemSpace *SpaceForIndex(unsigned index); // Return the space for a given index 295 296 // As a debugging check, write protect the immutable areas apart from during the GC. 297 void ProtectImmutable(bool on); 298 299 // Find a space that contains a given address. This is called for every cell 300 // during a GC so needs to be fast., 301 // N.B. This must be called on an address at the beginning or within the cell. 302 // Generally that means with a pointer to the length word. Pointing at the 303 // first "data" word may give the wrong result if the length is zero. SpaceForAddress(const void * pt)304 MemSpace *SpaceForAddress(const void *pt) const 305 { 306 uintptr_t t = (uintptr_t)pt; 307 SpaceTree *tr = spaceTree; 308 309 // Each level of the tree is either a leaf or a vector of trees. 310 unsigned j = sizeof(void *)*8; 311 for (;;) 312 { 313 if (tr == 0 || tr->isSpace) 314 return (MemSpace*)tr; 315 j -= 8; 316 tr = ((SpaceTreeTree*)tr)->tree[(t >> j) & 0xff]; 317 } 318 return 0; 319 } 320 321 // SpaceForAddress must NOT be applied to a PolyObject *. That's because 322 // it works nearly all the time except when a zero-sized object is placed 323 // at the end of page. Then the base address will be the start of the 324 // next page. SpaceForAddress(PolyObject * pt)325 void SpaceForAddress(PolyObject *pt) {} 326 327 // Use this instead. SpaceForObjectAddress(PolyObject * pt)328 MemSpace* SpaceForObjectAddress(PolyObject* pt) 329 { return SpaceForAddress(((PolyWord*)pt) - 1); } 330 331 // Find a local address for a space. 332 // N.B. The argument should generally be the length word. See 333 // comment on SpaceForAddress. LocalSpaceForAddress(const void * pt)334 LocalMemSpace *LocalSpaceForAddress(const void *pt) const 335 { 336 MemSpace *s = SpaceForAddress(pt); 337 if (s != 0 && s->spaceType == ST_LOCAL) 338 return (LocalMemSpace*)s; 339 else return 0; 340 } 341 342 // LocalSpaceForAddress must NOT be applied to PolyObject*. 343 // See comment on SpaceForAddress above. LocalSpaceForAddress(PolyObject * pt)344 void LocalSpaceForAddress(PolyObject* pt) {} 345 LocalSpaceForObjectAddress(PolyObject * pt)346 LocalMemSpace* LocalSpaceForObjectAddress(PolyObject* pt) 347 { return LocalSpaceForAddress(((PolyWord*)pt) - 1); } 348 SetReservation(uintptr_t words)349 void SetReservation(uintptr_t words) { reservedSpace = words; } 350 351 // In several places we assume that segments are filled with valid 352 // objects. This fills unused memory with one or more "byte" objects. 353 void FillUnusedSpace(PolyWord *base, uintptr_t words); 354 355 // Return number of words of free space for stats. 356 uintptr_t GetFreeAllocSpace(); 357 358 // Remove unused local areas. 359 void RemoveEmptyLocals(); 360 // Remove unused code areas. 361 void RemoveEmptyCodeAreas(); 362 363 // Remove unused allocation areas to reduce the space below the limit. 364 void RemoveExcessAllocation(uintptr_t words); RemoveExcessAllocation()365 void RemoveExcessAllocation() { RemoveExcessAllocation(spaceBeforeMinorGC); } 366 367 // Table for permanent spaces 368 std::vector<PermanentMemSpace *> pSpaces; 369 370 // Table for local spaces 371 std::vector<LocalMemSpace *> lSpaces; 372 373 // Table for export spaces 374 std::vector<PermanentMemSpace *> eSpaces; 375 376 // Table for stack spaces 377 std::vector<StackSpace *> sSpaces; 378 PLock stackSpaceLock; 379 380 // Table for code spaces 381 std::vector<CodeSpace *> cSpaces; 382 PLock codeSpaceLock; 383 384 // Storage manager lock. 385 PLock allocLock; 386 387 // Lock for creating new bitmaps for code profiling 388 PLock codeBitmapLock; 389 390 unsigned nextIndex; // Used when allocating new permanent spaces. 391 SpaceBeforeMinorGC()392 uintptr_t SpaceBeforeMinorGC() const { return spaceBeforeMinorGC; } SpaceForHeap()393 uintptr_t SpaceForHeap() const { return spaceForHeap; } SetSpaceBeforeMinorGC(uintptr_t minorSize)394 void SetSpaceBeforeMinorGC(uintptr_t minorSize) { spaceBeforeMinorGC = minorSize; } SetSpaceForHeap(uintptr_t heapSize)395 void SetSpaceForHeap(uintptr_t heapSize) { spaceForHeap = heapSize; } 396 CurrentAllocSpace()397 uintptr_t CurrentAllocSpace() { return currentAllocSpace; } 398 uintptr_t AllocatedInAlloc(); CurrentHeapSize()399 uintptr_t CurrentHeapSize() { return currentHeapSize; } 400 DefaultSpaceSize()401 uintptr_t DefaultSpaceSize() const { return defaultSpaceSize; } 402 403 void ReportHeapSizes(const char *phase); 404 405 // Profiling - Find a code object or return zero if not found. 406 PolyObject *FindCodeObject(const byte *addr); 407 // Profiling - Free bitmaps to indicate start of an object. 408 void RemoveProfilingBitmaps(); 409 410 private: 411 bool AddLocalSpace(LocalMemSpace *space); 412 bool AddCodeSpace(CodeSpace *space); 413 414 uintptr_t reservedSpace; 415 unsigned nextAllocator; 416 // The default size in words when creating new segments. 417 uintptr_t defaultSpaceSize; 418 // The number of words that can be used for initial allocation. 419 uintptr_t spaceBeforeMinorGC; 420 // The number of words that can be used for the heap 421 uintptr_t spaceForHeap; 422 // The current sizes of the allocation space and the total heap size. 423 uintptr_t currentAllocSpace, currentHeapSize; 424 // LocalSpaceForAddress is a hot-spot so we use a B-tree to convert addresses; 425 SpaceTree *spaceTree; 426 PLock spaceTreeLock; AddTree(MemSpace * space)427 void AddTree(MemSpace *space) { AddTree(space, space->bottom, space->top); } RemoveTree(MemSpace * space)428 void RemoveTree(MemSpace *space) { RemoveTree(space, space->bottom, space->top); } 429 void AddTree(MemSpace *space, PolyWord *startS, PolyWord *endS); 430 void RemoveTree(MemSpace *space, PolyWord *startS, PolyWord *endS); 431 432 void AddTreeRange(SpaceTree **t, MemSpace *space, uintptr_t startS, uintptr_t endS); 433 void RemoveTreeRange(SpaceTree **t, MemSpace *space, uintptr_t startS, uintptr_t endS); 434 435 OSMem osHeapAlloc, osStackAlloc, osCodeAlloc; 436 }; 437 438 extern MemMgr gMem; 439 440 #endif 441