boehm-gc/linux_threads.c

   1 /*
   2  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
   3  * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
   4  * Copyright (c) 1998 by Fergus Henderson.  All rights reserved.
   5  * Copyright (c) 2000-2001 by Hewlett-Packard Company.  All rights reserved.
   6  *
   7  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   8  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   9  *
  10  * Permission is hereby granted to use or copy this program
  11  * for any purpose,  provided the above notices are retained on all copies.
  12  * Permission to modify the code and to distribute modified code is granted,
  13  * provided the above notices are retained, and a notice that the code was
  14  * modified is included with the above copyright notice.
  15  */
  16 /*
  17  * Support code for LinuxThreads, the clone()-based kernel
  18  * thread package for Linux which is included in libc6.
  19  *
  20  * This code relies on implementation details of LinuxThreads,
  21  * (i.e. properties not guaranteed by the Pthread standard),
  22  * though this version now does less of that than the other Pthreads
  23  * support code.
  24  *
  25  * Note that there is a lot of code duplication between linux_threads.c
  26  * and thread support for some of the other Posix platforms; any changes
  27  * made here may need to be reflected there too.
  28  */
  29 /*
  30  * Linux_threads.c now also includes some code to support HPUX and
  31  * OSF1 (Compaq Tru64 Unix, really).  The OSF1 support is not yet
  32  * functional.  The OSF1 code is based on Eric Benson's
  33  * patch, though that was originally against hpux_irix_threads.  The code
  34  * here is completely untested.  With 0.0000001% probability, it might
  35  * actually work.
  36  *
  37  * Eric also suggested an alternate basis for a lock implementation in
  38  * his code:
  39  * + #elif defined(OSF1)
  40  * +    unsigned long GC_allocate_lock = 0;
  41  * +    msemaphore GC_allocate_semaphore;
  42  * + #  define GC_TRY_LOCK() \
  43  * +    ((msem_lock(&GC_allocate_semaphore, MSEM_IF_NOWAIT) == 0) \
  44  * +     ? (GC_allocate_lock = 1) \
  45  * +     : 0)
  46  * + #  define GC_LOCK_TAKEN GC_allocate_lock
  47  */
  48
  49 /* #define DEBUG_THREADS 1 */
  50
  51 /* ANSI C requires that a compilation unit contains something */
  52
  53 # if defined(GC_LINUX_THREADS) || defined(LINUX_THREADS) \
  54      || defined(GC_HPUX_THREADS) || defined(HPUX_THREADS) \
  55      || defined(GC_OSF1_THREADS) || defined(OSF1_THREADS) \
  56
  57 # include "private/gc_priv.h"
  58 # ifdef THREAD_LOCAL_ALLOC
  59 #   if !defined(USE_PTHREAD_SPECIFIC) && !defined(USE_HPUX_TLS)
  60 #     include "private/specific.h"
  61 #   endif
  62 #   if defined(USE_PTHREAD_SPECIFIC)
  63 #     define GC_getspecific pthread_getspecific
  64 #     define GC_setspecific pthread_setspecific
  65 #     define GC_key_create pthread_key_create
  66       typedef pthread_key_t GC_key_t;
  67 #   endif
  68 #   if defined(USE_HPUX_TLS)
  69 #     define GC_getspecific(x) (x)
  70 #     define GC_setspecific(key, v) ((key) = (v), 0)
  71 #     define GC_key_create(key, d) 0
  72       typedef void * GC_key_t;
  73 #   endif
  74 # endif
  75 # include <stdlib.h>
  76 # include <pthread.h>
  77 # include <sched.h>
  78 # include <time.h>
  79 # include <errno.h>
  80 # include <unistd.h>
  81 # include <sys/mman.h>
  82 # include <sys/time.h>
  83 # include <semaphore.h>
  84 # include <signal.h>
  85 # include <sys/types.h>
  86 # include <sys/stat.h>
  87 # include <fcntl.h>
  88
  89 #ifndef __GNUC__
  90 #   define __inline__
  91 #endif
  92
  93 #ifdef GC_USE_LD_WRAP
  94 #   define WRAP_FUNC(f) __wrap_##f
  95 #   define REAL_FUNC(f) __real_##f
  96 #else
  97 #   define WRAP_FUNC(f) GC_##f
  98 #   define REAL_FUNC(f) f
  99 #   undef pthread_create
 100 #   undef pthread_sigmask
 101 #   undef pthread_join
 102 #   undef pthread_detach
 103 #endif
 104
 105
 106 void GC_thr_init();
 107
 108 #if 0
 109 void GC_print_sig_mask()
 110 {
 111     sigset_t blocked;
 112     int i;
 113
 114     if (pthread_sigmask(SIG_BLOCK, NULL, &blocked) != 0)
 115         ABORT("pthread_sigmask");
 116     GC_printf0("Blocked: ");
 117     for (i = 1; i <= MAXSIG; i++) {
 118         if (sigismember(&blocked, i)) { GC_printf1("%ld ",(long) i); }
 119     }
 120     GC_printf0("\n");
 121 }
 122 #endif
 123
 124
 125 /* We use the allocation lock to protect thread-related data structures. */
 126
 127 /* The set of all known threads.  We intercept thread creation and      */
 128 /* joins.                                                               */
 129 /* Protected by allocation/GC lock.                                     */
 130 /* Some of this should be declared volatile, but that's inconsistent    */
 131 /* with some library routine declarations.                              */
 132 typedef struct GC_Thread_Rep {
 133     struct GC_Thread_Rep * next;  /* More recently allocated threads    */
 134                                   /* with a given pthread id come       */
 135                                   /* first.  (All but the first are     */
 136                                   /* guaranteed to be dead, but we may  */
 137                                   /* not yet have registered the join.) */
 138     pthread_t id;
 139     short flags;
 140 #       define FINISHED 1       /* Thread has exited.   */
 141 #       define DETACHED 2       /* Thread is intended to be detached.   */
 142 #       define MAIN_THREAD 4    /* True for the original thread only.   */
 143     short thread_blocked;       /* Protected by GC lock.                */
 144                                 /* Treated as a boolean value.  If set, */
 145                                 /* thread will acquire GC lock before   */
 146                                 /* doing any pointer manipulations, and */
 147                                 /* has set its sp value.  Thus it does  */
 148                                 /* not need to be sent a signal to stop */
 149                                 /* it.                                  */
 150     ptr_t stack_end;            /* Cold end of the stack.               */
 151     ptr_t stack_ptr;            /* Valid only when stopped.             */
 152 #   ifdef IA64
 153         ptr_t backing_store_end;
 154         ptr_t backing_store_ptr;
 155 #   endif
 156     int signal;
 157     void * status;              /* The value returned from the thread.  */
 158                                 /* Used only to avoid premature         */
 159                                 /* reclamation of any data it might     */
 160                                 /* reference.                           */
 161 #   ifdef THREAD_LOCAL_ALLOC
 162 #       if CPP_WORDSZ == 64 && defined(ALIGN_DOUBLE)
 163 #           define GRANULARITY 16
 164 #           define NFREELISTS 48
 165 #       else
 166 #           define GRANULARITY 8
 167 #           define NFREELISTS 64
 168 #       endif
 169         /* The ith free list corresponds to size (i+1)*GRANULARITY */
 170 #       define INDEX_FROM_BYTES(n) (ADD_SLOP(n) - 1)/GRANULARITY
 171 #       define BYTES_FROM_INDEX(i) (((i) + 1) * GRANULARITY - EXTRA_BYTES)
 172 #       define SMALL_ENOUGH(bytes) (ADD_SLOP(bytes) <= NFREELISTS*GRANULARITY)
 173         ptr_t ptrfree_freelists[NFREELISTS];
 174         ptr_t normal_freelists[NFREELISTS];
 175 #       ifdef GC_GCJ_SUPPORT
 176           ptr_t gcj_freelists[NFREELISTS];
 177 #       endif
 178                 /* Free lists contain either a pointer or a small count */
 179                 /* reflecting the number of granules allocated at that  */
 180                 /* size.                                                */
 181                 /* 0 ==> thread-local allocation in use, free list      */
 182                 /*       empty.                                         */
 183                 /* > 0, <= DIRECT_GRANULES ==> Using global allocation, */
 184                 /*       too few objects of this size have been         */
 185                 /*       allocated by this thread.                      */
 186                 /* >= HBLKSIZE  => pointer to nonempty free list.       */
 187                 /* > DIRECT_GRANULES, < HBLKSIZE ==> transition to      */
 188                 /*    local alloc, equivalent to 0.                     */
 189 #       define DIRECT_GRANULES (HBLKSIZE/GRANULARITY)
 190                 /* Don't use local free lists for up to this much       */
 191                 /* allocation.                                          */
 192 #   endif
 193 } * GC_thread;
 194
 195 GC_thread GC_lookup_thread(pthread_t id);
 196
 197 static GC_bool fully_initialized = FALSE;
 198
 199 # if defined(__GNUC__)
 200     void GC_full_init() __attribute__ ((constructor));
 201 # else
 202     void GC_full_init();
 203 # endif
 204
 205 # if defined(THREAD_LOCAL_ALLOC) && !defined(DBG_HDRS_ALL)
 206
 207 /* We don't really support thread-local allocation with DBG_HDRS_ALL */
 208
 209 #ifdef USE_HPUX_TLS
 210   __thread
 211 #endif
 212 GC_key_t GC_thread_key;
 213
 214 static GC_bool keys_initialized;
 215
 216 /* Recover the contents of the freelist array fl into the global one gfl.*/
 217 /* Note that the indexing scheme differs, in that gfl has finer size    */
 218 /* resolution, even if not all entries are used.                        */
 219 /* We hold the allocator lock.                                          */
 220 static void return_freelists(ptr_t *fl, ptr_t *gfl)
 221 {
 222     int i;
 223     ptr_t q, *qptr;
 224     size_t nwords;
 225
 226     for (i = 0; i < NFREELISTS; ++i) {
 227         nwords = (i + 1) * (GRANULARITY/sizeof(word));
 228         qptr = fl + i;
 229         q = *qptr;
 230         if ((word)q < HBLKSIZE) continue;
 231         if (gfl[nwords] == 0) {
 232             gfl[nwords] = q;
 233         } else {
 234             /* Concatenate: */
 235             for (; (word)q >= HBLKSIZE; qptr = &(obj_link(q)), q = *qptr);
 236             GC_ASSERT(0 == q);
 237             *qptr = gfl[nwords];
 238             gfl[nwords] = fl[i];
 239         }
 240         /* Clear fl[i], since the thread structure may hang around.     */
 241         /* Do it in a way that is likely to trap if we access it.       */
 242         fl[i] = (ptr_t)HBLKSIZE;
 243     }
 244 }
 245
 246 /* Each thread structure must be initialized.   */
 247 /* This call must be made from the new thread.  */
 248 /* Caller holds allocation lock.                */
 249 void GC_init_thread_local(GC_thread p)
 250 {
 251     int i;
 252
 253     if (!keys_initialized) {
 254         if (0 != GC_key_create(&GC_thread_key, 0)) {
 255             ABORT("Failed to create key for local allocator");
 256         }
 257         keys_initialized = TRUE;
 258     }
 259     if (0 != GC_setspecific(GC_thread_key, p)) {
 260         ABORT("Failed to set thread specific allocation pointers");
 261     }
 262     for (i = 0; i < NFREELISTS; ++i) {
 263         p -> ptrfree_freelists[i] = (ptr_t)1;
 264         p -> normal_freelists[i] = (ptr_t)1;
 265 #       ifdef GC_GCJ_SUPPORT
 266           p -> gcj_freelists[i] = (ptr_t)1;
 267 #       endif
 268     }
 269 }
 270
 271 #ifdef GC_GCJ_SUPPORT
 272   extern ptr_t * GC_gcjobjfreelist;
 273 #endif
 274
 275 /* We hold the allocator lock.  */
 276 void GC_destroy_thread_local(GC_thread p)
 277 {
 278     /* We currently only do this from the thread itself.        */
 279         GC_ASSERT(GC_getspecific(GC_thread_key) == (void *)p);
 280     return_freelists(p -> ptrfree_freelists, GC_aobjfreelist);
 281     return_freelists(p -> normal_freelists, GC_objfreelist);
 282 #   ifdef GC_GCJ_SUPPORT
 283         return_freelists(p -> gcj_freelists, GC_gcjobjfreelist);
 284 #   endif
 285 }
 286
 287 extern GC_PTR GC_generic_malloc_many();
 288
 289 GC_PTR GC_local_malloc(size_t bytes)
 290 {
 291     if (EXPECT(!SMALL_ENOUGH(bytes),0)) {
 292         return(GC_malloc(bytes));
 293     } else {
 294         int index = INDEX_FROM_BYTES(bytes);
 295         ptr_t * my_fl;
 296         ptr_t my_entry;
 297         GC_key_t k = GC_thread_key;
 298         void * tsd;
 299
 300 #       if defined(REDIRECT_MALLOC) && !defined(USE_PTHREAD_SPECIFIC) \
 301            || !defined(__GNUC__)
 302             if (EXPECT(0 == k, 0)) {
 303                 /* This can happen if we get called when the world is   */
 304                 /* being initialized.  Whether we can actually complete */
 305                 /* the initialization then is unclear.                  */
 306                 GC_full_init();
 307                 k = GC_thread_key;
 308             }
 309 #       endif
 310         tsd = GC_getspecific(GC_thread_key);
 311 #       ifdef GC_ASSERTIONS
 312           LOCK();
 313           GC_ASSERT(tsd == (void *)GC_lookup_thread(pthread_self()));
 314           UNLOCK();
 315 #       endif
 316         my_fl = ((GC_thread)tsd) -> normal_freelists + index;
 317         my_entry = *my_fl;
 318         if (EXPECT((word)my_entry >= HBLKSIZE, 1)) {
 319             ptr_t next = obj_link(my_entry);
 320             GC_PTR result = (GC_PTR)my_entry;
 321             *my_fl = next;
 322             obj_link(my_entry) = 0;
 323             PREFETCH_FOR_WRITE(next);
 324             return result;
 325         } else if ((word)my_entry - 1 < DIRECT_GRANULES) {
 326             *my_fl = my_entry + index + 1;
 327             return GC_malloc(bytes);
 328         } else {
 329             my_entry = GC_generic_malloc_many(BYTES_FROM_INDEX(index),
 330                                               NORMAL);
 331             *my_fl = my_entry;
 332             if (my_entry == 0) return GC_oom_fn(bytes);
 333             return GC_local_malloc(bytes);
 334         }
 335     }
 336 }
 337
 338 GC_PTR GC_local_malloc_atomic(size_t bytes)
 339 {
 340     if (EXPECT(!SMALL_ENOUGH(bytes), 0)) {
 341         return(GC_malloc_atomic(bytes));
 342     } else {
 343         int index = INDEX_FROM_BYTES(bytes);
 344         ptr_t * my_fl = ((GC_thread)GC_getspecific(GC_thread_key))
 345                         -> ptrfree_freelists + index;
 346         ptr_t my_entry = *my_fl;
 347         if (EXPECT((word)my_entry >= HBLKSIZE, 1)) {
 348             GC_PTR result = (GC_PTR)my_entry;
 349             *my_fl = obj_link(my_entry);
 350             return result;
 351         } else if ((word)my_entry - 1 < DIRECT_GRANULES) {
 352             *my_fl = my_entry + index + 1;
 353             return GC_malloc_atomic(bytes);
 354         } else {
 355             my_entry = GC_generic_malloc_many(BYTES_FROM_INDEX(index),
 356                                               PTRFREE);
 357             *my_fl = my_entry;
 358             if (my_entry == 0) return GC_oom_fn(bytes);
 359             return GC_local_malloc_atomic(bytes);
 360         }
 361     }
 362 }
 363
 364 #ifdef GC_GCJ_SUPPORT
 365
 366 #include "include/gc_gcj.h"
 367
 368 #ifdef GC_ASSERTIONS
 369   extern GC_bool GC_gcj_malloc_initialized;
 370 #endif
 371
 372 extern int GC_gcj_kind;
 373
 374 GC_PTR GC_local_gcj_malloc(size_t bytes,
 375                            void * ptr_to_struct_containing_descr)
 376 {
 377     GC_ASSERT(GC_gcj_malloc_initialized);
 378     if (EXPECT(!SMALL_ENOUGH(bytes), 0)) {
 379         return GC_gcj_malloc(bytes, ptr_to_struct_containing_descr);
 380     } else {
 381         int index = INDEX_FROM_BYTES(bytes);
 382         ptr_t * my_fl = ((GC_thread)GC_getspecific(GC_thread_key))
 383                         -> gcj_freelists + index;
 384         ptr_t my_entry = *my_fl;
 385         if (EXPECT((word)my_entry >= HBLKSIZE, 1)) {
 386             GC_PTR result = (GC_PTR)my_entry;
 387             GC_ASSERT(!GC_incremental);
 388             /* We assert that any concurrent marker will stop us.       */
 389             /* Thus it is impossible for a mark procedure to see the    */
 390             /* allocation of the next object, but to see this object    */
 391             /* still containing a free list pointer.  Otherwise the     */
 392             /* marker might find a random "mark descriptor".            */
 393             *my_fl = obj_link(my_entry);
 394             *(void **)result = ptr_to_struct_containing_descr;
 395             return result;
 396         } else if ((word)my_entry - 1 < DIRECT_GRANULES) {
 397             *my_fl = my_entry + index + 1;
 398             return GC_gcj_malloc(bytes, ptr_to_struct_containing_descr);
 399         } else {
 400             my_entry = GC_generic_malloc_many(BYTES_FROM_INDEX(index),
 401                                               GC_gcj_kind);
 402             *my_fl = my_entry;
 403             if (my_entry == 0) return GC_oom_fn(bytes);
 404             return GC_gcj_malloc(bytes, ptr_to_struct_containing_descr);
 405         }
 406     }
 407 }
 408
 409 #endif /* GC_GCJ_SUPPORT */
 410
 411 # else  /* !THREAD_LOCAL_ALLOC  && !DBG_HDRS_ALL */
 412
 413 #   define GC_destroy_thread_local(t)
 414
 415 # endif /* !THREAD_LOCAL_ALLOC */
 416
 417 /*
 418  * The only way to suspend threads given the pthread interface is to send
 419  * signals.  We can't use SIGSTOP directly, because we need to get the
 420  * thread to save its stack pointer in the GC thread table before
 421  * suspending.  So we have to reserve a signal of our own for this.
 422  * This means we have to intercept client calls to change the signal mask.
 423  * The linuxthreads package already uses SIGUSR1 and SIGUSR2,
 424  * so we need to reuse something else.  I chose SIGPWR.
 425  * (Perhaps SIGUNUSED would be a better choice.)
 426  */
 427 #ifndef SIG_SUSPEND
 428 #  if defined(HPUX_THREADS) || defined(GC_OSF1_THREADS)
 429 #   define SIG_SUSPEND _SIGRTMIN + 6
 430 #  else
 431 #   define SIG_SUSPEND SIGPWR
 432 #  endif
 433 #endif
 434
 435 #ifndef SIG_THR_RESTART
 436 #  if defined(HPUX_THREADS) || defined(GC_OSF1_THREADS)
 437 #   define SIG_THR_RESTART _SIGRTMIN + 5
 438 #  else
 439 #   define SIG_THR_RESTART SIGXCPU
 440 #  endif
 441 #endif
 442
 443 /* SPARC/Linux doesn't properly define SIGPWR in <signal.h>.
 444  * It is aliased to SIGLOST in asm/signal.h, though.            */
 445 #if defined(SPARC) && !defined(SIGPWR)
 446 #   define SIGPWR SIGLOST
 447 #endif
 448
 449 sem_t GC_suspend_ack_sem;
 450
 451 #if !defined(HPUX_THREADS) && !defined(GC_OSF1_THREADS)
 452 /*
 453 To make sure that we're using LinuxThreads and not some other thread
 454 package, we generate a dummy reference to `pthread_kill_other_threads_np'
 455 (was `__pthread_initial_thread_bos' but that disappeared),
 456 which is a symbol defined in LinuxThreads, but (hopefully) not in other
 457 thread packages.
 458 */
 459 void (*dummy_var_to_force_linux_threads)() = pthread_kill_other_threads_np;
 460 #endif /* !HPUX_THREADS */
 461
 462 #if defined(SPARC) || defined(IA64)
 463   extern word GC_save_regs_in_stack();
 464 #endif
 465
 466 long GC_nprocs = 1;     /* Number of processors.  We may not have       */
 467                         /* access to all of them, but this is as good   */
 468                         /* a guess as any ...                           */
 469
 470 #ifdef PARALLEL_MARK
 471
 472 # ifndef MAX_MARKERS
 473 #   define MAX_MARKERS 16
 474 # endif
 475
 476 static ptr_t marker_sp[MAX_MARKERS] = {0};
 477
 478 void * GC_mark_thread(void * id)
 479 {
 480   word my_mark_no = 0;
 481
 482   marker_sp[(word)id] = GC_approx_sp();
 483   for (;; ++my_mark_no) {
 484     /* GC_mark_no is passed only to allow GC_help_marker to terminate   */
 485     /* promptly.  This is important if it were called from the signal   */
 486     /* handler or from the GC lock acquisition code.  Under Linux, it's */
 487     /* not safe to call it from a signal handler, since it uses mutexes */
 488     /* and condition variables.  Since it is called only here, the      */
 489     /* argument is unnecessary.                                         */
 490     if (my_mark_no < GC_mark_no || my_mark_no > GC_mark_no + 2) {
 491         /* resynchronize if we get far off, e.g. because GC_mark_no     */
 492         /* wrapped.                                                     */
 493         my_mark_no = GC_mark_no;
 494     }
 495 #   ifdef DEBUG_THREADS
 496         GC_printf1("Starting mark helper for mark number %ld\n", my_mark_no);
 497 #   endif
 498     GC_help_marker(my_mark_no);
 499   }
 500 }
 501
 502 extern long GC_markers;         /* Number of mark threads we would      */
 503                                 /* like to have.  Includes the          */
 504                                 /* initiating thread.                   */
 505
 506 pthread_t GC_mark_threads[MAX_MARKERS];
 507
 508 #define PTHREAD_CREATE REAL_FUNC(pthread_create)
 509
 510 static void start_mark_threads()
 511 {
 512     unsigned i;
 513     pthread_attr_t attr;
 514
 515     if (GC_markers > MAX_MARKERS) {
 516         WARN("Limiting number of mark threads\n", 0);
 517         GC_markers = MAX_MARKERS;
 518     }
 519     if (0 != pthread_attr_init(&attr)) ABORT("pthread_attr_init failed");
 520
 521     if (0 != pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED))
 522         ABORT("pthread_attr_setdetachstate failed");
 523 #   ifdef CONDPRINT
 524       if (GC_print_stats) {
 525         GC_printf1("Starting %ld marker threads\n", GC_markers - 1);
 526       }
 527 #   endif
 528     for (i = 0; i < GC_markers - 1; ++i) {
 529       if (0 != PTHREAD_CREATE(GC_mark_threads + i, &attr,
 530                               GC_mark_thread, (void *)(word)i)) {
 531         WARN("Marker thread creation failed, errno = %ld.\n", errno);
 532       }
 533     }
 534 }
 535
 536 #else  /* !PARALLEL_MARK */
 537
 538 static __inline__ void start_mark_threads()
 539 {
 540 }
 541
 542 #endif /* !PARALLEL_MARK */
 543
 544 void GC_suspend_handler(int sig)
 545 {
 546     int dummy;
 547     pthread_t my_thread = pthread_self();
 548     GC_thread me;
 549     sigset_t all_sigs;
 550     sigset_t old_sigs;
 551     int i;
 552     sigset_t mask;
 553 #   ifdef PARALLEL_MARK
 554         word my_mark_no = GC_mark_no;
 555         /* Marker can't proceed until we acknowledge.  Thus this is     */
 556         /* guaranteed to be the mark_no correspending to our            */
 557         /* suspension, i.e. the marker can't have incremented it yet.   */
 558 #   endif
 559
 560     if (sig != SIG_SUSPEND) ABORT("Bad signal in suspend_handler");
 561
 562 #if DEBUG_THREADS
 563     GC_printf1("Suspending 0x%x\n", my_thread);
 564 #endif
 565
 566     me = GC_lookup_thread(my_thread);
 567     /* The lookup here is safe, since I'm doing this on behalf  */
 568     /* of a thread which holds the allocation lock in order     */
 569     /* to stop the world.  Thus concurrent modification of the  */
 570     /* data structure is impossible.                            */
 571 #   ifdef SPARC
 572         me -> stack_ptr = (ptr_t)GC_save_regs_in_stack();
 573 #   else
 574         me -> stack_ptr = (ptr_t)(&dummy);
 575 #   endif
 576 #   ifdef IA64
 577         me -> backing_store_ptr = (ptr_t)GC_save_regs_in_stack();
 578 #   endif
 579
 580     /* Tell the thread that wants to stop the world that this   */
 581     /* thread has been stopped.  Note that sem_post() is        */
 582     /* the only async-signal-safe primitive in LinuxThreads.    */
 583     sem_post(&GC_suspend_ack_sem);
 584
 585     /* Wait until that thread tells us to restart by sending    */
 586     /* this thread a SIG_THR_RESTART signal.                    */
 587     /* SIG_THR_RESTART should be masked at this point.  Thus there      */
 588     /* is no race.                                              */
 589     if (sigfillset(&mask) != 0) ABORT("sigfillset() failed");
 590     if (sigdelset(&mask, SIG_THR_RESTART) != 0) ABORT("sigdelset() failed");
 591 #   ifdef NO_SIGNALS
 592       if (sigdelset(&mask, SIGINT) != 0) ABORT("sigdelset() failed");
 593       if (sigdelset(&mask, SIGQUIT) != 0) ABORT("sigdelset() failed");
 594       if (sigdelset(&mask, SIGTERM) != 0) ABORT("sigdelset() failed");
 595       if (sigdelset(&mask, SIGABRT) != 0) ABORT("sigdelset() failed");
 596 #   endif
 597     do {
 598             me->signal = 0;
 599             sigsuspend(&mask);             /* Wait for signal */
 600     } while (me->signal != SIG_THR_RESTART);
 601
 602 #if DEBUG_THREADS
 603     GC_printf1("Continuing 0x%x\n", my_thread);
 604 #endif
 605 }
 606
 607 void GC_restart_handler(int sig)
 608 {
 609     GC_thread me;
 610
 611     if (sig != SIG_THR_RESTART) ABORT("Bad signal in suspend_handler");
 612
 613     /* Let the GC_suspend_handler() know that we got a SIG_THR_RESTART. */
 614     /* The lookup here is safe, since I'm doing this on behalf  */
 615     /* of a thread which holds the allocation lock in order     */
 616     /* to stop the world.  Thus concurrent modification of the  */
 617     /* data structure is impossible.                            */
 618     me = GC_lookup_thread(pthread_self());
 619     me->signal = SIG_THR_RESTART;
 620
 621     /*
 622     ** Note: even if we didn't do anything useful here,
 623     ** it would still be necessary to have a signal handler,
 624     ** rather than ignoring the signals, otherwise
 625     ** the signals will not be delivered at all, and
 626     ** will thus not interrupt the sigsuspend() above.
 627     */
 628
 629 #if DEBUG_THREADS
 630     GC_printf1("In GC_restart_handler for 0x%x\n", pthread_self());
 631 #endif
 632 }
 633
 634 /* Defining INSTALL_LOOPING_SEGV_HANDLER causes SIGSEGV and SIGBUS to   */
 635 /* result in an infinite loop in a signal handler.  This can be very    */
 636 /* useful for debugging, since (as of RH7) gdb still seems to have      */
 637 /* serious problems with threads.                                       */
 638 #ifdef INSTALL_LOOPING_SEGV_HANDLER
 639 void GC_looping_handler(int sig)
 640 {
 641     GC_printf3("Signal %ld in thread %lx, pid %ld\n",
 642                sig, pthread_self(), getpid());
 643     for (;;);
 644 }
 645 #endif
 646
 647 GC_bool GC_thr_initialized = FALSE;
 648
 649 # define THREAD_TABLE_SZ 128    /* Must be power of 2   */
 650 volatile GC_thread GC_threads[THREAD_TABLE_SZ];
 651
 652 void GC_push_thread_structures GC_PROTO((void))
 653 {
 654     GC_push_all((ptr_t)(GC_threads), (ptr_t)(GC_threads)+sizeof(GC_threads));
 655 }
 656
 657 /* Add a thread to GC_threads.  We assume it wasn't already there.      */
 658 /* Caller holds allocation lock.                                        */
 659 GC_thread GC_new_thread(pthread_t id)
 660 {
 661     int hv = ((word)id) % THREAD_TABLE_SZ;
 662     GC_thread result;
 663     static struct GC_Thread_Rep first_thread;
 664     static GC_bool first_thread_used = FALSE;
 665
 666     if (!first_thread_used) {
 667         result = &first_thread;
 668         first_thread_used = TRUE;
 669     } else {
 670         result = (struct GC_Thread_Rep *)
 671                  GC_INTERNAL_MALLOC(sizeof(struct GC_Thread_Rep), NORMAL);
 672     }
 673     if (result == 0) return(0);
 674     result -> id = id;
 675     result -> next = GC_threads[hv];
 676     GC_threads[hv] = result;
 677     GC_ASSERT(result -> flags == 0 && result -> thread_blocked == 0);
 678     return(result);
 679 }
 680
 681 /* Delete a thread from GC_threads.  We assume it is there.     */
 682 /* (The code intentionally traps if it wasn't.)                 */
 683 /* Caller holds allocation lock.                                */
 684 void GC_delete_thread(pthread_t id)
 685 {
 686     int hv = ((word)id) % THREAD_TABLE_SZ;
 687     register GC_thread p = GC_threads[hv];
 688     register GC_thread prev = 0;
 689
 690     while (!pthread_equal(p -> id, id)) {
 691         prev = p;
 692         p = p -> next;
 693     }
 694     if (prev == 0) {
 695         GC_threads[hv] = p -> next;
 696     } else {
 697         prev -> next = p -> next;
 698     }
 699     GC_INTERNAL_FREE(p);
 700 }
 701
 702 /* If a thread has been joined, but we have not yet             */
 703 /* been notified, then there may be more than one thread        */
 704 /* in the table with the same pthread id.                       */
 705 /* This is OK, but we need a way to delete a specific one.      */
 706 void GC_delete_gc_thread(pthread_t id, GC_thread gc_id)
 707 {
 708     int hv = ((word)id) % THREAD_TABLE_SZ;
 709     register GC_thread p = GC_threads[hv];
 710     register GC_thread prev = 0;
 711
 712     while (p != gc_id) {
 713         prev = p;
 714         p = p -> next;
 715     }
 716     if (prev == 0) {
 717         GC_threads[hv] = p -> next;
 718     } else {
 719         prev -> next = p -> next;
 720     }
 721     GC_INTERNAL_FREE(p);
 722 }
 723
 724 /* Return a GC_thread corresponding to a given thread_t.        */
 725 /* Returns 0 if it's not there.                                 */
 726 /* Caller holds  allocation lock or otherwise inhibits          */
 727 /* updates.                                                     */
 728 /* If there is more than one thread with the given id we        */
 729 /* return the most recent one.                                  */
 730 GC_thread GC_lookup_thread(pthread_t id)
 731 {
 732     int hv = ((word)id) % THREAD_TABLE_SZ;
 733     register GC_thread p = GC_threads[hv];
 734
 735     while (p != 0 && !pthread_equal(p -> id, id)) p = p -> next;
 736     return(p);
 737 }
 738
 739 /* There seems to be a very rare thread stopping problem.  To help us  */
 740 /* debug that, we save the ids of the stopping thread. */
 741 pthread_t GC_stopping_thread;
 742 int GC_stopping_pid;
 743
 744 /* Caller holds allocation lock.        */
 745 void GC_stop_world()
 746 {
 747     pthread_t my_thread = pthread_self();
 748     register int i;
 749     register GC_thread p;
 750     register int n_live_threads = 0;
 751     register int result;
 752
 753     GC_stopping_thread = my_thread;    /* debugging only.      */
 754     GC_stopping_pid = getpid();                /* debugging only.      */
 755
 756     /* Make sure all free list construction has stopped before we start. */
 757     /* No new construction can start, since free list construction is   */
 758     /* required to acquire and release the GC lock before it starts,    */
 759     /* and we have the lock.                                            */
 760 #   ifdef PARALLEL_MARK
 761       GC_acquire_mark_lock();
 762       GC_ASSERT(GC_fl_builder_count == 0);
 763       /* We should have previously waited for it to become zero. */
 764 #   endif /* PARALLEL_MARK */
 765     for (i = 0; i < THREAD_TABLE_SZ; i++) {
 766       for (p = GC_threads[i]; p != 0; p = p -> next) {
 767         if (p -> id != my_thread) {
 768             if (p -> flags & FINISHED) continue;
 769             if (p -> thread_blocked) /* Will wait */ continue;
 770             n_live_threads++;
 771             #if DEBUG_THREADS
 772               GC_printf1("Sending suspend signal to 0x%x\n", p -> id);
 773             #endif
 774             result = pthread_kill(p -> id, SIG_SUSPEND);
 775             switch(result) {
 776                 case ESRCH:
 777                     /* Not really there anymore.  Possible? */
 778                     n_live_threads--;
 779                     break;
 780                 case 0:
 781                     break;
 782                 default:
 783                     ABORT("pthread_kill failed");
 784             }
 785         }
 786       }
 787     }
 788     for (i = 0; i < n_live_threads; i++) {
 789         if (0 != sem_wait(&GC_suspend_ack_sem))
 790             ABORT("sem_wait in handler failed");
 791     }
 792 #   ifdef PARALLEL_MARK
 793       GC_release_mark_lock();
 794 #   endif
 795     #if DEBUG_THREADS
 796       GC_printf1("World stopped 0x%x\n", pthread_self());
 797     #endif
 798 }
 799
 800 /* Caller holds allocation lock, and has held it continuously since     */
 801 /* the world stopped.                                                   */
 802 void GC_start_world()
 803 {
 804     pthread_t my_thread = pthread_self();
 805     register int i;
 806     register GC_thread p;
 807     register int n_live_threads = 0;
 808     register int result;
 809
 810 #   if DEBUG_THREADS
 811       GC_printf0("World starting\n");
 812 #   endif
 813
 814     for (i = 0; i < THREAD_TABLE_SZ; i++) {
 815       for (p = GC_threads[i]; p != 0; p = p -> next) {
 816         if (p -> id != my_thread) {
 817             if (p -> flags & FINISHED) continue;
 818             if (p -> thread_blocked) continue;
 819             n_live_threads++;
 820             #if DEBUG_THREADS
 821               GC_printf1("Sending restart signal to 0x%x\n", p -> id);
 822             #endif
 823             result = pthread_kill(p -> id, SIG_THR_RESTART);
 824             switch(result) {
 825                 case ESRCH:
 826                     /* Not really there anymore.  Possible? */
 827                     n_live_threads--;
 828                     break;
 829                 case 0:
 830                     break;
 831                 default:
 832                     ABORT("pthread_kill failed");
 833             }
 834         }
 835       }
 836     }
 837     #if DEBUG_THREADS
 838       GC_printf0("World started\n");
 839     #endif
 840     GC_stopping_thread = 0;  /* debugging only */
 841 }
 842
 843 # ifdef IA64
 844 #   define IF_IA64(x) x
 845 # else
 846 #   define IF_IA64(x)
 847 # endif
 848 /* We hold allocation lock.  Should do exactly the right thing if the   */
 849 /* world is stopped.  Should not fail if it isn't.                      */
 850 void GC_push_all_stacks()
 851 {
 852     int i;
 853     GC_thread p;
 854     ptr_t sp = GC_approx_sp();
 855     ptr_t lo, hi;
 856     /* On IA64, we also need to scan the register backing store. */
 857     IF_IA64(ptr_t bs_lo; ptr_t bs_hi;)
 858     pthread_t me = pthread_self();
 859
 860     if (!GC_thr_initialized) GC_thr_init();
 861     #if DEBUG_THREADS
 862         GC_printf1("Pushing stacks from thread 0x%lx\n", (unsigned long) me);
 863     #endif
 864     for (i = 0; i < THREAD_TABLE_SZ; i++) {
 865       for (p = GC_threads[i]; p != 0; p = p -> next) {
 866         if (p -> flags & FINISHED) continue;
 867         if (pthread_equal(p -> id, me)) {
 868 #           ifdef SPARC
 869                 lo = (ptr_t)GC_save_regs_in_stack();
 870 #           else
 871                 lo = GC_approx_sp();
 872 #           endif
 873             IF_IA64(bs_hi = (ptr_t)GC_save_regs_in_stack();)
 874         } else {
 875             lo = p -> stack_ptr;
 876             IF_IA64(bs_hi = p -> backing_store_ptr;)
 877         }
 878         if ((p -> flags & MAIN_THREAD) == 0) {
 879             hi = p -> stack_end;
 880             IF_IA64(bs_lo = p -> backing_store_end);
 881         } else {
 882             /* The original stack. */
 883             hi = GC_stackbottom;
 884             IF_IA64(bs_lo = BACKING_STORE_BASE;)
 885         }
 886         #if DEBUG_THREADS
 887             GC_printf3("Stack for thread 0x%lx = [%lx,%lx)\n",
 888                 (unsigned long) p -> id,
 889                 (unsigned long) lo, (unsigned long) hi);
 890         #endif
 891         if (0 == lo) ABORT("GC_push_all_stacks: sp not set!\n");
 892 #       ifdef STACK_GROWS_UP
 893           /* We got them backwards! */
 894           GC_push_all_stack(hi, lo);
 895 #       else
 896           GC_push_all_stack(lo, hi);
 897 #       endif
 898 #       ifdef IA64
 899           if (pthread_equal(p -> id, me)) {
 900             GC_push_all_eager(bs_lo, bs_hi);
 901           } else {
 902             GC_push_all_stack(bs_lo, bs_hi);
 903           }
 904 #       endif
 905       }
 906     }
 907 }
 908
 909 #ifdef USE_PROC_FOR_LIBRARIES
 910 int GC_segment_is_thread_stack(ptr_t lo, ptr_t hi)
 911 {
 912     int i;
 913     GC_thread p;
 914
 915 #   ifdef PARALLEL_MARK
 916       for (i = 0; i < GC_markers; ++i) {
 917         if (marker_sp[i] > lo & marker_sp[i] < hi) return 1;
 918       }
 919 #   endif
 920     for (i = 0; i < THREAD_TABLE_SZ; i++) {
 921       for (p = GC_threads[i]; p != 0; p = p -> next) {
 922         if (0 != p -> stack_end) {
 923 #         ifdef STACK_GROWS_UP
 924             if (p -> stack_end >= lo && p -> stack_end < hi) return 1;
 925 #         else /* STACK_GROWS_DOWN */
 926             if (p -> stack_end > lo && p -> stack_end <= hi) return 1;
 927 #         endif
 928         }
 929       }
 930     }
 931     return 0;
 932 }
 933 #endif /* USE_PROC_FOR_LIBRARIES */
 934
 935 #ifdef LINUX_THREADS
 936 /* Return the number of processors, or i<= 0 if it can't be determined. */
 937 int GC_get_nprocs()
 938 {
 939     /* Should be "return sysconf(_SC_NPROCESSORS_ONLN);" but that       */
 940     /* appears to be buggy in many cases.                               */
 941     /* We look for lines "cpu<n>" in /proc/stat.                        */
 942 #   define STAT_BUF_SIZE 4096
 943 #   if defined(GC_USE_LD_WRAP)
 944 #       define STAT_READ __real_read
 945 #   else
 946 #       define STAT_READ read
 947 #   endif
 948     char stat_buf[STAT_BUF_SIZE];
 949     int f;
 950     char c;
 951     word result = 1;
 952         /* Some old kernels only have a single "cpu nnnn ..."   */
 953         /* entry in /proc/stat.  We identify those as           */
 954         /* uniprocessors.                                       */
 955     size_t i, len = 0;
 956
 957     f = open("/proc/stat", O_RDONLY);
 958     if (f < 0 || (len = STAT_READ(f, stat_buf, STAT_BUF_SIZE)) < 100) {
 959         WARN("Couldn't read /proc/stat\n", 0);
 960         return -1;
 961     }
 962     for (i = 0; i < len - 100; ++i) {
 963         if (stat_buf[i] == '\n' && stat_buf[i+1] == 'c'
 964             && stat_buf[i+2] == 'p' && stat_buf[i+3] == 'u') {
 965             int cpu_no = atoi(stat_buf + i + 4);
 966             if (cpu_no >= result) result = cpu_no + 1;
 967         }
 968     }
 969     return result;
 970 }
 971 #endif /* LINUX_THREADS */
 972
 973 /* We hold the allocation lock. */
 974 void GC_thr_init()
 975 {
 976     int dummy;
 977     GC_thread t;
 978     struct sigaction act;
 979
 980     if (GC_thr_initialized) return;
 981     GC_thr_initialized = TRUE;
 982
 983     if (sem_init(&GC_suspend_ack_sem, 0, 0) != 0)
 984         ABORT("sem_init failed");
 985
 986     act.sa_flags = SA_RESTART;
 987     if (sigfillset(&act.sa_mask) != 0) {
 988         ABORT("sigfillset() failed");
 989     }
 990 #   ifdef NO_SIGNALS
 991       if (sigdelset(&act.sa_mask, SIGINT) != 0
 992           || sigdelset(&act.sa_mask, SIGQUIT != 0)
 993           || sigdelset(&act.sa_mask, SIGABRT != 0)
 994           || sigdelset(&act.sa_mask, SIGTERM != 0)) {
 995         ABORT("sigdelset() failed");
 996       }
 997 #   endif
 998
 999     /* SIG_THR_RESTART is unmasked by the handler when necessary.       */
1000     act.sa_handler = GC_suspend_handler;
1001     if (sigaction(SIG_SUSPEND, &act, NULL) != 0) {
1002         ABORT("Cannot set SIG_SUSPEND handler");
1003     }
1004
1005     act.sa_handler = GC_restart_handler;
1006     if (sigaction(SIG_THR_RESTART, &act, NULL) != 0) {
1007         ABORT("Cannot set SIG_THR_RESTART handler");
1008     }
1009 #   ifdef INSTALL_LOOPING_SEGV_HANDLER
1010         act.sa_handler = GC_looping_handler;
1011         if (sigaction(SIGSEGV, &act, NULL) != 0
1012             || sigaction(SIGBUS, &act, NULL) != 0) {
1013             ABORT("Cannot set SIGSEGV or SIGBUS looping handler");
1014         }
1015 #   endif  /* INSTALL_LOOPING_SEGV_HANDLER */
1016
1017     /* Add the initial thread, so we can stop it.       */
1018       t = GC_new_thread(pthread_self());
1019       t -> stack_ptr = (ptr_t)(&dummy);
1020       t -> flags = DETACHED | MAIN_THREAD;
1021
1022     /* Set GC_nprocs.  */
1023       {
1024         char * nprocs_string = GETENV("GC_NPROCS");
1025         GC_nprocs = -1;
1026         if (nprocs_string != NULL) GC_nprocs = atoi(nprocs_string);
1027       }
1028       if (GC_nprocs <= 0) {
1029 #       if defined(HPUX_THREADS)
1030           GC_nprocs = pthread_num_processors_np();
1031 #       endif
1032 #       if defined(OSF1_THREADS)
1033           GC_nprocs = 1;
1034 #       endif
1035 #       ifdef LINUX_THREADS
1036           GC_nprocs = GC_get_nprocs();
1037 #       endif
1038       }
1039       if (GC_nprocs <= 0) {
1040         WARN("GC_get_nprocs() returned %ld\n", GC_nprocs);
1041         GC_nprocs = 2;
1042 #       ifdef PARALLEL_MARK
1043           GC_markers = 1;
1044 #       endif
1045       } else {
1046 #       ifdef PARALLEL_MARK
1047           GC_markers = GC_nprocs;
1048 #       endif
1049       }
1050 #   ifdef PARALLEL_MARK
1051 #     ifdef CONDPRINT
1052         if (GC_print_stats) {
1053           GC_printf2("Number of processors = %ld, "
1054                  "number of marker threads = %ld\n", GC_nprocs, GC_markers);
1055         }
1056 #     endif
1057       if (GC_markers == 1) {
1058         GC_parallel = FALSE;
1059 #       ifdef CONDPRINT
1060           if (GC_print_stats) {
1061             GC_printf0("Single marker thread, turning off parallel marking\n");
1062           }
1063 #       endif
1064       } else {
1065         GC_parallel = TRUE;
1066       }
1067 #   endif
1068 }
1069
1070
1071 /* Perform all initializations, including those that    */
1072 /* may require allocation.                              */
1073 /* Called as constructor without allocation lock.       */
1074 /* Must be called before a second thread is created.    */
1075 void GC_full_init()
1076 {
1077     if (fully_initialized) return;
1078     if (!GC_is_initialized) GC_init();
1079     /* If we are using a parallel marker, start the helper threads.  */
1080 #     ifdef PARALLEL_MARK
1081         if (GC_parallel) start_mark_threads();
1082 #     endif
1083     /* Initialize thread local free lists if used.      */
1084 #   if defined(THREAD_LOCAL_ALLOC) && !defined(DBG_HDRS_ALL)
1085       LOCK();
1086       GC_init_thread_local(GC_lookup_thread(pthread_self()));
1087       UNLOCK();
1088 #   endif
1089     fully_initialized = TRUE;
1090 }
1091
1092
1093 int WRAP_FUNC(pthread_sigmask)(int how, const sigset_t *set, sigset_t *oset)
1094 {
1095     sigset_t fudged_set;
1096
1097     if (set != NULL && (how == SIG_BLOCK || how == SIG_SETMASK)) {
1098         fudged_set = *set;
1099         sigdelset(&fudged_set, SIG_SUSPEND);
1100         set = &fudged_set;
1101     }
1102     return(REAL_FUNC(pthread_sigmask)(how, set, oset));
1103 }
1104
1105 /* Wrappers for functions that are likely to block for an appreciable   */
1106 /* length of time.  Must be called in pairs, if at all.                 */
1107 /* Nothing much beyond the system call itself should be executed        */
1108 /* between these.                                                       */
1109
1110 void GC_start_blocking(void) {
1111 #   define SP_SLOP 128
1112     GC_thread me;
1113     LOCK();
1114     me = GC_lookup_thread(pthread_self());
1115     GC_ASSERT(!(me -> thread_blocked));
1116 #   ifdef SPARC
1117         me -> stack_ptr = (ptr_t)GC_save_regs_in_stack();
1118 #   else
1119         me -> stack_ptr = (ptr_t)GC_approx_sp();
1120 #   endif
1121 #   ifdef IA64
1122         me -> backing_store_ptr = (ptr_t)GC_save_regs_in_stack() + SP_SLOP;
1123 #   endif
1124     /* Add some slop to the stack pointer, since the wrapped call may   */
1125     /* end up pushing more callee-save registers.                       */
1126 #   ifdef STACK_GROWS_UP
1127         me -> stack_ptr += SP_SLOP;
1128 #   else
1129         me -> stack_ptr -= SP_SLOP;
1130 #   endif
1131     me -> thread_blocked = TRUE;
1132     UNLOCK();
1133 }
1134
1135 GC_end_blocking(void) {
1136     GC_thread me;
1137     LOCK();   /* This will block if the world is stopped.       */
1138     me = GC_lookup_thread(pthread_self());
1139     GC_ASSERT(me -> thread_blocked);
1140     me -> thread_blocked = FALSE;
1141     UNLOCK();
1142 }
1143
1144 /* A wrapper for the standard C sleep function  */
1145 int WRAP_FUNC(sleep) (unsigned int seconds)
1146 {
1147     int result;
1148
1149     GC_start_blocking();
1150     result = REAL_FUNC(sleep)(seconds);
1151     GC_end_blocking();
1152     return result;
1153 }
1154
1155 struct start_info {
1156     void *(*start_routine)(void *);
1157     void *arg;
1158     word flags;
1159     sem_t registered;           /* 1 ==> in our thread table, but       */
1160                                 /* parent hasn't yet noticed.           */
1161 };
1162
1163 /* Called at thread exit.                               */
1164 /* Never called for main thread.  That's OK, since it   */
1165 /* results in at most a tiny one-time leak.  And        */
1166 /* linuxthreads doesn't reclaim the main threads        */
1167 /* resources or id anyway.                              */
1168 void GC_thread_exit_proc(void *arg)
1169 {
1170     GC_thread me;
1171
1172     LOCK();
1173     me = GC_lookup_thread(pthread_self());
1174     GC_destroy_thread_local(me);
1175     if (me -> flags & DETACHED) {
1176         GC_delete_thread(pthread_self());
1177     } else {
1178         me -> flags |= FINISHED;
1179     }
1180 #   if defined(THREAD_LOCAL_ALLOC) && !defined(USE_PTHREAD_SPECIFIC) \
1181        && !defined(USE_HPUX_TLS) && !defined(DBG_HDRS_ALL)
1182       GC_remove_specific(GC_thread_key);
1183 #   endif
1184     if (GC_incremental && GC_collection_in_progress()) {
1185         int old_gc_no = GC_gc_no;
1186
1187         /* Make sure that no part of our stack is still on the mark stack, */
1188         /* since it's about to be unmapped.                                */
1189         while (GC_incremental && GC_collection_in_progress()
1190                && old_gc_no == GC_gc_no) {
1191             ENTER_GC();
1192             GC_collect_a_little_inner(1);
1193             EXIT_GC();
1194             UNLOCK();
1195             sched_yield();
1196             LOCK();
1197         }
1198     }
1199     UNLOCK();
1200 }
1201
1202 int WRAP_FUNC(pthread_join)(pthread_t thread, void **retval)
1203 {
1204     int result;
1205     GC_thread thread_gc_id;
1206
1207     LOCK();
1208     thread_gc_id = GC_lookup_thread(thread);
1209     /* This is guaranteed to be the intended one, since the thread id   */
1210     /* cant have been recycled by pthreads.                             */
1211     UNLOCK();
1212     result = REAL_FUNC(pthread_join)(thread, retval);
1213     if (result == 0) {
1214         LOCK();
1215         /* Here the pthread thread id may have been recycled. */
1216         GC_delete_gc_thread(thread, thread_gc_id);
1217         UNLOCK();
1218     }
1219     return result;
1220 }
1221
1222 int
1223 WRAP_FUNC(pthread_detach)(pthread_t thread)
1224 {
1225     int result;
1226     GC_thread thread_gc_id;
1227
1228     LOCK();
1229     thread_gc_id = GC_lookup_thread(thread);
1230     UNLOCK();
1231     result = REAL_FUNC(pthread_detach)(thread);
1232     if (result == 0) {
1233       LOCK();
1234       thread_gc_id -> flags |= DETACHED;
1235       /* Here the pthread thread id may have been recycled. */
1236       if (thread_gc_id -> flags & FINISHED) {
1237         GC_delete_gc_thread(thread, thread_gc_id);
1238       }
1239       UNLOCK();
1240     }
1241     return result;
1242 }
1243
1244 void * GC_start_routine(void * arg)
1245 {
1246     int dummy;
1247     struct start_info * si = arg;
1248     void * result;
1249     GC_thread me;
1250     pthread_t my_pthread;
1251     void *(*start)(void *);
1252     void *start_arg;
1253
1254     my_pthread = pthread_self();
1255 #   ifdef DEBUG_THREADS
1256         GC_printf1("Starting thread 0x%lx\n", my_pthread);
1257         GC_printf1("pid = %ld\n", (long) getpid());
1258         GC_printf1("sp = 0x%lx\n", (long) &arg);
1259 #   endif
1260     LOCK();
1261     me = GC_new_thread(my_pthread);
1262     me -> flags = si -> flags;
1263     me -> stack_ptr = 0;
1264     /* me -> stack_end = GC_linux_stack_base(); -- currently (11/99)    */
1265     /* doesn't work because the stack base in /proc/self/stat is the    */
1266     /* one for the main thread.  There is a strong argument that that's */
1267     /* a kernel bug, but a pervasive one.                               */
1268 #   ifdef STACK_GROWS_DOWN
1269       me -> stack_end = (ptr_t)(((word)(&dummy) + (GC_page_size - 1))
1270                                 & ~(GC_page_size - 1));
1271       me -> stack_ptr = me -> stack_end - 0x10;
1272         /* Needs to be plausible, since an asynchronous stack mark      */
1273         /* should not crash.                                            */
1274 #   else
1275       me -> stack_end = (ptr_t)((word)(&dummy) & ~(GC_page_size - 1));
1276       me -> stack_ptr = me -> stack_end + 0x10;
1277 #   endif
1278     /* This is dubious, since we may be more than a page into the stack, */
1279     /* and hence skip some of it, though it's not clear that matters.    */
1280 #   ifdef IA64
1281       me -> backing_store_end = (ptr_t)
1282                         (GC_save_regs_in_stack() & ~(GC_page_size - 1));
1283       /* This is also < 100% convincing.  We should also read this      */
1284       /* from /proc, but the hook to do so isn't there yet.             */
1285 #   endif /* IA64 */
1286     UNLOCK();
1287     start = si -> start_routine;
1288 #   ifdef DEBUG_THREADS
1289         GC_printf1("start_routine = 0x%lx\n", start);
1290 #   endif
1291     start_arg = si -> arg;
1292     sem_post(&(si -> registered));      /* Last action on si.   */
1293                                         /* OK to deallocate.    */
1294     pthread_cleanup_push(GC_thread_exit_proc, 0);
1295 #   if defined(THREAD_LOCAL_ALLOC) && !defined(DBG_HDRS_ALL)
1296         LOCK();
1297         GC_init_thread_local(me);
1298         UNLOCK();
1299 #   endif
1300     result = (*start)(start_arg);
1301 #if DEBUG_THREADS
1302         GC_printf1("Finishing thread 0x%x\n", pthread_self());
1303 #endif
1304     me -> status = result;
1305     me -> flags |= FINISHED;
1306     pthread_cleanup_pop(1);
1307     /* Cleanup acquires lock, ensuring that we can't exit               */
1308     /* while a collection that thinks we're alive is trying to stop     */
1309     /* us.                                                              */
1310     return(result);
1311 }
1312
1313 int
1314 WRAP_FUNC(pthread_create)(pthread_t *new_thread,
1315                   const pthread_attr_t *attr,
1316                   void *(*start_routine)(void *), void *arg)
1317 {
1318     int result;
1319     GC_thread t;
1320     pthread_t my_new_thread;
1321     int detachstate;
1322     word my_flags = 0;
1323     struct start_info * si;
1324         /* This is otherwise saved only in an area mmapped by the thread */
1325         /* library, which isn't visible to the collector.                */
1326
1327     LOCK();
1328     si = (struct start_info *)GC_INTERNAL_MALLOC(sizeof(struct start_info), NORMAL);
1329     UNLOCK();
1330     if (!fully_initialized) GC_full_init();
1331     if (0 == si) return(ENOMEM);
1332     sem_init(&(si -> registered), 0, 0);
1333     si -> start_routine = start_routine;
1334     si -> arg = arg;
1335     LOCK();
1336     if (!GC_thr_initialized) GC_thr_init();
1337     if (NULL == attr) {
1338         detachstate = PTHREAD_CREATE_JOINABLE;
1339     } else {
1340         pthread_attr_getdetachstate(attr, &detachstate);
1341     }
1342     if (PTHREAD_CREATE_DETACHED == detachstate) my_flags |= DETACHED;
1343     si -> flags = my_flags;
1344     UNLOCK();
1345 #   ifdef DEBUG_THREADS
1346         GC_printf1("About to start new thread from thread 0x%X\n",
1347                    pthread_self());
1348 #   endif
1349     result = REAL_FUNC(pthread_create)(new_thread, attr, GC_start_routine, si);
1350 #   ifdef DEBUG_THREADS
1351         GC_printf1("Started thread 0x%X\n", *new_thread);
1352 #   endif
1353     /* Wait until child has been added to the thread table.             */
1354     /* This also ensures that we hold onto si until the child is done   */
1355     /* with it.  Thus it doesn't matter whether it is otherwise         */
1356     /* visible to the collector.                                        */
1357         while (0 != sem_wait(&(si -> registered))) {
1358             if (EINTR != errno) ABORT("sem_wait failed");
1359         }
1360         sem_destroy(&(si -> registered));
1361         LOCK();
1362         GC_INTERNAL_FREE(si);
1363         UNLOCK();
1364     return(result);
1365 }
1366
1367 #ifdef GENERIC_COMPARE_AND_SWAP
1368   pthread_mutex_t GC_compare_and_swap_lock = PTHREAD_MUTEX_INITIALIZER;
1369
1370   GC_bool GC_compare_and_exchange(volatile GC_word *addr,
1371                                   GC_word old, GC_word new_val)
1372   {
1373     GC_bool result;
1374     pthread_mutex_lock(&GC_compare_and_swap_lock);
1375     if (*addr == old) {
1376       *addr = new_val;
1377       result = TRUE;
1378     } else {
1379       result = FALSE;
1380     }
1381     pthread_mutex_unlock(&GC_compare_and_swap_lock);
1382     return result;
1383   }
1384
1385   GC_word GC_atomic_add(volatile GC_word *addr, GC_word how_much)
1386   {
1387     GC_word old;
1388     pthread_mutex_lock(&GC_compare_and_swap_lock);
1389     old = *addr;
1390     *addr = old + how_much;
1391     pthread_mutex_unlock(&GC_compare_and_swap_lock);
1392     return old;
1393   }
1394
1395 #endif /* GENERIC_COMPARE_AND_SWAP */
1396 /* Spend a few cycles in a way that can't introduce contention with     */
1397 /* othre threads.                                                       */
1398 void GC_pause()
1399 {
1400     int i;
1401     volatile word dummy = 0;
1402
1403     for (i = 0; i < 10; ++i) {
1404 #     ifdef __GNUC__
1405         __asm__ __volatile__ (" " : : : "memory");
1406 #     else
1407         /* Something that's unlikely to be optimized away. */
1408         GC_noop(++dummy);
1409 #     endif
1410     }
1411 }
1412
1413 #define SPIN_MAX 1024   /* Maximum number of calls to GC_pause before   */
1414                         /* give up.                                     */
1415
1416 VOLATILE GC_bool GC_collecting = 0;
1417                         /* A hint that we're in the collector and       */
1418                         /* holding the allocation lock for an           */
1419                         /* extended period.                             */
1420
1421 #if !defined(USE_SPIN_LOCK) || defined(PARALLEL_MARK)
1422 /* If we don't want to use the below spinlock implementation, either    */
1423 /* because we don't have a GC_test_and_set implementation, or because   */
1424 /* we don't want to risk sleeping, we can still try spinning on         */
1425 /* pthread_mutex_trylock for a while.  This appears to be very          */
1426 /* beneficial in many cases.                                            */
1427 /* I suspect that under high contention this is nearly always better    */
1428 /* than the spin lock.  But it's a bit slower on a uniprocessor.        */
1429 /* Hence we still default to the spin lock.                             */
1430 /* This is also used to acquire the mark lock for the parallel          */
1431 /* marker.                                                              */
1432
1433 /* Here we use a strict exponential backoff scheme.  I don't know       */
1434 /* whether that's better or worse than the above.  We eventually        */
1435 /* yield by calling pthread_mutex_lock(); it never makes sense to       */
1436 /* explicitly sleep.                                                    */
1437
1438 void GC_generic_lock(pthread_mutex_t * lock)
1439 {
1440     unsigned pause_length = 1;
1441     unsigned i;
1442
1443     if (0 == pthread_mutex_trylock(lock)) return;
1444     for (; pause_length <= SPIN_MAX; pause_length <<= 1) {
1445         for (i = 0; i < pause_length; ++i) {
1446             GC_pause();
1447         }
1448         switch(pthread_mutex_trylock(lock)) {
1449             case 0:
1450                 return;
1451             case EBUSY:
1452                 break;
1453             default:
1454                 ABORT("Unexpected error from pthread_mutex_trylock");
1455         }
1456     }
1457     pthread_mutex_lock(lock);
1458 }
1459
1460 #endif /* !USE_SPIN_LOCK || PARALLEL_MARK */
1461
1462 #if defined(USE_SPIN_LOCK)
1463
1464 /* Reasonably fast spin locks.  Basically the same implementation */
1465 /* as STL alloc.h.  This isn't really the right way to do this.   */
1466 /* but until the POSIX scheduling mess gets straightened out ...  */
1467
1468 volatile unsigned int GC_allocate_lock = 0;
1469
1470
1471 void GC_lock()
1472 {
1473 #   define low_spin_max 30  /* spin cycles if we suspect uniprocessor */
1474 #   define high_spin_max SPIN_MAX /* spin cycles for multiprocessor */
1475     static unsigned spin_max = low_spin_max;
1476     unsigned my_spin_max;
1477     static unsigned last_spins = 0;
1478     unsigned my_last_spins;
1479     int i;
1480
1481     if (!GC_test_and_set(&GC_allocate_lock)) {
1482         return;
1483     }
1484     my_spin_max = spin_max;
1485     my_last_spins = last_spins;
1486     for (i = 0; i < my_spin_max; i++) {
1487         if (GC_collecting || GC_nprocs == 1) goto yield;
1488         if (i < my_last_spins/2 || GC_allocate_lock) {
1489             GC_pause();
1490             continue;
1491         }
1492         if (!GC_test_and_set(&GC_allocate_lock)) {
1493             /*
1494              * got it!
1495              * Spinning worked.  Thus we're probably not being scheduled
1496              * against the other process with which we were contending.
1497              * Thus it makes sense to spin longer the next time.
1498              */
1499             last_spins = i;
1500             spin_max = high_spin_max;
1501             return;
1502         }
1503     }
1504     /* We are probably being scheduled against the other process.  Sleep. */
1505     spin_max = low_spin_max;
1506 yield:
1507     for (i = 0;; ++i) {
1508         if (!GC_test_and_set(&GC_allocate_lock)) {
1509             return;
1510         }
1511 #       define SLEEP_THRESHOLD 12
1512                 /* nanosleep(<= 2ms) just spins under Linux.  We        */
1513                 /* want to be careful to avoid that behavior.           */
1514         if (i < SLEEP_THRESHOLD) {
1515             sched_yield();
1516         } else {
1517             struct timespec ts;
1518
1519             if (i > 24) i = 24;
1520                         /* Don't wait for more than about 15msecs, even */
1521                         /* under extreme contention.                    */
1522             ts.tv_sec = 0;
1523             ts.tv_nsec = 1 << i;
1524             nanosleep(&ts, 0);
1525         }
1526     }
1527 }
1528
1529 #else  /* !USE_SPINLOCK */
1530
1531 void GC_lock()
1532 {
1533     if (1 == GC_nprocs || GC_collecting) {
1534         pthread_mutex_lock(&GC_allocate_ml);
1535     } else {
1536         GC_generic_lock(&GC_allocate_ml);
1537     }
1538 }
1539
1540 #endif /* !USE_SPINLOCK */
1541
1542 #ifdef PARALLEL_MARK
1543
1544 #ifdef GC_ASSERTIONS
1545   pthread_t GC_mark_lock_holder = NO_THREAD;
1546 #endif
1547
1548 #ifdef IA64
1549   /* Ugly workaround for a linux threads bug in the final versions      */
1550   /* of glibc2.1.  Pthread_mutex_trylock sets the mutex owner           */
1551   /* field even when it fails to acquire the mutex.  This causes        */
1552   /* pthread_cond_wait to die.  Remove for glibc2.2.                    */
1553   /* According to the man page, we should use                           */
1554   /* PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP, but that isn't actually   */
1555   /* defined.                                                           */
1556   static pthread_mutex_t mark_mutex =
1557         {0, 0, 0, PTHREAD_MUTEX_ERRORCHECK_NP, {0, 0}};
1558 #else
1559   static pthread_mutex_t mark_mutex = PTHREAD_MUTEX_INITIALIZER;
1560 #endif
1561
1562 static pthread_cond_t mark_cv = PTHREAD_COND_INITIALIZER;
1563
1564 static pthread_cond_t builder_cv = PTHREAD_COND_INITIALIZER;
1565
1566 void GC_acquire_mark_lock()
1567 {
1568 /*
1569     if (pthread_mutex_lock(&mark_mutex) != 0) {
1570         ABORT("pthread_mutex_lock failed");
1571     }
1572 */
1573     GC_generic_lock(&mark_mutex);
1574 #   ifdef GC_ASSERTIONS
1575         GC_mark_lock_holder = pthread_self();
1576 #   endif
1577 }
1578
1579 void GC_release_mark_lock()
1580 {
1581     GC_ASSERT(GC_mark_lock_holder == pthread_self());
1582 #   ifdef GC_ASSERTIONS
1583         GC_mark_lock_holder = NO_THREAD;
1584 #   endif
1585     if (pthread_mutex_unlock(&mark_mutex) != 0) {
1586         ABORT("pthread_mutex_unlock failed");
1587     }
1588 }
1589
1590 void GC_wait_marker()
1591 {
1592     GC_ASSERT(GC_mark_lock_holder == pthread_self());
1593 #   ifdef GC_ASSERTIONS
1594         GC_mark_lock_holder = NO_THREAD;
1595 #   endif
1596     if (pthread_cond_wait(&mark_cv, &mark_mutex) != 0) {
1597         ABORT("pthread_cond_wait failed");
1598     }
1599     GC_ASSERT(GC_mark_lock_holder == NO_THREAD);
1600 #   ifdef GC_ASSERTIONS
1601         GC_mark_lock_holder = pthread_self();
1602 #   endif
1603 }
1604
1605 void GC_wait_builder()
1606 {
1607     GC_ASSERT(GC_mark_lock_holder == pthread_self());
1608 #   ifdef GC_ASSERTIONS
1609         GC_mark_lock_holder = NO_THREAD;
1610 #   endif
1611     if (pthread_cond_wait(&builder_cv, &mark_mutex) != 0) {
1612         ABORT("pthread_cond_wait failed");
1613     }
1614     GC_ASSERT(GC_mark_lock_holder == NO_THREAD);
1615 #   ifdef GC_ASSERTIONS
1616         GC_mark_lock_holder = pthread_self();
1617 #   endif
1618 }
1619
1620 void GC_notify_all_marker()
1621 {
1622     if (pthread_cond_broadcast(&mark_cv) != 0) {
1623         ABORT("pthread_cond_broadcast failed");
1624     }
1625 }
1626
1627 void GC_notify_all_builder()
1628 {
1629     GC_ASSERT(GC_mark_lock_holder == pthread_self());
1630     if (pthread_cond_broadcast(&builder_cv) != 0) {
1631         ABORT("pthread_cond_broadcast failed");
1632     }
1633 }
1634
1635 void GC_wait_for_reclaim()
1636 {
1637     GC_acquire_mark_lock();
1638     while (GC_fl_builder_count > 0) {
1639         GC_wait_builder();
1640     }
1641     GC_release_mark_lock();
1642 }
1643 #endif /* PARALLEL_MARK */
1644
1645 # endif /* LINUX_THREADS */
1646