lib/librte_efd/rte_efd.h

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