Patch Detail

HTTP 200 OK
Allow: GET, PUT, PATCH, HEAD, OPTIONS
Content-Type: application/json
Vary: Accept

{
    "id": 7981,
    "url": "https://patches.dpdk.org/api/patches/7981/?format=api",
    "web_url": "https://patches.dpdk.org/project/dpdk/patch/20151023125906.36fd3856@xeon-e3/",
    "project": {
        "id": 1,
        "url": "https://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": "<20151023125906.36fd3856@xeon-e3>",
    "list_archive_url": "https://inbox.dpdk.org/dev/20151023125906.36fd3856@xeon-e3",
    "date": "2015-10-23T19:59:06",
    "name": "[dpdk-dev,v1,0/3] lpm: increase number of next hops for lpm (ipv4)",
    "commit_ref": null,
    "pull_url": null,
    "state": "not-applicable",
    "archived": true,
    "hash": "268baa5ec363694e98575c8b91f4e1371ec3847f",
    "submitter": {
        "id": 27,
        "url": "https://patches.dpdk.org/api/people/27/?format=api",
        "name": "Stephen Hemminger",
        "email": "stephen@networkplumber.org"
    },
    "delegate": null,
    "mbox": "https://patches.dpdk.org/project/dpdk/patch/20151023125906.36fd3856@xeon-e3/mbox/",
    "series": [],
    "comments": "https://patches.dpdk.org/api/patches/7981/comments/",
    "check": "pending",
    "checks": "https://patches.dpdk.org/api/patches/7981/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 [IPv6:::1])\n\tby dpdk.org (Postfix) with ESMTP id 3815C5A1F;\n\tFri, 23 Oct 2015 21:59:01 +0200 (CEST)",
            "from mail-pa0-f50.google.com (mail-pa0-f50.google.com\n\t[209.85.220.50]) by dpdk.org (Postfix) with ESMTP id D3E29592B\n\tfor <dev@dpdk.org>; Fri, 23 Oct 2015 21:58:59 +0200 (CEST)",
            "by pacfv9 with SMTP id fv9so132230619pac.3\n\tfor <dev@dpdk.org>; Fri, 23 Oct 2015 12:58:59 -0700 (PDT)",
            "from xeon-e3 (static-50-53-82-155.bvtn.or.frontiernet.net.\n\t[50.53.82.155]) by smtp.gmail.com with ESMTPSA id\n\txm4sm20469280pab.27.2015.10.23.12.58.58\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);\n\tFri, 23 Oct 2015 12:58:58 -0700 (PDT)"
        ],
        "X-Google-DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20130820;\n\th=x-gm-message-state:date:from:to:cc:subject:message-id:in-reply-to\n\t:references:mime-version:content-type:content-transfer-encoding;\n\tbh=E17LhrnyW24m2xyJ0iCL6sG7FiXk+vJ2JkWJHHbn8Rs=;\n\tb=EeefJ6/GytlZnGcR+pSNwZ40H+7su0G/bDvBmPntfCxC7SMWgunUYC5WjdXe7zIE6E\n\t5ZFGw0sYIc2URK8GgsbTUOEKBCydI2GO80oB5QyaQS1WuoexhF4f6Cw/6V7M6W926FZG\n\t6IrKfn+0qtf3oj02LDBjnltq+t6th58dhGlrA0B1LBSmX38Rzh8DxPWnD4YJP1KfbzNA\n\t+UVBjdIyIg9GHNEt8lq2aQff9k9I+oJ83xCRktZUTAusEs6JbWT1+HnEJPOto45/iVy2\n\t0wnaGc9jLTA1TbYh1qfFD4qCSm8yxadkM7t0xYwZNNG48+DKUca2ga99tjeAmcKPcdSL\n\tDjqg==",
        "X-Gm-Message-State": "ALoCoQn6w2YoGf3OwtvPX318jK1AJvDDfm3YUtCNt9vQLM7zJU1MQh2xh3yy3DMGVtSPHSaYuW+X",
        "X-Received": "by 10.68.65.37 with SMTP id u5mr25741794pbs.76.1445630338943;\n\tFri, 23 Oct 2015 12:58:58 -0700 (PDT)",
        "Date": "Fri, 23 Oct 2015 12:59:06 -0700",
        "From": "Stephen Hemminger <stephen@networkplumber.org>",
        "To": "Matthew Hall <mhall@mhcomputing.net>",
        "Message-ID": "<20151023125906.36fd3856@xeon-e3>",
        "In-Reply-To": "<20151023183811.GA11859@mhcomputing.net>",
        "References": "<1445608311-8092-1-git-send-email-michalx.k.jastrzebski@intel.com>\n\t<20151023162033.GA10036@mhcomputing.net>\n\t<20151023093305.2e971298@xeon-e3>\n\t<20151023183811.GA11859@mhcomputing.net>",
        "MIME-Version": "1.0",
        "Content-Type": "text/plain; charset=US-ASCII",
        "Content-Transfer-Encoding": "quoted-printable",
        "Cc": "dev@dpdk.org",
        "Subject": "Re: [dpdk-dev] [PATCH v1 0/3] lpm: increase number of next hops for\n\tlpm (ipv4)",
        "X-BeenThere": "dev@dpdk.org",
        "X-Mailman-Version": "2.1.15",
        "Precedence": "list",
        "List-Id": "patches and discussions about DPDK <dev.dpdk.org>",
        "List-Unsubscribe": "<http://dpdk.org/ml/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>",
        "List-Archive": "<http://dpdk.org/ml/archives/dev/>",
        "List-Post": "<mailto:dev@dpdk.org>",
        "List-Help": "<mailto:dev-request@dpdk.org?subject=help>",
        "List-Subscribe": "<http://dpdk.org/ml/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>",
        "Errors-To": "dev-bounces@dpdk.org",
        "Sender": "\"dev\" <dev-bounces@dpdk.org>"
    },
    "content": "From 9efec4571eec4db455a29773b95cf9264c046a03 Mon Sep 17 00:00:00 2001\nFrom: Stephen Hemminger <shemming@brocade.com>\nDate: Fri, 23 Oct 2015 12:55:05 -0700\nSubject: [PATCH] lpm: brocade extensions\n\nThis is a brute-force merge of the Brocade extension to LPM\nto current DPDK source tree.\n\nNo API/ABI compatibility is expected.\n  1. Allow arbitrary number of rules\n  2. Get rid of N^2 search for rule add/delete\n  3. Add route scope\n  4. Extend nexthop to 16 bits\n  5. Extend to allow for more info on delete, (callback and nexthop)\n  6. Dynamically grow /8 table (requires RCU)\n  7. Support full /0 and /32 rules\n\n---\n lib/librte_lpm/rte_lpm.c | 814 ++++++++++++++++++++++++++---------------------\n lib/librte_lpm/rte_lpm.h | 381 +++++++---------------\n 2 files changed, 567 insertions(+), 628 deletions(-)",
    "diff": "diff --git a/lib/librte_lpm/rte_lpm.c b/lib/librte_lpm/rte_lpm.c\nindex 163ba3c..ef1f0bf 100644\n--- a/lib/librte_lpm/rte_lpm.c\n+++ b/lib/librte_lpm/rte_lpm.c\n@@ -2,6 +2,7 @@\n  *   BSD LICENSE\n  *\n  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.\n+ *   Copyright(c) 2012-2015 Brocade Communications Systems\n  *   All rights reserved.\n  *\n  *   Redistribution and use in source and binary forms, with or without\n@@ -38,13 +39,15 @@\n #include <stdio.h>\n #include <errno.h>\n #include <sys/queue.h>\n+#include <bsd/sys/tree.h>\n \n #include <rte_log.h>\n #include <rte_branch_prediction.h>\n #include <rte_common.h>\n-#include <rte_memory.h>        /* for definition of RTE_CACHE_LINE_SIZE */\n+#include <rte_memory.h>               /* for definition of RTE_CACHE_LINE_SIZE */\n #include <rte_malloc.h>\n #include <rte_memzone.h>\n+#include <rte_tailq.h>\n #include <rte_eal.h>\n #include <rte_eal_memconfig.h>\n #include <rte_per_lcore.h>\n@@ -52,9 +55,25 @@\n #include <rte_errno.h>\n #include <rte_rwlock.h>\n #include <rte_spinlock.h>\n+#include <rte_debug.h>\n \n #include \"rte_lpm.h\"\n \n+#include <urcu-qsbr.h>\n+\n+/** Auto-growth of tbl8 */\n+#define RTE_LPM_TBL8_INIT_GROUPS\t256\t/* power of 2 */\n+#define RTE_LPM_TBL8_INIT_ENTRIES\t(RTE_LPM_TBL8_INIT_GROUPS * \\\n+\t\t\t\t\t RTE_LPM_TBL8_GROUP_NUM_ENTRIES)\n+/** Rule structure. */\n+struct rte_lpm_rule {\n+\tuint32_t ip;\t    /**< Rule IP address. */\n+\tuint16_t next_hop;  /**< Rule next hop. */\n+\tuint8_t  scope;\t    /**< Rule scope */\n+\tuint8_t\t reserved;\n+\tRB_ENTRY(rte_lpm_rule) link;\n+};\n+\n TAILQ_HEAD(rte_lpm_list, rte_tailq_entry);\n \n static struct rte_tailq_elem rte_lpm_tailq = {\n@@ -71,31 +90,55 @@ enum valid_flag {\n \n /* Macro to enable/disable run-time checks. */\n #if defined(RTE_LIBRTE_LPM_DEBUG)\n-#include <rte_debug.h>\n-#define VERIFY_DEPTH(depth) do {                                \\\n-\tif ((depth == 0) || (depth > RTE_LPM_MAX_DEPTH))        \\\n+#define VERIFY_DEPTH(depth) do {\t\t\t\t\\\n+\tif (depth > RTE_LPM_MAX_DEPTH)\t\t\t\t\\\n \t\trte_panic(\"LPM: Invalid depth (%u) at line %d\", \\\n-\t\t\t\t(unsigned)(depth), __LINE__);   \\\n+\t\t\t\t(unsigned)(depth), __LINE__);\t\\\n } while (0)\n #else\n #define VERIFY_DEPTH(depth)\n #endif\n \n+/* Comparison function for red-black tree nodes.\n+   \"If the first argument is smaller than the second, the function\n+    returns a value smaller than zero.\tIf they are equal, the function\n+    returns zero.  Otherwise, it should return a value greater than zero.\"\n+*/\n+static inline int rules_cmp(const struct rte_lpm_rule *r1,\n+\t\t\t    const struct rte_lpm_rule *r2)\n+{\n+\tif (r1->ip < r2->ip)\n+\t\treturn -1;\n+\telse if (r1->ip > r2->ip)\n+\t\treturn 1;\n+\telse\n+\t\treturn r1->scope - r2->scope;\n+}\n+\n+/* Satisfy old style attribute in tree.h header */\n+#ifndef __unused\n+#define __unused __attribute__ ((unused))\n+#endif\n+\n+/* Generate internal functions and make them static. */\n+RB_GENERATE_STATIC(rte_lpm_rules_tree, rte_lpm_rule, link, rules_cmp)\n+\n /*\n  * Converts a given depth value to its corresponding mask value.\n  *\n  * depth  (IN)\t\t: range = 1 - 32\n- * mask   (OUT)\t\t: 32bit mask\n+ * mask   (OUT)                : 32bit mask\n  */\n static uint32_t __attribute__((pure))\n depth_to_mask(uint8_t depth)\n {\n \tVERIFY_DEPTH(depth);\n \n-\t/* To calculate a mask start with a 1 on the left hand side and right\n-\t * shift while populating the left hand side with 1's\n-\t */\n-\treturn (int)0x80000000 >> (depth - 1);\n+\t/* per C std. shift of 32 bits is undefined */\n+\tif (depth == 0)\n+\t\treturn 0;\n+\n+\treturn ~0u << (32 - depth);\n }\n \n /*\n@@ -113,7 +156,7 @@ depth_to_range(uint8_t depth)\n \t\treturn 1 << (MAX_DEPTH_TBL24 - depth);\n \n \t/* Else if depth is greater than 24 */\n-\treturn (1 << (RTE_LPM_MAX_DEPTH - depth));\n+\treturn 1 << (32 - depth);\n }\n \n /*\n@@ -148,31 +191,28 @@ rte_lpm_find_existing(const char *name)\n  * Allocates memory for LPM object\n  */\n struct rte_lpm *\n-rte_lpm_create(const char *name, int socket_id, int max_rules,\n-\t\t__rte_unused int flags)\n+rte_lpm_create(const char *name, int socket_id)\n {\n \tchar mem_name[RTE_LPM_NAMESIZE];\n \tstruct rte_lpm *lpm = NULL;\n \tstruct rte_tailq_entry *te;\n-\tuint32_t mem_size;\n+\tunsigned int depth;\n \tstruct rte_lpm_list *lpm_list;\n \n+\t/* check that we have an initialized tail queue */\n \tlpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);\n \n-\tRTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl24_entry) != 2);\n-\tRTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl8_entry) != 2);\n+\tRTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl24_entry) != 4);\n+\tRTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl8_entry) != 4);\n \n \t/* Check user arguments. */\n-\tif ((name == NULL) || (socket_id < -1) || (max_rules == 0)){\n+\tif ((name == NULL) || (socket_id < -1)) {\n \t\trte_errno = EINVAL;\n \t\treturn NULL;\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->rules_tbl[0]) * max_rules);\n-\n \trte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);\n \n \t/* guarantee there's no existing */\n@@ -192,17 +232,33 @@ rte_lpm_create(const char *name, int socket_id, int max_rules,\n \t}\n \n \t/* Allocate memory to store the LPM data structures. */\n-\tlpm = (struct rte_lpm *)rte_zmalloc_socket(mem_name, mem_size,\n-\t\t\tRTE_CACHE_LINE_SIZE, socket_id);\n+\tlpm = rte_zmalloc_socket(mem_name, sizeof(*lpm), RTE_CACHE_LINE_SIZE,\n+\t\t\t\t socket_id);\n \tif (lpm == NULL) {\n \t\tRTE_LOG(ERR, LPM, \"LPM memory allocation failed\\n\");\n-\t\trte_free(te);\n \t\tgoto exit;\n \t}\n \n \t/* Save user arguments. */\n-\tlpm->max_rules = max_rules;\n \tsnprintf(lpm->name, sizeof(lpm->name), \"%s\", name);\n+\tlpm->socket_id = socket_id;\n+\n+\t/* Vyatta change to use red-black tree */\n+\tfor (depth = 0; depth < RTE_LPM_MAX_DEPTH; ++depth)\n+\t\tRB_INIT(&lpm->rules[depth]);\n+\n+\t/* Vyatta change to dynamically grow tbl8 */\n+\tlpm->tbl8_num_groups = RTE_LPM_TBL8_INIT_GROUPS;\n+\tlpm->tbl8_rover = RTE_LPM_TBL8_INIT_GROUPS - 1;\n+\tlpm->tbl8 = rte_calloc_socket(NULL, RTE_LPM_TBL8_INIT_ENTRIES,\n+\t\t\t\t      sizeof(struct rte_lpm_tbl8_entry),\n+\t\t\t\t      RTE_CACHE_LINE_SIZE, socket_id);\n+\tif (lpm->tbl8 == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"LPM tbl8 group allocation failed\\n\");\n+\t\trte_free(lpm);\n+\t\tlpm = NULL;\n+\t\tgoto exit;\n+\t}\n \n \tte->data = (void *) lpm;\n \n@@ -245,248 +301,237 @@ rte_lpm_free(struct rte_lpm *lpm)\n \n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n \n+\trte_free(lpm->tbl8);\n \trte_free(lpm);\n \trte_free(te);\n }\n \n+\n /*\n- * Adds a rule to the rule table.\n- *\n- * NOTE: The rule table is split into 32 groups. Each group contains rules that\n- * apply to a specific prefix depth (i.e. group 1 contains rules that apply to\n- * prefixes with a depth of 1 etc.). In the following code (depth - 1) is used\n- * to refer to depth 1 because even though the depth range is 1 - 32, depths\n- * are stored in the rule table from 0 - 31.\n- * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.\n+ * Finds a rule in rule table.\n  */\n-static inline int32_t\n-rule_add(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n-\tuint8_t next_hop)\n+static struct rte_lpm_rule *\n+rule_find(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, uint8_t scope)\n {\n-\tuint32_t rule_gindex, rule_index, last_rule;\n-\tint i;\n-\n-\tVERIFY_DEPTH(depth);\n-\n-\t/* Scan through rule group to see if rule already exists. */\n-\tif (lpm->rule_info[depth - 1].used_rules > 0) {\n-\n-\t\t/* rule_gindex stands for rule group index. */\n-\t\trule_gindex = 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 + lpm->rule_info[depth - 1].used_rules;\n-\n-\t\tfor (; rule_index < last_rule; rule_index++) {\n+\tstruct rte_lpm_rules_tree *head = &lpm->rules[depth];\n+\tstruct rte_lpm_rule k = {\n+\t\t.ip = ip_masked,\n+\t\t.scope = scope,\n+\t};\n \n-\t\t\t/* If rule already exists update its next_hop and return. */\n-\t\t\tif (lpm->rules_tbl[rule_index].ip == ip_masked) {\n-\t\t\t\tlpm->rules_tbl[rule_index].next_hop = next_hop;\n-\n-\t\t\t\treturn rule_index;\n-\t\t\t}\n-\t\t}\n-\n-\t\tif (rule_index == 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+\treturn RB_FIND(rte_lpm_rules_tree, head, &k);\n+}\n \n-\t\tfor (i = depth - 1; i > 0; i--) {\n-\t\t\tif (lpm->rule_info[i - 1].used_rules > 0) {\n-\t\t\t\trule_index = lpm->rule_info[i - 1].first_rule + lpm->rule_info[i - 1].used_rules;\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t}\n-\t\tif (rule_index == lpm->max_rules)\n-\t\t\treturn -ENOSPC;\n+/* Finds rule in table in scope order */\n+static struct rte_lpm_rule *\n+rule_find_any(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth)\n+{\n+\tstruct rte_lpm_rule *r;\n+\tint scope;\n \n-\t\tlpm->rule_info[depth - 1].first_rule = rule_index;\n+\tfor (scope = 255; scope >= 0; --scope) {\n+\t\tr = rule_find(lpm, ip_masked, depth, scope);\n+\t\tif (r)\n+\t\t\treturn r;\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 (lpm->rule_info[i - 1].first_rule + lpm->rule_info[i - 1].used_rules == lpm->max_rules)\n-\t\t\treturn -ENOSPC;\n+\treturn NULL;\n+}\n \n-\t\tif (lpm->rule_info[i - 1].used_rules > 0) {\n-\t\t\tlpm->rules_tbl[lpm->rule_info[i - 1].first_rule + lpm->rule_info[i - 1].used_rules]\n-\t\t\t\t\t= lpm->rules_tbl[lpm->rule_info[i - 1].first_rule];\n-\t\t\tlpm->rule_info[i - 1].first_rule++;\n-\t\t}\n-\t}\n+/*\n+ * Adds a rule to the rule table.\n+ *\n+ * NOTE: The rule table is split into 32 groups. Each group contains rules that\n+ * apply to a specific prefix depth (i.e. group 1 contains rules that apply to\n+ * prefixes with a depth of 1 etc.).\n+ * NOTE: Valid range for depth parameter is 0 .. 32 inclusive.\n+ */\n+static struct rte_lpm_rule *\n+rule_add(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n+\t uint16_t next_hop, uint8_t scope)\n+{\n+\tstruct rte_lpm_rules_tree *head = &lpm->rules[depth];\n+\tstruct rte_lpm_rule *r, *old;\n \n-\t/* Add the new rule. */\n-\tlpm->rules_tbl[rule_index].ip = ip_masked;\n-\tlpm->rules_tbl[rule_index].next_hop = next_hop;\n+\t/*\n+\t * NB: uses regular malloc to avoid chewing up precious\n+\t *  memory pool space for rules.\n+\t */\n+\tr = malloc(sizeof(*r));\n+\tif (!r)\n+\t\treturn NULL;\n \n-\t/* Increment the used rules counter for this rule group. */\n-\tlpm->rule_info[depth - 1].used_rules++;\n+\tr->ip = ip_masked;\n+\tr->next_hop = next_hop;\n+\tr->scope = scope;\n \n-\treturn rule_index;\n+\told = RB_INSERT(rte_lpm_rules_tree, head, r);\n+\tif (!old)\n+\t\treturn r;\n+\n+\t/* collision with existing rule */\n+\tfree(r);\n+\treturn old;\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 inline void\n-rule_delete(struct rte_lpm *lpm, int32_t rule_index, uint8_t depth)\n+static void\n+rule_delete(struct rte_lpm *lpm, struct rte_lpm_rule *r, uint8_t depth)\n {\n-\tint i;\n+\tstruct rte_lpm_rules_tree *head = &lpm->rules[depth];\n \n-\tVERIFY_DEPTH(depth);\n-\n-\tlpm->rules_tbl[rule_index] = lpm->rules_tbl[lpm->rule_info[depth - 1].first_rule\n-\t\t\t+ lpm->rule_info[depth - 1].used_rules - 1];\n+\tRB_REMOVE(rte_lpm_rules_tree, head, r);\n \n-\tfor (i = depth; i < RTE_LPM_MAX_DEPTH; i++) {\n-\t\tif (lpm->rule_info[i].used_rules > 0) {\n-\t\t\tlpm->rules_tbl[lpm->rule_info[i].first_rule - 1] =\n-\t\t\t\t\tlpm->rules_tbl[lpm->rule_info[i].first_rule + lpm->rule_info[i].used_rules - 1];\n-\t\t\tlpm->rule_info[i].first_rule--;\n-\t\t}\n-\t}\n-\n-\tlpm->rule_info[depth - 1].used_rules--;\n+\tfree(r);\n }\n \n /*\n- * Finds a rule in rule table.\n- * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.\n+ * Dynamically increase size of tbl8\n  */\n-static inline int32_t\n-rule_find(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth)\n+static int\n+tbl8_grow(struct rte_lpm *lpm)\n {\n-\tuint32_t rule_gindex, last_rule, rule_index;\n-\n-\tVERIFY_DEPTH(depth);\n+\tsize_t old_size, new_size;\n+\tstruct rte_lpm_tbl8_entry *new_tbl8;\n+\n+\t/* This should not happen,\n+\t * worst case is each /24 can point to one tbl8 */\n+\tif (lpm->tbl8_num_groups >= RTE_LPM_TBL24_NUM_ENTRIES)\n+\t\trte_panic(\"LPM: tbl8 grow already at %u\",\n+\t\t\t  lpm->tbl8_num_groups);\n+\n+\told_size = lpm->tbl8_num_groups;\n+\tnew_size = old_size << 1;\n+\tnew_tbl8 = rte_calloc_socket(NULL,\n+\t\t\t\t     new_size * RTE_LPM_TBL8_GROUP_NUM_ENTRIES,\n+\t\t\t\t     sizeof(struct rte_lpm_tbl8_entry),\n+\t\t\t\t     RTE_CACHE_LINE_SIZE,\n+\t\t\t\t     lpm->socket_id);\n+\tif (new_tbl8 == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"LPM tbl8 group expand allocation failed\\n\");\n+\t\treturn -ENOMEM;\n+\t}\n \n-\trule_gindex = lpm->rule_info[depth - 1].first_rule;\n-\tlast_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;\n+\tmemcpy(new_tbl8, lpm->tbl8,\n+\t       old_size * RTE_LPM_TBL8_GROUP_NUM_ENTRIES\n+\t\t   * sizeof(struct rte_lpm_tbl8_entry));\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 (lpm->rules_tbl[rule_index].ip == ip_masked)\n-\t\t\treturn rule_index;\n-\t}\n+\t/* swap in new table */\n+\tdefer_rcu(rte_free, lpm->tbl8);\n+\trcu_assign_pointer(lpm->tbl8, new_tbl8);\n+\tlpm->tbl8_num_groups = new_size;\n \n-\t/* If rule is not found return -EINVAL. */\n-\treturn -EINVAL;\n+\treturn 0;\n }\n \n /*\n  * Find, clean and allocate a tbl8.\n  */\n-static inline int32_t\n-tbl8_alloc(struct rte_lpm_tbl8_entry *tbl8)\n+static int32_t\n+tbl8_alloc(struct rte_lpm *lpm)\n {\n \tuint32_t tbl8_gindex; /* tbl8 group index. */\n \tstruct rte_lpm_tbl8_entry *tbl8_entry;\n \n \t/* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */\n-\tfor (tbl8_gindex = 0; tbl8_gindex < RTE_LPM_TBL8_NUM_GROUPS;\n-\t\t\ttbl8_gindex++) {\n-\t\ttbl8_entry = &tbl8[tbl8_gindex *\n-\t\t                   RTE_LPM_TBL8_GROUP_NUM_ENTRIES];\n+\tfor (tbl8_gindex = (lpm->tbl8_rover + 1) & (lpm->tbl8_num_groups - 1);\n+\t     tbl8_gindex != lpm->tbl8_rover;\n+\t     tbl8_gindex = (tbl8_gindex + 1) & (lpm->tbl8_num_groups - 1)) {\n+\t\ttbl8_entry = lpm->tbl8\n+\t\t\t+ tbl8_gindex * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n+\n \t\t/* If a free tbl8 group is found clean it and set as VALID. */\n-\t\tif (!tbl8_entry->valid_group) {\n-\t\t\tmemset(&tbl8_entry[0], 0,\n-\t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES *\n-\t\t\t\t\tsizeof(tbl8_entry[0]));\n+\t\tif (likely(!tbl8_entry->valid_group))\n+\t\t\tgoto found;\n+\t}\n \n-\t\t\ttbl8_entry->valid_group = VALID;\n+\t/* Out of space expand */\n+\ttbl8_gindex = lpm->tbl8_num_groups;\n+\tif (tbl8_grow(lpm) < 0)\n+\t\treturn -ENOSPC;\n \n-\t\t\t/* Return group index for allocated tbl8 group. */\n-\t\t\treturn tbl8_gindex;\n-\t\t}\n-\t}\n+\ttbl8_entry = lpm->tbl8\n+\t\t+ tbl8_gindex * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n+ found:\n+\tmemset(tbl8_entry, 0,\n+\t       RTE_LPM_TBL8_GROUP_NUM_ENTRIES * sizeof(tbl8_entry[0]));\n+\n+\ttbl8_entry->valid_group = VALID;\n \n-\t/* If there are no tbl8 groups free then return error. */\n-\treturn -ENOSPC;\n+\t/* Remember last slot to start looking there */\n+\tlpm->tbl8_rover = tbl8_gindex;\n+\n+\t/* Return group index for allocated tbl8 group. */\n+\treturn tbl8_gindex;\n }\n \n static inline void\n-tbl8_free(struct rte_lpm_tbl8_entry *tbl8, uint32_t tbl8_group_start)\n+tbl8_free(struct rte_lpm *lpm, uint32_t tbl8_group_start)\n {\n \t/* Set tbl8 group invalid*/\n-\ttbl8[tbl8_group_start].valid_group = INVALID;\n+\tlpm->tbl8[tbl8_group_start].valid_group = INVALID;\n }\n \n-static inline int32_t\n+static void\n add_depth_small(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n-\t\tuint8_t next_hop)\n+\t\tuint16_t next_hop)\n {\n \tuint32_t tbl24_index, tbl24_range, tbl8_index, tbl8_group_end, i, j;\n+\tstruct rte_lpm_tbl24_entry new_tbl24_entry = {\n+\t\t.valid = VALID,\n+\t\t.ext_entry = 0,\n+\t\t.depth = depth,\n+\t\t{ .next_hop = next_hop, }\n+\t};\n+\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n+\t\t.valid_group = VALID,\n+\t\t.valid = VALID,\n+\t\t.depth = depth,\n+\t\t.next_hop = next_hop,\n+\t};\n+\n+\t/* Force compiler to initialize before assignment */\n+\trte_barrier();\n \n \t/* Calculate the index into Table24. */\n \ttbl24_index = ip >> 8;\n \ttbl24_range = depth_to_range(depth);\n-\n \tfor (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {\n \t\t/*\n \t\t * For invalid OR valid and non-extended tbl 24 entries set\n \t\t * entry.\n \t\t */\n-\t\tif (!lpm->tbl24[i].valid || (lpm->tbl24[i].ext_entry == 0 &&\n-\t\t\t\tlpm->tbl24[i].depth <= depth)) {\n-\n-\t\t\tstruct rte_lpm_tbl24_entry new_tbl24_entry = {\n-\t\t\t\t{ .next_hop = next_hop, },\n-\t\t\t\t.valid = VALID,\n-\t\t\t\t.ext_entry = 0,\n-\t\t\t\t.depth = depth,\n-\t\t\t};\n-\n-\t\t\t/* Setting tbl24 entry in one go to avoid race\n-\t\t\t * conditions\n-\t\t\t */\n-\t\t\tlpm->tbl24[i] = new_tbl24_entry;\n-\n+\t\tif (!lpm->tbl24[i].valid || lpm->tbl24[i].ext_entry == 0) {\n+\t\t\tif (!lpm->tbl24[i].valid ||\n+\t\t\t    lpm->tbl24[i].depth <= depth)\n+\t\t\t\tlpm->tbl24[i] = new_tbl24_entry;\n \t\t\tcontinue;\n \t\t}\n \n-\t\tif (lpm->tbl24[i].ext_entry == 1) {\n-\t\t\t/* If tbl24 entry is valid and extended calculate the\n-\t\t\t *  index into tbl8.\n-\t\t\t */\n-\t\t\ttbl8_index = lpm->tbl24[i].tbl8_gindex *\n-\t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n-\t\t\ttbl8_group_end = tbl8_index +\n-\t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n-\n-\t\t\tfor (j = tbl8_index; j < tbl8_group_end; j++) {\n-\t\t\t\tif (!lpm->tbl8[j].valid ||\n-\t\t\t\t\t\tlpm->tbl8[j].depth <= depth) {\n-\t\t\t\t\tstruct rte_lpm_tbl8_entry\n-\t\t\t\t\t\tnew_tbl8_entry = {\n-\t\t\t\t\t\t.valid = VALID,\n-\t\t\t\t\t\t.valid_group = VALID,\n-\t\t\t\t\t\t.depth = depth,\n-\t\t\t\t\t\t.next_hop = next_hop,\n-\t\t\t\t\t};\n-\n-\t\t\t\t\t/*\n-\t\t\t\t\t * Setting tbl8 entry in one go to avoid\n-\t\t\t\t\t * race conditions\n-\t\t\t\t\t */\n-\t\t\t\t\tlpm->tbl8[j] = new_tbl8_entry;\n-\n-\t\t\t\t\tcontinue;\n-\t\t\t\t}\n+\t\t/* If tbl24 entry is valid and extended calculate the index\n+\t\t * into tbl8. */\n+\t\ttbl8_index = lpm->tbl24[i].tbl8_gindex\n+\t\t\t* RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n+\t\ttbl8_group_end = tbl8_index + RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n+\t\tfor (j = tbl8_index; j < tbl8_group_end; j++) {\n+\t\t\tif (!lpm->tbl8[j].valid ||\n+\t\t\t    lpm->tbl8[j].depth <= depth) {\n+\t\t\t\t/*\n+\t\t\t\t * Setting tbl8 entry in one go to avoid race\n+\t\t\t\t * conditions\n+\t\t\t\t */\n+\t\t\t\tlpm->tbl8[j] = new_tbl8_entry;\n \t\t\t}\n \t\t}\n \t}\n-\n-\treturn 0;\n }\n \n-static inline int32_t\n+static int32_t\n add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n-\t\tuint8_t next_hop)\n+\t\tuint16_t next_hop)\n {\n \tuint32_t tbl24_index;\n \tint32_t tbl8_group_index, tbl8_group_start, tbl8_group_end, tbl8_index,\n@@ -497,12 +542,11 @@ add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n \n \tif (!lpm->tbl24[tbl24_index].valid) {\n \t\t/* Search for a free tbl8 group. */\n-\t\ttbl8_group_index = tbl8_alloc(lpm->tbl8);\n+\t\ttbl8_group_index = tbl8_alloc(lpm);\n \n-\t\t/* Check tbl8 allocation was successful. */\n-\t\tif (tbl8_group_index < 0) {\n+\t\t/* Check tbl8 allocation was unsuccessful. */\n+\t\tif (tbl8_group_index < 0)\n \t\t\treturn tbl8_group_index;\n-\t\t}\n \n \t\t/* Find index into tbl8 and range. */\n \t\ttbl8_index = (tbl8_group_index *\n@@ -510,35 +554,38 @@ add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n \t\t\t\t(ip_masked & 0xFF);\n \n \t\t/* Set tbl8 entry. */\n-\t\tfor (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {\n-\t\t\tlpm->tbl8[i].depth = depth;\n-\t\t\tlpm->tbl8[i].next_hop = next_hop;\n-\t\t\tlpm->tbl8[i].valid = VALID;\n-\t\t}\n+\t\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n+\t\t\t.valid_group = VALID,\n+\t\t\t.valid = VALID,\n+\t\t\t.depth = depth,\n+\t\t\t.next_hop = next_hop,\n+\t\t};\n+\n+\t\tfor (i = tbl8_index; i < (tbl8_index + tbl8_range); i++)\n+\t\t\tlpm->tbl8[i] = new_tbl8_entry;\n \n \t\t/*\n \t\t * Update tbl24 entry to point to new tbl8 entry. Note: The\n \t\t * ext_flag and tbl8_index need to be updated simultaneously,\n \t\t * so assign whole structure in one go\n \t\t */\n-\n \t\tstruct rte_lpm_tbl24_entry new_tbl24_entry = {\n-\t\t\t{ .tbl8_gindex = (uint8_t)tbl8_group_index, },\n \t\t\t.valid = VALID,\n \t\t\t.ext_entry = 1,\n \t\t\t.depth = 0,\n+\t\t\t{ .tbl8_gindex = tbl8_group_index, }\n \t\t};\n \n+\t\trte_barrier();\n \t\tlpm->tbl24[tbl24_index] = new_tbl24_entry;\n-\n-\t}/* If valid entry but not extended calculate the index into Table8. */\n+\t}\n+\t/* If valid entry but not extended calculate the index into Table8. */\n \telse if (lpm->tbl24[tbl24_index].ext_entry == 0) {\n \t\t/* Search for free tbl8 group. */\n-\t\ttbl8_group_index = tbl8_alloc(lpm->tbl8);\n+\t\ttbl8_group_index = tbl8_alloc(lpm);\n \n-\t\tif (tbl8_group_index < 0) {\n+\t\tif (tbl8_group_index < 0)\n \t\t\treturn tbl8_group_index;\n-\t\t}\n \n \t\ttbl8_group_start = tbl8_group_index *\n \t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n@@ -546,69 +593,68 @@ add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n \t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n \n \t\t/* Populate new tbl8 with tbl24 value. */\n-\t\tfor (i = tbl8_group_start; i < tbl8_group_end; i++) {\n-\t\t\tlpm->tbl8[i].valid = VALID;\n-\t\t\tlpm->tbl8[i].depth = lpm->tbl24[tbl24_index].depth;\n-\t\t\tlpm->tbl8[i].next_hop =\n-\t\t\t\t\tlpm->tbl24[tbl24_index].next_hop;\n-\t\t}\n+\t\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n+\t\t\t.valid_group = VALID,\n+\t\t\t.valid = VALID,\n+\t\t\t.depth = lpm->tbl24[tbl24_index].depth,\n+\t\t\t.next_hop = lpm->tbl24[tbl24_index].next_hop,\n+\t\t};\n+\n+\t\tfor (i = tbl8_group_start; i < tbl8_group_end; i++)\n+\t\t\tlpm->tbl8[i] = new_tbl8_entry;\n \n \t\ttbl8_index = tbl8_group_start + (ip_masked & 0xFF);\n \n-\t\t/* Insert new rule into the tbl8 entry. */\n-\t\tfor (i = tbl8_index; i < tbl8_index + tbl8_range; i++) {\n-\t\t\tif (!lpm->tbl8[i].valid ||\n-\t\t\t\t\tlpm->tbl8[i].depth <= depth) {\n-\t\t\t\tlpm->tbl8[i].valid = VALID;\n-\t\t\t\tlpm->tbl8[i].depth = depth;\n-\t\t\t\tlpm->tbl8[i].next_hop = next_hop;\n-\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t}\n+\t\t/* Insert new specific rule into the tbl8 entry. */\n+\t\tnew_tbl8_entry.depth = depth;\n+\t\tnew_tbl8_entry.next_hop = next_hop;\n+\t\tfor (i = tbl8_index; i < tbl8_index + tbl8_range; i++)\n+\t\t\tlpm->tbl8[i] = new_tbl8_entry;\n \n \t\t/*\n \t\t * Update tbl24 entry to point to new tbl8 entry. Note: The\n \t\t * ext_flag and tbl8_index need to be updated simultaneously,\n \t\t * so assign whole structure in one go.\n \t\t */\n-\n \t\tstruct rte_lpm_tbl24_entry new_tbl24_entry = {\n-\t\t\t\t{ .tbl8_gindex = (uint8_t)tbl8_group_index, },\n \t\t\t\t.valid = VALID,\n \t\t\t\t.ext_entry = 1,\n \t\t\t\t.depth = 0,\n+\t\t\t\t{ .tbl8_gindex = tbl8_group_index, }\n \t\t};\n \n+\t\t/*\n+\t\t * Ensure compiler isn't doing something completely odd\n+\t\t * like updating tbl24 before tbl8.\n+\t\t */\n+\t\trte_barrier();\n \t\tlpm->tbl24[tbl24_index] = new_tbl24_entry;\n \n-\t}\n-\telse { /*\n-\t\t* If it is valid, extended entry calculate the index into tbl8.\n-\t\t*/\n+\t} else {\n+\t\t/*\n+\t\t * If it is valid, extended entry calculate the index into tbl8.\n+\t\t */\n+\t\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n+\t\t\t.valid_group = VALID,\n+\t\t\t.valid = VALID,\n+\t\t\t.depth = depth,\n+\t\t\t.next_hop = next_hop,\n+\t\t};\n+\t\trte_barrier();\n+\n \t\ttbl8_group_index = lpm->tbl24[tbl24_index].tbl8_gindex;\n \t\ttbl8_group_start = tbl8_group_index *\n \t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n \t\ttbl8_index = tbl8_group_start + (ip_masked & 0xFF);\n \n \t\tfor (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {\n-\n \t\t\tif (!lpm->tbl8[i].valid ||\n-\t\t\t\t\tlpm->tbl8[i].depth <= depth) {\n-\t\t\t\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n-\t\t\t\t\t.valid = VALID,\n-\t\t\t\t\t.depth = depth,\n-\t\t\t\t\t.next_hop = next_hop,\n-\t\t\t\t\t.valid_group = lpm->tbl8[i].valid_group,\n-\t\t\t\t};\n-\n+\t\t\t    lpm->tbl8[i].depth <= depth) {\n \t\t\t\t/*\n \t\t\t\t * Setting tbl8 entry in one go to avoid race\n \t\t\t\t * condition\n \t\t\t\t */\n \t\t\t\tlpm->tbl8[i] = new_tbl8_entry;\n-\n-\t\t\t\tcontinue;\n \t\t\t}\n \t\t}\n \t}\n@@ -621,38 +667,32 @@ add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n  */\n int\n rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n-\t\tuint8_t next_hop)\n+\t    uint16_t next_hop, uint8_t scope)\n {\n-\tint32_t rule_index, status = 0;\n-\tuint32_t ip_masked;\n+\tstruct rte_lpm_rule *rule;\n+\tuint32_t ip_masked = (ip & depth_to_mask(depth));\n \n \t/* Check user arguments. */\n-\tif ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH))\n+\tif ((lpm == NULL) || (depth >= RTE_LPM_MAX_DEPTH))\n \t\treturn -EINVAL;\n \n-\tip_masked = ip & depth_to_mask(depth);\n-\n \t/* Add the rule to the rule table. */\n-\trule_index = rule_add(lpm, ip_masked, depth, next_hop);\n+\trule = rule_add(lpm, ip_masked, depth, next_hop, scope);\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-\t}\n-\n-\tif (depth <= MAX_DEPTH_TBL24) {\n-\t\tstatus = add_depth_small(lpm, ip_masked, depth, next_hop);\n-\t}\n-\telse { /* If depth > RTE_LPM_MAX_DEPTH_TBL24 */\n-\t\tstatus = add_depth_big(lpm, ip_masked, depth, next_hop);\n+\tif (rule == NULL)\n+\t\treturn -ENOSPC;\n \n+\tif (depth <= MAX_DEPTH_TBL24)\n+\t\tadd_depth_small(lpm, ip_masked, depth, next_hop);\n+\telse {\n \t\t/*\n \t\t * If add fails due to exhaustion of tbl8 extensions delete\n \t\t * rule that was added to rule table.\n \t\t */\n+\t\tint status = add_depth_big(lpm, ip_masked, depth, next_hop);\n \t\tif (status < 0) {\n-\t\t\trule_delete(lpm, rule_index, depth);\n-\n+\t\t\trule_delete(lpm, rule, depth);\n \t\t\treturn status;\n \t\t}\n \t}\n@@ -665,10 +705,10 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n  */\n int\n rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n-uint8_t *next_hop)\n+\t\t\tuint16_t *next_hop, uint8_t scope)\n {\n \tuint32_t ip_masked;\n-\tint32_t rule_index;\n+\tstruct rte_lpm_rule *rule;\n \n \t/* Check user arguments. */\n \tif ((lpm == NULL) ||\n@@ -678,10 +718,10 @@ uint8_t *next_hop)\n \n \t/* Look for the rule using rule_find. */\n \tip_masked = ip & depth_to_mask(depth);\n-\trule_index = rule_find(lpm, ip_masked, depth);\n+\trule = rule_find(lpm, ip_masked, depth, scope);\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@@ -689,30 +729,29 @@ uint8_t *next_hop)\n \treturn 0;\n }\n \n-static inline int32_t\n-find_previous_rule(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint8_t *sub_rule_depth)\n+static struct rte_lpm_rule *\n+find_previous_rule(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n+\t\t   uint8_t *sub_rule_depth)\n {\n-\tint32_t rule_index;\n+\tstruct rte_lpm_rule *rule;\n \tuint32_t ip_masked;\n-\tuint8_t prev_depth;\n+\tint prev_depth;\n \n-\tfor (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) {\n+\tfor (prev_depth = depth - 1; prev_depth >= 0; prev_depth--) {\n \t\tip_masked = ip & depth_to_mask(prev_depth);\n-\n-\t\trule_index = rule_find(lpm, ip_masked, prev_depth);\n-\n-\t\tif (rule_index >= 0) {\n+\t\trule = rule_find_any(lpm, ip_masked, prev_depth);\n+\t\tif (rule) {\n \t\t\t*sub_rule_depth = prev_depth;\n-\t\t\treturn rule_index;\n+\t\t\treturn rule;\n \t\t}\n \t}\n \n-\treturn -1;\n+\treturn NULL;\n }\n \n-static inline int32_t\n-delete_depth_small(struct rte_lpm *lpm, uint32_t ip_masked,\n-\tuint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)\n+static void\n+delete_depth_small(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n+\t\t   struct rte_lpm_rule *sub_rule, uint8_t new_depth)\n {\n \tuint32_t tbl24_range, tbl24_index, tbl8_group_index, tbl8_index, i, j;\n \n@@ -720,28 +759,22 @@ delete_depth_small(struct rte_lpm *lpm, uint32_t ip_masked,\n \ttbl24_range = depth_to_range(depth);\n \ttbl24_index = (ip_masked >> 8);\n \n-\t/*\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+\t/* Firstly check the sub_rule. */\n+\tif (sub_rule == NULL) {\n \t\t/*\n \t\t * If no replacement rule exists then invalidate entries\n \t\t * associated with this rule.\n \t\t */\n \t\tfor (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {\n-\n-\t\t\tif (lpm->tbl24[i].ext_entry == 0 &&\n-\t\t\t\t\tlpm->tbl24[i].depth <= depth ) {\n-\t\t\t\tlpm->tbl24[i].valid = INVALID;\n-\t\t\t}\n-\t\t\telse {\n+\t\t\tif (lpm->tbl24[i].ext_entry == 0) {\n+\t\t\t\tif (lpm->tbl24[i].depth <= depth)\n+\t\t\t\t\tlpm->tbl24[i].valid = INVALID;\n+\t\t\t} else {\n \t\t\t\t/*\n \t\t\t\t * If TBL24 entry is extended, then there has\n \t\t\t\t * to be a rule with depth >= 25 in the\n \t\t\t\t * associated TBL8 group.\n \t\t\t\t */\n-\n \t\t\t\ttbl8_group_index = lpm->tbl24[i].tbl8_gindex;\n \t\t\t\ttbl8_index = tbl8_group_index *\n \t\t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n@@ -749,60 +782,54 @@ delete_depth_small(struct rte_lpm *lpm, uint32_t ip_masked,\n \t\t\t\tfor (j = tbl8_index; j < (tbl8_index +\n \t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) {\n \n-\t\t\t\t\tif (lpm->tbl8[j].depth <= depth)\n+\t\t\t\t\tif (lpm->tbl8[j].valid &&\n+\t\t\t\t\t    lpm->tbl8[j].depth <= depth)\n \t\t\t\t\t\tlpm->tbl8[j].valid = INVALID;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n-\t}\n-\telse {\n+\t} else {\n \t\t/*\n \t\t * If a replacement rule exists then modify entries\n \t\t * associated with this rule.\n \t\t */\n-\n \t\tstruct rte_lpm_tbl24_entry new_tbl24_entry = {\n-\t\t\t{.next_hop = lpm->rules_tbl[sub_rule_index].next_hop,},\n \t\t\t.valid = VALID,\n \t\t\t.ext_entry = 0,\n-\t\t\t.depth = sub_rule_depth,\n+\t\t\t.depth = new_depth,\n+\t\t\t{ .next_hop = sub_rule->next_hop, }\n \t\t};\n \n \t\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n+\t\t\t.valid_group = VALID,\n \t\t\t.valid = VALID,\n-\t\t\t.depth = sub_rule_depth,\n-\t\t\t.next_hop = lpm->rules_tbl\n-\t\t\t[sub_rule_index].next_hop,\n+\t\t\t.depth = new_depth,\n+\t\t\t.next_hop = sub_rule->next_hop,\n \t\t};\n \n \t\tfor (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {\n-\n-\t\t\tif (lpm->tbl24[i].ext_entry == 0 &&\n-\t\t\t\t\tlpm->tbl24[i].depth <= depth ) {\n-\t\t\t\tlpm->tbl24[i] = new_tbl24_entry;\n-\t\t\t}\n-\t\t\telse {\n+\t\t\tif (lpm->tbl24[i].ext_entry == 0) {\n+\t\t\t\tif (lpm->tbl24[i].depth <= depth)\n+\t\t\t\t\tlpm->tbl24[i] = new_tbl24_entry;\n+\t\t\t} else {\n \t\t\t\t/*\n \t\t\t\t * If TBL24 entry is extended, then there has\n \t\t\t\t * to be a rule with depth >= 25 in the\n \t\t\t\t * associated TBL8 group.\n \t\t\t\t */\n-\n \t\t\t\ttbl8_group_index = lpm->tbl24[i].tbl8_gindex;\n \t\t\t\ttbl8_index = tbl8_group_index *\n \t\t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n \n \t\t\t\tfor (j = tbl8_index; j < (tbl8_index +\n \t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) {\n-\n-\t\t\t\t\tif (lpm->tbl8[j].depth <= depth)\n+\t\t\t\t\tif (!lpm->tbl8[j].valid ||\n+\t\t\t\t\t    lpm->tbl8[j].depth <= depth)\n \t\t\t\t\t\tlpm->tbl8[j] = new_tbl8_entry;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n-\n-\treturn 0;\n }\n \n /*\n@@ -813,8 +840,9 @@ delete_depth_small(struct rte_lpm *lpm, uint32_t ip_masked,\n  * Return of value > -1 means tbl8 is in use but has all the same values and\n  * thus can be recycled\n  */\n-static inline int32_t\n-tbl8_recycle_check(struct rte_lpm_tbl8_entry *tbl8, uint32_t tbl8_group_start)\n+static int32_t\n+tbl8_recycle_check(const struct rte_lpm_tbl8_entry *tbl8,\n+\t\t   uint32_t tbl8_group_start)\n {\n \tuint32_t tbl8_group_end, i;\n \ttbl8_group_end = tbl8_group_start + RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n@@ -855,13 +883,14 @@ tbl8_recycle_check(struct rte_lpm_tbl8_entry *tbl8, uint32_t tbl8_group_start)\n \t\tif (tbl8[i].valid)\n \t\t\treturn -EEXIST;\n \t}\n+\n \t/* If no valid entries are found then return -EINVAL. */\n \treturn -EINVAL;\n }\n \n-static inline int32_t\n-delete_depth_big(struct rte_lpm *lpm, uint32_t ip_masked,\n-\tuint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)\n+static void\n+delete_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,\n+\t\t struct rte_lpm_rule *sub_rule, uint8_t new_depth)\n {\n \tuint32_t tbl24_index, tbl8_group_index, tbl8_group_start, tbl8_index,\n \t\t\ttbl8_range, i;\n@@ -879,23 +908,22 @@ delete_depth_big(struct rte_lpm *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 (sub_rule == NULL) {\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 \t\t */\n \t\tfor (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {\n-\t\t\tif (lpm->tbl8[i].depth <= depth)\n+\t\t\tif (lpm->tbl8[i].valid && lpm->tbl8[i].depth <= depth)\n \t\t\t\tlpm->tbl8[i].valid = INVALID;\n \t\t}\n-\t}\n-\telse {\n+\t} else {\n \t\t/* Set new tbl8 entry. */\n \t\tstruct rte_lpm_tbl8_entry new_tbl8_entry = {\n+\t\t\t.valid_group = VALID,\n \t\t\t.valid = VALID,\n-\t\t\t.depth = sub_rule_depth,\n-\t\t\t.valid_group = lpm->tbl8[tbl8_group_start].valid_group,\n-\t\t\t.next_hop = lpm->rules_tbl[sub_rule_index].next_hop,\n+\t\t\t.depth = new_depth,\n+\t\t\t.next_hop = sub_rule->next_hop,\n \t\t};\n \n \t\t/*\n@@ -903,7 +931,7 @@ delete_depth_big(struct rte_lpm *lpm, uint32_t ip_masked,\n \t\t * rule_to_delete must be modified.\n \t\t */\n \t\tfor (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {\n-\t\t\tif (lpm->tbl8[i].depth <= depth)\n+\t\t\tif (!lpm->tbl8[i].valid || lpm->tbl8[i].depth <= depth)\n \t\t\t\tlpm->tbl8[i] = new_tbl8_entry;\n \t\t}\n \t}\n@@ -915,100 +943,158 @@ delete_depth_big(struct rte_lpm *lpm, uint32_t ip_masked,\n \t */\n \n \ttbl8_recycle_index = tbl8_recycle_check(lpm->tbl8, tbl8_group_start);\n-\n-\tif (tbl8_recycle_index == -EINVAL){\n+\tif (tbl8_recycle_index == -EINVAL) {\n \t\t/* Set tbl24 before freeing tbl8 to avoid race condition. */\n \t\tlpm->tbl24[tbl24_index].valid = 0;\n-\t\ttbl8_free(lpm->tbl8, tbl8_group_start);\n-\t}\n-\telse if (tbl8_recycle_index > -1) {\n+\t\trte_barrier();\n+\t\ttbl8_free(lpm, tbl8_group_start);\n+\t} else if (tbl8_recycle_index > -1) {\n \t\t/* Update tbl24 entry. */\n \t\tstruct rte_lpm_tbl24_entry new_tbl24_entry = {\n-\t\t\t{ .next_hop = lpm->tbl8[tbl8_recycle_index].next_hop, },\n \t\t\t.valid = VALID,\n \t\t\t.ext_entry = 0,\n \t\t\t.depth = lpm->tbl8[tbl8_recycle_index].depth,\n+\t\t\t{ .next_hop = lpm->tbl8[tbl8_recycle_index].next_hop, }\n \t\t};\n \n \t\t/* Set tbl24 before freeing tbl8 to avoid race condition. */\n \t\tlpm->tbl24[tbl24_index] = new_tbl24_entry;\n-\t\ttbl8_free(lpm->tbl8, tbl8_group_start);\n+\t\trte_barrier();\n+\t\ttbl8_free(lpm, tbl8_group_start);\n \t}\n+}\n \n-\treturn 0;\n+/*\n+ * Find rule to replace the just deleted. If there is no rule to\n+ * replace the rule_to_delete we return NULL and invalidate the table\n+ * entries associated with this rule.\n+ */\n+static void rule_replace(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)\n+{\n+\tuint32_t ip_masked;\n+\tstruct rte_lpm_rule *sub_rule;\n+\tuint8_t sub_depth = 0;\n+\n+\tip_masked = ip & depth_to_mask(depth);\n+\tsub_rule = find_previous_rule(lpm, ip, depth, &sub_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\tdelete_depth_small(lpm, ip_masked, depth, sub_rule, sub_depth);\n+\telse\n+\t\tdelete_depth_big(lpm, ip_masked, depth, sub_rule, sub_depth);\n }\n \n /*\n  * Deletes a rule\n  */\n int\n-rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)\n+rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n+\t       uint16_t *next_hop, uint8_t scope)\n {\n-\tint32_t rule_to_delete_index, sub_rule_index;\n+\tstruct rte_lpm_rule *rule;\n \tuint32_t ip_masked;\n-\tuint8_t sub_rule_depth;\n+\n \t/*\n \t * Check input arguments. Note: IP must be a positive integer of 32\n \t * bits in length therefore it need not be checked.\n \t */\n-\tif ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) {\n+\tif ((lpm == NULL) || (depth >= RTE_LPM_MAX_DEPTH))\n \t\treturn -EINVAL;\n-\t}\n \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 * Find 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+\trule = rule_find(lpm, ip_masked, depth, scope);\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 * function rule_find returns -E_RTE_NO_TAILQ.\n \t */\n-\tif (rule_to_delete_index < 0)\n+\tif (rule == NULL)\n \t\treturn -EINVAL;\n \n-\t/* Delete the rule from the rule table. */\n-\trule_delete(lpm, rule_to_delete_index, depth);\n-\n \t/*\n-\t * Find rule to replace the rule_to_delete. If there is no rule to\n-\t * replace the rule_to_delete we return -1 and invalidate the table\n-\t * entries associated with this rule.\n+\t * Return next hop so caller can avoid lookup.\n \t */\n-\tsub_rule_depth = 0;\n-\tsub_rule_index = find_previous_rule(lpm, ip, depth, &sub_rule_depth);\n+\tif (next_hop)\n+\t\t*next_hop = rule->next_hop;\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(lpm, ip_masked, depth,\n-\t\t\t\tsub_rule_index, sub_rule_depth);\n-\t}\n-\telse { /* If depth > MAX_DEPTH_TBL24 */\n-\t\treturn delete_depth_big(lpm, ip_masked, depth, sub_rule_index, sub_rule_depth);\n-\t}\n+\t/* Delete the rule from the rule table. */\n+\trule_delete(lpm, rule, depth);\n+\n+\t/* Replace with next level up rule */\n+\trule_replace(lpm, ip, depth);\n+\n+\treturn 0;\n }\n \n /*\n  * Delete all rules from the LPM table.\n  */\n void\n-rte_lpm_delete_all(struct rte_lpm *lpm)\n+rte_lpm_delete_all(struct rte_lpm *lpm, rte_lpm_walk_func_t func, void *arg)\n {\n-\t/* Zero rule information. */\n-\tmemset(lpm->rule_info, 0, sizeof(lpm->rule_info));\n+\tuint8_t depth;\n \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));\n+\tmemset(lpm->tbl8, 0,\n+\t       lpm->tbl8_num_groups * RTE_LPM_TBL8_GROUP_NUM_ENTRIES\n+\t\t   * sizeof(struct rte_lpm_tbl8_entry));\n+\tlpm->tbl8_rover = lpm->tbl8_num_groups - 1;\n \n \t/* Delete all rules form the rules table. */\n-\tmemset(lpm->rules_tbl, 0, sizeof(lpm->rules_tbl[0]) * lpm->max_rules);\n+\tfor (depth = 0; depth < RTE_LPM_MAX_DEPTH; ++depth) {\n+\t\tstruct rte_lpm_rules_tree *head = &lpm->rules[depth];\n+\t\tstruct rte_lpm_rule *r, *n;\n+\n+\t\tRB_FOREACH_SAFE(r, rte_lpm_rules_tree, head, n) {\n+\t\t\tif (func)\n+\t\t\t\tfunc(lpm, r->ip, depth, r->scope,\n+\t\t\t\t     r->next_hop, arg);\n+\t\t\trule_delete(lpm, r, depth);\n+\t\t}\n+\t}\n+}\n+\n+/*\n+ * Iterate over LPM rules\n+ */\n+void\n+rte_lpm_walk(struct rte_lpm *lpm, rte_lpm_walk_func_t func, void *arg)\n+{\n+\tuint8_t depth;\n+\n+\tfor (depth = 0; depth < RTE_LPM_MAX_DEPTH; depth++) {\n+\t\tstruct rte_lpm_rules_tree *head = &lpm->rules[depth];\n+\t\tstruct rte_lpm_rule *r, *n;\n+\n+\t\tRB_FOREACH_SAFE(r, rte_lpm_rules_tree, head, n) {\n+\t\t\tfunc(lpm, r->ip, depth, r->scope, r->next_hop, arg);\n+\t\t}\n+\t}\n+}\n+\n+/* Count usage of tbl8 */\n+unsigned\n+rte_lpm_tbl8_count(const struct rte_lpm *lpm)\n+{\n+\tunsigned i, count = 0;\n+\n+\tfor (i = 0; i < lpm->tbl8_num_groups; i++) {\n+\t\tconst struct rte_lpm_tbl8_entry *tbl8_entry\n+\t\t\t= lpm->tbl8 + i * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n+\t\tif (tbl8_entry->valid_group)\n+\t\t\t++count;\n+\t}\n+\treturn count;\n }\ndiff --git a/lib/librte_lpm/rte_lpm.h b/lib/librte_lpm/rte_lpm.h\nindex c299ce2..a39e3b5 100644\n--- a/lib/librte_lpm/rte_lpm.h\n+++ b/lib/librte_lpm/rte_lpm.h\n@@ -2,6 +2,7 @@\n  *   BSD LICENSE\n  *\n  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.\n+ *   Copyright(c) 2012-2015 Brocade Communications Systems\n  *   All rights reserved.\n  *\n  *   Redistribution and use in source and binary forms, with or without\n@@ -43,11 +44,9 @@\n #include <sys/queue.h>\n #include <stdint.h>\n #include <stdlib.h>\n+#include <bsd/sys/tree.h>\n #include <rte_branch_prediction.h>\n-#include <rte_byteorder.h>\n #include <rte_memory.h>\n-#include <rte_common.h>\n-#include <rte_vect.h>\n \n #ifdef __cplusplus\n extern \"C\" {\n@@ -55,130 +54,89 @@ extern \"C\" {\n \n /** Max number of characters in LPM name. */\n #define RTE_LPM_NAMESIZE                32\n+ \n+ /** Maximum depth value possible for IPv4 LPM. */\n+#define RTE_LPM_MAX_DEPTH               33\n+ \n+/** Total number of tbl24 entries. */\n+#define RTE_LPM_TBL24_NUM_ENTRIES (1 << 24)\n \n-/** Maximum depth value possible for IPv4 LPM. */\n-#define RTE_LPM_MAX_DEPTH               32\n+/** Number of entries in a tbl8 group. */\n+#define RTE_LPM_TBL8_GROUP_NUM_ENTRIES 256\n \n-/** @internal Total number of tbl24 entries. */\n-#define RTE_LPM_TBL24_NUM_ENTRIES       (1 << 24)\n-\n-/** @internal Number of entries in a tbl8 group. */\n-#define RTE_LPM_TBL8_GROUP_NUM_ENTRIES  256\n-\n-/** @internal Total number of tbl8 groups in the tbl8. */\n-#define RTE_LPM_TBL8_NUM_GROUPS         256\n-\n-/** @internal Total number of tbl8 entries. */\n-#define RTE_LPM_TBL8_NUM_ENTRIES        (RTE_LPM_TBL8_NUM_GROUPS * \\\n-\t\t\t\t\tRTE_LPM_TBL8_GROUP_NUM_ENTRIES)\n-\n-/** @internal Macro to enable/disable run-time checks. */\n-#if defined(RTE_LIBRTE_LPM_DEBUG)\n-#define RTE_LPM_RETURN_IF_TRUE(cond, retval) do { \\\n-\tif (cond) return (retval);                \\\n-} while (0)\n-#else\n-#define RTE_LPM_RETURN_IF_TRUE(cond, retval)\n-#endif\n-\n-/** @internal bitmask with valid and ext_entry/valid_group fields set */\n-#define RTE_LPM_VALID_EXT_ENTRY_BITMASK 0x0300\n-\n-/** Bitmask used to indicate successful lookup */\n-#define RTE_LPM_LOOKUP_SUCCESS          0x0100\n-\n-#if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN\n-/** @internal Tbl24 entry structure. */\n+/** Tbl24 entry structure. */\n struct rte_lpm_tbl24_entry {\n+\t/* Using single uint8_t to store 3 values. */\n+\tuint8_t valid       :1; /**< Validation flag. */\n+\tuint8_t ext_entry   :1; /**< external entry? */\n+\tuint8_t depth;\t      /**< Rule depth. */\n \t/* Stores Next hop or group index (i.e. gindex)into tbl8. */\n \tunion {\n-\t\tuint8_t next_hop;\n-\t\tuint8_t tbl8_gindex;\n+\t\tuint16_t next_hop;\n+\t\tuint16_t tbl8_gindex;\n \t};\n-\t/* Using single uint8_t to store 3 values. */\n-\tuint8_t valid     :1; /**< Validation flag. */\n-\tuint8_t ext_entry :1; /**< External entry. */\n-\tuint8_t depth     :6; /**< Rule depth. */\n };\n \n-/** @internal Tbl8 entry structure. */\n+/** Tbl8 entry structure. */\n struct rte_lpm_tbl8_entry {\n-\tuint8_t next_hop; /**< next hop. */\n-\t/* Using single uint8_t to store 3 values. */\n+\tuint16_t next_hop;\t/**< next hop. */\n+\tuint8_t  depth;\t/**< Rule depth. */\n \tuint8_t valid       :1; /**< Validation flag. */\n \tuint8_t valid_group :1; /**< Group validation flag. */\n-\tuint8_t depth       :6; /**< Rule depth. */\n-};\n-#else\n-struct rte_lpm_tbl24_entry {\n-\tuint8_t depth       :6;\n-\tuint8_t ext_entry   :1;\n-\tuint8_t valid       :1;\n-\tunion {\n-\t\tuint8_t tbl8_gindex;\n-\t\tuint8_t next_hop;\n-\t};\n-};\n-\n-struct rte_lpm_tbl8_entry {\n-\tuint8_t depth       :6;\n-\tuint8_t valid_group :1;\n-\tuint8_t valid       :1;\n-\tuint8_t next_hop;\n-};\n-#endif\n-\n-/** @internal Rule structure. */\n-struct rte_lpm_rule {\n-\tuint32_t ip; /**< Rule IP address. */\n-\tuint8_t  next_hop; /**< Rule next hop. */\n-};\n-\n-/** @internal Contains metadata about the rules table. */\n-struct rte_lpm_rule_info {\n-\tuint32_t used_rules; /**< Used rules so far. */\n-\tuint32_t first_rule; /**< Indexes the first rule of a given depth. */\n };\n \n /** @internal LPM structure. */\n struct rte_lpm {\n+\tTAILQ_ENTRY(rte_lpm) next;      /**< Next in list. */\n+\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-\tstruct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH]; /**< Rule info table. */\n+\tchar name[RTE_LPM_NAMESIZE];    /**< Name of the lpm. */\n+\n+\t/**< LPM rules. */\n+\tint socket_id;\t\t/**< socket to allocate rules on */\n+\tRB_HEAD(rte_lpm_rules_tree, rte_lpm_rule) rules[RTE_LPM_MAX_DEPTH];\n \n \t/* LPM Tables. */\n-\tstruct rte_lpm_tbl24_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES] \\\n+\tuint32_t tbl8_num_groups;\t\t/* Number of slots */\n+\tuint32_t tbl8_rover;\t\t\t/* Next slot to check */\n+\tstruct rte_lpm_tbl8_entry *tbl8;\t/* Actual table */\n+\n+\tstruct rte_lpm_tbl24_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES]\n \t\t\t__rte_cache_aligned; /**< LPM tbl24 table. */\n-\tstruct rte_lpm_tbl8_entry tbl8[RTE_LPM_TBL8_NUM_ENTRIES] \\\n-\t\t\t__rte_cache_aligned; /**< LPM tbl8 table. */\n-\tstruct rte_lpm_rule rules_tbl[0] \\\n-\t\t\t__rte_cache_aligned; /**< LPM rules. */\n };\n \n /**\n+ * Compiler memory barrier.\n+ *\n+ * Protects against compiler optimization of ordered operations.\n+ */\n+#ifdef __GNUC__\n+#define rte_barrier() asm volatile(\"\": : :\"memory\")\n+#else\n+/* Intel compiler has intrinsic for this. */\n+#define rte_barrier() __memory_barrier()\n+#endif\n+\n+/**\n  * Create an LPM object.\n  *\n  * @param name\n  *   LPM object name\n  * @param socket_id\n  *   NUMA socket ID for LPM table memory allocation\n- * @param max_rules\n- *   Maximum number of LPM rules that can be added\n- * @param flags\n- *   This parameter is currently unused\n  * @return\n  *   Handle to LPM object on success, NULL otherwise with rte_errno set\n  *   to an appropriate values. Possible rte_errno values include:\n  *    - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure\n  *    - E_RTE_SECONDARY - function was called from a secondary process instance\n+ *    - E_RTE_NO_TAILQ - no tailq list could be got for the lpm object list\n  *    - EINVAL - invalid parameter passed to function\n  *    - ENOSPC - the maximum number of memzones has already been allocated\n  *    - EEXIST - a memzone with the same name already exists\n  *    - ENOMEM - no appropriate memory area found in which to create memzone\n  */\n struct rte_lpm *\n-rte_lpm_create(const char *name, int socket_id, int max_rules, int flags);\n+rte_lpm_create(const char *name, int socket_id);\n \n /**\n  * Find an existing LPM object and return a pointer to it.\n@@ -215,11 +173,14 @@ rte_lpm_free(struct rte_lpm *lpm);\n  *   Depth of the rule to be added to the LPM table\n  * @param next_hop\n  *   Next hop of the rule to be added to the LPM table\n+ * @param scope\n+ *   Priority scope of this route rule\n  * @return\n  *   0 on success, negative value otherwise\n  */\n int\n-rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint8_t next_hop);\n+rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n+\t    uint16_t next_hop, uint8_t scope);\n \n /**\n  * Check if a rule is present in the LPM table,\n@@ -231,6 +192,8 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint8_t next_hop);\n  *   IP of the rule to be searched\n  * @param depth\n  *   Depth of the rule to searched\n+ * @param scope\n+ *   Priority scope of the rule\n  * @param next_hop\n  *   Next hop of the rule (valid only if it is found)\n  * @return\n@@ -238,7 +201,7 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint8_t next_hop);\n  */\n int\n rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n-uint8_t *next_hop);\n+\t\t\tuint16_t *next_hop, uint8_t scope);\n \n /**\n  * Delete a rule from the LPM table.\n@@ -249,20 +212,30 @@ uint8_t *next_hop);\n  *   IP of the rule to be deleted from the LPM table\n  * @param depth\n  *   Depth of the rule to be deleted from the LPM table\n+ * @param scope\n+ *   Priority scope of this route rule\n  * @return\n  *   0 on success, negative value otherwise\n  */\n int\n-rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);\n+rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,\n+\t       uint16_t *next_hop, uint8_t scope);\n+\n+/** iterator function for LPM rule */\n+typedef void (*rte_lpm_walk_func_t)(struct rte_lpm *lpm,\n+\t\t\t\t    uint32_t ip, uint8_t depth, uint8_t scope,\n+\t\t\t\t    uint16_t next_hop, void *arg);\n \n /**\n  * Delete all rules from the LPM table.\n  *\n  * @param lpm\n  *   LPM object handle\n+ * @param func\n+ *   Optional callback for each entry\n  */\n void\n-rte_lpm_delete_all(struct rte_lpm *lpm);\n+rte_lpm_delete_all(struct rte_lpm *lpm, rte_lpm_walk_func_t func, void *arg);\n \n /**\n  * Lookup an IP into the LPM table.\n@@ -277,200 +250,80 @@ rte_lpm_delete_all(struct rte_lpm *lpm);\n  *   -EINVAL for incorrect arguments, -ENOENT on lookup miss, 0 on lookup hit\n  */\n static inline int\n-rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint8_t *next_hop)\n+rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint16_t *next_hop)\n {\n-\tunsigned tbl24_index = (ip >> 8);\n-\tuint16_t tbl_entry;\n+\tstruct rte_lpm_tbl24_entry tbl24;\n+\tstruct rte_lpm_tbl8_entry tbl8;\n \n-\t/* DEBUG: Check user input arguments. */\n-\tRTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (next_hop == NULL)), -EINVAL);\n+\t/* Copy tbl24 entry (to avoid conconcurrency issues) */\n+\ttbl24 = lpm->tbl24[ip >> 8];\n+\trte_barrier();\n \n-\t/* Copy tbl24 entry */\n-\ttbl_entry = *(const uint16_t *)&lpm->tbl24[tbl24_index];\n+\t/*\n+\t * Use the tbl24_index to access the required tbl24 entry then check if\n+\t * the tbl24 entry is INVALID, if so return -ENOENT.\n+\t */\n+\tif (unlikely(!tbl24.valid))\n+\t\treturn -ENOENT; /* Lookup miss. */\n \n-\t/* Copy tbl8 entry (only if needed) */\n-\tif (unlikely((tbl_entry & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==\n-\t\t\tRTE_LPM_VALID_EXT_ENTRY_BITMASK)) {\n+\t/*\n+\t * If tbl24 entry is valid check if it is NOT extended (i.e. it does\n+\t * not use a tbl8 extension) if so return the next hop.\n+\t */\n+\tif (tbl24.ext_entry == 0) {\n+\t\t*next_hop = tbl24.next_hop;\n+\t\treturn 0; /* Lookup hit. */\n+\t}\n \n-\t\tunsigned tbl8_index = (uint8_t)ip +\n-\t\t\t\t((uint8_t)tbl_entry * RTE_LPM_TBL8_GROUP_NUM_ENTRIES);\n+\t/*\n+\t * If tbl24 entry is valid and extended calculate the index into the\n+\t * tbl8 entry.\n+\t */\n+\ttbl8 = lpm->tbl8[tbl24.tbl8_gindex * RTE_LPM_TBL8_GROUP_NUM_ENTRIES\n+\t\t\t + (ip & 0xFF)];\n+\trte_barrier();\n \n-\t\ttbl_entry = *(const uint16_t *)&lpm->tbl8[tbl8_index];\n-\t}\n+\t/* Check if the tbl8 entry is invalid and if so return -ENOENT. */\n+\tif (unlikely(!tbl8.valid))\n+\t\treturn -ENOENT; /* Lookup miss. */\n \n-\t*next_hop = (uint8_t)tbl_entry;\n-\treturn (tbl_entry & RTE_LPM_LOOKUP_SUCCESS) ? 0 : -ENOENT;\n+\t/* If the tbl8 entry is valid return return the next_hop. */\n+\t*next_hop = tbl8.next_hop;\n+\treturn 0; /* Lookup hit. */\n }\n \n /**\n- * Lookup multiple IP addresses in an LPM table. This may be implemented as a\n- * macro, so the address of the function should not be used.\n+ * Iterate over all rules in the LPM table.\n  *\n  * @param lpm\n  *   LPM object handle\n- * @param ips\n- *   Array of IPs to be looked up in the LPM table\n- * @param next_hops\n- *   Next hop of the most specific rule found for IP (valid on lookup hit only).\n- *   This is an array of two byte values. The most significant byte in each\n- *   value says whether the lookup was successful (bitmask\n- *   RTE_LPM_LOOKUP_SUCCESS is set). The least significant byte is the\n- *   actual next hop.\n- * @param n\n- *   Number of elements in ips (and next_hops) array to lookup. This should be a\n- *   compile time constant, and divisible by 8 for best performance.\n- *  @return\n- *   -EINVAL for incorrect arguments, otherwise 0\n+ * @param func\n+ *   Callback to display\n+ * @param arg\n+ *   Argument passed to iterator\n  */\n-#define rte_lpm_lookup_bulk(lpm, ips, next_hops, n) \\\n-\t\trte_lpm_lookup_bulk_func(lpm, ips, next_hops, n)\n-\n-static inline int\n-rte_lpm_lookup_bulk_func(const struct rte_lpm *lpm, const uint32_t * ips,\n-\t\tuint16_t * next_hops, const unsigned n)\n-{\n-\tunsigned i;\n-\tunsigned tbl24_indexes[n];\n-\n-\t/* DEBUG: Check user input arguments. */\n-\tRTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (ips == NULL) ||\n-\t\t\t(next_hops == NULL)), -EINVAL);\n-\n-\tfor (i = 0; i < n; i++) {\n-\t\ttbl24_indexes[i] = ips[i] >> 8;\n-\t}\n-\n-\tfor (i = 0; i < n; i++) {\n-\t\t/* Simply copy tbl24 entry to output */\n-\t\tnext_hops[i] = *(const uint16_t *)&lpm->tbl24[tbl24_indexes[i]];\n-\n-\t\t/* Overwrite output with tbl8 entry if needed */\n-\t\tif (unlikely((next_hops[i] & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==\n-\t\t\t\tRTE_LPM_VALID_EXT_ENTRY_BITMASK)) {\n-\n-\t\t\tunsigned tbl8_index = (uint8_t)ips[i] +\n-\t\t\t\t\t((uint8_t)next_hops[i] *\n-\t\t\t\t\t RTE_LPM_TBL8_GROUP_NUM_ENTRIES);\n-\n-\t\t\tnext_hops[i] = *(const uint16_t *)&lpm->tbl8[tbl8_index];\n-\t\t}\n-\t}\n-\treturn 0;\n-}\n+void\n+rte_lpm_walk(struct rte_lpm *lpm, rte_lpm_walk_func_t func, void *arg);\n \n-/* Mask four results. */\n-#define\t RTE_LPM_MASKX4_RES\tUINT64_C(0x00ff00ff00ff00ff)\n+/**\n+ * Return the number of entries in the Tbl8 array\n+ *\n+ * @param lpm\n+ *   LPM object handle\n+ */\n+unsigned\n+rte_lpm_tbl8_count(const struct rte_lpm *lpm);\n \n /**\n- * Lookup four IP addresses in an LPM table.\n+ * Return the number of free entries in the Tbl8 array\n  *\n  * @param lpm\n  *   LPM object handle\n- * @param ip\n- *   Four IPs to be looked up in the LPM table\n- * @param hop\n- *   Next hop of the most specific rule found for IP (valid on lookup hit only).\n- *   This is an 4 elements array of two byte values.\n- *   If the lookup was succesfull for the given IP, then least significant byte\n- *   of the corresponding element is the  actual next hop and the most\n- *   significant byte is zero.\n- *   If the lookup for the given IP failed, then corresponding element would\n- *   contain default value, see description of then next parameter.\n- * @param defv\n- *   Default value to populate into corresponding element of hop[] array,\n- *   if lookup would fail.\n  */\n-static inline void\n-rte_lpm_lookupx4(const struct rte_lpm *lpm, __m128i ip, uint16_t hop[4],\n-\tuint16_t defv)\n+static inline unsigned\n+rte_lpm_tbl8_free_count(const struct rte_lpm *lpm)\n {\n-\t__m128i i24;\n-\trte_xmm_t i8;\n-\tuint16_t tbl[4];\n-\tuint64_t idx, pt;\n-\n-\tconst __m128i mask8 =\n-\t\t_mm_set_epi32(UINT8_MAX, UINT8_MAX, UINT8_MAX, UINT8_MAX);\n-\n-\t/*\n-\t * RTE_LPM_VALID_EXT_ENTRY_BITMASK for 4 LPM entries\n-\t * as one 64-bit value (0x0300030003000300).\n-\t */\n-\tconst uint64_t mask_xv =\n-\t\t((uint64_t)RTE_LPM_VALID_EXT_ENTRY_BITMASK |\n-\t\t(uint64_t)RTE_LPM_VALID_EXT_ENTRY_BITMASK << 16 |\n-\t\t(uint64_t)RTE_LPM_VALID_EXT_ENTRY_BITMASK << 32 |\n-\t\t(uint64_t)RTE_LPM_VALID_EXT_ENTRY_BITMASK << 48);\n-\n-\t/*\n-\t * RTE_LPM_LOOKUP_SUCCESS for 4 LPM entries\n-\t * as one 64-bit value (0x0100010001000100).\n-\t */\n-\tconst uint64_t mask_v =\n-\t\t((uint64_t)RTE_LPM_LOOKUP_SUCCESS |\n-\t\t(uint64_t)RTE_LPM_LOOKUP_SUCCESS << 16 |\n-\t\t(uint64_t)RTE_LPM_LOOKUP_SUCCESS << 32 |\n-\t\t(uint64_t)RTE_LPM_LOOKUP_SUCCESS << 48);\n-\n-\t/* get 4 indexes for tbl24[]. */\n-\ti24 = _mm_srli_epi32(ip, CHAR_BIT);\n-\n-\t/* extract values from tbl24[] */\n-\tidx = _mm_cvtsi128_si64(i24);\n-\ti24 = _mm_srli_si128(i24, sizeof(uint64_t));\n-\n-\ttbl[0] = *(const uint16_t *)&lpm->tbl24[(uint32_t)idx];\n-\ttbl[1] = *(const uint16_t *)&lpm->tbl24[idx >> 32];\n-\n-\tidx = _mm_cvtsi128_si64(i24);\n-\n-\ttbl[2] = *(const uint16_t *)&lpm->tbl24[(uint32_t)idx];\n-\ttbl[3] = *(const uint16_t *)&lpm->tbl24[idx >> 32];\n-\n-\t/* get 4 indexes for tbl8[]. */\n-\ti8.x = _mm_and_si128(ip, mask8);\n-\n-\tpt = (uint64_t)tbl[0] |\n-\t\t(uint64_t)tbl[1] << 16 |\n-\t\t(uint64_t)tbl[2] << 32 |\n-\t\t(uint64_t)tbl[3] << 48;\n-\n-\t/* search successfully finished for all 4 IP addresses. */\n-\tif (likely((pt & mask_xv) == mask_v)) {\n-\t\tuintptr_t ph = (uintptr_t)hop;\n-\t\t*(uint64_t *)ph = pt & RTE_LPM_MASKX4_RES;\n-\t\treturn;\n-\t}\n-\n-\tif (unlikely((pt & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==\n-\t\t\tRTE_LPM_VALID_EXT_ENTRY_BITMASK)) {\n-\t\ti8.u32[0] = i8.u32[0] +\n-\t\t\t(uint8_t)tbl[0] * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n-\t\ttbl[0] = *(const uint16_t *)&lpm->tbl8[i8.u32[0]];\n-\t}\n-\tif (unlikely((pt >> 16 & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==\n-\t\t\tRTE_LPM_VALID_EXT_ENTRY_BITMASK)) {\n-\t\ti8.u32[1] = i8.u32[1] +\n-\t\t\t(uint8_t)tbl[1] * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n-\t\ttbl[1] = *(const uint16_t *)&lpm->tbl8[i8.u32[1]];\n-\t}\n-\tif (unlikely((pt >> 32 & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==\n-\t\t\tRTE_LPM_VALID_EXT_ENTRY_BITMASK)) {\n-\t\ti8.u32[2] = i8.u32[2] +\n-\t\t\t(uint8_t)tbl[2] * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n-\t\ttbl[2] = *(const uint16_t *)&lpm->tbl8[i8.u32[2]];\n-\t}\n-\tif (unlikely((pt >> 48 & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==\n-\t\t\tRTE_LPM_VALID_EXT_ENTRY_BITMASK)) {\n-\t\ti8.u32[3] = i8.u32[3] +\n-\t\t\t(uint8_t)tbl[3] * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;\n-\t\ttbl[3] = *(const uint16_t *)&lpm->tbl8[i8.u32[3]];\n-\t}\n-\n-\thop[0] = (tbl[0] & RTE_LPM_LOOKUP_SUCCESS) ? (uint8_t)tbl[0] : defv;\n-\thop[1] = (tbl[1] & RTE_LPM_LOOKUP_SUCCESS) ? (uint8_t)tbl[1] : defv;\n-\thop[2] = (tbl[2] & RTE_LPM_LOOKUP_SUCCESS) ? (uint8_t)tbl[2] : defv;\n-\thop[3] = (tbl[3] & RTE_LPM_LOOKUP_SUCCESS) ? (uint8_t)tbl[3] : defv;\n+\treturn lpm->tbl8_num_groups - rte_lpm_tbl8_count(lpm);\n }\n \n #ifdef __cplusplus\n",
    "prefixes": [
        "dpdk-dev",
        "v1",
        "0/3"
    ]
}