lib/librte_lpm/rte_lpm.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2012 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
  35 #ifndef _RTE_LPM_H_
  36 #define _RTE_LPM_H_
  37
  38 /**
  39  * @file
  40  * RTE Longest Prefix Match (LPM)
  41  */
  42
  43 #include <errno.h>
  44 #include <sys/queue.h>
  45 #include <stdint.h>
  46 #include <stdlib.h>
  47 #include <rte_branch_prediction.h>
  48 #include <rte_memory.h>
  49
  50 #ifdef __cplusplus
  51 extern "C" {
  52 #endif
  53
  54 /** Max number of characters in LPM name. */
  55 #define RTE_LPM_NAMESIZE        32
  56
  57 /** Possible location to allocate memory. */
  58 #define RTE_LPM_HEAP    0
  59
  60 /** Possible location to allocate memory. */
  61 #define RTE_LPM_MEMZONE 1
  62
  63 /** Maximum depth value possible for IPv4 LPM. */
  64 #define RTE_LPM_MAX_DEPTH 32
  65
  66 /** Total number of tbl24 entries. */
  67 #define RTE_LPM_TBL24_NUM_ENTRIES (1 << 24)
  68
  69 /** Number of entries in a tbl8 group. */
  70 #define RTE_LPM_TBL8_GROUP_NUM_ENTRIES 256
  71
  72 /** Total number of tbl8 groups in the tbl8. */
  73 #define RTE_LPM_TBL8_NUM_GROUPS 256
  74
  75 /** Total number of tbl8 entries. */
  76 #define RTE_LPM_TBL8_NUM_ENTRIES (RTE_LPM_TBL8_NUM_GROUPS *                   \
  77                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES)
  78
  79 /** Macro to enable/disable run-time checks. */
  80 #if defined(RTE_LIBRTE_LPM_DEBUG)
  81 #define RTE_LPM_RETURN_IF_TRUE(cond, retval) do {                             \
  82         if (cond) return (retval);                                            \
  83 } while (0)
  84 #else
  85 #define RTE_LPM_RETURN_IF_TRUE(cond, retval)
  86 #endif
  87
  88 /** Tbl24 entry structure. */
  89 struct rte_lpm_tbl24_entry {
  90         /* Using single uint8_t to store 3 values. */
  91         uint8_t valid     :1; /**< Validation flag. */
  92         uint8_t ext_entry :1; /**< External entry. */
  93         uint8_t depth     :6; /**< Rule depth. */
  94         /* Stores Next hop or group index (i.e. gindex)into tbl8. */
  95         union {
  96                 uint8_t next_hop;
  97                 uint8_t tbl8_gindex;
  98         };
  99 };
 100
 101 /** Tbl8 entry structure. */
 102 struct rte_lpm_tbl8_entry {
 103         /* Using single uint8_t to store 3 values. */
 104         uint8_t valid       :1; /**< Validation flag. */
 105         uint8_t valid_group :1; /**< Group validation flag. */
 106         uint8_t depth       :6; /**< Rule depth. */
 107         uint8_t next_hop; /**< next hop. */
 108 };
 109
 110 /** Rule structure. */
 111 struct rte_lpm_rule {
 112         uint32_t ip; /**< Rule IP address. */
 113         uint8_t  next_hop; /**< Rule next hop. */
 114 };
 115
 116 /** LPM structure. */
 117 struct rte_lpm {
 118         TAILQ_ENTRY(rte_lpm) next;      /**< Next in list. */
 119
 120         /* LPM metadata. */
 121         char name[RTE_LPM_NAMESIZE];        /**< Name of the lpm. */
 122         int mem_location; /**< Location of memory to be allocated. */
 123         uint32_t max_rules_per_depth; /**< Max. balanced rules per lpm. */
 124         uint32_t used_rules_at_depth[RTE_LPM_MAX_DEPTH]; /**< Rules / depth. */
 125
 126         /* LPM Tables. */
 127         struct rte_lpm_tbl24_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES] \
 128                         __rte_cache_aligned; /**< LPM tbl24 table. */
 129         struct rte_lpm_tbl8_entry tbl8[RTE_LPM_TBL8_NUM_ENTRIES] \
 130                         __rte_cache_aligned; /**< LPM tbl8 table. */
 131         struct rte_lpm_rule rules_tbl[0] \
 132                         __rte_cache_aligned; /**< LPM rules. */
 133 };
 134
 135 /**
 136  * Create an LPM object.
 137  *
 138  * @param name
 139  *   LPM object name
 140  * @param socket_id
 141  *   NUMA socket ID for LPM table memory allocation
 142  * @param max_rules
 143  *   Maximum number of LPM rules that can be added
 144  * @param mem_location
 145  *   Location of memory to be allocated. Can only be RTE_LPM_HEAP or
 146  *   RTE_LPM_MEMZONE
 147  * @return
 148  *   Handle to LPM object on success, NULL otherwise with rte_errno set
 149  *   to an appropriate values. Possible rte_errno values include:
 150  *    - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure
 151  *    - E_RTE_SECONDARY - function was called from a secondary process instance
 152  *    - E_RTE_NO_TAILQ - no tailq list could be got for the lpm object list
 153  *    - EINVAL - invalid parameter passed to function
 154  *    - ENOSPC - the maximum number of memzones has already been allocated
 155  *    - EEXIST - a memzone with the same name already exists
 156  *    - ENOMEM - no appropriate memory area found in which to create memzone
 157  */
 158 struct rte_lpm *
 159 rte_lpm_create(const char *name, int socket_id, int max_rules,
 160                 int mem_location);
 161
 162 /**
 163  * Find an existing LPM object and return a pointer to it.
 164  *
 165  * @param name
 166  *   Name of the lpm object as passed to rte_lpm_create()
 167  * @return
 168  *   Pointer to lpm object or NULL if object not found with rte_errno
 169  *   set appropriately. Possible rte_errno values include:
 170  *    - ENOENT - required entry not available to return.
 171  */
 172 struct rte_lpm *
 173 rte_lpm_find_existing(const char *name);
 174
 175 /**
 176  * Free an LPM object.
 177  *
 178  * @param lpm
 179  *   LPM object handle
 180  * @return
 181  *   None
 182  */
 183 void
 184 rte_lpm_free(struct rte_lpm *lpm);
 185
 186 /**
 187  * Add a rule to the LPM table.
 188  *
 189  * @param lpm
 190  *   LPM object handle
 191  * @param ip
 192  *   IP of the rule to be added to the LPM table
 193  * @param depth
 194  *   Depth of the rule to be added to the LPM table
 195  * @param next_hop
 196  *   Next hop of the rule to be added to the LPM table
 197  * @return
 198  *   0 on success, negative value otherwise
 199  */
 200 int
 201 rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint8_t next_hop);
 202
 203 /**
 204  * Delete a rule from the LPM table.
 205  *
 206  * @param lpm
 207  *   LPM object handle
 208  * @param ip
 209  *   IP of the rule to be deleted from the LPM table
 210  * @param depth
 211  *   Depth of the rule to be deleted from the LPM table
 212  * @return
 213  *   0 on success, negative value otherwise
 214  */
 215 int
 216 rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);
 217
 218 /**
 219  * Delete all rules from the LPM table.
 220  *
 221  * @param lpm
 222  *   LPM object handle
 223  */
 224 void
 225 rte_lpm_delete_all(struct rte_lpm *lpm);
 226
 227 /**
 228  * Lookup an IP into the LPM table.
 229  *
 230  * @param lpm
 231  *   LPM object handle
 232  * @param ip
 233  *   IP to be looked up in the LPM table
 234  * @param next_hop
 235  *   Next hop of the most specific rule found for IP (valid on lookup hit only)
 236  * @return
 237  *   -EINVAL for incorrect arguments, -ENOENT on lookup miss, 0 on lookup hit
 238  */
 239 static inline int
 240 rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint8_t *next_hop)
 241 {
 242         uint32_t tbl24_index, tbl8_group_index, tbl8_index;
 243
 244         /* DEBUG: Check user input arguments. */
 245         RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (next_hop == NULL)), -EINVAL);
 246
 247         /* Calculate index into tbl24. */
 248         tbl24_index = (ip >> 8);
 249
 250         /*
 251          * Use the tbl24_index to access the required tbl24 entry then check if
 252          * the tbl24 entry is INVALID, if so return -ENOENT.
 253          */
 254         if (!lpm->tbl24[tbl24_index].valid){
 255                 return -ENOENT; /* Lookup miss. */
 256         }
 257         /*
 258          * If tbl24 entry is valid check if it is NOT extended (i.e. it does
 259          * not use a tbl8 extension) if so return the next hop.
 260          */
 261         if (likely(lpm->tbl24[tbl24_index].ext_entry == 0)) {
 262                 *next_hop = lpm->tbl24[tbl24_index].next_hop;
 263                 return 0; /* Lookup hit. */
 264         }
 265
 266         /*
 267          * If tbl24 entry is valid and extended calculate the index into the
 268          * tbl8 entry.
 269          */
 270         tbl8_group_index = lpm->tbl24[tbl24_index].tbl8_gindex;
 271         tbl8_index = (tbl8_group_index * RTE_LPM_TBL8_GROUP_NUM_ENTRIES) +
 272                         (ip & 0xFF);
 273
 274         /* Check if the tbl8 entry is invalid and if so return -ENOENT. */
 275         if (!lpm->tbl8[tbl8_index].valid)
 276                 return -ENOENT;/* Lookup miss. */
 277
 278         /* If the tbl8 entry is valid return return the next_hop. */
 279         *next_hop = lpm->tbl8[tbl8_index].next_hop;
 280         return 0; /* Lookup hit. */
 281 }
 282
 283 #ifdef __cplusplus
 284 }
 285 #endif
 286
 287 #endif /* _RTE_LPM_H_ */