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__), "..", "dts", "python-devicetree", "src"))
33from devicetree import edtlib  # noqa: F401
34
35# Prefix used for "struct device" reference initialized based on devicetree
36# entries with a known ordinal.
37_DEVICE_ORD_PREFIX = "__device_dts_ord_"
38
39# Defined init level in order of priority.
40_DEVICE_INIT_LEVELS = ["EARLY", "PRE_KERNEL_1", "PRE_KERNEL_2", "POST_KERNEL", "APPLICATION", "SMP"]
41
42# List of compatibles for nodes where we don't check the priority.
43_IGNORE_COMPATIBLES = frozenset(
44    [
45        # There is no direct dependency between the CDC ACM UART and the USB
46        # device controller, the logical connection is established after USB
47        # device support is enabled.
48        "zephyr,cdc-acm-uart",
49    ]
50)
51
52# Deferred initialization property name.
53# When present, the device is not initialized during boot.
54# (it is evaluated as if initializing "after everything else")
55_DEFERRED_INIT_PROP_NAME = "zephyr,deferred-init"
56
57# The offset of the init pointer in "struct device", in number of pointers.
58DEVICE_INIT_OFFSET = 5
59
60
61class Priority:
62    """Parses and holds a device initialization priority.
63
64    The object can be used for comparing levels with one another.
65
66    Attributes:
67        name: the section name
68    """
69
70    def __init__(self, level: str, priority: int):
71        for idx, level_name in enumerate(_DEVICE_INIT_LEVELS):
72            if level_name == level:
73                self._level = idx
74                self._priority = priority
75                # Tuples compare elementwise in order
76                self._level_priority = (self._level, self._priority)
77                return
78
79        raise ValueError(f"Unknown level in {level}")
80
81    def __repr__(self):
82        level = _DEVICE_INIT_LEVELS[self._level]
83        return f"<{self.__class__.__name__} {level} {self._priority}>"
84
85    def __str__(self):
86        level = _DEVICE_INIT_LEVELS[self._level]
87        return f"{level}+{self._priority}"
88
89    def __lt__(self, other):
90        return self._level_priority < other._level_priority
91
92    def __eq__(self, other):
93        return self._level_priority == other._level_priority
94
95    def __hash__(self):
96        return self._level_priority
97
98
99class ZephyrInitLevels:
100    """Load an executable file and find the initialization calls and devices.
101
102    Load a Zephyr executable file and scan for the list of initialization calls
103    and defined devices.
104
105    The list of devices is available in the "devices" class variable in the
106    {ordinal: Priority} format, the list of initilevels is in the "initlevels"
107    class variables in the {"level name": ["call", ...]} format.
108
109    Attributes:
110        file_path: path of the file to be loaded.
111    """
112
113    def __init__(self, file_path, elf_file):
114        self.file_path = file_path
115        self._elf = ELFFile(elf_file)
116        self._load_objects()
117        self._load_level_addr()
118        self._process_initlevels()
119
120    def _load_objects(self):
121        """Initialize the object table."""
122        self._objects = {}
123        self._object_addr = {}
124
125        for section in self._elf.iter_sections():
126            if not isinstance(section, SymbolTableSection):
127                continue
128
129            for sym in section.iter_symbols():
130                if (
131                    sym.name
132                    and sym.entry.st_size > 0
133                    and sym.entry.st_info.type in ["STT_OBJECT", "STT_FUNC"]
134                ):
135                    self._objects[sym.entry.st_value] = (
136                        sym.name,
137                        sym.entry.st_size,
138                        sym.entry.st_shndx,
139                    )
140                    self._object_addr[sym.name] = sym.entry.st_value
141
142    def _load_level_addr(self):
143        """Find the address associated with known init levels."""
144        self._init_level_addr = {}
145
146        for section in self._elf.iter_sections():
147            if not isinstance(section, SymbolTableSection):
148                continue
149
150            for sym in section.iter_symbols():
151                for level in _DEVICE_INIT_LEVELS:
152                    name = f"__init_{level}_start"
153                    if sym.name == name:
154                        self._init_level_addr[level] = sym.entry.st_value
155                    elif sym.name == "__init_end":
156                        self._init_level_end = sym.entry.st_value
157
158        if len(self._init_level_addr) != len(_DEVICE_INIT_LEVELS):
159            raise ValueError(f"Missing init symbols, found: {self._init_level_addr}")
160
161        if not self._init_level_end:
162            raise ValueError("Missing init section end symbol")
163
164    def _device_ord_from_name(self, sym_name):
165        """Find a device ordinal from a symbol name."""
166        if not sym_name:
167            return None
168
169        if not sym_name.startswith(_DEVICE_ORD_PREFIX):
170            return None
171
172        _, device_ord = sym_name.split(_DEVICE_ORD_PREFIX)
173        return int(device_ord)
174
175    def _object_name(self, addr):
176        if not addr:
177            return "NULL"
178        elif addr in self._objects:
179            return self._objects[addr][0]
180        else:
181            return "unknown"
182
183    def _initlevel_pointer(self, addr, idx, shidx):
184        elfclass = self._elf.elfclass
185        if elfclass == 32:
186            ptrsize = 4
187        elif elfclass == 64:
188            ptrsize = 8
189        else:
190            raise ValueError(f"Unknown pointer size for ELF class f{elfclass}")
191
192        section = self._elf.get_section(shidx)
193        start = section.header.sh_addr
194        data = section.data()
195
196        offset = addr - start
197
198        start = offset + ptrsize * idx
199        stop = offset + ptrsize * (idx + 1)
200
201        return int.from_bytes(data[start:stop], byteorder="little")
202
203    def _process_initlevels(self):
204        """Process the init level and find the init functions and devices."""
205        self.devices = {}
206        self.initlevels = {}
207
208        for i, level in enumerate(_DEVICE_INIT_LEVELS):
209            start = self._init_level_addr[level]
210            if i + 1 == len(_DEVICE_INIT_LEVELS):
211                stop = self._init_level_end
212            else:
213                stop = self._init_level_addr[_DEVICE_INIT_LEVELS[i + 1]]
214
215            self.initlevels[level] = []
216
217            priority = 0
218            addr = start
219            while addr < stop:
220                if addr not in self._objects:
221                    raise ValueError(f"no symbol at addr {addr:08x}")
222                obj, size, shidx = self._objects[addr]
223
224                arg0_name = self._object_name(self._initlevel_pointer(addr, 0, shidx))
225                arg1_name = self._object_name(self._initlevel_pointer(addr, 1, shidx))
226
227                ordinal = self._device_ord_from_name(arg1_name)
228                if ordinal:
229                    dev_addr = self._object_addr[arg1_name]
230                    _, _, shidx = self._objects[dev_addr]
231                    arg0_name = self._object_name(
232                        self._initlevel_pointer(dev_addr, DEVICE_INIT_OFFSET, shidx)
233                    )
234
235                    prio = Priority(level, priority)
236                    self.devices[ordinal] = (prio, arg0_name)
237
238                self.initlevels[level].append(f"{obj}: {arg0_name}({arg1_name})")
239
240                addr += size
241                priority += 1
242
243
244class Validator:
245    """Validates the initialization priorities.
246
247    Scans through a build folder for object files and list all the device
248    initialization priorities. Then compares that against the EDT derived
249    dependency list and log any found priority issue.
250
251    Attributes:
252        elf_file_path: path of the ELF file
253        edt_pickle: name of the EDT pickle file
254        log: a logging.Logger object
255    """
256
257    def __init__(self, elf_file_path, edt_pickle, log, elf_file):
258        self.log = log
259
260        edt_pickle_path = pathlib.Path(pathlib.Path(elf_file_path).parent, edt_pickle)
261        with open(edt_pickle_path, "rb") as f:
262            edt = pickle.load(f)
263
264        self._ord2node = edt.dep_ord2node
265
266        self._obj = ZephyrInitLevels(elf_file_path, elf_file)
267
268        self.errors = 0
269
270    def _flag_error(self, msg):
271        """Remember that a validation error occurred and report to user"""
272        if not self.errors:
273            self.log.error(
274                "Device initialization priority validation failed, "
275                "the sequence of initialization calls does not match "
276                "the devicetree dependencies."
277            )
278        self.errors += 1
279        self.log.error(msg)
280
281    def _check_dep(self, dev_ord, dep_ord):
282        """Validate the priority between two devices."""
283        if dev_ord == dep_ord:
284            return
285
286        dev_node = self._ord2node[dev_ord]
287        dep_node = self._ord2node[dep_ord]
288
289        if dev_node._binding:
290            dev_compat = dev_node._binding.compatible
291            if dev_compat in _IGNORE_COMPATIBLES:
292                self.log.info(f"Ignoring priority: {dev_node._binding.compatible}")
293                return
294
295        def _deferred(node):
296            # Even though the property is boolean, it is sometimes present
297            # in node.props despite having value false: check for both
298            # presence *and* value.
299            if (p := node.props.get(_DEFERRED_INIT_PROP_NAME)) is None:
300                return False
301            assert isinstance(p.val, bool)
302            return p.val
303
304        dev_deferred = _deferred(dev_node)
305        dep_deferred = _deferred(dep_node)
306
307        # Deferred devices can depend on any device...
308        if dev_deferred:
309            self.log.info(f"Ignoring deferred device {dev_node.path}")
310            return
311
312        # ...but non-deferred devices cannot depend on them!
313        if dep_deferred:  # we already know dev_deferred==False
314            self._flag_error(
315                f"Non-deferred device {dev_node.path} depends on deferred device {dep_node.path}"
316            )
317            return
318
319        dev_prio, dev_init = self._obj.devices.get(dev_ord, (None, None))
320        dep_prio, dep_init = self._obj.devices.get(dep_ord, (None, None))
321
322        if not dev_prio or not dep_prio:
323            return
324
325        if dev_prio == dep_prio:
326            raise ValueError(
327                f"{dev_node.path} and {dep_node.path} have the same priority: {dev_prio}"
328            )
329        elif dev_prio < dep_prio:
330            self._flag_error(
331                f"{dev_node.path} <{dev_init}> is initialized before its dependency "
332                f"{dep_node.path} <{dep_init}> ({dev_prio} < {dep_prio})"
333            )
334        else:
335            self.log.info(
336                f"{dev_node.path} <{dev_init}> {dev_prio} > {dep_node.path} <{dep_init}> {dep_prio}"
337            )
338
339    def check_edt(self):
340        """Scan through all known devices and validate the init priorities."""
341        for dev_ord in self._obj.devices:
342            dev = self._ord2node[dev_ord]
343            for dep in dev.depends_on:
344                self._check_dep(dev_ord, dep.dep_ordinal)
345
346    def print_initlevels(self):
347        for level, calls in self._obj.initlevels.items():
348            print(level)
349            for call in calls:
350                print(f"  {call}")
351
352
353def _parse_args(argv):
354    """Parse the command line arguments."""
355    parser = argparse.ArgumentParser(
356        description=__doc__,
357        formatter_class=argparse.RawDescriptionHelpFormatter,
358        allow_abbrev=False,
359    )
360
361    parser.add_argument(
362        "-f",
363        "--elf-file",
364        default=pathlib.Path("build", "zephyr", "zephyr.elf"),
365        help="ELF file to use",
366    )
367    parser.add_argument(
368        "-v",
369        "--verbose",
370        action="count",
371        help=("enable verbose output, can be used multiple times to increase verbosity level"),
372    )
373    parser.add_argument(
374        "--always-succeed",
375        action="store_true",
376        help="always exit with a return code of 0, used for testing",
377    )
378    parser.add_argument("-o", "--output", help="write the output to a file in addition to stdout")
379    parser.add_argument(
380        "-i",
381        "--initlevels",
382        action="store_true",
383        help="print the initlevel functions instead of checking the device dependencies",
384    )
385    parser.add_argument(
386        "--edt-pickle",
387        default=pathlib.Path("edt.pickle"),
388        help="name of the pickled edtlib.EDT file",
389        type=pathlib.Path,
390    )
391
392    return parser.parse_args(argv)
393
394
395def _init_log(verbose, output):
396    """Initialize a logger object."""
397    log = logging.getLogger(__file__)
398
399    console = logging.StreamHandler()
400    console.setFormatter(logging.Formatter("%(levelname)s: %(message)s"))
401    log.addHandler(console)
402
403    if output:
404        file = logging.FileHandler(output, mode="w")
405        file.setFormatter(logging.Formatter("%(levelname)s: %(message)s"))
406        log.addHandler(file)
407
408    if verbose and verbose > 1:
409        log.setLevel(logging.DEBUG)
410    elif verbose and verbose > 0:
411        log.setLevel(logging.INFO)
412    else:
413        log.setLevel(logging.WARNING)
414
415    return log
416
417
418def main(argv=None):
419    args = _parse_args(argv)
420
421    log = _init_log(args.verbose, args.output)
422
423    log.info(f"check_init_priorities: {args.elf_file}")
424
425    with open(args.elf_file, "rb") as elf_file:
426        validator = Validator(args.elf_file, args.edt_pickle, log, elf_file)
427        if args.initlevels:
428            validator.print_initlevels()
429        else:
430            validator.check_edt()
431
432        if args.always_succeed:
433            return 0
434
435        if validator.errors:
436            return 1
437
438    return 0
439
440
441if __name__ == "__main__":
442    sys.exit(main(sys.argv[1:]))
443