From: Gage Eads <gage.eads@intel.com>
To: dev@dpdk.org
Cc: olivier.matz@6wind.com, arybchenko@solarflare.com,
bruce.richardson@intel.com, konstantin.ananyev@intel.com,
stephen@networkplumber.org
Subject: [dpdk-dev] [PATCH v3 1/5] ring: add 64-bit headtail structure
Date: Fri, 18 Jan 2019 09:23:22 -0600 [thread overview]
Message-ID: <20190118152326.22686-2-gage.eads@intel.com> (raw)
In-Reply-To: <20190118152326.22686-1-gage.eads@intel.com>
64-bit head and tail index widths greatly increases the time it takes for
them to wrap-around (with current CPU speeds, it won't happen within the
author's lifetime). This is important in avoiding the ABA problem -- in
which a thread mistakes reading the same tail index in two accesses to mean
that the ring was not modified in the intervening time -- in the upcoming
non-blocking ring implementation. Using a 64-bit index makes the
possibility of this occurring effectively zero.
This commit places the new producer and consumer structures in the same
location in struct rte_ring as their 32-bit counterparts. Since the 32-bit
versions are padded out to a cache line, there is space for the new
structure without affecting the layout of struct rte_ring. Thus, the ABI is
preserved.
Signed-off-by: Gage Eads <gage.eads@intel.com>
---
lib/librte_eventdev/rte_event_ring.h | 2 +-
lib/librte_ring/Makefile | 3 +-
lib/librte_ring/rte_ring.h | 24 +++++-
lib/librte_ring/rte_ring_generic_64.h | 152 ++++++++++++++++++++++++++++++++++
4 files changed, 176 insertions(+), 5 deletions(-)
create mode 100644 lib/librte_ring/rte_ring_generic_64.h
diff --git a/lib/librte_eventdev/rte_event_ring.h b/lib/librte_eventdev/rte_event_ring.h
index 827a3209e..5fcb2d5f7 100644
--- a/lib/librte_eventdev/rte_event_ring.h
+++ b/lib/librte_eventdev/rte_event_ring.h
@@ -1,5 +1,5 @@
/* SPDX-License-Identifier: BSD-3-Clause
- * Copyright(c) 2016-2017 Intel Corporation
+ * Copyright(c) 2016-2019 Intel Corporation
*/
/**
diff --git a/lib/librte_ring/Makefile b/lib/librte_ring/Makefile
index 21a36770d..18c48fbc8 100644
--- a/lib/librte_ring/Makefile
+++ b/lib/librte_ring/Makefile
@@ -19,6 +19,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RING) := rte_ring.c
# install includes
SYMLINK-$(CONFIG_RTE_LIBRTE_RING)-include := rte_ring.h \
rte_ring_generic.h \
- rte_ring_c11_mem.h
+ rte_ring_c11_mem.h \
+ rte_ring_generic_64.h
include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_ring/rte_ring.h b/lib/librte_ring/rte_ring.h
index af5444a9f..b270a4746 100644
--- a/lib/librte_ring/rte_ring.h
+++ b/lib/librte_ring/rte_ring.h
@@ -1,6 +1,6 @@
/* SPDX-License-Identifier: BSD-3-Clause
*
- * Copyright (c) 2010-2017 Intel Corporation
+ * Copyright (c) 2010-2019 Intel Corporation
* Copyright (c) 2007-2009 Kip Macy kmacy@freebsd.org
* All rights reserved.
* Derived from FreeBSD's bufring.h
@@ -70,6 +70,15 @@ struct rte_ring_headtail {
uint32_t single; /**< True if single prod/cons */
};
+/* 64-bit version of rte_ring_headtail, for use by rings that need to avoid
+ * head/tail wrap-around.
+ */
+struct rte_ring_headtail_64 {
+ volatile uint64_t head; /**< Prod/consumer head. */
+ volatile uint64_t tail; /**< Prod/consumer tail. */
+ uint32_t single; /**< True if single prod/cons */
+};
+
/**
* An RTE ring structure.
*
@@ -97,11 +106,19 @@ struct rte_ring {
char pad0 __rte_cache_aligned; /**< empty cache line */
/** Ring producer status. */
- struct rte_ring_headtail prod __rte_cache_aligned;
+ RTE_STD_C11
+ union {
+ struct rte_ring_headtail prod __rte_cache_aligned;
+ struct rte_ring_headtail_64 prod_64 __rte_cache_aligned;
+ };
char pad1 __rte_cache_aligned; /**< empty cache line */
/** Ring consumer status. */
- struct rte_ring_headtail cons __rte_cache_aligned;
+ RTE_STD_C11
+ union {
+ struct rte_ring_headtail cons __rte_cache_aligned;
+ struct rte_ring_headtail_64 cons_64 __rte_cache_aligned;
+ };
char pad2 __rte_cache_aligned; /**< empty cache line */
};
@@ -312,6 +329,7 @@ void rte_ring_dump(FILE *f, const struct rte_ring *r);
#else
#include "rte_ring_generic.h"
#endif
+#include "rte_ring_generic_64.h"
/**
* @internal Enqueue several objects on the ring
diff --git a/lib/librte_ring/rte_ring_generic_64.h b/lib/librte_ring/rte_ring_generic_64.h
new file mode 100644
index 000000000..58de144c6
--- /dev/null
+++ b/lib/librte_ring/rte_ring_generic_64.h
@@ -0,0 +1,152 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Copyright (c) 2010-2019 Intel Corporation
+ * Copyright (c) 2007-2009 Kip Macy kmacy@freebsd.org
+ * All rights reserved.
+ * Derived from FreeBSD's bufring.h
+ * Used as BSD-3 Licensed with permission from Kip Macy.
+ */
+
+#ifndef _RTE_RING_GENERIC_64_H_
+#define _RTE_RING_GENERIC_64_H_
+
+/**
+ * @internal This function updates the producer head for enqueue using
+ * 64-bit head/tail values.
+ *
+ * @param r
+ * A pointer to the ring structure
+ * @param is_sp
+ * Indicates whether multi-producer path is needed or not
+ * @param n
+ * The number of elements we will want to enqueue, i.e. how far should the
+ * head be moved
+ * @param behavior
+ * RTE_RING_QUEUE_FIXED: Enqueue a fixed number of items from a ring
+ * RTE_RING_QUEUE_VARIABLE: Enqueue as many items as possible from ring
+ * @param old_head
+ * Returns head value as it was before the move, i.e. where enqueue starts
+ * @param new_head
+ * Returns the current/new head value i.e. where enqueue finishes
+ * @param free_entries
+ * Returns the amount of free space in the ring BEFORE head was moved
+ * @return
+ * Actual number of objects enqueued.
+ * If behavior == RTE_RING_QUEUE_FIXED, this will be 0 or n only.
+ */
+static __rte_always_inline unsigned int
+__rte_ring_move_prod_head_64(struct rte_ring *r, unsigned int is_sp,
+ unsigned int n, enum rte_ring_queue_behavior behavior,
+ uint64_t *old_head, uint64_t *new_head,
+ uint32_t *free_entries)
+{
+ const uint32_t capacity = r->capacity;
+ unsigned int max = n;
+ int success;
+
+ do {
+ /* Reset n to the initial burst count */
+ n = max;
+
+ *old_head = r->prod_64.head;
+
+ /* add rmb barrier to avoid load/load reorder in weak
+ * memory model. It is noop on x86
+ */
+ rte_smp_rmb();
+
+ /*
+ * The subtraction is done between two unsigned 64bits value
+ * (the result is always modulo 64 bits even if we have
+ * *old_head > cons_tail). So 'free_entries' is always between 0
+ * and capacity (which is < size).
+ */
+ *free_entries = (capacity + r->cons_64.tail - *old_head);
+
+ /* check that we have enough room in ring */
+ if (unlikely(n > *free_entries))
+ n = (behavior == RTE_RING_QUEUE_FIXED) ?
+ 0 : *free_entries;
+
+ if (n == 0)
+ return 0;
+
+ *new_head = *old_head + n;
+ if (is_sp)
+ r->prod_64.head = *new_head, success = 1;
+ else
+ success = rte_atomic64_cmpset(&r->prod_64.head,
+ *old_head, *new_head);
+ } while (unlikely(success == 0));
+ return n;
+}
+
+/**
+ * @internal This function updates the consumer head for dequeue using
+ * 64-bit head/tail values.
+ *
+ * @param r
+ * A pointer to the ring structure
+ * @param is_sc
+ * Indicates whether multi-consumer path is needed or not
+ * @param n
+ * The number of elements we will want to enqueue, i.e. how far should the
+ * head be moved
+ * @param behavior
+ * RTE_RING_QUEUE_FIXED: Dequeue a fixed number of items from a ring
+ * RTE_RING_QUEUE_VARIABLE: Dequeue as many items as possible from ring
+ * @param old_head
+ * Returns head value as it was before the move, i.e. where dequeue starts
+ * @param new_head
+ * Returns the current/new head value i.e. where dequeue finishes
+ * @param entries
+ * Returns the number of entries in the ring BEFORE head was moved
+ * @return
+ * - Actual number of objects dequeued.
+ * If behavior == RTE_RING_QUEUE_FIXED, this will be 0 or n only.
+ */
+static __rte_always_inline unsigned int
+__rte_ring_move_cons_head_64(struct rte_ring *r, unsigned int is_sc,
+ unsigned int n, enum rte_ring_queue_behavior behavior,
+ uint64_t *old_head, uint64_t *new_head,
+ uint32_t *entries)
+{
+ unsigned int max = n;
+ int success;
+
+ do {
+ /* Restore n as it may change every loop */
+ n = max;
+
+ *old_head = r->cons_64.head;
+
+ /* add rmb barrier to avoid load/load reorder in weak
+ * memory model. It is noop on x86
+ */
+ rte_smp_rmb();
+
+ /* The subtraction is done between two unsigned 64bits value
+ * (the result is always modulo 64 bits even if we have
+ * cons_head > prod_tail). So 'entries' is always between 0
+ * and size(ring)-1.
+ */
+ *entries = (r->prod_64.tail - *old_head);
+
+ /* Set the actual entries for dequeue */
+ if (n > *entries)
+ n = (behavior == RTE_RING_QUEUE_FIXED) ? 0 : *entries;
+
+ if (unlikely(n == 0))
+ return 0;
+
+ *new_head = *old_head + n;
+ if (is_sc)
+ r->cons_64.head = *new_head, success = 1;
+ else
+ success = rte_atomic64_cmpset(&r->cons_64.head,
+ *old_head, *new_head);
+ } while (unlikely(success == 0));
+ return n;
+}
+
+#endif /* _RTE_RING_GENERIC_64_H_ */
--
2.13.6
next prev parent reply other threads:[~2019-01-18 15:24 UTC|newest]
Thread overview: 123+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-01-10 21:01 [dpdk-dev] [PATCH 0/6] Add non-blocking ring Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 1/6] ring: change head and tail to pointer-width size Gage Eads
2019-01-11 4:38 ` Stephen Hemminger
2019-01-11 19:07 ` Eads, Gage
2019-01-11 10:25 ` Burakov, Anatoly
2019-01-11 19:12 ` Eads, Gage
2019-01-11 19:55 ` Stephen Hemminger
2019-01-15 15:48 ` Eads, Gage
2019-01-11 10:40 ` Burakov, Anatoly
2019-01-11 10:58 ` Bruce Richardson
2019-01-11 11:30 ` Burakov, Anatoly
[not found] ` <20190111115851.GC3336@bricha3-MOBL.ger.corp.intel.com>
2019-01-11 19:27 ` Eads, Gage
2019-01-21 14:14 ` Burakov, Anatoly
2019-01-22 18:27 ` Eads, Gage
2019-01-10 21:01 ` [dpdk-dev] [PATCH 2/6] ring: add a non-blocking implementation Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 3/6] test_ring: add non-blocking ring autotest Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 4/6] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 5/6] mempool/ring: add non-blocking ring handlers Gage Eads
2019-01-13 13:43 ` Andrew Rybchenko
2019-01-10 21:01 ` [dpdk-dev] [PATCH 6/6] doc: add NB ring comment to EAL "known issues" Gage Eads
2019-01-11 2:51 ` Varghese, Vipin
2019-01-11 19:30 ` Eads, Gage
2019-01-14 0:07 ` Varghese, Vipin
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 0/5] Add non-blocking ring Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 1/5] ring: change head and tail to pointer-width size Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 2/5] ring: add a non-blocking implementation Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 3/5] test_ring: add non-blocking ring autotest Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 4/5] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 5/5] mempool/ring: add non-blocking ring handlers Gage Eads
2019-01-16 0:26 ` [dpdk-dev] [PATCH v2 0/5] Add non-blocking ring Stephen Hemminger
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 " Gage Eads
2019-01-18 15:23 ` Gage Eads [this message]
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 2/5] ring: add a non-blocking implementation Gage Eads
2019-01-22 10:12 ` Ola Liljedahl
2019-01-22 14:49 ` Ola Liljedahl
2019-01-22 21:31 ` Eads, Gage
2019-01-23 10:16 ` Ola Liljedahl
2019-01-25 17:21 ` Eads, Gage
2019-01-28 10:35 ` Ola Liljedahl
2019-01-28 18:54 ` Eads, Gage
2019-01-28 22:31 ` Ola Liljedahl
2019-01-28 13:34 ` Jerin Jacob Kollanukkaran
2019-01-28 13:43 ` Ola Liljedahl
2019-01-28 14:04 ` Jerin Jacob Kollanukkaran
2019-01-28 14:06 ` Ola Liljedahl
2019-01-28 18:59 ` Eads, Gage
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 3/5] test_ring: add non-blocking ring autotest Gage Eads
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 4/5] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 5/5] mempool/ring: add non-blocking ring handlers Gage Eads
2019-01-22 9:27 ` [dpdk-dev] [PATCH v3 0/5] Add non-blocking ring Ola Liljedahl
2019-01-22 10:15 ` Ola Liljedahl
2019-01-22 19:15 ` Eads, Gage
2019-01-23 16:02 ` Jerin Jacob Kollanukkaran
2019-01-23 16:29 ` Ola Liljedahl
2019-01-28 13:10 ` [dpdk-dev] [EXT] " Jerin Jacob Kollanukkaran
2019-01-25 5:20 ` [dpdk-dev] " Honnappa Nagarahalli
2019-01-25 17:42 ` Eads, Gage
2019-01-25 17:56 ` Eads, Gage
2019-01-28 10:41 ` Ola Liljedahl
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 " Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 1/5] ring: add 64-bit headtail structure Gage Eads
2019-01-29 12:56 ` Ola Liljedahl
2019-01-30 4:26 ` Eads, Gage
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 2/5] ring: add a non-blocking implementation Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 3/5] test_ring: add non-blocking ring autotest Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 4/5] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 5/5] mempool/ring: add non-blocking ring handlers Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 0/6] Add lock-free ring and mempool handler Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 2/6] ring: add a ring start marker Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 3/6] ring: add a lock-free implementation Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 0/6] Add lock-free ring and mempool handler Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 2/6] ring: add a ring start marker Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 3/6] ring: add a lock-free implementation Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 0/6] Add lock-free ring and mempool handler Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 2/6] ring: add a ring start marker Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 3/6] ring: add a lock-free implementation Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-19 15:50 ` Stephen Hemminger
2019-03-19 15:50 ` Stephen Hemminger
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:49 ` [dpdk-dev] [PATCH v7 0/6] Add lock-free ring and mempool handler Eads, Gage
2019-03-18 21:49 ` Eads, Gage
2019-03-19 15:51 ` Stephen Hemminger
2019-03-19 15:51 ` Stephen Hemminger
2019-04-01 19:23 ` Eads, Gage
2019-04-01 19:23 ` Eads, Gage
2019-04-02 10:16 ` Ola Liljedahl
2019-04-02 10:16 ` Ola Liljedahl
2019-04-04 22:28 ` Eads, Gage
2019-04-04 22:28 ` Eads, Gage
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 " Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 2/6] ring: add a ring start marker Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 3/6] ring: add a lock-free implementation Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-04-03 16:46 ` [dpdk-dev] [PATCH v8 0/6] Add lock-free ring and mempool handler Thomas Monjalon
2019-04-03 16:46 ` Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190118152326.22686-2-gage.eads@intel.com \
--to=gage.eads@intel.com \
--cc=arybchenko@solarflare.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=konstantin.ananyev@intel.com \
--cc=olivier.matz@6wind.com \
--cc=stephen@networkplumber.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).