lib/librte_table/rte_table_hash.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   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  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * 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  *     * Neither the name of Intel Corporation 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 FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #ifndef __INCLUDE_RTE_TABLE_HASH_H__
  35 #define __INCLUDE_RTE_TABLE_HASH_H__
  36
  37 #ifdef __cplusplus
  38 extern "C" {
  39 #endif
  40
  41 /**
  42  * @file
  43  * RTE Table Hash
  44  *
  45  * These tables use the exact match criterion to uniquely associate data to
  46  * lookup keys.
  47  *
  48  * Use-cases: Flow classification table, Address Resolution Protocol (ARP) table
  49  *
  50  * Hash table types:
  51  * 1. Entry add strategy on bucket full:
  52  *     a. Least Recently Used (LRU): One of the existing keys in the bucket is
  53  *        deleted and the new key is added in its place. The number of keys in
  54  *        each bucket never grows bigger than 4. The logic to pick the key to
  55  *        be dropped from the bucket is LRU. The hash table lookup operation
  56  *        maintains the order in which the keys in the same bucket are hit, so
  57  *        every time a key is hit, it becomes the new Most Recently Used (MRU)
  58  *        key, i.e. the most unlikely candidate for drop. When a key is added
  59  *        to the bucket, it also becomes the new MRU key. When a key needs to
  60  *        be picked and dropped, the most likely candidate for drop, i.e. the
  61  *        current LRU key, is always picked. The LRU logic requires maintaining
  62  *        specific data structures per each bucket.
  63  *     b. Extendible bucket (ext): The bucket is extended with space for 4 more
  64  *        keys. This is done by allocating additional memory at table init time,
  65  *        which is used to create a pool of free keys (the size of this pool is
  66  *        configurable and always a multiple of 4). On key add operation, the
  67  *        allocation of a group of 4 keys only happens successfully within the
  68  *        limit of free keys, otherwise the key add operation fails. On key
  69  *        delete operation, a group of 4 keys is freed back to the pool of free
  70  *        keys when the key to be deleted is the only key that was used within
  71  *        its group of 4 keys at that time. On key lookup operation, if the
  72  *        current bucket is in extended state and a match is not found in the
  73  *        first group of 4 keys, the search continues beyond the first group of
  74  *        4 keys, potentially until all keys in this bucket are examined. The
  75  *        extendible bucket logic requires maintaining specific data structures
  76  *        per table and per each bucket.
  77  * 2. Key signature computation:
  78  *     a. Pre-computed key signature: The key lookup operation is split between
  79  *        two CPU cores. The first CPU core (typically the CPU core performing
  80  *        packet RX) extracts the key from the input packet, computes the key
  81  *        signature and saves both the key and the key signature in the packet
  82  *        buffer as packet meta-data. The second CPU core reads both the key and
  83  *        the key signature from the packet meta-data and performs the bucket
  84  *        search step of the key lookup operation.
  85  *     b. Key signature computed on lookup (do-sig): The same CPU core reads
  86  *        the key from the packet meta-data, uses it to compute the key
  87  *        signature and also performs the bucket search step of the key lookup
  88  *        operation.
  89  * 3. Key size:
  90  *     a. Configurable key size
  91  *     b. Single key size (8-byte, 16-byte or 32-byte key size)
  92  *
  93  ***/
  94 #include <stdint.h>
  95
  96 #include "rte_table.h"
  97
  98 /** Hash function */
  99 typedef uint64_t (*rte_table_hash_op_hash)(
 100         void *key,
 101         uint32_t key_size,
 102         uint64_t seed);
 103
 104 /**
 105  * Hash tables with configurable key size
 106  *
 107  */
 108 /** Extendible bucket hash table parameters */
 109 struct rte_table_hash_ext_params {
 110         /** Key size (number of bytes) */
 111         uint32_t key_size;
 112
 113         /** Maximum number of keys */
 114         uint32_t n_keys;
 115
 116         /** Number of hash table buckets. Each bucket stores up to 4 keys. */
 117         uint32_t n_buckets;
 118
 119         /** Number of hash table bucket extensions. Each bucket extension has
 120         space for 4 keys and each bucket can have 0, 1 or more extensions. */
 121         uint32_t n_buckets_ext;
 122
 123         /** Hash function */
 124         rte_table_hash_op_hash f_hash;
 125
 126         /** Seed value for the hash function */
 127         uint64_t seed;
 128
 129         /** Byte offset within packet meta-data where the 4-byte key signature
 130         is located. Valid for pre-computed key signature tables, ignored for
 131         do-sig tables. */
 132         uint32_t signature_offset;
 133
 134         /** Byte offset within packet meta-data where the key is located */
 135         uint32_t key_offset;
 136 };
 137
 138 /** Extendible bucket hash table operations for pre-computed key signature */
 139 extern struct rte_table_ops rte_table_hash_ext_ops;
 140
 141 /** Extendible bucket hash table operations for key signature computed on
 142         lookup ("do-sig") */
 143 extern struct rte_table_ops rte_table_hash_ext_dosig_ops;
 144
 145 /** LRU hash table parameters */
 146 struct rte_table_hash_lru_params {
 147         /** Key size (number of bytes) */
 148         uint32_t key_size;
 149
 150         /** Maximum number of keys */
 151         uint32_t n_keys;
 152
 153         /** Number of hash table buckets. Each bucket stores up to 4 keys. */
 154         uint32_t n_buckets;
 155
 156         /** Hash function */
 157         rte_table_hash_op_hash f_hash;
 158
 159         /** Seed value for the hash function */
 160         uint64_t seed;
 161
 162         /** Byte offset within packet meta-data where the 4-byte key signature
 163         is located. Valid for pre-computed key signature tables, ignored for
 164         do-sig tables. */
 165         uint32_t signature_offset;
 166
 167         /** Byte offset within packet meta-data where the key is located */
 168         uint32_t key_offset;
 169 };
 170
 171 /** LRU hash table operations for pre-computed key signature */
 172 extern struct rte_table_ops rte_table_hash_lru_ops;
 173
 174 /** LRU hash table operations for key signature computed on lookup ("do-sig") */
 175 extern struct rte_table_ops rte_table_hash_lru_dosig_ops;
 176
 177 /**
 178  * 8-byte key hash tables
 179  *
 180  */
 181 /** LRU hash table parameters */
 182 struct rte_table_hash_key8_lru_params {
 183         /** Maximum number of entries (and keys) in the table */
 184         uint32_t n_entries;
 185
 186         /** Hash function */
 187         rte_table_hash_op_hash f_hash;
 188
 189         /** Seed for the hash function */
 190         uint64_t seed;
 191
 192         /** Byte offset within packet meta-data where the 4-byte key signature
 193         is located. Valid for pre-computed key signature tables, ignored for
 194         do-sig tables. */
 195         uint32_t signature_offset;
 196
 197         /** Byte offset within packet meta-data where the key is located */
 198         uint32_t key_offset;
 199
 200         /** Bit-mask to be AND-ed to the key on lookup */
 201         uint8_t *key_mask;
 202 };
 203
 204 extern struct rte_table_ops rte_table_hash_key8_lru_ops;
 205
 206 /** Extendible bucket hash table parameters */
 207 struct rte_table_hash_key8_ext_params {
 208         /** Maximum number of entries (and keys) in the table */
 209         uint32_t n_entries;
 210
 211         /** Number of entries (and keys) for hash table bucket extensions. Each
 212                 bucket is extended in increments of 4 keys. */
 213         uint32_t n_entries_ext;
 214
 215         /** Hash function */
 216         rte_table_hash_op_hash f_hash;
 217
 218         /** Seed for the hash function */
 219         uint64_t seed;
 220
 221         /** Byte offset within packet meta-data where the 4-byte key signature
 222         is located. Valid for pre-computed key signature tables, ignored for
 223         do-sig tables. */
 224         uint32_t signature_offset;
 225
 226         /** Byte offset within packet meta-data where the key is located */
 227         uint32_t key_offset;
 228
 229         /** Bit-mask to be AND-ed to the key on lookup */
 230         uint8_t *key_mask;
 231 };
 232
 233 extern struct rte_table_ops rte_table_hash_key8_ext_ops;
 234
 235 /**
 236  * 16-byte key hash tables
 237  *
 238  */
 239 /** LRU hash table parameters */
 240 struct rte_table_hash_key16_lru_params {
 241         /** Maximum number of entries (and keys) in the table */
 242         uint32_t n_entries;
 243
 244         /** Hash function */
 245         rte_table_hash_op_hash f_hash;
 246
 247         /** Seed for the hash function */
 248         uint64_t seed;
 249
 250         /** Byte offset within packet meta-data where the 4-byte key signature
 251         is located. Valid for pre-computed key signature tables, ignored for
 252         do-sig tables. */
 253         uint32_t signature_offset;
 254
 255         /** Byte offset within packet meta-data where the key is located */
 256         uint32_t key_offset;
 257
 258         /** Bit-mask to be AND-ed to the key on lookup */
 259         uint8_t *key_mask;
 260 };
 261
 262 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
 263
 264 /** Extendible bucket hash table parameters */
 265 struct rte_table_hash_key16_ext_params {
 266         /** Maximum number of entries (and keys) in the table */
 267         uint32_t n_entries;
 268
 269         /** Number of entries (and keys) for hash table bucket extensions. Each
 270         bucket is extended in increments of 4 keys. */
 271         uint32_t n_entries_ext;
 272
 273         /** Hash function */
 274         rte_table_hash_op_hash f_hash;
 275
 276         /** Seed for the hash function */
 277         uint64_t seed;
 278
 279         /** Byte offset within packet meta-data where the 4-byte key signature
 280         is located. Valid for pre-computed key signature tables, ignored for
 281         do-sig tables. */
 282         uint32_t signature_offset;
 283
 284         /** Byte offset within packet meta-data where the key is located */
 285         uint32_t key_offset;
 286
 287         /** Bit-mask to be AND-ed to the key on lookup */
 288         uint8_t *key_mask;
 289 };
 290
 291 extern struct rte_table_ops rte_table_hash_key16_ext_ops;
 292
 293 /**
 294  * 32-byte key hash tables
 295  *
 296  */
 297 /** LRU hash table parameters */
 298 struct rte_table_hash_key32_lru_params {
 299         /** Maximum number of entries (and keys) in the table */
 300         uint32_t n_entries;
 301
 302         /** Hash function */
 303         rte_table_hash_op_hash f_hash;
 304
 305         /** Seed for the hash function */
 306         uint64_t seed;
 307
 308         /** Byte offset within packet meta-data where the 4-byte key signature
 309         is located. Valid for pre-computed key signature tables, ignored for
 310         do-sig tables. */
 311         uint32_t signature_offset;
 312
 313         /** Byte offset within packet meta-data where the key is located */
 314         uint32_t key_offset;
 315 };
 316
 317 /** LRU hash table operations for pre-computed key signature */
 318 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
 319
 320 /** Extendible bucket hash table parameters */
 321 struct rte_table_hash_key32_ext_params {
 322         /** Maximum number of entries (and keys) in the table */
 323         uint32_t n_entries;
 324
 325         /** Number of entries (and keys) for hash table bucket extensions. Each
 326                 bucket is extended in increments of 4 keys. */
 327         uint32_t n_entries_ext;
 328
 329         /** Hash function */
 330         rte_table_hash_op_hash f_hash;
 331
 332         /** Seed for the hash function */
 333         uint64_t seed;
 334
 335         /** Byte offset within packet meta-data where the 4-byte key signature
 336         is located. Valid for pre-computed key signature tables, ignored for
 337         do-sig tables. */
 338         uint32_t signature_offset;
 339
 340         /** Byte offset within packet meta-data where the key is located */
 341         uint32_t key_offset;
 342 };
 343
 344 /** Extendible bucket hash table operations */
 345 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
 346
 347 /** Cuckoo hash table parameters */
 348 struct rte_table_hash_cuckoo_params {
 349     /** Key size (number of bytes */
 350                 uint32_t key_size;
 351
 352         /** Maximum number of hash table entries */
 353         uint32_t n_keys;
 354
 355         /** Hash function used to calculate hash */
 356         rte_table_hash_op_hash f_hash;
 357
 358         /** Seed value or Init value used by f_hash */
 359         uint32_t seed;
 360
 361         /** Byte offset within packet meta-data where the 4-byte key signature
 362         is located. Valid for pre-computed key signature tables, ignored for
 363         do-sig tables. */
 364         uint32_t signature_offset;
 365
 366         /** Byte offset within packet meta-data where the key is located */
 367         uint32_t key_offset;
 368
 369         /** Hash table name */
 370         const char *name;
 371 };
 372
 373 /** Cuckoo hash table operations */
 374 extern struct rte_table_ops rte_table_hash_cuckoo_dosig_ops;
 375
 376 #ifdef __cplusplus
 377 }
 378 #endif
 379
 380 #endif