barriers vs. reads

barriers vs. reads

[Werner Almesberger]

I'm working on an elevator with priorities, and I'm wondering what
semantics are expected from barriers when it comes to reads.

My problem with read barriers is that they can upset priorities
quite a bit, by forcing the entire queue to be processed before
any new (possibly timing-critical) reads are allowed.

So, is there anything that actually depends on barriers also
constraining read - or, more likely, read vs. write - order ?
If not, will there be ?

Also, it seems, but is never quite explicitly spelt out, that an
elevator is never really supposed to look for barriers in
rq->flags, but can solely rely on the insertion position as an
indication for barriers. Is this true ?

Thanks,
- Werner

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

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Werner Almesberger wrote:
> I'm working on an elevator with priorities, and I'm wondering what
> semantics are expected from barriers when it comes to reads.
> 
> My problem with read barriers is that they can upset priorities
> quite a bit, by forcing the entire queue to be processed before
> any new (possibly timing-critical) reads are allowed.
> 
> So, is there anything that actually depends on barriers also
> constraining read - or, more likely, read vs. write - order ?
> If not, will there be ?

I don't think a read-barrier currently has a meaning. A write barrier
will force ordering for later reads too, of course.

> Also, it seems, but is never quite explicitly spelt out, that an
> elevator is never really supposed to look for barriers in
> rq->flags, but can solely rely on the insertion position as an
> indication for barriers. Is this true ?

It can't, the insert position doesn't tell you whether it's a barrier or
not. You have to check ->flags for that.

-- 
Jens Axboe

Re: barriers vs. reads

[Werner Almesberger]

Jens Axboe wrote:
> I don't think a read-barrier currently has a meaning. A write barrier
> will force ordering for later reads too, of course.

That's one of the problem spots with priorities: if there are a
lot of writes in the queue, high-priority reads will be delayed
for a long time.

But do we have cases where reads must not cross write barriers ?

> It can't, the insert position doesn't tell you whether it's a barrier or
> not. You have to check ->flags for that.

Yet deadline, AS, and CFQ don't do any such check :-)

- Werner

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

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Werner Almesberger wrote:
> Jens Axboe wrote:
> > I don't think a read-barrier currently has a meaning. A write barrier
> > will force ordering for later reads too, of course.
> 
> That's one of the problem spots with priorities: if there are a
> lot of writes in the queue, high-priority reads will be delayed
> for a long time.

If there are lots of barrier writes, you mean?

> But do we have cases where reads must not cross write barriers ?

To me, it's the expected behaviour. If you issue a barrier write, a read
issued later should not be able to fetch old data.

> > It can't, the insert position doesn't tell you whether it's a barrier or
> > not. You have to check ->flags for that.
> 
> Yet deadline, AS, and CFQ don't do any such check :-)

Hmm? Recently this was moved into __elv_add_request() to make sure that
a barrier always implies ELEVATOR_INSERT_BACK so these checks were
removed. deadline still has it though:

        /* barriers must flush the reorder queue */
        if (unlikely(rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)
                        && where == ELEVATOR_INSERT_SORT))
                where = ELEVATOR_INSERT_BACK;

this can be removed now, though. So it's definitely there, if you are
using a recent kernel you can assume that INSERT_BACK implies a barrier.

-- 
Jens Axboe

Re: barriers vs. reads

[Werner Almesberger]

Jens Axboe wrote:
> If there are lots of barrier writes, you mean?

If there are a lot of writes before the barrier. Then the reads
after the barrier have to wait for all these writes to complete.
Of course, things get even worse if you have a lot of barriers,
in addition to there being lots of writes.

> To me, it's the expected behaviour. If you issue a barrier write, a read
> issued later should not be able to fetch old data.

... which pretty much kills the idea of short predictable
queuing delays :-(

> Hmm? Recently this was moved into __elv_add_request()

Ah, okay, different definition of where the elevator starts ;-)
Yes, I saw that.

BTW, in what cases would ELEVATOR_INSERT_FRONT combined with
a barrier make sense ?

- Werner

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

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Werner Almesberger wrote:
> Jens Axboe wrote:
> > If there are lots of barrier writes, you mean?
> 
> If there are a lot of writes before the barrier. Then the reads
> after the barrier have to wait for all these writes to complete.
> Of course, things get even worse if you have a lot of barriers,
> in addition to there being lots of writes.

There's nothing you can do about that, in my opinion. Barriers are bad
for io scheduler performance, that's a given.

> > To me, it's the expected behaviour. If you issue a barrier write, a read
> > issued later should not be able to fetch old data.
> 
> ... which pretty much kills the idea of short predictable
> queuing delays :-(

So you can't support guarenteed low delays with lots of writes and
barriers, big deal. If you need hard guarantees, you need to tailor the
environment. IMHO this is no different than the regular linux code base
not supporting hard realtime processing.

> > Hmm? Recently this was moved into __elv_add_request()
> 
> Ah, okay, different definition of where the elevator starts ;-)
> Yes, I saw that.
> 
> BTW, in what cases would ELEVATOR_INSERT_FRONT combined with
> a barrier make sense ?

It wouldn't really, INSERT_BACK is the only one that really makes sense.
But if you do an elv_requeue_request() (ide barrier does this) to
reinsert a barrier, it would have the barrier bit set but need to go to
the front anyways. SCSI does it too, come to think of it.

-- 
Jens Axboe

Re: barriers vs. reads

[Jamie Lokier]

Jens Axboe wrote:
> > But do we have cases where reads must not cross write barriers ?
> 
> To me, it's the expected behaviour. If you issue a barrier write, a read
> issued later should not be able to fetch old data.

Two things:

   1. A read _which doesn't overlap writes before the barrier_
      should be ok before the barrier with no visible change.

      So, look at the block numbers and permit reordering if there's
      no overlap.  This reordering is semantically invisible.

   2. Other than O_DIRECT, can the I/O subsystem issue reads that
      overlap writes in flight?  Surely that never occurs?

      If it never occurs, then reads can be safely moved before write
      barriers without looking at block numbers.

-- Jamie

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Jamie Lokier wrote:
> Jens Axboe wrote:
> > > But do we have cases where reads must not cross write barriers ?
> > 
> > To me, it's the expected behaviour. If you issue a barrier write, a read
> > issued later should not be able to fetch old data.
> 
> Two things:
> 
>    1. A read _which doesn't overlap writes before the barrier_
>       should be ok before the barrier with no visible change.
> 
>       So, look at the block numbers and permit reordering if there's
>       no overlap.  This reordering is semantically invisible.

You mean a read that doesn't contain sectors that overlap with the
barrier writes? Yes that would be fine.

It's easier said than done, though. Current io schedulers don't handle
barriers in a very fast fashion - they push all pending requests from
the internal sorted tree to the dispatch list, the latter which is
always accessed in FIFO like fashion (io scheduler adds to tail, driver
eats from the head). So if you wanted to optimize this, that has to be
changed.

>    2. Other than O_DIRECT, can the I/O subsystem issue reads that
>       overlap writes in flight?  Surely that never occurs?

No, it can only happen for reads that don't go through the page cache.

>       If it never occurs, then reads can be safely moved before write
>       barriers without looking at block numbers.

It can happen with direct io of any sort, the solution has to take this
into account. That's why we currently have handling for rbtree aliases
as well.

-- 
Jens Axboe

Re: barriers vs. reads

[Bryan Henderson]

>>    2. Other than O_DIRECT, can the I/O subsystem issue reads that
>>       overlap writes in flight?  Surely that never occurs?
>
>No, it can only happen for reads that don't go through the page cache.
>
>>       If it never occurs, then reads can be safely moved before write
>>       barriers without looking at block numbers.
>
>It can happen with direct io of any sort, the solution has to take this
>into account. That's why we currently have handling for rbtree aliases
>as well.

Are you saying that if Sector A contains "foo", and I do a 
__make_request(Write, Sector A, "bar") and then a __make_request(Read, 
Sector A), the read might read "foo"?  Assuming no barriers.

As I understand it, the topic of discussion is completely outside the 
realm of the page cache and open() flags -- it's all down below that.

--
Bryan Henderson                          IBM Almaden Research Center
San Jose CA                              Filesystems

Re: barriers vs. reads

[Werner Almesberger]

Jamie Lokier wrote:
>    1. A read _which doesn't overlap writes before the barrier_
>       should be ok before the barrier with no visible change.

Ah, that's an excellent point. Thanks !

- Werner

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

Re: barriers vs. reads

[Werner Almesberger]

Jens Axboe wrote:
> It can happen with direct io of any sort, the solution has to take this
> into account. That's why we currently have handling for rbtree aliases
> as well.

How well is this actually supposed to work ? When reading what
as-iosched does, I was left with the impression that you could
construct a set of partially overlapping requests that doesn't
get sorted in FIFO order.

I haven't tried to feed as-iosched such a request mix, though,
so maybe I'm wrong.

(For partially overlapping requests, it may actually be nice
to be able to break them into multiple parts, and queue them
separately. Particularly if they also come with distinct
priorities.)

- Werner

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

RE: barriers vs. reads

[Guy]

Maybe I am missing something.

A read that does not overlap a write could be moved up, regardless of
barriers.

A read that does overlap a write could be moved up to the write, but not
before it, regardless of barriers.

Writes that overlap should be written in order!  Or corrupt data!

Guy

-----Original Message-----
From: linux-fsdevel-owner@vger.kernel.org
[mailto:linux-fsdevel-owner@vger.kernel.org] On Behalf Of Werner Almesberger
Sent: Tuesday, June 22, 2004 2:46 PM
To: Jamie Lokier
Cc: Jens Axboe; linux-fsdevel@vger.kernel.org
Subject: Re: barriers vs. reads

Jamie Lokier wrote:
>    1. A read _which doesn't overlap writes before the barrier_
>       should be ok before the barrier with no visible change.

Ah, that's an excellent point. Thanks !

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: barriers vs. reads

[Jamie Lokier]

Werner Almesberger wrote:
> (For partially overlapping requests, it may actually be nice
> to be able to break them into multiple parts, and queue them
> separately. Particularly if they also come with distinct
> priorities.)

If there's a read which depends on a prior write, doesn't it make more
sense to just copy the data in memory for the parts which overlap?

If you do that, then you can service all high priority reads properly:
those that don't overlap can cross write barriers, and those that do
overlap can be copied in memory immediately.

There may be a case for forcing a direct read for programs which check
storage data integrity, although probably not even then is it useful.
(A program that wants to write some data and then read using direct
I/O will call write(), _wait_ until that returns after committing the
data, and then call read()).

Even if the current behaviour of requiring a device read after the
barrier must remain for ordinary direct I/O, it isn't required for
requests marked as "high-priority I/O".

-- Jamie

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Bryan Henderson wrote:
> >>    2. Other than O_DIRECT, can the I/O subsystem issue reads that
> >>       overlap writes in flight?  Surely that never occurs?
> >
> >No, it can only happen for reads that don't go through the page cache.
> >
> >>       If it never occurs, then reads can be safely moved before write
> >>       barriers without looking at block numbers.
> >
> >It can happen with direct io of any sort, the solution has to take this
> >into account. That's why we currently have handling for rbtree aliases
> >as well.
> 
> Are you saying that if Sector A contains "foo", and I do a 
> __make_request(Write, Sector A, "bar") and then a __make_request(Read, 
> Sector A), the read might read "foo"?  Assuming no barriers.

Well no, even for direct io we maintain ordering if you hit an alias.
See cfq_add_crq_rb() in cfq-iosched.c for example. AS handles it
differently, but result is the same. At least the io is issued in that
order, so if the underlying storage hardware doesn't mess it up, there
is no problem.

If you have overlapping requests, then you could get into serious
trouble. You should not do that.

> As I understand it, the topic of discussion is completely outside the 
> realm of the page cache and open() flags -- it's all down below that.

The page cache will make sure don't see "foo", since you'll wait for the
page to unlocked at the end of io. The above description is only valid
for direct io, this is where the alias handling works.

-- 
Jens Axboe

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Werner Almesberger wrote:
> Jens Axboe wrote:
> > It can happen with direct io of any sort, the solution has to take this
> > into account. That's why we currently have handling for rbtree aliases
> > as well.
> 
> How well is this actually supposed to work ? When reading what
> as-iosched does, I was left with the impression that you could
> construct a set of partially overlapping requests that doesn't
> get sorted in FIFO order.

Overlapping requests are only detected if they start at the same
sector.

The mechanism is just there because of the data structure use, Linux has
never made any effort to guard against this outside of the page cache
context. If you issue direct io that overlaps, you are providing your
own rope.

> I haven't tried to feed as-iosched such a request mix, though,
> so maybe I'm wrong.
> 
> (For partially overlapping requests, it may actually be nice
> to be able to break them into multiple parts, and queue them
> separately. Particularly if they also come with distinct
> priorities.)

Bad idea, unless you have zero setup overhead for the hardware issued
commands. Linux will also attempt to remerge these requests when it
later discovers they are adjacent. You can block this by disallowing
merging of request with different priorities, but I really don't see why
you'd want to do that. It would be a net loss in the end anyways.

-- 
Jens Axboe

Re: barriers vs. reads

[Werner Almesberger]

Jens Axboe wrote:
> Overlapping requests are only detected if they start at the same
> sector.
> 
> The mechanism is just there because of the data structure use, [...]

So even the special handling of requests that start with the
same sector isn't required, and shouldn't be depended on, right ?

> Bad idea, unless you have zero setup overhead for the hardware issued
> commands. Linux will also attempt to remerge these requests when it
> later discovers they are adjacent. You can block this by disallowing
> merging of request with different priorities, but I really don't see why
> you'd want to do that. It would be a net loss in the end anyways.

The issue is that you may get large requests, in the middle of
which a single page gets a higher priority, e.g. because the
large request comes from a low-priority copy operation, and
there's a high-priority reader concurrently working on the
same file.

In this case, the high-priority reader either has to wait for
the whole low-priority request to crawl to the head of the queue
(probably missing the deadline of the high-priority read), or we
could take the request and raise its priority, giving our
low-priority reader a nice boost. The latter isn't so bad if it
happens every once in a while, but someone may figure out how to
do this repeatedly, throwing off our bandwidth calculations.

- Werner

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

Re: barriers vs. reads

[Werner Almesberger]

Jamie Lokier wrote:
> If there's a read which depends on a prior write, doesn't it make more
> sense to just copy the data in memory for the parts which overlap?

Probably. In this case, we'd have to fragment the read request
into the part that's handled through this copy operation, and
the 0-2 parts that need to come from disk.

- Werner

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

Re: barriers vs. reads

[Jamie Lokier]

Werner Almesberger wrote:
> > Bad idea, unless you have zero setup overhead for the hardware issued
> > commands. Linux will also attempt to remerge these requests when it
> > later discovers they are adjacent. You can block this by disallowing
> > merging of request with different priorities, but I really don't see why
> > you'd want to do that. It would be a net loss in the end anyways.
> 
> The issue is that you may get large requests, in the middle of
> which a single page gets a higher priority, e.g. because the
> large request comes from a low-priority copy operation, and
> there's a high-priority reader concurrently working on the
> same file.
> 
> In this case, the high-priority reader either has to wait for
> the whole low-priority request to crawl to the head of the queue
> (probably missing the deadline of the high-priority read), or we
> could take the request and raise its priority, giving our
> low-priority reader a nice boost. The latter isn't so bad if it
> happens every once in a while, but someone may figure out how to
> do this repeatedly, throwing off our bandwidth calculations.

That's fine for a device with fast data transfer and slow seek times.
But for a device with slow data transfer (e.g. nbd to a remote disk),
you'd want to split the request for sure.

-- Jamie

Re: barriers vs. reads

[Jens Axboe]

On Tue, Jun 22 2004, Werner Almesberger wrote:
> Jens Axboe wrote:
> > Overlapping requests are only detected if they start at the same
> > sector.
> > 
> > The mechanism is just there because of the data structure use, [...]
> 
> So even the special handling of requests that start with the
> same sector isn't required, and shouldn't be depended on, right ?

Correct, it's just a side effect of the rbtree. 2.4 never tried to do
anything about it.

> > Bad idea, unless you have zero setup overhead for the hardware issued
> > commands. Linux will also attempt to remerge these requests when it
> > later discovers they are adjacent. You can block this by disallowing
> > merging of request with different priorities, but I really don't see why
> > you'd want to do that. It would be a net loss in the end anyways.
> 
> The issue is that you may get large requests, in the middle of
> which a single page gets a higher priority, e.g. because the
> large request comes from a low-priority copy operation, and
> there's a high-priority reader concurrently working on the
> same file.
> 
> In this case, the high-priority reader either has to wait for
> the whole low-priority request to crawl to the head of the queue
> (probably missing the deadline of the high-priority read), or we
> could take the request and raise its priority, giving our
> low-priority reader a nice boost. The latter isn't so bad if it
> happens every once in a while, but someone may figure out how to
> do this repeatedly, throwing off our bandwidth calculations.
> 

I see your point. Sounds like you have to be careful with request
allocations once a single request suddenly needs 2 more request slots
due to splitting (livelock country).

-- 
Jens Axboe

Re: barriers vs. reads

[Bryan Henderson]

>> Are you saying that if Sector A contains "foo", and I do a 
>> __make_request(Write, Sector A, "bar") and then a __make_request(Read, 
>> Sector A), the read might read "foo"?  Assuming no barriers.
>
>Well no, even for direct io we maintain ordering if you hit an alias.
>...
>If you have overlapping requests, then you could get into serious
>trouble. You should not do that.

What is an alias, and how is it different from an overlap?

Also:  The question is about the block layer, but you answer in terms of 
direct I/O.  Does __make_request() know what direct I/O is?  I thought it 
just did I/O for I/O's sake.

>The page cache will make sure don't see "foo", since you'll wait for the
>page to unlocked at the end of io.

If it's a page cache page, the point is moot because the elevator would 
never see the sequence of requests in question.  But my question is about 
the general case, with no assumptions about who is calling 
__make_request() and why.

Re: barriers vs. reads

[Jens Axboe]

On Wed, Jun 23 2004, Bryan Henderson wrote:
> >> Are you saying that if Sector A contains "foo", and I do a 
> >> __make_request(Write, Sector A, "bar") and then a __make_request(Read, 
> >> Sector A), the read might read "foo"?  Assuming no barriers.
> >
> >Well no, even for direct io we maintain ordering if you hit an alias.
> >...
> >If you have overlapping requests, then you could get into serious
> >trouble. You should not do that.
> 
> What is an alias, and how is it different from an overlap?

It's just an internal problem - when you add a request to the rbtree of
the io scheduler, and an existing request with that key (start location)
already exists.

> Also:  The question is about the block layer, but you answer in terms
> of direct I/O.  Does __make_request() know what direct I/O is?  I
> thought it just did I/O for I/O's sake.

The block layer doesn't know and it doesn't care. I answer in terms of
direct IO since that's the only way you'll get a request issued for the
same sector. As mentioned below, the page cache prevents that from
happening.

> >The page cache will make sure don't see "foo", since you'll wait for the
> >page to unlocked at the end of io.
> 
> If it's a page cache page, the point is moot because the elevator would 
> never see the sequence of requests in question.  But my question is about 

Precisely.

> the general case, with no assumptions about who is calling 
> __make_request() and why.

As stated earlier in this thread, the io scheduler makes no real attempt
to cope with this scenario. Users of direct io are expected to
syncronize themselves. It would be pretty silly not to do this, if only
for performance reasons. The fact that the io scheduler catches
"aliases" is not a feature and not something that is really useful in
this respect, since it's only a slight subset of the general problem of
overlapping ios.

-- 
Jens Axboe

Re: barriers vs. reads

[Jamie Lokier]

Bryan Henderson wrote:
> Also:  The question is about the block layer, but you answer in terms of 
> direct I/O.  Does __make_request() know what direct I/O is?  I thought it 
> just did I/O for I/O's sake.
> 
> >The page cache will make sure don't see "foo", since you'll wait for the
> >page to unlocked at the end of io.
> 
> If it's a page cache page, the point is moot because the elevator would 
> never see the sequence of requests in question.  But my question is about 
> the general case, with no assumptions about who is calling 
> __make_request() and why.

This whole thread is asking a simple question: what shall we define
"I/O write barrier" to mean?  Does it force an ordering for reads
after the barrier which overlap writes before the barrier, or not?

We are free to define the answer as "yes" or "no", according to
whichever is more useful.  Or even to define two kinds of barrier, if
that would be useful.  (E.g. I wonder if direct I/O to a file on a
journalled filesystem would need that).

-- Jamie

Re: barriers vs. reads

[Bryan Henderson]

>This whole thread is asking a simple question: what shall we define
>"I/O write barrier" to mean?  Does it force an ordering for reads
>after the barrier which overlap writes before the barrier, or not?
>
>We are free to define the answer as "yes" or "no", according to
>whichever is more useful.  Or even to define two kinds of barrier, if
>that would be useful.

There was a small branch of the thread aimed at clarifying what kind of 
ordering there is independent of barriers, which is crucial to deciding 
what additional ordering a barrier should impose.  The answer to that 
subsidiary question appears to be "none" unless you count a side effect of 
alias handling (and you shouldn't).

This is, incidentally, nonobvious.  I believe in most contexts, when 
people say "elevator algorithm," they're talking about something that 
affects the timing of a stream of disk I/O requests, but not the outcome; 
the outcome is expected to be the same as FIFO regardless of the 
scheduling.  Barriers come into play only when you have timing 
dependencies between two sectors, e.g. when you don't want to wipe 
something out of the journal until _after_ it has been written someplace 
else.  Jens points out that this ideal elevator isn't practical, or 
necessary, in Linux.

--
Bryan Henderson                          IBM Almaden Research Center
San Jose CA                              Filesystems

Re: barriers vs. reads

[Werner Almesberger]

Jamie Lokier wrote:
> This whole thread is asking a simple question: what shall we define
> "I/O write barrier" to mean?  Does it force an ordering for reads
> after the barrier which overlap writes before the barrier, or not?

It's always the simple questions that are the hardest to answer ;-)

So far, we seem to have the following rules (at least for
"barrier-only" barriers. Special requests come with their own
barriers, see below):

 i) write requests may never cross a barrier that separates
    them from other write requests
 ii) a read request R and a write request W may change their
     order (with respect to each other), unless they overlap
     AND are separated by at least one barrier
 iii) in all other cases, requests are free to move about

Rule ii) seems a little tricky. Is there actually a means for
user space to send a barrier, e.g. when doing direct IO ? If
not, the I think only user of ii) would be "direct IO" that
comes from unbuffered file system meta-data and such.

> Or even to define two kinds of barrier, if that would be useful.

I can think of three distinct uses of barriers (but there may
be more):

 1) ensure integrity involving multiple requests
 2) disentangle overlapping requests
 3) make sure special requests (power management or such) don't
    wander off

2) may merit a distinction. E.g. an elevator that automatically
puts overlapping requests in FIFO order (i.e. Bryan's "ideal"
elevator) could ignore this kind of barriers. Barriers of type
3) restricts the move of anything.

Cheers, Werner

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

Re: barriers vs. reads

[Werner Almesberger]

BTW, regarding overlapping requests, I wonder if there's a data
structure that gives O(log requests) or such lookups for ranges.
The best I could spontaneously think of would be
O(new_request_size*log(requests*avg_request_size))
which isn't pretty.

BTW2, is O_DIRECT actually a Linux-only thing, or is there some
ancestor whose semantics we may want to preserve ? I've had a
quick look at POSIX, but they don't seem to have direct IO.

- Werner

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

Re: barriers vs. reads

[Werner Almesberger]

I wrote:
> BTW, regarding overlapping requests, I wonder if there's a data
> structure that gives O(log requests) or such lookups for ranges.

Seem that I've found one that is maybe 2-4 times as expensive as a
single tree. It works as follows: if we have a set of ranges (a,b)
and want to see if any of them overlap with a range (x,y), we
compare the indices of the matches (or almost-matches).

  num_overlaps = |{a : a < y}| - |{b : b <= x}|

"{a : a < y}" is "the set of all a where a < y". "|...|" is the
number of elements in a set.

We could obtain such indices by counting the number of nodes in
each branch of the tree. That's O(1) for all regular tree
operations, and O(log n) for the sum. The index is the size of
all the trees under left branches we haven't taken, plus the
number of nodes we've left through the right branch. If there are
multiple equal entries, we must find the first one.

One problem: I did this mostly by instinct. It seems to work
perfectly, but I can't quite explain why :-(

I put a dirty little program to simulate this on
http://abiss.sourceforge.net/t.tar.gz

- Werner

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

Re: barriers vs. reads

[Herbert Poetzl]

On Thu, Jun 24, 2004 at 12:39:44AM -0300, Werner Almesberger wrote:
> I wrote:
> > BTW, regarding overlapping requests, I wonder if there's a data
> > structure that gives O(log requests) or such lookups for ranges.
> 
> Seem that I've found one that is maybe 2-4 times as expensive as a
> single tree. It works as follows: if we have a set of ranges (a,b)
> and want to see if any of them overlap with a range (x,y), we
> compare the indices of the matches (or almost-matches).
> 
>   num_overlaps = |{a : a < y}| - |{b : b <= x}|
> 
> "{a : a < y}" is "the set of all a where a < y". "|...|" is the
> number of elements in a set.
> 
> We could obtain such indices by counting the number of nodes in
> each branch of the tree. That's O(1) for all regular tree
> operations, and O(log n) for the sum. The index is the size of
> all the trees under left branches we haven't taken, plus the
> number of nodes we've left through the right branch. If there are
> multiple equal entries, we must find the first one.
> 
> One problem: I did this mostly by instinct. It seems to work
> perfectly, but I can't quite explain why :-(

hmm ... there are eight cases how ranges can interact ...

    a     b     		        		a	  b
    |     |			        		|	  |
 1) +-----+       +---------+	       2) +-----+	+---------+
                  |         |	          |	|
		  x         y	          x	y

    a             b		        		a	  b
    |      	  |		        		|	  |
 3) +-------------+---------+	       4) +-------------+---------+
                  |         |	          |		|
		  x         y	          x		y


    a                 b    	        	a		  b
    |                 | 	        	|		  |
 5) +-------------+===+-----+	       6) +-----+========+--------+
                  |         |	          |		 |
		  x         y	          x		 y
	
    a			    b	        	a	 b
    |			    |	        	|	 |
 7) +-----+========+--------+	       8) +-----+========+--------+
          |        |		          |			  |
	  x        y		          x			  y
	

by verifying those eight cases for correctness, you
can conclude, that the sum of N such cases will give
the correct number of overlaps (with a given test
range); verification itself is simple:

case     a<y    b<=x    |{a:a<y}| - |{b:b<= x}|
------+-------+-------+-------------------------
 1)   |  YES  |  YES  |  0
 2)   |  NO   |  NO   |  0
 3)   |  YES  |  YES  |  0
 4)   |  NO   |  NO   |  0
------+-------+-------+-----
 5)   |  YES  |  NO   |  1
 6)   |  YES  |  NO   |  1
 7)   |  YES  |  NO   |  1
 8)   |  YES  |  NO   |  1

HTH,
Herbert

> I put a dirty little program to simulate this on
> http://abiss.sourceforge.net/t.tar.gz
> 
> - Werner
> 
> -- 
>   _________________________________________________________________________
>  / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
> /_http://www.almesberger.net/____________________________________________/
> -
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: barriers vs. reads

[Werner Almesberger]

Herbert Poetzl wrote:
> by verifying those eight cases for correctness, you
> can conclude, that the sum of N such cases will give
> the correct number of overlaps (with a given test
> range); verification itself is simple:

Thanks (very nice drawings, btw.) ! Yes, now that I see it
written down, I also see how we can generalize that to a
proof for any number of (a,b) ranges. Cool !

So this means that we have a solution to detect overlaps
that shouldn't be  significantly slower than, say tree+hash
as used in the anticipatory scheduler. One problem is that
this approach doesn't tell us where the overlapping
requests are, only that there are somewhere out there.

Thanks,
- Werner

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

Re: barriers vs. reads

[Jamie Lokier]

Werner Almesberger wrote:
> I wrote:
> > BTW, regarding overlapping requests, I wonder if there's a data
> > structure that gives O(log requests) or such lookups for ranges.
> 
> Seem that I've found one that is maybe 2-4 times as expensive as a
> single tree. It works as follows: if we have a set of ranges (a,b)
> and want to see if any of them overlap with a range (x,y), we
> compare the indices of the matches (or almost-matches).

Is the prio_tree data structure, the one being used by recent VM work,
which keeps track of ranges, any use?

-- Jamie

Re: barriers vs. reads

[Jamie Lokier]

Werner Almesberger wrote:
>  i) write requests may never cross a barrier that separates
>     them from other write requests
>  ii) a read request R and a write request W may change their
>      order (with respect to each other), unless they overlap
>      AND are separated by at least one barrier
>  iii) in all other cases, requests are free to move about
> 
> Rule ii) seems a little tricky. Is there actually a means for
> user space to send a barrier, e.g. when doing direct IO ? If
> not, the I think only user of ii) would be "direct IO" that
> comes from unbuffered file system meta-data and such.

It should be possible to write a decent filesystem in userspace --
even if it's just for prototyping -- so barriers from userspace should
be offered, eventually.

Note that unbuffered file system meta-data can theoretically overlap
page cache, although it usually doesn't, and a filesystem could easily
set a flag to say that it doesn't ever.

Think of the experimental modifications to ext3 to allow inodes to be
allocated in a file.  That means blocks are changing their meaning
from being file blocks to inode blocks or vice versa -- and both I/Os
could conceivably be in flight at the same time.

-- Jamie

Re: barriers vs. reads

[Christoph Hellwig]

On Thu, Jun 24, 2004 at 02:43:07PM +0100, Jamie Lokier wrote:
> Think of the experimental modifications to ext3 to allow inodes to be
> allocated in a file.

Long time ago  Kristian Köhntoppp did the for ext2 for his Diploma Thesis [1]

[1] http://kris.koehntopp.de/artikel/diplom/ (Warning: German)
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: barriers vs. reads

[Steve Lord]

Werner Almesberger wrote:
> BTW, regarding overlapping requests, I wonder if there's a data
> structure that gives O(log requests) or such lookups for ranges.
> The best I could spontaneously think of would be
> O(new_request_size*log(requests*avg_request_size))
> which isn't pretty.
> 
> BTW2, is O_DIRECT actually a Linux-only thing, or is there some
> ancestor whose semantics we may want to preserve ? I've had a
> quick look at POSIX, but they don't seem to have direct IO.

Irix has O_DIRECT, Solaris has something too, but it is not
in the posix specs. Cray Unicos is the oldest implementation I came
across.

Irix explicitly lets multiple readers and writers into a file
at once with O_DIRECT. The assumption being that the application
which does this is doing its own coordination and will not
shoot itself in the foot.

Steve Lord

Re: barriers vs. reads

[Werner Almesberger]

Jamie Lokier wrote:
> Is the prio_tree data structure, the one being used by recent VM work,
> which keeps track of ranges, any use?

Hmm, they deliver exactly the data we need. That's great. Unlike
rb-trees, they also aren't balanced, and thus have a worst-case
O(log n) term with "log n" = sizeof(sector_t)*8 for simple
lookups. Furthermore, they have a scary worst-case insertion
time of O((log n)^2).

With rb-trees, we get a mere O(log nr_requests) for lookups. So
that's A*32 vs. B*7 using all-default 2.6.7 on ia32. Insertion
has the same typical cost, and A*1024 vs. B*7 worst-case. A and B
are implementation-specific per-operation cost factors.

But yes, they look very interesting ...

Thanks,
- Werner

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

Re: barriers vs. reads

[Werner Almesberger]

Jamie Lokier wrote:
> It should be possible to write a decent filesystem in userspace --
> even if it's just for prototyping -- so barriers from userspace should
> be offered, eventually.

Yes, I suppose also databases would want barriers. My question
was more in the direction of "what might we break if we change
some of the rules now ?".

> Think of the experimental modifications to ext3 to allow inodes to be
> allocated in a file.  That means blocks are changing their meaning
> from being file blocks to inode blocks or vice versa -- and both I/Os
> could conceivably be in flight at the same time.

Oh, that one's evil !

- Werner

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