From: Brian Norris <banorris@uci.edu>
Date: Tue, 5 Mar 2013 18:10:53 +0000 (-0800)
Subject: mcs-queue -> ms-queue
X-Git-Tag: oopsla2013-final~37
X-Git-Url: http://demsky.eecs.uci.edu/git/?p=model-checker-benchmarks.git;a=commitdiff_plain;h=7df8191c93d3664a3b1ea2dfcd0e88de2cfcc7c9

mcs-queue -> ms-queue

This queue is by Michael and Scott; hence, "M&S".
---

diff --git a/mcs-queue/Makefile b/mcs-queue/Makefile
deleted file mode 100644
index 0f19830..0000000
--- a/mcs-queue/Makefile
+++ /dev/null
@@ -1,17 +0,0 @@
-include ../benchmarks.mk
-
-TESTNAME = main
-
-HEADERS = main.h my_queue.h
-OBJECTS = main.o my_queue.o args.o
-
-all: $(TESTNAME)
-
-$(TESTNAME): $(HEADERS) $(OBJECTS)
-	$(CC) -o $@ $^ $(CPPFLAGS) $(LDFLAGS)
-
-%.o: %.c
-	$(CC) -c -o $@ $< $(CPPFLAGS)
-
-clean:
-	rm -f $(TESTNAME) *.o
diff --git a/mcs-queue/args.c b/mcs-queue/args.c
deleted file mode 100644
index 89101e5..0000000
--- a/mcs-queue/args.c
+++ /dev/null
@@ -1,26 +0,0 @@
-#include "main.h"
-
-extern unsigned iterations;
-extern unsigned multi;
-extern unsigned initial_nodes;
-extern unsigned procs;
-extern unsigned repetitions;
-extern unsigned work;
-
-void parse_args(int argc, char **argv)
-{
-	extern char * optarg;
-	int c;
-
-	while ((c = getopt(argc, argv, "i:m:n:p:r:w:")) != EOF)
-		switch(c) {
-			case 'i':  iterations = atoi(optarg); break;
-			case 'm':  multi = atoi(optarg);  break;
-			case 'n':  initial_nodes = atoi(optarg);  break;
-			case 'p':   procs = atoi(optarg);   break;
-			case 'r':   repetitions = atoi(optarg);   break;
-			case 'w':   work = atoi(optarg);   break;
-			default:
-				    assert(0);
-		}
-}
diff --git a/mcs-queue/main.c b/mcs-queue/main.c
deleted file mode 100644
index 015fbd4..0000000
--- a/mcs-queue/main.c
+++ /dev/null
@@ -1,80 +0,0 @@
-#include "main.h"
-#include <stdlib.h>
-
-#define NUM_PROCESSORS			12
-
-struct tms tim;
-struct tms tim1;
-
-int shmid;
-
-unsigned pid;
-char* name = "";
-unsigned procs = 1;
-unsigned multi = 1;
-unsigned iterations = 1;
-unsigned initial_nodes = 0;
-unsigned repetitions = 1;
-unsigned work = 0;
-private_t private;
-shared_mem_t *smp;
-
-void time_test()
-{
-	unsigned i,j;
-	struct tms time_val;
-	clock_t t1, t2;
-	unsigned val;
-
-	if(pid==0) {
-		init_queue();
-	}
-	init_memory();
-	init_private();
-	for(i=0;i<iterations;i++) {
-		val = private.value;
-		enqueue(val);
-		for(j=0; j<work;) j++;
-		val = dequeue();
-		for(j=0; j<work;) j++;
-		private.value++;
-	}
-}
-
-void main_task()
-{
-	unsigned processor;
-	unsigned i;
-
-	processor = (pid/multi)+1;
-	processor %= NUM_PROCESSORS;
-	for (i=0; i<repetitions; i++) {
-		time_test();
-	}
-}
-
-int user_main(int argc, char **argv)
-{
-	int i, num_threads;
-	thrd_t *t;
-
-	parse_args(argc, argv);
-	name = argv[0];
-	iterations = (iterations + ((procs*multi)>>1))/(procs*multi);
-
-	smp = (shared_mem_t *)calloc(1, sizeof(shared_mem_t));
-	assert(smp);
-
-	num_threads = procs * multi;
-	t = malloc(num_threads * sizeof(thrd_t));
-
-	for (i = 0; i < num_threads; i++)
-		thrd_create(&t[i], main_task, NULL);
-	for (i = 0; i < num_threads; i++)
-		thrd_join(t[i]);
-
-	free(t);
-	free(smp);
-
-	return 0;
-}
diff --git a/mcs-queue/main.h b/mcs-queue/main.h
deleted file mode 100644
index 7a7d2a7..0000000
--- a/mcs-queue/main.h
+++ /dev/null
@@ -1,11 +0,0 @@
-#include <stdio.h>
-#include <sys/param.h>
-#include <sys/types.h>
-#include <sys/times.h>
-#include <sys/types.h>
-#include <sys/ipc.h>
-#include <sys/shm.h>
-#include <signal.h>
-#include <assert.h>
-#include <threads.h>
-#include "my_queue.h"
diff --git a/mcs-queue/my_queue.c b/mcs-queue/my_queue.c
deleted file mode 100644
index 1f8a446..0000000
--- a/mcs-queue/my_queue.c
+++ /dev/null
@@ -1,130 +0,0 @@
-#include "main.h"
-
-extern unsigned pid;
-extern unsigned iterations;
-extern unsigned initial_nodes;
-extern private_t private;
-extern shared_mem_t* smp;
-
-void init_private()
-{
-	private.node = 2 + initial_nodes + pid;
-	private.value = 1 + initial_nodes + (pid * iterations);
-
-}
-
-void init_memory()
-{
-}
-
-static unsigned new_node()
-{
-	return private.node;
-}
-
-static void reclaim(unsigned node)
-{
-	private.node = node;
-}
-
-void init_queue()
-{
-	unsigned i;
-
-	/* initialize queue */
-	smp->head.sep.ptr = 1;
-	smp->head.sep.count = 0;
-	smp->tail.sep.ptr = 1;
-	smp->tail.sep.count = 0;
-	smp->nodes[1].next.sep.ptr = NULL;
-	smp->nodes[1].next.sep.count = 0;
-
-	/* initialize avail list */
-	for (i=2; i<MAX_NODES; i++) {
-		smp->nodes[i].next.sep.ptr = i+1;
-		smp->nodes[i].next.sep.count = 0;
-	}
-	smp->nodes[MAX_NODES].next.sep.ptr = NULL;
-	smp->nodes[MAX_NODES].next.sep.count = 0;
-
-	/* initialize queue contents */
-	if (initial_nodes > 0) {
-		for (i=2; i<initial_nodes+2; i++) {
-			smp->nodes[i].value = i;
-			smp->nodes[i-1].next.sep.ptr = i;
-			smp->nodes[i].next.sep.ptr = NULL;
-		}
-		smp->head.sep.ptr = 1;
-		smp->tail.sep.ptr = 1 + initial_nodes;    
-	}
-}
-
-void enqueue(unsigned val)
-{
-	unsigned success;
-	unsigned node;
-	pointer_t tail;
-	pointer_t next;
-
-	node = new_node();
-	smp->nodes[node].value = val;
-	smp->nodes[node].next.sep.ptr = NULL;
-
-	for (success = FALSE; success == FALSE; ) {
-		tail.con = smp->tail.con;
-		next.con = smp->nodes[tail.sep.ptr].next.con;
-		if (tail.con == smp->tail.con) {
-			if (next.sep.ptr == NULL) {
-				success = cas(&smp->nodes[tail.sep.ptr].next, 
-						next.con,
-						MAKE_LONG(node, next.sep.count+1));
-			}
-			if (success == FALSE) {
-				cas(&smp->tail,
-						tail.con,
-						MAKE_LONG(smp->nodes[tail.sep.ptr].next.sep.ptr,
-							tail.sep.count+1));
-				thrd_yield();
-			}
-		}
-	}
-	cas(&smp->tail, 
-			tail.con,
-			MAKE_LONG(node, tail.sep.count+1));
-}
-
-unsigned dequeue()
-{
-	unsigned value;
-	unsigned success;
-	pointer_t head;
-	pointer_t tail;
-	pointer_t next;
-
-	for (success = FALSE; success == FALSE; ) {
-		head.con = smp->head.con;
-		tail.con = smp->tail.con;
-		next.con = smp->nodes[head.sep.ptr].next.con;
-		if (smp->head.con == head.con) {
-			if (head.sep.ptr == tail.sep.ptr) {
-				if (next.sep.ptr == NULL) {
-					return NULL;
-				}
-				cas(&smp->tail,
-						tail.con,
-						MAKE_LONG(next.sep.ptr, tail.sep.count+1));
-				thrd_yield();
-			} else {
-				value = smp->nodes[next.sep.ptr].value;
-				success = cas(&smp->head,
-						head.con,
-						MAKE_LONG(next.sep.ptr, head.sep.count+1));
-				if (success == FALSE) {
-					thrd_yield();
-				}
-			}
-		}
-	}
-	reclaim(head.sep.ptr);
-	return value;
-}
diff --git a/mcs-queue/my_queue.h b/mcs-queue/my_queue.h
deleted file mode 100644
index 3e3f435..0000000
--- a/mcs-queue/my_queue.h
+++ /dev/null
@@ -1,43 +0,0 @@
-#include <stdatomic.h>
-
-#define TRUE				1
-#define FALSE				0
-
-#define MAX_NODES			0xff
-#define MAX_SERIAL			10000
-
-#define MAKE_LONG(lo, hi)		((hi)<<16)+(lo)
-
-typedef union pointer {
-	struct {
-		volatile unsigned short count;
-		volatile unsigned short ptr;
-	} sep;
-	atomic_ulong con;
-} pointer_t;
-
-typedef struct node {
-	unsigned value;
-	pointer_t next;
-	unsigned foo[30];
-} node_t;
-
-typedef struct private {
-	unsigned node;
-	unsigned value;
-	unsigned serial[MAX_SERIAL];
-} private_t;
-
-typedef struct shared_mem {
-	pointer_t head;
-	unsigned foo1[31];
-	pointer_t tail;
-	unsigned foo2[31];
-	node_t nodes[MAX_NODES+1];
-	unsigned serial;
-} shared_mem_t;
-
-void init_private();
-void init_memory();
-void init_queue();
-unsigned dequeue();
diff --git a/ms-queue/Makefile b/ms-queue/Makefile
new file mode 100644
index 0000000..0f19830
--- /dev/null
+++ b/ms-queue/Makefile
@@ -0,0 +1,17 @@
+include ../benchmarks.mk
+
+TESTNAME = main
+
+HEADERS = main.h my_queue.h
+OBJECTS = main.o my_queue.o args.o
+
+all: $(TESTNAME)
+
+$(TESTNAME): $(HEADERS) $(OBJECTS)
+	$(CC) -o $@ $^ $(CPPFLAGS) $(LDFLAGS)
+
+%.o: %.c
+	$(CC) -c -o $@ $< $(CPPFLAGS)
+
+clean:
+	rm -f $(TESTNAME) *.o
diff --git a/ms-queue/args.c b/ms-queue/args.c
new file mode 100644
index 0000000..89101e5
--- /dev/null
+++ b/ms-queue/args.c
@@ -0,0 +1,26 @@
+#include "main.h"
+
+extern unsigned iterations;
+extern unsigned multi;
+extern unsigned initial_nodes;
+extern unsigned procs;
+extern unsigned repetitions;
+extern unsigned work;
+
+void parse_args(int argc, char **argv)
+{
+	extern char * optarg;
+	int c;
+
+	while ((c = getopt(argc, argv, "i:m:n:p:r:w:")) != EOF)
+		switch(c) {
+			case 'i':  iterations = atoi(optarg); break;
+			case 'm':  multi = atoi(optarg);  break;
+			case 'n':  initial_nodes = atoi(optarg);  break;
+			case 'p':   procs = atoi(optarg);   break;
+			case 'r':   repetitions = atoi(optarg);   break;
+			case 'w':   work = atoi(optarg);   break;
+			default:
+				    assert(0);
+		}
+}
diff --git a/ms-queue/main.c b/ms-queue/main.c
new file mode 100644
index 0000000..015fbd4
--- /dev/null
+++ b/ms-queue/main.c
@@ -0,0 +1,80 @@
+#include "main.h"
+#include <stdlib.h>
+
+#define NUM_PROCESSORS			12
+
+struct tms tim;
+struct tms tim1;
+
+int shmid;
+
+unsigned pid;
+char* name = "";
+unsigned procs = 1;
+unsigned multi = 1;
+unsigned iterations = 1;
+unsigned initial_nodes = 0;
+unsigned repetitions = 1;
+unsigned work = 0;
+private_t private;
+shared_mem_t *smp;
+
+void time_test()
+{
+	unsigned i,j;
+	struct tms time_val;
+	clock_t t1, t2;
+	unsigned val;
+
+	if(pid==0) {
+		init_queue();
+	}
+	init_memory();
+	init_private();
+	for(i=0;i<iterations;i++) {
+		val = private.value;
+		enqueue(val);
+		for(j=0; j<work;) j++;
+		val = dequeue();
+		for(j=0; j<work;) j++;
+		private.value++;
+	}
+}
+
+void main_task()
+{
+	unsigned processor;
+	unsigned i;
+
+	processor = (pid/multi)+1;
+	processor %= NUM_PROCESSORS;
+	for (i=0; i<repetitions; i++) {
+		time_test();
+	}
+}
+
+int user_main(int argc, char **argv)
+{
+	int i, num_threads;
+	thrd_t *t;
+
+	parse_args(argc, argv);
+	name = argv[0];
+	iterations = (iterations + ((procs*multi)>>1))/(procs*multi);
+
+	smp = (shared_mem_t *)calloc(1, sizeof(shared_mem_t));
+	assert(smp);
+
+	num_threads = procs * multi;
+	t = malloc(num_threads * sizeof(thrd_t));
+
+	for (i = 0; i < num_threads; i++)
+		thrd_create(&t[i], main_task, NULL);
+	for (i = 0; i < num_threads; i++)
+		thrd_join(t[i]);
+
+	free(t);
+	free(smp);
+
+	return 0;
+}
diff --git a/ms-queue/main.h b/ms-queue/main.h
new file mode 100644
index 0000000..7a7d2a7
--- /dev/null
+++ b/ms-queue/main.h
@@ -0,0 +1,11 @@
+#include <stdio.h>
+#include <sys/param.h>
+#include <sys/types.h>
+#include <sys/times.h>
+#include <sys/types.h>
+#include <sys/ipc.h>
+#include <sys/shm.h>
+#include <signal.h>
+#include <assert.h>
+#include <threads.h>
+#include "my_queue.h"
diff --git a/ms-queue/my_queue.c b/ms-queue/my_queue.c
new file mode 100644
index 0000000..1f8a446
--- /dev/null
+++ b/ms-queue/my_queue.c
@@ -0,0 +1,130 @@
+#include "main.h"
+
+extern unsigned pid;
+extern unsigned iterations;
+extern unsigned initial_nodes;
+extern private_t private;
+extern shared_mem_t* smp;
+
+void init_private()
+{
+	private.node = 2 + initial_nodes + pid;
+	private.value = 1 + initial_nodes + (pid * iterations);
+
+}
+
+void init_memory()
+{
+}
+
+static unsigned new_node()
+{
+	return private.node;
+}
+
+static void reclaim(unsigned node)
+{
+	private.node = node;
+}
+
+void init_queue()
+{
+	unsigned i;
+
+	/* initialize queue */
+	smp->head.sep.ptr = 1;
+	smp->head.sep.count = 0;
+	smp->tail.sep.ptr = 1;
+	smp->tail.sep.count = 0;
+	smp->nodes[1].next.sep.ptr = NULL;
+	smp->nodes[1].next.sep.count = 0;
+
+	/* initialize avail list */
+	for (i=2; i<MAX_NODES; i++) {
+		smp->nodes[i].next.sep.ptr = i+1;
+		smp->nodes[i].next.sep.count = 0;
+	}
+	smp->nodes[MAX_NODES].next.sep.ptr = NULL;
+	smp->nodes[MAX_NODES].next.sep.count = 0;
+
+	/* initialize queue contents */
+	if (initial_nodes > 0) {
+		for (i=2; i<initial_nodes+2; i++) {
+			smp->nodes[i].value = i;
+			smp->nodes[i-1].next.sep.ptr = i;
+			smp->nodes[i].next.sep.ptr = NULL;
+		}
+		smp->head.sep.ptr = 1;
+		smp->tail.sep.ptr = 1 + initial_nodes;    
+	}
+}
+
+void enqueue(unsigned val)
+{
+	unsigned success;
+	unsigned node;
+	pointer_t tail;
+	pointer_t next;
+
+	node = new_node();
+	smp->nodes[node].value = val;
+	smp->nodes[node].next.sep.ptr = NULL;
+
+	for (success = FALSE; success == FALSE; ) {
+		tail.con = smp->tail.con;
+		next.con = smp->nodes[tail.sep.ptr].next.con;
+		if (tail.con == smp->tail.con) {
+			if (next.sep.ptr == NULL) {
+				success = cas(&smp->nodes[tail.sep.ptr].next, 
+						next.con,
+						MAKE_LONG(node, next.sep.count+1));
+			}
+			if (success == FALSE) {
+				cas(&smp->tail,
+						tail.con,
+						MAKE_LONG(smp->nodes[tail.sep.ptr].next.sep.ptr,
+							tail.sep.count+1));
+				thrd_yield();
+			}
+		}
+	}
+	cas(&smp->tail, 
+			tail.con,
+			MAKE_LONG(node, tail.sep.count+1));
+}
+
+unsigned dequeue()
+{
+	unsigned value;
+	unsigned success;
+	pointer_t head;
+	pointer_t tail;
+	pointer_t next;
+
+	for (success = FALSE; success == FALSE; ) {
+		head.con = smp->head.con;
+		tail.con = smp->tail.con;
+		next.con = smp->nodes[head.sep.ptr].next.con;
+		if (smp->head.con == head.con) {
+			if (head.sep.ptr == tail.sep.ptr) {
+				if (next.sep.ptr == NULL) {
+					return NULL;
+				}
+				cas(&smp->tail,
+						tail.con,
+						MAKE_LONG(next.sep.ptr, tail.sep.count+1));
+				thrd_yield();
+			} else {
+				value = smp->nodes[next.sep.ptr].value;
+				success = cas(&smp->head,
+						head.con,
+						MAKE_LONG(next.sep.ptr, head.sep.count+1));
+				if (success == FALSE) {
+					thrd_yield();
+				}
+			}
+		}
+	}
+	reclaim(head.sep.ptr);
+	return value;
+}
diff --git a/ms-queue/my_queue.h b/ms-queue/my_queue.h
new file mode 100644
index 0000000..3e3f435
--- /dev/null
+++ b/ms-queue/my_queue.h
@@ -0,0 +1,43 @@
+#include <stdatomic.h>
+
+#define TRUE				1
+#define FALSE				0
+
+#define MAX_NODES			0xff
+#define MAX_SERIAL			10000
+
+#define MAKE_LONG(lo, hi)		((hi)<<16)+(lo)
+
+typedef union pointer {
+	struct {
+		volatile unsigned short count;
+		volatile unsigned short ptr;
+	} sep;
+	atomic_ulong con;
+} pointer_t;
+
+typedef struct node {
+	unsigned value;
+	pointer_t next;
+	unsigned foo[30];
+} node_t;
+
+typedef struct private {
+	unsigned node;
+	unsigned value;
+	unsigned serial[MAX_SERIAL];
+} private_t;
+
+typedef struct shared_mem {
+	pointer_t head;
+	unsigned foo1[31];
+	pointer_t tail;
+	unsigned foo2[31];
+	node_t nodes[MAX_NODES+1];
+	unsigned serial;
+} shared_mem_t;
+
+void init_private();
+void init_memory();
+void init_queue();
+unsigned dequeue();