/*
 * @COPYRIGHT@
 * 
 * x-kernel v3.3
 * 
 * Copyright (c) 1996,1993,1991,1990  Arizona Board of Regents
 * 
 * @COPYRIGHT@
 *
 * $RCSfile: scout_thread.c,v $
 *
 * HISTORY
 * $Log: scout_thread.c,v $
 * Revision 1.4  1996/06/19 16:23:29  slm
 * Update to brakmo's changes.
 *
 * Revision 1.3  1996/02/01  15:20:28  slm
 * Updated copyright and version.
 *
 * Revision 1.2  1995/08/28  16:14:30  acb
 * Initial revision for x3.3
 *
 * Revision 1.2  1994/11/22  21:18:48  hkaram
 * Added platform.h; Changed NORETURN to XNORETURN;
 * Fixed a bug in which the stack was not being returned.
 * Removed fpu_dirty instances
 *
 * Revision 1.1  1994/10/26  20:03:13  hkaram
 * Initial revision
 *
 * Revision 1.6  1994/08/30  18:20:29  davidm
 * Minor fixes.
 *
 * Revision 1.5  1994/08/30  17:02:14  davidm
 * Fixed major memory leak: dead_man() didn't get de-allocated if
 * next thread started via continuation (i.e., through start()).
 *
 * Revision 1.4  1994/08/30  16:48:06  davidm
 * Added support for ev4 performance counter (to avoid measuring the
 * idle-thread).
 *
 * Revision 1.3  1994/06/11  00:02:32  menze
 * Added copyright notice
 *
 * Revision 1.2  1994/05/14  23:56:26  davidm
 * (show_blocked): added.  Helps to keep track of where your threads go.
 *
 * Revision 1.1  1994/04/15  17:47:46  davidm
 * Initial revision
 */
/*
 * Threads package.
 */
#include <strings.h>
#include "xk_assert.h"
#include "scout_trace.h"
#include "platform.h"

#define NPRIORITIES	(SCOUT_THREAD_PRIORITY_MIN \
			 - SCOUT_THREAD_PRIORITY_MAX + 1)

static Scout_Thread *SThreadFreeList=NULL;

#ifdef XMEMTRACK

static int SthreadTrackId = 0;

extern char *xMallocTrack(unsigned, int);
extern char *xMallocZeroTrack(unsigned, int);
extern void xFreeTrack(char *, unsigned, int);
extern int  TrackGetId(char *);

#define xMalloc(s)     xMallocTrack(s, SthreadTrackId)
#define xMallocZero(s) xMallocZeroTrack(s, SthreadTrackId)

#endif

#define THREAD_DBG 

#ifdef THREAD_DBG
static int tdbgCreateCnt=0;
static int tdbgDeleteCnt=0;
static int tdbgAlloc=0;
static int tdbgStkAlloc=0;
static int tdbgStkCnt=0;

#ifdef XMEMTRACK

int tdbgPrint()
{
  printf("tdbgCreateCnt: %d, tdbgDeleteCnt: %d, diff: %d\n",
         tdbgCreateCnt, tdbgDeleteCnt, tdbgCreateCnt-tdbgDeleteCnt);
  printf("tdbgAlloc: %d\n", tdbgAlloc);
  printf("tdbgStkCnt: %d, tdbgStkAlloc: %d\n", tdbgStkCnt, tdbgStkAlloc);

  return 0;
}

#endif

#endif

struct scout_stack {
    union {
	void			*sp;		/* top of stack */
	struct scout_stack	*next;		/* next free stack */
    } u;
    void	*stack_limit;
    long	magic;				/* magic number */
};

int trace_scout_thread = 0;

static void start (void)  XNORETURN;	/* forward declaration */
static void retire (void) XNORETURN;	/* never returns */
static void sched (void);

static Scout_Thread_Options def_opts =
{
    "noname",
    0,
    DEFAULT_STACK_SIZE,
    SCOUT_THREAD_PRIORITY_STD
};
const Scout_Thread_Options	*scout_thread_default_options = &def_opts;

/*
 * Invariant: the currently running thread is "scout_thread_self" (it is
 * *not* in any ready_q!).
 */
Scout_Thread			*scout_thread_self = 0;

static Scout_Thread	*dead_man = 0;
static Scout_Thread	*idle_thread = 0;
static u_int		high_prio = SCOUT_THREAD_PRIORITY_MAX;
static Scout_Queue	ready_q[NPRIORITIES];

static struct scout_stack *first_stack = 0;

#ifdef THREAD_DBG

int ThreadFreeStacks(int keep)
{
  int cnt;
  struct scout_stack *sp;

  cnt = tdbgStkCnt - keep;
  for (sp=first_stack; cnt>0  &&  sp != NULL; cnt--,sp=first_stack) {
    first_stack = sp->u.next;
#ifdef XMEMTRACK
    xFreeTrack((char *)sp, DEFAULT_STACK_SIZE, SthreadTrackId);
#else
    xFree((char *)sp);
#endif
  }
  tdbgStkCnt = keep + cnt;
  return 0;
}

#endif

#define ATTACH_STACK(s) \
{ \
    (s) = first_stack; \
    if (s PREDICT_TRUE) { \
	first_stack = first_stack->u.next; \
    } else { \
	(s) = mkstack(); \
    } /* if */ \
    (s)->u.sp = (s)->stack_limit; \
}

#define DETACH_STACK(s) \
{ \
    (s)->u.next = first_stack; \
    first_stack = (s); \
}


#ifdef SCOUT_DEBUG
# ifdef SCOUT_KGDB
#  define STACK_CHECK() \
{ \
    if (scout_thread_free_stack() <= 0 || \
	scout_thread_self->stack->magic != MAGIC_COOKIE) \
    { \
	error("stack overflow!"); \
	error("kgdb: waiting for remote gdb..."); \
	kgdb_breakpoint(); \
	retire(); \
    } /* if */ \
}
# else /* !SCOUT_KGDB */
#  define STACK_CHECK() \
{ \
    if (scout_thread_free_stack() <= 0 || \
	scout_thread_self->stack->magic != MAGIC_COOKIE) \
    { \
	error("stack overflow!"); \
	retire(); \
    } /* if */ \
}
# endif /* !SCOUT_KGDB */
#else
# define STACK_CHECK()
#endif /* SCOUT_DEBUG */


#ifdef SCOUT_DEBUG

#define MAX_THREADS	256

static Scout_Thread	*blocked[MAX_THREADS];

#define HASH(a)	(((u_long)(a) >> 3) % MAX_THREADS)


static void
mark_blocked(Scout_Thread *t)
{
    int i, i0;

    i = i0 = HASH(t);
    while (blocked[i]) {
	i = (i + 1) % MAX_THREADS;
	if (i == i0) {
	    Kabort("scout_thread: mark_blocked: too many threads!");
	} /* if */
    } /* while */
    blocked[i] = t;
} /* mark_blocked */


static void
mark_unblocked(Scout_Thread *t)
{
    int i, i0;

    i = i0 = HASH(t);
    while (blocked[i] != t) {
	i = (i + 1) % MAX_THREADS;
	if (i == i0) {
	    Kabort("scout_thread: mark_unblocked: couldn't find thread!");
	} /* if */
    } /* while */
    blocked[i] = 0;
} /* mark_unblocked */


void
show_blocked(void)
{
    Scout_Thread *t;
    int i;

    printf("%-16s %-16s %-16s name:\n",
	   "tcb address:", "sp:", "pc:");
    for (i = 0; i < MAX_THREADS; ++i) {
	t = blocked[i];
	if (t) {
	    printf("%16p %16p %16p %s\n",
		   t, t->stack,
		   t->running ? GET_SAVED_PC(t->stack->u.sp) : t->fun,
		   scout_thread_get_name(t));
	} /* if */
    } /* for */
} /* show_blocked */


/*
 * Print string using minimal amount of stack space:
 */
static void
error(const char *msg)
{
    int ch;

    while ((ch = *msg++) != '\0') {
	putchar(ch);
    } /* while */
    putchar('\n');
} /* error */

#endif /* SCOUT_DEBUG */


static struct scout_stack*
mkstack(void)
{
    struct scout_stack *s;

    /*
     * For now, we have only one size of stacks (i.e., we ignore stack
     * size option).
     */
    s = (struct scout_stack *)xMalloc(DEFAULT_STACK_SIZE);
#ifdef THREAD_DBG
    tdbgStkCnt++;
    tdbgStkAlloc += DEFAULT_STACK_SIZE;
#endif
    if (!s PREDICT_FALSE) {
	Kabort(__FILE__": mkstack: out of memory");
    } /* if */
    s->stack_limit = (char*)s + DEFAULT_STACK_SIZE;
    s->magic = MAGIC_COOKIE;
    return s;
} /* mkstack */


/*
 * Instead of an endless loop calling scout_yield(), use
 * continuations.  This avoids having to waste a stack for the idle
 * thread.
 */
static void
idler(void *arg)
{
    scout_queue_append(&ready_q[scout_thread_self->option.priority],
		       scout_thread_self);
    scout_thread_self->running = FALSE;
    DETACH_STACK(scout_thread_self->stack);
    scout_thread_self->stack = 0;
    scout_thread_self = 0;		/* no need to save any state */
    sched();
} /* idler */


/*
 * Switch context from scout_thread_self to t.  This is tricky code.  You
 * should verify the generated assembly code.
 */
static void
cswtch(Scout_Thread *t)
{
    static Scout_Thread *old;

    old = scout_thread_self;
    scout_thread_self = t;
    if (old) {
	SAVE_STATE(old->stack->u.sp);
    } /* if */
    if (scout_thread_self->running) {
	LOAD_STATE(scout_thread_self->stack->u.sp);
    } else {
	scout_thread_self->running = TRUE;
	/*
	 * Switch to new stack and invoke start(); the second argument
	 * is just there to tell GCC that start() is really used.
	 */
	SWITCH_STACK_AND_START(scout_thread_self->stack->u.sp, start);
    } /* if */
} /* cswtch */


static void
sched(void)
{
    Scout_Thread *next;

    /* dispatch to highest priority thread: */
    while (1) {
	xAssert(high_prio <= SCOUT_THREAD_PRIORITY_MIN);
	next = (Scout_Thread*) scout_queue_remove(&ready_q[high_prio]);
	if (next) {
#ifdef SCOUT_PERFMON
	    /* scout_thread_self maybe 0 at this point, so don't rely on it! */
	    if (next == idle_thread) {
		ev4_disable_counters();
	    } else {
		ev4_enable_counters();
	    } /* if */
#endif
	    if (!next->stack) {
		ATTACH_STACK(next->stack);
	    } /* if */
	    cswtch(next);
	    if (dead_man) {
		ScoutTrace(scout_thread, TR_EVENTS,
			   (__FILE__": "
			    "freeing space of dead thread `%s' at %p",
			    scout_thread_get_name(dead_man), dead_man));
		DETACH_STACK(dead_man->stack);
 		dead_man->next = SThreadFreeList;
		SThreadFreeList = dead_man;
/*		xFree(dead_man); */
#ifdef THREAD_DBG
        	tdbgDeleteCnt++;
#endif
		dead_man = 0;
	    } /* if */
	    return;
	} /* if */
	++high_prio;
    } /* while */
} /* sched */


static Scout_Thread*
create(Scout_Thread_Func fun, const Scout_Thread_Options *options)
{
    Scout_Thread *t;
    char *mem;
    int name_len;

    name_len = strlen(options->name) + 1;

    /*
     * Make sure requested stack-size is reasonable:
     */
    if (options->stack_size < MIN_USEFUL_STACK_SIZE) {
	ScoutTrace(scout_thread, TR_ERRORS,
		   (__FILE__": "
		    "stack too small (%d bytes, should be >%d bytes)",
		    options->stack_size, MIN_USEFUL_STACK_SIZE));
	return 0;
    } /* if */
    if (options->priority > SCOUT_THREAD_PRIORITY_MIN) {
	ScoutTrace(scout_thread, TR_ERRORS,
		   (__FILE__": illegal thread priority %d specified",
		    options->priority));
	return 0;
    } /* if */

    /*
     * Allocate thread descriptor, and name string in one chunk:
     */
    if (SThreadFreeList != NULL) {
      mem = (char *)SThreadFreeList;
      SThreadFreeList = SThreadFreeList->next;
#ifdef THREAD_DBG
      tdbgCreateCnt++;
#endif
    }
    else {
      mem = xMalloc(sizeof(Scout_Thread) + 64);
#ifdef THREAD_DBG
      tdbgCreateCnt++;
      tdbgAlloc += sizeof(Scout_Thread) + 64;
#endif
    }
    if (!mem) {
	ScoutTrace(scout_thread, TR_EVENTS,
		   (__FILE__": not enough memory for new thread"));
	return 0;
    } /* if */

    /* initialize memory: */
    t = (Scout_Thread*) mem;
    t->option		= *options;
    t->option.name	= (char*) t + sizeof(Scout_Thread);
    t->running		= FALSE;
    t->fun		= fun;
    t->stack		= 0;
    if (name_len > 64) {
      printf("ERROR: options->name is too long (%d) in Scout thread\n",
             name_len);
      exit(1);
    }
    strcpy(t->option.name, options->name);

#ifdef SCOUT_DEBUG
    mark_blocked(t);
#endif
    return t;
} /* create */


/*
 * Retire the currently executing thread and invoke the scheduler.
 * All memory associated with the current thread is freed.
 */
static void
retire(void)
{
    dead_man = scout_thread_self;	/* let next thread deallocate space */
    scout_thread_self = 0;		/* avoid state saving */
    sched();
} /* retire */


/*
 * Invoke the initial function of thread scout_thread_self.  If it ever
 * returns, we simply retire the thread.
 */
static void
start(void)
{
    if (dead_man) {
	ScoutTrace(scout_thread, TR_EVENTS,
		   (__FILE__":start: freeing space of dead thread `%s' at %p",
		    scout_thread_get_name(dead_man), dead_man));
	DETACH_STACK(dead_man->stack);
/*	xFree(dead_man); */
        dead_man->next = SThreadFreeList;
        SThreadFreeList = dead_man;
#ifdef THREAD_DBG
        tdbgDeleteCnt++;
#endif
	dead_man = 0;
    } /* if */

    ScoutTrace(scout_thread, TR_EVENTS,
	       (__FILE__": starting thread `%s' at %p free stack %d bytes",
		scout_thread_get_name(scout_thread_self),
		scout_thread_self, scout_thread_free_stack()));

    (*scout_thread_self->fun)(scout_thread_self->option.arg);

    ScoutTrace(scout_thread, TR_EVENTS,
	       (__FILE__": thread `%s' (%#p) terminating.",
		scout_thread_get_name(scout_thread_self), scout_thread_self));
    retire();
} /* start */


void
scout_thread_init(Scout_Thread_Func user_init, void *user_arg)
{
    int prio;
    Scout_Thread_Options to;
    Scout_Thread *t;

#ifdef XMEMTRACK
    SthreadTrackId = TrackGetId("Scout Thread");
#endif

    for (prio = 0; prio < NPRIORITIES; ++prio) {
	scout_queue_init(&ready_q[prio]);
    } /* for */
#ifdef SCOUT_DEBUG
    bzero(blocked, sizeof(blocked));
#endif

    /* create initial thread: */
    to = def_opts;
    to.name = "initializer";
    to.arg  = user_arg;
    t = create(user_init, &to);
    if (!t) {
	Kabort("scout_thread_init: failed to create thread `%s'",
		    to.name);
    } /* if */
    scout_thread_wakeup(t);

    /* create idle thread: */
    to = def_opts;
    to.name = "idler";
    to.arg  = 0;
    to.priority = SCOUT_THREAD_PRIORITY_MIN;
    idle_thread = create(idler, &to);
    if (!idle_thread) {
	Kabort("scout_thread_init: failed to create thread `%s'",
		    to.name);
    } /* if */
    scout_thread_wakeup(idle_thread);

    /* terminate boot stack and get things going: */
    retire();
} /* scout_thread_init */


Scout_Thread*
scout_thread_create(Scout_Thread_Func fun, const Scout_Thread_Options *options)
{
    STACK_CHECK();
    return create(fun, options);
} /* scout_thread_create */


void
scout_thread_stop(void)
{
    ScoutTrace(scout_thread, TR_EVENTS,
	       ("scout_thread_stop: thread `%s' (%p) terminating.",
		scout_thread_get_name(scout_thread_self), scout_thread_self));
    retire();
} /* Scout_ThreadStop */


void
scout_thread_suspend(void)
{
    STACK_CHECK();
#ifdef SCOUT_DEBUG
    mark_blocked(scout_thread_self());
#endif    
    sched();
} /* scout_thread_suspend */


void
scout_thread_suspend_with_continuation(void)
{
    STACK_CHECK();
#ifdef SCOUT_DEBUG
    mark_blocked(scout_thread_self());
#endif    
    scout_thread_self->running = FALSE;
    DETACH_STACK(scout_thread_self->stack);
    scout_thread_self->stack = 0;
    scout_thread_self = 0;		/* no need to save any state */
    sched();
} /* scout_thread_suspend_with_continuation */


void
scout_thread_wakeup(Scout_Thread *t)
{
#ifdef SCOUT_DEBUG
    mark_unblocked(t);
#endif    
    xAssert(t->option.priority <= SCOUT_THREAD_PRIORITY_MIN);
    scout_queue_append(&ready_q[t->option.priority], t);
    if (t->option.priority < high_prio) {
	high_prio = t->option.priority;
    } /* if */
} /* scout_thread_wakeup */


void
scout_thread_yield(void)
{
    STACK_CHECK();
    scout_queue_append(&ready_q[scout_thread_self->option.priority],
		       scout_thread_self);
    sched();
} /* scout_thread_yield */


int
scout_thread_free_stack(void)
{
    char sp;

    return (&sp - (char*)scout_thread_self->stack) - MIN_STACK_SIZE;
} /* scout_thread_free_stack */

			/*** end of scout_thread.c ***/