score: Add an SMP sequence lock implementation

5 files changed, 520 insertions, 24 deletions

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 <rtems/score/cpuopts.h>
+
+#if defined(RTEMS_SMP)
+
+#include <rtems/score/atomic.h>
+
+#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 <rtems/score/smplock.h>
 #include <rtems/score/smplockmcs.h>
+#include <rtems/score/smplockseq.h>
 #include <rtems/score/smpbarrier.h>
 #include <rtems/score/atomic.h>
 #include <rtems.h>
@@ -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 ***