src/profile-generator.cc - fp2-dev/platform/external/v8 - Gitiles

 // Copyright 2010 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
 //       with the distribution.
 //     * Neither the name of Google Inc. nor the names of its
 //       contributors may be used to endorse or promote products derived
 //       from this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 #ifdef ENABLE_LOGGING_AND_PROFILING

 #include "v8.h"

 #include "profile-generator-inl.h"

 #include "../include/v8-profiler.h"

 namespace v8 {
 namespace internal {


 const char* CodeEntry::kEmptyNamePrefix = "";
 unsigned CodeEntry::next_call_uid_ = 1;


 ProfileNode* ProfileNode::FindChild(CodeEntry* entry) {
   HashMap::Entry* map_entry =
       children_.Lookup(entry, CodeEntryHash(entry), false);
   return map_entry != NULL ?
       reinterpret_cast<ProfileNode*>(map_entry->value) : NULL;
 }


 ProfileNode* ProfileNode::FindOrAddChild(CodeEntry* entry) {
   HashMap::Entry* map_entry =
       children_.Lookup(entry, CodeEntryHash(entry), true);
   if (map_entry->value == NULL) {
     // New node added.
     ProfileNode* new_node = new ProfileNode(tree_, entry);
     map_entry->value = new_node;
     children_list_.Add(new_node);
   }
   return reinterpret_cast<ProfileNode*>(map_entry->value);
 }


 double ProfileNode::GetSelfMillis() const {
   return tree_->TicksToMillis(self_ticks_);
 }


 double ProfileNode::GetTotalMillis() const {
   return tree_->TicksToMillis(total_ticks_);
 }


 void ProfileNode::Print(int indent) {
   OS::Print("%5u %5u %*c %s%s",
             total_ticks_, self_ticks_,
             indent, ' ',
             entry_->name_prefix(),
             entry_->name());
   if (entry_->resource_name()[0] != '\0')
     OS::Print(" %s:%d", entry_->resource_name(), entry_->line_number());
   OS::Print("\n");
   for (HashMap::Entry* p = children_.Start();
        p != NULL;
        p = children_.Next(p)) {
     reinterpret_cast<ProfileNode*>(p->value)->Print(indent + 2);
   }
 }


 namespace {

 class DeleteNodesCallback {
  public:
   void AfterAllChildrenTraversed(ProfileNode* node) {
     delete node;
   }

   void AfterChildTraversed(ProfileNode*, ProfileNode*) { }
 };

 }  // namespace


 ProfileTree::ProfileTree()
     : root_entry_(Logger::FUNCTION_TAG, "", "(root)", "", 0),
       root_(new ProfileNode(this, &root_entry_)) {
 }


 ProfileTree::~ProfileTree() {
   DeleteNodesCallback cb;
   TraverseDepthFirstPostOrder(&cb);
 }


 void ProfileTree::AddPathFromEnd(const Vector<CodeEntry*>& path) {
   ProfileNode* node = root_;
   for (CodeEntry** entry = path.start() + path.length() - 1;
        entry != path.start() - 1;
        --entry) {
     if (*entry != NULL) {
       node = node->FindOrAddChild(*entry);
     }
   }
   node->IncrementSelfTicks();
 }


 void ProfileTree::AddPathFromStart(const Vector<CodeEntry*>& path) {
   ProfileNode* node = root_;
   for (CodeEntry** entry = path.start();
        entry != path.start() + path.length();
        ++entry) {
     if (*entry != NULL) {
       node = node->FindOrAddChild(*entry);
     }
   }
   node->IncrementSelfTicks();
 }


 void ProfileTree::SetTickRatePerMs(double ticks_per_ms) {
   ms_to_ticks_scale_ = ticks_per_ms > 0 ? 1.0 / ticks_per_ms : 1.0;
 }


 namespace {

 class Position {
  public:
   explicit Position(ProfileNode* node)
       : node(node), child_idx_(0) { }
   INLINE(ProfileNode* current_child()) {
     return node->children()->at(child_idx_);
   }
   INLINE(bool has_current_child()) {
     return child_idx_ < node->children()->length();
   }
   INLINE(void next_child()) { ++child_idx_; }

   ProfileNode* node;
  private:
   int child_idx_;
 };

 }  // namespace


 // Non-recursive implementation of a depth-first post-order tree traversal.
 template <typename Callback>
 void ProfileTree::TraverseDepthFirstPostOrder(Callback* callback) {
   List<Position> stack(10);
   stack.Add(Position(root_));
   do {
     Position& current = stack.last();
     if (current.has_current_child()) {
       stack.Add(Position(current.current_child()));
     } else {
       callback->AfterAllChildrenTraversed(current.node);
       if (stack.length() > 1) {
         Position& parent = stack[stack.length() - 2];
         callback->AfterChildTraversed(parent.node, current.node);
         parent.next_child();
         // Remove child from the stack.
         stack.RemoveLast();
       }
     }
   } while (stack.length() > 1 || stack.last().has_current_child());
 }


 namespace {

 class CalculateTotalTicksCallback {
  public:
   void AfterAllChildrenTraversed(ProfileNode* node) {
     node->IncreaseTotalTicks(node->self_ticks());
   }

   void AfterChildTraversed(ProfileNode* parent, ProfileNode* child) {
     parent->IncreaseTotalTicks(child->total_ticks());
   }
 };

 }  // namespace


 void ProfileTree::CalculateTotalTicks() {
   CalculateTotalTicksCallback cb;
   TraverseDepthFirstPostOrder(&cb);
 }


 void ProfileTree::ShortPrint() {
   OS::Print("root: %u %u %.2fms %.2fms\n",
             root_->total_ticks(), root_->self_ticks(),
             root_->GetTotalMillis(), root_->GetSelfMillis());
 }


 void CpuProfile::AddPath(const Vector<CodeEntry*>& path) {
   top_down_.AddPathFromEnd(path);
   bottom_up_.AddPathFromStart(path);
 }


 void CpuProfile::CalculateTotalTicks() {
   top_down_.CalculateTotalTicks();
   bottom_up_.CalculateTotalTicks();
 }


 void CpuProfile::SetActualSamplingRate(double actual_sampling_rate) {
   top_down_.SetTickRatePerMs(actual_sampling_rate);
   bottom_up_.SetTickRatePerMs(actual_sampling_rate);
 }


 void CpuProfile::ShortPrint() {
   OS::Print("top down ");
   top_down_.ShortPrint();
   OS::Print("bottom up ");
   bottom_up_.ShortPrint();
 }


 void CpuProfile::Print() {
   OS::Print("[Top down]:\n");
   top_down_.Print();
   OS::Print("[Bottom up]:\n");
   bottom_up_.Print();
 }


 const CodeMap::CodeTreeConfig::Key CodeMap::CodeTreeConfig::kNoKey = NULL;
 const CodeMap::CodeTreeConfig::Value CodeMap::CodeTreeConfig::kNoValue =
     CodeMap::CodeEntryInfo(NULL, 0);


 void CodeMap::AddAlias(Address alias, Address addr) {
   CodeTree::Locator locator;
   if (tree_.Find(addr, &locator)) {
     const CodeEntryInfo& entry_info = locator.value();
     tree_.Insert(alias, &locator);
     locator.set_value(entry_info);
   }
 }


 CodeEntry* CodeMap::FindEntry(Address addr) {
   CodeTree::Locator locator;
   if (tree_.FindGreatestLessThan(addr, &locator)) {
     // locator.key() <= addr. Need to check that addr is within entry.
     const CodeEntryInfo& entry = locator.value();
     if (addr < (locator.key() + entry.size))
       return entry.entry;
   }
   return NULL;
 }


 void CodeMap::CodeTreePrinter::Call(
     const Address& key, const CodeMap::CodeEntryInfo& value) {
   OS::Print("%p %5d %s\n", key, value.size, value.entry->name());
 }


 void CodeMap::Print() {
   CodeTreePrinter printer;
   tree_.ForEach(&printer);
 }


 CpuProfilesCollection::CpuProfilesCollection()
     : function_and_resource_names_(StringsMatch),
       profiles_uids_(CpuProfilesMatch),
       current_profiles_semaphore_(OS::CreateSemaphore(1)) {
 }


 static void DeleteArgsCountName(char** name_ptr) {
   DeleteArray(*name_ptr);
 }


 static void DeleteCodeEntry(CodeEntry** entry_ptr) {
   delete *entry_ptr;
 }

 static void DeleteCpuProfile(CpuProfile** profile_ptr) {
   delete *profile_ptr;
 }


 CpuProfilesCollection::~CpuProfilesCollection() {
   delete current_profiles_semaphore_;
   current_profiles_.Iterate(DeleteCpuProfile);
   profiles_.Iterate(DeleteCpuProfile);
   code_entries_.Iterate(DeleteCodeEntry);
   args_count_names_.Iterate(DeleteArgsCountName);
   for (HashMap::Entry* p = function_and_resource_names_.Start();
        p != NULL;
        p = function_and_resource_names_.Next(p)) {
     DeleteArray(reinterpret_cast<const char*>(p->value));
   }
 }


 bool CpuProfilesCollection::StartProfiling(const char* title, unsigned uid) {
   ASSERT(uid > 0);
   current_profiles_semaphore_->Wait();
   for (int i = 0; i < current_profiles_.length(); ++i) {
     if (strcmp(current_profiles_[i]->title(), title) == 0) {
       // Ignore attempts to start profile with the same title.
       current_profiles_semaphore_->Signal();
       return false;
     }
   }
   current_profiles_.Add(new CpuProfile(title, uid));
   current_profiles_semaphore_->Signal();
   return true;
 }


 bool CpuProfilesCollection::StartProfiling(String* title, unsigned uid) {
   return StartProfiling(GetName(title), uid);
 }


 CpuProfile* CpuProfilesCollection::StopProfiling(const char* title,
                                                  double actual_sampling_rate) {
   const int title_len = StrLength(title);
   CpuProfile* profile = NULL;
   current_profiles_semaphore_->Wait();
   for (int i = current_profiles_.length() - 1; i >= 0; --i) {
     if (title_len == 0 || strcmp(current_profiles_[i]->title(), title) == 0) {
       profile = current_profiles_.Remove(i);
       break;
     }
   }
   current_profiles_semaphore_->Signal();

   if (profile != NULL) {
     profile->CalculateTotalTicks();
     profile->SetActualSamplingRate(actual_sampling_rate);
     profiles_.Add(profile);
     HashMap::Entry* entry =
         profiles_uids_.Lookup(reinterpret_cast<void*>(profile->uid()),
                               static_cast<uint32_t>(profile->uid()),
                               true);
     ASSERT(entry->value == NULL);
     entry->value = profile;
   }
   return profile;
 }


 CpuProfile* CpuProfilesCollection::StopProfiling(String* title,
                                                  double actual_sampling_rate) {
   return StopProfiling(GetName(title), actual_sampling_rate);
 }


 CpuProfile* CpuProfilesCollection::GetProfile(unsigned uid) {
   HashMap::Entry* entry = profiles_uids_.Lookup(reinterpret_cast<void*>(uid),
                                                 static_cast<uint32_t>(uid),
                                                 false);
   return entry != NULL ? reinterpret_cast<CpuProfile*>(entry->value) : NULL;
 }


 CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
                                                String* name,
                                                String* resource_name,
                                                int line_number) {
   CodeEntry* entry = new CodeEntry(tag,
                                    CodeEntry::kEmptyNamePrefix,
                                    GetFunctionName(name),
                                    GetName(resource_name),
                                    line_number);
   code_entries_.Add(entry);
   return entry;
 }


 CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
                                                const char* name) {
   CodeEntry* entry = new CodeEntry(tag,
                                    CodeEntry::kEmptyNamePrefix,
                                    GetFunctionName(name),
                                    "",
                                    v8::CpuProfileNode::kNoLineNumberInfo);
   code_entries_.Add(entry);
   return entry;
 }


 CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
                                                const char* name_prefix,
                                                String* name) {
   CodeEntry* entry = new CodeEntry(tag,
                                    name_prefix,
                                    GetName(name),
                                    "",
                                    v8::CpuProfileNode::kNoLineNumberInfo);
   code_entries_.Add(entry);
   return entry;
 }


 CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
                                                int args_count) {
   CodeEntry* entry = new CodeEntry(tag,
                                    "args_count: ",
                                    GetName(args_count),
                                    "",
                                    v8::CpuProfileNode::kNoLineNumberInfo);
   code_entries_.Add(entry);
   return entry;
 }


 const char* CpuProfilesCollection::GetName(String* name) {
   if (name->IsString()) {
     char* c_name =
         name->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL).Detach();
     HashMap::Entry* cache_entry =
         function_and_resource_names_.Lookup(c_name,
                                             name->Hash(),
                                             true);
     if (cache_entry->value == NULL) {
       // New entry added.
       cache_entry->value = c_name;
     } else {
       DeleteArray(c_name);
     }
     return reinterpret_cast<const char*>(cache_entry->value);
   } else {
     return "";
   }
 }


 const char* CpuProfilesCollection::GetName(int args_count) {
   ASSERT(args_count >= 0);
   if (args_count_names_.length() <= args_count) {
     args_count_names_.AddBlock(
         NULL, args_count - args_count_names_.length() + 1);
   }
   if (args_count_names_[args_count] == NULL) {
     const int kMaximumNameLength = 32;
     char* name = NewArray<char>(kMaximumNameLength);
     OS::SNPrintF(Vector<char>(name, kMaximumNameLength), "%d", args_count);
     args_count_names_[args_count] = name;
   }
   return args_count_names_[args_count];
 }


 void CpuProfilesCollection::AddPathToCurrentProfiles(
     const Vector<CodeEntry*>& path) {
   // As starting / stopping profiles is rare relatively to this
   // method, we don't bother minimizing the duration of lock holding,
   // e.g. copying contents of the list to a local vector.
   current_profiles_semaphore_->Wait();
   for (int i = 0; i < current_profiles_.length(); ++i) {
     current_profiles_[i]->AddPath(path);
   }
   current_profiles_semaphore_->Signal();
 }


 void SampleRateCalculator::Tick() {
   if (--wall_time_query_countdown_ == 0)
     UpdateMeasurements(OS::TimeCurrentMillis());
 }


 void SampleRateCalculator::UpdateMeasurements(double current_time) {
   if (measurements_count_++ != 0) {
     const double measured_ticks_per_ms =
         (kWallTimeQueryIntervalMs * ticks_per_ms_) /
         (current_time - last_wall_time_);
     // Update the average value.
     ticks_per_ms_ +=
         (measured_ticks_per_ms - ticks_per_ms_) / measurements_count_;
     // Update the externally accessible result.
     result_ = static_cast<AtomicWord>(ticks_per_ms_ * kResultScale);
   }
   last_wall_time_ = current_time;
   wall_time_query_countdown_ =
       static_cast<unsigned>(kWallTimeQueryIntervalMs * ticks_per_ms_);
 }


 const char* ProfileGenerator::kAnonymousFunctionName = "(anonymous function)";
 const char* ProfileGenerator::kProgramEntryName = "(program)";
 const char* ProfileGenerator::kGarbageCollectorEntryName =
   "(garbage collector)";


 ProfileGenerator::ProfileGenerator(CpuProfilesCollection* profiles)
     : profiles_(profiles),
       program_entry_(
           profiles->NewCodeEntry(Logger::FUNCTION_TAG, kProgramEntryName)),
       gc_entry_(
           profiles->NewCodeEntry(Logger::BUILTIN_TAG,
                                  kGarbageCollectorEntryName)) {
 }


 void ProfileGenerator::RecordTickSample(const TickSample& sample) {
   // Allocate space for stack frames + pc + function + vm-state.
   ScopedVector<CodeEntry*> entries(sample.frames_count + 3);
   // As actual number of decoded code entries may vary, initialize
   // entries vector with NULL values.
   CodeEntry** entry = entries.start();
   memset(entry, 0, entries.length() * sizeof(*entry));
   if (sample.pc != NULL) {
     *entry++ = code_map_.FindEntry(sample.pc);

     if (sample.function != NULL) {
       *entry = code_map_.FindEntry(sample.function);
       if (*entry != NULL && !(*entry)->is_js_function()) {
         *entry = NULL;
       } else {
         CodeEntry* pc_entry = *entries.start();
         if (pc_entry == NULL || pc_entry->is_js_function())
           *entry = NULL;
       }
       entry++;
     }

     for (const Address *stack_pos = sample.stack,
            *stack_end = stack_pos + sample.frames_count;
          stack_pos != stack_end;
          ++stack_pos) {
       *entry++ = code_map_.FindEntry(*stack_pos);
     }
   }

   if (FLAG_prof_browser_mode) {
     bool no_symbolized_entries = true;
     for (CodeEntry** e = entries.start(); e != entry; ++e) {
       if (*e != NULL) {
         no_symbolized_entries = false;
         break;
       }
     }
     // If no frames were symbolized, put the VM state entry in.
     if (no_symbolized_entries) {
       *entry++ = EntryForVMState(sample.state);
     }
   }

   profiles_->AddPathToCurrentProfiles(entries);
 }

 } }  // namespace v8::internal

 #endif  // ENABLE_LOGGING_AND_PROFILING
	// Copyright 2010 the V8 project authors. All rights reserved.
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are
	// met:
	//
	// * Redistributions of source code must retain the above copyright
	// notice, this list of conditions and the following disclaimer.
	// * Redistributions in binary form must reproduce the above
	// copyright notice, this list of conditions and the following
	// disclaimer in the documentation and/or other materials provided
	// with the distribution.
	// * Neither the name of Google Inc. nor the names of its
	// contributors may be used to endorse or promote products derived
	// from this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	#ifdef ENABLE_LOGGING_AND_PROFILING

	#include "v8.h"

	#include "profile-generator-inl.h"

	#include "../include/v8-profiler.h"

	namespace v8 {
	namespace internal {


	const char* CodeEntry::kEmptyNamePrefix = "";
	unsigned CodeEntry::next_call_uid_ = 1;


	ProfileNode* ProfileNode::FindChild(CodeEntry* entry) {
	HashMap::Entry* map_entry =
	children_.Lookup(entry, CodeEntryHash(entry), false);
	return map_entry != NULL ?
	reinterpret_cast<ProfileNode*>(map_entry->value) : NULL;
	}


	ProfileNode* ProfileNode::FindOrAddChild(CodeEntry* entry) {
	HashMap::Entry* map_entry =
	children_.Lookup(entry, CodeEntryHash(entry), true);
	if (map_entry->value == NULL) {
	// New node added.
	ProfileNode* new_node = new ProfileNode(tree_, entry);
	map_entry->value = new_node;
	children_list_.Add(new_node);
	}
	return reinterpret_cast<ProfileNode*>(map_entry->value);
	}


	double ProfileNode::GetSelfMillis() const {
	return tree_->TicksToMillis(self_ticks_);
	}


	double ProfileNode::GetTotalMillis() const {
	return tree_->TicksToMillis(total_ticks_);
	}


	void ProfileNode::Print(int indent) {
	OS::Print("%5u %5u %*c %s%s",
	total_ticks_, self_ticks_,
	indent, ' ',
	entry_->name_prefix(),
	entry_->name());
	if (entry_->resource_name()[0] != '\0')
	OS::Print(" %s:%d", entry_->resource_name(), entry_->line_number());
	OS::Print("\n");
	for (HashMap::Entry* p = children_.Start();
	p != NULL;
	p = children_.Next(p)) {
	reinterpret_cast<ProfileNode*>(p->value)->Print(indent + 2);
	}
	}


	namespace {

	class DeleteNodesCallback {
	public:
	void AfterAllChildrenTraversed(ProfileNode* node) {
	delete node;
	}

	void AfterChildTraversed(ProfileNode, ProfileNode) { }
	};

	} // namespace


	ProfileTree::ProfileTree()
	: root_entry_(Logger::FUNCTION_TAG, "", "(root)", "", 0),
	root_(new ProfileNode(this, &root_entry_)) {
	}


	ProfileTree::~ProfileTree() {
	DeleteNodesCallback cb;
	TraverseDepthFirstPostOrder(&cb);
	}


	void ProfileTree::AddPathFromEnd(const Vector<CodeEntry*>& path) {
	ProfileNode* node = root_;
	for (CodeEntry** entry = path.start() + path.length() - 1;
	entry != path.start() - 1;
	--entry) {
	if (*entry != NULL) {
	node = node->FindOrAddChild(*entry);
	}
	}
	node->IncrementSelfTicks();
	}


	void ProfileTree::AddPathFromStart(const Vector<CodeEntry*>& path) {
	ProfileNode* node = root_;
	for (CodeEntry** entry = path.start();
	entry != path.start() + path.length();
	++entry) {
	if (*entry != NULL) {
	node = node->FindOrAddChild(*entry);
	}
	}
	node->IncrementSelfTicks();
	}


	void ProfileTree::SetTickRatePerMs(double ticks_per_ms) {
	ms_to_ticks_scale_ = ticks_per_ms > 0 ? 1.0 / ticks_per_ms : 1.0;
	}


	namespace {

	class Position {
	public:
	explicit Position(ProfileNode* node)
	: node(node), child_idx_(0) { }
	INLINE(ProfileNode* current_child()) {
	return node->children()->at(child_idx_);
	}
	INLINE(bool has_current_child()) {
	return child_idx_ < node->children()->length();
	}
	INLINE(void next_child()) { ++child_idx_; }

	ProfileNode* node;
	private:
	int child_idx_;
	};

	} // namespace


	// Non-recursive implementation of a depth-first post-order tree traversal.
	template <typename Callback>
	void ProfileTree::TraverseDepthFirstPostOrder(Callback* callback) {
	List<Position> stack(10);
	stack.Add(Position(root_));
	do {
	Position& current = stack.last();
	if (current.has_current_child()) {
	stack.Add(Position(current.current_child()));
	} else {
	callback->AfterAllChildrenTraversed(current.node);
	if (stack.length() > 1) {
	Position& parent = stack[stack.length() - 2];
	callback->AfterChildTraversed(parent.node, current.node);
	parent.next_child();
	// Remove child from the stack.
	stack.RemoveLast();
	}
	}
	} while (stack.length() > 1 \|\| stack.last().has_current_child());
	}


	namespace {

	class CalculateTotalTicksCallback {
	public:
	void AfterAllChildrenTraversed(ProfileNode* node) {
	node->IncreaseTotalTicks(node->self_ticks());
	}

	void AfterChildTraversed(ProfileNode* parent, ProfileNode* child) {
	parent->IncreaseTotalTicks(child->total_ticks());
	}
	};

	} // namespace


	void ProfileTree::CalculateTotalTicks() {
	CalculateTotalTicksCallback cb;
	TraverseDepthFirstPostOrder(&cb);
	}


	void ProfileTree::ShortPrint() {
	OS::Print("root: %u %u %.2fms %.2fms\n",
	root_->total_ticks(), root_->self_ticks(),
	root_->GetTotalMillis(), root_->GetSelfMillis());
	}


	void CpuProfile::AddPath(const Vector<CodeEntry*>& path) {
	top_down_.AddPathFromEnd(path);
	bottom_up_.AddPathFromStart(path);
	}


	void CpuProfile::CalculateTotalTicks() {
	top_down_.CalculateTotalTicks();
	bottom_up_.CalculateTotalTicks();
	}


	void CpuProfile::SetActualSamplingRate(double actual_sampling_rate) {
	top_down_.SetTickRatePerMs(actual_sampling_rate);
	bottom_up_.SetTickRatePerMs(actual_sampling_rate);
	}


	void CpuProfile::ShortPrint() {
	OS::Print("top down ");
	top_down_.ShortPrint();
	OS::Print("bottom up ");
	bottom_up_.ShortPrint();
	}


	void CpuProfile::Print() {
	OS::Print("[Top down]:\n");
	top_down_.Print();
	OS::Print("[Bottom up]:\n");
	bottom_up_.Print();
	}


	const CodeMap::CodeTreeConfig::Key CodeMap::CodeTreeConfig::kNoKey = NULL;
	const CodeMap::CodeTreeConfig::Value CodeMap::CodeTreeConfig::kNoValue =
	CodeMap::CodeEntryInfo(NULL, 0);


	void CodeMap::AddAlias(Address alias, Address addr) {
	CodeTree::Locator locator;
	if (tree_.Find(addr, &locator)) {
	const CodeEntryInfo& entry_info = locator.value();
	tree_.Insert(alias, &locator);
	locator.set_value(entry_info);
	}
	}


	CodeEntry* CodeMap::FindEntry(Address addr) {
	CodeTree::Locator locator;
	if (tree_.FindGreatestLessThan(addr, &locator)) {
	// locator.key() <= addr. Need to check that addr is within entry.
	const CodeEntryInfo& entry = locator.value();
	if (addr < (locator.key() + entry.size))
	return entry.entry;
	}
	return NULL;
	}


	void CodeMap::CodeTreePrinter::Call(
	const Address& key, const CodeMap::CodeEntryInfo& value) {
	OS::Print("%p %5d %s\n", key, value.size, value.entry->name());
	}


	void CodeMap::Print() {
	CodeTreePrinter printer;
	tree_.ForEach(&printer);
	}


	CpuProfilesCollection::CpuProfilesCollection()
	: function_and_resource_names_(StringsMatch),
	profiles_uids_(CpuProfilesMatch),
	current_profiles_semaphore_(OS::CreateSemaphore(1)) {
	}


	static void DeleteArgsCountName(char** name_ptr) {
	DeleteArray(*name_ptr);
	}


	static void DeleteCodeEntry(CodeEntry** entry_ptr) {
	delete *entry_ptr;
	}

	static void DeleteCpuProfile(CpuProfile** profile_ptr) {
	delete *profile_ptr;
	}


	CpuProfilesCollection::~CpuProfilesCollection() {
	delete current_profiles_semaphore_;
	current_profiles_.Iterate(DeleteCpuProfile);
	profiles_.Iterate(DeleteCpuProfile);
	code_entries_.Iterate(DeleteCodeEntry);
	args_count_names_.Iterate(DeleteArgsCountName);
	for (HashMap::Entry* p = function_and_resource_names_.Start();
	p != NULL;
	p = function_and_resource_names_.Next(p)) {
	DeleteArray(reinterpret_cast<const char*>(p->value));
	}
	}


	bool CpuProfilesCollection::StartProfiling(const char* title, unsigned uid) {
	ASSERT(uid > 0);
	current_profiles_semaphore_->Wait();
	for (int i = 0; i < current_profiles_.length(); ++i) {
	if (strcmp(current_profiles_[i]->title(), title) == 0) {
	// Ignore attempts to start profile with the same title.
	current_profiles_semaphore_->Signal();
	return false;
	}
	}
	current_profiles_.Add(new CpuProfile(title, uid));
	current_profiles_semaphore_->Signal();
	return true;
	}


	bool CpuProfilesCollection::StartProfiling(String* title, unsigned uid) {
	return StartProfiling(GetName(title), uid);
	}


	CpuProfile* CpuProfilesCollection::StopProfiling(const char* title,
	double actual_sampling_rate) {
	const int title_len = StrLength(title);
	CpuProfile* profile = NULL;
	current_profiles_semaphore_->Wait();
	for (int i = current_profiles_.length() - 1; i >= 0; --i) {
	if (title_len == 0 \|\| strcmp(current_profiles_[i]->title(), title) == 0) {
	profile = current_profiles_.Remove(i);
	break;
	}
	}
	current_profiles_semaphore_->Signal();

	if (profile != NULL) {
	profile->CalculateTotalTicks();
	profile->SetActualSamplingRate(actual_sampling_rate);
	profiles_.Add(profile);
	HashMap::Entry* entry =
	profiles_uids_.Lookup(reinterpret_cast<void*>(profile->uid()),
	static_cast<uint32_t>(profile->uid()),
	true);
	ASSERT(entry->value == NULL);
	entry->value = profile;
	}
	return profile;
	}


	CpuProfile* CpuProfilesCollection::StopProfiling(String* title,
	double actual_sampling_rate) {
	return StopProfiling(GetName(title), actual_sampling_rate);
	}


	CpuProfile* CpuProfilesCollection::GetProfile(unsigned uid) {
	HashMap::Entry* entry = profiles_uids_.Lookup(reinterpret_cast<void*>(uid),
	static_cast<uint32_t>(uid),
	false);
	return entry != NULL ? reinterpret_cast<CpuProfile*>(entry->value) : NULL;
	}


	CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
	String* name,
	String* resource_name,
	int line_number) {
	CodeEntry* entry = new CodeEntry(tag,
	CodeEntry::kEmptyNamePrefix,
	GetFunctionName(name),
	GetName(resource_name),
	line_number);
	code_entries_.Add(entry);
	return entry;
	}


	CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
	const char* name) {
	CodeEntry* entry = new CodeEntry(tag,
	CodeEntry::kEmptyNamePrefix,
	GetFunctionName(name),
	"",
	v8::CpuProfileNode::kNoLineNumberInfo);
	code_entries_.Add(entry);
	return entry;
	}


	CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
	const char* name_prefix,
	String* name) {
	CodeEntry* entry = new CodeEntry(tag,
	name_prefix,
	GetName(name),
	"",
	v8::CpuProfileNode::kNoLineNumberInfo);
	code_entries_.Add(entry);
	return entry;
	}


	CodeEntry* CpuProfilesCollection::NewCodeEntry(Logger::LogEventsAndTags tag,
	int args_count) {
	CodeEntry* entry = new CodeEntry(tag,
	"args_count: ",
	GetName(args_count),
	"",
	v8::CpuProfileNode::kNoLineNumberInfo);
	code_entries_.Add(entry);
	return entry;
	}


	const char* CpuProfilesCollection::GetName(String* name) {
	if (name->IsString()) {
	char* c_name =
	name->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL).Detach();
	HashMap::Entry* cache_entry =
	function_and_resource_names_.Lookup(c_name,
	name->Hash(),
	true);
	if (cache_entry->value == NULL) {
	// New entry added.
	cache_entry->value = c_name;
	} else {
	DeleteArray(c_name);
	}
	return reinterpret_cast<const char*>(cache_entry->value);
	} else {
	return "";
	}
	}


	const char* CpuProfilesCollection::GetName(int args_count) {
	ASSERT(args_count >= 0);
	if (args_count_names_.length() <= args_count) {
	args_count_names_.AddBlock(
	NULL, args_count - args_count_names_.length() + 1);
	}
	if (args_count_names_[args_count] == NULL) {
	const int kMaximumNameLength = 32;
	char* name = NewArray<char>(kMaximumNameLength);
	OS::SNPrintF(Vector<char>(name, kMaximumNameLength), "%d", args_count);
	args_count_names_[args_count] = name;
	}
	return args_count_names_[args_count];
	}


	void CpuProfilesCollection::AddPathToCurrentProfiles(
	const Vector<CodeEntry*>& path) {
	// As starting / stopping profiles is rare relatively to this
	// method, we don't bother minimizing the duration of lock holding,
	// e.g. copying contents of the list to a local vector.
	current_profiles_semaphore_->Wait();
	for (int i = 0; i < current_profiles_.length(); ++i) {
	current_profiles_[i]->AddPath(path);
	}
	current_profiles_semaphore_->Signal();
	}


	void SampleRateCalculator::Tick() {
	if (--wall_time_query_countdown_ == 0)
	UpdateMeasurements(OS::TimeCurrentMillis());
	}


	void SampleRateCalculator::UpdateMeasurements(double current_time) {
	if (measurements_count_++ != 0) {
	const double measured_ticks_per_ms =
	(kWallTimeQueryIntervalMs * ticks_per_ms_) /
	(current_time - last_wall_time_);
	// Update the average value.
	ticks_per_ms_ +=
	(measured_ticks_per_ms - ticks_per_ms_) / measurements_count_;
	// Update the externally accessible result.
	result_ = static_cast<AtomicWord>(ticks_per_ms_ * kResultScale);
	}
	last_wall_time_ = current_time;
	wall_time_query_countdown_ =
	static_cast<unsigned>(kWallTimeQueryIntervalMs * ticks_per_ms_);
	}


	const char* ProfileGenerator::kAnonymousFunctionName = "(anonymous function)";
	const char* ProfileGenerator::kProgramEntryName = "(program)";
	const char* ProfileGenerator::kGarbageCollectorEntryName =
	"(garbage collector)";


	ProfileGenerator::ProfileGenerator(CpuProfilesCollection* profiles)
	: profiles_(profiles),
	program_entry_(
	profiles->NewCodeEntry(Logger::FUNCTION_TAG, kProgramEntryName)),
	gc_entry_(
	profiles->NewCodeEntry(Logger::BUILTIN_TAG,
	kGarbageCollectorEntryName)) {
	}


	void ProfileGenerator::RecordTickSample(const TickSample& sample) {
	// Allocate space for stack frames + pc + function + vm-state.
	ScopedVector<CodeEntry*> entries(sample.frames_count + 3);
	// As actual number of decoded code entries may vary, initialize
	// entries vector with NULL values.
	CodeEntry** entry = entries.start();
	memset(entry, 0, entries.length() * sizeof(*entry));
	if (sample.pc != NULL) {
	*entry++ = code_map_.FindEntry(sample.pc);

	if (sample.function != NULL) {
	*entry = code_map_.FindEntry(sample.function);
	if (entry != NULL && !(entry)->is_js_function()) {
	*entry = NULL;
	} else {
	CodeEntry* pc_entry = *entries.start();
	if (pc_entry == NULL \|\| pc_entry->is_js_function())
	*entry = NULL;
	}
	entry++;
	}

	for (const Address *stack_pos = sample.stack,
	*stack_end = stack_pos + sample.frames_count;
	stack_pos != stack_end;
	++stack_pos) {
	entry++ = code_map_.FindEntry(stack_pos);
	}
	}

	if (FLAG_prof_browser_mode) {
	bool no_symbolized_entries = true;
	for (CodeEntry** e = entries.start(); e != entry; ++e) {
	if (*e != NULL) {
	no_symbolized_entries = false;
	break;
	}
	}
	// If no frames were symbolized, put the VM state entry in.
	if (no_symbolized_entries) {
	*entry++ = EntryForVMState(sample.state);
	}
	}

	profiles_->AddPathToCurrentProfiles(entries);
	}

	} } // namespace v8::internal

	#endif // ENABLE_LOGGING_AND_PROFILING