Date: Sat, 08 Dec 2012 13:49:21 +0400 From: "Alexander V. Chernikov" <melifaro@FreeBSD.org> To: "Andrey V. Elsukov" <ae@FreeBSD.org> Cc: freebsd-net@freebsd.org, freebsd-ipfw <freebsd-ipfw@freebsd.org> Subject: Re: [RFC] IPv6 ifaddr hash Message-ID: <50C30D21.6070804@FreeBSD.org> In-Reply-To: <50C1E09A.5050301@FreeBSD.org> References: <50C1E09A.5050301@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 07.12.2012 16:27, Andrey V. Elsukov wrote: > Hi All, > > We have discovered that ipfw(4) shows very low performance results with > our rules. One of the biggest problems is rules with O_IP6_XXX_ME > opcode. They checks match or not match packet's addresses with locally > configured IPv6 addresses. > > For IPv4 we have an in_ifaddr hash for the quick search an address, but > not for the IPv6. So, I have implemented the first patch based on the > code for the IPv4, but there are several questions I want to discuss. > > The patch is here: > http://people.freebsd.org/~ae/in6_ifaddrhash.diff > > 1. The hash size. I made it the same what IPv4 has. But I think 512 > buckets is too many. While the same IPv6 configuration can have up to x2 addresses as in IPv4 (link-local addresses), 512 is really too much, maybe 64, or 128 be better for common-use case? > > 2. What hash function is better to use? We've got at least 3 (known to me) hashes in our kernel: ng_netflow one, flowtable and in ipfw. Can you provide some benchmarks and hashing effectiveness for some real-world data for those? > > 3. Using the whole 128 bit of address to hash seems like overkill. There are people using IPv6 address space just as plain IPv4, e.g: XX:YY:ZZ::1, XX:YY:ZZ::2, ... ::n, or even XX:YY:ZZ::A.B.C.D, so hashing upper 64 bits can lead to collisions. Hashing lower 64 is more promising, but there can be other use cases, too. Imho we can just test test performance of hashing functions and see how much is the different and is it worth talking. There is another problem: link-local addresses. They are all the same, (or there are some small number of different groups) so one (or more) bucket will always be filled by them. This can result in * some searches for global addresses being much slower * IPv6 code accepting packet to link-local address of the other interface ( RFC 4291 sec 2.5.6 ) We can workaround first problem by adding global unicast to list head, and link-local - to list tail, but this leaves us with the second one. One of possible solutions is to add interface index as another parameter to hash function, and use it IFF address is site-local. >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?50C30D21.6070804>