tools/symalyzer.py

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