benchmarks/cdschecker/msqueue/ms-queue_simple.c.in

   1 #include <threads.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <stdatomic.h>
   5 #define true 1
   6 #define false 0
   7
   8
   9 #include "ms-queue_simple.h"
  10
  11 queue_t queue;
  12 void init_queue(queue_t *q, int num_threads);
  13 void enqueue(queue_t *q, unsigned int val);
  14 bool dequeue(queue_t *q, unsigned int *retVal);
  15
  16 void init_queue(queue_t *q, int num_threads) {
  17         struct node *newnode=malloc(sizeof (struct node));
  18         atomic_store(&newnode->value, 0);
  19
  20         atomic_store(&newnode->next, (uintptr_t) NULL);
  21                 /* initialize queue */
  22         atomic_store(&q->head, newnode);
  23
  24         atomic_store(&q->tail, newnode);
  25 }
  26
  27 void enqueue(queue_t *q, unsigned int val) {
  28         struct node *tail;
  29         struct node * node_ptr = malloc(sizeof(struct node));
  30         atomic_store(&node_ptr->value, val);
  31
  32         atomic_store(&node_ptr->next, NULL);
  33
  34         while (true) {
  35                 tail = (struct node *) atomic_load(&q->tail);
  36
  37                 struct node * next = (struct node *) atomic_load( &tail->next);
  38
  39                 struct node * qtail = (struct node *) atomic_load(&q->tail);
  40                 if (tail == qtail) {
  41
  42                         if (next == NULL) {
  43                                 if (atomic_compare_exchange_strong( & tail->next,& next, node_ptr))
  44                                         break;
  45                         }
  46                 }
  47                 struct node * new_tailptr = (struct node *)atomic_load( &tail->next);
  48                 atomic_compare_exchange_strong(&q->tail, & tail, new_tailptr);
  49                 thrd_yield();
  50         }
  51         atomic_compare_exchange_strong(&q->tail, & tail, node_ptr);
  52 }
  53
  54 bool dequeue(queue_t *q, unsigned int *retVal) {
  55         while (true) {
  56                 struct node * head = (struct node *) atomic_load(&q->head);
  57                 struct node * tail = (struct node *) atomic_load(&q->tail);
  58                 struct node * next = (struct node *) atomic_load(&head->next);
  59
  60                 int t = ((struct node *) atomic_load(&q->head)) == head;
  61                 if (t) {
  62                         if (head == tail) {
  63
  64                                 if (next == NULL) {
  65                                         return false; // NULL
  66                                 }
  67                                 atomic_compare_exchange_strong(&q->tail, & tail, next);
  68                                 thrd_yield();
  69                         } else {
  70                                 *retVal = atomic_load(&next->value);
  71                                 if (atomic_compare_exchange_strong(&q->head,& head, next)) {
  72                                         return true;
  73                                 } else {
  74                                         thrd_yield();
  75                                 }
  76                         }
  77                 }
  78         }
  79 }
  80
  81 static void e(void *param)
  82 {
  83         int i;
  84         for(i=0;i<PROBLEMSIZE;i++)
  85                 enqueue(&queue, 1);
  86 }
  87
  88 static void d(void *param) {
  89         int val,i;
  90         for(i=0;i<PROBLEMSIZE;i++) {
  91                 dequeue(&queue, &val);
  92         }
  93 }
  94
  95 int user_main(int argc, char **argv)
  96 {
  97         // MODEL_ASSERT(queue);
  98
  99         init_queue(&queue, 2);
 100
 101         thrd_t t1,t2;
 102         thrd_create(&t1, e, NULL);
 103         thrd_create(&t2, d, NULL);
 104
 105
 106         return 0;
 107 }