Re: [RFC] Generalize prio_tree (1/3)

From: Werner Almesberger
Date: Mon Nov 15 2004 - 09:34:26 EST

Nick Piggin wrote:
> ... but humor me, you _are_ ensuring the following doesn't get
> reordered, say:
> (write, sect 100), (barrier), (write, sect 200)

Ah you found the case I didn't mention :-) Yes, that's handled
somewhere else. When the ABISS elevator sees a barrier, it just
pushes the current sort tree for non-reads (writes and weird
stuff) to a FIFO list.

So writes don't benefit that much from priorities. The good
thing is that they also happen to need them less ;-)

Hmm, I just see that power down (suspend and shutdown) sneaked out
again. Well, easy enough to fix.

> No comment on your prio tree generalization, sorry. Other than: it
> seems to be unfortunately quite ugly.

I know. Unfortunately, there doesn't seem to be a nice alternative
that doesn't either require additional fields (e.g. in MM, only half
of the key is not stored in the tree, the other half is calculated)
or *very* busy callbacks.

Of course, if Rajesh or the MM folks in general think that storing
the whole key in the tree is fine, I wouldn't complain :-)

> (eg. add the patch to the front
> of your ABISS elevator if you submit it to 2.6 or -mm).

Ah no, the ABISS elevator won't go into the kernel - it's just for
experimenting. But Jens is planning to add the overlap handling to
the block device layer. So the user is well on its way :-) It's just
more convenient if we can do this one step at a time, particularly
since prio_tree is a very general concept (much like lists or
red-black trees) anyway.

> But I don't have strong feelings on the matter. If Rajesh says its OK
> to go ahead as is, that would be fine by me :)

Cool. Thanks !

- Werner

/ Werner Almesberger, Buenos Aires, Argentina werner@xxxxxxxxxxxxxxx /
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at