This patch modified the control ring protocol (of which there is
not yet an implementation) to make it more general. Most of the
concepts are not limited to toeplitz hashing so it's best not to
make them unnecessarily specific.
Apart from changing the names of various definitions and modifying
comments, this patch:
- Adds a new control message type to select a hash algorithm.
- Adds a reference implementation of the toeplitz hash.
- Changes the 'toeplitz' extra info fragment into a 'hash' extra
info fragment and replaces the octet of padding with the index of
the algorithm that was used to create the hash value.
The patch also fixes a few spelling typos noticed along the way.
Signed-off-by: Paul Durrant
Cc: Ian Campbell
Cc: Ian Jackson
Cc: Jan Beulich
Cc: Keir Fraser
Cc: Tim Deegan
---
v2:
- Remove 'inline' from reference hash definition and make the
definition optional
v3:
- Use XEN_NETIF_ prefix instead of NETIF_
- Make hash mapping table optional
- Allow a hash mapping table that is not power-of-two sized
---
xen/include/public/io/netif.h | 275 --
1 file changed, 183 insertions(+), 92 deletions(-)
diff --git a/xen/include/public/io/netif.h b/xen/include/public/io/netif.h
index 8816e0f..6eacd76 100644
--- a/xen/include/public/io/netif.h
+++ b/xen/include/public/io/netif.h
@@ -164,7 +164,7 @@
* Control ring
*
*
- * Some features, such as toeplitz hashing (detailed below), require a
+ * Some features, such as hashing (detailed below), require a
* significant amount of out-of-band data to be passed from frontend to
* backend. Use of xenstore is not suitable for large quantities of data
* because of quota limitations and so a dedicated 'control ring' is used.
@@ -191,8 +191,8 @@
*/
/*
- * Toeplitz hash types
- * ===
+ * Hash types
+ * ==
*
* For the purposes of the definitions below, 'Packet[]' is an array of
* octets containing an IP packet without options, 'Array[X..Y]' means a
@@ -206,10 +206,10 @@
* Buffer[0..8] = Packet[12..15] (source address) +
*Packet[16..19] (destination address)
*
- * Result = ToeplitzHash(Buffer, 8)
+ * Result = Hash(Buffer, 8)
*/
-#define _NETIF_CTRL_TOEPLITZ_HASH_IPV4 0
-#define NETIF_CTRL_TOEPLITZ_HASH_IPV4 (1 <<
_NETIF_CTRL_TOEPLITZ_HASH_IPV4)
+#define _NETIF_CTRL_HASH_TYPE_IPV4 0
+#define NETIF_CTRL_HASH_TYPE_IPV4 (1 << _NETIF_CTRL_HASH_TYPE_IPV4)
/*
* A hash calculated over an IP version 4 header and TCP header as
@@ -220,10 +220,10 @@
* Packet[20..21] (source port) +
* Packet[22..23] (destination port)
*
- * Result = ToeplitzHash(Buffer, 12)
+ * Result = Hash(Buffer, 12)
*/
-#define _NETIF_CTRL_TOEPLITZ_HASH_IPV4_TCP 1
-#define NETIF_CTRL_TOEPLITZ_HASH_IPV4_TCP (1 <<
_NETIF_CTRL_TOEPLITZ_HASH_IPV4_TCP)
+#define _NETIF_CTRL_HASH_TYPE_IPV4_TCP 1
+#define NETIF_CTRL_HASH_TYPE_IPV4_TCP (1 << _NETIF_CTRL_HASH_TYPE_IPV4_TCP)
/*
* A hash calculated over an IP version 6 header as follows:
@@ -231,10 +231,10 @@
* Buffer[0..32] = Packet[8..23] (source address ) +
* Packet[24..39] (destination address)
*
- * Result = ToeplitzHash(Buffer, 32)
+ * Result = Hash(Buffer, 32)
*/
-#define _NETIF_CTRL_TOEPLITZ_HASH_IPV6 2
-#define NETIF_CTRL_TOEPLITZ_HASH_IPV6 (1 <<
_NETIF_CTRL_TOEPLITZ_HASH_IPV4)
+#define _NETIF_CTRL_HASH_TYPE_IPV6 2
+#define NETIF_CTRL_HASH_TYPE_IPV6 (1 << _NETIF_CTRL_HASH_TYPE_IPV6)
/*
* A hash calculated over an IP version 6 header and TCP header as
@@ -245,10 +245,79 @@
* Packet[40..41] (source port) +
* Packet[42..43] (destination port)
*
- * Result = ToeplitzHash(Buffer, 36)
+ * Result = Hash(Buffer, 36)
+ */
+#define _NETIF_CTRL_HASH_TYPE_IPV6_TCP 3
+#define NETIF_CTRL_HASH_TYPE_IPV6_TCP (1 << _NETIF_CTRL_HASH_TYPE_IPV6_TCP)
+
+/*
+ * Hash algorithms
+ * ===
+ */
+
+#define NETIF_CTRL_HASH_ALGORITHM_NONE 0
+
+/*
+ * Toeplitz hash:
*/
-#define _NETIF_CTRL_TOEPLITZ_HASH_IPV6_TCP 3
-#define NETIF_CTRL_TOEPLITZ_HASH_IPV6_TCP (1 <<
_NETIF_CTRL_TOEPLITZ_HASH_IPV4_TCP)
+
+#define NETIF_CTRL_HASH_ALGORITHM_TOEPLITZ 1
+
+/*
+ * This algorithm uses a 'key' as well as the data buffer itself.
+ * (Buffer[] and Key[] are treated as shift-registers where the MSB of
+ * Buffer/Key[0] is considered 'left-most' and the LSB of Buffer/Key[N-1]
+ * is the 'right-most').
+ *
+ * Value = 0
+ * For number of bits in Buffer[]
+ *If (left-most bit of Buffer[] is 1)
+ *Value ^= left-most 32 bits of Key[]
+ *Key[] << 1
+ *Buffer[] << 1
+ *
+ * The code below is provided for convenience where an operating system
+ * does not already provide an implementation.
+ */
+#ifdef XEN_NETIF_DEFINE_TOEPLITZ
+static uint32_t netif_toeplitz_hash(const uint8_t *key,
+unsigned int keylen,
+const uint8_t *buf,
+
