1#!/usr/bin/env python3
2#
3# Copyright (C) 2019 The Android Open Source Project
4# All rights reserved.
5#
6# Redistribution and use in source and binary forms, with or without
7# modification, are permitted provided that the following conditions
8# are met:
9#  * Redistributions of source code must retain the above copyright
10#    notice, this list of conditions and the following disclaimer.
11#  * Redistributions in binary form must reproduce the above copyright
12#    notice, this list of conditions and the following disclaimer in
13#    the documentation and/or other materials provided with the
14#    distribution.
15#
16# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20# COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
22# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
23# OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27# SUCH DAMAGE.
28
29# Generate a benchmark using a JSON dump of ELF file symbols and relocations.
30
31import argparse
32import codecs
33import json
34import math
35import os
36import re
37import shlex
38import shutil
39import subprocess
40import sys
41import tempfile
42import textwrap
43import typing
44from enum import Enum
45from typing import Dict, List, Optional, Set
46from subprocess import PIPE, DEVNULL
47from pathlib import Path
48
49from common_types import LoadedLibrary, SymbolRef, SymKind, bfs_walk, json_to_elf_tree
50
51
52g_obfuscate = True
53g_benchmark_name = 'linker_reloc_bench'
54
55
56kBionicSonames: Set[str] = set([
57    'libc.so',
58    'libdl.so',
59    'libdl_android.so',
60    'libm.so',
61    'ld-android.so',
62])
63
64# Skip these symbols so the benchmark runs on multiple C libraries (glibc, Bionic, musl).
65kBionicIgnoredSymbols: Set[str] = set([
66    '__FD_ISSET_chk',
67    '__FD_SET_chk',
68    '__assert',
69    '__assert2',
70    '__b64_ntop',
71    '__cmsg_nxthdr',
72    '__cxa_thread_atexit_impl',
73    '__errno',
74    '__gnu_basename',
75    '__gnu_strerror_r',
76    '__memcpy_chk',
77    '__memmove_chk',
78    '__memset_chk',
79    '__open_2',
80    '__openat_2',
81    '__pread64_chk',
82    '__pread_chk',
83    '__read_chk',
84    '__readlink_chk',
85    '__register_atfork',
86    '__sF',
87    '__strcat_chk',
88    '__strchr_chk',
89    '__strcpy_chk',
90    '__strlcat_chk',
91    '__strlcpy_chk',
92    '__strlen_chk',
93    '__strncat_chk',
94    '__strncpy_chk',
95    '__strncpy_chk2',
96    '__strrchr_chk',
97    '__system_property_area_serial',
98    '__system_property_find',
99    '__system_property_foreach',
100    '__system_property_get',
101    '__system_property_read',
102    '__system_property_serial',
103    '__system_property_set',
104    '__umask_chk',
105    '__vsnprintf_chk',
106    '__vsprintf_chk',
107    'android_dlopen_ext',
108    'android_set_abort_message',
109    'arc4random_buf',
110    'dl_unwind_find_exidx',
111    'fts_close',
112    'fts_open',
113    'fts_read',
114    'fts_set',
115    'getprogname',
116    'gettid',
117    'isnanf',
118    'mallinfo',
119    'malloc_info',
120    'pthread_gettid_np',
121    'res_mkquery',
122    'strlcpy',
123    'strtoll_l',
124    'strtoull_l',
125    'tgkill',
126])
127
128
129Definitions = Dict[str, LoadedLibrary]
130
131def build_symbol_index(lib: LoadedLibrary) -> Definitions:
132    defs: Dict[str, LoadedLibrary] = {}
133    for lib in bfs_walk(lib):
134        for sym in lib.syms.values():
135            if not sym.defined: continue
136            defs.setdefault(sym.name, lib)
137    return defs
138
139
140def check_rels(root: LoadedLibrary, defs: Definitions) -> None:
141    # Find every symbol for every relocation in the load group.
142    has_missing = False
143    for lib in bfs_walk(root):
144        rels = lib.rels
145        for sym in rels.got + rels.jump_slots + [sym for off, sym in rels.symbolic]:
146            if sym.name not in defs:
147                if sym.is_weak:
148                    pass # print('info: weak undefined', lib.soname, r)
149                else:
150                    print(f'error: {lib.soname}: unresolved relocation to {sym.name}')
151                    has_missing = True
152    if has_missing: sys.exit('error: had unresolved relocations')
153
154
155# Obscure names to avoid polluting Android code search.
156def rot13(text: str) -> str:
157    if g_obfuscate:
158        result = codecs.getencoder("rot-13")(text)[0]
159        assert isinstance(result, str)
160        return result
161    else:
162        return text
163
164
165def make_asm_file(lib: LoadedLibrary, is_main: bool, out_filename: Path, map_out_filename: Path,
166                  defs: Definitions) -> bool:
167
168    def trans_sym(name: str, ver: Optional[str]) -> Optional[str]:
169        nonlocal defs
170        d = defs.get(name)
171        if d is not None and d.soname in kBionicSonames:
172            if name in kBionicIgnoredSymbols: return None
173            # Discard relocations to newer Bionic symbols, because there aren't many of them, and
174            # they would limit where the benchmark can run.
175            if ver == 'LIBC': return name
176            return None
177        return 'b_' + rot13(name)
178
179    versions: Dict[Optional[str], List[str]] = {}
180
181    with open(out_filename, 'w') as out:
182        out.write(f'// AUTO-GENERATED BY {os.path.basename(__file__)} -- do not edit manually\n')
183        out.write(f'#include "{g_benchmark_name}_asm.h"\n')
184        out.write('.data\n')
185        out.write('.p2align 4\n')
186
187        if is_main:
188            out.write('.text\n' 'MAIN\n')
189
190        for d in lib.syms.values():
191            if not d.defined: continue
192            sym = trans_sym(d.name, None)
193            if sym is None: continue
194            if d.kind == SymKind.Func:
195                out.write('.text\n'
196                          f'.globl {sym}\n'
197                          f'.type {sym},%function\n'
198                          f'{sym}:\n'
199                          'nop\n')
200            else: # SymKind.Var
201                out.write('.data\n'
202                          f'.globl {sym}\n'
203                          f'.type {sym},%object\n'
204                          f'{sym}:\n'
205                          f'.space __SIZEOF_POINTER__\n')
206            versions.setdefault(d.ver_name, []).append(sym)
207
208        out.write('.text\n')
209        for r in lib.rels.jump_slots:
210            sym = trans_sym(r.name, r.ver)
211            if sym is None: continue
212            if r.is_weak: out.write(f'.weak {sym}\n')
213            out.write(f'CALL({sym})\n')
214        out.write('.text\n')
215        for r in lib.rels.got:
216            sym = trans_sym(r.name, r.ver)
217            if sym is None: continue
218            if r.is_weak: out.write(f'.weak {sym}\n')
219            out.write(f'GOT_RELOC({sym})\n')
220
221        out.write('.data\n')
222        out.write('local_label:\n')
223
224        image = []
225        for off in lib.rels.relative:
226            image.append((off, f'DATA_WORD(local_label)\n'))
227        for off, r in lib.rels.symbolic:
228            sym = trans_sym(r.name, r.ver)
229            if sym is None: continue
230            text = f'DATA_WORD({sym})\n'
231            if r.is_weak: text += f'.weak {sym}\n'
232            image.append((off, text))
233        image.sort()
234
235        cur_off = 0
236        for off, text in image:
237            if cur_off < off:
238                out.write(f'.space (__SIZEOF_POINTER__ * {off - cur_off})\n')
239                cur_off = off
240            out.write(text)
241            cur_off += 1
242
243    has_map_file = False
244    if len(versions) > 0 and list(versions.keys()) != [None]:
245        has_map_file = True
246        with open(map_out_filename, 'w') as out:
247            if None in versions:
248                print(f'error: {out_filename} has both unversioned and versioned symbols')
249                print(versions.keys())
250                sys.exit(1)
251            for ver in sorted(versions.keys()):
252                assert ver is not None
253                out.write(f'{rot13(ver)} {{\n')
254                if len(versions[ver]) > 0:
255                    out.write('  global:\n')
256                    out.write(''.join(f'    {x};\n' for x in versions[ver]))
257                out.write(f'}};\n')
258
259    return has_map_file
260
261
262class LibNames:
263    def __init__(self, root: LoadedLibrary):
264        self._root = root
265        self._names: Dict[LoadedLibrary, str] = {}
266        all_libs = [x for x in bfs_walk(root) if x is not root and x.soname not in kBionicSonames]
267        num_digits = math.ceil(math.log10(len(all_libs) + 1))
268        if g_obfuscate:
269            self._names = {x : f'{i:0{num_digits}}' for i, x in enumerate(all_libs)}
270        else:
271            self._names = {x : re.sub(r'\.so$', '', x.soname) for x in all_libs}
272
273    def name(self, lib: LoadedLibrary) -> str:
274        if lib is self._root:
275            return f'{g_benchmark_name}_main'
276        else:
277            return f'lib{g_benchmark_name}_{self._names[lib]}'
278
279
280# Generate a ninja file directly that builds the benchmark using a C compiler driver and ninja.
281# Using a driver directly can be faster than building with Soong, and it allows testing
282# configurations that Soong can't target, like musl.
283def make_ninja_benchmark(root: LoadedLibrary, defs: Definitions, cc: str, out: Path) -> None:
284
285    lib_names = LibNames(root)
286
287    def lib_dso_name(lib: LoadedLibrary) -> str:
288        return lib_names.name(lib) + '.so'
289
290    ninja = open(out / 'build.ninja', 'w')
291    include_path = os.path.relpath(os.path.dirname(__file__) + '/../include', out)
292    common_flags = f"-Wl,-rpath-link,. -lm -I{include_path}"
293    ninja.write(textwrap.dedent(f'''\
294        rule exe
295            command = {cc} -fpie -pie $in -o $out {common_flags} $extra_args
296        rule dso
297            command = {cc} -fpic -shared $in -o $out -Wl,-soname,$out {common_flags} $extra_args
298    '''))
299
300    for lib in bfs_walk(root):
301        if lib.soname in kBionicSonames: continue
302
303        lib_base_name = lib_names.name(lib)
304        asm_name = lib_base_name + '.S'
305        map_name = lib_base_name + '.map'
306        asm_path = out / asm_name
307        map_path = out / map_name
308
309        has_map_file = make_asm_file(lib, lib is root, asm_path, map_path, defs)
310        needed = ' '.join([lib_dso_name(x) for x in lib.needed if x.soname not in kBionicSonames])
311
312        if lib is root:
313            ninja.write(f'build {lib_base_name}: exe {asm_name} {needed}\n')
314        else:
315            ninja.write(f'build {lib_dso_name(lib)}: dso {asm_name} {needed}\n')
316        if has_map_file:
317            ninja.write(f'    extra_args = -Wl,--version-script={map_name}\n')
318
319    ninja.close()
320
321    subprocess.run(['ninja', '-C', str(out), lib_names.name(root)], check=True)
322
323
324def make_soong_benchmark(root: LoadedLibrary, defs: Definitions, out: Path) -> None:
325
326    lib_names = LibNames(root)
327
328    bp = open(out / 'Android.bp', 'w')
329    bp.write(f'// AUTO-GENERATED BY {os.path.basename(__file__)} -- do not edit\n')
330
331    bp.write(f'cc_defaults {{\n')
332    bp.write(f'    name: "{g_benchmark_name}_all_libs",\n')
333    bp.write(f'    runtime_libs: [\n')
334    for lib in bfs_walk(root):
335        if lib.soname in kBionicSonames: continue
336        if lib is root: continue
337        bp.write(f'        "{lib_names.name(lib)}",\n')
338    bp.write(f'    ],\n')
339    bp.write(f'}}\n')
340
341    for lib in bfs_walk(root):
342        if lib.soname in kBionicSonames: continue
343
344        lib_base_name = lib_names.name(lib)
345        asm_name = lib_base_name + '.S'
346        map_name = lib_base_name + '.map'
347        asm_path = out / asm_name
348        map_path = out / map_name
349
350        has_map_file = make_asm_file(lib, lib is root, asm_path, map_path, defs)
351
352        if lib is root:
353            bp.write(f'cc_binary {{\n')
354            bp.write(f'    defaults: ["{g_benchmark_name}_binary"],\n')
355        else:
356            bp.write(f'cc_test_library {{\n')
357            bp.write(f'    defaults: ["{g_benchmark_name}_library"],\n')
358        bp.write(f'    name: "{lib_base_name}",\n')
359        bp.write(f'    srcs: ["{asm_name}"],\n')
360        bp.write(f'    shared_libs: [\n')
361        for need in lib.needed:
362            if need.soname in kBionicSonames: continue
363            bp.write(f'        "{lib_names.name(need)}",\n')
364        bp.write(f'    ],\n')
365        if has_map_file:
366            bp.write(f'    version_script: "{map_name}",\n')
367        bp.write('}\n')
368
369    bp.close()
370
371
372def main() -> None:
373    parser = argparse.ArgumentParser()
374    parser.add_argument('input', type=str)
375    parser.add_argument('out_dir', type=str)
376    parser.add_argument('--ninja', action='store_true',
377                        help='Generate a benchmark using a compiler and ninja rather than Soong')
378    parser.add_argument('--cc',
379                        help='For --ninja, a target-specific C clang driver and flags (e.g. "'
380                             '$NDK/toolchains/llvm/prebuilt/linux-x86_64/bin/aarch64-linux-android29-clang'
381                             ' -fuse-ld=lld")')
382
383    args = parser.parse_args()
384
385    if args.ninja:
386        if args.cc is None: sys.exit('error: --cc required with --ninja')
387
388    out = Path(args.out_dir)
389    with open(Path(args.input)) as f:
390        root = json_to_elf_tree(json.load(f))
391    defs = build_symbol_index(root)
392    check_rels(root, defs)
393
394    if out.exists(): shutil.rmtree(out)
395    os.makedirs(str(out))
396
397    if args.ninja:
398        make_ninja_benchmark(root, defs, args.cc, out)
399    else:
400        make_soong_benchmark(root, defs, out)
401
402
403if __name__ == '__main__':
404    main()
405