[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH 4/6] qemu/queue.h: reimplement QTAILQ without po
|
From: |
Markus Armbruster |
|
Subject: |
Re: [Qemu-devel] [PATCH 4/6] qemu/queue.h: reimplement QTAILQ without pointer-to-pointers |
|
Date: |
Fri, 07 Dec 2018 10:22:37 +0100 |
|
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.1 (gnu/linux) |
Paolo Bonzini <address@hidden> writes:
> QTAILQ is a doubly linked list, with a pointer-to-pointer to the last
> element from the head, and the previous element from each node.
>
> But if you squint enough, QTAILQ becomes a combination of a singly-linked
> forwards list, and another singly-linked list which goes backwards and
> is circular. This is the idea that lets QTAILQ implement reverse
> iteration: only, because the backwards list points inside the node,
> accessing the previous element needs to go two steps back and one
> forwards.
>
> What this patch does is implement it in these terms, without actually
> changing the in-memory layout at all. The coexistence of the two lists
> is realized by making QTAILQ_HEAD and QTAILQ_ENTRY unions of the forwards
> pointer and a generic QTailQLink node. Thq QTailQLink can walk the list in
s/Thq/The/
> both directions; the union is needed so that the forwards pointer can
> have the correct type, as a sort of poor man's template. While there
> are other ways to get the same layout without a union, this one has
> the advantage of simpler operation in the debugger, because the fields
> tqh_first and tqe_next still exist as before the patch. Those fields are
> also used by scripts/qemugdb/mtree.py, so it's a good idea to preserve them.
>
> The advantage of the new representation is that the two-back-one-forward
> dance done by backwards accesses can be done all while operating on
> QTailQLinks. No casting to the head struct is needed anymore because,
> even though the QTailQLink's forward pointer is a void *, we can use
> typeof to recover the correct type. This patch only changes the
> implementation, not the interface. The next patch will remove the head
> struct name from the backwards visit macros.
>
> Signed-off-by: Paolo Bonzini <address@hidden>
> ---
> include/qemu/queue.h | 143 ++++++++++++++++---------------------
> include/qemu/rcu_queue.h | 45 ++++++------
> scripts/cocci-macro-file.h | 24 ++-----
> 3 files changed, 93 insertions(+), 119 deletions(-)
>
> diff --git a/include/qemu/queue.h b/include/qemu/queue.h
> index ac418efc43..cb1bd6327c 100644
> --- a/include/qemu/queue.h
> +++ b/include/qemu/queue.h
> @@ -346,77 +346,80 @@ struct {
> \
> #define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
> #define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
>
> +typedef struct QTailQLink {
> + void *tql_next;
> + struct QTailQLink *tql_prev;
> +} QTailQLink;
>
> /*
> - * Tail queue definitions.
> + * Tail queue definitions. The union acts as a poor man template, as if
> + * it were QTailQLink<type>.
> */
> -#define Q_TAILQ_HEAD(name, type, qual) \
> -struct name { \
> - qual type *tqh_first; /* first element */ \
> - qual type *qual *tqh_last; /* addr of last next element */ \
> +#define QTAILQ_HEAD(name, type) \
> +union name { \
> + struct type *tqh_first; /* first element */ \
> + QTailQLink tqh_circ; /* link for circular backwards list */
> \
> }
> -#define QTAILQ_HEAD(name, type) Q_TAILQ_HEAD(name, struct type,)
>
> #define QTAILQ_HEAD_INITIALIZER(head) \
> - { NULL, &(head).tqh_first }
> + { .tqh_circ = { NULL, &(head).tqh_circ } }
>
> -#define Q_TAILQ_ENTRY(type, qual) \
> -struct { \
> - qual type *tqe_next; /* next element */ \
> - qual type *qual *tqe_prev; /* address of previous next element
> */\
> +#define QTAILQ_ENTRY(type) \
> +union { \
> + struct type *tqe_next; /* next element */ \
> + QTailQLink tqe_circ; /* link for circular backwards list */
> \
> }
> -#define QTAILQ_ENTRY(type) Q_TAILQ_ENTRY(struct type,)
I think this conflates two things:
(a) The one advertized by the commit message, and
(b) Getting rid of Q_TAILQ_HEAD(), Q_TAILQ_ENTRY() as unnecessary
complications.
I suspect doing (b) first in a separate patch would make (a) a bit
easier to review.
The way my brain works, I need to redo your explanation my own way;
reading your (undoubtedly fine) commit message won't do.
Let me start with examining (a) in the light of "no change of the
in-memory layout".
The head is a pair of pointers. Before the patch, they are
struct T *tqh_first;
struct T **tqh_last;
The patch changes tqh_first from the first member of a struct into the
first member of a union, which is effectively the same. Okay.
It adds tqh_circ.tql_next as alias of type void *. Exploits uniform
pointer representation on sane machines. Okay.
It replaces tqh_last by tqh_circ.tql_prev, changing its type from struct
T ** to QTailQLink *.
The entry has the same structure, only the names are different.
tqe_next stays the same, with new alias tqe_circ.tql_next.
tqe_prev gets replaced by tqe_circ.tql_prev.
The commit message claims the QTailQLink permits walking the list in
both directions. True: ->tqe_next->FIELD.tqe_circ is the next
QTailQLink, and ->tql_prev points to the previous one.
To go from QTailQLink to the T that contains it, we can
->tql_prev->tql->next (the backward list is circular). This yields a
void *, which we need to cast to struct T *.
The cast to struct T * can be done without having to name struct T when
we have a head or an entry: typeof ->tqh_first or ->tqe_next does the
trick.
Yup, that should work. I figure the changes below are actually almost
mechanical.
Or did I screw up somewhere?
>
> /*
> * Tail queue functions.
> */
> #define QTAILQ_INIT(head) do { \
> (head)->tqh_first = NULL; \
> - (head)->tqh_last = &(head)->tqh_first; \
> + (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_INSERT_HEAD(head, elm, field) do { \
> if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
> - (head)->tqh_first->field.tqe_prev = \
> - &(elm)->field.tqe_next; \
> + (head)->tqh_first->field.tqe_circ.tql_prev = \
> + &(elm)->field.tqe_circ; \
> else \
> - (head)->tqh_last = &(elm)->field.tqe_next; \
> + (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
> (head)->tqh_first = (elm); \
> - (elm)->field.tqe_prev = &(head)->tqh_first; \
> + (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_INSERT_TAIL(head, elm, field) do { \
> (elm)->field.tqe_next = NULL; \
> - (elm)->field.tqe_prev = (head)->tqh_last; \
> - *(head)->tqh_last = (elm); \
> - (head)->tqh_last = &(elm)->field.tqe_next; \
> + (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
> + (head)->tqh_circ.tql_prev->tql_next = (elm); \
> + (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
> if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
> - (elm)->field.tqe_next->field.tqe_prev = \
> - &(elm)->field.tqe_next; \
> + (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
> + &(elm)->field.tqe_circ; \
> else \
> - (head)->tqh_last = &(elm)->field.tqe_next; \
> + (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
> (listelm)->field.tqe_next = (elm); \
> - (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
> + (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
> } while (/*CONSTCOND*/0)
>
> -#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
> - (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
> - (elm)->field.tqe_next = (listelm); \
> - *(listelm)->field.tqe_prev = (elm); \
> - (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
> +#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do {
> \
> + (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev;
> \
> + (elm)->field.tqe_next = (listelm);
> \
> + (listelm)->field.tqe_circ.tql_prev->tql_next = (elm);
> \
> + (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ;
> \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_REMOVE(head, elm, field) do { \
> if (((elm)->field.tqe_next) != NULL) \
> - (elm)->field.tqe_next->field.tqe_prev = \
> - (elm)->field.tqe_prev; \
> + (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
> + (elm)->field.tqe_circ.tql_prev; \
> else \
> - (head)->tqh_last = (elm)->field.tqe_prev; \
> - *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
> - (elm)->field.tqe_prev = NULL; \
> + (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
> + (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
> + (elm)->field.tqe_circ.tql_prev = NULL; \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_FOREACH(var, head, field) \
> @@ -430,13 +433,13 @@ struct {
> \
> (var) = (next_var))
>
> #define QTAILQ_FOREACH_REVERSE(var, head, headname, field) \
> - for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));
> \
> + for ((var) = QTAILQ_LAST(head, headname); \
> (var); \
> - (var) = (*(((struct headname
> *)((var)->field.tqe_prev))->tqh_last)))
> + (var) = QTAILQ_PREV(var, headname, field))
>
> #define QTAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev_var) \
> - for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));
> \
> - (var) && ((prev_var) = (*(((struct headname
> *)((var)->field.tqe_prev))->tqh_last)), 1); \
> + for ((var) = QTAILQ_LAST(head, headname); \
> + (var) && ((prev_var) = QTAILQ_PREV(var, headname, field)); \
> (var) = (prev_var))
>
> /*
> @@ -445,71 +448,49 @@ struct {
> \
> #define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
> #define QTAILQ_FIRST(head) ((head)->tqh_first)
> #define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
> -#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_prev != NULL)
> +#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev !=
> NULL)
>
> +#define QTAILQ_LINK_PREV(link) \
> + ((link).tql_prev->tql_prev->tql_next)
> #define QTAILQ_LAST(head, headname) \
> - (*(((struct headname *)((head)->tqh_last))->tqh_last))
> + ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
> #define QTAILQ_PREV(elm, headname, field) \
> - (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
> + ((typeof((elm)->field.tqe_next))
> QTAILQ_LINK_PREV((elm)->field.tqe_circ))
>
> #define field_at_offset(base, offset, type)
> \
> - ((type) (((char *) (base)) + (offset)))
> -
> -typedef struct DUMMY_Q_ENTRY DUMMY_Q_ENTRY;
> -typedef struct DUMMY_Q DUMMY_Q;
> -
> -struct DUMMY_Q_ENTRY {
> - QTAILQ_ENTRY(DUMMY_Q_ENTRY) next;
> -};
> -
> -struct DUMMY_Q {
> - QTAILQ_HEAD(DUMMY_Q_HEAD, DUMMY_Q_ENTRY) head;
> -};
> -
> -#define dummy_q ((DUMMY_Q *) 0)
> -#define dummy_qe ((DUMMY_Q_ENTRY *) 0)
> + ((type *) (((char *) (base)) + (offset)))
>
> /*
> - * Offsets of layout of a tail queue head.
> - */
> -#define QTAILQ_FIRST_OFFSET (offsetof(typeof(dummy_q->head), tqh_first))
> -#define QTAILQ_LAST_OFFSET (offsetof(typeof(dummy_q->head), tqh_last))
> -/*
> - * Raw access of elements of a tail queue
> + * Raw access of elements of a tail queue head. Offsets are all zero
> + * because it's a union.
> */
> #define QTAILQ_RAW_FIRST(head)
> \
> - (*field_at_offset(head, QTAILQ_FIRST_OFFSET, void **))
> -#define QTAILQ_RAW_TQH_LAST(head)
> \
> - (*field_at_offset(head, QTAILQ_LAST_OFFSET, void ***))
> -
> -/*
> - * Offsets of layout of a tail queue element.
> - */
> -#define QTAILQ_NEXT_OFFSET (offsetof(typeof(dummy_qe->next), tqe_next))
> -#define QTAILQ_PREV_OFFSET (offsetof(typeof(dummy_qe->next), tqe_prev))
> + field_at_offset(head, 0, void *)
> +#define QTAILQ_RAW_TQH_CIRC(head)
> \
> + field_at_offset(head, 0, QTailQLink)
>
> /*
> * Raw access of elements of a tail entry
> */
> #define QTAILQ_RAW_NEXT(elm, entry)
> \
> - (*field_at_offset(elm, entry + QTAILQ_NEXT_OFFSET, void **))
> -#define QTAILQ_RAW_TQE_PREV(elm, entry)
> \
> - (*field_at_offset(elm, entry + QTAILQ_PREV_OFFSET, void ***))
> + field_at_offset(elm, entry, void *)
> +#define QTAILQ_RAW_TQE_CIRC(elm, entry)
> \
> + field_at_offset(elm, entry, QTailQLink)
> /*
> - * Tail queue tranversal using pointer arithmetic.
> + * Tail queue traversal using pointer arithmetic.
> */
> #define QTAILQ_RAW_FOREACH(elm, head, entry)
> \
> - for ((elm) = QTAILQ_RAW_FIRST(head);
> \
> + for ((elm) = *QTAILQ_RAW_FIRST(head);
> \
> (elm);
> \
> - (elm) = QTAILQ_RAW_NEXT(elm, entry))
> + (elm) = *QTAILQ_RAW_NEXT(elm, entry))
> /*
> * Tail queue insertion using pointer arithmetic.
> */
> -#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do {
> \
> - QTAILQ_RAW_NEXT(elm, entry) = NULL;
> \
> - QTAILQ_RAW_TQE_PREV(elm, entry) = QTAILQ_RAW_TQH_LAST(head);
> \
> - *QTAILQ_RAW_TQH_LAST(head) = (elm);
> \
> - QTAILQ_RAW_TQH_LAST(head) = &QTAILQ_RAW_NEXT(elm, entry);
> \
> +#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do {
> \
> + *QTAILQ_RAW_NEXT(elm, entry) = NULL;
> \
> + QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev =
> QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \
> + QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm);
> \
> + QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm,
> entry); \
> } while (/*CONSTCOND*/0)
>
> #endif /* QEMU_SYS_QUEUE_H */
> diff --git a/include/qemu/rcu_queue.h b/include/qemu/rcu_queue.h
> index 904b3372dc..2bee5dff80 100644
> --- a/include/qemu/rcu_queue.h
> +++ b/include/qemu/rcu_queue.h
> @@ -206,47 +206,50 @@ extern "C" {
> #define QTAILQ_INSERT_HEAD_RCU(head, elm, field) do { \
> (elm)->field.tqe_next = (head)->tqh_first; \
> if ((elm)->field.tqe_next != NULL) { \
> - (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \
> + (head)->tqh_first->field.tqe_circ.tql_prev = \
> + &(elm)->field.tqe_circ; \
> } else { \
> - (head)->tqh_last = &(elm)->field.tqe_next; \
> + (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
> } \
> atomic_rcu_set(&(head)->tqh_first, (elm)); \
> - (elm)->field.tqe_prev = &(head)->tqh_first; \
> + (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
> } while (/*CONSTCOND*/0)
>
> -#define QTAILQ_INSERT_TAIL_RCU(head, elm, field) do { \
> - (elm)->field.tqe_next = NULL; \
> - (elm)->field.tqe_prev = (head)->tqh_last; \
> - atomic_rcu_set((head)->tqh_last, (elm)); \
> - (head)->tqh_last = &(elm)->field.tqe_next; \
> +#define QTAILQ_INSERT_TAIL_RCU(head, elm, field) do { \
> + (elm)->field.tqe_next = NULL; \
> + (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
> + atomic_rcu_set(&(head)->tqh_circ.tql_prev->tql_next, (elm)); \
> + (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_INSERT_AFTER_RCU(head, listelm, elm, field) do { \
> (elm)->field.tqe_next = (listelm)->field.tqe_next; \
> if ((elm)->field.tqe_next != NULL) { \
> - (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \
> + (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
> + &(elm)->field.tqe_circ; \
> } else { \
> - (head)->tqh_last = &(elm)->field.tqe_next; \
> + (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
> } \
> atomic_rcu_set(&(listelm)->field.tqe_next, (elm)); \
> - (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
> + (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
> } while (/*CONSTCOND*/0)
>
> -#define QTAILQ_INSERT_BEFORE_RCU(listelm, elm, field) do { \
> - (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
> - (elm)->field.tqe_next = (listelm); \
> - atomic_rcu_set((listelm)->field.tqe_prev, (elm)); \
> - (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
> - } while (/*CONSTCOND*/0)
> +#define QTAILQ_INSERT_BEFORE_RCU(listelm, elm, field) do { \
> + (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
> + (elm)->field.tqe_next = (listelm); \
> + atomic_rcu_set(&(listelm)->field.tqe_circ.tql_prev->tql_next, (elm)); \
> + (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \
> +} while (/*CONSTCOND*/0)
>
> #define QTAILQ_REMOVE_RCU(head, elm, field) do { \
> if (((elm)->field.tqe_next) != NULL) { \
> - (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \
> + (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
> + (elm)->field.tqe_circ.tql_prev; \
> } else { \
> - (head)->tqh_last = (elm)->field.tqe_prev; \
> + (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
> } \
> - atomic_set((elm)->field.tqe_prev, (elm)->field.tqe_next); \
> - (elm)->field.tqe_prev = NULL; \
> + atomic_set(&(elm)->field.tqe_circ.tql_prev->tql_next,
> (elm)->field.tqe_next); \
> + (elm)->field.tqe_circ.tql_prev = NULL; \
> } while (/*CONSTCOND*/0)
>
> #define QTAILQ_FOREACH_RCU(var, head, field) \
> diff --git a/scripts/cocci-macro-file.h b/scripts/cocci-macro-file.h
> index 9f2e72e7e1..7f1006e97c 100644
> --- a/scripts/cocci-macro-file.h
> +++ b/scripts/cocci-macro-file.h
> @@ -93,29 +93,19 @@ struct {
> \
> /*
> * Tail queue definitions.
> */
> -#define Q_TAILQ_HEAD(name, type, qual) \
> -struct name { \
> - qual type *tqh_first; /* first element */ \
> - qual type *qual *tqh_last; /* addr of last next element */ \
> -}
> #define QTAILQ_HEAD(name, type) \
> -struct name { \
> - type *tqh_first; /* first element */ \
> - type **tqh_last; /* addr of last next element */ \
> +union name { \
> + struct type *tqh_first; /* first element */ \
> + QTailQLink tqh_circ; /* link for last element */ \
> }
>
> #define QTAILQ_HEAD_INITIALIZER(head) \
> - { NULL, &(head).tqh_first }
> + { .tqh_circ = { NULL, &(head).tqh_circ } }
>
> -#define Q_TAILQ_ENTRY(type, qual) \
> -struct { \
> - qual type *tqe_next; /* next element */ \
> - qual type *qual *tqe_prev; /* address of previous next element
> */\
> -}
> #define QTAILQ_ENTRY(type) \
> -struct { \
> - type *tqe_next; /* next element */ \
> - type **tqe_prev; /* address of previous next element */ \
> +union { \
> + struct type *tqe_next; /* next element */ \
> + QTailQLink tqe_circ; /* link for prev element */ \
> }
>
> /* From glib */
- Re: [Qemu-devel] [PATCH 1/6] qemu/queue.h: do not access tqe_prev directly, (continued)
- [Qemu-devel] [PATCH 3/6] qemu/queue.h: typedef QTAILQ heads, Paolo Bonzini, 2018/12/06
- [Qemu-devel] [PATCH 2/6] qemu/queue.h: leave head structs anonymous unless necessary, Paolo Bonzini, 2018/12/06
- [Qemu-devel] [PATCH 5/6] qemu/queue.h: simplify reverse access to QTAILQ, Paolo Bonzini, 2018/12/06
- [Qemu-devel] [PATCH 4/6] qemu/queue.h: reimplement QTAILQ without pointer-to-pointers, Paolo Bonzini, 2018/12/06
- Re: [Qemu-devel] [PATCH 4/6] qemu/queue.h: reimplement QTAILQ without pointer-to-pointers,
Markus Armbruster <=
- [Qemu-devel] [PATCH 6/6] checkpatch: warn about queue/queue.h head structs that are not typedef-ed, Paolo Bonzini, 2018/12/06