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