1#!/usr/bin/env python3
2#
3# Copyright (c) 2022, CSIRO
4#
5# SPDX-License-Identifier: Apache-2.0
6
7import struct
8import sys
9from packaging import version
10
11import elftools
12from elftools.elf.elffile import ELFFile
13from elftools.elf.sections import SymbolTableSection
14
15if version.parse(elftools.__version__) < version.parse('0.24'):
16    sys.exit("pyelftools is out of date, need version 0.24 or later")
17
18class _Symbol:
19    """
20    Parent class for objects derived from an elf symbol.
21    """
22    def __init__(self, elf, sym):
23        self.elf = elf
24        self.sym = sym
25        self.data = self.elf.symbol_data(sym)
26
27    def __lt__(self, other):
28        return self.sym.entry.st_value < other.sym.entry.st_value
29
30    def _data_native_read(self, offset):
31        (format, size) = self.elf.native_struct_format
32        return struct.unpack(format, self.data[offset:offset + size])[0]
33
34class DevicePM(_Symbol):
35    """
36    Represents information about device PM capabilities.
37    """
38    required_ld_consts = [
39        "_PM_DEVICE_STRUCT_FLAGS_OFFSET",
40        "_PM_DEVICE_FLAG_PD"
41    ]
42
43    def __init__(self, elf, sym):
44        super().__init__(elf, sym)
45        self.flags = self._data_native_read(self.elf.ld_consts['_PM_DEVICE_STRUCT_FLAGS_OFFSET'])
46
47    @property
48    def is_power_domain(self):
49        return self.flags & (1 << self.elf.ld_consts["_PM_DEVICE_FLAG_PD"])
50
51class DeviceOrdinals(_Symbol):
52    """
53    Represents information about device dependencies.
54    """
55    DEVICE_HANDLE_SEP = -32768
56    DEVICE_HANDLE_ENDS = 32767
57    DEVICE_HANDLE_NULL = 0
58
59    def __init__(self, elf, sym):
60        super().__init__(elf, sym)
61        format = "<" if self.elf.little_endian else ">"
62        format += "{:d}h".format(len(self.data) // 2)
63        self._ordinals = struct.unpack(format, self.data)
64        self._ordinals_split = []
65
66        # Split ordinals on DEVICE_HANDLE_SEP
67        prev =  1
68        for idx, val in enumerate(self._ordinals, 1):
69            if val == self.DEVICE_HANDLE_SEP:
70                self._ordinals_split.append(self._ordinals[prev:idx-1])
71                prev = idx
72        self._ordinals_split.append(self._ordinals[prev:])
73
74    @property
75    def self_ordinal(self):
76        return self._ordinals[0]
77
78    @property
79    def ordinals(self):
80        return self._ordinals_split
81
82class Device(_Symbol):
83    """
84    Represents information about a device object and its references to other objects.
85    """
86    required_ld_consts = [
87        "_DEVICE_STRUCT_HANDLES_OFFSET",
88        "_DEVICE_STRUCT_PM_OFFSET"
89    ]
90
91    def __init__(self, elf, sym):
92        super().__init__(elf, sym)
93        self.edt_node = None
94        self.handle = None
95        self.ordinals = None
96        self.pm = None
97
98        # Devicetree dependencies, injected dependencies, supported devices
99        self.devs_depends_on = set()
100        self.devs_depends_on_injected = set()
101        self.devs_supports = set()
102
103        # Point to the handles instance associated with the device;
104        # assigned by correlating the device struct handles pointer
105        # value with the addr of a Handles instance.
106        self.obj_ordinals = None
107        if '_DEVICE_STRUCT_HANDLES_OFFSET' in self.elf.ld_consts:
108            ordinal_offset = self.elf.ld_consts['_DEVICE_STRUCT_HANDLES_OFFSET']
109            self.obj_ordinals = self._data_native_read(ordinal_offset)
110
111        self.obj_pm = None
112        if '_DEVICE_STRUCT_PM_OFFSET' in self.elf.ld_consts:
113            pm_offset = self.elf.ld_consts['_DEVICE_STRUCT_PM_OFFSET']
114            self.obj_pm = self._data_native_read(pm_offset)
115
116    @property
117    def ordinal(self):
118        return self.ordinals.self_ordinal
119
120class ZephyrElf:
121    """
122    Represents information about devices in an elf file.
123    """
124    def __init__(self, kernel, edt, device_start_symbol):
125        self.elf = ELFFile(open(kernel, "rb"))
126        self.relocatable = self.elf['e_type'] == 'ET_REL'
127        self.edt = edt
128        self.devices = []
129        self.ld_consts = self._symbols_find_value(set([device_start_symbol, *Device.required_ld_consts, *DevicePM.required_ld_consts]))
130        self._device_parse_and_link()
131
132    @property
133    def little_endian(self):
134        """
135        True if the elf file is for a little-endian architecture.
136        """
137        return self.elf.little_endian
138
139    @property
140    def native_struct_format(self):
141        """
142        Get the struct format specifier and byte size of the native machine type.
143        """
144        format = "<" if self.little_endian else ">"
145        if self.elf.elfclass == 32:
146            format += "I"
147            size = 4
148        else:
149            format += "Q"
150            size = 8
151        return (format, size)
152
153    def symbol_data(self, sym):
154        """
155        Retrieve the raw bytes associated with a symbol from the elf file.
156        """
157        # Symbol data parameters
158        addr = sym.entry.st_value
159        length = sym.entry.st_size
160        # Section associated with the symbol
161        section = self.elf.get_section(sym.entry['st_shndx'])
162        data = section.data()
163        # Relocatable data does not appear to be shifted
164        offset = addr - (0 if self.relocatable else section['sh_addr'])
165        # Validate data extraction
166        assert offset + length <= len(data)
167        # Extract symbol bytes from section
168        return bytes(data[offset:offset + length])
169
170    def _symbols_find_value(self, names):
171        symbols = {}
172        for section in self.elf.iter_sections():
173            if isinstance(section, SymbolTableSection):
174                for sym in section.iter_symbols():
175                    if sym.name in names:
176                        symbols[sym.name] = sym.entry.st_value
177        return symbols
178
179    def _object_find_named(self, prefix, cb):
180        for section in self.elf.iter_sections():
181            if isinstance(section, SymbolTableSection):
182                for sym in section.iter_symbols():
183                    if sym.entry.st_info.type != 'STT_OBJECT':
184                        continue
185                    if sym.name.startswith(prefix):
186                        cb(sym)
187
188    def _link_devices(self, devices):
189        # Compute the dependency graph induced from the full graph restricted to the
190        # the nodes that exist in the application.  Note that the edges in the
191        # induced graph correspond to paths in the full graph.
192        root = self.edt.dep_ord2node[0]
193
194        for ord, dev in devices.items():
195            n = self.edt.dep_ord2node[ord]
196
197            deps = set(n.depends_on)
198            while len(deps) > 0:
199                dn = deps.pop()
200                if dn.dep_ordinal in devices:
201                    # this is used
202                    dev.devs_depends_on.add(devices[dn.dep_ordinal])
203                elif dn != root:
204                    # forward the dependency up one level
205                    for ddn in dn.depends_on:
206                        deps.add(ddn)
207
208            sups = set(n.required_by)
209            while len(sups) > 0:
210                sn = sups.pop()
211                if sn.dep_ordinal in devices:
212                    dev.devs_supports.add(devices[sn.dep_ordinal])
213                else:
214                    # forward the support down one level
215                    for ssn in sn.required_by:
216                        sups.add(ssn)
217
218    def _link_injected(self, devices):
219        for dev in devices.values():
220            injected = dev.ordinals.ordinals[1]
221            for inj in injected:
222                if inj in devices:
223                    dev.devs_depends_on_injected.add(devices[inj])
224                    devices[inj].devs_supports.add(dev)
225
226    def _device_parse_and_link(self):
227        # Find all PM structs
228        pm_structs = {}
229        def _on_pm(sym):
230            pm_structs[sym.entry.st_value] = DevicePM(self, sym)
231        self._object_find_named('__pm_device_', _on_pm)
232
233        # Find all ordinal arrays
234        ordinal_arrays = {}
235        def _on_ordinal(sym):
236            ordinal_arrays[sym.entry.st_value] = DeviceOrdinals(self, sym)
237        self._object_find_named('__devicedeps_', _on_ordinal)
238
239        # Find all device structs
240        def _on_device(sym):
241            self.devices.append(Device(self, sym))
242        self._object_find_named('__device_', _on_device)
243
244        # Sort the device array by address (st_value) for handle calculation
245        self.devices = sorted(self.devices)
246
247        # Assign handles to the devices
248        for idx, dev in enumerate(self.devices):
249            dev.handle = 1 + idx
250
251        # Link devices structs with PM and ordinals
252        for dev in self.devices:
253            if dev.obj_pm in pm_structs:
254                dev.pm = pm_structs[dev.obj_pm]
255            if dev.obj_ordinals in ordinal_arrays:
256                dev.ordinals = ordinal_arrays[dev.obj_ordinals]
257                if dev.ordinal != DeviceOrdinals.DEVICE_HANDLE_NULL:
258                    dev.edt_node = self.edt.dep_ord2node[dev.ordinal]
259
260        # Create mapping of ordinals to devices
261        devices_by_ord = {d.ordinal: d for d in self.devices if d.edt_node}
262
263        # Link devices to each other based on the EDT tree
264        self._link_devices(devices_by_ord)
265
266        # Link injected devices to each other
267        self._link_injected(devices_by_ord)
268
269    def device_dependency_graph(self, title, comment):
270        """
271        Construct a graphviz Digraph of the relationships between devices.
272        """
273        import graphviz
274        dot = graphviz.Digraph(title, comment=comment)
275        # Split iteration so nodes and edges are grouped in source
276        for dev in self.devices:
277            if dev.ordinal == DeviceOrdinals.DEVICE_HANDLE_NULL:
278                text = '{:s}\\nHandle: {:d}'.format(dev.sym.name, dev.handle)
279            else:
280                n = self.edt.dep_ord2node[dev.ordinal]
281                text = '{:s}\\nOrdinal: {:d} | Handle: {:d}\\n{:s}'.format(
282                    n.name, dev.ordinal, dev.handle, n.path
283                )
284            dot.node(str(dev.ordinal), text)
285        for dev in self.devices:
286            for sup in sorted(dev.devs_supports):
287                dot.edge(str(dev.ordinal), str(sup.ordinal))
288        return dot
289