Re: [PATCH] lpm: rte_lpm_iterate() - iterate through the routes

CC: dev@dpdk.org. Missed that address when pulling from email archive.

-----Original Message-----
From: Bruce Richardson [mailto:bruce.richardson@intel.com]
Sent: Wednesday, February 22, 2017 1:39 PM
To: chunguang yang <redacted>
Subject: Re: [dpdk-dev] [PATCH] lpm: rte_lpm_iterate() - iterate through
the routes

On Fri, Nov 25, 2016 at 01:31:31AM -0500, chunguang yang wrote:

quoted

From: J?rgen Grahn <redacted>

In practice, there's a need to iterate through the entries of a
rte_lpm, apart from the usual insert/delete/lookup operations.  This
is useful for debugging and perhaps for things like removing all
entries referencing a certain nexthop.

This patch implements this through rte_lpm_iterate(), which uses a
cursor (or iterator) to keep track of the current position.  Client
code doesn't need to be aware of rte_lpm implementation details.

Change-Id: I28ea3d7d92f318988444553ee2bb30b709bcb3b6
Signed-off-by: Jorgen Grahn <redacted>
Signed-off-by: alloc <redacted>

Apologies for the late review, I missed this patch at the time and only
spotted it in patchwork now.

First off, there are a number of checkpatch issues flagged by the
automated scan. If you still want to continue with this patch for 17.05
release, you should resubmit with those fixed. Other review comments
inline below too.

/Bruce

quoted

---
 lib/librte_lpm/Makefile          |  4 +-
 lib/librte_lpm/rte_lpm_iterate.c | 81
++++++++++++++++++++++++++++++++++++++++
 lib/librte_lpm/rte_lpm_iterate.h | 56 +++++++++++++++++++++++++++
 3 files changed, 139 insertions(+), 2 deletions(-)  create mode
100644 lib/librte_lpm/rte_lpm_iterate.c  create mode 100644
lib/librte_lpm/rte_lpm_iterate.h

diff --git a/lib/librte_lpm/Makefile b/lib/librte_lpm/Makefile index

3dc549d..c45da19 100644

--- a/lib/librte_lpm/Makefile
+++ b/lib/librte_lpm/Makefile

@@ -42,10 +42,10 @@ EXPORT_MAP := rte_lpm_version.map  LIBABIVER := 2

 # all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_LPM) := rte_lpm.c rte_lpm6.c
+SRCS-$(CONFIG_RTE_LIBRTE_LPM) := rte_lpm.c rte_lpm6.c
+rte_lpm_iterate.c

I don't see any reason why this needs to be in a new file. Can you
consider merging it into the existing rte_lpm.c/.h files.
What about an implementation for IPv6? Any plans for an equivalent
implementation.

quoted

 # install this header file
-SYMLINK-$(CONFIG_RTE_LIBRTE_LPM)-include := rte_lpm.h rte_lpm6.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_LPM)-include := rte_lpm.h rte_lpm6.h
+rte_lpm_iterate.h

 ifneq ($(filter y,$(CONFIG_RTE_ARCH_ARM) $(CONFIG_RTE_ARCH_ARM64)),)
SYMLINK-$(CONFIG_RTE_LIBRTE_LPM)-include += rte_lpm_neon.h diff --git
a/lib/librte_lpm/rte_lpm_iterate.c b/lib/librte_lpm/rte_lpm_iterate.c
new file mode 100644
index 0000000..f643764

--- /dev/null
+++ b/lib/librte_lpm/rte_lpm_iterate.c

@@ -0,0 +1,81 @@
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2014 J?rgen Grahn. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above

copyright

quoted

+ *       notice, this list of conditions and the following disclaimer

in

quoted

+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Intel Corporation nor the names of its
+ *       contributors may be used to endorse or promote products

derived

quoted

+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND

CONTRIBUTORS

quoted

+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS

FOR

quoted

+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE

COPYRIGHT

quoted

+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

INCIDENTAL,

quoted

+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF

USE,

quoted

+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON

ANY

quoted

+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR

TORT

quoted

+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE

USE

quoted

+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH

DAMAGE.

quoted

+ */
+#include "rte_lpm_iterate.h"
+#include "rte_lpm.h"
+
+#include <arpa/inet.h>
+
+
+/**
+ * Iterate through the lpm, pulling out at most 'buflen' valid routes
+ * (less means we've hit the end).  The cursor should be initialized
+ * to { 0, 0 } before the first call.
+ *
+ * The routes are partially sorted, by prefix length.  Undefined
+ * results if the lpm is modified in parallel with or inbetween
+calls,
+ * although the iteration will still terminate properly.
+ */
+unsigned
+rte_lpm_iterate(struct rte_lpm_route* const buf, unsigned buflen,
+		const struct rte_lpm* lpm,
+		struct rte_lpm_cursor* const cursor)

For the lpm library functions, the lpm parameter is given first. I think
this should be the same, for consistency.

quoted

+{
+	struct rte_lpm_route* p = buf;
+	struct rte_lpm_route* const end = p + buflen;
+
+	const struct rte_lpm_rule_info* const rinfo = lpm->rule_info;
+	const struct rte_lpm_rule* const rtbl = lpm->rules_tbl;
+
+	unsigned d = cursor->d;
+	unsigned n = cursor->n;
+
+	while(p!=end) {
+		if(d==32) break;
+		if(n>=rinfo[d].used_rules) {
+			d++;
+			n = 0;
+			continue;
+		}
+		const struct rte_lpm_rule rule = rtbl[rinfo[d].first_rule +

n];

quoted

+		p->addr.s_addr = htonl(rule.ip);
+		p->plen = d+1;
+		p->nh = rule.next_hop;
+		p++;
+		n++;
+	}
+
+	cursor->d = d;
+	cursor->n = n;
+
+	return p - buf;
+}

My impression from the description and the function title "iterate" was
that this would iterate through the lpm table itself, returning all ip
address and next hop matchings. Instead, it appears that this just returns
the rules from the rules table.

Given this, I think the function name and behaviour might be better as
"rte_lpm_get_rules(lpm, lpm_rules_buffer, num_rules, start_idx)"
where up to num_rules as filled into lpm_rules_buffer, starting at rule
start_idx in the list. The return value should indicate the number of
rules that would be filled into lpm_rules_buffer if it had space. This is
a standard approach we use for situations like this - if retval <
num_rules, you have them all, otherwise you need to query again. If you
want, it's also easy to get all the rules in one go - just make a call
first with a zero-buffer size, and then use the return value to allocate a
suitably-sized buffer and call a second time.

quoted

diff --git a/lib/librte_lpm/rte_lpm_iterate.h

b/lib/librte_lpm/rte_lpm_iterate.h
new file mode 100644
index 0000000..25c7841

--- /dev/null
+++ b/lib/librte_lpm/rte_lpm_iterate.h

@@ -0,0 +1,56 @@
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2014 J?rgen Grahn. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above

copyright

quoted

+ *       notice, this list of conditions and the following disclaimer

in

quoted

+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Intel Corporation nor the names of its
+ *       contributors may be used to endorse or promote products

derived

quoted

+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND

CONTRIBUTORS

quoted

+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS

FOR

quoted

+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE

COPYRIGHT

quoted

+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

INCIDENTAL,

quoted

+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF

USE,

quoted

+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON

ANY

quoted

+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR

TORT

quoted

+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE

USE

quoted

+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH

DAMAGE.

quoted

+ */
+#ifndef _RTE_LPM_ITERATE_H_
+#define _RTE_LPM_ITERATE_H_
+
+#include <stdint.h>
+#include <netinet/in.h>
+
+struct rte_lpm;
+
+struct rte_lpm_cursor {
+	unsigned d;
+	unsigned n;
+};

While I don't think we need a "cursor" structure - see my proposed API
above, if we do have one, I think it should be made opaque with an API to
initialize it.

quoted

+
+struct rte_lpm_route {
+	struct in_addr addr;
+	uint8_t plen;
+	uint8_t nh;
+};
+
+unsigned rte_lpm_iterate(struct rte_lpm_route* buf, unsigned buflen,
+			 const struct rte_lpm* lpm,
+			 struct rte_lpm_cursor* cursor);
+
+#endif
--
2.7.4