Re: [PATCH v3 1/2] Add RIB library

[Bruce Richardson <bruce.richardson@intel.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