From patchwork Thu Mar 12 09:39:51 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yanqin Wei X-Patchwork-Id: 1253447 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.136; helo=silver.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 48dP2P42d4z9sPR for ; Thu, 12 Mar 2020 20:40:28 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 0542E2660E; Thu, 12 Mar 2020 09:40:27 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GzkBGI0joPTB; Thu, 12 Mar 2020 09:40:20 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by silver.osuosl.org (Postfix) with ESMTP id 0BC34221B5; Thu, 12 Mar 2020 09:40:20 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id E476FC1D87; Thu, 12 Mar 2020 09:40:19 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 40B9EC0177 for ; Thu, 12 Mar 2020 09:40:19 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 3D3D289373 for ; Thu, 12 Mar 2020 09:40:19 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id El9AjIeC1oei for ; Thu, 12 Mar 2020 09:40:18 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by hemlock.osuosl.org (Postfix) with ESMTP id E52EE89361 for ; Thu, 12 Mar 2020 09:40:17 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 862421FB; Thu, 12 Mar 2020 02:40:17 -0700 (PDT) Received: from net-arm-thunderx2-03.shanghai.arm.com (net-arm-thunderx2-03.shanghai.arm.com [10.169.41.185]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id ABBA73F67D; Thu, 12 Mar 2020 02:40:15 -0700 (PDT) From: Yanqin Wei To: dev@openvswitch.org Date: Thu, 12 Mar 2020 17:39:51 +0800 Message-Id: <20200312093953.56756-2-Yanqin.Wei@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200312093953.56756-1-Yanqin.Wei@arm.com> References: <20200312093953.56756-1-Yanqin.Wei@arm.com> Cc: nd@arm.com, Gavin.Hu@arm.com Subject: [ovs-dev] [PATCH v1 1/3] lib: implement scalable direct address table for fast lookup X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" In the partial flow offloading path, mark2flow table lookup is a hot spot. "cmap_find" takes more than 20% CPU cycles in datapath. Hash map is too heavy for this case and a lighter direct address table can be used for faster lookup. This patch implements a scalable direct address table. It is composed of a series of arrays. It has no array in the initial phase, but it can expand without memory copy. An element of the array is a chain header, whose address can be calculated by index. This table supports single writer, multi-reader concurrent access. Reviewed-by: Gavin Hu Reviewed-by: Malvika Gupta Signed-off-by: Yanqin Wei --- lib/automake.mk | 2 + lib/sda-table.c | 166 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/sda-table.h | 127 ++++++++++++++++++++++++++++++++++++ 3 files changed, 295 insertions(+) create mode 100644 lib/sda-table.c create mode 100644 lib/sda-table.h diff --git a/lib/automake.mk b/lib/automake.mk index 95925b57c..aff21d82a 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -238,6 +238,8 @@ lib_libopenvswitch_la_SOURCES = \ lib/pcap-file.h \ lib/perf-counter.h \ lib/perf-counter.c \ + lib/sda-table.h \ + lib/sda-table.c \ lib/stopwatch.h \ lib/stopwatch.c \ lib/poll-loop.c \ diff --git a/lib/sda-table.c b/lib/sda-table.c new file mode 100644 index 000000000..d83f9e5d0 --- /dev/null +++ b/lib/sda-table.c @@ -0,0 +1,166 @@ +/* + * Copyright (c) 2020 Arm Limited. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include "sda-table.h" +#include "util.h" + +#define SDA_ARRAY_SIZE(ARRAYID) (ARRAYID == 0 ? SDA_TABLE_BASE_SIZE : \ + 1 << (SDA_TABLE_BASE_SIZE_LOG2 + ARRAYID -1)) + +static bool +sda_table_find_node_header(struct sda_table *sda, uint32_t id, + struct sda_table_node **header, bool create_array) +{ + struct sda_table_node *p_array; + uint32_t array_id, offset; + uint32_t l1 = leftmost_1bit_idx(id); + + array_id = id < SDA_TABLE_BASE_SIZE ? + 0 : l1 - SDA_TABLE_BASE_SIZE_LOG2 + 1; + + p_array = ovsrcu_get(struct sda_table_node *, &sda->array[array_id]); + if (p_array == NULL) { + if (create_array) { + p_array = xzalloc_cacheline(sizeof(struct sda_table_node) * + SDA_ARRAY_SIZE(array_id)); + ovsrcu_set(&sda->array[array_id], p_array); + } else { + return false; + } + } + + offset = id < SDA_TABLE_BASE_SIZE ? + id : id - (1 << l1); + *header = p_array + offset; + + return true; +} + +bool +sda_table_insert_node(struct sda_table *sda, uint32_t id, + struct sda_table_node *new) +{ + struct sda_table_node *header = NULL; + + if (sda_table_find_node_header(sda, id, &header, true)) { + struct sda_table_node *node = sda_table_node_next_protected(header); + ovsrcu_set_hidden(&new->next, node); + ovsrcu_set(&header->next, new); + return true; + } else { + return false; + } +} + +bool +sda_table_remove_node(struct sda_table *sda, uint32_t id, + struct sda_table_node *node) +{ + struct sda_table_node *iter = NULL; + + if (sda_table_find_node_header(sda, id, &iter, false)) { + for (;;) { + struct sda_table_node *next = sda_table_node_next_protected(iter); + + if (next == node) { + ovsrcu_set(&iter->next, sda_table_node_next_protected(node)); + return true; + } + else if (next == NULL) { + return false; + } + iter = next; + } + } + + return false; +} + +const struct sda_table_node * +sda_table_find_node(struct sda_table *sda, uint32_t id) +{ + struct sda_table_node * header = NULL; + + if (sda_table_find_node_header(sda, id, &header, false) && header) { + return sda_table_node_next(header); + } else { + return NULL; + } +} + +void +sda_table_destroy(struct sda_table *sda) +{ + if (sda) { + for (uint32_t i = 0; i < SDA_TABLE_ARRAY_NUM; i++) { + const struct sda_table_node *b = + ovsrcu_get(struct sda_table_node *, &sda->array[i]); + if (b) { + ovsrcu_postpone(free, &sda->array[i]); + ovsrcu_set(&sda->array[i], NULL); + } + } + } +} + +struct sda_table_cursor +sda_table_cursor_init(const struct sda_table *sda) +{ + struct sda_table_cursor cursor; + + cursor.sda = sda; + cursor.array_id = 0; + cursor.offset = 0; + cursor.node = NULL; + + return cursor; +} + +bool +sda_table_cursor_next(struct sda_table_cursor *cursor) +{ + const struct sda_table *sda = cursor->sda; + + if (cursor->node) { + cursor->node = sda_table_node_next(cursor->node); + if (cursor->node) { + return true; + } + } + + while (cursor->array_id < SDA_TABLE_ARRAY_NUM) { + const struct sda_table_node *b = + ovsrcu_get(struct sda_table_node *, &sda->array[cursor->array_id]); + if (b == NULL) { + break; + } + + while (cursor->offset < SDA_ARRAY_SIZE(cursor->array_id)) { + cursor->node = sda_table_node_next(b + cursor->offset++); + if (cursor->node) { + return true; + } + } + + cursor->array_id++; + cursor->offset = 0; + } + + return false; +} + + diff --git a/lib/sda-table.h b/lib/sda-table.h new file mode 100644 index 000000000..d38a5e687 --- /dev/null +++ b/lib/sda-table.h @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2020 Arm Limited. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef SDA_TABLE_H +#define SDA_TABLE_H 1 + +#include +#include +#include +#include +#include "ovs-rcu.h" +#include "util.h" + +/* Concurrent scalable direct address table + * ======================================== + * + */ + +/* Scalable direct address table. It is composed of a series of arrays which + * are dynamically allocated as needed. The size of arrays is 2 ^ 10, 2 ^ 10, + * 2 ^ 11, 2 ^ 12 ... The index of the elements in each array increases in + * order, + * i.e array 0: 0 ~ 2 ^ 10 - 1, + * array 1: 2 ^ 10 ~ 2 ^ 11 - 1, + * array 2: 2 ^ 11 ~ 2 ^ 12 - 1. + * When the index of inserted element is out of range of created arrays, a new + * array needs be allocated. + * + * +--------+-------+--------------------------+-------+ + * array No. | 0 | 1 | 2 | 3 | ... | 21 | + * +----|---+---|---+---|---+---|---+----------+---|---+ + * V V V V V + * +----+ +----+ +----+ +----+ + * array size |2^10| |2^10| |2^11| |2^12| + * +----+ +----+ | | | | + * +----+ | | + * | | + * | | + * +----+ + * If the element index is allocated by id_pool which always returns the lowest + * available id, the size of the table will be gradually expanded to 2 ^ 10, + * 2 ^ 11, 2 ^ 12 ... + * + * An element of the array is a chain header, whose address can be calculated + * by index. Computing complexity of the address is O(1) and cost is small. So + * table lookup has high performance. And sda table can support single writer, + * multi-reader concurrent access by means of RCU protection. + */ + +#define SDA_TABLE_BASE_SIZE_LOG2 10 +#define SDA_TABLE_BASE_SIZE (1 << SDA_TABLE_BASE_SIZE_LOG2) +#define SDA_TABLE_ARRAY_NUM (32 - SDA_TABLE_BASE_SIZE_LOG2) + +struct sda_table_node { + OVSRCU_TYPE(struct sda_table_node *) next; +}; + +struct sda_table_cursor { + const struct sda_table *sda; + uint32_t array_id; + uint32_t offset; + struct sda_table_node *node; +}; + +static inline struct sda_table_node * +sda_table_node_next(const struct sda_table_node *node) +{ + return ovsrcu_get(struct sda_table_node *, &node->next); +} + +static inline struct sda_table_node * +sda_table_node_next_protected(const struct sda_table_node *node) +{ + return ovsrcu_get_protected(struct sda_table_node *, &node->next); +} + +struct sda_table { + OVSRCU_TYPE(struct sda_table_node *) array[SDA_TABLE_ARRAY_NUM]; +}; + +/* Initializer for an empty sda table. */ +#define SDA_TABLE_INITIALIZER { { { NULL } } } + +void sda_table_destroy(struct sda_table *sda); +bool sda_table_insert_node(struct sda_table *sda, uint32_t id, + struct sda_table_node *new); +bool sda_table_remove_node(struct sda_table *sda, uint32_t id, + struct sda_table_node *node); +const struct sda_table_node * sda_table_find_node(struct sda_table *sda, + uint32_t id); +struct sda_table_cursor sda_table_cursor_init(const struct sda_table *sda); +bool sda_table_cursor_next(struct sda_table_cursor *cursor); + +#define SDA_TABLE_NODE_FOR_EACH(NODE, MEMBER, SDA_TABLE_NODE) \ + for (INIT_CONTAINER(NODE, SDA_TABLE_NODE, MEMBER); \ + (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER); \ + ASSIGN_CONTAINER(NODE, sda_table_node_next(&(NODE)->MEMBER), MEMBER)) + +#define SDA_TABLE_FOR_EACH_WITH_ID(NODE, MEMBER, ID, SDA_TABLE) \ + SDA_TABLE_NODE_FOR_EACH(NODE, MEMBER, sda_table_find_node(SDA_TABLE, ID)) + +#define SDA_TABLE_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER) \ + (sda_table_cursor_next(CURSOR) \ + ? (INIT_CONTAINER(NODE, (CURSOR)->node, MEMBER), \ + true) \ + : false) + +#define SDA_TABLE_FOR_EACH(NODE, MEMBER, SDA_TABLE) \ + for (struct sda_table_cursor cursor__ = \ + sda_table_cursor_init(SDA_TABLE); \ + SDA_TABLE_CURSOR_FOR_EACH__ (NODE, &cursor__, MEMBER); \ + ) + +#endif /* sda-table.h */ From patchwork Thu Mar 12 09:39:52 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yanqin Wei X-Patchwork-Id: 1253446 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.137; helo=fraxinus.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 48dP2M6pScz9sNg for ; Thu, 12 Mar 2020 20:40:27 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 7ACA286AC1; Thu, 12 Mar 2020 09:40:26 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VPMmd8zaB6m8; Thu, 12 Mar 2020 09:40:25 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by fraxinus.osuosl.org (Postfix) with ESMTP id BC95D869BC; Thu, 12 Mar 2020 09:40:25 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 99CE4C18D3; Thu, 12 Mar 2020 09:40:25 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id ADC8EC0177 for ; Thu, 12 Mar 2020 09:40:23 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 99725893A1 for ; Thu, 12 Mar 2020 09:40:23 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FdVphngZwrWw for ; Thu, 12 Mar 2020 09:40:22 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by hemlock.osuosl.org (Postfix) with ESMTP id 901FC89387 for ; Thu, 12 Mar 2020 09:40:22 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 0D9241FB; Thu, 12 Mar 2020 02:40:22 -0700 (PDT) Received: from net-arm-thunderx2-03.shanghai.arm.com (net-arm-thunderx2-03.shanghai.arm.com [10.169.41.185]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 4926D3F67D; Thu, 12 Mar 2020 02:40:20 -0700 (PDT) From: Yanqin Wei To: dev@openvswitch.org Date: Thu, 12 Mar 2020 17:39:52 +0800 Message-Id: <20200312093953.56756-3-Yanqin.Wei@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200312093953.56756-1-Yanqin.Wei@arm.com> References: <20200312093953.56756-1-Yanqin.Wei@arm.com> Cc: nd@arm.com, Gavin.Hu@arm.com Subject: [ovs-dev] [PATCH v1 2/3] dpif-netdev: improve partial offloding datapath by sda-table lookup X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Cmap_find is a hot spot in partial offloading datapath. This patch applies sda-table for mark2flow lookup. The throughput uplift is more than 10% in case of single flow and 20% with 1000 mega flows. Reviewed-by: Gavin Hu Reviewed-by: Malvika Gupta Signed-off-by: Yanqin Wei --- lib/dpif-netdev.c | 30 +++++++++++++++++------------- 1 file changed, 17 insertions(+), 13 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index d393aab5e..47eacdc51 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -48,6 +48,7 @@ #include "flow.h" #include "hmapx.h" #include "id-pool.h" +#include "sda-table.h" #include "ipf.h" #include "netdev.h" #include "netdev-offload.h" @@ -523,7 +524,8 @@ struct dp_netdev_flow { /* Hash table index by unmasked flow. */ const struct cmap_node node; /* In owning dp_netdev_pmd_thread's */ /* 'flow_table'. */ - const struct cmap_node mark_node; /* In owning flow_mark's mark_to_flow */ + const struct sda_table_node mark_node; /* In owning flow_mark's */ + /* mark_to_flow */ const ovs_u128 ufid; /* Unique flow identifier. */ const ovs_u128 mega_ufid; /* Unique mega flow identifier. */ const unsigned pmd_id; /* The 'core_id' of pmd thread owning this */ @@ -2159,13 +2161,13 @@ struct megaflow_to_mark_data { struct flow_mark { struct cmap megaflow_to_mark; - struct cmap mark_to_flow; + struct sda_table mark_to_flow; struct id_pool *pool; }; static struct flow_mark flow_mark = { .megaflow_to_mark = CMAP_INITIALIZER, - .mark_to_flow = CMAP_INITIALIZER, + .mark_to_flow = SDA_TABLE_INITIALIZER, }; static uint32_t @@ -2248,9 +2250,10 @@ mark_to_flow_associate(const uint32_t mark, struct dp_netdev_flow *flow) { dp_netdev_flow_ref(flow); - cmap_insert(&flow_mark.mark_to_flow, - CONST_CAST(struct cmap_node *, &flow->mark_node), - hash_int(mark, 0)); + sda_table_insert_node(&flow_mark.mark_to_flow, + mark, + CONST_CAST(struct sda_table_node *, &flow->mark_node)); + flow->mark = mark; VLOG_DBG("Associated dp_netdev flow %p with mark %u\n", flow, mark); @@ -2261,8 +2264,8 @@ flow_mark_has_no_ref(uint32_t mark) { struct dp_netdev_flow *flow; - CMAP_FOR_EACH_WITH_HASH (flow, mark_node, hash_int(mark, 0), - &flow_mark.mark_to_flow) { + SDA_TABLE_FOR_EACH_WITH_ID (flow, mark_node, mark, + &flow_mark.mark_to_flow) { if (flow->mark == mark) { return false; } @@ -2277,10 +2280,11 @@ mark_to_flow_disassociate(struct dp_netdev_pmd_thread *pmd, { int ret = 0; uint32_t mark = flow->mark; - struct cmap_node *mark_node = CONST_CAST(struct cmap_node *, + struct sda_table_node *mark_node = CONST_CAST(struct sda_table_node *, &flow->mark_node); - cmap_remove(&flow_mark.mark_to_flow, mark_node, hash_int(mark, 0)); + ovs_assert(sda_table_remove_node(&flow_mark.mark_to_flow, + mark, mark_node)); flow->mark = INVALID_FLOW_MARK; /* @@ -2316,7 +2320,7 @@ flow_mark_flush(struct dp_netdev_pmd_thread *pmd) { struct dp_netdev_flow *flow; - CMAP_FOR_EACH (flow, mark_node, &flow_mark.mark_to_flow) { + SDA_TABLE_FOR_EACH (flow, mark_node, &flow_mark.mark_to_flow) { if (flow->pmd_id == pmd->core_id) { queue_netdev_flow_del(pmd, flow); } @@ -2329,8 +2333,8 @@ mark_to_flow_find(const struct dp_netdev_pmd_thread *pmd, { struct dp_netdev_flow *flow; - CMAP_FOR_EACH_WITH_HASH (flow, mark_node, hash_int(mark, 0), - &flow_mark.mark_to_flow) { + SDA_TABLE_FOR_EACH_WITH_ID (flow, mark_node, mark, + &flow_mark.mark_to_flow) { if (flow->mark == mark && flow->pmd_id == pmd->core_id && flow->dead == false) { return flow; From patchwork Thu Mar 12 09:39:53 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yanqin Wei X-Patchwork-Id: 1253448 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.137; helo=fraxinus.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 48dP2R5vcxz9sQt for ; Thu, 12 Mar 2020 20:40:31 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 5ABB186BB9; Thu, 12 Mar 2020 09:40:30 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id l0FAOrxEd8dQ; Thu, 12 Mar 2020 09:40:28 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by fraxinus.osuosl.org (Postfix) with ESMTP id B29A586BFF; Thu, 12 Mar 2020 09:40:28 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id A6C56C1D87; Thu, 12 Mar 2020 09:40:28 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1BF1FC0177 for ; Thu, 12 Mar 2020 09:40:27 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 07976893A2 for ; Thu, 12 Mar 2020 09:40:27 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bDWWmnEiFq-j for ; Thu, 12 Mar 2020 09:40:25 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by hemlock.osuosl.org (Postfix) with ESMTP id 9AA16893A9 for ; Thu, 12 Mar 2020 09:40:25 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 4569B1FB; Thu, 12 Mar 2020 02:40:25 -0700 (PDT) Received: from net-arm-thunderx2-03.shanghai.arm.com (net-arm-thunderx2-03.shanghai.arm.com [10.169.41.185]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 73F333F67D; Thu, 12 Mar 2020 02:40:23 -0700 (PDT) From: Yanqin Wei To: dev@openvswitch.org Date: Thu, 12 Mar 2020 17:39:53 +0800 Message-Id: <20200312093953.56756-4-Yanqin.Wei@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200312093953.56756-1-Yanqin.Wei@arm.com> References: <20200312093953.56756-1-Yanqin.Wei@arm.com> Cc: nd@arm.com, Gavin.Hu@arm.com Subject: [ovs-dev] [PATCH v1 3/3] tests/test-sda-table: add check test for sda-table. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Add check test for sda-table lookup, insertion and deletion. Reviewed-by: Gavin Hu Reviewed-by: Malvika Gupta Signed-off-by: Yanqin Wei --- tests/automake.mk | 3 +- tests/test-sda-table.c | 197 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 199 insertions(+), 1 deletion(-) create mode 100644 tests/test-sda-table.c diff --git a/tests/automake.mk b/tests/automake.mk index 9c7ebdce9..9581ffb8e 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -462,7 +462,8 @@ tests_ovstest_SOURCES = \ tests/test-bitmap.c \ tests/test-vconn.c \ tests/test-aa.c \ - tests/test-stopwatch.c + tests/test-stopwatch.c \ + tests/test-sda-table.c if !WIN32 tests_ovstest_SOURCES += \ diff --git a/tests/test-sda-table.c b/tests/test-sda-table.c new file mode 100644 index 000000000..6bcd4cefb --- /dev/null +++ b/tests/test-sda-table.c @@ -0,0 +1,197 @@ +/* + * Copyright (c) 2020 Arm Limited. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* A functional test for some of the functions and macros declared in + * sda-table.h. */ + +#include +#undef NDEBUG +#include "sda-table.h" +#include "id-pool.h" +#include +#include +#include +#include "bitmap.h" +#include "command-line.h" +#include "ovstest.h" +#include "ovs-thread.h" +#include "util.h" + +struct element { + struct sda_table_node node; +}; + +/* Tests basic sda table insertion and deletion for single node chain. */ +static void +test_sda_table_add_del_singlenode_chain(void) +{ + enum { N_ELEMS = 10000 }; + struct element elements[N_ELEMS]; + uint32_t id[N_ELEMS]; + + size_t i; + struct id_pool *pool = id_pool_create(0, UINT32_MAX - 1); + struct sda_table sda = SDA_TABLE_INITIALIZER; + const struct sda_table_node * node; + bool ret; + + for (i = 0; i < N_ELEMS; i++) { + ret = id_pool_alloc_id(pool, &id[i]); + ovs_assert(ret == true); + + ret = sda_table_insert_node(&sda, id[i], &elements[id[i]].node); + ovs_assert(ret == true); + + node = sda_table_find_node(&sda, id[i]); + ovs_assert(node == &elements[id[i]].node); + + ret = sda_table_remove_node(&sda, id[i], &elements[id[i]].node); + ovs_assert(ret == true); + + node = sda_table_find_node(&sda, id[i]); + ovs_assert(node == NULL); + + id_pool_free_id(pool, id[i]); + } + + sda_table_destroy(&sda); + id_pool_destroy(pool); +} + + +static void +test_sda_table_add_del_multinode_chain(void) +{ + enum { N_ELEMS = 10000, N_NODES = 10 }; + struct element elements[N_ELEMS][N_NODES]; + uint32_t id[N_ELEMS]; + + struct element *elm; + size_t i, j; + struct id_pool *pool = id_pool_create(0, UINT32_MAX - 1); + struct sda_table sda = SDA_TABLE_INITIALIZER; + bool ret; + + for (i = 0; i < N_ELEMS; i++) { + ret = id_pool_alloc_id(pool, &id[i]); + ovs_assert(ret == true); + + for (j = 0; j < N_NODES; j++) { + ret = sda_table_insert_node(&sda, id[i], &elements[id[i]][j].node); + ovs_assert(ret == true); + } + + SDA_TABLE_FOR_EACH_WITH_ID (elm, node, id[i], &sda) { + for (j = 0; j < N_NODES; j++) { + if (elm == &elements[id[i]][j]) { + break; + } + } + ovs_assert(elm == &elements[id[i]][j]); + } + + for (j = N_NODES / 2; j < N_NODES; j++) { + ret = sda_table_remove_node(&sda, id[i], &elements[id[i]][j].node); + ovs_assert(ret == true); + } + + SDA_TABLE_FOR_EACH_WITH_ID (elm, node, id[i], &sda) { + for (j = 0; j < N_NODES / 2; j++) { + if (elm == &elements[id[i]][j]) { + break; + } + } + ovs_assert(elm == &elements[id[i]][j]); + } + } + + for (i = N_ELEMS / 2; i < N_ELEMS; i++) { + for (j = 0; j < N_NODES; j++) { + ret = sda_table_remove_node(&sda, id[i], &elements[id[i]][j].node); + } + id_pool_free_id(pool, id[i]); + + SDA_TABLE_FOR_EACH_WITH_ID (elm, node, id[i], &sda) { + ovs_assert(elm == NULL); + } + } + + for (i = 0; i < N_ELEMS / 2; i++) { + SDA_TABLE_FOR_EACH_WITH_ID (elm, node, id[i], &sda) { + for (j = 0; j < N_NODES; j++) { + if (elm == &elements[id[i]][j]) { + break; + } + } + ovs_assert(elm == &elements[id[i]][j]); + } + } + + sda_table_destroy(&sda); + id_pool_destroy(pool); +} + +static void +test_sda_table_invalid_add_del(void) +{ + enum { N_ELEMS = 10000, N_NODES = 10 }; + struct element elements; + + struct id_pool *pool = id_pool_create(0, UINT32_MAX - 1); + struct sda_table sda = SDA_TABLE_INITIALIZER; + bool ret; + + ret = sda_table_insert_node(&sda, SDA_TABLE_BASE_SIZE * 2, &elements.node); + ovs_assert(ret == true); + + ret = sda_table_remove_node(&sda, SDA_TABLE_BASE_SIZE * 2, &elements.node); + ovs_assert(ret == true); + + ret = sda_table_remove_node(&sda, SDA_TABLE_BASE_SIZE * 2, &elements.node); + ovs_assert(ret == false); + + sda_table_destroy(&sda); + id_pool_destroy(pool); +} + + +static void +run_tests(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + test_sda_table_add_del_singlenode_chain(); + test_sda_table_add_del_multinode_chain(); + test_sda_table_invalid_add_del(); + printf("\n"); +} + +static const struct ovs_cmdl_command commands[] = { + {"check", NULL, 0, 1, run_tests, OVS_RO}, + {NULL, NULL, 0, 0, NULL, OVS_RO}, +}; + +static void +test_sda_table_main(int argc, char *argv[]) +{ + struct ovs_cmdl_context ctx = { + .argc = argc - optind, + .argv = argv + optind, + }; + + set_program_name(argv[0]); + ovs_cmdl_run_command(&ctx, commands); +} + +OVSTEST_REGISTER("test-sda-table", test_sda_table_main);