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 /*
25 This is the first, mark, phase of the garbage collector. It detects all
26 reachable cells in the area being collected. At the end of the phase the
27 bit-maps associated with the areas will have ones for words belonging to cells
28 that must be retained and zeros for words that can be reused.
29
30 This is now multi-threaded. The mark phase involves setting a bit in the header
31 of each live cell and then a pass over the memory building the bitmaps and clearing
32 this bit. It is unfortunate that we cannot use the GC-bit that is used in
33 forwarding pointers but we may well have forwarded pointers left over from a
34 partially completed minor GC. Using a bit in the header avoids the need for
35 locking since at worst it may involve two threads duplicating some marking.
36
37 The code ensures that each reachable cell is marked at least once but with
38 multiple threads a cell may be marked by more than once cell if the
39 memory is not fully up to date. Each thread has a stack on which it
40 remembers cells that have been marked but not fully scanned. If a
41 thread runs out of cells of its own to scan it can pick a pointer off
42 the stack of another thread and scan that. The original thread will
43 still scan it some time later but it should find that the addresses
44 in it have all been marked and it can simply pop this off. This is
45 all done without locking. Stacks are only modified by the owning
46 thread and when they pop anything they write zero in its place.
47 Other threads only need to search for a zero to find if they are
48 at the top and if they get a pointer that has already been scanned
49 then this is safe. The only assumption made about the memory is
50 that all the bits of a word are updated together so that a thread
51 will always read a value that is a valid pointer.
52
53 Many 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
86 class MTGCProcessMarkPointers: public ScanAddress
87 {
88 public:
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.
ScanAddressesInObject(PolyObject * base)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.
ScanCodeAddressAt(PolyObject ** pt)101 POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt) { ASSERT(0); return 0; }
102
103 static void MarkPointersTask(GCTaskId *, void *arg1, void *arg2);
104
InitStatics(unsigned threads)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
115 private:
116 bool TestForScan(PolyWord *pt);
117 void MarkAndTestForScan(PolyWord *pt);
118 void Reset();
119
PushToStack(PolyObject * obj,PolyWord * currentPtr=0)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;
158 protected:
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.
167 MTGCProcessMarkPointers *MTGCProcessMarkPointers::markStacks;
168 unsigned MTGCProcessMarkPointers::nThreads, MTGCProcessMarkPointers::nInUse;
169 PLock 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.
FollowForwarding(PolyObject * obj)174 inline PolyObject *FollowForwarding(PolyObject *obj)
175 {
176 while (obj->ContainsForwardingPtr())
177 obj = obj->GetForwardingPtr();
178 return obj;
179 }
180
MTGCProcessMarkPointers()181 MTGCProcessMarkPointers::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.
Reset()195 void 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.
StackOverflow(PolyObject * obj)210 void 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.
ForkNew(PolyObject * obj)228 bool 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.
MarkPointersTask(GCTaskId *,void * arg1,void * arg2)255 void 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.
TestForScan(PolyWord * pt)300 bool 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
MarkAndTestForScan(PolyWord * pt)336 void 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.
ScanObjectAddress(PolyObject * obj)349 PolyObject *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.
ScanRuntimeAddress(PolyObject ** pt,RtsStrength weak)408 void 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.
ScanAddressesInObject(PolyObject * obj,POLYUNSIGNED lengthWord)419 void 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.
ScanConstant(PolyObject * base,byte * addressOfConstant,ScanRelocationKind code)557 void 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.
MarkRoots(void)594 void 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.
624 class Rescanner: public ScanAddress
625 {
626 public:
Rescanner(MTGCProcessMarkPointers * marker)627 Rescanner(MTGCProcessMarkPointers *marker): m_marker(marker) {}
628
ScanAddressesInObject(PolyObject * obj,POLYUNSIGNED lengthWord)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.
ScanObjectAddress(PolyObject * base)638 virtual PolyObject *ScanObjectAddress(PolyObject *base) { ASSERT(false); return 0; }
ScanCodeAddressAt(PolyObject ** pt)639 virtual POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt) { ASSERT(false); return 0; }
640
641 bool ScanSpace(MarkableSpace *space);
642 private:
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.
ScanSpace(MarkableSpace * space)649 bool 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.
RescanForStackOverflow()672 bool 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
SetBitmaps(LocalMemSpace * space,PolyWord * pt,PolyWord * top)701 static 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
CreateBitmapsTask(GCTaskId *,void * arg1,void * arg2)753 static 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.
CheckMarksOnCodeTask(GCTaskId *,void * arg1,void * arg2)762 static 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
GCMarkPhase(void)822 void 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.
initialiseMarkerTables()883 void initialiseMarkerTables()
884 {
885 unsigned threads = gpTaskFarm->ThreadCount();
886 if (threads == 0) threads = 1;
887 MTGCProcessMarkPointers::InitStatics(threads);
888 }
889