[PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[David Miller]

People who use PACKET_FANOUT_HASH want a symmetric hash, meaning that
they want packets going in both directions on a flow to hash to the
same bucket.

The core kernel SKB hash became non-symmetric when the ipv6 flow label
and other entities were incorporated into the standard flow hash order
to increase entropy.

But there are no users of PACKET_FANOUT_HASH who want an assymetric
hash, they all want a symmetric one.

Therefore, use the flow dissector to compute a flat symmetric hash
over only the protocol, addresses and ports.  This hash does not get
installed into and override the normal skb hash, so this change has
no effect whatsoever on the rest of the stack.

Reported-by: Eric Leblond <eric@regit.org>
Tested-by: Eric Leblond <eric@regit.org>
Signed-off-by: David S. Miller <davem@davemloft.net>
---

I'll be pushing this to -stable branches as well.

 include/linux/skbuff.h    |  1 +
 net/core/flow_dissector.c | 43 +++++++++++++++++++++++++++++++++++++++++++
 net/packet/af_packet.c    |  2 +-
 3 files changed, 45 insertions(+), 1 deletion(-)

diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
index ee38a41..24859d4 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
@@ -1062,6 +1062,7 @@ __skb_set_sw_hash(struct sk_buff *skb, __u32 hash, bool is_l4)
 }
 
 void __skb_get_hash(struct sk_buff *skb);
+u32 __skb_get_hash_symmetric(struct sk_buff *skb);
 u32 skb_get_poff(const struct sk_buff *skb);
 u32 __skb_get_poff(const struct sk_buff *skb, void *data,
 		   const struct flow_keys *keys, int hlen);
diff --git a/net/core/flow_dissector.c b/net/core/flow_dissector.c
index a669dea..61ad43f 100644
--- a/net/core/flow_dissector.c
+++ b/net/core/flow_dissector.c
@@ -651,6 +651,23 @@ void make_flow_keys_digest(struct flow_keys_digest *digest,
 }
 EXPORT_SYMBOL(make_flow_keys_digest);
 
+static struct flow_dissector flow_keys_dissector_symmetric __read_mostly;
+
+u32 __skb_get_hash_symmetric(struct sk_buff *skb)
+{
+	struct flow_keys keys;
+
+	__flow_hash_secret_init();
+
+	memset(&keys, 0, sizeof(keys));
+	__skb_flow_dissect(skb, &flow_keys_dissector_symmetric, &keys,
+			   NULL, 0, 0, 0,
+			   FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL);
+
+	return __flow_hash_from_keys(&keys, hashrnd);
+}
+EXPORT_SYMBOL_GPL(__skb_get_hash_symmetric);
+
 /**
  * __skb_get_hash: calculate a flow hash
  * @skb: sk_buff to calculate flow hash from
@@ -868,6 +885,29 @@ static const struct flow_dissector_key flow_keys_dissector_keys[] = {
 	},
 };
 
+static const struct flow_dissector_key flow_keys_dissector_symmetric_keys[] = {
+	{
+		.key_id = FLOW_DISSECTOR_KEY_CONTROL,
+		.offset = offsetof(struct flow_keys, control),
+	},
+	{
+		.key_id = FLOW_DISSECTOR_KEY_BASIC,
+		.offset = offsetof(struct flow_keys, basic),
+	},
+	{
+		.key_id = FLOW_DISSECTOR_KEY_IPV4_ADDRS,
+		.offset = offsetof(struct flow_keys, addrs.v4addrs),
+	},
+	{
+		.key_id = FLOW_DISSECTOR_KEY_IPV6_ADDRS,
+		.offset = offsetof(struct flow_keys, addrs.v6addrs),
+	},
+	{
+		.key_id = FLOW_DISSECTOR_KEY_PORTS,
+		.offset = offsetof(struct flow_keys, ports),
+	},
+};
+
 static const struct flow_dissector_key flow_keys_buf_dissector_keys[] = {
 	{
 		.key_id = FLOW_DISSECTOR_KEY_CONTROL,
@@ -889,6 +929,9 @@ static int __init init_default_flow_dissectors(void)
 	skb_flow_dissector_init(&flow_keys_dissector,
 				flow_keys_dissector_keys,
 				ARRAY_SIZE(flow_keys_dissector_keys));
+	skb_flow_dissector_init(&flow_keys_dissector_symmetric,
+				flow_keys_dissector_symmetric_keys,
+				ARRAY_SIZE(flow_keys_dissector_symmetric_keys));
 	skb_flow_dissector_init(&flow_keys_buf_dissector,
 				flow_keys_buf_dissector_keys,
 				ARRAY_SIZE(flow_keys_buf_dissector_keys));
diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c
index 9bff6ef..9f0983f 100644
--- a/net/packet/af_packet.c
+++ b/net/packet/af_packet.c
@@ -1341,7 +1341,7 @@ static unsigned int fanout_demux_hash(struct packet_fanout *f,
 				      struct sk_buff *skb,
 				      unsigned int num)
 {
-	return reciprocal_scale(skb_get_hash(skb), num);
+	return reciprocal_scale(__skb_get_hash_symmetric(skb), num);
 }
 
 static unsigned int fanout_demux_lb(struct packet_fanout *f,
-- 
2.5.5

Re: [PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[Tom Herbert]

On Fri, Jul 1, 2016 at 1:08 PM, David Miller <davem@davemloft.net> wrote:
>
> People who use PACKET_FANOUT_HASH want a symmetric hash, meaning that
> they want packets going in both directions on a flow to hash to the
> same bucket.
>
> The core kernel SKB hash became non-symmetric when the ipv6 flow label
> and other entities were incorporated into the standard flow hash order
> to increase entropy.
>
> But there are no users of PACKET_FANOUT_HASH who want an assymetric
> hash, they all want a symmetric one.
>
> Therefore, use the flow dissector to compute a flat symmetric hash
> over only the protocol, addresses and ports.  This hash does not get
> installed into and override the normal skb hash, so this change has
> no effect whatsoever on the rest of the stack.
>
This doesn't work for any of the UDP encapsulations, packets of an
encapsulated flow will still have asymmetric hashes.

Why are symmetric hashes required?

Tom

> Reported-by: Eric Leblond <eric@regit.org>
> Tested-by: Eric Leblond <eric@regit.org>
> Signed-off-by: David S. Miller <davem@davemloft.net>
> ---
>
> I'll be pushing this to -stable branches as well.
>
>  include/linux/skbuff.h    |  1 +
>  net/core/flow_dissector.c | 43 +++++++++++++++++++++++++++++++++++++++++++
>  net/packet/af_packet.c    |  2 +-
>  3 files changed, 45 insertions(+), 1 deletion(-)
>
> diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
> index ee38a41..24859d4 100644
> --- a/include/linux/skbuff.h
> +++ b/include/linux/skbuff.h
> @@ -1062,6 +1062,7 @@ __skb_set_sw_hash(struct sk_buff *skb, __u32 hash, bool is_l4)
>  }
>
>  void __skb_get_hash(struct sk_buff *skb);
> +u32 __skb_get_hash_symmetric(struct sk_buff *skb);
>  u32 skb_get_poff(const struct sk_buff *skb);
>  u32 __skb_get_poff(const struct sk_buff *skb, void *data,
>                    const struct flow_keys *keys, int hlen);
> diff --git a/net/core/flow_dissector.c b/net/core/flow_dissector.c
> index a669dea..61ad43f 100644
> --- a/net/core/flow_dissector.c
> +++ b/net/core/flow_dissector.c
> @@ -651,6 +651,23 @@ void make_flow_keys_digest(struct flow_keys_digest *digest,
>  }
>  EXPORT_SYMBOL(make_flow_keys_digest);
>
> +static struct flow_dissector flow_keys_dissector_symmetric __read_mostly;
> +
> +u32 __skb_get_hash_symmetric(struct sk_buff *skb)
> +{
> +       struct flow_keys keys;
> +
> +       __flow_hash_secret_init();
> +
> +       memset(&keys, 0, sizeof(keys));
> +       __skb_flow_dissect(skb, &flow_keys_dissector_symmetric, &keys,
> +                          NULL, 0, 0, 0,
> +                          FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL);
> +
> +       return __flow_hash_from_keys(&keys, hashrnd);
> +}
> +EXPORT_SYMBOL_GPL(__skb_get_hash_symmetric);
> +
>  /**
>   * __skb_get_hash: calculate a flow hash
>   * @skb: sk_buff to calculate flow hash from
> @@ -868,6 +885,29 @@ static const struct flow_dissector_key flow_keys_dissector_keys[] = {
>         },
>  };
>
> +static const struct flow_dissector_key flow_keys_dissector_symmetric_keys[] = {
> +       {
> +               .key_id = FLOW_DISSECTOR_KEY_CONTROL,
> +               .offset = offsetof(struct flow_keys, control),
> +       },
> +       {
> +               .key_id = FLOW_DISSECTOR_KEY_BASIC,
> +               .offset = offsetof(struct flow_keys, basic),
> +       },
> +       {
> +               .key_id = FLOW_DISSECTOR_KEY_IPV4_ADDRS,
> +               .offset = offsetof(struct flow_keys, addrs.v4addrs),
> +       },
> +       {
> +               .key_id = FLOW_DISSECTOR_KEY_IPV6_ADDRS,
> +               .offset = offsetof(struct flow_keys, addrs.v6addrs),
> +       },
> +       {
> +               .key_id = FLOW_DISSECTOR_KEY_PORTS,
> +               .offset = offsetof(struct flow_keys, ports),
> +       },
> +};
> +
>  static const struct flow_dissector_key flow_keys_buf_dissector_keys[] = {
>         {
>                 .key_id = FLOW_DISSECTOR_KEY_CONTROL,
> @@ -889,6 +929,9 @@ static int __init init_default_flow_dissectors(void)
>         skb_flow_dissector_init(&flow_keys_dissector,
>                                 flow_keys_dissector_keys,
>                                 ARRAY_SIZE(flow_keys_dissector_keys));
> +       skb_flow_dissector_init(&flow_keys_dissector_symmetric,
> +                               flow_keys_dissector_symmetric_keys,
> +                               ARRAY_SIZE(flow_keys_dissector_symmetric_keys));
>         skb_flow_dissector_init(&flow_keys_buf_dissector,
>                                 flow_keys_buf_dissector_keys,
>                                 ARRAY_SIZE(flow_keys_buf_dissector_keys));
> diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c
> index 9bff6ef..9f0983f 100644
> --- a/net/packet/af_packet.c
> +++ b/net/packet/af_packet.c
> @@ -1341,7 +1341,7 @@ static unsigned int fanout_demux_hash(struct packet_fanout *f,
>                                       struct sk_buff *skb,
>                                       unsigned int num)
>  {
> -       return reciprocal_scale(skb_get_hash(skb), num);
> +       return reciprocal_scale(__skb_get_hash_symmetric(skb), num);
>  }
>
>  static unsigned int fanout_demux_lb(struct packet_fanout *f,
> --
> 2.5.5
>

Re: [PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[David Miller]

From: Tom Herbert <tom@herbertland.com>
Date: Fri, 1 Jul 2016 13:52:58 -0700

> Why are symmetric hashes required?

Because they want load balancing, such that one flow only can overrun
one single socket not all of the ones in the fanout.

Every single user of AF_PACKET fanout wants this behavior.

Re: [PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[Tom Herbert]

On Fri, Jul 1, 2016 at 2:07 PM, David Miller <davem@davemloft.net> wrote:
> From: Tom Herbert <tom@herbertland.com>
> Date: Fri, 1 Jul 2016 13:52:58 -0700
>
>> Why are symmetric hashes required?
>
> Because they want load balancing, such that one flow only can overrun
> one single socket not all of the ones in the fanout.
>
I'm still missing it. Why is this any different than what we need with
something like SO_REUSEPORT?

> Every single user of AF_PACKET fanout wants this behavior.

Re: [PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[David Miller]

From: Tom Herbert <tom@herbertland.com>
Date: Fri, 1 Jul 2016 14:16:54 -0700

> On Fri, Jul 1, 2016 at 2:07 PM, David Miller <davem@davemloft.net> wrote:
>> From: Tom Herbert <tom@herbertland.com>
>> Date: Fri, 1 Jul 2016 13:52:58 -0700
>>
>>> Why are symmetric hashes required?
>>
>> Because they want load balancing, such that one flow only can overrun
>> one single socket not all of the ones in the fanout.
>>
> I'm still missing it. Why is this any different than what we need with
> something like SO_REUSEPORT?

Because local sockets only demux on RX packets for a flow so they
don't need a symmetric hash, and in fact wouldn't even notice if the
hash was symmetric or not.

Programs like suricata that are operating as a bump in the stack see
both directions of traffic for a flow and therefore for them whether
the hash is symmetric is an issue.

Re: [PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[Victor Julien]

On 02-07-16 22:38, David Miller wrote:
> From: Tom Herbert <tom@herbertland.com>
> Date: Fri, 1 Jul 2016 14:16:54 -0700
> 
>> On Fri, Jul 1, 2016 at 2:07 PM, David Miller <davem@davemloft.net> wrote:
>>> From: Tom Herbert <tom@herbertland.com>
>>> Date: Fri, 1 Jul 2016 13:52:58 -0700
>>>
>>>> Why are symmetric hashes required?
>>>
>>> Because they want load balancing, such that one flow only can overrun
>>> one single socket not all of the ones in the fanout.
>>>
>> I'm still missing it. Why is this any different than what we need with
>> something like SO_REUSEPORT?
> 
> Because local sockets only demux on RX packets for a flow so they
> don't need a symmetric hash, and in fact wouldn't even notice if the
> hash was symmetric or not.
> 
> Programs like suricata that are operating as a bump in the stack see
> both directions of traffic for a flow and therefore for them whether
> the hash is symmetric is an issue.

Tools like Suricata, Bro, Snort, netsniff-ng are often used to sit on
the side and receive a copy of the traffic from a tap or span port. This
leads to both sides of connections coming in on the RX side. As the said
tools often rely on the hashing for load balancing to multiple
threads/processes, the hashing should be done symmetrically.

-- 
---------------------------------------------
Victor Julien
http://www.inliniac.net/
PGP: http://www.inliniac.net/victorjulien.asc
---------------------------------------------

Re: [PATCH] packet: Use symmetric hash for PACKET_FANOUT_HASH.

[Hannes Frederic Sowa]

On 01.07.2016 22:08, David Miller wrote:
> 
> People who use PACKET_FANOUT_HASH want a symmetric hash, meaning that
> they want packets going in both directions on a flow to hash to the
> same bucket.
> 
> The core kernel SKB hash became non-symmetric when the ipv6 flow label
> and other entities were incorporated into the standard flow hash order
> to increase entropy.
> 
> But there are no users of PACKET_FANOUT_HASH who want an assymetric
> hash, they all want a symmetric one.
> 
> Therefore, use the flow dissector to compute a flat symmetric hash
> over only the protocol, addresses and ports.  This hash does not get
> installed into and override the normal skb hash, so this change has
> no effect whatsoever on the rest of the stack.
> 
> Reported-by: Eric Leblond <eric@regit.org>
> Tested-by: Eric Leblond <eric@regit.org>
> Signed-off-by: David S. Miller <davem@davemloft.net>
> ---
> 
> I'll be pushing this to -stable branches as well.

Acked-by: Hannes Frederic Sowa <hannes@stressinduktion.org>

Actually a funny trick I learned from DragonflyBSD sources is to just
randomize the first two bytes of the rss key and replicate them to fill
up the the last 38 bytes (or more). Doing so makes the rss hash
generation on the networking card symmetric [1].

Bye,
Hannes

[1]
http://gitweb.dragonflybsd.org/dragonfly.git/blob/HEAD:/sys/net/toeplitz.c#l41