net: Strengthen TX and RX hashes
Subsystems (5)
cover net: Strengthen TX and RX hashes
Both the TX and RX hashes associated with skb->hash are mostly 4-tuple hashes. This is potentially problematic. For instance one could concieve of a DOS attack against a TCP connection using UDP with same 4-tuple. Most switches already use at least a 5-tuple hash, NICs probably should also (for instance Toeplitz hash for UDP could include UDP protocol number). This patch set implements 5-tuple hashes in the stack.
For transmit, we simply initialize sk_hash to a random value instead of performing any actual hash computation. A random value should provide full 32-bits of entropy and ensure that connected sockets have a different hash value regardless of protocol, 4-tuple, network namespace, etc. sock_init_txhash was created to provide this. This also can be called for any family not just IP.
For receive, we add a new field in flow_keys called hash_extra. When doing the jhash this value is XORed into the destination address field. In flow_dissector, the IP protocol is placed in this field so that we get a 5-tuple hash.
Also, in flow_dissector, we add support for including VLAN ID and GRE keyid in the hash (via hash_extra). We implement support for extracting a hash from MPLS entropy labels (RFC 6790).
Tom Herbert (6):
net: initialize sk_txhash using random value
flow_dissector: Include ip_proto in hash computation
flow_dissector: Add hash_extra field to flow_keys struct
flow_dissector: Include VLAN ID in hash computation
flow_dissector: Include GRE keyid in hash computation
flow_dissector: Include MPLS entropy label in hash computation
include/net/flow_keys.h | 1 + include/net/ip.h | 13 ------------- include/net/ipv6.h | 14 -------------- include/net/sch_generic.h | 2 +- include/net/sock.h | 6 ++++++ include/uapi/linux/in.h | 2 ++ include/uapi/linux/mpls.h | 3 +++ net/core/flow_dissector.c | 44 ++++++++++++++++++++++++++++++++++++++++++-- net/ipv4/datagram.c | 2 +- net/ipv4/tcp_ipv4.c | 4 ++-- net/ipv6/datagram.c | 2 +- net/ipv6/tcp_ipv6.c | 4 ++-- 12 files changed, 61 insertions(+), 36 deletions(-)
Signature · 1 line
2.2.0.rc0.207.ga3a616c
PATCH 1/6 net: initialize sk_txhash using random value
This patch creates sock_init_txhash which simply intializes sk_txhash to a random value. This satisfies the entropy requirements of the hash and is stronger than old method of doing flow_hash_from_keys. This function can be called for any type of connected socket, and will generate different hash values for same 4-tuple across different IP protocols or namespaces.
--- include/net/ip.h | 13 ------------- include/net/ipv6.h | 14 -------------- include/net/sock.h | 6 ++++++ net/ipv4/datagram.c | 2 +- net/ipv4/tcp_ipv4.c | 4 ++-- net/ipv6/datagram.c | 2 +- net/ipv6/tcp_ipv6.c | 4 ++-- 7 files changed, 12 insertions(+), 33 deletions(-)
include/net/ip.h +0 -13
@@ -352,19 +352,6 @@ static inline __wsum inet_compute_pseudo(struct sk_buff *skb, int proto) skb->len, proto, 0); } -static inline void inet_set_txhash (struct sock *sk) -{ -struct inet_sock *inet =inet_sk (sk); -struct flow_keys keys; - - keys.src = inet->inet_saddr; - keys.dst = inet->inet_daddr; - keys.port16[0 ] = inet->inet_sport; - keys.port16[1 ] = inet->inet_dport; - - sk->sk_txhash =flow_hash_from_keys (&keys); -} -static inline __wsum inet_gro_compute_pseudo (struct sk_buff *skb,int proto) {const struct iphdr *iph =skb_gro_network_header (skb);
include/net/ipv6.h +0 -14
@@ -691,20 +691,6 @@ static inline int ip6_sk_dst_hoplimit(struct ipv6_pinfo *np, struct flowi6 *fl6, }#if IS_ENABLED (CONFIG_IPV6 ) -static inline void ip6_set_txhash (struct sock *sk) -{ -struct inet_sock *inet =inet_sk (sk); -struct ipv6_pinfo *np =inet6_sk (sk); -struct flow_keys keys; - - keys.src = (__force __be32 )ipv6_addr_hash (&np->saddr); - keys.dst = (__force __be32 )ipv6_addr_hash (&sk->sk_v6_daddr); - keys.port16[0 ] = inet->inet_sport; - keys.port16[1 ] = inet->inet_dport; - - sk->sk_txhash =flow_hash_from_keys (&keys); -} -static inline __be32 ip6_make_flowlabel (struct net *net,struct sk_buff *skb,__be32 flowlabel,bool autolabel) {
include/net/sock.h +6 -0
@@ -56,6 +56,7 @@#include <linux/uaccess.h> #include <linux/page_counter.h> #include <linux/memcontrol.h> +#include <linux/random.h> #include <linux/static_key.h> #include <linux/aio.h> #include <linux/sched.h>
@@ -880,6 +881,11 @@ static inline void sock_rps_reset_rxhash(struct sock *sk)#endif } +static inline void sock_init_txhash (struct sock *sk) +{ + sk->sk_txhash =prandom_u32 (); +} +#define sk_wait_event (__sk, __timeo, __condition) \ ({ int __rc; \ release_sock(__sk); \
net/ipv4/datagram.c +1 -1
@@ -76,7 +76,7 @@ int ip4_datagram_connect(struct sock *sk, struct sockaddr *uaddr, int addr_len) inet->inet_daddr = fl4->daddr; inet->inet_dport = usin->sin_port; sk->sk_state =TCP_ESTABLISHED ; -inet_set_txhash (sk); +sock_init_txhash (sk); inet->inet_id = jiffies;sk_dst_set (sk, &rt->dst);
net/ipv4/tcp_ipv4.c +2 -2
@@ -222,7 +222,7 @@ int tcp_v4_connect(struct sock *sk, struct sockaddr *uaddr, int addr_len)if (err) goto failure; -inet_set_txhash (sk); +sock_init_txhash (sk); rt =ip_route_newports (fl4, rt, orig_sport, orig_dport, inet->inet_sport, inet->inet_dport, sk);
@@ -1328,7 +1328,7 @@ struct sock *tcp_v4_syn_recv_sock(struct sock *sk, struct sk_buff *skb, newinet->mc_ttl =ip_hdr (skb)->ttl; newinet->rcv_tos =ip_hdr (skb)->tos;inet_csk (newsk)->icsk_ext_hdr_len =0 ; -inet_set_txhash (newsk); +sock_init_txhash (newsk);if (inet_opt)inet_csk (newsk)->icsk_ext_hdr_len = inet_opt->opt.optlen; newinet->inet_id = newtp->write_seq ^ jiffies;
net/ipv6/datagram.c +1 -1
@@ -199,7 +199,7 @@ ipv4_connected: NULL); sk->sk_state =TCP_ESTABLISHED ; -ip6_set_txhash (sk); +sock_init_txhash (sk); out:fl6_sock_release (flowlabel);return err;
net/ipv6/tcp_ipv6.c +2 -2
@@ -295,7 +295,7 @@ static int tcp_v6_connect(struct sock *sk, struct sockaddr *uaddr,if (err) goto late_failure; -ip6_set_txhash (sk); +sock_init_txhash (sk);if (!tp->write_seq &&likely (!tp->repair)) tp->write_seq = secure_tcpv6_sequence_number(np->saddr.s6_addr32,
@@ -1155,7 +1155,7 @@ static struct sock *tcp_v6_syn_recv_sock(struct sock *sk, struct sk_buff *skb, newsk->sk_v6_rcv_saddr = ireq->ir_v6_loc_addr; newsk->sk_bound_dev_if = ireq->ir_iif; -ip6_set_txhash (newsk); +sock_init_txhash (newsk);/* Now IPv6 options...
Signature · 1 line
2.2.0.rc0.207.ga3a616c
PATCH 2/6 flow_dissector: Include ip_proto in hash computation
In reply to Tom HerbertFold ip_proto into dst when computing hash. This provides a more standard 5-tuple hash.
--- net/core/flow_dissector.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
net/core/flow_dissector.c +3 -1
@@ -276,6 +276,7 @@ static __always_inline u32 __flow_hash_3words(u32 a, u32 b, u32 c)static inline u32 __flow_hash_from_keys (struct flow_keys *keys) {u32 hash; +u32 extra;/* get a consistent hash (same value on both flow directions) */ if (((__force u32)keys->dst < (__force u32)keys->src) ||
@@ -285,7 +286,8 @@ static inline u32 __flow_hash_from_keys(struct flow_keys *keys)swap (keys->port16[0 ], keys->port16[1 ]); } - hash =__flow_hash_3words ((__force u32 )keys->dst, + extra = keys->ip_proto; + hash =__flow_hash_3words ((__force u32 )keys->dst ^ extra, (__force u32 )keys->src, (__force u32 )keys->ports);if (!hash)
Signature · 1 line
2.2.0.rc0.207.ga3a616c
PATCH 3/6 flow_dissector: Add hash_extra field to flow_keys struct
In reply to Tom HerbertThis will be used for additional input into the hash computation such as VLAN ID or GRE keyid.
--- include/net/flow_keys.h | 1 + include/net/sch_generic.h | 2 +- net/core/flow_dissector.c | 2 +- 3 files changed, 3 insertions(+), 2 deletions(-)
include/net/flow_keys.h +1 -0
@@ -24,6 +24,7 @@ struct flow_keys { };u16 thoff;__be16 n_proto; +__be32 hash_extra;u8 ip_proto; };
include/net/sch_generic.h +1 -1
@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };
net/core/flow_dissector.c +1 -1
@@ -286,7 +286,7 @@ static inline u32 __flow_hash_from_keys(struct flow_keys *keys)swap (keys->port16[0 ], keys->port16[1 ]); } - extra = keys->ip_proto; + extra = keys->ip_proto ^ keys->hash_extra; hash =__flow_hash_3words ((__force u32 )keys->dst ^ extra, (__force u32 )keys->src, (__force u32 )keys->ports);
Signature · 1 line
2.2.0.rc0.207.ga3a616c
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
include/net/sch_generic.h struct qdisc_skb_cb { · line 258
Quoted 13 lines · Tom Herbert
include/net/sch_generic.h +1
-1@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };
This change breaks kernel build : We already are at the cb[] limit.
Please check commit 257117862634d89de33fec74858b1a0ba5ab444b ("net: sched: shrink struct qdisc_skb_cb to 28 bytes")
from drivers/infiniband/ulp/ipoib/ipoib_main.c:35:
In function ‘ipoib_skb_cb’,
inlined from ‘ipoib_hard_header’ at drivers/infiniband/ulp/ipoib/ipoib_main.c:816:19:include/linux/compiler.h:424:20: error: call to ‘__compiletime_assert_136’ declared with attribute error: BUILD_BUG_ON failed: sizeof(skb->cb) < sizeof(struct ipoib_cb)
prefix ## suffix(); \
^include/linux/compiler.h:429:2: note: in expansion of macro ‘__compiletime_assert’
__compiletime_assert(condition, msg, prefix, suffix)
^include/linux/compiler.h:441:2: note: in expansion of macro ‘_compiletime_assert’
_compiletime_assert(condition, msg, __compiletime_assert_, __LINE__) ^include/linux/bug.h:50:37: note: in expansion of macro ‘compiletime_assert’
#define BUILD_BUG_ON_MSG(cond, msg) compiletime_assert(!(cond), msg)
^include/linux/bug.h:74:2: note: in expansion of macro ‘BUILD_BUG_ON_MSG’
BUILD_BUG_ON_MSG(condition, "BUILD_BUG_ON failed: " #condition)
^drivers/infiniband/ulp/ipoib/ipoib.h:136:2: note: in expansion of macro ‘BUILD_BUG_ON’
BUILD_BUG_ON(sizeof(skb->cb) < sizeof(struct ipoib_cb));
^
CC drivers/parport/ieee1284.o
CC drivers/net/arcnet/arc-rawmode.o
CC drivers/misc/c2port/core.o
CC drivers/mfd/rtsx_pcr.o
In function ‘ipoib_skb_cb’,
inlined from ‘ipoib_start_xmit’ at drivers/infiniband/ulp/ipoib/ipoib_main.c:719:19:
include/linux/compiler.h:424:20: error: call to ‘__compiletime_assert_136’ declared with attribute error: BUILD_BUG_ON failed: sizeof(skb->cb) < sizeof(struct ipoib_cb)
prefix ## suffix(); \
^include/linux/compiler.h:429:2: note: in expansion of macro ‘__compiletime_assert’
__compiletime_assert(condition, msg, prefix, suffix)
^include/linux/compiler.h:441:2: note: in expansion of macro ‘_compiletime_assert’
_compiletime_assert(condition, msg, __compiletime_assert_, __LINE__) ^include/linux/bug.h:50:37: note: in expansion of macro ‘compiletime_assert’
#define BUILD_BUG_ON_MSG(cond, msg) compiletime_assert(!(cond), msg)
^include/linux/bug.h:74:2: note: in expansion of macro ‘BUILD_BUG_ON_MSG’
BUILD_BUG_ON_MSG(condition, "BUILD_BUG_ON failed: " #condition)
^drivers/infiniband/ulp/ipoib/ipoib.h:136:2: note: in expansion of macro ‘BUILD_BUG_ON’
BUILD_BUG_ON(sizeof(skb->cb) < sizeof(struct ipoib_cb));
^
make[4]: *** [drivers/infiniband/ulp/ipoib/ipoib_main.o] Error 1 make[3]: *** [drivers/infiniband/ulp/ipoib] Error 2
make[2]: *** [drivers/infiniband/ulp] Error 2
make[1]: *** [drivers/infiniband] Error 2
make[1]: *** Waiting for unfinished jobs....
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 18 lines · Eric Dumazet
include/net/sch_generic.h struct qdisc_skb_cb { · line 258
Quoted 13 lines · Tom Herbert
include/net/sch_generic.h +1
-1@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };This change breaks kernel build : We already are at the cb[] limit.
Quoted 2 lines
Please check commit
257117862634d89de33fec74858b1a0ba5ab444b("net: sched: shrink structqdisc_skb_cbto 28 bytes")
I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
It makes sfq use a smaller flow key state.
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 25 lines · Florian Westphal
Quoted 18 lines · Eric Dumazet
include/net/sch_generic.h struct qdisc_skb_cb { · line 258
Quoted 13 lines · Tom Herbert
include/net/sch_generic.h +1
-1@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };This change breaks kernel build : We already are at the cb[] limit.
Quoted 2 lines
Please check commit
257117862634d89de33fec74858b1a0ba5ab444b("net: sched: shrink structqdisc_skb_cbto 28 bytes")I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
Quoted 7 lines
It makes sfq use a smaller flow key state.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
My concern with all this work is that you are possibly not looking at the quality of the hash
as the number of queues goes down, or the effects of adding in all this extra stuff
to the hash is, in cases where they don't exist, or are not very random.
The default, in fq_codel is 1024 queues, and that worked pretty good in monty carlo simulations, but I have always felt it could be better after we measured more real traffic - there is not a lot of information in the proto field in real traffic, and - although it has been improved - the ipv6 hash was kind of weak originally and a little odd now.
As some are attempting to deploy these hashes with 64, 32 and even 8 queues, I would hope that someone (and I can if I get the time) would look closely at avalanche effects down to these last few bits.
http://en.wikipedia.org/wiki/Avalanche_effect
Signature · 4 lines
Dave Täht Let's make wifi fast, less jittery and reliable again! https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 47 lines · Dave Taht
Quoted 25 lines · Florian Westphal
Quoted 18 lines · Eric Dumazet
include/net/sch_generic.h struct qdisc_skb_cb { · line 258
Quoted 13 lines · Tom Herbert
include/net/sch_generic.h +1
-1@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };This change breaks kernel build : We already are at the cb[] limit.
Quoted 2 lines
Please check commit
257117862634d89de33fec74858b1a0ba5ab444b("net: sched: shrink structqdisc_skb_cbto 28 bytes")I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
Quoted 7 lines
It makes sfq use a smaller flow key state.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.htmlMy concern with all this work is that you are possibly not looking at the quality of the hash
as the number of queues goes down, or the effects of adding in all this extra stuff
to the hash is, in cases where they don't exist, or are not very random.The default, in
fq_codelis 1024 queues, and that worked pretty good in monty carlo simulations, but I have always felt it could be better after we measured more real traffic - there is not a lot of information in the proto field in real traffic, and - although it has been improved - the ipv6 hash was kind of weak originally and a little odd now.
Quoted 6 lines
As some are attempting to deploy these hashes with 64, 32 and even 8 queues, I would hope that someone (and I can if I get the time) would look closely at avalanche effects down to these last few bits.
We are only increasing the input to the hash function by XOR not reducing, so it seems unlikely this could result in less entropy. In worse case extra input would might have no effect. As for the avalanche effect that is more dependent on the hash function itself. In the kernel we are using Jenkin's hash for such things, and there's a nice graphical representation for the avalanche effect in the wikipedia page:
http://en.wikipedia.org/wiki/Jenkins_hash_function
Quoted 5 lines
--
Dave Täht
Let's make wifi fast, less jittery and reliable again!https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 62 lines · Tom Herbert
Quoted 47 lines · Dave Taht
Quoted 25 lines · Florian Westphal
Quoted 18 lines · Eric Dumazet
include/net/sch_generic.h struct qdisc_skb_cb { · line 258
Quoted 13 lines · Tom Herbert
include/net/sch_generic.h +1
-1@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };This change breaks kernel build : We already are at the cb[] limit.
Quoted 2 lines
Please check commit
257117862634d89de33fec74858b1a0ba5ab444b("net: sched: shrink structqdisc_skb_cbto 28 bytes")I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
Quoted 7 lines
It makes sfq use a smaller flow key state.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.htmlMy concern with all this work is that you are possibly not looking at the quality of the hash
as the number of queues goes down, or the effects of adding in all this extra stuff
to the hash is, in cases where they don't exist, or are not very random.The default, in
fq_codelis 1024 queues, and that worked pretty good in monty carlo simulations, but I have always felt it could be better after we measured more real traffic - there is not a lot of information in the proto field in real traffic, and - although it has been improved - the ipv6 hash was kind of weak originally and a little odd now.Quoted 6 lines
As some are attempting to deploy these hashes with 64, 32 and even 8 queues, I would hope that someone (and I can if I get the time) would look closely at avalanche effects down to these last few bits.
We are only increasing the input to the hash function by XOR not reducing, so it seems unlikely this could result in less entropy. In worse case extra input would might have no effect. As for the avalanche effect that is more dependent on the hash function itself. In the kernel we are using Jenkin's hash for such things, and there's a nice graphical representation for the avalanche effect in the wikipedia page:
Quoted 1 line
I did not say you were wrong! I just said you were making me nervous. :)
Hash functions are usually evaluated by tossing random data into them and expecting random data all the way to the least significant bit.
In the networking case there is now a significant amount of data with low entropy tossed into the function. I would be happier from a theoretical perspective if you just tossed every input (like the full ipv6 addresses) into the hash itself with no xor tricks and with some care as to what low entropy sources were being used on the low order bits.
As an example, you get 2 bits of data from the remote port truly mixed in at 1024 queues, and yes, jenkins should avalanche that, but I really would prefer it be evaluated on various forms of real traffic, not random data.
And there might be other hash functions besides jenkins better or faster now. Although I have an interest in such things, I generally lack time to play with the way coool! new stuff like
http://www.burtleburtle.net/bob/hash/spooky.html
and:
https://code.google.com/p/smhasher/wiki/MurmurHash
Certainly it doesn't generally matter what hash is used, so long as it is correctly responsive to its inputs, and fast.
Quoted 6 lines
Quoted 6 lines
--
Dave Täht
Let's make wifi fast, less jittery and reliable again!https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
Signature · 4 lines
Dave Täht Let's make wifi fast, less jittery and reliable again! https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
In reply to Florian WestphalQuoted 22 lines · Florian Westphal
Quoted 18 lines · Eric Dumazet
include/net/sch_generic.h struct qdisc_skb_cb { · line 258
Quoted 13 lines · Tom Herbert
include/net/sch_generic.h +1
-1@@ -252,7 +252,7 @@ struct qdisc_skb_cb {unsigned int pkt_len;u16 slave_dev_queue_mapping;u16 _pad; -#define QDISC_CB_PRIV_LEN 20 +#define QDISC_CB_PRIV_LEN 24unsigned char data[QDISC_CB_PRIV_LEN ]; };This change breaks kernel build : We already are at the cb[] limit.
Quoted 2 lines
Please check commit
257117862634d89de33fec74858b1a0ba5ab444b("net: sched: shrink structqdisc_skb_cbto 28 bytes")
Quoted 6 lines
I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
It makes sfq use a smaller flow key state.
Alternatively, I think we might be able to eliminate the use of flow_keys and flow_dissect from the qdisc code altogether. It looks like this is only being used to determine a hash over the addresses, ports, and protocol so I am thinking that we can just call skb_get_hash for that. Will try to post some patches soon.
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 6 lines · Tom Herbert
Quoted 5 lines · Florian Westphal
I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
Quoted 7 lines
Quoted 1 line
It makes sfq use a smaller flow key state.
Alternatively, I think we might be able to eliminate the use of
flow_keysandflow_dissectfrom the qdisc code altogether. It looks like this is only being used to determine a hash over the addresses, ports, and protocol so I am thinking that we can just callskb_get_hashfor that. Will try to post some patches soon.
The problem with this is that you'll lose the secret input to jhash in sfq_hash().
assuming you have packets p1 and p2 (from different flows) with skb_get_hash(p1) == skb_get_hash(p2) those flows share same queue/bin forever as the hash pertubation will no longer work.
For sfq, hash collisions may exist as well but they'll be resolved after some time when q->perturbation (its part of hash input) is reseeded.
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 15 lines · Florian Westphal
Quoted 6 lines · Tom Herbert
Quoted 5 lines · Florian Westphal
I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
Quoted 7 lines
Quoted 1 line
It makes sfq use a smaller flow key state.
Alternatively, I think we might be able to eliminate the use of
flow_keysandflow_dissectfrom the qdisc code altogether. It looks like this is only being used to determine a hash over the addresses, ports, and protocol so I am thinking that we can just callskb_get_hashfor that. Will try to post some patches soon.
Quoted 7 lines
The problem with this is that you'll lose the secret input to jhash in
sfq_hash().assuming you have packets p1 and p2 (from different flows) with
skb_get_hash(p1)==skb_get_hash(p2)those flows share same queue/bin forever as the hash pertubation will no longer work.
We still need hash perturbation for the mapping to a small number of queues which can be done after retrieving skb_get_hash, but the probability that two different flows match perfectly in skb_get_hash() should be 1/2^32-- so are hash collisions really a concern here? Note that we already lose information in the IPv6 address fold in flow_dissect and don't include VLAN or VNID yet in the flow_keys yet, so these probably already make a greater probability in a tuple collision for sfc hash.
Quoted 2 lines
For sfq, hash collisions may exist as well but they'll be resolved after some time when
q->perturbation(its part of hash input) is reseeded.
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
Quoted 4 lines · Tom Herbert
We still need hash perturbation for the mapping to a small number of queues which can be done after retrieving
skb_get_hash, but the probability that two different flows match perfectly inskb_get_hash()should be 1/2^32-- so are hash collisions really a concern here?
I'm not concerned about accidental collisions, how predictable is skb_get_hash()? Is skb_get_hash() guaranteed to e.g. contain L4 information?
AFAIK answer to both is "depends on nic/driver", so I feel its better to use software flow dissector.
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
In reply to Florian WestphalQuoted 9 lines · Florian Westphal
Quoted 8 lines · Tom Herbert
Quoted 6 lines · Florian Westphal
I've been toying around with reducing skb->cb[] to 44 bytes, Seems Tom could integrate following patch from my test branch:
It makes sfq use a smaller flow key state.
Quoted 8 lines
Quoted 5 lines
Alternatively, I think we might be able to eliminate the use of
flow_keysandflow_dissectfrom the qdisc code altogether. It looks like this is only being used to determine a hash over the addresses, ports, and protocol so I am thinking that we can just callskb_get_hashfor that. Will try to post some patches soon.The problem with this is that you'll lose the secret input to jhash in
sfq_hash().
fq_codel relies on a secret input to the hash also, but it is only created at instantation time. Retaining that secret input is critical
- otherwise an attacker can fairly easily derive the hash and find ways of flooding the connection at low rates that are almost as effective as simple attacks against pfifo_fast.
A note on sfq: it is commonly deployed with perturb 10 - which acts as a "poor man's AQM" scrambling big flows and causing tcp cwnd reductions - or at least it used to before linux gained much better resilience in re-ordering. Either behavior - blowing up tcp flows (then) - or allowing them to overbuffer (now) is pretty undesirable.
I have gone in detail on everything that is wrong with common SFQ deployments here, commenting extensively on what was once, one of the most popular shapers in the world:
http://www.bufferbloat.net/projects/cerowrt/wiki/Wondershaper_Must_Die
Quoted 10 lines
assuming you have packets p1 and p2 (from different flows) with
skb_get_hash(p1)==skb_get_hash(p2)those flows share same queue/bin forever as the hash pertubation will no longer work.For sfq, hash collisions may exist as well but they'll be resolved after some time when
q->perturbation(its part of hash input) is reseeded. --
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 4 lines
Dave Täht Let's make wifi fast, less jittery and reliable again! https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
Re: [PATCH net-next 3/6] flow_dissector: Add hash_extra field to flow_keys struct
In reply to Tom HerbertQuoted 5 lines · Tom Herbert
Alternatively, I think we might be able to eliminate the use of
flow_keysandflow_dissectfrom the qdisc code altogether. It looks like this is only being used to determine a hash over the addresses, ports, and protocol so I am thinking that we can just callskb_get_hashfor that. Will try to post some patches soon.
Note that SFQ only stored the keys in case of a potential rehash, and because skb->cb[] was available then.
As the rehash implies to _not_ use skb_get_hash() it is simply better to recompute the flow key from packet, in the unlikely case we do have a rehash.
Rehashing SFQ adds reorders, so people should think twice before using it.
PATCH 4/6 flow_dissector: Include VLAN ID in hash computation
In reply to Tom HerbertIf VLAN is present include that in hash_extra in flow_keys when dissecting. This will then be included in hash computation.
--- net/core/flow_dissector.c | 1 + 1 file changed, 1 insertion(+)
net/core/flow_dissector.c +1 -0
@@ -155,6 +155,7 @@ ipv6:if (!vlan)return false; + flow->hash_extra ^= vlan->h_vlan_TCI; proto = vlan->h_vlan_encapsulated_proto; nhoff +=sizeof (*vlan); goto again;
Signature · 1 line
2.2.0.rc0.207.ga3a616c
PATCH 5/6 flow_dissector: Include GRE keyid in hash computation
In reply to Tom HerbertIf keyid is present include that in hash_extra in flow_keys when dissecting. This will then be included in hash computation.
--- net/core/flow_dissector.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-)
net/core/flow_dissector.c +14 -1
@@ -219,8 +219,21 @@ ipv6: nhoff +=4 ;if (hdr->flags &GRE_CSUM ) nhoff +=4 ; -if (hdr->flags &GRE_KEY ) +if (hdr->flags &GRE_KEY ) { +const __be32 *keyid; +__be32 _keyid; + + keyid =__skb_header_pointer (skb, nhoff, +sizeof (_keyid), + data, hlen, + &_keyid); +if (!keyid) +return false; + + flow->hash_extra ^= *keyid; + nhoff +=4 ; + }if (hdr->flags &GRE_SEQ ) nhoff +=4 ;if (proto ==htons (ETH_P_TEB )) {
Signature · 1 line
2.2.0.rc0.207.ga3a616c
PATCH 6/6 flow_dissector: Include MPLS entropy label in hash computation
In reply to Tom HerbertThis patch add MPLS cases in flow dissection. If the top labels are entropy labels (entropy label next indicator label followed by an entropy label) the entropy value is extracted and used as a substitute for ports in flow keys.
Entropy labels for MPLS are described in RFC 6790.
--- include/uapi/linux/in.h | 2 ++ include/uapi/linux/mpls.h | 3 +++ net/core/flow_dissector.c | 24 ++++++++++++++++++++++++ 3 files changed, 29 insertions(+)
include/uapi/linux/in.h +2 -0
@@ -69,6 +69,8 @@ enum {#define IPPROTO_SCTP IPPROTO_SCTP IPPROTO_UDPLITE = 136, /* UDP-Lite (RFC 3828) */#define IPPROTO_UDPLITE IPPROTO_UDPLITE + IPPROTO_MPLS = 137, /* MPLS (RFC 4023) */ +#define IPPROTO_MPLS IPPROTO_MPLS IPPROTO_RAW = 255, /* Raw IP packets */#define IPPROTO_RAW IPPROTO_RAWIPPROTO_MAX
include/uapi/linux/mpls.h +3 -0
@@ -31,4 +31,7 @@ struct mpls_label {#define MPLS_LS_TTL_MASK 0x000000FF#define MPLS_LS_TTL_SHIFT 0 +/* Reserved labels */ +#define MPLS_LS_ENTROPY_IS_NEXT 7 +#endif /* _UAPI_MPLS_H */
net/core/flow_dissector.c +24 -0
@@ -7,6 +7,7 @@#include <net/ipv6.h> #include <linux/igmp.h> #include <linux/icmp.h> +#include <linux/mpls.h> #include <linux/sctp.h> #include <linux/dccp.h> #include <linux/if_tunnel.h>
@@ -193,6 +194,26 @@ ipv6: flow->thoff = (u16 )nhoff;return true; } +case htons (ETH_P_MPLS_UC ): +case htons (ETH_P_MPLS_MC ): { +struct mpls_label *hdr, _hdr[2 ]; +mpls: + hdr =__skb_header_pointer (skb, nhoff,sizeof (_hdr), data, + hlen, &_hdr); +if (!hdr) +return false; +if ((ntohl (hdr[0 ].entry) &MPLS_LS_LABEL_MASK ) == +MPLS_LS_ENTROPY_IS_NEXT ) { + flow->n_proto = proto; + flow->ip_proto = ip_proto; + flow->ports =ntohl (hdr[1 ].entry) &MPLS_LS_LABEL_MASK ; + flow->thoff = (u16 )nhoff; + +return true; + }else { +return false; + } + }case htons (ETH_P_FCOE ): flow->thoff = (u16)(nhoff +FCOE_HEADER_LEN );/* fall through */
@@ -258,6 +279,9 @@ ipv6:case IPPROTO_IPV6 : proto =htons (ETH_P_IPV6 ); goto ipv6; +case IPPROTO_MPLS : + proto =htons (ETH_P_MPLS_UC ); + goto mpls;default :break ; }
Signature · 1 line
2.2.0.rc0.207.ga3a616c