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 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", 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 }