test/ms-queue-freelist.c

   1 #include "threads.h"
   2 #include <stdlib.h>
   3 // #include "librace.h"
   4 // #include "model-assert.h"
   5
   6 #include "libinterface.h"
   7 #include "ms-queue-freelist.h"
   8
   9
  10 #define MAX_FREELIST 4 /* Each thread can own up to MAX_FREELIST free nodes */
  11 #define INITIAL_FREE 2 /* Each thread starts with INITIAL_FREE free nodes */
  12
  13 #define POISON_IDX 0x666
  14
  15 static unsigned int (*free_lists)[MAX_FREELIST];
  16
  17 /* Search this thread's free list for a "new" node */
  18 static unsigned int new_node()
  19 {
  20         int i;
  21         int t = get_thread_num();
  22         for (i = 0; i < MAX_FREELIST; i++) {
  23                 unsigned int node = load_32(&free_lists[t][i]);
  24                 if (node) {
  25                         store_32(&free_lists[t][i], 0);
  26                         return node;
  27                 }
  28         }
  29         /* free_list is empty? */
  30         // MODEL_ASSERT(0);
  31         return 0;
  32 }
  33
  34 /* Place this node index back on this thread's free list */
  35 static void reclaim(unsigned int node)
  36 {
  37         int i;
  38         int t = get_thread_num();
  39
  40         /* Don't reclaim NULL node */
  41         // MODEL_ASSERT(node);
  42
  43         for (i = 0; i < MAX_FREELIST; i++) {
  44                 /* Should never race with our own thread here */
  45                 unsigned int idx = load_32(&free_lists[t][i]);
  46
  47                 /* Found empty spot in free list */
  48                 if (idx == 0) {
  49                         store_32(&free_lists[t][i], node);
  50                         return;
  51                 }
  52         }
  53         /* free list is full? */
  54         // MODEL_ASSERT(0);
  55 }
  56
  57 void init_queue(queue_t *q, int num_threads)
  58 {
  59         int i, j;
  60
  61         /* Initialize each thread's free list with INITIAL_FREE pointers */
  62         /* The actual nodes are initialized with poison indexes */
  63         free_lists = malloc(num_threads * sizeof(*free_lists));
  64         for (i = 0; i < num_threads; i++) {
  65                 for (j = 0; j < INITIAL_FREE; j++) {
  66                         free_lists[i][j] = 2 + i * MAX_FREELIST + j;
  67                         store_32(&q->nodes[free_lists[i][j]].next, MAKE_POINTER(POISON_IDX, 0));
  68                 }
  69         }
  70
  71         /* initialize queue */
  72         store_32(&q->head, MAKE_POINTER(1, 0));
  73         store_32(&q->tail, MAKE_POINTER(1, 0));
  74         store_32(&q->nodes[1].next, MAKE_POINTER(0, 0));
  75 }
  76
  77 void enqueue(queue_t *q, unsigned int val)
  78 {
  79         int success = 0;
  80         unsigned int node;
  81         pointer tail;
  82         pointer next;
  83         pointer tmp;
  84
  85         node = new_node();
  86         store_32(&q->nodes[node].value, val);
  87         tmp = load_32(&q->nodes[node].next);
  88         // manually inlined macro: set_ptr(&tmp, 0); // NULL
  89         tmp = (tmp & ~PTR_MASK);
  90         store_32(&q->nodes[node].next, tmp);
  91
  92         while (!success) {
  93                 pointer_t * qt = &q->tail;
  94                 tail = load_32(qt);
  95                 pointer_t * qn = &q->nodes[tail & PTR_MASK].next;
  96                 next = load_32(qn);
  97                 if (tail == load_32(&q->tail)) {
  98
  99                         /* Check for uninitialized 'next' */
 100                         // MODEL_ASSERT(get_ptr(next) != POISON_IDX);
 101
 102                         if ((next & PTR_MASK) == 0) { // == NULL
 103                                 pointer value = MAKE_POINTER(node, ((next & COUNT_MASK) >> 32) + 1);
 104                                 success = rmw_32(CAS, &q->nodes[tail & PTR_MASK].next,
 105                                                 (uint32_t)&next, value);
 106                         }
 107                         if (!success) {
 108                                 unsigned int ptr = (load_32(&q->nodes[tail & PTR_MASK].next) & PTR_MASK);
 109                                 pointer value = MAKE_POINTER(ptr,
 110                                              ((tail & COUNT_MASK) >> 32) + 1);
 111                                 rmw_32(CAS, &q->tail,
 112                                                 (uint32_t)&tail, value);
 113                                 thrd_yield();
 114                         }
 115                 }
 116         }
 117         rmw_32(CAS, &q->tail,
 118                    (uint32_t)&tail,
 119                    MAKE_POINTER(node, ((tail & COUNT_MASK) >> 32) + 1));
 120 }
 121
 122 bool dequeue(queue_t *q, unsigned int *retVal)
 123 {
 124         int success = 0;
 125         pointer head;
 126         pointer tail;
 127         pointer next;
 128
 129         while (!success) {
 130                 head = load_32(&q->head);
 131                 tail = load_32(&q->tail);
 132                 next = load_32(&q->nodes[(head & PTR_MASK)].next);
 133                 if (load_32(&q->head) == head) {
 134                         if ((head & PTR_MASK) == (tail & PTR_MASK)) {
 135
 136                                 /* Check for uninitialized 'next' */
 137                                 // MODEL_ASSERT(get_ptr(next) != POISON_IDX);
 138
 139                                 if (get_ptr(next) == 0) { // NULL
 140                                         return false; // NULL
 141                                 }
 142                                 rmw_32(CAS, &q->tail,
 143                                            (uint32_t)&tail,
 144                                            MAKE_POINTER((next & PTR_MASK), ((tail & COUNT_MASK) >> 32) + 1));
 145                                 thrd_yield();
 146                         } else {
 147                                 *retVal = load_32(&q->nodes[(next & PTR_MASK)].value);
 148                                 success = rmw_32(CAS, &q->head,
 149                                                                 (uint32_t)&head,
 150                                             MAKE_POINTER((next & PTR_MASK), ((head & COUNT_MASK) >> 32) + 1));
 151                                 if (!success)
 152                                         thrd_yield();
 153                         }
 154                 }
 155         }
 156         reclaim((head & PTR_MASK));
 157         return true;
 158 }
 159
 160 /* ms-queue-main */
 161 static int procs = 2;
 162 static queue_t *queue;
 163 static thrd_t *threads;
 164 static unsigned int *input;
 165 static unsigned int *output;
 166 static int num_threads;
 167
 168 int get_thread_num()
 169 {
 170         thrd_t curr = thrd_current();
 171         int i;
 172         for (i = 0; i < num_threads; i++)
 173                 if (curr.priv == threads[i].priv)
 174                         return i;
 175         /* MODEL_ASSERT(0); */
 176         return -1;
 177 }
 178
 179 bool succ1, succ2;
 180
 181 static void main_task(void *param)
 182 {
 183         unsigned int val;
 184         int pid = *((int *)param);
 185         if (!pid) {
 186                 input[0] = 17;
 187                 enqueue(queue, input[0]);
 188                 succ1 = dequeue(queue, &output[0]);
 189                 //printf("Dequeue: %d\n", output[0]);
 190         } else {
 191                 input[1] = 37;
 192                 enqueue(queue, input[1]);
 193                 succ2 = dequeue(queue, &output[1]);
 194         }
 195 }
 196
 197 int user_main(int argc, char **argv)
 198 {
 199         int i;
 200         int *param;
 201         unsigned int in_sum = 0, out_sum = 0;
 202
 203         queue = calloc(1, sizeof(*queue));
 204         // MODEL_ASSERT(queue);
 205
 206         num_threads = procs;
 207         threads = malloc(num_threads * sizeof(thrd_t));
 208         param = malloc(num_threads * sizeof(*param));
 209         input = calloc(num_threads, sizeof(*input));
 210         output = calloc(num_threads, sizeof(*output));
 211
 212         init_queue(queue, num_threads);
 213         for (i = 0; i < num_threads; i++) {
 214                 param[i] = i;
 215                 thrd_create(&threads[i], main_task, &param[i]);
 216         }
 217         for (i = 0; i < num_threads; i++)
 218                 thrd_join(threads[i]);
 219
 220         for (i = 0; i < num_threads; i++) {
 221                 in_sum += input[i];
 222                 out_sum += output[i];
 223         }
 224         for (i = 0; i < num_threads; i++)
 225                 printf("input[%d] = %u\n", i, input[i]);
 226         for (i = 0; i < num_threads; i++)
 227                 printf("output[%d] = %u\n", i, output[i]);
 228         /* if (succ1 && succ2) */
 229         /*      MODEL_ASSERT(in_sum == out_sum); */
 230         /* else */
 231         /*      MODEL_ASSERT (false); */
 232
 233         free(param);
 234         free(threads);
 235         free(queue);
 236
 237         return 0;
 238 }