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