/
gc.cpp
434 lines (370 loc) · 15.2 KB
/
gc.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
/*
Title: Multi-Threaded Garbage Collector
Copyright (c) 2010-12, 2019, 2020 David C. J. Matthews
Based on the original garbage collector code
Copyright 2000-2008
Cambridge University Technical Services Limited
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#elif defined(_WIN32)
#include "winconfig.h"
#else
#error "No configuration file"
#endif
#ifdef HAVE_ASSERT_H
#include <assert.h>
#define ASSERT(x) assert(x)
#else
#define ASSERT(x)
#endif
#include "globals.h"
#include "run_time.h"
#include "machine_dep.h"
#include "diagnostics.h"
#include "processes.h"
#include "timing.h"
#include "gc.h"
#include "scanaddrs.h"
#include "check_objects.h"
#include "osmem.h"
#include "bitmap.h"
#include "rts_module.h"
#include "memmgr.h"
#include "gctaskfarm.h"
#include "mpoly.h"
#include "statistics.h"
#include "profiling.h"
#include "heapsizing.h"
#include "gc_progress.h"
static GCTaskFarm gTaskFarm; // Global task farm.
GCTaskFarm *gpTaskFarm = &gTaskFarm;
// If the GC converts a weak ref from SOME to NONE it sets this ref. It can be
// cleared by the signal handler thread. There's no need for a lock since it
// is only set during GC and only cleared when not GCing.
bool convertedWeak = false;
/*
How the garbage collector works.
The GC has two phases. The minor (quick) GC is a copying collector that
copies data from the allocation area into the mutable and immutable area.
The major collector is started when either the mutable or the immutable
area is full. The major collector uses a mark/sweep scheme.
The GC has three phases:
1. Mark phase.
Working from the roots; which are the the permanent mutable segments and
the RTS roots (e.g. thread stacks), mark all reachable cells.
Marking involves setting bits in the bitmap for reachable words.
2. Compact phase.
Marked objects are copied to try to compact, upwards, the heap segments. When
an object is moved the length word of the object in the old location is set as
a tombstone that points to its new location. In particular this means that we
cannot reuse the space where an object previously was during the compaction phase.
Immutable objects are moved into immutable segments. When an object is moved
to a new location the bits are set in the bitmap as though the object had been
marked at that location.
3. Update phase.
The roots and objects marked during the first two phases are scanned and any
addresses for moved objects are updated. The lowest address used in the area
then becomes the base of the area for future allocations.
There is a sharing phase which may be performed before the mark phase. This
merges immutable cells with the same contents with the aim of reducing the
size of the live data. It is expensive so is not performed by default.
Updated DCJM 12/06/12
*/
static bool doGC(const POLYUNSIGNED wordsRequiredToAllocate)
{
gHeapSizeParameters.RecordAtStartOfMajorGC();
gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeStart);
globalStats.incCount(PSC_GC_FULLGC);
// Remove any empty spaces. There will not normally be any except
// if we have triggered a full GC as a result of detecting paging in the
// minor GC but in that case we want to try to stop the system writing
// out areas that are now empty.
gMem.RemoveEmptyLocals();
if (debugOptions & DEBUG_GC)
Log("GC: Full GC, %lu words required %" PRI_SIZET " spaces\n", wordsRequiredToAllocate, gMem.lSpaces.size());
if (debugOptions & DEBUG_HEAPSIZE)
gMem.ReportHeapSizes("Full GC (before)");
// Data sharing pass.
if (gHeapSizeParameters.PerformSharingPass())
{
globalStats.incCount(PSC_GC_SHARING);
GCSharingPhase();
}
gcProgressBeginMajorGC(); // The GC sharing phase is treated separately
/*
* There is a really weird bug somewhere. An extra bit may be set in the bitmap during
* the mark phase. It seems to be related to heavy swapping activity. Duplicating the
* bitmap causes it to occur only in one copy and write-protecting the bitmap apart from
* when it is actually being updated does not result in a seg-fault. So far I've only
* seen it on 64-bit Linux but it may be responsible for other crashes. The work-around
* is to check the number of bits set in the bitmap and repeat the mark phase if it does
* not match.
*/
for (unsigned p = 3; p > 0; p--)
{
for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *lSpace = *i;
ASSERT (lSpace->top >= lSpace->upperAllocPtr);
ASSERT (lSpace->upperAllocPtr >= lSpace->lowerAllocPtr);
ASSERT (lSpace->lowerAllocPtr >= lSpace->bottom);
// Set upper and lower limits of weak refs.
lSpace->highestWeak = lSpace->bottom;
lSpace->lowestWeak = lSpace->top;
lSpace->fullGCLowerLimit = lSpace->top;
// Put dummy objects in the unused space. This allows
// us to scan over the whole of the space.
gMem.FillUnusedSpace(lSpace->lowerAllocPtr,
lSpace->upperAllocPtr-lSpace->lowerAllocPtr);
}
// Set limits of weak refs.
for (std::vector<PermanentMemSpace*>::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++)
{
PermanentMemSpace *pSpace = *i;
pSpace->highestWeak = pSpace->bottom;
pSpace->lowestWeak = pSpace->top;
}
/* Mark phase */
GCMarkPhase();
uintptr_t bitCount = 0, markCount = 0;
for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *lSpace = *i;
markCount += lSpace->i_marked + lSpace->m_marked;
bitCount += lSpace->bitmap.CountSetBits(lSpace->spaceSize());
}
if (markCount == bitCount)
break;
else
{
// Report an error. If this happens again we crash.
Log("GC: Count error mark count %lu, bitCount %lu\n", markCount, bitCount);
if (p == 1)
{
ASSERT(markCount == bitCount);
}
}
}
for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *lSpace = *i;
// Reset the allocation pointers. They will be set to the
// limits of the retained data.
#ifdef POLYML32IN64
lSpace->lowerAllocPtr = lSpace->bottom+1; // Must be odd-word aligned
lSpace->lowerAllocPtr[-1] = PolyWord::FromUnsigned(0);
#else
lSpace->lowerAllocPtr = lSpace->bottom;
#endif
lSpace->upperAllocPtr = lSpace->top;
}
gcProgressSetPercent(25);
if (debugOptions & DEBUG_GC) Log("GC: Check weak refs\n");
/* Detect unreferenced streams, windows etc. */
GCheckWeakRefs();
gcProgressSetPercent(50);
// Check that the heap is not overfull. We make sure the marked
// mutable and immutable data is no more than 90% of the
// corresponding areas. This is a very coarse adjustment.
{
uintptr_t iMarked = 0, mMarked = 0;
uintptr_t iSpace = 0, mSpace = 0;
for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *lSpace = *i;
iMarked += lSpace->i_marked;
mMarked += lSpace->m_marked;
if (! lSpace->allocationSpace)
{
if (lSpace->isMutable)
mSpace += lSpace->spaceSize();
else
iSpace += lSpace->spaceSize();
}
}
// Add space if necessary and possible.
while (iMarked > iSpace - iSpace/10 && gHeapSizeParameters.AddSpaceBeforeCopyPhase(false) != 0)
iSpace += gMem.DefaultSpaceSize();
while (mMarked > mSpace - mSpace/10 && gHeapSizeParameters.AddSpaceBeforeCopyPhase(true) != 0)
mSpace += gMem.DefaultSpaceSize();
}
/* Compact phase */
GCCopyPhase();
gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeIntermediate, "Copy");
gcProgressSetPercent(75);
// Update Phase.
if (debugOptions & DEBUG_GC) Log("GC: Update\n");
GCUpdatePhase();
gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeIntermediate, "Update");
{
uintptr_t iUpdated = 0, mUpdated = 0, iMarked = 0, mMarked = 0;
for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *lSpace = *i;
iMarked += lSpace->i_marked;
mMarked += lSpace->m_marked;
if (lSpace->isMutable)
mUpdated += lSpace->updated;
else
iUpdated += lSpace->updated;
}
ASSERT(iUpdated+mUpdated == iMarked+mMarked);
}
// Delete empty spaces.
gMem.RemoveEmptyLocals();
if (debugOptions & DEBUG_GC_ENHANCED)
{
for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *lSpace = *i;
Log("GC: %s space %p %" PRI_SIZET " free in %" PRI_SIZET " words %2.1f%% full\n", lSpace->spaceTypeString(),
lSpace, lSpace->freeSpace(), lSpace->spaceSize(),
((float)lSpace->allocatedSpace()) * 100 / (float)lSpace->spaceSize());
}
}
// Compute values for statistics
globalStats.setSize(PSS_AFTER_LAST_GC, 0);
globalStats.setSize(PSS_AFTER_LAST_FULLGC, 0);
globalStats.setSize(PSS_ALLOCATION, 0);
globalStats.setSize(PSS_ALLOCATION_FREE, 0);
for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
{
LocalMemSpace *space = *i;
uintptr_t free = space->freeSpace();
globalStats.incSize(PSS_AFTER_LAST_GC, free*sizeof(PolyWord));
globalStats.incSize(PSS_AFTER_LAST_FULLGC, free*sizeof(PolyWord));
if (space->allocationSpace)
{
if (space->allocatedSpace() > space->freeSpace()) // It's more than half full
gMem.ConvertAllocationSpaceToLocal(space);
else
{
globalStats.incSize(PSS_ALLOCATION, free*sizeof(PolyWord));
globalStats.incSize(PSS_ALLOCATION_FREE, free*sizeof(PolyWord));
}
}
#ifdef FILL_UNUSED_MEMORY
memset(space->bottom, 0xaa, (char*)space->upperAllocPtr - (char*)space->bottom);
#endif
if (debugOptions & DEBUG_GC_ENHANCED)
Log("GC: %s space %p %" PRI_SIZET " free in %" PRI_SIZET " words %2.1f%% full\n", space->spaceTypeString(),
space, space->freeSpace(), space->spaceSize(),
((float)space->allocatedSpace()) * 100 / (float)space->spaceSize());
}
// End of garbage collection
gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeEnd);
// Now we've finished we can adjust the heap sizes.
gHeapSizeParameters.AdjustSizeAfterMajorGC(wordsRequiredToAllocate);
gHeapSizeParameters.resetMajorTimingData();
bool haveSpace = gMem.CheckForAllocation(wordsRequiredToAllocate);
// Invariant: the bitmaps are completely clean.
if (debugOptions & DEBUG_GC)
{
if (haveSpace)
Log("GC: Completed successfully\n");
else Log("GC: Completed with insufficient space\n");
}
if (debugOptions & DEBUG_HEAPSIZE)
gMem.ReportHeapSizes("Full GC (after)");
// if (profileMode == kProfileLiveData || profileMode == kProfileLiveMutables)
// printprofile();
CheckMemory();
return haveSpace; // Completed
}
// Create the initial heap. hsize, isize and msize are the requested heap sizes
// from the user arguments in units of kbytes.
// Fills in the defaults and attempts to allocate the heap. If the heap size
// is too large it allocates as much as it can. The default heap size is half the
// physical memory.
void CreateHeap()
{
// Create an initial allocation space.
if (gMem.CreateAllocationSpace(gMem.DefaultSpaceSize()) == 0)
Exit("Insufficient memory to allocate the heap");
// Create the task farm if required
if (userOptions.gcthreads != 1)
{
if (! gTaskFarm.Initialise(userOptions.gcthreads, 100))
Crash("Unable to initialise the GC task farm");
}
// Set up the stacks for the mark phase.
initialiseMarkerTables();
}
class FullGCRequest: public MainThreadRequest
{
public:
FullGCRequest(): MainThreadRequest(MTP_GCPHASEMARK) {}
virtual void Perform()
{
doGC (0);
}
};
class QuickGCRequest: public MainThreadRequest
{
public:
QuickGCRequest(POLYUNSIGNED words): MainThreadRequest(MTP_GCPHASEMARK), wordsRequired(words) {}
virtual void Perform()
{
result =
#ifndef DEBUG_ONLY_FULL_GC
// If DEBUG_ONLY_FULL_GC is defined then we skip the partial GC.
RunQuickGC(wordsRequired) ||
#endif
doGC (wordsRequired);
}
bool result;
POLYUNSIGNED wordsRequired;
};
// Perform a full garbage collection. This is called either from ML via the full_gc RTS call
// or from various RTS functions such as open_file to try to recover dropped file handles.
void FullGC(TaskData *taskData)
{
FullGCRequest request;
processes->MakeRootRequest(taskData, &request);
if (convertedWeak)
// Notify the signal thread to broadcast on the condition var when
// the GC is complete. We mustn't call SignalArrived within the GC
// because it locks schedLock and the main GC thread already holds schedLock.
processes->SignalArrived();
}
// This is the normal call when memory is exhausted and we need to garbage collect.
bool QuickGC(TaskData *taskData, POLYUNSIGNED wordsRequiredToAllocate)
{
QuickGCRequest request(wordsRequiredToAllocate);
processes->MakeRootRequest(taskData, &request);
if (convertedWeak)
processes->SignalArrived();
return request.result;
}
// Called in RunShareData. This is called as a root function
void FullGCForShareCommonData(void)
{
doGC(0);
}
// RTS module for the GC. Only used for ForkChild.
class GarbageCollectModule : public RtsModule
{
public:
virtual void ForkChild(void);
};
// Set single threaded mode. This is only used in a child process after
// Posix fork in case there is a GC before the exec.
void GarbageCollectModule::ForkChild(void)
{
gpTaskFarm->SetSingleThreaded();
initialiseMarkerTables();
}
// Declare this. It will be automatically added to the table.
static GarbageCollectModule gcModule;