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