Add lock-free ring and mempool handler
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v8 Latest6 patches 1 replyIn review
- v76 patches 6 repliesSuperseded
- v66 patches 0 repliesSuperseded
Earlier versions · 1
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v5 | 6 patches | 0 replies | Superseded |
Changes in v8 from the cover letter
- Fixed two bugs in the generic implementation written as though the compare-and-swap would update the expected value on failure.
Patches in v8 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/6 | ring: add a pointer-width headtail structurelib/ lib/ lib/ | +291 | 0 replies | |
| 2/6 | ring: add a ring start markerlib/ | +3 | 0 replies | |
| 3/6 | ring: add a lock-free implementationlib/ lib/ lib/ +2 more | +1082 | 0 replies | |
| 4/6 | test_ring: add lock-free ring autotestapp/ | +38 | 0 replies | |
| 5/6 | test_ring_perf: add lock-free ring perf testapp/ | +16 | 0 replies | |
| 6/6 | mempool/ring: add lock-free ring handlersdoc/ drivers/ drivers/ +1 more | +68 | 0 replies |
Reviews trailers per patch
1 of 6 patches has a Reviewed-by or Acked-by.
| Patch | Andrew Rybchenko |
|---|---|
| 1/6 | |
| 2/6 | |
| 3/6 | |
| 4/6 | |
| 5/6 | |
| 6/6 | A-b |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH v8 0/6] Add lock-free ring and mempool handler
For some users, the rte ring's "non-preemptive" constraint is not acceptable; for example, if the application uses a mixture of pinned high-priority threads and multiplexed low-priority threads that share a mempool.
This patchset introduces a lock-free ring and a mempool based on it. The lock-free algorithm relies on a double-pointer compare-and-swap, so for 64-bit architectures it is currently limited to x86_64.
The ring uses more compare-and-swap atomic operations than the regular rte ring:
With no contention, an enqueue of n pointers uses (1 + n) CAS operations and a dequeue of n pointers uses 1. This algorithm has worse average-case performance than the regular rte ring (particularly a highly-contended ring with large bulk accesses), however:
- For applications with preemptible pthreads, the regular rte ring's worst-case performance (i.e. one thread being preempted in the update_tail() critical section) is much worse than the lock-free ring's.
- Software caching can mitigate the average case performance for ring-based algorithms. For example, a lock-free ring based mempool (a likely use case for this ring) with per-thread caching.
The lock-free ring is enabled via a new flag, RING_F_LF. For ease-of-use, existing ring enqueue/dequeue functions work with both standard and lock-free rings. This is also an experimental API, so RING_F_LF users must build with the ALLOW_EXPERIMENTAL_API flag.
This patchset also adds lock-free versions of ring_autotest and ring_perf_autotest, and a lock-free ring based mempool.
This patchset makes one API change; a deprecation notice was posted in a separate commit[1].
This patchset depends on the 128-bit compare-and-set patch[2].
[1] http://mails.dpdk.org/archives/dev/2019-February/124321.html
[2] http://mails.dpdk.org/archives/dev/2019-March/125751.html
v8:
- Fixed two bugs in the generic implementation written as though the compare-and-swap would update the expected value on failure.
v7:
- Added ARM copyright to rte_ring_generic.h and rte_ring_c11_mem.h, since the lock-free algorithm is based on ARM's lfring (see v5 notes)
- Rename __rte_ring_reload_tail() -> __rte_ring_lf_load_tail()
- Remove the unused return value from __rte_ring_lf_load_tail()
- Rename 'prev_tail' to 'next_tail' in the multi-producer lock-free enqueue
v6:
- Rebase patchset onto master (test/test/ -> app/test/)
v5:
- Incorporated lfring's enqueue and dequeue logic from
http://mails.dpdk.org/archives/dev/2019-January/124242.html
- Renamed non-blocking -> lock-free and NB -> LF to align with a similar change in the lock-free stack patchset:
http://mails.dpdk.org/archives/dev/2019-March/125797.html
- Added support for 32-bit architectures by using the full 32b of the modification counter and requiring LF rings on these architectures to be at least 1024 entries.
- Updated to the latest rte_atomic128_cmp_exchange() interface.
- Added ring start marker to struct rte_ring
v4:
- Split out nb_enqueue and nb_dequeue functions in generic and C11 versions, with the necessary memory ordering behavior for weakly consistent machines.
- Convert size_t variables (from v2) to uint64_t and no-longer-applicable comment about variably-sized ring indexes.
- Fix bug in nb_enqueue_mp that the breaks the non-blocking guarantee.
- Split the ring_ptr cast into two lines.
- Change the dependent patchset from the non-blocking stack patch series to one only containing the 128b CAS commit
v3:
- Avoid the ABI break by putting 64-bit head and tail values in the same cacheline as struct rte_ring's prod and cons members.
- Don't attempt to compile rte_atomic128_cmpset without ALLOW_EXPERIMENTAL_API, as this would break a large number of libraries.
- Add a helpful warning to __rte_ring_do_nb_enqueue_mp() in case someone tries to use RING_F_NB without the ALLOW_EXPERIMENTAL_API flag.
- Update the ring mempool to use experimental APIs
- Clarify that RINB_F_NB is only limited to x86_64 currently; e.g. ARMv8 has the ISA support for 128-bit CAS to eventually support it.
v2:
- Merge separate docs commit into patch #5
- Convert uintptr_t to size_t
- Add a compile-time check for the size of size_t
- Fix a space-after-typecast issue
- Fix an unnecessary-parentheses checkpatch warning
- Bump librte_ring's library version
Gage Eads (6):
ring: add a pointer-width headtail structure
ring: add a ring start marker
ring: add a lock-free implementation
test_ring: add lock-free ring autotest
test_ring_perf: add lock-free ring perf test
mempool/ring: add lock-free ring handlers
app/test/test_ring.c | 61 +-- app/test/test_ring_perf.c | 19 +- doc/guides/prog_guide/env_abstraction_layer.rst | 10 + drivers/mempool/ring/Makefile | 1 + drivers/mempool/ring/meson.build | 2 + drivers/mempool/ring/rte_mempool_ring.c | 58 ++- lib/librte_ring/rte_ring.c | 92 ++++- lib/librte_ring/rte_ring.h | 334 ++++++++++++++-- lib/librte_ring/rte_ring_c11_mem.h | 501 ++++++++++++++++++++++++ lib/librte_ring/rte_ring_generic.h | 487 ++++++++++++++++++++++- lib/librte_ring/rte_ring_version.map | 7 + 11 files changed, 1494 insertions(+), 78 deletions(-)
Signature · 1 line
2.13.6