1 // Copyright 2012 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
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.
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.
28 #ifndef V8_MARK_COMPACT_H_
29 #define V8_MARK_COMPACT_H_
31 #include "compiler-intrinsics.h"
37 // Callback function, returns whether an object is alive. The heap size
38 // of the object is returned in size. It optionally updates the offset
39 // to the first live object in the page (only used for old and map objects).
40 typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset);
42 // Forward declarations.
46 class RootMarkingVisitor;
51 explicit Marking(Heap* heap)
55 static inline MarkBit MarkBitFrom(Address addr);
57 static inline MarkBit MarkBitFrom(HeapObject* obj) {
58 return MarkBitFrom(reinterpret_cast<Address>(obj));
61 // Impossible markbits: 01
62 static const char* kImpossibleBitPattern;
63 static inline bool IsImpossible(MarkBit mark_bit) {
64 return !mark_bit.Get() && mark_bit.Next().Get();
67 // Black markbits: 10 - this is required by the sweeper.
68 static const char* kBlackBitPattern;
69 static inline bool IsBlack(MarkBit mark_bit) {
70 return mark_bit.Get() && !mark_bit.Next().Get();
73 // White markbits: 00 - this is required by the mark bit clearer.
74 static const char* kWhiteBitPattern;
75 static inline bool IsWhite(MarkBit mark_bit) {
76 return !mark_bit.Get();
80 static const char* kGreyBitPattern;
81 static inline bool IsGrey(MarkBit mark_bit) {
82 return mark_bit.Get() && mark_bit.Next().Get();
85 static inline void MarkBlack(MarkBit mark_bit) {
87 mark_bit.Next().Clear();
90 static inline void BlackToGrey(MarkBit markbit) {
94 static inline void WhiteToGrey(MarkBit markbit) {
99 static inline void GreyToBlack(MarkBit markbit) {
100 markbit.Next().Clear();
103 static inline void BlackToGrey(HeapObject* obj) {
104 BlackToGrey(MarkBitFrom(obj));
107 static inline void AnyToGrey(MarkBit markbit) {
109 markbit.Next().Set();
112 // Returns true if the the object whose mark is transferred is marked black.
113 bool TransferMark(Address old_start, Address new_start);
123 static const char* ColorName(ObjectColor color) {
125 case BLACK_OBJECT: return "black";
126 case WHITE_OBJECT: return "white";
127 case GREY_OBJECT: return "grey";
128 case IMPOSSIBLE_COLOR: return "impossible";
133 static ObjectColor Color(HeapObject* obj) {
134 return Color(Marking::MarkBitFrom(obj));
137 static ObjectColor Color(MarkBit mark_bit) {
138 if (IsBlack(mark_bit)) return BLACK_OBJECT;
139 if (IsWhite(mark_bit)) return WHITE_OBJECT;
140 if (IsGrey(mark_bit)) return GREY_OBJECT;
142 return IMPOSSIBLE_COLOR;
146 // Returns true if the transferred color is black.
147 INLINE(static bool TransferColor(HeapObject* from,
149 MarkBit from_mark_bit = MarkBitFrom(from);
150 MarkBit to_mark_bit = MarkBitFrom(to);
151 bool is_black = false;
152 if (from_mark_bit.Get()) {
154 is_black = true; // Looks black so far.
156 if (from_mark_bit.Next().Get()) {
157 to_mark_bit.Next().Set();
158 is_black = false; // Was actually gray.
167 // ----------------------------------------------------------------------------
168 // Marking deque for tracing live objects.
173 : array_(NULL), top_(0), bottom_(0), mask_(0), overflowed_(false) { }
175 void Initialize(Address low, Address high) {
176 HeapObject** obj_low = reinterpret_cast<HeapObject**>(low);
177 HeapObject** obj_high = reinterpret_cast<HeapObject**>(high);
179 mask_ = RoundDownToPowerOf2(static_cast<int>(obj_high - obj_low)) - 1;
184 inline bool IsFull() { return ((top_ + 1) & mask_) == bottom_; }
186 inline bool IsEmpty() { return top_ == bottom_; }
188 bool overflowed() const { return overflowed_; }
190 void ClearOverflowed() { overflowed_ = false; }
192 void SetOverflowed() { overflowed_ = true; }
194 // Push the (marked) object on the marking stack if there is room,
195 // otherwise mark the object as overflowed and wait for a rescan of the
197 inline void PushBlack(HeapObject* object) {
198 ASSERT(object->IsHeapObject());
200 Marking::BlackToGrey(object);
201 MemoryChunk::IncrementLiveBytesFromGC(object->address(), -object->Size());
204 array_[top_] = object;
205 top_ = ((top_ + 1) & mask_);
209 inline void PushGrey(HeapObject* object) {
210 ASSERT(object->IsHeapObject());
214 array_[top_] = object;
215 top_ = ((top_ + 1) & mask_);
219 inline HeapObject* Pop() {
221 top_ = ((top_ - 1) & mask_);
222 HeapObject* object = array_[top_];
223 ASSERT(object->IsHeapObject());
227 inline void UnshiftGrey(HeapObject* object) {
228 ASSERT(object->IsHeapObject());
232 bottom_ = ((bottom_ - 1) & mask_);
233 array_[bottom_] = object;
237 HeapObject** array() { return array_; }
238 int bottom() { return bottom_; }
239 int top() { return top_; }
240 int mask() { return mask_; }
241 void set_top(int top) { top_ = top; }
245 // array_[(top - 1) & mask_] is the top element in the deque. The Deque is
246 // empty when top_ == bottom_. It is full when top_ + 1 == bottom
253 DISALLOW_COPY_AND_ASSIGN(MarkingDeque);
257 class SlotsBufferAllocator {
259 SlotsBuffer* AllocateBuffer(SlotsBuffer* next_buffer);
260 void DeallocateBuffer(SlotsBuffer* buffer);
262 void DeallocateChain(SlotsBuffer** buffer_address);
266 // SlotsBuffer records a sequence of slots that has to be updated
267 // after live objects were relocated from evacuation candidates.
268 // All slots are either untyped or typed:
269 // - Untyped slots are expected to contain a tagged object pointer.
270 // They are recorded by an address.
271 // - Typed slots are expected to contain an encoded pointer to a heap
272 // object where the way of encoding depends on the type of the slot.
273 // They are recorded as a pair (SlotType, slot address).
274 // We assume that zero-page is never mapped this allows us to distinguish
275 // untyped slots from typed slots during iteration by a simple comparison:
276 // if element of slots buffer is less than NUMBER_OF_SLOT_TYPES then it
277 // is the first element of typed slot's pair.
280 typedef Object** ObjectSlot;
282 explicit SlotsBuffer(SlotsBuffer* next_buffer)
283 : idx_(0), chain_length_(1), next_(next_buffer) {
285 chain_length_ = next_->chain_length_ + 1;
292 void Add(ObjectSlot slot) {
293 ASSERT(0 <= idx_ && idx_ < kNumberOfElements);
294 slots_[idx_++] = slot;
298 EMBEDDED_OBJECT_SLOT,
299 RELOCATED_CODE_OBJECT,
307 void UpdateSlots(Heap* heap);
309 void UpdateSlotsWithFilter(Heap* heap);
311 SlotsBuffer* next() { return next_; }
313 static int SizeOfChain(SlotsBuffer* buffer) {
314 if (buffer == NULL) return 0;
315 return static_cast<int>(buffer->idx_ +
316 (buffer->chain_length_ - 1) * kNumberOfElements);
319 inline bool IsFull() {
320 return idx_ == kNumberOfElements;
323 inline bool HasSpaceForTypedSlot() {
324 return idx_ < kNumberOfElements - 1;
327 static void UpdateSlotsRecordedIn(Heap* heap,
329 bool code_slots_filtering_required) {
330 while (buffer != NULL) {
331 if (code_slots_filtering_required) {
332 buffer->UpdateSlotsWithFilter(heap);
334 buffer->UpdateSlots(heap);
336 buffer = buffer->next();
345 static bool ChainLengthThresholdReached(SlotsBuffer* buffer) {
346 return buffer != NULL && buffer->chain_length_ >= kChainLengthThreshold;
349 static bool AddTo(SlotsBufferAllocator* allocator,
350 SlotsBuffer** buffer_address,
353 SlotsBuffer* buffer = *buffer_address;
354 if (buffer == NULL || buffer->IsFull()) {
355 if (mode == FAIL_ON_OVERFLOW && ChainLengthThresholdReached(buffer)) {
356 allocator->DeallocateChain(buffer_address);
359 buffer = allocator->AllocateBuffer(buffer);
360 *buffer_address = buffer;
366 static bool IsTypedSlot(ObjectSlot slot);
368 static bool AddTo(SlotsBufferAllocator* allocator,
369 SlotsBuffer** buffer_address,
374 static const int kNumberOfElements = 1021;
377 static const int kChainLengthThreshold = 15;
380 intptr_t chain_length_;
382 ObjectSlot slots_[kNumberOfElements];
386 // Defined in isolate.h.
387 class ThreadLocalTop;
390 // -------------------------------------------------------------------------
391 // Mark-Compact collector
392 class MarkCompactCollector {
394 // Type of functions to compute forwarding addresses of objects in
395 // compacted spaces. Given an object and its size, return a (non-failure)
396 // Object* that will be the object after forwarding. There is a separate
397 // allocation function for each (compactable) space based on the location
398 // of the object before compaction.
399 typedef MaybeObject* (*AllocationFunction)(Heap* heap,
403 // Type of functions to encode the forwarding address for an object.
404 // Given the object, its size, and the new (non-failure) object it will be
405 // forwarded to, encode the forwarding address. For paged spaces, the
406 // 'offset' input/output parameter contains the offset of the forwarded
407 // object from the forwarding address of the previous live object in the
408 // page as input, and is updated to contain the offset to be used for the
409 // next live object in the same page. For spaces using a different
410 // encoding (i.e., contiguous spaces), the offset parameter is ignored.
411 typedef void (*EncodingFunction)(Heap* heap,
412 HeapObject* old_object,
417 // Type of functions to process non-live objects.
418 typedef void (*ProcessNonLiveFunction)(HeapObject* object, Isolate* isolate);
420 // Pointer to member function, used in IterateLiveObjects.
421 typedef int (MarkCompactCollector::*LiveObjectCallback)(HeapObject* obj);
423 // Set the global flags, it must be called before Prepare to take effect.
424 inline void SetFlags(int flags);
426 static void Initialize();
428 void CollectEvacuationCandidates(PagedSpace* space);
430 void AddEvacuationCandidate(Page* p);
432 // Prepares for GC by resetting relocation info in old and map spaces and
433 // choosing spaces to compact.
434 void Prepare(GCTracer* tracer);
436 // Performs a global garbage collection.
437 void CollectGarbage();
439 enum CompactionMode {
440 INCREMENTAL_COMPACTION,
441 NON_INCREMENTAL_COMPACTION
444 bool StartCompaction(CompactionMode mode);
446 void AbortCompaction();
448 // During a full GC, there is a stack-allocated GCTracer that is used for
449 // bookkeeping information. Return a pointer to that tracer.
450 GCTracer* tracer() { return tracer_; }
453 // Checks whether performing mark-compact collection.
454 bool in_use() { return state_ > PREPARE_GC; }
455 bool are_map_pointers_encoded() { return state_ == UPDATE_POINTERS; }
458 // Determine type of object and emit deletion log event.
459 static void ReportDeleteIfNeeded(HeapObject* obj, Isolate* isolate);
461 // Distinguishable invalid map encodings (for single word and multiple words)
462 // that indicate free regions.
463 static const uint32_t kSingleFreeEncoding = 0;
464 static const uint32_t kMultiFreeEncoding = 1;
466 static inline bool IsMarked(Object* obj);
468 inline Heap* heap() const { return heap_; }
470 CodeFlusher* code_flusher() { return code_flusher_; }
471 inline bool is_code_flushing_enabled() const { return code_flusher_ != NULL; }
472 void EnableCodeFlushing(bool enable);
481 void VerifyMarkbitsAreClean();
482 static void VerifyMarkbitsAreClean(PagedSpace* space);
483 static void VerifyMarkbitsAreClean(NewSpace* space);
486 // Sweep a single page from the given space conservatively.
487 // Return a number of reclaimed bytes.
488 static intptr_t SweepConservatively(PagedSpace* space, Page* p);
490 INLINE(static bool ShouldSkipEvacuationSlotRecording(Object** anchor)) {
491 return Page::FromAddress(reinterpret_cast<Address>(anchor))->
492 ShouldSkipEvacuationSlotRecording();
495 INLINE(static bool ShouldSkipEvacuationSlotRecording(Object* host)) {
496 return Page::FromAddress(reinterpret_cast<Address>(host))->
497 ShouldSkipEvacuationSlotRecording();
500 INLINE(static bool IsOnEvacuationCandidate(Object* obj)) {
501 return Page::FromAddress(reinterpret_cast<Address>(obj))->
502 IsEvacuationCandidate();
505 void EvictEvacuationCandidate(Page* page) {
506 if (FLAG_trace_fragmentation) {
507 PrintF("Page %p is too popular. Disabling evacuation.\n",
508 reinterpret_cast<void*>(page));
511 // TODO(gc) If all evacuation candidates are too popular we
512 // should stop slots recording entirely.
513 page->ClearEvacuationCandidate();
515 // We were not collecting slots on this page that point
516 // to other evacuation candidates thus we have to
517 // rescan the page after evacuation to discover and update all
518 // pointers to evacuated objects.
519 if (page->owner()->identity() == OLD_DATA_SPACE) {
520 evacuation_candidates_.RemoveElement(page);
522 page->SetFlag(Page::RESCAN_ON_EVACUATION);
526 void RecordRelocSlot(RelocInfo* rinfo, Object* target);
527 void RecordCodeEntrySlot(Address slot, Code* target);
529 INLINE(void RecordSlot(Object** anchor_slot, Object** slot, Object* object));
531 void MigrateObject(Address dst,
534 AllocationSpace to_old_space);
536 bool TryPromoteObject(HeapObject* object, int object_size);
538 inline Object* encountered_weak_maps() { return encountered_weak_maps_; }
539 inline void set_encountered_weak_maps(Object* weak_map) {
540 encountered_weak_maps_ = weak_map;
543 void InvalidateCode(Code* code);
545 void ClearMarkbits();
548 MarkCompactCollector();
549 ~MarkCompactCollector();
551 bool MarkInvalidatedCode();
552 void RemoveDeadInvalidatedCode();
553 void ProcessInvalidatedCode(ObjectVisitor* visitor);
557 enum CollectorState {
562 ENCODE_FORWARDING_ADDRESSES,
567 // The current stage of the collector.
568 CollectorState state_;
571 // Global flag that forces sweeping to be precise, so we can traverse the
573 bool sweep_precisely_;
575 bool reduce_memory_footprint_;
577 bool abort_incremental_marking_;
579 // True if we are collecting slots to perform evacuation from evacuation
583 bool was_marked_incrementally_;
587 bool flush_monomorphic_ics_;
589 // A pointer to the current stack-allocated GC tracer object during a full
590 // collection (NULL before and after).
593 SlotsBufferAllocator slots_buffer_allocator_;
595 SlotsBuffer* migration_slots_buffer_;
597 // Finishes GC, performs heap verification if enabled.
600 // -----------------------------------------------------------------------
601 // Phase 1: Marking live objects.
603 // Before: The heap has been prepared for garbage collection by
604 // MarkCompactCollector::Prepare() and is otherwise in its
607 // After: Live objects are marked and non-live objects are unmarked.
610 friend class RootMarkingVisitor;
611 friend class MarkingVisitor;
612 friend class StaticMarkingVisitor;
613 friend class CodeMarkingVisitor;
614 friend class SharedFunctionInfoMarkingVisitor;
616 // Mark non-optimize code for functions inlined into the given optimized
617 // code. This will prevent it from being flushed.
618 void MarkInlinedFunctionsCode(Code* code);
620 // Mark code objects that are active on the stack to prevent them
621 // from being flushed.
622 void PrepareThreadForCodeFlushing(Isolate* isolate, ThreadLocalTop* top);
624 void PrepareForCodeFlushing();
626 // Marking operations for objects reachable from roots.
627 void MarkLiveObjects();
631 // Marks the object black and pushes it on the marking stack.
632 // This is for non-incremental marking.
633 INLINE(void MarkObject(HeapObject* obj, MarkBit mark_bit));
635 INLINE(bool MarkObjectWithoutPush(HeapObject* object));
636 INLINE(void MarkObjectAndPush(HeapObject* value));
638 // Marks the object black. This is for non-incremental marking.
639 INLINE(void SetMark(HeapObject* obj, MarkBit mark_bit));
641 void ProcessNewlyMarkedObject(HeapObject* obj);
643 // Creates back pointers for all map transitions, stores them in
644 // the prototype field. The original prototype pointers are restored
645 // in ClearNonLiveTransitions(). All JSObject maps
646 // connected by map transitions have the same prototype object, which
647 // is why we can use this field temporarily for back pointers.
648 void CreateBackPointers();
650 // Mark a Map and its DescriptorArray together, skipping transitions.
651 void MarkMapContents(Map* map);
652 void MarkAccessorPairSlot(HeapObject* accessors, int offset);
653 void MarkDescriptorArray(DescriptorArray* descriptors);
655 // Mark the heap roots and all objects reachable from them.
656 void MarkRoots(RootMarkingVisitor* visitor);
658 // Mark the symbol table specially. References to symbols from the
659 // symbol table are weak.
660 void MarkSymbolTable();
662 // Mark objects in object groups that have at least one object in the
664 void MarkObjectGroups();
666 // Mark objects in implicit references groups if their parent object
668 void MarkImplicitRefGroups();
670 // Mark all objects which are reachable due to host application
671 // logic like object groups or implicit references' groups.
672 void ProcessExternalMarking();
674 // Mark objects reachable (transitively) from objects in the marking stack
675 // or overflowed in the heap.
676 void ProcessMarkingDeque();
678 // Mark objects reachable (transitively) from objects in the marking
679 // stack. This function empties the marking stack, but may leave
680 // overflowed objects in the heap, in which case the marking stack's
681 // overflow flag will be set.
682 void EmptyMarkingDeque();
684 // Refill the marking stack with overflowed objects from the heap. This
685 // function either leaves the marking stack full or clears the overflow
686 // flag on the marking stack.
687 void RefillMarkingDeque();
689 // After reachable maps have been marked process per context object
690 // literal map caches removing unmarked entries.
691 void ProcessMapCaches();
693 // Callback function for telling whether the object *p is an unmarked
695 static bool IsUnmarkedHeapObject(Object** p);
697 // Map transitions from a live map to a dead map must be killed.
698 // We replace them with a null descriptor, with the same key.
699 void ClearNonLiveTransitions();
700 void ClearNonLivePrototypeTransitions(Map* map);
701 void ClearNonLiveMapTransitions(Map* map, MarkBit map_mark);
703 // Marking detaches initial maps from SharedFunctionInfo objects
704 // to make this reference weak. We need to reattach initial maps
705 // back after collection. This is either done during
706 // ClearNonLiveTransitions pass or by calling this function.
707 void ReattachInitialMaps();
709 // Mark all values associated with reachable keys in weak maps encountered
710 // so far. This might push new object or even new weak maps onto the
712 void ProcessWeakMaps();
714 // After all reachable objects have been marked those weak map entries
715 // with an unreachable key are removed from all encountered weak maps.
716 // The linked list of all encountered weak maps is destroyed.
717 void ClearWeakMaps();
719 // -----------------------------------------------------------------------
720 // Phase 2: Sweeping to clear mark bits and free non-live objects for
721 // a non-compacting collection.
723 // Before: Live objects are marked and non-live objects are unmarked.
725 // After: Live objects are unmarked, non-live regions have been added to
726 // their space's free list. Active eden semispace is compacted by
730 // If we are not compacting the heap, we simply sweep the spaces except
731 // for the large object space, clearing mark bits and adding unmarked
732 // regions to each space's free list.
735 void EvacuateNewSpace();
737 void EvacuateLiveObjectsFromPage(Page* p);
739 void EvacuatePages();
741 void EvacuateNewSpaceAndCandidates();
743 void SweepSpace(PagedSpace* space, SweeperType sweeper);
746 friend class MarkObjectVisitor;
747 static void VisitObject(HeapObject* obj);
749 friend class UnmarkObjectVisitor;
750 static void UnmarkObject(HeapObject* obj);
754 MarkingDeque marking_deque_;
755 CodeFlusher* code_flusher_;
756 Object* encountered_weak_maps_;
758 List<Page*> evacuation_candidates_;
759 List<Code*> invalidated_code_;
765 const char* AllocationSpaceName(AllocationSpace space);
767 } } // namespace v8::internal
769 #endif // V8_MARK_COMPACT_H_