mark-compact.cc revision a7e24c173cf37484693b9abb38e494fa7bd7baeb
1// Copyright 2006-2008 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#include "v8.h" 29 30#include "execution.h" 31#include "global-handles.h" 32#include "ic-inl.h" 33#include "mark-compact.h" 34#include "stub-cache.h" 35 36namespace v8 { 37namespace internal { 38 39// ------------------------------------------------------------------------- 40// MarkCompactCollector 41 42bool MarkCompactCollector::force_compaction_ = false; 43bool MarkCompactCollector::compacting_collection_ = false; 44bool MarkCompactCollector::compact_on_next_gc_ = false; 45 46int MarkCompactCollector::previous_marked_count_ = 0; 47GCTracer* MarkCompactCollector::tracer_ = NULL; 48 49 50#ifdef DEBUG 51MarkCompactCollector::CollectorState MarkCompactCollector::state_ = IDLE; 52 53// Counters used for debugging the marking phase of mark-compact or mark-sweep 54// collection. 55int MarkCompactCollector::live_bytes_ = 0; 56int MarkCompactCollector::live_young_objects_ = 0; 57int MarkCompactCollector::live_old_data_objects_ = 0; 58int MarkCompactCollector::live_old_pointer_objects_ = 0; 59int MarkCompactCollector::live_code_objects_ = 0; 60int MarkCompactCollector::live_map_objects_ = 0; 61int MarkCompactCollector::live_cell_objects_ = 0; 62int MarkCompactCollector::live_lo_objects_ = 0; 63#endif 64 65void MarkCompactCollector::CollectGarbage() { 66 // Make sure that Prepare() has been called. The individual steps below will 67 // update the state as they proceed. 68 ASSERT(state_ == PREPARE_GC); 69 70 // Prepare has selected whether to compact the old generation or not. 71 // Tell the tracer. 72 if (IsCompacting()) tracer_->set_is_compacting(); 73 74 MarkLiveObjects(); 75 76 if (FLAG_collect_maps) ClearNonLiveTransitions(); 77 78 SweepLargeObjectSpace(); 79 80 if (IsCompacting()) { 81 EncodeForwardingAddresses(); 82 83 UpdatePointers(); 84 85 RelocateObjects(); 86 87 RebuildRSets(); 88 89 } else { 90 SweepSpaces(); 91 } 92 93 Finish(); 94 95 // Save the count of marked objects remaining after the collection and 96 // null out the GC tracer. 97 previous_marked_count_ = tracer_->marked_count(); 98 ASSERT(previous_marked_count_ == 0); 99 tracer_ = NULL; 100} 101 102 103void MarkCompactCollector::Prepare(GCTracer* tracer) { 104 // Rather than passing the tracer around we stash it in a static member 105 // variable. 106 tracer_ = tracer; 107 108#ifdef DEBUG 109 ASSERT(state_ == IDLE); 110 state_ = PREPARE_GC; 111#endif 112 ASSERT(!FLAG_always_compact || !FLAG_never_compact); 113 114 compacting_collection_ = 115 FLAG_always_compact || force_compaction_ || compact_on_next_gc_; 116 compact_on_next_gc_ = false; 117 118 if (FLAG_never_compact) compacting_collection_ = false; 119 if (FLAG_collect_maps) CreateBackPointers(); 120 121#ifdef DEBUG 122 if (compacting_collection_) { 123 // We will write bookkeeping information to the remembered set area 124 // starting now. 125 Page::set_rset_state(Page::NOT_IN_USE); 126 } 127#endif 128 129 PagedSpaces spaces; 130 while (PagedSpace* space = spaces.next()) { 131 space->PrepareForMarkCompact(compacting_collection_); 132 } 133 134#ifdef DEBUG 135 live_bytes_ = 0; 136 live_young_objects_ = 0; 137 live_old_pointer_objects_ = 0; 138 live_old_data_objects_ = 0; 139 live_code_objects_ = 0; 140 live_map_objects_ = 0; 141 live_cell_objects_ = 0; 142 live_lo_objects_ = 0; 143#endif 144} 145 146 147void MarkCompactCollector::Finish() { 148#ifdef DEBUG 149 ASSERT(state_ == SWEEP_SPACES || state_ == REBUILD_RSETS); 150 state_ = IDLE; 151#endif 152 // The stub cache is not traversed during GC; clear the cache to 153 // force lazy re-initialization of it. This must be done after the 154 // GC, because it relies on the new address of certain old space 155 // objects (empty string, illegal builtin). 156 StubCache::Clear(); 157 158 // If we've just compacted old space there's no reason to check the 159 // fragmentation limit. Just return. 160 if (HasCompacted()) return; 161 162 // We compact the old generation on the next GC if it has gotten too 163 // fragmented (ie, we could recover an expected amount of space by 164 // reclaiming the waste and free list blocks). 165 static const int kFragmentationLimit = 15; // Percent. 166 static const int kFragmentationAllowed = 1 * MB; // Absolute. 167 int old_gen_recoverable = 0; 168 int old_gen_used = 0; 169 170 OldSpaces spaces; 171 while (OldSpace* space = spaces.next()) { 172 old_gen_recoverable += space->Waste() + space->AvailableFree(); 173 old_gen_used += space->Size(); 174 } 175 176 int old_gen_fragmentation = 177 static_cast<int>((old_gen_recoverable * 100.0) / old_gen_used); 178 if (old_gen_fragmentation > kFragmentationLimit && 179 old_gen_recoverable > kFragmentationAllowed) { 180 compact_on_next_gc_ = true; 181 } 182} 183 184 185// ------------------------------------------------------------------------- 186// Phase 1: tracing and marking live objects. 187// before: all objects are in normal state. 188// after: a live object's map pointer is marked as '00'. 189 190// Marking all live objects in the heap as part of mark-sweep or mark-compact 191// collection. Before marking, all objects are in their normal state. After 192// marking, live objects' map pointers are marked indicating that the object 193// has been found reachable. 194// 195// The marking algorithm is a (mostly) depth-first (because of possible stack 196// overflow) traversal of the graph of objects reachable from the roots. It 197// uses an explicit stack of pointers rather than recursion. The young 198// generation's inactive ('from') space is used as a marking stack. The 199// objects in the marking stack are the ones that have been reached and marked 200// but their children have not yet been visited. 201// 202// The marking stack can overflow during traversal. In that case, we set an 203// overflow flag. When the overflow flag is set, we continue marking objects 204// reachable from the objects on the marking stack, but no longer push them on 205// the marking stack. Instead, we mark them as both marked and overflowed. 206// When the stack is in the overflowed state, objects marked as overflowed 207// have been reached and marked but their children have not been visited yet. 208// After emptying the marking stack, we clear the overflow flag and traverse 209// the heap looking for objects marked as overflowed, push them on the stack, 210// and continue with marking. This process repeats until all reachable 211// objects have been marked. 212 213static MarkingStack marking_stack; 214 215 216static inline HeapObject* ShortCircuitConsString(Object** p) { 217 // Optimization: If the heap object pointed to by p is a non-symbol 218 // cons string whose right substring is Heap::empty_string, update 219 // it in place to its left substring. Return the updated value. 220 // 221 // Here we assume that if we change *p, we replace it with a heap object 222 // (ie, the left substring of a cons string is always a heap object). 223 // 224 // The check performed is: 225 // object->IsConsString() && !object->IsSymbol() && 226 // (ConsString::cast(object)->second() == Heap::empty_string()) 227 // except the maps for the object and its possible substrings might be 228 // marked. 229 HeapObject* object = HeapObject::cast(*p); 230 MapWord map_word = object->map_word(); 231 map_word.ClearMark(); 232 InstanceType type = map_word.ToMap()->instance_type(); 233 if ((type & kShortcutTypeMask) != kShortcutTypeTag) return object; 234 235 Object* second = reinterpret_cast<ConsString*>(object)->unchecked_second(); 236 if (second != Heap::raw_unchecked_empty_string()) { 237 return object; 238 } 239 240 // Since we don't have the object's start, it is impossible to update the 241 // remembered set. Therefore, we only replace the string with its left 242 // substring when the remembered set does not change. 243 Object* first = reinterpret_cast<ConsString*>(object)->unchecked_first(); 244 if (!Heap::InNewSpace(object) && Heap::InNewSpace(first)) return object; 245 246 *p = first; 247 return HeapObject::cast(first); 248} 249 250 251// Helper class for marking pointers in HeapObjects. 252class MarkingVisitor : public ObjectVisitor { 253 public: 254 void VisitPointer(Object** p) { 255 MarkObjectByPointer(p); 256 } 257 258 void VisitPointers(Object** start, Object** end) { 259 // Mark all objects pointed to in [start, end). 260 const int kMinRangeForMarkingRecursion = 64; 261 if (end - start >= kMinRangeForMarkingRecursion) { 262 if (VisitUnmarkedObjects(start, end)) return; 263 // We are close to a stack overflow, so just mark the objects. 264 } 265 for (Object** p = start; p < end; p++) MarkObjectByPointer(p); 266 } 267 268 void VisitCodeTarget(RelocInfo* rinfo) { 269 ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode())); 270 Code* code = Code::GetCodeFromTargetAddress(rinfo->target_address()); 271 if (FLAG_cleanup_ics_at_gc && code->is_inline_cache_stub()) { 272 IC::Clear(rinfo->pc()); 273 // Please note targets for cleared inline cached do not have to be 274 // marked since they are contained in Heap::non_monomorphic_cache(). 275 } else { 276 MarkCompactCollector::MarkObject(code); 277 } 278 } 279 280 void VisitDebugTarget(RelocInfo* rinfo) { 281 ASSERT(RelocInfo::IsJSReturn(rinfo->rmode()) && 282 rinfo->IsCallInstruction()); 283 HeapObject* code = Code::GetCodeFromTargetAddress(rinfo->call_address()); 284 MarkCompactCollector::MarkObject(code); 285 // When compacting we convert the call to a real object pointer. 286 if (IsCompacting()) rinfo->set_call_object(code); 287 } 288 289 private: 290 // Mark object pointed to by p. 291 void MarkObjectByPointer(Object** p) { 292 if (!(*p)->IsHeapObject()) return; 293 HeapObject* object = ShortCircuitConsString(p); 294 MarkCompactCollector::MarkObject(object); 295 } 296 297 // Tells whether the mark sweep collection will perform compaction. 298 bool IsCompacting() { return MarkCompactCollector::IsCompacting(); } 299 300 // Visit an unmarked object. 301 void VisitUnmarkedObject(HeapObject* obj) { 302#ifdef DEBUG 303 ASSERT(Heap::Contains(obj)); 304 ASSERT(!obj->IsMarked()); 305#endif 306 Map* map = obj->map(); 307 MarkCompactCollector::SetMark(obj); 308 // Mark the map pointer and the body. 309 MarkCompactCollector::MarkObject(map); 310 obj->IterateBody(map->instance_type(), obj->SizeFromMap(map), this); 311 } 312 313 // Visit all unmarked objects pointed to by [start, end). 314 // Returns false if the operation fails (lack of stack space). 315 inline bool VisitUnmarkedObjects(Object** start, Object** end) { 316 // Return false is we are close to the stack limit. 317 StackLimitCheck check; 318 if (check.HasOverflowed()) return false; 319 320 // Visit the unmarked objects. 321 for (Object** p = start; p < end; p++) { 322 if (!(*p)->IsHeapObject()) continue; 323 HeapObject* obj = HeapObject::cast(*p); 324 if (obj->IsMarked()) continue; 325 VisitUnmarkedObject(obj); 326 } 327 return true; 328 } 329}; 330 331 332// Visitor class for marking heap roots. 333class RootMarkingVisitor : public ObjectVisitor { 334 public: 335 void VisitPointer(Object** p) { 336 MarkObjectByPointer(p); 337 } 338 339 void VisitPointers(Object** start, Object** end) { 340 for (Object** p = start; p < end; p++) MarkObjectByPointer(p); 341 } 342 343 MarkingVisitor* stack_visitor() { return &stack_visitor_; } 344 345 private: 346 MarkingVisitor stack_visitor_; 347 348 void MarkObjectByPointer(Object** p) { 349 if (!(*p)->IsHeapObject()) return; 350 351 // Replace flat cons strings in place. 352 HeapObject* object = ShortCircuitConsString(p); 353 if (object->IsMarked()) return; 354 355 Map* map = object->map(); 356 // Mark the object. 357 MarkCompactCollector::SetMark(object); 358 // Mark the map pointer and body, and push them on the marking stack. 359 MarkCompactCollector::MarkObject(map); 360 object->IterateBody(map->instance_type(), object->SizeFromMap(map), 361 &stack_visitor_); 362 363 // Mark all the objects reachable from the map and body. May leave 364 // overflowed objects in the heap. 365 MarkCompactCollector::EmptyMarkingStack(&stack_visitor_); 366 } 367}; 368 369 370// Helper class for pruning the symbol table. 371class SymbolTableCleaner : public ObjectVisitor { 372 public: 373 SymbolTableCleaner() : pointers_removed_(0) { } 374 void VisitPointers(Object** start, Object** end) { 375 // Visit all HeapObject pointers in [start, end). 376 for (Object** p = start; p < end; p++) { 377 if ((*p)->IsHeapObject() && !HeapObject::cast(*p)->IsMarked()) { 378 // Check if the symbol being pruned is an external symbol. We need to 379 // delete the associated external data as this symbol is going away. 380 381 // Since the object is not marked we can access its map word safely 382 // without having to worry about marking bits in the object header. 383 Map* map = HeapObject::cast(*p)->map(); 384 // Since no objects have yet been moved we can safely access the map of 385 // the object. 386 uint32_t type = map->instance_type(); 387 bool is_external = (type & kStringRepresentationMask) == 388 kExternalStringTag; 389 if (is_external) { 390 bool is_two_byte = (type & kStringEncodingMask) == kTwoByteStringTag; 391 byte* resource_addr = reinterpret_cast<byte*>(*p) + 392 ExternalString::kResourceOffset - 393 kHeapObjectTag; 394 if (is_two_byte) { 395 v8::String::ExternalStringResource** resource = 396 reinterpret_cast<v8::String::ExternalStringResource**> 397 (resource_addr); 398 delete *resource; 399 // Clear the resource pointer in the symbol. 400 *resource = NULL; 401 } else { 402 v8::String::ExternalAsciiStringResource** resource = 403 reinterpret_cast<v8::String::ExternalAsciiStringResource**> 404 (resource_addr); 405 delete *resource; 406 // Clear the resource pointer in the symbol. 407 *resource = NULL; 408 } 409 } 410 // Set the entry to null_value (as deleted). 411 *p = Heap::raw_unchecked_null_value(); 412 pointers_removed_++; 413 } 414 } 415 } 416 417 int PointersRemoved() { 418 return pointers_removed_; 419 } 420 private: 421 int pointers_removed_; 422}; 423 424 425void MarkCompactCollector::MarkUnmarkedObject(HeapObject* object) { 426 ASSERT(!object->IsMarked()); 427 ASSERT(Heap::Contains(object)); 428 if (object->IsMap()) { 429 Map* map = Map::cast(object); 430 if (FLAG_cleanup_caches_in_maps_at_gc) { 431 map->ClearCodeCache(); 432 } 433 SetMark(map); 434 if (FLAG_collect_maps && 435 map->instance_type() >= FIRST_JS_OBJECT_TYPE && 436 map->instance_type() <= JS_FUNCTION_TYPE) { 437 MarkMapContents(map); 438 } else { 439 marking_stack.Push(map); 440 } 441 } else { 442 SetMark(object); 443 marking_stack.Push(object); 444 } 445} 446 447 448void MarkCompactCollector::MarkMapContents(Map* map) { 449 MarkDescriptorArray(reinterpret_cast<DescriptorArray*>( 450 *HeapObject::RawField(map, Map::kInstanceDescriptorsOffset))); 451 452 // Mark the Object* fields of the Map. 453 // Since the descriptor array has been marked already, it is fine 454 // that one of these fields contains a pointer to it. 455 MarkingVisitor visitor; // Has no state or contents. 456 visitor.VisitPointers(HeapObject::RawField(map, Map::kPrototypeOffset), 457 HeapObject::RawField(map, Map::kSize)); 458} 459 460 461void MarkCompactCollector::MarkDescriptorArray( 462 DescriptorArray* descriptors) { 463 if (descriptors->IsMarked()) return; 464 // Empty descriptor array is marked as a root before any maps are marked. 465 ASSERT(descriptors != Heap::raw_unchecked_empty_descriptor_array()); 466 SetMark(descriptors); 467 468 FixedArray* contents = reinterpret_cast<FixedArray*>( 469 descriptors->get(DescriptorArray::kContentArrayIndex)); 470 ASSERT(contents->IsHeapObject()); 471 ASSERT(!contents->IsMarked()); 472 ASSERT(contents->IsFixedArray()); 473 ASSERT(contents->length() >= 2); 474 SetMark(contents); 475 // Contents contains (value, details) pairs. If the details say 476 // that the type of descriptor is MAP_TRANSITION, CONSTANT_TRANSITION, 477 // or NULL_DESCRIPTOR, we don't mark the value as live. Only for 478 // type MAP_TRANSITION is the value a Object* (a Map*). 479 for (int i = 0; i < contents->length(); i += 2) { 480 // If the pair (value, details) at index i, i+1 is not 481 // a transition or null descriptor, mark the value. 482 PropertyDetails details(Smi::cast(contents->get(i + 1))); 483 if (details.type() < FIRST_PHANTOM_PROPERTY_TYPE) { 484 HeapObject* object = reinterpret_cast<HeapObject*>(contents->get(i)); 485 if (object->IsHeapObject() && !object->IsMarked()) { 486 SetMark(object); 487 marking_stack.Push(object); 488 } 489 } 490 } 491 // The DescriptorArray descriptors contains a pointer to its contents array, 492 // but the contents array is already marked. 493 marking_stack.Push(descriptors); 494} 495 496 497void MarkCompactCollector::CreateBackPointers() { 498 HeapObjectIterator iterator(Heap::map_space()); 499 while (iterator.has_next()) { 500 Object* next_object = iterator.next(); 501 if (next_object->IsMap()) { // Could also be ByteArray on free list. 502 Map* map = Map::cast(next_object); 503 if (map->instance_type() >= FIRST_JS_OBJECT_TYPE && 504 map->instance_type() <= JS_FUNCTION_TYPE) { 505 map->CreateBackPointers(); 506 } else { 507 ASSERT(map->instance_descriptors() == Heap::empty_descriptor_array()); 508 } 509 } 510 } 511} 512 513 514static int OverflowObjectSize(HeapObject* obj) { 515 // Recover the normal map pointer, it might be marked as live and 516 // overflowed. 517 MapWord map_word = obj->map_word(); 518 map_word.ClearMark(); 519 map_word.ClearOverflow(); 520 return obj->SizeFromMap(map_word.ToMap()); 521} 522 523 524// Fill the marking stack with overflowed objects returned by the given 525// iterator. Stop when the marking stack is filled or the end of the space 526// is reached, whichever comes first. 527template<class T> 528static void ScanOverflowedObjects(T* it) { 529 // The caller should ensure that the marking stack is initially not full, 530 // so that we don't waste effort pointlessly scanning for objects. 531 ASSERT(!marking_stack.is_full()); 532 533 while (it->has_next()) { 534 HeapObject* object = it->next(); 535 if (object->IsOverflowed()) { 536 object->ClearOverflow(); 537 ASSERT(object->IsMarked()); 538 ASSERT(Heap::Contains(object)); 539 marking_stack.Push(object); 540 if (marking_stack.is_full()) return; 541 } 542 } 543} 544 545 546bool MarkCompactCollector::IsUnmarkedHeapObject(Object** p) { 547 return (*p)->IsHeapObject() && !HeapObject::cast(*p)->IsMarked(); 548} 549 550 551class SymbolMarkingVisitor : public ObjectVisitor { 552 public: 553 void VisitPointers(Object** start, Object** end) { 554 MarkingVisitor marker; 555 for (Object** p = start; p < end; p++) { 556 if (!(*p)->IsHeapObject()) continue; 557 558 HeapObject* object = HeapObject::cast(*p); 559 // If the object is marked, we have marked or are in the process 560 // of marking subparts. 561 if (object->IsMarked()) continue; 562 563 // The object is unmarked, we do not need to unmark to use its 564 // map. 565 Map* map = object->map(); 566 object->IterateBody(map->instance_type(), 567 object->SizeFromMap(map), 568 &marker); 569 } 570 } 571}; 572 573 574void MarkCompactCollector::MarkSymbolTable() { 575 // Objects reachable from symbols are marked as live so as to ensure 576 // that if the symbol itself remains alive after GC for any reason, 577 // and if it is a sliced string or a cons string backed by an 578 // external string (even indirectly), then the external string does 579 // not receive a weak reference callback. 580 SymbolTable* symbol_table = Heap::raw_unchecked_symbol_table(); 581 // Mark the symbol table itself. 582 SetMark(symbol_table); 583 // Explicitly mark the prefix. 584 MarkingVisitor marker; 585 symbol_table->IteratePrefix(&marker); 586 ProcessMarkingStack(&marker); 587 // Mark subparts of the symbols but not the symbols themselves 588 // (unless reachable from another symbol). 589 SymbolMarkingVisitor symbol_marker; 590 symbol_table->IterateElements(&symbol_marker); 591 ProcessMarkingStack(&marker); 592} 593 594 595void MarkCompactCollector::MarkRoots(RootMarkingVisitor* visitor) { 596 // Mark the heap roots including global variables, stack variables, 597 // etc., and all objects reachable from them. 598 Heap::IterateStrongRoots(visitor); 599 600 // Handle the symbol table specially. 601 MarkSymbolTable(); 602 603 // There may be overflowed objects in the heap. Visit them now. 604 while (marking_stack.overflowed()) { 605 RefillMarkingStack(); 606 EmptyMarkingStack(visitor->stack_visitor()); 607 } 608} 609 610 611void MarkCompactCollector::MarkObjectGroups() { 612 List<ObjectGroup*>* object_groups = GlobalHandles::ObjectGroups(); 613 614 for (int i = 0; i < object_groups->length(); i++) { 615 ObjectGroup* entry = object_groups->at(i); 616 if (entry == NULL) continue; 617 618 List<Object**>& objects = entry->objects_; 619 bool group_marked = false; 620 for (int j = 0; j < objects.length(); j++) { 621 Object* object = *objects[j]; 622 if (object->IsHeapObject() && HeapObject::cast(object)->IsMarked()) { 623 group_marked = true; 624 break; 625 } 626 } 627 628 if (!group_marked) continue; 629 630 // An object in the group is marked, so mark as gray all white heap 631 // objects in the group. 632 for (int j = 0; j < objects.length(); ++j) { 633 if ((*objects[j])->IsHeapObject()) { 634 MarkObject(HeapObject::cast(*objects[j])); 635 } 636 } 637 // Once the entire group has been colored gray, set the object group 638 // to NULL so it won't be processed again. 639 delete object_groups->at(i); 640 object_groups->at(i) = NULL; 641 } 642} 643 644 645// Mark all objects reachable from the objects on the marking stack. 646// Before: the marking stack contains zero or more heap object pointers. 647// After: the marking stack is empty, and all objects reachable from the 648// marking stack have been marked, or are overflowed in the heap. 649void MarkCompactCollector::EmptyMarkingStack(MarkingVisitor* visitor) { 650 while (!marking_stack.is_empty()) { 651 HeapObject* object = marking_stack.Pop(); 652 ASSERT(object->IsHeapObject()); 653 ASSERT(Heap::Contains(object)); 654 ASSERT(object->IsMarked()); 655 ASSERT(!object->IsOverflowed()); 656 657 // Because the object is marked, we have to recover the original map 658 // pointer and use it to mark the object's body. 659 MapWord map_word = object->map_word(); 660 map_word.ClearMark(); 661 Map* map = map_word.ToMap(); 662 MarkObject(map); 663 object->IterateBody(map->instance_type(), object->SizeFromMap(map), 664 visitor); 665 } 666} 667 668 669// Sweep the heap for overflowed objects, clear their overflow bits, and 670// push them on the marking stack. Stop early if the marking stack fills 671// before sweeping completes. If sweeping completes, there are no remaining 672// overflowed objects in the heap so the overflow flag on the markings stack 673// is cleared. 674void MarkCompactCollector::RefillMarkingStack() { 675 ASSERT(marking_stack.overflowed()); 676 677 SemiSpaceIterator new_it(Heap::new_space(), &OverflowObjectSize); 678 ScanOverflowedObjects(&new_it); 679 if (marking_stack.is_full()) return; 680 681 HeapObjectIterator old_pointer_it(Heap::old_pointer_space(), 682 &OverflowObjectSize); 683 ScanOverflowedObjects(&old_pointer_it); 684 if (marking_stack.is_full()) return; 685 686 HeapObjectIterator old_data_it(Heap::old_data_space(), &OverflowObjectSize); 687 ScanOverflowedObjects(&old_data_it); 688 if (marking_stack.is_full()) return; 689 690 HeapObjectIterator code_it(Heap::code_space(), &OverflowObjectSize); 691 ScanOverflowedObjects(&code_it); 692 if (marking_stack.is_full()) return; 693 694 HeapObjectIterator map_it(Heap::map_space(), &OverflowObjectSize); 695 ScanOverflowedObjects(&map_it); 696 if (marking_stack.is_full()) return; 697 698 HeapObjectIterator cell_it(Heap::cell_space(), &OverflowObjectSize); 699 ScanOverflowedObjects(&cell_it); 700 if (marking_stack.is_full()) return; 701 702 LargeObjectIterator lo_it(Heap::lo_space(), &OverflowObjectSize); 703 ScanOverflowedObjects(&lo_it); 704 if (marking_stack.is_full()) return; 705 706 marking_stack.clear_overflowed(); 707} 708 709 710// Mark all objects reachable (transitively) from objects on the marking 711// stack. Before: the marking stack contains zero or more heap object 712// pointers. After: the marking stack is empty and there are no overflowed 713// objects in the heap. 714void MarkCompactCollector::ProcessMarkingStack(MarkingVisitor* visitor) { 715 EmptyMarkingStack(visitor); 716 while (marking_stack.overflowed()) { 717 RefillMarkingStack(); 718 EmptyMarkingStack(visitor); 719 } 720} 721 722 723void MarkCompactCollector::ProcessObjectGroups(MarkingVisitor* visitor) { 724 bool work_to_do = true; 725 ASSERT(marking_stack.is_empty()); 726 while (work_to_do) { 727 MarkObjectGroups(); 728 work_to_do = !marking_stack.is_empty(); 729 ProcessMarkingStack(visitor); 730 } 731} 732 733 734void MarkCompactCollector::MarkLiveObjects() { 735#ifdef DEBUG 736 ASSERT(state_ == PREPARE_GC); 737 state_ = MARK_LIVE_OBJECTS; 738#endif 739 // The to space contains live objects, the from space is used as a marking 740 // stack. 741 marking_stack.Initialize(Heap::new_space()->FromSpaceLow(), 742 Heap::new_space()->FromSpaceHigh()); 743 744 ASSERT(!marking_stack.overflowed()); 745 746 RootMarkingVisitor root_visitor; 747 MarkRoots(&root_visitor); 748 749 // The objects reachable from the roots are marked, yet unreachable 750 // objects are unmarked. Mark objects reachable from object groups 751 // containing at least one marked object, and continue until no new 752 // objects are reachable from the object groups. 753 ProcessObjectGroups(root_visitor.stack_visitor()); 754 755 // The objects reachable from the roots or object groups are marked, 756 // yet unreachable objects are unmarked. Mark objects reachable 757 // only from weak global handles. 758 // 759 // First we identify nonlive weak handles and mark them as pending 760 // destruction. 761 GlobalHandles::IdentifyWeakHandles(&IsUnmarkedHeapObject); 762 // Then we mark the objects and process the transitive closure. 763 GlobalHandles::IterateWeakRoots(&root_visitor); 764 while (marking_stack.overflowed()) { 765 RefillMarkingStack(); 766 EmptyMarkingStack(root_visitor.stack_visitor()); 767 } 768 769 // Repeat the object groups to mark unmarked groups reachable from the 770 // weak roots. 771 ProcessObjectGroups(root_visitor.stack_visitor()); 772 773 // Prune the symbol table removing all symbols only pointed to by the 774 // symbol table. Cannot use symbol_table() here because the symbol 775 // table is marked. 776 SymbolTable* symbol_table = Heap::raw_unchecked_symbol_table(); 777 SymbolTableCleaner v; 778 symbol_table->IterateElements(&v); 779 symbol_table->ElementsRemoved(v.PointersRemoved()); 780 781 // Remove object groups after marking phase. 782 GlobalHandles::RemoveObjectGroups(); 783} 784 785 786static int CountMarkedCallback(HeapObject* obj) { 787 MapWord map_word = obj->map_word(); 788 map_word.ClearMark(); 789 return obj->SizeFromMap(map_word.ToMap()); 790} 791 792 793#ifdef DEBUG 794void MarkCompactCollector::UpdateLiveObjectCount(HeapObject* obj) { 795 live_bytes_ += obj->Size(); 796 if (Heap::new_space()->Contains(obj)) { 797 live_young_objects_++; 798 } else if (Heap::map_space()->Contains(obj)) { 799 ASSERT(obj->IsMap()); 800 live_map_objects_++; 801 } else if (Heap::cell_space()->Contains(obj)) { 802 ASSERT(obj->IsJSGlobalPropertyCell()); 803 live_cell_objects_++; 804 } else if (Heap::old_pointer_space()->Contains(obj)) { 805 live_old_pointer_objects_++; 806 } else if (Heap::old_data_space()->Contains(obj)) { 807 live_old_data_objects_++; 808 } else if (Heap::code_space()->Contains(obj)) { 809 live_code_objects_++; 810 } else if (Heap::lo_space()->Contains(obj)) { 811 live_lo_objects_++; 812 } else { 813 UNREACHABLE(); 814 } 815} 816#endif // DEBUG 817 818 819void MarkCompactCollector::SweepLargeObjectSpace() { 820#ifdef DEBUG 821 ASSERT(state_ == MARK_LIVE_OBJECTS); 822 state_ = 823 compacting_collection_ ? ENCODE_FORWARDING_ADDRESSES : SWEEP_SPACES; 824#endif 825 // Deallocate unmarked objects and clear marked bits for marked objects. 826 Heap::lo_space()->FreeUnmarkedObjects(); 827} 828 829// Safe to use during marking phase only. 830bool MarkCompactCollector::SafeIsMap(HeapObject* object) { 831 MapWord metamap = object->map_word(); 832 metamap.ClearMark(); 833 return metamap.ToMap()->instance_type() == MAP_TYPE; 834} 835 836void MarkCompactCollector::ClearNonLiveTransitions() { 837 HeapObjectIterator map_iterator(Heap::map_space(), &CountMarkedCallback); 838 // Iterate over the map space, setting map transitions that go from 839 // a marked map to an unmarked map to null transitions. At the same time, 840 // set all the prototype fields of maps back to their original value, 841 // dropping the back pointers temporarily stored in the prototype field. 842 // Setting the prototype field requires following the linked list of 843 // back pointers, reversing them all at once. This allows us to find 844 // those maps with map transitions that need to be nulled, and only 845 // scan the descriptor arrays of those maps, not all maps. 846 // All of these actions are carried out only on maps of JSObects 847 // and related subtypes. 848 while (map_iterator.has_next()) { 849 Map* map = reinterpret_cast<Map*>(map_iterator.next()); 850 if (!map->IsMarked() && map->IsByteArray()) continue; 851 852 ASSERT(SafeIsMap(map)); 853 // Only JSObject and subtypes have map transitions and back pointers. 854 if (map->instance_type() < FIRST_JS_OBJECT_TYPE) continue; 855 if (map->instance_type() > JS_FUNCTION_TYPE) continue; 856 // Follow the chain of back pointers to find the prototype. 857 Map* current = map; 858 while (SafeIsMap(current)) { 859 current = reinterpret_cast<Map*>(current->prototype()); 860 ASSERT(current->IsHeapObject()); 861 } 862 Object* real_prototype = current; 863 864 // Follow back pointers, setting them to prototype, 865 // clearing map transitions when necessary. 866 current = map; 867 bool on_dead_path = !current->IsMarked(); 868 Object* next; 869 while (SafeIsMap(current)) { 870 next = current->prototype(); 871 // There should never be a dead map above a live map. 872 ASSERT(on_dead_path || current->IsMarked()); 873 874 // A live map above a dead map indicates a dead transition. 875 // This test will always be false on the first iteration. 876 if (on_dead_path && current->IsMarked()) { 877 on_dead_path = false; 878 current->ClearNonLiveTransitions(real_prototype); 879 } 880 *HeapObject::RawField(current, Map::kPrototypeOffset) = 881 real_prototype; 882 current = reinterpret_cast<Map*>(next); 883 } 884 } 885} 886 887// ------------------------------------------------------------------------- 888// Phase 2: Encode forwarding addresses. 889// When compacting, forwarding addresses for objects in old space and map 890// space are encoded in their map pointer word (along with an encoding of 891// their map pointers). 892// 893// 31 21 20 10 9 0 894// +-----------------+------------------+-----------------+ 895// |forwarding offset|page offset of map|page index of map| 896// +-----------------+------------------+-----------------+ 897// 11 bits 11 bits 10 bits 898// 899// An address range [start, end) can have both live and non-live objects. 900// Maximal non-live regions are marked so they can be skipped on subsequent 901// sweeps of the heap. A distinguished map-pointer encoding is used to mark 902// free regions of one-word size (in which case the next word is the start 903// of a live object). A second distinguished map-pointer encoding is used 904// to mark free regions larger than one word, and the size of the free 905// region (including the first word) is written to the second word of the 906// region. 907// 908// Any valid map page offset must lie in the object area of the page, so map 909// page offsets less than Page::kObjectStartOffset are invalid. We use a 910// pair of distinguished invalid map encodings (for single word and multiple 911// words) to indicate free regions in the page found during computation of 912// forwarding addresses and skipped over in subsequent sweeps. 913static const uint32_t kSingleFreeEncoding = 0; 914static const uint32_t kMultiFreeEncoding = 1; 915 916 917// Encode a free region, defined by the given start address and size, in the 918// first word or two of the region. 919void EncodeFreeRegion(Address free_start, int free_size) { 920 ASSERT(free_size >= kIntSize); 921 if (free_size == kIntSize) { 922 Memory::uint32_at(free_start) = kSingleFreeEncoding; 923 } else { 924 ASSERT(free_size >= 2 * kIntSize); 925 Memory::uint32_at(free_start) = kMultiFreeEncoding; 926 Memory::int_at(free_start + kIntSize) = free_size; 927 } 928 929#ifdef DEBUG 930 // Zap the body of the free region. 931 if (FLAG_enable_slow_asserts) { 932 for (int offset = 2 * kIntSize; 933 offset < free_size; 934 offset += kPointerSize) { 935 Memory::Address_at(free_start + offset) = kZapValue; 936 } 937 } 938#endif 939} 940 941 942// Try to promote all objects in new space. Heap numbers and sequential 943// strings are promoted to the code space, large objects to large object space, 944// and all others to the old space. 945inline Object* MCAllocateFromNewSpace(HeapObject* object, int object_size) { 946 Object* forwarded; 947 if (object_size > Heap::MaxObjectSizeInPagedSpace()) { 948 forwarded = Failure::Exception(); 949 } else { 950 OldSpace* target_space = Heap::TargetSpace(object); 951 ASSERT(target_space == Heap::old_pointer_space() || 952 target_space == Heap::old_data_space()); 953 forwarded = target_space->MCAllocateRaw(object_size); 954 } 955 if (forwarded->IsFailure()) { 956 forwarded = Heap::new_space()->MCAllocateRaw(object_size); 957 } 958 return forwarded; 959} 960 961 962// Allocation functions for the paged spaces call the space's MCAllocateRaw. 963inline Object* MCAllocateFromOldPointerSpace(HeapObject* ignore, 964 int object_size) { 965 return Heap::old_pointer_space()->MCAllocateRaw(object_size); 966} 967 968 969inline Object* MCAllocateFromOldDataSpace(HeapObject* ignore, int object_size) { 970 return Heap::old_data_space()->MCAllocateRaw(object_size); 971} 972 973 974inline Object* MCAllocateFromCodeSpace(HeapObject* ignore, int object_size) { 975 return Heap::code_space()->MCAllocateRaw(object_size); 976} 977 978 979inline Object* MCAllocateFromMapSpace(HeapObject* ignore, int object_size) { 980 return Heap::map_space()->MCAllocateRaw(object_size); 981} 982 983 984inline Object* MCAllocateFromCellSpace(HeapObject* ignore, int object_size) { 985 return Heap::cell_space()->MCAllocateRaw(object_size); 986} 987 988 989// The forwarding address is encoded at the same offset as the current 990// to-space object, but in from space. 991inline void EncodeForwardingAddressInNewSpace(HeapObject* old_object, 992 int object_size, 993 Object* new_object, 994 int* ignored) { 995 int offset = 996 Heap::new_space()->ToSpaceOffsetForAddress(old_object->address()); 997 Memory::Address_at(Heap::new_space()->FromSpaceLow() + offset) = 998 HeapObject::cast(new_object)->address(); 999} 1000 1001 1002// The forwarding address is encoded in the map pointer of the object as an 1003// offset (in terms of live bytes) from the address of the first live object 1004// in the page. 1005inline void EncodeForwardingAddressInPagedSpace(HeapObject* old_object, 1006 int object_size, 1007 Object* new_object, 1008 int* offset) { 1009 // Record the forwarding address of the first live object if necessary. 1010 if (*offset == 0) { 1011 Page::FromAddress(old_object->address())->mc_first_forwarded = 1012 HeapObject::cast(new_object)->address(); 1013 } 1014 1015 MapWord encoding = 1016 MapWord::EncodeAddress(old_object->map()->address(), *offset); 1017 old_object->set_map_word(encoding); 1018 *offset += object_size; 1019 ASSERT(*offset <= Page::kObjectAreaSize); 1020} 1021 1022 1023// Most non-live objects are ignored. 1024inline void IgnoreNonLiveObject(HeapObject* object) {} 1025 1026 1027// A code deletion event is logged for non-live code objects. 1028inline void LogNonLiveCodeObject(HeapObject* object) { 1029 if (object->IsCode()) LOG(CodeDeleteEvent(object->address())); 1030} 1031 1032 1033// Function template that, given a range of addresses (eg, a semispace or a 1034// paged space page), iterates through the objects in the range to clear 1035// mark bits and compute and encode forwarding addresses. As a side effect, 1036// maximal free chunks are marked so that they can be skipped on subsequent 1037// sweeps. 1038// 1039// The template parameters are an allocation function, a forwarding address 1040// encoding function, and a function to process non-live objects. 1041template<MarkCompactCollector::AllocationFunction Alloc, 1042 MarkCompactCollector::EncodingFunction Encode, 1043 MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive> 1044inline void EncodeForwardingAddressesInRange(Address start, 1045 Address end, 1046 int* offset) { 1047 // The start address of the current free region while sweeping the space. 1048 // This address is set when a transition from live to non-live objects is 1049 // encountered. A value (an encoding of the 'next free region' pointer) 1050 // is written to memory at this address when a transition from non-live to 1051 // live objects is encountered. 1052 Address free_start = NULL; 1053 1054 // A flag giving the state of the previously swept object. Initially true 1055 // to ensure that free_start is initialized to a proper address before 1056 // trying to write to it. 1057 bool is_prev_alive = true; 1058 1059 int object_size; // Will be set on each iteration of the loop. 1060 for (Address current = start; current < end; current += object_size) { 1061 HeapObject* object = HeapObject::FromAddress(current); 1062 if (object->IsMarked()) { 1063 object->ClearMark(); 1064 MarkCompactCollector::tracer()->decrement_marked_count(); 1065 object_size = object->Size(); 1066 1067 Object* forwarded = Alloc(object, object_size); 1068 // Allocation cannot fail, because we are compacting the space. 1069 ASSERT(!forwarded->IsFailure()); 1070 Encode(object, object_size, forwarded, offset); 1071 1072#ifdef DEBUG 1073 if (FLAG_gc_verbose) { 1074 PrintF("forward %p -> %p.\n", object->address(), 1075 HeapObject::cast(forwarded)->address()); 1076 } 1077#endif 1078 if (!is_prev_alive) { // Transition from non-live to live. 1079 EncodeFreeRegion(free_start, current - free_start); 1080 is_prev_alive = true; 1081 } 1082 } else { // Non-live object. 1083 object_size = object->Size(); 1084 ProcessNonLive(object); 1085 if (is_prev_alive) { // Transition from live to non-live. 1086 free_start = current; 1087 is_prev_alive = false; 1088 } 1089 } 1090 } 1091 1092 // If we ended on a free region, mark it. 1093 if (!is_prev_alive) EncodeFreeRegion(free_start, end - free_start); 1094} 1095 1096 1097// Functions to encode the forwarding pointers in each compactable space. 1098void MarkCompactCollector::EncodeForwardingAddressesInNewSpace() { 1099 int ignored; 1100 EncodeForwardingAddressesInRange<MCAllocateFromNewSpace, 1101 EncodeForwardingAddressInNewSpace, 1102 IgnoreNonLiveObject>( 1103 Heap::new_space()->bottom(), 1104 Heap::new_space()->top(), 1105 &ignored); 1106} 1107 1108 1109template<MarkCompactCollector::AllocationFunction Alloc, 1110 MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive> 1111void MarkCompactCollector::EncodeForwardingAddressesInPagedSpace( 1112 PagedSpace* space) { 1113 PageIterator it(space, PageIterator::PAGES_IN_USE); 1114 while (it.has_next()) { 1115 Page* p = it.next(); 1116 // The offset of each live object in the page from the first live object 1117 // in the page. 1118 int offset = 0; 1119 EncodeForwardingAddressesInRange<Alloc, 1120 EncodeForwardingAddressInPagedSpace, 1121 ProcessNonLive>( 1122 p->ObjectAreaStart(), 1123 p->AllocationTop(), 1124 &offset); 1125 } 1126} 1127 1128 1129static void SweepSpace(NewSpace* space) { 1130 HeapObject* object; 1131 for (Address current = space->bottom(); 1132 current < space->top(); 1133 current += object->Size()) { 1134 object = HeapObject::FromAddress(current); 1135 if (object->IsMarked()) { 1136 object->ClearMark(); 1137 MarkCompactCollector::tracer()->decrement_marked_count(); 1138 } else { 1139 // We give non-live objects a map that will correctly give their size, 1140 // since their existing map might not be live after the collection. 1141 int size = object->Size(); 1142 if (size >= ByteArray::kHeaderSize) { 1143 object->set_map(Heap::raw_unchecked_byte_array_map()); 1144 ByteArray::cast(object)->set_length(ByteArray::LengthFor(size)); 1145 } else { 1146 ASSERT(size == kPointerSize); 1147 object->set_map(Heap::raw_unchecked_one_pointer_filler_map()); 1148 } 1149 ASSERT(object->Size() == size); 1150 } 1151 // The object is now unmarked for the call to Size() at the top of the 1152 // loop. 1153 } 1154} 1155 1156 1157static void SweepSpace(PagedSpace* space, DeallocateFunction dealloc) { 1158 PageIterator it(space, PageIterator::PAGES_IN_USE); 1159 while (it.has_next()) { 1160 Page* p = it.next(); 1161 1162 bool is_previous_alive = true; 1163 Address free_start = NULL; 1164 HeapObject* object; 1165 1166 for (Address current = p->ObjectAreaStart(); 1167 current < p->AllocationTop(); 1168 current += object->Size()) { 1169 object = HeapObject::FromAddress(current); 1170 if (object->IsMarked()) { 1171 object->ClearMark(); 1172 MarkCompactCollector::tracer()->decrement_marked_count(); 1173 if (!is_previous_alive) { // Transition from free to live. 1174 dealloc(free_start, current - free_start); 1175 is_previous_alive = true; 1176 } 1177 } else { 1178 if (object->IsCode()) { 1179 // Notify the logger that compiled code has been collected. 1180 LOG(CodeDeleteEvent(Code::cast(object)->address())); 1181 } 1182 if (is_previous_alive) { // Transition from live to free. 1183 free_start = current; 1184 is_previous_alive = false; 1185 } 1186 } 1187 // The object is now unmarked for the call to Size() at the top of the 1188 // loop. 1189 } 1190 1191 // If the last region was not live we need to deallocate from 1192 // free_start to the allocation top in the page. 1193 if (!is_previous_alive) { 1194 int free_size = p->AllocationTop() - free_start; 1195 if (free_size > 0) { 1196 dealloc(free_start, free_size); 1197 } 1198 } 1199 } 1200} 1201 1202 1203void MarkCompactCollector::DeallocateOldPointerBlock(Address start, 1204 int size_in_bytes) { 1205 Heap::ClearRSetRange(start, size_in_bytes); 1206 Heap::old_pointer_space()->Free(start, size_in_bytes); 1207} 1208 1209 1210void MarkCompactCollector::DeallocateOldDataBlock(Address start, 1211 int size_in_bytes) { 1212 Heap::old_data_space()->Free(start, size_in_bytes); 1213} 1214 1215 1216void MarkCompactCollector::DeallocateCodeBlock(Address start, 1217 int size_in_bytes) { 1218 Heap::code_space()->Free(start, size_in_bytes); 1219} 1220 1221 1222void MarkCompactCollector::DeallocateMapBlock(Address start, 1223 int size_in_bytes) { 1224 // Objects in map space are frequently assumed to have size Map::kSize and a 1225 // valid map in their first word. Thus, we break the free block up into 1226 // chunks and free them separately. 1227 ASSERT(size_in_bytes % Map::kSize == 0); 1228 Heap::ClearRSetRange(start, size_in_bytes); 1229 Address end = start + size_in_bytes; 1230 for (Address a = start; a < end; a += Map::kSize) { 1231 Heap::map_space()->Free(a); 1232 } 1233} 1234 1235 1236void MarkCompactCollector::DeallocateCellBlock(Address start, 1237 int size_in_bytes) { 1238 // Free-list elements in cell space are assumed to have a fixed size. 1239 // We break the free block into chunks and add them to the free list 1240 // individually. 1241 int size = Heap::cell_space()->object_size_in_bytes(); 1242 ASSERT(size_in_bytes % size == 0); 1243 Heap::ClearRSetRange(start, size_in_bytes); 1244 Address end = start + size_in_bytes; 1245 for (Address a = start; a < end; a += size) { 1246 Heap::cell_space()->Free(a); 1247 } 1248} 1249 1250 1251void MarkCompactCollector::EncodeForwardingAddresses() { 1252 ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES); 1253 // Objects in the active semispace of the young generation may be 1254 // relocated to the inactive semispace (if not promoted). Set the 1255 // relocation info to the beginning of the inactive semispace. 1256 Heap::new_space()->MCResetRelocationInfo(); 1257 1258 // Compute the forwarding pointers in each space. 1259 EncodeForwardingAddressesInPagedSpace<MCAllocateFromOldPointerSpace, 1260 IgnoreNonLiveObject>( 1261 Heap::old_pointer_space()); 1262 1263 EncodeForwardingAddressesInPagedSpace<MCAllocateFromOldDataSpace, 1264 IgnoreNonLiveObject>( 1265 Heap::old_data_space()); 1266 1267 EncodeForwardingAddressesInPagedSpace<MCAllocateFromCodeSpace, 1268 LogNonLiveCodeObject>( 1269 Heap::code_space()); 1270 1271 EncodeForwardingAddressesInPagedSpace<MCAllocateFromCellSpace, 1272 IgnoreNonLiveObject>( 1273 Heap::cell_space()); 1274 1275 1276 // Compute new space next to last after the old and code spaces have been 1277 // compacted. Objects in new space can be promoted to old or code space. 1278 EncodeForwardingAddressesInNewSpace(); 1279 1280 // Compute map space last because computing forwarding addresses 1281 // overwrites non-live objects. Objects in the other spaces rely on 1282 // non-live map pointers to get the sizes of non-live objects. 1283 EncodeForwardingAddressesInPagedSpace<MCAllocateFromMapSpace, 1284 IgnoreNonLiveObject>( 1285 Heap::map_space()); 1286 1287 // Write relocation info to the top page, so we can use it later. This is 1288 // done after promoting objects from the new space so we get the correct 1289 // allocation top. 1290 Heap::old_pointer_space()->MCWriteRelocationInfoToPage(); 1291 Heap::old_data_space()->MCWriteRelocationInfoToPage(); 1292 Heap::code_space()->MCWriteRelocationInfoToPage(); 1293 Heap::map_space()->MCWriteRelocationInfoToPage(); 1294 Heap::cell_space()->MCWriteRelocationInfoToPage(); 1295} 1296 1297 1298void MarkCompactCollector::SweepSpaces() { 1299 ASSERT(state_ == SWEEP_SPACES); 1300 ASSERT(!IsCompacting()); 1301 // Noncompacting collections simply sweep the spaces to clear the mark 1302 // bits and free the nonlive blocks (for old and map spaces). We sweep 1303 // the map space last because freeing non-live maps overwrites them and 1304 // the other spaces rely on possibly non-live maps to get the sizes for 1305 // non-live objects. 1306 SweepSpace(Heap::old_pointer_space(), &DeallocateOldPointerBlock); 1307 SweepSpace(Heap::old_data_space(), &DeallocateOldDataBlock); 1308 SweepSpace(Heap::code_space(), &DeallocateCodeBlock); 1309 SweepSpace(Heap::cell_space(), &DeallocateCellBlock); 1310 SweepSpace(Heap::new_space()); 1311 SweepSpace(Heap::map_space(), &DeallocateMapBlock); 1312} 1313 1314 1315// Iterate the live objects in a range of addresses (eg, a page or a 1316// semispace). The live regions of the range have been linked into a list. 1317// The first live region is [first_live_start, first_live_end), and the last 1318// address in the range is top. The callback function is used to get the 1319// size of each live object. 1320int MarkCompactCollector::IterateLiveObjectsInRange( 1321 Address start, 1322 Address end, 1323 HeapObjectCallback size_func) { 1324 int live_objects = 0; 1325 Address current = start; 1326 while (current < end) { 1327 uint32_t encoded_map = Memory::uint32_at(current); 1328 if (encoded_map == kSingleFreeEncoding) { 1329 current += kPointerSize; 1330 } else if (encoded_map == kMultiFreeEncoding) { 1331 current += Memory::int_at(current + kIntSize); 1332 } else { 1333 live_objects++; 1334 current += size_func(HeapObject::FromAddress(current)); 1335 } 1336 } 1337 return live_objects; 1338} 1339 1340 1341int MarkCompactCollector::IterateLiveObjects(NewSpace* space, 1342 HeapObjectCallback size_f) { 1343 ASSERT(MARK_LIVE_OBJECTS < state_ && state_ <= RELOCATE_OBJECTS); 1344 return IterateLiveObjectsInRange(space->bottom(), space->top(), size_f); 1345} 1346 1347 1348int MarkCompactCollector::IterateLiveObjects(PagedSpace* space, 1349 HeapObjectCallback size_f) { 1350 ASSERT(MARK_LIVE_OBJECTS < state_ && state_ <= RELOCATE_OBJECTS); 1351 int total = 0; 1352 PageIterator it(space, PageIterator::PAGES_IN_USE); 1353 while (it.has_next()) { 1354 Page* p = it.next(); 1355 total += IterateLiveObjectsInRange(p->ObjectAreaStart(), 1356 p->AllocationTop(), 1357 size_f); 1358 } 1359 return total; 1360} 1361 1362 1363// ------------------------------------------------------------------------- 1364// Phase 3: Update pointers 1365 1366// Helper class for updating pointers in HeapObjects. 1367class UpdatingVisitor: public ObjectVisitor { 1368 public: 1369 void VisitPointer(Object** p) { 1370 UpdatePointer(p); 1371 } 1372 1373 void VisitPointers(Object** start, Object** end) { 1374 // Mark all HeapObject pointers in [start, end) 1375 for (Object** p = start; p < end; p++) UpdatePointer(p); 1376 } 1377 1378 void VisitCodeTarget(RelocInfo* rinfo) { 1379 ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode())); 1380 Object* target = Code::GetCodeFromTargetAddress(rinfo->target_address()); 1381 VisitPointer(&target); 1382 rinfo->set_target_address( 1383 reinterpret_cast<Code*>(target)->instruction_start()); 1384 } 1385 1386 private: 1387 void UpdatePointer(Object** p) { 1388 if (!(*p)->IsHeapObject()) return; 1389 1390 HeapObject* obj = HeapObject::cast(*p); 1391 Address old_addr = obj->address(); 1392 Address new_addr; 1393 ASSERT(!Heap::InFromSpace(obj)); 1394 1395 if (Heap::new_space()->Contains(obj)) { 1396 Address forwarding_pointer_addr = 1397 Heap::new_space()->FromSpaceLow() + 1398 Heap::new_space()->ToSpaceOffsetForAddress(old_addr); 1399 new_addr = Memory::Address_at(forwarding_pointer_addr); 1400 1401#ifdef DEBUG 1402 ASSERT(Heap::old_pointer_space()->Contains(new_addr) || 1403 Heap::old_data_space()->Contains(new_addr) || 1404 Heap::new_space()->FromSpaceContains(new_addr) || 1405 Heap::lo_space()->Contains(HeapObject::FromAddress(new_addr))); 1406 1407 if (Heap::new_space()->FromSpaceContains(new_addr)) { 1408 ASSERT(Heap::new_space()->FromSpaceOffsetForAddress(new_addr) <= 1409 Heap::new_space()->ToSpaceOffsetForAddress(old_addr)); 1410 } 1411#endif 1412 1413 } else if (Heap::lo_space()->Contains(obj)) { 1414 // Don't move objects in the large object space. 1415 return; 1416 1417 } else { 1418#ifdef DEBUG 1419 PagedSpaces spaces; 1420 PagedSpace* original_space = spaces.next(); 1421 while (original_space != NULL) { 1422 if (original_space->Contains(obj)) break; 1423 original_space = spaces.next(); 1424 } 1425 ASSERT(original_space != NULL); 1426#endif 1427 new_addr = MarkCompactCollector::GetForwardingAddressInOldSpace(obj); 1428 ASSERT(original_space->Contains(new_addr)); 1429 ASSERT(original_space->MCSpaceOffsetForAddress(new_addr) <= 1430 original_space->MCSpaceOffsetForAddress(old_addr)); 1431 } 1432 1433 *p = HeapObject::FromAddress(new_addr); 1434 1435#ifdef DEBUG 1436 if (FLAG_gc_verbose) { 1437 PrintF("update %p : %p -> %p\n", 1438 reinterpret_cast<Address>(p), old_addr, new_addr); 1439 } 1440#endif 1441 } 1442}; 1443 1444 1445void MarkCompactCollector::UpdatePointers() { 1446#ifdef DEBUG 1447 ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES); 1448 state_ = UPDATE_POINTERS; 1449#endif 1450 UpdatingVisitor updating_visitor; 1451 Heap::IterateRoots(&updating_visitor); 1452 GlobalHandles::IterateWeakRoots(&updating_visitor); 1453 1454 int live_maps = IterateLiveObjects(Heap::map_space(), 1455 &UpdatePointersInOldObject); 1456 int live_pointer_olds = IterateLiveObjects(Heap::old_pointer_space(), 1457 &UpdatePointersInOldObject); 1458 int live_data_olds = IterateLiveObjects(Heap::old_data_space(), 1459 &UpdatePointersInOldObject); 1460 int live_codes = IterateLiveObjects(Heap::code_space(), 1461 &UpdatePointersInOldObject); 1462 int live_cells = IterateLiveObjects(Heap::cell_space(), 1463 &UpdatePointersInOldObject); 1464 int live_news = IterateLiveObjects(Heap::new_space(), 1465 &UpdatePointersInNewObject); 1466 1467 // Large objects do not move, the map word can be updated directly. 1468 LargeObjectIterator it(Heap::lo_space()); 1469 while (it.has_next()) UpdatePointersInNewObject(it.next()); 1470 1471 USE(live_maps); 1472 USE(live_pointer_olds); 1473 USE(live_data_olds); 1474 USE(live_codes); 1475 USE(live_cells); 1476 USE(live_news); 1477 ASSERT(live_maps == live_map_objects_); 1478 ASSERT(live_data_olds == live_old_data_objects_); 1479 ASSERT(live_pointer_olds == live_old_pointer_objects_); 1480 ASSERT(live_codes == live_code_objects_); 1481 ASSERT(live_cells == live_cell_objects_); 1482 ASSERT(live_news == live_young_objects_); 1483} 1484 1485 1486int MarkCompactCollector::UpdatePointersInNewObject(HeapObject* obj) { 1487 // Keep old map pointers 1488 Map* old_map = obj->map(); 1489 ASSERT(old_map->IsHeapObject()); 1490 1491 Address forwarded = GetForwardingAddressInOldSpace(old_map); 1492 1493 ASSERT(Heap::map_space()->Contains(old_map)); 1494 ASSERT(Heap::map_space()->Contains(forwarded)); 1495#ifdef DEBUG 1496 if (FLAG_gc_verbose) { 1497 PrintF("update %p : %p -> %p\n", obj->address(), old_map->address(), 1498 forwarded); 1499 } 1500#endif 1501 // Update the map pointer. 1502 obj->set_map(reinterpret_cast<Map*>(HeapObject::FromAddress(forwarded))); 1503 1504 // We have to compute the object size relying on the old map because 1505 // map objects are not relocated yet. 1506 int obj_size = obj->SizeFromMap(old_map); 1507 1508 // Update pointers in the object body. 1509 UpdatingVisitor updating_visitor; 1510 obj->IterateBody(old_map->instance_type(), obj_size, &updating_visitor); 1511 return obj_size; 1512} 1513 1514 1515int MarkCompactCollector::UpdatePointersInOldObject(HeapObject* obj) { 1516 // Decode the map pointer. 1517 MapWord encoding = obj->map_word(); 1518 Address map_addr = encoding.DecodeMapAddress(Heap::map_space()); 1519 ASSERT(Heap::map_space()->Contains(HeapObject::FromAddress(map_addr))); 1520 1521 // At this point, the first word of map_addr is also encoded, cannot 1522 // cast it to Map* using Map::cast. 1523 Map* map = reinterpret_cast<Map*>(HeapObject::FromAddress(map_addr)); 1524 int obj_size = obj->SizeFromMap(map); 1525 InstanceType type = map->instance_type(); 1526 1527 // Update map pointer. 1528 Address new_map_addr = GetForwardingAddressInOldSpace(map); 1529 int offset = encoding.DecodeOffset(); 1530 obj->set_map_word(MapWord::EncodeAddress(new_map_addr, offset)); 1531 1532#ifdef DEBUG 1533 if (FLAG_gc_verbose) { 1534 PrintF("update %p : %p -> %p\n", obj->address(), 1535 map_addr, new_map_addr); 1536 } 1537#endif 1538 1539 // Update pointers in the object body. 1540 UpdatingVisitor updating_visitor; 1541 obj->IterateBody(type, obj_size, &updating_visitor); 1542 return obj_size; 1543} 1544 1545 1546Address MarkCompactCollector::GetForwardingAddressInOldSpace(HeapObject* obj) { 1547 // Object should either in old or map space. 1548 MapWord encoding = obj->map_word(); 1549 1550 // Offset to the first live object's forwarding address. 1551 int offset = encoding.DecodeOffset(); 1552 Address obj_addr = obj->address(); 1553 1554 // Find the first live object's forwarding address. 1555 Page* p = Page::FromAddress(obj_addr); 1556 Address first_forwarded = p->mc_first_forwarded; 1557 1558 // Page start address of forwarded address. 1559 Page* forwarded_page = Page::FromAddress(first_forwarded); 1560 int forwarded_offset = forwarded_page->Offset(first_forwarded); 1561 1562 // Find end of allocation of in the page of first_forwarded. 1563 Address mc_top = forwarded_page->mc_relocation_top; 1564 int mc_top_offset = forwarded_page->Offset(mc_top); 1565 1566 // Check if current object's forward pointer is in the same page 1567 // as the first live object's forwarding pointer 1568 if (forwarded_offset + offset < mc_top_offset) { 1569 // In the same page. 1570 return first_forwarded + offset; 1571 } 1572 1573 // Must be in the next page, NOTE: this may cross chunks. 1574 Page* next_page = forwarded_page->next_page(); 1575 ASSERT(next_page->is_valid()); 1576 1577 offset -= (mc_top_offset - forwarded_offset); 1578 offset += Page::kObjectStartOffset; 1579 1580 ASSERT_PAGE_OFFSET(offset); 1581 ASSERT(next_page->OffsetToAddress(offset) < next_page->mc_relocation_top); 1582 1583 return next_page->OffsetToAddress(offset); 1584} 1585 1586 1587// ------------------------------------------------------------------------- 1588// Phase 4: Relocate objects 1589 1590void MarkCompactCollector::RelocateObjects() { 1591#ifdef DEBUG 1592 ASSERT(state_ == UPDATE_POINTERS); 1593 state_ = RELOCATE_OBJECTS; 1594#endif 1595 // Relocates objects, always relocate map objects first. Relocating 1596 // objects in other space relies on map objects to get object size. 1597 int live_maps = IterateLiveObjects(Heap::map_space(), &RelocateMapObject); 1598 int live_pointer_olds = IterateLiveObjects(Heap::old_pointer_space(), 1599 &RelocateOldPointerObject); 1600 int live_data_olds = IterateLiveObjects(Heap::old_data_space(), 1601 &RelocateOldDataObject); 1602 int live_codes = IterateLiveObjects(Heap::code_space(), &RelocateCodeObject); 1603 int live_cells = IterateLiveObjects(Heap::cell_space(), &RelocateCellObject); 1604 int live_news = IterateLiveObjects(Heap::new_space(), &RelocateNewObject); 1605 1606 USE(live_maps); 1607 USE(live_data_olds); 1608 USE(live_pointer_olds); 1609 USE(live_codes); 1610 USE(live_cells); 1611 USE(live_news); 1612 ASSERT(live_maps == live_map_objects_); 1613 ASSERT(live_data_olds == live_old_data_objects_); 1614 ASSERT(live_pointer_olds == live_old_pointer_objects_); 1615 ASSERT(live_codes == live_code_objects_); 1616 ASSERT(live_cells == live_cell_objects_); 1617 ASSERT(live_news == live_young_objects_); 1618 1619 // Flip from and to spaces 1620 Heap::new_space()->Flip(); 1621 1622 // Set age_mark to bottom in to space 1623 Address mark = Heap::new_space()->bottom(); 1624 Heap::new_space()->set_age_mark(mark); 1625 1626 Heap::new_space()->MCCommitRelocationInfo(); 1627#ifdef DEBUG 1628 // It is safe to write to the remembered sets as remembered sets on a 1629 // page-by-page basis after committing the m-c forwarding pointer. 1630 Page::set_rset_state(Page::IN_USE); 1631#endif 1632 PagedSpaces spaces; 1633 while (PagedSpace* space = spaces.next()) space->MCCommitRelocationInfo(); 1634} 1635 1636 1637int MarkCompactCollector::RelocateMapObject(HeapObject* obj) { 1638 // Recover map pointer. 1639 MapWord encoding = obj->map_word(); 1640 Address map_addr = encoding.DecodeMapAddress(Heap::map_space()); 1641 ASSERT(Heap::map_space()->Contains(HeapObject::FromAddress(map_addr))); 1642 1643 // Get forwarding address before resetting map pointer 1644 Address new_addr = GetForwardingAddressInOldSpace(obj); 1645 1646 // Reset map pointer. The meta map object may not be copied yet so 1647 // Map::cast does not yet work. 1648 obj->set_map(reinterpret_cast<Map*>(HeapObject::FromAddress(map_addr))); 1649 1650 Address old_addr = obj->address(); 1651 1652 if (new_addr != old_addr) { 1653 memmove(new_addr, old_addr, Map::kSize); // copy contents 1654 } 1655 1656#ifdef DEBUG 1657 if (FLAG_gc_verbose) { 1658 PrintF("relocate %p -> %p\n", old_addr, new_addr); 1659 } 1660#endif 1661 1662 return Map::kSize; 1663} 1664 1665 1666static inline int RestoreMap(HeapObject* obj, 1667 PagedSpace* space, 1668 Address new_addr, 1669 Address map_addr) { 1670 // This must be a non-map object, and the function relies on the 1671 // assumption that the Map space is compacted before the other paged 1672 // spaces (see RelocateObjects). 1673 1674 // Reset map pointer. 1675 obj->set_map(Map::cast(HeapObject::FromAddress(map_addr))); 1676 1677 int obj_size = obj->Size(); 1678 ASSERT_OBJECT_SIZE(obj_size); 1679 1680 ASSERT(space->MCSpaceOffsetForAddress(new_addr) <= 1681 space->MCSpaceOffsetForAddress(obj->address())); 1682 1683#ifdef DEBUG 1684 if (FLAG_gc_verbose) { 1685 PrintF("relocate %p -> %p\n", obj->address(), new_addr); 1686 } 1687#endif 1688 1689 return obj_size; 1690} 1691 1692 1693int MarkCompactCollector::RelocateOldNonCodeObject(HeapObject* obj, 1694 PagedSpace* space) { 1695 // Recover map pointer. 1696 MapWord encoding = obj->map_word(); 1697 Address map_addr = encoding.DecodeMapAddress(Heap::map_space()); 1698 ASSERT(Heap::map_space()->Contains(map_addr)); 1699 1700 // Get forwarding address before resetting map pointer. 1701 Address new_addr = GetForwardingAddressInOldSpace(obj); 1702 1703 // Reset the map pointer. 1704 int obj_size = RestoreMap(obj, space, new_addr, map_addr); 1705 1706 Address old_addr = obj->address(); 1707 1708 if (new_addr != old_addr) { 1709 memmove(new_addr, old_addr, obj_size); // Copy contents 1710 } 1711 1712 ASSERT(!HeapObject::FromAddress(new_addr)->IsCode()); 1713 1714 return obj_size; 1715} 1716 1717 1718int MarkCompactCollector::RelocateOldPointerObject(HeapObject* obj) { 1719 return RelocateOldNonCodeObject(obj, Heap::old_pointer_space()); 1720} 1721 1722 1723int MarkCompactCollector::RelocateOldDataObject(HeapObject* obj) { 1724 return RelocateOldNonCodeObject(obj, Heap::old_data_space()); 1725} 1726 1727 1728int MarkCompactCollector::RelocateCellObject(HeapObject* obj) { 1729 return RelocateOldNonCodeObject(obj, Heap::cell_space()); 1730} 1731 1732 1733int MarkCompactCollector::RelocateCodeObject(HeapObject* obj) { 1734 // Recover map pointer. 1735 MapWord encoding = obj->map_word(); 1736 Address map_addr = encoding.DecodeMapAddress(Heap::map_space()); 1737 ASSERT(Heap::map_space()->Contains(HeapObject::FromAddress(map_addr))); 1738 1739 // Get forwarding address before resetting map pointer 1740 Address new_addr = GetForwardingAddressInOldSpace(obj); 1741 1742 // Reset the map pointer. 1743 int obj_size = RestoreMap(obj, Heap::code_space(), new_addr, map_addr); 1744 1745 Address old_addr = obj->address(); 1746 1747 if (new_addr != old_addr) { 1748 memmove(new_addr, old_addr, obj_size); // Copy contents. 1749 } 1750 1751 HeapObject* copied_to = HeapObject::FromAddress(new_addr); 1752 if (copied_to->IsCode()) { 1753 // May also update inline cache target. 1754 Code::cast(copied_to)->Relocate(new_addr - old_addr); 1755 // Notify the logger that compiled code has moved. 1756 LOG(CodeMoveEvent(old_addr, new_addr)); 1757 } 1758 1759 return obj_size; 1760} 1761 1762 1763int MarkCompactCollector::RelocateNewObject(HeapObject* obj) { 1764 int obj_size = obj->Size(); 1765 1766 // Get forwarding address 1767 Address old_addr = obj->address(); 1768 int offset = Heap::new_space()->ToSpaceOffsetForAddress(old_addr); 1769 1770 Address new_addr = 1771 Memory::Address_at(Heap::new_space()->FromSpaceLow() + offset); 1772 1773#ifdef DEBUG 1774 if (Heap::new_space()->FromSpaceContains(new_addr)) { 1775 ASSERT(Heap::new_space()->FromSpaceOffsetForAddress(new_addr) <= 1776 Heap::new_space()->ToSpaceOffsetForAddress(old_addr)); 1777 } else { 1778 ASSERT(Heap::TargetSpace(obj) == Heap::old_pointer_space() || 1779 Heap::TargetSpace(obj) == Heap::old_data_space()); 1780 } 1781#endif 1782 1783 // New and old addresses cannot overlap. 1784 memcpy(reinterpret_cast<void*>(new_addr), 1785 reinterpret_cast<void*>(old_addr), 1786 obj_size); 1787 1788#ifdef DEBUG 1789 if (FLAG_gc_verbose) { 1790 PrintF("relocate %p -> %p\n", old_addr, new_addr); 1791 } 1792#endif 1793 1794 return obj_size; 1795} 1796 1797 1798// ------------------------------------------------------------------------- 1799// Phase 5: rebuild remembered sets 1800 1801void MarkCompactCollector::RebuildRSets() { 1802#ifdef DEBUG 1803 ASSERT(state_ == RELOCATE_OBJECTS); 1804 state_ = REBUILD_RSETS; 1805#endif 1806 Heap::RebuildRSets(); 1807} 1808 1809} } // namespace v8::internal 1810