Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1438178 > unrolled thread

Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion NeilBrown <neilb@suse.com> - 2016-07-07 07:40 +0200
    Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion Lars Ellenberg <lars.ellenberg@linbit.com> - 2016-07-07 10:20 +0200
      Re: block: fix blk_queue_split() resource exhaustion Mike Snitzer <snitzer@redhat.com> - 2016-07-07 14:50 +0200
      Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion Lars Ellenberg <lars.ellenberg@linbit.com> - 2016-07-07 14:50 +0200
      Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion NeilBrown <neilb@suse.com> - 2016-07-08 00:10 +0200
        Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion Lars Ellenberg <lars.ellenberg@linbit.com> - 2016-07-08 10:10 +0200
          Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion NeilBrown <neilb@suse.com> - 2016-07-08 11:50 +0200
            Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion Lars Ellenberg <lars.ellenberg@linbit.com> - 2016-07-08 15:10 +0200
        Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion Ming Lei <ming.lei@canonical.com> - 2016-07-08 13:10 +0200
          Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion Lars Ellenberg <lars.ellenberg@linbit.com> - 2016-07-08 15:00 +0200
            Re: block: fix blk_queue_split() resource exhaustion Mike Snitzer <snitzer@redhat.com> - 2016-07-08 15:10 +0200
    Re: block: fix blk_queue_split() resource exhaustion Mike Snitzer <snitzer@redhat.com> - 2016-07-07 14:50 +0200
      Re: block: fix blk_queue_split() resource exhaustion NeilBrown <neilb@suse.com> - 2016-07-08 00:50 +0200

#1438178 — Re: [dm-devel] [RFC] block: fix blk_queue_split() resource exhaustion

[Multipart message — attachments visible in raw view] — view raw

On Wed, Jun 22 2016, Lars Ellenberg wrote:

> For a long time, generic_make_request() converts recursion into
> iteration by queuing recursive arguments on current->bio_list.
>
> This is convenient for stacking drivers,
> the top-most driver would take the originally submitted bio,
> and re-submit a re-mapped version of it, or one or more clones,
> or one or more new allocated bios to its backend(s). Which
> are then simply processed in turn, and each can again queue
> more "backend-bios" until we reach the bottom of the driver stack,
> and actually dispatch to the real backend device.
>
> Any stacking driver ->make_request_fn() could expect that,
> once it returns, any backend-bios it submitted via recursive calls
> to generic_make_request() would now be processed and dispatched, before
> the current task would call into this driver again.
>
> This is changed by commit
>   54efd50 block: make generic_make_request handle arbitrarily sized bios
>
> Drivers may call blk_queue_split() inside their ->make_request_fn(),
> which may split the current bio into a front-part to be dealt with
> immediately, and a remainder-part, which may need to be split even
> further. That remainder-part will simply also be pushed to
> current->bio_list, and would end up being head-of-queue, in front
> of any backend-bios the current make_request_fn() might submit during
> processing of the fron-part.
>
> Which means the current task would immediately end up back in the same
> make_request_fn() of the same driver again, before any of its backend
> bios have even been processed.
>
> This can lead to resource starvation deadlock.
> Drivers could avoid this by learning to not need blk_queue_split(),
> or by submitting their backend bios in a different context (dedicated
> kernel thread, work_queue context, ...). Or by playing funny re-ordering
> games with entries on current->bio_list.
>
> Instead, I suggest to distinguish between recursive calls to
> generic_make_request(), and pushing back the remainder part in
> blk_queue_split(), by pointing current->bio_lists to a
> 	struct recursion_to_iteration_bio_lists {
> 		struct bio_list recursion;
> 		struct bio_list remainder;
> 	}
>
> To have all bios targeted to drivers lower in the stack processed before
> processing the next piece of a bio targeted at the higher levels,
> as long as queued bios resulting from recursion are available,
> they will continue to be processed in FIFO order.
> Pushed back bio-parts resulting from blk_queue_split() will be processed
> in LIFO order, one-by-one, whenever the recursion list becomes empty.

I really like this change.  It seems to precisely address the problem.
The "problem" being that requests for "this" device are potentially
mixed up with requests from underlying devices.
However I'm not sure it is quite general enough.

The "remainder" list is a stack of requests aimed at "this" level or
higher, and I think it will always exactly fit that description.
The "recursion" list needs to be a queue of requests aimed at the next
level down, and that doesn't quiet work, because once you start acting
on the first entry in that list, all the rest become "this" level.

I think you can address this by always calling ->make_request_fn with an
empty "recursion", then after the call completes, splice the "recursion"
list that resulted (if any) on top of the "remainder" stack.

This way, the "remainder" stack is always "requests for lower-level
devices before request for upper level devices" and the "recursion"
queue is always "requests for devices below the current level".

I also really *don't* like the idea of punting to a separate thread - it
seems to be just delaying the problem.

Can you try move the bio_list_init(->recursion) call to just before
the ->make_request_fn() call, and adding
    bio_list_merge_head(->remainder, ->recursion)
just after?
(or something like that) and confirm it makes sense, and works?

Thanks!

NeilBrown

[toc] | [next] | [standalone]

#1438302

On Thu, Jul 07, 2016 at 03:35:48PM +1000, NeilBrown wrote:
> On Wed, Jun 22 2016, Lars Ellenberg wrote:
> 
> > For a long time, generic_make_request() converts recursion into
> > iteration by queuing recursive arguments on current->bio_list.
> >
> > This is convenient for stacking drivers,
> > the top-most driver would take the originally submitted bio,
> > and re-submit a re-mapped version of it, or one or more clones,
> > or one or more new allocated bios to its backend(s). Which
> > are then simply processed in turn, and each can again queue
> > more "backend-bios" until we reach the bottom of the driver stack,
> > and actually dispatch to the real backend device.
> >
> > Any stacking driver ->make_request_fn() could expect that,
> > once it returns, any backend-bios it submitted via recursive calls
> > to generic_make_request() would now be processed and dispatched, before
> > the current task would call into this driver again.
> >
> > This is changed by commit
> >   54efd50 block: make generic_make_request handle arbitrarily sized bios
> >
> > Drivers may call blk_queue_split() inside their ->make_request_fn(),
> > which may split the current bio into a front-part to be dealt with
> > immediately, and a remainder-part, which may need to be split even
> > further. That remainder-part will simply also be pushed to
> > current->bio_list, and would end up being head-of-queue, in front
> > of any backend-bios the current make_request_fn() might submit during
> > processing of the fron-part.
> >
> > Which means the current task would immediately end up back in the same
> > make_request_fn() of the same driver again, before any of its backend
> > bios have even been processed.
> >
> > This can lead to resource starvation deadlock.
> > Drivers could avoid this by learning to not need blk_queue_split(),
> > or by submitting their backend bios in a different context (dedicated
> > kernel thread, work_queue context, ...). Or by playing funny re-ordering
> > games with entries on current->bio_list.
> >
> > Instead, I suggest to distinguish between recursive calls to
> > generic_make_request(), and pushing back the remainder part in
> > blk_queue_split(), by pointing current->bio_lists to a
> > 	struct recursion_to_iteration_bio_lists {
> > 		struct bio_list recursion;
> > 		struct bio_list remainder;
> > 	}
> >
> > To have all bios targeted to drivers lower in the stack processed before
> > processing the next piece of a bio targeted at the higher levels,
> > as long as queued bios resulting from recursion are available,
> > they will continue to be processed in FIFO order.
> > Pushed back bio-parts resulting from blk_queue_split() will be processed
> > in LIFO order, one-by-one, whenever the recursion list becomes empty.
> 
> I really like this change.  It seems to precisely address the problem.
> The "problem" being that requests for "this" device are potentially
> mixed up with requests from underlying devices.
> However I'm not sure it is quite general enough.
> 
> The "remainder" list is a stack of requests aimed at "this" level or
> higher, and I think it will always exactly fit that description.
> The "recursion" list needs to be a queue of requests aimed at the next
> level down, and that doesn't quiet work, because once you start acting
> on the first entry in that list, all the rest become "this" level.

Uhm, well,
that's how it has been since you introduced this back in 2007, d89d879.
And it worked.

> I think you can address this by always calling ->make_request_fn with an
> empty "recursion", then after the call completes, splice the "recursion"
> list that resulted (if any) on top of the "remainder" stack.
> 
> This way, the "remainder" stack is always "requests for lower-level
> devices before request for upper level devices" and the "recursion"
> queue is always "requests for devices below the current level".

Yes, I guess that would work as well,
but may need "empirical proof" to check for performance regressions.

> I also really *don't* like the idea of punting to a separate thread - it
> seems to be just delaying the problem.
> 
> Can you try move the bio_list_init(->recursion) call to just before
> the ->make_request_fn() call, and adding
>     bio_list_merge_head(->remainder, ->recursion)
> just after?
> (or something like that) and confirm it makes sense, and works?

Sure, will do.
I'd suggest this would be a patch on its own though, on top of this one.
Because it would change the order in which stacked bios are processed
wrt the way it used to be since 2007 (my suggestion as is does not).

Which may change performance metrics.
It may even improve some of them,
or maybe it does nothing, but we don't know.

Thanks,

    Lars

[toc] | [prev] | [next] | [standalone]

#1438578 — Re: block: fix blk_queue_split() resource exhaustion

On Thu, Jul 07 2016 at  8:39am -0400,
Lars Ellenberg <lars.ellenberg@linbit.com> wrote:

> On Thu, Jul 07, 2016 at 10:16:16AM +0200, Lars Ellenberg wrote:
> > > > Instead, I suggest to distinguish between recursive calls to
> > > > generic_make_request(), and pushing back the remainder part in
> > > > blk_queue_split(), by pointing current->bio_lists to a
> > > > 	struct recursion_to_iteration_bio_lists {
> > > > 		struct bio_list recursion;
> > > > 		struct bio_list remainder;
> > > > 	}
> > > >
> > > > To have all bios targeted to drivers lower in the stack processed before
> > > > processing the next piece of a bio targeted at the higher levels,
> > > > as long as queued bios resulting from recursion are available,
> > > > they will continue to be processed in FIFO order.
> > > > Pushed back bio-parts resulting from blk_queue_split() will be processed
> > > > in LIFO order, one-by-one, whenever the recursion list becomes empty.
> > > 
> > > I really like this change.  It seems to precisely address the problem.
> > > The "problem" being that requests for "this" device are potentially
> > > mixed up with requests from underlying devices.
> > > However I'm not sure it is quite general enough.
> > > 
> > > The "remainder" list is a stack of requests aimed at "this" level or
> > > higher, and I think it will always exactly fit that description.
> > > The "recursion" list needs to be a queue of requests aimed at the next
> > > level down, and that doesn't quiet work, because once you start acting
> > > on the first entry in that list, all the rest become "this" level.
> > 
> > Uhm, well,
> > that's how it has been since you introduced this back in 2007, d89d879.
> > And it worked.
> > 
> > > I think you can address this by always calling ->make_request_fn with an
> > > empty "recursion", then after the call completes, splice the "recursion"
> > > list that resulted (if any) on top of the "remainder" stack.
> > > 
> > > This way, the "remainder" stack is always "requests for lower-level
> > > devices before request for upper level devices" and the "recursion"
> > > queue is always "requests for devices below the current level".
> > 
> > Yes, I guess that would work as well,
> > but may need "empirical proof" to check for performance regressions.
> > 
> > > I also really *don't* like the idea of punting to a separate thread - it
> > > seems to be just delaying the problem.
> > > 
> > > Can you try move the bio_list_init(->recursion) call to just before
> > > the ->make_request_fn() call, and adding
> > >     bio_list_merge_head(->remainder, ->recursion)
> > > just after?
> > > (or something like that) and confirm it makes sense, and works?
> > 
> > Sure, will do.
> 
> Attached,
> on top of the patch of my initial post.
> Also fixes the issue for me.
> 
> > I'd suggest this would be a patch on its own though, on top of this one.
> > Because it would change the order in which stacked bios are processed
> > wrt the way it used to be since 2007 (my suggestion as is does not).
> > 
> > Which may change performance metrics.
> > It may even improve some of them,
> > or maybe it does nothing, but we don't know.
> > 
> > Thanks,
> > 
> >     Lars
> > 

> From 73254eae63786aca0af10e42e5b41465c90d8da8 Mon Sep 17 00:00:00 2001
> From: Lars Ellenberg <lars.ellenberg@linbit.com>
> Date: Thu, 7 Jul 2016 11:03:30 +0200
> Subject: [PATCH] block: generic_make_request() recursive bios: process deepest
>  levels first
> 
> By providing each q->make_request_fn() with an empty "recursion"
> bio_list, then merging any recursively submitted bios to the
> head of the "remainder" list, we can make the recursion-to-iteration
> logic in generic_make_request() process deepest level bios first.
> 
> ---
> 
> As suggested by Neil Brown while discussing
> [RFC] block: fix blk_queue_split() resource exhaustion
> https://lkml.org/lkml/2016/7/7/27

Will look closer at this today, thanks!

[toc] | [prev] | [next] | [standalone]

#1438579

[Multipart message — attachments visible in raw view] — view raw

On Thu, Jul 07, 2016 at 10:16:16AM +0200, Lars Ellenberg wrote:
> > > Instead, I suggest to distinguish between recursive calls to
> > > generic_make_request(), and pushing back the remainder part in
> > > blk_queue_split(), by pointing current->bio_lists to a
> > > 	struct recursion_to_iteration_bio_lists {
> > > 		struct bio_list recursion;
> > > 		struct bio_list remainder;
> > > 	}
> > >
> > > To have all bios targeted to drivers lower in the stack processed before
> > > processing the next piece of a bio targeted at the higher levels,
> > > as long as queued bios resulting from recursion are available,
> > > they will continue to be processed in FIFO order.
> > > Pushed back bio-parts resulting from blk_queue_split() will be processed
> > > in LIFO order, one-by-one, whenever the recursion list becomes empty.
> > 
> > I really like this change.  It seems to precisely address the problem.
> > The "problem" being that requests for "this" device are potentially
> > mixed up with requests from underlying devices.
> > However I'm not sure it is quite general enough.
> > 
> > The "remainder" list is a stack of requests aimed at "this" level or
> > higher, and I think it will always exactly fit that description.
> > The "recursion" list needs to be a queue of requests aimed at the next
> > level down, and that doesn't quiet work, because once you start acting
> > on the first entry in that list, all the rest become "this" level.
> 
> Uhm, well,
> that's how it has been since you introduced this back in 2007, d89d879.
> And it worked.
> 
> > I think you can address this by always calling ->make_request_fn with an
> > empty "recursion", then after the call completes, splice the "recursion"
> > list that resulted (if any) on top of the "remainder" stack.
> > 
> > This way, the "remainder" stack is always "requests for lower-level
> > devices before request for upper level devices" and the "recursion"
> > queue is always "requests for devices below the current level".
> 
> Yes, I guess that would work as well,
> but may need "empirical proof" to check for performance regressions.
> 
> > I also really *don't* like the idea of punting to a separate thread - it
> > seems to be just delaying the problem.
> > 
> > Can you try move the bio_list_init(->recursion) call to just before
> > the ->make_request_fn() call, and adding
> >     bio_list_merge_head(->remainder, ->recursion)
> > just after?
> > (or something like that) and confirm it makes sense, and works?
> 
> Sure, will do.

Attached,
on top of the patch of my initial post.
Also fixes the issue for me.

> I'd suggest this would be a patch on its own though, on top of this one.
> Because it would change the order in which stacked bios are processed
> wrt the way it used to be since 2007 (my suggestion as is does not).
> 
> Which may change performance metrics.
> It may even improve some of them,
> or maybe it does nothing, but we don't know.
> 
> Thanks,
> 
>     Lars
> 

[toc] | [prev] | [next] | [standalone]

#1438951

[Multipart message — attachments visible in raw view] — view raw

On Thu, Jul 07 2016, Lars Ellenberg wrote:

> On Thu, Jul 07, 2016 at 03:35:48PM +1000, NeilBrown wrote:
>> On Wed, Jun 22 2016, Lars Ellenberg wrote:
>> 
>> > For a long time, generic_make_request() converts recursion into
>> > iteration by queuing recursive arguments on current->bio_list.
>> >
>> > This is convenient for stacking drivers,
>> > the top-most driver would take the originally submitted bio,
>> > and re-submit a re-mapped version of it, or one or more clones,
>> > or one or more new allocated bios to its backend(s). Which
>> > are then simply processed in turn, and each can again queue
>> > more "backend-bios" until we reach the bottom of the driver stack,
>> > and actually dispatch to the real backend device.
>> >
>> > Any stacking driver ->make_request_fn() could expect that,
>> > once it returns, any backend-bios it submitted via recursive calls
>> > to generic_make_request() would now be processed and dispatched, before
>> > the current task would call into this driver again.
>> >
>> > This is changed by commit
>> >   54efd50 block: make generic_make_request handle arbitrarily sized bios
>> >
>> > Drivers may call blk_queue_split() inside their ->make_request_fn(),
>> > which may split the current bio into a front-part to be dealt with
>> > immediately, and a remainder-part, which may need to be split even
>> > further. That remainder-part will simply also be pushed to
>> > current->bio_list, and would end up being head-of-queue, in front
>> > of any backend-bios the current make_request_fn() might submit during
>> > processing of the fron-part.
>> >
>> > Which means the current task would immediately end up back in the same
>> > make_request_fn() of the same driver again, before any of its backend
>> > bios have even been processed.
>> >
>> > This can lead to resource starvation deadlock.
>> > Drivers could avoid this by learning to not need blk_queue_split(),
>> > or by submitting their backend bios in a different context (dedicated
>> > kernel thread, work_queue context, ...). Or by playing funny re-ordering
>> > games with entries on current->bio_list.
>> >
>> > Instead, I suggest to distinguish between recursive calls to
>> > generic_make_request(), and pushing back the remainder part in
>> > blk_queue_split(), by pointing current->bio_lists to a
>> > 	struct recursion_to_iteration_bio_lists {
>> > 		struct bio_list recursion;
>> > 		struct bio_list remainder;
>> > 	}
>> >
>> > To have all bios targeted to drivers lower in the stack processed before
>> > processing the next piece of a bio targeted at the higher levels,
>> > as long as queued bios resulting from recursion are available,
>> > they will continue to be processed in FIFO order.
>> > Pushed back bio-parts resulting from blk_queue_split() will be processed
>> > in LIFO order, one-by-one, whenever the recursion list becomes empty.
>> 
>> I really like this change.  It seems to precisely address the problem.
>> The "problem" being that requests for "this" device are potentially
>> mixed up with requests from underlying devices.
>> However I'm not sure it is quite general enough.
>> 
>> The "remainder" list is a stack of requests aimed at "this" level or
>> higher, and I think it will always exactly fit that description.
>> The "recursion" list needs to be a queue of requests aimed at the next
>> level down, and that doesn't quiet work, because once you start acting
>> on the first entry in that list, all the rest become "this" level.
>
> Uhm, well,
> that's how it has been since you introduced this back in 2007, d89d879.
> And it worked.

Just because it "worked", doesn't mean it was "right" :-)

>
>> I think you can address this by always calling ->make_request_fn with an
>> empty "recursion", then after the call completes, splice the "recursion"
>> list that resulted (if any) on top of the "remainder" stack.
>> 
>> This way, the "remainder" stack is always "requests for lower-level
>> devices before request for upper level devices" and the "recursion"
>> queue is always "requests for devices below the current level".
>
> Yes, I guess that would work as well,
> but may need "empirical proof" to check for performance regressions.
>
>> I also really *don't* like the idea of punting to a separate thread - it
>> seems to be just delaying the problem.
>> 
>> Can you try move the bio_list_init(->recursion) call to just before
>> the ->make_request_fn() call, and adding
>>     bio_list_merge_head(->remainder, ->recursion)
>> just after?
>> (or something like that) and confirm it makes sense, and works?
>
> Sure, will do.
> I'd suggest this would be a patch on its own though, on top of this one.
> Because it would change the order in which stacked bios are processed
> wrt the way it used to be since 2007 (my suggestion as is does not).

Yes, because I think the original order is wrong, as you have helped me
to see.
Before I introduced the recursion limiting, requests were handled as an
in-order tree walk.  The code I wrote tried to preserve that but didn't
for several reasons.  I think we need to restore the original in-order
walk because it makes the most sense.
So after processing a particular bio, we should then process all the
'child' bios - bios send to underlying devices.  Then the 'sibling'
bios, that were split off, and then any remaining parents and ancestors.

You patch created the right structures for doing this, my proposal took
it a step closer, but now after more careful analysis I don't think it
is quite right.
With my previous proposal (and you latest patch - thanks!) requests for
"this" level are stacked, but they should be queued.
If a make_request_fn only ever submits one request for this level and
zero or more lower levels, then the difference between a queue and a
stack is irrelevant.  If it submited more that one, a stack would cause
them to be handled in the reverse order.

To make the patch "perfect", and maybe even more elegant we could treat
->remainder and ->recursion more alike.
i.e.:
  - generic make request has a private "stack" of requests.
  - before calling ->make_request_fn(), both ->remainder and ->recursion
    are initialised
  - after ->make_request_fn(), ->remainder are spliced in to top of
    'stack', then ->recursion is spliced onto that.
  - If stack is not empty, the top request is popped and we loop to top.

This reliably follows in-order execution, and handles siblings correctly
(in submitted order) if/when a request splits off multiple siblings.

>
> Which may change performance metrics.
> It may even improve some of them,
> or maybe it does nothing, but we don't know.

I think that as long a requests are submitted in the order they are
created at each level there is no reason to expect performance
regressions.
All we are doing is changing the ordering between requests generated at
different levels, and I think we are restoring a more natural order.

Thanks,
NeilBrown

[toc] | [prev] | [next] | [standalone]

#1439164

On Fri, Jul 08, 2016 at 08:07:52AM +1000, NeilBrown wrote:
> Before I introduced the recursion limiting, requests were handled as an
> in-order tree walk.  The code I wrote tried to preserve that but didn't
> for several reasons.  I think we need to restore the original in-order
> walk because it makes the most sense.
> So after processing a particular bio, we should then process all the
> 'child' bios - bios send to underlying devices.  Then the 'sibling'
> bios, that were split off, and then any remaining parents and ancestors.
> 
> You patch created the right structures for doing this, my proposal took
> it a step closer, but now after more careful analysis I don't think it
> is quite right.
> With my previous proposal (and you latest patch - thanks!) requests for
> "this" level are stacked, but they should be queued.
> If a make_request_fn only ever submits one request for this level and
> zero or more lower levels, then the difference between a queue and a
> stack is irrelevant.  If it submited more that one, a stack would cause
> them to be handled in the reverse order.

We have a device stack.
q_this_level->make_request_fn() cannot possibly submit anything
on "this_level", or it would create a device loop, I think.

So we start with the initial, "top most" call to generic_make_request().
That is one single bio. All queues are empty.

This bio is then passed on to its destination queue make_request_fn().

Which may chose to split it (via blk_queue_split, or like dm does, or
else). If it, like blk_queue_split() does, splits it into
"piece-I-can-handle-now" and "remainder", both still targeted at the
top most (current) queue, I think the "remainder" should just be pushed
back, which will make it look as if upper layers did
	generic_make_request("piece-I-can-handle-now");
	generic_make_request("remainder");
Which I do, by using bio_list_add_head(remainder, bio); (*head*).

I don't see any other way for a make_request_fn(bio(l=x)) to generate
"sibling" bios to the same level (l=x) as its own argument.

This same q(l=x)->make_request_fn(bio(l=x)) may now call
generic_make_request() for zero or more "child" bios (l=x+1),
which are queued in order: bio_list_add(recursion, bio); (*tail*).
Then, once l=x returns, the queue generated by it is spliced
in front of the "remainder" (*head*).
All bios are processed in the order they have been queued,
by peeling off of the head.

After all "child" bios of level l>=x+1 have been processed,
the next bio to be processed will be the "pushed back" remainder.

All "Natural order".

> To make the patch "perfect", and maybe even more elegant we could treat
> ->remainder and ->recursion more alike.
> i.e.:
>   - generic make request has a private "stack" of requests.
>   - before calling ->make_request_fn(), both ->remainder and ->recursion
>     are initialised
>   - after ->make_request_fn(), ->remainder are spliced in to top of
>     'stack', then ->recursion is spliced onto that.
>   - If stack is not empty, the top request is popped and we loop to top.
> 
> This reliably follows in-order execution, and handles siblings correctly
> (in submitted order) if/when a request splits off multiple siblings.

The only splitting that creates siblings on the current level
is blk_queue_split(), which splits the current bio into
"front piece" and "remainder", already processed in this order.

Anything else creating "siblings" is not creating siblings for the
current layer, but for the next deeper layer, which are queue on
"recursion" and also processed in the order they have been generated.

> I think that as long a requests are submitted in the order they are
> created at each level there is no reason to expect performance
> regressions.
> All we are doing is changing the ordering between requests generated at
> different levels, and I think we are restoring a more natural order.

I believe both patches combined are doing exactly this already.
I could rename .remainder to .todo or .incoming, though.

.incoming = [ bio(l=0) ]
.recursion = []

split

.incoming = [ bio(l=0,now_1), bio(l=0,remainder_1) ]
.recursion = []

process head of .incoming

.incoming = [ bio(l=0,remainder_1) ]
.recursion = [ bio(l=1,a), bio(l=1,b), bio(l=1,c), ... ]

merge_head

.incoming = [ bio(l=1,a), bio(l=1,b), bio(l=1,c), ...,
		bio(l=0,remainder_1) ]
.recursion = []

process head of .incoming, potentially split first

.incoming = [ bio(l=1,a,now), bio(l=1,a,remainder), bio(l=1,b), bio(l=1,c), ...,
		bio(l=0,remainder_1) ]
...
.incoming = [ bio(l=1,a,remainder), bio(l=1,b), bio(l=1,c), ...,
		bio(l=0,remainder_1) ]
.recursion = [ bio(l=2,aa), bio(l=2,ab), ... ]

merge_head

.incoming = [ bio(l=2,aa), bio(l=2,ab), ...,
		bio(l=1,a,remainder), bio(l=1,b), bio(l=1,c), ...,
		bio(l=0,remainder_1) ]
.recursion = []

...

process away ... until back at l=0

.incoming = [ bio(l=0,remainder_1) ]
.recursion = []

potentially split further
.incoming = [ bio(l=0,now_2), bio(l=0,remainder_2) ]
.recursion = []

rinse, repeat.

Thanks,

    Lars Ellenberg

[toc] | [prev] | [next] | [standalone]

#1439254

[Multipart message — attachments visible in raw view] — view raw

On Fri, Jul 08 2016, Lars Ellenberg wrote:

> On Fri, Jul 08, 2016 at 08:07:52AM +1000, NeilBrown wrote:
>> Before I introduced the recursion limiting, requests were handled as an
>> in-order tree walk.  The code I wrote tried to preserve that but didn't
>> for several reasons.  I think we need to restore the original in-order
>> walk because it makes the most sense.
>> So after processing a particular bio, we should then process all the
>> 'child' bios - bios send to underlying devices.  Then the 'sibling'
>> bios, that were split off, and then any remaining parents and ancestors.
>> 
>> You patch created the right structures for doing this, my proposal took
>> it a step closer, but now after more careful analysis I don't think it
>> is quite right.
>> With my previous proposal (and you latest patch - thanks!) requests for
>> "this" level are stacked, but they should be queued.
>> If a make_request_fn only ever submits one request for this level and
>> zero or more lower levels, then the difference between a queue and a
>> stack is irrelevant.  If it submited more that one, a stack would cause
>> them to be handled in the reverse order.
>
> We have a device stack.
> q_this_level->make_request_fn() cannot possibly submit anything
> on "this_level", or it would create a device loop, I think.
>
> So we start with the initial, "top most" call to generic_make_request().
> That is one single bio. All queues are empty.
>
> This bio is then passed on to its destination queue make_request_fn().
>
> Which may chose to split it (via blk_queue_split, or like dm does, or
> else). If it, like blk_queue_split() does, splits it into
> "piece-I-can-handle-now" and "remainder", both still targeted at the
> top most (current) queue, I think the "remainder" should just be pushed
> back, which will make it look as if upper layers did
> 	generic_make_request("piece-I-can-handle-now");
> 	generic_make_request("remainder");
> Which I do, by using bio_list_add_head(remainder, bio); (*head*).

This is exactly what I mean by "submitting a request at 'this' level".
Maybe that is a poor way to express it.  Within a make_request_fn, you
cannot "submit" a request, you can only "queue" a request.
generic_make_request hides that by doing something different for a call
From a make_request_fn that for a call from anywhere else.
The important thing is to have 2 queues to queue to.

>
> I don't see any other way for a make_request_fn(bio(l=x)) to generate
> "sibling" bios to the same level (l=x) as its own argument.

Yes, it only comes from splitting.

>
> This same q(l=x)->make_request_fn(bio(l=x)) may now call
> generic_make_request() for zero or more "child" bios (l=x+1),
> which are queued in order: bio_list_add(recursion, bio); (*tail*).
> Then, once l=x returns, the queue generated by it is spliced
> in front of the "remainder" (*head*).
> All bios are processed in the order they have been queued,
> by peeling off of the head.
>
> After all "child" bios of level l>=x+1 have been processed,
> the next bio to be processed will be the "pushed back" remainder.
>
> All "Natural order".
>
>> To make the patch "perfect", and maybe even more elegant we could treat
>> ->remainder and ->recursion more alike.
>> i.e.:
>>   - generic make request has a private "stack" of requests.
>>   - before calling ->make_request_fn(), both ->remainder and ->recursion
>>     are initialised
>>   - after ->make_request_fn(), ->remainder are spliced in to top of
>>     'stack', then ->recursion is spliced onto that.
>>   - If stack is not empty, the top request is popped and we loop to top.
>> 
>> This reliably follows in-order execution, and handles siblings correctly
>> (in submitted order) if/when a request splits off multiple siblings.
>
> The only splitting that creates siblings on the current level
> is blk_queue_split(), which splits the current bio into
> "front piece" and "remainder", already processed in this order.

Yes.
I imagine that a driver *could* split a bio into three parts with a
single allocation, but I cannot actually see any point in doing it.  So
I was over-complicating things.

>
> Anything else creating "siblings" is not creating siblings for the
> current layer, but for the next deeper layer, which are queue on
> "recursion" and also processed in the order they have been generated.
>
>> I think that as long a requests are submitted in the order they are
>> created at each level there is no reason to expect performance
>> regressions.
>> All we are doing is changing the ordering between requests generated at
>> different levels, and I think we are restoring a more natural order.
>
> I believe both patches combined are doing exactly this already.
> I could rename .remainder to .todo or .incoming, though.

:-)  neither "remainder" or "recursion" seem like brilliant names to me,
but I don't have anything better to suggest.  Naming is hard!
As long as a comment explains the name clearly I could cope with X and Y.

>
> .incoming = [ bio(l=0) ]
> .recursion = []
>
> split
>
> .incoming = [ bio(l=0,now_1), bio(l=0,remainder_1) ]
> .recursion = []
>
> process head of .incoming
>
> .incoming = [ bio(l=0,remainder_1) ]
> .recursion = [ bio(l=1,a), bio(l=1,b), bio(l=1,c), ... ]
>
> merge_head
>
> .incoming = [ bio(l=1,a), bio(l=1,b), bio(l=1,c), ...,
> 		bio(l=0,remainder_1) ]
> .recursion = []
>
> process head of .incoming, potentially split first
>
> .incoming = [ bio(l=1,a,now), bio(l=1,a,remainder), bio(l=1,b), bio(l=1,c), ...,
> 		bio(l=0,remainder_1) ]
> ...
> .incoming = [ bio(l=1,a,remainder), bio(l=1,b), bio(l=1,c), ...,
> 		bio(l=0,remainder_1) ]
> .recursion = [ bio(l=2,aa), bio(l=2,ab), ... ]
>
> merge_head
>
> .incoming = [ bio(l=2,aa), bio(l=2,ab), ...,
> 		bio(l=1,a,remainder), bio(l=1,b), bio(l=1,c), ...,
> 		bio(l=0,remainder_1) ]
> .recursion = []
>
> ...
>
> process away ... until back at l=0
>
> .incoming = [ bio(l=0,remainder_1) ]
> .recursion = []
>
> potentially split further
> .incoming = [ bio(l=0,now_2), bio(l=0,remainder_2) ]
> .recursion = []
>
> rinse, repeat.

I think we just might be in violent agreement.

Thanks,
NeilBrown

[toc] | [prev] | [next] | [standalone]

#1439436

On Fri, Jul 08, 2016 at 07:39:36PM +1000, NeilBrown wrote:
> >> To make the patch "perfect", and maybe even more elegant we could treat
> >> ->remainder and ->recursion more alike.
> >> i.e.:
> >>   - generic make request has a private "stack" of requests.
> >>   - before calling ->make_request_fn(), both ->remainder and ->recursion
> >>     are initialised
> >>   - after ->make_request_fn(), ->remainder are spliced in to top of
> >>     'stack', then ->recursion is spliced onto that.
> >>   - If stack is not empty, the top request is popped and we loop to top.
> >> 
> >> This reliably follows in-order execution, and handles siblings correctly
> >> (in submitted order) if/when a request splits off multiple siblings.
> >
> > The only splitting that creates siblings on the current level
> > is blk_queue_split(), which splits the current bio into
> > "front piece" and "remainder", already processed in this order.
> 
> Yes.
> I imagine that a driver *could* split a bio into three parts with a
> single allocation, but I cannot actually see any point in doing it.  So
> I was over-complicating things.
> 
> >
> > Anything else creating "siblings" is not creating siblings for the
> > current layer, but for the next deeper layer, which are queue on
> > "recursion" and also processed in the order they have been generated.
> >
> >> I think that as long a requests are submitted in the order they are
> >> created at each level there is no reason to expect performance
> >> regressions.
> >> All we are doing is changing the ordering between requests generated at
> >> different levels, and I think we are restoring a more natural order.
> >
> > I believe both patches combined are doing exactly this already.
> > I could rename .remainder to .todo or .incoming, though.
> 
> :-)  neither "remainder" or "recursion" seem like brilliant names to me,
> but I don't have anything better to suggest.  Naming is hard!
> As long as a comment explains the name clearly I could cope with X and Y.

...

> I think we just might be in violent agreement.

I thought so, too :-)

Should I merge both patches,
rename to ".queue" and ".tmp",
and submit for inclusion?

    Lars Ellenberg

[toc] | [prev] | [next] | [standalone]

#1439297

On Fri, Jul 8, 2016 at 6:07 AM, NeilBrown <neilb@suse.com> wrote:
> On Thu, Jul 07 2016, Lars Ellenberg wrote:
>
>> On Thu, Jul 07, 2016 at 03:35:48PM +1000, NeilBrown wrote:
>>> On Wed, Jun 22 2016, Lars Ellenberg wrote:
>>>
>>> > For a long time, generic_make_request() converts recursion into
>>> > iteration by queuing recursive arguments on current->bio_list.
>>> >
>>> > This is convenient for stacking drivers,
>>> > the top-most driver would take the originally submitted bio,
>>> > and re-submit a re-mapped version of it, or one or more clones,
>>> > or one or more new allocated bios to its backend(s). Which
>>> > are then simply processed in turn, and each can again queue
>>> > more "backend-bios" until we reach the bottom of the driver stack,
>>> > and actually dispatch to the real backend device.
>>> >
>>> > Any stacking driver ->make_request_fn() could expect that,
>>> > once it returns, any backend-bios it submitted via recursive calls
>>> > to generic_make_request() would now be processed and dispatched, before
>>> > the current task would call into this driver again.
>>> >
>>> > This is changed by commit
>>> >   54efd50 block: make generic_make_request handle arbitrarily sized bios
>>> >
>>> > Drivers may call blk_queue_split() inside their ->make_request_fn(),
>>> > which may split the current bio into a front-part to be dealt with
>>> > immediately, and a remainder-part, which may need to be split even
>>> > further. That remainder-part will simply also be pushed to
>>> > current->bio_list, and would end up being head-of-queue, in front
>>> > of any backend-bios the current make_request_fn() might submit during
>>> > processing of the fron-part.
>>> >
>>> > Which means the current task would immediately end up back in the same
>>> > make_request_fn() of the same driver again, before any of its backend
>>> > bios have even been processed.
>>> >
>>> > This can lead to resource starvation deadlock.
>>> > Drivers could avoid this by learning to not need blk_queue_split(),
>>> > or by submitting their backend bios in a different context (dedicated
>>> > kernel thread, work_queue context, ...). Or by playing funny re-ordering
>>> > games with entries on current->bio_list.
>>> >
>>> > Instead, I suggest to distinguish between recursive calls to
>>> > generic_make_request(), and pushing back the remainder part in
>>> > blk_queue_split(), by pointing current->bio_lists to a
>>> >    struct recursion_to_iteration_bio_lists {
>>> >            struct bio_list recursion;
>>> >            struct bio_list remainder;
>>> >    }
>>> >
>>> > To have all bios targeted to drivers lower in the stack processed before
>>> > processing the next piece of a bio targeted at the higher levels,
>>> > as long as queued bios resulting from recursion are available,
>>> > they will continue to be processed in FIFO order.
>>> > Pushed back bio-parts resulting from blk_queue_split() will be processed
>>> > in LIFO order, one-by-one, whenever the recursion list becomes empty.
>>>
>>> I really like this change.  It seems to precisely address the problem.
>>> The "problem" being that requests for "this" device are potentially
>>> mixed up with requests from underlying devices.
>>> However I'm not sure it is quite general enough.
>>>
>>> The "remainder" list is a stack of requests aimed at "this" level or
>>> higher, and I think it will always exactly fit that description.
>>> The "recursion" list needs to be a queue of requests aimed at the next
>>> level down, and that doesn't quiet work, because once you start acting
>>> on the first entry in that list, all the rest become "this" level.
>>
>> Uhm, well,
>> that's how it has been since you introduced this back in 2007, d89d879.
>> And it worked.
>
> Just because it "worked", doesn't mean it was "right" :-)
>
>>
>>> I think you can address this by always calling ->make_request_fn with an
>>> empty "recursion", then after the call completes, splice the "recursion"
>>> list that resulted (if any) on top of the "remainder" stack.
>>>
>>> This way, the "remainder" stack is always "requests for lower-level
>>> devices before request for upper level devices" and the "recursion"
>>> queue is always "requests for devices below the current level".
>>
>> Yes, I guess that would work as well,
>> but may need "empirical proof" to check for performance regressions.
>>
>>> I also really *don't* like the idea of punting to a separate thread - it
>>> seems to be just delaying the problem.
>>>
>>> Can you try move the bio_list_init(->recursion) call to just before
>>> the ->make_request_fn() call, and adding
>>>     bio_list_merge_head(->remainder, ->recursion)
>>> just after?
>>> (or something like that) and confirm it makes sense, and works?
>>
>> Sure, will do.
>> I'd suggest this would be a patch on its own though, on top of this one.
>> Because it would change the order in which stacked bios are processed
>> wrt the way it used to be since 2007 (my suggestion as is does not).
>
> Yes, because I think the original order is wrong, as you have helped me
> to see.
> Before I introduced the recursion limiting, requests were handled as an
> in-order tree walk.  The code I wrote tried to preserve that but didn't
> for several reasons.  I think we need to restore the original in-order
> walk because it makes the most sense.

> So after processing a particular bio, we should then process all the
> 'child' bios - bios send to underlying devices.  Then the 'sibling'
> bios, that were split off, and then any remaining parents and ancestors.

IMHO, that is just what the oneline patch is doing, isn't it?

| diff --git a/block/blk-core.c b/block/blk-core.c
 | index 2475b1c7..a5623f6 100644
 | --- a/block/blk-core.c
 | +++ b/block/blk-core.c
 | @@ -2048,7 +2048,7 @@ blk_qc_t generic_make_request(struct bio *bio)
 |       * should be added at the tail
 |       */
 |      if (current->bio_list) {
 | -            bio_list_add(current->bio_list, bio);
 | +            bio_list_add_head(current->bio_list, bio);
 |              goto out;
 |      }

Thanks,

>
> You patch created the right structures for doing this, my proposal took
> it a step closer, but now after more careful analysis I don't think it
> is quite right.
> With my previous proposal (and you latest patch - thanks!) requests for
> "this" level are stacked, but they should be queued.
> If a make_request_fn only ever submits one request for this level and
> zero or more lower levels, then the difference between a queue and a
> stack is irrelevant.  If it submited more that one, a stack would cause
> them to be handled in the reverse order.
>
> To make the patch "perfect", and maybe even more elegant we could treat
> ->remainder and ->recursion more alike.
> i.e.:
>   - generic make request has a private "stack" of requests.
>   - before calling ->make_request_fn(), both ->remainder and ->recursion
>     are initialised
>   - after ->make_request_fn(), ->remainder are spliced in to top of
>     'stack', then ->recursion is spliced onto that.
>   - If stack is not empty, the top request is popped and we loop to top.
>
> This reliably follows in-order execution, and handles siblings correctly
> (in submitted order) if/when a request splits off multiple siblings.
>
>>
>> Which may change performance metrics.
>> It may even improve some of them,
>> or maybe it does nothing, but we don't know.
>
> I think that as long a requests are submitted in the order they are
> created at each level there is no reason to expect performance
> regressions.
> All we are doing is changing the ordering between requests generated at
> different levels, and I think we are restoring a more natural order.
>
> Thanks,
> NeilBrown

[toc] | [prev] | [next] | [standalone]

#1439425

On Fri, Jul 08, 2016 at 07:08:32PM +0800, Ming Lei wrote:
> > So after processing a particular bio, we should then process all the
> > 'child' bios - bios send to underlying devices.  Then the 'sibling'
> > bios, that were split off, and then any remaining parents and ancestors.
> 
> IMHO, that is just what the oneline patch is doing, isn't it?
> 
> | diff --git a/block/blk-core.c b/block/blk-core.c
>  | index 2475b1c7..a5623f6 100644
>  | --- a/block/blk-core.c
>  | +++ b/block/blk-core.c
>  | @@ -2048,7 +2048,7 @@ blk_qc_t generic_make_request(struct bio *bio)
>  |       * should be added at the tail
>  |       */
>  |      if (current->bio_list) {
>  | -            bio_list_add(current->bio_list, bio);
>  | +            bio_list_add_head(current->bio_list, bio);
>  |              goto out;
>  |      }

Almost, but not quite.

As explained earlier, this will re-order.
It will still process bios in "deepest level first" order,
but it will process "sibling" bios in reverse submission order.

Think "very large bio" submitted to a stripe set
with small stripe width/stripe unit size.

So I'd expect this to be a performance hit in some scenarios,
unless the stack at some deeper level does back-merging in its elevator.
(If some driver is not able to merge stuff because of "reverse submission
order" this can easily mean saturating IOPS of the physical device with
small requests, throttling bandwidth to a minimum.)

That's why I mentioned it as "potential easy fix for the deadlock",
but did not suggest it as the proper way to fix this.

If however the powers that be decide that this was a non-issue,
we could use it this way.

	Lars

[toc] | [prev] | [next] | [standalone]

#1439434 — Re: block: fix blk_queue_split() resource exhaustion

On Fri, Jul 08 2016 at  8:52am -0400,
Lars Ellenberg <lars.ellenberg@linbit.com> wrote:

> On Fri, Jul 08, 2016 at 07:08:32PM +0800, Ming Lei wrote:
> > > So after processing a particular bio, we should then process all the
> > > 'child' bios - bios send to underlying devices.  Then the 'sibling'
> > > bios, that were split off, and then any remaining parents and ancestors.
> > 
> > IMHO, that is just what the oneline patch is doing, isn't it?
> > 
> > | diff --git a/block/blk-core.c b/block/blk-core.c
> >  | index 2475b1c7..a5623f6 100644
> >  | --- a/block/blk-core.c
> >  | +++ b/block/blk-core.c
> >  | @@ -2048,7 +2048,7 @@ blk_qc_t generic_make_request(struct bio *bio)
> >  |       * should be added at the tail
> >  |       */
> >  |      if (current->bio_list) {
> >  | -            bio_list_add(current->bio_list, bio);
> >  | +            bio_list_add_head(current->bio_list, bio);
> >  |              goto out;
> >  |      }
> 
> Almost, but not quite.
> 
> As explained earlier, this will re-order.
> It will still process bios in "deepest level first" order,
> but it will process "sibling" bios in reverse submission order.
> 
> Think "very large bio" submitted to a stripe set
> with small stripe width/stripe unit size.
> 
> So I'd expect this to be a performance hit in some scenarios,
> unless the stack at some deeper level does back-merging in its elevator.
> (If some driver is not able to merge stuff because of "reverse submission
> order" this can easily mean saturating IOPS of the physical device with
> small requests, throttling bandwidth to a minimum.)
> 
> That's why I mentioned it as "potential easy fix for the deadlock",
> but did not suggest it as the proper way to fix this.
> 
> If however the powers that be decide that this was a non-issue,
> we could use it this way.

No, we cannot do this.  With blk-mq it doesn't have any of the more
elaborate IO scheduling that request_fn request_queues have.  We should
not be knowingly mangling the order of IO with the thought that some
other layer will fix it up.

I think it best for you to rebase your work (against jens' for-4.8/core)
into a single coherent patch and resubmit for 4.8 inclusion.  I really
don't see a huge benefit to keeping neilb's suggestion split out -- but
if you or others do that's fine.

The only concern I have relative to DM is: DM doesn't use
blk_queue_split, so will it need to open-code setting
recursion/remainder in order to ensure forward progress?  neilb seemed
to think the rework in generic_make_request would "just work" for the
dm-snapshot deadlock case though so maybe this isn't a valid
concern... unfortunately we don't have a quick reproducer for that
dm-snapshot issue so it'll take a bit to prove.

Mike

[toc] | [prev] | [next] | [standalone]

#1438585 — Re: block: fix blk_queue_split() resource exhaustion

On Thu, Jul 07 2016 at  1:35am -0400,
NeilBrown <neilb@suse.com> wrote:

> On Wed, Jun 22 2016, Lars Ellenberg wrote:
> 
> > For a long time, generic_make_request() converts recursion into
> > iteration by queuing recursive arguments on current->bio_list.
> >
> > This is convenient for stacking drivers,
> > the top-most driver would take the originally submitted bio,
> > and re-submit a re-mapped version of it, or one or more clones,
> > or one or more new allocated bios to its backend(s). Which
> > are then simply processed in turn, and each can again queue
> > more "backend-bios" until we reach the bottom of the driver stack,
> > and actually dispatch to the real backend device.
> >
> > Any stacking driver ->make_request_fn() could expect that,
> > once it returns, any backend-bios it submitted via recursive calls
> > to generic_make_request() would now be processed and dispatched, before
> > the current task would call into this driver again.
> >
> > This is changed by commit
> >   54efd50 block: make generic_make_request handle arbitrarily sized bios
> >
> > Drivers may call blk_queue_split() inside their ->make_request_fn(),
> > which may split the current bio into a front-part to be dealt with
> > immediately, and a remainder-part, which may need to be split even
> > further. That remainder-part will simply also be pushed to
> > current->bio_list, and would end up being head-of-queue, in front
> > of any backend-bios the current make_request_fn() might submit during
> > processing of the fron-part.
> >
> > Which means the current task would immediately end up back in the same
> > make_request_fn() of the same driver again, before any of its backend
> > bios have even been processed.
> >
> > This can lead to resource starvation deadlock.
> > Drivers could avoid this by learning to not need blk_queue_split(),
> > or by submitting their backend bios in a different context (dedicated
> > kernel thread, work_queue context, ...). Or by playing funny re-ordering
> > games with entries on current->bio_list.
> >
> > Instead, I suggest to distinguish between recursive calls to
> > generic_make_request(), and pushing back the remainder part in
> > blk_queue_split(), by pointing current->bio_lists to a
> > 	struct recursion_to_iteration_bio_lists {
> > 		struct bio_list recursion;
> > 		struct bio_list remainder;
> > 	}
> >
> > To have all bios targeted to drivers lower in the stack processed before
> > processing the next piece of a bio targeted at the higher levels,
> > as long as queued bios resulting from recursion are available,
> > they will continue to be processed in FIFO order.
> > Pushed back bio-parts resulting from blk_queue_split() will be processed
> > in LIFO order, one-by-one, whenever the recursion list becomes empty.
> 
> I really like this change.  It seems to precisely address the problem.
> The "problem" being that requests for "this" device are potentially
> mixed up with requests from underlying devices.
> However I'm not sure it is quite general enough.
> 
> The "remainder" list is a stack of requests aimed at "this" level or
> higher, and I think it will always exactly fit that description.
> The "recursion" list needs to be a queue of requests aimed at the next
> level down, and that doesn't quiet work, because once you start acting
> on the first entry in that list, all the rest become "this" level.
> 
> I think you can address this by always calling ->make_request_fn with an
> empty "recursion", then after the call completes, splice the "recursion"
> list that resulted (if any) on top of the "remainder" stack.
> 
> This way, the "remainder" stack is always "requests for lower-level
> devices before request for upper level devices" and the "recursion"
> queue is always "requests for devices below the current level".
> 
> I also really *don't* like the idea of punting to a separate thread

Hi Neil,

Was this concern about "punting to a separate thread" in reference to
the line of work from Mikulas at the top of this 'wip' branch?
http://git.kernel.org/cgit/linux/kernel/git/snitzer/linux.git/log/?h=wip

> - it seems to be just delaying the problem.

Have you looked at this closely?  Not seeing how you can say that given
that on schedule the bios on current->bio_list are flushed.

The incremental work to delay the offload of queued bios is just meant
to preserve existing bio submission order unless there is reason to
believe a deadlock exists.

I would agree that this timer based approach is rather "gross" to some
degree _but_ it beats deadlocks!  This code needs fixing.  And the fix
cannot be constrained to bio_queue_split() because DM isn't even using
it.

Mike

[toc] | [prev] | [next] | [standalone]

#1438991 — Re: block: fix blk_queue_split() resource exhaustion

[Multipart message — attachments visible in raw view] — view raw

On Thu, Jul 07 2016, Mike Snitzer wrote:

> On Thu, Jul 07 2016 at  1:35am -0400,
> NeilBrown <neilb@suse.com> wrote:
>
>> On Wed, Jun 22 2016, Lars Ellenberg wrote:
>> 
>> > For a long time, generic_make_request() converts recursion into
>> > iteration by queuing recursive arguments on current->bio_list.
>> >
>> > This is convenient for stacking drivers,
>> > the top-most driver would take the originally submitted bio,
>> > and re-submit a re-mapped version of it, or one or more clones,
>> > or one or more new allocated bios to its backend(s). Which
>> > are then simply processed in turn, and each can again queue
>> > more "backend-bios" until we reach the bottom of the driver stack,
>> > and actually dispatch to the real backend device.
>> >
>> > Any stacking driver ->make_request_fn() could expect that,
>> > once it returns, any backend-bios it submitted via recursive calls
>> > to generic_make_request() would now be processed and dispatched, before
>> > the current task would call into this driver again.
>> >
>> > This is changed by commit
>> >   54efd50 block: make generic_make_request handle arbitrarily sized bios
>> >
>> > Drivers may call blk_queue_split() inside their ->make_request_fn(),
>> > which may split the current bio into a front-part to be dealt with
>> > immediately, and a remainder-part, which may need to be split even
>> > further. That remainder-part will simply also be pushed to
>> > current->bio_list, and would end up being head-of-queue, in front
>> > of any backend-bios the current make_request_fn() might submit during
>> > processing of the fron-part.
>> >
>> > Which means the current task would immediately end up back in the same
>> > make_request_fn() of the same driver again, before any of its backend
>> > bios have even been processed.
>> >
>> > This can lead to resource starvation deadlock.
>> > Drivers could avoid this by learning to not need blk_queue_split(),
>> > or by submitting their backend bios in a different context (dedicated
>> > kernel thread, work_queue context, ...). Or by playing funny re-ordering
>> > games with entries on current->bio_list.
>> >
>> > Instead, I suggest to distinguish between recursive calls to
>> > generic_make_request(), and pushing back the remainder part in
>> > blk_queue_split(), by pointing current->bio_lists to a
>> > 	struct recursion_to_iteration_bio_lists {
>> > 		struct bio_list recursion;
>> > 		struct bio_list remainder;
>> > 	}
>> >
>> > To have all bios targeted to drivers lower in the stack processed before
>> > processing the next piece of a bio targeted at the higher levels,
>> > as long as queued bios resulting from recursion are available,
>> > they will continue to be processed in FIFO order.
>> > Pushed back bio-parts resulting from blk_queue_split() will be processed
>> > in LIFO order, one-by-one, whenever the recursion list becomes empty.
>> 
>> I really like this change.  It seems to precisely address the problem.
>> The "problem" being that requests for "this" device are potentially
>> mixed up with requests from underlying devices.
>> However I'm not sure it is quite general enough.
>> 
>> The "remainder" list is a stack of requests aimed at "this" level or
>> higher, and I think it will always exactly fit that description.
>> The "recursion" list needs to be a queue of requests aimed at the next
>> level down, and that doesn't quiet work, because once you start acting
>> on the first entry in that list, all the rest become "this" level.
>> 
>> I think you can address this by always calling ->make_request_fn with an
>> empty "recursion", then after the call completes, splice the "recursion"
>> list that resulted (if any) on top of the "remainder" stack.
>> 
>> This way, the "remainder" stack is always "requests for lower-level
>> devices before request for upper level devices" and the "recursion"
>> queue is always "requests for devices below the current level".
>> 
>> I also really *don't* like the idea of punting to a separate thread
>
> Hi Neil,
>
> Was this concern about "punting to a separate thread" in reference to
> the line of work from Mikulas at the top of this 'wip' branch?
> http://git.kernel.org/cgit/linux/kernel/git/snitzer/linux.git/log/?h=wip

A little bit in response to
  https://patchwork.kernel.org/patch/7398411/
which you linked upthread, but more in response to the per-blocked
workqueue threads we now have. The (Commit df2cb6daa4) really seemed
like a lazy solution.
I may will be that the current proposal makes these threads redundant by
completely handling the first section split of a request before looking
to see if there is any more to split.

For this to work, each split would need to be a binary split.
i.e.
  If request is too big:
    1/ split into A that isn't too big and B
    2/ add B to the "remainder" queue
    3/ generate sub requests for A and submit them to "recursion" queue

Then 'A' would be completely submitted before B was started, so it would
be safe for B to wait for any resources (like something from a mempool)
that A might be using.

>
>> - it seems to be just delaying the problem.
>
> Have you looked at this closely?  Not seeing how you can say that given
> that on schedule the bios on current->bio_list are flushed.

I fully accept that it is similar to a current solution.  I just don't
like either.

In the sequence of steps given in
https://patchwork.kernel.org/patch/7398411/

step 6 would now not happen until after the bio mentioned in step 4 has
been completely submitted, and so after step5 has had a chance to
release the lock.

>
> The incremental work to delay the offload of queued bios is just meant
> to preserve existing bio submission order unless there is reason to
> believe a deadlock exists.
>
> I would agree that this timer based approach is rather "gross" to some
> degree _but_ it beats deadlocks!  This code needs fixing.  And the fix
> cannot be constrained to bio_queue_split() because DM isn't even using
> it.

Yes, the 1-second timer isn't the most elegant thing ever.  Certainly
better than a deadlock.  But I think we can do better.

Certainly DM needs fixing, as well as md (and maybe others).  The fix
should be fairly easy though.
For md/raid0, the loop in raid0_make_request would be discarded
and the
	} while (split != bio);
at the end would be replaced by
       if (split != bio)
              generic_queue_request(bio);

though probably with a better function name.
generic_queue_request() would add the bio to the ->remainder list.

Presumably DM could do something similar, but I'm not familiar enough
with the code to say precisely what.

Thanks,
NeilBrown

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web