Re: [lng-odp] [API-NEXT PATCH v3 1/2] helper: table: add impl of cuckoo hash table

[HePeng]

Hi, 

   We appreciate more comments on the patch. Thanks. 
> 在 2016年4月27日，下午7:35，Raj Murali  写道：
> 
> Agree with Bill.
> The original copyright statement should be retained and we need to add our's 
> over and above it.
> 
> Raj Murali
> 
> 
> Raj Murali 
> Director - Linaro Networking Group
> Skype: rajmurali_s  │ M: +91 98450 70135  
> Linaro.org  │ Open source software for ARM SoCs
> 
> 
> On 27 April 2016 at 16:53, Bill Fischofer  > wrote:
> I believe the rule is you retain the original copyright from the base code 
> but can add your own copyright for any additions/changes. The point is not to 
> erase history but preserve acknowledgement and the record of the code's BSD 
> provenance.
> 
> See http://www.openbsd.org/policy.html  
> for some discussion of this topic.
> 
> On Wed, Apr 27, 2016 at 4:06 AM, Maxim Uvarov  > wrote:
> On 04/27/16 11:12, Ru Jia wrote:
> Signed-off-by: Ru Jia mailto:ji...@ict.ac.cn>>
> ---
>   helper/Makefile.am|   6 +-
>   helper/cuckootable.c  | 746 
> ++
>   helper/odph_cuckootable.h |  82 +
>   3 files changed, 832 insertions(+), 2 deletions(-)
>   create mode 100644 helper/cuckootable.c
>   create mode 100644 helper/odph_cuckootable.h
> 
> diff --git a/helper/Makefile.am b/helper/Makefile.am
> index 8a86eb7..1763b99 100644
> --- a/helper/Makefile.am
> +++ b/helper/Makefile.am
> @@ -27,13 +27,15 @@ noinst_HEADERS = \
>  $(srcdir)/odph_debug.h \
>  $(srcdir)/odph_hashtable.h \
>  $(srcdir)/odph_lineartable.h \
> -$(srcdir)/odph_list_internal.h
> +$(srcdir)/odph_list_internal.h \
> +$(srcdir)/odph_cuckootable.h
> __LIB__libodphelper_linux_la_SOURCES = \
> eth.c \
> ip.c \
> linux.c \
> hashtable.c \
> -   lineartable.c
> +   lineartable.c \
> +   cuckootable.c
> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la 
> 
> diff --git a/helper/cuckootable.c b/helper/cuckootable.c
> new file mode 100644
> index 000..64bd894
> --- /dev/null
> +++ b/helper/cuckootable.c
> @@ -0,0 +1,746 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/*-
> + *   BSD LICENSE
> + *
> + *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
> + *   All rights reserved.
> 
> Looks like this code was totally rewritten now to ODP. And I probably we 
> should
> check does it make sense to keep Intels copyright here or not. Any ideas?
> 
> Maxim.
> 
> 
> + *
> + *   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 
> +#include 
> +#include 
> +#include 
> +
> +#include "odph_cuckootable.h"
> +#include "odph_debug.h"
> +#include 
> +
> +/* Macro to enable/disable run-time checking of function parameters */
> +#define RETURN_IF_TRUE(cond, retval) do { \
> +   if (cond) \
> +   return retval; \
> +} while (0)
> +
> +/* More efficient acc

Re: [lng-odp] [API-NEXT 1/2] helper: table: add impl of ip lookup table

[HePeng]

Hi, 
This patch aims to provide a trie implementation to Table APIs. The 
functions declared in .h file 
will not be exposed to users. Just like odph_hashtable.h resides in the same 
dir as its .c file.  



> 在 2016年5月16日，下午1:43，Jia Ru  写道：
> 
> The functions of this IP lookup table are almost same with odph_table API. 
> Compared with providing a new IP lookup table API, I think it’s better to use 
> the existing odph_table API. So I didn’t put the header file into 
> odp/helper/include/. 
>  
> From: Bill Fischofer [mailto:bill.fischo...@linaro.org 
> ] 
> Sent: Sunday, May 15, 2016 6:41 AM
> To: Ru Jia
> Cc: LNG ODP Mailman List
> Subject: Re: [lng-odp] [API-NEXT 1/2] helper: table: add impl of ip lookup 
> table
>  
>  
>  
> On Fri, May 13, 2016 at 12:47 AM, Ru Jia  > wrote:
>> This is an implementation of the 16,8,8 ip lookup
>> (longest prefix matching) algorithm. The key of the
>> table is 32-bit IPv4 address.
>> 
>> Signed-off-by: Ru Jia mailto:ji...@ict.ac.cn>>
>> ---
>>  helper/Makefile.am  |   2 +
>>  helper/iplookuptable.c  | 974 
>> 
>>  helper/odph_iplookuptable.h |  58 +++
>>  3 files changed, 1034 insertions(+)
>>  create mode 100644 helper/iplookuptable.c
>>  create mode 100644 helper/odph_iplookuptable.h
>> 
>> diff --git a/helper/Makefile.am b/helper/Makefile.am
>> index aa58e8c..e629c14 100644
>> --- a/helper/Makefile.am
>> +++ b/helper/Makefile.am
>> @@ -27,6 +27,7 @@ noinst_HEADERS = \
>>  $(srcdir)/odph_debug.h \
>>  $(srcdir)/odph_hashtable.h \
>>  $(srcdir)/odph_lineartable.h \
>> +$(srcdir)/odph_iplookuptable.h \
>>  $(srcdir)/odph_list_internal.h
>> 
>>  __LIB__libodphelper_linux_la_SOURCES = \
>> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
>> chksum.c \
>> linux.c \
>> hashtable.c \
>> +   iplookuptable.c \
>> lineartable.c
>> 
>>  lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la 
>> 
>> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
>> new file mode 100644
>> index 000..a0b7e6b
>> --- /dev/null
>> +++ b/helper/iplookuptable.c
>> @@ -0,0 +1,974 @@
>> +/* Copyright (c) 2015, Linaro Limited
>> + * All rights reserved.
>> + *
>> + * SPDX-License-Identifier: BSD-3-Clause
>> + */
>> +
>> +#include 
>> +#include 
>> +#include 
>> +#include 
>> +
>> +#include "odph_iplookuptable.h"
>> +#include "odph_list_internal.h"
>> +#include "odph_debug.h"
>> +#include 
>> +
>> +/** @magic word, write to the first byte of the memory block
>> + *   to indicate this block is used by a ip lookup table
>> + */
>> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
>> +
>> +/* The length(bit) of the IPv4 address */
>> +#define IP_LENGTH 32
>> +
>> +/* The number of L1 entries */
>> +#define ENTRY_NUM_L1   (1 << 16)
>> +/* The size of one L2\L3 subtree */
>> +#define ENTRY_NUM_SUBTREE  (1 << 8)
>> +
>> +#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x0001)
>> +
>> +/** @internal entry struct
>> + *   Structure store an entry of the ip prefix table.
>> + *   Because of the leaf pushing, each entry of the table must have
>> + *   either a child entry, or a nexthop info.
>> + *   If child == 0 and index != ODP_BUFFER_INVALID, this entry has
>> + * a nexthop info, index indicates the buffer that stores the
>> + * nexthop value, and ptr points to the address of the buffer.
>> + *   If child == 1, this entry has a subtree, index indicates
>> + * the buffer that stores the subtree, and ptr points to the
>> + * address of the buffer.
>> + */
>> +typedef struct {
>> +   union {
>> +   uint8_t u8;
>> +   struct {
>> +#if ODP_BYTE_ORDER == ODP_BIG_ENDIAN
>> +   uint8_t child : 1;
>> +   uint8_t cidr  : 7;
>> +#else
>> +   uint8_t cidr  : 7;
>> +   uint8_t child : 1;
>> +#endif
>> +   };
>> +   };
>> +   odp_buffer_t index;
>> +   void *ptr;
>> +} prefix_entry_t;
>> +
>> +/** @internal trie node struct
>> + *  In this IP lookup algorithm, we use a
>> + *  binary tire to detect the overlap prefix.
>> + */
>> +typedef struct trie_node {
>> +   /* tree structure */
>> +   struct trie_node *parent;
>> +   struct trie_node *left;
>> +   struct trie_node *right;
>> +   /* IP prefix length */
>> +   uint8_t cidr;
>> +   /* Nexthop buffer index */
>> +   odp_buffer_t nexthop;
>> +   /* Buffer that stores this node */
>> +   odp_buffer_t buffer;
>> +} trie_node_t;
>> +
>> +/** Number of L2\L3 entries(subtrees) per cache cube.

Re: [lng-odp] [API-NEXT PATCH v3 1/2] helper: table: add impl of ip lookup table

[HePeng]

Ping. 

> 在 2016年5月23日，下午12:26，Ru Jia  写道：
> 
> This is an implementation of the 16,8,8 ip lookup
> (longest prefix matching) algorithm. The key of the
> table is 32-bit IPv4 address.
> 
> Signed-off-by: Ru Jia 
> ---
> helper/Makefile.am  |   4 +-
> helper/iplookuptable.c  | 974 
> helper/odph_iplookuptable.h |  58 +++
> 3 files changed, 1035 insertions(+), 1 deletion(-)
> create mode 100644 helper/iplookuptable.c
> create mode 100644 helper/odph_iplookuptable.h
> 
> diff --git a/helper/Makefile.am b/helper/Makefile.am
> index aa58e8c..2e1d519 100644
> --- a/helper/Makefile.am
> +++ b/helper/Makefile.am
> @@ -27,6 +27,7 @@ noinst_HEADERS = \
>$(srcdir)/odph_debug.h \
>$(srcdir)/odph_hashtable.h \
>$(srcdir)/odph_lineartable.h \
> +  $(srcdir)/odph_iplookuptable.h \
>$(srcdir)/odph_list_internal.h
> 
> __LIB__libodphelper_linux_la_SOURCES = \
> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
>   chksum.c \
>   linux.c \
>   hashtable.c \
> - lineartable.c
> + lineartable.c \
> + iplookuptable.c
> 
> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la
> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
> new file mode 100644
> index 000..a0b7e6b
> --- /dev/null
> +++ b/helper/iplookuptable.c
> @@ -0,0 +1,974 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include "odph_iplookuptable.h"
> +#include "odph_list_internal.h"
> +#include "odph_debug.h"
> +#include 
> +
> +/** @magic word, write to the first byte of the memory block
> + *   to indicate this block is used by a ip lookup table
> + */
> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
> +
> +/* The length(bit) of the IPv4 address */
> +#define IP_LENGTH 32
> +
> +/* The number of L1 entries */
> +#define ENTRY_NUM_L1 (1 << 16)
> +/* The size of one L2\L3 subtree */
> +#define ENTRY_NUM_SUBTREE(1 << 8)
> +
> +#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x0001)
> +
> +/** @internal entry struct
> + *   Structure store an entry of the ip prefix table.
> + *   Because of the leaf pushing, each entry of the table must have
> + *   either a child entry, or a nexthop info.
> + *   If child == 0 and index != ODP_BUFFER_INVALID, this entry has
> + *   a nexthop info, index indicates the buffer that stores the
> + *   nexthop value, and ptr points to the address of the buffer.
> + *   If child == 1, this entry has a subtree, index indicates
> + *   the buffer that stores the subtree, and ptr points to the
> + *   address of the buffer.
> + */
> +typedef struct {
> + union {
> + uint8_t u8;
> + struct {
> +#if ODP_BYTE_ORDER == ODP_BIG_ENDIAN
> + uint8_t child : 1;
> + uint8_t cidr  : 7;
> +#else
> + uint8_t cidr  : 7;
> + uint8_t child : 1;
> +#endif
> + };
> + };
> + odp_buffer_t index;
> + void *ptr;
> +} prefix_entry_t;
> +
> +/** @internal trie node struct
> + *  In this IP lookup algorithm, we use a
> + *  binary tire to detect the overlap prefix.
> + */
> +typedef struct trie_node {
> + /* tree structure */
> + struct trie_node *parent;
> + struct trie_node *left;
> + struct trie_node *right;
> + /* IP prefix length */
> + uint8_t cidr;
> + /* Nexthop buffer index */
> + odp_buffer_t nexthop;
> + /* Buffer that stores this node */
> + odp_buffer_t buffer;
> +} trie_node_t;
> +
> +/** Number of L2\L3 entries(subtrees) per cache cube. */
> +#define CACHE_NUM_SUBTREE(1 << 13)
> +/** Number of nexthop values per cache cube. */
> +#define CACHE_NUM_NEXTHOP(1 << 20)
> +/** Number of trie nodes per cache cube. */
> +#define CACHE_NUM_TRIE   (1 << 20)
> +
> +/** @typedef cache_type_t
> + *   Cache node type
> + */
> +typedef enum {
> + CACHE_TYPE_SUBTREE = 0,
> + CACHE_TYPE_TRIE,
> + CACHE_TYPE_NEXTHOP
> +} cache_type_t;
> +
> +/** A IP lookup table structure. */
> +typedef struct {
> + /**< for check */
> + uint32_t magicword;
> + /** Name of the hash. */
> + char name[ODPH_TABLE_NAME_LEN];
> + /** Total L1 entries. */
> + prefix_entry_t *l1e;
> + /** Root node of the binary trie */
> + trie_node_t *trie;
> + /** Length of value. */
> + uint32_t nexthop_len;
> + /** Queues of free slots (caches)
> +  *  There are three queues:
> +  *  - free_slots[CACHE_TYPE_SUBTREE] is used for L2 and
> +  *L3 entries (subtrees). Each buffer sto

Re: [lng-odp] [API-NEXT PATCH v3 2/2] helper: test: add validation test of ip lookup table

[HePeng]

Ping
> 在 2016年5月23日，下午12:26，Ru Jia  写道：
> 
> Signed-off-by: Ru Jia 
> ---
> helper/test/Makefile.am |   4 +-
> helper/test/iplookuptable.c | 173 
> 2 files changed, 176 insertions(+), 1 deletion(-)
> create mode 100644 helper/test/iplookuptable.c
> 
> diff --git a/helper/test/Makefile.am b/helper/test/Makefile.am
> index 7f0b67d..e8524e7 100644
> --- a/helper/test/Makefile.am
> +++ b/helper/test/Makefile.am
> @@ -9,7 +9,8 @@ EXECUTABLES = chksum$(EXEEXT) \
>   thread$(EXEEXT) \
>   parse$(EXEEXT)\
>   process$(EXEEXT)\
> -  table$(EXEEXT)
> +   table$(EXEEXT)\
> +   iplookuptable$(EXEEXT)
> 
> COMPILE_ONLY =
> 
> @@ -31,3 +32,4 @@ dist_process_SOURCES = process.c
> dist_parse_SOURCES = parse.c
> process_LDADD = $(LIB)/libodphelper-linux.la $(LIB)/libodp-linux.la
> dist_table_SOURCES = table.c
> +dist_iplookuptable_SOURCES = iplookuptable.c
> diff --git a/helper/test/iplookuptable.c b/helper/test/iplookuptable.c
> new file mode 100644
> index 000..b915d2d
> --- /dev/null
> +++ b/helper/test/iplookuptable.c
> @@ -0,0 +1,173 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include <../odph_iplookuptable.h>
> +#include 
> +
> +static void print_prefix_info(
> + const char *msg, uint32_t ip, uint8_t cidr)
> +{
> + int i = 0;
> + uint8_t *ptr = (uint8_t *)(&ip);
> +
> + printf("%s IP prefix: ", msg);
> + for (i = 3; i >= 0; i--) {
> + if (i != 3)
> + printf(".");
> + printf("%d", ptr[i]);
> + }
> + printf("/%d\n", cidr);
> +}
> +
> +/*
> + * Basic sequence of operations for a single key:
> + *   - put short prefix
> + *   - put long prefix
> + *   - get (hit long prefix)
> + *   - remove long prefix
> + *   - get (hit short prefix)
> + */
> +static int test_ip_lookup_table(void)
> +{
> + odph_iplookup_prefix_t prefix1, prefix2;
> + odph_table_t table;
> + int ret;
> + uint32_t value1 = 1, value2 = 2, result = 0, lkp_ip = 0;
> +
> + table = odph_iplookup_table_create(
> + "prefix_test", 0, 0, sizeof(uint32_t));
> + if (table == NULL) {
> + printf("IP prefix lookup table creation failed\n");
> + return -1;
> + }
> +
> + ret = odph_ipv4_addr_parse(&prefix1.ip, "192.168.0.0");
> + if (ret < 0) {
> + printf("Failed to get IP addr from str\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> + prefix1.cidr = 11;
> +
> + ret = odph_ipv4_addr_parse(&prefix2.ip, "192.168.0.0");
> + if (ret < 0) {
> + printf("Failed to get IP addr from str\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> + prefix2.cidr = 24;
> +
> + ret = odph_ipv4_addr_parse(&lkp_ip, "192.168.0.1");
> + if (ret < 0) {
> + printf("Failed to get IP addr from str\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> +
> + /* test with standard put/get/remove functions */
> + ret = odph_iplookup_table_put_value(table, &prefix1, &value1);
> + print_prefix_info("Add", prefix1.ip, prefix1.cidr);
> + if (ret < 0) {
> + printf("Failed to add ip prefix\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> +
> + ret = odph_iplookup_table_get_value(table, &lkp_ip, &result, 0);
> + print_prefix_info("Lkp", lkp_ip, 32);
> + if (ret < 0 || result != 1) {
> + printf("Failed to find longest prefix\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> +
> + /* add a longer prefix */
> + ret = odph_iplookup_table_put_value(table, &prefix2, &value2);
> + print_prefix_info("Add", prefix2.ip, prefix2.cidr);
> + if (ret < 0) {
> + printf("Failed to add ip prefix\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> +
> + ret = odph_iplookup_table_get_value(table, &lkp_ip, &result, 0);
> + print_prefix_info("Lkp", lkp_ip, 32);
> + if (ret < 0 || result != 2) {
> + printf("Failed to find longest prefix\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> +
> + ret = odph_iplookup_table_remove_value(table, &prefix2);
> + print_prefix_info("Del", prefix2.ip, prefix2.cidr);
> + if (ret < 0) {
> + printf("Failed to delete ip prefix\n");
> + odph_iplookup_table_destroy(table);
> + return -1;
> + }
> +
> + ret = odph_iplookup_table_get_value(table, &lkp_ip, &result, 0);
> + print_prefix_info("

Re: [lng-odp] [API-NEXT PATCH v3 1/2] helper: table: add impl of ip lookup table

[HePeng]

sorry to reply this late. 
Ru Jia recently has been very busy and I happened to miss this email and still 
am wondering 
why nobody review this. 

Now, we submit the v4. 


> 在 2016年6月3日，上午2:30，Maxim Uvarov  写道：
> 
> Just status to be clear here. Bill wanted to review/test this patch but fail 
> to apply it.
> Please update to current master and send v4.
> 
> Maxim.
> 
> On 06/02/16 06:25, HePeng wrote:
>> Ping.
>> 
>>> 在 2016年5月23日，下午12:26，Ru Jia  写道：
>>> 
>>> This is an implementation of the 16,8,8 ip lookup
>>> (longest prefix matching) algorithm. The key of the
>>> table is 32-bit IPv4 address.
>>> 
>>> Signed-off-by: Ru Jia 
>>> ---
>>> helper/Makefile.am  |   4 +-
>>> helper/iplookuptable.c  | 974 
>>> 
>>> helper/odph_iplookuptable.h |  58 +++
>>> 3 files changed, 1035 insertions(+), 1 deletion(-)
>>> create mode 100644 helper/iplookuptable.c
>>> create mode 100644 helper/odph_iplookuptable.h
>>> 
>>> diff --git a/helper/Makefile.am b/helper/Makefile.am
>>> index aa58e8c..2e1d519 100644
>>> --- a/helper/Makefile.am
>>> +++ b/helper/Makefile.am
>>> @@ -27,6 +27,7 @@ noinst_HEADERS = \
>>>  $(srcdir)/odph_debug.h \
>>>  $(srcdir)/odph_hashtable.h \
>>>  $(srcdir)/odph_lineartable.h \
>>> +$(srcdir)/odph_iplookuptable.h \
>>>  $(srcdir)/odph_list_internal.h
>>> 
>>> __LIB__libodphelper_linux_la_SOURCES = \
>>> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
>>> chksum.c \
>>> linux.c \
>>> hashtable.c \
>>> -   lineartable.c
>>> +   lineartable.c \
>>> +   iplookuptable.c
>>> 
>>> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la
>>> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
>>> new file mode 100644
>>> index 000..a0b7e6b
>>> --- /dev/null
>>> +++ b/helper/iplookuptable.c
>>> @@ -0,0 +1,974 @@
>>> +/* Copyright (c) 2015, Linaro Limited
>>> + * All rights reserved.
>>> + *
>>> + * SPDX-License-Identifier: BSD-3-Clause
>>> + */
>>> +
>>> +#include 
>>> +#include 
>>> +#include 
>>> +#include 
>>> +
>>> +#include "odph_iplookuptable.h"
>>> +#include "odph_list_internal.h"
>>> +#include "odph_debug.h"
>>> +#include 
>>> +
>>> +/** @magic word, write to the first byte of the memory block
>>> + *   to indicate this block is used by a ip lookup table
>>> + */
>>> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
>>> +
>>> +/* The length(bit) of the IPv4 address */
>>> +#define IP_LENGTH 32
>>> +
>>> +/* The number of L1 entries */
>>> +#define ENTRY_NUM_L1   (1 << 16)
>>> +/* The size of one L2\L3 subtree */
>>> +#define ENTRY_NUM_SUBTREE  (1 << 8)
>>> +
>>> +#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x0001)
>>> +
>>> +/** @internal entry struct
>>> + *   Structure store an entry of the ip prefix table.
>>> + *   Because of the leaf pushing, each entry of the table must have
>>> + *   either a child entry, or a nexthop info.
>>> + *   If child == 0 and index != ODP_BUFFER_INVALID, this entry has
>>> + * a nexthop info, index indicates the buffer that stores the
>>> + * nexthop value, and ptr points to the address of the buffer.
>>> + *   If child == 1, this entry has a subtree, index indicates
>>> + * the buffer that stores the subtree, and ptr points to the
>>> + * address of the buffer.
>>> + */
>>> +typedef struct {
>>> +   union {
>>> +   uint8_t u8;
>>> +   struct {
>>> +#if ODP_BYTE_ORDER == ODP_BIG_ENDIAN
>>> +   uint8_t child : 1;
>>> +   uint8_t cidr  : 7;
>>> +#else
>>> +   uint8_t cidr  : 7;
>>> +   uint8_t child : 1;
>>> +#endif
>>> +   };
>>> +   };
>>> +   odp_buffer_t index;
>>> +   void *ptr;

Re: [lng-odp] [API-NEXT PATCH v4 1/2] helper: table: add impl of ip lookup table

[HePeng]

Hi, bill
 this patch is based on the current API-NEXT …
 
> 在 2016年6月14日，上午6:24，Bill Fischofer  写道：
> 
> v4 of this patch still doesn't apply for me:
> 
> bill@Ubuntu15:~/linaro/review$ git am --reject ~/Mail/Incoming/Ru/5
> Applying: helper: table: add impl of ip lookup table
> fatal: corrupt patch at line 14
> Patch failed at 0001 helper: table: add impl of ip lookup table
> The copy of the patch that failed is found in: .git/rebase-apply/patch
> When you have resolved this problem, run "git am --continue".
> If you prefer to skip this patch, run "git am --skip" instead.
> To restore the original branch and stop patching, run "git am --abort".
> 
> Looks like this still needs a rebase on to the current master?
> 
> Thanks.
> 
> Bill
> 
> 
> 
> On Mon, Jun 13, 2016 at 3:57 AM, Ru Jia  wrote:
> 
>> This is an implementation of the 16,8,8 ip lookup
>> (longest prefix matching) algorithm. The key of the
>> table is 32-bit IPv4 address.
>> 
>> Signed-off-by: Ru Jia 
>> ---
>> helper/Makefile.am  |   4 +-
>> helper/iplookuptable.c  | 934
>> 
>> helper/odph_iplookuptable.h |  58 +++
>> 3 files changed, 995 insertions(+), 1 deletion(-)
>> create mode 100644 helper/iplookuptable.c
>> create mode 100644 helper/odph_iplookuptable.h
>> 
>> diff --git a/helper/Makefile.am b/helper/Makefile.am
>> index aa58e8c..2e1d519 100644
>> --- a/helper/Makefile.am
>> +++ b/helper/Makefile.am
>> @@ -27,6 +27,7 @@ noinst_HEADERS = \
>> $(srcdir)/odph_debug.h \
>> $(srcdir)/odph_hashtable.h \
>> $(srcdir)/odph_lineartable.h \
>> +$(srcdir)/odph_iplookuptable.h \
>> $(srcdir)/odph_list_internal.h
>> 
>> __LIB__libodphelper_linux_la_SOURCES = \
>> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
>>chksum.c \
>>linux.c \
>>hashtable.c \
>> -   lineartable.c
>> +   lineartable.c \
>> +   iplookuptable.c
>> 
>> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la
>> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
>> new file mode 100644
>> index 000..8763abc
>> --- /dev/null
>> +++ b/helper/iplookuptable.c
>> @@ -0,0 +1,934 @@
>> +/* Copyright (c) 2016, Linaro Limited
>> + * All rights reserved.
>> + *
>> + * SPDX-License-Identifier: BSD-3-Clause
>> + */
>> +
>> +#include 
>> +#include 
>> +#include 
>> +#include 
>> +
>> +#include "odph_iplookuptable.h"
>> +#include "odph_list_internal.h"
>> +#include "odph_debug.h"
>> +#include 
>> +
>> +/** @magic word, write to the first byte of the memory block
>> + *   to indicate this block is used by a ip lookup table
>> + */
>> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
>> +
>> +/* The length(bit) of the IPv4 address */
>> +#define IP_LENGTH 32
>> +
>> +/* The number of L1 entries */
>> +#define ENTRY_NUM_L1   (1 << 16)
>> +/* The size of one L2\L3 subtree */
>> +#define ENTRY_NUM_SUBTREE  (1 << 8)
>> +
>> +#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x0001)
>> +
>> +/** @internal entry struct
>> + *   Structure store an entry of the ip prefix table.
>> + *   Because of the leaf pushing, each entry of the table must have
>> + *   either a child entry, or a nexthop info.
>> + *   If child == 0 and index != ODP_BUFFER_INVALID, this entry has
>> + * a nexthop info, index indicates the buffer that stores the
>> + * nexthop value, and ptr points to the address of the buffer.
>> + *   If child == 1, this entry has a subtree, index indicates
>> + * the buffer that stores the subtree, and ptr points to the
>> + * address of the buffer.
>> + */
>> +typedef struct {
>> +   union {
>> +   uint8_t u8;
>> +   struct {
>> +#if ODP_BYTE_ORDER == ODP_BIG_ENDIAN
>> +   uint8_t child : 1;
>> +   uint8_t cidr  : 7;
>> +#else
>> +   uint8_t cidr  : 7;
>> +   uint8_t child : 1;
>> +#endif
>> +   };
>> +   };
>> +   union {
>> +   odp_buffer_t nexthop;
>> +   void *ptr;
>> +   };
>> +} prefix_entry_t;
>> +
>> +#define ENTRY_SIZE (sizeof(prefix_entry_t) + sizeof(odp_buffer_t))
>> +#define ENTRY_BUFF_ARR(x) ((odp_buffer_t *)((char *)x \
>> +   + sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE))
>> +
>> +/** @internal trie node struct
>> + *  In this IP lookup algorithm, we use a
>> + *  binary tire to detect the overlap prefix.
>> + */
>> +typedef struct trie_node {
>> +   /* tree structure */
>> +   struct trie_node *parent;
>> +   struct trie_node *left;
>> +   struct trie_node *right;
>> +   /* IP prefix length */
>> +   uint8_t cidr;
>> +   /* Nextho

Re: [lng-odp] [API-NEXT PATCH v3 1/2] helper: table: add impl of ip lookup table

[HePeng]

Yes, we would like to have a discussion on these two patches. 
But I cannot add it myself, I do not have the account. 
> 在 2016年6月13日，下午8:19，Mike Holmes  写道：
> 
> Hi  HePeng
> 
> If you would like to try to stir up interest you could raise it at the weekly 
> call as well as try to get viewers interested on the list.
> There is a call this week [1] but the call will be cancelled next week due to 
> the OPNFV summit.
> 
> Just let Bill, Maxim or I know and we can add it to the agenda.
> 
> [1] https://collaborate.linaro.org/display/ODP/2016-06-14+ODP+ARCH 
> <https://collaborate.linaro.org/display/ODP/2016-06-14+ODP+ARCH>
> 
> On 13 June 2016 at 05:07, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
> sorry to reply this late.
> Ru Jia recently has been very busy and I happened to miss this email and 
> still am wondering
> why nobody review this.
> 
> Now, we submit the v4.
> 
> 
> > 在 2016年6月3日，上午2:30，Maxim Uvarov  > <mailto:maxim.uva...@linaro.org>> 写道：
> >
> > Just status to be clear here. Bill wanted to review/test this patch but 
> > fail to apply it.
> > Please update to current master and send v4.
> >
> > Maxim.
> >
> > On 06/02/16 06:25, HePeng wrote:
> >> Ping.
> >>
> >>> 在 2016年5月23日，下午12:26，Ru Jia mailto:ji...@ict.ac.cn>> 写道：
> >>>
> >>> This is an implementation of the 16,8,8 ip lookup
> >>> (longest prefix matching) algorithm. The key of the
> >>> table is 32-bit IPv4 address.
> >>>
> >>> Signed-off-by: Ru Jia mailto:ji...@ict.ac.cn>>
> >>> ---
> >>> helper/Makefile.am  |   4 +-
> >>> helper/iplookuptable.c  | 974 
> >>> 
> >>> helper/odph_iplookuptable.h |  58 +++
> >>> 3 files changed, 1035 insertions(+), 1 deletion(-)
> >>> create mode 100644 helper/iplookuptable.c
> >>> create mode 100644 helper/odph_iplookuptable.h
> >>>
> >>> diff --git a/helper/Makefile.am b/helper/Makefile.am
> >>> index aa58e8c..2e1d519 100644
> >>> --- a/helper/Makefile.am
> >>> +++ b/helper/Makefile.am
> >>> @@ -27,6 +27,7 @@ noinst_HEADERS = \
> >>>  $(srcdir)/odph_debug.h \
> >>>  $(srcdir)/odph_hashtable.h \
> >>>  $(srcdir)/odph_lineartable.h \
> >>> +$(srcdir)/odph_iplookuptable.h \
> >>>  $(srcdir)/odph_list_internal.h
> >>>
> >>> __LIB__libodphelper_linux_la_SOURCES = \
> >>> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
> >>> chksum.c \
> >>> linux.c \
> >>> hashtable.c \
> >>> -   lineartable.c
> >>> +   lineartable.c \
> >>> +   iplookuptable.c
> >>>
> >>> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la 
> >>> <http://libodphelper-linux.la/>
> >>> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
> >>> new file mode 100644
> >>> index 000..a0b7e6b
> >>> --- /dev/null
> >>> +++ b/helper/iplookuptable.c
> >>> @@ -0,0 +1,974 @@
> >>> +/* Copyright (c) 2015, Linaro Limited
> >>> + * All rights reserved.
> >>> + *
> >>> + * SPDX-License-Identifier: BSD-3-Clause
> >>> + */
> >>> +
> >>> +#include 
> >>> +#include 
> >>> +#include 
> >>> +#include 
> >>> +
> >>> +#include "odph_iplookuptable.h"
> >>> +#include "odph_list_internal.h"
> >>> +#include "odph_debug.h"
> >>> +#include 
> >>> +
> >>> +/** @magic word, write to the first byte of the memory block
> >>> + *   to indicate this block is used by a ip lookup table
> >>> + */
> >>> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
> >>> +
> >>> +/* The length(bit) of the IPv4 address */
> >>> +#define IP_LENGTH 32
> >>> +
> >>> +/* The number of L1 entries */
> >>> +#define ENTRY_NUM_L1   (1 << 16)
> >>> +/* The size of one L2\L3 subtree */
> >>> +#define ENTRY_NUM_SUBTREE  (1 << 8)
&

Re: [lng-odp] [API-NEXT PATCH v4 1/2] helper: table: add impl of ip lookup table

[HePeng]

Ping?
> 在 2016年6月14日，上午9:30，HePeng  写道：
> 
> Hi, bill
> this patch is based on the current API-NEXT …
> 
>> 在 2016年6月14日，上午6:24，Bill Fischofer  写道：
>> 
>> v4 of this patch still doesn't apply for me:
>> 
>> bill@Ubuntu15:~/linaro/review$ git am --reject ~/Mail/Incoming/Ru/5
>> Applying: helper: table: add impl of ip lookup table
>> fatal: corrupt patch at line 14
>> Patch failed at 0001 helper: table: add impl of ip lookup table
>> The copy of the patch that failed is found in: .git/rebase-apply/patch
>> When you have resolved this problem, run "git am --continue".
>> If you prefer to skip this patch, run "git am --skip" instead.
>> To restore the original branch and stop patching, run "git am --abort".
>> 
>> Looks like this still needs a rebase on to the current master?
>> 
>> Thanks.
>> 
>> Bill
>> 
>> 
>> 
>> On Mon, Jun 13, 2016 at 3:57 AM, Ru Jia  wrote:
>> 
>>> This is an implementation of the 16,8,8 ip lookup
>>> (longest prefix matching) algorithm. The key of the
>>> table is 32-bit IPv4 address.
>>> 
>>> Signed-off-by: Ru Jia 
>>> ---
>>> helper/Makefile.am  |   4 +-
>>> helper/iplookuptable.c  | 934
>>> 
>>> helper/odph_iplookuptable.h |  58 +++
>>> 3 files changed, 995 insertions(+), 1 deletion(-)
>>> create mode 100644 helper/iplookuptable.c
>>> create mode 100644 helper/odph_iplookuptable.h
>>> 
>>> diff --git a/helper/Makefile.am b/helper/Makefile.am
>>> index aa58e8c..2e1d519 100644
>>> --- a/helper/Makefile.am
>>> +++ b/helper/Makefile.am
>>> @@ -27,6 +27,7 @@ noinst_HEADERS = \
>>>$(srcdir)/odph_debug.h \
>>>$(srcdir)/odph_hashtable.h \
>>>$(srcdir)/odph_lineartable.h \
>>> +$(srcdir)/odph_iplookuptable.h \
>>>$(srcdir)/odph_list_internal.h
>>> 
>>> __LIB__libodphelper_linux_la_SOURCES = \
>>> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
>>>   chksum.c \
>>>   linux.c \
>>>   hashtable.c \
>>> -   lineartable.c
>>> +   lineartable.c \
>>> +   iplookuptable.c
>>> 
>>> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la
>>> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
>>> new file mode 100644
>>> index 000..8763abc
>>> --- /dev/null
>>> +++ b/helper/iplookuptable.c
>>> @@ -0,0 +1,934 @@
>>> +/* Copyright (c) 2016, Linaro Limited
>>> + * All rights reserved.
>>> + *
>>> + * SPDX-License-Identifier: BSD-3-Clause
>>> + */
>>> +
>>> +#include 
>>> +#include 
>>> +#include 
>>> +#include 
>>> +
>>> +#include "odph_iplookuptable.h"
>>> +#include "odph_list_internal.h"
>>> +#include "odph_debug.h"
>>> +#include 
>>> +
>>> +/** @magic word, write to the first byte of the memory block
>>> + *   to indicate this block is used by a ip lookup table
>>> + */
>>> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
>>> +
>>> +/* The length(bit) of the IPv4 address */
>>> +#define IP_LENGTH 32
>>> +
>>> +/* The number of L1 entries */
>>> +#define ENTRY_NUM_L1   (1 << 16)
>>> +/* The size of one L2\L3 subtree */
>>> +#define ENTRY_NUM_SUBTREE  (1 << 8)
>>> +
>>> +#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x0001)
>>> +
>>> +/** @internal entry struct
>>> + *   Structure store an entry of the ip prefix table.
>>> + *   Because of the leaf pushing, each entry of the table must have
>>> + *   either a child entry, or a nexthop info.
>>> + *   If child == 0 and index != ODP_BUFFER_INVALID, this entry has
>>> + * a nexthop info, index indicates the buffer that stores the
>>> + * nexthop value, and ptr points to the address of the buffer.
>>> + *   If child == 1, this entry has a subtree, index indicates
>>> + * the buffer that stores the subtree, and ptr points to the
>>> + * add

Re: [lng-odp] [API-NEXT PATCH v4 1/2] helper: table: add impl of ip lookup table

[HePeng]

Ping?
> 在 2016年6月23日，下午4:05，HePeng  写道：
> 
> Hello，is there anyone who is reviewing this patch?
>> 在 2016年6月17日，下午2:01，HePeng  写道：
>> 
>> Ping?
>>> 在 2016年6月14日，上午9:30，HePeng  写道：
>>> 
>>> Hi, bill
>>> this patch is based on the current API-NEXT …
>>> 
>>>> 在 2016年6月14日，上午6:24，Bill Fischofer  写道：
>>>> 
>>>> v4 of this patch still doesn't apply for me:
>>>> 
>>>> bill@Ubuntu15:~/linaro/review$ git am --reject ~/Mail/Incoming/Ru/5
>>>> Applying: helper: table: add impl of ip lookup table
>>>> fatal: corrupt patch at line 14
>>>> Patch failed at 0001 helper: table: add impl of ip lookup table
>>>> The copy of the patch that failed is found in: .git/rebase-apply/patch
>>>> When you have resolved this problem, run "git am --continue".
>>>> If you prefer to skip this patch, run "git am --skip" instead.
>>>> To restore the original branch and stop patching, run "git am --abort".
>>>> 
>>>> Looks like this still needs a rebase on to the current master?
>>>> 
>>>> Thanks.
>>>> 
>>>> Bill
>>>> 
>>>> 
>>>> 
>>>> On Mon, Jun 13, 2016 at 3:57 AM, Ru Jia  wrote:
>>>> 
>>>>> This is an implementation of the 16,8,8 ip lookup
>>>>> (longest prefix matching) algorithm. The key of the
>>>>> table is 32-bit IPv4 address.
>>>>> 
>>>>> Signed-off-by: Ru Jia 
>>>>> ---
>>>>> helper/Makefile.am  |   4 +-
>>>>> helper/iplookuptable.c  | 934
>>>>> 
>>>>> helper/odph_iplookuptable.h |  58 +++
>>>>> 3 files changed, 995 insertions(+), 1 deletion(-)
>>>>> create mode 100644 helper/iplookuptable.c
>>>>> create mode 100644 helper/odph_iplookuptable.h
>>>>> 
>>>>> diff --git a/helper/Makefile.am b/helper/Makefile.am
>>>>> index aa58e8c..2e1d519 100644
>>>>> --- a/helper/Makefile.am
>>>>> +++ b/helper/Makefile.am
>>>>> @@ -27,6 +27,7 @@ noinst_HEADERS = \
>>>>>  $(srcdir)/odph_debug.h \
>>>>>  $(srcdir)/odph_hashtable.h \
>>>>>  $(srcdir)/odph_lineartable.h \
>>>>> +$(srcdir)/odph_iplookuptable.h \
>>>>>  $(srcdir)/odph_list_internal.h
>>>>> 
>>>>> __LIB__libodphelper_linux_la_SOURCES = \
>>>>> @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \
>>>>> chksum.c \
>>>>> linux.c \
>>>>> hashtable.c \
>>>>> -   lineartable.c
>>>>> +   lineartable.c \
>>>>> +   iplookuptable.c
>>>>> 
>>>>> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la
>>>>> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c
>>>>> new file mode 100644
>>>>> index 000..8763abc
>>>>> --- /dev/null
>>>>> +++ b/helper/iplookuptable.c
>>>>> @@ -0,0 +1,934 @@
>>>>> +/* Copyright (c) 2016, Linaro Limited
>>>>> + * All rights reserved.
>>>>> + *
>>>>> + * SPDX-License-Identifier: BSD-3-Clause
>>>>> + */
>>>>> +
>>>>> +#include 
>>>>> +#include 
>>>>> +#include 
>>>>> +#include 
>>>>> +
>>>>> +#include "odph_iplookuptable.h"
>>>>> +#include "odph_list_internal.h"
>>>>> +#include "odph_debug.h"
>>>>> +#include 
>>>>> +
>>>>> +/** @magic word, write to the first byte of the memory block
>>>>> + *   to indicate this block is used by a ip lookup table
>>>>> + */
>>>>> +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
>>>>> +
>>>>> +/* The length(bit) of the IPv4 address */
>>>>> +#define IP_LENGTH 32
>>>>> +
>>>>> +/* The number of L1 entries */
>>>>> +#define ENTRY_NUM_L1   (1 << 16)
>>>>> +/* The size o

Re: [lng-odp] [API-NEXT PATCH v4 1/2] helper: table: add impl of ip lookup table

[HePeng]

Hi, do you guys use patch this using API-NEXT branch?


> 在 2016年6月30日，上午1:23，Bill Fischofer  写道：
> 
> I see the same behavior.  git am reports the first patch is corrupt at line
> 14, but patch can apply it.  Not sure what is going on with that.
> 
> The test runs fine, however this still has a number of checkpatch issues
> that need to be addressed:
> 
> WARNING: please, no spaces at the start of a line
> #480: FILE: helper/iplookuptable.c:434:
> +return NULL;$
> 
> WARNING: braces {} are not necessary for single statement blocks
> #532: FILE: helper/iplookuptable.c:486:
> + for (i = 0; i < ENTRY_NUM_L1; i++) {
> + tbl->l1e[i].nexthop = ODP_BUFFER_INVALID;
> + }
> 
> WARNING: please, no spaces at the start of a line
> #617: FILE: helper/iplookuptable.c:571:
> +return 0;$
> 
> WARNING: line over 80 characters
> #660: FILE: helper/iplookuptable.c:614:
> + odph_iplookup_table_impl *tbl, prefix_entry_t *entry, odp_buffer_t *buff,
> 
> WARNING: line over 80 characters
> #730: FILE: helper/iplookuptable.c:684:
> + impl, impl->trie, prefix->ip, prefix->cidr, nexthop);
> 
> WARNING: line over 80 characters
> #792: FILE: helper/iplookuptable.c:746:
> + odph_iplookup_table_impl *tbl, prefix_entry_t *l1e, odp_buffer_t *buff,
> 
> WARNING: line over 80 characters
> #872: FILE: helper/iplookuptable.c:826:
> + if (ne->child != 0 || ne->cidr != cidr || ne->nexthop != index) {
> 
> WARNING: line over 80 characters
> #882: FILE: helper/iplookuptable.c:836:
> + odph_iplookup_table_impl *tbl, prefix_entry_t *e, odp_buffer_t *buff,
> 
> WARNING: line over 80 characters
> #899: FILE: helper/iplookuptable.c:853:
> + tbl, ne, nbuff, ip, cidr - 8, level + 8, depth + 1);
> 
> total: 0 errors, 9 warnings, 0 checks, 1007 lines checked
> 
> NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL
> DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO
> 
> 0001-helper-table-add-impl-of-ip-lookup-table.patch has style problems,
> please review.
> 
> If any of these errors are false positives, please report
> them to the maintainer, see CHECKPATCH in MAINTAINERS.
> total: 0 errors, 0 warnings, 0 checks, 187 lines checked
> 
> NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL
> DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO
> 
> 0002-helper-test-add-validation-test-of-ip-lookup-table.patch has no
> obvious style problems and is ready for submission.
> 
> 
> On Fri, Jun 17, 2016 at 2:13 AM, Maxim Uvarov 
> wrote:
> 
>> Bill,
>> 
>> I'm able to apply it with just:
>> git am -s -3 /tmp/1/*.eml
>> patch -p1 < /opt/Linaro/odp3.git/.git/rebase-apply/patch
>> git add -A
>> git am --continue
>> 
>> Interesting that git am -3 can not resolve conflicts but patch -p1 works
>> fine.
>> 
>> He, Bill is travelling and will be on conference so it will take some time
>> for him to respond / review.
>> 
>> Maxim.
>> 
>> 
>> On 06/17/16 09:01, HePeng wrote:
>> 
>>> Ping?
>>> 
>>>> 在 2016年6月14日，上午9:30，HePeng  写道：
>>>> 
>>>> Hi, bill
>>>> this patch is based on the current API-NEXT …
>>>> 
>>>> 在 2016年6月14日，上午6:24，Bill Fischofer  写道：
>>>>> 
>>>>> v4 of this patch still doesn't apply for me:
>>>>> 
>>>>> bill@Ubuntu15:~/linaro/review$ git am --reject ~/Mail/Incoming/Ru/5
>>>>> Applying: helper: table: add impl of ip lookup table
>>>>> fatal: corrupt patch at line 14
>>>>> Patch failed at 0001 helper: table: add impl of ip lookup table
>>>>> The copy of the patch that failed is found in: .git/rebase-apply/patch
>>>>> When you have resolved this problem, run "git am --continue".
>>>>> If you prefer to skip this patch, run "git am --skip" instead.
>>>>> To restore the original branch and stop patching, run "git am --abort".
>>>>> 
>>>>> Looks like this still needs a rebase on to the current master?
>>>>> 
>>>>> Thanks.
>>>>> 
>>>>> Bill
>>>>> 
>>>>> 
>>>>> 
>>>>> On Mon, Jun 13, 2016 at 3:57 AM, Ru Jia  wrote:
>>>>> 
>>>>> This is an implementation of the 16,8,8 ip lookup
>>>>>> (longest prefix matching) algorithm. The key of the
>>>>>> table is 32-bit IPv4 address.
>>>>>> 
>>>>>> Signed-off-by: Ru Jia 
>>>

Re: [lng-odp] How about adding an algorithm APIs to ODP

[HePeng]

Hi, Maxim

Thanks for your reply.
> 在 2015年8月25日，下午7:43，Maxim Uvarov  写道：
> 
> On 08/25/15 14:40, Bill Fischofer wrote:
>> ODP is an open source and open contribution project, so anyone is free to 
>> contribute code.  The only requirement is to sign a contributor's agreement 
>> (standard with open source projects) so we know you have the right to submit 
>> the code to the project. The way to do this is to post a proposed patch or 
>> RFC to this mailing list and also to bring the topic up for discussion, as 
>> you've done here. We also have a weekly public call on Tuesdays at 15:00 
>> UTC.  We use the BlueJeans conferencing system.  Just go to 
>> meetings.opendataplane.org <http://meetings.opendataplane.org> to join.  
>> It's a great way to participate in ODP design discussions.
>> 
>> Some general hash functions are being added as part of the Egress Traffic 
>> Manager implementation for linux-generic, however at present these are for 
>> internal use.  It might be possible to extend them, along with your 
>> ideas/code into a general set of APIs for this area.
>> 
>> So thanks for the suggestion and welcome.
>> 
>> On Tue, Aug 25, 2015 at 6:28 AM, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> 
>>Hi,
>>I am new to the ODP project, so I am not sure that should
>>I send this email to the mailing list or to somewhere else.
>> 
>>The thing is that I did some investigation on the code
>>itself, and find that there are not any algorithm APIs in ODP. By
>>algorithms,
>>I mean IP lookup, hash lookup, which is quite common in many
>>network applications.
>> 
>>To note, I did notice that, DPDK provides some code base
>>to do this, for example, the hash, and the lpm (longest prefix
>>matching).
>> 
>>My question is that what do you think to add some
>>algorithm APIs to the ODP projects?
>>For example,
>>odp_trie_search(…) or odp_hash_table_insert(…)?
>> 
> 
> Can you please share why is that needed? Do you want functions to maintain 
> flow table?
> 
> Maxim.


I am a DPDK developer. When I am developing DPDK programs, I find a nice 
feature is that 
DPDK provides some useful data structures &  algorithms, such as LPM lookup 
and some hash functions. For example, if your apps are dealing with some VPN or 
routing stuff, 
you may need to use IP lookup (the longest prefix matching). Or if your apps 
want to maintain a 
IP-MAC mapping or as you mentioned, flow tables, you may need to use hash 
tables to store the corresponding 
content (flows, mac addresses, etc). 
DPDK has already provided some implementations for these algorithms, and I 
think this is a very nice feature for developers. 

However currently DPDK is binding with Intel x86 processors, it is painful 
to port a DPDK programs to anther platform. We are in fact now maintaining two 
code bases 
for two platforms: x86 and Tilera. 

While at the first look, the algorithm implementations should be 
platform-indepenent, but in the real world, they 
usually are tightly binding to the specific code base and platform features. 
For example, DPDK’s hash lib uses 
its own byte-order definitions and memory management primitives. Also, some 
algorithm implementations 
use basic data structures such as lists, queues, … due to the lack of a 
commonly used libraries, usually each 
platform has its own set of implementations for these basic data structures 
(for example in Linux kernel, they have list.h impl for lists)
Porting the DPDK’s lib to another platform usually forces the developers to 
re-implement all required 
data structures, byte-order, memory management, etc. 


So I am thinking that maybe we need a platform independent APIs of all these 
algorithms & data structures. 
I am glad to see ODP has provided a subset of required features, such as 
byte-order and memory management, but it is 
still not enough for many algorithm implementations. 








> 
>>Any feedback is appreciated. Thanks.
>> 
>>___
>>lng-odp mailing list
>>lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
>>https://lists.linaro.org/mailman/listinfo/lng-odp
>> 
>> 
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org
>> https://lists.linaro.org/mailman/listinfo/lng-odp
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] How about adding an algorithm APIs to ODP

[HePeng]

> 在 2015年8月25日，下午11:01，Maxim Uvarov  写道：
> 
> On 08/25/15 17:06, Mike Holmes wrote:
>> HI HePeng,
>> 
>> You can help us greatly even if you can't contribute the code for what you 
>> need.
>> 
>> Can you provide a short list in priority order of the specific requirement 
>> or APIs you would need? Maybe take DPDK as inspiration and modify the API to 
>> be independent as you observe above. That discussion driven by yourself who 
>> needs them might help get them in place much sooner.
>> 
> 
> Yes, that will be very helpful. We can check with vendors which of that api 
> can be hardware optimized (you never know what smart hardware can do). With 
> software only algorithms we should be very careful, from one point it good if 
> we have api to fast porting dpdk apps on odp. From other point having libc 
> and C++/boost inside odp will duplicate efforts. If possible please provide a 
> list what is needed and we will try to solve that. Might be it's good for odp 
> helpers.
> 
> Thanks,
> Maxim.
Hi, Maxim,

Yes, I totally agree that there are already a lot of algorithm implementations 
in other libs. The reason that DPDK has 
re-implemented some of them is that they are not specified for the dataplane 
processing. Boost/C++ implements the 
hash-tables using associated arrays, but I do not see any dataplane programs 
using associated arrays to maintain flows. 
OVS uses its own hash table implementations, and DPDK has its own also. 

I also agree that implementing another algorithm lib may duplicate efforts. So 
at the first step, I think maybe contain some 
hash tables and LPM functions are just fine. All in all, my original intention 
is just to ease the porting from DPDK to ODP. 

So my list begins as follows :
1. famous hash functions, such as jhash, crc, etc.
2. hash table implementations, such as cuckoo hash table, etc.
3. LPM implementations, such as Tree Bitmap algorithms or 16-8-8 algorithms. 

Thanks, 
Peng He.

> 
> 
>> As Bill mentioned please join the public call on Tuesdays (later today) if 
>> you can to get the ideas moving faster.
>> 
>> Mike
>> 
>> On 25 August 2015 at 09:18, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> 
>>Hi, Maxim
>> 
>>Thanks for your reply.
>>> 在 2015年8月25日，下午7:43，Maxim Uvarov > <mailto:maxim.uva...@linaro.org>> 写道：
>>>
>>> On 08/25/15 14:40, Bill Fischofer wrote:
>>>> ODP is an open source and open contribution project, so anyone
>>is free to contribute code.  The only requirement is to sign a
>>contributor's agreement (standard with open source projects) so we
>>know you have the right to submit the code to the project. The way
>>to do this is to post a proposed patch or RFC to this mailing list
>>and also to bring the topic up for discussion, as you've done
>>here. We also have a weekly public call on Tuesdays at 15:00 UTC. We 
>> use the BlueJeans conferencing system. Just go to
>>meetings.opendataplane.org <http://meetings.opendataplane.org>
>><http://meetings.opendataplane.org> to join.  It's a great way to
>>participate in ODP design discussions.
>>>>
>>>> Some general hash functions are being added as part of the
>>Egress Traffic Manager implementation for linux-generic, however
>>at present these are for internal use.  It might be possible to
>>extend them, along with your ideas/code into a general set of APIs
>>for this area.
>>>>
>>>> So thanks for the suggestion and welcome.
>>>>
>>>> On Tue, Aug 25, 2015 at 6:28 AM, HePeng ><mailto:xnhp0...@icloud.com> <mailto:xnhp0...@icloud.com
>><mailto:xnhp0...@icloud.com>>> wrote:
>>>>
>>>>Hi,
>>>>I am new to the ODP project, so I am not sure that
>>should
>>>>I send this email to the mailing list or to somewhere else.
>>>>
>>>>The thing is that I did some investigation on the code
>>>>itself, and find that there are not any algorithm APIs in
>>ODP. By
>>>>algorithms,
>>>>I mean IP lookup, hash lookup, which is quite common in many
>>>>network applications.
>>>>
>>>>To note, I did notice that, DPDK provides some code base
>>>>to do this, for example, the hash, and the lpm (longest prefix
>>>>matching).
>>>>
>>>>

Re: [lng-odp] How about adding an algorithm APIs to ODP

[HePeng]

> 在 2015年8月25日，下午7:40，Bill Fischofer  写道：
> 
> ODP is an open source and open contribution project, so anyone is free to 
> contribute code.  The only requirement is to sign a contributor's agreement 
> (standard with open source projects) so we know you have the right to submit 
> the code to the project. The way to do this is to post a proposed patch or 
> RFC to this mailing list and also to bring the topic up for discussion, as 
> you've done here. We also have a weekly public call on Tuesdays at 15:00 UTC. 
>  We use the BlueJeans conferencing system.  Just go to 
> meetings.opendataplane.org <http://meetings.opendataplane.org/> to join.  
> It's a great way to participate in ODP design discussions.
> 
> Some general hash functions are being added as part of the Egress Traffic 
> Manager implementation for linux-generic, however at present these are for 
> internal use.  It might be possible to extend them, along with your 
> ideas/code into a general set of APIs for this area.


Hi, Bill, 
Can you please tell me where I can get these being added hash functions?
I did some code investigation and I did not find any hash implementations 
in 
the whole ODP project. 

Thanks,
Peng He


> 
> So thanks for the suggestion and welcome.
> 
> On Tue, Aug 25, 2015 at 6:28 AM, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
> Hi,
> I am new to the ODP project, so I am not sure that should I send this 
> email to the mailing list or to somewhere else.
> 
> The thing is that I did some investigation on the code itself, and 
> find that there are not any algorithm APIs in ODP. By algorithms,
> I mean IP lookup, hash lookup, which is quite common in many network 
> applications.
> 
> To note, I did notice that, DPDK provides some code base to do this, 
> for example, the hash, and the lpm (longest prefix matching).
> 
> My question is that what do you think to add some algorithm APIs to 
> the ODP projects?
> For example,
> odp_trie_search(…) or odp_hash_table_insert(…)?
> 
> Any feedback is appreciated. Thanks.
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
> 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] How about adding an algorithm APIs to ODP

[HePeng]

> 在 2015年8月26日，下午1:14，Maxim Uvarov  写道：
> 
> On 08/26/15 05:06, HePeng wrote:
>> 
>>> 在 2015年8月25日，下午11:01，Maxim Uvarov >> <mailto:maxim.uva...@linaro.org>> 写道：
>>> 
>>> On 08/25/15 17:06, Mike Holmes wrote:
>>>> HI HePeng,
>>>> 
>>>> You can help us greatly even if you can't contribute the code for what you 
>>>> need.
>>>> 
>>>> Can you provide a short list in priority order of the specific requirement 
>>>> or APIs you would need? Maybe take DPDK as inspiration and modify the API 
>>>> to be independent as you observe above. That discussion driven by yourself 
>>>> who needs them might help get them in place much sooner.
>>>> 
>>> 
>>> Yes, that will be very helpful. We can check with vendors which of that api 
>>> can be hardware optimized (you never know what smart hardware can do). With 
>>> software only algorithms we should be very careful, from one point it good 
>>> if we have api to fast porting dpdk apps on odp. From other point having 
>>> libc and C++/boost inside odp will duplicate efforts. If possible please 
>>> provide a list what is needed and we will try to solve that. Might be it's 
>>> good for odp helpers.
>>> 
>>> Thanks,
>>> Maxim.
>> Hi, Maxim,
>> 
>> Yes, I totally agree that there are already a lot of algorithm 
>> implementations in other libs. The reason that DPDK has
>> re-implemented some of them is that they are not specified for the dataplane 
>> processing. Boost/C++ implements the
>> hash-tables using associated arrays, but I do not see any dataplane programs 
>> using associated arrays to maintain flows.
>> OVS uses its own hash table implementations, and DPDK has its own also.
>> 
>> I also agree that implementing another algorithm lib may duplicate efforts. 
>> So at the first step, I think maybe contain some
>> hash tables and LPM functions are just fine. All in all, my original 
>> intention is just to ease the porting from DPDK to ODP.
>> 
>> So my list begins as follows :
>> 1. famous hash functions, such as jhash, crc, etc.
>> 2. hash table implementations, such as cuckoo hash table, etc.
>> 3. LPM implementations, such as Tree Bitmap algorithms or 16-8-8 algorithms.
>> 
>> Thanks,
>> Peng He.
> That would be interesting to have such functions in ODP. We have spinlocks 
> implementation, odph_ipv4_csum_valid() and etc.
> Please be very careful with taking code from other projects. ODP has BSD 
> license so you can not take any GPL code for example.
> 
> Maxim.
> 

Hi, Maxim, 

My plan is to port some code directly from DPDK. DPDK is also BSD licensed. 

I notice that DPDK has its own crc implementation and it is optimized to run on 
x86 platform using SSE instructions. 
I am now considering to port a pure software implementation of crc and also 
jhash to ODP’s helper dir.

The csum.h in helpers/ dir will be modified also. 

Thanks.
> 
>> 
>>> 
>>> 
>>>> As Bill mentioned please join the public call on Tuesdays (later today) if 
>>>> you can to get the ideas moving faster.
>>>> 
>>>> Mike
>>>> 
>>>> On 25 August 2015 at 09:18, HePeng >>> <mailto:xnhp0...@icloud.com> <mailto:xnhp0...@icloud.com>> wrote:
>>>> 
>>>>   Hi, Maxim
>>>> 
>>>>   Thanks for your reply.
>>>>   > 在 2015年8月25日，下午7:43，Maxim Uvarov >>> <mailto:maxim.uva...@linaro.org> <mailto:maxim.uva...@linaro.org>> 写道：
>>>>   >
>>>>   > On 08/25/15 14:40, Bill Fischofer wrote:
>>>>   >> ODP is an open source and open contribution project, so anyone
>>>>   is free to contribute code.  The only requirement is to sign a
>>>>   contributor's agreement (standard with open source projects) so we
>>>>   know you have the right to submit the code to the project. The way
>>>>   to do this is to post a proposed patch or RFC to this mailing list
>>>>   and also to bring the topic up for discussion, as you've done
>>>>   here. We also have a weekly public call on Tuesdays at 15:00 UTC. We 
>>>> use the BlueJeans conferencing system. Just go to
>>>> meetings.opendataplane.org <http://meetings.opendataplane.org> 
>>>> <http://meetings.opendataplane.org>
>>>>   <http://meetings.opendataplane.org> to join.  It's a great way to
>>>>   participate in ODP design disc

Re: [lng-odp] How about adding an algorithm APIs to ODP

[HePeng]

Bill, Thanks, 

will look at it.

> 在 2015年8月26日，下午7:46，Bill Fischofer  写道：
> 
> HePeng,
> 
> As Mike mentioned, the TM Implementation is currently being staged in its own 
> repository for ease of development. The patches for that implementation 
> should be appearing on the ODP mailing list shortly.  Barry provided an 
> overview of this implementation, which includes a discussion of the internal 
> hashing functions, a few weeks ago during one of the ODP public calls.  You 
> can see the slides for that overview here: 
> https://docs.google.com/presentation/d/1bJJwgYiDTvE-OdjGq2ceDJYUQVVMkNgKUtHrCVYBv_A/edit#slide=id.p4
>  
> <https://docs.google.com/presentation/d/1bJJwgYiDTvE-OdjGq2ceDJYUQVVMkNgKUtHrCVYBv_A/edit#slide=id.p4>
> 
> On Wed, Aug 26, 2015 at 5:43 AM, Mike Holmes  <mailto:mike.hol...@linaro.org>> wrote:
> Just as a note that as part of the traffic manager API that is being merged 
> there is some AES hash functionality being added to the linux-generic 
> implementation if not the ODP-API
> 
> https://github.com/mike-holmes-linaro/odp/blob/api-next-traffic-mngr/platform/linux-generic/odp_name_table.c
>  
> <https://github.com/mike-holmes-linaro/odp/blob/api-next-traffic-mngr/platform/linux-generic/odp_name_table.c>
> 
> Mike
> 
> On 26 August 2015 at 05:17, Benoît Ganne  <mailto:benoit.ga...@kalray.eu>> wrote:
> Hi all,
> 
> I also agree that implementing another algorithm lib may duplicate
> efforts. So at the first step, I think maybe contain some
> hash tables and LPM functions are just fine. All in all, my original
> intention is just to ease the porting from DPDK to ODP.
> 
> So my list begins as follows :
> 1. famous hash functions, such as jhash, crc, etc.
> 2. hash table implementations, such as cuckoo hash table, etc.
> 3. LPM implementations, such as Tree Bitmap algorithms or 16-8-8
> algorithms.
> 
> I those would be very useful.
> Regarding CRC, shouldn't it be part of the crypto API or a similar API? At 
> least on our HW we have asynchronous accelerators for CRC that you can invoke 
> directly from the cores. They can be used synchronously obviously, bu using 
> an API similar to crypto (or crypto itself FWIW) would allow to do work in 
> parallel.
> Regarding jhash etc. I don't think there is any HW acceleration on any 
> platform do it could be in odph.
> Regarding LPM, I have a 16-8-8 trie ready that I planned to relase soon to 
> ODP as part of a l3fwd app example. Tree bitmaps or similar would be better 
> but LPM algorithms is a patent minefield (and AFAICT tree bitmaps are 
> patented).
> 
> ben
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
> 
> 
> 
> -- 
> Mike Holmes
> Technical Manager - Linaro Networking Group
> Linaro.org <http://www.linaro.org/> │ Open source software for ARM SoCs
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [PATCH 1/5] Add Jhash and CRC functions

[HePeng]

> 在 2015年10月7日，下午9:05，Ola Liljedahl  写道：
> 
> We did some talking about this on some ODP architecture call but I don't 
> remember the outcome.
> 
> ODP started out as a networking HW abstraction and does include some CPU 
> abstractions (e.g. atomics). So e.g. CRC support definitively fits into this 
> scheme and could be added to the public API. A function that specifically 
> provides jhash does not fit in IMO as I don't think any HW implements jhash. 
> A generic hash function (with jhash as the default SW-implementation) can be 
> seen as a HW abstraction. The alternative is to put jhash support as an ODP 
> helper (as the patch does).
> 

So you mean that we should split the whole patch into two parts, one is for 
public APIs, the other is for SW jhash? 




> On 27 September 2015 at 16:24, rujiacs  > wrote:
> Jhash and CRC are two basic hash functions, and are a part of the hash 
> library.
> Migrated from DPDK's hash library, and:
> -- remove its dependence on DPDK library,
> -- remove architecture-specific extensions.
> 
> Signed-off-by: rujiacs mailto:ruji...@163.com>>
> ---
>  helper/include/odp/helper/hash_crc.h   | 426 
> +
>  helper/include/odp/helper/hash_jhash.h | 416 
>  2 files changed, 842 insertions(+)
>  create mode 100644 helper/include/odp/helper/hash_crc.h
>  create mode 100644 helper/include/odp/helper/hash_jhash.h
> 
> diff --git a/helper/include/odp/helper/hash_crc.h 
> b/helper/include/odp/helper/hash_crc.h
> new file mode 100644
> index 000..552a39b
> --- /dev/null
> +++ b/helper/include/odp/helper/hash_crc.h
> @@ -0,0 +1,426 @@
> +/*-
> + *   BSD LICENSE
> + *
> + *   Copyright(c) 2010-2014 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
> +*
> +* ODP Hash CRC
> +*/
> +
> +#ifndef ODPH_HASH_CRC_H_
> +#define ODPH_HASH_CRC_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include 
> +
> +/* Lookup tables for software implementation of CRC32C */
> +static const uint32_t crc32c_tables[8][256] = {{
> +   0x, 0xF26B8303, 0xE13B70F7, 0x1350F3F4, 0xC79A971F, 
> 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
> +   0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B, 0x4D43CFD0, 
> 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
> +   0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B, 0xD7C45070, 
> 0x25AFD373, 0x36FF2087, 0xC494A384,
> +   0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54, 0x5D1D08BF, 
> 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
> +   0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A, 0xE72719C1, 
> 0x154C9AC2, 0x061C6936, 0xF477EA35,
> +   0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5, 0x6DFE410E, 
> 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
> +   0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45, 0xF779DEAE, 
> 0x05125DAD, 0x1642AE59, 0xE4292D5A,
> +   0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A, 0x7DA08661, 
> 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
> +   0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48, 0x86E18AA3, 
> 0x748A09A0, 0x67DAFA54, 0x95B17957,
> +   0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687, 0x0C38D26C, 
> 0xFE53516F, 0xED03A29B, 0x1F682198,
> +   0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927, 0x96BF4DCC, 
> 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
> +   0xDBFC821C, 0x29970

Re: [lng-odp] [PATCH 5/8] add fbk hash table

[HePeng]

So we should change the code into ODP conventions, and resubmit in a v2?


> 在 2015年10月8日，下午4:25，Mike Holmes  写道：
> 
> http://docs.opendataplane.org/master/linux-generic-doxygen-html/api_guide_lines.html
>  
> 
> Api guide states what you say bill, 
> On Oct 8, 2015 4:02 AM, "Bill Fischofer"  > wrote:
> >
> > Trying to keep the rte_ prefix would be confusing.  One of the precepts of 
> > ODP is that it doesn't preclude an application also using an underlying SDK 
> > in addition to ODP APIs.  Whether that makes sense is up to the 
> > application, of course.  But if ODP were to start using other prefixes I'd 
> > imagine that would get very messy.
> 
> http://docs.opendataplane.org/master/linux-generic-doxygen-html/api_guide_lines.html
>  
> 
> We prohibited other prefixes
> 
> >
> > On Wednesday, October 7, 2015, Ola Liljedahl  > > wrote:
> >>
> >> On 23 September 2015 at 19:51, Maxim Uvarov  >> > wrote:
> >>>
> >>>
> >>>
> >>> On 09/20/15 07:04, rujiacs wrote:
> 
>  Signed-off-by: rujiacs mailto:ruji...@163.com>>
>  ---
>    helper/hash_fbk.c| 179 
>    helper/include/odp/helper/hash_fbk.h | 404 
>  +++
>    2 files changed, 583 insertions(+)
>    create mode 100644 helper/hash_fbk.c
>    create mode 100644 helper/include/odp/helper/hash_fbk.h
> 
>  diff --git a/helper/hash_fbk.c b/helper/hash_fbk.c
>  new file mode 100644
>  index 000..eae7596
>  --- /dev/null
>  +++ b/helper/hash_fbk.c
>  @@ -0,0 +1,179 @@
>  +/**
>  + *   BSD LICENSE
>  + *
>  + *   Copyright(c) 2010-2014 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 
>  +#include 
>  +#include 
>  +#include 
>  +#include 
>  +
>  +#include 
>  +#include 
>  +#include "odph_debug.h"
>  +#include 
>  +
>  +static TAILQ_HEAD(, odp_fbk_hash_table) fbk_hash_list;
>  +static odp_rwlock_t fbk_hash_lock;
>  +
>  +void
>  +odp_fbk_hash_list_init()
>  +{
>  +TAILQ_INIT(&fbk_hash_list);
>  +odp_rwlock_init(&fbk_hash_lock);
>  +}
>  +
>  +/**
>  + * Performs a lookup for an existing hash table, and returns a pointer 
>  to
>  + * the table if found.
>  + *
>  + * @param name
>  + *   Name of the hash table to find
>  + *
>  + * @return
>  + *   pointer to hash table structure or NULL on error.
>  + */
>  +struct odp_fbk_hash_table *
>  +odp_fbk_hash_find_existing(const char *name)
>  +{
>  +   struct odp_fbk_hash_table *h = NULL;
>  +
>  +odp_rwlock_read_lock(&fbk_hash_lock);
>  +   TAILQ_FOREACH(h, &fbk_hash_list, next) {
>  +   if (strncmp(name, h->name, ODP_FBK_HASH_NAMESIZE) == 0)
> 

Re: [lng-odp] [PATCH 5/8] add fbk hash table

[HePeng]

There are some discussion about moving the crc into the ODP APIs. 
see the thread [lng-odp] [PATCH 1/5] Add Jhash and CRC functions





> 在 2015年10月8日，下午5:27，Mike Holmes  写道：
> 
> 
> On Oct 8, 2015 5:20 AM, "HePeng"  <mailto:xnhp0...@icloud.com>> wrote:
> >
> > So we should change the code into ODP conventions, and resubmit in a v2?
> >
> 
> Yes.
> 
> I would  check that there are no more api changes suggested by anyone that 
> need discussion first. With that if checkpatch is clean and each patch can be 
> applied without breaking  the build it is good for a v2.
> 
> It will be checked with the check-odp tools which  you can run locally to be 
> sure it is basically  acceptable.
> 
> >
> >> 在 2015年10月8日，下午4:25，Mike Holmes  >> <mailto:mike.hol...@linaro.org>> 写道：
> >>
> >> http://docs.opendataplane.org/master/linux-generic-doxygen-html/api_guide_lines.html
> >>  
> >> <http://docs.opendataplane.org/master/linux-generic-doxygen-html/api_guide_lines.html>
> >>
> >> Api guide states what you say bill, 
> >> On Oct 8, 2015 4:02 AM, "Bill Fischofer"  >> <mailto:bill.fischo...@linaro.org>> wrote:
> >> >
> >> > Trying to keep the rte_ prefix would be confusing.  One of the precepts 
> >> > of ODP is that it doesn't preclude an application also using an 
> >> > underlying SDK in addition to ODP APIs.  Whether that makes sense is up 
> >> > to the application, of course.  But if ODP were to start using other 
> >> > prefixes I'd imagine that would get very messy.
> >>
> >> http://docs.opendataplane.org/master/linux-generic-doxygen-html/api_guide_lines.html
> >>  
> >> <http://docs.opendataplane.org/master/linux-generic-doxygen-html/api_guide_lines.html>
> >>
> >> We prohibited other prefixes
> >>
> >> >
> >> > On Wednesday, October 7, 2015, Ola Liljedahl  >> > <mailto:ola.liljed...@linaro.org>> wrote:
> >> >>
> >> >> On 23 September 2015 at 19:51, Maxim Uvarov  >> >> <mailto:maxim.uva...@linaro.org>> wrote:
> >> >>>
> >> >>>
> >> >>>
> >> >>> On 09/20/15 07:04, rujiacs wrote:
> >> >>>>
> >> >>>> Signed-off-by: rujiacs mailto:ruji...@163.com>>
> >> >>>> ---
> >> >>>>   helper/hash_fbk.c| 179 
> >> >>>>   helper/include/odp/helper/hash_fbk.h | 404 
> >> >>>> +++
> >> >>>>   2 files changed, 583 insertions(+)
> >> >>>>   create mode 100644 helper/hash_fbk.c
> >> >>>>   create mode 100644 helper/include/odp/helper/hash_fbk.h
> >> >>>>
> >> >>>> diff --git a/helper/hash_fbk.c b/helper/hash_fbk.c
> >> >>>> new file mode 100644
> >> >>>> index 000..eae7596
> >> >>>> --- /dev/null
> >> >>>> +++ b/helper/hash_fbk.c
> >> >>>> @@ -0,0 +1,179 @@
> >> >>>> +/**
> >> >>>> + *   BSD LICENSE
> >> >>>> + *
> >> >>>> + *   Copyright(c) 2010-2014 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
> >

Re: [lng-odp] [PATCH 5/8] add fbk hash table

[HePeng]

> 在 2015年10月8日，下午8:13，Ola Liljedahl  写道：
> 
> On 8 October 2015 at 10:02, Bill Fischofer  > wrote:
> Trying to keep the rte_ prefix would be confusing.  One of the precepts of 
> ODP is that it doesn't preclude an application also using an underlying SDK 
> in addition to ODP APIs.  Whether that makes sense is up to the application, 
> of course.  But if ODP were to start using other prefixes I'd imagine that 
> would get very messy.
> It would also be confusing to have functions that use odp_ naming conventions 
> but don't behave like ODP functions (with regards to e.g. handling and 
> returning errors or checking parameters).
We can fix this by wrapping these functions.
 But considering that the internal code is already ready, I am thinking reserve 
the code of *static* functions (internal implementations)?



> 
> So if we rename code imported from e.g. DPDK, we should also convert it to 
> behave like proper ODP functions. That we can base the implementation on 
> preexisting code is just incidental and should not affect how the code 
> behaves.
> 
> 
> On Wednesday, October 7, 2015, Ola Liljedahl  > wrote:
> On 23 September 2015 at 19:51, Maxim Uvarov > 
> wrote:
> 
> 
> On 09/20/15 07:04, rujiacs wrote:
> Signed-off-by: rujiacs >
> ---
>   helper/hash_fbk.c| 179 
>   helper/include/odp/helper/hash_fbk.h | 404 
> +++
>   2 files changed, 583 insertions(+)
>   create mode 100644 helper/hash_fbk.c
>   create mode 100644 helper/include/odp/helper/hash_fbk.h
> 
> diff --git a/helper/hash_fbk.c b/helper/hash_fbk.c
> new file mode 100644
> index 000..eae7596
> --- /dev/null
> +++ b/helper/hash_fbk.c
> @@ -0,0 +1,179 @@
> +/**
> + *   BSD LICENSE
> + *
> + *   Copyright(c) 2010-2014 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 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include "odph_debug.h"
> +#include 
> +
> +static TAILQ_HEAD(, odp_fbk_hash_table) fbk_hash_list;
> +static odp_rwlock_t fbk_hash_lock;
> +
> +void
> +odp_fbk_hash_list_init()
> +{
> +TAILQ_INIT(&fbk_hash_list);
> +odp_rwlock_init(&fbk_hash_lock);
> +}
> +
> +/**
> + * Performs a lookup for an existing hash table, and returns a pointer to
> + * the table if found.
> + *
> + * @param name
> + *   Name of the hash table to find
> + *
> + * @return
> + *   pointer to hash table structure or NULL on error.
> + */
> +struct odp_fbk_hash_table *
> +odp_fbk_hash_find_existing(const char *name)
> +{
> +   struct odp_fbk_hash_table *h = NULL;
> +
> +odp_rwlock_read_lock(&fbk_hash_lock);
> +   TAILQ_FOREACH(h, &fbk_hash_list, next) {
> +   if (strncmp(name, h->name, ODP_FBK_HASH_NAMESIZE) == 0)
> +   break;
> +   }
> +   odp_rwlock_read_unlock(&fbk_hash_lock);
> +   if (h == NULL) {
> +   return NULL;
> +   }
> +   return h;
> simple return h. (if it's NULL, NULL will be returned.)
> 
> 
> 
> +}
> +
> +/**
> + * Create a new hash table for use with four byte keys.
> + *
> + * @param params
> + *   Parameters used in creation of hash table.
> + *
> + * @return
> + *   Pointer to hash table structure that is used in future hash 

Re: [lng-odp] [PATCH 4/5] Add four byte key hash table

[HePeng]

Thank you for the reviewing, will check for it and re-submit the patch in a v2.



> 在 2015年10月8日，下午8:43，Ola Liljedahl  写道：
> 
> On 27 September 2015 at 16:24, rujiacs  > wrote:
> Four byte key(fbk) hash table is a part of hash library, and migrated
> from DPDK. Replacing DPDK's memory management with ODP's shared memory
> management, remove the dependence on DKDP lib.
> 
> Signed-off-by: rujiacs mailto:ruji...@163.com>>
> ---
>  helper/hash_fbk.c| 182 
>  helper/include/odp/helper/hash_fbk.h | 394 
> +++
>  2 files changed, 576 insertions(+)
>  create mode 100644 helper/hash_fbk.c
>  create mode 100644 helper/include/odp/helper/hash_fbk.h
> 
> diff --git a/helper/hash_fbk.c b/helper/hash_fbk.c
> new file mode 100644
> index 000..6e1cb5d
> --- /dev/null
> +++ b/helper/hash_fbk.c
> @@ -0,0 +1,182 @@
> +/**
> + *   BSD LICENSE
> + *
> + *   Copyright(c) 2010-2014 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 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include "odph_debug.h"
> +#include 
> +#include 
> +
> +static TAILQ_HEAD(, odph_fbk_hash_table) fbk_hash_list;
> +static odp_rwlock_t fbk_hash_lock;
> +
> +void
> +odph_fbk_hash_list_init()
> +{
> +   TAILQ_INIT(&fbk_hash_list);
> +   odp_rwlock_init(&fbk_hash_lock);
> +}
> +
> +/**
> + * Performs a lookup for an existing hash table, and returns a pointer to
> + * the table if found.
> + *
> + * @param name
> + *   Name of the hash table to find
> + *
> + * @return
> + *   pointer to hash table structure or NULL on error.
> + */
> +struct odph_fbk_hash_table *
> +odph_fbk_hash_find_existing(const char *name)
> Isn't there an ODP naming convention for calls that look up some existing 
> resource by name? E.g. look up shared memory segment by name. Please follow 
> this convention.
> 
>  
> +{
> +   struct odph_fbk_hash_table *h = NULL;
> +
> +   odp_rwlock_read_lock(&fbk_hash_lock);
> +   TAILQ_FOREACH(h, &fbk_hash_list, next) {
> +   if (strncmp(name, h->name, ODPH_FBK_HASH_NAMESIZE) == 0)
> +   break;
> +   }
> +   odp_rwlock_read_unlock(&fbk_hash_lock);
> +   return h;
> +}
> +
> +/**
> + * Create a new hash table for use with four byte keys.
> + *
> + * @param params
> + *   Parameters used in creation of hash table.
> + *
> + * @return
> + *   Pointer to hash table structure that is used in future hash table
> + *   operations, or NULL on error.
> + */
> +struct odph_fbk_hash_table *
> +odph_fbk_hash_create(const struct odph_fbk_hash_params *params)
> +{
> +   struct odph_fbk_hash_table *ht = NULL;
> +   odp_shm_t shm;
> +   char hash_name[ODPH_FBK_HASH_NAMESIZE];
> +   const uint32_t mem_size =
> +   sizeof(*ht) + (sizeof(ht->t[0]) * params->entries);
> +   uint32_t i;
> +
> +   /* Error checking of parameters. */
> +   if (
> +   (!odph_is_power_of_2(params->entries)) ||
> +   (!odph_is_power_of_2(params->entries_per_bucket)) ||
> +   (params->entries == 0) ||
> +   (params->entries_per_bucket == 0) ||
> +   (params->entries_per_bucket > params->en

Re: [lng-odp] [PATCH 2/5] Modify the Ring structure

[HePeng]

Ping.

> 在 2015年9月27日，下午10:24，rujiacs  写道：
> 
> Add interfaces odph_ring_sp_enqueue() and odph_ring_sc_dequeue() to satify 
> the requirement of the cuckoo hash table.
> Add odph_ring_free() to free the shared memory allocated to a ring.
> 
> Signed-off-by: rujiacs 
> ---
> helper/include/odp/helper/ring.h | 43 
> helper/ring.c| 28 ++
> 2 files changed, 71 insertions(+)
> 
> diff --git a/helper/include/odp/helper/ring.h 
> b/helper/include/odp/helper/ring.h
> index 65c32ad..3c1a3bf 100644
> --- a/helper/include/odp/helper/ring.h
> +++ b/helper/include/odp/helper/ring.h
> @@ -132,6 +132,8 @@ typedef struct odph_ring {
>   /** @private Flags supplied at creation. */
>   int flags;
> 
> + odp_shm_t shm;
> +
>   /** @private Producer */
>   struct prod {
>   uint32_t watermark;  /* Maximum items */
> @@ -194,6 +196,18 @@ typedef struct odph_ring {
> odph_ring_t *odph_ring_create(const char *name, unsigned count,
>   unsigned flags);
> 
> +/**
> + * Free a ring in memory.
> + *
> + * This function uses odp_shm_reserve() to allocate memory. Its size is
> + * set to *count*, which must be a power of two. Water marking is
> + * disabled by default. Note that the real usable ring size is count-1
> + * instead of count.
> + *
> + * @param r
> + *   The pointer to the ring need to be free.
> + */
> +void odph_ring_free(odph_ring_t *r);
> 
> /**
>  * Change the high water mark.
> @@ -372,6 +386,21 @@ int odph_ring_sp_enqueue_bulk(odph_ring_t *r, void * 
> const *obj_table,
> unsigned n);
> 
> /**
> + * Enqueue one object on a ring (NOT multi-producers safe).
> + *
> + * @param r
> + *   A pointer to the ring structure.
> + * @param obj
> + *   A pointer to the object to be added.
> + * @return
> + *   - 0: Success; objects enqueued.
> + *   - -EDQUOT: Quota exceeded. The objects have been enqueued, but the
> + * high water mark is exceeded.
> + *   - -ENOBUFS: Not enough room in the ring to enqueue; no object is 
> enqueued.
> + */
> +int odph_ring_sp_enqueue(odph_ring_t *r, void *obj);
> +
> +/**
>  * Dequeue several objects from a ring (multi-consumers safe).
>  *
>  * This function uses a "compare and set" instruction to move the
> @@ -408,6 +437,20 @@ int odph_ring_mc_dequeue_bulk(odph_ring_t *r, void 
> **obj_table, unsigned n);
> int odph_ring_sc_dequeue_bulk(odph_ring_t *r, void **obj_table, unsigned n);
> 
> /**
> + * Dequeue one object from a ring (NOT multi-consumers safe).
> + *
> + * @param r
> + *   A pointer to the ring structure.
> + * @param obj_p
> + *   A pointer to a void * pointer (object) that will be filled.
> + * @return
> + *   - 0: Success; objects dequeued.
> + *   - -ENOENT: Not enough entries in the ring to dequeue, no object is
> + * dequeued.
> + */
> +int odph_ring_sc_dequeue(odph_ring_t *r, void *obj);
> +
> +/**
>  * Test if a ring is full.
>  *
>  * @param r
> diff --git a/helper/ring.c b/helper/ring.c
> index 3122173..afd7244 100644
> --- a/helper/ring.c
> +++ b/helper/ring.c
> @@ -174,12 +174,18 @@ odph_ring_create(const char *name, unsigned count, 
> unsigned flags)
>   /* reserve a memory zone for this ring.*/
>   shm = odp_shm_reserve(ring_name, ring_size, ODP_CACHE_LINE_SIZE, 0);
> 
> + if (shm == ODP_SHM_INVALID) {
> + ODPH_ERR("shm allocation failed for ring %s\n", ring_name);
> + return NULL;
> + }
> +
>   r = odp_shm_addr(shm);
> 
>   if (r != NULL) {
>   /* init the ring structure */
>   snprintf(r->name, sizeof(r->name), "%s", name);
>   r->flags = flags;
> + r->shm = shm;
>   r->prod.watermark = count;
>   r->prod.sp_enqueue = !!(flags & ODPH_RING_F_SP_ENQ);
>   r->cons.sc_dequeue = !!(flags & ODPH_RING_F_SC_DEQ);
> @@ -201,6 +207,18 @@ odph_ring_create(const char *name, unsigned count, 
> unsigned flags)
>   return r;
> }
> 
> +/* free a ring */
> +void
> +odph_ring_free(odph_ring_t *r)
> +{
> + odp_rwlock_write_lock(&qlock);
> + TAILQ_REMOVE(&odp_ring_list, r, next);
> + odp_rwlock_write_unlock(&qlock);
> +
> + if (r->shm != ODP_SHM_INVALID)
> + odp_shm_free(r->shm);
> +}
> +
> /*
>  * change the high water mark. If *count* is 0, water marking is
>  * disabled
> @@ -471,6 +489,11 @@ int odph_ring_sp_enqueue_bulk(odph_ring_t *r, void * 
> const *obj_table,
>ODPH_RING_QUEUE_FIXED);
> }
> 
> +int odph_ring_sp_enqueue(odph_ring_t *r, void *obj)
> +{
> + return odph_ring_sp_enqueue_bulk(r, &obj, 1);
> +}
> +
> /**
>  * Dequeue several objects from a ring (multi-consumers safe).
>  */
> @@ -489,6 +512,11 @@ int odph_ring_sc_dequeue_bulk(odph_ring_t *r, void 
> **obj_table, unsigned n)
>ODPH_RING_QUEUE_FIXED);
> }
> 
> +int odph_ring_sc_dequeue(odph_ring_t 

Re: [lng-odp] [PATCH 1/5] Add Jhash and CRC functions

[HePeng]

We should first added a generic hash API to api-next, and then provide crc and 
jhash implementations?

I am not clear about how hash functions can be added into ODP. Should we first 
present a proposal ?

In fact, jhash, cuckoo hash and fbk hash tables are part of the patches we are 
preparing for the algorithmic APIs I proposed before. 

See the thread in the maillist

https://lists.linaro.org/pipermail/lng-odp/2015-August/014665.html



> 在 2015年10月8日，下午3:44，Savolainen, Petri (Nokia - FI/Espoo) 
>  写道：
> 
>  
>  
> From: lng-odp [mailto:lng-odp-boun...@lists.linaro.org 
> <mailto:lng-odp-boun...@lists.linaro.org>] On Behalf Of EXT Ola Liljedahl
> Sent: Wednesday, October 07, 2015 6:12 PM
> To: HePeng
> Cc: 杨馥榕; LNG ODP Mailman List
> Subject: Re: [lng-odp] [PATCH 1/5] Add Jhash and CRC functions
>  
> On 7 October 2015 at 16:36, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
>  
> 在 2015年10月7日，下午9:05，Ola Liljedahl  <mailto:ola.liljed...@linaro.org>> 写道：
>  
> We did some talking about this on some ODP architecture call but I don't 
> remember the outcome.
>  
> ODP started out as a networking HW abstraction and does include some CPU 
> abstractions (e.g. atomics). So e.g. CRC support definitively fits into this 
> scheme and could be added to the public API. A function that specifically 
> provides jhash does not fit in IMO as I don't think any HW implements jhash. 
> A generic hash function (with jhash as the default SW-implementation) can be 
> seen as a HW abstraction. The alternative is to put jhash support as an ODP 
> helper (as the patch does).
>  
>  
> So you mean that we should split the whole patch into two parts, one is for 
> public APIs, the other is for SW jhash? 
> This is my suggestion but I want to hear Petri's view on this.
>  
> I think it makes sense to add  CRC as a proper ODP API. It could be first 
> just a synchronous function call (crypto API style - async completion event 
> option could follow if needed). There could be couple of functions: one for 
> user defined polynomial, and another ones for mostly used polynomials. For 
> example:
>  
> odp/include/hash.h
>  
> // Calculate CRC using the given polynomial
> uint32_t odp_hash_crc(const void *data, uint32_t data_len, uint32_t init_val, 
> uint32_t polynomial) 
>  
> // Calculate CRC32
> uint32_t odp_hash_crc32(const void *data, uint32_t data_len, uint32_t 
> init_val);
>  
> // Calculate CRC32C
> uint32_t odp_hash_crc32c(const void *data, uint32_t data_len, uint32_t 
> init_val);
>  
> -Petri
>  
>  
>  

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [PATCH 5/8] add fbk hash table

[HePeng]

> 在 2015年10月9日，下午4:26，Ola Liljedahl  写道：
> 
> On 8 October 2015 at 14:43, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
> 
>> 在 2015年10月8日，下午8:13，Ola Liljedahl > <mailto:ola.liljed...@linaro.org>> 写道：
>> 
>> On 8 October 2015 at 10:02, Bill Fischofer > <mailto:bill.fischo...@linaro.org>> wrote:
>> Trying to keep the rte_ prefix would be confusing.  One of the precepts of 
>> ODP is that it doesn't preclude an application also using an underlying SDK 
>> in addition to ODP APIs.  Whether that makes sense is up to the application, 
>> of course.  But if ODP were to start using other prefixes I'd imagine that 
>> would get very messy.
>> It would also be confusing to have functions that use odp_ naming 
>> conventions but don't behave like ODP functions (with regards to e.g. 
>> handling and returning errors or checking parameters).
> 
> We can fix this by wrapping these functions.
> I don't follow you. How can you make these function behave like ODP functions 
> by "wrapping" them?
> Me thinks you have to modify the implementation in order to change the 
> behaviour.

I mean that perhaps not all the functions needs to be changed, only the exposed 
ones (APIs). Some functions are static and are only used in  
the internal of implementation, these functions can reserve their code. 

> 
>  But considering that the internal code is already ready, I am thinking 
> reserve the code of *static* functions (internal implementations)?
> 
> 
> 
>> 
>> So if we rename code imported from e.g. DPDK, we should also convert it to 
>> behave like proper ODP functions. That we can base the implementation on 
>> preexisting code is just incidental and should not affect how the code 
>> behaves.
>> 
>> 
>> On Wednesday, October 7, 2015, Ola Liljedahl > <mailto:ola.liljed...@linaro.org>> wrote:
>> On 23 September 2015 at 19:51, Maxim Uvarov > 
>> wrote:
>> 
>> 
>> On 09/20/15 07:04, rujiacs wrote:
>> Signed-off-by: rujiacs >
>> ---
>>   helper/hash_fbk.c| 179 
>>   helper/include/odp/helper/hash_fbk.h | 404 
>> +++
>>   2 files changed, 583 insertions(+)
>>   create mode 100644 helper/hash_fbk.c
>>   create mode 100644 helper/include/odp/helper/hash_fbk.h
>> 
>> diff --git a/helper/hash_fbk.c b/helper/hash_fbk.c
>> new file mode 100644
>> index 000..eae7596
>> --- /dev/null
>> +++ b/helper/hash_fbk.c
>> @@ -0,0 +1,179 @@
>> +/**
>> + *   BSD LICENSE
>> + *
>> + *   Copyright(c) 2010-2014 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 
>> +#include 
>> +#include 
>> +#include 
>> +#include 
>> +
>> +#include 
>> +#include 
>> +#include "odph_debug

Re: [lng-odp] [PATCH 5/8] add fbk hash table

[HePeng]

> 在 2015年10月9日，下午4:36，Ola Liljedahl  写道：
> 
> On 9 October 2015 at 10:33, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
> 
>> 在 2015年10月9日，下午4:26，Ola Liljedahl > <mailto:ola.liljed...@linaro.org>> 写道：
>> 
>> On 8 October 2015 at 14:43, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> 
>>> 在 2015年10月8日，下午8:13，Ola Liljedahl >> <mailto:ola.liljed...@linaro.org>> 写道：
>>> 
>>> On 8 October 2015 at 10:02, Bill Fischofer >> <mailto:bill.fischo...@linaro.org>> wrote:
>>> Trying to keep the rte_ prefix would be confusing.  One of the precepts of 
>>> ODP is that it doesn't preclude an application also using an underlying SDK 
>>> in addition to ODP APIs.  Whether that makes sense is up to the 
>>> application, of course.  But if ODP were to start using other prefixes I'd 
>>> imagine that would get very messy.
>>> It would also be confusing to have functions that use odp_ naming 
>>> conventions but don't behave like ODP functions (with regards to e.g. 
>>> handling and returning errors or checking parameters).
>> 
>> We can fix this by wrapping these functions.
>> I don't follow you. How can you make these function behave like ODP 
>> functions by "wrapping" them?
>> Me thinks you have to modify the implementation in order to change the 
>> behaviour.
> 
> I mean that perhaps not all the functions needs to be changed, only the 
> exposed ones (APIs). Some functions are static and are only used in  
> the internal of implementation, these functions can reserve their code. 
> Static functions can have whatever names you like. But if their 
> implementation contributes to the behaviour as seen by callers of the public 
> functions, that behaviour must be compliant with the ODP style.

I see. Thanks. 


>  
> 
>> 
>>  But considering that the internal code is already ready, I am thinking 
>> reserve the code of *static* functions (internal implementations)?
>> 
>> 
>> 
>>> 
>>> So if we rename code imported from e.g. DPDK, we should also convert it to 
>>> behave like proper ODP functions. That we can base the implementation on 
>>> preexisting code is just incidental and should not affect how the code 
>>> behaves.
>>> 
>>> 
>>> On Wednesday, October 7, 2015, Ola Liljedahl >> <mailto:ola.liljed...@linaro.org>> wrote:
>>> On 23 September 2015 at 19:51, Maxim Uvarov > 
>>> wrote:
>>> 
>>> 
>>> On 09/20/15 07:04, rujiacs wrote:
>>> Signed-off-by: rujiacs >
>>> ---
>>>   helper/hash_fbk.c| 179 
>>>   helper/include/odp/helper/hash_fbk.h | 404 
>>> +++
>>>   2 files changed, 583 insertions(+)
>>>   create mode 100644 helper/hash_fbk.c
>>>   create mode 100644 helper/include/odp/helper/hash_fbk.h
>>> 
>>> diff --git a/helper/hash_fbk.c b/helper/hash_fbk.c
>>> new file mode 100644
>>> index 000..eae7596
>>> --- /dev/null
>>> +++ b/helper/hash_fbk.c
>>> @@ -0,0 +1,179 @@
>>> +/**
>>> + *   BSD LICENSE
>>> + *
>>> + *   Copyright(c) 2010-2014 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

Re: [lng-odp] [PATCH v2] Add CRC as an odp api, and a SW implementation in linux-generic. Add copyright license.

[HePeng]

> 在 2015年10月14日，下午7:46，Savolainen, Petri (Nokia - FI/Espoo) 
>  写道：
> 
> As Maxim mentioned any patches that modify api files should target the 
> api-next branch and should be named like this
> 
> [API-NEXT PATCH v3] api: hash: Added crc32 and crc32c hash functions
> 
> 

will do it  in v3. 

> 
> 
> 
> My proposal for the content of include/odp/api/hash.h is this:


I think your proposal is better. will follow it in v3 patch. 
> 
> 
> /**
> * Calculate CRC-32
> *
> * Calculates CRC-32 over the data. The polynomial is 0x04c11db7.
> *
> * @param data   Pointer to data
> * @param data_len   Data length in bytes
> * @param init_val   CRC generator initialization value
> *
> * @return CRC32 value
> */
> uint32_t odp_hash_crc32(const void *data, uint32_t data_len, uint32_t 
> init_val);
> 
> /**
> * Calculate CRC-32C
> *
> * Calculates CRC-32C (a.k.a. CRC-32 Castagnoli) over the data. The polynomial 
> * is 0x1edc6f41.
> *
> * @param data   Pointer to data
> * @param data_len   Data length in bytes
> * @param init_val   CRC generator initialization value
> *
> * @return CRC32C value
> */
> uint32_t odp_hash_crc32c(const void *data, uint32_t data_len, uint32_t 
> init_val);
> 
> /**
> * CRC parameters
> *
> * Supports CRCs up to 64 bits
> */
> typedef struct odp_hash_crc_param_t {
>   /** CRC width in bits */
>   uint32_t width;
> 
>   /** Polynomial (stored in 'width' LSB bits) */
>   uint64_t poly;
> 
>   /** 0: don't reflect, 1: reflect bits in input bytes */
>   odp_bool_t reflect_in;
> 
>   /** 0: don't reflect, 1: reflect bits in output bytes */
>   odp_bool_t reflect_out;
> 
>   /** XOR this value to CRC output (stored in 'width' LSB bits) */
>   uint64_t xor_out;
> } odp_hash_crc_param_t;
> 
> /**
> * Calculate up to 64 bit CRC using the given parameters
> *
> * Calculates CRC over the data using the given parameters.
> *
> * @param data   Pointer to data
> * @param data_len   Data length in bytes
> * @param init_val   CRC generator initialization value
> * @param crc_param  CRC parameters
> * @param crcPointer for CRC output
> *
> * @return 0 on success, <0 on failure (e.g. not supported algorithm)
> */
> int odp_hash_crc_gen64(const void *data, uint32_t data_len, uint64_t 
> init_val, odp_hash_crc_param_t *param, uint64_t *crc); 
> 
> 
> This last one (generic) can be left out for now and added if multiple 
> different CRCs are needed.
> 
> See additional comments under.
> 
> 
>> -Original Message-
>> From: lng-odp [mailto:lng-odp-boun...@lists.linaro.org 
>> ] On Behalf Of EXT
>> Peng
>> Sent: Tuesday, October 13, 2015 3:57 PM
>> To: lng-odp@lists.linaro.org 
>> Cc: Peng
>> Subject: [lng-odp] [PATCH v2] Add CRC as an odp api, and a SW
>> implementation in linux-generic. Add copyright license.
>> 
>> From: Peng 
>> 
>> Signed-off-by: Peng 
>> ---
>> include/odp.h |   1 +
>> include/odp/api/hash.h|  73 +
>> platform/linux-generic/Makefile.am|   3 +
>> platform/linux-generic/include/odp/hash.h |  34 +++
>> platform/linux-generic/odp_hash.c | 486
>> ++
>> 5 files changed, 597 insertions(+)
>> create mode 100644 include/odp/api/hash.h
>> create mode 100644 platform/linux-generic/include/odp/hash.h
>> create mode 100644 platform/linux-generic/odp_hash.c
>> 
>> diff --git a/include/odp.h b/include/odp.h
>> index 825c7e1..da57da8 100644
>> --- a/include/odp.h
>> +++ b/include/odp.h
>> @@ -24,6 +24,7 @@ extern "C" {
>> #include 
>> #include 
>> #include 
>> +#include 
>> #include 
>> #include 
>> #include 
>> diff --git a/include/odp/api/hash.h b/include/odp/api/hash.h
>> new file mode 100644
>> index 000..bdfa024
>> --- /dev/null
>> +++ b/include/odp/api/hash.h
>> @@ -0,0 +1,73 @@
>> +/* Copyright (c) 2013, Linaro Limited
> 
> 2015
> 
>> + * All rights reserved.
>> + *
>> + * SPDX-License-Identifier: BSD-3-Clause
>> + */
>> +
>> +/**
>> + * @file
>> + *
>> + * ODP Hash functions
>> + */
>> +
>> +#ifndef ODP_API_HASH_H_
>> +#define ODP_API_HASH_H_
>> +
>> +#ifdef __cplusplus
>> +extern "C" {
>> +#endif
>> +
>> +#include 
>> +
>> +/** @defgroup odp_hash ODP HASH FUNCTIONS
>> + *  ODP Hash functions
>> + *  @{
>> + */
>> +
>> +/**
>> + * CRC32 Hash function
>> + *
>> + * @param data
>> + *   Data to perform hash on.
>> + * @param data_len
>> + *   How many bytes to use to calculate hash value.
>> + * @param init_val
>> + *   Value to initialise hash generator.
>> + * @return
>> + *   32bit calculated hash value.
>> + */
>> +uint32_t odp_crc(const void *data, size_t data_len, uint32_t init_val);
> 
> Data length should be uint32_t. Replace this one with these two:
> 
> uint32_t odp_hash_crc32(const void *data, uint32_t data_len, uint32_t 
> init_val);
> uint32_t odp_hash_crc32c(const void *data, uint32_t data_len, uint32_t 
> init_val);
> 
> ... or with odp_hash_crc32c() if

Re: [lng-odp] [API-NEXT PATCH] api: clib: added standard c library api

[HePeng]

> 在 2015年10月16日，下午8:16，Bill Fischofer  写道：
> 
> Why would you not expect a platform to provide an optimized implementation of 
> these stdlib functions itself?  GCC, in particular, seems to do a good job of 
> this for most platforms.

Hi Bill, 
DPDK has its own impl for memcpy (rte_memcpy). 


> 
> On Fri, Oct 16, 2015 at 7:13 AM, Petri Savolainen  > wrote:
> Some C library calls are often used in data plane code. This
> API enables possibility to HW optimized implementation of those.
> Added first memcpy and memset.
> 
> Signed-off-by: Petri Savolainen  >
> ---
>  include/odp.h |  1 +
>  include/odp/api/std_clib.h| 64 
> +++
>  platform/linux-generic/Makefile.am|  2 +
>  platform/linux-generic/include/odp/std_clib.h | 30 +
>  4 files changed, 97 insertions(+)
>  create mode 100644 include/odp/api/std_clib.h
>  create mode 100644 platform/linux-generic/include/odp/std_clib.h
> 
> diff --git a/include/odp.h b/include/odp.h
> index 825c7e1..f2cd2d3 100644
> --- a/include/odp.h
> +++ b/include/odp.h
> @@ -56,6 +56,7 @@ extern "C" {
>  #include 
>  #include 
>  #include 
> +#include 
> 
>  #ifdef __cplusplus
>  }
> diff --git a/include/odp/api/std_clib.h b/include/odp/api/std_clib.h
> new file mode 100644
> index 000..2119ec4
> --- /dev/null
> +++ b/include/odp/api/std_clib.h
> @@ -0,0 +1,64 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/**
> + * @file
> + *
> + * ODP version of often used C library calls
> + */
> +
> +#ifndef ODP_API_STD_CLIB_H_
> +#define ODP_API_STD_CLIB_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +/**
> + * @defgroup odp_std_clib ODP STD CLIB
> + * @details
> + * ODP version of often used C library calls
> + * @{
> + */
> +
> +/**
> + * Memcpy
> + *
> + * ODP version of C library memcpy function. It copies 'num' bytes from 
> source
> + * to destination address. Source and destination memory blocks must not
> + * overlap.
> + *
> + * @param dstPointer to destination memory block
> + * @param srcPointer to source memory block
> + * @param numNumber of bytes to copy
> + *
> + * @return 'dst' address
> + */
> +void *odp_memcpy(void *dst, const void *src, size_t num);
> +
> +/**
> + * Memset
> + *
> + * ODP version of C library memset function. It sets 'value' to first 'num'
> + * bytes of memory block pointed by 'ptr'.
> + *
> + * @param ptrPointer to the memory block
> + * @param value  Value to be set
> + * @param numNumber of bytes to set
> + *
> + * @return 'ptr' address
> + */
> +void *odp_memset(void *ptr, int value, size_t num);
> +
> +/**
> + * @}
> + */
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif
> diff --git a/platform/linux-generic/Makefile.am 
> b/platform/linux-generic/Makefile.am
> index 85c976d..fc202cc 100644
> --- a/platform/linux-generic/Makefile.am
> +++ b/platform/linux-generic/Makefile.am
> @@ -41,6 +41,7 @@ odpinclude_HEADERS = \
>   $(srcdir)/include/odp/shared_memory.h \
>   $(srcdir)/include/odp/spinlock.h \
>   $(srcdir)/include/odp/spinlock_recursive.h \
> + $(srcdir)/include/odp/std_clib.h \
>   $(srcdir)/include/odp/std_types.h \
>   $(srcdir)/include/odp/sync.h \
>   $(srcdir)/include/odp/system_info.h \
> @@ -108,6 +109,7 @@ odpapiinclude_HEADERS = \
>   $(top_srcdir)/include/odp/api/shared_memory.h \
>   $(top_srcdir)/include/odp/api/spinlock.h \
>   $(top_srcdir)/include/odp/api/spinlock_recursive.h \
> + $(top_srcdir)/include/odp/api/std_clib.h \
>   $(top_srcdir)/include/odp/api/std_types.h \
>   $(top_srcdir)/include/odp/api/sync.h \
>   $(top_srcdir)/include/odp/api/system_info.h \
> diff --git a/platform/linux-generic/include/odp/std_clib.h 
> b/platform/linux-generic/include/odp/std_clib.h
> new file mode 100644
> index 000..c939c48
> --- /dev/null
> +++ b/platform/linux-generic/include/odp/std_clib.h
> @@ -0,0 +1,30 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +#ifndef ODP_PLAT_STD_CLIB_H_
> +#define ODP_PLAT_STD_CLIB_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include 
> +
> +static inline void *odp_memcpy(void *dst, const void *src, size_t num)
> +{
> +   return memcpy(dst, src, num);
> +}
> +
> +static inline void *odp_memset(void *ptr, int value, size_t num)
> +{
> +   return memset(ptr, value, num);
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif
> --
> 2.6.0
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org 

Re: [lng-odp] [PATCH] [API-NEXT PATCH v5] api: hash: Added crc32 and crc32c hash functions

[HePeng]

Hi, Maxim

> 在 2015年10月23日，下午11:40，Maxim Uvarov  写道：
> 
> Somehow that email inside previous version thread it's hard to follow it.

I am having troubles in using git send-email to reply to specific emails, even 
I’ve 
tried using —reply-to message-id, the email is sent as a new thread. 

We will soon revise the current version and present a new one.

Thanks. 

> 
> I have few notes:
> 
> 1. version should be remove from long log  and put under "---" in email.
> 
> 2. doxygen:
> /opt/Linaro/odp2.git/include/odp/api/hash.h:73: warning: argument 'crc_param' 
> of command @param is not found in the argument list of 
> odp_hash_crc_gen64(const void *data, uint32_t data_len, uint64_t init_val, 
> odp_hash_crc_param_t *param, uint64_t *crc)
> /opt/Linaro/odp2.git/include/odp/api/hash.h:73: warning: The following 
> parameters of odp_hash_crc_gen64(const void *data, uint32_t data_len, 
> uint64_t init_val, odp_hash_crc_param_t *param, uint64_t *crc) are not 
> documented:
>  parameter 'param'
> 
> 3. It will be good to include test coverage tests cases for make check.
> 
> Thanks,
> Maxim.
> 
> 
> On 10/23/2015 16:09, Savolainen, Petri (Nokia - FI/Espoo) wrote:
>> Ping. Why this has not been merged yet.
>> 
>> 
>>> -Original Message-
>>> From: Savolainen, Petri (Nokia - FI/Espoo)
>>> Sent: Thursday, October 15, 2015 11:08 AM
>>> To: 'EXT Peng'; lng-odp@lists.linaro.org
>>> Cc: Peng
>>> Subject: RE: [PATCH] [API-NEXT PATCH v5] api: hash: Added crc32 and crc32c
>>> hash functions
>>> 
>>> 
>>> Reviewed-by: Petri Savolainen 
>>> 
>>> 
 -Original Message-
 From: EXT Peng [mailto:xnhp0...@icloud.com]
 Sent: Thursday, October 15, 2015 10:51 AM
 To: lng-odp@lists.linaro.org
 Cc: Savolainen, Petri (Nokia - FI/Espoo); Peng
 Subject: [PATCH] [API-NEXT PATCH v5] api: hash: Added crc32 and crc32c
>>> hash
 functions
 
 From: Peng 
 
 v2: Add copyright license.
 v3: APIs: crc32c, crc32 and generic CRC hash impl
 linux-generic: add impl for crc32c.
 v4: linux-generic:
 change odp_crc32c_1word to crc32c_u32,
 change odp_crc32c_2words to crc32c_u64,
 drop inline decorator for odp_hash_crc32c.
 change copyrights to 2015.
 v5: linux-generic:
 add copyrights to 2015 for linux-generic headers
 
 Signed-off-by: Peng 
 ---
  include/odp.h |   1 +
  include/odp/api/hash.h|  98 ++
  platform/linux-generic/Makefile.am|   3 +
  platform/linux-generic/include/odp/hash.h |  34 +++
  platform/linux-generic/odp_hash.c | 487
 ++
  5 files changed, 623 insertions(+)
  create mode 100644 include/odp/api/hash.h
  create mode 100644 platform/linux-generic/include/odp/hash.h
  create mode 100644 platform/linux-generic/odp_hash.c
 
 diff --git a/include/odp.h b/include/odp.h
 index 825c7e1..da57da8 100644
 --- a/include/odp.h
 +++ b/include/odp.h
 @@ -24,6 +24,7 @@ extern "C" {
  #include 
  #include 
  #include 
 +#include 
  #include 
  #include 
  #include 
 diff --git a/include/odp/api/hash.h b/include/odp/api/hash.h
 new file mode 100644
 index 000..59466c1
 --- /dev/null
 +++ b/include/odp/api/hash.h
 @@ -0,0 +1,98 @@
 +/* Copyright (c) 2015, Linaro Limited
 + * All rights reserved.
 + *
 + * SPDX-License-Identifier:   BSD-3-Clause
 + */
 +
 +/**
 + * @file
 + *
 + * ODP Hash functions
 + */
 +
 +#ifndef ODP_API_HASH_H_
 +#define ODP_API_HASH_H_
 +
 +#ifdef __cplusplus
 +extern "C" {
 +#endif
 +
 +#include 
 +
 +/** @defgroup odp_hash ODP HASH FUNCTIONS
 + *  ODP Hash functions
 + *  @{
 + */
 +
 +/**
 +* Calculate CRC-32
 +*
 +* Calculates CRC-32 over the data. The polynomial is 0x04c11db7.
 +*
 +* @param data   Pointer to data
 +* @param data_len   Data length in bytes
 +* @param init_val   CRC generator initialization value
 +*
 +* @return CRC32 value
 +*/
 +uint32_t odp_hash_crc32(const void *data, uint32_t data_len, uint32_t
 init_val);
 +
 +/**
 +* Calculate CRC-32C
 +*
 +* Calculates CRC-32C (a.k.a. CRC-32 Castagnoli) over the data.
 +* The polynomial is 0x1edc6f41.
 +*
 +* @param data   Pointer to data
 +* @param data_len   Data length in bytes
 +* @param init_val   CRC generator initialization value
 +*
 +* @return CRC32C value
 +*/
 +uint32_t odp_hash_crc32c(const void *data, uint32_t data_len,
 +   uint32_t init_val);
 +
 +/**
 +* CRC parameters
 +*
 +* Supports CRCs up to 64 bits
 +*/
 +typedef struct odp_hash_crc_param_t {
 +  /** CRC width in bits */
 +  uint32_t width;
 +  /** Polynomial (stored in 'width' LS

[lng-odp] Is there an errno api in ODP?

[HePeng]

Hi, 
I am preparing some patches for ODP. I need to set errno value for some 
functions, 
is there an API? all errno related APIs are just to read errno. 

Thanks.
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

[lng-odp] Is there an errno api in ODP?

[HePeng]

Hi, 
I am preparing some patches for ODP. I need to set errno value for some 
functions, 
is there an API? all errno related APIs are just to read errno. 

Thanks.
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] Is there an errno api in ODP?

[HePeng]

Hi, Maxim,
The problem is that I want to add a patch that is located in the 
helper/ dir. There are 
no platform layout in helper/. 



> 在 2015年11月25日，下午5:02，Maxim Uvarov  写道：
> 
> On 11/25/2015 11:53, HePeng wrote:
>> Hi,
>>  I am preparing some patches for ODP. I need to set errno value for some 
>> functions,
>> is there an API? all errno related APIs are just to read errno.
>> 
>>  Thanks.
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org
>> https://lists.linaro.org/mailman/listinfo/lng-odp
> 
> Yes, take a look how linux-generic deals with it:
> 
> #include 
> __odp_errno = EEXIST
> 
> Maxim.
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Please ignore this patch, it contains a silly mistake on hash.h 
which modifies its comments causing a typo.

sorry.

> 在 2015年11月26日，上午10:20，Peng  写道：
> 
> Signed-off-by: Peng 
> ---
> helper/Makefile.am  |2 +
> helper/cuckoo_hash.c| 1117 +++
> helper/include/odp/helper/cuckoo_hash.h |  435 
> helper/include/odp/helper/ring.h|   43 ++
> helper/ring.c   |   28 +
> helper/test/Makefile.am |4 +-
> helper/test/odp_cuckoo_hash.c   |  779 +
> include/odp/api/hash.h  |   16 +-
> 8 files changed, 2422 insertions(+), 2 deletions(-)
> create mode 100644 helper/cuckoo_hash.c
> create mode 100644 helper/include/odp/helper/cuckoo_hash.h
> create mode 100644 helper/test/odp_cuckoo_hash.c
> 
> diff --git a/helper/Makefile.am b/helper/Makefile.am
> index e72507e..e923aa8 100644
> --- a/helper/Makefile.am
> +++ b/helper/Makefile.am
> @@ -18,6 +18,7 @@ helperinclude_HEADERS = \
> $(srcdir)/include/odp/helper/ipsec.h\
> $(srcdir)/include/odp/helper/tcp.h\
> $(srcdir)/include/odp/helper/table.h\
> +   $(srcdir)/include/odp/helper/cuckoo_hash.h\
> $(srcdir)/include/odp/helper/udp.h
> 
> noinst_HEADERS = \
> @@ -30,6 +31,7 @@ noinst_HEADERS = \
> __LIB__libodphelper_la_SOURCES = \
>   linux.c \
>   ring.c \
> + cuckoo_hash.c \
>   hashtable.c \
>   lineartable.c
> 
> diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c
> new file mode 100644
> index 000..4a4b56b
> --- /dev/null
> +++ b/helper/cuckoo_hash.c
> @@ -0,0 +1,1117 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/*-
> + *   BSD LICENSE
> + *
> + *   Copyright(c) 2010-2015 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 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include "odph_debug.h"
> +
> +/* Macro to enable/disable run-time checking of function parameters */
> +#define RETURN_IF_TRUE(cond, retval) do { \
> + if (cond) \
> + return retval; \
> +} while (0)
> +
> +/* Hash function used if none is specified */
> +#include 
> +
> +/** Number of items per bucket. */
> +#define HASH_BUCKET_ENTRIES  4
> +#define NULL_SIGNATURE   0
> +#define KEY_ALIGNMENT16
> +
> +/** Maximum size of hash table that can be created. */
> +#define HASH_ENTRIES_MAX1048576
> +
> +/** Maximum number of keys that can be
> + *  searched for using odph_hash_lookup_bulk. */
> +#define HASH_LOOKUP_BULK_MAX 64
> +#define HASH_LOOKUP_MULTI_MAXHASH_LOOKUP_BULK_MAX
> +
> +/* Structure storing both primary and secondary hashes */
> +struct cuckoo_hash_signatures {
> + union {
> + struct {
> + uint32_t current;
> + uint32_t alt;
> + };
> +

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Cuckoo Hash Table is an efficient hash table variant which has a very high 
utilization (load/total entries > 90%).
In our tests, the utilization is around 94%.

Here is a brief introduction on cuckoo hash:
https://en.wikipedia.org/wiki/Cuckoo_hashing 


This implementation is a port from DPDK. I convert it into ODP conventions, 
based on ODP facilities. I think it will be nice for ODP developer to use this 
data structure for many dataplane functions. 

Thanks. 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Cuckoo Hash Table is an efficient hash table variant which has a very high 
utilization (load/total entries > 90%).
In our tests, the utilization is around 94%.

Here is a brief introduction on cuckoo hash:
https://en.wikipedia.org/wiki/Cuckoo_hashing 


This implementation is a port from DPDK. I convert it into ODP conventions, 
based on ODP facilities. I think it will be nice for ODP developer to use this 
data structure for many dataplane functions. 

Thanks. 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

> 在 2015年11月30日，下午11:04，Maxim Uvarov  写道：
> 
> On 11/30/2015 11:18, HePeng wrote:
>> Hi, Maxim,
>> How is everything going, about the ring?
> 
> 
> Hello Peng,
> 
> We need to take a look it it's possible to rewrite your hash implementation 
> to odp queues api instead of odp ring.
> That will allow to use hw queues accelerators for hash.
> 
> Maxim.

Hi Maxim,

The ring structure in cuckoo hash is just a buffer storing the “key” 
address. 

The hash table stores all the keys. In this implementation,  it is the 
hash table itself which maintains the memory of all the keys. 
When add a new key, the hash table will firstly allocate an“index” of the key 
using the ring, and when delete a key, the 
hash table will recycle the “index” of the key into the ring. All in all, this 
ring is like a free slots buffer storing all the free indexes. 

In my opinion, (while I did not do this in hardware), the ring is not a 
critical data structure in the scenario of hash table matching, 
because only when table update happens,  the hash table will need to use the 
ring. Unless you use the hash table in a write-heavy 
scenario, and this hardware queue can help you to ease the lock contention in 
multi-core. 

So my opinion is that, 1) yes, we can use the queue to replace the 
ring, as long as the queue can be large enough to hold 
all the hash entries. 2) But I do not think it is a critical optimization. 



___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

> 在 2015年12月2日，下午5:30，Maxim Uvarov  写道：
> 
> On 12/02/2015 10:26, HePeng wrote:
>>> 在 2015年11月30日，下午11:04，Maxim Uvarov  写道：
>>> 
>>> On 11/30/2015 11:18, HePeng wrote:
>>>> Hi, Maxim,
>>>> How is everything going, about the ring?
>>> 
>>> Hello Peng,
>>> 
>>> We need to take a look it it's possible to rewrite your hash implementation 
>>> to odp queues api instead of odp ring.
>>> That will allow to use hw queues accelerators for hash.
>>> 
>>> Maxim.
>> Hi Maxim,
>>  
>>  The ring structure in cuckoo hash is just a buffer storing the “key” 
>> address.
>> 
>>  The hash table stores all the keys. In this implementation,  it is the 
>> hash table itself which maintains the memory of all the keys.
>> When add a new key, the hash table will firstly allocate an“index” of the 
>> key using the ring, and when delete a key, the
>> hash table will recycle the “index” of the key into the ring. All in all, 
>> this ring is like a free slots buffer storing all the free indexes.
>> 
>>  In my opinion, (while I did not do this in hardware), the ring is not a 
>> critical data structure in the scenario of hash table matching,
>> because only when table update happens,  the hash table will need to use the 
>> ring. Unless you use the hash table in a write-heavy
>> scenario, and this hardware queue can help you to ease the lock contention 
>> in multi-core.
>> 
>>  So my opinion is that, 1) yes, we can use the queue to replace the 
>> ring, as long as the queue can be large enough to hold
>> all the hash entries. 2) But I do not think it is a critical optimization.
> On the latest Tuesday call we have long discussion about that.  And the final 
> agreement was that cuckoo has is needed but it needs to
> use native odp interface. I.e. use of odp_queue instead of helper odph_ring. 
> The other deal is how that odp_queue is implemented.
> If needed we can extend current implementation of odp_queue or add some 
> parameter to api. I.e. if needed we can put ring code
> inside implementation and make external interface as odp_queue.  In that case 
> platform which can work with queues in hardware
> can accelerate it as other poll queues, other platform will have it in 
> software. You might seen that interface of the ring and
> queue is about the same, i.e. it puts and gets patches to object. So it might 
> be not so hard to rewrite code to current queues api,
> but in that form odp community will be happy to accept that patch. If there 
> will be some performance degradation, than we can work
> on queues implementation and fix it.
> 
> So plan is:
> 1) have this code with queues api;
> 2) remove ring code completely from helper
> 3) move ring code inside linux-generic (I will reuse it for shm pktio ipc);
> 4) test performance of cuckoo hash
> 5) move it to odp hash API when it will be ready (to do that code should not 
> use other helper code, just native odp apis).
Glad to see this. I will begin to shape the code using odp_queue API. 



> 
> Best regards,
> Maxim.

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Hi Maxim, 
I implement a new version of cuckoo hash based on the ODP buffer/pool. 

As I’ve mentioned earlier, the use of ring in cuckoo hash is like to 
the use of 
a container, e.g. a queue in C++ STL.  In current ODP implementation, I found 
that 
the ODP queue is implemented more likely a facility for transmitting objects, 
not 
a container to store objects. Look at the ODP queue enqueue interface:

int odp_queue_enq(odp_queue_t queue, odp_event_t ev);

the *odp_event_t* is related to the events, but I only want to use odp_queue to 
storing and retrieving objects, any objects. 


So I use ODP buffer/pool interfaces instead of ODP queue 
for the new cuckoo hash implementation. 

However, compared to the previous implementation based on ring, this 
version 
suffers a serious performance degradation. The evaluation is carried out on a 
Intel 
servers. I test lookup time for 1000 lookups on a table storing 1 million 
items. 
The ODP buffer/pool version suffers at least a 2x performance degradation. 

This is the buffer/pool version, for 1M insert, and 1000 lookup time:

Average insert time = 2.383836, lookup time = 0.000353,

This is the ring version. 

Average insert time = 1.629115, lookup time = 0.98

This performance degradation stems from the heavy implementation of
 ODP buffer/pool. In the ring based one, all the key is stored in a big array, 
and 
the ring only stores the array indexes of each key. Keys are retrieved using 
array indexes. 
In the new one, I use ODP buffer to store the key content. Keys are retrieved 
by 
dereferencing a *odp_buffer_t*  handle. 

With this high performance degradation, I suggest moving ring into the 
odp/api 
as a container implementation, and use the previous implementation of cuckoo 
hash. 






___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

> 在 2015年12月8日，下午9:34，Ola Liljedahl  写道：
> 
> On 8 December 2015 at 12:42, Bill Fischofer  <mailto:bill.fischo...@linaro.org>> wrote:
> This is an interesting topic.  I'd like to discuss this a bit during today's 
> ODP public call.  
> 
> I think the issue is that while a ring is a very useful implementation 
> construct its semantics are very SW centric.
> But isn't the use case here SW centric?
>  
> Perhaps there's opportunity here for a new Queue type that would permit an 
> implementation to implement the queue API as a ring for additional 
> performance?
> I think it is a bad idea to overload the ODP queue with another type of usage 
> and implied implementation. Better to define a new ODP object.
> 
> What are the real requirements of the "ring" as used by the cuckoo hash 
> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
> objects (not just ODP events)?

The real requirement is use the ring as a sort of container. 
Fixed Size is OK. And the ring should be used to 
store any ODP events, since it is used as a container, 
like vector in C++ STL. 


> 
>  
>   The scheduler itself could use this since its use of queues is subject to 
> the same issues.
> 
> On Mon, Dec 7, 2015 at 11:39 PM, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
> Hi Maxim,
> I implement a new version of cuckoo hash based on the ODP buffer/pool.
> 
> As I’ve mentioned earlier, the use of ring in cuckoo hash is like to 
> the use of
> a container, e.g. a queue in C++ STL.  In current ODP implementation, I found 
> that
> the ODP queue is implemented more likely a facility for transmitting objects, 
> not
> a container to store objects. Look at the ODP queue enqueue interface:
> 
> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
> 
> the *odp_event_t* is related to the events, but I only want to use odp_queue 
> to
> storing and retrieving objects, any objects.
> 
> 
> So I use ODP buffer/pool interfaces instead of ODP queue
> for the new cuckoo hash implementation.
> 
> However, compared to the previous implementation based on ring, this 
> version
> suffers a serious performance degradation. The evaluation is carried out on a 
> Intel
> servers. I test lookup time for 1000 lookups on a table storing 1 million 
> items.
> The ODP buffer/pool version suffers at least a 2x performance degradation.
> 
> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
> 
> Average insert time = 2.383836, lookup time = 0.000353,
> 
> This is the ring version.
> 
> Average insert time = 1.629115, lookup time = 0.98
> 
> This performance degradation stems from the heavy implementation of
>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
> array, and
> the ring only stores the array indexes of each key. Keys are retrieved using 
> array indexes.
> In the new one, I use ODP buffer to store the key content. Keys are retrieved 
> by
> dereferencing a *odp_buffer_t*  handle.
> 
> With this high performance degradation, I suggest moving ring into 
> the odp/api
> as a container implementation, and use the previous implementation of cuckoo 
> hash.
> 
> 
> 
> 
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
> 
> 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Let me further explain this. 

Cuckoo hash is a hash table, and as a hash table, it needs to store the 
key-value paris.
For any input, e.g. a key ( a byte string with some size), a hash table needs 
to 
calculate the hash value from the key, find the right bucket, and compare 
the input key with the keys stored in the bucket. If the two keys are equal, 
then 
return the value of the key. 

So any hash table needs to manage some memory to store the keys. 
In the previous implementation, the hash table will allocate a big 
array for storing every keys, and the ring is used to store the index of 
all the empty array slot. If you need to insert a new key, the hash table will
firstly dequeue an index from the ring, and then calculate the address 
of the empty slot (base_ptr + index * key_size), and memcpy the key into 
the array slot. 

So this is why I say the ring is used as a container, it is just used as a 
container to 
store key indices. It is quite similar to ODP buffer/pool. And this is the 
reason 
I use ODP buffer/pool to store all the keys in the new implementation.   


> 在 2015年12月9日，下午1:31，HePeng  写道：
> 
>> 
>> 在 2015年12月8日，下午9:34，Ola Liljedahl > <mailto:ola.liljed...@linaro.org>> 写道：
>> 
>> On 8 December 2015 at 12:42, Bill Fischofer > <mailto:bill.fischo...@linaro.org>> wrote:
>> This is an interesting topic.  I'd like to discuss this a bit during today's 
>> ODP public call.  
>> 
>> I think the issue is that while a ring is a very useful implementation 
>> construct its semantics are very SW centric.
>> But isn't the use case here SW centric?
>>  
>> Perhaps there's opportunity here for a new Queue type that would permit an 
>> implementation to implement the queue API as a ring for additional 
>> performance?
>> I think it is a bad idea to overload the ODP queue with another type of 
>> usage and implied implementation. Better to define a new ODP object.
>> 
>> What are the real requirements of the "ring" as used by the cuckoo hash 
>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>> objects (not just ODP events)?
> 
> The real requirement is use the ring as a sort of container. 
> Fixed Size is OK. And the ring should be used to 
> store any ODP events, since it is used as a container, 
> like vector in C++ STL. 
> 
> 
>> 
>>  
>>   The scheduler itself could use this since its use of queues is subject to 
>> the same issues.
>> 
>> On Mon, Dec 7, 2015 at 11:39 PM, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> Hi Maxim,
>> I implement a new version of cuckoo hash based on the ODP 
>> buffer/pool.
>> 
>> As I’ve mentioned earlier, the use of ring in cuckoo hash is like to 
>> the use of
>> a container, e.g. a queue in C++ STL.  In current ODP implementation, I 
>> found that
>> the ODP queue is implemented more likely a facility for transmitting 
>> objects, not
>> a container to store objects. Look at the ODP queue enqueue interface:
>> 
>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>> 
>> the *odp_event_t* is related to the events, but I only want to use odp_queue 
>> to
>> storing and retrieving objects, any objects.
>> 
>> 
>> So I use ODP buffer/pool interfaces instead of ODP queue
>> for the new cuckoo hash implementation.
>> 
>> However, compared to the previous implementation based on ring, this 
>> version
>> suffers a serious performance degradation. The evaluation is carried out on 
>> a Intel
>> servers. I test lookup time for 1000 lookups on a table storing 1 million 
>> items.
>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>> 
>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>> 
>> Average insert time = 2.383836, lookup time = 0.000353,
>> 
>> This is the ring version.
>> 
>> Average insert time = 1.629115, lookup time = 0.98
>> 
>> This performance degradation stems from the heavy implementation of
>>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
>> array, and
>> the ring only stores the array indexes of each key. Keys are retrieved using 
>> array indexes.
>> In the new one, I use ODP buffer to store the key content. Keys are 
>> retrieved by
>> dereferencing a *odp_buffer_t*  handle.
>> 
>> With this high performance degradation, I suggest moving ring into 
>> the odp/api
>> as a container implementation, and use the previous implemen

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

> 在 2015年12月9日，下午6:20，Maxim Uvarov  写道：
> 
> On 12/09/2015 08:54, HePeng wrote:
>> Let me further explain this.
>> 
>> Cuckoo hash is a hash table, and as a hash table, it needs to store the 
>> key-value paris.
>> For any input, e.g. a key ( a byte string with some size), a hash table 
>> needs to
>> calculate the hash value from the key, find the right bucket, and compare
>> the input key with the keys stored in the bucket. If the two keys are equal, 
>> then
>> return the value of the key.
>> 
>> So any hash table needs to manage some memory to store the keys.
>> In the previous implementation, the hash table will allocate a big
>> array for storing every keys, and the ring is used to store the index of
>> all the empty array slot. If you need to insert a new key, the hash table 
>> will
>> firstly dequeue an index from the ring, and then calculate the address
>> of the empty slot (base_ptr + index * key_size), and memcpy the key into
>> the array slot.
>> 
>> So this is why I say the ring is used as a container, it is just used as a 
>> container to
>> store key indices. It is quite similar to ODP buffer/pool. And this is the 
>> reason
>> I use ODP buffer/pool to store all the keys in the new implementation.
> 
> Thanks that description is clear.
> 
> For now we have pool for buffers and packets. Will but we do not have pool 
> for objects.
> That might be fixed size objects and FIFO and LIFO type of that pool (Petris 
> idea).
> What do you think about it?

I think it is a good idea to have this data structure as a facility in ODP. 
We can use the ring code for the implementation. 


> 
> Maxim.
> 
>> 
>> 
>>> 在 2015年12月9日，下午1:31，HePeng >> <mailto:xnhp0...@icloud.com>> 写道：
>>> 
>>>> 
>>>> 在 2015年12月8日，下午9:34，Ola Liljedahl >>> <mailto:ola.liljed...@linaro.org>> 写道：
>>>> 
>>>> On 8 December 2015 at 12:42, Bill Fischofer>>> <mailto:bill.fischo...@linaro.org>>wrote:
>>>> 
>>>>This is an interesting topic.  I'd like to discuss this a bit
>>>>during today's ODP public call.
>>>> 
>>>>I think the issue is that while a ring is a very useful
>>>>implementation construct its semantics are very SW centric.
>>>> 
>>>> But isn't the use case here SW centric?
>>>> 
>>>>Perhaps there's opportunity here for a new Queue type that would
>>>>permit an implementation to implement the queue API as a ring
>>>>for additional performance?
>>>> 
>>>> I think it is a bad idea to overload the ODP queue with another type of 
>>>> usage and implied implementation. Better to define a new ODP object.
>>>> 
>>>> What are the real requirements of the "ring" as used by the cuckoo hash 
>>>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>>>> objects (not just ODP events)?
>>> 
>>> The real requirement is use the ring as a sort of container.
>>> Fixed Size is OK. And the ring should be used to
>>> store any ODP events, since it is used as a container,
>>> like vector in C++ STL.
>>> 
>>> 
>>>> 
>>>>  The scheduler itself could use this since its use of queues is
>>>>subject to the same issues.
>>>> 
>>>>On Mon, Dec 7, 2015 at 11:39 PM, HePeng>>><mailto:xnhp0...@icloud.com>>wrote:
>>>> 
>>>>Hi Maxim,
>>>>I implement a new version of cuckoo hash based on
>>>>the ODP buffer/pool.
>>>> 
>>>>As I’ve mentioned earlier, the use of ring in cuckoo
>>>>hash is like to the use of
>>>>a container, e.g. a queue in C++ STL.  In current ODP
>>>>implementation, I found that
>>>>the ODP queue is implemented more likely a facility for
>>>>transmitting objects, not
>>>>a container to store objects. Look at the ODP queue enqueue
>>>>interface:
>>>> 
>>>>int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>>>> 
>>>>the *odp_event_t* is related to the events, but I only want
>>>>to use odp_queue to
>>>>storing and retrieving objects, any objects.
>>>> 
>>>> 
>>>>

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

> 在 2015年12月9日，下午6:49，Ola Liljedahl  写道：
> 
> On 9 December 2015 at 06:31, HePeng  <mailto:xnhp0...@icloud.com>> wrote:
> 
>> 在 2015年12月8日，下午9:34，Ola Liljedahl > <mailto:ola.liljed...@linaro.org>> 写道：
>> 
>> On 8 December 2015 at 12:42, Bill Fischofer > <mailto:bill.fischo...@linaro.org>> wrote:
>> This is an interesting topic.  I'd like to discuss this a bit during today's 
>> ODP public call.  
>> 
>> I think the issue is that while a ring is a very useful implementation 
>> construct its semantics are very SW centric.
>> But isn't the use case here SW centric?
>>  
>> Perhaps there's opportunity here for a new Queue type that would permit an 
>> implementation to implement the queue API as a ring for additional 
>> performance?
>> I think it is a bad idea to overload the ODP queue with another type of 
>> usage and implied implementation. Better to define a new ODP object.
>> 
>> What are the real requirements of the "ring" as used by the cuckoo hash 
>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>> objects (not just ODP events)?
> 
> The real requirement is use the ring as a sort of container. 
> Fixed Size is OK. And the ring should be used to 
> store any ODP events, since it is used as a container, 
> like vector in C++ STL. 
> What if I would like to store objects that are not ODP events in the cuckoo 
> hash table? E.g. arbitrary pointers (to memory that is managed in some other 
> way).
> 
    Yes, that is currently ring’s implementation. 


> 
> 
>> 
>>  
>>   The scheduler itself could use this since its use of queues is subject to 
>> the same issues.
>> 
>> On Mon, Dec 7, 2015 at 11:39 PM, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> Hi Maxim,
>> I implement a new version of cuckoo hash based on the ODP 
>> buffer/pool.
>> 
>> As I’ve mentioned earlier, the use of ring in cuckoo hash is like to 
>> the use of
>> a container, e.g. a queue in C++ STL.  In current ODP implementation, I 
>> found that
>> the ODP queue is implemented more likely a facility for transmitting 
>> objects, not
>> a container to store objects. Look at the ODP queue enqueue interface:
>> 
>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>> 
>> the *odp_event_t* is related to the events, but I only want to use odp_queue 
>> to
>> storing and retrieving objects, any objects.
>> 
>> 
>> So I use ODP buffer/pool interfaces instead of ODP queue
>> for the new cuckoo hash implementation.
>> 
>> However, compared to the previous implementation based on ring, this 
>> version
>> suffers a serious performance degradation. The evaluation is carried out on 
>> a Intel
>> servers. I test lookup time for 1000 lookups on a table storing 1 million 
>> items.
>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>> 
>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>> 
>> Average insert time = 2.383836, lookup time = 0.000353,
>> 
>> This is the ring version.
>> 
>> Average insert time = 1.629115, lookup time = 0.98
>> 
>> This performance degradation stems from the heavy implementation of
>>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
>> array, and
>> the ring only stores the array indexes of each key. Keys are retrieved using 
>> array indexes.
>> In the new one, I use ODP buffer to store the key content. Keys are 
>> retrieved by
>> dereferencing a *odp_buffer_t*  handle.
>> 
>> With this high performance degradation, I suggest moving ring into 
>> the odp/api
>> as a container implementation, and use the previous implementation of cuckoo 
>> hash.
>> 
>> 
>> 
>> 
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>> <https://lists.linaro.org/mailman/listinfo/lng-odp>
>> 
>> 
>> ___
>> lng-odp mailing list
>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>> <https://lists.linaro.org/mailman/listinfo/lng-odp>
>> 
>> 
> 
> 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Ping.

So what is your decision on this.
> 在 2015年12月10日，下午1:06，HePeng  写道：
> 
>> 
>> 在 2015年12月9日，下午6:49，Ola Liljedahl > <mailto:ola.liljed...@linaro.org>> 写道：
>> 
>> On 9 December 2015 at 06:31, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> 
>>> 在 2015年12月8日，下午9:34，Ola Liljedahl >> <mailto:ola.liljed...@linaro.org>> 写道：
>>> 
>>> On 8 December 2015 at 12:42, Bill Fischofer >> <mailto:bill.fischo...@linaro.org>> wrote:
>>> This is an interesting topic.  I'd like to discuss this a bit during 
>>> today's ODP public call.  
>>> 
>>> I think the issue is that while a ring is a very useful implementation 
>>> construct its semantics are very SW centric.
>>> But isn't the use case here SW centric?
>>>  
>>> Perhaps there's opportunity here for a new Queue type that would permit an 
>>> implementation to implement the queue API as a ring for additional 
>>> performance?
>>> I think it is a bad idea to overload the ODP queue with another type of 
>>> usage and implied implementation. Better to define a new ODP object.
>>> 
>>> What are the real requirements of the "ring" as used by the cuckoo hash 
>>> design? Enqueue/dequeue operations. Fixed size is OK? Storing arbitrary 
>>> objects (not just ODP events)?
>> 
>> The real requirement is use the ring as a sort of container. 
>> Fixed Size is OK. And the ring should be used to 
>> store any ODP events, since it is used as a container, 
>> like vector in C++ STL. 
>> What if I would like to store objects that are not ODP events in the cuckoo 
>> hash table? E.g. arbitrary pointers (to memory that is managed in some other 
>> way).
>> 
>   Yes, that is currently ring’s implementation. 
> 
> 
>> 
>> 
>>> 
>>>  
>>>   The scheduler itself could use this since its use of queues is subject to 
>>> the same issues.
>>> 
>>> On Mon, Dec 7, 2015 at 11:39 PM, HePeng >> <mailto:xnhp0...@icloud.com>> wrote:
>>> Hi Maxim,
>>> I implement a new version of cuckoo hash based on the ODP 
>>> buffer/pool.
>>> 
>>> As I’ve mentioned earlier, the use of ring in cuckoo hash is like 
>>> to the use of
>>> a container, e.g. a queue in C++ STL.  In current ODP implementation, I 
>>> found that
>>> the ODP queue is implemented more likely a facility for transmitting 
>>> objects, not
>>> a container to store objects. Look at the ODP queue enqueue interface:
>>> 
>>> int odp_queue_enq(odp_queue_t queue, odp_event_t ev);
>>> 
>>> the *odp_event_t* is related to the events, but I only want to use 
>>> odp_queue to
>>> storing and retrieving objects, any objects.
>>> 
>>> 
>>> So I use ODP buffer/pool interfaces instead of ODP queue
>>> for the new cuckoo hash implementation.
>>> 
>>> However, compared to the previous implementation based on ring, 
>>> this version
>>> suffers a serious performance degradation. The evaluation is carried out on 
>>> a Intel
>>> servers. I test lookup time for 1000 lookups on a table storing 1 million 
>>> items.
>>> The ODP buffer/pool version suffers at least a 2x performance degradation.
>>> 
>>> This is the buffer/pool version, for 1M insert, and 1000 lookup time:
>>> 
>>> Average insert time = 2.383836, lookup time = 0.000353,
>>> 
>>> This is the ring version.
>>> 
>>> Average insert time = 1.629115, lookup time = 0.98
>>> 
>>> This performance degradation stems from the heavy implementation of
>>>  ODP buffer/pool. In the ring based one, all the key is stored in a big 
>>> array, and
>>> the ring only stores the array indexes of each key. Keys are retrieved 
>>> using array indexes.
>>> In the new one, I use ODP buffer to store the key content. Keys are 
>>> retrieved by
>>> dereferencing a *odp_buffer_t*  handle.
>>> 
>>> With this high performance degradation, I suggest moving ring into 
>>> the odp/api
>>> as a container implementation, and use the previous implementation of 
>>> cuckoo hash.
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
>>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>>> <https://lists.linaro.org/mailman/listinfo/lng-odp>
>>> 
>>> 
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
>>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>>> <https://lists.linaro.org/mailman/listinfo/lng-odp>
>>> 
>>> 
>> 
>> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
> https://lists.linaro.org/mailman/listinfo/lng-odp 
> <https://lists.linaro.org/mailman/listinfo/lng-odp>
___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

Hi, Maxim

I will present a quick patch that will not pass the kernel style 
check as this one is just for evaluation. 


> 在 2015年12月16日，下午8:22，Maxim Uvarov  写道：
> 
> From meeting we decided that we want solution based on pool. Can you post that
> patches? We will try to help how to improve performance.
> 
> Maxim.
> 
> On 12/14/2015 22:30, Mike Holmes wrote:
>> Added to Tuesday agenda
>> 
>> On 12 December 2015 at 22:18, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> 
>>Ping.
>> 
>>So what is your decision on this.
>> 
>>>在 2015年12月10日，下午1:06，HePeng >><mailto:xnhp0...@icloud.com>> 写道：
>>> 
>>>> 
>>>>在 2015年12月9日，下午6:49，Ola Liljedahl
>>>>mailto:ola.liljed...@linaro.org>> 写道：
>>>> 
>>>>On 9 December 2015 at 06:31, HePeng>>><mailto:xnhp0...@icloud.com>>wrote:
>>>> 
>>>> 
>>>>>在 2015年12月8日，下午9:34，Ola Liljedahl
>>>>>>>>><mailto:ola.liljed...@linaro.org>> 写道：
>>>>> 
>>>>>On 8 December 2015 at 12:42, Bill
>>>>>Fischofer>>>><mailto:bill.fischo...@linaro.org>>wrote:
>>>>> 
>>>>>This is an interesting topic.  I'd like to discuss this
>>>>>a bit during today's ODP public call.
>>>>> 
>>>>>I think the issue is that while a ring is a very useful
>>>>>implementation construct its semantics are very SW centric.
>>>>> 
>>>>>But isn't the use case here SW centric?
>>>>> 
>>>>>Perhaps there's opportunity here for a new Queue type
>>>>>that would permit an implementation to implement the
>>>>>queue API as a ring for additional performance?
>>>>> 
>>>>>I think it is a bad idea to overload the ODP queue with
>>>>>another type of usage and implied implementation. Better to
>>>>>define a new ODP object.
>>>>> 
>>>>>What are the real requirements of the "ring" as used by the
>>>>>cuckoo hash design? Enqueue/dequeue operations. Fixed size
>>>>>is OK? Storing arbitrary objects (not just ODP events)?
>>>> 
>>>>The real requirement is use the ring as a sort of container.
>>>>Fixed Size is OK. And the ring should be used to
>>>>store any ODP events, since it is used as a container,
>>>>like vector in C++ STL.
>>>> 
>>>>What if I would like to store objects that are not ODP events in
>>>>the cuckoo hash table? E.g. arbitrary pointers (to memory that
>>>>is managed in some other way).
>>>> 
>>>Yes, that is currently ring’s implementation.
>>> 
>>> 
>>>> 
>>>> 
>>>>> 
>>>>>  The scheduler itself could use this since its use of
>>>>>queues is subject to the same issues.
>>>>> 
>>>>>On Mon, Dec 7, 2015 at 11:39 PM,
>>>>>HePeng>>>><mailto:xnhp0...@icloud.com>>wrote:
>>>>> 
>>>>>Hi Maxim,
>>>>>I implement a new version of cuckoo hash
>>>>>based on the ODP buffer/pool.
>>>>> 
>>>>>As I’ve mentioned earlier, the use of ring
>>>>>in cuckoo hash is like to the use of
>>>>>a container, e.g. a queue in C++ STL. In current
>>>>>ODP implementation, I found that
>>>>>the ODP queue is implemented more likely a facility
>>>>>for transmitting objects, not
>>>>>a container to store objects. Look at the ODP queue
>>>>>enqueue interface:
>>>>> 
>>>>>int odp_queue_enq(odp_queue_t queue,
>>>>>odp_event_t ev);
>>>>> 
>>>>>the *odp_event_t* is related to the events, but I
>>>>>only want to use odp_queue to
>>>>>   

Re: [lng-odp] [API-NEXT PATCH v2] helper: add cuckoo hash implementation

[HePeng]

> 在 2015年12月17日，下午4:26，Maxim Uvarov  写道：
> 
> On 12/17/2015 08:56, HePeng wrote:
>> Hi, Maxim
>> 
>> I will present a quick patch that will not pass the kernel style
>> check as this one is just for evaluation.
> ok, in that case you can add RFC to patch tag.

Sorry, I misunderstood your decision. Will provide a 
patch passing style check soon. 

Another question is that last time you told me 
about moving cuckoo hash into the ODP/ not 
helper/. Is there any changes? if not, I am going to 
add this in ODP/. 

> 
> Maxim.
>> 
>>> 在 2015年12月16日，下午8:22，Maxim Uvarov  写道：
>>> 
>>> From meeting we decided that we want solution based on pool. Can you post 
>>> that
>>> patches? We will try to help how to improve performance.
>>> 
>>> Maxim.
>>> 
>>> On 12/14/2015 22:30, Mike Holmes wrote:
>>>> Added to Tuesday agenda
>>>> 
>>>> On 12 December 2015 at 22:18, HePeng >>> <mailto:xnhp0...@icloud.com>> wrote:
>>>> 
>>>>Ping.
>>>> 
>>>>So what is your decision on this.
>>>> 
>>>>>在 2015年12月10日，下午1:06，HePeng >>>><mailto:xnhp0...@icloud.com>> 写道：
>>>>> 
>>>>>>在 2015年12月9日，下午6:49，Ola Liljedahl
>>>>>>mailto:ola.liljed...@linaro.org>> 写道：
>>>>>> 
>>>>>>On 9 December 2015 at 06:31, HePeng>>>>><mailto:xnhp0...@icloud.com>>wrote:
>>>>>> 
>>>>>> 
>>>>>>>在 2015年12月8日，下午9:34，Ola Liljedahl
>>>>>>>>>>>>><mailto:ola.liljed...@linaro.org>> 写道：
>>>>>>> 
>>>>>>>On 8 December 2015 at 12:42, Bill
>>>>>>>Fischofer>>>>>><mailto:bill.fischo...@linaro.org>>wrote:
>>>>>>> 
>>>>>>>This is an interesting topic.  I'd like to discuss this
>>>>>>>a bit during today's ODP public call.
>>>>>>> 
>>>>>>>I think the issue is that while a ring is a very useful
>>>>>>>implementation construct its semantics are very SW centric.
>>>>>>> 
>>>>>>>But isn't the use case here SW centric?
>>>>>>> 
>>>>>>>Perhaps there's opportunity here for a new Queue type
>>>>>>>that would permit an implementation to implement the
>>>>>>>queue API as a ring for additional performance?
>>>>>>> 
>>>>>>>I think it is a bad idea to overload the ODP queue with
>>>>>>>another type of usage and implied implementation. Better to
>>>>>>>define a new ODP object.
>>>>>>> 
>>>>>>>What are the real requirements of the "ring" as used by the
>>>>>>>cuckoo hash design? Enqueue/dequeue operations. Fixed size
>>>>>>>is OK? Storing arbitrary objects (not just ODP events)?
>>>>>>The real requirement is use the ring as a sort of container.
>>>>>>Fixed Size is OK. And the ring should be used to
>>>>>>store any ODP events, since it is used as a container,
>>>>>>like vector in C++ STL.
>>>>>> 
>>>>>>What if I would like to store objects that are not ODP events in
>>>>>>the cuckoo hash table? E.g. arbitrary pointers (to memory that
>>>>>>is managed in some other way).
>>>>>> 
>>>>>Yes, that is currently ring’s implementation.
>>>>> 
>>>>> 
>>>>>> 
>>>>>>>  The scheduler itself could use this since its use of
>>>>>>>queues is subject to the same issues.
>>>>>>> 
>>>>>>>On Mon, Dec 7, 2015 at 11:39 PM,
>>>>>>>HePeng>>>>>><mailto:xnhp0...@icloud.com>>wrote:
>>>>>>> 
>>>>>>>Hi Maxim,
>>>>>>>I implement a new version of cuckoo hash
>>>>>>>based on the ODP buffer/pool.
>

[lng-odp] Contribute IP lookup code to ODP

[HePeng]

Hi, 
I plan to submit an IP lookup code to ODP. However, this code is a little 
bit complex. 
So I am here asking for some suggestions. (Please view this email using the 
monospaced font.)

The code is actually an IP lookup architecture, including a “backend” of 
all IP lookup 
algorithms and the “frontend” for each IP lookup algorithm. I made this design 
because 
normally the data structure for IP lookup is usually highly optimized, 
compressed, containing  
minimall information for fast lookup. However, a full functional IP lookup 
engine should support 
many extra functions rather than just lookup (prefix exist, print all prefix, 
…). One way to do this 
is to design a “control plane” (large data structure containing most of query 
information and can help to 
incremental update the lookup tree in “dataplane") to do this. The control 
plane is the backend, 
while the highly optimized data structure is the dataplane, the front end. 


+--+ +-+ +-+
| 1688 | --> | lib | <-- | TBM |
+--+ +-+ +-+


 So the code includes a lib/ for backend, and two algorithms in total (Tree 
Bitmap (TBM) and DIR-16-8-8). 
I am now finishing the lib/ and TBM. I am not sure is that:

 1. Is ODP community willing to accept this? or you guys just want a very 
simple implementation?
 2. Should this code including the IP lookup APIs go to helper/ or main 
thread?


 I’ve tested the code using 350K prefixes from the core router’s FIB. The 
backend uses 11MB memory and 
the front end uses 5MB memory. The TBM algorithms achieves 25MLPS (million 
lookups for second, 16.9Gbps for 64B packets) 
on Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz CPU and a very low locality trace 
dedicated for the FIB. On Random traffic, 
the code achieves 55MLPS. 

 Thanks.



___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] Contribute IP lookup code to ODP

[HePeng]

Hi, Sorin, 
Thanks for your comments! 

I did some code investigation on your DIR 1688 and OFP project. 
I guess currently the IP lookup code in OFP is complete. OFP seems to have 
already the backend and 
front-end together, I have seen the code for DIR1688 and also the code for a 
binary trie. 

The responses list below：
> 在 2016年1月21日，下午10:58，Sorin Vultureanu  写道：
> 
> Hi,
> 
> I think this IP lookup fits better within OpenFastPath Project - OFP.
> www.openfastpath.org
> 
> OFP has DIR 1688 (lockless, multicore with linear scalability, very low 
> overhead) and Radix Tree(read/write locks).
> 
> TBM algorithm and Front-End /Back-End architecture are interesting for OFP 
> project L3 forwarding functionality, but we might need to check some details 
> to see if it fits:
> - multicore, hopefully lockless
I have not yet consider the lock issues, will consider it in the code
> - the front-end should be available in ODP shared memory
Now the back-end and front-end has their own memory management 
sub-system. 
To submit the code, I need to change it to use ODP memory management 
system.
> - an API between Front-End and Back-End, so that we can have it as SPMC 
> on the shared memory.
The back-end is also a trie, it provides:

*Print all the prefixes;

*Test if a prefix exist;

*Detect if a prefix overlaps with an existing prefix, 
and the length of the existing prefix is smaller than a pre-set length;
This is useful for prefix delete in many multi-trie algorithms.

*Traverse all the prefixes;




> - ...
> 
> Can you share more light into these details?
> 
> It would be great if you can contribute/integrate this as patches to OFP.
> 
> Kind Regards,
> Sorin
> 
> 


> 
>> -Original Message-
>> From: HePeng [mailto:xnhp0...@icloud.com]
>> Sent: Thursday, January 21, 2016 4:40 AM
>> To: LNG ODP Mailman List 
>> Subject: [lng-odp] Contribute IP lookup code to ODP
>> 
>> Hi,
>>I plan to submit an IP lookup code to ODP. However, this code is a little 
>> bit
>> complex.
>> So I am here asking for some suggestions. (Please view this email using the
>> monospaced font.)
>> 
>>The code is actually an IP lookup architecture, including a "backend" of 
>> all
>> IP lookup algorithms and the "frontend" for each IP lookup algorithm. I
>> made this design because normally the data structure for IP lookup is usually
>> highly optimized, compressed, containing minimall information for fast
>> lookup. However, a full functional IP lookup engine should support many
>> extra functions rather than just lookup (prefix exist, print all prefix, 
>> ...). One
>> way to do this is to design a "control plane" (large data structure 
>> containing
>> most of query information and can help to incremental update the lookup
>> tree in "dataplane") to do this. The control plane is the backend, while the
>> highly optimized data structure is the dataplane, the front end.
>> 
>> 
>> +--+ +-+ +-+
>> | 1688 | --> | lib | <-- | TBM |
>> +--+ +-+ +-+
>> 
>> 
>> So the code includes a lib/ for backend, and two algorithms in total 
>> (Tree
>> Bitmap (TBM) and DIR-16-8-8).
>> I am now finishing the lib/ and TBM. I am not sure is that:
>> 
>> 1. Is ODP community willing to accept this? or you guys just want a very
>> simple implementation?
>> 2. Should this code including the IP lookup APIs go to helper/ or main
>> thread?
>> 
>> 
>> I've tested the code using 350K prefixes from the core router's FIB. The
>> backend uses 11MB memory and the front end uses 5MB memory. The TBM
>> algorithms achieves 25MLPS (million lookups for second, 16.9Gbps for 64B
>> packets) on Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz CPU and a very low
>> locality trace dedicated for the FIB. On Random traffic, the code achieves
>> 55MLPS.
>> 
>> Thanks.
>> 
>> 
>> 
> 


___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] Contribute IP lookup code to ODP

[HePeng]

Hi, Bill,
Thanks for your commits!

I have another question is that Tree Bitmap is a patent algorithm from 
Cisco. The code is 
developed independently with a lot of optimization skills. 
I am not sure if I can submit it to an open source community. 

Thank you again for reply.  
> 在 2016年1月22日，上午7:32，Bill Fischofer  写道：
> 
> The main criteria for introducing new APIs into ODP is twofold:
> Does this represent an area of general interest for dataplane applications?
> Do these functions lend themselves to HW acceleration?
> For the case of IP lookup the answer to both of these questions is clearly 
> yes, so on that basis they'd be worthwhile to consider.  So I'd encourage you 
> to submit your patches.  They can be submitted as RFCs if they are incomplete 
> and you'd simply like people to be able to review them in more detail to 
> provide feedback.
> 
> In terms of whether these functions would more naturally reside with ODP or 
> with a higher level component like OFP, the acceleration question is key.  
> One of the things ODP is designed to do is to provide application portability 
> across variant approaches to HW acceleration of key APIs.  For example, 
> crypto acceleration is a common feature on many SoCs, however each SoC does 
> this slightly differently.  By having an ODP crypto API these differences can 
> be abstracted into a common portable API that can be efficiently mapped to 
> many different underlying implementations.
> 
> You'd want IP lookup to follow the same model, meaning that the structures 
> that are used to hold and search the tables should not be exposed as part of 
> the API (since that's an aspect of how one might implement these functions) 
> but instead focus on simply defining the functions as the application would 
> see and use them.  The structures themselves would then become the 
> linux-generic SW reference implementation of these APIs, which of course 
> could be done differently on platforms that have access to TCAMs or other HW 
> features useful for accelerating these functions.
> 
> While many ODP applications will want to take advantage of the additional 
> capabilities offered by OFP, IP lookup seems to be a lower-level function 
> that is needed by switching and routing functions that do not require access 
> to a full stack.  If OFP itself has various built-in lookup algorithms needed 
> for its internal use, then it would be interesting to see if they can be 
> folded into lower level ODP APIs that can front-end HW accelerated versions 
> of them on different platforms.   Again, the key distinction is that ODP is 
> the natural place to hold low-level HW abstractions while higher-level 
> components like OFP can abstract higher-level functions of interest to a 
> wider range of applications.
> 
> Bill
> 
> On Thu, Jan 21, 2016 at 8:58 AM, Sorin Vultureanu  <mailto:sorin.vulture...@enea.com>> wrote:
> Hi,
> 
> I think this IP lookup fits better within OpenFastPath Project - OFP.
> www.openfastpath.org <http://www.openfastpath.org/>
> 
> OFP has DIR 1688 (lockless, multicore with linear scalability, very low 
> overhead) and Radix Tree(read/write locks).
> 
> TBM algorithm and Front-End /Back-End architecture are interesting for OFP 
> project L3 forwarding functionality, but we might need to check some details 
> to see if it fits:
> -   multicore, hopefully lockless
> -   the front-end should be available in ODP shared memory
> -   an API between Front-End and Back-End, so that we can have it as SPMC 
> on the shared memory.
> -   ...
> 
> Can you share more light into these details?
> 
> It would be great if you can contribute/integrate this as patches to OFP.
> 
> Kind Regards,
> Sorin
> 
> 
> 
> > -Original Message-
> > From: HePeng [mailto:xnhp0...@icloud.com <mailto:xnhp0...@icloud.com>]
> > Sent: Thursday, January 21, 2016 4:40 AM
> > To: LNG ODP Mailman List  > <mailto:lng-odp@lists.linaro.org>>
> > Subject: [lng-odp] Contribute IP lookup code to ODP
> >
> > Hi,
> > I plan to submit an IP lookup code to ODP. However, this code is a 
> > little bit
> > complex.
> > So I am here asking for some suggestions. (Please view this email using the
> > monospaced font.)
> >
> > The code is actually an IP lookup architecture, including a "backend" 
> > of all
> > IP lookup algorithms and the "frontend" for each IP lookup algorithm. I
> > made this design because normally the data structure for IP lookup is 
> > usually
> > highly optimized, compressed, containing minimall information for fast
&g

Re: [lng-odp] [API-NEXT PATCH 1/3] api: add cuckoo hash api

[HePeng]

Ping


Any comments?
or should we put the code into helper/?
> 在 2016年4月8日，上午9:19，he peng  写道：
> 
> Perhaps a generic hash table APIs (not cuckoo hash) could be put in the main 
> APIs?
> 
> 
>> 在 2016年4月6日，下午10:18，Ru Jia mailto:ji...@ict.ac.cn>> 写道：
>> 
>> Last year, there was a discussion about cuckoo hash. I saw the last reply 
>> (https://lists.linaro.org/pipermail/lng-odp/2015-December/017921.html 
>> ).
>>  
>> You recommended to:
>> “
>> 1) have this code with queues api;
>> 2) remove ring code completely from helper
>> 3) move ring code inside linux-generic (I will reuse it for shm pktio ipc);
>> 4) test performance of cuckoo hash
>> 5) move it to odp hash API when it will be ready (to do that code should 
>> not use other helper code, just native odp apis).
>> ”
>>  
>> Now I find a ring structure in platform/linux-generic/pktio, so I use it to 
>> implement cuckoo hash. Then as the 5th point, I put it into odp apis.
>>  
>> So, where should cuckoo hash be?
>>  
>> And if it’s need to move cuckoo hash into helper, do I need to use odp_queue 
>> to implement it?
>> 发件人: Mike Holmes [mailto:mike.hol...@linaro.org 
>> ] 
>> 发送时间: 2016年4月6日 19:43
>> 收件人: Ru Jia
>> 抄送: lng-odp; hep...@ict.ac.cn 
>> 主题: Re: [lng-odp] [API-NEXT PATCH 1/3] api: add cuckoo hash api
>>  
>> Thank you for the patch
>>  
>> Remember that if there is a new API added we also need good validation test 
>> coverage in test/validation for it to be accepted eventually into master.
>>  
>> The performance test is a really good thing to have but we need a cunit test 
>> case to help platforms ensure that they all operate the same way for a given 
>> release.
>>  
>> Is there a reason this is not a helper rather than an odp API like the other 
>> hashtable support, can this be HW accelerated  ?
>>  
>>  
>> Mike
>>  
>> On 6 April 2016 at 06:02, Ru Jia mailto:ji...@ict.ac.cn>> 
>> wrote:
>>> Added cuckoo hash api, which is an efficient hash table. It could
>>> be used for many algorithms.
>>> 
>>> Signed-off-by: Ru Jia mailto:ji...@ict.ac.cn>>
>>> ---
>>>  include/odp/api/spec/cuckoo_hash.h | 463 
>>> +
>>>  include/odp_api.h  |   1 +
>>>  .../linux-generic/include/odp/api/cuckoo_hash.h|  34 ++
>>>  3 files changed, 498 insertions(+)
>>>  create mode 100644 include/odp/api/spec/cuckoo_hash.h
>>>  create mode 100644 platform/linux-generic/include/odp/api/cuckoo_hash.h
>>> 
>>> diff --git a/include/odp/api/spec/cuckoo_hash.h 
>>> b/include/odp/api/spec/cuckoo_hash.h
>>> new file mode 100644
>>> index 000..ca147ce
>>> --- /dev/null
>>> +++ b/include/odp/api/spec/cuckoo_hash.h
>>> @@ -0,0 +1,463 @@
>>> +/* Copyright (c) 2015, Linaro Limited
>>> + * All rights reserved.
>>> + *
>>> + * SPDX-License-Identifier: BSD-3-Clause
>>> + */
>>> +
>>> +/*-
>>> + *   BSD LICENSE
>>> + *
>>> + *   Copyright(c) 2010-2015 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.
>>> + */
>>> +
>>> +#ifndef ODP_API_CUCKOO_HASH_H_
>>> +#define ODP_API_CUCKOO_HASH_H_
>>> +
>>> +#include 
>>> +#include 
>>> +#include 
>>> +#include 
>>> +
>>> +/**
>>> + * @file
>>> + *
>>> +

Re: [lng-odp] [API-NEXT PATCH 1/3] api: add cuckoo hash api

[HePeng]

Hi, Maxim,
   Thanks for your comments.
   We will fix the code and resubmit.
> 在 2016年4月13日，下午3:28，Maxim Uvarov  写道：
> 
> On 04/13/16 09:40, HePeng wrote:
>> Ping
>> 
>> 
>> Any comments?
> 
> Hello  He,
> 
> people still review your code. I think most of people are busy with 
> finalizing pktio/packet  apis so some time later here should be more 
> feedbacks.
> Please see my comments bellow:
> 
>> or should we put the code into helper/?
>>> 在 2016年4月8日，上午9:19，he peng mailto:hep...@ict.ac.cn>> 写道：
>>> 
>>> Perhaps a generic hash table APIs (not cuckoo hash) could be put in the 
>>> main APIs?
>>> 
>>> 
>>>> 在 2016年4月6日，下午10:18，Ru Jia mailto:ji...@ict.ac.cn>> 写道：
>>>> 
>>>> Last year, there was a discussion about cuckoo hash. I saw the last reply 
>>>> (https://lists.linaro.org/pipermail/lng-odp/2015-December/017921.html).
>>>> You recommended to:
>>>> “
>>>> 1) have this code with queues api;
> this is not done. You still use _ring instead of 
> odp_queue_create()/odp_queue_enq()
>>>> 2) remove ring code completely from helper
> that is now done (api-next branch only).
>>>> 3) move ring code inside linux-generic (I will reuse it for shm pktio ipc);
> that is now done (api-next branch only).
>>>> 4) test performance of cuckoo hash
> I think in cover letter you should write some performance results, which test 
> case prints.
>>>> 5) move it to odp hash API when it will be ready (to do that code should
>>>> not use other helper code, just native odp apis).
>>>> ”
> 
> By saying that I meant that your implementation should use odp api. If there 
> will be some places to implement in hardware
> or it will be very common code for others then we will move that from helper 
> to main api. But as I see now it's almost software
> implementation which should be considered for helper. (I think changing odp_ 
> to odph_ is not big deal).
> 
>>>> Now I find a ring structure in platform/linux-generic/pktio, so I use it 
>>>> to implement cuckoo hash. Then as the 5th point, I put it into odp apis.
> That is wrong. Ideas was that cuckoo hash uses odp_queue() api, not ring. But 
> if current software implementation of queue is slow you
> can accelerate it.
> 
>>>> So, where should cuckoo hash be?
> In the helper.
> 
>>>> And if it’s need to move cuckoo hash into helper, do I need to use 
>>>> odp_queue to implement it?
> Yes, you need to use odp_queue() which is hardware accelerated on many 
> platforms.
> 
> Best regards,
> Maxim.
> 
> 
>>>> *发 件人:*Mike Holmes [mailto:mike.hol...@linaro.org]
>>>> *发送时间:*2016年4月6日19:43
>>>> *收件人:*Ru Jia
>>>> *抄送:*lng-odp; hep...@ict.ac.cn <mailto:hep...@ict.ac.cn>
>>>> *主题:*Re: [lng-odp] [API-NEXT PATCH 1/3] api: add cuckoo hash api
>>>> Thank you for the patch
>>>> Remember that if there is a new API added we also need good validation 
>>>> test coverage in test/validation for it to be accepted eventually into 
>>>> master.
>>>> The performance test is a really good thing to have but we need a cunit 
>>>> test case to help platforms ensure that they all operate the same way for 
>>>> a given release.
>>>> Is there a reason this is not a helper rather than an odp API like the 
>>>> other hashtable support, can this be HW accelerated  ?
>>>> Mike
>>>> On 6 April 2016 at 06:02, Ru Jia >>> <mailto:ji...@ict.ac.cn>> wrote:
>>>>> Added cuckoo hash api, which is an efficient hash table. It could
>>>>> be used for many algorithms.
>>>>> 
>>>>> Signed-off-by: Ru Jia mailto:ji...@ict.ac.cn>>
>>>>> ---
>>>>> include/odp/api/spec/cuckoo_hash.h| 463 
>>>>> +
>>>>> include/odp_api.h |   1 +
>>>>> .../linux-generic/include/odp/api/cuckoo_hash.h   |  34 ++
>>>>> 3 files changed, 498 insertions(+)
>>>>> create mode 100644 include/odp/api/spec/cuckoo_hash.h
>>>>> create mode 100644 platform/linux-generic/include/odp/api/cuckoo_hash.h
>>>>> 
>>>>> diff --git a/include/odp/api/spec/cuckoo_hash.h 
>>>>> b/include/odp/api/spec/cuckoo_hash.h
>>>>> new file mode 100644
>>>>> index 000..ca147ce
>>>>> --- /dev/null
>>>>> +++ b/include/o

Re: [lng-odp] LPM Algorithm APIs in ODP

[HePeng]

Hi, 
   We are in the progress of releasing the LPM code, but currently we are 
busy submitting the cuckoo hash code into ODP helper.

   About the LPM code we have already a 16-8-8 implementation. Now we are 
working on the code to fit it into ODP architecture. But we have not
submitted any code for LPM yet. 
   
   If there is a requirement, we can switch to focus on LPM code. 
   
> 在 2016年4月18日，上午9:03，gyanesh patra  写道：
> 
> I encountered an old email chain about the different LPM algorithm for ODP. I 
> am curious if anyone has released or working on something for l3 
> forwarding/routing.
> Here is the link to the mail chain:
> https://lists.linaro.org/pipermail/lng-odp/2015-August/014717.html 
> 
> 
> If any work is going on, then point me in the correct direction. Also do we 
> have any example code for l3 forwarding in ODP available now?
> 
> Thank you
> P Gyanesh K. Patra
> University of Campinas (Unicamp)
> 
> 
> ___
> lng-odp mailing list
> lng-odp@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/lng-odp

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] LPM Algorithm APIs in ODP

[HePeng]

Hi, 
   Our current LPM code is based on Tree Bitmap as a backend for IP prefixes 
management. Before we submit the code, we need first to remove this part of 
code as Tree Bitmap is a patent algorithm for Cisco.

   If you just want an LPM algorithm for evaluation, we can provide the Tree 
Bitmap code alone, 
but it is not fit into ODP architecture. Please check 
https://github.com/xnhp0320/prefix_lookup_mc.git 
and pull the develop branch. 

   We are working on the code, I think the code should be ready in two weeks. 

   

> 在 2016年4月18日，下午12:39，P Gyanesh Kumar Patra  写道：
> 
> Hi,
> Thank you for the details.
> Do we have any time frame for the LPM code submission? 
> Is it possible to do some trial on the LPM code now?
> 
> Is there a list of names of Algorithms in the pipeline to be developed for 
> ODP?
> 
> Thank You
> P Gyanesh K. Patra
> University of Campinas (Unicamp)
> 
> 
> 
> 
>> On Apr 17, 2016, at 22:55, HePeng > <mailto:xnhp0...@icloud.com>> wrote:
>> 
>> Hi, 
>>We are in the progress of releasing the LPM code, but currently we are 
>> busy submitting the cuckoo hash code into ODP helper.
>> 
>>About the LPM code we have already a 16-8-8 implementation. Now we are 
>> working on the code to fit it into ODP architecture. But we have not
>> submitted any code for LPM yet. 
>>
>>If there is a requirement, we can switch to focus on LPM code. 
>>
>>> 在 2016年4月18日，上午9:03，gyanesh patra >> <mailto:pgyanesh.pa...@gmail.com>> 写道：
>>> 
>>> I encountered an old email chain about the different LPM algorithm for ODP. 
>>> I am curious if anyone has released or working on something for l3 
>>> forwarding/routing.
>>> Here is the link to the mail chain:
>>> https://lists.linaro.org/pipermail/lng-odp/2015-August/014717.html 
>>> <https://lists.linaro.org/pipermail/lng-odp/2015-August/014717.html>
>>> 
>>> If any work is going on, then point me in the correct direction. Also do we 
>>> have any example code for l3 forwarding in ODP available now?
>>> 
>>> Thank you
>>> P Gyanesh K. Patra
>>> University of Campinas (Unicamp)
>>> 
>>> 
>>> ___
>>> lng-odp mailing list
>>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org>
>>> https://lists.linaro.org/mailman/listinfo/lng-odp 
>>> <https://lists.linaro.org/mailman/listinfo/lng-odp>
>> 
> 

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp

Re: [lng-odp] [API-NEXT PATCH v2 1/2] helper: table: add impl of cuckoo hash table

[HePeng]

Hi, 
   We have changed the cuckoo hash code into the ODP/helper where 
we find a table pipeline infrastructure.

   We think maybe it is a better idea to make cuckoo hash as one 
of alternative table.  

> 在 2016年4月18日，下午1:26，Jia Ru  写道：
> 
> According to the comments, I modified the following aspects:
> 1) replaced ring with odp_queue,
> 2) moved cuckoo hash table into helper, and implememted odph_table api
> (helper/table.h)
> 
>> -Original Message-
>> From: Ru Jia [mailto:ji...@ict.ac.cn]
>> Sent: Monday, April 18, 2016 12:53 PM
>> To: lng-odp@lists.linaro.org
>> Cc: xnhp0...@icloud.com; Ru Jia
>> Subject: [API-NEXT PATCH v2 1/2] helper: table: add impl of cuckoo hash
> table
>> 
>> Signed-off-by: Ru Jia 
>> ---
>> helper/Makefile.am|   6 +-
>> helper/cuckootable.c  | 746
>> ++
>> helper/odph_cuckootable.h |  82 +
>> 3 files changed, 832 insertions(+), 2 deletions(-)  create mode 100644
>> helper/cuckootable.c  create mode 100644 helper/odph_cuckootable.h
>> 
>> diff --git a/helper/Makefile.am b/helper/Makefile.am index
> 8a86eb7..1763b99
>> 100644
>> --- a/helper/Makefile.am
>> +++ b/helper/Makefile.am
>> @@ -27,13 +27,15 @@ noinst_HEADERS = \
>>   $(srcdir)/odph_debug.h \
>>   $(srcdir)/odph_hashtable.h \
>>   $(srcdir)/odph_lineartable.h \
>> - $(srcdir)/odph_list_internal.h
>> + $(srcdir)/odph_list_internal.h \
>> + $(srcdir)/odph_cuckootable.h
>> 
>> __LIB__libodphelper_linux_la_SOURCES = \
>>  eth.c \
>>  ip.c \
>>  linux.c \
>>  hashtable.c \
>> -lineartable.c
>> +lineartable.c \
>> +cuckootable.c
>> 
>> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la diff --git
> a/helper/cuckootable.c
>> b/helper/cuckootable.c new file mode 100644 index 000..f607fa0
>> --- /dev/null
>> +++ b/helper/cuckootable.c
>> @@ -0,0 +1,746 @@
>> +/* Copyright (c) 2015, Linaro Limited
>> + * All rights reserved.
>> + *
>> + * SPDX-License-Identifier: BSD-3-Clause
>> + */
>> +
>> +/*-
>> + *   BSD LICENSE
>> + *
>> + *   Copyright(c) 2010-2015 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 
>> +#include 
>> +#include 
>> +#include 
>> +
>> +#include "odph_cuckootable.h"
>> +#include "odph_debug.h"
>> +#include 
>> +
>> +/* Macro to enable/disable run-time checking of function parameters */
>> +#define RETURN_IF_TRUE(cond, retval) do { \
>> +if (cond) \
>> +return retval; \
>> +} while (0)
>> +
>> +/* More efficient access to a map of single ullong */
>> +#define ULLONG_FOR_EACH_1(IDX, MAP) \
>> +for (; MAP && (((IDX) = __builtin_ctzll(MAP)), true); \
>> + MAP = (MAP & (MAP - 1)))
>> +
>> +/** @magic word, write to the first byte of the memory block
>> + *   to indicate this block is used by a cuckoo hash table
>> + */
>> +#define ODPH_CUCKOO_TABLE_MAGIC_WORD 0xDFDFFDFD
>> +
>> +/** Number of items per bucket. */
>> +#define HASH_BUCKET_ENTRIES 4
>> +
>> +#define NULL_SI

[lng-odp] How about adding an algorithm APIs to ODP

[HePeng]

Hi, 
I am new to the ODP project, so I am not sure that should I send this 
email to the mailing list or to somewhere else. 

The thing is that I did some investigation on the code itself, and find 
that there are not any algorithm APIs in ODP. By algorithms, 
I mean IP lookup, hash lookup, which is quite common in many network 
applications.  

To note, I did notice that, DPDK provides some code base to do this, 
for example, the hash, and the lpm (longest prefix matching).
 
My question is that what do you think to add some algorithm APIs to the 
ODP projects?
For example, 
odp_trie_search(…) or odp_hash_table_insert(…)?

Any feedback is appreciated. Thanks.

___
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp