Page MenuHomeFreeBSD

ipfw: Improve hash function for flow tables
Needs ReviewPublic

Authored by donner on May 2 2021, 11:28 PM.

Details

Reviewers
ae
kp
melifaro
Group Reviewers
network
Summary

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 in the same systematic way). Current code does
not even include the protocol number.

By switching from simple XOR to the already existing, hardware
accelerated crc32 function, the probability to have a uniform
distributed hash key increases dramatically and the lookup becomes
faster by avoiding traversing a long linked list of entries of the
same bucket.

PR: 217618
MFC: 2 weeks
Sponsored by: IKS Service GmbH

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 39896
Build 36785: arc lint + arc unit