[Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Ladi Prosek]

QSIMPLEQ supports appending to tail in O(1) and is intrusive so
it doesn't require extra memory allocations for the bookkeeping
data.

Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Ladi Prosek <lprosek@redhat.com>
---
 backends/rng-egd.c    |  9 ++++-----
 backends/rng-random.c |  6 +++---
 backends/rng.c        | 17 ++++++++++-------
 include/sysemu/rng.h  |  3 ++-
 4 files changed, 19 insertions(+), 16 deletions(-)

diff --git a/backends/rng-egd.c b/backends/rng-egd.c
index 30332ed..6e0ba22 100644
--- a/backends/rng-egd.c
+++ b/backends/rng-egd.c
@@ -49,11 +49,10 @@ static void rng_egd_request_entropy(RngBackend *b, RngRequest *req)
 static int rng_egd_chr_can_read(void *opaque)
 {
     RngEgd *s = RNG_EGD(opaque);
-    GSList *i;
+    RngRequest *req;
     int size = 0;
 
-    for (i = s->parent.requests; i; i = i->next) {
-        RngRequest *req = i->data;
+    QSIMPLEQ_FOREACH(req, &s->parent.requests, next) {
         size += req->size - req->offset;
     }
 
@@ -65,8 +64,8 @@ static void rng_egd_chr_read(void *opaque, const uint8_t *buf, int size)
     RngEgd *s = RNG_EGD(opaque);
     size_t buf_offset = 0;
 
-    while (size > 0 && s->parent.requests) {
-        RngRequest *req = s->parent.requests->data;
+    while (size > 0 && !QSIMPLEQ_EMPTY(&s->parent.requests)) {
+        RngRequest *req = QSIMPLEQ_FIRST(&s->parent.requests);
         int len = MIN(size, req->size - req->offset);
 
         memcpy(req->data + req->offset, buf + buf_offset, len);
diff --git a/backends/rng-random.c b/backends/rng-random.c
index a6cb385..122e8d4 100644
--- a/backends/rng-random.c
+++ b/backends/rng-random.c
@@ -35,8 +35,8 @@ static void entropy_available(void *opaque)
 {
     RndRandom *s = RNG_RANDOM(opaque);
 
-    while (s->parent.requests != NULL) {
-        RngRequest *req = s->parent.requests->data;
+    while (!QSIMPLEQ_EMPTY(&s->parent.requests)) {
+        RngRequest *req = QSIMPLEQ_FIRST(&s->parent.requests);
         ssize_t len;
 
         len = read(s->fd, req->data, req->size);
@@ -58,7 +58,7 @@ static void rng_random_request_entropy(RngBackend *b, RngRequest *req)
 {
     RndRandom *s = RNG_RANDOM(b);
 
-    if (s->parent.requests == NULL) {
+    if (QSIMPLEQ_EMPTY(&s->parent.requests)) {
         /* If there are no pending requests yet, we need to
          * install our fd handler. */
         qemu_set_fd_handler(s->fd, entropy_available, NULL, s);
diff --git a/backends/rng.c b/backends/rng.c
index 277a41b..e57e2b4 100644
--- a/backends/rng.c
+++ b/backends/rng.c
@@ -33,7 +33,7 @@ void rng_backend_request_entropy(RngBackend *s, size_t size,
 
         k->request_entropy(s, req);
 
-        s->requests = g_slist_append(s->requests, req);
+        QSIMPLEQ_INSERT_TAIL(&s->requests, req, next);
     }
 }
 
@@ -83,24 +83,27 @@ static void rng_backend_free_request(RngRequest *req)
 
 static void rng_backend_free_requests(RngBackend *s)
 {
-    GSList *i;
+    RngRequest *req, *next;
 
-    for (i = s->requests; i; i = i->next) {
-        rng_backend_free_request(i->data);
+    QSIMPLEQ_FOREACH_SAFE(req, &s->requests, next, next) {
+        rng_backend_free_request(req);
     }
 
-    g_slist_free(s->requests);
-    s->requests = NULL;
+    QSIMPLEQ_INIT(&s->requests);
 }
 
 void rng_backend_finalize_request(RngBackend *s, RngRequest *req)
 {
-    s->requests = g_slist_remove(s->requests, req);
+    QSIMPLEQ_REMOVE(&s->requests, req, RngRequest, next);
     rng_backend_free_request(req);
 }
 
 static void rng_backend_init(Object *obj)
 {
+    RngBackend *s = RNG_BACKEND(obj);
+
+    QSIMPLEQ_INIT(&s->requests);
+
     object_property_add_bool(obj, "opened",
                              rng_backend_prop_get_opened,
                              rng_backend_prop_set_opened,
diff --git a/include/sysemu/rng.h b/include/sysemu/rng.h
index a7ed580..4454722 100644
--- a/include/sysemu/rng.h
+++ b/include/sysemu/rng.h
@@ -40,6 +40,7 @@ struct RngRequest
     void *opaque;
     size_t offset;
     size_t size;
+    QSIMPLEQ_ENTRY(RngRequest) next;
 };
 
 struct RngBackendClass
@@ -57,7 +58,7 @@ struct RngBackend
 
     /*< protected >*/
     bool opened;
-    GSList *requests;
+    QSIMPLEQ_HEAD(requests, RngRequest) requests;
 };
 
 
-- 
2.5.0

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Paolo Bonzini]

On 03/03/2016 14:16, Ladi Prosek wrote:
> QSIMPLEQ supports appending to tail in O(1) and is intrusive so
> it doesn't require extra memory allocations for the bookkeeping
> data.
> 
> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> Signed-off-by: Ladi Prosek <lprosek@redhat.com>

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Thanks,

Paolo

> ---
>  backends/rng-egd.c    |  9 ++++-----
>  backends/rng-random.c |  6 +++---
>  backends/rng.c        | 17 ++++++++++-------
>  include/sysemu/rng.h  |  3 ++-
>  4 files changed, 19 insertions(+), 16 deletions(-)
> 
> diff --git a/backends/rng-egd.c b/backends/rng-egd.c
> index 30332ed..6e0ba22 100644
> --- a/backends/rng-egd.c
> +++ b/backends/rng-egd.c
> @@ -49,11 +49,10 @@ static void rng_egd_request_entropy(RngBackend *b, RngRequest *req)
>  static int rng_egd_chr_can_read(void *opaque)
>  {
>      RngEgd *s = RNG_EGD(opaque);
> -    GSList *i;
> +    RngRequest *req;
>      int size = 0;
>  
> -    for (i = s->parent.requests; i; i = i->next) {
> -        RngRequest *req = i->data;
> +    QSIMPLEQ_FOREACH(req, &s->parent.requests, next) {
>          size += req->size - req->offset;
>      }
>  
> @@ -65,8 +64,8 @@ static void rng_egd_chr_read(void *opaque, const uint8_t *buf, int size)
>      RngEgd *s = RNG_EGD(opaque);
>      size_t buf_offset = 0;
>  
> -    while (size > 0 && s->parent.requests) {
> -        RngRequest *req = s->parent.requests->data;
> +    while (size > 0 && !QSIMPLEQ_EMPTY(&s->parent.requests)) {
> +        RngRequest *req = QSIMPLEQ_FIRST(&s->parent.requests);
>          int len = MIN(size, req->size - req->offset);
>  
>          memcpy(req->data + req->offset, buf + buf_offset, len);
> diff --git a/backends/rng-random.c b/backends/rng-random.c
> index a6cb385..122e8d4 100644
> --- a/backends/rng-random.c
> +++ b/backends/rng-random.c
> @@ -35,8 +35,8 @@ static void entropy_available(void *opaque)
>  {
>      RndRandom *s = RNG_RANDOM(opaque);
>  
> -    while (s->parent.requests != NULL) {
> -        RngRequest *req = s->parent.requests->data;
> +    while (!QSIMPLEQ_EMPTY(&s->parent.requests)) {
> +        RngRequest *req = QSIMPLEQ_FIRST(&s->parent.requests);
>          ssize_t len;
>  
>          len = read(s->fd, req->data, req->size);
> @@ -58,7 +58,7 @@ static void rng_random_request_entropy(RngBackend *b, RngRequest *req)
>  {
>      RndRandom *s = RNG_RANDOM(b);
>  
> -    if (s->parent.requests == NULL) {
> +    if (QSIMPLEQ_EMPTY(&s->parent.requests)) {
>          /* If there are no pending requests yet, we need to
>           * install our fd handler. */
>          qemu_set_fd_handler(s->fd, entropy_available, NULL, s);
> diff --git a/backends/rng.c b/backends/rng.c
> index 277a41b..e57e2b4 100644
> --- a/backends/rng.c
> +++ b/backends/rng.c
> @@ -33,7 +33,7 @@ void rng_backend_request_entropy(RngBackend *s, size_t size,
>  
>          k->request_entropy(s, req);
>  
> -        s->requests = g_slist_append(s->requests, req);
> +        QSIMPLEQ_INSERT_TAIL(&s->requests, req, next);
>      }
>  }
>  
> @@ -83,24 +83,27 @@ static void rng_backend_free_request(RngRequest *req)
>  
>  static void rng_backend_free_requests(RngBackend *s)
>  {
> -    GSList *i;
> +    RngRequest *req, *next;
>  
> -    for (i = s->requests; i; i = i->next) {
> -        rng_backend_free_request(i->data);
> +    QSIMPLEQ_FOREACH_SAFE(req, &s->requests, next, next) {
> +        rng_backend_free_request(req);
>      }
>  
> -    g_slist_free(s->requests);
> -    s->requests = NULL;
> +    QSIMPLEQ_INIT(&s->requests);
>  }
>  
>  void rng_backend_finalize_request(RngBackend *s, RngRequest *req)
>  {
> -    s->requests = g_slist_remove(s->requests, req);
> +    QSIMPLEQ_REMOVE(&s->requests, req, RngRequest, next);
>      rng_backend_free_request(req);
>  }
>  
>  static void rng_backend_init(Object *obj)
>  {
> +    RngBackend *s = RNG_BACKEND(obj);
> +
> +    QSIMPLEQ_INIT(&s->requests);
> +
>      object_property_add_bool(obj, "opened",
>                               rng_backend_prop_get_opened,
>                               rng_backend_prop_set_opened,
> diff --git a/include/sysemu/rng.h b/include/sysemu/rng.h
> index a7ed580..4454722 100644
> --- a/include/sysemu/rng.h
> +++ b/include/sysemu/rng.h
> @@ -40,6 +40,7 @@ struct RngRequest
>      void *opaque;
>      size_t offset;
>      size_t size;
> +    QSIMPLEQ_ENTRY(RngRequest) next;
>  };
>  
>  struct RngBackendClass
> @@ -57,7 +58,7 @@ struct RngBackend
>  
>      /*< protected >*/
>      bool opened;
> -    GSList *requests;
> +    QSIMPLEQ_HEAD(requests, RngRequest) requests;
>  };
>  
>  
> 

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Amit Shah]

On (Thu) 03 Mar 2016 [14:16:11], Ladi Prosek wrote:
> QSIMPLEQ supports appending to tail in O(1) and is intrusive so
> it doesn't require extra memory allocations for the bookkeeping
> data.
> 
> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> Signed-off-by: Ladi Prosek <lprosek@redhat.com>

> @@ -83,24 +83,27 @@ static void rng_backend_free_request(RngRequest *req)
>  
>  static void rng_backend_free_requests(RngBackend *s)
>  {
> -    GSList *i;
> +    RngRequest *req, *next;
>  
> -    for (i = s->requests; i; i = i->next) {
> -        rng_backend_free_request(i->data);
> +    QSIMPLEQ_FOREACH_SAFE(req, &s->requests, next, next) {
> +        rng_backend_free_request(req);
>      }
>  
> -    g_slist_free(s->requests);
> -    s->requests = NULL;
> +    QSIMPLEQ_INIT(&s->requests);
>  }

This init here isn't necessary, the accessors for the queue will take
care of this.

		Amit

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Ladi Prosek]

On Fri, Mar 4, 2016 at 7:27 AM, Amit Shah <amit.shah@redhat.com> wrote:
> On (Thu) 03 Mar 2016 [14:16:11], Ladi Prosek wrote:
>> QSIMPLEQ supports appending to tail in O(1) and is intrusive so
>> it doesn't require extra memory allocations for the bookkeeping
>> data.
>>
>> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
>> Signed-off-by: Ladi Prosek <lprosek@redhat.com>
>
>> @@ -83,24 +83,27 @@ static void rng_backend_free_request(RngRequest *req)
>>
>>  static void rng_backend_free_requests(RngBackend *s)
>>  {
>> -    GSList *i;
>> +    RngRequest *req, *next;
>>
>> -    for (i = s->requests; i; i = i->next) {
>> -        rng_backend_free_request(i->data);
>> +    QSIMPLEQ_FOREACH_SAFE(req, &s->requests, next, next) {
>> +        rng_backend_free_request(req);
>>      }
>>
>> -    g_slist_free(s->requests);
>> -    s->requests = NULL;
>> +    QSIMPLEQ_INIT(&s->requests);
>>  }
>
> This init here isn't necessary, the accessors for the queue will take
> care of this.

We are basically purging the queue here and we want to leave it in a
consistent state. Without the QSIMPLEQ_INIT the queue head would
become a pair of dangling pointers. Let me know if I misunderstood
your comment.

>
>                 Amit

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Paolo Bonzini]

On 04/03/2016 09:04, Ladi Prosek wrote:
>>> >> +    QSIMPLEQ_INIT(&s->requests);
>>> >>  }
>> >
>> > This init here isn't necessary, the accessors for the queue will take
>> > care of this.
> We are basically purging the queue here and we want to leave it in a
> consistent state. Without the QSIMPLEQ_INIT the queue head would
> become a pair of dangling pointers. Let me know if I misunderstood
> your comment.

It wouldn't, check out QSIMPLEQ_REMOVE_HEAD:

#define QSIMPLEQ_REMOVE_HEAD(head, field) do {
    if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)
        (head)->sqh_last = &(head)->sqh_first;
} while (/*CONSTCOND*/0)

The queue would become { NULL, &s->requests.sqh_first }.  So the
QSIMPLEQ_INIT is indeed redundant.

Paolo

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Amit Shah]

On (Fri) 04 Mar 2016 [09:04:22], Ladi Prosek wrote:
> On Fri, Mar 4, 2016 at 7:27 AM, Amit Shah <amit.shah@redhat.com> wrote:
> > On (Thu) 03 Mar 2016 [14:16:11], Ladi Prosek wrote:
> >> QSIMPLEQ supports appending to tail in O(1) and is intrusive so
> >> it doesn't require extra memory allocations for the bookkeeping
> >> data.
> >>
> >> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> >> Signed-off-by: Ladi Prosek <lprosek@redhat.com>
> >
> >> @@ -83,24 +83,27 @@ static void rng_backend_free_request(RngRequest *req)
> >>
> >>  static void rng_backend_free_requests(RngBackend *s)
> >>  {
> >> -    GSList *i;
> >> +    RngRequest *req, *next;
> >>
> >> -    for (i = s->requests; i; i = i->next) {
> >> -        rng_backend_free_request(i->data);
> >> +    QSIMPLEQ_FOREACH_SAFE(req, &s->requests, next, next) {
> >> +        rng_backend_free_request(req);
> >>      }
> >>
> >> -    g_slist_free(s->requests);
> >> -    s->requests = NULL;
> >> +    QSIMPLEQ_INIT(&s->requests);
> >>  }
> >
> > This init here isn't necessary, the accessors for the queue will take
> > care of this.
> 
> We are basically purging the queue here and we want to leave it in a
> consistent state. Without the QSIMPLEQ_INIT the queue head would
> become a pair of dangling pointers. Let me know if I misunderstood
> your comment.

QSIMPLEQ_REMOVE does take care to assign NULL, so future
QSIMPLEQ_EMPTY, QSIMPLEQ_FIRST, etc., calls work just fine.

		Amit

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Ladi Prosek]

On Fri, Mar 4, 2016 at 10:12 AM, Paolo Bonzini <pbonzini@redhat.com> wrote:
>
>
> On 04/03/2016 09:04, Ladi Prosek wrote:
>>>> >> +    QSIMPLEQ_INIT(&s->requests);
>>>> >>  }
>>> >
>>> > This init here isn't necessary, the accessors for the queue will take
>>> > care of this.
>> We are basically purging the queue here and we want to leave it in a
>> consistent state. Without the QSIMPLEQ_INIT the queue head would
>> become a pair of dangling pointers. Let me know if I misunderstood
>> your comment.
>
> It wouldn't, check out QSIMPLEQ_REMOVE_HEAD:
>
> #define QSIMPLEQ_REMOVE_HEAD(head, field) do {
>     if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)
>         (head)->sqh_last = &(head)->sqh_first;
> } while (/*CONSTCOND*/0)
>
> The queue would become { NULL, &s->requests.sqh_first }.  So the
> QSIMPLEQ_INIT is indeed redundant.

Right, but we're not running QSIMPLEQ_REMOVE_HEAD in this function. We
iterate the queue and free all elements without writing anything to
the head or to the next ptr. This is the only "write" we do in
rng_backend_free_requests.

> Paolo

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Paolo Bonzini]

On 04/03/2016 10:19, Ladi Prosek wrote:
> On Fri, Mar 4, 2016 at 10:12 AM, Paolo Bonzini <pbonzini@redhat.com> wrote:
>>
>>
>> On 04/03/2016 09:04, Ladi Prosek wrote:
>>>>>>> +    QSIMPLEQ_INIT(&s->requests);
>>>>>>>  }
>>>>>
>>>>> This init here isn't necessary, the accessors for the queue will take
>>>>> care of this.
>>> We are basically purging the queue here and we want to leave it in a
>>> consistent state. Without the QSIMPLEQ_INIT the queue head would
>>> become a pair of dangling pointers. Let me know if I misunderstood
>>> your comment.
>>
>> It wouldn't, check out QSIMPLEQ_REMOVE_HEAD:
>>
>> #define QSIMPLEQ_REMOVE_HEAD(head, field) do {
>>     if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)
>>         (head)->sqh_last = &(head)->sqh_first;
>> } while (/*CONSTCOND*/0)
>>
>> The queue would become { NULL, &s->requests.sqh_first }.  So the
>> QSIMPLEQ_INIT is indeed redundant.
> 
> Right, but we're not running QSIMPLEQ_REMOVE_HEAD in this function. We
> iterate the queue and free all elements without writing anything to
> the head or to the next ptr. This is the only "write" we do in
> rng_backend_free_requests.

Ah, sorry, I was convinced that rng_backend_free_request did the remove,
but now I remember checking it yesterday (after making the same
reasoning as Amit) and indeed it doesn't. :)

So the patch is okay.  It's just a slightly unusual use of
QSIMPLEQ_FOREACH_SAFE.

Paolo

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Amit Shah]

On (Fri) 04 Mar 2016 [10:27:57], Paolo Bonzini wrote:
> 
> 
> On 04/03/2016 10:19, Ladi Prosek wrote:
> > On Fri, Mar 4, 2016 at 10:12 AM, Paolo Bonzini <pbonzini@redhat.com> wrote:
> >>
> >>
> >> On 04/03/2016 09:04, Ladi Prosek wrote:
> >>>>>>> +    QSIMPLEQ_INIT(&s->requests);
> >>>>>>>  }
> >>>>>
> >>>>> This init here isn't necessary, the accessors for the queue will take
> >>>>> care of this.
> >>> We are basically purging the queue here and we want to leave it in a
> >>> consistent state. Without the QSIMPLEQ_INIT the queue head would
> >>> become a pair of dangling pointers. Let me know if I misunderstood
> >>> your comment.
> >>
> >> It wouldn't, check out QSIMPLEQ_REMOVE_HEAD:
> >>
> >> #define QSIMPLEQ_REMOVE_HEAD(head, field) do {
> >>     if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)
> >>         (head)->sqh_last = &(head)->sqh_first;
> >> } while (/*CONSTCOND*/0)
> >>
> >> The queue would become { NULL, &s->requests.sqh_first }.  So the
> >> QSIMPLEQ_INIT is indeed redundant.
> > 
> > Right, but we're not running QSIMPLEQ_REMOVE_HEAD in this function. We
> > iterate the queue and free all elements without writing anything to
> > the head or to the next ptr. This is the only "write" we do in
> > rng_backend_free_requests.
> 
> Ah, sorry, I was convinced that rng_backend_free_request did the remove,
> but now I remember checking it yesterday (after making the same
> reasoning as Amit) and indeed it doesn't. :)
> 
> So the patch is okay.  It's just a slightly unusual use of
> QSIMPLEQ_FOREACH_SAFE.

Yeah, it's confusing when common idioms don't apply.

Nice attention to detail, Ladi :-)


		Amit

Re: [Qemu-devel] [PATCH] rng: switch request queue to QSIMPLEQ

[Amit Shah]

On (Thu) 03 Mar 2016 [14:16:11], Ladi Prosek wrote:
> QSIMPLEQ supports appending to tail in O(1) and is intrusive so
> it doesn't require extra memory allocations for the bookkeeping
> data.
> 
> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> Signed-off-by: Ladi Prosek <lprosek@redhat.com>

Reviewed-by: Amit Shah <amit.shah@redhat.com>

		Amit