diff mbox

[dpdk-dev,1/7] member: implement main API

Message ID 1503361193-36699-2-git-send-email-yipeng1.wang@intel.com (mailing list archive)
State Superseded, archived
Headers show

Checks

Context Check Description
ci/checkpatch success coding style OK
ci/Intel-compilation success Compilation OK

Commit Message

Wang, Yipeng1 Aug. 22, 2017, 12:19 a.m. UTC
Membership library is an extension and generalization of a traditional
filter (for example Bloom Filter) structure. In general, the Membership
library is a data structure that provides a "set-summary" and responds
to set-membership queries of whether a certain element belongs to a
set(s). A membership test for an element will return the set this element
belongs to or not-found if the element is never inserted into the
set-summary.

The results of the membership test is not 100% accurate. Certain
false positive or false negative probability could exist. However,
comparing to a "full-blown" complete list of elements, a "set-summary"
is memory efficient and fast on lookup.

This patch add the main API definition.

Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
---
 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               |  48 +++
 lib/librte_member/rte_member.c           | 357 +++++++++++++++++++++
 lib/librte_member/rte_member.h           | 518 +++++++++++++++++++++++++++++++
 lib/librte_member/rte_member_version.map |  15 +
 7 files changed, 942 insertions(+)
 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_version.map

Comments

Stephen Hemminger Aug. 22, 2017, 3:59 a.m. UTC | #1
On Mon, 21 Aug 2017 17:19:47 -0700
Yipeng Wang <yipeng1.wang@intel.com> wrote:

> +int
> +rte_member_lookup(const void *ss, const void *key,
> +		MEMBER_SET_TYPE *set_id)
> +{
> +	const struct rte_member_setsum *setsum = ss;
> +	if (setsum == NULL || key == NULL || set_id == NULL)
> +		return -EINVAL;
> +
> +	int ret = 0;

Don't needlessly initialize all variable.
In all code paths, ret is set.

In fact you could just make all cases of the switch into return
and  compiler could optimize it as a tail call.
Luca Boccassi Aug. 22, 2017, 10:02 a.m. UTC | #2
On Mon, 2017-08-21 at 17:19 -0700, Yipeng Wang wrote:
> Membership library is an extension and generalization of a
> traditional
> filter (for example Bloom Filter) structure. In general, the
> Membership
> library is a data structure that provides a "set-summary" and
> responds
> to set-membership queries of whether a certain element belongs to a
> set(s). A membership test for an element will return the set this
> element
> belongs to or not-found if the element is never inserted into the
> set-summary.
> 
> The results of the membership test is not 100% accurate. Certain
> false positive or false negative probability could exist. However,
> comparing to a "full-blown" complete list of elements, a "set-
> summary"
> is memory efficient and fast on lookup.
> 
> This patch add the main API definition.
> 
> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
> ---
>  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               |  48 +++
>  lib/librte_member/rte_member.c           | 357 +++++++++++++++++++++
>  lib/librte_member/rte_member.h           | 518
> +++++++++++++++++++++++++++++++
>  lib/librte_member/rte_member_version.map |  15 +
>  7 files changed, 942 insertions(+)
>  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_version.map
> 

> diff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile
> new file mode 100644
> index 0000000..997c825
> --- /dev/null
> +++ b/lib/librte_member/Makefile
> @@ -0,0 +1,48 @@
> +#   BSD LICENSE
> +#
> +#   Copyright(c) 2017 Intel Corporation. All rights reserved.
> +#   All rights reserved.
> +#
> +#   Redistribution and use in source and binary forms, with or
> without
> +#   modification, are permitted provided that the following
> conditions
> +#   are met:
> +#
> +#     * Redistributions of source code must retain the above
> copyright
> +#       notice, this list of conditions and the following
> disclaimer.
> +#     * Redistributions in binary form must reproduce the above
> copyright
> +#       notice, this list of conditions and the following disclaimer
> in
> +#       the documentation and/or other materials provided with the
> +#       distribution.
> +#     * Neither the name of Intel Corporation nor the names of its
> +#       contributors may be used to endorse or promote products
> derived
> +#       from this software without specific prior written
> permission.
> +#
> +#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> CONTRIBUTORS
> +#   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
> NOT
> +#   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> FITNESS FOR
> +#   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> COPYRIGHT
> +#   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> INCIDENTAL,
> +#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> +#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
> USE,
> +#   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
> ON ANY
> +#   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
> TORT
> +#   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> THE USE
> +#   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> DAMAGE.
> +
> +include $(RTE_SDK)/mk/rte.vars.mk
> +
> +# library name
> +LIB = librte_member.a
> +
> +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
> +

This breaks reproducibility as the output directory will be included
before the source directory, causing a race - please do something like:

CFLAGS := -I$(SRCDIR) $(CFLAGS)
CFLAGS += $(WERROR_FLAGS) -O3

> +EXPORT_MAP := rte_member_version.map
> +
> +LIBABIVER := 1
> +
> +# all source are stored in SRCS-y
> +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) +=  rte_member.c
> +# install includes
> +SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h
> +
> +include $(RTE_SDK)/mk/rte.lib.mk
Ferruh Yigit Aug. 24, 2017, 9:35 a.m. UTC | #3
On 8/22/2017 11:02 AM, Luca Boccassi wrote:
> On Mon, 2017-08-21 at 17:19 -0700, Yipeng Wang wrote:
>> Membership library is an extension and generalization of a
>> traditional
>> filter (for example Bloom Filter) structure. In general, the
>> Membership
>> library is a data structure that provides a "set-summary" and
>> responds
>> to set-membership queries of whether a certain element belongs to a
>> set(s). A membership test for an element will return the set this
>> element
>> belongs to or not-found if the element is never inserted into the
>> set-summary.
>>
>> The results of the membership test is not 100% accurate. Certain
>> false positive or false negative probability could exist. However,
>> comparing to a "full-blown" complete list of elements, a "set-
>> summary"
>> is memory efficient and fast on lookup.
>>
>> This patch add the main API definition.
>>
>> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
>> ---
>>  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               |  48 +++
>>  lib/librte_member/rte_member.c           | 357 +++++++++++++++++++++
>>  lib/librte_member/rte_member.h           | 518
>> +++++++++++++++++++++++++++++++
>>  lib/librte_member/rte_member_version.map |  15 +
>>  7 files changed, 942 insertions(+)
>>  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_version.map
>>
> 
>> diff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile
>> new file mode 100644
>> index 0000000..997c825
>> --- /dev/null
>> +++ b/lib/librte_member/Makefile
>> @@ -0,0 +1,48 @@
>> +#   BSD LICENSE
>> +#
>> +#   Copyright(c) 2017 Intel Corporation. All rights reserved.
>> +#   All rights reserved.
>> +#
>> +#   Redistribution and use in source and binary forms, with or
>> without
>> +#   modification, are permitted provided that the following
>> conditions
>> +#   are met:
>> +#
>> +#     * Redistributions of source code must retain the above
>> copyright
>> +#       notice, this list of conditions and the following
>> disclaimer.
>> +#     * Redistributions in binary form must reproduce the above
>> copyright
>> +#       notice, this list of conditions and the following disclaimer
>> in
>> +#       the documentation and/or other materials provided with the
>> +#       distribution.
>> +#     * Neither the name of Intel Corporation nor the names of its
>> +#       contributors may be used to endorse or promote products
>> derived
>> +#       from this software without specific prior written
>> permission.
>> +#
>> +#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
>> CONTRIBUTORS
>> +#   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
>> NOT
>> +#   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
>> FITNESS FOR
>> +#   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
>> COPYRIGHT
>> +#   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
>> INCIDENTAL,
>> +#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
>> +#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
>> USE,
>> +#   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
>> ON ANY
>> +#   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
>> TORT
>> +#   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
>> THE USE
>> +#   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
>> DAMAGE.
>> +
>> +include $(RTE_SDK)/mk/rte.vars.mk
>> +
>> +# library name
>> +LIB = librte_member.a
>> +
>> +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
>> +
> 
> This breaks reproducibility as the output directory will be included
> before the source directory, causing a race - please do something like:
> 
> CFLAGS := -I$(SRCDIR) $(CFLAGS)
> CFLAGS += $(WERROR_FLAGS) -O3

Can we remove "-I$(SRCDIR)" completely by first installing headers and
later compiling objects, all using $(RTE_OUT) only?

Do you think can this work?

> 
>> +EXPORT_MAP := rte_member_version.map
>> +
>> +LIBABIVER := 1
>> +
>> +# all source are stored in SRCS-y
>> +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) +=  rte_member.c
>> +# install includes
>> +SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h
>> +
>> +include $(RTE_SDK)/mk/rte.lib.mk
>
Luca Boccassi Aug. 24, 2017, 9:55 a.m. UTC | #4
On Thu, 2017-08-24 at 10:35 +0100, Ferruh Yigit wrote:
> On 8/22/2017 11:02 AM, Luca Boccassi wrote:
> > On Mon, 2017-08-21 at 17:19 -0700, Yipeng Wang wrote:
> > > Membership library is an extension and generalization of a
> > > traditional
> > > filter (for example Bloom Filter) structure. In general, the
> > > Membership
> > > library is a data structure that provides a "set-summary" and
> > > responds
> > > to set-membership queries of whether a certain element belongs to
> > > a
> > > set(s). A membership test for an element will return the set this
> > > element
> > > belongs to or not-found if the element is never inserted into the
> > > set-summary.
> > > 
> > > The results of the membership test is not 100% accurate. Certain
> > > false positive or false negative probability could exist.
> > > However,
> > > comparing to a "full-blown" complete list of elements, a "set-
> > > summary"
> > > is memory efficient and fast on lookup.
> > > 
> > > This patch add the main API definition.
> > > 
> > > Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
> > > ---
> > >  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               |  48 +++
> > >  lib/librte_member/rte_member.c           | 357
> > > +++++++++++++++++++++
> > >  lib/librte_member/rte_member.h           | 518
> > > +++++++++++++++++++++++++++++++
> > >  lib/librte_member/rte_member_version.map |  15 +
> > >  7 files changed, 942 insertions(+)
> > >  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_version.map
> > > 
> > > diff --git a/lib/librte_member/Makefile
> > > b/lib/librte_member/Makefile
> > > new file mode 100644
> > > index 0000000..997c825
> > > --- /dev/null
> > > +++ b/lib/librte_member/Makefile
> > > @@ -0,0 +1,48 @@
> > > +#   BSD LICENSE
> > > +#
> > > +#   Copyright(c) 2017 Intel Corporation. All rights reserved.
> > > +#   All rights reserved.
> > > +#
> > > +#   Redistribution and use in source and binary forms, with or
> > > without
> > > +#   modification, are permitted provided that the following
> > > conditions
> > > +#   are met:
> > > +#
> > > +#     * Redistributions of source code must retain the above
> > > copyright
> > > +#       notice, this list of conditions and the following
> > > disclaimer.
> > > +#     * Redistributions in binary form must reproduce the above
> > > copyright
> > > +#       notice, this list of conditions and the following
> > > disclaimer
> > > in
> > > +#       the documentation and/or other materials provided with
> > > the
> > > +#       distribution.
> > > +#     * Neither the name of Intel Corporation nor the names of
> > > its
> > > +#       contributors may be used to endorse or promote products
> > > derived
> > > +#       from this software without specific prior written
> > > permission.
> > > +#
> > > +#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> > > CONTRIBUTORS
> > > +#   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
> > > BUT
> > > NOT
> > > +#   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> > > FITNESS FOR
> > > +#   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> > > COPYRIGHT
> > > +#   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> > > INCIDENTAL,
> > > +#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
> > > NOT
> > > +#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
> > > LOSS OF
> > > USE,
> > > +#   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
> > > AND
> > > ON ANY
> > > +#   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
> > > OR
> > > TORT
> > > +#   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
> > > OF
> > > THE USE
> > > +#   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> > > DAMAGE.
> > > +
> > > +include $(RTE_SDK)/mk/rte.vars.mk
> > > +
> > > +# library name
> > > +LIB = librte_member.a
> > > +
> > > +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
> > > +
> > 
> > This breaks reproducibility as the output directory will be
> > included
> > before the source directory, causing a race - please do something
> > like:
> > 
> > CFLAGS := -I$(SRCDIR) $(CFLAGS)
> > CFLAGS += $(WERROR_FLAGS) -O3
> 
> Can we remove "-I$(SRCDIR)" completely by first installing headers
> and
> later compiling objects, all using $(RTE_OUT) only?
> 
> Do you think can this work?

I'm not sure, it might - but given Bruce's effort to port to Meson I'm
not sure it's worth spending a lot of time doing big refactoring of the
existing build system

> > > +EXPORT_MAP := rte_member_version.map
> > > +
> > > +LIBABIVER := 1
> > > +
> > > +# all source are stored in SRCS-y
> > > +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) +=  rte_member.c
> > > +# install includes
> > > +SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h
> > > +
> > > +include $(RTE_SDK)/mk/rte.lib.mk
> 
>
Wang, Yipeng1 Aug. 24, 2017, 6:38 p.m. UTC | #5
> -----Original Message-----

> From: Luca Boccassi [mailto:luca.boccassi@gmail.com]

> Sent: Tuesday, August 22, 2017 3:02 AM

> To: Wang, Yipeng1 <yipeng1.wang@intel.com>

> Cc: dev@dpdk.org

> Subject: Re: [dpdk-dev] [PATCH 1/7] member: implement main API

> 

> On Mon, 2017-08-21 at 17:19 -0700, Yipeng Wang wrote:

> > Membership library is an extension and generalization of a

> > traditional

> > filter (for example Bloom Filter) structure. In general, the

> > Membership

> > library is a data structure that provides a "set-summary" and

> > responds

> > to set-membership queries of whether a certain element belongs to a

> > set(s). A membership test for an element will return the set this

> > element

> > belongs to or not-found if the element is never inserted into the

> > set-summary.

> >

> > The results of the membership test is not 100% accurate. Certain

> > false positive or false negative probability could exist. However,

> > comparing to a "full-blown" complete list of elements, a "set-

> > summary"

> > is memory efficient and fast on lookup.

> >

> > This patch add the main API definition.

> >

> > Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>

> > ---

> >  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               |  48 +++

> >  lib/librte_member/rte_member.c           | 357 +++++++++++++++++++++

> >  lib/librte_member/rte_member.h           | 518

> > +++++++++++++++++++++++++++++++

> >  lib/librte_member/rte_member_version.map |  15 +

> >  7 files changed, 942 insertions(+)

> >  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_version.map

> >

> 

> > diff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile

> > new file mode 100644

> > index 0000000..997c825

> > --- /dev/null

> > +++ b/lib/librte_member/Makefile

> > @@ -0,0 +1,48 @@

> > +#   BSD LICENSE

> > +#

> > +#   Copyright(c) 2017 Intel Corporation. All rights reserved.

> > +#   All rights reserved.

> > +#

> > +#   Redistribution and use in source and binary forms, with or

> > without

> > +#   modification, are permitted provided that the following

> > conditions

> > +#   are met:

> > +#

> > +#     * Redistributions of source code must retain the above

> > copyright

> > +#       notice, this list of conditions and the following

> > disclaimer.

> > +#     * Redistributions in binary form must reproduce the above

> > copyright

> > +#       notice, this list of conditions and the following disclaimer

> > in

> > +#       the documentation and/or other materials provided with the

> > +#       distribution.

> > +#     * Neither the name of Intel Corporation nor the names of its

> > +#       contributors may be used to endorse or promote products

> > derived

> > +#       from this software without specific prior written

> > permission.

> > +#

> > +#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND

> > CONTRIBUTORS

> > +#   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT

> > NOT

> > +#   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND

> > FITNESS FOR

> > +#   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE

> > COPYRIGHT

> > +#   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

> > INCIDENTAL,

> > +#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,

> BUT NOT

> > +#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

> LOSS OF

> > USE,

> > +#   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED

> AND

> > ON ANY

> > +#   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR

> > TORT

> > +#   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT

> OF

> > THE USE

> > +#   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH

> > DAMAGE.

> > +

> > +include $(RTE_SDK)/mk/rte.vars.mk

> > +

> > +# library name

> > +LIB = librte_member.a

> > +

> > +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3

> > +

> 

> This breaks reproducibility as the output directory will be included

> before the source directory, causing a race - please do something like:

> 

> CFLAGS := -I$(SRCDIR) $(CFLAGS)

> CFLAGS += $(WERROR_FLAGS) -O3

> 

[Wang, Yipeng] 
Thanks Luca, I will reverse the include order in next version.

I am not an expert on the build system, to be more clear, the race condition you 
mentioned is because the library may search build directory first that some symlinks
may have not been created yet, right?

Thanks

> > +EXPORT_MAP := rte_member_version.map

> > +

> > +LIBABIVER := 1

> > +

> > +# all source are stored in SRCS-y

> > +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) +=  rte_member.c

> > +# install includes

> > +SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h

> > +

> > +include $(RTE_SDK)/mk/rte.lib.mk

> 

> --

> Kind regards,

> Luca Boccassi
Luca Boccassi Sept. 2, 2017, 12:54 p.m. UTC | #6
On Thu, 2017-08-24 at 18:38 +0000, Wang, Yipeng1 wrote:
> > -----Original Message-----
> > From: Luca Boccassi [mailto:luca.boccassi@gmail.com]
> > Sent: Tuesday, August 22, 2017 3:02 AM
> > To: Wang, Yipeng1 <yipeng1.wang@intel.com>
> > Cc: dev@dpdk.org
> > Subject: Re: [dpdk-dev] [PATCH 1/7] member: implement main API
> > 
> > On Mon, 2017-08-21 at 17:19 -0700, Yipeng Wang wrote:
> > > Membership library is an extension and generalization of a
> > > traditional
> > > filter (for example Bloom Filter) structure. In general, the
> > > Membership
> > > library is a data structure that provides a "set-summary" and
> > > responds
> > > to set-membership queries of whether a certain element belongs to
> > > a
> > > set(s). A membership test for an element will return the set this
> > > element
> > > belongs to or not-found if the element is never inserted into the
> > > set-summary.
> > > 
> > > The results of the membership test is not 100% accurate. Certain
> > > false positive or false negative probability could exist.
> > > However,
> > > comparing to a "full-blown" complete list of elements, a "set-
> > > summary"
> > > is memory efficient and fast on lookup.
> > > 
> > > This patch add the main API definition.
> > > 
> > > Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
> > > ---
> > >  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               |  48 +++
> > >  lib/librte_member/rte_member.c           | 357
> > > +++++++++++++++++++++
> > >  lib/librte_member/rte_member.h           | 518
> > > +++++++++++++++++++++++++++++++
> > >  lib/librte_member/rte_member_version.map |  15 +
> > >  7 files changed, 942 insertions(+)
> > >  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_version.map
> > > 
> > > diff --git a/lib/librte_member/Makefile
> > > b/lib/librte_member/Makefile
> > > new file mode 100644
> > > index 0000000..997c825
> > > --- /dev/null
> > > +++ b/lib/librte_member/Makefile
> > > @@ -0,0 +1,48 @@
> > > +#   BSD LICENSE
> > > +#
> > > +#   Copyright(c) 2017 Intel Corporation. All rights reserved.
> > > +#   All rights reserved.
> > > +#
> > > +#   Redistribution and use in source and binary forms, with or
> > > without
> > > +#   modification, are permitted provided that the following
> > > conditions
> > > +#   are met:
> > > +#
> > > +#     * Redistributions of source code must retain the above
> > > copyright
> > > +#       notice, this list of conditions and the following
> > > disclaimer.
> > > +#     * Redistributions in binary form must reproduce the above
> > > copyright
> > > +#       notice, this list of conditions and the following
> > > disclaimer
> > > in
> > > +#       the documentation and/or other materials provided with
> > > the
> > > +#       distribution.
> > > +#     * Neither the name of Intel Corporation nor the names of
> > > its
> > > +#       contributors may be used to endorse or promote products
> > > derived
> > > +#       from this software without specific prior written
> > > permission.
> > > +#
> > > +#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> > > CONTRIBUTORS
> > > +#   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
> > > BUT
> > > NOT
> > > +#   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> > > FITNESS FOR
> > > +#   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> > > COPYRIGHT
> > > +#   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> > > INCIDENTAL,
> > > +#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
> > 
> > BUT NOT
> > > +#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
> > 
> > LOSS OF
> > > USE,
> > > +#   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
> > 
> > AND
> > > ON ANY
> > > +#   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
> > > OR
> > > TORT
> > > +#   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
> > 
> > OF
> > > THE USE
> > > +#   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> > > DAMAGE.
> > > +
> > > +include $(RTE_SDK)/mk/rte.vars.mk
> > > +
> > > +# library name
> > > +LIB = librte_member.a
> > > +
> > > +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
> > > +
> > 
> > This breaks reproducibility as the output directory will be
> > included
> > before the source directory, causing a race - please do something
> > like:
> > 
> > CFLAGS := -I$(SRCDIR) $(CFLAGS)
> > CFLAGS += $(WERROR_FLAGS) -O3
> > 
> 
> [Wang, Yipeng] 
> Thanks Luca, I will reverse the include order in next version.
> 
> I am not an expert on the build system, to be more clear, the race
> condition you 
> mentioned is because the library may search build directory first
> that some symlinks
> may have not been created yet, right?
> 
> Thanks

Yes, and as a consequence on some builds the DWARF symbols list
lib/libfoo/foo.h as the source file path in the .debug, and on some
builds they list build-dir/include/foo.h

> > > +EXPORT_MAP := rte_member_version.map
> > > +
> > > +LIBABIVER := 1
> > > +
> > > +# all source are stored in SRCS-y
> > > +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) +=  rte_member.c
> > > +# install includes
> > > +SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h
> > > +
> > > +include $(RTE_SDK)/mk/rte.lib.mk
> > 
> > --
> > Kind regards,
> > Luca Boccassi
diff mbox

Patch

diff --git a/lib/Makefile b/lib/Makefile
index 86caba1..c82033a 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -108,6 +108,8 @@  DIRS-$(CONFIG_RTE_LIBRTE_REORDER) += librte_reorder
 DEPDIRS-librte_reorder := librte_eal librte_mempool librte_mbuf
 DIRS-$(CONFIG_RTE_LIBRTE_PDUMP) += librte_pdump
 DEPDIRS-librte_pdump := librte_eal librte_mempool librte_mbuf librte_ether
+DIRS-$(CONFIG_RTE_LIBRTE_MEMBER) += librte_member
+DEPDIRS-librte_member := librte_eal librte_hash
 
 ifeq ($(CONFIG_RTE_EXEC_ENV_LINUXAPP),y)
 DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni
diff --git a/lib/librte_eal/common/eal_common_log.c b/lib/librte_eal/common/eal_common_log.c
index 0e3b932..90db6a3 100644
--- a/lib/librte_eal/common/eal_common_log.c
+++ b/lib/librte_eal/common/eal_common_log.c
@@ -279,6 +279,7 @@  static const struct logtype logtype_strings[] = {
 	{RTE_LOGTYPE_CRYPTODEV,  "cryptodev"},
 	{RTE_LOGTYPE_EFD,        "efd"},
 	{RTE_LOGTYPE_EVENTDEV,   "eventdev"},
+	{RTE_LOGTYPE_MEMBER,     "member"},
 	{RTE_LOGTYPE_USER1,      "user1"},
 	{RTE_LOGTYPE_USER2,      "user2"},
 	{RTE_LOGTYPE_USER3,      "user3"},
diff --git a/lib/librte_eal/common/include/rte_log.h b/lib/librte_eal/common/include/rte_log.h
index ec8dba7..ce1a3d0 100644
--- a/lib/librte_eal/common/include/rte_log.h
+++ b/lib/librte_eal/common/include/rte_log.h
@@ -87,6 +87,7 @@  extern struct rte_logs rte_logs;
 #define RTE_LOGTYPE_CRYPTODEV 17 /**< Log related to cryptodev. */
 #define RTE_LOGTYPE_EFD       18 /**< Log related to EFD. */
 #define RTE_LOGTYPE_EVENTDEV  19 /**< Log related to eventdev. */
+#define RTE_LOGTYPE_MEMBER    20 /**< Log related to membership. */
 
 /* these log types can be used in an application */
 #define RTE_LOGTYPE_USER1     24 /**< User-defined log type 1. */
diff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile
new file mode 100644
index 0000000..997c825
--- /dev/null
+++ b/lib/librte_member/Makefile
@@ -0,0 +1,48 @@ 
+#   BSD LICENSE
+#
+#   Copyright(c) 2017 Intel Corporation. All rights reserved.
+#   All rights reserved.
+#
+#   Redistribution and use in source and binary forms, with or without
+#   modification, are permitted provided that the following conditions
+#   are met:
+#
+#     * Redistributions of source code must retain the above copyright
+#       notice, this list of conditions and the following disclaimer.
+#     * Redistributions in binary form must reproduce the above copyright
+#       notice, this list of conditions and the following disclaimer in
+#       the documentation and/or other materials provided with the
+#       distribution.
+#     * Neither the name of Intel Corporation nor the names of its
+#       contributors may be used to endorse or promote products derived
+#       from this software without specific prior written permission.
+#
+#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+#   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+#   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+#   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+#   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+#   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+#   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+#   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+#   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_member.a
+
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
+
+EXPORT_MAP := rte_member_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) +=  rte_member.c
+# install includes
+SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_member/rte_member.c b/lib/librte_member/rte_member.c
new file mode 100644
index 0000000..560b754
--- /dev/null
+++ b/lib/librte_member/rte_member.c
@@ -0,0 +1,357 @@ 
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2017 Intel Corporation. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in
+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Intel Corporation nor the names of its
+ *       contributors may be used to endorse or promote products derived
+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <string.h>
+
+#include <rte_eal.h>
+#include <rte_eal_memconfig.h>
+#include <rte_memory.h>
+#include <rte_memzone.h>
+#include <rte_malloc.h>
+#include <rte_errno.h>
+
+#include "rte_member.h"
+#include "rte_member_ht.h"
+#include "rte_member_vbf.h"
+
+TAILQ_HEAD(rte_member_list, rte_tailq_entry);
+static struct rte_tailq_elem rte_member_tailq = {
+	.name = "RTE_MEMBER",
+};
+EAL_REGISTER_TAILQ(rte_member_tailq)
+
+
+void *
+rte_member_find_existing(const char *name)
+{
+	struct rte_member_setsum *setsum;
+	struct rte_tailq_entry *te;
+	struct rte_member_list *member_list;
+
+	member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);
+
+	rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
+	TAILQ_FOREACH(te, member_list, next) {
+		setsum = (struct rte_member_setsum *) te->data;
+		if (strncmp(name, setsum->name, RTE_MEMBER_NAMESIZE) == 0)
+			break;
+	}
+	rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	if (te == NULL) {
+		rte_errno = ENOENT;
+		return NULL;
+	}
+	return setsum;
+}
+
+void
+rte_member_free(void *ss)
+{
+	struct rte_member_setsum *setsum;
+	struct rte_member_list *member_list = NULL;
+	struct rte_tailq_entry *te;
+
+	if (ss == NULL)
+		return;
+	setsum = ss;
+	member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+	TAILQ_FOREACH(te, member_list, next) {
+		if (te->data == ss)
+			break;
+	}
+	if (te == NULL) {
+		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+		return;
+	}
+	TAILQ_REMOVE(member_list, te, next);
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		rte_member_free_ht(setsum);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		rte_member_free_vbf(setsum);
+		break;
+	default:
+		break;
+	}
+	rte_free(setsum);
+	rte_free(te);
+}
+
+
+void *
+rte_member_create(const struct rte_member_parameters *params)
+{
+	struct rte_tailq_entry *te;
+	struct rte_member_list *member_list = NULL;
+	struct rte_member_setsum *setsum = NULL;
+	int ret;
+
+	if (params == NULL) {
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	if ((params->key_len == 0)) {
+		rte_errno = EINVAL;
+		RTE_LOG(ERR, MEMBER,
+			"Memship create with invalid parameters\n");
+		return NULL;
+	}
+
+	member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	TAILQ_FOREACH(te, member_list, next) {
+		setsum = (struct rte_member_setsum *) te->data;
+		if (strncmp(params->name, setsum->name,
+				RTE_MEMBER_NAMESIZE) == 0)
+			break;
+	}
+	setsum = NULL;
+	if (te != NULL) {
+		rte_errno = EEXIST;
+		te = NULL;
+		goto error_unlock_exit;
+	}
+	te = rte_zmalloc("MEMBER_TAILQ_ENTRY", sizeof(*te), 0);
+	if (te == NULL) {
+		RTE_LOG(ERR, MEMBER, "tailq entry allocation failed\n");
+		goto error_unlock_exit;
+	}
+
+	/* Create a new setsum structure */
+	setsum = (struct rte_member_setsum *) rte_zmalloc_socket(params->name,
+			sizeof(struct rte_member_setsum), RTE_CACHE_LINE_SIZE,
+			params->socket_id);
+	if (setsum == NULL) {
+		RTE_LOG(ERR, MEMBER, "Create setsummary failed\n");
+		goto error_unlock_exit;
+	}
+	setsum->type = params->type;
+	setsum->socket_id = params->socket_id;
+	setsum->key_len = params->key_len;
+	setsum->num_set = params->num_set;
+	setsum->name = params->name;
+	setsum->prim_hash_seed = params->prim_hash_seed;
+	setsum->sec_hash_seed = params->sec_hash_seed;
+
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_create_ht(setsum, params);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		ret = rte_member_create_vbf(setsum, params);
+		break;
+	default:
+		goto error_unlock_exit;
+	}
+	if (ret < 0)
+		goto error_unlock_exit;
+	RTE_LOG(DEBUG, MEMBER, "Creating a setsummary table with mode %u\n",
+			setsum->type);
+
+	te->data = (void *)setsum;
+	TAILQ_INSERT_TAIL(member_list, te, next);
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+	return setsum;
+
+error_unlock_exit:
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+	rte_member_free(setsum);
+	return NULL;
+}
+
+
+int
+rte_member_add(const void *ss, const void *key, MEMBER_SET_TYPE set_id)
+{
+	const struct rte_member_setsum *setsum = ss;
+
+	if (setsum == NULL || key == NULL)
+		return -EINVAL;
+	int ret = 0;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_add_ht(setsum, key, set_id);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		ret = rte_member_add_vbf(setsum, key, set_id);
+		break;
+	default:
+		return -EINVAL;
+	}
+	return ret;
+}
+
+
+int
+rte_member_lookup(const void *ss, const void *key,
+		MEMBER_SET_TYPE *set_id)
+{
+	const struct rte_member_setsum *setsum = ss;
+	if (setsum == NULL || key == NULL || set_id == NULL)
+		return -EINVAL;
+
+	int ret = 0;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_lookup_ht(setsum, key, set_id);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		ret = rte_member_lookup_vbf(setsum, key, set_id);
+		break;
+	default:
+		return -EINVAL;
+	}
+	return ret;
+}
+
+
+int
+rte_member_lookup_bulk(const void *ss, const void **keys, uint32_t num_keys,
+		MEMBER_SET_TYPE *set_ids)
+{
+	const struct rte_member_setsum *setsum = ss;
+
+	if (setsum == NULL || keys == NULL || set_ids == NULL)
+		return -EINVAL;
+
+	int ret = 0;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_lookup_bulk_ht(setsum, keys, num_keys,
+				set_ids);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		ret = rte_member_lookup_bulk_vbf(setsum, keys, num_keys,
+				set_ids);
+		break;
+	default:
+		return -EINVAL;
+	}
+	return ret;
+}
+
+int
+rte_member_lookup_multi(const void *ss, const void *key,
+		uint32_t match_per_key, MEMBER_SET_TYPE *set_id)
+{
+	const struct rte_member_setsum *setsum = ss;
+
+	if (setsum == NULL || key == NULL || set_id == NULL)
+		return -EINVAL;
+	int ret = 0;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_lookup_multi_ht(setsum, key, match_per_key,
+				set_id);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		ret = rte_member_lookup_multi_vbf(setsum, key, match_per_key,
+				set_id);
+		break;
+	default:
+		return -EINVAL;
+	}
+	return ret;
+}
+
+
+int
+rte_member_lookup_multi_bulk(const void *ss, const void **keys,
+		uint32_t num_keys, uint32_t max_match_per_key,
+		uint32_t *match_count, MEMBER_SET_TYPE *set_ids)
+{
+	const struct rte_member_setsum *setsum = ss;
+	if (setsum == NULL || keys == NULL || set_ids == NULL ||
+			match_count == NULL)
+		return -EINVAL;
+	int ret = 0;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_lookup_multi_bulk_ht(setsum, keys, num_keys,
+				max_match_per_key, match_count, set_ids);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		ret = rte_member_lookup_multi_bulk_vbf(setsum, keys, num_keys,
+				max_match_per_key, match_count, set_ids);
+		break;
+	default:
+		return -EINVAL;
+	}
+	return ret;
+}
+
+
+int
+rte_member_delete(void *ss, const void *key, MEMBER_SET_TYPE set_id)
+{
+	struct rte_member_setsum *setsum = ss;
+	if (setsum == NULL || key == NULL)
+		return -EINVAL;
+	int ret = 0;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		ret = rte_member_delete_ht(setsum, key, set_id);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+	default:
+		return -EINVAL;
+	}
+	return ret;
+}
+
+
+void
+rte_member_reset(const void *ss)
+{
+	const struct rte_member_setsum *setsum = ss;
+	if (setsum == NULL)
+		return;
+	switch (setsum->type) {
+	case RTE_MEMBER_TYPE_HT:
+		rte_member_reset_ht(setsum);
+		break;
+	case RTE_MEMBER_TYPE_VBF:
+		rte_member_reset_vbf(setsum);
+		break;
+	default:
+		break;
+	}
+}
diff --git a/lib/librte_member/rte_member.h b/lib/librte_member/rte_member.h
new file mode 100644
index 0000000..de44b1b
--- /dev/null
+++ b/lib/librte_member/rte_member.h
@@ -0,0 +1,518 @@ 
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) 2017 Intel Corporation. All rights reserved.
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in
+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Intel Corporation nor the names of its
+ *       contributors may be used to endorse or promote products derived
+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+
+/**
+ * @file
+ *
+ * RTE Membership Library
+ *
+ * The Membership Library is an extension and generalization of a traditional
+ * filter (for example Bloom Filter) structure that has multiple usages in a
+ * variety of workloads and applications. The library is used to test if a key
+ * belongs to certain sets. Two types of such "set-summary" structures are
+ * implemented: hash-table based (HT) and vector bloom filter (vBF). For HT
+ * setsummary, two subtype or modes are available, cache and non-cache modes.
+ * The table below summarize some properties of the different implementations.
+ *
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ */
+
+
+/**
+ * <!--
+ * +==========+=====================+================+=========================+
+ * |   type   |      vbf            |     HT-cache   |     HT-non-cache        |
+ * +==========+=====================+==========================================+
+ * |structure |  bloom-filter array |  hash-table like without storing key     |
+ * +----------+---------------------+------------------------------------------+
+ * |set id    | limited by bf count |           [1, 0x7fff]                    |
+ * |          | up to 32.           |                                          |
+ * +----------+---------------------+------------------------------------------+
+ * |usages &  | small set range,    | can delete,    | cache most recent keys, |
+ * |properties| user-specified      | big set range, | have both false-positive|
+ * |          | false-positive rate,| small false    | and false-negative      |
+ * |          | no deletion support.| positive depend| depend on table size,   |
+ * |          |                     | on table size, | automatic overwritten.  |
+ * |          |                     | new key does   |                         |
+ * |          |                     | not overwrite  |                         |
+ * |          |                     | existing key.  |                         |
+ * +----------+---------------------+----------------+-------------------------+
+ * -->
+ */
+
+
+#ifndef _RTE_MEMBER_H_
+#define _RTE_MEMBER_H_
+
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+#include <stdio.h>
+#include <stdint.h>
+#include <rte_hash_crc.h>
+
+/** The set ID type that stored internally in hash table based set summary. */
+typedef uint16_t MEMBER_SET_TYPE;
+/** Invalid set ID used to mean no match found. */
+#define RTE_MEMBER_NO_MATCH 0
+/** Maximum size of hash table that can be created. */
+#define RTE_MEMBER_ENTRIES_MAX (1 << 30)
+/** Maximum number of keys that can be searched as a bulk */
+#define RTE_MEMBER_LOOKUP_BULK_MAX 64
+/** Entry count per bucket in hash table based mode. */
+#define RTE_MEMBER_BUCKET_ENTRIES 16
+/** Maximum number of characters in setsum name. */
+#define RTE_MEMBER_NAMESIZE 32
+
+/** @internal Primary hash function to calculate 1st independent hash. */
+#define MEMBER_PRIM_HASH(key, key_len, seed) \
+	(uint32_t)(rte_hash_crc(key, key_len, seed))
+/** @internal Secondary hash function to calculate 2nd independent hash. */
+#define MEMBER_SEC_HASH(key, key_len, seed) \
+	(uint32_t)(rte_hash_crc(key, key_len, seed))
+
+
+struct rte_member_setsum;
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Parameter struct used to create set summary
+ */
+struct rte_member_parameters;
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Define different set summary types
+ */
+enum rte_member_setsum_type {
+	RTE_MEMBER_TYPE_HT = 0,  /**< Hash table based set summary. */
+	RTE_MEMBER_TYPE_VBF,     /**< vector of bloom filters. */
+	RTE_MEMBER_NUM_TYPE
+};
+
+/** @internal compare function for different arch. */
+enum rte_member_sig_compare_function {
+	RTE_MEMBER_COMPARE_SCALAR = 0,
+	RTE_MEMBER_COMPARE_AVX2,
+	RTE_MEMBER_COMPARE_NUM
+};
+
+/** @internal setsummary structure. */
+struct rte_member_setsum {
+	enum rte_member_setsum_type type;
+	const char *name;
+	uint32_t key_len;
+	uint32_t socket_id;          /* NUMA Socket ID for memory. */
+	uint32_t prim_hash_seed;
+	uint32_t sec_hash_seed;
+
+
+	/* hash table based */
+	uint32_t bucket_cnt;
+	uint32_t bucket_mask;
+	uint8_t cache;
+	enum rte_member_sig_compare_function sig_cmp_fn;
+
+	/* vector bloom filter*/
+	uint32_t num_set;
+	uint32_t bits;
+	uint32_t bit_mask;
+	uint32_t num_hashes;
+	void *table;
+};
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Parameters used when create the set summary table. Currently user can
+ * specify two types of setsummary: HT based and vBF. For HT based, user can
+ * specify cache or non-cache mode. Here is a table to describe some differences
+ *
+ */
+struct rte_member_parameters {
+	const char *name;			/**< Name of the hash. */
+
+	/**
+	 * User to specify the type of the setsummary from one of
+	 * rte_member_setsum_type.
+	 *
+	 * HT based setsummary is implemented like a hash table. User should use
+	 * this type when there are many sets.
+	 *
+	 * vBF setsummary is a vector of bloom filters. It is used when number
+	 * of sets is not big (less than 32 for current implementation).
+	 */
+	enum rte_member_setsum_type type;
+	/**
+	 * If it is HT based setsummary, user to specify the subtype or mode
+	 * of the setsummary. It could be cache, or non-cache mode.
+	 * Set iscache to be 1 if to use as cache mode.
+	 *
+	 * For cache mode, keys can be evicted out of the HT setsummary. Keys
+	 * with the same signature and map to the same bucket
+	 * will overwrite each other in the setsummary table.
+	 * This mode is useful for the case that the set-summary only
+	 * needs to keep record of the recently inserted keys. Both
+	 * false-negative and false-positive could happen.
+	 *
+	 * For non-cache mode, keys cannot be evicted out of the cache. So for
+	 * this mode the setsummary will become full eventually. Keys with the
+	 * same signature but map to the same bucket will still occupy multiple
+	 * entries. This mode does not give false-negative result.
+	 */
+	uint8_t iscache;
+
+	/**
+	 * For HT setsummary, num_keys equals to the number of entries of the
+	 * table. When the number of keys that inserted to the HT setsummary
+	 * approaches this number, eviction could happen. For cache mode,
+	 * keys could be evicted out of the table. For non-cache mode, keys will
+	 * be evicted to other buckets like cuckoo hash. The table will also
+	 * likely to become full before the number of inserted keys equal to the
+	 * total number of entries.
+	 *
+	 * For vBF, num_keys equal to the expected number of keys that will
+	 * be inserted into the vBF. The implementation assumes the keys are
+	 * evenly distributed to each BF in vBF. This is used to calculate the
+	 * number of bits we need for each BF. User does not specify the size of
+	 * each BF directly because the optimal size depends on the num_keys
+	 * and false positive rate.
+	 */
+	uint32_t num_keys;
+
+
+	/**
+	 * The length of key is used for hash calculation. Since key is not
+	 * stored in set-summary, large key does not require more memory space.
+	 */
+	uint32_t key_len;
+
+
+	/**
+	 * num_set is only relevant to vBF based setsummary.
+	 * num_set is equal to the number of BFs in vBF. For current
+	 * implementation, it only supports 1,2,4,8,16,32 BFs in one vBF set
+	 * summary. If other number of sets are needed, for example 5, the user
+	 * should allocate the minimum available value that larger than 5,
+	 * which is 8.
+	 */
+	uint32_t num_set;
+
+	/**
+	 * false_postive_rate is only relevant to vBF based setsummary.
+	 * false_postivie_rate is the user-defined false positive rate
+	 * given expected number of inserted keys (num_keys). It is used to
+	 * calculate the total number of bits for each BF, and the number of
+	 * hash values used during lookup and insertion. For details please
+	 * refer to vBF implementation and membership library documentation.
+	 *
+	 * HT setsummary's false positive rate is in the order of:
+	 * false_pos = (1/bucket_count)*(1/2^16), since we use 16-bit signature.
+	 * This is because two keys needs to map to same bucket and same
+	 * signature to have a collision (false positive). bucket_count is equal
+	 * to number of entries (num_keys) divided by entry count per bucket
+	 * (RTE_MEMBER_BUCKET_ENTRIES). Thus, the false_postivie_rate is not
+	 * directly set by users.
+	 */
+	float false_positive_rate;
+
+	/**
+	 * We use two seeds to calculate two independent hashes for each key.
+	 *
+	 * For HT type, one hash is used as signature, and the other is used
+	 * for bucket location.
+	 * For vBF type, these two hashes and their combinations are used as
+	 * hash locations to index the bit array.
+	 */
+	uint32_t prim_hash_seed;
+
+	/**
+	 * The secondary seed should be a different value from the primary seed.
+	 */
+	uint32_t sec_hash_seed;
+
+	int socket_id;			/**< NUMA Socket ID for memory. */
+};
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Find an existing set-summary and return a pointer to it.
+ *
+ * @param name
+ *   Name of the set-summary
+ * @return
+ *   Pointer to the set-summary or NULL if object not found
+ *   with rte_errno set appropriately. Possible rte_errno values include:
+ *    - ENOENT - value not available for return
+ */
+void *
+rte_member_find_existing(const char *name);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Create set-summary (SS).
+ *
+ * @param params
+ *   parameters to initialize the setsummary
+ * @return
+ *   return the pointer to the setsummary
+ *   return value is NULL if the creation failed
+ */
+
+void *
+rte_member_create(const struct rte_member_parameters *params);
+
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Lookup key in set-summary (SS).
+ * Single key lookup and return as soon as the first match found
+ * @param setsum
+ *   pointer of a setsummary
+ * @param key
+ *   pointer of the key that needs to lookup
+ * @param set_id
+ *   output the set id matches the key
+ * @return
+ *   return 1 for found a match and 0 for not found a match
+ */
+
+int
+rte_member_lookup(const void *setsum,
+		const void *key, MEMBER_SET_TYPE *set_id);
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * lookup bulk of keys in set-summary (SS).
+ * Each key lookup returns as soon as the first match found
+ * @param setsum
+ *   Pointer of a setsummary
+ * @param keys
+ *   Pointer of bulk of keys that to be lookup
+ * @param num_keys
+ *   Number of keys that will be lookup
+ * @param set_ids
+ *   Output set ids for all the keys to this array.
+ *   User should preallocate array that can contain all results, which size is
+ *   the num_keys.
+ * @return
+ *   The number of keys that found a match
+ */
+
+
+int
+rte_member_lookup_bulk(const void *setsum,
+		const void **keys, uint32_t num_keys,
+		MEMBER_SET_TYPE *set_ids);
+
+
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Lookup a key in set-summary (SS) for multiple matches.
+ * The key lookup will find all matched entries (multiple match).
+ * Note that for cache mode of HT, each key can have at most one match. This is
+ * because keys with same signature that maps to same bucket will overwrite
+ * each other. So multi-match lookup should be used for vBF and non-cache HT.
+ * @param setsum
+ *   pointer of a set-summary
+ * @param key
+ *   The key that to be lookup
+ * @param max_match_per_key
+ *   User specified maximum number of matches for each key. The function returns
+ *   as soon as this number of matches found for the key.
+ * @param set_id
+ *   Output set ids for all the matches of the key. User needs to preallocate
+ *   the array that can contain max_match_per_key number of results.
+ * @return
+ *   The number of matches that found for the key.
+ *   For cache mode HT set-summary, the number should be at most 1
+ */
+
+int
+rte_member_lookup_multi(const void *setsum,
+		const void *key, uint32_t max_match_per_key,
+		MEMBER_SET_TYPE *set_id);
+
+
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Lookup a bulk of keys in set-summary (SS) for multiple matches each key.
+ * Each key lookup will find all matched entries (multiple match).
+ * Note that for cache mode HT, each key can have at most one match. So
+ * multi-match function is mainly used for vBF and non-cache mode HT.
+ * @param setsum
+ *   pointer of a setsummary
+ * @param keys
+ *   The keys that to be lookup
+ * @param num_keys
+ *   The number of keys that will be lookup
+ * @param max_match_per_key
+ *   The possible maximum number of matches for each key
+ * @param match_count
+ *   Output the number of matches for each key in an array
+ * @param set_ids
+ *   Return set ids for all the matches of all keys. User pass in a preallocated
+ *   2D array with first dimension as key index and second dimension as match
+ *   index. For example set_ids[bulk_size][max_match_per_key]
+ * @return
+ *   The number of keys that found one or more matches in the set-summary
+ */
+
+int
+rte_member_lookup_multi_bulk(const void *setsum,
+		const void **keys, uint32_t num_keys,
+		uint32_t max_match_per_key,
+		uint32_t *match_count,
+		MEMBER_SET_TYPE *set_ids);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Insert key into set-summary (SS).
+ *
+ * @param setsum
+ *   pointer of a set-summary
+ * @param key
+ *   the key that needs to be added
+ * @param set_id
+ *   The set id associated with the key that needs to be added. Different mode
+ *   supports different set_id ranges. 0 cannot be used as set_id since
+ *   RTE_MEMBER_NO_MATCH by default is set as 0.
+ *   For HT mode, the set_id has range as [1, 0x7FFF], MSB is reserved.
+ *   For vBF mode the set id is limited by the num_set parameter when create
+ *   the set-summary.
+ * @return
+ *   HT (cache mode) and vBF should never fail unless the set_id is not in the
+ *   valid range. In such case -EINVAL is returned.
+ *   For HT (non-cache mode) it could fail with -ENOSPC error code when table is
+ *   full.
+ *   For success it returns different values for different modes to provide
+ *   extra information for users.
+ *   Return 0 for HT (cache mode) if the add does not cause
+ *   eviction, return 1 otherwise. Return 0 for HT mode if success, -ENOSPC for
+ *   full, and 1 if cuckoo eviction happens. Always return 0 for vBF mode.
+ */
+
+int
+rte_member_add(const void *setsum, const void *key,
+		MEMBER_SET_TYPE set_id);
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * De-allocate memory used by set-summary.
+ * @param setsum
+ *   Pointer to the set summary
+ */
+void
+rte_member_free(void *setsum);
+
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Reset the set-summary tables. E.g. reset bits to be 0 in BF,
+ * reset set_id in each entry to be RTE_MEMBER_NO_MATCH in HT based SS.
+ * @param setsum
+ *   Pointer to the set-summary
+ */
+void
+rte_member_reset(const void *setsum);
+
+
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Delete items from the set-summary. Note that vBF does not support deletion
+ * in current implementation. For vBF, error code of -EINVAL will be returned.
+ * @param setsum
+ *   Pointer to the set-summary
+ * @param key
+ *   The key to be deleted
+ * @param set_id
+ *   For HT mode, we need both key and its corresponding set_id to
+ *   properly delete the key. Without set_id, we may delete other keys with the
+ *   same signature
+ * @return
+ *   If no entry found to delete, an error code of -ENOENT could be returned
+ */
+
+int
+rte_member_delete(void *setsum, const void *key,
+		MEMBER_SET_TYPE set_id);
+
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_H_ */
diff --git a/lib/librte_member/rte_member_version.map b/lib/librte_member/rte_member_version.map
new file mode 100644
index 0000000..b0977e1
--- /dev/null
+++ b/lib/librte_member/rte_member_version.map
@@ -0,0 +1,15 @@ 
+DPDK_17.11 {
+	global:
+
+	rte_member_create;
+	rte_member_lookup;
+	rte_member_lookup_bulk;
+	rte_member_lookup_multi;
+	rte_member_lookup_multi_bulk;
+	rte_member_add;
+	rte_member_free;
+	rte_member_reset;
+	rte_member_delete;
+
+	local: *;
+};