The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/net/toeplitz.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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 }

Cache object: f1c2a4c8b6adda2d96d71549e2555ef8


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.