On Sun, Mar 25, 2018 at 09:35:35PM +0300, Vladimir Medvedkin wrote:
> 2018-03-15 17:27 GMT+03:00 Bruce Richardson <bruce.richard...@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 <medvedk...@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
