sys/net/toeplitz.c

   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 }