This queue is by Michael and Scott; hence, "M&S".
+++ /dev/null
-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
+++ /dev/null
-#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);
- }
-}
+++ /dev/null
-#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;
-}
+++ /dev/null
-#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"
+++ /dev/null
-#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;
-}
+++ /dev/null
-#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();
--- /dev/null
+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
--- /dev/null
+#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);
+ }
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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"
--- /dev/null
+#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;
+}
--- /dev/null
+#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();