1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright 2008-2015 Solarflare Communications Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #include <sys/param.h>
28 #include <sys/int_limits.h>
29 #include <sys/byteorder.h>
30 #include <sys/random.h>
31 #include <sys/types.h>
32 #include <sys/kmem.h>
33 #include <netinet/in.h>
34 #include "sfxge.h"
35 #include "efx.h"
36
37 /*
38 * The largest amount of the data which the hash may be calculated over
39 * is a 4-tuple of source/destination IPv6 addresses (2 x 16 bytes)
40 * and source/destination TCP port numbers (2 x 2 bytes), adding up to 40 bytes
41 */
42 #define SFXGE_TOEPLITZ_IN_MAX \
43 (2 * (sizeof (struct in6_addr) + sizeof (in_port_t)))
44 #define SFXGE_TOEPLITZ_CACHE_SIZE (SFXGE_TOEPLITZ_IN_MAX * (UINT8_MAX + 1))
45
46 static uint32_t
47 toeplitz_hash(const uint32_t *cache, const uint8_t *input,
48 unsigned pos, unsigned datalen)
49 {
50 uint32_t hash = 0;
51 for (; datalen != 0; datalen--, pos++, input++) {
52 hash ^= cache[pos * (UINT8_MAX + 1) + *input];
53 }
54
55 return (hash);
56 }
57
58 uint32_t
59 sfxge_toeplitz_hash(sfxge_t *sp, unsigned int addr_size,
60 uint8_t *src_addr, uint16_t src_port, uint8_t *dst_addr, uint16_t dst_port)
61 {
62 uint32_t hash = 0;
63 unsigned pos = 0;
64
65 hash ^= toeplitz_hash(sp->s_toeplitz_cache, src_addr, pos, addr_size);
66 pos += addr_size;
67 hash ^= toeplitz_hash(sp->s_toeplitz_cache, dst_addr, pos, addr_size);
68 pos += addr_size;
69 if (src_port != 0 || dst_port != 0) {
70 hash ^= toeplitz_hash(sp->s_toeplitz_cache,
71 (const uint8_t *)&src_port, pos, sizeof (src_port));
72 pos += sizeof (src_port);
73 hash ^= toeplitz_hash(sp->s_toeplitz_cache,
74 (const uint8_t *)&dst_port, pos, sizeof (dst_port));
75 }
76 return (hash);
77 }
78
79 /*
80 * The algorithm to calculate RSS Toeplitz hash is essentially as follows:
81 * - Regard a Toeplitz key and an input as bit strings, with the
82 * most significant bit of the first byte being the first bit
83 * - Let's have a 32-bit window sliding over the Toeplitz key bit by bit
84 * - Let the initial value of the hash be zero
85 * - Then for every bit in the input that is set to 1, XOR the value of the
86 * window at a given bit position into the resulting hash
87 *
88 * First we note that since XOR is commutative and associative, the
89 * resulting hash is just a XOR of subhashes for every input bit:
90 * H = H_0 XOR H_1 XOR ... XOR H_n (1)
91 * Then we note that every H_i is only dependent on the value of i and
92 * the value of i'th bit of input, but not on any preceding or following
93 * input bits.
94 * Then we note that (1) holds also for any bit sequences,
95 * e.g. for bytes of input:
96 * H = H_0_7 XOR H_8_15 XOR ... XOR H_(n-7)_n (2)
97 * and every
98 * H_i_j = H_i XOR H_(i+1) ... XOR H_j. (3)
99 *
100 * It naturally follows than H_i_(i+7) only depends on the value of the byte
101 * and the position of the byte in the input.
102 * Therefore we may pre-calculate the value of each byte sub-hash H_i_(i+7)
103 * for each possible byte value and each possible byte input position, and
104 * then just assemble the hash of the packet byte-by-byte instead of
105 * bit-by-bit.
106 *
107 * The amount of memory required for such a cache is not prohibitive:
108 * - we have at most 36 bytes of input, each holding 256 possible values
109 * - and the hash is 32-bit wide
110 * - hence, we need only 36 * 256 * 4 = 36kBytes of cache.
111 *
112 * The performance gain, at least on synthetic benchmarks, is significant:
113 * cache lookup is about 15 times faster than direct hash calculation
114 */
115 const uint32_t *
116 toeplitz_cache_init(const uint8_t *key)
117 {
118 uint32_t *cache = kmem_alloc(SFXGE_TOEPLITZ_CACHE_SIZE *
119 sizeof (uint32_t), KM_SLEEP);
120 unsigned i;
121
122 for (i = 0; i < SFXGE_TOEPLITZ_IN_MAX; i++, key++) {
123 uint32_t key_bits[NBBY] = { 0 };
124 unsigned j;
125 unsigned mask;
126 unsigned byte;
127
128 #if defined(BE_IN32)
129 key_bits[0] = BE_IN32(key);
130 #else
131 key_bits[0] = BE_32(*(uint32_t *)key);
132 #endif
133 for (j = 1, mask = 1 << (NBBY - 1); j < NBBY; j++, mask >>= 1) {
134 key_bits[j] = key_bits[j - 1] << 1;
135 if ((key[sizeof (uint32_t)] & mask) != 0)
136 key_bits[j] |= 1;
137 }
138
139 for (byte = 0; byte <= UINT8_MAX; byte++) {
140 uint32_t res = 0;
141 for (j = 0, mask = 1 << (NBBY - 1);
142 j < NBBY;
143 j++, mask >>= 1) {
144 if (byte & mask)
145 res ^= key_bits[j];
146 }
147 cache[i * (UINT8_MAX + 1) + byte] = res;
148 }
149 }
150 return (cache);
151 }
152
153
154 int
155 sfxge_toeplitz_hash_init(sfxge_t *sp)
156 {
157 int rc;
158 uint8_t toeplitz_key[SFXGE_TOEPLITZ_KEY_LEN];
159
160 (void) random_get_pseudo_bytes(toeplitz_key, sizeof (toeplitz_key));
161
162 if ((rc = efx_rx_scale_mode_set(sp->s_enp, EFX_RX_HASHALG_TOEPLITZ,
163 (1 << EFX_RX_HASH_IPV4) | (1 << EFX_RX_HASH_TCPIPV4) |
164 (1 << EFX_RX_HASH_IPV6) | (1 << EFX_RX_HASH_TCPIPV6), B_TRUE)) != 0)
165 return (rc);
166
167 if ((rc = efx_rx_scale_key_set(sp->s_enp, toeplitz_key,
168 sizeof (toeplitz_key))) != 0)
169 return (rc);
170
171 sp->s_toeplitz_cache = toeplitz_cache_init(toeplitz_key);
172
173 return (0);
174 }
175
176 void
177 sfxge_toeplitz_hash_fini(sfxge_t *sp)
178 {
179 if (sp->s_toeplitz_cache != NULL) {
180 kmem_free((void *)sp->s_toeplitz_cache,
181 SFXGE_TOEPLITZ_CACHE_SIZE);
182 sp->s_toeplitz_cache = NULL;
183 }
184 }