Bug 217618 - Enhance hash function in ip_fw_table_algo.c for flow:hash
Summary: Enhance hash function in ip_fw_table_algo.c for flow:hash
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: kern (show other bugs)
Version: 11.0-STABLE
Hardware: Any Any
: --- Affects Some People
Assignee: freebsd-bugs mailing list
URL:
Keywords: patch
Depends on:
Blocks:
 
Reported: 2017-03-07 21:02 UTC by lutz
Modified: 2017-05-15 21:02 UTC (History)
2 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description lutz 2017-03-07 21:02:37 UTC
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));
 }
Comment 1 Conrad Meyer freebsd_committer 2017-03-07 21:17:37 UTC
I would suggest maybe using crc32c() instead of crc32() — the former is the ISCSI polynomial with hardware support on recent amd64 CPUs.
Comment 2 lutz 2017-03-07 23:46:19 UTC
Please choose the most appropriate call, you can find.
My choice was driven by minimal impact considerations.
Comment 3 lutz 2017-05-15 21:02:58 UTC
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)
 {