nataraid(4): Add devstat support.
[dragonfly.git] / sys / net / toeplitz.c
CommitLineData
cc85a685
SZ
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
4d334cdb
SZ
56#include "opt_rss.h"
57
cc85a685
SZ
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
d9304583 68#define TOEPLITZ_INIT_KEYLEN (TOEPLITZ_KEYSEED_CNT + sizeof(uint32_t))
cc85a685
SZ
69
70static uint32_t toeplitz_keyseeds[TOEPLITZ_KEYSEED_CNT] =
71 { TOEPLITZ_KEYSEED0, TOEPLITZ_KEYSEED1 };
72
73uint32_t toeplitz_cache[TOEPLITZ_KEYSEED_CNT][256];
74
75TUNABLE_INT("net.toeplitz.keyseed0", &toeplitz_keyseeds[0]);
76TUNABLE_INT("net.toeplitz.keyseed1", &toeplitz_keyseeds[1]);
77
78SYSCTL_NODE(_net, OID_AUTO, toeplitz, CTLFLAG_RW, 0, "Toeplitz hash");
79SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed0, CTLFLAG_RD,
80 &toeplitz_keyseeds[0], 0, "Toeplitz hash key seed0");
81SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed1, CTLFLAG_RD,
82 &toeplitz_keyseeds[1], 0, "Toeplitz hash key seed1");
83
cc85a685
SZ
84static void
85toeplitz_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
4d334cdb
SZ
130#ifdef RSS_DEBUG
131
132static void
133toeplitz_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",
b73d4152
SZ
151 toeplitz_rawhash_addrport(faddr, laddr, fport, lport),
152 toeplitz_rawhash_addr(faddr, laddr));
4d334cdb
SZ
153}
154
155#endif /* RSS_DEBUG */
156
cc85a685
SZ
157static void
158toeplitz_init(void *dummy __unused)
159{
d9304583 160 uint8_t key[TOEPLITZ_INIT_KEYLEN];
cc85a685
SZ
161 int i;
162
163 for (i = 0; i < TOEPLITZ_KEYSEED_CNT; ++i)
164 toeplitz_keyseeds[i] &= 0xff;
165
d9304583 166 toeplitz_get_key(key, TOEPLITZ_INIT_KEYLEN);
cc85a685 167
4d334cdb 168#ifdef RSS_DEBUG
d9304583
SZ
169 kprintf("toeplitz: keystr ");
170 for (i = 0; i < TOEPLITZ_INIT_KEYLEN; ++i)
171 kprintf("%02x ", key[i]);
172 kprintf("\n");
4d334cdb 173#endif
4d334cdb 174
cc85a685 175 toeplitz_cache_create(toeplitz_cache, TOEPLITZ_KEYSEED_CNT,
d9304583 176 key, TOEPLITZ_INIT_KEYLEN);
4d334cdb
SZ
177
178#ifdef RSS_DEBUG
179 toeplitz_verify();
180#endif
cc85a685
SZ
181}
182SYSINIT(toeplitz, SI_SUB_PRE_DRIVERS, SI_ORDER_FIRST, toeplitz_init, NULL);
b263df52 183
b263df52
SZ
184void
185toeplitz_get_key(uint8_t *key, int keylen)
186{
187 int i;
188
189 if (keylen > TOEPLITZ_KEYLEN_MAX)
190 panic("invalid key length %d\n", keylen);
191
192 /* Replicate key seeds to form key */
193 for (i = 0; i < keylen; ++i)
194 key[i] = toeplitz_keyseeds[i % TOEPLITZ_KEYSEED_CNT];
195}