supersize: Track symbol aliases and shared symbols

tools/binary_size/libsupersize/models.py

 # Copyright 2017 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 """Classes that comprise the data model for binary size analysis.
 
 The primary classes are Symbol, and SymbolGroup.
 
 Description of common properties:
   * address: The start address of the symbol.
         May be 0 (e.g. for .bss or for SymbolGroups).
   * size: The number of bytes this symbol takes up, including padding that comes
        before |address|.
+  * num_aliases: The number of symbols with the same address (including self).
+  * pss: size / num_aliases.
   * padding: The number of bytes of padding before |address| due to this symbol.
   * name: Symbol names with parameter list removed.
         Never None, but will be '' for anonymous symbols.
   * full_name: Symbols names with parameter list left in.
        Never None, but will be '' for anonymous symbols, and for symbols that do
        not contain a parameter list.
   * is_anonymous: True when the symbol exists in an anonymous namespace (which
        are removed from both full_name and name during normalization).
   * section_name: E.g. ".text", ".rodata", ".data.rel.local"
   * section: The second character of |section_name|. E.g. "t", "r", "d".
 """
 
 import collections
-import copy
+import logging
 import os
 import re
 
 import match_util
 
 
 METADATA_GIT_REVISION = 'git_revision'
 METADATA_APK_FILENAME = 'apk_file_name'  # Path relative to output_directory.
 METADATA_MAP_FILENAME = 'map_file_name'  # Path relative to output_directory.
 METADATA_ELF_ARCHITECTURE = 'elf_arch'  # "Machine" field from readelf -h
@@ skipping 10 matching lines @@
     't': '.text',
 }
 
 FLAG_ANONYMOUS = 1
 FLAG_STARTUP = 2
 FLAG_UNLIKELY = 4
 FLAG_REL = 8
 FLAG_REL_LOCAL = 16
 
 
+def _StripCloneSuffix(name):
+  clone_idx = name.find(' [clone ')
+  if clone_idx != -1:
+    return name[:clone_idx]
+  return name
+
+
 class SizeInfo(object):
   """Represents all size information for a single binary.
 
   Fields:
     section_sizes: A dict of section_name -> size.
     raw_symbols: A flat list of all symbols.
     symbols: A SymbolGroup containing raw_symbols, but with some Symbols grouped
         into sub-SymbolGroups.
     metadata: A dict.
   """
@@ skipping 58 matching lines @@
     return self.size - self.padding
 
   @property
   def end_address(self):
     return self.address + self.size_without_padding
 
   @property
   def is_anonymous(self):
     return bool(self.flags & FLAG_ANONYMOUS)
 
+  @property
+  def num_aliases(self):
+    return len(self.aliases) if self.aliases else 1
+
   def FlagsString(self):
     # Most flags are 0.
     flags = self.flags
-    if not flags:
+    if not flags and not self.aliases:
       return '{}'
     parts = []
     if flags & FLAG_ANONYMOUS:
       parts.append('anon')
     if flags & FLAG_STARTUP:
       parts.append('startup')
     if flags & FLAG_UNLIKELY:
       parts.append('unlikely')
     if flags & FLAG_REL:
       parts.append('rel')
     if flags & FLAG_REL_LOCAL:
       parts.append('rel.loc')
+    # Not actually a part of flags, but useful to show it here.
+    if self.aliases:
+      parts.append('{} aliases'.format(self.num_aliases))
     return '{%s}' % ','.join(parts)
 
   def IsBss(self):
     return self.section_name == '.bss'
 
   def IsGroup(self):
     return False
 
   def IsGenerated(self):
     # TODO(agrieve): Also match generated functions such as:
     #     startup._GLOBAL__sub_I_page_allocator.cc
     return self.name.endswith(']') and not self.name.endswith('[]')
 
   def _Key(self):
     """Returns a tuple that can be used to see if two Symbol are the same.
 
     Keys are not guaranteed to be unique within a SymbolGroup. For example, it
     is common to have multiple "** merge strings" symbols, which will have a
     common key."""
     stripped_full_name = self.full_name
     if stripped_full_name:
-      clone_idx = stripped_full_name.find(' [clone ')
-      if clone_idx != -1:
-        stripped_full_name = stripped_full_name[:clone_idx]
+      stripped_full_name = _StripCloneSuffix(stripped_full_name)
     return (self.section_name, stripped_full_name or self.name)
 
 
 class Symbol(BaseSymbol):
   """Represents a single symbol within a binary.
 
   Refer to module docs for field descriptions.
   """
 
   __slots__ = (
       'address',
       'full_name',
       'flags',
       'object_path',
       'name',
+      'aliases',
       'padding',
       'section_name',
       'source_path',
       'size',
   )
 
   def __init__(self, section_name, size_without_padding, address=None,
                name=None, source_path=None, object_path=None, full_name=None,
-               flags=0):
+               flags=0, aliases=None):
     self.section_name = section_name
     self.address = address or 0
     self.name = name or ''
     self.full_name = full_name or ''
     self.source_path = source_path or ''
     self.object_path = object_path or ''
     self.size = size_without_padding
     self.flags = flags
+    self.aliases = aliases
     self.padding = 0
 
   def __repr__(self):
-    return ('%s@%x(size_without_padding=%d,padding=%d,name=%s,path=%s,flags=%s)'
-            % (self.section_name, self.address, self.size_without_padding,
-               self.padding, self.name, self.source_path or self.object_path,
-               self.FlagsString()))
+    template = ('{}@{:x}(size_without_padding={},padding={},name={},'
+                'object_path={},source_path={},flags={})')
+    return template.format(
+        self.section_name, self.address, self.size_without_padding,
+        self.padding, self.name, self.object_path, self.source_path,
+        self.FlagsString())
+
+  @property
+  def pss(self):
+    return float(self.size) / self.num_aliases
+
+  @property
+  def pss_without_padding(self):
+    return float(self.size_without_padding) / self.num_aliases
 
 
 class SymbolGroup(BaseSymbol):
   """Represents a group of symbols using the same interface as Symbol.
 
   SymbolGroups are immutable. All filtering / sorting will return new
   SymbolGroups objects.
 
   Overrides many __functions__. E.g. the following are all valid:
   * len(group)
   * iter(group)
   * group[0]
   * group['0x1234']  # By symbol address
   * without_group2 = group1 - group2
   * unioned = group1 + group2
   """
 
   __slots__ = (
       '_padding',
       '_size',
+      '_pss',
       '_symbols',
       '_filtered_symbols',
       'full_name',
       'name',
       'section_name',
       'is_sorted',
   )
 
   def __init__(self, symbols, filtered_symbols=None, name=None,
                full_name=None, section_name=None, is_sorted=False):
     self._padding = None
     self._size = None
+    self._pss = None
     self._symbols = symbols
     self._filtered_symbols = filtered_symbols or []
     self.name = name or ''
     self.full_name = full_name
     self.section_name = section_name or '.*'
     self.is_sorted = is_sorted
 
   def __repr__(self):
     return 'Group(name=%s,count=%d,size=%d)' % (
         self.name, len(self), self.size)
@@ skipping 39 matching lines @@
     return first if all(s.address == first for s in self._symbols) else 0
 
   @property
   def flags(self):
     first = self._symbols[0].flags
     return first if all(s.flags == first for s in self._symbols) else 0
 
   @property
   def object_path(self):
     first = self._symbols[0].object_path
-    return first if all(s.object_path == first for s in self._symbols) else None
+    return first if all(s.object_path == first for s in self._symbols) else ''
 
   @property
   def source_path(self):
     first = self._symbols[0].source_path
-    return first if all(s.source_path == first for s in self._symbols) else None
+    return first if all(s.source_path == first for s in self._symbols) else ''
+
+  def IterUniqueSymbols(self):
+    seen_aliases_lists = set()
+    for s in self:
+      if not s.aliases:
+        yield s
+      elif id(s.aliases) not in seen_aliases_lists:
+        seen_aliases_lists.add(id(s.aliases))
+        yield s
 
   @property
   def size(self):
     if self._size is None:
       if self.IsBss():
         self._size = sum(s.size for s in self)
-      self._size = sum(s.size for s in self if not s.IsBss())
+      else:
+        self._size = sum(s.size for s in self.IterUniqueSymbols())
     return self._size
 
   @property
+  def pss(self):
+    if self._pss is None:
+      if self.IsBss():
+        self._pss = self.size
+      else:
+        self._pss = sum(s.pss for s in self)
+    return self._pss
+
+  @property
   def padding(self):
     if self._padding is None:
-      self._padding = sum(s.padding for s in self)
+      self._padding = sum(s.padding for s in self.IterUniqueSymbols())
     return self._padding
 
+  @property
+  def aliases(self):
+    return None
+
   def IsGroup(self):
     return True
 
   def _CreateTransformed(self, symbols, filtered_symbols=None, name=None,
                          section_name=None, is_sorted=None):
     if is_sorted is None:
       is_sorted = self.is_sorted
     return SymbolGroup(symbols, filtered_symbols=filtered_symbols, name=name,
                        section_name=section_name, is_sorted=is_sorted)
 
@@ skipping 13 matching lines @@
 
   def SortedByAddress(self, reverse=False):
     return self.Sorted(key=(lambda s:s.address), reverse=reverse)
 
   def SortedByCount(self, reverse=False):
     return self.Sorted(key=(lambda s:len(s) if s.IsGroup() else 1),
                        reverse=not reverse)
 
   def Filter(self, func):
     filtered_and_kept = ([], [])
-    for symbol in self:
-      filtered_and_kept[int(bool(func(symbol)))].append(symbol)
+    symbol = None
+    try:
+      for symbol in self:
+        filtered_and_kept[int(bool(func(symbol)))].append(symbol)
+    except:
+      logging.warning('Filter failed on symbol %r', symbol)
+      raise
+
     return self._CreateTransformed(filtered_and_kept[1],
                                    filtered_symbols=filtered_and_kept[0],
                                    section_name=self.section_name)
 
   def WhereBiggerThan(self, min_size):
     return self.Filter(lambda s: s.size >= min_size)
 
   def WhereInSection(self, section):
     if len(section) == 1:
       ret = self.Filter(lambda s: s.section == section)
@@ skipping 237 matching lines @@
     key = id(sym)
     return key not in self._added_ids and key not in self._removed_ids
 
   def IsRemoved(self, sym):
     return id(sym) in self._removed_ids
 
   def WhereNotUnchanged(self):
     return self.Filter(lambda s: not self.IsSimilar(s) or s.size)
 
 
-def Diff(before, after):
-  """Diffs two SizeInfo or SymbolGroup objects.
-
-  When diffing SizeInfos, a SizeInfoDiff is returned.
-  When diffing SymbolGroups, a SymbolDiff is returned.
-
-  Returns:
-    Returns a SizeInfo when args are of type SizeInfo.
-    Returns a SymbolDiff when args are of type SymbolGroup.
-  """
-  if isinstance(after, SizeInfo):
-    assert isinstance(before, SizeInfo)
-    section_sizes = {k: after.section_sizes[k] - v
-                     for k, v in before.section_sizes.iteritems()}
-    symbol_diff = _DiffSymbols(before.symbols, after.symbols)
-    return SizeInfoDiff(section_sizes, symbol_diff, before.metadata,
-                        after.metadata)
-
-  assert isinstance(after, SymbolGroup) and isinstance(before, SymbolGroup)
-  return _DiffSymbols(before, after)
-
-
-def _NegateAll(symbols):
-  ret = []
-  for symbol in symbols:
-    if symbol.IsGroup():
-      duped = SymbolDiff([], _NegateAll(symbol), [], name=symbol.name,
-                         full_name=symbol.full_name,
-                         section_name=symbol.section_name)
-    else:
-      duped = copy.copy(symbol)
-      duped.size = -duped.size
-      duped.padding = -duped.padding
-    ret.append(duped)
-  return ret
-
-
-def _DiffSymbols(before, after):
-  symbols_by_key = collections.defaultdict(list)
-  for s in before:
-    symbols_by_key[s._Key()].append(s)
-
-  added = []
-  similar = []
-  # For similar symbols, padding is zeroed out. In order to not lose the
-  # information entirely, store it in aggregate.
-  padding_by_section_name = collections.defaultdict(int)
-  for after_sym in after:
-    matching_syms = symbols_by_key.get(after_sym._Key())
-    if matching_syms:
-      before_sym = matching_syms.pop(0)
-      if before_sym.IsGroup() and after_sym.IsGroup():
-        merged_sym = _DiffSymbols(before_sym, after_sym)
-      else:
-        size_diff = (after_sym.size_without_padding -
-                     before_sym.size_without_padding)
-        merged_sym = Symbol(after_sym.section_name, size_diff,
-                            address=after_sym.address, name=after_sym.name,
-                            source_path=after_sym.source_path,
-                            object_path=after_sym.object_path,
-                            full_name=after_sym.full_name,
-                            flags=after_sym.flags)
-
-        # Diffs are more stable when comparing size without padding, except when
-        # the symbol is a padding-only symbol.
-        if after_sym.size_without_padding == 0 and size_diff == 0:
-          merged_sym.padding = after_sym.padding - before_sym.padding
-        else:
-          padding_by_section_name[after_sym.section_name] += (
-              after_sym.padding - before_sym.padding)
-
-      similar.append(merged_sym)
-    else:
-      added.append(after_sym)
-
-  removed = []
-  for remaining_syms in symbols_by_key.itervalues():
-    if remaining_syms:
-      removed.extend(_NegateAll(remaining_syms))
-
-  for section_name, padding in padding_by_section_name.iteritems():
-    if padding != 0:
-      similar.append(Symbol(section_name, padding,
-                            name="** aggregate padding of diff'ed symbols"))
-  return SymbolDiff(added, removed, similar, name=after.name,
-                    full_name=after.full_name,
-                    section_name=after.section_name)
-
-
 def _ExtractPrefixBeforeSeparator(string, separator, count=1):
   idx = -len(separator)
   prev_idx = None
   for _ in xrange(count):
     idx = string.find(separator, idx + len(separator))
     if idx < 0:
       break
     prev_idx = idx
   return string[:prev_idx]