[Qemu-devel] [PATCH v2 0/5] qemu-queue cleanups

[Qemu-devel] [PATCH v2 0/5] qemu-queue cleanups

[Paolo Bonzini]

These patches slighly change the assortment of lists provided by
qemu-queue.  QCIRCLEQ is dropped, since it provides no real advantage
over QTAILQ (and in fact is unused).  QSLIST is introduced and used for
free lists.

QSIMPLEQ is left in, since it provides some memory saving over QTAILQ.

Stefan, these are a bit borderline for qemu-trivial.  Let me know
if they're fine.

Paolo Bonzini (5):
  notifier: switch to QLIST
  qemu-queue: add QSLIST
  qemu-queue: drop QCIRCLEQ
  coroutine: switch to QSLIST
  block: use QSLIST for the AIO free list

v1->v2: leave QSIMPLEQ in, add QSLIST (Peter)

 block.c              |    9 +-
 block_int.h          |    4 +-
 coroutine-ucontext.c |   10 +-
 input.c              |    2 +-
 migration.c          |    2 +-
 notify.c             |   10 +-
 notify.h             |    8 +-
 qemu-coroutine-int.h |    2 +-
 qemu-queue.h         |  205 +++++++++++++++++++++-----------------------------
 qemu-timer.c         |    2 +-
 vl.c                 |    2 +-
 11 files changed, 110 insertions(+), 146 deletions(-)

-- 
1.7.7.1

[Qemu-devel] [PATCH v2 1/5] notifier: switch to QLIST

[Paolo Bonzini]

Notifiers do not need to access both ends of the list, and using
a QLIST also simplifies the API.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 input.c      |    2 +-
 migration.c  |    2 +-
 notify.c     |   10 +++++-----
 notify.h     |    8 ++++----
 qemu-timer.c |    2 +-
 vl.c         |    2 +-
 6 files changed, 13 insertions(+), 13 deletions(-)

diff --git a/input.c b/input.c
index 9ade63f..b618ea4 100644
--- a/input.c
+++ b/input.c
@@ -268,5 +268,5 @@ void qemu_add_mouse_mode_change_notifier(Notifier *notify)
 
 void qemu_remove_mouse_mode_change_notifier(Notifier *notify)
 {
-    notifier_list_remove(&mouse_mode_notifiers, notify);
+    notifier_remove(notify);
 }
diff --git a/migration.c b/migration.c
index 412fdfe..0de907c 100644
--- a/migration.c
+++ b/migration.c
@@ -333,7 +333,7 @@ void add_migration_state_change_notifier(Notifier *notify)
 
 void remove_migration_state_change_notifier(Notifier *notify)
 {
-    notifier_list_remove(&migration_state_notifiers, notify);
+    notifier_remove(notify);
 }
 
 bool migration_is_active(MigrationState *s)
diff --git a/notify.c b/notify.c
index a6bac1f..ac05f91 100644
--- a/notify.c
+++ b/notify.c
@@ -16,24 +16,24 @@
 
 void notifier_list_init(NotifierList *list)
 {
-    QTAILQ_INIT(&list->notifiers);
+    QLIST_INIT(&list->notifiers);
 }
 
 void notifier_list_add(NotifierList *list, Notifier *notifier)
 {
-    QTAILQ_INSERT_HEAD(&list->notifiers, notifier, node);
+    QLIST_INSERT_HEAD(&list->notifiers, notifier, node);
 }
 
-void notifier_list_remove(NotifierList *list, Notifier *notifier)
+void notifier_remove(Notifier *notifier)
 {
-    QTAILQ_REMOVE(&list->notifiers, notifier, node);
+    QLIST_REMOVE(notifier, node);
 }
 
 void notifier_list_notify(NotifierList *list, void *data)
 {
     Notifier *notifier, *next;
 
-    QTAILQ_FOREACH_SAFE(notifier, &list->notifiers, node, next) {
+    QLIST_FOREACH_SAFE(notifier, &list->notifiers, node, next) {
         notifier->notify(notifier, data);
     }
 }
diff --git a/notify.h b/notify.h
index 54fc57c..03cf26c 100644
--- a/notify.h
+++ b/notify.h
@@ -21,22 +21,22 @@ typedef struct Notifier Notifier;
 struct Notifier
 {
     void (*notify)(Notifier *notifier, void *data);
-    QTAILQ_ENTRY(Notifier) node;
+    QLIST_ENTRY(Notifier) node;
 };
 
 typedef struct NotifierList
 {
-    QTAILQ_HEAD(, Notifier) notifiers;
+    QLIST_HEAD(, Notifier) notifiers;
 } NotifierList;
 
 #define NOTIFIER_LIST_INITIALIZER(head) \
-    { QTAILQ_HEAD_INITIALIZER((head).notifiers) }
+    { QLIST_HEAD_INITIALIZER((head).notifiers) }
 
 void notifier_list_init(NotifierList *list);
 
 void notifier_list_add(NotifierList *list, Notifier *notifier);
 
-void notifier_list_remove(NotifierList *list, Notifier *notifier);
+void notifier_remove(Notifier *notifier);
 
 void notifier_list_notify(NotifierList *list, void *data);
 
diff --git a/qemu-timer.c b/qemu-timer.c
index cd026c6..2eda9b9 100644
--- a/qemu-timer.c
+++ b/qemu-timer.c
@@ -453,7 +453,7 @@ void qemu_register_clock_reset_notifier(QEMUClock *clock, Notifier *notifier)
 
 void qemu_unregister_clock_reset_notifier(QEMUClock *clock, Notifier *notifier)
 {
-    notifier_list_remove(&clock->reset_notifiers, notifier);
+    notifier_remove(notifier);
 }
 
 void init_clocks(void)
diff --git a/vl.c b/vl.c
index ba55b35..4373f2a 100644
--- a/vl.c
+++ b/vl.c
@@ -2058,7 +2058,7 @@ void qemu_add_exit_notifier(Notifier *notify)
 
 void qemu_remove_exit_notifier(Notifier *notify)
 {
-    notifier_list_remove(&exit_notifiers, notify);
+    notifier_remove(notify);
 }
 
 static void qemu_run_exit_notifiers(void)
-- 
1.7.7.1

[Qemu-devel] [PATCH v2 2/5] qemu-queue: add QSLIST

[Paolo Bonzini]

Based on http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/queue.h?rev=1.53
with only the prefix change.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-queue.h |   87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 84 insertions(+), 3 deletions(-)

diff --git a/qemu-queue.h b/qemu-queue.h
index 2214230..6021057 100644
--- a/qemu-queue.h
+++ b/qemu-queue.h
@@ -2,8 +2,8 @@
 
 /*
  * Qemu version: Copy from netbsd, removed debug code, removed some of
- * the implementations.  Left in lists, simple queues, tail queues and
- * circular queues.
+ * the implementations.  Left in singly-linked lists, lists, simple
+ * queues, tail queues and circular queues.
  */
 
 /*
@@ -41,9 +41,19 @@
 #define QEMU_SYS_QUEUE_H_
 
 /*
- * This file defines four types of data structures:
+ * This file defines five types of data structures: singly-linked lists,
  * lists, simple queues, tail queues, and circular queues.
  *
+ * A singly-linked list is headed by a single forward pointer. The
+ * elements are singly linked for minimum space and pointer manipulation
+ * overhead at the expense of O(n) removal for arbitrary elements. New
+ * elements can be added to the list after an existing element or at the
+ * head of the list.  Elements being removed from the head of the list
+ * should use the explicit macro for this purpose for optimum
+ * efficiency. A singly-linked list may only be traversed in the forward
+ * direction.  Singly-linked lists are ideal for applications with large
+ * datasets and few or no removals or for implementing a LIFO queue.
+ *
  * A list is headed by a single forward pointer (or an array of forward
  * pointers for a hash table header). The elements are doubly linked
  * so that an arbitrary element can be removed without a need to
@@ -161,6 +171,64 @@ struct {                                                                \
 
 
 /*
+ * Singly-linked List definitions.
+ */
+#define QSLIST_HEAD(name, type)                                          \
+struct name {                                                           \
+        struct type *slh_first; /* first element */                     \
+}
+
+#define QSLIST_HEAD_INITIALIZER(head)                                    \
+        { NULL }
+
+#define QSLIST_ENTRY(type)                                               \
+struct {                                                                \
+        struct type *sle_next;  /* next element */                      \
+}
+
+/*
+ * Singly-linked List functions.
+ */
+#define QSLIST_INIT(head) do {                                           \
+        (head)->slh_first = NULL;                                       \
+} while (/*CONSTCOND*/0)
+
+#define QSLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
+        (elm)->field.sle_next = (slistelm)->field.sle_next;             \
+        (slistelm)->field.sle_next = (elm);                             \
+} while (/*CONSTCOND*/0)
+
+#define QSLIST_INSERT_HEAD(head, elm, field) do {                        \
+        (elm)->field.sle_next = (head)->slh_first;                      \
+        (head)->slh_first = (elm);                                      \
+} while (/*CONSTCOND*/0)
+
+#define QSLIST_REMOVE_HEAD(head, field) do {                             \
+        (head)->slh_first = (head)->slh_first->field.sle_next;          \
+} while (/*CONSTCOND*/0)
+
+#define QSLIST_REMOVE_AFTER(slistelm, field) do {                        \
+        (slistelm)->field.sle_next =                                    \
+            QSLIST_NEXT(QSLIST_NEXT((slistelm), field), field);           \
+} while (/*CONSTCOND*/0)
+
+#define QSLIST_FOREACH(var, head, field)                                 \
+        for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
+
+#define QSLIST_FOREACH_SAFE(var, head, field, tvar)                      \
+        for ((var) = QSLIST_FIRST((head));                               \
+            (var) && ((tvar) = QSLIST_NEXT((var), field), 1);            \
+            (var) = (tvar))
+
+/*
+ * Singly-linked List access methods.
+ */
+#define QSLIST_EMPTY(head)       ((head)->slh_first == NULL)
+#define QSLIST_FIRST(head)       ((head)->slh_first)
+#define QSLIST_NEXT(elm, field)  ((elm)->field.sle_next)
+
+
+/*
  * Simple queue definitions.
  */
 #define QSIMPLEQ_HEAD(name, type)                                       \
-- 
1.7.7.1

[Qemu-devel] [PATCH v2 3/5] qemu-queue: drop QCIRCLEQ

[Paolo Bonzini]

The main advantage of circular lists (the fact that the head node
has the same memory layout as any other node) is completely negated
by the implementation in qemu-queue.h.  Not surprisingly, nobody
uses QCIRCLEQ.  While this might change if RCU is ever adopted by
QEMU, the QLIST is also RCU-friendly and in fact it is used in a
RCU-like manner by 9pfs already.  So, just kill QCIRCLEQ.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-queue.h |  122 +--------------------------------------------------------
 1 files changed, 3 insertions(+), 119 deletions(-)

diff --git a/qemu-queue.h b/qemu-queue.h
index 6021057..92df809 100644
--- a/qemu-queue.h
+++ b/qemu-queue.h
@@ -3,7 +3,7 @@
 /*
  * Qemu version: Copy from netbsd, removed debug code, removed some of
  * the implementations.  Left in singly-linked lists, lists, simple
- * queues, tail queues and circular queues.
+ * queues, and tail queues.
  */
 
 /*
@@ -41,8 +41,8 @@
 #define QEMU_SYS_QUEUE_H_
 
 /*
- * This file defines five types of data structures: singly-linked lists,
- * lists, simple queues, tail queues, and circular queues.
+ * This file defines four types of data structures: singly-linked lists,
+ * lists, simple queues, and tail queues.
  *
  * A singly-linked list is headed by a single forward pointer. The
  * elements are singly linked for minimum space and pointer manipulation
@@ -75,14 +75,6 @@
  * after an existing element, at the head of the list, or at the end of
  * the list. A tail queue may be traversed in either direction.
  *
- * A circle queue is headed by a pair of pointers, one to the head of the
- * list and the other to the tail of the list. The elements are doubly
- * linked so that an arbitrary element can be removed without a need to
- * traverse the list. New elements can be added to the list before or after
- * an existing element, at the head of the list, or at the end of the list.
- * A circle queue may be traversed in either direction, but has a more
- * complex end of list detection.
- *
  * For details on the use of these macros, see the queue(3) manual page.
  */
 
@@ -432,112 +424,4 @@ struct {                                                                \
 #define QTAILQ_PREV(elm, headname, field) \
         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 
-
-/*
- * Circular queue definitions.
- */
-#define QCIRCLEQ_HEAD(name, type)                                       \
-struct name {                                                           \
-        struct type *cqh_first;         /* first element */             \
-        struct type *cqh_last;          /* last element */              \
-}
-
-#define QCIRCLEQ_HEAD_INITIALIZER(head)                                 \
-        { (void *)&head, (void *)&head }
-
-#define QCIRCLEQ_ENTRY(type)                                            \
-struct {                                                                \
-        struct type *cqe_next;          /* next element */              \
-        struct type *cqe_prev;          /* previous element */          \
-}
-
-/*
- * Circular queue functions.
- */
-#define QCIRCLEQ_INIT(head) do {                                        \
-        (head)->cqh_first = (void *)(head);                             \
-        (head)->cqh_last = (void *)(head);                              \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \
-        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
-        (elm)->field.cqe_prev = (listelm);                              \
-        if ((listelm)->field.cqe_next == (void *)(head))                \
-                (head)->cqh_last = (elm);                               \
-        else                                                            \
-                (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
-        (listelm)->field.cqe_next = (elm);                              \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {          \
-        (elm)->field.cqe_next = (listelm);                              \
-        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
-        if ((listelm)->field.cqe_prev == (void *)(head))                \
-                (head)->cqh_first = (elm);                              \
-        else                                                            \
-                (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
-        (listelm)->field.cqe_prev = (elm);                              \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_HEAD(head, elm, field) do {                     \
-        (elm)->field.cqe_next = (head)->cqh_first;                      \
-        (elm)->field.cqe_prev = (void *)(head);                         \
-        if ((head)->cqh_last == (void *)(head))                         \
-                (head)->cqh_last = (elm);                               \
-        else                                                            \
-                (head)->cqh_first->field.cqe_prev = (elm);              \
-        (head)->cqh_first = (elm);                                      \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_TAIL(head, elm, field) do {                     \
-        (elm)->field.cqe_next = (void *)(head);                         \
-        (elm)->field.cqe_prev = (head)->cqh_last;                       \
-        if ((head)->cqh_first == (void *)(head))                        \
-                (head)->cqh_first = (elm);                              \
-        else                                                            \
-                (head)->cqh_last->field.cqe_next = (elm);               \
-        (head)->cqh_last = (elm);                                       \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_REMOVE(head, elm, field) do {                          \
-        if ((elm)->field.cqe_next == (void *)(head))                    \
-                (head)->cqh_last = (elm)->field.cqe_prev;               \
-        else                                                            \
-                (elm)->field.cqe_next->field.cqe_prev =                 \
-                    (elm)->field.cqe_prev;                              \
-        if ((elm)->field.cqe_prev == (void *)(head))                    \
-                (head)->cqh_first = (elm)->field.cqe_next;              \
-        else                                                            \
-                (elm)->field.cqe_prev->field.cqe_next =                 \
-                    (elm)->field.cqe_next;                              \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_FOREACH(var, head, field)                              \
-        for ((var) = ((head)->cqh_first);                               \
-                (var) != (const void *)(head);                          \
-                (var) = ((var)->field.cqe_next))
-
-#define QCIRCLEQ_FOREACH_REVERSE(var, head, field)                      \
-        for ((var) = ((head)->cqh_last);                                \
-                (var) != (const void *)(head);                          \
-                (var) = ((var)->field.cqe_prev))
-
-/*
- * Circular queue access methods.
- */
-#define QCIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void *)(head))
-#define QCIRCLEQ_FIRST(head)             ((head)->cqh_first)
-#define QCIRCLEQ_LAST(head)              ((head)->cqh_last)
-#define QCIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
-#define QCIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
-
-#define QCIRCLEQ_LOOP_NEXT(head, elm, field)                            \
-        (((elm)->field.cqe_next == (void *)(head))                      \
-            ? ((head)->cqh_first)                                       \
-            : (elm->field.cqe_next))
-#define QCIRCLEQ_LOOP_PREV(head, elm, field)                            \
-        (((elm)->field.cqe_prev == (void *)(head))                      \
-            ? ((head)->cqh_last)                                        \
-            : (elm->field.cqe_prev))
-
 #endif  /* !QEMU_SYS_QUEUE_H_ */
-- 
1.7.7.1

[Qemu-devel] [PATCH v2 4/5] coroutine: switch to QSLIST

[Paolo Bonzini]

QSLIST can be used for a free list, do it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 coroutine-ucontext.c |   10 +++++-----
 qemu-coroutine-int.h |    2 +-
 2 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/coroutine-ucontext.c b/coroutine-ucontext.c
index 3d01075..5f43083 100644
--- a/coroutine-ucontext.c
+++ b/coroutine-ucontext.c
@@ -36,7 +36,7 @@ enum {
 };
 
 /** Free list to speed up creation */
-static QLIST_HEAD(, Coroutine) pool = QLIST_HEAD_INITIALIZER(pool);
+static QSLIST_HEAD(, Coroutine) pool = QSLIST_HEAD_INITIALIZER(pool);
 static unsigned int pool_size;
 
 typedef struct {
@@ -92,7 +92,7 @@ static void __attribute__((destructor)) coroutine_cleanup(void)
     Coroutine *co;
     Coroutine *tmp;
 
-    QLIST_FOREACH_SAFE(co, &pool, pool_next, tmp) {
+    QSLIST_FOREACH_SAFE(co, &pool, pool_next, tmp) {
         g_free(DO_UPCAST(CoroutineUContext, base, co)->stack);
         g_free(co);
     }
@@ -175,9 +175,9 @@ Coroutine *qemu_coroutine_new(void)
 {
     Coroutine *co;
 
-    co = QLIST_FIRST(&pool);
+    co = QSLIST_FIRST(&pool);
     if (co) {
-        QLIST_REMOVE(co, pool_next);
+        QSLIST_REMOVE_HEAD(&pool, pool_next);
         pool_size--;
     } else {
         co = coroutine_new();
@@ -190,7 +190,7 @@ void qemu_coroutine_delete(Coroutine *co_)
     CoroutineUContext *co = DO_UPCAST(CoroutineUContext, base, co_);
 
     if (pool_size < POOL_MAX_SIZE) {
-        QLIST_INSERT_HEAD(&pool, &co->base, pool_next);
+        QSLIST_INSERT_HEAD(&pool, &co->base, pool_next);
         co->base.caller = NULL;
         pool_size++;
         return;
diff --git a/qemu-coroutine-int.h b/qemu-coroutine-int.h
index d495615..0f1bd80 100644
--- a/qemu-coroutine-int.h
+++ b/qemu-coroutine-int.h
@@ -37,7 +37,7 @@ struct Coroutine {
     CoroutineEntry *entry;
     void *entry_arg;
     Coroutine *caller;
-    QLIST_ENTRY(Coroutine) pool_next;
+    QSLIST_ENTRY(Coroutine) pool_next;
     QTAILQ_ENTRY(Coroutine) co_queue_next;
 };
 
-- 
1.7.7.1

[Qemu-devel] [PATCH v2 5/5] block: use QSLIST for the AIO free list

[Paolo Bonzini]

QSLIST is equivalent to an open-coded free list, use it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 block.c     |    9 ++++-----
 block_int.h |    4 ++--
 2 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/block.c b/block.c
index 3f072f6..acb54b1 100644
--- a/block.c
+++ b/block.c
@@ -3242,9 +3242,9 @@ void *qemu_aio_get(AIOPool *pool, BlockDriverState *bs,
 {
     BlockDriverAIOCB *acb;
 
-    if (pool->free_aiocb) {
-        acb = pool->free_aiocb;
-        pool->free_aiocb = acb->next;
+    if (!QSLIST_EMPTY(pool->free_aiocb)) {
+        acb = QSLIST_FIRST(pool->free_aiocb);
+        QSLIST_REMOVE_HEAD(pool->free_aiocb, next);
     } else {
         acb = g_malloc0(pool->aiocb_size);
         acb->pool = pool;
@@ -3259,8 +3259,7 @@ void qemu_aio_release(void *p)
 {
     BlockDriverAIOCB *acb = (BlockDriverAIOCB *)p;
     AIOPool *pool = acb->pool;
-    acb->next = pool->free_aiocb;
-    pool->free_aiocb = acb;
+    QSLIST_INSERT_HEAD(pool->free_aiocb, acb, next);
 }
 
 /**************************************************************/
diff --git a/block_int.h b/block_int.h
index 311bd2a..c592e54 100644
--- a/block_int.h
+++ b/block_int.h
@@ -56,7 +56,7 @@ typedef struct BdrvTrackedRequest BdrvTrackedRequest;
 typedef struct AIOPool {
     void (*cancel)(BlockDriverAIOCB *acb);
     int aiocb_size;
-    BlockDriverAIOCB *free_aiocb;
+    QSLIST_HEAD(, BlockDriverAIOCB) *free_aiocb;
 } AIOPool;
 
 typedef struct BlockIOLimit {
@@ -268,7 +268,7 @@ struct BlockDriverAIOCB {
     BlockDriverState *bs;
     BlockDriverCompletionFunc *cb;
     void *opaque;
-    BlockDriverAIOCB *next;
+    QSLIST_ENTRY(BlockDriverAIOCB) next;
 };
 
 void get_tmp_filename(char *filename, int size);
-- 
1.7.7.1

Re: [Qemu-devel] [PATCH v2 3/5] qemu-queue: drop QCIRCLEQ

[Peter Maydell]

On 13 January 2012 16:34, Paolo Bonzini <pbonzini@redhat.com> wrote:
> The main advantage of circular lists (the fact that the head node
> has the same memory layout as any other node) is completely negated
> by the implementation in qemu-queue.h.  Not surprisingly, nobody
> uses QCIRCLEQ.  While this might change if RCU is ever adopted by
> QEMU, the QLIST is also RCU-friendly and in fact it is used in a
> RCU-like manner by 9pfs already.  So, just kill QCIRCLEQ.

Kirk McKusick on why CIRCLEQ existed in the first place and
why BSD still has it:
http://markmail.org/message/i5oir4jhmkopjzy5
...basically just legacy back-compat. So it's fine for us to drop
it from QEMU, since we have nothing to be back-compat with.

-- PMM

Re: [Qemu-devel] [PATCH v2 3/5] qemu-queue: drop QCIRCLEQ

[Paolo Bonzini]

On 01/13/2012 05:44 PM, Peter Maydell wrote:
>> The main advantage of circular lists (the fact that the head node
>> >  has the same memory layout as any other node) is completely negated
>> >  by the implementation in qemu-queue.h.  Not surprisingly, nobody
>> >  uses QCIRCLEQ.  While this might change if RCU is ever adopted by
>> >  QEMU, the QLIST is also RCU-friendly and in fact it is used in a
>> >  RCU-like manner by 9pfs already.  So, just kill QCIRCLEQ.
> Kirk McKusick on why CIRCLEQ existed in the first place and
> why BSD still has it:
> http://markmail.org/message/i5oir4jhmkopjzy5
> ...basically just legacy back-compat. So it's fine for us to drop
> it from QEMU, since we have nothing to be back-compat with.

Thanks for posting this.

I think it's not entirely correct because the cast in QTAILQ_PREV and 
QTAILQ_FOREACH_REVERSE does not look like valid ANSI C.  No matter how 
hard I look I admit I cannot figure out how it works, but anyway I 
suspect it can be changed to ANSI C using typeof if one was bitten by 
it.  So removing QCIRCLEQ is not a bad idea anyway.

BTW, NetBSD also has some STAILQ which looks entirely the same as SIMPLEQ.

Paolo

Re: [Qemu-devel] [PATCH v2 3/5] qemu-queue: drop QCIRCLEQ

[Paolo Bonzini]

On 01/13/2012 06:05 PM, Paolo Bonzini wrote:
> I think it's not entirely correct because the cast in QTAILQ_PREV and 
> QTAILQ_FOREACH_REVERSE does not look like valid ANSI C.  No matter how 
> hard I look I admit I cannot figure out how it works, but anyway I 
> suspect it can be changed to ANSI C using typeof if one was bitten by 
> it.  So removing QCIRCLEQ is not a bad idea anyway.

Ah, got it.  Here are two ways to rewrite it using typeof (not exactly
ANSI C of course, but perhaps somewhat more aliasing friendly).

#define QTAILQ_PREV(elm, next) \
        (*(((__typeof__((elm)->next) *)((elm)->next.tqe_prev))->tqe_prev))

#define Q_TAILQ_PREV(tqe) \
        ((__typeof__(tqe) *)((tqe).tqe_prev))
#define QTAILQ_PREV(elm, next) \
        (Q_TAILQ_PREV(*Q_TAILQ_PREV((elm)->next))->tqe_next)

It's treating the TAILQ as a half-linear (forwards), half-circular
(backwards) list.  Doing two backwards accesses and one forwards
access ensures that the last access is always on a pointer rather
than a pointer-to-pointer.  Clever.

Paolo

Re: [Qemu-devel] [PATCH v2 0/5] qemu-queue cleanups

[Paolo Bonzini]

On 01/13/2012 05:34 PM, Paolo Bonzini wrote:
> These patches slighly change the assortment of lists provided by
> qemu-queue.  QCIRCLEQ is dropped, since it provides no real advantage
> over QTAILQ (and in fact is unused).  QSLIST is introduced and used for
> free lists.
> 
> QSIMPLEQ is left in, since it provides some memory saving over QTAILQ.
> 
> Stefan, these are a bit borderline for qemu-trivial.  Let me know
> if they're fine.
> 
> Paolo Bonzini (5):
>   notifier: switch to QLIST
>   qemu-queue: add QSLIST
>   qemu-queue: drop QCIRCLEQ
>   coroutine: switch to QSLIST
>   block: use QSLIST for the AIO free list
> 
> v1->v2: leave QSIMPLEQ in, add QSLIST (Peter)
> 
>  block.c              |    9 +-
>  block_int.h          |    4 +-
>  coroutine-ucontext.c |   10 +-
>  input.c              |    2 +-
>  migration.c          |    2 +-
>  notify.c             |   10 +-
>  notify.h             |    8 +-
>  qemu-coroutine-int.h |    2 +-
>  qemu-queue.h         |  205 +++++++++++++++++++++-----------------------------
>  qemu-timer.c         |    2 +-
>  vl.c                 |    2 +-
>  11 files changed, 110 insertions(+), 146 deletions(-)
> 

Ping.

Paolo

Re: [Qemu-devel] [PATCH v2 5/5] block: use QSLIST for the AIO free list

[Anthony Liguori]

On 01/13/2012 10:34 AM, Paolo Bonzini wrote:
> QSLIST is equivalent to an open-coded free list, use it.
>
> Signed-off-by: Paolo Bonzini<pbonzini@redhat.com>

Surprisingly enough, this breaks hotplug (causes QEMU to segv).

I'll drop this patch and you can bring the next one in through Kevin's queue to 
make sure it gets adequate review.

Regards,

Anthony Liguori

> ---
>   block.c     |    9 ++++-----
>   block_int.h |    4 ++--
>   2 files changed, 6 insertions(+), 7 deletions(-)
>
> diff --git a/block.c b/block.c
> index 3f072f6..acb54b1 100644
> --- a/block.c
> +++ b/block.c
> @@ -3242,9 +3242,9 @@ void *qemu_aio_get(AIOPool *pool, BlockDriverState *bs,
>   {
>       BlockDriverAIOCB *acb;
>
> -    if (pool->free_aiocb) {
> -        acb = pool->free_aiocb;
> -        pool->free_aiocb = acb->next;
> +    if (!QSLIST_EMPTY(pool->free_aiocb)) {
> +        acb = QSLIST_FIRST(pool->free_aiocb);
> +        QSLIST_REMOVE_HEAD(pool->free_aiocb, next);
>       } else {
>           acb = g_malloc0(pool->aiocb_size);
>           acb->pool = pool;
> @@ -3259,8 +3259,7 @@ void qemu_aio_release(void *p)
>   {
>       BlockDriverAIOCB *acb = (BlockDriverAIOCB *)p;
>       AIOPool *pool = acb->pool;
> -    acb->next = pool->free_aiocb;
> -    pool->free_aiocb = acb;
> +    QSLIST_INSERT_HEAD(pool->free_aiocb, acb, next);
>   }
>
>   /**************************************************************/
> diff --git a/block_int.h b/block_int.h
> index 311bd2a..c592e54 100644
> --- a/block_int.h
> +++ b/block_int.h
> @@ -56,7 +56,7 @@ typedef struct BdrvTrackedRequest BdrvTrackedRequest;
>   typedef struct AIOPool {
>       void (*cancel)(BlockDriverAIOCB *acb);
>       int aiocb_size;
> -    BlockDriverAIOCB *free_aiocb;
> +    QSLIST_HEAD(, BlockDriverAIOCB) *free_aiocb;
>   } AIOPool;
>
>   typedef struct BlockIOLimit {
> @@ -268,7 +268,7 @@ struct BlockDriverAIOCB {
>       BlockDriverState *bs;
>       BlockDriverCompletionFunc *cb;
>       void *opaque;
> -    BlockDriverAIOCB *next;
> +    QSLIST_ENTRY(BlockDriverAIOCB) next;
>   };
>
>   void get_tmp_filename(char *filename, int size);

Re: [Qemu-devel] [PATCH v2 0/5] qemu-queue cleanups

[Anthony Liguori]

On 01/13/2012 10:34 AM, Paolo Bonzini wrote:
> These patches slighly change the assortment of lists provided by
> qemu-queue.  QCIRCLEQ is dropped, since it provides no real advantage
> over QTAILQ (and in fact is unused).  QSLIST is introduced and used for
> free lists.
>
> QSIMPLEQ is left in, since it provides some memory saving over QTAILQ.
>
> Stefan, these are a bit borderline for qemu-trivial.  Let me know
> if they're fine.

Applied 1-4 since 5 introduced a regression.  Thanks.

Regards,

Anthony Liguori

>
> Paolo Bonzini (5):
>    notifier: switch to QLIST
>    qemu-queue: add QSLIST
>    qemu-queue: drop QCIRCLEQ
>    coroutine: switch to QSLIST
>    block: use QSLIST for the AIO free list
>
> v1->v2: leave QSIMPLEQ in, add QSLIST (Peter)
>
>   block.c              |    9 +-
>   block_int.h          |    4 +-
>   coroutine-ucontext.c |   10 +-
>   input.c              |    2 +-
>   migration.c          |    2 +-
>   notify.c             |   10 +-
>   notify.h             |    8 +-
>   qemu-coroutine-int.h |    2 +-
>   qemu-queue.h         |  205 +++++++++++++++++++++-----------------------------
>   qemu-timer.c         |    2 +-
>   vl.c                 |    2 +-
>   11 files changed, 110 insertions(+), 146 deletions(-)
>