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