1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 
  22 /*
  23  * Copyright 2008-2015 Solarflare Communications Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26 
  27 #include <sys/param.h>
  28 #include <sys/int_limits.h>
  29 #include <sys/byteorder.h>
  30 #include <sys/random.h>
  31 #include <sys/types.h>
  32 #include <sys/kmem.h>
  33 #include <netinet/in.h>
  34 #include "sfxge.h"
  35 #include "efx.h"
  36 
  37 /*
  38  * The largest amount of the data which the hash may be calculated over
  39  * is a 4-tuple of source/destination IPv6 addresses (2 x 16 bytes)
  40  * and source/destination TCP port numbers (2 x 2 bytes), adding up to 40 bytes
  41  */
  42 #define SFXGE_TOEPLITZ_IN_MAX \
  43         (2 * (sizeof (struct in6_addr) + sizeof (in_port_t)))
  44 #define SFXGE_TOEPLITZ_CACHE_SIZE (SFXGE_TOEPLITZ_IN_MAX * (UINT8_MAX + 1))
  45 
  46 static uint32_t
  47 toeplitz_hash(const uint32_t *cache, const uint8_t *input,
  48         unsigned pos, unsigned datalen)
  49 {
  50         uint32_t hash = 0;
  51         for (; datalen != 0; datalen--, pos++, input++) {
  52                 hash ^= cache[pos * (UINT8_MAX + 1) + *input];
  53         }
  54 
  55         return (hash);
  56 }
  57 
  58 uint32_t
  59 sfxge_toeplitz_hash(sfxge_t *sp, unsigned int addr_size,
  60     uint8_t *src_addr, uint16_t src_port, uint8_t *dst_addr, uint16_t dst_port)
  61 {
  62         uint32_t hash = 0;
  63         unsigned pos = 0;
  64 
  65         hash ^= toeplitz_hash(sp->s_toeplitz_cache, src_addr, pos, addr_size);
  66         pos += addr_size;
  67         hash ^= toeplitz_hash(sp->s_toeplitz_cache, dst_addr, pos, addr_size);
  68         pos += addr_size;
  69         if (src_port != 0 || dst_port != 0) {
  70                 hash ^= toeplitz_hash(sp->s_toeplitz_cache,
  71                     (const uint8_t *)&src_port, pos, sizeof (src_port));
  72                 pos += sizeof (src_port);
  73                 hash ^= toeplitz_hash(sp->s_toeplitz_cache,
  74                     (const uint8_t *)&dst_port, pos, sizeof (dst_port));
  75         }
  76         return (hash);
  77 }
  78 
  79 /*
  80  * The algorithm to calculate RSS Toeplitz hash is essentially as follows:
  81  * - Regard a Toeplitz key and an input as bit strings, with the
  82  * most significant bit of the first byte being the first bit
  83  * - Let's have a 32-bit window sliding over the Toeplitz key bit by bit
  84  * - Let the initial value of the hash be zero
  85  * - Then for every bit in the input that is set to 1, XOR the value of the
  86  *   window at a given bit position into the resulting hash
  87  *
  88  * First we note that since XOR is commutative and associative, the
  89  * resulting hash is just a XOR of subhashes for every input bit:
  90  *        H = H_0 XOR H_1 XOR ... XOR H_n               (1)
  91  * Then we note that every H_i is only dependent on the value of i and
  92  * the value of i'th bit of input, but not on any preceding or following
  93  * input bits.
  94  * Then we note that (1) holds also for any bit sequences,
  95  * e.g. for bytes of input:
  96  *       H = H_0_7 XOR H_8_15 XOR ... XOR H_(n-7)_n     (2)
  97  * and every
  98  *       H_i_j = H_i XOR H_(i+1) ... XOR H_j.           (3)
  99  *
 100  * It naturally follows than H_i_(i+7) only depends on the value of the byte
 101  * and the position of the byte in the input.
 102  * Therefore we may pre-calculate the value of each byte sub-hash H_i_(i+7)
 103  * for each possible byte value and each possible byte input position, and
 104  * then just assemble the hash of the packet byte-by-byte instead of
 105  * bit-by-bit.
 106  *
 107  * The amount of memory required for such a cache is not prohibitive:
 108  * - we have at most 36 bytes of input, each holding 256 possible values
 109  * - and the hash is 32-bit wide
 110  * - hence, we need only 36 * 256 * 4 = 36kBytes of cache.
 111  *
 112  * The performance gain, at least on synthetic benchmarks, is significant:
 113  * cache lookup is about 15 times faster than direct hash calculation
 114  */
 115 const uint32_t *
 116 toeplitz_cache_init(const uint8_t *key)
 117 {
 118         uint32_t *cache = kmem_alloc(SFXGE_TOEPLITZ_CACHE_SIZE *
 119             sizeof (uint32_t), KM_SLEEP);
 120         unsigned i;
 121 
 122         for (i = 0; i < SFXGE_TOEPLITZ_IN_MAX; i++, key++) {
 123                 uint32_t key_bits[NBBY] = { 0 };
 124                 unsigned j;
 125                 unsigned mask;
 126                 unsigned byte;
 127 
 128 #if defined(BE_IN32)
 129                 key_bits[0] = BE_IN32(key);
 130 #else
 131                 key_bits[0] = BE_32(*(uint32_t *)key);
 132 #endif
 133                 for (j = 1, mask = 1 << (NBBY - 1); j < NBBY; j++, mask >>= 1) {
 134                         key_bits[j] = key_bits[j - 1] << 1;
 135                         if ((key[sizeof (uint32_t)] & mask) != 0)
 136                                 key_bits[j] |= 1;
 137                 }
 138 
 139                 for (byte = 0; byte <= UINT8_MAX; byte++) {
 140                         uint32_t res = 0;
 141                         for (j = 0, mask = 1 << (NBBY - 1);
 142                             j < NBBY;
 143                             j++, mask >>= 1) {
 144                                 if (byte & mask)
 145                                         res ^= key_bits[j];
 146                         }
 147                         cache[i * (UINT8_MAX + 1) + byte] = res;
 148                 }
 149         }
 150         return (cache);
 151 }
 152 
 153 
 154 int
 155 sfxge_toeplitz_hash_init(sfxge_t *sp)
 156 {
 157         int rc;
 158         uint8_t toeplitz_key[SFXGE_TOEPLITZ_KEY_LEN];
 159 
 160         (void) random_get_pseudo_bytes(toeplitz_key, sizeof (toeplitz_key));
 161 
 162         if ((rc = efx_rx_scale_mode_set(sp->s_enp, EFX_RX_HASHALG_TOEPLITZ,
 163             (1 << EFX_RX_HASH_IPV4) | (1 << EFX_RX_HASH_TCPIPV4) |
 164             (1 << EFX_RX_HASH_IPV6) | (1 << EFX_RX_HASH_TCPIPV6), B_TRUE)) != 0)
 165                 return (rc);
 166 
 167         if ((rc = efx_rx_scale_key_set(sp->s_enp, toeplitz_key,
 168             sizeof (toeplitz_key))) != 0)
 169                 return (rc);
 170 
 171         sp->s_toeplitz_cache = toeplitz_cache_init(toeplitz_key);
 172 
 173         return (0);
 174 }
 175 
 176 void
 177 sfxge_toeplitz_hash_fini(sfxge_t *sp)
 178 {
 179         if (sp->s_toeplitz_cache != NULL) {
 180                 kmem_free((void *)sp->s_toeplitz_cache,
 181                     SFXGE_TOEPLITZ_CACHE_SIZE);
 182                 sp->s_toeplitz_cache = NULL;
 183         }
 184 }