2022q1 Homework5 (quiz8)

contributed by < leewei05 >

測驗 1

完整程式碼

memchr_opt 初步理解為以下：

注意用詞:

• bit 的翻譯是「位元」
• byte 的翻譯是「位元組」

尊重資訊科技前輩的篳路藍縷，儘量使用傳統詞彙。
jserv

首先會判斷帶入的字串長度是否比 8 個位元組還要長，如果比 8 個位元組還短即比對各個位元組 (byte) 搜尋指定的 char。如果比字串比 8 個位元組還要長，那就會進入 if (!TOO_SMALL(length)) 的判斷式。

與其一個位元組接著一個位元組比對，memchr 會根據 unsigned char d (欲搜尋的字元) 製作一個 8 個位元組的 bytemask。

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 (UNALIGNED(src)) {
        if (!length--)
            return NULL;
        if (*src == d)
            return (void *) src;
        src++;
    }

    if (!TOO_SMALL(length)) {
        /* If we get this far, we know that length is large and
         * src is word-aligned.
         */

        /* The fast code reads the source one word at a time and only performs
         * the bytewise search on word-sized segments if they contain the search
         * character, which is detected by XORing the word-sized segment with a
         * word-sized block of the search character and then detecting for the
         * presence of NULL in the result.
         */
        unsigned long *asrc = (unsigned long *) src;
        unsigned long mask = d << 8 | d;
        mask = mask << 16 | mask;
        for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
            mask = (mask << i) | mask;

        while (length >= LBLOCKSIZE) {
            // check if char matches
            if (DETECT_CHAR(*asrc, mask)) {
                // if yes, check char one by one until we find the char
                src = (unsigned char *) asrc;
                while (length--) {
                    if (*src == d)
                        return (void *) src;
                    src++;
                }
            }
            // if no char matches, reduce length by LBLOCKSIZE
            length -= LBLOCKSIZE;
            // move forward by LBLOCKSIZE because there were no matching
            // charater in this block
            asrc += 1;
            // check if source array is shorter than LBLOCKSIZE
            if (DETECT_NULL(*asrc))
                break;
        }

        /* If there are fewer than LBLOCKSIZE characters left, then we resort to
         * the bytewise loop.
         */
        src = (unsigned char *) asrc;
    }

    while (length--) {
        if (*src == d)
            return (void *) src;
        src++;
    }

    return NULL;
}

int main()
{
    const char str[] = "http://wiki.csie.ncku.edu.tw";
    const char ch = '.';
    const char str2[] = "http://wiki.csie.ncku.edu.tw";
    const char ch2 = 'p';
    const char str3[] = "http://wiki.csie.ncku.edu.tw";
    const char ch3 = 'u';

    char *ret = memchr_opt(str, ch, strlen(str));
    printf("String after |%c| is - |%s|\n", ch, ret);
    char *ret2 = memchr_opt(str2, ch2, strlen(str2));
    printf("String after |%c| is - |%s|\n", ch2, ret2);
    char *ret3 = memchr_opt(str3, ch3, strlen(str3));
    printf("String after |%c| is - |%s|\n", ch3, ret3);
    return 0;
}

執行結果如下：

String after |.| is - |.csie.ncku.edu.tw|
String after |p| is - |p://wiki.csie.ncku.edu.tw|
String after |u| is - |u.edu.tw|

除錯過程

一開始很快就 parse 出 .，但加了另外兩個 case 發現都會回傳 NULL。透過 gdb 檢查之後發現這行寫錯了。原本是要位移一個 pointer to long，但一開始寫的版本是取回一個位元組，所以才會出錯。也因為為了熟悉 gdb 的關係，花了不少時間，但學會使用 gdb 除錯真的節省不少時間以及排除用感覺寫程式的壞習慣。

// WRONG
*asrc = *asrc + 8;

// CORRECT
asrc += 1;

---

測驗 2

---

測驗 3

• 列出完整且有效的 periodic_routine 函式程式碼，並附上註解
• 解釋上述程式碼運作原理，應探討 Linux 核心內部 ptrace 系統呼叫和 signal 的實作方式
• 研讀 The race to limit ptrace 一類的材料，探討行程避免被追蹤的手法

完整程式碼

理解並實作程式碼

首先從核心模組的 init function 開始看起。查閱 Linux Kernel 原始碼，dont_trace_init 基本上就是建立一個 work queue，並且設定 work queue 的延遲時間(1 Jiffy)。

exit function 則是停止 work queue 的 routine 並清除先前定義的 work queue。

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");
}

除了 periodic_routine 以外需要實作，其他四個函式分別為：

• kill_task: 刪除 Kernel space 的行程
• is_tracer: 判斷行程是否有追蹤其他行程
• kill_tracee: 刪除所有 tracer 追蹤的行程
• check: 檢查所有的行程的 ptraced，也就是追蹤的行程。如果 is_tracer 返回 true，則刪除所有追蹤行程以及該行程。

/*
	 * 'ptraced' is the list of tasks this task is using ptrace() on.
	 *
	 * This includes both natural children and PTRACE_ATTACH targets.
	 * 'ptrace_entry' is this task's link on the p->parent->ptraced list.
	 */
	struct list_head		ptraced;

首先，likely 巨集是由 gcc extension __builtin_expect 組成。此用途是可提示編譯器產生對 branch predictor 友善的程式碼，因為工程師可以透過 __builtin_expect 來告知編譯器 !!(x) == 1 的機率很大，也就是 x 很可能為 1。!! 是確保 !!(x) 的結果一定為 0 或是 1。

6.5.3.3 Unary arithmetic operators
The result of the logical negation operator ! is 0 if the value of its operand compares
unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int.
The expression !E is equivalent to (0==E)

# define likely(x)	__builtin_expect(!!(x), 1)

什麼時候需要會需要執行 check()? A: 掛載核心模組的時候。
可以使用 init function 所定義的 loaded = true;，因為大部分的時間 loaded == true。

static void periodic_routine(struct work_struct *ws)
{
    // check each process if dont_trace module is loaded
    if (likely(loaded))
        check();
    // run work task again after JIFFIES_DELAY
    schedule_delayed_work(&dont_trace_task, JIFFIES_DELAY);
}

測試程式碼

# 確認沒有掛載模組
$ lsmod | grep dont

# 編譯模組
$ make
make -C /lib/modules/`uname -r`/build M=quiz3 modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-39-generic'
  CC [M]  quiz3/dont_trace.o
  MODPOST quiz3/Module.symvers
  CC [M]  quiz3/dont_trace.mod.o
  LD [M]  quiz3/dont_trace.ko
  BTF [M] quiz3/dont_trace.ko
Skipping BTF generation for quiz3/dont_trace.ko due to unavailability of vmlinux
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-39-generic'

$  yes >/dev/null &
[1] 21169

$ sudo gdb -q --pid=`pidof yes`
Attaching to process 21169
Reading symbols from /usr/bin/yes...
(No debugging symbols found in /usr/bin/yes)
Reading symbols from /lib/x86_64-linux-gnu/libc.so.6...
Reading symbols from /usr/lib/debug//lib/x86_64-linux-gnu/libc-2.31.so...
Reading symbols from /lib64/ld-linux-x86-64.so.2...
(No debugging symbols found in /lib64/ld-linux-x86-64.so.2)
0x00007f399da860a7 in __GI___libc_write (fd=1, buf=0x555c63a3b510, nbytes=8192) at ../sysdeps/unix/sysv/linux/write.c:26
26      ../sysdeps/unix/sysv/linux/write.c: No such file or directory.
(gdb) signal SIGINT
Continuing with signal SIGINT.

Program terminated with signal SIGINT, Interrupt.
The program no longer exists.
(gdb) quit
[1]+  Interrupt               yes > /dev/null

$ make load
sudo insmod dont_trace.ko

$ lsmod | grep dont
dont_trace             16384  0

$ yes >/dev/null &
[1] 21450

$ sudo gdb -q --pid=`pidof yes`
Attaching to process 21450
[1]+  Killed                  yes > /dev/null
Killed

$make unload
sudo rmmod dont_trace

Ptrace (process trace) & signal

當一個行程追蹤了另一個行程，被追蹤的行程 (tracee) 需要成為追蹤行程 (tracer) 的子行程，tracer 擁有 tracee 的控制權，包括設定 break point，檢視 tracee 的記憶體位址，攔截系統呼叫等等。GDB 即是透過 ptrace 實現上述的功能。

Ptrace 的限制

• Ptrace 沒有符合 POSIX 標準，在每個平台的實作方式都不同
• 為了追蹤某一個行程，tracer 一定要是 tracee 的父行程

參考文件

Ptrace manual
Intercepting and Emulating Linux System Calls with Ptrace
Ptrace, Utrace, Uprobes: Lightweight, Dynamic Tracing of User Apps