1/*
2    Title:      Multi-Threaded Garbage Collector - Update phase
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/*
26This is the third, update, phase of the garbage collector.  The previous, copy,
27phase will have moved cells in memory.  The update phase goes through all cells
28that could contain an address of a cell that has been moved and looks for a
29tomb-stone that contains its new location.
30*/
31#ifdef HAVE_CONFIG_H
32#include "config.h"
33#elif defined(_WIN32)
34#include "winconfig.h"
35#else
36#error "No configuration file"
37#endif
38
39#ifdef HAVE_ASSERT_H
40#include <assert.h>
41#define ASSERT(x)   assert(x)
42#else
43#define ASSERT(x)
44#endif
45
46#include "globals.h"
47#include "run_time.h"
48#include "processes.h"
49#include "gc.h"
50#include "scanaddrs.h"
51#include "check_objects.h"
52#include "bitmap.h"
53#include "memmgr.h"
54#include "gctaskfarm.h"
55#include "diagnostics.h"
56
57class MTGCProcessUpdate: public ScanAddress
58{
59public:
60    virtual POLYUNSIGNED ScanAddressAt(PolyWord *pt);
61    virtual void ScanRuntimeAddress(PolyObject **pt, RtsStrength weak);
62    virtual PolyObject *ScanObjectAddress(PolyObject *base);
63
64    void UpdateObjectsInArea(LocalMemSpace *area);
65
66private:
67    static void UpdateAddress(PolyObject *&obj)
68    {
69        while (obj->ContainsForwardingPtr())
70            obj = obj->GetForwardingPtr();
71    }
72};
73
74/*********************************************************************/
75/* This function is called in the update phase to update pointers to */
76/* objects in the gc area that are in old mutable segments.          */
77/*********************************************************************/
78PolyObject *MTGCProcessUpdate::ScanObjectAddress(PolyObject *obj)
79{
80    PolyWord val = obj;
81
82    LocalMemSpace *space = gMem.LocalSpaceForAddress(val.AsStackAddr()-1);
83    if (space != 0)
84    {
85        UpdateAddress(obj);
86        ASSERT(obj->ContainsNormalLengthWord());
87    }
88    return obj;
89}
90
91void MTGCProcessUpdate::ScanRuntimeAddress(PolyObject **pt, RtsStrength/* weak*/)
92/* weak is not used, but needed so type of the function is correct */
93{
94    PolyObject *obj = *pt;
95    if (obj->ContainsForwardingPtr())
96    {
97        UpdateAddress(obj);
98        *pt = obj;
99    }
100}
101
102// Update the addresses in a group of words.
103POLYUNSIGNED MTGCProcessUpdate::ScanAddressAt(PolyWord *pt)
104{
105    PolyWord val = *pt;
106
107    if (val.IsTagged())
108        return 0;
109
110    // It looked like it would be possible to simplify this code and
111    // just call ContainsForwardingPtr on any address.
112    // Profiling shows that it's quite important to avoid calling
113    // ContainsForwardingPtr unnecessarily. I guess the reason is that
114    // it actually accesses the memory referenced by the address and it
115    // is unlikely to be in the cache.
116
117    PolyObject *obj = val.AsObjPtr();
118    if (obj->ContainsForwardingPtr())
119    {
120        UpdateAddress(obj);
121        *pt = obj;
122    }
123    return 0;
124}
125
126// Updates the addresses for objects in the area with the "allocated" bit set.
127// It processes the area between area->pointer and the bit corresponding to area->highest.
128// area->highest corresponds to gen_top i.e. we don't process older generations.
129void MTGCProcessUpdate::UpdateObjectsInArea(LocalMemSpace *area)
130{
131    PolyWord *pt      = area->upperAllocPtr;
132    POLYUNSIGNED   bitno   = area->wordNo(pt);
133    POLYUNSIGNED   highest = area->wordNo(area->top);
134
135    for (;;)
136    {
137        ASSERT(bitno <= highest);
138        /* Zero unused words.  This is necessary so that
139           ScanAddressesInRegion can work.  It requires the allocated
140           area of memory to contain either objects with a valid length
141           word or forwarding pointer or zeros.  We should only be
142           zeroing words that we couldn't fill with real data so it
143           shouldn't be too much.  Profiling showed that using dummy
144           byte objects here didn't make a measurable difference,
145        */
146        while (bitno < highest && !area->bitmap.TestBit(bitno))
147        {
148            *pt++ = PolyWord::FromUnsigned(0);
149            bitno++;
150        }
151
152        if (bitno == highest) {
153            // Have reached the top of the area
154            ASSERT(pt == area->top);
155            break;
156        }
157
158        /* first set bit corresponds to the length word */
159        pt++;
160        PolyObject *obj = (PolyObject*)pt;
161        POLYUNSIGNED L = obj->LengthWord();
162        bitno++;
163
164        if (obj->ContainsForwardingPtr())
165        {
166            // Skip over moved objects.  We have to find the new location to find
167            // its length.
168            UpdateAddress(obj);
169            POLYUNSIGNED length = obj->Length();
170            pt    += length;
171            bitno += length;
172        }
173        else // Contains real object
174        {
175
176            if (OBJ_IS_WORD_OBJECT(L))
177            {
178                POLYUNSIGNED length = OBJ_OBJECT_LENGTH(L);
179
180                area->updated += length+1;
181
182                while (length--)
183                {
184                    PolyWord val = *pt;
185
186                    if (! val.IsTagged() && val != PolyWord::FromUnsigned(0))
187                    {
188                        PolyObject *obj = val.AsObjPtr();
189
190                        if (obj->ContainsForwardingPtr())
191                        {
192                            UpdateAddress(obj);
193                            *pt = obj;
194                        }
195                    }
196
197                    pt++;
198                    bitno++;
199                }
200            }
201
202            else /* !OBJ_IS_WORD_OBJECT(L) */
203            {
204                POLYUNSIGNED length = OBJ_OBJECT_LENGTH(L);
205                area->updated += length+1;
206                ScanAddressesInObject(obj, L);
207                pt    += length;
208                bitno += length;
209            } /* !OBJ_IS_WORD_OBJECT(L) */
210
211            CheckObject(obj); // Can check it after it's been updated
212        }  /* !OBJ_IS_POINTER(L) */
213    } /* for loop */
214}
215
216// Task to update addresses in a local area.
217static void updateLocalArea(GCTaskId*, void *arg1, void *arg2)
218{
219    MTGCProcessUpdate *processUpdate = (MTGCProcessUpdate *)arg1;
220    LocalMemSpace *space = (LocalMemSpace *)arg2;
221    if (debugOptions & DEBUG_GC_ENHANCED)
222        Log("GC: Update local area %p\n", space);
223    // Process the current generation for mutable or immutable areas.
224    processUpdate->UpdateObjectsInArea(space);
225    if (debugOptions & DEBUG_GC_ENHANCED)
226        Log("GC: Completed local update for %p. %lu words updated\n", space, space->updated);
227}
228
229// Task to update addresses in a non-local area.
230static void updateNonLocalMutableArea(GCTaskId*, void *arg1, void *arg2)
231{
232    MTGCProcessUpdate *processUpdate = (MTGCProcessUpdate *)arg1;
233    MemSpace *space = (MemSpace *)arg2;
234    if (debugOptions & DEBUG_GC_ENHANCED)
235        Log("GC: Update non-local mutable area %p\n", space);
236    processUpdate->ScanAddressesInRegion(space->bottom, space->top);
237    if (debugOptions & DEBUG_GC_ENHANCED)
238        Log("GC: Completed non-local mutable update for %p\n", space);
239}
240
241// Task to update addresses maintained by the RTS itself.
242static void updateGCProcAddresses(GCTaskId*, void *arg1, void *)
243{
244    MTGCProcessUpdate *processUpdate = (MTGCProcessUpdate *)arg1;
245    GCModules(processUpdate);
246}
247
248void GCUpdatePhase()
249{
250    /* Update phase */
251    mainThreadPhase = MTP_GCPHASEUPDATE;
252
253    /* Invariant: at most the first (gen_top - bottom) bits of each bitmap can be dirty here. */
254    for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
255        (*i)->updated = 0;
256
257    // We can do the updates in parallel since they don't interfere at all.
258    MTGCProcessUpdate processUpdate;
259
260    // Process local areas.
261    for (std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++)
262    {
263        LocalMemSpace *space = *i;
264        // As well as updating the addresses this also clears the bitmaps.
265        gpTaskFarm->AddWorkOrRunNow(&updateLocalArea, &processUpdate, space);
266    }
267    // Scan the permanent mutable areas and the code areas.
268    for (std::vector<PermanentMemSpace*>::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++)
269    {
270        PermanentMemSpace *space = *i;
271        if (space->isMutable && ! space->byteOnly)
272            gpTaskFarm->AddWorkOrRunNow(&updateNonLocalMutableArea, &processUpdate, space);
273    }
274    for (std::vector<CodeSpace *>::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++)
275    {
276        CodeSpace *space = *i;
277        gpTaskFarm->AddWorkOrRunNow(&updateNonLocalMutableArea, &processUpdate, space);
278        // We could remove the mutable bit if there are no longer any mutable code objects
279        // but it's easier to leave that to the minor GC.
280    }
281
282    // Update addresses in RTS modules.
283    gpTaskFarm->AddWorkOrRunNow(&updateGCProcAddresses, &processUpdate, 0);
284    // Wait for these to complete before proceeding.
285    gpTaskFarm->WaitForCompletion();
286}
287