/*
    TMScheduler.c, Copyright  (c) by Christian Conrad & George,
    Swiss Federal Institute of Technology,
    Computer Engineering and Networks Laboratory.

    TOPSY -- A Teachable Operating System.
             Implementation of a tiny and simple
             micro kernel for teaching purposes.

    For further information, please visit http://www.tik.ee.ethz.ch/~topsy

    This software is provided under the terms of the GNU General Public Licence.

    A full copy of the GNU GPL is provided in the file COPYING found in the 
    development root of Topsy.
*/
/*
	
	File:                  $Source: /usr/drwho/vault/cvs/topsy/Topsy/Threads/TMScheduler.c,v $
 	Author(s):             Christian Conrad & George Fankhauser
 	Affiliation:           ETH Zuerich, TIK
 	Version:               $Revision: 1.35 $
 	Creation Date:         
 	Last Date of Change:   $Date: 1999/12/13 21:48:33 $      by: $Author: ruf $
	
	
	$Log: TMScheduler.c,v $
	Revision 1.35  1999/12/13 21:48:33  ruf
	GNU General Public Licence Update
	
	Revision 1.34  1999/10/23 19:07:14  jeker
	added Makefile.SimOS.mips and did some code cleanup
	
	Revision 1.33  1999/06/06 20:55:10  jeker
	putting everything together for Topsy 2.0

	Revision 1.32  1999/01/08 18:56:35  cjeker
	more code cleaning, moved tmResetClockInterrupt to the clock interrupt handlers

	Revision 1.31  1998/06/05 14:37:37  gfa
	clock update added
	
	Revision 1.30  1997/04/18 16:28:30  conrad
	*** empty log message ***

 * Revision 1.29  1997/04/17  10:55:45  conrad
 * *** empty log message ***
 *
 * Revision 1.28  1997/04/14  21:08:48  conrad
 * *** empty log message ***
 *
 * Revision 1.27  1997/04/14  12:32:12  conrad
 * clock int reset performed in clock handler (THE solution !)
 *
 * Revision 1.26  1997/04/09  16:22:36  conrad
 * *** empty log message ***
 *
 * Revision 1.25  1997/04/06  18:56:20  gfa
 * source cleanup
 *
 * Revision 1.24  1997/04/01  16:23:37  conrad
 * *** empty log message ***
 *
 * Revision 1.23  1997/03/31  20:30:42  gfa
 * minor redesign, uses a symmetric structure (ready/blocked queues) and
 * leaves the running thread in the ready queue (saves some headache).
 * uses new efficient and memory free list ops.
 *
 * Revision 1.22  1997/03/28  11:41:35  conrad
 * using of generic lists with hint field
 *
 * Revision 1.21  1997/03/26  10:50:32  gfa
 * cosmetics
 *
 * Revision 1.20  1997/03/24  10:57:20  conrad
 * fixed bug in remove(), lastPtr was forgotten, bouh ....
 *
 * Revision 1.19  1997/03/21  20:01:53  conrad
 * new idle thread
 *
 * Revision 1.18  1997/03/21  19:14:06  conrad
 * cosmetics
 *
 * Revision 1.17  1997/03/21  13:02:49  conrad
 * adding of an idleCProcedure for testing
 *
 * Revision 1.16  1997/03/19  21:38:23  conrad
 * cosmetics
 *
 * Revision 1.15  1997/03/18  16:28:49  conrad
 * adding of some debug messages
 *
 * Revision 1.14  1997/03/16  22:10:43  gfa
 * added include IPC
 *
 * Revision 1.13  1997/03/13  14:25:02  conrad
 * Restoring status of pending buffer during each scheduling decision
 *
 * Revision 1.12  1997/03/12  17:53:48  conrad
 * Debugging version
 *
 * Revision 1.11  1997/03/11  20:07:06  conrad
 * First version to be debugged with Simulator
 *
 * Revision 1.10  1997/03/07  13:00:38  conrad
 * Adding Error module
 *
 * Revision 1.9  1997/03/04  16:56:01  conrad
 * minor changes
 *
 * Revision 1.8  1997/03/03  11:26:19  conrad
 * Correction in scheduler (removal of ready list !!!)
 *
 * Revision 1.7  1997/02/26  17:34:02  conrad
 * cleaning
 *
 * Revision 1.6  1997/02/25  16:58:14  conrad
 * Cleaning ready and blocked functions
 *
 * Revision 1.5  1997/02/24  21:35:02  conrad
 * incomplete version
 *
 * Revision 1.4  1997/02/19  17:46:24  conrad
 * *** empty log message ***
 *
 * Revision 1.3  1997/02/18  18:28:04  conrad
 * Introduction of tm-include.h
 *
 * Revision 1.2  1997/02/13  15:44:51  conrad
 * First compilation/linking of complete environment (all modules)
 *
 * Revision 1.1  1997/02/12  15:35:07  conrad
 * Initial revision
 *
*/

#include "TMScheduler.h"

#include "TMIPC.h"	/* ipcCheckPendingFlag */
#include "TMThread.h"	/* threadLock          */
#include "TMHal.h"
#include "TMClock.h"
#include "TMTime.h"
#include "Lock.h"

/* globals (need to be accessed in exception handler to get current context) */
Scheduler scheduler;

/* local variables */
static LockDesc sLockDesc;
static Lock schedLock = &sLockDesc;


/* Clock interrupt handler
 * this function is just for readability. we would have called schedule
 * directly.
 * it's also the function where we would place clock updates.
 */
void tmClockHandler()
{
    /* Stop the clock. If not done the interrupt is generated once again and again ... */
    tmResetClockInterrupt(CLOCK0);
    tmTimeUpdate();	/* update time by one tick */
    schedule();		/* check for other ready threads */
}


/* idle thread's main function, quite boring but nevertheless important 
 */
void tmIdleMain()
{
    while (TRUE) { powerSaver(); }
}


/*
 * Initialisation of the scheduler with queues and lock.
 * this function is only used at startup to initialize the scheduler with
 * a thread (which saves us the continuous testing on running == NULL) in
 * schedule().
 */
void schedulerInit(Thread* threadPtr)
{
    int i;
    
    lockInit(schedLock);

    scheduler.running = threadPtr;
    for (i = 0; i < NBPRIORITYLEVELS; i++) {
	scheduler.prioList[i].ready = listNew();
	scheduler.prioList[i].blocked = listNew();
    }
}


/* return the current thread 
 */
Thread* schedulerRunning()
{
    return scheduler.running;
}


/*
 * A new thread structure is registered in the scheduler at its corresponding
 * priority level and at the head of the blocked queue.
 */
void schedulerInsert( Thread* threadPtr, ThreadPriority priority)
{
    threadPtr->schedInfo.status = BLOCKED;
    threadPtr->schedInfo.priority = priority;

    lock(schedLock); {
	listAddInFront( scheduler.prioList[priority].blocked, threadPtr,
		    &(threadPtr->schedInfo.hint));
    }
    unlock(schedLock);
}


/*
 * The thread structure passed as argument is removed from any queue
 */
void schedulerRemove( Thread* threadPtr)
{
    ThreadPriority priority = threadPtr->schedInfo.priority;

    lock(schedLock); {    
	if (threadPtr->schedInfo.status == BLOCKED) {
	    listRemove( scheduler.prioList[priority].blocked, threadPtr,
			threadPtr->schedInfo.hint);
	} else if (threadPtr->schedInfo.status == READY) {
	    listRemove( scheduler.prioList[priority].ready, threadPtr,
			threadPtr->schedInfo.hint);
	} else {
	    PANIC("Not possible to remove a RUNNING thread from scheduler");
	}
    }
    unlock(schedLock);
}


/*
 * The thread passed as argument is appended at the end of the ready
 * list of same priority level. It is assumed the thread is already registered
 * in the scheduler queues.
 * ! This function may run in an exception handler.
 */
Error schedulerSetReady( Thread* threadPtr)
{
    ThreadPriority priority = threadPtr->schedInfo.priority;

    if ((threadPtr->schedInfo.status == READY) ||
	(threadPtr->schedInfo.status == RUNNING)) return TM_OK;

    lock(schedLock); {
	/* swap thread from blocked-list to ready-list */
	listSwap(scheduler.prioList[priority].blocked, 
		 scheduler.prioList[priority].ready,
		 threadPtr, threadPtr->schedInfo.hint);
	threadPtr->schedInfo.status = READY;
    }
    unlock(schedLock); 
    return TM_OK;
}


/*
 * The thread passed as argument is added at the beginning of the blocked
 * list of the same priority level. It is assumed the thread is already  
 * registered in the scheduler queues.
 * ! This function may run in an exception handler.
 */
Error schedulerSetBlocked( Thread* threadPtr)
{
    ThreadPriority priority = threadPtr->schedInfo.priority;

    if (threadPtr->schedInfo.status == BLOCKED) return TM_OK;

    lock(schedLock); {
	/* swap thread from ready-list to blocked-list */
	listSwap(scheduler.prioList[priority].ready, 
		 scheduler.prioList[priority].blocked, 
		 threadPtr, threadPtr->schedInfo.hint);

	threadPtr->schedInfo.status = BLOCKED;
	/* remark: at this point, scheduler.running may point to a blocked
	 * thread. so after setBlocked we should call schedule (see msgDispatcher).
	 */
    }
    unlock(schedLock);
    return TM_OK;
}


/*
 * The next thread with the highest priority is set to running.
 * ! This function may run in an interrupt handler.
 */
void schedule()
{
    ThreadPriority priority;
    Thread* newRunning = NULL;
    Thread* oldRunning = scheduler.running;

    /* here we may be in the clock interrupt and possible are in race 
     * condition with the thread manager (e.g. start/exit). this can be 
     * solved by testing schedLock. if it's locked we just give up because
     * we must give the thread manager a chance to release this lock.
     */
    if (!lockTry(schedLock)) return;
    else unlock(schedLock);
    
    /* next we must avoid picking a thread that makes a syscall while the
     * thread manager is in the process of updating the global list/hashlist
     * of threads.
     */
    if (!lockTry(threadLock)) return;
    else unlock(threadLock);
    
    /* Current running thread is put at the end of its ready queue,
     * unless it was previously put to sleep (by doing a msgRecv)
     */
    if (oldRunning->schedInfo.status != BLOCKED) {
	listMoveToEnd(scheduler.prioList[oldRunning->schedInfo.priority].ready,
		    oldRunning, oldRunning->schedInfo.hint);
	oldRunning->schedInfo.status = READY;
    }
    
    /* Loop over all ready queues from higher to lower priority to find
     * next thread that is allowed to run
     */
    for (priority = KERNEL_PRIORITY; priority < NBPRIORITYLEVELS; priority++) {
	listGetFirst(scheduler.prioList[priority].ready, (void**)&newRunning);
	if (newRunning != NULL) {
	    /* yup, we found a non-empty ready queue and we always pick
	     * the first one. we already put the old running thread to its
	     * queue end which results in a fine priority round-robin
	     * scheduling.
	     */
	    newRunning->schedInfo.status = RUNNING;
	    ipcResetPendingFlag(newRunning);
	    break;
	}
	/* the idle thread(s) guarantee that we always find a ready thread */
    }
    scheduler.running = newRunning;
}