drivers/net/sfc/sfc_resource/falcon_hash.c

   1 /****************************************************************************
   2  * Driver for Solarflare network controllers -
   3  *          resource management for Xen backend, OpenOnload, etc
   4  *           (including support for SFE4001 10GBT NIC)
   5  *
   6  * This file contains EtherFabric NIC hash algorithms implementation.
   7  *
   8  * Copyright 2005-2007: Solarflare Communications Inc,
   9  *                      9501 Jeronimo Road, Suite 250,
  10  *                      Irvine, CA 92618, USA
  11  *
  12  * Developed and maintained by Solarflare Communications:
  13  *                      <linux-xen-drivers@solarflare.com>
  14  *                      <onload-dev@solarflare.com>
  15  *
  16  *
  17  * This program is free software; you can redistribute it and/or modify it
  18  * under the terms of the GNU General Public License version 2 as published
  19  * by the Free Software Foundation, incorporated herein by reference.
  20  *
  21  * This program is distributed in the hope that it will be useful,
  22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24  * GNU General Public License for more details.
  25  *
  26  * You should have received a copy of the GNU General Public License
  27  * along with this program; if not, write to the Free Software
  28  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  29  ****************************************************************************
  30  */
  31
  32 #include <ci/efhw/debug.h>
  33 #include <ci/driver/efab/hardware.h>
  34
  35
  36 static unsigned int
  37 common_get_ip_key(unsigned int src_ip, unsigned int src_port,
  38                   unsigned int dest_ip, unsigned int dest_port,
  39                   int tcp, int full, int tx, unsigned int masked_q_id)
  40 {
  41
  42         unsigned int tmp_port, result;
  43
  44         EFHW_ASSERT(tcp == 0 || tcp == 1);
  45         EFHW_ASSERT(full == 0 || full == 1);
  46         EFHW_ASSERT(masked_q_id < (1 << 10));
  47
  48         /* m=masked_q_id(TX)/0(RX)  u=UDP  S,D=src/dest addr  s,d=src/dest port
  49          *
  50          * Wildcard filters have src(TX)/dest(RX) addr and port = 0;
  51          * and UDP wildcard filters have the src and dest port fields swapped.
  52          *
  53          * Addr/port fields are little-endian.
  54          *
  55          * 3322222222221111111111
  56          * 10987654321098765432109876543210
  57          *
  58          * 000000000000000000000mmmmmmmmmmu ^
  59          * DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD ^
  60          * ddddddddddddddddSSSSSSSSSSSSSSSS ^
  61          * SSSSSSSSSSSSSSSSssssssssssssssss
  62          */
  63
  64         if (!tx)
  65                 masked_q_id = 0;
  66
  67         if (!full) {
  68                 if (tx) {
  69                         dest_ip = 0;
  70                         dest_port = 0;
  71                 } else {
  72                         src_ip = 0;
  73                         src_port = 0;
  74                 }
  75                 if (!tcp) {
  76                         tmp_port = src_port;
  77                         src_port = dest_port;
  78                         dest_port = tmp_port;
  79                 }
  80         }
  81
  82         result = ((masked_q_id << 1) | (!tcp))                              ^
  83                  (dest_ip)                                                  ^
  84                  (((dest_port & 0xffff) << 16) | ((src_ip >> 16) & 0xffff)) ^
  85                  (((src_ip & 0xffff) << 16) | (src_port & 0xffff));
  86
  87         EFHW_TRACE("%s: IP %s %s %x", __func__, tcp ? "TCP" : "UDP",
  88                    full ? "Full" : "Wildcard", result);
  89
  90         return result;
  91 }
  92
  93
  94 unsigned int
  95 falcon_hash_get_ip_key(unsigned int src_ip, unsigned int src_port,
  96                        unsigned int dest_ip, unsigned int dest_port,
  97                        int tcp, int full)
  98 {
  99         return common_get_ip_key(src_ip, src_port, dest_ip, dest_port, tcp,
 100                                  full, 0, 0);
 101 }
 102
 103
 104 /* This function generates the First Hash key */
 105 unsigned int falcon_hash_function1(unsigned int key, unsigned int nfilters)
 106 {
 107
 108         unsigned short int lfsr_reg;
 109         unsigned int tmp_key;
 110         int index;
 111
 112         unsigned short int lfsr_input;
 113         unsigned short int single_bit_key;
 114         unsigned short int bit16_lfsr;
 115         unsigned short int bit3_lfsr;
 116
 117         lfsr_reg = 0xFFFF;
 118         tmp_key = key;
 119
 120         /* For Polynomial equation X^16+X^3+1 */
 121         for (index = 0; index < 32; index++) {
 122                 /* Get the bit from key and shift the key */
 123                 single_bit_key = (tmp_key & 0x80000000) >> 31;
 124                 tmp_key = tmp_key << 1;
 125
 126                 /* get the Tap bits to XOR operation */
 127                 bit16_lfsr = (lfsr_reg & 0x8000) >> 15;
 128                 bit3_lfsr = (lfsr_reg & 0x0004) >> 2;
 129
 130                 /* Get the Input value to the LFSR */
 131                 lfsr_input = ((bit16_lfsr ^ bit3_lfsr) ^ single_bit_key);
 132
 133                 /* Shift and store out of the two TAPs */
 134                 lfsr_reg = lfsr_reg << 1;
 135                 lfsr_reg = lfsr_reg | (lfsr_input & 0x0001);
 136
 137         }
 138
 139         lfsr_reg = lfsr_reg & (nfilters - 1);
 140
 141         return lfsr_reg;
 142 }
 143
 144 /* This function generates the Second Hash */
 145 unsigned int
 146 falcon_hash_function2(unsigned int key, unsigned int nfilters)
 147 {
 148         return (unsigned int)(((unsigned long long)key * 2 - 1) &
 149                               (nfilters - 1));
 150 }
 151
 152 /* This function iterates through the hash table */
 153 unsigned int
 154 falcon_hash_iterator(unsigned int hash1, unsigned int hash2,
 155                      unsigned int n_search, unsigned int nfilters)
 156 {
 157         return (hash1 + (n_search * hash2)) & (nfilters - 1);
 158 }
 159