1 // Copyright 2011 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_GLOBAL_HANDLES_H_ 29 #define V8_GLOBAL_HANDLES_H_ 30 31 #include "../include/v8.h" 32 #include "../include/v8-profiler.h" 33 34 #include "handles.h" 35 #include "list.h" 36 #include "v8utils.h" 37 38 namespace v8 { 39 namespace internal { 40 41 class GCTracer; 42 class HeapStats; 43 class ObjectVisitor; 44 45 // Structure for tracking global handles. 46 // A single list keeps all the allocated global handles. 47 // Destroyed handles stay in the list but is added to the free list. 48 // At GC the destroyed global handles are removed from the free list 49 // and deallocated. 50 51 // Data structures for tracking object groups and implicit references. 52 53 // An object group is treated like a single JS object: if one of object in 54 // the group is alive, all objects in the same group are considered alive. 55 // An object group is used to simulate object relationship in a DOM tree. 56 57 // An implicit references group consists of two parts: a parent object and a 58 // list of children objects. If the parent is alive, all the children are alive 59 // too. 60 61 struct ObjectGroup { 62 explicit ObjectGroup(size_t length) 63 : info(NULL), length(length) { 64 ASSERT(length > 0); 65 objects = new Object**[length]; 66 } 67 ~ObjectGroup(); 68 69 v8::RetainedObjectInfo* info; 70 Object*** objects; 71 size_t length; 72 }; 73 74 75 struct ImplicitRefGroup { 76 ImplicitRefGroup(HeapObject** parent, size_t length) 77 : parent(parent), length(length) { 78 ASSERT(length > 0); 79 children = new Object**[length]; 80 } 81 ~ImplicitRefGroup(); 82 83 HeapObject** parent; 84 Object*** children; 85 size_t length; 86 }; 87 88 89 // For internal bookkeeping. 90 struct ObjectGroupConnection { 91 ObjectGroupConnection(UniqueId id, Object** object) 92 : id(id), object(object) {} 93 94 bool operator==(const ObjectGroupConnection& other) const { 95 return id == other.id; 96 } 97 98 bool operator<(const ObjectGroupConnection& other) const { 99 return id < other.id; 100 } 101 102 UniqueId id; 103 Object** object; 104 }; 105 106 107 struct ObjectGroupRetainerInfo { 108 ObjectGroupRetainerInfo(UniqueId id, RetainedObjectInfo* info) 109 : id(id), info(info) {} 110 111 bool operator==(const ObjectGroupRetainerInfo& other) const { 112 return id == other.id; 113 } 114 115 bool operator<(const ObjectGroupRetainerInfo& other) const { 116 return id < other.id; 117 } 118 119 UniqueId id; 120 RetainedObjectInfo* info; 121 }; 122 123 124 class GlobalHandles { 125 public: 126 ~GlobalHandles(); 127 128 // Creates a new global handle that is alive until Destroy is called. 129 Handle<Object> Create(Object* value); 130 131 // Destroy a global handle. 132 static void Destroy(Object** location); 133 134 typedef WeakReferenceCallbacks<v8::Value, void>::Revivable RevivableCallback; 135 136 // Make the global handle weak and set the callback parameter for the 137 // handle. When the garbage collector recognizes that only weak global 138 // handles point to an object the handles are cleared and the callback 139 // function is invoked (for each handle) with the handle and corresponding 140 // parameter as arguments. Note: cleared means set to Smi::FromInt(0). The 141 // reason is that Smi::FromInt(0) does not change during garage collection. 142 static void MakeWeak(Object** location, 143 void* parameter, 144 RevivableCallback weak_reference_callback); 145 146 void RecordStats(HeapStats* stats); 147 148 // Returns the current number of weak handles. 149 int NumberOfWeakHandles(); 150 151 // Returns the current number of weak handles to global objects. 152 // These handles are also included in NumberOfWeakHandles(). 153 int NumberOfGlobalObjectWeakHandles(); 154 155 // Returns the current number of handles to global objects. 156 int global_handles_count() const { 157 return number_of_global_handles_; 158 } 159 160 // Clear the weakness of a global handle. 161 static void ClearWeakness(Object** location); 162 163 // Clear the weakness of a global handle. 164 static void MarkIndependent(Object** location); 165 166 // Mark the reference to this object externaly unreachable. 167 static void MarkPartiallyDependent(Object** location); 168 169 static bool IsIndependent(Object** location); 170 171 // Tells whether global handle is near death. 172 static bool IsNearDeath(Object** location); 173 174 // Tells whether global handle is weak. 175 static bool IsWeak(Object** location); 176 177 // Process pending weak handles. 178 // Returns true if next major GC is likely to collect more garbage. 179 bool PostGarbageCollectionProcessing(GarbageCollector collector, 180 GCTracer* tracer); 181 182 // Iterates over all strong handles. 183 void IterateStrongRoots(ObjectVisitor* v); 184 185 // Iterates over all handles. 186 void IterateAllRoots(ObjectVisitor* v); 187 188 // Iterates over all handles that have embedder-assigned class ID. 189 void IterateAllRootsWithClassIds(ObjectVisitor* v); 190 191 // Iterates over all handles in the new space that have embedder-assigned 192 // class ID. 193 void IterateAllRootsInNewSpaceWithClassIds(ObjectVisitor* v); 194 195 // Iterates over all weak roots in heap. 196 void IterateWeakRoots(ObjectVisitor* v); 197 198 // Find all weak handles satisfying the callback predicate, mark 199 // them as pending. 200 void IdentifyWeakHandles(WeakSlotCallback f); 201 202 // NOTE: Three ...NewSpace... functions below are used during 203 // scavenge collections and iterate over sets of handles that are 204 // guaranteed to contain all handles holding new space objects (but 205 // may also include old space objects). 206 207 // Iterates over strong and dependent handles. See the node above. 208 void IterateNewSpaceStrongAndDependentRoots(ObjectVisitor* v); 209 210 // Finds weak independent or partially independent handles satisfying 211 // the callback predicate and marks them as pending. See the note above. 212 void IdentifyNewSpaceWeakIndependentHandles(WeakSlotCallbackWithHeap f); 213 214 // Iterates over weak independent or partially independent handles. 215 // See the note above. 216 void IterateNewSpaceWeakIndependentRoots(ObjectVisitor* v); 217 218 // Iterate over objects in object groups that have at least one object 219 // which requires visiting. The callback has to return true if objects 220 // can be skipped and false otherwise. 221 bool IterateObjectGroups(ObjectVisitor* v, WeakSlotCallbackWithHeap can_skip); 222 223 // Add an object group. 224 // Should be only used in GC callback function before a collection. 225 // All groups are destroyed after a garbage collection. 226 void AddObjectGroup(Object*** handles, 227 size_t length, 228 v8::RetainedObjectInfo* info); 229 230 // Associates handle with the object group represented by id. 231 // Should be only used in GC callback function before a collection. 232 // All groups are destroyed after a garbage collection. 233 void SetObjectGroupId(Object** handle, UniqueId id); 234 235 // Set RetainedObjectInfo for an object group. Should not be called more than 236 // once for a group. Should not be called for a group which contains no 237 // handles. 238 void SetRetainedObjectInfo(UniqueId id, RetainedObjectInfo* info); 239 240 // Add an implicit references' group. 241 // Should be only used in GC callback function before a collection. 242 // All groups are destroyed after a mark-compact collection. 243 void AddImplicitReferences(HeapObject** parent, 244 Object*** children, 245 size_t length); 246 247 // Adds an implicit reference from a group to an object. Should be only used 248 // in GC callback function before a collection. All implicit references are 249 // destroyed after a mark-compact collection. 250 void SetReferenceFromGroup(UniqueId id, Object** child); 251 252 // Adds an implicit reference from a parent object to a child object. Should 253 // be only used in GC callback function before a collection. All implicit 254 // references are destroyed after a mark-compact collection. 255 void SetReference(HeapObject** parent, Object** child); 256 257 List<ObjectGroup*>* object_groups() { 258 ComputeObjectGroupsAndImplicitReferences(); 259 return &object_groups_; 260 } 261 262 List<ImplicitRefGroup*>* implicit_ref_groups() { 263 ComputeObjectGroupsAndImplicitReferences(); 264 return &implicit_ref_groups_; 265 } 266 267 // Remove bags, this should only happen after GC. 268 void RemoveObjectGroups(); 269 void RemoveImplicitRefGroups(); 270 271 // Tear down the global handle structure. 272 void TearDown(); 273 274 Isolate* isolate() { return isolate_; } 275 276 #ifdef DEBUG 277 void PrintStats(); 278 void Print(); 279 #endif 280 281 private: 282 explicit GlobalHandles(Isolate* isolate); 283 284 // Migrates data from the internal representation (object_group_connections_, 285 // retainer_infos_ and implicit_ref_connections_) to the public and more 286 // efficient representation (object_groups_ and implicit_ref_groups_). 287 void ComputeObjectGroupsAndImplicitReferences(); 288 289 // v8::internal::List is inefficient even for small number of elements, if we 290 // don't assign any initial capacity. 291 static const int kObjectGroupConnectionsCapacity = 20; 292 293 // Internal node structures. 294 class Node; 295 class NodeBlock; 296 class NodeIterator; 297 298 Isolate* isolate_; 299 300 // Field always containing the number of handles to global objects. 301 int number_of_global_handles_; 302 303 // List of all allocated node blocks. 304 NodeBlock* first_block_; 305 306 // List of node blocks with used nodes. 307 NodeBlock* first_used_block_; 308 309 // Free list of nodes. 310 Node* first_free_; 311 312 // Contains all nodes holding new space objects. Note: when the list 313 // is accessed, some of the objects may have been promoted already. 314 List<Node*> new_space_nodes_; 315 316 int post_gc_processing_count_; 317 318 // Object groups and implicit references, public and more efficient 319 // representation. 320 List<ObjectGroup*> object_groups_; 321 List<ImplicitRefGroup*> implicit_ref_groups_; 322 323 // Object groups and implicit references, temporary representation while 324 // constructing the groups. 325 List<ObjectGroupConnection> object_group_connections_; 326 List<ObjectGroupRetainerInfo> retainer_infos_; 327 List<ObjectGroupConnection> implicit_ref_connections_; 328 329 friend class Isolate; 330 331 DISALLOW_COPY_AND_ASSIGN(GlobalHandles); 332 }; 333 334 335 class EternalHandles { 336 public: 337 enum SingletonHandle { 338 I18N_TEMPLATE_ONE, 339 I18N_TEMPLATE_TWO, 340 341 NUMBER_OF_SINGLETON_HANDLES 342 }; 343 344 EternalHandles(); 345 ~EternalHandles(); 346 347 int NumberOfHandles() { return size_; } 348 349 // Create an EternalHandle, returning the index. 350 int Create(Isolate* isolate, Object* object); 351 352 // Grab the handle for an existing EternalHandle. 353 inline Handle<Object> Get(int index) { 354 return Handle<Object>(GetLocation(index)); 355 } 356 357 // Grab the handle for an existing SingletonHandle. 358 inline Handle<Object> GetSingleton(SingletonHandle singleton) { 359 ASSERT(Exists(singleton)); 360 return Get(singleton_handles_[singleton]); 361 } 362 363 // Checks whether a SingletonHandle has been assigned. 364 inline bool Exists(SingletonHandle singleton) { 365 return singleton_handles_[singleton] != kInvalidIndex; 366 } 367 368 // Assign a SingletonHandle to an empty slot and returns the handle. 369 Handle<Object> CreateSingleton(Isolate* isolate, 370 Object* object, 371 SingletonHandle singleton) { 372 ASSERT(singleton_handles_[singleton] == kInvalidIndex); 373 singleton_handles_[singleton] = Create(isolate, object); 374 return Get(singleton_handles_[singleton]); 375 } 376 377 // Iterates over all handles. 378 void IterateAllRoots(ObjectVisitor* visitor); 379 // Iterates over all handles which might be in new space. 380 void IterateNewSpaceRoots(ObjectVisitor* visitor); 381 // Rebuilds new space list. 382 void PostGarbageCollectionProcessing(Heap* heap); 383 384 private: 385 static const int kInvalidIndex = -1; 386 static const int kShift = 8; 387 static const int kSize = 1 << kShift; 388 static const int kMask = 0xff; 389 390 // Gets the slot for an index 391 inline Object** GetLocation(int index) { 392 ASSERT(index >= 0 && index < size_); 393 return &blocks_[index >> kShift][index & kMask]; 394 } 395 396 int size_; 397 List<Object**> blocks_; 398 List<int> new_space_indices_; 399 int singleton_handles_[NUMBER_OF_SINGLETON_HANDLES]; 400 401 DISALLOW_COPY_AND_ASSIGN(EternalHandles); 402 }; 403 404 405 } } // namespace v8::internal 406 407 #endif // V8_GLOBAL_HANDLES_H_ 408