/*****************************************************************************
 *                                                                           *
 *  Copyright (c) 1993, 1994, Elan Feingold (elan@tasha.cheme.cornell.edu)   *
 *                                                                           *
 *     PERMISSION TO USE, COPY, MODIFY, AND TO DISTRIBUTE THIS SOFTWARE      *
 *     AND ITS DOCUMENTATION FOR ANY PURPOSE IS HEREBY GRANTED WITHOUT       *
 *     FEE, PROVIDED THAT THE ABOVE COPYRIGHT NOTICE APPEAR IN ALL           *
 *     COPIES AND MODIFIED COPIES AND THAT BOTH THAT COPYRIGHT NOTICE AND    *
 *     THIS PERMISSION NOTICE APPEAR IN SUPPORTING DOCUMENTATION.  THERE     *
 *     IS NO REPRESENTATIONS ABOUT THE SUITABILITY OF THIS SOFTWARE FOR      *
 *     ANY PURPOSE.  THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS       *
 *     OR IMPLIED WARRANTY.                                                  *
 *                                                                           *
 *****************************************************************************/

#include <stdio.h> 
#include <string.h>
#include <setjmp.h> 
#include <stdlib.h> 
#include <sys/time.h>
#include <signal.h>
#include <stdarg.h>
  
#include "queue.h" 
#include "thread.h" 
#include "types.h" 
#include "debug.h" 

/* Private data structures for registered conditions.
 * The conditions will be held in a singly linked list.
 * clkNextTime is the time at which the condition next
 * needs to be scheduled for execution.  The algorithm
 * used is the following:  
 *   Every time we get a SIGVTARLM, run down the list,
 * which is sorted in increasing order, acording to 
 * clkNextRunTime.  Any conditions that have a run
 * time in the present or past get signalled.  Each
 * condition that is scheduled, gets put on a queue
 * temporarily.  When all the conditions that need 
 * to be signalled are signalled, we remove the
 * conditions on the queue, updating their fields, 
 * and then inserting them on the linked list again
 * in sorted order.
 *   In this way, if there are no conditions to
 * signal, all that is required is one check to
 * the head of the linked list.  If there is
 * a condition to signal, the operations are
 * simple and cheap, and require no drastic
 * measures such as rebuilding the whole list.
 */

typedef struct _CondNode
{
  RT_Timing_Info      rtTimingInfo;
  clock_t             clkNextRunTime;
  PCondition          pCond;
  struct _CondNode   *next;
} CondNode;

typedef struct _CondList
{
  CondNode *pList;
} CondList;

/* A few macros for Timed Conditions */
#define _timed_cond_empty() (TimedCondList.pList==NULL)
#define _timed_cond_next_time()  TimedCondList.pList->clkNextRunTime

/* Make life easier for us non-touch typists */
typedef struct itimerval ITimer;
 
/* A few defines used */
#define STACK_COOKIE 0xCC   /* Detects stack overflow */
#define NAME_SIZE    32     /* Max size of the default thread name */

/* Magic preemptive scheduling macro.  We NEED one-shot action
 * which is done by having a Boolean around telling us if
 * the timer is armed or not.   Every time the signal handler
 * is invoked, we set fArmed to FALSE.
 */

#define _t_arm_timer()  \
  if(!fArmed) { \
    fArmed = TRUE; \
    itSchedule.it_value.tv_sec  = 0;  \
    itSchedule.it_value.tv_usec = TIME_SLICE;  \
    setitimer(ITIMER_VIRTUAL, &itSchedule, NULL); }

/* Thread destroying macro */
#define _t_destroy_thread(pThread) { \
  MEM_Free(pThread->strThreadName); \
  MEM_Free(pThread->pStack); \
  MEM_Free(pThread); }

/* Condition destroying macro */
#define _t_destroy_cond(pCond) { \
  q_destroy(pCond->pBlockedQueue); \
  q_destroy(pCond->pSignalsQueue); \
  MEM_Free(pCond); }

/* Private helper & glue routines */ 
void _timed_cond_issue_signalsRT(void);
void _timed_cond_chrono_insert(CondNode *pNode);
void _timed_cond_destroy_list(void);
void _t_switch_context(void); 
void _t_cleanup(void); 
void _t_schedule(void);
void _t_debug_dump(String strEvent);
void _t_sig_handler(int iSig);
void _t_fprintf(FILE *hFile, String strFormat, ...);
void _t_free_all_memory(void);

/* Private globals */ 
Condition    pcondReadyThreads[2]; /* Holds all of the ready threads */
PQueue       pqueueDeadThreads;    /* Not unlike Dead Heads :) */
PQueue       pqueueDeadCond;       /* Holds conditions we've allocated */
PQueue       pqueueLiveCond;       /* Holds conditions we've freed */ 
Thread      *pRunningThread;       /* Currently executing thread */
jmp_buf      contextTheEnd;        /* Context to jump to when all ends */
Boolean      fHandleFailures;      /* Do we handle RT failures ? */
UInt         uiThreadNum;          /* Used for thread auto-names */
FILE        *hLogFile;             /* File to dump debug stuff to */
ITimer       itSchedule;           /* Interval timer for scheduling */
Boolean      fArmed;               /* Whether the timer is armed */
UInt         uiRetVal;             /* The value to t_start[RT] returns */
UInt         uiCSDepth;            /* For nesting critical sections */


/* Timed Condition Globals */
CondList   TimedCondList;           /* Points to head of list */
PQueue     pTempQueue;              /* Kept around to speed things up */


/************************************************************************ 
 *  FUNCTION: t_exit_all
 *  HISTORY: 
 *     11/07/93  ESF  Created 
 *  PURPOSE: 
 *     This function is called when, for some reason or another, all
 *   threads need to be terminated, and t_fork[RT]() needs to return
 *   iValue, which can indicate why the abort took place.  First, we
 *   unregister the signal handler, and then cancel the itimer, which
 *   will have at most one interrupt pending, because of its one-shot
 *   nature.  After we have done this, we longjmp to a context from 
 *   which t_fork[RT]() can exit from, after we destroy every bit of
 *   memory that was being used.
 *  NOTES: 
 ************************************************************************/ 
void t_exit_all(int iValue)
{
  /* Cancel the main timer, if it's pending, not that it matters... */
  itSchedule.it_value.tv_usec = 0; 
  setitimer(ITIMER_VIRTUAL, &itSchedule, NULL);
  
  /* Unregister the signal handler */
  signal(SIGVTALRM, SIG_IGN);
  
  /* The return value */
  uiRetVal = (UInt)iValue;

  /* longjmp, so that we can return from t_start */
  longjmp(contextTheEnd, 1);
}


/************************************************************************ 
 *  FUNCTION: t_start
 *  HISTORY: 
 *     10/30/93  ESF  Created 
 *  PURPOSE: 
 *     Simply calls the RealTime t_startRT() function.  It exists for
 *   backwards compatibility with EThreads 1.0.
 *  NOTES: 
 *     The default is to _not_ handle Real-Time scheduling failures.
 ************************************************************************/ 
int t_start(ThreadFunc thdProc, any_ptr pvValue)
{
  return t_startRT(thdProc, pvValue, NULL, PRIORITY_HIGH, FALSE);
} 


/************************************************************************ 
 *  FUNCTION: t_startRT
 *  HISTORY: 
 *     10/01/93  ESF  Created. 
 *     10/02/93  ESF  Modified to include jmp_buf for "all threads dead". 
 *     10/25/93  ESF  Modified to use two thread queues for scheduling.
 *     11/07/93  ESF  Modified to allocate live/dead cond queues.
 *     11/09/93  ESF  Small bug fix, moved _t_debug_dump later.
 *  PURPOSE: 
 *     Initializes all of the EThreads global variables, queues, and
 *   conditions.  Inits the recycling bins (queues) for dead threads
 *   and conditions, forks off the first thread, sets up the signal
 *   handler, and then calls the scheduler.
 *  NOTES: 
 ************************************************************************/ 
int t_startRT(ThreadFunc thdProc, any_ptr pvValue, char *strName, 
	       Priority priPriority, Boolean fHardFail) 
{ 
  signal(SIGVTALRM, (void(*)(int))_t_sig_handler);

  /* Create the needed conditions for holding ready threads */
  pcondReadyThreads[PRIORITY_LOW]  = (PCondition)cond_create(); 
  pcondReadyThreads[PRIORITY_HIGH] = (PCondition)cond_create(); 

  /* Create queues for dead thread stacks and live & dead conditions */
  pqueueDeadThreads  = (PQueue)q_create(); 
  pqueueDeadCond     = (PQueue)q_create();
  pqueueLiveCond     = (PQueue)q_create();

  /* Setup misc parameters for the thread subsystem */
  fHandleFailures = fHardFail;
  uiThreadNum     = 0;
  pRunningThread  = (Thread *)NULL;
  pTempQueue      = q_create();
  fArmed          = FALSE;
  uiCSDepth       = 0;

  _t_debug_dump("START");

  /* Now fork the first thread */
  t_forkRT(thdProc, pvValue, strName, priPriority);
 
  /* Save a context that we can return to when everything's over */
  if (!setjmp(contextTheEnd)) 
    {
      /* Set up the timer fields for monostable operation.  The
       * interval field is set to 0 so that once the timer fires
       * once, it won't fire again.
       */
      
      itSchedule.it_interval.tv_sec  = 0;
      itSchedule.it_interval.tv_usec = 0;
      
      /* Schedule the first thread */
      _t_schedule();
    }
  else 
    {
      /* Clean up everything that's still around */
      _t_free_all_memory();
      
      /* Check for memory leaks */
      MEM_TheEnd();

      return((int)uiRetVal);
    }
} 
 

/************************************************************************ 
 *  FUNCTION: t_fork
 *  HISTORY: 
 *     10/30/93  ESF  Created 
 *  PURPOSE: 
 *     Simply calls the RealTime t_forkRT() function.  It exists for
 *   backwards compatibility with EThreads 1.0. 
 *  NOTES: 
 ************************************************************************/ 
void t_fork(ThreadFunc thdProc, any_ptr pvValue)
{
  t_forkRT(thdProc, pvValue, NULL, PRIORITY_HIGH);
} 
 
/************************************************************************ 
 *  FUNCTION: t_forkRT 
 *  HISTORY: 
 *     10/01/93  ESF  Created 
 *     10/25/93  ESF  Modified for Real-Time threads
 *  PURPOSE: 
 *     First, create a new thread + stack if we need to (i.e. if there
 *   aren't any threads on the recycled threads queue.  Create a default
 *   name if none was passed in, and initialize the various threads
 *   parameters.  Then insert the thread in the appropriate ready thread
 *   queue (actually a condition).
 *  NOTES: 
 ************************************************************************/ 
void t_forkRT(ThreadFunc thdProc, any_ptr pvValue, String strName, 
	    Priority priPriority) 
{ 
  Thread   *pThread;
  String    strTemp;
  sigset_t  sigOldMask;

  /* There a lot of things in here that can generate nasty
   * race conditions.  We want the thread all set and on the
   * queue before we let any context switching happen.
   */

  sigOldMask = sigblock(sigmask(SIGVTALRM));

  _t_debug_dump("FORKING");

  /* Allocate memory for the new thread & stack (if needed) */ 
  if (q_is_empty(pqueueDeadThreads))
    {
      pThread  =  (Thread *)MEM_Alloc(sizeof(Thread)); 
      pThread->pStack = (Byte *)MEM_Alloc(THREAD_STACK * sizeof(Byte));
    }
  else /* it was a really cheap thread creation */
    {
      pThread = (Thread *)q_remove(pqueueDeadThreads);
      
      /* The name is going to be redone, so free it */
      MEM_Free(pThread->strThreadName);
    }

  /* Set up the thread's parameters */
  pThread->thdProc     = thdProc; 
  pThread->pvArg       = pvValue; 
  pThread->iState      = THREAD_NOTLIVE; 
  pThread->priPriority = priPriority;
  
  /* If no strName, generate unique name, otherwise copy given name */
  if (strName==NULL)
    {
      strTemp = (String)MEM_Alloc(NAME_SIZE);
      sprintf(strTemp, "Thread[%ld]", uiThreadNum++);    
    }
  else
    {
      strTemp = (String)MEM_Alloc(strlen(strName)+1);
      strcpy(strTemp, strName);
    }

  /* Put the name in the thread structure */
  pThread->strThreadName = strTemp;

  /* Put the new thread on the tail of the right condition queue */ 
  q_insert(pcondReadyThreads[priPriority]->pBlockedQueue, 
	   (any_ptr)pThread); 

  sigsetmask(sigOldMask);
}  
   
 
/************************************************************************ 
 *  FUNCTION: t_wait 
 *  HISTORY: 
 *     10/01/93  ESF  Created. 
 *     10/02/93  ESF  Fixed signalling bug.  
 *  PURPOSE: 
 *     The calling thread blocks on pCond.  If there are already signals 
 *     on the queue, then simply return the oldest one.  Otherwise, save 
 *     the context of the thread, schedule a new thread, and then switch 
 *     contexts. 
 *  NOTES: 
 ************************************************************************/ 
any_ptr t_wait(PCondition pCond) 
{
  any_ptr   signal;
  sigset_t  sigOldMask;

  /* Atomically check the queue and remove the signal and 
   * the thread that might need to wait.
   */

  sigOldMask = sigblock(sigmask(SIGVTALRM));

  _t_debug_dump("WAIT");  

  /* Are there signals pending for the condition? */
  if (!q_is_empty(pCond->pSignalsQueue)) 
    {
      signal = (any_ptr)q_remove(pCond->pSignalsQueue);
      _t_debug_dump("SIGNALLED");

      sigsetmask(sigOldMask);
      return(signal);
    }

  /* We need to save the context of the thread, and then queue 
   * it up on the blocked threads queue, to wait for its signal.  
   * Note that this is the only place in which the context for
   * a thread gets saved.
   */ 

  if (!setjmp(pRunningThread->State)) 
    {
      pRunningThread->iState = THREAD_BLOCKED; 
      q_insert(pCond->pBlockedQueue, pRunningThread); 
      pRunningThread = NULL;
      _t_schedule(); 
    } 
  else
    {
      _t_debug_dump("SIGNALLED");
      sigsetmask(sigOldMask);
      return(pRunningThread->pvArg); 
    }
} 

 
/************************************************************************ 
 *  FUNCTION: t_sig 
 *  HISTORY: 
 *     10/01/93  ESF  Created. 
 *     10/02/93  ESF  Fixed a sig value bug.  Store it in awoken thread. 
 *  PURPOSE: 
 *     Signals a condition with value pvValue.  If fQueueSignal is TRUE 
 *   treats signal like a semaphore, storing it on the Signals queue for 
 *   future threads, otherwise discard it.  If there was a thread blocked 
 *   on this condition, move it over to the runnable threads queue. 
 *  NOTES: 
 *     If there was a thread waiting, instead of storing the signal on 
 *   the queue for it to take off, store it in the thread itself,  
 *   because if the thread signalling waits on the signal before 
 *   yielding itself, unless we add a check, it will find its own 
 *   signal. 
 ************************************************************************/ 
void t_sig(PCondition pCond, any_ptr pvValue, Boolean fQueueSignal) 
{ 
  /* If there is a thread blocked, run it.  More race condition
   * possibilities with checking conditions and then removing
   * things from queues.
   */

  sigset_t  sigOldMask = sigblock(sigmask(SIGVTALRM));

  if (!cond_is_empty(pCond)) 
    { 
      Thread   *pThread = (Thread *)q_remove(pCond->pBlockedQueue);

      /* Move the thread from cond onto the right ready threads queue */
      pThread->iState = THREAD_WAITING;
      pThread->pvArg  = pvValue;
      q_insert(pcondReadyThreads[pThread->priPriority]->pBlockedQueue, 
	       pThread);
    } 
  else if (fQueueSignal)
    q_insert(pCond->pSignalsQueue, pvValue); 

  sigsetmask(sigOldMask);
} 
 

/************************************************************************ 
 *  FUNCTION: t_sig_urgent 
 *  HISTORY: 
 *     10/31/93  ESF  Created. 
 *     11/07/93  ESF  Inserted missing code.
 *  PURPOSE: 
 *     Same as t_sig, except when it puts a thread on the ready queue, 
 *   it puts it at the head of the queue (cuts it in line :).  If there
 *   isn't a thread waiting on the signal, the signal is stored on the
 *   signal queue if desired (fQueueSignal) and then it is treated 
 *   normally (i.e. next thread that comes along gets put on the tail
 *   of the queue.
 *  NOTES: 
 ************************************************************************/ 
void t_sig_urgent(PCondition pCond, any_ptr pvValue, Boolean fQueueSignal) 
{ 
  sigset_t  sigOldMask = sigblock(sigmask(SIGVTALRM));

  if (!cond_is_empty(pCond)) 
    { 
      Thread *pThread  = (Thread *)q_remove(pCond->pBlockedQueue);
      
      pThread->iState = THREAD_WAITING;
      pThread->pvArg  = pvValue;

      /* Simply put the signaled thread at the head of the queue */
      q_cut_in_line(pcondReadyThreads[pThread->priPriority]->pBlockedQueue, 
		    (any_ptr)pThread);  
    } 
  else if (fQueueSignal) /* The signal is now not special */
    q_insert(pCond->pSignalsQueue, pvValue); 

  sigsetmask(sigOldMask);
} 
 

/************************************************************************ 
 *  FUNCTION: t_yield 
 *  HISTORY: 
 *     10/01/93  ESF  Created. 
 *     10/02/93  ESF  Fixed bug, not initializing pThread correctly. 
 *     10/26/93  ESF  Changed to implement priority scheduling.
 *     10/26/93  ESF  Optimized, adding NOOP conditions.
 *  PURPOSE: 
 *     A thread calls this function to relinquish its control of the  
 *   CPU.  A new thread is scheduled, and the context is switched. 
 *   the function is optimized, in that if the thread is high priority
 *   and there are no high priority threads ready, it returns right away,
 *   and, likewise, when there are no high or low priority threads, it
 *   returns for a low priority thread.
 *  NOTES: 
 ************************************************************************/ 
void t_yield(void) 
{ 
  Int       priRunning;
  Boolean   fHighEmpty;
  Boolean   fLowEmpty;
  sigset_t  sigOldMask;

  /* Find out if the yield is a no-op, do it atomically, so that
   * no other threads potentially get put on the queues after we
   * check them for emptyness.
   */

  sigOldMask = sigblock(sigmask(SIGVTALRM));

  priRunning = (Int)pRunningThread->priPriority;
  fLowEmpty  = cond_is_empty(pcondReadyThreads[PRIORITY_LOW]);
  fHighEmpty = cond_is_empty(pcondReadyThreads[PRIORITY_HIGH]);

  if ((priRunning == PRIORITY_HIGH && fHighEmpty) ||
      (priRunning == PRIORITY_LOW  && fHighEmpty && fLowEmpty))
    {
      sigsetmask(sigOldMask);
      return;  /* NO-OP */
    }

  /* This will save its context and put it on the right ready queue */
  t_wait(pcondReadyThreads[priRunning]);

  sigsetmask(sigOldMask);
} 
 

 /************************************************************************ 
 *  FUNCTION: t_name
 *  HISTORY: 
 *     10/26/93  ESF  Created.
 *     10/27/93  ESF  Modified to recognize an idle system.
 *  PURPOSE:
 *     Returns the name of the current thread, or else if there are no
 *   active threads, it returns "< System Idle >".
 *  NOTES: 
 ************************************************************************/ 
String t_name(void)
{
  char      *strName;
  sigset_t   sigOldMask;

  /* If we're not careful, we could check for pRunningThread, and then
   * have a pre-emptive thread switch occur, and pRunningThread could 
   * potentially get NULL'ed, so do it carefully.
   */

  sigOldMask = sigblock(sigmask(SIGVTALRM));

  if (pRunningThread)
    strName = pRunningThread->strThreadName;
  else
    strName = "< System Idle >";

  sigsetmask(sigOldMask);

  return strName;
}


/************************************************************************ 
 *  FUNCTION: t_debug
 *  HISTORY: 
 *     10/26/93  ESF  Created 
 *  PURPOSE: 
 *     If the file handle passed in is non-NULL, uses this handle as the
 *   output for any debugging statements, by setting the global variable
 *   hLogFile.  Otherwise, if a NULL handle is passed in, it resets the
 *   global handle to cease the debugging output.
 *  NOTES: 
 ************************************************************************/ 
void t_debug(FILE *hFile)
{
  hLogFile = hFile;
}


/************************************************************************ 
 *  FUNCTION: t_cs_entry
 *  HISTORY: 
 *     10/30/93  ESF  Created 
 *     11/24/93  ESF  Modified to work with nested CS
 *  PURPOSE: 
 *     Blocks signals, so that any code between a t_cs_entry and a 
 *   t_cs_exit does not get interrupted by a signal.  Used for
 *   implementing critical sections.  If you don't match this with a 
 *   corresponding call to t_exit_all, the premptiveness of EThreads
 *   will be lost.
 *  NOTES: 
 ************************************************************************/ 
void t_cs_entry(void) { sigblock(sigmask(SIGVTALRM)); uiCSDepth++; }


/************************************************************************ 
 *  FUNCTION: t_cs_exit
 *  HISTORY: 
 *     10/30/93  ESF  Created 
 *     11/24/93  ESF  Modified to work with nested CS
 *  PURPOSE: 
 *     Sets the signal mask so as to let any signals go through again.
 *   Used for implementing critical sections with t_cs_entry.
 *  NOTES: 
 ************************************************************************/ 
void t_cs_exit(void) { if (!--uiCSDepth) sigsetmask(0L); }


/************************************************************************ 
 *  FUNCTION: cond_create
 *  HISTORY:
 *     10/01/93  ESF  Created.
 *     11/07/93  ESF  Fixed race condition.
 *  PURPOSE: 
 *     Dynamically allocates room for a new condition.  We need two 
 *   queues, one for threads blocked on the condition, and another 
 *   for pending signals.  If there are dead conditions around on
 *   the dead conditions queue, grabs one of the queue, otherwise
 *   builds a new one from scratch.
 *  NOTES: 
 ************************************************************************/ 
PCondition cond_create(void) 
{ 
  PCondition  pCond;
  sigset_t    sigOldMask = sigblock(sigmask(SIGVTALRM));

  /* We might not need to create a whole new condition */
  if (q_is_empty(pqueueDeadCond))
    {
      pCond = (PCondition)MEM_Alloc(sizeof(struct _Condition));  
      
      /* Create the two queues we'll be using */ 
      pCond->pBlockedQueue = q_create(); 
      pCond->pSignalsQueue = q_create();  
      
      /* Keep a pointer to the condition around, for later */
      q_insert(pqueueLiveCond, (any_ptr)pCond);
    }
  else
    pCond = (PCondition)q_remove(pqueueDeadCond);

  sigsetmask(sigOldMask);

  return (pCond);                       
} 
 
 
/************************************************************************ 
 *  FUNCTION: cond_is_empty 
 *  HISTORY: 
 *     10/01/93  ESF  Created 
 *     11/07/93  ESF  Fixed to prevent race condition.
 *  PURPOSE: 
 *     Returns TRUE <==> there are no threads blocked on a condition, 
 *   and FALSE otherwise.  
 *  NOTES: 
 ************************************************************************/ 
Boolean cond_is_empty(PCondition pCond) 
{
  Boolean   fEmpty;
  sigset_t  sigOldMask = sigblock(sigmask(SIGVTALRM));

  /* Find out the state of the queue atomically */
  fEmpty = q_is_empty(pCond->pBlockedQueue); 

  sigsetmask(sigOldMask);
  
  return(fEmpty);
} 
 
 
/************************************************************************ 
 *  FUNCTION: cond_destroy
 *  HISTORY: 
 *     10/01/93  ESF  Created.
 *     11/07/93  ESF  Modified to use the dead condition queue.
 *  PURPOSE: 
 *     Destroys a condition.  Doesn't actually free the memory used
 *   by the condition, because then we'd have to somehow remove the
 *   condition from the live condition queue, so that if we exited, 
 *   we wouldn't free it twice.  By using condition recycling, we
 *   are guaranteed that we WILL NOT use more memory than we would
 *   if we took the time to free it and remove it from the queue,
 *   and, the performance it greatly improved!
 *  NOTES: 
 ************************************************************************/ 
void cond_destroy(PCondition pCond) 
{
  sigset_t sigOldMask = sigblock(sigmask(SIGVTALRM));

  /* This condition might have signals and/or threads queued.  Destroy 
   * the queue with the signals, but the threads queue is more of a 
   * problem.  There may be threads waiting on this condition.  However,
   * they will never get signalled, so put them on the dead threads queue
   * for recycling.
   */

  /* Rebuild signal queue */
  q_destroy(pCond->pSignalsQueue);
  pCond->pSignalsQueue = q_create();

  /* Recycle the threads */
  while (!cond_is_empty(pCond))
    q_insert(pqueueDeadThreads, (any_ptr)q_remove(pCond->pBlockedQueue));

  /* Recycle the condition */
  q_insert(pqueueDeadCond, (any_ptr)pCond);  

  sigsetmask(sigOldMask);
} 

 
 /************************************************************************ 
 *  FUNCTION: cond_registerRT
 *  HISTORY: 
 *     11/02/93  ESF  Created.
 *     11/08/93  ESF  Fixed bastard bug.
 *  PURPOSE: 
 *     Sets up a new CondNode in the timed condition list, and 
 *   initializes it.  For more information on the data structures used,
 *   see the top of this file, where they are defined and explained in
 *   great detail.  Essentially, a new CondNode is built, and the time
 *   calculated when the condition next needs to be signalled.  Based on
 *   this value, it is inserted into the list, which is organized in
 *   chronological order.
 *  NOTES: 
 ************************************************************************/ 
void cond_registerRT(PCondition pCond, clock_t clkInterval)
{
  CondNode  *pNode;
  sigset_t   sigOldMask = sigblock(sigmask(SIGVTALRM)); 

  /* Create a new CondNode structure and initialize it */
  pNode = (CondNode *)MEM_Alloc(sizeof(CondNode));
  pNode->rtTimingInfo.registered = clock();
  pNode->rtTimingInfo.interval   = clkInterval;
  pNode->rtTimingInfo.iterations = 0;
  pNode->clkNextRunTime = pNode->rtTimingInfo.registered + clkInterval;
  pNode->pCond = pCond;
  pNode->next  = NULL;

  /* Now insert the new node in the list, in chronological order */
  _timed_cond_chrono_insert(pNode);
  
  sigsetmask(sigOldMask);
}


 /************************************************************************ 
 *  FUNCTION: _timed_cond_destroy_list
 *  HISTORY: 
 *     11/02/93  ESF  Created.
 *     11/08/93  ESF  Fixed bug, set list to NULL after freeing.
 *  PURPOSE: 
 *    Frees all of the memory taken by the list of timed conditions.
 *  NOTES: 
 ************************************************************************/ 
void _timed_cond_destroy_list(void)
{
  CondNode *p, *q;

  /* Destroy the global queue we use */
  q_destroy(pTempQueue);

  /* Destroy all of the timed condition nodes.  All of the
   * conditions that might be in here are freed by
   * _t_free_all_memory, since they are also stored on
   * the live condition queue.
   */
  
  for (p=TimedCondList.pList; p; p=q)
    q=p->next, MEM_Free(p);

  TimedCondList.pList = NULL;
}


 /************************************************************************ 
 *  FUNCTION: _timed_cond_issue_signalsRT
 *  HISTORY: 
 *     11/02/93  ESF  Created.
 *     11/07/93  ESF  Fixed paranoid race condition possibility.
 *     11/09/93  ESF  Changed to handle skewing better.
 *  PURPOSE: 
 *     Walk through the list of timed conditions, signalling all of the
 *   expired conditions.  This may be a no-op.  As we signal each of them
 *   take them off of the list and into a queue.  At the end, remove each
 *   one from the queue, update its parameters, and then reinsert it into
 *   the list in chronological order.
 *  NOTES: 
 ************************************************************************/ 
void _timed_cond_issue_signalsRT(void)
{
  clock_t    clkTime = clock();
  CondNode  *p;
  sigset_t   sigOldMask;

  sigOldMask = sigblock(sigmask(SIGVTALRM));

  /* Return iff there are no timed conditions, or none have "gone off" */
  if (!TimedCondList.pList ||
      TimedCondList.pList->clkNextRunTime > clkTime)
    {
      sigsetmask(sigOldMask);
      return;
    }
  
  /* Run through and signal all of the needed conditions, and at the same 
   * time through all of the nodes on a queue, after updating them.  We 
   * need to use a queue, because if we didn't, we might end up trying to 
   * signal a thread twice without letting it run.  This way, even if a 
   * timed condition is more than one signal behind, it has to wait for 
   * the next clock tick.  If a high priority thread does hog the system, 
   * a Real Time scheduling failure is likely to occur, though, if we let it.
   */
  
  for (;
       TimedCondList.pList && 
       TimedCondList.pList->clkNextRunTime <= clkTime;
       TimedCondList.pList=TimedCondList.pList->next)
    {             
      p = TimedCondList.pList;

      /* If there is a thread waiting, signal it, otherwise if we are 
       * meant to handle Real-Time scheduling failures, exit.
       */
      
      if (!cond_is_empty(p->pCond))
	t_sig(p->pCond, (any_ptr)&p->rtTimingInfo, FALSE);
      else if (fHandleFailures)
	t_exit_all(T_HARD_RT_FAIL);

      /* Update the time of next signal, update misc info fields.
       * We may run in situations where timed conditions have been 
       * starved for a while, because of a critical section.  We
       * have to be careful of how to handle this, to prevent skew.
       * The easy way is just to add the interval to clkNextRunTime,
       * but, this may be in the past, if the condition has been 
       * starved for a while.  In this case, add on as many intervals
       * as needed to bring the next clock time into the future.
       * In this way, intervals should stay together (skewing), and
       * we have less chance of generating Real Time failures.  Note
       * that in a genuine real-time system this would probably be 
       * unaceptable, but it's not -- it's UNIX!  Note that we
       * only add one to the number of times signalled, although it
       * _might_ have wanted to be signalled more times during the
       * time period.
       */

      p->rtTimingInfo.signaled = clock();
      p->rtTimingInfo.iterations++;

      while (p->clkNextRunTime <= p->rtTimingInfo.signaled) 
	p->clkNextRunTime += p->rtTimingInfo.interval;

      q_insert(pTempQueue, (any_ptr)p);
    }

  /* And now put all of the signalled nodes back on the list */
  while (!q_is_empty(pTempQueue))
    _timed_cond_chrono_insert((CondNode *)q_remove(pTempQueue));

  sigsetmask(sigOldMask);
}


 /************************************************************************ 
 *  FUNCTION: _timed_cond_chrono_insert
 *  HISTORY: 
 *     11/02/93  ESF  Created.
 *  PURPOSE: 
 *     Takes a CondNode, and based on the clkNextRunTime field, inserts
 *   it into the TimedCondList in chronological order, so that the
 *   conditions that need to be signalled sooner are earlier in the list. 
 *  NOTES: 
 ************************************************************************/ 
void _timed_cond_chrono_insert(CondNode *pNode)
{
  CondNode   *pLast, *p;

  /* Is list empty or do we need to put at the beginning? */
  if (TimedCondList.pList == NULL ||
      TimedCondList.pList->clkNextRunTime >= pNode->clkNextRunTime)
    {
      pNode->next = TimedCondList.pList;
      TimedCondList.pList = pNode;
    }
  else
    {
      /* Run down the list to find the place of insertion */
      for (p=pLast=TimedCondList.pList;
	   p && p->clkNextRunTime < pNode->clkNextRunTime; 
	   pLast=p, p=p->next)
	; /* TwiddleThumbs() */
      
      pNode->next = pLast->next;
      pLast->next = pNode;
    }
}


 /************************************************************************ 
 *  FUNCTION: cond_unregisterRT
 *  HISTORY: 
 *     11/02/93  ESF  Created.
 *     11/30/93  ESF  Fixed race condition.
 *  PURPOSE: 
 *     Seaches through the TimedCondList, and if the Condition that user
 *   is trying to remove is in the list, remove it, and free the memory
 *   that it takes.
 *  NOTES: 
 *     The actual condition is not frees, since this is independant, and
 *   and will be freed later.
 ************************************************************************/ 
void cond_unregisterRT(PCondition pCond)
{
  CondNode  *p;
  sigset_t   sigMask = sigblock(sigmask(SIGVTALRM));
  
  /* Is the operation bogus? */
  if (TimedCondList.pList == NULL)
    {
      sigsetmask(sigMask);
      return;
    }

  /* Special case the first one on the list */
  if (TimedCondList.pList->pCond == pCond)
    {
      p = TimedCondList.pList;
      TimedCondList.pList = p->next;
      MEM_Free(p);
      sigsetmask(sigMask);
      return;
    }

  /* OK, we have to go out and look for it */
  for(p=TimedCondList.pList;
      p->next && p->next->pCond != pCond;
      p=p->next)
    ; /* TwiddleThumbs() */

  /* Remove the element if found */
  if (p->next)
    {
      CondNode *q = p->next;
      p->next = q->next;
      MEM_Free(q);
    }
  
  sigsetmask(sigMask);
}

 
/************************************************************************ 
 *  FUNCTION: _t_switch_context 
 *  HISTORY: 
 *     10/02/93  ESF  Created. 
 *     10/02/93  ESF  Added longjmp to TheEnd context. 
 *     10/02/93  ESF  Added code to check for stack overflow. 
 *     10/26/93  ESF  Changed to implement piority scheduling.
 *     11/02/93  ESF  Fixed race condition.
 *  PURPOSE: 
 *     Switches into the context of the newly active thread.  This 
 *   may be as easy as longjmping to it, but if it's the first time around, 
 *   we need to set up the context. 
 *  NOTES: 
 ************************************************************************/ 
void _t_switch_context(void) 
{
  /* If the thread is already live, just switch contexts */ 
  if(pRunningThread->iState == THREAD_WAITING || 
     pRunningThread->iState == THREAD_BLOCKED) 
    { 
      pRunningThread->iState = THREAD_RUNNING; 
      _t_debug_dump("CONTEXT_IN");
      _t_arm_timer();
      longjmp(pRunningThread->State, 1); 
    } 
  
  /* We need to set up a context for the thread and then jump to it */ 
  if(!setjmp(pRunningThread->State)) 
    { 
      /* Set the new stack for the thread.  This is very system dependant. 
       * However, in all setjmp implementations I've seen, the stack pointer  
       * is directly accessable through some offset of the jmp_buf.   
       * Therefore, the dependant code is limited to defining STACK_POINTER. 
       * We set the stack pointer to point to the end of the stack, minus 
       * buffer room and we align it on a 64 bit boundary.  Most architectures 
       * are friendly with this and the only common machine that would need a 
       * little extra code is the HP9000, on which the stack grows upwards.  
       * Other chip families, such as MIPS, Intel, SPARC, VAX, and Motorola 
       * only need the stack pointer offset changed.  Also, some systems don't
       * implement jmp_buf as an array, but rather as a structure (i.e. Linux).
       * Because of this we cast the State (jmp_buf) to an pointer before 
       * proceeding.
       */
  
      ((UInt *)pRunningThread->State)[STACK_POINTER] = 
	(((UInt)pRunningThread->pStack + (THREAD_STACK-1) -
	  LOCALS_BUFFER) & ~7);
      
      /* Set this so that we can check for stack overflow later */ 
      pRunningThread->pStack[0] = STACK_COOKIE; 
      
      /* The thread is going to running in a jiffy */ 
      pRunningThread->iState    = THREAD_RUNNING; 
      
      /* We just set up the new context for a thread */ 
      _t_arm_timer();
      longjmp(pRunningThread->State, 1); 
    } 
  else 
    {
      /* Hello world!  A thread is born. */
      _t_debug_dump("CONTEXT_IN");

      /* Make sure that signals are enabled before we call the function */
      sigsetmask(0L); 

      /* Invoke the thread */
      pRunningThread->thdProc(pRunningThread->pvArg); 
      
      /* At this point we will have a dead thread */ 
      sigblock(sigmask(SIGVTALRM));
      _t_debug_dump("EXIT");
      _t_debug_dump("CONTEXT_OUT"); 
      _t_cleanup();
      _t_schedule();
    } 
} 

 
 
/************************************************************************ 
 *  FUNCTION: _t_cleanup 
 *  HISTORY: 
 *     10/02/93  ESF  Created. 
 *     10/02/93  ESF  Stack overflow code. 
 *     10/20/93  ESF  Changed to recycle threads.
 *  PURPOSE: 
 *     Takes the running thread, and destroys it by recycling it.
 *  NOTES: 
 *     This function is not made into a critical section since it's 
 *   always part of another critical section.
 ************************************************************************/ 
void _t_cleanup(void) 
{
  /* Check to see if there's been a stack overflow */
  if(pRunningThread->pStack[0] != STACK_COOKIE) 
   { 
     printf("Fatal Error: Stack overflow in thread: EThreads Unstable!"); 
     exit(-1); 
   }  
 
  /* Recycle the thread */
  q_insert(pqueueDeadThreads, pRunningThread);
  pRunningThread = (Thread *)NULL;
} 


/************************************************************************ 
 *  FUNCTION: _t_schedule
 *  HISTORY: 
 *     10/26/93  ESF  Created. 
 *     11/03/93  ESF  Cleaned up, broke up into 4 cases.
 *  PURPOSE: 
 *     Handles scheduling for EThreads.  First, if there is a running 
 *   thread, then given that its context will be saved by this point,
 *   it puts it on the tail of the appropriate queue.  Then it schedules
 *   the next thread to run.  See the comments in the function for how
 *   it does this.  After it schedules the next thread, it calls 
 *   _t_switch_context to run it.
 *  NOTES: 
 *    The scheduler runs in the context of the thread that is being
 *   switched out, as opposed to a separate context (like a separate
 *   scheduler thread).  This is a more monolithic approach, with
 *   large performance gains, as opposed to the separate scheduler
 *   thread, which is reminiscent of a micro-kernel approach, where 
 *   scheduling and memory management can filter up from the lower
 *   levels of the kernel to a personality server running in user
 *   space.
 ************************************************************************/ 
void _t_schedule(void)
{
  /* If there was a running thread, put it on the tail of the appropriate 
   * ready queue, a la round robin scheduling.  The state of the thread 
   * will either have been saved by t_wait(), or the thread won't have
   * a context yet, so in either case we don't have to worry about saving
   * its context.
   */
  
  if (pRunningThread)
    {
      _t_debug_dump("CONTEXT_OUT");
      
      /* The thread now waits. */
      pRunningThread->iState = THREAD_WAITING; 
      
      /* Put the thread on the appropriate queue */
      q_insert(pcondReadyThreads[pRunningThread->priPriority]->pBlockedQueue, 
	       (any_ptr)pRunningThread);
    } 
  
  /*
   *   There are four things that can happen as a result
   *   of scheduling, in the following order:
   *
   *      1. If there are no threads ready, but there are timed
   *         conditions around, idle until one of the timed 
   *         conditions becomes "active."
   *      2. If there is a high priority thread ready, prepare it to run.
   *      3. If there is a low priority thread ready, prepare it to run.
   *      4. Otherwise we in a position to exit, so longjmp
   *         to the exit context to clean up.
   */

  if (cond_is_empty(pcondReadyThreads[PRIORITY_HIGH]) &&
      cond_is_empty(pcondReadyThreads[PRIORITY_LOW]) &&
      !pRunningThread && 
      !_timed_cond_empty())
    {
      /* Loop until time to signal one of them */
      while (_timed_cond_next_time() > clock())
	; /* TwiddleThumbs() */
      
      /* This moves the threads onto the ready queues */
      _timed_cond_issue_signalsRT();
    }

  /* Now ready a thread for execution, if there is one available */
  if (!cond_is_empty(pcondReadyThreads[PRIORITY_HIGH]))
    pRunningThread = (Thread *)
      q_remove(pcondReadyThreads[PRIORITY_HIGH]->pBlockedQueue);
  else if (!cond_is_empty(pcondReadyThreads[PRIORITY_LOW]))
    pRunningThread = (Thread *)
      q_remove(pcondReadyThreads[PRIORITY_LOW]->pBlockedQueue);
  else
    {
      D_PrintStr("All threads exited...\n");
      t_exit_all(T_OK);
    }
  
  /* If we reach here, there is a thread ready to run */
  _t_switch_context();
}


/************************************************************************ 
 *  FUNCTION: _t_debug_dump
 *  HISTORY: 
 *     10/26/93  ESF  Created. 
 *     11/07/93  ESF  Guarded against paranoid race condition possibility.
 *  PURPOSE: 
 *     Dumps a debugging event to the file registered with EThreads.
 *  NOTES: 
 *     Uses a safe version of fprintf, which will not get interrupted
 *   by signals.
 ************************************************************************/ 
void _t_debug_dump(String strEvent)
{
  time_t    t;
  sigset_t  sigOldMask = sigblock(sigmask(SIGVTALRM));

  if (hLogFile)
    _t_fprintf(hLogFile, "%7d %15s%s%s\n", clock(), strEvent, "  ", t_name());

  sigsetmask(sigOldMask);
}


/************************************************************************ 
 *  FUNCTION: _t_sig_handler
 *  HISTORY: 
 *     10/27/93  ESF  Created. 
 *     11/02/93  ESF  Fixed scheduling bug.
 *  PURPOSE: 
 *     This is the signal handler.  First, set fArmed to FALSE to
 *   indicate that we can arm the timer at some future time.  Next
 *   reregister the signal handler.  Then, optimize by seeing if
 *   we really need to switch threads.  If not return right away.
 *   If so, schedule the next thread to run, after saving the context
 *   of the currently running thread if there is one.
 *  NOTES: 
 *     There is real reason to mask out signals, since we are not going
 *   to get any from the itimers, since they are configured to be one-
 *   shot, but we do so anyway, just out of the paranoid fear that a 
 *   signal may be generated by an ignorant user.  Better safe than
 *   sorry.
 ************************************************************************/ 
void _t_sig_handler(int iSig)
{
  sigset_t  sigOldMask = sigblock(sigmask(SIGVTALRM));

  fArmed = FALSE;

  /* Reregister the handler */
  signal(iSig, (void(*)())_t_sig_handler);

  _t_debug_dump("TIMER_INT");

  /* Signal all the timed conditions */
  _timed_cond_issue_signalsRT();

  /* If there is a thread running, wait for the queue to be signaled.
   * This will save the context, and schedule the next thread.  
   * Otherwise we need to schedule the first thread.  We
   * can optimize this procedure a bit, becuase if there's only
   * one thread of low priority running, or only high priority threads
   * running, we don't need to switch contexts at all -- this is very 
   * cheap and it helps that the scheduler runs in the local thread's context.
   */

  /* High priority threads don't get interrupted */
  if(pRunningThread && pRunningThread->priPriority == PRIORITY_HIGH)
    {
      sigsetmask(sigOldMask);
      _t_arm_timer();
      return;
    }
  
  /* Maybe only low priority threads are running and there's only one */
  if(pRunningThread && pRunningThread->priPriority == PRIORITY_LOW &&
     cond_is_empty(pcondReadyThreads[PRIORITY_LOW]) &&
     cond_is_empty(pcondReadyThreads[PRIORITY_HIGH]))
    {
      sigsetmask(sigOldMask);
      _t_arm_timer();
      return;
    }
  
  /* Otherwise, we need to schedule in a new thread.  */
  if (pRunningThread)
    t_yield();
  else
    _t_schedule();
}


/************************************************************************ 
 *  FUNCTION: _t_fprintf
 *  HISTORY: 
 *     11/01/93  ESF  Created. 
 *  PURPOSE: 
 *     A version of fprintf that will not get interrupted by timer signals.
 *  NOTES: 
 ************************************************************************/ 
void _t_fprintf(FILE *hFile, String strFormat, ...)
{
  va_list   vaArgs;
  sigset_t  sigOldMask;

  va_start(vaArgs, strFormat);

  /* Do the output in a critical section */
  sigOldMask = sigblock(sigmask(SIGVTALRM));

  vfprintf(hFile,  strFormat, vaArgs);
  va_end(vaArgs);
  fflush(hFile);

  sigsetmask(sigOldMask);
}


/************************************************************************ 
 *  FUNCTION: _t_free_all_memory
 *  HISTORY: 
 *     11/07/93  ESF  Created. 
 *  PURPOSE: 
 *     This function frees all of the memory left over by EThreads, in
 *   anticipation of exiting the package.  Everything, including dead 
 *   threads, live and dead conditions, timed conditions, ready threads, 
 *   and the running thread is destroyed.
 *  NOTES: 
 ************************************************************************/ 
void _t_free_all_memory(void)
{
  Thread      *pThread;
  PCondition   pCond;

  /* Destroy low priority threads queue, along with possible threads */
  while (!cond_is_empty(pcondReadyThreads[PRIORITY_LOW]))
    {
      pThread = (Thread *)
	q_remove(pcondReadyThreads[PRIORITY_LOW]->pBlockedQueue);
      _t_destroy_thread(pThread);
    }
  _t_destroy_cond(pcondReadyThreads[PRIORITY_LOW]); 
  
  /* Destroy high priority threads queue, along with possible threads */
  while (!cond_is_empty(pcondReadyThreads[PRIORITY_HIGH]))
    {
      pThread = (Thread *)
	q_remove(pcondReadyThreads[PRIORITY_HIGH]->pBlockedQueue);
      _t_destroy_thread(pThread);
    }
  _t_destroy_cond(pcondReadyThreads[PRIORITY_HIGH]); 

  /* Destroy all of the dead threads that we have left around */
  while (!q_is_empty(pqueueDeadThreads))
    {
      pThread = (Thread *)q_remove(pqueueDeadThreads);
      _t_destroy_thread(pThread);
    }
  q_destroy(pqueueDeadThreads);
  
  /* Take care of destroying the timed conditions structure */
  _timed_cond_destroy_list();

  /* And now, take care of destroying all of the conditions the user 
   * has created to date.  We can do this because we have kept track of them 
   * in a queue.  In order to assure that the user hasn't already freed them, 
   * we cheat a little and make cond_destroy a no-op.  This makes the call 
   * cheap, since otherwise we would need to remove the condition from the
   * queue.  Perhaps we should keep them in a hash table, but this
   * complicated the package.  
   */

  while (!q_is_empty(pqueueLiveCond))
    {
      pCond = (PCondition)q_remove(pqueueLiveCond);
      
      /* Now remove all stale threads from the condition */
      while (!cond_is_empty(pCond))
	{
	  pThread = (Thread *)q_remove(pCond->pBlockedQueue);
	  _t_destroy_thread(pThread);
	}

      /* And finally, free the condition itself */
      _t_destroy_cond(pCond);
    }

  /* Was there a running thread?  If so, destroy it */
  if (pRunningThread)
    _t_destroy_thread(pRunningThread);

  /* And simply destroy the dead & live conditions queue */
  q_destroy(pqueueDeadCond); 
  q_destroy(pqueueLiveCond);
  pqueueDeadCond = (PQueue)NULL;
  pqueueLiveCond = (PQueue)NULL;
}



