Re: [PATCH] netfilter: remove modulo operations

["Maciej Żenczykowski" <zenczykowski@gmail.com>]

> To be read as: one OV is reachable by 13 input values; 5 OVs are each
> reachable by 12 input values (IV) (i.e. a group of 60 IV lead to only 5
> OV), etc.

I don't quite follow what you are doing here.

> You can surely agree with me that this looks very much like at least
> one queue will be at a disadvantage (getting less packets).
>
> And indeed, with total_queues=4 I get a packet distribution of
>
>  24.41404 25.58534 25.00025 25.00037
>
> percent. With more queues, I suspect the variance will go up.

This suggests the hash function is bad.

The only difference between
  HASH32 % N
and
  (HASH32 * N) >> 32
is that modulus has a tendency to use the lower bits of the HASH32,
while multiplication has a tendency to use the higher bits of the
HASH32.
Non-prime values of N will be worse than prime values (excluding two),
and power-of-two values of N will be worst.

If the HASH32 is being calculated as SRC_IP^DST_IP, and then we're
using a power-of-two value of N, then we're basically using the top
two (for N=4)
bits of SRC_IP^DST_IP, which has a bad distribution for obvious
reasons - namely, ips aren't randomly distributed, especially so for
their top two bits.
Remember entire /8's haven't been allocated, the entire top /3 is
multicast or reserved.  And certain /8's (like 10.*) are much more
likely than others (0.*).

It certainly seems that the hash function should be fixed.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html