drivers/xen/sfc_netutil/accel_cuckoo_hash.h

   1 /****************************************************************************
   2  * Solarflare driver for Xen network acceleration
   3  *
   4  * Copyright 2006-2008: Solarflare Communications Inc,
   5  *                      9501 Jeronimo Road, Suite 250,
   6  *                      Irvine, CA 92618, USA
   7  *
   8  * Maintained by Solarflare Communications <linux-xen-drivers@solarflare.com>
   9  *
  10  * This program is free software; you can redistribute it and/or modify it
  11  * under the terms of the GNU General Public License version 2 as published
  12  * by the Free Software Foundation, incorporated herein by reference.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  22  ****************************************************************************
  23  */
  24
  25 /*
  26  * A cuckoo hash table consists of two sub tables.  Each entry can
  27  * hash to a position in each table.  If, on entry, its position is
  28  * found to be occupied, the existing element is moved to it's other
  29  * location.  This recurses until success or a loop is found.  If a
  30  * loop is found the table is rehashed.
  31  *
  32  *  See http://www.it-c.dk/people/pagh/papers/cuckoo-jour.pdf
  33  */
  34
  35 #ifndef NET_ACCEL_CUCKOO_HASH_H
  36 #define NET_ACCEL_CUCKOO_HASH_H
  37
  38 /*! Type used for hash table keys of ip pairs */
  39 typedef struct {
  40         u32 local_ip;
  41         //u32 remote_ip;
  42         u16 local_port;
  43         //u16 remote_port;
  44         /* Technically only 1 bit, but use 16 to make key a round
  45            number size */
  46         u16 proto;
  47 } cuckoo_hash_ip_key;
  48
  49 /*! Type used for hash table keys of mac addresses */
  50 typedef u64 cuckoo_hash_mac_key;
  51
  52 /*! This type is designed to be large enough to hold all supported key
  53  *  sizes to avoid having to malloc storage for them.
  54  */
  55 typedef u64 cuckoo_hash_key;
  56
  57 /*! Type used for the values stored in the hash table */
  58 typedef int cuckoo_hash_value;
  59
  60 /*! Type used for the hash used to index the table */
  61 typedef u32 cuckoo_hash;
  62
  63 /*! How long to spend displacing values when adding before giving up
  64  *  and rehashing */
  65 #define CUCKOO_HASH_MAX_LOOP (hashtab->length)
  66
  67 /*! State of hash table entry */
  68 typedef enum {
  69         CUCKOO_HASH_STATE_VACANT = 0,
  70         CUCKOO_HASH_STATE_OCCUPIED
  71 } cuckoo_hash_state;
  72
  73 /*! An entry in the hash table */
  74 typedef struct {
  75         cuckoo_hash_state state;
  76         cuckoo_hash_key key;
  77         cuckoo_hash_value value;
  78 } cuckoo_hash_entry;
  79
  80 /*! A cuckoo hash table */
  81 typedef struct {
  82         /*! The length of each table (NB. there are two tables of this
  83          *  length) */
  84         unsigned length;
  85         /*! The length of each table in bits */
  86         unsigned length_bits;
  87         /*! The length of the key in bytes */
  88         unsigned key_length;
  89         /*! The number of entries currently stored in the table */
  90         unsigned entries;
  91         /*! Index into table used by cuckoo_hash_iterate */
  92         unsigned iterate_index;
  93
  94         /* parameter of hash functions */
  95         /*! The "a" parameter of the first hash function */
  96         cuckoo_hash_key a0;
  97         /*! The "a" parameter of the second hash function */
  98         cuckoo_hash_key a1;
  99
 100         /*! The first table */
 101         cuckoo_hash_entry *table0;
 102         /*! The second table */
 103         cuckoo_hash_entry *table1;
 104 } cuckoo_hash_table;
 105
 106 /*! Initialise the cuckoo has table
 107  *
 108  * \param hashtab A pointer to an unitialised hash table structure
 109  * \param length_bits The number of elements in each table equals
 110  * 2**length_bits
 111  * \param key_length The length of the key in bytes
 112  *
 113  * \return 0 on success, -ENOMEM if it couldn't allocate the tables
 114  */
 115 extern
 116 int cuckoo_hash_init(cuckoo_hash_table *hashtab, unsigned length_bits,
 117                      unsigned key_length);
 118
 119
 120 /*! Destroy a hash table
 121  *
 122  * \param hashtab A hash table that has previously been passed to a
 123  * successful call of cuckoo_hash_init()
 124  */
 125 extern
 126 void cuckoo_hash_destroy(cuckoo_hash_table *hashtab);
 127
 128
 129 /*! Lookup an entry in the hash table
 130  *
 131  * \param hashtab The hash table in which to look.
 132  * \param key Pointer to a mac address to use as the key
 133  * \param value On exit set to the value stored if key was present
 134  *
 135  * \return 0 if not present in the table, non-zero if it is (and value
 136  * is set accordingly)
 137  */
 138 extern
 139 int cuckoo_hash_lookup(cuckoo_hash_table *hashtab,
 140                        cuckoo_hash_key *key,
 141                        cuckoo_hash_value *value);
 142
 143 /*! Add an entry to the hash table.  Key must not be a duplicate of
 144  * anything already in the table.  If this is a risk, see
 145  * cuckoo_hash_add_check
 146  *
 147  * \param hashtab The hash table to add the entry to
 148  * \param key Pointer to a mac address to use as a key
 149  * \param value The value to store
 150  * \param can_rehash Flag to allow the add function to rehash the
 151  * table if necessary
 152  *
 153  * \return 0 on success, non-zero on failure.  -ENOSPC means it just
 154  * couldn't find anywhere to put it - this is bad and probably means
 155  * an entry has been dropped on the floor (but the entry you just
 156  * tried to add may now be included)
 157  */
 158 extern
 159 int cuckoo_hash_add(cuckoo_hash_table *hashtab,
 160                     cuckoo_hash_key *key,
 161                     cuckoo_hash_value value,
 162                     int can_rehash);
 163
 164 /*! Same as cuckoo_hash_add but first checks to ensure entry is not
 165  * already there
 166  * \return -EBUSY if already there
 167  */
 168
 169 extern
 170 int cuckoo_hash_add_check(cuckoo_hash_table *hashtab,
 171                           cuckoo_hash_key *key,
 172                           cuckoo_hash_value value,
 173                           int can_rehash);
 174 /*! Remove an entry from the table
 175  *
 176  * \param hashtab The hash table to remove the entry from
 177  * \param key The key that was used to previously add the entry
 178  *
 179  * \return 0 on success, -EINVAL if the entry couldn't be found
 180  */
 181 extern
 182 int cuckoo_hash_remove(cuckoo_hash_table *hashtab, cuckoo_hash_key *key);
 183
 184
 185 /*! Helper for those using mac addresses to convert to a key for the
 186  *  hash table
 187  */
 188 static inline cuckoo_hash_mac_key cuckoo_mac_to_key(const u8 *mac)
 189 {
 190         return (cuckoo_hash_mac_key)(mac[0])
 191                 | (cuckoo_hash_mac_key)(mac[1]) << 8
 192                 | (cuckoo_hash_mac_key)(mac[2]) << 16
 193                 | (cuckoo_hash_mac_key)(mac[3]) << 24
 194                 | (cuckoo_hash_mac_key)(mac[4]) << 32
 195                 | (cuckoo_hash_mac_key)(mac[5]) << 40;
 196 }
 197
 198
 199 /*! Update an entry already in the hash table to take a new value
 200  *
 201  * \param hashtab The hash table to add the entry to
 202  * \param key Pointer to a mac address to use as a key
 203  * \param value The value to store
 204  *
 205  * \return 0 on success, non-zero on failure.
 206  */
 207 int cuckoo_hash_update(cuckoo_hash_table *hashtab, cuckoo_hash_key *key,
 208                        cuckoo_hash_value value);
 209
 210
 211 /*! Go through the hash table and return all used entries (one per call)
 212  *
 213  * \param hashtab The hash table to iterate over
 214  * \param key Pointer to a key to take the returned key
 215  * \param value Pointer to a value to take the returned value
 216  *
 217  * \return 0 on success (key, value set), non-zero on failure.
 218  */
 219 int cuckoo_hash_iterate(cuckoo_hash_table *hashtab,
 220                         cuckoo_hash_key *key, cuckoo_hash_value *value);
 221 void cuckoo_hash_iterate_reset(cuckoo_hash_table *hashtab);
 222
 223 /* debug, not compiled by default */
 224 void cuckoo_hash_valid(cuckoo_hash_table *hashtab);
 225 void cuckoo_hash_dump(cuckoo_hash_table *hashtab);
 226
 227 #endif /* NET_ACCEL_CUCKOO_HASH_H */