ck_barrier_combining.c

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 2011-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 #include <ck_barrier.h>
   29 #include <ck_cc.h>
   30 #include <ck_pr.h>
   31 #include <ck_spinlock.h>
   32 
   33 struct ck_barrier_combining_queue {
   34         struct ck_barrier_combining_group *head;
   35         struct ck_barrier_combining_group *tail;
   36 };
   37 
   38 static struct ck_barrier_combining_group *
   39 ck_barrier_combining_queue_dequeue(struct ck_barrier_combining_queue *queue)
   40 {
   41         struct ck_barrier_combining_group *front = NULL;
   42 
   43         if (queue->head != NULL) {
   44                 front = queue->head;
   45                 queue->head = queue->head->next;
   46         }
   47 
   48         return front;
   49 }
   50 
   51 static void
   52 ck_barrier_combining_insert(struct ck_barrier_combining_group *parent,
   53     struct ck_barrier_combining_group *tnode,
   54     struct ck_barrier_combining_group **child)
   55 {
   56 
   57         *child = tnode;
   58         tnode->parent = parent;
   59 
   60         /*
   61          * After inserting, we must increment the parent group's count for
   62          * number of threads expected to reach it; otherwise, the
   63          * barrier may end prematurely.
   64          */
   65         parent->k++;
   66         return;
   67 }
   68 
   69 /*
   70  * This implementation of software combining tree barriers
   71  * uses level order traversal to insert new thread groups
   72  * into the barrier's tree. We use a queue to implement this
   73  * traversal.
   74  */
   75 static void
   76 ck_barrier_combining_queue_enqueue(struct ck_barrier_combining_queue *queue,
   77     struct ck_barrier_combining_group *node_value)
   78 {
   79 
   80         node_value->next = NULL;
   81         if (queue->head == NULL) {
   82                 queue->head = queue->tail = node_value;
   83                 return;
   84         }
   85 
   86         queue->tail->next = node_value;
   87         queue->tail = node_value;
   88 
   89         return;
   90 }
   91 
   92 
   93 void
   94 ck_barrier_combining_group_init(struct ck_barrier_combining *root,
   95     struct ck_barrier_combining_group *tnode,
   96     unsigned int nthr)
   97 {
   98         struct ck_barrier_combining_group *node;
   99         struct ck_barrier_combining_queue queue;
  100 
  101         queue.head = queue.tail = NULL;
  102 
  103         tnode->k = nthr;
  104         tnode->count = 0;
  105         tnode->sense = 0;
  106         tnode->left = tnode->right = NULL;
  107 
  108         /*
  109          * Finds the first available node for linkage into the combining
  110          * tree. The use of a spinlock is excusable as this is a one-time
  111          * initialization cost.
  112          */
  113         ck_spinlock_fas_lock(&root->mutex);
  114         ck_barrier_combining_queue_enqueue(&queue, root->root);
  115         while (queue.head != NULL) {
  116                 node = ck_barrier_combining_queue_dequeue(&queue);
  117 
  118                 /* If the left child is free, link the group there. */
  119                 if (node->left == NULL) {
  120                         ck_barrier_combining_insert(node, tnode, &node->left);
  121                         goto leave;
  122                 }
  123 
  124                 /* If the right child is free, link the group there. */
  125                 if (node->right == NULL) {
  126                         ck_barrier_combining_insert(node, tnode, &node->right);
  127                         goto leave;
  128                 }
  129 
  130                 /*
  131                  * If unsuccessful, try inserting as a child of the children of the
  132                  * current node.
  133                  */
  134                 ck_barrier_combining_queue_enqueue(&queue, node->left);
  135                 ck_barrier_combining_queue_enqueue(&queue, node->right);
  136         }
  137 
  138 leave:
  139         ck_spinlock_fas_unlock(&root->mutex);
  140         return;
  141 }
  142 
  143 void
  144 ck_barrier_combining_init(struct ck_barrier_combining *root,
  145     struct ck_barrier_combining_group *init_root)
  146 {
  147 
  148         init_root->k = 0;
  149         init_root->count = 0;
  150         init_root->sense = 0;
  151         init_root->parent = init_root->left = init_root->right = NULL;
  152         ck_spinlock_fas_init(&root->mutex);
  153         root->root = init_root;
  154         return;
  155 }
  156 
  157 static void
  158 ck_barrier_combining_aux(struct ck_barrier_combining *barrier,
  159     struct ck_barrier_combining_group *tnode,
  160     unsigned int sense)
  161 {
  162 
  163         /*
  164          * If this is the last thread in the group, it moves on to the parent group.
  165          * Otherwise, it spins on this group's sense.
  166          */
  167         if (ck_pr_faa_uint(&tnode->count, 1) == tnode->k - 1) {
  168                 /*
  169                  * If we are and will be the last thread entering the barrier for the
  170                  * current group then signal the parent group if one exists.
  171                  */
  172                 if (tnode->parent != NULL)
  173                         ck_barrier_combining_aux(barrier, tnode->parent, sense);
  174 
  175                 /*
  176                  * Once the thread returns from its parent(s), it reinitializes the group's
  177                  * arrival count and signals other threads to continue by flipping the group
  178                  * sense. Order of these operations is not important since we assume a static
  179                  * number of threads are members of a barrier for the lifetime of the barrier.
  180                  * Since count is explicitly reinitialized, it is guaranteed that at any point
  181                  * tnode->count is equivalent to tnode->k if and only if that many threads
  182                  * are at the barrier.
  183                  */
  184                 ck_pr_store_uint(&tnode->count, 0);
  185                 ck_pr_fence_store();
  186                 ck_pr_store_uint(&tnode->sense, ~tnode->sense);
  187         } else {
  188                 while (sense != ck_pr_load_uint(&tnode->sense))
  189                         ck_pr_stall();
  190         }
  191         ck_pr_fence_memory();
  192 
  193         return;
  194 }
  195 
  196 void
  197 ck_barrier_combining(struct ck_barrier_combining *barrier,
  198     struct ck_barrier_combining_group *tnode,
  199     struct ck_barrier_combining_state *state)
  200 {
  201 
  202         ck_barrier_combining_aux(barrier, tnode, state->sense);
  203 
  204         /* Reverse the execution context's sense for the next barrier. */
  205         state->sense = ~state->sense;
  206         return;
  207 }

Cache object: f3ba57b8bfe4052d3a0557bb04172247

[ 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/src/ck_barrier_combining.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/src/ck_barrier_combining.c