# Linux OS: Project 2

<br>

## 1. Project Requirements

> In this lab, you need to implement a custom wait queue-like functionality in kernel space, allowing user applications to operate through the system call.

Implement a system call `call_my_wait_queue(int id)` . This function takes an argument `id` to determine which of the following two operations to perform:
1. Add a thread to the wait queue to wait
- If an error occurs, return `0`; on success, return `1`.
2. Remove threads from the wait queue, allowing them to exit
- If an error occurs, return `0`; on success, return `1`. The removal order must follow the FIFO (First In, First Out) principle.

<br><br>

## 2. Kernel Code Implementation

**TL;DR:**
> - 所有 thread 一開始都會依序卡在 `my_wait_queue` 中
> - `clean_wait_queue` 開始跑後，才一個個叫醒 thread
> - 每個 thread 都必須等到 global 變數 `is_resource_available` 為 `1` 才可結束

<br>

### 2.1 初始化
利用 `DECLARE_WAIT_QUEUE_HEAD` 定義一個 `my_wait_queue`。

定義一個 global 變數 `is_resource_available`，表示當前是否有資源可用。

---

### 2.2 enter_wait_queue
`enter_wait_queue()` 的內容是該 thread 開始運作時才會跑的。當其運作時：
1. 先將 `is_resource_available` 設為 `0`，代表資源正在被它使用
2. 利用 `wait_event_interruptible_exclusive()` 來卡住自己，直到有 resource 可用
3. 如果 2. 的結果是 0 代表成功（回傳 1），否則失敗（回傳 0）

備註：
- `interruptible` 令 thread 可以從外部透過 signal 叫醒
- `exclusive` 確保每次只能有一個 thread 在等待資源，其他一律要繼續睡

---

### 2.3 clean_wait_queue
`clean_wait_queue()` 則是先把 `is_resource_available` 設為 `1`，讓第一個 thread 可以動作。

`while` 迴圈會一個一個把 `my_wait_queue` 內的 thread 叫醒，直到 `my_wait_queue` 的下一個（`head.next`）等於第一個（`head`），清掉以後就結束，實現 FIFO。

<br><br><br>

## 3. Code

### 3.1 Kernel Code (`call_my_wait_queue.c`)

#include <linux/kernel.h>
#include <linux/syscalls.h>
#include <linux/wait.h>
#include <linux/delay.h>

DECLARE_WAIT_QUEUE_HEAD(my_wait_queue);

int is_resource_available = 0;

static int enter_wait_queue(void) {
    is_resource_available = 0;

    int is_interrupted = wait_event_interruptible_exclusive(my_wait_queue, is_resource_available);
    
    if (is_interrupted) return 0;
    else return 1;
}

static int clean_wait_queue(void) {
    is_resource_available = 1;

    while (my_wait_queue.head.next != &my_wait_queue.head) {
        wake_up_interruptible(&my_wait_queue);
        msleep(100);
    }
    
    return 1;
}

SYSCALL_DEFINE1(call_my_wait_queue, int, id) {
    switch (id) {
        case 1:
            enter_wait_queue();
            break;
        case 2:
            clean_wait_queue();
            break;
    }
    return 0;
}

### 3.2 User Code (`project2.c`)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/syscall.h>

#define NUM_THREADS 10

void * call_my_wait_queue(int id){
    return (void *)syscall(449, id);
};

void *enter_wait_queue(void *thread_id)
{
    fprintf(stderr, "enter wait queue thread_id: %d\n", *(int *)thread_id);

    /*
    // your syscall here
        syscall( xxx , 1);
    */
    call_my_wait_queue(1);

    fprintf(stderr, "exit wait queue thread_id: %d\n", *(int *)thread_id);
}
void *clean_wait_queue()
{
    /*
        // your syscall here 
        syscall( xxx , 2);
    */
    call_my_wait_queue(2);
}
int main()
{
    void *ret;
    pthread_t id[NUM_THREADS];
    int thread_args[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
        thread_args[i] = i;
        pthread_create(&id[i], NULL, enter_wait_queue, (void *)&thread_args[i]);
    }
    
    sleep(1);
    fprintf(stderr, "start clean queue ...\n");
    clean_wait_queue();
    
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(id[i], &ret);
    }
    
    return 0;
}

<br><br>

## 4. Compiling Steps
1. Create a folder `mycall` in the Linux kernel folder
2. Put the script `call_my_wait_queue.c` into `mycall`
3. Create a Makefile in the same directory, and put the following line:

    obj-y := call_my_wait_queue.o

3. In `/arch/x86/entry/syscalls`, add this line:

    449	common	call_my_wait_queue		sys_call_my_wait_queue

4. Run this custom shell script (in the Linux kernel folder, no `sudo` when calling)

    #! /bin/bash
    
    sudo make mrproper

    cp -v /boot/config-$(uname -r) .config
    make localmodconfig

    scripts/config --disable SYSTEM_TRUSTED_KEYS
    scripts/config --disable SYSTEM_REVOCATION_KEYS
    scripts/config --set-str CONFIG_SYSTEM_TRUSTED_KEYS ""
    scripts/config --set-str CONFIG_SYSTEM_REVOCATION_KEYS ""
    scripts/config --disable CONFIG_X86_32

    make -j$(nproc)
    sudo make modules_install -j$(nproc)
    sudo make install -j$(nproc)
    sudo update-grub

<br><br>

## 5. Results

**TL;DR: The threads get waken up in a FIFO manner.**

> 備註：Thread 的 scheduling 是由系統決定，不見得一定會按順序（見 Ref. 9 & 10）

### Trial 1:

### Trial 2:

### Trial 3:

<br><br>

## References
1. [Blocking I/O - Linux Device Drivers, Second Edition [Book]](https://www.oreilly.com/library/view/linux-device-drivers/0596000081/ch05s02.html#:~:text=A%20wait%20queue%20is%20exactly,wait_queue_head_t%20my_queue%3B%20init_waitqueue_head%20(%26my_queue)%3B)
1. [Delay and sleep mechanisms](https://www.kernel.org/doc/html/next/timers/delay_sleep_functions.html#c.fsleep)
1. [waitqueue_active(9) — linux-manual-4.8 - Debian](https://manpages.debian.org/jessie-backports/linux-manual-4.8/waitqueue_active.9.en.html)
1. [wait.h by Torvalds](https://github.com/torvalds/linux/blob/master/include/linux/wait.h)
1. [wait.c on bootlin](https://elixir.bootlin.com/linux/v5.15.137/source/kernel/sched/wait.c#L29)
1. [wait.h on bootlin](https://elixir.bootlin.com/linux/v5.15.137/source/include/linux/wait.h#L20)
1. [捋一下等待队列waitqueue - CSDN](https://blog.csdn.net/m0_37797953/article/details/118762796)
1. [内核--任务调度--等待 - CSDN](https://blog.csdn.net/yxfabcdefg/article/details/77503466)
1. [Why do these threads not execute in the same order as the code? - StackOverflow](https://stackoverflow.com/questions/61180142/why-do-these-threads-not-execute-in-the-same-order-as-the-code)
1. [Why don't these threads run in order? - StackOverflow](https://stackoverflow.com/questions/27282125/why-dont-these-threads-run-in-order)