ck_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_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 */
Cache object: fbdb0dd2374db1662226b9a15762bf00
[ 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_fifo.h

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