* [PATCH net-next 1/7] net: Add skb_get_hash_perturb
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
2015-04-29 7:59 ` Florian Westphal
2015-04-29 4:27 ` [PATCH net-next 2/7] sched: Eliminate use of flow_keys in sch_fq_codel Tom Herbert
` (5 subsequent siblings)
6 siblings, 1 reply; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH net-next 1/7] net: Add skb_get_hash_perturb
2015-04-29 4:27 ` [PATCH net-next 1/7] net: Add skb_get_hash_perturb Tom Herbert
@ 2015-04-29 7:59 ` Florian Westphal
2015-04-29 11:19 ` Eric Dumazet
0 siblings, 1 reply; 12+ messages in thread
From: Florian Westphal @ 2015-04-29 7:59 UTC (permalink / raw)
To: Tom Herbert; +Cc: davem, netdev, jiri
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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH net-next 1/7] net: Add skb_get_hash_perturb
2015-04-29 7:59 ` Florian Westphal
@ 2015-04-29 11:19 ` Eric Dumazet
2015-04-29 19:51 ` Tom Herbert
0 siblings, 1 reply; 12+ messages in thread
From: Eric Dumazet @ 2015-04-29 11:19 UTC (permalink / raw)
To: Florian Westphal; +Cc: Tom Herbert, davem, netdev, jiri
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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH net-next 1/7] net: Add skb_get_hash_perturb
2015-04-29 11:19 ` Eric Dumazet
@ 2015-04-29 19:51 ` Tom Herbert
0 siblings, 0 replies; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 19:51 UTC (permalink / raw)
To: Eric Dumazet
Cc: Florian Westphal, David S. Miller,
Linux Kernel Network Developers, Jiří Pírko
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.
>
>
>
>
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH net-next 2/7] sched: Eliminate use of flow_keys in sch_fq_codel
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 1/7] net: Add skb_get_hash_perturb Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 3/7] sched: Eliminate use of flow_keys in sch_hhf Tom Herbert
` (4 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH net-next 3/7] sched: Eliminate use of flow_keys in sch_hhf
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 1/7] net: Add skb_get_hash_perturb Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 2/7] sched: Eliminate use of flow_keys in sch_fq_codel Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 4/7] sched: Eliminate use of flow_keys in sch_sfb Tom Herbert
` (3 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH net-next 4/7] sched: Eliminate use of flow_keys in sch_sfb
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
` (2 preceding siblings ...)
2015-04-29 4:27 ` [PATCH net-next 3/7] sched: Eliminate use of flow_keys in sch_hhf Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 5/7] sched: Eliminate use of flow_keys in sch_sfq Tom Herbert
` (2 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH net-next 5/7] sched: Eliminate use of flow_keys in sch_sfq
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
` (3 preceding siblings ...)
2015-04-29 4:27 ` [PATCH net-next 4/7] sched: Eliminate use of flow_keys in sch_sfb Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 6/7] net: Add flow_keys digest Tom Herbert
2015-04-29 4:27 ` [PATCH net-next 7/7] sch_choke: Use flow_keys_digest Tom Herbert
6 siblings, 0 replies; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH net-next 6/7] net: Add flow_keys digest
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
` (4 preceding siblings ...)
2015-04-29 4:27 ` [PATCH net-next 5/7] sched: Eliminate use of flow_keys in sch_sfq Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
2015-04-29 5:15 ` Eric Dumazet
2015-04-29 4:27 ` [PATCH net-next 7/7] sch_choke: Use flow_keys_digest Tom Herbert
6 siblings, 1 reply; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH net-next 6/7] net: Add flow_keys digest
2015-04-29 4:27 ` [PATCH net-next 6/7] net: Add flow_keys digest Tom Herbert
@ 2015-04-29 5:15 ` Eric Dumazet
0 siblings, 0 replies; 12+ messages in thread
From: Eric Dumazet @ 2015-04-29 5:15 UTC (permalink / raw)
To: Tom Herbert; +Cc: davem, netdev, jiri
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH net-next 7/7] sch_choke: Use flow_keys_digest
2015-04-29 4:27 [PATCH net-next 0/7] net: Eliminate calls to flow_dissector and introduce flow_keys_digest Tom Herbert
` (5 preceding siblings ...)
2015-04-29 4:27 ` [PATCH net-next 6/7] net: Add flow_keys digest Tom Herbert
@ 2015-04-29 4:27 ` Tom Herbert
6 siblings, 0 replies; 12+ messages in thread
From: Tom Herbert @ 2015-04-29 4:27 UTC (permalink / raw)
To: davem, netdev; +Cc: jiri
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
^ permalink raw reply related [flat|nested] 12+ messages in thread