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_pr.h> 30 31 #include "ck_internal.h" 32 33 /* 34 * This is a tournament barrier implementation. Threads are statically 35 * assigned roles to perform for each round of the barrier. Winners 36 * move on to the next round, while losers spin in their current rounds 37 * on their own flags. During the last round, the champion of the tournament 38 * sets the last flag that begins the wakeup process. 39 */ 40 41 enum { 42 CK_BARRIER_TOURNAMENT_BYE, 43 CK_BARRIER_TOURNAMENT_CHAMPION, 44 CK_BARRIER_TOURNAMENT_DROPOUT, 45 CK_BARRIER_TOURNAMENT_LOSER, 46 CK_BARRIER_TOURNAMENT_WINNER 47 }; 48 49 void 50 ck_barrier_tournament_subscribe(struct ck_barrier_tournament *barrier, 51 struct ck_barrier_tournament_state *state) 52 { 53 54 state->sense = ~0; 55 state->vpid = ck_pr_faa_uint(&barrier->tid, 1); 56 return; 57 } 58 59 void 60 ck_barrier_tournament_init(struct ck_barrier_tournament *barrier, 61 struct ck_barrier_tournament_round **rounds, 62 unsigned int nthr) 63 { 64 unsigned int i, k, size, twok, twokm1, imod2k; 65 66 ck_pr_store_uint(&barrier->tid, 0); 67 barrier->size = size = ck_barrier_tournament_size(nthr); 68 69 for (i = 0; i < nthr; ++i) { 70 /* The first role is always CK_BARRIER_TOURNAMENT_DROPOUT. */ 71 rounds[i][0].flag = 0; 72 rounds[i][0].role = CK_BARRIER_TOURNAMENT_DROPOUT; 73 for (k = 1, twok = 2, twokm1 = 1; k < size; ++k, twokm1 = twok, twok <<= 1) { 74 rounds[i][k].flag = 0; 75 76 imod2k = i & (twok - 1); 77 if (imod2k == 0) { 78 if ((i + twokm1 < nthr) && (twok < nthr)) 79 rounds[i][k].role = CK_BARRIER_TOURNAMENT_WINNER; 80 else if (i + twokm1 >= nthr) 81 rounds[i][k].role = CK_BARRIER_TOURNAMENT_BYE; 82 } 83 84 if (imod2k == twokm1) 85 rounds[i][k].role = CK_BARRIER_TOURNAMENT_LOSER; 86 else if ((i == 0) && (twok >= nthr)) 87 rounds[i][k].role = CK_BARRIER_TOURNAMENT_CHAMPION; 88 89 if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_LOSER) 90 rounds[i][k].opponent = &rounds[i - twokm1][k].flag; 91 else if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_WINNER || 92 rounds[i][k].role == CK_BARRIER_TOURNAMENT_CHAMPION) 93 rounds[i][k].opponent = &rounds[i + twokm1][k].flag; 94 } 95 } 96 97 ck_pr_store_ptr(&barrier->rounds, rounds); 98 return; 99 } 100 101 unsigned int 102 ck_barrier_tournament_size(unsigned int nthr) 103 { 104 105 return (ck_internal_log(ck_internal_power_2(nthr)) + 1); 106 } 107 108 void 109 ck_barrier_tournament(struct ck_barrier_tournament *barrier, 110 struct ck_barrier_tournament_state *state) 111 { 112 struct ck_barrier_tournament_round **rounds = ck_pr_load_ptr(&barrier->rounds); 113 int round = 1; 114 115 if (barrier->size == 1) 116 return; 117 118 for (;; ++round) { 119 switch (rounds[state->vpid][round].role) { 120 case CK_BARRIER_TOURNAMENT_BYE: 121 break; 122 case CK_BARRIER_TOURNAMENT_CHAMPION: 123 /* 124 * The CK_BARRIER_TOURNAMENT_CHAMPION waits until it wins the tournament; it then 125 * sets the final flag before the wakeup phase of the barrier. 126 */ 127 while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense) 128 ck_pr_stall(); 129 130 ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense); 131 goto wakeup; 132 case CK_BARRIER_TOURNAMENT_DROPOUT: 133 /* NOTREACHED */ 134 break; 135 case CK_BARRIER_TOURNAMENT_LOSER: 136 /* 137 * CK_BARRIER_TOURNAMENT_LOSERs set the flags of their opponents and wait until 138 * their opponents release them after the tournament is over. 139 */ 140 ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense); 141 while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense) 142 ck_pr_stall(); 143 144 goto wakeup; 145 case CK_BARRIER_TOURNAMENT_WINNER: 146 /* 147 * CK_BARRIER_TOURNAMENT_WINNERs wait until their current opponent sets their flag; they then 148 * continue to the next round of the tournament. 149 */ 150 while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense) 151 ck_pr_stall(); 152 break; 153 } 154 } 155 156 wakeup: 157 for (round -= 1 ;; --round) { 158 switch (rounds[state->vpid][round].role) { 159 case CK_BARRIER_TOURNAMENT_BYE: 160 break; 161 case CK_BARRIER_TOURNAMENT_CHAMPION: 162 /* NOTREACHED */ 163 break; 164 case CK_BARRIER_TOURNAMENT_DROPOUT: 165 goto leave; 166 break; 167 case CK_BARRIER_TOURNAMENT_LOSER: 168 /* NOTREACHED */ 169 break; 170 case CK_BARRIER_TOURNAMENT_WINNER: 171 /* 172 * Winners inform their old opponents the tournament is over 173 * by setting their flags. 174 */ 175 ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense); 176 break; 177 } 178 } 179 180 leave: 181 ck_pr_fence_memory(); 182 state->sense = ~state->sense; 183 return; 184 } 185