| Message ID | 1457010971-24771-1-git-send-email-lprosek@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
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; > }; > > >
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
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
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
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
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
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
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
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
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; };
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(-)