作者: haogroot

Monotonic Stack – 陪你刷題

Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

本篇要來探討的是 Monotonic Stack。

什麼是 Monotonic Stack

Stack 我們都了解，有著 First-in-Last-out 的特性，而 Monotonic Stack 則是 stack 內的元素都保持著 Monotonic (單調性) 。

閱讀全文〈Monotonic Stack – 陪你刷題〉

CS:APP Ch7 Linking 學習筆記

更新版修改於 https://hackmd.io/@haogroot/cs-app_ch7 。

為什麼要學習 Linking

  • 理解 linker 幫助你建構大型程式
    • 大型程式會包含許多 libraries ，了解如何 linking 可以幫助你處理棘手的編譯錯誤。
  • 理解 linker 可以避免寫程式上犯下難以抓出的錯誤
    • linker 執行 symbol resolution 所做的決定將大大的影響程式執行。
  • 理解 linking 幫助你理解 scope 的概念
    • global 跟 local variable 之間的差別
    • static 的作用
  • 理解 linking 幫助你理解重要的系統概念
  • 理解 linking 讓你更理解如何使用 shared library
  • 我個人在工作上常常遇到 Linker 報出的錯誤，深感完全不理解其背後的運作原理，所以決定將這張拿出來好好學習。

閱讀全文〈CS:APP Ch7 Linking 學習筆記〉

漫談 linked list 在 linux kernel 中的不一樣

linked list 是大家在學資料結構一定會學到的，通常會將資料跟指標寫在同一個 struct，但在 linux kernel 內卻不是這樣使用的。

Linux kernel 內的定義

一般來說 linked list 在 linux kernel 都以 struct list_head 來描述。

在 tools/include/linux/types.h 可以見到其定義:

struct list_head {
        struct list_head *next, *prev;
    };

這個 struct 沒有帶任何的 data，Kernel 用法會將它直接放到其他 struct 內，使得其他 struct 也可以擁有 linked list 的操作。

我們來看一個例子，在 linux/net/netlabel/netlabel_addrlist.h 可以見到這樣用法

    /**
     * struct netlbl_af6list - NetLabel IPv6 address list
     * @addr: IPv6 address
     * @mask: IPv6 address mask
     * @valid: valid flag
     * @list: list structure, used internally
     */
    struct netlbl_af6list {
        struct in6_addr addr;
        struct in6_addr mask;
        u32 valid;
        struct list_head list;
    };

疑~ 等等 ! 那這樣就算我們走訪整個 linked list，我們也存取不到 data，這樣我們就失去使用 linked list 的意義了!

一般在走訪到每個 list node ，透過指標就可以直接存取 data ，如以下作法:

    ListNode *current = head;
    while(current != 0) {
        printf("%d", current->data);
        current = current->next;
    }

由於 kernel 並沒有把 data 跟 pointer 放在同樣的 struct，造成無法直接存取 data ，以下就來探討 kernel 是如何解決的問題。

如何走訪 linked list 並存取資料

kernel 提供 containerof 這個巨集來解決上述問題，以下我們就來拆解

    #define container_of(ptr, type, member)                            \\
        __extension__({                                                \\
            const __typeof__(((type *) 0)->member) *__pmember = (ptr); \\
            (type *) ((char *) __pmember - offsetof(type, member));    \\
        })
  • offsetof(type, member) 這個 macro 定義在標準函式庫裡，通過把 0 位址轉換為 type 型態的 pointer，然後去獲取該 struct 中的 member 的 pointer，也就是獲取了 member 與該 struct 起始點的 offset。
  • typeof 可以用在 expression 或 type 上，此 macro 會回傳 argument 的 type，值得留意的是，使用 expression 作為 argument 上並不會真的執行這個 expression。
    typeof (int *) m
    typeof (typeof (char *)[4]) n;

上述等同於宣告 int m 和 char n[4] 一樣。

  • （type *）0 -> 這個 type 形態的 struct，他裡面有個成員叫做 member，我們利用 typeof 取得 member 的型態。
  • 再用 __pmember 減去 offset，也就等於得到了該 type struct 的真實位址。
  • 因此 container_of 我們可以理解為我們利用其成員來反求其母結構的位址
  • __ extension __
    GCC uses the extension attribute when using the -ansi flag to avoid warnings in headers with GCC extensions.

透過 container_of 讓我們能夠在走訪 linked list 時候隨時都可以得到其所在之 struct 的位址，一但有了位址，就能夠自由的存取他的所有成員變數了。

Updated on 2022-07-27 08:04:21 星期三