treiber-stack/my_stack.c

   1 #include <threads.h>
   2 #include <stdlib.h>
   3 #include "librace.h"
   4 #include "model-assert.h"
   5
   6 #include "my_stack.h"
   7
   8 #define MAX_FREELIST 4 /* Each thread can own up to MAX_FREELIST free nodes */
   9 #define INITIAL_FREE 2 /* Each thread starts with INITIAL_FREE free nodes */
  10
  11 #define POISON_IDX 0x666
  12
  13 static unsigned int (*free_lists)[MAX_FREELIST];
  14
  15 /* Search this thread's free list for a "new" node */
  16 static unsigned int new_node()
  17 {
  18         int i;
  19         int t = get_thread_num();
  20         for (i = 0; i < MAX_FREELIST; i++) {
  21                 //unsigned int node = load_32(&free_lists[t][i]);
  22                 unsigned int node = free_lists[t][i];
  23                 if (node) {
  24                         //store_32(&free_lists[t][i], 0);
  25                         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                 unsigned int idx = free_lists[t][i];
  47
  48                 /* Found empty spot in free list */
  49                 if (idx == 0) {
  50                         //store_32(&free_lists[t][i], node);
  51                         free_lists[t][i] = node;
  52                         return;
  53                 }
  54         }
  55         /* free list is full? */
  56         MODEL_ASSERT(0);
  57 }
  58
  59 void init_stack(mystack_t *s, int num_threads)
  60 {
  61         int i, j;
  62
  63         /* Initialize each thread's free list with INITIAL_FREE pointers */
  64         /* The actual nodes are initialized with poison indexes */
  65         free_lists = malloc(num_threads * sizeof(*free_lists));
  66         for (i = 0; i < num_threads; i++) {
  67                 for (j = 0; j < INITIAL_FREE; j++) {
  68                         free_lists[i][j] = 1 + i * MAX_FREELIST + j;
  69                         atomic_init(&s->nodes[free_lists[i][j]].next, MAKE_POINTER(POISON_IDX, 0));
  70                 }
  71         }
  72
  73         /* initialize stack */
  74         atomic_init(&s->top, MAKE_POINTER(0, 0));
  75 }
  76
  77 void push(mystack_t *s, unsigned int val) {
  78         unsigned int nodeIdx = new_node();
  79         node_t *node = &s->nodes[nodeIdx];
  80         node->value = val;
  81         pointer oldTop, newTop;
  82         bool success;
  83         while (true) {
  84                 // acquire
  85                 oldTop = atomic_load_explicit(&s->top, acquire);
  86                 newTop = MAKE_POINTER(nodeIdx, get_count(oldTop) + 1);
  87                 // relaxed
  88                 atomic_store_explicit(&node->next, oldTop, relaxed);
  89
  90                 // release & relaxed
  91                 success = atomic_compare_exchange_strong_explicit(&s->top, &oldTop,
  92                         newTop, release, relaxed);
  93                 if (success)
  94                         break;
  95         }
  96 }
  97
  98 unsigned int pop(mystack_t *s)
  99 {
 100         pointer oldTop, newTop, next;
 101         node_t *node;
 102         bool success;
 103         int val;
 104         while (true) {
 105                 // acquire
 106                 oldTop = atomic_load_explicit(&s->top, acquire);
 107                 if (get_ptr(oldTop) == 0)
 108                         return 0;
 109                 node = &s->nodes[get_ptr(oldTop)];
 110                 // relaxed
 111                 next = atomic_load_explicit(&node->next, relaxed);
 112                 newTop = MAKE_POINTER(get_ptr(next), get_count(oldTop) + 1);
 113                 // release & relaxed
 114                 success = atomic_compare_exchange_strong_explicit(&s->top, &oldTop,
 115                         newTop, release, relaxed);
 116                 if (success)
 117                         break;
 118         }
 119         val = node->value;
 120         /* Reclaim the used slot */
 121         reclaim(get_ptr(oldTop));
 122         return val;
 123 }