From patchwork Wed Feb 10 15:33:57 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gaetan Rivet X-Patchwork-Id: 1439080 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.138; helo=whitealder.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=u256.net header.i=@u256.net header.a=rsa-sha256 header.s=fm1 header.b=Ffc+NyGX; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=messagingengine.com header.i=@messagingengine.com header.a=rsa-sha256 header.s=fm2 header.b=oOuecTaY; dkim-atps=neutral Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4DbP481k5Nz9sB4 for ; Thu, 11 Feb 2021 02:36:08 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id B2E1586D8D; Wed, 10 Feb 2021 15:36:06 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ulfOXhW2Hur5; Wed, 10 Feb 2021 15:35:54 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by whitealder.osuosl.org (Postfix) with ESMTP id 241A287070; Wed, 10 Feb 2021 15:34:36 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id DC497C1E73; Wed, 10 Feb 2021 15:34:35 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7E677C1E70 for ; Wed, 10 Feb 2021 15:34:31 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 623B286FA6 for ; Wed, 10 Feb 2021 15:34:31 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id x8AGtsoXkK41 for ; Wed, 10 Feb 2021 15:34:17 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from wnew4-smtp.messagingengine.com (wnew4-smtp.messagingengine.com [64.147.123.18]) by whitealder.osuosl.org (Postfix) with ESMTPS id A79CF86B16 for ; Wed, 10 Feb 2021 15:34:17 +0000 (UTC) Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailnew.west.internal (Postfix) with ESMTP id C966DA1E; Wed, 10 Feb 2021 10:34:16 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute3.internal (MEProxy); Wed, 10 Feb 2021 10:34:17 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=u256.net; h=from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; s=fm1; bh=UI3SZ4owHN8FV vJ4Z+b6wrgq4PQsYs8CzWujrVb2k9g=; b=Ffc+NyGXxbECWkSLZSc+UHlPrzC64 LUJuzJN0H8LODU6bYlFcA02IJWgEttf2RY2IJU9+uGO+75vgSXa0Y6L0zckaDN+K INb+9pyI4tkyhh1SB0J1xmnCnhJCJlbkpufP7eypKmIe/Ryv9QJNmGfmx4sihM62 e8gAfdICIOzwIqBif8xRvWv8JdBHlTljdyV+nVGJxJrxKZmGreSEZdS/Coq9KQfl AeIQu6sZ4uzKa56cFn3glrLplsKG9nvdY7ZDWBLY/vVmM/XvZMu0GVg9EwAzWKlt T0n8NK1+TgtKe9opWcTn81jU2nTHWkdSuBFLmfmDdJW/m+gh+sOn/9p4A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:date:from :in-reply-to:message-id:mime-version:references:subject:to :x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm2; bh=UI3SZ4owHN8FVvJ4Z+b6wrgq4PQsYs8CzWujrVb2k9g=; b=oOuecTaY V2vzyFzF8WVXRac3toFt72TDhpNseTNIbgI2ULJmaiK/0GJApizOKXD+7358HEj4 pPGInDGDEX0zbWYZq3r6edsOmM03XdNIfASQ2YL4MgVAVPIRKOe8OV4V8N6YY0dJ 3qtC/xNGMP+/uK6b3QCnKIggp0ssp58jJbizBcF5Rorzv1uaJNSdAwDiWmtag0xz KwJzmHomnsS9A4CVD/dXH7XuNXLxeMkvIH3iQexKEYQ7X/1NC0O6cHB7MV1588Sy l1nGGOPVioFyhSVJz16njp3RpkhuDh/SP0owCPqO65Q9Q3CZEm0MGQmO9Xqu/WcT AISzxlt8JcFMtg== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrheejgdejkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefhvffufffkofgjfhgggfestdekredtredttdenucfhrhhomhepifgrvghtrghn ucftihhvvghtuceoghhrihhvvgesuhdvheeirdhnvghtqeenucggtffrrghtthgvrhhnpe duhfefieekieeiudetgfehkeeludektdekjeehudehffetieduheeigfekvdelfeenucff ohhmrghinheprghprggthhgvrdhorhhgnecukfhppeekiedrvdehgedrudeigedrudejge enucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehgrhhi vhgvsehuvdehiedrnhgvth X-ME-Proxy: Received: from inocybe.home (lfbn-poi-1-842-174.w86-254.abo.wanadoo.fr [86.254.164.174]) by mail.messagingengine.com (Postfix) with ESMTPA id D4194240064; Wed, 10 Feb 2021 10:34:14 -0500 (EST) From: Gaetan Rivet To: dev@openvswitch.org Date: Wed, 10 Feb 2021 16:33:57 +0100 Message-Id: <6e199c03be14af89cddcd490e08f9dde10a0c5cd.1612968146.git.grive@u256.net> X-Mailer: git-send-email 2.30.0 In-Reply-To: References: MIME-Version: 1.0 Cc: Eli Britstein Subject: [ovs-dev] [PATCH v1 11/23] seq-pool: Module for faster ID generation 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" The current id-pool module is slow to allocate the next valid ID, and can be optimized when restricting some properties of the pool. Those restrictions are: * No ability to add a random ID to the pool. * A new ID is no more the smallest possible ID. It is however guaranteed to be in the range of [base, next_id]. Multiple users of the pool are registered, each with a thread-local cache for better scalability and the next_id is one after the latest ID added to any user cache. The allocation range can be written as: [base, last_alloc + nb-user * cache-size + 1]. * A user should never free an ID that is not allocated. No checks are done and doing so will duplicate the spurious ID. Refcounting or other memory management scheme should be used to ensure an object and its ID are only freed once. This pool is designed to scale reasonably well in multi-thread setup. As it is aimed at being a faster replacement to the current id-pool, a benchmark has been implemented alongside unit tests. The benchmark is composed of 4 rounds: 'new', 'del', 'mix', and 'rnd'. Respectively + 'new': only allocate IDs + 'del': only free IDs + 'mix': allocate, sequential free, then allocate ID. + 'rnd': allocate, random free, allocate ID. Randomized freeing is done by swapping the latest allocated ID with any from the range of currently allocated ID, which is reminiscent of the Fisher-Yates shuffle. This evaluates freeing non-sequential IDs, which is the more natural use-case. For this specific round, the id-pool performance is such that a timeout of 10 seconds is added to the benchmark: $ ./tests/ovstest test-seq-pool benchmark 10000 1 Benchmarking n=10000 on 1 thread. type\thread: 1 Avg seq-pool new: 1 1 ms seq-pool del: 0 0 ms seq-pool mix: 1 1 ms seq-pool rnd: 1 1 ms id-pool new: 0 0 ms id-pool del: 1 1 ms id-pool mix: 1 1 ms id-pool rnd: 1201 1201 ms $ ./tests/ovstest test-seq-pool benchmark 100000 1 Benchmarking n=100000 on 1 thread. type\thread: 1 Avg seq-pool new: 2 2 ms seq-pool del: 5 5 ms seq-pool mix: 5 5 ms seq-pool rnd: 5 5 ms id-pool new: 8 8 ms id-pool del: 5 5 ms id-pool mix: 11 11 ms id-pool rnd: 10000+ ****** ms $ ./tests/ovstest test-seq-pool benchmark 1000000 1 Benchmarking n=1000000 on 1 thread. type\thread: 1 Avg seq-pool new: 23 23 ms seq-pool del: 49 49 ms seq-pool mix: 53 53 ms seq-pool rnd: 53 53 ms id-pool new: 190 190 ms id-pool del: 173 173 ms id-pool mix: 273 273 ms id-pool rnd: 10042+ ****** ms $ ./tests/ovstest test-seq-pool benchmark 1000000 2 Benchmarking n=1000000 on 2 threads. type\thread: 1 2 Avg seq-pool new: 40 39 39 ms seq-pool del: 33 33 33 ms seq-pool mix: 89 91 90 ms seq-pool rnd: 146 151 148 ms id-pool new: 485 485 485 ms id-pool del: 541 542 541 ms id-pool mix: 550 600 575 ms id-pool rnd: 10048+ 10003+ ****** ms $ ./tests/ovstest test-seq-pool benchmark 1000000 4 Benchmarking n=1000000 on 4 threads. type\thread: 1 2 3 4 Avg seq-pool new: 40 39 40 40 39 ms seq-pool del: 24 28 28 30 27 ms seq-pool mix: 60 63 69 69 65 ms seq-pool rnd: 195 197 202 202 199 ms id-pool new: 478 471 482 485 479 ms id-pool del: 474 469 467 474 471 ms id-pool mix: 558 558 611 545 568 ms id-pool rnd: 10121+ 10076+ 10030+ 10167+ ****** ms Signed-off-by: Gaetan Rivet Reviewed-by: Eli Britstein --- lib/automake.mk | 2 + lib/seq-pool.c | 198 +++++++++++++++ lib/seq-pool.h | 66 +++++ tests/automake.mk | 1 + tests/library.at | 5 + tests/test-seq-pool.c | 543 ++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 815 insertions(+) create mode 100644 lib/seq-pool.c create mode 100644 lib/seq-pool.h create mode 100644 tests/test-seq-pool.c diff --git a/lib/automake.mk b/lib/automake.mk index 45948e519..2577c6130 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -295,6 +295,8 @@ lib_libopenvswitch_la_SOURCES = \ lib/sat-math.h \ lib/seq.c \ lib/seq.h \ + lib/seq-pool.c \ + lib/seq-pool.h \ lib/sha1.c \ lib/sha1.h \ lib/shash.c \ diff --git a/lib/seq-pool.c b/lib/seq-pool.c new file mode 100644 index 000000000..4426d11d8 --- /dev/null +++ b/lib/seq-pool.c @@ -0,0 +1,198 @@ +/* + * Copyright (c) 2020 NVIDIA Corporation. + * + * 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 "openvswitch/list.h" +#include "openvswitch/thread.h" +#include "openvswitch/util.h" +#include "ovs-atomic.h" +#include "llring.h" +#include "seq-pool.h" + +#define SEQPOOL_CACHE_SIZE 32 +BUILD_ASSERT_DECL(IS_POW2(SEQPOOL_CACHE_SIZE)); + +struct seq_node { + struct ovs_list list_node; + uint32_t id; +}; + +struct seq_pool { + uint32_t next_id; + struct llring **cache; /* per-user id cache. */ + size_t nb_user; /* Number of user threads. */ + struct ovs_mutex lock; /* Protects free_ids access. */ + struct ovs_list free_ids; /* Set of currently free IDs. */ + uint32_t base; /* IDs in the range of [base, base + n_ids). */ + uint32_t n_ids; /* Total number of ids in the pool. */ +}; + +struct seq_pool * +seq_pool_create(unsigned int nb_user, uint32_t base, uint32_t n_ids) +{ + struct seq_pool *pool; + size_t i; + + ovs_assert(nb_user != 0); + ovs_assert(base <= UINT32_MAX - n_ids); + + pool = xmalloc(sizeof *pool); + + pool->cache = xcalloc(nb_user, sizeof *pool->cache); + for (i = 0; i < nb_user; i++) { + pool->cache[i] = llring_create(SEQPOOL_CACHE_SIZE); + } + pool->nb_user = nb_user; + + pool->next_id = base; + pool->base = base; + pool->n_ids = n_ids; + + ovs_mutex_init(&pool->lock); + ovs_list_init(&pool->free_ids); + + return pool; +} + +void +seq_pool_destroy(struct seq_pool *pool) +{ + struct seq_node *node; + struct seq_node *next; + size_t i; + + if (!pool) { + return; + } + + ovs_mutex_lock(&pool->lock); + LIST_FOR_EACH_SAFE (node, next, list_node, &pool->free_ids) { + free(node); + } + ovs_list_poison(&pool->free_ids); + ovs_mutex_unlock(&pool->lock); + ovs_mutex_destroy(&pool->lock); + + for (i = 0; i < pool->nb_user; i++) { + llring_destroy(pool->cache[i]); + } + free(pool->cache); + + free(pool); +} + +bool +seq_pool_new_id(struct seq_pool *pool, unsigned int uid, uint32_t *id) +{ + struct llring *cache; + struct ovs_list *front; + struct seq_node *node; + + uid %= pool->nb_user; + cache = pool->cache[uid]; + + if (llring_dequeue(cache, id)) { + return true; + } + + ovs_mutex_lock(&pool->lock); + + while (!ovs_list_is_empty(&pool->free_ids)) { + front = ovs_list_front(&pool->free_ids); + node = CONTAINER_OF(front, struct seq_node, list_node); + if (llring_enqueue(cache, node->id)) { + ovs_list_remove(front); + free(node); + } else { + break; + } + } + + while (pool->next_id < pool->base + pool->n_ids) { + if (llring_enqueue(cache, pool->next_id)) { + pool->next_id++; + } else { + break; + } + } + + ovs_mutex_unlock(&pool->lock); + + if (llring_dequeue(cache, id)) { + return true; + } else { + struct llring *c2; + size_t i; + + /* If no ID was available either from shared counter, + * free-list or local cache, steal an ID from another + * user cache. + */ + for (i = 0; i < pool->nb_user; i++) { + if (i == uid) { + continue; + } + c2 = pool->cache[i]; + if (llring_dequeue(c2, id)) { + return true; + } + } + } + + return false; +} + +void +seq_pool_free_id(struct seq_pool *pool, unsigned int uid, uint32_t id) +{ + struct seq_node *nodes[SEQPOOL_CACHE_SIZE + 1]; + struct llring *cache; + uint32_t node_id; + size_t i; + + if (id < pool->base || id >= pool->base + pool->n_ids) { + return; + } + + uid %= pool->nb_user; + cache = pool->cache[uid]; + + if (llring_enqueue(cache, id)) { + return; + } + + /* Flush the cache. */ + for (i = 0; llring_dequeue(cache, &node_id); i++) { + nodes[i] = xmalloc(sizeof *nodes[i]); + nodes[i]->id = node_id; + } + + /* Finish with the last freed node. */ + nodes[i] = xmalloc(sizeof **nodes); + nodes[i]->id = id; + i++; + + if (i < ARRAY_SIZE(nodes)) { + nodes[i] = NULL; + } + + ovs_mutex_lock(&pool->lock); + for (i = 0; i < ARRAY_SIZE(nodes) && nodes[i] != NULL; i++) { + ovs_list_push_back(&pool->free_ids, &nodes[i]->list_node); + } + ovs_mutex_unlock(&pool->lock); +} diff --git a/lib/seq-pool.h b/lib/seq-pool.h new file mode 100644 index 000000000..c992a0988 --- /dev/null +++ b/lib/seq-pool.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2020 NVIDIA Corporation. + * + * 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 SEQ_POOL_H +#define SEQ_POOL_H + +#include +#include +#include + +/* + * Sequential ID pool. + * =================== + * + * Pool of unique 32bits IDs. + * + * Multiple users are registered at initialization. Each user uses a cache + * of ID. When each thread using the pool uses its own user ID, the pool + * scales reasonably for concurrent allocation. + * + * New IDs are always in the range of '[base, next_id]', where 'next_id' is + * in the range of '[last_alloc_ID + nb_user * cache_size + 1]'. + * This means that a new ID is not always the smallest available ID, but it is + * still from a limited range. + * + * Users should ensure that an ID is *never* freed twice. Not doing so will + * have the effect of double-allocating such ID afterward. + * + * Thread-safety + * ============= + * + * APIs are thread safe. + * + * Multiple threads can share the same user ID if necessary, but it can hurt + * performance if threads are not otherwise synchronized. + */ + +struct seq_pool; + +/* nb_user is the number of expected users of the pool, + * in terms of execution threads. */ +struct seq_pool *seq_pool_create(unsigned int nb_user, + uint32_t base, uint32_t n_ids); +void seq_pool_destroy(struct seq_pool *pool); + +/* uid is the thread user-id. It should be within '[0, nb_user['. */ +bool seq_pool_new_id(struct seq_pool *pool, unsigned int uid, uint32_t *id); + +/* uid is the thread user-id. It should be within '[0, nb_user['. + * An allocated ID must *never* be freed twice. + */ +void seq_pool_free_id(struct seq_pool *pool, unsigned int uid, uint32_t id); +#endif /* seq-pool.h */ diff --git a/tests/automake.mk b/tests/automake.mk index d7ae5df90..f34016a24 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -469,6 +469,7 @@ tests_ovstest_SOURCES = \ tests/test-rcu.c \ tests/test-reconnect.c \ tests/test-rstp.c \ + tests/test-seq-pool.c \ tests/test-sflow.c \ tests/test-sha1.c \ tests/test-skiplist.c \ diff --git a/tests/library.at b/tests/library.at index ac24921f8..a312a448f 100644 --- a/tests/library.at +++ b/tests/library.at @@ -259,3 +259,8 @@ AT_SETUP([mpsc-queue module]) AT_CHECK([ovstest test-mpsc-queue check], [0], [.. ]) AT_CLEANUP + +AT_SETUP([seq-pool module]) +AT_CHECK([ovstest test-seq-pool check], [0], [.... +]) +AT_CLEANUP diff --git a/tests/test-seq-pool.c b/tests/test-seq-pool.c new file mode 100644 index 000000000..a1e0d5500 --- /dev/null +++ b/tests/test-seq-pool.c @@ -0,0 +1,543 @@ +/* + * Copyright (c) 2020 NVIDIA Corporation. + * + * 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. + */ + +#undef NDEBUG +#include +#include +#include + +#include + +#include "command-line.h" +#include "id-pool.h" +#include "openvswitch/util.h" +#include "ovs-thread.h" +#include "ovs-rcu.h" +#include "ovstest.h" +#include "random.h" +#include "seq-pool.h" +#include "timeval.h" +#include "util.h" + +#define SEQ_POOL_CACHE_SIZE 32 + +#define N_IDS 100 + +static void +test_seq_pool_alloc_full_range(void) +{ + bool ids[N_IDS]; + struct seq_pool *pool; + size_t i; + + memset(ids, 0, sizeof ids); + pool = seq_pool_create(1, 0, N_IDS); + + for (i = 0; i < N_IDS; i++) { + uint32_t id; + + ovs_assert(seq_pool_new_id(pool, 0, &id)); + /* No double alloc.*/ + ovs_assert(ids[id] == false); + ids[id] = true; + } + + for (i = 0; i < N_IDS; i++) { + ovs_assert(ids[i]); + } + + seq_pool_destroy(pool); + printf("."); +} + +static void +test_seq_pool_alloc_steal(void) +{ + /* N must be less than a pool cache size to force the second user + * to steal from the first. + */ +#define N (SEQ_POOL_CACHE_SIZE / 4) + bool ids[N]; + struct seq_pool *pool; + uint32_t id; + size_t i; + + memset(ids, 0, sizeof ids); + pool = seq_pool_create(2, 0, N); + + /* Fill up user 0 cache. */ + ovs_assert(seq_pool_new_id(pool, 0, &id)); + for (i = 0; i < N - 1; i++) { + /* Check that user 1 can still alloc from user 0 cache. */ + ovs_assert(seq_pool_new_id(pool, 1, &id)); + } + + seq_pool_destroy(pool); + printf("."); +#undef N +} + +static void +test_seq_pool_alloc_monotonic(void) +{ + uint32_t ids[N_IDS]; + struct seq_pool *pool; + size_t i; + + memset(ids, 0, sizeof ids); + pool = seq_pool_create(1, 0, N_IDS); + + for (i = 0; i < N_IDS; i++) { + ovs_assert(seq_pool_new_id(pool, 0, &ids[i])); + ovs_assert(ids[i] == i); + } + + seq_pool_destroy(pool); + printf("."); +} + +static void +test_seq_pool_alloc_under_limit(void) +{ + uint32_t ids[N_IDS]; + unsigned int limit; + struct seq_pool *pool; + size_t i; + + memset(ids, 0, sizeof ids); + pool = seq_pool_create(1, 0, N_IDS); + + for (limit = 1; limit < N_IDS; limit++) { + /* Allocate until arbitrary limit then free allocated ids. */ + for (i = 0; i < limit; i++) { + ovs_assert(seq_pool_new_id(pool, 0, &ids[i])); + } + for (i = 0; i < limit; i++) { + seq_pool_free_id(pool, 0, ids[i]); + } + /* Verify that the N='limit' next allocations are under limit. */ + for (i = 0; i < limit; i++) { + ovs_assert(seq_pool_new_id(pool, 0, &ids[i])); + ovs_assert(ids[i] < limit + SEQ_POOL_CACHE_SIZE); + } + for (i = 0; i < limit; i++) { + seq_pool_free_id(pool, 0, ids[i]); + } + } + + seq_pool_destroy(pool); + printf("."); +} + +static void +run_tests(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + /* Check that all ids can be allocated. */ + test_seq_pool_alloc_full_range(); + /* Check that all ids can be allocated with multiple users. */ + test_seq_pool_alloc_steal(); + /* Check that id allocation is always increasing. */ + test_seq_pool_alloc_monotonic(); + /* Check that id allocation stays under some limit. */ + test_seq_pool_alloc_under_limit(); + printf("\n"); +} + +static uint32_t *ids; +static uint64_t *thread_working_ms; /* Measured work time. */ + +static unsigned int n_threads; +static unsigned int n_ids; + +static struct ovs_barrier barrier; + +#define TIMEOUT_MS (10 * 1000) /* 10 sec timeout */ +static int running_time_ms; +static volatile bool stop = false; + +static int +elapsed(int *start) +{ + return running_time_ms - *start; +} + +static void +swap_u32(uint32_t *a, uint32_t *b) +{ + uint32_t t; + t = *a; + *a = *b; + *b = t; +} + +static void +shuffle(uint32_t *p, size_t n) +{ + for (; n > 1; n--, p++) { + uint32_t *q = &p[random_range(n)]; + swap_u32(p, q); + } +} + +static void +print_result(const char *prefix) +{ + uint64_t avg; + size_t i; + + avg = 0; + for (i = 0; i < n_threads; i++) { + avg += thread_working_ms[i]; + } + avg /= n_threads; + printf("%s: ", prefix); + for (i = 0; i < n_threads; i++) { + if (thread_working_ms[i] >= TIMEOUT_MS) { + printf("%6" PRIu64 "+", thread_working_ms[i]); + } else { + printf(" %6" PRIu64, thread_working_ms[i]); + } + } + if (avg >= TIMEOUT_MS) { + printf(" ****** ms\n"); + } else { + printf(" %6" PRIu64 " ms\n", avg); + } +} + +struct seq_pool_aux { + struct seq_pool *pool; + atomic_uint thread_id; +}; + +static void * +seq_pool_thread(void *aux_) +{ + unsigned int n_ids_per_thread; + struct seq_pool_aux *aux = aux_; + uint32_t *th_ids; + unsigned int tid; + int start; + size_t i; + + atomic_add(&aux->thread_id, 1u, &tid); + n_ids_per_thread = n_ids / n_threads; + th_ids = &ids[tid * n_ids_per_thread]; + + /* NEW / ALLOC */ + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + ignore(seq_pool_new_id(aux->pool, tid, &th_ids[i])); + } + thread_working_ms[tid] = elapsed(&start); + + ovs_barrier_block(&barrier); + + /* DEL */ + + shuffle(th_ids, n_ids_per_thread); + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + seq_pool_free_id(aux->pool, tid, th_ids[i]); + } + thread_working_ms[tid] = elapsed(&start); + + ovs_barrier_block(&barrier); + + /* MIX */ + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + ignore(seq_pool_new_id(aux->pool, tid, &th_ids[i])); + seq_pool_free_id(aux->pool, tid, th_ids[i]); + ignore(seq_pool_new_id(aux->pool, tid, &th_ids[i])); + } + thread_working_ms[tid] = elapsed(&start); + + ovs_barrier_block(&barrier); + + /* MIX SHUFFLED */ + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + if (elapsed(&start) >= TIMEOUT_MS) { + break; + } + ignore(seq_pool_new_id(aux->pool, tid, &th_ids[i])); + swap_u32(&th_ids[i], &th_ids[random_range(i + 1)]); + seq_pool_free_id(aux->pool, tid, th_ids[i]); + ignore(seq_pool_new_id(aux->pool, tid, &th_ids[i])); + } + thread_working_ms[tid] = elapsed(&start); + + return NULL; +} + +static void +benchmark_seq_pool(void) +{ + pthread_t *threads; + struct seq_pool_aux aux; + size_t i; + + memset(ids, 0, n_ids & sizeof *ids); + memset(thread_working_ms, 0, n_threads & sizeof *thread_working_ms); + + aux.pool = seq_pool_create(n_threads, 0, n_ids); + atomic_store(&aux.thread_id, 0); + + for (i = n_ids - (n_ids % n_threads); i < n_ids; i++) { + uint32_t id; + + seq_pool_new_id(aux.pool, 0, &id); + ids[i] = id; + } + + threads = xmalloc(n_threads * sizeof *threads); + ovs_barrier_init(&barrier, n_threads + 1); + + for (i = 0; i < n_threads; i++) { + threads[i] = ovs_thread_create("seq_pool_alloc", + seq_pool_thread, &aux); + } + + ovs_barrier_block(&barrier); + + print_result("seq-pool new"); + + ovs_barrier_block(&barrier); + + print_result("seq-pool del"); + + ovs_barrier_block(&barrier); + + print_result("seq-pool mix"); + + for (i = 0; i < n_threads; i++) { + xpthread_join(threads[i], NULL); + } + + print_result("seq-pool rnd"); + + seq_pool_destroy(aux.pool); + ovs_barrier_destroy(&barrier); + free(threads); +} + +struct id_pool_aux { + struct id_pool *pool; + struct ovs_mutex *lock; + atomic_uint thread_id; +}; + +static void * +id_pool_thread(void *aux_) +{ + unsigned int n_ids_per_thread; + struct id_pool_aux *aux = aux_; + uint32_t *th_ids; + unsigned int tid; + int start; + size_t i; + + atomic_add(&aux->thread_id, 1u, &tid); + n_ids_per_thread = n_ids / n_threads; + th_ids = &ids[tid * n_ids_per_thread]; + + /* NEW */ + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + ovs_mutex_lock(aux->lock); + ovs_assert(id_pool_alloc_id(aux->pool, &th_ids[i])); + ovs_mutex_unlock(aux->lock); + } + thread_working_ms[tid] = elapsed(&start); + + ovs_barrier_block(&barrier); + + /* DEL */ + + shuffle(th_ids, n_ids_per_thread); + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + ovs_mutex_lock(aux->lock); + id_pool_free_id(aux->pool, th_ids[i]); + ovs_mutex_unlock(aux->lock); + } + thread_working_ms[tid] = elapsed(&start); + + ovs_barrier_block(&barrier); + + /* MIX */ + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + ovs_mutex_lock(aux->lock); + ignore(id_pool_alloc_id(aux->pool, &th_ids[i])); + id_pool_free_id(aux->pool, th_ids[i]); + ignore(id_pool_alloc_id(aux->pool, &th_ids[i])); + ovs_mutex_unlock(aux->lock); + } + thread_working_ms[tid] = elapsed(&start); + + ovs_barrier_block(&barrier); + + /* MIX SHUFFLED */ + + start = running_time_ms; + for (i = 0; i < n_ids_per_thread; i++) { + if (elapsed(&start) >= TIMEOUT_MS) { + break; + } + ovs_mutex_lock(aux->lock); + ignore(id_pool_alloc_id(aux->pool, &th_ids[i])); + swap_u32(&th_ids[i], &th_ids[random_range(i + 1)]); + id_pool_free_id(aux->pool, th_ids[i]); + ignore(id_pool_alloc_id(aux->pool, &th_ids[i])); + ovs_mutex_unlock(aux->lock); + } + thread_working_ms[tid] = elapsed(&start); + + return NULL; +} + +static void +benchmark_id_pool(void) +{ + pthread_t *threads; + struct id_pool_aux aux; + struct ovs_mutex lock; + size_t i; + + memset(ids, 0, n_ids & sizeof *ids); + memset(thread_working_ms, 0, n_threads & sizeof *thread_working_ms); + + aux.pool = id_pool_create(0, n_ids); + aux.lock = &lock; + ovs_mutex_init(&lock); + atomic_store(&aux.thread_id, 0); + + for (i = n_ids - (n_ids % n_threads); i < n_ids; i++) { + id_pool_alloc_id(aux.pool, &ids[i]); + } + + threads = xmalloc(n_threads * sizeof *threads); + ovs_barrier_init(&barrier, n_threads + 1); + + for (i = 0; i < n_threads; i++) { + threads[i] = ovs_thread_create("id_pool_alloc", id_pool_thread, &aux); + } + + ovs_barrier_block(&barrier); + + print_result(" id-pool new"); + + ovs_barrier_block(&barrier); + + print_result(" id-pool del"); + + ovs_barrier_block(&barrier); + + print_result(" id-pool mix"); + + for (i = 0; i < n_threads; i++) { + xpthread_join(threads[i], NULL); + } + + print_result(" id-pool rnd"); + + id_pool_destroy(aux.pool); + ovs_barrier_destroy(&barrier); + free(threads); +} + +static void * +clock_main(void *arg OVS_UNUSED) +{ + struct timeval start; + struct timeval end; + + xgettimeofday(&start); + while (!stop) { + xgettimeofday(&end); + running_time_ms = timeval_to_msec(&end) - timeval_to_msec(&start); + xnanosleep(1000); + } + + return NULL; +} + +static void +run_benchmarks(struct ovs_cmdl_context *ctx) +{ + pthread_t clock; + long int l_threads; + long int l_ids; + size_t i; + + l_ids = strtol(ctx->argv[1], NULL, 10); + l_threads = strtol(ctx->argv[2], NULL, 10); + ovs_assert(l_ids > 0 && l_threads > 0); + + n_ids = l_ids; + n_threads = l_threads; + + ids = xcalloc(n_ids, sizeof *ids); + thread_working_ms = xcalloc(n_threads, sizeof *thread_working_ms); + + clock = ovs_thread_create("clock", clock_main, NULL); + + printf("Benchmarking n=%u on %u thread%s.\n", n_ids, n_threads, + n_threads > 1 ? "s" : ""); + + printf(" type\\thread: "); + for (i = 0; i < n_threads; i++) { + printf(" %3" PRIuSIZE " ", i + 1); + } + printf(" Avg\n"); + + benchmark_seq_pool(); + benchmark_id_pool(); + + stop = true; + + free(thread_working_ms); + xpthread_join(clock, NULL); +} + +static const struct ovs_cmdl_command commands[] = { + {"check", NULL, 0, 0, run_tests, OVS_RO}, + {"benchmark", " ", 2, 2, run_benchmarks, OVS_RO}, + {NULL, NULL, 0, 0, NULL, OVS_RO}, +}; + +static void +test_seq_pool_main(int argc, char *argv[]) +{ + struct ovs_cmdl_context ctx = { + .argc = argc - optind, + .argv = argv + optind, + }; + + set_program_name(argv[0]); + ovs_cmdl_run_command(&ctx, commands); +} + +OVSTEST_REGISTER("test-seq-pool", test_seq_pool_main);