• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #ifndef V8_MARK_COMPACT_H_
29 #define V8_MARK_COMPACT_H_
30 
31 #include "spaces.h"
32 
33 namespace v8 {
34 namespace internal {
35 
36 // Callback function, returns whether an object is alive. The heap size
37 // of the object is returned in size. It optionally updates the offset
38 // to the first live object in the page (only used for old and map objects).
39 typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset);
40 
41 // Forward declarations.
42 class CodeFlusher;
43 class GCTracer;
44 class MarkingVisitor;
45 class RootMarkingVisitor;
46 
47 
48 // ----------------------------------------------------------------------------
49 // Marking stack for tracing live objects.
50 
51 class MarkingStack {
52  public:
MarkingStack()53   MarkingStack() : low_(NULL), top_(NULL), high_(NULL), overflowed_(false) { }
54 
Initialize(Address low,Address high)55   void Initialize(Address low, Address high) {
56     top_ = low_ = reinterpret_cast<HeapObject**>(low);
57     high_ = reinterpret_cast<HeapObject**>(high);
58     overflowed_ = false;
59   }
60 
is_full()61   bool is_full() const { return top_ >= high_; }
62 
is_empty()63   bool is_empty() const { return top_ <= low_; }
64 
overflowed()65   bool overflowed() const { return overflowed_; }
66 
clear_overflowed()67   void clear_overflowed() { overflowed_ = false; }
68 
69   // Push the (marked) object on the marking stack if there is room,
70   // otherwise mark the object as overflowed and wait for a rescan of the
71   // heap.
Push(HeapObject * object)72   void Push(HeapObject* object) {
73     CHECK(object->IsHeapObject());
74     if (is_full()) {
75       object->SetOverflow();
76       overflowed_ = true;
77     } else {
78       *(top_++) = object;
79     }
80   }
81 
Pop()82   HeapObject* Pop() {
83     ASSERT(!is_empty());
84     HeapObject* object = *(--top_);
85     CHECK(object->IsHeapObject());
86     return object;
87   }
88 
89  private:
90   HeapObject** low_;
91   HeapObject** top_;
92   HeapObject** high_;
93   bool overflowed_;
94 
95   DISALLOW_COPY_AND_ASSIGN(MarkingStack);
96 };
97 
98 
99 // -------------------------------------------------------------------------
100 // Mark-Compact collector
101 
102 class OverflowedObjectsScanner;
103 
104 class MarkCompactCollector {
105  public:
106   // Type of functions to compute forwarding addresses of objects in
107   // compacted spaces.  Given an object and its size, return a (non-failure)
108   // Object* that will be the object after forwarding.  There is a separate
109   // allocation function for each (compactable) space based on the location
110   // of the object before compaction.
111   typedef MaybeObject* (*AllocationFunction)(Heap* heap,
112                                              HeapObject* object,
113                                              int object_size);
114 
115   // Type of functions to encode the forwarding address for an object.
116   // Given the object, its size, and the new (non-failure) object it will be
117   // forwarded to, encode the forwarding address.  For paged spaces, the
118   // 'offset' input/output parameter contains the offset of the forwarded
119   // object from the forwarding address of the previous live object in the
120   // page as input, and is updated to contain the offset to be used for the
121   // next live object in the same page.  For spaces using a different
122   // encoding (ie, contiguous spaces), the offset parameter is ignored.
123   typedef void (*EncodingFunction)(Heap* heap,
124                                    HeapObject* old_object,
125                                    int object_size,
126                                    Object* new_object,
127                                    int* offset);
128 
129   // Type of functions to process non-live objects.
130   typedef void (*ProcessNonLiveFunction)(HeapObject* object, Isolate* isolate);
131 
132   // Pointer to member function, used in IterateLiveObjects.
133   typedef int (MarkCompactCollector::*LiveObjectCallback)(HeapObject* obj);
134 
135   // Set the global force_compaction flag, it must be called before Prepare
136   // to take effect.
SetForceCompaction(bool value)137   void SetForceCompaction(bool value) {
138     force_compaction_ = value;
139   }
140 
141 
142   static void Initialize();
143 
144   // Prepares for GC by resetting relocation info in old and map spaces and
145   // choosing spaces to compact.
146   void Prepare(GCTracer* tracer);
147 
148   // Performs a global garbage collection.
149   void CollectGarbage();
150 
151   // True if the last full GC performed heap compaction.
HasCompacted()152   bool HasCompacted() { return compacting_collection_; }
153 
154   // True after the Prepare phase if the compaction is taking place.
IsCompacting()155   bool IsCompacting() {
156 #ifdef DEBUG
157     // For the purposes of asserts we don't want this to keep returning true
158     // after the collection is completed.
159     return state_ != IDLE && compacting_collection_;
160 #else
161     return compacting_collection_;
162 #endif
163   }
164 
165   // The count of the number of objects left marked at the end of the last
166   // completed full GC (expected to be zero).
previous_marked_count()167   int previous_marked_count() { return previous_marked_count_; }
168 
169   // During a full GC, there is a stack-allocated GCTracer that is used for
170   // bookkeeping information.  Return a pointer to that tracer.
tracer()171   GCTracer* tracer() { return tracer_; }
172 
173 #ifdef DEBUG
174   // Checks whether performing mark-compact collection.
in_use()175   bool in_use() { return state_ > PREPARE_GC; }
are_map_pointers_encoded()176   bool are_map_pointers_encoded() { return state_ == UPDATE_POINTERS; }
177 #endif
178 
179   // Determine type of object and emit deletion log event.
180   static void ReportDeleteIfNeeded(HeapObject* obj, Isolate* isolate);
181 
182   // Returns size of a possibly marked object.
183   static int SizeOfMarkedObject(HeapObject* obj);
184 
185   // Distinguishable invalid map encodings (for single word and multiple words)
186   // that indicate free regions.
187   static const uint32_t kSingleFreeEncoding = 0;
188   static const uint32_t kMultiFreeEncoding = 1;
189 
heap()190   inline Heap* heap() const { return heap_; }
191 
code_flusher()192   CodeFlusher* code_flusher() { return code_flusher_; }
is_code_flushing_enabled()193   inline bool is_code_flushing_enabled() const { return code_flusher_ != NULL; }
194   void EnableCodeFlushing(bool enable);
195 
196  private:
197   MarkCompactCollector();
198   ~MarkCompactCollector();
199 
200 #ifdef DEBUG
201   enum CollectorState {
202     IDLE,
203     PREPARE_GC,
204     MARK_LIVE_OBJECTS,
205     SWEEP_SPACES,
206     ENCODE_FORWARDING_ADDRESSES,
207     UPDATE_POINTERS,
208     RELOCATE_OBJECTS
209   };
210 
211   // The current stage of the collector.
212   CollectorState state_;
213 #endif
214 
215   // Global flag that forces a compaction.
216   bool force_compaction_;
217 
218   // Global flag indicating whether spaces were compacted on the last GC.
219   bool compacting_collection_;
220 
221   // Global flag indicating whether spaces will be compacted on the next GC.
222   bool compact_on_next_gc_;
223 
224   // The number of objects left marked at the end of the last completed full
225   // GC (expected to be zero).
226   int previous_marked_count_;
227 
228   // A pointer to the current stack-allocated GC tracer object during a full
229   // collection (NULL before and after).
230   GCTracer* tracer_;
231 
232   // Finishes GC, performs heap verification if enabled.
233   void Finish();
234 
235   // -----------------------------------------------------------------------
236   // Phase 1: Marking live objects.
237   //
238   //  Before: The heap has been prepared for garbage collection by
239   //          MarkCompactCollector::Prepare() and is otherwise in its
240   //          normal state.
241   //
242   //   After: Live objects are marked and non-live objects are unmarked.
243 
244 
245   friend class RootMarkingVisitor;
246   friend class MarkingVisitor;
247   friend class StaticMarkingVisitor;
248   friend class CodeMarkingVisitor;
249   friend class SharedFunctionInfoMarkingVisitor;
250 
251   void PrepareForCodeFlushing();
252 
253   // Marking operations for objects reachable from roots.
254   void MarkLiveObjects();
255 
256   void MarkUnmarkedObject(HeapObject* obj);
257 
MarkObject(HeapObject * obj)258   inline void MarkObject(HeapObject* obj) {
259     if (!obj->IsMarked()) MarkUnmarkedObject(obj);
260   }
261 
262   inline void SetMark(HeapObject* obj);
263 
264   // Creates back pointers for all map transitions, stores them in
265   // the prototype field.  The original prototype pointers are restored
266   // in ClearNonLiveTransitions().  All JSObject maps
267   // connected by map transitions have the same prototype object, which
268   // is why we can use this field temporarily for back pointers.
269   void CreateBackPointers();
270 
271   // Mark a Map and its DescriptorArray together, skipping transitions.
272   void MarkMapContents(Map* map);
273   void MarkDescriptorArray(DescriptorArray* descriptors);
274 
275   // Mark the heap roots and all objects reachable from them.
276   void MarkRoots(RootMarkingVisitor* visitor);
277 
278   // Mark the symbol table specially.  References to symbols from the
279   // symbol table are weak.
280   void MarkSymbolTable();
281 
282   // Mark objects in object groups that have at least one object in the
283   // group marked.
284   void MarkObjectGroups();
285 
286   // Mark objects in implicit references groups if their parent object
287   // is marked.
288   void MarkImplicitRefGroups();
289 
290   // Mark all objects which are reachable due to host application
291   // logic like object groups or implicit references' groups.
292   void ProcessExternalMarking();
293 
294   // Mark objects reachable (transitively) from objects in the marking stack
295   // or overflowed in the heap.
296   void ProcessMarkingStack();
297 
298   // Mark objects reachable (transitively) from objects in the marking
299   // stack.  This function empties the marking stack, but may leave
300   // overflowed objects in the heap, in which case the marking stack's
301   // overflow flag will be set.
302   void EmptyMarkingStack();
303 
304   // Refill the marking stack with overflowed objects from the heap.  This
305   // function either leaves the marking stack full or clears the overflow
306   // flag on the marking stack.
307   void RefillMarkingStack();
308 
309   // Callback function for telling whether the object *p is an unmarked
310   // heap object.
311   static bool IsUnmarkedHeapObject(Object** p);
312 
313 #ifdef DEBUG
314   void UpdateLiveObjectCount(HeapObject* obj);
315 #endif
316 
317   // We sweep the large object space in the same way whether we are
318   // compacting or not, because the large object space is never compacted.
319   void SweepLargeObjectSpace();
320 
321   // Test whether a (possibly marked) object is a Map.
322   static inline bool SafeIsMap(HeapObject* object);
323 
324   // Map transitions from a live map to a dead map must be killed.
325   // We replace them with a null descriptor, with the same key.
326   void ClearNonLiveTransitions();
327 
328   // -----------------------------------------------------------------------
329   // Phase 2: Sweeping to clear mark bits and free non-live objects for
330   // a non-compacting collection, or else computing and encoding
331   // forwarding addresses for a compacting collection.
332   //
333   //  Before: Live objects are marked and non-live objects are unmarked.
334   //
335   //   After: (Non-compacting collection.)  Live objects are unmarked,
336   //          non-live regions have been added to their space's free
337   //          list.
338   //
339   //   After: (Compacting collection.)  The forwarding address of live
340   //          objects in the paged spaces is encoded in their map word
341   //          along with their (non-forwarded) map pointer.
342   //
343   //          The forwarding address of live objects in the new space is
344   //          written to their map word's offset in the inactive
345   //          semispace.
346   //
347   //          Bookkeeping data is written to the page header of
348   //          eached paged-space page that contains live objects after
349   //          compaction:
350   //
351   //          The allocation watermark field is used to track the
352   //          relocation top address, the address of the first word
353   //          after the end of the last live object in the page after
354   //          compaction.
355   //
356   //          The Page::mc_page_index field contains the zero-based index of the
357   //          page in its space.  This word is only used for map space pages, in
358   //          order to encode the map addresses in 21 bits to free 11
359   //          bits per map word for the forwarding address.
360   //
361   //          The Page::mc_first_forwarded field contains the (nonencoded)
362   //          forwarding address of the first live object in the page.
363   //
364   //          In both the new space and the paged spaces, a linked list
365   //          of live regions is constructructed (linked through
366   //          pointers in the non-live region immediately following each
367   //          live region) to speed further passes of the collector.
368 
369   // Encodes forwarding addresses of objects in compactable parts of the
370   // heap.
371   void EncodeForwardingAddresses();
372 
373   // Encodes the forwarding addresses of objects in new space.
374   void EncodeForwardingAddressesInNewSpace();
375 
376   // Function template to encode the forwarding addresses of objects in
377   // paged spaces, parameterized by allocation and non-live processing
378   // functions.
379   template<AllocationFunction Alloc, ProcessNonLiveFunction ProcessNonLive>
380   void EncodeForwardingAddressesInPagedSpace(PagedSpace* space);
381 
382   // Iterates live objects in a space, passes live objects
383   // to a callback function which returns the heap size of the object.
384   // Returns the number of live objects iterated.
385   int IterateLiveObjects(NewSpace* space, LiveObjectCallback size_f);
386   int IterateLiveObjects(PagedSpace* space, LiveObjectCallback size_f);
387 
388   // Iterates the live objects between a range of addresses, returning the
389   // number of live objects.
390   int IterateLiveObjectsInRange(Address start, Address end,
391                                 LiveObjectCallback size_func);
392 
393   // If we are not compacting the heap, we simply sweep the spaces except
394   // for the large object space, clearing mark bits and adding unmarked
395   // regions to each space's free list.
396   void SweepSpaces();
397 
398   // -----------------------------------------------------------------------
399   // Phase 3: Updating pointers in live objects.
400   //
401   //  Before: Same as after phase 2 (compacting collection).
402   //
403   //   After: All pointers in live objects, including encoded map
404   //          pointers, are updated to point to their target's new
405   //          location.
406 
407   friend class UpdatingVisitor;  // helper for updating visited objects
408 
409   // Updates pointers in all spaces.
410   void UpdatePointers();
411 
412   // Updates pointers in an object in new space.
413   // Returns the heap size of the object.
414   int UpdatePointersInNewObject(HeapObject* obj);
415 
416   // Updates pointers in an object in old spaces.
417   // Returns the heap size of the object.
418   int UpdatePointersInOldObject(HeapObject* obj);
419 
420   // Calculates the forwarding address of an object in an old space.
421   static Address GetForwardingAddressInOldSpace(HeapObject* obj);
422 
423   // -----------------------------------------------------------------------
424   // Phase 4: Relocating objects.
425   //
426   //  Before: Pointers to live objects are updated to point to their
427   //          target's new location.
428   //
429   //   After: Objects have been moved to their new addresses.
430 
431   // Relocates objects in all spaces.
432   void RelocateObjects();
433 
434   // Converts a code object's inline target to addresses, convention from
435   // address to target happens in the marking phase.
436   int ConvertCodeICTargetToAddress(HeapObject* obj);
437 
438   // Relocate a map object.
439   int RelocateMapObject(HeapObject* obj);
440 
441   // Relocates an old object.
442   int RelocateOldPointerObject(HeapObject* obj);
443   int RelocateOldDataObject(HeapObject* obj);
444 
445   // Relocate a property cell object.
446   int RelocateCellObject(HeapObject* obj);
447 
448   // Helper function.
449   inline int RelocateOldNonCodeObject(HeapObject* obj,
450                                       PagedSpace* space);
451 
452   // Relocates an object in the code space.
453   int RelocateCodeObject(HeapObject* obj);
454 
455   // Copy a new object.
456   int RelocateNewObject(HeapObject* obj);
457 
458 #ifdef DEBUG
459   // -----------------------------------------------------------------------
460   // Debugging variables, functions and classes
461   // Counters used for debugging the marking phase of mark-compact or
462   // mark-sweep collection.
463 
464   // Size of live objects in Heap::to_space_.
465   int live_young_objects_size_;
466 
467   // Size of live objects in Heap::old_pointer_space_.
468   int live_old_pointer_objects_size_;
469 
470   // Size of live objects in Heap::old_data_space_.
471   int live_old_data_objects_size_;
472 
473   // Size of live objects in Heap::code_space_.
474   int live_code_objects_size_;
475 
476   // Size of live objects in Heap::map_space_.
477   int live_map_objects_size_;
478 
479   // Size of live objects in Heap::cell_space_.
480   int live_cell_objects_size_;
481 
482   // Size of live objects in Heap::lo_space_.
483   int live_lo_objects_size_;
484 
485   // Number of live bytes in this collection.
486   int live_bytes_;
487 
488   friend class MarkObjectVisitor;
489   static void VisitObject(HeapObject* obj);
490 
491   friend class UnmarkObjectVisitor;
492   static void UnmarkObject(HeapObject* obj);
493 #endif
494 
495   Heap* heap_;
496   MarkingStack marking_stack_;
497   CodeFlusher* code_flusher_;
498 
499   friend class Heap;
500   friend class OverflowedObjectsScanner;
501 };
502 
503 
504 } }  // namespace v8::internal
505 
506 #endif  // V8_MARK_COMPACT_H_
507