Fixing SC-DRF tests (working): test_mm_sc_drf_00 (atomic + spin-lock) and test_mm_sc_drf_01 (mutex lock + condition-wait)

Turns out SC-DRF does work very well on modified non-atomic memory within
an atomic or locked-mutex acquire/release critical block.

Issues were within the test code itself.

Both tests follow the same 'waiting for their turn' semantics.
- test_mm_sc_drf_00 using atomic + spin-lock
- test_mm_sc_drf_01 using mutex lock + condition-wait

+++

On raspi4b-aarch64 (4 cores, 1.5GHz, loops=100, DEBUG=OFF, -O3)
'test_mm_sc_drf_00' is extremely slow using ~18s,
while 'test_mm_sc_drf_01' uses ~0.6s only.

On raspi3b-arm32 (4 cores, 1.4GHz, loops=100, DEBUG=OFF, -O3)
'test_mm_sc_drf_00' is extremely slow using ~36s,
while 'test_mm_sc_drf_01' uses ~0.9s only.

"./build-*/test/direct_bt/test_mm_sc_drf_00 -loop 100"

2 files changed, 130 insertions, 78 deletions

diff --git a/test/direct_bt/test_mm_sc_drf_00.cpp b/test/direct_bt/test_mm_sc_drf_00.cpp
index 3538597e..505cbcc1 100644
--- a/test/direct_bt/test_mm_sc_drf_00.cpp
+++ b/test/direct_bt/test_mm_sc_drf_00.cpp
@@ -15,7 +15,23 @@
 
 using namespace direct_bt;
 
-// Test examples.
+static int loops = 10;
+
+/**
+ * test_mm_sc_drf_00: Testing SC-DRF non-atomic global read and write within an atomic acquire/release critical block.
+ * <p>
+ * Modified non-atomic memory within the atomic acquire (load) and release (store) block,
+ * must be visible for all threads according to memory model (MM) Sequentially Consistent (SC) being data-race-free (DRF).
+ * <br>
+ * See Herb Sutter's 2013-12-23 slides p19, first box "It must be impossible for the assertion to fail – wouldn’t be SC.".
+ * </p>
+ * <p>
+ * This test's threads utilize a spin-lock, waiting for their turn.
+ * Such busy cycles were chosen to simplify the test and are not recommended
+ * as they expose poor performance on a high thread-count and hence long 'working thread pipe'.
+ * </p>
+ * See 'test_mm_sc_drf_01' implementing same test using mutex-lock and condition wait.
+ */
 class Cppunit_tests : public Cppunit {
   private:
     enum Defaults : int {
@@ -29,14 +45,14 @@ class Cppunit_tests : public Cppunit {
     int array[array_size] = { 0 };
     sc_atomic_int sync_value;
 
-    void reset(int v) {
+    void reset(int v1, int array_value) {
         int _sync_value = sync_value; // SC-DRF acquire atomic
         (void) _sync_value;
-        value1 = v;
+        value1 = v1;
         for(int i=0; i<array_size; i++) {
-            array[i] = v;
+            array[i] = array_value;
         }
-        sync_value = v; // SC-DRF release atomic
+        sync_value = v1; // SC-DRF release atomic
     }
 
     void putThreadType01(int _len, int startValue) {
@@ -44,15 +60,12 @@ class Cppunit_tests : public Cppunit {
         {
             int _sync_value = sync_value; // SC-DRF acquire atomic
             _sync_value = startValue;
+            for(int i=0; i<len; i++) {
+                array[i] = _sync_value+i;
+            }
             value1 = startValue;
             sync_value = _sync_value; // SC-DRF release atomic
         }
-
-        for(int i=0; i<len; i++) {
-            int _sync_value = sync_value; // SC-DRF acquire atomic
-            array[i] = _sync_value+i;
-            sync_value = _sync_value; // SC-DRF release atomic
-        }
     }
     void getThreadType01(const std::string msg, int _len, int startValue) {
         const int len = std::min(number(array_size), _len);
@@ -71,30 +84,42 @@ class Cppunit_tests : public Cppunit {
     }
 
     void putThreadType11(int indexAndValue) {
-        const int idx = std::min(number(array_size), indexAndValue);
+        const int idx = std::min(number(array_size)-1, indexAndValue);
         {
-            int _sync_value = sync_value; // SC-DRF acquire atomic
+            // idx is encoded on sync_value (v) as follows
+            //   v > 0: get @ idx = v -1
+            //   v < 0: put @ idx = abs(v) -1
+            int _sync_value;
+            // SC-DRF acquire atomic with spin-lock waiting for encoded idx
+            do {
+                _sync_value = sync_value;
+            } while( idx != (_sync_value * -1) - 1 );
+            // fprintf(stderr, "putThreadType11.done @ %d (has %d, exp %d)\n", idx, _sync_value, (idx+1)*-1);
             _sync_value = idx;
             value1 = idx;
-            array[idx] = idx;
+            array[idx] = idx; // last written checked first, SC-DRF should handle...
             sync_value = _sync_value; // SC-DRF release atomic
         }
     }
     void getThreadType11(const std::string msg, int _idx) {
-        const int idx = std::min(number(array_size), _idx);
+        const int idx = std::min(number(array_size)-1, _idx);
 
+        // idx is encoded on sync_value (v) as follows
+        //   v > 0: get @ idx = v -1
+        //   v < 0: put @ idx = abs(v) -1
         int _sync_value;
-        while( idx != ( _sync_value = sync_value ) ) ; // SC-DRF acquire atomic with spin-lock waiting for startValue
-        CHECKM(msg+": %s: Wrong value at read value1 (sync), idx "+std::to_string(idx), _sync_value, value1);
-        CHECKM(msg+": %s: Wrong value at read value1 (idx), idx "+std::to_string(idx), idx, value1);
-        CHECKM(msg+": %s: Wrong value at read array (idx), idx "+std::to_string(idx), idx, array[idx]);
-        sync_value = _sync_value; // SC-DRF release atomic
-    }
-    void getThreadType12(const std::string msg) {
-        int _sync_value = sync_value; // SC-DRF acquire atomic with spin-lock waiting for startValue
-        CHECKM(msg+": %s: Wrong value at read value1 (sync)", _sync_value, value1);
-        CHECKTM(msg+": %s: Wrong value at read value1: Not: sync "+std::to_string(value1)+" < "+std::to_string(number(array_size)), value1 < array_size);
-        CHECKM(msg+": %s: Wrong value at read array (sync)", value1, array[value1]);
+        // SC-DRF acquire atomic with spin-lock waiting for idx
+        do {
+            _sync_value = sync_value;
+        } while( idx != _sync_value );
+        CHECKM(msg+": %s: Wrong value at read array (a), idx "+std::to_string(idx), idx, array[idx]); // check last-written first
+        CHECKM(msg+": %s: Wrong value at read value1, idx "+std::to_string(idx), idx, value1);
+        CHECKM(msg+": %s: Wrong value at read sync, idx "+std::to_string(idx), idx, _sync_value);
+        // next write encoded idx
+        _sync_value = (idx+1)%array_size;
+        _sync_value = ( _sync_value + 1 ) * -1;
+        // fprintf(stderr, "getThreadType11.done for %d, next %d (v %d)\n", idx, (idx+1)%array_size, _sync_value);
+        value1 = _sync_value;
         sync_value = _sync_value; // SC-DRF release atomic
     }
 
@@ -106,7 +131,7 @@ class Cppunit_tests : public Cppunit {
 
     void test01_Read1Write1() {
         fprintf(stderr, "\n\ntest01_Read1Write1.a\n");
-        reset(1010);
+        reset(0, 1010);
 
         std::thread getThread01(&Cppunit_tests::getThreadType01, this, "test01.get01", array_size, 3); // @suppress("Invalid arguments")
         std::thread putThread01(&Cppunit_tests::putThreadType01, this, array_size, 3); // @suppress("Invalid arguments")
@@ -116,7 +141,7 @@ class Cppunit_tests : public Cppunit {
 
     void test02_Read2Write1() {
         fprintf(stderr, "\n\ntest01_Read2Write1.a\n");
-        reset(1021);
+        reset(0, 1021);
         {
             std::thread getThread00(&Cppunit_tests::getThreadType01, this, "test01.get00", array_size, 4); // @suppress("Invalid arguments")
             std::thread getThread01(&Cppunit_tests::getThreadType01, this, "test01.get01", array_size, 4); // @suppress("Invalid arguments")
@@ -127,7 +152,7 @@ class Cppunit_tests : public Cppunit {
         }
 
         fprintf(stderr, "\n\ntest01_Read2Write1.b\n");
-        reset(1022);
+        reset(0, 1022);
         {
             std::thread putThread01(&Cppunit_tests::putThreadType01, this, array_size, 5); // @suppress("Invalid arguments")
             std::thread getThread00(&Cppunit_tests::getThreadType01, this, "test01.get00", array_size, 5); // @suppress("Invalid arguments")
@@ -140,7 +165,7 @@ class Cppunit_tests : public Cppunit {
 
     void test03_Read4Write1() {
         fprintf(stderr, "\n\ntest02_Read4Write1\n");
-        reset(1030);
+        reset(0, 1030);
 
         std::thread getThread01(&Cppunit_tests::getThreadType01, this, "test02.get01", array_size, 6); // @suppress("Invalid arguments")
         std::thread getThread02(&Cppunit_tests::getThreadType01, this, "test02.get02", array_size, 6); // @suppress("Invalid arguments")
@@ -156,17 +181,15 @@ class Cppunit_tests : public Cppunit {
 
     void test11_Read10Write10() {
         fprintf(stderr, "\n\ntest11_Read10Write10\n");
-        reset(1110);
+        reset(-1, 1110); // start put idx 0
 
         std::thread reader[array_size];
         std::thread writer[array_size];
         for(int i=0; i<number(array_size); i++) {
             reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test11.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
-            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
-            // reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test11.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
-            // reader[i] = std::thread(&Cppunit_tests::getThreadType12, this, "test11.get12"); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
+            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
             writer[i].join();
@@ -178,16 +201,15 @@ class Cppunit_tests : public Cppunit {
 
     void test12_Read10Write10() {
         fprintf(stderr, "\n\ntest12_Read10Write10\n");
-        reset(1110);
+        reset(-1, 1120); // start put idx 0
 
         std::thread reader[array_size];
         std::thread writer[array_size];
         for(int i=0; i<number(array_size); i++) {
-            reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test12.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
-            // reader[i] = std::thread(&Cppunit_tests::getThreadType12, this, "test12.get12"); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
+            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
-            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
+            reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test12.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
             writer[i].join();
@@ -198,18 +220,22 @@ class Cppunit_tests : public Cppunit {
     }
 
     void test_list() override {
-        const int loops = 1000;
         for(int i=loops; i>0; i--) { test01_Read1Write1(); }
         for(int i=loops; i>0; i--) { test02_Read2Write1(); }
-        for(int i=loops; i>0; i--) { test03_Read4Write1(); } // fail: sync_value != array[idx] .. less often
-        // for(int i=loops; i>0; i--) { test11_Read10Write10(); } // fail: value1 != sync_value
-        // for(int i=loops; i>0; i--) { test12_Read10Write10(); } // fail: value1 != sync_value
+        for(int i=loops; i>0; i--) { test03_Read4Write1(); }
+        for(int i=loops; i>0; i--) { test11_Read10Write10(); }
+        for(int i=loops; i>0; i--) { test12_Read10Write10(); }
     }
 };
 
 int main(int argc, char *argv[]) {
-    (void)argc;
-    (void)argv;
+    for(int i=1; i<argc; i++) {
+        std::string arg(argv[i]);
+        if( "-loops" == arg && argc > i+1 ) {
+            loops = atoi(argv[i+1]);
+        }
+    }
+    fprintf(stderr, "Loops %d\n", loops);
 
     Cppunit_tests test1;
     return test1.run();
diff --git a/test/direct_bt/test_mm_sc_drf_01.cpp b/test/direct_bt/test_mm_sc_drf_01.cpp
index fe3969e0..faddc96d 100644
--- a/test/direct_bt/test_mm_sc_drf_01.cpp
+++ b/test/direct_bt/test_mm_sc_drf_01.cpp
@@ -17,7 +17,18 @@
 
 using namespace direct_bt;
 
-// Test examples.
+static int loops = 10;
+
+/**
+ * test_mm_sc_drf_01: Testing SC-DRF non-atomic global read and write within a locked mutex critical block.
+ * <p>
+ * Modified non-atomic memory within the locked mutex acquire and release block,
+ * must be visible for all threads according to memory model (MM) Sequentially Consistent (SC) being data-race-free (DRF).
+ * <br>
+ * See Herb Sutter's 2013-12-23 slides p19, first box "It must be impossible for the assertion to fail – wouldn’t be SC.".
+ * </p>
+ * See 'test_mm_sc_drf_00' implementing same test using an atomic acquire/release critical block with spin-lock.
+ */
 class Cppunit_tests : public Cppunit {
   private:
     enum Defaults : int {
@@ -31,12 +42,13 @@ class Cppunit_tests : public Cppunit {
     int array[array_size] = { 0 };
     std::mutex mtx_value;
     std::condition_variable cvRead;
+    std::condition_variable cvWrite;
 
-    void reset(int v) {
+    void reset(int v1, int array_value) {
         std::unique_lock<std::mutex> lock(mtx_value); // SC-DRF acquire and release @ scope exit
-        value1 = v;
+        value1 = v1;
         for(int i=0; i<array_size; i++) {
-            array[i] = v;
+            array[i] = array_value;
         }
     }
 
@@ -44,11 +56,10 @@ class Cppunit_tests : public Cppunit {
         const int len = std::min(number(array_size), _len);
         {
             std::unique_lock<std::mutex> lock(mtx_value); // SC-DRF acquire and release @ scope exit
-            value1 = startValue;
-
             for(int i=0; i<len; i++) {
                 array[i] = startValue+i;
             }
+            value1 = startValue;
             cvRead.notify_all(); // notify waiting getter
         }
     }
@@ -68,28 +79,42 @@ class Cppunit_tests : public Cppunit {
     }
 
     void putThreadType11(int indexAndValue) {
-        const int idx = std::min(number(array_size), indexAndValue);
+        const int idx = std::min(number(array_size)-1, indexAndValue);
         {
+            // idx is encoded on sync_value (v) as follows
+            //   v > 0: get @ idx = v -1
+            //   v < 0: put @ idx = abs(v) -1
             std::unique_lock<std::mutex> lock(mtx_value); // SC-DRF acquire and release @ scope exit
+            // SC-DRF acquire atomic with spin-lock waiting for encoded idx
+            while( idx != (value1 * -1) - 1 ) {
+                cvWrite.wait(lock);
+            }
+            // fprintf(stderr, "putThreadType11.done @ %d (has %d, exp %d)\n", idx, value1, (idx+1)*-1);
             value1 = idx;
-            array[idx] = idx;
-            cvRead.notify_all(); // notify waiting getter
+            array[idx] = idx; // last written checked first, SC-DRF should handle...
+            cvRead.notify_all();
         }
     }
     void getThreadType11(const std::string msg, int _idx) {
-        const int idx = std::min(number(array_size), _idx);
+        const int idx = std::min(number(array_size)-1, _idx);
 
-        std::unique_lock<std::mutex> lock(mtx_value); // SC-DRF acquire and release @ scope exit
+        // idx is encoded on sync_value (v) as follows
+        //   v > 0: get @ idx = v -1
+        //   v < 0: put @ idx = abs(v) -1
+        // SC-DRF acquire atomic with spin-lock waiting for idx
+        std::unique_lock<std::mutex> lock(mtx_value);
         while( idx != value1 ) {
+            // fprintf(stderr, "getThreadType11.wait for has %d == exp %d\n", value1, idx);
             cvRead.wait(lock);
         }
+        CHECKM(msg+": %s: Wrong value at read array (idx), idx "+std::to_string(idx), idx, array[idx]); // check last-written first
         CHECKM(msg+": %s: Wrong value at read value1 (idx), idx "+std::to_string(idx), idx, value1);
-        CHECKM(msg+": %s: Wrong value at read array (idx), idx "+std::to_string(idx), idx, array[idx]);
-    }
-    void getThreadType12(const std::string msg) {
-        std::unique_lock<std::mutex> lock(mtx_value); // SC-DRF acquire and release @ scope exit
-        CHECKTM(msg+": %s: Wrong value at read value1: Not: sync "+std::to_string(value1)+" < "+std::to_string(number(array_size)), value1 < array_size);
-        CHECKM(msg+": %s: Wrong value at read array (sync)", value1, array[value1]);
+        // next write encoded idx
+        int next_idx = (idx+1)%array_size;
+        next_idx = ( next_idx + 1 ) * -1;
+        // fprintf(stderr, "getThreadType11.done for %d, next %d (v %d)\n", idx, (idx+1)%array_size, next_idx);
+        value1 = next_idx;
+        cvWrite.notify_all();
     }
 
 
@@ -100,7 +125,7 @@ class Cppunit_tests : public Cppunit {
 
     void test01_Read1Write1() {
         fprintf(stderr, "\n\ntest01_Read1Write1.a\n");
-        reset(1010);
+        reset(0, 1010);
 
         std::thread getThread01(&Cppunit_tests::getThreadType01, this, "test01.get01", array_size, 3); // @suppress("Invalid arguments")
         std::thread putThread01(&Cppunit_tests::putThreadType01, this, array_size, 3); // @suppress("Invalid arguments")
@@ -110,7 +135,7 @@ class Cppunit_tests : public Cppunit {
 
     void test02_Read2Write1() {
         fprintf(stderr, "\n\ntest01_Read2Write1.a\n");
-        reset(1021);
+        reset(0, 1021);
         {
             std::thread getThread00(&Cppunit_tests::getThreadType01, this, "test01.get00", array_size, 4); // @suppress("Invalid arguments")
             std::thread getThread01(&Cppunit_tests::getThreadType01, this, "test01.get01", array_size, 4); // @suppress("Invalid arguments")
@@ -121,7 +146,7 @@ class Cppunit_tests : public Cppunit {
         }
 
         fprintf(stderr, "\n\ntest01_Read2Write1.b\n");
-        reset(1022);
+        reset(0, 1022);
         {
             std::thread putThread01(&Cppunit_tests::putThreadType01, this, array_size, 5); // @suppress("Invalid arguments")
             std::thread getThread00(&Cppunit_tests::getThreadType01, this, "test01.get00", array_size, 5); // @suppress("Invalid arguments")
@@ -134,7 +159,7 @@ class Cppunit_tests : public Cppunit {
 
     void test03_Read4Write1() {
         fprintf(stderr, "\n\ntest02_Read4Write1\n");
-        reset(1030);
+        reset(0, 1030);
 
         std::thread getThread01(&Cppunit_tests::getThreadType01, this, "test02.get01", array_size, 6); // @suppress("Invalid arguments")
         std::thread getThread02(&Cppunit_tests::getThreadType01, this, "test02.get02", array_size, 6); // @suppress("Invalid arguments")
@@ -150,17 +175,15 @@ class Cppunit_tests : public Cppunit {
 
     void test11_Read10Write10() {
         fprintf(stderr, "\n\ntest11_Read10Write10\n");
-        reset(1110);
+        reset(-1, 1110);
 
         std::thread reader[array_size];
         std::thread writer[array_size];
         for(int i=0; i<number(array_size); i++) {
             reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test11.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
-            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
-            // reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test11.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
-            // reader[i] = std::thread(&Cppunit_tests::getThreadType12, this, "test11.get12"); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
+            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
             writer[i].join();
@@ -172,16 +195,15 @@ class Cppunit_tests : public Cppunit {
 
     void test12_Read10Write10() {
         fprintf(stderr, "\n\ntest12_Read10Write10\n");
-        reset(1110);
+        reset(-1, 1120);
 
         std::thread reader[array_size];
         std::thread writer[array_size];
         for(int i=0; i<number(array_size); i++) {
-            reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test12.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
-            // reader[i] = std::thread(&Cppunit_tests::getThreadType12, this, "test12.get12"); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
+            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
-            writer[i] = std::thread(&Cppunit_tests::putThreadType11, this, i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
+            reader[i] = std::thread(&Cppunit_tests::getThreadType11, this, "test12.get11", i); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
         }
         for(int i=0; i<number(array_size); i++) {
             writer[i].join();
@@ -192,18 +214,22 @@ class Cppunit_tests : public Cppunit {
     }
 
     void test_list() override {
-        const int loops = 1000;
         for(int i=loops; i>0; i--) { test01_Read1Write1(); }
         for(int i=loops; i>0; i--) { test02_Read2Write1(); }
         for(int i=loops; i>0; i--) { test03_Read4Write1(); }
-        // for(int i=loops; i>0; i--) { test11_Read10Write10(); }
-        // for(int i=loops; i>0; i--) { test12_Read10Write10(); }
+        for(int i=loops; i>0; i--) { test11_Read10Write10(); }
+        for(int i=loops; i>0; i--) { test12_Read10Write10(); }
     }
 };
 
 int main(int argc, char *argv[]) {
-    (void)argc;
-    (void)argv;
+    for(int i=1; i<argc; i++) {
+        std::string arg(argv[i]);
+        if( "-loops" == arg && argc > i+1 ) {
+            loops = atoi(argv[i+1]);
+        }
+    }
+    fprintf(stderr, "Loops %d\n", loops);
 
     Cppunit_tests test1;
     return test1.run();