netdev
[Top] [All Lists]

Re: [BUG] overflow in net/ipv4/route.c rt_check_expire()

To: Robert Olsson <Robert.Olsson@xxxxxxxxxxx>
Subject: Re: [BUG] overflow in net/ipv4/route.c rt_check_expire()
From: Herbert Xu <herbert@xxxxxxxxxxxxxxxxxxx>
Date: Mon, 4 Apr 2005 07:43:58 +1000
Cc: Eric Dumazet <dada1@xxxxxxxxxxxxx>, davem@xxxxxxxxxxxxx, netdev@xxxxxxxxxxx
In-reply-to: <16976.17876.832677.945878@xxxxxxxxxxxx>
References: <E1DHdsP-0003Lr-00@xxxxxxxxxxxxxxxxxxxxxxxx> <424E641A.1020609@xxxxxxxxxxxxx> <16974.41648.568927.54429@xxxxxxxxxxxx> <20050402193224.GA25157@xxxxxxxxxxxxxxxxxxx> <16976.17876.832677.945878@xxxxxxxxxxxx>
Sender: netdev-bounce@xxxxxxxxxxx
User-agent: Mutt/1.5.6+20040907i
On Sun, Apr 03, 2005 at 09:36:52PM +0200, Robert Olsson wrote:
> 
>  Well I don't see how we detect the need for rehash just be looking
>  at the hash chains. How does the the "lengthening" look like that
>  are allowed to trigger a rehash?

The only way to attack a hash is by exploiting collisions and
create one or more excessively long chains.

This can be detected as follows at each rt hash insertion.  If

(total number of entries in cache >> (hash length - user defined length)) <
current bucket length

is true, then we schedule a rehash/flush.

Hash length is the number of bits in the hash, i.e.,

1 << hash length == number of buckets

I'd suggest a default shift length of 3.  That is, if any individual
chain is growing beyond 8 times the average chain length then we've
got a problem.

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

<Prev in Thread] Current Thread [Next in Thread>