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