[PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Eric Dumazet]

[-- Attachment #1: Type: text/plain, Size: 704 bytes --]

On commit 39c90ece7565f5c47110c2fa77409d7a9478bd5b we converted 
rt_check_expire() from softirq to workqueue, allowing the function to perform 
all work it was supposed to do.

When the IP route cache is big, rt_check_expire() can take a long time to run.
(default settings : 20% of the hash table is scanned at each invocation)

Adding cond_resched() helps giving cpu to higher priority tasks if necessary.

Using a "if (need_resched())" test before calling "cond_resched();" is 
necessary to avoid spending too much time doing the resched check.
(My tests gave a time reduction from 88 ms to 25 ms per rt_check_expire() run 
on my i686 test machine)

Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>


[-- Attachment #2: rt_check_expire_resched.patch --]
[-- Type: text/plain, Size: 387 bytes --]

diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index a9471b7..f0b28f9 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -580,6 +580,9 @@ static void rt_check_expire(struct work_struct *work)
 		i = (i + 1) & rt_hash_mask;
 		rthp = &rt_hash_table[i].chain;
 
+		if (need_resched())
+			cond_resched();
+
 		if (*rthp == NULL)
 			continue;
 		spin_lock_bh(rt_hash_lock_addr(i));

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[David Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Wed, 14 Nov 2007 22:34:13 +0100

> On commit 39c90ece7565f5c47110c2fa77409d7a9478bd5b we converted 
> rt_check_expire() from softirq to workqueue, allowing the function to perform 
> all work it was supposed to do.
> 
> When the IP route cache is big, rt_check_expire() can take a long time to run.
> (default settings : 20% of the hash table is scanned at each invocation)
> 
> Adding cond_resched() helps giving cpu to higher priority tasks if necessary.
> 
> Using a "if (need_resched())" test before calling "cond_resched();" is 
> necessary to avoid spending too much time doing the resched check.
> (My tests gave a time reduction from 88 ms to 25 ms per rt_check_expire() run 
> on my i686 test machine)
> 
> Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>

Patch applied, thanks!

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Andi Kleen]

Eric Dumazet <dada1@cosmosbay.com> writes:
>
> Using a "if (need_resched())" test before calling "cond_resched();" is
> necessary to avoid spending too much time doing the resched check.

The only difference between cond_resched() and if (need_resched())
cond_resched() is one function call less and one might_sleep less. If
the might_sleep or the function call are really problems (did you
measure it? -- i doubt it somewhat) then it would be better to fix the
generic code to either inline that or supply a __cond_resched()
without might_sleep.

A cheaper change might have been to just limit the number of buckets
scanned.

-Andi

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Herbert Xu]

Andi Kleen <andi@firstfloor.org> wrote:
>
> A cheaper change might have been to just limit the number of buckets
> scanned.

Actually the whole point of moving it out to process context
is so that we don't have to worry about keeping track of the number
of buckets since deciding on how many buckets to process is black
magic.

IMHO preemption is the answer :) But failing that, a resched
is the next best thing.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Eric Dumazet]

Andi Kleen a écrit :
> Eric Dumazet <dada1@cosmosbay.com> writes:
>> Using a "if (need_resched())" test before calling "cond_resched();" is
>> necessary to avoid spending too much time doing the resched check.
> 
> The only difference between cond_resched() and if (need_resched())
> cond_resched() is one function call less and one might_sleep less. If
> the might_sleep or the function call are really problems (did you
> measure it? -- i doubt it somewhat) then it would be better to fix the
> generic code to either inline that or supply a __cond_resched()
> without might_sleep.

Please note that :

if (need_resched())
     cond_resched();

will re-test need_resched() once cond_resched() is called.

So it may sound unnecessary but in the rt_check_expire() case, with a loop 
potentially doing XXX.XXX iterations, being able to bypass the function call 
is a clear win (in my bench case, 25 ms instead of 88 ms). Impact on I-cache 
is irrelevant here as this rt_check_expires() runs once every 60 sec.

I think the actual cond_resched() is fine for other uses in the kernel, that 
are not used in a loop : In the general case, kernel text size should be as 
small as possible to reduce I-cache pressure, so a function call is better 
than an inline.

> 
> A cheaper change might have been to just limit the number of buckets
> scanned.
> 

Well, not in some particular cases, when there are 3 millions of routes for 
example in the cache. We really want to scan/free them eventually :)

An admin already has the possibility to tune 
/proc/sys/net/ipv4/route/gc_interval and /proc/sys/net/ipv4/route/gc_timeout, 
so on a big cache, it will probably set gc_interval to 1 instead of 60

Next step will be to move "ip route flush cache" and rt_secret_rebuild() 
handling from softirq to process context too, since this still can kill a machine.

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Thu, 15 Nov 2007 08:30:16 +0100

> Eric Dumazet <dada1@cosmosbay.com> writes:
> >
> > Using a "if (need_resched())" test before calling "cond_resched();" is
> > necessary to avoid spending too much time doing the resched check.
> 
> The only difference between cond_resched() and if (need_resched())
> cond_resched() is one function call less and one might_sleep less. If
> the might_sleep or the function call are really problems (did you
> measure it? -- i doubt it somewhat) then it would be better to fix the
> generic code to either inline that or supply a __cond_resched()
> without might_sleep.
> 
> A cheaper change might have been to just limit the number of buckets
> scanned.

Fix up unmap_vmas() too if this is done as it does a similar
need_resched() check too.

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[David Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Thu, 15 Nov 2007 09:25:59 +0100

> Please note that :
> 
> if (need_resched())
>      cond_resched();
> 
> will re-test need_resched() once cond_resched() is called.
> 
> So it may sound unnecessary but in the rt_check_expire() case, with a loop 
> potentially doing XXX.XXX iterations, being able to bypass the function call 
> is a clear win (in my bench case, 25 ms instead of 88 ms). Impact on I-cache 
> is irrelevant here as this rt_check_expires() runs once every 60 sec.

BTW, Eric, initially I was going to recommend that you do
something like:

	if ((goal % SOME_POWER_OF_2) == 0)
		cond_resched();

to mitigate this cost but decided it wasn't worth the bother.

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Andi Kleen]

Eric Dumazet <dada1@cosmosbay.com> writes:

> So it may sound unnecessary but in the rt_check_expire() case, with a
> loop potentially doing XXX.XXX iterations, being able to bypass the
> function call is a clear win (in my bench case, 25 ms instead of 88
> ms). Impact on I-cache is irrelevant here as this rt_check_expires()

Measuring what? And really milli-seconds? The number does not sound plausible 
to me.

-Andi

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Eric Dumazet]

Andi Kleen a écrit :
> Eric Dumazet <dada1@cosmosbay.com> writes:
> 
>> So it may sound unnecessary but in the rt_check_expire() case, with a
>> loop potentially doing XXX.XXX iterations, being able to bypass the
>> function call is a clear win (in my bench case, 25 ms instead of 88
>> ms). Impact on I-cache is irrelevant here as this rt_check_expires()
> 
> Measuring what? And really milli-seconds? The number does not sound plausible 
> to me.

You know Andi, I have seen production servers that needed several seconds to 
perform the flush. When you have millions of entries on this table, can you 
imagine the number of memory transactions (including atomic ops) needed to 
flush them all ?

The 25.000.000 ns and 88.000.000 ns numbers where on an empty table, but large 
(16 MB of memory)

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[Andi Kleen]

> The 25.000.000 ns and 88.000.000 ns numbers where on an empty table, but 
> large (16 MB of memory)

This would mean that cond_resched() needs ~4x as much time as checking
an empty bucket. I find that somewhat hard to believe.

-Andi

Re: [PATCH] NET : rt_check_expire() can take a long time, add a cond_resched()

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Sat, 17 Nov 2007 22:46:40 +0100

> > The 25.000.000 ns and 88.000.000 ns numbers where on an empty table, but 
> > large (16 MB of memory)
> 
> This would mean that cond_resched() needs ~4x as much time as checking
> an empty bucket. I find that somewhat hard to believe.

Based upon Arjan's analysis of the stall created by the
cond_resched() assembler, this doesn't surprise me.

I also don't believe Eric would make up such numbers or
measure them carelessly and then present them as fact.