netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH net-next 0/6] net: Call skb_get_hash in qdiscs
@ 2015-03-04 18:39 Tom Herbert
  2015-03-04 18:39 ` [PATCH net-next 1/6] net: Add skb_get_hash_perturb Tom Herbert
                   ` (7 more replies)
  0 siblings, 8 replies; 15+ messages in thread
From: Tom Herbert @ 2015-03-04 18:39 UTC (permalink / raw)
  To: davem, netdev, eric.dumazet, fw

In several qdiscs, we currently compute packet hashes primarily as part
of queue selection. This is done by calling flow_dissect and then
performing a jhash.

There are several problems with this:

- The functionality of doing a packet hash is replicated in the qdiscs.
- The hashing algorithm is not consistent, for instance in hhf an
  attempt is made to get the hash out of sk_hash, but other qdiscs
  don't do that. Some qdiscs XOR ip_proto into the source before
  jhash, some don't.
- Without a common infrastructure, if we want to use a new (potentially
  stronger) hash function or wanted to add more input to the hash,
  we would need to address this in each qdisc.
- Flow dissector is potentially called multiple times for a single
  packet.
- The flow keys are passed in cb[] structure. This severely limits
  our ability to increase the key space. For instance, the folding
  of IPv6 addresses in flow_dissector to make a 32-bit value
  represents a significant loss of information (it would be easy
  to create millions of different 4-tuples that would always produce the
  same hash value). 

This patch set consolidates the packet hashing in the qdiscs to use the
common skb_get_hash function. Specifically:

- Add skb_get_hash_perturb. This allows a caller to perturb the
  skb->hash value for a local use. This support the pertubation
  feature in qdiscs.
- Call skb_get_hash or skb_get_hash_perturb from the qdiscs

There are at least two caveats to mention:

- The probability that two different flows randomly match to the same
  hash from skb_get_hash is 1/2^32. If such a collision were to happen,
  then the flows potentially also map to the same qdisc queue in
  perpetuity despite perturbation being performed. Given the very low
  probability of this occurring, this may in practice only be an
  academic issue. If it is a real concern, rekeying of the underlying
  mechanisms of skb->hash could be done.
- skb_get_hash may return a value from the hardware. There are two
  questions around that:
  1) Does this produce predicatable hash values that can be exploited
     by an attacker? The answer for this is that we need to enforce
     that any device returning a hash to host must be initialized
     with a random hash key.
  2) Is the quality of the hash done in HW poorer than what host can
     do? Hardware typically provides a Toeplitz hash which was
     originally specified by MS for RSS. The application of Toeplitz
     hash was only specified for TCP and IPv4/v6, although some NICs
     have extrapolated the algorithm to apply to UDP also. Toeplitz
     is fairly well known at this point, it doesn't seem like there
     is evidence that this is poorer quality than Jenkin's hash, and
     in fact in the case of TCP/IPv6 the hash quality is probably
     better since the fully 40 bytes of 4-tuple are used as input.
     However, if there are concerns about the quality of HW hash,
     we do have the option of turning it off.

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(-)

-- 
2.2.0.rc0.207.ga3a616c

^ permalink raw reply	[flat|nested] 15+ messages in thread
* [PATCH RFC net-next 0/6] net: Call skb_get_hash in net/sched
@ 2015-03-01 22:09 Tom Herbert
  2015-03-01 22:09 ` [PATCH net-next 3/6] sched: Eliminate use of flow_keys in sch_fq_codel Tom Herbert
  0 siblings, 1 reply; 15+ messages in thread
From: Tom Herbert @ 2015-03-01 22:09 UTC (permalink / raw)
  To: davem, netdev, eric.dumazet, fw

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(-)

-- 
2.2.0.rc0.207.ga3a616c

^ permalink raw reply	[flat|nested] 15+ messages in thread
end of thread, other threads:[~2015-03-05 21:06 UTC | newest]

Thread overview: 15+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2015-03-04 18:39 [PATCH net-next 0/6] net: Call skb_get_hash in qdiscs Tom Herbert
2015-03-04 18:39 ` [PATCH net-next 1/6] net: Add skb_get_hash_perturb Tom Herbert
2015-03-04 18:40 ` [PATCH net-next 2/6] sched: Eliminate use of flow_keys in sch_choke Tom Herbert
2015-03-04 18:40 ` [PATCH net-next 3/6] sched: Eliminate use of flow_keys in sch_fq_codel Tom Herbert
2015-03-04 18:40 ` [PATCH net-next 4/6] sched: Eliminate use of flow_keys in sch_hhf Tom Herbert
2015-03-04 18:40 ` [PATCH net-next 5/6] sched: Eliminate use of flow_keys in sch_sfb Tom Herbert
2015-03-04 18:40 ` [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq Tom Herbert
2015-03-04 20:03 ` [PATCH net-next 0/6] net: Call skb_get_hash in qdiscs Eric Dumazet
2015-03-04 21:49   ` Tom Herbert
2015-03-04 22:31     ` Eric Dumazet
2015-03-05 21:06   ` David Miller
2015-03-05 11:13 ` David Laight
2015-03-05 17:19   ` Tom Herbert
2015-03-05 17:59     ` Eric Dumazet
  -- strict thread matches above, loose matches on Subject: below --
2015-03-01 22:09 [PATCH RFC net-next 0/6] net: Call skb_get_hash in net/sched Tom Herbert
2015-03-01 22:09 ` [PATCH net-next 3/6] sched: Eliminate use of flow_keys in sch_fq_codel Tom Herbert

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).