bb12be0b09a222cfd2bbd1cca1fa0e329fa3a39a
[cdsspec-compiler.git] / benchmark / chase-lev-deque-bugfix / deque.c
1 #include <stdatomic.h>
2 #include <inttypes.h>
3 #include "deque.h"
4 #include <stdlib.h>
5 #include <stdio.h>
6
7 Deque * create() {
8         Deque * q = (Deque *) calloc(1, sizeof(Deque));
9         Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int));
10         atomic_store_explicit(&q->array, a, memory_order_relaxed);
11         atomic_store_explicit(&q->top, 0, memory_order_relaxed);
12         atomic_store_explicit(&q->bottom, 0, memory_order_relaxed);
13         atomic_store_explicit(&a->size, 2, memory_order_relaxed);
14         return q;
15 }
16
17
18 /**
19         @Begin
20         @Interface_define: Take 
21         @End
22 */
23 int take(Deque *q) {
24         size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed) - 1;
25         /**
26                 @Begin
27                 @Commit_point_define_check: true
28                 @Label: TakeReadBottom
29                 @End
30         */
31         Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
32         atomic_store_explicit(&q->bottom, b, memory_order_relaxed);
33         /**** SPEC (sequential) (testcase1.c) ****/
34         atomic_thread_fence(memory_order_seq_cst);
35         size_t t = atomic_load_explicit(&q->top, memory_order_relaxed);
36         int x;
37         if (t <= b) {
38                 /**
39                         @Begin
40                         @Commit_point_clear: true
41                         @Label: TakeClear1
42                         @End
43                 */
44
45                 /* Non-empty queue. */
46                 int size = atomic_load_explicit(&a->size,memory_order_relaxed);
47                 x = atomic_load_explicit(&a->buffer[b % size], memory_order_relaxed);
48                 /**
49                         @Begin
50                         @Commit_point_define_check: true 
51                         @Label: TakeReadBuffer
52                         @End
53                 */
54                 if (t == b) {
55                         /* Single last element in queue. */
56                         //FIXME: weaken the following seq_cst causes no spec problem
57                         bool succ = atomic_compare_exchange_strong_explicit(&q->top, &t, t +
58                                 1, memory_order_seq_cst, memory_order_relaxed);
59                         if (!succ) {
60                                 /**
61                                         @Begin
62                                         @Commit_point_clear: true
63                                         @Label: TakeClear2
64                                         @End
65                                 */
66
67                                 /**
68                                         @Begin
69                                         @Commit_point_define_check: true
70                                         @Label: TakeReadTop
71                                         @End
72                                 */
73
74                                 /* Failed race. */
75                                 x = EMPTY;
76                         }
77                         atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
78                 }
79         } else { /* Empty queue. */
80                 x = EMPTY;
81                 atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
82         }
83         return x;
84 }
85
86 void resize(Deque *q) {
87         Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
88         size_t size=atomic_load_explicit(&a->size, memory_order_relaxed);
89         size_t new_size=size << 1;
90         Array *new_a = (Array *) calloc(1, new_size * sizeof(atomic_int) + sizeof(Array));
91         size_t top=atomic_load_explicit(&q->top, memory_order_relaxed);
92         size_t bottom=atomic_load_explicit(&q->bottom, memory_order_relaxed);
93         atomic_store_explicit(&new_a->size, new_size, memory_order_relaxed);
94         size_t i;
95
96         // Initialize the whole new array to turn off the CDSChecker UL error
97         // Check if CDSSpec checker can catch this bug
98         /*
99         for(i=0; i < new_size; i++) {
100                 atomic_store_explicit(&new_a->buffer[i % new_size], atomic_load_explicit(&a->buffer[i % size], memory_order_relaxed), memory_order_relaxed);
101         }
102         */
103         for(i=top; i < bottom; i++) {
104                 atomic_store_explicit(&new_a->buffer[i % new_size], atomic_load_explicit(&a->buffer[i % size], memory_order_relaxed), memory_order_relaxed);
105         }
106         /**** detected UL ****/
107         atomic_store_explicit(&q->array, new_a, memory_order_release);
108         //printf("resize\n");
109 }
110
111 /**
112         @Begin
113         @Interface_define: Push
114         @End
115 */
116 void push(Deque *q, int x) {
117         size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed);
118         /**** SPEC (sequential) ****/
119         size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
120         Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
121         if (b - t > atomic_load_explicit(&a->size, memory_order_relaxed) - 1) /* Full queue. */ {
122                 resize(q);
123                 // CDSSpec can actually detect the same bug if we avoid the UL error
124                 //Bug in paper...should have next line...
125                 a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
126         }
127         int size = atomic_load_explicit(&a->size, memory_order_relaxed);
128
129         atomic_store_explicit(&a->buffer[b % size], x, memory_order_relaxed);
130         /**
131                 @Begin
132                 @Commit_point_define_check: true
133                 @Label: PushUpdateBuffer
134                 @End
135         */
136         /**** UL & SPEC (Sync) (run with -u100 to avoid the uninitialized bug) ****/
137         atomic_thread_fence(memory_order_release);
138         atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
139         
140 }
141
142 /**
143         @Begin
144         @Interface_define: Steal 
145         @End
146 */
147 int steal(Deque *q) {
148         //Watch out: actually on need to be an acquire (don't count it)
149         // An old bug
150         size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
151         /**
152                 @Begin
153                 @Commit_point_define_check: true
154                 @Label: StealReadTop1
155                 @End
156         */
157         /********** SPEC error (testcase3.c) **********/
158         atomic_thread_fence(memory_order_seq_cst);
159         /**** SPEC & UL ****/
160         size_t b = atomic_load_explicit(&q->bottom, memory_order_acquire);
161         
162         int x = EMPTY;
163         if (t < b) {
164                 /**
165                         @Begin
166                         @Commit_point_clear: true
167                         @Label: StealClear1
168                         @End
169                 */
170
171                 /* Non-empty queue. */
172                 /**** detected UL ****/
173                 Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_acquire);
174                 int size = atomic_load_explicit(&a->size, memory_order_relaxed);
175                 x = atomic_load_explicit(&a->buffer[t % size], memory_order_relaxed);
176                 /**
177                         @Begin
178                         @Commit_point_define_check: true
179                         @Label: StealReadBuffer
180                         @End
181                 */
182                 /**** SPEC (sequential) ****/ 
183                 bool succ = atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1,
184                         memory_order_seq_cst, memory_order_relaxed);
185                 if (!succ) {
186                         /**
187                                 @Begin
188                                 @Commit_point_clear: true
189                                 @Label: StealClear2
190                                 @End
191                         */
192
193                         /**
194                                 @Begin
195                                 @Commit_point_define_check: true
196                                 @Label: StealReadTop2
197                                 @End
198                         */
199
200                         /* Failed race. */
201                         return ABORT;
202                 }
203         }
204         return x;
205 }