Ragnar Kjørstad <reiserfs@ragnark.vestdata.no> writes:
> If I understand the current code correctly, it works like this:
[ example deleted ]
> So we've ended up with a very silly queue....
Indeed, the elevator logic is somewhat flawed. There are two problems
with the current code:
1. The test that decides if we have found a good spot to insert the
current request doesn't handle the wraparound case correctly. (The
case when the elevator reaches the end of the disk and starts over
from the beginning.)
2. If we can't find a good spot to insert the new request, we
currently insert it as early as possible in the queue. If no good
spot is found, it is more efficient and more fair to insert the new
request last in the queue.
The following patch fixes both problems. Here are the results from
'iozone 100' and Bonnie with and without this patch.
test8:
------
iozone:
4626750 bytes/second for writing the file
7431438 bytes/second for reading the file
bonnie:
-------Sequential Output-------- ---Sequential Input-- --Random--
-Per Char- --Block--- -Rewrite-- -Per Char- --Block--- --Seeks---
Machine MB K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU /sec %CPU
100 5278 60.6 7940 18.3 2876 9.7 5635 49.3 8344 16.7 179.3 2.0
test8 + modified elevator:
--------------------------
iozone:
4801172 bytes/second for writing the file
7613088 bytes/second for reading the file
bonnie:
-------Sequential Output-------- ---Sequential Input-- --Random--
-Per Char- --Block--- -Rewrite-- -Per Char- --Block--- --Seeks---
Machine MB K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU /sec %CPU
100 5727 66.6 8365 18.1 2921 9.2 5991 52.2 8171 16.0 171.0 2.0
Here is the patch:
--- linux-2.4.0-test8/drivers/block/elevator.c.orig Sun Sep 17 00:05:03 2000
+++ linux-2.4.0-test8/drivers/block/elevator.c Sun Sep 17 00:06:31 2000
@@ -34,20 +34,38 @@
struct list_head *real_head,
struct list_head *head, int orig_latency)
{
- struct list_head *entry = real_head;
- struct request *tmp;
-
- req->elevator_sequence = orig_latency;
-
- while ((entry = entry->prev) != head) {
- tmp = blkdev_entry_to_request(entry);
- if (IN_ORDER(tmp, req))
- break;
- if (!tmp->elevator_sequence)
- break;
- tmp->elevator_sequence--;
- }
- list_add(&req->queue, entry);
+ struct list_head *last = real_head->prev;
+ struct list_head *insert_after = last;
+ struct list_head *entry;
+ struct request *tmp1, *tmp2;
+
+ req->elevator_sequence = orig_latency;
+
+ if (last == head)
+ goto out;
+
+ entry = last;
+ tmp1 = blkdev_entry_to_request(entry);
+ do {
+ tmp2 = tmp1;
+ entry = entry->prev;
+ tmp1 = blkdev_entry_to_request(entry);
+ if (!tmp2->elevator_sequence)
+ break;
+ if (IN_ORDER(tmp1, tmp2) ?
+ (IN_ORDER(tmp1, req) && IN_ORDER(req, tmp2)) :
+ (IN_ORDER(tmp1, req) || IN_ORDER(req, tmp2))) {
+ insert_after = entry;
+ do {
+ entry = entry->next;
+ tmp1 = blkdev_entry_to_request(entry);
+ tmp1->elevator_sequence--;
+ } while (entry != last);
+ break;
+ }
+ } while (entry != head);
+out:
+ list_add(&req->queue, insert_after);
}
int elevator_linus_merge(request_queue_t *q, struct request **req,
-- Peter Österlund Email: peter.osterlund@mailbox.swipnet.se Sköndalsvägen 35 f90-pos@nada.kth.se S-128 66 Sköndal Home page: http://home1.swipnet.se/~w-15919 Sweden Phone: +46 8 942647- 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/
This archive was generated by hypermail 2b29 : Sat Sep 23 2000 - 21:00:14 EST