Messages in this thread | | | Date | Sat, 5 Apr 2003 20:34:18 +0200 | From | Willy Tarreau <> | Subject | Re: Route cache performance under stress |
| |
Hello !
On Sat, Apr 05, 2003 at 06:37:43PM +0200, Florian Weimer wrote: > Please read the following paper: > > <http://www.cs.rice.edu/~scrosby/tr/HashAttack.pdf>
very interesting article.
> Then look at the 2.4 route cache implementation.
Since we need commutative source/dest addresses in many places, the use of a XOR is a common practice. In fact, while working on hash tables a while ago, I found that I could get very good results with something such as :
RND1 = random_generated_at_start_time() ; RND2 = random_generated_at_start_time() ; /* RND2 may be 0 or equal to RND1, all cases seem OK */ x = (RND1 - saddr) ^ (RND1 - daddr) ^ (RND2 + saddr + daddr); reduce(x) ...
With this method, I found no way to guess a predictable (saddr, daddr) couple which gives a same result, and saddr/daddr are still commutative. It resists common cases where saddr=daddr, saddr=~daddr, saddr=-daddr. And *I think* tha the random makes other cases difficult to predict. I'm not specialized in crypto or whatever, so I cannot tell how to generate the best RND1/2, and it's obvious to me that stupid values like 0 or -1 may not help a lot, but this is still better than a trivial saddr ^ daddr, at a very low cost. For example, the x86 encoding of the simple XOR hash would result in : mov saddr, %eax xor daddr, %eax => 2 cycles with result in %eax
The new calculation will look like : mov saddr, %ebx mov daddr, %ecx
lea (%ebx,%ecx,1), %eax neg %ecx
add RND2, %eax // can be omitted if zero add RND1, %ecx
neg %ebx xor %ecx, %eax
add RND1, %ebx xor %ebx, %eax => 5 cycles on dual-pipelines CPUs, result in eax, but uses 2 more regs.
Any comments ?
Regards, Willy
- 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/
| |