Re: [Qemu-devel] [RFC v2 07/38] queue: add QTAILQ_REMOVE_SEVERAL

[Emilio G. Cota]

On Mon, Feb 25, 2019 at 16:22:52 +0000, Alex Bennée wrote:
> Emilio G. Cota <address@hidden> writes:
> > +/* remove @left, @right and all elements in between from @head */
> > +#define QTAILQ_REMOVE_SEVERAL(head, left, right, field) do {    \
> > +        if (((right)->field.tqe_next) != NULL)                  \
> > +            (right)->field.tqe_next->field.tqe_prev =           \
> > +                (left)->field.tqe_prev;                         \
> > +        else                                                    \
> > +            (head)->tqh_last = (left)->field.tqe_prev;          \
> > +        *(left)->field.tqe_prev = (right)->field.tqe_next;      \
> 
> This seems wrong, shouldn't it be:
> 
>   (left)->field.tqe_prev->field.tqe_next = (right)->field.tqe_next;

That would make too much sense, wouldn't it!

Looking at QTAILQ_REMOVE is the easiest way to reason about this:

#define QTAILQ_REMOVE(head, elm, field) do {                            \
        if (((elm)->field.tqe_next) != NULL)                            \
                (elm)->field.tqe_next->field.tqe_prev =                 \
                    (elm)->field.tqe_prev;                              \
        else                                                            \
                (head)->tqh_last = (elm)->field.tqe_prev;               \
        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
        (elm)->field.tqe_prev = NULL;                                   \
} while (/*CONSTCOND*/0)

Imagine we're removing the only element in the list. Thus,
*(elm)->field.tqe_prev will be setting (head)->tqh_first (to NULL).
IOW, we can't assume that the previous "element" (whether true element
or head) has a .tqe_next field (the head has .thq_first); note that
tqe_prev is a **, not a *.

> Although to be honest every time I read the QUEUE macros I end up with a 
> headache...

You're not alone.

BTW, this code had to change for v3 because of 7274f01bb8 ("qemu/queue.h:
reimplement QTAILQ without pointer-to-pointers", 2019-01-11)

I think you might like that implementation better, since it is a little
closer to sanity, i.e. kernel-style lists :-)
It uses a more predictable structure (*prev,*next) that is shoehorned
with a union to avoid changing the memory layout.

Thanks,

                Emilio