/*
 * Copyright (c) 1994, 1996 by Bennet Yee.
 *
 * This material was developed by the author.  Permission to copy this
 * software, to redistribute it, and to use it for any purpose is hereby
 * granted, subject to the following five restrictions.
 *
 * 1. Any copy made of this software must include this copyright notice in
 * full.
 *
 * 2. All materials containing this software or derivatives thereof must
 * provide this software in source form or provide a means of obtaining
 * this software in source form; no fees may be charged for this software
 * except those for covering media costs and handling.
 *
 * 3. All materials developed as a consequence of the use of this software
 * shall duly acknowledge such use, in accordance with the usual standards
 * of acknowledging credit in academic research.
 *
 * 4. The author makes no warranty or representation that the operation
 * of this software will be error-free, and the author is under no
 * obligation to provide any services, by way of maintenance, update, or
 * otherwise.
 *
 * 5. In conjunction with products arising from the use of this material,
 * there shall be no use of the names of the author, of Carnegie-Mellon
 * University or University of California, nor of any adaptation thereof
 * in any advertising, promotional, or sales literature without prior
 * written consent from the author, Carnegie-Mellon University, and
 * University of California in each case.
 *
 * If you have questions, you can contact the author at bsy@cs.ucsd.edu
 *
 * Users of this software is requested to make their best efforts (a) to
 * return to the author any improvements or extensions that they make, so
 * that these may be included in future releases; (b) to document clearly
 * any improvements or extensions made to this software; and (c) to inform
 * the author of noteworthy uses of this software.  Any improvements or
 * extensions to this software may be placed under different copyright
 * restrictions by the author of those improvements or extensions.  That
 * those improvements or extensions be placed under the same copyright as
 * this software is encouraged.
 */

/*
 * dread thread -- portable mostly machine independent coroutine threads.
 *
 * Created, bsy@cs.cmu.edu, 1994.
 * Added stack overflow checks, bsy@cs.ucsd.edu, 1996.
 *
 * To do:
 *
 * I/O thread wait.
 * Preemption via timers / signals.
 */
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

#include "dreadthread.h"

#define MAGIC_TEST      1

#define DEBUG           0
#define DEBUG_QUEUES    0
#define DEBUG_SIGBLOCK  0
#define SIG_DISABLE     0
#if DEBUG
# if 1
#  define DBOUT(args) do { printf args; fflush(stdout); } while (0)
# else
#  include <stdarg.h>
char dboutbuf[4096];
#  define DBOUT(args) do { dbprint args; } while (0)
void dbprint(char *fmt, ...)
{
  va_list alist;
  int nch;
  va_start(alist,fmt);
  nch = vsprintf(dboutbuf,fmt,alist);
  write(1,dboutbuf,nch);
  va_end(alist);
}
# endif
# define  SHOWTHREAD  do { \
    printf("Th: %p\n", (void *) dthr_cur_thread); \
  } while (0)
# if  !defined(SIG_DISABLE)
#  define SIG_DISABLE 1
# endif
#else
# define  DBOUT(args)
# define  SHOWTHREAD
#endif

#define DREAD_THREAD_CSW_CSW    0
#define DREAD_THREAD_CSW_NORM   1
#define DREAD_THREAD_CSW_CREATE   2
#define DREAD_THREAD_CSW_EXIT   3
#define DREAD_THREAD_CSW_MAX    4

struct dthr_thread            *dthr_cur_thread = 0;

static struct dthr_stack      dthr_topmost_stack;
static struct dthr_thread     dthr_topmost_thread;
static struct dthr_chain      dthr_free_stacks, dthr_active_stacks,
                              dthr_runq, dthr_newq;
static struct dthr_semaphore  dthr_newq_sema;
static struct dthr_event      dthr_newq_event;
static dthr_ctxt_t            dthr_deadlock;
int       (*dthr_on_deadlock)() = 0;

#if DEBUG_QUEUES
void dthr_show_queues(void)
{
#define SHOW(var) fprintf(stderr,"\n" #var ":\n"); dthr_chain_show(stderr,&var);
  SHOW(dthr_free_stacks);
  SHOW(dthr_active_stacks);
  SHOW(dthr_runq);
  SHOW(dthr_newq);
  SHOW(dthr_newq_event.threadq);
  SHOW(dthr_newq_sema.threadq);
}
#else
# define  dthr_show_queues()  do { ;} while (0)
#endif


/* may eventually want to sort stacks by addresses */
struct dthr_thread  *dthr_this_thread(void)
{
  int                         stack_var;
  register caddr_t            stack_addr = (caddr_t) &stack_var;
  register struct dthr_chain  *p;

  DBOUT(("dthr_this_thread:  scanning for stack addr %p\n",
         (void *) stack_addr));
  for (p = dthr_active_stacks.next; p != &dthr_active_stacks; p = p->next) {
#if MAGIC_TEST
    if (((struct dthr_stack *) p)->magic != DREAD_THREAD_STACK_MAGIC) {
      fprintf(stderr,
              "dthr_thread: stack descriptor corruption"
              " detected by dthr_this_thread()\n");
      abort();
    }
#endif
#if DREAD_THREAD_STACK_GROWS_DOWN
    if (((struct dthr_stack *) p)->stack_top <= stack_addr
        && stack_addr <= ((struct dthr_stack *) p)->stack_base)
      break;
#else
    if (((struct dthr_stack *) p)->stack_base <= stack_addr
        && stack_addr <= ((struct dthr_stack *) p)->stack_top)
      break;
#endif
  }
  if (DEBUG) {  /* DCE */
    if (p == &dthr_active_stacks) {
      printf("dthr_this_thread: NOT FOUND, assuming TOPMOST (%p)\n",
             (void *) &dthr_topmost_thread);
    } else {
      printf("dthr_this_thread: thread %p",
             (void *) ((struct dthr_stack *) p)->thread);
    }
  }
  return (p == &dthr_active_stacks) ?
      &dthr_topmost_thread : ((struct dthr_stack *) p)->thread;
}

static void dthr_csw(struct dthr_stack  *target, int  op);

void dthr_thread_yield(void)
{
  struct dthr_thread  *next_runnable;

  SHOWTHREAD;
  DBOUT(("dthr_thread_yield\n"));
  next_runnable = (struct dthr_thread *) DREAD_THREAD_CHAIN_DEQUEUE(&dthr_runq);
  if (next_runnable) {
#if MAGIC_TEST
    if (next_runnable->magic != DREAD_THREAD_TH_MAGIC) {
      fprintf(stderr,
              "dthr_thread:  thread structure corruption detected"
              " in dthr_thread_yield()\n");
      abort();
    }
#endif
    DBOUT((" found runnable thread %p\n",(void *) next_runnable));
    (void) dthr_chain_enqueue(&dthr_runq,&dthr_cur_thread->link);
    dthr_csw(next_runnable->stack,DREAD_THREAD_CSW_NORM);
  }
  SHOWTHREAD;
  DBOUT(("LV dthr_thread_yield\n"));
}

struct dthr_semaphore *dthr_semaphore_init(struct dthr_semaphore  *sema,
               int      init)
{
  sema->value = init;
  (void) dthr_chain_init(&sema->threadq);
  sema->magic = DREAD_THREAD_SEMA_MAGIC;
  return sema;
}

/* current thread must already be enqueued somewhere */
static void dthr_thread_sleep(int leave)
{
  struct dthr_thread  *next_thread;

  SHOWTHREAD;
  DBOUT(("dthr_thread_sleep(%d):",leave));
  dthr_show_queues();

  do {
    next_thread = (struct dthr_thread *) DREAD_THREAD_CHAIN_DEQUEUE(&dthr_runq);
    DBOUT((" %sthread found %p\n",next_thread?"":"NO ",(void *) next_thread));

  } while (!next_thread && dthr_on_deadlock && (*dthr_on_deadlock)());

  if (!next_thread) {
    dthr_load_ctxt(&dthr_deadlock,1);
    fprintf(stderr,"dthr_thread:  DEADLOCK load context returned\n");
    abort();
  }
#if MAGIC_TEST
  if (next_thread->magic != DREAD_THREAD_TH_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  thread structure corruption detected"
            " in dthr_thread_sleep(%d)\n",
            leave);
    abort();
  }
#endif
  dthr_csw(next_thread->stack,leave ? DREAD_THREAD_CSW_EXIT
           : DREAD_THREAD_CSW_NORM);
  SHOWTHREAD;
  DBOUT(("LV dthr_thread_sleep\n"));
}

int dthr_semaphore_try(struct dthr_semaphore  *sema)
{
  register int  rv;

  SHOWTHREAD;
  DBOUT(("dthr_semaphore_try(%p):",(void *) sema));
#if MAGIC_TEST
  if (sema->magic != DREAD_THREAD_SEMA_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  semaphore structure corruption detected"
            " in dthr_semaphore_try(%p)\n",
            (void *) sema);
    abort();
  }
#endif
  if (sema->value == 0) {
    rv = 0;
  } else {
    sema->value--;
    rv = 1;
  }
  DBOUT(("\n"));
  return rv;
}

static void dthr_semaphore_take_no_yield(struct dthr_semaphore  *sema)
{
  SHOWTHREAD;
  DBOUT(("dthr_semaphore_take_no_yield(%p)\n",(void *) sema));
#if MAGIC_TEST
  if (sema->magic != DREAD_THREAD_SEMA_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  semaphore structure corruption detected"
            " in dthr_semaphore_take_no_yield(%p),1\n",
            (void *) sema);
    abort();
  }
#endif
  while (sema->value == 0) {
    DBOUT(("dthr_semaphore_take_no_yield: not available\n"));
    dthr_chain_enqueue(&sema->threadq,&dthr_cur_thread->link);
    dthr_cur_thread->state = DREAD_THREAD_TH_SEMA_WAIT;
    dthr_thread_sleep(0);
#if MAGIC_TEST
    if (sema->magic != DREAD_THREAD_SEMA_MAGIC) {
      fprintf(stderr,
              "dthr_thread:  semaphore structure corruption detected"
              " in dthr_semaphore_take_no_yield(%p),2\n",
              (void *) sema);
      abort();
    }
#endif
  }
  sema->value--;
  SHOWTHREAD;
  DBOUT(("LV dthr_semaphore_take_no_yield\n"));
}

void  dthr_semaphore_take(struct dthr_semaphore *sema)
{
  SHOWTHREAD;
  DBOUT(("dthr_semaphore_take(%p)\n",(void *) sema));
  /* yield -before- taking the semaphore! */
  dthr_thread_yield();
  dthr_semaphore_take_no_yield(sema);
  SHOWTHREAD;
  DBOUT(("LV dthr_semaphore_take\n"));
}

static void dthr_semaphore_drop_no_yield(struct dthr_semaphore  *sema)
{
  struct dthr_thread  *waker;

  SHOWTHREAD;
  DBOUT(("dthr_semaphore_drop_no_yield(%p)\n",(void *) sema));
#if MAGIC_TEST
  if (sema->magic != DREAD_THREAD_SEMA_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  semaphore structure corruption detected"
            " in dthr_semaphore_drop_no_yield(%p)\n",
            (void *) sema);
    abort();
  }
#endif
  ++sema->value;
  waker = (struct dthr_thread *) DREAD_THREAD_CHAIN_DEQUEUE(&sema->threadq);
  if (waker) {
    waker->state = DREAD_THREAD_TH_RUNNABLE;
    dthr_chain_enqueue(&dthr_runq,&waker->link);
  }
  SHOWTHREAD;
  DBOUT(("LV dthr_semaphore_drop_no_yield\n"));
}

void  dthr_semaphore_drop(struct dthr_semaphore *sema)
{
  SHOWTHREAD;
  DBOUT(("dthr_semaphore_drop(%p)\n",(void *) sema));
  dthr_semaphore_drop_no_yield(sema);
  dthr_thread_yield();
  SHOWTHREAD;
  DBOUT(("LV dthr_semaphore_drop\n"));
}

void  dthr_event_wait(struct dthr_event *event,
      struct dthr_semaphore *lock)
{
  SHOWTHREAD;
  DBOUT(("dthr_event_wait(%p,%p)\n",(void *) event,(void *) lock));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif

  DBOUT(("p_e_w: enqueuing current thread %p\n",(void *) dthr_cur_thread));
#if MAGIC_TEST
  if (event->magic != DREAD_THREAD_EV_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  event structure corruption detected"
            " in dthr_event_wait(%p,%p)\n",
            (void *) event,(void *) lock);
    abort();
  }
#endif
  DBOUT(("p_e_w: about to enqueue this thread onto event\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
  dthr_chain_enqueue(&event->threadq,&dthr_cur_thread->link);
  dthr_cur_thread->state = DREAD_THREAD_TH_EVENT_WAIT;
  DBOUT(("p_e_w: dropping lock %p\n",(void *) lock));
  dthr_semaphore_drop_no_yield(lock);

  DBOUT(("p_e_w: about to go sleeping\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
  DBOUT(("p_e_w: sleeping\n"));
  dthr_thread_sleep(0);
  DBOUT(("p_e_w: awaken, retaking lock %p\n",(void *) lock));
  dthr_semaphore_take_no_yield(lock);

  DBOUT(("about to lv dthr_event_wait, SHOWTHREAD/chain_show first\n"));
  SHOWTHREAD;
  DBOUT(("about to lv dthr_event_wait, calling chain show prior to exiting\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
  DBOUT(("LV dthr_event_wait\n"));
}

static void dthr_eventq_to_runq(struct dthr_event *event,
            unsigned int  max)
{
  struct dthr_thread  *th;

#if MAGIC_TEST
  if (event->magic != DREAD_THREAD_EV_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  event structure corruption detected"
            " in dthr_eventq_to_runq(%p,%d)\n",
            (void *) event,max);
    abort();
  }
#endif
  while (max > 0 &&
         NULL != (th = (struct dthr_thread *)
                  DREAD_THREAD_CHAIN_DEQUEUE(&event->threadq))) {
#if MAGIC_TEST
    if (th->magic != DREAD_THREAD_TH_MAGIC) {
      fprintf(stderr,
              "dthr_thread:  thread structure corruption detected"
              " in dthr_eventq_to_runq(%p,%d)\n",
              (void *) event,max);
      abort();
    }
#endif
#if DEBUG
    dthr_chain_show(stderr,&event->threadq);
#endif
    th->state = DREAD_THREAD_TH_RUNNABLE;
    dthr_chain_enqueue(&dthr_runq,&th->link);
    DBOUT(("dthr_eventq_move: %p is now runnable\n",(void *) th));
    --max;
  }
}

void  dthr_event_broadcast_no_yield(struct dthr_event *event)
{
  SHOWTHREAD;
  DBOUT(("dthr_event_broadcast_no_yield(%p)\n",(void *) event));

#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
  dthr_eventq_to_runq(event,UINT_MAX);
  SHOWTHREAD;
  DBOUT(("LV dthr_event_broadcast\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
}

void  dthr_event_broadcast(struct dthr_event  *event)
{
  SHOWTHREAD;
  DBOUT(("dthr_event_broadcast(%p)\n",(void *) event));

  dthr_eventq_to_runq(event,UINT_MAX);
  dthr_thread_yield();
  SHOWTHREAD;
  DBOUT(("LV dthr_event_broadcast\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
}

void  dthr_event_signal_no_yield(struct dthr_event  *event)
{
  SHOWTHREAD;
  DBOUT(("dthr_event_signal_no_yield(%p)\n",(void *) event));

#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
  dthr_eventq_to_runq(event,1);
  SHOWTHREAD;
  DBOUT(("LV dthr_event_signal_no_yield\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
}

void  dthr_event_signal(struct dthr_event *event)
{
  SHOWTHREAD;
  DBOUT(("dthr_event_signal(%p)\n",(void *) event));

  dthr_eventq_to_runq(event,1);
  dthr_thread_yield();
  SHOWTHREAD;
  DBOUT(("LV dthr_event_signal\n"));
#if DEBUG
  dthr_chain_show(stderr,&event->threadq);
#endif
}

struct dthr_event *dthr_event_init(struct dthr_event  *ev)
{
  (void) dthr_chain_init(&ev->threadq);
  ev->magic = DREAD_THREAD_EV_MAGIC;
  return ev;
}

/*
 * Should be first dthr_* routine to be called.
 */
void  dthr_init(void)
{
#if DEBUG
  setbuf(stdout,0);
#endif
  (void) dthr_chain_init(&dthr_free_stacks);
  (void) dthr_chain_init(&dthr_active_stacks);
  (void) dthr_chain_init(&dthr_runq);
  (void) dthr_chain_init(&dthr_newq);
  dthr_topmost_thread.stack = 0;
  dthr_topmost_thread.magic = DREAD_THREAD_TH_MAGIC;
  (void) dthr_semaphore_init(&dthr_newq_sema,1);
  (void) dthr_event_init(&dthr_newq_event);
}

void  dthr_thread_exit(void *status)
{
  struct dthr_thread_exit   *x;

  SHOWTHREAD;
  DBOUT(("dthr_thread_exit\n"));
  while ((x = dthr_cur_thread->on_exit) != 0) {
    dthr_cur_thread->on_exit = x->next;
    (*x->fn)(dthr_cur_thread,x->arg);
    free(x);
  }
#if MAGIC_TEST
  if (dthr_cur_thread->magic != DREAD_THREAD_TH_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  thread structure corruption detected"
            " in dthr_thread_exit(%p)\n",
            status);
      abort();
    }
#endif
  dthr_cur_thread->exit_value = status;
  dthr_cur_thread->state = DREAD_THREAD_TH_EXITED;

  SHOWTHREAD;
  DBOUT(("dthr_thread_exit -> sleep"));
  dthr_thread_sleep(1);

  fprintf(stderr,"dthr_thread_exit:  exited thread still running\n");
  abort();
}

struct dthr_thread  *dthr_thread_init(struct dthr_thread  *th,
                                      void                *(*fn)(void *),
                                      void                *fn_arg,
                                      size_t              requested_stack_size)
{
  DBOUT(("dthr_thread_init(%p,%p,%p,%p)\n",
         (void *) th,(void *) fn,(void *) fn_arg,
         (void *) requested_stack_size));
  th->fn = fn;
  th->fn_arg = fn_arg;
  th->stack_size = requested_stack_size;

  th->exit_value = (void *) 0;
  th->state = DREAD_THREAD_TH_RUNNABLE;
  th->stack = 0;
  (void) dthr_semaphore_init(&th->exit_sema,0);
  th->on_exit = 0;
  th->magic = DREAD_THREAD_TH_MAGIC;
  /*
   * no stack bound to this thread yet
   */
  return th;
}

int dthr_thread_on_exit(struct dthr_thread  *th,
          void    (*fn)(struct dthr_thread *,void *),
          void    *arg)
{
  struct dthr_thread_exit *x;

  DBOUT(("on exit thread %p, fn %p\n",(void *) th,(void *) fn));
  if (!(x = (struct dthr_thread_exit *) malloc(sizeof *x))) return 0;
#if MAGIC_TEST
  if (th->magic != DREAD_THREAD_TH_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  thread structure corruption detected"
            " in dthr_thread_on_exit(%p,%p,%p)\n",
            (void *) th,(void *) fn,(void *) arg);
    abort();
  }
#endif

  x->next = th->on_exit;
  x->fn = fn;
  x->arg = arg;
  th->on_exit = x;
  return 1;
}

/*
 * Place onto new thread queue.  Topmost thread creates stack space and
 * moves thread from new queue to run queue.
 */
struct dthr_thread  *dthr_thread_run(struct dthr_thread *th)
{
#if MAGIC_TEST
  if (th->magic != DREAD_THREAD_TH_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  thread structure corruption detected"
            " in dthr_thread_run(%p)\n",
            (void *) th);
    abort();
  }
#endif
  SHOWTHREAD;
  DBOUT(("dthr_thread_run(%p)\n",(void *) th));
  dthr_semaphore_take_no_yield(&dthr_newq_sema);
  dthr_chain_enqueue(&dthr_newq,&th->link);
  dthr_event_signal_no_yield(&dthr_newq_event);
  dthr_semaphore_drop_no_yield(&dthr_newq_sema);
  dthr_thread_yield();
  SHOWTHREAD;
  DBOUT(("LV dthr_thread_run\n"));
  return th;
}

struct dthr_thread  *dthr_thread_wait(struct dthr_thread *th)
{
#if MAGIC_TEST
  if (th->magic != DREAD_THREAD_TH_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  thread structure corruption detected"
            " in dthr_thread_wait(%p)\n",
            (void *) th);
    abort();
  }
#endif
  dthr_semaphore_take(&th->exit_sema);
  dthr_semaphore_drop(&th->exit_sema);
  return th;
}

struct dthr_thread  *dthr_thread_detach(struct dthr_thread *th)
{
#if MAGIC_TEST
  if (th->magic != DREAD_THREAD_TH_MAGIC) {
    fprintf(stderr,
            "dthr_thread:  thread structure corruption detected"
            " in dthr_thread_detach(%p)\n",
            (void *) th);
    abort();
  }
#endif
  dthr_semaphore_drop(&th->exit_sema);
  /* self cleanup? */
  return th;
}

/*
 * Returns a stack descriptor from free list -- best fit.
 */
static struct dthr_stack  *dthr_find_free_stack(int size)
{
  struct dthr_stack *stk, *best_so_far;
  int     best_size_diff = INT_MAX, size_diff;

  DBOUT(("dthr_find_free_stack\n"));
  for (best_so_far = 0, stk = (struct dthr_stack *) dthr_free_stacks.next;
       (struct dthr_chain *) stk != &dthr_free_stacks;
       stk = (struct dthr_stack *) stk->link.next) {
#if MAGIC_TEST
    if (stk->magic != DREAD_THREAD_STACK_MAGIC) {
      fprintf(stderr,
              "dthr_thread: stack descriptor corruption detected"
              " by dthr_find_free_stack(0x%08x)\n",
              size);
      abort();
    }
#endif
    if ((size_diff = stk->stack_size - size) > 0
        && size_diff < best_size_diff) {
      best_size_diff = size_diff;
      best_so_far = stk;
    }
  }
  DBOUT(("dthr_find_free_stack -> %p\n",(void *) best_so_far));
  return best_so_far;
}

static void dthr_thread_launcher(void);

static void dthr_new_topmost_thread(struct dthr_stack *stk,
                                    size_t            size_wanted,
                                    int               first_time,
                                    dthr_ctxt_t       *continuation)
{
  int         base_candidate;
  caddr_t     stack_pos;
  int         sofar;
#if DEBUG
  static int  counter;
#endif

#if MAGIC_TEST
  if (stk->magic != DREAD_THREAD_STACK_MAGIC) {
    fprintf(stderr,
            "dthr_thread: stack descriptor corruption detected"
            " by dthr_new_topmost_thread(%p,0x%08lx,%d,%p)\n",
            (void *) stk,(unsigned long) size_wanted,
            first_time,(void *) continuation);
    abort();
  }
#endif
  /*
   * The new thread is on the run queue, and when the
   * topmost launcher thread finishes, the new thread
   * will context switch normally and be run.
   */
  if (first_time) {
#if DEBUG
    DBOUT(("dthr_new_topmost_thread(%p,0x%08x,%d)\n",
           (void *) stk,size_wanted,first_time));
    DBOUT(("dthr_new_topmost_thread: stack at %p, prev stack_base at %p\n",
           (void *) &base_candidate,(void *) stk->stack_base));
    counter = 0;
#endif
    DBOUT(("dthr_new_topmost_thread.save_ctxt(%p)\n",(void *) &stk->regs));
    if (dthr_save_ctxt(&stk->regs)) {
      DBOUT(("dthr_new_topmost_thread: topmost split, thread %p on the way\n",
             (void *) stk->thread));
      DBOUT(("dthr_new_topmost_thread.load_ctxt(%p,1)\n",
             (void *) continuation));
      dthr_load_ctxt(continuation,1);
    }
  }

  stack_pos = (void *) &base_candidate;
#if DREAD_THREAD_STACK_GROWS_DOWN
  sofar = stk->stack_base - stack_pos;
#else
  sofar = stack_pos - stk->stack_base;
#endif

#if DEBUG
  ++counter;
  if (!(counter % 0x10)) {
    printf("dthr_new_topmost_thread: stack 0x%08x so far\n",sofar);
  }
#endif
  if (sofar < size_wanted + DREAD_THREAD_STACK_EXTRA) {
    dthr_new_topmost_thread(stk,size_wanted,0,continuation);
    /* compiler should not tail recurse here! */
  }
  DBOUT(("dthr_new_topmost_thread: enough stack!\n"));
  /*
   * Actual thread_fork happens here.  The stack has grown to the
   * appropriate size, and now we can reset the topmost-stack descriptor
   * to updated values.
   */
  DBOUT(("dthr_new_topmost_thread:  marking thread %p as runnable\n",
         (void *) stk->thread));
  dthr_chain_enqueue(&dthr_runq,&stk->thread->link);

  DBOUT(("dthr_new_topmost_thread -> launcher\n"));
  dthr_thread_launcher();
}

static void dthr_thread_launcher(void)
{
  unsigned long           magic = DREAD_THREAD_MAGIC2;
  struct dthr_thread      *new_th;
  struct dthr_stack       *new_stk;
  dthr_ctxt_t             continuation;
  struct dthr_thread_exit *x;

  DBOUT(("dthr_thread_launcher\n"));

  dthr_topmost_stack.stack_size = 0;
  dthr_topmost_stack.stack_base = (void *) &magic;
  dthr_topmost_stack.stack_top = 0;
  dthr_topmost_stack.thread = &dthr_topmost_thread;
  dthr_topmost_stack.magic = DREAD_THREAD_STACK_MAGIC;

  dthr_topmost_thread.stack = &dthr_topmost_stack;

  DBOUT(("p_t_l: grabbing new thread queue lock\n"));
  dthr_semaphore_take_no_yield(&dthr_newq_sema);
  for (;;) {
    DBOUT(("p_t_l: getting thread\n"));
    dthr_show_queues();
    while ((new_th = (struct dthr_thread *)
            DREAD_THREAD_CHAIN_DEQUEUE(&dthr_newq)) != 0) {
#if MAGIC_TEST
      if (new_th->magic != DREAD_THREAD_TH_MAGIC) {
        fprintf(stderr,
                "dthr_thread:  thread structure corruption detected"
                " in dthr_thread_launcher(), thread scan\n");
        abort();
      }
#endif
      DBOUT(("p_t_l: launching thread %p\n",(void *) new_th));
      /* dthr_find_free_stack does magic test */
      if (0 != (new_stk = dthr_find_free_stack(new_th->stack_size))) {
        /*
         * Found a stack for this thread,
         * so now we can just bind them together
         * and context switch to the base of
         * the stack to launch the thread.
         */
        DBOUT(("p_t_l:  free stack available on free list %p\n",
               (void *) new_stk));
        DBOUT(("p_t_l:  reverting regs\n"));
        memcpy((void *) &new_stk->regs,(void *) &new_stk->base,
               sizeof new_stk->regs);
        new_stk->thread = new_th;
        new_th->stack = new_stk;
        new_th->state = DREAD_THREAD_TH_RUNNABLE;
        dthr_chain_enqueue(&dthr_runq,&new_th->link);
      } else {
        DBOUT(("p_t_l:  no sufficiently large stack on free list,"
               " allocating new stack descriptor\n"));
        new_stk = (struct dthr_stack *) malloc(sizeof *new_stk);
        if (!new_stk) {
          fprintf(stderr,
                  "dthr_thread:  top_thread:  No space for stack descriptor\n");
          abort();
        }
        /* copy and correct */
        new_stk->stack_base = dthr_topmost_stack.stack_base;
        new_stk->stack_size = new_th->stack_size;
#if DREAD_THREAD_STACK_GROWS_DOWN
        new_stk->stack_top = new_stk->stack_base - new_stk->stack_size;
#else
        new_stk->stack_top = new_stk->stack_base + new_stk->stack_size;
#endif
        new_stk->magic = DREAD_THREAD_STACK_MAGIC;

        /*
         * Turn into new thread; note that temporarily
         * a stack will reference a thread that is not
         * in the run/sema/event queues and is not the
         * current thread.
         */
        new_stk->thread = new_th;
        new_th->stack = new_stk;
        new_th->state = DREAD_THREAD_TH_RUNNABLE;
        /*
         * Ensure that dthr_this_thread will make sense
         */
        dthr_chain_push(&dthr_active_stacks,&new_stk->link);
        /*
         * Grow stack; dthr_topmost_stack is updated
         * as a side effect.
         */
        DBOUT(("p_t_l: dropping new thread queue lock\n"));
        dthr_semaphore_drop_no_yield(&dthr_newq_sema);
        DBOUT(("p_t_l: growing stack\n"));
        DBOUT(("p_t_l.save_ctxt(%p) [cont]\n",(void *) &continuation));
        if (!dthr_save_ctxt(&continuation))
          dthr_new_topmost_thread(new_stk,new_th->stack_size,1,&continuation);
        for (;;) {
          /* base, allowing for stack reuse */
          DBOUT(("p_t_l.dthr_save_ctxt(%p) [base]\n",(void *) &new_stk->base));
          (void) dthr_save_ctxt(&new_stk->base);

          /* launch the thread */
          new_th = new_stk->thread;
          dthr_cur_thread = new_th;
#if MAGIC_TEST
          if (new_th->magic != DREAD_THREAD_TH_MAGIC) {
            fprintf(stderr,
                    "dthr_thread:  thread structure corruption detected"
                    " in dthr_thread_launcher(), base launch\n");
            abort();
          }
#endif
          new_th->exit_value = (*new_th->fn)(new_th->fn_arg);

          while ((x = new_th->on_exit) != 0) {
            new_th->on_exit = x->next;
            (*x->fn)(new_th,x->arg);
            free(x);
          }

          DBOUT(("p_t_l: thread %p exited\n",(void *) dthr_cur_thread));
          /* same as dthr_thread_exit here */
          new_th->state = DREAD_THREAD_TH_EXITED;

          dthr_thread_sleep(1);
          fprintf(stderr,"dthr_thread_launcher: exited thread still runs\n");
          abort();
        }
      }
    }
    /*
     * wait for more threads to launch
     */
    DBOUT(("p_t_l: waiting for a new thread to launch\n"));
    dthr_event_wait(&dthr_newq_event,&dthr_newq_sema);
    DBOUT(("p_t_l: event wait returned\n"));
  }
}

/*
 * We force user to pass us a runnable thread directly
 * rather than just placing it on the run queue
 * in order to programmatically enforce that there must
 * be at least one runnable thread when the process
 * goes multithreaded.
 */
void  dthr_thread_multithread(struct dthr_thread  *th)
{
  DBOUT(("dthr_thread_multithread\n"));

  dthr_show_queues();

  /* no need to lock it yet, since we are only thread running */
  dthr_chain_enqueue(&dthr_newq,&th->link);
  dthr_cur_thread = &dthr_topmost_thread;

  dthr_show_queues();
  DBOUT(("dthr_thread_multithread -> launch\n"));
  if (!dthr_save_ctxt(&dthr_deadlock))
    dthr_thread_launcher();
}


/*
 * Context switch to thread th_next, doing op to current thread.
 * Interrupts are masked.
 */
static void dthr_csw(struct dthr_stack  *target, int  op)
{
  register struct dthr_stack  *this_stack;
  register int      rv;

  unsigned long     magic = DREAD_THREAD_MAGIC;

  dthr_show_queues();
  DBOUT(("dthr_csw(%p,%d)\n",(void *) target,op));
  this_stack = dthr_cur_thread->stack;
  DBOUT((" old stack = %p\n",(void *) this_stack));
  if (!this_stack) {
    fprintf(stderr,"dthr_csw:  no current stack\n");
    abort();
  }
  if (op == DREAD_THREAD_CSW_EXIT) {
    DBOUT((" leaving exited thread\n"));

    dthr_cur_thread->stack = 0;

    memset(&this_stack->regs,0,sizeof this_stack->regs);
    dthr_show_queues();
    (void) dthr_chain_delete(&this_stack->link);
    dthr_show_queues();
    dthr_chain_enqueue(&dthr_free_stacks,&this_stack->link);
    dthr_show_queues();

    dthr_cur_thread->fn = 0;
    dthr_cur_thread->fn_arg = 0;
    dthr_cur_thread->stack_size = 0;

    DBOUT(("dthr_csw.long(%p,DREAD_THREAD_CSW_NORM)\n",(void *) &target->regs));
    dthr_load_ctxt(&target->regs,DREAD_THREAD_CSW_NORM);
    fprintf(stderr,"dthr_csw:  exit load context returned\n");
    abort();
  }

  DBOUT(("dthr_csw.save_ctxt(%p)\n",(void *) &this_stack->regs));
  switch (rv = dthr_save_ctxt(&this_stack->regs)) {
  case DREAD_THREAD_CSW_CSW:
    DBOUT(("dthr_csw.load_ctxt(%p,%d)\n",(void *) &target->regs,op));
    dthr_load_ctxt(&target->regs,op);
    fprintf(stderr,"dthr_csw:  csw failed\n");
    abort();
    break;
  case DREAD_THREAD_CSW_CREATE:
    if (magic != DREAD_THREAD_MAGIC) {
      fprintf(stderr,
              "dthr_csw:  stack corruption detected, thread ID %p (tomost)\n",
              (void *) dthr_cur_thread);
      abort();
    }
    if ((dthr_cur_thread = this_stack->thread) != &dthr_topmost_thread) {
      fprintf(stderr,"dthr_csw:  create csw, am not topmost\n");
      abort();
    }
    DBOUT(("dthr_csw/ret: cur thread %p\n",(void *) dthr_cur_thread));
    return;
  case DREAD_THREAD_CSW_NORM:
    if (magic != DREAD_THREAD_MAGIC) {
      fprintf(stderr,
              "dthr_csw:  stack corruption detected, thread %p\n",
              (void *) dthr_cur_thread);
      abort();
    }
    dthr_cur_thread = this_stack->thread;
    DBOUT(("dthr_csw/ret: cur thread %p\n",(void *) dthr_cur_thread));
    return;
  default:
    fprintf(stderr,"dthr_csw:  Unexpected op code %d\n",rv);
    abort();
  }
}

/*
 * A simpler, higher level threads interface:  one function,
 * DThr_Thread_Run, which queues threads to be run before going
 * multithreaded, uses NULL pointers in arglist to go multithreaded,
 * and once multithreaded may be called to spawn additional
 * threads.  The threads are automatically garbage collected.
 *
 * This has to be inside of the abstraction barrier to permit reuse of
 * the dthr_thread data structure.  Otherwise we would declare a union...
 * We also stomp on the user data field.  We assume that that field is
 * needed by the user only for the duration of the thread function but
 * not during on-exit routines.
 */

static struct dthr_thread     *dthr_thread_q = 0;
static int                    DThr_Thread_State = 0;
static struct dthr_semaphore  to_be_freed_sema, numDThr_Threads;
static struct dthr_event      to_be_freed_ev;
static struct dthr_thread     *to_be_freed = 0;

/*
 * Things break horribly if we yield here, since the malloc'ed thread
 * descriptor could get free'd prior to actually finishing up with
 * the thread.  In particular, we do not wish the reaper thread to
 * run until we have csw'd out of the exiting thread.
 */
static void mark_of_death(struct dthr_thread *th, void *arg)
{
  DBOUT(("thread %p, going to the guillotine\n", (void *) th));
  dthr_semaphore_take_no_yield(&to_be_freed_sema);
  th->data = (void *) to_be_freed;
  to_be_freed = th;
  dthr_semaphore_drop_no_yield(&to_be_freed_sema);
  dthr_event_signal_no_yield(&to_be_freed_ev);
}

static void reaper(void)
{
  struct dthr_thread  *th;

  dthr_semaphore_take(&to_be_freed_sema);
  for (;;) {
    while ((th = to_be_freed) != 0) {
      to_be_freed = (struct dthr_thread *) th->data;
      DBOUT(("Grim reaper:  got thread %p\n",(void *) th));
      free(th);
      dthr_semaphore_drop(&numDThr_Threads);
    }
    if (!dthr_semaphore_try(&numDThr_Threads)) break; /* thread exits */
    DBOUT(("reaper event wait\n"));
    dthr_event_wait(&to_be_freed_ev,&to_be_freed_sema);
    DBOUT(("reaper event occurred\n"));
  }
  dthr_semaphore_drop(&to_be_freed_sema);
}

static void *DThr_MultiThread(void *arg)
{
  struct dthr_thread  *th;

  DBOUT(("Entered DThr_MultiThread\n"));
  while ((th = dthr_thread_q) != 0) {
    dthr_thread_q = (struct dthr_thread *) th->data;
    dthr_thread_init(th,th->fn,th->fn_arg,th->stack_size);
    if (!dthr_thread_on_exit(th,mark_of_death,0)) {
      perror("DThr_Thread");
      fprintf(stderr,
              "DThr_Thread:  startup failure while setting up on-exit fn\n");
      abort();
    }
    (void) dthr_thread_run(th);
    (void) dthr_thread_detach(th);
  }
  reaper();
  DBOUT(("Leaving DThr_MultiThread\n"));
  return 0;
}

int DThr_Thread_Run(void    *(*fn)(void *),
                    void    *fn_arg,
                    size_t  req_stack_size)
{
  struct dthr_thread  main_th, *th;

  DBOUT(("Entered DThr_Thread_Run\n"));
  switch (DThr_Thread_State) {
  case 0:
    dthr_init();
    (void) dthr_semaphore_init(&to_be_freed_sema,0);
    (void) dthr_semaphore_init(&numDThr_Threads,0);
    (void) dthr_event_init(&to_be_freed_ev);
    DThr_Thread_State = 1;
    /* fall thru */
  case 1:
    if (!fn) {
      /* begin multithreading */
      dthr_thread_init(&main_th,DThr_MultiThread,fn_arg, 0x1000);
      DThr_Thread_State = 2;
      dthr_thread_multithread(&main_th);
      return 1;
    }
    th = (struct dthr_thread *) malloc(sizeof *th);
    if (!th) return 0;
    th->fn = fn;
    th->fn_arg = fn_arg;
    th->stack_size = req_stack_size;

    th->data = (void *) dthr_thread_q;
    dthr_thread_q = th;

    dthr_semaphore_drop(&numDThr_Threads);

    DBOUT(("Leaving DThr_Thread_Run\n"));
    return 1;
  case 2:
    th = (struct dthr_thread *) malloc(sizeof *th);
    if (!th) return 0;
    th->fn = fn;
    th->fn_arg = fn_arg;
    th->stack_size = req_stack_size;

    dthr_semaphore_drop(&numDThr_Threads);

    if (!dthr_thread_on_exit(th,mark_of_death,0)) {
      perror("DThr_Thread");
      fprintf(stderr,
              "DThr_Thread:  runtime failure while setting up on-exit fn\n");
      abort();
    }
    (void) dthr_thread_run(th);
    (void) dthr_thread_detach(th);

    DBOUT(("Leaving DThr_Thread_Run\n"));
    return 1;
  }
  /* NOTREACHED -- make lint happy */
  return 1;
}