![[BACK]](/icons/back.gif){kind=icon}
Up to [local] / src / sys / net
Request diff between arbitrary revisions
Default branch: MAIN
Revision 1.10 / (download) - annotate - [select for diffs], Sun Feb 21 02:37:38 2021 UTC (3 years, 3 months ago) by dlg
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE,
OPENBSD_7_5,
OPENBSD_7_4_BASE,
OPENBSD_7_4,
OPENBSD_7_3_BASE,
OPENBSD_7_3,
OPENBSD_7_2_BASE,
OPENBSD_7_2,
OPENBSD_7_1_BASE,
OPENBSD_7_1,
OPENBSD_7_0_BASE,
OPENBSD_7_0,
OPENBSD_6_9_BASE,
OPENBSD_6_9,
HEAD
Changes since 1.9: +10 -1 lines
Diff to previous 1.9 (colored)
add stoeplitz_eaddr, for getting a hash value from an ethernet address.
Revision 1.9 / (download) - annotate - [select for diffs], Tue Sep 1 19:18:26 2020 UTC (3 years, 9 months ago) by tb
Branch: MAIN
CVS Tags: OPENBSD_6_8_BASE,
OPENBSD_6_8
Changes since 1.8: +3 -3 lines
Diff to previous 1.8 (colored)
zap nasty whitespace
Revision 1.8 / (download) - annotate - [select for diffs], Fri Jul 17 13:13:36 2020 UTC (3 years, 10 months ago) by tb
Branch: MAIN
Changes since 1.7: +30 -1 lines
Diff to previous 1.7 (colored)
Randomize the system stoeplitz key One can prove that the Toeplitz matrix generated from a 16-bit seed is invertible if and only if the seed has odd Boolean parity. Invertibility is necessary and sufficient for the stoeplitz hash to take all 65536 possible values. Generate a system stoeplitz seed of odd parity uniformly at random. This is done by generating a random 16-bit number and then flipping its last bit if it's of even parity. This works since flipping the last bit swaps the numbers of even and odd parity, so we obtain a 2:1 mapping from all 16-bit numbers onto those with odd parity. Implementation of parity via popcount provided by naddy; input from miod, David Higgs, Matthew Martin, Martin Vahlensieck and others. ok dlg
Revision 1.7 / (download) - annotate - [select for diffs], Fri Jun 19 08:48:15 2020 UTC (3 years, 11 months ago) by dlg
Branch: MAIN
Changes since 1.6: +3 -2 lines
Diff to previous 1.6 (colored)
let stoeplitz_to_key take a void * argument instead of uint8_t *. ix(4) wants an array of uint32_ts to push into 32bit registers.
Revision 1.6 / (download) - annotate - [select for diffs], Thu Jun 18 12:22:39 2020 UTC (3 years, 11 months ago) by tb
Branch: MAIN
Changes since 1.5: +6 -19 lines
Diff to previous 1.5 (colored)
Introduce stoeplitz_hash_n32() and use it to simplify the hash_ip* functions further. ok dlg
Revision 1.5 / (download) - annotate - [select for diffs], Thu Jun 18 11:06:32 2020 UTC (3 years, 11 months ago) by tb
Branch: MAIN
Changes since 1.4: +23 -40 lines
Diff to previous 1.4 (colored)
The same simplification can be done a second time: widen the type, xor laddr and faddr and the ports together and only then fold the 32 bits into 16 bits. ok dlg
Revision 1.4 / (download) - annotate - [select for diffs], Thu Jun 18 05:33:17 2020 UTC (3 years, 11 months ago) by tb
Branch: MAIN
Changes since 1.3: +9 -38 lines
Diff to previous 1.3 (colored)
Now that the calls to stoeplitz_cache_entry() are out of the way, we can ditch half of the calculations by merging the computation of hi and lo, only splitting at the end. This allows us to leverage stoeplitz_hash_n16(). The name lo is now wrong. I kept it in order to avoid noise. I'm going to clean this up in the next step. ok dlg
Revision 1.3 / (download) - annotate - [select for diffs], Thu Jun 18 03:53:38 2020 UTC (3 years, 11 months ago) by tb
Branch: MAIN
Changes since 1.2: +53 -49 lines
Diff to previous 1.2 (colored)
The next step is to use that we have cached the result of the matrix
multiplication H * val in stoeplitz_cache_entry(scache, val), so the
identity (H * x) ^ (H * y) == H * (x ^ y) allows us to push the calls to
the cache function down to the end of stoeplitz_hash_ip{4,6}{,port}().
The identity in question was also confirmed on amd64, sparc64 and powerpc
for all possible values of skey, x and y.
ok dlg
Revision 1.2 / (download) - annotate - [select for diffs], Wed Jun 17 06:36:56 2020 UTC (3 years, 11 months ago) by tb
Branch: MAIN
Changes since 1.1: +22 -25 lines
Diff to previous 1.1 (colored)
Remove some of the unnecessary complications in the calculation of the stoeplitz_cache and bring them into a form more suitable for mathematical reasoning. Add a comment explaining the full construction which will also help justifying upcoming diffs. The observations for the code changes are the following: First, scache->bytes[val] is a uint16_t, and we only need the lower 16 bits of res in the second nested pair of for loops. The values of key[b] are only xored together to compute res, so we only need the lower 16 bits of those, too. Second, looking at the first nested for loop, we see that the values 0..15 of j only touch the top 16 bits of key[b], so we can skip them. For b = 0, the inner loop for j in 16..31 scans backwards through skey and sets the corresponding bits of key[b], so key[0] = skey. A bit of pondering then leads to key[b] = skey << b | skey >> (NBSK - b). The key array is renamed into column since it stores columns of the Toeplitz matrix. It's not very expensive to brute-force verify that scache->bytes[val] remains the same for all values of val and all values of skey. I did this on amd64, sparc64 and powerpc. ok dlg
Revision 1.1 / (download) - annotate - [select for diffs], Tue Jun 16 04:46:49 2020 UTC (3 years, 11 months ago) by dlg
Branch: MAIN
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@