uthreads.cpp

#include "uthreads.h"
#include <deque>
#include <stdio.h>
#include <stdlib.h>
#include "Thread.h"
#include <sys/time.h>
#include <algorithm>

#define EXIT_ERR (-1)
#define THREAD_LIB_ERR "thread library error: %s.\n"
#define THREAD_LIB_ERR_EXIT(err_msg) \
        fprintf(stderr, THREAD_LIB_ERR, err_msg); \
        return EXIT_ERR;
#define EXIT_SYS_CALL_ERR 1
#define SYS_CALL_ERR "system error: %s.\n"
#define SYS_CALL_ERR_EXIT(err_msg) \
        fprintf(stderr, SYS_CALL_ERR, err_msg); \
        delete_threads(); \
        exit(EXIT_SYS_CALL_ERR);

#define INVALID_QUANTUM "Quantum must be a positive integer"
#define STARTING_QUANTUMS 1
#define SIGACTION_FAILURE "Sigaction failed. Terminating process"
#define TIMER_SETUP_FAILURE "Failed to set up timer. Terminating process"
#define INVALID_ENTRY_POINT "Entry point cannot be null"
#define NO_AVAILABLE_THREAD_ERR "Maximum number of concurrent threads reached"
#define SIG_SET_INIT_FAILURE "Failed to initialize the signal set"
#define SIGVTALRM_BLOCK_FAILURE "Failed to block SIGVTALRM signal"
#define SIGVTALRM_RESTORE_FAILURE "Failed to restore SIGVTALRM signal masks"
#define ERR_MSG_LEN 256
#define MEMORY_ALLOC_FAILURE "Memory allocation for thread %d failed"
#define INVALID_TID "Thread ID %d is invalid"
#define SIG_LONG_JMP_VAL 1 // A non-zero value to indicate a long jump
#define BLOCK_MAIN_THREAD_ERR "Main thread cannot be blocked"


Thread * threads[MAX_THREAD_NUM] = {nullptr};
std::deque<int> ready_queue;
int current_tid;
int total_quantums_elapsed;
int quantum_time_usecs;
struct itimerval timer;

int setup_timer(); // Forward declaration
void timer_handler(int signum); // Forward declaration
void delete_threads(); // Forward declaration
void delete_thread(int tid); // Forward declaration
int thread_lib_exit(const char* msg, const sigset_t* old_mask=nullptr); // Forward declaration
void sys_call_exit(const char* msg, const sigset_t* old_mask=nullptr); // Forward declaration;

/**
 * Blocks the SIGVTALRM signal and saves the old signal mask in old_mask.
 * @param old_mask A pointer to a sigset_t structure that will hold the old signal mask.
 * @return EXIT_SUCCESS on success, -1 on failure. Will terminate the process if it fails.
 */
int block_sigvtalrm(sigset_t* old_mask)
{
    sigset_t mask;
    if (sigemptyset(&mask) == EXIT_ERR || sigaddset(&mask, SIGVTALRM) == EXIT_ERR)
    {
        return thread_lib_exit(SIG_SET_INIT_FAILURE, old_mask);
    }

    if (sigprocmask(SIG_BLOCK, &mask, old_mask) == EXIT_ERR)
    {
        sys_call_exit(SIGVTALRM_BLOCK_FAILURE, old_mask);
    }

    return EXIT_SUCCESS;
}

/**
 * Restores the old signal mask of the SIGVTALRM signal.
 * If the signal mask cannot be restored, it terminates the process.
 * @param old_mask The old signal mask to restore.
 */
void restore_sigvtalrm(const sigset_t* old_mask)
{
    if (sigprocmask(SIG_SETMASK, old_mask, nullptr) == EXIT_ERR)
    {
        return sys_call_exit(SIGVTALRM_RESTORE_FAILURE, old_mask);
    }
}

/**
 * Prints an error message and returns EXIT_ERR.
 * If old_mask is not null, it restores the old signal mask.
 * @param msg The error message to print.
 * @param old_mask If not null, the old signal mask to restore.
 * @return EXIT_ERR.
 * @note Terminates the program in case of failure.
 */
int thread_lib_exit(const char* msg, const sigset_t* old_mask)
{
    if (old_mask != nullptr)
    {
        // Restore the old signal mask
        restore_sigvtalrm(old_mask);
    }
    THREAD_LIB_ERR_EXIT(msg)
}

/**
 * Terminates the program and restores the old signal mask.
 * @param msg The message to print.
 * @param old_mask If not null, the old signal mask to restore.
 */
void sys_call_exit(const char* msg, const sigset_t* old_mask)
{
    if (old_mask != nullptr)
    {
        // Restore the old signal mask
        restore_sigvtalrm(old_mask);
    }
    SYS_CALL_ERR_EXIT(msg)
}

/**
 * Update the sleeping threads.
 * Reduces the quantum sleeping for each sleeping thread.
 * If a thread's quantum sleeping reaches 0, it is moved to the ready queue, but only if it is not blocked.
 */
void update_sleeping_threads()
{
    for (auto & thread : threads)
    {
        if (thread != nullptr && thread->is_sleeping())
        {
            thread->dec_quantum_sleeping();
            if (!thread->is_sleeping() && !thread->get_is_blocked())
            {
                // We change the thread's state only if it is both not sleeping and not blocked.
                thread->set_state(READY);
                ready_queue.push_back(thread->get_tid());
            }
        }
    }
}

/**
 * Switches the context to the next thread in the ready queue.
 * @param delete_current_thread If \c true, deletes the current thread.
 * @param old_mask The old signal mask to restore.
 */
void switch_context(const sigset_t* old_mask, const bool delete_current_thread=false)
{
    // First, we need to save the current thread's context, but only if we don't intend to delete it.
    if (!delete_current_thread && sigsetjmp(*threads[current_tid]->get_env(), SAVE_SIGS) == SIG_LONG_JMP_VAL)
    {
        return; // This is the long jump back to the thread's context
    }
    // Then, we need to find the next thread to run.
    if (ready_queue.empty())
    {
        // We do not think that this case will ever be reached, but just in case,
        // in such a case we will add the main thread to the ready queue, thus making it the thread
        // we will jump to.
        ready_queue.push_front(MAIN_THREAD_TID);
    }

    const int old_tid = current_tid; // Save the current thread ID
    const int new_tid = ready_queue.front(); // Get the next thread to run
    ready_queue.pop_front(); // Remove it from the ready queue
    threads[new_tid]->set_state(RUNNING); // Set the new thread to RUNNING state
    threads[new_tid]->inc_quantum_running(); // Increment the quantum running for the new thread
    total_quantums_elapsed++; // Increment the total quantums elapsed
    current_tid = new_tid;

    update_sleeping_threads(); // Update the sleeping threads

    if (delete_current_thread)
    {
        delete_thread(old_tid); // Delete the current thread
    }

    if (setup_timer() == EXIT_ERR) // Reset the timer for the new thread
    {
        sys_call_exit(TIMER_SETUP_FAILURE);
    }

    // Restore the old signal mask
    restore_sigvtalrm(old_mask);

    // Switch to the new thread
    siglongjmp(*threads[new_tid]->get_env(), SIG_LONG_JMP_VAL); // Jump to the new thread's context
}

/**
 * Handles the SIGVTALRM signal: Preempts the current thread and switches to the next thread.
 * @param signum The number of the signal this timer handles (SIGVTALRM).
 */
void timer_handler(int signum)
{
    // Block SIGVTALRM signal to prevent interruption
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        sys_call_exit(SIGVTALRM_BLOCK_FAILURE);
    }

    threads[current_tid]->set_state(READY);
    ready_queue.push_back(current_tid);
    switch_context(&old_mask); // Switch to the next thread
}

/**
 * Sets up the timer to expire after quantum_time_usecs microseconds.
 */
int setup_timer()
{
    timer.it_value.tv_sec = 0; // First time interval, seconds part
    timer.it_value.tv_usec = quantum_time_usecs; // First time interval, micro-seconds part

    // Configure the timer to expire every quantum_time_usecs microseconds after that.
    timer.it_interval.tv_sec = 0; // Following time intervals, seconds part
    timer.it_interval.tv_usec = quantum_time_usecs; // Following time intervals, micro-seconds part

    if (setitimer(ITIMER_VIRTUAL, &timer, NULL) != 0)
    {
        return EXIT_ERR;
    }
    return EXIT_SUCCESS;
}

/**
 * Installs the timer handler for SIGVTALRM.
 */
int install_timer_handler()
{
    struct sigaction sa;
    sa.sa_handler = &timer_handler;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = 0;
    if (sigaction(SIGVTALRM, &sa, nullptr) != 0)
    {
        return EXIT_ERR;
    }
    return EXIT_SUCCESS;
}

int uthread_init(const int quantum_usecs)
{
    if (quantum_usecs <= 0)
    {
        return thread_lib_exit(INVALID_QUANTUM);
    }
    quantum_time_usecs = quantum_usecs;
    total_quantums_elapsed = STARTING_QUANTUMS;
    current_tid = MAIN_THREAD_TID;
    threads[MAIN_THREAD_TID] = new(std::nothrow) Thread(MAIN_THREAD_TID, nullptr);
    if (threads[MAIN_THREAD_TID] == nullptr)
    {
        char msg[ERR_MSG_LEN];
        snprintf(msg, ERR_MSG_LEN, MEMORY_ALLOC_FAILURE, MAIN_THREAD_TID);
        sys_call_exit(msg);
    }

    threads[MAIN_THREAD_TID]->set_state(RUNNING);
    threads[MAIN_THREAD_TID]->inc_quantum_running();
    if (install_timer_handler() == EXIT_ERR)
    {
        sys_call_exit(SIGACTION_FAILURE);
    }
    if (setup_timer() == EXIT_ERR)
    {
        sys_call_exit(TIMER_SETUP_FAILURE);
    }
    return EXIT_SUCCESS;
}

/**
 * @return The smallest available thread ID, or EXIT_ERR if no available thread ID is found.
 */
int get_smallest_available_tid()
{
    for (int i = 0; i < MAX_THREAD_NUM; i++)
    {
        if (threads[i] == nullptr)
        {
            return i;
        }
    }
    return EXIT_ERR;
}

/**
 * Removes the thread with the given ID from the ready queue if it is there.
 * @param tid The thread id to remove from the ready queue.
 */
void remove_from_ready_queue(const int tid)
{
    const auto it = std::find(ready_queue.begin(), ready_queue.end(), tid);
    if (it != ready_queue.end()) // If the thread is in the ready queue
    {
        ready_queue.erase(it);
    }
}

/**
 * Deletes the thread and frees its resources.
 * If it is in the ready queue, it removes it from the queue.
 * @note Assumes thread is not null.
 * @param tid The id of the thread to delete.
 */
void delete_thread(const int tid)
{
    remove_from_ready_queue(tid); // Remove the thread from the ready queue if it is there
    delete threads[tid];
    threads[tid] = nullptr;
}

/**
 * Deletes all threads in the threads array.
 * @note Called only when the library is terminated.
 */
void delete_threads()
{
    for (auto & thread : threads)
    {
        if (thread != nullptr)
        {
            delete_thread(thread->get_tid());
        }
    }
}

int uthread_spawn(const thread_entry_point entry_point)
{
    // Block SIGVTALRM signal to prevent interruption during thread creation
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        return EXIT_ERR;
    }

    if (entry_point == nullptr)
    {
        return thread_lib_exit(INVALID_ENTRY_POINT, &old_mask);
    }

    const int tid = get_smallest_available_tid();
    if (tid == EXIT_ERR)
    {
        return thread_lib_exit(NO_AVAILABLE_THREAD_ERR, &old_mask);
    }

    threads[tid] = new(std::nothrow) Thread(tid, entry_point);
    if (threads[tid] == nullptr)
    {
        char msg[ERR_MSG_LEN];
        snprintf(msg, ERR_MSG_LEN, MEMORY_ALLOC_FAILURE, tid);
        sys_call_exit(msg, &old_mask);
    }

    // Add the new thread to the end of the ready queue
    ready_queue.push_back(tid);

    // Restore the old signal mask
    restore_sigvtalrm(&old_mask);

    return tid;
}

/**
 * Checks if the given thread ID is valid.
 * @param tid The tid to check.
 * @return \c true if the tid is valid, \c false otherwise.
 */
bool is_valid_tid(const int tid)
{
    return tid >= MAIN_THREAD_TID && tid < MAX_THREAD_NUM && threads[tid] != nullptr;
}

int uthread_terminate(const int tid)
{
    // Block SIGVTALRM signal to prevent interruption during thread creation
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        return EXIT_ERR;
    }

    if (!is_valid_tid(tid)) // checks the validity of the given tid
    {
        char msg[ERR_MSG_LEN];
        snprintf(msg, ERR_MSG_LEN, INVALID_TID, tid);
        return thread_lib_exit(msg, &old_mask);
    }

    if (tid == MAIN_THREAD_TID) // If the user wants to terminate the main thread
    {
        delete_threads();
        restore_sigvtalrm(&old_mask);
        exit(EXIT_SUCCESS);
    }

    if (tid != current_tid)
    {
        delete_thread(tid);
        restore_sigvtalrm(&old_mask);
        return EXIT_SUCCESS;
    }

    // If we get here, this means the user wants to terminate the current thread.
    switch_context(&old_mask, true);

    return EXIT_SUCCESS; // This line is not reachable, but it's here to avoid a compiler warning.
}

int uthread_block(const int tid)
{
    // Block SIGVTALRM signal to prevent interruption during thread creation
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        return EXIT_ERR;
    }

    if (!is_valid_tid(tid)) // checks the validity of the given tid
    {
        char msg[ERR_MSG_LEN];
        snprintf(msg, ERR_MSG_LEN, INVALID_TID, tid);
        return thread_lib_exit(msg, &old_mask);
    }

    if (tid == MAIN_THREAD_TID)
    {
        return thread_lib_exit(BLOCK_MAIN_THREAD_ERR, &old_mask);
    }

    // Since blocking a thread in the BLOCKED state is allowed and is not considered an error,
    // if it is already blocked, the function will not affect its state and will return 0.
    // Moreover, if a thread is in the BLOCKED state, it means it is either sleeping or blocked.
    // If it is only sleeping, it will make sure its is_blocked flag is set to true.
    threads[tid]->set_state(BLOCKED); // Block the thread
    threads[tid]->set_is_blocked(true);

    if (tid == current_tid) // If the current thread blocks itself
    {
        switch_context(&old_mask);
        return EXIT_SUCCESS;
    }

    // If the thread is not the current thread, we have already blocked it, but we also need to
    // remove it from the ready queue if it is there
    remove_from_ready_queue(tid);

    // Restore the old signal mask
    restore_sigvtalrm(&old_mask);
    return EXIT_SUCCESS;
}

int uthread_resume(const int tid)
{
    // Block SIGVTALRM signal to prevent interruption during thread creation
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        return EXIT_ERR;
    }

    if (!is_valid_tid(tid)) // checks the validity of the given tid
    {
        char msg[ERR_MSG_LEN];
        snprintf(msg, ERR_MSG_LEN, INVALID_TID, tid);
        return thread_lib_exit(msg, &old_mask);
    }

    Thread* thread = threads[tid];

    if (thread->get_state() == BLOCKED)
    {
        thread->set_is_blocked(false); // Mark the thread as not blocked
        if (!thread->is_sleeping())
        {
            // We add the thread to the ready queue only if it is not currently sleeping.
            // If the thread is sleeping, it will be added to the end of the queue when it wakes up.
            thread->set_state(READY); // Set the thread to READY state
            ready_queue.push_back(tid);
        }
    }

    // If we get here, the thread is either not blocked or we have just finished unblocking it.
    // Restore the old signal mask
    restore_sigvtalrm(&old_mask);
    return EXIT_SUCCESS;
}

int uthread_sleep(const int num_quantums)
{
    // Block SIGVTALRM signal to prevent interruption during thread creation
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        return EXIT_ERR;
    }

    if (num_quantums <= 0)
    {
        return thread_lib_exit(INVALID_QUANTUM, &old_mask);
    }

    if (current_tid == MAIN_THREAD_TID)
    {
        return thread_lib_exit(BLOCK_MAIN_THREAD_ERR, &old_mask);
    }

    threads[current_tid]->set_quantum_sleeping(num_quantums + 1);
    threads[current_tid]->set_state(BLOCKED); // Set the thread to the BLOCKED state

    switch_context(&old_mask);

    return EXIT_SUCCESS;
}

int uthread_get_tid()
{
    return current_tid;
}

int uthread_get_total_quantums()
{
    return total_quantums_elapsed;
}

int uthread_get_quantums(const int tid)
{
    // Block SIGVTALRM signal to prevent interruption
    sigset_t old_mask;
    if (block_sigvtalrm(&old_mask) == EXIT_ERR)
    {
        return EXIT_ERR;
    }

    if (!is_valid_tid(tid)) // checks the validity of the given tid
    {
        char msg[ERR_MSG_LEN];
        snprintf(msg, ERR_MSG_LEN, INVALID_TID, tid);
        return thread_lib_exit(msg, &old_mask);
    }

    // Restore the old signal mask
    restore_sigvtalrm(&old_mask);
    return threads[tid]->get_quantum_running();
}