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(-)
diff --git a/block/blk-core.c b/block/blk-core.c
index 4b4dbdf..e7759f8 100644
--- a/block/blk-core.c
+++ b/block/blk-core.c
@@ -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;
--
1.7.9.5
????{.n?+???????+%?????ݶ??w??{.n?+????{??G?????{ay? ʇڙ?,j??f???h?????????z_??(?階?ݢj"???m??????G????????????&???~???iO???z??v?^?m???? ????????I?
2012/8/8 Jianpeng Ma <[email protected]>:
> 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.
> 2:Only two device can trace plug.
I didn't get the point, can you have more details?
> 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.
On 2012-08-08 11:06 Shaohua Li <[email protected]> Wrote:
>2012/8/8 Jianpeng Ma <[email protected]>:
>> 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
>
>> 2:Only two device can trace plug.
>I didn't get the point, can you have more details?
>>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.
>
>> 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???h?????????z_??(?階?ݢj"???m??????G????????????&???~???iO???z??v?^?m???? ????????I?
2012/8/8 Jianpeng Ma <[email protected]>:
> On 2012-08-08 11:06 Shaohua Li <[email protected]> Wrote:
>>2012/8/8 Jianpeng Ma <[email protected]>:
>>> 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
>>
>>> 2:Only two device can trace plug.
>>I didn't get the point, can you have more details?
>
>>>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.
ok, this is true. please send a new patch for the item 1&2 then.