Skip to contentSkip to conversation

netfilter: remove modulo operations

PATCH Superseded Changli Gao 6 participants 11 messages Oct 24, 2010 – Oct 25, 2010

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 netfilter: remove modulo operations

---
 net/netfilter/xt_NFQUEUE.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/netfilter/xt_NFQUEUE.c +4 -2
index 039cce1..3962770 100644
@@ -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);
maintainer
#1 lore raw
Quoted 9 lines · Changli Gao
---
 net/netfilter/xt_NFQUEUE.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/netfilter/xt_NFQUEUE.c +0 -0
index 039cce1..3962770 100644

net/netfilter/xt_NFQUEUE.c nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par) · line 76

Quoted 6 lines
net/netfilter/xt_NFQUEUE.c +2 -1
@@ -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?

#2 lore raw
Quoted 3 lines · Florian Westphal

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.

Quoted 1 line

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

maintainer
#3 lore raw
Quoted 5 lines · Eric Dumazet
Quoted 3 lines · Florian Westphal

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

Quoted 8 lines

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

Quoted 1 line

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#4 lore raw
In reply to Eric Dumazet
Quoted 1 line

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.

#5 lore raw
In reply to Eric Dumazet
Quoted 5 lines · Eric Dumazet
Quoted 2 lines · Florian Westphal

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

Quoted 8 lines

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

Quoted 1 line

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#6 lore raw
Quoted 3 lines

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.

Quoted 8 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#7 lore raw
Quoted 5 lines · Maciej Żenczykowski
Quoted 3 lines

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.

Quoted 10 lines
Quoted 8 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#8 lore raw
Quoted 10 lines · Jan Engelhardt
Quoted 5 lines · Maciej Żenczykowski
Quoted 3 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Acked-by on v1 1/1
#9 lore raw
In reply to Changli Gao
Quoted 13 lines · Changli Gao
---
 net/netfilter/xt_NFQUEUE.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/netfilter/xt_NFQUEUE.c +0 -1
index 039cce1..3962770 100644
@@ -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;

net/netfilter/xt_NFQUEUE.c nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par) · line 83

Quoted 10 lines
net/netfilter/xt_NFQUEUE.c +4 -1
+			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);

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#10 lore raw

Am 25.10.2010 11:26, schrieb Eric Dumazet:

Quoted 11 lines · Changli Gao
Quoted 10 lines
---
 net/netfilter/xt_NFQUEUE.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/netfilter/xt_NFQUEUE.c +0 -0
index 039cce1..3962770 100644
@@ -72,10 +72,12 @@ nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par)
 
Quoted 16 lines

net/netfilter/xt_NFQUEUE.c nfqueue_tg_v1(struct sk_buff *skb, const struct xt_action_param *par) · line 83

Quoted 13 lines
net/netfilter/xt_NFQUEUE.c +4 -2
 	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);

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html