1/* 2 Title: Multi-Threaded Garbage Collector - Copy 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 second, copy, phase of the garbage collector. The previous, 27mark, phase has identified all the live data and set the bits in the bit-maps. 28This phase compacts the memory by copying cells from lower in the segment or 29from other segments. When a cell is copied the length-word is modified to be 30a tomb-stone that gives the new location for the cell. Cells can be copied to 31areas of memory that are shown as free in the bit-maps and the destination area 32is then marked as allocated. Because there are tomb-stones left behind the original 33location of a cell must remain as allocated and its space cannot be reused until the 34GC is complete. 35 36We copy cells in a defined order to avoid copying loops. 37The ordering on the addresses is: 38 Immutable areas (for immutable cells) (highest) 39 Mutable areas 40 Allocation areas (lowest) 41Within each group a lower position in the gMem.lSpaces is higher 42MemMgr::AddLocalSpace enters spaces gMem.lSpaces such that immutable 43areas come before mutable areas which come before allocation areas 44so this reduces to the order in that table. 45Within a space higher addresses are higher. 46So we try to copy data out of the allocation areas and to copy any 47cells that are now immutable out of the mutable areas. We try to copy 48data out of higher numbered spaces in order to try to free them 49completely and to compact data towards the top of a space if we 50can't. 51 52Once a thread has started copying into or out of an area it takes 53ownership of the area and no other thread can use the area. This 54avoids 55*/ 56 57#ifdef HAVE_CONFIG_H 58#include "config.h" 59#elif defined(_WIN32) 60#include "winconfig.h" 61#else 62#error "No configuration file" 63#endif 64 65#ifdef HAVE_ASSERT_H 66#include <assert.h> 67#define ASSERT(x) assert(x) 68#else 69#define ASSERT(x) 70#endif 71 72#ifdef HAVE_STRING_H 73#include <string.h> 74#endif 75 76#include "globals.h" 77#include "machine_dep.h" 78#include "processes.h" 79#include "gc.h" 80#include "scanaddrs.h" 81#include "bitmap.h" 82#include "memmgr.h" 83#include "gctaskfarm.h" 84#include "locking.h" 85#include "diagnostics.h" 86 87static PLock copyLock("Copy"); 88 89// Search the area downwards looking for n consecutive free words. 90// Return the address of the word if successful or 0 on failure. 91// "limit" is the bit position of the bottom of the area or, if we're compacting an area, 92// the bit position of the object we'd like to move to a higher address. 93static inline PolyWord *FindFreeAndAllocate(LocalMemSpace *dst, POLYUNSIGNED limit, POLYUNSIGNED n) 94{ 95 if (dst == 0) return 0; // No current space 96 97 /* SPF's version of the start caching code. SPF 2/10/96 */ 98 // The idea of it is to avoid having to search over an area that is 99 // already known not to have any spaces large enough for an object of 100 // a given size. Knowing that there is no space for an object of 101 // size n implies that there is no space for anything of size larger 102 // than n. SPF's idea is that after finding the space in the bitmap 103 // we update only the element for the size we are looking for rather 104 // than everything larger. 105 unsigned truncated_n = n < NSTARTS ? (unsigned)n : NSTARTS - 1; 106 107 // If we're looking for something larger than last time update 108 // all the entries last time's size and this size. 109 for (unsigned i = dst->start_index; i < truncated_n; i ++) 110 { 111 if (dst->start[i] < dst->start[i+1]) 112 dst->start[i+1] = dst->start[i]; 113 } 114 115 dst->start_index = truncated_n; 116 POLYUNSIGNED start = dst->start[truncated_n]; 117 if (start <= limit) 118 return 0; 119 120 // Look in the bitmap. Returns "start" if it can't find space. 121 POLYUNSIGNED free = dst->bitmap.FindFree(limit, start, n); 122 123 // If we failed to allocate the space (free == start) we set this to 124 // zero to indicate that there is no space for anything of this size 125 // or larger. 126 if (n < NSTARTS) 127 dst->start[n] = free == start ? 0 : free; 128 129 if (free == start) 130 return 0; 131 132 // Allocate the space. 133 dst->bitmap.SetBits(free, n); 134 135 PolyWord *newp = dst->wordAddr(free); /* New object address */ 136 137 // Update dst->upperAllocPtr, so the new object doesn't get trampled. 138 if (newp < dst->upperAllocPtr) 139 dst->upperAllocPtr = newp; 140 141 return newp; 142} 143 144// This does nothing to the addresses but by applying it in ScanConstantsWithinCode we 145// adjust any relative addresses so they are relative to the new location. 146class MTGCProcessIdentity: public ScanAddress { 147public: 148 virtual PolyObject *ScanObjectAddress(PolyObject *base) { return base; } 149}; 150 151// Copy a cell to its new address. 152void CopyObjectToNewAddress(PolyObject *srcAddress, PolyObject *destAddress, POLYUNSIGNED L) 153{ 154 destAddress->SetLengthWord(L); /* copy length word */ 155 156 POLYUNSIGNED n = OBJ_OBJECT_LENGTH(L); 157 158 // Unroll loop for most common cases. 159 switch (n) 160 { 161 default: 162 memcpy(destAddress, srcAddress, n * sizeof(PolyWord)); 163 break; 164 case 4: 165 destAddress->Set(3, srcAddress->Get(3)); 166 case 3: 167 destAddress->Set(2, srcAddress->Get(2)); 168 case 2: 169 destAddress->Set(1, srcAddress->Get(1)); 170 case 1: 171 destAddress->Set(0, srcAddress->Get(0)); 172 } 173 174 // If this is a code object flush out anything from the instruction cache 175 // that might previously have been at this address 176 if (OBJ_IS_CODE_OBJECT(L)) 177 { 178 MTGCProcessIdentity identity; 179 machineDependent->FlushInstructionCache(destAddress, n * sizeof(PolyWord)); 180 // We have to update any relative addresses in the code. 181 machineDependent->ScanConstantsWithinCode(destAddress, srcAddress, OBJ_OBJECT_LENGTH(L), &identity); 182 } 183} 184 185// Find the next space in the sequence. It may return with the space unchanged if it 186// is unable to find a suitable space. 187static bool FindNextSpace(LocalMemSpace *src, LocalMemSpace **dst, bool isMutable, GCTaskId *id) 188{ 189 std::vector<LocalMemSpace*>::iterator m = gMem.lSpaces.begin(); 190 // If we're compressing the space and it's full that's it. 191 if (*dst == src) 192 return false; 193 if (*dst != 0) 194 { 195 // Find the next space after this 196 while (*m != *dst) m++; 197 m++; 198 } 199 for (; m < gMem.lSpaces.end(); m++) { 200 LocalMemSpace *lSpace = *m; 201 if (lSpace == src) 202 { 203 // The only possibility is to compact this area. 204 ASSERT(!isMutable || src->isMutable); 205 *dst = src; 206 return true; // We already own it 207 } 208 if (lSpace->isMutable == isMutable && !lSpace->allocationSpace && lSpace->spaceOwner == 0) 209 { 210 // Now acquire the lock. We have to retest spaceOwner with the lock held. 211 PLocker lock(©Lock); 212 if (lSpace->spaceOwner == 0) 213 { 214 // Change the space. 215 lSpace->spaceOwner = id; 216 *dst = lSpace; // Return the space 217 if (debugOptions & DEBUG_GC_ENHANCED) 218 Log("GC: Copy: copying %s cells from %p to %p\n", 219 isMutable ? "mutable" : "immutable", src, lSpace); 220 return true; 221 } 222 } 223 } 224 return false; 225} 226 227// Copy objects from the source space into an earlier space or up within the 228// current space. 229static void copyAllData(GCTaskId *id, void * /*arg1*/, void * /*arg2*/) 230{ 231 LocalMemSpace *mutableDest = 0, *immutableDest = 0; 232 233 for (std::vector<LocalMemSpace*>::reverse_iterator i = gMem.lSpaces.rbegin(); i != gMem.lSpaces.rend(); i++) 234 { 235 LocalMemSpace *src = *i; 236 237 if (src->spaceOwner == 0) 238 { 239 PLocker lock(©Lock); 240 if (src->spaceOwner == 0) 241 src->spaceOwner = id; 242 else continue; 243 } 244 else if (src->spaceOwner != id) 245 continue; 246 247 if (debugOptions & DEBUG_GC_ENHANCED) 248 Log("GC: Copy: copying area %p (thread %p) %s \n", src, id, src->spaceTypeString()); 249 250 // We start at fullGCLowerLimit which is the lowest marked object in the heap 251 // N.B. It's essential that the first set bit at or above this corresponds 252 // to the length word of a real object. 253 POLYUNSIGNED bitno = src->wordNo(src->fullGCLowerLimit); 254 // Set the limit to the top so we won't rescan this. That can 255 // only happen if copying takes a very short time and the same 256 // thread runs multiple tasks. 257 src->fullGCLowerLimit = src->top; 258 259 // src->highest is the bit position that corresponds to the top of 260 // generation we're copying. 261 POLYUNSIGNED highest = src->wordNo(src->top); 262 263 for (;;) 264 { 265 if (bitno >= highest) break; 266 267 /* SPF version; Invariant: 0 < highest - bitno */ 268 bitno += src->bitmap.CountZeroBits(bitno, highest - bitno); 269 270 if (bitno >= highest) break; 271 272 /* first set bit corresponds to the length word */ 273 PolyWord *old = src->wordAddr(bitno); /* Old object address */ 274 275 PolyObject *obj = (PolyObject*)(old+1); 276 277 POLYUNSIGNED L = obj->LengthWord(); 278 ASSERT (OBJ_IS_LENGTH(L)); 279 280 POLYUNSIGNED n = OBJ_OBJECT_LENGTH(L) + 1 ;/* Length of allocation (including length word) */ 281 bitno += n; 282 283 // Find a mutable space for the mutable objects and an immutable space for 284 // the immutables. We copy objects into earlier spaces or within its own 285 // space but we don't copy an object to a later space. This avoids the 286 // risk of copying an object multiple times. Previously this copied objects 287 // into later spaces but that doesn't work well if we have converted old 288 // saved state segments into local areas. It's much better to delete them 289 // if possible. 290 bool isMutable = OBJ_IS_MUTABLE_OBJECT(L); 291 LocalMemSpace *destSpace = isMutable || immutableDest == 0 ? mutableDest : immutableDest; 292 PolyWord *newp = FindFreeAndAllocate(destSpace, (src == destSpace) ? bitno : 0, n); 293 if (newp == 0 && src != destSpace) 294 { 295 // See if we can find a different space. 296 // N.B. FindNextSpace side-effects mutableDest/immutableDest to give the next space. 297 if (FindNextSpace(src, isMutable ? &mutableDest : &immutableDest, isMutable, id)) 298 { 299 bitno -= n; // Redo this object 300 continue; 301 } 302 // else just leave it 303 } 304 305 if (newp == 0) /* no room */ 306 { 307 // We're not going to move this object 308 // Update src->upperAllocPtr, so the old object doesn't get trampled. 309 if (old < src->upperAllocPtr) 310 src->upperAllocPtr = old; 311 312 // Previously this continued compressing to try to make space available 313 // on the next GC. Normally full GCs are infrequent so the chances are 314 // that at the next GC other data will have been freed. Just stop at 315 // this point. 316 // However if we're compressing a mutable area and there is immutable 317 // data in it we should move those out because the mutable area is scanned 318 // on every partial GC. 319 if (! src->isMutable || src->i_marked == 0) 320 break; 321 } 322 else 323 { 324 PolyObject *destAddress = (PolyObject*)(newp+1); 325 obj->SetForwardingPtr(destAddress); 326 CopyObjectToNewAddress(obj, destAddress, L); 327 328 if (debugOptions & DEBUG_GC_DETAIL) 329 Log("GC: Copy: %p %lu %u -> %p\n", obj, OBJ_OBJECT_LENGTH(L), 330 GetTypeBits(L), destAddress); 331 } 332 } 333 334 if (mutableDest == src) 335 mutableDest = 0; 336 if (immutableDest == src) 337 immutableDest = 0; 338 } 339} 340 341void GCCopyPhase() 342{ 343 mainThreadPhase = MTP_GCPHASECOMPACT; 344 345 for(std::vector<LocalMemSpace*>::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) 346 { 347 LocalMemSpace *lSpace = *i; 348 POLYUNSIGNED highest = lSpace->wordNo(lSpace->top); 349 for (unsigned i = 0; i < NSTARTS; i++) 350 lSpace->start[i] = highest; 351 lSpace->start_index = NSTARTS - 1; 352 lSpace->spaceOwner = 0; 353 // Reset the allocation pointers. This puts garbage (and real data) below them. 354 // At the end of the compaction the allocation pointer will point below the 355 // lowest real data. 356 lSpace->upperAllocPtr = lSpace->top; 357 } 358 359 // Copy the mutable data into a lower area if possible. 360 if (gpTaskFarm->ThreadCount() == 0) 361 copyAllData(globalTask, 0, 0); 362 else 363 { 364 // We start as many tasks as we have threads. If the amount of work to 365 // be done is very small one thread could process more than one task. 366 // Have to be careful because we use the task ID to decide which space 367 // to scan. 368 for (unsigned j = 0; j < gpTaskFarm->ThreadCount(); j++) 369 gpTaskFarm->AddWorkOrRunNow(©AllData, 0, 0); 370 } 371 372 gpTaskFarm->WaitForCompletion(); 373} 374