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_cc.h> 30309260Scognet#include <ck_pr.h> 31309260Scognet#include <ck_stdbool.h> 32309260Scognet 33309260Scognetvoid 34309260Scognetck_barrier_mcs_init(struct ck_barrier_mcs *barrier, unsigned int nthr) 35309260Scognet{ 36309260Scognet unsigned int i, j; 37309260Scognet 38309260Scognet ck_pr_store_uint(&barrier->tid, 0); 39309260Scognet 40309260Scognet for (i = 0; i < nthr; ++i) { 41309260Scognet for (j = 0; j < 4; ++j) { 42309260Scognet /* 43309260Scognet * If there are still threads that don't have parents, 44309260Scognet * add it as a child. 45309260Scognet */ 46309260Scognet barrier[i].havechild[j] = ((i << 2) + j < nthr - 1) ? ~0 : 0; 47309260Scognet 48309260Scognet /* 49309260Scognet * childnotready is initialized to havechild to ensure 50309260Scognet * a thread does not wait for a child that does not exist. 51309260Scognet */ 52309260Scognet barrier[i].childnotready[j] = barrier[i].havechild[j]; 53309260Scognet } 54309260Scognet 55309260Scognet /* The root thread does not have a parent. */ 56309260Scognet barrier[i].parent = (i == 0) ? 57309260Scognet &barrier[i].dummy : 58309260Scognet &barrier[(i - 1) >> 2].childnotready[(i - 1) & 3]; 59309260Scognet 60309260Scognet /* Leaf threads do not have any children. */ 61309260Scognet barrier[i].children[0] = ((i << 1) + 1 >= nthr) ? 62309260Scognet &barrier[i].dummy : 63309260Scognet &barrier[(i << 1) + 1].parentsense; 64309260Scognet 65309260Scognet barrier[i].children[1] = ((i << 1) + 2 >= nthr) ? 66309260Scognet &barrier[i].dummy : 67309260Scognet &barrier[(i << 1) + 2].parentsense; 68309260Scognet 69309260Scognet barrier[i].parentsense = 0; 70309260Scognet } 71309260Scognet 72309260Scognet return; 73309260Scognet} 74309260Scognet 75309260Scognetvoid 76309260Scognetck_barrier_mcs_subscribe(struct ck_barrier_mcs *barrier, struct ck_barrier_mcs_state *state) 77309260Scognet{ 78309260Scognet 79309260Scognet state->sense = ~0; 80309260Scognet state->vpid = ck_pr_faa_uint(&barrier->tid, 1); 81309260Scognet return; 82309260Scognet} 83309260Scognet 84309260ScognetCK_CC_INLINE static bool 85309260Scognetck_barrier_mcs_check_children(unsigned int *childnotready) 86309260Scognet{ 87309260Scognet 88309260Scognet if (ck_pr_load_uint(&childnotready[0]) != 0) 89309260Scognet return false; 90309260Scognet if (ck_pr_load_uint(&childnotready[1]) != 0) 91309260Scognet return false; 92309260Scognet if (ck_pr_load_uint(&childnotready[2]) != 0) 93309260Scognet return false; 94309260Scognet if (ck_pr_load_uint(&childnotready[3]) != 0) 95309260Scognet return false; 96309260Scognet 97309260Scognet return true; 98309260Scognet} 99309260Scognet 100309260ScognetCK_CC_INLINE static void 101309260Scognetck_barrier_mcs_reinitialize_children(struct ck_barrier_mcs *node) 102309260Scognet{ 103309260Scognet 104309260Scognet ck_pr_store_uint(&node->childnotready[0], node->havechild[0]); 105309260Scognet ck_pr_store_uint(&node->childnotready[1], node->havechild[1]); 106309260Scognet ck_pr_store_uint(&node->childnotready[2], node->havechild[2]); 107309260Scognet ck_pr_store_uint(&node->childnotready[3], node->havechild[3]); 108309260Scognet return; 109309260Scognet} 110309260Scognet 111309260Scognetvoid 112309260Scognetck_barrier_mcs(struct ck_barrier_mcs *barrier, 113309260Scognet struct ck_barrier_mcs_state *state) 114309260Scognet{ 115309260Scognet 116309260Scognet /* 117309260Scognet * Wait until all children have reached the barrier and are done waiting 118309260Scognet * for their children. 119309260Scognet */ 120309260Scognet while (ck_barrier_mcs_check_children(barrier[state->vpid].childnotready) == false) 121309260Scognet ck_pr_stall(); 122309260Scognet 123309260Scognet /* Reinitialize for next barrier. */ 124309260Scognet ck_barrier_mcs_reinitialize_children(&barrier[state->vpid]); 125309260Scognet 126309260Scognet /* Inform parent thread and its children have arrived at the barrier. */ 127309260Scognet ck_pr_store_uint(barrier[state->vpid].parent, 0); 128309260Scognet 129309260Scognet /* Wait until parent indicates all threads have arrived at the barrier. */ 130309260Scognet if (state->vpid != 0) { 131309260Scognet while (ck_pr_load_uint(&barrier[state->vpid].parentsense) != state->sense) 132309260Scognet ck_pr_stall(); 133309260Scognet } 134309260Scognet 135309260Scognet /* Inform children of successful barrier. */ 136309260Scognet ck_pr_store_uint(barrier[state->vpid].children[0], state->sense); 137309260Scognet ck_pr_store_uint(barrier[state->vpid].children[1], state->sense); 138309260Scognet state->sense = ~state->sense; 139309260Scognet ck_pr_fence_memory(); 140309260Scognet return; 141309260Scognet} 142