1309260Scognet/* 2309260Scognet * Copyright 2011-2015 Samy Al Bahra. 3309260Scognet * Copyright 2011 David Joseph. 4309260Scognet * All rights reserved. 5309260Scognet * 6309260Scognet * Redistribution and use in source and binary forms, with or without 7309260Scognet * modification, are permitted provided that the following conditions 8309260Scognet * are met: 9309260Scognet * 1. Redistributions of source code must retain the above copyright 10309260Scognet * notice, this list of conditions and the following disclaimer. 11309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 12309260Scognet * notice, this list of conditions and the following disclaimer in the 13309260Scognet * documentation and/or other materials provided with the distribution. 14309260Scognet * 15309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25309260Scognet * SUCH DAMAGE. 26309260Scognet */ 27309260Scognet 28309260Scognet#include <ck_barrier.h> 29309260Scognet#include <ck_pr.h> 30309260Scognet 31309260Scognet#include "ck_internal.h" 32309260Scognet 33309260Scognet/* 34309260Scognet * This is a tournament barrier implementation. Threads are statically 35309260Scognet * assigned roles to perform for each round of the barrier. Winners 36309260Scognet * move on to the next round, while losers spin in their current rounds 37309260Scognet * on their own flags. During the last round, the champion of the tournament 38309260Scognet * sets the last flag that begins the wakeup process. 39309260Scognet */ 40309260Scognet 41309260Scognetenum { 42309260Scognet CK_BARRIER_TOURNAMENT_BYE, 43309260Scognet CK_BARRIER_TOURNAMENT_CHAMPION, 44309260Scognet CK_BARRIER_TOURNAMENT_DROPOUT, 45309260Scognet CK_BARRIER_TOURNAMENT_LOSER, 46309260Scognet CK_BARRIER_TOURNAMENT_WINNER 47309260Scognet}; 48309260Scognet 49309260Scognetvoid 50309260Scognetck_barrier_tournament_subscribe(struct ck_barrier_tournament *barrier, 51309260Scognet struct ck_barrier_tournament_state *state) 52309260Scognet{ 53309260Scognet 54309260Scognet state->sense = ~0; 55309260Scognet state->vpid = ck_pr_faa_uint(&barrier->tid, 1); 56309260Scognet return; 57309260Scognet} 58309260Scognet 59309260Scognetvoid 60309260Scognetck_barrier_tournament_init(struct ck_barrier_tournament *barrier, 61309260Scognet struct ck_barrier_tournament_round **rounds, 62309260Scognet unsigned int nthr) 63309260Scognet{ 64309260Scognet unsigned int i, k, size, twok, twokm1, imod2k; 65309260Scognet 66309260Scognet ck_pr_store_uint(&barrier->tid, 0); 67309260Scognet barrier->size = size = ck_barrier_tournament_size(nthr); 68309260Scognet 69309260Scognet for (i = 0; i < nthr; ++i) { 70309260Scognet /* The first role is always CK_BARRIER_TOURNAMENT_DROPOUT. */ 71309260Scognet rounds[i][0].flag = 0; 72309260Scognet rounds[i][0].role = CK_BARRIER_TOURNAMENT_DROPOUT; 73309260Scognet for (k = 1, twok = 2, twokm1 = 1; k < size; ++k, twokm1 = twok, twok <<= 1) { 74309260Scognet rounds[i][k].flag = 0; 75309260Scognet 76309260Scognet imod2k = i & (twok - 1); 77309260Scognet if (imod2k == 0) { 78309260Scognet if ((i + twokm1 < nthr) && (twok < nthr)) 79309260Scognet rounds[i][k].role = CK_BARRIER_TOURNAMENT_WINNER; 80309260Scognet else if (i + twokm1 >= nthr) 81309260Scognet rounds[i][k].role = CK_BARRIER_TOURNAMENT_BYE; 82309260Scognet } 83309260Scognet 84309260Scognet if (imod2k == twokm1) 85309260Scognet rounds[i][k].role = CK_BARRIER_TOURNAMENT_LOSER; 86309260Scognet else if ((i == 0) && (twok >= nthr)) 87309260Scognet rounds[i][k].role = CK_BARRIER_TOURNAMENT_CHAMPION; 88309260Scognet 89309260Scognet if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_LOSER) 90309260Scognet rounds[i][k].opponent = &rounds[i - twokm1][k].flag; 91309260Scognet else if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_WINNER || 92309260Scognet rounds[i][k].role == CK_BARRIER_TOURNAMENT_CHAMPION) 93309260Scognet rounds[i][k].opponent = &rounds[i + twokm1][k].flag; 94309260Scognet } 95309260Scognet } 96309260Scognet 97309260Scognet ck_pr_store_ptr(&barrier->rounds, rounds); 98309260Scognet return; 99309260Scognet} 100309260Scognet 101309260Scognetunsigned int 102309260Scognetck_barrier_tournament_size(unsigned int nthr) 103309260Scognet{ 104309260Scognet 105309260Scognet return (ck_internal_log(ck_internal_power_2(nthr)) + 1); 106309260Scognet} 107309260Scognet 108309260Scognetvoid 109309260Scognetck_barrier_tournament(struct ck_barrier_tournament *barrier, 110309260Scognet struct ck_barrier_tournament_state *state) 111309260Scognet{ 112309260Scognet struct ck_barrier_tournament_round **rounds = ck_pr_load_ptr(&barrier->rounds); 113309260Scognet int round = 1; 114309260Scognet 115309260Scognet if (barrier->size == 1) 116309260Scognet return; 117309260Scognet 118309260Scognet for (;; ++round) { 119309260Scognet switch (rounds[state->vpid][round].role) { 120309260Scognet case CK_BARRIER_TOURNAMENT_BYE: 121309260Scognet break; 122309260Scognet case CK_BARRIER_TOURNAMENT_CHAMPION: 123309260Scognet /* 124309260Scognet * The CK_BARRIER_TOURNAMENT_CHAMPION waits until it wins the tournament; it then 125309260Scognet * sets the final flag before the wakeup phase of the barrier. 126309260Scognet */ 127309260Scognet while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense) 128309260Scognet ck_pr_stall(); 129309260Scognet 130309260Scognet ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense); 131309260Scognet goto wakeup; 132309260Scognet case CK_BARRIER_TOURNAMENT_DROPOUT: 133309260Scognet /* NOTREACHED */ 134309260Scognet break; 135309260Scognet case CK_BARRIER_TOURNAMENT_LOSER: 136309260Scognet /* 137309260Scognet * CK_BARRIER_TOURNAMENT_LOSERs set the flags of their opponents and wait until 138309260Scognet * their opponents release them after the tournament is over. 139309260Scognet */ 140309260Scognet ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense); 141309260Scognet while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense) 142309260Scognet ck_pr_stall(); 143309260Scognet 144309260Scognet goto wakeup; 145309260Scognet case CK_BARRIER_TOURNAMENT_WINNER: 146309260Scognet /* 147309260Scognet * CK_BARRIER_TOURNAMENT_WINNERs wait until their current opponent sets their flag; they then 148309260Scognet * continue to the next round of the tournament. 149309260Scognet */ 150309260Scognet while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense) 151309260Scognet ck_pr_stall(); 152309260Scognet break; 153309260Scognet } 154309260Scognet } 155309260Scognet 156309260Scognetwakeup: 157309260Scognet for (round -= 1 ;; --round) { 158309260Scognet switch (rounds[state->vpid][round].role) { 159309260Scognet case CK_BARRIER_TOURNAMENT_BYE: 160309260Scognet break; 161309260Scognet case CK_BARRIER_TOURNAMENT_CHAMPION: 162309260Scognet /* NOTREACHED */ 163309260Scognet break; 164309260Scognet case CK_BARRIER_TOURNAMENT_DROPOUT: 165309260Scognet goto leave; 166309260Scognet break; 167309260Scognet case CK_BARRIER_TOURNAMENT_LOSER: 168309260Scognet /* NOTREACHED */ 169309260Scognet break; 170309260Scognet case CK_BARRIER_TOURNAMENT_WINNER: 171309260Scognet /* 172309260Scognet * Winners inform their old opponents the tournament is over 173309260Scognet * by setting their flags. 174309260Scognet */ 175309260Scognet ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense); 176309260Scognet break; 177309260Scognet } 178309260Scognet } 179309260Scognet 180309260Scognetleave: 181309260Scognet ck_pr_fence_memory(); 182309260Scognet state->sense = ~state->sense; 183309260Scognet return; 184309260Scognet} 185