[dpdk-dev] [RFC] Add Membership Library

[Yipeng Wang]

A proposal for a new DPDK library that is called “Membership Library”. It
provides an API for DPDK applications to insert a new member, delete an existing
member, or query the existence of a member in a given set, or a group of sets.
For the case of a group of sets the library will return not only whether the
element has been inserted before in one of the sets but also which set it
belongs to.

The Membership Library is an extension and generalization of a traditional
filter (for example Bloom Filter) structure that has multiple usages in a wide
variety of workloads and applications. In general, the Membership Library is a
data structure that provides a “set-summary” and responds to set-membership
queries whether a certain member belongs to a set(s). There are two advantages
of using such a set-summary rather than operating on a “full-blown” complete
list of elements: firstly it has a much smaller storage requirement than storing
the whole list of elements themselves, and secondly checking an element
membership (or other operations) in this set-summary is much faster than
checking it for the original full-blown complete list of elements.

A membership test for an element will return the set this element belongs to or
null (meaning not found) with very high probability of accuracy. Set-summary is
a fundamental data aggregation component that can be used in many network
(and other) applications. It is a crucial structure to address performance and
scalability issues of diverse network applications including overlay networks,
wild card flow classification, web-caches, load balancing, connection tracking,
data-centric networks, flow table summaries, network statistics and traffic
monitoring.

Our Proof of Concept (PoC) using membership library to optimize flow lookup for
Open vSwitch (OvS) shows a speed up of about 3X.

Signed-off-by: Yipeng Wang<Yipeng1.wang at intel.com>
Signed-off-by: Sameh Gobriel<sameh.gobriel at intel.com>
Signed-off-by: Charlie Tai<charlie.tai at intel.com>
Signed-off-by: Ren Wang<ren.wang at intel.com>

Yipeng Wang (1):
  Add Membership Library

 MAINTAINERS                                      |    7 +
 config/defconfig_x86_64-native-linuxapp-gcc      |    3 +
 doc/guides/prog_guide/img/memship_i1.svg         | 1269 ++++++++++++++++++++++
 doc/guides/prog_guide/img/memship_i2.svg         |   36 +
 doc/guides/prog_guide/img/memship_i3.svg         |  148 +++
 doc/guides/prog_guide/img/memship_i4.svg         |  428 ++++++++
 doc/guides/prog_guide/img/memship_i5.svg         |  123 +++
 doc/guides/prog_guide/img/memship_i6.svg         |  233 ++++
 doc/guides/prog_guide/img/memship_i7.svg         |  277 +++++
 doc/guides/prog_guide/index.rst                  |   14 +
 doc/guides/prog_guide/membership_lib.rst         |  421 +++++++
 lib/Makefile                                     |    3 +-
 lib/librte_eal/common/eal_common_log.c           |    1 +
 lib/librte_eal/common/include/rte_log.h          |    1 +
 lib/librte_membership/Makefile                   |   48 +
 lib/librte_membership/rte_membership.c           |  378 +++++++
 lib/librte_membership/rte_membership.h           |  321 ++++++
 lib/librte_membership/rte_membership_bf.c        |  254 +++++
 lib/librte_membership/rte_membership_bf.h        |   99 ++
 lib/librte_membership/rte_membership_cache.c     |  345 ++++++
 lib/librte_membership/rte_membership_cache.h     |   95 ++
 lib/librte_membership/rte_membership_ht.c        |  471 ++++++++
 lib/librte_membership/rte_membership_ht.h        |   98 ++
 lib/librte_membership/rte_membership_vbf.c       |  391 +++++++
 lib/librte_membership/rte_membership_vbf.h       |   85 ++
 lib/librte_membership/rte_membership_version.map |   15 +
 mk/rte.app.mk                                    |    1 +
 test/test/Makefile                               |    2 +
 test/test/test_membership.c                      |  459 ++++++++
 29 files changed, 6025 insertions(+), 1 deletion(-)
 create mode 100644 doc/guides/prog_guide/img/memship_i1.svg
 create mode 100644 doc/guides/prog_guide/img/memship_i2.svg
 create mode 100644 doc/guides/prog_guide/img/memship_i3.svg
 create mode 100644 doc/guides/prog_guide/img/memship_i4.svg
 create mode 100644 doc/guides/prog_guide/img/memship_i5.svg
 create mode 100644 doc/guides/prog_guide/img/memship_i6.svg
 create mode 100644 doc/guides/prog_guide/img/memship_i7.svg
 create mode 100644 doc/guides/prog_guide/membership_lib.rst
 create mode 100644 lib/librte_membership/Makefile
 create mode 100644 lib/librte_membership/rte_membership.c
 create mode 100644 lib/librte_membership/rte_membership.h
 create mode 100644 lib/librte_membership/rte_membership_bf.c
 create mode 100644 lib/librte_membership/rte_membership_bf.h
 create mode 100644 lib/librte_membership/rte_membership_cache.c
 create mode 100644 lib/librte_membership/rte_membership_cache.h
 create mode 100644 lib/librte_membership/rte_membership_ht.c
 create mode 100644 lib/librte_membership/rte_membership_ht.h
 create mode 100644 lib/librte_membership/rte_membership_vbf.c
 create mode 100644 lib/librte_membership/rte_membership_vbf.h
 create mode 100644 lib/librte_membership/rte_membership_version.map
 create mode 100644 test/test/test_membership.c

-- 
1.9.1