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
35namespace v8 {
36namespace internal {
37
38
39ObjectGroup::~ObjectGroup() {
40  if (info != NULL) info->Dispose();
41  delete[] objects;
42}
43
44
45ImplicitRefGroup::~ImplicitRefGroup() {
46  delete[] children;
47}
48
49
50class 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
319class 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
383GlobalHandles* GlobalHandles::Node::GetGlobalHandles() {
384  return FindBlock()->global_handles();
385}
386
387
388GlobalHandles::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
397void 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
406void 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
417class 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
445GlobalHandles::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
455GlobalHandles::~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
466Handle<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
485void GlobalHandles::Destroy(Object** location) {
486  if (location != NULL) Node::FromLocation(location)->Release();
487}
488
489
490void 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
498void GlobalHandles::ClearWeakness(Object** location) {
499  Node::FromLocation(location)->ClearWeakness();
500}
501
502
503void GlobalHandles::MarkIndependent(Object** location) {
504  Node::FromLocation(location)->MarkIndependent();
505}
506
507
508void GlobalHandles::MarkPartiallyDependent(Object** location) {
509  Node::FromLocation(location)->MarkPartiallyDependent();
510}
511
512
513bool GlobalHandles::IsIndependent(Object** location) {
514  return Node::FromLocation(location)->is_independent();
515}
516
517
518bool GlobalHandles::IsNearDeath(Object** location) {
519  return Node::FromLocation(location)->IsNearDeath();
520}
521
522
523bool GlobalHandles::IsWeak(Object** location) {
524  return Node::FromLocation(location)->IsWeak();
525}
526
527
528void 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
535void 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
544void 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
556void 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
569void 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
581bool 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
627bool 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
706void 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
715void 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
724void 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
734void 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
745int 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
756int 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
768void 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
790void 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
815void 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
829void 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
849void GlobalHandles::SetObjectGroupId(Object** handle,
850                                     UniqueId id) {
851  object_group_connections_.Add(ObjectGroupConnection(id, handle));
852}
853
854
855void GlobalHandles::SetRetainedObjectInfo(UniqueId id,
856                                          RetainedObjectInfo* info) {
857  retainer_infos_.Add(ObjectGroupRetainerInfo(id, info));
858}
859
860
861void 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
878void GlobalHandles::SetReferenceFromGroup(UniqueId id, Object** child) {
879  ASSERT(!Node::FromLocation(child)->is_independent());
880  implicit_ref_connections_.Add(ObjectGroupConnection(id, child));
881}
882
883
884void 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
892void 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
904void 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
913void GlobalHandles::TearDown() {
914  // TODO(1428): invoke weak callbacks.
915}
916
917
918void 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
1022EternalHandles::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
1030EternalHandles::~EternalHandles() {
1031  for (int i = 0; i < blocks_.length(); i++) delete[] blocks_[i];
1032}
1033
1034
1035void 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
1046void 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
1053void 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
1065int 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