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

[Paolo Bonzini <pbonzini@redhat.com>]

On 19/02/20 18:53, Stefan Hajnoczi wrote:
> The ctx->first_bh list contains all created BHs, including those that
> are not scheduled.  The list is iterated by the event loop and therefore
> has O(n) time complexity with respected to the number of created BHs.
> 
> Rewrite BHs so that only scheduled or deleted BHs are enqueued.
> Only BHs that actually require action will be iterated.
> 
> One semantic change is required: qemu_bh_delete() enqueues the BH and
> therefore invokes aio_notify().  The
> tests/test-aio.c:test_source_bh_delete_from_cb() test case assumed that
> g_main_context_iteration(NULL, false) returns false after
> qemu_bh_delete() but it now returns true for one iteration.  Fix up the
> test case.
> 
> This patch makes aio_compute_timeout() and aio_bh_poll() drop from a CPU
> profile reported by perf-top(1).  Previously they combined to 9% CPU
> utilization when AioContext polling is commented out and the guest has 2
> virtio-blk,num-queues=1 and 99 virtio-blk,num-queues=32 devices.
> 
> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
> ---
> v2:
>  * Use QSLIST for BHs and QSIMPLEQ for BHListSlices [Paolo]
>    (Note that I replaced bh = atomic_rcu_read(&first_bh) with
>     QSLIST_FOREACH(&bh_list) so there is no memory ordering but I think
>     this is safe.)

I have sent an implementation of QSLIST_FOREACH_RCU.  I doubt you'd see
any problem in practice, since RCU accesses only need a compiler
barrier, but it's cleaner.

With that changed,

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

Any further optimization of aio_compute_timeout() and aio_ctx_check()
can be done on top.

Paolo

> ---
>  include/block/aio.h |  20 +++-
>  tests/test-aio.c    |   3 +-
>  util/async.c        | 236 +++++++++++++++++++++++++-------------------
>  3 files changed, 157 insertions(+), 102 deletions(-)
> 
> diff --git a/include/block/aio.h b/include/block/aio.h
> index 7ba9bd7874..1a2ce9ca26 100644
> --- a/include/block/aio.h
> +++ b/include/block/aio.h
> @@ -51,6 +51,19 @@ struct ThreadPool;
>  struct LinuxAioState;
>  struct LuringState;
>  
> +/*
> + * 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 chain their slices together in a list, so that
> + * nested aio_bh_poll() calls process all scheduled bottom halves.
> + */
> +typedef QSLIST_HEAD(, QEMUBH) BHList;
> +typedef struct BHListSlice BHListSlice;
> +struct BHListSlice {
> +    BHList bh_list;
> +    QSIMPLEQ_ENTRY(BHListSlice) next;
> +};
> +
>  struct AioContext {
>      GSource source;
>  
> @@ -91,8 +104,11 @@ struct AioContext {
>       */
>      QemuLockCnt list_lock;
>  
> -    /* Anchor of the list of Bottom Halves belonging to the context */
> -    struct QEMUBH *first_bh;
> +    /* Bottom Halves pending aio_bh_poll() processing */
> +    BHList bh_list;
> +
> +    /* Chained BH list slices for each nested aio_bh_poll() call */
> +    QSIMPLEQ_HEAD(, BHListSlice) bh_slice_list;
>  
>      /* Used by aio_notify.
>       *
> diff --git a/tests/test-aio.c b/tests/test-aio.c
> index 86fb73b3d5..8a46078463 100644
> --- a/tests/test-aio.c
> +++ b/tests/test-aio.c
> @@ -615,7 +615,8 @@ static void test_source_bh_delete_from_cb(void)
>      g_assert_cmpint(data1.n, ==, data1.max);
>      g_assert(data1.bh == NULL);
>  
> -    g_assert(!g_main_context_iteration(NULL, false));
> +    assert(g_main_context_iteration(NULL, false));
> +    assert(!g_main_context_iteration(NULL, false));
>  }
>  
>  static void test_source_bh_delete_from_cb_many(void)
> diff --git a/util/async.c b/util/async.c
> index c192a24a61..2c8499cc29 100644
> --- a/util/async.c
> +++ b/util/async.c
> @@ -36,16 +36,76 @@
>  /***********************************************************/
>  /* bottom halves (can be seen as timers which expire ASAP) */
>  
> +/* QEMUBH::flags values */
> +enum {
> +    /* Already enqueued and waiting for aio_bh_poll() */
> +    BH_PENDING   = (1 << 0),
> +
> +    /* Invoke the callback */
> +    BH_SCHEDULED = (1 << 1),
> +
> +    /* Delete without invoking callback */
> +    BH_DELETED   = (1 << 2),
> +
> +    /* Delete after invoking callback */
> +    BH_ONESHOT   = (1 << 3),
> +
> +    /* Schedule periodically when the event loop is idle */
> +    BH_IDLE      = (1 << 4),
> +};
> +
>  struct QEMUBH {
>      AioContext *ctx;
>      QEMUBHFunc *cb;
>      void *opaque;
> -    QEMUBH *next;
> -    bool scheduled;
> -    bool idle;
> -    bool deleted;
> +    QSLIST_ENTRY(QEMUBH) next;
> +    unsigned flags;
>  };
>  
> +/* Called concurrently from any thread */
> +static void aio_bh_enqueue(QEMUBH *bh, unsigned new_flags)
> +{
> +    AioContext *ctx = bh->ctx;
> +    unsigned old_flags;
> +
> +    /*
> +     * The memory barrier implicit in atomic_fetch_or makes sure that:
> +     * 1. idle & any writes needed by the callback are done before the
> +     *    locations are read in the aio_bh_poll.
> +     * 2. ctx is loaded before the callback has a chance to execute and bh
> +     *    could be freed.
> +     */
> +    old_flags = atomic_fetch_or(&bh->flags, BH_PENDING | new_flags);
> +    if (!(old_flags & BH_PENDING)) {
> +        QSLIST_INSERT_HEAD_ATOMIC(&ctx->bh_list, bh, next);
> +    }
> +
> +    aio_notify(ctx);
> +}
> +
> +/* Only called from aio_bh_poll() and aio_ctx_finalize() */
> +static QEMUBH *aio_bh_dequeue(BHList *head, unsigned *flags)
> +{
> +    QEMUBH *bh = QSLIST_FIRST(head);
> +
> +    if (!bh) {
> +        return NULL;
> +    }
> +
> +    QSLIST_REMOVE_HEAD(head, next);
> +
> +    /*
> +     * The atomic_and is paired with aio_bh_enqueue().  The implicit memory
> +     * barrier ensures that the callback sees all writes done by the scheduling
> +     * thread.  It also ensures that the scheduling thread sees the cleared
> +     * flag before bh->cb has run, and thus will call aio_notify again if
> +     * necessary.
> +     */
> +    *flags = atomic_fetch_and(&bh->flags,
> +                              ~(BH_PENDING | BH_SCHEDULED | BH_IDLE));
> +    return bh;
> +}
> +
>  void aio_bh_schedule_oneshot(AioContext *ctx, QEMUBHFunc *cb, void *opaque)
>  {
>      QEMUBH *bh;
> @@ -55,15 +115,7 @@ void aio_bh_schedule_oneshot(AioContext *ctx, QEMUBHFunc *cb, void *opaque)
>          .cb = cb,
>          .opaque = opaque,
>      };
> -    qemu_lockcnt_lock(&ctx->list_lock);
> -    bh->next = ctx->first_bh;
> -    bh->scheduled = 1;
> -    bh->deleted = 1;
> -    /* Make sure that the members are ready before putting bh into list */
> -    smp_wmb();
> -    ctx->first_bh = bh;
> -    qemu_lockcnt_unlock(&ctx->list_lock);
> -    aio_notify(ctx);
> +    aio_bh_enqueue(bh, BH_SCHEDULED | BH_ONESHOT);
>  }
>  
>  QEMUBH *aio_bh_new(AioContext *ctx, QEMUBHFunc *cb, void *opaque)
> @@ -75,12 +127,6 @@ QEMUBH *aio_bh_new(AioContext *ctx, QEMUBHFunc *cb, void *opaque)
>          .cb = cb,
>          .opaque = opaque,
>      };
> -    qemu_lockcnt_lock(&ctx->list_lock);
> -    bh->next = ctx->first_bh;
> -    /* Make sure that the members are ready before putting bh into list */
> -    smp_wmb();
> -    ctx->first_bh = bh;
> -    qemu_lockcnt_unlock(&ctx->list_lock);
>      return bh;
>  }
>  
> @@ -89,91 +135,56 @@ void aio_bh_call(QEMUBH *bh)
>      bh->cb(bh->opaque);
>  }
>  
> -/* 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.
> - */
> +/* Multiple occurrences of aio_bh_poll cannot be called concurrently. */
>  int aio_bh_poll(AioContext *ctx)
>  {
> -    QEMUBH *bh, **bhp, *next;
> -    int ret;
> -    bool deleted = false;
> -
> -    ret = 0;
> -    for (bh = atomic_rcu_read(&ctx->first_bh); bh; bh = next) {
> -        next = atomic_rcu_read(&bh->next);
> -        /* The atomic_xchg is paired with the one in qemu_bh_schedule.  The
> -         * implicit memory barrier ensures that the callback sees all writes
> -         * done by the scheduling thread.  It also ensures that the scheduling
> -         * thread sees the zero before bh->cb has run, and thus will call
> -         * aio_notify again if necessary.
> -         */
> -        if (atomic_xchg(&bh->scheduled, 0)) {
> +    BHListSlice slice;
> +    BHListSlice *s;
> +    int ret = 0;
> +
> +    QSLIST_MOVE_ATOMIC(&slice.bh_list, &ctx->bh_list);
> +    QSIMPLEQ_INSERT_TAIL(&ctx->bh_slice_list, &slice, next);
> +
> +    while ((s = QSIMPLEQ_FIRST(&ctx->bh_slice_list))) {
> +        QEMUBH *bh;
> +        unsigned flags;
> +
> +        bh = aio_bh_dequeue(&s->bh_list, &flags);
> +        if (!bh) {
> +            QSIMPLEQ_REMOVE_HEAD(&ctx->bh_slice_list, next);
> +            continue;
> +        }
> +
> +        if ((flags & (BH_SCHEDULED | BH_DELETED)) == BH_SCHEDULED) {
>              /* Idle BHs don't count as progress */
> -            if (!bh->idle) {
> +            if (!(flags & BH_IDLE)) {
>                  ret = 1;
>              }
> -            bh->idle = 0;
>              aio_bh_call(bh);
>          }
> -        if (bh->deleted) {
> -            deleted = true;
> +        if (flags & (BH_DELETED | BH_ONESHOT)) {
> +            g_free(bh);
>          }
>      }
>  
> -    /* remove deleted bhs */
> -    if (!deleted) {
> -        return ret;
> -    }
> -
> -    if (qemu_lockcnt_dec_if_lock(&ctx->list_lock)) {
> -        bhp = &ctx->first_bh;
> -        while (*bhp) {
> -            bh = *bhp;
> -            if (bh->deleted && !bh->scheduled) {
> -                *bhp = bh->next;
> -                g_free(bh);
> -            } else {
> -                bhp = &bh->next;
> -            }
> -        }
> -        qemu_lockcnt_inc_and_unlock(&ctx->list_lock);
> -    }
>      return ret;
>  }
>  
>  void qemu_bh_schedule_idle(QEMUBH *bh)
>  {
> -    bh->idle = 1;
> -    /* Make sure that idle & any writes needed by the callback are done
> -     * before the locations are read in the aio_bh_poll.
> -     */
> -    atomic_mb_set(&bh->scheduled, 1);
> +    aio_bh_enqueue(bh, BH_SCHEDULED | BH_IDLE);
>  }
>  
>  void qemu_bh_schedule(QEMUBH *bh)
>  {
> -    AioContext *ctx;
> -
> -    ctx = bh->ctx;
> -    bh->idle = 0;
> -    /* The memory barrier implicit in atomic_xchg makes sure that:
> -     * 1. idle & any writes needed by the callback are done before the
> -     *    locations are read in the aio_bh_poll.
> -     * 2. ctx is loaded before scheduled is set and the callback has a chance
> -     *    to execute.
> -     */
> -    if (atomic_xchg(&bh->scheduled, 1) == 0) {
> -        aio_notify(ctx);
> -    }
> +    aio_bh_enqueue(bh, BH_SCHEDULED);
>  }
>  
> -
>  /* This func is async.
>   */
>  void qemu_bh_cancel(QEMUBH *bh)
>  {
> -    atomic_mb_set(&bh->scheduled, 0);
> +    atomic_and(&bh->flags, ~BH_SCHEDULED);
>  }
>  
>  /* This func is async.The bottom half will do the delete action at the finial
> @@ -181,21 +192,16 @@ void qemu_bh_cancel(QEMUBH *bh)
>   */
>  void qemu_bh_delete(QEMUBH *bh)
>  {
> -    bh->scheduled = 0;
> -    bh->deleted = 1;
> +    aio_bh_enqueue(bh, BH_DELETED);
>  }
>  
> -int64_t
> -aio_compute_timeout(AioContext *ctx)
> +static int64_t aio_compute_bh_timeout(BHList *head, int timeout)
>  {
> -    int64_t deadline;
> -    int timeout = -1;
>      QEMUBH *bh;
>  
> -    for (bh = atomic_rcu_read(&ctx->first_bh); bh;
> -         bh = atomic_rcu_read(&bh->next)) {
> -        if (bh->scheduled) {
> -            if (bh->idle) {
> +    QSLIST_FOREACH(bh, head, next) {
> +        if ((bh->flags & (BH_SCHEDULED | BH_DELETED)) == BH_SCHEDULED) {
> +            if (bh->flags & BH_IDLE) {
>                  /* idle bottom halves will be polled at least
>                   * every 10ms */
>                  timeout = 10000000;
> @@ -207,6 +213,28 @@ aio_compute_timeout(AioContext *ctx)
>          }
>      }
>  
> +    return timeout;
> +}
> +
> +int64_t
> +aio_compute_timeout(AioContext *ctx)
> +{
> +    BHListSlice *s;
> +    int64_t deadline;
> +    int timeout = -1;
> +
> +    timeout = aio_compute_bh_timeout(&ctx->bh_list, timeout);
> +    if (timeout == 0) {
> +        return 0;
> +    }
> +
> +    QSIMPLEQ_FOREACH(s, &ctx->bh_slice_list, next) {
> +        timeout = aio_compute_bh_timeout(&s->bh_list, timeout);
> +        if (timeout == 0) {
> +            return 0;
> +        }
> +    }
> +
>      deadline = timerlistgroup_deadline_ns(&ctx->tlg);
>      if (deadline == 0) {
>          return 0;
> @@ -237,15 +265,24 @@ aio_ctx_check(GSource *source)
>  {
>      AioContext *ctx = (AioContext *) source;
>      QEMUBH *bh;
> +    BHListSlice *s;
>  
>      atomic_and(&ctx->notify_me, ~1);
>      aio_notify_accept(ctx);
>  
> -    for (bh = ctx->first_bh; bh; bh = bh->next) {
> -        if (bh->scheduled) {
> +    QSLIST_FOREACH(bh, &ctx->bh_list, next) {
> +        if ((bh->flags & (BH_SCHEDULED | BH_DELETED)) == BH_SCHEDULED) {
>              return true;
>          }
>      }
> +
> +    QSIMPLEQ_FOREACH(s, &ctx->bh_slice_list, next) {
> +        QSLIST_FOREACH(bh, &s->bh_list, next) {
> +            if ((bh->flags & (BH_SCHEDULED | BH_DELETED)) == BH_SCHEDULED) {
> +                return true;
> +            }
> +        }
> +    }
>      return aio_pending(ctx) || (timerlistgroup_deadline_ns(&ctx->tlg) == 0);
>  }
>  
> @@ -265,6 +302,8 @@ static void
>  aio_ctx_finalize(GSource     *source)
>  {
>      AioContext *ctx = (AioContext *) source;
> +    QEMUBH *bh;
> +    unsigned flags;
>  
>      thread_pool_free(ctx->thread_pool);
>  
> @@ -287,18 +326,15 @@ aio_ctx_finalize(GSource     *source)
>      assert(QSLIST_EMPTY(&ctx->scheduled_coroutines));
>      qemu_bh_delete(ctx->co_schedule_bh);
>  
> -    qemu_lockcnt_lock(&ctx->list_lock);
> -    assert(!qemu_lockcnt_count(&ctx->list_lock));
> -    while (ctx->first_bh) {
> -        QEMUBH *next = ctx->first_bh->next;
> +    /* There must be no aio_bh_poll() calls going on */
> +    assert(QSIMPLEQ_EMPTY(&ctx->bh_slice_list));
>  
> +    while ((bh = aio_bh_dequeue(&ctx->bh_list, &flags))) {
>          /* qemu_bh_delete() must have been called on BHs in this AioContext */
> -        assert(ctx->first_bh->deleted);
> +        assert(flags & BH_DELETED);
>  
> -        g_free(ctx->first_bh);
> -        ctx->first_bh = next;
> +        g_free(bh);
>      }
> -    qemu_lockcnt_unlock(&ctx->list_lock);
>  
>      aio_set_event_notifier(ctx, &ctx->notifier, false, NULL, NULL);
>      event_notifier_cleanup(&ctx->notifier);
> @@ -445,6 +481,8 @@ AioContext *aio_context_new(Error **errp)
>      AioContext *ctx;
>  
>      ctx = (AioContext *) g_source_new(&aio_source_funcs, sizeof(AioContext));
> +    QSLIST_INIT(&ctx->bh_list);
> +    QSIMPLEQ_INIT(&ctx->bh_slice_list);
>      aio_context_setup(ctx);
>  
>      ret = event_notifier_init(&ctx->notifier, false);
>