LLVM OpenMP* Runtime Library
kmp_lock.cpp
1/*
2 * kmp_lock.cpp -- lock-related functions
3 */
4
5//===----------------------------------------------------------------------===//
6//
7// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
8// See https://llvm.org/LICENSE.txt for license information.
9// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
10//
11//===----------------------------------------------------------------------===//
12
13#include <stddef.h>
14#include <atomic>
15
16#include "kmp.h"
17#include "kmp_i18n.h"
18#include "kmp_io.h"
19#include "kmp_itt.h"
20#include "kmp_lock.h"
21#include "kmp_wait_release.h"
22#include "kmp_wrapper_getpid.h"
23
24#if KMP_USE_FUTEX
25#include <sys/syscall.h>
26#include <unistd.h>
27// We should really include <futex.h>, but that causes compatibility problems on
28// different Linux* OS distributions that either require that you include (or
29// break when you try to include) <pci/types.h>. Since all we need is the two
30// macros below (which are part of the kernel ABI, so can't change) we just
31// define the constants here and don't include <futex.h>
32#ifndef FUTEX_WAIT
33#define FUTEX_WAIT 0
34#endif
35#ifndef FUTEX_WAKE
36#define FUTEX_WAKE 1
37#endif
38#endif
39
40/* Implement spin locks for internal library use. */
41/* The algorithm implemented is Lamport's bakery lock [1974]. */
42
43void __kmp_validate_locks(void) {
44 int i;
45 kmp_uint32 x, y;
46
47 /* Check to make sure unsigned arithmetic does wraps properly */
48 x = ~((kmp_uint32)0) - 2;
49 y = x - 2;
50
51 for (i = 0; i < 8; ++i, ++x, ++y) {
52 kmp_uint32 z = (x - y);
53 KMP_ASSERT(z == 2);
54 }
55
56 KMP_ASSERT(offsetof(kmp_base_queuing_lock, tail_id) % 8 == 0);
57}
58
59/* ------------------------------------------------------------------------ */
60/* test and set locks */
61
62// For the non-nested locks, we can only assume that the first 4 bytes were
63// allocated, since gcc only allocates 4 bytes for omp_lock_t, and the Intel
64// compiler only allocates a 4 byte pointer on IA-32 architecture. On
65// Windows* OS on Intel(R) 64, we can assume that all 8 bytes were allocated.
66//
67// gcc reserves >= 8 bytes for nested locks, so we can assume that the
68// entire 8 bytes were allocated for nested locks on all 64-bit platforms.
69
70static kmp_int32 __kmp_get_tas_lock_owner(kmp_tas_lock_t *lck) {
71 return KMP_LOCK_STRIP(KMP_ATOMIC_LD_RLX(&lck->lk.poll)) - 1;
72}
73
74static inline bool __kmp_is_tas_lock_nestable(kmp_tas_lock_t *lck) {
75 return lck->lk.depth_locked != -1;
76}
77
78__forceinline static int
79__kmp_acquire_tas_lock_timed_template(kmp_tas_lock_t *lck, kmp_int32 gtid) {
80 KMP_MB();
81
82#ifdef USE_LOCK_PROFILE
83 kmp_uint32 curr = KMP_LOCK_STRIP(lck->lk.poll);
84 if ((curr != 0) && (curr != gtid + 1))
85 __kmp_printf("LOCK CONTENTION: %p\n", lck);
86/* else __kmp_printf( "." );*/
87#endif /* USE_LOCK_PROFILE */
88
89 kmp_int32 tas_free = KMP_LOCK_FREE(tas);
90 kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas);
91
92 if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free &&
93 __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) {
94 KMP_FSYNC_ACQUIRED(lck);
95 return KMP_LOCK_ACQUIRED_FIRST;
96 }
97
98 kmp_uint32 spins;
99 kmp_uint64 time;
100 KMP_FSYNC_PREPARE(lck);
101 KMP_INIT_YIELD(spins);
102 KMP_INIT_BACKOFF(time);
103 kmp_backoff_t backoff = __kmp_spin_backoff_params;
104 do {
105#if !KMP_HAVE_UMWAIT
106 __kmp_spin_backoff(&backoff);
107#else
108 if (!__kmp_tpause_enabled)
109 __kmp_spin_backoff(&backoff);
110#endif
111 KMP_YIELD_OVERSUB_ELSE_SPIN(spins, time);
112 } while (KMP_ATOMIC_LD_RLX(&lck->lk.poll) != tas_free ||
113 !__kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy));
114 KMP_FSYNC_ACQUIRED(lck);
115 return KMP_LOCK_ACQUIRED_FIRST;
116}
117
118int __kmp_acquire_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
119 int retval = __kmp_acquire_tas_lock_timed_template(lck, gtid);
120 return retval;
121}
122
123static int __kmp_acquire_tas_lock_with_checks(kmp_tas_lock_t *lck,
124 kmp_int32 gtid) {
125 char const *const func = "omp_set_lock";
126 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
127 __kmp_is_tas_lock_nestable(lck)) {
128 KMP_FATAL(LockNestableUsedAsSimple, func);
129 }
130 if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) == gtid)) {
131 KMP_FATAL(LockIsAlreadyOwned, func);
132 }
133 return __kmp_acquire_tas_lock(lck, gtid);
134}
135
136int __kmp_test_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
137 kmp_int32 tas_free = KMP_LOCK_FREE(tas);
138 kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas);
139 if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free &&
140 __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) {
141 KMP_FSYNC_ACQUIRED(lck);
142 return TRUE;
143 }
144 return FALSE;
145}
146
147static int __kmp_test_tas_lock_with_checks(kmp_tas_lock_t *lck,
148 kmp_int32 gtid) {
149 char const *const func = "omp_test_lock";
150 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
151 __kmp_is_tas_lock_nestable(lck)) {
152 KMP_FATAL(LockNestableUsedAsSimple, func);
153 }
154 return __kmp_test_tas_lock(lck, gtid);
155}
156
157int __kmp_release_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
158 KMP_MB(); /* Flush all pending memory write invalidates. */
159
160 KMP_FSYNC_RELEASING(lck);
161 KMP_ATOMIC_ST_REL(&lck->lk.poll, KMP_LOCK_FREE(tas));
162 KMP_MB(); /* Flush all pending memory write invalidates. */
163
164 KMP_YIELD_OVERSUB();
165 return KMP_LOCK_RELEASED;
166}
167
168static int __kmp_release_tas_lock_with_checks(kmp_tas_lock_t *lck,
169 kmp_int32 gtid) {
170 char const *const func = "omp_unset_lock";
171 KMP_MB(); /* in case another processor initialized lock */
172 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
173 __kmp_is_tas_lock_nestable(lck)) {
174 KMP_FATAL(LockNestableUsedAsSimple, func);
175 }
176 if (__kmp_get_tas_lock_owner(lck) == -1) {
177 KMP_FATAL(LockUnsettingFree, func);
178 }
179 if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) >= 0) &&
180 (__kmp_get_tas_lock_owner(lck) != gtid)) {
181 KMP_FATAL(LockUnsettingSetByAnother, func);
182 }
183 return __kmp_release_tas_lock(lck, gtid);
184}
185
186void __kmp_init_tas_lock(kmp_tas_lock_t *lck) {
187 lck->lk.poll = KMP_LOCK_FREE(tas);
188}
189
190void __kmp_destroy_tas_lock(kmp_tas_lock_t *lck) { lck->lk.poll = 0; }
191
192static void __kmp_destroy_tas_lock_with_checks(kmp_tas_lock_t *lck) {
193 char const *const func = "omp_destroy_lock";
194 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
195 __kmp_is_tas_lock_nestable(lck)) {
196 KMP_FATAL(LockNestableUsedAsSimple, func);
197 }
198 if (__kmp_get_tas_lock_owner(lck) != -1) {
199 KMP_FATAL(LockStillOwned, func);
200 }
201 __kmp_destroy_tas_lock(lck);
202}
203
204// nested test and set locks
205
206int __kmp_acquire_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
207 KMP_DEBUG_ASSERT(gtid >= 0);
208
209 if (__kmp_get_tas_lock_owner(lck) == gtid) {
210 lck->lk.depth_locked += 1;
211 return KMP_LOCK_ACQUIRED_NEXT;
212 } else {
213 __kmp_acquire_tas_lock_timed_template(lck, gtid);
214 lck->lk.depth_locked = 1;
215 return KMP_LOCK_ACQUIRED_FIRST;
216 }
217}
218
219static int __kmp_acquire_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
220 kmp_int32 gtid) {
221 char const *const func = "omp_set_nest_lock";
222 if (!__kmp_is_tas_lock_nestable(lck)) {
223 KMP_FATAL(LockSimpleUsedAsNestable, func);
224 }
225 return __kmp_acquire_nested_tas_lock(lck, gtid);
226}
227
228int __kmp_test_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
229 int retval;
230
231 KMP_DEBUG_ASSERT(gtid >= 0);
232
233 if (__kmp_get_tas_lock_owner(lck) == gtid) {
234 retval = ++lck->lk.depth_locked;
235 } else if (!__kmp_test_tas_lock(lck, gtid)) {
236 retval = 0;
237 } else {
238 KMP_MB();
239 retval = lck->lk.depth_locked = 1;
240 }
241 return retval;
242}
243
244static int __kmp_test_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
245 kmp_int32 gtid) {
246 char const *const func = "omp_test_nest_lock";
247 if (!__kmp_is_tas_lock_nestable(lck)) {
248 KMP_FATAL(LockSimpleUsedAsNestable, func);
249 }
250 return __kmp_test_nested_tas_lock(lck, gtid);
251}
252
253int __kmp_release_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
254 KMP_DEBUG_ASSERT(gtid >= 0);
255
256 KMP_MB();
257 if (--(lck->lk.depth_locked) == 0) {
258 __kmp_release_tas_lock(lck, gtid);
259 return KMP_LOCK_RELEASED;
260 }
261 return KMP_LOCK_STILL_HELD;
262}
263
264static int __kmp_release_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
265 kmp_int32 gtid) {
266 char const *const func = "omp_unset_nest_lock";
267 KMP_MB(); /* in case another processor initialized lock */
268 if (!__kmp_is_tas_lock_nestable(lck)) {
269 KMP_FATAL(LockSimpleUsedAsNestable, func);
270 }
271 if (__kmp_get_tas_lock_owner(lck) == -1) {
272 KMP_FATAL(LockUnsettingFree, func);
273 }
274 if (__kmp_get_tas_lock_owner(lck) != gtid) {
275 KMP_FATAL(LockUnsettingSetByAnother, func);
276 }
277 return __kmp_release_nested_tas_lock(lck, gtid);
278}
279
280void __kmp_init_nested_tas_lock(kmp_tas_lock_t *lck) {
281 __kmp_init_tas_lock(lck);
282 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
283}
284
285void __kmp_destroy_nested_tas_lock(kmp_tas_lock_t *lck) {
286 __kmp_destroy_tas_lock(lck);
287 lck->lk.depth_locked = 0;
288}
289
290static void __kmp_destroy_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) {
291 char const *const func = "omp_destroy_nest_lock";
292 if (!__kmp_is_tas_lock_nestable(lck)) {
293 KMP_FATAL(LockSimpleUsedAsNestable, func);
294 }
295 if (__kmp_get_tas_lock_owner(lck) != -1) {
296 KMP_FATAL(LockStillOwned, func);
297 }
298 __kmp_destroy_nested_tas_lock(lck);
299}
300
301#if KMP_USE_FUTEX
302
303/* ------------------------------------------------------------------------ */
304/* futex locks */
305
306// futex locks are really just test and set locks, with a different method
307// of handling contention. They take the same amount of space as test and
308// set locks, and are allocated the same way (i.e. use the area allocated by
309// the compiler for non-nested locks / allocate nested locks on the heap).
310
311static kmp_int32 __kmp_get_futex_lock_owner(kmp_futex_lock_t *lck) {
312 return KMP_LOCK_STRIP((TCR_4(lck->lk.poll) >> 1)) - 1;
313}
314
315static inline bool __kmp_is_futex_lock_nestable(kmp_futex_lock_t *lck) {
316 return lck->lk.depth_locked != -1;
317}
318
319__forceinline static int
320__kmp_acquire_futex_lock_timed_template(kmp_futex_lock_t *lck, kmp_int32 gtid) {
321 kmp_int32 gtid_code = (gtid + 1) << 1;
322
323 KMP_MB();
324
325#ifdef USE_LOCK_PROFILE
326 kmp_uint32 curr = KMP_LOCK_STRIP(TCR_4(lck->lk.poll));
327 if ((curr != 0) && (curr != gtid_code))
328 __kmp_printf("LOCK CONTENTION: %p\n", lck);
329/* else __kmp_printf( "." );*/
330#endif /* USE_LOCK_PROFILE */
331
332 KMP_FSYNC_PREPARE(lck);
333 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d entering\n",
334 lck, lck->lk.poll, gtid));
335
336 kmp_int32 poll_val;
337
338 while ((poll_val = KMP_COMPARE_AND_STORE_RET32(
339 &(lck->lk.poll), KMP_LOCK_FREE(futex),
340 KMP_LOCK_BUSY(gtid_code, futex))) != KMP_LOCK_FREE(futex)) {
341
342 kmp_int32 cond = KMP_LOCK_STRIP(poll_val) & 1;
343 KA_TRACE(
344 1000,
345 ("__kmp_acquire_futex_lock: lck:%p, T#%d poll_val = 0x%x cond = 0x%x\n",
346 lck, gtid, poll_val, cond));
347
348 // NOTE: if you try to use the following condition for this branch
349 //
350 // if ( poll_val & 1 == 0 )
351 //
352 // Then the 12.0 compiler has a bug where the following block will
353 // always be skipped, regardless of the value of the LSB of poll_val.
354 if (!cond) {
355 // Try to set the lsb in the poll to indicate to the owner
356 // thread that they need to wake this thread up.
357 if (!KMP_COMPARE_AND_STORE_REL32(&(lck->lk.poll), poll_val,
358 poll_val | KMP_LOCK_BUSY(1, futex))) {
359 KA_TRACE(
360 1000,
361 ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d can't set bit 0\n",
362 lck, lck->lk.poll, gtid));
363 continue;
364 }
365 poll_val |= KMP_LOCK_BUSY(1, futex);
366
367 KA_TRACE(1000,
368 ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d bit 0 set\n", lck,
369 lck->lk.poll, gtid));
370 }
371
372 KA_TRACE(
373 1000,
374 ("__kmp_acquire_futex_lock: lck:%p, T#%d before futex_wait(0x%x)\n",
375 lck, gtid, poll_val));
376
377 long rc;
378 if ((rc = syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAIT, poll_val, NULL,
379 NULL, 0)) != 0) {
380 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p, T#%d futex_wait(0x%x) "
381 "failed (rc=%ld errno=%d)\n",
382 lck, gtid, poll_val, rc, errno));
383 continue;
384 }
385
386 KA_TRACE(1000,
387 ("__kmp_acquire_futex_lock: lck:%p, T#%d after futex_wait(0x%x)\n",
388 lck, gtid, poll_val));
389 // This thread has now done a successful futex wait call and was entered on
390 // the OS futex queue. We must now perform a futex wake call when releasing
391 // the lock, as we have no idea how many other threads are in the queue.
392 gtid_code |= 1;
393 }
394
395 KMP_FSYNC_ACQUIRED(lck);
396 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck,
397 lck->lk.poll, gtid));
398 return KMP_LOCK_ACQUIRED_FIRST;
399}
400
401int __kmp_acquire_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
402 int retval = __kmp_acquire_futex_lock_timed_template(lck, gtid);
403 return retval;
404}
405
406static int __kmp_acquire_futex_lock_with_checks(kmp_futex_lock_t *lck,
407 kmp_int32 gtid) {
408 char const *const func = "omp_set_lock";
409 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
410 __kmp_is_futex_lock_nestable(lck)) {
411 KMP_FATAL(LockNestableUsedAsSimple, func);
412 }
413 if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) == gtid)) {
414 KMP_FATAL(LockIsAlreadyOwned, func);
415 }
416 return __kmp_acquire_futex_lock(lck, gtid);
417}
418
419int __kmp_test_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
420 if (KMP_COMPARE_AND_STORE_ACQ32(&(lck->lk.poll), KMP_LOCK_FREE(futex),
421 KMP_LOCK_BUSY((gtid + 1) << 1, futex))) {
422 KMP_FSYNC_ACQUIRED(lck);
423 return TRUE;
424 }
425 return FALSE;
426}
427
428static int __kmp_test_futex_lock_with_checks(kmp_futex_lock_t *lck,
429 kmp_int32 gtid) {
430 char const *const func = "omp_test_lock";
431 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
432 __kmp_is_futex_lock_nestable(lck)) {
433 KMP_FATAL(LockNestableUsedAsSimple, func);
434 }
435 return __kmp_test_futex_lock(lck, gtid);
436}
437
438int __kmp_release_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
439 KMP_MB(); /* Flush all pending memory write invalidates. */
440
441 KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d entering\n",
442 lck, lck->lk.poll, gtid));
443
444 KMP_FSYNC_RELEASING(lck);
445
446 kmp_int32 poll_val = KMP_XCHG_FIXED32(&(lck->lk.poll), KMP_LOCK_FREE(futex));
447
448 KA_TRACE(1000,
449 ("__kmp_release_futex_lock: lck:%p, T#%d released poll_val = 0x%x\n",
450 lck, gtid, poll_val));
451
452 if (KMP_LOCK_STRIP(poll_val) & 1) {
453 KA_TRACE(1000,
454 ("__kmp_release_futex_lock: lck:%p, T#%d futex_wake 1 thread\n",
455 lck, gtid));
456 syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAKE, KMP_LOCK_BUSY(1, futex),
457 NULL, NULL, 0);
458 }
459
460 KMP_MB(); /* Flush all pending memory write invalidates. */
461
462 KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck,
463 lck->lk.poll, gtid));
464
465 KMP_YIELD_OVERSUB();
466 return KMP_LOCK_RELEASED;
467}
468
469static int __kmp_release_futex_lock_with_checks(kmp_futex_lock_t *lck,
470 kmp_int32 gtid) {
471 char const *const func = "omp_unset_lock";
472 KMP_MB(); /* in case another processor initialized lock */
473 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
474 __kmp_is_futex_lock_nestable(lck)) {
475 KMP_FATAL(LockNestableUsedAsSimple, func);
476 }
477 if (__kmp_get_futex_lock_owner(lck) == -1) {
478 KMP_FATAL(LockUnsettingFree, func);
479 }
480 if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) >= 0) &&
481 (__kmp_get_futex_lock_owner(lck) != gtid)) {
482 KMP_FATAL(LockUnsettingSetByAnother, func);
483 }
484 return __kmp_release_futex_lock(lck, gtid);
485}
486
487void __kmp_init_futex_lock(kmp_futex_lock_t *lck) {
488 TCW_4(lck->lk.poll, KMP_LOCK_FREE(futex));
489}
490
491void __kmp_destroy_futex_lock(kmp_futex_lock_t *lck) { lck->lk.poll = 0; }
492
493static void __kmp_destroy_futex_lock_with_checks(kmp_futex_lock_t *lck) {
494 char const *const func = "omp_destroy_lock";
495 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
496 __kmp_is_futex_lock_nestable(lck)) {
497 KMP_FATAL(LockNestableUsedAsSimple, func);
498 }
499 if (__kmp_get_futex_lock_owner(lck) != -1) {
500 KMP_FATAL(LockStillOwned, func);
501 }
502 __kmp_destroy_futex_lock(lck);
503}
504
505// nested futex locks
506
507int __kmp_acquire_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
508 KMP_DEBUG_ASSERT(gtid >= 0);
509
510 if (__kmp_get_futex_lock_owner(lck) == gtid) {
511 lck->lk.depth_locked += 1;
512 return KMP_LOCK_ACQUIRED_NEXT;
513 } else {
514 __kmp_acquire_futex_lock_timed_template(lck, gtid);
515 lck->lk.depth_locked = 1;
516 return KMP_LOCK_ACQUIRED_FIRST;
517 }
518}
519
520static int __kmp_acquire_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
521 kmp_int32 gtid) {
522 char const *const func = "omp_set_nest_lock";
523 if (!__kmp_is_futex_lock_nestable(lck)) {
524 KMP_FATAL(LockSimpleUsedAsNestable, func);
525 }
526 return __kmp_acquire_nested_futex_lock(lck, gtid);
527}
528
529int __kmp_test_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
530 int retval;
531
532 KMP_DEBUG_ASSERT(gtid >= 0);
533
534 if (__kmp_get_futex_lock_owner(lck) == gtid) {
535 retval = ++lck->lk.depth_locked;
536 } else if (!__kmp_test_futex_lock(lck, gtid)) {
537 retval = 0;
538 } else {
539 KMP_MB();
540 retval = lck->lk.depth_locked = 1;
541 }
542 return retval;
543}
544
545static int __kmp_test_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
546 kmp_int32 gtid) {
547 char const *const func = "omp_test_nest_lock";
548 if (!__kmp_is_futex_lock_nestable(lck)) {
549 KMP_FATAL(LockSimpleUsedAsNestable, func);
550 }
551 return __kmp_test_nested_futex_lock(lck, gtid);
552}
553
554int __kmp_release_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
555 KMP_DEBUG_ASSERT(gtid >= 0);
556
557 KMP_MB();
558 if (--(lck->lk.depth_locked) == 0) {
559 __kmp_release_futex_lock(lck, gtid);
560 return KMP_LOCK_RELEASED;
561 }
562 return KMP_LOCK_STILL_HELD;
563}
564
565static int __kmp_release_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
566 kmp_int32 gtid) {
567 char const *const func = "omp_unset_nest_lock";
568 KMP_MB(); /* in case another processor initialized lock */
569 if (!__kmp_is_futex_lock_nestable(lck)) {
570 KMP_FATAL(LockSimpleUsedAsNestable, func);
571 }
572 if (__kmp_get_futex_lock_owner(lck) == -1) {
573 KMP_FATAL(LockUnsettingFree, func);
574 }
575 if (__kmp_get_futex_lock_owner(lck) != gtid) {
576 KMP_FATAL(LockUnsettingSetByAnother, func);
577 }
578 return __kmp_release_nested_futex_lock(lck, gtid);
579}
580
581void __kmp_init_nested_futex_lock(kmp_futex_lock_t *lck) {
582 __kmp_init_futex_lock(lck);
583 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
584}
585
586void __kmp_destroy_nested_futex_lock(kmp_futex_lock_t *lck) {
587 __kmp_destroy_futex_lock(lck);
588 lck->lk.depth_locked = 0;
589}
590
591static void __kmp_destroy_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) {
592 char const *const func = "omp_destroy_nest_lock";
593 if (!__kmp_is_futex_lock_nestable(lck)) {
594 KMP_FATAL(LockSimpleUsedAsNestable, func);
595 }
596 if (__kmp_get_futex_lock_owner(lck) != -1) {
597 KMP_FATAL(LockStillOwned, func);
598 }
599 __kmp_destroy_nested_futex_lock(lck);
600}
601
602#endif // KMP_USE_FUTEX
603
604/* ------------------------------------------------------------------------ */
605/* ticket (bakery) locks */
606
607static kmp_int32 __kmp_get_ticket_lock_owner(kmp_ticket_lock_t *lck) {
608 return std::atomic_load_explicit(&lck->lk.owner_id,
609 std::memory_order_relaxed) -
610 1;
611}
612
613static inline bool __kmp_is_ticket_lock_nestable(kmp_ticket_lock_t *lck) {
614 return std::atomic_load_explicit(&lck->lk.depth_locked,
615 std::memory_order_relaxed) != -1;
616}
617
618static kmp_uint32 __kmp_bakery_check(void *now_serving, kmp_uint32 my_ticket) {
619 return std::atomic_load_explicit((std::atomic<unsigned> *)now_serving,
620 std::memory_order_acquire) == my_ticket;
621}
622
623__forceinline static int
624__kmp_acquire_ticket_lock_timed_template(kmp_ticket_lock_t *lck,
625 kmp_int32 gtid) {
626 kmp_uint32 my_ticket = std::atomic_fetch_add_explicit(
627 &lck->lk.next_ticket, 1U, std::memory_order_relaxed);
628
629#ifdef USE_LOCK_PROFILE
630 if (std::atomic_load_explicit(&lck->lk.now_serving,
631 std::memory_order_relaxed) != my_ticket)
632 __kmp_printf("LOCK CONTENTION: %p\n", lck);
633/* else __kmp_printf( "." );*/
634#endif /* USE_LOCK_PROFILE */
635
636 if (std::atomic_load_explicit(&lck->lk.now_serving,
637 std::memory_order_acquire) == my_ticket) {
638 return KMP_LOCK_ACQUIRED_FIRST;
639 }
640 KMP_WAIT_PTR(&lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck);
641 return KMP_LOCK_ACQUIRED_FIRST;
642}
643
644int __kmp_acquire_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
645 int retval = __kmp_acquire_ticket_lock_timed_template(lck, gtid);
646 return retval;
647}
648
649static int __kmp_acquire_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
650 kmp_int32 gtid) {
651 char const *const func = "omp_set_lock";
652
653 if (!std::atomic_load_explicit(&lck->lk.initialized,
654 std::memory_order_relaxed)) {
655 KMP_FATAL(LockIsUninitialized, func);
656 }
657 if (lck->lk.self != lck) {
658 KMP_FATAL(LockIsUninitialized, func);
659 }
660 if (__kmp_is_ticket_lock_nestable(lck)) {
661 KMP_FATAL(LockNestableUsedAsSimple, func);
662 }
663 if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) == gtid)) {
664 KMP_FATAL(LockIsAlreadyOwned, func);
665 }
666
667 __kmp_acquire_ticket_lock(lck, gtid);
668
669 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
670 std::memory_order_relaxed);
671 return KMP_LOCK_ACQUIRED_FIRST;
672}
673
674int __kmp_test_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
675 kmp_uint32 my_ticket = std::atomic_load_explicit(&lck->lk.next_ticket,
676 std::memory_order_relaxed);
677
678 if (std::atomic_load_explicit(&lck->lk.now_serving,
679 std::memory_order_relaxed) == my_ticket) {
680 kmp_uint32 next_ticket = my_ticket + 1;
681 if (std::atomic_compare_exchange_strong_explicit(
682 &lck->lk.next_ticket, &my_ticket, next_ticket,
683 std::memory_order_acquire, std::memory_order_acquire)) {
684 return TRUE;
685 }
686 }
687 return FALSE;
688}
689
690static int __kmp_test_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
691 kmp_int32 gtid) {
692 char const *const func = "omp_test_lock";
693
694 if (!std::atomic_load_explicit(&lck->lk.initialized,
695 std::memory_order_relaxed)) {
696 KMP_FATAL(LockIsUninitialized, func);
697 }
698 if (lck->lk.self != lck) {
699 KMP_FATAL(LockIsUninitialized, func);
700 }
701 if (__kmp_is_ticket_lock_nestable(lck)) {
702 KMP_FATAL(LockNestableUsedAsSimple, func);
703 }
704
705 int retval = __kmp_test_ticket_lock(lck, gtid);
706
707 if (retval) {
708 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
709 std::memory_order_relaxed);
710 }
711 return retval;
712}
713
714int __kmp_release_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
715 kmp_uint32 distance = std::atomic_load_explicit(&lck->lk.next_ticket,
716 std::memory_order_relaxed) -
717 std::atomic_load_explicit(&lck->lk.now_serving,
718 std::memory_order_relaxed);
719
720 std::atomic_fetch_add_explicit(&lck->lk.now_serving, 1U,
721 std::memory_order_release);
722
723 KMP_YIELD(distance >
724 (kmp_uint32)(__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc));
725 return KMP_LOCK_RELEASED;
726}
727
728static int __kmp_release_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
729 kmp_int32 gtid) {
730 char const *const func = "omp_unset_lock";
731
732 if (!std::atomic_load_explicit(&lck->lk.initialized,
733 std::memory_order_relaxed)) {
734 KMP_FATAL(LockIsUninitialized, func);
735 }
736 if (lck->lk.self != lck) {
737 KMP_FATAL(LockIsUninitialized, func);
738 }
739 if (__kmp_is_ticket_lock_nestable(lck)) {
740 KMP_FATAL(LockNestableUsedAsSimple, func);
741 }
742 if (__kmp_get_ticket_lock_owner(lck) == -1) {
743 KMP_FATAL(LockUnsettingFree, func);
744 }
745 if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) >= 0) &&
746 (__kmp_get_ticket_lock_owner(lck) != gtid)) {
747 KMP_FATAL(LockUnsettingSetByAnother, func);
748 }
749 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
750 return __kmp_release_ticket_lock(lck, gtid);
751}
752
753void __kmp_init_ticket_lock(kmp_ticket_lock_t *lck) {
754 lck->lk.location = NULL;
755 lck->lk.self = lck;
756 std::atomic_store_explicit(&lck->lk.next_ticket, 0U,
757 std::memory_order_relaxed);
758 std::atomic_store_explicit(&lck->lk.now_serving, 0U,
759 std::memory_order_relaxed);
760 std::atomic_store_explicit(
761 &lck->lk.owner_id, 0,
762 std::memory_order_relaxed); // no thread owns the lock.
763 std::atomic_store_explicit(
764 &lck->lk.depth_locked, -1,
765 std::memory_order_relaxed); // -1 => not a nested lock.
766 std::atomic_store_explicit(&lck->lk.initialized, true,
767 std::memory_order_release);
768}
769
770void __kmp_destroy_ticket_lock(kmp_ticket_lock_t *lck) {
771 std::atomic_store_explicit(&lck->lk.initialized, false,
772 std::memory_order_release);
773 lck->lk.self = NULL;
774 lck->lk.location = NULL;
775 std::atomic_store_explicit(&lck->lk.next_ticket, 0U,
776 std::memory_order_relaxed);
777 std::atomic_store_explicit(&lck->lk.now_serving, 0U,
778 std::memory_order_relaxed);
779 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
780 std::atomic_store_explicit(&lck->lk.depth_locked, -1,
781 std::memory_order_relaxed);
782}
783
784static void __kmp_destroy_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
785 char const *const func = "omp_destroy_lock";
786
787 if (!std::atomic_load_explicit(&lck->lk.initialized,
788 std::memory_order_relaxed)) {
789 KMP_FATAL(LockIsUninitialized, func);
790 }
791 if (lck->lk.self != lck) {
792 KMP_FATAL(LockIsUninitialized, func);
793 }
794 if (__kmp_is_ticket_lock_nestable(lck)) {
795 KMP_FATAL(LockNestableUsedAsSimple, func);
796 }
797 if (__kmp_get_ticket_lock_owner(lck) != -1) {
798 KMP_FATAL(LockStillOwned, func);
799 }
800 __kmp_destroy_ticket_lock(lck);
801}
802
803// nested ticket locks
804
805int __kmp_acquire_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
806 KMP_DEBUG_ASSERT(gtid >= 0);
807
808 if (__kmp_get_ticket_lock_owner(lck) == gtid) {
809 std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1,
810 std::memory_order_relaxed);
811 return KMP_LOCK_ACQUIRED_NEXT;
812 } else {
813 __kmp_acquire_ticket_lock_timed_template(lck, gtid);
814 std::atomic_store_explicit(&lck->lk.depth_locked, 1,
815 std::memory_order_relaxed);
816 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
817 std::memory_order_relaxed);
818 return KMP_LOCK_ACQUIRED_FIRST;
819 }
820}
821
822static int __kmp_acquire_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
823 kmp_int32 gtid) {
824 char const *const func = "omp_set_nest_lock";
825
826 if (!std::atomic_load_explicit(&lck->lk.initialized,
827 std::memory_order_relaxed)) {
828 KMP_FATAL(LockIsUninitialized, func);
829 }
830 if (lck->lk.self != lck) {
831 KMP_FATAL(LockIsUninitialized, func);
832 }
833 if (!__kmp_is_ticket_lock_nestable(lck)) {
834 KMP_FATAL(LockSimpleUsedAsNestable, func);
835 }
836 return __kmp_acquire_nested_ticket_lock(lck, gtid);
837}
838
839int __kmp_test_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
840 int retval;
841
842 KMP_DEBUG_ASSERT(gtid >= 0);
843
844 if (__kmp_get_ticket_lock_owner(lck) == gtid) {
845 retval = std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1,
846 std::memory_order_relaxed) +
847 1;
848 } else if (!__kmp_test_ticket_lock(lck, gtid)) {
849 retval = 0;
850 } else {
851 std::atomic_store_explicit(&lck->lk.depth_locked, 1,
852 std::memory_order_relaxed);
853 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
854 std::memory_order_relaxed);
855 retval = 1;
856 }
857 return retval;
858}
859
860static int __kmp_test_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
861 kmp_int32 gtid) {
862 char const *const func = "omp_test_nest_lock";
863
864 if (!std::atomic_load_explicit(&lck->lk.initialized,
865 std::memory_order_relaxed)) {
866 KMP_FATAL(LockIsUninitialized, func);
867 }
868 if (lck->lk.self != lck) {
869 KMP_FATAL(LockIsUninitialized, func);
870 }
871 if (!__kmp_is_ticket_lock_nestable(lck)) {
872 KMP_FATAL(LockSimpleUsedAsNestable, func);
873 }
874 return __kmp_test_nested_ticket_lock(lck, gtid);
875}
876
877int __kmp_release_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
878 KMP_DEBUG_ASSERT(gtid >= 0);
879
880 if ((std::atomic_fetch_add_explicit(&lck->lk.depth_locked, -1,
881 std::memory_order_relaxed) -
882 1) == 0) {
883 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
884 __kmp_release_ticket_lock(lck, gtid);
885 return KMP_LOCK_RELEASED;
886 }
887 return KMP_LOCK_STILL_HELD;
888}
889
890static int __kmp_release_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
891 kmp_int32 gtid) {
892 char const *const func = "omp_unset_nest_lock";
893
894 if (!std::atomic_load_explicit(&lck->lk.initialized,
895 std::memory_order_relaxed)) {
896 KMP_FATAL(LockIsUninitialized, func);
897 }
898 if (lck->lk.self != lck) {
899 KMP_FATAL(LockIsUninitialized, func);
900 }
901 if (!__kmp_is_ticket_lock_nestable(lck)) {
902 KMP_FATAL(LockSimpleUsedAsNestable, func);
903 }
904 if (__kmp_get_ticket_lock_owner(lck) == -1) {
905 KMP_FATAL(LockUnsettingFree, func);
906 }
907 if (__kmp_get_ticket_lock_owner(lck) != gtid) {
908 KMP_FATAL(LockUnsettingSetByAnother, func);
909 }
910 return __kmp_release_nested_ticket_lock(lck, gtid);
911}
912
913void __kmp_init_nested_ticket_lock(kmp_ticket_lock_t *lck) {
914 __kmp_init_ticket_lock(lck);
915 std::atomic_store_explicit(&lck->lk.depth_locked, 0,
916 std::memory_order_relaxed);
917 // >= 0 for nestable locks, -1 for simple locks
918}
919
920void __kmp_destroy_nested_ticket_lock(kmp_ticket_lock_t *lck) {
921 __kmp_destroy_ticket_lock(lck);
922 std::atomic_store_explicit(&lck->lk.depth_locked, 0,
923 std::memory_order_relaxed);
924}
925
926static void
927__kmp_destroy_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
928 char const *const func = "omp_destroy_nest_lock";
929
930 if (!std::atomic_load_explicit(&lck->lk.initialized,
931 std::memory_order_relaxed)) {
932 KMP_FATAL(LockIsUninitialized, func);
933 }
934 if (lck->lk.self != lck) {
935 KMP_FATAL(LockIsUninitialized, func);
936 }
937 if (!__kmp_is_ticket_lock_nestable(lck)) {
938 KMP_FATAL(LockSimpleUsedAsNestable, func);
939 }
940 if (__kmp_get_ticket_lock_owner(lck) != -1) {
941 KMP_FATAL(LockStillOwned, func);
942 }
943 __kmp_destroy_nested_ticket_lock(lck);
944}
945
946// access functions to fields which don't exist for all lock kinds.
947
948static const ident_t *__kmp_get_ticket_lock_location(kmp_ticket_lock_t *lck) {
949 return lck->lk.location;
950}
951
952static void __kmp_set_ticket_lock_location(kmp_ticket_lock_t *lck,
953 const ident_t *loc) {
954 lck->lk.location = loc;
955}
956
957static kmp_lock_flags_t __kmp_get_ticket_lock_flags(kmp_ticket_lock_t *lck) {
958 return lck->lk.flags;
959}
960
961static void __kmp_set_ticket_lock_flags(kmp_ticket_lock_t *lck,
962 kmp_lock_flags_t flags) {
963 lck->lk.flags = flags;
964}
965
966/* ------------------------------------------------------------------------ */
967/* queuing locks */
968
969/* First the states
970 (head,tail) = 0, 0 means lock is unheld, nobody on queue
971 UINT_MAX or -1, 0 means lock is held, nobody on queue
972 h, h means lock held or about to transition,
973 1 element on queue
974 h, t h <> t, means lock is held or about to
975 transition, >1 elements on queue
976
977 Now the transitions
978 Acquire(0,0) = -1 ,0
979 Release(0,0) = Error
980 Acquire(-1,0) = h ,h h > 0
981 Release(-1,0) = 0 ,0
982 Acquire(h,h) = h ,t h > 0, t > 0, h <> t
983 Release(h,h) = -1 ,0 h > 0
984 Acquire(h,t) = h ,t' h > 0, t > 0, t' > 0, h <> t, h <> t', t <> t'
985 Release(h,t) = h',t h > 0, t > 0, h <> t, h <> h', h' maybe = t
986
987 And pictorially
988
989 +-----+
990 | 0, 0|------- release -------> Error
991 +-----+
992 | ^
993 acquire| |release
994 | |
995 | |
996 v |
997 +-----+
998 |-1, 0|
999 +-----+
1000 | ^
1001 acquire| |release
1002 | |
1003 | |
1004 v |
1005 +-----+
1006 | h, h|
1007 +-----+
1008 | ^
1009 acquire| |release
1010 | |
1011 | |
1012 v |
1013 +-----+
1014 | h, t|----- acquire, release loopback ---+
1015 +-----+ |
1016 ^ |
1017 | |
1018 +------------------------------------+
1019 */
1020
1021#ifdef DEBUG_QUEUING_LOCKS
1022
1023/* Stuff for circular trace buffer */
1024#define TRACE_BUF_ELE 1024
1025static char traces[TRACE_BUF_ELE][128] = {0};
1026static int tc = 0;
1027#define TRACE_LOCK(X, Y) \
1028 KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s\n", X, Y);
1029#define TRACE_LOCK_T(X, Y, Z) \
1030 KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s%d\n", X, Y, Z);
1031#define TRACE_LOCK_HT(X, Y, Z, Q) \
1032 KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s %d,%d\n", X, Y, \
1033 Z, Q);
1034
1035static void __kmp_dump_queuing_lock(kmp_info_t *this_thr, kmp_int32 gtid,
1036 kmp_queuing_lock_t *lck, kmp_int32 head_id,
1037 kmp_int32 tail_id) {
1038 kmp_int32 t, i;
1039
1040 __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: TRACE BEGINS HERE! \n");
1041
1042 i = tc % TRACE_BUF_ELE;
1043 __kmp_printf_no_lock("%s\n", traces[i]);
1044 i = (i + 1) % TRACE_BUF_ELE;
1045 while (i != (tc % TRACE_BUF_ELE)) {
1046 __kmp_printf_no_lock("%s", traces[i]);
1047 i = (i + 1) % TRACE_BUF_ELE;
1048 }
1049 __kmp_printf_no_lock("\n");
1050
1051 __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: gtid+1:%d, spin_here:%d, "
1052 "next_wait:%d, head_id:%d, tail_id:%d\n",
1053 gtid + 1, this_thr->th.th_spin_here,
1054 this_thr->th.th_next_waiting, head_id, tail_id);
1055
1056 __kmp_printf_no_lock("\t\thead: %d ", lck->lk.head_id);
1057
1058 if (lck->lk.head_id >= 1) {
1059 t = __kmp_threads[lck->lk.head_id - 1]->th.th_next_waiting;
1060 while (t > 0) {
1061 __kmp_printf_no_lock("-> %d ", t);
1062 t = __kmp_threads[t - 1]->th.th_next_waiting;
1063 }
1064 }
1065 __kmp_printf_no_lock("; tail: %d ", lck->lk.tail_id);
1066 __kmp_printf_no_lock("\n\n");
1067}
1068
1069#endif /* DEBUG_QUEUING_LOCKS */
1070
1071static kmp_int32 __kmp_get_queuing_lock_owner(kmp_queuing_lock_t *lck) {
1072 return TCR_4(lck->lk.owner_id) - 1;
1073}
1074
1075static inline bool __kmp_is_queuing_lock_nestable(kmp_queuing_lock_t *lck) {
1076 return lck->lk.depth_locked != -1;
1077}
1078
1079/* Acquire a lock using a the queuing lock implementation */
1080template <bool takeTime>
1081/* [TLW] The unused template above is left behind because of what BEB believes
1082 is a potential compiler problem with __forceinline. */
1083__forceinline static int
1084__kmp_acquire_queuing_lock_timed_template(kmp_queuing_lock_t *lck,
1085 kmp_int32 gtid) {
1086 kmp_info_t *this_thr = __kmp_thread_from_gtid(gtid);
1087 volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1088 volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1089 volatile kmp_uint32 *spin_here_p;
1090
1091#if OMPT_SUPPORT
1092 ompt_state_t prev_state = ompt_state_undefined;
1093#endif
1094
1095 KA_TRACE(1000,
1096 ("__kmp_acquire_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1097
1098 KMP_FSYNC_PREPARE(lck);
1099 KMP_DEBUG_ASSERT(this_thr != NULL);
1100 spin_here_p = &this_thr->th.th_spin_here;
1101
1102#ifdef DEBUG_QUEUING_LOCKS
1103 TRACE_LOCK(gtid + 1, "acq ent");
1104 if (*spin_here_p)
1105 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1106 if (this_thr->th.th_next_waiting != 0)
1107 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1108#endif
1109 KMP_DEBUG_ASSERT(!*spin_here_p);
1110 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1111
1112 /* The following st.rel to spin_here_p needs to precede the cmpxchg.acq to
1113 head_id_p that may follow, not just in execution order, but also in
1114 visibility order. This way, when a releasing thread observes the changes to
1115 the queue by this thread, it can rightly assume that spin_here_p has
1116 already been set to TRUE, so that when it sets spin_here_p to FALSE, it is
1117 not premature. If the releasing thread sets spin_here_p to FALSE before
1118 this thread sets it to TRUE, this thread will hang. */
1119 *spin_here_p = TRUE; /* before enqueuing to prevent race */
1120
1121 while (1) {
1122 kmp_int32 enqueued;
1123 kmp_int32 head;
1124 kmp_int32 tail;
1125
1126 head = *head_id_p;
1127
1128 switch (head) {
1129
1130 case -1: {
1131#ifdef DEBUG_QUEUING_LOCKS
1132 tail = *tail_id_p;
1133 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1134#endif
1135 tail = 0; /* to make sure next link asynchronously read is not set
1136 accidentally; this assignment prevents us from entering the
1137 if ( t > 0 ) condition in the enqueued case below, which is not
1138 necessary for this state transition */
1139
1140 /* try (-1,0)->(tid,tid) */
1141 enqueued = KMP_COMPARE_AND_STORE_ACQ64((volatile kmp_int64 *)tail_id_p,
1142 KMP_PACK_64(-1, 0),
1143 KMP_PACK_64(gtid + 1, gtid + 1));
1144#ifdef DEBUG_QUEUING_LOCKS
1145 if (enqueued)
1146 TRACE_LOCK(gtid + 1, "acq enq: (-1,0)->(tid,tid)");
1147#endif
1148 } break;
1149
1150 default: {
1151 tail = *tail_id_p;
1152 KMP_DEBUG_ASSERT(tail != gtid + 1);
1153
1154#ifdef DEBUG_QUEUING_LOCKS
1155 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1156#endif
1157
1158 if (tail == 0) {
1159 enqueued = FALSE;
1160 } else {
1161 /* try (h,t) or (h,h)->(h,tid) */
1162 enqueued = KMP_COMPARE_AND_STORE_ACQ32(tail_id_p, tail, gtid + 1);
1163
1164#ifdef DEBUG_QUEUING_LOCKS
1165 if (enqueued)
1166 TRACE_LOCK(gtid + 1, "acq enq: (h,t)->(h,tid)");
1167#endif
1168 }
1169 } break;
1170
1171 case 0: /* empty queue */
1172 {
1173 kmp_int32 grabbed_lock;
1174
1175#ifdef DEBUG_QUEUING_LOCKS
1176 tail = *tail_id_p;
1177 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1178#endif
1179 /* try (0,0)->(-1,0) */
1180
1181 /* only legal transition out of head = 0 is head = -1 with no change to
1182 * tail */
1183 grabbed_lock = KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1);
1184
1185 if (grabbed_lock) {
1186
1187 *spin_here_p = FALSE;
1188
1189 KA_TRACE(
1190 1000,
1191 ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: no queuing\n",
1192 lck, gtid));
1193#ifdef DEBUG_QUEUING_LOCKS
1194 TRACE_LOCK_HT(gtid + 1, "acq exit: ", head, 0);
1195#endif
1196
1197#if OMPT_SUPPORT
1198 if (ompt_enabled.enabled && prev_state != ompt_state_undefined) {
1199 /* change the state before clearing wait_id */
1200 this_thr->th.ompt_thread_info.state = prev_state;
1201 this_thr->th.ompt_thread_info.wait_id = 0;
1202 }
1203#endif
1204
1205 KMP_FSYNC_ACQUIRED(lck);
1206 return KMP_LOCK_ACQUIRED_FIRST; /* lock holder cannot be on queue */
1207 }
1208 enqueued = FALSE;
1209 } break;
1210 }
1211
1212#if OMPT_SUPPORT
1213 if (ompt_enabled.enabled && prev_state == ompt_state_undefined) {
1214 /* this thread will spin; set wait_id before entering wait state */
1215 prev_state = this_thr->th.ompt_thread_info.state;
1216 this_thr->th.ompt_thread_info.wait_id = (uint64_t)lck;
1217 this_thr->th.ompt_thread_info.state = ompt_state_wait_lock;
1218 }
1219#endif
1220
1221 if (enqueued) {
1222 if (tail > 0) {
1223 kmp_info_t *tail_thr = __kmp_thread_from_gtid(tail - 1);
1224 KMP_ASSERT(tail_thr != NULL);
1225 tail_thr->th.th_next_waiting = gtid + 1;
1226 /* corresponding wait for this write in release code */
1227 }
1228 KA_TRACE(1000,
1229 ("__kmp_acquire_queuing_lock: lck:%p, T#%d waiting for lock\n",
1230 lck, gtid));
1231
1232 KMP_MB();
1233 // ToDo: Use __kmp_wait_sleep or similar when blocktime != inf
1234 KMP_WAIT(spin_here_p, FALSE, KMP_EQ, lck);
1235 // Synchronize writes to both runtime thread structures
1236 // and writes in user code.
1237 KMP_MB();
1238
1239#ifdef DEBUG_QUEUING_LOCKS
1240 TRACE_LOCK(gtid + 1, "acq spin");
1241
1242 if (this_thr->th.th_next_waiting != 0)
1243 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1244#endif
1245 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1246 KA_TRACE(1000, ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: after "
1247 "waiting on queue\n",
1248 lck, gtid));
1249
1250#ifdef DEBUG_QUEUING_LOCKS
1251 TRACE_LOCK(gtid + 1, "acq exit 2");
1252#endif
1253
1254#if OMPT_SUPPORT
1255 /* change the state before clearing wait_id */
1256 this_thr->th.ompt_thread_info.state = prev_state;
1257 this_thr->th.ompt_thread_info.wait_id = 0;
1258#endif
1259
1260 /* got lock, we were dequeued by the thread that released lock */
1261 return KMP_LOCK_ACQUIRED_FIRST;
1262 }
1263
1264 /* Yield if number of threads > number of logical processors */
1265 /* ToDo: Not sure why this should only be in oversubscription case,
1266 maybe should be traditional YIELD_INIT/YIELD_WHEN loop */
1267 KMP_YIELD_OVERSUB();
1268
1269#ifdef DEBUG_QUEUING_LOCKS
1270 TRACE_LOCK(gtid + 1, "acq retry");
1271#endif
1272 }
1273 KMP_ASSERT2(0, "should not get here");
1274 return KMP_LOCK_ACQUIRED_FIRST;
1275}
1276
1277int __kmp_acquire_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1278 KMP_DEBUG_ASSERT(gtid >= 0);
1279
1280 int retval = __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1281 return retval;
1282}
1283
1284static int __kmp_acquire_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1285 kmp_int32 gtid) {
1286 char const *const func = "omp_set_lock";
1287 if (lck->lk.initialized != lck) {
1288 KMP_FATAL(LockIsUninitialized, func);
1289 }
1290 if (__kmp_is_queuing_lock_nestable(lck)) {
1291 KMP_FATAL(LockNestableUsedAsSimple, func);
1292 }
1293 if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1294 KMP_FATAL(LockIsAlreadyOwned, func);
1295 }
1296
1297 __kmp_acquire_queuing_lock(lck, gtid);
1298
1299 lck->lk.owner_id = gtid + 1;
1300 return KMP_LOCK_ACQUIRED_FIRST;
1301}
1302
1303int __kmp_test_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1304 volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1305 kmp_int32 head;
1306#ifdef KMP_DEBUG
1307 kmp_info_t *this_thr;
1308#endif
1309
1310 KA_TRACE(1000, ("__kmp_test_queuing_lock: T#%d entering\n", gtid));
1311 KMP_DEBUG_ASSERT(gtid >= 0);
1312#ifdef KMP_DEBUG
1313 this_thr = __kmp_thread_from_gtid(gtid);
1314 KMP_DEBUG_ASSERT(this_thr != NULL);
1315 KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1316#endif
1317
1318 head = *head_id_p;
1319
1320 if (head == 0) { /* nobody on queue, nobody holding */
1321 /* try (0,0)->(-1,0) */
1322 if (KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1)) {
1323 KA_TRACE(1000,
1324 ("__kmp_test_queuing_lock: T#%d exiting: holding lock\n", gtid));
1325 KMP_FSYNC_ACQUIRED(lck);
1326 return TRUE;
1327 }
1328 }
1329
1330 KA_TRACE(1000,
1331 ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid));
1332 return FALSE;
1333}
1334
1335static int __kmp_test_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1336 kmp_int32 gtid) {
1337 char const *const func = "omp_test_lock";
1338 if (lck->lk.initialized != lck) {
1339 KMP_FATAL(LockIsUninitialized, func);
1340 }
1341 if (__kmp_is_queuing_lock_nestable(lck)) {
1342 KMP_FATAL(LockNestableUsedAsSimple, func);
1343 }
1344
1345 int retval = __kmp_test_queuing_lock(lck, gtid);
1346
1347 if (retval) {
1348 lck->lk.owner_id = gtid + 1;
1349 }
1350 return retval;
1351}
1352
1353int __kmp_release_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1354 volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1355 volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1356
1357 KA_TRACE(1000,
1358 ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1359 KMP_DEBUG_ASSERT(gtid >= 0);
1360#if KMP_DEBUG || DEBUG_QUEUING_LOCKS
1361 kmp_info_t *this_thr = __kmp_thread_from_gtid(gtid);
1362#endif
1363 KMP_DEBUG_ASSERT(this_thr != NULL);
1364#ifdef DEBUG_QUEUING_LOCKS
1365 TRACE_LOCK(gtid + 1, "rel ent");
1366
1367 if (this_thr->th.th_spin_here)
1368 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1369 if (this_thr->th.th_next_waiting != 0)
1370 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1371#endif
1372 KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1373 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1374
1375 KMP_FSYNC_RELEASING(lck);
1376
1377 while (1) {
1378 kmp_int32 dequeued;
1379 kmp_int32 head;
1380 kmp_int32 tail;
1381
1382 head = *head_id_p;
1383
1384#ifdef DEBUG_QUEUING_LOCKS
1385 tail = *tail_id_p;
1386 TRACE_LOCK_HT(gtid + 1, "rel read: ", head, tail);
1387 if (head == 0)
1388 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1389#endif
1390 KMP_DEBUG_ASSERT(head !=
1391 0); /* holding the lock, head must be -1 or queue head */
1392
1393 if (head == -1) { /* nobody on queue */
1394 /* try (-1,0)->(0,0) */
1395 if (KMP_COMPARE_AND_STORE_REL32(head_id_p, -1, 0)) {
1396 KA_TRACE(
1397 1000,
1398 ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: queue empty\n",
1399 lck, gtid));
1400#ifdef DEBUG_QUEUING_LOCKS
1401 TRACE_LOCK_HT(gtid + 1, "rel exit: ", 0, 0);
1402#endif
1403
1404#if OMPT_SUPPORT
1405/* nothing to do - no other thread is trying to shift blame */
1406#endif
1407 return KMP_LOCK_RELEASED;
1408 }
1409 dequeued = FALSE;
1410 } else {
1411 KMP_MB();
1412 tail = *tail_id_p;
1413 if (head == tail) { /* only one thread on the queue */
1414#ifdef DEBUG_QUEUING_LOCKS
1415 if (head <= 0)
1416 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1417#endif
1418 KMP_DEBUG_ASSERT(head > 0);
1419
1420 /* try (h,h)->(-1,0) */
1421 dequeued = KMP_COMPARE_AND_STORE_REL64(
1422 RCAST(volatile kmp_int64 *, tail_id_p), KMP_PACK_64(head, head),
1423 KMP_PACK_64(-1, 0));
1424#ifdef DEBUG_QUEUING_LOCKS
1425 TRACE_LOCK(gtid + 1, "rel deq: (h,h)->(-1,0)");
1426#endif
1427
1428 } else {
1429 volatile kmp_int32 *waiting_id_p;
1430 kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1431 KMP_DEBUG_ASSERT(head_thr != NULL);
1432 waiting_id_p = &head_thr->th.th_next_waiting;
1433
1434/* Does this require synchronous reads? */
1435#ifdef DEBUG_QUEUING_LOCKS
1436 if (head <= 0 || tail <= 0)
1437 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1438#endif
1439 KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1440
1441 /* try (h,t)->(h',t) or (t,t) */
1442 KMP_MB();
1443 /* make sure enqueuing thread has time to update next waiting thread
1444 * field */
1445 *head_id_p =
1446 KMP_WAIT((volatile kmp_uint32 *)waiting_id_p, 0, KMP_NEQ, NULL);
1447#ifdef DEBUG_QUEUING_LOCKS
1448 TRACE_LOCK(gtid + 1, "rel deq: (h,t)->(h',t)");
1449#endif
1450 dequeued = TRUE;
1451 }
1452 }
1453
1454 if (dequeued) {
1455 kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1456 KMP_DEBUG_ASSERT(head_thr != NULL);
1457
1458/* Does this require synchronous reads? */
1459#ifdef DEBUG_QUEUING_LOCKS
1460 if (head <= 0 || tail <= 0)
1461 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1462#endif
1463 KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1464
1465 /* For clean code only. Thread not released until next statement prevents
1466 race with acquire code. */
1467 head_thr->th.th_next_waiting = 0;
1468#ifdef DEBUG_QUEUING_LOCKS
1469 TRACE_LOCK_T(gtid + 1, "rel nw=0 for t=", head);
1470#endif
1471
1472 KMP_MB();
1473 /* reset spin value */
1474 head_thr->th.th_spin_here = FALSE;
1475
1476 KA_TRACE(1000, ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: after "
1477 "dequeuing\n",
1478 lck, gtid));
1479#ifdef DEBUG_QUEUING_LOCKS
1480 TRACE_LOCK(gtid + 1, "rel exit 2");
1481#endif
1482 return KMP_LOCK_RELEASED;
1483 }
1484 /* KMP_CPU_PAUSE(); don't want to make releasing thread hold up acquiring
1485 threads */
1486
1487#ifdef DEBUG_QUEUING_LOCKS
1488 TRACE_LOCK(gtid + 1, "rel retry");
1489#endif
1490
1491 } /* while */
1492 KMP_ASSERT2(0, "should not get here");
1493 return KMP_LOCK_RELEASED;
1494}
1495
1496static int __kmp_release_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1497 kmp_int32 gtid) {
1498 char const *const func = "omp_unset_lock";
1499 KMP_MB(); /* in case another processor initialized lock */
1500 if (lck->lk.initialized != lck) {
1501 KMP_FATAL(LockIsUninitialized, func);
1502 }
1503 if (__kmp_is_queuing_lock_nestable(lck)) {
1504 KMP_FATAL(LockNestableUsedAsSimple, func);
1505 }
1506 if (__kmp_get_queuing_lock_owner(lck) == -1) {
1507 KMP_FATAL(LockUnsettingFree, func);
1508 }
1509 if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1510 KMP_FATAL(LockUnsettingSetByAnother, func);
1511 }
1512 lck->lk.owner_id = 0;
1513 return __kmp_release_queuing_lock(lck, gtid);
1514}
1515
1516void __kmp_init_queuing_lock(kmp_queuing_lock_t *lck) {
1517 lck->lk.location = NULL;
1518 lck->lk.head_id = 0;
1519 lck->lk.tail_id = 0;
1520 lck->lk.next_ticket = 0;
1521 lck->lk.now_serving = 0;
1522 lck->lk.owner_id = 0; // no thread owns the lock.
1523 lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
1524 lck->lk.initialized = lck;
1525
1526 KA_TRACE(1000, ("__kmp_init_queuing_lock: lock %p initialized\n", lck));
1527}
1528
1529void __kmp_destroy_queuing_lock(kmp_queuing_lock_t *lck) {
1530 lck->lk.initialized = NULL;
1531 lck->lk.location = NULL;
1532 lck->lk.head_id = 0;
1533 lck->lk.tail_id = 0;
1534 lck->lk.next_ticket = 0;
1535 lck->lk.now_serving = 0;
1536 lck->lk.owner_id = 0;
1537 lck->lk.depth_locked = -1;
1538}
1539
1540static void __kmp_destroy_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1541 char const *const func = "omp_destroy_lock";
1542 if (lck->lk.initialized != lck) {
1543 KMP_FATAL(LockIsUninitialized, func);
1544 }
1545 if (__kmp_is_queuing_lock_nestable(lck)) {
1546 KMP_FATAL(LockNestableUsedAsSimple, func);
1547 }
1548 if (__kmp_get_queuing_lock_owner(lck) != -1) {
1549 KMP_FATAL(LockStillOwned, func);
1550 }
1551 __kmp_destroy_queuing_lock(lck);
1552}
1553
1554// nested queuing locks
1555
1556int __kmp_acquire_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1557 KMP_DEBUG_ASSERT(gtid >= 0);
1558
1559 if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1560 lck->lk.depth_locked += 1;
1561 return KMP_LOCK_ACQUIRED_NEXT;
1562 } else {
1563 __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1564 KMP_MB();
1565 lck->lk.depth_locked = 1;
1566 KMP_MB();
1567 lck->lk.owner_id = gtid + 1;
1568 return KMP_LOCK_ACQUIRED_FIRST;
1569 }
1570}
1571
1572static int
1573__kmp_acquire_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1574 kmp_int32 gtid) {
1575 char const *const func = "omp_set_nest_lock";
1576 if (lck->lk.initialized != lck) {
1577 KMP_FATAL(LockIsUninitialized, func);
1578 }
1579 if (!__kmp_is_queuing_lock_nestable(lck)) {
1580 KMP_FATAL(LockSimpleUsedAsNestable, func);
1581 }
1582 return __kmp_acquire_nested_queuing_lock(lck, gtid);
1583}
1584
1585int __kmp_test_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1586 int retval;
1587
1588 KMP_DEBUG_ASSERT(gtid >= 0);
1589
1590 if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1591 retval = ++lck->lk.depth_locked;
1592 } else if (!__kmp_test_queuing_lock(lck, gtid)) {
1593 retval = 0;
1594 } else {
1595 KMP_MB();
1596 retval = lck->lk.depth_locked = 1;
1597 KMP_MB();
1598 lck->lk.owner_id = gtid + 1;
1599 }
1600 return retval;
1601}
1602
1603static int __kmp_test_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1604 kmp_int32 gtid) {
1605 char const *const func = "omp_test_nest_lock";
1606 if (lck->lk.initialized != lck) {
1607 KMP_FATAL(LockIsUninitialized, func);
1608 }
1609 if (!__kmp_is_queuing_lock_nestable(lck)) {
1610 KMP_FATAL(LockSimpleUsedAsNestable, func);
1611 }
1612 return __kmp_test_nested_queuing_lock(lck, gtid);
1613}
1614
1615int __kmp_release_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1616 KMP_DEBUG_ASSERT(gtid >= 0);
1617
1618 KMP_MB();
1619 if (--(lck->lk.depth_locked) == 0) {
1620 KMP_MB();
1621 lck->lk.owner_id = 0;
1622 __kmp_release_queuing_lock(lck, gtid);
1623 return KMP_LOCK_RELEASED;
1624 }
1625 return KMP_LOCK_STILL_HELD;
1626}
1627
1628static int
1629__kmp_release_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1630 kmp_int32 gtid) {
1631 char const *const func = "omp_unset_nest_lock";
1632 KMP_MB(); /* in case another processor initialized lock */
1633 if (lck->lk.initialized != lck) {
1634 KMP_FATAL(LockIsUninitialized, func);
1635 }
1636 if (!__kmp_is_queuing_lock_nestable(lck)) {
1637 KMP_FATAL(LockSimpleUsedAsNestable, func);
1638 }
1639 if (__kmp_get_queuing_lock_owner(lck) == -1) {
1640 KMP_FATAL(LockUnsettingFree, func);
1641 }
1642 if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1643 KMP_FATAL(LockUnsettingSetByAnother, func);
1644 }
1645 return __kmp_release_nested_queuing_lock(lck, gtid);
1646}
1647
1648void __kmp_init_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1649 __kmp_init_queuing_lock(lck);
1650 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
1651}
1652
1653void __kmp_destroy_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1654 __kmp_destroy_queuing_lock(lck);
1655 lck->lk.depth_locked = 0;
1656}
1657
1658static void
1659__kmp_destroy_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1660 char const *const func = "omp_destroy_nest_lock";
1661 if (lck->lk.initialized != lck) {
1662 KMP_FATAL(LockIsUninitialized, func);
1663 }
1664 if (!__kmp_is_queuing_lock_nestable(lck)) {
1665 KMP_FATAL(LockSimpleUsedAsNestable, func);
1666 }
1667 if (__kmp_get_queuing_lock_owner(lck) != -1) {
1668 KMP_FATAL(LockStillOwned, func);
1669 }
1670 __kmp_destroy_nested_queuing_lock(lck);
1671}
1672
1673// access functions to fields which don't exist for all lock kinds.
1674
1675static const ident_t *__kmp_get_queuing_lock_location(kmp_queuing_lock_t *lck) {
1676 return lck->lk.location;
1677}
1678
1679static void __kmp_set_queuing_lock_location(kmp_queuing_lock_t *lck,
1680 const ident_t *loc) {
1681 lck->lk.location = loc;
1682}
1683
1684static kmp_lock_flags_t __kmp_get_queuing_lock_flags(kmp_queuing_lock_t *lck) {
1685 return lck->lk.flags;
1686}
1687
1688static void __kmp_set_queuing_lock_flags(kmp_queuing_lock_t *lck,
1689 kmp_lock_flags_t flags) {
1690 lck->lk.flags = flags;
1691}
1692
1693#if KMP_USE_ADAPTIVE_LOCKS
1694
1695/* RTM Adaptive locks */
1696
1697#if KMP_HAVE_RTM_INTRINSICS
1698#include <immintrin.h>
1699#define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1700
1701#else
1702
1703// Values from the status register after failed speculation.
1704#define _XBEGIN_STARTED (~0u)
1705#define _XABORT_EXPLICIT (1 << 0)
1706#define _XABORT_RETRY (1 << 1)
1707#define _XABORT_CONFLICT (1 << 2)
1708#define _XABORT_CAPACITY (1 << 3)
1709#define _XABORT_DEBUG (1 << 4)
1710#define _XABORT_NESTED (1 << 5)
1711#define _XABORT_CODE(x) ((unsigned char)(((x) >> 24) & 0xFF))
1712
1713// Aborts for which it's worth trying again immediately
1714#define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1715
1716#define STRINGIZE_INTERNAL(arg) #arg
1717#define STRINGIZE(arg) STRINGIZE_INTERNAL(arg)
1718
1719// Access to RTM instructions
1720/*A version of XBegin which returns -1 on speculation, and the value of EAX on
1721 an abort. This is the same definition as the compiler intrinsic that will be
1722 supported at some point. */
1723static __inline int _xbegin() {
1724 int res = -1;
1725
1726#if KMP_OS_WINDOWS
1727#if KMP_ARCH_X86_64
1728 _asm {
1729 _emit 0xC7
1730 _emit 0xF8
1731 _emit 2
1732 _emit 0
1733 _emit 0
1734 _emit 0
1735 jmp L2
1736 mov res, eax
1737 L2:
1738 }
1739#else /* IA32 */
1740 _asm {
1741 _emit 0xC7
1742 _emit 0xF8
1743 _emit 2
1744 _emit 0
1745 _emit 0
1746 _emit 0
1747 jmp L2
1748 mov res, eax
1749 L2:
1750 }
1751#endif // KMP_ARCH_X86_64
1752#else
1753 /* Note that %eax must be noted as killed (clobbered), because the XSR is
1754 returned in %eax(%rax) on abort. Other register values are restored, so
1755 don't need to be killed.
1756
1757 We must also mark 'res' as an input and an output, since otherwise
1758 'res=-1' may be dropped as being dead, whereas we do need the assignment on
1759 the successful (i.e., non-abort) path. */
1760 __asm__ volatile("1: .byte 0xC7; .byte 0xF8;\n"
1761 " .long 1f-1b-6\n"
1762 " jmp 2f\n"
1763 "1: movl %%eax,%0\n"
1764 "2:"
1765 : "+r"(res)::"memory", "%eax");
1766#endif // KMP_OS_WINDOWS
1767 return res;
1768}
1769
1770/* Transaction end */
1771static __inline void _xend() {
1772#if KMP_OS_WINDOWS
1773 __asm {
1774 _emit 0x0f
1775 _emit 0x01
1776 _emit 0xd5
1777 }
1778#else
1779 __asm__ volatile(".byte 0x0f; .byte 0x01; .byte 0xd5" ::: "memory");
1780#endif
1781}
1782
1783/* This is a macro, the argument must be a single byte constant which can be
1784 evaluated by the inline assembler, since it is emitted as a byte into the
1785 assembly code. */
1786// clang-format off
1787#if KMP_OS_WINDOWS
1788#define _xabort(ARG) _asm _emit 0xc6 _asm _emit 0xf8 _asm _emit ARG
1789#else
1790#define _xabort(ARG) \
1791 __asm__ volatile(".byte 0xC6; .byte 0xF8; .byte " STRINGIZE(ARG):::"memory");
1792#endif
1793// clang-format on
1794#endif // KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300
1795
1796// Statistics is collected for testing purpose
1797#if KMP_DEBUG_ADAPTIVE_LOCKS
1798
1799// We accumulate speculative lock statistics when the lock is destroyed. We
1800// keep locks that haven't been destroyed in the liveLocks list so that we can
1801// grab their statistics too.
1802static kmp_adaptive_lock_statistics_t destroyedStats;
1803
1804// To hold the list of live locks.
1805static kmp_adaptive_lock_info_t liveLocks;
1806
1807// A lock so we can safely update the list of locks.
1808static kmp_bootstrap_lock_t chain_lock =
1809 KMP_BOOTSTRAP_LOCK_INITIALIZER(chain_lock);
1810
1811// Initialize the list of stats.
1812void __kmp_init_speculative_stats() {
1813 kmp_adaptive_lock_info_t *lck = &liveLocks;
1814
1815 memset(CCAST(kmp_adaptive_lock_statistics_t *, &(lck->stats)), 0,
1816 sizeof(lck->stats));
1817 lck->stats.next = lck;
1818 lck->stats.prev = lck;
1819
1820 KMP_ASSERT(lck->stats.next->stats.prev == lck);
1821 KMP_ASSERT(lck->stats.prev->stats.next == lck);
1822
1823 __kmp_init_bootstrap_lock(&chain_lock);
1824}
1825
1826// Insert the lock into the circular list
1827static void __kmp_remember_lock(kmp_adaptive_lock_info_t *lck) {
1828 __kmp_acquire_bootstrap_lock(&chain_lock);
1829
1830 lck->stats.next = liveLocks.stats.next;
1831 lck->stats.prev = &liveLocks;
1832
1833 liveLocks.stats.next = lck;
1834 lck->stats.next->stats.prev = lck;
1835
1836 KMP_ASSERT(lck->stats.next->stats.prev == lck);
1837 KMP_ASSERT(lck->stats.prev->stats.next == lck);
1838
1839 __kmp_release_bootstrap_lock(&chain_lock);
1840}
1841
1842static void __kmp_forget_lock(kmp_adaptive_lock_info_t *lck) {
1843 KMP_ASSERT(lck->stats.next->stats.prev == lck);
1844 KMP_ASSERT(lck->stats.prev->stats.next == lck);
1845
1846 kmp_adaptive_lock_info_t *n = lck->stats.next;
1847 kmp_adaptive_lock_info_t *p = lck->stats.prev;
1848
1849 n->stats.prev = p;
1850 p->stats.next = n;
1851}
1852
1853static void __kmp_zero_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1854 memset(CCAST(kmp_adaptive_lock_statistics_t *, &lck->stats), 0,
1855 sizeof(lck->stats));
1856 __kmp_remember_lock(lck);
1857}
1858
1859static void __kmp_add_stats(kmp_adaptive_lock_statistics_t *t,
1860 kmp_adaptive_lock_info_t *lck) {
1861 kmp_adaptive_lock_statistics_t volatile *s = &lck->stats;
1862
1863 t->nonSpeculativeAcquireAttempts += lck->acquire_attempts;
1864 t->successfulSpeculations += s->successfulSpeculations;
1865 t->hardFailedSpeculations += s->hardFailedSpeculations;
1866 t->softFailedSpeculations += s->softFailedSpeculations;
1867 t->nonSpeculativeAcquires += s->nonSpeculativeAcquires;
1868 t->lemmingYields += s->lemmingYields;
1869}
1870
1871static void __kmp_accumulate_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1872 __kmp_acquire_bootstrap_lock(&chain_lock);
1873
1874 __kmp_add_stats(&destroyedStats, lck);
1875 __kmp_forget_lock(lck);
1876
1877 __kmp_release_bootstrap_lock(&chain_lock);
1878}
1879
1880static float percent(kmp_uint32 count, kmp_uint32 total) {
1881 return (total == 0) ? 0.0 : (100.0 * count) / total;
1882}
1883
1884void __kmp_print_speculative_stats() {
1885 kmp_adaptive_lock_statistics_t total = destroyedStats;
1886 kmp_adaptive_lock_info_t *lck;
1887
1888 for (lck = liveLocks.stats.next; lck != &liveLocks; lck = lck->stats.next) {
1889 __kmp_add_stats(&total, lck);
1890 }
1891 kmp_adaptive_lock_statistics_t *t = &total;
1892 kmp_uint32 totalSections =
1893 t->nonSpeculativeAcquires + t->successfulSpeculations;
1894 kmp_uint32 totalSpeculations = t->successfulSpeculations +
1895 t->hardFailedSpeculations +
1896 t->softFailedSpeculations;
1897 if (totalSections <= 0)
1898 return;
1899
1900 kmp_safe_raii_file_t statsFile;
1901 if (strcmp(__kmp_speculative_statsfile, "-") == 0) {
1902 statsFile.set_stdout();
1903 } else {
1904 size_t buffLen = KMP_STRLEN(__kmp_speculative_statsfile) + 20;
1905 char buffer[buffLen];
1906 KMP_SNPRINTF(&buffer[0], buffLen, __kmp_speculative_statsfile,
1907 (kmp_int32)getpid());
1908 statsFile.open(buffer, "w");
1909 }
1910
1911 fprintf(statsFile, "Speculative lock statistics (all approximate!)\n");
1912 fprintf(statsFile,
1913 " Lock parameters: \n"
1914 " max_soft_retries : %10d\n"
1915 " max_badness : %10d\n",
1916 __kmp_adaptive_backoff_params.max_soft_retries,
1917 __kmp_adaptive_backoff_params.max_badness);
1918 fprintf(statsFile, " Non-speculative acquire attempts : %10d\n",
1919 t->nonSpeculativeAcquireAttempts);
1920 fprintf(statsFile, " Total critical sections : %10d\n",
1921 totalSections);
1922 fprintf(statsFile, " Successful speculations : %10d (%5.1f%%)\n",
1923 t->successfulSpeculations,
1924 percent(t->successfulSpeculations, totalSections));
1925 fprintf(statsFile, " Non-speculative acquires : %10d (%5.1f%%)\n",
1926 t->nonSpeculativeAcquires,
1927 percent(t->nonSpeculativeAcquires, totalSections));
1928 fprintf(statsFile, " Lemming yields : %10d\n\n",
1929 t->lemmingYields);
1930
1931 fprintf(statsFile, " Speculative acquire attempts : %10d\n",
1932 totalSpeculations);
1933 fprintf(statsFile, " Successes : %10d (%5.1f%%)\n",
1934 t->successfulSpeculations,
1935 percent(t->successfulSpeculations, totalSpeculations));
1936 fprintf(statsFile, " Soft failures : %10d (%5.1f%%)\n",
1937 t->softFailedSpeculations,
1938 percent(t->softFailedSpeculations, totalSpeculations));
1939 fprintf(statsFile, " Hard failures : %10d (%5.1f%%)\n",
1940 t->hardFailedSpeculations,
1941 percent(t->hardFailedSpeculations, totalSpeculations));
1942}
1943
1944#define KMP_INC_STAT(lck, stat) (lck->lk.adaptive.stats.stat++)
1945#else
1946#define KMP_INC_STAT(lck, stat)
1947
1948#endif // KMP_DEBUG_ADAPTIVE_LOCKS
1949
1950static inline bool __kmp_is_unlocked_queuing_lock(kmp_queuing_lock_t *lck) {
1951 // It is enough to check that the head_id is zero.
1952 // We don't also need to check the tail.
1953 bool res = lck->lk.head_id == 0;
1954
1955// We need a fence here, since we must ensure that no memory operations
1956// from later in this thread float above that read.
1957#if KMP_COMPILER_ICC
1958 _mm_mfence();
1959#else
1960 __sync_synchronize();
1961#endif
1962
1963 return res;
1964}
1965
1966// Functions for manipulating the badness
1967static __inline void
1968__kmp_update_badness_after_success(kmp_adaptive_lock_t *lck) {
1969 // Reset the badness to zero so we eagerly try to speculate again
1970 lck->lk.adaptive.badness = 0;
1971 KMP_INC_STAT(lck, successfulSpeculations);
1972}
1973
1974// Create a bit mask with one more set bit.
1975static __inline void __kmp_step_badness(kmp_adaptive_lock_t *lck) {
1976 kmp_uint32 newBadness = (lck->lk.adaptive.badness << 1) | 1;
1977 if (newBadness > lck->lk.adaptive.max_badness) {
1978 return;
1979 } else {
1980 lck->lk.adaptive.badness = newBadness;
1981 }
1982}
1983
1984// Check whether speculation should be attempted.
1985KMP_ATTRIBUTE_TARGET_RTM
1986static __inline int __kmp_should_speculate(kmp_adaptive_lock_t *lck,
1987 kmp_int32 gtid) {
1988 kmp_uint32 badness = lck->lk.adaptive.badness;
1989 kmp_uint32 attempts = lck->lk.adaptive.acquire_attempts;
1990 int res = (attempts & badness) == 0;
1991 return res;
1992}
1993
1994// Attempt to acquire only the speculative lock.
1995// Does not back off to the non-speculative lock.
1996KMP_ATTRIBUTE_TARGET_RTM
1997static int __kmp_test_adaptive_lock_only(kmp_adaptive_lock_t *lck,
1998 kmp_int32 gtid) {
1999 int retries = lck->lk.adaptive.max_soft_retries;
2000
2001 // We don't explicitly count the start of speculation, rather we record the
2002 // results (success, hard fail, soft fail). The sum of all of those is the
2003 // total number of times we started speculation since all speculations must
2004 // end one of those ways.
2005 do