[PATCH] LPM: add iterator over LPM rules

[PATCH] LPM: add iterator over LPM rules

[Qiaobin Fu]

Add an iterator over the LPM rules.
The iterator requires a prefix as a parameter and
lists all entries as long as the given prefix (or longer).

Signed-off-by: Qiaobin Fu <qiaobinf@bu.edu>
Reviewed-by: Cody Doucette <doucette@bu.edu>
Reviewed-by: Michel Machado <michel@digirati.com.br>
---
 lib/librte_lpm/rte_lpm.c  | 99 +++++++++++++++++++++++++++++++++++++++
 lib/librte_lpm/rte_lpm.h  | 55 ++++++++++++++++++++++
 lib/librte_lpm/rte_lpm6.c | 82 +++++++++++++++++++++++++++++---
 lib/librte_lpm/rte_lpm6.h | 56 ++++++++++++++++++++++
 4 files changed, 285 insertions(+), 7 deletions(-)

diff --git a/lib/librte_lpm/rte_lpm.c b/lib/librte_lpm/rte_lpm.c
index d00b13d93..17cc49a86 100644
--- a/lib/librte_lpm/rte_lpm.c
+++ b/lib/librte_lpm/rte_lpm.c
@@ -85,6 +85,105 @@ depth_to_range(uint8_t depth)
 	return 1 << (RTE_LPM_MAX_DEPTH - depth);
 }
 
+int
+rte_lpm_iterator_state_init(const struct rte_lpm *lpm, uint32_t ip,
+	uint8_t depth, struct rte_lpm_iterator_state *state)
+{
+	if (lpm == NULL || depth > RTE_LPM_MAX_DEPTH || state == NULL)
+		return -EINVAL;
+
+	state->dmask = depth_to_mask(depth);
+	state->ip_masked = ip & state->dmask;
+	state->depth = depth == 0 ? 1 : depth;
+	state->next = 0;
+	state->lpm = lpm;
+
+	return 0;
+}
+
+/*
+ * An iterator over its rule entries.
+ */
+int
+rte_lpm_rule_iterate_v20(struct rte_lpm_iterator_state *state,
+	const struct rte_lpm_rule **rule)
+{
+	if (state == NULL || rule == NULL) {
+		if (rule != NULL)
+			*rule = NULL;
+
+		return -EINVAL;
+	}
+
+	while (state->depth <= RTE_LPM_MAX_DEPTH) {
+		uint32_t rule_gindex =
+			state->lpm->rule_info[state->depth - 1].first_rule;
+		uint32_t last_rule = rule_gindex +
+			state->lpm->rule_info[state->depth - 1].used_rules;
+		uint32_t rule_index = rule_gindex + state->next;
+
+		while (rule_index < last_rule) {
+			if ((state->lpm->rules_tbl[rule_index].ip &
+					state->dmask) == state->ip_masked) {
+				state->next = rule_index - rule_gindex + 1;
+				*rule = (const struct rte_lpm_rule *)
+					&state->lpm->rules_tbl[rule_index];
+				return 0;
+			}
+
+			rule_index++;
+		}
+
+		state->depth++;
+		state->next = 0;
+	}
+
+	*rule = NULL;
+	return -ENOENT;
+}
+VERSION_SYMBOL(rte_lpm_rule_iterate, _v20, 2.0);
+
+int
+rte_lpm_rule_iterate_v1604(struct rte_lpm_iterator_state *state,
+	const struct rte_lpm_rule **rule)
+{
+	if (state == NULL || rule == NULL) {
+		if (rule != NULL)
+			*rule = NULL;
+
+		return -EINVAL;
+	}
+
+	while (state->depth <= RTE_LPM_MAX_DEPTH) {
+		uint32_t rule_gindex =
+			state->lpm->rule_info[state->depth - 1].first_rule;
+		uint32_t last_rule = rule_gindex +
+			state->lpm->rule_info[state->depth - 1].used_rules;
+		uint32_t rule_index = rule_gindex + state->next;
+
+		while (rule_index < last_rule) {
+			if ((state->lpm->rules_tbl[rule_index].ip &
+					state->dmask) == state->ip_masked) {
+				state->next = rule_index - rule_gindex + 1;
+				*rule = (const struct rte_lpm_rule *)
+					&state->lpm->rules_tbl[rule_index];
+				return 0;
+			}
+
+			rule_index++;
+		}
+
+		state->depth++;
+		state->next = 0;
+	}
+
+	*rule = NULL;
+	return -ENOENT;
+}
+BIND_DEFAULT_SYMBOL(rte_lpm_rule_iterate, _v1604, 16.04);
+MAP_STATIC_SYMBOL(int rte_lpm_rule_iterate(struct rte_lpm_iterator_state *state,
+	const struct rte_lpm_rule **rule), rte_lpm_rule_iterate_v1604);
+
 /*
  * Find an existing lpm table and return a pointer to it.
  */
diff --git a/lib/librte_lpm/rte_lpm.h b/lib/librte_lpm/rte_lpm.h
index 21550444d..c1311c67a 100644
--- a/lib/librte_lpm/rte_lpm.h
+++ b/lib/librte_lpm/rte_lpm.h
@@ -188,6 +188,61 @@ struct rte_lpm {
 	struct rte_lpm_rule *rules_tbl; /**< LPM rules. */
 };
 
+/** LPM iterator state structure. */
+struct rte_lpm_iterator_state {
+	uint32_t dmask;
+	uint32_t ip_masked;
+	uint8_t  depth;
+	uint32_t next;
+	const struct rte_lpm *lpm;
+};
+
+/**
+ * Initialize the lpm iterator state.
+ *
+ * @param lpm
+ *   LPM object handle
+ * @param ip
+ *   IP of the rule to be searched
+ * @param depth
+ *   Initial depth of the rule to be searched.
+ *   Pass zero to enumerate the whole LPM table.
+ * @param state
+ *   Pointer to the iterator state
+ * @return
+ *   0 on successfully initialize the state variable, negative otherwise.
+ *   Possible error values include:
+ *   - EINVAL - invalid parameter passed to function
+ */
+int
+rte_lpm_iterator_state_init(const struct rte_lpm *lpm, uint32_t ip,
+	uint8_t depth, struct rte_lpm_iterator_state *state);
+
+/**
+ * An iterator over its rule entries.
+ * The iterator should require a prefix as a parameter
+ * and should list all entries as long as the given prefix (or longer).
+ *
+ * @param state
+ *   Pointer to the LPM rule iterator state
+ * @param rule
+ *   Pointer to the next rule entry
+ * @return
+ *   0 on successfully searching the next rule entry, negative otherwise.
+ *   Possible error values include:
+ *   - EINVAL - invalid parameter passed to function
+ *   - ENOENT - no rule entries found
+ */
+int
+rte_lpm_rule_iterate(struct rte_lpm_iterator_state *state,
+	const struct rte_lpm_rule **rule);
+int
+rte_lpm_rule_iterate_v20(struct rte_lpm_iterator_state *state,
+	const struct rte_lpm_rule **rule);
+int
+rte_lpm_rule_iterate_v1604(struct rte_lpm_iterator_state *state,
+	const struct rte_lpm_rule **rule);
+
 /**
  * Create an LPM object.
  *
diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
index 149677eb1..b2a9b0da7 100644
--- a/lib/librte_lpm/rte_lpm6.c
+++ b/lib/librte_lpm/rte_lpm6.c
@@ -63,13 +63,6 @@ struct rte_lpm6_tbl_entry {
 	uint32_t ext_entry :1;   /**< External entry. */
 };
 
-/** Rules tbl entry structure. */
-struct rte_lpm6_rule {
-	uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
-	uint32_t next_hop; /**< Rule next hop. */
-	uint8_t depth; /**< Rule depth. */
-};
-
 /** LPM6 structure. */
 struct rte_lpm6 {
 	/* LPM metadata. */
@@ -111,6 +104,81 @@ mask_ip(uint8_t *ip, uint8_t depth)
 		}
 }
 
+int
+rte_lpm6_iterator_state_init(const struct rte_lpm6 *lpm, uint8_t *ip,
+	uint8_t depth, struct rte_lpm6_iterator_state *state)
+{
+	if (lpm == NULL || depth > RTE_LPM6_MAX_DEPTH || state == NULL)
+		return -EINVAL;
+
+	if (ip == NULL)
+		memset(state->ip_masked, 0, sizeof(state->ip_masked));
+	else {
+		rte_memcpy(state->ip_masked, ip, sizeof(state->ip_masked));
+		mask_ip(state->ip_masked, depth);
+	}
+
+	state->depth = depth;
+	state->next = 0;
+	state->lpm = lpm;
+
+	return 0;
+}
+
+/*
+ * An iterator over its rule entries.
+ */
+int
+rte_lpm6_rule_iterate(struct rte_lpm6_iterator_state *state,
+	const struct rte_lpm6_rule **rule)
+{
+	uint32_t index;
+
+	/* Check user arguments. */
+	if (state == NULL || rule == NULL) {
+		if (rule != NULL)
+			*rule = NULL;
+
+		return -EINVAL;
+	}
+
+	if (state->next >= state->lpm->used_rules) {
+		*rule = NULL;
+		return -ENOENT;
+	}
+
+	index = state->next;
+
+	/* Scan used rules to find rules. */
+	while (index < state->lpm->used_rules) {
+		uint8_t rule_ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
+
+		if (state->lpm->rules_tbl[index].depth < state->depth) {
+			index++;
+			continue;
+		}
+
+		rte_memcpy(rule_ip_masked, state->lpm->rules_tbl[index].ip,
+			RTE_LPM6_IPV6_ADDR_SIZE);
+		mask_ip(rule_ip_masked, state->depth);
+
+		/* If rule is found return the rule index. */
+		if ((memcmp(state->ip_masked, rule_ip_masked,
+				RTE_LPM6_IPV6_ADDR_SIZE) == 0)) {
+			state->next = index + 1;
+			*rule = (const struct rte_lpm6_rule *)
+				&state->lpm->rules_tbl[index];
+			return 0;
+		}
+
+		index++;
+	}
+
+	state->next = index;
+	*rule = NULL;
+	return -ENOENT;
+}
+
 /*
  * Allocates memory for LPM object
  */
diff --git a/lib/librte_lpm/rte_lpm6.h b/lib/librte_lpm/rte_lpm6.h
index 5d59ccb1f..b8a394f6d 100644
--- a/lib/librte_lpm/rte_lpm6.h
+++ b/lib/librte_lpm/rte_lpm6.h
@@ -22,6 +22,13 @@ extern "C" {
 /** Max number of characters in LPM name. */
 #define RTE_LPM6_NAMESIZE                 32
 
+/** Rules tbl entry structure. */
+struct rte_lpm6_rule {
+	uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
+	uint8_t next_hop; /**< Rule next hop. */
+	uint8_t depth; /**< Rule depth. */
+};
+
 /** LPM structure. */
 struct rte_lpm6;
 
@@ -32,6 +39,55 @@ struct rte_lpm6_config {
 	int flags;               /**< This field is currently unused. */
 };
 
+/** LPM6 iterator state structure. */
+struct rte_lpm6_iterator_state {
+	uint8_t  ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
+	uint8_t  depth;
+	uint32_t next;
+	const struct rte_lpm6 *lpm;
+};
+
+/**
+ * Initialize the lpm iterator state.
+ *
+ * @param lpm
+ *   LPM object handle
+ * @param ip
+ *   IP of the rule to be searched
+ *   ip == NULL behaves as having passed an all-zero IPv6 address
+ * @param depth
+ *   Initial depth of the rule to be searched.
+ *   Pass zero to enumerate the whole LPM table.
+ * @param state
+ *   Pointer to the iterator state
+ * @return
+ *   0 on successfully initialize the state variable, negative otherwise.
+ *   Possible error values include:
+ *   - EINVAL - invalid parameter passed to function
+ */
+int
+rte_lpm6_iterator_state_init(const struct rte_lpm6 *lpm, uint8_t *ip,
+	uint8_t depth, struct rte_lpm6_iterator_state *state);
+
+/**
+ * An iterator over its rule entries.
+ * The iterator should require a prefix as a parameter
+ * and should list all entries as long as the given prefix (or longer).
+ *
+ * @param state
+ *   Pointer to the LPM rule iterator state
+ * @param rule
+ *   Pointer to the next rule entry
+ * @return
+ *   0 on successfully searching the next rule entry, negative otherwise.
+ *   Possible error values include:
+ *   - EINVAL - invalid parameter passed to function
+ *   - ENOENT - no rule entries found
+ */
+int
+rte_lpm6_rule_iterate(struct rte_lpm6_iterator_state *state,
+	const struct rte_lpm6_rule **rule);
+
 /**
  * Create an LPM object.
  *
-- 
2.17.1

Re: [PATCH] LPM: add iterator over LPM rules

[Thomas Monjalon]

08/07/2018 23:46, Qiaobin Fu:
> Add an iterator over the LPM rules.
> The iterator requires a prefix as a parameter and
> lists all entries as long as the given prefix (or longer).
> 
> Signed-off-by: Qiaobin Fu <qiaobinf@bu.edu>
> Reviewed-by: Cody Doucette <doucette@bu.edu>
> Reviewed-by: Michel Machado <michel@digirati.com.br>

Any news about this patch?

Re: [PATCH] LPM: add iterator over LPM rules

[Fu, Qiaobin]

Hi Thomas,

We are currently working on the patch by incorporating the latest DPDK update, and will submit a new patch on this.

Thanks,
Qiaobin

> On Oct 28, 2018, at 6:24 AM, Thomas Monjalon <thomas@monjalon.net> wrote:
> 
> 08/07/2018 23:46, Qiaobin Fu:
>> Add an iterator over the LPM rules.
>> The iterator requires a prefix as a parameter and
>> lists all entries as long as the given prefix (or longer).
>> 
>> Signed-off-by: Qiaobin Fu <qiaobinf@bu.edu>
>> Reviewed-by: Cody Doucette <doucette@bu.edu>
>> Reviewed-by: Michel Machado <michel@digirati.com.br>
> 
> Any news about this patch?
> 
> 
> 

Re: [PATCH] LPM: add iterator over LPM rules

[Stephen Hemminger]

This patch is old, no longer applies and is incomplete.
There are no new tests, and no useful examples for using it.
It should be rejected.

Re: [PATCH 1/2] eal/bitmap: support bitmap reverse scanning

[Stephen Hemminger]

This patch is old, no longer applies and is incomplete.
There are no new tests, and no useful examples for using it.
It should be rejected.