On 14/01/2021 11:54, Ilya Maximets wrote:
On 1/11/21 10:51 AM, [email protected] wrote:
From: Anton Ivanov <[email protected]>
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 <[email protected]>
Hi.
Not a full review. Just a couple of first glance comments inline.
Best regards, Ilya Maximets.
---
lib/automake.mk | 2 +
lib/fasthmap.c | 281 ++++++++++++++++++++++++++++++++++++++++++++++++
lib/fasthmap.h | 206 +++++++++++++++++++++++++++++++++++
3 files changed, 489 insertions(+)
create mode 100644 lib/fasthmap.c
create mode 100644 lib/fasthmap.h
diff --git a/lib/automake.mk b/lib/automake.mk
index 250c7aefa..d7e4b20cf 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/fasthmap.h \
+ lib/fasthmap.c \
lib/ip-mcast-index.c \
lib/ip-mcast-index.h \
lib/mcast-group-index.c \
diff --git a/lib/fasthmap.c b/lib/fasthmap.c
new file mode 100644
index 000000000..3096c90d3
--- /dev/null
+++ b/lib/fasthmap.c
@@ -0,0 +1,281 @@
+/*
+ * 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 <config.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <semaphore.h>
+#include "fatal-signal.h"
+#include "util.h"
+#include "openvswitch/vlog.h"
+#include "openvswitch/hmap.h"
+#include "openvswitch/thread.h"
+#include "fasthmap.h"
+#include "ovs-atomic.h"
+#include "ovs-thread.h"
+#include "ovs-numa.h"
+
+VLOG_DEFINE_THIS_MODULE(fasthmap);
+
+
+static bool worker_pool_setup = false;
+static bool workers_must_exit = false;
This must be atomic as it constantly used and updated frm different
threads without the lock.
There is a fence after the only place where must_exit is set which happens only
in the exit hook.
It can be replaced by an atomic, but that means using atomics to check it on
every iteration.
The fence does the same job with less code and less memory access/order
requirements in normal operation. It should be made stronger though - acq_rel.
worker_pool_setup is accessed only under mutex. The mutex is locked/unlocked
before access in ovn_add_worker_pool() and there is no other access.
I will amend the fence and move the setting of _setup into the calling function
so it is clear that is checked and set under mutex.
+static bool can_parallelize = 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 void worker_pool_hook(void *aux OVS_UNUSED) {
+ int i;
+ static struct worker_pool *pool;
+ workers_must_exit = true; /* all workers must honour this flag */
+ atomic_thread_fence(memory_order_release);
What is the purpose of these thread fences here and there?
To ensure that the main thread which is waiting on the workers to complete sees
the correct data.
The principle of operation is:
1. Main thread triggers all workers to run on "data descriptors" by posting
semaphores. Each data descriptor contains pointers to data to process and pointer(s) to
results. In this case datapaths, ports, igmp_groups, etc.
2. Under normal circumstances there is NO RESULT LOCKING because there is no
need to do any. Each worker thread chews on its data portion (f.e. slice of a
hash in this case) and writes to its own result portion - a per-thread lflow
hash. Once the thread completes it signals the main thread via a semaphore.
3. The main thread walks the data descriptor list and merges (using fast
brute-force hash merge) the completed per-thread lflow hashes into the final
lflow hash. In order to do that it needs to be reading the correct data from
memory. If there are worker threads still busy, it goes to sleep until they
semaphor it.
That is the intended mode of operation.
With datapath groups this no longer works - the data is by necessity contended
and lflows become a variable in the transform. There, unfortunately, some
locking is needed and the datapath group version uses the same data and same
results everywhere as well as some locking when checking/adding lflows.
The results from this are obvious.
The average speedup on a 6 core/12 thread system for without datapath groups is
from 1.2 microseconds per lflow to <0.3 microseconds per lflow ~ x4 or more.
With datapath groups the speedup is only from 2 microseconds per flow to 1 ~ x2
All of them has 'release' memory ordering semantics, but there
is no any code that uses 'acquire'. If you're trying to ensure
ordering within current thread, this must be documented.
Basically, please, add comments to all thread fences you're using.
It's not trivial to figure out why they are there.
They should be really acq_rel. My mistake for putting _release only.
Alternatively, I can do acquire in the main thread, but there is no benefit
from that compared to an acq_rel mfence in the workers upon completion.
--
Anton R. Ivanov
Cambridgegreys Limited. Registered in England. Company Number 10273661
https://www.cambridgegreys.com/
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
