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 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 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 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 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 * 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 * 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