lib/librte_table/rte_table_hash.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2017 Intel Corporation
   3  */
   4
   5 #ifndef __INCLUDE_RTE_TABLE_HASH_H__
   6 #define __INCLUDE_RTE_TABLE_HASH_H__
   7
   8 #ifdef __cplusplus
   9 extern "C" {
  10 #endif
  11
  12 /**
  13  * @file
  14  * RTE Table Hash
  15  *
  16  * These tables use the exact match criterion to uniquely associate data to
  17  * lookup keys.
  18  *
  19  * Hash table types:
  20  * 1. Entry add strategy on bucket full:
  21  *     a. Least Recently Used (LRU): One of the existing keys in the bucket is
  22  *        deleted and the new key is added in its place. The number of keys in
  23  *        each bucket never grows bigger than 4. The logic to pick the key to
  24  *        be dropped from the bucket is LRU. The hash table lookup operation
  25  *        maintains the order in which the keys in the same bucket are hit, so
  26  *        every time a key is hit, it becomes the new Most Recently Used (MRU)
  27  *        key, i.e. the most unlikely candidate for drop. When a key is added
  28  *        to the bucket, it also becomes the new MRU key. When a key needs to
  29  *        be picked and dropped, the most likely candidate for drop, i.e. the
  30  *        current LRU key, is always picked. The LRU logic requires maintaining
  31  *        specific data structures per each bucket. Use-cases: flow cache, etc.
  32  *     b. Extendible bucket (ext): The bucket is extended with space for 4 more
  33  *        keys. This is done by allocating additional memory at table init time,
  34  *        which is used to create a pool of free keys (the size of this pool is
  35  *        configurable and always a multiple of 4). On key add operation, the
  36  *        allocation of a group of 4 keys only happens successfully within the
  37  *        limit of free keys, otherwise the key add operation fails. On key
  38  *        delete operation, a group of 4 keys is freed back to the pool of free
  39  *        keys when the key to be deleted is the only key that was used within
  40  *        its group of 4 keys at that time. On key lookup operation, if the
  41  *        current bucket is in extended state and a match is not found in the
  42  *        first group of 4 keys, the search continues beyond the first group of
  43  *        4 keys, potentially until all keys in this bucket are examined. The
  44  *        extendible bucket logic requires maintaining specific data structures
  45  *        per table and per each bucket. Use-cases: flow table, etc.
  46  * 2. Key size:
  47  *     a. Configurable key size
  48  *     b. Single key size (8-byte, 16-byte or 32-byte key size)
  49  *
  50  ***/
  51 #include <stdint.h>
  52
  53 #include "rte_table.h"
  54
  55 /** Hash function */
  56 typedef uint64_t (*rte_table_hash_op_hash)(
  57         void *key,
  58         void *key_mask,
  59         uint32_t key_size,
  60         uint64_t seed);
  61
  62 /** Hash table parameters */
  63 struct rte_table_hash_params {
  64         /** Name */
  65         const char *name;
  66
  67         /** Key size (number of bytes) */
  68         uint32_t key_size;
  69
  70         /** Byte offset within packet meta-data where the key is located */
  71         uint32_t key_offset;
  72
  73         /** Key mask */
  74         uint8_t *key_mask;
  75
  76         /** Number of keys */
  77         uint32_t n_keys;
  78
  79         /** Number of buckets */
  80         uint32_t n_buckets;
  81
  82         /** Hash function */
  83         rte_table_hash_op_hash f_hash;
  84
  85         /** Seed value for the hash function */
  86         uint64_t seed;
  87 };
  88
  89 /** Extendible bucket hash table operations */
  90 extern struct rte_table_ops rte_table_hash_ext_ops;
  91 extern struct rte_table_ops rte_table_hash_key8_ext_ops;
  92 extern struct rte_table_ops rte_table_hash_key16_ext_ops;
  93 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
  94
  95 /** LRU hash table operations */
  96 extern struct rte_table_ops rte_table_hash_lru_ops;
  97
  98 extern struct rte_table_ops rte_table_hash_key8_lru_ops;
  99 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
 100 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
 101
 102 #ifdef __cplusplus
 103 }
 104 #endif
 105
 106 #endif