src/v8/src/global-handles.cc

   1 // Copyright 2009 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 #include "v8.h"
   6
   7 #include "api.h"
   8 #include "global-handles.h"
   9
  10 #include "vm-state-inl.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14
  15
  16 ObjectGroup::~ObjectGroup() {
  17   if (info != NULL) info->Dispose();
  18   delete[] objects;
  19 }
  20
  21
  22 ImplicitRefGroup::~ImplicitRefGroup() {
  23   delete[] children;
  24 }
  25
  26
  27 class GlobalHandles::Node {
  28  public:
  29   // State transition diagram:
  30   // FREE -> NORMAL <-> WEAK -> PENDING -> NEAR_DEATH -> { NORMAL, WEAK, FREE }
  31   enum State {
  32     FREE = 0,
  33     NORMAL,     // Normal global handle.
  34     WEAK,       // Flagged as weak but not yet finalized.
  35     PENDING,    // Has been recognized as only reachable by weak handles.
  36     NEAR_DEATH  // Callback has informed the handle is near death.
  37   };
  38
  39   // Maps handle location (slot) to the containing node.
  40   static Node* FromLocation(Object** location) {
  41     ASSERT(OFFSET_OF(Node, object_) == 0);
  42     return reinterpret_cast<Node*>(location);
  43   }
  44
  45   Node() {
  46     ASSERT(OFFSET_OF(Node, class_id_) == Internals::kNodeClassIdOffset);
  47     ASSERT(OFFSET_OF(Node, flags_) == Internals::kNodeFlagsOffset);
  48     STATIC_ASSERT(static_cast<int>(NodeState::kMask) ==
  49                   Internals::kNodeStateMask);
  50     STATIC_ASSERT(WEAK == Internals::kNodeStateIsWeakValue);
  51     STATIC_ASSERT(PENDING == Internals::kNodeStateIsPendingValue);
  52     STATIC_ASSERT(NEAR_DEATH == Internals::kNodeStateIsNearDeathValue);
  53     STATIC_ASSERT(static_cast<int>(IsIndependent::kShift) ==
  54                   Internals::kNodeIsIndependentShift);
  55     STATIC_ASSERT(static_cast<int>(IsPartiallyDependent::kShift) ==
  56                   Internals::kNodeIsPartiallyDependentShift);
  57   }
  58
  59 #ifdef ENABLE_HANDLE_ZAPPING
  60   ~Node() {
  61     // TODO(1428): if it's a weak handle we should have invoked its callback.
  62     // Zap the values for eager trapping.
  63     object_ = reinterpret_cast<Object*>(kGlobalHandleZapValue);
  64     class_id_ = v8::HeapProfiler::kPersistentHandleNoClassId;
  65     index_ = 0;
  66     set_independent(false);
  67     set_partially_dependent(false);
  68     set_in_new_space_list(false);
  69     parameter_or_next_free_.next_free = NULL;
  70     weak_callback_ = NULL;
  71   }
  72 #endif
  73
  74   void Initialize(int index, Node** first_free) {
  75     index_ = static_cast<uint8_t>(index);
  76     ASSERT(static_cast<int>(index_) == index);
  77     set_state(FREE);
  78     set_in_new_space_list(false);
  79     parameter_or_next_free_.next_free = *first_free;
  80     *first_free = this;
  81   }
  82
  83   void Acquire(Object* object) {
  84     ASSERT(state() == FREE);
  85     object_ = object;
  86     class_id_ = v8::HeapProfiler::kPersistentHandleNoClassId;
  87     set_independent(false);
  88     set_partially_dependent(false);
  89     set_state(NORMAL);
  90     parameter_or_next_free_.parameter = NULL;
  91     weak_callback_ = NULL;
  92     IncreaseBlockUses();
  93   }
  94
  95   void Release() {
  96     ASSERT(state() != FREE);
  97     set_state(FREE);
  98     // Zap the values for eager trapping.
  99     object_ = reinterpret_cast<Object*>(kGlobalHandleZapValue);
 100     class_id_ = v8::HeapProfiler::kPersistentHandleNoClassId;
 101     set_independent(false);
 102     set_partially_dependent(false);
 103     weak_callback_ = NULL;
 104     DecreaseBlockUses();
 105   }
 106
 107   // Object slot accessors.
 108   Object* object() const { return object_; }
 109   Object** location() { return &object_; }
 110   Handle<Object> handle() { return Handle<Object>(location()); }
 111
 112   // Wrapper class ID accessors.
 113   bool has_wrapper_class_id() const {
 114     return class_id_ != v8::HeapProfiler::kPersistentHandleNoClassId;
 115   }
 116
 117   uint16_t wrapper_class_id() const { return class_id_; }
 118
 119   // State and flag accessors.
 120
 121   State state() const {
 122     return NodeState::decode(flags_);
 123   }
 124   void set_state(State state) {
 125     flags_ = NodeState::update(flags_, state);
 126   }
 127
 128   bool is_independent() {
 129     return IsIndependent::decode(flags_);
 130   }
 131   void set_independent(bool v) {
 132     flags_ = IsIndependent::update(flags_, v);
 133   }
 134
 135   bool is_partially_dependent() {
 136     return IsPartiallyDependent::decode(flags_);
 137   }
 138   void set_partially_dependent(bool v) {
 139     flags_ = IsPartiallyDependent::update(flags_, v);
 140   }
 141
 142   bool is_in_new_space_list() {
 143     return IsInNewSpaceList::decode(flags_);
 144   }
 145   void set_in_new_space_list(bool v) {
 146     flags_ = IsInNewSpaceList::update(flags_, v);
 147   }
 148
 149   bool IsNearDeath() const {
 150     // Check for PENDING to ensure correct answer when processing callbacks.
 151     return state() == PENDING || state() == NEAR_DEATH;
 152   }
 153
 154   bool IsWeak() const { return state() == WEAK; }
 155
 156   bool IsRetainer() const { return state() != FREE; }
 157
 158   bool IsStrongRetainer() const { return state() == NORMAL; }
 159
 160   bool IsWeakRetainer() const {
 161     return state() == WEAK || state() == PENDING || state() == NEAR_DEATH;
 162   }
 163
 164   void MarkPending() {
 165     ASSERT(state() == WEAK);
 166     set_state(PENDING);
 167   }
 168
 169   // Independent flag accessors.
 170   void MarkIndependent() {
 171     ASSERT(state() != FREE);
 172     set_independent(true);
 173   }
 174
 175   void MarkPartiallyDependent() {
 176     ASSERT(state() != FREE);
 177     if (GetGlobalHandles()->isolate()->heap()->InNewSpace(object_)) {
 178       set_partially_dependent(true);
 179     }
 180   }
 181   void clear_partially_dependent() { set_partially_dependent(false); }
 182
 183   // Callback accessor.
 184   // TODO(svenpanne) Re-enable or nuke later.
 185   // WeakReferenceCallback callback() { return callback_; }
 186
 187   // Callback parameter accessors.
 188   void set_parameter(void* parameter) {
 189     ASSERT(state() != FREE);
 190     parameter_or_next_free_.parameter = parameter;
 191   }
 192   void* parameter() const {
 193     ASSERT(state() != FREE);
 194     return parameter_or_next_free_.parameter;
 195   }
 196
 197   // Accessors for next free node in the free list.
 198   Node* next_free() {
 199     ASSERT(state() == FREE);
 200     return parameter_or_next_free_.next_free;
 201   }
 202   void set_next_free(Node* value) {
 203     ASSERT(state() == FREE);
 204     parameter_or_next_free_.next_free = value;
 205   }
 206
 207   void MakeWeak(void* parameter, WeakCallback weak_callback) {
 208     ASSERT(weak_callback != NULL);
 209     ASSERT(state() != FREE);
 210     set_state(WEAK);
 211     set_parameter(parameter);
 212     weak_callback_ = weak_callback;
 213   }
 214
 215   void* ClearWeakness() {
 216     ASSERT(state() != FREE);
 217     void* p = parameter();
 218     set_state(NORMAL);
 219     set_parameter(NULL);
 220     return p;
 221   }
 222
 223   bool PostGarbageCollectionProcessing(Isolate* isolate) {
 224     if (state() != Node::PENDING) return false;
 225     if (weak_callback_ == NULL) {
 226       Release();
 227       return false;
 228     }
 229     void* par = parameter();
 230     set_state(NEAR_DEATH);
 231     set_parameter(NULL);
 232
 233     Object** object = location();
 234     {
 235       // Check that we are not passing a finalized external string to
 236       // the callback.
 237       ASSERT(!object_->IsExternalAsciiString() ||
 238              ExternalAsciiString::cast(object_)->resource() != NULL);
 239       ASSERT(!object_->IsExternalTwoByteString() ||
 240              ExternalTwoByteString::cast(object_)->resource() != NULL);
 241       // Leaving V8.
 242       VMState<EXTERNAL> state(isolate);
 243       HandleScope handle_scope(isolate);
 244       Handle<Object> handle(*object, isolate);
 245       v8::WeakCallbackData<v8::Value, void> data(
 246           reinterpret_cast<v8::Isolate*>(isolate),
 247           v8::Utils::ToLocal(handle),
 248           par);
 249       weak_callback_(data);
 250     }
 251     // Absence of explicit cleanup or revival of weak handle
 252     // in most of the cases would lead to memory leak.
 253     CHECK(state() != NEAR_DEATH);
 254     return true;
 255   }
 256
 257   inline GlobalHandles* GetGlobalHandles();
 258
 259  private:
 260   inline NodeBlock* FindBlock();
 261   inline void IncreaseBlockUses();
 262   inline void DecreaseBlockUses();
 263
 264   // Storage for object pointer.
 265   // Placed first to avoid offset computation.
 266   Object* object_;
 267
 268   // Next word stores class_id, index, state, and independent.
 269   // Note: the most aligned fields should go first.
 270
 271   // Wrapper class ID.
 272   uint16_t class_id_;
 273
 274   // Index in the containing handle block.
 275   uint8_t index_;
 276
 277   // This stores three flags (independent, partially_dependent and
 278   // in_new_space_list) and a State.
 279   class NodeState:            public BitField<State, 0, 4> {};
 280   class IsIndependent:        public BitField<bool,  4, 1> {};
 281   class IsPartiallyDependent: public BitField<bool,  5, 1> {};
 282   class IsInNewSpaceList:     public BitField<bool,  6, 1> {};
 283
 284   uint8_t flags_;
 285
 286   // Handle specific callback - might be a weak reference in disguise.
 287   WeakCallback weak_callback_;
 288
 289   // Provided data for callback.  In FREE state, this is used for
 290   // the free list link.
 291   union {
 292     void* parameter;
 293     Node* next_free;
 294   } parameter_or_next_free_;
 295
 296   DISALLOW_COPY_AND_ASSIGN(Node);
 297 };
 298
 299
 300 class GlobalHandles::NodeBlock {
 301  public:
 302   static const int kSize = 256;
 303
 304   explicit NodeBlock(GlobalHandles* global_handles, NodeBlock* next)
 305       : next_(next),
 306         used_nodes_(0),
 307         next_used_(NULL),
 308         prev_used_(NULL),
 309         global_handles_(global_handles) {}
 310
 311   void PutNodesOnFreeList(Node** first_free) {
 312     for (int i = kSize - 1; i >= 0; --i) {
 313       nodes_[i].Initialize(i, first_free);
 314     }
 315   }
 316
 317   Node* node_at(int index) {
 318     ASSERT(0 <= index && index < kSize);
 319     return &nodes_[index];
 320   }
 321
 322   void IncreaseUses() {
 323     ASSERT(used_nodes_ < kSize);
 324     if (used_nodes_++ == 0) {
 325       NodeBlock* old_first = global_handles_->first_used_block_;
 326       global_handles_->first_used_block_ = this;
 327       next_used_ = old_first;
 328       prev_used_ = NULL;
 329       if (old_first == NULL) return;
 330       old_first->prev_used_ = this;
 331     }
 332   }
 333
 334   void DecreaseUses() {
 335     ASSERT(used_nodes_ > 0);
 336     if (--used_nodes_ == 0) {
 337       if (next_used_ != NULL) next_used_->prev_used_ = prev_used_;
 338       if (prev_used_ != NULL) prev_used_->next_used_ = next_used_;
 339       if (this == global_handles_->first_used_block_) {
 340         global_handles_->first_used_block_ = next_used_;
 341       }
 342     }
 343   }
 344
 345   GlobalHandles* global_handles() { return global_handles_; }
 346
 347   // Next block in the list of all blocks.
 348   NodeBlock* next() const { return next_; }
 349
 350   // Next/previous block in the list of blocks with used nodes.
 351   NodeBlock* next_used() const { return next_used_; }
 352   NodeBlock* prev_used() const { return prev_used_; }
 353
 354  private:
 355   Node nodes_[kSize];
 356   NodeBlock* const next_;
 357   int used_nodes_;
 358   NodeBlock* next_used_;
 359   NodeBlock* prev_used_;
 360   GlobalHandles* global_handles_;
 361 };
 362
 363
 364 GlobalHandles* GlobalHandles::Node::GetGlobalHandles() {
 365   return FindBlock()->global_handles();
 366 }
 367
 368
 369 GlobalHandles::NodeBlock* GlobalHandles::Node::FindBlock() {
 370   intptr_t ptr = reinterpret_cast<intptr_t>(this);
 371   ptr = ptr - index_ * sizeof(Node);
 372   NodeBlock* block = reinterpret_cast<NodeBlock*>(ptr);
 373   ASSERT(block->node_at(index_) == this);
 374   return block;
 375 }
 376
 377
 378 void GlobalHandles::Node::IncreaseBlockUses() {
 379   NodeBlock* node_block = FindBlock();
 380   node_block->IncreaseUses();
 381   GlobalHandles* global_handles = node_block->global_handles();
 382   global_handles->isolate()->counters()->global_handles()->Increment();
 383   global_handles->number_of_global_handles_++;
 384 }
 385
 386
 387 void GlobalHandles::Node::DecreaseBlockUses() {
 388   NodeBlock* node_block = FindBlock();
 389   GlobalHandles* global_handles = node_block->global_handles();
 390   parameter_or_next_free_.next_free = global_handles->first_free_;
 391   global_handles->first_free_ = this;
 392   node_block->DecreaseUses();
 393   global_handles->isolate()->counters()->global_handles()->Decrement();
 394   global_handles->number_of_global_handles_--;
 395 }
 396
 397
 398 class GlobalHandles::NodeIterator {
 399  public:
 400   explicit NodeIterator(GlobalHandles* global_handles)
 401       : block_(global_handles->first_used_block_),
 402         index_(0) {}
 403
 404   bool done() const { return block_ == NULL; }
 405
 406   Node* node() const {
 407     ASSERT(!done());
 408     return block_->node_at(index_);
 409   }
 410
 411   void Advance() {
 412     ASSERT(!done());
 413     if (++index_ < NodeBlock::kSize) return;
 414     index_ = 0;
 415     block_ = block_->next_used();
 416   }
 417
 418  private:
 419   NodeBlock* block_;
 420   int index_;
 421
 422   DISALLOW_COPY_AND_ASSIGN(NodeIterator);
 423 };
 424
 425
 426 GlobalHandles::GlobalHandles(Isolate* isolate)
 427     : isolate_(isolate),
 428       number_of_global_handles_(0),
 429       first_block_(NULL),
 430       first_used_block_(NULL),
 431       first_free_(NULL),
 432       post_gc_processing_count_(0),
 433       object_group_connections_(kObjectGroupConnectionsCapacity) {}
 434
 435
 436 GlobalHandles::~GlobalHandles() {
 437   NodeBlock* block = first_block_;
 438   while (block != NULL) {
 439     NodeBlock* tmp = block->next();
 440     delete block;
 441     block = tmp;
 442   }
 443   first_block_ = NULL;
 444 }
 445
 446
 447 Handle<Object> GlobalHandles::Create(Object* value) {
 448   if (first_free_ == NULL) {
 449     first_block_ = new NodeBlock(this, first_block_);
 450     first_block_->PutNodesOnFreeList(&first_free_);
 451   }
 452   ASSERT(first_free_ != NULL);
 453   // Take the first node in the free list.
 454   Node* result = first_free_;
 455   first_free_ = result->next_free();
 456   result->Acquire(value);
 457   if (isolate_->heap()->InNewSpace(value) &&
 458       !result->is_in_new_space_list()) {
 459     new_space_nodes_.Add(result);
 460     result->set_in_new_space_list(true);
 461   }
 462   return result->handle();
 463 }
 464
 465
 466 Handle<Object> GlobalHandles::CopyGlobal(Object** location) {
 467   ASSERT(location != NULL);
 468   return Node::FromLocation(location)->GetGlobalHandles()->Create(*location);
 469 }
 470
 471
 472 void GlobalHandles::Destroy(Object** location) {
 473   if (location != NULL) Node::FromLocation(location)->Release();
 474 }
 475
 476
 477 void GlobalHandles::MakeWeak(Object** location,
 478                              void* parameter,
 479                              WeakCallback weak_callback) {
 480   Node::FromLocation(location)->MakeWeak(parameter, weak_callback);
 481 }
 482
 483
 484 void* GlobalHandles::ClearWeakness(Object** location) {
 485   return Node::FromLocation(location)->ClearWeakness();
 486 }
 487
 488
 489 void GlobalHandles::MarkIndependent(Object** location) {
 490   Node::FromLocation(location)->MarkIndependent();
 491 }
 492
 493
 494 void GlobalHandles::MarkPartiallyDependent(Object** location) {
 495   Node::FromLocation(location)->MarkPartiallyDependent();
 496 }
 497
 498
 499 bool GlobalHandles::IsIndependent(Object** location) {
 500   return Node::FromLocation(location)->is_independent();
 501 }
 502
 503
 504 bool GlobalHandles::IsNearDeath(Object** location) {
 505   return Node::FromLocation(location)->IsNearDeath();
 506 }
 507
 508
 509 bool GlobalHandles::IsWeak(Object** location) {
 510   return Node::FromLocation(location)->IsWeak();
 511 }
 512
 513
 514 void GlobalHandles::IterateWeakRoots(ObjectVisitor* v) {
 515   for (NodeIterator it(this); !it.done(); it.Advance()) {
 516     if (it.node()->IsWeakRetainer()) v->VisitPointer(it.node()->location());
 517   }
 518 }
 519
 520
 521 void GlobalHandles::IdentifyWeakHandles(WeakSlotCallback f) {
 522   for (NodeIterator it(this); !it.done(); it.Advance()) {
 523     if (it.node()->IsWeak() && f(it.node()->location())) {
 524       it.node()->MarkPending();
 525     }
 526   }
 527 }
 528
 529
 530 void GlobalHandles::IterateNewSpaceStrongAndDependentRoots(ObjectVisitor* v) {
 531   for (int i = 0; i < new_space_nodes_.length(); ++i) {
 532     Node* node = new_space_nodes_[i];
 533     if (node->IsStrongRetainer() ||
 534         (node->IsWeakRetainer() && !node->is_independent() &&
 535          !node->is_partially_dependent())) {
 536         v->VisitPointer(node->location());
 537     }
 538   }
 539 }
 540
 541
 542 void GlobalHandles::IdentifyNewSpaceWeakIndependentHandles(
 543     WeakSlotCallbackWithHeap f) {
 544   for (int i = 0; i < new_space_nodes_.length(); ++i) {
 545     Node* node = new_space_nodes_[i];
 546     ASSERT(node->is_in_new_space_list());
 547     if ((node->is_independent() || node->is_partially_dependent()) &&
 548         node->IsWeak() && f(isolate_->heap(), node->location())) {
 549       node->MarkPending();
 550     }
 551   }
 552 }
 553
 554
 555 void GlobalHandles::IterateNewSpaceWeakIndependentRoots(ObjectVisitor* v) {
 556   for (int i = 0; i < new_space_nodes_.length(); ++i) {
 557     Node* node = new_space_nodes_[i];
 558     ASSERT(node->is_in_new_space_list());
 559     if ((node->is_independent() || node->is_partially_dependent()) &&
 560         node->IsWeakRetainer()) {
 561       v->VisitPointer(node->location());
 562     }
 563   }
 564 }
 565
 566
 567 bool GlobalHandles::IterateObjectGroups(ObjectVisitor* v,
 568                                         WeakSlotCallbackWithHeap can_skip) {
 569   ComputeObjectGroupsAndImplicitReferences();
 570   int last = 0;
 571   bool any_group_was_visited = false;
 572   for (int i = 0; i < object_groups_.length(); i++) {
 573     ObjectGroup* entry = object_groups_.at(i);
 574     ASSERT(entry != NULL);
 575
 576     Object*** objects = entry->objects;
 577     bool group_should_be_visited = false;
 578     for (size_t j = 0; j < entry->length; j++) {
 579       Object* object = *objects[j];
 580       if (object->IsHeapObject()) {
 581         if (!can_skip(isolate_->heap(), &object)) {
 582           group_should_be_visited = true;
 583           break;
 584         }
 585       }
 586     }
 587
 588     if (!group_should_be_visited) {
 589       object_groups_[last++] = entry;
 590       continue;
 591     }
 592
 593     // An object in the group requires visiting, so iterate over all
 594     // objects in the group.
 595     for (size_t j = 0; j < entry->length; ++j) {
 596       Object* object = *objects[j];
 597       if (object->IsHeapObject()) {
 598         v->VisitPointer(&object);
 599         any_group_was_visited = true;
 600       }
 601     }
 602
 603     // Once the entire group has been iterated over, set the object
 604     // group to NULL so it won't be processed again.
 605     delete entry;
 606     object_groups_.at(i) = NULL;
 607   }
 608   object_groups_.Rewind(last);
 609   return any_group_was_visited;
 610 }
 611
 612
 613 bool GlobalHandles::PostGarbageCollectionProcessing(
 614     GarbageCollector collector, GCTracer* tracer) {
 615   // Process weak global handle callbacks. This must be done after the
 616   // GC is completely done, because the callbacks may invoke arbitrary
 617   // API functions.
 618   ASSERT(isolate_->heap()->gc_state() == Heap::NOT_IN_GC);
 619   const int initial_post_gc_processing_count = ++post_gc_processing_count_;
 620   bool next_gc_likely_to_collect_more = false;
 621   if (collector == SCAVENGER) {
 622     for (int i = 0; i < new_space_nodes_.length(); ++i) {
 623       Node* node = new_space_nodes_[i];
 624       ASSERT(node->is_in_new_space_list());
 625       if (!node->IsRetainer()) {
 626         // Free nodes do not have weak callbacks. Do not use them to compute
 627         // the next_gc_likely_to_collect_more.
 628         continue;
 629       }
 630       // Skip dependent handles. Their weak callbacks might expect to be
 631       // called between two global garbage collection callbacks which
 632       // are not called for minor collections.
 633       if (!node->is_independent() && !node->is_partially_dependent()) {
 634         continue;
 635       }
 636       node->clear_partially_dependent();
 637       if (node->PostGarbageCollectionProcessing(isolate_)) {
 638         if (initial_post_gc_processing_count != post_gc_processing_count_) {
 639           // Weak callback triggered another GC and another round of
 640           // PostGarbageCollection processing.  The current node might
 641           // have been deleted in that round, so we need to bail out (or
 642           // restart the processing).
 643           return next_gc_likely_to_collect_more;
 644         }
 645       }
 646       if (!node->IsRetainer()) {
 647         next_gc_likely_to_collect_more = true;
 648       }
 649     }
 650   } else {
 651     for (NodeIterator it(this); !it.done(); it.Advance()) {
 652       if (!it.node()->IsRetainer()) {
 653         // Free nodes do not have weak callbacks. Do not use them to compute
 654         // the next_gc_likely_to_collect_more.
 655         continue;
 656       }
 657       it.node()->clear_partially_dependent();
 658       if (it.node()->PostGarbageCollectionProcessing(isolate_)) {
 659         if (initial_post_gc_processing_count != post_gc_processing_count_) {
 660           // See the comment above.
 661           return next_gc_likely_to_collect_more;
 662         }
 663       }
 664       if (!it.node()->IsRetainer()) {
 665         next_gc_likely_to_collect_more = true;
 666       }
 667     }
 668   }
 669   // Update the list of new space nodes.
 670   int last = 0;
 671   for (int i = 0; i < new_space_nodes_.length(); ++i) {
 672     Node* node = new_space_nodes_[i];
 673     ASSERT(node->is_in_new_space_list());
 674     if (node->IsRetainer()) {
 675       if (isolate_->heap()->InNewSpace(node->object())) {
 676         new_space_nodes_[last++] = node;
 677         tracer->increment_nodes_copied_in_new_space();
 678       } else {
 679         node->set_in_new_space_list(false);
 680         tracer->increment_nodes_promoted();
 681       }
 682     } else {
 683       node->set_in_new_space_list(false);
 684       tracer->increment_nodes_died_in_new_space();
 685     }
 686   }
 687   new_space_nodes_.Rewind(last);
 688   return next_gc_likely_to_collect_more;
 689 }
 690
 691
 692 void GlobalHandles::IterateStrongRoots(ObjectVisitor* v) {
 693   for (NodeIterator it(this); !it.done(); it.Advance()) {
 694     if (it.node()->IsStrongRetainer()) {
 695       v->VisitPointer(it.node()->location());
 696     }
 697   }
 698 }
 699
 700
 701 void GlobalHandles::IterateAllRoots(ObjectVisitor* v) {
 702   for (NodeIterator it(this); !it.done(); it.Advance()) {
 703     if (it.node()->IsRetainer()) {
 704       v->VisitPointer(it.node()->location());
 705     }
 706   }
 707 }
 708
 709
 710 void GlobalHandles::IterateAllRootsWithClassIds(ObjectVisitor* v) {
 711   for (NodeIterator it(this); !it.done(); it.Advance()) {
 712     if (it.node()->IsRetainer() && it.node()->has_wrapper_class_id()) {
 713       v->VisitEmbedderReference(it.node()->location(),
 714                                 it.node()->wrapper_class_id());
 715     }
 716   }
 717 }
 718
 719
 720 void GlobalHandles::IterateAllRootsInNewSpaceWithClassIds(ObjectVisitor* v) {
 721   for (int i = 0; i < new_space_nodes_.length(); ++i) {
 722     Node* node = new_space_nodes_[i];
 723     if (node->IsRetainer() && node->has_wrapper_class_id()) {
 724       v->VisitEmbedderReference(node->location(),
 725                                 node->wrapper_class_id());
 726     }
 727   }
 728 }
 729
 730
 731 int GlobalHandles::NumberOfWeakHandles() {
 732   int count = 0;
 733   for (NodeIterator it(this); !it.done(); it.Advance()) {
 734     if (it.node()->IsWeakRetainer()) {
 735       count++;
 736     }
 737   }
 738   return count;
 739 }
 740
 741
 742 int GlobalHandles::NumberOfGlobalObjectWeakHandles() {
 743   int count = 0;
 744   for (NodeIterator it(this); !it.done(); it.Advance()) {
 745     if (it.node()->IsWeakRetainer() &&
 746         it.node()->object()->IsJSGlobalObject()) {
 747       count++;
 748     }
 749   }
 750   return count;
 751 }
 752
 753
 754 void GlobalHandles::RecordStats(HeapStats* stats) {
 755   *stats->global_handle_count = 0;
 756   *stats->weak_global_handle_count = 0;
 757   *stats->pending_global_handle_count = 0;
 758   *stats->near_death_global_handle_count = 0;
 759   *stats->free_global_handle_count = 0;
 760   for (NodeIterator it(this); !it.done(); it.Advance()) {
 761     *stats->global_handle_count += 1;
 762     if (it.node()->state() == Node::WEAK) {
 763       *stats->weak_global_handle_count += 1;
 764     } else if (it.node()->state() == Node::PENDING) {
 765       *stats->pending_global_handle_count += 1;
 766     } else if (it.node()->state() == Node::NEAR_DEATH) {
 767       *stats->near_death_global_handle_count += 1;
 768     } else if (it.node()->state() == Node::FREE) {
 769       *stats->free_global_handle_count += 1;
 770     }
 771   }
 772 }
 773
 774 #ifdef DEBUG
 775
 776 void GlobalHandles::PrintStats() {
 777   int total = 0;
 778   int weak = 0;
 779   int pending = 0;
 780   int near_death = 0;
 781   int destroyed = 0;
 782
 783   for (NodeIterator it(this); !it.done(); it.Advance()) {
 784     total++;
 785     if (it.node()->state() == Node::WEAK) weak++;
 786     if (it.node()->state() == Node::PENDING) pending++;
 787     if (it.node()->state() == Node::NEAR_DEATH) near_death++;
 788     if (it.node()->state() == Node::FREE) destroyed++;
 789   }
 790
 791   PrintF("Global Handle Statistics:\n");
 792   PrintF("  allocated memory = %" V8_PTR_PREFIX "dB\n", sizeof(Node) * total);
 793   PrintF("  # weak       = %d\n", weak);
 794   PrintF("  # pending    = %d\n", pending);
 795   PrintF("  # near_death = %d\n", near_death);
 796   PrintF("  # free       = %d\n", destroyed);
 797   PrintF("  # total      = %d\n", total);
 798 }
 799
 800
 801 void GlobalHandles::Print() {
 802   PrintF("Global handles:\n");
 803   for (NodeIterator it(this); !it.done(); it.Advance()) {
 804     PrintF("  handle %p to %p%s\n",
 805            reinterpret_cast<void*>(it.node()->location()),
 806            reinterpret_cast<void*>(it.node()->object()),
 807            it.node()->IsWeak() ? " (weak)" : "");
 808   }
 809 }
 810
 811 #endif
 812
 813
 814
 815 void GlobalHandles::AddObjectGroup(Object*** handles,
 816                                    size_t length,
 817                                    v8::RetainedObjectInfo* info) {
 818 #ifdef DEBUG
 819   for (size_t i = 0; i < length; ++i) {
 820     ASSERT(!Node::FromLocation(handles[i])->is_independent());
 821   }
 822 #endif
 823   if (length == 0) {
 824     if (info != NULL) info->Dispose();
 825     return;
 826   }
 827   ObjectGroup* group = new ObjectGroup(length);
 828   for (size_t i = 0; i < length; ++i)
 829     group->objects[i] = handles[i];
 830   group->info = info;
 831   object_groups_.Add(group);
 832 }
 833
 834
 835 void GlobalHandles::SetObjectGroupId(Object** handle,
 836                                      UniqueId id) {
 837   object_group_connections_.Add(ObjectGroupConnection(id, handle));
 838 }
 839
 840
 841 void GlobalHandles::SetRetainedObjectInfo(UniqueId id,
 842                                           RetainedObjectInfo* info) {
 843   retainer_infos_.Add(ObjectGroupRetainerInfo(id, info));
 844 }
 845
 846
 847 void GlobalHandles::AddImplicitReferences(HeapObject** parent,
 848                                           Object*** children,
 849                                           size_t length) {
 850 #ifdef DEBUG
 851   ASSERT(!Node::FromLocation(BitCast<Object**>(parent))->is_independent());
 852   for (size_t i = 0; i < length; ++i) {
 853     ASSERT(!Node::FromLocation(children[i])->is_independent());
 854   }
 855 #endif
 856   if (length == 0) return;
 857   ImplicitRefGroup* group = new ImplicitRefGroup(parent, length);
 858   for (size_t i = 0; i < length; ++i)
 859     group->children[i] = children[i];
 860   implicit_ref_groups_.Add(group);
 861 }
 862
 863
 864 void GlobalHandles::SetReferenceFromGroup(UniqueId id, Object** child) {
 865   ASSERT(!Node::FromLocation(child)->is_independent());
 866   implicit_ref_connections_.Add(ObjectGroupConnection(id, child));
 867 }
 868
 869
 870 void GlobalHandles::SetReference(HeapObject** parent, Object** child) {
 871   ASSERT(!Node::FromLocation(child)->is_independent());
 872   ImplicitRefGroup* group = new ImplicitRefGroup(parent, 1);
 873   group->children[0] = child;
 874   implicit_ref_groups_.Add(group);
 875 }
 876
 877
 878 void GlobalHandles::RemoveObjectGroups() {
 879   for (int i = 0; i < object_groups_.length(); i++)
 880     delete object_groups_.at(i);
 881   object_groups_.Clear();
 882   for (int i = 0; i < retainer_infos_.length(); ++i)
 883     retainer_infos_[i].info->Dispose();
 884   retainer_infos_.Clear();
 885   object_group_connections_.Clear();
 886   object_group_connections_.Initialize(kObjectGroupConnectionsCapacity);
 887 }
 888
 889
 890 void GlobalHandles::RemoveImplicitRefGroups() {
 891   for (int i = 0; i < implicit_ref_groups_.length(); i++) {
 892     delete implicit_ref_groups_.at(i);
 893   }
 894   implicit_ref_groups_.Clear();
 895   implicit_ref_connections_.Clear();
 896 }
 897
 898
 899 void GlobalHandles::TearDown() {
 900   // TODO(1428): invoke weak callbacks.
 901 }
 902
 903
 904 void GlobalHandles::ComputeObjectGroupsAndImplicitReferences() {
 905   if (object_group_connections_.length() == 0) {
 906     for (int i = 0; i < retainer_infos_.length(); ++i)
 907       retainer_infos_[i].info->Dispose();
 908     retainer_infos_.Clear();
 909     implicit_ref_connections_.Clear();
 910     return;
 911   }
 912
 913   object_group_connections_.Sort();
 914   retainer_infos_.Sort();
 915   implicit_ref_connections_.Sort();
 916
 917   int info_index = 0;  // For iterating retainer_infos_.
 918   UniqueId current_group_id(0);
 919   int current_group_start = 0;
 920
 921   int current_implicit_refs_start = 0;
 922   int current_implicit_refs_end = 0;
 923   for (int i = 0; i <= object_group_connections_.length(); ++i) {
 924     if (i == 0)
 925       current_group_id = object_group_connections_[i].id;
 926     if (i == object_group_connections_.length() ||
 927         current_group_id != object_group_connections_[i].id) {
 928       // Group detected: objects in indices [current_group_start, i[.
 929
 930       // Find out which implicit references are related to this group. (We want
 931       // to ignore object groups which only have 1 object, but that object is
 932       // needed as a representative object for the implicit refrerence group.)
 933       while (current_implicit_refs_start < implicit_ref_connections_.length() &&
 934              implicit_ref_connections_[current_implicit_refs_start].id <
 935                  current_group_id)
 936         ++current_implicit_refs_start;
 937       current_implicit_refs_end = current_implicit_refs_start;
 938       while (current_implicit_refs_end < implicit_ref_connections_.length() &&
 939              implicit_ref_connections_[current_implicit_refs_end].id ==
 940                  current_group_id)
 941         ++current_implicit_refs_end;
 942
 943       if (current_implicit_refs_end > current_implicit_refs_start) {
 944         // Find a representative object for the implicit references.
 945         HeapObject** representative = NULL;
 946         for (int j = current_group_start; j < i; ++j) {
 947           Object** object = object_group_connections_[j].object;
 948           if ((*object)->IsHeapObject()) {
 949             representative = reinterpret_cast<HeapObject**>(object);
 950             break;
 951           }
 952         }
 953         if (representative) {
 954           ImplicitRefGroup* group = new ImplicitRefGroup(
 955               representative,
 956               current_implicit_refs_end - current_implicit_refs_start);
 957           for (int j = current_implicit_refs_start;
 958                j < current_implicit_refs_end;
 959                ++j) {
 960             group->children[j - current_implicit_refs_start] =
 961                 implicit_ref_connections_[j].object;
 962           }
 963           implicit_ref_groups_.Add(group);
 964         }
 965         current_implicit_refs_start = current_implicit_refs_end;
 966       }
 967
 968       // Find a RetainedObjectInfo for the group.
 969       RetainedObjectInfo* info = NULL;
 970       while (info_index < retainer_infos_.length() &&
 971              retainer_infos_[info_index].id < current_group_id) {
 972         retainer_infos_[info_index].info->Dispose();
 973         ++info_index;
 974       }
 975       if (info_index < retainer_infos_.length() &&
 976           retainer_infos_[info_index].id == current_group_id) {
 977         // This object group has an associated ObjectGroupRetainerInfo.
 978         info = retainer_infos_[info_index].info;
 979         ++info_index;
 980       }
 981
 982       // Ignore groups which only contain one object.
 983       if (i > current_group_start + 1) {
 984         ObjectGroup* group = new ObjectGroup(i - current_group_start);
 985         for (int j = current_group_start; j < i; ++j) {
 986           group->objects[j - current_group_start] =
 987               object_group_connections_[j].object;
 988         }
 989         group->info = info;
 990         object_groups_.Add(group);
 991       } else if (info) {
 992         info->Dispose();
 993       }
 994
 995       if (i < object_group_connections_.length()) {
 996         current_group_id = object_group_connections_[i].id;
 997         current_group_start = i;
 998       }
 999     }
1000   }
1001   object_group_connections_.Clear();
1002   object_group_connections_.Initialize(kObjectGroupConnectionsCapacity);
1003   retainer_infos_.Clear();
1004   implicit_ref_connections_.Clear();
1005 }
1006
1007
1008 EternalHandles::EternalHandles() : size_(0) {
1009   for (unsigned i = 0; i < ARRAY_SIZE(singleton_handles_); i++) {
1010     singleton_handles_[i] = kInvalidIndex;
1011   }
1012 }
1013
1014
1015 EternalHandles::~EternalHandles() {
1016   for (int i = 0; i < blocks_.length(); i++) delete[] blocks_[i];
1017 }
1018
1019
1020 void EternalHandles::IterateAllRoots(ObjectVisitor* visitor) {
1021   int limit = size_;
1022   for (int i = 0; i < blocks_.length(); i++) {
1023     ASSERT(limit > 0);
1024     Object** block = blocks_[i];
1025     visitor->VisitPointers(block, block + Min(limit, kSize));
1026     limit -= kSize;
1027   }
1028 }
1029
1030
1031 void EternalHandles::IterateNewSpaceRoots(ObjectVisitor* visitor) {
1032   for (int i = 0; i < new_space_indices_.length(); i++) {
1033     visitor->VisitPointer(GetLocation(new_space_indices_[i]));
1034   }
1035 }
1036
1037
1038 void EternalHandles::PostGarbageCollectionProcessing(Heap* heap) {
1039   int last = 0;
1040   for (int i = 0; i < new_space_indices_.length(); i++) {
1041     int index = new_space_indices_[i];
1042     if (heap->InNewSpace(*GetLocation(index))) {
1043       new_space_indices_[last++] = index;
1044     }
1045   }
1046   new_space_indices_.Rewind(last);
1047 }
1048
1049
1050 void EternalHandles::Create(Isolate* isolate, Object* object, int* index) {
1051   ASSERT_EQ(kInvalidIndex, *index);
1052   if (object == NULL) return;
1053   ASSERT_NE(isolate->heap()->the_hole_value(), object);
1054   int block = size_ >> kShift;
1055   int offset = size_ & kMask;
1056   // need to resize
1057   if (offset == 0) {
1058     Object** next_block = new Object*[kSize];
1059     Object* the_hole = isolate->heap()->the_hole_value();
1060     MemsetPointer(next_block, the_hole, kSize);
1061     blocks_.Add(next_block);
1062   }
1063   ASSERT_EQ(isolate->heap()->the_hole_value(), blocks_[block][offset]);
1064   blocks_[block][offset] = object;
1065   if (isolate->heap()->InNewSpace(object)) {
1066     new_space_indices_.Add(size_);
1067   }
1068   *index = size_++;
1069 }
1070
1071
1072 } }  // namespace v8::internal