[PATCH] netfilter: remove modulo operations

[PATCH] netfilter: remove modulo operations

[Changli Gao]

Signed-off-by: Changli Gao <xiaosuo@gmail.com>
---
 net/netfilter/xt_NFQUEUE.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/net/netfilter/xt_NFQUEUE.c b/net/netfilter/xt_NFQUEUE.c
index 039cce1..3962770 100644
--- a/net/netfilter/xt_NFQUEUE.c
+++ b/net/netfilter/xt_NFQUEUE.c
@@ -72,10 +72,12 @@ nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par)
 
 	if (info->queues_total > 1) {
 		if (par->family == NFPROTO_IPV4)
-			queue = hash_v4(skb) % info->queues_total + queue;
+			queue = (((u64) hash_v4(skb) * info->queues_total) >>
+				 32) + queue;
 #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)
 		else if (par->family == NFPROTO_IPV6)
-			queue = hash_v6(skb) % info->queues_total + queue;
+			queue = (((u64) hash_v6(skb) * info->queues_total) >>
+				 32) + queue;
 #endif
 	}
 	return NF_QUEUE_NR(queue);

Re: [PATCH] netfilter: remove modulo operations

[Florian Westphal]

Changli Gao <xiaosuo@gmail.com> wrote:
> Signed-off-by: Changli Gao <xiaosuo@gmail.com>
> ---
>  net/netfilter/xt_NFQUEUE.c |    6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
> diff --git a/net/netfilter/xt_NFQUEUE.c b/net/netfilter/xt_NFQUEUE.c
> index 039cce1..3962770 100644
> --- a/net/netfilter/xt_NFQUEUE.c
> +++ b/net/netfilter/xt_NFQUEUE.c
> @@ -72,10 +72,12 @@ nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par)
>  
>  	if (info->queues_total > 1) {
>  		if (par->family == NFPROTO_IPV4)
> -			queue = hash_v4(skb) % info->queues_total + queue;
> +			queue = (((u64) hash_v4(skb) * info->queues_total) >>
> +				 32) + queue;

I'd imagine that the result of ((hash * total) >> 32) is (almost)
always zero, especially if total is small (which it is usually).

Did you test that this change does not affect distribution average?

Re: [PATCH] netfilter: remove modulo operations

[Eric Dumazet]

Le dimanche 24 octobre 2010 à 20:25 +0200, Florian Westphal a écrit :

> I'd imagine that the result of ((hash * total) >> 32) is (almost)
> always zero, especially if total is small (which it is usually).
> 

Absolutely not. total is a 32bit number, using full range.

> Did you test that this change does not affect distribution average?

That would be shocking actually, given we use jhash()

I did same tricks in various parts of network stack in the past, and its
fine.



--
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

Re: [PATCH] netfilter: remove modulo operations

[Florian Westphal]

Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le dimanche 24 octobre 2010 à 20:25 +0200, Florian Westphal a écrit :
> > I'd imagine that the result of ((hash * total) >> 32) is (almost)
> > always zero, especially if total is small (which it is usually).
> > 
> 
> Absolutely not. total is a 32bit number, using full range.
> 
> > Did you test that this change does not affect distribution average?
> 
> That would be shocking actually, given we use jhash()
> 
> I did same tricks in various parts of network stack in the past, and its
> fine.

Yes, you are right.  I tested this change and it is OK.
--
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

Re: [PATCH] netfilter: remove modulo operations

[Maciej Żenczykowski]

> Absolutely not. total is a 32bit number, using full range.

Strictly speaking I think you mean 'hash' here, which as a hash
should indeed be a random value across a full 32-bit range.
Total might very well be pretty small.

Anyway, without having tested, the change looks fine to me.

Re: [PATCH] netfilter: remove modulo operations

[Jan Engelhardt]

On Sunday 2010-10-24 21:11, Eric Dumazet wrote:
>Le dimanche 24 octobre 2010 à 20:25 +0200, Florian Westphal a écrit :
>
>> I'd imagine that the result of ((hash * total) >> 32) is (almost)
>> always zero, especially if total is small (which it is usually).
>
>Absolutely not. total is a 32bit number, using full range.
>
>> Did you test that this change does not affect distribution average?
>
>That would be shocking actually, given we use jhash()
>
>I did same tricks in various parts of network stack in the past, and its
>fine.

I spent the afternoon raking on the impact on the distribution that 
using multiplication here would have. Intriguing concourse.

(I looked at Jenkins3, so there is a little gap to what's in the 
kernel.) Anyhow, the frequency of Jenkins3 output values (OV) being hit 
is:

1591633245x 0
1568275918x 1
 784435879x 2
 265277962x 3
  68188245x 4
  14213782x 5
   2499352x 6
    383550x 7
     52243x 8
      6340x 9
       699x 10
        74x 11
         5x 12
         1x 13

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.

With ct's input domain, i.e. ipv4saddr^ipv4daddr, a 32-bit quantity, 
~1.59G OVs are never reachable/obtainable ("holes") no matter which IVs 
are chosen. The more these 1.59G points agglomerate together, the higher 
the chance that some queue will not be used (with the multiplication 
approach), of course.

If the 1.59G holes are uniformly distributed across the 32-bit space, a 
CDF-like plot would output a straight line. Alternatively, one can 
calculate the difference instead for visual output:

http://picpaste.de/jenkins3.png

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.

===

Bottom line: modulus is resistant to hole agglomeration, and only 
problematic with certain patterns of uniform hole distribution 
(which in 
turn would be a sign that the hash function is bad).

--
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

Re: [PATCH] netfilter: remove modulo operations

[Maciej Żenczykowski]

> 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

Re: [PATCH] netfilter: remove modulo operations

[Jan Engelhardt]

On Monday 2010-10-25 05:19, Maciej Żenczykowski wrote:

>> 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.

See the code at the end of the mail; that will probably help some 
people more than my description.

>> 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.

Well, the hash function is not necessarily bad, it just is not a 
perfect hash function for the given input domain.
--
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

Re: [PATCH] netfilter: remove modulo operations

[Jan Engelhardt]

On Monday 2010-10-25 11:13, Jan Engelhardt wrote:

>On Monday 2010-10-25 05:19, Maciej Żenczykowski wrote:
>
>>> 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.
>
>See the code at the end of the mail; that will probably help some 
>people more than my description.

/* calculate all possible 32-bit hashes
   needs 16G of address space, so better have a 64-bit kernel at hand
 */
#define _GNU_SOURCE 1
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(*(x)))
#define S_IRUGO (S_IRUSR | S_IRGRP | S_IROTH)
#define S_IWUGO (S_IWUSR | S_IWGRP | S_IWOTH)

#define jrot(x,k) (((x) << (k)) | ((x) >> (32 - (k))))

/* jhash_mix - mix 3 32-bit values reversibly. */
#define jhash_mix(a, b, c) { \
	a -= c; a ^= jrot(c,  4); c += b; \
	b -= a; b ^= jrot(a,  6); a += c; \
	c -= b; c ^= jrot(b,  8); b += a; \
	a -= c; a ^= jrot(c, 16); c += b; \
	b -= a; b ^= jrot(a, 19); a += c; \
	c -= b; c ^= jrot(b,  4); b += a; \
}

#define jhash_final(a, b, c) { \
	c ^= b; c -= jrot(b, 14); \
	a ^= c; a -= jrot(c, 11); \
	b ^= a; b -= jrot(a, 25); \
	c ^= b; c -= jrot(b, 16); \
	a ^= c; a -= jrot(c,  4);  \
	b ^= a; b -= jrot(a, 14); \
	c ^= b; c -= jrot(b, 24); \
}

static uint32_t hash_jlookup3(const void *vkey, size_t length)
{
	static const unsigned int JHASH_GOLDEN_RATIO = 0x9e3779b9;
	const uint8_t *key = vkey;
	uint32_t a, b, c;

	a = b = c = JHASH_GOLDEN_RATIO + length;
	/* All but the last block: affect some 32 bits of (a,b,c) */
	for (; length > 12; length -= 12, key += 12) {
		a += key[0] + ((uint32_t)key[1] << 8) +
		     ((uint32_t)key[2] << 16) + ((uint32_t)key[3] << 24);
		b += key[4] + ((uint32_t)key[5] << 8) +
		     ((uint32_t)key[6] << 16) + ((uint32_t)key[7] << 24);
		c += key[8] + ((uint32_t)key[9] << 8) +
		     ((uint32_t)key[10] << 16)+ ((uint32_t)key[11] << 24);
		jhash_mix(a, b, c);
	}

	switch (length) {
	case 12: c += ((uint32_t)key[11]) << 24;
	case 11: c += ((uint32_t)key[10]) << 16;
	case 10: c += ((uint32_t)key[9])  << 8;
	case  9: c += key[8];
	case  8: b += ((uint32_t)key[7]) << 24;
	case  7: b += ((uint32_t)key[6]) << 16;
	case  6: b += ((uint32_t)key[5]) << 8;
	case  5: b += key[4];
	case  4: a += ((uint32_t)key[3]) << 24;
	case  3: a += ((uint32_t)key[2]) << 16;
	case  2: a += ((uint32_t)key[1]) << 8;
	case  1: a += key[0];
		break;
	case  0: return c;
	}

	jhash_final(a,b,c);
	return c;
}

static uint32_t hash_djb2(const void *p, size_t z)
{
	const char *c = p;
	unsigned long v = 5381;

	while (*c != '\0')
		v = ((v << 5) + v) ^ *c++;
		/* v = v * 33 ^ *c++; */

	return v;
}

static uint32_t *freq;
static const unsigned long long freq_size = 0x100000000UL * sizeof(*freq);

static void map_freq(void)
{
	int fd;

	fd = open("jenkins3.frq", O_RDWR | O_CREAT, S_IRUGO | S_IWUGO);
	if (fd < 0) {
		perror("open");
		abort();
	}

	if (ftruncate(fd, freq_size) < 0) {
		perror("ftruncate");
		abort();
	}

	freq = mmap(NULL, freq_size, PROT_READ | PROT_WRITE,
	       MAP_SHARED, fd, 0);
	if (freq == NULL) {
		perror("mmap");
		abort();
	}
}

static void malloc_freq(void)
{
	freq = malloc(freq_size);
	if (freq == NULL) {
		perror("malloc");
		abort();
	}
}

static inline void calc_all_hashes(void)
{
	uint32_t x, y;

	memset(freq, 0, freq_size);
	for (x = 0; x < UINT32_MAX; ++x) {
		if ((x & 0xFFFFF) == 0)
			fprintf(stderr, "\r\e[2K""fill: %08x", x);
		y = hash_jlookup3(&x, sizeof(x));
		if (freq[y] < UINT32_MAX)
			++freq[y];
	}
}

static void freq_chart(void)
{
	uint32_t dist[32];
	uint32_t x;

	for (x = 0; x < UINT32_MAX; ++x) {
		if ((x & 0xFFFFFF) == 0)
			fprintf(stderr, "\r\e[2K""%s: %08x", __func__, x);
		if (freq[x] >= ARRAY_SIZE(dist))
			printf("\nHash %08x reachable by %u input values\n",
			       x, dist[x]);
		if (dist[freq[x]] < UINT32_MAX)
			++dist[freq[x]];
	}
	if (freq[UINT32_MAX] < ARRAY_SIZE(dist) &&
	    dist[freq[UINT32_MAX]] < UINT16_MAX)
		++dist[freq[UINT32_MAX]];

	fprintf(stderr, "\n----\n");
	for (x = 0; x < ARRAY_SIZE(dist); ++x)
		printf("%10ux %u\n", dist[x], x);
}

static void xy_plot(void)
{
	uint32_t x, r = 0;

	printf("# x y\n");
	for (x = 0; x < UINT32_MAX; ++x) {
		r += freq[x];
		if ((x & 0xFFFFF) == 0)
			printf("%u %u\n", x, r);
	}
}

int main(int argc, const char **argv)
{
	step = (argc >= 2) ? strtoul(argv[1], NULL, 0) : 0;
//	map_freq();
	malloc_freq();
	calc_all_hashes();
	if (step == 1)
		freq_chart();
	else if (step == 2)
		xy_plot();
	return 0;
}
--
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

Re: [PATCH] netfilter: remove modulo operations

[Eric Dumazet]

Le dimanche 24 octobre 2010 à 11:40 +0800, Changli Gao a écrit :
> Signed-off-by: Changli Gao <xiaosuo@gmail.com>
> ---
>  net/netfilter/xt_NFQUEUE.c |    6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
> diff --git a/net/netfilter/xt_NFQUEUE.c b/net/netfilter/xt_NFQUEUE.c
> index 039cce1..3962770 100644
> --- a/net/netfilter/xt_NFQUEUE.c
> +++ b/net/netfilter/xt_NFQUEUE.c
> @@ -72,10 +72,12 @@ nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par)
>  
>  	if (info->queues_total > 1) {
>  		if (par->family == NFPROTO_IPV4)
> -			queue = hash_v4(skb) % info->queues_total + queue;
> +			queue = (((u64) hash_v4(skb) * info->queues_total) >>
> +				 32) + queue;
>  #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)
>  		else if (par->family == NFPROTO_IPV6)
> -			queue = hash_v6(skb) % info->queues_total + queue;
> +			queue = (((u64) hash_v6(skb) * info->queues_total) >>
> +				 32) + queue;
>  #endif
>  	}
>  	return NF_QUEUE_NR(queue);


Acked-by: Eric Dumazet <eric.dumazet@gmail.com>

Maybe its time to add a new helper in include/linux/reciprocal_div.h
to make this trick documented...



--
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

Re: [PATCH] netfilter: remove modulo operations

[Patrick McHardy]

Am 25.10.2010 11:26, schrieb Eric Dumazet:
> Le dimanche 24 octobre 2010 à 11:40 +0800, Changli Gao a écrit :
>> Signed-off-by: Changli Gao <xiaosuo@gmail.com>
>> ---
>>  net/netfilter/xt_NFQUEUE.c |    6 ++++--
>>  1 file changed, 4 insertions(+), 2 deletions(-)
>> diff --git a/net/netfilter/xt_NFQUEUE.c b/net/netfilter/xt_NFQUEUE.c
>> index 039cce1..3962770 100644
>> --- a/net/netfilter/xt_NFQUEUE.c
>> +++ b/net/netfilter/xt_NFQUEUE.c
>> @@ -72,10 +72,12 @@ nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par)
>>  
>>  	if (info->queues_total > 1) {
>>  		if (par->family == NFPROTO_IPV4)
>> -			queue = hash_v4(skb) % info->queues_total + queue;
>> +			queue = (((u64) hash_v4(skb) * info->queues_total) >>
>> +				 32) + queue;
>>  #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)
>>  		else if (par->family == NFPROTO_IPV6)
>> -			queue = hash_v6(skb) % info->queues_total + queue;
>> +			queue = (((u64) hash_v6(skb) * info->queues_total) >>
>> +				 32) + queue;
>>  #endif
>>  	}
>>  	return NF_QUEUE_NR(queue);
> 
> 
> Acked-by: Eric Dumazet <eric.dumazet@gmail.com>

This looks fine to me, however I'm currently only taking bugfixes.
Please resend once net-next opens up for new patches again.
--
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