Revision: 16040
Author: [email protected]
Date: Mon Aug 5 00:34:29 2013
Log: Make GlobalHandle::NodeBlock deletable
[email protected]
BUG=
Review URL: https://codereview.chromium.org/21042004
http://code.google.com/p/v8/source/detail?r=16040
Modified:
/branches/bleeding_edge/src/global-handles.cc
/branches/bleeding_edge/src/global-handles.h
/branches/bleeding_edge/test/cctest/cctest.h
/branches/bleeding_edge/test/cctest/test-global-handles.cc
/branches/bleeding_edge/test/cctest/test-strings.cc
=======================================
--- /branches/bleeding_edge/src/global-handles.cc Sun Aug 4 23:58:48 2013
+++ /branches/bleeding_edge/src/global-handles.cc Mon Aug 5 00:34:29 2013
@@ -56,7 +56,9 @@
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.
+
+ NUMBER_OF_STATES
};
// Maps handle location (slot) to the containing node.
@@ -94,13 +96,12 @@
}
#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) {
@@ -112,7 +113,6 @@
set_state(NORMAL);
parameter_or_next_free_.parameter = NULL;
weak_reference_callback_ = NULL;
- IncreaseBlockUses();
}
void Release() {
@@ -126,7 +126,7 @@
set_partially_dependent(false);
weak_reference_callback_ = NULL;
#endif
- DecreaseBlockUses();
+ ReleaseFromBlock();
}
// Object slot accessors.
@@ -204,10 +204,6 @@
}
}
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) {
@@ -277,8 +273,7 @@
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.
@@ -316,68 +311,275 @@
};
-class GlobalHandles::NodeBlock {
+class GlobalHandles::BlockListIterator {
+ public:
+ explicit inline BlockListIterator(BlockList* anchor)
+ : anchor_(anchor), current_(anchor->next()) {
+ ASSERT(anchor->IsAnchor());
+ }
+ inline BlockList* block() const {
+ ASSERT(!done());
+ return current_;
+ }
+ inline bool done() const {
+ ASSERT_EQ(anchor_ == current_, current_->IsAnchor());
+ return anchor_ == current_;
+ }
+ inline void Advance() {
+ ASSERT(!done());
+ current_ = current_->next();
+ }
+
+ private:
+ BlockList* const anchor_;
+ BlockList* current_;
+ DISALLOW_COPY_AND_ASSIGN(BlockListIterator);
+};
+
+
+GlobalHandles::BlockList::BlockList()
+ : prev_block_(this),
+ next_block_(this),
+ first_free_(NULL),
+ used_nodes_(0) {}
+
+
+void GlobalHandles::BlockList::InsertAsNext(BlockList* const block) {
+ ASSERT(block != this);
+ ASSERT(!block->IsAnchor());
+ ASSERT(block->IsDetached());
+ block->prev_block_ = this;
+ block->next_block_ = next_block_;
+ next_block_->prev_block_ = block;
+ next_block_ = block;
+ ASSERT(!IsDetached());
+ ASSERT(!block->IsDetached());
+}
+
+
+void GlobalHandles::BlockList::Detach() {
+ ASSERT(!IsAnchor());
+ ASSERT(!IsDetached());
+ prev_block_->next_block_ = next_block_;
+ next_block_->prev_block_ = prev_block_;
+ prev_block_ = this;
+ next_block_ = this;
+ ASSERT(IsDetached());
+}
+
+
+bool GlobalHandles::BlockList::HasAtLeastLength(int length) {
+ ASSERT(IsAnchor());
+ ASSERT(length > 0);
+ for (BlockListIterator it(this); !it.done(); it.Advance()) {
+ if (--length <= 0) return true;
+ }
+ return false;
+}
+
+
+#ifdef DEBUG
+int GlobalHandles::BlockList::LengthOfFreeList() {
+ int count = 0;
+ Node* node = first_free_;
+ while (node != NULL) {
+ count++;
+ node = node->next_free();
+ }
+ return count;
+}
+#endif
+
+
+int GlobalHandles::BlockList::CompareBlocks(const void* a, const void* b) {
+ const BlockList* block_a =
+ *reinterpret_cast<const BlockList**>(reinterpret_cast<uintptr_t>(a));
+ const BlockList* block_b =
+ *reinterpret_cast<const BlockList**>(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;
+}
+
+
+class GlobalHandles::NodeBlock : public BlockList {
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)
+ : 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];
}
- }
-
- Node* node_at(int index) {
- ASSERT(0 <= index && index < kSize);
- return &nodes_[index];
+ first_free_ = first_free;
+ ASSERT(!IsAnchor());
+ // Link into global_handles
+ ASSERT(global_handles->non_full_blocks_.IsDetached());
+ global_handles->non_full_blocks_.InsertAsHead(this);
+ global_handles->number_of_blocks_++;
}
- 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_->non_full_blocks_.next() == 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);
+ bool now_full = ++used_nodes_ == kSize;
+ ASSERT_EQ(now_full, first_free_ == NULL);
+ if (now_full) {
+ // Move block to tail of non_full_blocks_
+ Detach();
+ global_handles_->full_blocks_.InsertAsTail(this);
}
+ 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_--;
+ bool was_full = used_nodes_-- == kSize;
+ ASSERT_EQ(was_full, first_free_->next_free() == NULL);
+ if (was_full) {
+ // Move this block to head of non_full_blocks_
+ Detach();
+ global_handles_->non_full_blocks_.InsertAsHead(this);
}
}
+
+ Node* node_at(int index) {
+ ASSERT(0 <= index && index < kSize);
+ return &nodes_[index];
+ }
GlobalHandles* global_handles() { return global_handles_; }
- // Next block in the list of all blocks.
- NodeBlock* next() const { return next_; }
+ static NodeBlock* Cast(BlockList* block_list) {
+ ASSERT(!block_list->IsAnchor());
+ return static_cast<NodeBlock*>(block_list);
+ }
- // 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_; }
+ static NodeBlock* From(Node* node, uint8_t index) {
+ uintptr_t ptr = reinterpret_cast<uintptr_t>(node - index);
+ ptr -= OFFSET_OF(NodeBlock, nodes_);
+ NodeBlock* block = reinterpret_cast<NodeBlock*>(ptr);
+ ASSERT(block->node_at(index) == node);
+ return block;
+ }
private:
Node nodes_[kSize];
- NodeBlock* const next_;
- int used_nodes_;
- NodeBlock* next_used_;
- NodeBlock* prev_used_;
GlobalHandles* global_handles_;
};
+
+
+void GlobalHandles::BlockList::SortBlocks(GlobalHandles* global_handles,
+ bool prune) {
+ // Always sort at least 2 blocks
+ if (!global_handles->non_full_blocks_.HasAtLeastLength(2)) return;
+ // build a vector that could contain the upper bound of the block count
+ int number_of_blocks = global_handles->block_count();
+ // Build array of blocks and update number_of_blocks to actual count
+ ScopedVector<BlockList*> blocks(number_of_blocks);
+ {
+ int i = 0;
+ BlockList* anchor = &global_handles->non_full_blocks_;
+ for (BlockListIterator it(anchor); !it.done(); it.Advance()) {
+ blocks[i++] = it.block();
+ }
+ number_of_blocks = i;
+ }
+ // Nothing to do.
+ if (number_of_blocks <= 1) return;
+ // Sort blocks
+ qsort(blocks.start(), number_of_blocks, sizeof(blocks[0]),
CompareBlocks);
+ // Prune empties
+ if (prune) {
+ static const double kUnusedPercentage = 0.30;
+ static const double kUsedPercentage = 1.30;
+ int total_slots = global_handles->number_of_blocks_ * NodeBlock::kSize;
+ const int total_used = global_handles->number_of_global_handles_;
+ const int target_unused = static_cast<int>(Max(
+ total_used * kUsedPercentage,
+ total_slots * kUnusedPercentage));
+ // Reverse through empty blocks. Note: always leave one block free.
+ int blocks_deleted = 0;
+ for (int i = number_of_blocks - 1; i > 0 && blocks[i]->IsUnused();
i--) {
+ // Not worth deleting
+ if (total_slots - total_used < target_unused) break;
+ blocks[i]->Detach();
+ delete blocks[i];
+ blocks_deleted++;
+ total_slots -= NodeBlock::kSize;
+ }
+ global_handles->number_of_blocks_ -= blocks_deleted;
+ number_of_blocks -= blocks_deleted;
+ }
+ // Relink all blocks
+ for (int i = 0; i < number_of_blocks; i++) {
+ blocks[i]->Detach();
+ global_handles->non_full_blocks_.InsertAsTail(blocks[i]);
+ }
+#ifdef DEBUG
+ // Check sorting
+ BlockList* anchor = &global_handles->non_full_blocks_;
+ int last_size = NodeBlock::kSize;
+ for (BlockListIterator it(anchor); !it.done(); it.Advance()) {
+ ASSERT(it.block()->used_nodes() <= last_size);
+ last_size = it.block()->used_nodes();
+ }
+#endif
+}
+
+
+#ifdef DEBUG
+void GlobalHandles::VerifyBlockInvariants() {
+ int number_of_blocks = 0;
+ int number_of_handles = 0;
+ for (int i = 0; i < kAllAnchorsSize; i++) {
+ for (BlockListIterator it(all_anchors_[i]); !it.done(); it.Advance()) {
+ BlockList* block = it.block();
+ 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 (all_anchors_[i] == &full_blocks_) {
+ ASSERT_EQ(NodeBlock::kSize, used_nodes);
+ } else {
+ ASSERT_NE(NodeBlock::kSize, used_nodes);
+ }
+ }
+ }
+ ASSERT_EQ(number_of_handles, number_of_global_handles_);
+ ASSERT_EQ(number_of_blocks, number_of_blocks_);
+}
+#endif
+
+
+void GlobalHandles::SortBlocks(bool shouldPrune) {
+#ifdef DEBUG
+ VerifyBlockInvariants();
+#endif
+ BlockList::SortBlocks(this, shouldPrune);
+#ifdef DEBUG
+ VerifyBlockInvariants();
+#endif
+}
GlobalHandles* GlobalHandles::Node::GetGlobalHandles() {
@@ -386,93 +588,127 @@
GlobalHandles::NodeBlock* GlobalHandles::Node::FindBlock() {
- intptr_t ptr = reinterpret_cast<intptr_t>(this);
- ptr = ptr - index_ * sizeof(Node);
- NodeBlock* block = reinterpret_cast<NodeBlock*>(ptr);
- ASSERT(block->node_at(index_) == this);
- return block;
+ return NodeBlock::From(this, index_);
}
-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) {}
+ : all_anchors_(global_handles->all_anchors_),
+ block_(all_anchors_[0]),
+ anchor_index_(0),
+ node_index_(0) {
+ AdvanceBlock();
+ }
- bool done() const { return block_ == NULL; }
+ bool done() const {
+ return anchor_index_ == kAllAnchorsSize;
+ }
Node* node() const {
ASSERT(!done());
- return block_->node_at(index_);
+ return NodeBlock::Cast(block_)->node_at(node_index_);
}
void Advance() {
ASSERT(!done());
- if (++index_ < NodeBlock::kSize) return;
- index_ = 0;
- block_ = block_->next_used();
+ if (++node_index_ < NodeBlock::kSize) return;
+ node_index_ = 0;
+ AdvanceBlock();
}
+
+ typedef int CountArray[Node::NUMBER_OF_STATES];
+ static int CollectStats(GlobalHandles* global_handles, CountArray
counts);
private:
- NodeBlock* block_;
- int index_;
+ void AdvanceBlock() {
+ ASSERT(!done());
+ while (true) {
+ block_ = block_->next();
+ // block is valid
+ if (block_ != all_anchors_[anchor_index_]) {
+ ASSERT(!done());
+ ASSERT(!block_->IsAnchor());
+ // skip empty blocks
+ if (block_->IsUnused()) continue;
+ return;
+ }
+ // jump lists
+ anchor_index_++;
+ if (anchor_index_ == kAllAnchorsSize) break;
+ block_ = all_anchors_[anchor_index_];
+ }
+ ASSERT(done());
+ }
+
+ BlockList* const * const all_anchors_;
+ BlockList* block_;
+ int anchor_index_;
+ int node_index_;
DISALLOW_COPY_AND_ASSIGN(NodeIterator);
};
+
+
+int GlobalHandles::NodeIterator::CollectStats(GlobalHandles*
global_handles,
+ CountArray counts) {
+ static const int kSize = Node::NUMBER_OF_STATES;
+ for (int i = 0; i < kSize; 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 < kSize);
+ 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),
post_gc_processing_count_(0),
- object_group_connections_(kObjectGroupConnectionsCapacity) {}
+ object_group_connections_(kObjectGroupConnectionsCapacity) {
+ all_anchors_[0] = &full_blocks_;
+ all_anchors_[1] = &non_full_blocks_;
+}
GlobalHandles::~GlobalHandles() {
- NodeBlock* block = first_block_;
- while (block != NULL) {
- NodeBlock* tmp = block->next();
- delete block;
- block = tmp;
+ for (int i = 0; i < kAllAnchorsSize; i++) {
+ BlockList* block = all_anchors_[i]->next();
+ while (block != all_anchors_[i]) {
+ BlockList* tmp = block->next();
+ block->Detach();
+ delete NodeBlock::Cast(block);
+ block = tmp;
+ }
}
- first_block_ = NULL;
}
Handle<Object> GlobalHandles::Create(Object* value) {
- if (first_free_ == NULL) {
- first_block_ = new NodeBlock(this, first_block_);
- first_block_->PutNodesOnFreeList(&first_free_);
+ if (non_full_blocks_.IsDetached()) {
+ new NodeBlock(this);
+ ASSERT(!non_full_blocks_.IsDetached());
}
- ASSERT(first_free_ != NULL);
- // Take the first node in the free list.
- Node* result = first_free_;
- first_free_ = result->next_free();
- result->Acquire(value);
+ ASSERT(non_full_blocks_.IsAnchor());
+ ASSERT(!non_full_blocks_.next()->IsAnchor());
+ Node* result = NodeBlock::Cast(non_full_blocks_.next())->Acquire(value);
if (isolate_->heap()->InNewSpace(value) &&
!result->is_in_new_space_list()) {
new_space_nodes_.Add(result);
@@ -662,22 +898,33 @@
}
}
} else {
- for (NodeIterator it(this); !it.done(); it.Advance()) {
- if (!it.node()->IsRetainer()) {
- // Free nodes do not have weak callbacks. Do not use them to
compute
- // the next_gc_likely_to_collect_more.
- continue;
+ // Must cache all blocks, as NodeIterator can't survive mutation.
+ List<NodeBlock*> blocks(number_of_blocks_);
+ for (int i = 0; i < kAllAnchorsSize; i++) {
+ for (BlockListIterator it(all_anchors_[i]); !it.done();
it.Advance()) {
+ blocks.Add(NodeBlock::Cast(it.block()));
}
- it.node()->clear_partially_dependent();
- if (it.node()->PostGarbageCollectionProcessing(isolate_)) {
- if (initial_post_gc_processing_count != post_gc_processing_count_)
{
- // See the comment above.
- return next_gc_likely_to_collect_more;
+ }
+ for (int block_index = 0; block_index < blocks.length();
block_index++) {
+ NodeBlock* block = blocks[block_index];
+ for (int node_index = 0; node_index < NodeBlock::kSize;
node_index++) {
+ Node* node = block->node_at(node_index);
+ if (!node->IsRetainer()) {
+ // Free nodes do not have weak callbacks. Do not use them to
compute
+ // the next_gc_likely_to_collect_more.
+ continue;
+ }
+ node->clear_partially_dependent();
+ if (node->PostGarbageCollectionProcessing(isolate_)) {
+ if (initial_post_gc_processing_count !=
post_gc_processing_count_) {
+ // See the comment above.
+ return next_gc_likely_to_collect_more;
+ }
+ }
+ if (!node->IsRetainer()) {
+ next_gc_likely_to_collect_more = true;
}
}
- if (!it.node()->IsRetainer()) {
- next_gc_likely_to_collect_more = true;
- }
}
}
// Update the list of new space nodes.
@@ -699,6 +946,8 @@
}
}
new_space_nodes_.Rewind(last);
+ bool shouldPruneBlocks = collector != SCAVENGER;
+ SortBlocks(shouldPruneBlocks);
return next_gc_likely_to_collect_more;
}
@@ -766,48 +1015,30 @@
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);
}
=======================================
--- /branches/bleeding_edge/src/global-handles.h Fri Jun 21 00:56:22 2013
+++ /branches/bleeding_edge/src/global-handles.h Mon Aug 5 00:34:29 2013
@@ -155,6 +155,9 @@
int global_handles_count() const {
return number_of_global_handles_;
}
+
+ // Returns the current number of allocated blocks
+ int block_count() const { return number_of_blocks_; }
// Clear the weakness of a global handle.
static void ClearWeakness(Object** location);
@@ -275,11 +278,14 @@
#ifdef DEBUG
void PrintStats();
void Print();
+ void VerifyBlockInvariants();
#endif
private:
explicit GlobalHandles(Isolate* isolate);
+ void SortBlocks(bool shouldPrune);
+
// Migrates data from the internal representation
(object_group_connections_,
// retainer_infos_ and implicit_ref_connections_) to the public and more
// efficient representation (object_groups_ and implicit_ref_groups_).
@@ -293,20 +299,64 @@
class Node;
class NodeBlock;
class NodeIterator;
+ class BlockListIterator;
+ // Base class for NodeBlock
+ class BlockList {
+ public:
+ BlockList();
+ ~BlockList() { ASSERT(IsDetached()); }
+ void Detach();
+ void InsertAsHead(BlockList* block) {
+ ASSERT(IsAnchor());
+ InsertAsNext(block);
+ }
+ void InsertAsTail(BlockList* block) {
+ ASSERT(IsAnchor());
+ prev_block_->InsertAsNext(block);
+ }
+ inline bool IsAnchor() { return first_free_ == NULL && used_nodes_ ==
0; }
+ inline bool IsDetached() {
+ ASSERT_EQ(prev_block_ == this, next_block_ == this);
+ return prev_block_ == this;
+ }
+ bool HasAtLeastLength(int length);
+ bool IsUnused() { return used_nodes_ == 0; }
+ int used_nodes() const { return used_nodes_; }
+ BlockList* next() { return next_block_; }
+ BlockList* prev() { return prev_block_; }
+#ifdef DEBUG
+ int LengthOfFreeList();
+#endif
+ static void SortBlocks(GlobalHandles* global_handles, bool prune);
+
+ protected:
+ BlockList* prev_block_;
+ BlockList* next_block_;
+ Node* first_free_;
+ int used_nodes_;
+
+ private:
+ // Needed for quicksort
+ static int CompareBlocks(const void* a, const void* b);
+ void InsertAsNext(BlockList* block);
+ DISALLOW_COPY_AND_ASSIGN(BlockList);
+ };
Isolate* isolate_;
+ // Field always containing the number of blocks allocated.
+ int number_of_blocks_;
// Field always containing the number of handles to global objects.
int number_of_global_handles_;
- // List of all allocated node blocks.
- NodeBlock* first_block_;
-
- // List of node blocks with used nodes.
- NodeBlock* first_used_block_;
+ // Anchors for doubly linked lists of blocks
+ BlockList full_blocks_;
+ BlockList non_full_blocks_;
- // Free list of nodes.
- Node* first_free_;
+ // An array of all the anchors held by GlobalHandles.
+ // This simplifies iteration across all blocks.
+ static const int kAllAnchorsSize = 2;
+ BlockList* all_anchors_[kAllAnchorsSize];
// Contains all nodes holding new space objects. Note: when the list
// is accessed, some of the objects may have been promoted already.
=======================================
--- /branches/bleeding_edge/test/cctest/cctest.h Thu Jun 13 02:27:09 2013
+++ /branches/bleeding_edge/test/cctest/cctest.h Mon Aug 5 00:34:29 2013
@@ -298,6 +298,59 @@
space->ResetFreeList();
space->ClearStats();
}
+
+
+// Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry
+class RandomNumberGenerator {
+ public:
+ RandomNumberGenerator() {
+ init();
+ }
+
+ void init(uint32_t seed = 0x5688c73e) {
+ static const uint32_t phi = 0x9e3779b9;
+ c = 362436;
+ i = kQSize-1;
+ Q[0] = seed;
+ Q[1] = seed + phi;
+ Q[2] = seed + phi + phi;
+ for (unsigned j = 3; j < kQSize; j++) {
+ Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j;
+ }
+ }
+
+ uint32_t next() {
+ uint64_t a = 18782;
+ uint32_t r = 0xfffffffe;
+ i = (i + 1) & (kQSize-1);
+ uint64_t t = a * Q[i] + c;
+ c = (t >> 32);
+ uint32_t x = static_cast<uint32_t>(t + c);
+ if (x < c) {
+ x++;
+ c++;
+ }
+ return (Q[i] = r - x);
+ }
+
+ uint32_t next(int max) {
+ return next() % max;
+ }
+
+ bool next(double threshold) {
+ ASSERT(threshold >= 0.0 && threshold <= 1.0);
+ if (threshold == 1.0) return true;
+ if (threshold == 0.0) return false;
+ uint32_t value = next() % 100000;
+ return threshold > static_cast<double>(value)/100000.0;
+ }
+
+ private:
+ static const uint32_t kQSize = 4096;
+ uint32_t Q[kQSize];
+ uint32_t c;
+ uint32_t i;
+};
#endif // ifndef CCTEST_H_
=======================================
--- /branches/bleeding_edge/test/cctest/test-global-handles.cc Wed Apr 24
08:59:23 2013
+++ /branches/bleeding_edge/test/cctest/test-global-handles.cc Mon Aug 5
00:34:29 2013
@@ -25,6 +25,9 @@
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#include <map>
+#include <vector>
+
#include "global-handles.h"
#include "cctest.h"
@@ -315,3 +318,154 @@
ASSERT(implicit_refs->at(1)->length == 1);
ASSERT(implicit_refs->at(1)->children[0] == g2c1.location());
}
+
+
+static const int kBlockSize = 256;
+
+
+TEST(BlockCollection) {
+ v8::V8::Initialize();
+ Isolate* isolate = Isolate::Current();
+ GlobalHandles* global_handles = isolate->global_handles();
+ CHECK_EQ(0, global_handles->block_count());
+ CHECK_EQ(0, global_handles->global_handles_count());
+ Object* object = isolate->heap()->undefined_value();
+ const int kNumberOfBlocks = 5;
+ typedef Handle<Object> Block[kBlockSize];
+ for (int round = 0; round < 3; round++) {
+ Block blocks[kNumberOfBlocks];
+ for (int i = 0; i < kNumberOfBlocks; i++) {
+ for (int j = 0; j < kBlockSize; j++) {
+ blocks[i][j] = global_handles->Create(object);
+ }
+ }
+ CHECK_EQ(kNumberOfBlocks, global_handles->block_count());
+ for (int i = 0; i < kNumberOfBlocks; i++) {
+ for (int j = 0; j < kBlockSize; j++) {
+ global_handles->Destroy(blocks[i][j].location());
+ }
+ }
+ isolate->heap()->CollectAllAvailableGarbage("BlockCollection");
+ CHECK_EQ(0, global_handles->global_handles_count());
+ CHECK_EQ(1, global_handles->block_count());
+ }
+}
+
+
+class RandomMutationData {
+ public:
+ explicit RandomMutationData(Isolate* isolate)
+ : isolate_(isolate), weak_offset_(0) {}
+
+ void Mutate(double strong_growth_tendency,
+ double weak_growth_tendency = 0.05) {
+ for (int i = 0; i < kBlockSize * 100; i++) {
+ if (rng_.next(strong_growth_tendency)) {
+ AddStrong();
+ } else if (strong_nodes_.size() != 0) {
+ size_t to_remove =
rng_.next(static_cast<int>(strong_nodes_.size()));
+ RemoveStrong(to_remove);
+ }
+ if (rng_.next(weak_growth_tendency)) AddWeak();
+ if (rng_.next(0.05)) {
+#ifdef DEBUG
+ isolate_->global_handles()->VerifyBlockInvariants();
+#endif
+ }
+ if (rng_.next(0.0001)) {
+ isolate_->heap()->PerformScavenge();
+ } else if (rng_.next(0.00003)) {
+ isolate_->heap()->CollectAllAvailableGarbage();
+ }
+ CheckSizes();
+ }
+ }
+
+ void RemoveAll() {
+ while (strong_nodes_.size() != 0) {
+ RemoveStrong(strong_nodes_.size() - 1);
+ }
+ isolate_->heap()->PerformScavenge();
+ isolate_->heap()->CollectAllAvailableGarbage();
+ CheckSizes();
+ }
+
+ private:
+ typedef std::vector<Object**> NodeVector;
+ typedef std::map<int32_t, Object**> NodeMap;
+
+ void CheckSizes() {
+ int stored_sizes =
+ static_cast<int>(strong_nodes_.size() + weak_nodes_.size());
+ CHECK_EQ(isolate_->global_handles()->global_handles_count(),
stored_sizes);
+ }
+
+ void AddStrong() {
+ Object* object = isolate_->heap()->undefined_value();
+ Object** location =
isolate_->global_handles()->Create(object).location();
+ strong_nodes_.push_back(location);
+ }
+
+ void RemoveStrong(size_t offset) {
+ isolate_->global_handles()->Destroy(strong_nodes_.at(offset));
+ strong_nodes_.erase(strong_nodes_.begin() + offset);
+ }
+
+ void AddWeak() {
+ v8::Isolate* isolate = reinterpret_cast<v8::Isolate*>(isolate_);
+ v8::HandleScope scope(isolate);
+ v8::Local<v8::Object> object = v8::Object::New();
+ int32_t offset = ++weak_offset_;
+ object->Set(7, v8::Integer::New(offset, isolate));
+ v8::Persistent<v8::Object> persistent(isolate, object);
+ persistent.MakeWeak(isolate, this, WeakCallback);
+ persistent.MarkIndependent();
+ Object** location = v8::Utils::OpenPersistent(persistent).location();
+ bool inserted =
+ weak_nodes_.insert(std::make_pair(offset, location)).second;
+ CHECK(inserted);
+ }
+
+ static void WeakCallback(v8::Isolate* isolate,
+ v8::Persistent<v8::Object>* persistent,
+ RandomMutationData* data) {
+ v8::Local<v8::Object> object =
+ v8::Local<v8::Object>::New(isolate, *persistent);
+ int32_t offset =
+ v8::Local<v8::Integer>::Cast(object->Get(7))->Int32Value();
+ Object** location = v8::Utils::OpenPersistent(persistent).location();
+ NodeMap& weak_nodes = data->weak_nodes_;
+ NodeMap::iterator it = weak_nodes.find(offset);
+ CHECK(it != weak_nodes.end());
+ CHECK(it->second == location);
+ weak_nodes.erase(it);
+ persistent->Dispose();
+ }
+
+ Isolate* isolate_;
+ RandomNumberGenerator rng_;
+ NodeVector strong_nodes_;
+ NodeMap weak_nodes_;
+ int32_t weak_offset_;
+};
+
+
+TEST(RandomMutation) {
+ v8::V8::Initialize();
+ Isolate* isolate = Isolate::Current();
+ CHECK_EQ(0, isolate->global_handles()->block_count());
+ HandleScope handle_scope(isolate);
+ v8::Context::Scope context_scope(
+ v8::Context::New(reinterpret_cast<v8::Isolate*>(isolate)));
+ RandomMutationData data(isolate);
+ // grow some
+ data.Mutate(0.65);
+ data.Mutate(0.55);
+ // balanced mutation
+ for (int i = 0; i < 3; i++) data.Mutate(0.50);
+ // shrink some
+ data.Mutate(0.45);
+ data.Mutate(0.35);
+ // clear everything
+ data.RemoveAll();
+}
=======================================
--- /branches/bleeding_edge/test/cctest/test-strings.cc Wed Jun 26 06:36:16
2013
+++ /branches/bleeding_edge/test/cctest/test-strings.cc Mon Aug 5 00:34:29
2013
@@ -40,58 +40,6 @@
#include "cctest.h"
#include "zone-inl.h"
-// Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry
-class RandomNumberGenerator {
- public:
- RandomNumberGenerator() {
- init();
- }
-
- void init(uint32_t seed = 0x5688c73e) {
- static const uint32_t phi = 0x9e3779b9;
- c = 362436;
- i = kQSize-1;
- Q[0] = seed;
- Q[1] = seed + phi;
- Q[2] = seed + phi + phi;
- for (unsigned j = 3; j < kQSize; j++) {
- Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j;
- }
- }
-
- uint32_t next() {
- uint64_t a = 18782;
- uint32_t r = 0xfffffffe;
- i = (i + 1) & (kQSize-1);
- uint64_t t = a * Q[i] + c;
- c = (t >> 32);
- uint32_t x = static_cast<uint32_t>(t + c);
- if (x < c) {
- x++;
- c++;
- }
- return (Q[i] = r - x);
- }
-
- uint32_t next(int max) {
- return next() % max;
- }
-
- bool next(double threshold) {
- ASSERT(threshold >= 0.0 && threshold <= 1.0);
- if (threshold == 1.0) return true;
- if (threshold == 0.0) return false;
- uint32_t value = next() % 100000;
- return threshold > static_cast<double>(value)/100000.0;
- }
-
- private:
- static const uint32_t kQSize = 4096;
- uint32_t Q[kQSize];
- uint32_t c;
- uint32_t i;
-};
-
using namespace v8::internal;
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
