Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/42106/?format=api
{ "id": 42106, "url": "http://patchwork.dpdk.org/api/patches/42106/?format=api", "web_url": "http://patchwork.dpdk.org/project/dpdk/patch/20180702164222.A2C911B500@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": "<20180702164222.A2C911B500@dpdk.org>", "list_archive_url": "https://inbox.dpdk.org/dev/20180702164222.A2C911B500@dpdk.org", "date": "2018-07-02T16:42:11", "name": "[v2] librte_lpm: Improve performance of the delete and add functions", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "0515c91cf16a7a895dd4b9840e47653169f815a7", "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/20180702164222.A2C911B500@dpdk.org/mbox/", "series": [ { "id": 360, "url": "http://patchwork.dpdk.org/api/series/360/?format=api", "web_url": "http://patchwork.dpdk.org/project/dpdk/list/?series=360", "date": "2018-07-02T16:42:11", "name": "[v2] librte_lpm: Improve performance of the delete and add functions", "version": 2, "mbox": "http://patchwork.dpdk.org/series/360/mbox/" } ], "comments": "http://patchwork.dpdk.org/api/patches/42106/comments/", "check": "fail", "checks": "http://patchwork.dpdk.org/api/patches/42106/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 A2C911B500;\n\tMon, 2 Jul 2018 18:42:22 +0200 (CEST)", "from relay-out4.mail.masterhost.ru (relay-out4.mail.masterhost.ru\n\t[83.222.12.14]) by dpdk.org (Postfix) with ESMTP id 31B1F1B500\n\tfor <dev@dpdk.org>; Mon, 2 Jul 2018 18:42:21 +0200 (CEST)", "from [37.139.80.50] (helo=h5.therouter.net)\n\tby relay4.mail.masterhost.ru with esmtpa \n\tenvelope from <alex@therouter.net>\n\tauthenticated with alex@therouter.net\n\tmessage id 1fa1tz-0007W0-Rj; Mon, 02 Jul 2018 19:42:13 +0300", "by h5.therouter.net (sSMTP sendmail emulation);\n\tMon, 02 Jul 2018 19:42:11 +0300" ], "From": "\"Alex Kiselev\" <alex@therouter.net>", "Date": "Mon, 02 Jul 2018 19:42:11 +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": "126449 [Jul 02 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 v2] 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": "<20180702164222.A2C911B500@dpdk.org>" }, "content": "There are 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 | 1073 ++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 816 insertions(+), 257 deletions(-)", "diff": "diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c\nindex 149677eb1..438db0831 100644\n--- a/lib/librte_lpm/rte_lpm6.c\n+++ b/lib/librte_lpm/rte_lpm6.c\n@@ -21,6 +21,10 @@\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 <rte_mempool.h>\n+#include <assert.h>\n \n #include \"rte_lpm6.h\"\n \n@@ -37,6 +41,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 +77,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 +101,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 +123,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 +259,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 +274,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 +352,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 +360,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 +379,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 +468,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 +563,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 +588,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 +690,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 +716,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 +738,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 +755,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 +781,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 +802,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 +832,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 +858,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 +916,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 +943,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 +1021,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 +1058,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 +1133,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 +1160,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, masked_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 +1188,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 }\n", "prefixes": [ "v2" ] }