chase-lev-deque-bugfix/deque_wildcard.c

   1 #include <stdatomic.h>
   2 #include <inttypes.h>
   3 #include "deque.h"
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include "wildcard.h"
   7
   8 Deque * create_size(int size) {
   9         Deque * q = (Deque *) calloc(1, sizeof(Deque));
  10         Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int));
  11         atomic_store_explicit(&q->array, a, wildcard(1));
  12         atomic_store_explicit(&q->top, 0, wildcard(2));
  13         atomic_store_explicit(&q->bottom, 0, wildcard(3));
  14         atomic_store_explicit(&a->size, size, wildcard(4));
  15         return q;
  16 }
  17
  18 Deque * create() {
  19         Deque * q = (Deque *) calloc(1, sizeof(Deque));
  20         Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int));
  21         atomic_store_explicit(&q->array, a, wildcard(1));
  22         atomic_store_explicit(&q->top, 0, wildcard(2));
  23         atomic_store_explicit(&q->bottom, 0, wildcard(3));
  24         atomic_store_explicit(&a->size, 2, wildcard(4));
  25         return q;
  26 }
  27
  28 int take(Deque *q) {
  29         size_t b = atomic_load_explicit(&q->bottom, wildcard(5)) - 1;
  30         Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(6));
  31         atomic_store_explicit(&q->bottom, b, wildcard(7));
  32         atomic_thread_fence(wildcard(8)); // seq_cst
  33         size_t t = atomic_load_explicit(&q->top, wildcard(9));
  34         int x;
  35         if (t <= b) {
  36                 /* Non-empty queue. */
  37                 x = atomic_load_explicit(&a->buffer[b %
  38                 atomic_load_explicit(&a->size,wildcard(10))], wildcard(11));
  39                 if (t == b) {
  40                         /* Single last element in queue. */
  41                         if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1,
  42                                 wildcard(12), wildcard(13))) // 12 -> seq_cst
  43                                 /* Failed race. */
  44                                 x = EMPTY;
  45                         atomic_store_explicit(&q->bottom, b + 1, wildcard(14));
  46                 }
  47         } else { /* Empty queue. */
  48                 x = EMPTY;
  49                 atomic_store_explicit(&q->bottom, b + 1, wildcard(15));
  50         }
  51         return x;
  52 }
  53
  54 void resize(Deque *q) {
  55         Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(16));
  56         size_t size=atomic_load_explicit(&a->size, wildcard(17));
  57         size_t new_size=size << 1;
  58         Array *new_a = (Array *) calloc(1, new_size * sizeof(atomic_int) + sizeof(Array));
  59         size_t top=atomic_load_explicit(&q->top, wildcard(18));
  60         size_t bottom=atomic_load_explicit(&q->bottom, wildcard(19));
  61         atomic_store_explicit(&new_a->size, new_size, wildcard(20));
  62         size_t i;
  63         for(i=top; i < bottom; i++) {
  64                 atomic_store_explicit(&new_a->buffer[i % new_size],
  65                 atomic_load_explicit(&a->buffer[i % size], wildcard(21)), wildcard(22));
  66         }
  67         atomic_store_explicit(&q->array, new_a, wildcard(23)); // release
  68         printf("resize\n");
  69 }
  70
  71 void push(Deque *q, int x) {
  72         size_t b = atomic_load_explicit(&q->bottom, wildcard(24));
  73         size_t t = atomic_load_explicit(&q->top, wildcard(25)); // acquire
  74         Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(26));
  75         if (b - t > atomic_load_explicit(&a->size, wildcard(27)) - 1) /* Full queue. */ {
  76                 resize(q);
  77                 //Bug in paper...should have next line...
  78                 a = (Array *) atomic_load_explicit(&q->array, wildcard(28));
  79         }
  80         atomic_store_explicit(&a->buffer[b % atomic_load_explicit(&a->size,
  81         wildcard(29))], x, wildcard(30));
  82         atomic_thread_fence(wildcard(31)); // release
  83         //atomic_thread_fence(release); // release
  84         atomic_store_explicit(&q->bottom, b + 1, wildcard(32));
  85 }
  86
  87 int steal(Deque *q) {
  88         size_t t = atomic_load_explicit(&q->top, wildcard(33)); // acquire
  89         atomic_thread_fence(wildcard(34)); // seq_cst
  90         size_t b = atomic_load_explicit(&q->bottom, wildcard(35)); // acquire
  91         int x = EMPTY;
  92         if (t < b) {
  93                 /* Non-empty queue. */
  94                 // acquire
  95                 Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(36));
  96                 x = atomic_load_explicit(&a->buffer[t % atomic_load_explicit(&a->size,
  97                 wildcard(37))], wildcard(38));
  98                 // seq_cst
  99                 if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1,
 100                         wildcard(39), wildcard(40)))
 101                         /* Failed race. */
 102                         return ABORT;
 103         }
 104         return x;
 105 }