new IO scheduler for 2.4.20

The major benefit of this patch is that read latency is much lower while lots of writes are occuring. On my machine, running:

while :; do dd if=/dev/zero of=foo bs=1M count=1000 conv=notrunc; done

makes 2.4.20 unusable. With this patch the "write bomb" causes no particular problems.

With this version of the patch I've improved the bulk read performance of the elevator. The bonnie++ results are now:

-Per Chr- --Block-- -Rewrite- -Per Chr- --Block--
Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP

2.4.20           1G 13001  97 34939  18 13034   7 12175  92 34112  14
2.4.20-nas       1G 12923  98 36471  17 13340   8 10809  83 35569  13

Note that the "rewrite" and "per-char read" stats are slightly bogus for 2.4.20-nas. Reads get a boost in priority over writes. When the "per-char read" test has started there is still some writing happening from the rewrite test. I think the net effect is that the "rewrite" number is too high and the "per-char read" number is too low.

I would be very pleased if someone could run some tests on using bonnie, contest, or their other favorite benchmarks and post the results.

Neil

diff -u -ur linux-2.4.20/Makefile linux-iosched-2/Makefile
@@ -1,7 +1,7 @@
 VERSION = 2
 PATCHLEVEL = 4
 SUBLEVEL = 20
-EXTRAVERSION =
+EXTRAVERSION = -nas
 
 KERNELRELEASE=$(VERSION).$(PATCHLEVEL).$(SUBLEVEL)$(EXTRAVERSION)
 

diff -u -ur linux-2.4.20/drivers/block/ll_rw_blk.c linux-iosched-2/drivers/block/ll_rw_blk.c
@@ -480,7 +480,7 @@
 void blk_init_queue(request_queue_t * q, request_fn_proc * rfn)
 {
 	INIT_LIST_HEAD(&q->queue_head);
-	elevator_init(&q->elevator, ELEVATOR_LINUS);
+	elevator_init(&q->elevator, ELEVATOR_NEIL);
 	blk_init_free_list(q);
 	q->request_fn     	= rfn;
 	q->back_merge_fn       	= ll_back_merge_fn;

@@ -922,7 +922,8 @@
 			rw = READ;	/* drop into READ */
 		case READ:
 		case WRITE:
-			latency = elevator_request_latency(elevator, rw);
+			/* latency = elevator_request_latency(elevator, rw); */
+			latency = 1;
 			break;
 		default:
 			BUG();

diff -u -ur linux-2.4.20/include/linux/elevator.h linux-iosched-2/include/linux/elevator.h
@@ -31,6 +31,9 @@
 void elevator_linus_merge_cleanup(request_queue_t *, struct request *, int);
 void elevator_linus_merge_req(struct request *, struct request *);
 
+int elevator_neil_merge(request_queue_t *, struct request **, struct list_head *, struct buffer_head *, int, int);
+void elevator_neil_merge_req(struct request *, struct request *);
+
 typedef struct blkelv_ioctl_arg_s {
 	int queue_ID;
 	int read_latency;

@@ -101,3 +104,12 @@
 	})
 
 #endif
+
+#define ELEVATOR_NEIL							\
+((elevator_t) {								\
+	0,				/* read_latency */		\
+	0,				/* write_latency */		\
+									\
+	elevator_neil_merge,		/* elevator_merge_fn */		\
+	elevator_neil_merge_req,	/* elevator_merge_req_fn */	\
+	})

Nice to see 2.4 getting some attention. I'll try and get around to contesting it.

How does this compare to akpm's read-latency2 patch that he posed some time ago? That seems to make a massive difference but was knocked back for style or approach.

Con

It looks like they do fairly similar things. Andrew's patch puts unmergable read requests at a fixed distance from the front of the queue. My patch lets unmerged reads skip max((reads - writes), 0) requests. That's probably more fair when lots of reads and writes are in queue.

Andrew's idea of always allowing a merge is probably a good idea and could be adopted.

My patch uses a fixed deadline for requests (similar to Jen's deadline scheduler). I'm not sure if that's an advantage or not. Note that the deadline of writes are ignored when inserting a read.

I didn't change the size of the request queue. I can't find where that gets set in 2.4.20. :-(

Sorry for the hand-waving. I didn't know about Andrew's patch and I obviously didn't do enough testing yet.

Neil

in drivers/block/ll_rw_blk.c :: blk_init_free_list()

I think the main reason (aside from memory consumption) 2.4 has such small queues is to minimize read latency. If your patch goes off fixes that, you can probably get away with larger queues, which will help in merging. But then you definitely want to look into always merging reads, like Andrew does.

A maximum of ~1000 request entries seems nice if you really give a boost to reads otherwise.

Robert Love