#include #include #include #define _XOPEN_SOURCE #include #include #include #include "mythreads.h" // Wrapper function macro that disables interrupts #define interruptDisable() \ do { \ assert(!interruptsAreDisabled); \ interruptsAreDisabled = true; \ } while(0) // Wrapper function macro that enables interrupts #define interruptEnable() \ do { \ assert(interruptsAreDisabled); \ interruptsAreDisabled = false; \ } while(0) // Struct to represent a thread typedef struct Thread { int ID; // Context to hold the events that should be performed by the thread ucontext_t *newContext; // Context to hold the events that preceded the start of the thread // (such as the call from threadCreate) ucontext_t *originalContext; bool isRunning; // Variable to hold the return value of the function call void *returnValue; // Pointer to the next thread in a linked list struct Thread *next; } thread_t; // Struct to represent a single lock with CONDITIONS_PER_LOCK conditions typedef struct Lock { bool locked; bool conditions[CONDITIONS_PER_LOCK]; } lock_t; // Variable that holds the status of whether interrupts are disabled int interruptsAreDisabled; // Linked list nodes to hold threads thread_t *head = NULL; thread_t *tail = NULL; thread_t *currentThread = NULL; // Array to hold a series of locks that can be acquired by a thread lock_t locks[NUM_LOCKS]; // Status variable that determines whether destructor should actually memory other than head node bool freeListMemory = true; // Destructor that runs at the end of main to free memory void __attribute__((destructor)) lastChecks() { if (freeListMemory) { // Create temp node to loop through linked list (starting after head) thread_t *temp = head->next; // Loop through linked list while (temp != NULL) { // Store node to be freed thread_t *toBeFreed = temp; // Advance temp node temp = temp->next; // Free all dynamically allocated memory for current node free(toBeFreed->newContext); free(toBeFreed->originalContext); free(toBeFreed); } } // Free dynamically allocated memory for head node free(head->newContext); free(head); } // Wrapper function to observe return value of function pointer call // Takes in thFuncPtr function pointer and argument from threadCreate, calls thFuncPtr like // normal function with assignable return value // Reference: https://stackoverflow.com/a/65776559 void thFuncWrapper(void *(*thFuncPtr) (void *), void *argPtr) { // Assign return value of thFuncPtr call to returnValue void *returnValue = thFuncPtr(argPtr); // Call threadExit, passing returnValue as expected return value for later storage threadExit(returnValue); } // Function to get a thread by its ID thread_t *getThreadByID(int threadID) { // Create a temp node to loop through the linked list thread_t *temp = head; // Loop while there's still a node in the list while (temp != NULL) { // If the thread's ID matches the parameter, return it if (threadID == temp->ID) { return temp; } // Move to the next node in list temp = temp->next; } // If the function has made it to this point without finding a match, return NULL return NULL; } // Function to test and set a specified spinlock bool checkIfLocked(bool *lock) { // Store initial status of lock bool initialStatus = *lock; // Set lock to true (either locks an unlocked lock or has no effect on a locked lock) *lock = true; return initialStatus; } // My test applications will call threadInit to initialize // your library. You can safely assume that this will be the first call into // your library that any application will make. This would be a good // place to initialize any data structures. void threadInit() { // Initialize global interrupts status variable interruptsAreDisabled = 1; // Loop through locks array for (int i = 0; i < NUM_LOCKS; i++) { // Initialize lock to false locks[i].locked = false; // Loop through conditions array within current lock for (int j = 0; j < CONDITIONS_PER_LOCK; j++) { // Initialize condition to false locks[i].conditions[j] = false; } } // Allocate memory for head node in linked list (main thread) head = malloc(sizeof(thread_t)); // Initialize thread information head->ID = 0; // head does not have an original context, since it's essentially the original // context of all subsequent threads head->originalContext = NULL; head->isRunning = true; head->returnValue = NULL; // Set head next pointer to NULL since it's the first thread head->next = NULL; // Set linked list nodes tail = head; currentThread = head; // Dynamically allocate memory for main thread context head->newContext = malloc(sizeof(ucontext_t)); // Enable interrupts interruptEnable(); // Save main thread context getcontext(head->newContext); } // Applications will call threadCreate to create new // threads. When an application calls this function, a new thread should // be created. The new thread should have a stack of size STACK_SIZE // and should execute the specified function with the argument (void // *) that was passed to threadCreate. If successful, this function should // return an int that uniquely identifies the new thread, and will be // used in calls to the threadJoin function. The newly created thread // should be run immediately after it is created (before threadCreate // returns). int threadCreate(thFuncPtr funcPtr, void *argPtr) { // Disable interrupts interruptDisable(); // Create a new thread node thread_t *newThread = malloc(sizeof(thread_t)); // Initialize new thread with the next incremental ID newThread->ID = tail->ID + 1; newThread->isRunning = true; newThread->returnValue = NULL; // Set next pointers appropriately newThread->next = NULL; tail->next = newThread; // Set linked list nodes appropriately tail = newThread; currentThread = newThread; // Create a new stack for the new thread char *newStack = malloc(STACK_SIZE); // Allocate memory for the new thread's context newThread->newContext = malloc(sizeof(ucontext_t)); getcontext(newThread->newContext); // Give the new thread the new stack newThread->newContext->uc_stack.ss_sp = newStack; newThread->newContext->uc_stack.ss_size = STACK_SIZE; newThread->newContext->uc_stack.ss_flags = 0; // Make the new context run the function call that was passed to threadCreate // using a wrapper function that can observe the return value of the funcPtr call // Reference: https://stackoverflow.com/a/65776559 makecontext(newThread->newContext, (void (*)(void))thFuncWrapper, 2, funcPtr, argPtr); // Allocate memory for the context of the active call to threadCreate so that it can // eventually return the thread ID newThread->originalContext = malloc(sizeof(ucontext_t)); // Enable interrupts interruptEnable(); // Switch the context from current to new swapcontext(tail->originalContext, tail->newContext); // Disable interrupts interruptDisable(); // Free memory for new thread stack free(newStack); // Enable interrupts interruptEnable(); return newThread->ID; } // Calls to threadYield cause the currently running thread // to “yield” (give up) the processor to the next runnable thread. Your // threading library will save the current thread’s context and select // the next thread for execution. The call to threadYield will not re- // turn until the thread that called it is selected again to run. We will // also call this function in order to preempt your threads during test- // ing. void threadYield() { // Disable interrupts interruptDisable(); // Set the next thread to be executed to the current thread thread_t *nextThread = currentThread; // Loop while there's a thread after the current thread while (nextThread->next != NULL) { // Advance nextThread = nextThread->next; // If the next thread is running and isn't the current thread, we've found a good candidate if (nextThread->isRunning == true && nextThread != currentThread) { break; } } // Create a context for the current running context // (so that there's something to swap from) ucontext_t *yieldContext = malloc(sizeof(ucontext_t)); getcontext(yieldContext); // Free memory for the current thread's existing context free(currentThread->newContext); // Set the current thread's context to the new context in threadYield currentThread->newContext = yieldContext; // Update currentThread to the newly-chosen thread currentThread = nextThread; // Enable interrupts interruptEnable(); // Switch the context from current state of threadYield to the new thread to be run swapcontext(yieldContext, currentThread->newContext); } // This function waits until the thread corresponding to // id exits (either through a call to threadExit or by returning from // the thread function). If the result argument is not NULL, then the // thread function’s return value (or the return value passed to threadExit) // is stored at the address pointed to by result. Otherwise, the thread’s // return value is ignored. If the thread specified by id has either al- // ready exited, or does not exist, then the call should return immedi- // ately. You should store the results of all exited threads, at least until // threadJoin has been called on that thread, so that the result can be // retrieved. void threadJoin(int thread_id, void **result) { // Disable interrupts interruptDisable(); // Call helper function getThreadNodeByID to find the thread matching the // supplied ID thread_t *threadByID = getThreadByID(thread_id); // If the thread found by getThreadNodeByID is NULL, return early if (threadByID == NULL) { // Enable interrupts interruptEnable(); return; } // Create a context for the current running context // (so that there's something to swap from) ucontext_t *currentContext = malloc(sizeof(ucontext_t)); getcontext(currentContext); // Wait until the thread is no longer running // This loop gets broken up by context switches, which is difficult to follow, but // if it works then it works while (threadByID->isRunning == true) { // Set the current thread (functionally next thread) to the thread found by ID currentThread = threadByID; // Enable interrupts interruptEnable(); // Switch context to the run context of the thread found by ID swapcontext(currentContext, currentThread->newContext); // Disable interrupts interruptDisable(); } // If the supplied result is not NULL, store the current thread's result if (result != NULL) { *result = threadByID->returnValue; } // Free memory for context free(currentContext); // Enable interrupts interruptEnable(); } // This function causes the current thread to exit. Calling // this function in the main thread will cause the process to exit. The // argument passed to threadExit is the thread’s return value (equiv- // alent to returning the same value from the thread function), which // should be passed to any calls to threadJoin by other threads wait- // ing on this thread. void threadExit(void *result) { // If the current thread is the head node, exit program entirely // This is in case threadExit gets called from main if (currentThread == head) { freeListMemory = false; exit(-1); } // Set the running status of the current thread to false and store the // supplied result in the thread node currentThread->isRunning = false; currentThread->returnValue = result; // Switch context back to the thread's original context, which is the original call // to threadCreate swapcontext(currentThread->newContext, currentThread->originalContext); } // This function blocks (waits) until it is able to acquire // the specified lock. Your library should allow other threads to con- // tinue to execute concurrently while one or more threads are waiting // for locks. Note that the parameter passed to the function is a num- // ber that indicates which lock is to be locked (i.e., lock #3 — locks are // numbered from 0 to NUM_LOCKS-1). This parameter is not the lock // itself. void threadLock(int lockNum) { // Disable interrupts interruptDisable(); // Loop until the specified lock is no longer locked while (checkIfLocked(&locks[lockNum].locked) == true) { // Enable interrupts (required to call other thread function) interruptEnable(); // Call threadYield to allow other threads to run concurrently threadYield(); // Disable interrupts interruptDisable(); } // Enable interrupts interruptEnable(); } // This function unlocks the specified lock. As with // threadLock, the parameter passed is not the lock, but rather indi- // cates the number of the lock that should be unlocked. Trying to // unlock an already unlocked lock should have no effect. void threadUnlock(int lockNum) { // Disable interrupts interruptDisable(); // Set lock to false (does nothing if lock is already unlocked) locks[lockNum].locked = false; // Enable interrupts interruptEnable(); } // This function atomically unlocks the specified mutex // lock and causes the current thread to block (wait) until the speci- // fied condition is signaled (by a call to threadSignal). The waiting // thread unblocks only after another thread calls threadSignal with // the same lock and condition variable. The mutex must be locked be- // fore calling this function, otherwise the behavior is undefined (your // library should exit the process, if this occurs, and print out an error // message). Before threadWait returns to the calling function, it re- // acquires the lock. void threadWait(int lockNum, int conditionNum) { // Disable interrupts interruptDisable(); // Check to make sure the specified lock is not unlocked if (locks[lockNum].locked == false) { // Print error message fprintf(stderr, "Error: Lock #%d is already unlocked.", lockNum); exit(-1); } // Enable interrupts (required to call other thread function) interruptEnable(); // Unlock specified lock threadUnlock(lockNum); // Disable interrupts interruptDisable(); // Wait until the specified condition is met (triggered by a call to threadSignal) while (locks[lockNum].conditions[conditionNum] == false) { // Enable interrupts (required to call other thread function) interruptEnable(); // Move on to another thread threadYield(); // Disable interrupts interruptDisable(); } // Enable interrupts interruptEnable(); // Acquire the specified lock threadLock(lockNum); } // This function unblocks a single thread waiting on // the specified condition variable. If no threads are waiting on the // condition variable, the call has no effect. void threadSignal(int lockNum, int conditionNum) { // Disable interrupts interruptDisable(); locks[lockNum].conditions[conditionNum] = true; // Enable interrupts interruptEnable(); }