From 0b9c43b37b152c69a4aeeb2f6dfd64367a29ef16 Mon Sep 17 00:00:00 2001 From: "ager@chromium.org" Date: Wed, 3 Sep 2008 19:15:48 +0000 Subject: [PATCH] Add the profiler tick processors to the tools directory. git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@123 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- tools/js2c.py | 1 + tools/linux-tick-processor.py | 81 ++++++++++++ tools/splaytree.py | 219 ++++++++++++++++++++++++++++++++ tools/tickprocessor.py | 204 +++++++++++++++++++++++++++++ tools/windows-tick-processor.py | 140 ++++++++++++++++++++ 5 files changed, 645 insertions(+) create mode 100755 tools/linux-tick-processor.py create mode 100644 tools/splaytree.py create mode 100644 tools/tickprocessor.py create mode 100755 tools/windows-tick-processor.py diff --git a/tools/js2c.py b/tools/js2c.py index 996fb1407..ac9c6b209 100755 --- a/tools/js2c.py +++ b/tools/js2c.py @@ -1,4 +1,5 @@ #!/usr/bin/env python +# # Copyright 2006 Google Inc. All Rights Reserved. # Redistribution and use in source and binary forms, with or without # modification, are permitted provided that the following conditions are diff --git a/tools/linux-tick-processor.py b/tools/linux-tick-processor.py new file mode 100755 index 000000000..339c96b51 --- /dev/null +++ b/tools/linux-tick-processor.py @@ -0,0 +1,81 @@ +#!/usr/bin/env python +# +# Copyright 2008 Google Inc. 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. + +# Usage: process-ticks.py +# Where is the log file name (eg, v8.log). + +import os, re, sys, tickprocessor, getopt; + +class LinuxTickProcessor(tickprocessor.TickProcessor): + + def ParseVMSymbols(self, filename, start, end): + """Extract symbols and add them to the cpp entries.""" + pipe = os.popen('nm -n %s | c++filt' % filename, 'r') + try: + for line in pipe: + row = re.match('^([0-9a-fA-F]{8}) . (.*)$', line) + if row: + addr = int(row.group(1), 16) + if addr < start and addr < end - start: + addr += start + self.cpp_entries.Insert(addr, tickprocessor.CodeEntry(addr, row.group(2))) + finally: + pipe.close() + + +def Usage(): + print("Usage: linux-tick-processor.py --{js,gc,compiler,other} logfile-name"); + sys.exit(2) + +def Main(): + # parse command line options + state = None; + try: + opts, args = getopt.getopt(sys.argv[1:], "jgco", ["js", "gc", "compiler", "other"]) + except getopt.GetoptError: + usage() + # process options. + for key, value in opts: + if key in ("-j", "--js"): + state = 0 + if key in ("-g", "--gc"): + state = 1 + if key in ("-c", "--compiler"): + state = 2 + if key in ("-o", "--other"): + state = 3 + # do the processing. + if len(args) != 1: + Usage(); + tick_processor = LinuxTickProcessor() + tick_processor.ProcessLogfile(args[0], state) + tick_processor.PrintResults() + +if __name__ == '__main__': + Main() diff --git a/tools/splaytree.py b/tools/splaytree.py new file mode 100644 index 000000000..86f52f378 --- /dev/null +++ b/tools/splaytree.py @@ -0,0 +1,219 @@ +# Copyright 2008 Google Inc. 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. + + +class Node(object): + """Nodes in the splay tree.""" + + def __init__(self, key, value): + self.key = key + self.value = value + self.left = None + self.right = None + + +class SplayTree(object): + """The splay tree itself is just a reference to the root of the tree.""" + + def __init__(self): + """Create a new SplayTree.""" + self.root = None + + def IsEmpty(self): + """Is the SplayTree empty?""" + return not self.root + + def Insert(self, key, value): + """Insert a new node in the SplayTree.""" + # If the tree is empty, insert the new node. + if self.IsEmpty(): + self.root = Node(key, value) + return + # Splay on the key to move the last node on the search path for + # the key to the root of the tree. + self.Splay(key) + # Ignore repeated insertions with the same key. + if self.root.key == key: + return + # Insert the new node. + node = Node(key, value) + if key > self.root.key: + node.left = self.root + node.right = self.root.right + self.root.right = None + else: + node.right = self.root + node.left = self.root.left + self.root.left = None + self.root = node + + def Remove(self, key): + """Remove the node with the given key from the SplayTree.""" + # Raise exception for key that is not found if the tree is empty. + if self.IsEmpty(): + raise 'KeyNotFound' + # Splay on the key to move the node with the given key to the top. + self.Splay(key) + # Raise exception for key that is not found. + if self.root.key != key: + raise 'KeyNotFound' + removed = self.root + # Link out the root node. + if not self.root.left: + # No left child, so the new tree is just the right child. + self.root = self.root.right + else: + # Left child exists. + right = self.root.right + # Make the original left child the new root. + self.root = self.root.left + # Splay to make sure that the new root has an empty right child. + self.Splay(key) + # Insert the original right child as the right child of the new + # root. + self.root.right = right + return removed + + def Find(self, key): + """Returns the node with the given key or None if no such node exists.""" + if self.IsEmpty(): + return None + self.Splay(key) + if self.root.key == key: + return self.root + return None + + def FindMax(self): + """Returns the node with the largest key value.""" + if self.IsEmpty(): + return None + current = self.root + while current.right != None: + current = current.right + return current + + # Returns the node with the smallest key value. + def FindMin(self): + if self.IsEmpty(): + return None + current = self.root + while current.left != None: + current = current.left + return current + + def FindGreatestsLessThan(self, key): + """Returns node with greatest key less than or equal to the given key.""" + if self.IsEmpty(): + return None + # Splay on the key to move the node with the given key or the last + # node on the search path to the top of the tree. + self.Splay(key) + # Now the result is either the root node or the greatest node in + # the left subtree. + if self.root.key <= key: + return self.root + else: + tmp = self.root + self.root = self.root.left + result = self.FindMax() + self.root = tmp + return result + + def ExportValueList(self): + """Returns a list containing all the values of the nodes in the tree.""" + result = [] + nodes_to_visit = [self.root] + while len(nodes_to_visit) > 0: + node = nodes_to_visit.pop() + if not node: + continue + result.append(node.value) + nodes_to_visit.append(node.left) + nodes_to_visit.append(node.right) + return result + + def Splay(self, key): + """Perform splay operation. + + Perform the splay operation for the given key. Moves the node with + the given key to the top of the tree. If no node has the given + key, the last node on the search path is moved to the top of the + tree. + + This uses the simplified top-down splaying algorithm from: + + "Self-adjusting Binary Search Trees" by Sleator and Tarjan + + """ + if self.IsEmpty(): + return + # Create a dummy node. The use of the dummy node is a bit + # counter-intuitive: The right child of the dummy node will hold + # the L tree of the algorithm. The left child of the dummy node + # will hold the R tree of the algorithm. Using a dummy node, left + # and right will always be nodes and we avoid special cases. + dummy = left = right = Node(None, None) + current = self.root + while True: + if key < current.key: + if not current.left: + break + if key < current.left.key: + # Rotate right. + tmp = current.left + current.left = tmp.right + tmp.right = current + current = tmp + if not current.left: + break + # Link right. + right.left = current + right = current + current = current.left + elif key > current.key: + if not current.right: + break + if key > current.right.key: + # Rotate left. + tmp = current.right + current.right = tmp.left + tmp.left = current + current = tmp + if not current.right: + break + # Link left. + left.right = current + left = current + current = current.right + else: + break + # Assemble. + left.right = current.left + right.left = current.right + current.left = dummy.right + current.right = dummy.left + self.root = current diff --git a/tools/tickprocessor.py b/tools/tickprocessor.py new file mode 100644 index 000000000..07dd94a75 --- /dev/null +++ b/tools/tickprocessor.py @@ -0,0 +1,204 @@ +# Copyright 2008 Google Inc. 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. + +import csv, splaytree, sys + + +class CodeEntry(object): + + def __init__(self, start_addr, name): + self.start_addr = start_addr + self.tick_count = 0 + self.name = name + + def IncrementTickCount(self): + self.tick_count += 1 + + def SetStartAddress(self, start_addr): + self.start_addr = start_addr + + def ToString(self): + return self.name + + def IsSharedLibraryEntry(self): + return False + + +class SharedLibraryEntry(CodeEntry): + + def __init__(self, start_addr, name): + CodeEntry.__init__(self, start_addr, name) + + def IsSharedLibraryEntry(self): + return True + + +class JSCodeEntry(CodeEntry): + + def __init__(self, start_addr, name, type, size): + CodeEntry.__init__(self, start_addr, name) + self.type = type + self.size = size + + def ToString(self): + return self.name + ' ' + self.type + + +class TickProcessor(object): + + def __init__(self): + self.log_file = '' + self.deleted_code = [] + self.vm_extent = {} + self.js_entries = splaytree.SplayTree() + self.cpp_entries = splaytree.SplayTree() + self.total_number_of_ticks = 0 + self.number_of_library_ticks = 0 + self.unaccounted_number_of_ticks = 0 + self.excluded_number_of_ticks = 0 + + def ProcessLogfile(self, filename, included_state = None): + self.log_file = filename + self.included_state = included_state + try: + logfile = open(filename, 'rb') + except IOError: + sys.exit("Could not open logfile: " + filename) + try: + logreader = csv.reader(logfile) + for row in logreader: + if row[0] == 'tick': + self.ProcessTick(int(row[1], 16), int(row[2], 16), int(row[3])) + elif row[0] == 'code-creation': + self.ProcessCodeCreation(row[1], int(row[2], 16), int(row[3]), row[4]) + elif row[0] == 'code-move': + self.ProcessCodeMove(int(row[1], 16), int(row[2], 16)) + elif row[0] == 'code-delete': + self.ProcessCodeDelete(int(row[1], 16)) + elif row[0] == 'shared-library': + self.AddSharedLibraryEntry(row[1], int(row[2], 16), int(row[3], 16)) + self.ParseVMSymbols(row[1], int(row[2], 16), int(row[3], 16)) + finally: + logfile.close() + + def AddSharedLibraryEntry(self, filename, start, end): + # Mark the pages used by this library. + i = start + while i < end: + page = i >> 12 + self.vm_extent[page] = 1 + i += 4096 + # Add the library to the entries so that ticks for which we do not + # have symbol information is reported as belonging to the library. + self.cpp_entries.Insert(start, SharedLibraryEntry(start, filename)) + + def ParseVMSymbols(self, filename, start, end): + return + + def ProcessCodeCreation(self, type, addr, size, name): + self.js_entries.Insert(addr, JSCodeEntry(addr, name, type, size)) + + def ProcessCodeMove(self, from_addr, to_addr): + try: + removed_node = self.js_entries.Remove(from_addr) + removed_node.value.SetStartAddress(to_addr); + self.js_entries.Insert(to_addr, removed_node.value) + except 'KeyNotFound': + print('Code move event for unknown code: 0x%x' % from_addr) + + def ProcessCodeDelete(self, from_addr): + try: + removed_node = self.js_entries.Remove(from_addr) + self.deleted_code.append(removed_node.value) + except 'KeyNotFound': + print('Code delete event for unknown code: 0x%x' % from_addr) + + def IncludeTick(self, pc, sp, state): + return (self.included_state is None) or (self.included_state == state) + + def ProcessTick(self, pc, sp, state): + if not self.IncludeTick(pc, sp, state): + self.excluded_number_of_ticks += 1; + return + self.total_number_of_ticks += 1 + page = pc >> 12 + if page in self.vm_extent: + entry = self.cpp_entries.FindGreatestsLessThan(pc).value + if entry.IsSharedLibraryEntry(): + self.number_of_library_ticks += 1 + entry.IncrementTickCount() + return + max = self.js_entries.FindMax() + min = self.js_entries.FindMin() + if max != None and pc < max.key and pc > min.key: + self.js_entries.FindGreatestsLessThan(pc).value.IncrementTickCount() + return + self.unaccounted_number_of_ticks += 1 + + def PrintResults(self): + print('Statistical profiling result from %s, (%d ticks, %d unaccounted, %d excluded).' % + (self.log_file, + self.total_number_of_ticks, + self.unaccounted_number_of_ticks, + self.excluded_number_of_ticks)) + if self.total_number_of_ticks > 0: + js_entries = self.js_entries.ExportValueList() + js_entries.extend(self.deleted_code) + cpp_entries = self.cpp_entries.ExportValueList() + # Print the library ticks. + self.PrintHeader('Shared libraries') + self.PrintEntries(cpp_entries, lambda e:e.IsSharedLibraryEntry()) + # Print the JavaScript ticks. + self.PrintHeader('JavaScript') + self.PrintEntries(js_entries, lambda e:not e.IsSharedLibraryEntry()) + # Print the C++ ticks. + self.PrintHeader('C++') + self.PrintEntries(cpp_entries, lambda e:not e.IsSharedLibraryEntry()) + + def PrintHeader(self, header_title): + print('\n [%s]:' % header_title) + print(' total nonlib name') + + def PrintEntries(self, entries, condition): + number_of_accounted_ticks = self.total_number_of_ticks - self.unaccounted_number_of_ticks + number_of_non_library_ticks = number_of_accounted_ticks - self.number_of_library_ticks + entries.sort(key=lambda e:e.tick_count, reverse=True) + for entry in entries: + if entry.tick_count > 0 and condition(entry): + total_percentage = entry.tick_count * 100.0 / number_of_accounted_ticks + if entry.IsSharedLibraryEntry(): + non_library_percentage = 0 + else: + non_library_percentage = entry.tick_count * 100.0 / number_of_non_library_ticks + print(' %(total)5.1f%% %(nonlib)6.1f%% %(name)s' % { + 'total' : total_percentage, + 'nonlib' : non_library_percentage, + 'name' : entry.ToString() + }) + +if __name__ == '__main__': + sys.exit('You probably want to run windows-tick-processor.py or linux-tick-processor.py.') diff --git a/tools/windows-tick-processor.py b/tools/windows-tick-processor.py new file mode 100755 index 000000000..447e3075b --- /dev/null +++ b/tools/windows-tick-processor.py @@ -0,0 +1,140 @@ +#!/usr/bin/env python +# +# Copyright 2008 Google Inc. 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. + + +# Usage: process-ticks.py +# +# Where is the binary program name (eg, v8_shell.exe) and +# is the log file name (eg, v8.log). +# +# This tick processor expects to find a map file for the binary named +# binary.map if the binary is named binary.exe. The tick processor +# only works for statically linked executables - no information about +# shared libraries is logged from v8 on Windows. + +import os, re, sys, tickprocessor, getopt + +class WindowsTickProcessor(tickprocessor.TickProcessor): + + def Unmangle(self, name): + """Performs very simple unmangling of C++ names. + + Does not handle arguments and template arguments. The mangled names have + the form: + + ?LookupInDescriptor@JSObject@internal@v8@@...arguments info... + + """ + # Name is mangled if it starts with a question mark. + is_mangled = re.match("^\?(.*)", name) + if is_mangled: + substrings = is_mangled.group(1).split('@') + try: + # The function name is terminated by two @s in a row. Find the + # substrings that are part of the function name. + index = substrings.index('') + substrings = substrings[0:index] + except ValueError: + # If we did not find two @s in a row, the mangled name is not in + # the format we expect and we give up. + return name + substrings.reverse() + function_name = "::".join(substrings) + return function_name + return name + + + def ParseMapFile(self, filename): + """Parse map file and add symbol information to the cpp entries.""" + # Locate map file. + has_dot = re.match('^([a-zA-F0-9_-]*)[\.]?.*$', filename) + if has_dot: + map_file_name = has_dot.group(1) + '.map' + try: + map_file = open(map_file_name, 'rb') + except IOError: + sys.exit("Could not open map file: " + map_file_name) + else: + sys.exit("Could not find map file for executable: " + filename) + try: + max_addr = 0 + min_addr = 2**30 + # Process map file and search for function entries. + row_regexp = re.compile(' 0001:[0-9a-fA-F]{8}\s*([_\?@$0-9a-zA-Z]*)\s*([0-9a-fA-F]{8}).*') + for line in map_file: + row = re.match(row_regexp, line) + if row: + addr = int(row.group(2), 16) + if addr > max_addr: + max_addr = addr + if addr < min_addr: + min_addr = addr + mangled_name = row.group(1) + name = self.Unmangle(mangled_name) + self.cpp_entries.Insert(addr, tickprocessor.CodeEntry(addr, name)); + i = min_addr + # Mark the pages for which there are functions in the map file. + while i < max_addr: + page = i >> 12 + self.vm_extent[page] = 1 + i += 4096 + finally: + map_file.close() + +def Usage(): + print("Usage: windows-tick-processor.py binary logfile-name"); + sys.exit(2) + +def Main(): + # parse command line options + state = None; + try: + opts, args = getopt.getopt(sys.argv[1:], "jgco", ["js", "gc", "compiler", "other"]) + except getopt.GetoptError: + usage() + # process options. + for key, value in opts: + if key in ("-j", "--js"): + state = 0 + if key in ("-g", "--gc"): + state = 1 + if key in ("-c", "--compiler"): + state = 2 + if key in ("-o", "--other"): + state = 3 + # do the processing. + if len(args) != 2: + Usage(); + tickprocessor = WindowsTickProcessor() + tickprocessor.ParseMapFile(args[0]) + tickprocessor.ProcessLogfile(args[1], state) + tickprocessor.PrintResults() + +if __name__ == '__main__': + Main() -- 2.34.1