1#!/usr/bin/env python
2#
3# Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
4#
5# SPDX-License-Identifier: BSD-2-Clause
6#
7
8from __future__ import absolute_import, division, print_function, \
9    unicode_literals
10
11import unittest
12
13import hypothesis.strategies as st
14from hypothesis import given
15
16from capdl import Spec, Untyped, Endpoint, IRQControl, Frame
17from capdl.Allocator import BestFitAllocator, AllocatorException
18from capdl.util import round_up
19from tests import CapdlTestCase
20
21
22class TestAllocator(CapdlTestCase):
23
24    def assertValidSpec(self, allocator, spec, ut_size, child_size, children, uts):
25        if ut_size >= child_size:
26            allocator.allocate(spec)
27            # now check if all the children got allocated
28            for c in children:
29                if not any(c in ut.children for ut in uts):
30                    self.fail("Child {0} not allocated!".format(c))
31        else:
32            with self.assertRaises(AllocatorException):
33                allocator.allocate(spec)
34
35    @given(st.integers(min_value=4, max_value=64), st.integers(min_value=4, max_value=64))
36    def test_alloc_single_fun_obj(self, child_size_bits, ut_size_bits):
37        """
38        Test allocating a single object from a single untyped. Vary the untyped size and object size,
39        and make sure it either succeeds (should always succeed if the untyped size is big enough) or fails
40        by throwing an AllocatorException
41        """
42        allocator = BestFitAllocator()
43        spec = Spec()
44
45        ut = Untyped(name="test_ut", size_bits=ut_size_bits, paddr=1 << ut_size_bits)
46        allocator.add_untyped(ut)
47
48        child = Untyped(name="child_ut", size_bits=child_size_bits)
49        spec.add_object(child)
50
51        self.assertValidSpec(allocator, spec, ut_size_bits, child_size_bits, [child], [ut])
52
53    @staticmethod
54    def alloc_children(spec, object_sizes):
55        sum = 0
56        children = []
57        for i, size_bits in enumerate(object_sizes):
58            sum += (1 << size_bits)
59            child = Untyped(name="child ut {0}".format(i), size_bits=size_bits)
60            spec.add_object(child)
61            children.append(child)
62        return sum, children
63
64    @given(st.lists(st.integers(min_value=4, max_value=64), max_size=100, min_size=10), st.integers(min_value=4, max_value=64))
65    def test_alloc_multiple_fun_obj(self, object_sizes, ut_size_bits):
66        """Test allocating multiple child objects from a single untyped"""
67        allocator = BestFitAllocator()
68        spec = Spec()
69        (total_child_size, children) = TestAllocator.alloc_children(spec, object_sizes)
70
71        ut = Untyped(name="test_ut", size_bits=ut_size_bits, paddr=1 << ut_size_bits)
72        allocator.add_untyped(ut)
73
74        self.assertValidSpec(allocator, spec, 1 << ut_size_bits, total_child_size, children, [ut])
75
76    @given(st.lists(st.integers(min_value=4, max_value=32), max_size=100, min_size=10),
77           st.lists(st.integers(min_value=32, max_value=64), max_size=20, min_size=2))
78    def test_alloc_multiple_fun_multiple_untyped(self, object_sizes, ut_sizes):
79        """Test allocating multiple children from multiple untyped"""
80        allocator = BestFitAllocator()
81        spec = Spec()
82        (total_child_size, children) = TestAllocator.alloc_children(spec, object_sizes)
83        untyped = []
84        paddr = 0x1
85        ut_size = 0
86
87        for i in range(0, len(ut_sizes)):
88            size_bits = ut_sizes[i]
89            paddr = round_up(paddr, 1 << size_bits)
90            ut = Untyped("untyped_{0}".format(i), size_bits=size_bits, paddr=paddr)
91            untyped.append(ut)
92            allocator.add_untyped(ut)
93            paddr += 1 << size_bits
94            ut_size += 1 << size_bits
95
96        self.assertValidSpec(allocator, spec, ut_size, total_child_size, children, untyped)
97
98    def test_alloc_no_spec_no_untyped(self):
99        """
100        Test allocating nothing from nothing works.
101        """
102        BestFitAllocator().allocate(Spec())
103
104    def test_alloc_no_spec(self):
105        """
106        Test allocating nothing from something works
107        """
108        allocator = BestFitAllocator()
109        allocator.add_untyped(Untyped(name="test_ut", size_bits=16, paddr=0))
110        allocator.allocate(Spec())
111
112    def test_alloc_no_untyped(self):
113        """
114        Test allocating something from nothing fails elegantly
115        """
116        ep = Endpoint(name="test_ep")
117        spec = Spec()
118        spec.add_object(ep)
119
120        with self.assertRaises(AllocatorException):
121            BestFitAllocator().allocate(spec)
122
123    def test_alloc_unsized(self):
124        """Test allocating an object with no size"""
125        irq_ctrl = IRQControl("irq_control")
126        spec = Spec()
127        spec.add_object(irq_ctrl)
128        allocator = BestFitAllocator()
129        allocator.add_untyped(Untyped(name="test_ut", size_bits=16, paddr=0x10000))
130        allocator.allocate(spec)
131        self.assertTrue(irq_ctrl in spec.objs)
132
133    @given(st.integers(min_value=0xA0, max_value=0xD0), st.integers(min_value=0xB0, max_value=0xC0))
134    def test_alloc_paddr(self, unfun_paddr, ut_paddr):
135        """
136        Test allocating a single unfun untyped in and out of bounds of an untyped
137        """
138
139        allocator = BestFitAllocator()
140        size_bits = 12
141
142        unfun_paddr = unfun_paddr << size_bits
143        ut_paddr = ut_paddr << size_bits
144        unfun_end = unfun_paddr + (1 << size_bits)
145        ut_end = ut_paddr + (1 << size_bits)
146
147        parent = Untyped("parent_ut", size_bits=size_bits, paddr=ut_paddr)
148        allocator.add_untyped(parent)
149        spec = Spec()
150        child = Untyped("child_ut", size_bits=size_bits, paddr=unfun_paddr)
151        spec.add_object(child)
152
153        if unfun_paddr >= ut_paddr and unfun_end <= ut_end:
154            self.assertValidSpec(allocator, spec, size_bits, size_bits, [child], [parent])
155        else:
156            with self.assertRaises(AllocatorException):
157                allocator.allocate(spec)
158
159    @given(st.lists(st.integers(min_value=4, max_value=64), min_size=1), st.lists(st.integers(min_value=4, max_value=64), min_size=1))
160    def test_device_ut_only(self, ut_sizes, obj_sizes):
161        """
162        Test allocating fun objects from only device untypeds
163        """
164        allocator = BestFitAllocator()
165        paddr = 0x1
166        for i in range(0, len(ut_sizes)):
167            paddr = round_up(paddr, 1 << ut_sizes[i])
168            allocator.add_device_untyped(
169                Untyped("device_untyped_{0}".format(i), size_bits=ut_sizes[i], paddr=paddr))
170            paddr += 1 << ut_sizes[i]
171
172        spec = Spec()
173        for i in range(0, len(obj_sizes)):
174            spec.add_object(Untyped("obj_untyped_{0}".format(i), size_bits=obj_sizes[i]))
175
176        with self.assertRaises(AllocatorException):
177            allocator.allocate(spec)
178
179    @given(st.integers(min_value=0, max_value=3))
180    def test_overlapping_paddr_smaller(self, offset):
181        """Test allocating unfun objects with overlapping paddrs, where the overlapping paddr is from a smaller
182        object """
183
184        paddr = 0xAAAA0000
185        size_bits = 16
186        overlap_paddr = paddr + offset * (1 << (size_bits-2))
187
188        allocator = BestFitAllocator()
189        allocator.add_untyped(Untyped("parent", paddr=paddr, size_bits=size_bits))
190
191        spec = Spec()
192        spec.add_object(Untyped("child", paddr=paddr, size_bits=size_bits))
193        spec.add_object(Untyped("overlap_child", paddr=overlap_paddr, size_bits=size_bits-2))
194
195        with self.assertRaises(AllocatorException):
196            allocator.allocate(spec)
197
198    def test_overlapping_paddr_larger(self):
199        """Test allocating unfun objects with overlapping paddrs, where the overlapping paddr is from a larger object"""
200        allocator = BestFitAllocator()
201
202        paddr = 0xAAAA0000
203        allocator.add_untyped(Untyped("deadbeef", size_bits=16, paddr=paddr))
204
205        spec = Spec()
206        spec.add_object(Untyped("obj_untyped_1", size_bits=14, paddr=paddr + 2 * (1 << 15)))
207        spec.add_object(Untyped("obj_untyped_2", size_bits=15, paddr=paddr))
208
209        with self.assertRaises(AllocatorException):
210            allocator.allocate(spec)
211
212    @given(st.lists(st.integers(min_value=4, max_value=16), min_size=1, max_size=1000))
213    def test_placeholder_uts(self, sizes):
214        """
215        Test allocating a collection of unfun objects that do not align and have placeholder uts between them
216        """
217        allocator = BestFitAllocator()
218        start_paddr = 1 << (max(sizes) + len(sizes).bit_length())
219        paddr = start_paddr
220        ut_size = 0
221
222        children = []
223        spec = Spec()
224        for i in range(0, len(sizes)):
225            paddr = round_up(paddr, 1 << sizes[i])
226            ut = Untyped("ut_{0}".format(i), size_bits=sizes[i], paddr=paddr)
227            spec.add_object(ut)
228            paddr += 1 << sizes[i]
229            ut_size += 1 << sizes[i]
230            children.append(ut)
231
232        ut_size_bits = (paddr - start_paddr).bit_length()
233        ut = Untyped("ut_parent", size_bits=ut_size_bits, paddr=start_paddr)
234        allocator.add_untyped(ut)
235        self.assertValidSpec(allocator, spec, 1 << ut_size_bits, ut_size, children, [ut])
236
237    def test_regression_unfun_at_end(self):
238        """
239        Ensure that if an unfun object is the last to get allocated,
240        its root ut is included in the spec.
241        """
242        allocator = BestFitAllocator()
243        root_ut_A = Untyped("root_ut_A", size_bits=16, paddr=0x10000)
244        root_ut_B = Untyped("root_ut_B", size_bits=16, paddr=0x20000)
245        allocator.add_untyped(root_ut_A)
246        allocator.add_untyped(root_ut_B)
247
248        spec = Spec()
249        my_frame_A0 = Frame("my_frame_A0")
250        my_frame_A1 = Frame("my_frame_A1")
251        my_pinned_frame_B = Frame("my_pinned_frame_B", paddr=0x20000)
252        spec.add_object(my_frame_A0)
253        spec.add_object(my_frame_A1)
254        spec.add_object(my_pinned_frame_B)
255
256        allocator.allocate(spec)
257        self.assertIn(root_ut_B, spec.objs)  # main test
258        # other tests:
259        for obj in (root_ut_A, root_ut_B, my_frame_A0, my_frame_A1, my_pinned_frame_B):
260            self.assertIn(obj, spec.objs)
261        for obj in (my_frame_A0, my_frame_A1):
262            self.assertIn(obj, root_ut_A.children)
263        for obj in (my_pinned_frame_B,):
264            self.assertIn(obj, root_ut_B.children)
265
266
267if __name__ == '__main__':
268    unittest.main()
269