Try   HackMD

2024q1 Homework1 (lab0)

contributed by < Grace258 >

Reviewed by HenryChaing

可以再詳閱課程教材補充背景知識,指標觀念可以再補強。
其餘的 review 在底下有留言

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
    CPU family:          6
    Model:               166
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            0
    CPU max MHz:         4700.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3199.92

在終端機執行 export LC_ALL=C 並執行上述命令,可得到英語的輸出訊息,原本中文訊息用語不精準。

指定的佇列操作

請附上 commit 紀錄,以及 github repository 連結, 你的 github
HenryChaing

q_new

建立一個的 struct list_head * ,如果沒有足夠空間配置的話,回傳 NULL
如果有成功配置空間,將其初始化成符合環狀雙向鏈結串列的 head 指標。

我們要請求配置 struct list_head 的記憶體空間,成功的話指標會指向剛才配置成功的空間。
HenryChaing

q_free

list_for_each_safe (current, next_node, head) {
    element_t *node = list_entry(current, element_t, list);
    list_del(current);
    q_release_element(node);
}
free(head);

因為要刪除 current 所在的節點,所以使用定義在 list.hlist_for_each_safe 走訪所有的節點,讓 next_node 記住 current 要移動到的下一個位置,最後再刪除剩下的 head 指標。

head 指標並沒有被刪除,我們做的是釋放 head 所指向的記憶體空間,參閱: 課程教材
HenryChaing

q_insert_head

element_t *new_element = malloc(sizeof(element_t));
new_element->value = malloc(strlen(s) + 1);

strncpy(new_element->value, s, strlen(s) + 1);
list_add(&new_element->list, head);

將要插入到 head 的字串 selement_t 將其存取,因為 element_t 才是鏈結串列節點的資料型態,因為 snew_element->value 都是指標,因此要用 strncpy 來複製,因為對指標使用 是指向的意思。

指標也是紀錄資料,但是紀錄的是記憶體位置,因此

= 依舊是賦予數值的作用 。
HenryChaing

改進你的漢語表達。

q_insert_tail

element_t *new_element = malloc(sizeof(element_t));
new_element->value = malloc(strlen(s) + 1);

strncpy(new_element->value, s, strlen(s) + 1);
list_add_tail(&new_element->list, head);

操作原理和 q_insert_head 相似,差別在於使用 list_add_tail 將節點插到最後面。

將節點插入串列尾端。
HenryChaing

q_remove_head

struct list_head *first = head->next;
element_t *first_element = list_entry(first, element_t, list);

strncpy(sp, first_element->value, bufsize);
list_del(first);

避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。

建立一個指標 first 指向鏈結串列中的第一個節點,建立一個 element_t 來取得要移除的節點的字串,將字串內容複製到 sp 中,並且要注意字串的最後是 \0 因此長度是字母數量 +1

字串長度+1較恰當,電腦科學用語中字元才是單位量詞。
HenryChaing

q_remove_tail

struct list_head *last = head->prev;
element_t *last_element = list_entry(last, element_t, list);

strncpy(sp, last_element->value, bufsize);
list_del(last);

操作原理和 q_remove_head 相似,差別在於指標一開始是指向鏈結串列的最後一個節點。

q_size

list_for_each (current, head) {
    count++;
}

使用 list_for_each 走訪每一個節點,用 count 來計算走過得節點數量。

q_delete_mid

list_for_each (fast, head) {
    fast = fast->next;
    slow = slow->next;
    if (fast == head)
        break;
}
list_del(slow);

element_t *deleted_element = list_entry(slow, element_t, list);
if (deleted_element->value != NULL) {
    free(deleted_element->value);
}
free(deleted_element);

使用 list_for_each 和快慢指標走訪, fast 一次走兩個節點, slow 一此走一個節點,當 fast 走完整個 list 後,就代表 slow 已經走到中間的節點,此時將其刪除,刪除不同於移除,需要釋放記憶體空間。

q_delete_dup

bool last_check = false;
list_for_each_safe (current, next_node, head) {
    element_t *nodeA = list_entry(current, element_t, list);
    element_t *nodeB = list_entry(next_node, element_t, list);

    if (next_node != head && strcmp(nodeA->value, nodeB->value) == 0) {
            last_check = true;
            list_del(current);
            q_release_element(nodeA);
    } 
    else if (last_check) {
            last_check = false;
            list_del(current);
            q_release_element(nodeA);
    }
}

要刪除所有重複的節點(包含當前的節點),因此會用到一個 boolflag last_check 可以用來檢查當前節點是否是要刪除的最後一個節點,因為是 delete 所以會用到 q_release_element 來釋放記憶體空間。

q_swap

q_reverseK(head, 2);

相鄰的兩個節點互換其實就是以 2 為單位反轉節點,因此可以直接使用 q_reverseK

q_reverse

list_for_each_safe (current, next_node, head) {
    list_move(current, head);
    current = next_node;
}

這裡的想法是走訪每一個節點,並將當前節點移至 list 的最前面。

q_reverseK

INIT_LIST_HEAD(&start);
end = head;

list_for_each_safe (current, next_node, head) {
    count++;
    if (count == k) {
        list_cut_position(&start, end, current);
        q_reverse(&start);
        list_splice_init(&start, end);
        count = 0;
        end = next_node->prev;
    }
}

先初始化一個指標 start 用來標示 group K 的第一個節點,在反轉之後將其接到 group K 的下一個節點的前面。

q_sort

merge_sort(head);
    if (descend)
        q_reverse(head);

listmerge sort ,因為我寫的 merge sort 是上升排序,所以如果descend 為真,要對整個 list 做反轉。

q_ascend

list_for_each_entry_safe (current, next_node, head, list) {
    element_t *scan = list_entry(&next_node->list, element_t, list);
    while (&scan->list != head) {
        if (strcmp(scan->value, current->value) < 0) {
            list_del(&current->list);
            q_release_element(current);
            break;
        }
        scan = list_entry(scan->list.next, element_t, list);
    }
}

用兩個迴圈走訪節點,當內圈迴圈走訪到的節點小於外圈迴圈所在的節點時,表示此時的 list 不是上升排序,因此要刪除外圈迴圈的當前節點。

撰寫出更精簡的程式碼。

q_descend

list_for_each_entry_safe (current, next_node, head, list) {
    element_t *scan = list_entry(&next_node->list, element_t, list);
    while (&scan->list != head) {
        if (strcmp(scan->value, current->value) > 0) {
            list_del(&current->list);
            q_release_element(current);
            break;
        }
        scan = list_entry(scan->list.next, element_t, list);
    }
}

操作和 q_ascend 相似,差別在於刪除節點的時機是當內圈迴圈走訪到的節點大於外圈迴圈所在的節點時。

q_merge

queue_contex_t *m_queue = list_entry(head->next, queue_contex_t, chain);
queue_contex_t *node;
list_for_each_entry (node, head->next, chain) {
    if (node == list_entry(head, queue_contex_t, chain))
        break;
    list_splice_tail_init(node->q, m_queue->q);
    m_queue->size += node->size;
    node->size = 0;
}

將所有的 queue 接在一起,使用的資料型態是 queue_contex_t 用來表示多個 list


Valgrind 排除記憶體錯誤

==7733== 40 bytes in 1 blocks are still reachable in loss record 34 of 40
==7733==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==7733==    by 0x10DB6C: malloc_or_fail (report.c:215)
==7733==    by 0x10EA73: add_param (console.c:105)
==7733==    by 0x10D32D: console_init (qtest.c:1055)
==7733==    by 0x10D32D: main (qtest.c:1238)

文字訊息避免用圖片來表示,否則不好搜尋和分類。

這個錯誤訊息表示在程式結束時仍有一些動態分配的記憶體(使用malloc分配的)沒有被釋放,導致這些記憶體被視為 reachable ,也就是說,程式結束時仍然可以訪問到這些記憶體。

==7733== : 是 Valgrindprocess ID
at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) : 表示記憶體分配操作發生的位置
by 0x10DB6C: malloc_or_fail (report.c:215) : 表示程式執行中的呼叫堆疊,以及記憶體操作是被 malloc_or_fail 這個 function 使用的,並且這個 function 位於 report.c的第215行。


研讀論文 Dude, is my code constant time?

透過實驗(非理論)驗證時間複雜度

  • Timing leakage detection
    1. 測量執行時間: 針對兩個不同資料型態的輸入,重複測量加密函式的執行時間。通常利用CPU提供的 cycle counter 來實現。(例如 x86 系列的 TSC registerARM 架構中的systick 外設 )
    2. 套用 post-processing : 在進行系統分析之前,可以對每個單獨的測量套用一些 post-preocessing (包含 cropping) 或套用更高階的 preprocessing (例如 centered product)模仿高階 DPA 攻擊。
    3. 套用統計測試: 採用統計測試來驗證兩個時間分布是否相等。使用 Welch's t-testKolmogorov-Smirnov test
    • 綜上所述,程式的 simulatioin 是基於實際執行時間的測量和統計分析,以及使用統計測試來驗證兩個不同資料型態輸入的執行式間是否有顯著差異,因此 simulatioin 是通過實驗來驗證程式碼的時間複雜度,而不是依賴理論推導。

現有程式碼和論文描述哪裡不同?


研讀 Linux 核心原始程式碼 lib/list_sort.c

// SPDX-License-Identifier: GPL-2.0

GNU General Public License v2.0
GNU General Public License 可以縮寫成 GNU GPLGPL,這一行的意思是指其使用 GPL2.0 版本,大多數軟體的許可證用意是剝奪使用者分享和修改的自由,相較之下, GPL 的用意是保證所有使用者分享和更改軟體的自由。

__attribute__((nonnull(2,3,4)))

告知編譯器第二、三、四個傳遞的參數不可為 NULL ,可以幫助開發者避免由傳遞 NULL 指標引起的意外行為或崩潰,提高程式碼的可維護性和可靠性。

merge

根據註解:

* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.

可以得知 merge 沒有維護到 prev 指標

__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b)
{
	struct list_head *head, **tail = &head;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			*tail = a;
			tail = &a->next;
			a = a->next;
			if (!a) {
				*tail = b;
				break;
			}
		} else {
			*tail = b;
			tail = &b->next;
			b = b->next;
			if (!b) {
				*tail = a;
				break;
			}
		}
	}
	return head;
}

可以發現傳遞的參數有一個自定義的函式 list_cmp_func_t ,可以在 list_sort.h 中找到。

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);

這裡定義了一個函式指標 list_cmp_func_t ,它會接收三個參數,它們的資料型態分別是 void* 和兩個 const struct list_head* ,最後會返回一個整數,而 __attribute__((nonnull(2,3))) 表示編譯器會檢查該函式指標的使用,確保第二個和第三個參數不為 NULL

根據 list_sort.c 的註解:

 * The comparison function @cmp must return > 0 if @a should sort after
 * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
 * sort before @b *or* their original order should be preserved.  It is
 * always called with the element that came first in the input in @a,
 * and list_sort is a stable sort, so it is not necessary to distinguish
 * the @a < @b and @a == @b cases.

可以得知:

  1. 以升冪排列
  2. 如果 a > b 那麼回傳 > 0
  3. 如果 a < b 那麼回傳 <= 0 (表示 a 應該在 b 之前或維持原本的排序)
  4. list_sort 是一個穩定排序,因此不需要考慮 a <= b 的情況

所以當 cmp 回傳的值 <= 0 時,要將 a 放到已排序的鏈結串列的尾端,因為 a 要比 b 先被排序。


merge_final

根據註解:

* Combine final list merge with restoration of standard doubly-linked
* list structure.  This approach duplicates code from merge(), but
* runs faster than the tidier alternatives of either a separate final
* prev-link restoration pass, or maintaining the prev links
* throughout.

可以得知 merge_final 會將鏈結串列恢復成雙向的。

__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
			struct list_head *a, struct list_head *b)
{
	struct list_head *tail = head;
	u8 count = 0;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			tail->next = a;
			a->prev = tail;
			tail = a;
			a = a->next;
			if (!a)
				break;
		} else {
			tail->next = b;
			b->prev = tail;
			tail = b;
			b = b->next;
			if (!b) {
				b = a;
				break;
			}
		}
	}

	/* Finish linking remainder of list b on to tail */
	tail->next = b;
	do {
		/*
		 * If the merge is highly unbalanced (e.g. the input is
		 * already sorted), this loop may run many iterations.
		 * Continue callbacks to the client even though no
		 * element comparison is needed, so the client's cmp()
		 * routine can invoke cond_resched() periodically.
		 */
		if (unlikely(!++count))
			cmp(priv, b, b);
		b->prev = tail;
		tail = b;
		b = b->next;
	} while (b);

	/* And the final links to make a circular doubly-linked list */
	tail->next = head;
	head->prev = tail;
}

這裡的註解提到當 merge 非常不平衡時,舉例來說,儘管輸入都是已排序的節點,但是迴圈可能還是會跑很多次,這時可以定期調用 cond_resched() 解決此問題。
此處使用的函式 unlikely() 可以在 /include/linux/compiler.h 中找到。

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

__builtin_expect()gcc 內建函式,作用是將執行頻率高的分支標示為 likely ,執行頻率低的分枝則標示為 unlikely ,所以 merge_final() 中的 unlikely 是用來檢查是否已經對鏈結串列 b 中的節點進行多次迭代,如果是的話,則調用 cmp 函式來觸發回調。
使用 !!(x) 兩個 ! 的原因是將表達是轉換成布林值的 01

list_sort