[ovs-dev] [PATCH 4/4] classifier: Avoid inserting duplicates to cmaps.

Ryan Moats rmoats at us.ibm.com
Mon Apr 18 20:29:40 UTC 2016


> --- Original Message ---
> Staged lookup indices assumed that cmap is efficient fealing with
> duplicates.  Duplicates are implemented as linked lists, however,
> causing removal of rules to become (O^2) and highly cache-inefficient
> with large number of duplicates.
>
> This was problematic especially when many rules shared the same match
> in packet metadata (e.g., a port number, but nothing else).
>
> This patch fixes the problem by introducing a new 'count' variant of
> the cmap (ccmap), which can be efficiently used to keep counts of
> inserted hash values provided by the caller.  This does not require a
> node in the user data structure, so this makes the classifier
> implementation a bit more memory efficient, too.
>
> Reported-by: Alok Kumar Maurya <alok-kumar.maurya at hpe.com>
> Signed-off-by: Jarno Rajahalme <jarno at ovn.org>
> ---

Acked-by: Ryan Moats <rmoats at us.ibm.com>



More information about the dev mailing list