Re: [PATCH] util/async: make bh_aio_poll() O(1)

[Stefan Hajnoczi]

On Wed, Feb 19, 2020 at 12:09:48PM +0100, Paolo Bonzini wrote:
> Really a great idea, though I have some remarks on the implementation below.
> 
> On 19/02/20 11:00, Stefan Hajnoczi wrote:
> > + * Each aio_bh_poll() call carves off a slice of the BH list.  This way 
> > newly
> > + * scheduled BHs are not processed until the next aio_bh_poll() call.  This
> > + * concept extends to nested aio_bh_poll() calls because slices are chained
> > + * together.
> 
> This is the tricky part so I would expand a bit on why it's needed:
> 
> /*
>  * Each aio_bh_poll() call carves off a slice of the BH list, so that
>  * newly scheduled BHs are not processed until the next aio_bh_poll()
>  * call.  All active aio_bh_poll() calls chained their slices together
>  * in a list, so that nested aio_bh_poll() calls process all scheduled
>  * bottom halves.
>  */

Thanks, will fix in v2.

> > +struct BHListSlice {
> > +    QEMUBH *first_bh;
> > +    BHListSlice *next;
> > +};
> > +
> 
> Using QLIST and QSLIST removes the need to create your own lists, since
> you can use QSLIST_MOVE_ATOMIC and QSLIST_INSERT_HEAD_ATOMIC.  For example:
> 
> struct BHListSlice {
>     QSLIST_HEAD(, QEMUBH) first_bh;
>     QLIST_ENTRY(BHListSlice) next;
> };
> 
> ...
> 
>     QSLIST_HEAD(, QEMUBH) active_bh;
>     QLIST_HEAD(, BHListSlice) bh_list;

I thought about this but chose the explicit tail pointer approach
because it lets aio_compute_timeout() and aio_ctx_check() iterate over
both the active BH list and slices in a single for loop :).  But
thinking about it more, maybe it can still be done by replacing
active_bh with a permanently present first BHListSlice element.

> 
> Related to this, in the aio_bh_poll() loop:
> 
>     for (s = ctx->bh_list.next; s; s = s->next) {
>     }
> 
> You can actually do the removal inside the loop.  This is slightly more
> efficient since you can remove slices early from the nested
> aio_bh_poll().  Not that it's relevant for performance, but I think the
> FIFO order for slices is also more intuitive than LIFO.
> 
> Putting this idea together with the QLIST one, you would get:
> 
>     /*
>      * If a bottom half causes a recursive call, this slice will be
>      * removed by the nested aio_bh_poll().
>      */
>     QSLIST_MOVE_ATOMIC(&slice.first_bh, ctx->active_bh);
>     QLIST_INSERT_TAIL(&ctx->bh_list, slice);
>     while ((s = QLIST_FIRST(&ctx->bh_list)) {
>         while ((bh = aio_bh_dequeue(&s, &flags))) {
>         }
>         QLIST_REMOVE_HEAD(s, next);
>     }

Cool, reusing "queue.h" is nice.

> 
> >  /* Multiple occurrences of aio_bh_poll cannot be called concurrently.
> >   * The count in ctx->list_lock is incremented before the call, and is
> >   * not affected by the call.
> 
> The second sentence is now stale.

Thanks, will fix in v2.

Stefan

signature.asc
Description: PGP signature