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>

3 files changed, 284 insertions, 20 deletions

diff --git a/common/queue.c b/common/queue.c
index e289584a85..67934ca74e 100644
--- a/common/queue.c
+++ b/common/queue.c
@@ -42,6 +42,82 @@ size_t queue_space(struct queue const *q)
 	return q->buffer_units - queue_count(q);
 }
 
+int queue_is_full(struct queue const *q)
+{
+	return (queue_space(q) == 0);
+}
+
+/*
+ * These pictures make the logic below clearer.  The H and T markers are the
+ * head and tail indicies after they have been modded by the queue size.  The
+ * Empty and Full states are disambiguated by looking at the pre-modded
+ * indicies.
+ *
+ * Empty:       T
+ * T == H       H
+ *          |----------------|
+ *
+ * Normal:      H     T
+ * H < T    |---******-------|
+ *
+ * Wrapped:     T         H
+ * T < H    |***----------***|
+ *
+ * Full:        T
+ * T == H       H
+ *          |****************|
+ */
+
+struct queue_chunk queue_get_write_chunk(struct queue const *q)
+{
+	size_t head = q->state->head & (q->buffer_units - 1);
+	size_t tail = q->state->tail & (q->buffer_units - 1);
+	size_t last = (queue_is_full(q) ? tail : /* Full           */
+		       ((tail < head) ? head :   /* Wrapped        */
+			q->buffer_units));       /* Normal | Empty */
+
+	return ((struct queue_chunk) {
+		.length = (last - tail) * q->unit_bytes,
+		.buffer = q->buffer + tail * q->unit_bytes,
+	});
+}
+
+struct queue_chunk queue_get_read_chunk(struct queue const *q)
+{
+	size_t head = q->state->head & (q->buffer_units - 1);
+	size_t tail = q->state->tail & (q->buffer_units - 1);
+	size_t last = (queue_is_empty(q) ? head : /* Empty          */
+		       ((head < tail) ? tail :    /* Normal         */
+			q->buffer_units));        /* Wrapped | Full */
+
+	return ((struct queue_chunk) {
+		.length = (last - head) * q->unit_bytes,
+		.buffer = q->buffer + head * q->unit_bytes,
+	});
+}
+
+size_t queue_advance_head(struct queue const *q, size_t count)
+{
+	size_t transfer = MIN(count, queue_count(q));
+
+	q->state->head += transfer;
+
+	q->policy->remove(q->policy, transfer);
+
+	return transfer;
+}
+
+size_t queue_advance_tail(struct queue const *q, size_t count)
+{
+	size_t transfer = MIN(count, queue_space(q));
+
+	q->state->tail += transfer;
+
+	q->policy->add(q->policy, transfer);
+
+	return transfer;
+}
+
 size_t queue_add_unit(struct queue const *q, const void *src)
 {
 	size_t tail = q->state->tail & (q->buffer_units - 1);
@@ -54,11 +130,7 @@ size_t queue_add_unit(struct queue const *q, const void *src)
 	else
 		memcpy(q->buffer + tail * q->unit_bytes, src, q->unit_bytes);
 
-	q->state->tail += 1;
-
-	q->policy->add(q->policy, 1);
-
-	return 1;
+	return queue_advance_tail(q, 1);
 }
 
 size_t queue_add_units(struct queue const *q, const void *src, size_t count)
@@ -86,11 +158,7 @@ size_t queue_add_memcpy(struct queue const *q,
 		       ((uint8_t const *) src) + first * q->unit_bytes,
 		       (transfer - first) * q->unit_bytes);
 
-	q->state->tail += transfer;
-
-	q->policy->add(q->policy, transfer);
-
-	return transfer;
+	return queue_advance_tail(q, transfer);
 }
 
 static void queue_read_safe(struct queue const *q,
@@ -125,11 +193,7 @@ size_t queue_remove_unit(struct queue const *q, void *dest)
 	else
 		memcpy(dest, q->buffer + head * q->unit_bytes, q->unit_bytes);
 
-	q->state->head += 1;
-
-	q->policy->remove(q->policy, 1);
-
-	return 1;
+	return queue_advance_head(q, 1);
 }
 
 size_t queue_remove_units(struct queue const *q, void *dest, size_t count)
@@ -149,11 +213,7 @@ size_t queue_remove_memcpy(struct queue const *q,
 
 	queue_read_safe(q, dest, head, transfer, memcpy);
 
-	q->state->head += transfer;
-
-	q->policy->remove(q->policy, transfer);
-
-	return transfer;
+	return queue_advance_head(q, transfer);
 }
 
 size_t queue_peek_units(struct queue const *q,
diff --git a/include/queue.h b/include/queue.h
index db3c8fe4c4..ef7d001f47 100644
--- a/include/queue.h
+++ b/include/queue.h
@@ -105,6 +105,58 @@ size_t queue_count(struct queue const *q);
 /* Return the number of units worth of free space the queue has. */
 size_t queue_space(struct queue const *q);
 
+/* Return TRUE if the queue is full. */
+int queue_is_full(struct queue const *q);
+
+/*
+ * Chunk based queue access.  A queue_chunk is a contiguous region of queue
+ * buffer bytes, not units.  It may represent either free space in the queue
+ * or entries.
+ */
+struct queue_chunk {
+	size_t  length;
+	uint8_t *buffer;
+};
+
+/*
+ * Return the largest contiguous block of free space from the tail of the
+ * queue.  This may not be all of the available free space in the queue.  Once
+ * some or all of the free space has been written to you must call
+ * queue_advance_tail to update the queue.  You do not need to fill all of the
+ * free space returned before calling queue_advance_tail, and you may call
+ * queue_advance tail multiple times for a single chunk.  But you must not
+ * advance the tail more than the length of the chunk, or more than the actual
+ * number of units that you have written to the free space represented by the
+ * chunk.
+ */
+struct queue_chunk queue_get_write_chunk(struct queue const *q);
+
+/*
+ * Return the largest contiguous block of units from the head of the queue.
+ * This may not be all of the available units in the queue.  Similar rules to
+ * the above apply to reading from this chunk, you can call queue_advance_head
+ * after reading, and you can all it multiple times if you like.  However, if
+ * you do not call queue_advance_head this chunk will effectively be a peek
+ * into the queue contents, and later calls to queue_remove_* will see the
+ * same units.
+ */
+struct queue_chunk queue_get_read_chunk(struct queue const *q);
+
+/*
+ * Move the queue head pointer forward count units.  This discards count
+ * elements from the head of the queue.  It will only discard up to the total
+ * number of elements in the queue, and it returns the number discarded.
+ */
+size_t queue_advance_head(struct queue const *q, size_t count);
+
+/*
+ * Move the queue tail pointer forward count units.  This signals to the queue
+ * that count new elements have been added to the queue using a queue_chunk
+ * that was returned by queue_get_write_chunk.  Make sure that count units have
+ * been added to the chunk before calling queue_advance_tail.
+ */
+size_t queue_advance_tail(struct queue const *q, size_t count);
+
 /* Add one unit to queue. */
 size_t queue_add_unit(struct queue const *q, const void *src);
 
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();
 }