1#!/usr/bin/env python3
2
3from __future__ import print_function
4
5import argparse
6import codecs
7import collections
8import copy
9import csv
10import io
11import itertools
12import json
13import os
14import posixpath
15import re
16import shutil
17import stat
18import struct
19import sys
20import zipfile
21
22
23#------------------------------------------------------------------------------
24# Python 2 and 3 Compatibility Layer
25#------------------------------------------------------------------------------
26
27if sys.version_info >= (3, 0):
28    from os import makedirs
29    from mmap import ACCESS_READ, mmap
30
31    def get_py3_bytes(buf):
32        return buf
33
34    create_chr = chr
35    enumerate_bytes = enumerate
36else:
37    from mmap import ACCESS_READ, mmap
38
39    def makedirs(path, exist_ok):
40        if exist_ok and os.path.isdir(path):
41            return
42        return os.makedirs(path)
43
44    class mmap(mmap):
45        def __enter__(self):
46            return self
47
48        def __exit__(self, exc, value, tb):
49            self.close()
50
51        def __getitem__(self, key):
52            res = super(mmap, self).__getitem__(key)
53            if type(key) == int:
54                return ord(res)
55            return res
56
57    class Py3Bytes(bytes):
58        def __getitem__(self, key):
59            res = super(Py3Bytes, self).__getitem__(key)
60            if type(key) == int:
61                return ord(res)
62            return Py3Bytes(res)
63
64    def get_py3_bytes(buf):
65        return Py3Bytes(buf)
66
67    create_chr = unichr
68
69    def enumerate_bytes(iterable):
70        for i, byte in enumerate(iterable):
71            yield (i, ord(byte))
72
73    FileNotFoundError = OSError
74
75try:
76    from sys import intern
77except ImportError:
78    pass
79
80
81#------------------------------------------------------------------------------
82# Modified UTF-8 Encoder and Decoder
83#------------------------------------------------------------------------------
84
85def encode_mutf8(input, errors='strict'):
86    i = 0
87    res = io.BytesIO()
88
89    for i, char in enumerate(input):
90        code = ord(char)
91        if code == 0x00:
92            res.write(b'\xc0\x80')
93        elif code < 0x80:
94            res.write(bytearray((code,)))
95        elif code < 0x800:
96            res.write(bytearray((0xc0 | (code >> 6), 0x80 | (code & 0x3f))))
97        elif code < 0x10000:
98            res.write(bytearray((0xe0 | (code >> 12),
99                                 0x80 | ((code >> 6) & 0x3f),
100                                 0x80 | (code & 0x3f))))
101        elif code < 0x110000:
102            code -= 0x10000
103            code_hi = 0xd800 + (code >> 10)
104            code_lo = 0xdc00 + (code & 0x3ff)
105            res.write(bytearray((0xe0 | (code_hi >> 12),
106                                 0x80 | ((code_hi >> 6) & 0x3f),
107                                 0x80 | (code_hi & 0x3f),
108                                 0xe0 | (code_lo >> 12),
109                                 0x80 | ((code_lo >> 6) & 0x3f),
110                                 0x80 | (code_lo & 0x3f))))
111        else:
112            raise UnicodeEncodeError('mutf-8', input, i, i + 1,
113                                     'illegal code point')
114
115    return (res.getvalue(), i)
116
117
118def decode_mutf8(input, errors='strict'):
119    res = io.StringIO()
120
121    num_next = 0
122
123    i = 0
124    code = 0
125    start = 0
126
127    code_surrogate = None
128    start_surrogate = None
129
130    def raise_error(start, reason):
131        raise UnicodeDecodeError('mutf-8', input, start, i + 1, reason)
132
133    for i, byte in enumerate_bytes(input):
134        if (byte & 0x80) == 0x00:
135            if num_next > 0:
136                raise_error(start, 'invalid continuation byte')
137            num_next = 0
138            code = byte
139            start = i
140        elif (byte & 0xc0) == 0x80:
141            if num_next < 1:
142                raise_error(start, 'invalid start byte')
143            num_next -= 1
144            code = (code << 6) | (byte & 0x3f)
145        elif (byte & 0xe0) == 0xc0:
146            if num_next > 0:
147                raise_error(start, 'invalid continuation byte')
148            num_next = 1
149            code = byte & 0x1f
150            start = i
151        elif (byte & 0xf0) == 0xe0:
152            if num_next > 0:
153                raise_error(start, 'invalid continuation byte')
154            num_next = 2
155            code = byte & 0x0f
156            start = i
157        else:
158            raise_error(i, 'invalid start byte')
159
160        if num_next == 0:
161            if code >= 0xd800 and code <= 0xdbff:  # High surrogate
162                if code_surrogate is not None:
163                    raise_error(start_surrogate, 'invalid high surrogate')
164                code_surrogate = code
165                start_surrogate = start
166                continue
167
168            if code >= 0xdc00 and code <= 0xdfff:  # Low surrogate
169                if code_surrogate is None:
170                    raise_error(start, 'invalid low surrogate')
171                code = ((code_surrogate & 0x3f) << 10) | (code & 0x3f) + 0x10000
172                code_surrogate = None
173                start_surrogate = None
174            elif code_surrogate is not None:
175                if errors == 'ignore':
176                    res.write(create_chr(code_surrogate))
177                    code_surrogate = None
178                    start_surrogate = None
179                else:
180                    raise_error(start_surrogate, 'illegal surrogate')
181
182            res.write(create_chr(code))
183
184    # Check the unexpected end of input
185    if num_next > 0:
186        raise_error(start, 'unexpected end')
187    if code_surrogate is not None:
188        raise_error(start_surrogate, 'unexpected end')
189
190    return (res.getvalue(), i)
191
192
193def probe_mutf8(name):
194    if name == 'mutf-8':
195        return codecs.CodecInfo(encode_mutf8, decode_mutf8)
196    return None
197
198codecs.register(probe_mutf8)
199
200
201#------------------------------------------------------------------------------
202# Collections
203#------------------------------------------------------------------------------
204
205def defaultnamedtuple(typename, field_names, default):
206    """Create a namedtuple type with default values.
207
208    This function creates a namedtuple type which will fill in default value
209    when actual arguments to the constructor were omitted.
210
211    >>> Point = defaultnamedtuple('Point', ['x', 'y'], 0)
212    >>> Point()
213    Point(x=0, y=0)
214    >>> Point(1)
215    Point(x=1, y=0)
216    >>> Point(1, 2)
217    Point(x=1, y=2)
218    >>> Point(x=1, y=2)
219    Point(x=1, y=2)
220    >>> Point(y=2, x=1)
221    Point(x=1, y=2)
222
223    >>> PermSet = defaultnamedtuple('PermSet', 'allowed disallowed', set())
224    >>> s = PermSet()
225    >>> s
226    PermSet(allowed=set(), disallowed=set())
227    >>> s.allowed is not s.disallowed
228    True
229    >>> PermSet({1})
230    PermSet(allowed={1}, disallowed=set())
231    >>> PermSet({1}, {2})
232    PermSet(allowed={1}, disallowed={2})
233    """
234
235    if isinstance(field_names, str):
236        field_names = field_names.replace(',', ' ').split()
237    field_names = list(map(str, field_names))
238    num_fields = len(field_names)
239
240    base_cls = collections.namedtuple(typename, field_names)
241    def __new__(cls, *args, **kwargs):
242        args = list(args)
243        for i in range(len(args), num_fields):
244            arg = kwargs.get(field_names[i])
245            if arg:
246                args.append(arg)
247            else:
248                args.append(copy.copy(default))
249        return base_cls.__new__(cls, *args)
250    return type(typename, (base_cls,), {'__new__': __new__})
251
252
253def create_struct(name, fields):
254    """Create a namedtuple with unpack_from() function.
255    >>> Point = create_struct('Point', [('x', 'I'), ('y', 'I')])
256    >>> pt = Point.unpack_from(b'\\x00\\x00\\x00\\x00\\x01\\x00\\x00\\x00', 0)
257    >>> pt.x
258    0
259    >>> pt.y
260    1
261    """
262    field_names = [name for name, ty in fields]
263    cls = collections.namedtuple(name, field_names)
264    cls.struct_fmt = ''.join(ty for name, ty in fields)
265    cls.struct_size = struct.calcsize(cls.struct_fmt)
266    def unpack_from(cls, buf, offset=0):
267        unpacked = struct.unpack_from(cls.struct_fmt, buf, offset)
268        return cls.__new__(cls, *unpacked)
269    cls.unpack_from = classmethod(unpack_from)
270    return cls
271
272
273#------------------------------------------------------------------------------
274# ELF Parser
275#------------------------------------------------------------------------------
276
277Elf_Hdr = collections.namedtuple(
278        'Elf_Hdr',
279        'ei_class ei_data ei_version ei_osabi e_type e_machine e_version '
280        'e_entry e_phoff e_shoff e_flags e_ehsize e_phentsize e_phnum '
281        'e_shentsize e_shnum e_shstridx')
282
283
284Elf_Shdr = collections.namedtuple(
285        'Elf_Shdr',
286        'sh_name sh_type sh_flags sh_addr sh_offset sh_size sh_link sh_info '
287        'sh_addralign sh_entsize')
288
289
290Elf_Phdr = collections.namedtuple(
291        'Elf_Phdr',
292        'p_type p_offset p_vaddr p_paddr p_filesz p_memsz p_flags p_align')
293
294
295Elf_Dyn = collections.namedtuple('Elf_Dyn', 'd_tag d_val')
296
297
298class Elf_Sym(collections.namedtuple(
299    'ELF_Sym', 'st_name st_value st_size st_info st_other st_shndx')):
300
301    STB_LOCAL = 0
302    STB_GLOBAL = 1
303    STB_WEAK = 2
304
305    SHN_UNDEF = 0
306
307    @property
308    def st_bind(self):
309        return (self.st_info >> 4)
310
311    @property
312    def is_local(self):
313        return self.st_bind == Elf_Sym.STB_LOCAL
314
315    @property
316    def is_global(self):
317        return self.st_bind == Elf_Sym.STB_GLOBAL
318
319    @property
320    def is_weak(self):
321        return self.st_bind == Elf_Sym.STB_WEAK
322
323    @property
324    def is_undef(self):
325        return self.st_shndx == Elf_Sym.SHN_UNDEF
326
327
328class ELFError(ValueError):
329    pass
330
331
332class ELF(object):
333    # ELF file format constants.
334    ELF_MAGIC = b'\x7fELF'
335
336    EI_CLASS = 4
337    EI_DATA = 5
338
339    ELFCLASSNONE = 0
340    ELFCLASS32 = 1
341    ELFCLASS64 = 2
342
343    ELFDATANONE = 0
344    ELFDATA2LSB = 1
345    ELFDATA2MSB = 2
346
347    PT_LOAD = 1
348
349    PF_X = 1
350    PF_W = 2
351    PF_R = 4
352
353    DT_NEEDED = 1
354    DT_RPATH = 15
355    DT_RUNPATH = 29
356
357    _ELF_CLASS_NAMES = {
358        ELFCLASS32: '32',
359        ELFCLASS64: '64',
360    }
361
362    _ELF_DATA_NAMES = {
363        ELFDATA2LSB: 'Little-Endian',
364        ELFDATA2MSB: 'Big-Endian',
365    }
366
367    EM_NONE = 0
368    EM_386 = 3
369    EM_MIPS = 8
370    EM_ARM = 40
371    EM_X86_64 = 62
372    EM_AARCH64 = 183
373
374    def _create_elf_machines(d):
375        elf_machine_ids = {}
376        for key, value in d.items():
377            if key.startswith('EM_'):
378                elf_machine_ids[value] = key
379        return elf_machine_ids
380
381    ELF_MACHINES = _create_elf_machines(locals())
382
383    del _create_elf_machines
384
385
386    @staticmethod
387    def _dict_find_key_by_value(d, dst):
388        for key, value in d.items():
389            if value == dst:
390                return key
391        raise KeyError(dst)
392
393    @staticmethod
394    def get_ei_class_from_name(name):
395        return ELF._dict_find_key_by_value(ELF._ELF_CLASS_NAMES, name)
396
397    @staticmethod
398    def get_ei_data_from_name(name):
399        return ELF._dict_find_key_by_value(ELF._ELF_DATA_NAMES, name)
400
401    @staticmethod
402    def get_e_machine_from_name(name):
403        return ELF._dict_find_key_by_value(ELF.ELF_MACHINES, name)
404
405
406    __slots__ = ('ei_class', 'ei_data', 'e_machine', 'dt_rpath', 'dt_runpath',
407                 'dt_needed', 'exported_symbols', 'imported_symbols',
408                 'file_size', 'ro_seg_file_size', 'ro_seg_mem_size',
409                 'rw_seg_file_size', 'rw_seg_mem_size',)
410
411
412    def __init__(self, ei_class=ELFCLASSNONE, ei_data=ELFDATANONE, e_machine=0,
413                 dt_rpath=None, dt_runpath=None, dt_needed=None,
414                 exported_symbols=None, imported_symbols=None,
415                 file_size=0, ro_seg_file_size=0, ro_seg_mem_size=0,
416                 rw_seg_file_size=0, rw_seg_mem_size=0):
417        self.ei_class = ei_class
418        self.ei_data = ei_data
419        self.e_machine = e_machine
420        self.dt_rpath = dt_rpath if dt_rpath is not None else []
421        self.dt_runpath = dt_runpath if dt_runpath is not None else []
422        self.dt_needed = dt_needed if dt_needed is not None else []
423        self.exported_symbols = \
424                exported_symbols if exported_symbols is not None else set()
425        self.imported_symbols = \
426                imported_symbols if imported_symbols is not None else set()
427        self.file_size = file_size
428        self.ro_seg_file_size = ro_seg_file_size
429        self.ro_seg_mem_size = ro_seg_mem_size
430        self.rw_seg_file_size = rw_seg_file_size
431        self.rw_seg_mem_size = rw_seg_mem_size
432
433    def __repr__(self):
434        args = (a + '=' + repr(getattr(self, a)) for a in self.__slots__)
435        return 'ELF(' + ', '.join(args) + ')'
436
437    def __eq__(self, rhs):
438        return all(getattr(self, a) == getattr(rhs, a) for a in self.__slots__)
439
440    @property
441    def elf_class_name(self):
442        return self._ELF_CLASS_NAMES.get(self.ei_class, 'None')
443
444    @property
445    def elf_data_name(self):
446        return self._ELF_DATA_NAMES.get(self.ei_data, 'None')
447
448    @property
449    def elf_machine_name(self):
450        return self.ELF_MACHINES.get(self.e_machine, str(self.e_machine))
451
452    @property
453    def is_32bit(self):
454        return self.ei_class == ELF.ELFCLASS32
455
456    @property
457    def is_64bit(self):
458        return self.ei_class == ELF.ELFCLASS64
459
460    @property
461    def sorted_exported_symbols(self):
462        return sorted(list(self.exported_symbols))
463
464    @property
465    def sorted_imported_symbols(self):
466        return sorted(list(self.imported_symbols))
467
468    def dump(self, file=None):
469        """Print parsed ELF information to the file"""
470        file = file if file is not None else sys.stdout
471
472        print('EI_CLASS\t' + self.elf_class_name, file=file)
473        print('EI_DATA\t\t' + self.elf_data_name, file=file)
474        print('E_MACHINE\t' + self.elf_machine_name, file=file)
475        print('FILE_SIZE\t' + str(self.file_size), file=file)
476        print('RO_SEG_FILE_SIZE\t' + str(self.ro_seg_file_size), file=file)
477        print('RO_SEG_MEM_SIZE\t' + str(self.ro_seg_mem_size), file=file)
478        print('RW_SEG_FILE_SIZE\t' + str(self.rw_seg_file_size), file=file)
479        print('RW_SEG_MEM_SIZE\t' + str(self.rw_seg_mem_size), file=file)
480        for dt_rpath in self.dt_rpath:
481            print('DT_RPATH\t' + dt_rpath, file=file)
482        for dt_runpath in self.dt_runpath:
483            print('DT_RUNPATH\t' + dt_runpath, file=file)
484        for dt_needed in self.dt_needed:
485            print('DT_NEEDED\t' + dt_needed, file=file)
486        for symbol in self.sorted_exported_symbols:
487            print('EXP_SYMBOL\t' + symbol, file=file)
488        for symbol in self.sorted_imported_symbols:
489            print('IMP_SYMBOL\t' + symbol, file=file)
490
491    # Extract zero-terminated buffer slice.
492    def _extract_zero_terminated_buf_slice(self, buf, offset):
493        """Extract a zero-terminated buffer slice from the given offset"""
494        end = buf.find(b'\0', offset)
495        if end == -1:
496            return buf[offset:]
497        return buf[offset:end]
498
499    # Extract c-style interned string from the buffer.
500    if sys.version_info >= (3, 0):
501        def _extract_zero_terminated_str(self, buf, offset):
502            """Extract a c-style string from the given buffer and offset"""
503            buf_slice = self._extract_zero_terminated_buf_slice(buf, offset)
504            return intern(buf_slice.decode('utf-8'))
505    else:
506        def _extract_zero_terminated_str(self, buf, offset):
507            """Extract a c-style string from the given buffer and offset"""
508            return intern(self._extract_zero_terminated_buf_slice(buf, offset))
509
510    def _parse_from_buf_internal(self, buf):
511        """Parse ELF image resides in the buffer"""
512
513        # Check ELF ident.
514        if buf.size() < 8:
515            raise ELFError('bad ident')
516
517        if buf[0:4] != ELF.ELF_MAGIC:
518            raise ELFError('bad magic')
519
520        self.ei_class = buf[ELF.EI_CLASS]
521        if self.ei_class not in (ELF.ELFCLASS32, ELF.ELFCLASS64):
522            raise ELFError('unknown word size')
523
524        self.ei_data = buf[ELF.EI_DATA]
525        if self.ei_data not in (ELF.ELFDATA2LSB, ELF.ELFDATA2MSB):
526            raise ELFError('unknown endianness')
527
528        self.file_size = buf.size()
529
530        # ELF structure definitions.
531        endian_fmt = '<' if self.ei_data == ELF.ELFDATA2LSB else '>'
532
533        if self.is_32bit:
534            elf_hdr_fmt = endian_fmt + '4x4B8xHHLLLLLHHHHHH'
535            elf_shdr_fmt = endian_fmt + 'LLLLLLLLLL'
536            elf_phdr_fmt = endian_fmt + 'LLLLLLLL'
537            elf_dyn_fmt = endian_fmt + 'lL'
538            elf_sym_fmt = endian_fmt + 'LLLBBH'
539        else:
540            elf_hdr_fmt = endian_fmt + '4x4B8xHHLQQQLHHHHHH'
541            elf_shdr_fmt = endian_fmt + 'LLQQQQLLQQ'
542            elf_phdr_fmt = endian_fmt + 'LLQQQQQQ'
543            elf_dyn_fmt = endian_fmt + 'QQ'
544            elf_sym_fmt = endian_fmt + 'LBBHQQ'
545
546        def parse_struct(cls, fmt, offset, error_msg):
547            try:
548                return cls._make(struct.unpack_from(fmt, buf, offset))
549            except struct.error:
550                raise ELFError(error_msg)
551
552        def parse_elf_hdr(offset):
553            return parse_struct(Elf_Hdr, elf_hdr_fmt, offset, 'bad elf header')
554
555        def parse_elf_shdr(offset):
556            return parse_struct(Elf_Shdr, elf_shdr_fmt, offset,
557                                'bad section header')
558
559        if self.is_32bit:
560            def parse_elf_phdr(offset):
561                return parse_struct(Elf_Phdr, elf_phdr_fmt, offset,
562                                    'bad program header')
563        else:
564            def parse_elf_phdr(offset):
565                try:
566                    p = struct.unpack_from(elf_phdr_fmt, buf, offset)
567                    return Elf_Phdr(p[0], p[2], p[3], p[4], p[5], p[6], p[1],
568                                    p[7])
569                except struct.error:
570                    raise ELFError('bad program header')
571
572        def parse_elf_dyn(offset):
573            return parse_struct(Elf_Dyn, elf_dyn_fmt, offset,
574                                'bad .dynamic entry')
575
576        if self.is_32bit:
577            def parse_elf_sym(offset):
578                return parse_struct(Elf_Sym, elf_sym_fmt, offset, 'bad elf sym')
579        else:
580            def parse_elf_sym(offset):
581                try:
582                    p = struct.unpack_from(elf_sym_fmt, buf, offset)
583                    return Elf_Sym(p[0], p[4], p[5], p[1], p[2], p[3])
584                except struct.error:
585                    raise ELFError('bad elf sym')
586
587        def extract_str(offset):
588            return self._extract_zero_terminated_str(buf, offset)
589
590        # Parse ELF header.
591        header = parse_elf_hdr(0)
592        self.e_machine = header.e_machine
593
594        # Parse ELF program header and calculate segment size.
595        if header.e_phentsize == 0:
596            raise ELFError('no program header')
597
598        ro_seg_file_size = 0
599        ro_seg_mem_size = 0
600        rw_seg_file_size = 0
601        rw_seg_mem_size = 0
602
603        assert struct.calcsize(elf_phdr_fmt) == header.e_phentsize
604        seg_end = header.e_phoff + header.e_phnum * header.e_phentsize
605        for phdr_off in range(header.e_phoff, seg_end, header.e_phentsize):
606            phdr = parse_elf_phdr(phdr_off)
607            if phdr.p_type != ELF.PT_LOAD:
608                continue
609            if phdr.p_flags & ELF.PF_W:
610                rw_seg_file_size += phdr.p_filesz
611                rw_seg_mem_size += phdr.p_memsz
612            else:
613                ro_seg_file_size += phdr.p_filesz
614                ro_seg_mem_size += phdr.p_memsz
615
616        self.ro_seg_file_size = ro_seg_file_size
617        self.ro_seg_mem_size = ro_seg_mem_size
618        self.rw_seg_file_size = rw_seg_file_size
619        self.rw_seg_mem_size = rw_seg_mem_size
620
621        # Check section header size.
622        if header.e_shentsize == 0:
623            raise ELFError('no section header')
624
625        # Find .shstrtab section.
626        shstrtab_shdr_off = \
627                header.e_shoff + header.e_shstridx * header.e_shentsize
628        shstrtab_shdr = parse_elf_shdr(shstrtab_shdr_off)
629        shstrtab_off = shstrtab_shdr.sh_offset
630
631        # Parse ELF section header.
632        sections = dict()
633        header_end = header.e_shoff + header.e_shnum * header.e_shentsize
634        for shdr_off in range(header.e_shoff, header_end, header.e_shentsize):
635            shdr = parse_elf_shdr(shdr_off)
636            name = extract_str(shstrtab_off + shdr.sh_name)
637            sections[name] = shdr
638
639        # Find .dynamic and .dynstr section header.
640        dynamic_shdr = sections.get('.dynamic')
641        if not dynamic_shdr:
642            raise ELFError('no .dynamic section')
643
644        dynstr_shdr = sections.get('.dynstr')
645        if not dynstr_shdr:
646            raise ELFError('no .dynstr section')
647
648        dynamic_off = dynamic_shdr.sh_offset
649        dynstr_off = dynstr_shdr.sh_offset
650
651        # Parse entries in .dynamic section.
652        assert struct.calcsize(elf_dyn_fmt) == dynamic_shdr.sh_entsize
653        dynamic_end = dynamic_off + dynamic_shdr.sh_size
654        for ent_off in range(dynamic_off, dynamic_end, dynamic_shdr.sh_entsize):
655            ent = parse_elf_dyn(ent_off)
656            if ent.d_tag == ELF.DT_NEEDED:
657                self.dt_needed.append(extract_str(dynstr_off + ent.d_val))
658            elif ent.d_tag == ELF.DT_RPATH:
659                self.dt_rpath.extend(
660                        extract_str(dynstr_off + ent.d_val).split(':'))
661            elif ent.d_tag == ELF.DT_RUNPATH:
662                self.dt_runpath.extend(
663                        extract_str(dynstr_off + ent.d_val).split(':'))
664
665        # Parse exported symbols in .dynsym section.
666        dynsym_shdr = sections.get('.dynsym')
667        if dynsym_shdr:
668            exp_symbols = self.exported_symbols
669            imp_symbols = self.imported_symbols
670
671            dynsym_off = dynsym_shdr.sh_offset
672            dynsym_end = dynsym_off + dynsym_shdr.sh_size
673            dynsym_entsize = dynsym_shdr.sh_entsize
674
675            # Skip first symbol entry (null symbol).
676            dynsym_off += dynsym_entsize
677
678            for ent_off in range(dynsym_off, dynsym_end, dynsym_entsize):
679                ent = parse_elf_sym(ent_off)
680                symbol_name = extract_str(dynstr_off + ent.st_name)
681                if ent.is_undef:
682                    imp_symbols.add(symbol_name)
683                elif not ent.is_local:
684                    exp_symbols.add(symbol_name)
685
686    def _parse_from_buf(self, buf):
687        """Parse ELF image resides in the buffer"""
688        try:
689            self._parse_from_buf_internal(buf)
690        except IndexError:
691            raise ELFError('bad offset')
692
693    def _parse_from_file(self, path):
694        """Parse ELF image from the file path"""
695        with open(path, 'rb') as f:
696            st = os.fstat(f.fileno())
697            if not st.st_size:
698                raise ELFError('empty file')
699            with mmap(f.fileno(), st.st_size, access=ACCESS_READ) as image:
700                self._parse_from_buf(image)
701
702    def _parse_from_dump_lines(self, path, lines):
703        patt = re.compile('^([A-Za-z_]+)\t+(.*)$')
704        for line_no, line in enumerate(lines):
705            match = patt.match(line)
706            if not match:
707                print('error: {}: {}: failed to parse'
708                        .format(path, line_no + 1), file=sys.stderr)
709                continue
710            key = match.group(1)
711            value = match.group(2)
712
713            if key == 'EI_CLASS':
714                self.ei_class = ELF.get_ei_class_from_name(value)
715            elif key == 'EI_DATA':
716                self.ei_data = ELF.get_ei_data_from_name(value)
717            elif key == 'E_MACHINE':
718                self.e_machine = ELF.get_e_machine_from_name(value)
719            elif key == 'FILE_SIZE':
720                self.file_size = int(value)
721            elif key == 'RO_SEG_FILE_SIZE':
722                self.ro_seg_file_size = int(value)
723            elif key == 'RO_SEG_MEM_SIZE':
724                self.ro_seg_mem_size = int(value)
725            elif key == 'RW_SEG_FILE_SIZE':
726                self.rw_seg_file_size = int(value)
727            elif key == 'RW_SEG_MEM_SIZE':
728                self.rw_seg_mem_size = int(value)
729            elif key == 'DT_RPATH':
730                self.dt_rpath.append(intern(value))
731            elif key == 'DT_RUNPATH':
732                self.dt_runpath.append(intern(value))
733            elif key == 'DT_NEEDED':
734                self.dt_needed.append(intern(value))
735            elif key == 'EXP_SYMBOL':
736                self.exported_symbols.add(intern(value))
737            elif key == 'IMP_SYMBOL':
738                self.imported_symbols.add(intern(value))
739            else:
740                print('error: {}: {}: unknown tag name: {}'
741                        .format(path, line_no + 1, key), file=sys.stderr)
742
743    def _parse_from_dump_file(self, path):
744        """Load information from ELF dump file."""
745        with open(path, 'r') as f:
746            self._parse_from_dump_lines(path, f)
747
748    def _parse_from_dump_buf(self, buf):
749        """Load information from ELF dump buffer."""
750        self._parse_from_dump_lines('<str:0x{:x}>'.format(id(buf)),
751                                    buf.splitlines())
752
753    @staticmethod
754    def load(path):
755        """Create an ELF instance from the file path"""
756        elf = ELF()
757        elf._parse_from_file(path)
758        return elf
759
760    @staticmethod
761    def loads(buf):
762        """Create an ELF instance from the buffer"""
763        elf = ELF()
764        elf._parse_from_buf(buf)
765        return elf
766
767    @staticmethod
768    def load_dump(path):
769        """Create an ELF instance from a dump file path"""
770        elf = ELF()
771        elf._parse_from_dump_file(path)
772        return elf
773
774    @staticmethod
775    def load_dumps(buf):
776        """Create an ELF instance from a dump file buffer"""
777        elf = ELF()
778        elf._parse_from_dump_buf(buf)
779        return elf
780
781    def is_jni_lib(self):
782        """Test whether the ELF file looks like a JNI library."""
783        for name in ['libnativehelper.so', 'libandroid_runtime.so']:
784            if name in self.dt_needed:
785                return True
786        for symbol in itertools.chain(self.imported_symbols,
787                                      self.exported_symbols):
788            if symbol.startswith('JNI_') or symbol.startswith('Java_') or \
789               symbol == 'jniRegisterNativeMethods':
790                return True
791        return False
792
793
794#------------------------------------------------------------------------------
795# APK / Dex File Reader
796#------------------------------------------------------------------------------
797
798class DexFileReader(object):
799    @classmethod
800    def extract_dex_string(cls, buf, offset=0):
801        end = buf.find(b'\0', offset)
802        res = buf[offset:] if end == -1 else buf[offset:end]
803        return res.decode('mutf-8', 'ignore')
804
805    if sys.version_info < (3,):
806        _extract_dex_string = extract_dex_string
807
808        @classmethod
809        def extract_dex_string(cls, buf, offset=0):
810            return cls._extract_dex_string(buf, offset).encode('utf-8')
811
812
813    @classmethod
814    def extract_uleb128(cls, buf, offset=0):
815        num_bytes = 0
816        result = 0
817        shift = 0
818        while True:
819            byte = buf[offset + num_bytes]
820            result |= (byte & 0x7f) << shift
821            num_bytes += 1
822            if (byte & 0x80) == 0:
823                break
824            shift += 7
825        return (result, num_bytes)
826
827
828    Header = create_struct('Header', (
829        ('magic', '4s'),
830        ('version', '4s'),
831        ('checksum', 'I'),
832        ('signature', '20s'),
833        ('file_size', 'I'),
834        ('header_size', 'I'),
835        ('endian_tag', 'I'),
836        ('link_size', 'I'),
837        ('link_off', 'I'),
838        ('map_off', 'I'),
839        ('string_ids_size', 'I'),
840        ('string_ids_off', 'I'),
841        ('type_ids_size', 'I'),
842        ('type_ids_off', 'I'),
843        ('proto_ids_size', 'I'),
844        ('proto_ids_off', 'I'),
845        ('field_ids_size', 'I'),
846        ('field_ids_off', 'I'),
847        ('method_ids_size', 'I'),
848        ('method_ids_off', 'I'),
849        ('class_defs_size', 'I'),
850        ('class_defs_off', 'I'),
851        ('data_size', 'I'),
852        ('data_off', 'I'),
853    ))
854
855
856    StringId = create_struct('StringId', (
857        ('string_data_off', 'I'),
858    ))
859
860
861    @staticmethod
862    def generate_classes_dex_names():
863        yield 'classes.dex'
864        for i in itertools.count(start=2):
865            yield 'classes{}.dex'.format(i)
866
867
868    @classmethod
869    def enumerate_dex_strings_buf(cls, buf, offset=0, data_offset=None):
870        buf = get_py3_bytes(buf)
871        header = cls.Header.unpack_from(buf, offset=offset)
872
873        if data_offset is None:
874            if header.magic == b'dex\n':
875                # In the standard dex file, the data_offset is the offset of
876                # the dex header.
877                data_offset = offset
878            else:
879                # In the compact dex file, the data_offset is sum of the offset
880                # of the dex header and header.data_off.
881                data_offset = offset + header.data_off
882
883        StringId = cls.StringId
884        struct_size = StringId.struct_size
885
886        offset_start = offset + header.string_ids_off
887        offset_end = offset_start + header.string_ids_size * struct_size
888
889        for offset in range(offset_start, offset_end, struct_size):
890            offset = StringId.unpack_from(buf, offset).string_data_off
891            offset += data_offset
892
893            # Skip the ULEB128 integer for UTF-16 string length
894            offset += cls.extract_uleb128(buf, offset)[1]
895
896            # Extract the string
897            yield cls.extract_dex_string(buf, offset)
898
899
900    @classmethod
901    def _read_first_bytes(cls, apk_file, num_bytes):
902        try:
903            with open(apk_file, 'rb') as fp:
904                return fp.read(num_bytes)
905        except IOError:
906            return b''
907
908    @classmethod
909    def is_zipfile(cls, apk_file_path):
910        magic = cls._read_first_bytes(apk_file_path, 2)
911        return magic == b'PK' and zipfile.is_zipfile(apk_file_path)
912
913    @classmethod
914    def enumerate_dex_strings_apk(cls, apk_file_path):
915        with zipfile.ZipFile(apk_file_path, 'r') as zip_file:
916            for name in cls.generate_classes_dex_names():
917                try:
918                    with zip_file.open(name) as dex_file:
919                        for s in cls.enumerate_dex_strings_buf(dex_file.read()):
920                            yield s
921                except KeyError:
922                    break
923
924    @classmethod
925    def is_vdex_file(cls, vdex_file_path):
926        return vdex_file_path.endswith('.vdex')
927
928    VdexHeader = create_struct('VdexHeader', (
929        ('magic', '4s'),
930        ('version', '4s'),
931        ('number_of_dex_files', 'I'),
932        ('dex_size', 'I'),
933        # ('dex_shared_data_size', 'I'),  # >= 016
934        ('verifier_deps_size', 'I'),
935        ('quickening_info_size', 'I'),
936    ))
937
938    @classmethod
939    def enumerate_dex_strings_vdex_buf(cls, buf):
940        buf = get_py3_bytes(buf)
941        vdex_header = cls.VdexHeader.unpack_from(buf, offset=0)
942
943        quickening_table_off_size = 0
944        if vdex_header.version > b'010\x00':
945            quickening_table_off_size = 4
946
947        # Skip vdex file header size
948        offset = cls.VdexHeader.struct_size
949
950        # Skip `dex_shared_data_size`
951        if vdex_header.version >= b'016\x00':
952            offset += 4
953
954        # Skip dex file checksums size
955        offset += 4 * vdex_header.number_of_dex_files
956
957        # Skip this vdex file if there is no dex file section
958        if vdex_header.dex_size == 0:
959            return
960
961        for i in range(vdex_header.number_of_dex_files):
962            # Skip quickening_table_off size
963            offset += quickening_table_off_size
964
965            # Check the dex file magic
966            dex_magic = buf[offset:offset + 4]
967            if dex_magic != b'dex\n' and dex_magic != b'cdex':
968                raise ValueError('bad dex file offset {}'.format(offset))
969
970            dex_header = cls.Header.unpack_from(buf, offset)
971            dex_file_end = offset + dex_header.file_size
972            for s in cls.enumerate_dex_strings_buf(buf, offset):
973                yield s
974            offset = (dex_file_end + 3) // 4 * 4
975
976    @classmethod
977    def enumerate_dex_strings_vdex(cls, vdex_file_path):
978        with open(vdex_file_path, 'rb') as vdex_file:
979            return cls.enumerate_dex_strings_vdex_buf(vdex_file.read())
980
981
982#------------------------------------------------------------------------------
983# TaggedDict
984#------------------------------------------------------------------------------
985
986class TaggedDict(object):
987    def _define_tag_constants(local_ns):
988        tag_list = [
989            'll_ndk', 'll_ndk_indirect',
990            'vndk_sp', 'vndk_sp_indirect', 'vndk_sp_indirect_private',
991            'vndk',
992            'fwk_only', 'fwk_only_rs',
993            'sp_hal', 'sp_hal_dep',
994            'vnd_only',
995            'remove',
996        ]
997        assert len(tag_list) < 32
998
999        tags = {}
1000        for i, tag in enumerate(tag_list):
1001            local_ns[tag.upper()] = 1 << i
1002            tags[tag] = 1 << i
1003
1004        local_ns['TAGS'] = tags
1005
1006    _define_tag_constants(locals())
1007    del _define_tag_constants
1008
1009    _TAG_ALIASES = {
1010        'hl_ndk': 'fwk_only',  # Treat HL-NDK as FWK-ONLY.
1011        'sp_ndk': 'll_ndk',
1012        'sp_ndk_indirect': 'll_ndk_indirect',
1013        'vndk_indirect': 'vndk',  # Legacy
1014        'vndk_sp_hal': 'vndk_sp',  # Legacy
1015        'vndk_sp_both': 'vndk_sp',  # Legacy
1016
1017        # FIXME: LL-NDK-Private, VNDK-Private and VNDK-SP-Private are new tags.
1018        # They should not be treated as aliases.
1019        # TODO: Refine the code that compute and verify VNDK sets and reverse
1020        # the aliases.
1021        'll_ndk_private': 'll_ndk_indirect',
1022        'vndk_private': 'vndk',
1023        'vndk_sp_private': 'vndk_sp_indirect_private',
1024    }
1025
1026    @classmethod
1027    def _normalize_tag(cls, tag):
1028        tag = tag.lower().replace('-', '_')
1029        tag = cls._TAG_ALIASES.get(tag, tag)
1030        if tag not in cls.TAGS:
1031            raise ValueError('unknown lib tag ' + tag)
1032        return tag
1033
1034    _LL_NDK_VIS = {'ll_ndk', 'll_ndk_indirect'}
1035    _VNDK_SP_VIS = {'ll_ndk', 'vndk_sp', 'vndk_sp_indirect',
1036                    'vndk_sp_indirect_private', 'fwk_only_rs'}
1037    _FWK_ONLY_VIS = {'ll_ndk', 'll_ndk_indirect',
1038                     'vndk_sp', 'vndk_sp_indirect', 'vndk_sp_indirect_private',
1039                     'vndk', 'fwk_only', 'fwk_only_rs', 'sp_hal'}
1040    _SP_HAL_VIS = {'ll_ndk', 'vndk_sp', 'sp_hal', 'sp_hal_dep'}
1041
1042    _TAG_VISIBILITY = {
1043        'll_ndk': _LL_NDK_VIS,
1044        'll_ndk_indirect': _LL_NDK_VIS,
1045
1046        'vndk_sp': _VNDK_SP_VIS,
1047        'vndk_sp_indirect': _VNDK_SP_VIS,
1048        'vndk_sp_indirect_private': _VNDK_SP_VIS,
1049
1050        'vndk': {'ll_ndk', 'vndk_sp', 'vndk_sp_indirect', 'vndk'},
1051
1052        'fwk_only': _FWK_ONLY_VIS,
1053        'fwk_only_rs': _FWK_ONLY_VIS,
1054
1055        'sp_hal': _SP_HAL_VIS,
1056        'sp_hal_dep': _SP_HAL_VIS,
1057
1058        'vnd_only': {'ll_ndk', 'vndk_sp', 'vndk_sp_indirect',
1059                     'vndk', 'sp_hal', 'sp_hal_dep', 'vnd_only'},
1060
1061        'remove': set(),
1062    }
1063
1064    del _LL_NDK_VIS, _VNDK_SP_VIS, _FWK_ONLY_VIS, _SP_HAL_VIS
1065
1066    @classmethod
1067    def is_tag_visible(cls, from_tag, to_tag):
1068        return to_tag in cls._TAG_VISIBILITY[from_tag]
1069
1070    def __init__(self, vndk_lib_dirs=None):
1071        self._path_tag = dict()
1072        for tag in self.TAGS:
1073            setattr(self, tag, set())
1074        self._regex_patterns = []
1075
1076        if vndk_lib_dirs is None:
1077            self._vndk_suffixes = ['']
1078        else:
1079            self._vndk_suffixes = [VNDKLibDir.create_vndk_dir_suffix(version)
1080                                   for version in vndk_lib_dirs]
1081
1082    def add(self, tag, lib):
1083        lib_set = getattr(self, tag)
1084        lib_set.add(lib)
1085        self._path_tag[lib] = tag
1086
1087    def add_regex(self, tag, pattern):
1088        self._regex_patterns.append((re.compile(pattern), tag))
1089
1090    def get_path_tag(self, lib):
1091        try:
1092            return self._path_tag[lib]
1093        except KeyError:
1094            pass
1095
1096        for pattern, tag in self._regex_patterns:
1097            if pattern.match(lib):
1098                return tag
1099
1100        return self.get_path_tag_default(lib)
1101
1102    def get_path_tag_default(self, lib):
1103        raise NotImplementedError()
1104
1105    def get_path_tag_bit(self, lib):
1106        return self.TAGS[self.get_path_tag(lib)]
1107
1108    def is_path_visible(self, from_lib, to_lib):
1109        return self.is_tag_visible(self.get_path_tag(from_lib),
1110                                   self.get_path_tag(to_lib))
1111
1112    @staticmethod
1113    def is_ll_ndk(tag_bit):
1114        return bool(tag_bit & TaggedDict.LL_NDK)
1115
1116    @staticmethod
1117    def is_vndk_sp(tag_bit):
1118        return bool(tag_bit & TaggedDict.VNDK_SP)
1119
1120    @staticmethod
1121    def is_vndk_sp_indirect(tag_bit):
1122        return bool(tag_bit & TaggedDict.VNDK_SP_INDIRECT)
1123
1124    @staticmethod
1125    def is_vndk_sp_indirect_private(tag_bit):
1126        return bool(tag_bit & TaggedDict.VNDK_SP_INDIRECT_PRIVATE)
1127
1128    @staticmethod
1129    def is_fwk_only_rs(tag_bit):
1130        return bool(tag_bit & TaggedDict.FWK_ONLY_RS)
1131
1132    @staticmethod
1133    def is_sp_hal(tag_bit):
1134        return bool(tag_bit & TaggedDict.SP_HAL)
1135
1136
1137class TaggedPathDict(TaggedDict):
1138    def load_from_csv(self, fp):
1139        reader = csv.reader(fp)
1140
1141        # Read first row and check the existence of the header.
1142        try:
1143            row = next(reader)
1144        except StopIteration:
1145            return
1146
1147        try:
1148            path_col = row.index('Path')
1149            tag_col = row.index('Tag')
1150        except ValueError:
1151            path_col = 0
1152            tag_col = 1
1153            self.add(self._normalize_tag(row[tag_col]), row[path_col])
1154
1155        # Read the rest of rows.
1156        for row in reader:
1157            self.add(self._normalize_tag(row[tag_col]), row[path_col])
1158
1159    @staticmethod
1160    def create_from_csv(fp, vndk_lib_dirs=None):
1161        d = TaggedPathDict(vndk_lib_dirs)
1162        d.load_from_csv(fp)
1163        return d
1164
1165    @staticmethod
1166    def create_from_csv_path(path, vndk_lib_dirs=None):
1167        with open(path, 'r') as fp:
1168            return TaggedPathDict.create_from_csv(fp, vndk_lib_dirs)
1169
1170    def _enumerate_paths_with_lib(self, pattern):
1171        if '${LIB}' in pattern:
1172            yield pattern.replace('${LIB}', 'lib')
1173            yield pattern.replace('${LIB}', 'lib64')
1174        else:
1175            yield pattern
1176
1177    def _enumerate_paths(self, pattern):
1178        if '${VNDK_VER}' not in pattern:
1179            for path in self._enumerate_paths_with_lib(pattern):
1180                yield path
1181            return
1182        for suffix in self._vndk_suffixes:
1183            pattern_with_suffix = pattern.replace('${VNDK_VER}', suffix)
1184            for path in self._enumerate_paths_with_lib(pattern_with_suffix):
1185                yield path
1186
1187    def add(self, tag, path):
1188        if path.startswith('[regex]'):
1189            super(TaggedPathDict, self).add_regex(tag, path[7:])
1190            return
1191        for path in self._enumerate_paths(path):
1192            super(TaggedPathDict, self).add(tag, path)
1193
1194    def get_path_tag_default(self, path):
1195        return 'vnd_only' if path.startswith('/vendor') else 'fwk_only'
1196
1197
1198class TaggedLibDict(object):
1199    def __init__(self):
1200        self._path_tag = dict()
1201        for tag in TaggedDict.TAGS:
1202            setattr(self, tag, set())
1203
1204    def add(self, tag, lib):
1205        lib_set = getattr(self, tag)
1206        lib_set.add(lib)
1207        self._path_tag[lib] = tag
1208
1209    @staticmethod
1210    def create_from_graph(graph, tagged_paths, generic_refs=None):
1211        d = TaggedLibDict()
1212
1213        for lib in graph.lib_pt[PT_SYSTEM].values():
1214            d.add(tagged_paths.get_path_tag(lib.path), lib)
1215
1216        sp_lib = graph.compute_sp_lib(generic_refs)
1217        for lib in graph.lib_pt[PT_VENDOR].values():
1218            if lib in sp_lib.sp_hal:
1219                d.add('sp_hal', lib)
1220            elif lib in sp_lib.sp_hal_dep:
1221                d.add('sp_hal_dep', lib)
1222            else:
1223                d.add('vnd_only', lib)
1224        return d
1225
1226    def get_path_tag(self, lib):
1227        try:
1228            return self._path_tag[lib]
1229        except KeyError:
1230            return self.get_path_tag_default(lib)
1231
1232    def get_path_tag_default(self, lib):
1233        return 'vnd_only' if lib.path.startswith('/vendor') else 'fwk_only'
1234
1235
1236class LibProperties(object):
1237    Properties = collections.namedtuple(
1238            'Properties', 'vndk vndk_sp vendor_available rule')
1239
1240
1241    def __init__(self, csv_file=None):
1242        self.modules = {}
1243
1244        if csv_file:
1245            reader = csv.reader(csv_file)
1246
1247            header = next(reader)
1248            assert header == ['name', 'vndk', 'vndk_sp', 'vendor_available',
1249                              'rule'], repr(header)
1250
1251            for name, vndk, vndk_sp, vendor_available, rule in reader:
1252                self.modules[name] = self.Properties(
1253                        vndk == 'True', vndk_sp == 'True',
1254                        vendor_available == 'True', rule)
1255
1256
1257    @classmethod
1258    def load_from_path_or_default(cls, path):
1259        if not path:
1260            return LibProperties()
1261
1262        try:
1263            with open(path, 'r') as csv_file:
1264                return LibProperties(csv_file)
1265        except FileNotFoundError:
1266            return LibProperties()
1267
1268
1269    def get(self, name):
1270        try:
1271            return self.modules[name]
1272        except KeyError:
1273            return self.Properties(False, False, False, None)
1274
1275
1276    @staticmethod
1277    def get_lib_properties_file_path(tag_file_path):
1278        root, ext = os.path.splitext(tag_file_path)
1279        return root + '-properties' + ext
1280
1281
1282#------------------------------------------------------------------------------
1283# ELF Linker
1284#------------------------------------------------------------------------------
1285
1286def is_accessible(path):
1287    try:
1288        mode = os.stat(path).st_mode
1289        return (mode & (stat.S_IRUSR | stat.S_IRGRP | stat.S_IROTH)) != 0
1290    except FileNotFoundError:
1291        return False
1292
1293
1294def scan_accessible_files(root):
1295    for base, dirs, files in os.walk(root):
1296        for filename in files:
1297            path = os.path.join(base, filename)
1298            if is_accessible(path):
1299                yield path
1300
1301
1302def scan_elf_files(root):
1303    for path in scan_accessible_files(root):
1304        try:
1305            yield (path, ELF.load(path))
1306        except ELFError:
1307            pass
1308
1309
1310def scan_elf_dump_files(root):
1311    for path in scan_accessible_files(root):
1312        if not path.endswith('.sym'):
1313            continue
1314        yield (path[0:-4], ELF.load_dump(path))
1315
1316
1317PT_SYSTEM = 0
1318PT_VENDOR = 1
1319NUM_PARTITIONS = 2
1320
1321
1322SPLibResult = collections.namedtuple(
1323        'SPLibResult',
1324        'sp_hal sp_hal_dep vndk_sp_hal ll_ndk ll_ndk_indirect '
1325        'vndk_sp_both')
1326
1327
1328VNDKLibTuple = defaultnamedtuple('VNDKLibTuple', 'vndk_sp vndk', [])
1329
1330
1331class VNDKLibDir(list):
1332    """VNDKLibDir is a dict which maps version to VNDK-SP and VNDK directory
1333    paths."""
1334
1335
1336    @classmethod
1337    def create_vndk_dir_suffix(cls, version):
1338        """Create VNDK version suffix."""
1339        return '' if version == 'current' else '-' + version
1340
1341
1342    @classmethod
1343    def create_vndk_sp_dir_name(cls, version):
1344        """Create VNDK-SP directory name from a given version."""
1345        return 'vndk-sp' + cls.create_vndk_dir_suffix(version)
1346
1347
1348    @classmethod
1349    def create_vndk_dir_name(cls, version):
1350        """Create VNDK directory name from a given version."""
1351        return 'vndk' + cls.create_vndk_dir_suffix(version)
1352
1353
1354    @classmethod
1355    def extract_version_from_name(cls, name):
1356        """Extract VNDK version from a name."""
1357        if name in {'vndk', 'vndk-sp'}:
1358            return 'current'
1359        elif name.startswith('vndk-sp-'):
1360            return name[len('vndk-sp-'):]
1361        elif name.startswith('vndk-'):
1362            return name[len('vndk-'):]
1363        else:
1364            return None
1365
1366
1367    @classmethod
1368    def extract_path_component(cls, path, index):
1369        """Extract n-th path component from a posix path."""
1370        start = 0
1371        for i in range(index):
1372            pos = path.find('/', start)
1373            if pos == -1:
1374                return None
1375            start = pos + 1
1376        end = path.find('/', start)
1377        if end == -1:
1378            return None
1379        return path[start:end]
1380
1381
1382    @classmethod
1383    def extract_version_from_path(cls, path):
1384        """Extract VNDK version from the third path component."""
1385        component = cls.extract_path_component(path, 3)
1386        if not component:
1387            return None
1388        return cls.extract_version_from_name(component)
1389
1390
1391    @classmethod
1392    def is_in_vndk_dir(cls, path):
1393        """Determine whether a path is under a VNDK directory."""
1394        component = cls.extract_path_component(path, 3)
1395        if not component:
1396            return False
1397        return (component == 'vndk' or
1398                (component.startswith('vndk-') and
1399                    not component == 'vndk-sp' and
1400                    not component.startswith('vndk-sp-')))
1401
1402
1403    @classmethod
1404    def is_in_vndk_sp_dir(cls, path):
1405        """Determine whether a path is under a VNDK-SP directory."""
1406        component = cls.extract_path_component(path, 3)
1407        if not component:
1408            return False
1409        return component == 'vndk-sp' or component.startswith('vndk-sp-')
1410
1411
1412    @classmethod
1413    def create_vndk_search_paths(cls, lib_dir, version):
1414        """Create VNDK/VNDK-SP search paths from lib_dir and version."""
1415        vndk_sp_name = cls.create_vndk_sp_dir_name(version)
1416        vndk_name = cls.create_vndk_dir_name(version)
1417        return VNDKLibTuple(
1418                [posixpath.join('/vendor', lib_dir, vndk_sp_name),
1419                 posixpath.join('/system', lib_dir, vndk_sp_name)],
1420                [posixpath.join('/vendor', lib_dir, vndk_name),
1421                 posixpath.join('/system', lib_dir, vndk_name)])
1422
1423
1424    @classmethod
1425    def create_default(cls):
1426        """Create default VNDK-SP and VNDK paths without versions."""
1427        vndk_lib_dirs = VNDKLibDir()
1428        vndk_lib_dirs.append('current')
1429        return vndk_lib_dirs
1430
1431
1432    @classmethod
1433    def create_from_version(cls, version):
1434        """Create default VNDK-SP and VNDK paths with the specified version."""
1435        vndk_lib_dirs = VNDKLibDir()
1436        vndk_lib_dirs.append(version)
1437        return vndk_lib_dirs
1438
1439
1440    @classmethod
1441    def create_from_dirs(cls, system_dirs, vendor_dirs):
1442        """Scan system_dirs and vendor_dirs and collect all VNDK-SP and VNDK
1443        directory paths."""
1444
1445        def collect_versions(base_dirs):
1446            versions = set()
1447            for base_dir in base_dirs:
1448                for lib_dir in ('lib', 'lib64'):
1449                    lib_dir_path = os.path.join(base_dir, lib_dir)
1450                    try:
1451                        for name in os.listdir(lib_dir_path):
1452                            version = cls.extract_version_from_name(name)
1453                            if version:
1454                                versions.add(version)
1455                    except FileNotFoundError:
1456                        pass
1457            return versions
1458
1459        versions = set()
1460        if system_dirs:
1461            versions.update(collect_versions(system_dirs))
1462        if vendor_dirs:
1463            versions.update(collect_versions(vendor_dirs))
1464
1465        # Sanity check: Versions must not be 'sp' or start with 'sp-'.
1466        bad_versions = [version for version in versions
1467                        if version == 'sp' or version.startswith('sp-')]
1468        if bad_versions:
1469            raise ValueError('bad vndk version: ' + repr(bad_versions))
1470
1471        return VNDKLibDir(cls.sorted_version(versions))
1472
1473
1474    def classify_vndk_libs(self, libs):
1475        """Classify VNDK/VNDK-SP shared libraries."""
1476        vndk_sp_libs = collections.defaultdict(set)
1477        vndk_libs = collections.defaultdict(set)
1478        other_libs = set()
1479
1480        for lib in libs:
1481            component = self.extract_path_component(lib.path, 3)
1482            if component is None:
1483                other_libs.add(lib)
1484                continue
1485
1486            version = self.extract_version_from_name(component)
1487            if version is None:
1488                other_libs.add(lib)
1489                continue
1490
1491            if component.startswith('vndk-sp'):
1492                vndk_sp_libs[version].add(lib)
1493            else:
1494                vndk_libs[version].add(lib)
1495
1496        return (vndk_sp_libs, vndk_libs, other_libs)
1497
1498
1499    @classmethod
1500    def _get_property(cls, property_file, name):
1501        """Read a property from a property file."""
1502        for line in property_file:
1503            if line.startswith(name + '='):
1504                return line[len(name) + 1:].strip()
1505        return None
1506
1507
1508    @classmethod
1509    def get_ro_vndk_version(cls, vendor_dirs):
1510        """Read ro.vendor.version property from vendor partitions."""
1511        for vendor_dir in vendor_dirs:
1512            path = os.path.join(vendor_dir, 'default.prop')
1513            with open(path, 'r') as property_file:
1514                result = cls._get_property(property_file, 'ro.vndk.version')
1515                if result is not None:
1516                    return result
1517        return None
1518
1519
1520    @classmethod
1521    def sorted_version(cls, versions):
1522        """Sort versions in the following rule:
1523
1524        1. 'current' is the first.
1525
1526        2. The versions that cannot be converted to int are sorted
1527           lexicographically in descendant order.
1528
1529        3. The versions that can be converted to int are sorted as integers in
1530           descendant order.
1531        """
1532
1533        current = []
1534        alpha = []
1535        numeric = []
1536
1537        for version in versions:
1538            if version == 'current':
1539                current.append(version)
1540                continue
1541            try:
1542                numeric.append(int(version))
1543            except ValueError:
1544                alpha.append(version)
1545
1546        alpha.sort(reverse=True)
1547        numeric.sort(reverse=True)
1548
1549        return current + alpha + [str(x) for x in numeric]
1550
1551
1552    def find_vendor_vndk_version(self, vendor_dirs):
1553        """Find the best-fitting VNDK version."""
1554
1555        ro_vndk_version = self.get_ro_vndk_version(vendor_dirs)
1556        if ro_vndk_version is not None:
1557            return ro_vndk_version
1558
1559        if not self:
1560            return 'current'
1561
1562        return self.sorted_version(self)[0]
1563
1564
1565class ELFResolver(object):
1566    def __init__(self, lib_set, default_search_path):
1567        self.lib_set = lib_set
1568        self.default_search_path = default_search_path
1569
1570    def get_candidates(self, name, dt_rpath=None, dt_runpath=None):
1571        if dt_rpath:
1572            for d in dt_rpath:
1573                yield os.path.join(d, name)
1574        if dt_runpath:
1575            for d in dt_runpath:
1576                yield os.path.join(d, name)
1577        for d in self.default_search_path:
1578            yield os.path.join(d, name)
1579
1580    def resolve(self, name, dt_rpath=None, dt_runpath=None):
1581        for path in self.get_candidates(name, dt_rpath, dt_runpath):
1582            try:
1583                return self.lib_set[path]
1584            except KeyError:
1585                continue
1586        return None
1587
1588
1589class ELFLinkData(object):
1590    def __init__(self, partition, path, elf, tag_bit):
1591        self.partition = partition
1592        self.path = path
1593        self.elf = elf
1594        self.deps_needed = set()
1595        self.deps_needed_hidden = set()
1596        self.deps_dlopen = set()
1597        self.deps_dlopen_hidden = set()
1598        self.users_needed = set()
1599        self.users_needed_hidden = set()
1600        self.users_dlopen = set()
1601        self.users_dlopen_hidden = set()
1602        self.imported_ext_symbols = collections.defaultdict(set)
1603        self._tag_bit = tag_bit
1604        self.unresolved_symbols = set()
1605        self.unresolved_dt_needed = []
1606        self.linked_symbols = dict()
1607
1608    @property
1609    def is_ll_ndk(self):
1610        return TaggedDict.is_ll_ndk(self._tag_bit)
1611
1612    @property
1613    def is_vndk_sp(self):
1614        return TaggedDict.is_vndk_sp(self._tag_bit)
1615
1616    @property
1617    def is_vndk_sp_indirect(self):
1618        return TaggedDict.is_vndk_sp_indirect(self._tag_bit)
1619
1620    @property
1621    def is_vndk_sp_indirect_private(self):
1622        return TaggedDict.is_vndk_sp_indirect_private(self._tag_bit)
1623
1624    @property
1625    def is_fwk_only_rs(self):
1626        return TaggedDict.is_fwk_only_rs(self._tag_bit)
1627
1628    @property
1629    def is_sp_hal(self):
1630        return TaggedDict.is_sp_hal(self._tag_bit)
1631
1632    def add_needed_dep(self, dst):
1633        assert dst not in self.deps_needed_hidden
1634        assert self not in dst.users_needed_hidden
1635        self.deps_needed.add(dst)
1636        dst.users_needed.add(self)
1637
1638    def add_dlopen_dep(self, dst):
1639        assert dst not in self.deps_dlopen_hidden
1640        assert self not in dst.users_dlopen_hidden
1641        self.deps_dlopen.add(dst)
1642        dst.users_dlopen.add(self)
1643
1644    def hide_needed_dep(self, dst):
1645        self.deps_needed.remove(dst)
1646        dst.users_needed.remove(self)
1647        self.deps_needed_hidden.add(dst)
1648        dst.users_needed_hidden.add(self)
1649
1650    def hide_dlopen_dep(self, dst):
1651        self.deps_dlopen.remove(dst)
1652        dst.users_dlopen.remove(self)
1653        self.deps_dlopen_hidden.add(dst)
1654        dst.users_dlopen_hidden.add(self)
1655
1656    @property
1657    def num_deps(self):
1658        """Get the number of dependencies.  If a library is linked by both
1659        NEEDED and DLOPEN relationship, then it will be counted twice."""
1660        return (len(self.deps_needed) + len(self.deps_needed_hidden) +
1661                len(self.deps_dlopen) + len(self.deps_dlopen_hidden))
1662
1663    @property
1664    def deps_all(self):
1665        return itertools.chain(self.deps_needed, self.deps_needed_hidden,
1666                               self.deps_dlopen, self.deps_dlopen_hidden)
1667
1668    @property
1669    def deps_good(self):
1670        return itertools.chain(self.deps_needed, self.deps_dlopen)
1671
1672    @property
1673    def deps_needed_all(self):
1674        return itertools.chain(self.deps_needed, self.deps_needed_hidden)
1675
1676    @property
1677    def deps_dlopen_all(self):
1678        return itertools.chain(self.deps_dlopen, self.deps_dlopen_hidden)
1679
1680    @property
1681    def num_users(self):
1682        """Get the number of users.  If a library is linked by both NEEDED and
1683        DLOPEN relationship, then it will be counted twice."""
1684        return (len(self.users_needed) + len(self.users_needed_hidden) +
1685                len(self.users_dlopen) + len(self.users_dlopen_hidden))
1686
1687    @property
1688    def users_all(self):
1689        return itertools.chain(self.users_needed, self.users_needed_hidden,
1690                               self.users_dlopen, self.users_dlopen_hidden)
1691
1692    @property
1693    def users_good(self):
1694        return itertools.chain(self.users_needed, self.users_dlopen)
1695
1696    @property
1697    def users_needed_all(self):
1698        return itertools.chain(self.users_needed, self.users_needed_hidden)
1699
1700    @property
1701    def users_dlopen_all(self):
1702        return itertools.chain(self.users_dlopen, self.users_dlopen_hidden)
1703
1704    def has_dep(self, dst):
1705        return (dst in self.deps_needed or dst in self.deps_needed_hidden or
1706                dst in self.deps_dlopen or dst in self.deps_dlopen_hidden)
1707
1708    def has_user(self, dst):
1709        return (dst in self.users_needed or dst in self.users_needed_hidden or
1710                dst in self.users_dlopen or dst in self.users_dlopen_hidden)
1711
1712    def is_system_lib(self):
1713        return self.partition == PT_SYSTEM
1714
1715    def get_dep_linked_symbols(self, dep):
1716        symbols = set()
1717        for symbol, exp_lib in self.linked_symbols.items():
1718            if exp_lib == dep:
1719                symbols.add(symbol)
1720        return sorted(symbols)
1721
1722    def __lt__(self, rhs):
1723        return self.path < rhs.path
1724
1725
1726def sorted_lib_path_list(libs):
1727    libs = [lib.path for lib in libs]
1728    libs.sort()
1729    return libs
1730
1731_VNDK_RESULT_FIELD_NAMES = (
1732        'll_ndk', 'll_ndk_indirect',
1733        'vndk_sp', 'vndk_sp_unused', 'vndk_sp_indirect',
1734        'vndk_sp_indirect_unused', 'vndk_sp_indirect_private', 'vndk',
1735        'vndk_indirect', 'fwk_only', 'fwk_only_rs', 'sp_hal', 'sp_hal_dep',
1736        'vnd_only', 'vndk_ext', 'vndk_sp_ext', 'vndk_sp_indirect_ext',
1737        'extra_vendor_libs')
1738
1739VNDKResult = defaultnamedtuple('VNDKResult', _VNDK_RESULT_FIELD_NAMES, set())
1740
1741_SIMPLE_VNDK_RESULT_FIELD_NAMES = (
1742        'vndk_sp', 'vndk_sp_ext', 'extra_vendor_libs')
1743
1744SimpleVNDKResult = defaultnamedtuple(
1745        'SimpleVNDKResult', _SIMPLE_VNDK_RESULT_FIELD_NAMES, set())
1746
1747
1748class ELFLibDict(defaultnamedtuple('ELFLibDict', ('lib32', 'lib64'), {})):
1749    def get_lib_dict(self, elf_class):
1750        return self[elf_class - 1]
1751
1752    def add(self, path, lib):
1753        self.get_lib_dict(lib.elf.ei_class)[path] = lib
1754
1755    def remove(self, lib):
1756        del self.get_lib_dict(lib.elf.ei_class)[lib.path]
1757
1758    def get(self, path, default=None):
1759        for lib_set in self:
1760            res = lib_set.get(path, None)
1761            if res:
1762                return res
1763        return default
1764
1765    def keys(self):
1766        return itertools.chain(self.lib32.keys(), self.lib64.keys())
1767
1768    def values(self):
1769        return itertools.chain(self.lib32.values(), self.lib64.values())
1770
1771    def items(self):
1772        return itertools.chain(self.lib32.items(), self.lib64.items())
1773
1774
1775class ELFLinker(object):
1776    def __init__(self, tagged_paths=None, vndk_lib_dirs=None,
1777                 ro_vndk_version='current'):
1778        self.lib_pt = [ELFLibDict() for i in range(NUM_PARTITIONS)]
1779
1780        if vndk_lib_dirs is None:
1781            vndk_lib_dirs = VNDKLibDir.create_default()
1782
1783        self.vndk_lib_dirs = vndk_lib_dirs
1784
1785        if tagged_paths is None:
1786            script_dir = os.path.dirname(os.path.abspath(__file__))
1787            dataset_path = os.path.join(
1788                    script_dir, 'datasets', 'minimum_tag_file.csv')
1789            self.tagged_paths = TaggedPathDict.create_from_csv_path(
1790                    dataset_path, vndk_lib_dirs)
1791        else:
1792            self.tagged_paths = tagged_paths
1793
1794        self.ro_vndk_version = ro_vndk_version
1795
1796    def _add_lib_to_lookup_dict(self, lib):
1797        self.lib_pt[lib.partition].add(lib.path, lib)
1798
1799    def _remove_lib_from_lookup_dict(self, lib):
1800        self.lib_pt[lib.partition].remove(lib)
1801
1802    def add_lib(self, partition, path, elf):
1803        lib = ELFLinkData(partition, path, elf,
1804                          self.tagged_paths.get_path_tag_bit(path))
1805        self._add_lib_to_lookup_dict(lib)
1806        return lib
1807
1808    def add_dlopen_dep(self, src_path, dst_path):
1809        num_matches = 0
1810        for elf_class in (ELF.ELFCLASS32, ELF.ELFCLASS64):
1811            srcs = self._get_libs_in_elf_class(elf_class, src_path)
1812            dsts = self._get_libs_in_elf_class(elf_class, dst_path)
1813            for src, dst in itertools.product(srcs, dsts):
1814                src.add_dlopen_dep(dst)
1815                num_matches += 1
1816        if num_matches == 0:
1817            raise ValueError('Failed to add dlopen dependency from {} to {}'
1818                             .format(src_path, dst_path))
1819
1820    def _get_libs_in_elf_class(self, elf_class, path):
1821        result = set()
1822        if '${LIB}' in path:
1823            lib_dir = 'lib' if elf_class == ELF.ELFCLASS32 else 'lib64'
1824            path = path.replace('${LIB}', lib_dir)
1825        if path.startswith('[regex]'):
1826            patt = re.compile(path[7:])
1827            for partition in range(NUM_PARTITIONS):
1828                lib_set = self.lib_pt[partition].get_lib_dict(elf_class)
1829                for path ,lib in lib_set.items():
1830                    if patt.match(path):
1831                        result.add(lib)
1832        else:
1833            for partition in range(NUM_PARTITIONS):
1834                lib_set = self.lib_pt[partition].get_lib_dict(elf_class)
1835                lib = lib_set.get(path)
1836                if lib:
1837                    result.add(lib)
1838        return result
1839
1840    def get_lib(self, path):
1841        for lib_set in self.lib_pt:
1842            lib = lib_set.get(path)
1843            if lib:
1844                return lib
1845        return None
1846
1847    def get_libs(self, paths, report_error=None):
1848        result = set()
1849        for path in paths:
1850            lib = self.get_lib(path)
1851            if not lib:
1852                if report_error is None:
1853                    raise ValueError('path not found ' + path)
1854                report_error(path)
1855                continue
1856            result.add(lib)
1857        return result
1858
1859    def all_libs(self):
1860        for lib_set in self.lib_pt:
1861            for lib in lib_set.values():
1862                yield lib
1863
1864    def _compute_lib_dict(self, elf_class):
1865        res = dict()
1866        for lib_pt in self.lib_pt:
1867            res.update(lib_pt.get_lib_dict(elf_class))
1868        return res
1869
1870    @staticmethod
1871    def _compile_path_matcher(root, subdirs):
1872        dirs = [os.path.normpath(os.path.join(root, i)) for i in subdirs]
1873        patts = ['(?:' + re.escape(i) + os.sep + ')' for i in dirs]
1874        return re.compile('|'.join(patts))
1875
1876    def add_executables_in_dir(self, partition_name, partition, root,
1877                               alter_partition, alter_subdirs, ignored_subdirs,
1878                               scan_elf_files):
1879        root = os.path.abspath(root)
1880        prefix_len = len(root) + 1
1881
1882        if alter_subdirs:
1883            alter_patt = ELFLinker._compile_path_matcher(root, alter_subdirs)
1884        if ignored_subdirs:
1885            ignored_patt = ELFLinker._compile_path_matcher(root, ignored_subdirs)
1886
1887        for path, elf in scan_elf_files(root):
1888            # Ignore ELF files with unknown machine ID (eg. DSP).
1889            if elf.e_machine not in ELF.ELF_MACHINES:
1890                continue
1891
1892            # Ignore ELF files with matched path.
1893            short_path = os.path.join('/', partition_name, path[prefix_len:])
1894            if ignored_subdirs and ignored_patt.match(path):
1895                continue
1896
1897            if alter_subdirs and alter_patt.match(path):
1898                self.add_lib(alter_partition, short_path, elf)
1899            else:
1900                self.add_lib(partition, short_path, elf)
1901
1902    def add_dlopen_deps(self, path):
1903        patt = re.compile('([^:]*):\\s*(.*)')
1904        with open(path, 'r') as dlopen_dep_file:
1905            for line_no, line in enumerate(dlopen_dep_file, start=1):
1906                match = patt.match(line)
1907                if not match:
1908                    continue
1909                try:
1910                    self.add_dlopen_dep(match.group(1), match.group(2))
1911                except ValueError as e:
1912                    print('error:{}:{}: {}.'.format(path, line_no, e),
1913                          file=sys.stderr)
1914
1915    def _find_exported_symbol(self, symbol, libs):
1916        """Find the shared library with the exported symbol."""
1917        for lib in libs:
1918            if symbol in lib.elf.exported_symbols:
1919                return lib
1920        return None
1921
1922    def _resolve_lib_imported_symbols(self, lib, imported_libs, generic_refs):
1923        """Resolve the imported symbols in a library."""
1924        for symbol in lib.elf.imported_symbols:
1925            imported_lib = self._find_exported_symbol(symbol, imported_libs)
1926            if not imported_lib:
1927                lib.unresolved_symbols.add(symbol)
1928            else:
1929                lib.linked_symbols[symbol] = imported_lib
1930                if generic_refs:
1931                    ref_lib = generic_refs.refs.get(imported_lib.path)
1932                    if not ref_lib or not symbol in ref_lib.exported_symbols:
1933                        lib.imported_ext_symbols[imported_lib].add(symbol)
1934
1935    def _resolve_lib_dt_needed(self, lib, resolver):
1936        imported_libs = []
1937        for dt_needed in lib.elf.dt_needed:
1938            dep = resolver.resolve(dt_needed, lib.elf.dt_rpath,
1939                                   lib.elf.dt_runpath)
1940            if not dep:
1941                candidates = list(resolver.get_candidates(
1942                    dt_needed, lib.elf.dt_rpath, lib.elf.dt_runpath))
1943                print('warning: {}: Missing needed library: {}  Tried: {}'
1944                      .format(lib.path, dt_needed, candidates), file=sys.stderr)
1945                lib.unresolved_dt_needed.append(dt_needed)
1946                continue
1947            lib.add_needed_dep(dep)
1948            imported_libs.append(dep)
1949        return imported_libs
1950
1951    def _resolve_lib_deps(self, lib, resolver, generic_refs):
1952        # Resolve DT_NEEDED entries.
1953        imported_libs = self._resolve_lib_dt_needed(lib, resolver)
1954
1955        if generic_refs:
1956            for imported_lib in imported_libs:
1957                if imported_lib.path not in generic_refs.refs:
1958                    # Add imported_lib to imported_ext_symbols to make sure
1959                    # non-AOSP libraries are in the imported_ext_symbols key
1960                    # set.
1961                    lib.imported_ext_symbols[imported_lib].update()
1962
1963        # Resolve imported symbols.
1964        self._resolve_lib_imported_symbols(lib, imported_libs, generic_refs)
1965
1966    def _resolve_lib_set_deps(self, lib_set, resolver, generic_refs):
1967        for lib in lib_set:
1968            self._resolve_lib_deps(lib, resolver, generic_refs)
1969
1970
1971    def _get_system_search_paths(self, lib_dir):
1972        return [
1973            '/system/' + lib_dir,
1974            # To find violating dependencies to vendor partitions.
1975            '/vendor/' + lib_dir,
1976        ]
1977
1978    def _get_vendor_search_paths(self, lib_dir, vndk_sp_dirs, vndk_dirs):
1979        vendor_lib_dirs = [
1980            '/vendor/' + lib_dir + '/hw',
1981            '/vendor/' + lib_dir + '/egl',
1982            '/vendor/' + lib_dir,
1983        ]
1984        system_lib_dirs = [
1985            # For degenerated VNDK libs.
1986            '/system/' + lib_dir,
1987        ]
1988        return vendor_lib_dirs + vndk_sp_dirs + vndk_dirs + system_lib_dirs
1989
1990
1991    def _get_vndk_sp_search_paths(self, lib_dir, vndk_sp_dirs):
1992        fallback_lib_dirs = [
1993            # To find missing VNDK-SP dependencies.
1994            '/vendor/' + lib_dir,
1995            # To find missing VNDK-SP dependencies or LL-NDK.
1996            '/system/' + lib_dir,
1997        ]
1998        return vndk_sp_dirs + fallback_lib_dirs
1999
2000
2001    def _get_vndk_search_paths(self, lib_dir, vndk_sp_dirs, vndk_dirs):
2002        fallback_lib_dirs = [
2003            # To find missing VNDK dependencies or LL-NDK.
2004            '/system/' + lib_dir,
2005        ]
2006        return vndk_sp_dirs + vndk_dirs + fallback_lib_dirs
2007
2008
2009    def _resolve_elf_class_deps(self, lib_dir, elf_class, generic_refs):
2010        # Classify libs.
2011        vndk_lib_dirs = self.vndk_lib_dirs
2012        lib_dict = self._compute_lib_dict(elf_class)
2013
2014        system_lib_dict = self.lib_pt[PT_SYSTEM].get_lib_dict(elf_class)
2015        system_vndk_sp_libs, system_vndk_libs, system_libs = \
2016                vndk_lib_dirs.classify_vndk_libs(system_lib_dict.values())
2017
2018        vendor_lib_dict = self.lib_pt[PT_VENDOR].get_lib_dict(elf_class)
2019        vendor_vndk_sp_libs, vendor_vndk_libs, vendor_libs = \
2020                vndk_lib_dirs.classify_vndk_libs(vendor_lib_dict.values())
2021
2022        # Resolve system libs.
2023        search_paths = self._get_system_search_paths(lib_dir)
2024        resolver = ELFResolver(lib_dict, search_paths)
2025        self._resolve_lib_set_deps(system_libs, resolver, generic_refs)
2026
2027        # Resolve vndk-sp libs
2028        for version in vndk_lib_dirs:
2029            vndk_sp_dirs, vndk_dirs = \
2030                    vndk_lib_dirs.create_vndk_search_paths(lib_dir, version)
2031            vndk_sp_libs = system_vndk_sp_libs[version] | \
2032                           vendor_vndk_sp_libs[version]
2033            search_paths = self._get_vndk_sp_search_paths(lib_dir, vndk_sp_dirs)
2034            resolver = ELFResolver(lib_dict, search_paths)
2035            self._resolve_lib_set_deps(vndk_sp_libs, resolver, generic_refs)
2036
2037        # Resolve vndk libs
2038        for version in vndk_lib_dirs:
2039            vndk_sp_dirs, vndk_dirs = \
2040                    vndk_lib_dirs.create_vndk_search_paths(lib_dir, version)
2041            vndk_libs = system_vndk_libs[version] | vendor_vndk_libs[version]
2042            search_paths = self._get_vndk_search_paths(
2043                    lib_dir, vndk_sp_dirs, vndk_dirs)
2044            resolver = ELFResolver(lib_dict, search_paths)
2045            self._resolve_lib_set_deps(vndk_libs, resolver, generic_refs)
2046
2047        # Resolve vendor libs.
2048        vndk_sp_dirs, vndk_dirs = vndk_lib_dirs.create_vndk_search_paths(
2049                lib_dir, self.ro_vndk_version)
2050        search_paths = self._get_vendor_search_paths(
2051                lib_dir, vndk_sp_dirs, vndk_dirs)
2052        resolver = ELFResolver(lib_dict, search_paths)
2053        self._resolve_lib_set_deps(vendor_libs, resolver, generic_refs)
2054
2055
2056    def resolve_deps(self, generic_refs=None):
2057        self._resolve_elf_class_deps('lib', ELF.ELFCLASS32, generic_refs)
2058        self._resolve_elf_class_deps('lib64', ELF.ELFCLASS64, generic_refs)
2059
2060
2061    def compute_predefined_sp_hal(self):
2062        """Find all same-process HALs."""
2063        return set(lib for lib in self.all_libs() if lib.is_sp_hal)
2064
2065
2066    def compute_sp_lib(self, generic_refs, ignore_hidden_deps=False):
2067        def is_ll_ndk_or_sp_hal(lib):
2068            return lib.is_ll_ndk or lib.is_sp_hal
2069
2070        ll_ndk = set(lib for lib in self.all_libs() if lib.is_ll_ndk)
2071        ll_ndk_closure = self.compute_deps_closure(
2072                ll_ndk, is_ll_ndk_or_sp_hal, ignore_hidden_deps)
2073        ll_ndk_indirect = ll_ndk_closure - ll_ndk
2074
2075        def is_ll_ndk(lib):
2076            return lib.is_ll_ndk
2077
2078        sp_hal = self.compute_predefined_sp_hal()
2079        sp_hal_closure = self.compute_deps_closure(
2080                sp_hal, is_ll_ndk, ignore_hidden_deps)
2081
2082        def is_aosp_lib(lib):
2083            return (not generic_refs or
2084                    generic_refs.classify_lib(lib) != GenericRefs.NEW_LIB)
2085
2086        vndk_sp_hal = set()
2087        sp_hal_dep = set()
2088        for lib in sp_hal_closure - sp_hal:
2089            if is_aosp_lib(lib):
2090                vndk_sp_hal.add(lib)
2091            else:
2092                sp_hal_dep.add(lib)
2093
2094        vndk_sp_both = ll_ndk_indirect & vndk_sp_hal
2095        ll_ndk_indirect -= vndk_sp_both
2096        vndk_sp_hal -= vndk_sp_both
2097
2098        return SPLibResult(sp_hal, sp_hal_dep, vndk_sp_hal, ll_ndk,
2099                           ll_ndk_indirect, vndk_sp_both)
2100
2101    def normalize_partition_tags(self, sp_hals, generic_refs):
2102        def is_system_lib_or_sp_hal(lib):
2103            return lib.is_system_lib() or lib in sp_hals
2104
2105        for lib in self.lib_pt[PT_SYSTEM].values():
2106            if all(is_system_lib_or_sp_hal(dep) for dep in lib.deps_all):
2107                continue
2108            # If a system module is depending on a vendor shared library and
2109            # such shared library is not a SP-HAL library, then emit an error
2110            # and hide the dependency.
2111            for dep in list(lib.deps_needed_all):
2112                if not is_system_lib_or_sp_hal(dep):
2113                    print('error: {}: system exe/lib must not depend on '
2114                          'vendor lib {}.  Assume such dependency does '
2115                          'not exist.'.format(lib.path, dep.path),
2116                          file=sys.stderr)
2117                    lib.hide_needed_dep(dep)
2118            for dep in list(lib.deps_dlopen_all):
2119                if not is_system_lib_or_sp_hal(dep):
2120                    print('error: {}: system exe/lib must not dlopen() '
2121                          'vendor lib {}.  Assume such dependency does '
2122                          'not exist.'.format(lib.path, dep.path),
2123                          file=sys.stderr)
2124                    lib.hide_dlopen_dep(dep)
2125
2126    @staticmethod
2127    def _parse_action_on_ineligible_lib(arg):
2128        follow = False
2129        warn = False
2130        for flag in arg.split(','):
2131            if flag == 'follow':
2132                follow = True
2133            elif flag == 'warn':
2134                warn = True
2135            elif flag == 'ignore':
2136                continue
2137            else:
2138                raise ValueError('unknown action \"{}\"'.format(flag))
2139        return (follow, warn)
2140
2141    def compute_degenerated_vndk(self, generic_refs, tagged_paths=None,
2142                                 action_ineligible_vndk_sp='warn',
2143                                 action_ineligible_vndk='warn'):
2144        # Find LL-NDK libs.
2145        ll_ndk = set(lib for lib in self.all_libs() if lib.is_ll_ndk)
2146
2147        # Find pre-defined libs.
2148        fwk_only_rs = set(lib for lib in self.all_libs() if lib.is_fwk_only_rs)
2149        predefined_vndk_sp = set(
2150                lib for lib in self.all_libs() if lib.is_vndk_sp)
2151        predefined_vndk_sp_indirect = set(
2152                lib for lib in self.all_libs() if lib.is_vndk_sp_indirect)
2153        predefined_vndk_sp_indirect_private = set(
2154                lib for lib in self.all_libs()
2155                if lib.is_vndk_sp_indirect_private)
2156
2157        # FIXME: Don't squash VNDK-SP-Indirect-Private into VNDK-SP-Indirect.
2158        predefined_vndk_sp_indirect |= predefined_vndk_sp_indirect_private
2159
2160        # Find SP-HAL libs.
2161        sp_hal = self.compute_predefined_sp_hal()
2162
2163        # Normalize partition tags.  We expect many violations from the
2164        # pre-Treble world.  Guess a resolution for the incorrect partition
2165        # tag.
2166        self.normalize_partition_tags(sp_hal, generic_refs)
2167
2168        # Find SP-HAL-Dep libs.
2169        def is_aosp_lib(lib):
2170            if not generic_refs:
2171                # If generic reference is not available, then assume all system
2172                # libs are AOSP libs.
2173                return lib.partition == PT_SYSTEM
2174            return generic_refs.has_same_name_lib(lib)
2175
2176        def is_not_sp_hal_dep(lib):
2177            if lib.is_ll_ndk or lib in sp_hal:
2178                return True
2179            return is_aosp_lib(lib)
2180
2181        sp_hal_dep = self.compute_deps_closure(sp_hal, is_not_sp_hal_dep, True)
2182        sp_hal_dep -= sp_hal
2183
2184        # Find VNDK-SP libs.
2185        def is_not_vndk_sp(lib):
2186            return lib.is_ll_ndk or lib in sp_hal or lib in sp_hal_dep
2187
2188        follow_ineligible_vndk_sp, warn_ineligible_vndk_sp = \
2189                self._parse_action_on_ineligible_lib(action_ineligible_vndk_sp)
2190        vndk_sp = set()
2191        for lib in itertools.chain(sp_hal, sp_hal_dep):
2192            for dep in lib.deps_all:
2193                if is_not_vndk_sp(dep):
2194                    continue
2195                if dep in predefined_vndk_sp:
2196                    vndk_sp.add(dep)
2197                    continue
2198                if warn_ineligible_vndk_sp:
2199                    print('error: SP-HAL {} depends on non vndk-sp '
2200                          'library {}.'.format(lib.path, dep.path),
2201                          file=sys.stderr)
2202                if follow_ineligible_vndk_sp:
2203                    vndk_sp.add(dep)
2204
2205        # Find VNDK-SP-Indirect libs.
2206        def is_not_vndk_sp_indirect(lib):
2207            return lib.is_ll_ndk or lib in vndk_sp or lib in fwk_only_rs
2208
2209        vndk_sp_indirect = self.compute_deps_closure(
2210                vndk_sp, is_not_vndk_sp_indirect, True)
2211        vndk_sp_indirect -= vndk_sp
2212
2213        # Find unused predefined VNDK-SP libs.
2214        vndk_sp_unused = set(lib for lib in predefined_vndk_sp
2215                             if VNDKLibDir.is_in_vndk_sp_dir(lib.path))
2216        vndk_sp_unused -= vndk_sp
2217        vndk_sp_unused -= vndk_sp_indirect
2218
2219        # Find dependencies of unused predefined VNDK-SP libs.
2220        def is_not_vndk_sp_indirect_unused(lib):
2221            return is_not_vndk_sp_indirect(lib) or lib in vndk_sp_indirect
2222        vndk_sp_unused_deps = self.compute_deps_closure(
2223                vndk_sp_unused, is_not_vndk_sp_indirect_unused, True)
2224        vndk_sp_unused_deps -= vndk_sp_unused
2225
2226        vndk_sp_indirect_unused = set(lib for lib in predefined_vndk_sp_indirect
2227                                      if VNDKLibDir.is_in_vndk_sp_dir(lib.path))
2228        vndk_sp_indirect_unused -= vndk_sp_indirect
2229        vndk_sp_indirect_unused -= vndk_sp_unused
2230        vndk_sp_indirect_unused |= vndk_sp_unused_deps
2231
2232        # TODO: Compute VNDK-SP-Indirect-Private.
2233        vndk_sp_indirect_private = set()
2234
2235        assert not (vndk_sp & vndk_sp_indirect)
2236        assert not (vndk_sp_unused & vndk_sp_indirect_unused)
2237
2238        # Define helper functions for vndk_sp sets.
2239        def is_vndk_sp_public(lib):
2240            return lib in vndk_sp or lib in vndk_sp_unused or \
2241                   lib in vndk_sp_indirect or \
2242                   lib in vndk_sp_indirect_unused
2243
2244        def is_vndk_sp(lib):
2245            return is_vndk_sp_public(lib) or lib in vndk_sp_indirect_private
2246
2247        def is_vndk_sp_unused(lib):
2248            return lib in vndk_sp_unused or lib in vndk_sp_indirect_unused
2249
2250        def relabel_vndk_sp_as_used(lib):
2251            assert is_vndk_sp_unused(lib)
2252
2253            if lib in vndk_sp_unused:
2254                vndk_sp_unused.remove(lib)
2255                vndk_sp.add(lib)
2256            else:
2257                vndk_sp_indirect_unused.remove(lib)
2258                vndk_sp_indirect.add(lib)
2259
2260            # Add the dependencies to vndk_sp_indirect if they are not vndk_sp.
2261            closure = self.compute_deps_closure(
2262                    {lib}, lambda lib: lib not in vndk_sp_indirect_unused, True)
2263            closure.remove(lib)
2264            vndk_sp_indirect_unused.difference_update(closure)
2265            vndk_sp_indirect.update(closure)
2266
2267        # Find VNDK-SP-Ext libs.
2268        vndk_sp_ext = set()
2269        def collect_vndk_ext(libs):
2270            result = set()
2271            for lib in libs:
2272                for dep in lib.imported_ext_symbols:
2273                    if dep in vndk_sp and dep not in vndk_sp_ext:
2274                        result.add(dep)
2275            return result
2276
2277        candidates = collect_vndk_ext(self.lib_pt[PT_VENDOR].values())
2278        while candidates:
2279            vndk_sp_ext |= candidates
2280            candidates = collect_vndk_ext(candidates)
2281
2282        # Find VNDK-SP-Indirect-Ext libs.
2283        vndk_sp_indirect_ext = set()
2284        def collect_vndk_sp_indirect_ext(libs):
2285            result = set()
2286            for lib in libs:
2287                exts = set(lib.imported_ext_symbols.keys())
2288                for dep in lib.deps_all:
2289                    if not is_vndk_sp_public(dep):
2290                        continue
2291                    if dep in vndk_sp_ext or dep in vndk_sp_indirect_ext:
2292                        continue
2293                    # If lib is using extended definition from deps, then we
2294                    # have to make a copy of dep.
2295                    if dep in exts:
2296                        result.add(dep)
2297                        continue
2298                    # If lib is using non-predefined VNDK-SP-Indirect, then we
2299                    # have to make a copy of dep.
2300                    if dep not in predefined_vndk_sp and \
2301                            dep not in predefined_vndk_sp_indirect:
2302                        result.add(dep)
2303                        continue
2304            return result
2305
2306        def is_not_vndk_sp_indirect(lib):
2307            return lib.is_ll_ndk or lib in vndk_sp or lib in fwk_only_rs
2308
2309        candidates = collect_vndk_sp_indirect_ext(vndk_sp_ext)
2310        while candidates:
2311            vndk_sp_indirect_ext |= candidates
2312            candidates = collect_vndk_sp_indirect_ext(candidates)
2313
2314        # Find VNDK libs (a.k.a. system shared libs directly used by vendor
2315        # partition.)
2316        def is_not_vndk(lib):
2317            if lib.is_ll_ndk or is_vndk_sp_public(lib) or lib in fwk_only_rs:
2318                return True
2319            return lib.partition != PT_SYSTEM
2320
2321        def is_eligible_lib_access(lib, dep):
2322            return not tagged_paths or \
2323                    tagged_paths.is_path_visible(lib.path, dep.path)
2324
2325        follow_ineligible_vndk, warn_ineligible_vndk = \
2326                self._parse_action_on_ineligible_lib(action_ineligible_vndk)
2327        vndk = set()
2328        extra_vendor_libs = set()
2329        def collect_vndk(vendor_libs):
2330            next_vendor_libs = set()
2331            for lib in vendor_libs:
2332                for dep in lib.deps_all:
2333                    if is_vndk_sp_unused(dep):
2334                        relabel_vndk_sp_as_used(dep)
2335                        continue
2336                    if is_not_vndk(dep):
2337                        continue
2338                    if not is_aosp_lib(dep):
2339                        # The dependency should be copied into vendor partition
2340                        # as an extra vendor lib.
2341                        if dep not in extra_vendor_libs:
2342                            next_vendor_libs.add(dep)
2343                            extra_vendor_libs.add(dep)
2344                        continue
2345                    if is_eligible_lib_access(lib, dep):
2346                        vndk.add(dep)
2347                        continue
2348                    if warn_ineligible_vndk:
2349                        print('warning: vendor lib/exe {} depends on '
2350                              'ineligible framework shared lib {}.'
2351                              .format(lib.path, dep.path), file=sys.stderr)
2352                    if follow_ineligible_vndk:
2353                        vndk.add(dep)
2354            return next_vendor_libs
2355
2356        candidates = collect_vndk(self.lib_pt[PT_VENDOR].values())
2357        while candidates:
2358            candidates = collect_vndk(candidates)
2359
2360        vndk_indirect = self.compute_deps_closure(vndk, is_not_vndk, True)
2361        vndk_indirect -= vndk
2362
2363        def is_vndk(lib):
2364            return lib in vndk or lib in vndk_indirect
2365
2366        # Find VNDK-EXT libs (VNDK libs with extended definitions and the
2367        # extended definitions are used by the vendor modules (including
2368        # extra_vendor_libs).
2369
2370        # FIXME: DAUX libraries won't be found by the following algorithm.
2371        vndk_ext = set()
2372
2373        def collect_vndk_ext(libs):
2374            result = set()
2375            for lib in libs:
2376                for dep in lib.imported_ext_symbols:
2377                    if dep in vndk and dep not in vndk_ext:
2378                        result.add(dep)
2379            return result
2380
2381        candidates = collect_vndk_ext(self.lib_pt[PT_VENDOR].values())
2382        candidates |= collect_vndk_ext(extra_vendor_libs)
2383
2384        while candidates:
2385            vndk_ext |= candidates
2386            candidates = collect_vndk_ext(candidates)
2387
2388        # Compute LL-NDK-Indirect.
2389        def is_not_ll_ndk_indirect(lib):
2390            return lib.is_ll_ndk or lib.is_sp_hal or is_vndk_sp(lib) or \
2391                   is_vndk_sp(lib) or is_vndk(lib)
2392
2393        ll_ndk_indirect = self.compute_deps_closure(
2394                ll_ndk, is_not_ll_ndk_indirect, True)
2395        ll_ndk_indirect -= ll_ndk
2396
2397        # Return the VNDK classifications.
2398        return VNDKResult(
2399                ll_ndk=ll_ndk,
2400                ll_ndk_indirect=ll_ndk_indirect,
2401                vndk_sp=vndk_sp,
2402                vndk_sp_indirect=vndk_sp_indirect,
2403                # vndk_sp_indirect_private=vndk_sp_indirect_private,
2404                vndk_sp_unused=vndk_sp_unused,
2405                vndk_sp_indirect_unused=vndk_sp_indirect_unused,
2406                vndk=vndk,
2407                vndk_indirect=vndk_indirect,
2408                # fwk_only=fwk_only,
2409                fwk_only_rs=fwk_only_rs,
2410                sp_hal=sp_hal,
2411                sp_hal_dep=sp_hal_dep,
2412                # vnd_only=vnd_only,
2413                vndk_ext=vndk_ext,
2414                vndk_sp_ext=vndk_sp_ext,
2415                vndk_sp_indirect_ext=vndk_sp_indirect_ext,
2416                extra_vendor_libs=extra_vendor_libs)
2417
2418    @staticmethod
2419    def _compute_closure(root_set, is_excluded, get_successors):
2420        closure = set(root_set)
2421        stack = list(root_set)
2422        while stack:
2423            lib = stack.pop()
2424            for succ in get_successors(lib):
2425                if is_excluded(succ):
2426                    continue
2427                if succ not in closure:
2428                    closure.add(succ)
2429                    stack.append(succ)
2430        return closure
2431
2432    @classmethod
2433    def compute_deps_closure(cls, root_set, is_excluded,
2434                             ignore_hidden_deps=False):
2435        get_successors = (lambda x: x.deps_good) if ignore_hidden_deps else \
2436                         (lambda x: x.deps_all)
2437        return cls._compute_closure(root_set, is_excluded, get_successors)
2438
2439    @classmethod
2440    def compute_users_closure(cls, root_set, is_excluded,
2441                              ignore_hidden_users=False):
2442        get_successors = (lambda x: x.users_good) if ignore_hidden_users else \
2443                         (lambda x: x.users_all)
2444        return cls._compute_closure(root_set, is_excluded, get_successors)
2445
2446    @staticmethod
2447    def _create_internal(scan_elf_files, system_dirs, system_dirs_as_vendor,
2448                         system_dirs_ignored, vendor_dirs,
2449                         vendor_dirs_as_system, vendor_dirs_ignored,
2450                         extra_deps, generic_refs, tagged_paths,
2451                         vndk_lib_dirs):
2452        if vndk_lib_dirs is None:
2453            vndk_lib_dirs = VNDKLibDir.create_from_dirs(
2454                    system_dirs, vendor_dirs)
2455        ro_vndk_version = vndk_lib_dirs.find_vendor_vndk_version(vendor_dirs)
2456        graph = ELFLinker(tagged_paths, vndk_lib_dirs, ro_vndk_version)
2457
2458        if system_dirs:
2459            for path in system_dirs:
2460                graph.add_executables_in_dir('system', PT_SYSTEM, path,
2461                                             PT_VENDOR, system_dirs_as_vendor,
2462                                             system_dirs_ignored,
2463                                             scan_elf_files)
2464
2465        if vendor_dirs:
2466            for path in vendor_dirs:
2467                graph.add_executables_in_dir('vendor', PT_VENDOR, path,
2468                                             PT_SYSTEM, vendor_dirs_as_system,
2469                                             vendor_dirs_ignored,
2470                                             scan_elf_files)
2471
2472        if extra_deps:
2473            for path in extra_deps:
2474                graph.add_dlopen_deps(path)
2475
2476        graph.resolve_deps(generic_refs)
2477
2478        return graph
2479
2480    @staticmethod
2481    def create(system_dirs=None, system_dirs_as_vendor=None,
2482               system_dirs_ignored=None, vendor_dirs=None,
2483               vendor_dirs_as_system=None, vendor_dirs_ignored=None,
2484               extra_deps=None, generic_refs=None, tagged_paths=None,
2485               vndk_lib_dirs=None):
2486        return ELFLinker._create_internal(
2487                scan_elf_files, system_dirs, system_dirs_as_vendor,
2488                system_dirs_ignored, vendor_dirs, vendor_dirs_as_system,
2489                vendor_dirs_ignored, extra_deps, generic_refs, tagged_paths,
2490                vndk_lib_dirs)
2491
2492
2493#------------------------------------------------------------------------------
2494# Generic Reference
2495#------------------------------------------------------------------------------
2496
2497class GenericRefs(object):
2498    NEW_LIB = 0
2499    EXPORT_EQUAL = 1
2500    EXPORT_SUPER_SET = 2
2501    MODIFIED = 3
2502
2503    def __init__(self):
2504        self.refs = dict()
2505        self._lib_names = set()
2506
2507    def add(self, path, elf):
2508        self.refs[path] = elf
2509        self._lib_names.add(os.path.basename(path))
2510
2511    def _load_from_sym_dir(self, root):
2512        root = os.path.abspath(root)
2513        prefix_len = len(root) + 1
2514        for base, dirnames, filenames in os.walk(root):
2515            for filename in filenames:
2516                if not filename.endswith('.sym'):
2517                    continue
2518                path = os.path.join(base, filename)
2519                lib_path = '/' + path[prefix_len:-4]
2520                with open(path, 'r') as f:
2521                    self.add(lib_path, ELF.load_dump(path))
2522
2523    @staticmethod
2524    def create_from_sym_dir(root):
2525        result = GenericRefs()
2526        result._load_from_sym_dir(root)
2527        return result
2528
2529    def _load_from_image_dir(self, root, prefix):
2530        root = os.path.abspath(root)
2531        root_len = len(root) + 1
2532        for path, elf in scan_elf_files(root):
2533            self.add(os.path.join(prefix, path[root_len:]), elf)
2534
2535    @staticmethod
2536    def create_from_image_dir(root, prefix):
2537        result = GenericRefs()
2538        result._load_from_image_dir(root, prefix)
2539        return result
2540
2541    def classify_lib(self, lib):
2542        ref_lib = self.refs.get(lib.path)
2543        if not ref_lib:
2544            return GenericRefs.NEW_LIB
2545        exported_symbols = lib.elf.exported_symbols
2546        if exported_symbols == ref_lib.exported_symbols:
2547            return GenericRefs.EXPORT_EQUAL
2548        if exported_symbols > ref_lib.exported_symbols:
2549            return GenericRefs.EXPORT_SUPER_SET
2550        return GenericRefs.MODIFIED
2551
2552    def is_equivalent_lib(self, lib):
2553        return self.classify_lib(lib) == GenericRefs.EXPORT_EQUAL
2554
2555    def has_same_name_lib(self, lib):
2556        return os.path.basename(lib.path) in self._lib_names
2557
2558
2559#------------------------------------------------------------------------------
2560# APK Dep
2561#------------------------------------------------------------------------------
2562def _build_lib_names_dict(graph, min_name_len=6, lib_ext='.so'):
2563    names = collections.defaultdict(set)
2564    for lib in graph.all_libs():
2565        name = os.path.basename(lib.path)
2566        root, ext = os.path.splitext(name)
2567
2568        if ext != lib_ext:
2569            continue
2570
2571        if not lib.elf.is_jni_lib():
2572            continue
2573
2574        names[name].add(lib)
2575        names[root].add(lib)
2576
2577        if root.startswith('lib') and len(root) > min_name_len:
2578            # FIXME: libandroid.so is a JNI lib.  However, many apps have
2579            # "android" as a constant string literal, thus "android" is
2580            # skipped here to reduce the false positives.
2581            #
2582            # Note: It is fine to exclude libandroid.so because it is only
2583            # a user of JNI and it does not define any JNI methods.
2584            if root != 'libandroid':
2585                names[root[3:]].add(lib)
2586    return names
2587
2588
2589def _enumerate_partition_paths(partition, root):
2590    prefix_len = len(root) + 1
2591    for base, dirs, files in os.walk(root):
2592        for filename in files:
2593            path = os.path.join(base, filename)
2594            android_path = posixpath.join('/', partition, path[prefix_len:])
2595            yield (android_path, path)
2596
2597
2598def _enumerate_paths(system_dirs, vendor_dirs):
2599    for root in system_dirs:
2600        for ap, path in _enumerate_partition_paths('system', root):
2601            yield (ap, path)
2602    for root in vendor_dirs:
2603        for ap, path in _enumerate_partition_paths('vendor', root):
2604            yield (ap, path)
2605
2606
2607def scan_apk_dep(graph, system_dirs, vendor_dirs):
2608    libnames = _build_lib_names_dict(graph)
2609    results = []
2610
2611    for ap, path in _enumerate_paths(system_dirs, vendor_dirs):
2612        # Read the dex file from various file formats
2613        try:
2614            if DexFileReader.is_zipfile(path):
2615                strs = set(DexFileReader.enumerate_dex_strings_apk(path))
2616            elif DexFileReader.is_vdex_file(path):
2617                strs = set(DexFileReader.enumerate_dex_strings_vdex(path))
2618            else:
2619                continue
2620        except FileNotFoundError:
2621            continue
2622
2623        # Skip the file that does not call System.loadLibrary()
2624        if 'loadLibrary' not in strs:
2625            continue
2626
2627        # Collect libraries from string tables
2628        libs = set()
2629        for string in strs:
2630            try:
2631                libs.update(libnames[string])
2632            except KeyError:
2633                pass
2634
2635        if libs:
2636            results.append((ap, sorted_lib_path_list(libs)))
2637
2638    results.sort()
2639    return results
2640
2641
2642#------------------------------------------------------------------------------
2643# Module Info
2644#------------------------------------------------------------------------------
2645
2646class ModuleInfo(object):
2647    def __init__(self, json=None):
2648        if not json:
2649            self._mods = dict()
2650            return
2651
2652        mods = collections.defaultdict(set)
2653        installed_path_patt = re.compile(
2654                '.*[\\\\/]target[\\\\/]product[\\\\/][^\\\\/]+([\\\\/].*)$')
2655        for name, module in json.items():
2656            for path in module['installed']:
2657                match = installed_path_patt.match(path)
2658                if match:
2659                    for path in module['path']:
2660                        mods[match.group(1)].add(path)
2661        self._mods = { installed_path: sorted(src_dirs)
2662                       for installed_path, src_dirs in mods.items() }
2663
2664    def get_module_path(self, installed_path):
2665        return self._mods.get(installed_path, [])
2666
2667    @staticmethod
2668    def load(f):
2669        return ModuleInfo(json.load(f))
2670
2671    @staticmethod
2672    def load_from_path_or_default(path):
2673        if not path:
2674            return ModuleInfo()
2675        with open(path, 'r') as f:
2676            return ModuleInfo.load(f)
2677
2678
2679#------------------------------------------------------------------------------
2680# Commands
2681#------------------------------------------------------------------------------
2682
2683class Command(object):
2684    def __init__(self, name, help):
2685        self.name = name
2686        self.help = help
2687
2688    def add_argparser_options(self, parser):
2689        pass
2690
2691    def main(self, args):
2692        return 0
2693
2694
2695class ELFDumpCommand(Command):
2696    def __init__(self):
2697        super(ELFDumpCommand, self).__init__(
2698                'elfdump', help='Dump ELF .dynamic section')
2699
2700    def add_argparser_options(self, parser):
2701        parser.add_argument('path', help='path to an ELF file')
2702
2703    def main(self, args):
2704        try:
2705            ELF.load(args.path).dump()
2706        except ELFError as e:
2707            print('error: {}: Bad ELF file ({})'.format(args.path, e),
2708                  file=sys.stderr)
2709            sys.exit(1)
2710        return 0
2711
2712
2713class CreateGenericRefCommand(Command):
2714    def __init__(self):
2715        super(CreateGenericRefCommand, self).__init__(
2716                'create-generic-ref', help='Create generic references')
2717
2718    def add_argparser_options(self, parser):
2719        parser.add_argument('dir')
2720
2721        parser.add_argument(
2722                '--output', '-o', metavar='PATH', required=True,
2723                help='output directory')
2724
2725    def main(self, args):
2726        root = os.path.abspath(args.dir)
2727        print(root)
2728        prefix_len = len(root) + 1
2729        for path, elf in scan_elf_files(root):
2730            name = path[prefix_len:]
2731            print('Processing:', name, file=sys.stderr)
2732            out = os.path.join(args.output, name) + '.sym'
2733            makedirs(os.path.dirname(out), exist_ok=True)
2734            with open(out, 'w') as f:
2735                elf.dump(f)
2736        return 0
2737
2738
2739class ELFGraphCommand(Command):
2740    def add_argparser_options(self, parser):
2741        parser.add_argument(
2742                '--load-extra-deps', action='append',
2743                help='load extra module dependencies')
2744
2745        parser.add_argument(
2746                '--system', action='append',
2747                help='path to system partition contents')
2748
2749        parser.add_argument(
2750                '--vendor', action='append',
2751                help='path to vendor partition contents')
2752
2753        parser.add_argument(
2754                '--system-dir-as-vendor', action='append',
2755                help='sub directory of system partition that has vendor files')
2756
2757        parser.add_argument(
2758                '--system-dir-ignored', action='append',
2759                help='sub directory of system partition that must be ignored')
2760
2761        parser.add_argument(
2762                '--vendor-dir-as-system', action='append',
2763                help='sub directory of vendor partition that has system files')
2764
2765        parser.add_argument(
2766                '--vendor-dir-ignored', action='append',
2767                help='sub directory of vendor partition that must be ignored')
2768
2769        parser.add_argument(
2770                '--load-generic-refs',
2771                help='compare with generic reference symbols')
2772
2773        parser.add_argument(
2774                '--aosp-system',
2775                help='compare with AOSP generic system image directory')
2776
2777        parser.add_argument('--tag-file', help='lib tag file')
2778
2779    def get_generic_refs_from_args(self, args):
2780        if args.load_generic_refs:
2781            return GenericRefs.create_from_sym_dir(args.load_generic_refs)
2782        if args.aosp_system:
2783            return GenericRefs.create_from_image_dir(args.aosp_system,
2784                                                     '/system')
2785        return None
2786
2787    def _check_arg_dir_exists(self, arg_name, dirs):
2788        for path in dirs:
2789            if not os.path.exists(path):
2790                print('error: Failed to find the directory "{}" specified in {}'
2791                        .format(path, arg_name), file=sys.stderr)
2792                sys.exit(1)
2793            if not os.path.isdir(path):
2794                print('error: Path "{}" specified in {} is not a directory'
2795                        .format(path, arg_name), file=sys.stderr)
2796                sys.exit(1)
2797
2798    def check_dirs_from_args(self, args):
2799        self._check_arg_dir_exists('--system', args.system)
2800        self._check_arg_dir_exists('--vendor', args.vendor)
2801
2802    def create_from_args(self, args):
2803        self.check_dirs_from_args(args)
2804
2805        generic_refs = self.get_generic_refs_from_args(args)
2806
2807        vndk_lib_dirs = VNDKLibDir.create_from_dirs(args.system, args.vendor)
2808
2809        if args.tag_file:
2810            tagged_paths = TaggedPathDict.create_from_csv_path(
2811                    args.tag_file, vndk_lib_dirs)
2812        else:
2813            tagged_paths = None
2814
2815        graph = ELFLinker.create(args.system, args.system_dir_as_vendor,
2816                                 args.system_dir_ignored,
2817                                 args.vendor, args.vendor_dir_as_system,
2818                                 args.vendor_dir_ignored,
2819                                 args.load_extra_deps,
2820                                 generic_refs=generic_refs,
2821                                 tagged_paths=tagged_paths)
2822
2823        return (generic_refs, graph, tagged_paths, vndk_lib_dirs)
2824
2825
2826class VNDKCommandBase(ELFGraphCommand):
2827    def add_argparser_options(self, parser):
2828        super(VNDKCommandBase, self).add_argparser_options(parser)
2829
2830        parser.add_argument('--no-default-dlopen-deps', action='store_true',
2831                help='do not add default dlopen dependencies')
2832
2833        parser.add_argument(
2834                '--action-ineligible-vndk-sp', default='warn',
2835                help='action when a sp-hal uses non-vndk-sp libs '
2836                     '(option: follow,warn,ignore)')
2837
2838        parser.add_argument(
2839                '--action-ineligible-vndk', default='warn',
2840                help='action when a vendor lib/exe uses fwk-only libs '
2841                     '(option: follow,warn,ignore)')
2842
2843    def create_from_args(self, args):
2844        """Create all essential data structures for VNDK computation."""
2845
2846        generic_refs, graph, tagged_paths, vndk_lib_dirs  = \
2847                super(VNDKCommandBase, self).\
2848                create_from_args(args)
2849
2850        if not args.no_default_dlopen_deps:
2851            script_dir = os.path.dirname(os.path.abspath(__file__))
2852            minimum_dlopen_deps = os.path.join(script_dir, 'datasets',
2853                                               'minimum_dlopen_deps.txt')
2854            graph.add_dlopen_deps(minimum_dlopen_deps)
2855
2856        return (generic_refs, graph, tagged_paths, vndk_lib_dirs)
2857
2858
2859class VNDKCommand(VNDKCommandBase):
2860    def __init__(self):
2861        super(VNDKCommand, self).__init__(
2862                'vndk', help='Compute VNDK libraries set')
2863
2864    def add_argparser_options(self, parser):
2865        super(VNDKCommand, self).add_argparser_options(parser)
2866
2867        parser.add_argument(
2868                '--warn-incorrect-partition', action='store_true',
2869                help='warn about libraries only have cross partition linkages')
2870
2871        parser.add_argument(
2872                '--full', action='store_true',
2873                help='print all classification')
2874
2875        parser.add_argument(
2876                '--output-format', default='tag',
2877                help='output format for vndk classification')
2878
2879        parser.add_argument(
2880                '--file-size-output',
2881                help='output file for calculated file sizes')
2882
2883    def _warn_incorrect_partition_lib_set(self, lib_set, partition, error_msg):
2884        for lib in lib_set.values():
2885            if not lib.num_users:
2886                continue
2887            if all((user.partition != partition for user in lib.users_all)):
2888                print(error_msg.format(lib.path), file=sys.stderr)
2889
2890    def _warn_incorrect_partition(self, graph):
2891        self._warn_incorrect_partition_lib_set(
2892                graph.lib_pt[PT_VENDOR], PT_VENDOR,
2893                'warning: {}: This is a vendor library with framework-only '
2894                'usages.')
2895
2896        self._warn_incorrect_partition_lib_set(
2897                graph.lib_pt[PT_SYSTEM], PT_SYSTEM,
2898                'warning: {}: This is a framework library with vendor-only '
2899                'usages.')
2900
2901    @staticmethod
2902    def _extract_simple_vndk_result(vndk_result):
2903        field_name_tags = [
2904            ('vndk_sp', 'vndk_sp'),
2905            ('vndk_sp_unused', 'vndk_sp'),
2906            ('vndk_sp_indirect', 'vndk_sp'),
2907            ('vndk_sp_indirect_unused', 'vndk_sp'),
2908            ('vndk_sp_indirect_private', 'vndk_sp'),
2909
2910            ('vndk_sp_ext', 'vndk_sp_ext'),
2911            ('vndk_sp_indirect_ext', 'vndk_sp_ext'),
2912
2913            ('vndk_ext', 'extra_vendor_libs'),
2914            ('extra_vendor_libs', 'extra_vendor_libs'),
2915        ]
2916        results = SimpleVNDKResult()
2917        for field_name, tag in field_name_tags:
2918            getattr(results, tag).update(getattr(vndk_result, field_name))
2919        return results
2920
2921    def _print_tags(self, vndk_lib, full, file=sys.stdout):
2922        if full:
2923            result_tags = _VNDK_RESULT_FIELD_NAMES
2924            results = vndk_lib
2925        else:
2926            # Simplified VNDK output with only three sets.
2927            result_tags = _SIMPLE_VNDK_RESULT_FIELD_NAMES
2928            results = self._extract_simple_vndk_result(vndk_lib)
2929
2930        for tag in result_tags:
2931            libs = getattr(results, tag)
2932            tag += ':'
2933            for lib in sorted_lib_path_list(libs):
2934                print(tag, lib, file=file)
2935
2936    def _print_make(self, vndk_lib, file=sys.stdout):
2937        def get_module_name(path):
2938            name = os.path.basename(path)
2939            root, ext = os.path.splitext(name)
2940            return root
2941
2942        def get_module_names(lib_set):
2943            return sorted({ get_module_name(lib.path) for lib in lib_set })
2944
2945        results = self._extract_simple_vndk_result(vndk_lib)
2946        vndk_sp = get_module_names(results.vndk_sp)
2947        vndk_sp_ext = get_module_names(results.vndk_sp_ext)
2948        extra_vendor_libs= get_module_names(results.extra_vendor_libs)
2949
2950        def format_module_names(module_names):
2951            return '\\\n    ' +  ' \\\n    '.join(module_names)
2952
2953        script_dir = os.path.dirname(os.path.abspath(__file__))
2954        template_path = os.path.join(script_dir, 'templates', 'vndk.txt')
2955        with open(template_path, 'r') as f:
2956            template = f.read()
2957
2958        template = template.replace('##_VNDK_SP_##',
2959                                    format_module_names(vndk_sp))
2960        template = template.replace('##_VNDK_SP_EXT_##',
2961                                    format_module_names(vndk_sp_ext))
2962        template = template.replace('##_EXTRA_VENDOR_LIBS_##',
2963                                    format_module_names(extra_vendor_libs))
2964
2965        file.write(template)
2966
2967    def _print_file_size_output(self, graph, vndk_lib, file=sys.stderr):
2968        def collect_tags(lib):
2969            tags = []
2970            for field_name in _VNDK_RESULT_FIELD_NAMES:
2971                if lib in getattr(vndk_lib, field_name):
2972                    tags.append(field_name)
2973            return ' '.join(tags)
2974
2975        writer = csv.writer(file, lineterminator='\n')
2976        writer.writerow(('Path', 'Tag', 'File size', 'RO segment file size',
2977                         'RO segment mem size', 'RW segment file size',
2978                         'RW segment mem size'))
2979
2980        # Print the file size of all ELF files.
2981        for lib in sorted(graph.all_libs()):
2982            writer.writerow((lib.path, collect_tags(lib), lib.elf.file_size,
2983                             lib.elf.ro_seg_file_size, lib.elf.ro_seg_mem_size,
2984                             lib.elf.rw_seg_file_size, lib.elf.rw_seg_mem_size))
2985
2986        # Calculate the summation of each sets.
2987        def calc_total_size(lib_set):
2988            total_file_size = 0
2989            total_ro_seg_file_size = 0
2990            total_ro_seg_mem_size = 0
2991            total_rw_seg_file_size = 0
2992            total_rw_seg_mem_size = 0
2993
2994            for lib in lib_set:
2995                total_file_size += lib.elf.file_size
2996                total_ro_seg_file_size += lib.elf.ro_seg_file_size
2997                total_ro_seg_mem_size += lib.elf.ro_seg_mem_size
2998                total_rw_seg_file_size += lib.elf.rw_seg_file_size
2999                total_rw_seg_mem_size += lib.elf.rw_seg_mem_size
3000
3001            return [total_file_size, total_ro_seg_file_size,
3002                    total_ro_seg_mem_size, total_rw_seg_file_size,
3003                    total_rw_seg_mem_size]
3004
3005        SEPARATOR = ('----------', None, None, None, None, None, None)
3006
3007        writer.writerow(SEPARATOR)
3008        for tag in _VNDK_RESULT_FIELD_NAMES:
3009            lib_set = getattr(vndk_lib, tag)
3010            lib_set = [lib for lib in lib_set if lib.elf.is_32bit]
3011            total = calc_total_size(lib_set)
3012            writer.writerow(['Subtotal ' + tag + ' (32-bit)', None] + total)
3013
3014        writer.writerow(SEPARATOR)
3015        for tag in _VNDK_RESULT_FIELD_NAMES:
3016            lib_set = getattr(vndk_lib, tag)
3017            lib_set = [lib for lib in lib_set if not lib.elf.is_32bit]
3018            total = calc_total_size(lib_set)
3019            writer.writerow(['Subtotal ' + tag + ' (64-bit)', None] + total)
3020
3021        writer.writerow(SEPARATOR)
3022        for tag in _VNDK_RESULT_FIELD_NAMES:
3023            total = calc_total_size(getattr(vndk_lib, tag))
3024            writer.writerow(['Subtotal ' + tag + ' (both)', None] + total)
3025
3026        # Calculate the summation of all ELF files.
3027        writer.writerow(SEPARATOR)
3028        writer.writerow(['Total', None] + calc_total_size(graph.all_libs()))
3029
3030    def main(self, args):
3031        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3032                self.create_from_args(args)
3033
3034        if args.warn_incorrect_partition:
3035            self._warn_incorrect_partition(graph)
3036
3037        # Compute vndk heuristics.
3038        vndk_lib = graph.compute_degenerated_vndk(
3039                generic_refs, tagged_paths, args.action_ineligible_vndk_sp,
3040                args.action_ineligible_vndk)
3041
3042        # Print results.
3043        if args.output_format == 'make':
3044            self._print_make(vndk_lib)
3045        else:
3046            self._print_tags(vndk_lib, args.full)
3047
3048        # Calculate and print file sizes.
3049        if args.file_size_output:
3050            with open(args.file_size_output, 'w') as fp:
3051                self._print_file_size_output(graph, vndk_lib, file=fp)
3052        return 0
3053
3054
3055class DepsInsightCommand(VNDKCommandBase):
3056    def __init__(self):
3057        super(DepsInsightCommand, self).__init__(
3058                'deps-insight', help='Generate HTML to show dependencies')
3059
3060    def add_argparser_options(self, parser):
3061        super(DepsInsightCommand, self).add_argparser_options(parser)
3062
3063        parser.add_argument('--module-info')
3064
3065        parser.add_argument(
3066                '--output', '-o', help='output directory')
3067
3068    @staticmethod
3069    def serialize_data(libs, vndk_lib, module_info):
3070        strs = []
3071        strs_dict = dict()
3072
3073        libs.sort(key=lambda lib: lib.path)
3074        libs_dict = {lib: i for i, lib in enumerate(libs)}
3075
3076        def get_str_idx(s):
3077            try:
3078                return strs_dict[s]
3079            except KeyError:
3080                idx = len(strs)
3081                strs_dict[s] = idx
3082                strs.append(s)
3083                return idx
3084
3085        def collect_path_sorted_lib_idxs(libs):
3086            return [libs_dict[lib] for lib in sorted(libs)]
3087
3088        def collect_deps(lib):
3089            queue = list(lib.deps_all)
3090            visited = set(queue)
3091            visited.add(lib)
3092            deps = []
3093
3094            # Traverse dependencies with breadth-first search.
3095            while queue:
3096                # Collect dependencies for next queue.
3097                next_queue = []
3098                for lib in queue:
3099                    for dep in lib.deps_all:
3100                        if dep not in visited:
3101                            next_queue.append(dep)
3102                            visited.add(dep)
3103
3104                # Append current queue to result.
3105                deps.append(collect_path_sorted_lib_idxs(queue))
3106
3107                queue = next_queue
3108
3109            return deps
3110
3111        def collect_source_dir_paths(lib):
3112            return [get_str_idx(path)
3113                    for path in module_info.get_module_path(lib.path)]
3114
3115        def collect_tags(lib):
3116            tags = []
3117            for field_name in _VNDK_RESULT_FIELD_NAMES:
3118                if lib in getattr(vndk_lib, field_name):
3119                    tags.append(get_str_idx(field_name))
3120            return tags
3121
3122        mods = []
3123        for lib in libs:
3124            mods.append([get_str_idx(lib.path),
3125                         32 if lib.elf.is_32bit else 64,
3126                         collect_tags(lib),
3127                         collect_deps(lib),
3128                         collect_path_sorted_lib_idxs(lib.users_all),
3129                         collect_source_dir_paths(lib)])
3130
3131        return (strs, mods)
3132
3133    def main(self, args):
3134        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3135                self.create_from_args(args)
3136
3137        module_info = ModuleInfo.load_from_path_or_default(args.module_info)
3138
3139        # Compute vndk heuristics.
3140        vndk_lib = graph.compute_degenerated_vndk(
3141                generic_refs, tagged_paths, args.action_ineligible_vndk_sp,
3142                args.action_ineligible_vndk)
3143
3144        # Serialize data.
3145        strs, mods = self.serialize_data(list(graph.all_libs()), vndk_lib,
3146                                         module_info)
3147
3148        # Generate output files.
3149        makedirs(args.output, exist_ok=True)
3150        script_dir = os.path.dirname(os.path.abspath(__file__))
3151        for name in ('index.html', 'insight.css', 'insight.js'):
3152            shutil.copyfile(os.path.join(script_dir, 'assets', 'insight', name),
3153                            os.path.join(args.output, name))
3154
3155        with open(os.path.join(args.output, 'insight-data.js'), 'w') as f:
3156            f.write('''(function () {
3157    var strs = ''' + json.dumps(strs) + ''';
3158    var mods = ''' + json.dumps(mods) + ''';
3159    insight.init(document, strs, mods);
3160})();''')
3161
3162        return 0
3163
3164
3165class DepsCommand(ELFGraphCommand):
3166    def __init__(self):
3167        super(DepsCommand, self).__init__(
3168                'deps', help='Print binary dependencies for debugging')
3169
3170    def add_argparser_options(self, parser):
3171        super(DepsCommand, self).add_argparser_options(parser)
3172
3173        parser.add_argument(
3174                '--revert', action='store_true',
3175                help='print usage dependency')
3176
3177        parser.add_argument(
3178                '--leaf', action='store_true',
3179                help='print binaries without dependencies or usages')
3180
3181        parser.add_argument(
3182                '--symbols', action='store_true',
3183                help='print symbols')
3184
3185        parser.add_argument('--module-info')
3186
3187    def main(self, args):
3188        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3189                self.create_from_args(args)
3190
3191        module_info = ModuleInfo.load_from_path_or_default(args.module_info)
3192
3193        results = []
3194        for partition in range(NUM_PARTITIONS):
3195            for name, lib in graph.lib_pt[partition].items():
3196                if args.symbols:
3197                    def collect_symbols(user, definer):
3198                        return user.get_dep_linked_symbols(definer)
3199                else:
3200                    def collect_symbols(user, definer):
3201                        return ()
3202
3203                data = []
3204                if args.revert:
3205                    for assoc_lib in sorted(lib.users_all):
3206                        data.append((assoc_lib.path,
3207                                     collect_symbols(assoc_lib, lib)))
3208                else:
3209                    for assoc_lib in sorted(lib.deps_all):
3210                        data.append((assoc_lib.path,
3211                                     collect_symbols(lib, assoc_lib)))
3212                results.append((name, data))
3213        results.sort()
3214
3215        if args.leaf:
3216            for name, deps in results:
3217                if not deps:
3218                    print(name)
3219        else:
3220            delimiter = ''
3221            for name, assoc_libs in results:
3222                print(delimiter, end='')
3223                delimiter = '\n'
3224
3225                print(name)
3226                for module_path in module_info.get_module_path(name):
3227                    print('\tMODULE_PATH:', module_path)
3228                for assoc_lib, symbols in assoc_libs:
3229                    print('\t' + assoc_lib)
3230                    for module_path in module_info.get_module_path(assoc_lib):
3231                        print('\t\tMODULE_PATH:', module_path)
3232                    for symbol in symbols:
3233                        print('\t\t' + symbol)
3234        return 0
3235
3236
3237class DepsClosureCommand(ELFGraphCommand):
3238    def __init__(self):
3239        super(DepsClosureCommand, self).__init__(
3240                'deps-closure', help='Find transitive closure of dependencies')
3241
3242    def add_argparser_options(self, parser):
3243        super(DepsClosureCommand, self).add_argparser_options(parser)
3244
3245        parser.add_argument('lib', nargs='*',
3246                            help='root set of the shared libraries')
3247
3248        parser.add_argument('--exclude-lib', action='append', default=[],
3249                            help='libraries to be excluded')
3250
3251        parser.add_argument('--exclude-ndk', action='store_true',
3252                            help='exclude ndk libraries')
3253
3254        parser.add_argument('--revert', action='store_true',
3255                            help='print usage dependency')
3256
3257        parser.add_argument('--enumerate', action='store_true',
3258                            help='print closure for each lib instead of union')
3259
3260    def print_deps_closure(self, root_libs, graph, is_excluded_libs,
3261                           is_reverted, indent):
3262        if is_reverted:
3263            closure = graph.compute_users_closure(root_libs, is_excluded_libs)
3264        else:
3265            closure = graph.compute_deps_closure(root_libs, is_excluded_libs)
3266
3267        for lib in sorted_lib_path_list(closure):
3268            print(indent + lib)
3269
3270
3271    def main(self, args):
3272        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3273                self.create_from_args(args)
3274
3275        # Find root/excluded libraries by their paths.
3276        def report_error(path):
3277            print('error: no such lib: {}'.format(path), file=sys.stderr)
3278        root_libs = graph.get_libs(args.lib, report_error)
3279        excluded_libs = graph.get_libs(args.exclude_lib, report_error)
3280
3281        # Define the exclusion filter.
3282        if args.exclude_ndk:
3283            def is_excluded_libs(lib):
3284                return lib.is_ll_ndk or lib in excluded_libs
3285        else:
3286            def is_excluded_libs(lib):
3287                return lib in excluded_libs
3288
3289        if not args.enumerate:
3290            self.print_deps_closure(root_libs, graph, is_excluded_libs,
3291                                    args.revert, '')
3292        else:
3293            if not root_libs:
3294                root_libs = list(graph.all_libs())
3295            for lib in sorted(root_libs):
3296                print(lib.path)
3297                self.print_deps_closure({lib}, graph, is_excluded_libs,
3298                                        args.revert, '\t')
3299        return 0
3300
3301
3302class DepsUnresolvedCommand(ELFGraphCommand):
3303    def __init__(self):
3304        super(DepsUnresolvedCommand, self).__init__(
3305                'deps-unresolved',
3306                help='Show unresolved dt_needed entries or symbols')
3307
3308    def add_argparser_options(self, parser):
3309        super(DepsUnresolvedCommand, self).add_argparser_options(parser)
3310        parser.add_argument('--module-info')
3311        parser.add_argument('--path-filter')
3312
3313    def _dump_unresolved(self, lib, module_info, delimiter):
3314        if not lib.unresolved_symbols and not lib.unresolved_dt_needed:
3315            return
3316
3317        print(delimiter, end='')
3318        print(lib.path)
3319        for module_path in module_info.get_module_path(lib.path):
3320            print('\tMODULE_PATH:', module_path)
3321        for dt_needed in sorted(lib.unresolved_dt_needed):
3322            print('\tUNRESOLVED_DT_NEEDED:', dt_needed)
3323        for symbol in sorted(lib.unresolved_symbols):
3324            print('\tUNRESOLVED_SYMBOL:', symbol)
3325
3326    def main(self, args):
3327        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3328                self.create_from_args(args)
3329        module_info = ModuleInfo.load_from_path_or_default(args.module_info)
3330
3331        libs = graph.all_libs()
3332        if args.path_filter:
3333            path_filter = re.compile(args.path_filter)
3334            libs = [lib for lib in libs if path_filter.match(lib.path)]
3335
3336        delimiter = ''
3337        for lib in sorted(libs):
3338            self._dump_unresolved(lib, module_info, delimiter)
3339            delimiter = '\n'
3340
3341
3342class ApkDepsCommand(ELFGraphCommand):
3343    def __init__(self):
3344        super(ApkDepsCommand, self).__init__(
3345                'apk-deps', help='Print APK dependencies for debugging')
3346
3347    def add_argparser_options(self, parser):
3348        super(ApkDepsCommand, self).add_argparser_options(parser)
3349
3350    def main(self, args):
3351        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3352                self.create_from_args(args)
3353
3354        apk_deps = scan_apk_dep(graph, args.system, args.vendor)
3355
3356        for apk_path, dep_paths in apk_deps:
3357            print(apk_path)
3358            for dep_path in dep_paths:
3359                print('\t' + dep_path)
3360
3361        return 0
3362
3363
3364class CheckDepCommandBase(ELFGraphCommand):
3365    def __init__(self, *args, **kwargs):
3366        super(CheckDepCommandBase, self).__init__(*args, **kwargs)
3367        self.delimiter = ''
3368
3369    def add_argparser_options(self, parser):
3370        super(CheckDepCommandBase, self).add_argparser_options(parser)
3371        parser.add_argument('--module-info')
3372
3373    def _print_delimiter(self):
3374        print(self.delimiter, end='')
3375        self.delimiter = '\n'
3376
3377    def _dump_dep(self, lib, bad_deps, module_info):
3378        self._print_delimiter()
3379        print(lib.path)
3380        for module_path in module_info.get_module_path(lib.path):
3381            print('\tMODULE_PATH:', module_path)
3382        for dep in sorted(bad_deps):
3383            print('\t' + dep.path)
3384            for module_path in module_info.get_module_path(dep.path):
3385                print('\t\tMODULE_PATH:', module_path)
3386            for symbol in lib.get_dep_linked_symbols(dep):
3387                print('\t\t' + symbol)
3388
3389    def _dump_apk_dep(self, apk_path, bad_deps, module_info):
3390        self._print_delimiter()
3391        print(apk_path)
3392        for module_path in module_info.get_module_path(apk_path):
3393            print('\tMODULE_PATH:', module_path)
3394        for dep_path in sorted(bad_deps):
3395            print('\t' + dep_path)
3396            for module_path in module_info.get_module_path(dep_path):
3397                print('\t\tMODULE_PATH:', module_path)
3398
3399
3400class CheckDepCommand(CheckDepCommandBase):
3401    def __init__(self):
3402        super(CheckDepCommand, self).__init__(
3403                'check-dep', help='Check the eligible dependencies')
3404
3405
3406    def add_argparser_options(self, parser):
3407        super(CheckDepCommand, self).add_argparser_options(parser)
3408
3409        group = parser.add_mutually_exclusive_group()
3410
3411        group.add_argument('--check-apk', action='store_true', default=False,
3412                           help='Check JNI dependencies in APK files')
3413
3414        group.add_argument('--no-check-apk', action='store_false',
3415                           dest='check_apk',
3416                           help='Do not check JNI dependencies in APK files')
3417
3418        group = parser.add_mutually_exclusive_group()
3419
3420        group.add_argument('--check-dt-needed-ordering',
3421                           action='store_true', default=False,
3422                           help='Check ordering of DT_NEEDED entries')
3423
3424        group.add_argument('--no-check-dt-needed-ordering',
3425                           action='store_false',
3426                           dest='check_dt_needed_ordering',
3427                           help='Do not check ordering of DT_NEEDED entries')
3428
3429
3430    def _check_vendor_dep(self, graph, tagged_libs, lib_properties,
3431                          module_info):
3432        """Check whether vendor libs are depending on non-eligible libs."""
3433        num_errors = 0
3434
3435        vendor_libs = set(graph.lib_pt[PT_VENDOR].values())
3436
3437        eligible_libs = (tagged_libs.ll_ndk | tagged_libs.vndk_sp |
3438                         tagged_libs.vndk_sp_indirect | tagged_libs.vndk)
3439
3440        for lib in sorted(vendor_libs):
3441            bad_deps = set()
3442
3443            # Check whether vendor modules depend on extended NDK symbols.
3444            for dep, symbols in lib.imported_ext_symbols.items():
3445                if dep.is_ll_ndk:
3446                    num_errors += 1
3447                    bad_deps.add(dep)
3448                    for symbol in symbols:
3449                        print('error: vendor lib "{}" depends on extended '
3450                              'NDK symbol "{}" from "{}".'
3451                              .format(lib.path, symbol, dep.path),
3452                              file=sys.stderr)
3453
3454            # Check whether vendor modules depend on ineligible libs.
3455            for dep in lib.deps_all:
3456                if dep not in vendor_libs and dep not in eligible_libs:
3457                    num_errors += 1
3458                    bad_deps.add(dep)
3459
3460                    dep_name = os.path.splitext(os.path.basename(dep.path))[0]
3461                    dep_properties = lib_properties.get(dep_name)
3462                    if not dep_properties.vendor_available:
3463                        print('error: vendor lib "{}" depends on non-eligible '
3464                              'lib "{}".'.format(lib.path, dep.path),
3465                              file=sys.stderr)
3466                    elif dep_properties.vndk_sp:
3467                        print('error: vendor lib "{}" depends on vndk-sp "{}" '
3468                              'but it must be copied to '
3469                              '/system/lib[64]/vndk-sp.'
3470                              .format(lib.path, dep.path),
3471                              file=sys.stderr)
3472                    elif dep_properties.vndk:
3473                        print('error: vendor lib "{}" depends on vndk "{}" but '
3474                              'it must be copied to /system/lib[64]/vndk.'
3475                              .format(lib.path, dep.path),
3476                              file=sys.stderr)
3477                    else:
3478                        print('error: vendor lib "{}" depends on '
3479                              'vendor_available "{}" but it must be copied to '
3480                              '/vendor/lib[64].'.format(lib.path, dep.path),
3481                              file=sys.stderr)
3482
3483            if bad_deps:
3484                self._dump_dep(lib, bad_deps, module_info)
3485
3486        return num_errors
3487
3488
3489    def _check_dt_needed_ordering(self, graph, module_info):
3490        """Check DT_NEEDED entries order of all libraries"""
3491
3492        num_errors = 0
3493
3494        def _is_libc_prior_to_libdl(lib):
3495            dt_needed = lib.elf.dt_needed
3496            try:
3497                return dt_needed.index('libc.so') < dt_needed.index('libdl.so')
3498            except ValueError:
3499                return True
3500
3501        for lib in sorted(graph.all_libs()):
3502            if _is_libc_prior_to_libdl(lib):
3503                continue
3504
3505            print('error: The ordering of DT_NEEDED entries in "{}" may be '
3506                  'problematic.  libc.so must be prior to libdl.so.  '
3507                  'But found: {}.'
3508                  .format(lib.path, lib.elf.dt_needed), file=sys.stderr)
3509
3510            num_errors += 1
3511
3512        return num_errors
3513
3514
3515    def _check_apk_dep(self, graph, system_dirs, vendor_dirs, module_info):
3516        num_errors = 0
3517
3518        def is_in_system_partition(path):
3519            return path.startswith('/system/') or \
3520                   path.startswith('/product/') or \
3521                   path.startswith('/oem/')
3522
3523        apk_deps = scan_apk_dep(graph, system_dirs, vendor_dirs)
3524
3525        for apk_path, dep_paths in apk_deps:
3526            apk_in_system = is_in_system_partition(apk_path)
3527            bad_deps = []
3528            for dep_path in dep_paths:
3529                dep_in_system = is_in_system_partition(dep_path)
3530                if apk_in_system != dep_in_system:
3531                    bad_deps.append(dep_path)
3532                    print('error: apk "{}" has cross-partition dependency '
3533                          'lib "{}".'.format(apk_path, dep_path),
3534                          file=sys.stderr)
3535                    num_errors += 1
3536            if bad_deps:
3537                self._dump_apk_dep(apk_path, sorted(bad_deps), module_info)
3538        return num_errors
3539
3540
3541    def main(self, args):
3542        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3543                self.create_from_args(args)
3544
3545        tagged_paths = TaggedPathDict.create_from_csv_path(
3546                args.tag_file, vndk_lib_dirs)
3547        tagged_libs = TaggedLibDict.create_from_graph(
3548                graph, tagged_paths, generic_refs)
3549
3550        module_info = ModuleInfo.load_from_path_or_default(args.module_info)
3551
3552        lib_properties_path = \
3553                LibProperties.get_lib_properties_file_path(args.tag_file)
3554        lib_properties = \
3555                LibProperties.load_from_path_or_default(lib_properties_path)
3556
3557        num_errors = self._check_vendor_dep(graph, tagged_libs, lib_properties,
3558                                            module_info)
3559
3560        if args.check_dt_needed_ordering:
3561            num_errors += self._check_dt_needed_ordering(graph, module_info)
3562
3563        if args.check_apk:
3564            num_errors += self._check_apk_dep(graph, args.system, args.vendor,
3565                                              module_info)
3566
3567        return 0 if num_errors == 0 else 1
3568
3569
3570class CheckEligibleListCommand(CheckDepCommandBase):
3571    def __init__(self):
3572        super(CheckEligibleListCommand, self).__init__(
3573                'check-eligible-list', help='Check the eligible list')
3574
3575
3576    def _check_eligible_vndk_dep(self, graph, tagged_libs, module_info):
3577        """Check whether eligible sets are self-contained."""
3578        num_errors = 0
3579
3580        indirect_libs = (tagged_libs.ll_ndk_indirect |
3581                         tagged_libs.vndk_sp_indirect_private |
3582                         tagged_libs.fwk_only_rs)
3583
3584        eligible_libs = (tagged_libs.ll_ndk | tagged_libs.vndk_sp |
3585                         tagged_libs.vndk_sp_indirect | tagged_libs.vndk)
3586
3587        # Check eligible vndk is self-contained.
3588        for lib in sorted(eligible_libs):
3589            bad_deps = []
3590            for dep in lib.deps_all:
3591                if dep not in eligible_libs and dep not in indirect_libs:
3592                    print('error: eligible lib "{}" should not depend on '
3593                          'non-eligible lib "{}".'.format(lib.path, dep.path),
3594                          file=sys.stderr)
3595                    bad_deps.append(dep)
3596                    num_errors += 1
3597            if bad_deps:
3598                self._dump_dep(lib, bad_deps, module_info)
3599
3600        # Check the libbinder dependencies.
3601        for lib in sorted(eligible_libs):
3602            bad_deps = []
3603            for dep in lib.deps_all:
3604                if os.path.basename(dep.path) == 'libbinder.so':
3605                    print('error: eligible lib "{}" should not depend on '
3606                          'libbinder.so.'.format(lib.path), file=sys.stderr)
3607                    bad_deps.append(dep)
3608                    num_errors += 1
3609            if bad_deps:
3610                self._dump_dep(lib, bad_deps, module_info)
3611
3612        return num_errors
3613
3614
3615    def main(self, args):
3616        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3617                self.create_from_args(args)
3618
3619        tagged_paths = TaggedPathDict.create_from_csv_path(
3620                args.tag_file, vndk_lib_dirs)
3621        tagged_libs = TaggedLibDict.create_from_graph(
3622                graph, tagged_paths, generic_refs)
3623
3624        module_info = ModuleInfo.load_from_path_or_default(args.module_info)
3625
3626        num_errors = self._check_eligible_vndk_dep(graph, tagged_libs,
3627                                                   module_info)
3628        return 0 if num_errors == 0 else 1
3629
3630
3631class DepGraphCommand(ELFGraphCommand):
3632    def __init__(self):
3633        super(DepGraphCommand, self).__init__(
3634                'dep-graph', help='Show the eligible dependencies graph')
3635
3636    def add_argparser_options(self, parser):
3637        super(DepGraphCommand, self).add_argparser_options(parser)
3638
3639        parser.add_argument('--output', '-o', help='output directory')
3640
3641    def _get_tag_from_lib(self, lib, tagged_paths):
3642        tag_hierarchy = dict()
3643        for tag in TaggedPathDict.TAGS:
3644            if tag in {'sp_hal', 'sp_hal_dep', 'vnd_only'}:
3645                tag_hierarchy[tag] = 'vendor.private.{}'.format(tag)
3646            else:
3647                vendor_visible = TaggedPathDict.is_tag_visible('vnd_only', tag)
3648                pub = 'public' if vendor_visible else 'private'
3649                tag_hierarchy[tag] = 'system.{}.{}'.format(pub, tag)
3650
3651        return tag_hierarchy[tagged_paths.get_path_tag(lib.path)]
3652
3653    def _check_if_allowed(self, my_tag, other_tag):
3654        my = my_tag.split('.')
3655        other = other_tag.split('.')
3656        if my[0] == 'system' and other[0] == 'vendor':
3657            return False
3658        if my[0] == 'vendor' and other[0] == 'system' \
3659                             and other[1] == 'private':
3660            return False
3661        return True
3662
3663    def _get_dep_graph(self, graph, tagged_paths):
3664        data = []
3665        violate_libs = dict()
3666        system_libs = graph.lib_pt[PT_SYSTEM].values()
3667        vendor_libs = graph.lib_pt[PT_VENDOR].values()
3668        for lib in itertools.chain(system_libs, vendor_libs):
3669            tag = self._get_tag_from_lib(lib, tagged_paths)
3670            violate_count = 0
3671            lib_item = {
3672                'name': lib.path,
3673                'tag': tag,
3674                'depends': [],
3675                'violates': [],
3676            }
3677            for dep in lib.deps_all:
3678                if self._check_if_allowed(tag,
3679                        self._get_tag_from_lib(dep, tagged_paths)):
3680                    lib_item['depends'].append(dep.path)
3681                else:
3682                    lib_item['violates'].append([dep.path, lib.get_dep_linked_symbols(dep)])
3683                    violate_count += 1;
3684            lib_item['violate_count'] = violate_count
3685            if violate_count > 0:
3686                if not tag in violate_libs:
3687                    violate_libs[tag] = []
3688                violate_libs[tag].append((lib.path, violate_count))
3689            data.append(lib_item)
3690        return data, violate_libs
3691
3692    def main(self, args):
3693        generic_refs, graph, tagged_paths, vndk_lib_dirs = \
3694                self.create_from_args(args)
3695
3696        tagged_paths = TaggedPathDict.create_from_csv_path(
3697                args.tag_file, vndk_lib_dirs)
3698        data, violate_libs = self._get_dep_graph(graph, tagged_paths)
3699        data.sort(key=lambda lib_item: (lib_item['tag'],
3700                                        lib_item['violate_count']))
3701        for libs in violate_libs.values():
3702            libs.sort(key=lambda libs: libs[1], reverse=True)
3703
3704        makedirs(args.output, exist_ok=True)
3705        script_dir = os.path.dirname(os.path.abspath(__file__))
3706        for name in ('index.html', 'dep-graph.js', 'dep-graph.css'):
3707            shutil.copyfile(os.path.join(script_dir, 'assets', 'visual', name),
3708                            os.path.join(args.output, name))
3709        with open(os.path.join(args.output, 'dep-data.js'), 'w') as f:
3710            f.write('var violatedLibs = ' + json.dumps(violate_libs) +
3711                    '\nvar depData = ' + json.dumps(data) + ';')
3712
3713        return 0
3714
3715
3716def main():
3717    parser = argparse.ArgumentParser()
3718    subparsers = parser.add_subparsers(dest='subcmd')
3719    subcmds = dict()
3720
3721    def register_subcmd(cmd):
3722        subcmds[cmd.name] = cmd
3723        cmd.add_argparser_options(
3724                subparsers.add_parser(cmd.name, help=cmd.help))
3725
3726    register_subcmd(ELFDumpCommand())
3727    register_subcmd(CreateGenericRefCommand())
3728    register_subcmd(VNDKCommand())
3729    register_subcmd(DepsCommand())
3730    register_subcmd(DepsClosureCommand())
3731    register_subcmd(DepsInsightCommand())
3732    register_subcmd(DepsUnresolvedCommand())
3733    register_subcmd(ApkDepsCommand())
3734    register_subcmd(CheckDepCommand())
3735    register_subcmd(CheckEligibleListCommand())
3736    register_subcmd(DepGraphCommand())
3737
3738    args = parser.parse_args()
3739    if not args.subcmd:
3740        parser.print_help()
3741        sys.exit(1)
3742    return subcmds[args.subcmd].main(args)
3743
3744if __name__ == '__main__':
3745    sys.exit(main())
3746