Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Mon, 26 Sep 2022 20:39:03 -0700 (PDT)
From:   Hugh Dickins <hughd@google.com>
To:     Jan Kara <jack@suse.cz>
cc:     Hugh Dickins <hughd@google.com>, Keith Busch <kbusch@kernel.org>,
        Jens Axboe <axboe@kernel.dk>,
        Yu Kuai <yukuai1@huaweicloud.com>,
        Liu Song <liusong@linux.alibaba.com>,
        linux-block@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH next] sbitmap: fix lockup while swapping
In-Reply-To: <20220926114416.t7t65u66ze76aiz7@quack3>
Message-ID: <4539e48-417-edae-d42-9ef84602af0@google.com>
References: <aef9de29-e9f5-259a-f8be-12d1b734e72@google.com> <YyjdiKC0YYUkI+AI@kbusch-mbp> <f2d130d2-f3af-d09d-6fd7-10da28d26ba9@google.com> <20220921164012.s7lvklp2qk6occcg@quack3> <20220923144303.fywkmgnkg6eken4x@quack3> <d83885c9-2635-ef45-2ccc-a7e06421e1cc@google.com>
 <Yy4D54kPpenBkjHz@kbusch-mbp.dhcp.thefacebook.com> <391b1763-7146-857-e3b6-dc2a8e797162@google.com> <929a3aba-72b0-5e-5b80-824a2b7f5dc7@google.com> <20220926114416.t7t65u66ze76aiz7@quack3>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Precedence: bulk

On Mon, 26 Sep 2022, Jan Kara wrote:
> On Fri 23-09-22 16:15:29, Hugh Dickins wrote:
> 
> I don't think any magic with sbq_index_atomic_inc() is going to reliably
> fix this. After all the current waitqueue may be the only one that has active
> waiters so sbq_wake_ptr() will always end up returning this waitqueue
> regardless of the current value of sbq->wake_index.
> 
> Honestly, this whole code needs a serious redesign.

I was pleased to see you say so, Jan: I do agree.

> I have some
> simplifications in mind but it will take some thinking and benchmarking

I'm definitely not the right person to take it on, and glad if you can.
But I did have some thoughts and experiments over the weekend, and would
like to throw a couple of suggestions into the pot.

One, not a big issue, but I think sbq_index_atomic_inc() is misconceived.
It's unhelpful for multiple racers to be adjusting sbq->wake_index, and
	wake_index = ws - sbq->ws;
	atomic_cmpxchg(&sbq->wake_index, wake_index, sbq_index_inc(wake_index));
seems to me a better way for __sbq_wake_up() to increment it.

Two, and here the depths of my naivete and incomprehension may be on
display, but: I get the impression that __sbq_wake_up() is intended
to accumulate wake_batch-1 wakeups while doing nothing, then on the
wake_batch'th it hopes to do all those wake_batch wakeups.  I assume
someone in the past has established that that's a safe way to procede
here, though it's not obviously safe to me.

Now, those !waitqueue_active(&ws->wait) checks are good for catching
when the hoped-for procedure has gone so "wrong" that there's actually
nothing to be woken on this ws (so proceed to the next); but they give
no clue as to when there are some but not enough wakeups done.

It is very easy to add a wake_up_nr_return() to kernel/sched/wait.c,
which returns the nr_exclusive still not woken (__wake_up_common_lock()
merely has to return nr_exclusive itself); and then __sbq_wake_up() can
be recalled until wake_batch have been woken (or all queues empty).

I do have an experiment running that way: but my testing is much too
limited to draw serious conclusions from, and I've already admitted
that I may just be misunderstanding the whole thing.  But, just maybe,
a wake_up_nr_return() might be useful.  End of those suggestions.

> so
> we need some fix for the interim. I was pondering for quite some time about
> some band aid to the problem you've found but didn't find anything
> satisfactory.
> 
> In the end I see two options: 
> 
> 1) Take your patch (as wrong as it is ;). Yes, it can lead to lost wakeups
> but we were living with those for a relatively long time so probably we can
> live with them for some longer.

In getting that experiment above going, I did have to make this change
below: and it looks to me now as better than my original patch - since
this one does try all SBQ_WAIT_QUEUES before giving up, whereas my first
patch immediately gave up on the waitqueue_active !wait_cnt case.

--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -587,7 +587,7 @@ static struct sbq_wait_state *sbq_wake_p
 	for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
 		struct sbq_wait_state *ws = &sbq->ws[wake_index];
 
-		if (waitqueue_active(&ws->wait)) {
+		if (waitqueue_active(&ws->wait) && atomic_read(&ws->wait_cnt)) {
 			if (wake_index != atomic_read(&sbq->wake_index))
 				atomic_set(&sbq->wake_index, wake_index);
 			return ws;

TBH I have not tested this one outside of that experiment: would you
prefer this patch to my first one, I test and sign this off and send?

> 
> 2) Revert Yu Kuai's original fix 040b83fcecfb8 ("sbitmap: fix possible io
> hung due to lost wakeup") and my fixup 48c033314f37 ("sbitmap: Avoid leaving
> waitqueue in invalid state in __sbq_wake_up()"). But then Keith would have
> to redo his batched accounting patches on top.

I know much too little to help make that choice.

Hugh