[ovs-dev] [PATCH v1 1/3] lib: implement scalable direct address table for fast lookup
Yanqin Wei
Yanqin.Wei at arm.com
Thu Mar 12 09:39:51 UTC 2020
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 <Gavin.Hu at arm.com>
Reviewed-by: Malvika Gupta <Malvika.Gupta at arm.com>
Signed-off-by: Yanqin Wei <Yanqin.Wei at arm.com>
---
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 <config.h>
+#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 <config.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#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 */
--
2.17.1
More information about the dev
mailing list