Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/134046/?format=api
{ "id": 134046, "url": "http://patches.dpdk.org/api/patches/134046/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/0d975b44d6d443abaa00c02a1967c6b7@verisign.com/", "project": { "id": 1, "url": "http://patches.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": "<0d975b44d6d443abaa00c02a1967c6b7@verisign.com>", "list_archive_url": "https://inbox.dpdk.org/dev/0d975b44d6d443abaa00c02a1967c6b7@verisign.com", "date": "2023-11-09T23:11:04", "name": "[v2] lpm: improve performance with copious IPv4 peering routes", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "c2f9c2b03b26f172f4e25de15b6a0f0ee30a5550", "submitter": { "id": 3113, "url": "http://patches.dpdk.org/api/people/3113/?format=api", "name": "Warrington, Jeffrey", "email": "jwarrington@verisign.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/0d975b44d6d443abaa00c02a1967c6b7@verisign.com/mbox/", "series": [ { "id": 30230, "url": "http://patches.dpdk.org/api/series/30230/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=30230", "date": "2023-11-09T23:11:04", "name": "[v2] lpm: improve performance with copious IPv4 peering routes", "version": 2, "mbox": "http://patches.dpdk.org/series/30230/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/134046/comments/", "check": "fail", "checks": "http://patches.dpdk.org/api/patches/134046/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@inbox.dpdk.org", "Delivered-To": "patchwork@inbox.dpdk.org", "Received": [ "from mails.dpdk.org (mails.dpdk.org [217.70.189.124])\n\tby inbox.dpdk.org (Postfix) with ESMTP id 756A2432EC;\n\tFri, 10 Nov 2023 00:11:07 +0100 (CET)", "from mails.dpdk.org (localhost [127.0.0.1])\n\tby mails.dpdk.org (Postfix) with ESMTP id 63766402E4;\n\tFri, 10 Nov 2023 00:11:07 +0100 (CET)", "from mail4.verisign.com (mail4.verisign.com [69.58.187.30])\n by mails.dpdk.org (Postfix) with ESMTP id AF4ED40268\n for <dev@dpdk.org>; Fri, 10 Nov 2023 00:11:05 +0100 (CET)", "from BRN1WNEX02.vcorp.ad.vrsn.com (10.173.153.49) by\n BRN1WNEX01.vcorp.ad.vrsn.com (10.173.153.48) with Microsoft SMTP Server\n (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id\n 15.1.2507.34; Thu, 9 Nov 2023 18:11:04 -0500", "from BRN1WNEX02.vcorp.ad.vrsn.com ([10.173.153.49]) by\n BRN1WNEX02.vcorp.ad.vrsn.com ([10.173.153.49]) with mapi id 15.01.2507.034;\n Thu, 9 Nov 2023 18:11:04 -0500" ], "DKIM-Signature": "v=1; a=rsa-sha256; c=simple/simple;\n d=verisign.com; l=19618; q=dns/txt; s=VRSN; t=1699571466;\n h=from:to:subject:date:message-id:\n content-transfer-encoding:mime-version;\n bh=X2tRkAehln1RNk67pauCmWwdiRABw/sIxKjV3bES0tg=;\n b=Pdh6cOXWpzyiZdSbPE807UQ680xqQcWhlRU6U/wSNNgxh/9l1uYI1ZN0\n ynu+9p85YlL2gwrncwm8+pVU+JFqhAM+rujaPqUDhlEGtpEP2j7jexfMo\n KwNb3U7OMowbQcgkOwS75rqShl8UkSxmpjKlXL5giMwvxPJkBhifaN35D\n DSuo3uKRUzePU/4KSiG/M5p0khN5thWdKHQ3OPiVzxRYE2/lkfs86ksId\n Cmoka7r4Pmezqjfp/LZ3u5OU5wK3xpaEMoIWbqfberqDuCj0WfzR+oEKn\n LpMxMLo5mk5ovT+qxXMYh9WJF7iJm78B/3j87qjI9dsIqMtG2dN1hNs2R A==;", "IronPort-Data": "A9a23:tMI1P6+04a6+l9MVW6E9DrUD0X+TJUtcMsCJ2f8bNWPcYEJGY0x3n\n GccWTqCMq2KZGb3c98gaNni/RtVup7Vx4U3SFFr+30xFiIbosf7XtnIdU2Y0wF+jCHgZBk+s\n 5hBMImowOQcFCK0SsKFa+C5xZVE/fjUAOC6UoYoAwgpLSd8UiAtlBl/rOAwh49skLCRDhiE0\n T/Ii5S31GSNhXgsaQr414rZ8Ek05a2q6WtF1rADTasjUGH2xiF94K03ePnZw0vQGuF8AuO8T\n uDf+7C1lkuxE8AFU47Nfh7TKyXmc5aKVeS8oiM+t5uK23CukhcPPpMTb5LwX28M0mnUwIoho\n Dl6ncfYpQ8BZsUgkcxDC0UIS3kW0aduoNcrKlDn2SCfItGvn9IBDJyCAWlvVbD09NqbDkkfz\n N1DMCIILSyvuNOv5Jyrbehvn+oseZyD0IM34hmMzBnzN9B/frbuc/2To8FT2y0owMlCW+jEf\n MxfYj1qBPjCS0QXfA5IU9Rnwbzu2imXnz5w8Tp5oYI1/GHJ1g1336TqNvLLd8aLXsRamACTo\n WeuE2HRWExGboHElmDtHnSEjdLVsBq4Sa0oEZq71aFEqVuPnS8jMUhDPbe8ibzj4qKkYPpTJ\n lI89jIiru417kPDczXmdxeipiebuBMMA4MVCPMgrgSM0e/e5ECTHG5dCCBbc9pgv8gzLdA36\n mK0cxrSLWQHmNWopbi1r994cRva1fApEFI/", "IronPort-HdrOrdr": "A9a23:PBC2GqmwVSybZ7r4a9dlyhatGFfpDfIT3DAbv31ZSRFFG/Fwz/\n re/8jzpiWE6gr5P0tQ4OxoWZPwJ080mqQV3WB8B92ftWrdyROVxeNZjbcKqgeIc0bDH4VmuZ\n uIBpIRNDSGNzdHZKjBjTVQWOxQpeVvuJrY4ds24U0dKj1XVw==", "X-Talos-CUID": "\n 9a23:bgW9qmjXpZCcE4soRxN7JxXSjDJuI0T8l2/CJgyEJVlYUZm7WXiR+7pKnJ87", "X-Talos-MUID": "9a23:/zLYIQntHqcVoi85zUsRdnppCd1F2ue/J3oItpYl5OetMzAreAek2WE=", "X-IronPort-AV": "E=Sophos;i=\"6.03,290,1694750400\"; d=\"scan'208\";a=\"25425372\"", "From": "\"Warrington, Jeffrey\" <jwarrington@verisign.com>", "To": "\"'dev@dpdk.org'\" <dev@dpdk.org>", "Subject": "[PATCH v2] lpm: improve performance with copious IPv4 peering routes", "Thread-Topic": "[PATCH v2] lpm: improve performance with copious IPv4 peering\n routes", "Thread-Index": "AdoTYeSpaEx7h22XQWehjM5aEQNmGg==", "Date": "Thu, 9 Nov 2023 23:11:04 +0000", "Message-ID": "<0d975b44d6d443abaa00c02a1967c6b7@verisign.com>", "Accept-Language": "en-US", "Content-Language": "en-US", "X-MS-Has-Attach": "", "X-MS-TNEF-Correlator": "", "x-originating-ip": "[10.170.148.18]", "Content-Type": "text/plain; charset=\"us-ascii\"", "Content-Transfer-Encoding": "quoted-printable", "MIME-Version": "1.0", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.29", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n <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 <mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org" }, "content": "Minimize the performance impact of large numbers of BGP peering\nroutes by updating LPM's IPv4 code to use a hash like the IPv6 code.\n\nCo-authored-by: Julien Charbon <jcharbon@verisign.com>\nSigned-off-by: Julien Charbon <jcharbon@verisign.com>\nSigned-off-by: Jeff Warrington <jwarrington@verisign.com>\nCo-authored-by: Nicolas Witkowski <nwitkowski@verisign.com>\nSigned-off-by: Nicolas Witkowski <nwitkowski@verisign.com>\nCo-authored-by: Rohit Gupta <rogupta@verisign.com>\nSigned-off-by: Rohit Gupta <rogupta@verisign.com>\n---\n lib/lpm/rte_lpm.c | 306 ++++++++++++++++++++++------------------------\n lib/lpm/rte_lpm.h | 6 +\n 2 files changed, 149 insertions(+), 163 deletions(-)", "diff": "diff --git a/lib/lpm/rte_lpm.c b/lib/lpm/rte_lpm.c\nindex cdcd1b7f9e..c951be8946 100644\n--- a/lib/lpm/rte_lpm.c\n+++ b/lib/lpm/rte_lpm.c\n@@ -16,9 +16,13 @@\n #include <rte_string_fns.h>\n #include <rte_errno.h>\n #include <rte_tailq.h>\n+#include <rte_hash.h>\n+#include <rte_jhash.h>\n \n #include \"rte_lpm.h\"\n \n+#define RULE_HASH_TABLE_EXTRA_SPACE 64\n+\n TAILQ_HEAD(rte_lpm_list, rte_tailq_entry);\n \n static struct rte_tailq_elem rte_lpm_tailq = {\n@@ -53,10 +57,11 @@ struct __rte_lpm {\n \t/* LPM metadata. */\n \tchar name[RTE_LPM_NAMESIZE]; /**< Name of the lpm. */\n \tuint32_t max_rules; /**< Max. balanced rules per lpm. */\n+\tuint32_t used_rules; /**< Used rules so far. */\n \tuint32_t number_tbl8s; /**< Number of tbl8s. */\n \t/**< Rule info table. */\n \tstruct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH];\n-\tstruct rte_lpm_rule *rules_tbl; /**< LPM rules. */\n+\tstruct rte_hash *rules_tbl; /**< LPM rules. */\n \n \t/* RCU config. */\n \tstruct rte_rcu_qsbr *v;\t\t/* RCU QSBR variable. */\n@@ -76,6 +81,47 @@ struct __rte_lpm {\n #define VERIFY_DEPTH(depth)\n #endif\n \n+/*\n+ * LPM rule hash function\n+ *\n+ * It's used as a hash function for the rte_hash\n+ *\tcontaining rules\n+ */\n+static inline uint32_t\n+rule_hash(const void *data, __rte_unused uint32_t data_len,\n+\t\t uint32_t init_val)\n+{\n+\treturn rte_jhash(data, sizeof(struct rte_lpm_rule_key), init_val);\n+}\n+\n+static inline void\n+rule_key_init(struct rte_lpm_rule_key *key, uint32_t ip, uint8_t depth)\n+{\n+\tkey->ip = ip;\n+\tkey->depth = depth;\n+}\n+\n+/* Find a rule */\n+static inline int\n+rule_find_with_key(struct rte_lpm *lpm, const struct rte_lpm_rule_key *rule_key, uint32_t *next_hop)\n+{\n+\tstruct __rte_lpm *i_lpm;\n+\tuint64_t hash_val;\n+\tint ret;\n+\n+\ti_lpm = container_of(lpm, struct __rte_lpm, lpm);\n+\n+\t/* lookup for a rule */\n+\tret = rte_hash_lookup_data(i_lpm->rules_tbl, (const void *) rule_key,\n+\t\t(void **) &hash_val);\n+\tif (ret >= 0) {\n+\t\t*next_hop = (uint32_t) hash_val;\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n /*\n * Converts a given depth value to its corresponding mask value.\n *\n@@ -150,8 +196,9 @@ rte_lpm_create(const char *name, int socket_id,\n \tstruct __rte_lpm *i_lpm;\n \tstruct rte_lpm *lpm = NULL;\n \tstruct rte_tailq_entry *te;\n-\tuint32_t mem_size, rules_size, tbl8s_size;\n+\tuint32_t mem_size, tbl8s_size;\n \tstruct rte_lpm_list *lpm_list;\n+\tstruct rte_hash *rules_tbl = NULL;\n \n \tlpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);\n \n@@ -164,7 +211,25 @@ rte_lpm_create(const char *name, int socket_id,\n \t\treturn NULL;\n \t}\n \n-\tsnprintf(mem_name, sizeof(mem_name), \"LPM_%s\", name);\n+\tsnprintf(mem_name, sizeof(mem_name), \"LRHv4_%s\", name);\n+\tstruct rte_hash_parameters rule_hash_tbl_params = {\n+\t\t.entries = config->max_rules * 1.2 + RULE_HASH_TABLE_EXTRA_SPACE,\n+\t\t.key_len = sizeof(struct rte_lpm_rule_key),\n+\t\t.hash_func = rule_hash,\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+\n+\t\treturn NULL;\n+\t}\n \n \trte_mcfg_tailq_write_lock();\n \n@@ -182,7 +247,6 @@ rte_lpm_create(const char *name, int socket_id,\n \n \t/* Determine the amount of memory to allocate. */\n \tmem_size = sizeof(*i_lpm);\n-\trules_size = sizeof(struct rte_lpm_rule) * config->max_rules;\n \ttbl8s_size = sizeof(struct rte_lpm_tbl_entry) *\n \t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s;\n \n@@ -204,18 +268,6 @@ rte_lpm_create(const char *name, int socket_id,\n \t\tgoto exit;\n \t}\n \n-\ti_lpm->rules_tbl = rte_zmalloc_socket(NULL,\n-\t\t\t(size_t)rules_size, RTE_CACHE_LINE_SIZE, socket_id);\n-\n-\tif (i_lpm->rules_tbl == NULL) {\n-\t\tRTE_LOG(ERR, LPM, \"LPM rules_tbl memory allocation failed\\n\");\n-\t\trte_free(i_lpm);\n-\t\ti_lpm = NULL;\n-\t\trte_free(te);\n-\t\trte_errno = ENOMEM;\n-\t\tgoto exit;\n-\t}\n-\n \ti_lpm->lpm.tbl8 = rte_zmalloc_socket(NULL,\n \t\t\t(size_t)tbl8s_size, RTE_CACHE_LINE_SIZE, socket_id);\n \n@@ -230,6 +282,7 @@ rte_lpm_create(const char *name, int socket_id,\n \t}\n \n \t/* Save user arguments. */\n+\ti_lpm->rules_tbl = rules_tbl;\n \ti_lpm->max_rules = config->max_rules;\n \ti_lpm->number_tbl8s = config->number_tbl8s;\n \tstrlcpy(i_lpm->name, name, sizeof(i_lpm->name));\n@@ -277,7 +330,7 @@ rte_lpm_free(struct rte_lpm *lpm)\n \tif (i_lpm->dq != NULL)\n \t\trte_rcu_qsbr_dq_delete(i_lpm->dq);\n \trte_free(i_lpm->lpm.tbl8);\n-\trte_free(i_lpm->rules_tbl);\n+\trte_hash_free(i_lpm->rules_tbl);\n \trte_free(i_lpm);\n \trte_free(te);\n }\n@@ -359,106 +412,64 @@ rte_lpm_rcu_qsbr_add(struct rte_lpm *lpm, struct rte_lpm_rcu_config *cfg)\n * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.\n */\n static int32_t\n-rule_add(struct __rte_lpm *i_lpm, uint32_t ip_masked, uint8_t depth,\n-\tuint32_t next_hop)\n+rule_add(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, uint32_t next_hop)\n {\n-\tuint32_t rule_gindex, rule_index, last_rule;\n-\tint i;\n+\tint ret, rule_exist;\n+\tstruct rte_lpm_rule_key rule_key;\n+\tuint32_t unused;\n \n \tVERIFY_DEPTH(depth);\n \n-\t/* Scan through rule group to see if rule already exists. */\n-\tif (i_lpm->rule_info[depth - 1].used_rules > 0) {\n+\t/* init a rule key */\n+\trule_key_init(&rule_key, ip_masked, depth);\n \n-\t\t/* rule_gindex stands for rule group index. */\n-\t\trule_gindex = i_lpm->rule_info[depth - 1].first_rule;\n-\t\t/* Initialise rule_index to point to start of rule group. */\n-\t\trule_index = rule_gindex;\n-\t\t/* Last rule = Last used rule in this rule group. */\n-\t\tlast_rule = rule_gindex + i_lpm->rule_info[depth - 1].used_rules;\n+\t/* Scan through rule list to see if rule already exists. */\n+\trule_exist = rule_find_with_key(lpm, &rule_key, &unused);\n \n-\t\tfor (; rule_index < last_rule; rule_index++) {\n+\tstruct __rte_lpm *i_lpm = container_of(lpm, struct __rte_lpm, lpm);\n \n-\t\t\t/* If rule already exists update next hop and return. */\n-\t\t\tif (i_lpm->rules_tbl[rule_index].ip == ip_masked) {\n+\tif (!rule_exist && i_lpm->used_rules == i_lpm->max_rules)\n+\t\treturn -ENOSPC;\n \n-\t\t\t\tif (i_lpm->rules_tbl[rule_index].next_hop\n-\t\t\t\t\t\t== next_hop)\n-\t\t\t\t\treturn -EEXIST;\n-\t\t\t\ti_lpm->rules_tbl[rule_index].next_hop = next_hop;\n+\tret = rte_hash_add_key_data(i_lpm->rules_tbl, &rule_key,\n+\t\t(void *)(uintptr_t) next_hop);\n \n-\t\t\t\treturn rule_index;\n-\t\t\t}\n-\t\t}\n-\n-\t\tif (rule_index == i_lpm->max_rules)\n-\t\t\treturn -ENOSPC;\n-\t} else {\n-\t\t/* Calculate the position in which the rule will be stored. */\n-\t\trule_index = 0;\n-\n-\t\tfor (i = depth - 1; i > 0; i--) {\n-\t\t\tif (i_lpm->rule_info[i - 1].used_rules > 0) {\n-\t\t\t\trule_index = i_lpm->rule_info[i - 1].first_rule\n-\t\t\t\t\t\t+ i_lpm->rule_info[i - 1].used_rules;\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t}\n-\t\tif (rule_index == i_lpm->max_rules)\n-\t\t\treturn -ENOSPC;\n-\n-\t\ti_lpm->rule_info[depth - 1].first_rule = rule_index;\n-\t}\n-\n-\t/* Make room for the new rule in the array. */\n-\tfor (i = RTE_LPM_MAX_DEPTH; i > depth; i--) {\n-\t\tif (i_lpm->rule_info[i - 1].first_rule\n-\t\t\t\t+ i_lpm->rule_info[i - 1].used_rules == i_lpm->max_rules)\n-\t\t\treturn -ENOSPC;\n-\n-\t\tif (i_lpm->rule_info[i - 1].used_rules > 0) {\n-\t\t\ti_lpm->rules_tbl[i_lpm->rule_info[i - 1].first_rule\n-\t\t\t\t+ i_lpm->rule_info[i - 1].used_rules]\n-\t\t\t\t\t= i_lpm->rules_tbl[i_lpm->rule_info[i - 1].first_rule];\n-\t\t\ti_lpm->rule_info[i - 1].first_rule++;\n-\t\t}\n-\t}\n-\n-\t/* Add the new rule. */\n-\ti_lpm->rules_tbl[rule_index].ip = ip_masked;\n-\ti_lpm->rules_tbl[rule_index].next_hop = next_hop;\n+\tif (ret < 0)\n+\t\treturn ret;\n \n \t/* Increment the used rules counter for this rule group. */\n-\ti_lpm->rule_info[depth - 1].used_rules++;\n+\tif (!rule_exist) {\n+\t\ti_lpm->rule_info[depth - 1].used_rules++;\n+\t\ti_lpm->used_rules++;\n+\t\treturn 1;\n+\t}\n \n-\treturn rule_index;\n+\treturn 0;\n }\n \n /*\n * Delete a rule from the rule table.\n * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.\n */\n-static void\n-rule_delete(struct __rte_lpm *i_lpm, int32_t rule_index, uint8_t depth)\n+static int\n+rule_delete(struct __rte_lpm *i_lpm, int32_t ip, uint8_t depth)\n {\n-\tint i;\n+\tint ret;\n+\tstruct rte_lpm_rule_key rule_key;\n \n \tVERIFY_DEPTH(depth);\n \n-\ti_lpm->rules_tbl[rule_index] =\n-\t\t\ti_lpm->rules_tbl[i_lpm->rule_info[depth - 1].first_rule\n-\t\t\t+ i_lpm->rule_info[depth - 1].used_rules - 1];\n+\trule_key_init(&rule_key, ip, depth);\n \n-\tfor (i = depth; i < RTE_LPM_MAX_DEPTH; i++) {\n-\t\tif (i_lpm->rule_info[i].used_rules > 0) {\n-\t\t\ti_lpm->rules_tbl[i_lpm->rule_info[i].first_rule - 1] =\n-\t\t\t\t\ti_lpm->rules_tbl[i_lpm->rule_info[i].first_rule\n-\t\t\t\t\t\t+ i_lpm->rule_info[i].used_rules - 1];\n-\t\t\ti_lpm->rule_info[i].first_rule--;\n-\t\t}\n+\t/* delete the rule */\n+\tret = rte_hash_del_key(i_lpm->rules_tbl, (void *) &rule_key);\n+\n+\tif (ret >= 0) {\n+\t\ti_lpm->rule_info[depth - 1].used_rules--;\n+\t\ti_lpm->used_rules--;\n \t}\n \n-\ti_lpm->rule_info[depth - 1].used_rules--;\n+\treturn ret;\n }\n \n /*\n@@ -466,24 +477,14 @@ rule_delete(struct __rte_lpm *i_lpm, int32_t rule_index, uint8_t depth)\n * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.\n */\n static int32_t\n-rule_find(struct __rte_lpm *i_lpm, uint32_t ip_masked, uint8_t depth)\n+rule_find(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, uint32_t *next_hop)\n {\n-\tuint32_t rule_gindex, last_rule, rule_index;\n-\n-\tVERIFY_DEPTH(depth);\n-\n-\trule_gindex = i_lpm->rule_info[depth - 1].first_rule;\n-\tlast_rule = rule_gindex + i_lpm->rule_info[depth - 1].used_rules;\n+\tstruct rte_lpm_rule_key rule_key;\n \n-\t/* Scan used rules at given depth to find rule. */\n-\tfor (rule_index = rule_gindex; rule_index < last_rule; rule_index++) {\n-\t\t/* If rule is found return the rule index. */\n-\t\tif (i_lpm->rules_tbl[rule_index].ip == ip_masked)\n-\t\t\treturn rule_index;\n-\t}\n+\t/* init a rule key */\n+\trule_key_init(&rule_key, ip_masked, depth);\n \n-\t/* If rule is not found return -EINVAL. */\n-\treturn -EINVAL;\n+\treturn rule_find_with_key(lpm, &rule_key, next_hop);\n }\n \n /*\n@@ -799,7 +800,7 @@ int\n rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n \t\tuint32_t next_hop)\n {\n-\tint32_t rule_index, status = 0;\n+\tint32_t status = 0;\n \tstruct __rte_lpm *i_lpm;\n \tuint32_t ip_masked;\n \n@@ -811,17 +812,11 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n \tip_masked = ip & depth_to_mask(depth);\n \n \t/* Add the rule to the rule table. */\n-\trule_index = rule_add(i_lpm, ip_masked, depth, next_hop);\n-\n-\t/* Skip table entries update if The rule is the same as\n-\t * the rule in the rules table.\n-\t */\n-\tif (rule_index == -EEXIST)\n-\t\treturn 0;\n+\tstatus = rule_add(lpm, ip_masked, depth, next_hop);\n \n \t/* If the is no space available for new rule return error. */\n-\tif (rule_index < 0) {\n-\t\treturn rule_index;\n+\tif (status < 0) {\n+\t\treturn status;\n \t}\n \n \tif (depth <= MAX_DEPTH_TBL24) {\n@@ -834,7 +829,7 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n \t\t * rule that was added to rule table.\n \t\t */\n \t\tif (status < 0) {\n-\t\t\trule_delete(i_lpm, rule_index, depth);\n+\t\t\trule_delete(i_lpm, ip_masked, depth);\n \n \t\t\treturn status;\n \t\t}\n@@ -850,9 +845,7 @@ int\n rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n uint32_t *next_hop)\n {\n-\tstruct __rte_lpm *i_lpm;\n \tuint32_t ip_masked;\n-\tint32_t rule_index;\n \n \t/* Check user arguments. */\n \tif ((lpm == NULL) ||\n@@ -861,44 +854,42 @@ uint32_t *next_hop)\n \t\treturn -EINVAL;\n \n \t/* Look for the rule using rule_find. */\n-\ti_lpm = container_of(lpm, struct __rte_lpm, lpm);\n \tip_masked = ip & depth_to_mask(depth);\n-\trule_index = rule_find(i_lpm, ip_masked, depth);\n \n-\tif (rule_index >= 0) {\n-\t\t*next_hop = i_lpm->rules_tbl[rule_index].next_hop;\n+\tif (rule_find(lpm, ip_masked, depth, next_hop))\n \t\treturn 1;\n-\t}\n \n \t/* If rule is not found return 0. */\n \treturn 0;\n }\n \n static int32_t\n-find_previous_rule(struct __rte_lpm *i_lpm, uint32_t ip, uint8_t depth,\n-\t\tuint8_t *sub_rule_depth)\n+find_previous_rule(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n+\tuint32_t *subrule_prev_hop, uint8_t *subrule_prev_depth)\n {\n-\tint32_t rule_index;\n \tuint32_t ip_masked;\n+\tuint32_t prev_hop;\n \tuint8_t prev_depth;\n+\tint found;\n \n \tfor (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) {\n \t\tip_masked = ip & depth_to_mask(prev_depth);\n \n-\t\trule_index = rule_find(i_lpm, ip_masked, prev_depth);\n+\t\tfound = rule_find(lpm, ip_masked, prev_depth, &prev_hop);\n \n-\t\tif (rule_index >= 0) {\n-\t\t\t*sub_rule_depth = prev_depth;\n-\t\t\treturn rule_index;\n+\t\tif (found) {\n+\t\t\t*subrule_prev_hop = prev_hop;\n+\t\t\t*subrule_prev_depth = prev_depth;\n+\t\t\treturn 1;\n \t\t}\n \t}\n \n-\treturn -1;\n+\treturn 0;\n }\n \n static int32_t\n delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n-\tuint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)\n+\tuint8_t depth, int found, uint32_t sub_rule_hop, uint8_t sub_rule_depth)\n {\n #define group_idx next_hop\n \tuint32_t tbl24_range, tbl24_index, tbl8_group_index, tbl8_index, i, j;\n@@ -912,7 +903,7 @@ delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n \t * Firstly check the sub_rule_index. A -1 indicates no replacement rule\n \t * and a positive number indicates a sub_rule_index.\n \t */\n-\tif (sub_rule_index < 0) {\n+\tif (!found) {\n \t\t/*\n \t\t * If no replacement rule exists then invalidate entries\n \t\t * associated with this rule.\n@@ -949,7 +940,7 @@ delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n \t\t */\n \n \t\tstruct rte_lpm_tbl_entry new_tbl24_entry = {\n-\t\t\t.next_hop = i_lpm->rules_tbl[sub_rule_index].next_hop,\n+\t\t\t.next_hop = sub_rule_hop,\n \t\t\t.valid = VALID,\n \t\t\t.valid_group = 0,\n \t\t\t.depth = sub_rule_depth,\n@@ -959,8 +950,7 @@ delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n \t\t\t.valid = VALID,\n \t\t\t.valid_group = VALID,\n \t\t\t.depth = sub_rule_depth,\n-\t\t\t.next_hop = i_lpm->rules_tbl\n-\t\t\t[sub_rule_index].next_hop,\n+\t\t\t.next_hop = sub_rule_hop,\n \t\t};\n \n \t\tfor (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {\n@@ -1052,7 +1042,7 @@ tbl8_recycle_check(struct rte_lpm_tbl_entry *tbl8,\n \n static int32_t\n delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n-\tuint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)\n+\tuint8_t depth, int found, uint32_t sub_rule_hop, uint8_t sub_rule_depth)\n {\n #define group_idx next_hop\n \tuint32_t tbl24_index, tbl8_group_index, tbl8_group_start, tbl8_index,\n@@ -1071,7 +1061,7 @@ delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n \ttbl8_index = tbl8_group_start + (ip_masked & 0xFF);\n \ttbl8_range = depth_to_range(depth);\n \n-\tif (sub_rule_index < 0) {\n+\tif (!found) {\n \t\t/*\n \t\t * Loop through the range of entries on tbl8 for which the\n \t\t * rule_to_delete must be removed or modified.\n@@ -1086,7 +1076,7 @@ delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n \t\t\t.valid = VALID,\n \t\t\t.depth = sub_rule_depth,\n \t\t\t.valid_group = i_lpm->lpm.tbl8[tbl8_group_start].valid_group,\n-\t\t\t.next_hop = i_lpm->rules_tbl[sub_rule_index].next_hop,\n+\t\t\t.next_hop = sub_rule_hop,\n \t\t};\n \n \t\t/*\n@@ -1142,9 +1132,10 @@ delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,\n int\n rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)\n {\n-\tint32_t rule_to_delete_index, sub_rule_index;\n+\tint32_t found;\n \tstruct __rte_lpm *i_lpm;\n \tuint32_t ip_masked;\n+\tuint32_t sub_rule_hop;\n \tuint8_t sub_rule_depth;\n \t/*\n \t * Check input arguments. Note: IP must be a positive integer of 32\n@@ -1157,21 +1148,9 @@ rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)\n \ti_lpm = container_of(lpm, struct __rte_lpm, lpm);\n \tip_masked = ip & depth_to_mask(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(i_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 -EINVAL.\n-\t */\n-\tif (rule_to_delete_index < 0)\n-\t\treturn -EINVAL;\n-\n \t/* Delete the rule from the rule table. */\n-\trule_delete(i_lpm, rule_to_delete_index, depth);\n+\tif (rule_delete(i_lpm, ip_masked, depth) < 0)\n+\t\treturn -EINVAL;\n \n \t/*\n \t * Find rule to replace the rule_to_delete. If there is no rule to\n@@ -1179,18 +1158,18 @@ rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)\n \t * entries associated with this rule.\n \t */\n \tsub_rule_depth = 0;\n-\tsub_rule_index = find_previous_rule(i_lpm, ip, depth, &sub_rule_depth);\n+\tfound = find_previous_rule(lpm, ip, depth, &sub_rule_hop, &sub_rule_depth);\n \n \t/*\n \t * If the input depth value is less than 25 use function\n \t * delete_depth_small otherwise use delete_depth_big.\n \t */\n \tif (depth <= MAX_DEPTH_TBL24) {\n-\t\treturn delete_depth_small(i_lpm, ip_masked, depth,\n-\t\t\t\tsub_rule_index, sub_rule_depth);\n-\t} else { /* If depth > MAX_DEPTH_TBL24 */\n-\t\treturn delete_depth_big(i_lpm, ip_masked, depth, sub_rule_index,\n-\t\t\t\tsub_rule_depth);\n+\t\treturn delete_depth_small(i_lpm, ip_masked, depth, found,\n+\t\t\t\tsub_rule_hop, sub_rule_depth);\n+\t} else {\n+\t\treturn delete_depth_big(i_lpm, ip_masked, depth, found,\n+\t\t\t\tsub_rule_hop, sub_rule_depth);\n \t}\n }\n \n@@ -1205,6 +1184,7 @@ rte_lpm_delete_all(struct rte_lpm *lpm)\n \ti_lpm = container_of(lpm, struct __rte_lpm, lpm);\n \t/* Zero rule information. */\n \tmemset(i_lpm->rule_info, 0, sizeof(i_lpm->rule_info));\n+\ti_lpm->used_rules = 0;\n \n \t/* Zero tbl24. */\n \tmemset(i_lpm->lpm.tbl24, 0, sizeof(i_lpm->lpm.tbl24));\n@@ -1214,5 +1194,5 @@ rte_lpm_delete_all(struct rte_lpm *lpm)\n \t\t\t* RTE_LPM_TBL8_GROUP_NUM_ENTRIES * i_lpm->number_tbl8s);\n \n \t/* Delete all rules form the rules table. */\n-\tmemset(i_lpm->rules_tbl, 0, sizeof(i_lpm->rules_tbl[0]) * i_lpm->max_rules);\n+\trte_hash_reset(i_lpm->rules_tbl);\n }\ndiff --git a/lib/lpm/rte_lpm.h b/lib/lpm/rte_lpm.h\nindex 75e27ff164..605445f3a7 100644\n--- a/lib/lpm/rte_lpm.h\n+++ b/lib/lpm/rte_lpm.h\n@@ -108,6 +108,12 @@ struct rte_lpm_tbl_entry {\n \n #endif\n \n+/** Rules tbl entry key. */\n+struct rte_lpm_rule_key {\n+\tuint32_t ip; /**< Rule IP address. */\n+\tuint32_t depth; /**< Rule depth. */\n+};\n+\n /** LPM configuration structure. */\n struct rte_lpm_config {\n \tuint32_t max_rules; /**< Max number of rules. */\n", "prefixes": [ "v2" ] }