Test and document the linked list from `ds::linked_list`. Although our linked list implementation does feature comments, they are more about the underlying technical details and do not really help newcomers understand how to use it. This matters because we do not have `std::list`. Address this by adding a test for the linked list which also explains how to use it for a basic use-case. Signed-off-by: Hugo Lefeuvre <hugo.lefeuvre@scisemi.com>
diff --git a/sdk/include/ds/linked_list.h b/sdk/include/ds/linked_list.h index 2894bb2..5194d2f 100644 --- a/sdk/include/ds/linked_list.h +++ b/sdk/include/ds/linked_list.h
@@ -4,6 +4,8 @@ /** * @file A (circular) doubly linked list, abstracted over cons cell * representations. + * + * See `tests/list-test.cc` for additional information on how to use it. */ #pragma once @@ -356,7 +358,7 @@ /** * Search through all elements of a ring *except* `elem`. If `elem` is the * sentinel of a ring, then this is, as one expects, a `search` over all - * non-sentinel memebers of the ring. + * non-sentinel members of the ring. */ template<cell::HasCellOperations Cell, typename F> __always_inline bool search(Cell *elem, F f)
diff --git a/tests/list-test.cc b/tests/list-test.cc new file mode 100644 index 0000000..7db652e --- /dev/null +++ b/tests/list-test.cc
@@ -0,0 +1,241 @@ +// 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."); +}
diff --git a/tests/test-runner.cc b/tests/test-runner.cc index 8d99fdd..719b1f1 100644 --- a/tests/test-runner.cc +++ b/tests/test-runner.cc
@@ -122,6 +122,7 @@ run_timed("Queue", test_queue); run_timed("Futex", test_futex); run_timed("Locks", test_locks); + run_timed("List", test_list); run_timed("Event groups", test_eventgroup); run_timed("Multiwaiter", test_multiwaiter); run_timed("Allocator", test_allocator);
diff --git a/tests/tests.hh b/tests/tests.hh index bd63a3c..f5625bc 100644 --- a/tests/tests.hh +++ b/tests/tests.hh
@@ -12,6 +12,7 @@ __cheri_compartment("futex_test") void test_futex(); __cheri_compartment("queue_test") void test_queue(); __cheri_compartment("locks_test") void test_locks(); +__cheri_compartment("list_test") void test_list(); __cheri_compartment("crash_recovery_test") void test_crash_recovery(); __cheri_compartment("multiwaiter_test") void test_multiwaiter(); __cheri_compartment("stack_test") void test_stack();
diff --git a/tests/xmake.lua b/tests/xmake.lua index 2f9e5ed..267e791 100644 --- a/tests/xmake.lua +++ b/tests/xmake.lua
@@ -50,6 +50,8 @@ test("futex") -- Test locks built on top of the futex test("locks") +-- Test the generic linked list from ds/ +test("list") -- Test queues test("queue") -- Test minimal stdio implementation @@ -106,6 +108,7 @@ add_deps("futex_test") add_deps("queue_test") add_deps("locks_test") + add_deps("list_test") add_deps("static_sealing_test", "static_sealing_inner") add_deps("crash_recovery_test", "crash_recovery_inner", "crash_recovery_outer") add_deps("multiwaiter_test")