1/* 2 Title: Multi-Threaded Garbage Collector - Mark phase 3 4 Copyright (c) 2010-12, 2015-16, 2019 David C. J. Matthews 5 6 Based on the original garbage collector code 7 Copyright 2000-2008 8 Cambridge University Technical Services Limited 9 10 This library is free software; you can redistribute it and/or 11 modify it under the terms of the GNU Lesser General Public 12 License version 2.1 as published by the Free Software Foundation. 13 14 This library is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 Lesser General Public License for more details. 18 19 You should have received a copy of the GNU Lesser General Public 20 License along with this library; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 22 23*/ 24/* 25This is the first, mark, phase of the garbage collector. It detects all 26reachable cells in the area being collected. At the end of the phase the 27bit-maps associated with the areas will have ones for words belonging to cells 28that must be retained and zeros for words that can be reused. 29 30This is now multi-threaded. The mark phase involves setting a bit in the header 31of each live cell and then a pass over the memory building the bitmaps and clearing 32this bit. It is unfortunate that we cannot use the GC-bit that is used in 33forwarding pointers but we may well have forwarded pointers left over from a 34partially completed minor GC. Using a bit in the header avoids the need for 35locking since at worst it may involve two threads duplicating some marking. 36 37The code ensures that each reachable cell is marked at least once but with 38multiple threads a cell may be marked by more than once cell if the 39memory is not fully up to date. Each thread has a stack on which it 40remembers cells that have been marked but not fully scanned. If a 41thread runs out of cells of its own to scan it can pick a pointer off 42the stack of another thread and scan that. The original thread will 43still scan it some time later but it should find that the addresses 44in it have all been marked and it can simply pop this off. This is 45all done without locking. Stacks are only modified by the owning 46thread and when they pop anything they write zero in its place. 47Other threads only need to search for a zero to find if they are 48at the top and if they get a pointer that has already been scanned 49then this is safe. The only assumption made about the memory is 50that all the bits of a word are updated together so that a thread 51will always read a value that is a valid pointer. 52 53Many of the ideas are drawn from Flood, Detlefs, Shavit and Zhang 2001 54"Parallel Garbage Collection for Shared Memory Multiprocessors". 55*/ 56#ifdef HAVE_CONFIG_H 57#include "config.h" 58#elif defined(_WIN32) 59#include "winconfig.h" 60#else 61#error "No configuration file" 62#endif 63 64#ifdef HAVE_ASSERT_H 65#include <assert.h> 66#define ASSERT(x) assert(x) 67#else 68#define ASSERT(x) 69#endif 70 71#include "globals.h" 72#include "processes.h" 73#include "gc.h" 74#include "scanaddrs.h" 75#include "check_objects.h" 76#include "bitmap.h" 77#include "memmgr.h" 78#include "diagnostics.h" 79#include "gctaskfarm.h" 80#include "profiling.h" 81#include "heapsizing.h" 82 83#define MARK_STACK_SIZE 3000 84#define LARGECACHE_SIZE 20 85 86class MTGCProcessMarkPointers: public ScanAddress 87{ 88public: 89 MTGCProcessMarkPointers(); 90 91 virtual void ScanRuntimeAddress(PolyObject **pt, RtsStrength weak); 92 virtual PolyObject *ScanObjectAddress(PolyObject *base); 93 94 virtual void ScanAddressesInObject(PolyObject *base, POLYUNSIGNED lengthWord); 95 // Have to redefine this for some reason. 96 void ScanAddressesInObject(PolyObject *base) 97 { ScanAddressesInObject(base, base->LengthWord()); } 98 99 virtual void ScanConstant(PolyObject *base, byte *addressOfConstant, ScanRelocationKind code); 100 // ScanCodeAddressAt should never be called. 101 POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt) { ASSERT(0); return 0; } 102 103 static void MarkPointersTask(GCTaskId *, void *arg1, void *arg2); 104 105 static void InitStatics(unsigned threads) 106 { 107 markStacks = new MTGCProcessMarkPointers[threads]; 108 nInUse = 0; 109 nThreads = threads; 110 } 111 112 static void MarkRoots(void); 113 static bool RescanForStackOverflow(); 114 115private: 116 bool TestForScan(PolyWord *pt); 117 void MarkAndTestForScan(PolyWord *pt); 118 void Reset(); 119 120 void PushToStack(PolyObject *obj, PolyWord *currentPtr = 0) 121 { 122 // If we don't have all the threads running we start a new one but 123 // only once we have several items on the stack. Otherwise we 124 // can end up creating a task that terminates almost immediately. 125 if (nInUse >= nThreads || msp < 2 || ! ForkNew(obj)) 126 { 127 if (msp < MARK_STACK_SIZE) 128 { 129 markStack[msp++] = obj; 130 if (currentPtr != 0) 131 { 132 locPtr++; 133 if (locPtr == LARGECACHE_SIZE) locPtr = 0; 134 largeObjectCache[locPtr].base = obj; 135 largeObjectCache[locPtr].current = currentPtr; 136 } 137 } 138 else StackOverflow(obj); 139 } 140 // else the new task is processing it. 141 } 142 143 static void StackOverflow(PolyObject *obj); 144 static bool ForkNew(PolyObject *obj); 145 146 PolyObject *markStack[MARK_STACK_SIZE]; 147 unsigned msp; 148 bool active; 149 150 // For the typical small cell it's easier just to rescan from the start 151 // but that can be expensive for large cells. This caches the offset for 152 // large cells. 153 static const POLYUNSIGNED largeObjectSize = 50; 154 struct { PolyObject *base; PolyWord *current; } largeObjectCache[LARGECACHE_SIZE]; 155 unsigned locPtr; 156 157 static MTGCProcessMarkPointers *markStacks; 158protected: 159 static unsigned nThreads, nInUse; 160 static PLock stackLock; 161}; 162 163// There is one mark-stack for each GC thread. markStacks[0] is used by the 164// main thread when marking the roots and rescanning after mark-stack overflow. 165// Once that work is done markStacks[0] is released and is available for a 166// worker thread. 167MTGCProcessMarkPointers *MTGCProcessMarkPointers::markStacks; 168unsigned MTGCProcessMarkPointers::nThreads, MTGCProcessMarkPointers::nInUse; 169PLock MTGCProcessMarkPointers::stackLock("GC mark stack"); 170 171// It is possible to have two levels of forwarding because 172// we could have a cell in the allocation area that has been moved 173// to the immutable area and then shared with another cell. 174inline PolyObject *FollowForwarding(PolyObject *obj) 175{ 176 while (obj->ContainsForwardingPtr()) 177 obj = obj->GetForwardingPtr(); 178 return obj; 179} 180 181MTGCProcessMarkPointers::MTGCProcessMarkPointers(): msp(0), active(false), locPtr(0) 182{ 183 // Clear the mark stack 184 for (unsigned i = 0; i < MARK_STACK_SIZE; i++) 185 markStack[i] = 0; 186 // Clear the large object cache just to be sure. 187 for (unsigned j = 0; j < LARGECACHE_SIZE; j++) 188 { 189 largeObjectCache[j].base = 0; 190 largeObjectCache[j].current = 0; 191 } 192} 193 194// Clear the state at the beginning of a new GC pass. 195void MTGCProcessMarkPointers::Reset() 196{ 197 locPtr = 0; 198 //largeObjectCache[locPtr].base = 0; 199 // Clear the cache completely just to be safe 200 for (unsigned j = 0; j < LARGECACHE_SIZE; j++) 201 { 202 largeObjectCache[j].base = 0; 203 largeObjectCache[j].current = 0; 204 } 205 206} 207 208// Called when the stack has overflowed. We need to include this 209// in the range to be rescanned. 210void MTGCProcessMarkPointers::StackOverflow(PolyObject *obj) 211{ 212 MarkableSpace *space = (MarkableSpace*)gMem.SpaceForObjectAddress(obj); 213 ASSERT(space != 0 && (space->spaceType == ST_LOCAL || space->spaceType == ST_CODE)); 214 PLocker lock(&space->spaceLock); 215 // Have to include this in the range to rescan. 216 if (space->fullGCRescanStart > ((PolyWord*)obj) - 1) 217 space->fullGCRescanStart = ((PolyWord*)obj) - 1; 218 POLYUNSIGNED n = obj->Length(); 219 if (space->fullGCRescanEnd < ((PolyWord*)obj) + n) 220 space->fullGCRescanEnd = ((PolyWord*)obj) + n; 221 ASSERT(obj->LengthWord() & _OBJ_GC_MARK); // Should have been marked. 222 if (debugOptions & DEBUG_GC_ENHANCED) 223 Log("GC: Mark: Stack overflow. Rescan for %p\n", obj); 224} 225 226// Fork a new task. Because we've checked nInUse without taking the lock 227// we may find that we can no longer create a new task. 228bool MTGCProcessMarkPointers::ForkNew(PolyObject *obj) 229{ 230 MTGCProcessMarkPointers *marker = 0; 231 { 232 PLocker lock(&stackLock); 233 if (nInUse == nThreads) 234 return false; 235 for (unsigned i = 0; i < nThreads; i++) 236 { 237 if (! markStacks[i].active) 238 { 239 marker = &markStacks[i]; 240 break; 241 } 242 } 243 ASSERT(marker != 0); 244 marker->active = true; 245 nInUse++; 246 } 247 bool test = gpTaskFarm->AddWork(&MTGCProcessMarkPointers::MarkPointersTask, marker, obj); 248 ASSERT(test); 249 return true; 250} 251 252// Main marking task. This is forked off initially to scan a specific object and 253// anything reachable from it but once that has finished it tries to find objects 254// on other stacks to scan. 255void MTGCProcessMarkPointers::MarkPointersTask(GCTaskId *, void *arg1, void *arg2) 256{ 257 MTGCProcessMarkPointers *marker = (MTGCProcessMarkPointers*)arg1; 258 marker->Reset(); 259 260 marker->ScanAddressesInObject((PolyObject*)arg2); 261 262 while (true) 263 { 264 // Look for a stack that has at least one item on it. 265 MTGCProcessMarkPointers *steal = 0; 266 for (unsigned i = 0; i < nThreads && steal == 0; i++) 267 { 268 if (markStacks[i].markStack[0] != 0) 269 steal = &markStacks[i]; 270 } 271 // We're finished if they're all done. 272 if (steal == 0) 273 break; 274 // Look for items on this stack 275 for (unsigned j = 0; j < MARK_STACK_SIZE; j++) 276 { 277 // Pick the item off the stack. 278 // N.B. The owning thread may update this to zero 279 // at any time. 280 PolyObject *toSteal = steal->markStack[j]; 281 if (toSteal == 0) break; // Nothing more on the stack 282 // The idea here is that the original thread pushed this 283 // because there were at least two addresses it needed to 284 // process. It started down one branch but left the other. 285 // Since it will have marked cells in the branch it has 286 // followed this thread will start on the unprocessed 287 // address(es). 288 marker->ScanAddressesInObject(toSteal); 289 } 290 } 291 292 PLocker lock(&stackLock); 293 marker->active = false; // It's finished 294 nInUse--; 295 ASSERT(marker->markStack[0] == 0); 296} 297 298// Tests if this needs to be scanned. It marks it if it has not been marked 299// unless it has to be scanned. 300bool MTGCProcessMarkPointers::TestForScan(PolyWord *pt) 301{ 302 if ((*pt).IsTagged()) 303 return false; 304 305 // This could contain a forwarding pointer if it points into an 306 // allocation area and has been moved by the minor GC. 307 // We have to be a little careful. Another thread could also 308 // be following any forwarding pointers here. However it's safe 309 // because they will update it with the same value. 310 PolyObject *obj = (*pt).AsObjPtr(); 311 if (obj->ContainsForwardingPtr()) 312 { 313 obj = FollowForwarding(obj); 314 *pt = obj; 315 } 316 317 MemSpace *sp = gMem.SpaceForObjectAddress(obj); 318 if (sp == 0 || (sp->spaceType != ST_LOCAL && sp->spaceType != ST_CODE)) 319 return false; // Ignore it if it points to a permanent area 320 321 POLYUNSIGNED L = obj->LengthWord(); 322 if (L & _OBJ_GC_MARK) 323 return false; // Already marked 324 325 if (debugOptions & DEBUG_GC_DETAIL) 326 Log("GC: Mark: %p %" POLYUFMT " %u\n", obj, OBJ_OBJECT_LENGTH(L), GetTypeBits(L)); 327 328 if (OBJ_IS_BYTE_OBJECT(L)) 329 { 330 obj->SetLengthWord(L | _OBJ_GC_MARK); // Mark it 331 return false; // We've done as much as we need 332 } 333 return true; 334} 335 336void MTGCProcessMarkPointers::MarkAndTestForScan(PolyWord *pt) 337{ 338 if (TestForScan(pt)) 339 { 340 PolyObject *obj = (*pt).AsObjPtr(); 341 obj->SetLengthWord(obj->LengthWord() | _OBJ_GC_MARK); 342 } 343} 344 345// The initial entry to process the roots. These may be RTS addresses or addresses in 346// a thread stack. Also called recursively to process the addresses of constants in 347// code segments. This is used in situations where a scanner may return the 348// updated address of an object. 349PolyObject *MTGCProcessMarkPointers::ScanObjectAddress(PolyObject *obj) 350{ 351 MemSpace *sp = gMem.SpaceForAddress((PolyWord*)obj-1); 352 353 if (!(sp->spaceType == ST_LOCAL || sp->spaceType == ST_CODE)) 354 return obj; // Ignore it if it points to a permanent area 355 356 // We may have a forwarding pointer if this has been moved by the 357 // minor GC. 358 if (obj->ContainsForwardingPtr()) 359 { 360 obj = FollowForwarding(obj); 361 sp = gMem.SpaceForAddress((PolyWord*)obj - 1); 362 } 363 364 ASSERT(obj->ContainsNormalLengthWord()); 365 366 POLYUNSIGNED L = obj->LengthWord(); 367 if (L & _OBJ_GC_MARK) 368 return obj; // Already marked 369 sp->writeAble(obj)->SetLengthWord(L | _OBJ_GC_MARK); // Mark it 370 371 if (profileMode == kProfileLiveData || (profileMode == kProfileLiveMutables && obj->IsMutable())) 372 AddObjectProfile(obj); 373 374 POLYUNSIGNED n = OBJ_OBJECT_LENGTH(L); 375 if (debugOptions & DEBUG_GC_DETAIL) 376 Log("GC: Mark: %p %" POLYUFMT " %u\n", obj, n, GetTypeBits(L)); 377 378 if (OBJ_IS_BYTE_OBJECT(L)) 379 return obj; 380 381 // If we already have something on the stack we must being called 382 // recursively to process a constant in a code segment. Just push 383 // it on the stack and let the caller deal with it. 384 if (msp != 0) 385 PushToStack(obj); // Can't check this because it may have forwarding ptrs. 386 else 387 { 388 // Normally a root but this can happen if we're following constants in code. 389 // In that case we want to make sure that we don't recurse too deeply and 390 // overflow the C stack. Push the address to the stack before calling 391 // ScanAddressesInObject so that if we come back here msp will be non-zero. 392 // ScanAddressesInObject will empty the stack. 393 PushToStack(obj); 394 MTGCProcessMarkPointers::ScanAddressesInObject(obj, L); 395 // We can only check after we've processed it because if we 396 // have addresses left over from an incomplete partial GC they 397 // may need to forwarded. 398 CheckObject (obj); 399 } 400 401 return obj; 402} 403 404// These functions are only called with pointers held by the runtime system. 405// Weak references can occur in the runtime system, eg. streams and windows. 406// Weak references are not marked and so unreferenced streams and windows 407// can be detected and closed. 408void MTGCProcessMarkPointers::ScanRuntimeAddress(PolyObject **pt, RtsStrength weak) 409{ 410 if (weak == STRENGTH_WEAK) return; 411 *pt = ScanObjectAddress(*pt); 412 CheckPointer (*pt); // Check it after any forwarding pointers have been followed. 413} 414 415// This is called via ScanAddressesInRegion to process the permanent mutables. It is 416// also called from ScanObjectAddress to process root addresses. 417// It processes all the addresses reachable from the object. 418// This is almost the same as RecursiveScan::ScanAddressesInObject. 419void MTGCProcessMarkPointers::ScanAddressesInObject(PolyObject *obj, POLYUNSIGNED lengthWord) 420{ 421 if (OBJ_IS_BYTE_OBJECT(lengthWord)) 422 return; 423 424 while (true) 425 { 426 ASSERT (OBJ_IS_LENGTH(lengthWord)); 427 428 POLYUNSIGNED length = OBJ_OBJECT_LENGTH(lengthWord); 429 PolyWord *baseAddr = (PolyWord*)obj; 430 PolyWord *endWord = baseAddr + length; 431 432 if (OBJ_IS_WEAKREF_OBJECT(lengthWord)) 433 { 434 // Special case. 435 ASSERT(OBJ_IS_MUTABLE_OBJECT(lengthWord)); // Should be a mutable. 436 ASSERT(OBJ_IS_WORD_OBJECT(lengthWord)); // Should be a plain object. 437 // We need to mark the "SOME" values in this object but we don't mark 438 // the references contained within the "SOME". 439 // Mark every word but ignore the result. 440 for (POLYUNSIGNED i = 0; i < length; i++) 441 (void)MarkAndTestForScan(baseAddr+i); 442 // We've finished with this. 443 endWord = baseAddr; 444 } 445 446 else if (OBJ_IS_CODE_OBJECT(lengthWord)) 447 { 448 // Code addresses in the native code versions. 449 // Closure cells are normal (word) objects and code addresses are normal addresses. 450 // It's better to process the whole code object in one go. 451 ScanAddress::ScanAddressesInObject(obj, lengthWord); 452 endWord = baseAddr; // Finished 453 } 454 455 else if (OBJ_IS_CLOSURE_OBJECT(lengthWord)) 456 { 457 // Closure cells in 32-in-64. 458 // The first word is the absolute address of the code ... 459 PolyObject *codeAddr = *(PolyObject**)obj; 460 // except that it is possible we haven't yet set it. 461 if (((uintptr_t)codeAddr & 1) == 0) 462 ScanObjectAddress(codeAddr); 463 // The rest is a normal tuple. 464 baseAddr += sizeof(PolyObject*) / sizeof(PolyWord); 465 } 466 467 // If there are only two addresses in this cell that need to be 468 // followed we follow them immediately and treat this cell as done. 469 // If there are more than two we push the address of this cell on 470 // the stack, follow the first address and then rescan it. That way 471 // list cells are processed once only but we don't overflow the 472 // stack by pushing all the addresses in a very large vector. 473 PolyObject *firstWord = 0; 474 PolyObject *secondWord = 0; 475 PolyWord *restartAddr = 0; 476 477 if (obj == largeObjectCache[locPtr].base) 478 { 479 baseAddr = largeObjectCache[locPtr].current; 480 ASSERT(baseAddr > (PolyWord*)obj && baseAddr < endWord); 481 if (locPtr == 0) locPtr = LARGECACHE_SIZE - 1; else locPtr--; 482 } 483 484 while (baseAddr != endWord) 485 { 486 PolyWord wordAt = *baseAddr; 487 488 if (wordAt.IsDataPtr() && wordAt != PolyWord::FromUnsigned(0)) 489 { 490 // Normal address. We can have words of all zeros at least in the 491 // situation where we have a partially constructed code segment where 492 // the constants at the end of the code have not yet been filled in. 493 if (TestForScan(baseAddr)) 494 { 495 if (firstWord == 0) 496 firstWord = baseAddr->AsObjPtr(); 497 else if (secondWord == 0) 498 { 499 // If we need to rescan because there are three or more words to do 500 // this is the place we need to restart (or the start of the cell if it's 501 // small). 502 restartAddr = baseAddr; 503 secondWord = baseAddr->AsObjPtr(); 504 } 505 else break; // More than two words. 506 } 507 } 508 baseAddr++; 509 } 510 511 if (baseAddr != endWord) 512 // Put this back on the stack while we process the first word 513 PushToStack(obj, length < largeObjectSize ? 0 : restartAddr); 514 else if (secondWord != 0) 515 { 516 // Mark it now because we will process it. 517 PolyObject* writeAble = secondWord; 518 if (secondWord->IsCodeObject()) 519 writeAble = gMem.SpaceForObjectAddress(secondWord)->writeAble(secondWord); 520 writeAble->SetLengthWord(secondWord->LengthWord() | _OBJ_GC_MARK); 521 // Put this on the stack. If this is a list node we will be 522 // pushing the tail. 523 PushToStack(secondWord); 524 } 525 526 if (firstWord != 0) 527 { 528 // Mark it and process it immediately. 529 PolyObject* writeAble = firstWord; 530 if (firstWord->IsCodeObject()) 531 writeAble = gMem.SpaceForObjectAddress(firstWord)->writeAble(firstWord); 532 writeAble->SetLengthWord(firstWord->LengthWord() | _OBJ_GC_MARK); 533 obj = firstWord; 534 } 535 else if (msp == 0) 536 { 537 markStack[msp] = 0; // Really finished 538 return; 539 } 540 else 541 { 542 // Clear the item above the top. This really is finished. 543 if (msp < MARK_STACK_SIZE) markStack[msp] = 0; 544 // Pop the item from the stack but don't overwrite it yet. 545 // This allows another thread to steal it if there really 546 // is nothing else to do. This is only really important 547 // for large objects. 548 obj = markStack[--msp]; // Pop something. 549 } 550 551 lengthWord = obj->LengthWord(); 552 } 553} 554 555// Process a constant within the code. This is a direct copy of ScanAddress::ScanConstant 556// with the addition of the locking. 557void MTGCProcessMarkPointers::ScanConstant(PolyObject *base, byte *addressOfConstant, ScanRelocationKind code) 558{ 559 // If we have newly compiled code the constants may be in the 560 // local heap. MTGCProcessMarkPointers::ScanObjectAddress can 561 // return an updated address for a local address if there is a 562 // forwarding pointer. 563 // Constants can be aligned on any byte offset so another thread 564 // scanning the same code could see an invalid address if it read 565 // the constant while it was being updated. We put a lock round 566 // this just in case. 567 MemSpace *space = gMem.SpaceForAddress(addressOfConstant); 568 PLock *lock = 0; 569 if (space->spaceType == ST_CODE) 570 lock = &((CodeSpace*)space)->spaceLock; 571 572 if (lock != 0) 573 lock->Lock(); 574 PolyObject *p = GetConstantValue(addressOfConstant, code); 575 if (lock != 0) 576 lock->Unlock(); 577 578 if (p != 0) 579 { 580 PolyObject *newVal = ScanObjectAddress(p); 581 if (newVal != p) // Update it if it has changed. 582 { 583 if (lock != 0) 584 lock->Lock(); 585 SetConstantValue(addressOfConstant, newVal, code); 586 if (lock != 0) 587 lock->Unlock(); 588 } 589 } 590} 591 592// Mark all the roots. This is run in the main thread and has the effect 593// of starting new tasks as the scanning runs. 594void MTGCProcessMarkPointers::MarkRoots(void) 595{ 596 ASSERT(nThreads >= 1); 597 ASSERT(nInUse == 0); 598 MTGCProcessMarkPointers *marker = &markStacks[0]; 599 marker->Reset(); 600 marker->active = true; 601 nInUse = 1; 602 603 // Scan the permanent mutable areas. 604 for (std::vector<PermanentMemSpace*>::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) 605 { 606 PermanentMemSpace *space = *i; 607 if (space->isMutable && ! space->byteOnly) 608 marker->ScanAddressesInRegion(space->bottom, space->top); 609 } 610 611 // Scan the RTS roots. 612 GCModules(marker); 613 614 ASSERT(marker->markStack[0] == 0); 615 616 // When this has finished there may well be other tasks running. 617 PLocker lock(&stackLock); 618 marker->active = false; 619 nInUse--; 620} 621 622// This class just allows us to use ScanAddress::ScanAddressesInRegion to call 623// ScanAddressesInObject for each object in the region. 624class Rescanner: public ScanAddress 625{ 626public: 627 Rescanner(MTGCProcessMarkPointers *marker): m_marker(marker) {} 628 629 virtual void ScanAddressesInObject(PolyObject *obj, POLYUNSIGNED lengthWord) 630 { 631 // If it has previously been marked it is known to be reachable but 632 // the contents may not have been scanned if the stack overflowed. 633 if (lengthWord &_OBJ_GC_MARK) 634 m_marker->ScanAddressesInObject(obj, lengthWord); 635 } 636 637 // Have to define this. 638 virtual PolyObject *ScanObjectAddress(PolyObject *base) { ASSERT(false); return 0; } 639 virtual POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt) { ASSERT(false); return 0; } 640 641 bool ScanSpace(MarkableSpace *space); 642private: 643 MTGCProcessMarkPointers *m_marker; 644}; 645 646// Rescan any marked objects in the area between fullGCRescanStart and fullGCRescanEnd. 647// N.B. We may have threads already processing other areas and they could overflow 648// their stacks and change fullGCRescanStart or fullGCRescanEnd. 649bool Rescanner::ScanSpace(MarkableSpace *space) 650{ 651 PolyWord *start, *end; 652 { 653 PLocker lock(&space->spaceLock); 654 start = space->fullGCRescanStart; 655 end = space->fullGCRescanEnd; 656 space->fullGCRescanStart = space->top; 657 space->fullGCRescanEnd = space->bottom; 658 } 659 if (start < end) 660 { 661 if (debugOptions & DEBUG_GC_ENHANCED) 662 Log("GC: Mark: Rescanning from %p to %p\n", start, end); 663 ScanAddressesInRegion(start, end); 664 return true; // Require rescan 665 } 666 else return false; 667} 668 669// When the threads created by marking the roots have completed we need to check that 670// the mark stack has not overflowed. If it has we need to rescan. This rescanning 671// pass may result in a further overflow so if we find we have to rescan we repeat. 672bool MTGCProcessMarkPointers::RescanForStackOverflow() 673{ 674 ASSERT(nThreads >= 1); 675 ASSERT(nInUse == 0); 676 MTGCProcessMarkPointers *marker = &markStacks[0]; 677 marker->Reset(); 678 marker->active = true; 679 nInUse = 1; 680 bool rescan = false; 681 Rescanner rescanner(marker); 682 683 for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) 684 { 685 if (rescanner.ScanSpace(*i)) 686 rescan = true; 687 } 688 for (std::vector<CodeSpace *>::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) 689 { 690 if (rescanner.ScanSpace(*i)) 691 rescan = true; 692 } 693 { 694 PLocker lock(&stackLock); 695 nInUse--; 696 marker->active = false; 697 } 698 return rescan; 699} 700 701static void SetBitmaps(LocalMemSpace *space, PolyWord *pt, PolyWord *top) 702{ 703 while (pt < top) 704 { 705#ifdef POLYML32IN64 706 if ((((uintptr_t)pt) & 4) == 0) 707 { 708 pt++; 709 continue; 710 } 711#endif 712 PolyObject *obj = (PolyObject*)++pt; 713 // If it has been copied by a minor collection skip it 714 if (obj->ContainsForwardingPtr()) 715 { 716 obj = FollowForwarding(obj); 717 ASSERT(obj->ContainsNormalLengthWord()); 718 pt += obj->Length(); 719 } 720 else 721 { 722 POLYUNSIGNED L = obj->LengthWord(); 723 POLYUNSIGNED n = OBJ_OBJECT_LENGTH(L); 724 if (L & _OBJ_GC_MARK) 725 { 726 obj->SetLengthWord(L & ~(_OBJ_GC_MARK)); 727 uintptr_t bitno = space->wordNo(pt); 728 space->bitmap.SetBits(bitno - 1, n + 1); 729 730 if (OBJ_IS_MUTABLE_OBJECT(L)) 731 space->m_marked += n + 1; 732 else 733 space->i_marked += n + 1; 734 735 if ((PolyWord*)obj <= space->fullGCLowerLimit) 736 space->fullGCLowerLimit = (PolyWord*)obj-1; 737 738 if (OBJ_IS_WEAKREF_OBJECT(L)) 739 { 740 // Add this to the limits for the containing area. 741 PolyWord *baseAddr = (PolyWord*)obj; 742 PolyWord *startAddr = baseAddr-1; // Must point AT length word. 743 PolyWord *endObject = baseAddr + n; 744 if (startAddr < space->lowestWeak) space->lowestWeak = startAddr; 745 if (endObject > space->highestWeak) space->highestWeak = endObject; 746 } 747 } 748 pt += n; 749 } 750 } 751} 752 753static void CreateBitmapsTask(GCTaskId *, void *arg1, void *arg2) 754{ 755 LocalMemSpace *lSpace = (LocalMemSpace *)arg1; 756 lSpace->bitmap.ClearBits(0, lSpace->spaceSize()); 757 SetBitmaps(lSpace, lSpace->bottom, lSpace->top); 758} 759 760// Parallel task to check the marks on cells in the code area and 761// turn them into byte areas if they are free. 762static void CheckMarksOnCodeTask(GCTaskId *, void *arg1, void *arg2) 763{ 764 CodeSpace *space = (CodeSpace*)arg1; 765#ifdef POLYML32IN64 766 PolyWord *pt = space->bottom+1; 767#else 768 PolyWord *pt = space->bottom; 769#endif 770 PolyWord *lastFree = 0; 771 POLYUNSIGNED lastFreeSpace = 0; 772 space->largestFree = 0; 773 space->firstFree = 0; 774 while (pt < space->top) 775 { 776 PolyObject *obj = (PolyObject*)(pt+1); 777 // There should not be forwarding pointers 778 ASSERT(obj->ContainsNormalLengthWord()); 779 POLYUNSIGNED L = obj->LengthWord(); 780 POLYUNSIGNED length = OBJ_OBJECT_LENGTH(L); 781 if (L & _OBJ_GC_MARK) 782 { 783 // It's marked - retain it. 784 ASSERT(L & _OBJ_CODE_OBJ); 785 space->writeAble(obj)->SetLengthWord(L & ~(_OBJ_GC_MARK)); // Clear the mark bit 786 lastFree = 0; 787 lastFreeSpace = 0; 788 } 789#ifdef POLYML32IN64 790 else if (length == 0) 791 { 792 // We may have zero filler words to set the correct alignment. 793 // Merge them into a previously free area otherwise leave 794 // them if they're after something allocated. 795 if (lastFree + lastFreeSpace == pt) 796 { 797 lastFreeSpace += length + 1; 798 PolyObject *freeSpace = (PolyObject*)(lastFree + 1); 799 space->writeAble(freeSpace)->SetLengthWord(lastFreeSpace - 1, F_BYTE_OBJ); 800 } 801 } 802#endif 803 else { // Turn it into a byte area i.e. free. It may already be free. 804 if (space->firstFree == 0) space->firstFree = pt; 805 space->headerMap.ClearBit(pt-space->bottom); // Remove the "header" bit 806 if (lastFree + lastFreeSpace == pt) 807 // Merge free spaces. Speeds up subsequent scans. 808 lastFreeSpace += length + 1; 809 else 810 { 811 lastFree = pt; 812 lastFreeSpace = length + 1; 813 } 814 PolyObject *freeSpace = (PolyObject*)(lastFree+1); 815 space->writeAble(freeSpace)->SetLengthWord(lastFreeSpace-1, F_BYTE_OBJ); 816 if (lastFreeSpace > space->largestFree) space->largestFree = lastFreeSpace; 817 } 818 pt += length+1; 819 } 820} 821 822void GCMarkPhase(void) 823{ 824 mainThreadPhase = MTP_GCPHASEMARK; 825 826 // Clear the mark counters and set the rescan limits. 827 for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) 828 { 829 LocalMemSpace *lSpace = *i; 830 lSpace->i_marked = lSpace->m_marked = 0; 831 lSpace->fullGCRescanStart = lSpace->top; 832 lSpace->fullGCRescanEnd = lSpace->bottom; 833 } 834 for (std::vector<CodeSpace *>::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) 835 { 836 CodeSpace *space = *i; 837 space->fullGCRescanStart = space->top; 838 space->fullGCRescanEnd = space->bottom; 839 } 840 841 MTGCProcessMarkPointers::MarkRoots(); 842 gpTaskFarm->WaitForCompletion(); 843 844 // Do we have to rescan because the mark stack overflowed? 845 bool rescan; 846 do { 847 rescan = MTGCProcessMarkPointers::RescanForStackOverflow(); 848 gpTaskFarm->WaitForCompletion(); 849 } while(rescan); 850 851 gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeIntermediate, "Mark"); 852 853 // Turn the marks into bitmap entries. 854 for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) 855 gpTaskFarm->AddWorkOrRunNow(&CreateBitmapsTask, *i, 0); 856 857 // Process the code areas. 858 for (std::vector<CodeSpace *>::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) 859 gpTaskFarm->AddWorkOrRunNow(&CheckMarksOnCodeTask, *i, 0); 860 861 gpTaskFarm->WaitForCompletion(); // Wait for completion of the bitmaps 862 863 gMem.RemoveEmptyCodeAreas(); 864 865 gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeIntermediate, "Bitmap"); 866 867 uintptr_t totalLive = 0; 868 for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) 869 { 870 LocalMemSpace *lSpace = *i; 871 if (! lSpace->isMutable) ASSERT(lSpace->m_marked == 0); 872 totalLive += lSpace->m_marked + lSpace->i_marked; 873 if (debugOptions & DEBUG_GC_ENHANCED) 874 Log("GC: Mark: %s space %p: %" POLYUFMT " immutable words marked, %" POLYUFMT " mutable words marked\n", 875 lSpace->spaceTypeString(), lSpace, 876 lSpace->i_marked, lSpace->m_marked); 877 } 878 if (debugOptions & DEBUG_GC) 879 Log("GC: Mark: Total live data %" POLYUFMT " words\n", totalLive); 880} 881 882// Set up the stacks. 883void initialiseMarkerTables() 884{ 885 unsigned threads = gpTaskFarm->ThreadCount(); 886 if (threads == 0) threads = 1; 887 MTGCProcessMarkPointers::InitStatics(threads); 888} 889