tools/symalyzer.py

   1 #!/usr/bin/python3
   2 #
   3 # 2019 by David Lamparter, placed in public domain
   4 #
   5 # This tool generates a report of possibly unused symbols in the build.  It's
   6 # particularly useful for libfrr to find bitrotting functions that aren't even
   7 # used anywhere anymore.
   8 #
   9 # Note that the tool can't distinguish between "a symbol is completely unused"
  10 # and "a symbol is used only in its file" since file-internal references are
  11 # invisible in nm output.  However, the compiler will warn you if a static
  12 # symbol is unused.
  13 #
  14 # This tool is only tested on Linux, it probably needs `nm` from GNU binutils
  15 # (as opposed to BSD `nm`).  Could use pyelftools instead but that's a lot of
  16 # extra work.
  17 #
  18 # This is a developer tool, please don't put it in any packages :)
  19
  20 import sys, os, subprocess
  21 import re
  22 from collections import namedtuple
  23
  24 sys.path.insert(
  25     0,
  26     os.path.join(os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "python"),
  27 )
  28
  29 from makevars import MakeVars
  30
  31 SymRowBase = namedtuple(
  32     "SymRow",
  33     [
  34         "target",
  35         "object",
  36         "name",
  37         "address",
  38         "klass",
  39         "typ",
  40         "size",
  41         "line",
  42         "section",
  43         "loc",
  44     ],
  45 )
  46
  47
  48 class SymRow(SymRowBase):
  49     """
  50     wrapper around a line of `nm` output
  51     """
  52
  53     lib_re = re.compile(r"/lib[^/]+\.(so|la)$")
  54
  55     def is_global(self):
  56         return self.klass.isupper() or self.klass in "uvw"
  57
  58     def scope(self):
  59         if self.lib_re.search(self.target) is None:
  60             return self.target
  61         # "global"
  62         return None
  63
  64     def is_export(self):
  65         """
  66         FRR-specific list of symbols which are considered "externally used"
  67
  68         e.g. hooks are by design APIs for external use, same for qobj_t_*
  69         frr_inet_ntop is here because it's used through an ELF alias to
  70         "inet_ntop()"
  71         """
  72         if self.name in ["main", "frr_inet_ntop", "_libfrr_version"]:
  73             return True
  74         if self.name.startswith("_hook_"):
  75             return True
  76         if self.name.startswith("qobj_t_"):
  77             return True
  78         return False
  79
  80
  81 class Symbols(dict):
  82     """
  83     dict of all symbols in all libs & executables
  84     """
  85
  86     from_re = re.compile(r"^Symbols from (.*?):$")
  87     lt_re = re.compile(r"^(.*/)([^/]+)\.l[oa]$")
  88
  89     def __init__(self):
  90         super().__init__()
  91
  92     class ReportSym(object):
  93         def __init__(self, sym):
  94             self.sym = sym
  95
  96         def __repr__(self):
  97             return "<%-25s %-40s [%s]>" % (
  98                 self.__class__.__name__ + ":",
  99                 self.sym.name,
 100                 self.sym.loc,
 101             )
 102
 103         def __lt__(self, other):
 104             return self.sym.name.__lt__(other.sym.name)
 105
 106     class ReportSymCouldBeStaticAlreadyLocal(ReportSym):
 107         idshort = "Z"
 108         idlong = "extrastatic"
 109         title = "symbol is local to library, but only used in its source file (make static?)"
 110
 111     class ReportSymCouldBeStatic(ReportSym):
 112         idshort = "S"
 113         idlong = "static"
 114         title = "symbol is only used in its source file (make static?)"
 115
 116     class ReportSymCouldBeLibLocal(ReportSym):
 117         idshort = "L"
 118         idlong = "liblocal"
 119         title = "symbol is only used inside of library"
 120
 121     class ReportSymModuleAPI(ReportSym):
 122         idshort = "A"
 123         idlong = "api"
 124         title = "symbol (in executable) is referenced externally from a module"
 125
 126     class Symbol(object):
 127         def __init__(self, name):
 128             super().__init__()
 129             self.name = name
 130             self.defs = {}
 131             self.refs = []
 132
 133         def process(self, row):
 134             scope = row.scope()
 135             if row.section == "*UND*":
 136                 self.refs.append(row)
 137             else:
 138                 self.defs.setdefault(scope, []).append(row)
 139
 140         def evaluate(self, out):
 141             """
 142             generate output report
 143
 144             invoked after all object files have been read in, so it can look
 145             at inter-object-file relationships
 146             """
 147             if len(self.defs) == 0:
 148                 out.extsyms.add(self.name)
 149                 return
 150
 151             for scopename, symdefs in self.defs.items():
 152                 common_defs = [
 153                     symdef for symdef in symdefs if symdef.section == "*COM*"
 154                 ]
 155                 proper_defs = [
 156                     symdef for symdef in symdefs if symdef.section != "*COM*"
 157                 ]
 158
 159                 if len(proper_defs) > 1:
 160                     print(self.name, " DUPLICATE")
 161                     print(
 162                         "\tD: %s %s"
 163                         % (scopename, "\n\t\t".join([repr(s) for s in symdefs]))
 164                     )
 165                     for syms in self.refs:
 166                         print("\tR: %s" % (syms,))
 167                     return
 168
 169                 if len(proper_defs):
 170                     primary_def = proper_defs[0]
 171                 elif len(common_defs):
 172                     # "common" = global variables without initializer;
 173                     # they can occur in multiple .o files and the linker will
 174                     # merge them into one variable/storage location.
 175                     primary_def = common_defs[0]
 176                 else:
 177                     # undefined symbol, e.g. libc
 178                     continue
 179
 180                 if scopename is not None and len(self.refs) > 0:
 181                     for ref in self.refs:
 182                         if ref.target != primary_def.target and ref.target.endswith(
 183                             ".la"
 184                         ):
 185                             outobj = out.report.setdefault(primary_def.object, [])
 186                             outobj.append(out.ReportSymModuleAPI(primary_def))
 187                             break
 188
 189                 if len(self.refs) == 0:
 190                     if primary_def.is_export():
 191                         continue
 192                     outobj = out.report.setdefault(primary_def.object, [])
 193                     if primary_def.visible:
 194                         outobj.append(out.ReportSymCouldBeStatic(primary_def))
 195                     else:
 196                         outobj.append(
 197                             out.ReportSymCouldBeStaticAlreadyLocal(primary_def)
 198                         )
 199                     continue
 200
 201                 if scopename is None and primary_def.visible:
 202                     # lib symbol
 203                     for ref in self.refs:
 204                         if ref.target != primary_def.target:
 205                             break
 206                     else:
 207                         outobj = out.report.setdefault(primary_def.object, [])
 208                         outobj.append(out.ReportSymCouldBeLibLocal(primary_def))
 209
 210     def evaluate(self):
 211         self.extsyms = set()
 212         self.report = {}
 213
 214         for sym in self.values():
 215             sym.evaluate(self)
 216
 217     def load(self, target, files):
 218         def libtoolmustdie(fn):
 219             m = self.lt_re.match(fn)
 220             if m is None:
 221                 return fn
 222             return m.group(1) + ".libs/" + m.group(2) + ".o"
 223
 224         def libtooltargetmustdie(fn):
 225             m = self.lt_re.match(fn)
 226             if m is None:
 227                 a, b = fn.rsplit("/", 1)
 228                 return "%s/.libs/%s" % (a, b)
 229             return m.group(1) + ".libs/" + m.group(2) + ".so"
 230
 231         files = list(set([libtoolmustdie(fn) for fn in files]))
 232
 233         def parse_nm_output(text):
 234             filename = None
 235             path_rel_to = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
 236
 237             for line in text.split("\n"):
 238                 if line.strip() == "":
 239                     continue
 240                 m = self.from_re.match(line)
 241                 if m is not None:
 242                     filename = m.group(1)
 243                     continue
 244                 if line.startswith("Name"):
 245                     continue
 246
 247                 items = [i.strip() for i in line.split("|")]
 248                 loc = None
 249                 if "\t" in items[-1]:
 250                     items[-1], loc = items[-1].split("\t", 1)
 251                     fn, lno = loc.rsplit(":", 1)
 252                     fn = os.path.relpath(fn, path_rel_to)
 253                     loc = "%s:%s" % (fn, lno)
 254
 255                 items[1] = int(items[1] if items[1] != "" else "0", 16)
 256                 items[4] = int(items[4] if items[4] != "" else "0", 16)
 257                 items.append(loc)
 258                 row = SymRow(target, filename, *items)
 259
 260                 if row.section == ".group" or row.name == "_GLOBAL_OFFSET_TABLE_":
 261                     continue
 262                 if not row.is_global():
 263                     continue
 264
 265                 yield row
 266
 267         visible_syms = set()
 268
 269         # the actual symbol report uses output from the individual object files
 270         # (e.g. lib/.libs/foo.o), but we also read the linked binary (e.g.
 271         # lib/.libs/libfrr.so) to determine which symbols are actually visible
 272         # in the linked result (this covers ELF "hidden"/"internal" linkage)
 273
 274         libfile = libtooltargetmustdie(target)
 275         nmlib = subprocess.Popen(
 276             ["nm", "-l", "-g", "--defined-only", "-f", "sysv", libfile],
 277             stdout=subprocess.PIPE,
 278         )
 279         out = nmlib.communicate()[0].decode("US-ASCII")
 280
 281         for row in parse_nm_output(out):
 282             visible_syms.add(row.name)
 283
 284         nm = subprocess.Popen(
 285             ["nm", "-l", "-f", "sysv"] + files, stdout=subprocess.PIPE
 286         )
 287         out = nm.communicate()[0].decode("US-ASCII")
 288
 289         for row in parse_nm_output(out):
 290             row.visible = row.name in visible_syms
 291             sym = self.setdefault(row.name, self.Symbol(row.name))
 292             sym.process(row)
 293
 294
 295 def write_html_report(syms):
 296     try:
 297         import jinja2
 298     except ImportError:
 299         sys.stderr.write("jinja2 could not be imported, not writing HTML report!\n")
 300         return
 301
 302     self_path = os.path.dirname(os.path.abspath(__file__))
 303     jenv = jinja2.Environment(loader=jinja2.FileSystemLoader(self_path))
 304     template = jenv.get_template("symalyzer.html")
 305
 306     dirgroups = {}
 307     for fn, reports in syms.report.items():
 308         dirname, filename = fn.replace(".libs/", "").rsplit("/", 1)
 309         dirgroups.setdefault(dirname, {})[fn] = reports
 310
 311     klasses = {
 312         "T": "code / plain old regular function (Text)",
 313         "D": "global variable, read-write, with nonzero initializer (Data)",
 314         "B": "global variable, read-write, with zero initializer (BSS)",
 315         "C": "global variable, read-write, with zero initializer (Common)",
 316         "R": "global variable, read-only (Rodata)",
 317     }
 318
 319     with open("symalyzer_report.html.tmp", "w") as fd:
 320         fd.write(template.render(dirgroups=dirgroups, klasses=klasses))
 321     os.rename("symalyzer_report.html.tmp", "symalyzer_report.html")
 322
 323     if not os.path.exists("jquery-3.4.1.min.js"):
 324         url = "https://code.jquery.com/jquery-3.4.1.min.js"
 325         sys.stderr.write(
 326             "trying to grab a copy of jquery from %s\nif this fails, please get it manually (the HTML output is done.)\n"
 327             % (url)
 328         )
 329         import requests
 330
 331         r = requests.get("https://code.jquery.com/jquery-3.4.1.min.js")
 332         if r.status_code != 200:
 333             sys.stderr.write(
 334                 "failed -- please download jquery-3.4.1.min.js and put it next to the HTML report\n"
 335             )
 336         else:
 337             with open("jquery-3.4.1.min.js.tmp", "w") as fd:
 338                 fd.write(r.text)
 339             os.rename("jquery-3.4.1.min.js.tmp", "jquery-3.4.1.min.js")
 340             sys.stderr.write("done.\n")
 341
 342
 343 def automake_escape(s):
 344     return s.replace(".", "_").replace("/", "_")
 345
 346
 347 if __name__ == "__main__":
 348     mv = MakeVars()
 349
 350     if not (os.path.exists("config.version") and os.path.exists("lib/.libs/libfrr.so")):
 351         sys.stderr.write(
 352             "please execute this script in the root directory of an FRR build tree\n"
 353         )
 354         sys.stderr.write("./configure && make need to have completed successfully\n")
 355         sys.exit(1)
 356
 357     amtargets = [
 358         "bin_PROGRAMS",
 359         "sbin_PROGRAMS",
 360         "lib_LTLIBRARIES",
 361         "module_LTLIBRARIES",
 362     ]
 363     targets = []
 364
 365     mv.getvars(amtargets)
 366     for amtarget in amtargets:
 367         targets.extend(
 368             [item for item in mv[amtarget].strip().split() if item != "tools/ssd"]
 369         )
 370
 371     mv.getvars(["%s_LDADD" % automake_escape(t) for t in targets])
 372     ldobjs = targets[:]
 373     for t in targets:
 374         ldadd = mv["%s_LDADD" % automake_escape(t)].strip().split()
 375         for item in ldadd:
 376             if item.startswith("-"):
 377                 continue
 378             if item.endswith(".a"):
 379                 ldobjs.append(item)
 380
 381     mv.getvars(["%s_OBJECTS" % automake_escape(o) for o in ldobjs])
 382
 383     syms = Symbols()
 384
 385     for t in targets:
 386         objs = mv["%s_OBJECTS" % automake_escape(t)].strip().split()
 387         ldadd = mv["%s_LDADD" % automake_escape(t)].strip().split()
 388         for item in ldadd:
 389             if item.startswith("-"):
 390                 continue
 391             if item.endswith(".a"):
 392                 objs.extend(mv["%s_OBJECTS" % automake_escape(item)].strip().split())
 393
 394         sys.stderr.write("processing %s...\n" % t)
 395         sys.stderr.flush()
 396         # print(t, '\n\t', objs)
 397         syms.load(t, objs)
 398
 399     syms.evaluate()
 400
 401     for obj, reports in sorted(syms.report.items()):
 402         print("%s:" % obj)
 403         for report in reports:
 404             print("\t%r" % report)
 405
 406     write_html_report(syms)