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 #ifdef RSS 74 75 uint32_t toeplitz_cache[TOEPLITZ_KEYSEED_CNT][256]; 76 77 TUNABLE_INT("net.toeplitz.keyseed0", &toeplitz_keyseeds[0]); 78 TUNABLE_INT("net.toeplitz.keyseed1", &toeplitz_keyseeds[1]); 79 80 SYSCTL_NODE(_net, OID_AUTO, toeplitz, CTLFLAG_RW, 0, "Toeplitz hash"); 81 SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed0, CTLFLAG_RD, 82 &toeplitz_keyseeds[0], 0, "Toeplitz hash key seed0"); 83 SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed1, CTLFLAG_RD, 84 &toeplitz_keyseeds[1], 0, "Toeplitz hash key seed1"); 85 86 static void 87 toeplitz_cache_create(uint32_t cache[][256], int cache_len, 88 const uint8_t key_str[], int key_strlen) 89 { 90 int i; 91 92 for (i = 0; i < cache_len; ++i) { 93 uint32_t key[NBBY]; 94 int j, b, shift, val; 95 96 bzero(key, sizeof(key)); 97 98 /* 99 * Calculate 32bit keys for one byte; one key for each bit. 100 */ 101 for (b = 0; b < NBBY; ++b) { 102 for (j = 0; j < 32; ++j) { 103 uint8_t k; 104 int bit; 105 106 bit = (i * NBBY) + b + j; 107 108 k = key_str[bit / NBBY]; 109 shift = NBBY - (bit % NBBY) - 1; 110 if (k & (1 << shift)) 111 key[b] |= 1 << (31 - j); 112 } 113 } 114 115 /* 116 * Cache the results of all possible bit combination of 117 * one byte. 118 */ 119 for (val = 0; val < 256; ++val) { 120 uint32_t res = 0; 121 122 for (b = 0; b < NBBY; ++b) { 123 shift = NBBY - b - 1; 124 if (val & (1 << shift)) 125 res ^= key[b]; 126 } 127 cache[i][val] = res; 128 } 129 } 130 } 131 132 #ifdef RSS_DEBUG 133 134 static void 135 toeplitz_verify(void) 136 { 137 in_addr_t faddr, laddr; 138 in_port_t fport, lport; 139 140 /* 141 * The first IPv4 example in the verification suite 142 */ 143 144 /* 66.9.149.187:2794 */ 145 faddr = 0xbb950942; 146 fport = 0xea0a; 147 148 /* 161.142.100.80:1766 */ 149 laddr = 0x50648ea1; 150 lport = 0xe606; 151 152 kprintf("toeplitz: verify addr/port 0x%08x, addr 0x%08x\n", 153 toeplitz_rawhash_addrport(faddr, laddr, fport, lport), 154 toeplitz_rawhash_addr(faddr, laddr)); 155 } 156 157 #endif /* RSS_DEBUG */ 158 159 static void 160 toeplitz_init(void *dummy __unused) 161 { 162 uint8_t key[TOEPLITZ_INIT_KEYLEN]; 163 int i; 164 165 for (i = 0; i < TOEPLITZ_KEYSEED_CNT; ++i) 166 toeplitz_keyseeds[i] &= 0xff; 167 168 toeplitz_get_key(key, TOEPLITZ_INIT_KEYLEN); 169 170 #ifdef RSS_DEBUG 171 kprintf("toeplitz: keystr "); 172 for (i = 0; i < TOEPLITZ_INIT_KEYLEN; ++i) 173 kprintf("%02x ", key[i]); 174 kprintf("\n"); 175 #endif 176 177 toeplitz_cache_create(toeplitz_cache, TOEPLITZ_KEYSEED_CNT, 178 key, TOEPLITZ_INIT_KEYLEN); 179 180 #ifdef RSS_DEBUG 181 toeplitz_verify(); 182 #endif 183 } 184 SYSINIT(toeplitz, SI_SUB_PRE_DRIVERS, SI_ORDER_FIRST, toeplitz_init, NULL); 185 186 #endif /* RSS */ 187 188 void 189 toeplitz_get_key(uint8_t *key, int keylen) 190 { 191 int i; 192 193 if (keylen > TOEPLITZ_KEYLEN_MAX) 194 panic("invalid key length %d\n", keylen); 195 196 /* Replicate key seeds to form key */ 197 for (i = 0; i < keylen; ++i) 198 key[i] = toeplitz_keyseeds[i % TOEPLITZ_KEYSEED_CNT]; 199 } 200