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

[Ming Lei]

On Wed, Jul 6, 2016 at 8:38 PM, Lars Ellenberg
<lars.ellenberg@xxxxxxxxxx> wrote:
> On Mon, Jul 04, 2016 at 06:47:29PM +0800, Ming Lei wrote:
>> >> One clean solution may be to convert the loop of generic_make_request()
>> >> into the following way:
>> >>
>> >> do {
>> >>     struct bio *splitted, *remainder = NULL;
>> >>     struct request_queue *q = bdev_get_queue(bio->bi_bdev);
>> >>
>> >>     blk_queue_split(q, &bio, &remainder, q->bio_split);
>> >>
>> >>     ret = q->make_request_fn(q, bio);
>> >>
>> >>     if (remainder)
>> >>          bio_list_add(current->bio_list, remainder);
>> >>     bio = bio_list_pop(current->bio_list);
>> >> } while (bio)
>> >
>> > Not good enough.
>
>
>> > Goal was to first process all "deeper level" bios
>> > before processing the remainder.
>>
>> For the reported bio splitting issue, I think the goal is to make sure all
>> BIOs generated from 'bio' inside .make_request_fn(bio) are queued
>> before the 'current' remainder. Cause it is the issue introduced by
>> blk_split_bio().

I believe the above description is correct, but my previous solution
is wrong, looks what we need is a binary tree, in which left child is
the splitted bio and the remainder bio is the right child, and the tree
need to be traversed in pre-order to make sure all BIOs generated
from 'bio' inside .make_request_fn(bio) are queued before the
remainder of bio splitting.

Another property of the tree is that if one node has only one child,
the child has to be left one.

I will think about it further to see if it is doable to implement.

>
> Stacking:
>         qA (limitting layer)
>         -> qB (remapping)
>         -> qC (remapping)
>         -> qD (hardware)
>
> [in fact you don't even need four layers,
>  this is just to clarify that the stack may be more complex than you
>  assume it would be]
>
> Columns below:
> 1) argument to generic_make_request() and its target queue.
> 2) current->bio_list
> 3) "in-flight" counter of qA.
>
> ==== In your new picture, iiuc:
>
> generic_make_request(bio_orig)
>                 NULL                    in-flight=0
> bio_orig        empty
>   blk_queue_split()
>   result:
>   bio_s, bio_r
> qA->make_request_fn(bio_s)
>                                         in-flight=1
>   bio_c = bio_clone(bio_s)
>   generic_make_request(bio_c to qB)
>                 bio_c
> <-return
>   bio_list_add(bio_r)
>                 bio_c, bio_r
>   bio_list_pop()
>                 bio_r
> qB->make_request_fn(bio_c)
>   (Assume it does not clone, but only remap.
>   But it may also be a striping layer,
>   and queue more than one bio here.)
>   generic_make_request(bio_c to qC)
>                 bio_r, bio_c
> <-return
>   bio_list_pop()
>                 bio_c
> qA->make_request_fn(bio_r)              in-flight still 1
>
>         BLOCKS, because bio_c has not been processed to its final
>         destination qD yet, and not dispatched to hardware.

Yes, you are right.

>
>
> ==== my suggestion
>
> generic_make_request(bio_orig)
>                 NULL                    in-flight=0
> bio_orig        empty                   in-flight=0
> qA->make_request_fn(bio_orig)
>   blk_queue_split()
>   result:
>   bio_s, and bio_r stuffed away to head of remainder list.
>                                         in-flight=1
>   bio_c = bio_clone(bio_s)
>   generic_make_request(bio_c to qB)
>                 bio_c
> <-return
>                 bio_c
>   bio_list_pop()
>                 empty
> qB->make_request_fn(bio_c)
>   (Assume it does not clone, but only remap.
>   But it may also be a striping layer,
>   and queue more than one bio here.)
>   generic_make_request(bio_c to qC)
>                 bio_c
> <-return
>   bio_list_pop()
>                 empty
> qC->make_request_fn(bio_c)
>   generic_make_request(bio_c to qD)
>                 bio_c
> <-return
>   bio_list_pop()
>                 empty
> qD->make_request_fn(bio_c)
>         dispatches to hardware
> <-return
>                 empty
>    bio_list_pop()
>    NULL, great, lets pop from remainder list
> qA->make_request_fn(bio_r)              in-flight=?
>
>         May block, but only until completion of bio_c.
>         Which may already have happened.
>
>         *makes progress*

I admit your solution is smart, but it isn't easy to prove it as correct
in theory.  But if the traversal can be mapped into pre-order traversal
of the above binary tree, it may be correct.

Thanks,
Ming

>
> Thanks,
>
>     Lars
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-block" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at  http://vger.kernel.org/majordomo-info.html