Queue: Add ability to modify contiguous units inplace

Previously all access to the queue was done by adding or removing units
with no access to the underlying byte array, or ability to notify the
queue that the byte array had been updated.  This prevented direct DMA
transfers to and from the underlying byte array.

This change adds a new struct, a queue_chunk, that represents a
contiguous region of the queues byte array.  Regions of valid units as
well as free space can be requested.  And there are now update functions
to signal to the queue that new units were added or existing units were
read from these chunks.  A chunk can be queried and used to initialize
a DMA transfer, as interrupts or polling indicates that the DMA is
working the queue indicies can be updated and the policy activated as
needed.

Signed-off-by: Anton Staaf <robotboy@chromium.org>

BRANCH=None
BUG=None
TEST=make buildall -j

Change-Id: I7e37d937c56153122f0a3c73ba8064b656106e3a
Reviewed-on: https://chromium-review.googlesource.com/285556
Trybot-Ready: Anton Staaf <robotboy@chromium.org>
Tested-by: Anton Staaf <robotboy@chromium.org>
Reviewed-by: Gwendal Grignou <gwendal@chromium.org>
Commit-Queue: Anton Staaf <robotboy@chromium.org>

1 files changed, 152 insertions, 0 deletions

diff --git a/test/queue.c b/test/queue.c
index 7196663943..16feb07129 100644
--- a/test/queue.c
+++ b/test/queue.c
@@ -153,6 +153,153 @@ static int test_queue2_odd_even(void)
 	return EC_SUCCESS;
 }
 
+static int test_queue8_chunks(void)
+{
+	static uint8_t const data[3] = {1, 2, 3};
+	struct queue_chunk chunk;
+
+	queue_init(&test_queue8);
+
+	chunk = queue_get_write_chunk(&test_queue8);
+
+	TEST_ASSERT(chunk.length == 8);
+
+	memcpy(chunk.buffer, data, 3);
+
+	TEST_ASSERT(queue_advance_tail(&test_queue8, 3) == 3);
+
+	chunk = queue_get_read_chunk(&test_queue8);
+
+	TEST_ASSERT(chunk.length == 3);
+	TEST_ASSERT_ARRAY_EQ(chunk.buffer, data, 3);
+
+	TEST_ASSERT(queue_advance_head(&test_queue8, 3) == 3);
+	TEST_ASSERT(queue_is_empty(&test_queue8));
+
+	return EC_SUCCESS;
+}
+
+static int test_queue8_chunks_wrapped(void)
+{
+	static uint8_t const data[3] = {1, 2, 3};
+
+	queue_init(&test_queue8);
+
+	/* Move near the end of the queue */
+	TEST_ASSERT(queue_advance_tail(&test_queue8, 6) == 6);
+	TEST_ASSERT(queue_advance_head(&test_queue8, 6) == 6);
+
+	/* Add three units, causing the tail to wrap */
+	TEST_ASSERT(queue_add_units(&test_queue8, data, 3) == 3);
+
+	/*
+	 * With a wrapped tail we should only be able to access the first two
+	 * elements for reading, but all five free elements for writing.
+	 */
+	TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 2);
+	TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 5);
+
+	/* Signal that we have read an element */
+	TEST_ASSERT(queue_advance_head(&test_queue8, 1) == 1);
+
+	/*
+	 * Now we should only be able to see a single element for reading, but
+	 * all six free element.
+	 */
+	TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 1);
+	TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 6);
+
+	/* Signal that we have read the last two elements */
+	TEST_ASSERT(queue_advance_head(&test_queue8, 2) == 2);
+
+	/*
+	 * Now there should be no elements available for reading, and only
+	 * seven, not eight elements available for writing.  This is because
+	 * the head/tail pointers now point to the second unit in the array.
+	 */
+	TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 0);
+	TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 7);
+
+	return EC_SUCCESS;
+}
+
+static int test_queue8_chunks_full(void)
+{
+	static uint8_t const data[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+	struct queue_chunk chunk;
+
+	queue_init(&test_queue8);
+
+	/* Move near the end of the queue */
+	TEST_ASSERT(queue_advance_tail(&test_queue8, 6) == 6);
+	TEST_ASSERT(queue_advance_head(&test_queue8, 6) == 6);
+
+	/* Fill the queue */
+	TEST_ASSERT(queue_add_units(&test_queue8, data, 8) == 8);
+
+	/* With a full queue we shouldn't be able to write */
+	TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 0);
+
+	/* But we should be able to read, though only two entries at first */
+	chunk = queue_get_read_chunk(&test_queue8);
+
+	TEST_ASSERT(chunk.length == 2);
+	TEST_ASSERT_ARRAY_EQ(chunk.buffer, data, 2);
+
+	/* Signal that we have read both units */
+	TEST_ASSERT(queue_advance_head(&test_queue8, 2) == 2);
+
+	/* Now we should only be able to see the rest */
+	chunk = queue_get_read_chunk(&test_queue8);
+
+	TEST_ASSERT(chunk.length == 6);
+	TEST_ASSERT_ARRAY_EQ(chunk.buffer, data + 2, 6);
+
+
+	return EC_SUCCESS;
+}
+
+static int test_queue8_chunks_empty(void)
+{
+	queue_init(&test_queue8);
+
+	/* With an empty queue we shouldn't be able to read */
+	TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 0);
+
+	/* But we should be able to write, everything */
+	TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 8);
+
+	return EC_SUCCESS;
+}
+
+static int test_queue8_chunks_advance(void)
+{
+	queue_init(&test_queue8);
+
+	/*
+	 * We should only be able to advance the tail (add units) as many
+	 * units as there are in an empty queue.
+	 */
+	TEST_ASSERT(queue_advance_tail(&test_queue8, 10) == 8);
+
+	/*
+	 * Similarly, we should only be able to advance the head (remove
+	 * units) as many units as there are in the now full queue.
+	 */
+	TEST_ASSERT(queue_advance_head(&test_queue8, 10) == 8);
+
+	/*
+	 * And it shouldn't matter if we start in the middle of the queue.
+	 */
+	TEST_ASSERT(queue_advance_tail(&test_queue8, 3) == 3);
+	TEST_ASSERT(queue_advance_head(&test_queue8, 3) == 3);
+
+	TEST_ASSERT(queue_advance_tail(&test_queue8, 10) == 8);
+	TEST_ASSERT(queue_advance_head(&test_queue8, 10) == 8);
+
+	return EC_SUCCESS;
+}
+
 void run_test(void)
 {
 	test_reset();
@@ -164,6 +311,11 @@ void run_test(void)
 	RUN_TEST(test_queue8_removal);
 	RUN_TEST(test_queue8_peek);
 	RUN_TEST(test_queue2_odd_even);
+	RUN_TEST(test_queue8_chunks);
+	RUN_TEST(test_queue8_chunks_wrapped);
+	RUN_TEST(test_queue8_chunks_full);
+	RUN_TEST(test_queue8_chunks_empty);
+	RUN_TEST(test_queue8_chunks_advance);
 
 	test_print_result();
 }