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

[Herbert Xu <herbert@xxxxxxxxxxxxxxxxxxx>]

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