[PATCH] Linus elevator

[PATCH] Linus elevator

[Mark Hemment]

Hi,

  Looking at the second loop in elevator_linus_merge(), it is possible for
requests to have their elevator_sequence go negative.  This can cause a
v long latency before the request is finally serviced.

  Say, for example, a request (in the queue) is jumped in the first loop
in elevator_linus_merge() as "cmd != rw", even though its 
elevator_sequence is zero.  If it is found that the new request will
merge, the walking back over requests which were jumped makes no test for
an already zeroed elevator_sequence.  Hence it zero values can occur.

  With high default values for read/wite_latency, this hardly ever occurs.

  A simple fix for this is to test for zero before decrementing (patch
below) in the second loop.
  Alternatively, should testing in the first loop be modified?

Mark


diff -u --recursive --new-file -X dontdiff linux-2.4.0-test12/drivers/block/elevator.c markhe-2.4.0-test12/drivers/block/elevator.c
--- linux-2.4.0-test12/drivers/block/elevator.c	Tue Dec  5 23:05:26 2000
+++ markhe-2.4.0-test12/drivers/block/elevator.c	Mon Dec 18 17:50:19 2000
@@ -90,6 +90,9 @@
 	if (ret != ELEVATOR_NO_MERGE && *req) {
 		while ((entry = entry->next) != &q->queue_head) {
 			struct request *tmp = blkdev_entry_to_request(entry);
+
+			if (!tmp->elevator_sequence)
+				continue;
 			tmp->elevator_sequence--;
 		}
 	}

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] Linus elevator

[Jens Axboe]

On Mon, Dec 18 2000, Mark Hemment wrote:
> Hi,
> 
>   Looking at the second loop in elevator_linus_merge(), it is possible for
> requests to have their elevator_sequence go negative.  This can cause a
> v long latency before the request is finally serviced.
> 
>   Say, for example, a request (in the queue) is jumped in the first loop
> in elevator_linus_merge() as "cmd != rw", even though its 
> elevator_sequence is zero.  If it is found that the new request will
> merge, the walking back over requests which were jumped makes no test for
> an already zeroed elevator_sequence.  Hence it zero values can occur.
> 
>   With high default values for read/wite_latency, this hardly ever occurs.
> 
>   A simple fix for this is to test for zero before decrementing (patch
> below) in the second loop.

The merge part was original deliberate, as not to account successful
merges as much as a new request added (and thus an implied seek). But
you did uncover a problem, btw this is also fixed in the blk-12 patch
that also does better accounting to avoid indefinite starvation.

>   Alternatively, should testing in the first loop be modified?

To stay with the original design, yes.

-- 
* Jens Axboe <axboe@suse.de>
* SuSE Labs
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/