Initial revision

1 files changed, 665 insertions, 0 deletions

diff --git a/gc/linux_threads.c b/gc/linux_threads.c
new file mode 100644
index 0000000..8287dce
--- /dev/null
+++ b/gc/linux_threads.c
@@ -0,0 +1,665 @@
+/* 
+ * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
+ * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
+ * Copyright (c) 1998 by Fergus Henderson.  All rights reserved.
+ *
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose,  provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ */
+/*
+ * Support code for LinuxThreads, the clone()-based kernel
+ * thread package for Linux which is included in libc6.
+ *
+ * This code relies on implementation details of LinuxThreads,
+ * (i.e. properties not guaranteed by the Pthread standard):
+ *
+ *	- the function GC_linux_thread_top_of_stack(void)
+ *	  relies on the way LinuxThreads lays out thread stacks
+ *	  in the address space.
+ *
+ * Note that there is a lot of code duplication between linux_threads.c
+ * and irix_threads.c; any changes made here may need to be reflected
+ * there too.
+ */
+
+/* #define DEBUG_THREADS 1 */
+
+/* ANSI C requires that a compilation unit contains something */
+# include "gc_priv.h"
+
+# if defined(LINUX_THREADS)
+
+# include <pthread.h>
+# include <time.h>
+# include <errno.h>
+# include <unistd.h>
+# include <sys/mman.h>
+# include <sys/time.h>
+# include <semaphore.h>
+
+#undef pthread_create
+#undef pthread_sigmask
+#undef pthread_join
+
+void GC_thr_init();
+
+#if 0
+void GC_print_sig_mask()
+{
+    sigset_t blocked;
+    int i;
+
+    if (pthread_sigmask(SIG_BLOCK, NULL, &blocked) != 0)
+    	ABORT("pthread_sigmask");
+    GC_printf0("Blocked: ");
+    for (i = 1; i <= MAXSIG; i++) {
+        if (sigismember(&blocked, i)) { GC_printf1("%ld ",(long) i); }
+    }
+    GC_printf0("\n");
+}
+#endif
+
+/* We use the allocation lock to protect thread-related data structures. */
+
+/* The set of all known threads.  We intercept thread creation and 	*/
+/* joins.  We never actually create detached threads.  We allocate all 	*/
+/* new thread stacks ourselves.  These allow us to maintain this	*/
+/* data structure.							*/
+/* Protected by GC_thr_lock.						*/
+/* Some of this should be declared volatile, but that's incosnsistent	*/
+/* with some library routine declarations.  		 		*/
+typedef struct GC_Thread_Rep {
+    struct GC_Thread_Rep * next;  /* More recently allocated threads	*/
+				  /* with a given pthread id come 	*/
+				  /* first.  (All but the first are	*/
+				  /* guaranteed to be dead, but we may  */
+				  /* not yet have registered the join.) */
+    pthread_t id;
+    word flags;
+#	define FINISHED 1   	/* Thread has exited.	*/
+#	define DETACHED 2	/* Thread is intended to be detached.	*/
+#	define MAIN_THREAD 4	/* True for the original thread only.	*/
+
+    ptr_t stack_end;
+    ptr_t stack_ptr;  		/* Valid only when stopped. */
+    int	signal;
+    void * status;		/* The value returned from the thread.  */
+    				/* Used only to avoid premature 	*/
+				/* reclamation of any data it might 	*/
+				/* reference.				*/
+} * GC_thread;
+
+GC_thread GC_lookup_thread(pthread_t id);
+
+/*
+ * The only way to suspend threads given the pthread interface is to send
+ * signals.  We can't use SIGSTOP directly, because we need to get the
+ * thread to save its stack pointer in the GC thread table before
+ * suspending.  So we have to reserve a signal of our own for this.
+ * This means we have to intercept client calls to change the signal mask.
+ * The linuxthreads package already uses SIGUSR1 and SIGUSR2,
+ * so we need to reuse something else.  I chose SIGPWR.
+ * (Perhaps SIGUNUSED would be a better choice.)
+ */
+#define SIG_SUSPEND SIGPWR
+
+#define SIG_RESTART SIGXCPU
+
+sem_t GC_suspend_ack_sem;
+
+/*
+GC_linux_thread_top_of_stack() relies on implementation details of
+LinuxThreads, namely that thread stacks are allocated on 2M boundaries
+and grow to no more than 2M.
+To make sure that we're using LinuxThreads and not some other thread
+package, we generate a dummy reference to `pthread_kill_other_threads_np'
+(was `__pthread_initial_thread_bos' but that disappeared),
+which is a symbol defined in LinuxThreads, but (hopefully) not in other
+thread packages.
+*/
+void (*dummy_var_to_force_linux_threads)() = pthread_kill_other_threads_np;
+
+#define LINUX_THREADS_STACK_SIZE  (2 * 1024 * 1024)
+
+static inline ptr_t GC_linux_thread_top_of_stack(void)
+{
+  char *sp = GC_approx_sp();
+  ptr_t tos = (ptr_t) (((unsigned long)sp | (LINUX_THREADS_STACK_SIZE - 1)) + 1);
+#if DEBUG_THREADS
+  GC_printf1("SP = %lx\n", (unsigned long)sp);
+  GC_printf1("TOS = %lx\n", (unsigned long)tos);
+#endif
+  return tos;
+}
+
+void GC_suspend_handler(int sig)
+{
+    int dummy;
+    pthread_t my_thread = pthread_self();
+    GC_thread me;
+    sigset_t all_sigs;
+    sigset_t old_sigs;
+    int i;
+    sigset_t mask;
+
+    if (sig != SIG_SUSPEND) ABORT("Bad signal in suspend_handler");
+
+#if DEBUG_THREADS
+    GC_printf1("Suspending 0x%x\n", my_thread);
+#endif
+
+    me = GC_lookup_thread(my_thread);
+    /* The lookup here is safe, since I'm doing this on behalf  */
+    /* of a thread which holds the allocation lock in order	*/
+    /* to stop the world.  Thus concurrent modification of the	*/
+    /* data structure is impossible.				*/
+    me -> stack_ptr = (ptr_t)(&dummy);
+    me -> stack_end = GC_linux_thread_top_of_stack();
+
+    /* Tell the thread that wants to stop the world that this   */
+    /* thread has been stopped.  Note that sem_post() is  	*/
+    /* the only async-signal-safe primitive in LinuxThreads.    */
+    sem_post(&GC_suspend_ack_sem);
+
+    /* Wait until that thread tells us to restart by sending    */
+    /* this thread a SIG_RESTART signal.			*/
+    /* SIG_RESTART should be masked at this point.  Thus there	*/
+    /* is no race.						*/
+    if (sigfillset(&mask) != 0) ABORT("sigfillset() failed");
+    if (sigdelset(&mask, SIG_RESTART) != 0) ABORT("sigdelset() failed");
+    do {
+	    me->signal = 0;
+	    sigsuspend(&mask);             /* Wait for signal */
+    } while (me->signal != SIG_RESTART);
+
+#if DEBUG_THREADS
+    GC_printf1("Continuing 0x%x\n", my_thread);
+#endif
+}
+
+void GC_restart_handler(int sig)
+{
+    GC_thread me;
+
+    if (sig != SIG_RESTART) ABORT("Bad signal in suspend_handler");
+
+    /* Let the GC_suspend_handler() know that we got a SIG_RESTART. */
+    /* The lookup here is safe, since I'm doing this on behalf  */
+    /* of a thread which holds the allocation lock in order	*/
+    /* to stop the world.  Thus concurrent modification of the	*/
+    /* data structure is impossible.				*/
+    me = GC_lookup_thread(pthread_self());
+    me->signal = SIG_RESTART;
+
+    /*
+    ** Note: even if we didn't do anything useful here,
+    ** it would still be necessary to have a signal handler,
+    ** rather than ignoring the signals, otherwise
+    ** the signals will not be delivered at all, and
+    ** will thus not interrupt the sigsuspend() above.
+    */
+
+#if DEBUG_THREADS
+    GC_printf1("In GC_restart_handler for 0x%x\n", pthread_self());
+#endif
+}
+
+GC_bool GC_thr_initialized = FALSE;
+
+# define THREAD_TABLE_SZ 128	/* Must be power of 2	*/
+volatile GC_thread GC_threads[THREAD_TABLE_SZ];
+
+/* Add a thread to GC_threads.  We assume it wasn't already there.	*/
+/* Caller holds allocation lock.					*/
+GC_thread GC_new_thread(pthread_t id)
+{
+    int hv = ((word)id) % THREAD_TABLE_SZ;
+    GC_thread result;
+    static struct GC_Thread_Rep first_thread;
+    static GC_bool first_thread_used = FALSE;
+    
+    if (!first_thread_used) {
+    	result = &first_thread;
+    	first_thread_used = TRUE;
+    	/* Dont acquire allocation lock, since we may already hold it. */
+    } else {
+        result = (struct GC_Thread_Rep *)
+        	 GC_generic_malloc_inner(sizeof(struct GC_Thread_Rep), NORMAL);
+    }
+    if (result == 0) return(0);
+    result -> id = id;
+    result -> next = GC_threads[hv];
+    GC_threads[hv] = result;
+    /* result -> flags = 0; */
+    return(result);
+}
+
+/* Delete a thread from GC_threads.  We assume it is there.	*/
+/* (The code intentionally traps if it wasn't.)			*/
+/* Caller holds allocation lock.				*/
+void GC_delete_thread(pthread_t id)
+{
+    int hv = ((word)id) % THREAD_TABLE_SZ;
+    register GC_thread p = GC_threads[hv];
+    register GC_thread prev = 0;
+    
+    while (!pthread_equal(p -> id, id)) {
+        prev = p;
+        p = p -> next;
+    }
+    if (prev == 0) {
+        GC_threads[hv] = p -> next;
+    } else {
+        prev -> next = p -> next;
+    }
+}
+
+/* If a thread has been joined, but we have not yet		*/
+/* been notified, then there may be more than one thread 	*/
+/* in the table with the same pthread id.			*/
+/* This is OK, but we need a way to delete a specific one.	*/
+void GC_delete_gc_thread(pthread_t id, GC_thread gc_id)
+{
+    int hv = ((word)id) % THREAD_TABLE_SZ;
+    register GC_thread p = GC_threads[hv];
+    register GC_thread prev = 0;
+
+    while (p != gc_id) {
+        prev = p;
+        p = p -> next;
+    }
+    if (prev == 0) {
+        GC_threads[hv] = p -> next;
+    } else {
+        prev -> next = p -> next;
+    }
+}
+
+/* Return a GC_thread corresponding to a given thread_t.	*/
+/* Returns 0 if it's not there.					*/
+/* Caller holds  allocation lock or otherwise inhibits 		*/
+/* updates.							*/
+/* If there is more than one thread with the given id we 	*/
+/* return the most recent one.					*/
+GC_thread GC_lookup_thread(pthread_t id)
+{
+    int hv = ((word)id) % THREAD_TABLE_SZ;
+    register GC_thread p = GC_threads[hv];
+    
+    while (p != 0 && !pthread_equal(p -> id, id)) p = p -> next;
+    return(p);
+}
+
+/* Caller holds allocation lock.	*/
+void GC_stop_world()
+{
+    pthread_t my_thread = pthread_self();
+    register int i;
+    register GC_thread p;
+    register int n_live_threads = 0;
+    register int result;
+
+    for (i = 0; i < THREAD_TABLE_SZ; i++) {
+      for (p = GC_threads[i]; p != 0; p = p -> next) {
+        if (p -> id != my_thread) {
+            if (p -> flags & FINISHED) continue;
+            n_live_threads++;
+	    #if DEBUG_THREADS
+	      GC_printf1("Sending suspend signal to 0x%x\n", p -> id);
+	    #endif
+            result = pthread_kill(p -> id, SIG_SUSPEND);
+	    switch(result) {
+                case ESRCH:
+                    /* Not really there anymore.  Possible? */
+                    n_live_threads--;
+                    break;
+                case 0:
+                    break;
+                default:
+                    ABORT("pthread_kill failed");
+            }
+        }
+      }
+    }
+    for (i = 0; i < n_live_threads; i++) {
+    	sem_wait(&GC_suspend_ack_sem);
+    }
+    #if DEBUG_THREADS
+    GC_printf1("World stopped 0x%x\n", pthread_self());
+    #endif
+}
+
+/* Caller holds allocation lock.	*/
+void GC_start_world()
+{
+    pthread_t my_thread = pthread_self();
+    register int i;
+    register GC_thread p;
+    register int n_live_threads = 0;
+    register int result;
+    
+#   if DEBUG_THREADS
+      GC_printf0("World starting\n");
+#   endif
+
+    for (i = 0; i < THREAD_TABLE_SZ; i++) {
+      for (p = GC_threads[i]; p != 0; p = p -> next) {
+        if (p -> id != my_thread) {
+            if (p -> flags & FINISHED) continue;
+            n_live_threads++;
+	    #if DEBUG_THREADS
+	      GC_printf1("Sending restart signal to 0x%x\n", p -> id);
+	    #endif
+            result = pthread_kill(p -> id, SIG_RESTART);
+	    switch(result) {
+                case ESRCH:
+                    /* Not really there anymore.  Possible? */
+                    n_live_threads--;
+                    break;
+                case 0:
+                    break;
+                default:
+                    ABORT("pthread_kill failed");
+            }
+        }
+      }
+    }
+    #if DEBUG_THREADS
+      GC_printf0("World started\n");
+    #endif
+}
+
+/* We hold allocation lock.  We assume the world is stopped.	*/
+void GC_push_all_stacks()
+{
+    register int i;
+    register GC_thread p;
+    register ptr_t sp = GC_approx_sp();
+    register ptr_t lo, hi;
+    pthread_t me = pthread_self();
+    
+    if (!GC_thr_initialized) GC_thr_init();
+    #if DEBUG_THREADS
+        GC_printf1("Pushing stacks from thread 0x%lx\n", (unsigned long) me);
+    #endif
+    for (i = 0; i < THREAD_TABLE_SZ; i++) {
+      for (p = GC_threads[i]; p != 0; p = p -> next) {
+        if (p -> flags & FINISHED) continue;
+        if (pthread_equal(p -> id, me)) {
+	    lo = GC_approx_sp();
+	} else {
+	    lo = p -> stack_ptr;
+	}
+        if ((p -> flags & MAIN_THREAD) == 0) {
+	    if (pthread_equal(p -> id, me)) {
+		hi = GC_linux_thread_top_of_stack();
+	    } else {
+		hi = p -> stack_end;
+	    }
+        } else {
+            /* The original stack. */
+            hi = GC_stackbottom;
+        }
+        #if DEBUG_THREADS
+            GC_printf3("Stack for thread 0x%lx = [%lx,%lx)\n",
+    	        (unsigned long) p -> id,
+		(unsigned long) lo, (unsigned long) hi);
+        #endif
+        GC_push_all_stack(lo, hi);
+      }
+    }
+}
+
+
+/* We hold the allocation lock.	*/
+void GC_thr_init()
+{
+    GC_thread t;
+    struct sigaction act;
+
+    if (GC_thr_initialized) return;
+    GC_thr_initialized = TRUE;
+
+    if (sem_init(&GC_suspend_ack_sem, 0, 0) != 0)
+    	ABORT("sem_init failed");
+
+    act.sa_flags = SA_RESTART;
+    if (sigfillset(&act.sa_mask) != 0) {
+    	ABORT("sigfillset() failed");
+    }
+    /* SIG_RESTART is unmasked by the handler when necessary. 	*/
+    act.sa_handler = GC_suspend_handler;
+    if (sigaction(SIG_SUSPEND, &act, NULL) != 0) {
+    	ABORT("Cannot set SIG_SUSPEND handler");
+    }
+
+    act.sa_handler = GC_restart_handler;
+    if (sigaction(SIG_RESTART, &act, NULL) != 0) {
+    	ABORT("Cannot set SIG_SUSPEND handler");
+    }
+
+    /* Add the initial thread, so we can stop it.	*/
+      t = GC_new_thread(pthread_self());
+      t -> stack_ptr = 0;
+      t -> flags = DETACHED | MAIN_THREAD;
+}
+
+int GC_pthread_sigmask(int how, const sigset_t *set, sigset_t *oset)
+{
+    sigset_t fudged_set;
+    
+    if (set != NULL && (how == SIG_BLOCK || how == SIG_SETMASK)) {
+        fudged_set = *set;
+        sigdelset(&fudged_set, SIG_SUSPEND);
+        set = &fudged_set;
+    }
+    return(pthread_sigmask(how, set, oset));
+}
+
+struct start_info {
+    void *(*start_routine)(void *);
+    void *arg;
+    word flags;
+    sem_t registered;   	/* 1 ==> in our thread table, but 	*/
+				/* parent hasn't yet noticed.		*/
+};
+
+
+void GC_thread_exit_proc(void *arg)
+{
+    GC_thread me;
+    struct start_info * si = arg;
+
+    LOCK();
+    me = GC_lookup_thread(pthread_self());
+    if (me -> flags & DETACHED) {
+    	GC_delete_thread(pthread_self());
+    } else {
+	me -> flags |= FINISHED;
+    }
+    UNLOCK();
+}
+
+int GC_pthread_join(pthread_t thread, void **retval)
+{
+    int result;
+    GC_thread thread_gc_id;
+    
+    LOCK();
+    thread_gc_id = GC_lookup_thread(thread);
+    /* This is guaranteed to be the intended one, since the thread id	*/
+    /* cant have been recycled by pthreads.				*/
+    UNLOCK();
+    result = pthread_join(thread, retval);
+    LOCK();
+    /* Here the pthread thread id may have been recycled. */
+    GC_delete_gc_thread(thread, thread_gc_id);
+    UNLOCK();
+    return result;
+}
+
+void * GC_start_routine(void * arg)
+{
+    struct start_info * si = arg;
+    void * result;
+    GC_thread me;
+    pthread_t my_pthread;
+    void *(*start)(void *);
+    void *start_arg;
+
+    my_pthread = pthread_self();
+    LOCK();
+    me = GC_new_thread(my_pthread);
+    me -> flags = si -> flags;
+    me -> stack_ptr = 0;
+    me -> stack_end = 0;
+    UNLOCK();
+    start = si -> start_routine;
+    start_arg = si -> arg;
+    sem_post(&(si -> registered));
+    pthread_cleanup_push(GC_thread_exit_proc, si);
+#   ifdef DEBUG_THREADS
+        GC_printf1("Starting thread 0x%lx\n", pthread_self());
+        GC_printf1("pid = %ld\n", (long) getpid());
+        GC_printf1("sp = 0x%lx\n", (long) &arg);
+	GC_printf1("start_routine = 0x%lx\n", start);
+#   endif
+    result = (*start)(start_arg);
+#if DEBUG_THREADS
+        GC_printf1("Finishing thread 0x%x\n", pthread_self());
+#endif
+    me -> status = result;
+    me -> flags |= FINISHED;
+    pthread_cleanup_pop(1);
+    /* Cleanup acquires lock, ensuring that we can't exit		*/
+    /* while a collection that thinks we're alive is trying to stop     */
+    /* us.								*/
+    return(result);
+}
+
+int
+GC_pthread_create(pthread_t *new_thread,
+		  const pthread_attr_t *attr,
+                  void *(*start_routine)(void *), void *arg)
+{
+    int result;
+    GC_thread t;
+    pthread_t my_new_thread;
+    void * stack;
+    size_t stacksize;
+    pthread_attr_t new_attr;
+    int detachstate;
+    word my_flags = 0;
+    struct start_info * si = GC_malloc(sizeof(struct start_info)); 
+	/* This is otherwise saved only in an area mmapped by the thread */
+	/* library, which isn't visible to the collector.		 */
+
+    if (0 == si) return(ENOMEM);
+    sem_init(&(si -> registered), 0, 0);
+    si -> start_routine = start_routine;
+    si -> arg = arg;
+    LOCK();
+    if (!GC_thr_initialized) GC_thr_init();
+    if (NULL == attr) {
+        stack = 0;
+	(void) pthread_attr_init(&new_attr);
+    } else {
+        new_attr = *attr;
+    }
+    pthread_attr_getdetachstate(&new_attr, &detachstate);
+    if (PTHREAD_CREATE_DETACHED == detachstate) my_flags |= DETACHED;
+    si -> flags = my_flags;
+    UNLOCK();
+    result = pthread_create(new_thread, &new_attr, GC_start_routine, si);
+    /* Wait until child has been added to the thread table.		*/
+    /* This also ensures that we hold onto si until the child is done	*/
+    /* with it.  Thus it doesn't matter whether it is otherwise		*/
+    /* visible to the collector.					*/
+        if (0 != sem_wait(&(si -> registered))) ABORT("sem_wait failed");
+        sem_destroy(&(si -> registered));
+    /* pthread_attr_destroy(&new_attr); */
+    /* pthread_attr_destroy(&new_attr); */
+    return(result);
+}
+
+GC_bool GC_collecting = 0;
+			/* A hint that we're in the collector and       */
+                        /* holding the allocation lock for an           */
+                        /* extended period.                             */
+
+/* Reasonably fast spin locks.  Basically the same implementation */
+/* as STL alloc.h.  This isn't really the right way to do this.   */
+/* but until the POSIX scheduling mess gets straightened out ...  */
+
+volatile unsigned int GC_allocate_lock = 0;
+
+
+void GC_lock()
+{
+#   define low_spin_max 30  /* spin cycles if we suspect uniprocessor */
+#   define high_spin_max 1000 /* spin cycles for multiprocessor */
+    static unsigned spin_max = low_spin_max;
+    unsigned my_spin_max;
+    static unsigned last_spins = 0;
+    unsigned my_last_spins;
+    volatile unsigned junk;
+#   define PAUSE junk *= junk; junk *= junk; junk *= junk; junk *= junk
+    int i;
+
+    if (!GC_test_and_set(&GC_allocate_lock)) {
+        return;
+    }
+    junk = 0;
+    my_spin_max = spin_max;
+    my_last_spins = last_spins;
+    for (i = 0; i < my_spin_max; i++) {
+        if (GC_collecting) goto yield;
+        if (i < my_last_spins/2 || GC_allocate_lock) {
+            PAUSE; 
+            continue;
+        }
+        if (!GC_test_and_set(&GC_allocate_lock)) {
+	    /*
+             * got it!
+             * Spinning worked.  Thus we're probably not being scheduled
+             * against the other process with which we were contending.
+             * Thus it makes sense to spin longer the next time.
+	     */
+            last_spins = i;
+            spin_max = high_spin_max;
+            return;
+        }
+    }
+    /* We are probably being scheduled against the other process.  Sleep. */
+    spin_max = low_spin_max;
+yield:
+    for (i = 0;; ++i) {
+        if (!GC_test_and_set(&GC_allocate_lock)) {
+            return;
+        }
+#       define SLEEP_THRESHOLD 12
+		/* nanosleep(<= 2ms) just spins under Linux.  We	*/
+		/* want to be careful to avoid that behavior.		*/
+        if (i < SLEEP_THRESHOLD) {
+            sched_yield();
+	} else {
+	    struct timespec ts;
+	
+	    if (i > 26) i = 26;
+			/* Don't wait for more than about 60msecs, even	*/
+			/* under extreme contention.			*/
+	    ts.tv_sec = 0;
+	    ts.tv_nsec = 1 << i;
+	    nanosleep(&ts, 0);
+	}
+    }
+}
+
+# endif /* LINUX_THREADS */
+