Skip to contentSkip to conversation

net: Call skb_get_hash in net/sched

RFC PATCH In review Tom Herbert 3 participants 18 messages Mar 1, 2015 – Mar 3, 2015

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

cover net: Call skb_get_hash in net/sched

Replace instance of calling flow_dissect and jhash with call to skb_get_hash. This also eliminates use of flow_keys in skb->cb[].

Tom Herbert (6):
net: Add skb_get_hash_perturb
sched: Eliminate use of flow_keys in sch_choke
sched: Eliminate use of flow_keys in sch_fq_codel
sched: Eliminate use of flow_keys in sch_hhf
sched: Eliminate use of flow_keys in sch_sfb
sched: Eliminate use of flow_keys in sch_sfq

 include/linux/skbuff.h   | 15 +++++++++++++++
 net/sched/sch_choke.c    | 32 ++------------------------------
 net/sched/sch_fq_codel.c | 11 ++---------
 net/sched/sch_hhf.c      | 19 +------------------
 net/sched/sch_sfb.c      | 24 ++++++++----------------
 net/sched/sch_sfq.c      | 29 +++--------------------------
 6 files changed, 31 insertions(+), 99 deletions(-)
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#1 lore raw

PATCH 1/6 net: Add skb_get_hash_perturb

This is used to get the skb->hash and then perturb it for a local use.

---
 include/linux/skbuff.h | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
include/linux/skbuff.h +15 -0
index d898b32..48c1978 100644
@@ -17,6 +17,7 @@
 #include <linux/kernel.h>
 #include <linux/kmemcheck.h>
 #include <linux/compiler.h>
+#include <linux/jhash.h>
 #include <linux/time.h>
 #include <linux/bug.h>
 #include <linux/cache.h>
@@ -922,6 +923,20 @@ static inline __u32 skb_get_hash(struct sk_buff *skb)
 	return skb->hash;
 }
 
+static inline __u32 skb_get_hash_perturb(struct sk_buff *skb,
+					 u32 perturb)
+{
+	u32 hash = skb_get_hash(skb);
+
+	if (likely(hash)) {
+		hash = jhash_1word((__force __u32) hash, perturb);
+		if (unlikely(!hash))
+			hash = 1;
+	}
+
+	return hash;
+}
+
 static inline __u32 skb_get_hash_raw(const struct sk_buff *skb)
 {
 	return skb->hash;
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#2 lore raw

PATCH 2/6 sched: Eliminate use of flow_keys in sch_choke

In reply to Tom Herbert

In choke_match_flow compare skb_get_hash values for the skbuffs instead of explicitly matching keys after calling flow_dissector.

---
 net/sched/sch_choke.c | 32 ++------------------------------
 1 file changed, 2 insertions(+), 30 deletions(-)
net/sched/sch_choke.c +2 -30
index c009eb9..8faa375 100644
@@ -18,7 +18,6 @@
 #include <net/pkt_sched.h>
 #include <net/inet_ecn.h>
 #include <net/red.h>
-#include <net/flow_keys.h>
 
 /*
    CHOKe stateless AQM for fair bandwidth allocation
@@ -133,16 +132,8 @@ static void choke_drop_by_idx(struct Qdisc *sch, unsigned int idx)
 	--sch->q.qlen;
 }
 
-/* private part of skb->cb[] that a qdisc is allowed to use
- * is limited to QDISC_CB_PRIV_LEN bytes.
- * As a flow key might be too large, we store a part of it only.
- */
-#define CHOKE_K_LEN min_t(u32, sizeof(struct flow_keys), QDISC_CB_PRIV_LEN - 3)
-
 struct choke_skb_cb {
 	u16			classid;
-	u8			keys_valid;
-	u8			keys[QDISC_CB_PRIV_LEN - 3];
 };
 
 static inline struct choke_skb_cb *choke_skb_cb(const struct sk_buff *skb)
@@ -169,26 +160,8 @@ static u16 choke_get_classid(const struct sk_buff *skb)
 static bool choke_match_flow(struct sk_buff *skb1,
 			     struct sk_buff *skb2)
 {
-	struct flow_keys temp;
-
-	if (skb1->protocol != skb2->protocol)
-		return false;
-
-	if (!choke_skb_cb(skb1)->keys_valid) {
-		choke_skb_cb(skb1)->keys_valid = 1;
-		skb_flow_dissect(skb1, &temp);
-		memcpy(&choke_skb_cb(skb1)->keys, &temp, CHOKE_K_LEN);
-	}
-
-	if (!choke_skb_cb(skb2)->keys_valid) {
-		choke_skb_cb(skb2)->keys_valid = 1;
-		skb_flow_dissect(skb2, &temp);
-		memcpy(&choke_skb_cb(skb2)->keys, &temp, CHOKE_K_LEN);
-	}
-
-	return !memcmp(&choke_skb_cb(skb1)->keys,
-		       &choke_skb_cb(skb2)->keys,
-		       CHOKE_K_LEN);
+	return (skb1->protocol == skb2->protocol &&
+		skb_get_hash(skb1) == skb_get_hash(skb2));
 }
 
 /*
@@ -279,7 +252,6 @@ static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 			goto other_drop;	/* Packet was eaten by filter */
 	}
 
-	choke_skb_cb(skb)->keys_valid = 0;
 	/* Compute average queue usage (see RED) */
 	q->vars.qavg = red_calc_qavg(p, &q->vars, sch->q.qlen);
 	if (red_is_idling(&q->vars))
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#3 lore raw

PATCH 3/6 sched: Eliminate use of flow_keys in sch_fq_codel

In reply to Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

---
 net/sched/sch_fq_codel.c | 11 ++---------
 1 file changed, 2 insertions(+), 9 deletions(-)
net/sched/sch_fq_codel.c +2 -9
index 1e52dec..a6fc53d 100644
@@ -23,7 +23,6 @@
 #include <linux/vmalloc.h>
 #include <net/netlink.h>
 #include <net/pkt_sched.h>
-#include <net/flow_keys.h>
 #include <net/codel.h>
 
 /*	Fair Queue CoDel.
@@ -68,15 +67,9 @@ struct fq_codel_sched_data {
 };
 
 static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q,
-				  const struct sk_buff *skb)
+				  struct sk_buff *skb)
 {
-	struct flow_keys keys;
-	unsigned int hash;
-
-	skb_flow_dissect(skb, &keys);
-	hash = jhash_3words((__force u32)keys.dst,
-			    (__force u32)keys.src ^ keys.ip_proto,
-			    (__force u32)keys.ports, q->perturbation);
+	u32 hash = skb_get_hash_perturb(skb, q->perturbation);
 
 	return reciprocal_scale(hash, q->flows_cnt);
 }
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#4 lore raw

PATCH 4/6 sched: Eliminate use of flow_keys in sch_hhf

In reply to Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

---
 net/sched/sch_hhf.c | 19 +------------------
 1 file changed, 1 insertion(+), 18 deletions(-)
net/sched/sch_hhf.c +1 -18
index 15d3aab..9d15cb6 100644
@@ -9,7 +9,6 @@
 #include <linux/module.h>
 #include <linux/skbuff.h>
 #include <linux/vmalloc.h>
-#include <net/flow_keys.h>
 #include <net/pkt_sched.h>
 #include <net/sock.h>
 
@@ -176,22 +175,6 @@ static u32 hhf_time_stamp(void)
 	return jiffies;
 }
 
-static unsigned int skb_hash(const struct hhf_sched_data *q,
-			     const struct sk_buff *skb)
-{
-	struct flow_keys keys;
-	unsigned int hash;
-
-	if (skb->sk && skb->sk->sk_hash)
-		return skb->sk->sk_hash;
-
-	skb_flow_dissect(skb, &keys);
-	hash = jhash_3words((__force u32)keys.dst,
-			    (__force u32)keys.src ^ keys.ip_proto,
-			    (__force u32)keys.ports, q->perturbation);
-	return hash;
-}
-
 /* Looks up a heavy-hitter flow in a chaining list of table T. */
 static struct hh_flow_state *seek_list(const u32 hash,
 				       struct list_head *head,
@@ -280,7 +263,7 @@ static enum wdrr_bucket_idx hhf_classify(struct sk_buff *skb, struct Qdisc *sch)
 	}
 
 	/* Get hashed flow-id of the skb. */
-	hash = skb_hash(q, skb);
+	hash = skb_get_hash_perturb(skb, q->perturbation);
 
 	/* Check if this packet belongs to an already established HH flow. */
 	flow_pos = hash & HHF_BIT_MASK;
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#5 lore raw

PATCH 5/6 sched: Eliminate use of flow_keys in sch_sfb

In reply to Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

---
 net/sched/sch_sfb.c | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)
net/sched/sch_sfb.c +8 -16
index 5819dd8..402d051 100644
@@ -26,7 +26,6 @@
 #include <net/ip.h>
 #include <net/pkt_sched.h>
 #include <net/inet_ecn.h>
-#include <net/flow_keys.h>
 
 /*
  * SFB uses two B[l][n] : L x N arrays of bins (L levels, N bins per level)
@@ -285,9 +284,9 @@ static int sfb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 	int i;
 	u32 p_min = ~0;
 	u32 minqlen = ~0;
-	u32 r, slot, salt, sfbhash;
+	u32 r, sfbhash;
+	u32 slot = q->slot;
 	int ret = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
-	struct flow_keys keys;
 
 	if (unlikely(sch->q.qlen >= q->limit)) {
 		qdisc_qstats_overlimit(sch);
@@ -309,22 +308,17 @@ static int sfb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 
 	fl = rcu_dereference_bh(q->filter_list);
 	if (fl) {
+		u32 salt;
+
 		/* If using external classifiers, get result and record it. */
 		if (!sfb_classify(skb, fl, &ret, &salt))
 			goto other_drop;
-		keys.src = salt;
-		keys.dst = 0;
-		keys.ports = 0;
+		sfbhash = jhash_1word(salt, q->bins[q->slot].perturbation);
 	} else {
-		skb_flow_dissect(skb, &keys);
+		sfbhash = skb_get_hash_perturb(skb, q->bins[slot].perturbation);
 	}
 
-	slot = q->slot;
 
-	sfbhash = jhash_3words((__force u32)keys.dst,
-			       (__force u32)keys.src,
-			       (__force u32)keys.ports,
-			       q->bins[slot].perturbation);
 	if (!sfbhash)
 		sfbhash = 1;
 	sfb_skb_cb(skb)->hashes[slot] = sfbhash;
@@ -356,10 +350,8 @@ static int sfb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 	if (unlikely(p_min >= SFB_MAX_PROB)) {
 		/* Inelastic flow */
 		if (q->double_buffering) {
-			sfbhash = jhash_3words((__force u32)keys.dst,
-					       (__force u32)keys.src,
-					       (__force u32)keys.ports,
-					       q->bins[slot].perturbation);
+			sfbhash = skb_get_hash_perturb(skb,
+			    q->bins[slot].perturbation);
 			if (!sfbhash)
 				sfbhash = 1;
 			sfb_skb_cb(skb)->hashes[slot] = sfbhash;
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#6 lore raw

PATCH 6/6 sched: Eliminate use of flow_keys in sch_sfq

In reply to Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

---
 net/sched/sch_sfq.c | 29 +++--------------------------
 1 file changed, 3 insertions(+), 26 deletions(-)
net/sched/sch_sfq.c +3 -26
index b877140..e7ed8a5 100644
@@ -23,7 +23,6 @@
 #include <linux/vmalloc.h>
 #include <net/netlink.h>
 #include <net/pkt_sched.h>
-#include <net/flow_keys.h>
 #include <net/red.h>
 
 
@@ -156,30 +155,10 @@ static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index
 	return &q->dep[val - SFQ_MAX_FLOWS];
 }
 
-/*
- * In order to be able to quickly rehash our queue when timer changes
- * q->perturbation, we store flow_keys in skb->cb[]
- */
-struct sfq_skb_cb {
-       struct flow_keys        keys;
-};
-
-static inline struct sfq_skb_cb *sfq_skb_cb(const struct sk_buff *skb)
-{
-	qdisc_cb_private_validate(skb, sizeof(struct sfq_skb_cb));
-	return (struct sfq_skb_cb *)qdisc_skb_cb(skb)->data;
-}
-
 static unsigned int sfq_hash(const struct sfq_sched_data *q,
-			     const struct sk_buff *skb)
+			     struct sk_buff *skb)
 {
-	const struct flow_keys *keys = &sfq_skb_cb(skb)->keys;
-	unsigned int hash;
-
-	hash = jhash_3words((__force u32)keys->dst,
-			    (__force u32)keys->src ^ keys->ip_proto,
-			    (__force u32)keys->ports, q->perturbation);
-	return hash & (q->divisor - 1);
+	return skb_get_hash_perturb(skb, q->perturbation) & (q->divisor - 1);
 }
 
 static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
@@ -196,10 +175,8 @@ static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
 		return TC_H_MIN(skb->priority);
 
 	fl = rcu_dereference_bh(q->filter_list);
-	if (!fl) {
-		skb_flow_dissect(skb, &sfq_skb_cb(skb)->keys);
+	if (!fl)
 		return sfq_hash(q, skb) + 1;
-	}
 
 	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
 	result = tc_classify(skb, fl, &res);
Signature · 1 line
2.2.0.rc0.207.ga3a616c
#7 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 2 lines · Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

This defeats one of the perturbation goal :

If two flows hashes into same hash, then skb_get_hash_perturb(skb, q->perturbation) will also give same hash forever and map to same hash bucket.

Ideally, we could add a 'u32 perturbation' salt to __skb_get_hash()/__flow_hash_from_keys()/__flow_hash_3words instead of using a net_get_random_once(&hashrnd, sizeof(hashrnd));

but I guess all these functions are becoming very fat.

maintainer
#8 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

From: Eric Dumazet <[email protected]>
Date: Sun, 01 Mar 2015 16:58:52 -0800

Quoted 9 lines · Tom Herbert
Quoted 2 lines

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

This defeats one of the perturbation goal :

If two flows hashes into same hash, then skb_get_hash_perturb(skb, q->perturbation) will also give same hash forever and map to same hash bucket.

Yes, this needs to be resolved.

#9 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

In reply to Eric Dumazet
Quoted 10 lines · Eric Dumazet
Quoted 2 lines · Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

This defeats one of the perturbation goal :

If two flows hashes into same hash, then skb_get_hash_perturb(skb, q->perturbation) will also give same hash forever and map to same hash bucket.

As I already mentioned, the probability of skb_get_hash returning the same value for two flows is 1/2^32. I suspect it's greater probability to get a hash collision between two IPv6 flows with subtlety different addresses or simply match 4-tuples in different address spaces (like VLAN or with VNID). If hash collision is really a problem, we can periodically rekey skb->hash (either SW or HW) or maybe move to 64 bit hashes somehow. Anyway, we potentially have the same problem in RSS and other uses of the hash, if hashes collide then two flows share the same bucket forever unless there is an action to break that.

Quoted 6 lines

Ideally, we could add a 'u32 perturbation' salt to __skb_get_hash()/__flow_hash_from_keys()/__flow_hash_3words instead of using a net_get_random_once(&hashrnd, sizeof(hashrnd));

but I guess all these functions are becoming very fat.

Same thing as rekeying.

Quoted 2 lines
#10 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 12 lines · Tom Herbert
Quoted 10 lines · Eric Dumazet
Quoted 2 lines · Tom Herbert

Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then jhash by hand.

This defeats one of the perturbation goal :

If two flows hashes into same hash, then skb_get_hash_perturb(skb, q->perturbation) will also give same hash forever and map to same hash bucket.

Quoted 10 lines

As I already mentioned, the probability of skb_get_hash returning the same value for two flows is 1/2^32. I suspect it's greater probability to get a hash collision between two IPv6 flows with subtlety different addresses or simply match 4-tuples in different address spaces (like VLAN or with VNID). If hash collision is really a problem, we can periodically rekey skb->hash (either SW or HW) or maybe move to 64 bit hashes somehow. Anyway, we potentially have the same problem in RSS and other uses of the hash, if hashes collide then two flows share the same bucket forever unless there is an action to break that.

One other possibility is that with the txhash changes we can rehash individual connections that are sourced from the host. I was planning to do this on too many TCP retransmits to try to get a different ECMP path (type of source routing), but we could also do this periodically or based on request from qdisc. ooo_okay could be taken into account to avoid OOO packets.

Quoted 11 lines
Quoted 7 lines

Ideally, we could add a 'u32 perturbation' salt to __skb_get_hash()/__flow_hash_from_keys()/__flow_hash_3words instead of using a net_get_random_once(&hashrnd, sizeof(hashrnd));

but I guess all these functions are becoming very fat.

Same thing as rekeying.

Quoted 2 lines
#11 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 6 lines · Tom Herbert

One other possibility is that with the txhash changes we can rehash individual connections that are sourced from the host. I was planning to do this on too many TCP retransmits to try to get a different ECMP path (type of source routing), but we could also do this periodically or based on request from qdisc. ooo_okay could be taken into account to avoid OOO packets.

About locally generated traffic, skb->txhash potential uses would be

1) Somewhat spray txhash on the wire (Hmmm...)
Hard to do that with regular IPv4/tcp traffic, or quite hacky. (like VLAN spraying...)

2.1) Slave selection on bonding driver
2.2) TX queue selection on multiqueue NIC.

In this model (way different than XPS), then skb->ooo_okay is of no use :

In both cases, if you change skb->txhash after congestion event, you do not care of reorders anyway. They are going to be generated most probably because of different paths.

#12 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 10 lines · Eric Dumazet
Quoted 6 lines · Tom Herbert

One other possibility is that with the txhash changes we can rehash individual connections that are sourced from the host. I was planning to do this on too many TCP retransmits to try to get a different ECMP path (type of source routing), but we could also do this periodically or based on request from qdisc. ooo_okay could be taken into account to avoid OOO packets.

Quoted 6 lines

About locally generated traffic, skb->txhash potential uses would be

1) Somewhat spray txhash on the wire (Hmmm...)
Hard to do that with regular IPv4/tcp traffic, or quite hacky. (like VLAN spraying...)

Spraying would be quite easy by modulating txhash from TCP and using either UDP encapsulation like GUE or IPv6 flow labels. Only problem is that this would constantly be changing rxhash at the receiver for the connection, although flow labels might 'just work' with IPv6 Toeplitz in NICs.

Quoted 12 lines

2.1) Slave selection on bonding driver
2.2) TX queue selection on multiqueue NIC.

In this model (way different than XPS), then skb->ooo_okay is of no use :

In both cases, if you change skb->txhash after congestion event, you do not care of reorders anyway. They are going to be generated most probably because of different paths.

#13 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 5 lines · Tom Herbert

Spraying would be quite easy by modulating txhash from TCP and using either UDP encapsulation like GUE or IPv6 flow labels. Only problem is that this would constantly be changing rxhash at the receiver for the connection, although flow labels might 'just work' with IPv6 Toeplitz in NICs.

When I said 'regular IPv4/tcp traffic' this did not include any added encapsulation.

Most NIC are not able to properly offload TCP (TSO) with such encapsulations.

#14 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 8 lines · Eric Dumazet
Quoted 5 lines · Tom Herbert

Spraying would be quite easy by modulating txhash from TCP and using either UDP encapsulation like GUE or IPv6 flow labels. Only problem is that this would constantly be changing rxhash at the receiver for the connection, although flow labels might 'just work' with IPv6 Toeplitz in NICs.

Quoted 6 lines

When I said 'regular IPv4/tcp traffic' this did not include any added encapsulation.

Most NIC are not able to properly offload TCP (TSO) with such encapsulations.

IPv6 flow labels should work through TSO, they would just be replicated for each segment. You would need switches that can hash based on flow label though, and of course IPv6 deployed in the network :-).

Quoted 2 lines
#15 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 12 lines · Tom Herbert
Quoted 11 lines · Eric Dumazet
Quoted 5 lines · Tom Herbert

Spraying would be quite easy by modulating txhash from TCP and using either UDP encapsulation like GUE or IPv6 flow labels. Only problem is that this would constantly be changing rxhash at the receiver for the connection, although flow labels might 'just work' with IPv6 Toeplitz in NICs.

When I said 'regular IPv4/tcp traffic' this did not include any added encapsulation.

Quoted 7 lines
Quoted 3 lines

Most NIC are not able to properly offload TCP (TSO) with such encapsulations.

IPv6 flow labels should work through TSO, they would just be replicated for each segment. You would need switches that can hash based on flow label though, and of course IPv6 deployed in the network :-).

Yeah, but I explicitly talked about native IPv4 + TCP ;)

not IPv6 + TCP, or IPv6 + IPV4 + TCP or some encapsulation...

Trend is to generalize random packet spraying, even within a flow.

https://www.cs.purdue.edu/homes/kompella/publications/infocom13.pdf

This forces us to build a resilient TCP stack.

#16 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

In reply to Tom Herbert
Quoted 9 lines · Tom Herbert

As I already mentioned, the probability of skb_get_hash returning the same value for two flows is 1/2^32. I suspect it's greater probability to get a hash collision between two IPv6 flows with subtlety different addresses or simply match 4-tuples in different address spaces (like VLAN or with VNID). If hash collision is really a problem, we can periodically rekey skb->hash (either SW or HW) or maybe move to 64 bit hashes somehow. Anyway, we potentially have the same problem in RSS and other uses of the hash, if hashes collide then two flows share the same bucket forever unless there is an action to break that.

Main historical use of SFQ is for routers.

We do not control skb->hash for forwarding workload, unless you reprogram RSS keys on the NIC.

If you remember, we used to have a problem on some NIC using a well known RSS key. It is fortunate SFQ/fq_codel did not rely on skb->hash too much.

If to target one flow, attackers need to attack your big boxes to flood one particular RX queue at NIC level, this has a huge cost for them.

While targeting one hash bucket on a qdisc might be much easier, if they know even a hash perturbation has no effect against their attack.

#17 lore raw

Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

Quoted 12 lines · Eric Dumazet
Quoted 9 lines · Tom Herbert

As I already mentioned, the probability of skb_get_hash returning the same value for two flows is 1/2^32. I suspect it's greater probability to get a hash collision between two IPv6 flows with subtlety different addresses or simply match 4-tuples in different address spaces (like VLAN or with VNID). If hash collision is really a problem, we can periodically rekey skb->hash (either SW or HW) or maybe move to 64 bit hashes somehow. Anyway, we potentially have the same problem in RSS and other uses of the hash, if hashes collide then two flows share the same bucket forever unless there is an action to break that.

Quoted 9 lines

Main historical use of SFQ is for routers.

We do not control skb->hash for forwarding workload, unless you reprogram RSS keys on the NIC.

If you remember, we used to have a problem on some NIC using a well known RSS key. It is fortunate SFQ/fq_codel did not rely on skb->hash too much.

Okay, I'll audit the drivers returning skb->hash fro HW to make sure they are properly randomizing the initial hash key.

Unless, there's other material objections, I'll formally post these patches. Consolidating the packet hash for different use cases should be more efficient and we'll be able focus efforts on strengthening it over time in one place. As for SW vs. HW hash, it still seems like getting a Toeplitz hash from the hardware is going to be stronger at least for TCP/IPv6 than what we can currently do with jhash as the input is the full 40 bytes of 4-tuple. I must admit I wish Microsoft would have continued to make advancements with Toeplitz hash, it would be nice if there was a real definition for use with UDP and maybe we had instructions for this in x86!

Tom

Quoted 8 lines

If to target one flow, attackers need to attack your big boxes to flood one particular RX queue at NIC level, this has a huge cost for them.

While targeting one hash bucket on a qdisc might be much easier, if they know even a hash perturbation has no effect against their attack.