kthread.c.bak

The main purpose of this project is to add a new scheduling algorithm to GeekOS and to implement a s

/*
 * Kernel threads
 * Copyright (c) 2001,2003 David H. Hovemeyer <[e-mail]>
 * $Revision: 1.49 $
 * 
 * This is free software.  You are permitted to use,
 * redistribute, and modify it as specified in the file "COPYING".
 */

#include <geekos/kassert.h>
#include <geekos/defs.h>
#include <geekos/screen.h>
#include <geekos/int.h>
#include <geekos/mem.h>
#include <geekos/symbol.h>
#include <geekos/string.h>
#include <geekos/kthread.h>
#include <geekos/malloc.h>


/* ----------------------------------------------------------------------
 * Private data
 * ---------------------------------------------------------------------- */

/*
 * List of all threads in the system.
 */
static struct All_Thread_List s_allThreadList;

/*
 * Run queues.  0 is the highest priority queue.
 */
static struct Thread_Queue s_runQueue[MAX_QUEUE_LEVEL];

/*
 * Current thread.
 */
struct Kernel_Thread* g_currentThread;

/*
 * Boolean flag indicating that we need to choose a new runnable thread.
 * It is checked by the interrupt return code (Handle_Interrupt,
 * in lowlevel.asm) before returning from an interrupt.
 */
int g_needReschedule;

/*
 * Boolean flag indicating that preemption is disabled.
 * When set, external interrupts (such as the timer tick)
 * will not cause a new thread to be selected.
 */
volatile int g_preemptionDisabled;

/*
 * Queue of finished threads needing disposal,
 * and a wait queue used for communication between exited threads
 * and the reaper thread.
 */
static struct Thread_Queue s_graveyardQueue;
static struct Thread_Queue s_reaperWaitQueue;

/*
 * Counter for keys that access thread-local data, and an array
 * of destructors for freeing that data when the thread dies.  This is
 * based on POSIX threads' thread-specific data functionality.
 */
static unsigned int s_tlocalKeyCounter = 0;
static tlocal_destructor_t s_tlocalDestructors[MAX_TLOCAL_KEYS];

/* ----------------------------------------------------------------------
 * Private functions
 * ---------------------------------------------------------------------- */

/*
 * Initialize a new Kernel_Thread.
 */
static void Init_Thread(struct Kernel_Thread* kthread, void* stackPage,
	int priority, bool detached)
{
    static int nextFreePid = 1;

    struct Kernel_Thread* owner = detached ? (struct Kernel_Thread*)0 : g_currentThread;

    memset(kthread, '\0', sizeof(*kthread));
    kthread->stackPage = stackPage;
    kthread->esp = ((ulong_t) kthread->stackPage) + PAGE_SIZE;
    kthread->numTicks = 0;
    kthread->priority = priority;
    kthread->userContext = 0;
    kthread->owner = owner;

    /*
     * The thread has an implicit self-reference.
     * If the thread is not detached, then its owner
     * also has a reference to it.
     */
    kthread->refCount = detached ? 1 : 2;

    kthread->alive = true;
    Clear_Thread_Queue(&kthread->joinQueue);
    
    kthread->pid = nextFreePid++;

    kthread->currentReadyQueue = 0;
    kthread->blocked = false;
    Enqueue_Thread(&s_runQueue[0], kthread);
}

/*
 * Create a new raw thread object.
 * Returns a null pointer if there isn't enough memory.
 */
static struct Kernel_Thread* Create_Thread(int priority, bool detached)
{
    struct Kernel_Thread* kthread;
    void* stackPage = 0;

    /*
     * For now, just allocate one page each for the thread context
     * object and the thread's stack.
     */
    kthread = Alloc_Page();
    if (kthread != 0)
        stackPage = Alloc_Page();    

    /* Make sure that the memory allocations succeeded. */
    if (kthread == 0)
	return 0;
    if (stackPage == 0) {
	Free_Page(kthread);
	return 0;
    }

    /*Print("New thread @ %x, stack @ %x\n", kthread, stackPage); */

    /*
     * Initialize the stack pointer of the new thread
     * and accounting info
     */
    Init_Thread(kthread, stackPage, priority, detached);

    /* Add to the list of all threads in the system. */
    Add_To_Back_Of_All_Thread_List(&s_allThreadList, kthread);

    return kthread;
}

/*
 * Push a dword value on the stack of given thread.
 * We use this to set up some context for the thread before
 * we make it runnable.
 */
static __inline__ void Push(struct Kernel_Thread* kthread, ulong_t value)
{
    kthread->esp -= 4;
    *((ulong_t *) kthread->esp) = value;
}

/*
 * Destroy given thread.
 * This function should perform all cleanup needed to
 * reclaim the resources used by a thread.
 * Called with interrupts enabled.
 */
static void Destroy_Thread(struct Kernel_Thread* kthread)
{

    /* Dispose of the thread's memory. */
    Disable_Interrupts();
    Free_Page(kthread->stackPage);
    Free_Page(kthread);

    /* Remove from list of all threads */
    Remove_From_All_Thread_List(&s_allThreadList, kthread);

    Enable_Interrupts();

}

/*
 * Hand given thread to the reaper for destruction.
 * Must be called with interrupts disabled!
 */
static void Reap_Thread(struct Kernel_Thread* kthread)
{
    KASSERT(!Interrupts_Enabled());
    Enqueue_Thread(&s_graveyardQueue, kthread);
    Wake_Up(&s_reaperWaitQueue);
}

/*
 * Called when a reference to the thread is broken.
 */
static void Detach_Thread(struct Kernel_Thread* kthread)
{
    KASSERT(!Interrupts_Enabled());
    KASSERT(kthread->refCount > 0);

    --kthread->refCount;
    if (kthread->refCount == 0) {
	Reap_Thread(kthread);
    }
}

/*
 * This function performs any needed initialization before
 * a thread start function is executed.  Currently we just use
 * it to enable interrupts (since Schedule() always activates
 * a thread with interrupts disabled).
 */
static void Launch_Thread(void)
{
    Enable_Interrupts();
}

/*
 * Push initial values for general purpose registers.
 */
static void Push_General_Registers(struct Kernel_Thread* kthread)
{
    /*
     * Push initial values for saved general-purpose registers.
     * (The actual values are not important.)
     */
    Push(kthread, 0);  /* eax */
    Push(kthread, 0);  /* ebx */
    Push(kthread, 0);  /* edx */
    Push(kthread, 0);  /* edx */
    Push(kthread, 0);  /* esi */
    Push(kthread, 0);  /* edi */
    Push(kthread, 0);  /* ebp */
}

/*
 * Shutdown a kernel thread.
 * This is called if a kernel thread exits by falling off
 * the end of its start function.
 */
static void Shutdown_Thread(void)
{
    Exit(0);
}

/*
 * Set up the initial context for a kernel-mode-only thread.
 */
static void Setup_Kernel_Thread(
    struct Kernel_Thread* kthread,
    Thread_Start_Func startFunc,
    ulong_t arg)
{
    /*
     * Push the argument to the thread start function, and the
     * return address (the Shutdown_Thread function, so the thread will
     * go away cleanly when the start function returns).
     */
    Push(kthread, arg);
    Push(kthread, (ulong_t) &Shutdown_Thread);

    /* Push the address of the start function. */
    Push(kthread, (ulong_t) startFunc);

    /*
     * To make the thread schedulable, we need to make it look
     * like it was suspended by an interrupt.  This means pushing
     * an "eflags, cs, eip" sequence onto the stack,
     * as well as int num, error code, saved registers, etc.
     */

    /*
     * The EFLAGS register will have all bits clear.
     * The important constraint is that we want to have the IF
     * bit clear, so that interrupts are disabled when the
     * thread starts.
     */
    Push(kthread, 0UL);  /* EFLAGS */

    /*
     * As the "return address" specifying where the new thread will
     * start executing, use the Launch_Thread() function.
     */
    Push(kthread, KERNEL_CS);
    Push(kthread, (ulong_t) &Launch_Thread);

    /* Push fake error code and interrupt number. */
    Push(kthread, 0);
    Push(kthread, 0);

    /* Push initial values for general-purpose registers. */
    Push_General_Registers(kthread);

    /*
     * Push values for saved segment registers.
     * Only the ds and es registers will contain valid selectors.
     * The fs and gs registers are not used by any instruction
     * generated by gcc.
     */
    Push(kthread, KERNEL_DS);  /* ds */
    Push(kthread, KERNEL_DS);  /* es */
    Push(kthread, 0);  /* fs */
    Push(kthread, 0);  /* gs */
}

/*
 * Set up the a user mode thread.
 */
/*static*/ void Setup_User_Thread(
    struct Kernel_Thread* kthread, struct User_Context* userContext)
{
    /*
     * Hints:
     * - Call Attach_User_Context() to attach the user context
     *   to the Kernel_Thread
     * - Set up initial thread stack to make it appear that
     *   the thread was interrupted while in user mode
     *   just before the entry point instruction was executed
     * - The esi register should contain the address of
     *   the argument block
     */
//    TODO("Create a new thread to execute in user mode");
    unsigned csSelector = userContext->csSelector;
    unsigned dsSelector = userContext->dsSelector;

    Attach_User_Context(kthread, userContext);

    /*
     * Make the thread's stack look like it was interrupted
     * while in user mode.
     */

    /* Stack segment and stack pointer within user mode. */
    Push(kthread, dsSelector);  /* user ss */
    Push(kthread, userContext->stackPointerAddr);  /* user esp */

    /* eflags, cs, eip */
    Push(kthread, EFLAGS_IF);
    Push(kthread, csSelector);
    Push(kthread, userContext->entryAddr);

    /* Push fake error code and interrupt number. */
    Push(kthread, 0);
    Push(kthread, 0);

    /*
     * Push initial values for general-purpose registers.
     * The only important register is esi, which we use to
     * pass the address of the argument block.
     */
    Push(kthread, 0);  /* eax */
    Push(kthread, 0);  /* ebx */
    Push(kthread, 0);  /* edx */
    Push(kthread, 0);  /* edx */
    Push(kthread, userContext->argBlockAddr);  /* esi */
    Push(kthread, 0);  /* edi */
    Push(kthread, 0);  /* ebp */

    /* Push initial values for the data segment registers. */
    Push(kthread, dsSelector);  /* ds */
    Push(kthread, dsSelector);  /* es */
    Push(kthread, dsSelector);  /* fs */
    Push(kthread, dsSelector);  /* gs */
}


/*
 * This is the body of the idle thread.  Its job is to preserve
 * the invariant that a runnable thread always exists,
 * i.e., the run queue is never empty.
 */
static void Idle(ulong_t arg)
{
    while (true)
	Yield();
}

/*
 * The reaper thread.  Its job is to de-allocate memory
 * used by threads which have finished.
 */
static void Reaper(ulong_t arg)
{
    struct Kernel_Thread *kthread;

    Disable_Interrupts();

    while (true) {
	/* See if there are any threads needing disposal. */
	if ((kthread = s_graveyardQueue.head) == 0) {
	    /* Graveyard is empty, so wait for a thread to die. */
	    Wait(&s_reaperWaitQueue);
	}
	else {
	    /* Make the graveyard queue empty. */
	    Clear_Thread_Queue(&s_graveyardQueue);

	    /*
	     * Now we can re-enable interrupts, since we
	     * have removed all the threads needing disposal.
	     */
	    Enable_Interrupts();
	    Yield();   /* allow other threads to run? */

	    /* Dispose of the dead threads. */
	    while (kthread != 0) {
		struct Kernel_Thread* next = Get_Next_In_Thread_Queue(kthread);
#if 0
		Print("Reaper: disposing of thread @ %x, stack @ %x\n",
		    kthread, kthread->stackPage);
#endif
		Destroy_Thread(kthread);
		kthread = next;
	    }

	    /*
	     * Disable interrupts again, since we're going to
	     * do another iteration.
	     */
	    Disable_Interrupts();
	}
    }
}

/*
 * Find the best (highest priority) thread in given
 * thread queue.  Returns null if queue is empty.
 */
static __inline__ struct Kernel_Thread* Find_Best(struct Thread_Queue* queue)
{
    /* Pick the highest priority thread */
    struct Kernel_Thread *kthread = queue->head, *best = 0;
    while (kthread != 0) {
	if (best == 0 || kthread->priority > best->priority)
	    best = kthread;
	kthread = Get_Next_In_Thread_Queue(kthread);
    }
    return best;
}

/*
 * Acquires pointer to thread-local data from the current thread
 * indexed by the given key.  Assumes interrupts are off.
 */
static __inline__ const void** Get_Tlocal_Pointer(tlocal_key_t k) 
{
    struct Kernel_Thread* current = g_currentThread;

    KASSERT(k < MAX_TLOCAL_KEYS);

    return &current->tlocalData[k];
}

/*
 * Clean up any thread-local data upon thread exit.  Assumes
 * this is called with interrupts disabled.  We follow the POSIX style
 * of possibly invoking a destructor more than once, because a
 * destructor to some thread-local data might cause other thread-local
 * data to become alive once again.  If everything is NULL by the end
 * of an iteration, we are done.
 */
static void Tlocal_Exit(struct Kernel_Thread* curr) {
    int i, j, called = 0;

    KASSERT(!Interrupts_Enabled());

    for (j = 0; j<MIN_DESTRUCTOR_ITERATIONS; j++) {

        for (i = 0; i<MAX_TLOCAL_KEYS; i++) {

	    void *x = (void *)curr->tlocalData[i];
	    if (x != NULL && s_tlocalDestructors[i] != NULL) {

	        curr->tlocalData[i] = NULL;
		called = 1;

		Enable_Interrupts();
		s_tlocalDestructors[i](x);
		Disable_Interrupts();
	    }
	}
	if (!called) break;