ck_hp_fifo.h

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

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

Cache object: a1764a5b919a2f49f47c3fb2bb9d1805

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/contrib/ck/include/ck_hp_fifo.h

FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/include/ck_hp_fifo.h