lib/librte_table/rte_table_hash.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2017 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  * Hash table types:
  49  * 1. Entry add strategy on bucket full:
  50  *     a. Least Recently Used (LRU): One of the existing keys in the bucket is
  51  *        deleted and the new key is added in its place. The number of keys in
  52  *        each bucket never grows bigger than 4. The logic to pick the key to
  53  *        be dropped from the bucket is LRU. The hash table lookup operation
  54  *        maintains the order in which the keys in the same bucket are hit, so
  55  *        every time a key is hit, it becomes the new Most Recently Used (MRU)
  56  *        key, i.e. the most unlikely candidate for drop. When a key is added
  57  *        to the bucket, it also becomes the new MRU key. When a key needs to
  58  *        be picked and dropped, the most likely candidate for drop, i.e. the
  59  *        current LRU key, is always picked. The LRU logic requires maintaining
  60  *        specific data structures per each bucket. Use-cases: flow cache, etc.
  61  *     b. Extendible bucket (ext): The bucket is extended with space for 4 more
  62  *        keys. This is done by allocating additional memory at table init time,
  63  *        which is used to create a pool of free keys (the size of this pool is
  64  *        configurable and always a multiple of 4). On key add operation, the
  65  *        allocation of a group of 4 keys only happens successfully within the
  66  *        limit of free keys, otherwise the key add operation fails. On key
  67  *        delete operation, a group of 4 keys is freed back to the pool of free
  68  *        keys when the key to be deleted is the only key that was used within
  69  *        its group of 4 keys at that time. On key lookup operation, if the
  70  *        current bucket is in extended state and a match is not found in the
  71  *        first group of 4 keys, the search continues beyond the first group of
  72  *        4 keys, potentially until all keys in this bucket are examined. The
  73  *        extendible bucket logic requires maintaining specific data structures
  74  *        per table and per each bucket. Use-cases: flow table, etc.
  75  * 2. Key size:
  76  *     a. Configurable key size
  77  *     b. Single key size (8-byte, 16-byte or 32-byte key size)
  78  *
  79  ***/
  80 #include <stdint.h>
  81
  82 #include "rte_table.h"
  83
  84 /** Hash function */
  85 typedef uint64_t (*rte_table_hash_op_hash)(
  86         void *key,
  87         void *key_mask,
  88         uint32_t key_size,
  89         uint64_t seed);
  90
  91 /** Hash table parameters */
  92 struct rte_table_hash_params {
  93         /** Name */
  94         const char *name;
  95
  96         /** Key size (number of bytes) */
  97         uint32_t key_size;
  98
  99         /** Byte offset within packet meta-data where the key is located */
 100         uint32_t key_offset;
 101
 102         /** Key mask */
 103         uint8_t *key_mask;
 104
 105         /** Number of keys */
 106         uint32_t n_keys;
 107
 108         /** Number of buckets */
 109         uint32_t n_buckets;
 110
 111         /** Hash function */
 112         rte_table_hash_op_hash f_hash;
 113
 114         /** Seed value for the hash function */
 115         uint64_t seed;
 116 };
 117
 118 /** Extendible bucket hash table operations */
 119 extern struct rte_table_ops rte_table_hash_ext_ops;
 120 extern struct rte_table_ops rte_table_hash_key8_ext_ops;
 121 extern struct rte_table_ops rte_table_hash_key16_ext_ops;
 122 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
 123
 124 /** LRU hash table operations */
 125 extern struct rte_table_ops rte_table_hash_lru_ops;
 126
 127 extern struct rte_table_ops rte_table_hash_key8_lru_ops;
 128 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
 129 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
 130
 131 /** Cuckoo hash table operations */
 132 extern struct rte_table_ops rte_table_hash_cuckoo_ops;
 133
 134 #ifdef __cplusplus
 135 }
 136 #endif
 137
 138 #endif