diff mbox series

[ovs-dev,v1,1/3] lib: implement scalable direct address table for fast lookup

Message ID 20200312093953.56756-2-Yanqin.Wei@arm.com
State Under Review
Delegated to: Ilya Maximets
Headers show
Series improve mark2flow lookup for partial offloading datapath | expand

Commit Message

Yanqin Wei March 12, 2020, 9:39 a.m. UTC
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@arm.com>
Reviewed-by: Malvika Gupta <Malvika.Gupta@arm.com>
Signed-off-by: Yanqin Wei <Yanqin.Wei@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

Comments

0-day Robot March 12, 2020, 9:58 a.m. UTC | #1
Bleep bloop.  Greetings Yanqin Wei, I am a robot and I have tried out your patch.
Thanks for your contribution.

I encountered some error that I wasn't expecting.  See the details below.


checkpatch:
ERROR: Improper whitespace around control block
#326 FILE: lib/sda-table.h:107:
#define SDA_TABLE_NODE_FOR_EACH(NODE, MEMBER, SDA_TABLE_NODE)             \

ERROR: Improper whitespace around control block
#331 FILE: lib/sda-table.h:112:
#define SDA_TABLE_FOR_EACH_WITH_ID(NODE, MEMBER, ID, SDA_TABLE)          \

ERROR: Improper whitespace around control block
#332 FILE: lib/sda-table.h:113:
    SDA_TABLE_NODE_FOR_EACH(NODE, MEMBER, sda_table_find_node(SDA_TABLE, ID))

ERROR: Improper whitespace around control block
#334 FILE: lib/sda-table.h:115:
#define SDA_TABLE_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER)   \

ERROR: Improper whitespace around control block
#340 FILE: lib/sda-table.h:121:
#define SDA_TABLE_FOR_EACH(NODE, MEMBER, SDA_TABLE) \

ERROR: Inappropriate bracing around statement
#343 FILE: lib/sda-table.h:124:
             SDA_TABLE_CURSOR_FOR_EACH__ (NODE, &cursor__, MEMBER);  \

Lines checked: 349, Warnings: 0, Errors: 6


Please check this out.  If you feel there has been an error, please email aconole@redhat.com

Thanks,
0-day Robot
diff mbox series

Patch

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 */