Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/44827/?format=api
{ "id": 44827, "url": "http://patchwork.dpdk.org/api/patches/44827/?format=api", "web_url": "http://patchwork.dpdk.org/project/dpdk/patch/20180918105723.6ACC95F0F@dpdk.org/", "project": { "id": 1, "url": "http://patchwork.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<20180918105723.6ACC95F0F@dpdk.org>", "list_archive_url": "https://inbox.dpdk.org/dev/20180918105723.6ACC95F0F@dpdk.org", "date": "2018-09-18T10:57:17", "name": "[v7,2/2] librte_lpm: Improve performance of the delete and add functions", "commit_ref": null, "pull_url": null, "state": "accepted", "archived": true, "hash": "88d50abc4d26a93642dfad504a4ef808e14cf032", "submitter": { "id": 1036, "url": "http://patchwork.dpdk.org/api/people/1036/?format=api", "name": "Alex Kiselev", "email": "alex@therouter.net" }, "delegate": { "id": 1, "url": "http://patchwork.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patchwork.dpdk.org/project/dpdk/patch/20180918105723.6ACC95F0F@dpdk.org/mbox/", "series": [ { "id": 1367, "url": "http://patchwork.dpdk.org/api/series/1367/?format=api", "web_url": "http://patchwork.dpdk.org/project/dpdk/list/?series=1367", "date": "2018-09-18T10:57:09", "name": "[v7,1/2] librte_lpm: Improve performance of the delete and add functions", "version": 7, "mbox": "http://patchwork.dpdk.org/series/1367/mbox/" } ], "comments": "http://patchwork.dpdk.org/api/patches/44827/comments/", "check": "success", "checks": "http://patchwork.dpdk.org/api/patches/44827/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id 6ACC95F0F;\n\tTue, 18 Sep 2018 12:57:23 +0200 (CEST)", "from relay-out1.mail.masterhost.ru (relay-out1.mail.masterhost.ru\n\t[83.222.12.11]) by dpdk.org (Postfix) with ESMTP id 129285B3E\n\tfor <dev@dpdk.org>; Tue, 18 Sep 2018 12:57:22 +0200 (CEST)", "from [37.139.80.50] (helo=h5.therouter.net)\n\tby relay1.mail.masterhost.ru with esmtpa \n\tenvelope from <alex@therouter.net>\n\tauthenticated with alex@therouter.net\n\tmessage id 1g2Dgz-0003KQ-Qj; Tue, 18 Sep 2018 13:57:19 +0300", "by h5.therouter.net (sSMTP sendmail emulation);\n\tTue, 18 Sep 2018 13:57:17 +0300" ], "Date": "Tue, 18 Sep 2018 13:57:17 +0300", "To": "\"dev@dpdk.org\" <dev@dpdk.org>,\n\tBruce Richardson <bruce.richardson@intel.com>,\n\tStephen Hemminger <stephen@networkplumber.org>", "From": "Alex Kiselev <alex@therouter.net>", "X-KLMS-Rule-ID": "1", "X-KLMS-Message-Action": "clean", "X-KLMS-AntiSpam-Lua-Profiles": "128975 [Sep 18 2018]", "X-KLMS-AntiSpam-Version": "5.8.3.0", "X-KLMS-AntiSpam-Envelope-From": "alex@therouter.net", "X-KLMS-AntiSpam-Rate": "0", "X-KLMS-AntiSpam-Status": "not_detected", "X-KLMS-AntiSpam-Method": "none", "X-KLMS-AntiSpam-Info": "LuaCore: 199 199\n\tc524e2367ecb0510dd40ed0f0677dbf1650d9f24, {rep_avail},\n\t{msgid_missed_heavy}, DmarcAF: none", "X-MS-Exchange-Organization-SCL": "-1", "X-KLMS-AntiSpam-Interceptor-Info": "scan successful", "X-KLMS-AntiPhishing": "not scanned, disabled by settings", "X-KLMS-AntiVirus": "Kaspersky Security for Linux Mail Server, version 8.0.2.16,\n\tnot scanned, license restriction", "Subject": "[dpdk-dev] [PATCH v7 2/2] librte_lpm: Improve performance of the\n\tdelete and add functions", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>", "Message-Id": "<20180918105723.6ACC95F0F@dpdk.org>" }, "content": "lpm6: add incremental update on delete\n\nrework the delete function and add additional \ninternal data structures to support incremental \nLPM tree update rather than full tree rebuild\n\nSigned-off-by: Alex Kiselev <alex@therouter.net>\nAcked-by: Bruce Richardson <bruce.richardson@intel.com>\n---\n lib/librte_lpm/rte_lpm6.c | 712 ++++++++++++++++++++++++++++++++++++++--------\n 1 file changed, 597 insertions(+), 115 deletions(-)", "diff": "diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c\nindex d86e878bc..6f1f94e23 100644\n--- a/lib/librte_lpm/rte_lpm6.c\n+++ b/lib/librte_lpm/rte_lpm6.c\n@@ -41,6 +41,7 @@\n #define BYTES2_SIZE 16\n \n #define RULE_HASH_TABLE_EXTRA_SPACE 64\n+#define TBL24_IND UINT32_MAX\n \n #define lpm6_tbl8_gindex next_hop\n \n@@ -81,6 +82,17 @@ struct rte_lpm6_rule_key {\n \tuint8_t depth; /**< Rule depth. */\n };\n \n+/* Header of tbl8 */\n+struct rte_lpm_tbl8_hdr {\n+\tuint32_t owner_tbl_ind; /**< owner table: TBL24_IND if owner is tbl24,\n+\t\t\t\t\t* otherwise index of tbl8\n+\t\t\t\t\t*/\n+\tuint32_t owner_entry_ind; /**< index of the owner table entry where\n+\t\t\t\t\t* pointer to the tbl8 is stored\n+\t\t\t\t\t*/\n+\tuint32_t ref_cnt; /**< table reference counter */\n+};\n+\n /** LPM6 structure. */\n struct rte_lpm6 {\n \t/* LPM metadata. */\n@@ -88,12 +100,17 @@ struct rte_lpm6 {\n \tuint32_t max_rules; /**< Max number of rules. */\n \tuint32_t used_rules; /**< Used rules so far. */\n \tuint32_t number_tbl8s; /**< Number of tbl8s to allocate. */\n-\tuint32_t next_tbl8; /**< Next tbl8 to be used. */\n \n \t/* LPM Tables. */\n \tstruct rte_hash *rules_tbl; /**< LPM rules. */\n \tstruct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]\n \t\t\t__rte_cache_aligned; /**< LPM tbl24 table. */\n+\n+\tuint32_t *tbl8_pool; /**< pool of indexes of free tbl8s */\n+\tuint32_t tbl8_pool_pos; /**< current position in the tbl8 pool */\n+\n+\tstruct rte_lpm_tbl8_hdr *tbl8_hdrs; /* array of tbl8 headers */\n+\n \tstruct rte_lpm6_tbl_entry tbl8[0]\n \t\t\t__rte_cache_aligned; /**< LPM tbl8 table. */\n };\n@@ -142,6 +159,59 @@ rule_hash(const void *data, __rte_unused uint32_t data_len,\n \treturn rte_jhash(data, sizeof(struct rte_lpm6_rule_key), init_val);\n }\n \n+/*\n+ * Init pool of free tbl8 indexes\n+ */\n+static void\n+tbl8_pool_init(struct rte_lpm6 *lpm)\n+{\n+\tuint32_t i;\n+\n+\t/* put entire range of indexes to the tbl8 pool */\n+\tfor (i = 0; i < lpm->number_tbl8s; i++)\n+\t\tlpm->tbl8_pool[i] = i;\n+\n+\tlpm->tbl8_pool_pos = 0;\n+}\n+\n+/*\n+ * Get an index of a free tbl8 from the pool\n+ */\n+static inline uint32_t\n+tbl8_get(struct rte_lpm6 *lpm, uint32_t *tbl8_ind)\n+{\n+\tif (lpm->tbl8_pool_pos == lpm->number_tbl8s)\n+\t\t/* no more free tbl8 */\n+\t\treturn -ENOSPC;\n+\n+\t/* next index */\n+\t*tbl8_ind = lpm->tbl8_pool[lpm->tbl8_pool_pos++];\n+\treturn 0;\n+}\n+\n+/*\n+ * Put an index of a free tbl8 back to the pool\n+ */\n+static inline uint32_t\n+tbl8_put(struct rte_lpm6 *lpm, uint32_t tbl8_ind)\n+{\n+\tif (lpm->tbl8_pool_pos == 0)\n+\t\t/* pool is full */\n+\t\treturn -ENOSPC;\n+\n+\tlpm->tbl8_pool[--lpm->tbl8_pool_pos] = tbl8_ind;\n+\treturn 0;\n+}\n+\n+/*\n+ * Returns number of tbl8s available in the pool\n+ */\n+static inline uint32_t\n+tbl8_available(struct rte_lpm6 *lpm)\n+{\n+\treturn lpm->number_tbl8s - lpm->tbl8_pool_pos;\n+}\n+\n /*\n * Init a rule key.\n *\t note that ip must be already masked\n@@ -182,6 +252,8 @@ rte_lpm6_create(const char *name, int socket_id,\n \tuint64_t mem_size;\n \tstruct rte_lpm6_list *lpm_list;\n \tstruct rte_hash *rules_tbl = NULL;\n+\tuint32_t *tbl8_pool = NULL;\n+\tstruct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL;\n \n \tlpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);\n \n@@ -216,6 +288,28 @@ rte_lpm6_create(const char *name, int socket_id,\n \t\tgoto fail_wo_unlock;\n \t}\n \n+\t/* allocate tbl8 indexes pool */\n+\ttbl8_pool = rte_malloc(NULL,\n+\t\t\tsizeof(uint32_t) * config->number_tbl8s,\n+\t\t\tRTE_CACHE_LINE_SIZE);\n+\tif (tbl8_pool == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"LPM tbl8 pool allocation failed: %s (%d)\",\n+\t\t\t\t rte_strerror(rte_errno), rte_errno);\n+\t\trte_errno = ENOMEM;\n+\t\tgoto fail_wo_unlock;\n+\t}\n+\n+\t/* allocate tbl8 headers */\n+\ttbl8_hdrs = rte_malloc(NULL,\n+\t\t\tsizeof(struct rte_lpm_tbl8_hdr) * config->number_tbl8s,\n+\t\t\tRTE_CACHE_LINE_SIZE);\n+\tif (tbl8_hdrs == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"LPM tbl8 headers allocation failed: %s (%d)\",\n+\t\t\t\t rte_strerror(rte_errno), rte_errno);\n+\t\trte_errno = ENOMEM;\n+\t\tgoto fail_wo_unlock;\n+\t}\n+\n \tsnprintf(mem_name, sizeof(mem_name), \"LPM_%s\", name);\n \n \t/* Determine the amount of memory to allocate. */\n@@ -260,6 +354,11 @@ rte_lpm6_create(const char *name, int socket_id,\n \tlpm->number_tbl8s = config->number_tbl8s;\n \tsnprintf(lpm->name, sizeof(lpm->name), \"%s\", name);\n \tlpm->rules_tbl = rules_tbl;\n+\tlpm->tbl8_pool = tbl8_pool;\n+\tlpm->tbl8_hdrs = tbl8_hdrs;\n+\n+\t/* init the stack */\n+\ttbl8_pool_init(lpm);\n \n \tte->data = (void *) lpm;\n \n@@ -271,6 +370,8 @@ rte_lpm6_create(const char *name, int socket_id,\n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n \n fail_wo_unlock:\n+\trte_free(tbl8_hdrs);\n+\trte_free(tbl8_pool);\n \trte_hash_free(rules_tbl);\n \n \treturn NULL;\n@@ -332,6 +433,8 @@ rte_lpm6_free(struct rte_lpm6 *lpm)\n \n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n \n+\trte_free(lpm->tbl8_hdrs);\n+\trte_free(lpm->tbl8_pool);\n \trte_hash_free(lpm->rules_tbl);\n \trte_free(lpm);\n \trte_free(te);\n@@ -420,24 +523,24 @@ rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)\n * in the IP address returns a match.\n */\n static void\n-expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,\n-\t\tuint32_t next_hop)\n+expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t old_depth,\n+\t\tuint8_t new_depth, uint32_t next_hop, uint8_t valid)\n {\n \tuint32_t tbl8_group_end, tbl8_gindex_next, j;\n \n \ttbl8_group_end = tbl8_gindex + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;\n \n \tstruct rte_lpm6_tbl_entry new_tbl8_entry = {\n-\t\t.valid = VALID,\n-\t\t.valid_group = VALID,\n-\t\t.depth = depth,\n+\t\t.valid = valid,\n+\t\t.valid_group = valid,\n+\t\t.depth = new_depth,\n \t\t.next_hop = next_hop,\n \t\t.ext_entry = 0,\n \t};\n \n \tfor (j = tbl8_gindex; j < tbl8_group_end; j++) {\n \t\tif (!lpm->tbl8[j].valid || (lpm->tbl8[j].ext_entry == 0\n-\t\t\t\t&& lpm->tbl8[j].depth <= depth)) {\n+\t\t\t\t&& lpm->tbl8[j].depth <= old_depth)) {\n \n \t\t\tlpm->tbl8[j] = new_tbl8_entry;\n \n@@ -445,11 +548,101 @@ expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,\n \n \t\t\ttbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex\n \t\t\t\t\t* RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;\n-\t\t\texpand_rule(lpm, tbl8_gindex_next, depth, next_hop);\n+\t\t\texpand_rule(lpm, tbl8_gindex_next, old_depth, new_depth,\n+\t\t\t\t\tnext_hop, valid);\n \t\t}\n \t}\n }\n \n+/*\n+ * Init a tbl8 header\n+ */\n+static inline void\n+init_tbl8_header(struct rte_lpm6 *lpm, uint32_t tbl_ind,\n+\t\tuint32_t owner_tbl_ind, uint32_t owner_entry_ind)\n+{\n+\tstruct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind];\n+\ttbl_hdr->owner_tbl_ind = owner_tbl_ind;\n+\ttbl_hdr->owner_entry_ind = owner_entry_ind;\n+\ttbl_hdr->ref_cnt = 0;\n+}\n+\n+/*\n+ * Calculate index to the table based on the number and position\n+ * of the bytes being inspected in this step.\n+ */\n+static uint32_t\n+get_bitshift(const uint8_t *ip, uint8_t first_byte, uint8_t bytes)\n+{\n+\tuint32_t entry_ind, i;\n+\tint8_t bitshift;\n+\n+\tentry_ind = 0;\n+\tfor (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {\n+\t\tbitshift = (int8_t)((bytes - i)*BYTE_SIZE);\n+\n+\t\tif (bitshift < 0)\n+\t\t\tbitshift = 0;\n+\t\tentry_ind = entry_ind | ip[i-1] << bitshift;\n+\t}\n+\n+\treturn entry_ind;\n+}\n+\n+/*\n+ * Simulate adding a new route to the LPM counting number\n+ * of new tables that will be needed\n+ *\n+ * It returns 0 on success, or 1 if\n+ * the process needs to be continued by calling the function again.\n+ */\n+static inline int\n+simulate_add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n+\t\tstruct rte_lpm6_tbl_entry **next_tbl, const uint8_t *ip,\n+\t\tuint8_t bytes, uint8_t first_byte, uint8_t depth,\n+\t\tuint32_t *need_tbl_nb)\n+{\n+\tuint32_t entry_ind;\n+\tuint8_t bits_covered;\n+\tuint32_t next_tbl_ind;\n+\n+\t/*\n+\t * Calculate index to the table based on the number and position\n+\t * of the bytes being inspected in this step.\n+\t */\n+\tentry_ind = get_bitshift(ip, first_byte, bytes);\n+\n+\t/* Number of bits covered in this step */\n+\tbits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);\n+\n+\tif (depth <= bits_covered) {\n+\t\t*need_tbl_nb = 0;\n+\t\treturn 0;\n+\t}\n+\n+\tif (tbl[entry_ind].valid == 0 || tbl[entry_ind].ext_entry == 0) {\n+\t\t/* from this point on a new table is needed on each level\n+\t\t * that is not covered yet\n+\t\t */\n+\t\tdepth -= bits_covered;\n+\t\tuint32_t cnt = depth >> 3; /* depth / BYTE_SIZE */\n+\t\tif (depth & 7) /* 0b00000111 */\n+\t\t\t/* if depth % 8 > 0 then one more table is needed\n+\t\t\t * for those last bits\n+\t\t\t */\n+\t\t\tcnt++;\n+\n+\t\t*need_tbl_nb = cnt;\n+\t\treturn 0;\n+\t}\n+\n+\tnext_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex;\n+\t*next_tbl = &(lpm->tbl8[next_tbl_ind *\n+\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);\n+\t*need_tbl_nb = 0;\n+\treturn 1;\n+}\n+\n /*\n * Partially adds a new route to the data structure (tbl24+tbl8s).\n * It returns 0 on success, a negative number on failure, or 1 if\n@@ -457,25 +650,21 @@ expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,\n */\n static inline int\n add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n-\t\tstruct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip, uint8_t bytes,\n-\t\tuint8_t first_byte, uint8_t depth, uint32_t next_hop)\n+\t\tuint32_t tbl_ind, struct rte_lpm6_tbl_entry **next_tbl,\n+\t\tuint32_t *next_tbl_ind, uint8_t *ip, uint8_t bytes,\n+\t\tuint8_t first_byte, uint8_t depth, uint32_t next_hop,\n+\t\tuint8_t is_new_rule)\n {\n-\tuint32_t tbl_index, tbl_range, tbl8_group_start, tbl8_group_end, i;\n-\tint32_t tbl8_gindex;\n-\tint8_t bitshift;\n+\tuint32_t entry_ind, tbl_range, tbl8_group_start, tbl8_group_end, i;\n+\tuint32_t tbl8_gindex;\n \tuint8_t bits_covered;\n+\tint ret;\n \n \t/*\n \t * Calculate index to the table based on the number and position\n \t * of the bytes being inspected in this step.\n \t */\n-\ttbl_index = 0;\n-\tfor (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {\n-\t\tbitshift = (int8_t)((bytes - i)*BYTE_SIZE);\n-\n-\t\tif (bitshift < 0) bitshift = 0;\n-\t\ttbl_index = tbl_index | ip[i-1] << bitshift;\n-\t}\n+\tentry_ind = get_bitshift(ip, first_byte, bytes);\n \n \t/* Number of bits covered in this step */\n \tbits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);\n@@ -487,7 +676,7 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n \tif (depth <= bits_covered) {\n \t\ttbl_range = 1 << (bits_covered - depth);\n \n-\t\tfor (i = tbl_index; i < (tbl_index + tbl_range); i++) {\n+\t\tfor (i = entry_ind; i < (entry_ind + tbl_range); i++) {\n \t\t\tif (!tbl[i].valid || (tbl[i].ext_entry == 0 &&\n \t\t\t\t\ttbl[i].depth <= depth)) {\n \n@@ -509,10 +698,15 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n \t\t\t\t */\n \t\t\t\ttbl8_gindex = tbl[i].lpm6_tbl8_gindex *\n \t\t\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES;\n-\t\t\t\texpand_rule(lpm, tbl8_gindex, depth, next_hop);\n+\t\t\t\texpand_rule(lpm, tbl8_gindex, depth, depth,\n+\t\t\t\t\t\tnext_hop, VALID);\n \t\t\t}\n \t\t}\n \n+\t\t/* update tbl8 rule reference counter */\n+\t\tif (tbl_ind != TBL24_IND && is_new_rule)\n+\t\t\tlpm->tbl8_hdrs[tbl_ind].ref_cnt++;\n+\n \t\treturn 0;\n \t}\n \t/*\n@@ -521,12 +715,24 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n \t */\n \telse {\n \t\t/* If it's invalid a new tbl8 is needed */\n-\t\tif (!tbl[tbl_index].valid) {\n-\t\t\tif (lpm->next_tbl8 < lpm->number_tbl8s)\n-\t\t\t\ttbl8_gindex = (lpm->next_tbl8)++;\n-\t\t\telse\n+\t\tif (!tbl[entry_ind].valid) {\n+\t\t\t/* get a new table */\n+\t\t\tret = tbl8_get(lpm, &tbl8_gindex);\n+\t\t\tif (ret != 0)\n \t\t\t\treturn -ENOSPC;\n \n+\t\t\t/* invalidate all new tbl8 entries */\n+\t\t\ttbl8_group_start = tbl8_gindex *\n+\t\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES;\n+\t\t\tmemset(&lpm->tbl8[tbl8_group_start], 0,\n+\t\t\t\t\t RTE_LPM6_TBL8_GROUP_NUM_ENTRIES);\n+\n+\t\t\t/* init the new table's header:\n+\t\t\t * save the reference to the owner table\n+\t\t\t */\n+\t\t\tinit_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind);\n+\n+\t\t\t/* reference to a new tbl8 */\n \t\t\tstruct rte_lpm6_tbl_entry new_tbl_entry = {\n \t\t\t\t.lpm6_tbl8_gindex = tbl8_gindex,\n \t\t\t\t.depth = 0,\n@@ -535,17 +741,20 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n \t\t\t\t.ext_entry = 1,\n \t\t\t};\n \n-\t\t\ttbl[tbl_index] = new_tbl_entry;\n+\t\t\ttbl[entry_ind] = new_tbl_entry;\n+\n+\t\t\t/* update the current table's reference counter */\n+\t\t\tif (tbl_ind != TBL24_IND)\n+\t\t\t\tlpm->tbl8_hdrs[tbl_ind].ref_cnt++;\n \t\t}\n \t\t/*\n-\t\t * If it's valid but not extended the rule that was stored *\n+\t\t * If it's valid but not extended the rule that was stored\n \t\t * here needs to be moved to the next table.\n \t\t */\n-\t\telse if (tbl[tbl_index].ext_entry == 0) {\n-\t\t\t/* Search for free tbl8 group. */\n-\t\t\tif (lpm->next_tbl8 < lpm->number_tbl8s)\n-\t\t\t\ttbl8_gindex = (lpm->next_tbl8)++;\n-\t\t\telse\n+\t\telse if (tbl[entry_ind].ext_entry == 0) {\n+\t\t\t/* get a new tbl8 index */\n+\t\t\tret = tbl8_get(lpm, &tbl8_gindex);\n+\t\t\tif (ret != 0)\n \t\t\t\treturn -ENOSPC;\n \n \t\t\ttbl8_group_start = tbl8_gindex *\n@@ -553,13 +762,22 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n \t\t\ttbl8_group_end = tbl8_group_start +\n \t\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES;\n \n+\t\t\tstruct rte_lpm6_tbl_entry tbl_entry = {\n+\t\t\t\t.next_hop = tbl[entry_ind].next_hop,\n+\t\t\t\t.depth = tbl[entry_ind].depth,\n+\t\t\t\t.valid = VALID,\n+\t\t\t\t.valid_group = VALID,\n+\t\t\t\t.ext_entry = 0\n+\t\t\t};\n+\n \t\t\t/* Populate new tbl8 with tbl value. */\n-\t\t\tfor (i = tbl8_group_start; i < tbl8_group_end; i++) {\n-\t\t\t\tlpm->tbl8[i].valid = VALID;\n-\t\t\t\tlpm->tbl8[i].depth = tbl[tbl_index].depth;\n-\t\t\t\tlpm->tbl8[i].next_hop = tbl[tbl_index].next_hop;\n-\t\t\t\tlpm->tbl8[i].ext_entry = 0;\n-\t\t\t}\n+\t\t\tfor (i = tbl8_group_start; i < tbl8_group_end; i++)\n+\t\t\t\tlpm->tbl8[i] = tbl_entry;\n+\n+\t\t\t/* init the new table's header:\n+\t\t\t * save the reference to the owner table\n+\t\t\t */\n+\t\t\tinit_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind);\n \n \t\t\t/*\n \t\t\t * Update tbl entry to point to new tbl8 entry. Note: The\n@@ -574,11 +792,16 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,\n \t\t\t\t.ext_entry = 1,\n \t\t\t};\n \n-\t\t\ttbl[tbl_index] = new_tbl_entry;\n+\t\t\ttbl[entry_ind] = new_tbl_entry;\n+\n+\t\t\t/* update the current table's reference counter */\n+\t\t\tif (tbl_ind != TBL24_IND)\n+\t\t\t\tlpm->tbl8_hdrs[tbl_ind].ref_cnt++;\n \t\t}\n \n-\t\t*tbl_next = &(lpm->tbl8[tbl[tbl_index].lpm6_tbl8_gindex *\n-\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);\n+\t\t*next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex;\n+\t\t*next_tbl = &(lpm->tbl8[*next_tbl_ind *\n+\t\t\t\t RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);\n \t}\n \n \treturn 1;\n@@ -595,13 +818,56 @@ rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n }\n VERSION_SYMBOL(rte_lpm6_add, _v20, 2.0);\n \n+\n+/*\n+ * Simulate adding a route to LPM\n+ *\n+ *\tReturns:\n+ * 0 on success\n+ * -ENOSPC not enought tbl8 left\n+ */\n+static int\n+simulate_add(struct rte_lpm6 *lpm, const uint8_t *masked_ip, uint8_t depth)\n+{\n+\tstruct rte_lpm6_tbl_entry *tbl;\n+\tstruct rte_lpm6_tbl_entry *tbl_next = NULL;\n+\tint ret, i;\n+\n+\t/* number of new tables needed for a step */\n+\tuint32_t need_tbl_nb;\n+\t/* total number of new tables needed */\n+\tuint32_t total_need_tbl_nb;\n+\n+\t/* Inspect the first three bytes through tbl24 on the first step. */\n+\tret = simulate_add_step(lpm, lpm->tbl24, &tbl_next, masked_ip,\n+\t\t\tADD_FIRST_BYTE, 1, depth, &need_tbl_nb);\n+\ttotal_need_tbl_nb = need_tbl_nb;\n+\t/*\n+\t * Inspect one by one the rest of the bytes until\n+\t * the process is completed.\n+\t */\n+\tfor (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && ret == 1; i++) {\n+\t\ttbl = tbl_next;\n+\t\tret = simulate_add_step(lpm, tbl, &tbl_next, masked_ip, 1,\n+\t\t\t\t(uint8_t)(i+1), depth, &need_tbl_nb);\n+\t\ttotal_need_tbl_nb += need_tbl_nb;\n+\t}\n+\n+\tif (tbl8_available(lpm) < total_need_tbl_nb)\n+\t\t/* not enought tbl8 to add a rule */\n+\t\treturn -ENOSPC;\n+\n+\treturn 0;\n+}\n+\n int\n rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n \t\tuint32_t next_hop)\n {\n \tstruct rte_lpm6_tbl_entry *tbl;\n \tstruct rte_lpm6_tbl_entry *tbl_next = NULL;\n-\tint32_t ret;\n+\t/* init to avoid compiler warning */\n+\tuint32_t tbl_next_num = 123456;\n \tint status;\n \tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n \tint i;\n@@ -614,21 +880,23 @@ rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n \tip6_copy_addr(masked_ip, ip);\n \tip6_mask_addr(masked_ip, depth);\n \n-\t/* Add the rule to the rule table. */\n-\tret = rule_add(lpm, masked_ip, depth, next_hop);\n-\t/* If there is no space available for new rule return error. */\n+\t/* Simulate adding a new route */\n+\tint ret = simulate_add(lpm, masked_ip, depth);\n \tif (ret < 0)\n \t\treturn ret;\n \n+\t/* Add the rule to the rule table. */\n+\tint is_new_rule = rule_add(lpm, masked_ip, depth, next_hop);\n+\t/* If there is no space available for new rule return error. */\n+\tif (is_new_rule < 0)\n+\t\treturn is_new_rule;\n+\n \t/* Inspect the first three bytes through tbl24 on the first step. */\n \ttbl = lpm->tbl24;\n-\tstatus = add_step (lpm, tbl, &tbl_next, masked_ip, ADD_FIRST_BYTE, 1,\n-\t\t\tdepth, next_hop);\n-\tif (status < 0) {\n-\t\trte_lpm6_delete(lpm, masked_ip, depth);\n-\n-\t\treturn status;\n-\t}\n+\tstatus = add_step(lpm, tbl, TBL24_IND, &tbl_next, &tbl_next_num,\n+\t\t\tmasked_ip, ADD_FIRST_BYTE, 1, depth, next_hop,\n+\t\t\tis_new_rule);\n+\tassert(status >= 0);\n \n \t/*\n \t * Inspect one by one the rest of the bytes until\n@@ -636,13 +904,10 @@ rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n \t */\n \tfor (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && status == 1; i++) {\n \t\ttbl = tbl_next;\n-\t\tstatus = add_step (lpm, tbl, &tbl_next, masked_ip, 1, (uint8_t)(i+1),\n-\t\t\t\tdepth, next_hop);\n-\t\tif (status < 0) {\n-\t\t\trte_lpm6_delete(lpm, masked_ip, depth);\n-\n-\t\t\treturn status;\n-\t\t}\n+\t\tstatus = add_step(lpm, tbl, tbl_next_num, &tbl_next,\n+\t\t\t\t&tbl_next_num, masked_ip, 1, (uint8_t)(i+1),\n+\t\t\t\tdepth, next_hop, is_new_rule);\n+\t\tassert(status >= 0);\n \t}\n \n \treturn status;\n@@ -717,9 +982,8 @@ rte_lpm6_lookup_v1705(const struct rte_lpm6 *lpm, uint8_t *ip,\n \tuint32_t tbl24_index;\n \n \t/* DEBUG: Check user input arguments. */\n-\tif ((lpm == NULL) || (ip == NULL) || (next_hop == NULL)) {\n+\tif ((lpm == NULL) || (ip == NULL) || (next_hop == NULL))\n \t\treturn -EINVAL;\n-\t}\n \n \tfirst_byte = LOOKUP_FIRST_BYTE;\n \ttbl24_index = (ip[0] << BYTES2_SIZE) | (ip[1] << BYTE_SIZE) | ip[2];\n@@ -755,9 +1019,8 @@ rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm,\n \tint status;\n \n \t/* DEBUG: Check user input arguments. */\n-\tif ((lpm == NULL) || (ips == NULL) || (next_hops == NULL)) {\n+\tif ((lpm == NULL) || (ips == NULL) || (next_hops == NULL))\n \t\treturn -EINVAL;\n-\t}\n \n \tfor (i = 0; i < n; i++) {\n \t\tfirst_byte = LOOKUP_FIRST_BYTE;\n@@ -900,62 +1163,22 @@ rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n \treturn ret;\n }\n \n-/*\n- * Deletes a rule\n- */\n-int\n-rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n-{\n-\tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n-\tint ret;\n-\n-\t/*\n-\t * Check input arguments.\n-\t */\n-\tif ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) {\n-\t\treturn -EINVAL;\n-\t}\n-\n-\t/* Copy the IP and mask it to avoid modifying user's input data. */\n-\tip6_copy_addr(masked_ip, ip);\n-\tip6_mask_addr(masked_ip, depth);\n-\n-\t/* Delete the rule from the rule table. */\n-\tret = rule_delete(lpm, masked_ip, depth);\n-\tif (ret < 0)\n-\t\treturn -ENOENT;\n-\n-\t/*\n-\t * Set all the table entries to 0 (ie delete every rule\n-\t * from the data structure.\n-\t */\n-\tlpm->next_tbl8 = 0;\n-\tmemset(lpm->tbl24, 0, sizeof(lpm->tbl24));\n-\tmemset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])\n-\t\t\t* RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);\n-\n-\t/*\n-\t * Add every rule again (except for the one that was removed from\n-\t * the rules table).\n-\t */\n-\trebuild_lpm(lpm);\n-\n-\treturn 0;\n-}\n-\n /*\n * Deletes a group of rules\n+ *\n+ * Note that the function rebuilds the lpm table,\n+ * rather than doing incremental updates like\n+ * the regular delete function\n */\n int\n rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,\n-\t\tuint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, unsigned n)\n+\t\tuint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths,\n+\t\tunsigned n)\n {\n \tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n \tunsigned i;\n \n-\t/*\n-\t * Check input arguments.\n-\t */\n+\t/* Check input arguments. */\n \tif ((lpm == NULL) || (ips == NULL) || (depths == NULL))\n \t\treturn -EINVAL;\n \n@@ -969,10 +1192,10 @@ rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,\n \t * Set all the table entries to 0 (ie delete every rule\n \t * from the data structure.\n \t */\n-\tlpm->next_tbl8 = 0;\n \tmemset(lpm->tbl24, 0, sizeof(lpm->tbl24));\n \tmemset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])\n \t\t\t* RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);\n+\ttbl8_pool_init(lpm);\n \n \t/*\n \t * Add every rule again (except for the ones that were removed from\n@@ -992,9 +1215,6 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm)\n \t/* Zero used rules counter. */\n \tlpm->used_rules = 0;\n \n-\t/* Zero next tbl8 index. */\n-\tlpm->next_tbl8 = 0;\n-\n \t/* Zero tbl24. */\n \tmemset(lpm->tbl24, 0, sizeof(lpm->tbl24));\n \n@@ -1002,6 +1222,268 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm)\n \tmemset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *\n \t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);\n \n+\t/* init pool of free tbl8 indexes */\n+\ttbl8_pool_init(lpm);\n+\n \t/* Delete all rules form the rules table. */\n \trte_hash_reset(lpm->rules_tbl);\n }\n+\n+/*\n+ * Convert a depth to a one byte long mask\n+ * Example: 4 will be converted to 0xF0\n+ */\n+static uint8_t __attribute__((pure))\n+depth_to_mask_1b(uint8_t depth)\n+{\n+\t/* To calculate a mask start with a 1 on the left hand side and right\n+\t * shift while populating the left hand side with 1's\n+\t */\n+\treturn (signed char)0x80 >> (depth - 1);\n+}\n+\n+/*\n+ * Find a less specific rule\n+ */\n+static int\n+rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n+\tstruct rte_lpm6_rule *rule)\n+{\n+\tint ret;\n+\tuint32_t next_hop;\n+\tuint8_t mask;\n+\tstruct rte_lpm6_rule_key rule_key;\n+\n+\tif (depth == 1)\n+\t\treturn 0;\n+\n+\trule_key_init(&rule_key, ip, depth);\n+\n+\twhile (depth > 1) {\n+\t\tdepth--;\n+\n+\t\t/* each iteration zero one more bit of the key */\n+\t\tmask = depth & 7; /* depth % BYTE_SIZE */\n+\t\tif (mask > 0)\n+\t\t\tmask = depth_to_mask_1b(mask);\n+\n+\t\trule_key.depth = depth;\n+\t\trule_key.ip[depth >> 3] &= mask;\n+\n+\t\tret = rule_find_with_key(lpm, &rule_key, &next_hop);\n+\t\tif (ret) {\n+\t\t\trule->depth = depth;\n+\t\t\tip6_copy_addr(rule->ip, rule_key.ip);\n+\t\t\trule->next_hop = next_hop;\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Find range of tbl8 cells occupied by a rule\n+ */\n+static void\n+rule_find_range(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth,\n+\t\t struct rte_lpm6_tbl_entry **from,\n+\t\t struct rte_lpm6_tbl_entry **to,\n+\t\t uint32_t *out_tbl_ind)\n+{\n+\tuint32_t ind;\n+\tuint32_t first_3bytes = (uint32_t)ip[0] << 16 | ip[1] << 8 | ip[2];\n+\n+\tif (depth <= 24) {\n+\t\t/* rule is within the top level */\n+\t\tind = first_3bytes;\n+\t\t*from = &lpm->tbl24[ind];\n+\t\tind += (1 << (24 - depth)) - 1;\n+\t\t*to = &lpm->tbl24[ind];\n+\t\t*out_tbl_ind = TBL24_IND;\n+\t} else {\n+\t\t/* top level entry */\n+\t\tstruct rte_lpm6_tbl_entry *tbl = &lpm->tbl24[first_3bytes];\n+\t\tassert(tbl->ext_entry == 1);\n+\t\t/* first tbl8 */\n+\t\tuint32_t tbl_ind = tbl->lpm6_tbl8_gindex;\n+\t\ttbl = &lpm->tbl8[tbl_ind *\n+\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES];\n+\t\t/* current ip byte, the top level is already behind */\n+\t\tuint8_t byte = 3;\n+\t\t/* minus top level */\n+\t\tdepth -= 24;\n+\n+\t\t/* interate through levels (tbl8s)\n+\t\t * until we reach the last one\n+\t\t */\n+\t\twhile (depth > 8) {\n+\t\t\ttbl += ip[byte];\n+\t\t\tassert(tbl->ext_entry == 1);\n+\t\t\t/* go to the next level/tbl8 */\n+\t\t\ttbl_ind = tbl->lpm6_tbl8_gindex;\n+\t\t\ttbl = &lpm->tbl8[tbl_ind *\n+\t\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES];\n+\t\t\tbyte += 1;\n+\t\t\tdepth -= 8;\n+\t\t}\n+\n+\t\t/* last level/tbl8 */\n+\t\tind = ip[byte] & depth_to_mask_1b(depth);\n+\t\t*from = &tbl[ind];\n+\t\tind += (1 << (8 - depth)) - 1;\n+\t\t*to = &tbl[ind];\n+\t\t*out_tbl_ind = tbl_ind;\n+\t}\n+}\n+\n+/*\n+ * Remove a table from the LPM tree\n+ */\n+static void\n+remove_tbl(struct rte_lpm6 *lpm, struct rte_lpm_tbl8_hdr *tbl_hdr,\n+\t\t uint32_t tbl_ind, struct rte_lpm6_rule *lsp_rule)\n+{\n+\tstruct rte_lpm6_tbl_entry *owner_entry;\n+\n+\tif (tbl_hdr->owner_tbl_ind == TBL24_IND)\n+\t\towner_entry = &lpm->tbl24[tbl_hdr->owner_entry_ind];\n+\telse {\n+\t\tuint32_t owner_tbl_ind = tbl_hdr->owner_tbl_ind;\n+\t\towner_entry = &lpm->tbl8[\n+\t\t\towner_tbl_ind * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES +\n+\t\t\ttbl_hdr->owner_entry_ind];\n+\n+\t\tstruct rte_lpm_tbl8_hdr *owner_tbl_hdr =\n+\t\t\t&lpm->tbl8_hdrs[owner_tbl_ind];\n+\t\tif (--owner_tbl_hdr->ref_cnt == 0)\n+\t\t\tremove_tbl(lpm, owner_tbl_hdr, owner_tbl_ind, lsp_rule);\n+\t}\n+\n+\tassert(owner_entry->ext_entry == 1);\n+\n+\t/* unlink the table */\n+\tif (lsp_rule != NULL) {\n+\t\tstruct rte_lpm6_tbl_entry new_tbl_entry = {\n+\t\t\t.next_hop = lsp_rule->next_hop,\n+\t\t\t.depth = lsp_rule->depth,\n+\t\t\t.valid = VALID,\n+\t\t\t.valid_group = VALID,\n+\t\t\t.ext_entry = 0\n+\t\t};\n+\n+\t\t*owner_entry = new_tbl_entry;\n+\t} else {\n+\t\tstruct rte_lpm6_tbl_entry new_tbl_entry = {\n+\t\t\t.next_hop = 0,\n+\t\t\t.depth = 0,\n+\t\t\t.valid = INVALID,\n+\t\t\t.valid_group = INVALID,\n+\t\t\t.ext_entry = 0\n+\t\t};\n+\n+\t\t*owner_entry = new_tbl_entry;\n+\t}\n+\n+\t/* return the table to the pool */\n+\ttbl8_put(lpm, tbl_ind);\n+}\n+\n+/*\n+ * Deletes a rule\n+ */\n+int\n+rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n+{\n+\tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n+\tstruct rte_lpm6_rule lsp_rule_obj;\n+\tstruct rte_lpm6_rule *lsp_rule;\n+\tint ret;\n+\tuint32_t tbl_ind;\n+\tstruct rte_lpm6_tbl_entry *from, *to;\n+\n+\t/* Check input arguments. */\n+\tif ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))\n+\t\treturn -EINVAL;\n+\n+\t/* Copy the IP and mask it to avoid modifying user's input data. */\n+\tip6_copy_addr(masked_ip, ip);\n+\tip6_mask_addr(masked_ip, depth);\n+\n+\t/* Delete the rule from the rule table. */\n+\tret = rule_delete(lpm, masked_ip, depth);\n+\tif (ret < 0)\n+\t\treturn -ENOENT;\n+\n+\t/* find rule cells */\n+\trule_find_range(lpm, masked_ip, depth, &from, &to, &tbl_ind);\n+\n+\t/* find a less specific rule (a rule with smaller depth)\n+\t * note: masked_ip will be modified, don't use it anymore\n+\t */\n+\tret = rule_find_less_specific(lpm, masked_ip, depth,\n+\t\t\t&lsp_rule_obj);\n+\tlsp_rule = ret ? &lsp_rule_obj : NULL;\n+\n+\t/* decrement the table rule counter,\n+\t * note that tbl24 doesn't have a header\n+\t */\n+\tif (tbl_ind != TBL24_IND) {\n+\t\tstruct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind];\n+\t\tif (--tbl_hdr->ref_cnt == 0) {\n+\t\t\t/* remove the table */\n+\t\t\tremove_tbl(lpm, tbl_hdr, tbl_ind, lsp_rule);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\n+\t/* iterate rule cells */\n+\tfor (; from <= to; from++)\n+\t\tif (from->ext_entry == 1) {\n+\t\t\t/* reference to a more specific space\n+\t\t\t * of the prefix/rule. Entries in a more\n+\t\t\t * specific space that are not used by\n+\t\t\t * a more specific prefix must be occupied\n+\t\t\t * by the prefix\n+\t\t\t */\n+\t\t\tif (lsp_rule != NULL)\n+\t\t\t\texpand_rule(lpm,\n+\t\t\t\t\tfrom->lpm6_tbl8_gindex *\n+\t\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES,\n+\t\t\t\t\tdepth, lsp_rule->depth,\n+\t\t\t\t\tlsp_rule->next_hop, VALID);\n+\t\t\telse\n+\t\t\t\t/* since the prefix has no less specific prefix,\n+\t\t\t\t * its more specific space must be invalidated\n+\t\t\t\t */\n+\t\t\t\texpand_rule(lpm,\n+\t\t\t\t\tfrom->lpm6_tbl8_gindex *\n+\t\t\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES,\n+\t\t\t\t\tdepth, 0, 0, INVALID);\n+\t\t} else if (from->depth == depth) {\n+\t\t\t/* entry is not a reference and belongs to the prefix */\n+\t\t\tif (lsp_rule != NULL) {\n+\t\t\t\tstruct rte_lpm6_tbl_entry new_tbl_entry = {\n+\t\t\t\t\t.next_hop = lsp_rule->next_hop,\n+\t\t\t\t\t.depth = lsp_rule->depth,\n+\t\t\t\t\t.valid = VALID,\n+\t\t\t\t\t.valid_group = VALID,\n+\t\t\t\t\t.ext_entry = 0\n+\t\t\t\t};\n+\n+\t\t\t\t*from = new_tbl_entry;\n+\t\t\t} else {\n+\t\t\t\tstruct rte_lpm6_tbl_entry new_tbl_entry = {\n+\t\t\t\t\t.next_hop = 0,\n+\t\t\t\t\t.depth = 0,\n+\t\t\t\t\t.valid = INVALID,\n+\t\t\t\t\t.valid_group = INVALID,\n+\t\t\t\t\t.ext_entry = 0\n+\t\t\t\t};\n+\n+\t\t\t\t*from = new_tbl_entry;\n+\t\t\t}\n+\t\t}\n+\n+\treturn 0;\n+}\n", "prefixes": [ "v7", "2/2" ] }