1/* 2 Title: memmgr.cpp Memory segment manager 3 4 Copyright (c) 2006-7, 2011-12, 2016-17 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#ifdef HAVE_CONFIG_H 21#include "config.h" 22#elif defined(_WIN32) 23#include "winconfig.h" 24#else 25#error "No configuration file" 26#endif 27 28#ifdef HAVE_ASSERT_H 29#include <assert.h> 30#define ASSERT(x) assert(x) 31#else 32#define ASSERT(x) 33#endif 34 35#include <new> 36 37#include "globals.h" 38#include "memmgr.h" 39#include "osmem.h" 40#include "scanaddrs.h" 41#include "bitmap.h" 42#include "mpoly.h" 43#include "diagnostics.h" 44#include "statistics.h" 45#include "processes.h" 46 47// heap resizing policy option requested on command line 48unsigned heapsizingOption = 0; 49 50MemSpace::MemSpace(): SpaceTree(true) 51{ 52 spaceType = ST_PERMANENT; 53 isMutable = false; 54 bottom = 0; 55 top = 0; 56 isOwnSpace = false; 57 isCode = false; 58} 59 60MemSpace::~MemSpace() 61{ 62 if (isOwnSpace && bottom != 0) 63 osMemoryManager->Free(bottom, (char*)top - (char*)bottom); 64} 65 66MarkableSpace::MarkableSpace(): spaceLock("Local space") 67{ 68} 69 70LocalMemSpace::LocalMemSpace() 71{ 72 spaceType = ST_LOCAL; 73 upperAllocPtr = lowerAllocPtr = 0; 74 for (unsigned i = 0; i < NSTARTS; i++) 75 start[i] = 0; 76 start_index = 0; 77 i_marked = m_marked = updated = 0; 78 allocationSpace = false; 79} 80 81bool LocalMemSpace::InitSpace(POLYUNSIGNED size, bool mut) 82{ 83 isMutable = mut; 84 85 // Allocate the heap itself. 86 size_t iSpace = size*sizeof(PolyWord); 87 bottom = 88 (PolyWord*)osMemoryManager->Allocate(iSpace, PERMISSION_READ|PERMISSION_WRITE); 89 90 if (bottom == 0) 91 return false; 92 isOwnSpace = true; // Deallocate when we're finished. 93 94 // The size may have been rounded up to a block boundary. 95 size = iSpace/sizeof(PolyWord); 96 97 top = bottom + size; 98 // Initialise all the fields. The partial GC in particular relies on this. 99 upperAllocPtr = partialGCTop = fullGCRescanStart = fullGCLowerLimit = lowestWeak = top; 100 lowerAllocPtr = partialGCScan = partialGCRootBase = partialGCRootTop = 101 fullGCRescanEnd = highestWeak = bottom; 102 spaceOwner = 0; 103 104 allocationSpace = false; 105 106 // Bitmap for the space. 107 return bitmap.Create(size); 108} 109 110MemMgr::MemMgr(): allocLock("Memmgr alloc"), codeBitmapLock("Code bitmap") 111{ 112 nextIndex = 0; 113 reservedSpace = 0; 114 nextAllocator = 0; 115 defaultSpaceSize = 0; 116 spaceBeforeMinorGC = 0; 117 spaceForHeap = 0; 118 currentAllocSpace = currentHeapSize = 0; 119 defaultSpaceSize = 1024 * 1024 / sizeof(PolyWord); // 1Mbyte segments. 120 spaceTree = new SpaceTreeTree; 121} 122 123MemMgr::~MemMgr() 124{ 125 delete(spaceTree); // Have to do this before we delete the spaces. 126 for (std::vector<PermanentMemSpace *>::iterator i = pSpaces.begin(); i < pSpaces.end(); i++) 127 delete(*i); 128 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); i++) 129 delete(*i); 130 for (std::vector<PermanentMemSpace *>::iterator i = eSpaces.begin(); i < eSpaces.end(); i++) 131 delete(*i); 132 for (std::vector<StackSpace *>::iterator i = sSpaces.begin(); i < sSpaces.end(); i++) 133 delete(*i); 134 for (std::vector<CodeSpace *>::iterator i = cSpaces.begin(); i < cSpaces.end(); i++) 135 delete(*i); 136} 137 138// Create and initialise a new local space and add it to the table. 139LocalMemSpace* MemMgr::NewLocalSpace(POLYUNSIGNED size, bool mut) 140{ 141 try { 142 LocalMemSpace *space = new LocalMemSpace; 143 // Before trying to allocate the heap temporarily allocate the 144 // reserved space. This ensures that this much space will always 145 // be available for C stacks and the C++ heap. 146 void *reservation = 0; 147 size_t rSpace = reservedSpace*sizeof(PolyWord); 148 149 if (reservedSpace != 0) { 150 reservation = osMemoryManager->Allocate(rSpace, PERMISSION_READ); 151 if (reservation == 0) { 152 // Insufficient space for the reservation. Can't allocate this local space. 153 if (debugOptions & DEBUG_MEMMGR) 154 Log("MMGR: New local %smutable space: insufficient reservation space\n", mut ? "": "im"); 155 delete space; 156 return 0; 157 } 158 } 159 160 bool success = space->InitSpace(size, mut) && AddLocalSpace(space); 161 if (reservation != 0) osMemoryManager->Free(reservation, rSpace); 162 if (success) 163 { 164 if (debugOptions & DEBUG_MEMMGR) 165 Log("MMGR: New local %smutable space %p, size=%luk words, bottom=%p, top=%p\n", mut ? "": "im", 166 space, space->spaceSize()/1024, space->bottom, space->top); 167 currentHeapSize += space->spaceSize(); 168 globalStats.setSize(PSS_TOTAL_HEAP, currentHeapSize * sizeof(PolyWord)); 169 return space; 170 } 171 172 // If something went wrong. 173 delete space; 174 if (debugOptions & DEBUG_MEMMGR) 175 Log("MMGR: New local %smutable space: insufficient space\n", mut ? "": "im"); 176 return 0; 177 } 178 catch (std::bad_alloc&) { 179 if (debugOptions & DEBUG_MEMMGR) 180 Log("MMGR: New local %smutable space: \"new\" failed\n", mut ? "": "im"); 181 return 0; 182 } 183} 184 185// Create a local space for initial allocation. 186LocalMemSpace *MemMgr::CreateAllocationSpace(POLYUNSIGNED size) 187{ 188 LocalMemSpace *result = NewLocalSpace(size, true); 189 if (result) 190 { 191 result->allocationSpace = true; 192 currentAllocSpace += result->spaceSize(); 193 globalStats.incSize(PSS_ALLOCATION, result->spaceSize()*sizeof(PolyWord)); 194 globalStats.incSize(PSS_ALLOCATION_FREE, result->freeSpace()*sizeof(PolyWord)); 195 } 196 return result; 197} 198 199// If an allocation space has a lot of data left in it after a GC, particularly 200// a single large object we should turn it into a local area. 201void MemMgr::ConvertAllocationSpaceToLocal(LocalMemSpace *space) 202{ 203 ASSERT(space->allocationSpace); 204 space->allocationSpace = false; 205 // Currently it is left as a mutable area but if the contents are all 206 // immutable e.g. a large vector it could be better to turn it into an 207 // immutable area. 208 currentAllocSpace -= space->spaceSize(); 209} 210 211// Add a local memory space to the table. 212bool MemMgr::AddLocalSpace(LocalMemSpace *space) 213{ 214 // Add to the table. 215 // Update the B-tree. 216 try { 217 AddTree(space); 218 // The entries in the local table are ordered so that the copy phase of the full 219 // GC simply has to copy to an entry earlier in the table. Immutable spaces come 220 // first, followed by mutable spaces and finally allocation spaces. 221 if (space->allocationSpace) 222 lSpaces.push_back(space); // Just add at the end 223 else if (space->isMutable) 224 { 225 // Add before the allocation spaces 226 std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); 227 while (i != lSpaces.end() && ! (*i)->allocationSpace) i++; 228 lSpaces.insert(i, space); 229 } 230 else 231 { 232 // Immutable space: Add before the mutable spaces 233 std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); 234 while (i != lSpaces.end() && ! (*i)->isMutable) i++; 235 lSpaces.insert(i, space); 236 } 237 } 238 catch (std::bad_alloc&) { 239 RemoveTree(space); 240 return false; 241 } 242 return true; 243} 244 245 246// Create an entry for a permanent space. 247PermanentMemSpace* MemMgr::NewPermanentSpace(PolyWord *base, POLYUNSIGNED words, 248 unsigned flags, unsigned index, unsigned hierarchy /*= 0*/) 249{ 250 try { 251 PermanentMemSpace *space = new PermanentMemSpace; 252 space->bottom = base; 253 space->topPointer = space->top = space->bottom + words; 254 space->spaceType = ST_PERMANENT; 255 space->isMutable = flags & MTF_WRITEABLE ? true : false; 256 space->noOverwrite = flags & MTF_NO_OVERWRITE ? true : false; 257 space->byteOnly = flags & MTF_BYTES ? true : false; 258 space->isCode = flags & MTF_EXECUTABLE ? true : false; 259 space->index = index; 260 space->hierarchy = hierarchy; 261 if (index >= nextIndex) nextIndex = index+1; 262 263 // Extend the permanent memory table and add this space to it. 264 try { 265 AddTree(space); 266 pSpaces.push_back(space); 267 } 268 catch (std::exception&) { 269 RemoveTree(space); 270 delete space; 271 return 0; 272 } 273 return space; 274 } 275 catch (std::bad_alloc&) { 276 return 0; 277 } 278} 279 280// Delete a local space and remove it from the table. 281void MemMgr::DeleteLocalSpace(std::vector<LocalMemSpace*>::iterator &iter) 282{ 283 LocalMemSpace *sp = *iter; 284 if (debugOptions & DEBUG_MEMMGR) 285 Log("MMGR: Deleted local %s space %p\n", sp->spaceTypeString(), sp); 286 currentHeapSize -= sp->spaceSize(); 287 globalStats.setSize(PSS_TOTAL_HEAP, currentHeapSize * sizeof(PolyWord)); 288 if (sp->allocationSpace) currentAllocSpace -= sp->spaceSize(); 289 RemoveTree(sp); 290 delete(sp); 291 iter = lSpaces.erase(iter); 292} 293 294// Remove local areas that are now empty after a GC. 295// It isn't clear if we always want to do this. 296void MemMgr::RemoveEmptyLocals() 297{ 298 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); ) 299 { 300 LocalMemSpace *space = *i; 301 if (space->allocatedSpace() == 0) 302 DeleteLocalSpace(i); 303 else i++; 304 } 305} 306 307// Create and initialise a new export space and add it to the table. 308PermanentMemSpace* MemMgr::NewExportSpace(POLYUNSIGNED size, bool mut, bool noOv, bool code) 309{ 310 try { 311 PermanentMemSpace *space = new PermanentMemSpace; 312 space->spaceType = ST_EXPORT; 313 space->isMutable = mut; 314 space->noOverwrite = noOv; 315 space->isCode = code; 316 space->index = nextIndex++; 317 // Allocate the memory itself. 318 size_t iSpace = size*sizeof(PolyWord); 319 space->bottom = 320 (PolyWord*)osMemoryManager->Allocate(iSpace, PERMISSION_READ|PERMISSION_WRITE|PERMISSION_EXEC); 321 322 if (space->bottom == 0) 323 { 324 delete space; 325 if (debugOptions & DEBUG_MEMMGR) 326 Log("MMGR: New export %smutable space: insufficient space\n", mut ? "" : "im"); 327 return 0; 328 } 329 space->isOwnSpace = true; 330 331 // The size may have been rounded up to a block boundary. 332 size = iSpace/sizeof(PolyWord); 333 space->top = space->bottom + size; 334 space->topPointer = space->bottom; 335 336 if (debugOptions & DEBUG_MEMMGR) 337 Log("MMGR: New export %smutable %s%sspace %p, size=%luk words, bottom=%p, top=%p\n", mut ? "" : "im", 338 noOv ? "no-overwrite " : "", code ? "code " : "", space, 339 space->spaceSize() / 1024, space->bottom, space->top); 340 341 // Add to the table. 342 try { 343 AddTree(space); 344 eSpaces.push_back(space); 345 } 346 catch (std::exception&) { 347 RemoveTree(space); 348 delete space; 349 if (debugOptions & DEBUG_MEMMGR) 350 Log("MMGR: New export %smutable space: Adding to tree failed\n", mut ? "" : "im"); 351 return 0; 352 } 353 return space; 354 } 355 catch (std::bad_alloc&) { 356 if (debugOptions & DEBUG_MEMMGR) 357 Log("MMGR: New export %smutable space: \"new\" failed\n", mut ? "" : "im"); 358 return 0; 359 } 360} 361 362void MemMgr::DeleteExportSpaces(void) 363{ 364 for (std::vector<PermanentMemSpace *>::iterator i = eSpaces.begin(); i < eSpaces.end(); i++) 365 { 366 PermanentMemSpace *space = *i; 367 RemoveTree(space); 368 delete(space); 369 } 370 eSpaces.clear(); 371} 372 373// If we have saved the state rather than exported a function we turn the exported 374// spaces into permanent ones, removing existing permanent spaces at the same or 375// lower level. 376bool MemMgr::PromoteExportSpaces(unsigned hierarchy) 377{ 378 // Save permanent spaces at a lower hierarchy. Others are converted into 379 // local spaces. Most or all items will have been copied from these spaces 380 // into an export space but there could be items reachable only from the stack. 381 std::vector<PermanentMemSpace*>::iterator i = pSpaces.begin(); 382 while (i != pSpaces.end()) 383 { 384 PermanentMemSpace *pSpace = *i; 385 if (pSpace->hierarchy < hierarchy) 386 i++; 387 else 388 { 389 try { 390 // Turn this into a local space or a code space 391 // Remove this from the tree - AddLocalSpace will make an entry for the local version. 392 RemoveTree(pSpace); 393 394 if (pSpace->isCode) 395 { 396 CodeSpace *space = new CodeSpace(pSpace->bottom, pSpace->spaceSize()); 397 if (! space->headerMap.Create(space->spaceSize())) 398 { 399 if (debugOptions & DEBUG_MEMMGR) 400 Log("MMGR: Unable to create header map for state space %p\n", pSpace); 401 return false; 402 } 403 if (!AddCodeSpace(space)) 404 { 405 if (debugOptions & DEBUG_MEMMGR) 406 Log("MMGR: Unable to convert saved state space %p into code space\n", pSpace); 407 return false; 408 } 409 if (debugOptions & DEBUG_MEMMGR) 410 Log("MMGR: Converted saved state space %p into code space %p\n", pSpace, space); 411 // Set the bits in the header map. 412 for (PolyWord *ptr = space->bottom; ptr < space->top; ) 413 { 414 PolyObject *obj = (PolyObject*)(ptr+1); 415 // We may have forwarded this if this has been 416 // copied to the exported area. Restore the original length word. 417 if (obj->ContainsForwardingPtr()) 418 { 419 PolyObject *forwardedTo = obj->FollowForwardingChain(); 420 obj->SetLengthWord(forwardedTo->LengthWord()); 421 } 422 if (obj->IsCodeObject()) 423 space->headerMap.SetBit(ptr-space->bottom); 424 ptr += obj->Length() + 1; 425 } 426 } 427 else 428 { 429 LocalMemSpace *space = new LocalMemSpace; 430 space->top = pSpace->top; 431 // Space is allocated in local areas from the top down. This area is full and 432 // all data is in the old generation. The area can be recovered by a full GC. 433 space->bottom = space->upperAllocPtr = space->lowerAllocPtr = 434 space->fullGCLowerLimit = pSpace->bottom; 435 space->isMutable = pSpace->isMutable; 436 space->isOwnSpace = true; 437 space->isCode = false; 438 if (! space->bitmap.Create(space->top-space->bottom) || ! AddLocalSpace(space)) 439 { 440 if (debugOptions & DEBUG_MEMMGR) 441 Log("MMGR: Unable to convert saved state space %p into local space\n", pSpace); 442 return false; 443 } 444 if (debugOptions & DEBUG_MEMMGR) 445 Log("MMGR: Converted saved state space %p into local %smutable space %p\n", 446 pSpace, pSpace->isMutable ? "im": "", space); 447 currentHeapSize += space->spaceSize(); 448 globalStats.setSize(PSS_TOTAL_HEAP, currentHeapSize * sizeof(PolyWord)); 449 } 450 i = pSpaces.erase(i); 451 } 452 catch (std::bad_alloc&) { 453 return false; 454 } 455 } 456 } 457 // Save newly exported spaces. 458 for(std::vector<PermanentMemSpace *>::iterator j = eSpaces.begin(); j < eSpaces.end(); j++) 459 { 460 PermanentMemSpace *space = *j; 461 space->hierarchy = hierarchy; // Set the hierarchy of the new spaces. 462 space->spaceType = ST_PERMANENT; 463 // Put a dummy object to fill up the unused space. 464 if (space->topPointer != space->top) 465 FillUnusedSpace(space->topPointer, space->top - space->topPointer); 466 // Put in a dummy object to fill the rest of the space. 467 pSpaces.push_back(space); 468 } 469 eSpaces.clear(); 470 471 return true; 472} 473 474 475// Before we import a hierarchical saved state we need to turn any previously imported 476// spaces into local spaces. 477bool MemMgr::DemoteImportSpaces() 478{ 479 return PromoteExportSpaces(1); // Only truly permanent spaces are retained. 480} 481 482// Return the space for a given index 483PermanentMemSpace *MemMgr::SpaceForIndex(unsigned index) 484{ 485 for (std::vector<PermanentMemSpace*>::iterator i = pSpaces.begin(); i < pSpaces.end(); i++) 486 { 487 PermanentMemSpace *space = *i; 488 if (space->index == index) 489 return space; 490 } 491 return NULL; 492} 493 494// In several places we assume that segments are filled with valid 495// objects. This fills unused memory with one or more "byte" objects. 496void MemMgr::FillUnusedSpace(PolyWord *base, POLYUNSIGNED words) 497{ 498 PolyWord *pDummy = base+1; 499 while (words > 0) 500 { 501 POLYUNSIGNED oSize = words; 502 // If the space is larger than the maximum object size 503 // we will need several objects. 504 if (words > MAX_OBJECT_SIZE) oSize = MAX_OBJECT_SIZE; 505 else oSize = words-1; 506 // Make this a byte object so it's always skipped. 507 ((PolyObject*)pDummy)->SetLengthWord(oSize, F_BYTE_OBJ); 508 words -= oSize+1; 509 pDummy += oSize+1; 510 } 511} 512 513// Allocate an area of the heap of at least minWords and at most maxWords. 514// This is used both when allocating single objects (when minWords and maxWords 515// are the same) and when allocating heap segments. If there is insufficient 516// space to satisfy the minimum it will return 0. 517PolyWord *MemMgr::AllocHeapSpace(POLYUNSIGNED minWords, POLYUNSIGNED &maxWords, bool doAllocation) 518{ 519 PLocker locker(&allocLock); 520 // We try to distribute the allocations between the memory spaces 521 // so that at the next GC we don't have all the most recent cells in 522 // one space. The most recent cells will be more likely to survive a 523 // GC so distibuting them improves the load balance for a multi-thread GC. 524 nextAllocator++; 525 if (nextAllocator > gMem.lSpaces.size()) nextAllocator = 0; 526 527 unsigned j = nextAllocator; 528 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); i++) 529 { 530 if (j >= gMem.lSpaces.size()) j = 0; 531 LocalMemSpace *space = gMem.lSpaces[j++]; 532 if (space->allocationSpace) 533 { 534 POLYUNSIGNED available = space->freeSpace(); 535 if (available > 0 && available >= minWords) 536 { 537 // Reduce the maximum value if we had less than that. 538 if (available < maxWords) 539 maxWords = available; 540 PolyWord *result = space->lowerAllocPtr; // Return the address. 541 if (doAllocation) 542 space->lowerAllocPtr += maxWords; // Allocate it. 543 return result; 544 } 545 } 546 } 547 // There isn't space in the existing areas - can we create a new area? 548 // The reason we don't have enough space could simply be that we want to 549 // allocate an object larger than the default space size. Try deleting 550 // some other spaces to bring currentAllocSpace below spaceBeforeMinorGC - minWords. 551 if (minWords > defaultSpaceSize && minWords < spaceBeforeMinorGC) 552 RemoveExcessAllocation(spaceBeforeMinorGC - minWords); 553 554 if (currentAllocSpace/* + minWords */ < spaceBeforeMinorGC) 555 { 556 // i.e. the current allocation space is less than the space allowed for the minor GC 557 // but it may be that allocating this object will take us over the limit. We allow 558 // that to happen so that we can successfully allocate very large objects even if 559 // we have a new GC very shortly. 560 POLYUNSIGNED spaceSize = defaultSpaceSize; 561 if (minWords > spaceSize) spaceSize = minWords; // If we really want a large space. 562 LocalMemSpace *space = CreateAllocationSpace(spaceSize); 563 if (space == 0) return 0; // Can't allocate it 564 // Allocate our space in this new area. 565 POLYUNSIGNED available = space->freeSpace(); 566 ASSERT(available >= minWords); 567 if (available < maxWords) 568 maxWords = available; 569 PolyWord *result = space->lowerAllocPtr; // Return the address. 570 if (doAllocation) 571 space->lowerAllocPtr += maxWords; // Allocate it. 572 return result; 573 } 574 return 0; // There isn't space even for the minimum. 575} 576 577CodeSpace::CodeSpace(PolyWord *start, POLYUNSIGNED spaceSize) 578{ 579 isOwnSpace = true; 580 bottom = start; 581 top = start+spaceSize; 582 isMutable = true; // Make it mutable just in case. This will cause it to be scanned. 583 isOwnSpace = true; 584 isCode = true; 585 spaceType = ST_CODE; 586 largestFree = spaceSize-1; 587 firstFree = start; 588} 589 590CodeSpace *MemMgr::NewCodeSpace(POLYUNSIGNED size) 591{ 592 // Allocate a new area and add it at the end of the table. 593 CodeSpace *allocSpace = 0; 594 // Allocate a new mutable, code space. N.B. This may round up "actualSize". 595 size_t actualSize = size * sizeof(PolyWord); 596 PolyWord *mem = 597 (PolyWord*)osMemoryManager->Allocate(actualSize, 598 PERMISSION_READ | PERMISSION_WRITE | PERMISSION_EXEC); 599 if (mem != 0) 600 { 601 try { 602 allocSpace = new CodeSpace(mem, actualSize / sizeof(PolyWord)); 603 if (!allocSpace->headerMap.Create(allocSpace->spaceSize())) 604 { 605 delete allocSpace; 606 allocSpace = 0; 607 } 608 else if (!AddCodeSpace(allocSpace)) 609 { 610 delete allocSpace; 611 allocSpace = 0; 612 } 613 else if (debugOptions & DEBUG_MEMMGR) 614 Log("MMGR: New code space %p allocated at %p size %lu\n", allocSpace, allocSpace->bottom, allocSpace->spaceSize()); 615 // Put in a byte cell to mark the area as unallocated. 616 FillUnusedSpace(allocSpace->bottom, allocSpace->spaceSize()); 617 } 618 catch (std::bad_alloc&) 619 { 620 } 621 if (allocSpace == 0) 622 { 623 osMemoryManager->Free(mem, actualSize); 624 mem = 0; 625 } 626 } 627 return allocSpace; 628} 629 630// Allocate memory for a piece of code. This needs to be both mutable and executable, 631// at least for native code. The interpreted version need not (should not?) make the 632// area executable. It will not be executed until the mutable bit has been cleared. 633// Once code is allocated it is not GCed or moved. 634// initCell is a byte cell that is copied into the new code area. 635PolyObject*MemMgr::AllocCodeSpace(PolyObject *initCell) 636{ 637 PLocker locker(&codeSpaceLock); 638 // Search the code spaces until we find a free area big enough. 639 size_t i = 0; 640 POLYUNSIGNED requiredSize = initCell->Length(); 641 while (true) 642 { 643 if (i != cSpaces.size()) 644 { 645 CodeSpace *space = cSpaces[i]; 646 if (space->largestFree >= requiredSize) 647 { 648 POLYUNSIGNED actualLargest = 0; 649 while (space->firstFree < space->top) 650 { 651 PolyObject *obj = (PolyObject*)(space->firstFree+1); 652 // Skip over allocated areas or free areas that are too small. 653 if (obj->IsCodeObject() || obj->Length() < 8) 654 space->firstFree += obj->Length()+1; 655 else break; 656 } 657 PolyWord *pt = space->firstFree; 658 while (pt < space->top) 659 { 660 PolyObject *obj = (PolyObject*)(pt+1); 661 POLYUNSIGNED length = obj->Length(); 662 if (obj->IsByteObject()) 663 { 664 if (length >= requiredSize) 665 { 666 // Free and large enough 667 PolyWord *next = pt+requiredSize+1; 668 if (requiredSize < length) 669 FillUnusedSpace(next, length-requiredSize); 670 space->isMutable = true; // Set this - it ensures the area is scanned on GC. 671 space->headerMap.SetBit(pt-space->bottom); // Set the "header" bit 672 // Set the length word of the code area and copy the byte cell in. 673 // The code bit must be set before the lock is released to ensure 674 // another thread doesn't reuse this. 675 obj->SetLengthWord(requiredSize, F_CODE_OBJ|F_MUTABLE_BIT); 676 memcpy(obj, initCell, requiredSize * sizeof(PolyWord)); 677 return obj; 678 } 679 else if (length >= actualLargest) actualLargest = length+1; 680 } 681 pt += length+1; 682 } 683 // Reached the end without finding what we wanted. Update the largest size. 684 space->largestFree = actualLargest; 685 } 686 i++; // Next area 687 } 688 else 689 { 690 // Allocate a new area and add it at the end of the table. 691 CodeSpace *allocSpace = NewCodeSpace(requiredSize + 1); 692 if (allocSpace == 0) 693 return 0; // Try a GC. 694 } 695 } 696} 697 698// Remove code areas that are completely empty. This is probably better than waiting to reuse them. 699// It's particularly important if we reload a saved state because the code areas for old saved states 700// are made into local code areas just in case they are currently in use or reachable. 701void MemMgr::RemoveEmptyCodeAreas() 702{ 703 for (std::vector<CodeSpace *>::iterator i = cSpaces.begin(); i != cSpaces.end(); ) 704 { 705 CodeSpace *space = *i; 706 PolyObject *start = (PolyObject *)(space->bottom+1); 707 if (start->IsByteObject() && start->Length() == space->spaceSize()-1) 708 { 709 if (debugOptions & DEBUG_MEMMGR) 710 Log("MMGR: Deleted code space %p\n", space); 711 // We have an empty cell that fills the whole space. 712 RemoveTree(space); 713 delete(space); 714 i = cSpaces.erase(i); 715 } 716 else i++; 717 } 718} 719 720// Add a code space to the tables. Used both for newly compiled code and also demoted saved spaces. 721bool MemMgr::AddCodeSpace(CodeSpace *space) 722{ 723 try { 724 AddTree(space); 725 cSpaces.push_back(space); 726 } 727 catch (std::exception&) { 728 RemoveTree(space); 729 return false; 730 } 731 return true; 732} 733 734// Check that we have sufficient space for an allocation to succeed. 735// Called from the GC to ensure that we will not get into an infinite 736// loop trying to allocate, failing and garbage-collecting again. 737bool MemMgr::CheckForAllocation(POLYUNSIGNED words) 738{ 739 POLYUNSIGNED allocated = 0; 740 return AllocHeapSpace(words, allocated, false) != 0; 741} 742 743// Adjust the allocation area by removing free areas so that the total 744// size of the allocation area is less than the required value. This 745// is used after the quick GC and also if we need to allocate a large 746// object. 747void MemMgr::RemoveExcessAllocation(POLYUNSIGNED words) 748{ 749 // First remove any non-standard allocation areas. 750 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end();) 751 { 752 LocalMemSpace *space = *i; 753 if (space->allocationSpace && space->allocatedSpace() == 0 && 754 space->spaceSize() != defaultSpaceSize) 755 DeleteLocalSpace(i); 756 else i++; 757 } 758 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); currentAllocSpace > words && i < lSpaces.end(); ) 759 { 760 LocalMemSpace *space = *i; 761 if (space->allocationSpace && space->allocatedSpace() == 0) 762 DeleteLocalSpace(i); 763 else i++; 764 } 765} 766 767// Return number of words free in all allocation spaces. 768POLYUNSIGNED MemMgr::GetFreeAllocSpace() 769{ 770 POLYUNSIGNED freeSpace = 0; 771 PLocker lock(&allocLock); 772 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); i++) 773 { 774 LocalMemSpace *space = *i; 775 if (space->allocationSpace) 776 freeSpace += space->freeSpace(); 777 } 778 return freeSpace; 779} 780 781StackSpace *MemMgr::NewStackSpace(POLYUNSIGNED size) 782{ 783 PLocker lock(&stackSpaceLock); 784 785 try { 786 StackSpace *space = new StackSpace; 787 size_t iSpace = size*sizeof(PolyWord); 788 space->bottom = 789 (PolyWord*)osMemoryManager->Allocate(iSpace, PERMISSION_READ|PERMISSION_WRITE); 790 if (space->bottom == 0) 791 { 792 if (debugOptions & DEBUG_MEMMGR) 793 Log("MMGR: New stack space: insufficient space\n"); 794 delete space; 795 return 0; 796 } 797 798 // The size may have been rounded up to a block boundary. 799 size = iSpace/sizeof(PolyWord); 800 space->top = space->bottom + size; 801 space->spaceType = ST_STACK; 802 space->isMutable = true; 803 804 // Add the stack space to the tree. This ensures that operations such as 805 // LocalSpaceForAddress will work for addresses within the stack. We can 806 // get them in the RTS with functions such as quot_rem and exception stack. 807 // It's not clear whether they really appear in the GC. 808 try { 809 AddTree(space); 810 sSpaces.push_back(space); 811 } 812 catch (std::exception&) { 813 RemoveTree(space); 814 delete space; 815 return 0; 816 } 817 if (debugOptions & DEBUG_MEMMGR) 818 Log("MMGR: New stack space %p allocated at %p size %lu\n", space, space->bottom, space->spaceSize()); 819 return space; 820 } 821 catch (std::bad_alloc&) { 822 if (debugOptions & DEBUG_MEMMGR) 823 Log("MMGR: New stack space: \"new\" failed\n"); 824 return 0; 825 } 826} 827 828// If checkmem is given write protect the immutable areas except during a GC. 829void MemMgr::ProtectImmutable(bool on) 830{ 831 if (debugOptions & DEBUG_CHECK_OBJECTS) 832 { 833 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); i++) 834 { 835 LocalMemSpace *space = *i; 836 if (! space->isMutable) 837 osMemoryManager->SetPermissions(space->bottom, (char*)space->top - (char*)space->bottom, 838 on ? PERMISSION_READ|PERMISSION_EXEC : PERMISSION_READ|PERMISSION_EXEC|PERMISSION_WRITE); 839 } 840 } 841} 842 843bool MemMgr::GrowOrShrinkStack(TaskData *taskData, POLYUNSIGNED newSize) 844{ 845 StackSpace *space = taskData->stack; 846 size_t iSpace = newSize*sizeof(PolyWord); 847 PolyWord *newSpace = (PolyWord*)osMemoryManager->Allocate(iSpace, PERMISSION_READ|PERMISSION_WRITE); 848 if (newSpace == 0) 849 { 850 if (debugOptions & DEBUG_MEMMGR) 851 Log("MMGR: Unable to change size of stack %p from %lu to %lu: insufficient space\n", 852 space, space->spaceSize(), newSize); 853 return false; 854 } 855 // The size may have been rounded up to a block boundary. 856 newSize = iSpace/sizeof(PolyWord); 857 try { 858 AddTree(space, newSpace, newSpace+newSize); 859 } 860 catch (std::bad_alloc&) { 861 RemoveTree(space, newSpace, newSpace+newSize); 862 delete space; 863 return 0; 864 } 865 taskData->CopyStackFrame(space->stack(), space->spaceSize(), (StackObject*)newSpace, newSize); 866 if (debugOptions & DEBUG_MEMMGR) 867 Log("MMGR: Size of stack %p changed from %lu to %lu at %p\n", space, space->spaceSize(), newSize, newSpace); 868 RemoveTree(space); // Remove it BEFORE freeing the space - another thread may allocate it 869 PolyWord *oldBottom = space->bottom; 870 size_t oldSize = (char*)space->top - (char*)space->bottom; 871 space->bottom = newSpace; // Switch this before freeing - We could get a profile trap during the free 872 space->top = newSpace+newSize; 873 osMemoryManager->Free(oldBottom, oldSize); 874 return true; 875} 876 877 878// Delete a stack when a thread has finished. 879// This can be called by an ML thread so needs an interlock. 880bool MemMgr::DeleteStackSpace(StackSpace *space) 881{ 882 PLocker lock(&stackSpaceLock); 883 884 for (std::vector<StackSpace *>::iterator i = sSpaces.begin(); i < sSpaces.end(); i++) 885 { 886 if (*i == space) 887 { 888 RemoveTree(space); 889 delete space; 890 sSpaces.erase(i); 891 if (debugOptions & DEBUG_MEMMGR) 892 Log("MMGR: Deleted stack space %p\n", space); 893 return true; 894 } 895 } 896 ASSERT(false); // It should always be in the table. 897 return false; 898} 899 900SpaceTreeTree::SpaceTreeTree(): SpaceTree(false) 901{ 902 for (unsigned i = 0; i < 256; i++) 903 tree[i] = 0; 904} 905 906SpaceTreeTree::~SpaceTreeTree() 907{ 908 for (unsigned i = 0; i < 256; i++) 909 { 910 if (tree[i] && ! tree[i]->isSpace) 911 delete(tree[i]); 912 } 913} 914 915// Add and remove entries in the space tree. 916 917void MemMgr::AddTree(MemSpace *space, PolyWord *startS, PolyWord *endS) 918{ 919 // It isn't clear we need to lock here but it's probably sensible. 920 PLocker lock(&spaceTreeLock); 921 AddTreeRange(&spaceTree, space, (uintptr_t)startS, (uintptr_t)endS); 922} 923 924void MemMgr::RemoveTree(MemSpace *space, PolyWord *startS, PolyWord *endS) 925{ 926 PLocker lock(&spaceTreeLock); 927 RemoveTreeRange(&spaceTree, space, (uintptr_t)startS, (uintptr_t)endS); 928} 929 930 931void MemMgr::AddTreeRange(SpaceTree **tt, MemSpace *space, uintptr_t startS, uintptr_t endS) 932{ 933 if (*tt == 0) 934 *tt = new SpaceTreeTree; 935 ASSERT(! (*tt)->isSpace); 936 SpaceTreeTree *t = (SpaceTreeTree*)*tt; 937 938 const unsigned shift = (sizeof(void*)-1) * 8; // Takes the high-order byte 939 uintptr_t r = startS >> shift; 940 ASSERT(r < 256); 941 const uintptr_t s = endS == 0 ? 256 : endS >> shift; 942 ASSERT(s >= r && s <= 256); 943 944 if (r == s) // Wholly within this entry 945 AddTreeRange(&(t->tree[r]), space, startS << 8, endS << 8); 946 else 947 { 948 // Deal with any remainder at the start. 949 if ((r << shift) != startS) 950 { 951 AddTreeRange(&(t->tree[r]), space, startS << 8, 0 /*End of range*/); 952 r++; 953 } 954 // Whole entries. 955 while (r < s) 956 { 957 ASSERT(t->tree[r] == 0); 958 t->tree[r] = space; 959 r++; 960 } 961 // Remainder at the end. 962 if ((s << shift) != endS) 963 AddTreeRange(&(t->tree[r]), space, 0, endS << 8); 964 } 965} 966 967// Remove an entry from the tree for a range. Strictly speaking we don't need the 968// space argument here but it's useful as a check. 969// This may be called to remove a partially installed structure if we have 970// run out of space in AddTreeRange. 971void MemMgr::RemoveTreeRange(SpaceTree **tt, MemSpace *space, uintptr_t startS, uintptr_t endS) 972{ 973 SpaceTreeTree *t = (SpaceTreeTree*)*tt; 974 if (t == 0) 975 return; // This can only occur if we're recovering. 976 ASSERT(! t->isSpace); 977 const unsigned shift = (sizeof(void*)-1) * 8; 978 uintptr_t r = startS >> shift; 979 const uintptr_t s = endS == 0 ? 256 : endS >> shift; 980 981 if (r == s) 982 RemoveTreeRange(&(t->tree[r]), space, startS << 8, endS << 8); 983 else 984 { 985 // Deal with any remainder at the start. 986 if ((r << shift) != startS) 987 { 988 RemoveTreeRange(&(t->tree[r]), space, startS << 8, 0); 989 r++; 990 } 991 // Whole entries. 992 while (r < s) 993 { 994 ASSERT(t->tree[r] == space || t->tree[r] == 0 /* Recovery only */); 995 t->tree[r] = 0; 996 r++; 997 } 998 // Remainder at the end. 999 if ((s << shift) != endS) 1000 RemoveTreeRange(&(t->tree[r]), space, 0, endS << 8); 1001 } 1002 // See if the whole vector is now empty. 1003 for (unsigned j = 0; j < 256; j++) 1004 { 1005 if (t->tree[j]) 1006 return; // It's not empty - we're done. 1007 } 1008 delete(t); 1009 *tt = 0; 1010} 1011 1012POLYUNSIGNED MemMgr::AllocatedInAlloc() 1013{ 1014 POLYUNSIGNED inAlloc = 0; 1015 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); i++) 1016 { 1017 LocalMemSpace *sp = *i; 1018 if (sp->allocationSpace) inAlloc += sp->allocatedSpace(); 1019 } 1020 return inAlloc; 1021} 1022 1023// Report heap sizes and occupancy before and after GC 1024void MemMgr::ReportHeapSizes(const char *phase) 1025{ 1026 POLYUNSIGNED alloc = 0, nonAlloc = 0, inAlloc = 0, inNonAlloc = 0; 1027 for (std::vector<LocalMemSpace*>::iterator i = lSpaces.begin(); i < lSpaces.end(); i++) 1028 { 1029 LocalMemSpace *sp = *i; 1030 if (sp->allocationSpace) 1031 { 1032 alloc += sp->spaceSize(); 1033 inAlloc += sp->allocatedSpace(); 1034 } 1035 else 1036 { 1037 nonAlloc += sp->spaceSize(); 1038 inNonAlloc += sp->allocatedSpace(); 1039 } 1040 } 1041 Log("Heap: %s Major heap used ", phase); 1042 LogSize(inNonAlloc); Log(" of "); 1043 LogSize(nonAlloc); 1044 Log(" (%1.0f%%). Alloc space used ", (float)inNonAlloc / (float)nonAlloc * 100.0F); 1045 LogSize(inAlloc); Log(" of "); 1046 LogSize(alloc); 1047 Log(" (%1.0f%%). Total space ", (float)inAlloc / (float)alloc * 100.0F); 1048 LogSize(spaceForHeap); 1049 Log(" %1.0f%% full.\n", (float)(inAlloc + inNonAlloc) / (float)spaceForHeap * 100.0F); 1050 Log("Heap: Local spaces %" PRI_SIZET ", permanent spaces %" PRI_SIZET ", code spaces %" PRI_SIZET ", stack spaces %" PRI_SIZET "\n", 1051 lSpaces.size(), pSpaces.size(), cSpaces.size(), sSpaces.size()); 1052 POLYUNSIGNED cTotal = 0, cOccupied = 0; 1053 for (std::vector<CodeSpace*>::iterator c = cSpaces.begin(); c != cSpaces.end(); c++) 1054 { 1055 cTotal += (*c)->spaceSize(); 1056 PolyWord *pt = (*c)->bottom; 1057 while (pt < (*c)->top) 1058 { 1059 pt++; 1060 PolyObject *obj = (PolyObject*)pt; 1061 if (obj->ContainsForwardingPtr()) 1062 { 1063 obj = obj->FollowForwardingChain(); 1064 pt += obj->Length(); 1065 } 1066 else 1067 { 1068 if (obj->IsCodeObject()) 1069 cOccupied += obj->Length() + 1; 1070 pt += obj->Length(); 1071 } 1072 } 1073 } 1074 Log("Heap: Code area: total "); LogSize(cTotal); Log(" occupied: "); LogSize(cOccupied); Log("\n"); 1075 POLYUNSIGNED stackSpace = 0; 1076 for (std::vector<StackSpace*>::iterator s = sSpaces.begin(); s != sSpaces.end(); s++) 1077 { 1078 stackSpace += (*s)->spaceSize(); 1079 } 1080 Log("Heap: Stack area: total "); LogSize(stackSpace); Log("\n"); 1081} 1082 1083// Profiling - Find a code object or return zero if not found. 1084// This can be called on a "user" thread. 1085PolyObject *MemMgr::FindCodeObject(const byte *addr) 1086{ 1087 MemSpace *space = SpaceForAddress(addr); 1088 if (space == 0) return 0; 1089 Bitmap *profMap = 0; 1090 if (! space->isCode) return 0; 1091 if (space->spaceType == ST_CODE) 1092 { 1093 CodeSpace *cSpace = (CodeSpace*)space; 1094 profMap = &cSpace->headerMap; 1095 } 1096 else if (space->spaceType == ST_PERMANENT) 1097 { 1098 PermanentMemSpace *pSpace = (PermanentMemSpace*)space; 1099 profMap = &pSpace->profileCode; 1100 } 1101 else return 0; // Must be in code or permanent code. 1102 1103 // For the permanent areas the header maps are created and initialised on demand. 1104 if (! profMap->Created()) 1105 { 1106 PLocker lock(&codeBitmapLock); 1107 if (! profMap->Created()) // Second check now we've got the lock. 1108 { 1109 // Create the bitmap. If it failed just say "not in this area" 1110 if (! profMap->Create(space->spaceSize())) 1111 return 0; 1112 // Set the first bit before releasing the lock. 1113 profMap->SetBit(0); 1114 } 1115 } 1116 1117 // A bit is set if it is a length word. 1118 while ((POLYUNSIGNED)addr & (sizeof(POLYUNSIGNED)-1)) addr--; // Make it word aligned 1119 PolyWord *wordAddr = (PolyWord*)addr; 1120 // Work back to find the first set bit before this. 1121 // Normally we will find one but if we're looking up a value that 1122 // is actually an integer it might be in a piece of code that is now free. 1123 POLYUNSIGNED bitOffset = profMap->FindLastSet(wordAddr - space->bottom); 1124 if (space->spaceType == ST_CODE) 1125 { 1126 PolyWord *ptr = space->bottom+bitOffset; 1127 if (ptr >= space->top) return 0; 1128 // This will find the last non-free code cell or the first cell. 1129 // Return zero if the value was not actually in the cell or it wasn't code. 1130 PolyObject *obj = (PolyObject*)(ptr+1); 1131 PolyObject *lastObj = obj->FollowForwardingChain(); 1132 // We normally replace forwarding pointers but when scanning to update 1133 // addresses after a saved state we may not have yet done that. 1134 if (wordAddr > ptr && wordAddr < ptr + 1 + lastObj->Length() && lastObj->IsCodeObject()) 1135 return obj; 1136 else return 0; 1137 } 1138 // Permanent area - the bits are set on demand. 1139 // Now work forward, setting any bits if necessary. We don't need a lock 1140 // because this is monotonic. 1141 for (;;) 1142 { 1143 PolyWord *ptr = space->bottom+bitOffset; 1144 if (ptr >= space->top) return 0; 1145 PolyObject *obj = (PolyObject*)(ptr+1); 1146 ASSERT(obj->ContainsNormalLengthWord()); 1147 if (wordAddr > ptr && wordAddr < ptr + obj->Length()) 1148 return obj; 1149 bitOffset += obj->Length()+1; 1150 profMap->SetBit(bitOffset); 1151 } 1152 return 0; 1153} 1154 1155// Remove profiling bitmaps from permanent areas to free up memory. 1156void MemMgr::RemoveProfilingBitmaps() 1157{ 1158 for (std::vector<PermanentMemSpace*>::iterator i = pSpaces.begin(); i < pSpaces.end(); i++) 1159 (*i)->profileCode.Destroy(); 1160} 1161 1162MemMgr gMem; // The one and only memory manager object 1163 1164