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