# F05: review contributed by < `zodf0055980` > ###### tags: `Linux 核心設計` ## 第 2 週測驗題 測驗 3 ```clike= #include <stdio.h> #define cons(x, y) (struct llist[]){x, y} struct llist { int val; struct llist *next; }; int main() { struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL)))); struct llist *p = list; for (; p; p = p->next) printf("%d", p->val); printf("\n"); return 0; } ``` 會選擇這題是因為第一次看到這種技巧，這種技巧為 Compound literals，在 C99 中的 6.5.2.5 有講述 Compound literals 的行為。 `The type name shall specify an object type or an array of unknown size, but not a variable length array type.` 可看到它可以對未知大小的矩陣做初始話的動作。因此可以利用 Compound literals 去省下指標的操作。此外這種方法也可以套用到函式上，下面做一個簡單的實做： ```clike= #include <stdio.h> struct S { int x, y; }; void prints(struct S p) { printf("%d, %d", p.x, p.y); } int main() { prints((struct S){2, 3}); return 0; } ``` 執行這個程式可以看到結果是` 2, 3` 因此題目中的`struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL))));` 其實可以解讀成 `list->val = 9; list->next = cons(5, cons(4, cons(7, NULL)))) `再依此往下帶入 最後會形成 head->9->5->4->7->NULL 的 linklist。 這種方法在 linux kernel 也時常看見，例如在 [linux/arch/sh/include/asm/atomic.h](https://github.com/torvalds/linux/blob/7796916146b8c34cbbef66470ab8b5b28cf47e83/arch/sh/include/asm/atomic.h)就有這段 ```clike= #define ATOMIC_INIT(i) { (i) } ``` 便是使用 Compound literals 去進行附值。 ## 第 3 週測驗題 (上) 測驗 1 ```clike #include <stdint.h> #include <stddef.h> int memcmp(const uint8_t *m1, const uint8_t *m2, size_t n) { for (size_t i = 0; i < n; ++i ) { int diff = m1[i] - m2[i]; if (diff != 0) return (diff < 0) ? -1 : +1; } return 0; } ``` 這種寫法是去一一筆比較每一個記憶體位置看是否相符，一遇到不相符就回傳 -1 或 1。但這種方法容易有資料外洩的問題，如果我們利用這種一一比較的方式去比較密碼的話，我們可以利用函式執行時間去判斷密碼前面幾個正確，因此便可以利用這種方式去利用大量資料破解密碼。我下面做個測試: ```clike #include <stdio.h> #include <stdint.h> #include <stddef.h> #include <time.h> int memcmp(const uint8_t *m1, const uint8_t *m2, size_t n) { for (size_t i = 0; i < n; ++i ) { int diff = m1[i] - m2[i]; if (diff != 0) return (diff < 0) ? -1 : +1; } return 0; } static int diff_in_ns(struct timespec t1, struct timespec t2) { struct timespec diff; if (t2.tv_nsec - t1.tv_nsec < 0) { diff.tv_sec = t2.tv_sec - t1.tv_sec - 1; diff.tv_nsec = t2.tv_nsec - t1.tv_nsec + 1000000000; } else { diff.tv_sec = t2.tv_sec - t1.tv_sec; diff.tv_nsec = t2.tv_nsec - t1.tv_nsec; } return (diff.tv_sec * 1000000000 + diff.tv_nsec); } int main() { char *password = "ABCDEFGHIJKLMNOPQRSTUV"; char error[23][23] = { "XXXXXXXXXXXXXXXXXXXXXX", "AXXXXXXXXXXXXXXXXXXXXX", "ABXXXXXXXXXXXXXXXXXXXX", "ABCXXXXXXXXXXXXXXXXXXX", "ABCDXXXXXXXXXXXXXXXXXX", "ABCDEXXXXXXXXXXXXXXXXX", "ABCDEFXXXXXXXXXXXXXXXX", "ABCDEFGXXXXXXXXXXXXXXX", "ABCDEFGHXXXXXXXXXXXXXX", "ABCDEFGHIXXXXXXXXXXXXX", "ABCDEFGHIJXXXXXXXXXXXX", "ABCDEFGHIJKXXXXXXXXXXX", "ABCDEFGHIJKLXXXXXXXXXX", "ABCDEFGHIJKLMXXXXXXXXX", "ABCDEFGHIJKLMNXXXXXXXX", "ABCDEFGHIJKLMNOXXXXXXX", "ABCDEFGHIJKLMNOPXXXXXX", "ABCDEFGHIJKLMNOPQXXXXX", "ABCDEFGHIJKLMNOPQRXXXX", "ABCDEFGHIJKLMNOPQRSXXX", "ABCDEFGHIJKLMNOPQRSTXX", "ABCDEFGHIJKLMNOPQRSTUX", "ABCDEFGHIJKLMNOPQRSTUV", }; FILE *fp = fopen("time.txt", "wb+"); int i; for (i=0; i<22; i++) { char *com = &error[i][0]; struct timespec start, end; clock_gettime(CLOCK_REALTIME, &start); int get = memcmp(com,password, 23); clock_gettime(CLOCK_REALTIME, &end); fprintf(fp, "%d %d\n", i, diff_in_ns(start, end)); } return 0; } ``` ![](https://i.imgur.com/tFNgUDl.png) 若改用 constant-time 的比較 ![](https://i.imgur.com/lsObL0d.png) :::info 像是全錯或是只有第一個 char 正確 為何前幾次執行的時間特別高呢？ ::: 觀察 [linux/lib/string.c](https://github.com/torvalds/linux/blob/master/lib/string.c) 中我們常用到的 strcmp 以及 strncmp ```clike int strcmp(const char *cs, const char *ct) { unsigned char c1, c2; while (1) { c1 = *cs++; c2 = *ct++; if (c1 != c2) return c1 < c2 ? -1 : 1; if (!c1) break; } return 0; } int strncmp(const char *cs, const char *ct, size_t count) { unsigned char c1, c2; while (count) { c1 = *cs++; c2 = *ct++; if (c1 != c2) return c1 < c2 ? -1 : 1; if (!c1) break; count--; } return 0; } ``` 可以發現都不是使用 constant-time。