Scheduler issues

[bomboclaat954]

Hey. I'm working on the scheduler and basically on process management in my OS (BOMBOCLAAT-OS). It works good until it's time to come back to shell after executing a command. Everything is in ELF64 format (and it all works on x86_64). Another important info is that my timer (PIC) doesn't work (worked until I decided to implement tasks) and I have to call the scheduler manually. When I did some debug it turned out that some of the registers that should be saved during the context switch are overwritten by some random trash. When it should go back to shell, I get page fault instead.

task.h

Code: Select all

#ifndef TASK_H
#define TASK_H

#include <stdint.h>
#include <stddef.h>

typedef struct vmm_table vmm_table_t;

typedef struct
{
    uint64_t r15, r14, r13, r12, r11, r10, r9, r8;
    uint64_t rbp, rdi, rsi, rdx, rcx, rbx, rax;
    uint64_t int_no;
    uint64_t err_code;
    uint64_t rip;
    uint64_t cs;
    uint64_t rflags;
    uint64_t rsp;
    uint64_t ss;
} __attribute__((packed)) context_t;

typedef enum
{
    TASK_READY,
    TASK_RUNNING,
    TASK_BLOCKED,
    TASK_ZOMBIE
} task_state_t;

typedef struct task
{
    int pid;
    int parent_pid;
    task_state_t state;
    vmm_table_t *pml4;
    uintptr_t kstack_top;
    uintptr_t rsp;
    char name[16];
    struct task *next;
} task_t;

extern volatile int need_reschedule;

void task_init(void);
task_t *task_create(void *elf_data, int parent_pid, char *name);
context_t *schedule(context_t *ctx);
void task_exit();

extern void switch_to_task(uintptr_t next_rsp, uintptr_t next_cr3);

#endif

task.c

Code: Select all

#include <tasks/tasks.h>
#include <memory/memtools.h>
#include <memory/kmalloc.h>
#include <memory/vmm.h>
#include <memory/pmm.h>
#include <int/int.h>
#include <bomboclaat/elf64.h>
#include <bomboclaat/kprintf.h>
#include <lib/string.h>

extern vmm_table_t *kernel_pml4_virt;
extern uint64_t hhdm_offset;
extern tss_ptr tss;

task_t *current_task = NULL;
task_t *task_list_head = NULL;
int next_pid = 1;
volatile int need_reschedule = 0;

void task_init(void)
{
    task_t *kernel_task = (task_t *)kmalloc(sizeof(task_t));
    kernel_task->pid = 0;
    strcpy("kernel", kernel_task->name);
    kernel_task->state = TASK_BLOCKED;
    kernel_task->pml4 = kernel_pml4_virt;

    void *kstack_phys = pmm_alloc_frame();
    kernel_task->kstack_top = (uintptr_t)kstack_phys + hhdm_offset + PAGE_SIZE;
    kernel_task->rsp = kernel_task->kstack_top - sizeof(context_t);

    context_t *ctx = (context_t *)kernel_task->rsp;
    memset(ctx, 0, sizeof(context_t));

    kernel_task->next = kernel_task;
    kernel_task->parent_pid = 0;
    current_task = kernel_task;
    task_list_head = kernel_task;
}

task_t *task_create(void *elf_data, int parent_pid, char *name)
{
    ELF64_Ehdr *header = (ELF64_Ehdr *)elf_data;
    if (*(uint32_t *)header->e_ident != ELF_MAGIC || header->e_machine != 0x3E)
        return NULL;

    task_t *new_task = (task_t *)kmalloc(sizeof(task_t));
    strcpy(name, new_task->name);
    new_task->pid = next_pid++;
    new_task->parent_pid = parent_pid;
    new_task->pml4 = vmm_init();
    ELF64_Phdr *ph_table = (ELF64_Phdr *)((uintptr_t)elf_data + header->e_phoff);
    for (int i = 0; i < header->e_phnum; i++)
    {
        ELF64_Phdr *phdr = &ph_table[i];
        if (phdr->p_type == PT_LOAD)
        {
            uintptr_t page_boundary_dist = phdr->p_vaddr & 0xFFF;

            uintptr_t current_virt = phdr->p_vaddr & ~0xFFFULL;
            size_t bytes_written = 0;
            size_t mem_size = phdr->p_memsz;
            size_t file_size = phdr->p_filesz;
            size_t file_bytes_written = 0;

            while (bytes_written < mem_size)
            {
                void *phys_frame = pmm_alloc_frame();
                vmm_map_page(new_task->pml4, current_virt, (uintptr_t)phys_frame, VMM_PRESENT | VMM_WRITE | VMM_USER);

                uint8_t *kvirt = (uint8_t *)((uintptr_t)phys_frame + hhdm_offset);
                memset(kvirt, 0, PAGE_SIZE);

                uintptr_t dest_off = (bytes_written == 0) ? page_boundary_dist : 0;
                size_t space = PAGE_SIZE - dest_off;

                if (file_bytes_written < file_size)
                {
                    size_t to_copy = file_size - file_bytes_written;
                    if (to_copy > space)
                        to_copy = space;

                    memcpy(kvirt + dest_off,
                           (uint8_t *)elf_data + phdr->p_offset + file_bytes_written,
                           to_copy);

                    file_bytes_written += to_copy;
                }

                bytes_written += space;
                current_virt += PAGE_SIZE;
            }
        }
    }

    uintptr_t user_stack_virtual = 0xFFFFFFFFD0000000;

    void *ustack_frame1 = pmm_alloc_frame();
    void *ustack_frame2 = pmm_alloc_frame();

    vmm_map_page(new_task->pml4, user_stack_virtual, (uintptr_t)ustack_frame1, VMM_PRESENT | VMM_WRITE | VMM_USER);
    vmm_map_page(new_task->pml4, user_stack_virtual + PAGE_SIZE, (uintptr_t)ustack_frame2, VMM_PRESENT | VMM_WRITE | VMM_USER);

    uintptr_t user_rsp = (user_stack_virtual + (PAGE_SIZE * 2)) & ~0xFULL;

    void *kstack_phys = pmm_alloc_frame();
    new_task->kstack_top = (uintptr_t)kstack_phys + hhdm_offset + PAGE_SIZE;

    new_task->rsp = new_task->kstack_top - sizeof(context_t);
    context_t *ctx = (context_t *)new_task->rsp;
    memset(ctx, 0, sizeof(context_t));

    ctx->rip = header->e_entry;
    ctx->rsp = user_rsp;
    ctx->cs = 0x43;
    ctx->ss = 0x3B;
    ctx->rflags = 0x202;
    ctx->int_no = 0x20;
    ctx->err_code = 0;

    new_task->next = current_task->next;
    current_task->next = new_task;
    new_task->state = TASK_READY;

    return new_task;
}

context_t *schedule(context_t *ctx)
{
    if (current_task == NULL)
        return ctx;

    current_task->rsp = (uintptr_t)ctx;

    if (current_task->state == TASK_RUNNING)
        current_task->state = TASK_READY;

    task_t *next = current_task->next;
    int safety_counter = 0;

    while (next->state != TASK_READY && safety_counter < 64)
    {
        next = next->next;
        safety_counter++;
    }

    if (next->state != TASK_READY)
    {
        task_t *search = current_task;
        do
        {
            if (search->pid == 0)
            {
                next = search;
                break;
            }
            search = search->next;
        } while (search != current_task);
    }

    current_task = next;
    current_task->state = TASK_RUNNING;

    tss.rsp0 = current_task->kstack_top;

    uintptr_t next_cr3 = (uintptr_t)current_task->pml4 - hhdm_offset;
    // asm volatile("mov %0, %%cr3" : : "r"(next_cr3) : "memory");
    // context_t *next_ctx = (context_t *)next->rsp;
    // kprintf("Switching to pid=%d rip=0x%x rsp=0x%x cs=0x%x ss=0x%x\n", next->pid, next_ctx->rip, next_ctx->rsp, next_ctx->cs, next_ctx->ss);
    asm volatile("sti");
    switch_to_task(current_task->rsp, next_cr3);
    return (context_t *)current_task->rsp;
}

void task_exit()
{
    current_task->state = TASK_ZOMBIE;
    asm volatile("int $0x20");
    while (1)
        asm volatile("hlt");
}

switch.asm

Code: Select all

bits 64

global switch_to_task
switch_to_task:
    mov rax, cr3
    cmp rax, rsi
    je .skip_cr3
    mov cr3, rsi
.skip_cr3:
    mov rsp, rdi

    pop r15
    pop r14
    pop r13
    pop r12
    pop r11
    pop r10
    pop r9
    pop r8
    pop rbp
    pop rdi
    pop rsi
    pop rdx
    pop rcx
    pop rbx
    pop rax
    add rsp, 16

    iretq

isr.asm (may be useful)

Code: Select all

bits 64

%macro isr_no_err_stub 1
isr_stub_%1:
    cli
    push qword 0
    push qword %1
    jmp isr_common_stub
%endmacro

%macro isr_err_stub 1
isr_stub_%1:
    cli
    push qword %1
    jmp isr_common_stub
%endmacro

extern irq_handler
extern exception_handler
extern schedule
extern syscall_handler  

global isr_stub_default
global isr_stub_128
global syscall_exit

isr_stub_128:
    cli
    push qword 0
    push qword 128
    jmp syscall_common_stub

syscall_common_stub:
    cli
    push rax
    push rbx
    push rcx
    push rdx
    push rsi
    push rdi
    push rbp
    push r8
    push r9
    push r10
    push r11
    push r12
    push r13
    push r14
    push r15
    
    sub rsp, 8
    mov rdi, rsp
    add rdi, 8
    call syscall_handler
    add rsp, 8

    mov [rsp + 112], rax

    pop r15
    pop r14
    pop r13
    pop r12
    pop r11
    pop r10
    pop r9
    pop r8
    pop rbp
    pop rdi
    pop rsi
    pop rdx
    pop rcx
    pop rbx
    pop rax
    add rsp, 16
    iretq

syscall_exit:
    mov [rsp + 112], rax
    pop r15
    pop r14
    pop r13
    pop r12
    pop r11
    pop r10
    pop r9
    pop r8
    pop rbp
    pop rdi
    pop rsi
    pop rdx
    pop rcx
    pop rbx
    pop rax
    add rsp, 16
    iretq

isr_common_stub:
    push rax
    push rbx
    push rcx
    push rdx
    push rsi
    push rdi
    push rbp
    push r8
    push r9
    push r10
    push r11
    push r12
    push r13
    push r14
    push r15

    mov rdi, rsp
    call exception_handler

    pop r15
    pop r14
    pop r13
    pop r12
    pop r11
    pop r10
    pop r9
    pop r8
    pop rbp
    pop rdi
    pop rsi
    pop rdx
    pop rcx
    pop rbx
    pop rax

    add rsp, 16
    iretq

irq_common_stub:
    push rax
    push rbx
    push rcx
    push rdx
    push rsi
    push rdi
    push rbp
    push r8
    push r9
    push r10
    push r11
    push r12
    push r13
    push r14
    push r15

    mov ax, 0x30
    mov ds, ax
    mov es, ax

    mov rdi, rsp
    call schedule
    
    mov rsp, rax

    mov ax, 0x3B
    mov ds, ax
    mov es, ax

    pop r15
    pop r14
    pop r13
    pop r12
    pop r11
    pop r10
    pop r9
    pop r8
    pop rbp
    pop rdi
    pop rsi
    pop rdx
    pop rcx
    pop rbx
    pop rax
    add rsp, 16
    iretq

isr_no_err_stub 0
isr_no_err_stub 1
isr_no_err_stub 2
isr_no_err_stub 3
isr_no_err_stub 4
isr_no_err_stub 5
isr_no_err_stub 6
isr_no_err_stub 7
isr_err_stub    8
isr_no_err_stub 9
isr_err_stub    10
isr_err_stub    11
isr_err_stub    12
isr_err_stub    13
isr_err_stub    14
isr_no_err_stub 15
isr_no_err_stub 16
isr_err_stub    17
isr_no_err_stub 18
isr_no_err_stub 19
isr_no_err_stub 20
isr_no_err_stub 21
isr_no_err_stub 22
isr_no_err_stub 23
isr_no_err_stub 24
isr_no_err_stub 25
isr_no_err_stub 26
isr_no_err_stub 27
isr_no_err_stub 28
isr_no_err_stub 29
isr_err_stub    30
isr_no_err_stub 31

global isr_stub_32
isr_stub_32:
    cli
    push qword 0
    push qword 32
    jmp irq_common_stub

global isr_stub_33
isr_stub_33:
    cli
    push qword 0
    push qword 33
    jmp irq_common_stub

isr_stub_default:
    cli
    push qword 0
    push qword 0xFF
    jmp irq_common_stub

global isr_stub_table
isr_stub_table:
    %assign i 0
    %rep 32
        dq isr_stub_%+i
        %assign i i+1
    %endrep
    dq isr_stub_32
    dq isr_stub_33

syscall.c (where the processes are created after a request from ring 3)

Code: Select all

#include <int/int.h>
#include <bomboclaat/kprintf.h>
#include <bomboclaat/globals.h>
#include <bomboclaat/panic.h>
#include <bomboclaat/initramfs.h>
#include <tasks/loader.h>
#include <lib/string.h>
#include <fs/ramfs.h>
#include <memory/vmm.h>
#include <memory/pmm.h>
#include <memory/memtools.h>
#include <memory/kmalloc.h>
#include <drivers/io.h>
#include <tasks/tasks.h>
#include <stddef.h>

#define TEMP_MAP_ADDR 0xFFFFFFFFF0000000
extern void enter_user_mode(uintptr_t entry_point, uintptr_t user_stack);

void reboot()
{
    unsigned char good = 0x02;
    while (good & 0x02)
        good = inb(0x64);
    outb(0x64, 0xFE);
}

void shutdown()
{
    outw(0xB004, 0x2000); // QEMU
    outw(0x604, 0x2000);  // QEMU / Bochs
    outw(0x4004, 0x3400); // VirtualBox
    asm volatile("cli");
    asm volatile("hlt");
}

void syscall_send(uint64_t nsyscall, const char *args)
{
    asm volatile(
        "int $0x80"
        :
        : "a"(nsyscall), "D"(args)
        : "memory");
}

uint64_t syscall_handler(context_t *r)
{
    extern task_t *current_task;
    extern task_t *task_list_head;
    switch (r->rax)
    {
    case 1:
        kprintf((const char *)r->rdi);
        return 0;
    case 2:
        char *name = (char *)r->rdi;
        int current_pid = current_task->pid;
        extern void *initramfs_base;
        uint64_t size = 0;
        void *file = initramfs_find_file(initramfs_base, name, &size);
        if (file == NULL)
            return 0;

        task_t *new_task = task_create(file, current_task->pid, name);
        if (new_task == NULL)
            return 0;

        new_task->parent_pid = current_pid;
        current_task->state = TASK_BLOCKED;
        new_task->state = TASK_READY;
        r->rax = 1;
        schedule(r);
        return (uint64_t)r;
    case 3:
        current_task->state = TASK_ZOMBIE;

        task_t *t = current_task->next;
        while (t != current_task)
        {
            if (t->pid == current_task->parent_pid)
            {
                t->state = TASK_READY;
                break;
            }
            t = t->next;
        }

        task_t *prev = current_task->next;
        while (prev->next != current_task)
            prev = prev->next;
        prev->next = current_task->next;
        schedule(r);
        while (1)
            asm volatile("hlt");
    case 4:
        char *buf = (char *)r->rdi;
        input(buf);
        r->rax = 1;
        return (uint64_t)r;
    case 5:
        r->rax = 1;
        return (uint64_t)r;
    case 6:
        r->rax = 1;
        return (uint64_t)r;
    case 7:
        int type = (int)r->rdi;
        char *ret_buf = (char *)r->rsi;
        if (type == 0)
            strcpy(UNAME[0], ret_buf);
        else if (type == 1)
            strcpy(UNAME[1], ret_buf);
        else if (type == 2)
            strcpy(UNAME[2], ret_buf);
        r->rax = 1;
        return (uint64_t)r;
    case 8:
        int x = (int)r->rdi;
        if (x == 0)
            reboot();
        else if (x == 1)
            shutdown();
        r->rax = 1;
        return (uint64_t)r;
    case 9:
        extern vmm_table_t *kernel_pml4_virt;
        size_t increment = (size_t)r->rdi;
        uint8_t *previous_heap_end = init_heap_current;
        init_heap_current += increment;
        for (int i = 0; i < (increment / PAGE_SIZE) + 1; i++)
        {
            init_heap_current += i;
            void *frame = pmm_alloc_frame();
            vmm_map_page(kernel_pml4_virt, (uintptr_t)init_heap_current, (uintptr_t)frame, VMM_PRESENT | VMM_WRITE); // | VMM_USER
        }
        return (uint64_t)previous_heap_end;
    default:
        kprintf("Unknown syscall\n");
        r->rax = 1;
        return (uint64_t)r;
    }
}

shell.c (running in ring 3)

Code: Select all

#include <bomboclaat.h>
#include <stdint.h>

char *OSVER = "BOMBOCLAAT-OS v2.0-beta2";

int main()
{
    printf("%s\n", OSVER);
    while (1)
    {
        printf("# ");
        char cmd_line[1024];
        char cmd[32];
        char arg[96];
        scanf(cmd_line);

        int i = 0, j = 0;
        while (cmd_line[i] != ' ' && cmd_line[i] != '\0' && i < 31)
        {
            cmd[i] = cmd_line[i];
            i++;
        }
        cmd[i] = '\0';

        while (cmd_line[i] == ' ')
            i++;

        while (cmd_line[i] != '\0' && j < 95)
        {
            arg[j] = cmd_line[i];
            i++;
            j++;
        }
        arg[j] = '\0';

        char path[128];
        join("bin/", cmd, path, 0);
        // parse and pass the arguments somehow

        if (strcmp(cmd_line, "\0") == 0)
            continue;
        else if (sysexec_elf(path) == 0)
            printf("Unknown command\n");
    }
    return 0;
}

I know that shell code looks absolutely terrible but it should just return to it after the command, right?

Syscall implementation in ring 3

Code: Select all

int sysexec_elf(char *name)
{
    int res;
    asm volatile(
        "int $0x80"
        : "=a"(res)
        : "a"(2), "D"(name)
        : "memory");
    return res;
}

entry.asm (linked to every command file)

Code: Select all

bits 64
extern main
global _start

_start:
    call main
    
    mov rdi, rax    
    mov rax, 3
    int 0x80
    .dead_loop: ;in case if the syscall didn't work
        jmp .dead_loop

Please note that this project is on an early state of development and I'm a beginner! Every help is appreciated. If you need to see any other files just let me know, I'll post them.

[Octocontrabass]

Another important info is that my timer (PIC) doesn't work (worked until I decided to implement tasks) and I have to call the scheduler manually.

This might happen if you forget to set RFLAGS.IF in the new task's context before you switch to it, or if you forget to send an EOI to the interrupt controller before you switch tasks.

When I did some debug it turned out that some of the registers that should be saved during the context switch are overwritten by some random trash.

Did you remember to pass "-mno-red-zone" to your compiler?

Code: Select all

    switch_to_task(current_task->rsp, next_cr3);
    return (context_t *)current_task->rsp;

It looks like your schedule() function expects switch_to_task() to return, but it never will. Which function is wrong?

Code: Select all

void task_exit()
{
    current_task->state = TASK_ZOMBIE;
    asm volatile("int $0x20");
    while (1)
        asm volatile("hlt");
}

Why are you using a software interrupt in ring 0? You should be able to use ordinary function calls.

Code: Select all

switch_to_task:

Using interrupts to switch tasks is a common beginner mistake. The wiki has a pretty good example for how to build task switching without requiring interrupts. (But you can still switch tasks inside an interrupt handler if you want to switch tasks in response to an interrupt.)

Code: Select all

int sysexec_elf(char *name)
{
    int res;
    asm volatile(
        "int $0x80"
        : "=a"(res)
        : "a"(2), "D"(name)
        : "memory");
    return res;
}

Why are you using INT instead of SYSCALL?

[bomboclaat954]

whole switching sequence

This might happen if you forget to set RFLAGS.IF in the new task's context before you switch to it, or if you forget to send an EOI to the interrupt controller before you switch tasks.

I always set RFLAGS to 0x202 but the debug shows some other values (look at the screenshot). Also the timer is broken globally - I have timestamps in logs but they're always 0 (I guess it means that my kernel can't read the IRQ0 properly but I swear it worked perfectly until I started doing tasks).

Did you remember to pass "-mno-red-zone" to your compiler?

Yes, here are my compiling flags:

Code: Select all

CFLAGS =-m64 \
        -O2 \
        -pipe \
        -ffreestanding \
        -fno-stack-protector \
        -fno-stack-check \
        -fno-pie \
        -fno-PIC \
        -mno-80387 \
        -mno-mmx \
        -mno-red-zone \
        -mcmodel=kernel \
        -Iinclude \
        -march=x86-64 \
        -g

It looks like your schedule() function expects switch_to_task() to return, but it never will. Which function is wrong?

I changed the definition of switch_to_task() and added noreturn attribute:

Code: Select all

extern void switch_to_task(uintptr_t next_rsp, uintptr_t next_cr3) __attribute__((noreturn));

Why are you using a software interrupt in ring 0? You should be able to use ordinary function calls.

I changed task_exit():

Code: Select all

void task_exit(context_t *ctx)
{
    current_task->state = TASK_ZOMBIE;
    current_task->next->state = TASK_READY;
    kprintf("Exiting task %s, and switching to %s\n", current_task->name, current_task->next->name);
    schedule(ctx);
    while (1)
        asm volatile("hlt");
}

I changed my syscalls a bit (2 is task_create and 3 is task_exit):

Code: Select all

    case 2:
        char *name = (char *)r->rdi;
        int current_pid = current_task->pid;
        extern void *initramfs_base;
        uint64_t size = 0;
        void *file = initramfs_find_file(initramfs_base, name, &size);
        if (file == NULL)
            return 0;

        task_t *new_task = task_create(file, current_task->pid, name);
        if (new_task == NULL)
            return 0;

        new_task->parent_pid = current_pid;
        new_task->next = current_task;
        current_task->state = TASK_BLOCKED;
        new_task->state = TASK_READY;
        r->rax = 1;
        schedule(r);
        return (uint64_t)r;
    case 3:
        task_exit(r);
        while (1)
            asm volatile("hlt");

Why are you using INT instead of SYSCALL?

Because it was easier to write on the start but I will implement SYSCALL.

After the changes shown here, while switching tasks there's a page fault (look at the screenshot) but the debug note tells correct PID to switch (from 3 to 2). Any ideas what happened there?

[Octocontrabass]

I always set RFLAGS to 0x202 but the debug shows some other values (look at the screenshot).

It's normal for programs to change RFLAGS while they run. Why does your screenshot only show the lower 32 bits of each 64-bit register?

Code: Select all

        -mno-80387 \
        -mno-mmx \

Why aren't you using "-mgeneral-regs-only"?

I changed the definition of switch_to_task() and added noreturn attribute:

Why don't you want switch_to_task() to return to the caller? Normally it should return.

After the changes shown here, while switching tasks there's a page fault (look at the screenshot) but the debug note tells correct PID to switch (from 3 to 2). Any ideas what happened there?

Why does it look like RSP is the same for every task? Normally each task needs a separate ring 0 stack.