include/ck_hp_fifo.h

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