Re: [Qemu-devel] [PATCH v4 1/3] util/fifo8: implement push/pop of multiple bytes

[Beniamino Galvani <b.galvani@gmail.com>]

On Tue, Jan 28, 2014 at 10:04:09AM +1000, Peter Crosthwaite wrote:
> On Tue, Jan 28, 2014 at 4:32 AM, Peter Maydell <peter.maydell@linaro.org> wrote:
> > On 26 January 2014 21:39, Beniamino Galvani <b.galvani@gmail.com> wrote:
> >> In some circumstances it is useful to be able to push the entire
> >> content of a memory buffer to the fifo or to pop multiple bytes with a
> >> single operation.
> >>
> >> The functions fifo8_has_space() and fifo8_push_all() added by this
> >> patch allow to perform the first kind of operation efficiently.
> >>
> >> The function fifo8_pop_buf() can be used instead to pop multiple bytes
> >> from the fifo, returning a pointer to the backing buffer.
> >
> >
> > Thanks; a few nits below but mostly this looks OK.
> >
> >
> >> Signed-off-by: Beniamino Galvani <b.galvani@gmail.com>
> >> ---
> >>  include/qemu/fifo8.h |   43 +++++++++++++++++++++++++++++++++++++++++++
> >>  util/fifo8.c         |   44 ++++++++++++++++++++++++++++++++++++++++++++
> >>  2 files changed, 87 insertions(+)
> >>
> >> diff --git a/include/qemu/fifo8.h b/include/qemu/fifo8.h
> >> index d318f71..ea6e9f6 100644
> >> --- a/include/qemu/fifo8.h
> >> +++ b/include/qemu/fifo8.h
> >> @@ -44,6 +44,19 @@ void fifo8_destroy(Fifo8 *fifo);
> >>  void fifo8_push(Fifo8 *fifo, uint8_t data);
> >>
> >>  /**
> >> + * fifo8_push_all:
> >> + * @fifo: FIFO to push to
> >> + * @data: data to push
> >> + * @size: number of bytes to push
> >> + *
> >> + * Push a byte array to the FIFO. Behaviour is undefined is the FIFO is
> >
> > "if the FIFO"
> >
> >> + * full. Clients are responsible for checking the space left in the FIFO using
> >> + * fifo8_has_space().
> >> + */
> >> +
> >> +void fifo8_push_all(Fifo8 *fifo, const uint8_t *data, uint32_t num);
> >> +
> >> +/**
> >>   * fifo8_pop:
> >>   * @fifo: fifo to pop from
> >>   *
> >> @@ -56,6 +69,24 @@ void fifo8_push(Fifo8 *fifo, uint8_t data);
> >>  uint8_t fifo8_pop(Fifo8 *fifo);
> >>
> >>  /**
> >> + * fifo8_pop_buf:
> >> + * @fifo: FIFO to pop from
> >> + * @max: maximum number of bytes to pop
> >> + * @num: actual number of returned bytes
> >> + *
> >> + * Pop a number of elements from the FIFO up to a maximum of max. The buffer
> >> + * containing the popped data is returned. This buffer points directly into
> >> + * the FIFO backing store and data is invalidated once any of the fifo8_* APIs
> >> + * are called on the FIFO.
> >> + *
> >> + * May short return, the number of valid bytes returned is populated in
> >> + * *num. Will always return at least 1 byte.
> >
> > What does "May short return" mean here? Rephrasing might help.
> >
> > Like fifo8_pop, you should say that clients are responsible
> > for checking that the fifo is empty before calling this.
> >
> >> + *
> >> + * Behavior is undefined if max == 0.
> >> + */
> >> +const uint8_t *fifo8_pop_buf(Fifo8 *fifo, uint32_t max, uint32_t *num);
> >> +
> >> +/**
> >>   * fifo8_reset:
> >>   * @fifo: FIFO to reset
> >>   *
> >> @@ -86,6 +117,18 @@ bool fifo8_is_empty(Fifo8 *fifo);
> >>
> >>  bool fifo8_is_full(Fifo8 *fifo);
> >>
> >> +/**
> >> + * fifo8_has_space:
> >> + * @fifo: FIFO to check
> >> + * @num: number of bytes
> >> + *
> >> + * Check if a given number of bytes can be pushed to a FIFO.
> >> + *
> >> + * Returns: True if the fifo can hold the given elements, false otherwise.
> >> + */
> >> +
> >> +bool fifo8_has_space(Fifo8 *fifo, uint32_t num);
> >> +
> >>  extern const VMStateDescription vmstate_fifo8;
> >>
> >>  #define VMSTATE_FIFO8(_field, _state) {                              \
> >> diff --git a/util/fifo8.c b/util/fifo8.c
> >> index 013e903..2808169 100644
> >> --- a/util/fifo8.c
> >> +++ b/util/fifo8.c
> >> @@ -15,6 +15,8 @@
> >>  #include "qemu-common.h"
> >>  #include "qemu/fifo8.h"
> >>
> >> +#define min(a, b) ((a) < (b) ? (a) : (b))
> >
> > Just use MIN, the QEMU include files define it for you.
> >
> >>  void fifo8_create(Fifo8 *fifo, uint32_t capacity)
> >>  {
> >>      fifo->data = g_new(uint8_t, capacity);
> >> @@ -37,6 +39,27 @@ void fifo8_push(Fifo8 *fifo, uint8_t data)
> >>      fifo->num++;
> >>  }
> >>
> >> +void fifo8_push_all(Fifo8 *fifo, const uint8_t *data, uint32_t num)
> >> +{
> >> +    uint32_t start, avail;
> >> +
> >> +    if (fifo->num + num > fifo->capacity) {
> >> +        abort();
> >> +    }
> >> +
> >> +    start = (fifo->head + fifo->num) % fifo->capacity;
> >> +
> >> +    if (start + num <= fifo->capacity) {
> >> +        memcpy(&fifo->data[start], data, num);
> >> +    } else {
> >> +        avail = fifo->capacity - start;
> >> +        memcpy(&fifo->data[start], data, avail);
> >> +        memcpy(&fifo->data[0], &data[avail], num - avail);
> >> +    }
> >> +
> >> +    fifo->num += num;
> >> +}
> >> +
> >>  uint8_t fifo8_pop(Fifo8 *fifo)
> >>  {
> >>      uint8_t ret;
> >> @@ -50,9 +73,25 @@ uint8_t fifo8_pop(Fifo8 *fifo)
> >>      return ret;
> >>  }
> >>
> >> +const uint8_t *fifo8_pop_buf(Fifo8 *fifo, uint32_t max, uint32_t *num)
> >> +{
> >> +    uint8_t *ret;
> >> +
> >> +    *num = min(fifo->capacity - fifo->head, max);
> >> +    *num = min(*num, fifo->num);
> >> +
> >> +    ret = &fifo->data[fifo->head];
> >> +
> >> +    fifo->head += *num;
> >> +    fifo->head %= fifo->capacity;
> >> +
> >> +    return ret;
> >> +}
> >> +
> >>  void fifo8_reset(Fifo8 *fifo)
> >>  {
> >>      fifo->num = 0;
> >> +    fifo->head = 0;
> >
> > This is a bug fix, right? It should go in its own patch.
> >
> 
> No bug - where the ring buffer starts following a reset is undefined
> and need not be defined. But it improves the predicatability of the
> newly added pop_buf fn as you can now following a reset, guarantee
> that a single pop_buf will take all contents if its the first pop
> (which is how its being used in P2).

Right; in the next patch I will add an explanation.
 
> >>  }
> >>
> >>  bool fifo8_is_empty(Fifo8 *fifo)
> >> @@ -65,6 +104,11 @@ bool fifo8_is_full(Fifo8 *fifo)
> >>      return (fifo->num == fifo->capacity);
> >>  }
> >>
> >> +bool fifo8_has_space(Fifo8 *fifo, uint32_t num)
> >> +{
> >> +    return (fifo->num + num <= fifo->capacity);
> >> +}
> >> +
> 
> This is a little specific and perhaps limited in usage. Can we just
> add occupancy/vacancy getters and let the caller do what it wants:
> 
> uint32_t fifo8_num_free(Fifo *fifo) {
>     return fifo->capacity - fifo->num;
> }

Ok.

Thanks,
Beniamino