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
ck_barrier_mcs_init(struct ck_barrier_mcs * barrier,unsigned int nthr)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
ck_barrier_mcs_subscribe(struct ck_barrier_mcs * barrier,struct ck_barrier_mcs_state * state)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
ck_barrier_mcs_check_children(unsigned int * childnotready)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
ck_barrier_mcs_reinitialize_children(struct ck_barrier_mcs * node)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
ck_barrier_mcs(struct ck_barrier_mcs * barrier,struct ck_barrier_mcs_state * state)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