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