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