[rtems commit] SMP: Add Mellor-Crummey and Scott (MCS) lock
Sebastian Huber
sebh at rtems.org
Thu May 19 09:51:19 UTC 2016
Module: rtems
Branch: master
Commit: 41ce30a9676341af2fe3688ea6160cc386d5d90f
Changeset: http://git.rtems.org/rtems/commit/?id=41ce30a9676341af2fe3688ea6160cc386d5d90f
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Wed May 18 14:34:26 2016 +0200
SMP: Add Mellor-Crummey and Scott (MCS) lock
Added only for evaluation purposes. We have to compare the performance
against the ticket lock on the interesting platforms via
smptests/smplock01.
The following GCC shortcoming affects the MCS lock:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66867
---
cpukit/score/Makefile.am | 1 +
cpukit/score/include/rtems/score/smplockmcs.h | 262 ++++++++++++++++++++++++++
cpukit/score/preinstall.am | 4 +
testsuites/smptests/smplock01/init.c | 173 +++++++++++++++--
4 files changed, 426 insertions(+), 14 deletions(-)
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 80eafc4..ac2f0b5 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -129,6 +129,7 @@ include_rtems_score_HEADERS += include/rtems/score/schedulerprioritysmpimpl.h
include_rtems_score_HEADERS += include/rtems/score/schedulerpriorityaffinitysmp.h
include_rtems_score_HEADERS += include/rtems/score/schedulersimplesmp.h
include_rtems_score_HEADERS += include/rtems/score/schedulerstrongapa.h
+include_rtems_score_HEADERS += include/rtems/score/smplockmcs.h
include_rtems_score_HEADERS += include/rtems/score/smplockstats.h
include_rtems_score_HEADERS += include/rtems/score/smplockticket.h
endif
diff --git a/cpukit/score/include/rtems/score/smplockmcs.h b/cpukit/score/include/rtems/score/smplockmcs.h
new file mode 100644
index 0000000..5a1ad23
--- /dev/null
+++ b/cpukit/score/include/rtems/score/smplockmcs.h
@@ -0,0 +1,262 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreSMPLock
+ *
+ * @brief SMP Lock API
+ */
+
+/*
+ * Copyright (c) 2016 embedded brains GmbH
+ *
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.org/license/LICENSE.
+ */
+
+#ifndef _RTEMS_SCORE_SMPLOCKMCS_H
+#define _RTEMS_SCORE_SMPLOCKMCS_H
+
+#include <rtems/score/cpuopts.h>
+
+#if defined(RTEMS_SMP)
+
+#include <rtems/score/atomic.h>
+#include <rtems/score/smplockstats.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+/**
+ * @addtogroup ScoreSMPLock
+ *
+ * @{
+ */
+
+/**
+ * @brief SMP Mellor-Crummey and Scott (MCS) lock context.
+ */
+typedef struct SMP_MCS_lock_Context {
+ /**
+ * @brief The next context on the queue if it exists.
+ */
+ union {
+ /**
+ * @brief The next context as an atomic unsigned integer pointer value.
+ */
+ Atomic_Uintptr atomic;
+
+ /**
+ * @brief The next context as a normal pointer.
+ *
+ * Only provided for debugging purposes.
+ */
+ struct SMP_MCS_lock_Context *normal;
+ } next;
+
+ /**
+ * @brief Indicates if the lock is owned or free in case a previous context
+ * exits on the queue.
+ *
+ * This field is initialized to a non-zero value. The previous lock owner
+ * (which is the owner of the previous context) will set it to zero during
+ * its lock release.
+ */
+ Atomic_Uint locked;
+
+#if defined(RTEMS_PROFILING)
+ SMP_lock_Stats_context Stats_context;
+
+ unsigned int queue_length;
+#endif
+} SMP_MCS_lock_Context;
+
+/**
+ * @brief SMP Mellor-Crummey and Scott (MCS) lock control.
+ */
+typedef struct {
+ /**
+ * @brief The queue tail context.
+ *
+ * The lock is free, in case this field is zero, otherwise it is locked by
+ * the owner of the queue head.
+ */
+ union {
+ /**
+ * @brief The queue tail context as an atomic unsigned integer pointer
+ * value.
+ */
+ Atomic_Uintptr atomic;
+
+ /**
+ * @brief The queue tail context as a normal pointer.
+ *
+ * Only provided for debugging purposes.
+ */
+ struct SMP_MCS_lock_Context *normal;
+ } queue;
+} SMP_MCS_lock_Control;
+
+/**
+ * @brief SMP MCS lock control initializer for static initialization.
+ */
+#define SMP_MCS_LOCK_INITIALIZER { { ATOMIC_INITIALIZER_UINTPTR( 0 ) } }
+
+/**
+ * @brief Initializes an SMP MCS lock.
+ *
+ * Concurrent initialization leads to unpredictable results.
+ *
+ * @param lock The SMP MCS lock control.
+ */
+static inline void _SMP_MCS_lock_Initialize( SMP_MCS_lock_Control *lock )
+{
+ _Atomic_Init_uintptr( &lock->queue.atomic, 0 );
+}
+
+/**
+ * @brief Destroys an SMP MCS lock.
+ *
+ * Concurrent destruction leads to unpredictable results.
+ *
+ * @param lock The SMP MCS lock control.
+ */
+static inline void _SMP_MCS_lock_Destroy( SMP_MCS_lock_Control *lock )
+{
+ (void) lock;
+}
+
+static inline void _SMP_MCS_lock_Do_acquire(
+ SMP_MCS_lock_Control *lock,
+ SMP_MCS_lock_Context *context
+#if defined(RTEMS_PROFILING)
+ ,
+ SMP_lock_Stats *stats
+#endif
+)
+{
+ SMP_MCS_lock_Context *previous;
+#if defined(RTEMS_PROFILING)
+ SMP_lock_Stats_acquire_context acquire_context;
+
+ _SMP_lock_Stats_acquire_begin( &acquire_context );
+ context->queue_length = 0;
+#endif
+
+ _Atomic_Store_uintptr( &context->next.atomic, 0, ATOMIC_ORDER_RELAXED );
+ _Atomic_Store_uint( &context->locked, 1, ATOMIC_ORDER_RELAXED );
+
+ previous = (SMP_MCS_lock_Context *) _Atomic_Exchange_uintptr(
+ &lock->queue.atomic,
+ (uintptr_t) context,
+ ATOMIC_ORDER_ACQ_REL
+ );
+
+ if ( previous != NULL ) {
+ unsigned int locked;
+
+ _Atomic_Store_uintptr(
+ &previous->next.atomic,
+ (uintptr_t) context,
+ ATOMIC_ORDER_RELAXED
+ );
+
+ do {
+ locked = _Atomic_Load_uint( &context->locked, ATOMIC_ORDER_ACQUIRE );
+ } while ( locked != 0 );
+ }
+
+#if defined(RTEMS_PROFILING)
+ _SMP_lock_Stats_acquire_end(
+ &acquire_context,
+ stats,
+ &context->Stats_context,
+ context->queue_length
+ );
+#endif
+}
+
+/**
+ * @brief Acquires an SMP MCS lock.
+ *
+ * This function will not disable interrupts. The caller must ensure that the
+ * current thread of execution is not interrupted indefinite once it obtained
+ * the SMP MCS lock.
+ *
+ * @param lock The SMP MCS lock control.
+ * @param context The SMP MCS lock context.
+ * @param stats The SMP lock statistics.
+ */
+#if defined(RTEMS_PROFILING)
+ #define _SMP_MCS_lock_Acquire( lock, context, stats ) \
+ _SMP_MCS_lock_Do_acquire( lock, context, stats )
+#else
+ #define _SMP_MCS_lock_Acquire( lock, context, stats ) \
+ _SMP_MCS_lock_Do_acquire( lock, context )
+#endif
+
+/**
+ * @brief Releases an SMP MCS lock.
+ *
+ * @param lock The SMP MCS lock control.
+ * @param context The SMP MCS lock context.
+ */
+static inline void _SMP_MCS_lock_Release(
+ SMP_MCS_lock_Control *lock,
+ SMP_MCS_lock_Context *context
+)
+{
+ SMP_MCS_lock_Context *next;
+
+ next = (SMP_MCS_lock_Context *) _Atomic_Load_uintptr(
+ &context->next.atomic,
+ ATOMIC_ORDER_RELAXED
+ );
+
+ if ( next == NULL ) {
+ uintptr_t expected;
+ bool success;
+
+ expected = (uintptr_t) context;
+ success = _Atomic_Compare_exchange_uintptr(
+ &lock->queue.atomic,
+ &expected,
+ 0,
+ ATOMIC_ORDER_RELEASE,
+ ATOMIC_ORDER_RELAXED
+ );
+
+ if ( success ) {
+#if defined(RTEMS_PROFILING)
+ _SMP_lock_Stats_release_update( &context->Stats_context );
+#endif
+ /* Nobody waits. So, we are done */
+ return;
+ }
+
+ do {
+ next = (SMP_MCS_lock_Context *) _Atomic_Load_uintptr(
+ &context->next.atomic,
+ ATOMIC_ORDER_RELAXED
+ );
+ } while ( next == NULL );
+ }
+
+#if defined(RTEMS_PROFILING)
+ next->queue_length = context->queue_length + 1;
+ _SMP_lock_Stats_release_update( &context->Stats_context );
+#endif
+
+ _Atomic_Store_uint( &next->locked, 0, ATOMIC_ORDER_RELEASE );
+}
+
+/**@}*/
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* RTEMS_SMP */
+
+#endif /* _RTEMS_SCORE_SMPLOCKMCS_H */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index 2e89f7a..9485140 100644
--- a/cpukit/score/preinstall.am
+++ b/cpukit/score/preinstall.am
@@ -451,6 +451,10 @@ $(PROJECT_INCLUDE)/rtems/score/schedulerstrongapa.h: include/rtems/score/schedul
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/schedulerstrongapa.h
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/schedulerstrongapa.h
+$(PROJECT_INCLUDE)/rtems/score/smplockmcs.h: include/rtems/score/smplockmcs.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+ $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/smplockmcs.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/smplockmcs.h
+
$(PROJECT_INCLUDE)/rtems/score/smplockstats.h: include/rtems/score/smplockstats.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/smplockstats.h
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/smplockstats.h
diff --git a/testsuites/smptests/smplock01/init.c b/testsuites/smptests/smplock01/init.c
index 8cc10fa..5eeb1ca 100644
--- a/testsuites/smptests/smplock01/init.c
+++ b/testsuites/smptests/smplock01/init.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2013-2014 embedded brains GmbH. All rights reserved.
+ * Copyright (c) 2013, 2016 embedded brains GmbH. All rights reserved.
*
* embedded brains GmbH
* Dornierstr. 4
@@ -17,6 +17,7 @@
#endif
#include <rtems/score/smplock.h>
+#include <rtems/score/smplockmcs.h>
#include <rtems/score/smpbarrier.h>
#include <rtems/score/atomic.h>
#include <rtems.h>
@@ -29,7 +30,7 @@ const char rtems_test_name[] = "SMPLOCK 1";
#define CPU_COUNT 32
-#define TEST_COUNT 5
+#define TEST_COUNT 10
typedef enum {
INITIAL,
@@ -45,20 +46,33 @@ typedef struct {
unsigned long counter[TEST_COUNT];
unsigned long test_counter[TEST_COUNT][CPU_COUNT];
SMP_lock_Control lock;
+#if defined(RTEMS_PROFILING)
+ SMP_lock_Stats mcs_stats;
+#endif
+ SMP_MCS_lock_Control mcs_lock;
} global_context;
static global_context context = {
.state = ATOMIC_INITIALIZER_UINT(INITIAL),
.barrier = SMP_BARRIER_CONTROL_INITIALIZER,
- .lock = SMP_LOCK_INITIALIZER("global")
+ .lock = SMP_LOCK_INITIALIZER("global ticket"),
+#if defined(RTEMS_PROFILING)
+ .mcs_stats = SMP_LOCK_STATS_INITIALIZER("global MCS"),
+#endif
+ .mcs_lock = SMP_MCS_LOCK_INITIALIZER
};
-static const char *test_names[TEST_COUNT] = {
- "aquire global lock with local counter",
- "aquire global lock with global counter",
- "aquire local lock with local counter",
- "aquire local lock with global counter",
- "aquire global lock with busy section"
+static const char * const test_names[TEST_COUNT] = {
+ "global ticket lock with local counter",
+ "global MCS lock with local counter",
+ "global ticket lock with global counter",
+ "global MCS lock with global counter",
+ "local ticket lock with local counter",
+ "local MCS lock with local counter",
+ "local ticket lock with global counter",
+ "local MCS lock with global counter",
+ "global ticket lock with busy section",
+ "global MCS lock with busy section"
};
static void stop_test_timer(rtems_id timer_id, void *arg)
@@ -119,6 +133,26 @@ static void test_1_body(
)
{
unsigned long counter = 0;
+ SMP_MCS_lock_Context lock_context;
+
+ while (assert_state(ctx, START_TEST)) {
+ _SMP_MCS_lock_Acquire(&ctx->mcs_lock, &lock_context, &ctx->mcs_stats);
+ _SMP_MCS_lock_Release(&ctx->mcs_lock, &lock_context);
+ ++counter;
+ }
+
+ ctx->test_counter[test][cpu_self] = counter;
+}
+
+static void test_2_body(
+ int test,
+ global_context *ctx,
+ SMP_barrier_State *bs,
+ unsigned int cpu_count,
+ unsigned int cpu_self
+)
+{
+ unsigned long counter = 0;
SMP_lock_Context lock_context;
while (assert_state(ctx, START_TEST)) {
@@ -131,7 +165,28 @@ static void test_1_body(
ctx->test_counter[test][cpu_self] = counter;
}
-static void test_2_body(
+static void test_3_body(
+ int test,
+ global_context *ctx,
+ SMP_barrier_State *bs,
+ unsigned int cpu_count,
+ unsigned int cpu_self
+)
+{
+ unsigned long counter = 0;
+ SMP_MCS_lock_Context lock_context;
+
+ while (assert_state(ctx, START_TEST)) {
+ _SMP_MCS_lock_Acquire(&ctx->mcs_lock, &lock_context, &ctx->mcs_stats);
+ ++ctx->counter[test];
+ _SMP_MCS_lock_Release(&ctx->mcs_lock, &lock_context);
+ ++counter;
+ }
+
+ ctx->test_counter[test][cpu_self] = counter;
+}
+
+static void test_4_body(
int test,
global_context *ctx,
SMP_barrier_State *bs,
@@ -156,7 +211,37 @@ static void test_2_body(
ctx->test_counter[test][cpu_self] = counter;
}
-static void test_3_body(
+static void test_5_body(
+ int test,
+ global_context *ctx,
+ SMP_barrier_State *bs,
+ unsigned int cpu_count,
+ unsigned int cpu_self
+)
+{
+ unsigned long counter = 0;
+#if defined(RTEMS_PROFILING)
+ SMP_lock_Stats stats;
+#endif
+ SMP_MCS_lock_Control lock;
+ SMP_MCS_lock_Context lock_context;
+
+ _SMP_lock_Stats_initialize(&stats, "local");
+ _SMP_MCS_lock_Initialize(&lock);
+
+ while (assert_state(ctx, START_TEST)) {
+ _SMP_MCS_lock_Acquire(&lock, &lock_context, &stats);
+ _SMP_MCS_lock_Release(&lock, &lock_context);
+ ++counter;
+ }
+
+ _SMP_MCS_lock_Destroy(&lock);
+ _SMP_lock_Stats_destroy(&stats);
+
+ ctx->test_counter[test][cpu_self] = counter;
+}
+
+static void test_6_body(
int test,
global_context *ctx,
SMP_barrier_State *bs,
@@ -185,6 +270,40 @@ static void test_3_body(
ctx->test_counter[test][cpu_self] = counter;
}
+static void test_7_body(
+ int test,
+ global_context *ctx,
+ SMP_barrier_State *bs,
+ unsigned int cpu_count,
+ unsigned int cpu_self
+)
+{
+ unsigned long counter = 0;
+#if defined(RTEMS_PROFILING)
+ SMP_lock_Stats stats;
+#endif
+ SMP_MCS_lock_Control lock;
+ SMP_MCS_lock_Context lock_context;
+
+ _SMP_lock_Stats_initialize(&stats, "local");
+ _SMP_MCS_lock_Initialize(&lock);
+
+ while (assert_state(ctx, START_TEST)) {
+ _SMP_MCS_lock_Acquire(&lock, &lock_context, &stats);
+
+ /* The counter value is not interesting, only the access to it */
+ ++ctx->counter[test];
+
+ _SMP_MCS_lock_Release(&lock, &lock_context);
+ ++counter;
+ }
+
+ _SMP_MCS_lock_Destroy(&lock);
+ _SMP_lock_Stats_destroy(&stats);
+
+ ctx->test_counter[test][cpu_self] = counter;
+}
+
static void busy_section(void)
{
int i;
@@ -194,7 +313,7 @@ static void busy_section(void)
}
}
-static void test_4_body(
+static void test_8_body(
int test,
global_context *ctx,
SMP_barrier_State *bs,
@@ -215,12 +334,38 @@ static void test_4_body(
ctx->test_counter[test][cpu_self] = counter;
}
+static void test_9_body(
+ int test,
+ global_context *ctx,
+ SMP_barrier_State *bs,
+ unsigned int cpu_count,
+ unsigned int cpu_self
+)
+{
+ unsigned long counter = 0;
+ SMP_MCS_lock_Context lock_context;
+
+ while (assert_state(ctx, START_TEST)) {
+ _SMP_MCS_lock_Acquire(&ctx->mcs_lock, &lock_context, &ctx->mcs_stats);
+ busy_section();
+ _SMP_MCS_lock_Release(&ctx->mcs_lock, &lock_context);
+ ++counter;
+ }
+
+ ctx->test_counter[test][cpu_self] = counter;
+}
+
static const test_body test_bodies[TEST_COUNT] = {
test_0_body,
test_1_body,
test_2_body,
test_3_body,
- test_4_body
+ test_4_body,
+ test_5_body,
+ test_6_body,
+ test_7_body,
+ test_8_body,
+ test_9_body
};
static void run_tests(
@@ -299,7 +444,7 @@ static void test(void)
}
}
- ctx->timeout = 10 * rtems_clock_get_ticks_per_second();
+ ctx->timeout = 5 * rtems_clock_get_ticks_per_second();
sc = rtems_timer_create(rtems_build_name('T', 'I', 'M', 'R'), &ctx->timer_id);
rtems_test_assert(sc == RTEMS_SUCCESSFUL);
More information about the vc
mailing list