From patchwork Tue Mar 30 09:16:45 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anton Ivanov X-Patchwork-Id: 1459964 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=2605:bc80:3010::136; helo=smtp3.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4F8kNq0RYDz9sVq for ; Tue, 30 Mar 2021 20:17:15 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 7B45760853; Tue, 30 Mar 2021 09:17:12 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id igNPg88x2BhC; Tue, 30 Mar 2021 09:17:06 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp3.osuosl.org (Postfix) with ESMTP id 273B16083F; Tue, 30 Mar 2021 09:17:05 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id EB6DEC000C; Tue, 30 Mar 2021 09:17:04 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3BF12C000A for ; Tue, 30 Mar 2021 09:17:01 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 18DE083CEE for ; Tue, 30 Mar 2021 09:17:00 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vTJWiHP5jcvJ for ; Tue, 30 Mar 2021 09:16:58 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from www.kot-begemot.co.uk (ivanoab7.miniserver.com [37.128.132.42]) by smtp1.osuosl.org (Postfix) with ESMTPS id 086D383CE6 for ; Tue, 30 Mar 2021 09:16:57 +0000 (UTC) Received: from tun252.jain.kot-begemot.co.uk ([192.168.18.6] helo=jain.kot-begemot.co.uk) by www.kot-begemot.co.uk with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lRAUY-00017U-Fb; Tue, 30 Mar 2021 09:16:55 +0000 Received: from jain.kot-begemot.co.uk ([192.168.3.3]) by jain.kot-begemot.co.uk with esmtp (Exim 4.92) (envelope-from ) id 1lRAUU-0006Ng-Fp; Tue, 30 Mar 2021 10:16:52 +0100 From: anton.ivanov@cambridgegreys.com To: ovs-dev@openvswitch.org Date: Tue, 30 Mar 2021 10:16:45 +0100 Message-Id: <20210330091647.24470-1-anton.ivanov@cambridgegreys.com> X-Mailer: git-send-email 2.20.1 MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett Cc: i.maximets@ovn.org, Anton Ivanov Subject: [ovs-dev] [OVN Patch v16 1/3] ovn-libs: Add support for parallel processing 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: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" From: Anton Ivanov This adds a set of functions and macros intended to process hashes in parallel. The principles of operation are documented in the fasthmap.h If these one day go into the OVS tree, the OVS tree versions would be used in preference. Signed-off-by: Anton Ivanov --- lib/automake.mk | 2 + lib/ovn-parallel-hmap.c | 460 ++++++++++++++++++++++++++++++++++++++++ lib/ovn-parallel-hmap.h | 303 ++++++++++++++++++++++++++ ovs | 2 +- 4 files changed, 766 insertions(+), 1 deletion(-) create mode 100644 lib/ovn-parallel-hmap.c create mode 100644 lib/ovn-parallel-hmap.h diff --git a/lib/automake.mk b/lib/automake.mk index 250c7aefa..781be2109 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -13,6 +13,8 @@ lib_libovn_la_SOURCES = \ lib/expr.c \ lib/extend-table.h \ lib/extend-table.c \ + lib/ovn-parallel-hmap.h \ + lib/ovn-parallel-hmap.c \ lib/ip-mcast-index.c \ lib/ip-mcast-index.h \ lib/mcast-group-index.c \ diff --git a/lib/ovn-parallel-hmap.c b/lib/ovn-parallel-hmap.c new file mode 100644 index 000000000..6b7fccfde --- /dev/null +++ b/lib/ovn-parallel-hmap.c @@ -0,0 +1,460 @@ +/* + * Copyright (c) 2020 Red Hat, Inc. + * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2015, 2019 Nicira, Inc. + * + * 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 +#include +#include +#include +#include +#include +#include +#include "fatal-signal.h" +#include "util.h" +#include "openvswitch/vlog.h" +#include "openvswitch/hmap.h" +#include "openvswitch/thread.h" +#include "ovn-parallel-hmap.h" +#include "ovs-atomic.h" +#include "ovs-thread.h" +#include "ovs-numa.h" +#include "random.h" + +VLOG_DEFINE_THIS_MODULE(ovn_parallel_hmap); + +#ifndef OVS_HAS_PARALLEL_HMAP + +#define WORKER_SEM_NAME "%x-%p-%x" +#define MAIN_SEM_NAME "%x-%p-main" + +/* These are accessed under mutex inside add_worker_pool(). + * They do not need to be atomic. + */ + +static atomic_bool initial_pool_setup = ATOMIC_VAR_INIT(false); +static bool can_parallelize = false; + +/* This is set only in the process of exit and the set is + * accompanied by a fence. It does not need to be atomic or be + * accessed under a lock. + */ + +static bool workers_must_exit = false; + +static struct ovs_list worker_pools = OVS_LIST_INITIALIZER(&worker_pools); + +static struct ovs_mutex init_mutex = OVS_MUTEX_INITIALIZER; + +static int pool_size; + +static int sembase; + +static void worker_pool_hook(void *aux OVS_UNUSED); +static void setup_worker_pools(bool force); +static void merge_list_results(struct worker_pool *pool OVS_UNUSED, + void *fin_result, void *result_frags, + int index); +static void merge_hash_results(struct worker_pool *pool OVS_UNUSED, + void *fin_result, void *result_frags, + int index); + +bool ovn_stop_parallel_processing(void) +{ + return workers_must_exit; +} + +bool ovn_can_parallelize_hashes(bool force_parallel) +{ + bool test = false; + + if (atomic_compare_exchange_strong( + &initial_pool_setup, + &test, + true)) { + ovs_mutex_lock(&init_mutex); + setup_worker_pools(force_parallel); + ovs_mutex_unlock(&init_mutex); + } + return can_parallelize; +} + +struct worker_pool *ovn_add_worker_pool(void *(*start)(void *)){ + + struct worker_pool *new_pool = NULL; + struct worker_control *new_control; + bool test = false; + int i; + char sem_name[256]; + + + /* Belt and braces - initialize the pool system just in case if + * if it is not yet initialized. + */ + + if (atomic_compare_exchange_strong( + &initial_pool_setup, + &test, + true)) { + ovs_mutex_lock(&init_mutex); + setup_worker_pools(false); + ovs_mutex_unlock(&init_mutex); + } + + ovs_mutex_lock(&init_mutex); + if (can_parallelize) { + new_pool = xmalloc(sizeof(struct worker_pool)); + new_pool->size = pool_size; + new_pool->controls = NULL; + sprintf(sem_name, MAIN_SEM_NAME, sembase, new_pool); + new_pool->done = sem_open(sem_name, O_CREAT, S_IRWXU, 0); + if (new_pool->done == SEM_FAILED) { + goto cleanup; + } + + new_pool->controls = + xmalloc(sizeof(struct worker_control) * new_pool->size); + + for (i = 0; i < new_pool->size; i++) { + new_control = &new_pool->controls[i]; + new_control->id = i; + new_control->done = new_pool->done; + new_control->data = NULL; + ovs_mutex_init(&new_control->mutex); + new_control->finished = ATOMIC_VAR_INIT(false); + sprintf(sem_name, WORKER_SEM_NAME, sembase, new_pool, i); + new_control->fire = sem_open(sem_name, O_CREAT, S_IRWXU, 0); + if (new_control->fire == SEM_FAILED) { + goto cleanup; + } + } + + for (i = 0; i < pool_size; i++) { + new_pool->controls[i].worker = + ovs_thread_create("worker pool helper", start, &new_pool->controls[i]); + } + ovs_list_push_back(&worker_pools, &new_pool->list_node); + } + ovs_mutex_unlock(&init_mutex); + return new_pool; +cleanup: + + /* Something went wrong when opening semaphores. In this case + * it is better to shut off parallel procesing altogether + */ + + VLOG_INFO("Failed to initialize parallel processing, error %d", errno); + can_parallelize = false; + if (new_pool->controls) { + for (i = 0; i < new_pool->size; i++) { + if (new_pool->controls[i].fire != SEM_FAILED) { + sem_close(new_pool->controls[i].fire); + sprintf(sem_name, WORKER_SEM_NAME, sembase, new_pool, i); + sem_unlink(sem_name); + break; /* semaphores past this one are uninitialized */ + } + } + } + if (new_pool->done != SEM_FAILED) { + sem_close(new_pool->done); + sprintf(sem_name, MAIN_SEM_NAME, sembase, new_pool); + sem_unlink(sem_name); + } + ovs_mutex_unlock(&init_mutex); + return NULL; +} + + +/* Initializes 'hmap' as an empty hash table with mask N. */ +void +ovn_fast_hmap_init(struct hmap *hmap, ssize_t mask) +{ + size_t i; + + hmap->buckets = xmalloc(sizeof (struct hmap_node *) * (mask + 1)); + hmap->one = NULL; + hmap->mask = mask; + hmap->n = 0; + for (i = 0; i <= hmap->mask; i++) { + hmap->buckets[i] = NULL; + } +} + +/* Initializes 'hmap' as an empty hash table of size X. + * Intended for use in parallel processing so that all + * fragments used to store results in a parallel job + * are the same size. + */ +void +ovn_fast_hmap_size_for(struct hmap *hmap, int size) +{ + size_t mask; + mask = size / 2; + mask |= mask >> 1; + mask |= mask >> 2; + mask |= mask >> 4; + mask |= mask >> 8; + mask |= mask >> 16; +#if SIZE_MAX > UINT32_MAX + mask |= mask >> 32; +#endif + + /* If we need to dynamically allocate buckets we might as well allocate at + * least 4 of them. */ + mask |= (mask & 1) << 1; + + fast_hmap_init(hmap, mask); +} + +/* Run a thread pool which uses a callback function to process results + */ + +void ovn_run_pool_callback(struct worker_pool *pool, + void *fin_result, void *result_frags, + void (*helper_func)(struct worker_pool *pool, + void *fin_result, + void *result_frags, int index)) +{ + int index, completed; + + /* Ensure that all worker threads see the same data as the + * main thread. + */ + + atomic_thread_fence(memory_order_release); + + /* Start workers */ + + for (index = 0; index < pool->size; index++) { + sem_post(pool->controls[index].fire); + } + + completed = 0; + + do { + bool test; + /* Note - we do not loop on semaphore until it reaches + * zero, but on pool size/remaining workers. + * This is by design. If the inner loop can handle + * completion for more than one worker within an iteration + * it will do so to ensure no additional iterations and + * waits once all of them are done. + * + * This may result in us having an initial positive value + * of the semaphore when the pool is invoked the next time. + * This is harmless - the loop will spin up a couple of times + * doing nothing while the workers are processing their data + * slices. + */ + wait_for_work_completion(pool); + for (index = 0; index < pool->size; index++) { + test = true; + /* If the worker has marked its data chunk as complete, + * invoke the helper function to combine the results of + * this worker into the main result. + * + * The worker must invoke an appropriate memory fence + * (most likely acq_rel) to ensure that the main thread + * sees all of the results produced by the worker. + */ + if (atomic_compare_exchange_weak( + &pool->controls[index].finished, + &test, + false)) { + atomic_thread_fence(memory_order_acquire); + if (helper_func) { + (helper_func)(pool, fin_result, result_frags, index); + } + completed++; + pool->controls[index].data = NULL; + } + } + } while (completed < pool->size); +} + +/* Run a thread pool - basic, does not do results processing. + */ + +void ovn_run_pool(struct worker_pool *pool) +{ + run_pool_callback(pool, NULL, NULL, NULL); +} + +/* Brute force merge of a hashmap into another hashmap. + * Intended for use in parallel processing. The destination + * hashmap MUST be the same size as the one being merged. + * + * This can be achieved by pre-allocating them to correct size + * and using hmap_insert_fast() instead of hmap_insert() + */ + +void ovn_fast_hmap_merge(struct hmap *dest, struct hmap *inc) +{ + size_t i; + + ovs_assert(inc->mask == dest->mask); + + if (!inc->n) { + /* Request to merge an empty frag, nothing to do */ + return; + } + + for (i = 0; i <= dest->mask; i++) { + struct hmap_node **dest_bucket = &dest->buckets[i]; + struct hmap_node **inc_bucket = &inc->buckets[i]; + if (*inc_bucket != NULL) { + struct hmap_node *last_node = *inc_bucket; + while (last_node->next != NULL) { + last_node = last_node->next; + } + last_node->next = *dest_bucket; + *dest_bucket = *inc_bucket; + *inc_bucket = NULL; + } + } + dest->n += inc->n; + inc->n = 0; +} + +/* Run a thread pool which gathers results in an array + * of hashes. Merge results. + */ + + +void ovn_run_pool_hash( + struct worker_pool *pool, + struct hmap *result, + struct hmap *result_frags) +{ + run_pool_callback(pool, result, result_frags, merge_hash_results); +} + +/* Run a thread pool which gathers results in an array of lists. + * Merge results. + */ +void ovn_run_pool_list( + struct worker_pool *pool, + struct ovs_list *result, + struct ovs_list *result_frags) +{ + run_pool_callback(pool, result, result_frags, merge_list_results); +} + +void ovn_update_hashrow_locks(struct hmap *lflows, struct hashrow_locks *hrl) +{ + int i; + if (hrl->mask != lflows->mask) { + if (hrl->row_locks) { + free(hrl->row_locks); + } + hrl->row_locks = xcalloc(sizeof(struct ovs_mutex), lflows->mask + 1); + hrl->mask = lflows->mask; + for (i = 0; i <= lflows->mask; i++) { + ovs_mutex_init(&hrl->row_locks[i]); + } + } +} + +static void worker_pool_hook(void *aux OVS_UNUSED) { + int i; + static struct worker_pool *pool; + char sem_name[256]; + + workers_must_exit = true; + + /* All workers must honour the must_exit flag and check for it regularly. + * We can make it atomic and check it via atomics in workers, but that + * is not really necessary as it is set just once - when the program + * terminates. So we use a fence which is invoked before exiting instead. + */ + atomic_thread_fence(memory_order_acq_rel); + + /* Wake up the workers after the must_exit flag has been set */ + + LIST_FOR_EACH (pool, list_node, &worker_pools) { + for (i = 0; i < pool->size ; i++) { + sem_post(pool->controls[i].fire); + } + for (i = 0; i < pool->size ; i++) { + pthread_join(pool->controls[i].worker, NULL); + } + for (i = 0; i < pool->size ; i++) { + sem_close(pool->controls[i].fire); + sprintf(sem_name, WORKER_SEM_NAME, sembase, pool, i); + sem_unlink(sem_name); + } + sem_close(pool->done); + sprintf(sem_name, MAIN_SEM_NAME, sembase, pool); + sem_unlink(sem_name); + } +} + +static void setup_worker_pools(bool force) { + int cores, nodes; + + nodes = ovs_numa_get_n_numas(); + if (nodes == OVS_NUMA_UNSPEC || nodes <= 0) { + nodes = 1; + } + cores = ovs_numa_get_n_cores(); + + /* If there is no NUMA config, use 4 cores. + * If there is NUMA config use half the cores on + * one node so that the OS does not start pushing + * threads to other nodes. + */ + if (cores == OVS_CORE_UNSPEC || cores <= 0) { + /* If there is no NUMA we can try the ovs-threads routine. + * It falls back to sysconf and/or affinity mask. + */ + cores = count_cpu_cores(); + pool_size = cores; + } else { + pool_size = cores / nodes; + } + if ((pool_size < 4) && force) { + pool_size = 4; + } + can_parallelize = (pool_size >= 3); + fatal_signal_add_hook(worker_pool_hook, NULL, NULL, true); + sembase = random_uint32(); +} + +static void merge_list_results(struct worker_pool *pool OVS_UNUSED, + void *fin_result, void *result_frags, + int index) +{ + struct ovs_list *result = (struct ovs_list *)fin_result; + struct ovs_list *res_frags = (struct ovs_list *)result_frags; + + if (!ovs_list_is_empty(&res_frags[index])) { + ovs_list_splice(result->next, + ovs_list_front(&res_frags[index]), &res_frags[index]); + } +} + +static void merge_hash_results(struct worker_pool *pool OVS_UNUSED, + void *fin_result, void *result_frags, + int index) +{ + struct hmap *result = (struct hmap *)fin_result; + struct hmap *res_frags = (struct hmap *)result_frags; + + fast_hmap_merge(result, &res_frags[index]); + hmap_destroy(&res_frags[index]); +} + +#endif diff --git a/lib/ovn-parallel-hmap.h b/lib/ovn-parallel-hmap.h new file mode 100644 index 000000000..124dfcbc7 --- /dev/null +++ b/lib/ovn-parallel-hmap.h @@ -0,0 +1,303 @@ +/* + * Copyright (c) 2020 Red Hat, Inc. + * + * 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 OVN_PARALLEL_HMAP +#define OVN_PARALLEL_HMAP 1 + +/* if the parallel macros are defined by hmap.h or any other ovs define + * we skip over the ovn specific definitions. + */ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include +#include +#include +#include "openvswitch/util.h" +#include "openvswitch/hmap.h" +#include "openvswitch/thread.h" +#include "ovs-atomic.h" + +/* Process this include only if OVS does not supply parallel definitions + */ + +#ifdef OVS_HAS_PARALLEL_HMAP + +#include "parallel-hmap.h" + +#else + + +#ifdef __clang__ +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wthread-safety" +#endif + + +/* A version of the HMAP_FOR_EACH macro intended for iterating as part + * of parallel processing. + * Each worker thread has a different ThreadID in the range of 0..POOL_SIZE + * and will iterate hash buckets ThreadID, ThreadID + step, + * ThreadID + step * 2, etc. The actual macro accepts + * ThreadID + step * i as the JOBID parameter. + */ + +#define HMAP_FOR_EACH_IN_PARALLEL(NODE, MEMBER, JOBID, HMAP) \ + for (INIT_CONTAINER(NODE, hmap_first_in_bucket_num(HMAP, JOBID), MEMBER); \ + (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) \ + || ((NODE = NULL), false); \ + ASSIGN_CONTAINER(NODE, hmap_next_in_bucket(&(NODE)->MEMBER), MEMBER)) + +/* We do not have a SAFE version of the macro, because the hash size is not + * atomic and hash removal operations would need to be wrapped with + * locks. This will defeat most of the benefits from doing anything in + * parallel. + * If the code block inside FOR_EACH_IN_PARALLEL needs to remove elements, + * each thread should store them in a temporary list result instead, merging + * the lists into a combined result at the end */ + +/* Work "Handle" */ + +struct worker_control { + int id; /* Used as a modulo when iterating over a hash. */ + atomic_bool finished; /* Set to true after achunk of work is complete. */ + sem_t *fire; /* Work start semaphore - sem_post starts the worker. */ + sem_t *done; /* Work completion semaphore - sem_post on completion. */ + struct ovs_mutex mutex; /* Guards the data. */ + void *data; /* Pointer to data to be processed. */ + void *workload; /* back-pointer to the worker pool structure. */ + pthread_t worker; +}; + +struct worker_pool { + int size; /* Number of threads in the pool. */ + struct ovs_list list_node; /* List of pools - used in cleanup/exit. */ + struct worker_control *controls; /* "Handles" in this pool. */ + sem_t *done; /* Work completion semaphorew. */ +}; + +/* Add a worker pool for thread function start() which expects a pointer to + * a worker_control structure as an argument. */ + +struct worker_pool *ovn_add_worker_pool(void *(*start)(void *)); + +/* Setting this to true will make all processing threads exit */ + +bool ovn_stop_parallel_processing(void); + +/* Build a hmap pre-sized for size elements */ + +void ovn_fast_hmap_size_for(struct hmap *hmap, int size); + +/* Build a hmap with a mask equals to size */ + +void ovn_fast_hmap_init(struct hmap *hmap, ssize_t size); + +/* Brute-force merge a hmap into hmap. + * Dest and inc have to have the same mask. The merge is performed + * by extending the element list for bucket N in the dest hmap with the list + * from bucket N in inc. + */ + +void ovn_fast_hmap_merge(struct hmap *dest, struct hmap *inc); + +/* Run a pool, without any default processing of results. + */ + +void ovn_run_pool(struct worker_pool *pool); + +/* Run a pool, merge results from hash frags into a final hash result. + * The hash frags must be pre-sized to the same size. + */ + +void ovn_run_pool_hash(struct worker_pool *pool, + struct hmap *result, struct hmap *result_frags); +/* Run a pool, merge results from list frags into a final list result. + */ + +void ovn_run_pool_list(struct worker_pool *pool, + struct ovs_list *result, struct ovs_list *result_frags); + +/* Run a pool, call a callback function to perform processing of results. + */ + +void ovn_run_pool_callback(struct worker_pool *pool, void *fin_result, + void *result_frags, + void (*helper_func)(struct worker_pool *pool, + void *fin_result, void *result_frags, int index)); + + +/* Returns the first node in 'hmap' in the bucket in which the given 'hash' + * would land, or a null pointer if that bucket is empty. */ + +static inline struct hmap_node * +hmap_first_in_bucket_num(const struct hmap *hmap, size_t num) +{ + return hmap->buckets[num]; +} + +static inline struct hmap_node * +parallel_hmap_next__(const struct hmap *hmap, size_t start, size_t pool_size) +{ + size_t i; + for (i = start; i <= hmap->mask; i+= pool_size) { + struct hmap_node *node = hmap->buckets[i]; + if (node) { + return node; + } + } + return NULL; +} + +/* Returns the first node in 'hmap', as expected by thread with job_id + * for parallel processing in arbitrary order, or a null pointer if + * the slice of 'hmap' for that job_id is empty. */ +static inline struct hmap_node * +parallel_hmap_first(const struct hmap *hmap, size_t job_id, size_t pool_size) +{ + return parallel_hmap_next__(hmap, job_id, pool_size); +} + +/* Returns the next node in the slice of 'hmap' following 'node', + * in arbitrary order, or a * null pointer if 'node' is the last node in + * the 'hmap' slice. + * + */ +static inline struct hmap_node * +parallel_hmap_next(const struct hmap *hmap, + const struct hmap_node *node, ssize_t pool_size) +{ + return (node->next + ? node->next + : parallel_hmap_next__(hmap, + (node->hash & hmap->mask) + pool_size, pool_size)); +} + +static inline void post_completed_work(struct worker_control *control) +{ + atomic_thread_fence(memory_order_release); + atomic_store_relaxed(&control->finished, true); + sem_post(control->done); +} + +static inline void wait_for_work(struct worker_control *control) +{ + int ret; + + do { + ret = sem_wait(control->fire); + } while ((ret == -1) && (errno == EINTR)); + atomic_thread_fence(memory_order_acquire); + ovs_assert(ret == 0); +} +static inline void wait_for_work_completion(struct worker_pool *pool) +{ + int ret; + + do { + ret = sem_wait(pool->done); + } while ((ret == -1) && (errno == EINTR)); + ovs_assert(ret == 0); +} + + +/* Hash per-row locking support - to be used only in conjunction + * with fast hash inserts. Normal hash inserts may resize the hash + * rendering the locking invalid. + */ + +struct hashrow_locks { + ssize_t mask; + struct ovs_mutex *row_locks; +}; + +/* Update an hash row locks structure to match the current hash size */ + +void ovn_update_hashrow_locks(struct hmap *lflows, struct hashrow_locks *hrl); + +/* Lock a hash row */ + +static inline void lock_hash_row(struct hashrow_locks *hrl, uint32_t hash) +{ + ovs_mutex_lock(&hrl->row_locks[hash % hrl->mask]); +} + +/* Unlock a hash row */ + +static inline void unlock_hash_row(struct hashrow_locks *hrl, uint32_t hash) +{ + ovs_mutex_unlock(&hrl->row_locks[hash % hrl->mask]); +} +/* Init the row locks structure */ + +static inline void init_hash_row_locks(struct hashrow_locks *hrl) +{ + hrl->mask = 0; + hrl->row_locks = NULL; +} + +bool ovn_can_parallelize_hashes(bool force_parallel); + +/* Use the OVN library functions for stuff which OVS has not defined + * If OVS has defined these, they will still compile using the OVN + * local names, but will be dropped by the linker in favour of the OVS + * supplied functions. + */ + +#define update_hashrow_locks(lflows, hrl) ovn_update_hashrow_locks(lflows, hrl) + +#define can_parallelize_hashes(force) ovn_can_parallelize_hashes(force) + +#define stop_parallel_processing() ovn_stop_parallel_processing() + +#define add_worker_pool(start) ovn_add_worker_pool(start) + +#define fast_hmap_size_for(hmap, size) ovn_fast_hmap_size_for(hmap, size) + +#define fast_hmap_init(hmap, size) ovn_fast_hmap_init(hmap, size) + +#define fast_hmap_merge(dest, inc) ovn_fast_hmap_merge(dest, inc) + +#define hmap_merge(dest, inc) ovn_hmap_merge(dest, inc) + +#define ovn_run_pool(pool) ovn_run_pool(pool) + +#define run_pool_hash(pool, result, result_frags) \ + ovn_run_pool_hash(pool, result, result_frags) + +#define run_pool_list(pool, result, result_frags) \ + ovn_run_pool_list(pool, result, result_frags) + +#define run_pool_callback(pool, fin_result, result_frags, helper_func) \ + ovn_run_pool_callback(pool, fin_result, result_frags, helper_func) + + + +#ifdef __clang__ +#pragma clang diagnostic pop +#endif + +#endif + +#ifdef __cplusplus +} +#endif + + +#endif /* lib/fasthmap.h */ diff --git a/ovs b/ovs index ac09cbfcb..50e5523b9 160000 --- a/ovs +++ b/ovs @@ -1 +1 @@ -Subproject commit ac09cbfcb70ac6f443f039d5934448bd80f74493 +Subproject commit 50e5523b9b2b154e5fafc5acdcdec85e9cc5a330 From patchwork Tue Mar 30 09:16:46 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anton Ivanov X-Patchwork-Id: 1459962 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=smtp3.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4F8kNj0hkqz9sVq for ; Tue, 30 Mar 2021 20:17:09 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id D519C60845; Tue, 30 Mar 2021 09:17:05 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Ic1x94wM07AK; Tue, 30 Mar 2021 09:17:04 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp3.osuosl.org (Postfix) with ESMTP id 4381E60822; Tue, 30 Mar 2021 09:17:03 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id C17C2C0015; Tue, 30 Mar 2021 09:17:01 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1BD02C000C for ; Tue, 30 Mar 2021 09:17:00 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id F0E7140407 for ; Tue, 30 Mar 2021 09:16:59 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6SIbt_2Gqd7R for ; Tue, 30 Mar 2021 09:16:58 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from www.kot-begemot.co.uk (ivanoab7.miniserver.com [37.128.132.42]) by smtp4.osuosl.org (Postfix) with ESMTPS id 395A0403FE for ; Tue, 30 Mar 2021 09:16:58 +0000 (UTC) Received: from tun252.jain.kot-begemot.co.uk ([192.168.18.6] helo=jain.kot-begemot.co.uk) by www.kot-begemot.co.uk with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lRAUa-00017X-9Q; Tue, 30 Mar 2021 09:16:56 +0000 Received: from jain.kot-begemot.co.uk ([192.168.3.3]) by jain.kot-begemot.co.uk with esmtp (Exim 4.92) (envelope-from ) id 1lRAUW-0006Ng-QX; Tue, 30 Mar 2021 10:16:54 +0100 From: anton.ivanov@cambridgegreys.com To: ovs-dev@openvswitch.org Date: Tue, 30 Mar 2021 10:16:46 +0100 Message-Id: <20210330091647.24470-2-anton.ivanov@cambridgegreys.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330091647.24470-1-anton.ivanov@cambridgegreys.com> References: <20210330091647.24470-1-anton.ivanov@cambridgegreys.com> MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett Cc: i.maximets@ovn.org, Anton Ivanov Subject: [ovs-dev] [OVN Patch v16 2/3] ovn-northd: Introduce parallel lflow build 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: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" From: Anton Ivanov Datapaths, ports, igmp groups and load balancers can now be iterated over in parallel in order to speed up the lflow generation. This decreases the time needed to generate the logical flows by a factor of 4+ on a 6 core/12 thread CPU without datapath groups - from 0.8-1 microseconds per flow down to 0.2-0.3 microseconds per flow on average. The decrease in time to compute lflows with datapath groups enabled is ~2 times for the same hardware - from an average of 2.4 microseconds per flow to 1.2 microseconds per flow. Tested for on an 8 node, 400 pod K8 simulation resulting in > 6K flows. Signed-off-by: Anton Ivanov --- northd/ovn-northd.c | 363 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 301 insertions(+), 62 deletions(-) diff --git a/northd/ovn-northd.c b/northd/ovn-northd.c index 57df62b92..eb5cbf832 100644 --- a/northd/ovn-northd.c +++ b/northd/ovn-northd.c @@ -39,6 +39,7 @@ #include "lib/ovn-util.h" #include "lib/lb.h" #include "memory.h" +#include "lib/ovn-parallel-hmap.h" #include "ovn/actions.h" #include "ovn/features.h" #include "ovn/logical-fields.h" @@ -539,10 +540,10 @@ struct mcast_switch_info { * be received for queries that were sent out. */ - uint32_t active_v4_flows; /* Current number of active IPv4 multicast + atomic_uint64_t active_v4_flows; /* Current number of active IPv4 multicast * flows. */ - uint32_t active_v6_flows; /* Current number of active IPv6 multicast + atomic_uint64_t active_v6_flows; /* Current number of active IPv6 multicast * flows. */ }; @@ -1001,8 +1002,8 @@ init_mcast_info_for_switch_datapath(struct ovn_datapath *od) smap_get_ullong(&od->nbs->other_config, "mcast_query_max_response", OVN_MCAST_DEFAULT_QUERY_MAX_RESPONSE_S); - mcast_sw_info->active_v4_flows = 0; - mcast_sw_info->active_v6_flows = 0; + mcast_sw_info->active_v4_flows = ATOMIC_VAR_INIT(0); + mcast_sw_info->active_v6_flows = ATOMIC_VAR_INIT(0); } static void @@ -4067,6 +4068,34 @@ ovn_lflow_init(struct ovn_lflow *lflow, struct ovn_datapath *od, /* If this option is 'true' northd will combine logical flows that differ by * logical datapath only by creating a datapath group. */ static bool use_logical_dp_groups = false; +static bool use_parallel_build = true; + +static struct hashrow_locks lflow_locks; + +/* Adds a row with the specified contents to the Logical_Flow table. + * Version to use when locking is required. + */ +static void +do_ovn_lflow_add(struct hmap *lflow_map, bool shared, + struct ovn_datapath *od, + uint32_t hash, struct ovn_lflow *lflow) +{ + + struct ovn_lflow *old_lflow; + + if (shared && use_logical_dp_groups) { + old_lflow = ovn_lflow_find_by_lflow(lflow_map, lflow, hash); + if (old_lflow) { + ovn_lflow_destroy(NULL, lflow); + hmapx_add(&old_lflow->od_group, od); + return; + } + } + + hmapx_add(&lflow->od_group, od); + hmap_insert_fast(lflow_map, &lflow->hmap_node, hash); +} + /* Adds a row with the specified contents to the Logical_Flow table. */ static void @@ -4077,7 +4106,7 @@ ovn_lflow_add_at(struct hmap *lflow_map, struct ovn_datapath *od, { ovs_assert(ovn_stage_to_datapath_type(stage) == ovn_datapath_get_type(od)); - struct ovn_lflow *old_lflow, *lflow; + struct ovn_lflow *lflow; uint32_t hash; lflow = xmalloc(sizeof *lflow); @@ -4089,17 +4118,14 @@ ovn_lflow_add_at(struct hmap *lflow_map, struct ovn_datapath *od, ovn_lflow_hint(stage_hint), where); hash = ovn_lflow_hash(lflow); - if (shared && use_logical_dp_groups) { - old_lflow = ovn_lflow_find_by_lflow(lflow_map, lflow, hash); - if (old_lflow) { - ovn_lflow_destroy(NULL, lflow); - hmapx_add(&old_lflow->od_group, od); - return; - } - } - hmapx_add(&lflow->od_group, od); - hmap_insert(lflow_map, &lflow->hmap_node, hash); + if (use_logical_dp_groups && use_parallel_build) { + lock_hash_row(&lflow_locks, hash); + do_ovn_lflow_add(lflow_map, shared, od, hash, lflow); + unlock_hash_row(&lflow_locks, hash); + } else { + do_ovn_lflow_add(lflow_map, shared, od, hash, lflow); + } } /* Adds a row with the specified contents to the Logical_Flow table. */ @@ -7285,6 +7311,8 @@ build_lswitch_ip_mcast_igmp_mld(struct ovn_igmp_group *igmp_group, struct ds *actions, struct ds *match) { + uint64_t dummy; + if (igmp_group->datapath) { ds_clear(match); @@ -7303,10 +7331,13 @@ build_lswitch_ip_mcast_igmp_mld(struct ovn_igmp_group *igmp_group, return; } - if (mcast_sw_info->active_v4_flows >= mcast_sw_info->table_size) { + if (atomic_compare_exchange_strong( + &mcast_sw_info->active_v4_flows, + &mcast_sw_info->table_size, + mcast_sw_info->table_size)) { return; } - mcast_sw_info->active_v4_flows++; + atomic_add(&mcast_sw_info->active_v4_flows, 1, &dummy); ds_put_format(match, "eth.mcast && ip4 && ip4.dst == %s ", igmp_group->mcgroup.name); } else { @@ -7316,10 +7347,13 @@ build_lswitch_ip_mcast_igmp_mld(struct ovn_igmp_group *igmp_group, if (ipv6_is_all_hosts(&igmp_group->address)) { return; } - if (mcast_sw_info->active_v6_flows >= mcast_sw_info->table_size) { + if (atomic_compare_exchange_strong( + &mcast_sw_info->active_v6_flows, + &mcast_sw_info->table_size, + mcast_sw_info->table_size)) { return; } - mcast_sw_info->active_v6_flows++; + atomic_add(&mcast_sw_info->active_v6_flows, 1, &dummy); ds_put_format(match, "eth.mcast && ip6 && ip6.dst == %s ", igmp_group->mcgroup.name); } @@ -7347,6 +7381,8 @@ build_lswitch_ip_mcast_igmp_mld(struct ovn_igmp_group *igmp_group, } } +static struct ovs_mutex mcgroup_mutex = OVS_MUTEX_INITIALIZER; + /* Ingress table 19: Destination lookup, unicast handling (priority 50), */ static void build_lswitch_ip_unicast_lookup(struct ovn_port *op, @@ -7385,7 +7421,9 @@ build_lswitch_ip_unicast_lookup(struct ovn_port *op, &op->nbsp->header_); } else if (!strcmp(op->nbsp->addresses[i], "unknown")) { if (lsp_is_enabled(op->nbsp)) { + ovs_mutex_lock(&mcgroup_mutex); ovn_multicast_add(mcgroups, &mc_unknown, op); + ovs_mutex_unlock(&mcgroup_mutex); op->od->has_unknown = true; } } else if (is_dynamic_lsp_address(op->nbsp->addresses[i])) { @@ -7947,6 +7985,8 @@ route_hash(struct parsed_route *route) (uint32_t)route->plen); } +static struct ovs_mutex bfd_lock = OVS_MUTEX_INITIALIZER; + /* Parse and validate the route. Return the parsed route if successful. * Otherwise return NULL. */ static struct parsed_route * @@ -7999,6 +8039,7 @@ parsed_routes_add(struct ovs_list *routes, bfd_e = bfd_port_lookup(bfd_connections, nb_bt->logical_port, nb_bt->dst_ip); + ovs_mutex_lock(&bfd_lock); if (bfd_e) { bfd_e->ref = true; } @@ -8008,8 +8049,10 @@ parsed_routes_add(struct ovs_list *routes, } if (!strcmp(nb_bt->status, "down")) { + ovs_mutex_unlock(&bfd_lock); return NULL; } + ovs_mutex_unlock(&bfd_lock); } struct parsed_route *pr = xzalloc(sizeof *pr); @@ -11770,7 +11813,9 @@ build_lswitch_and_lrouter_iterate_by_od(struct ovn_datapath *od, build_lswitch_arp_nd_responder_default(od, lsi->lflows); build_lswitch_dns_lookup_and_response(od, lsi->lflows); build_lswitch_dhcp_and_dns_defaults(od, lsi->lflows); + build_lswitch_destination_lookup_bmcast(od, lsi->lflows, &lsi->actions); + build_lswitch_output_port_sec_od(od, lsi->lflows); /* Build Logical Router Flows. */ @@ -11799,6 +11844,7 @@ build_lswitch_and_lrouter_iterate_by_od(struct ovn_datapath *od, /* Helper function to combine all lflow generation which is iterated by port. */ + static void build_lswitch_and_lrouter_iterate_by_op(struct ovn_port *op, struct lswitch_flow_build_info *lsi) @@ -11814,7 +11860,7 @@ build_lswitch_and_lrouter_iterate_by_op(struct ovn_port *op, lsi->ports, &lsi->actions, &lsi->match); - build_lswitch_dhcp_options_and_response(op,lsi->lflows); + build_lswitch_dhcp_options_and_response(op, lsi->lflows); build_lswitch_external_port(op, lsi->lflows); build_lswitch_ip_unicast_lookup(op, lsi->lflows, lsi->mcgroups, &lsi->actions, &lsi->match); @@ -11842,6 +11888,124 @@ build_lswitch_and_lrouter_iterate_by_op(struct ovn_port *op, &lsi->actions); } +struct lflows_thread_pool { + struct worker_pool *pool; +}; + + +static void *build_lflows_thread(void *arg) +{ + struct worker_control *control = (struct worker_control *) arg; + struct lflows_thread_pool *workload; + struct lswitch_flow_build_info *lsi; + + struct ovn_datapath *od; + struct ovn_port *op; + struct ovn_northd_lb *lb; + struct ovn_igmp_group *igmp_group; + int bnum; + + while (!stop_parallel_processing()) { + wait_for_work(control); + workload = (struct lflows_thread_pool *) control->workload; + lsi = (struct lswitch_flow_build_info *) control->data; + if (stop_parallel_processing()) { + return NULL; + } + if (lsi && workload) { + /* Iterate over bucket ThreadID, ThreadID+size, ... */ + for (bnum = control->id; + bnum <= lsi->datapaths->mask; + bnum += workload->pool->size) + { + HMAP_FOR_EACH_IN_PARALLEL (od, key_node, bnum, lsi->datapaths) { + if (stop_parallel_processing()) { + return NULL; + } + build_lswitch_and_lrouter_iterate_by_od(od, lsi); + } + } + for (bnum = control->id; + bnum <= lsi->ports->mask; + bnum += workload->pool->size) + { + HMAP_FOR_EACH_IN_PARALLEL (op, key_node, bnum, lsi->ports) { + if (stop_parallel_processing()) { + return NULL; + } + build_lswitch_and_lrouter_iterate_by_op(op, lsi); + } + } + for (bnum = control->id; + bnum <= lsi->lbs->mask; + bnum += workload->pool->size) + { + HMAP_FOR_EACH_IN_PARALLEL (lb, hmap_node, bnum, lsi->lbs) { + if (stop_parallel_processing()) { + return NULL; + } + build_lswitch_arp_nd_service_monitor(lb, lsi->lflows, + &lsi->match, + &lsi->actions); + } + } + for (bnum = control->id; + bnum <= lsi->igmp_groups->mask; + bnum += workload->pool->size) + { + HMAP_FOR_EACH_IN_PARALLEL ( + igmp_group, hmap_node, bnum, lsi->igmp_groups) { + if (stop_parallel_processing()) { + return NULL; + } + build_lswitch_ip_mcast_igmp_mld(igmp_group, lsi->lflows, + &lsi->match, + &lsi->actions); + } + } + } + post_completed_work(control); + } + return NULL; +} + +static bool pool_init_done = false; +static struct lflows_thread_pool *build_lflows_pool = NULL; + +static void init_lflows_thread_pool(void) +{ + int index; + + if (!pool_init_done) { + struct worker_pool *pool = add_worker_pool(build_lflows_thread); + pool_init_done = true; + if (pool) { + build_lflows_pool = xmalloc(sizeof(*build_lflows_pool)); + build_lflows_pool->pool = pool; + for (index = 0; index < build_lflows_pool->pool->size; index++) { + build_lflows_pool->pool->controls[index].workload = + build_lflows_pool; + } + } + } +} + +/* TODO: replace hard cutoffs by configurable via commands. These are + * temporary defines to determine single-thread to multi-thread processing + * cutoff. + * Setting to 1 forces "all parallel" lflow build. + */ + +static void +noop_callback(struct worker_pool *pool OVS_UNUSED, + void *fin_result OVS_UNUSED, + void *result_frags OVS_UNUSED, + int index OVS_UNUSED) +{ + /* Do nothing */ +} + + static void build_lswitch_and_lrouter_flows(struct hmap *datapaths, struct hmap *ports, struct hmap *port_groups, struct hmap *lflows, @@ -11850,53 +12014,114 @@ build_lswitch_and_lrouter_flows(struct hmap *datapaths, struct hmap *ports, struct shash *meter_groups, struct hmap *lbs, struct hmap *bfd_connections) { - struct ovn_datapath *od; - struct ovn_port *op; - struct ovn_northd_lb *lb; - struct ovn_igmp_group *igmp_group; char *svc_check_match = xasprintf("eth.dst == %s", svc_monitor_mac); - struct lswitch_flow_build_info lsi = { - .datapaths = datapaths, - .ports = ports, - .port_groups = port_groups, - .lflows = lflows, - .mcgroups = mcgroups, - .igmp_groups = igmp_groups, - .meter_groups = meter_groups, - .lbs = lbs, - .bfd_connections = bfd_connections, - .svc_check_match = svc_check_match, - .match = DS_EMPTY_INITIALIZER, - .actions = DS_EMPTY_INITIALIZER, - }; - - /* Combined build - all lflow generation from lswitch and lrouter - * will move here and will be reogranized by iterator type. - */ - HMAP_FOR_EACH (od, key_node, datapaths) { - build_lswitch_and_lrouter_iterate_by_od(od, &lsi); - } - HMAP_FOR_EACH (op, key_node, ports) { - build_lswitch_and_lrouter_iterate_by_op(op, &lsi); - } - HMAP_FOR_EACH (lb, hmap_node, lbs) { - build_lswitch_arp_nd_service_monitor(lb, lsi.lflows, - &lsi.actions, - &lsi.match); - } - HMAP_FOR_EACH (igmp_group, hmap_node, igmp_groups) { - build_lswitch_ip_mcast_igmp_mld(igmp_group, - lsi.lflows, - &lsi.actions, - &lsi.match); + if (use_parallel_build) { + init_lflows_thread_pool(); + if (!can_parallelize_hashes(false)) { + use_parallel_build = false; + } } - free(svc_check_match); - ds_destroy(&lsi.match); - ds_destroy(&lsi.actions); + if (use_parallel_build) { + struct hmap *lflow_segs; + struct lswitch_flow_build_info *lsiv; + int index; + + lsiv = xcalloc(sizeof(*lsiv), build_lflows_pool->pool->size); + if (use_logical_dp_groups) { + lflow_segs = NULL; + } else { + lflow_segs = xcalloc(sizeof(*lflow_segs), build_lflows_pool->pool->size); + } + + /* Set up "work chunks" for each thread to work on. */ + + for (index = 0; index < build_lflows_pool->pool->size; index++) { + if (use_logical_dp_groups) { + /* if dp_groups are in use we lock a shared lflows hash + * on a per-bucket level instead of merging hash frags */ + lsiv[index].lflows = lflows; + } else { + fast_hmap_init(&lflow_segs[index], lflows->mask); + lsiv[index].lflows = &lflow_segs[index]; + } + lsiv[index].datapaths = datapaths; + lsiv[index].ports = ports; + lsiv[index].port_groups = port_groups; + lsiv[index].mcgroups = mcgroups; + lsiv[index].igmp_groups = igmp_groups; + lsiv[index].meter_groups = meter_groups; + lsiv[index].lbs = lbs; + lsiv[index].bfd_connections = bfd_connections; + lsiv[index].svc_check_match = svc_check_match; + ds_init(&lsiv[index].match); + ds_init(&lsiv[index].actions); + + build_lflows_pool->pool->controls[index].data = &lsiv[index]; + } + + /* Run thread pool. */ + if (use_logical_dp_groups) { + run_pool_callback(build_lflows_pool->pool, NULL, NULL, noop_callback); + } else { + run_pool_hash(build_lflows_pool->pool, lflows, lflow_segs); + } + + for (index = 0; index < build_lflows_pool->pool->size; index++) { + ds_destroy(&lsiv[index].match); + ds_destroy(&lsiv[index].actions); + } + free(lflow_segs); + free(lsiv); + } else { + struct ovn_datapath *od; + struct ovn_port *op; + struct ovn_northd_lb *lb; + struct ovn_igmp_group *igmp_group; + struct lswitch_flow_build_info lsi = { + .datapaths = datapaths, + .ports = ports, + .port_groups = port_groups, + .lflows = lflows, + .mcgroups = mcgroups, + .igmp_groups = igmp_groups, + .meter_groups = meter_groups, + .lbs = lbs, + .bfd_connections = bfd_connections, + .svc_check_match = svc_check_match, + .match = DS_EMPTY_INITIALIZER, + .actions = DS_EMPTY_INITIALIZER, + }; + + /* Combined build - all lflow generation from lswitch and lrouter + * will move here and will be reogranized by iterator type. + */ + HMAP_FOR_EACH (od, key_node, datapaths) { + build_lswitch_and_lrouter_iterate_by_od(od, &lsi); + } + HMAP_FOR_EACH (op, key_node, ports) { + build_lswitch_and_lrouter_iterate_by_op(op, &lsi); + } + HMAP_FOR_EACH (lb, hmap_node, lbs) { + build_lswitch_arp_nd_service_monitor(lb, lsi.lflows, + &lsi.actions, + &lsi.match); + } + HMAP_FOR_EACH (igmp_group, hmap_node, igmp_groups) { + build_lswitch_ip_mcast_igmp_mld(igmp_group, + lsi.lflows, + &lsi.actions, + &lsi.match); + } + + ds_destroy(&lsi.match); + ds_destroy(&lsi.actions); + } + + free(svc_check_match); build_lswitch_flows(datapaths, lflows); } @@ -11967,6 +12192,8 @@ ovn_sb_set_lflow_logical_dp_group( sbrec_logical_flow_set_logical_dp_group(sbflow, dpg->dp_group); } +static ssize_t max_seen_lflow_size = 128; + /* Updates the Logical_Flow and Multicast_Group tables in the OVN_SB database, * constructing their contents based on the OVN_NB database. */ static void @@ -11976,13 +12203,21 @@ build_lflows(struct northd_context *ctx, struct hmap *datapaths, struct shash *meter_groups, struct hmap *lbs, struct hmap *bfd_connections) { - struct hmap lflows = HMAP_INITIALIZER(&lflows); + struct hmap lflows; + fast_hmap_size_for(&lflows, max_seen_lflow_size); + if (use_parallel_build) { + update_hashrow_locks(&lflows, &lflow_locks); + } build_lswitch_and_lrouter_flows(datapaths, ports, port_groups, &lflows, mcgroups, igmp_groups, meter_groups, lbs, bfd_connections); + if (hmap_count(&lflows) > max_seen_lflow_size) { + max_seen_lflow_size = hmap_count(&lflows); + } + /* Collecting all unique datapath groups. */ struct hmap dp_groups = HMAP_INITIALIZER(&dp_groups); struct hmapx single_dp_lflows = HMAPX_INITIALIZER(&single_dp_lflows); @@ -13784,6 +14019,9 @@ main(int argc, char *argv[]) daemonize_complete(); + init_hash_row_locks(&lflow_locks); + use_parallel_build = can_parallelize_hashes(false); + /* We want to detect (almost) all changes to the ovn-nb db. */ struct ovsdb_idl_loop ovnnb_idl_loop = OVSDB_IDL_LOOP_INITIALIZER( ovsdb_idl_create(ovnnb_db, &nbrec_idl_class, true, true)); @@ -14052,6 +14290,7 @@ main(int argc, char *argv[]) exiting = false; state.had_lock = false; state.paused = false; + while (!exiting) { memory_run(); if (memory_should_report()) { From patchwork Tue Mar 30 09:16:47 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anton Ivanov X-Patchwork-Id: 1459961 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.133; helo=smtp2.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4F8kNd3Ngxz9sVt for ; Tue, 30 Mar 2021 20:17:05 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 9894340188; Tue, 30 Mar 2021 09:17:02 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id zJ69FjrRmzB6; Tue, 30 Mar 2021 09:17:01 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp2.osuosl.org (Postfix) with ESMTP id DE0F8400AB; Tue, 30 Mar 2021 09:17:00 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id C35FEC000C; Tue, 30 Mar 2021 09:17:00 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 03F52C000A for ; Tue, 30 Mar 2021 09:17:00 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id E761F83DC1 for ; Tue, 30 Mar 2021 09:16:59 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Mc5BZo-BCHOb for ; Tue, 30 Mar 2021 09:16:59 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from www.kot-begemot.co.uk (ivanoab7.miniserver.com [37.128.132.42]) by smtp1.osuosl.org (Postfix) with ESMTPS id 57F8483CEE for ; Tue, 30 Mar 2021 09:16:59 +0000 (UTC) Received: from tun252.jain.kot-begemot.co.uk ([192.168.18.6] helo=jain.kot-begemot.co.uk) by www.kot-begemot.co.uk with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lRAUb-00017e-HQ; Tue, 30 Mar 2021 09:16:57 +0000 Received: from jain.kot-begemot.co.uk ([192.168.3.3]) by jain.kot-begemot.co.uk with esmtp (Exim 4.92) (envelope-from ) id 1lRAUY-0006Ng-S7; Tue, 30 Mar 2021 10:16:56 +0100 From: anton.ivanov@cambridgegreys.com To: ovs-dev@openvswitch.org Date: Tue, 30 Mar 2021 10:16:47 +0100 Message-Id: <20210330091647.24470-3-anton.ivanov@cambridgegreys.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330091647.24470-1-anton.ivanov@cambridgegreys.com> References: <20210330091647.24470-1-anton.ivanov@cambridgegreys.com> MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett Cc: i.maximets@ovn.org, Anton Ivanov Subject: [ovs-dev] [OVN Patch v16 3/3] ovn-northd: Add configuration option for parallel lflow build 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: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" From: Anton Ivanov Signed-off-by: Anton Ivanov --- northd/ovn-northd.c | 3 +++ ovn-nb.xml | 13 +++++++++++++ 2 files changed, 16 insertions(+) diff --git a/northd/ovn-northd.c b/northd/ovn-northd.c index eb5cbf832..e2232c53a 100644 --- a/northd/ovn-northd.c +++ b/northd/ovn-northd.c @@ -13207,6 +13207,9 @@ ovnnb_db_run(struct northd_context *ctx, northd_probe_interval_nb = get_probe_interval(ovnnb_db, nb); northd_probe_interval_sb = get_probe_interval(ovnsb_db, nb); + use_parallel_build = smap_get_bool(&nb->options, + "use_parallel_build", false) && + ovn_can_parallelize_hashes(false); use_logical_dp_groups = smap_get_bool(&nb->options, "use_logical_dp_groups", false); /* deprecated, use --event instead */ diff --git a/ovn-nb.xml b/ovn-nb.xml index b0a4adffe..98608a475 100644 --- a/ovn-nb.xml +++ b/ovn-nb.xml @@ -213,6 +213,19 @@ The default value is false.

+ +

+ If set to true, ovn-northd will attempt + to compute logical flows in parallel. +

+

+ Parallel computation is enabled only if the system has 4 or more + cores/threads available to be used by ovn-northd. +

+

+ The default value is false. +

+