From: Bruce Richardson <bruce.richardson@intel.com>
To: Vladimir Medvedkin <medvedkinv@gmail.com>
Cc: dev@dpdk.org, thomas@monjalon.net
Subject: Re: [dpdk-dev] [PATCH v3 1/2] Add RIB library
Date: Mon, 26 Mar 2018 10:55:41 +0100 [thread overview]
Message-ID: <20180326095541.GB17660@bricha3-MOBL.ger.corp.intel.com> (raw)
In-Reply-To: <CANDrEHmnkNnsX13C06XYXDCsqgHwQJtLzsinYVtQ=0NLb7Re0A@mail.gmail.com>
On Sun, Mar 25, 2018 at 09:35:35PM +0300, Vladimir Medvedkin wrote:
> 2018-03-15 17:27 GMT+03:00 Bruce Richardson <bruce.richardson@intel.com>:
>
> > On Thu, Feb 22, 2018 at 10:50:55PM +0000, Medvedkin Vladimir wrote:
> > > RIB is an alternative to current LPM library.
> > > It solves the following problems
> > > - Increases the speed of control plane operations against lpm such as
> > > adding/deleting routes
> > > - Adds abstraction from dataplane algorithms, so it is possible to add
> > > different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc
> > > in addition to current dir24_8
> > > - It is possible to keep user defined application specific additional
> > > information in struct rte_rib_node which represents route entry.
> > > It can be next hop/set of next hops (i.e. active and feasible),
> > > pointers to link rte_rib_node based on some criteria (i.e. next_hop),
> > > plenty of additional control plane information.
> > > - For dir24_8 implementation it is possible to remove
> > > rte_lpm_tbl_entry.depth field that helps to save 6 bits.
> > > - Also new dir24_8 implementation supports different next_hop sizes
> > > (1/2/4/8 bytes per next hop)
> > > - Removed RTE_LPM_LOOKUP_SUCCESS to save 1 bit and to eleminate
> > > ternary operator.
> > > Instead it returns special default value if there is no route.
> > >
> > > Signed-off-by: Medvedkin Vladimir <medvedkinv@gmail.com>
> >
> > More comments inline below. Mostly for rte_rib.c file.
> >
> > /Bruce
> >
<snip>
> >
> > > + while (cur != NULL) {
> > > + if ((cur->key == key) && (cur->depth == depth) &&
> > > + (cur->flag & RTE_RIB_VALID_NODE))
> > > + return cur;
> > > + if ((cur->depth > depth) ||
> > > + (((uint64_t)key >> (32 - cur->depth)) !=
> > > + ((uint64_t)cur->key >> (32 - cur->depth))))
> > > + break;
> > > + cur = RTE_RIB_GET_NXT_NODE(cur, key);
> > > + }
> > > + return NULL;
> > > +}
> > > +
> > > +struct rte_rib_node *
> > > +rte_rib_tree_get_nxt(struct rte_rib *rib, uint32_t key,
> > > + uint8_t depth, struct rte_rib_node *cur, int flag)
> > > +{
> > > + struct rte_rib_node *tmp, *prev = NULL;
> > > +
> > > + if (cur == NULL) {
> > > + tmp = rib->trie;
> > > + while ((tmp) && (tmp->depth < depth))
> > > + tmp = RTE_RIB_GET_NXT_NODE(tmp, key);
> > > + } else {
> > > + tmp = cur;
> > > + while ((tmp->parent != NULL) &&
> > (RTE_RIB_IS_RIGHT_NODE(tmp) ||
> > > + (tmp->parent->right == NULL))) {
> > > + tmp = tmp->parent;
> > > + if ((tmp->flag & RTE_RIB_VALID_NODE) &&
> > > + (RTE_RIB_IS_COVERED(tmp->key, tmp->depth,
> > > + key, depth)))
> > > + return tmp;
> > > + }
> > > + tmp = (tmp->parent) ? tmp->parent->right : NULL;
> > > + }
> > > + while (tmp) {
> > > + if ((tmp->flag & RTE_RIB_VALID_NODE) &&
> > > + (RTE_RIB_IS_COVERED(tmp->key, tmp->depth,
> > > + key, depth))) {
> > > + prev = tmp;
> > > + if (flag == RTE_RIB_GET_NXT_COVER)
> > > + return prev;
> > > + }
> > > + tmp = (tmp->left) ? tmp->left : tmp->right;
> > > + }
> > > + return prev;
> > > +}
> >
> > I think this function could do with some comments explaining the logic
> > behind it.
> >
> This function traverses on subtree and retrieves more specific routes for a
> given in args key/depth prefix (treat it like a top of the subtree).
> Traverse without using recursion but using some kind of stack. It uses *cur
> argument like a pointer to the last returned node to resume retrieval after
> cur node.
>
Yes. Please add such an explanation into the code for future patches. [Same
with the other additional explanations in your reply email].
Thanks,
/Bruce
next prev parent reply other threads:[~2018-03-26 9:55 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-02-22 22:50 [dpdk-dev] [PATCH v3 0/2] lib/rib: Add Routing Information Base library Medvedkin Vladimir
2018-02-22 22:50 ` [dpdk-dev] [PATCH v3 1/2] Add RIB library Medvedkin Vladimir
2018-03-14 11:58 ` Bruce Richardson
2018-03-15 14:27 ` Bruce Richardson
2018-03-25 18:35 ` Vladimir Medvedkin
2018-03-26 9:55 ` Bruce Richardson [this message]
2018-02-22 22:50 ` [dpdk-dev] [PATCH v3 2/2] Add autotests for " Medvedkin Vladimir
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180326095541.GB17660@bricha3-MOBL.ger.corp.intel.com \
--to=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=medvedkinv@gmail.com \
--cc=thomas@monjalon.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).