CFQ scheduler, #2

Hi,

The version posted the other day did fair queueing of requests between processes, but it did not help to provide fair request allocation. This version does that too, results are rather remarkable. In addition, the following changes were made:

- Fix lost request problem with rbtree aliasing. The default io scheduler in 2.5.60 has the same bug, a fix has been sent separetely to Linus that addresses this.

- Add front merging.

- Missing queue_lock grab in get_request_wait() before checking request list count. Again, a generic kernel bug. A patch will be sent to Linus to address that as well.

Obligatory contest results.

no_load:

Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   31      177.4   0       0.0     1.00
2.5.60-cfq-fr2      1   31      177.4   0       0.0     1.00
2.5.60-mm1          2   32      171.9   0       0.0     1.00
cacherun:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   29      182.8   0       0.0     0.94
2.5.60-cfq-fr2      1   29      182.8   0       0.0     0.94
2.5.60-mm1          2   29      186.2   0       0.0     0.91
process_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   38      142.1   12      47.4    1.23
2.5.60-cfq-fr2      1   43      123.3   20      67.4    1.39
2.5.60-mm1          2   38      142.1   13      50.0    1.19
ctar_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   38      147.4   0       0.0     1.23
2.5.60-cfq-fr2      1   37      151.4   0       0.0     1.19
2.5.60-mm1          2   36      155.6   0       0.0     1.12
xtar_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   40      140.0   0       2.5     1.29
2.5.60-cfq-fr2      1   37      148.6   0       2.6     1.19
2.5.60-mm1          2   39      143.6   0       2.6     1.22
io_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   93      61.3    2       14.0    3.00
2.5.60-cfq-fr2      1   73      76.7    1       9.8     2.35
2.5.60-mm1          2   82      69.5    1       9.8     2.56
read_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   40      140.0   0       5.0     1.29
2.5.60-cfq-fr2      1   40      140.0   0       5.0     1.29
2.5.60-mm1          2   38      147.4   0       2.6     1.19
list_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   35      157.1   0       8.6     1.13
2.5.60-cfq-fr2      1   35      160.0   0       11.4    1.13
2.5.60-mm1          2   34      164.7   0       8.8     1.06
mem_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   50      116.0   75      10.0    1.61
2.5.60-cfq-fr2      1   57      100.0   81      8.8     1.84
2.5.60-mm1          2   52      113.5   77      9.4     1.62
dbench_load:
Kernel         [runs]   Time    CPU%    Loads   LCPU%   Ratio
2.5.60              2   36      155.6   12693   27.8    1.16
2.5.60-mm1          2   35      160.0   12486   28.6    1.09

Patch is against 2.5.60-BK.

===== drivers/block/Makefile 1.14 vs edited =====

@@ -8,7 +8,8 @@
 # In the future, some of these should be built conditionally.
 #
 
-obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o deadline-iosched.o
+obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o \
+	    deadline-iosched.o cfq-iosched.o
 
 obj-$(CONFIG_MAC_FLOPPY)	+= swim3.o
 obj-$(CONFIG_BLK_DEV_FD)	+= floppy.o

===== drivers/block/elevator.c 1.37 vs edited =====

@@ -408,6 +408,16 @@
 	return NULL;
 }
 
+int elv_may_queue(request_queue_t *q, int rw)
+{
+	elevator_t *e = &q->elevator;
+
+	if (e->elevator_may_queue_fn)
+		return e->elevator_may_queue_fn(q, rw);
+
+	return 1;
+}
+
 int elv_register_queue(struct gendisk *disk)
 {
 	request_queue_t *q = disk->queue;

===== drivers/block/ll_rw_blk.c 1.151 vs edited =====

@@ -45,7 +45,7 @@
  * Number of requests per queue.  This many for reads and for writes (twice
  * this number, total).
  */
-static int queue_nr_requests;
+int queue_nr_requests;
 
 /*
  * How many free requests must be available before we wake a process which

@@ -1283,7 +1283,7 @@
 	if (blk_init_free_list(q))
 		return -ENOMEM;
 
-	if ((ret = elevator_init(q, &iosched_deadline))) {
+	if ((ret = elevator_init(q, &iosched_cfq))) {
 		blk_cleanup_queue(q);
 		return ret;
 	}

@@ -1320,7 +1320,7 @@
 	struct request *rq = NULL;
 	struct request_list *rl = q->rq + rw;
 
-	if (!list_empty(&rl->free)) {
+	if (!list_empty(&rl->free) && elv_may_queue(q, rw)) {
 		rq = blkdev_free_rq(&rl->free);
 		list_del_init(&rq->queuelist);
 		rq->ref_count = 1;

@@ -1358,11 +1358,19 @@
 
 	generic_unplug_device(q);
 	do {
+		int block = 0;
+
 		prepare_to_wait_exclusive(&rl->wait, &wait,
 					TASK_UNINTERRUPTIBLE);
-		if (!rl->count)
+		spin_lock_irq(q->queue_lock);
+		if (!rl->count || !elv_may_queue(q, rw))
+			block = 1;
+		spin_unlock_irq(q->queue_lock);
+
+		if (block)
 			io_schedule();
 		finish_wait(&rl->wait, &wait);
+
 		spin_lock_irq(q->queue_lock);
 		rq = get_request(q, rw);
 		spin_unlock_irq(q->queue_lock);

===== include/linux/elevator.h 1.18 vs edited =====

@@ -15,6 +15,7 @@
 typedef void (elevator_remove_req_fn) (request_queue_t *, struct request *);
 typedef struct request *(elevator_request_list_fn) (request_queue_t *, struct request *);
 typedef struct list_head *(elevator_get_sort_head_fn) (request_queue_t *, struct request *);
+typedef int (elevator_may_queue_fn) (request_queue_t *, int);
 
 typedef int (elevator_init_fn) (request_queue_t *, elevator_t *);
 typedef void (elevator_exit_fn) (request_queue_t *, elevator_t *);

@@ -34,6 +35,8 @@
 	elevator_request_list_fn *elevator_former_req_fn;
 	elevator_request_list_fn *elevator_latter_req_fn;
 
+	elevator_may_queue_fn *elevator_may_queue_fn;
+
 	elevator_init_fn *elevator_init_fn;
 	elevator_exit_fn *elevator_exit_fn;
 

@@ -58,6 +61,7 @@
 extern struct request *elv_latter_request(request_queue_t *, struct request *);
 extern int elv_register_queue(struct gendisk *);
 extern void elv_unregister_queue(struct gendisk *);
+extern int elv_may_queue(request_queue_t *, int);
 
 #define __elv_add_request_pos(q, rq, pos)	\
 	(q)->elevator.elevator_add_req_fn((q), (rq), (pos))

@@ -72,6 +76,8 @@
  * starvation
  */
 extern elevator_t iosched_deadline;
+
+extern elevator_t iosched_cfq;
 
 extern int elevator_init(request_queue_t *, elevator_t *);
 extern void elevator_exit(request_queue_t *);

Jens Axboe

Agrh, old scores (not the fr2). Here's for the version sent out:

no_load:

Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    31      177.4   0       0.0     1.00
2.5.60-cfq-fr      2    31      177.4   0       0.0     1.00
2.5.60-mm1         2    32      171.9   0       0.0     1.00
cacherun:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    29      182.8   0       0.0     0.94
2.5.60-cfq-fr      2    29      182.8   0       0.0     0.94
2.5.60-mm1         2    29      186.2   0       0.0     0.91
process_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    38      142.1   12      47.4    1.23
2.5.60-cfq-fr      2    38      142.1   12      47.4    1.23
2.5.60-mm1         2    38      142.1   13      50.0    1.19
ctar_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    38      147.4   0       0.0     1.23
2.5.60-cfq-fr      2    38      147.4   0       0.0     1.23
2.5.60-mm1         2    36      155.6   0       0.0     1.12
xtar_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    40      140.0   0       2.5     1.29
2.5.60-cfq-fr      2    38      147.4   0       2.6     1.23
2.5.60-mm1         2    39      143.6   0       2.6     1.22
io_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    93      61.3    2       14.0    3.00
2.5.60-cfq-fr      2    71      78.9    1       8.1     2.29
2.5.60-mm1         2    82      69.5    1       9.8     2.56
read_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    40      140.0   0       5.0     1.29
2.5.60-cfq-fr      2    41      136.6   0       4.9     1.32
2.5.60-mm1         2    38      147.4   0       2.6     1.19
list_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    35      157.1   0       8.6     1.13
2.5.60-cfq-fr      2    34      161.8   0       8.8     1.10
2.5.60-mm1         2    34      164.7   0       8.8     1.06
mem_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    50      116.0   75      10.0    1.61
2.5.60-cfq-fr      2    47      123.4   74      10.6    1.52
2.5.60-mm1         2    52      113.5   77      9.4     1.62
dbench_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio
2.5.60             2    36      155.6   12693   27.8    1.16
2.5.60-cfq-fr      2    35      157.1   11368   25.7    1.13
2.5.60-mm1         2    35      160.0   12486   28.6    1.09

Jens Axboe

Greetings

I gave this a burn, and under hefty load it seems to provide a bit of anti-thrash benefit.

i(dang, wish I had pine/vi for winders box)log data attached

-Mike

2.5.61virgin make bzImage reference run
(poor box isn't _rediculously_ overloaded;)

real    8m9.710s
user    7m27.045s
sys     0m34.605s

three consecutive make -j30 bzImage runs

2.5.61cfq2

real    8m41.834s   8m36.908s   8m38.164s
user    7m37.208s   7m36.986s   7m36.456s
sys     0m42.921s   0m43.387s   0m43.312s

2.5.61virgin

real    8m39.723s   8m39.456s   8m42.102s
user    7m39.343s   7m38.800s   7m38.542s
sys     0m43.417s   0m43.322s   0m43.502s

/proc/vmstat 2.5.61cfq2 2.5.61virgin
-----------------------------------------
nr_dirty 20 13
nr_writeback 0 0
nr_pagecache 7308 7593
nr_page_table_pages 85 85
nr_reverse_maps 3229 3198
nr_mapped 599 599
nr_slab 1203 1184

pgpgin             1767432        1911614
pgpgout            1606743        1746497
pswpin              311297         338436
pswpout             371161         406675
pgalloc            3037961        3070811
pgfree             3060825        3093420
pgactivate          142329         135616
pgdeactivate        514672         507026
pgfault            4896877        4928530
pgmajfault           74342          84476
pgscan             2751953        5328260  <== ? hmm
pgrefill           1821561        1972715
pgsteal             528014         575301
pginodesteal             0              0
kswapd_steal        380282         522126
kswapd_inodesteal     7010           7132
pageoutrun            1107           1956
allocstall            3472           1238

pgrotated 358243 413450

Judging from your log, it ends up stalling kswapd and dramatically increases the number of times that normal processes need to go into the pageout code.

If this provides an anti-thrashing benefit, something's wrong with the VM in 2.5 ;)

Rik

Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>

With 30 odds processes, it doesn't take a whole lot for one process to have its share of requests eaten.

It's not a vm problem. But it is a problem if kswapd + pdflush can consume the entire request pool, stalling real user processes.

Mike, please retry the test with more requests available. CFQ does not rely on request queue length for fairness. Just changes:

	 (queue_nr_requests > 128)
		queue_nr_requests = 128;

to

	 (queue_nr_requests > 512)
		queue_nr_requests = 512;

in ll_rw_blk.c:blk_dev_init() and see how that runs.

Jens Axboe

Results attached. 512 comes out to be 240 on this box (128MB). I also did a burn with it hardwired to 512 on GP. Throughput numbers cut since there's all within expected jitter.

-Mike

/proc/vmstat 2.5.61cfq2 2.5.61virgin cfq2-512(240) cfq2-512
-----------------------------------------------------------------
nr_dirty 20 13 9 12
nr_writeback 0 0 0 0
nr_pagecache 7308 7593 7176 7737
nr_page_table_pages 85 85 85 85
nr_reverse_maps 3229 3198 3254 3159
nr_mapped 599 599 608 583
nr_slab 1203 1184 1169 1237

pgpgin          1767432        1911614       1758501      1775402
pgpgout         1606743        1746497       1595920      1654366
pswpin           311297         338436        307811       311515
pswpout          371161         406675        369132       383302
pgalloc         3037961        3070811       3030482      3020966
pgfree          3060825        3093420       3053524      3043355
pgactivate       142329         135616        134968       136655
pgdeactivate     514672         507026        481156       501111
pgfault         4896877        4928530       4891987      4913594
pgmajfault        74342          84476         74058        82857
pgscan          2751953        5328260       3250880      3797919
pgrefill        1821561        1972715       1896119      2057461
pgsteal          528014         575301        528513       529011
pginodesteal          0              0             0            0
kswapd_steal     380282         522126        405078       410382
kswapd_inodesteal  7010           7132          6704         6829
pageoutrun         1107           1956          1263         1259
allocstall         3472           1238          2865         2782

pgrotated 358243 413450 365914 387277

Which number are you looking at?

-Mike

pgscan 2751953 5328260 <== ? hmm

kswapd_steal 380282 522126

pageoutrun            1107           1956
allocstall            3472           1238

- we scan far less pages
- kswapd reclaims less pages
- we go into the pageout code less often
- allocations stall more often for a lack of free memory

cheers,

Rik

Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>

$ echo $(( 5328260/1956.0 ))       
2724.0593047034763
$ echo $(( (5328260/1956.0)*4 ))
10896.237218813905

That's 2724 pages or 11MB scanned per pageout run. Order-of-magnitude better ratio for pages stolen per pageout run. Wouldn't mind seeing a patch that improves this.

-- wli

I would interpret that differently. I would say we scan less because we don't need to scan as much, kswapd reclaims less for the same reason, and ditto for pageout ;-) The reduction in scans does seem _way_ high though...

wrt allocstall, I bet if I do a few runs, I'll see mucho variance there (could be wrong.. hunch)

-Mke

After 10 consecutive runs, stalls for 2.5.61cfq2 were 11060 vs. 3656 for 2.5.61virgin.

(dang, hunch-o-meter needs calibration;)

-Mike