# 2022-04-04
>contributed by < `happyjack91630` >
>[happyjack91630 GitHub](https://github.com/happyjack91630/2022_Q1W8)

### 測驗 `1`

利用上述 SIMD within a register (SWAR) 的技巧，我們可改寫為以下 `memchr_opt` 函式:

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

/* Nonzero if either X or Y is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))

/* How many bytes are loaded each iteration of the word copy loop */
#define LBLOCKSIZE (sizeof(long))

/* Threshhold for punting to the bytewise iterator */
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)

#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) -0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) (((X) -0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif

/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, MASK) (DETECT_NULL(X ^ MASK))

void *memchr_opt(const void *src_void, int c, size_t length)
{
    const unsigned char *src = (const unsigned char *) src_void;
    unsigned char d = c;
    
    /* 以下 while 是要將 src 起始地址跟 long size 對齊 */
    while (UNALIGNED(src)) {
        if (!length--)
            return NULL;
        if (*src == d)
            return (void *) src;
        src++;
    }
    /* 如果我們要找的 length 都比一個 word 還要小，就不用進入 if 裡面了 */
    if (!TOO_SMALL(length)) {
        unsigned long *asrc = (unsigned long *) src;
        /* src 原本是以 unsigned char 的角度來看，現在改成 unsigned long 來看 */
        unsigned long mask = d << 8 | d;
        mask = mask << 16 | mask;
        for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
            mask = (mask << i) | mask;
        /* 將我們要找的 target d 轉換成一個 word size 的 mask。
         * e.g. d = 46 , mask = 46464646
         */
        while (length >= LBLOCKSIZE) {
            /* DETECT_CHAR if return 0 => 此次 asrc 的 word size 沒有 target c ， 
             *             就將 asrc++ 且 length 減一個word size。
             *             else return != 0，代表此次的 asrc 裡有存在的 target c，
             *             就將while break
            */
            if(!DETECT_CHAR(*asrc, mask)){   
                asrc++;
                length-=LBLOCKSIZE;
            }
            else{
                break;
            }
        }
        src = (unsigned char *) asrc;
    }
    while (length--) {
        if (*src == d)
            return (void *) src;
        src++;
    }
    return NULL;
}

### 測驗 `3`

ptrace 系統呼叫允許一個追蹤者 (tracer) 行程得以觀察或控制另外一個受追蹤者 (tracee) 行程的內容（如記憶體或暫存器）或執行流程。這主要用來實作除錯器 (debugger) 與系統呼叫的追蹤。使用這個系統呼叫之後，被追蹤者必須依附 (attach) 於追蹤者行程。該 attach 行為是以執行緒為單位，也就是說，在一個具備多個執行緒的行程中，其中每個執行緒都可個別 attach 在不同的追蹤者行程，或在其他執行緒被追蹤時，維持原本的執行流程。

`dont_trace` 這個 Linux 核心模組利用 `task_struct` 內部成員 ptrace 來偵測給定的行程是否被除錯器或其他使用 ptrace 系統呼叫的程式所 attach，一旦偵測到其他行程嘗試追蹤該行程，`dont_trace` 就會主動 `kill` 追蹤者行程。流程:

* Once any process starts “ptracing” another, the tracee gets added into ptraced that’s located in `task_struct`, which is simply a linked list that contains all the tracees that the process is “ptracing”.
* Once a tracer is found, the module lists all its tracees and sends a `SIGKILL` signal to each of them including the tracer. This results in killing both the tracer and its tracees.
* Once the module is attached to the kernel, the module’s “core” function will run periodically through the advantage of workqueues. Specifically, the module runs every `JIFFIES_DELAY`, which is set to 1. That is, the module will run every one jiffy. This can be changed through modifying the macro `JIFFIES_DELAY` defined in the module.

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

#include <linux/list.h>
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/sched/signal.h>
#include <linux/workqueue.h>

MODULE_AUTHOR("National Cheng Kung University, Taiwan");
MODULE_LICENSE("Dual BSD/GPL");
MODULE_DESCRIPTION("A kernel module that kills ptrace tracer and its tracees");

#define JIFFIES_DELAY 1
#define DONT_TRACE_WQ_NAME "dont_trace_worker"

static void periodic_routine(struct work_struct *);
static DECLARE_DELAYED_WORK(dont_trace_task, periodic_routine);
static struct workqueue_struct *wq;
static bool loaded;

/* Send SIGKILL from kernel space */
static void kill_task(struct task_struct *task)
{
    send_sig(SIGKILL, task, 1);
}

/* @return true if the process has tracees */

static bool is_tracer(struct list_head *children)
{
    struct list_head *list;
    list_for_each (list, children) {
        struct task_struct *task =
            list_entry(list, struct task_struct, ptrace_entry);
        /* 檢查此 task 的 ptraced 裡，有沒有 ptrace_entry 的空間
         * ，有的話就代表此 task 為 tracer 
         */
        if (task)
            return true;
    }
    return false;
}

/* Traverse the element in the linked list of the ptraced proccesses and
 * finally kills them.
 */
static void kill_tracee(struct list_head *children)
{
    struct list_head *list;
    list_for_each (list, children) {
        struct task_struct *task_ptraced =
            list_entry(list, struct task_struct, ptrace_entry);
        pr_info("ptracee -> comm: %s, pid: %d, gid: %d, ptrace: %d\n",
                task_ptraced->comm, task_ptraced->pid, task_ptraced->tgid,
                task_ptraced->ptrace);
        kill_task(task_ptraced);
    }
}

/* 檢查有無tracer，如果有的話就將tracer裡的linked-list ptraced刪掉，
 * 最後再將tracer刪掉
 */ 
static void check(void)
{
    struct task_struct *task;
    for_each_process (task) {
        if (!is_tracer(&task->ptraced))
            continue;

        kill_tracee(&task->ptraced);
        kill_task(task); /* Kill the tracer once all tracees are killed */
    }
}

static void periodic_routine(struct work_struct *ws)
{
    /* loaded = True，有進入此核心模組
     * loaded = False，沒有進入此核心模組
     */
    if (likely(loaded))
        check();
    /*the module runs every JIFFIES_DELAY, which is set to 1. 
     * That is, the module will run every one jiffy
     */
    queue_delayed_work(wq, &dont_trace_task, JIFFIES_DELAY);
}

static int __init dont_trace_init(void)
{
    wq = create_workqueue(DONT_TRACE_WQ_NAME);
    queue_delayed_work(wq, &dont_trace_task, JIFFIES_DELAY);

    loaded = true;
    pr_info("Loaded!\n");
    return 0;
}

static void __exit dont_trace_exit(void)
{
    loaded = false;

    /* No new routines will be queued */
    cancel_delayed_work(&dont_trace_task);

    /* Wait for the completion of all routines */
    flush_workqueue(wq);
    destroy_workqueue(wq);

    pr_info("Unloaded.\n");
}

module_init(dont_trace_init);
module_exit(dont_trace_exit);