Subject: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

From: Alexander Duyck <[email-masked]>
Date: Fri, 17 Dec 2010 17:00:32 -0800

This patch series is meant to be a proof of concept for simplifying the cost
of Toeplitz hashing by reducing the complexity of the key to a 16 bit
repeating value.  The resultant advantages are that the hash computation
performance is significantly increased, and that the resultant hash is the
same for flows in either direction.

The idea for this occurred to me while working on the ATR hashing algorithms
and improving their performance.  ATR implements a 32 bit repeating key which
results in us being able to XOR everything down to a 32 bit value.  By using a
16 bit key we are able to cut down the 12 to 36 byte input value to only 2
bytes via XOR operations.  This reduces the resultant hash to 16 bits, however
since queue selection only requires 7 bits for RSS that still leaves us with a
large enough resultant key.

I'm currently not planning to do any more work on this in the near future as I
have several other projects in which I am currently engaged.  However I just
wanted to put this code out there in case anyone had a use for it.

Thanks,

Alex

---

Alexander Duyck (3):
      igb: example of how to update igb to make use of in-kernel Toeplitz hashing
      ixgbe: example of how to update ixgbe to make use of in-kernel Toeplitz hash
      net: add simplified 16 bit Toeplitz hash function for transmit side hashing

 drivers/net/igb/igb_main.c     |   22 ++++------
 drivers/net/ixgbe/ixgbe_main.c |   47 ++++++++++++---------
 include/linux/netdevice.h      |    2 +
 include/linux/toeplitz.h       |   89 ++++++++++++++++++++++++++++++++++++++++
 net/core/dev.c                 |   68 +++++++++++++++++++++++++++++++
 5 files changed, 195 insertions(+), 33 deletions(-)
 create mode 100644 include/linux/toeplitz.h

--