2024q1 Homework 5 (Assessment)

contributed by < otteryc >

閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發

閱讀心得

這一系列的文章讓我印象最深的一句話應該是製冰機的障礙，以及作者父親在知道作者本人在做的事情之後訓斥怎麼沒有早點跟他講的部分。
製冰機帶給我的體悟就是當在資本上尚屬於充足的話，如果可以用金錢解決的問題，就盡量不要重造輪子，尤其是所處理的事務並非自己專業的狀況下。在這個例子中，製冰機尚不致於完全不能購買的程度。過度小心翼翼的降低成本，不夠大膽反而會使挑戰失敗。

課程問題

在閱讀 sort_mod.c 的過程中，發現在 sort_read 函式內，第 28 、 29 行的 early-return 可能有造成 sort_buffer 所指向的記憶體空間發生記憶體洩漏的疑慮。但是 User Mode Linux 似乎不能搭配 Valgrind 進行分析，不知道除了重編 Kernel 並選取 KMEMLEAK 工具以外，有沒有不需要重新編譯 Kernel 的方式？

































static ssize_t sort_read(struct file *file,
                         char *buf,
                         size_t size,
                         loff_t *offset)
{
    unsigned long len;
    size_t es;

    void *sort_buffer = kmalloc(size, GFP_KERNEL);
    if (!sort_buffer)
        return 0;

    /* FIXME: Requiring users to manually input data into a buffer for read
     * operations is not ideal, even if it is only for testing purposes.
     */
    len = copy_from_user(sort_buffer, buf, size);
    if (len != 0)
        return 0;

    /* TODO: While currently designed to handle integer arrays, there is an
     * intention to expand the sorting object's capability to accommodate
     * various types in the future.
     */
    es = sizeof(int);
    sort_main(sort_buffer, size / es, es, num_compare);

    len = copy_to_user(buf, sort_buffer, size);
    if (len != 0)
        return 0;

    kfree(sort_buffer);
    return size;
}

希望投入的專案

mm/ksm

在閱讀涂老師利用 GPU 加速 Kernel Samepage Merging 論文[1]之後，我對於 ksmd 相關的議題感到興趣。在該篇論文中，提到透過 ksmd 呼叫 KGPU 仍需交由 userspace 的 KGPU helper 以及 CUDA runtime，最後才會交由 GPU 進行雜湊運算。由於進行了多次的資料移動，使得整體運算成本不容小覷。
此外，在 linux v6.8 中，加入了 ksm advisor 機制，希望可以在本課程的專案中，加以研究。

[1] Wei-Cheng Lin, Chia-Heng Tu, Chih-Wei Yeh and Shi-Hao Hung, "GPU acceleration for Kernel Samepage Merging," 2017 IEEE 23rd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), Hsinchu, Taiwan, 2017, pp. 1-6, doi: 10.1109/RTCSA.2017.8046334.

撰寫 LKMPG 的 Rust 核心模組

https://www.kernel.org/doc/html/latest/dev-tools/kasan.html + vng (virtme-ng)

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// branchless
unsigned min_comp(unsigned a, unsigned b) {
  int tmp = -(a < b);
  unsigned mask = *(unsigned *)&tmp;
  return b ^ ((a ^ b) & mask);
}

// branchless, no comparison operator
unsigned min(unsigned a, unsigned b) {
  unsigned c = a - b;
  unsigned mask =
      -((~a & c) | (~a & b) | (b & c) >> (sizeof(unsigned) * 8 - 1));
  return a ^ ((a ^ b) & mask);
}

// branchless, signed integer
signed s_min(signed a, signed b) {
  signed c = a - b;
  signed mask =
      -!!((~a & ~c) | (~a & b) | (b & ~c) >> (sizeof(signed) * 8 - 1));
  return a ^ ((a ^ b) & mask);
}

int main(int argc, char **argv) {
  unsigned a = atoll(argv[1]), b = atoll(argv[2]);
  printf("a = %u, b = %u\n", a, b);
  unsigned expected = a > b ? b : a;
  assert(min_comp(a, b) == expected);
  assert(min(a, b) == expected);
}

https://hackmd.io/@sysprog/binary-representation
不使用比較運算子
TODO: 探討 signed vs. unsigned 的 branchless

試著從無號數

a

b

的

M S B_{a}

M S B_{b}

以及

M S B_{a - b}

中找出規律，並用卡諾圖化簡：

$M S B_{a}$	$M S B_{b}$	$M S B_{a - b}$	Unsigned	Signed
0	0	0	$a > b$	$a > b$
0	0	1	$b > a$	$b > a$
0	1	0	$b > a$	$a > b$
0	1	1	$b > a$	$a > b$
1	0	0	$a > b$	$b > a$
1	0	1	$a > b$	$b > a$
1	1	0	$a > b$	$a > b$
1	1	1	$b > a$	$b > a$

上表是考量無號數 underflow 之後的狀況。於有號數時，需要考量正數減負數時發生 overflow 以及負數減正數發生 underflow 的狀況，但又因為有正負之分，以兩者之間的正負關係判斷即可，不受 INT32_MIN <= (a - b) <= INT32_MAX 的限制。
值得注意的是，根據 ISO9899:1999 6.5.7.5 ，對於有號數進行 right shift 時，其結果為 implementation-defined ，所以， s_min 函式中， mask 要先進行兩次 Boolean Negate 再取負值，否則會產生可移植性問題。

C99
The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of
$\frac{E 1}{2^{E 2}}$ . If E1 has a signed type and a negative value, the resulting value is implementation-defined.

KSM -> cloud / KVM
cgroups
fastpath, slowpath
PSI (pressure)

oom
Rust
cargo

C + GNU make => rules / target

2024q1 Homework 5 (Assessment)

閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發

閱讀心得

課程問題

希望投入的專案

mm/ksm

撰寫 LKMPG 的 Rust 核心模組

Read more

民法物權編

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz 3+4)

2024q1 Homework2 (quiz1+2)