1# 2# Copyright 2020, Data61, CSIRO (ABN 41 687 119 230) 3# 4# SPDX-License-Identifier: BSD-2-Clause 5# 6 7from __future__ import absolute_import, division, print_function, \ 8 unicode_literals 9 10import abc 11import collections 12import logging 13 14import six 15from sortedcontainers import SortedList, SortedSet, SortedDict 16 17from .Cap import Cap 18from .Object import Frame, PageTable, PageDirectory, CNode, Endpoint, \ 19 Notification, TCB, Untyped, IOPageTable, Object, IRQ, IOPorts, IODevice, \ 20 ARMIODevice, VCPU, ASIDPool, SC, SchedControl, RTReply, ObjectType, \ 21 ObjectRights, IOAPICIRQ, MSIIRQ, IRQControl, get_object_size, ASIDControl, \ 22 DomainControl, is_aligned, ARMIRQMode, ARMIRQ, ContextBank, StreamID 23from capdl.util import ctz 24from .Spec import Spec 25 26 27class AllocatorState(object): 28 def __init__(self, obj_space, cspaces={}, pds={}, addr_spaces={}): 29 self.obj_space = obj_space 30 self.cspaces = cspaces 31 self.pds = pds 32 self.addr_spaces = addr_spaces 33 34 35class RenderState(AllocatorState): 36 ''' 37 This bolts extra CAmkES state onto the capDL allocator state. 38 For now, this just tracks extra adjustments to the integrity 39 policy used in cdl-refine.thy. 40 41 FIXME: this ought to go into camkes-tool, but Python pickle 42 doesn't seem to like deserialising locally defined classes. 43 ''' 44 45 def __init__(self, *args, **kwargs): 46 super(RenderState, self).__init__(*args, **kwargs) 47 self.policy_extra = set() 48 49 50class ObjectAllocator(object): 51 ''' 52 An offline object allocator. This can be useful for incrementally 53 generating a CapDL spec. 54 ''' 55 56 def __init__(self, prefix='obj'): 57 self.prefix = prefix 58 self.counter = 0 59 self.spec = Spec() 60 self.labels = collections.defaultdict(set) 61 self.name_to_object = {} 62 63 def _assign_label(self, label, obj): 64 self.labels[label].add(obj) 65 66 def _remove_label(self, obj): 67 for l, objs in self.labels.items(): 68 if obj in objs: 69 self.labels[l].remove(obj) 70 break 71 72 def relabel(self, label, obj): 73 self._remove_label(obj) 74 self._assign_label(label, obj) 75 76 def alloc(self, type, name=None, label=None, **kwargs): 77 if name is None: 78 name = '%s%d' % (self.prefix, self.counter) 79 80 o = self.name_to_object.get(name) 81 if o is not None: 82 assert o in self.labels.get(label, set()), \ 83 'attempt to allocate object %s under a new, differing label' % o.name 84 return o 85 86 self.counter += 1 87 frame_type = [page for page in self.spec.arch.get_pages() if page == type] 88 if type == ObjectType.seL4_UntypedObject: 89 size_bits = kwargs.get('size_bits', 12) 90 paddr = kwargs.get('paddr', None) 91 assert(paddr != 0) 92 o = Untyped(name, size_bits, paddr) 93 elif type == ObjectType.seL4_TCBObject: 94 o = TCB(name) 95 elif type == ObjectType.seL4_EndpointObject: 96 o = Endpoint(name) 97 elif type == ObjectType.seL4_NotificationObject: 98 o = Notification(name) 99 elif type == ObjectType.seL4_CapTableObject: 100 o = CNode(name, **kwargs) 101 elif type == ObjectType.seL4_FrameObject: 102 if 'size' not in kwargs: 103 kwargs['size'] = 4096 104 o = Frame(name, **kwargs) 105 elif type == ObjectType.seL4_PageTableObject: 106 o = PageTable(name) 107 elif type == self.spec.arch.vspace().object: 108 o = self.spec.arch.vspace().make_object(name) 109 elif type == ObjectType.seL4_PageDirectoryObject: 110 o = PageDirectory(name) 111 elif type == ObjectType.seL4_IOPageTableObject: 112 o = IOPageTable(name) 113 elif type == ObjectType.seL4_IA32_IOPort: 114 # There is only one IOPort object in the system, which describes the entire 115 # port region. 116 if 'start_port' in kwargs and 'end_port' in kwargs: 117 o = IOPorts(name, start_port=kwargs['start_port'], end_port=kwargs['end_port']) 118 else: 119 raise ValueError 120 elif type == ObjectType.seL4_IA32_IOSpace: 121 o = IODevice(name, **kwargs) 122 elif type == ObjectType.seL4_ARM_IOSpace: 123 o = ARMIODevice(name, **kwargs) 124 elif type == ObjectType.seL4_VCPU: 125 o = VCPU(name) 126 elif type == ObjectType.seL4_IRQHandler: 127 notification = None 128 if 'notification' in kwargs: 129 notification = kwargs['notification'] 130 del kwargs['notification'] 131 132 if 'trigger' in kwargs or 'target' in kwargs: 133 o = ARMIRQ(name, **kwargs) 134 elif 'number' in kwargs: 135 o = IRQ(name, kwargs['number']) 136 elif 'vector' in kwargs and 'ioapic' in kwargs \ 137 and 'ioapic_pin' in kwargs and 'level' in kwargs and 'polarity' in kwargs: 138 o = IOAPICIRQ(name, kwargs['vector'], kwargs['ioapic'], kwargs['ioapic_pin'], 139 kwargs['level'], kwargs['polarity']) 140 elif 'vector' in kwargs and 'handle' in kwargs \ 141 and 'pci_bus' in kwargs and 'pci_dev' in kwargs and 'pci_fun' in kwargs: 142 o = MSIIRQ(name, kwargs['vector'], kwargs['handle'], kwargs['pci_bus'], 143 kwargs['pci_dev'], kwargs['pci_fun']) 144 else: 145 raise ValueError("IRQHandler objects must define (number|vector,ioapic,ioapic_pin,level," 146 "polarity|vector,handle,pci_bus,pci_dev,pci_fun)") 147 148 if notification is not None: 149 o.set_notification(notification) 150 elif type == ObjectType.seL4_IRQControl: 151 o = IRQControl(name) 152 elif type == ObjectType.seL4_ASID_Control: 153 o = ASIDControl(name) 154 elif type == ObjectType.seL4_DomainControl: 155 o = DomainControl(name) 156 elif type == ObjectType.seL4_ASID_Pool: 157 o = ASIDPool(name) 158 elif len(frame_type) == 1: 159 o = Frame(name, get_object_size(frame_type[0]), **kwargs) 160 elif type == ObjectType.seL4_SchedContextObject: 161 o = SC(name) 162 elif type == ObjectType.seL4_SchedControl: 163 o = SchedControl(name) 164 elif type == ObjectType.seL4_RTReplyObject: 165 o = RTReply(name) 166 elif type == ObjectType.seL4_ARMSID: 167 o = StreamID(name) 168 elif type == ObjectType.seL4_ARMCB: 169 o = ContextBank(name) 170 else: 171 raise Exception('Invalid object type %s' % type) 172 self.spec.add_object(o) 173 self.name_to_object[name] = o 174 self._assign_label(label, o) 175 return o 176 177 def merge(self, spec, label=None): 178 assert isinstance(spec, Spec) 179 self.spec.merge(spec) 180 [self._assign_label(label, x) for x in spec.objs] 181 self.name_to_object.update({x.name: x for x in spec}) 182 183 def __contains__(self, item): 184 return item in self.name_to_object 185 186 def __getitem__(self, name): 187 return self.name_to_object[name] 188 189 def __iter__(self): 190 return self.spec.__iter__() 191 192 def remove(self, o): 193 self._remove_label(o) 194 self.spec.objs.remove(o) 195 del self.name_to_object[o.name] 196 197 198class CSpaceAllocator(object): 199 ''' 200 An offline CSpace allocator. Note that this is only capable of allocating 201 from a single level CSpace. 202 ''' 203 204 def __init__(self, cnode): 205 assert isinstance(cnode, CNode) 206 self.cnode = cnode 207 self.slot = 1 # Skip the null slot 208 209 def alloc(self, obj, **kwargs): 210 ''' 211 Allocate a cap in the next available slot, referencing the given 212 object. The caller is expected to pass either (a) no extra parameters 213 indicating a cap with no rights, (b) the extra parameter 'rights' set 214 to one of 0/seL4_CanRead/seL4_CanWrite/seL4_CanGrant/seL4_AllRights, 215 or (c) some combination of the boolean parameters 'read', 'write', 'grant' 216 and 'grantreply' indicating the rights of the cap. 217 ''' 218 assert isinstance(obj, Object) or obj is None 219 220 while self.slot in self.cnode.slots: 221 # Skip slots the caller may have manually populated. 222 self.slot += 1 223 if self.cnode.size_bits != 'auto' and self.slot > (1 << self.cnode.size_bits) - 1: 224 # Ran out of space in the CNode. 225 return -1 226 slot = self.slot 227 self.slot += 1 228 if obj is None: 229 # The caller requested just a free slot. 230 cap = None 231 else: 232 if 'rights' in kwargs: 233 assert 'read' not in kwargs 234 assert 'write' not in kwargs 235 assert 'grant' not in kwargs 236 assert 'grantreply' not in kwargs 237 kwargs['read'] = kwargs['rights'] & ObjectRights.seL4_CanRead > 0 238 kwargs['write'] = kwargs['rights'] & ObjectRights.seL4_CanWrite > 0 239 kwargs['grant'] = kwargs['rights'] & ObjectRights.seL4_CanGrant > 0 240 kwargs['grantreply'] = kwargs['rights'] & ObjectRights.seL4_CanGrantReply > 0 241 cap = Cap(obj, **kwargs) 242 if isinstance(obj, CNode): 243 obj.update_guard_size_caps.append(cap) 244 245 self.cnode[slot] = cap 246 return slot 247 248 249class AddressSpaceAllocator(object): 250 ''' 251 Structure for describing backing frame policy for an address space loaded 252 by capDL. 253 254 Currently there is a default policy that will create frame mappings 255 for all elf loadable sections that will use the largest frames that are less 256 or equal to the section sizes. In the future it may be possible to specify 257 different policies, such as ones that minimise object count or translate 258 ELF mapping attributes differently. 259 260 For now, this structure is used to describe regions with different attributes 261 than the default policy for describing things such as IPC buffers, shared memory, 262 guarded symbols, unmapped symbols, DMA pools, Physical memory mappings, etc. 263 264 A likely lifecycle of this object is to record special symbols that will appear 265 in the ELF file with the frame objects to use for mapping. Then when the ELF file is 266 constructed, these symbols will be translated into virtual addresses that can 267 be given to the PageCollection object as it creates a spec with the provided frames. 268 ''' 269 270 def __init__(self, name, vspace_root): 271 self.name = name 272 self.vspace_root = vspace_root 273 self._symbols = {} 274 self._regions = {} 275 276 def add_symbol_with_caps(self, symbol, sizes, caps): 277 ''' 278 Specify the caps and sizes to use for a given symbol. Objects that the 279 caps refer to should have been allocated by a ObjectAllocator otherwise 280 they might not end up in the final CDL spec file. 281 282 It should be possible for the frames to be mapped into the address space 283 of the symbol in a sensible way. Therefore alignment and size of the symbol 284 should be compatible with the array of frames provided. 285 286 Examples: 287 - A symbol of size 4k with a 4k Frame object should be 4K aligned in the 288 elf file. 289 - A Symbol of size 12k, with 3 4K Frames that have different rights, should 290 be 4K aligned in the ELF file and the frames correspond to the mappings 291 in order from lowest to highest. 292 - A Symbol using a 1M sized frame object should be either 1M sized with 293 compatible alignment, or guarantee that the ELF file will have a 1M hole 294 with compatible alignment for the 1M frame to be mapped that overlaps the 295 symbol. 296 ''' 297 self._symbols[symbol] = (sizes, caps) 298 299 def get_symbols_and_clear(self): 300 ''' 301 This function is used for converting symbols into virtual addresses with 302 an elf file. Resulting regions should be added back via add_region_with_caps 303 This sets the internal symbols structure to None to prevent usages after. 304 ''' 305 symbols = self._symbols 306 self._symbols = None 307 return symbols 308 309 def add_region_with_caps(self, vaddr, sizes, caps): 310 ''' 311 This is the same as add_symbol_with_caps but uses a specific address in 312 the virtual address space instead of a symbol. At some point before the 313 address space objects are created, all of the symbols should be converted 314 to regions using get_symbols_and_clear and add_region_with_caps to transform 315 the symbols into vaddrs with the help of an ELF file. 316 ''' 317 assert len(sizes) == len(caps) 318 for (size, cap) in zip(sizes, caps): 319 assert vaddr not in self._regions, "duplicate definition: vaddr 0x%x already exists" % vaddr 320 self._regions[vaddr] = (size, cap) 321 vaddr += size 322 323 def get_regions_and_clear(self): 324 ''' 325 This is for consuming this allocator to create a PageCollection structure 326 that gets merged with the main object allocator. 327 This sets the internal regions structure to None to prevent usages after. 328 ''' 329 regions = self._regions 330 self._regions = None 331 return regions 332 333 334class AllocatorException(Exception): 335 pass 336 337 338class ASIDTableAllocator(object): 339 """ 340 Assign ASID table slot numbers for ASID pools. 341 342 While slot numbers are not visible to userland, they are visible in the 343 DSpec verification model, so the capDL loader supports explicit policies 344 for ASID allocation. 345 """ 346 347 def allocate(self, spec): 348 """ 349 For each ASID pool in the spec, assign it to an unused ASID table slot. 350 This modifies the spec's ASID pool objects in-place. 351 352 Slot 0 is always skipped, because it is used for the init thread's ASID pool. 353 We assume that the C loader also skips slot 0. 354 355 This allocator allows ASID pools that already have assigned asid_high numbers. 356 However, seL4 only allows allocating table slots in sequential order. 357 Therefore, we raise AllocatorException if the spec's asid_high numbers cannot 358 be obtained by the C loader. 359 """ 360 assert(isinstance(spec, Spec)) 361 362 num_asid_high = get_object_size(ObjectType.seL4_ASID_Table) 363 free_asid_highs = SortedSet(range(num_asid_high)) 364 free_asid_highs.remove(0) # Init thread's 365 366 asid_pools = [] 367 368 # Get all ASIDPools 369 for obj in spec.objs: 370 if isinstance(obj, ASIDPool): 371 asid_pools.append(obj) 372 # Make deterministic 373 asid_pools = sorted(asid_pools, key=lambda obj: obj.name) 374 375 # Check availability of asid_highs; check existing claims 376 for asid_pool in asid_pools: 377 if asid_pool.asid_high is not None: 378 if asid_pool.asid_high < 0 or asid_pool.asid_high >= num_asid_high: 379 raise AllocatorException("invalid asid_high of 0x%x, ASID pool %s" % 380 (asid_pool.asid_high, asid_pool.name)) 381 elif asid_pool.asid_high in free_asid_highs: 382 raise AllocatorException("asid_high 0x%x already in use, can't give to ASID pool %s" % 383 (asid_pool.asid_high, asid_pool.name)) 384 else: 385 free_asid_highs.remove(asid_pool.asid_high) 386 387 # Allocate free_asid_highs 388 for asid_pool in asid_pools: 389 if asid_pool.asid_high is None: 390 if not free_asid_highs: 391 raise AllocatorException("ran out of asid_highs to allocate (next ASID pool: %s)" % 392 asid_pool.name) 393 else: 394 asid_pool.asid_high = free_asid_highs.pop(0) 395 396 # Check that asid_highs are contiguous 397 for asid_pool in asid_pools: 398 if asid_pool.asid_high > 0 and asid_pool.asid_high - 1 in free_asid_highs: 399 raise AllocatorException("asid_high not contiguous: %s wants 0x%x but 0x%x not assigned" % 400 (asid_pool.name, asid_pool.asid_high, asid_pool.asid_high - 1)) 401 402 403class UntypedAllocator(six.with_metaclass(abc.ABCMeta, object)): 404 """ 405 An allocation interface for assigning objects to specific untypeds. 406 Each untyped allocator implements its own policy. 407 """ 408 409 @abc.abstractmethod 410 def add_untyped(self, u, device=False): 411 pass 412 413 def add_device_untyped(self, u): 414 self.add_untyped(u, True) 415 416 @abc.abstractmethod 417 def allocate(self, spec): 418 """ 419 Using the untypeds added to this instance of this class via add_untyped and add_device_untyped, calculate 420 untyped derivations of all objects from spec from those untyped. Throw an AllocationException if the untypeds do 421 not cover the required paddrs, or if the untyped are insufficient to allocate all objects in the spec. 422 423 This method will mutate the spec by adding the used untypeds from the UntypedAllocator as objects, and adding any 424 intermediate untypeds created to maintain alignment or achieve a specific paddr in a seL4_Untyped_Retype call. 425 :param spec: 426 :return: 427 """ 428 pass 429 430 431class AllocQueue: 432 433 def __init__(self, s): 434 assert(isinstance(s, Spec)) 435 # dict of unfungible objects, sorted by paddr. 436 self.unfun_objects = SortedDict(lambda x: -x) 437 # dict of lists of fungible objects, indexed by size_bits 438 self.objects = {} 439 self.sizes = SortedList() 440 # Sort objects secondarily by name, for two reasons: 441 # 1. Determinism (Python sets are not ordered) 442 # 2. Makes it more likely that objects of the same size will be 443 # allocated contiguously by name. For example, the CAmkES DMA 444 # allocator relies on this for large contiguous allocations. 445 # Reversed because we are pushing onto a queue. 446 for o in sorted(s.objs, key=lambda obj: obj.name, reverse=True): 447 if hasattr(o, 'paddr') and o.paddr: 448 self._push_unfun_obj(o) 449 elif o.get_size_bits(): 450 self._push_fun(o) 451 452 def _push_fun(self, o): 453 size_bits = o.get_size_bits() 454 if size_bits in self.objects: 455 self.objects[size_bits].append(o) 456 else: 457 self.objects[size_bits] = collections.deque([o]) 458 self.sizes.add(size_bits) 459 460 def pop_fun(self, size_bits): 461 if size_bits in self.objects: 462 popped = self.objects[size_bits].pop() 463 if not len(self.objects[size_bits]): 464 self.sizes.remove(size_bits) 465 del self.objects[size_bits] 466 return popped 467 468 def _push_unfun_obj(self, o): 469 if o.paddr in self.unfun_objects: 470 old = self.unfun_objects[o.paddr] 471 raise AllocatorException("Duplicate paddr 0x%x (%s, %s)" % (o.paddr, old.name, o.name)) 472 self.unfun_objects[o.paddr] = o 473 474 def pop_unfun(self): 475 if self.unfun_objects: 476 (paddr, obj) = self.unfun_objects.popitem() 477 return obj 478 return None 479 480 def max_size(self): 481 return self.sizes[len(self.sizes) - 1] 482 483 def min_size(self): 484 return self.sizes[0] 485 486 def more_unfun(self): 487 return len(self.unfun_objects) > 0 488 489 def more_fun(self, size_bits=0): 490 if size_bits: 491 return size_bits in self.objects and len(self.objects[size_bits]) 492 return len(self.objects) > 0 493 494 495class BestFitAllocator(UntypedAllocator): 496 """ 497 This allocator works using the following algorithm: 498 499 - sort untyped objects by paddr 500 - sort unfun objects by paddr 501 - collate fun objects by size 502 503 Starting from the first untyped and unfun, allocate appropriately sized fun objects 504 from the untyped until the first unfun paddr is reached. Then take the next unfun object, and take 505 the next untyped when the current one is full. If there are no fun objects to fill gaps with, create 506 placeholder untypeds to acheive the desired retype alignment. 507 """ 508 509 def __init__(self): 510 self.untyped = SortedList() 511 self.ut_iter = None 512 513 @staticmethod 514 def _overlap(before, after): 515 assert isinstance(before, Untyped) 516 assert isinstance(after, Untyped) 517 assert(before.paddr <= after.paddr) 518 return not (before.paddr < after.paddr and ((before.paddr + before.get_size()) < (after.paddr + after.get_size()))) 519 520 @staticmethod 521 def _overlap_exception(u, overlap): 522 assert isinstance(u, Untyped) 523 assert isinstance(overlap, Untyped) 524 raise AllocatorException("New untyped (%x <--> %x) would overlap with existing (%x <--> %x)", 525 u.paddr, u.paddr + u.get_size(), 526 overlap.paddr, overlap.paddr + overlap.get_size()) 527 528 def add_untyped(self, u, device=False): 529 """ 530 Add an untyped object to the allocator. Throw an error if the untyped overlaps with existing untypeds, is 531 missing a paddr, or does not have a paddr aligned to its size. 532 """ 533 assert isinstance(u, Untyped) 534 if u.paddr is None: 535 raise AllocatorException("Untyped has no defined paddr") 536 if not is_aligned(u.paddr, u.get_size_bits()): 537 raise AllocatorException("Untyped at %x is not aligned", u.paddr) 538 539 # check overlap 540 index = self.untyped.bisect_right((u, device)) 541 if index > 0 and self._overlap(self.untyped[index - 1][0], u): 542 self._overlap_exception(u, self.untyped[index - 1][0]) 543 if index < len(self.untyped) and self._overlap(u, self.untyped[index][0]): 544 self._overlap_exception(u, self.untyped[index][0]) 545 546 self.untyped.add((u, device)) 547 548 @staticmethod 549 def _add_placeholder(untyped, size_bits, spec): 550 name = "place_holder_0x%x" % untyped.watermark_paddr() 551 placeholder = Untyped(name, size_bits, untyped.watermark_paddr()) 552 untyped.add_child(placeholder, untyped.watermark_paddr()) 553 spec.add_object(placeholder) 554 555 def _fill_from_objects(self, objects, untyped, size_bits, spec): 556 if not objects.more_fun() or size_bits < objects.min_size(): 557 return size_bits 558 if objects.more_fun(size_bits): 559 # we found an object of size_bits that needs allocating, allocate it! 560 untyped.add_child(objects.pop_fun(size_bits)) 561 return 0 562 else: 563 # no objects of the size we were looking for -- try for two of a smaller size 564 first = self._fill_from_objects(objects, untyped, size_bits - 1, spec) 565 second = self._fill_from_objects(objects, untyped, size_bits - 1, spec) 566 assert(first == 0 or first == size_bits - 1) 567 assert(second == 0 or second == size_bits - 1) 568 if first == second: 569 if first == 0: 570 # we successfully allocated all of the space 571 return 0 572 elif first == size_bits - 1: 573 # we didn't allocate either successfully, return that amount for potential 574 # munging into a larger untyped 575 return size_bits 576 else: 577 # we only managed to allocate one of the smaller objects. Create a 578 # place holder untyped to retain alignment 579 self._add_placeholder(untyped, size_bits - 1, spec) 580 return 0 581 582 def _use_untyped(self, objects, untyped, size_bytes, is_device, spec): 583 assert(untyped.remaining() >= size_bytes) 584 585 while size_bytes: 586 # size_bits is calculated from the minimum alignment between the goal 587 # size_bytes and the watermark. If the watermark is 0 (which is valid) 588 # then just take the alignment of the size_bytes as it's guaranteed to 589 # be smaller. 590 size_bits = min(ctz(size_bytes), ctz(untyped.watermark_paddr()) 591 ) if untyped.watermark_paddr() else ctz(size_bytes) 592 if is_device: 593 self._add_placeholder(untyped, size_bits, spec) 594 else: 595 res = self._fill_from_objects(objects, untyped, size_bits, spec) 596 if res == size_bits: 597 # we failed to fill from objects at all 598 self._add_placeholder(untyped, size_bits, spec) 599 size_bytes -= (1 << size_bits) 600 assert(size_bytes >= 0) 601 602 def _next_ut(self): 603 if not self.ut_iter: 604 self.ut_iter = iter(self.untyped) 605 try: 606 return next(self.ut_iter) 607 except StopIteration: 608 raise AllocatorException("Out of untyped memory to allocate from") 609 610 def allocate(self, s): 611 assert(isinstance(s, Spec)) 612 613 if not len(s.objs): 614 # nothing to do 615 logging.warn("No objects to allocate") 616 return 617 618 # put the objects from spec into the order we need to complete allocation 619 objects = AllocQueue(s) 620 (ut, is_device) = self._next_ut() 621 622 # allocate all of the unfun objects 623 while objects.more_unfun(): 624 paddr, unfun = objects.unfun_objects.peekitem() 625 626 if ut.remaining() == 0: 627 # HACK: Only add untypeds where we actually allocated objects. 628 # This is mainly to skip special device regions which might 629 # appear in the untyped list but are not available at boot. 630 if all(obj.name.startswith('place_holder_') for obj in ut.children): 631 for obj in ut.children: 632 s.objs.remove(obj) 633 else: 634 s.add_object(ut) 635 (ut, is_device) = self._next_ut() 636 637 if paddr < ut.watermark_paddr(): 638 # we've gone past the paddr and didn't find a ut! 639 raise AllocatorException( 640 "No untyped for object: {0} paddr: {1}".format(unfun.name, paddr)) 641 elif paddr >= ut.watermark_paddr() and \ 642 (paddr + unfun.get_size()) <= (ut.paddr + ut.get_size()): 643 # the object we want is in this untyped! 644 self._use_untyped(objects, ut, paddr - ut.watermark_paddr(), is_device, s) 645 ut.add_child(unfun, paddr) 646 objects.unfun_objects.popitem() 647 elif objects.more_fun(): 648 # no objects we want in this untyped, fill it up 649 self._use_untyped(objects, ut, ut.remaining(), is_device, s) 650 else: 651 (ut, is_device) = self._next_ut() 652 653 # we don't allocate device untyped from this point, so 654 # if the last untyped we used was a device and has some children, add it to the new objects, 655 if is_device: 656 if ut.children: 657 s.add_object(ut) 658 elif ut.remaining() > 0: 659 self._use_untyped(objects, ut, ut.remaining(), is_device, s) 660 if not objects.more_fun(): 661 # the allocator below will not run; add ut before we finish 662 s.add_object(ut) 663 664 # now allocate the rest of the objects 665 while objects.more_fun(): 666 (ut, is_device) = self._next_ut() 667 if not is_device: 668 self._use_untyped(objects, ut, ut.remaining(), is_device, s) 669 s.add_object(ut) 670