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

[Werner Almesberger <werner@almesberger.net>]

Nick Piggin wrote:
> I'm curious, how do you plan to use them for healthier barrier handling?

Ah, you missed the great discussion on fsdevel and the BOF
at OLS :-)

http://marc.theaimsgroup.com/?t=108787649700005&r=1&w=2&n=34
http://marc.theaimsgroup.com/?t=108809650200006&r=1&w=2&n=11
http://marc.theaimsgroup.com/?l=linux-fsdevel&m=109107082406140&w=2

This comes from prioritization of requests at the elevator.
In order to honor priorities as much as possible, we need to
keep barriers from affecting all requests in the queue.

The idea is to ignore barriers unless requests separated by a
barrier overlap, and at least one of them is a write. prio_tree
is used to find those overlaps.

That way, priorities are only affected by barriers if using
some form of direct IO, with overlaps and writes. While this
isn't perfect (i.e. someone else scribbling over our files can
still spoil all the fun), it allows a much larger class of
applications to enjoy the full benefits of priorities.

Besides that, it also helps the elevator to do a better job for
requests even without priorities, because it doesn't have to go
FIFO whenever it sees a barrier.

See also section 3.6 of
http://abiss.sourceforge.net/doc/abiss-lk.ps.gz

The CPU overhead is actually quite marginal: in tests, the ABISS
elevator would actually outperform AS in terms of CPU time
spent (measured by sending a lot of random requests with AIO
into a large queue). While such tests compare apples and oranges,
they at least indicate that minimalizing the effect of barriers
doesn't have a horrible performance impact.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
/_http://www.almesberger.net/____________________________________________/