From: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
To: Gage Eads <gage.eads@intel.com>, "dev@dpdk.org" <dev@dpdk.org>
Cc: "olivier.matz@6wind.com" <olivier.matz@6wind.com>,
"arybchenko@solarflare.com" <arybchenko@solarflare.com>,
"bruce.richardson@intel.com" <bruce.richardson@intel.com>,
"konstantin.ananyev@intel.com" <konstantin.ananyev@intel.com>,
"Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.com>,
nd <nd@arm.com>, "thomas@monjalon.net" <thomas@monjalon.net>,
nd <nd@arm.com>
Subject: Re: [dpdk-dev] [PATCH v5 5/8] stack: add lock-free stack implementation
Date: Mon, 1 Apr 2019 18:08:37 +0000 [thread overview]
Message-ID: <VE1PR08MB5149C7725C1BD074516BCABB98550@VE1PR08MB5149.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <20190401001238.17625-6-gage.eads@intel.com>
> Subject: [PATCH v5 5/8] stack: add lock-free stack implementation
>
> This commit adds support for a lock-free (linked list based) stack to the stack
> API. This behavior is selected through a new rte_stack_create() flag,
> RTE_STACK_F_LF.
>
> The stack consists of a linked list of elements, each containing a data pointer
> and a next pointer, and an atomic stack depth counter.
>
> The lock-free push operation enqueues a linked list of pointers by pointing
> the tail of the list to the current stack head, and using a CAS to swing the
> stack head pointer to the head of the list. The operation retries if it is
> unsuccessful (i.e. the list changed between reading the head and modifying
> it), else it adjusts the stack length and returns.
>
> The lock-free pop operation first reserves num elements by adjusting the
> stack length, to ensure the dequeue operation will succeed without blocking.
> It then dequeues pointers by walking the list -- starting from the head -- then
> swinging the head pointer (using a CAS as well). While walking the list, the
> data pointers are recorded in an object table.
>
> This algorithm stack uses a 128-bit compare-and-swap instruction, which
> atomically updates the stack top pointer and a modification counter, to
> protect against the ABA problem.
>
> The linked list elements themselves are maintained in a lock-free LIFO list,
> and are allocated before stack pushes and freed after stack pops.
> Since the stack has a fixed maximum depth, these elements do not need to
> be dynamically created.
>
> Signed-off-by: Gage Eads <gage.eads@intel.com>
> Reviewed-by: Olivier Matz <olivier.matz@6wind.com>
> ---
Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
next prev parent reply other threads:[~2019-04-01 18:08 UTC|newest]
Thread overview: 228+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-02-22 16:06 [dpdk-dev] [PATCH 0/7] Subject: [PATCH ...] Add stack library and new mempool handler Gage Eads
2019-02-22 16:06 ` [dpdk-dev] [PATCH 1/7] stack: introduce rte stack library Gage Eads
2019-02-25 10:43 ` Olivier Matz
2019-02-28 5:10 ` Eads, Gage
2019-02-22 16:06 ` [dpdk-dev] [PATCH 2/7] mempool/stack: convert mempool to use rte stack Gage Eads
2019-02-25 10:46 ` Olivier Matz
2019-02-22 16:06 ` [dpdk-dev] [PATCH 3/7] test/stack: add stack test Gage Eads
2019-02-25 10:59 ` Olivier Matz
2019-02-28 5:11 ` Eads, Gage
2019-02-22 16:06 ` [dpdk-dev] [PATCH 4/7] test/stack: add stack perf test Gage Eads
2019-02-25 11:04 ` Olivier Matz
2019-02-22 16:06 ` [dpdk-dev] [PATCH 5/7] stack: add non-blocking stack implementation Gage Eads
2019-02-25 11:28 ` Olivier Matz
[not found] ` <2EC44CCD3517A842B44C82651A5557A14AF13386@fmsmsx118.amr.corp.intel.com>
2019-03-01 20:53 ` [dpdk-dev] FW: " Eads, Gage
2019-03-01 21:12 ` Thomas Monjalon
2019-03-01 21:29 ` Eads, Gage
2019-02-22 16:06 ` [dpdk-dev] [PATCH 6/7] test/stack: add non-blocking stack tests Gage Eads
2019-02-25 11:28 ` Olivier Matz
2019-02-22 16:06 ` [dpdk-dev] [PATCH 7/7] mempool/stack: add non-blocking stack mempool handler Gage Eads
2019-02-25 11:29 ` Olivier Matz
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 0/8] Add stack library and new " Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 1/8] stack: introduce rte stack library Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 3/8] test/stack: add stack test Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 4/8] test/stack: add stack perf test Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 5/8] stack: add lock-free stack implementation Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 6/8] stack: add C11 atomic implementation Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 7/8] test/stack: add lock-free stack tests Gage Eads
2019-03-05 16:42 ` [dpdk-dev] [PATCH v2 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 0/8] Add stack library and new " Gage Eads
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 1/8] stack: introduce rte stack library Gage Eads
2019-03-14 8:00 ` Olivier Matz
2019-03-14 8:00 ` Olivier Matz
2019-03-28 23:26 ` Honnappa Nagarahalli
2019-03-28 23:26 ` Honnappa Nagarahalli
2019-03-29 19:23 ` Eads, Gage
2019-03-29 19:23 ` Eads, Gage
2019-03-29 21:07 ` Thomas Monjalon
2019-03-29 21:07 ` Thomas Monjalon
2019-04-01 17:41 ` Honnappa Nagarahalli
2019-04-01 17:41 ` Honnappa Nagarahalli
2019-04-01 19:34 ` Eads, Gage
2019-04-01 19:34 ` Eads, Gage
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 3/8] test/stack: add stack test Gage Eads
2019-03-14 8:00 ` Olivier Matz
2019-03-14 8:00 ` Olivier Matz
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 4/8] test/stack: add stack perf test Gage Eads
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 5/8] stack: add lock-free stack implementation Gage Eads
2019-03-14 8:01 ` Olivier Matz
2019-03-14 8:01 ` Olivier Matz
2019-03-28 23:27 ` Honnappa Nagarahalli
2019-03-28 23:27 ` Honnappa Nagarahalli
2019-03-29 19:25 ` Eads, Gage
2019-03-29 19:25 ` Eads, Gage
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 6/8] stack: add C11 atomic implementation Gage Eads
2019-03-14 8:04 ` Olivier Matz
2019-03-14 8:04 ` Olivier Matz
2019-03-28 23:27 ` Honnappa Nagarahalli
2019-03-28 23:27 ` Honnappa Nagarahalli
2019-03-29 19:24 ` Eads, Gage
2019-03-29 19:24 ` Eads, Gage
2019-04-01 0:06 ` Eads, Gage
2019-04-01 0:06 ` Eads, Gage
2019-04-01 19:06 ` Honnappa Nagarahalli
2019-04-01 19:06 ` Honnappa Nagarahalli
2019-04-01 20:21 ` Eads, Gage
2019-04-01 20:21 ` Eads, Gage
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 7/8] test/stack: add lock-free stack tests Gage Eads
2019-03-06 14:45 ` [dpdk-dev] [PATCH v3 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 0/8] Add stack library and new " Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 1/8] stack: introduce rte stack library Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 3/8] test/stack: add stack test Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 4/8] test/stack: add stack perf test Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 5/8] stack: add lock-free stack implementation Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 6/8] stack: add C11 atomic implementation Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 7/8] test/stack: add lock-free stack tests Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-03-28 18:00 ` [dpdk-dev] [PATCH v4 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-03-28 18:00 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 0/8] Add stack library and new " Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 1/8] stack: introduce rte stack library Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 3/8] test/stack: add stack test Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 4/8] test/stack: add stack perf test Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 5/8] stack: add lock-free stack implementation Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 18:08 ` Honnappa Nagarahalli [this message]
2019-04-01 18:08 ` Honnappa Nagarahalli
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 6/8] stack: add C11 atomic implementation Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 7/8] test/stack: add lock-free stack tests Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 0:12 ` [dpdk-dev] [PATCH v5 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-04-01 0:12 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 0/8] Add stack library and new " Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 1/8] stack: introduce rte stack library Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-02 11:14 ` Honnappa Nagarahalli
2019-04-02 11:14 ` Honnappa Nagarahalli
2019-04-03 17:06 ` Thomas Monjalon
2019-04-03 17:06 ` Thomas Monjalon
2019-04-03 17:13 ` Eads, Gage
2019-04-03 17:13 ` Eads, Gage
2019-04-03 17:23 ` Thomas Monjalon
2019-04-03 17:23 ` Thomas Monjalon
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 3/8] test/stack: add stack test Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 4/8] test/stack: add stack perf test Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 5/8] stack: add lock-free stack implementation Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 6/8] stack: add C11 atomic implementation Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-02 11:11 ` Honnappa Nagarahalli
2019-04-02 11:11 ` Honnappa Nagarahalli
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 7/8] test/stack: add lock-free stack tests Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-01 21:14 ` [dpdk-dev] [PATCH v6 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-04-01 21:14 ` Gage Eads
2019-04-03 17:04 ` [dpdk-dev] [PATCH v6 0/8] Add stack library and new " Thomas Monjalon
2019-04-03 17:04 ` Thomas Monjalon
2019-04-03 17:10 ` Eads, Gage
2019-04-03 17:10 ` Eads, Gage
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 " Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 1/8] stack: introduce rte stack library Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 3/8] test/stack: add stack test Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 4/8] test/stack: add stack perf test Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 5/8] stack: add lock-free stack implementation Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 6/8] stack: add C11 atomic implementation Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 7/8] test/stack: add lock-free stack tests Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:09 ` [dpdk-dev] [PATCH v7 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-04-03 20:09 ` Gage Eads
2019-04-03 20:39 ` [dpdk-dev] [PATCH v7 0/8] Add stack library and new " Thomas Monjalon
2019-04-03 20:39 ` Thomas Monjalon
2019-04-03 20:49 ` Eads, Gage
2019-04-03 20:49 ` Eads, Gage
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 " Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 1/8] stack: introduce rte stack library Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 3/8] test/stack: add stack test Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 22:41 ` Thomas Monjalon
2019-04-03 22:41 ` Thomas Monjalon
2019-04-03 23:05 ` Eads, Gage
2019-04-03 23:05 ` Eads, Gage
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 4/8] test/stack: add stack perf test Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 5/8] stack: add lock-free stack implementation Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 6/8] stack: add C11 atomic implementation Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 7/8] test/stack: add lock-free stack tests Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 20:50 ` [dpdk-dev] [PATCH v8 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-04-03 20:50 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 0/8] Add stack library and new " Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 1/8] stack: introduce rte stack library Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-04 13:30 ` Thomas Monjalon
2019-04-04 13:30 ` Thomas Monjalon
2019-04-04 14:14 ` Eads, Gage
2019-04-04 14:14 ` Eads, Gage
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 3/8] test/stack: add stack test Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-04 7:34 ` Thomas Monjalon
2019-04-04 7:34 ` Thomas Monjalon
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 4/8] test/stack: add stack perf test Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 5/8] stack: add lock-free stack implementation Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 6/8] stack: add C11 atomic implementation Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 7/8] test/stack: add lock-free stack tests Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-03 23:20 ` [dpdk-dev] [PATCH v9 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-04-03 23:20 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 0/8] Add stack library and new " Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 1/8] stack: introduce rte stack library Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 2/8] mempool/stack: convert mempool to use rte stack Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 3/8] test/stack: add stack test Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 4/8] test/stack: add stack perf test Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 5/8] stack: add lock-free stack implementation Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 6/8] stack: add C11 atomic implementation Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 7/8] test/stack: add lock-free stack tests Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 10:01 ` [dpdk-dev] [PATCH v10 8/8] mempool/stack: add lock-free stack mempool handler Gage Eads
2019-04-04 10:01 ` Gage Eads
2019-04-04 15:42 ` [dpdk-dev] [PATCH v10 0/8] Add stack library and new " Thomas Monjalon
2019-04-04 15:42 ` 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=VE1PR08MB5149C7725C1BD074516BCABB98550@VE1PR08MB5149.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=Gavin.Hu@arm.com \
--cc=arybchenko@solarflare.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=gage.eads@intel.com \
--cc=konstantin.ananyev@intel.com \
--cc=nd@arm.com \
--cc=olivier.matz@6wind.com \
--cc=thomas@monjalon.net \
/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).