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_FIFO_H 29 #define CK_FIFO_H 30 31 #include <ck_cc.h> 32 #include <ck_md.h> 33 #include <ck_pr.h> 34 #include <ck_spinlock.h> 35 #include <ck_stddef.h> 36 37 #ifndef CK_F_FIFO_SPSC 38 #define CK_F_FIFO_SPSC 39 struct ck_fifo_spsc_entry { 40 void *value; 41 struct ck_fifo_spsc_entry *next; 42 }; 43 typedef struct ck_fifo_spsc_entry ck_fifo_spsc_entry_t; 44 45 struct ck_fifo_spsc { 46 ck_spinlock_t m_head; 47 struct ck_fifo_spsc_entry *head; 48 char pad[CK_MD_CACHELINE - sizeof(struct ck_fifo_spsc_entry *) - sizeof(ck_spinlock_t)]; 49 ck_spinlock_t m_tail; 50 struct ck_fifo_spsc_entry *tail; 51 struct ck_fifo_spsc_entry *head_snapshot; 52 struct ck_fifo_spsc_entry *garbage; 53 }; 54 typedef struct ck_fifo_spsc ck_fifo_spsc_t; 55 56 CK_CC_INLINE static bool 57 ck_fifo_spsc_enqueue_trylock(struct ck_fifo_spsc *fifo) 58 { 59 60 return ck_spinlock_trylock(&fifo->m_tail); 61 } 62 63 CK_CC_INLINE static void 64 ck_fifo_spsc_enqueue_lock(struct ck_fifo_spsc *fifo) 65 { 66 67 ck_spinlock_lock(&fifo->m_tail); 68 return; 69 } 70 71 CK_CC_INLINE static void 72 ck_fifo_spsc_enqueue_unlock(struct ck_fifo_spsc *fifo) 73 { 74 75 ck_spinlock_unlock(&fifo->m_tail); 76 return; 77 } 78 79 CK_CC_INLINE static bool 80 ck_fifo_spsc_dequeue_trylock(struct ck_fifo_spsc *fifo) 81 { 82 83 return ck_spinlock_trylock(&fifo->m_head); 84 } 85 86 CK_CC_INLINE static void 87 ck_fifo_spsc_dequeue_lock(struct ck_fifo_spsc *fifo) 88 { 89 90 ck_spinlock_lock(&fifo->m_head); 91 return; 92 } 93 94 CK_CC_INLINE static void 95 ck_fifo_spsc_dequeue_unlock(struct ck_fifo_spsc *fifo) 96 { 97 98 ck_spinlock_unlock(&fifo->m_head); 99 return; 100 } 101 102 CK_CC_INLINE static void 103 ck_fifo_spsc_init(struct ck_fifo_spsc *fifo, struct ck_fifo_spsc_entry *stub) 104 { 105 106 ck_spinlock_init(&fifo->m_head); 107 ck_spinlock_init(&fifo->m_tail); 108 109 stub->next = NULL; 110 fifo->head = fifo->tail = fifo->head_snapshot = fifo->garbage = stub; 111 return; 112 } 113 114 CK_CC_INLINE static void 115 ck_fifo_spsc_deinit(struct ck_fifo_spsc *fifo, struct ck_fifo_spsc_entry **garbage) 116 { 117 118 *garbage = fifo->garbage; 119 fifo->head = fifo->tail = NULL; 120 return; 121 } 122 123 CK_CC_INLINE static void 124 ck_fifo_spsc_enqueue(struct ck_fifo_spsc *fifo, 125 struct ck_fifo_spsc_entry *entry, 126 void *value) 127 { 128 129 entry->value = value; 130 entry->next = NULL; 131 132 /* If stub->next is visible, guarantee that entry is consistent. */ 133 ck_pr_fence_store(); 134 ck_pr_store_ptr(&fifo->tail->next, entry); 135 fifo->tail = entry; 136 return; 137 } 138 139 CK_CC_INLINE static bool 140 ck_fifo_spsc_dequeue(struct ck_fifo_spsc *fifo, void *value) 141 { 142 struct ck_fifo_spsc_entry *entry; 143 144 /* 145 * The head pointer is guaranteed to always point to a stub entry. 146 * If the stub entry does not point to an entry, then the queue is 147 * empty. 148 */ 149 entry = ck_pr_load_ptr(&fifo->head->next); 150 if (entry == NULL) 151 return false; 152 153 /* If entry is visible, guarantee store to value is visible. */ 154 ck_pr_store_ptr_unsafe(value, entry->value); 155 ck_pr_fence_store(); 156 ck_pr_store_ptr(&fifo->head, entry); 157 return true; 158 } 159 160 /* 161 * Recycle a node. This technique for recycling nodes is based on 162 * Dmitriy Vyukov's work. 163 */ 164 CK_CC_INLINE static struct ck_fifo_spsc_entry * 165 ck_fifo_spsc_recycle(struct ck_fifo_spsc *fifo) 166 { 167 struct ck_fifo_spsc_entry *garbage; 168 169 if (fifo->head_snapshot == fifo->garbage) { 170 fifo->head_snapshot = ck_pr_load_ptr(&fifo->head); 171 if (fifo->head_snapshot == fifo->garbage) 172 return NULL; 173 } 174 175 garbage = fifo->garbage; 176 fifo->garbage = garbage->next; 177 return garbage; 178 } 179 180 CK_CC_INLINE static bool 181 ck_fifo_spsc_isempty(struct ck_fifo_spsc *fifo) 182 { 183 struct ck_fifo_spsc_entry *head = ck_pr_load_ptr(&fifo->head); 184 return ck_pr_load_ptr(&head->next) == NULL; 185 } 186 187 #define CK_FIFO_SPSC_ISEMPTY(f) ((f)->head->next == NULL) 188 #define CK_FIFO_SPSC_FIRST(f) ((f)->head->next) 189 #define CK_FIFO_SPSC_NEXT(m) ((m)->next) 190 #define CK_FIFO_SPSC_SPARE(f) ((f)->head) 191 #define CK_FIFO_SPSC_FOREACH(fifo, entry) \ 192 for ((entry) = CK_FIFO_SPSC_FIRST(fifo); \ 193 (entry) != NULL; \ 194 (entry) = CK_FIFO_SPSC_NEXT(entry)) 195 #define CK_FIFO_SPSC_FOREACH_SAFE(fifo, entry, T) \ 196 for ((entry) = CK_FIFO_SPSC_FIRST(fifo); \ 197 (entry) != NULL && ((T) = (entry)->next, 1); \ 198 (entry) = (T)) 199 200 #endif /* CK_F_FIFO_SPSC */ 201 202 #ifdef CK_F_PR_CAS_PTR_2 203 #ifndef CK_F_FIFO_MPMC 204 #define CK_F_FIFO_MPMC 205 struct ck_fifo_mpmc_entry; 206 struct ck_fifo_mpmc_pointer { 207 struct ck_fifo_mpmc_entry *pointer; 208 char *generation CK_CC_PACKED; 209 } CK_CC_ALIGN(16); 210 211 struct ck_fifo_mpmc_entry { 212 void *value; 213 struct ck_fifo_mpmc_pointer next; 214 }; 215 typedef struct ck_fifo_mpmc_entry ck_fifo_mpmc_entry_t; 216 217 struct ck_fifo_mpmc { 218 struct ck_fifo_mpmc_pointer head; 219 char pad[CK_MD_CACHELINE - sizeof(struct ck_fifo_mpmc_pointer)]; 220 struct ck_fifo_mpmc_pointer tail; 221 }; 222 typedef struct ck_fifo_mpmc ck_fifo_mpmc_t; 223 224 CK_CC_INLINE static void 225 ck_fifo_mpmc_init(struct ck_fifo_mpmc *fifo, struct ck_fifo_mpmc_entry *stub) 226 { 227 228 stub->next.pointer = NULL; 229 stub->next.generation = NULL; 230 fifo->head.pointer = fifo->tail.pointer = stub; 231 fifo->head.generation = fifo->tail.generation = NULL; 232 return; 233 } 234 235 CK_CC_INLINE static void 236 ck_fifo_mpmc_deinit(struct ck_fifo_mpmc *fifo, struct ck_fifo_mpmc_entry **garbage) 237 { 238 239 *garbage = fifo->head.pointer; 240 fifo->head.pointer = fifo->tail.pointer = NULL; 241 return; 242 } 243 244 CK_CC_INLINE static void 245 ck_fifo_mpmc_enqueue(struct ck_fifo_mpmc *fifo, 246 struct ck_fifo_mpmc_entry *entry, 247 void *value) 248 { 249 struct ck_fifo_mpmc_pointer tail, next, update; 250 251 /* 252 * Prepare the upcoming node and make sure to commit the updates 253 * before publishing. 254 */ 255 entry->value = value; 256 entry->next.pointer = NULL; 257 entry->next.generation = 0; 258 ck_pr_fence_store_atomic(); 259 260 for (;;) { 261 tail.generation = ck_pr_load_ptr(&fifo->tail.generation); 262 ck_pr_fence_load(); 263 tail.pointer = ck_pr_load_ptr(&fifo->tail.pointer); 264 next.generation = ck_pr_load_ptr(&tail.pointer->next.generation); 265 ck_pr_fence_load(); 266 next.pointer = ck_pr_load_ptr(&tail.pointer->next.pointer); 267 268 if (ck_pr_load_ptr(&fifo->tail.generation) != tail.generation) 269 continue; 270 271 if (next.pointer != NULL) { 272 /* 273 * If the tail pointer has an entry following it then 274 * it needs to be forwarded to the next entry. This 275 * helps us guarantee we are always operating on the 276 * last entry. 277 */ 278 update.pointer = next.pointer; 279 update.generation = tail.generation + 1; 280 ck_pr_cas_ptr_2(&fifo->tail, &tail, &update); 281 } else { 282 /* 283 * Attempt to commit new entry to the end of the 284 * current tail. 285 */ 286 update.pointer = entry; 287 update.generation = next.generation + 1; 288 if (ck_pr_cas_ptr_2(&tail.pointer->next, &next, &update) == true) 289 break; 290 } 291 } 292 293 ck_pr_fence_atomic(); 294 295 /* After a successful insert, forward the tail to the new entry. */ 296 update.generation = tail.generation + 1; 297 ck_pr_cas_ptr_2(&fifo->tail, &tail, &update); 298 return; 299 } 300 301 CK_CC_INLINE static bool 302 ck_fifo_mpmc_tryenqueue(struct ck_fifo_mpmc *fifo, 303 struct ck_fifo_mpmc_entry *entry, 304 void *value) 305 { 306 struct ck_fifo_mpmc_pointer tail, next, update; 307 308 entry->value = value; 309 entry->next.pointer = NULL; 310 entry->next.generation = 0; 311 312 ck_pr_fence_store_atomic(); 313 314 tail.generation = ck_pr_load_ptr(&fifo->tail.generation); 315 ck_pr_fence_load(); 316 tail.pointer = ck_pr_load_ptr(&fifo->tail.pointer); 317 next.generation = ck_pr_load_ptr(&tail.pointer->next.generation); 318 ck_pr_fence_load(); 319 next.pointer = ck_pr_load_ptr(&tail.pointer->next.pointer); 320 321 if (ck_pr_load_ptr(&fifo->tail.generation) != tail.generation) 322 return false; 323 324 if (next.pointer != NULL) { 325 /* 326 * If the tail pointer has an entry following it then 327 * it needs to be forwarded to the next entry. This 328 * helps us guarantee we are always operating on the 329 * last entry. 330 */ 331 update.pointer = next.pointer; 332 update.generation = tail.generation + 1; 333 ck_pr_cas_ptr_2(&fifo->tail, &tail, &update); 334 return false; 335 } else { 336 /* 337 * Attempt to commit new entry to the end of the 338 * current tail. 339 */ 340 update.pointer = entry; 341 update.generation = next.generation + 1; 342 if (ck_pr_cas_ptr_2(&tail.pointer->next, &next, &update) == false) 343 return false; 344 } 345 346 ck_pr_fence_atomic(); 347 348 /* After a successful insert, forward the tail to the new entry. */ 349 update.generation = tail.generation + 1; 350 ck_pr_cas_ptr_2(&fifo->tail, &tail, &update); 351 return true; 352 } 353 354 CK_CC_INLINE static bool 355 ck_fifo_mpmc_dequeue(struct ck_fifo_mpmc *fifo, 356 void *value, 357 struct ck_fifo_mpmc_entry **garbage) 358 { 359 struct ck_fifo_mpmc_pointer head, tail, next, update; 360 361 for (;;) { 362 head.generation = ck_pr_load_ptr(&fifo->head.generation); 363 ck_pr_fence_load(); 364 head.pointer = ck_pr_load_ptr(&fifo->head.pointer); 365 tail.generation = ck_pr_load_ptr(&fifo->tail.generation); 366 ck_pr_fence_load(); 367 tail.pointer = ck_pr_load_ptr(&fifo->tail.pointer); 368 369 next.generation = ck_pr_load_ptr(&head.pointer->next.generation); 370 ck_pr_fence_load(); 371 next.pointer = ck_pr_load_ptr(&head.pointer->next.pointer); 372 373 update.pointer = next.pointer; 374 if (head.pointer == tail.pointer) { 375 /* 376 * The head is guaranteed to always point at a stub 377 * entry. If the stub entry has no references then the 378 * queue is empty. 379 */ 380 if (next.pointer == NULL) 381 return false; 382 383 /* Forward the tail pointer if necessary. */ 384 update.generation = tail.generation + 1; 385 ck_pr_cas_ptr_2(&fifo->tail, &tail, &update); 386 } else { 387 /* 388 * It is possible for head snapshot to have been 389 * re-used. Avoid deferencing during enqueue 390 * re-use. 391 */ 392 if (next.pointer == NULL) 393 continue; 394 395 /* Save value before commit. */ 396 *(void **)value = ck_pr_load_ptr(&next.pointer->value); 397 398 /* Forward the head pointer to the next entry. */ 399 update.generation = head.generation + 1; 400 if (ck_pr_cas_ptr_2(&fifo->head, &head, &update) == true) 401 break; 402 } 403 } 404 405 *garbage = head.pointer; 406 return true; 407 } 408 409 CK_CC_INLINE static bool 410 ck_fifo_mpmc_trydequeue(struct ck_fifo_mpmc *fifo, 411 void *value, 412 struct ck_fifo_mpmc_entry **garbage) 413 { 414 struct ck_fifo_mpmc_pointer head, tail, next, update; 415 416 head.generation = ck_pr_load_ptr(&fifo->head.generation); 417 ck_pr_fence_load(); 418 head.pointer = ck_pr_load_ptr(&fifo->head.pointer); 419 420 tail.generation = ck_pr_load_ptr(&fifo->tail.generation); 421 ck_pr_fence_load(); 422 tail.pointer = ck_pr_load_ptr(&fifo->tail.pointer); 423 424 next.generation = ck_pr_load_ptr(&head.pointer->next.generation); 425 ck_pr_fence_load(); 426 next.pointer = ck_pr_load_ptr(&head.pointer->next.pointer); 427 428 update.pointer = next.pointer; 429 if (head.pointer == tail.pointer) { 430 /* 431 * The head is guaranteed to always point at a stub 432 * entry. If the stub entry has no references then the 433 * queue is empty. 434 */ 435 if (next.pointer == NULL) 436 return false; 437 438 /* Forward the tail pointer if necessary. */ 439 update.generation = tail.generation + 1; 440 ck_pr_cas_ptr_2(&fifo->tail, &tail, &update); 441 return false; 442 } else { 443 /* 444 * It is possible for head snapshot to have been 445 * re-used. Avoid deferencing during enqueue. 446 */ 447 if (next.pointer == NULL) 448 return false; 449 450 /* Save value before commit. */ 451 *(void **)value = ck_pr_load_ptr(&next.pointer->value); 452 453 /* Forward the head pointer to the next entry. */ 454 update.generation = head.generation + 1; 455 if (ck_pr_cas_ptr_2(&fifo->head, &head, &update) == false) 456 return false; 457 } 458 459 *garbage = head.pointer; 460 return true; 461 } 462 463 #define CK_FIFO_MPMC_ISEMPTY(f) ((f)->head.pointer->next.pointer == NULL) 464 #define CK_FIFO_MPMC_FIRST(f) ((f)->head.pointer->next.pointer) 465 #define CK_FIFO_MPMC_NEXT(m) ((m)->next.pointer) 466 #define CK_FIFO_MPMC_FOREACH(fifo, entry) \ 467 for ((entry) = CK_FIFO_MPMC_FIRST(fifo); \ 468 (entry) != NULL; \ 469 (entry) = CK_FIFO_MPMC_NEXT(entry)) 470 #define CK_FIFO_MPMC_FOREACH_SAFE(fifo, entry, T) \ 471 for ((entry) = CK_FIFO_MPMC_FIRST(fifo); \ 472 (entry) != NULL && ((T) = (entry)->next.pointer, 1); \ 473 (entry) = (T)) 474 475 #endif /* CK_F_FIFO_MPMC */ 476 #endif /* CK_F_PR_CAS_PTR_2 */ 477 478 #endif /* CK_FIFO_H */ 479