new IO scheduler for 2.4.20

Hi all,

Recently I was bitten badly by bad IO scheduler behavior on an important Linux server. An easy way to trigger this problem is to start a streaming write process:

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

and then try doing a bunch of small reads:

time (find kernel-tree -type f | xargs cat > /dev/null)

With Linux 2.4.20, the reading takes a very long time to finish. I looked at backporting Jen's deadline scheduler to 2.4 but decided it would be too much work (especially for someone like me who doesn't know much about kernel hacking).

I've come up with a fairly simple patch that seems to solve the starvation problem. Perhaps it is simple enough to get merged into the stable branch (after a little more polish). The basic idea is to give reads a boost if there are lots of write requests in the queue. I think my solution also prevents reads and writes from being starved indefinitely.

Throughput also seems good although I have not done a lot of testing yet. I would greatly appreciate it if people could give it a test.

Neil

diff -u -ur linux-2.4.20/drivers/block/elevator.c linux-iosched-1d/drivers/block/elevator.c
@@ -74,6 +74,86 @@
 	return 0;
 }
 
+int elevator_neil_merge(request_queue_t *q, struct request **req,
+			 struct list_head * head,
+			 struct buffer_head *bh, int rw,
+			 int max_sectors)
+{
+	struct list_head *entry = &q->queue_head;
+	unsigned int count = bh->b_size >> 9, ret = ELEVATOR_NO_MERGE;
+	unsigned long read_sectors = 0, write_sectors = 0;
+	unsigned int expire_time = jiffies - 1*HZ;
+	struct request *__rq;
+
+	while ((entry = entry->prev) != head) {
+		__rq = blkdev_entry_to_request(entry);
+
+		/*
+		 * we can't insert beyond a zero sequence point
+		 */
+		if (__rq->elevator_sequence == 0) {
+			goto append;
+		}
+
+		if (__rq->cmd == READ)
+			read_sectors += __rq->nr_sectors;
+		else
+			write_sectors += __rq->nr_sectors;
+
+		if (__rq->rq_dev != bh->b_rdev)
+			continue;
+
+		if (__rq->waiting)
+			continue;
+
+		if (__rq->cmd != rw)
+			continue;
+
+		if (time_before(__rq->start_time, expire_time)) {
+			break;
+		}
+
+		if (__rq->sector + __rq->nr_sectors == bh->b_rsector) {
+			if (__rq->nr_sectors + count <= max_sectors)
+				ret = ELEVATOR_BACK_MERGE;
+			*req = __rq;
+			break;
+		} else if (__rq->sector - count == bh->b_rsector) {
+			if (__rq->nr_sectors + count <= max_sectors)
+				ret = ELEVATOR_FRONT_MERGE;
+			*req = __rq;
+			break;
+		}
+	}
+
+	if (!*req && rw == READ) {
+		long extra_writes = write_sectors - read_sectors;
+		/*
+		 * If there are more writes than reads in the queue then put
+		 * read requests ahead of the extra writes.  This prevents
+		 * writes from starving reads.
+		 */
+		entry = q->queue_head.prev;
+		while (extra_writes > 0 && entry != head) {
+			__rq = blkdev_entry_to_request(entry);
+			if (__rq->cmd == WRITE)
+				extra_writes -= __rq->nr_sectors;
+			entry = entry->prev;
+		}
+		*req = blkdev_entry_to_request(entry);
+	}
+
+append:
+
+	return ret;
+}
+
+void elevator_neil_merge_req(struct request *req, struct request *next)
+{
+	if (time_before(next->start_time, req->start_time))
+		req->start_time = next->start_time;
+}
+
 
 int elevator_linus_merge(request_queue_t *q, struct request **req,
 			 struct list_head * head,

diff -u -ur linux-2.4.20/drivers/block/ll_rw_blk.c linux-iosched-1d/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-1d/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 */	\
+	})

Only in linux-iosched-1d: inst.sh

That's a local DoS.

Awful, isn't it?

This is a nice looking patch!

[...]

Okay, nas1 is the patch I orginally posted. With nas2, I am counting requests instead of sectors. The times below are for the find/cat command to complete while the dd command is running.

            time
    2.4.20  ????????? (I gave up after about 15 minutes)
    -nas1   1m56.746s
    -nas2   2m36.928s

Here's the contest results:

    no_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	50	90.0	0.0	0.0	1.00
    2.4.20-nas1      1	50	90.0	0.0	0.0	1.00
    2.4.20-nas2      1	50	92.0	0.0	0.0	1.00
    cacherun:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	46	97.8	0.0	0.0	0.92
    2.4.20-nas1      1	46	97.8	0.0	0.0	0.92
    2.4.20-nas2      1	46	97.8	0.0	0.0	0.92
    process_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	74	58.1	70.0	40.5	1.48
    2.4.20-nas1      1	75	57.3	73.0	40.0	1.50
    2.4.20-nas2      1	76	56.6	76.0	40.8	1.52
    ctar_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	60	78.3	9.0	16.7	1.20
    2.4.20-nas1      1	58	81.0	8.0	13.8	1.16
    2.4.20-nas2      1	60	78.3	9.0	16.7	1.20
    xtar_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	139	34.5	6.0	7.9	2.78
    2.4.20-nas1      1	71	64.8	2.0	4.2	1.42
    2.4.20-nas2      1	71	66.2	1.0	4.2	1.42
    io_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	191	27.7	42.1	13.1	3.82
    2.4.20-nas1      1	71	71.8	12.1	8.5	1.42
    2.4.20-nas2      1	76	69.7	12.3	9.1	1.52
    io_other:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	97	55.7	21.5	12.4	1.94
    2.4.20-nas1      1	65	80.0	12.3	9.0	1.30
    2.4.20-nas2      1	68	79.4	15.5	11.8	1.36
    read_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	75	73.3	3.6	9.3	1.50
    2.4.20-nas1      1	75	70.7	3.4	9.3	1.50
    2.4.20-nas2      1	79	69.6	3.7	8.9	1.58
    list_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	66	89.4	0.0	7.5	1.32
    2.4.20-nas1      1	66	87.9	0.0	7.6	1.32
    2.4.20-nas2      1	66	87.9	0.0	7.6	1.32
    mem_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	78	62.8	77.0	3.8	1.56
    2.4.20-nas1      1	70	68.6	77.0	5.7	1.40
    2.4.20-nas2      1	68	72.1	75.0	5.9	1.36
    dbench_load:
    Kernel      [runs]	Time	CPU%	Loads	LCPU%	Ratio
    2.4.20           1	202	23.8	6.0	60.4	4.04
    2.4.20-nas1      1	194	24.2	6.0	63.4	3.88
    2.4.20-nas2      1	194	24.2	6.0	63.4	3.88

It looks like nas1 works a little better. I think the reason is that if requests are counted then as soon as there is one read in queue, however small, the next non-contiguous read request will be inserted after a write request, however large.

Neil

On Sunday 20 April 2003 20:26, Neil Schemenauer wrote:

Hi Neil,

what about i/o throughput, bonnie or such?

ciao, Marc

bonnie++
Version 1.03 ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP

2.4.20           1G           36236  18 13423   7           29948  11 210.1   0
2.4.20-nas1      1G           35998  18 12076   7           19056   9 206.7   0
2.4.20-nas2      1G           37450  18 12101   7           19363   9 210.7   0

Read throughput has definitely taken a hit. I don't know why. Perhaps the elevator needs to have a little more relaxed definition of contiguous requests. Right now it only puts requests together if they are perfectly contiguous (the first sector in one request is the next after the last sector of another). I'll try to test that.

Any other theories?

Neil

can you try the above on 2.4.21pre5aa2? I also spent effort to fix it some month ago.

The interesting patch is this:

	http://www.us.kernel.org/pub/linux/kernel/people/andrea/kernels/v2.4/2.4.21pre5aa2/9981_elevator-lowlatency-4

the reason 2.4 mainline stalls so much is that the size of the queue is overkill for no good reason, so no matter the elvtune numbers, you're going to wait several dozen mbytes to be read or written before you can read or write the next 1k from another task.

the above patch is fairly old and it basically fixes the showstopper problem for me, contest looks fine now and throughput still is the best.

I don't like special "read hacks" for generic kernels that are critical with O_SYNC and journaling responsiveness too.

So I recommend to apply the above 2.4 patch if you suffer any I/O latency issue.

Andrea