LLVM OpenMP* Runtime Library
kmp_lock.h
1 /*
2  * kmp_lock.h -- lock header file
3  */
4 
5 
6 //===----------------------------------------------------------------------===//
7 //
8 // The LLVM Compiler Infrastructure
9 //
10 // This file is dual licensed under the MIT and the University of Illinois Open
11 // Source Licenses. See LICENSE.txt for details.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 
16 #ifndef KMP_LOCK_H
17 #define KMP_LOCK_H
18 
19 #include <limits.h> // CHAR_BIT
20 #include <stddef.h> // offsetof
21 
22 #include "kmp_os.h"
23 #include "kmp_debug.h"
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif // __cplusplus
28 
29 // ----------------------------------------------------------------------------
30 // Have to copy these definitions from kmp.h because kmp.h cannot be included
31 // due to circular dependencies. Will undef these at end of file.
32 
33 #define KMP_PAD(type, sz) (sizeof(type) + (sz - ((sizeof(type) - 1) % (sz)) - 1))
34 #define KMP_GTID_DNE (-2)
35 
36 // Forward declaration of ident and ident_t
37 
38 struct ident;
39 typedef struct ident ident_t;
40 
41 // End of copied code.
42 // ----------------------------------------------------------------------------
43 
44 //
45 // We need to know the size of the area we can assume that the compiler(s)
46 // allocated for obects of type omp_lock_t and omp_nest_lock_t. The Intel
47 // compiler always allocates a pointer-sized area, as does visual studio.
48 //
49 // gcc however, only allocates 4 bytes for regular locks, even on 64-bit
50 // intel archs. It allocates at least 8 bytes for nested lock (more on
51 // recent versions), but we are bounded by the pointer-sized chunks that
52 // the Intel compiler allocates.
53 //
54 
55 #if KMP_OS_LINUX && defined(KMP_GOMP_COMPAT)
56 # define OMP_LOCK_T_SIZE sizeof(int)
57 # define OMP_NEST_LOCK_T_SIZE sizeof(void *)
58 #else
59 # define OMP_LOCK_T_SIZE sizeof(void *)
60 # define OMP_NEST_LOCK_T_SIZE sizeof(void *)
61 #endif
62 
63 //
64 // The Intel compiler allocates a 32-byte chunk for a critical section.
65 // Both gcc and visual studio only allocate enough space for a pointer.
66 // Sometimes we know that the space was allocated by the Intel compiler.
67 //
68 #define OMP_CRITICAL_SIZE sizeof(void *)
69 #define INTEL_CRITICAL_SIZE 32
70 
71 //
72 // lock flags
73 //
74 typedef kmp_uint32 kmp_lock_flags_t;
75 
76 #define kmp_lf_critical_section 1
77 
78 //
79 // When a lock table is used, the indices are of kmp_lock_index_t
80 //
81 typedef kmp_uint32 kmp_lock_index_t;
82 
83 //
84 // When memory allocated for locks are on the lock pool (free list),
85 // it is treated as structs of this type.
86 //
87 struct kmp_lock_pool {
88  union kmp_user_lock *next;
89  kmp_lock_index_t index;
90 };
91 
92 typedef struct kmp_lock_pool kmp_lock_pool_t;
93 
94 
95 extern void __kmp_validate_locks( void );
96 
97 
98 // ----------------------------------------------------------------------------
99 //
100 // There are 5 lock implementations:
101 //
102 // 1. Test and set locks.
103 // 2. futex locks (Linux* OS on x86 and Intel(R) Many Integrated Core architecture)
104 // 3. Ticket (Lamport bakery) locks.
105 // 4. Queuing locks (with separate spin fields).
106 // 5. DRPA (Dynamically Reconfigurable Distributed Polling Area) locks
107 //
108 // and 3 lock purposes:
109 //
110 // 1. Bootstrap locks -- Used for a few locks available at library startup-shutdown time.
111 // These do not require non-negative global thread ID's.
112 // 2. Internal RTL locks -- Used everywhere else in the RTL
113 // 3. User locks (includes critical sections)
114 //
115 // ----------------------------------------------------------------------------
116 
117 
118 // ============================================================================
119 // Lock implementations.
120 // ============================================================================
121 
122 
123 // ----------------------------------------------------------------------------
124 // Test and set locks.
125 //
126 // Non-nested test and set locks differ from the other lock kinds (except
127 // futex) in that we use the memory allocated by the compiler for the lock,
128 // rather than a pointer to it.
129 //
130 // On lin32, lin_32e, and win_32, the space allocated may be as small as 4
131 // bytes, so we have to use a lock table for nested locks, and avoid accessing
132 // the depth_locked field for non-nested locks.
133 //
134 // Information normally available to the tools, such as lock location,
135 // lock usage (normal lock vs. critical section), etc. is not available with
136 // test and set locks.
137 // ----------------------------------------------------------------------------
138 
139 struct kmp_base_tas_lock {
140  volatile kmp_int32 poll; // 0 => unlocked
141  // locked: (gtid+1) of owning thread
142  kmp_int32 depth_locked; // depth locked, for nested locks only
143 };
144 
145 typedef struct kmp_base_tas_lock kmp_base_tas_lock_t;
146 
147 union kmp_tas_lock {
148  kmp_base_tas_lock_t lk;
149  kmp_lock_pool_t pool; // make certain struct is large enough
150  double lk_align; // use worst case alignment
151  // no cache line padding
152 };
153 
154 typedef union kmp_tas_lock kmp_tas_lock_t;
155 
156 //
157 // Static initializer for test and set lock variables. Usage:
158 // kmp_tas_lock_t xlock = KMP_TAS_LOCK_INITIALIZER( xlock );
159 //
160 #define KMP_TAS_LOCK_INITIALIZER( lock ) { { 0, 0 } }
161 
162 extern void __kmp_acquire_tas_lock( kmp_tas_lock_t *lck, kmp_int32 gtid );
163 extern int __kmp_test_tas_lock( kmp_tas_lock_t *lck, kmp_int32 gtid );
164 extern int __kmp_release_tas_lock( kmp_tas_lock_t *lck, kmp_int32 gtid );
165 extern void __kmp_init_tas_lock( kmp_tas_lock_t *lck );
166 extern void __kmp_destroy_tas_lock( kmp_tas_lock_t *lck );
167 
168 extern void __kmp_acquire_nested_tas_lock( kmp_tas_lock_t *lck, kmp_int32 gtid );
169 extern int __kmp_test_nested_tas_lock( kmp_tas_lock_t *lck, kmp_int32 gtid );
170 extern int __kmp_release_nested_tas_lock( kmp_tas_lock_t *lck, kmp_int32 gtid );
171 extern void __kmp_init_nested_tas_lock( kmp_tas_lock_t *lck );
172 extern void __kmp_destroy_nested_tas_lock( kmp_tas_lock_t *lck );
173 
174 #define KMP_LOCK_RELEASED 1
175 #define KMP_LOCK_STILL_HELD 0
176 
177 
178 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
179 
180 // ----------------------------------------------------------------------------
181 // futex locks. futex locks are only available on Linux* OS.
182 //
183 // Like non-nested test and set lock, non-nested futex locks use the memory
184 // allocated by the compiler for the lock, rather than a pointer to it.
185 //
186 // Information normally available to the tools, such as lock location,
187 // lock usage (normal lock vs. critical section), etc. is not available with
188 // test and set locks. With non-nested futex locks, the lock owner is not
189 // even available.
190 // ----------------------------------------------------------------------------
191 
192 struct kmp_base_futex_lock {
193  volatile kmp_int32 poll; // 0 => unlocked
194  // 2*(gtid+1) of owning thread, 0 if unlocked
195  // locked: (gtid+1) of owning thread
196  kmp_int32 depth_locked; // depth locked, for nested locks only
197 };
198 
199 typedef struct kmp_base_futex_lock kmp_base_futex_lock_t;
200 
201 union kmp_futex_lock {
202  kmp_base_futex_lock_t lk;
203  kmp_lock_pool_t pool; // make certain struct is large enough
204  double lk_align; // use worst case alignment
205  // no cache line padding
206 };
207 
208 typedef union kmp_futex_lock kmp_futex_lock_t;
209 
210 //
211 // Static initializer for futex lock variables. Usage:
212 // kmp_futex_lock_t xlock = KMP_FUTEX_LOCK_INITIALIZER( xlock );
213 //
214 #define KMP_FUTEX_LOCK_INITIALIZER( lock ) { { 0, 0 } }
215 
216 extern void __kmp_acquire_futex_lock( kmp_futex_lock_t *lck, kmp_int32 gtid );
217 extern int __kmp_test_futex_lock( kmp_futex_lock_t *lck, kmp_int32 gtid );
218 extern int __kmp_release_futex_lock( kmp_futex_lock_t *lck, kmp_int32 gtid );
219 extern void __kmp_init_futex_lock( kmp_futex_lock_t *lck );
220 extern void __kmp_destroy_futex_lock( kmp_futex_lock_t *lck );
221 
222 extern void __kmp_acquire_nested_futex_lock( kmp_futex_lock_t *lck, kmp_int32 gtid );
223 extern int __kmp_test_nested_futex_lock( kmp_futex_lock_t *lck, kmp_int32 gtid );
224 extern int __kmp_release_nested_futex_lock( kmp_futex_lock_t *lck, kmp_int32 gtid );
225 extern void __kmp_init_nested_futex_lock( kmp_futex_lock_t *lck );
226 extern void __kmp_destroy_nested_futex_lock( kmp_futex_lock_t *lck );
227 
228 #endif // KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
229 
230 
231 // ----------------------------------------------------------------------------
232 // Ticket locks.
233 // ----------------------------------------------------------------------------
234 
235 struct kmp_base_ticket_lock {
236  // `initialized' must be the first entry in the lock data structure!
237  volatile union kmp_ticket_lock * initialized; // points to the lock union if in initialized state
238  ident_t const * location; // Source code location of omp_init_lock().
239  volatile kmp_uint32 next_ticket; // ticket number to give to next thread which acquires
240  volatile kmp_uint32 now_serving; // ticket number for thread which holds the lock
241  volatile kmp_int32 owner_id; // (gtid+1) of owning thread, 0 if unlocked
242  kmp_int32 depth_locked; // depth locked, for nested locks only
243  kmp_lock_flags_t flags; // lock specifics, e.g. critical section lock
244 };
245 
246 typedef struct kmp_base_ticket_lock kmp_base_ticket_lock_t;
247 
248 union KMP_ALIGN_CACHE kmp_ticket_lock {
249  kmp_base_ticket_lock_t lk; // This field must be first to allow static initializing.
250  kmp_lock_pool_t pool;
251  double lk_align; // use worst case alignment
252  char lk_pad[ KMP_PAD( kmp_base_ticket_lock_t, CACHE_LINE ) ];
253 };
254 
255 typedef union kmp_ticket_lock kmp_ticket_lock_t;
256 
257 //
258 // Static initializer for simple ticket lock variables. Usage:
259 // kmp_ticket_lock_t xlock = KMP_TICKET_LOCK_INITIALIZER( xlock );
260 // Note the macro argument. It is important to make var properly initialized.
261 //
262 #define KMP_TICKET_LOCK_INITIALIZER( lock ) { { (kmp_ticket_lock_t *) & (lock), NULL, 0, 0, 0, -1 } }
263 
264 extern void __kmp_acquire_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
265 extern int __kmp_test_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
266 extern int __kmp_test_ticket_lock_with_cheks( kmp_ticket_lock_t *lck, kmp_int32 gtid );
267 extern int __kmp_release_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
268 extern void __kmp_init_ticket_lock( kmp_ticket_lock_t *lck );
269 extern void __kmp_destroy_ticket_lock( kmp_ticket_lock_t *lck );
270 
271 extern void __kmp_acquire_nested_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
272 extern int __kmp_test_nested_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
273 extern int __kmp_release_nested_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
274 extern void __kmp_init_nested_ticket_lock( kmp_ticket_lock_t *lck );
275 extern void __kmp_destroy_nested_ticket_lock( kmp_ticket_lock_t *lck );
276 
277 
278 // ----------------------------------------------------------------------------
279 // Queuing locks.
280 // ----------------------------------------------------------------------------
281 
282 #if KMP_USE_ADAPTIVE_LOCKS
283 
284 struct kmp_adaptive_lock_info;
285 
286 typedef struct kmp_adaptive_lock_info kmp_adaptive_lock_info_t;
287 
288 #if KMP_DEBUG_ADAPTIVE_LOCKS
289 
290 struct kmp_adaptive_lock_statistics {
291  /* So we can get stats from locks that haven't been destroyed. */
292  kmp_adaptive_lock_info_t * next;
293  kmp_adaptive_lock_info_t * prev;
294 
295  /* Other statistics */
296  kmp_uint32 successfulSpeculations;
297  kmp_uint32 hardFailedSpeculations;
298  kmp_uint32 softFailedSpeculations;
299  kmp_uint32 nonSpeculativeAcquires;
300  kmp_uint32 nonSpeculativeAcquireAttempts;
301  kmp_uint32 lemmingYields;
302 };
303 
304 typedef struct kmp_adaptive_lock_statistics kmp_adaptive_lock_statistics_t;
305 
306 extern void __kmp_print_speculative_stats();
307 extern void __kmp_init_speculative_stats();
308 
309 #endif // KMP_DEBUG_ADAPTIVE_LOCKS
310 
311 struct kmp_adaptive_lock_info
312 {
313  /* Values used for adaptivity.
314  * Although these are accessed from multiple threads we don't access them atomically,
315  * because if we miss updates it probably doesn't matter much. (It just affects our
316  * decision about whether to try speculation on the lock).
317  */
318  kmp_uint32 volatile badness;
319  kmp_uint32 volatile acquire_attempts;
320  /* Parameters of the lock. */
321  kmp_uint32 max_badness;
322  kmp_uint32 max_soft_retries;
323 
324 #if KMP_DEBUG_ADAPTIVE_LOCKS
325  kmp_adaptive_lock_statistics_t volatile stats;
326 #endif
327 };
328 
329 #endif // KMP_USE_ADAPTIVE_LOCKS
330 
331 
332 struct kmp_base_queuing_lock {
333 
334  // `initialized' must be the first entry in the lock data structure!
335  volatile union kmp_queuing_lock *initialized; // Points to the lock union if in initialized state.
336 
337  ident_t const * location; // Source code location of omp_init_lock().
338 
339  KMP_ALIGN( 8 ) // tail_id must be 8-byte aligned!
340 
341  volatile kmp_int32 tail_id; // (gtid+1) of thread at tail of wait queue, 0 if empty
342  // Must be no padding here since head/tail used in 8-byte CAS
343  volatile kmp_int32 head_id; // (gtid+1) of thread at head of wait queue, 0 if empty
344  // Decl order assumes little endian
345  // bakery-style lock
346  volatile kmp_uint32 next_ticket; // ticket number to give to next thread which acquires
347  volatile kmp_uint32 now_serving; // ticket number for thread which holds the lock
348  volatile kmp_int32 owner_id; // (gtid+1) of owning thread, 0 if unlocked
349  kmp_int32 depth_locked; // depth locked, for nested locks only
350 
351  kmp_lock_flags_t flags; // lock specifics, e.g. critical section lock
352 };
353 
354 typedef struct kmp_base_queuing_lock kmp_base_queuing_lock_t;
355 
356 KMP_BUILD_ASSERT( offsetof( kmp_base_queuing_lock_t, tail_id ) % 8 == 0 );
357 
358 union KMP_ALIGN_CACHE kmp_queuing_lock {
359  kmp_base_queuing_lock_t lk; // This field must be first to allow static initializing.
360  kmp_lock_pool_t pool;
361  double lk_align; // use worst case alignment
362  char lk_pad[ KMP_PAD( kmp_base_queuing_lock_t, CACHE_LINE ) ];
363 };
364 
365 typedef union kmp_queuing_lock kmp_queuing_lock_t;
366 
367 extern void __kmp_acquire_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid );
368 extern int __kmp_test_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid );
369 extern int __kmp_release_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid );
370 extern void __kmp_init_queuing_lock( kmp_queuing_lock_t *lck );
371 extern void __kmp_destroy_queuing_lock( kmp_queuing_lock_t *lck );
372 
373 extern void __kmp_acquire_nested_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid );
374 extern int __kmp_test_nested_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid );
375 extern int __kmp_release_nested_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid );
376 extern void __kmp_init_nested_queuing_lock( kmp_queuing_lock_t *lck );
377 extern void __kmp_destroy_nested_queuing_lock( kmp_queuing_lock_t *lck );
378 
379 #if KMP_USE_ADAPTIVE_LOCKS
380 
381 // ----------------------------------------------------------------------------
382 // Adaptive locks.
383 // ----------------------------------------------------------------------------
384 struct kmp_base_adaptive_lock {
385  kmp_base_queuing_lock qlk;
386  KMP_ALIGN(CACHE_LINE)
387  kmp_adaptive_lock_info_t adaptive; // Information for the speculative adaptive lock
388 };
389 
390 typedef struct kmp_base_adaptive_lock kmp_base_adaptive_lock_t;
391 
392 union KMP_ALIGN_CACHE kmp_adaptive_lock {
393  kmp_base_adaptive_lock_t lk;
394  kmp_lock_pool_t pool;
395  double lk_align;
396  char lk_pad[ KMP_PAD(kmp_base_adaptive_lock_t, CACHE_LINE) ];
397 };
398 typedef union kmp_adaptive_lock kmp_adaptive_lock_t;
399 
400 # define GET_QLK_PTR(l) ((kmp_queuing_lock_t *) & (l)->lk.qlk)
401 
402 #endif // KMP_USE_ADAPTIVE_LOCKS
403 
404 // ----------------------------------------------------------------------------
405 // DRDPA ticket locks.
406 // ----------------------------------------------------------------------------
407 
408 struct kmp_base_drdpa_lock {
409  //
410  // All of the fields on the first cache line are only written when
411  // initializing or reconfiguring the lock. These are relatively rare
412  // operations, so data from the first cache line will usually stay
413  // resident in the cache of each thread trying to acquire the lock.
414  //
415  // initialized must be the first entry in the lock data structure!
416  //
417  KMP_ALIGN_CACHE
418 
419  volatile union kmp_drdpa_lock * initialized; // points to the lock union if in initialized state
420  ident_t const * location; // Source code location of omp_init_lock().
421  volatile struct kmp_lock_poll {
422  kmp_uint64 poll;
423  } * volatile polls;
424  volatile kmp_uint64 mask; // is 2**num_polls-1 for mod op
425  kmp_uint64 cleanup_ticket; // thread with cleanup ticket
426  volatile struct kmp_lock_poll * old_polls; // will deallocate old_polls
427  kmp_uint32 num_polls; // must be power of 2
428 
429  //
430  // next_ticket it needs to exist in a separate cache line, as it is
431  // invalidated every time a thread takes a new ticket.
432  //
433  KMP_ALIGN_CACHE
434 
435  volatile kmp_uint64 next_ticket;
436 
437  //
438  // now_serving is used to store our ticket value while we hold the lock.
439  // It has a slightly different meaning in the DRDPA ticket locks (where
440  // it is written by the acquiring thread) than it does in the simple
441  // ticket locks (where it is written by the releasing thread).
442  //
443  // Since now_serving is only read an written in the critical section,
444  // it is non-volatile, but it needs to exist on a separate cache line,
445  // as it is invalidated at every lock acquire.
446  //
447  // Likewise, the vars used for nested locks (owner_id and depth_locked)
448  // are only written by the thread owning the lock, so they are put in
449  // this cache line. owner_id is read by other threads, so it must be
450  // declared volatile.
451  //
452  KMP_ALIGN_CACHE
453 
454  kmp_uint64 now_serving; // doesn't have to be volatile
455  volatile kmp_uint32 owner_id; // (gtid+1) of owning thread, 0 if unlocked
456  kmp_int32 depth_locked; // depth locked
457  kmp_lock_flags_t flags; // lock specifics, e.g. critical section lock
458 };
459 
460 typedef struct kmp_base_drdpa_lock kmp_base_drdpa_lock_t;
461 
462 union KMP_ALIGN_CACHE kmp_drdpa_lock {
463  kmp_base_drdpa_lock_t lk; // This field must be first to allow static initializing. */
464  kmp_lock_pool_t pool;
465  double lk_align; // use worst case alignment
466  char lk_pad[ KMP_PAD( kmp_base_drdpa_lock_t, CACHE_LINE ) ];
467 };
468 
469 typedef union kmp_drdpa_lock kmp_drdpa_lock_t;
470 
471 extern void __kmp_acquire_drdpa_lock( kmp_drdpa_lock_t *lck, kmp_int32 gtid );
472 extern int __kmp_test_drdpa_lock( kmp_drdpa_lock_t *lck, kmp_int32 gtid );
473 extern int __kmp_release_drdpa_lock( kmp_drdpa_lock_t *lck, kmp_int32 gtid );
474 extern void __kmp_init_drdpa_lock( kmp_drdpa_lock_t *lck );
475 extern void __kmp_destroy_drdpa_lock( kmp_drdpa_lock_t *lck );
476 
477 extern void __kmp_acquire_nested_drdpa_lock( kmp_drdpa_lock_t *lck, kmp_int32 gtid );
478 extern int __kmp_test_nested_drdpa_lock( kmp_drdpa_lock_t *lck, kmp_int32 gtid );
479 extern int __kmp_release_nested_drdpa_lock( kmp_drdpa_lock_t *lck, kmp_int32 gtid );
480 extern void __kmp_init_nested_drdpa_lock( kmp_drdpa_lock_t *lck );
481 extern void __kmp_destroy_nested_drdpa_lock( kmp_drdpa_lock_t *lck );
482 
483 
484 // ============================================================================
485 // Lock purposes.
486 // ============================================================================
487 
488 
489 // ----------------------------------------------------------------------------
490 // Bootstrap locks.
491 // ----------------------------------------------------------------------------
492 
493 // Bootstrap locks -- very few locks used at library initialization time.
494 // Bootstrap locks are currently implemented as ticket locks.
495 // They could also be implemented as test and set lock, but cannot be
496 // implemented with other lock kinds as they require gtids which are not
497 // available at initialization time.
498 
499 typedef kmp_ticket_lock_t kmp_bootstrap_lock_t;
500 
501 #define KMP_BOOTSTRAP_LOCK_INITIALIZER( lock ) KMP_TICKET_LOCK_INITIALIZER( (lock) )
502 
503 static inline void
504 __kmp_acquire_bootstrap_lock( kmp_bootstrap_lock_t *lck )
505 {
506  __kmp_acquire_ticket_lock( lck, KMP_GTID_DNE );
507 }
508 
509 static inline int
510 __kmp_test_bootstrap_lock( kmp_bootstrap_lock_t *lck )
511 {
512  return __kmp_test_ticket_lock( lck, KMP_GTID_DNE );
513 }
514 
515 static inline void
516 __kmp_release_bootstrap_lock( kmp_bootstrap_lock_t *lck )
517 {
518  __kmp_release_ticket_lock( lck, KMP_GTID_DNE );
519 }
520 
521 static inline void
522 __kmp_init_bootstrap_lock( kmp_bootstrap_lock_t *lck )
523 {
524  __kmp_init_ticket_lock( lck );
525 }
526 
527 static inline void
528 __kmp_destroy_bootstrap_lock( kmp_bootstrap_lock_t *lck )
529 {
530  __kmp_destroy_ticket_lock( lck );
531 }
532 
533 
534 // ----------------------------------------------------------------------------
535 // Internal RTL locks.
536 // ----------------------------------------------------------------------------
537 
538 //
539 // Internal RTL locks are also implemented as ticket locks, for now.
540 //
541 // FIXME - We should go through and figure out which lock kind works best for
542 // each internal lock, and use the type declaration and function calls for
543 // that explicit lock kind (and get rid of this section).
544 //
545 
546 typedef kmp_ticket_lock_t kmp_lock_t;
547 
548 static inline void
549 __kmp_acquire_lock( kmp_lock_t *lck, kmp_int32 gtid )
550 {
551  __kmp_acquire_ticket_lock( lck, gtid );
552 }
553 
554 static inline int
555 __kmp_test_lock( kmp_lock_t *lck, kmp_int32 gtid )
556 {
557  return __kmp_test_ticket_lock( lck, gtid );
558 }
559 
560 static inline void
561 __kmp_release_lock( kmp_lock_t *lck, kmp_int32 gtid )
562 {
563  __kmp_release_ticket_lock( lck, gtid );
564 }
565 
566 static inline void
567 __kmp_init_lock( kmp_lock_t *lck )
568 {
569  __kmp_init_ticket_lock( lck );
570 }
571 
572 static inline void
573 __kmp_destroy_lock( kmp_lock_t *lck )
574 {
575  __kmp_destroy_ticket_lock( lck );
576 }
577 
578 
579 // ----------------------------------------------------------------------------
580 // User locks.
581 // ----------------------------------------------------------------------------
582 
583 //
584 // Do not allocate objects of type union kmp_user_lock!!!
585 // This will waste space unless __kmp_user_lock_kind == lk_drdpa.
586 // Instead, check the value of __kmp_user_lock_kind and allocate objects of
587 // the type of the appropriate union member, and cast their addresses to
588 // kmp_user_lock_p.
589 //
590 
591 enum kmp_lock_kind {
592  lk_default = 0,
593  lk_tas,
594 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
595  lk_futex,
596 #endif
597  lk_ticket,
598  lk_queuing,
599  lk_drdpa,
600 #if KMP_USE_ADAPTIVE_LOCKS
601  lk_adaptive
602 #endif // KMP_USE_ADAPTIVE_LOCKS
603 };
604 
605 typedef enum kmp_lock_kind kmp_lock_kind_t;
606 
607 extern kmp_lock_kind_t __kmp_user_lock_kind;
608 
609 union kmp_user_lock {
610  kmp_tas_lock_t tas;
611 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
612  kmp_futex_lock_t futex;
613 #endif
614  kmp_ticket_lock_t ticket;
615  kmp_queuing_lock_t queuing;
616  kmp_drdpa_lock_t drdpa;
617 #if KMP_USE_ADAPTIVE_LOCKS
618  kmp_adaptive_lock_t adaptive;
619 #endif // KMP_USE_ADAPTIVE_LOCKS
620  kmp_lock_pool_t pool;
621 };
622 
623 typedef union kmp_user_lock *kmp_user_lock_p;
624 
625 #if ! KMP_USE_DYNAMIC_LOCK
626 
627 extern size_t __kmp_base_user_lock_size;
628 extern size_t __kmp_user_lock_size;
629 
630 extern kmp_int32 ( *__kmp_get_user_lock_owner_ )( kmp_user_lock_p lck );
631 
632 static inline kmp_int32
633 __kmp_get_user_lock_owner( kmp_user_lock_p lck )
634 {
635  KMP_DEBUG_ASSERT( __kmp_get_user_lock_owner_ != NULL );
636  return ( *__kmp_get_user_lock_owner_ )( lck );
637 }
638 
639 extern void ( *__kmp_acquire_user_lock_with_checks_ )( kmp_user_lock_p lck, kmp_int32 gtid );
640 
641 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
642 
643 #define __kmp_acquire_user_lock_with_checks(lck,gtid) \
644  if (__kmp_user_lock_kind == lk_tas) { \
645  if ( __kmp_env_consistency_check ) { \
646  char const * const func = "omp_set_lock"; \
647  if ( ( sizeof ( kmp_tas_lock_t ) <= OMP_LOCK_T_SIZE ) \
648  && lck->tas.lk.depth_locked != -1 ) { \
649  KMP_FATAL( LockNestableUsedAsSimple, func ); \
650  } \
651  if ( ( gtid >= 0 ) && ( lck->tas.lk.poll - 1 == gtid ) ) { \
652  KMP_FATAL( LockIsAlreadyOwned, func ); \
653  } \
654  } \
655  if ( ( lck->tas.lk.poll != 0 ) || \
656  ( ! KMP_COMPARE_AND_STORE_ACQ32( &(lck->tas.lk.poll), 0, gtid + 1 ) ) ) { \
657  kmp_uint32 spins; \
658  KMP_FSYNC_PREPARE( lck ); \
659  KMP_INIT_YIELD( spins ); \
660  if ( TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc) ) { \
661  KMP_YIELD( TRUE ); \
662  } else { \
663  KMP_YIELD_SPIN( spins ); \
664  } \
665  while ( ( lck->tas.lk.poll != 0 ) || \
666  ( ! KMP_COMPARE_AND_STORE_ACQ32( &(lck->tas.lk.poll), 0, gtid + 1 ) ) ) { \
667  if ( TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc) ) { \
668  KMP_YIELD( TRUE ); \
669  } else { \
670  KMP_YIELD_SPIN( spins ); \
671  } \
672  } \
673  } \
674  KMP_FSYNC_ACQUIRED( lck ); \
675  } else { \
676  KMP_DEBUG_ASSERT( __kmp_acquire_user_lock_with_checks_ != NULL ); \
677  ( *__kmp_acquire_user_lock_with_checks_ )( lck, gtid ); \
678  }
679 
680 #else
681 static inline void
682 __kmp_acquire_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
683 {
684  KMP_DEBUG_ASSERT( __kmp_acquire_user_lock_with_checks_ != NULL );
685  ( *__kmp_acquire_user_lock_with_checks_ )( lck, gtid );
686 }
687 #endif
688 
689 extern int ( *__kmp_test_user_lock_with_checks_ )( kmp_user_lock_p lck, kmp_int32 gtid );
690 
691 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
692 
693 #include "kmp_i18n.h" /* AC: KMP_FATAL definition */
694 extern int __kmp_env_consistency_check; /* AC: copy from kmp.h here */
695 static inline int
696 __kmp_test_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
697 {
698  if ( __kmp_user_lock_kind == lk_tas ) {
699  if ( __kmp_env_consistency_check ) {
700  char const * const func = "omp_test_lock";
701  if ( ( sizeof ( kmp_tas_lock_t ) <= OMP_LOCK_T_SIZE )
702  && lck->tas.lk.depth_locked != -1 ) {
703  KMP_FATAL( LockNestableUsedAsSimple, func );
704  }
705  }
706  return ( ( lck->tas.lk.poll == 0 ) &&
707  KMP_COMPARE_AND_STORE_ACQ32( &(lck->tas.lk.poll), 0, gtid + 1 ) );
708  } else {
709  KMP_DEBUG_ASSERT( __kmp_test_user_lock_with_checks_ != NULL );
710  return ( *__kmp_test_user_lock_with_checks_ )( lck, gtid );
711  }
712 }
713 #else
714 static inline int
715 __kmp_test_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
716 {
717  KMP_DEBUG_ASSERT( __kmp_test_user_lock_with_checks_ != NULL );
718  return ( *__kmp_test_user_lock_with_checks_ )( lck, gtid );
719 }
720 #endif
721 
722 extern int ( *__kmp_release_user_lock_with_checks_ )( kmp_user_lock_p lck, kmp_int32 gtid );
723 
724 static inline void
725 __kmp_release_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
726 {
727  KMP_DEBUG_ASSERT( __kmp_release_user_lock_with_checks_ != NULL );
728  ( *__kmp_release_user_lock_with_checks_ ) ( lck, gtid );
729 }
730 
731 extern void ( *__kmp_init_user_lock_with_checks_ )( kmp_user_lock_p lck );
732 
733 static inline void
734 __kmp_init_user_lock_with_checks( kmp_user_lock_p lck )
735 {
736  KMP_DEBUG_ASSERT( __kmp_init_user_lock_with_checks_ != NULL );
737  ( *__kmp_init_user_lock_with_checks_ )( lck );
738 }
739 
740 //
741 // We need a non-checking version of destroy lock for when the RTL is
742 // doing the cleanup as it can't always tell if the lock is nested or not.
743 //
744 extern void ( *__kmp_destroy_user_lock_ )( kmp_user_lock_p lck );
745 
746 static inline void
747 __kmp_destroy_user_lock( kmp_user_lock_p lck )
748 {
749  KMP_DEBUG_ASSERT( __kmp_destroy_user_lock_ != NULL );
750  ( *__kmp_destroy_user_lock_ )( lck );
751 }
752 
753 extern void ( *__kmp_destroy_user_lock_with_checks_ )( kmp_user_lock_p lck );
754 
755 static inline void
756 __kmp_destroy_user_lock_with_checks( kmp_user_lock_p lck )
757 {
758  KMP_DEBUG_ASSERT( __kmp_destroy_user_lock_with_checks_ != NULL );
759  ( *__kmp_destroy_user_lock_with_checks_ )( lck );
760 }
761 
762 extern void ( *__kmp_acquire_nested_user_lock_with_checks_ )( kmp_user_lock_p lck, kmp_int32 gtid );
763 
764 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64)
765 
766 #define __kmp_acquire_nested_user_lock_with_checks(lck,gtid) \
767  if (__kmp_user_lock_kind == lk_tas) { \
768  if ( __kmp_env_consistency_check ) { \
769  char const * const func = "omp_set_nest_lock"; \
770  if ( ( sizeof ( kmp_tas_lock_t ) <= OMP_NEST_LOCK_T_SIZE ) \
771  && lck->tas.lk.depth_locked == -1 ) { \
772  KMP_FATAL( LockSimpleUsedAsNestable, func ); \
773  } \
774  } \
775  if ( lck->tas.lk.poll - 1 == gtid ) { \
776  lck->tas.lk.depth_locked += 1; \
777  } else { \
778  if ( ( lck->tas.lk.poll != 0 ) || \
779  ( ! KMP_COMPARE_AND_STORE_ACQ32( &(lck->tas.lk.poll), 0, gtid + 1 ) ) ) { \
780  kmp_uint32 spins; \
781  KMP_FSYNC_PREPARE( lck ); \
782  KMP_INIT_YIELD( spins ); \
783  if ( TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc) ) { \
784  KMP_YIELD( TRUE ); \
785  } else { \
786  KMP_YIELD_SPIN( spins ); \
787  } \
788  while ( ( lck->tas.lk.poll != 0 ) || \
789  ( ! KMP_COMPARE_AND_STORE_ACQ32( &(lck->tas.lk.poll), 0, gtid + 1 ) ) ) { \
790  if ( TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc) ) { \
791  KMP_YIELD( TRUE ); \
792  } else { \
793  KMP_YIELD_SPIN( spins ); \
794  } \
795  } \
796  } \
797  lck->tas.lk.depth_locked = 1; \
798  } \
799  KMP_FSYNC_ACQUIRED( lck ); \
800  } else { \
801  KMP_DEBUG_ASSERT( __kmp_acquire_nested_user_lock_with_checks_ != NULL ); \
802  ( *__kmp_acquire_nested_user_lock_with_checks_ )( lck, gtid ); \
803  }
804 
805 #else
806 static inline void
807 __kmp_acquire_nested_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
808 {
809  KMP_DEBUG_ASSERT( __kmp_acquire_nested_user_lock_with_checks_ != NULL );
810  ( *__kmp_acquire_nested_user_lock_with_checks_ )( lck, gtid );
811 }
812 #endif
813 
814 extern int ( *__kmp_test_nested_user_lock_with_checks_ )( kmp_user_lock_p lck, kmp_int32 gtid );
815 
816 #if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64)
817 static inline int
818 __kmp_test_nested_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
819 {
820  if ( __kmp_user_lock_kind == lk_tas ) {
821  int retval;
822  if ( __kmp_env_consistency_check ) {
823  char const * const func = "omp_test_nest_lock";
824  if ( ( sizeof ( kmp_tas_lock_t ) <= OMP_NEST_LOCK_T_SIZE )
825  && lck->tas.lk.depth_locked == -1 ) {
826  KMP_FATAL( LockSimpleUsedAsNestable, func );
827  }
828  }
829  KMP_DEBUG_ASSERT( gtid >= 0 );
830  if ( lck->tas.lk.poll - 1 == gtid ) { /* __kmp_get_tas_lock_owner( lck ) == gtid */
831  return ++lck->tas.lk.depth_locked; /* same owner, depth increased */
832  }
833  retval = ( ( lck->tas.lk.poll == 0 ) &&
834  KMP_COMPARE_AND_STORE_ACQ32( &(lck->tas.lk.poll), 0, gtid + 1 ) );
835  if ( retval ) {
836  KMP_MB();
837  lck->tas.lk.depth_locked = 1;
838  }
839  return retval;
840  } else {
841  KMP_DEBUG_ASSERT( __kmp_test_nested_user_lock_with_checks_ != NULL );
842  return ( *__kmp_test_nested_user_lock_with_checks_ )( lck, gtid );
843  }
844 }
845 #else
846 static inline int
847 __kmp_test_nested_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
848 {
849  KMP_DEBUG_ASSERT( __kmp_test_nested_user_lock_with_checks_ != NULL );
850  return ( *__kmp_test_nested_user_lock_with_checks_ )( lck, gtid );
851 }
852 #endif
853 
854 extern int ( *__kmp_release_nested_user_lock_with_checks_ )( kmp_user_lock_p lck, kmp_int32 gtid );
855 
856 static inline int
857 __kmp_release_nested_user_lock_with_checks( kmp_user_lock_p lck, kmp_int32 gtid )
858 {
859  KMP_DEBUG_ASSERT( __kmp_release_nested_user_lock_with_checks_ != NULL );
860  return ( *__kmp_release_nested_user_lock_with_checks_ )( lck, gtid );
861 }
862 
863 extern void ( *__kmp_init_nested_user_lock_with_checks_ )( kmp_user_lock_p lck );
864 
865 static inline void __kmp_init_nested_user_lock_with_checks( kmp_user_lock_p lck )
866 {
867  KMP_DEBUG_ASSERT( __kmp_init_nested_user_lock_with_checks_ != NULL );
868  ( *__kmp_init_nested_user_lock_with_checks_ )( lck );
869 }
870 
871 extern void ( *__kmp_destroy_nested_user_lock_with_checks_ )( kmp_user_lock_p lck );
872 
873 static inline void
874 __kmp_destroy_nested_user_lock_with_checks( kmp_user_lock_p lck )
875 {
876  KMP_DEBUG_ASSERT( __kmp_destroy_nested_user_lock_with_checks_ != NULL );
877  ( *__kmp_destroy_nested_user_lock_with_checks_ )( lck );
878 }
879 
880 //
881 // user lock functions which do not necessarily exist for all lock kinds.
882 //
883 // The "set" functions usually have wrapper routines that check for a NULL set
884 // function pointer and call it if non-NULL.
885 //
886 // In some cases, it makes sense to have a "get" wrapper function check for a
887 // NULL get function pointer and return NULL / invalid value / error code if
888 // the function pointer is NULL.
889 //
890 // In other cases, the calling code really should differentiate between an
891 // unimplemented function and one that is implemented but returning NULL /
892 // invalied value. If this is the case, no get function wrapper exists.
893 //
894 
895 extern int ( *__kmp_is_user_lock_initialized_ )( kmp_user_lock_p lck );
896 
897 // no set function; fields set durining local allocation
898 
899 extern const ident_t * ( *__kmp_get_user_lock_location_ )( kmp_user_lock_p lck );
900 
901 static inline const ident_t *
902 __kmp_get_user_lock_location( kmp_user_lock_p lck )
903 {
904  if ( __kmp_get_user_lock_location_ != NULL ) {
905  return ( *__kmp_get_user_lock_location_ )( lck );
906  }
907  else {
908  return NULL;
909  }
910 }
911 
912 extern void ( *__kmp_set_user_lock_location_ )( kmp_user_lock_p lck, const ident_t *loc );
913 
914 static inline void
915 __kmp_set_user_lock_location( kmp_user_lock_p lck, const ident_t *loc )
916 {
917  if ( __kmp_set_user_lock_location_ != NULL ) {
918  ( *__kmp_set_user_lock_location_ )( lck, loc );
919  }
920 }
921 
922 extern kmp_lock_flags_t ( *__kmp_get_user_lock_flags_ )( kmp_user_lock_p lck );
923 
924 extern void ( *__kmp_set_user_lock_flags_ )( kmp_user_lock_p lck, kmp_lock_flags_t flags );
925 
926 static inline void
927 __kmp_set_user_lock_flags( kmp_user_lock_p lck, kmp_lock_flags_t flags )
928 {
929  if ( __kmp_set_user_lock_flags_ != NULL ) {
930  ( *__kmp_set_user_lock_flags_ )( lck, flags );
931  }
932 }
933 
934 //
935 // The fuction which sets up all of the vtbl pointers for kmp_user_lock_t.
936 //
937 extern void __kmp_set_user_lock_vptrs( kmp_lock_kind_t user_lock_kind );
938 
939 //
940 // Macros for binding user lock functions.
941 //
942 #define KMP_BIND_USER_LOCK_TEMPLATE(nest, kind, suffix) { \
943  __kmp_acquire##nest##user_lock_with_checks_ = ( void (*)( kmp_user_lock_p, kmp_int32 ) ) \
944  __kmp_acquire##nest##kind##_##suffix; \
945  __kmp_release##nest##user_lock_with_checks_ = ( int (*)( kmp_user_lock_p, kmp_int32 ) ) \
946  __kmp_release##nest##kind##_##suffix; \
947  __kmp_test##nest##user_lock_with_checks_ = ( int (*)( kmp_user_lock_p, kmp_int32 ) ) \
948  __kmp_test##nest##kind##_##suffix; \
949  __kmp_init##nest##user_lock_with_checks_ = ( void (*)( kmp_user_lock_p ) ) \
950  __kmp_init##nest##kind##_##suffix; \
951  __kmp_destroy##nest##user_lock_with_checks_ = ( void (*)( kmp_user_lock_p ) ) \
952  __kmp_destroy##nest##kind##_##suffix; \
953 }
954 
955 #define KMP_BIND_USER_LOCK(kind) KMP_BIND_USER_LOCK_TEMPLATE(_, kind, lock)
956 #define KMP_BIND_USER_LOCK_WITH_CHECKS(kind) KMP_BIND_USER_LOCK_TEMPLATE(_, kind, lock_with_checks)
957 #define KMP_BIND_NESTED_USER_LOCK(kind) KMP_BIND_USER_LOCK_TEMPLATE(_nested_, kind, lock)
958 #define KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(kind) KMP_BIND_USER_LOCK_TEMPLATE(_nested_, kind, lock_with_checks)
959 
960 // ----------------------------------------------------------------------------
961 // User lock table & lock allocation
962 // ----------------------------------------------------------------------------
963 
964 /*
965  On 64-bit Linux* OS (and OS X*) GNU compiler allocates only 4 bytems memory for lock variable, which
966  is not enough to store a pointer, so we have to use lock indexes instead of pointers and
967  maintain lock table to map indexes to pointers.
968 
969 
970  Note: The first element of the table is not a pointer to lock! It is a pointer to previously
971  allocated table (or NULL if it is the first table).
972 
973  Usage:
974 
975  if ( OMP_LOCK_T_SIZE < sizeof( <lock> ) ) { // or OMP_NEST_LOCK_T_SIZE
976  Lock table is fully utilized. User locks are indexes, so table is
977  used on user lock operation.
978  Note: it may be the case (lin_32) that we don't need to use a lock
979  table for regular locks, but do need the table for nested locks.
980  }
981  else {
982  Lock table initialized but not actually used.
983  }
984 */
985 
986 struct kmp_lock_table {
987  kmp_lock_index_t used; // Number of used elements
988  kmp_lock_index_t allocated; // Number of allocated elements
989  kmp_user_lock_p * table; // Lock table.
990 };
991 
992 typedef struct kmp_lock_table kmp_lock_table_t;
993 
994 extern kmp_lock_table_t __kmp_user_lock_table;
995 extern kmp_user_lock_p __kmp_lock_pool;
996 
997 struct kmp_block_of_locks {
998  struct kmp_block_of_locks * next_block;
999  void * locks;
1000 };
1001 
1002 typedef struct kmp_block_of_locks kmp_block_of_locks_t;
1003 
1004 extern kmp_block_of_locks_t *__kmp_lock_blocks;
1005 extern int __kmp_num_locks_in_block;
1006 
1007 extern kmp_user_lock_p __kmp_user_lock_allocate( void **user_lock, kmp_int32 gtid, kmp_lock_flags_t flags );
1008 extern void __kmp_user_lock_free( void **user_lock, kmp_int32 gtid, kmp_user_lock_p lck );
1009 extern kmp_user_lock_p __kmp_lookup_user_lock( void **user_lock, char const *func );
1010 extern void __kmp_cleanup_user_locks();
1011 
1012 #define KMP_CHECK_USER_LOCK_INIT() \
1013  { \
1014  if ( ! TCR_4( __kmp_init_user_locks ) ) { \
1015  __kmp_acquire_bootstrap_lock( &__kmp_initz_lock ); \
1016  if ( ! TCR_4( __kmp_init_user_locks ) ) { \
1017  TCW_4( __kmp_init_user_locks, TRUE ); \
1018  } \
1019  __kmp_release_bootstrap_lock( &__kmp_initz_lock ); \
1020  } \
1021  }
1022 
1023 #endif // KMP_USE_DYNAMIC_LOCK
1024 
1025 #undef KMP_PAD
1026 #undef KMP_GTID_DNE
1027 
1028 #if KMP_USE_DYNAMIC_LOCK
1029 
1030 #define DYNA_HAS_FUTEX (KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM))
1031 #define DYNA_HAS_HLE (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_MIC)
1032 #define DYNA_USE_FAST_FUTEX 0 && DYNA_HAS_FUTEX
1033 #define DYNA_USE_FAST_TAS 1 && DYNA_HAS_FUTEX
1034 
1035 // List of lock definitions; all nested locks are indirect locks.
1036 // hle lock is xchg lock prefixed with XACQUIRE/XRELEASE.
1037 // All nested locks are indirect lock types.
1038 #if DYNA_HAS_FUTEX
1039 # if DYNA_HAS_HLE
1040 # define FOREACH_D_LOCK(m, a) m(tas, a) m(futex, a) m(hle, a)
1041 # define DYNA_LAST_D_LOCK_SEQ lockseq_hle
1042 # else
1043 # define FOREACH_D_LOCK(m, a) m(tas, a) m(futex, a)
1044 # define DYNA_LAST_D_LOCK_SEQ lockseq_futex
1045 # endif // DYNA_HAS_HLE
1046 # if KMP_USE_ADAPTIVE_LOCKS
1047 # define FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a) m(adaptive, a) m(drdpa, a) \
1048  m(nested_tas, a) m(nested_futex, a) m(nested_ticket, a) \
1049  m(nested_queuing, a) m(nested_drdpa, a)
1050 # else
1051 # define FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a) m(drdpa, a) \
1052  m(nested_tas, a) m(nested_futex, a) m(nested_ticket, a) \
1053  m(nested_queuing, a) m(nested_drdpa, a)
1054 # endif // KMP_USE_ADAPTIVE_LOCKS
1055 #else
1056 # if DYNA_HAS_HLE
1057 # define FOREACH_D_LOCK(m, a) m(tas, a) m(hle, a)
1058 # define DYNA_LAST_D_LOCK_SEQ lockseq_hle
1059 # else
1060 # define FOREACH_D_LOCK(m, a) m(tas, a)
1061 # define DYNA_LAST_D_LOCK_SEQ lockseq_tas
1062 # endif // DYNA_HAS_HLE
1063 # if KMP_USE_ADAPTIVE_LOCKS
1064 # define FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a) m(adaptive, a) m(drdpa, a) \
1065  m(nested_tas, a) m(nested_ticket, a) \
1066  m(nested_queuing, a) m(nested_drdpa, a)
1067 # else
1068 # define FOREACH_I_LOCK(m, a) m(ticket, a) m(queuing, a) m(drdpa, a) \
1069  m(nested_tas, a) m(nested_ticket, a) \
1070  m(nested_queuing, a) m(nested_drdpa, a)
1071 # endif // KMP_USE_ADAPTIVE_LOCKS
1072 #endif // DYNA_HAS_FUTEX
1073 
1074 // Information used in dynamic dispatch
1075 #define DYNA_LOCK_VALUE_SHIFT 8
1076 #define DYNA_LOCK_TYPE_MASK ((1<<DYNA_LOCK_VALUE_SHIFT)-1)
1077 #define DYNA_NUM_D_LOCKS DYNA_LAST_D_LOCK_SEQ
1078 #define DYNA_NUM_I_LOCKS (locktag_nested_drdpa+1)
1079 
1080 // Base type for dynamic locks.
1081 typedef kmp_uint32 kmp_dyna_lock_t;
1082 
1083 // Lock sequence that enumerates all lock kinds.
1084 // Always make this enumeration consistent with kmp_lockseq_t in the include directory.
1085 typedef enum {
1086  lockseq_indirect = 0,
1087 #define expand_seq(l,a) lockseq_##l,
1088  FOREACH_D_LOCK(expand_seq, 0)
1089  FOREACH_I_LOCK(expand_seq, 0)
1090 #undef expand_seq
1091 } kmp_dyna_lockseq_t;
1092 
1093 // Enumerates indirect lock tags.
1094 typedef enum {
1095 #define expand_tag(l,a) locktag_##l,
1096  FOREACH_I_LOCK(expand_tag, 0)
1097 #undef expand_tag
1098 } kmp_indirect_locktag_t;
1099 
1100 // Utility macros that extract information from lock sequences.
1101 #define DYNA_IS_D_LOCK(seq) (seq >= lockseq_tas && seq <= DYNA_LAST_D_LOCK_SEQ)
1102 #define DYNA_IS_I_LOCK(seq) (seq >= lockseq_ticket && seq <= lockseq_nested_drdpa)
1103 #define DYNA_GET_I_TAG(seq) (kmp_indirect_locktag_t)(seq - lockseq_ticket)
1104 #define DYNA_GET_D_TAG(seq) (seq<<1 | 1)
1105 
1106 // Enumerates direct lock tags starting from indirect tag.
1107 typedef enum {
1108 #define expand_tag(l,a) locktag_##l = DYNA_GET_D_TAG(lockseq_##l),
1109  FOREACH_D_LOCK(expand_tag, 0)
1110 #undef expand_tag
1111 } kmp_direct_locktag_t;
1112 
1113 // Indirect lock type
1114 typedef struct {
1115  kmp_user_lock_p lock;
1116  kmp_indirect_locktag_t type;
1117 } kmp_indirect_lock_t;
1118 
1119 // Function tables for direct locks. Set/unset/test differentiate functions with/without consistency checking.
1120 extern void (*__kmp_direct_init_ops[])(kmp_dyna_lock_t *, kmp_dyna_lockseq_t);
1121 extern void (*__kmp_direct_destroy_ops[])(kmp_dyna_lock_t *);
1122 extern void (*(*__kmp_direct_set_ops))(kmp_dyna_lock_t *, kmp_int32);
1123 extern void (*(*__kmp_direct_unset_ops))(kmp_dyna_lock_t *, kmp_int32);
1124 extern int (*(*__kmp_direct_test_ops))(kmp_dyna_lock_t *, kmp_int32);
1125 
1126 // Function tables for indirect locks. Set/unset/test differentiate functions with/withuot consistency checking.
1127 extern void (*__kmp_indirect_init_ops[])(kmp_user_lock_p);
1128 extern void (*__kmp_indirect_destroy_ops[])(kmp_user_lock_p);
1129 extern void (*(*__kmp_indirect_set_ops))(kmp_user_lock_p, kmp_int32);
1130 extern void (*(*__kmp_indirect_unset_ops))(kmp_user_lock_p, kmp_int32);
1131 extern int (*(*__kmp_indirect_test_ops))(kmp_user_lock_p, kmp_int32);
1132 
1133 // Extracts direct lock tag from a user lock pointer
1134 #define DYNA_EXTRACT_D_TAG(l) (*((kmp_dyna_lock_t *)(l)) & DYNA_LOCK_TYPE_MASK & -(*((kmp_dyna_lock_t *)(l)) & 1))
1135 
1136 // Extracts indirect lock index from a user lock pointer
1137 #define DYNA_EXTRACT_I_INDEX(l) (*(kmp_lock_index_t *)(l) >> 1)
1138 
1139 // Returns function pointer to the direct lock function with l (kmp_dyna_lock_t *) and op (operation type).
1140 #define DYNA_D_LOCK_FUNC(l, op) __kmp_direct_##op##_ops[DYNA_EXTRACT_D_TAG(l)]
1141 
1142 // Returns function pointer to the indirect lock function with l (kmp_indirect_lock_t *) and op (operation type).
1143 #define DYNA_I_LOCK_FUNC(l, op) __kmp_indirect_##op##_ops[((kmp_indirect_lock_t *)(l))->type]
1144 
1145 // Initializes a direct lock with the given lock pointer and lock sequence.
1146 #define DYNA_INIT_D_LOCK(l, seq) __kmp_direct_init_ops[DYNA_GET_D_TAG(seq)]((kmp_dyna_lock_t *)l, seq)
1147 
1148 // Initializes an indirect lock with the given lock pointer and lock sequence.
1149 #define DYNA_INIT_I_LOCK(l, seq) __kmp_direct_init_ops[0]((kmp_dyna_lock_t *)(l), seq)
1150 
1151 // Returns "free" lock value for the given lock type.
1152 #define DYNA_LOCK_FREE(type) (locktag_##type)
1153 
1154 // Returns "busy" lock value for the given lock teyp.
1155 #define DYNA_LOCK_BUSY(v, type) ((v)<<DYNA_LOCK_VALUE_SHIFT | locktag_##type)
1156 
1157 // Returns lock value after removing (shifting) lock tag.
1158 #define DYNA_LOCK_STRIP(v) ((v)>>DYNA_LOCK_VALUE_SHIFT)
1159 
1160 // Updates __kmp_user_lock_seq with the give lock type.
1161 #define DYNA_STORE_LOCK_SEQ(type) (__kmp_user_lock_seq = lockseq_##type)
1162 
1163 // Internal entries for hinted lock initializers.
1164 extern void __kmp_init_lock_hinted(void **, int);
1165 extern void __kmp_init_nest_lock_hinted(void **, int);
1166 
1167 // Initializes global states and data structures for managing dynamic user locks.
1168 extern void __kmp_init_dynamic_user_locks();
1169 
1170 // Allocates and returns an indirect lock with the given indirect lock tag.
1171 extern kmp_indirect_lock_t * __kmp_allocate_indirect_lock(void **, kmp_int32, kmp_indirect_locktag_t);
1172 
1173 // Cleans up global states and data structures for managing dynamic user locks.
1174 extern void __kmp_cleanup_indirect_user_locks();
1175 
1176 // Default user lock sequence when not using hinted locks.
1177 extern kmp_dyna_lockseq_t __kmp_user_lock_seq;
1178 
1179 // Jump table for "set lock location", available only for indirect locks.
1180 extern void (*__kmp_indirect_set_location[DYNA_NUM_I_LOCKS])(kmp_user_lock_p, const ident_t *);
1181 #define DYNA_SET_I_LOCK_LOCATION(lck, loc) { \
1182  if (__kmp_indirect_set_location[(lck)->type] != NULL) \
1183  __kmp_indirect_set_location[(lck)->type]((lck)->lock, loc); \
1184 }
1185 
1186 // Jump table for "set lock flags", available only for indirect locks.
1187 extern void (*__kmp_indirect_set_flags[DYNA_NUM_I_LOCKS])(kmp_user_lock_p, kmp_lock_flags_t);
1188 #define DYNA_SET_I_LOCK_FLAGS(lck, flag) { \
1189  if (__kmp_indirect_set_flags[(lck)->type] != NULL) \
1190  __kmp_indirect_set_flags[(lck)->type]((lck)->lock, flag); \
1191 }
1192 
1193 // Jump table for "get lock location", available only for indirect locks.
1194 extern const ident_t * (*__kmp_indirect_get_location[DYNA_NUM_I_LOCKS])(kmp_user_lock_p);
1195 #define DYNA_GET_I_LOCK_LOCATION(lck) ( __kmp_indirect_get_location[(lck)->type] != NULL \
1196  ? __kmp_indirect_get_location[(lck)->type]((lck)->lock) \
1197  : NULL )
1198 
1199 // Jump table for "get lock flags", available only for indirect locks.
1200 extern kmp_lock_flags_t (*__kmp_indirect_get_flags[DYNA_NUM_I_LOCKS])(kmp_user_lock_p);
1201 #define DYNA_GET_I_LOCK_FLAGS(lck) ( __kmp_indirect_get_flags[(lck)->type] != NULL \
1202  ? __kmp_indirect_get_flags[(lck)->type]((lck)->lock) \
1203  : NULL )
1204 
1205 //
1206 // Lock table for indirect locks.
1207 //
1208 // Simple linear structure is used to keep pointers to allocated indirect locks.
1209 extern kmp_indirect_lock_t **__kmp_indirect_lock_table;
1210 // Current size of the lock table; it may increase but never shrink.
1211 extern kmp_lock_index_t __kmp_indirect_lock_table_size;
1212 // Next index to be used for a new indirect lock (= number of indirect locks allocated).
1213 extern kmp_lock_index_t __kmp_indirect_lock_table_next;
1214 // Number of locks in a lock block, which is fixed to "1" now.
1215 // TODO: No lock block implementation now. If we do support, we need to manage lock block data
1216 // structure for each indirect lock type.
1217 extern int __kmp_num_locks_in_block;
1218 
1219 // Fast lock table lookup without consistency checking
1220 #define DYNA_LOOKUP_I_LOCK(l) ( (OMP_LOCK_T_SIZE < sizeof(void *)) \
1221  ? __kmp_indirect_lock_table[DYNA_EXTRACT_I_INDEX(l)] \
1222  : *((kmp_indirect_lock_t **)l) )
1223 
1224 // Used once in kmp_error.c
1225 extern kmp_int32
1226 __kmp_get_user_lock_owner(kmp_user_lock_p, kmp_uint32);
1227 
1228 #else // KMP_USE_DYNAMIC_LOCK
1229 
1230 # define DYNA_LOCK_BUSY(v, type) (v)
1231 # define DYNA_LOCK_FREE(type) 0
1232 # define DYNA_LOCK_STRIP(v) (v)
1233 # define DYNA_STORE_LOCK_SEQ(seq)
1234 
1235 #endif // KMP_USE_DYNAMIC_LOCK
1236 
1237 #ifdef __cplusplus
1238 } // extern "C"
1239 #endif // __cplusplus
1240 
1241 #endif /* KMP_LOCK_H */
1242 
Definition: kmp.h:198