[ovs-git] [openvswitch/ovs] 1c4dd4: lib: Add new 'counting cmap' type.

[GitHub]

  Branch: refs/heads/master
  Home:   https://github.com/openvswitch/ovs
  Commit: 1c4dd4246c2776a58b5c5a78db0d5581edf4205b
      https://github.com/openvswitch/ovs/commit/1c4dd4246c2776a58b5c5a78db0d5581edf4205b
  Author: Jarno Rajahalme <jarno at ovn.org>
  Date:   2016-05-16 (Mon, 16 May 2016)

  Changed paths:
    M lib/automake.mk
    A lib/ccmap.c
    A lib/ccmap.h
    M tests/automake.mk
    M tests/library.at
    A tests/test-ccmap.c

  Log Message:
  -----------
  lib: Add new 'counting cmap' type.

cmap implements duplicates as linked lists, which causes removal of
rules to become (O^2) with large number of duplicates.  This patch
fixes the problem by introducing a new 'counting' 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 user implementation a bit more
memory efficient, too.

Signed-off-by: Jarno Rajahalme <jarno at ovn.org>
Acked-by: Ben Pfaff <blp at ovn.org>


  Commit: 59936df6f45cf554ca201a08d8335af04d82a82c
      https://github.com/openvswitch/ovs/commit/59936df6f45cf554ca201a08d8335af04d82a82c
  Author: Jarno Rajahalme <jarno at ovn.org>
  Date:   2016-05-16 (Mon, 16 May 2016)

  Changed paths:
    M lib/classifier-private.h
    M lib/classifier.c

  Log Message:
  -----------
  classifier: Use ccmaps for staged lookup indices.

Use the new ccmap type instead of cmap for staged lookup indices to
fix the problem with slow removal of rules 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), causing a large number of duplicates to be inserted into the
staged lookup index.  ccmap only keeps the count of inserted (hash)
values, so duplicates do not add any performance penalty.

Reported-by: Alok Kumar Maurya <alok-kumar.maurya at hpe.com>
Signed-off-by: Jarno Rajahalme <jarno at ovn.org>
Acked-by: Ben Pfaff <blp at ovn.org>


Compare: https://github.com/openvswitch/ovs/compare/9baaabfff3c7...59936df6f45c