[PATCH 0/3] blk-mq: optimise plugging

[PATCH 0/3] blk-mq: optimise plugging

[Pavel Begunkov]

Clean and optimise blk_mq_flush_plug_list().

Pavel Begunkov (3):
  blk-mq: optimise rq sort function
  list: introduce list_for_each_continue()
  blk-mq: optimise blk_mq_flush_plug_list()

 block/blk-mq.c       | 69 +++++++++++++++-----------------------------
 include/linux/list.h | 10 +++++++
 2 files changed, 33 insertions(+), 46 deletions(-)

-- 
2.24.0

[PATCH 1/3] blk-mq: optimise rq sort function

[Pavel Begunkov]

Check "!=" in multi-layer comparisons. The same memory usage, fewer
instructions, and 2 from 4 jumps are replaced with SETcc.

Note, that list_sort() doesn't differ 0 and <0.

Signed-off-by: Pavel Begunkov <asml.silence@gmail.com>
---
 block/blk-mq.c | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)

diff --git a/block/blk-mq.c b/block/blk-mq.c
index 323c9cb28066..f32a3cfdd34e 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -1668,14 +1668,10 @@ static int plug_rq_cmp(void *priv, struct list_head *a, struct list_head *b)
 	struct request *rqa = container_of(a, struct request, queuelist);
 	struct request *rqb = container_of(b, struct request, queuelist);
 
-	if (rqa->mq_ctx < rqb->mq_ctx)
-		return -1;
-	else if (rqa->mq_ctx > rqb->mq_ctx)
-		return 1;
-	else if (rqa->mq_hctx < rqb->mq_hctx)
-		return -1;
-	else if (rqa->mq_hctx > rqb->mq_hctx)
-		return 1;
+	if (rqa->mq_ctx != rqb->mq_ctx)
+		return rqa->mq_ctx > rqb->mq_ctx;
+	if (rqa->mq_hctx != rqb->mq_hctx)
+		return rqa->mq_hctx > rqb->mq_hctx;
 
 	return blk_rq_pos(rqa) > blk_rq_pos(rqb);
 }
-- 
2.24.0

Re: [PATCH 1/3] blk-mq: optimise rq sort function

[Nikolay Borisov]

On 28.11.19 г. 23:11 ч., Pavel Begunkov wrote:
> Check "!=" in multi-layer comparisons. The same memory usage, fewer
> instructions, and 2 from 4 jumps are replaced with SETcc.
> 
> Note, that list_sort() doesn't differ 0 and <0.
> 
> Signed-off-by: Pavel Begunkov <asml.silence@gmail.com>

My first reaction was this is wrong since you no longer return negative
values. But then I looked into list_sort/merge and this branch
'if (cmp(priv, a, b) <= 0) {' clearly shows this is correct.

So :

Reviewed-by: Nikolay Borisov <nborisov@suse.com>

> ---
>  block/blk-mq.c | 12 ++++--------
>  1 file changed, 4 insertions(+), 8 deletions(-)
> 
> diff --git a/block/blk-mq.c b/block/blk-mq.c
> index 323c9cb28066..f32a3cfdd34e 100644
> --- a/block/blk-mq.c
> +++ b/block/blk-mq.c
> @@ -1668,14 +1668,10 @@ static int plug_rq_cmp(void *priv, struct list_head *a, struct list_head *b)
>  	struct request *rqa = container_of(a, struct request, queuelist);
>  	struct request *rqb = container_of(b, struct request, queuelist);
>  
> -	if (rqa->mq_ctx < rqb->mq_ctx)
> -		return -1;
> -	else if (rqa->mq_ctx > rqb->mq_ctx)
> -		return 1;
> -	else if (rqa->mq_hctx < rqb->mq_hctx)
> -		return -1;
> -	else if (rqa->mq_hctx > rqb->mq_hctx)
> -		return 1;
> +	if (rqa->mq_ctx != rqb->mq_ctx)
> +		return rqa->mq_ctx > rqb->mq_ctx;
> +	if (rqa->mq_hctx != rqb->mq_hctx)
> +		return rqa->mq_hctx > rqb->mq_hctx;
>  
>  	return blk_rq_pos(rqa) > blk_rq_pos(rqb);
>  }
> 

Re: [PATCH 1/3] blk-mq: optimise rq sort function

[Pavel Begunkov]

On 11/29/2019 11:28 AM, Nikolay Borisov wrote:
> On 28.11.19 г. 23:11 ч., Pavel Begunkov wrote:
>> Check "!=" in multi-layer comparisons. The same memory usage, fewer
>> instructions, and 2 from 4 jumps are replaced with SETcc.
>>
>> Note, that list_sort() doesn't differ 0 and <0.
>>
>> Signed-off-by: Pavel Begunkov <asml.silence@gmail.com>
> 
> My first reaction was this is wrong since you no longer return negative
> values. But then I looked into list_sort/merge and this branch
> 'if (cmp(priv, a, b) <= 0) {' clearly shows this is correct.

Yes, that's why there is a note in the patch description. The same is
told by list_sort() description.

> 
> So :
> 
> Reviewed-by: Nikolay Borisov <nborisov@suse.com>

Thanks for taking a look

> 
>> ---
>>  block/blk-mq.c | 12 ++++--------
>>  1 file changed, 4 insertions(+), 8 deletions(-)
>>
>> diff --git a/block/blk-mq.c b/block/blk-mq.c
>> index 323c9cb28066..f32a3cfdd34e 100644
>> --- a/block/blk-mq.c
>> +++ b/block/blk-mq.c
>> @@ -1668,14 +1668,10 @@ static int plug_rq_cmp(void *priv, struct list_head *a, struct list_head *b)
>>  	struct request *rqa = container_of(a, struct request, queuelist);
>>  	struct request *rqb = container_of(b, struct request, queuelist);
>>  
>> -	if (rqa->mq_ctx < rqb->mq_ctx)
>> -		return -1;
>> -	else if (rqa->mq_ctx > rqb->mq_ctx)
>> -		return 1;
>> -	else if (rqa->mq_hctx < rqb->mq_hctx)
>> -		return -1;
>> -	else if (rqa->mq_hctx > rqb->mq_hctx)
>> -		return 1;
>> +	if (rqa->mq_ctx != rqb->mq_ctx)
>> +		return rqa->mq_ctx > rqb->mq_ctx;
>> +	if (rqa->mq_hctx != rqb->mq_hctx)
>> +		return rqa->mq_hctx > rqb->mq_hctx;
>>  
>>  	return blk_rq_pos(rqa) > blk_rq_pos(rqb);
>>  }
>>

-- 
Pavel Begunkov

Re: [PATCH 1/3] blk-mq: optimise rq sort function

[Nikolay Borisov]

On 29.11.19 г. 11:45 ч., Pavel Begunkov wrote:
> On 11/29/2019 11:28 AM, Nikolay Borisov wrote:
>> On 28.11.19 г. 23:11 ч., Pavel Begunkov wrote:
>>> Check "!=" in multi-layer comparisons. The same memory usage, fewer
>>> instructions, and 2 from 4 jumps are replaced with SETcc.
>>>
>>> Note, that list_sort() doesn't differ 0 and <0.
>>>
>>> Signed-off-by: Pavel Begunkov <asml.silence@gmail.com>
>>
>> My first reaction was this is wrong since you no longer return negative
>> values. But then I looked into list_sort/merge and this branch
>> 'if (cmp(priv, a, b) <= 0) {' clearly shows this is correct.
> 
> Yes, that's why there is a note in the patch description. The same is
> told by list_sort() description.

And of course I have missed your remark in the changelog :)

> 
>>
>> So :
>>
>> Reviewed-by: Nikolay Borisov <nborisov@suse.com>
> 
> Thanks for taking a look
> 
>>
>>> ---
>>>  block/blk-mq.c | 12 ++++--------
>>>  1 file changed, 4 insertions(+), 8 deletions(-)
>>>
>>> diff --git a/block/blk-mq.c b/block/blk-mq.c
>>> index 323c9cb28066..f32a3cfdd34e 100644
>>> --- a/block/blk-mq.c
>>> +++ b/block/blk-mq.c
>>> @@ -1668,14 +1668,10 @@ static int plug_rq_cmp(void *priv, struct list_head *a, struct list_head *b)
>>>  	struct request *rqa = container_of(a, struct request, queuelist);
>>>  	struct request *rqb = container_of(b, struct request, queuelist);
>>>  
>>> -	if (rqa->mq_ctx < rqb->mq_ctx)
>>> -		return -1;
>>> -	else if (rqa->mq_ctx > rqb->mq_ctx)
>>> -		return 1;
>>> -	else if (rqa->mq_hctx < rqb->mq_hctx)
>>> -		return -1;
>>> -	else if (rqa->mq_hctx > rqb->mq_hctx)
>>> -		return 1;
>>> +	if (rqa->mq_ctx != rqb->mq_ctx)
>>> +		return rqa->mq_ctx > rqb->mq_ctx;
>>> +	if (rqa->mq_hctx != rqb->mq_hctx)
>>> +		return rqa->mq_hctx > rqb->mq_hctx;
>>>  
>>>  	return blk_rq_pos(rqa) > blk_rq_pos(rqb);
>>>  }
>>>
> 

[PATCH 2/3] list: introduce list_for_each_continue()

[Pavel Begunkov]

As other *continue() helpers, this continues iteration from a given
position.

Signed-off-by: Pavel Begunkov <asml.silence@gmail.com>
---
 include/linux/list.h | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/include/linux/list.h b/include/linux/list.h
index 85c92555e31f..3c391bbd03c3 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -538,6 +538,16 @@ static inline void list_splice_tail_init(struct list_head *list,
 #define list_for_each(pos, head) \
 	for (pos = (head)->next; pos != (head); pos = pos->next)
 
+/**
+ * list_for_each_continue - continue iteration over a list
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @head:	the head for your list.
+ *
+ * Continue to iterate over a list, continuing after the current position.
+ */
+#define list_for_each_continue(pos, head) \
+	for (pos = pos->next; pos != (head); pos = pos->next)
+
 /**
  * list_for_each_prev	-	iterate over a list backwards
  * @pos:	the &struct list_head to use as a loop cursor.
-- 
2.24.0

[PATCH 3/3] blk-mq: optimise blk_mq_flush_plug_list()

[Pavel Begunkov]

Instead of using list_del_init() in a loop, that generates a lot of
unnecessary memory read/writes, iterate from the first request of a
batch and cut out a sublist with list_cut_before().

Apart from removing the list node initialisation part, this is more
register-friendly, and the assembly uses the stack less intensively.

list_empty() at the beginning is done with hope, that the compiler can
optimise out the same check in the following list_splice_init().

Signed-off-by: Pavel Begunkov <asml.silence@gmail.com>
---
 block/blk-mq.c | 57 +++++++++++++++++---------------------------------
 1 file changed, 19 insertions(+), 38 deletions(-)

diff --git a/block/blk-mq.c b/block/blk-mq.c
index f32a3cfdd34e..3c71d52b6401 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -1678,14 +1678,10 @@ static int plug_rq_cmp(void *priv, struct list_head *a, struct list_head *b)
 
 void blk_mq_flush_plug_list(struct blk_plug *plug, bool from_schedule)
 {
-	struct blk_mq_hw_ctx *this_hctx;
-	struct blk_mq_ctx *this_ctx;
-	struct request_queue *this_q;
-	struct request *rq;
 	LIST_HEAD(list);
-	LIST_HEAD(rq_list);
-	unsigned int depth;
 
+	if (list_empty(&plug->mq_list))
+		return;
 	list_splice_init(&plug->mq_list, &list);
 
 	if (plug->rq_count > 2 && plug->multiple_queues)
@@ -1693,42 +1689,27 @@ void blk_mq_flush_plug_list(struct blk_plug *plug, bool from_schedule)
 
 	plug->rq_count = 0;
 
-	this_q = NULL;
-	this_hctx = NULL;
-	this_ctx = NULL;
-	depth = 0;
-
-	while (!list_empty(&list)) {
-		rq = list_entry_rq(list.next);
-		list_del_init(&rq->queuelist);
-		BUG_ON(!rq->q);
-		if (rq->mq_hctx != this_hctx || rq->mq_ctx != this_ctx) {
-			if (this_hctx) {
-				trace_block_unplug(this_q, depth, !from_schedule);
-				blk_mq_sched_insert_requests(this_hctx, this_ctx,
-								&rq_list,
-								from_schedule);
-			}
-
-			this_q = rq->q;
-			this_ctx = rq->mq_ctx;
-			this_hctx = rq->mq_hctx;
-			depth = 0;
+	do {
+		struct list_head rq_list;
+		struct request *rq, *head_rq = list_entry_rq(list.next);
+		struct list_head *pos = &head_rq->queuelist; /* skip first */
+		struct blk_mq_hw_ctx *this_hctx = head_rq->mq_hctx;
+		struct blk_mq_ctx *this_ctx = head_rq->mq_ctx;
+		unsigned int depth = 1;
+
+		list_for_each_continue(pos, &list) {
+			rq = list_entry_rq(pos);
+			BUG_ON(!rq->q);
+			if (rq->mq_hctx != this_hctx || rq->mq_ctx != this_ctx)
+				break;
+			depth++;
 		}
 
-		depth++;
-		list_add_tail(&rq->queuelist, &rq_list);
-	}
-
-	/*
-	 * If 'this_hctx' is set, we know we have entries to complete
-	 * on 'rq_list'. Do those.
-	 */
-	if (this_hctx) {
-		trace_block_unplug(this_q, depth, !from_schedule);
+		list_cut_before(&rq_list, &list, pos);
+		trace_block_unplug(head_rq->q, depth, !from_schedule);
 		blk_mq_sched_insert_requests(this_hctx, this_ctx, &rq_list,
 						from_schedule);
-	}
+	} while(!list_empty(&list));
 }
 
 static void blk_mq_bio_to_request(struct request *rq, struct bio *bio,
-- 
2.24.0

Re: [PATCH 0/3] blk-mq: optimise plugging

[Pavel Begunkov]

[-- Attachment #1.1: Type: text/plain, Size: 460 bytes --]

On 29/11/2019 00:11, Pavel Begunkov wrote:
> Clean and optimise blk_mq_flush_plug_list().
> 
ping

> Pavel Begunkov (3):
>   blk-mq: optimise rq sort function
>   list: introduce list_for_each_continue()
>   blk-mq: optimise blk_mq_flush_plug_list()
> 
>  block/blk-mq.c       | 69 +++++++++++++++-----------------------------
>  include/linux/list.h | 10 +++++++
>  2 files changed, 33 insertions(+), 46 deletions(-)
> 

-- 
Pavel Begunkov


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH 0/3] blk-mq: optimise plugging

[Jens Axboe]

On 12/5/19 6:19 AM, Pavel Begunkov wrote:
> On 29/11/2019 00:11, Pavel Begunkov wrote:
>> Clean and optimise blk_mq_flush_plug_list().
>>
> ping

Looks good to me, I've been waiting a bit on this as I'll queue it up
for 5.6.

-- 
Jens Axboe