python-capdl-tool/tests/allocator.py - 3p/sel4/capdl - Git at Google

 #!/usr/bin/env python
 #
 # Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
 #
 # SPDX-License-Identifier: BSD-2-Clause
 #

 from __future__ import absolute_import, division, print_function, \
     unicode_literals

 import unittest

 import hypothesis.strategies as st
 from hypothesis import given

 from capdl import Spec, Untyped, Endpoint, IRQControl, Frame
 from capdl.Allocator import BestFitAllocator, AllocatorException
 from capdl.util import round_up
 from tests import CapdlTestCase


 class TestAllocator(CapdlTestCase):

     def assertValidSpec(self, allocator, spec, ut_size, child_size, children, uts):
         if ut_size >= child_size:
             allocator.allocate(spec)
             # now check if all the children got allocated
             for c in children:
                 if not any(c in ut.children for ut in uts):
                     self.fail("Child {0} not allocated!".format(c))
         else:
             with self.assertRaises(AllocatorException):
                 allocator.allocate(spec)

     @given(st.integers(min_value=4, max_value=64), st.integers(min_value=4, max_value=64))
     def test_alloc_single_fun_obj(self, child_size_bits, ut_size_bits):
         """
         Test allocating a single object from a single untyped. Vary the untyped size and object size,
         and make sure it either succeeds (should always succeed if the untyped size is big enough) or fails
         by throwing an AllocatorException
         """
         allocator = BestFitAllocator()
         spec = Spec()

         ut = Untyped(name="test_ut", size_bits=ut_size_bits, paddr=1 << ut_size_bits)
         allocator.add_untyped(ut)

         child = Untyped(name="child_ut", size_bits=child_size_bits)
         spec.add_object(child)

         self.assertValidSpec(allocator, spec, ut_size_bits, child_size_bits, [child], [ut])

     @staticmethod
     def alloc_children(spec, object_sizes):
         sum = 0
         children = []
         for i, size_bits in enumerate(object_sizes):
             sum += (1 << size_bits)
             child = Untyped(name="child ut {0}".format(i), size_bits=size_bits)
             spec.add_object(child)
             children.append(child)
         return sum, children

     @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))
     def test_alloc_multiple_fun_obj(self, object_sizes, ut_size_bits):
         """Test allocating multiple child objects from a single untyped"""
         allocator = BestFitAllocator()
         spec = Spec()
         (total_child_size, children) = TestAllocator.alloc_children(spec, object_sizes)

         ut = Untyped(name="test_ut", size_bits=ut_size_bits, paddr=1 << ut_size_bits)
         allocator.add_untyped(ut)

         self.assertValidSpec(allocator, spec, 1 << ut_size_bits, total_child_size, children, [ut])

     @given(st.lists(st.integers(min_value=4, max_value=32), max_size=100, min_size=10),
            st.lists(st.integers(min_value=32, max_value=64), max_size=20, min_size=2))
     def test_alloc_multiple_fun_multiple_untyped(self, object_sizes, ut_sizes):
         """Test allocating multiple children from multiple untyped"""
         allocator = BestFitAllocator()
         spec = Spec()
         (total_child_size, children) = TestAllocator.alloc_children(spec, object_sizes)
         untyped = []
         paddr = 0x1
         ut_size = 0

         for i in range(0, len(ut_sizes)):
             size_bits = ut_sizes[i]
             paddr = round_up(paddr, 1 << size_bits)
             ut = Untyped("untyped_{0}".format(i), size_bits=size_bits, paddr=paddr)
             untyped.append(ut)
             allocator.add_untyped(ut)
             paddr += 1 << size_bits
             ut_size += 1 << size_bits

         self.assertValidSpec(allocator, spec, ut_size, total_child_size, children, untyped)

     def test_alloc_no_spec_no_untyped(self):
         """
         Test allocating nothing from nothing works.
         """
         BestFitAllocator().allocate(Spec())

     def test_alloc_no_spec(self):
         """
         Test allocating nothing from something works
         """
         allocator = BestFitAllocator()
         allocator.add_untyped(Untyped(name="test_ut", size_bits=16, paddr=0))
         allocator.allocate(Spec())

     def test_alloc_no_untyped(self):
         """
         Test allocating something from nothing fails elegantly
         """
         ep = Endpoint(name="test_ep")
         spec = Spec()
         spec.add_object(ep)

         with self.assertRaises(AllocatorException):
             BestFitAllocator().allocate(spec)

     def test_alloc_unsized(self):
         """Test allocating an object with no size"""
         irq_ctrl = IRQControl("irq_control")
         spec = Spec()
         spec.add_object(irq_ctrl)
         allocator = BestFitAllocator()
         allocator.add_untyped(Untyped(name="test_ut", size_bits=16, paddr=0x10000))
         allocator.allocate(spec)
         self.assertTrue(irq_ctrl in spec.objs)

     @given(st.integers(min_value=0xA0, max_value=0xD0), st.integers(min_value=0xB0, max_value=0xC0))
     def test_alloc_paddr(self, unfun_paddr, ut_paddr):
         """
         Test allocating a single unfun untyped in and out of bounds of an untyped
         """

         allocator = BestFitAllocator()
         size_bits = 12

         unfun_paddr = unfun_paddr << size_bits
         ut_paddr = ut_paddr << size_bits
         unfun_end = unfun_paddr + (1 << size_bits)
         ut_end = ut_paddr + (1 << size_bits)

         parent = Untyped("parent_ut", size_bits=size_bits, paddr=ut_paddr)
         allocator.add_untyped(parent)
         spec = Spec()
         child = Untyped("child_ut", size_bits=size_bits, paddr=unfun_paddr)
         spec.add_object(child)

         if unfun_paddr >= ut_paddr and unfun_end <= ut_end:
             self.assertValidSpec(allocator, spec, size_bits, size_bits, [child], [parent])
         else:
             with self.assertRaises(AllocatorException):
                 allocator.allocate(spec)

     @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))
     def test_device_ut_only(self, ut_sizes, obj_sizes):
         """
         Test allocating fun objects from only device untypeds
         """
         allocator = BestFitAllocator()
         paddr = 0x1
         for i in range(0, len(ut_sizes)):
             paddr = round_up(paddr, 1 << ut_sizes[i])
             allocator.add_device_untyped(
                 Untyped("device_untyped_{0}".format(i), size_bits=ut_sizes[i], paddr=paddr))
             paddr += 1 << ut_sizes[i]

         spec = Spec()
         for i in range(0, len(obj_sizes)):
             spec.add_object(Untyped("obj_untyped_{0}".format(i), size_bits=obj_sizes[i]))

         with self.assertRaises(AllocatorException):
             allocator.allocate(spec)

     @given(st.integers(min_value=0, max_value=3))
     def test_overlapping_paddr_smaller(self, offset):
         """Test allocating unfun objects with overlapping paddrs, where the overlapping paddr is from a smaller
         object """

         paddr = 0xAAAA0000
         size_bits = 16
         overlap_paddr = paddr + offset * (1 << (size_bits-2))

         allocator = BestFitAllocator()
         allocator.add_untyped(Untyped("parent", paddr=paddr, size_bits=size_bits))

         spec = Spec()
         spec.add_object(Untyped("child", paddr=paddr, size_bits=size_bits))
         spec.add_object(Untyped("overlap_child", paddr=overlap_paddr, size_bits=size_bits-2))

         with self.assertRaises(AllocatorException):
             allocator.allocate(spec)

     def test_overlapping_paddr_larger(self):
         """Test allocating unfun objects with overlapping paddrs, where the overlapping paddr is from a larger object"""
         allocator = BestFitAllocator()

         paddr = 0xAAAA0000
         allocator.add_untyped(Untyped("deadbeef", size_bits=16, paddr=paddr))

         spec = Spec()
         spec.add_object(Untyped("obj_untyped_1", size_bits=14, paddr=paddr + 2 * (1 << 15)))
         spec.add_object(Untyped("obj_untyped_2", size_bits=15, paddr=paddr))

         with self.assertRaises(AllocatorException):
             allocator.allocate(spec)

     @given(st.lists(st.integers(min_value=4, max_value=16), min_size=1, max_size=1000))
     def test_placeholder_uts(self, sizes):
         """
         Test allocating a collection of unfun objects that do not align and have placeholder uts between them
         """
         allocator = BestFitAllocator()
         start_paddr = 1 << (max(sizes) + len(sizes).bit_length())
         paddr = start_paddr
         ut_size = 0

         children = []
         spec = Spec()
         for i in range(0, len(sizes)):
             paddr = round_up(paddr, 1 << sizes[i])
             ut = Untyped("ut_{0}".format(i), size_bits=sizes[i], paddr=paddr)
             spec.add_object(ut)
             paddr += 1 << sizes[i]
             ut_size += 1 << sizes[i]
             children.append(ut)

         ut_size_bits = (paddr - start_paddr).bit_length()
         ut = Untyped("ut_parent", size_bits=ut_size_bits, paddr=start_paddr)
         allocator.add_untyped(ut)
         self.assertValidSpec(allocator, spec, 1 << ut_size_bits, ut_size, children, [ut])

     def test_regression_unfun_at_end(self):
         """
         Ensure that if an unfun object is the last to get allocated,
         its root ut is included in the spec.
         """
         allocator = BestFitAllocator()
         root_ut_A = Untyped("root_ut_A", size_bits=16, paddr=0x10000)
         root_ut_B = Untyped("root_ut_B", size_bits=16, paddr=0x20000)
         allocator.add_untyped(root_ut_A)
         allocator.add_untyped(root_ut_B)

         spec = Spec()
         my_frame_A0 = Frame("my_frame_A0")
         my_frame_A1 = Frame("my_frame_A1")
         my_pinned_frame_B = Frame("my_pinned_frame_B", paddr=0x20000)
         spec.add_object(my_frame_A0)
         spec.add_object(my_frame_A1)
         spec.add_object(my_pinned_frame_B)

         allocator.allocate(spec)
         self.assertIn(root_ut_B, spec.objs)  # main test
         # other tests:
         for obj in (root_ut_A, root_ut_B, my_frame_A0, my_frame_A1, my_pinned_frame_B):
             self.assertIn(obj, spec.objs)
         for obj in (my_frame_A0, my_frame_A1):
             self.assertIn(obj, root_ut_A.children)
         for obj in (my_pinned_frame_B,):
             self.assertIn(obj, root_ut_B.children)


 if __name__ == '__main__':
     unittest.main()
	#!/usr/bin/env python
	#
	# Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
	#
	# SPDX-License-Identifier: BSD-2-Clause
	#

	from __future__ import absolute_import, division, print_function, \
	unicode_literals

	import unittest

	import hypothesis.strategies as st
	from hypothesis import given

	from capdl import Spec, Untyped, Endpoint, IRQControl, Frame
	from capdl.Allocator import BestFitAllocator, AllocatorException
	from capdl.util import round_up
	from tests import CapdlTestCase


	class TestAllocator(CapdlTestCase):

	def assertValidSpec(self, allocator, spec, ut_size, child_size, children, uts):
	if ut_size >= child_size:
	allocator.allocate(spec)
	# now check if all the children got allocated
	for c in children:
	if not any(c in ut.children for ut in uts):
	self.fail("Child {0} not allocated!".format(c))
	else:
	with self.assertRaises(AllocatorException):
	allocator.allocate(spec)

	@given(st.integers(min_value=4, max_value=64), st.integers(min_value=4, max_value=64))
	def test_alloc_single_fun_obj(self, child_size_bits, ut_size_bits):
	"""
	Test allocating a single object from a single untyped. Vary the untyped size and object size,
	and make sure it either succeeds (should always succeed if the untyped size is big enough) or fails
	by throwing an AllocatorException
	"""
	allocator = BestFitAllocator()
	spec = Spec()

	ut = Untyped(name="test_ut", size_bits=ut_size_bits, paddr=1 << ut_size_bits)
	allocator.add_untyped(ut)

	child = Untyped(name="child_ut", size_bits=child_size_bits)
	spec.add_object(child)

	self.assertValidSpec(allocator, spec, ut_size_bits, child_size_bits, [child], [ut])

	@staticmethod
	def alloc_children(spec, object_sizes):
	sum = 0
	children = []
	for i, size_bits in enumerate(object_sizes):
	sum += (1 << size_bits)
	child = Untyped(name="child ut {0}".format(i), size_bits=size_bits)
	spec.add_object(child)
	children.append(child)
	return sum, children

	@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))
	def test_alloc_multiple_fun_obj(self, object_sizes, ut_size_bits):
	"""Test allocating multiple child objects from a single untyped"""
	allocator = BestFitAllocator()
	spec = Spec()
	(total_child_size, children) = TestAllocator.alloc_children(spec, object_sizes)

	ut = Untyped(name="test_ut", size_bits=ut_size_bits, paddr=1 << ut_size_bits)
	allocator.add_untyped(ut)

	self.assertValidSpec(allocator, spec, 1 << ut_size_bits, total_child_size, children, [ut])

	@given(st.lists(st.integers(min_value=4, max_value=32), max_size=100, min_size=10),
	st.lists(st.integers(min_value=32, max_value=64), max_size=20, min_size=2))
	def test_alloc_multiple_fun_multiple_untyped(self, object_sizes, ut_sizes):
	"""Test allocating multiple children from multiple untyped"""
	allocator = BestFitAllocator()
	spec = Spec()
	(total_child_size, children) = TestAllocator.alloc_children(spec, object_sizes)
	untyped = []
	paddr = 0x1
	ut_size = 0

	for i in range(0, len(ut_sizes)):
	size_bits = ut_sizes[i]
	paddr = round_up(paddr, 1 << size_bits)
	ut = Untyped("untyped_{0}".format(i), size_bits=size_bits, paddr=paddr)
	untyped.append(ut)
	allocator.add_untyped(ut)
	paddr += 1 << size_bits
	ut_size += 1 << size_bits

	self.assertValidSpec(allocator, spec, ut_size, total_child_size, children, untyped)

	def test_alloc_no_spec_no_untyped(self):
	"""
	Test allocating nothing from nothing works.
	"""
	BestFitAllocator().allocate(Spec())

	def test_alloc_no_spec(self):
	"""
	Test allocating nothing from something works
	"""
	allocator = BestFitAllocator()
	allocator.add_untyped(Untyped(name="test_ut", size_bits=16, paddr=0))
	allocator.allocate(Spec())

	def test_alloc_no_untyped(self):
	"""
	Test allocating something from nothing fails elegantly
	"""
	ep = Endpoint(name="test_ep")
	spec = Spec()
	spec.add_object(ep)

	with self.assertRaises(AllocatorException):
	BestFitAllocator().allocate(spec)

	def test_alloc_unsized(self):
	"""Test allocating an object with no size"""
	irq_ctrl = IRQControl("irq_control")
	spec = Spec()
	spec.add_object(irq_ctrl)
	allocator = BestFitAllocator()
	allocator.add_untyped(Untyped(name="test_ut", size_bits=16, paddr=0x10000))
	allocator.allocate(spec)
	self.assertTrue(irq_ctrl in spec.objs)

	@given(st.integers(min_value=0xA0, max_value=0xD0), st.integers(min_value=0xB0, max_value=0xC0))
	def test_alloc_paddr(self, unfun_paddr, ut_paddr):
	"""
	Test allocating a single unfun untyped in and out of bounds of an untyped
	"""

	allocator = BestFitAllocator()
	size_bits = 12

	unfun_paddr = unfun_paddr << size_bits
	ut_paddr = ut_paddr << size_bits
	unfun_end = unfun_paddr + (1 << size_bits)
	ut_end = ut_paddr + (1 << size_bits)

	parent = Untyped("parent_ut", size_bits=size_bits, paddr=ut_paddr)
	allocator.add_untyped(parent)
	spec = Spec()
	child = Untyped("child_ut", size_bits=size_bits, paddr=unfun_paddr)
	spec.add_object(child)

	if unfun_paddr >= ut_paddr and unfun_end <= ut_end:
	self.assertValidSpec(allocator, spec, size_bits, size_bits, [child], [parent])
	else:
	with self.assertRaises(AllocatorException):
	allocator.allocate(spec)

	@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))
	def test_device_ut_only(self, ut_sizes, obj_sizes):
	"""
	Test allocating fun objects from only device untypeds
	"""
	allocator = BestFitAllocator()
	paddr = 0x1
	for i in range(0, len(ut_sizes)):
	paddr = round_up(paddr, 1 << ut_sizes[i])
	allocator.add_device_untyped(
	Untyped("device_untyped_{0}".format(i), size_bits=ut_sizes[i], paddr=paddr))
	paddr += 1 << ut_sizes[i]

	spec = Spec()
	for i in range(0, len(obj_sizes)):
	spec.add_object(Untyped("obj_untyped_{0}".format(i), size_bits=obj_sizes[i]))

	with self.assertRaises(AllocatorException):
	allocator.allocate(spec)

	@given(st.integers(min_value=0, max_value=3))
	def test_overlapping_paddr_smaller(self, offset):
	"""Test allocating unfun objects with overlapping paddrs, where the overlapping paddr is from a smaller
	object """

	paddr = 0xAAAA0000
	size_bits = 16
	overlap_paddr = paddr + offset * (1 << (size_bits-2))

	allocator = BestFitAllocator()
	allocator.add_untyped(Untyped("parent", paddr=paddr, size_bits=size_bits))

	spec = Spec()
	spec.add_object(Untyped("child", paddr=paddr, size_bits=size_bits))
	spec.add_object(Untyped("overlap_child", paddr=overlap_paddr, size_bits=size_bits-2))

	with self.assertRaises(AllocatorException):
	allocator.allocate(spec)

	def test_overlapping_paddr_larger(self):
	"""Test allocating unfun objects with overlapping paddrs, where the overlapping paddr is from a larger object"""
	allocator = BestFitAllocator()

	paddr = 0xAAAA0000
	allocator.add_untyped(Untyped("deadbeef", size_bits=16, paddr=paddr))

	spec = Spec()
	spec.add_object(Untyped("obj_untyped_1", size_bits=14, paddr=paddr + 2 * (1 << 15)))
	spec.add_object(Untyped("obj_untyped_2", size_bits=15, paddr=paddr))

	with self.assertRaises(AllocatorException):
	allocator.allocate(spec)

	@given(st.lists(st.integers(min_value=4, max_value=16), min_size=1, max_size=1000))
	def test_placeholder_uts(self, sizes):
	"""
	Test allocating a collection of unfun objects that do not align and have placeholder uts between them
	"""
	allocator = BestFitAllocator()
	start_paddr = 1 << (max(sizes) + len(sizes).bit_length())
	paddr = start_paddr
	ut_size = 0

	children = []
	spec = Spec()
	for i in range(0, len(sizes)):
	paddr = round_up(paddr, 1 << sizes[i])
	ut = Untyped("ut_{0}".format(i), size_bits=sizes[i], paddr=paddr)
	spec.add_object(ut)
	paddr += 1 << sizes[i]
	ut_size += 1 << sizes[i]
	children.append(ut)

	ut_size_bits = (paddr - start_paddr).bit_length()
	ut = Untyped("ut_parent", size_bits=ut_size_bits, paddr=start_paddr)
	allocator.add_untyped(ut)
	self.assertValidSpec(allocator, spec, 1 << ut_size_bits, ut_size, children, [ut])

	def test_regression_unfun_at_end(self):
	"""
	Ensure that if an unfun object is the last to get allocated,
	its root ut is included in the spec.
	"""
	allocator = BestFitAllocator()
	root_ut_A = Untyped("root_ut_A", size_bits=16, paddr=0x10000)
	root_ut_B = Untyped("root_ut_B", size_bits=16, paddr=0x20000)
	allocator.add_untyped(root_ut_A)
	allocator.add_untyped(root_ut_B)

	spec = Spec()
	my_frame_A0 = Frame("my_frame_A0")
	my_frame_A1 = Frame("my_frame_A1")
	my_pinned_frame_B = Frame("my_pinned_frame_B", paddr=0x20000)
	spec.add_object(my_frame_A0)
	spec.add_object(my_frame_A1)
	spec.add_object(my_pinned_frame_B)

	allocator.allocate(spec)
	self.assertIn(root_ut_B, spec.objs) # main test
	# other tests:
	for obj in (root_ut_A, root_ut_B, my_frame_A0, my_frame_A1, my_pinned_frame_B):
	self.assertIn(obj, spec.objs)
	for obj in (my_frame_A0, my_frame_A1):
	self.assertIn(obj, root_ut_A.children)
	for obj in (my_pinned_frame_B,):
	self.assertIn(obj, root_ut_B.children)


	if __name__ == '__main__':
	unittest.main()