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