lab0-c ideas

第三週課程直播

除法是一個高成本的操作，參考 第三周課堂問答 與 數值分析篇 提到的方法
比如用乘法先乘以很大的數再用向右位移

3/9直播

commit message 要考慮到，如果函式有機會使用到 q_new 之類的函式，那麼記憶體會怎麼處理，要寫出來

閱讀 分析「快慢指標」

快慢指標 v.s. 單一指標
這篇文章從組合語言分析了走訪鏈結串列使用快慢指標與單一指標的效能差別
從時間局部性來看，快指標走過的節點比較快被慢指標走過，相對於單一指標而言。快指標走過的節點被存進去快取後有可能直接再被慢指標存取，減少了快取替換，而單一指標可能有快取錯失。理論上快慢指標效能會比單一指標更好。
不過這是理論上，應該也需要經過實驗證實。

解析 2025 年「Linux 核心設計」第 2 次作業表單第六題

int x(int i, int k) {
return (i < k && putchar(i + '0') && !x(i + 1, k) || putchar(i + '0'); 
}

int main(){
    x(1, 3);
}

預期輸出 12321
運算規則：
&& 左式成立才執行右式，左式不成立則右式不執行
，OR 左式成立不執行右式，左式不成立才執行右式
putchar 回傳值根據 man ： putchar() return the character written as an unsigned char cast to an int or EOF on error.
呼叫第一次， i = 1 ，輸出 1 ，執行到遞迴，呼叫第二次， i = 2 ，輸出 2 ，執行到遞迴，呼叫第三次，這時 i = 3 不小於 k ，於是跳過 && 相連的第一次 putchar 和遞迴，執行第二次 putchar 輸出 3 然後回傳正值，經過 ! 轉換為負值後，因為 || 左式為負(非），執行右式輸出 2 ，接著同樣流程輸出 1 。
注意，因此 x 前面的 ! 很重要。因為 x 的回傳值一定是 true (由於 putchar 一定回傳非零值)，為確保會執行到這第二個 putchar，要將回傳值作 NOT，讓第一部份的結果為 false

dudect

為什麼要使用 t 檢定，不使用標準差就好。因為不知道分佈長什麼樣。

為什麼紀錄 cycle 而不是秒數。因為 cpu 會降頻，所以 cycle 和 instruction 比較有正相關。
現代處理器設計：原理和關鍵特徵

如何選擇剔除的百分比？剔除太多，可能讓非常數時間的也通過

解讀 lab0 讀取輸入的實作

在學校我學到使用 scanf, getc, gets 讀取來自 stdin 的輸入，送進 buffer ，我好奇在 lab0 是如何讀取 stdin 的？
在 lab0 ，不使用 scanf 等函數，如何藉由 linenoise
流程如下：

1. 判斷是否為 stdin 是否為 TTY (controlling terminal)
   stdin 可以透過設置改變。因此如果是的話，則呼叫 linenoise(prompt) 一次讀取一整行 terminal 輸入。否的話，則呼叫 console.c 中的 readline() 將讀取資料送進 rio_t 的結構。

將輸入結果經過 linenoise 處理特殊字元之後，回傳的是乾淨的字串，比如純粹的 "ih dolphin 1000"，沒有 \n 或 ctrl-d 之類的東西。
經過 console.c 的 parse_args() ，之後傳入 interpret_cmda() 呼叫 do_function()。
整個過程輸入被裝進 argv ，argv 並不是全域變數，而是透過參數與區域變數不斷在 function 間傳遞。

從程設 2 作業複習指標陣列

寫作業的時候，一開始想定義一連串指標指向許多個重複的結構體，當時我思索如何建立一個指標陣列 (array of pointers) ，只想到這樣的語法：

typedef struct {
  char *name;
  unsigned int price;
  unsigned int count;
} product;

// member products used as a pointer to first element of product array
typedef struct {
  char *date;
  product *products[MAX_PRODUCT];
  unsigned int num_product;
} record;

但想想覺得很不適合，於是只寫成 product *products; 後續使用 products 時必須以 sum += r->products[i].price * r->products[i].count; 這樣的形式。這樣的定義是 product 為一個指向 結構體 product 的指標，並且以這樣的形式分配時 product *products = malloc(n * sizeof(product)); ，記憶體的空間是用來放置結構體而非指標。並且指標指向該記憶體位址最小的地方，規格書如下，
7.22.3 Memory management functions

The pointer returned points to the start (lowest byte address) of the allocated
space.

後來想到方法是間接指標 product **products = malloc(n * sizeof(product *)); 這樣一來就達成一連串指標指向結構體。然而走到這才發現一開始的思維其實是錯的，因為真正存放資料的還是結構體本身，使用間接指標的方式僅僅分配記憶體給指標，仍然要一一分配每個記憶體給指標，反而更加麻煩：

for (int i = 0; i < n; i++) {
  p_array[i] = malloc(sizeof(product));
  // fill p_array[i]->price, etc.
}

使用 products[i] 時，編譯器會自動乘以 sizeof(product) ，所以每一個index會指向不同的結構體，所以原本的作法是直接分配記憶體給結構體，然後不以定義各別的指標，而是以第一個元素的位置往後推算來取得各個結構體的位址。

同時也讀到 calloc 可以用在初始化記憶體裡的值

The calloc function allocates space for an array of nmemb objects, each of whose size is size. The
space is initialized to all bits zero.

結構體最後一個可變大小陣列的成員

閱讀 lab0-c (B) 學到以下技巧：

typedef struct{
    char *birthday;
    record *records;
    unsigned int num_record;
    char name[0]; //technique: trailing array can be size changible
}user;

user *user = 
(user*)malloc(sizeof(user)+(name_len+1)*sizeof(char));

結構體中若想放置一個陣列，可將其至於結構體最後一個元素並宣告為長度為 0 的陣列，如此一來在分配結構體的記憶體空間時同時分配和定義該陣列的大小，不需要再另外呼叫一次 malloc。
該陣列必須是結構體最後一個元素，並且僅限於一個陣列，如果是兩個陣列將造成錯誤。因為陣列本質上是指向最小記憶體位置的指標，所以這技巧在兩個陣列的情況下，第二個陣列的指標事實上會與第一個陣列的指標相鄰，無法指向理想的位置。

// wrong
typedef struct{
    record *records;
    unsigned int num_record;
    char name[0]; //technique: trailing array can be size changible
    char birthday[0];
}user;

在 C99 之後，新增 char name[] 為合法的語法，因此也可以定義成未定空間。
然而這技巧被稱為 Struct Hack ，在後續程式碼擴增時會不好維護，因此要避免使用，在這篇文章最後提到幾個使用情境：

1. 使用flexible array member所宣告出來的陣列其記憶體空間是與其他的structure members的記憶體空間連續的 ，若該structure會被經常性的存取，則這樣的方式可以增加cache hit的機率 (基於Spatial locality的因素)
2. 某些自訂的資料結構就是規定該不定長度的空間就是得接續著其他的structure members
   如本篇文章最初所舉之romfs_super_block這個structure
   該name陣列 (為不定長度) 就是規定其記憶體空間得接在checksum變數之後
   

因此非必要還是不要使用 Struct Hack

os_random

從 quiz6

/* Generate an OS-specific random seed using ASLR and monotonic clock data.
 * Combines process identifiers and clock values to obtain a better seed.
 */
uintptr_t os_random(uintptr_t seed)
{
    uintptr_t x = (uintptr_t) &os_random ^ seed;
#if defined(__APPLE__)
    x ^= (uintptr_t) mach_absolute_time();
#else
    struct timespec time;
    clock_gettime(CLOCK_MONOTONIC, &time);
    x ^= (uintptr_t) time.tv_sec;
    x ^= (uintptr_t) time.tv_nsec;
#endif
    /* Do a few randomization steps */
    uintptr_t max = ((x ^ (x >> 17)) & 0x0F) + 1;
    for (uintptr_t i = 0; i < max; i++)
        x = random_shuffle(x);
    return x;
}

因 time() 回傳秒，容易預測。
uintptr_t x = (uintptr_t) &os_random ^ seed; 目的是利用 xor 的特性，將 x 變得平均分佈， seed 值代入的是 getpid
之後再用使用高精度的時間x ^= (uintptr_t) time.tv_nsec;

第六週課程直播

rop 攻擊本質是注入程式碼，藉由 buffer overflow, heap overflow

ARM 架構防範 rop，會藉由只使用 64 位元中的 39 或 48 位元來，linux kernel 也提供這樣的功能。
將指標的地址分成兩部份，一部分放簽章，另一部份放真正的地址。如果是注入的東西，他的地址就不包含簽章。
為什麼 rop 可以攻擊，因為 C 語言使用指標是很自然的，而rop 攻擊的根本是因為掌握記憶體位址。
還有 ASLR (位址空間布局隨機化)，可以將記憶體位置隨機放置，因此可以藉由取得函式，變數的位置作為亂數種子，看 lab0-c 的 os_random 實作

time(NULL)精度不夠

看到1hr:30min

不定個數參數的處理

#include <iostream>
#include <stdarg.h>

using namespace std;

void add(int a, ...){
    va_list num;
    int sum = 0, i;
    va_start(num, a);
    for (i = a; i >= 0; i = va_arg(num, int)){
        sum += i;
    }
    va_end(num);
    cout << sum << endl;
}

int main(){
    add(1);
    add(1, -1);
    add(2, 3, -1);
    add(-1, 1, 10, 100);
    add(100, 100, 100, 100, -1);
    cout << 'H' <<endl;
}

定義 va_list ， 呼叫 va_start 且第二個參數填入函式的最後一個參數（在此範例只有一個參數，因此最後一個也是第一個），接下來每次要使用下一個引數，就呼叫 va_arg 並定義型別然後它會回傳下一個引數的值。最後函式結束前要呼叫 va_end
如果呼叫 va_arg 次數超過引數數量，會導致回傳非預期的值（此函式沒有 index out of range 的檢查）。因此常見防範方法有以下三種：

1. Use of a printf or scanf-like format string with embedded specifiers that indicate argument types.
2. A sentinel value at the end of the variadic arguments.
3. A count argument indicating the number of variadic arguments.

範例藉由傳入 -1 跳出迴圈

Note: It is not required to read in all the arguments.