libgomp/work.c

   1 /* Copyright (C) 2005-2019 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 *
  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
 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 = gomp_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
 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     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
 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
 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
 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
 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
 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 }