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