From bead5206c1935e3b499300c7e8b5b41a259a04c6 Mon Sep 17 00:00:00 2001 From: Brian Norris Date: Tue, 5 Mar 2013 16:43:14 -0800 Subject: [PATCH] ms-queue: more cleanup --- ms-queue/.gitignore | 1 + ms-queue/Makefile | 4 +-- ms-queue/args.c | 18 ----------- ms-queue/main.c | 48 +++++++++++++++++++++-------- ms-queue/main.h | 11 ------- ms-queue/my_queue.c | 73 ++++++++++++++++++++------------------------- ms-queue/my_queue.h | 20 ++++--------- 7 files changed, 76 insertions(+), 99 deletions(-) create mode 100644 ms-queue/.gitignore delete mode 100644 ms-queue/args.c delete mode 100644 ms-queue/main.h diff --git a/ms-queue/.gitignore b/ms-queue/.gitignore new file mode 100644 index 0000000..95811e0 --- /dev/null +++ b/ms-queue/.gitignore @@ -0,0 +1 @@ +/main diff --git a/ms-queue/Makefile b/ms-queue/Makefile index 0f19830..c2a9104 100644 --- a/ms-queue/Makefile +++ b/ms-queue/Makefile @@ -2,8 +2,8 @@ include ../benchmarks.mk TESTNAME = main -HEADERS = main.h my_queue.h -OBJECTS = main.o my_queue.o args.o +HEADERS = my_queue.h +OBJECTS = main.o my_queue.o all: $(TESTNAME) diff --git a/ms-queue/args.c b/ms-queue/args.c deleted file mode 100644 index 6fe19de..0000000 --- a/ms-queue/args.c +++ /dev/null @@ -1,18 +0,0 @@ -#include "main.h" - -extern unsigned iterations; -extern unsigned procs; - -void parse_args(int argc, char **argv) -{ - extern char *optarg; - int c; - - while ((c = getopt(argc, argv, "i:p:")) != EOF) - switch(c) { - case 'i': iterations = atoi(optarg); break; - case 'p': procs = atoi(optarg); break; - default: - assert(0); - } -} diff --git a/ms-queue/main.c b/ms-queue/main.c index 30d9da9..fefb386 100644 --- a/ms-queue/main.c +++ b/ms-queue/main.c @@ -1,10 +1,33 @@ -#include "main.h" #include +#include +#include +#include -unsigned procs = 2; -unsigned iterations = 1; +#include "my_queue.h" + +static int procs = 2; +static int iterations = 1; private_t private; -shared_mem_t *smp; +static queue_t *queue; + +static void parse_args(int argc, char **argv) +{ + extern char *optarg; + int c; + + while ((c = getopt(argc, argv, "i:p:")) != EOF) { + switch (c) { + case 'i': + iterations = atoi(optarg); + break; + case 'p': + procs = atoi(optarg); + break; + default: + assert(0); + } + } +} static void main_task(void *param) { @@ -12,13 +35,12 @@ static void main_task(void *param) unsigned val; int pid = *((int *)param); - init_memory(); init_private(pid); for (i = 0; i < iterations; i++) { - val = private.value; - enqueue(val); - val = dequeue(); - private.value++; + val = 1 + pid * iterations + i; + enqueue(queue, val); + + val = dequeue(queue); } } @@ -31,14 +53,14 @@ int user_main(int argc, char **argv) parse_args(argc, argv); iterations = (iterations + (procs >> 1)) / procs; - smp = (shared_mem_t *)calloc(1, sizeof(shared_mem_t)); - assert(smp); + queue = calloc(1, sizeof(*queue)); + assert(queue); num_threads = procs; t = malloc(num_threads * sizeof(thrd_t)); param = malloc(num_threads * sizeof(*param)); - init_queue(); + init_queue(queue); for (i = 0; i < num_threads; i++) { param[i] = i; thrd_create(&t[i], main_task, ¶m[i]); @@ -48,7 +70,7 @@ int user_main(int argc, char **argv) free(param); free(t); - free(smp); + free(queue); return 0; } diff --git a/ms-queue/main.h b/ms-queue/main.h deleted file mode 100644 index 7a7d2a7..0000000 --- a/ms-queue/main.h +++ /dev/null @@ -1,11 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "my_queue.h" diff --git a/ms-queue/my_queue.c b/ms-queue/my_queue.c index 8fedd9c..eb5d54a 100644 --- a/ms-queue/my_queue.c +++ b/ms-queue/my_queue.c @@ -1,18 +1,12 @@ -#include "main.h" +#include + +#include "my_queue.h" -extern unsigned int iterations; extern private_t private; -extern shared_mem_t *smp; void init_private(int pid) { private.node = 2 + pid; - private.value = 1 + (pid * iterations); - -} - -void init_memory() -{ } static unsigned int new_node() @@ -25,7 +19,7 @@ static void reclaim(unsigned int node) private.node = node; } -void init_queue() +void init_queue(queue_t *q) { unsigned int i; pointer head; @@ -37,91 +31,90 @@ void init_queue() tail = MAKE_POINTER(1, 0); next = MAKE_POINTER(0, 0); // (NULL, 0) - atomic_init(&smp->nodes[0].next, 0); // assumed inititalized in original example + atomic_init(&q->nodes[0].next, 0); // assumed inititalized in original example - atomic_store(&smp->head, head); - atomic_store(&smp->tail, tail); - atomic_store(&smp->nodes[1].next, next); + atomic_store(&q->head, head); + atomic_store(&q->tail, tail); + atomic_store(&q->nodes[1].next, next); /* initialize avail list */ for (i = 2; i < MAX_NODES; i++) { next = MAKE_POINTER(i + 1, 0); - atomic_store(&smp->nodes[i].next, next); + atomic_store(&q->nodes[i].next, next); } next = MAKE_POINTER(0, 0); // (NULL, 0) - atomic_store(&smp->nodes[MAX_NODES].next, next); + atomic_store(&q->nodes[MAX_NODES].next, next); } -void enqueue(unsigned int val) +void enqueue(queue_t *q, unsigned int val) { - unsigned int success = 0; + int success = 0; unsigned int node; pointer tail; pointer next; pointer tmp; node = new_node(); - smp->nodes[node].value = val; - tmp = atomic_load(&smp->nodes[node].next); + q->nodes[node].value = val; + tmp = atomic_load(&q->nodes[node].next); set_ptr(&tmp, 0); // NULL - atomic_store(&smp->nodes[node].next, tmp); + atomic_store(&q->nodes[node].next, tmp); while (!success) { - tail = atomic_load(&smp->tail); - next = atomic_load(&smp->nodes[get_ptr(tail)].next); - if (tail == atomic_load(&smp->tail)) { + tail = atomic_load(&q->tail); + next = atomic_load(&q->nodes[get_ptr(tail)].next); + if (tail == atomic_load(&q->tail)) { if (get_ptr(next) == 0) { // == NULL pointer val = MAKE_POINTER(node, get_count(next) + 1); - success = atomic_compare_exchange_weak(&smp->nodes[get_ptr(tail)].next, + success = atomic_compare_exchange_weak(&q->nodes[get_ptr(tail)].next, &next, val); } if (!success) { - unsigned int ptr = get_ptr(atomic_load(&smp->nodes[get_ptr(tail)].next)); + unsigned int ptr = get_ptr(atomic_load(&q->nodes[get_ptr(tail)].next)); pointer val = MAKE_POINTER(ptr, get_count(tail) + 1); - atomic_compare_exchange_strong(&smp->tail, + atomic_compare_exchange_strong(&q->tail, &tail, val); thrd_yield(); } } } - atomic_compare_exchange_strong(&smp->tail, + atomic_compare_exchange_strong(&q->tail, &tail, MAKE_POINTER(node, get_count(tail) + 1)); } -unsigned int dequeue() +unsigned int dequeue(queue_t *q) { unsigned int value; - unsigned int success; + int success = 0; pointer head; pointer tail; pointer next; - for (success = FALSE; success == FALSE; ) { - head = atomic_load(&smp->head); - tail = atomic_load(&smp->tail); - next = atomic_load(&smp->nodes[get_ptr(head)].next); - if (atomic_load(&smp->head) == head) { + while (!success) { + head = atomic_load(&q->head); + tail = atomic_load(&q->tail); + next = atomic_load(&q->nodes[get_ptr(head)].next); + if (atomic_load(&q->head) == head) { if (get_ptr(head) == get_ptr(tail)) { if (get_ptr(next) == 0) { // NULL return 0; // NULL } - atomic_compare_exchange_weak(&smp->tail, + atomic_compare_exchange_weak(&q->tail, &tail, MAKE_POINTER(get_ptr(next), get_count(tail) + 1)); thrd_yield(); } else { - value = smp->nodes[get_ptr(next)].value; - success = atomic_compare_exchange_weak(&smp->head, + value = q->nodes[get_ptr(next)].value; + success = atomic_compare_exchange_weak(&q->head, &head, MAKE_POINTER(get_ptr(next), get_count(head) + 1)); - if (success == FALSE) { + if (!success) thrd_yield(); - } } } } diff --git a/ms-queue/my_queue.h b/ms-queue/my_queue.h index 519e9e3..4ce05b4 100644 --- a/ms-queue/my_queue.h +++ b/ms-queue/my_queue.h @@ -1,10 +1,6 @@ #include -#define TRUE 1 -#define FALSE 0 - #define MAX_NODES 0xf -#define MAX_SERIAL 10000 typedef unsigned long long pointer; typedef atomic_ullong pointer_t; @@ -21,25 +17,19 @@ static inline unsigned int get_ptr(pointer p) { return (p & COUNT_MASK) >> 32; } typedef struct node { unsigned int value; pointer_t next; - unsigned int foo[30]; } node_t; typedef struct private { unsigned int node; - unsigned int value; - unsigned int serial[MAX_SERIAL]; } private_t; typedef struct shared_mem { pointer_t head; - unsigned int foo1[31]; pointer_t tail; - unsigned int foo2[31]; - node_t nodes[MAX_NODES+1]; - unsigned int serial; -} shared_mem_t; + node_t nodes[MAX_NODES + 1]; +} queue_t; void init_private(int pid); -void init_memory(); -void init_queue(); -unsigned int dequeue(); +void init_queue(queue_t *q); +void enqueue(queue_t *q, unsigned int val); +unsigned int dequeue(queue_t *q); -- 2.34.1