Re: [RFC PATCH] sbitmap: fix batching wakeup

[Ming Lei <ming.lei@redhat.com>]

On Fri, Jul 21, 2023 at 12:35:43PM -0400, Gabriel Krisman Bertazi wrote:
> Ming Lei <ming.lei@redhat.com> writes:
> 
> > From: David Jeffery <djeffery@redhat.com>
> >
> > Current code supposes that it is enough to provide forward progress by just
> > waking up one wait queue after one completion batch is done.
> >
> > Unfortunately this way isn't enough, cause waiter can be added to
> > wait queue just after it is woken up.
> >
> > Follows one example(64 depth, wake_batch is 8)
> >
> > 1) all 64 tags are active
> >
> > 2) in each wait queue, there is only one single waiter
> >
> > 3) each time one completion batch(8 completions) wakes up just one waiter in each wait
> > queue, then immediately one new sleeper is added to this wait queue
> >
> > 4) after 64 completions, 8 waiters are wakeup, and there are still 8 waiters in each
> > wait queue
> >
> > 5) after another 8 active tags are completed, only one waiter can be wakeup, and the other 7
> > can't be waken up anymore.
> >
> > Turns out it isn't easy to fix this problem, so simply wakeup enough waiters for
> > single batch.
> 
> yes, I think this makes sense. When working on this algorithm I remember
> I considered it (thus wake_up_nr being ready), but ended up believing it
> wasn't needed.  please take:
> 
> Reviewed-by: Gabriel Krisman Bertazi <krisman@suse.de>
> 
> I wonder how likely it is to reach it.  Did you get a bug report?

It was reported from one RH customer, and I am also hit once
when running dbench on loop(bfq) over scsi_debug in my routine test.

David figured out the idea, and we discussed other solutions too, but
turns out others can't work, and the above (extreme)example seems easier
to follow, from me.

Per David's early analysis, it should be easier to trigger since commit
26edb30dd1c0 ("sbitmap: Try each queue to wake up at least one waiter")
because 'wake_index' isn't updated before calling wake_up_nr(), then
multiple completion batch may only wakeup one same wait queue, meantime
multiple sleepers are added to same wait queue.


Thanks, 
Ming