2020q1 Homework1 (lab0)

contributed by < ZhuMon >

tags: `linux2020`

Outline

2020q1 Homework1 (lab0)

環境

$ uname -a
Linux yx 5.3.0-40-generic #32-Ubuntu SMP Fri Jan 31 20:24:34 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.2.1-9ubuntu2) 9.2.1 20191008
Copyright (C) 2019 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.

作業要求

在 queue.[c/h] 中完成以下實作

q_new: 建立新的「空」佇列;
q_free: 釋放佇列所佔用的記憶體;
q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
q_size: 計算佇列中的元素數量。
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
q_sort: 以遞增順序來排序鏈結串列的元素

實作流程

queue.h

更改 queue.h 中的 queue_t ，使得 q_size() 以及 q_insert_tail() 能以
$O (1)$ 時間完成
依照作業教學，將 queue.h 中的 queue_t 增加成員 (size)
此舉能讓 q_size() 藉由直接讀取 queue_t 中的 size，不必每次重新計算 queue 的大小
缺點是必須在每次讓 queue 新增或刪除成員時，管理 queue 的 size 以及 tail 指標，也讓 queue 所需的記憶體空間增大 sizeof(pointer) + sizeof(int)

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;         /* Size of queue */
} queue_t;

queue.c

q_new

在初始化 queue_t 前，先確認是否成功分配記憶體，避免操作到空指標

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}

q_free

新增 tmp 作為釋放用的節點
藉由 q->head 的移動，遍歷整個 queue，並一一清除

本來想以 q->head 與 q->tail 是否相同作為結束迴圈的條件，後來發現這樣無法完全將 queue 清除，於是改為判斷 q->head 與 q->tail是否同時存在，又發現只要判斷 q->head 是否存在即可

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *tmp = q->head;
    while (q->head) {
        q->head = q->head->next;
        tmp->next = NULL;
        free(tmp->value);
        free(tmp);
        tmp = q->head;
    }
    free(q);
}

q_insert_head

將新元素 (list_ele_t) 放入 queue 的前端
先判斷傳入的 q 是否為 NULL，避免分配記憶體後才發現 q 為 NULL，造成 memory leak
在分配記憶體給新的元素後，判斷是否分配成功，若失敗，則將之前分配的 newh 清除
以 C library <string.h> 的 strncpy 複製 s，放入新元素的 value
因為 strncpy 不會自動將其他位置設為 \0，所以使用 memset 將 newh->value 歸零
確保 q->tail 能夠正常運作，第一個 element 建立時，將 q->tail 指向 q->head，且隨著新增元素，位移到最後

bool q_insert_head(queue_t *q, char *s)
{
   if (!q)
        return false;

    // Check separately to avoid extra malloc cause memory leak
    list_ele_t *newh;  // newh means new element in head
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    // Allocate space and copy the string
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, '\0', strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));

    newh->next = q->head;
    q->head = newh;

    // first time
    if (!q->tail) {
        q->tail = q->head;
    } else {
        while (q->tail->next) {
            q->tail = q->tail->next;
        }
    }

    q->size += 1;
    return true; 
}

q_insert_tail

與 q_insert_head 差不多
將新元素 (list_ele_t) 放入 queue 的尾端
若 queue 為空 (q->tail == NULL)，則將 head 和 tail 同時指向新元素 (newt)

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    // Check separately to avoid extra malloc cause memory leak
    list_ele_t *newt;  // newt means new element in tail
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;

    newt->value = malloc(sizeof(char) * strlen(s) + 1);
    if (!newt->value) {
        free(newt);
        return false;
    }
    memset(newt->value, '\0', strlen(s) + 1);
    strncpy(newt->value, s, strlen(s));
    newt->next = NULL;
    if (!q->tail) {
        q->tail = q->head = newt;
    } else {
        q->tail->next = newt;
        q->tail = newt;
    }

    q->size += 1;
    return true;
}

q_remove_head

藉由確認 q->head 是否為 NULL，確認 queue 是否為空
若 sp 不為 NULL，必須將成功刪除後的字串複製進去，並且依照傳入的 bufsize 決定複製多少
- 比較 bufsize or 要刪除的字串長度比較短，來決定真正要複製進 sp 的長度為何
- 呼叫 memset 時，需要保留最後一位來放 \0，所以 realbufsize 要加一
```
memset(sp, '\0', realbufsize + 1)
```
- 若只複製部分字串(bufsize)，由於呼叫 memset 會將 size += 1，而且複製完不能超過 bufsize，所以 realbufsize = bufsize - 1
新增一個指標 tmp 以供釋放 (free)
將 tmp 的成員都清空後，再釋放 tmp

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head) {
        return false;
    }
    if (sp) {
         // Insure copy size is right
        size_t realbufsize = (bufsize > strlen(q->head->value))
                             ? strlen(q->head->value)
                             : bufsize - 1;
        memset(sp, '\0', realbufsize + 1);
        strncpy(sp, q->head->value, realbufsize);
    }
    
    list_ele_t *tmp;
    
    tmp = q->head;
    q->head = q->head->next;
    tmp->next = NULL;
    free(tmp->value);
    free(tmp);

    q->size -= 1;
    return true;
}

q_size
- 若 q 不存在，則返回 0
- 藉由直接取得 q->size，達成在
  $O (1)$ 時間內完成 q_size()
- 在 q_new 時，便已將 q->size 設為 0 ，因此就算 queue 為空，還是會返回 0
```
int q_size(queue_t *q)
{
    return !q ? 0 : q->size;
}
```

q_reverse

原本使用三個指標 (prev, now, next) 來反轉 queue
一直思考如何將指標數量縮減，借鑑 gpwork4u 的方式後，發現可以藉由暫時不會用到的指標：q->tail->next 和 q->head->next，取代新的指標，只使用一個新的指標 tmp
藉由檢查 q->size < 2 來確認 queue 是否只有一個或沒有元素

void q_reverse(queue_t *q)
{
    // No effect if q is NULL or empty or only one element
    if (!q || q->size < 2) {
        return;
    }

    list_ele_t *tmp;
    tmp = q->head->next;
    q->tail->next = q->head;

    while (tmp != q->tail) {
        tmp = tmp->next;
        q->head->next->next = q->tail->next;
        q->tail->next = q->head->next;
        q->head->next = tmp;
    }
    q->tail = q->head;
    q->head = q->head->next;
    q->tail->next = NULL;
}

下圖為進入 while 迴圈之前，queue 的狀況，分別用三種顏色（紫、綠、紅）代表主要控制的指標

進入迴圈後，先將 tmp 指向下一個，避免待會將 b-next 反向後，無法取得 c
接著藉由操作 q->head->next->next，將 b->next 反向，指向 a
為了讓 q->head->next 前進，而不至於讓 b 無法取得，於是將 tail->next 指向 b
將 q->head->next 指向 tmp，準備下次的反向

  while (tmp != q->tail) {
      tmp = tmp->next;
      q->head->next->next = q->tail->next;
      q->tail->next = q->head->next;
      q->head->next = tmp;
  }

  while (tmp != q->tail) {
      tmp = tmp->next;
      q->head->next->next = q->tail->next;
      q->tail->next = q->head->next;
      q->head->next = tmp;
  }

考慮以下變更:

@@ -1,14 +1,13 @@
 void q_reverse(queue_t *q)
 {
-    if (q == NULL || q->head == NULL) {
+    if (!q  || !q->head)
         return;
-    }
+
     list_ele_t *prev, *now, *next;
     prev = q->head;
     now = q->head->next;
-    if (now == NULL) {  // there is only one element in queue
+    if (!now) /* only one element in queue */
         return;
-    }
 
     next = q->head->next->next;
 
@@ -18,7 +17,7 @@
 
     prev->next = NULL;
     now->next = prev;
-    while (next != NULL) {
+    while (next) {
         prev = now;
         now = next;
         next = now->next;

要點: 維持簡潔的縮排和風格

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

已更改程式碼為只剩一個新指標

q_sort

參考 Linked LIst Sort
使用 Merge sort 排序
merge_sort()
- 將一個 Linked list 拆成兩個
  - 藉由兩個指標 (l1, l2) 不同速度的前進
  - l1 會指向最後的 element
  - l2 會指向中間的 element
  - 將 l1 指向 l2->next 後，便可以得到兩個等長的 linked list (head 和 l1)
  - 將 l2 指向 *head，避免接下來使用 *head 後造成錯誤
- 將兩個已排序的 Linked list 合成一個 Linked list，並回傳
  - 參考 jwang0306 的 merge，將比較字串的部分縮進 while
  - 藉由走訪 l1 和 l2，並比較兩者元素，來建立新 Linked list
  - 最後離開 while 不是剩下 l1 就是 l2，於是縮成一行
q_sort()
- 藉由 pointer to pointer 省略回傳 q->head

void merge_sort(**head)
{
    if (!(*head) || !((*head)->next))
        return;

    list_ele_t *l1 = (*head)->next;  
    list_ele_t *l2 = *head;          

    while (l1 && l1->next) {
        l2 = l2->next;
        l1 = l1->next->next;
    }
    l1 = l2->next;
    l2->next = NULL;
    l2 = *head;

    merge_sort(&l2);
    merge_sort(&l1);

    *head = NULL;
    list_ele_t **tmp = head;

    while (l1 && l2) {
        if (strcmp(l1->value, l2->value) < 0) {  
            *tmp = l1;
            l1 = l1->next;
        } else {
            *tmp = l2;
            l2 = l2->next;
        }
        tmp = &((*tmp)->next);
    }

    *tmp = l1 ? l1 : l2;
}

void q_sort(queue_t *q)
{
    // if q has only one element or q is empty, q->head == q->tail
    if (!q || q->head == q->tail) {
        return;
    }

    merge_sort(&q->head);

    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

TODO:

考量到程式碼變數和函式命名的風格 (作業說明有提及，採用 Linux 核心程式碼慣用風格)，請修改上述程式碼，用小寫和精準的用字;
程式碼尚可更精簡，請改寫;
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv

沒有注意到參考的程式碼與當前的命名風格不同，已改正
改寫程式碼
- 將原來的 merge() 以及 mergeSortList() 合併為 merge_sort()
- ~~想將比較字串部分都縮進 while 迴圈內，但是還想不到辦法實現~~
- ~~雖然暫時無法再縮減程式碼~~，但是比較字串的 branch 數似乎也無法再降低
(更新）
- 參考 jwang0306 藉由 pointer to pointer 將比較字串的部分縮進 while
- 使用 pointer to pointer 省略回傳值
- 將使用的變數量縮減（重複使用變數）
- 在 hackmd 上刪除部分註解，避免雜亂

natsort

參考 natsort，將 strcmp 改為 strnatcmp

發現在執行 traces/trace-15-perf.cmd 時，會因為時間超過，而測試失敗
於是確認 strcmp 與 strnatcmp 的需要時間。以 time.h 的 clock 函式計算時間

此為未使用任何 gcc 最佳化方法 (-O1 -O2 -O3 …) 的狀況

發現 strnatcmp 需要的時間在十萬次以上的情況下，與 strcmp 差距極大，造成 qtest Timeout

很好！你終於發現這個故意安插的細節。
需要留意到，glibc 裡頭的 strcmp 做了一系列最佳化，類似 Speeding up string compare and sorting 的手段，但額外透過 SSE 和 AVX 指令集加速。相反地，natsort 實作就很 naive (取「原始」和「單純」的意思)，意味著有很大的加速空間，你可試著改進，記得對照 CS:APP 第 5 章來思考。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

經由老師提示，我試著去 linux kernel 內尋找有使用到 natural sort 的部分，一開始我認爲應該跟 file system 有關，於是聚焦在 linux/fs，粗略地尋找了一陣子卻沒有找到有關的資訊，但是在搜尋的過程中有發現 sort 這個命令

命令 (command) 和指令 (instruction) 不同，後者在「Linux 核心設計」課程特別指 CPU instruction，因此，sort 只能被稱「命令」，請變更用語;
Linux 核心的檔案系統主要維護 metadata (反映資料行為的資料)，可參見 i-node，sort 就仰賴 metadata 進行排序，所以，討論的主體該釐清，不是 Linux 核心去「排序」檔案名稱，而是 coreutils 一類的套件提供 sort 工具來排序;

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的，已更改用語

也就是說我一開始的找尋方向錯誤，Linux 核心不負責檔案的排序，「人類」看到的檔案系統順序都是由 coreutils 等套件來排序，所以我的確應該去閱讀 coreutils 的 sort 命令

不能說「方向錯誤」，有好奇心是值得稱許的事。需要注意，排序不全然跟 Linux 核心無關，可參見 The kernel and character set encodings，在核心內部的檔案系統實作，我們還是需要透過核心處理字元集 (如 Big5 [廣泛用於台灣], GB18030 [中國國家標準])，這樣後續在使用者層級的排序才有意義。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

確認 sort 這個命令是否符合 natural sort

發現 string 中含有空白時，兩者的行為會有差異

sourcefrog 的 natural sort

pic01
pic2
pic 4 else
pic 5
pic   7

macOS 的 sort 命令

後來發現應該使用 $ sort -V 來做排序

pic   7
pic 4 else
pic 5
pic01
pic2

再去各種線上排序的網站實驗後，發現每個網站對於 natural sort 的定義也都不一樣

測試了 Text Mechanic, PineTools, Gillmeister Software

閱讀 sort 命令的 man page 後，發現， sort 可以針對版本號碼做排序

$ ls pic* | sort -V
pic01
pic2
pic 4 else
pic 5
pic   7

效果符合 sourcefrog 的預期

稍微閱讀 sort 命令的運行方式後，發現 sort.c 關於檔案、版本號碼的排序是由 filevercmp 這個檔案來實作
實際與 strcmp、strnatcmp 比較（開啟 -O3 ）

很明顯地看到 filevercmp 遠超其他兩者

strcmp 所需時間一直只在 1 µs 附近，或許更低，但目前使用的 library 精準度只到微秒
另外，我還有發現字串越接近版本號（部分相似），strnatcmp 與 filevercmp 的表現越差
TODO: 發現 gnulib 比較字串的方式效率也不盡人意後，決定先熟悉編譯器的最佳化等教材，之後再試著改進

Valgrind 實驗

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

排解使用原配置可能造成的錯誤

使用 make valgrind 命令後，想要讓使用 massif 來視覺化記憶體使用量，可是卻發生錯誤

$ valgrind --tool=massif ./qtest
valgrind: Unknown option: --show-leak-kinds=all
valgrind: Use --help for more information or consult the user manual.

由於在 macOS 和 Linux 都遇到相同問題，確認兩者的版本

macOS 10.14.6

$ valgrind --version
valgrind-3.14.0.GIT

更新 macOS 的 Valgrind

$ brew upgrade valgrind

發生錯誤，要我更新 xcode，於是照著提示更新 xcode
由於之前安裝 Ubuntu 環境一直失敗，以爲是 macOS 版本的問題，於是將系統從 High Sierra(10.13.6) 升級到 Mojave (10.14.6)，所以 valgrind 是之前安裝的

升級完 xcode 後，想升級 Valgrind，發現 Valgrind not Found，試著安裝…

$ brew install valgrind
...
valgrind: This formula either does not compile or function 
          as expected on macOS versions newer than High Sierra
          due to an upstream incompatibility.
Error: An unsatisfied requirement failed this build.

只好試著以 github 安裝
參考此篇

$ brew install --HEAD https://raw.githubusercontent.com/sowson/valgrind/master/valgrind.rb

安裝成功，可是版本竟然是 3.16.0 ?

$ valgrind --version
valgrind-3.16.0.GIT

重新測試，發生同樣問題

$ valgrind --tool=massif ./qtest
valgrind: Unknown option: --show-leak-kinds=all
valgrind: Use --help for more information or consult the user manual.

Ubuntu 19.10

$ valgrind --version
valgrind-3.15.0

查詢 Valgrind 官網發現，最新版本的確是 3.15.0

重新閱讀 lab0-c 的 README.md 後，發現在 .valgrindrc 中有關於 Valgrind 的配置，並且找到該選項，將它刪除後，便可運作
發現 Valgrind 的另外一個配置： --leak-check 在 .valrindrc 裡的寫法為 --memcheck:leak-check=full，於是將 --show-leak-kinds=all 前也加上 memcheck，再執行，便通過了
- before
```
--show-leak-kinds=all
```
- after
```
--memcheck:show-leak-kinds=all
```

請提交 .valrindrc 相關的 pull request

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

已提交

設計實驗

目的：想要知道 strnatcmp 與 filevercmp 的記憶體用量

實驗一

讓兩者比較兩個不同字串 100000 次
TODO

論文 Dude, is my code constant time?

研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;

簡稱 dudect
TODO

獨立的終端機命令解譯器

解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

select 系統呼叫

在 Linux manual page 定義 select 如下

/* According to POSIX.1-2001, POSIX.1-2008 */
#include <sys/select.h>

/* According to earlier standards */
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

int select(int nfds, fd_set *readfds, fd_set *writefds,
              fd_set *exceptfds, struct timeval *timeout);

select() 可以監聽多個 file descriptors，
TODO

Bonus

發現新通過的 Pull request 含有一些小bug，進行修改

Add description of clang-format integration to vim (#28)
簡介：藉由在 vim 中新增 function，使得每次寫進 C/C++ 文件後，自動排版

function! Formatonsave()
  let l:formatdiff = 1
  py3f <path to your clang-format.py>/clang-format.py
endfunction
autocmd BufWritePre *.h,*.cc,*.cpp call Formatonsave()

已發 Pull Request，也已通過
Extend auto-indention for generic C/C++ source (#29)
簡介：新增 *.c 以及 *.hpp，使得 C/C++ 的檔案都適用自動排版

由於我的主系統是 macOS，他這個方法需要找到 clang-format.py 的位置，再取代 <path to your clang-format.py>，避免以後還需要再手動更新，於是寫了一個 script 將路徑寫好，並且 export 成環境變數

.vimrc

將 clang-format.py 的位置以 $CLANG_FORMAT_PATH 取代

...
function! Formatonsave()
  let l:formatdiff = 1
  py3f $CLANG_FORMAT_PATH
endfunction
autocmd BufWrite *.h,*.hpp,*.c,*.cpp,*.c++ call Formatonsave()
...

setEnv.sh

藉由 uname 命令，找出當前是在哪個作業系統
由於我存放 setEnv.sh 的資料夾裡，也有複製了老師的 .clang-fomat 檔案，所以之後不管在哪裡都會使用該設定進行排版
我是使用 zsh，所以會將設定放到 ~/.zshrc

#!/bin/sh
# Set environment of clang-format

sysOS=`uname`

if [ $sysOS = "Darwin" ]; then
    echo "On Mac OSX"
    echo "export CLANG_FORMAT_PATH to ~/.zshrc"
    echo "export CLANG_FORMAT_PATH=\"/usr/local/Cellar/clang-format/2019-05-14/share/clang/clang-format.py\"" >> ~/.zshrc
    echo "export clang_format_fallback_style=\"$PWD/.clang-format\"" >> ~/.zshrc

elif [ $sysOS = "Linux" ]; then
    echo "On Linux"
    echo "export CLANG_FORMAT_PATH to ~/.zshrc"
    echo "export CLANG_FORMAT_PATH=\"/usr/share/vim/addons/syntax/clang-format.py\"" >> ~/.zshrc
    echo "export clang_format_fallback_style=\"$PWD/.clang-format\"" >> ~/.zshrc
else
    echo "I don't know where clang-format.py is"
fi

TODO

natural sort
設計 Valgrind 實驗
讀論文
設計終端機命令解譯器

2020q1 Homework1 (lab0)

tags: linux2020

Outline

環境

作業要求

實作流程

queue.h

queue.c

natsort

Valgrind 實驗

排解使用原配置可能造成的錯誤

設計實驗

實驗一

論文 Dude, is my code constant time?

獨立的終端機命令解譯器

select 系統呼叫

Bonus

TODO

Read more

2020q3 Homework1 (quiz1)

透過 Netfilter 自動過濾廣告

2020q3 Homework3 (dict)

2020q3 Homework2 (quiz2)

tags: `linux2020`