Make GlobalHandle::NodeBlock deletable

src/global-handles.cc

Index: src/global-handles.cc
diff --git a/src/global-handles.cc b/src/global-handles.cc
index 88ebe31647dc954fa21f0f5deca99dbf2ccc819b..1dd1cfd171fdc900807f0cdfa5ee68eb96244f70 100644
--- a/src/global-handles.cc
+++ b/src/global-handles.cc
@@ -56,7 +56,9 @@ class GlobalHandles::Node {
     NORMAL,     // Normal global handle.
     WEAK,       // Flagged as weak but not yet finalized.
     PENDING,    // Has been recognized as only reachable by weak handles.
-    NEAR_DEATH  // Callback has informed the handle is near death.
+    NEAR_DEATH,  // Callback has informed the handle is near death.
+
+    LAST_STATE = NEAR_DEATH

[Michael Starzinger, 2013/08/01 12:29:02]

Let just rename this to STATE_COUNT or NUMBER_OF_STATES and drop the explicit
assignment of this constant.

   };
 
   // Maps handle location (slot) to the containing node.
@@ -93,13 +95,12 @@ class GlobalHandles::Node {
   }
 #endif
 
-  void Initialize(int index, Node** first_free) {
+  void Initialize(int index, Node* first_free) {
     index_ = static_cast<uint8_t>(index);
     ASSERT(static_cast<int>(index_) == index);
     set_state(FREE);
     set_in_new_space_list(false);
-    parameter_or_next_free_.next_free = *first_free;
-    *first_free = this;
+    parameter_or_next_free_.next_free = first_free;
   }
 
   void Acquire(Object* object) {
@@ -111,7 +112,6 @@ class GlobalHandles::Node {
     set_state(NORMAL);
     parameter_or_next_free_.parameter = NULL;
     weak_reference_callback_ = NULL;
-    IncreaseBlockUses();
   }
 
   void Release() {
@@ -125,7 +125,7 @@ class GlobalHandles::Node {
     set_partially_dependent(false);
     weak_reference_callback_ = NULL;
 #endif
-    DecreaseBlockUses();
+    ReleaseFromBlock();
   }
 
   // Object slot accessors.
@@ -204,10 +204,6 @@ class GlobalHandles::Node {
   }
   void clear_partially_dependent() { set_partially_dependent(false); }
 
-  // Callback accessor.
-  // TODO(svenpanne) Re-enable or nuke later.
-  // WeakReferenceCallback callback() { return callback_; }
-
   // Callback parameter accessors.
   void set_parameter(void* parameter) {
     ASSERT(state() != FREE);
@@ -276,8 +272,7 @@ class GlobalHandles::Node {
  private:
   inline NodeBlock* FindBlock();
   inline GlobalHandles* GetGlobalHandles();
-  inline void IncreaseBlockUses();
-  inline void DecreaseBlockUses();
+  inline void ReleaseFromBlock();
 
   // Storage for object pointer.
   // Placed first to avoid offset computation.
@@ -319,66 +314,287 @@ class GlobalHandles::NodeBlock {
  public:
   static const int kSize = 256;
 
-  explicit NodeBlock(GlobalHandles* global_handles, NodeBlock* next)
-      : next_(next),
-        used_nodes_(0),
-        next_used_(NULL),
-        prev_used_(NULL),
-        global_handles_(global_handles) {}
-
-  void PutNodesOnFreeList(Node** first_free) {
+  explicit NodeBlock(GlobalHandles* global_handles)
+      : used_nodes_(0),
+        first_free_(NULL),
+        next_block_(NULL),
+        prev_block_(NULL),
+        global_handles_(global_handles) {
+    // Initialize nodes
+    Node* first_free = first_free_;
     for (int i = kSize - 1; i >= 0; --i) {
       nodes_[i].Initialize(i, first_free);
+      first_free = &nodes_[i];
     }
+    first_free_ = first_free;
+    // Link into global_handles
+    ASSERT(global_handles->first_non_full_block_ == NULL);
+    global_handles->first_non_full_block_ = this;
+    global_handles->number_of_blocks_++;
+    if (global_handles->first_block_ == NULL) {
+      ASSERT(global_handles->last_block_ == NULL);
+      global_handles->first_block_ = this;
+      global_handles->last_block_ = this;
+      return;
+    }
+    ASSERT(global_handles->last_block_ != NULL);
+    prev_block_ = global_handles->last_block_;
+    prev_block_->next_block_ = this;
+    global_handles->last_block_ = this;
   }
 
-  Node* node_at(int index) {
-    ASSERT(0 <= index && index < kSize);
-    return &nodes_[index];
-  }
-
-  void IncreaseUses() {
+  Node* Acquire(Object* o) {
     ASSERT(used_nodes_ < kSize);
-    if (used_nodes_++ == 0) {
-      NodeBlock* old_first = global_handles_->first_used_block_;
-      global_handles_->first_used_block_ = this;
-      next_used_ = old_first;
-      prev_used_ = NULL;
-      if (old_first == NULL) return;
-      old_first->prev_used_ = this;
+    ASSERT(first_free_ != NULL);
+    ASSERT(global_handles_->first_non_full_block_ == this);
+    // Remove from free list
+    Node* node = first_free_;
+    first_free_ = node->next_free();
+    // Increment counters
+    global_handles_->isolate()->counters()->global_handles()->Increment();
+    global_handles_->number_of_global_handles_++;
+    // Initialize node with value
+    node->Acquire(o);
+    // Move block out of first_non_full_block_ if it becomes full
+    bool now_full = ++used_nodes_ == kSize;
+    if (now_full) {
+      global_handles_->first_non_full_block_ = next_block_;
     }
+    return node;
   }
 
-  void DecreaseUses() {
+  void Release(Node* node) {
     ASSERT(used_nodes_ > 0);
-    if (--used_nodes_ == 0) {
-      if (next_used_ != NULL) next_used_->prev_used_ = prev_used_;
-      if (prev_used_ != NULL) prev_used_->next_used_ = next_used_;
-      if (this == global_handles_->first_used_block_) {
-        global_handles_->first_used_block_ = next_used_;
+    // Add to free list
+    node->set_next_free(first_free_);
+    first_free_ = node;
+    // Decrement counters
+    global_handles_->isolate()->counters()->global_handles()->Decrement();
+    global_handles_->number_of_global_handles_--;
+    // Move this block to first_non_full_block_ if necessary
+    bool was_full = used_nodes_-- == kSize;
+    if (!was_full) return;
+    ASSERT(first_free_->next_free() == NULL);
+    ASSERT(global_handles_->first_non_full_block_ != this);
+    // Simple case: last block becomes non full. Just mark.
+    if (next_block_ == NULL) {
+      ASSERT(global_handles_->last_block_ == this);
+      ASSERT(global_handles_->first_non_full_block_ == NULL);
+      global_handles_->first_non_full_block_ = this;
+      return;
+    }
+    ASSERT(global_handles_->last_block_ != this);
+    // Unlink prev_block_ and next_block_
+    if (prev_block_ == NULL) {
+      // First block becomes non full
+      ASSERT(global_handles_->first_block_ == this);
+      global_handles_->first_block_ = next_block_;
+      next_block_->prev_block_ = NULL;
+    } else {
+      ASSERT(global_handles_->first_block_ != this);
+      prev_block_->next_block_ = next_block_;
+      next_block_->prev_block_ = prev_block_;
+    }
+    // Relink into first_non_full_block_ position
+    if (global_handles_->first_non_full_block_ == NULL) {
+      // Link into last position.
+      next_block_ = NULL;
+      prev_block_ = global_handles_->last_block_;
+      ASSERT(prev_block_->next_block_ == NULL);
+      prev_block_->next_block_ = this;
+      global_handles_->last_block_ = this;
+    } else {
+      next_block_ = global_handles_->first_non_full_block_;
+      prev_block_ = next_block_->prev_block_;
+      next_block_->prev_block_ = this;
+      if (prev_block_ == NULL) {
+        // link into first position
+        ASSERT(global_handles_->first_block_ == next_block_);
+        global_handles_->first_block_ = this;
+      } else {
+        ASSERT(global_handles_->first_block_ != next_block_);
+        prev_block_->next_block_ = this;
       }
     }
+    // Update first_non_full_block_
+    global_handles_->first_non_full_block_ = this;
   }
 
-  GlobalHandles* global_handles() { return global_handles_; }
+  static void SortBlocks(GlobalHandles* global_handles);
+  static void PruneBlocks(GlobalHandles* global_handles);
+  // Needed for quicksort
+  static int CompareBlocks(const void* a, const void* b);
+
+  Node* node_at(int index) {
+    ASSERT(0 <= index && index < kSize);
+    return &nodes_[index];
+  }
+
+#ifdef DEBUG
+  int LengthOfFreeList() {
+    int count = 0;
+    Node* node = first_free_;
+    while (node != NULL) {
+      count++;
+      node = node->next_free();
+    }
+    return count;
+  }
+#endif
 
-  // Next block in the list of all blocks.
-  NodeBlock* next() const { return next_; }
+  bool IsUnused() { return used_nodes_ == 0; }
 
-  // Next/previous block in the list of blocks with used nodes.
-  NodeBlock* next_used() const { return next_used_; }
-  NodeBlock* prev_used() const { return prev_used_; }
+  GlobalHandles* global_handles() { return global_handles_; }
+  int used_nodes() const { return used_nodes_; }
+  NodeBlock* next_block() const { return next_block_; }
+  NodeBlock* prev_block() const { return prev_block_; }
 
  private:
   Node nodes_[kSize];
-  NodeBlock* const next_;
   int used_nodes_;
-  NodeBlock* next_used_;
-  NodeBlock* prev_used_;
+  Node* first_free_;
+  NodeBlock* next_block_;
+  NodeBlock* prev_block_;
   GlobalHandles* global_handles_;
 };
 
 
+#ifdef DEBUG
+void GlobalHandles::VerifyBlockInvariants() {
+  int number_of_blocks = 0;
+  int number_of_handles = 0;
+  NodeBlock* first_non_full_block = NULL;
+  NodeBlock* block = first_block_;
+  NodeBlock* prev_block = NULL;
+  while (block != NULL) {
+    number_of_blocks++;
+    int used_nodes = block->used_nodes();
+    number_of_handles += used_nodes;
+    int unused_nodes = block->LengthOfFreeList();
+    ASSERT_EQ(used_nodes + unused_nodes, NodeBlock::kSize);
+    if (first_non_full_block != NULL) {
+      ASSERT_LT(used_nodes, NodeBlock::kSize);
+    } else if (used_nodes < NodeBlock::kSize) {
+      first_non_full_block = block;
+    } else {
+      ASSERT_EQ(used_nodes, NodeBlock::kSize);
+    }
+    prev_block = block;
+    block = block->next_block();
+  }
+  ASSERT_EQ(prev_block, last_block_);
+  ASSERT_EQ(number_of_handles, number_of_global_handles_);
+  ASSERT_EQ(number_of_blocks, number_of_blocks_);
+  ASSERT_EQ(first_non_full_block, first_non_full_block_);
+}
+#endif
+
+
+int GlobalHandles::NodeBlock::CompareBlocks(const void* a, const void* b) {
+  const NodeBlock* block_a =
+      *reinterpret_cast<const NodeBlock**>(reinterpret_cast<uintptr_t>(a));
+  const NodeBlock* block_b =
+      *reinterpret_cast<const NodeBlock**>(reinterpret_cast<uintptr_t>(b));
+  if (block_a->used_nodes_ > block_b->used_nodes_) return -1;
+  if (block_a->used_nodes_ == block_b->used_nodes_) return 0;
+  return 1;
+}
+
+
+void GlobalHandles::NodeBlock::SortBlocks(GlobalHandles* global_handles) {
+  int number_of_blocks = global_handles->number_of_blocks_;
+  // Always sort at least 2 blocks
+  if (number_of_blocks <= 1) return;
+  // Build array of blocks
+  ScopedVector<NodeBlock*> blocks(number_of_blocks);
+  {
+    NodeBlock* block = global_handles->first_block_;
+    for (int i = 0; block != NULL; i++) {
+      blocks[i] = block;
+      block = block->next_block();
+    }
+  }
+  // Sort blocks
+  qsort(blocks.start(), number_of_blocks, sizeof(blocks[0]), CompareBlocks);
+  // Relink blocks
+  NodeBlock* first_non_full_block = NULL;
+  {
+    NodeBlock* first_block = blocks[0];
+    global_handles->first_block_ = first_block;
+    first_block->prev_block_ = NULL;
+    first_block->next_block_ = blocks[1];
+    if (first_block->used_nodes_ < kSize) first_non_full_block = first_block;
+  }
+  for (int i = 1; i < number_of_blocks-1; i++) {
+    NodeBlock* block = blocks[i];
+    block->prev_block_ = blocks[i-1];
+    block->next_block_ = blocks[i+1];
+    if (first_non_full_block == NULL && block->used_nodes_ < kSize) {
+      first_non_full_block = block;
+    }
+  }
+  {
+    NodeBlock* last_block = blocks[number_of_blocks-1];
+    global_handles->last_block_ = last_block;
+    last_block->prev_block_ = blocks[number_of_blocks-2];
+    last_block->next_block_ = NULL;
+    if (first_non_full_block == NULL && last_block->used_nodes_ < kSize) {
+      first_non_full_block = last_block;
+    }
+  }
+  global_handles->first_non_full_block_ = first_non_full_block;
+}
+
+
+void GlobalHandles::NodeBlock::PruneBlocks(GlobalHandles* global_handles) {
+  static const double kUnusedPercentage = 0.30;
+  static const double kUsedPercentage = 1.30;
+  ASSERT(global_handles->last_block_ != NULL);
+  // Have at least one block available for deletion.
+  int total_slots = global_handles->number_of_blocks_*NodeBlock::kSize;

[Michael Starzinger, 2013/08/01 12:29:02]

nit: Whitespace around operators. Here and several other occurrences throughout
the file.

+  const int total_used = global_handles->number_of_global_handles_;
+  const int target_unused = static_cast<int>(Max(
+      total_used*kUsedPercentage,
+      total_slots*kUnusedPercentage));
+  NodeBlock* block = global_handles->last_block_;
+  int blocks_deleted = 0;
+  while (block->IsUnused()) {
+    // Not worth deleting
+    if (total_slots - total_used < target_unused) break;
+    // Don't delete only remaining block
+    if (block->prev_block() == NULL) break;
+    // Delete
+    NodeBlock* tmp = block;
+    block = block->prev_block();
+    total_slots -= NodeBlock::kSize;
+    delete tmp;
+    blocks_deleted++;
+  }
+  if (blocks_deleted == 0) return;
+  block->next_block_ = NULL;
+  global_handles->last_block_ = block;
+  global_handles->number_of_blocks_ -= blocks_deleted;
+}
+
+
+void GlobalHandles::SortBlocks(bool shouldPrune) {
+#ifdef DEBUG
+  VerifyBlockInvariants();
+#endif
+  // Nothing to sort or prune
+  if (first_non_full_block_ == NULL || first_block_ == last_block_) return;
+  NodeBlock::SortBlocks(this);
+#ifdef DEBUG
+  VerifyBlockInvariants();
+#endif
+  if (!shouldPrune) return;
+  NodeBlock::PruneBlocks(this);
+#ifdef DEBUG
+  VerifyBlockInvariants();
+#endif
+}
+
+
 GlobalHandles* GlobalHandles::Node::GetGlobalHandles() {
   return FindBlock()->global_handles();
 }
@@ -393,31 +609,18 @@ GlobalHandles::NodeBlock* GlobalHandles::Node::FindBlock() {
 }
 
 
-void GlobalHandles::Node::IncreaseBlockUses() {
-  NodeBlock* node_block = FindBlock();
-  node_block->IncreaseUses();
-  GlobalHandles* global_handles = node_block->global_handles();
-  global_handles->isolate()->counters()->global_handles()->Increment();
-  global_handles->number_of_global_handles_++;
-}
-
-
-void GlobalHandles::Node::DecreaseBlockUses() {
-  NodeBlock* node_block = FindBlock();
-  GlobalHandles* global_handles = node_block->global_handles();
-  parameter_or_next_free_.next_free = global_handles->first_free_;
-  global_handles->first_free_ = this;
-  node_block->DecreaseUses();
-  global_handles->isolate()->counters()->global_handles()->Decrement();
-  global_handles->number_of_global_handles_--;
+void GlobalHandles::Node::ReleaseFromBlock() {
+  FindBlock()->Release(this);
 }
 
 
 class GlobalHandles::NodeIterator {
  public:
   explicit NodeIterator(GlobalHandles* global_handles)
-      : block_(global_handles->first_used_block_),
-        index_(0) {}
+      : block_(global_handles->first_block_),
+        index_(0) {
+    SkipUnused();
+  }
 
   bool done() const { return block_ == NULL; }
 
@@ -430,10 +633,19 @@ class GlobalHandles::NodeIterator {
     ASSERT(!done());
     if (++index_ < NodeBlock::kSize) return;
     index_ = 0;
-    block_ = block_->next_used();
+    block_ = block_->next_block();
+    SkipUnused();
   }
 
+  static const int kCountArraySize = Node::LAST_STATE + 1;

[Michael Starzinger, 2013/08/01 12:29:02]

This constant is obsolete, see comment at the top of this file.

+  typedef int CountArray[kCountArraySize];
+  static int CollectStats(GlobalHandles* global_handles, CountArray counts);
+
  private:
+  inline void SkipUnused() {
+    while (block_ != NULL && block_->IsUnused()) block_ = block_->next_block();
+  }
+
   NodeBlock* block_;
   int index_;
 
@@ -441,12 +653,33 @@ class GlobalHandles::NodeIterator {
 };
 
 
+int GlobalHandles::NodeIterator::CollectStats(GlobalHandles* global_handles,
+                                              CountArray counts) {
+  for (int i = 0; i < kCountArraySize; i++) {
+    counts[i] = 0;
+  }
+  int total = 0;
+  for (NodeIterator it(global_handles); !it.done(); it.Advance()) {
+    total++;
+    Node::State state = it.node()->state();
+    ASSERT(state >= 0 && state < kCountArraySize);
+    counts[state]++;
+  }
+  // NodeIterator skips empty blocks
+  int skipped = global_handles->number_of_blocks_ * NodeBlock::kSize - total;
+  total += skipped;
+  counts[Node::FREE] += total;
+  return total;
+}
+
+
 GlobalHandles::GlobalHandles(Isolate* isolate)
     : isolate_(isolate),
+      number_of_blocks_(0),
       number_of_global_handles_(0),
       first_block_(NULL),
-      first_used_block_(NULL),
-      first_free_(NULL),
+      last_block_(NULL),
+      first_non_full_block_(NULL),
       post_gc_processing_count_(0),
       object_group_connections_(kObjectGroupConnectionsCapacity) {}
 
@@ -454,7 +687,7 @@ GlobalHandles::GlobalHandles(Isolate* isolate)
 GlobalHandles::~GlobalHandles() {
   NodeBlock* block = first_block_;
   while (block != NULL) {
-    NodeBlock* tmp = block->next();
+    NodeBlock* tmp = block->next_block();
     delete block;
     block = tmp;
   }
@@ -463,15 +696,10 @@ GlobalHandles::~GlobalHandles() {
 
 
 Handle<Object> GlobalHandles::Create(Object* value) {
-  if (first_free_ == NULL) {
-    first_block_ = new NodeBlock(this, first_block_);
-    first_block_->PutNodesOnFreeList(&first_free_);
-  }
-  ASSERT(first_free_ != NULL);
+  if (first_non_full_block_ == NULL) new NodeBlock(this);
+  ASSERT(first_non_full_block_ != NULL);
   // Take the first node in the free list.
-  Node* result = first_free_;
-  first_free_ = result->next_free();
-  result->Acquire(value);
+  Node* result = first_non_full_block_->Acquire(value);
   if (isolate_->heap()->InNewSpace(value) &&
       !result->is_in_new_space_list()) {
     new_space_nodes_.Add(result);
@@ -698,6 +926,8 @@ bool GlobalHandles::PostGarbageCollectionProcessing(
     }
   }
   new_space_nodes_.Rewind(last);
+  bool shouldPruneBlocks = collector != SCAVENGER;
+  SortBlocks(shouldPruneBlocks);
   return next_gc_likely_to_collect_more;
 }
 
@@ -765,48 +995,30 @@ int GlobalHandles::NumberOfGlobalObjectWeakHandles() {
 
 
 void GlobalHandles::RecordStats(HeapStats* stats) {
-  *stats->global_handle_count = 0;
-  *stats->weak_global_handle_count = 0;
-  *stats->pending_global_handle_count = 0;
-  *stats->near_death_global_handle_count = 0;
-  *stats->free_global_handle_count = 0;
-  for (NodeIterator it(this); !it.done(); it.Advance()) {
-    *stats->global_handle_count += 1;
-    if (it.node()->state() == Node::WEAK) {
-      *stats->weak_global_handle_count += 1;
-    } else if (it.node()->state() == Node::PENDING) {
-      *stats->pending_global_handle_count += 1;
-    } else if (it.node()->state() == Node::NEAR_DEATH) {
-      *stats->near_death_global_handle_count += 1;
-    } else if (it.node()->state() == Node::FREE) {
-      *stats->free_global_handle_count += 1;
-    }
-  }
+  NodeIterator::CountArray counts;
+  int total = NodeIterator::CollectStats(this, counts);
+  *stats->global_handle_count = total;
+  *stats->weak_global_handle_count = counts[Node::WEAK];
+  *stats->pending_global_handle_count = counts[Node::PENDING];
+  *stats->near_death_global_handle_count = counts[Node::NEAR_DEATH];
+  *stats->free_global_handle_count = counts[Node::FREE];
 }
 
+
 #ifdef DEBUG
 
 void GlobalHandles::PrintStats() {
-  int total = 0;
-  int weak = 0;
-  int pending = 0;
-  int near_death = 0;
-  int destroyed = 0;
-
-  for (NodeIterator it(this); !it.done(); it.Advance()) {
-    total++;
-    if (it.node()->state() == Node::WEAK) weak++;
-    if (it.node()->state() == Node::PENDING) pending++;
-    if (it.node()->state() == Node::NEAR_DEATH) near_death++;
-    if (it.node()->state() == Node::FREE) destroyed++;
-  }
-
+  NodeIterator::CountArray counts;
+  int total = NodeIterator::CollectStats(this, counts);
+  size_t total_consumed = sizeof(NodeBlock) * number_of_blocks_;
   PrintF("Global Handle Statistics:\n");
-  PrintF("  allocated memory = %" V8_PTR_PREFIX "dB\n", sizeof(Node) * total);
-  PrintF("  # weak       = %d\n", weak);
-  PrintF("  # pending    = %d\n", pending);
-  PrintF("  # near_death = %d\n", near_death);
-  PrintF("  # free       = %d\n", destroyed);
+  PrintF("  allocated blocks = %d\n", number_of_blocks_);
+  PrintF("  allocated memory = %" V8_PTR_PREFIX "dB\n", total_consumed);
+  PrintF("  # normal     = %d\n", counts[Node::NORMAL]);
+  PrintF("  # weak       = %d\n", counts[Node::WEAK]);
+  PrintF("  # pending    = %d\n", counts[Node::PENDING]);
+  PrintF("  # near_death = %d\n", counts[Node::NEAR_DEATH]);
+  PrintF("  # free       = %d\n", counts[Node::FREE]);
   PrintF("  # total      = %d\n", total);
 }