[dpdk-dev] [PATCH v3 0/3] MCS queued lock implementation

[Phil Yang <phil.yang@arm.com>]

This patch set added MCS lock library and its unit test.

The MCS lock (proposed by John M. Mellor-Crummey and Michael L. Scott) provides
scalability by spinning on a CPU/thread local variable which avoids expensive
cache bouncings. It provides fairness by maintaining a list of acquirers and
passing the lock to each CPU/thread in the order they acquired the lock.

References:
1. http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf
2. https://lwn.net/Articles/590243/

Micro benchmark (1M iterations):
---------------------------------------------------------------------------------------------------------
MCS lock                          | spinlock                          | ticket lock
---------------------------------------------------------------------------------------------------------
Test with lock on 20 cores...     | Test with lock on 20 cores...     | Test with lock on 20 cores...
Core [0]  Cost Time = 4221256 us  | Core [0]  Cost Time = 1948341 us  | Core [0]  cost time = 25388253 us
Core [14] Cost Time = 4221260 us  | Core [14] Cost Time = 5136122 us  | Core [14] cost time = 25389593 us
Core [28] Cost Time = 4221239 us  | Core [28] Cost Time = 4849188 us  | Core [28] cost time = 25387857 us
Core [29] Cost Time = 4221190 us  | Core [29] Cost Time = 3424137 us  | Core [29] cost time = 25387625 us
Core [30] Cost Time = 4221249 us  | Core [30] Cost Time = 3455813 us  | Core [30] cost time = 25387662 us
Core [31] Cost Time = 4221090 us  | Core [31] Cost Time = 4742221 us  | Core [31] cost time = 25387968 us
Core [32] Cost Time = 4221169 us  | Core [32] Cost Time = 4955011 us  | Core [32] cost time = 25387991 us
Core [33] Cost Time = 4221192 us  | Core [33] Cost Time = 3807345 us  | Core [33] cost time = 25387679 us
Core [34] Cost Time = 4221209 us  | Core [34] Cost Time = 5011178 us  | Core [34] cost time = 25389370 us
Core [35] Cost Time = 4221232 us  | Core [35] Cost Time = 4983119 us  | Core [35] cost time = 25387899 us
Core [36] Cost Time = 4221260 us  | Core [36] Cost Time = 5178121 us  | Core [36] cost time = 25389593 us
Core [37] Cost Time = 4221203 us  | Core [37] Cost Time = 5148525 us  | Core [37] cost time = 25389347 us
Core [38] Cost Time = 4221229 us  | Core [38] Cost Time = 5186183 us  | Core [38] cost time = 25389363 us
Core [39] Cost Time = 4221253 us  | Core [39] Cost Time = 4650058 us  | Core [39] cost time = 25387948 us
Core [40] Cost Time = 4221121 us  | Core [40] Cost Time = 4682572 us  | Core [40] cost time = 25387857 us
Core [41] Cost Time = 4221238 us  | Core [41] Cost Time = 4327049 us  | Core [41] cost time = 25389261 us
Core [42] Cost Time = 4221234 us  | Core [42] Cost Time = 5141807 us  | Core [42] cost time = 25389284 us
Core [43] Cost Time = 4221218 us  | Core [43] Cost Time = 3346939 us  | Core [43] cost time = 25387967 us
Core [44] Cost Time = 4221220 us  | Core [44] Cost Time = 2768786 us  | Core [44] cost time = 25387771 us
Core [45] Cost Time = 4221221 us  | Core [45] Cost Time = 3525078 us  | Core [45] cost time = 25389044 us
---------------------------------------------------------------------------------------------------------
Total Cost Time = 84424283 us     | Total Cost Time = 86267593 us     | Total cost time = 507769332 us
---------------------------------------------------------------------------------------------------------

Summary:
1. In the lock contention scenario, MCS lock and ticket lock can grantee
the fairness for each lock acquirers. MCS lock has better performance
than ticket lock.
2. Spinlock is fast, however spinlock has the unfairness issue in the
lock contention case. This will make some lock acquirers got starved.
MCS lock is fast and fair comparing with spinlock.

v3
Fix __rte_experimental coding style warning.

v2
1. Lowercase the algrithom author's name; (David Marchand)
2. Add the load test on master core to align with other locks test; (David Marchand)
3. Enlarge the test iterations from 10K to 1M; (Ananyev Konstantin)
4. Fixed potential deadlock issues.

v1
Initial version.


Phil Yang (3):
  eal/mcslock: add mcs queued lock implementation
  eal/mcslock: use generic msc queued lock on all arch
  test/mcslock: add mcs queued lock unit test

 MAINTAINERS                                        |   5 +
 app/test/Makefile                                  |   1 +
 app/test/autotest_data.py                          |   6 +
 app/test/autotest_test_funcs.py                    |  32 +++
 app/test/meson.build                               |   2 +
 app/test/test_mcslock.c                            | 251 +++++++++++++++++++++
 doc/api/doxy-api-index.md                          |   1 +
 doc/guides/rel_notes/release_19_08.rst             |   6 +
 lib/librte_eal/common/Makefile                     |   2 +-
 .../common/include/arch/arm/rte_mcslock.h          |  23 ++
 .../common/include/arch/ppc_64/rte_mcslock.h       |  19 ++
 .../common/include/arch/x86/rte_mcslock.h          |  19 ++
 .../common/include/generic/rte_mcslock.h           | 179 +++++++++++++++
 lib/librte_eal/common/meson.build                  |   1 +
 14 files changed, 546 insertions(+), 1 deletion(-)
 create mode 100644 app/test/test_mcslock.c
 create mode 100644 lib/librte_eal/common/include/arch/arm/rte_mcslock.h
 create mode 100644 lib/librte_eal/common/include/arch/ppc_64/rte_mcslock.h
 create mode 100644 lib/librte_eal/common/include/arch/x86/rte_mcslock.h
 create mode 100644 lib/librte_eal/common/include/generic/rte_mcslock.h

-- 
2.7.4