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