From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga01.intel.com (mga01.intel.com [192.55.52.88]) by dpdk.org (Postfix) with ESMTP id 81BBD101B for ; Wed, 6 Sep 2017 02:00:17 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 05 Sep 2017 17:00:15 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.41,481,1498546800"; d="scan'208";a="897423429" Received: from bdw-yipeng.jf.intel.com ([10.54.81.30]) by FMSMGA003.fm.intel.com with ESMTP; 05 Sep 2017 17:00:15 -0700 From: Yipeng Wang To: dev@dpdk.org Cc: charlie.tai@intel.com, sameh.gobriel@intel.com, ren.wang@intel.com, yipeng1.wang@intel.com, john.mcnamara@intel.com Date: Tue, 5 Sep 2017 16:59:42 -0700 Message-Id: <1504655989-1518-1-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1504315481-12854-1-git-send-email-yipeng1.wang@intel.com> References: <1504315481-12854-1-git-send-email-yipeng1.wang@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [PATCH v3 0/7] 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: Wed, 06 Sep 2017 00:00:18 -0000 DPDK Membership Library provides an API that can be used by many DPDK applications to conduct one or more set-membership tests (we mention some possible use cases below, but interested readers can refer to [1] for a wider survey of use cases). The basic functionalities of the Membership Library include inserting a new member, deleting an existing member, and querying the existence of a member. The query result would indicate with high accuracy which specific set this member belongs to among a group of sets. The Membership Library is an extension and generalization of traditional filter data structures [2,3], which maintain a space-efficient “set-summary”. 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, and secondly set membership tests (or other operations) is much more efficient than searching through the complete list of elements. A membership test for an element will return the set this element belongs to if found (or return "not-found") with high accuracy. If needed, the accuracy of the membership tests could be further increased with larger storage space. Set-summary is a fundamental data aggregation component that can be used in many network applications. It is a crucial structure to address performance and scalability issues of diverse 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 set-summary to optimize flow lookup in Open vSwitch (OvS) shows a speedup of about 2-3X. This patch set implements two types of set-summaries, i.e., hash-table based set-summary (HTSS) and Vector Bloom Filter (vBF). HTSS supports both the non-cache and cache modes. The non-cache mode can incur a small chance of false-positives which is the case when the set-summary indicates a key belongs to a given set while actually it is not. The cache mode can also have false-negatives in addition to false-positives. False-negatives means the case when the set-summary indicates a key does not belong to a given set while actually it does. This happens because cache mode allows new key to evict existing keys. vBF only has false-positives similar to the non-cache HTSS. However, one can set the false-positive rate arbitrarily. HTSS's false-positive rate is determined by the hash-table size and the signature size. [1] A Broder and M Mitzenmacher, “Network Applications of Bloom Filters: A Survey,” in Internet Mathematics, 2005. [2] B H Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, 1970. [3] B Fan, D G Andersen and M Kaminsky, “Cuckoo Filter: Practically Better Than Bloom,” in Conference on emerging Networking Experiments and Technologies, 2014. v3: - documentation: update documentation to incorperate John's review. v2: - test: add bad parameter test functions to test the creation fail case. - test: add find existing test. - member lib: Add num_entries check in rte_member_create_ht. - member lib: Add multiple checks for rte_member_create_vbf to avoid divide-by-0. - member lib: remove unnecessary ret from rte_member.c according to Stephen's comment. - member lib: change the vBF creation function to be not too conservative. Previous algorithm is too conservative on false positive. - member lib: fix uninitilize issue fail gcc-4.8 in rte_member_find_existing. - member lib: add rte_member_find_existing to version map. - makefile: lib/librte_member/Makefile: change include order according to Luca's comment. - documentation: update the programmer guide for membership library. Yipeng Wang (7): member: implement main API member: implement HT mode member: implement vBF mode member: add AVX for HT mode member: enable the library test/member: add functional and perf tests doc: add membership documentation MAINTAINERS | 7 + config/common_base | 5 + doc/api/doxy-api-index.md | 3 +- doc/api/doxy-api.conf | 1 + doc/guides/prog_guide/img/member_i1.svg | 1613 ++++++++++++++++++++++++++++++ doc/guides/prog_guide/img/member_i2.svg | 36 + doc/guides/prog_guide/img/member_i3.svg | 148 +++ doc/guides/prog_guide/img/member_i4.svg | 450 +++++++++ doc/guides/prog_guide/img/member_i5.svg | 163 +++ doc/guides/prog_guide/img/member_i6.svg | 332 ++++++ doc/guides/prog_guide/img/member_i7.svg | 399 ++++++++ doc/guides/prog_guide/index.rst | 14 + doc/guides/prog_guide/member_lib.rst | 421 ++++++++ doc/guides/rel_notes/release_17_11.rst | 17 + lib/Makefile | 2 + lib/librte_eal/common/eal_common_log.c | 1 + lib/librte_eal/common/include/rte_log.h | 1 + lib/librte_member/Makefile | 51 + lib/librte_member/rte_member.c | 342 +++++++ lib/librte_member/rte_member.h | 518 ++++++++++ lib/librte_member/rte_member_ht.c | 569 +++++++++++ lib/librte_member/rte_member_ht.h | 115 +++ lib/librte_member/rte_member_vbf.c | 350 +++++++ lib/librte_member/rte_member_vbf.h | 85 ++ lib/librte_member/rte_member_version.map | 16 + lib/librte_member/rte_member_x86.h | 111 ++ mk/rte.app.mk | 2 + test/test/Makefile | 3 + test/test/test_member.c | 682 +++++++++++++ test/test/test_member_perf.c | 643 ++++++++++++ 30 files changed, 7099 insertions(+), 1 deletion(-) create mode 100644 doc/guides/prog_guide/img/member_i1.svg create mode 100644 doc/guides/prog_guide/img/member_i2.svg create mode 100644 doc/guides/prog_guide/img/member_i3.svg create mode 100644 doc/guides/prog_guide/img/member_i4.svg create mode 100644 doc/guides/prog_guide/img/member_i5.svg create mode 100644 doc/guides/prog_guide/img/member_i6.svg create mode 100644 doc/guides/prog_guide/img/member_i7.svg create mode 100644 doc/guides/prog_guide/member_lib.rst create mode 100644 lib/librte_member/Makefile create mode 100644 lib/librte_member/rte_member.c create mode 100644 lib/librte_member/rte_member.h create mode 100644 lib/librte_member/rte_member_ht.c create mode 100644 lib/librte_member/rte_member_ht.h create mode 100644 lib/librte_member/rte_member_vbf.c create mode 100644 lib/librte_member/rte_member_vbf.h create mode 100644 lib/librte_member/rte_member_version.map create mode 100644 lib/librte_member/rte_member_x86.h create mode 100644 test/test/test_member.c create mode 100644 test/test/test_member_perf.c -- 2.7.4