Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

David S. Miller (davem@redhat.com)
Sat, 31 May 2003 01:12:10 -0700 (PDT)


From: Willy TARREAU <willy@w.ods.org>
Date: Sat, 31 May 2003 10:02:05 +0200

With this simple change, jhash_mix is *exactly* three times faster
for me on athlon-xp, whatever gcc I use (2.95.3 or 3.2.3), on the
following do_hash() function, and about 40% faster when used on
local variables.

Interesting :-)

This function is 189 bytes long, and takes about 72 cycles to
complete with the original macro, and is now 130 bytes long for
about 24 cycles, which means about 1.5 operation/cycle... not bad :-)

__jhash_mix takes ~23 cycles on sparc64 in the original version for
me. I get the same measurement for your version. Maybe your gcc
version just stinks :-(

Oh wait, yes, it's the memory operations it can't eliminate.
It can't do that because it has no idea whether certain pointers
alias or not. (ie. it doesn't know whether 'a' and 'b' point
to the same value)

Since all the networking versions work on local variables, in
2.4.x it shouldn't matter performance wise.

You'll note that my updated dcache jenkins patch for 2.5.x
brought the hash->words[] variables into locals before running
__jhash_mix() on it. So it shouldn't matter there either.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/