Speed up the cdrw packet writing driver

Hi!

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

Quoted 5 lines · Peter Osterlund

Hi!

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

It looks like you are assuming that bio->bi_sector is unique which isn't necessarily true. In that respect, list -> rbtree conversion isn't trivial (or, at least it requires extra code to handle this).

Quoted 10 lines · Jens Axboe

Quoted 5 lines · Peter Osterlund

Hi!

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

It looks like you are assuming that bio->bi_sector is unique which isn't necessarily true. In that respect, list -> rbtree conversion isn't trivial (or, at least it requires extra code to handle this).

I don't think that is assumed anywhere.

The pkt_rbtree_find() function returns the first node with a sector number >= s, even if there are multiple bios with bi_sector == s. Note that the code branches to the left if s == tmp->bio->bi_sector.

The pkt_rbtree_insert() function is careful to insert a bio after any already existing bios with the same sector number. Note that it branches to the right if s == tmp->bio->bi_sector.

The tree rotations done internally in rbtree.c also can't mess things up, because tree rotations don't change the inorder traversal order of a tree.

Quoted 12 lines · Peter Osterlund

Quoted 9 lines · Jens Axboe

Quoted 4 lines · Peter Osterlund

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

It looks like you are assuming that bio->bi_sector is unique which isn't necessarily true. In that respect, list -> rbtree conversion isn't trivial (or, at least it requires extra code to handle this).

Quoted 3 lines

I don't think that is assumed anywhere.

[...]

You are right, the code looks fine indeed. The bigger problem is probably that a faster data structure is needed at all, having hundreds of thousands bio's pending for a packet writing device is not nice at all.

Quoted 17 lines · Jens Axboe

Quoted 15 lines · Peter Osterlund

Quoted 9 lines · Jens Axboe

Quoted 4 lines · Peter Osterlund

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

It looks like you are assuming that bio->bi_sector is unique which isn't necessarily true. In that respect, list -> rbtree conversion isn't trivial (or, at least it requires extra code to handle this).

I don't think that is assumed anywhere.

[...]

Quoted 4 lines

You are right, the code looks fine indeed. The bigger problem is probably that a faster data structure is needed at all, having hundreds of thousands bio's pending for a packet writing device is not nice at all.

Why is it not nice? If the VM has decided to create 400MB of dirty data on a DVD+RW packet device, I don't see a problem with submitting all bio's at the same time to the packet device.

The situation happened when I dumped >1GB of data to a DVD+RW disc on a 1GB RAM machine. For some reason, the number of pending bio's didn't go much larger than 200000 (ie 400MB) even though it could probably have gone to 800MB without swapping. The machine didn't feel unresponsive during this test.

Quoted 4 lines · Peter Osterlund

Why is it not nice? If the VM has decided to create 400MB of dirty data on a DVD+RW packet device, I don't see a problem with submitting all bio's at the same time to the packet device.

We also have a limit on the number of in-flight requests:
/sys/block/sda/queue/nr_requests. It defaults to 128.

Are you saying that your requests are so huge that each one has 1000 BIOs? That would be odd, for an IDE interface.

This defaults to 8192 on my (IDE) system. IIRC this value is larger if 48-bit addressing is in use (drive size > ~128GB). It does not seem right to me that the size of your hard drive should dictate the amount of I/O allowed to be in flight.

Quoted 20 lines · Peter Osterlund

Quoted 17 lines · Jens Axboe

Quoted 15 lines · Peter Osterlund

Quoted 9 lines · Jens Axboe

Quoted 4 lines · Peter Osterlund

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

It looks like you are assuming that bio->bi_sector is unique which isn't necessarily true. In that respect, list -> rbtree conversion isn't trivial (or, at least it requires extra code to handle this).

I don't think that is assumed anywhere.

[...]

Quoted 8 lines

Quoted 4 lines

You are right, the code looks fine indeed. The bigger problem is probably that a faster data structure is needed at all, having hundreds of thousands bio's pending for a packet writing device is not nice at all.

Why is it not nice? If the VM has decided to create 400MB of dirty data on a DVD+RW packet device, I don't see a problem with submitting all bio's at the same time to the packet device.

We also have a limit on the number of in-flight requests:
/sys/block/sda/queue/nr_requests. It defaults to 128.

Are you saying that your requests are so huge that each one has 1000 BIOs? That would be odd, for an IDE interface.

Quoted 3 lines

Are you saying that your requests are so huge that each one has 1000 BIOs? That would be odd, for an IDE interface.

No, the thing is that the packet driver doesn't create requests at all. It stuffs incoming bio's in the rbtree, then the worker thread collects bio's from the rbtree for the same "zone" on the disc (each zone is 64kb on a CDRW and 32KB on a DVD). The driver then creates a new bio with the same size as the zone size and submits it to the real CD/DVD device.

Quoted 4 lines · Peter Osterlund

Quoted 3 lines

Are you saying that your requests are so huge that each one has 1000 BIOs? That would be odd, for an IDE interface.

Quoted 6 lines

No, the thing is that the packet driver doesn't create requests at all. It stuffs incoming bio's in the rbtree, then the worker thread collects bio's from the rbtree for the same "zone" on the disc (each zone is 64kb on a CDRW and 32KB on a DVD). The driver then creates a new bio with the same size as the zone size and submits it to the real CD/DVD device.

Good lord. I assume there's a good reason for this?

Quoted 17 lines · Jens Axboe

Quoted 15 lines · Peter Osterlund

Quoted 9 lines · Jens Axboe

Quoted 4 lines · Peter Osterlund

This patch replaces the pd->bio_queue linked list with an rbtree. The list can get very long (>200000 entries on a 1GB machine), so keeping it sorted with a naive algorithm is far too expensive.

It looks like you are assuming that bio->bi_sector is unique which isn't necessarily true. In that respect, list -> rbtree conversion isn't trivial (or, at least it requires extra code to handle this).

I don't think that is assumed anywhere.

[...]

Quoted 4 lines

You are right, the code looks fine indeed. The bigger problem is probably that a faster data structure is needed at all, having hundreds of thousands bio's pending for a packet writing device is not nice at all.

Why is it not nice? If the VM has decided to create 400MB of dirty data on a DVD+RW packet device, I don't see a problem with submitting all bio's at the same time to the packet device.

The situation happened when I dumped >1GB of data to a DVD+RW disc on a 1GB RAM machine. For some reason, the number of pending bio's didn't go much larger than 200000 (ie 400MB) even though it could probably have gone to 800MB without swapping. The machine didn't feel unresponsive during this test.

Quoted 10 lines · Peter Osterlund

Quoted 4 lines · Jens Axboe

You are right, the code looks fine indeed. The bigger problem is probably that a faster data structure is needed at all, having hundreds of thousands bio's pending for a packet writing device is not nice at all.

Why is it not nice? If the VM has decided to create 400MB of dirty data on a DVD+RW packet device, I don't see a problem with submitting all bio's at the same time to the packet device.

It's not nice because flushing 400MB of dirty data to the packet device will take _ages_. That the vm will dirty that much data for you non-blocking is a problem in itself. It would still be a really good idea for the packet writing driver to "congest" itself, like it happens for struct request devices, to prevent build up of these huge queues.

Quoted 5 lines

The situation happened when I dumped >1GB of data to a DVD+RW disc on a 1GB RAM machine. For some reason, the number of pending bio's didn't go much larger than 200000 (ie 400MB) even though it could probably have gone to 800MB without swapping. The machine didn't feel unresponsive during this test.

But it very well could have. If you dive into the bio mempool (or the biovec pool) and end up having most of those reserved entries built up for execution half an hour from now, you'll stall (or at least hinder) other processes from getting real work done.

Latencies are horrible, I don't think it makes sense to allow more than a few handful of pending zone writes in the packet writing driver.

Quoted 6 lines

Quoted 5 lines

The situation happened when I dumped >1GB of data to a DVD+RW disc on a 1GB RAM machine. For some reason, the number of pending bio's didn't go much larger than 200000 (ie 400MB) even though it could probably have gone to 800MB without swapping. The machine didn't feel unresponsive during this test.

Quoted 7 lines

But it very well could have. If you dive into the bio mempool (or the biovec pool) and end up having most of those reserved entries built up for execution half an hour from now, you'll stall (or at least hinder) other processes from getting real work done.

Latencies are horrible, I don't think it makes sense to allow more than a few handful of pending zone writes in the packet writing driver.

I ran some tests copying files to a 4x DVD+RW disc for different values of the maximum number of allowed bios in the queue. I used kernel 2.6.8.1 with the packet writing patches from the -mm tree. All tests used the udf filesystem.

Test 1: dd-ing 250MB from /dev/zero:

        1024:  	53.2s
        8192:	54.6s
        inf:	51.2s

Test 2: Writing 29 files, total size 120MB (Source files cached in RAM before the test started):

        1024:	71.6s
        8192:	81.1s
        32768:	52.7s
        49152:	31.4s
        65536:	26.6s
        inf:	27.7s

Test 3: Writing 48 files, total size 196MB (Source files cached in RAM before the test started):

        65536:	65.8s
        inf:	40.2s

Test 4: Repeat of test 3:

        65536:	67.4s
        inf:	41.8s

The conclusion is that when writing one big file, it doesn't hurt to limit the number of pending bios, but when writing many files, limiting the amount of queued data to "only" 128MB makes the write performance 60% slower.

Note that the reduced I/O performance will also reduce the lifetime of the disc, because some sectors will be written more often than necessary.

Quoted 19 lines · Peter Osterlund

Quoted 6 lines

Quoted 5 lines

The situation happened when I dumped >1GB of data to a DVD+RW disc on a 1GB RAM machine. For some reason, the number of pending bio's didn't go much larger than 200000 (ie 400MB) even though it could probably have gone to 800MB without swapping. The machine didn't feel unresponsive during this test.

Quoted 7 lines

But it very well could have. If you dive into the bio mempool (or the biovec pool) and end up having most of those reserved entries built up for execution half an hour from now, you'll stall (or at least hinder) other processes from getting real work done.

Latencies are horrible, I don't think it makes sense to allow more than a few handful of pending zone writes in the packet writing driver.

I ran some tests copying files to a 4x DVD+RW disc for different values of the maximum number of allowed bios in the queue. I used kernel 2.6.8.1 with the packet writing patches from the -mm tree. All tests used the udf filesystem.

Quoted 5 lines

Test 1: dd-ing 250MB from /dev/zero:

        1024:  	53.2s
        8192:	54.6s
        inf:	51.2s

Out of how many runs did you average those numbers? Look close enough to be normal variance, so not conclusive I'd say.

Quoted 21 lines

Test 2: Writing 29 files, total size 120MB (Source files cached in RAM before the test started):

        1024:	71.6s
        8192:	81.1s
        32768:	52.7s
        49152:	31.4s
        65536:	26.6s
        inf:	27.7s

Test 3: Writing 48 files, total size 196MB (Source files cached in RAM before the test started):

        65536:	65.8s
        inf:	40.2s

Test 4: Repeat of test 3:

        65536:	67.4s
        inf:	41.8s

Quoted 4 lines

The conclusion is that when writing one big file, it doesn't hurt to limit the number of pending bios, but when writing many files, limiting the amount of queued data to "only" 128MB makes the write performance 60% slower.

I'd rather say that the above is indicative of a layout (or other) problem with the file system. 64K bio queue must be at least 256MB pending in itself, how can inf even make a difference there?

You would gain so much more performance by fixing the fs

instead of attempting to build up hundreds of megabytes of pending data,

I think that's a really bad idea (not just a suboptimal solution, also extremely bad for the rest of the system).

Review

Quoted 3 lines

(quoted diff) +3 -0

+	while (pd->bio_queue_size >= 8192)
+		blk_congestion_wait(WRITE, HZ / 5);
+

This is not really how you'd want to do it. When you reach that threshold, mark the queue congested and get pdflush to leave you alone instead. Then clear the congestion when you get below a certain number again. For this test I don't think it should make a difference, though.

Is this a general VM limitation? Has anyone been able to saturate the
write bandwidth of two different block devices at the same time, when they operate at vastly different speeds (45MB/s vs 5MB/s), and when the writes are large enough to cause memory pressure?

Quoted 5 lines · Peter Osterlund

Is this a general VM limitation? Has anyone been able to saturate the
write bandwidth of two different block devices at the same time, when they operate at vastly different speeds (45MB/s vs 5MB/s), and when the writes are large enough to cause memory pressure?

I haven't explicitly tested the pdflush code in a while, and I never tested on devices with such disparate bandwidth. But it _should_ work.

The basic deign of the pdflush writeback path is:

	for ( ; ; ) {
		for (each superblock) {
			if (no pdflush thread is working this sb's queue &&
			    the superblock's backingdev is not congested) {
				do some writeout, up to congestion, trying
				to not block on request queue exhaustion
			}
		}
		blk_congestion_wait()
	}

So it basically spins around all the queues keeping them full in a non-blocking manner.

There _are_ times when pdflush will accidentally block. Say, doing a metadata read. In that case other pdflush instances will keep other queues busy.

I tested it up to 12 disks. Works OK.

Quoted 9 lines

So it basically spins around all the queues keeping them full in a non-blocking manner.

There _are_ times when pdflush will accidentally block. Say, doing a metadata read. In that case other pdflush instances will keep other queues busy.

I tested it up to 12 disks. Works OK.

OK, this should make sure that dirty data is flushed as fast as the disks can handle, but is there anything that makes sure there will be enough dirty data to flush for each disk?

Assume there are two processes writing one file each to two different block devices. To be able to dirty more data a process will have to allocate a page, and a page becomes available whenever one of the disks finishes an I/O operation. If both processes have a 50/50 chance to get the freed page, they will dirty data equally fast once steady state has been reached, even if the block devices have very different write bandwidths.

Quoted 4 lines · Peter Osterlund

OK, this should make sure that dirty data is flushed as fast as the disks can handle, but is there anything that makes sure there will be enough dirty data to flush for each disk?

Page allocation is fairly decoupled from the dirty memory thresholds. The process which wants to write to the fast disk will skirt around the pages which are dirty against the slow disk and will reclaim clean pagecache instead. So the writer to the fast disk _should_ be able to allocate pages sufficiently quickly.

The balance_dirty_pages() logic doesn't care (or know) about whether the pages are dirty against a slow device of a fast one - it just keeps the queues full while clamping the amount of dirty memory. I do think that it's possible for the writer to the fast device to get blocked in balance_dirty_pages() due to there being lots of dirty pages against a slow device.

Or not - the fact that the fast device retires writes more quickly will cause waiters in balance_dirty_pages() to unblock promptly.

Or not not - we'll probably get into the situation where almost all of the dirty pages are dirty against the slower device.

hm. It needs some verification testing.