1 /*
2 * Copyright 2010-2015 Samy Al Bahra.
3 * Copyright 2011 David Joseph.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27
28 #ifndef CK_HP_FIFO_H
29 #define CK_HP_FIFO_H
30
31 #include <ck_cc.h>
32 #include <ck_hp.h>
33 #include <ck_pr.h>
34 #include <ck_stddef.h>
35
36 #define CK_HP_FIFO_SLOTS_COUNT (2)
37 #define CK_HP_FIFO_SLOTS_SIZE (sizeof(void *) * CK_HP_FIFO_SLOTS_COUNT)
38
39 /*
40 * Though it is possible to embed the data structure, measurements need
41 * to be made for the cost of this. If we were to embed the hazard pointer
42 * state into the data structure, this means every deferred reclamation
43 * will also include a cache invalidation when linking into the hazard pointer
44 * pending queue. This may lead to terrible cache line bouncing.
45 */
46 struct ck_hp_fifo_entry {
47 void *value;
48 ck_hp_hazard_t hazard;
49 struct ck_hp_fifo_entry *next;
50 };
51 typedef struct ck_hp_fifo_entry ck_hp_fifo_entry_t;
52
53 struct ck_hp_fifo {
54 struct ck_hp_fifo_entry *head;
55 struct ck_hp_fifo_entry *tail;
56 };
57 typedef struct ck_hp_fifo ck_hp_fifo_t;
58
59 CK_CC_INLINE static void
ck_hp_fifo_init(struct ck_hp_fifo * fifo,struct ck_hp_fifo_entry * stub)60 ck_hp_fifo_init(struct ck_hp_fifo *fifo, struct ck_hp_fifo_entry *stub)
61 {
62
63 fifo->head = fifo->tail = stub;
64 stub->next = NULL;
65 return;
66 }
67
68 CK_CC_INLINE static void
ck_hp_fifo_deinit(struct ck_hp_fifo * fifo,struct ck_hp_fifo_entry ** stub)69 ck_hp_fifo_deinit(struct ck_hp_fifo *fifo, struct ck_hp_fifo_entry **stub)
70 {
71
72 *stub = fifo->head;
73 fifo->head = fifo->tail = NULL;
74 return;
75 }
76
77 CK_CC_INLINE static void
ck_hp_fifo_enqueue_mpmc(ck_hp_record_t * record,struct ck_hp_fifo * fifo,struct ck_hp_fifo_entry * entry,void * value)78 ck_hp_fifo_enqueue_mpmc(ck_hp_record_t *record,
79 struct ck_hp_fifo *fifo,
80 struct ck_hp_fifo_entry *entry,
81 void *value)
82 {
83 struct ck_hp_fifo_entry *tail, *next;
84
85 entry->value = value;
86 entry->next = NULL;
87 ck_pr_fence_store_atomic();
88
89 for (;;) {
90 tail = ck_pr_load_ptr(&fifo->tail);
91 ck_hp_set_fence(record, 0, tail);
92 if (tail != ck_pr_load_ptr(&fifo->tail))
93 continue;
94
95 next = ck_pr_load_ptr(&tail->next);
96 if (next != NULL) {
97 ck_pr_cas_ptr(&fifo->tail, tail, next);
98 continue;
99 } else if (ck_pr_cas_ptr(&fifo->tail->next, next, entry) == true)
100 break;
101 }
102
103 ck_pr_fence_atomic();
104 ck_pr_cas_ptr(&fifo->tail, tail, entry);
105 return;
106 }
107
108 CK_CC_INLINE static bool
ck_hp_fifo_tryenqueue_mpmc(ck_hp_record_t * record,struct ck_hp_fifo * fifo,struct ck_hp_fifo_entry * entry,void * value)109 ck_hp_fifo_tryenqueue_mpmc(ck_hp_record_t *record,
110 struct ck_hp_fifo *fifo,
111 struct ck_hp_fifo_entry *entry,
112 void *value)
113 {
114 struct ck_hp_fifo_entry *tail, *next;
115
116 entry->value = value;
117 entry->next = NULL;
118 ck_pr_fence_store_atomic();
119
120 tail = ck_pr_load_ptr(&fifo->tail);
121 ck_hp_set_fence(record, 0, tail);
122 if (tail != ck_pr_load_ptr(&fifo->tail))
123 return false;
124
125 next = ck_pr_load_ptr(&tail->next);
126 if (next != NULL) {
127 ck_pr_cas_ptr(&fifo->tail, tail, next);
128 return false;
129 } else if (ck_pr_cas_ptr(&fifo->tail->next, next, entry) == false)
130 return false;
131
132 ck_pr_fence_atomic();
133 ck_pr_cas_ptr(&fifo->tail, tail, entry);
134 return true;
135 }
136
137 CK_CC_INLINE static struct ck_hp_fifo_entry *
ck_hp_fifo_dequeue_mpmc(ck_hp_record_t * record,struct ck_hp_fifo * fifo,void * value)138 ck_hp_fifo_dequeue_mpmc(ck_hp_record_t *record,
139 struct ck_hp_fifo *fifo,
140 void *value)
141 {
142 struct ck_hp_fifo_entry *head, *tail, *next;
143
144 for (;;) {
145 head = ck_pr_load_ptr(&fifo->head);
146 ck_pr_fence_load();
147 tail = ck_pr_load_ptr(&fifo->tail);
148 ck_hp_set_fence(record, 0, head);
149 if (head != ck_pr_load_ptr(&fifo->head))
150 continue;
151
152 next = ck_pr_load_ptr(&head->next);
153 ck_hp_set_fence(record, 1, next);
154 if (head != ck_pr_load_ptr(&fifo->head))
155 continue;
156
157 if (head == tail) {
158 if (next == NULL)
159 return NULL;
160
161 ck_pr_cas_ptr(&fifo->tail, tail, next);
162 continue;
163 } else if (ck_pr_cas_ptr(&fifo->head, head, next) == true)
164 break;
165 }
166
167 ck_pr_store_ptr_unsafe(value, next->value);
168 return head;
169 }
170
171 CK_CC_INLINE static struct ck_hp_fifo_entry *
ck_hp_fifo_trydequeue_mpmc(ck_hp_record_t * record,struct ck_hp_fifo * fifo,void * value)172 ck_hp_fifo_trydequeue_mpmc(ck_hp_record_t *record,
173 struct ck_hp_fifo *fifo,
174 void *value)
175 {
176 struct ck_hp_fifo_entry *head, *tail, *next;
177
178 head = ck_pr_load_ptr(&fifo->head);
179 ck_pr_fence_load();
180 tail = ck_pr_load_ptr(&fifo->tail);
181 ck_hp_set_fence(record, 0, head);
182 if (head != ck_pr_load_ptr(&fifo->head))
183 return NULL;
184
185 next = ck_pr_load_ptr(&head->next);
186 ck_hp_set_fence(record, 1, next);
187 if (head != ck_pr_load_ptr(&fifo->head))
188 return NULL;
189
190 if (head == tail) {
191 if (next == NULL)
192 return NULL;
193
194 ck_pr_cas_ptr(&fifo->tail, tail, next);
195 return NULL;
196 } else if (ck_pr_cas_ptr(&fifo->head, head, next) == false)
197 return NULL;
198
199 ck_pr_store_ptr_unsafe(value, next->value);
200 return head;
201 }
202
203 #define CK_HP_FIFO_ISEMPTY(f) ((f)->head->next == NULL)
204 #define CK_HP_FIFO_FIRST(f) ((f)->head->next)
205 #define CK_HP_FIFO_NEXT(m) ((m)->next)
206 #define CK_HP_FIFO_FOREACH(fifo, entry) \
207 for ((entry) = CK_HP_FIFO_FIRST(fifo); \
208 (entry) != NULL; \
209 (entry) = CK_HP_FIFO_NEXT(entry))
210 #define CK_HP_FIFO_FOREACH_SAFE(fifo, entry, T) \
211 for ((entry) = CK_HP_FIFO_FIRST(fifo); \
212 (entry) != NULL && ((T) = (entry)->next, 1); \
213 (entry) = (T))
214
215 #endif /* CK_HP_FIFO_H */
216