LinuxLists.cc - Linux 2.4.21-rc6

2003-05-29 19:00:05

by Marcelo Tosatti

[permalink] [raw]

Subject: -rc7 Re: Linux 2.4.21-rc6

On Thu, 29 May 2003, Georg Nikodym wrote:

> On Wed, 28 May 2003 21:55:39 -0300 (BRT)
> Marcelo Tosatti <[email protected]> wrote:
>
> > Here goes -rc6. I've decided to delay 2.4.21 a bit and try Andrew's
> > fix for the IO stalls/deadlocks.
>
> While others may be dubious about the efficacy of this patch, I've been
> running -rc6 on my laptop now since sometime last night and have seen
> nothing odd.
>
> In case anybody cares, I'm using both ide and a ieee1394 (for a large
> external drive [which implies scsi]) and I do a _lot_ of big work with
> BK so I was seeing the problem within hours previously.

Great!

-rc7 will have to be released due to some problems :(

2003-05-29 19:44:22

On Wednesday 04 June 2003 00:59, Marc-Christian Petersen wrote:
> On Tuesday 03 June 2003 18:30, Michael Frank wrote:
> well, very easy one:
>
> dd if=/dev/zero of=/home/largefile bs=16384 count=131072

Got that already - more flexible:

http://www.ussg.iu.edu/hypermail/linux/kernel/0305.3/1291.html

Breaks anything >= 2.4.19 < rc6 in no time.

We need more - any ideas

Reagards
Michael

2003-06-03 17:48:49

On Thu, 2003-06-26 at 09:04, Nick Piggin wrote:

> >One of the things I tried in this area was basically queue ownership.
> >When each process woke up, he was given strict ownership of the queue
> >and could submit up to N number of requests. One process waited for
> >ownership in a yield loop for a max limit of a certain number of
> >jiffies, all the others waited on the request queue.
> >
>
> Not sure exactly what you mean by one process waiting for ownership
> in a yield loop, but why don't you simply allow the queue "owner" to
> submit up to a maximum of N requests within a time limit. Once either
> limit expires (or, rarely, another might become owner -) the process
> would just be put to sleep by the normal queue_full mechanism.
>

You need some way to wakeup the queue after that time limit has expired,
in case the owner never submits another request. This can either be a
timer or a process in a yield loop. Given that very short expire time I
set (10 jiffies), I went for the yield loop.

> >
> >It generally increased the latency in __get_request wait by a multiple
> >of N. I didn't keep it because the current patch is already full of
> >subtle interactions, I didn't want to make things more confusing than
> >they already were ;-)
> >
>
> Yeah, something like that. I think that in a queue full situation,
> the processes are wanting to submit more than 1 request though. So
> the better thoughput you can achieve by batching translates to
> better effective throughput. Read my recent debate with Andrea
> about this though - I couldn't convince him!
>

Well, it depends ;-) I think we've got 3 basic kinds of procs during a
q->full condition:

1) wants to submit lots of somewhat contiguous io
2) wants to submit a single io
3) wants to submit lots of random io

>From a throughput point of view, we only care about giving batch
ownership to #1. giving batch ownership to #3 will help reduce context
switches, but if it helps throughput than the io wasn't really random
(you've got a good point about locality below, drive write caches make a
huge difference there).

The problem I see in 2.4 is the elevator can't tell any of these cases
apart, so any attempt at batch ownership is certain to be wrong at least
part of the time.

> I have seen much better maximum latencies, 2-3 times the
> throughput, and an order of magnitude less context switching on
> many threaded tiobench write loads when using batching.
>
> In short, measuring get_request latency won't give you the full
> story.
>

Very true. But get_request latency is the minimum amount of time a
single read is going to wait (in 2.4.x anyway), and that is what we need
to focus on when we're trying to fix interactive performance.

> >
> >The real problem with this approach is that we're guessing about the
> >number of requests a given process wants to submit, and we're assuming
> >those requests are going to be highly mergable. If the higher levels
> >pass these hints down to the elevator, we should be able to do a better
> >job of giving both low latency and high throughput.
> >
>
> No, the numbers (batch # requests, batch time) are not highly scientific.
> Simply when a process wakes up, we'll let them submit a small burst of
> requests before they go back to sleep. Now in 2.5 (mm) we can cheat and
> make this more effective, fair, and without possible missed wakes because
> io contexts means that multiple processes can be batching at the same
> time, and dynamically allocated requests means it doesn't matter if we
> go a bit over the queue limit.
>

I agree 2.5 has a lot more room for the contexts to be effective, and I
think they are a really good idea.

> I think a decent solution for 2.4 would be to simply have the one queue
> owner, but he allowed the queue to fall below the batch limit, wake
> someone else and make them the owner. It can be a bit less fair, and
> it doesn't work across queues, but they're less important cases.
>
> >
> >Between bios and the pdflush daemons, I think 2.5 is in pretty good
> >shape to do what we need. I'm not 100% sure we need batching when the
> >requests being submitted are not highly mergable, but I haven't put lots
> >of thought into that part yet.
> >
>
> No, there are a couple of problems here.
> First, good locality != sequential. I saw tiobench 256 random write
> throughput _doubled_ because each process is writing within its own
> file.
>
> Second, mergeable doesn't mean anything if your request size only
> grows to say 128KB (IDE). I saw tiobench 256 sequential writes on IDE
> go from ~ 25% peak throughput to ~70% (4.85->14.11 from 20MB/s disk)

Well, play around with raw io, my box writes at roughly disk speed with
128k synchronous requests (contiguous writes).

> Third, context switch rate. In the latest IBM regression tests,
> tiobench 64 on ext2, 8xSMP (so don't look at throughput!), average
> cs/s was about 2500 with mainline (FIFO request allocation), and
> 140 in mm (batching allocation). So nearly 20x better. This might
> not be due to batching alone, but I didn't see any other obvious
> change in mm.
>

Makes sense.

> >
> >Anyway for 2.4 I'm not sure there's much more we can do. I'd like to
> >add tunables to the current patch, so userland can control the max io in
> >flight and a simple toggle between throughput mode and latency mode on a
> >per device basis. It's not perfect but should tide us over until 2.6.
> >
> >
>
> The changes do seem to be a critical fix due to the starvation issue,
> but I'm worried that they take a big step back in performance under
> high disk load. I found my FIFO mechanism to be unacceptably slow for
> 2.5.

Me too, but I'm not sure how to fix it other than a userspace knob to
turn off the q->full checks for server workloads. Andrea's
elevator-lowlatency alone has pretty good throughput numbers, since it
still allows request stealing. Its get_request_wait latency numbers
aren't horrible either, it only suffers in a few corner cases.

But, if someone wants to play with this more, I've attached a quick
remerge of my batch ownership code. I made a read and write owner, so
that a reader doing a single request doesn't grab ownership and make all
the writes wait.

It does make throughput better overall, and it also makes latencies
worse overall. We'll probably get similar results just by disabling
q->full in io-stalls-7, but the batch ownership does a better job of
limiting get_request latencies at a fixed (although potentially large)
number.

lat-stat-5.diff goes on top of io-stalls-7.diff from yesterday
batch_owner.diff goes on top of lat-stat-5.diff.

-chris

Attachments:

batch_owner.diff (4.40 kB)
lat-stat-5.diff (4.37 kB)
Download all attachments

2003-06-27 01:18:00

by Nick Piggin

[permalink] [raw]

Subject: Re: [PATCH] io stalls

Chris Mason wrote:

>On Thu, 2003-06-26 at 09:04, Nick Piggin wrote:
>
>
>>>One of the things I tried in this area was basically queue ownership.
>>>When each process woke up, he was given strict ownership of the queue
>>>and could submit up to N number of requests. One process waited for
>>>ownership in a yield loop for a max limit of a certain number of
>>>jiffies, all the others waited on the request queue.
>>>
>>>
>>Not sure exactly what you mean by one process waiting for ownership
>>in a yield loop, but why don't you simply allow the queue "owner" to
>>submit up to a maximum of N requests within a time limit. Once either
>>limit expires (or, rarely, another might become owner -) the process
>>would just be put to sleep by the normal queue_full mechanism.
>>
>>
>
>You need some way to wakeup the queue after that time limit has expired,
>in case the owner never submits another request. This can either be a
>timer or a process in a yield loop. Given that very short expire time I
>set (10 jiffies), I went for the yield loop.
>
>
>>>It generally increased the latency in __get_request wait by a multiple
>>>of N. I didn't keep it because the current patch is already full of
>>>subtle interactions, I didn't want to make things more confusing than
>>>they already were ;-)
>>>
>>>
>>Yeah, something like that. I think that in a queue full situation,
>>the processes are wanting to submit more than 1 request though. So
>>the better thoughput you can achieve by batching translates to
>>better effective throughput. Read my recent debate with Andrea
>>about this though - I couldn't convince him!
>>
>>
>
>Well, it depends ;-) I think we've got 3 basic kinds of procs during a
>q->full condition:
>
>1) wants to submit lots of somewhat contiguous io
>2) wants to submit a single io
>3) wants to submit lots of random io
>
>>From a throughput point of view, we only care about giving batch
>ownership to #1. giving batch ownership to #3 will help reduce context
>switches, but if it helps throughput than the io wasn't really random
>(you've got a good point about locality below, drive write caches make a
>huge difference there).
>
>The problem I see in 2.4 is the elevator can't tell any of these cases
>apart, so any attempt at batch ownership is certain to be wrong at least
>part of the time.
>

I think though, for fairness, if we allow one to submit a batch
of requests, we have to give that opportunity to the others.
And yeah, it does reduce context switches, and it does improve
throughput for "random" localised IO.

>
>
>>I have seen much better maximum latencies, 2-3 times the
>>throughput, and an order of magnitude less context switching on
>>many threaded tiobench write loads when using batching.
>>
>>In short, measuring get_request latency won't give you the full
>>story.
>>
>>
>
>Very true. But get_request latency is the minimum amount of time a
>single read is going to wait (in 2.4.x anyway), and that is what we need
>to focus on when we're trying to fix interactive performance.
>

The read situation is different to write. To fill the read queue,
you need queue_nr_requests / 2-3 (for readahead) reading processes
to fill the queue, more if the reads are random.
If this kernel is being used interactively, its not our fault we
might not give quite as good interactive performance. I'm sure
the fileserver admin would rather take the tripled bandwidth ;)

That said, I think a lot of interactive programs will want to do
more than 1 request at a time anyway.

>
>>>The real problem with this approach is that we're guessing about the
>>>number of requests a given process wants to submit, and we're assuming
>>>those requests are going to be highly mergable. If the higher levels
>>>pass these hints down to the elevator, we should be able to do a better
>>>job of giving both low latency and high throughput.
>>>
>>>
>>No, the numbers (batch # requests, batch time) are not highly scientific.
>>Simply when a process wakes up, we'll let them submit a small burst of
>>requests before they go back to sleep. Now in 2.5 (mm) we can cheat and
>>make this more effective, fair, and without possible missed wakes because
>>io contexts means that multiple processes can be batching at the same
>>time, and dynamically allocated requests means it doesn't matter if we
>>go a bit over the queue limit.
>>
>>
>
>I agree 2.5 has a lot more room for the contexts to be effective, and I
>think they are a really good idea.
>
>
>>I think a decent solution for 2.4 would be to simply have the one queue
>>owner, but he allowed the queue to fall below the batch limit, wake
>>someone else and make them the owner. It can be a bit less fair, and
>>it doesn't work across queues, but they're less important cases.
>>
>>
>>>Between bios and the pdflush daemons, I think 2.5 is in pretty good
>>>shape to do what we need. I'm not 100% sure we need batching when the
>>>requests being submitted are not highly mergable, but I haven't put lots
>>>of thought into that part yet.
>>>
>>>
>>No, there are a couple of problems here.
>>First, good locality != sequential. I saw tiobench 256 random write
>>throughput _doubled_ because each process is writing within its own
>>file.
>>
>>Second, mergeable doesn't mean anything if your request size only
>>grows to say 128KB (IDE). I saw tiobench 256 sequential writes on IDE
>>go from ~ 25% peak throughput to ~70% (4.85->14.11 from 20MB/s disk)
>>
>
>Well, play around with raw io, my box writes at roughly disk speed with
>128k synchronous requests (contiguous writes).
>

Yeah, I'm not talking about request overhead - I think a 128K sized
request is just fine. But when there are 256 threads writing, with
FIFO method, 128 threads will each have 1 request in the queue. If
they are sequential writers, each request will probably be 128K.
That isn't enough to get good disk bandwidth. The elevator _has_ to
make a suboptimal decision.

With batching, say 8 processes have 16 sequential requests on the
queue each. The elevator can make good choices.

2003-06-27 01:26:44

by Chris Mason

[permalink] [raw]

Subject: Re: [PATCH] io stalls

On Thu, 2003-06-26 at 21:21, Nick Piggin wrote:

> >Very true. But get_request latency is the minimum amount of time a
> >single read is going to wait (in 2.4.x anyway), and that is what we need
> >to focus on when we're trying to fix interactive performance.
> >
>
> The read situation is different to write. To fill the read queue,
> you need queue_nr_requests / 2-3 (for readahead) reading processes
> to fill the queue, more if the reads are random.
> If this kernel is being used interactively, its not our fault we
> might not give quite as good interactive performance. I'm sure
> the fileserver admin would rather take the tripled bandwidth ;)
>
> That said, I think a lot of interactive programs will want to do
> more than 1 request at a time anyway.
>

My intuition agrees with yours, but if this is true then andrea's old
elevator-lowlatency patch alone is enough, and we don't need q->full at
all. Users continued to complain of bad latencies even with his code
applied.

>From a practical point of view his old code is the same as the batch
wakeup code for get_request latencies and provides good throughput.
There are a few cases where batch wakeup has shorter overall latencies,
but I don't think people were in those heavy workloads while they were
complaining of stalls in -aa.

> >>Second, mergeable doesn't mean anything if your request size only
> >>grows to say 128KB (IDE). I saw tiobench 256 sequential writes on IDE
> >>go from ~ 25% peak throughput to ~70% (4.85->14.11 from 20MB/s disk)
> >>
> >
> >Well, play around with raw io, my box writes at roughly disk speed with
> >128k synchronous requests (contiguous writes).
> >
>
> Yeah, I'm not talking about request overhead - I think a 128K sized
> request is just fine. But when there are 256 threads writing, with
> FIFO method, 128 threads will each have 1 request in the queue. If
> they are sequential writers, each request will probably be 128K.
> That isn't enough to get good disk bandwidth. The elevator _has_ to
> make a suboptimal decision.
>
> With batching, say 8 processes have 16 sequential requests on the
> queue each. The elevator can make good choices.

I agree here too, it just doesn't match the user reports we've been
getting in 2.4 ;-) If 2.5 can dynamically allocate requests now and
then you can get much better results with io contexts/dynamic wakeups,
but I can't see how to make it work in 2.4 without larger backports.

So, the way I see things, we've got a few choices.

1) do nothing. 2.6 isn't that far off.

2) add elevator-lowlatency without q->full. It solves 90% of the
problem

3) add q->full as well and make it the default. Great latencies, not so
good throughput. Add userland tunables so people can switch.

4) back port some larger chunk of 2.5 and find a better overall
solution.

I vote for #3, don't care much if q->full is on or off by default, as
long as we make an easy way for people to set it.

-chris

2003-06-27 08:27:15

by Matthias Andree

[permalink] [raw]

Subject: write-caches, I/O stalls: MUST-FIX (was: [PATCH] io stalls)

On Wed, 25 Jun 2003, Chris Mason wrote:

> I've no preference really. I didn't notice a throughput difference but
> my scsi drives only have 2MB of cache.

You shouldn't be using the drive's write cache in the first place!

The write cache, regardless of ATA or SCSI, can, as far as I know, not
be used safely with any Linux file systems (and my questions whether 2.6
will finally change that went unanswered so far), because the write
reordering the write cache can do can seriously damage file systems,
whether journalling or not.

Please conduct all your tests with write caches turned off because
that's what matters in REAL systems; in that case, these latencies
become a REAL pain in the back because writing is so much slower because
of all the seeks.

Optimizing for write cached behaviour can happen not a single second
before:

1. the file systems know how to queue "ordered tags" in the right places
(write barrier to enforce proper ordering for on-disk consistency,
which I assume will make for a lot of ordered tags for writing to the
journal itself)

2. the device driver knows how to map "ordered tags" to flush or
whatever operations for drives that don't do tagged command queueing
(ATA mostly, or SCSI when TCQ is switched off).

All these "0-bytes in file" problems with XFS, ReiserFS, JFS, ext2 and
ext3 in data=writeback mode happen because the kernel doesn't care about
write ordering, and these broken files are a) occasionally hard to find,
b) another PITA.

I consider proper write ordering and enforcing thereof a MUST-FIX. This
is much more important than getting some extra latencies squished. It
must do the right thing in the first place, and then it can do the right
thing faster.

I am aware that you're not the only person responsible for the state
Linux is in, and I'd like to see the write barriers revived ASAP for at
least ext2/ext3/reiserfs, sym53c8xx, aic7xxx, tmscsim and IDE. I am
sorry not being able to offer any help on that, I'm not acquainted with
the kernel stuff and I can't donate money to anyone for me to do it.

SCNR.

--
Matthias Andree

2003-06-27 09:32:16

by Nick Piggin

[permalink] [raw]

Subject: Re: [PATCH] io stalls

Chris Mason wrote:

>On Thu, 2003-06-26 at 21:21, Nick Piggin wrote:
>
>
>>>Very true. But get_request latency is the minimum amount of time a
>>>single read is going to wait (in 2.4.x anyway), and that is what we need
>>>to focus on when we're trying to fix interactive performance.
>>>
>>>
>>The read situation is different to write. To fill the read queue,
>>you need queue_nr_requests / 2-3 (for readahead) reading processes
>>to fill the queue, more if the reads are random.
>>If this kernel is being used interactively, its not our fault we
>>might not give quite as good interactive performance. I'm sure
>>the fileserver admin would rather take the tripled bandwidth ;)
>>
>>That said, I think a lot of interactive programs will want to do
>>more than 1 request at a time anyway.
>>
>>
>
>My intuition agrees with yours, but if this is true then andrea's old
>elevator-lowlatency patch alone is enough, and we don't need q->full at
>all. Users continued to complain of bad latencies even with his code
>applied.
>

Didn't that still have the starvation issues in get_request that
my patch addressed though? This batching is needed due to the
strict FIFO behaviour that my "q->full" thing did.

>
>>From a practical point of view his old code is the same as the batch
>wakeup code for get_request latencies and provides good throughput.
>There are a few cases where batch wakeup has shorter overall latencies,
>but I don't think people were in those heavy workloads while they were
>complaining of stalls in -aa.
>
>
>>>>Second, mergeable doesn't mean anything if your request size only
>>>>grows to say 128KB (IDE). I saw tiobench 256 sequential writes on IDE
>>>>go from ~ 25% peak throughput to ~70% (4.85->14.11 from 20MB/s disk)
>>>>
>>>>
>>>Well, play around with raw io, my box writes at roughly disk speed with
>>>128k synchronous requests (contiguous writes).
>>>
>>>
>>Yeah, I'm not talking about request overhead - I think a 128K sized
>>request is just fine. But when there are 256 threads writing, with
>>FIFO method, 128 threads will each have 1 request in the queue. If
>>they are sequential writers, each request will probably be 128K.
>>That isn't enough to get good disk bandwidth. The elevator _has_ to
>>make a suboptimal decision.
>>
>>With batching, say 8 processes have 16 sequential requests on the
>>queue each. The elevator can make good choices.
>>
>
>I agree here too, it just doesn't match the user reports we've been
>getting in 2.4 ;-) If 2.5 can dynamically allocate requests now and
>then you can get much better results with io contexts/dynamic wakeups,
>but I can't see how to make it work in 2.4 without larger backports.
>
>So, the way I see things, we've got a few choices.
>
>1) do nothing. 2.6 isn't that far off.
>
>2) add elevator-lowlatency without q->full. It solves 90% of the
>problem
>
>3) add q->full as well and make it the default. Great latencies, not so
>good throughput. Add userland tunables so people can switch.
>
>4) back port some larger chunk of 2.5 and find a better overall
>solution.
>
>I vote for #3, don't care much if q->full is on or off by default, as
>long as we make an easy way for people to set it.
>

5) include the "q->full" starvation fix; add the concept of a
queue owner, the batching process.

I'm a bit busy at the moment and so I won't test this, unfortunately.
I would prefer that if something like #5 doesn't get in, then nothing
be done for .22 unless its backed up by a few decent benchmarks. But
its not my call anyway.

Cheers,
Nick

2003-06-27 12:28:12

by Chris Mason

[permalink] [raw]

Subject: Re: [PATCH] io stalls

On Fri, 2003-06-27 at 05:45, Nick Piggin wrote:
> Chris Mason wrote:
> >>>
> >>The read situation is different to write. To fill the read queue,
> >>you need queue_nr_requests / 2-3 (for readahead) reading processes
> >>to fill the queue, more if the reads are random.
> >>If this kernel is being used interactively, its not our fault we
> >>might not give quite as good interactive performance. I'm sure
> >>the fileserver admin would rather take the tripled bandwidth ;)
> >>
> >>That said, I think a lot of interactive programs will want to do
> >>more than 1 request at a time anyway.
> >>
> >>
> >
> >My intuition agrees with yours, but if this is true then andrea's old
> >elevator-lowlatency patch alone is enough, and we don't need q->full at
> >all. Users continued to complain of bad latencies even with his code
> >applied.
> >
>
> Didn't that still have the starvation issues in get_request that
> my patch addressed though? This batching is needed due to the
> strict FIFO behaviour that my "q->full" thing did.
>

Sure, but even though the batch wakeup code didn't have starvation
issues, the overall get_request latency was still high. The end result
was basically the same, without q->full we've got a higher max wait and
a lower average wait. With batch wakeup we've got a higher average
(300-400 jiffies) and a lower max (800-900 jiffies).

Especially for things like directory listings, where 2.4 generally does
io a few blocks at a time, the get_request latency is a big part of the
latency an interactive user sees.

> >So, the way I see things, we've got a few choices.
> >
> >1) do nothing. 2.6 isn't that far off.
> >
> >2) add elevator-lowlatency without q->full. It solves 90% of the
> >problem
> >
> >3) add q->full as well and make it the default. Great latencies, not so
> >good throughput. Add userland tunables so people can switch.
> >
> >4) back port some larger chunk of 2.5 and find a better overall
> >solution.
> >
> >I vote for #3, don't care much if q->full is on or off by default, as
> >long as we make an easy way for people to set it.
> >
>
> 5) include the "q->full" starvation fix; add the concept of a
> queue owner, the batching process.
>

I've tried two different approaches to #5, the first is a just a
batch_owner where other procs are still allowed to grab requests and the
owner was allowed to ignore q->full. The end result was low latencies
but not much better throughput. With a small number of procs, you've
got a good chance bdflush is going to get ownership and the throughput
is pretty good. With more procs the probability of that goes down and
the throughput benefit goes away.

My second attempt was the batch wakeup patch from yesterday. Overall I
don't feel the latencies are significantly better with that patch than
with Andrea's elevator-lowlatency and q->full disabled.

> I'm a bit busy at the moment and so I won't test this, unfortunately.
> I would prefer that if something like #5 doesn't get in, then nothing
> be done for .22 unless its backed up by a few decent benchmarks. But
> its not my call anyway.
>

Andrea's code without q->full is a good starting point regardless. The
throughput is good and the latencies are better overall. q->full is
simple enough that making it available via a tunable is pretty easy. I
really do wish I could make one patch that works well for both, but I've
honestly run out of ideas ;-)

-chris