1#!/usr/bin/env python3
2
3# Copyright 2023 Google LLC
4# SPDX-License-Identifier: Apache-2.0
5
6"""
7Checks the initialization priorities
8
9This script parses a Zephyr executable file, creates a list of known devices
10and their effective initialization priorities and compares that with the device
11dependencies inferred from the devicetree hierarchy.
12
13This can be used to detect devices that are initialized in the incorrect order,
14but also devices that are initialized at the same priority but depends on each
15other, which can potentially break if the linking order is changed.
16
17Optionally, it can also produce a human readable list of the initialization
18calls for the various init levels.
19"""
20
21import argparse
22import logging
23import os
24import pathlib
25import pickle
26import sys
27
28from elftools.elf.elffile import ELFFile
29from elftools.elf.sections import SymbolTableSection
30
31# This is needed to load edt.pickle files.
32sys.path.insert(0, os.path.join(os.path.dirname(__file__), "..",
33                                "dts", "python-devicetree", "src"))
34from devicetree import edtlib  # pylint: disable=unused-import
35
36# Prefix used for "struct device" reference initialized based on devicetree
37# entries with a known ordinal.
38_DEVICE_ORD_PREFIX = "__device_dts_ord_"
39
40# Defined init level in order of priority.
41_DEVICE_INIT_LEVELS = ["EARLY", "PRE_KERNEL_1", "PRE_KERNEL_2", "POST_KERNEL",
42                      "APPLICATION", "SMP"]
43
44# List of compatibles for nodes where we don't check the priority.
45_IGNORE_COMPATIBLES = frozenset([
46        # There is no direct dependency between the CDC ACM UART and the USB
47        # device controller, the logical connection is established after USB
48        # device support is enabled.
49        "zephyr,cdc-acm-uart",
50        ])
51
52# The offset of the init pointer in "struct device", in number of pointers.
53DEVICE_INIT_OFFSET = 5
54
55class Priority:
56    """Parses and holds a device initialization priority.
57
58    The object can be used for comparing levels with one another.
59
60    Attributes:
61        name: the section name
62    """
63    def __init__(self, level, priority):
64        for idx, level_name in enumerate(_DEVICE_INIT_LEVELS):
65            if level_name == level:
66                self._level = idx
67                self._priority = priority
68                # Tuples compare elementwise in order
69                self._level_priority = (self._level, self._priority)
70                return
71
72        raise ValueError("Unknown level in %s" % level)
73
74    def __repr__(self):
75        return "<%s %s %d>" % (self.__class__.__name__,
76                               _DEVICE_INIT_LEVELS[self._level], self._priority)
77
78    def __str__(self):
79        return "%s+%d" % (_DEVICE_INIT_LEVELS[self._level], self._priority)
80
81    def __lt__(self, other):
82        return self._level_priority < other._level_priority
83
84    def __eq__(self, other):
85        return self._level_priority == other._level_priority
86
87    def __hash__(self):
88        return self._level_priority
89
90
91class ZephyrInitLevels:
92    """Load an executable file and find the initialization calls and devices.
93
94    Load a Zephyr executable file and scan for the list of initialization calls
95    and defined devices.
96
97    The list of devices is available in the "devices" class variable in the
98    {ordinal: Priority} format, the list of initilevels is in the "initlevels"
99    class variables in the {"level name": ["call", ...]} format.
100
101    Attributes:
102        file_path: path of the file to be loaded.
103    """
104    def __init__(self, file_path, elf_file):
105        self.file_path = file_path
106        self._elf = ELFFile(elf_file)
107        self._load_objects()
108        self._load_level_addr()
109        self._process_initlevels()
110
111    def _load_objects(self):
112        """Initialize the object table."""
113        self._objects = {}
114        self._object_addr = {}
115
116        for section in self._elf.iter_sections():
117            if not isinstance(section, SymbolTableSection):
118                continue
119
120            for sym in section.iter_symbols():
121                if (sym.name and
122                    sym.entry.st_size > 0 and
123                    sym.entry.st_info.type in ["STT_OBJECT", "STT_FUNC"]):
124                    self._objects[sym.entry.st_value] = (
125                            sym.name, sym.entry.st_size, sym.entry.st_shndx)
126                    self._object_addr[sym.name] = sym.entry.st_value
127
128    def _load_level_addr(self):
129        """Find the address associated with known init levels."""
130        self._init_level_addr = {}
131
132        for section in self._elf.iter_sections():
133            if not isinstance(section, SymbolTableSection):
134                continue
135
136            for sym in section.iter_symbols():
137                for level in _DEVICE_INIT_LEVELS:
138                    name = f"__init_{level}_start"
139                    if sym.name == name:
140                        self._init_level_addr[level] = sym.entry.st_value
141                    elif sym.name == "__init_end":
142                        self._init_level_end = sym.entry.st_value
143
144        if len(self._init_level_addr) != len(_DEVICE_INIT_LEVELS):
145            raise ValueError(f"Missing init symbols, found: {self._init_level_addr}")
146
147        if not self._init_level_end:
148            raise ValueError(f"Missing init section end symbol")
149
150    def _device_ord_from_name(self, sym_name):
151        """Find a device ordinal from a symbol name."""
152        if not sym_name:
153            return None
154
155        if not sym_name.startswith(_DEVICE_ORD_PREFIX):
156            return None
157
158        _, device_ord = sym_name.split(_DEVICE_ORD_PREFIX)
159        return int(device_ord)
160
161    def _object_name(self, addr):
162        if not addr:
163            return "NULL"
164        elif addr in self._objects:
165            return self._objects[addr][0]
166        else:
167            return "unknown"
168
169    def _initlevel_pointer(self, addr, idx, shidx):
170        elfclass = self._elf.elfclass
171        if elfclass == 32:
172            ptrsize = 4
173        elif elfclass == 64:
174            ptrsize = 8
175        else:
176            raise ValueError(f"Unknown pointer size for ELF class f{elfclass}")
177
178        section = self._elf.get_section(shidx)
179        start = section.header.sh_addr
180        data = section.data()
181
182        offset = addr - start
183
184        start = offset + ptrsize * idx
185        stop = offset + ptrsize * (idx + 1)
186
187        return int.from_bytes(data[start:stop], byteorder="little")
188
189    def _process_initlevels(self):
190        """Process the init level and find the init functions and devices."""
191        self.devices = {}
192        self.initlevels = {}
193
194        for i, level in enumerate(_DEVICE_INIT_LEVELS):
195            start = self._init_level_addr[level]
196            if i + 1 == len(_DEVICE_INIT_LEVELS):
197                stop = self._init_level_end
198            else:
199                stop = self._init_level_addr[_DEVICE_INIT_LEVELS[i + 1]]
200
201            self.initlevels[level] = []
202
203            priority = 0
204            addr = start
205            while addr < stop:
206                if addr not in self._objects:
207                    raise ValueError(f"no symbol at addr {addr:08x}")
208                obj, size, shidx = self._objects[addr]
209
210                arg0_name = self._object_name(self._initlevel_pointer(addr, 0, shidx))
211                arg1_name = self._object_name(self._initlevel_pointer(addr, 1, shidx))
212
213                ordinal = self._device_ord_from_name(arg1_name)
214                if ordinal:
215                    dev_addr = self._object_addr[arg1_name]
216                    _, _, shidx = self._objects[dev_addr]
217                    arg0_name = self._object_name(self._initlevel_pointer(
218                        dev_addr, DEVICE_INIT_OFFSET, shidx))
219
220                    prio = Priority(level, priority)
221                    self.devices[ordinal] = (prio, arg0_name)
222
223                self.initlevels[level].append(f"{obj}: {arg0_name}({arg1_name})")
224
225                addr += size
226                priority += 1
227
228class Validator():
229    """Validates the initialization priorities.
230
231    Scans through a build folder for object files and list all the device
232    initialization priorities. Then compares that against the EDT derived
233    dependency list and log any found priority issue.
234
235    Attributes:
236        elf_file_path: path of the ELF file
237        edt_pickle: name of the EDT pickle file
238        log: a logging.Logger object
239    """
240    def __init__(self, elf_file_path, edt_pickle, log, elf_file):
241        self.log = log
242
243        edt_pickle_path = pathlib.Path(
244                pathlib.Path(elf_file_path).parent,
245                edt_pickle)
246        with open(edt_pickle_path, "rb") as f:
247            edt = pickle.load(f)
248
249        self._ord2node = edt.dep_ord2node
250
251        self._obj = ZephyrInitLevels(elf_file_path, elf_file)
252
253        self.errors = 0
254
255    def _check_dep(self, dev_ord, dep_ord):
256        """Validate the priority between two devices."""
257        if dev_ord == dep_ord:
258            return
259
260        dev_node = self._ord2node[dev_ord]
261        dep_node = self._ord2node[dep_ord]
262
263        if dev_node._binding:
264            dev_compat = dev_node._binding.compatible
265            if dev_compat in _IGNORE_COMPATIBLES:
266                self.log.info(f"Ignoring priority: {dev_node._binding.compatible}")
267                return
268
269        dev_prio, dev_init = self._obj.devices.get(dev_ord, (None, None))
270        dep_prio, dep_init = self._obj.devices.get(dep_ord, (None, None))
271
272        if not dev_prio or not dep_prio:
273            return
274
275        if dev_prio == dep_prio:
276            raise ValueError(f"{dev_node.path} and {dep_node.path} have the "
277                             f"same priority: {dev_prio}")
278        elif dev_prio < dep_prio:
279            if not self.errors:
280                self.log.error("Device initialization priority validation failed, "
281                               "the sequence of initialization calls does not match "
282                               "the devicetree dependencies.")
283            self.errors += 1
284            self.log.error(
285                    f"{dev_node.path} <{dev_init}> is initialized before its dependency "
286                    f"{dep_node.path} <{dep_init}> ({dev_prio} < {dep_prio})")
287        else:
288            self.log.info(
289                    f"{dev_node.path} <{dev_init}> {dev_prio} > "
290                    f"{dep_node.path} <{dep_init}> {dep_prio}")
291
292    def check_edt(self):
293        """Scan through all known devices and validate the init priorities."""
294        for dev_ord in self._obj.devices:
295            dev = self._ord2node[dev_ord]
296            for dep in dev.depends_on:
297                self._check_dep(dev_ord, dep.dep_ordinal)
298
299    def print_initlevels(self):
300        for level, calls in self._obj.initlevels.items():
301            print(level)
302            for call in calls:
303                print(f"  {call}")
304
305def _parse_args(argv):
306    """Parse the command line arguments."""
307    parser = argparse.ArgumentParser(
308        description=__doc__,
309        formatter_class=argparse.RawDescriptionHelpFormatter,
310        allow_abbrev=False)
311
312    parser.add_argument("-f", "--elf-file", default=pathlib.Path("build", "zephyr", "zephyr.elf"),
313                        help="ELF file to use")
314    parser.add_argument("-v", "--verbose", action="count",
315                        help=("enable verbose output, can be used multiple times "
316                              "to increase verbosity level"))
317    parser.add_argument("--always-succeed", action="store_true",
318                        help="always exit with a return code of 0, used for testing")
319    parser.add_argument("-o", "--output",
320                        help="write the output to a file in addition to stdout")
321    parser.add_argument("-i", "--initlevels", action="store_true",
322                        help="print the initlevel functions instead of checking the device dependencies")
323    parser.add_argument("--edt-pickle", default=pathlib.Path("edt.pickle"),
324                        help="name of the pickled edtlib.EDT file",
325                        type=pathlib.Path)
326
327    return parser.parse_args(argv)
328
329def _init_log(verbose, output):
330    """Initialize a logger object."""
331    log = logging.getLogger(__file__)
332
333    console = logging.StreamHandler()
334    console.setFormatter(logging.Formatter("%(levelname)s: %(message)s"))
335    log.addHandler(console)
336
337    if output:
338        file = logging.FileHandler(output, mode="w")
339        file.setFormatter(logging.Formatter("%(levelname)s: %(message)s"))
340        log.addHandler(file)
341
342    if verbose and verbose > 1:
343        log.setLevel(logging.DEBUG)
344    elif verbose and verbose > 0:
345        log.setLevel(logging.INFO)
346    else:
347        log.setLevel(logging.WARNING)
348
349    return log
350
351def main(argv=None):
352    args = _parse_args(argv)
353
354    log = _init_log(args.verbose, args.output)
355
356    log.info(f"check_init_priorities: {args.elf_file}")
357
358    with open(args.elf_file, "rb") as elf_file:
359        validator = Validator(args.elf_file, args.edt_pickle, log, elf_file)
360        if args.initlevels:
361            validator.print_initlevels()
362        else:
363            validator.check_edt()
364
365        if args.always_succeed:
366            return 0
367
368        if validator.errors:
369            return 1
370
371    return 0
372
373if __name__ == "__main__":
374    sys.exit(main(sys.argv[1:]))
375