X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_lpm%2Frte_lpm.h;h=2dc354ca0d7f1ea3e78299600aaea91ef9dfd16d;hb=1c1d4d7a923d4804f1926fc5264f9ecdd8977b04;hp=56eff4e338e5f60fa0b85e7e340036835fd8e63d;hpb=4cdf471a06e322fc6abf13c18c2028d48bc63ac1;p=dpdk.git diff --git a/lib/librte_lpm/rte_lpm.h b/lib/librte_lpm/rte_lpm.h index 56eff4e338..2dc354ca0d 100644 --- a/lib/librte_lpm/rte_lpm.h +++ b/lib/librte_lpm/rte_lpm.h @@ -1,35 +1,34 @@ /*- * BSD LICENSE * - * Copyright(c) 2010-2012 Intel Corporation. All rights reserved. + * Copyright(c) 2010-2013 Intel Corporation. All rights reserved. * All rights reserved. * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions * are met: * - * * Redistributions of source code must retain the above copyright + * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the * distribution. - * * Neither the name of Intel Corporation nor the names of its - * contributors may be used to endorse or promote products derived + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * */ #ifndef _RTE_LPM_H_ @@ -97,24 +96,24 @@ extern "C" { /** @internal Tbl24 entry structure. */ struct rte_lpm_tbl24_entry { - /* Using single uint8_t to store 3 values. */ - uint8_t valid :1; /**< Validation flag. */ - uint8_t ext_entry :1; /**< External entry. */ - uint8_t depth :6; /**< Rule depth. */ /* Stores Next hop or group index (i.e. gindex)into tbl8. */ union { uint8_t next_hop; uint8_t tbl8_gindex; }; + /* Using single uint8_t to store 3 values. */ + uint8_t valid :1; /**< Validation flag. */ + uint8_t ext_entry :1; /**< External entry. */ + uint8_t depth :6; /**< Rule depth. */ }; /** @internal Tbl8 entry structure. */ struct rte_lpm_tbl8_entry { + uint8_t next_hop; /**< next hop. */ /* Using single uint8_t to store 3 values. */ uint8_t valid :1; /**< Validation flag. */ uint8_t valid_group :1; /**< Group validation flag. */ uint8_t depth :6; /**< Rule depth. */ - uint8_t next_hop; /**< next hop. */ }; /** @internal Rule structure. */ @@ -247,45 +246,83 @@ rte_lpm_delete_all(struct rte_lpm *lpm); static inline int rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint8_t *next_hop) { - uint32_t tbl24_index, tbl8_group_index, tbl8_index; + unsigned tbl24_index = (ip >> 8); + uint16_t tbl_entry; /* DEBUG: Check user input arguments. */ RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (next_hop == NULL)), -EINVAL); - /* Calculate index into tbl24. */ - tbl24_index = (ip >> 8); + /* Copy tbl24 entry */ + tbl_entry = *(const uint16_t *)&lpm->tbl24[tbl24_index]; + + /* Copy tbl8 entry (only if needed) */ + if (unlikely((tbl_entry & RTE_LPM_VALID_EXT_ENTRY_BITMASK) == + RTE_LPM_VALID_EXT_ENTRY_BITMASK)) { - /* - * Use the tbl24_index to access the required tbl24 entry then check if - * the tbl24 entry is INVALID, if so return -ENOENT. - */ - if (!lpm->tbl24[tbl24_index].valid){ - return -ENOENT; /* Lookup miss. */ + unsigned tbl8_index = (uint8_t)ip + + ((uint8_t)tbl_entry * RTE_LPM_TBL8_GROUP_NUM_ENTRIES); + + tbl_entry = *(const uint16_t *)&lpm->tbl8[tbl8_index]; } - /* - * If tbl24 entry is valid check if it is NOT extended (i.e. it does - * not use a tbl8 extension) if so return the next hop. - */ - if (likely(lpm->tbl24[tbl24_index].ext_entry == 0)) { - *next_hop = lpm->tbl24[tbl24_index].next_hop; - return 0; /* Lookup hit. */ + + *next_hop = (uint8_t)tbl_entry; + return (tbl_entry & RTE_LPM_LOOKUP_SUCCESS) ? 0 : -ENOENT; +} + +/** + * Lookup multiple IP addresses in an LPM table. This may be implemented as a + * macro, so the address of the function should not be used. + * + * @param lpm + * LPM object handle + * @param ips + * Array of IPs to be looked up in the LPM table + * @param next_hops + * Next hop of the most specific rule found for IP (valid on lookup hit only). + * This is an array of two byte values. The most significant byte in each + * value says whether the lookup was successful (bitmask + * RTE_LPM_LOOKUP_SUCCESS is set). The least significant byte is the + * actual next hop. + * @param n + * Number of elements in ips (and next_hops) array to lookup. This should be a + * compile time constant, and divisible by 8 for best performance. + * @return + * -EINVAL for incorrect arguments, otherwise 0 + */ +#define rte_lpm_lookup_bulk(lpm, ips, next_hops, n) \ + rte_lpm_lookup_bulk_func(lpm, ips, next_hops, n) + +static inline int +rte_lpm_lookup_bulk_func(const struct rte_lpm *lpm, const uint32_t * ips, + uint16_t * next_hops, const unsigned n) +{ + unsigned i; + unsigned tbl24_indexes[n]; + + /* DEBUG: Check user input arguments. */ + RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (ips == NULL) || + (next_hops == NULL)), -EINVAL); + + for (i = 0; i < n; i++) { + tbl24_indexes[i] = ips[i] >> 8; } - /* - * If tbl24 entry is valid and extended calculate the index into the - * tbl8 entry. - */ - tbl8_group_index = lpm->tbl24[tbl24_index].tbl8_gindex; - tbl8_index = (tbl8_group_index * RTE_LPM_TBL8_GROUP_NUM_ENTRIES) + - (ip & 0xFF); - - /* Check if the tbl8 entry is invalid and if so return -ENOENT. */ - if (!lpm->tbl8[tbl8_index].valid) - return -ENOENT;/* Lookup miss. */ - - /* If the tbl8 entry is valid return return the next_hop. */ - *next_hop = lpm->tbl8[tbl8_index].next_hop; - return 0; /* Lookup hit. */ + for (i = 0; i < n; i++) { + /* Simply copy tbl24 entry to output */ + next_hops[i] = *(const uint16_t *)&lpm->tbl24[tbl24_indexes[i]]; + + /* Overwrite output with tbl8 entry if needed */ + if (unlikely((next_hops[i] & RTE_LPM_VALID_EXT_ENTRY_BITMASK) == + RTE_LPM_VALID_EXT_ENTRY_BITMASK)) { + + unsigned tbl8_index = (uint8_t)ips[i] + + ((uint8_t)next_hops[i] * + RTE_LPM_TBL8_GROUP_NUM_ENTRIES); + + next_hops[i] = *(const uint16_t *)&lpm->tbl8[tbl8_index]; + } + } + return 0; } #ifdef __cplusplus