lib-ult.c

/*
 * Brian Anderson, Com S 352 Project 1
 * UThread a User Thread Library, it uses only 1 "kernel thread"
 */


#ifdef __APPLE__
#define _XOPEN_SOURCE   /* See note at the bottom about this */
#endifult_activeContext

#ifndef LIB_USER_LEVEL_THREAD
#define LIB_USER_LEVEL_THREAD

#include <stdlib.h>
#include <stdio.h>
#include <ucontext.h>

/* Because using 0's and 1's are so very C and 1980's */
#define SUCCESSFUL 0
#define NOT_SUCCESSFUL -1

#define ULT_STACK_SIZE (8192)   /* Arbitrary size, might need to be larger ?? */

/*------------------------------------------------------------------------ */


/* ======================= PRIORITY QUEUE ===================================
* The follow is the priority queue node that contains
* the context of the function to be executed
*
* It works together with:
*            int ult_PQPush (ucontext_t* context, int priority)
*    ucontext_t* ult_PQPop (int *validContextReturned)
*
* This is a private data structure and functions. It is implements
* a priority queue that orders the priority on insert.
* Complexity:
*   Pop -   O(1),
*   Push -  O(n)
*
* ---------------- Priority Queue structure ------------------------------ */
struct ult_PQNode{
  int priority;                 /* Priority, lower integer is 
                                 *     a higher priority */
  struct ult_PQNode* next;      /* Next node */
  struct ult_PQNode* previous;  /* Previous node */
  ucontext_t* context;          /* the context to use */
};
typedef struct ult_PQNode ult_PQNode;   // I just hate writing struct :)
/* 
* The head node, static */
static ult_PQNode* ult_headNode;
/* ----------------------------------------------------------------------- */

/* 
 * Add a context with the priority to the Priority Queue
 * The add, walks down the ordered priority list
 * When it finds a task with a high priority integer than
 * the it's own, it adds itself right before it.
 * 
 * The expense of keeping the queue in priority order is
 * incurred on the add. Worst case is it visits every node
 * and is O(n).
 */
int ult_PQPush(ucontext_t* context, int priority){
    int ofTheJedi = NOT_SUCCESSFUL;
    if(priority >= 0){    // something sensible here

        // Allocate a new node space
        ult_PQNode* newNode = (ult_PQNode*) malloc(sizeof(ult_PQNode)); /* initialize new node */
        // set the priority
        newNode->priority = priority;
        // Defaults to having nothing after it
        newNode->next = 0;
        // Store the context
        newNode->context = context;
        // Starting with the Head node walk down until finding a 
        // lower priority (higher int value) thread and then insert it before that.
        ult_PQNode* checkNode = ult_headNode;
        // These maintain priority order
        while(checkNode->next != 0 && checkNode->next->priority <= newNode->priority){      
            checkNode = checkNode->next;
        }
        // The new node's next should map to the previou's nodes next
        newNode->next = checkNode->next;

          /* if there is a node here, we need it to point back */
        if(newNode->next != 0){
            newNode->next->previous = newNode;
        }

        newNode->previous = checkNode;
        checkNode->next = newNode;

        ofTheJedi = SUCCESSFUL; 
    } else {
        perror("I can not schedule a negative priority\n");
    }
    
    return ofTheJedi;
}


/* 
 * Pops the first item off the queue (lowest priority),
 * It returns a pointer to a context structure
 */
ucontext_t* ult_PQPop(int *validContextReturned){
    ucontext_t* context;

    // Check to verify we have a node to pop
    if(ult_headNode->next != 0){
        context = ult_headNode->next->context;

        // Remember the new next load
        ult_PQNode* theNewNextNode = ult_headNode->next->next;

        // free the memory allocated, don't want to leak
        free(ult_headNode->next); ult_headNode->next = 0;
                                                    // ^ old school habits;
        //Head's next is now the second node
        ult_headNode->next = theNewNextNode;

        //If there is another item available, 
        //      set the previous to point to head
        if(ult_headNode->next != 0){
          ult_headNode->next->previous  = ult_headNode;
        }

        *validContextReturned = SUCCESSFUL;        /* I am happy */
    } else {
        *validContextReturned = NOT_SUCCESSFUL;    /* Unable to pop */
    }
    return context;
}


/* ============== USER LEVEL THREADING LIBRARY ========================
 *
 * This function is called before any other uthread library
 * functions can be called. It initializes the uthread system.
 * 
 * NOTE: With the interface being defined, there is really no
 * mechanism to check this failed or not ...
 */
void system_init() {
  /* Initialize the headNode for the queue */
  ult_headNode = (ult_PQNode*) malloc(sizeof(ult_PQNode));
  ult_headNode->next = 0;
  ult_headNode->previous = 0;
  ult_headNode->context = 0;
  ult_headNode->priority = 0;
}

/*
 * This function creates a new user-level thread which runs func(),
 * with priority number specified by argument priority. This function 
 * returns 0 if succeeds, or -1 otherwise. 
 * 
 * NOTE:
 * the thread that has the highest priority level when it has 
 * the lowest priority number but the priority can not be 
 * less than zero (0).
 */
int uthread_create(void func(), int priority) {
    int returnValue = NOT_SUCCESSFUL;
    if(priority >= 0){

        // Create the thread context and allocate memory
        ucontext_t* threadContext = (ucontext_t*) malloc(sizeof(ucontext_t));
        getcontext(threadContext);
        // give the thread's context some more
        threadContext->uc_stack.ss_sp = (char *) malloc(ULT_STACK_SIZE);
        threadContext->uc_stack.ss_size = ULT_STACK_SIZE;
        
        // This now has the thread context created
        makecontext(threadContext, func, 0);

        //Now that the context is setup, its pushed onto the stack with the correct priority.
        returnValue = ult_PQPush(threadContext,priority);
    }
    return returnValue;
}

/*
 * The calling thread requests to yield the kernel thread, that
 * it is currently running, to one of other user threads which 
 * has the highest priority level among the ready threads. 
 * if there is one or more other threads ready to run. 
 * 
 * If no any other thread is ready to run, the calling thread should
 * proceed to run on the kernel thread. This function returns 0 
 * if succeeds, or -1 otherwise.
 */
int uthread_yield(int priority) {
    int returnValue = NOT_SUCCESSFUL;

    // Try to pop an item off the queue    
    int popResult;
    ucontext_t* contextToSwitchTo = ult_PQPop(&popResult);
    if(popResult == SUCCESSFUL){ // Okay, We have another item in the queue
        
        // This will hold the current context
        ucontext_t* currentContextToSave = (ucontext_t*) malloc(sizeof(ucontext_t));
        
        // Now all we need to do is push the previous one back
        returnValue = ult_PQPush(currentContextToSave, priority);
        if(returnValue == SUCCESSFUL){ // Successfully pushed it ont he queue
            swapcontext(currentContextToSave,contextToSwitchTo);
        }
    } else {
        // There is no other thread waiting for us... keep on going
        
        // It isn't clear that this actually is the right behavior?
        // Do we return NOT_SUCCESSFUL if we didn't switch contexts
        // or if we had an error ??
        returnValue = NOT_SUCCESSFUL;
    }

    return returnValue;
}

/* 
 * The calling user-level thread ends its execution.   
 *      Should be called at the end of every user thread code.
 */
void uthread_exit() {
    // This thread is done, is there another one waiting?
    int popResult;
    ucontext_t* contextToSwitchTo = ult_PQPop(&popResult);
    if(popResult == SUCCESSFUL){
        setcontext(contextToSwitchTo);
    } else {
        // Clean up the head node
        free(ult_headNode);
        ult_headNode = 0;
        
        // Nothing left to free, pop cleans up after itself
        // and I thinking setcontext will free() the previous context
        // for us.
        exit(0);
    }
    
}

#endif

/*
* -----------------------------------------------------------------------------
* Documentation and Resources
* =============================================================================
* Implementing a Thread Library on Linux
*   http://www.evanjones.ca/software/threading.html
*
* Man pages on makecontext(), swapcontext()
*   http://linux.die.net/man/3/makecontext
*/



/* On Mac OS X, _XOPEN_SOURCE must be defined before including ucontext.h.
 * Otherwise, getcontext/swapcontext causes memory corruption. See:
 * http://lists.apple.com/archives/darwin-dev/2008/Jan/msg00229.html 
 */

Thank you. This was really helpful.