/*     
 * $RCSfile: event.c,v $
 *
 * x-kernel v3.3
 *
 * Copyright (c) 1993,1991,1990,1996  Arizona Board of Regents
 *
 * $Log: event.c,v $
 * Revision 1.4  1997/03/17 01:29:31  dorgival
 * Changed tracing to make timing wheel locking explicit
 *
 * Revision 1.3  1997/03/16  18:23:15  dorgival
 * Increased tracing info with this_thread->status
 *
 * Revision 1.2  1997/03/11 20:57:59  dorgival
 * Created xk_thread_t and updated threadSelf()
 *
 * Revision 1.1  1997/03/11 20:47:08  dorgival
 * Initial revision
 *
 *
 */

 /*
 * Event manager.  This module implements a facility for managing
 * timeouts.  Both, scheduling timeouts via evSchedule() and
 * canceling them via eventCancel() are as efficient as possible.
 * This is achieved via a "timing wheel."  It consists of a number
 * (EVENT_WHEEL_SIZE) of queues.  All events with a firing time
 * that have the same low-order bits (modulo EVENT_WHEEL_SIZE)
 * go into the same queue.  With an appropriate choice of
 * EVENT_WHEEL_SIZE, each queue therefore will be relatively
 * short, guaranteeing efficient insertion into a queue.  Furthermore,
 * with each tick, the clock routine has to inspect a single queue
 * only to find events that are ready to fire.
 */

/*
 * To work with Paragon P-threads, this module is structured as follows:
 * soft_clock is an independent pthread, not under the xk_lock
 * coordination. It uses a dummy condition, which is never signalled,
 * to suspend for fixed intervals by using the timed condition wait call.
 * When it wakes up, if verifies the current clock, updates the wheel
 * and suspends itself again.
 * 
 * Since it is not under control of xk_lock, a different mutex
 * is used just to control access to this module. Since the functions
 * available to x-kernel threads (evCreate, evDetach, evCancel, etc.)
 * do not block but if they have to wait for the mutex, deadlock is
 * guaranteed never to happen.
 *
 * Accesses should be short, so we keep this controlled by a single
 * mutex, with no condition variables.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/timers.h>
#include "/usr/include/pthread.h"

#include "event.h"
#include "event_i.h"
#include "xk_thread.h"
#include "trace.h"
#include "xk_debug.h"
#include "x_util.h"

#define EVENT_WHEEL_SIZE    128
#define EVENT_CACHE_SIZE     32

#define E3 (1000)
#define E6 (1000000)

/*
 * soft_clock, the function responsible for time keeping, uses usleep()
 * to keep track of the time. It blocks only the calling thread. Tests
 * show that two threads trying to use usleep a the same time interfere
 * with each other, so no other use of usleep should be allowed.
 * It seems a second thread may use sleep without causing problems.
 */
static void* soft_clock (void* us_interval_as_ptr);
static void* hb (void* arg);

extern void usleep( u_long usec );

static u_long		soft_time = 0;	/* softClock's idea of "now" */
static u_long		usec_per_tick;	/* interval between ticks */
static struct Event	wheel[EVENT_WHEEL_SIZE];
static int		nevents_cached;
static Event		event_cache;

int traceevents;

static u_long timeNowInTicks( void );
static void event_stub(void* arg);

/*
 * We need a new mutex to make this module into an independed monitor
 */
static pthread_mutex_t timing_wheel_mutex;

Map             localEventMap;

u_long
timeNowInTicks( void )
{
  struct timespec tp;

  if ( getclock( TIMEOFDAY, &tp ) < 0 )
  {
    Kabort("timeNowInTicks: gettimer failed. Exiting!");
  }
  return ( tp.tv_sec*E6 + tp.tv_nsec/E3 ) / usec_per_tick;
}

static void
cache_event (Event e)
{
    if (nevents_cached < EVENT_CACHE_SIZE) {
	xTrace1(events, TR_DETAILED, "event.cache_event: caching event 0x%p", e);
	++nevents_cached;
	e->next = event_cache;
	event_cache = e;
    } else {
	xTrace1(events, TR_DETAILED, "event.cache_event: freeing event 0x%p", e);
	free(e);
    }
}


static Event
get_event (void)
{
    Event e;

    if (nevents_cached > 0) {
	--nevents_cached;
	e = event_cache;
	event_cache = event_cache->next;
	xTrace1(events, TR_DETAILED,
		"event.get_event: picked up event 0x%p from cache", e);
    } else {
	/* no cached event---have to create a new one */
	e = malloc(sizeof(struct Event));
	xTrace1(events, TR_DETAILED,
		"event.get_event: allocated event 0x%p", e);
    }
    assert(e);
    return e;
}

static void
fire (Event e)
{
    xTrace1(events, TR_FUNCTIONAL_TRACE, "event.fire(event=0x%p)", e);

    /*
     * xkThreadCreate will make sure the thread for this event acquires
     * the lock to the x-kernel before proceeding.
     */
    e->state = E_SCHEDULED;
    xkThreadCreate((ThreadFunc)event_stub, e, XK_EVENT );
}

/*
 * Enqueue "e" into a circular doubly linked list after element "after".
 */
static void
enqueue (Event e, Event after)
{
    e->prev = after;
    e->next = after->next;
    after->next = e;
    e->next->prev = e;
}

/*
 * Dequeue "e" from a circular doubly linked list.  It is guaranted
 * that the queue will remain non-empty.
 */

#define dequeue( e )                                                        \
do { e->prev->next = e->next; e->next->prev = e->prev; } while (0)

static u_long soft_clock_count = 0;

static void*
hb (void* us_interval_as_ptr)
{
    extern unsigned int sleep ( unsigned int seconds );
    extern int          xk_thread_count, p_thread_count;
    extern void         thread_map_dump( void );
    int                 local_count, hb_interval;
    xk_thread_t*        this_thread = threadSelf();

    this_thread->type = XK_HB;
    local_count = 0;
    hb_interval = 5; /* seconds */
    sleep(5);
    local_count += 5;

    xTrace3(events,TR_ALWAYS,"Debugging heart beat here: {xk=%d,pt=%d,c=%d}",
	    xk_thread_count, p_thread_count, soft_clock_count );
    while (1) {
	sleep(5); local_count += 5;
	xTrace3(events,TR_ALWAYS,"{xk=%d,pt=%d,c=%d}",
	        xk_thread_count,p_thread_count,soft_clock_count);
	if ( local_count > 30 ) {
	    local_count = 0;
	    thread_map_dump();
	}
    }
}

/*
 * When going from time "now" to "now+1", all events that should fire
 * in the interval (now-1*usec_per_tick,now*usec_per_tick] are fired.
 */
static void*
soft_clock (void* us_interval_as_ptr)
{
    unsigned us_interval = (unsigned)us_interval_as_ptr;
    u_long time, new_time;
    xk_thread_t* this_thread;
    Event e, q;

    this_thread = threadSelf();
    this_thread->type = XK_SOFT_CLOCK;

    xTrace1(events,TR_EVENTS,"soft_clock running as thread 0x%x",
            this_thread);

    soft_time = timeNowInTicks();
    usleep( us_interval );

    while (1) {
        soft_clock_count++;
	SET_THREAD_STATUS(this_thread,TW_LOCKING);
#ifdef XK_TRANSITION_TRACE
	this_thread->tinfo_cnt = -1;
#endif /* XK_TRANSITION_TRACE */
	pthread_mutex_lock( &timing_wheel_mutex );
	RESET_THREAD_STATUS(this_thread,TW_LOCKING);
	SET_THREAD_STATUS(this_thread,TW_LOCKED);

	xTrace1(events,TR_NEVER,"soft_clock(0x%x) now holds timing_wheel_mutex",
		this_thread);

	new_time = timeNowInTicks();
	xTrace2(events,TR_NEVER,"soft_clock(0x%x): %lu ticks",
		this_thread, new_time - soft_time );

	for (time = soft_time; time != new_time; ++time) {
	    q = &wheel[time % EVENT_WHEEL_SIZE];
	    for (e = q->next; e != q && e->deltat == 0; e = e->next) {
		dequeue(e);
		fire(e);
	    }
	    --e->deltat;
	}
	soft_time = new_time;

	pthread_mutex_unlock( &timing_wheel_mutex );
	RESET_THREAD_STATUS( this_thread, TW_LOCKED );

	xTrace1(events,TR_NEVER,
	        "soft_clock(0x%x) released timing_wheel_mutex,usleeping...",
		this_thread);

	usleep( us_interval );
    }
   
    /* It should never get here */
    Kabort("soft_clock thread should never exit, but it did!");
    return NULL; /* Just to make type checking happy */
}

/*
 * Insert event "newEvent" into "q".  The queue is maintained in a
 * sorted order such that the "deltat" value of events in the queue
 * specifies how many revolutions after the *preceeding* event the
 * event fires.
 */
static void
insert (Event new_event, Event head)
{
    Event curr;

    xTrace2(events, TR_FUNCTIONAL_TRACE,
	    "event.insert(new_event=0x%p,head=0x%p)", new_event, head);
    for (curr = head->next; curr != head; curr = curr->next) {
	if (curr->deltat < new_event->deltat) {
	    /* new_event goes after curr: */
	    new_event->deltat -= curr->deltat;
	} else {
	    /* new_event goes in front of curr: */
	    curr->deltat -= new_event->deltat;
	    enqueue(new_event, curr->prev);
	    return;
	}
    }
    /* new_event goes at the end */
    enqueue(new_event, head->prev);
}


/*
 * Fired events start here:
 */
static void
event_stub (void* arg)
{
    Event e = (Event) arg;
    xk_thread_t* this_thread = threadSelf();

    xTrace1(events, TR_FUNCTIONAL_TRACE, "event.start(e=0x%p)", e);
    assert(e->state == E_SCHEDULED);

    this_thread->type = XK_EVENT;

    if (e->flags & E_CANCELLED_F) {
	xTrace1(events, TR_EVENTS,
		"event.start: not starting cancelled event 0x%p", e);
	cache_event(e);
	return;
    }

    xTrace1(events, TR_EVENTS,
	    "event.start: invoking event-handler at 0x%p", e->func);
    e->state = E_RUNNING;

    SET_THREAD_STATUS( this_thread, XK_SCHEDULED );
    e->func(e, e->arg);
    RESET_THREAD_STATUS( this_thread, XK_SCHEDULED );

    e->state = E_FINISHED;

    if (e->flags & E_DETACHED_F) {
	cache_event(e);
    }
}


void
evInit (unsigned usec)
{
    int i;

    xTrace1(events, TR_FUNCTIONAL_TRACE, "eventInit(interval=%u)", usec);
    xTrace1(events, TR_DETAILED, "event_stub is 0x%x", event_stub );
    usec_per_tick = usec;
    pthread_mutex_init(&timing_wheel_mutex, pthread_mutexattr_default);

    for (i = 0; i < EVENT_WHEEL_SIZE; ++i) {
	wheel[i].next = &wheel[i];
	wheel[i].prev = &wheel[i];
	wheel[i].flags = 0;
    }

    xTrace0(events, TR_MAJOR_EVENTS, "eventInit(0x%x) calling xkThreadCreate");
    xkThreadCreate( (ThreadFunc)soft_clock, (void*)usec, XK_SOFT_CLOCK );

    xIfTrace(events,TR_MAJOR_EVENTS) {
	xTrace0(events, TR_MAJOR_EVENTS, "eventInit(0x%x) spawning hb");
	xkThreadCreate( (ThreadFunc)hb, NULL, XK_HB );
    }

    xTrace0(events, TR_FUNCTIONAL_TRACE, "eventInit returning" );
}

Event
evSchedule (EvFunc func, void* arg, unsigned usec)
{
    Event e;
    int nticks;
    xk_thread_t* this_thread = threadSelf();

    xTrace4(events, TR_EVENTS, "evSchedule[0x%x](handler=0x%p,arg=0x%p,usec=%u)",this_thread, func, arg, usec);

    SET_THREAD_STATUS( this_thread, TW_LOCKING );
    pthread_mutex_lock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKING );
    SET_THREAD_STATUS( this_thread, TW_LOCKED );

    xTrace1(events, TR_DETAILED, "evSchedule[0x%x] has wheel",this_thread);

    e = get_event();
    e->func = func;
    e->arg = arg;

    if (usec > 0) {
	/* rounded # of ticks to delay: */
	nticks = (2*usec + usec_per_tick) / (2*usec_per_tick);
	if (nticks == 0) {
	    ++nticks;		/* delay at least one tick */
	}
	/*
	 * Notice: soft_clock can be behind the real time due to other
	 *	   threads not relinquishing the processor frequently
	 *	   enough.  We take care of this by adding the
	 *	   difference between the real time (timeNowInTicks) and
	 *	   softClock's time to nticks:
	 */
	nticks += timeNowInTicks() - soft_time;

	/* compute how many clock-wheel revolutions this needs: */
	e->deltat = nticks / EVENT_WHEEL_SIZE;
	e->flags  = 0;
	e->state  = E_PENDING;
	insert(e, &wheel[(soft_time + nticks) % EVENT_WHEEL_SIZE]);
    } else {
	e->flags  = 0;
	e->deltat = 0;
	fire(e);
    }
    pthread_mutex_unlock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKED );

    xTrace1(events,TR_DETAILED,"evSchedule[0x%x] exits, wheel released", this_thread );

    return e;
}


void
evDetach (Event e)
{
    xk_thread_t* this_thread = threadSelf();

    xTrace2(events, TR_FUNCTIONAL_TRACE, "evDetach[0x%x](e=0x%p)", 
                   this_thread, e);

    SET_THREAD_STATUS( this_thread, TW_LOCKING );
    pthread_mutex_lock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKING );
    SET_THREAD_STATUS( this_thread, TW_LOCKED );

    xTrace1(events, TR_DETAILED, "evDetach[0x%x] has the wheel", 
                   this_thread);

    if (e->state == E_FINISHED) {
	xTrace1(events, TR_EVENTS, "evDetach: caching event 0x%p", e);
	cache_event(e);
    } else {
	xTrace1(events, TR_EVENTS, "evDetach: marks event 0x%p as detached", e);
	e->flags |= E_DETACHED_F;
    }

    pthread_mutex_unlock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKED );

    xTrace1(events, TR_DETAILED, "evDetach[0x%x] exits, wheel released",
            this_thread );
}


EvCancelReturn
evCancel (Event e)
{
    EvCancelReturn res = EVENT_CANCELLED;
    xk_thread_t*   this_thread = threadSelf();

    xTrace2(events, TR_FUNCTIONAL_TRACE, "eventCancel[0x%x](event=0x%p)", 
            this_thread, e);
    assert(e);


    SET_THREAD_STATUS( this_thread, TW_LOCKING );
    pthread_mutex_lock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKING );
    SET_THREAD_STATUS( this_thread, TW_LOCKED );

    xTrace1(events, TR_DETAILED, "eventCancel[0x%x] has the wheel", 
            this_thread);

#ifdef XK_DEBUG
  {
    XkReturn    xkr;

    xkr = mapResolve(localEventMap, &e, 0);
    if( xkr != XK_SUCCESS ) {
      Kabort("Attempt to cancel nonexistent event");
    }
  }
#endif

    e->flags |= E_DETACHED_F | E_CANCELLED_F;
    switch (e->state) {
      case E_SCHEDULED:
	/* 
	 * "start" will catch this event before it gets a chance to run:
	 */
	xTrace2(events, TR_EVENTS,
		"eventCancel: cancelled ev 0x%p in SCHEDULED state-flags %#x",
		e, e->flags);
	break;

      case E_BLOCKED:
      case E_RUNNING:
	res = EVENT_RUNNING;
	break;

      case E_FINISHED:
	res = EVENT_FINISHED;
	cache_event(e);
	break;

      case E_PENDING:
	e->next->deltat += e->deltat;
	dequeue(e);
	cache_event(e);
	break;

      default:
	Kabort("eventCancel: bad event state");
    }
    pthread_mutex_unlock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKED );

    xTrace1(events, TR_DETAILED, "eventCancel[0x%x] returning, wheel released", 
            this_thread);

    return res;
}


int
evIsCancelled(Event e)
{
    int result;
    xk_thread_t* this_thread = threadSelf();

    SET_THREAD_STATUS( this_thread, TW_LOCKING );
    pthread_mutex_lock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKING );
    SET_THREAD_STATUS( this_thread, TW_LOCKED );

    assert(e);
    result =  e->flags & E_CANCELLED_F;

    pthread_mutex_unlock( &timing_wheel_mutex );
    RESET_THREAD_STATUS( this_thread, TW_LOCKED );

    return result;
}

void
evCheckStack( char* str )
{
  /*
  fprintf(stderr,"evCheckStack(%s) not implemented for the Paragon\n",str);
  */
}