Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/41847/?format=api
{ "id": 41847, "url": "http://patchwork.dpdk.org/api/patches/41847/?format=api", "web_url": "http://patchwork.dpdk.org/project/dpdk/patch/20180628140551.A5B02378E@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": "<20180628140551.A5B02378E@dpdk.org>", "list_archive_url": "https://inbox.dpdk.org/dev/20180628140551.A5B02378E@dpdk.org", "date": "2018-06-28T14:05:37", "name": "librte_lpm: Improve performance of the delete and add functions", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "8abb2c1bbe0966938c8f4ee2ac6dd39f08feda48", "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/20180628140551.A5B02378E@dpdk.org/mbox/", "series": [ { "id": 295, "url": "http://patchwork.dpdk.org/api/series/295/?format=api", "web_url": "http://patchwork.dpdk.org/project/dpdk/list/?series=295", "date": "2018-06-28T14:05:37", "name": "librte_lpm: Improve performance of the delete and add functions", "version": 1, "mbox": "http://patchwork.dpdk.org/series/295/mbox/" } ], "comments": "http://patchwork.dpdk.org/api/patches/41847/comments/", "check": "fail", "checks": "http://patchwork.dpdk.org/api/patches/41847/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 A5B02378E;\n\tThu, 28 Jun 2018 16:05:51 +0200 (CEST)", "from relay-out3.mail.masterhost.ru (relay-out3.mail.masterhost.ru\n\t[83.222.12.13]) by dpdk.org (Postfix) with ESMTP id 327421DB9\n\tfor <dev@dpdk.org>; Thu, 28 Jun 2018 16:05:50 +0200 (CEST)", "from [37.139.80.50] (helo=h5.therouter.net)\n\tby relay3.mail.masterhost.ru with esmtpa \n\tenvelope from <alex@therouter.net>\n\tauthenticated with alex@therouter.net\n\tmessage id 1fYXYH-0000Ml-Ie; Thu, 28 Jun 2018 17:05:39 +0300", "by h5.therouter.net (sSMTP sendmail emulation);\n\tThu, 28 Jun 2018 17:05:37 +0300" ], "From": "\"Alex Kiselev\" <alex@therouter.net>", "Date": "Thu, 28 Jun 2018 17:05:37 +0300", "To": "\"dev@dpdk.org\" <dev@dpdk.org>,\n\tBruce Richardson <bruce.richardson@intel.com>", "X-KLMS-Rule-ID": "1", "X-KLMS-Message-Action": "clean", "X-KLMS-AntiSpam-Lua-Profiles": "126330 [Jun 28 2018]", "X-KLMS-AntiSpam-Version": "5.8.1.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: 148 148\n\t9a358fc38d9aa00e45831f16faac08b59faa47e7, {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] librte_lpm: Improve performance of the delete\n\tand 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": "<20180628140551.A5B02378E@dpdk.org>" }, "content": "There two major problems with the library:\nfirst, there is no need to rebuild the whole LPM tree \nwhen a rule is deleted and second, due to the current \nrules algorithm with complexity O(n) it's almost\nimpossible to deal with large rule sets (50k or so rules). \nThis patch addresses those two issues.\n\nSigned-off-by: Alex Kiselev <alex@therouter.net>\n---\n lib/librte_lpm/rte_lpm6.c | 1072 ++++++++++++++++++++++++++++++++++-----------\n lib/librte_lpm/rte_lpm6.h | 1 +\n 2 files changed, 816 insertions(+), 257 deletions(-)", "diff": "diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c\nindex 149677eb1..e9e6dbf90 100644\n--- a/lib/librte_lpm/rte_lpm6.c\n+++ b/lib/librte_lpm/rte_lpm6.c\n@@ -21,6 +21,9 @@\n #include <rte_errno.h>\n #include <rte_rwlock.h>\n #include <rte_spinlock.h>\n+#include <rte_hash.h>\n+#include <rte_hash_crc.h>\n+#include <assert.h>\n \n #include \"rte_lpm6.h\"\n \n@@ -37,6 +40,9 @@\n #define BYTE_SIZE 8\n #define BYTES2_SIZE 16\n \n+#define RULE_HASH_TABLE_EXTRA_SPACE 256\n+#define TBL24_IND UINT32_MAX\n+\n #define lpm6_tbl8_gindex next_hop\n \n /** Flags for setting an entry as valid/invalid. */\n@@ -70,6 +76,23 @@ struct rte_lpm6_rule {\n \tuint8_t depth; /**< Rule depth. */\n };\n \n+/** Rules tbl entry key. */\n+struct rte_lpm6_rule_key {\n+\tuint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */\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@@ -77,12 +100,18 @@ 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_lpm6_rule *rules_tbl; /**< LPM rules. */\n+\tstruct rte_mempool *rules_pool; /**< LPM rules mempool. */\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@@ -93,22 +122,130 @@ struct rte_lpm6 {\n * and set the rest to 0.\n */\n static inline void\n-mask_ip(uint8_t *ip, uint8_t depth)\n+ip6_mask_addr(uint8_t *ip, uint8_t depth)\n {\n- int16_t part_depth, mask;\n- int i;\n+\tint16_t part_depth, mask;\n+\tint i;\n \n-\t\tpart_depth = depth;\n+\tpart_depth = depth;\n \n-\t\tfor (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) {\n-\t\t\tif (part_depth < BYTE_SIZE && part_depth >= 0) {\n-\t\t\t\tmask = (uint16_t)(~(UINT8_MAX >> part_depth));\n-\t\t\t\tip[i] = (uint8_t)(ip[i] & mask);\n-\t\t\t} else if (part_depth < 0) {\n-\t\t\t\tip[i] = 0;\n-\t\t\t}\n-\t\t\tpart_depth -= BYTE_SIZE;\n-\t\t}\n+\tfor (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) {\n+\t\tif (part_depth < BYTE_SIZE && part_depth >= 0) {\n+\t\t\tmask = (uint16_t)(~(UINT8_MAX >> part_depth));\n+\t\t\tip[i] = (uint8_t)(ip[i] & mask);\n+\t\t} else if (part_depth < 0)\n+\t\t\tip[i] = 0;\n+\n+\t\tpart_depth -= BYTE_SIZE;\n+\t}\n+}\n+\n+/* copy ipv6 address */\n+static inline void\n+ip6_copy_addr(uint8_t *dst, const uint8_t *src)\n+{\n+\trte_memcpy(dst, src, RTE_LPM6_IPV6_ADDR_SIZE);\n+}\n+\n+/*\n+ * LPM6 rule hash function\n+ */\n+static inline uint32_t\n+rule_hash_crc(const void *data, __rte_unused uint32_t data_len,\n+\t\t uint32_t init_val)\n+{\n+\treturn rte_hash_crc(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+\t/* put entire range of indexes to the tbl8 pool */\n+\tuint32_t i;\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 awailable 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\tnote that ip must be already masked\n+ */\n+static inline void\n+rule_key_init(struct rte_lpm6_rule_key *key, uint8_t *ip, uint8_t depth)\n+{\n+\tip6_copy_addr(key->ip, ip);\n+\tkey->depth = depth;\n+}\n+\n+/*\n+ * Recreate the entire LPM tree by reinserting all rules\n+ */\n+static void\n+recreate_lpm(struct rte_lpm6 *lpm)\n+{\n+\tstruct rte_lpm6_rule *rule;\n+\tstruct rte_lpm6_rule *rule_key;\n+\tuint32_t iter = 0;\n+\twhile (rte_hash_iterate(lpm->rules_tbl, (const void **) &rule_key,\n+\t\t\t(void **) &rule, &iter) >= 0)\n+\t\trte_lpm6_add(lpm, rule->ip, rule->depth, rule->next_hop);\n+}\n+\n+/*\n+ *\tFree all rules\n+ */\n+static void\n+rules_free(struct rte_lpm6 *lpm)\n+{\n+\tstruct rte_lpm6_rule *rule;\n+\tstruct rte_lpm6_rule *rule_key;\n+\tuint32_t iter = 0;\n+\twhile (rte_hash_iterate(lpm->rules_tbl, (const void **) &rule_key,\n+\t\t\t(void **) &rule, &iter) >= 0)\n+\t\trte_mempool_put(lpm->rules_pool, rule);\n }\n \n /*\n@@ -121,7 +258,7 @@ rte_lpm6_create(const char *name, int socket_id,\n \tchar mem_name[RTE_LPM6_NAMESIZE];\n \tstruct rte_lpm6 *lpm = NULL;\n \tstruct rte_tailq_entry *te;\n-\tuint64_t mem_size, rules_size;\n+\tuint64_t mem_size;\n \tstruct rte_lpm6_list *lpm_list;\n \n \tlpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);\n@@ -136,12 +273,72 @@ rte_lpm6_create(const char *name, int socket_id,\n \t\treturn NULL;\n \t}\n \n+\tstruct rte_mempool *rules_mempool = NULL;\n+\tstruct rte_hash *rules_tbl = NULL;\n+\tuint32_t *tbl8_pool = NULL;\n+\tstruct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL;\n+\n+\t/* allocate rules mempool */\n+\tsnprintf(mem_name, sizeof(mem_name), \"LRM_%s\", name);\n+\trules_mempool = rte_mempool_create(mem_name,\n+\t\t\tconfig->max_rules, sizeof(struct rte_lpm6_rule), 0, 0,\n+\t\t\tNULL, NULL, NULL, NULL, socket_id,\n+\t\t\tMEMPOOL_F_NO_CACHE_ALIGN);\n+\tif (rules_mempool == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"LPM rules mempool 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/* create rules hash table */\n+\tsnprintf(mem_name, sizeof(mem_name), \"LRH_%s\", name);\n+\n+\tstruct rte_hash_parameters rule_hash_tbl_params = {\n+\t\t.entries = config->max_rules + RULE_HASH_TABLE_EXTRA_SPACE,\n+\t\t.key_len = sizeof(struct rte_lpm6_rule_key),\n+\t\t.hash_func = rule_hash_crc,\n+\t\t.hash_func_init_val = 0,\n+\t\t.name = mem_name,\n+\t\t.reserved = 0,\n+\t\t.socket_id = socket_id,\n+\t\t.extra_flag = 0\n+\t};\n+\n+\trules_tbl = rte_hash_create(&rule_hash_tbl_params);\n+\tif (rules_tbl == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"LPM rules hash table allocation failed: %s (%d)\",\n+\t\t\t\t rte_strerror(rte_errno), rte_errno);\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 \tmem_size = sizeof(*lpm) + (sizeof(lpm->tbl8[0]) *\n \t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s);\n-\trules_size = sizeof(struct rte_lpm6_rule) * config->max_rules;\n \n \trte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);\n \n@@ -154,7 +351,7 @@ rte_lpm6_create(const char *name, int socket_id,\n \tlpm = NULL;\n \tif (te != NULL) {\n \t\trte_errno = EEXIST;\n-\t\tgoto exit;\n+\t\tgoto fail;\n \t}\n \n \t/* allocate tailq entry */\n@@ -162,30 +359,18 @@ rte_lpm6_create(const char *name, int socket_id,\n \tif (te == NULL) {\n \t\tRTE_LOG(ERR, LPM, \"Failed to allocate tailq entry!\\n\");\n \t\trte_errno = ENOMEM;\n-\t\tgoto exit;\n+\t\tgoto fail;\n \t}\n \n \t/* Allocate memory to store the LPM data structures. */\n-\tlpm = rte_zmalloc_socket(mem_name, (size_t)mem_size,\n+\tlpm = (struct rte_lpm6 *)rte_zmalloc_socket(mem_name, (size_t)mem_size,\n \t\t\tRTE_CACHE_LINE_SIZE, socket_id);\n \n \tif (lpm == NULL) {\n \t\tRTE_LOG(ERR, LPM, \"LPM memory allocation failed\\n\");\n \t\trte_free(te);\n \t\trte_errno = ENOMEM;\n-\t\tgoto exit;\n-\t}\n-\n-\tlpm->rules_tbl = rte_zmalloc_socket(NULL,\n-\t\t\t(size_t)rules_size, RTE_CACHE_LINE_SIZE, socket_id);\n-\n-\tif (lpm->rules_tbl == NULL) {\n-\t\tRTE_LOG(ERR, LPM, \"LPM rules_tbl allocation failed\\n\");\n-\t\trte_free(lpm);\n-\t\tlpm = NULL;\n-\t\trte_free(te);\n-\t\trte_errno = ENOMEM;\n-\t\tgoto exit;\n+\t\tgoto fail;\n \t}\n \n \t/* Save user arguments. */\n@@ -193,14 +378,37 @@ 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 \n+\tlpm->rules_tbl = rules_tbl;\n+\tlpm->tbl8_pool = tbl8_pool;\n+\tlpm->tbl8_hdrs = tbl8_hdrs;\n+\tlpm->rules_pool = rules_mempool;\n+\n+\t/* init the stack */\n+\ttbl8_pool_init(lpm);\n+\n \tte->data = (void *) lpm;\n \n \tTAILQ_INSERT_TAIL(lpm_list, te, next);\n+\trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n+\treturn lpm;\n \n-exit:\n+fail:\n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n \n-\treturn lpm;\n+fail_wo_unlock:\n+\tif (rules_mempool != NULL)\n+\t\trte_mempool_free(rules_mempool);\n+\n+\tif (tbl8_hdrs != NULL)\n+\t\trte_free(tbl8_hdrs);\n+\n+\tif (tbl8_pool != NULL)\n+\t\trte_free(tbl8_pool);\n+\n+\tif (rules_tbl != NULL)\n+\t\trte_hash_free(rules_tbl);\n+\n+\treturn NULL;\n }\n \n /*\n@@ -259,50 +467,93 @@ rte_lpm6_free(struct rte_lpm6 *lpm)\n \n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n \n-\trte_free(lpm->rules_tbl);\n+\trte_mempool_free(lpm->rules_pool);\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 }\n \n+/* Find a rule */\n+static inline struct rte_lpm6_rule*\n+rule_find_with_key(struct rte_lpm6 *lpm,\n+\t\t const struct rte_lpm6_rule_key *rule_key)\n+{\n+\t/* look for a rule */\n+\tstruct rte_lpm6_rule\t*rule;\n+\tint ret = rte_hash_lookup_data(lpm->rules_tbl,\n+\t\t(const void *) rule_key, (void **) &rule);\n+\treturn (ret >= 0) ? rule : NULL;\n+}\n+\n+/* Find a rule */\n+static struct rte_lpm6_rule*\n+rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n+{\n+\t/* init a rule key */\n+\tstruct rte_lpm6_rule_key rule_key;\n+\trule_key_init(&rule_key, ip, depth);\n+\n+\treturn rule_find_with_key(lpm, &rule_key);\n+}\n+\n /*\n * Checks if a rule already exists in the rules table and updates\n * the nexthop if so. Otherwise it adds a new rule if enough space is available.\n+ *\n+ * Returns:\n+ * 0 - next hop of existed rule is updated\n+ * 1 - new rule successfuly added\n+ * <0 - error\n */\n-static inline int32_t\n-rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint32_t next_hop, uint8_t depth)\n+static inline int\n+rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)\n {\n-\tuint32_t rule_index;\n+\t/* init a rule key */\n+\tstruct rte_lpm6_rule_key rule_key;\n+\trule_key_init(&rule_key, ip, depth);\n \n \t/* Scan through rule list to see if rule already exists. */\n-\tfor (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {\n-\n-\t\t/* If rule already exists update its next_hop and return. */\n-\t\tif ((memcmp (lpm->rules_tbl[rule_index].ip, ip,\n-\t\t\t\tRTE_LPM6_IPV6_ADDR_SIZE) == 0) &&\n-\t\t\t\tlpm->rules_tbl[rule_index].depth == depth) {\n-\t\t\tlpm->rules_tbl[rule_index].next_hop = next_hop;\n+\tstruct rte_lpm6_rule *rule = rule_find_with_key(lpm, &rule_key);\n \n-\t\t\treturn rule_index;\n-\t\t}\n+\t/* If rule already exists update its next_hop and return. */\n+\tif (rule != NULL) {\n+\t\trule->next_hop = next_hop;\n+\t\treturn 0;\n \t}\n \n \t/*\n \t * If rule does not exist check if there is space to add a new rule to\n \t * this rule group. If there is no space return error.\n \t */\n-\tif (lpm->used_rules == lpm->max_rules) {\n+\tif (lpm->used_rules == lpm->max_rules)\n \t\treturn -ENOSPC;\n-\t}\n \n-\t/* If there is space for the new rule add it. */\n-\trte_memcpy(lpm->rules_tbl[rule_index].ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);\n-\tlpm->rules_tbl[rule_index].next_hop = next_hop;\n-\tlpm->rules_tbl[rule_index].depth = depth;\n+\t/*\n+\t * If there is space for the new rule add it.\n+\t */\n+\n+\t/* get a new rule */\n+\tint ret = rte_mempool_get(lpm->rules_pool, (void **) &rule);\n+\tif (ret < 0)\n+\t\treturn ret;\n+\n+\t/* init the rule */\n+\trule->depth = depth;\n+\tip6_copy_addr(rule->ip, ip);\n+\trule->next_hop = next_hop;\n+\n+\t/* add the rule */\n+\tret = rte_hash_add_key_data(lpm->rules_tbl, &rule_key, rule);\n+\tif (ret < 0) {\n+\t\trte_mempool_put(lpm->rules_pool, rule);\n+\t\treturn ret;\n+\t}\n \n \t/* Increment the used rules counter for this rule group. */\n \tlpm->used_rules++;\n-\n-\treturn rule_index;\n+\treturn 1;\n }\n \n /*\n@@ -311,24 +562,24 @@ rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint32_t next_hop, uint8_t depth)\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@@ -336,11 +587,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 / 3 */\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@@ -348,25 +689,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@@ -378,7 +715,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@@ -400,10 +737,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@@ -412,12 +754,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@@ -426,17 +780,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@@ -444,13 +801,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@@ -465,11 +831,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@@ -486,13 +857,55 @@ 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+ *\t\t0 if 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 rule_index;\n+\tuint32_t tbl_next_num;\n \tint status;\n \tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n \tint i;\n@@ -502,26 +915,26 @@ rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n \t\treturn -EINVAL;\n \n \t/* Copy the IP and mask it to avoid modifying user's input data. */\n-\tmemcpy(masked_ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);\n-\tmask_ip(masked_ip, 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-\trule_index = rule_add(lpm, masked_ip, next_hop, depth);\n-\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 (rule_index < 0) {\n-\t\treturn rule_index;\n-\t}\n+\tif (is_new_rule < 0)\n+\t\treturn is_new_rule;\n+\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/* 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@@ -529,13 +942,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@@ -610,9 +1020,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@@ -648,9 +1057,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@@ -724,30 +1132,6 @@ MAP_STATIC_SYMBOL(int rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,\n \t\t\t\tint32_t *next_hops, unsigned int n),\n \t\trte_lpm6_lookup_bulk_func_v1705);\n \n-/*\n- * Finds a rule in rule table.\n- * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.\n- */\n-static inline int32_t\n-rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n-{\n-\tuint32_t rule_index;\n-\n-\t/* Scan used rules at given depth to find rule. */\n-\tfor (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {\n-\t\t/* If rule is found return the rule index. */\n-\t\tif ((memcmp (lpm->rules_tbl[rule_index].ip, ip,\n-\t\t\t\tRTE_LPM6_IPV6_ADDR_SIZE) == 0) &&\n-\t\t\t\tlpm->rules_tbl[rule_index].depth == depth) {\n-\n-\t\t\treturn rule_index;\n-\t\t}\n-\t}\n-\n-\t/* If rule is not found return -ENOENT. */\n-\treturn -ENOENT;\n-}\n-\n /*\n * Look for a rule in the high-level rules table\n */\n@@ -775,23 +1159,20 @@ int\n rte_lpm6_is_rule_present_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,\n \t\tuint32_t *next_hop)\n {\n-\tuint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];\n-\tint32_t rule_index;\n-\n \t/* Check user arguments. */\n \tif ((lpm == NULL) || next_hop == NULL || ip == NULL ||\n \t\t\t(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-\tmemcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);\n-\tmask_ip(ip_masked, depth);\n+\tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n+\tip6_copy_addr(masked_ip, ip);\n+\tip6_mask_addr(masked_ip, depth);\n \n-\t/* Look for the rule using rule_find. */\n-\trule_index = rule_find(lpm, ip_masked, depth);\n+\tstruct rte_lpm6_rule *rule = rule_find(lpm, ip, depth);\n \n-\tif (rule_index >= 0) {\n-\t\t*next_hop = lpm->rules_tbl[rule_index].next_hop;\n+\tif (rule != NULL) {\n+\t\t*next_hop = rule->next_hop;\n \t\treturn 1;\n \t}\n \n@@ -806,156 +1187,333 @@ MAP_STATIC_SYMBOL(int rte_lpm6_is_rule_present(struct rte_lpm6 *lpm,\n /*\n * Delete a rule from the rule table.\n * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.\n+ * return\n+ *\t\t0 if successful delete\n+ * <0 if failure\n */\n-static inline void\n-rule_delete(struct rte_lpm6 *lpm, int32_t rule_index)\n+static inline int\n+rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n {\n-\t/*\n-\t * Overwrite redundant rule with last rule in group and decrement rule\n-\t * counter.\n-\t */\n-\tlpm->rules_tbl[rule_index] = lpm->rules_tbl[lpm->used_rules-1];\n-\tlpm->used_rules--;\n+\t/* init a rule key */\n+\tstruct rte_lpm6_rule_key rule_key;\n+\trule_key_init(&rule_key, ip, depth);\n+\n+\t/* Look for a rule */\n+\tstruct rte_lpm6_rule\t*rule;\n+\tint ret = rte_hash_lookup_data(lpm->rules_tbl, (void *) &rule_key,\n+\t\t(void **) &rule);\n+\tif (ret >= 0) {\n+\t\t/* delete the rule */\n+\t\trte_hash_del_key(lpm->rules_tbl, (void *) &rule_key);\n+\t\tlpm->used_rules--;\n+\t\trte_mempool_put(lpm->rules_pool, rule);\n+\t}\n+\n+\treturn ret;\n }\n \n /*\n- * Deletes a rule\n+ * Deletes a group of rules\n */\n int\n-rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n+rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,\n+\t\tuint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths,\n+\t\tunsigned n)\n {\n-\tint32_t rule_to_delete_index;\n-\tuint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];\n-\tunsigned i;\n-\n-\t/*\n-\t * Check input arguments.\n-\t */\n-\tif ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) {\n+\t/* Check input arguments. */\n+\tif ((lpm == NULL) || (ips == NULL) || (depths == NULL))\n \t\treturn -EINVAL;\n-\t}\n-\n-\t/* Copy the IP and mask it to avoid modifying user's input data. */\n-\tmemcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);\n-\tmask_ip(ip_masked, depth);\n-\n-\t/*\n-\t * Find the index of the input rule, that needs to be deleted, in the\n-\t * rule table.\n-\t */\n-\trule_to_delete_index = rule_find(lpm, ip_masked, depth);\n-\n-\t/*\n-\t * Check if rule_to_delete_index was found. If no rule was found the\n-\t * function rule_find returns -ENOENT.\n-\t */\n-\tif (rule_to_delete_index < 0)\n-\t\treturn rule_to_delete_index;\n \n-\t/* Delete the rule from the rule table. */\n-\trule_delete(lpm, rule_to_delete_index);\n+\tunsigned i;\n+\tfor (i = 0; i < n; i++)\n+\t\trule_delete(lpm, ips[i], depths[i]);\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+\ttbl8_pool_init(lpm);\n \n \t/*\n-\t * Add every rule again (except for the one that was removed from\n+\t * Add every rule again (except for the ones that were removed from\n \t * the rules table).\n \t */\n-\tfor (i = 0; i < lpm->used_rules; i++) {\n-\t\trte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,\n-\t\t\t\tlpm->rules_tbl[i].next_hop);\n-\t}\n+\trecreate_lpm(lpm);\n \n \treturn 0;\n }\n \n /*\n- * Deletes a group of rules\n+ * Delete all rules from the LPM table.\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+void\n+rte_lpm6_delete_all(struct rte_lpm6 *lpm)\n {\n-\tint32_t rule_to_delete_index;\n-\tuint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];\n-\tunsigned i;\n+\t/* Zero used rules counter. */\n+\tlpm->used_rules = 0;\n \n-\t/*\n-\t * Check input arguments.\n+\t/* Zero tbl24. */\n+\tmemset(lpm->tbl24, 0, sizeof(lpm->tbl24));\n+\n+\t/* Zero tbl8. */\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/* put all rules back to the mempool */\n+\trules_free(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+ */\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-\tif ((lpm == NULL) || (ips == NULL) || (depths == NULL)) {\n-\t\treturn -EINVAL;\n+\treturn (signed char)0x80 >> (depth - 1);\n+}\n+\n+/*\n+ * Find a less specific rule\n+ */\n+static struct rte_lpm6_rule*\n+rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n+{\n+\tif (depth == 1)\n+\t\treturn NULL;\n+\n+\tstruct rte_lpm6_rule *rule;\n+\tstruct rte_lpm6_rule_key rule_key;\n+\trule_key_init(&rule_key, ip, depth);\n+\tuint8_t mask;\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 % 8 */\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\trule = rule_find_with_key(lpm, &rule_key);\n+\t\tif (rule != NULL)\n+\t\t\treturn rule;\n \t}\n \n-\tfor (i = 0; i < n; i++) {\n-\t\t/* Copy the IP and mask it to avoid modifying user's input data. */\n-\t\tmemcpy(ip_masked, ips[i], RTE_LPM6_IPV6_ADDR_SIZE);\n-\t\tmask_ip(ip_masked, depths[i]);\n+\treturn NULL;\n+}\n \n-\t\t/*\n-\t\t * Find the index of the input rule, that needs to be deleted, in the\n-\t\t * rule table.\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\trule_to_delete_index = rule_find(lpm, ip_masked, depths[i]);\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/*\n-\t\t * Check if rule_to_delete_index was found. If no rule was found the\n-\t\t * function rule_find returns -ENOENT.\n-\t\t */\n-\t\tif (rule_to_delete_index < 0)\n-\t\t\tcontinue;\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-\t\t/* Delete the rule from the rule table. */\n-\t\trule_delete(lpm, rule_to_delete_index);\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-\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+\tassert(owner_entry->ext_entry == 1);\n \n-\t/*\n-\t * Add every rule again (except for the ones that were removed from\n-\t * the rules table).\n-\t */\n-\tfor (i = 0; i < lpm->used_rules; i++) {\n-\t\trte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,\n-\t\t\t\tlpm->rules_tbl[i].next_hop);\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-\treturn 0;\n+\t/* return the table to the pool */\n+\ttbl8_put(lpm, tbl_ind);\n }\n \n /*\n- * Delete all rules from the LPM table.\n+ * Deletes a rule\n */\n-void\n-rte_lpm6_delete_all(struct rte_lpm6 *lpm)\n+int\n+rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)\n {\n-\t/* Zero used rules counter. */\n-\tlpm->used_rules = 0;\n+\t/* Check input arguments. */\n+\tif ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))\n+\t\treturn -EINVAL;\n \n-\t/* Zero next tbl8 index. */\n-\tlpm->next_tbl8 = 0;\n+\t/* Copy the IP and mask it to avoid modifying user's input data. */\n+\tuint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];\n+\tip6_copy_addr(masked_ip, ip);\n+\tip6_mask_addr(masked_ip, depth);\n \n-\t/* Zero tbl24. */\n-\tmemset(lpm->tbl24, 0, sizeof(lpm->tbl24));\n+\t/* Delete the rule from the rule table. */\n+\tint ret = rule_delete(lpm, masked_ip, depth);\n+\tif (ret < 0)\n+\t\treturn -ENOENT;\n \n-\t/* Zero tbl8. */\n-\tmemset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *\n-\t\t\tRTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);\n+\t/* find rule cells */\n+\tstruct rte_lpm6_tbl_entry *from, *to;\n+\tuint32_t tbl_ind;\n+\trule_find_range(lpm, masked_ip, depth, &from, &to, &tbl_ind);\n \n-\t/* Delete all rules form the rules table. */\n-\tmemset(lpm->rules_tbl, 0, sizeof(struct rte_lpm6_rule) * lpm->max_rules);\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+\tstruct rte_lpm6_rule *lsp_rule = rule_find_less_specific(lpm,\n+\t\t\tmasked_ip, depth);\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 }\ndiff --git a/lib/librte_lpm/rte_lpm6.h b/lib/librte_lpm/rte_lpm6.h\nindex 5d59ccb1f..30cb83fb3 100644\n--- a/lib/librte_lpm/rte_lpm6.h\n+++ b/lib/librte_lpm/rte_lpm6.h\n@@ -11,6 +11,7 @@\n \n #include <stdint.h>\n #include <rte_compat.h>\n+#include <rte_mempool.h>\n \n #ifdef __cplusplus\n extern \"C\" {\n", "prefixes": [] }