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 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 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 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 SYSINIT(toeplitz, SI_SUB_PRE_DRIVERS, SI_ORDER_FIRST, toeplitz_init, NULL); 183 184 void 185 toeplitz_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 } 196