1#
2# Copyright 2021 Espressif Systems (Shanghai) CO LTD
3#
4# Licensed under the Apache License, Version 2.0 (the "License");
5# you may not use this file except in compliance with the License.
6# You may obtain a copy of the License at
7#
8#     http://www.apache.org/licenses/LICENSE-2.0
9#
10# Unless required by applicable law or agreed to in writing, software
11# distributed under the License is distributed on an "AS IS" BASIS,
12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13# See the License for the specific language governing permissions and
14# limitations under the License.
15#
16
17import collections
18import fnmatch
19import itertools
20from collections import namedtuple
21
22from entity import Entity
23from fragments import Mapping, Scheme, Sections
24from ldgen_common import LdGenFailure
25from output_commands import AlignAtAddress, InputSectionDesc, SymbolAtAddress
26
27
28class Placement():
29    """
30    A Placement is an assignment of an entity's input sections to a target
31    in the output linker script - a precursor to the input section description.
32
33    A placement can be excluded from another placement. These are represented
34    as contents of EXCLUDE_FILE in the input section description. Since the linker uses the
35    first matching rule, these exclusions make sure that accidental matching
36    of entities with higher specificity does not occur.
37
38    The placement which a placement is excluded from is referred to as the
39    'basis' placement. It operates on the same input section of the entity on
40    one of the parent (or parent's parent and so forth), but might have
41    a different target (see is_significant() for the criteria).
42
43    A placement is explicit if it was derived from an actual entry in one of
44    the mapping fragments. Just as intermediate entity nodes are created in some cases,
45    intermediate placements are created particularly for symbol placements.
46    The reason is that EXCLUDE_FILE does not work on symbols (see ObjectNode
47    for details).
48    """
49
50    def __init__(self, node, sections, target, flags, explicit, force=False, dryrun=False):
51        self.node = node
52        self.sections = sections
53        self.target = target
54        self.flags = flags
55
56        self.exclusions = set()
57        self.subplacements = set()
58
59        # Force this placement to be output
60        self.force = force
61
62        # This placement was created from a mapping
63        # fragment entry.
64        self.explicit = explicit
65
66        # Find basis placement.
67        parent = node.parent
68        candidate = None
69        while parent:
70            try:
71                candidate = parent.placements[sections]
72            except KeyError:
73                pass
74
75            if candidate and candidate.is_significant():
76                break
77            else:
78                parent = parent.parent
79
80        self.basis = candidate
81
82        if self.is_significant() and not dryrun and self.basis:
83            self.basis.add_exclusion(self)
84
85    def is_significant(self):
86        # Check if the placement is significant. Significant placements
87        # are the end of a basis chain (not self.basis) or a change
88        # in target (self.target != self.basis.target)
89        #
90        # Placement can also be a basis if it has flags
91        # (self.flags) or its basis has flags (self.basis.flags)
92        return (not self.basis or
93                self.target != self.basis.target or
94                (self.flags and not self.basis.flags) or
95                (not self.flags and self.basis.flags) or
96                self.force)
97
98    def force_significant(self):
99        if not self.is_significant():
100            self.force = True
101            if self.basis:
102                self.basis.add_exclusion(self)
103
104    def add_exclusion(self, exclusion):
105        self.exclusions.add(exclusion)
106
107    def add_subplacement(self, subplacement):
108        self.subplacements.add(subplacement)
109
110
111class EntityNode():
112    """
113    Node in entity tree. An EntityNode
114    is created from an Entity (see entity.py).
115
116    The entity tree has a maximum depth of 3. Nodes at different
117    depths are derived from this class for special behavior (see
118    RootNode, ArchiveNode, ObjectNode, SymbolNode) depending
119    on entity specificity.
120
121    Nodes for entities are inserted at the appropriate depth, creating
122    intermediate nodes along the path if necessary. For example, a node
123    for entity `lib1.a:obj1:sym1` needs to be inserted. If the node for `lib1:obj1`
124    does not exist, then it needs to be created.
125
126    A node contains a dictionary of placements (see Placement).
127    The key to this dictionary are contents of sections fragments,
128    representing the input sections of an entity. For example,
129    a node for entity `lib1.a` might have a placement entry for its `.text` input section
130    in this dictionary. The placement will contain details about the
131    target, the flags, etc.
132
133    Generation of output commands to be written to the output linker script
134    requires traversal of the tree, each node collecting the output commands
135    from its children, so on and so forth.
136    """
137
138    def __init__(self, parent, name):
139        self.children = []
140        self.parent = parent
141        self.name = name
142        self.child_t = EntityNode
143        self.entity = None
144        self.placements = dict()
145
146    def add_child(self, entity):
147        child_specificity = self.entity.specificity.value + 1
148        assert(child_specificity <= Entity.Specificity.SYMBOL.value)
149        name = entity[Entity.Specificity(child_specificity)]
150        assert(name and name != Entity.ALL)
151
152        child = [c for c in self.children if c.name == name]
153        assert(len(child) <= 1)
154
155        if not child:
156            child = self.child_t(self, name)
157            self.children.append(child)
158        else:
159            child = child[0]
160
161        return child
162
163    def get_output_commands(self):
164        commands = collections.defaultdict(list)
165
166        def process_commands(cmds):
167            for (target, commands_list) in cmds.items():
168                commands[target].extend(commands_list)
169
170        # Process the commands generated from this node
171        node_commands = self.get_node_output_commands()
172        process_commands(node_commands)
173
174        # Process the commands generated from this node's children
175        # recursively
176        for child in sorted(self.children, key=lambda c: c.name):
177            children_commands = child.get_output_commands()
178            process_commands(children_commands)
179
180        return commands
181
182    def get_node_output_commands(self):
183        commands = collections.defaultdict(list)
184
185        for sections in self.get_output_sections():
186            placement = self.placements[sections]
187            if placement.is_significant():
188                assert(placement.node == self)
189
190                keep = False
191                sort = None
192                surround_type = []
193
194                placement_flags = placement.flags if placement.flags is not None else []
195
196                for flag in placement_flags:
197                    if isinstance(flag, Mapping.Keep):
198                        keep = True
199                    elif isinstance(flag, Mapping.Sort):
200                        sort = (flag.first, flag.second)
201                    else:  # SURROUND or ALIGN
202                        surround_type.append(flag)
203
204                for flag in surround_type:
205                    if flag.pre:
206                        if isinstance(flag, Mapping.Surround):
207                            commands[placement.target].append(SymbolAtAddress('_%s_start' % flag.symbol))
208                        else:  # ALIGN
209                            commands[placement.target].append(AlignAtAddress(flag.alignment))
210
211                # This is for expanded object node and symbol node placements without checking for
212                # the type.
213                placement_sections = frozenset(placement.sections)
214                command_sections = sections if sections == placement_sections else placement_sections
215
216                command = InputSectionDesc(placement.node.entity, command_sections, [e.node.entity for e in placement.exclusions], keep, sort)
217                commands[placement.target].append(command)
218
219                # Generate commands for intermediate, non-explicit exclusion placements here, so that they can be enclosed by
220                # flags that affect the parent placement.
221                for subplacement in placement.subplacements:
222                    if not subplacement.flags and not subplacement.explicit:
223                        command = InputSectionDesc(subplacement.node.entity, subplacement.sections,
224                                                   [e.node.entity for e in subplacement.exclusions], keep, sort)
225                        commands[placement.target].append(command)
226
227                for flag in surround_type:
228                    if flag.post:
229                        if isinstance(flag, Mapping.Surround):
230                            commands[placement.target].append(SymbolAtAddress('_%s_end' % flag.symbol))
231                        else:  # ALIGN
232                            commands[placement.target].append(AlignAtAddress(flag.alignment))
233
234        return commands
235
236    def self_placement(self, sections, target, flags, explicit=True, force=False):
237        placement = Placement(self, sections, target, flags, explicit, force)
238        self.placements[sections] = placement
239        return placement
240
241    def child_placement(self, entity, sections, target, flags, sections_db):
242        child = self.add_child(entity)
243        child.insert(entity, sections, target, flags, sections_db)
244
245    def insert(self, entity, sections, target, flags, sections_db):
246        if self.entity.specificity == entity.specificity:
247            # Since specificities match, create the placement in this node.
248            self.self_placement(sections, target, flags)
249        else:
250            # If not, create a child node and try to create the placement there.
251            self.child_placement(entity, sections, target, flags, sections_db)
252
253    def get_output_sections(self):
254        return sorted(self.placements.keys(), key=' '.join)
255
256
257class SymbolNode(EntityNode):
258    """
259    Entities at depth=3. Represents entities with archive, object
260    and symbol specified.
261    """
262    def __init__(self, parent, name):
263        EntityNode.__init__(self, parent, name)
264        self.entity = Entity(self.parent.parent.name, self.parent.name)
265
266
267class ObjectNode(EntityNode):
268    """
269    Entities at depth=2. Represents entities with archive
270    and object specified.
271
272    Creating a placement on a child node (SymbolNode) has a different behavior, since
273    exclusions using EXCLUDE_FILE for symbols does not work.
274
275    The sections of this entity has to be 'expanded'. That is, we must
276    look into the actual input sections of this entity and remove
277    the ones corresponding to the symbol. The remaining sections of an expanded
278    object entity will be listed one-by-one in the corresponding
279    input section description.
280
281    An intermediate placement on this node is created, if one does not exist,
282    and is the one excluded from its basis placement.
283    """
284    def __init__(self, parent, name):
285        EntityNode.__init__(self, parent, name)
286        self.child_t = SymbolNode
287        self.entity = Entity(self.parent.name, self.name)
288        self.subplacements = list()
289
290    def child_placement(self, entity, sections, target, flags, sections_db):
291        child = self.add_child(entity)
292        sym_placement = Placement(child, sections, target, flags, True, dryrun=True)
293
294        # The basis placement for sym_placement can either be
295        # an existing placement on this node, or nonexistent.
296        if sym_placement.is_significant():
297            try:
298                obj_sections = self.placements[sections].sections
299            except KeyError:
300                obj_sections = None
301
302            if not obj_sections or obj_sections == sections:
303                # Expand this section for the first time
304                found_sections = sections_db.get_sections(self.parent.name, self.name)
305                obj_sections = []
306                for s in sections:
307                    obj_sections.extend(fnmatch.filter(found_sections, s))
308
309            if obj_sections:
310                symbol = entity.symbol
311                remove_sections = [s.replace('.*', '.%s' % symbol) for s in sections if '.*' in s]
312                filtered_sections = [s for s in obj_sections if s not in remove_sections]
313
314                if set(filtered_sections) != set(obj_sections):
315                    if sym_placement.basis:
316                        subplace = False
317                        try:
318                            # If existing placement exists, make sure that
319                            # it is emitted.
320                            obj_placement = self.placements[sections]
321                        except KeyError:
322                            # Create intermediate placement.
323                            obj_placement = self.self_placement(sections, sym_placement.basis.target, None, False)
324                            if obj_placement.basis.flags:
325                                subplace = True
326
327                        if subplace:
328                            obj_placement.basis.add_subplacement(obj_placement)
329                            self.subplacements.append(sections)
330                        else:
331                            obj_placement.force_significant()
332
333                        obj_placement.sections = filtered_sections
334                        sym_placement.basis = obj_placement
335
336                    sym_placement.sections = remove_sections
337                    child.placements[sections] = sym_placement
338
339    def get_output_sections(self):
340        output_sections = [key for key in self.placements if key not in self.subplacements]
341        return sorted(output_sections, key=' '.join)
342
343
344class ArchiveNode(EntityNode):
345    """
346    Entities at depth=1. Represents entities with archive specified.
347    """
348    def __init__(self, parent, name):
349        EntityNode.__init__(self, parent, name)
350        self.child_t = ObjectNode
351        self.entity = Entity(self.name)
352
353
354class RootNode(EntityNode):
355    """
356    Single entity at depth=0. Represents entities with no specific members
357    specified.
358    """
359    def __init__(self):
360        EntityNode.__init__(self, None, Entity.ALL)
361        self.child_t = ArchiveNode
362        self.entity = Entity(Entity.ALL)
363
364
365class Generation:
366    """
367    Processes all fragments processed from fragment files included in the build.
368    Generates output commands (see output_commands.py) that LinkerScript (see linker_script.py) can
369    write to the output linker script.
370    """
371
372    # Processed mapping, scheme and section entries
373    EntityMapping = namedtuple('EntityMapping', 'entity sections_group target flags')
374
375    def __init__(self, check_mappings=False, check_mapping_exceptions=None):
376        self.schemes = {}
377        self.placements = {}
378        self.mappings = {}
379
380        self.check_mappings = check_mappings
381
382        if check_mapping_exceptions:
383            self.check_mapping_exceptions = check_mapping_exceptions
384        else:
385            self.check_mapping_exceptions = []
386
387    def _prepare_scheme_dictionary(self):
388        scheme_dictionary = collections.defaultdict(dict)
389
390        # Collect sections into buckets based on target name
391        for scheme in self.schemes.values():
392            sections_bucket = collections.defaultdict(list)
393
394            for (sections_name, target_name) in scheme.entries:
395                # Get the sections under the bucket 'target_name'. If this bucket does not exist
396                # is is created automatically
397                sections_in_bucket = sections_bucket[target_name]
398
399                try:
400                    sections = self.placements[sections_name]
401                except KeyError:
402                    message = GenerationException.UNDEFINED_REFERENCE + " to sections '" + sections_name + "'."
403                    raise GenerationException(message, scheme)
404
405                sections_in_bucket.append(sections)
406
407            scheme_dictionary[scheme.name] = sections_bucket
408
409        # Search for and raise exception on first instance of sections mapped to multiple targets
410        for (scheme_name, sections_bucket) in scheme_dictionary.items():
411            for sections_a, sections_b in itertools.combinations(sections_bucket.values(), 2):
412                set_a = set()
413                set_b = set()
414
415                for sections in sections_a:
416                    set_a.update(sections.entries)
417
418                for sections in sections_b:
419                    set_b.update(sections.entries)
420
421                intersection = set_a.intersection(set_b)
422
423                # If the intersection is a non-empty set, it means sections are mapped to multiple
424                # targets. Raise exception.
425                if intersection:
426                    scheme = self.schemes[scheme_name]
427                    message = 'Sections ' + str(intersection) + ' mapped to multiple targets.'
428                    raise GenerationException(message, scheme)
429
430        return scheme_dictionary
431
432    def _prepare_entity_mappings(self, scheme_dictionary, entities):
433        # Prepare entity mappings processed from mapping fragment entries.
434        def get_section_strs(section):
435            s_list = [Sections.get_section_data_from_entry(s) for s in section.entries]
436            return frozenset([item for sublist in s_list for item in sublist])
437
438        entity_mappings = dict()
439
440        for mapping in self.mappings.values():
441            archive = mapping.archive
442
443            for (obj, symbol, scheme_name) in mapping.entries:
444                entity = Entity(archive, obj, symbol)
445
446                # Check the entity exists
447                if (self.check_mappings and
448                        entity.specificity.value > Entity.Specificity.ARCHIVE.value and
449                        mapping.name not in self.check_mapping_exceptions):
450                    if not entities.check_exists(entity):
451                        message = "'%s' not found" % str(entity)
452                        raise GenerationException(message, mapping)
453
454                if (obj, symbol, scheme_name) in mapping.flags.keys():
455                    flags = mapping.flags[(obj, symbol, scheme_name)]
456                    # Check if all section->target defined in the current
457                    # scheme.
458                    for (s, t, f) in flags:
459                        if (t not in scheme_dictionary[scheme_name].keys() or
460                                s not in [_s.name for _s in scheme_dictionary[scheme_name][t]]):
461
462                            message = "%s->%s not defined in scheme '%s'" % (s, t, scheme_name)
463                            raise GenerationException(message, mapping)
464                else:
465                    flags = None
466
467                # Create placement for each 'section -> target' in the scheme.
468                for (target, sections) in scheme_dictionary[scheme_name].items():
469                    for section in sections:
470                        # Find the applicable flags
471                        _flags = []
472
473                        if flags:
474                            for (s, t, f) in flags:
475                                if (s, t) == (section.name, target):
476                                    _flags.extend(f)
477
478                        sections_str = get_section_strs(section)
479
480                        key = (entity, section.name)
481
482                        try:
483                            existing = entity_mappings[key]
484                        except KeyError:
485                            existing = None
486
487                        if not existing:
488                            entity_mappings[key] = Generation.EntityMapping(entity, sections_str, target, _flags)
489                        else:
490                            # Check for conflicts.
491                            if (target != existing.target):
492                                raise GenerationException('Sections mapped to multiple targets.', mapping)
493
494                            # Combine flags here if applicable, to simplify
495                            # insertion logic.
496                            if (_flags or existing.flags):
497                                if ((_flags and not existing.flags) or (not _flags and existing.flags)):
498                                    _flags.extend(existing.flags)
499                                    entity_mappings[key] = Generation.EntityMapping(entity,
500                                                                                    sections_str,
501                                                                                    target, _flags)
502                                elif (_flags == existing.flags):
503                                    pass
504                                else:
505                                    raise GenerationException('Conflicting flags specified.', mapping)
506
507        # Sort the mappings by specificity, so as to simplify
508        # insertion logic.
509        res = list(entity_mappings.values())
510        res.sort(key=lambda m: m.entity)
511        return res
512
513    def generate(self, entities):
514        scheme_dictionary = self._prepare_scheme_dictionary()
515        entity_mappings = self._prepare_entity_mappings(scheme_dictionary, entities)
516        root_node = RootNode()
517        for mapping in entity_mappings:
518            (entity, sections, target, flags) = mapping
519            try:
520                root_node.insert(entity, sections, target, flags, entities)
521            except ValueError as e:
522                raise GenerationException(str(e))
523
524        # Traverse the tree, creating the placements
525        commands = root_node.get_output_commands()
526
527        return commands
528
529    def add_fragments_from_file(self, fragment_file):
530        for fragment in fragment_file.fragments:
531            dict_to_append_to = None
532
533            if isinstance(fragment, Mapping) and fragment.deprecated and fragment.name in self.mappings.keys():
534                self.mappings[fragment.name].entries |= fragment.entries
535            else:
536                if isinstance(fragment, Scheme):
537                    dict_to_append_to = self.schemes
538                elif isinstance(fragment, Sections):
539                    dict_to_append_to = self.placements
540                else:
541                    dict_to_append_to = self.mappings
542
543                # Raise exception when the fragment of the same type is already in the stored fragments
544                if fragment.name in dict_to_append_to.keys():
545                    stored = dict_to_append_to[fragment.name].path
546                    new = fragment.path
547                    message = "Duplicate definition of fragment '%s' found in %s and %s." % (fragment.name, stored, new)
548                    raise GenerationException(message)
549
550                dict_to_append_to[fragment.name] = fragment
551
552
553class GenerationException(LdGenFailure):
554    """
555    Exception for linker script generation failures such as undefined references/ failure to
556    evaluate conditions, duplicate mappings, etc.
557    """
558
559    UNDEFINED_REFERENCE = 'Undefined reference'
560
561    def __init__(self, message, fragment=None):
562        self.fragment = fragment
563        self.message = message
564
565    def __str__(self):
566        if self.fragment:
567            return "%s\nIn fragment '%s' defined in '%s'." % (self.message, self.fragment.name, self.fragment.path)
568        else:
569            return self.message
570