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_spinlock.h> 32 33 struct ck_barrier_combining_queue { 34 struct ck_barrier_combining_group *head; 35 struct ck_barrier_combining_group *tail; 36 }; 37 38 static struct ck_barrier_combining_group * 39 ck_barrier_combining_queue_dequeue(struct ck_barrier_combining_queue *queue) 40 { 41 struct ck_barrier_combining_group *front = NULL; 42 43 if (queue->head != NULL) { 44 front = queue->head; 45 queue->head = queue->head->next; 46 } 47 48 return front; 49 } 50 51 static void 52 ck_barrier_combining_insert(struct ck_barrier_combining_group *parent, 53 struct ck_barrier_combining_group *tnode, 54 struct ck_barrier_combining_group **child) 55 { 56 57 *child = tnode; 58 tnode->parent = parent; 59 60 /* 61 * After inserting, we must increment the parent group's count for 62 * number of threads expected to reach it; otherwise, the 63 * barrier may end prematurely. 64 */ 65 parent->k++; 66 return; 67 } 68 69 /* 70 * This implementation of software combining tree barriers 71 * uses level order traversal to insert new thread groups 72 * into the barrier's tree. We use a queue to implement this 73 * traversal. 74 */ 75 static void 76 ck_barrier_combining_queue_enqueue(struct ck_barrier_combining_queue *queue, 77 struct ck_barrier_combining_group *node_value) 78 { 79 80 node_value->next = NULL; 81 if (queue->head == NULL) { 82 queue->head = queue->tail = node_value; 83 return; 84 } 85 86 queue->tail->next = node_value; 87 queue->tail = node_value; 88 89 return; 90 } 91 92 93 void 94 ck_barrier_combining_group_init(struct ck_barrier_combining *root, 95 struct ck_barrier_combining_group *tnode, 96 unsigned int nthr) 97 { 98 struct ck_barrier_combining_group *node; 99 struct ck_barrier_combining_queue queue; 100 101 queue.head = queue.tail = NULL; 102 103 tnode->k = nthr; 104 tnode->count = 0; 105 tnode->sense = 0; 106 tnode->left = tnode->right = NULL; 107 108 /* 109 * Finds the first available node for linkage into the combining 110 * tree. The use of a spinlock is excusable as this is a one-time 111 * initialization cost. 112 */ 113 ck_spinlock_fas_lock(&root->mutex); 114 ck_barrier_combining_queue_enqueue(&queue, root->root); 115 while (queue.head != NULL) { 116 node = ck_barrier_combining_queue_dequeue(&queue); 117 118 /* If the left child is free, link the group there. */ 119 if (node->left == NULL) { 120 ck_barrier_combining_insert(node, tnode, &node->left); 121 goto leave; 122 } 123 124 /* If the right child is free, link the group there. */ 125 if (node->right == NULL) { 126 ck_barrier_combining_insert(node, tnode, &node->right); 127 goto leave; 128 } 129 130 /* 131 * If unsuccessful, try inserting as a child of the children of the 132 * current node. 133 */ 134 ck_barrier_combining_queue_enqueue(&queue, node->left); 135 ck_barrier_combining_queue_enqueue(&queue, node->right); 136 } 137 138 leave: 139 ck_spinlock_fas_unlock(&root->mutex); 140 return; 141 } 142 143 void 144 ck_barrier_combining_init(struct ck_barrier_combining *root, 145 struct ck_barrier_combining_group *init_root) 146 { 147 148 init_root->k = 0; 149 init_root->count = 0; 150 init_root->sense = 0; 151 init_root->parent = init_root->left = init_root->right = NULL; 152 ck_spinlock_fas_init(&root->mutex); 153 root->root = init_root; 154 return; 155 } 156 157 static void 158 ck_barrier_combining_aux(struct ck_barrier_combining *barrier, 159 struct ck_barrier_combining_group *tnode, 160 unsigned int sense) 161 { 162 163 /* 164 * If this is the last thread in the group, it moves on to the parent group. 165 * Otherwise, it spins on this group's sense. 166 */ 167 if (ck_pr_faa_uint(&tnode->count, 1) == tnode->k - 1) { 168 /* 169 * If we are and will be the last thread entering the barrier for the 170 * current group then signal the parent group if one exists. 171 */ 172 if (tnode->parent != NULL) 173 ck_barrier_combining_aux(barrier, tnode->parent, sense); 174 175 /* 176 * Once the thread returns from its parent(s), it reinitializes the group's 177 * arrival count and signals other threads to continue by flipping the group 178 * sense. Order of these operations is not important since we assume a static 179 * number of threads are members of a barrier for the lifetime of the barrier. 180 * Since count is explicitly reinitialized, it is guaranteed that at any point 181 * tnode->count is equivalent to tnode->k if and only if that many threads 182 * are at the barrier. 183 */ 184 ck_pr_store_uint(&tnode->count, 0); 185 ck_pr_fence_store(); 186 ck_pr_store_uint(&tnode->sense, ~tnode->sense); 187 } else { 188 while (sense != ck_pr_load_uint(&tnode->sense)) 189 ck_pr_stall(); 190 } 191 ck_pr_fence_memory(); 192 193 return; 194 } 195 196 void 197 ck_barrier_combining(struct ck_barrier_combining *barrier, 198 struct ck_barrier_combining_group *tnode, 199 struct ck_barrier_combining_state *state) 200 { 201 202 ck_barrier_combining_aux(barrier, tnode, state->sense); 203 204 /* Reverse the execution context's sense for the next barrier. */ 205 state->sense = ~state->sense; 206 return; 207 } 208