1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 */
10
11 #include "hpc/thread.h"
12
13 #include "code.h"
14 #include "error.h"
15 #include "fibhash.h"
16 #include "gapstate.h"
17 #include "gvars.h"
18 #include "modules.h"
19 #include "plist.h"
20 #include "stats.h"
21 #include "stringobj.h"
22 #include "vars.h"
23
24 #include "hpc/guards.h"
25 #include "hpc/misc.h"
26 #include "hpc/threadapi.h"
27
28 #include <errno.h>
29 #include <pthread.h>
30 #include <stdio.h>
31 #include <sys/mman.h>
32 #include <unistd.h>
33
34 #ifdef USE_BOEHM_GC
35 # ifdef HPCGAP
36 # define GC_THREADS
37 # endif
38 # include <gc/gc.h>
39 #endif
40
41
42 #define LOG2_NUM_LOCKS 11
43 #define NUM_LOCKS (1 << LOG2_NUM_LOCKS)
44
45 #ifndef WARD_ENABLED
46
47 typedef struct ThreadData {
48 pthread_t pthread_id;
49 pthread_mutex_t * lock;
50 pthread_cond_t * cond;
51 int joined;
52 int system;
53 AtomicUInt state;
54 void * tls;
55 void (*start)(void *);
56 void * arg;
57 Obj thread_object;
58 Obj region_name;
59 struct ThreadData * next;
60 } ThreadData;
61
62 Region *LimboRegion, *ReadOnlyRegion;
63 Obj PublicRegionName;
64
65 static int GlobalPauseInProgress;
66 static AtomicUInt ThreadCounter = 1;
67
IncThreadCounter(void)68 static inline void IncThreadCounter(void)
69 {
70 ATOMIC_INC(&ThreadCounter);
71 }
72
DecThreadCounter(void)73 static inline void DecThreadCounter(void)
74 {
75 ATOMIC_DEC(&ThreadCounter);
76 }
77
78 static ThreadData thread_data[MAX_THREADS];
79 static ThreadData * paused_threads[MAX_THREADS];
80 static ThreadData * thread_free_list;
81 static int num_paused_threads;
82
83 static pthread_rwlock_t master_lock;
84
85 static pthread_rwlock_t ObjLock[NUM_LOCKS];
86
87 int PreThreadCreation = 1;
88
LockThreadControl(int modify)89 void LockThreadControl(int modify)
90 {
91 if (modify)
92 pthread_rwlock_wrlock(&master_lock);
93 else
94 pthread_rwlock_rdlock(&master_lock);
95 }
96
UnlockThreadControl(void)97 void UnlockThreadControl(void)
98 {
99 pthread_rwlock_unlock(&master_lock);
100 }
101
102 #ifndef MAP_ANONYMOUS
103 #define MAP_ANONYMOUS MAP_ANON
104 #endif
105
106 #ifndef HAVE_NATIVE_TLS
107
AllocateTLS(void)108 void * AllocateTLS(void)
109 {
110 void * addr;
111 void * result;
112 size_t pagesize = getpagesize();
113 size_t tlssize =
114 (sizeof(GAPState) + pagesize - 1) & ~(pagesize - 1);
115 addr = mmap(0, 2 * TLS_SIZE, PROT_READ | PROT_WRITE,
116 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
117 result = (void *)((((uintptr_t)addr) + (TLS_SIZE - 1)) & TLS_MASK);
118 munmap(addr, (char *)result - (char *)addr);
119 munmap((char *)result + TLS_SIZE,
120 (char *)addr - (char *)result + TLS_SIZE);
121 /* generate a stack overflow protection area */
122 #ifdef STACK_GROWS_UP
123 mprotect((char *)result + TLS_SIZE - tlssize - pagesize, pagesize,
124 PROT_NONE);
125 #else
126 mprotect((char *)result + tlssize, pagesize, PROT_NONE);
127 #endif
128 return result;
129 }
130
FreeTLS(void * address)131 void FreeTLS(void * address)
132 {
133 /* We currently cannot free this memory because of garbage collector
134 * issues. Instead, it will be reused */
135 #if 0
136 munmap(address, TLS_STACK_SIZE);
137 #endif
138 }
139
140 #endif /* HAVE_NATIVE_TLS */
141
142 #ifndef DISABLE_GC
AddGCRoots(void)143 void AddGCRoots(void)
144 {
145 void * p = ActiveGAPState();
146 GC_add_roots(p, (char *)p + sizeof(GAPState));
147 }
148
RemoveGCRoots(void)149 static void RemoveGCRoots(void)
150 {
151 void * p = ActiveGAPState();
152 #if defined(__CYGWIN__) || defined(__CYGWIN32__)
153 memset(p, '\0', sizeof(GAPState));
154 #else
155 GC_remove_roots(p, (char *)p + sizeof(GAPState));
156 #endif
157 }
158 #endif /* DISABLE_GC */
159
160 #ifndef HAVE_NATIVE_TLS
161
162 /* In order to safely use thread-local memory on the main stack, we have
163 * to work around an idiosyncracy in some virtual memory systems. These
164 * VM implementations do not allow fully random access within the stack
165 * segment, but only quasi-linear access: a page can only be accessed if
166 * a nearby page was accessed before. If this pattern is not observed,
167 * but if we access memory within the stack segment randomly -- as in
168 * our TLS implementation, but also with very large stack frames -- a
169 * segmentation fault can arise. To avoid such segmentation faults, we
170 * traverse the stack segment of the main stack, touching each page in
171 * turn.
172 *
173 * Note that this is not necessary for thread stacks, which are
174 * allocated in private memory-mapped storage.
175 */
176
GrowStack(void)177 static NOINLINE void GrowStack(void)
178 {
179 char * tls = (char *)GetTLS();
180 size_t pagesize = getpagesize();
181 /* p needs to be a volatile pointer so that the memory writes are not
182 * removed by the optimizer */
183 volatile char * p = alloca(pagesize);
184 while (p > tls) {
185 /* touch memory */
186 *p = '\0';
187 p = alloca(pagesize);
188 }
189 }
190 #endif
191
SetupTLS(void)192 static NOINLINE void SetupTLS(void)
193 {
194 #ifndef HAVE_NATIVE_TLS
195 GrowStack();
196 #endif
197 InitializeTLS();
198 TLS(threadID) = 0;
199 }
200
InitMainThread(void)201 void InitMainThread(void)
202 {
203 TLS(threadObject) = NewThreadObject(0);
204 TLS(CountActive) = 1;
205 }
206
207 static NOINLINE void RunThreadedMain2(int (*mainFunction)(int, char **),
208 int argc,
209 char ** argv);
210
RunThreadedMain(int (* mainFunction)(int,char **),int argc,char ** argv)211 void RunThreadedMain(int (*mainFunction)(int, char **),
212 int argc,
213 char ** argv)
214 {
215 #ifndef HAVE_NATIVE_TLS
216 #ifdef STACK_GROWS_UP
217 #error Upward growing stack not yet supported
218 #else
219 /* We need to ensure that the stack pointer and frame pointer
220 * of the called function begin at the top end of a memory
221 * segment whose beginning and end address are a multiple of
222 * TLS_SIZE (which is a power of 2). To that end, we look at
223 * an approximation of the current stack pointer by taking
224 * the address of a local variable, then mask out the lowest
225 * bits and use alloca() to allocate at least that many bytes
226 * on the stack. We also need to touch the pages in that area;
227 * see the comments on GrowStack() for the reason why.
228 */
229 volatile int dummy[1];
230 size_t amount;
231 amount = ((uintptr_t)dummy) & ~TLS_MASK;
232 volatile char * p = alloca(((uintptr_t)dummy) & ~TLS_MASK);
233 volatile char * q;
234 for (q = p + amount - 1; (void *)q >= (void *)p; q -= 1024) {
235 /* touch memory */
236 *q = '\0';
237 }
238 #endif
239 #endif
240 RunThreadedMain2(mainFunction, argc, argv);
241 }
242
RunThreadedMain2(int (* mainFunction)(int,char **),int argc,char ** argv)243 static void RunThreadedMain2(int (*mainFunction)(int, char **),
244 int argc,
245 char ** argv)
246 {
247 int i;
248 static pthread_mutex_t main_thread_mutex;
249 static pthread_cond_t main_thread_cond;
250 SetupTLS();
251 for (i = 1; i < MAX_THREADS - 1; i++)
252 thread_data[i].next = thread_data + i + 1;
253 thread_data[0].next = NULL;
254 for (i = 0; i < NUM_LOCKS; i++)
255 pthread_rwlock_init(&ObjLock[i], 0);
256 thread_data[MAX_THREADS - 1].next = NULL;
257 for (i = 0; i < MAX_THREADS; i++) {
258 thread_data[i].tls = 0;
259 thread_data[i].state = TSTATE_TERMINATED;
260 thread_data[i].system = 0;
261 }
262 thread_free_list = thread_data + 1;
263 pthread_rwlock_init(&master_lock, 0);
264 pthread_mutex_init(&main_thread_mutex, 0);
265 pthread_cond_init(&main_thread_cond, 0);
266 TLS(threadLock) = &main_thread_mutex;
267 TLS(threadSignal) = &main_thread_cond;
268 thread_data[0].lock = TLS(threadLock);
269 thread_data[0].cond = TLS(threadSignal);
270 thread_data[0].state = TSTATE_RUNNING;
271 thread_data[0].tls = GetTLS();
272 InitSignals();
273 if (sySetjmp(TLS(threadExit)))
274 exit(0);
275 exit((*mainFunction)(argc, argv));
276 }
277
CreateMainRegion(void)278 void CreateMainRegion(void)
279 {
280 int i;
281 TLS(currentRegion) = NewRegion();
282 TLS(threadRegion) = TLS(currentRegion);
283 TLS(currentRegion)->fixed_owner = 1;
284 RegionWriteLock(TLS(currentRegion));
285 TLS(currentRegion)->name = MakeImmString("thread region #0");
286 PublicRegionName = MakeImmString("public region");
287 LimboRegion = NewRegion();
288 LimboRegion->fixed_owner = 1;
289 LimboRegion->name = MakeImmString("limbo region");
290 ReadOnlyRegion = NewRegion();
291 ReadOnlyRegion->name = MakeImmString("read-only region");
292 ReadOnlyRegion->fixed_owner = 1;
293 for (i = 0; i <= MAX_THREADS; i++) {
294 ReadOnlyRegion->readers[i] = 1;
295 }
296 }
297
MakeImmString2(const Char * cstr1,const Char * cstr2)298 static Obj MakeImmString2(const Char * cstr1, const Char * cstr2)
299 {
300 Obj result;
301 size_t len1 = strlen(cstr1), len2 = strlen(cstr2);
302 result = NEW_STRING(len1 + len2);
303 memcpy(CSTR_STRING(result), cstr1, len1);
304 memcpy(CSTR_STRING(result) + len1, cstr2, len2);
305 MakeImmutableNoRecurse(result);
306 return result;
307 }
308
DispatchThread(void * arg)309 static void * DispatchThread(void * arg)
310 {
311 ThreadData * this_thread = arg;
312 Region * region;
313 InitializeTLS();
314 TLS(threadID) = this_thread - thread_data;
315 #ifndef DISABLE_GC
316 AddGCRoots();
317 #endif
318 ModulesInitModuleState();
319 TLS(CountActive) = 1;
320 region = NewRegion();
321 TLS(currentRegion) = region;
322 TLS(threadRegion) = region;
323 TLS(threadLock) = this_thread->lock;
324 TLS(threadSignal) = this_thread->cond;
325 region->fixed_owner = 1;
326 region->name = this_thread->region_name;
327 RegionWriteLock(region);
328 if (!this_thread->region_name) {
329 char buf[8];
330 sprintf(buf, "%d", TLS(threadID));
331 this_thread->region_name = MakeImmString2("thread #", buf);
332 }
333 SetRegionName(region, this_thread->region_name);
334 TLS(threadObject) = this_thread->thread_object;
335 pthread_mutex_lock(this_thread->lock);
336
337 ThreadObject *thread = (ThreadObject *)ADDR_OBJ(TLS(threadObject));
338 thread->tls = GetTLS();
339 pthread_cond_broadcast(this_thread->cond);
340 pthread_mutex_unlock(this_thread->lock);
341 this_thread->start(this_thread->arg);
342 thread->status |= THREAD_TERMINATED;
343 region->fixed_owner = 0;
344 RegionWriteUnlock(region);
345 ModulesDestroyModuleState();
346 memset(ActiveGAPState(), 0, sizeof(GAPState));
347 #ifndef DISABLE_GC
348 RemoveGCRoots();
349 #endif
350 this_thread->state = TSTATE_TERMINATED;
351 DecThreadCounter();
352 return 0;
353 }
354
RunThread(void (* start)(void *),void * arg)355 Obj RunThread(void (*start)(void *), void * arg)
356 {
357 ThreadData * result;
358 #ifndef HAVE_NATIVE_TLS
359 void * tls;
360 size_t pagesize = getpagesize();
361 #endif
362 pthread_attr_t thread_attr;
363 LockThreadControl(1);
364 PreThreadCreation = 0;
365 /* allocate a new thread id */
366 if (thread_free_list == NULL) {
367 UnlockThreadControl();
368 errno = ENOMEM;
369 return (Obj)0;
370 }
371 result = thread_free_list;
372 thread_free_list = thread_free_list->next;
373 #ifndef HAVE_NATIVE_TLS
374 if (!result->tls)
375 result->tls = AllocateTLS();
376 tls = result->tls;
377 #endif
378 if (!result->lock) {
379 result->lock = AllocateMemoryBlock(sizeof(pthread_mutex_t));
380 result->cond = AllocateMemoryBlock(sizeof(pthread_cond_t));
381 pthread_mutex_init(result->lock, 0);
382 pthread_cond_init(result->cond, 0);
383 }
384 result->arg = arg;
385 result->start = start;
386 result->joined = 0;
387 if (GlobalPauseInProgress) {
388 /* New threads will be automatically paused */
389 result->state = TSTATE_PAUSED;
390 HandleInterrupts(0, 0);
391 }
392 else {
393 result->state = TSTATE_RUNNING;
394 }
395 result->thread_object = NewThreadObject(result - thread_data);
396 /* set up the thread attribute to support a custom stack in our TLS */
397 pthread_attr_init(&thread_attr);
398 #ifndef HAVE_NATIVE_TLS
399 pthread_attr_setstack(&thread_attr, (char *)tls + pagesize * 2,
400 TLS_SIZE - pagesize * 2);
401 #endif
402 UnlockThreadControl();
403 /* fork the thread */
404 IncThreadCounter();
405 if (pthread_create(&result->pthread_id, &thread_attr, DispatchThread,
406 result) < 0) {
407 /* No more threads available */
408 DecThreadCounter();
409 LockThreadControl(1);
410 result->next = thread_free_list;
411 thread_free_list = result;
412 UnlockThreadControl();
413 pthread_attr_destroy(&thread_attr);
414 #ifndef HAVE_NATIVE_TLS
415 FreeTLS(tls);
416 #endif
417 return (Obj)0;
418 }
419 pthread_attr_destroy(&thread_attr);
420 return result->thread_object;
421 }
422
JoinThread(int id)423 int JoinThread(int id)
424 {
425 pthread_t pthread_id;
426 void (*start)(void *);
427 #ifndef HAVE_NATIVE_TLS
428 void * tls;
429 #endif
430 if (id < 0 || id >= MAX_THREADS)
431 return 0;
432 LockThreadControl(1);
433 pthread_id = thread_data[id].pthread_id;
434 start = thread_data[id].start;
435 #ifndef HAVE_NATIVE_TLS
436 tls = thread_data[id].tls;
437 #endif
438 if (thread_data[id].joined || start == NULL) {
439 UnlockThreadControl();
440 return 0;
441 }
442 thread_data[id].joined = 1;
443 UnlockThreadControl();
444 pthread_join(pthread_id, NULL);
445 LockThreadControl(1);
446 thread_data[id].next = thread_free_list;
447 thread_free_list = thread_data + id;
448 /*
449 FreeTLS(thread_data[id].tls);
450 thread_data[id].tls = NULL;
451 */
452 thread_data[id].start = NULL;
453 UnlockThreadControl();
454 #ifndef HAVE_NATIVE_TLS
455 FreeTLS(tls);
456 #endif
457 return 1;
458 }
459
LockID(void * object)460 static UInt LockID(void * object)
461 {
462 #ifdef CUSTOM_OBJECT_HASH
463 UInt p = (UInt)object;
464 if (sizeof(void *) == 4)
465 return ((p >> 2) ^ (p >> (2 + LOG2_NUM_LOCKS)) ^
466 (p << (LOG2_NUM_LOCKS - 2))) %
467 NUM_LOCKS;
468 else
469 return ((p >> 3) ^ (p >> (3 + LOG2_NUM_LOCKS)) ^
470 (p << (LOG2_NUM_LOCKS - 3))) %
471 NUM_LOCKS;
472 #else
473 return FibHash((UInt)object, LOG2_NUM_LOCKS);
474 #endif
475 }
476
HashLock(void * object)477 void HashLock(void * object)
478 {
479 if (TLS(CurrentHashLock))
480 ErrorQuit("Nested hash locks", 0L, 0L);
481 TLS(CurrentHashLock) = object;
482 pthread_rwlock_wrlock(&ObjLock[LockID(object)]);
483 }
484
HashLockShared(void * object)485 void HashLockShared(void * object)
486 {
487 if (TLS(CurrentHashLock))
488 ErrorQuit("Nested hash locks", 0L, 0L);
489 TLS(CurrentHashLock) = object;
490 pthread_rwlock_rdlock(&ObjLock[LockID(object)]);
491 }
492
HashUnlock(void * object)493 void HashUnlock(void * object)
494 {
495 if (TLS(CurrentHashLock) != object)
496 ErrorQuit("Improperly matched hash lock/unlock calls", 0L, 0L);
497 TLS(CurrentHashLock) = 0;
498 pthread_rwlock_unlock(&ObjLock[LockID(object)]);
499 }
500
HashUnlockShared(void * object)501 void HashUnlockShared(void * object)
502 {
503 if (TLS(CurrentHashLock) != object)
504 ErrorQuit("Improperly matched hash lock/unlock calls", 0L, 0L);
505 TLS(CurrentHashLock) = 0;
506 pthread_rwlock_unlock(&ObjLock[LockID(object)]);
507 }
508
RegionWriteLock(Region * region)509 void RegionWriteLock(Region * region)
510 {
511 int result = 0;
512 assert(region->owner != GetTLS());
513
514 if (region->count_active || TLS(CountActive)) {
515 result = !pthread_rwlock_trywrlock(region->lock);
516
517 if (result) {
518 if (region->count_active)
519 region->locks_acquired++;
520 if (TLS(CountActive))
521 TLS(LocksAcquired)++;
522 }
523 else {
524 if (region->count_active)
525 region->locks_contended++;
526 if (TLS(CountActive))
527 TLS(LocksContended)++;
528 pthread_rwlock_wrlock(region->lock);
529 }
530 }
531 else {
532 pthread_rwlock_wrlock(region->lock);
533 }
534
535 region->owner = GetTLS();
536 }
537
RegionTryWriteLock(Region * region)538 int RegionTryWriteLock(Region * region)
539 {
540 int result;
541 assert(region->owner != GetTLS());
542 result = !pthread_rwlock_trywrlock(region->lock);
543
544 if (result) {
545 if (region->count_active)
546 region->locks_acquired++;
547 if (TLS(CountActive))
548 TLS(LocksAcquired)++;
549 region->owner = GetTLS();
550 }
551 else {
552 if (region->count_active)
553 region->locks_contended++;
554 if (TLS(CountActive))
555 TLS(LocksContended)++;
556 }
557 return result;
558 }
559
RegionWriteUnlock(Region * region)560 void RegionWriteUnlock(Region * region)
561 {
562 assert(region->owner == GetTLS());
563 region->owner = NULL;
564 pthread_rwlock_unlock(region->lock);
565 }
566
RegionReadLock(Region * region)567 void RegionReadLock(Region * region)
568 {
569 int result = 0;
570 assert(region->owner != GetTLS());
571 assert(region->readers[TLS(threadID)] == 0);
572
573 if (region->count_active || TLS(CountActive)) {
574 result = !pthread_rwlock_rdlock(region->lock);
575
576 if (result) {
577 if (region->count_active)
578 ATOMIC_INC(®ion->locks_acquired);
579 if (TLS(CountActive))
580 TLS(LocksAcquired)++;
581 }
582 else {
583 if (region->count_active)
584 ATOMIC_INC(®ion->locks_contended);
585 if (TLS(CountActive))
586 TLS(LocksAcquired)++;
587 pthread_rwlock_rdlock(region->lock);
588 }
589 }
590 else {
591 pthread_rwlock_rdlock(region->lock);
592 }
593 region->readers[TLS(threadID)] = 1;
594 }
595
RegionTryReadLock(Region * region)596 int RegionTryReadLock(Region * region)
597 {
598 int result = !pthread_rwlock_rdlock(region->lock);
599 assert(region->owner != GetTLS());
600 assert(region->readers[TLS(threadID)] == 0);
601
602 if (result) {
603 if (region->count_active)
604 ATOMIC_INC(®ion->locks_acquired);
605 if (TLS(CountActive))
606 TLS(LocksAcquired)++;
607 region->readers[TLS(threadID)] = 1;
608 }
609 else {
610 if (region->count_active)
611 ATOMIC_INC(®ion->locks_contended);
612 if (TLS(CountActive))
613 TLS(LocksContended)++;
614 }
615 return result;
616 }
617
RegionReadUnlock(Region * region)618 void RegionReadUnlock(Region * region)
619 {
620 assert(region->readers[TLS(threadID)]);
621 region->readers[TLS(threadID)] = 0;
622 pthread_rwlock_unlock(region->lock);
623 }
624
RegionUnlock(Region * region)625 void RegionUnlock(Region * region)
626 {
627 assert(region->owner == GetTLS() || region->readers[TLS(threadID)]);
628 if (region->owner == GetTLS())
629 region->owner = NULL;
630 region->readers[TLS(threadID)] = 0;
631 pthread_rwlock_unlock(region->lock);
632 }
633
IsLocked(Region * region)634 LockStatus IsLocked(Region * region)
635 {
636 if (!region)
637 return LOCK_STATUS_UNLOCKED; /* public region */
638 if (region->owner == GetTLS())
639 return LOCK_STATUS_READWRITE_LOCKED;
640 if (region->readers[TLS(threadID)])
641 return LOCK_STATUS_READONLY_LOCKED;
642 return LOCK_STATUS_UNLOCKED;
643 }
644
GetRegionOf(Obj obj)645 Region * GetRegionOf(Obj obj)
646 {
647 if (!IS_BAG_REF(obj))
648 return NULL;
649 if (TNUM_OBJ(obj) == T_REGION)
650 return *(Region **)(ADDR_OBJ(obj));
651 return REGION(obj);
652 }
653
SetRegionName(Region * region,Obj name)654 void SetRegionName(Region * region, Obj name)
655 {
656 if (name) {
657 if (!IS_STRING(name))
658 return;
659 if (IS_MUTABLE_OBJ(name))
660 name = CopyObj(name, 0);
661 }
662 MEMBAR_WRITE();
663 region->name = name;
664 }
665
GetRegionName(Region * region)666 Obj GetRegionName(Region * region)
667 {
668 Obj result;
669 if (region)
670 result = region->name;
671 else
672 result = PublicRegionName;
673 MEMBAR_READ();
674 return result;
675 }
676
GetLockStatus(int count,Obj * objects,LockStatus * status)677 void GetLockStatus(int count, Obj * objects, LockStatus * status)
678 {
679 int i;
680 for (i = 0; i < count; i++)
681 status[i] = IsLocked(REGION(objects[i]));
682 }
683
NewList(UInt size)684 static Obj NewList(UInt size)
685 {
686 Obj list;
687 list = NEW_PLIST(size == 0 ? T_PLIST_EMPTY : T_PLIST, size);
688 SET_LEN_PLIST(list, size);
689 return list;
690 }
691
GetRegionLockCounters(Region * region)692 Obj GetRegionLockCounters(Region * region)
693 {
694 Obj result = NewList(2);
695
696 if (region) {
697 SET_ELM_PLIST(result, 1, INTOBJ_INT(region->locks_acquired));
698 SET_ELM_PLIST(result, 2, INTOBJ_INT(region->locks_contended));
699 }
700 MEMBAR_READ();
701 return result;
702 }
703
ResetRegionLockCounters(Region * region)704 void ResetRegionLockCounters(Region * region)
705 {
706 if (region) {
707 region->locks_acquired = region->locks_contended = 0;
708 }
709 MEMBAR_WRITE();
710 }
711
712 #define MAX_LOCKS 1024
713
714 typedef struct {
715 Obj obj;
716 Region * region;
717 LockMode mode;
718 } LockRequest;
719
LessThanLockRequest(const void * a,const void * b)720 static int LessThanLockRequest(const void * a, const void * b)
721 {
722 Region * region_a = ((LockRequest *)a)->region;
723 Region * region_b = ((LockRequest *)b)->region;
724 Int prec_diff;
725 if (region_a == region_b) /* prioritize writes */
726 return ((LockRequest *)a)->mode > ((LockRequest *)b)->mode;
727 prec_diff = region_a->prec - region_b->prec;
728 return prec_diff > 0 ||
729 (prec_diff == 0 && (char *)region_a < (char *)region_b);
730 }
731
PushRegionLock(Region * region)732 void PushRegionLock(Region * region)
733 {
734 if (!TLS(lockStack)) {
735 TLS(lockStack) = NewList(16);
736 TLS(lockStackPointer) = 0;
737 }
738 else if (LEN_PLIST(TLS(lockStack)) == TLS(lockStackPointer)) {
739 int newlen = TLS(lockStackPointer) * 3 / 2;
740 GROW_PLIST(TLS(lockStack), newlen);
741 }
742 TLS(lockStackPointer)++;
743 SET_ELM_PLIST(TLS(lockStack), TLS(lockStackPointer),
744 region ? region->obj : (Obj)0);
745 }
746
PopRegionLocks(int newSP)747 void PopRegionLocks(int newSP)
748 {
749 while (newSP < TLS(lockStackPointer)) {
750 int p = TLS(lockStackPointer)--;
751 Obj region_obj = ELM_PLIST(TLS(lockStack), p);
752 if (!region_obj)
753 continue;
754 Region * region = *(Region **)(ADDR_OBJ(region_obj));
755 RegionUnlock(region);
756 SET_ELM_PLIST(TLS(lockStack), p, (Obj)0);
757 }
758 }
759
RegionLockSP(void)760 int RegionLockSP(void)
761 {
762 return TLS(lockStackPointer);
763 }
764
GetThreadState(int threadID)765 int GetThreadState(int threadID)
766 {
767 return (int)(thread_data[threadID].state);
768 }
769
UpdateThreadState(int threadID,int oldState,int newState)770 int UpdateThreadState(int threadID, int oldState, int newState)
771 {
772 return COMPARE_AND_SWAP(&thread_data[threadID].state,
773 (AtomicUInt)oldState, (AtomicUInt)newState);
774 }
775
SetInterrupt(int threadID)776 static void SetInterrupt(int threadID)
777 {
778 ThreadLocalStorage * tls = thread_data[threadID].tls;
779 MEMBAR_FULL();
780 ((GAPState *)tls)->CurrExecStatFuncs = IntrExecStatFuncs;
781 }
782
LockAndUpdateThreadState(int threadID,int oldState,int newState)783 static int LockAndUpdateThreadState(int threadID, int oldState, int newState)
784 {
785 if (pthread_mutex_trylock(thread_data[threadID].lock) < 0) {
786 return 0;
787 }
788 if (!UpdateThreadState(threadID, oldState, newState)) {
789 pthread_mutex_unlock(thread_data[threadID].lock);
790 return 0;
791 }
792 SetInterrupt(threadID);
793 pthread_cond_signal(thread_data[threadID].cond);
794 pthread_mutex_unlock(thread_data[threadID].lock);
795 return 1;
796 }
797
PauseThread(int threadID)798 void PauseThread(int threadID)
799 {
800 for (;;) {
801 int state = GetThreadState(threadID);
802 switch (state & TSTATE_MASK) {
803 case TSTATE_RUNNING:
804 if (UpdateThreadState(threadID, TSTATE_RUNNING,
805 TSTATE_PAUSED |
806 (TLS(threadID) << TSTATE_SHIFT))) {
807 SetInterrupt(threadID);
808 return;
809 }
810 break;
811 case TSTATE_BLOCKED:
812 case TSTATE_SYSCALL:
813 if (LockAndUpdateThreadState(threadID, state,
814 TSTATE_PAUSED |
815 (TLS(threadID) << TSTATE_SHIFT)))
816 return;
817 break;
818 case TSTATE_PAUSED:
819 case TSTATE_TERMINATED:
820 case TSTATE_KILLED:
821 case TSTATE_INTERRUPTED:
822 return;
823 }
824 }
825 }
826
TerminateCurrentThread(int locked)827 static void TerminateCurrentThread(int locked)
828 {
829 ThreadData * thread = thread_data + TLS(threadID);
830 if (locked)
831 pthread_mutex_unlock(thread->lock);
832 PopRegionLocks(0);
833 if (TLS(CurrentHashLock))
834 HashUnlock(TLS(CurrentHashLock));
835 syLongjmp(&(TLS(threadExit)), 1);
836 }
837
PauseCurrentThread(int locked)838 static void PauseCurrentThread(int locked)
839 {
840 ThreadData * thread = thread_data + TLS(threadID);
841 if (!locked)
842 pthread_mutex_lock(thread->lock);
843 for (;;) {
844 int state = GetThreadState(TLS(threadID));
845 if ((state & TSTATE_MASK) == TSTATE_KILLED)
846 TerminateCurrentThread(1);
847 if ((state & TSTATE_MASK) != TSTATE_PAUSED)
848 break;
849 TLS(currentRegion)->alt_owner =
850 thread_data[state >> TSTATE_SHIFT].tls;
851 pthread_cond_wait(thread->cond, thread->lock);
852 // TODO: This really should go in ResumeThread()
853 TLS(currentRegion)->alt_owner = NULL;
854 }
855 if (!locked)
856 pthread_mutex_unlock(thread->lock);
857 }
858
InterruptCurrentThread(int locked,Stat stat)859 static void InterruptCurrentThread(int locked, Stat stat)
860 {
861 if (stat == 0)
862 return;
863 ThreadData * thread = thread_data + TLS(threadID);
864 int state;
865 Obj handler = (Obj)0;
866 if (!locked)
867 pthread_mutex_lock(thread->lock);
868 STATE(CurrExecStatFuncs) = ExecStatFuncs;
869 SET_BRK_CALL_TO(stat);
870 state = GetThreadState(TLS(threadID));
871 if ((state & TSTATE_MASK) == TSTATE_INTERRUPTED)
872 UpdateThreadState(TLS(threadID), state, TSTATE_RUNNING);
873 if (state >> TSTATE_SHIFT) {
874 Int n = state >> TSTATE_SHIFT;
875 if (TLS(interruptHandlers)) {
876 if (n >= 1 && n <= LEN_PLIST(TLS(interruptHandlers)))
877 handler = ELM_PLIST(TLS(interruptHandlers), n);
878 }
879 }
880 if (handler)
881 CALL_WITH_CATCH(handler, NEW_PLIST(T_PLIST, 0));
882 else
883 ErrorReturnVoid("system interrupt", 0L, 0L, "you can 'return;'");
884 if (!locked)
885 pthread_mutex_unlock(thread->lock);
886 }
887
SetInterruptHandler(int handler,Obj func)888 void SetInterruptHandler(int handler, Obj func)
889 {
890 if (!TLS(interruptHandlers)) {
891 TLS(interruptHandlers) = NEW_PLIST(T_PLIST, MAX_INTERRUPT);
892 SET_LEN_PLIST(TLS(interruptHandlers), MAX_INTERRUPT);
893 }
894 SET_ELM_PLIST(TLS(interruptHandlers), handler, func);
895 }
896
HandleInterrupts(int locked,Stat stat)897 void HandleInterrupts(int locked, Stat stat)
898 {
899 switch (GetThreadState(TLS(threadID)) & TSTATE_MASK) {
900 case TSTATE_PAUSED:
901 PauseCurrentThread(locked);
902 break;
903 case TSTATE_INTERRUPTED:
904 InterruptCurrentThread(locked, stat);
905 break;
906 case TSTATE_KILLED:
907 TerminateCurrentThread(locked);
908 break;
909 }
910 }
911
KillThread(int threadID)912 void KillThread(int threadID)
913 {
914 for (;;) {
915 int state = GetThreadState(threadID);
916 switch (state & TSTATE_MASK) {
917 case TSTATE_RUNNING:
918 if (UpdateThreadState(threadID, TSTATE_RUNNING, TSTATE_KILLED)) {
919 SetInterrupt(threadID);
920 return;
921 }
922 break;
923 case TSTATE_BLOCKED:
924 if (LockAndUpdateThreadState(threadID, state, TSTATE_KILLED))
925 return;
926 break;
927 case TSTATE_SYSCALL:
928 if (UpdateThreadState(threadID, state, TSTATE_KILLED)) {
929 return;
930 }
931 break;
932 case TSTATE_INTERRUPTED:
933 if (UpdateThreadState(threadID, state, TSTATE_KILLED)) {
934 SetInterrupt(threadID);
935 return;
936 }
937 break;
938 case TSTATE_PAUSED:
939 if (LockAndUpdateThreadState(threadID, state, TSTATE_KILLED)) {
940 return;
941 }
942 break;
943 case TSTATE_TERMINATED:
944 case TSTATE_KILLED:
945 return;
946 }
947 }
948 }
949
InterruptThread(int threadID,int handler)950 void InterruptThread(int threadID, int handler)
951 {
952 for (;;) {
953 int state = GetThreadState(threadID);
954 switch (state & TSTATE_MASK) {
955 case TSTATE_RUNNING:
956 if (UpdateThreadState(threadID, TSTATE_RUNNING,
957 TSTATE_INTERRUPTED |
958 (handler << TSTATE_SHIFT))) {
959 SetInterrupt(threadID);
960 return;
961 }
962 break;
963 case TSTATE_BLOCKED:
964 if (LockAndUpdateThreadState(threadID, state,
965 TSTATE_INTERRUPTED |
966 (handler << TSTATE_SHIFT)))
967 return;
968 break;
969 case TSTATE_SYSCALL:
970 if (UpdateThreadState(threadID, state,
971 TSTATE_INTERRUPTED |
972 (handler << TSTATE_SHIFT)))
973 return;
974 break;
975 case TSTATE_PAUSED:
976 case TSTATE_TERMINATED:
977 case TSTATE_KILLED:
978 case TSTATE_INTERRUPTED:
979 /* We do not interrupt threads that are interrupted */
980 return;
981 }
982 }
983 }
984
ResumeThread(int threadID)985 void ResumeThread(int threadID)
986 {
987 int state = GetThreadState(threadID);
988 if ((state & TSTATE_MASK) == TSTATE_PAUSED) {
989 LockAndUpdateThreadState(threadID, state, TSTATE_RUNNING);
990 }
991 }
992
PauseAllThreads(void)993 int PauseAllThreads(void)
994 {
995 int i, n;
996 LockThreadControl(1);
997 if (GlobalPauseInProgress) {
998 UnlockThreadControl();
999 return 0;
1000 }
1001 GlobalPauseInProgress = 1;
1002 for (i = 0, n = 0; i < MAX_THREADS; i++) {
1003 switch (GetThreadState(i) & TSTATE_MASK) {
1004 case TSTATE_TERMINATED:
1005 case TSTATE_KILLED:
1006 break;
1007 default:
1008 if (!thread_data[i].system)
1009 paused_threads[n++] = thread_data + i;
1010 break;
1011 }
1012 }
1013 num_paused_threads = n;
1014 UnlockThreadControl();
1015 for (i = 0; i < n; i++)
1016 PauseThread(i);
1017 return 1;
1018 }
1019
ResumeAllThreads(void)1020 void ResumeAllThreads(void)
1021 {
1022 int i, n;
1023 n = num_paused_threads;
1024 for (i = 0; i < n; i++) {
1025 ResumeThread(i);
1026 }
1027 }
1028
1029 /**
1030 * Deadlock checks
1031 * ---------------
1032 *
1033 * We use a scheme of numerical tiers to implement deadlock checking.
1034 * Each region is assigned a numerical precedence, and regions must
1035 * be locked in strictly descending numerical order. If this order
1036 * is inverted, or if two regions of the same precedence are locked
1037 * through separate actions, then this is an error.
1038 *
1039 * Regions with negative precedence are ignored for these tests. This
1040 * is to facilitate more complex precedence schemes that cannot be
1041 * embedded in a total ordering.
1042 */
1043
CurrentRegionPrecedence(void)1044 static Int CurrentRegionPrecedence(void)
1045 {
1046 Int sp;
1047 if (!DeadlockCheck || !TLS(lockStack))
1048 return -1;
1049 sp = TLS(lockStackPointer);
1050 while (sp > 0) {
1051 Obj region_obj = ELM_PLIST(TLS(lockStack), sp);
1052 if (region_obj) {
1053 Int prec = ((Region *)(*ADDR_OBJ(region_obj)))->prec;
1054 if (prec >= 0)
1055 return prec;
1056 }
1057 sp--;
1058 }
1059 return -1;
1060 }
1061
LockObject(Obj obj,LockMode mode)1062 int LockObject(Obj obj, LockMode mode)
1063 {
1064 Region * region = GetRegionOf(obj);
1065 int result = TLS(lockStackPointer);
1066 if (!region)
1067 return result;
1068
1069 LockStatus locked = IsLocked(region);
1070 if (locked == LOCK_STATUS_READONLY_LOCKED && mode == LOCK_MODE_READWRITE)
1071 return -1;
1072 if (locked == LOCK_STATUS_UNLOCKED) {
1073 Int prec = CurrentRegionPrecedence();
1074 if (prec >= 0 && region->prec >= prec && region->prec >= 0)
1075 return -1;
1076 if (region->fixed_owner)
1077 return -1;
1078 if (mode == LOCK_MODE_READWRITE)
1079 RegionWriteLock(region);
1080 else
1081 RegionReadLock(region);
1082 PushRegionLock(region);
1083 }
1084 return result;
1085 }
1086
LockObjects(int count,Obj * objects,const LockMode * mode)1087 int LockObjects(int count, Obj * objects, const LockMode * mode)
1088 {
1089 int result;
1090 int i, p;
1091 Int curr_prec;
1092 LockRequest * order;
1093 if (count == 1) /* fast path */
1094 return LockObject(objects[0], mode[0]);
1095 if (count > MAX_LOCKS)
1096 return -1;
1097 order = alloca(sizeof(LockRequest) * count);
1098 for (i = 0, p = 0; i < count; i++) {
1099 Region * r = GetRegionOf(objects[i]);
1100 if (r) {
1101 order[p].obj = objects[i];
1102 order[p].region = GetRegionOf(objects[i]);
1103 order[p].mode = mode[i];
1104 p++;
1105 }
1106 }
1107 count = p;
1108 if (p > 1)
1109 MergeSort(order, count, sizeof(LockRequest), LessThanLockRequest);
1110 result = TLS(lockStackPointer);
1111 curr_prec = CurrentRegionPrecedence();
1112 for (i = 0; i < count; i++) {
1113 Region * region = order[i].region;
1114 /* If there are multiple lock requests with different modes,
1115 * they have been sorted for writes to occur first, so deadlock
1116 * cannot occur from doing readlocks before writelocks.
1117 */
1118 if (i > 0 && region == order[i - 1].region)
1119 continue; /* skip duplicates */
1120 if (!region)
1121 continue;
1122
1123 LockStatus locked = IsLocked(region);
1124 if (locked == LOCK_STATUS_READONLY_LOCKED &&
1125 order[i].mode == LOCK_MODE_READWRITE) {
1126 /* trying to upgrade read lock to write lock */
1127 PopRegionLocks(result);
1128 return -1;
1129 }
1130 if (!locked) {
1131 if (curr_prec >= 0 && region->prec >= curr_prec &&
1132 region->prec >= 0) {
1133 PopRegionLocks(result);
1134 return -1;
1135 }
1136 if (region->fixed_owner) {
1137 PopRegionLocks(result);
1138 return -1;
1139 }
1140 if (order[i].mode == LOCK_MODE_READWRITE)
1141 RegionWriteLock(region);
1142 else
1143 RegionReadLock(region);
1144 PushRegionLock(region);
1145 }
1146 if (GetRegionOf(order[i].obj) != region) {
1147 /* Race condition, revert locks and fail */
1148 PopRegionLocks(result);
1149 return -1;
1150 }
1151 }
1152 return result;
1153 }
1154
TryLockObjects(int count,Obj * objects,const LockMode * mode)1155 int TryLockObjects(int count, Obj * objects, const LockMode * mode)
1156 {
1157 int result;
1158 int i;
1159 LockRequest * order;
1160 if (count > MAX_LOCKS)
1161 return -1;
1162 order = alloca(sizeof(LockRequest) * count);
1163 for (i = 0; i < count; i++) {
1164 order[i].obj = objects[i];
1165 order[i].region = GetRegionOf(objects[i]);
1166 order[i].mode = mode[i];
1167 }
1168 MergeSort(order, count, sizeof(LockRequest), LessThanLockRequest);
1169 result = TLS(lockStackPointer);
1170 for (i = 0; i < count; i++) {
1171 Region * region = order[i].region;
1172 /* If there are multiple lock requests with different modes,
1173 * they have been sorted for writes to occur first, so deadlock
1174 * cannot occur from doing readlocks before writelocks.
1175 */
1176 if (i > 0 && region == order[i - 1].region)
1177 continue; /* skip duplicates */
1178 if (!region ||
1179 region->fixed_owner) { /* public or thread-local region */
1180 PopRegionLocks(result);
1181 return -1;
1182 }
1183 LockStatus locked = IsLocked(region);
1184 if (locked == LOCK_STATUS_READONLY_LOCKED &&
1185 order[i].mode == LOCK_MODE_READWRITE) {
1186 /* trying to upgrade read lock to write lock */
1187 PopRegionLocks(result);
1188 return -1;
1189 }
1190 if (locked == LOCK_STATUS_UNLOCKED) {
1191 if (order[i].mode == LOCK_MODE_READWRITE) {
1192 if (!RegionTryWriteLock(region)) {
1193 PopRegionLocks(result);
1194 return -1;
1195 }
1196 }
1197 else {
1198 if (!RegionTryReadLock(region)) {
1199 PopRegionLocks(result);
1200 return -1;
1201 }
1202 }
1203 PushRegionLock(region);
1204 }
1205 if (GetRegionOf(order[i].obj) != region) {
1206 /* Race condition, revert locks and fail */
1207 PopRegionLocks(result);
1208 return -1;
1209 }
1210 }
1211 return result;
1212 }
1213
CurrentRegion(void)1214 Region * CurrentRegion(void)
1215 {
1216 return TLS(currentRegion);
1217 }
1218
1219 #ifdef VERBOSE_GUARDS
1220
PrintGuardError(char * buffer,char * mode,Obj obj,const char * file,unsigned line,const char * func,const char * expr)1221 static void PrintGuardError(char * buffer,
1222 char * mode,
1223 Obj obj,
1224 const char * file,
1225 unsigned line,
1226 const char * func,
1227 const char * expr)
1228 {
1229 sprintf(buffer, "No %s access to object %llu of type %s\n"
1230 "in %s, line %u, function %s(), accessing %s",
1231 mode, (unsigned long long)(UInt)obj, TNAM_OBJ(obj), file, line,
1232 func, expr);
1233 }
WriteGuardError(Obj o,const char * file,unsigned line,const char * func,const char * expr)1234 void WriteGuardError(Obj o,
1235 const char * file,
1236 unsigned line,
1237 const char * func,
1238 const char * expr)
1239 {
1240 char * buffer = alloca(strlen(file) + strlen(func) + strlen(expr) + 200);
1241 ImpliedReadGuard(o);
1242 if (TLS(DisableGuards))
1243 return;
1244 SetGVar(&LastInaccessibleGVar, o);
1245 PrintGuardError(buffer, "write", o, file, line, func, expr);
1246 ErrorMayQuit("%s", (UInt)buffer, 0L);
1247 }
1248
ReadGuardError(Obj o,const char * file,unsigned line,const char * func,const char * expr)1249 void ReadGuardError(Obj o,
1250 const char * file,
1251 unsigned line,
1252 const char * func,
1253 const char * expr)
1254 {
1255 char * buffer = alloca(strlen(file) + strlen(func) + strlen(expr) + 200);
1256 ImpliedReadGuard(o);
1257 if (TLS(DisableGuards))
1258 return;
1259 SetGVar(&LastInaccessibleGVar, o);
1260 PrintGuardError(buffer, "read", o, file, line, func, expr);
1261 ErrorMayQuit("%s", (UInt)buffer, 0L);
1262 }
1263
1264 #else
WriteGuardError(Obj o)1265 void WriteGuardError(Obj o)
1266 {
1267 ImpliedReadGuard(o);
1268 if (TLS(DisableGuards))
1269 return;
1270 SetGVar(&LastInaccessibleGVar, o);
1271 ErrorMayQuit(
1272 "Attempt to write object %i of type %s without having write access",
1273 (Int)o, (Int)TNAM_OBJ(o));
1274 }
1275
ReadGuardError(Obj o)1276 void ReadGuardError(Obj o)
1277 {
1278 ImpliedReadGuard(o);
1279 if (TLS(DisableGuards))
1280 return;
1281 SetGVar(&LastInaccessibleGVar, o);
1282 ErrorMayQuit(
1283 "Attempt to read object %i of type %s without having read access",
1284 (Int)o, (Int)TNAM_OBJ(o));
1285 }
1286 #endif
1287
1288 #endif
1289