block:Fix some problems about handling plug in blk_queue_bio().

RFC PATCH In review Jianpeng Ma 2 participants 4 messages Aug 8, 2012 – Aug 9, 2012 Block layer

Share & tools

Jianpeng Ma

author

2012-08-08 02:05 UTC #0 lore raw

RFC PATCH 1/1 block:Fix some problems about handling plug in blk_queue_bio().

I think there are three problems about handling plug in blk_queue_bio():
1:if request_count >= BLK_MAX_REQUEST_COUNT, avoid unnecessary plug->should_sort judge. 2:Only two device can trace plug.
3:When exec blk_flush_plug_list,it use list_sort which has
O(nlog(n)) complexity. When insert and sort, it only O(n) complexity.

Signed-off-by Jianpeng Ma <[email protected]>

---
 block/blk-core.c |   32 +++++++++++++++-----------------
 1 file changed, 15 insertions(+), 17 deletions(-)

block/blk-core.c +15 ~~-17~~

index 4b4dbdf..e7759f8 100644
@@ -1514,20 +1514,31 @@ get_rq:
 		if (list_empty(&plug->list))
 			trace_block_plug(q);
 		else {
-			if (!plug->should_sort) {
+			if (request_count >= BLK_MAX_REQUEST_COUNT) {
+				blk_flush_plug_list(plug, false);
+				trace_block_plug(q);
+			} else	if (!plug->should_sort) {
 				struct request *__rq;
 
 				__rq = list_entry_rq(plug->list.prev);
 				if (__rq->q != q)
 					plug->should_sort = 1;
-			}
-			if (request_count >= BLK_MAX_REQUEST_COUNT) {
-				blk_flush_plug_list(plug, false);
+			} else  {
+				struct request *rq;
+
+				list_for_each_entry_reverse(rq, &plug->list, queuelist) {
+					if (rq->q == q) {
+						list_add(&req->queuelist, &rq->queuelist);
+						goto stat_acct;
+					}
+				}
 				trace_block_plug(q);
 			}
 		}
 		list_add_tail(&req->queuelist, &plug->list);
+stat_acct:
 		drive_stat_acct(req, 1);
+
 	} else {
 		spin_lock_irq(q->queue_lock);
 		add_acct_request(q, req, where);

@@ -2866,14 +2877,6 @@ void blk_start_plug(struct blk_plug *plug)
 }
 EXPORT_SYMBOL(blk_start_plug);
 
-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);
-
-	return !(rqa->q <= rqb->q);
-}
-
 /*
  * If 'from_schedule' is true, then postpone the dispatch of requests
  * until a safe kblockd context. We due this to avoid accidental big

@@ -2967,11 +2970,6 @@ void blk_flush_plug_list(struct blk_plug *plug, bool from_schedule)
 
 	list_splice_init(&plug->list, &list);
 
-	if (plug->should_sort) {
-		list_sort(NULL, &list, plug_rq_cmp);
-		plug->should_sort = 0;
-	}
-
 	q = NULL;
 	depth = 0;

Signature · 2 lines

1.7.9.5
�翳簕.n�+壏煯壄�+%娝�遍荻w�簕.n�+壏{炳G珴�妠ay�蕠跈�,jf＂穐殢飦�戧鐉_璁(殠娸"濟�m���G珴�⒏?櫒璀�&ｘ忈秈O曟瑉窔v豝�m����鹅�⒏?朓�

Shaohua Li

2012-08-08 03:06 UTC #1 lore raw

2012/8/8 Jianpeng Ma <[email protected]>:

Quoted 2 lines

I think there are three problems about handling plug in blk_queue_bio():
1:if request_count >= BLK_MAX_REQUEST_COUNT, avoid unnecessary plug->should_sort judge.

this makes sense, though not a big deal, nice to fix it.

Quoted 1 line

2:Only two device can trace plug.

I didn't get the point, can you have more details?

Quoted 2 lines

3:When exec blk_flush_plug_list,it use list_sort which has O(nlog(n)) complexity. When insert and sort, it only O(n) complexity.

but now you do the list iterator for every request, so it's O(n*n)? The plug list is unlikely too long, so I didn't worry about the time spending on list sort.

Jianpeng Ma

author

2012-08-08 05:35 UTC #2 lore raw

On 2012-08-08 11:06 Shaohua Li <[email protected]> Wrote:

Quoted 4 lines

2012/8/8 Jianpeng Ma <[email protected]>:
Quoted 2 lines
I think there are three problems about handling plug in blk_queue_bio():
1:if request_count >= BLK_MAX_REQUEST_COUNT, avoid unnecessary plug->should_sort judge.
this makes sense, though not a big deal, nice to fix it.

Thanks

Quoted 24 lines

Quoted 2 lines

2:Only two device can trace plug.

I didn't get the point, can you have more details?

Quoted 20 lines

if (plug) {
		/*
		 * If this is the first request added after a plug, fire
		 * of a plug trace. If others have been added before, check
		 * if we have multiple devices in this plug. If so, make a
		 * note to sort the list before dispatch.
		 */
		if (list_empty(&plug->list))
			trace_block_plug(q);
		else {
			if (!plug->should_sort) {
				struct request *__rq;

				__rq = list_entry_rq(plug->list.prev);
				if (__rq->q != q)
					plug->should_sort = 1;
			}
			if (request_count >= BLK_MAX_REQUEST_COUNT) {
				blk_flush_plug_list(plug, false);
				trace_block_plug(q);

The code only trace two point;
A: list_empty(&plug->list)
B: request_count >= BLK_MAX_REQUEST_COUNT). it's the same like A which plug->list is empty.
Suppose:
1;reqA-deviceA firstly come, it will call trace_block_plug because the list_empty(plug->list) is true. 2:reqB-deviceB comed, attempt_plug_merge will failed because not deviceB-request-queue.But it'll not to call trace_block_plug.

But call blk_flush_plug_list,it will trace_block_unplug all request_queue.

Quoted 6 lines

Quoted 3 lines
3:When exec blk_flush_plug_list,it use list_sort which has O(nlog(n)) complexity. When insert and sort, it only O(n) complexity.
but now you do the list iterator for every request, so it's O(n*n)? The plug list is unlikely too long, so I didn't worry about the time spending on list sort.

Sorry, it's my fault.�翳簕.n�+壏煯壄�+%娝�遍荻w�簕.n�+壏{炳G珴�妠ay�蕠跈�,jf＂穐殢飦�戧鐉_璁(殠娸"濟�m��G珴�⒏?櫒璀�&ｘ忈秈O曟瑉窔v豝�m��鹅�⒏?朓�

Shaohua Li

2012-08-09 08:50 UTC #3 lore raw

2012/8/8 Jianpeng Ma <[email protected]>:

Quoted 30 lines

On 2012-08-08 11:06 Shaohua Li <[email protected]> Wrote:
Quoted 4 lines
2012/8/8 Jianpeng Ma <[email protected]>:
Quoted 2 lines
I think there are three problems about handling plug in blk_queue_bio():
1:if request_count >= BLK_MAX_REQUEST_COUNT, avoid unnecessary plug->should_sort judge.
this makes sense, though not a big deal, nice to fix it.
Thanks
Quoted 24 lines
Quoted 2 lines
2:Only two device can trace plug.
I didn't get the point, can you have more details?
Quoted 20 lines
if (plug) {
             /*
              * If this is the first request added after a plug, fire
              * of a plug trace. If others have been added before, check
              * if we have multiple devices in this plug. If so, make a
              * note to sort the list before dispatch.
              */
             if (list_empty(&plug->list))
                     trace_block_plug(q);
             else {
                     if (!plug->should_sort) {
                             struct request *__rq;

                             __rq = list_entry_rq(plug->list.prev);
                             if (__rq->q != q)
                                     plug->should_sort = 1;
                     }
                     if (request_count >= BLK_MAX_REQUEST_COUNT) {
                             blk_flush_plug_list(plug, false);
                             trace_block_plug(q);

Quoted 8 lines

The code only trace two point;
A:      list_empty(&plug->list)
B:      request_count >= BLK_MAX_REQUEST_COUNT). it's the same like A which plug->list is empty.
Suppose:
1;reqA-deviceA firstly come, it will call trace_block_plug because the list_empty(plug->list) is true. 2:reqB-deviceB comed, attempt_plug_merge will failed because not deviceB-request-queue.But it'll not to call trace_block_plug.
But call blk_flush_plug_list,it will trace_block_unplug all request_queue.

ok, this is true. please send a new patch for the item 1&2 then.