From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from relay64.bu.edu (relay64.bu.edu [128.197.228.104]) by dpdk.org (Postfix) with ESMTP id A5B664C74 for ; Sun, 8 Jul 2018 23:47:11 +0200 (CEST) X-Envelope-From: qiaobinf@bu.edu X-BU-AUTH: xia1.bu.edu [128.197.41.97] Received: from BU-AUTH (localhost.localdomain [127.0.0.1]) (authenticated bits=0) by relay64.bu.edu (8.14.3/8.14.3) with ESMTP id w68LkCJS007903 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sun, 8 Jul 2018 17:46:19 -0400 From: Qiaobin Fu To: Bruce Richardson Cc: dev@dpdk.org, michel@digirati.com.br, doucette@bu.edu, qiaobinf@bu.edu Date: Sun, 8 Jul 2018 17:46:06 -0400 Message-Id: <20180708214606.124420-1-qiaobinf@bu.edu> X-Mailer: git-send-email 2.17.1 Subject: [dpdk-dev] [PATCH] LPM: add iterator over LPM rules X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 08 Jul 2018 21:47:11 -0000 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 Reviewed-by: Cody Doucette Reviewed-by: Michel Machado --- 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