Re: [PATCH] Speed up the cdrw packet writing driver

[Peter Osterlund <petero2@telia.com>]

Jens Axboe <axboe@suse.de> writes:

> On Sat, Aug 14 2004, Peter Osterlund wrote:
> > 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.

-- 
Peter Osterlund - petero2@telia.com
http://w1.894.telia.com/~u89404340