sched.c

pebble

/* 
 * Copyright 1999, 2000, 2001, 2002 Lucent Technologies Inc.
 * All Rights Reserved.
 * Information Sciences Research Center, Bell Labs.
 *
 * LUCENT TECHNOLOGIES DOES NOT CLAIM MERCHANTABILITY OF THIS SOFTWARE 
 * OR THE SUITABILITY OF THIS SOFTWARE FOR ANY PARTICULAR PURPOSE. The
 * software is provided "as is" without expressed or implied warranty 
 * of any kind.
 *
 * These notices must be retained in any copies of any part of this
 * software.
 *
 */

/*
 * User-level scheduler.
 * This code is always executed with interrupts disabled.
 * This version assumes a uniprocessor.
 *
 * *** important ***
 * All portal calls to the scheduler MUST save at least partial
 * state (but never minimal state), since the calling thread may
 * be suspended inside the scheduler.
 *
 * Note:
 * The Thread data structure is allocated in kernel space.
 * So we cannot access it directly. We only keep those pointers
 * and never de-referece them.
 */

#include <string.h>
#include <unistd.h>		/* for write */
#include "diag.h"
#include "pebble.h"
#include "mem.h"		/* for NASID */
#include "log.h"
#include "nucleus.h"
#include "time.h"
#include "inside.h"
#include <assert.h>

typedef	struct elem_t	{
	Thread	*thread;
	int	val;		/* return value from system call */
	Time	wakeup;		/* wakeup time if waiting on timer queue */
	int	asid;		/* thread's asid */
	int	pri;		/* wakeup priority (not always asid2pri[asid])*/
	/* semaphore list */
	struct elem_t *sem_next;
	struct elem_t *sem_last;
	void *sem_q;		/* waiting on a semaphore */
	/* timer list */
	struct elem_t *time_next;
	struct elem_t *time_last;
} Elem;

typedef	struct	{
	Elem	*head;
	Elem	*tail;
} Queue;

typedef	struct semaphore_t {
	int	count;
	struct semaphore_t *next;
	int	asid;		/* ASID that created this semaphore */
	int	portal_no;	/* portal number in requestor's portal table */
	Queue	q;		/* FIFO queue of waiting threads */
} Semaphore;

typedef	struct	{
	Semaphore write_lock;
	Semaphore full;
	Semaphore read_lock;
	Semaphore empty;
	char	*buf;		/* FIFO (pipe) buffer */
	int	head;		/* offset of head pointer into buffer */
	int	tail;		/* offset of tail pointer into buffer */
} Pipe;

typedef	struct	{
	Queue	free_q;		/* values list */
	Queue	wait_q;		/* waiting threads */
} ValQueue;

#define	NELEM		256
#define	PIPE_OFFSET	128
				/* is too short for actual sleep and wakeup */

static	Queue readyq[NPRIORITY];
static	Elem e[NELEM];
static	Elem *free_list;
static	Elem *wakeup_q = NULL;	/* threads timer queue */
static	int asid2pri[NASID];
static	ValQueue val_q[NASID];	/* values queue per domain */

static	Time fuzz;		/* cannot set the next wakup closer than this */
				/* to current time to avoid missing the event */
				/* in high-resolution ticks */
static	Time next_wakeup;	/* next wakeup time in high-resolution ticks */
static	Semaphore *sem_list = NULL;	/* list of all semaphores */


const char PORTAL_CREATE[] = "too many open portals";
const char SEM_OVERFLOW[] = "too many open semaphores";
const char MEM_ALLOC[] = "memory allocation failed";
const char BUF_LEN[] = "invalid buffer length";
const char HRSLEEP_AMOUNT[] = "invalid sleep time";
const char PRIORITY_ERROR[] = "invalid priority or asid";
const char SEM_MAGIC_ERROR[] = "no semaphore was allocated for this domain";
const char NO_CALLER[] = "no domain called current domain";

Time
min_time(Time x, Time y)
{
	return (x < y) ? x : y;
}

Time
max_time(Time x, Time y)
{
	return (x > y) ? x : y;
}

void
elem_init(void)
{
	int i;

	free_list = NULL;
	for (i = 0; i < NELEM; i++) {
		e[i].sem_next = free_list;
		free_list = &e[i];
	}
}

static Elem *
new_elem(void)
{
	Elem *ep;

	if ((ep = free_list) == NULL)
		panic("sched: no free elem");
	free_list = ep->sem_next;

	return ep;
}


static void
free_elem(Elem *ep)
{
	ep->sem_next = free_list;
	free_list = ep;
}


/* append to end of queue */
Elem *
enqueue(Queue *q, Thread *t, int asid, int pri, int ret_val)
{
	Elem *ep;

	ep = new_elem();
	ep->thread = t;
	ep->asid = asid;
	ep->pri = pri;
	ep->val = ret_val;
	
	if (q->tail == NULL)
		q->head = ep;
	else
		q->tail->sem_next = ep;
	ep->sem_next = NULL;
	ep->sem_last = q->tail;
	q->tail = ep;
	ep->sem_q = q;

	/* do not insert in timer queue */
	ep->time_next = ep->time_last = NULL;
	ep->wakeup = 0;

	return ep;
}

/* insert at head of queue (this is never a semaphore) */
Elem *
enqueue_head(Queue *q, Thread *t, int asid, int pri, int ret_val)
{
	Elem *ep;

	ep = new_elem();
	ep->thread = t;
	ep->asid = asid;
	ep->pri = pri;
	ep->val = ret_val;
	
	ep->sem_next = q->head;
	ep->sem_last = NULL;
	if (q->head == NULL)
		q->tail = ep;
	else
		q->head->sem_last = ep;
	q->head = ep;
	ep->sem_q = NULL;

	/* do not insert in timer queue */
	ep->time_next = ep->time_last = NULL;
	ep->wakeup = 0;

	return ep;
}

/* dequeue element from the head of the queue */
Thread *
dequeue(Queue *q, int *caller_asid, int *pri, int *ret_val)
{
	Elem *ep;
	Thread *t;

	if ((ep = q->head) == NULL)
		return NULL;

	assert(ep->sem_last == NULL);
	q->head = ep->sem_next;
	if (q->head == NULL)
		q->tail = NULL;
	else
		q->head->sem_last = NULL;

	/* remove element also from timer queue */
	if (ep->wakeup != 0) {
		if (ep->time_last != NULL)
			ep->time_last->time_next = ep->time_next;
		else
			wakeup_q = ep->time_next;

		if (ep->time_next != NULL)
			ep->time_next->time_last = ep->time_last;
	}

	t = ep->thread;
	*ret_val = ep->val;
	*caller_asid = ep->asid;
	*pri = ep->pri;
	free_elem(ep);

	return t;
}

/* insert into sorted wakeup queue */
void
enqueue_timer(Elem *ep, Time wakeup)
{
	Elem *p, *last_p;
	register Time next_t;

	ep->wakeup = wakeup;

	last_p = NULL;
	for (p = wakeup_q; p != NULL && ep->wakeup >= p->wakeup;
	     p = p->time_next)
		last_p = p;

	if (last_p == NULL)
		wakeup_q = ep;
	else
		last_p->time_next = ep;
	ep->time_next = p;
	ep->time_last = last_p;
	if (p != NULL)
		p->time_last = ep;

	/* reset timer */
	if (next_wakeup != wakeup_q->wakeup) {
		/* ensure that we reset the timer to a future time, */
		/* after the actual time that set_timer() is called */
		next_t = max_time(wakeup_q->wakeup, hrtime() + fuzz);
		if (next_t < next_wakeup) {
	 		next_wakeup = next_t;
			set_timer(next_t);
		}
	}
}

int
sys_dump_sched(Thread *t)
{
	int n = 0;
	Elem *p;
	Semaphore *s;
	int i;

	fdprintf(2, "ready queue:\n");
	for (i = 0; i < NPRIORITY; i++)
		for (p = readyq[i].head; p != NULL; p = p->sem_next) {
			n++;
			fdprintf(2, "ready thread %p asid %d priority %d\n",
				p->thread, p->asid, i);
		}
	if (n == 0)
		fdprintf(2, "ready queue is empty\n");

	fdprintf(2, "semaphores:\n");
	n = 0;
	for (s = sem_list ; s != NULL; s = s->next) {
		if (s->q.head != NULL)
			fdprintf(2,
		"semaphore %p created by asid %d portal %d count=%d\n",
			s, s->asid, s->portal_no, s->count);
		for (p = s->q.head; p != NULL; p = p->sem_next) {
			n++;
			fdprintf(2, "thread %p asid %d waiting on sem %p\n",
				p->thread, p->asid, s);
		}
	}
	if (n == 0)
		fdprintf(2, "no thread waiting on a semaphore\n");

	fdprintf(2, "timer queue:\n");
	n = 0;
	for (p = wakeup_q; p != NULL; p = p->time_next) {
		n++;
		fdprintf(2, "thread %p waiting until %u %u\n",
			p->thread, (uint)(p->wakeup>>32), (uint)p->wakeup);
	}
	if (n == 0)
		fdprintf(2, "timer queue is empty\n");

	return 0;
}

int
sys_ready(Thread *caller, Thread *p, int asid, int ret_val)
{
	int pri;

	pri = asid2pri[asid];
	enqueue(&readyq[pri], p, asid, pri, ret_val);

	return(0);
}


/*
 * Calls the scheduler and never returns.
 * 
 * This routine is called whenever the current thread has to be de-scheduled
 * either voluntarily (waiting on a semaphore or timer event) or involuntarily
 * (by an interrupt).
 * In the latter case, we return the thread to the *head* of the ready queue.
 *
 * This routine is called from sem_post with the caller's ASID.
 * If sem_post was called by the thread, it may be de-scheduled on the spot.
 * If sem_post was called by the interrupt dispatcher, sys_sched() will
 * never de-schedule the intrrupt dispatcher, since it has the highest
 * priority.
 *
 * The last line of the interrupt dispatcher calls sys_sched() with the
 * identity of the poor thread that was interrupted.
 * This call is done via a null portal, which does not save state on the
 * call stack.
 * In this case, sys_sched() may decide to schedule a thread with a higher
 * priority. So the interrupted thread is inserted at the head of the
 * ready queue, since it should not suffer unduly from the interrupt.
 *
 * Note that sys_sched() may be also called by the last sem_post in the
 * scheduler or by the timer_handler, also from the interrupt dispatcher.
 * In both cases, the last call (corresponding to the portal traversal
 * from the interrupt dispatcher to the scheduler) is removed from the
 * call stack prior to calling this routine.
 *
 * >> Future enhancement <<
 * If we will have time-slicing, we will append the thread at the tail
 * for timer interrupts, and to the head of the queue in all other cases.
 */
void
sys_sched(Thread *t, int caller_asid, int caller_val)
{
	Thread *p = NULL;
	int val;
	int caller_pri = -1;
	int i;
	int asid, pri;
	Time now;

	if (SCHED_LOG) {
		put_log(SCHED_LOG_SCHED, (int)t);
		put_log(SCHED_LOG_ASID, caller_asid);
	}

	if (t != NULL)
		caller_pri = asid2pri[caller_asid];

	for (i = PRI_MAX; i > caller_pri; i--)
		if ((p = dequeue(&readyq[i], &asid, &pri, &val)) != NULL)
			break;

	if (p != NULL) {
		/* if we have to be de-scheduled, return to head of queue */
		if (t != NULL) {
			enqueue_head(&readyq[caller_pri], t, caller_asid,
				caller_pri, caller_val);
			if (SCHED_LOG) {
				put_log(SCHED_LOG_READY, (int)t);
				put_log(SCHED_LOG_RUN_PRIORITY, caller_pri);
			}
		}
		if (SCHED_LOG) {
			put_log(SCHED_LOG_RUN, (int)p);
			put_log(SCHED_LOG_RUN_PRIORITY, i);
		}
		run(p, val);
	}

	/* there is no thread of a higher priority than the caller */
	if (t != NULL) {
		if (SCHED_LOG) {
			put_log(SCHED_LOG_RUN, (int)t);
			put_log(SCHED_LOG_RUN_PRIORITY, caller_pri);
		}
		run(t, caller_val);
	}

	if (SCHED_DIAG) {
		now = hrtime();
		fdprintf(2, "*** scheduler has nothing to run *** time=%u %u\n",
			(uint)(now>>32), (uint)now);
		sys_dump_sched(t);
		dump_lock();
	}
	panic("scheduler: nothing to run: caller asid=%d priority=%d thread=%p",
		caller_asid, caller_pri, t);
}

void
sys_yield(Thread *t, int asid)
{
	int pri;
//	Time now;

	if (SCHED_DIAG) {
		fdprintf(2, "yield called from thread %p, asid %d\n", t, asid);
	}

	/* the following condition will be eliminated by the compiler */
	/* if INTR_INSIDE is zero. */
	if (INTR_INSIDE && is_intr_stack())
		panic("interrupt handler thread %p called yield", t);

	if (SCHED_LOG)
		put_log(SCHED_LOG_YIELD, (int)t);

#if 0
	if (SCHED_DIAG) {
		now = hrtime();
		fdprintf(2, "*** dumping scheduler queue in yield.. *** time=%u %u\n",
			(uint)(now>>32), (uint)now);
		sys_dump_sched(t);
		dump_lock();
	}
#endif

	pri = asid2pri[asid];
	if (SCHED_DIAG) {
		fdprintf(2, "yield enqueing thread %p, asid %d, pri %d\n", t, asid, pri);
	}
	enqueue(&readyq[pri], t, asid, pri, 0);
	/* if the is a ready thread of higher or equal priority, run it */
	sys_sched(0, 0, 0);
}


int
sys_sem_wait(int asid, int caller_pri, Time wakeup, Semaphore *s, Thread *t)
{
	Elem *ep;
	int pri, caller_asid;

	/* the following condition will be eliminated by the compiler */
	/* if INTR_INSIDE is zero. */
	if (INTR_INSIDE && is_intr_stack())
		panic("interrupt handler thread %p blocked on sem_wait on %p",
			t, s);

	if (SCHED_LOG)
		put_log(SCHED_LOG_SEM_WAIT, (int)s);

	if (s->count > 0) {
		s->count--;
		if (SCHED_LOG)
			put_log((int)s,  s->count);
		return (0);
	}

	/* timeout in the past */
	if (wakeup != 0 && wakeup < hrtime())
		error(HRSLEEP_AMOUNT);
	
	if (caller_pri) {
		caller_asid = get_caller_asid(2);
		if (caller_asid < 0)
			error(NO_CALLER);
		pri = asid2pri[caller_asid];
	} else
		pri = asid2pri[asid];

	pri = asid2pri[asid];
	assert(t != NULL);
	ep = enqueue(&s->q, t, asid, pri, 0);
	if (wakeup != 0) {
		enqueue_timer(ep, wakeup);
	}
	sys_sched(0, 0, 0);

	/* not reached */
	return (0);
}


/*
 *	Post semaphore "s".
 *
 *	If this is the last call from the interrupt dispatcher,
 *	then this routine was called by a null portal, so we
 *	return to the thread that was running at the time of the
 *	interrupt. In this case, the interrupt dispatcher sets the
 *	2nd argument to contain the interrupted thread's ASID.
 * 	actually, it sets it to -ASID to distinguish between a regular
 *	sem_post() and the last sem_post() in the interrupt dispatcher.
 */
void
sys_sem_post(Thread *t, int caller_asid, Semaphore *s)
{
	Thread *p;
	int val;
	int asid;
	int pri;

	s->count++;
	if (SCHED_LOG) {
		put_log(SCHED_LOG_SEM_POST, (int)s);
		put_log((int)s, s->count);
	}

	/* Note that waiting threads are stored in a FIFO queue */
	if (s->count > 0 && (p = dequeue(&s->q, &asid, &pri, &val)) != NULL) {
		s->count--;
		if (SCHED_LOG) {
			put_log(SCHED_LOG_READY, (int)p);
			put_log(SCHED_LOG_RUN_PRIORITY, pri);