Home | History | Annotate | Download | only in src 
      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
   1087