[PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest

[PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest

[Tom Herbert]

In this patch set we add skb_get_hash_perturb which gets the skbuff
hash for a packet and perturbs it using a provided key and jhash1.
This function is used in serveral qdiscs and eliminates many calls
to flow_dissector and jhash3 to get a perturbed hash for a packet.

To handle the sch_choke issue (passes flow_keys in skbuff cb) we
add flow_keys_digest which is a digest of a flow constructed
from a flow_keys structure.

This is the second version of these patches I posted a while ago,
and is prerequisite work to increasing the size of the flow_keys
structure and hashing over it (full IPv6 address, flow label, VLAN ID,
etc.).

Tom Herbert (7):
  net: Add skb_get_hash_perturb
  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
  net: Add flow_keys digest
  sch_choke: Use flow_keys_digest

 include/linux/skbuff.h   | 15 +++++++++++++++
 include/net/flow_keys.h  | 19 +++++++++++++++++++
 net/sched/sch_choke.c    | 14 ++++----------
 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 +++--------------------------
 7 files changed, 52 insertions(+), 79 deletions(-)

-- 
1.8.1

[PATCH net-next 1/7] net: Add skb_get_hash_perturb

[Tom Herbert]

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

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 include/linux/skbuff.h | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
index 66e374d..b706889 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
@@ -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>
@@ -927,6 +928,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;
-- 
1.8.1

[PATCH net-next 2/7] sched: Eliminate use of flow_keys in sch_fq_codel

[Tom Herbert]

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

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 net/sched/sch_fq_codel.c | 11 ++---------
 1 file changed, 2 insertions(+), 9 deletions(-)

diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index 1e52dec..a6fc53d 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -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);
 }
-- 
1.8.1

[PATCH net-next 3/7] sched: Eliminate use of flow_keys in sch_hhf

[Tom Herbert]

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

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 net/sched/sch_hhf.c | 19 +------------------
 1 file changed, 1 insertion(+), 18 deletions(-)

diff --git a/net/sched/sch_hhf.c b/net/sched/sch_hhf.c
index 15d3aab..9d15cb6 100644
--- a/net/sched/sch_hhf.c
+++ b/net/sched/sch_hhf.c
@@ -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;
-- 
1.8.1

[PATCH net-next 4/7] sched: Eliminate use of flow_keys in sch_sfb

[Tom Herbert]

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

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 net/sched/sch_sfb.c | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)

diff --git a/net/sched/sch_sfb.c b/net/sched/sch_sfb.c
index 5819dd8..4b81519 100644
--- a/net/sched/sch_sfb.c
+++ b/net/sched/sch_sfb.c
@@ -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[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;
-- 
1.8.1

[PATCH net-next 5/7] sched: Eliminate use of flow_keys in sch_sfq

[Tom Herbert]

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

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 net/sched/sch_sfq.c | 29 +++--------------------------
 1 file changed, 3 insertions(+), 26 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index b877140..e7ed8a5 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -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);
-- 
1.8.1

[PATCH net-next 6/7] net: Add flow_keys digest

[Tom Herbert]

Some users of flow keys (well just sch_choke now) need to pass
flow_keys in skbuff cb, and use them for exact comparisons of flows
so that skb->hash is not sufficient. In order to increase size of
the flow_keys structure, we introduce another structure for
the purpose of passing flow keys in skbuff cb. We limit this structure
to sixteen bytes, and we will technically treat this as a digest of
flow_keys struct hence its name flow_keys_digest. In the first
incaranation we just copy the flow_keys structure up to 16 bytes--
this is the same information previously passed in the cb. In the
future, we'll adapt this for larger flow_keys and could use something
like SHA-1 over the whole flow_keys to improve the quality of the
digest.

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 include/net/flow_keys.h | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/include/net/flow_keys.h b/include/net/flow_keys.h
index dc8fd81..f2610ad 100644
--- a/include/net/flow_keys.h
+++ b/include/net/flow_keys.h
@@ -42,4 +42,23 @@ static inline __be32 skb_flow_get_ports(const struct sk_buff *skb, int thoff, u8
 u32 flow_hash_from_keys(struct flow_keys *keys);
 unsigned int flow_get_hlen(const unsigned char *data, unsigned int max_len,
 			   __be16 protocol);
+
+/* struct flow_keys_digest:
+ *
+ * This structure used to hold a digest of the full flow keys. This is a larger
+ * "hash" of a connection to allow definitively matching specific flows where
+ * the 32 bit skb_hash is not large enough. The size is limited to 16 bytes
+ * so that it can by used in CB of skb (see sch_choke for an example).
+ */
+#define FLOW_KEYS_DIGEST_LEN	16
+struct flow_keys_digest {
+	u8	data[FLOW_KEYS_DIGEST_LEN];
+};
+
+static inline void make_flow_keys_digest(struct flow_keys_digest *digest,
+					 struct flow_keys *flow)
+{
+	memcpy(&digest->data, flow, FLOW_KEYS_DIGEST_LEN);
+}
+
 #endif
-- 
1.8.1

[PATCH net-next 7/7] sch_choke: Use flow_keys_digest

[Tom Herbert]

Call make_flow_keys_digest to get a digest from flow keys and
use that to pass skbuff cb and for comparing flows.

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 net/sched/sch_choke.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/net/sched/sch_choke.c b/net/sched/sch_choke.c
index c009eb9..dfe3da7 100644
--- a/net/sched/sch_choke.c
+++ b/net/sched/sch_choke.c
@@ -133,16 +133,10 @@ 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];
+	struct			flow_keys_digest keys;
 };
 
 static inline struct choke_skb_cb *choke_skb_cb(const struct sk_buff *skb)
@@ -177,18 +171,18 @@ static bool choke_match_flow(struct sk_buff *skb1,
 	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);
+		make_flow_keys_digest(&choke_skb_cb(skb1)->keys, &temp);
 	}
 
 	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);
+		make_flow_keys_digest(&choke_skb_cb(skb2)->keys, &temp);
 	}
 
 	return !memcmp(&choke_skb_cb(skb1)->keys,
 		       &choke_skb_cb(skb2)->keys,
-		       CHOKE_K_LEN);
+		       sizeof(choke_skb_cb(skb1)->keys));
 }
 
 /*
-- 
1.8.1

Re: [PATCH net-next 6/7] net: Add flow_keys digest

[Eric Dumazet]

On Tue, 2015-04-28 at 21:27 -0700, Tom Herbert wrote:
> Some users of flow keys (well just sch_choke now) need to pass
> flow_keys in skbuff cb, and use them for exact comparisons of flows
> so that skb->hash is not sufficient. In order to increase size of
> the flow_keys structure, we introduce another structure for
> the purpose of passing flow keys in skbuff cb. We limit this structure
> to sixteen bytes, and we will technically treat this as a digest of
> flow_keys struct hence its name flow_keys_digest. In the first
> incaranation we just copy the flow_keys structure up to 16 bytes--
> this is the same information previously passed in the cb. In the
> future, we'll adapt this for larger flow_keys and could use something
> like SHA-1 over the whole flow_keys to improve the quality of the
> digest.
> 
> Signed-off-by: Tom Herbert <tom@herbertland.com>
> ---
>  include/net/flow_keys.h | 19 +++++++++++++++++++
>  1 file changed, 19 insertions(+)
> 
> diff --git a/include/net/flow_keys.h b/include/net/flow_keys.h
> index dc8fd81..f2610ad 100644
> --- a/include/net/flow_keys.h
> +++ b/include/net/flow_keys.h
> @@ -42,4 +42,23 @@ static inline __be32 skb_flow_get_ports(const struct sk_buff *skb, int thoff, u8
>  u32 flow_hash_from_keys(struct flow_keys *keys);
>  unsigned int flow_get_hlen(const unsigned char *data, unsigned int max_len,
>  			   __be16 protocol);
> +
> +/* struct flow_keys_digest:
> + *
> + * This structure used to hold a digest of the full flow keys. This is a larger
> + * "hash" of a connection to allow definitively matching specific flows where
> + * the 32 bit skb_hash is not large enough. The size is limited to 16 bytes
> + * so that it can by used in CB of skb (see sch_choke for an example).
> + */
> +#define FLOW_KEYS_DIGEST_LEN	16
> +struct flow_keys_digest {
> +	u8	data[FLOW_KEYS_DIGEST_LEN];
> +};
> +
> +static inline void make_flow_keys_digest(struct flow_keys_digest *digest,
> +					 struct flow_keys *flow)

const struct flow_keys *flow

> +{

Maybe document that src,dst,ports must be in first 16 bytes of
flows_keys

Some BUILD_BUG_ON() might do the trick

> +	memcpy(&digest->data, flow, FLOW_KEYS_DIGEST_LEN);
> +}
> +
>  #endif

Re: [PATCH net-next 1/7] net: Add skb_get_hash_perturb

[Florian Westphal]

Tom Herbert <tom@herbertland.com> wrote:
> This is used to get the skb->hash and then perturb it for a local use.
> 
> Signed-off-by: Tom Herbert <tom@herbertland.com>
> ---
>  include/linux/skbuff.h | 15 +++++++++++++++
>  1 file changed, 15 insertions(+)
> 
> diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
> index 66e374d..b706889 100644
> --- a/include/linux/skbuff.h
> +++ b/include/linux/skbuff.h
> @@ -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>
> @@ -927,6 +928,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);

Whats this perturb for?

perturb is supposed to make sure that if you have

flow1, flow2 where hash(flow1, perturb) == hash(flow2, perturb)
the collision will be temporary and go away once perturb changes.

If you perturb after hashing, such collision is permanent.

So I think this either should flow_dissect + hash in software,
or just use skb_get_hash without perturb.

Re: [PATCH net-next 1/7] net: Add skb_get_hash_perturb

[Eric Dumazet]

On Wed, 2015-04-29 at 09:59 +0200, Florian Westphal wrote:
> Tom Herbert <tom@herbertland.com> wrote:
> > This is used to get the skb->hash and then perturb it for a local use.
> > 
> > Signed-off-by: Tom Herbert <tom@herbertland.com>
> > ---
> >  include/linux/skbuff.h | 15 +++++++++++++++
> >  1 file changed, 15 insertions(+)
> > 
> > diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
> > index 66e374d..b706889 100644
> > --- a/include/linux/skbuff.h
> > +++ b/include/linux/skbuff.h
> > @@ -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>
> > @@ -927,6 +928,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);
> 
> Whats this perturb for?
> 
> perturb is supposed to make sure that if you have
> 
> flow1, flow2 where hash(flow1, perturb) == hash(flow2, perturb)
> the collision will be temporary and go away once perturb changes.
> 
> If you perturb after hashing, such collision is permanent.
> 
> So I think this either should flow_dissect + hash in software,
> or just use skb_get_hash without perturb.

Yes, I mentioned this several times to Tom in the various past attempts.

Also, this stuff means that sfq will call jhash twice instead of once,
unless skb->hash is already populated before sfq enqueue.

If the goal is to extend skb to include a flow_keys_digest instead of
u32 hash, lets state this right now ;)

I think I already suggested to add a 'perturb' parameter to
skb_get_hash() to use in place of hashrnd (found in
net/core/flow_dissector.c)

If hash is Toeplitz based and provided by a NIC, I doubt a jhash()
perturbation will get anything better.

Re: [PATCH net-next 1/7] net: Add skb_get_hash_perturb

[Tom Herbert]

On Wed, Apr 29, 2015 at 4:19 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Wed, 2015-04-29 at 09:59 +0200, Florian Westphal wrote:
>> Tom Herbert <tom@herbertland.com> wrote:
>> > This is used to get the skb->hash and then perturb it for a local use.
>> >
>> > Signed-off-by: Tom Herbert <tom@herbertland.com>
>> > ---
>> >  include/linux/skbuff.h | 15 +++++++++++++++
>> >  1 file changed, 15 insertions(+)
>> >
>> > diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
>> > index 66e374d..b706889 100644
>> > --- a/include/linux/skbuff.h
>> > +++ b/include/linux/skbuff.h
>> > @@ -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>
>> > @@ -927,6 +928,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);
>>
>> Whats this perturb for?
>>
>> perturb is supposed to make sure that if you have
>>
>> flow1, flow2 where hash(flow1, perturb) == hash(flow2, perturb)
>> the collision will be temporary and go away once perturb changes.
>>
>> If you perturb after hashing, such collision is permanent.
>>
>> So I think this either should flow_dissect + hash in software,
>> or just use skb_get_hash without perturb.
>
> Yes, I mentioned this several times to Tom in the various past attempts.
>
> Also, this stuff means that sfq will call jhash twice instead of once,
> unless skb->hash is already populated before sfq enqueue.
>
> If the goal is to extend skb to include a flow_keys_digest instead of
> u32 hash, lets state this right now ;)
>
> I think I already suggested to add a 'perturb' parameter to
> skb_get_hash() to use in place of hashrnd (found in
> net/core/flow_dissector.c)
>
Okay, I'll do this. We can try to optimize out the calls to
flow_dissector some other time.

> If hash is Toeplitz based and provided by a NIC, I doubt a jhash()
> perturbation will get anything better.
>
>
>
>