CVSROOT: /cvs
Module name: src
Changes by: [email protected] 2020/06/15 22:46:49
Added files:
sys/net : toeplitz.c toeplitz.h
Log message:
Add a symmetric toeplitz implementation, with integration for nics.
This is another bit of the puzzle for supporting multiple rx rings
and receive side scaling (RSS) on nics. It borrows heavily from
DragonflyBSD, but I've made some tweaks on the way.
The interesting bits that dfly came up with was a way to use Toeplitz
hashing so the kernel AND network interfaces hash packets so packets
in both directions onto the same bucket. The other interesting thing
is that the optimised the hash calculation by building a cache of
all the intermediate results possible for each input byte. Their
hash calculation is simply xoring these intermediate reults together.
So this diff adds an API for the kernel to use for calculating a
hash for ip addresses and ports, and adds a function for network
drivers to call that gives them a key to use with RSS. If all drivers
use the same key, then the same flows should be steered to the same
place when they enter the network stack regardless of which hardware
they came in on.
The changes I made relative to dfly are around reducing the size
of the caches. DragonflyBSD builds a cache of 32bit values, but
because of how the Toeplitz key is constructed, the 32bits are made
up of a repeated 16bit pattern. We can just store the 16 bits and
reconstruct the 32 bits if we want. Both us and dragonfly only
use 15 or 16 bits of the result anyway, so 32bits is unecessary.
Secondly, the dfly implementation keeps a cache of values for the
high and low bytes of input, but the values in the two caches are
almost the same. You can byteswap the values in one of the byte
caches to get the values for the other, but you can also just
byteswap values at runtime to get the same value, which is what
this implementation does. The result of both these changes is that
the byte cache is a quarter of the size of the one in dragonflybsd.
tb@ has had a close look at this and found a bunch of other
optimisations that can be implemented, and because he's a
wizard^Wmathematician he has proofs (and also did tests).
ok tb@ jmatthew@
