2022q1 Homework1 (lab0)

contributed by < Pepitaw >

tags: `linux2022`

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping:                        10
CPU MHz:                         2600.000
CPU max MHz:                     4500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5199.98
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11

開發紀錄

q_new

根據 list.h 參考函式 INIT_LIST_HEAD 初始化 q ，將 q 的 next 與 prev 指向自己。

實際程式碼

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

實作流程
1. 使用 malloc 分配記憶體空間給指標 q
2. 如果 malloc 分配空間失敗，會回傳 NULL
3. 使用 INIT_LIST_HEAD 初始化指標 q

q_free

根據 list.h 參考函式 list_for_each_entry_safe ，藉由副本遍歷各個 entry ，不會受到移除 entry 的影響

實際程式碼

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *pos, *n;
    list_for_each_entry_safe (pos, n, l, list)
        q_release_element(pos);
    free(l);
}

實作流程
1. 若 head 指向 NULL 就 return
2. 走訪整個 linked list ，對每個 entry 呼叫 q_release_element 釋放其空間
3. 釋放 head 的記憶體空間

q_insert_head

根據 list.h 參考函式 list_add ，將新增的 element_t 加到 head 的 next

實際程式碼

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add(&e->list, head);
    return true;
}

實作流程
1. 若 head 指向 NULL 就回傳 false
2. 使用 malloc() 分配 element_t 大小的記憶體空間給 e ，若分配失敗則回傳 false
3. 利用 strdup 會用 malloc 分配記憶體儲存字串的特性，直接指派給 e->value
4. 若 strdup 分配記憶體失敗就清除 e 與回傳 false
5. 加入新 entry 到list

過去嘗試與心路歷程

不知道在 queue.h 有定義 element_t ，自行定義 node

bool q_insert_head(struct list_head *head, char *s)
{
    struct node{
        char *str;
        struct list_head list;
    };
    struct node *n = malloc(sizeof(struct node));
    strcpy(n->str, s);
    list_add(&n->list, head);
    return true;
}

遇到以下問題 Segmentation fault occurred. You dereferenced a NULL or invalid pointer
發現是 e->value 未配置記憶體，利用 strdup 配置記憶體與複製 *s (規格書中提到 Memory for the new string is obtained with malloc ，有malloc仍有配置失敗的時候)

element_t *e = malloc(sizeof(element_t));
if(!e)
    return false;
strcpy(e->value, s);
list_add(&e->list, head);
return true;

去看 list_add 加入 node 的位置

struct list_head *tmp = head->next;
list_del(tmp);
list_add(tmp, head->next->next);

由以下結果得知，可以直接插入指定位置的下一個 entry

cmd> ih ant
l = [ant dolphin dolphin dolphin gerbil bear dolphin meerkat bear bear bear cat]
cmd> reverse
l = [dolphin dolphin ant dolphin gerbil bear dolphin meerkat bear bear bear cat]

q_insert_tail

根據 list.h 參考函式 list_add_tail ，將新增的 element_t 加到 head 的 prev ，其餘同 q_insert_head

實際程式碼

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add_tail(&e->list, head);
    return true;
}

q_remove_head

根據 list.h 參考函式 list_first_entry ，找到第一個 entry ，也參考函式 list_del 將目標 entry remove ，成為單一節點

實際程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    element_t *e = list_first_entry(head, element_t, list);
    list_del(&e->list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}

實作流程
1. 如果 head 指向 NULL 或只有 head 就回傳 NULL
2. 利用 list_first_entry 找到第一個 entry
3. 再用list_del 將目標 entry remove ，成為單一節點
4. 若 sp 存在，複製 e->value 到 sp 並補結尾 \0

過去嘗試與心路歷程（有問題待解）

想說用 strdup 修改 sp 不但有配置記憶體，還會自動補 \0 ，但卻報錯還不知道原因。

if(sp){
    sp = strndup(e->value, bufsize - 1);
}

ERROR: Failed to store removed value

q_remove_tail

根據 list.h 參考函式 list_last_entry ，找到最後一個 entry ，其餘與 q_remove_head 相同

實際程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    element_t *e = list_last_entry(head, element_t, list);
    list_del(&e->list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}

q_size

根據 list.h 參考函式 list_for_each() 遍歷各個 entry

實際程式碼

int q_size(struct list_head *head)
{
    if (!head)
        return false;
    int i = 0;
    struct list_head *lh;
    list_for_each (lh, head)
        i++;
    return i;
}

實作流程
1. 若傳入的 head 指向 NULL 就回傳 false
2. 每經過一個 entry i 就加一，最後即為size

q_delete_mid

依據「龜兔賽跑」Floyd’s Cycle detection，當 rabbit 跑完 list 時， turtle 跑到一半的特性，來尋找中間的節點

實際程式碼

bool q_delete_mid(struct list_head *head)
{
    struct list_head *fast = head->next, *slow = head->next;
    for (; fast != head->prev && fast->next != head->prev;
         fast = fast->next->next, slow = slow->next)
        ;
    /*while(fast != NULL && fast->next != NULL){
        fast = fast->next->next;
    slow = slow->next;
    }*/
    slow->prev->next = slow->next;
    slow->next->prev = slow->prev;
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

實作流程
1. 設置兩個 pointer ， fast 一次跑一個 entry ， slow 跑兩個 entry
2. 兩 pointer 開始遍歷 list ，當其中一個 pointer 跑完 list 時結束
3. 利用 q_release_element 對 slow 做 delete

過去嘗試與心路歷程

實做龜兔賽跑找中間節點，遇到以下問題
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
因為迴圈結束方式是判斷是否為 NULL ，但 circular linked list 是頭尾相接不會 NULL

for(struct list_head *fast = head, *slow = head; fast && fast->next; \
    fast = fast->next->next, slow = slow->next);

q_delete_dup

實際程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *pos, *n;
    bool used = false;
    list_for_each_entry_safe (pos, n, head, list) {
        if (pos->list.next != head &&
            !strcmp(pos->value,
                    list_entry(pos->list.next, element_t, list)->value)) {
            list_del(&pos->list);
            q_release_element(pos);
            used = true;
        } else if (used) {
            list_del(&pos->list);
            q_release_element(pos);
            used = false;
        }
    }
    return true;
}

實作流程
1. 如果 head 指向 NULL 就回傳 false
2. 利用 list_for_each_entry_safe 遍歷各個 entry
3. 利用 strcmp 比較 pos 跟下一個 entry 的 value 是否相同
4. 若 value 相同且 pos 不是結尾，就將 pos delete
5. 用 use 去紀錄該 entry 是否跟以刪除 entry 有相同的 value

q_swap

根據 list.h 參考函式 list_move_tail 將 entry 放到 head->prev

實際程式碼

void q_swap(struct list_head *head)
{
    bool odd = q_size(head) & 0x01;
    for (int i = q_size(head) >> 1; i > 0; i--) {
        list_move_tail(head->next->next, head);
        list_move_tail(head->next, head);
    }
    if (odd)
        list_move_tail(head->next, head);
}

實作流程
1. 先將第二個的 entry 放到尾巴
2. 再將第一個的 entry 放到尾巴
3. 總共做"總數的一半"次
4. 若總數為奇數，就要再做一次流程二

過去嘗試與心路歷程（有問題待解）

想使用 list.h 函式 list_swap ，但發現未定義
我是在 linux kernel 版本 5.13.0 查到的函式，與我的 linux kernel 5.13.0-30-generic 相符，但還是找不到原因

void q_shuffle(struct list_head *head)
{
    srand( time(NULL) );
    for (int i = q_size(head); i > 0; i--) {
        struct list_head *tmp = head->next;
        for (int x = rand()%i; x > 0; x--){
            tmp = tmp->next;
        }
        list_swap(tmp, head->prev);
        //list_move_tail(tmp, head);
    }
}

queue.c: In function ‘q_shuffle’:
queue.c:347:2: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
  347 |  list_swap(tmp, head->prev);
      |  ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:50：queue.o] 錯誤 1

q_reverse

實際程式碼

void q_reverse(struct list_head *head)
{
    if (!head || head->next->next == head)
        return;
    struct list_head *pos = head->prev;
    for (int i = q_size(head); i > 1; i--)
        list_move_tail(pos->prev, head);
}

實作流程
1. 若 head 指向 NULL 或 list 只有一個 entry 就回傳 NULL
2. 從尾巴開始反向遍歷，將 entry 依序放到尾巴

q_sort

實際程式碼

struct list_head *mergesort(struct list_head *node)
{
    if (!node || !node->next)
        return node;
    struct list_head *fast = node, *slow = node;
    for (; fast->next && fast->next->next;
         fast = fast->next->next, slow = slow->next)
        ;
    fast = slow->next;
    slow->next = NULL;

    struct list_head *l1 = mergesort(node);
    struct list_head *l2 = mergesort(fast);

    struct list_head t_head, *tmp = &t_head;
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) > 0) {
            tmp->next = l2;
            l2 = l2->next;
        } else {
            tmp->next = l1;
            l1 = l1->next;
        }
        tmp = tmp->next;
    }
    if (l1)
        tmp->next = l1;
    else
        tmp->next = l2;
    return t_head.next;
}

void q_sort(struct list_head *head)
{
    if (!head || !head->next)
        return;
    head->prev->next = NULL;
    struct list_head *list = head->next;
    list = mergesort(list);
    head->next = list;

    struct list_head *i = head;
    while (i->next != NULL) {
        i->next->prev = i;
        i = i->next;
    }
    head->prev = i;
    i->next = head;
}

實作流程
1. 若 head 指向 NULL 或 list 沒有 entry 就 return
2. 將尾巴的 next 指向 NULL，切斷 next 方向的 circular
3. 將去除 head 的 list 進行 mergesort
- 以下為 mergesort
1. 利用「龜兔賽跑」將 list 從中間一分為二
2. 再用 strcmp 比較大小，依小到大排列
3. 將 head 指向排序好的 list
4. 最後利用 list 的 next->prev 將所有 prev 重新排列

理解 Linux 核心中的排序實作

merge (pointer to pointer version)

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

程式碼理解
1. 用 pointer to pointer 指向 a 與 b 之間較小的
2. 但沒有處理 prev 的部份

merge_final (pointer version)

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

程式碼理解
1. 比較 a 跟 b 的大小，用 tail 的 next 指向比較小的 entry
2. 一路遍歷兩個 linked list 直到其中一個 linked list 結束(a 或 b 指向 NULL)
3. 用 b 指向還未走到尾巴的 linked list (未經過的 entry)
4. 用 tail 的 next 指向剩下的 entry
5. 遍歷完剩下的 entry ，並用 count 紀錄剩下的 entry 數量
6. 利用 unlikely 將 count 轉成 bool
7. 頭尾相接成為 circular
程式碼差異
1. 在每次 merge 時就處理好 prev 與 next 的 link
  我則是只看 next ，將 linked list 用 next 排列完後，再一次將所有的 prev 處理好
2. 計算兩個 linked list 的 merge 是否 entry 數量相近，我則沒有考慮

list_sort

void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
	struct list_head *list = head->next, *pending = NULL;
	size_t count = 0;	/* Count of pending */

	if (list == head->prev)	/* Zero or one elements */
		return;

	/* Convert to a null-terminated singly-linked list. */
	head->prev->next = NULL;

	do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

	/* End of input; merge together all the pending lists. */
	list = pending;
	pending = pending->prev;
	for (;;) {
		struct list_head *next = pending->prev;

		if (!next)
			break;
		list = merge(priv, cmp, pending, list);
		pending = next;
	}
	/* The final merge, rebuilding prev links */
	merge_final(priv, cmp, head, pending, list);
}

程式碼理解
1. 用 head->next == head->prev 去判斷是否只有一個 entry 或沒有 entry
2. 將 circular 的 next 部份斷開
程式碼差異

運用 Valgrind 排除 qtest 實作的記憶體錯誤

作業目標

運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗

更新中

$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd

==2951== 5 bytes in 1 blocks are still reachable in loss record 1 of 2
==2951==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2951==    by 0x4A5250E: strdup (strdup.c:42)
==2951==    by 0x1108BE: linenoiseHistoryAdd (linenoise.c:1236)
==2951==    by 0x111451: linenoiseHistoryLoad (linenoise.c:1325)
==2951==    by 0x10C6B0: main (qtest.c:951)
==2951== 
==2951== 160 bytes in 1 blocks are still reachable in loss record 2 of 2
==2951==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2951==    by 0x11087E: linenoiseHistoryAdd (linenoise.c:1224)
==2951==    by 0x111451: linenoiseHistoryLoad (linenoise.c:1325)
==2951==    by 0x10C6B0: main (qtest.c:951)

linecopy = strdup(line);

在 qtest 提供新的命令 shuffle

作業目標

在 qtest 提供新的命令 shuffle ，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示

程式碼

void q_shuffle(struct list_head *head)
{
    srand(time(NULL));
    for (int i = q_size(head); i > 0; i--) {
        struct list_head *tmp = head->next, *tail = head->prev;
        for (int x = rand() % i; x > 0; x--)
            tmp = tmp->next;
        list_del(tail);
        list_add(tail, tmp->prev);
        list_move_tail(tmp, head);
    }
}

實作流程
1. 將 linked list 的 size 不斷減一，作為隨機變數的範圍
2. 遍歷去找隨機變數所指定的 entry
3. 用 list_del 將尾巴成為獨立的 entry ，將尾巴用 list_add 加到目標 entry 的下一個 entry ，再將目標 entry 移動到尾巴，作為交換

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2022q1 Homework1 (lab0)

tags: `linux2022`

實驗環境

開發紀錄

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

理解 Linux 核心中的排序實作

運用 Valgrind 排除 qtest 實作的記憶體錯誤

在 qtest 提供新的命令 shuffle

在 qtest 提供新的命令 web

參考資料

2022q1 Homework1 (lab0)

tags: linux2022

實驗環境

開發紀錄

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

理解 Linux 核心中的排序實作

運用 Valgrind 排除 qtest 實作的記憶體錯誤

在 qtest 提供新的命令 shuffle

在 qtest 提供新的命令 web

參考資料

tags: `linux2022`