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() & 0x7f) != 0) { // Random delay
  48         }
  49         if (threadIndex == 0) {
  50             // We store 2 because Junction maps reserve 1 for the default Redirect value.
  51             // The default can be overridden, but this is easier.
  52             m_map.assign(x, (void*) 2);
  53             m_r1 = (uptr) m_map.get(y);
  54         } else {
  55             m_map.assign(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 Junction maps reserve 1 for the default Redirect value.
  91             // The default can be overridden, but this is easier.
  92             m_map.assign(x, (void*) 2);
  93             break;
  94
  95         case 1:
  96             m_map.assign(y, (void*) 2);
  97             break;
  98
  99         case 2:
 100             m_r1 = (uptr) m_map.get(x);
 101             m_r2 = (uptr) m_map.get(y);
 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     // Run StoreBufferTest
 115     turf::extra::JobDispatcher dispatcher(2);
 116     MapAdapter adapter(2);
 117
 118     u64 nonLinearizable = 0;
 119     for (u64 iterations = 0;; iterations++) {
 120         StoreBufferTest test;
 121         dispatcher.kick(&StoreBufferTest::run, test);
 122         if (test.m_r1 == 0 && test.m_r2 == 0) {
 123             nonLinearizable++;
 124         }
 125         if (iterations % 10000 == 0) {
 126             printf("%" TURF_U64D " non-linearizable histories after %" TURF_U64D " iterations\n", nonLinearizable, iterations);
 127         }
 128     }
 129 #else
 130     // Run IRIWTest
 131     turf::extra::JobDispatcher dispatcher(4);
 132     MapAdapter adapter(4);
 133
 134     u64 nonLinearizable = 0;
 135     for (u64 iterations = 0;; iterations++) {
 136         IRIWTest test;
 137         dispatcher.kick(&IRIWTest::run, test);
 138         if (test.m_r1 == 2 && test.m_r2 == 0 && test.m_r3 == 2 && test.m_r4 == 0) {
 139             nonLinearizable++;
 140         }
 141         if (iterations % 10000 == 0) {
 142             printf("%" TURF_U64D " non-linearizable histories after %" TURF_U64D " iterations\n", nonLinearizable, iterations);
 143         }
 144     }
 145 #endif
 146
 147     return 0;
 148 }