samples/MapLinearizabilityTest/MapLinearizabilityTest.cpp

   1 /*------------------------------------------------------------------------
   2   Junction: Concurrent data structures in C++
   3   Copyright (c) 2016 Jeff Preshing
   4
   5   Distributed under the Simplified BSD License.
   6   Original location: https://github.com/preshing/junction
   7
   8   This software is distributed WITHOUT ANY WARRANTY; without even the
   9   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10   See the LICENSE file for more information.
  11 ------------------------------------------------------------------------*/
  12
  13 #include <junction/Core.h>
  14 #include <turf/extra/JobDispatcher.h>
  15 #include <junction/extra/MapAdapter.h>
  16 #include <turf/extra/Random.h>
  17 #include <stdio.h>
  18
  19 using namespace turf::intTypes;
  20 typedef junction::extra::MapAdapter MapAdapter;
  21
  22 turf::extra::Random g_random[4];
  23
  24 class StoreBufferTest {
  25 public:
  26     MapAdapter::Map m_map;
  27     // Keys:
  28     u32 X;
  29     u32 Y;
  30     // Observed values:
  31     uptr m_r1;
  32     uptr m_r2;
  33
  34     StoreBufferTest() : m_map(1024) {
  35         // Randomize the keys
  36         do {
  37             X = g_random[0].next32();
  38         } while (X == 0);
  39         do {
  40             Y = g_random[0].next32();
  41         } while (Y == 0 || Y == X);
  42     }
  43
  44     void run(ureg threadIndex) {
  45         u32 x = X;
  46         u32 y = Y;
  47         while ((g_random[threadIndex].next32() & 0x1ff) != 0) { // Random delay
  48         }
  49         if (threadIndex == 0) {
  50             // We store 2 because 1 is reserved for the default Redirect value.
  51             // The default can be overridden, but this is easier.
  52             m_map.insert(x, (void*) 2);
  53             m_r1 = (uptr) m_map.get(y);
  54         } else {
  55             m_map.insert(y, (void*) 2);
  56             m_r2 = (uptr) m_map.get(x);
  57         }
  58     }
  59 };
  60
  61 class IRIWTest {
  62 public:
  63     MapAdapter::Map m_map;
  64     // Keys:
  65     u32 X;
  66     u32 Y;
  67     // Observed values:
  68     uptr m_r1;
  69     uptr m_r2;
  70     uptr m_r3;
  71     uptr m_r4;
  72
  73     IRIWTest() : m_map(1024) {
  74         // Randomize the keys
  75         do {
  76             X = g_random[0].next32();
  77         } while (X == 0);
  78         do {
  79             Y = g_random[0].next32();
  80         } while (Y == 0 || Y == X);
  81     }
  82
  83     void run(ureg threadIndex) {
  84         u32 x = X;
  85         u32 y = Y;
  86         while ((g_random[threadIndex].next32() & 0x7f) != 0) { // Random delay
  87         }
  88         switch (threadIndex) {
  89         case 0:
  90             // We store 2 because 1 is reserved for the default Redirect value.
  91             // The default can be overridden, but this is easier.
  92             m_map.insert(x, (void*) 2);
  93             break;
  94
  95         case 1:
  96             m_r1 = (uptr) m_map.get(x);
  97             m_r2 = (uptr) m_map.get(y);
  98             break;
  99
 100         case 2:
 101             m_map.insert(y, (void*) 2);
 102             break;
 103
 104         case 3:
 105             m_r3 = (uptr) m_map.get(y);
 106             m_r4 = (uptr) m_map.get(x);
 107             break;
 108         }
 109     }
 110 };
 111
 112 int main() {
 113 #if 1
 114     turf::extra::JobDispatcher dispatcher(4);
 115     MapAdapter adapter(4);
 116
 117     int nonLinearizable = 0;
 118     for (int iterations = 0;; iterations++) {
 119         IRIWTest test;
 120         dispatcher.kick(&IRIWTest::run, test);
 121 //        printf("%d %d %d %d\n", test.m_r1, test.m_r2, test.m_r3, test.m_r4);
 122         if ((test.m_r1 == 2 && test.m_r2 == 0 && test.m_r3 == 2 && test.m_r4 == 0)
 123             || (test.m_r1 == 0 && test.m_r2 == 2 && test.m_r3 == 0 && test.m_r4 == 2))
 124             nonLinearizable++;
 125         if (iterations % 10000 == 0) {
 126             printf("%d non-linearizable histories after %d iterations\n", nonLinearizable, iterations);
 127         }
 128     }
 129 #else
 130     turf::extra::JobDispatcher dispatcher(2);
 131     MapAdapter adapter(2);
 132
 133     u64 nonLinearizable = 0;
 134     for (u64 iterations = 0;; iterations++) {
 135         StoreBufferTest test;
 136         dispatcher.kick(&StoreBufferTest::run, test);
 137         if (test.m_r1 == 0 && test.m_r2 == 0)
 138             nonLinearizable++;
 139         if (iterations % 10000 == 0) {
 140             printf("%" TURF_U64D " non-linearizable histories after %" TURF_U64D " iterations\n", nonLinearizable, iterations);
 141         }
 142     }
 143 #endif
 144
 145     return 0;
 146 }