1 /* Copyright (C) 2005-2020 Free Software Foundation, Inc.
2 Contributed by Richard Henderson <rth@redhat.com>.
3
4 This file is part of the GNU Offloading and Multi Processing Library
5 (libgomp).
6
7 Libgomp is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 more details.
16
17 Under Section 7 of GPL version 3, you are granted additional
18 permissions described in the GCC Runtime Library Exception, version
19 3.1, as published by the Free Software Foundation.
20
21 You should have received a copy of the GNU General Public License and
22 a copy of the GCC Runtime Library Exception along with this program;
23 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 <http://www.gnu.org/licenses/>. */
25
26 /* This file contains routines to manage the work-share queue for a team
27 of threads. */
28
29 #include "libgomp.h"
30 #include <stddef.h>
31 #include <stdlib.h>
32 #include <string.h>
33
34
35 /* Allocate a new work share structure, preferably from current team's
36 free gomp_work_share cache. */
37
38 static struct gomp_work_share *
alloc_work_share(struct gomp_team * team)39 alloc_work_share (struct gomp_team *team)
40 {
41 struct gomp_work_share *ws;
42 unsigned int i;
43
44 /* This is called in a critical section. */
45 if (team->work_share_list_alloc != NULL)
46 {
47 ws = team->work_share_list_alloc;
48 team->work_share_list_alloc = ws->next_free;
49 return ws;
50 }
51
52 #ifdef HAVE_SYNC_BUILTINS
53 ws = team->work_share_list_free;
54 /* We need atomic read from work_share_list_free,
55 as free_work_share can be called concurrently. */
56 __asm ("" : "+r" (ws));
57
58 if (ws && ws->next_free)
59 {
60 struct gomp_work_share *next = ws->next_free;
61 ws->next_free = NULL;
62 team->work_share_list_alloc = next->next_free;
63 return next;
64 }
65 #else
66 gomp_mutex_lock (&team->work_share_list_free_lock);
67 ws = team->work_share_list_free;
68 if (ws)
69 {
70 team->work_share_list_alloc = ws->next_free;
71 team->work_share_list_free = NULL;
72 gomp_mutex_unlock (&team->work_share_list_free_lock);
73 return ws;
74 }
75 gomp_mutex_unlock (&team->work_share_list_free_lock);
76 #endif
77
78 team->work_share_chunk *= 2;
79 /* Allocating gomp_work_share structures aligned is just an
80 optimization, don't do it when using the fallback method. */
81 #ifdef GOMP_HAVE_EFFICIENT_ALIGNED_ALLOC
82 ws = gomp_aligned_alloc (__alignof (struct gomp_work_share),
83 team->work_share_chunk
84 * sizeof (struct gomp_work_share));
85 #else
86 ws = gomp_malloc (team->work_share_chunk * sizeof (struct gomp_work_share));
87 #endif
88 ws->next_alloc = team->work_shares[0].next_alloc;
89 team->work_shares[0].next_alloc = ws;
90 team->work_share_list_alloc = &ws[1];
91 for (i = 1; i < team->work_share_chunk - 1; i++)
92 ws[i].next_free = &ws[i + 1];
93 ws[i].next_free = NULL;
94 return ws;
95 }
96
97 /* Initialize an already allocated struct gomp_work_share.
98 This shouldn't touch the next_alloc field. */
99
100 void
gomp_init_work_share(struct gomp_work_share * ws,size_t ordered,unsigned nthreads)101 gomp_init_work_share (struct gomp_work_share *ws, size_t ordered,
102 unsigned nthreads)
103 {
104 gomp_mutex_init (&ws->lock);
105 if (__builtin_expect (ordered, 0))
106 {
107 #define INLINE_ORDERED_TEAM_IDS_SIZE \
108 (sizeof (struct gomp_work_share) \
109 - offsetof (struct gomp_work_share, inline_ordered_team_ids))
110
111 if (__builtin_expect (ordered != 1, 0))
112 {
113 size_t o = nthreads * sizeof (*ws->ordered_team_ids);
114 o += __alignof__ (long long) - 1;
115 if ((offsetof (struct gomp_work_share, inline_ordered_team_ids)
116 & (__alignof__ (long long) - 1)) == 0)
117 o &= ~(__alignof__ (long long) - 1);
118 ordered += o - 1;
119 }
120 else
121 ordered = nthreads * sizeof (*ws->ordered_team_ids);
122 if (ordered > INLINE_ORDERED_TEAM_IDS_SIZE)
123 ws->ordered_team_ids = team_malloc (ordered);
124 else
125 ws->ordered_team_ids = ws->inline_ordered_team_ids;
126 memset (ws->ordered_team_ids, '\0', ordered);
127 ws->ordered_num_used = 0;
128 ws->ordered_owner = -1;
129 ws->ordered_cur = 0;
130 }
131 else
132 ws->ordered_team_ids = ws->inline_ordered_team_ids;
133 gomp_ptrlock_init (&ws->next_ws, NULL);
134 ws->threads_completed = 0;
135 }
136
137 /* Do any needed destruction of gomp_work_share fields before it
138 is put back into free gomp_work_share cache or freed. */
139
140 void
gomp_fini_work_share(struct gomp_work_share * ws)141 gomp_fini_work_share (struct gomp_work_share *ws)
142 {
143 gomp_mutex_destroy (&ws->lock);
144 if (ws->ordered_team_ids != ws->inline_ordered_team_ids)
145 team_free (ws->ordered_team_ids);
146 gomp_ptrlock_destroy (&ws->next_ws);
147 }
148
149 /* Free a work share struct, if not orphaned, put it into current
150 team's free gomp_work_share cache. */
151
152 static inline void
free_work_share(struct gomp_team * team,struct gomp_work_share * ws)153 free_work_share (struct gomp_team *team, struct gomp_work_share *ws)
154 {
155 gomp_fini_work_share (ws);
156 if (__builtin_expect (team == NULL, 0))
157 free (ws);
158 else
159 {
160 struct gomp_work_share *next_ws;
161 #ifdef HAVE_SYNC_BUILTINS
162 do
163 {
164 next_ws = team->work_share_list_free;
165 ws->next_free = next_ws;
166 }
167 while (!__sync_bool_compare_and_swap (&team->work_share_list_free,
168 next_ws, ws));
169 #else
170 gomp_mutex_lock (&team->work_share_list_free_lock);
171 next_ws = team->work_share_list_free;
172 ws->next_free = next_ws;
173 team->work_share_list_free = ws;
174 gomp_mutex_unlock (&team->work_share_list_free_lock);
175 #endif
176 }
177 }
178
179 /* The current thread is ready to begin the next work sharing construct.
180 In all cases, thr->ts.work_share is updated to point to the new
181 structure. In all cases the work_share lock is locked. Return true
182 if this was the first thread to reach this point. */
183
184 bool
gomp_work_share_start(size_t ordered)185 gomp_work_share_start (size_t ordered)
186 {
187 struct gomp_thread *thr = gomp_thread ();
188 struct gomp_team *team = thr->ts.team;
189 struct gomp_work_share *ws;
190
191 /* Work sharing constructs can be orphaned. */
192 if (team == NULL)
193 {
194 ws = gomp_malloc (sizeof (*ws));
195 gomp_init_work_share (ws, ordered, 1);
196 thr->ts.work_share = ws;
197 return true;
198 }
199
200 ws = thr->ts.work_share;
201 thr->ts.last_work_share = ws;
202 ws = gomp_ptrlock_get (&ws->next_ws);
203 if (ws == NULL)
204 {
205 /* This thread encountered a new ws first. */
206 struct gomp_work_share *ws = alloc_work_share (team);
207 gomp_init_work_share (ws, ordered, team->nthreads);
208 thr->ts.work_share = ws;
209 return true;
210 }
211 else
212 {
213 thr->ts.work_share = ws;
214 return false;
215 }
216 }
217
218 /* The current thread is done with its current work sharing construct.
219 This version does imply a barrier at the end of the work-share. */
220
221 void
gomp_work_share_end(void)222 gomp_work_share_end (void)
223 {
224 struct gomp_thread *thr = gomp_thread ();
225 struct gomp_team *team = thr->ts.team;
226 gomp_barrier_state_t bstate;
227
228 /* Work sharing constructs can be orphaned. */
229 if (team == NULL)
230 {
231 free_work_share (NULL, thr->ts.work_share);
232 thr->ts.work_share = NULL;
233 return;
234 }
235
236 bstate = gomp_barrier_wait_start (&team->barrier);
237
238 if (gomp_barrier_last_thread (bstate))
239 {
240 if (__builtin_expect (thr->ts.last_work_share != NULL, 1))
241 {
242 team->work_shares_to_free = thr->ts.work_share;
243 free_work_share (team, thr->ts.last_work_share);
244 }
245 }
246
247 gomp_team_barrier_wait_end (&team->barrier, bstate);
248 thr->ts.last_work_share = NULL;
249 }
250
251 /* The current thread is done with its current work sharing construct.
252 This version implies a cancellable barrier at the end of the work-share. */
253
254 bool
gomp_work_share_end_cancel(void)255 gomp_work_share_end_cancel (void)
256 {
257 struct gomp_thread *thr = gomp_thread ();
258 struct gomp_team *team = thr->ts.team;
259 gomp_barrier_state_t bstate;
260
261 /* Cancellable work sharing constructs cannot be orphaned. */
262 bstate = gomp_barrier_wait_cancel_start (&team->barrier);
263
264 if (gomp_barrier_last_thread (bstate))
265 {
266 if (__builtin_expect (thr->ts.last_work_share != NULL, 1))
267 {
268 team->work_shares_to_free = thr->ts.work_share;
269 free_work_share (team, thr->ts.last_work_share);
270 }
271 }
272 thr->ts.last_work_share = NULL;
273
274 return gomp_team_barrier_wait_cancel_end (&team->barrier, bstate);
275 }
276
277 /* The current thread is done with its current work sharing construct.
278 This version does NOT imply a barrier at the end of the work-share. */
279
280 void
gomp_work_share_end_nowait(void)281 gomp_work_share_end_nowait (void)
282 {
283 struct gomp_thread *thr = gomp_thread ();
284 struct gomp_team *team = thr->ts.team;
285 struct gomp_work_share *ws = thr->ts.work_share;
286 unsigned completed;
287
288 /* Work sharing constructs can be orphaned. */
289 if (team == NULL)
290 {
291 free_work_share (NULL, ws);
292 thr->ts.work_share = NULL;
293 return;
294 }
295
296 if (__builtin_expect (thr->ts.last_work_share == NULL, 0))
297 return;
298
299 #ifdef HAVE_SYNC_BUILTINS
300 completed = __sync_add_and_fetch (&ws->threads_completed, 1);
301 #else
302 gomp_mutex_lock (&ws->lock);
303 completed = ++ws->threads_completed;
304 gomp_mutex_unlock (&ws->lock);
305 #endif
306
307 if (completed == team->nthreads)
308 {
309 team->work_shares_to_free = thr->ts.work_share;
310 free_work_share (team, thr->ts.last_work_share);
311 }
312 thr->ts.last_work_share = NULL;
313 }
314