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