clang/test/ms-queue_unannotated.c

   1 #include <threads.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #define true 1
   5 #define false 0
   6 #define bool int
   7
   8 #include "ms-queue.h"
   9 #include "libinterface.h"
  10
  11 void init_queue(queue_t *q, int num_threads);
  12 void enqueue(queue_t *q, unsigned int val);
  13 bool dequeue(queue_t *q, unsigned int *retVal);
  14
  15 void init_queue(queue_t *q, int num_threads) {
  16         int i, j;
  17         struct node *newnode=malloc(sizeof (struct node));
  18         store_32(&newnode->value, 0);
  19
  20         store_64(&newnode->next, (uintptr_t) MAKE_POINTER(NULL, 0LL));
  21         /* initialize queue */
  22         store_64(&q->head, (uintptr_t) MAKE_POINTER(newnode, 0LL));
  23
  24         store_64(&q->tail, (uintptr_t) MAKE_POINTER(newnode, 0LL));
  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         store_32(&node_ptr->value, val);
  31
  32         store_64(&node_ptr->next, (uintptr_t) MAKE_POINTER(NULL, GET_COUNT(1)));
  33
  34         while (true) {
  35                 tail = (struct node *) load_64(&q->tail);
  36                 struct node ** tail_ptr_next= & GET_PTR(tail)->next;
  37
  38                 struct node * next = (struct node *) load_64(tail_ptr_next);
  39
  40                 struct node * qtail = (struct node *) load_64(&q->tail);
  41                 int tqt = (tail == qtail);
  42                 if (tqt) {
  43                         struct node *next_ptr=GET_PTR(next);
  44
  45                         int npn = (next_ptr == NULL);
  46                         if (npn) {
  47                                 struct node * new_node = MAKE_POINTER(node_ptr, GET_COUNT(next) +1);
  48                                 struct node * valread = (struct node *) rmw_64(CAS, tail_ptr_next, (uintptr_t) next, (uintptr_t) new_node);
  49                                 int vn = (valread == next);
  50                                 if (vn) {
  51                                         break;
  52                                 } else {
  53                                         MC2_yield();
  54                                 }
  55                         } else {
  56                                 MC2_yield();
  57                         }
  58                         struct node * new_tailptr = GET_PTR(load_64( tail_ptr_next));
  59                         struct node * newtail = MAKE_POINTER(new_tailptr, GET_COUNT(tail) + 1);
  60                         rmw_64(CAS, &q->tail, (uintptr_t) tail, (uintptr_t) newtail);
  61                         MC2_yield();
  62                 } else {
  63                         MC2_yield();
  64                 }
  65         }
  66         rmw_64(CAS, &q->tail, (uintptr_t) tail, (uintptr_t)MAKE_POINTER(node_ptr, GET_COUNT(tail) + 1));
  67 }
  68
  69 bool dequeue(queue_t *q, unsigned int *retVal) {
  70         while (true) {
  71                 struct node * head = (struct node *) load_64(&q->head);
  72                 struct node * tail = (struct node *) load_64(&q->tail);
  73                 struct node * next = (struct node *) load_64(&(GET_PTR(head)->next));
  74
  75                 int t = ((struct node *) load_64(&q->head)) == head;
  76                 if (t) {
  77                         if (GET_PTR(head) == GET_PTR(tail)) {
  78
  79                                 if (GET_PTR(next) == NULL) {
  80                                         return false; // NULL
  81                                 } else {
  82                                         MC2_yield();
  83                                 }
  84                                 rmw_64(CAS, &q->tail, (uintptr_t) tail, (uintptr_t) MAKE_POINTER(GET_PTR(next), GET_COUNT(tail) + 1));
  85                                 MC2_yield();
  86                         } else {
  87                                 int nv = load_32(&GET_PTR(next)->value);
  88                                 store_32(retVal, nv);
  89                                 struct node * nh = MAKE_POINTER(GET_PTR(next), GET_COUNT(head)+1);
  90                                 struct node *old_head = (struct node *) rmw_64(CAS, &q->head,
  91                                                                                                                                                                                                                          (uintptr_t) head,
  92                                                                                                                                                                                                                          (uintptr_t) nh);
  93                                 if (old_head == head) {
  94                                         return true;
  95                                 } else {
  96                                         MC2_yield();
  97                                 }
  98                         }
  99                 }
 100         }
 101 }
 102
 103 /* ms-queue-main */
 104 static queue_t queue;
 105 bool succ1, succ2;
 106
 107 static void e(void *p) {
 108         int i;
 109         for(i=0;i<2;i++)
 110         enqueue(&queue, 1);
 111 }
 112
 113 static void d(void *p) {
 114         unsigned int val;
 115         int i;
 116         for(i=0;i<2;i++)
 117                 dequeue(&queue, &val);
 118 }
 119
 120 int user_main(int argc, char **argv)
 121 {
 122         init_queue(&queue, 2);
 123
 124         thrd_t t1,t2;
 125         thrd_create(&t1, e, NULL);
 126         thrd_create(&t2, d, NULL);
 127
 128         thrd_join(t1);
 129         thrd_join(t2);
 130
 131         return 0;
 132 }