linux-kernel - Re: block CFQ: avoid moving request to different queue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20121107010527.GA1501@kernel.org>
Date:	Wed, 7 Nov 2012 09:05:27 +0800
From:	Shaohua Li <shli@...nel.org>
To:	Jens Axboe <axboe@...nel.dk>
Cc:	linux-kernel@...r.kernel.org
Subject: Re: block CFQ: avoid moving request to different queue

On Tue, Nov 06, 2012 at 12:39:13PM +0100, Jens Axboe wrote:
> On 2012-11-06 12:34, Shaohua Li wrote:
> > request is queued in cfqq->fifo list. Looks it's possible we are
> > moving a request from one cfqq to another in request merge case. In
> > such case, adjusting the fifo list order doesn't make sense and is
> > impossible if we don't iterate the whole fifo list.
> > 
> > My test does hit one case the two cfqq are different, but didn't cause
> > kernel crash, maybe it's because fifo list isn't used frequently.
> > Anyway, from the code logic, this is buggy.
> 
> Good find!! Usually we never merge between cfqq's as our lookup basis is
> the cfqq. And yes, the fifo generally isn't used a lot, it's only a
> fallback measure to prevent inter-cfqq unfairness.
> 
> Applied to for-3.8/core.
> 
> And lets re-enable the recursive merging, please do send a patch for
> that too.
Here it is.


Subject: block: recursive merge requests

In a 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.

If we do recursive merge for such interleave access, some workloads throughput
get improvement. A recent worload I'm checking on is swap, below change
boostes the throughput around 5% ~ 10%.

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

Index: linux/block/elevator.c
===================================================================
--- linux.orig/block/elevator.c	2012-10-15 10:01:52.763544641 +0800
+++ linux/block/elevator.c	2012-11-06 15:16:57.987363075 +0800
@@ -458,6 +458,7 @@ static bool elv_attempt_insert_merge(str
 				     struct request *rq)
 {
 	struct request *__rq;
+	bool ret;
 
 	if (blk_queue_nomerges(q))
 		return false;
@@ -471,14 +472,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)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/