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

[Alex Kiselev]

>> +     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. 

>> +
>> +     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.

>> +}
>> +
>> +/*
>> + * 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 :)
  

>>  }
>> -- 
> 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. 

> Regards,
> /Bruce



-- 
Alex