Bill Fischofer(Bill-Fischofer-Linaro) replied on github web page: platform/linux-generic/include/odp_ring_st_internal.h @@ -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); + + /* Full */ + if (num == 0) + return 0; + + if (num > num_data) + num = num_data; + + idx = tail & mask; + + for (i = 0; i < num; i++) { + ring->data[idx] = data[i]; + idx = (idx + 1) & mask; + } + + ring->tail = tail + num; + + return num; +} + +/* Check if ring is empty */ +static inline int ring_st_is_empty(ring_st_t *ring) +{ + uint32_t head, tail, num; + + head = ring->head; + tail = ring->tail; + num = tail - head; + + if (num == 0) + return 1; + + return 0;
Comment: This routine can be optimized to: ``` return ring->head == ring->tail; ``` > Bill Fischofer(Bill-Fischofer-Linaro) wrote: > 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_r169804664 updated_at 2018-02-22 09:32:40