From: Tom Herbert <hidden> Date: 2015-02-28 03:12:38
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(-)
--
2.2.0.rc0.207.ga3a616c
From: Tom Herbert <hidden> Date: 2015-02-28 03:12:44
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.
Signed-off-by: Tom Herbert <redacted>
---
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(-)
From: Tom Herbert <hidden> Date: 2015-02-28 03:12:49
Fold ip_proto into dst when computing hash. This provides a more
standard 5-tuple hash.
Signed-off-by: Tom Herbert <redacted>
---
net/core/flow_dissector.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
@@ -276,6 +276,7 @@ static __always_inline u32 __flow_hash_3words(u32 a, u32 b, u32 c)staticinlineu32__flow_hash_from_keys(structflow_keys*keys){u32hash;+u32extra;/* get a consistent hash (same value on both flow directions) */if(((__forceu32)keys->dst<(__forceu32)keys->src)||
From: Tom Herbert <hidden> Date: 2015-02-28 03:12:54
This will be used for additional input into the hash computation
such as VLAN ID or GRE keyid.
Signed-off-by: Tom Herbert <redacted>
---
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(-)
From: Tom Herbert <hidden> Date: 2015-02-28 03:12:57
If VLAN is present include that in hash_extra in flow_keys when
dissecting. This will then be included in hash computation.
Signed-off-by: Tom Herbert <redacted>
---
net/core/flow_dissector.c | 1 +
1 file changed, 1 insertion(+)
From: Tom Herbert <hidden> Date: 2015-02-28 03:13:00
If keyid is present include that in hash_extra in flow_keys when
dissecting. This will then be included in hash computation.
Signed-off-by: Tom Herbert <redacted>
---
net/core/flow_dissector.c | 15 ++++++++++++++-
1 file changed, 14 insertions(+), 1 deletion(-)
From: Tom Herbert <hidden> Date: 2015-02-28 03:13:04
This 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.
Signed-off-by: Tom Herbert <redacted>
---
include/uapi/linux/in.h | 2 ++
include/uapi/linux/mpls.h | 3 +++
net/core/flow_dissector.c | 24 ++++++++++++++++++++++++
3 files changed, 29 insertions(+)
@@ -193,6 +194,26 @@ ipv6:flow->thoff=(u16)nhoff;returntrue;}+casehtons(ETH_P_MPLS_UC):+casehtons(ETH_P_MPLS_MC):{+structmpls_label*hdr,_hdr[2];+mpls:+hdr=__skb_header_pointer(skb,nhoff,sizeof(_hdr),data,+hlen,&_hdr);+if(!hdr)+returnfalse;+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;++returntrue;+}else{+returnfalse;+}+}casehtons(ETH_P_FCOE):flow->thoff=(u16)(nhoff+FCOE_HEADER_LEN);/* fall through */
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")
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")
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
--
Dave Täht
Let's make wifi fast, less jittery and reliable again!
https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
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")
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.
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")
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
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
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.
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.
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.
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.
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.
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?
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.
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.
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
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 majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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")
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
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
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.
From: Eric Dumazet <hidden> Date: 2015-03-01 21:27:48
On Sun, 2015-03-01 at 09:55 -0800, Tom Herbert wrote:
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.
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.