libgomp/work.c

   1 /* Copyright (C) 2005-2022 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_USE_ALIGNED_WORK_SHARES
  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               && __alignof__ (struct gomp_work_share)
 118                  >= __alignof__ (long long))
 119             o &= ~(__alignof__ (long long) - 1);
 120           ordered += o - 1;
 121         }
 122       else
 123         ordered = nthreads * sizeof (*ws->ordered_team_ids);
 124       if (ordered > INLINE_ORDERED_TEAM_IDS_SIZE)
 125         ws->ordered_team_ids = team_malloc (ordered);
 126       else
 127         ws->ordered_team_ids = ws->inline_ordered_team_ids;
 128       memset (ws->ordered_team_ids, '\0', ordered);
 129       ws->ordered_num_used = 0;
 130       ws->ordered_owner = -1;
 131       ws->ordered_cur = 0;
 132     }
 133   else
 134     ws->ordered_team_ids = ws->inline_ordered_team_ids;
 135   gomp_ptrlock_init (&ws->next_ws, NULL);
 136   ws->threads_completed = 0;
 137 }
 138
 139 /* Do any needed destruction of gomp_work_share fields before it
 140    is put back into free gomp_work_share cache or freed.  */
 141
 142 void
 143 gomp_fini_work_share (struct gomp_work_share *ws)
 144 {
 145   gomp_mutex_destroy (&ws->lock);
 146   if (ws->ordered_team_ids != ws->inline_ordered_team_ids)
 147     team_free (ws->ordered_team_ids);
 148   gomp_ptrlock_destroy (&ws->next_ws);
 149 }
 150
 151 /* Free a work share struct, if not orphaned, put it into current
 152    team's free gomp_work_share cache.  */
 153
 154 static inline void
 155 free_work_share (struct gomp_team *team, struct gomp_work_share *ws)
 156 {
 157   gomp_fini_work_share (ws);
 158   if (__builtin_expect (team == NULL, 0))
 159     free (ws);
 160   else
 161     {
 162       struct gomp_work_share *next_ws;
 163 #ifdef HAVE_SYNC_BUILTINS
 164       do
 165         {
 166           next_ws = team->work_share_list_free;
 167           ws->next_free = next_ws;
 168         }
 169       while (!__sync_bool_compare_and_swap (&team->work_share_list_free,
 170                                             next_ws, ws));
 171 #else
 172       gomp_mutex_lock (&team->work_share_list_free_lock);
 173       next_ws = team->work_share_list_free;
 174       ws->next_free = next_ws;
 175       team->work_share_list_free = ws;
 176       gomp_mutex_unlock (&team->work_share_list_free_lock);
 177 #endif
 178     }
 179 }
 180
 181 /* The current thread is ready to begin the next work sharing construct.
 182    In all cases, thr->ts.work_share is updated to point to the new
 183    structure.  In all cases the work_share lock is locked.  Return true
 184    if this was the first thread to reach this point.  */
 185
 186 bool
 187 gomp_work_share_start (size_t ordered)
 188 {
 189   struct gomp_thread *thr = gomp_thread ();
 190   struct gomp_team *team = thr->ts.team;
 191   struct gomp_work_share *ws;
 192
 193   /* Work sharing constructs can be orphaned.  */
 194   if (team == NULL)
 195     {
 196 #ifdef GOMP_USE_ALIGNED_WORK_SHARES
 197       ws = gomp_aligned_alloc (__alignof (struct gomp_work_share),
 198                                sizeof (*ws));
 199 #else
 200       ws = gomp_malloc (sizeof (*ws));
 201 #endif
 202       gomp_init_work_share (ws, ordered, 1);
 203       thr->ts.work_share = ws;
 204       return true;
 205     }
 206
 207   ws = thr->ts.work_share;
 208   thr->ts.last_work_share = ws;
 209   ws = gomp_ptrlock_get (&ws->next_ws);
 210   if (ws == NULL)
 211     {
 212       /* This thread encountered a new ws first.  */
 213       struct gomp_work_share *ws = alloc_work_share (team);
 214       gomp_init_work_share (ws, ordered, team->nthreads);
 215       thr->ts.work_share = ws;
 216       return true;
 217     }
 218   else
 219     {
 220       thr->ts.work_share = ws;
 221       return false;
 222     }
 223 }
 224
 225 /* The current thread is done with its current work sharing construct.
 226    This version does imply a barrier at the end of the work-share.  */
 227
 228 void
 229 gomp_work_share_end (void)
 230 {
 231   struct gomp_thread *thr = gomp_thread ();
 232   struct gomp_team *team = thr->ts.team;
 233   gomp_barrier_state_t bstate;
 234
 235   /* Work sharing constructs can be orphaned.  */
 236   if (team == NULL)
 237     {
 238       free_work_share (NULL, thr->ts.work_share);
 239       thr->ts.work_share = NULL;
 240       return;
 241     }
 242
 243   bstate = gomp_barrier_wait_start (&team->barrier);
 244
 245   if (gomp_barrier_last_thread (bstate))
 246     {
 247       if (__builtin_expect (thr->ts.last_work_share != NULL, 1))
 248         {
 249           team->work_shares_to_free = thr->ts.work_share;
 250           free_work_share (team, thr->ts.last_work_share);
 251         }
 252     }
 253
 254   gomp_team_barrier_wait_end (&team->barrier, bstate);
 255   thr->ts.last_work_share = NULL;
 256 }
 257
 258 /* The current thread is done with its current work sharing construct.
 259    This version implies a cancellable barrier at the end of the work-share.  */
 260
 261 bool
 262 gomp_work_share_end_cancel (void)
 263 {
 264   struct gomp_thread *thr = gomp_thread ();
 265   struct gomp_team *team = thr->ts.team;
 266   gomp_barrier_state_t bstate;
 267
 268   /* Cancellable work sharing constructs cannot be orphaned.  */
 269   bstate = gomp_barrier_wait_cancel_start (&team->barrier);
 270
 271   if (gomp_barrier_last_thread (bstate))
 272     {
 273       if (__builtin_expect (thr->ts.last_work_share != NULL, 1))
 274         {
 275           team->work_shares_to_free = thr->ts.work_share;
 276           free_work_share (team, thr->ts.last_work_share);
 277         }
 278     }
 279   thr->ts.last_work_share = NULL;
 280
 281   return gomp_team_barrier_wait_cancel_end (&team->barrier, bstate);
 282 }
 283
 284 /* The current thread is done with its current work sharing construct.
 285    This version does NOT imply a barrier at the end of the work-share.  */
 286
 287 void
 288 gomp_work_share_end_nowait (void)
 289 {
 290   struct gomp_thread *thr = gomp_thread ();
 291   struct gomp_team *team = thr->ts.team;
 292   struct gomp_work_share *ws = thr->ts.work_share;
 293   unsigned completed;
 294
 295   /* Work sharing constructs can be orphaned.  */
 296   if (team == NULL)
 297     {
 298       free_work_share (NULL, ws);
 299       thr->ts.work_share = NULL;
 300       return;
 301     }
 302
 303   if (__builtin_expect (thr->ts.last_work_share == NULL, 0))
 304     return;
 305
 306 #ifdef HAVE_SYNC_BUILTINS
 307   completed = __sync_add_and_fetch (&ws->threads_completed, 1);
 308 #else
 309   gomp_mutex_lock (&ws->lock);
 310   completed = ++ws->threads_completed;
 311   gomp_mutex_unlock (&ws->lock);
 312 #endif
 313
 314   if (completed == team->nthreads)
 315     {
 316       team->work_shares_to_free = thr->ts.work_share;
 317       free_work_share (team, thr->ts.last_work_share);
 318     }
 319   thr->ts.last_work_share = NULL;
 320 }