[dpdk-dev] [PATCH v2] librte_lpm: Improve performance of the delete and add functions

[Bruce Richardson]

On Mon, Jul 09, 2018 at 03:33:44PM +0300, Alex Kiselev wrote:
> >> +     int ret = rte_hash_lookup_data(lpm->rules_tbl, (void *) &rule_key,
> >> +             (void **) &rule);
> >> +     if (ret >= 0) {
> >> +             /* delete the rule */
> >> +             rte_hash_del_key(lpm->rules_tbl, (void *) &rule_key);
> >> +             lpm->used_rules--;
> >> +             rte_mempool_put(lpm->rules_pool, rule);
> >> +     }
> 
> > Rather than doing a lookup and then delete, why not just try the delete
> > straight off. If you want to check for the key not being present, it can be
> > detected from the output of the delete call. From rte_hash.h:
> 
> >  * @return
> >  *   - -EINVAL if the parameters are invalid.
> >  *   - -ENOENT if the key is not found.
> 
> A deleted rule has to be returned back to the mempool.
> And I don't see any delete function in the rte_hash that can
> return a deleted item back to a caller. 
> 
Good point, never mind my comment, so.

> >> +
> >> +     return ret;
> >>  }
> >>  
> >>  /*
> >> - * Deletes a rule
> >> + * Deletes a group of rules
> 
> > Include a comment that this bulk function will rebuild the lpm table,
> > rather than doing incremental updates like the regular delete function.
> ok
> 
> 
> >> + * Convert a depth to a one byte long mask
> >> + */
> >> +static uint8_t __attribute__((pure))
> >> +depth_to_mask_1b(uint8_t depth)
> >> +{
> >> +     /* To calculate a mask start with a 1 on the left hand side and right
> >> +      * shift while populating the left hand side with 1's
> >>        */
> >> -     if ((lpm == NULL) || (ips == NULL) || (depths == NULL)) {
> >> -             return -EINVAL;
> >> +     return (signed char)0x80 >> (depth - 1);
> 
> > I'd make the comment on the function a little clearer e.g. using an
> example: "4 =>> 0xF0", which should remove the need to have the second comment
> > above the return statement.
> 
> > An alternative that might be a little clearer for the calculation would be:
> "(uint8_t)(~(0xFF >>> depth))".
> 
> I've just copied this function from rte_lpm.c and converted it to 1byte version.
> I'll add an example 4 =>> 0xF0.
> 
Ok. Keeping the code as-is is fine.

> >> +}
> >> +
> >> +/*
> >> + * Find a less specific rule
> >> + */
> >> +static struct rte_lpm6_rule*
> >> +rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
> >> +{
> >> +     if (depth == 1)
> >> +             return NULL;
> >> +
> >> +     struct rte_lpm6_rule *rule;
> >> +     struct rte_lpm6_rule_key rule_key;
> >> +     rule_key_init(&rule_key, ip, depth);
> >> +     uint8_t mask;
> >> +
> >> +     while (depth > 1) {
> >> +             depth--;
> >> +
> >> +             /* each iteration zero one more bit of the key */
> >> +             mask = depth & 7; /* depth % 8 */
> >> +             if (mask > 0)
> >> +                     mask = depth_to_mask_1b(mask);
> >> +
> >> +             rule_key.depth = depth;
> >> +             rule_key.ip[depth >> 3] &= mask;
> >> +
> 
> > It seems strange that when you adjust the depth, you also need to mask out
> > bits of the key which should be ignored. Can you make the masking part of
> > the hash calculation, which would simplify the logic here a lot, and if so,
> > does it affect performance much?
> 
> The first version of rule_find_less_specific() was doing exactly what you are proposing,
> masking whole ipv6 address every time. But then I just couldn't stop myself from
> using this shortcut since it's a performance optimization patch.
> 
> So, yes, it could be a part of the hash calculation, but why? It's definetly not
> the most difficult part of the algorithm (even without this optimizations), 
> so it would not make life easier :)
>   

Ok, makes sense.

> >>  }
> >> -- 
> > Rest of the patch looks fine to me, though I can't say I've followed all
> > the logic paths in full detail.
> 
> > Main concern I have about the patch is the size. Is there any way this
> > patch could be split up into a few smaller ones with more gradual changes?
> I could try to split it in two parts. The first part will introduce the new rule
> subsystem using a hashtable instead of a flat array. And the second one will include
> the rest. 
> 
Please attempt to do so, if possible, for the next version.

Thanks,
/Bruce