While experimenting with some extentions for flow tables, I noticed, that the hash function does not separate distinct entries clearly enough. Larger flows tables do reflect external structures and tend to heavily cluster the entries on a few hash values (i.e. src-ip and dst-ip are varied both within a network). Current code does not even include the protocol number. So I propose to reuse the existing crc32 function for this small amount of data. The probability to have a uniform distributed hash key increases dramatically and overall the lookup is faster than step through a list of entries having the same key. Note: This code depends on a zeroed struct fhashentry*, because it does not select the individual fields. All functions despite ta_prepare_del_fhash do clean the structure. I'm not sure, if this is can cause a problem. --- sys/netpfil/ipfw/ip_fw_table_algo.c (revision 314807) +++ sys/netpfil/ipfw/ip_fw_table_algo.c (working copy) @@ -3163,7 +3176,7 @@ { uint32_t i; - i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport); + i = crc32(f, sizeof(*f)); return (i % (hsize - 1)); } @@ -3173,11 +3186,7 @@ { uint32_t i; - i = (f->dip6.__u6_addr.__u6_addr32[2]) ^ - (f->dip6.__u6_addr.__u6_addr32[3]) ^ - (f->sip6.__u6_addr.__u6_addr32[2]) ^ - (f->sip6.__u6_addr.__u6_addr32[3]) ^ - (f->e.dport) ^ (f->e.sport); + i = crc32(f, sizeof(*f)); return (i % (hsize - 1)); }
I would suggest maybe using crc32c() instead of crc32() — the former is the ISCSI polynomial with hardware support on recent amd64 CPUs.
Please choose the most appropriate call, you can find. My choice was driven by minimal impact considerations.
The patch is wrong. It does include too much fields from the record, especially nonstatic ones (e.next) or unknown ones (e.value). The following patch runs ins a production environment. --- sys/netpfil/ipfw/ip_fw_table_algo.c (revision 314807) +++ sys/netpfil/ipfw/ip_fw_table_algo.c (working copy) @@ -44,6 +44,7 @@ #include <sys/malloc.h> #include <sys/kernel.h> #include <sys/lock.h> +#include <sys/libkern.h> #include <sys/rwlock.h> #include <sys/rmlock.h> #include <sys/socket.h> @@ -3158,30 +3171,35 @@ return (0); } +#define UPDATE_CRC(c, x) c = calculate_crc32c(c, (const char*)&(x), sizeof(x)) static __inline uint32_t hash_flow4(struct fhashentry4 *f, int hsize) { - uint32_t i; + uint32_t i = ~0u; + + UPDATE_CRC(i, f->sip); + UPDATE_CRC(i, f->dip); + UPDATE_CRC(i, f->e.sport); + UPDATE_CRC(i, f->e.dport); + UPDATE_CRC(i, f->e.proto); - i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport); - - return (i % (hsize - 1)); + return ((~i) % (hsize - 1)); } static __inline uint32_t hash_flow6(struct fhashentry6 *f, int hsize) { - uint32_t i; + uint32_t i = ~0u; + + UPDATE_CRC(i, f->sip6); + UPDATE_CRC(i, f->dip6); + UPDATE_CRC(i, f->e.sport); + UPDATE_CRC(i, f->e.dport); + UPDATE_CRC(i, f->e.proto); - i = (f->dip6.__u6_addr.__u6_addr32[2]) ^ - (f->dip6.__u6_addr.__u6_addr32[3]) ^ - (f->sip6.__u6_addr.__u6_addr32[2]) ^ - (f->sip6.__u6_addr.__u6_addr32[3]) ^ - (f->e.dport) ^ (f->e.sport); - - return (i % (hsize - 1)); + return ((~i) % (hsize - 1)); } - +#undef UPDATE_CRC static uint32_t hash_flow_ent(struct fhashentry *ent, uint32_t size) {
https://reviews.freebsd.org/D30085