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