1309260Scognet/* 2309260Scognet * Copyright 2010-2015 Samy Al Bahra. 3309260Scognet * Copyright 2011 David Joseph. 4309260Scognet * All rights reserved. 5309260Scognet * 6309260Scognet * Redistribution and use in source and binary forms, with or without 7309260Scognet * modification, are permitted provided that the following conditions 8309260Scognet * are met: 9309260Scognet * 1. Redistributions of source code must retain the above copyright 10309260Scognet * notice, this list of conditions and the following disclaimer. 11309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 12309260Scognet * notice, this list of conditions and the following disclaimer in the 13309260Scognet * documentation and/or other materials provided with the distribution. 14309260Scognet * 15309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25309260Scognet * SUCH DAMAGE. 26309260Scognet */ 27309260Scognet 28309260Scognet#ifndef CK_HP_FIFO_H 29309260Scognet#define CK_HP_FIFO_H 30309260Scognet 31309260Scognet#include <ck_cc.h> 32309260Scognet#include <ck_hp.h> 33309260Scognet#include <ck_pr.h> 34309260Scognet#include <ck_stddef.h> 35309260Scognet 36309260Scognet#define CK_HP_FIFO_SLOTS_COUNT (2) 37309260Scognet#define CK_HP_FIFO_SLOTS_SIZE (sizeof(void *) * CK_HP_FIFO_SLOTS_COUNT) 38309260Scognet 39309260Scognet/* 40309260Scognet * Though it is possible to embed the data structure, measurements need 41309260Scognet * to be made for the cost of this. If we were to embed the hazard pointer 42309260Scognet * state into the data structure, this means every deferred reclamation 43309260Scognet * will also include a cache invalidation when linking into the hazard pointer 44309260Scognet * pending queue. This may lead to terrible cache line bouncing. 45309260Scognet */ 46309260Scognetstruct ck_hp_fifo_entry { 47309260Scognet void *value; 48309260Scognet ck_hp_hazard_t hazard; 49309260Scognet struct ck_hp_fifo_entry *next; 50309260Scognet}; 51309260Scognettypedef struct ck_hp_fifo_entry ck_hp_fifo_entry_t; 52309260Scognet 53309260Scognetstruct ck_hp_fifo { 54309260Scognet struct ck_hp_fifo_entry *head; 55309260Scognet struct ck_hp_fifo_entry *tail; 56309260Scognet}; 57309260Scognettypedef struct ck_hp_fifo ck_hp_fifo_t; 58309260Scognet 59309260ScognetCK_CC_INLINE static void 60309260Scognetck_hp_fifo_init(struct ck_hp_fifo *fifo, struct ck_hp_fifo_entry *stub) 61309260Scognet{ 62309260Scognet 63309260Scognet fifo->head = fifo->tail = stub; 64309260Scognet stub->next = NULL; 65309260Scognet return; 66309260Scognet} 67309260Scognet 68309260ScognetCK_CC_INLINE static void 69309260Scognetck_hp_fifo_deinit(struct ck_hp_fifo *fifo, struct ck_hp_fifo_entry **stub) 70309260Scognet{ 71309260Scognet 72309260Scognet *stub = fifo->head; 73309260Scognet fifo->head = fifo->tail = NULL; 74309260Scognet return; 75309260Scognet} 76309260Scognet 77309260ScognetCK_CC_INLINE static void 78309260Scognetck_hp_fifo_enqueue_mpmc(ck_hp_record_t *record, 79309260Scognet struct ck_hp_fifo *fifo, 80309260Scognet struct ck_hp_fifo_entry *entry, 81309260Scognet void *value) 82309260Scognet{ 83309260Scognet struct ck_hp_fifo_entry *tail, *next; 84309260Scognet 85309260Scognet entry->value = value; 86309260Scognet entry->next = NULL; 87309260Scognet ck_pr_fence_store_atomic(); 88309260Scognet 89309260Scognet for (;;) { 90309260Scognet tail = ck_pr_load_ptr(&fifo->tail); 91309260Scognet ck_hp_set_fence(record, 0, tail); 92309260Scognet if (tail != ck_pr_load_ptr(&fifo->tail)) 93309260Scognet continue; 94309260Scognet 95309260Scognet next = ck_pr_load_ptr(&tail->next); 96309260Scognet if (next != NULL) { 97309260Scognet ck_pr_cas_ptr(&fifo->tail, tail, next); 98309260Scognet continue; 99309260Scognet } else if (ck_pr_cas_ptr(&fifo->tail->next, next, entry) == true) 100309260Scognet break; 101309260Scognet } 102309260Scognet 103309260Scognet ck_pr_fence_atomic(); 104309260Scognet ck_pr_cas_ptr(&fifo->tail, tail, entry); 105309260Scognet return; 106309260Scognet} 107309260Scognet 108309260ScognetCK_CC_INLINE static bool 109309260Scognetck_hp_fifo_tryenqueue_mpmc(ck_hp_record_t *record, 110309260Scognet struct ck_hp_fifo *fifo, 111309260Scognet struct ck_hp_fifo_entry *entry, 112309260Scognet void *value) 113309260Scognet{ 114309260Scognet struct ck_hp_fifo_entry *tail, *next; 115309260Scognet 116309260Scognet entry->value = value; 117309260Scognet entry->next = NULL; 118309260Scognet ck_pr_fence_store_atomic(); 119309260Scognet 120309260Scognet tail = ck_pr_load_ptr(&fifo->tail); 121309260Scognet ck_hp_set_fence(record, 0, tail); 122309260Scognet if (tail != ck_pr_load_ptr(&fifo->tail)) 123309260Scognet return false; 124309260Scognet 125309260Scognet next = ck_pr_load_ptr(&tail->next); 126309260Scognet if (next != NULL) { 127309260Scognet ck_pr_cas_ptr(&fifo->tail, tail, next); 128309260Scognet return false; 129309260Scognet } else if (ck_pr_cas_ptr(&fifo->tail->next, next, entry) == false) 130309260Scognet return false; 131309260Scognet 132309260Scognet ck_pr_fence_atomic(); 133309260Scognet ck_pr_cas_ptr(&fifo->tail, tail, entry); 134309260Scognet return true; 135309260Scognet} 136309260Scognet 137309260ScognetCK_CC_INLINE static struct ck_hp_fifo_entry * 138309260Scognetck_hp_fifo_dequeue_mpmc(ck_hp_record_t *record, 139309260Scognet struct ck_hp_fifo *fifo, 140309260Scognet void *value) 141309260Scognet{ 142309260Scognet struct ck_hp_fifo_entry *head, *tail, *next; 143309260Scognet 144309260Scognet for (;;) { 145309260Scognet head = ck_pr_load_ptr(&fifo->head); 146309260Scognet ck_pr_fence_load(); 147309260Scognet tail = ck_pr_load_ptr(&fifo->tail); 148309260Scognet ck_hp_set_fence(record, 0, head); 149309260Scognet if (head != ck_pr_load_ptr(&fifo->head)) 150309260Scognet continue; 151309260Scognet 152309260Scognet next = ck_pr_load_ptr(&head->next); 153309260Scognet ck_hp_set_fence(record, 1, next); 154309260Scognet if (head != ck_pr_load_ptr(&fifo->head)) 155309260Scognet continue; 156309260Scognet 157309260Scognet if (head == tail) { 158309260Scognet if (next == NULL) 159309260Scognet return NULL; 160309260Scognet 161309260Scognet ck_pr_cas_ptr(&fifo->tail, tail, next); 162309260Scognet continue; 163309260Scognet } else if (ck_pr_cas_ptr(&fifo->head, head, next) == true) 164309260Scognet break; 165309260Scognet } 166309260Scognet 167309260Scognet ck_pr_store_ptr_unsafe(value, next->value); 168309260Scognet return head; 169309260Scognet} 170309260Scognet 171309260ScognetCK_CC_INLINE static struct ck_hp_fifo_entry * 172309260Scognetck_hp_fifo_trydequeue_mpmc(ck_hp_record_t *record, 173309260Scognet struct ck_hp_fifo *fifo, 174309260Scognet void *value) 175309260Scognet{ 176309260Scognet struct ck_hp_fifo_entry *head, *tail, *next; 177309260Scognet 178309260Scognet head = ck_pr_load_ptr(&fifo->head); 179309260Scognet ck_pr_fence_load(); 180309260Scognet tail = ck_pr_load_ptr(&fifo->tail); 181309260Scognet ck_hp_set_fence(record, 0, head); 182309260Scognet if (head != ck_pr_load_ptr(&fifo->head)) 183309260Scognet return NULL; 184309260Scognet 185309260Scognet next = ck_pr_load_ptr(&head->next); 186309260Scognet ck_hp_set_fence(record, 1, next); 187309260Scognet if (head != ck_pr_load_ptr(&fifo->head)) 188309260Scognet return NULL; 189309260Scognet 190309260Scognet if (head == tail) { 191309260Scognet if (next == NULL) 192309260Scognet return NULL; 193309260Scognet 194309260Scognet ck_pr_cas_ptr(&fifo->tail, tail, next); 195309260Scognet return NULL; 196309260Scognet } else if (ck_pr_cas_ptr(&fifo->head, head, next) == false) 197309260Scognet return NULL; 198309260Scognet 199309260Scognet ck_pr_store_ptr_unsafe(value, next->value); 200309260Scognet return head; 201309260Scognet} 202309260Scognet 203309260Scognet#define CK_HP_FIFO_ISEMPTY(f) ((f)->head->next == NULL) 204309260Scognet#define CK_HP_FIFO_FIRST(f) ((f)->head->next) 205309260Scognet#define CK_HP_FIFO_NEXT(m) ((m)->next) 206309260Scognet#define CK_HP_FIFO_FOREACH(fifo, entry) \ 207309260Scognet for ((entry) = CK_HP_FIFO_FIRST(fifo); \ 208309260Scognet (entry) != NULL; \ 209309260Scognet (entry) = CK_HP_FIFO_NEXT(entry)) 210309260Scognet#define CK_HP_FIFO_FOREACH_SAFE(fifo, entry, T) \ 211309260Scognet for ((entry) = CK_HP_FIFO_FIRST(fifo); \ 212309260Scognet (entry) != NULL && ((T) = (entry)->next, 1); \ 213309260Scognet (entry) = (T)) 214309260Scognet 215309260Scognet#endif /* CK_HP_FIFO_H */ 216