1 /*
2 * Copyright (c) 2009 The DragonFly Project. All rights reserved.
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Sepherosa Ziehau <sepherosa@gmail.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 /*
36 * Toeplitz hash function
37 *
38 * This function is used to support Receive Side Scaling:
39 * http://www.microsoft.com/whdc/device/network/ndis_rss.mspx
40 *
41 * Two things are changed from the above paper:
42 * o Instead of creating random 40 bytes key string, we replicate
43 * 2 user defined bytes to form the 40 bytes key string. So the
44 * hash result of TCP segment is commutative. '2' is chosen,
45 * since the hash is calculated upon the binary string formed by
46 * concatenating faddr,laddr,fport,lport; the smallest unit is
47 * the size of the fport/lport, which is 2 bytes.
48 * o Precalculated hash result cache is used to reduce the heavy
49 * computation burden
50 *
51 * Thank Simon 'corecode' Schubert <corecode@fs.ei.tum.de> very much
52 * for various constructive suggestions. Without him, this will not
53 * be possible.
54 */
55
56 #include "opt_rss.h"
57
58 #include <sys/param.h>
59 #include <sys/kernel.h>
60 #include <sys/systm.h>
61 #include <sys/sysctl.h>
62
63 #include <net/toeplitz.h>
64 #include <net/toeplitz2.h>
65
66 #define TOEPLITZ_KEYSEED0 0x6d
67 #define TOEPLITZ_KEYSEED1 0x5a
68 #define TOEPLITZ_INIT_KEYLEN (TOEPLITZ_KEYSEED_CNT + sizeof(uint32_t))
69
70 static uint32_t toeplitz_keyseeds[TOEPLITZ_KEYSEED_CNT] =
71 { TOEPLITZ_KEYSEED0, TOEPLITZ_KEYSEED1 };
72
73 uint32_t toeplitz_cache[TOEPLITZ_KEYSEED_CNT][256];
74
75 TUNABLE_INT("net.toeplitz.keyseed0", &toeplitz_keyseeds[0]);
76 TUNABLE_INT("net.toeplitz.keyseed1", &toeplitz_keyseeds[1]);
77
78 SYSCTL_NODE(_net, OID_AUTO, toeplitz, CTLFLAG_RW, 0, "Toeplitz hash");
79 SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed0, CTLFLAG_RD,
80 &toeplitz_keyseeds[0], 0, "Toeplitz hash key seed0");
81 SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed1, CTLFLAG_RD,
82 &toeplitz_keyseeds[1], 0, "Toeplitz hash key seed1");
83
84 static void
toeplitz_cache_create(uint32_t cache[][256],int cache_len,const uint8_t key_str[],int key_strlen)85 toeplitz_cache_create(uint32_t cache[][256], int cache_len,
86 const uint8_t key_str[], int key_strlen)
87 {
88 int i;
89
90 for (i = 0; i < cache_len; ++i) {
91 uint32_t key[NBBY];
92 int j, b, shift, val;
93
94 bzero(key, sizeof(key));
95
96 /*
97 * Calculate 32bit keys for one byte; one key for each bit.
98 */
99 for (b = 0; b < NBBY; ++b) {
100 for (j = 0; j < 32; ++j) {
101 uint8_t k;
102 int bit;
103
104 bit = (i * NBBY) + b + j;
105
106 k = key_str[bit / NBBY];
107 shift = NBBY - (bit % NBBY) - 1;
108 if (k & (1 << shift))
109 key[b] |= 1 << (31 - j);
110 }
111 }
112
113 /*
114 * Cache the results of all possible bit combination of
115 * one byte.
116 */
117 for (val = 0; val < 256; ++val) {
118 uint32_t res = 0;
119
120 for (b = 0; b < NBBY; ++b) {
121 shift = NBBY - b - 1;
122 if (val & (1 << shift))
123 res ^= key[b];
124 }
125 cache[i][val] = res;
126 }
127 }
128 }
129
130 #ifdef RSS_DEBUG
131
132 static void
toeplitz_verify(void)133 toeplitz_verify(void)
134 {
135 in_addr_t faddr, laddr;
136 in_port_t fport, lport;
137
138 /*
139 * The first IPv4 example in the verification suite
140 */
141
142 /* 66.9.149.187:2794 */
143 faddr = 0xbb950942;
144 fport = 0xea0a;
145
146 /* 161.142.100.80:1766 */
147 laddr = 0x50648ea1;
148 lport = 0xe606;
149
150 kprintf("toeplitz: verify addr/port 0x%08x, addr 0x%08x\n",
151 toeplitz_rawhash_addrport(faddr, laddr, fport, lport),
152 toeplitz_rawhash_addr(faddr, laddr));
153 }
154
155 #endif /* RSS_DEBUG */
156
157 static void
toeplitz_init(void * dummy __unused)158 toeplitz_init(void *dummy __unused)
159 {
160 uint8_t key[TOEPLITZ_INIT_KEYLEN];
161 int i;
162
163 for (i = 0; i < TOEPLITZ_KEYSEED_CNT; ++i)
164 toeplitz_keyseeds[i] &= 0xff;
165
166 toeplitz_get_key(key, TOEPLITZ_INIT_KEYLEN);
167
168 #ifdef RSS_DEBUG
169 kprintf("toeplitz: keystr ");
170 for (i = 0; i < TOEPLITZ_INIT_KEYLEN; ++i)
171 kprintf("%02x ", key[i]);
172 kprintf("\n");
173 #endif
174
175 toeplitz_cache_create(toeplitz_cache, TOEPLITZ_KEYSEED_CNT,
176 key, TOEPLITZ_INIT_KEYLEN);
177
178 #ifdef RSS_DEBUG
179 toeplitz_verify();
180 #endif
181 }
182 /* After netisr_init */
183 SYSINIT(toeplitz, SI_SUB_PRE_DRIVERS, SI_ORDER_SECOND, toeplitz_init, NULL);
184
185 void
toeplitz_get_key(uint8_t * key,int keylen)186 toeplitz_get_key(uint8_t *key, int keylen)
187 {
188 int i;
189
190 if (keylen > TOEPLITZ_KEYLEN_MAX)
191 panic("invalid key length %d", keylen);
192
193 /* Replicate key seeds to form key */
194 for (i = 0; i < keylen; ++i)
195 key[i] = toeplitz_keyseeds[i % TOEPLITZ_KEYSEED_CNT];
196 }
197