From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id 7F7FA2B9F for ; Sat, 27 May 2017 03:35:54 +0200 (CEST) Received: from orsmga001.jf.intel.com ([10.7.209.18]) by orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 26 May 2017 18:35:53 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.38,400,1491289200"; d="scan'208";a="1135252379" Received: from bdw-yipeng.jf.intel.com ([10.54.81.23]) by orsmga001.jf.intel.com with ESMTP; 26 May 2017 18:35:53 -0700 From: Yipeng Wang To: yipeng1.wang@intel.com Cc: dev@dpdk.org, sameh.gobriel@intel.com, ren.wang@intel.com, charlie.tai@intel.com Date: Fri, 26 May 2017 18:34:47 -0700 Message-Id: <1495848888-54621-1-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 1.9.1 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [RFC] Add Membership Library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 27 May 2017 01:35:55 -0000 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 Signed-off-by: Sameh Gobriel Signed-off-by: Charlie Tai Signed-off-by: Ren Wang 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