1169695Skan/* Copyright (C) 2005 Free Software Foundation, Inc. 2169695Skan Contributed by Richard Henderson <rth@redhat.com>. 3169695Skan 4169695Skan This file is part of the GNU OpenMP Library (libgomp). 5169695Skan 6169695Skan Libgomp is free software; you can redistribute it and/or modify it 7169695Skan under the terms of the GNU Lesser General Public License as published by 8169695Skan the Free Software Foundation; either version 2.1 of the License, or 9169695Skan (at your option) any later version. 10169695Skan 11169695Skan Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY 12169695Skan WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 13169695Skan FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for 14169695Skan more details. 15169695Skan 16169695Skan You should have received a copy of the GNU Lesser General Public License 17169695Skan along with libgomp; see the file COPYING.LIB. If not, write to the 18169695Skan Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 19169695Skan MA 02110-1301, USA. */ 20169695Skan 21169695Skan/* As a special exception, if you link this library with other files, some 22169695Skan of which are compiled with GCC, to produce an executable, this library 23169695Skan does not by itself cause the resulting executable to be covered by the 24169695Skan GNU General Public License. This exception does not however invalidate 25169695Skan any other reasons why the executable file might be covered by the GNU 26169695Skan General Public License. */ 27169695Skan 28169695Skan/* This file handles the ORDERED construct. */ 29169695Skan 30169695Skan#include "libgomp.h" 31169695Skan 32169695Skan 33169695Skan/* This function is called when first allocating an iteration block. That 34169695Skan is, the thread is not currently on the queue. The work-share lock must 35169695Skan be held on entry. */ 36169695Skan 37169695Skanvoid 38169695Skangomp_ordered_first (void) 39169695Skan{ 40169695Skan struct gomp_thread *thr = gomp_thread (); 41169695Skan struct gomp_team *team = thr->ts.team; 42169695Skan struct gomp_work_share *ws = thr->ts.work_share; 43169695Skan unsigned index; 44169695Skan 45169695Skan /* Work share constructs can be orphaned. */ 46169695Skan if (team == NULL || team->nthreads == 1) 47169695Skan return; 48169695Skan 49169695Skan index = ws->ordered_cur + ws->ordered_num_used; 50169695Skan if (index >= team->nthreads) 51169695Skan index -= team->nthreads; 52169695Skan ws->ordered_team_ids[index] = thr->ts.team_id; 53169695Skan 54169695Skan /* If this is the first and only thread in the queue, then there is 55169695Skan no one to release us when we get to our ordered section. Post to 56169695Skan our own release queue now so that we won't block later. */ 57169695Skan if (ws->ordered_num_used++ == 0) 58169695Skan gomp_sem_post (team->ordered_release[thr->ts.team_id]); 59169695Skan} 60169695Skan 61169695Skan/* This function is called when completing the last iteration block. That 62169695Skan is, there are no more iterations to perform and so the thread should be 63169695Skan removed from the queue entirely. Because of the way ORDERED blocks are 64169695Skan managed, it follows that we currently own access to the ORDERED block, 65169695Skan and should now pass it on to the next thread. The work-share lock must 66169695Skan be held on entry. */ 67169695Skan 68169695Skanvoid 69169695Skangomp_ordered_last (void) 70169695Skan{ 71169695Skan struct gomp_thread *thr = gomp_thread (); 72169695Skan struct gomp_team *team = thr->ts.team; 73169695Skan struct gomp_work_share *ws = thr->ts.work_share; 74169695Skan unsigned next_id; 75169695Skan 76169695Skan /* Work share constructs can be orphaned. */ 77169695Skan if (team == NULL || team->nthreads == 1) 78169695Skan return; 79169695Skan 80169695Skan /* We're no longer the owner. */ 81169695Skan ws->ordered_owner = -1; 82169695Skan 83169695Skan /* If we're not the last thread in the queue, then wake the next. */ 84169695Skan if (--ws->ordered_num_used > 0) 85169695Skan { 86169695Skan unsigned next = ws->ordered_cur + 1; 87169695Skan if (next == team->nthreads) 88169695Skan next = 0; 89169695Skan ws->ordered_cur = next; 90169695Skan 91169695Skan next_id = ws->ordered_team_ids[next]; 92169695Skan gomp_sem_post (team->ordered_release[next_id]); 93169695Skan } 94169695Skan} 95169695Skan 96169695Skan 97169695Skan/* This function is called when allocating a subsequent allocation block. 98169695Skan That is, we're done with the current iteration block and we're allocating 99169695Skan another. This is the logical combination of a call to gomp_ordered_last 100169695Skan followed by a call to gomp_ordered_first. The work-share lock must be 101169695Skan held on entry. */ 102169695Skan 103169695Skanvoid 104169695Skangomp_ordered_next (void) 105169695Skan{ 106169695Skan struct gomp_thread *thr = gomp_thread (); 107169695Skan struct gomp_team *team = thr->ts.team; 108169695Skan struct gomp_work_share *ws = thr->ts.work_share; 109169695Skan unsigned index, next_id; 110169695Skan 111169695Skan /* Work share constructs can be orphaned. */ 112169695Skan if (team == NULL || team->nthreads == 1) 113169695Skan return; 114169695Skan 115169695Skan /* We're no longer the owner. */ 116169695Skan ws->ordered_owner = -1; 117169695Skan 118169695Skan /* If there's only one thread in the queue, that must be us. */ 119169695Skan if (ws->ordered_num_used == 1) 120169695Skan { 121169695Skan /* We have a similar situation as in gomp_ordered_first 122169695Skan where we need to post to our own release semaphore. */ 123169695Skan gomp_sem_post (team->ordered_release[thr->ts.team_id]); 124169695Skan return; 125169695Skan } 126169695Skan 127169695Skan /* If the queue is entirely full, then we move ourself to the end of 128169695Skan the queue merely by incrementing ordered_cur. Only if it's not 129169695Skan full do we have to write our id. */ 130169695Skan if (ws->ordered_num_used < team->nthreads) 131169695Skan { 132169695Skan index = ws->ordered_cur + ws->ordered_num_used; 133169695Skan if (index >= team->nthreads) 134169695Skan index -= team->nthreads; 135169695Skan ws->ordered_team_ids[index] = thr->ts.team_id; 136169695Skan } 137169695Skan 138169695Skan index = ws->ordered_cur + 1; 139169695Skan if (index == team->nthreads) 140169695Skan index = 0; 141169695Skan ws->ordered_cur = index; 142169695Skan 143169695Skan next_id = ws->ordered_team_ids[index]; 144169695Skan gomp_sem_post (team->ordered_release[next_id]); 145169695Skan} 146169695Skan 147169695Skan 148169695Skan/* This function is called when a statically scheduled loop is first 149169695Skan being created. */ 150169695Skan 151169695Skanvoid 152169695Skangomp_ordered_static_init (void) 153169695Skan{ 154169695Skan struct gomp_thread *thr = gomp_thread (); 155169695Skan struct gomp_team *team = thr->ts.team; 156169695Skan 157169695Skan if (team == NULL || team->nthreads == 1) 158169695Skan return; 159169695Skan 160169695Skan gomp_sem_post (team->ordered_release[0]); 161169695Skan} 162169695Skan 163169695Skan/* This function is called when a statically scheduled loop is moving to 164169695Skan the next allocation block. Static schedules are not first come first 165169695Skan served like the others, so we're to move to the numerically next thread, 166169695Skan not the next thread on a list. The work-share lock should *not* be held 167169695Skan on entry. */ 168169695Skan 169169695Skanvoid 170169695Skangomp_ordered_static_next (void) 171169695Skan{ 172169695Skan struct gomp_thread *thr = gomp_thread (); 173169695Skan struct gomp_team *team = thr->ts.team; 174169695Skan struct gomp_work_share *ws = thr->ts.work_share; 175169695Skan unsigned id = thr->ts.team_id; 176169695Skan 177169695Skan if (team == NULL || team->nthreads == 1) 178169695Skan return; 179169695Skan 180169695Skan ws->ordered_owner = -1; 181169695Skan 182169695Skan /* This thread currently owns the lock. Increment the owner. */ 183169695Skan if (++id == team->nthreads) 184169695Skan id = 0; 185169695Skan ws->ordered_team_ids[0] = id; 186169695Skan gomp_sem_post (team->ordered_release[id]); 187169695Skan} 188169695Skan 189169695Skan/* This function is called when we need to assert that the thread owns the 190169695Skan ordered section. Due to the problem of posted-but-not-waited semaphores, 191169695Skan this needs to happen before completing a loop iteration. */ 192169695Skan 193169695Skanvoid 194169695Skangomp_ordered_sync (void) 195169695Skan{ 196169695Skan struct gomp_thread *thr = gomp_thread (); 197169695Skan struct gomp_team *team = thr->ts.team; 198169695Skan struct gomp_work_share *ws = thr->ts.work_share; 199169695Skan 200169695Skan /* Work share constructs can be orphaned. But this clearly means that 201169695Skan we are the only thread, and so we automatically own the section. */ 202169695Skan if (team == NULL || team->nthreads == 1) 203169695Skan return; 204169695Skan 205169695Skan /* ??? I believe it to be safe to access this data without taking the 206169695Skan ws->lock. The only presumed race condition is with the previous 207169695Skan thread on the queue incrementing ordered_cur such that it points 208169695Skan to us, concurrently with our check below. But our team_id is 209169695Skan already present in the queue, and the other thread will always 210169695Skan post to our release semaphore. So the two cases are that we will 211169695Skan either win the race an momentarily block on the semaphore, or lose 212169695Skan the race and find the semaphore already unlocked and so not block. 213169695Skan Either way we get correct results. */ 214169695Skan 215169695Skan if (ws->ordered_owner != thr->ts.team_id) 216169695Skan { 217169695Skan gomp_sem_wait (team->ordered_release[thr->ts.team_id]); 218169695Skan ws->ordered_owner = thr->ts.team_id; 219169695Skan } 220169695Skan} 221169695Skan 222169695Skan/* This function is called by user code when encountering the start of an 223169695Skan ORDERED block. We must check to see if the current thread is at the 224169695Skan head of the queue, and if not, block. */ 225169695Skan 226169695Skan#ifdef HAVE_ATTRIBUTE_ALIAS 227169695Skanextern void GOMP_ordered_start (void) 228169695Skan __attribute__((alias ("gomp_ordered_sync"))); 229169695Skan#else 230169695Skanvoid 231169695SkanGOMP_ordered_start (void) 232169695Skan{ 233169695Skan gomp_ordered_sync (); 234169695Skan} 235169695Skan#endif 236169695Skan 237169695Skan/* This function is called by user code when encountering the end of an 238169695Skan ORDERED block. With the current ORDERED implementation there's nothing 239169695Skan for us to do. 240169695Skan 241169695Skan However, the current implementation has a flaw in that it does not allow 242169695Skan the next thread into the ORDERED section immediately after the current 243169695Skan thread exits the ORDERED section in its last iteration. The existance 244169695Skan of this function allows the implementation to change. */ 245169695Skan 246169695Skanvoid 247169695SkanGOMP_ordered_end (void) 248169695Skan{ 249169695Skan} 250