1 // Copyright 2011 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef V8_GLOBAL_HANDLES_H_
6 #define V8_GLOBAL_HANDLES_H_
7 
8 #include "include/v8.h"
9 #include "include/v8-profiler.h"
10 
11 #include "src/handles.h"
12 #include "src/list.h"
13 #include "src/utils.h"
14 
15 namespace v8 {
16 namespace internal {
17 
18 class HeapStats;
19 class ObjectVisitor;
20 
21 // Structure for tracking global handles.
22 // A single list keeps all the allocated global handles.
23 // Destroyed handles stay in the list but is added to the free list.
24 // At GC the destroyed global handles are removed from the free list
25 // and deallocated.
26 
27 // Data structures for tracking object groups and implicit references.
28 
29 // An object group is treated like a single JS object: if one of object in
30 // the group is alive, all objects in the same group are considered alive.
31 // An object group is used to simulate object relationship in a DOM tree.
32 
33 // An implicit references group consists of two parts: a parent object and a
34 // list of children objects.  If the parent is alive, all the children are alive
35 // too.
36 
37 struct ObjectGroup {
ObjectGroupObjectGroup38   explicit ObjectGroup(size_t length)
39       : info(NULL), length(length) {
40     DCHECK(length > 0);
41     objects = new Object**[length];
42   }
43   ~ObjectGroup();
44 
45   v8::RetainedObjectInfo* info;
46   Object*** objects;
47   size_t length;
48 };
49 
50 
51 struct ImplicitRefGroup {
ImplicitRefGroupImplicitRefGroup52   ImplicitRefGroup(HeapObject** parent, size_t length)
53       : parent(parent), length(length) {
54     DCHECK(length > 0);
55     children = new Object**[length];
56   }
57   ~ImplicitRefGroup();
58 
59   HeapObject** parent;
60   Object*** children;
61   size_t length;
62 };
63 
64 
65 // For internal bookkeeping.
66 struct ObjectGroupConnection {
ObjectGroupConnectionObjectGroupConnection67   ObjectGroupConnection(UniqueId id, Object** object)
68       : id(id), object(object) {}
69 
70   bool operator==(const ObjectGroupConnection& other) const {
71     return id == other.id;
72   }
73 
74   bool operator<(const ObjectGroupConnection& other) const {
75     return id < other.id;
76   }
77 
78   UniqueId id;
79   Object** object;
80 };
81 
82 
83 struct ObjectGroupRetainerInfo {
ObjectGroupRetainerInfoObjectGroupRetainerInfo84   ObjectGroupRetainerInfo(UniqueId id, RetainedObjectInfo* info)
85       : id(id), info(info) {}
86 
87   bool operator==(const ObjectGroupRetainerInfo& other) const {
88     return id == other.id;
89   }
90 
91   bool operator<(const ObjectGroupRetainerInfo& other) const {
92     return id < other.id;
93   }
94 
95   UniqueId id;
96   RetainedObjectInfo* info;
97 };
98 
99 
100 enum WeaknessType {
101   NORMAL_WEAK,  // Embedder gets a handle to the dying object.
102   // In the following cases, the embedder gets the parameter they passed in
103   // earlier, and 0 or 2 first internal fields. Note that the internal
104   // fields must contain aligned non-V8 pointers.  Getting pointers to V8
105   // objects through this interface would be GC unsafe so in that case the
106   // embedder gets a null pointer instead.
107   PHANTOM_WEAK,
108   PHANTOM_WEAK_2_INTERNAL_FIELDS
109 };
110 
111 
112 class GlobalHandles {
113  public:
114   ~GlobalHandles();
115 
116   // Creates a new global handle that is alive until Destroy is called.
117   Handle<Object> Create(Object* value);
118 
119   // Copy a global handle
120   static Handle<Object> CopyGlobal(Object** location);
121 
122   // Destroy a global handle.
123   static void Destroy(Object** location);
124 
125   typedef WeakCallbackData<v8::Value, void>::Callback WeakCallback;
126 
127   // For a phantom weak reference, the callback does not have access to the
128   // dying object.  Phantom weak references are preferred because they allow
129   // memory to be reclaimed in one GC cycle rather than two.  However, for
130   // historical reasons the default is non-phantom.
131   enum PhantomState { Nonphantom, Phantom };
132 
133   // Make the global handle weak and set the callback parameter for the
134   // handle.  When the garbage collector recognizes that only weak global
135   // handles point to an object the callback function is invoked (for each
136   // handle) with the handle and corresponding parameter as arguments.  By
137   // default the handle still contains a pointer to the object that is being
138   // collected.  For this reason the object is not collected until the next
139   // GC.  For a phantom weak handle the handle is cleared (set to a Smi)
140   // before the callback is invoked, but the handle can still be identified
141   // in the callback by using the location() of the handle.
142   static void MakeWeak(Object** location, void* parameter,
143                        WeakCallback weak_callback);
144 
145   // It would be nice to template this one, but it's really hard to get
146   // the template instantiator to work right if you do.
147   static void MakeWeak(Object** location, void* parameter,
148                        WeakCallbackInfo<void>::Callback weak_callback,
149                        v8::WeakCallbackType type);
150 
151   void RecordStats(HeapStats* stats);
152 
153   // Returns the current number of weak handles.
154   int NumberOfWeakHandles();
155 
156   // Returns the current number of weak handles to global objects.
157   // These handles are also included in NumberOfWeakHandles().
158   int NumberOfGlobalObjectWeakHandles();
159 
160   // Returns the current number of handles to global objects.
global_handles_count()161   int global_handles_count() const {
162     return number_of_global_handles_;
163   }
164 
165   // Clear the weakness of a global handle.
166   static void* ClearWeakness(Object** location);
167 
168   // Clear the weakness of a global handle.
169   static void MarkIndependent(Object** location);
170 
171   // Mark the reference to this object externaly unreachable.
172   static void MarkPartiallyDependent(Object** location);
173 
174   static bool IsIndependent(Object** location);
175 
176   // Tells whether global handle is near death.
177   static bool IsNearDeath(Object** location);
178 
179   // Tells whether global handle is weak.
180   static bool IsWeak(Object** location);
181 
182   // Process pending weak handles.
183   // Returns the number of freed nodes.
184   int PostGarbageCollectionProcessing(
185       GarbageCollector collector, const v8::GCCallbackFlags gc_callback_flags);
186 
187   // Iterates over all strong handles.
188   void IterateStrongRoots(ObjectVisitor* v);
189 
190   // Iterates over all handles.
191   void IterateAllRoots(ObjectVisitor* v);
192 
193   // Iterates over all handles that have embedder-assigned class ID.
194   void IterateAllRootsWithClassIds(ObjectVisitor* v);
195 
196   // Iterates over all handles in the new space that have embedder-assigned
197   // class ID.
198   void IterateAllRootsInNewSpaceWithClassIds(ObjectVisitor* v);
199 
200   // Iterate over all handles in the new space that are weak, unmodified
201   // and have class IDs
202   void IterateWeakRootsInNewSpaceWithClassIds(ObjectVisitor* v);
203 
204   // Iterates over all weak roots in heap.
205   void IterateWeakRoots(ObjectVisitor* v);
206 
207   // Find all weak handles satisfying the callback predicate, mark
208   // them as pending.
209   void IdentifyWeakHandles(WeakSlotCallback f);
210 
211   // NOTE: Five ...NewSpace... functions below are used during
212   // scavenge collections and iterate over sets of handles that are
213   // guaranteed to contain all handles holding new space objects (but
214   // may also include old space objects).
215 
216   // Iterates over strong and dependent handles. See the node above.
217   void IterateNewSpaceStrongAndDependentRoots(ObjectVisitor* v);
218 
219   // Finds weak independent or partially independent handles satisfying
220   // the callback predicate and marks them as pending. See the note above.
221   void IdentifyNewSpaceWeakIndependentHandles(WeakSlotCallbackWithHeap f);
222 
223   // Iterates over weak independent or partially independent handles.
224   // See the note above.
225   void IterateNewSpaceWeakIndependentRoots(ObjectVisitor* v);
226 
227   // Finds weak independent or unmodified handles satisfying
228   // the callback predicate and marks them as pending. See the note above.
229   void MarkNewSpaceWeakUnmodifiedObjectsPending(
230       WeakSlotCallbackWithHeap is_unscavenged);
231 
232   // Iterates over weak independent or unmodified handles.
233   // See the note above.
234   void IterateNewSpaceWeakUnmodifiedRoots(ObjectVisitor* v);
235 
236   // Identify unmodified objects that are in weak state and marks them
237   // unmodified
238   void IdentifyWeakUnmodifiedObjects(WeakSlotCallback is_unmodified);
239 
240   // Iterate over objects in object groups that have at least one object
241   // which requires visiting. The callback has to return true if objects
242   // can be skipped and false otherwise.
243   bool IterateObjectGroups(ObjectVisitor* v, WeakSlotCallbackWithHeap can_skip);
244 
245   // Add an object group.
246   // Should be only used in GC callback function before a collection.
247   // All groups are destroyed after a garbage collection.
248   void AddObjectGroup(Object*** handles,
249                       size_t length,
250                       v8::RetainedObjectInfo* info);
251 
252   // Associates handle with the object group represented by id.
253   // Should be only used in GC callback function before a collection.
254   // All groups are destroyed after a garbage collection.
255   void SetObjectGroupId(Object** handle, UniqueId id);
256 
257   // Set RetainedObjectInfo for an object group. Should not be called more than
258   // once for a group. Should not be called for a group which contains no
259   // handles.
260   void SetRetainedObjectInfo(UniqueId id, RetainedObjectInfo* info);
261 
262   // Adds an implicit reference from a group to an object. Should be only used
263   // in GC callback function before a collection. All implicit references are
264   // destroyed after a mark-compact collection.
265   void SetReferenceFromGroup(UniqueId id, Object** child);
266 
267   // Adds an implicit reference from a parent object to a child object. Should
268   // be only used in GC callback function before a collection. All implicit
269   // references are destroyed after a mark-compact collection.
270   void SetReference(HeapObject** parent, Object** child);
271 
object_groups()272   List<ObjectGroup*>* object_groups() {
273     ComputeObjectGroupsAndImplicitReferences();
274     return &object_groups_;
275   }
276 
implicit_ref_groups()277   List<ImplicitRefGroup*>* implicit_ref_groups() {
278     ComputeObjectGroupsAndImplicitReferences();
279     return &implicit_ref_groups_;
280   }
281 
282   // Remove bags, this should only happen after GC.
283   void RemoveObjectGroups();
284   void RemoveImplicitRefGroups();
285 
286   // Tear down the global handle structure.
287   void TearDown();
288 
isolate()289   Isolate* isolate() { return isolate_; }
290 
291 #ifdef DEBUG
292   void PrintStats();
293   void Print();
294 #endif
295 
296  private:
297   explicit GlobalHandles(Isolate* isolate);
298 
299   // Migrates data from the internal representation (object_group_connections_,
300   // retainer_infos_ and implicit_ref_connections_) to the public and more
301   // efficient representation (object_groups_ and implicit_ref_groups_).
302   void ComputeObjectGroupsAndImplicitReferences();
303 
304   // v8::internal::List is inefficient even for small number of elements, if we
305   // don't assign any initial capacity.
306   static const int kObjectGroupConnectionsCapacity = 20;
307 
308   class PendingPhantomCallback;
309 
310   // Helpers for PostGarbageCollectionProcessing.
311   static void InvokeSecondPassPhantomCallbacks(
312       List<PendingPhantomCallback>* callbacks, Isolate* isolate);
313   int PostScavengeProcessing(int initial_post_gc_processing_count);
314   int PostMarkSweepProcessing(int initial_post_gc_processing_count);
315   int DispatchPendingPhantomCallbacks(bool synchronous_second_pass);
316   void UpdateListOfNewSpaceNodes();
317 
318   // Internal node structures.
319   class Node;
320   class NodeBlock;
321   class NodeIterator;
322   class PendingPhantomCallbacksSecondPassTask;
323 
324   Isolate* isolate_;
325 
326   // Field always containing the number of handles to global objects.
327   int number_of_global_handles_;
328 
329   // List of all allocated node blocks.
330   NodeBlock* first_block_;
331 
332   // List of node blocks with used nodes.
333   NodeBlock* first_used_block_;
334 
335   // Free list of nodes.
336   Node* first_free_;
337 
338   // Contains all nodes holding new space objects. Note: when the list
339   // is accessed, some of the objects may have been promoted already.
340   List<Node*> new_space_nodes_;
341 
342   int post_gc_processing_count_;
343 
344   // Object groups and implicit references, public and more efficient
345   // representation.
346   List<ObjectGroup*> object_groups_;
347   List<ImplicitRefGroup*> implicit_ref_groups_;
348 
349   // Object groups and implicit references, temporary representation while
350   // constructing the groups.
351   List<ObjectGroupConnection> object_group_connections_;
352   List<ObjectGroupRetainerInfo> retainer_infos_;
353   List<ObjectGroupConnection> implicit_ref_connections_;
354 
355   List<PendingPhantomCallback> pending_phantom_callbacks_;
356 
357   friend class Isolate;
358 
359   DISALLOW_COPY_AND_ASSIGN(GlobalHandles);
360 };
361 
362 
363 class GlobalHandles::PendingPhantomCallback {
364  public:
365   typedef v8::WeakCallbackInfo<void> Data;
PendingPhantomCallback(Node * node,Data::Callback callback,void * parameter,void * internal_fields[v8::kInternalFieldsInWeakCallback])366   PendingPhantomCallback(
367       Node* node, Data::Callback callback, void* parameter,
368       void* internal_fields[v8::kInternalFieldsInWeakCallback])
369       : node_(node), callback_(callback), parameter_(parameter) {
370     for (int i = 0; i < v8::kInternalFieldsInWeakCallback; ++i) {
371       internal_fields_[i] = internal_fields[i];
372     }
373   }
374 
375   void Invoke(Isolate* isolate);
376 
node()377   Node* node() { return node_; }
callback()378   Data::Callback callback() { return callback_; }
379 
380  private:
381   Node* node_;
382   Data::Callback callback_;
383   void* parameter_;
384   void* internal_fields_[v8::kInternalFieldsInWeakCallback];
385 };
386 
387 
388 class EternalHandles {
389  public:
390   enum SingletonHandle {
391     I18N_TEMPLATE_ONE,
392     I18N_TEMPLATE_TWO,
393     DATE_CACHE_VERSION,
394 
395     NUMBER_OF_SINGLETON_HANDLES
396   };
397 
398   EternalHandles();
399   ~EternalHandles();
400 
NumberOfHandles()401   int NumberOfHandles() { return size_; }
402 
403   // Create an EternalHandle, overwriting the index.
404   void Create(Isolate* isolate, Object* object, int* index);
405 
406   // Grab the handle for an existing EternalHandle.
Get(int index)407   inline Handle<Object> Get(int index) {
408     return Handle<Object>(GetLocation(index));
409   }
410 
411   // Grab the handle for an existing SingletonHandle.
GetSingleton(SingletonHandle singleton)412   inline Handle<Object> GetSingleton(SingletonHandle singleton) {
413     DCHECK(Exists(singleton));
414     return Get(singleton_handles_[singleton]);
415   }
416 
417   // Checks whether a SingletonHandle has been assigned.
Exists(SingletonHandle singleton)418   inline bool Exists(SingletonHandle singleton) {
419     return singleton_handles_[singleton] != kInvalidIndex;
420   }
421 
422   // Assign a SingletonHandle to an empty slot and returns the handle.
CreateSingleton(Isolate * isolate,Object * object,SingletonHandle singleton)423   Handle<Object> CreateSingleton(Isolate* isolate,
424                                  Object* object,
425                                  SingletonHandle singleton) {
426     Create(isolate, object, &singleton_handles_[singleton]);
427     return Get(singleton_handles_[singleton]);
428   }
429 
430   // Iterates over all handles.
431   void IterateAllRoots(ObjectVisitor* visitor);
432   // Iterates over all handles which might be in new space.
433   void IterateNewSpaceRoots(ObjectVisitor* visitor);
434   // Rebuilds new space list.
435   void PostGarbageCollectionProcessing(Heap* heap);
436 
437  private:
438   static const int kInvalidIndex = -1;
439   static const int kShift = 8;
440   static const int kSize = 1 << kShift;
441   static const int kMask = 0xff;
442 
443   // Gets the slot for an index
GetLocation(int index)444   inline Object** GetLocation(int index) {
445     DCHECK(index >= 0 && index < size_);
446     return &blocks_[index >> kShift][index & kMask];
447   }
448 
449   int size_;
450   List<Object**> blocks_;
451   List<int> new_space_indices_;
452   int singleton_handles_[NUMBER_OF_SINGLETON_HANDLES];
453 
454   DISALLOW_COPY_AND_ASSIGN(EternalHandles);
455 };
456 
457 
458 }  // namespace internal
459 }  // namespace v8
460 
461 #endif  // V8_GLOBAL_HANDLES_H_
462