From 5a6521efce9bad7488fb880311d77fecd87427fa Mon Sep 17 00:00:00 2001
From: Peizhao Ou <peizhaoo@uci.edu>
Date: Thu, 12 Feb 2015 17:02:50 -0800
Subject: [PATCH] barrier with weaker inferences & notes in comment

---
 barrier/Makefile           |  9 +++++--
 barrier/barrier-wildcard.h | 53 ++++++++++++++++++++++++++++++++++++++
 barrier/testcase.cc        | 43 +++++++++++++++++++++++++++++++
 3 files changed, 103 insertions(+), 2 deletions(-)
 create mode 100644 barrier/barrier-wildcard.h
 create mode 100644 barrier/testcase.cc

diff --git a/barrier/Makefile b/barrier/Makefile
index 22df223..90389ba 100644
--- a/barrier/Makefile
+++ b/barrier/Makefile
@@ -2,10 +2,15 @@ include ../benchmarks.mk
 
 TESTNAME = barrier
 
-all: $(TESTNAME)
+WILDCARD_TESTS = testcase
+
+all: $(TESTNAME) $(WILDCARD_TESTS)
 
 $(TESTNAME): $(TESTNAME).cc $(TESTNAME).h
 	$(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS)
 
+$(WILDCARD_TESTS): % : %.cc $(TESTNAME)-wildcard.h
+	$(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS)
+
 clean:
-	rm -f $(TESTNAME) *.o
+	rm -f $(TESTNAME) *.o $(WILDCARD_TESTS)
diff --git a/barrier/barrier-wildcard.h b/barrier/barrier-wildcard.h
new file mode 100644
index 0000000..58d01c5
--- /dev/null
+++ b/barrier/barrier-wildcard.h
@@ -0,0 +1,53 @@
+#include <atomic>
+#include "wildcard.h"
+
+class spinning_barrier {
+ public:
+	spinning_barrier (unsigned int n) : n_ (n) {
+		nwait_ = 0;
+		step_ = 0;
+	}
+
+	// The purpose of wait() is that threads that enter it synchronize with
+	// threads when they get out of it.
+	/** wildcard(2) is acq_rel, ensuring that all threads hb before other
+	 *  threads in the rmw chain order, then the wildcard (4) and (5) are
+	 *  release/acquire to make sure the last thread synchronize with all other
+	 *  earlier threads. Plus, the (4) and (5) synchronization can make sure the
+	 *  reset of nwait_ in wildcard(3) happens-before any other threads in the
+	 *  later usage of the barrier.
+	*/
+
+	// All orderings are SC originally!!!
+	bool wait() {
+		// Infer relaxed
+		unsigned int step = step_.load (wildcard(1));
+		
+		// Infer acq_rel 
+		if (nwait_.fetch_add (1, wildcard(2)) == n_ - 1) {
+			/* OK, last thread to come.  */
+			// Infer relaxed 
+			nwait_.store (0, wildcard(3)); // XXX: maybe can use relaxed ordering here ??
+			// Infer release
+			step_.fetch_add (1, wildcard(4));
+			return true;
+		} else {
+			/* Run in circles and scream like a little girl.  */
+			// Infer acquire 
+			while (step_.load (wildcard(5)) == step)
+				thrd_yield();
+			return false;
+		}
+	}
+
+ protected:
+	/* Number of synchronized threads. */
+	const unsigned int n_;
+
+	/* Number of threads currently spinning.  */
+	std::atomic<unsigned int> nwait_;
+
+	/* Number of barrier syncronizations completed so far, 
+	 *      * it's OK to wrap.  */
+	std::atomic<unsigned int> step_;
+};
diff --git a/barrier/testcase.cc b/barrier/testcase.cc
new file mode 100644
index 0000000..2d0ba49
--- /dev/null
+++ b/barrier/testcase.cc
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <threads.h>
+
+#include "barrier-wildcard.h"
+
+#include "librace.h"
+#include <atomic> 
+
+spinning_barrier *barr;
+std::atomic_int var;
+
+void threadA(void *arg)
+{
+	//store_32(&var, 1);
+	var.store(1, std::memory_order_relaxed);
+	barr->wait();
+}
+
+void threadB(void *arg)
+{
+	barr->wait();
+	//printf("var = %d\n", load_32(&var));
+	var.load(std::memory_order_relaxed);
+}
+
+#define NUMREADERS 2
+int user_main(int argc, char **argv)
+{
+	thrd_t A, B[NUMREADERS];
+	int i;
+
+	barr = new spinning_barrier(NUMREADERS + 1);
+
+	thrd_create(&A, &threadA, NULL);
+	for (i = 0; i < NUMREADERS; i++)
+		thrd_create(&B[i], &threadB, NULL);
+
+	for (i = 0; i < NUMREADERS; i++)
+		thrd_join(B[i]);
+	thrd_join(A);
+
+	return 0;
+}
-- 
2.34.1