Skip to content
Snippets Groups Projects
Select Git revision
0 results

asd_assignment

  • Clone with SSH
  • Clone with HTTPS
  • t2-akhmetov's avatar
    t2-akhmetov authored
    521cc97c
    History

    Context switching with fibers and FIFO scheduler in System V ABI

    Task 1

    This project demonstrates the implementation of a basic fiber system in C++, using context switching and stack management. It showcases the creation and execution of lightweight, user-space threading constructs called fibers within a single thread. The final solution(foo_goo_ext.cpp) for the last pseudo code comprises of three key functions: foo, goo, and main, which demonstrate context switching between fibers while respecting stack alignment and layout rules as specified by the System V ABI for x86-64 Linux systems.

    Files:

    • context.hpp: This header file contains the definition of the Context structure and declarations of the assembly-implemented functions for context manipulation (get_context, set_context, swap_context).
    • context_switching: This file demonstrates basic context switching, using the provided pseudo code as a guide. It's an exemplary illustration of saving and restoring execution contexts within a single thread.
    int main() {
        volatile int x = 0; // Using volatile to prevent compiler optimizations
        Context c;
    
        if (get_context(&c) == 0) { // Saves the current context
            std::cout << "a message" << std::endl;
    
            if (x == 0) {
                x = 1;
                set_context(&c); // Restores the previously saved context
            }
        }
    
        return 0;
    }
    • foo_fiber.cpp: This file shows a straightforward setup of a fiber to execute the foo function. The implementation respects the stack alignment and Red Zone requirements of the System V ABI.
    void foo() {
        std::cout << "you called foo" << std::endl;
        exit(0); // Exits the program
    }
    int main() {
        char stack[4096]; // Allocating space for stack
    
        // Stacks grow downwards, so we set the stack pointer to the end of the array
        char* sp = stack + sizeof(stack);
    
        // Aligning stack to 16 bytes as per System V ABI
        sp = reinterpret_cast<char*>((reinterpret_cast<uintptr_t>(sp)) & -16L);
    
        // Accounting for the Red Zone
        sp -= 128;
    
        Context c;
        c.rip = (void*)foo; // Set the instruction pointer to foo
        c.rsp = (void*)sp;  // Set the stack pointer
    
        set_context(&c); // Switch to foo's context
        return 0;
    }
    • foo_goo_ext.cpp: The main C++ file which includes the implementation of the Fiber structure, the foo and goo functions, and the main function to demonstrate the use of fibers. The following code snippets are the crucial parts of the solution:
    const int StackSize = 4096;
    
    struct Fiber {
        char stack[StackSize];
        Context context;
    
        Fiber(void(*func)(Context*, Context*)) {
            char* sp = stack + sizeof(stack);
            sp = reinterpret_cast<char*>((reinterpret_cast<uintptr_t>(sp)) & -16L); // Align stack
            sp -= 128; // Account for Red Zone
    
            context.rip = (void*)func;
            context.rsp = (void*)sp;
        }
    };

    The Fiber structure is a pivotal part of the solution. Its constructor takes a function pointer, aligns the stack according to System V ABI specifications, and accounts for the Red Zone.

    void foo(Context* mainContext, Context* selfContext) {
        std::cout << "you called foo" << std::endl;
        swap_context(selfContext, mainContext); // Switch back to main
    }
    
    void goo(Context* mainContext, Context* selfContext) {
        std::cout << "you called goo" << std::endl;
        swap_context(selfContext, mainContext); // Switch back to main
    }

    These functions have been adapted to support fiber/context switching. They demonstrate the practical application of swapping contexts between different fibers.

    Context mainContext;
    
        // Save mains context and switch to foo
        if (get_context(&mainContext) == 0) {
            swap_context(&mainContext, &fooFiber.context); 
        }
    
        // Switch to goo
        if (get_context(&mainContext) == 0) {
            swap_context(&mainContext, &gooFiber.context); 
        }

    The main function in foo_goo_ext.cpp orchestrates the context swapping between multiple fibers, such as foo and goo, showcasing the practical implementation of the concepts.

    The following are instructions for running the code:

    as -o context.o ../context/context.s
    clang++ -std=c++11 -o example example_last_pseudo_code.cpp context.o

    These commands compile the assembly code for context manipulation and the C++ code, linking them together to create an executable that demonstrates advanced systems programming techniques in action.

    Results

    Example

    Unit Testing

    Task 2

    In the second task of our Advanced Systems Programming assignment, we delve deeper into the concept of fibers and introduce a scheduler for managing their execution. The objective is to encapsulate the properties and behaviors of fibers within a class and implement a scheduler that allows fibers to be executed in a round-robin fashion.

    Fibers

    In this task, we define a fiber as having two critical properties:

    • RSP (Stack Pointer): Points to the top of its stack, aligned according to the System V ABI.
    • RIP (Instruction Pointer): Points to the function that constitutes the fiber's execution body.
    private:
        Context context_;
        char* stack_bottom_;
        char* stack_top_;
        bool finished_;
        void* shared_data_;
    
    public:
        Fiber(void(*func)(Context*, Context*), void* shared_data_)
            : finished_(false), shared_data_(shared_data_) {
            stack_bottom_ = new char[StackSize];
            stack_top_ = stack_bottom_ + StackSize;
            stack_top_ = reinterpret_cast<char*>((reinterpret_cast<uintptr_t>(stack_top_)) & -16L); // Align stack
            stack_top_ -= 128; // Account for Red Zone
    
            context_.rip = (void*)func;
            context_.rsp = (void*)stack_top_;
            // make_context(&context_, func, arg, stack_bottom_, StackSize);
            // *(int**)(stack_top_ - sizeof(int*)) = shared_data_;
            // context_.rdi = (void*)sharedData;
        }

    The Fiber class abstracts the concept of a fiber. It manages the fiber's stack and execution context.

    • Constructor: Sets up the stack (aligned and accounting for the Red Zone) and initializes the context with the function pointer and the stack pointer.

    • Destructor: Cleans up the allocated stack.

    • Context Management: Provides functionality to get the fiber's context and shared data.

    • Execution State: Tracks whether the fiber has finished execution. ###Scheduler The Scheduler class manages the execution of fibers.

    • Fiber Queue: Utilizes std::deque to store fibers in FIFO order.

    • Context Management: Maintains the context for the scheduler and the currently executing fiber.

    • Method spawn: Adds a new fiber to the queue.

    • Method do_it: Executes fibers in a round-robin fashion, managing context switching between the scheduler and fibers.

    • Method fiber_exit: Marks the current fiber as finished and yields control back to the scheduler.

    class Scheduler {
    private:
        std::deque<Fiber*> fibers_;
        Context mainContext_;
        Fiber* currentFiber_ = nullptr;
    void spawn(Fiber* f) {
            fibers_.push_back(f);
        }
    
        void do_it() {
        while (!fibers_.empty()) {
            currentFiber_ = fibers_.front();
            fibers_.pop_front();
    
            // Here we swap context to the current fiber
            swap_context(&mainContext_, currentFiber_->get_context());
    
            // After the fiber exits, we check if it is finished
            if (currentFiber_->isFinished()) {
                // Clean up the finished fiber
                delete currentFiber_;
                currentFiber_ = nullptr;
            } else {
                // If the fiber is not finished, re-add it to the queue
                fibers_.push_back(currentFiber_);
            }
        }
    }
    
        void fiber_exit() {
        // Mark the current fiber as finished
        if (currentFiber_) {
            currentFiber_->setFinished(true);
            
            // Yield control back to the scheduler
            set_context(&mainContext_);
            // After set_context, the execution should not return here.
        }
    }

    Implementation

    The example file demonstrates the use of the Fiber and Scheduler classes. It creates two fibers, foo and goo, each manipulating shared data to showcase communication between fibers.

    Both functions access shared data, modify it, and then yield control back to the scheduler using globalScheduler.fiber_exit().

    Scheduler globalScheduler;

    A global scheduler acts as a centralized system to manage and control all the fibers within the application. By having a global scheduler, it ensures that the state of fiber execution and scheduling is consistent and coherent across the entire application. This consistency is crucial in avoiding synchronization issues, such as race conditions or deadlocks.

    void foo(Context* currentContext, Context* mainContext) {
        Fiber* currentFiber = globalScheduler.getCurrentFiber();
        int* sharedData = static_cast<int*>(currentFiber->getSharedData());
        std::cout << "Address of sharedData in foo: " << sharedData << std::endl;
        std::cout << "Starting fiber 1" << std::endl;
        std::cout << "shared Data before the increment: " << *sharedData << std::endl;
        *sharedData += 1;
        std::cout << "Fiber 1 after increment: " << *sharedData << std::endl;
        globalScheduler.fiber_exit(); // Yield control back to the scheduler
    }
    
    void goo(Context* currentContext, Context* mainContext) {
        Fiber* currentFiber = globalScheduler.getCurrentFiber();
        int* sharedData = static_cast<int*>(currentFiber->getSharedData());
        std::cout << "Address of sharedData in goo: " << sharedData << std::endl;
        std::cout << "shared Data before the increment: " << *sharedData << std::endl;
        *sharedData += 1;
        std::cout << "Fiber 2: " << *sharedData << std::endl;
        globalScheduler.fiber_exit(); // Yield control back to the scheduler
    }

    The functions provided fiber/scheduler.

    int sharedData = 10;
        std::cout << "Address of sharedData in main: " << &sharedData << std::endl;
    
        // Create fibers with functions that match the signature void (*)(Context*, Context*)
        Fiber* fiber1 = new Fiber(foo, &sharedData);
        Fiber* fiber2 = new Fiber(goo, &sharedData);
    
        globalScheduler.spawn(fiber1);
        globalScheduler.spawn(fiber2);
    
        globalScheduler.do_it();
    
        std::cout << "All fibers have completed." << std::endl;
        return 0;

    The main function does following:

    • Initializes shared data.
    • Creates fibers with foo and goo and the shared data pointer.
    • Spawns fibers using the global scheduler.
    • Starts the execution of fibers using globalScheduler.do_it().

    Results

    Example

    Unit Testing

    Task 3

    This solution extends our fiber-based system by introducing the capability for fibers to yield control back to the scheduler before completion. This addition is particularly useful in scenarios like the producer-consumer pattern and other use cases where cooperative multitasking is required. The implementation demonstrates the use of yield in conjunction with get_data to share data between fibers.

    Implementation

    Class Fiber

    • Manages a fiber's execution context and stack.
    • Handles shared data between fibers.
    • Provides functionality to check if the fiber has finished execution. Class Scheduler
    • Maintains a queue of fibers to be executed.
    • Implements yield, allowing a fiber to pause its execution and let other fibers run.
    • Manages context switching between fibers and the main context.
    void yield() {
            if (currentFiber_ != nullptr) {
                Fiber* fiber = currentFiber_;
                currentFiber_ = nullptr; // Clear the current fiber
    
                // Choose the next fiber to run
                // This is a simplistic approach; you might want to use a more sophisticated scheduling algorithm
                if (!fibers_.empty()) {
                    currentFiber_ = fibers_.front();
                    fibers_.pop_front();
                    fibers_.push_back(fiber); // Re-add the yielding fiber to the end of the queue
    
                    swap_context(fiber->get_context(), currentFiber_->get_context());
                } else {
                    // No more fibers to run, switch back to the main context
                    swap_context(fiber->get_context(), &mainContext_);
                }
            }
    }
    void do_it() {
        while (!fibers_.empty()) {
            currentFiber_ = fibers_.front();
            fibers_.pop_front();
    
            // Here we swap context to the current fiber
            swap_context(&mainContext_, currentFiber_->get_context());
    
            // After the fiber exits, we check if it's finished
            if (currentFiber_->isFinished()) {
                // Clean up the finished fiber
                delete currentFiber_;
                currentFiber_ = nullptr;
            } else {
                // If the fiber is not finished, re-add it to the queue
                fibers_.push_back(currentFiber_);
            }
        }
    
    Yield
    • The yield implementation in our fiber system plays a crucial role in enabling cooperative multitasking. Here’s a more in-depth look at how it works:

    • Context of Yield: In our fiber system, each fiber maintains its own execution context (Context), which includes its stack pointer, instruction pointer, and other necessary registers. When a fiber is executing, it's essentially in control of the CPU.

    • Yielding Control: When the yield function is called within a fiber, it signals that the fiber wishes to temporarily relinquish control of the CPU. This allows other fibers to run.

    • Scheduler's Role: Upon a yield call, control is transferred back to the scheduler. The scheduler takes the currently executing fiber and places it back into the fiber queue. This re-queuing is key; it ensures that the yielding fiber will resume execution later, from the point where it yielded.

    • Selecting the Next Fiber: The scheduler then picks the next fiber in the queue to execute. If there are no other fibers to run, it can either revert to the main context or wait until a new fiber is spawned.

    • Resuming a Yielded Fiber: When the scheduler eventually comes back to the yielded fiber (after executing other fibers), it restores that fiber's context, and execution continues from the point immediately after the yield call.

    Shared Data with Yield
    • Here's how shared data works in conjunction with yield:

    • Shared Data Setup: Shared data is passed to fibers when they are created. This data can be any type, but in our implementation, it's a pointer (void*) for flexibility.

    • Accessing Shared Data: Each fiber can access and manipulate this shared data. Since fibers are essentially functions, they can read, modify, or write to this shared data as needed.

    • Yielding with Shared Data: When a fiber yields, any changes made to the shared data are immediately visible to other fibers. This is because the data is shared among all fibers, residing in a common memory space accessible by all fibers.

    • Synchronization Considerations: Since fibers can be preempted at any time due to yield, care must be taken to ensure data consistency. If multiple fibers are modifying the same shared data, some form of synchronization (like mutexes or atomic operations) might be necessary to prevent data races or inconsistencies.

    • Resuming Fiber Execution: When a fiber that has yielded is resumed, it continues to have access to the shared data. Any changes made to the data by other fibers while it was yielded will be reflected.

    Scheduler globalScheduler;
    
    void foo(Context* currentContext, Context* mainContext) {
        Fiber* currentFiber = globalScheduler.getCurrentFiber();
        int* sharedData = static_cast<int*>(currentFiber->getSharedData());
        std::cout << "Address of sharedData in foo: " << sharedData << std::endl;
        std::cout << "Starting fiber 1" << std::endl;
        globalScheduler.yield();
        std::cout << "after, yield shared Data before the increment: " << *sharedData << std::endl;
        *sharedData += 1;
        std::cout << "Fiber 1 after increment: " << *sharedData << std::endl;
        globalScheduler.fiber_exit(); // Yield control back to the scheduler
    }
    
    void goo(Context* currentContext, Context* mainContext) {
        Fiber* currentFiber = globalScheduler.getCurrentFiber();
        int* sharedData = static_cast<int*>(currentFiber->getSharedData());
        std::cout << "Address of sharedData in goo: " << sharedData << std::endl;
        std::cout << "shared Data before the increment: " << *sharedData << std::endl;
        // globalScheduler.yield();
        *sharedData += 1;
        std::cout << "Fiber 2: " << *sharedData << std::endl;
        globalScheduler.fiber_exit(); // Yield control back to the scheduler
    }

    foo and goo are two fiber functions. foo uses yield to pause its execution, demonstrating how fibers can cooperatively multitask. main sets up the fibers and shared data, and then starts the fiber execution using globalScheduler.do_it().

    This implementation effectively demonstrates how fibers can be used in a cooperative multitasking environment, especially useful in scenarios where fibers need to yield control back to the scheduler before completing their execution. The addition of yield adds flexibility and enhances the functionality of our fiber-based system.

    Results

    Example

    Unit Testing