/*
- * mem.spin: Promela code to validate memory barriers with OOO memory.
+ * mem.spin: Promela code to validate memory barriers with out-of-order memory
+ * and out-of-order instruction scheduling.
+ *
+ * Algorithm verified :
+ *
+ * alpha = 0;
+ * beta = 0;
+ * x = 1;
+ * y = 1;
+ *
+ * Process A Process B
+ * alpha = 1; beta = 1;
+ * mb(); mb();
+ * x = beta; y = alpha;
+ *
+ * if x = 0, then y != 0
+ * if y = 0, then x != 0
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
/* Promela validation variables. */
/*
- * Produced process data flow. Updated after each instruction to show which
- * variables are ready. Assigned using SSA (static single assignment) (defuse
- * analysis must be done on the program to map "real" variables to single define
- * followed by use). Using one-hot bit encoding per variable to save state
- * space. Used as triggers to execute the instructions having those variables
- * as input.
+ * Produced process control and data flow. Updated after each instruction to
+ * show which variables are ready. Using one-hot bit encoding per variable to
+ * save state space. Used as triggers to execute the instructions having those
+ * variables as input. Leaving bits active to inhibit instruction execution.
+ * Scheme used to make instruction disabling and automatic dependency fall-back
+ * automatic.
*/
-#define PRODUCE_TOKENS(state, bits) \
- state = (state) | (bits)
+#define CONSUME_TOKENS(state, bits, notbits) \
+ ((!(state & (notbits))) && (state & (bits)) == (bits))
-/* All bits must be active to consume. All notbits must be inactive. */
-/* Consuming a token does not clear it, it just waits for it. */
-#define CONSUME_TOKENS(state, bits, notbits) \
- ((!((state) & (notbits))) && ((state) & (bits)) == (bits))
+#define PRODUCE_TOKENS(state, bits) \
+ state = state | (bits);
-#define CLEAR_TOKENS(state, bits) \
- state = (state) & ~(bits)
-
-/*
- * Bit encoding, proc_one_produced :
- */
-
-#define P1_PROD_NONE (1 << 0)
-
-#define P1_WRITE (1 << 1)
-#define P1_WMB (1 << 2)
-#define P1_SYNC_CORE (1 << 3)
-#define P1_RMB (1 << 4)
-#define P1_READ (1 << 5)
-
-int proc_one_produced;
-
-#define P2_PROD_NONE (1 << 0)
-
-#define P2_WRITE (1 << 1)
-#define P2_WMB (1 << 2)
-#define P2_SYNC_CORE (1 << 3)
-#define P2_RMB (1 << 4)
-#define P2_READ (1 << 5)
-
-int proc_two_produced;
+#define CLEAR_TOKENS(state, bits) \
+ state = state & ~(bits)
#define NR_PROCS 2
DECLARE_CACHED_VAR(byte, alpha, 0);
DECLARE_CACHED_VAR(byte, beta, 0);
-/* value 2 is uninitialized */
-byte read_one = 2;
-byte read_two = 2;
+byte read_one = 1;
+byte read_two = 1;
+
+/*
+ * Bit encoding, proc_one_produced :
+ */
+
+#define P1_PROD_NONE (1 << 0)
+
+#define P1_WRITE (1 << 1)
+#define P1_WMB (1 << 2)
+#define P1_SYNC_CORE (1 << 3)
+#define P1_RMB (1 << 4)
+#define P1_READ (1 << 5)
+
+int proc_one_produced;
active proctype test_proc_one()
{
#ifdef NO_RMB
PRODUCE_TOKENS(proc_one_produced, P1_RMB);
#endif
+#ifdef NO_SYNC
+ PRODUCE_TOKENS(proc_one_produced, P1_SYNC_CORE);
+#endif
do
:: CONSUME_TOKENS(proc_one_produced, P1_PROD_NONE, P1_WRITE) ->
assert(!(read_one == 0 && read_two == 0));
}
+
+/*
+ * Bit encoding, proc_two_produced :
+ */
+
+#define P2_PROD_NONE (1 << 0)
+
+#define P2_WRITE (1 << 1)
+#define P2_WMB (1 << 2)
+#define P2_SYNC_CORE (1 << 3)
+#define P2_RMB (1 << 4)
+#define P2_READ (1 << 5)
+
+int proc_two_produced;
+
active proctype test_proc_two()
{
assert(get_pid() < NR_PROCS);
#ifdef NO_RMB
PRODUCE_TOKENS(proc_two_produced, P2_RMB);
#endif
+#ifdef NO_SYNC
+ PRODUCE_TOKENS(proc_two_produced, P2_SYNC_CORE);
+#endif
do
:: CONSUME_TOKENS(proc_two_produced, P2_PROD_NONE, P2_WRITE) ->