From patchwork Mon Nov 18 02:45:18 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yanqin Wei X-Patchwork-Id: 1196497 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=hemlock.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47GYGt0lGxz9sQp for ; Mon, 18 Nov 2019 13:45:41 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id C791587A0A; Mon, 18 Nov 2019 02:45:39 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id SLcfJRCBpuLP; Mon, 18 Nov 2019 02:45:38 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by hemlock.osuosl.org (Postfix) with ESMTP id 64BAF87A34; Mon, 18 Nov 2019 02:45:38 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 426CAC1DDD; Mon, 18 Nov 2019 02:45:38 +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 95F03C07AC; Mon, 18 Nov 2019 02:45:35 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 191F38637A; Mon, 18 Nov 2019 02:45:35 +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 19N4ur5SMNm5; Mon, 18 Nov 2019 02:45:33 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by whitealder.osuosl.org (Postfix) with ESMTP id A003686239; Mon, 18 Nov 2019 02:45:32 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id E5BF01FB; Sun, 17 Nov 2019 18:45:31 -0800 (PST) Received: from net-arm-thunderx2-03.shanghai.arm.com (net-arm-thunderx2-03.shanghai.arm.com [10.169.40.67]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id D908F3F6C4; Sun, 17 Nov 2019 18:45:29 -0800 (PST) From: Yanqin Wei To: dev@openvswitch.org, ovs-dev@openvswitch.org Date: Mon, 18 Nov 2019 10:45:18 +0800 Message-Id: <20191118024519.11367-2-Yanqin.Wei@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20191118024519.11367-1-Yanqin.Wei@arm.com> References: <20191118024519.11367-1-Yanqin.Wei@arm.com> Cc: Ola.Liljedahl@arm.com, nd@arm.com, Gavin.Hu@arm.com Subject: [ovs-dev] [PATCH v1 1/2] cmap: add thread fence for slot update 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: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" bucket update in the cmap lib is protected by a counter. But hash setting is possible to be moved before counter update. This patch fix this issue. Reviewed-by: Ola Liljedahl Reviewed-by: Gavin Hu Signed-off-by: Yanqin Wei --- lib/cmap.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/lib/cmap.c b/lib/cmap.c index c9eef3f4a..e41c40794 100644 --- a/lib/cmap.c +++ b/lib/cmap.c @@ -598,7 +598,9 @@ cmap_set_bucket(struct cmap_bucket *b, int i, uint32_t c; atomic_read_explicit(&b->counter, &c, memory_order_acquire); - atomic_store_explicit(&b->counter, c + 1, memory_order_release); + atomic_store_explicit(&b->counter, c + 1, memory_order_relaxed); + /*need to make sure setting hash is not moved up before counter update*/ + atomic_thread_fence(memory_order_release); ovsrcu_set(&b->nodes[i].next, node); /* Also atomic. */ b->hashes[i] = hash; atomic_store_explicit(&b->counter, c + 2, memory_order_release); From patchwork Mon Nov 18 02:45:19 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yanqin Wei X-Patchwork-Id: 1196499 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=hemlock.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47GYH14F00z9sPj for ; Mon, 18 Nov 2019 13:45:49 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id D4DBE87B2E; Mon, 18 Nov 2019 02:45:47 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LZNC+QXd4f1n; Mon, 18 Nov 2019 02:45:41 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by hemlock.osuosl.org (Postfix) with ESMTP id 7257187A2E; Mon, 18 Nov 2019 02:45:41 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 49230C18DE; Mon, 18 Nov 2019 02:45:41 +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 A011BC18DE; Mon, 18 Nov 2019 02:45:37 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 8DAD2863BE; Mon, 18 Nov 2019 02:45:37 +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 RdOtFLMSy2yc; Mon, 18 Nov 2019 02:45:35 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by whitealder.osuosl.org (Postfix) with ESMTP id 8B6D086239; Mon, 18 Nov 2019 02:45:35 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 076661FB; Sun, 17 Nov 2019 18:45:35 -0800 (PST) Received: from net-arm-thunderx2-03.shanghai.arm.com (net-arm-thunderx2-03.shanghai.arm.com [10.169.40.67]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 3E20D3F6C4; Sun, 17 Nov 2019 18:45:33 -0800 (PST) From: Yanqin Wei To: dev@openvswitch.org, ovs-dev@openvswitch.org Date: Mon, 18 Nov 2019 10:45:19 +0800 Message-Id: <20191118024519.11367-3-Yanqin.Wei@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20191118024519.11367-1-Yanqin.Wei@arm.com> References: <20191118024519.11367-1-Yanqin.Wei@arm.com> Cc: Ola.Liljedahl@arm.com, nd@arm.com, Gavin.Hu@arm.com Subject: [ovs-dev] [PATCH v1 2/2] cmap: non-blocking cmap lookup 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: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Currently cmap_bucket is protected by a counter. Cmap reader will be blocked until the counter becomes even, writer increments it by 1 to be odd, and after slot update, increments by 1 again to become even. If the writer is pending or scheduled out during the writer course, the reader will be blocked. This patch introduces a bitmap as guard variable for (hash,node) pair. Writer need set slot valid bit to 0 before each change. And after change, writer sets valid bit to 1 and increments counter. Thus, reader can ensure slot consistency by only scanning valid slot and then checking counter+bitmap does not change while examining the bucket. The only time a reader has to retry the read operation for single bucket is when 1)a writer clears a bit in the valid bitmap between a reader's first and second read of the counter+bitmap. 2)a writer increments the counter between a reader's first and second read of counter+bitmap. I.e. the read operation needs to be retried when some other thread has made progress (with a write). There is no spinning/waiting for other threads to complete. This makes the design non-blocking (for readers). And it has almost no additional overhead because counter and bitmap share one 32 bits variable. No additional load/store for reader and writer. Reviewed-by: Ola Liljedahl Reviewed-by: Gavin Hu Signed-off-by: Yanqin Wei --- lib/cmap.c | 157 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 101 insertions(+), 56 deletions(-) diff --git a/lib/cmap.c b/lib/cmap.c index e41c40794..a36efc68c 100644 --- a/lib/cmap.c +++ b/lib/cmap.c @@ -123,18 +123,27 @@ COVERAGE_DEFINE(cmap_shrink); /* Number of entries per bucket: 7 on 32-bit, 5 on 64-bit for 64B cacheline. */ #define CMAP_K ((CACHE_LINE_SIZE - 4) / CMAP_ENTRY_SIZE) +/* "counter_slotValidMap" in cmap_bucket includes counter and slot valid map. + * Reserve the "CMAP_K" least significant bits for slot valid bitmap and use + * remaining bits for bucket counter. Adding 1<counter, &counter, memory_order_acquire); + atomic_read_explicit(&bucket->counter_slotValidMap, &counter_slotValidMap, + memory_order_relaxed); - return counter; + return CMAP_SLOT_MAP(counter_slotValidMap); } static inline uint32_t -read_even_counter(const struct cmap_bucket *bucket) +read_counter_slot_bitmap(const struct cmap_bucket *bucket_) { - uint32_t counter; + struct cmap_bucket *bucket = CONST_CAST(struct cmap_bucket *, bucket_); + uint32_t counter_slotValidMap; - do { - counter = read_counter(bucket); - } while (OVS_UNLIKELY(counter & 1)); + /*Both counter and slot valid map are changed each time slot is updated. + * So counter_slotValidMap can be directly used for tracking hash update */ + atomic_read_explicit(&bucket->counter_slotValidMap, &counter_slotValidMap, + memory_order_acquire); - return counter; + return counter_slotValidMap; } static inline bool -counter_changed(const struct cmap_bucket *b_, uint32_t c) +bucket_changed(const struct cmap_bucket *b_, uint32_t c) { struct cmap_bucket *b = CONST_CAST(struct cmap_bucket *, b_); - uint32_t counter; + uint32_t counter_slotValidMap; /* Need to make sure the counter read is not moved up, before the hash and - * cmap_node_next(). Using atomic_read_explicit with memory_order_acquire - * would allow prior reads to be moved after the barrier. - * atomic_thread_fence prevents all following memory accesses from moving - * prior to preceding loads. */ + * cmap_node_next(). + * atomic_thread_fence with acquire memory ordering prevents all following + memory accesses from moving prior to preceding loads. */ atomic_thread_fence(memory_order_acquire); - atomic_read_relaxed(&b->counter, &counter); + atomic_read_relaxed(&b->counter_slotValidMap, &counter_slotValidMap); - return OVS_UNLIKELY(counter != c); + return OVS_UNLIKELY(counter_slotValidMap != c); } static inline const struct cmap_node * -cmap_find_in_bucket(const struct cmap_bucket *bucket, uint32_t hash) +cmap_find_in_bucket(const struct cmap_bucket *bucket, uint32_t hash, + uint32_t slot_map) { - for (int i = 0; i < CMAP_K; i++) { + int i; + + ULLONG_FOR_EACH_1 (i, slot_map) { if (bucket->hashes[i] == hash) { return cmap_node_next(&bucket->nodes[i]); } } + return NULL; } @@ -334,20 +349,23 @@ cmap_find__(const struct cmap_bucket *b1, const struct cmap_bucket *b2, do { do { - c1 = read_even_counter(b1); - node = cmap_find_in_bucket(b1, hash); - } while (OVS_UNLIKELY(counter_changed(b1, c1))); + c1 = read_counter_slot_bitmap(b1); + node = cmap_find_in_bucket(b1, hash, CMAP_SLOT_MAP(c1)); + } while (OVS_UNLIKELY(bucket_changed(b1, c1))); + if (node) { break; } + do { - c2 = read_even_counter(b2); - node = cmap_find_in_bucket(b2, hash); - } while (OVS_UNLIKELY(counter_changed(b2, c2))); + c2 = read_counter_slot_bitmap(b2); + node = cmap_find_in_bucket(b2, hash, CMAP_SLOT_MAP(c2)); + } while (OVS_UNLIKELY(bucket_changed(b2, c2))); + if (node) { break; } - } while (OVS_UNLIKELY(counter_changed(b1, c1))); + } while (OVS_UNLIKELY(bucket_changed(b1, c1))); return node; } @@ -418,31 +436,37 @@ cmap_find_index(const struct cmap *cmap, uint32_t hash) const struct cmap_bucket *b1 = &impl->buckets[b_index1]; const struct cmap_bucket *b2 = &impl->buckets[b_index2]; + int i; + do { do { - c1 = read_even_counter(b1); - for (int i = 0; i < CMAP_K; i++) { + c1 = read_counter_slot_bitmap(b1); + + ULLONG_FOR_EACH_1 (i, CMAP_SLOT_MAP(c1)) { if (b1->hashes[i] == hash) { index = b_index1 * CMAP_K + i; } } - } while (OVS_UNLIKELY(counter_changed(b1, c1))); + } while (OVS_UNLIKELY(bucket_changed(b1, c1))); + if (index != UINT32_MAX) { break; } + do { - c2 = read_even_counter(b2); - for (int i = 0; i < CMAP_K; i++) { + c2 = read_counter_slot_bitmap(b2); + + ULLONG_FOR_EACH_1 (i, CMAP_SLOT_MAP(c2)) { if (b2->hashes[i] == hash) { index = b_index2 * CMAP_K + i; } } - } while (OVS_UNLIKELY(counter_changed(b2, c2))); + } while (OVS_UNLIKELY(bucket_changed(b2, c2))); if (index != UINT32_MAX) { break; } - } while (OVS_UNLIKELY(counter_changed(b1, c1))); + } while (OVS_UNLIKELY(bucket_changed(b1, c1))); return index; } @@ -480,9 +504,9 @@ cmap_find_batch(const struct cmap *cmap, unsigned long map, const struct cmap_node *node; do { - c1 = read_even_counter(b1); - node = cmap_find_in_bucket(b1, hashes[i]); - } while (OVS_UNLIKELY(counter_changed(b1, c1))); + c1 = read_counter_slot_bitmap(b1); + node = cmap_find_in_bucket(b1, hashes[i], CMAP_SLOT_MAP(c1)); + } while (OVS_UNLIKELY(bucket_changed(b1, c1))); if (!node) { /* Not found (yet); Prefetch the 2nd bucket. */ @@ -503,9 +527,9 @@ cmap_find_batch(const struct cmap *cmap, unsigned long map, const struct cmap_node *node; do { - c2 = read_even_counter(b2); - node = cmap_find_in_bucket(b2, hashes[i]); - } while (OVS_UNLIKELY(counter_changed(b2, c2))); + c2 = read_counter_slot_bitmap(b2); + node = cmap_find_in_bucket(b2, hashes[i], CMAP_SLOT_MAP(c2)); + } while (OVS_UNLIKELY(bucket_changed(b2, c2))); if (!node) { /* Not found, but the node may have been moved from b2 to b1 right @@ -516,7 +540,7 @@ cmap_find_batch(const struct cmap *cmap, unsigned long map, * need to loop as long as it takes to get stable readings of * both buckets. cmap_find__() does that, and now that we have * fetched both buckets we can just use it. */ - if (OVS_UNLIKELY(counter_changed(b1s[i], c1s[i]))) { + if (OVS_UNLIKELY(bucket_changed(b1s[i], c1s[i]))) { node = cmap_find__(b1s[i], b2s[i], hashes[i]); if (node) { goto found; @@ -537,8 +561,11 @@ static int cmap_find_slot_protected(struct cmap_bucket *b, uint32_t hash) { int i; + uint32_t slot_map; - for (i = 0; i < CMAP_K; i++) { + slot_map = read_slot_bitmap_protected(b); + + ULLONG_FOR_EACH_1 (i, slot_map) { if (b->hashes[i] == hash && cmap_node_next_protected(&b->nodes[i])) { return i; } @@ -551,8 +578,11 @@ cmap_find_bucket_protected(struct cmap_impl *impl, uint32_t hash, uint32_t h) { struct cmap_bucket *b = &impl->buckets[h & impl->mask]; int i; + uint32_t slot_map; - for (i = 0; i < CMAP_K; i++) { + slot_map = read_slot_bitmap_protected(b); + + ULLONG_FOR_EACH_1 (i, slot_map) { if (b->hashes[i] == hash) { return cmap_node_next_protected(&b->nodes[i]); } @@ -595,15 +625,27 @@ static void cmap_set_bucket(struct cmap_bucket *b, int i, struct cmap_node *node, uint32_t hash) { - uint32_t c; + uint32_t counter_slotValidMap; + + atomic_read_explicit(&b->counter_slotValidMap, &counter_slotValidMap, + memory_order_relaxed); + /*clear the bit in the valid bitmap before update slot*/ + counter_slotValidMap &= ~(UINT32_C(1) << i); + atomic_store_explicit(&b->counter_slotValidMap, counter_slotValidMap, + memory_order_relaxed); - atomic_read_explicit(&b->counter, &c, memory_order_acquire); - atomic_store_explicit(&b->counter, c + 1, memory_order_relaxed); - /*need to make sure setting hash is not moved up before counter update*/ + /*need to make sure setting hash is not moved up before clearing + *slot_valid_map */ atomic_thread_fence(memory_order_release); ovsrcu_set(&b->nodes[i].next, node); /* Also atomic. */ b->hashes[i] = hash; - atomic_store_explicit(&b->counter, c + 2, memory_order_release); + + /*set the bit in the valid bitmap after update slot*/ + counter_slotValidMap |= (UINT32_C(1) << i); + /*increment the counter value to notify reader*/ + counter_slotValidMap += CMAP_CNT_INC; + atomic_store_explicit(&b->counter_slotValidMap, counter_slotValidMap, + memory_order_release); } /* Searches 'b' for a node with the given 'hash'. If it finds one, adds @@ -614,8 +656,11 @@ cmap_insert_dup(struct cmap_node *new_node, uint32_t hash, struct cmap_bucket *b) { int i; + uint32_t slot_map; - for (i = 0; i < CMAP_K; i++) { + slot_map = read_slot_bitmap_protected(b); + + ULLONG_FOR_EACH_1 (i, slot_map) { if (b->hashes[i] == hash) { struct cmap_node *node = cmap_node_next_protected(&b->nodes[i]);