3 // #include "librace.h"
4 // #include "model-assert.h"
7 #include "libinterface.h"
9 #define relaxed memory_order_relaxed
10 #define release memory_order_release
11 #define acquire memory_order_acquire
13 #define MAX_FREELIST 4 /* Each thread can own up to MAX_FREELIST free nodes */
14 #define INITIAL_FREE 2 /* Each thread starts with INITIAL_FREE free nodes */
16 #define POISON_IDX 0x666
18 static unsigned int (*free_lists)[MAX_FREELIST];
20 /* Search this thread's free list for a "new" node */
21 static unsigned int new_node()
24 int t = get_thread_num();
25 for (i = 0; i < MAX_FREELIST; i++) {
26 unsigned int node = load_32(&free_lists[t][i]);
28 store_32(&free_lists[t][i], 0);
32 /* free_list is empty? */
37 /* Place this node index back on this thread's free list */
38 static void reclaim(unsigned int node)
41 int t = get_thread_num();
43 /* Don't reclaim NULL node */
44 // MODEL_ASSERT(node);
46 for (i = 0; i < MAX_FREELIST; i++) {
47 /* Should never race with our own thread here */
48 unsigned int idx = load_32(&free_lists[t][i]);
50 /* Found empty spot in free list */
52 store_32(&free_lists[t][i], node);
56 /* free list is full? */
60 void init_queue(queue_t *q, int num_threads)
64 /* Initialize each thread's free list with INITIAL_FREE pointers */
65 /* The actual nodes are initialized with poison indexes */
66 free_lists = malloc(num_threads * sizeof(*free_lists));
67 for (i = 0; i < num_threads; i++) {
68 for (j = 0; j < INITIAL_FREE; j++) {
69 free_lists[i][j] = 2 + i * MAX_FREELIST + j;
70 atomic_init(&q->nodes[free_lists[i][j]].next, MAKE_POINTER(POISON_IDX, 0));
74 /* initialize queue */
75 atomic_init(&q->head, MAKE_POINTER(1, 0));
76 atomic_init(&q->tail, MAKE_POINTER(1, 0));
77 atomic_init(&q->nodes[1].next, MAKE_POINTER(0, 0));
80 void enqueue(queue_t *q, unsigned int val)
89 store_32(&q->nodes[node].value, val);
90 tmp = atomic_load_explicit(&q->nodes[node].next, relaxed);
91 // manually inlined macro: set_ptr(&tmp, 0); // NULL
92 tmp = (tmp & ~PTR_MASK);
93 atomic_store_explicit(&q->nodes[node].next, tmp, relaxed);
96 pointer_t * qt = &q->tail;
97 tail = atomic_load_explicit(qt, acquire);
98 pointer_t * qn = &q->nodes[tail & PTR_MASK].next;
99 next = atomic_load_explicit(qn, acquire);
100 if (tail == atomic_load_explicit(&q->tail, relaxed)) {
102 /* Check for uninitialized 'next' */
103 // MODEL_ASSERT(get_ptr(next) != POISON_IDX);
105 if ((next & PTR_MASK) == 0) { // == NULL
106 pointer value = MAKE_POINTER(node, ((next & COUNT_MASK) >> 32) + 1);
107 success = atomic_compare_exchange_strong_explicit(&q->nodes[tail & PTR_MASK].next,
108 &next, value, release, release);
111 unsigned int ptr = (atomic_load_explicit(&q->nodes[tail & PTR_MASK].next, acquire) & PTR_MASK);
112 pointer value = MAKE_POINTER(ptr,
113 ((tail & COUNT_MASK) >> 32) + 1);
114 atomic_compare_exchange_strong_explicit(&q->tail,
121 atomic_compare_exchange_strong_explicit(&q->tail,
123 MAKE_POINTER(node, ((tail & COUNT_MASK) >> 32) + 1),
127 bool dequeue(queue_t *q, unsigned int *retVal)
135 head = atomic_load_explicit(&q->head, acquire);
136 tail = atomic_load_explicit(&q->tail, relaxed);
137 next = atomic_load_explicit(&q->nodes[(head & PTR_MASK)].next, acquire);
138 if (atomic_load_explicit(&q->head, relaxed) == head) {
139 if ((head & PTR_MASK) == (tail & PTR_MASK)) {
141 /* Check for uninitialized 'next' */
142 // MODEL_ASSERT(get_ptr(next) != POISON_IDX);
144 if (get_ptr(next) == 0) { // NULL
145 return false; // NULL
147 atomic_compare_exchange_strong_explicit(&q->tail,
149 MAKE_POINTER((next & PTR_MASK), ((tail & COUNT_MASK) >> 32) + 1),
153 *retVal = load_32(&q->nodes[(next & PTR_MASK)].value);
154 success = atomic_compare_exchange_strong_explicit(&q->head,
156 MAKE_POINTER((next & PTR_MASK), ((head & COUNT_MASK) >> 32) + 1),
163 reclaim((head & PTR_MASK));