Re: symmetric toeplitz hashing
> On 13 Jun 2020, at 3:20 pm, Theo Buehler wrote: > > On Sat, Jun 13, 2020 at 11:35:42AM +1000, David Gwynne wrote: >> On Fri, Jun 12, 2020 at 03:37:59PM +0200, Theo Buehler wrote: >>> I finally found the time to think about the mathematics of this some >>> more and I'm now convinced that it's a sound construction. I hope that >>> one or the other observation below will be useful for you. >> >> Yes, I read everything below and it sounds great and useful. My only >> issue is that I'd like to show the application of those changes as >> commits in the tree. I already feel the diff I originally posted has >> diverged too far from the dfly code and a lot of why I made the changes >> have been lost. > > I'm fine with tweaking things in tree. I have reviewed the original code > and it looks good. The API looks sane. You have my ok for the original > diff (modulo the typos I pointed out), but it's really not my part of > the tree... > > Once it's landed, I can provide diffs for the tweaks for the internals I > suggested. We can also wait with those until some consumers are wired > up, so we can actually test them. Alright. I'm going to start putting it into the tree tomorrow unless someone with a good reason objects.
Re: symmetric toeplitz hashing
> On 14 Jun 2020, at 10:59 pm, Miod Vallat wrote: > > >>> Others have pointed out off-list that one can use __builtin_popcount(), >>> but __builtin_parity() is exactly what I want. Is it available on all >>> architectures? >> >> I don't think it is available on gcc 3.x for m88k but someone with >> an m88k should confirm. > > __builtin_popcount() does not exist in gcc 3. Also not sure it's necessary to omg-optimise the initialisation of the cache, which hopefully happens once early in boot.
Re: symmetric toeplitz hashing
>> Others have pointed out off-list that one can use __builtin_popcount(), >> but __builtin_parity() is exactly what I want. Is it available on all >> architectures? > > I don't think it is available on gcc 3.x for m88k but someone with > an m88k should confirm. __builtin_popcount() does not exist in gcc 3.
Re: symmetric toeplitz hashing
On 6/13/20 2:47 PM, Theo Buehler wrote: >>> Yes. The thing is that you need to convince yourself that this is still >>> uniformly distributed over the wanted numbers. But it's correct. In >>> fact, it's enough to flip a fixed bit, so you can get away with one call >>> to arc4random(). >> >> Its not immediately obvious because this is not always true. >> Only true if your bad seed was at least surjective onto the desired codomain. > > Since we start from a uniform distribution, surjective is not good > enough. It needs to be n:1. > Ah, yes, I missed that we're starting from a uniform distribution. I assumed the even the original generator one was non uniform. Which now that I think about it would be non trivial to convert to uniform. > Flipping the k-th bit swaps the numbers of odd parity (good seeds) with > the numbers of even parity (bad seeds). The suggested construction of > keeping a good seed and flipping the k-th bit of a bad one yields a 2:1 > mapping from all 16-bit numbers onto those with odd parity. We're good. > > David Higgs's code is also correct. Probably the easiest way to see that > is to start from a uniform distribution on [0, 2^16-1] x [0, 15] and map > it 32:1 onto the good seeds -- (x, k) maps to x if x is good, and to x > with the k-th bit flipped if x is bad. > Yep, thanks this follows once I get rid of my assumption. Aisha
Re: symmetric toeplitz hashing
On 6/13/20 9:19 AM, Theo Buehler wrote:
> On Sat, Jun 13, 2020 at 08:46:13AM -0400, David Higgs wrote:
>> On Fri, Jun 12, 2020 at 9:41 AM Theo Buehler wrote:
>>
>>> I finally found the time to think about the mathematics of this some
>>> more and I'm now convinced that it's a sound construction. I hope that
>>> one or the other observation below will be useful for you.
>>>
>>> The hash as it is now can be proved to produce values in the full range
>>> of uint16_t, so that's good.
>>>
>>> As we discussed already, you can simplify the construction further.
>>>
>>
>> [snip]
>>
>>
>>> Next, I don't particularly like this magic STOEPLITZ_KEYSEED number, but
>>> I guess we can live with it.
>>>
>>> Another option would be to generate the key seed randomly. You will get
>>> a "good" hash that spreads out over all 16 bit values if and only if the
>>> random value has an odd number of binary digits.
>>>
>>> I haven't thought hard about this, but I don't immediately see a better
>>> way of generating such numbers than:
>>>
>>> int
>>> stoeplitz_good_seed(uint16_t seed)
>>> {
>>> int ones = 0;
>>>
>>> while (seed > 0) {
>>> ones += seed % 2;
>>> seed /= 2;
>>> }
>>>
>>> return ones % 2;
>>> }
>>>
>>> uint16_t
>>> stoeplitz_seed_init(void)
>>> {
>>> uint16_tseed;
>>>
>>> do {
>>> seed = arc4random() & UINT16_MAX;
>>> } while (!stoeplitz_good_seed(seed));
>>>
>>> return seed;
>>> }
>>>
>>> This will loop as long as it needs to get a good toeplitz key seed.
>>> Each time there is a 50% chance that it will find one, so this will
>>> need to loop n times with probability 1 / 2**n. This is basically the
>>> same situation as for arc4random_uniform() with an upper bound that is
>>> not a power of two.
>>>
>>
>> I neither read nor understand the math but assuming you've described it
>> correctly, you can do this more simply by realizing that a random bad seed
>> can be made into a good seed by toggling one (random) bit.
>
> Yes. The thing is that you need to convince yourself that this is still
> uniformly distributed over the wanted numbers. But it's correct. In
> fact, it's enough to flip a fixed bit, so you can get away with one call
> to arc4random().
Its not immediately obvious because this is not always true.
Only true if your bad seed was at least surjective onto the desired codomain.
>
>> You also
>> replace stoeplitz_good_seed() with __builtin_parity() and perhaps leverage
>> some intrinsics?
>
> Others have pointed out off-list that one can use __builtin_popcount(),
> but __builtin_parity() is exactly what I want. Is it available on all
> architectures?
>
>>
>> uint16_t
>> stoeplitz_seed_init(void) {
>> uint16_t seed;
>> seed = arc4random() & UINT16_MAX;
>> if (!stoeplitz_good_seed(seed))
>> seed ^= 1 << (arc4random() % 16);
>> }
>>
>> --david
>
Re: symmetric toeplitz hashing
On Sat, Jun 13, 2020 at 07:10:50PM -, Christian Weisgerber wrote:
> On 2020-06-13, Theo Buehler wrote:
>
> > Others have pointed out off-list that one can use __builtin_popcount(),
> > but __builtin_parity() is exactly what I want. Is it available on all
> > architectures?
>
> The standard implementation will be perfectly fine, no need to resort
> to magic compiler built-ins.
>
I was curious.
> int
> popcount(uint16_t x)
> {
> x = (x & 0x) + ((x & 0x) >> 1);
> x = (x & 0x) + ((x & 0x) >> 2);
> x = (x & 0x0F0F) + ((x & 0xF0F0) >> 4);
> x = (x & 0x00FF) + ((x & 0xFF00) >> 8);
> return (x);
> }
>
> ... which immediately lends itself to:
Yes. Thank you!
>
> int
> parity(uint16_t x)
> {
> x = (x & 0x) ^ ((x & 0x) >> 1);
> x = (x & 0x) ^ ((x & 0x) >> 2);
> x = (x & 0x0F0F) ^ ((x & 0xF0F0) >> 4);
> x = (x & 0x00FF) ^ ((x & 0xFF00) >> 8);
> return (x);
> }
>
> --
> Christian "naddy" Weisgerber na...@mips.inka.de
>
Re: symmetric toeplitz hashing
On 2020-06-13, Theo Buehler wrote:
> Others have pointed out off-list that one can use __builtin_popcount(),
> but __builtin_parity() is exactly what I want. Is it available on all
> architectures?
The standard implementation will be perfectly fine, no need to resort
to magic compiler built-ins.
int
popcount(uint16_t x)
{
x = (x & 0x) + ((x & 0x) >> 1);
x = (x & 0x) + ((x & 0x) >> 2);
x = (x & 0x0F0F) + ((x & 0xF0F0) >> 4);
x = (x & 0x00FF) + ((x & 0xFF00) >> 8);
return (x);
}
... which immediately lends itself to:
int
parity(uint16_t x)
{
x = (x & 0x) ^ ((x & 0x) >> 1);
x = (x & 0x) ^ ((x & 0x) >> 2);
x = (x & 0x0F0F) ^ ((x & 0xF0F0) >> 4);
x = (x & 0x00FF) ^ ((x & 0xFF00) >> 8);
return (x);
}
--
Christian "naddy" Weisgerber na...@mips.inka.de
Re: symmetric toeplitz hashing
> > Yes. The thing is that you need to convince yourself that this is still > > uniformly distributed over the wanted numbers. But it's correct. In > > fact, it's enough to flip a fixed bit, so you can get away with one call > > to arc4random(). > > Its not immediately obvious because this is not always true. > Only true if your bad seed was at least surjective onto the desired codomain. Since we start from a uniform distribution, surjective is not good enough. It needs to be n:1. Flipping the k-th bit swaps the numbers of odd parity (good seeds) with the numbers of even parity (bad seeds). The suggested construction of keeping a good seed and flipping the k-th bit of a bad one yields a 2:1 mapping from all 16-bit numbers onto those with odd parity. We're good. David Higgs's code is also correct. Probably the easiest way to see that is to start from a uniform distribution on [0, 2^16-1] x [0, 15] and map it 32:1 onto the good seeds -- (x, k) maps to x if x is good, and to x with the k-th bit flipped if x is bad.
Re: symmetric toeplitz hashing
On Sat, 13 Jun 2020 15:19:28 +0200, Theo Buehler wrote: > Others have pointed out off-list that one can use __builtin_popcount(), > but __builtin_parity() is exactly what I want. Is it available on all > architectures? I don't think it is available on gcc 3.x for m88k but someone with an m88k should confirm. - todd
Re: symmetric toeplitz hashing
On Sat, Jun 13, 2020 at 08:46:13AM -0400, David Higgs wrote:
> On Fri, Jun 12, 2020 at 9:41 AM Theo Buehler wrote:
>
> > I finally found the time to think about the mathematics of this some
> > more and I'm now convinced that it's a sound construction. I hope that
> > one or the other observation below will be useful for you.
> >
> > The hash as it is now can be proved to produce values in the full range
> > of uint16_t, so that's good.
> >
> > As we discussed already, you can simplify the construction further.
> >
>
> [snip]
>
>
> > Next, I don't particularly like this magic STOEPLITZ_KEYSEED number, but
> > I guess we can live with it.
> >
> > Another option would be to generate the key seed randomly. You will get
> > a "good" hash that spreads out over all 16 bit values if and only if the
> > random value has an odd number of binary digits.
> >
> > I haven't thought hard about this, but I don't immediately see a better
> > way of generating such numbers than:
> >
> > int
> > stoeplitz_good_seed(uint16_t seed)
> > {
> > int ones = 0;
> >
> > while (seed > 0) {
> > ones += seed % 2;
> > seed /= 2;
> > }
> >
> > return ones % 2;
> > }
> >
> > uint16_t
> > stoeplitz_seed_init(void)
> > {
> > uint16_tseed;
> >
> > do {
> > seed = arc4random() & UINT16_MAX;
> > } while (!stoeplitz_good_seed(seed));
> >
> > return seed;
> > }
> >
> > This will loop as long as it needs to get a good toeplitz key seed.
> > Each time there is a 50% chance that it will find one, so this will
> > need to loop n times with probability 1 / 2**n. This is basically the
> > same situation as for arc4random_uniform() with an upper bound that is
> > not a power of two.
> >
>
> I neither read nor understand the math but assuming you've described it
> correctly, you can do this more simply by realizing that a random bad seed
> can be made into a good seed by toggling one (random) bit.
Yes. The thing is that you need to convince yourself that this is still
uniformly distributed over the wanted numbers. But it's correct. In
fact, it's enough to flip a fixed bit, so you can get away with one call
to arc4random().
> You also
> replace stoeplitz_good_seed() with __builtin_parity() and perhaps leverage
> some intrinsics?
Others have pointed out off-list that one can use __builtin_popcount(),
but __builtin_parity() is exactly what I want. Is it available on all
architectures?
>
> uint16_t
> stoeplitz_seed_init(void) {
> uint16_t seed;
> seed = arc4random() & UINT16_MAX;
> if (!stoeplitz_good_seed(seed))
> seed ^= 1 << (arc4random() % 16);
> }
>
> --david
Re: symmetric toeplitz hashing
On Fri, Jun 12, 2020 at 9:41 AM Theo Buehler wrote:
> I finally found the time to think about the mathematics of this some
> more and I'm now convinced that it's a sound construction. I hope that
> one or the other observation below will be useful for you.
>
> The hash as it is now can be proved to produce values in the full range
> of uint16_t, so that's good.
>
> As we discussed already, you can simplify the construction further.
>
[snip]
> Next, I don't particularly like this magic STOEPLITZ_KEYSEED number, but
> I guess we can live with it.
>
> Another option would be to generate the key seed randomly. You will get
> a "good" hash that spreads out over all 16 bit values if and only if the
> random value has an odd number of binary digits.
>
> I haven't thought hard about this, but I don't immediately see a better
> way of generating such numbers than:
>
> int
> stoeplitz_good_seed(uint16_t seed)
> {
> int ones = 0;
>
> while (seed > 0) {
> ones += seed % 2;
> seed /= 2;
> }
>
> return ones % 2;
> }
>
> uint16_t
> stoeplitz_seed_init(void)
> {
> uint16_tseed;
>
> do {
> seed = arc4random() & UINT16_MAX;
> } while (!stoeplitz_good_seed(seed));
>
> return seed;
> }
>
> This will loop as long as it needs to get a good toeplitz key seed.
> Each time there is a 50% chance that it will find one, so this will
> need to loop n times with probability 1 / 2**n. This is basically the
> same situation as for arc4random_uniform() with an upper bound that is
> not a power of two.
>
I neither read nor understand the math but assuming you've described it
correctly, you can do this more simply by realizing that a random bad seed
can be made into a good seed by toggling one (random) bit. You also
replace stoeplitz_good_seed() with __builtin_parity() and perhaps leverage
some intrinsics?
uint16_t
stoeplitz_seed_init(void) {
uint16_t seed;
seed = arc4random() & UINT16_MAX;
if (!stoeplitz_good_seed(seed))
seed ^= 1 << (arc4random() % 16);
}
--david
Re: symmetric toeplitz hashing
On Sat, Jun 13, 2020 at 11:35:42AM +1000, David Gwynne wrote: > On Fri, Jun 12, 2020 at 03:37:59PM +0200, Theo Buehler wrote: > > I finally found the time to think about the mathematics of this some > > more and I'm now convinced that it's a sound construction. I hope that > > one or the other observation below will be useful for you. > > Yes, I read everything below and it sounds great and useful. My only > issue is that I'd like to show the application of those changes as > commits in the tree. I already feel the diff I originally posted has > diverged too far from the dfly code and a lot of why I made the changes > have been lost. I'm fine with tweaking things in tree. I have reviewed the original code and it looks good. The API looks sane. You have my ok for the original diff (modulo the typos I pointed out), but it's really not my part of the tree... Once it's landed, I can provide diffs for the tweaks for the internals I suggested. We can also wait with those until some consumers are wired up, so we can actually test them.
Re: symmetric toeplitz hashing
On Fri, Jun 12, 2020 at 03:37:59PM +0200, Theo Buehler wrote:
> I finally found the time to think about the mathematics of this some
> more and I'm now convinced that it's a sound construction. I hope that
> one or the other observation below will be useful for you.
Yes, I read everything below and it sounds great and useful. My only
issue is that I'd like to show the application of those changes as
commits in the tree. I already feel the diff I originally posted has
diverged too far from the dfly code and a lot of why I made the changes
have been lost.
> The hash as it is now can be proved to produce values in the full range
> of uint16_t, so that's good.
>
> As we discussed already, you can simplify the construction further.
Yep, I'm keen.
> One trick is that stoeplitz_cache_entry() is linear in the second
> argument -- you can think of the xor operation ^ as addition of vectors
> (uint8_t and uint16_t) over the field with two elements {0, 1}. That's
> just the mathematician's way of expressing this relation:
>
> stoeplitz_cache_entry(scache, a ^ b)
> == stoeplitz_cache_entry(scache, a) ^ stoeplitz_cache_entry(scache,
> b);
>
> Using this, the stoeplitz hash functions can be rewritten to this.
> I would expect it to be a bit cheaper.
Yes, that's very cool.
> uint16_t
> stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
> in_addr_t faddr, in_addr_t laddr)
> {
> uint16_t lo, hi;
>
> lo = faddr >> 0;
> lo ^= faddr >> 16;
> lo ^= laddr >> 0;
> lo ^= laddr >> 16;
>
> hi = faddr >> 8;
> hi ^= faddr >> 24;
> hi ^= laddr >> 8;
> hi ^= laddr >> 24;
>
> return swap16(stoeplitz_cache_entry(scache, lo))
> ^ stoeplitz_cache_entry(scache, hi);
> }
>
> or another example:
>
> uint16_t
> stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache,
> const struct in6_addr *faddr6, const struct in6_addr * laddr6,
> in_port_t fport, in_port_t lport)
> {
> uint16_t hi = 0, lo = 0;
> size_t i;
>
> for (i = 0; i < nitems(faddr6->s6_addr32); i++) {
> uint32_t faddr = faddr6->s6_addr32[i];
> uint32_t laddr = laddr6->s6_addr32[i];
>
> lo ^= faddr >> 0;
> lo ^= faddr >> 16;
> lo ^= laddr >> 0;
> lo ^= laddr >> 16;
>
> hi ^= faddr >> 8;
> hi ^= faddr >> 24;
> hi ^= laddr >> 8;
> hi ^= laddr >> 24;
> }
>
> lo ^= fport >> 0;
> lo ^= lport >> 0;
>
> hi ^= fport >> 8;
> hi ^= lport >> 8;
>
> return swap16(stoeplitz_cache_entry(scache, lo))
> ^ stoeplitz_cache_entry(scache, hi);
> }
>
> and so on.
Very cool.
> Next, I don't particularly like this magic STOEPLITZ_KEYSEED number, but
> I guess we can live with it.
My understanding is that it comes from the vector MS provided or used. I
can't easily find their old or original documentation, but you can see
it's the first two bytes in the following:
https://docs.microsoft.com/en-us/windows-hardware/drivers/network/verifying-the-rss-hash-calculation
> Another option would be to generate the key seed randomly. You will get
> a "good" hash that spreads out over all 16 bit values if and only if the
> random value has an odd number of binary digits.
sephe and I have talked about replacing it with a random number, but I
was going to wait until such a change could have an interesting commit
message in a tree. However, my idea of a good seed was "making sure it's
not zero", so I'm super happy there's a much more rigorous definition
we can use.
> I haven't thought hard about this, but I don't immediately see a better
> way of generating such numbers than:
>
> int
> stoeplitz_good_seed(uint16_t seed)
> {
> int ones = 0;
>
> while (seed > 0) {
> ones += seed % 2;
> seed /= 2;
> }
>
> return ones % 2;
> }
>
> uint16_t
> stoeplitz_seed_init(void)
> {
> uint16_tseed;
>
> do {
> seed = arc4random() & UINT16_MAX;
> } while (!stoeplitz_good_seed(seed));
>
> return seed;
> }
>
> This will loop as long as it needs to get a good toeplitz key seed.
> Each time there is a 50% chance that it will find one, so this will
> need to loop n times with probability 1 / 2**n. This is basically the
> same situation as for arc4random_uniform() with an upper bound that is
> not a power of two.
>
> I don't know if something like that is acceptable early in init_main.c.
> If it is, you can use a seed generated by this init function in place
> of STOEPLITZ_KEYSEED.
I think deraadt@ would be fine with us permuting the random number
generator by taking some bytes out of it early.
> Finally, I don't think it would be all bad to eliminate the cache
> altogether and simply do this (and similarly for all the other
> stoeplitz_hash_*() variants). This would be another way of
Re: symmetric toeplitz hashing
I finally found the time to think about the mathematics of this some
more and I'm now convinced that it's a sound construction. I hope that
one or the other observation below will be useful for you.
The hash as it is now can be proved to produce values in the full range
of uint16_t, so that's good.
As we discussed already, you can simplify the construction further.
One trick is that stoeplitz_cache_entry() is linear in the second
argument -- you can think of the xor operation ^ as addition of vectors
(uint8_t and uint16_t) over the field with two elements {0, 1}. That's
just the mathematician's way of expressing this relation:
stoeplitz_cache_entry(scache, a ^ b)
== stoeplitz_cache_entry(scache, a) ^ stoeplitz_cache_entry(scache,
b);
Using this, the stoeplitz hash functions can be rewritten to this.
I would expect it to be a bit cheaper.
uint16_t
stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
in_addr_t faddr, in_addr_t laddr)
{
uint16_t lo, hi;
lo = faddr >> 0;
lo ^= faddr >> 16;
lo ^= laddr >> 0;
lo ^= laddr >> 16;
hi = faddr >> 8;
hi ^= faddr >> 24;
hi ^= laddr >> 8;
hi ^= laddr >> 24;
return swap16(stoeplitz_cache_entry(scache, lo))
^ stoeplitz_cache_entry(scache, hi);
}
or another example:
uint16_t
stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache,
const struct in6_addr *faddr6, const struct in6_addr * laddr6,
in_port_t fport, in_port_t lport)
{
uint16_t hi = 0, lo = 0;
size_t i;
for (i = 0; i < nitems(faddr6->s6_addr32); i++) {
uint32_t faddr = faddr6->s6_addr32[i];
uint32_t laddr = laddr6->s6_addr32[i];
lo ^= faddr >> 0;
lo ^= faddr >> 16;
lo ^= laddr >> 0;
lo ^= laddr >> 16;
hi ^= faddr >> 8;
hi ^= faddr >> 24;
hi ^= laddr >> 8;
hi ^= laddr >> 24;
}
lo ^= fport >> 0;
lo ^= lport >> 0;
hi ^= fport >> 8;
hi ^= lport >> 8;
return swap16(stoeplitz_cache_entry(scache, lo))
^ stoeplitz_cache_entry(scache, hi);
}
and so on.
Next, I don't particularly like this magic STOEPLITZ_KEYSEED number, but
I guess we can live with it.
Another option would be to generate the key seed randomly. You will get
a "good" hash that spreads out over all 16 bit values if and only if the
random value has an odd number of binary digits.
I haven't thought hard about this, but I don't immediately see a better
way of generating such numbers than:
int
stoeplitz_good_seed(uint16_t seed)
{
int ones = 0;
while (seed > 0) {
ones += seed % 2;
seed /= 2;
}
return ones % 2;
}
uint16_t
stoeplitz_seed_init(void)
{
uint16_tseed;
do {
seed = arc4random() & UINT16_MAX;
} while (!stoeplitz_good_seed(seed));
return seed;
}
This will loop as long as it needs to get a good toeplitz key seed.
Each time there is a 50% chance that it will find one, so this will
need to loop n times with probability 1 / 2**n. This is basically the
same situation as for arc4random_uniform() with an upper bound that is
not a power of two.
I don't know if something like that is acceptable early in init_main.c.
If it is, you can use a seed generated by this init function in place
of STOEPLITZ_KEYSEED.
Finally, I don't think it would be all bad to eliminate the cache
altogether and simply do this (and similarly for all the other
stoeplitz_hash_*() variants). This would be another way of eliminating
the magic number:
uint16_t
simple_hash_ip4(const struct stoeplitz_cache *scache,
in_addr_t faddr, in_addr_t laddr)
{
uint16_t lo, hi;
lo = faddr >> 0;
lo ^= faddr >> 16;
lo ^= laddr >> 0;
lo ^= laddr >> 16;
hi = faddr >> 8;
hi ^= faddr >> 24;
hi ^= laddr >> 8;
hi ^= laddr >> 24;
return (swap16(lo) ^ hi);
}
I don't see how this is fundamentally different from sephe's
construction although it's not quite a special case.
If there's a problem with this, I'd be really curious to know why.
Re: symmetric toeplitz hashing
> At the end of this loop, key[b] contains two copies of the cyclically
> permuted skey next to each other. When building the cache, you scan
> through the bits of val, xor the corresponding keys in if they're set
> and then throw away half of the 32 bits when assigning
> scache->bytes[val] = res;
>
> So I think you can use "uint16_t keys[NBBY];" and "uint16_t res = 0;",
> replace j < 32 by j < 16 and 31 - j by 15 - j and you'll get the exact
> same result.
In other words, the first nested loop can be simplified to this:
for (b = 0; b < NBBY; ++b)
key[b] = skey << b | skey >> (NBSK - b);
and instead of populating the the key[] array up front, you could do:
void
stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey)
{
unsigned int b, shift, val;
/*
* Cache the results of all possible bit combinations of
* one byte.
*/
for (val = 0; val < 256; ++val) {
uint16_t res = 0;
for (b = 0; b < NBBY; ++b) {
shift = NBBY - b - 1;
if (val & (1 << shift))
res ^= skey << b | skey >> (NBSK - b);
}
scache->bytes[val] = res;
}
}
Re: symmetric toeplitz hashing
On Fri, May 29, 2020 at 02:41:07PM +1000, David Gwynne wrote: > 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. > > For background on the dfly side, I recommend having a look at > https://leaf.dragonflybsd.org/~sephe/AsiaBSDCon%20-%20Dfly.pdf. > > From my point of view, the interesting thing is that they came up > with 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. > > I've made some tweaks compared to dfly for how the caching is > calculated and used, so it's not an exactly 1:1 port of the dfly > code. If anyone is interested in the tweaks, let me know. > > 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. > > I've tested it with vmx(4) and some quick and dirty hacks to the > network stack (and with some magical observability), and can see > things like tcpbench push packets onto the same numbered ifq/txring > that the "nic" picks for the rxring and therefore ifiq into the > stack. We're going to try it on some more drivers soon. > > The way this is set up now, if a nic driver wants to do RSS, you > add stoeplitz as a dependency in the kernel config file, which > causes this code to be included in the build. > > There's some discussion to be had about the best way to integrate > this on the IP stack side, but that is about where this API is > called from, not the internals of it per se. > > Thoughts? ok? It's a nice construction. Some tiny nits and one comment/question below. > > Index: share/man/man9/stoeplitz_to_key.9 > === > RCS file: share/man/man9/stoeplitz_to_key.9 > diff -N share/man/man9/stoeplitz_to_key.9 > --- /dev/null 1 Jan 1970 00:00:00 - > +++ share/man/man9/stoeplitz_to_key.9 29 May 2020 04:01:26 - > @@ -0,0 +1,126 @@ > +.\" $OpenBSD$ > +.\" > +.\" Copyright (c) 2020 David Gwynne > +.\" > +.\" Permission to use, copy, modify, and distribute this software for any > +.\" purpose with or without fee is hereby granted, provided that the above > +.\" copyright notice and this permission notice appear in all copies. > +.\" > +.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES > +.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF > +.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR > +.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES > +.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN > +.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF > +.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. > +.\" > +.Dd $Mdocdate: May 29 2020 $ > +.Dt STOEPLITZ_TO_KEY 9 > +.Os > +.Sh NAME > +.Nm stoeplitz_to_key , > +.Nm stoeplitz_hash_ip4 , > +.Nm stoeplitz_hash_ip4port , > +.Nm stoeplitz_hash_ip6 , > +.Nm stoeplitz_hash_ip4port > +.Nd Symmetric Toeplitz Hash API > +.Sh SYNOPSIS > +.In net/toeplitz.h > +.Ft void > +.Fn stoeplitz_to_key "uint8_t *key" "size_t keylen" > +.Ft uint16_t > +.Fo stoeplitz_hash_ip4 > +.Fa "uint32_t srcaddr" > +.Fa "uint32_t dstaddr" > +.Fc > +.Ft uint16_t > +.Fo stoeplitz_hash_ip4port > +.Fa "uint32_t srcaddr" > +.Fa "uint32_t dstaddr" > +.Fa "uint16_t srcport" > +.Fa "uint16_t dstport" > +.Fc > +.Ft uint16_t > +.Fo stoeplitz_hash_ip6 > +.Fa "const struct in6_addr *srcaddr" > +.Fa "const struct in6_addr *dstaddr" > +.Fc > +.Ft uint16_t > +.Fo stoeplitz_hash_ip6port > +.Fa "const struct in6_addr *srcaddr" > +.Fa "const struct in6_addr *dstaddr" > +.Fa "uint16_t srcport" > +.Fa "uint16_t dstport" > +.Fc > +.Sh DESCRIPTION > +The Toeplitz hash algorithm is commonly used by network interface > +controllers to to generate a short hash based on the value of fields > +in network packet headers. > +.\" mention RSS? > +The resulting hash value can be used as a flow identifier, which > +in turn can be used to consistently select a context for processing > +packets using those fields. > +Traditionally, the Toeplitz hash produces different results depending > +on the order of inputs, ie, adding port 80 then 1234 as inputs would > +produce a different result to hashing port 1234 then 80. > +.Pp > +The symmetric Toeplitz API uses a key selected to generate the same > +hash result regardless of the
symmetric toeplitz hashing
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. For background on the dfly side, I recommend having a look at https://leaf.dragonflybsd.org/~sephe/AsiaBSDCon%20-%20Dfly.pdf. >From my point of view, the interesting thing is that they came up with 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. I've made some tweaks compared to dfly for how the caching is calculated and used, so it's not an exactly 1:1 port of the dfly code. If anyone is interested in the tweaks, let me know. 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. I've tested it with vmx(4) and some quick and dirty hacks to the network stack (and with some magical observability), and can see things like tcpbench push packets onto the same numbered ifq/txring that the "nic" picks for the rxring and therefore ifiq into the stack. We're going to try it on some more drivers soon. The way this is set up now, if a nic driver wants to do RSS, you add stoeplitz as a dependency in the kernel config file, which causes this code to be included in the build. There's some discussion to be had about the best way to integrate this on the IP stack side, but that is about where this API is called from, not the internals of it per se. Thoughts? ok? Index: share/man/man9/stoeplitz_to_key.9 === RCS file: share/man/man9/stoeplitz_to_key.9 diff -N share/man/man9/stoeplitz_to_key.9 --- /dev/null 1 Jan 1970 00:00:00 - +++ share/man/man9/stoeplitz_to_key.9 29 May 2020 04:01:26 - @@ -0,0 +1,126 @@ +.\" $OpenBSD$ +.\" +.\" Copyright (c) 2020 David Gwynne +.\" +.\" Permission to use, copy, modify, and distribute this software for any +.\" purpose with or without fee is hereby granted, provided that the above +.\" copyright notice and this permission notice appear in all copies. +.\" +.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +.\" +.Dd $Mdocdate: May 29 2020 $ +.Dt STOEPLITZ_TO_KEY 9 +.Os +.Sh NAME +.Nm stoeplitz_to_key , +.Nm stoeplitz_hash_ip4 , +.Nm stoeplitz_hash_ip4port , +.Nm stoeplitz_hash_ip6 , +.Nm stoeplitz_hash_ip4port +.Nd Symmetric Toeplitz Hash API +.Sh SYNOPSIS +.In net/toeplitz.h +.Ft void +.Fn stoeplitz_to_key "uint8_t *key" "size_t keylen" +.Ft uint16_t +.Fo stoeplitz_hash_ip4 +.Fa "uint32_t srcaddr" +.Fa "uint32_t dstaddr" +.Fc +.Ft uint16_t +.Fo stoeplitz_hash_ip4port +.Fa "uint32_t srcaddr" +.Fa "uint32_t dstaddr" +.Fa "uint16_t srcport" +.Fa "uint16_t dstport" +.Fc +.Ft uint16_t +.Fo stoeplitz_hash_ip6 +.Fa "const struct in6_addr *srcaddr" +.Fa "const struct in6_addr *dstaddr" +.Fc +.Ft uint16_t +.Fo stoeplitz_hash_ip6port +.Fa "const struct in6_addr *srcaddr" +.Fa "const struct in6_addr *dstaddr" +.Fa "uint16_t srcport" +.Fa "uint16_t dstport" +.Fc +.Sh DESCRIPTION +The Toeplitz hash algorithm is commonly used by network interface +controllers to to generate a short hash based on the value of fields +in network packet headers. +.\" mention RSS? +The resulting hash value can be used as a flow identifier, which +in turn can be used to consistently select a context for processing +packets using those fields. +Traditionally, the Toeplitz hash produces different results depending +on the order of inputs, ie, adding port 80 then 1234 as inputs would +produce a different result to hashing port 1234 then 80. +.Pp +The symmetric Toeplitz API uses a key selected to generate the same +hash result regardless of the order the inputs were added. +The API also supports producing Toeplitz hash keys for use by +network interface controllers that provide the same symmetric +property. +.Pp +The +.Fn stoeplitz_to_key +function generates a Toeplitz key for use by a network interface +controller based on the systems symmetric Toeplitz key. +A Toeplitz key of +.Fa keylen +bytes will
