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
