From 05b7eec276a130cde39fed861ad4a9d1f01e876c Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Wed, 8 Jun 2016 15:18:14 +0200 Subject: score: Add an SMP sequence lock implementation --- cpukit/score/Makefile.am | 1 + cpukit/score/include/rtems/score/smplockseq.h | 173 +++++++++++++++ cpukit/score/preinstall.am | 4 + testsuites/smptests/smplock01/init.c | 60 ++++- testsuites/smptests/smplock01/smplock01.scn | 306 ++++++++++++++++++++++++-- 5 files changed, 520 insertions(+), 24 deletions(-) create mode 100644 cpukit/score/include/rtems/score/smplockseq.h diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 29e822d47d..537cf60c1a 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -82,6 +82,7 @@ include_rtems_score_HEADERS += include/rtems/score/schedulersmpimpl.h include_rtems_score_HEADERS += include/rtems/score/smp.h include_rtems_score_HEADERS += include/rtems/score/smpbarrier.h include_rtems_score_HEADERS += include/rtems/score/smplock.h +include_rtems_score_HEADERS += include/rtems/score/smplockseq.h include_rtems_score_HEADERS += include/rtems/score/smpimpl.h include_rtems_score_HEADERS += include/rtems/score/stack.h include_rtems_score_HEADERS += include/rtems/score/stackimpl.h diff --git a/cpukit/score/include/rtems/score/smplockseq.h b/cpukit/score/include/rtems/score/smplockseq.h new file mode 100644 index 0000000000..6fe7b7afa3 --- /dev/null +++ b/cpukit/score/include/rtems/score/smplockseq.h @@ -0,0 +1,173 @@ +/** + * @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_SMPLOCKSEQ_H +#define _RTEMS_SCORE_SMPLOCKSEQ_H + +#include + +#if defined(RTEMS_SMP) + +#include + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** + * @addtogroup ScoreSMPLock + * + * @{ + */ + +/** + * @brief SMP sequence lock control. + * + * The sequence lock offers a consistent data set for readers in the presence + * of at most one concurrent writer. Due to the read-modify-write operation in + * _SMP_sequence_lock_Read_retry() the data corresponding to the last written + * sequence number is observed. To allow multiple writers an additional SMP + * lock is necessary to serialize writes. + * + * See also Hans-J. Boehm, HP Laboratories, + * "Can Seqlocks Get Along With Programming Language Memory Models?", + * http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf + */ +typedef struct { + /** + * @brief The sequence number. + * + * An odd value indicates that a write is in progress. + */ + Atomic_Uint sequence; +} SMP_sequence_lock_Control; + +/** + * @brief SMP sequence lock control initializer for static initialization. + */ +#define SMP_SEQUENCE_LOCK_INITIALIZER { ATOMIC_INITIALIZER_UINT( 0 ) } + +/** + * @brief Initializes an SMP sequence lock. + * + * Concurrent initialization leads to unpredictable results. + * + * @param lock The SMP sequence lock control. + */ +static inline void _SMP_sequence_lock_Initialize( SMP_sequence_lock_Control *lock ) +{ + _Atomic_Init_uint( &lock->sequence, 0 ); +} + +/** + * @brief Destroys an SMP sequence lock. + * + * Concurrent destruction leads to unpredictable results. + * + * @param lock The SMP sequence lock control. + */ +static inline void _SMP_sequence_lock_Destroy( SMP_sequence_lock_Control *lock ) +{ + (void) lock; +} + +/** + * @brief Begins an SMP sequence lock write operation. + * + * This function will not disable interrupts. The caller must ensure that the + * current thread of execution is not interrupted indefinite since this would + * starve readers. + * + * @param lock The SMP sequence lock control. + * + * @return The current sequence number. + */ +static inline unsigned int _SMP_sequence_lock_Write_begin( + SMP_sequence_lock_Control *lock +) +{ + unsigned int seq; + + seq = _Atomic_Load_uint( &lock->sequence, ATOMIC_ORDER_RELAXED ); + _Atomic_Store_uint( &lock->sequence, seq + 1, ATOMIC_ORDER_RELAXED ); + + /* There is no atomic store with acquire/release semantics */ + _Atomic_Fence( ATOMIC_ORDER_ACQ_REL ); + + return seq; +} + +/** + * @brief Ends an SMP sequence lock write operation. + * + * @param lock The SMP sequence lock control. + * @param seq The sequence number returned by _SMP_sequence_lock_Write_begin(). + */ +static inline void _SMP_sequence_lock_Write_end( + SMP_sequence_lock_Control *lock, + unsigned int seq +) +{ + _Atomic_Store_uint( &lock->sequence, seq + 2, ATOMIC_ORDER_RELEASE ); +} + +/** + * @brief Begins an SMP sequence lock read operation. + * + * This function will not disable interrupts. + * + * @param lock The SMP sequence lock control. + * + * @return The current sequence number. + */ +static inline unsigned int _SMP_sequence_lock_Read_begin( + const SMP_sequence_lock_Control *lock +) +{ + return _Atomic_Load_uint( &lock->sequence, ATOMIC_ORDER_ACQUIRE ); +} + +/** + * @brief Ends an SMP sequence lock read operation and indicates if a retry is + * necessary. + * + * @param lock The SMP sequence lock control. + * @param seq The sequence number returned by _SMP_sequence_lock_Read_begin(). + * + * @retval true The read operation must be retried with a call to + * _SMP_sequence_lock_Read_begin(). + * @retval false Otherwise. + */ +static inline bool _SMP_sequence_lock_Read_retry( + SMP_sequence_lock_Control *lock, + unsigned int seq +) +{ + unsigned int seq2; + + seq2 = _Atomic_Fetch_add_uint( &lock->sequence, 0, ATOMIC_ORDER_RELEASE ); + return seq != seq2 || seq % 2 != 0; +} + +/**@}*/ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* RTEMS_SMP */ + +#endif /* _RTEMS_SCORE_SMPLOCKSEQ_H */ diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am index 2ed07b91e8..1ba332d098 100644 --- a/cpukit/score/preinstall.am +++ b/cpukit/score/preinstall.am @@ -296,6 +296,10 @@ $(PROJECT_INCLUDE)/rtems/score/smplock.h: include/rtems/score/smplock.h $(PROJEC $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/smplock.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/smplock.h +$(PROJECT_INCLUDE)/rtems/score/smplockseq.h: include/rtems/score/smplockseq.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/smplockseq.h +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/smplockseq.h + $(PROJECT_INCLUDE)/rtems/score/smpimpl.h: include/rtems/score/smpimpl.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/smpimpl.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/smpimpl.h diff --git a/testsuites/smptests/smplock01/init.c b/testsuites/smptests/smplock01/init.c index 5eeb1ca347..62397a3b27 100644 --- a/testsuites/smptests/smplock01/init.c +++ b/testsuites/smptests/smplock01/init.c @@ -18,6 +18,7 @@ #include #include +#include #include #include #include @@ -30,7 +31,7 @@ const char rtems_test_name[] = "SMPLOCK 1"; #define CPU_COUNT 32 -#define TEST_COUNT 10 +#define TEST_COUNT 11 typedef enum { INITIAL, @@ -50,6 +51,11 @@ typedef struct { SMP_lock_Stats mcs_stats; #endif SMP_MCS_lock_Control mcs_lock; + SMP_sequence_lock_Control seq_lock; + char unused_space_for_cache_line_separation_0[128]; + int a; + char unused_space_for_cache_line_separation_1[128]; + int b; } global_context; static global_context context = { @@ -59,7 +65,8 @@ static global_context context = { #if defined(RTEMS_PROFILING) .mcs_stats = SMP_LOCK_STATS_INITIALIZER("global MCS"), #endif - .mcs_lock = SMP_MCS_LOCK_INITIALIZER + .mcs_lock = SMP_MCS_LOCK_INITIALIZER, + .seq_lock = SMP_SEQUENCE_LOCK_INITIALIZER }; static const char * const test_names[TEST_COUNT] = { @@ -72,7 +79,8 @@ static const char * const test_names[TEST_COUNT] = { "local ticket lock with global counter", "local MCS lock with global counter", "global ticket lock with busy section", - "global MCS lock with busy section" + "global MCS lock with busy section", + "sequence lock" }; static void stop_test_timer(rtems_id timer_id, void *arg) @@ -355,6 +363,49 @@ static void test_9_body( ctx->test_counter[test][cpu_self] = counter; } +static void test_10_body( + int test, + global_context *ctx, + SMP_barrier_State *bs, + unsigned int cpu_count, + unsigned int cpu_self +) +{ + unsigned long counter = 0; + unsigned long seq; + + if (cpu_self == 0) { + while (assert_state(ctx, START_TEST)) { + seq = _SMP_sequence_lock_Write_begin(&ctx->seq_lock); + + ctx->a = counter; + ctx->b = counter; + + _SMP_sequence_lock_Write_end(&ctx->seq_lock, seq); + + ++counter; + } + } else { + while (assert_state(ctx, START_TEST)) { + unsigned long a; + unsigned long b; + + do { + seq = _SMP_sequence_lock_Read_begin(&ctx->seq_lock); + + a = ctx->a; + b = ctx->b; + + } while (_SMP_sequence_lock_Read_retry(&ctx->seq_lock, seq)); + + ++counter; + rtems_test_assert(a == b); + } + } + + ctx->test_counter[test][cpu_self] = counter; +} + static const test_body test_bodies[TEST_COUNT] = { test_0_body, test_1_body, @@ -365,7 +416,8 @@ static const test_body test_bodies[TEST_COUNT] = { test_6_body, test_7_body, test_8_body, - test_9_body + test_9_body, + test_10_body }; static void run_tests( diff --git a/testsuites/smptests/smplock01/smplock01.scn b/testsuites/smptests/smplock01/smplock01.scn index d9189f956a..b13bab0e45 100644 --- a/testsuites/smptests/smplock01/smplock01.scn +++ b/testsuites/smptests/smplock01/smplock01.scn @@ -1,22 +1,288 @@ *** BEGIN OF TEST SMPLOCK 1 *** -aquire global lock with local counter - processor 0, local counter 15964 - processor 1, local counter 99982377 - global counter 0, sum of local counter 99998341 -aquire global lock with global counter - processor 0, local counter 166073 - processor 1, local counter 99569103 - global counter 99735176, sum of local counter 99735176 -aquire local lock with local counter - processor 0, local counter 148133948 - processor 1, local counter 148148108 - global counter 0, sum of local counter 296282056 -aquire local lock with global counter - processor 0, local counter 55938783 - processor 1, local counter 55951781 - global counter 55951781, sum of local counter 111890564 -aquire global lock with busy section - processor 0, local counter 10694328 - processor 1, local counter 10694346 - global counter 0, sum of local counter 21388674 +global ticket lock with local counter + processor 0, local counter 830091 + processor 1, local counter 830090 + processor 2, local counter 830091 + processor 3, local counter 830091 + processor 4, local counter 830091 + processor 5, local counter 830091 + processor 6, local counter 830091 + processor 7, local counter 830091 + processor 8, local counter 830089 + processor 9, local counter 830088 + processor 10, local counter 830090 + processor 11, local counter 830090 + processor 12, local counter 830090 + processor 13, local counter 830092 + processor 14, local counter 830093 + processor 15, local counter 830092 + processor 16, local counter 830092 + processor 17, local counter 830092 + processor 18, local counter 830089 + processor 19, local counter 830092 + processor 20, local counter 830090 + processor 21, local counter 830090 + processor 22, local counter 830090 + processor 23, local counter 830092 + global counter 0, sum of local counter 19922178 +global MCS lock with local counter + processor 0, local counter 1579723 + processor 1, local counter 1580054 + processor 2, local counter 1579890 + processor 3, local counter 1579777 + processor 4, local counter 1579884 + processor 5, local counter 1580005 + processor 6, local counter 1578632 + processor 7, local counter 1578637 + processor 8, local counter 1578774 + processor 9, local counter 1578759 + processor 10, local counter 1580282 + processor 11, local counter 1579885 + processor 12, local counter 1580378 + processor 13, local counter 1580043 + processor 14, local counter 1580115 + processor 15, local counter 1580113 + processor 16, local counter 1579911 + processor 17, local counter 1579993 + processor 18, local counter 1580032 + processor 19, local counter 1579588 + processor 20, local counter 1580049 + processor 21, local counter 1580048 + processor 22, local counter 1578484 + processor 23, local counter 1580013 + global counter 0, sum of local counter 37913069 +global ticket lock with global counter + processor 0, local counter 784729 + processor 1, local counter 784730 + processor 2, local counter 784730 + processor 3, local counter 784730 + processor 4, local counter 784731 + processor 5, local counter 784730 + processor 6, local counter 784731 + processor 7, local counter 784730 + processor 8, local counter 784731 + processor 9, local counter 784729 + processor 10, local counter 784729 + processor 11, local counter 784730 + processor 12, local counter 784731 + processor 13, local counter 784729 + processor 14, local counter 784728 + processor 15, local counter 784730 + processor 16, local counter 784729 + processor 17, local counter 784730 + processor 18, local counter 784730 + processor 19, local counter 784729 + processor 20, local counter 784729 + processor 21, local counter 784729 + processor 22, local counter 784729 + processor 23, local counter 784731 + global counter 18833514, sum of local counter 18833514 +global MCS lock with global counter + processor 0, local counter 947856 + processor 1, local counter 947857 + processor 2, local counter 947857 + processor 3, local counter 947855 + processor 4, local counter 947858 + processor 5, local counter 947857 + processor 6, local counter 947856 + processor 7, local counter 947856 + processor 8, local counter 947856 + processor 9, local counter 947856 + processor 10, local counter 947857 + processor 11, local counter 947856 + processor 12, local counter 947855 + processor 13, local counter 947857 + processor 14, local counter 947857 + processor 15, local counter 947855 + processor 16, local counter 947856 + processor 17, local counter 947855 + processor 18, local counter 947858 + processor 19, local counter 947857 + processor 20, local counter 947858 + processor 21, local counter 947857 + processor 22, local counter 947857 + processor 23, local counter 947857 + global counter 22748556, sum of local counter 22748556 +local ticket lock with local counter + processor 0, local counter 77155869 + processor 1, local counter 77158831 + processor 2, local counter 77081105 + processor 3, local counter 77082737 + processor 4, local counter 77075777 + processor 5, local counter 77076154 + processor 6, local counter 77065268 + processor 7, local counter 77066500 + processor 8, local counter 77106686 + processor 9, local counter 77107321 + processor 10, local counter 77060207 + processor 11, local counter 77062079 + processor 12, local counter 77059638 + processor 13, local counter 77059931 + processor 14, local counter 77056750 + processor 15, local counter 77057813 + processor 16, local counter 76659137 + processor 17, local counter 76659205 + processor 18, local counter 76669140 + processor 19, local counter 76670415 + processor 20, local counter 76674221 + processor 21, local counter 76674630 + processor 22, local counter 76434805 + processor 23, local counter 76434361 + global counter 0, sum of local counter 1846208580 +local MCS lock with local counter + processor 0, local counter 44963740 + processor 1, local counter 45045357 + processor 2, local counter 45023035 + processor 3, local counter 45021994 + processor 4, local counter 44912701 + processor 5, local counter 44951749 + processor 6, local counter 45090697 + processor 7, local counter 45089463 + processor 8, local counter 45015619 + processor 9, local counter 45088716 + processor 10, local counter 45064955 + processor 11, local counter 45063568 + processor 12, local counter 44966963 + processor 13, local counter 45002743 + processor 14, local counter 45127830 + processor 15, local counter 45126512 + processor 16, local counter 44947194 + processor 17, local counter 44992882 + processor 18, local counter 45006760 + processor 19, local counter 45005553 + processor 20, local counter 44880447 + processor 21, local counter 44889042 + processor 22, local counter 45036454 + processor 23, local counter 45036288 + global counter 0, sum of local counter 1080350262 +local ticket lock with global counter + processor 0, local counter 3962116 + processor 1, local counter 3963441 + processor 2, local counter 3963482 + processor 3, local counter 3963367 + processor 4, local counter 3962978 + processor 5, local counter 3963102 + processor 6, local counter 3962979 + processor 7, local counter 3962911 + processor 8, local counter 3962974 + processor 9, local counter 3963125 + processor 10, local counter 3963056 + processor 11, local counter 3963093 + processor 12, local counter 3962996 + processor 13, local counter 3963100 + processor 14, local counter 3963096 + processor 15, local counter 3963028 + processor 16, local counter 3967076 + processor 17, local counter 3967251 + processor 18, local counter 3967222 + processor 19, local counter 3967093 + processor 20, local counter 3972862 + processor 21, local counter 3972917 + processor 22, local counter 3967217 + processor 23, local counter 3967220 + global counter 7095791, sum of local counter 95157702 +local MCS lock with global counter + processor 0, local counter 3849478 + processor 1, local counter 3860113 + processor 2, local counter 3966891 + processor 3, local counter 3966750 + processor 4, local counter 3973618 + processor 5, local counter 4014013 + processor 6, local counter 3914674 + processor 7, local counter 3914601 + processor 8, local counter 3910536 + processor 9, local counter 3924908 + processor 10, local counter 3995362 + processor 11, local counter 3995130 + processor 12, local counter 3909912 + processor 13, local counter 3923977 + processor 14, local counter 3995941 + processor 15, local counter 3995667 + processor 16, local counter 3842753 + processor 17, local counter 3852728 + processor 18, local counter 3956029 + processor 19, local counter 3955977 + processor 20, local counter 3961870 + processor 21, local counter 4001067 + processor 22, local counter 3911767 + processor 23, local counter 3911724 + global counter 8503087, sum of local counter 94505486 +global ticket lock with busy section + processor 0, local counter 614377 + processor 1, local counter 614376 + processor 2, local counter 614377 + processor 3, local counter 614377 + processor 4, local counter 614377 + processor 5, local counter 614378 + processor 6, local counter 614377 + processor 7, local counter 614377 + processor 8, local counter 614377 + processor 9, local counter 614376 + processor 10, local counter 614378 + processor 11, local counter 614377 + processor 12, local counter 614377 + processor 13, local counter 614377 + processor 14, local counter 614377 + processor 15, local counter 614376 + processor 16, local counter 614377 + processor 17, local counter 614377 + processor 18, local counter 614377 + processor 19, local counter 614378 + processor 20, local counter 614378 + processor 21, local counter 614377 + processor 22, local counter 614377 + processor 23, local counter 614377 + global counter 0, sum of local counter 14745049 +global MCS lock with busy section + processor 0, local counter 552660 + processor 1, local counter 552661 + processor 2, local counter 552659 + processor 3, local counter 552659 + processor 4, local counter 552660 + processor 5, local counter 552659 + processor 6, local counter 552659 + processor 7, local counter 552660 + processor 8, local counter 552660 + processor 9, local counter 552660 + processor 10, local counter 552660 + processor 11, local counter 552659 + processor 12, local counter 552660 + processor 13, local counter 552659 + processor 14, local counter 552660 + processor 15, local counter 552661 + processor 16, local counter 552660 + processor 17, local counter 552659 + processor 18, local counter 552660 + processor 19, local counter 552661 + processor 20, local counter 552660 + processor 21, local counter 552661 + processor 22, local counter 552660 + processor 23, local counter 552661 + global counter 0, sum of local counter 13263838 +sequence lock + processor 0, local counter 12138641 + processor 1, local counter 8 + processor 2, local counter 64 + processor 3, local counter 89 + processor 4, local counter 208 + processor 5, local counter 227 + processor 6, local counter 69 + processor 7, local counter 82 + processor 8, local counter 2019 + processor 9, local counter 2017 + processor 10, local counter 1914 + processor 11, local counter 2008 + processor 12, local counter 1890 + processor 13, local counter 1902 + processor 14, local counter 1734 + processor 15, local counter 1701 + processor 16, local counter 2198 + processor 17, local counter 2176 + processor 18, local counter 2011 + processor 19, local counter 2047 + processor 20, local counter 2072 + processor 21, local counter 2084 + processor 22, local counter 1866 + processor 23, local counter 1849 + global counter 0, sum of local counter 12170876 *** END OF TEST SMPLOCK 1 *** -- cgit v1.2.3