[Bug 217618] Enhance hash function in ip_fw_table_algo.c for flow:hash

[bugzilla-noreply at freebsd.org]

https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=217618

            Bug ID: 217618
           Summary: Enhance hash function in ip_fw_table_algo.c for
                    flow:hash
           Product: Base System
           Version: 11.0-STABLE
          Hardware: Any
                OS: Any
            Status: New
          Severity: Affects Some People
          Priority: ---
         Component: kern
          Assignee: freebsd-bugs at FreeBSD.org
          Reporter: lutz at donnerhacke.de

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));
 }

-- 
You are receiving this mail because:
You are the assignee for the bug.