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 } 142