Bill Fischofer(Bill-Fischofer-Linaro) replied on github web page:
platform/linux-generic/include/odp_ring_st_internal.h
line 78
@@ -0,0 +1,118 @@
+/* Copyright (c) 2018, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+#ifndef ODP_RING_ST_INTERNAL_H_
+#define ODP_RING_ST_INTERNAL_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <odp/api/hints.h>
+#include <odp_align_internal.h>
+
+/* Basic ring for single thread usage. Operations must be synchronized by using
+ * locks (or other means), when multiple threads use the same ring. */
+typedef struct {
+ uint32_t head;
+ uint32_t tail;
+ uint32_t mask;
+ uint32_t *data;
+
+} ring_st_t;
+
+/* Initialize ring. Ring size must be a power of two. */
+static inline void ring_st_init(ring_st_t *ring, uint32_t *data, uint32_t size)
+{
+ ring->head = 0;
+ ring->tail = 0;
+ ring->mask = size - 1;
+ ring->data = data;
+}
+
+/* Dequeue data from the ring head. Max_num is smaller than ring size.*/
+static inline uint32_t ring_st_deq_multi(ring_st_t *ring, uint32_t data[],
+ uint32_t max_num)
+{
+ uint32_t head, tail, mask, idx;
+ uint32_t num, i;
+
+ head = ring->head;
+ tail = ring->tail;
+ mask = ring->mask;
+ num = tail - head;
+
+ /* Empty */
+ if (num == 0)
+ return 0;
+
+ if (num > max_num)
+ num = max_num;
+
+ idx = head & mask;
+
+ for (i = 0; i < num; i++) {
+ data[i] = ring->data[idx];
+ idx = (idx + 1) & mask;
+ }
+
+ ring->head = head + num;
+
+ return num;
+}
+
+/* Enqueue data into the ring tail. Num_data is smaller than ring size. */
+static inline uint32_t ring_st_enq_multi(ring_st_t *ring, const uint32_t
data[],
+ uint32_t num_data)
+{
+ uint32_t head, tail, mask, size, idx;
+ uint32_t num, i;
+
+ head = ring->head;
+ tail = ring->tail;
+ mask = ring->mask;
+ size = mask + 1;
+ num = size - (tail - head);
Comment:
Your invariant is the queue is empty when `head == tail` therefore the queue is
full when `abs(tail - head) == mask`, so the correct calculation here is:
`num = mask - abs(tail - head);`
The effect is that a queue can only hold `size - 1` elements, otherwise you
cannot distinguish between a full and an empty queue without another bit of
metadata, which is a cost you're trying to avoid.
This is somewhat problematic if the caller is trying to be "optimal" by
specifying a power of two in the `size` parameter of the `odp_queue_param_t`
passed to `odp_queue_create()`. For this reason we may wish to return a
`max_size` of a power of 2 - 1 in `odp_queue_capability()` as part of this
patch series.
> Bill Fischofer(Bill-Fischofer-Linaro) wrote:
> This only works if `size` is a power of 2. Should be documented as such,
> since this is an internal routine. In this case an `ODP_ASSERT(size ==
> ROUNDUP_POWER2_U32(size))` for this requirement would be a useful debugging
> aid.
>> Bill Fischofer(Bill-Fischofer-Linaro) wrote:
>> should be `num = abs(tail - head);` to deal with wrap arounds, otherwise may
>> be misinterpreted as overly large since it's `uint32_t`. Note that GCC and
>> clang recognize `abs()` and treat it as a builtin, so there's no actual
>> `stdlib.h` call here.
>>> Bill Fischofer(Bill-Fischofer-Linaro) wrote:
>>> Extra blank line should be removed (nit).
https://github.com/Linaro/odp/pull/492#discussion_r169794712
updated_at 2018-02-22 09:32:40
