[patch 2/2]block: recursive merge requests

[Shaohua Li <shaohua.li@intel.com>]

In my workload, thread 1 accesses a, a+2, ..., thread 2 accesses a+1,
a+3,.... When the requests are flushed to queue, a and a+1 are merged
to (a, a+1), a+2 and a+3 too to (a+2, a+3), but (a, a+1) and (a+2, a+3)
aren't merged.
With recursive merge below, the workload throughput gets improved 20%
and context switch drops 60%.

Signed-off-by: Shaohua Li <shaohua.li@intel.com>
---
 block/elevator.c |   16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

Index: linux/block/elevator.c
===================================================================
--- linux.orig/block/elevator.c	2011-12-16 09:08:50.000000000 +0800
+++ linux/block/elevator.c	2011-12-16 09:08:58.000000000 +0800
@@ -521,6 +521,7 @@ static bool elv_attempt_insert_merge(str
 				     struct request *rq)
 {
 	struct request *__rq;
+	bool ret;
 
 	if (blk_queue_nomerges(q))
 		return false;
@@ -534,14 +535,21 @@ static bool elv_attempt_insert_merge(str
 	if (blk_queue_noxmerges(q))
 		return false;
 
+	ret = false;
 	/*
 	 * See if our hash lookup can find a potential backmerge.
 	 */
-	__rq = elv_rqhash_find(q, blk_rq_pos(rq));
-	if (__rq && blk_attempt_req_merge(q, __rq, rq))
-		return true;
+	while (1) {
+		__rq = elv_rqhash_find(q, blk_rq_pos(rq));
+		if (!__rq || !blk_attempt_req_merge(q, __rq, rq))
+			break;
+
+		/* The merged request could be merged with others, try again */
+		ret = true;
+		rq = __rq;
+	}
 
-	return false;
+	return ret;
 }
 
 void elv_merged_request(struct request_queue *q, struct request *rq, int type)