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