tests/list-test.cc - 3p/cheriot-rtos - Git at Google

 // Copyright Microsoft and CHERIoT Contributors.
 // SPDX-License-Identifier: MIT

 #define TEST_NAME "List"
 #include "tests.hh"
 #include <ds/linked_list.h>

 using CHERI::Capability;

 namespace
 {
 	/**
 	 * Example class we want to link into a doubly linked list.
 	 *
 	 * The class contains a single integer for the purposes of the test.
 	 *
 	 * `ds::linked_list` is an intrusive list: we embed the list node into
 	 * the class we want to link.  There are various implementations of the
 	 * list nodes. Here we use the most simple one
 	 * (`ds::linked_list::cell::Pointer`) which relies on two pointers
 	 * `next` and `prev`.
 	 */
 	struct LinkedObject
 	{
 		using ObjectRing = ds::linked_list::cell::Pointer;

 		int data;
 		/**
 		 * List node: links objects into the doubly-linked list.
 		 */
 		ObjectRing ring __attribute__((__cheri_no_subobject_bounds__)) = {};
 		/**
 		 * Container-of for the above field. This is used to retrieve the
 		 * corresponding object from a list element.
 		 */
 		__always_inline static struct LinkedObject *from_ring(ObjectRing *c)
 		{
 			return reinterpret_cast<struct LinkedObject *>(
 			  reinterpret_cast<uintptr_t>(c) -
 			  offsetof(struct LinkedObject, ring));
 		}
 	};
 } // namespace

 /**
  * `ds::linked_list`s are circular, doubly-linked collections. While they can
  * stand on their own as rings of objects, it is sometimes convenient to create
  * a designated 'sentinel' node that participates in the collection without
  * being part of the collection:
  *
  * - a sentinel node provides pointers to the effective head and tail of the
  *   collection (the successor and predecessor of the sentinel, respectively)
  *
  * - a sentinel allows not having to special-case 'the collection is empty' in
  *   as many places as some other representations (that is, collections with
  *   sentinels need fewer NULL pointer checks)
  *
  * - a sentinel provides many handy functions to operate on the list
  *
  * Note: do not allocate the sentinel (or any list cell) on the stack, because
  * it would lead some list nodes to hold a pointer to a stack value, i.e., to
  * an invalid capability. This would manifest as a crash while using the list.
  */
 ds::linked_list::Sentinel<LinkedObject::ObjectRing> objects = {};

 void test_list()
 {
 	debug_log("Testing the list implementation.");

 	// Number of elements we will add to the list in the test. Must be
 	// divisible by two.
 	static constexpr int NumberOfListElements = 30;

 	auto heapAtStart = heap_quota_remaining(MALLOC_CAPABILITY);

 	TEST(objects.is_empty(), "Newly created list is not empty");

 	// Create heap-allocated objects, and link them into the linked list.
 	for (int i = 0; i < NumberOfListElements; i++)
 	{
 		Timeout       t{UnlimitedTimeout};
 		LinkedObject *o = static_cast<LinkedObject *>(
 		  heap_allocate(&t, MALLOC_CAPABILITY, sizeof(LinkedObject)));
 		TEST(Capability{o}.is_valid(), "Cannot allocate linked object");

 		// Use the object integer as an index.
 		o->data = i;
 		// The list node has not yet been initialized.
 		o->ring.cell_reset();

 		// Test that we can retrieve the object from the link node and
 		// that this results in a capability which is identical to what
 		// we got from the allocator.
 		TEST(Capability{o} == Capability{LinkedObject::from_ring(&(o->ring))},
 		     "The container of method does not return the right object");
 		TEST(Capability{LinkedObject::from_ring(&(o->ring))}.is_valid(),
 		     "Capability retrieved from `from_ring` is invalid");

 		// Add the new object to the list through the sentinel node.
 		objects.append(&(o->ring));
 	}

 	TEST(!objects.is_empty(), "The list is empty after adding objects");

 	// Test that the sentinel can be used to retrieve the first and last
 	// elements of the list as expected.
 	TEST(LinkedObject::from_ring(objects.last())->data ==
 	       NumberOfListElements - 1,
 	     "Last element of the list is incorrect, expected {}, got {}",
 	     NumberOfListElements - 1,
 	     LinkedObject::from_ring(objects.last())->data);
 	TEST(objects.last()->cell_next() == &objects.sentinel,
 	     "Last element in not followed by the sentinel");
 	TEST(objects.last() == objects.sentinel.cell_prev(),
 	     "Sentinel is not preceeded by the last element");

 	TEST(LinkedObject::from_ring(objects.first())->data == 0,
 	     "First element of the list is incorrect, expected {}, got {}",
 	     0,
 	     LinkedObject::from_ring(objects.last())->data);
 	TEST(objects.first()->cell_prev() == &objects.sentinel,
 	     "First element in not preceeded by the sentinel");
 	TEST(objects.first() == objects.sentinel.cell_next(),
 	     "Sentinel is not followed by the first element");

 	// Test that we can go through the list by following `cell_next`
 	// pointers as expected.
 	int counter = 0;
 	// While at it, retrieve a pointer to the middle element which we will
 	// use to cleave the list later.
 	LinkedObject::ObjectRing *middle = nullptr;
 	// We reach the sentinel when we have gone through all elements of the
 	// list.
 	for (auto *cell = objects.first(); cell != &objects.sentinel;
 	     cell       = cell->cell_next())
 	{
 		struct LinkedObject *o = LinkedObject::from_ring(cell);
 		TEST(
 		  o->data == counter,
 		  "Ordering of elements in the list is incorrect, expected {}, got {}",
 		  o->data,
 		  counter);
 		if (counter == NumberOfListElements / 2)
 		{
 			middle = cell;
 		}
 		counter++;
 	}

 	TEST(middle != nullptr, "Could not find middle element of the list");

 	// Cut the list in the middle. `middle` is now a handle to the (valid)
 	// collection of objects [middle, last] that have become detached from
 	// the sentinel.
 	ds::linked_list::remove(middle, objects.last());

 	// This should leave us with a list of size `NumberOfListElements / 2`.
 	counter = 0;
 	for (auto *cell = objects.first(); cell != &objects.sentinel;
 	     cell       = cell->cell_next())
 	{
 		counter++;
 	}
 	TEST(counter == NumberOfListElements / 2,
 	     "Cleaving didn't leave a list with the right number of elements");

 	// Now remove (and free) a single element from the list.
 	TEST(LinkedObject::from_ring(objects.first())->data == 0,
 	     "First element of the list is incorrect, expected {}, got {}",
 	     0,
 	     LinkedObject::from_ring(objects.first())->data);
 	// We must keep a reference to the removed object to free it, as
 	// `remove` returns a pointer to the residual list (return value which
 	// we do not use here), not to the removed element.
 	LinkedObject::ObjectRing *removedCell = objects.first();
 	ds::linked_list::remove(objects.first());
 	heap_free(MALLOC_CAPABILITY, LinkedObject::from_ring(removedCell));
 	TEST(LinkedObject::from_ring(objects.first())->data == 1,
 	     "First element of the list is incorrect after removing the first "
 	     "element, expected {}, got {}",
 	     1,
 	     LinkedObject::from_ring(objects.first())->data);
 	TEST(objects.first()->cell_prev() == &objects.sentinel,
 	     "First element in not preceeded by the sentinel after removing the "
 	     "first object");

 	// We are done with the list, free it.
 	counter                        = 0;
 	LinkedObject::ObjectRing *cell = objects.first();
 	while (cell != &objects.sentinel)
 	{
 		struct LinkedObject *o = LinkedObject::from_ring(cell);
 		cell                   = cell->cell_next();
 		heap_free(MALLOC_CAPABILITY, o);
 		counter++;
 	}

 	TEST(counter == (NumberOfListElements / 2) - 1,
 	     "Incorrect number of elements freed, expected {}, got {}",
 	     (NumberOfListElements / 2) - 1,
 	     counter);

 	// Now that the list is freed, reset the sentinel.
 	objects.reset();

 	TEST(objects.is_empty(), "Reset-ed list is not empty");

 	// We must also free the span of the list which we removed earlier.
 	// This time use the `::search` method to go through the collection.
 	ds::linked_list::search(
 	  middle, [&counter](LinkedObject::ObjectRing *&cell) {
 		  // `unsafe_remove` does not update the node pointers of the
 		  // removed cell. This is great here because we will free the
 		  // object anyways. We could also use `remove` here.
 		  auto l = ds::linked_list::unsafe_remove(cell);
 		  heap_free(MALLOC_CAPABILITY, LinkedObject::from_ring(cell));
 		  // `l` is the predecessor of `cell` in the residual ring, so
 		  // this does exactly what we want when `::search` iterates.
 		  cell = l;
 		  counter++;
 		  return false;
 	  });
 	// `::search` does not visit the element passed (`middle`)
 	heap_free(MALLOC_CAPABILITY, LinkedObject::from_ring(middle));
 	counter++;

 	TEST(counter == NumberOfListElements - 1,
 	     "Incorrect number of elements freed, expected {}, got {}",
 	     NumberOfListElements - 1,
 	     counter);

 	// Check that we didn't leak anything in the process
 	auto heapAtEnd = heap_quota_remaining(MALLOC_CAPABILITY);
 	TEST(heapAtStart == heapAtEnd,
 	     "The list leaked {} bytes ({} vs. {})",
 	     heapAtEnd - heapAtStart,
 	     heapAtStart,
 	     heapAtEnd);

 	debug_log("Done testing the list.");
 }
	// Copyright Microsoft and CHERIoT Contributors.
	// SPDX-License-Identifier: MIT

	#define TEST_NAME "List"
	#include "tests.hh"
	#include <ds/linked_list.h>

	using CHERI::Capability;

	namespace
	{
	/**
	* Example class we want to link into a doubly linked list.
	*
	* The class contains a single integer for the purposes of the test.
	*
	* `ds::linked_list` is an intrusive list: we embed the list node into
	* the class we want to link. There are various implementations of the
	* list nodes. Here we use the most simple one
	* (`ds::linked_list::cell::Pointer`) which relies on two pointers
	* `next` and `prev`.
	*/
	struct LinkedObject
	{
	using ObjectRing = ds::linked_list::cell::Pointer;

	int data;
	/**
	* List node: links objects into the doubly-linked list.
	*/
	ObjectRing ring __attribute__((__cheri_no_subobject_bounds__)) = {};
	/**
	* Container-of for the above field. This is used to retrieve the
	* corresponding object from a list element.
	*/
	__always_inline static struct LinkedObject from_ring(ObjectRing c)
	{
	return reinterpret_cast<struct LinkedObject *>(
	reinterpret_cast<uintptr_t>(c) -
	offsetof(struct LinkedObject, ring));
	}
	};
	} // namespace

	/**
	* `ds::linked_list`s are circular, doubly-linked collections. While they can
	* stand on their own as rings of objects, it is sometimes convenient to create
	* a designated 'sentinel' node that participates in the collection without
	* being part of the collection:
	*
	* - a sentinel node provides pointers to the effective head and tail of the
	* collection (the successor and predecessor of the sentinel, respectively)
	*
	* - a sentinel allows not having to special-case 'the collection is empty' in
	* as many places as some other representations (that is, collections with
	* sentinels need fewer NULL pointer checks)
	*
	* - a sentinel provides many handy functions to operate on the list
	*
	* Note: do not allocate the sentinel (or any list cell) on the stack, because
	* it would lead some list nodes to hold a pointer to a stack value, i.e., to
	* an invalid capability. This would manifest as a crash while using the list.
	*/
	ds::linked_list::Sentinel<LinkedObject::ObjectRing> objects = {};

	void test_list()
	{
	debug_log("Testing the list implementation.");

	// Number of elements we will add to the list in the test. Must be
	// divisible by two.
	static constexpr int NumberOfListElements = 30;

	auto heapAtStart = heap_quota_remaining(MALLOC_CAPABILITY);

	TEST(objects.is_empty(), "Newly created list is not empty");

	// Create heap-allocated objects, and link them into the linked list.
	for (int i = 0; i < NumberOfListElements; i++)
	{
	Timeout t{UnlimitedTimeout};
	LinkedObject o = static_cast<LinkedObject >(
	heap_allocate(&t, MALLOC_CAPABILITY, sizeof(LinkedObject)));
	TEST(Capability{o}.is_valid(), "Cannot allocate linked object");

	// Use the object integer as an index.
	o->data = i;
	// The list node has not yet been initialized.
	o->ring.cell_reset();

	// Test that we can retrieve the object from the link node and
	// that this results in a capability which is identical to what
	// we got from the allocator.
	TEST(Capability{o} == Capability{LinkedObject::from_ring(&(o->ring))},
	"The container of method does not return the right object");
	TEST(Capability{LinkedObject::from_ring(&(o->ring))}.is_valid(),
	"Capability retrieved from `from_ring` is invalid");

	// Add the new object to the list through the sentinel node.
	objects.append(&(o->ring));
	}

	TEST(!objects.is_empty(), "The list is empty after adding objects");

	// Test that the sentinel can be used to retrieve the first and last
	// elements of the list as expected.
	TEST(LinkedObject::from_ring(objects.last())->data ==
	NumberOfListElements - 1,
	"Last element of the list is incorrect, expected {}, got {}",
	NumberOfListElements - 1,
	LinkedObject::from_ring(objects.last())->data);
	TEST(objects.last()->cell_next() == &objects.sentinel,
	"Last element in not followed by the sentinel");
	TEST(objects.last() == objects.sentinel.cell_prev(),
	"Sentinel is not preceeded by the last element");

	TEST(LinkedObject::from_ring(objects.first())->data == 0,
	"First element of the list is incorrect, expected {}, got {}",
	0,
	LinkedObject::from_ring(objects.last())->data);
	TEST(objects.first()->cell_prev() == &objects.sentinel,
	"First element in not preceeded by the sentinel");
	TEST(objects.first() == objects.sentinel.cell_next(),
	"Sentinel is not followed by the first element");

	// Test that we can go through the list by following `cell_next`
	// pointers as expected.
	int counter = 0;
	// While at it, retrieve a pointer to the middle element which we will
	// use to cleave the list later.
	LinkedObject::ObjectRing *middle = nullptr;
	// We reach the sentinel when we have gone through all elements of the
	// list.
	for (auto *cell = objects.first(); cell != &objects.sentinel;
	cell = cell->cell_next())
	{
	struct LinkedObject *o = LinkedObject::from_ring(cell);
	TEST(
	o->data == counter,
	"Ordering of elements in the list is incorrect, expected {}, got {}",
	o->data,
	counter);
	if (counter == NumberOfListElements / 2)
	{
	middle = cell;
	}
	counter++;
	}

	TEST(middle != nullptr, "Could not find middle element of the list");

	// Cut the list in the middle. `middle` is now a handle to the (valid)
	// collection of objects [middle, last] that have become detached from
	// the sentinel.
	ds::linked_list::remove(middle, objects.last());

	// This should leave us with a list of size `NumberOfListElements / 2`.
	counter = 0;
	for (auto *cell = objects.first(); cell != &objects.sentinel;
	cell = cell->cell_next())
	{
	counter++;
	}
	TEST(counter == NumberOfListElements / 2,
	"Cleaving didn't leave a list with the right number of elements");

	// Now remove (and free) a single element from the list.
	TEST(LinkedObject::from_ring(objects.first())->data == 0,
	"First element of the list is incorrect, expected {}, got {}",
	0,
	LinkedObject::from_ring(objects.first())->data);
	// We must keep a reference to the removed object to free it, as
	// `remove` returns a pointer to the residual list (return value which
	// we do not use here), not to the removed element.
	LinkedObject::ObjectRing *removedCell = objects.first();
	ds::linked_list::remove(objects.first());
	heap_free(MALLOC_CAPABILITY, LinkedObject::from_ring(removedCell));
	TEST(LinkedObject::from_ring(objects.first())->data == 1,
	"First element of the list is incorrect after removing the first "
	"element, expected {}, got {}",
	1,
	LinkedObject::from_ring(objects.first())->data);
	TEST(objects.first()->cell_prev() == &objects.sentinel,
	"First element in not preceeded by the sentinel after removing the "
	"first object");

	// We are done with the list, free it.
	counter = 0;
	LinkedObject::ObjectRing *cell = objects.first();
	while (cell != &objects.sentinel)
	{
	struct LinkedObject *o = LinkedObject::from_ring(cell);
	cell = cell->cell_next();
	heap_free(MALLOC_CAPABILITY, o);
	counter++;
	}

	TEST(counter == (NumberOfListElements / 2) - 1,
	"Incorrect number of elements freed, expected {}, got {}",
	(NumberOfListElements / 2) - 1,
	counter);

	// Now that the list is freed, reset the sentinel.
	objects.reset();

	TEST(objects.is_empty(), "Reset-ed list is not empty");

	// We must also free the span of the list which we removed earlier.
	// This time use the `::search` method to go through the collection.
	ds::linked_list::search(
	middle, [&counter](LinkedObject::ObjectRing *&cell) {
	// `unsafe_remove` does not update the node pointers of the
	// removed cell. This is great here because we will free the
	// object anyways. We could also use `remove` here.
	auto l = ds::linked_list::unsafe_remove(cell);
	heap_free(MALLOC_CAPABILITY, LinkedObject::from_ring(cell));
	// `l` is the predecessor of `cell` in the residual ring, so
	// this does exactly what we want when `::search` iterates.
	cell = l;
	counter++;
	return false;
	});
	// `::search` does not visit the element passed (`middle`)
	heap_free(MALLOC_CAPABILITY, LinkedObject::from_ring(middle));
	counter++;

	TEST(counter == NumberOfListElements - 1,
	"Incorrect number of elements freed, expected {}, got {}",
	NumberOfListElements - 1,
	counter);

	// Check that we didn't leak anything in the process
	auto heapAtEnd = heap_quota_remaining(MALLOC_CAPABILITY);
	TEST(heapAtStart == heapAtEnd,
	"The list leaked {} bytes ({} vs. {})",
	heapAtEnd - heapAtStart,
	heapAtStart,
	heapAtEnd);

	debug_log("Done testing the list.");
	}