sys/contrib/ck/src/ck_barrier_mcs.c

   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_stdbool.h>
  32
  33 void
  34 ck_barrier_mcs_init(struct ck_barrier_mcs *barrier, unsigned int nthr)
  35 {
  36         unsigned int i, j;
  37
  38         ck_pr_store_uint(&barrier->tid, 0);
  39
  40         for (i = 0; i < nthr; ++i) {
  41                 for (j = 0; j < 4; ++j) {
  42                         /*
  43                          * If there are still threads that don't have parents,
  44                          * add it as a child.
  45                          */
  46                         barrier[i].havechild[j] = ((i << 2) + j < nthr - 1) ? ~0 : 0;
  47
  48                         /*
  49                          * childnotready is initialized to havechild to ensure
  50                          * a thread does not wait for a child that does not exist.
  51                          */
  52                         barrier[i].childnotready[j] = barrier[i].havechild[j];
  53                 }
  54
  55                 /* The root thread does not have a parent. */
  56                 barrier[i].parent = (i == 0) ?
  57                     &barrier[i].dummy :
  58                     &barrier[(i - 1) >> 2].childnotready[(i - 1) & 3];
  59
  60                 /* Leaf threads do not have any children. */
  61                 barrier[i].children[0] = ((i << 1) + 1 >= nthr) ?
  62                     &barrier[i].dummy :
  63                     &barrier[(i << 1) + 1].parentsense;
  64
  65                 barrier[i].children[1] = ((i << 1) + 2 >= nthr) ?
  66                     &barrier[i].dummy :
  67                     &barrier[(i << 1) + 2].parentsense;
  68
  69                 barrier[i].parentsense = 0;
  70         }
  71
  72         return;
  73 }
  74
  75 void
  76 ck_barrier_mcs_subscribe(struct ck_barrier_mcs *barrier, struct ck_barrier_mcs_state *state)
  77 {
  78
  79         state->sense = ~0;
  80         state->vpid = ck_pr_faa_uint(&barrier->tid, 1);
  81         return;
  82 }
  83
  84 CK_CC_INLINE static bool
  85 ck_barrier_mcs_check_children(unsigned int *childnotready)
  86 {
  87
  88         if (ck_pr_load_uint(&childnotready[0]) != 0)
  89                 return false;
  90         if (ck_pr_load_uint(&childnotready[1]) != 0)
  91                 return false;
  92         if (ck_pr_load_uint(&childnotready[2]) != 0)
  93                 return false;
  94         if (ck_pr_load_uint(&childnotready[3]) != 0)
  95                 return false;
  96
  97         return true;
  98 }
  99
 100 CK_CC_INLINE static void
 101 ck_barrier_mcs_reinitialize_children(struct ck_barrier_mcs *node)
 102 {
 103
 104         ck_pr_store_uint(&node->childnotready[0], node->havechild[0]);
 105         ck_pr_store_uint(&node->childnotready[1], node->havechild[1]);
 106         ck_pr_store_uint(&node->childnotready[2], node->havechild[2]);
 107         ck_pr_store_uint(&node->childnotready[3], node->havechild[3]);
 108         return;
 109 }
 110
 111 void
 112 ck_barrier_mcs(struct ck_barrier_mcs *barrier,
 113     struct ck_barrier_mcs_state *state)
 114 {
 115
 116         /*
 117          * Wait until all children have reached the barrier and are done waiting
 118          * for their children.
 119          */
 120         while (ck_barrier_mcs_check_children(barrier[state->vpid].childnotready) == false)
 121                 ck_pr_stall();
 122
 123         /* Reinitialize for next barrier. */
 124         ck_barrier_mcs_reinitialize_children(&barrier[state->vpid]);
 125
 126         /* Inform parent thread and its children have arrived at the barrier. */
 127         ck_pr_store_uint(barrier[state->vpid].parent, 0);
 128
 129         /* Wait until parent indicates all threads have arrived at the barrier. */
 130         if (state->vpid != 0) {
 131                 while (ck_pr_load_uint(&barrier[state->vpid].parentsense) != state->sense)
 132                         ck_pr_stall();
 133         }
 134
 135         /* Inform children of successful barrier. */
 136         ck_pr_store_uint(barrier[state->vpid].children[0], state->sense);
 137         ck_pr_store_uint(barrier[state->vpid].children[1], state->sense);
 138         state->sense = ~state->sense;
 139         ck_pr_fence_memory();
 140         return;
 141 }