deps/v8/src/global-handles.cc

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