@@ -222,6 +222,10 @@ M: Joyce Kong <joyce.kong@arm.com>
F: lib/librte_eal/common/include/generic/rte_ticketlock.h
F: app/test/test_ticketlock.c
+MCSlock - EXPERIMENTAL
+M: Phil Yang <phil.yang@arm.com>
+F: lib/librte_eal/common/include/generic/rte_mcslock.h
+
ARM v7
M: Jan Viktorin <viktorin@rehivetech.com>
M: Gavin Hu <gavin.hu@arm.com>
@@ -63,6 +63,7 @@ The public API headers are grouped by topics:
- **locks**:
[atomic] (@ref rte_atomic.h),
+ [mcslock] (@ref rte_mcslock.h),
[rwlock] (@ref rte_rwlock.h),
[spinlock] (@ref rte_spinlock.h),
[ticketlock] (@ref rte_ticketlock.h),
@@ -54,6 +54,12 @@ New Features
Also, make sure to start the actual text at the margin.
=========================================================
+* **Added MCS lock library.**
+
+ Added MCS lock library. It 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.
Removed Items
-------------
@@ -21,7 +21,7 @@ INC += rte_reciprocal.h rte_fbarray.h rte_uuid.h
GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
GENERIC_INC += rte_memcpy.h rte_cpuflags.h
-GENERIC_INC += rte_spinlock.h rte_rwlock.h rte_ticketlock.h
+GENERIC_INC += rte_mcslock.h rte_spinlock.h rte_rwlock.h rte_ticketlock.h
GENERIC_INC += rte_vect.h rte_pause.h rte_io.h
# defined in mk/arch/$(RTE_ARCH)/rte.vars.mk
new file mode 100644
@@ -0,0 +1,169 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Arm Limited
+ */
+
+#ifndef _RTE_MCSLOCK_H_
+#define _RTE_MCSLOCK_H_
+
+/**
+ * @file
+ *
+ * RTE MCS lock
+ *
+ * This file defines the main data structure and APIs for MCS queued lock.
+ *
+ * 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.
+ */
+
+#include <rte_lcore.h>
+#include <rte_common.h>
+#include <rte_pause.h>
+
+/**
+ * The rte_mcslock_t type.
+ */
+typedef struct rte_mcslock {
+ struct rte_mcslock *next;
+ int locked; /* 1 if the queue locked, 0 otherwise */
+} rte_mcslock_t;
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: This API may change without prior notice
+ *
+ * Take the MCS lock.
+ *
+ * @param msl
+ * A pointer to the pointer of a MCS lock.
+ * When the lock is initialized or declared, the msl pointer should be
+ * set to NULL.
+ * @param me
+ * A pointer to a new node of MCS lock. Each CPU/thread acquiring the
+ * lock should use its 'own node'.
+ */
+static inline __rte_experimental void
+rte_mcslock_lock(rte_mcslock_t **msl, rte_mcslock_t *me)
+{
+ rte_mcslock_t *prev;
+
+ /* Init me node */
+ __atomic_store_n(&me->next, NULL, __ATOMIC_RELAXED);
+
+ /* If the queue is empty, the exchange operation is enough to acquire
+ * the lock. Hence, the exchange operation requires acquire semantics.
+ * The store to me->next above should complete before the node is
+ * visible to other CPUs/threads. Hence, the exchange operation requires
+ * release semantics as well.
+ */
+ prev = __atomic_exchange_n(msl, me, __ATOMIC_ACQ_REL);
+ if (likely(prev == NULL)) {
+ /* Queue was empty, no further action required,
+ * proceed with lock taken.
+ */
+ return;
+ }
+ __atomic_store_n(&me->locked, 1, __ATOMIC_RELAXED);
+ __atomic_store_n(&prev->next, me, __ATOMIC_RELAXED);
+
+ /* The while-load of me->locked should not move above the previous
+ * store to prev->next. Otherwise it will cause a deadlock. Need a
+ * store-load barrier.
+ */
+ __atomic_thread_fence(__ATOMIC_ACQ_REL);
+ /* If the lock has already been acquired, it first atomically
+ * places the node at the end of the queue and then proceeds
+ * to spin on me->locked until the previous lock holder resets
+ * the me->locked using mcslock_unlock().
+ */
+ while (__atomic_load_n(&me->locked, __ATOMIC_ACQUIRE))
+ rte_pause();
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: This API may change without prior notice
+ *
+ * Release the MCS lock.
+ *
+ * @param msl
+ * A pointer to the pointer of a MCS lock.
+ * @param me
+ * A pointer to the node of MCS lock passed in rte_mcslock_lock.
+ */
+static inline __rte_experimental void
+rte_mcslock_unlock(rte_mcslock_t **msl, rte_mcslock_t *me)
+{
+ /* Check if there are more nodes in the queue. */
+ if (likely(__atomic_load_n(&me->next, __ATOMIC_RELAXED) == NULL)) {
+ /* No, last member in the queue. */
+ rte_mcslock_t *save_me = __atomic_load_n(&me, __ATOMIC_RELAXED);
+
+ /* Release the lock by setting it to NULL */
+ if (likely(__atomic_compare_exchange_n(msl, &save_me, NULL, 0,
+ __ATOMIC_RELEASE, __ATOMIC_RELAXED)))
+ return;
+ /* More nodes added to the queue by other CPUs.
+ * Wait until the next pointer is set.
+ */
+ while (__atomic_load_n(&me->next, __ATOMIC_RELAXED) == NULL)
+ rte_pause();
+ }
+
+ /* Pass lock to next waiter. */
+ __atomic_store_n(&me->next->locked, 0, __ATOMIC_RELEASE);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: This API may change without prior notice
+ *
+ * Try to take the lock.
+ *
+ * @param msl
+ * A pointer to the pointer of a MCS lock.
+ * @param me
+ * A pointer to a new node of MCS lock.
+ * @return
+ * 1 if the lock is successfully taken; 0 otherwise.
+ */
+static inline __rte_experimental int
+rte_mcslock_trylock(rte_mcslock_t **msl, rte_mcslock_t *me)
+{
+ /* Init me node */
+ __atomic_store_n(&me->next, NULL, __ATOMIC_RELAXED);
+
+ /* Try to lock */
+ rte_mcslock_t *expected = NULL;
+
+ /* The lock can be taken only when the queue is empty. Hence,
+ * the compare-exchange operation requires acquire semantics.
+ * The store to me->next above should complete before the node
+ * is visible to other CPUs/threads. Hence, the compare-exchange
+ * operation requires release semantics as well.
+ */
+ return __atomic_compare_exchange_n(msl, &expected, me, 0,
+ __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: This API may change without prior notice
+ *
+ * Test if the lock is taken.
+ *
+ * @param msl
+ * A pointer to a MCS lock node.
+ * @return
+ * 1 if the lock is currently taken; 0 otherwise.
+ */
+static inline __rte_experimental int
+rte_mcslock_is_locked(rte_mcslock_t *msl)
+{
+ return (__atomic_load_n(&msl, __ATOMIC_RELAXED) != NULL);
+}
+
+#endif /* _RTE_MCSLOCK_H_ */
@@ -94,6 +94,7 @@ generic_headers = files(
'include/generic/rte_cpuflags.h',
'include/generic/rte_cycles.h',
'include/generic/rte_io.h',
+ 'include/generic/rte_mcslock.h',
'include/generic/rte_memcpy.h',
'include/generic/rte_pause.h',
'include/generic/rte_prefetch.h',