# F05: review
contributed by < `zodf0055980` >
###### tags: `Linux 核心設計`
## 第 2 週測驗題 測驗 3

#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 去省下指標的操作。此外這種方法也可以套用到函式上，下面做一個簡單的實做：

#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)就有這段

#define ATOMIC_INIT(i) { (i) }

便是使用 Compound literals 去進行附值。

## 第 3 週測驗題 (上) 測驗 1

#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。但這種方法容易有資料外洩的問題，如果我們利用這種一一比較的方式去比較密碼的話，我們可以利用函式執行時間去判斷密碼前面幾個正確，因此便可以利用這種方式去利用大量資料破解密碼。我下面做個測試:

#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; 
} 

若改用 constant-time 的比較
:::info
像是全錯或是只有第一個 char 正確
為何前幾次執行的時間特別高呢？
:::
觀察 [linux/lib/string.c](https://github.com/torvalds/linux/blob/master/lib/string.c) 中我們常用到的 strcmp 以及 strncmp

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。