1/* Copyright (C) 2005-2015 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 38static struct gomp_work_share * 39alloc_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 ws = gomp_malloc (team->work_share_chunk * sizeof (struct gomp_work_share)); 80 ws->next_alloc = team->work_shares[0].next_alloc; 81 team->work_shares[0].next_alloc = ws; 82 team->work_share_list_alloc = &ws[1]; 83 for (i = 1; i < team->work_share_chunk - 1; i++) 84 ws[i].next_free = &ws[i + 1]; 85 ws[i].next_free = NULL; 86 return ws; 87} 88 89/* Initialize an already allocated struct gomp_work_share. 90 This shouldn't touch the next_alloc field. */ 91 92void 93gomp_init_work_share (struct gomp_work_share *ws, bool ordered, 94 unsigned nthreads) 95{ 96 gomp_mutex_init (&ws->lock); 97 if (__builtin_expect (ordered, 0)) 98 { 99#define INLINE_ORDERED_TEAM_IDS_CNT \ 100 ((sizeof (struct gomp_work_share) \ 101 - offsetof (struct gomp_work_share, inline_ordered_team_ids)) \ 102 / sizeof (((struct gomp_work_share *) 0)->inline_ordered_team_ids[0])) 103 104 if (nthreads > INLINE_ORDERED_TEAM_IDS_CNT) 105 ws->ordered_team_ids 106 = gomp_malloc (nthreads * sizeof (*ws->ordered_team_ids)); 107 else 108 ws->ordered_team_ids = ws->inline_ordered_team_ids; 109 memset (ws->ordered_team_ids, '\0', 110 nthreads * sizeof (*ws->ordered_team_ids)); 111 ws->ordered_num_used = 0; 112 ws->ordered_owner = -1; 113 ws->ordered_cur = 0; 114 } 115 else 116 ws->ordered_team_ids = NULL; 117 gomp_ptrlock_init (&ws->next_ws, NULL); 118 ws->threads_completed = 0; 119} 120 121/* Do any needed destruction of gomp_work_share fields before it 122 is put back into free gomp_work_share cache or freed. */ 123 124void 125gomp_fini_work_share (struct gomp_work_share *ws) 126{ 127 gomp_mutex_destroy (&ws->lock); 128 if (ws->ordered_team_ids != ws->inline_ordered_team_ids) 129 free (ws->ordered_team_ids); 130 gomp_ptrlock_destroy (&ws->next_ws); 131} 132 133/* Free a work share struct, if not orphaned, put it into current 134 team's free gomp_work_share cache. */ 135 136static inline void 137free_work_share (struct gomp_team *team, struct gomp_work_share *ws) 138{ 139 gomp_fini_work_share (ws); 140 if (__builtin_expect (team == NULL, 0)) 141 free (ws); 142 else 143 { 144 struct gomp_work_share *next_ws; 145#ifdef HAVE_SYNC_BUILTINS 146 do 147 { 148 next_ws = team->work_share_list_free; 149 ws->next_free = next_ws; 150 } 151 while (!__sync_bool_compare_and_swap (&team->work_share_list_free, 152 next_ws, ws)); 153#else 154 gomp_mutex_lock (&team->work_share_list_free_lock); 155 next_ws = team->work_share_list_free; 156 ws->next_free = next_ws; 157 team->work_share_list_free = ws; 158 gomp_mutex_unlock (&team->work_share_list_free_lock); 159#endif 160 } 161} 162 163/* The current thread is ready to begin the next work sharing construct. 164 In all cases, thr->ts.work_share is updated to point to the new 165 structure. In all cases the work_share lock is locked. Return true 166 if this was the first thread to reach this point. */ 167 168bool 169gomp_work_share_start (bool ordered) 170{ 171 struct gomp_thread *thr = gomp_thread (); 172 struct gomp_team *team = thr->ts.team; 173 struct gomp_work_share *ws; 174 175 /* Work sharing constructs can be orphaned. */ 176 if (team == NULL) 177 { 178 ws = gomp_malloc (sizeof (*ws)); 179 gomp_init_work_share (ws, ordered, 1); 180 thr->ts.work_share = ws; 181 return ws; 182 } 183 184 ws = thr->ts.work_share; 185 thr->ts.last_work_share = ws; 186 ws = gomp_ptrlock_get (&ws->next_ws); 187 if (ws == NULL) 188 { 189 /* This thread encountered a new ws first. */ 190 struct gomp_work_share *ws = alloc_work_share (team); 191 gomp_init_work_share (ws, ordered, team->nthreads); 192 thr->ts.work_share = ws; 193 return true; 194 } 195 else 196 { 197 thr->ts.work_share = ws; 198 return false; 199 } 200} 201 202/* The current thread is done with its current work sharing construct. 203 This version does imply a barrier at the end of the work-share. */ 204 205void 206gomp_work_share_end (void) 207{ 208 struct gomp_thread *thr = gomp_thread (); 209 struct gomp_team *team = thr->ts.team; 210 gomp_barrier_state_t bstate; 211 212 /* Work sharing constructs can be orphaned. */ 213 if (team == NULL) 214 { 215 free_work_share (NULL, thr->ts.work_share); 216 thr->ts.work_share = NULL; 217 return; 218 } 219 220 bstate = gomp_barrier_wait_start (&team->barrier); 221 222 if (gomp_barrier_last_thread (bstate)) 223 { 224 if (__builtin_expect (thr->ts.last_work_share != NULL, 1)) 225 { 226 team->work_shares_to_free = thr->ts.work_share; 227 free_work_share (team, thr->ts.last_work_share); 228 } 229 } 230 231 gomp_team_barrier_wait_end (&team->barrier, bstate); 232 thr->ts.last_work_share = NULL; 233} 234 235/* The current thread is done with its current work sharing construct. 236 This version implies a cancellable barrier at the end of the work-share. */ 237 238bool 239gomp_work_share_end_cancel (void) 240{ 241 struct gomp_thread *thr = gomp_thread (); 242 struct gomp_team *team = thr->ts.team; 243 gomp_barrier_state_t bstate; 244 245 /* Cancellable work sharing constructs cannot be orphaned. */ 246 bstate = gomp_barrier_wait_cancel_start (&team->barrier); 247 248 if (gomp_barrier_last_thread (bstate)) 249 { 250 if (__builtin_expect (thr->ts.last_work_share != NULL, 1)) 251 { 252 team->work_shares_to_free = thr->ts.work_share; 253 free_work_share (team, thr->ts.last_work_share); 254 } 255 } 256 thr->ts.last_work_share = NULL; 257 258 return gomp_team_barrier_wait_cancel_end (&team->barrier, bstate); 259} 260 261/* The current thread is done with its current work sharing construct. 262 This version does NOT imply a barrier at the end of the work-share. */ 263 264void 265gomp_work_share_end_nowait (void) 266{ 267 struct gomp_thread *thr = gomp_thread (); 268 struct gomp_team *team = thr->ts.team; 269 struct gomp_work_share *ws = thr->ts.work_share; 270 unsigned completed; 271 272 /* Work sharing constructs can be orphaned. */ 273 if (team == NULL) 274 { 275 free_work_share (NULL, ws); 276 thr->ts.work_share = NULL; 277 return; 278 } 279 280 if (__builtin_expect (thr->ts.last_work_share == NULL, 0)) 281 return; 282 283#ifdef HAVE_SYNC_BUILTINS 284 completed = __sync_add_and_fetch (&ws->threads_completed, 1); 285#else 286 gomp_mutex_lock (&ws->lock); 287 completed = ++ws->threads_completed; 288 gomp_mutex_unlock (&ws->lock); 289#endif 290 291 if (completed == team->nthreads) 292 { 293 team->work_shares_to_free = thr->ts.work_share; 294 free_work_share (team, thr->ts.last_work_share); 295 } 296 thr->ts.last_work_share = NULL; 297} 298