lib/librte_efd/rte_efd.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2016-2017 Intel Corporation
   3  */
   4
   5 #ifndef _RTE_EFD_H_
   6 #define _RTE_EFD_H_
   7
   8 /**
   9  * @file
  10  *
  11  * RTE EFD Table
  12  */
  13
  14 #include <stdint.h>
  15
  16 #ifdef __cplusplus
  17 extern "C" {
  18 #endif
  19
  20 /*************************************************************************
  21  * User selectable constants
  22  *************************************************************************/
  23
  24 /*
  25  * If possible, best lookup performance will be achieved by ensuring that
  26  * the entire table fits in the L3 cache.
  27  *
  28  * Some formulas for calculating various sizes are listed below:
  29  *
  30  * # of chunks =
  31  *   2 ^ (ceiling(log2((requested # of rules) /
  32  *            (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES))))
  33  *
  34  * Target # of rules = (# of chunks) * EFD_CHUNK_NUM_GROUPS *
  35  *            EFD_TARGET_GROUP_NUM_RULES
  36  *
  37  * Group Size (in bytes) = 4 (per value bit)
  38  *
  39  * Table size (in bytes) = RTE_EFD_VALUE_NUM_BITS * (# of chunks) *
  40  *            EFD_CHUNK_NUM_GROUPS * (group size)
  41  */
  42
  43 /**
  44  * !!! This parameter should be adjusted for your application !!!
  45  *
  46  * This parameter adjusts the number of bits of value that can be
  47  * stored in the table.
  48  * For example, setting the number of bits to 3 will allow storing 8 values
  49  * in the table (between 0 and 7).
  50  *
  51  * This number directly affects the performance of both lookups and insertion.
  52  * In general, performance decreases as more bits are stored in the table.
  53  *
  54  * This number is directly proportional to the size of the online region
  55  * used for lookups.
  56  *
  57  * Note that due to the way the CPU operates on memory, best lookup performance
  58  * will be achieved when RTE_EFD_VALUE_NUM_BITS is a multiple of 8.
  59  * These values align the hash indexes on 16-byte boundaries.
  60  * The greatest performance drop is moving from 8->9 bits, 16->17 bits, etc.
  61  *
  62  * This value must be between 1 and 32
  63  */
  64 #ifndef RTE_EFD_VALUE_NUM_BITS
  65 #define RTE_EFD_VALUE_NUM_BITS (8)
  66 #endif
  67
  68 /*
  69  * EFD_TARGET_GROUP_NUM_RULES:
  70  *   Adjusts how many groups/chunks are allocated at table creation time
  71  *   to support the requested number of rules. Higher values pack entries
  72  *   more tightly in memory, resulting in a smaller memory footprint
  73  *   for the online table.
  74  *   This comes at the cost of lower insert/update performance.
  75  *
  76  * EFD_MAX_GROUP_NUM_RULES:
  77  *   This adjusts the amount of offline memory allocated to store key/value
  78  *   pairs for the table. The recommended numbers are upper-bounds for
  79  *   this parameter
  80  *   - any higher and it becomes very unlikely that a perfect hash function
  81  *   can be found for that group size. This value should be at
  82  *   least 40% larger than EFD_TARGET_GROUP_NUM_RULES
  83  *
  84  * Recommended values for various lookuptable and hashfunc sizes are:
  85  *
  86  *   HASH_FUNC_SIZE = 16, LOOKUPTBL_SIZE = 16:
  87  *     EFD_TARGET_GROUP_NUM_RULES = 22
  88  *     EFD_MAX_GROUP_NUM_RULES = 28
  89  */
  90 #define EFD_TARGET_GROUP_NUM_RULES (22)
  91 #define EFD_MAX_GROUP_NUM_RULES (28LU)
  92
  93 #define EFD_MIN_BALANCED_NUM_RULES      5
  94
  95 /**
  96  * Maximum number of keys that can be looked up in one call to efd_lookup_bulk
  97  */
  98 #ifndef RTE_EFD_BURST_MAX
  99 #define RTE_EFD_BURST_MAX (32)
 100 #endif
 101
 102 /** Maximum number of characters in efd name.*/
 103 #define RTE_EFD_NAMESIZE                        32
 104
 105 #if (RTE_EFD_VALUE_NUM_BITS > 0 && RTE_EFD_VALUE_NUM_BITS <= 8)
 106 typedef uint8_t efd_value_t;
 107 #elif (RTE_EFD_VALUE_NUM_BITS > 8 && RTE_EFD_VALUE_NUM_BITS <= 16)
 108 typedef uint16_t efd_value_t;
 109 #elif (RTE_EFD_VALUE_NUM_BITS > 16 && RTE_EFD_VALUE_NUM_BITS <= 32)
 110 typedef uint32_t efd_value_t;
 111 #else
 112 #error("RTE_EFD_VALUE_NUM_BITS must be in the range [1:32]")
 113 #endif
 114
 115 #define EFD_LOOKUPTBL_SHIFT (32 - 4)
 116 typedef uint16_t efd_lookuptbl_t;
 117 typedef uint16_t efd_hashfunc_t;
 118
 119 /**
 120  * Creates an EFD table with a single offline region and multiple per-socket
 121  * internally-managed copies of the online table used for lookups
 122  *
 123  * @param name
 124  *   EFD table name
 125  * @param max_num_rules
 126  *   Minimum number of rules the table should be sized to hold.
 127  *   Will be rounded up to the next smallest valid table size
 128  * @param key_len
 129  *   Length of the key
 130  * @param online_cpu_socket_bitmask
 131  *   Bitmask specifying which sockets should get a copy of the online table.
 132  *   LSB = socket 0, etc.
 133  * @param offline_cpu_socket
 134  *   Identifies the socket where the offline table will be allocated
 135  *   (and most efficiently accessed in the case of updates/insertions)
 136  *
 137  * @return
 138  *   EFD table, or NULL if table allocation failed or the bitmask is invalid
 139  */
 140 struct rte_efd_table *
 141 rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
 142         uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket);
 143
 144 /**
 145  * Releases the resources from an EFD table
 146  *
 147  * @param table
 148  *   Table to free
 149  */
 150 void
 151 rte_efd_free(struct rte_efd_table *table);
 152
 153 /**
 154  * Find an existing EFD table object and return a pointer to it.
 155  *
 156  * @param name
 157  *   Name of the EFD table as passed to rte_efd_create()
 158  * @return
 159  *   Pointer to EFD table or NULL if object not found
 160  *   with rte_errno set appropriately. Possible rte_errno values include:
 161  *    - ENOENT - value not available for return
 162  */
 163 struct rte_efd_table*
 164 rte_efd_find_existing(const char *name);
 165
 166 #define RTE_EFD_UPDATE_WARN_GROUP_FULL   (1)
 167 #define RTE_EFD_UPDATE_NO_CHANGE         (2)
 168 #define RTE_EFD_UPDATE_FAILED            (3)
 169
 170 /**
 171  * Computes an updated table entry for the supplied key/value pair.
 172  * The update is then immediately applied to the provided table and
 173  * all socket-local copies of the chunks are updated.
 174  * This operation is not multi-thread safe
 175  * and should only be called one from thread.
 176  *
 177  * @param table
 178  *   EFD table to reference
 179  * @param socket_id
 180  *   Socket ID to use to lookup existing value (ideally caller's socket id)
 181  * @param key
 182  *   EFD table key to modify
 183  * @param value
 184  *   Value to associate with the key
 185  *
 186  * @return
 187  *  RTE_EFD_UPDATE_WARN_GROUP_FULL
 188  *     Operation is insert, and the last available space in the
 189  *     key's group was just used
 190  *     Future inserts may fail as groups fill up
 191  *     This operation was still successful, and entry contains a valid update
 192  *  RTE_EFD_UPDATE_FAILED
 193  *     Either the EFD failed to find a suitable perfect hash or the group was full
 194  *     This is a fatal error, and the table is now in an indeterminate state
 195  *  RTE_EFD_UPDATE_NO_CHANGE
 196  *     Operation resulted in no change to the table (same value already exists)
 197  *  0 - success
 198  */
 199 int
 200 rte_efd_update(struct rte_efd_table *table, unsigned int socket_id,
 201         const void *key, efd_value_t value);
 202
 203 /**
 204  * Removes any value currently associated with the specified key from the table
 205  * This operation is not multi-thread safe
 206  * and should only be called from one thread.
 207  *
 208  * @param table
 209  *   EFD table to reference
 210  * @param socket_id
 211  *   Socket ID to use to lookup existing value (ideally caller's socket id)
 212  * @param key
 213  *   EFD table key to delete
 214  * @param prev_value
 215  *   If not NULL, will store the previous value here before deleting it
 216  *
 217  * @return
 218  *   0 - successfully found and deleted the key
 219  *   nonzero otherwise
 220  */
 221 int
 222 rte_efd_delete(struct rte_efd_table *table, unsigned int socket_id,
 223         const void *key, efd_value_t *prev_value);
 224
 225 /**
 226  * Looks up the value associated with a key
 227  * This operation is multi-thread safe.
 228  *
 229  * NOTE: Lookups will *always* succeed - this is a property of
 230  * using a perfect hash table.
 231  * If the specified key was never inserted, a pseudorandom answer will be returned.
 232  * There is no way to know based on the lookup if the key was ever inserted
 233  * originally, so this must be tracked elsewhere.
 234  *
 235  * @param table
 236  *   EFD table to reference
 237  * @param socket_id
 238  *   Socket ID to use to lookup existing value (ideally caller's socket id)
 239  * @param key
 240  *   EFD table key to look up
 241  *
 242  * @return
 243  *   Value associated with the key, or random junk if they key was never inserted
 244  */
 245 efd_value_t
 246 rte_efd_lookup(const struct rte_efd_table *table, unsigned int socket_id,
 247                 const void *key);
 248
 249 /**
 250  * Looks up the value associated with several keys.
 251  * This operation is multi-thread safe.
 252  *
 253  * NOTE: Lookups will *always* succeed - this is a property of
 254  * using a perfect hash table.
 255  * If the specified key was never inserted, a pseudorandom answer will be returned.
 256  * There is no way to know based on the lookup if the key was ever inserted
 257  * originally, so this must be tracked elsewhere.
 258  *
 259  * @param table
 260  *   EFD table to reference
 261  * @param socket_id
 262  *   Socket ID to use to lookup existing value (ideally caller's socket id)
 263  * @param num_keys
 264  *   Number of keys in the key_list array, must be less than RTE_EFD_BURST_MAX
 265  * @param key_list
 266  *   Array of num_keys pointers which point to keys to look up
 267  * @param value_list
 268  *   Array of size num_keys where lookup values will be stored
 269  */
 270 void
 271 rte_efd_lookup_bulk(const struct rte_efd_table *table, unsigned int socket_id,
 272                 int num_keys, const void **key_list,
 273                 efd_value_t *value_list);
 274
 275 #ifdef __cplusplus
 276 }
 277 #endif
 278
 279 #endif /* _RTE_EFD_H_ */