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...@arm.com> Reviewed-by: Malvika Gupta <malvika.gu...@arm.com> Signed-off-by: Yanqin Wei <yanqin....@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 _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev