get_request starvation fix

Second version of this patch, incorporating Suparna's suggested simplification (the low-water mark was unnecessary).

This patch is working well here. Hopefully it'll pop up in an rmap kernel soon.

Bill Irwin has been doing some fairly extensive tuning and testing of this. Hopefully he'll come out with some numbers soon.

I include the original description...

==== make_request description ====

Here's a patch which addresses the get_request starvation problem.

The problem we're experiencing is that when the request queue is exhausted, processes go to sleep until the request queue has refilled to the batch_nr_requests level. But already-running tasks can simply whizz in and steal free requests, thus preventing the sleeping tasks from getting woken.

Some instrumentation illustrates this clearly. All testing was on ext2. In a `dbench 64' run on stock 2.4.18-pre9, the maximum sleep duration in __get_request_wait() was 37 seconds, and it's being very unfair. Look at this section of the trace:

Feb  7 21:59:06 mnm kernel: dbench[883] wakes after 442ms
Feb  7 21:59:06 mnm kernel: dbench[877] wakes after 442ms
Feb  7 21:59:06 mnm kernel: dbench[868] wakes after 441ms
Feb  7 21:59:06 mnm kernel: kupdated[7] wakes after 11587ms
Feb  7 21:59:06 mnm kernel: dbench[914] wakes after 574ms
Feb  7 21:59:06 mnm kernel: dbench[873] wakes after 2618ms
Feb  7 21:59:06 mnm kernel: dbench[927] wakes after 755ms
Feb  7 21:59:06 mnm kernel: dbench[873] wakes after 263ms
Feb  7 21:59:06 mnm kernel: dbench[924] wakes after 838ms
Feb  7 21:59:06 mnm kernel: dbench[924] wakes after 134ms
Feb  7 21:59:06 mnm kernel: dbench[871] wakes after 18688ms
Feb  7 21:59:06 mnm kernel: dbench[908] wakes after 3245ms
Feb  7 21:59:06 mnm kernel: dbench[895] wakes after 974ms
Feb  7 21:59:06 mnm kernel: dbench[878] wakes after 27401ms
Feb  7 21:59:06 mnm kernel: dbench[895] wakes after 278ms
Feb  7 21:59:06 mnm kernel: dbench[904] wakes after 278ms

With the patch applied, the maximum sleep duration was eight seconds, but when this was happening, *all* tasks were sleeping for similar durations:

Feb  7 23:55:40 mnm kernel: dbench[948] wakes after 3978ms
Feb  7 23:55:40 mnm kernel: dbench[935] wakes after 3439ms
Feb  7 23:55:41 mnm kernel: dbench[955] wakes after 2998ms
Feb  7 23:55:41 mnm kernel: dbench[965] wakes after 2847ms
Feb  7 23:55:41 mnm kernel: dbench[994] wakes after 3032ms
Feb  7 23:55:41 mnm kernel: dbench[969] wakes after 2652ms
Feb  7 23:55:41 mnm kernel: dbench[956] wakes after 2197ms
Feb  7 23:55:41 mnm kernel: dbench[993] wakes after 1589ms
Feb  7 23:55:41 mnm kernel: dbench[990] wakes after 1590ms
Feb  7 23:55:41 mnm kernel: dbench[939] wakes after 1585ms
Feb  7 23:55:41 mnm kernel: kupdated[7] wakes after 1555ms
Feb  7 23:55:41 mnm kernel: dbench[976] wakes after 1787ms
Feb  7 23:55:41 mnm kernel: dbench[997] wakes after 1653ms
Feb  7 23:55:41 mnm kernel: dbench[961] wakes after 1891ms
Feb  7 23:55:42 mnm kernel: dbench[966] wakes after 1967ms
Feb  7 23:55:42 mnm kernel: dbench[936] wakes after 1339ms
Feb  7 23:55:42 mnm kernel: dbench[965] wakes after 1216ms
Feb  7 23:55:42 mnm kernel: kjournald[9] wakes after 1253ms
Feb  7 23:55:42 mnm kernel: dbench[990] wakes after 879ms
Feb  7 23:55:42 mnm kernel: kupdated[7] wakes after 849ms
Feb  7 23:55:42 mnm kernel: dbench[959] wakes after 343ms
Feb  7 23:55:42 mnm kernel: dbench[936] wakes after 343ms
Feb  7 23:55:42 mnm kernel: dbench[964] wakes after 492ms
Feb  7 23:55:42 mnm kernel: dbench[966] wakes after 648ms
Feb  7 23:55:42 mnm kernel: kupdated[7] wakes after 413ms
Feb  7 23:55:42 mnm kernel: dbench[988] wakes after 344ms

The actual algorithm I chose is described in the patch. It is noteworthy that the wakeup strategy has changed from wake-all to wake-one, which should save a few cycles. The number of context switches during the entire dbench 64 run fell from 57,000 to 29,000.

Interestingly, dbench runtimes are still very inconsistent, and many clients still exit quite early in the run. Beats me.

Rik, this patch will conflict with read-latency2 in the init code. Easily fixable. I haven't tested with the larger request queue, but I suggest that we want to keep the 1024 requests, a high-water mark of queue_nr_requests/4 and a low-water mark of queue_nr_requests/8. I'll do more testing tomorrow.

Also, you noted the other day that a LILO run *never* terminated when there was a dbench running. This is in fact not due to request starvation. It's due to livelock in invalidate_bdev(), which is called via ioctl(BLKFLSBUF) by LILO. invalidate_bdev() will never terminate as long as another task is generating locked buffers against the device.

=====================================

@@ -119,9 +119,9 @@ struct request_queue
 	spinlock_t		queue_lock;
 
 	/*
-	 * Tasks wait here for free request
+	 * Tasks wait here for free read and write requests
 	 */
-	wait_queue_head_t	wait_for_request;
+	wait_queue_head_t	wait_for_requests[2];
 };
 
 struct blk_dev_struct {

-

Much of my testing has involved varying elevator and bdflush parameters to find what works best with this. From preliminary results it is clear that the resolution of the fairness issues in this patch and the read latency patch does not impair performance.

I'll do a bunch more runs tonight with the latest version of this. My prior runs were with an earlier version.

Cheers,
Bill

It seems the real gain (in latency) is caused by the FIFO behaviour.

That is, removing this hunk (against __get_request_wait())

- if (q->rq[rw].count < batch_requests)
+ if (q->rq[rw].count == 0)

                        schedule();

Would not make _much_ difference latency-wise. I'm I right or missing something ?

Anyway, I would like to have the patch cleaned up for 2.4.19-pre (remove the instrumentation stuff _and_ make it clear on the documentation that READA requests are not being used in practice).

Thanks a lot for that, Andrew.

Well there is no net gain in latency. What we've gained is *fairness*, so the worst-case latency is improved. And yes, it's the FIFO behaviour
which provides that. And it is the exclusive wait which reduces the context
switch rate by 50%.

Well the code which is presently in -rc1 is quite pointless. We perform the above test a couple of microseconds after determining that there are zero free requests. So the test you've illustrated will *always* be true. The test for zero is the right thing to do - it's just normal waitqueue handling. It's just a little obfuscated by the implicit test-for-zero in get_request().

However, contrary to my earlier guess, the request batching does make a measurable difference. Changing the code so that we wake up a sleeper as soon as any request is freed costs maybe 30% on `dbench 64'.

READA is used in a few filesystems for directory readahead. (And since dir-in-pagecache, ext2 is no longer performing directory readhead. Bad.)

I came >this< close to killing READA altogether. I believe it's a misfeature. If we're under intense seek pressure, the very, very _last_ thing we want to do is to create more seeks by not performing readahead. But given that the misfeature only applies to creation of new requests, and that block-contiguous readahead will still work OK, it's not too serious. Plus it's a stable kernel :)

@@ -119,9 +119,9 @@ struct request_queue
 	spinlock_t		queue_lock;
 
 	/*
-	 * Tasks wait here for free request
+	 * Tasks wait here for free read and write requests
 	 */
-	wait_queue_head_t	wait_for_request;
+	wait_queue_head_t	wait_for_requests[2];
 };
 
 struct blk_dev_struct {

-

Is this consistent with results on other IO benchmarks?

--
Daniel

I dunno. I doubt it - few of the other benchmarks are very
seek-intensive. dbench is somewhat repeatable if you load
it up with enough clients. And average the results across enough runs. And stand on one leg and squint.