2019q1 Homework1 (list)

contributed by <JEFF1216>

• 自我檢查表
• 為何採用 macro 來實作? function call 的成本?
• typeof
• add 與 delete 之外一糸列操作的原因
• LIST_POISONING 這樣的設計有何意義？
• 環狀 linked list 的考量
• list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？
• for_each 風格的開發方式對程式開發者的影響為何？
• 程式註解裡頭大量存在 @ 符號
• tests/ 目錄
• 修改 lab0

自我檢查表

• 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
• Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
• GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
• 解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

• 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
• LIST_POISONING 這樣的設計有何意義？
• linked list 採用環狀是基於哪些考量？
• list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？
• for_each 風格的開發方式對程式開發者的影響為何？
• 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
• tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
• tests/ 目錄的 unit test 可如何持續精進和改善呢？

---

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

function call 需要對 stack push 及 pop ，會對 stack 造成負擔以及產生多餘的指令。但優點是即使函數被呼叫多次，在記憶體中仍只有一份實體，較節省記憶體空間。能節省存放及使用的記憶體空間
用 macro 來實作的話就不會有多餘的指令及額外的 stack 消耗，但會有編譯後程式體積增加及難以維護和在被呼叫多次以後，會耗損存放及使用大量的記憶體空間。

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

memache原碼分析 slab內存分析器
memcached使用了一個名為slab的記憶體分配方法，，slab其實可以簡單地把它看作一個 memory pool 。memcached的memory pool分配的空間大小是固定的。雖然是固定大小，但memcached的能分配的空間大小(尺寸)也是有很多種規格的。一般来說，是以满足所需求的為主。
memcached定義一個名為slabclass_t結構，并且定義了slabclass_t類型slabclass(是一个全域變數)。可以把結構的每一个元素稱為一個slab分配器。一個slab分配器能分配的記憶體大小是固定的，不同的slab分配的記憶體大小是不同的。如圖：

而每一個從slab分配出去的記憶體都會以指標連接起來。

而其中如果我們每次都不停的用動態記憶體分配malloc，勢必會出現很多記憶體碎片，所以memcached的做法是，先創建一個比較大的記憶體池，然後把這塊記憶體分成一塊塊的item，並用兩個指標(prev和next)把這些item連接起来。如圖：

code review:

#include "memcached.h"
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/socket.h>
#include <sys/resource.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <signal.h>
#include <assert.h>
#include <pthread.h>

//#define DEBUG_SLAB_MOVER
/* powers-of-N allocation structures */

typedef struct {
    unsigned int size;      //slab分配器分配的item的大小 
    unsigned int perslab;   //每一個slab分配器能分配多少個item

    void *slots;          //指向空閒item鏈表
    unsigned int sl_curr;   //空閒的item的個數 

    unsigned int slabs;     /* how many slabs were allocated for this class */
//這個是已经分配了記憶體的slabs個数。list_size是這個slabs陣列(slab_list)的大小
    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; //slab陣列的大小

    size_t requested; /* The number of requested bytes */
} slabclass_t;

static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];
static size_t mem_limit = 0;
static size_t mem_malloced = 0;
/* If the memory limit has been hit once. Used as a hint to decide when to
 * early-wake the LRU maintenance thread */
static bool mem_limit_reached = false;
static int power_largest;

typeof

typeof是用來擴充c語言原有的資料型態，通常我們會將某個資料型態或者將常用的資料型態組合給予一個比較直觀而易懂的別名。 定義別名之後我們就可以像使用原有的資料型態來宣告或定義變數一樣， 直接拿它來宣告或定義變數。
底下以 linux-2.6.7/include/linux/kernel.h 來舉例：

#define min(x,y) ({ 
	typeof(x) _x = (x);	
	typeof(y) _y = (y);	
	(void) (&_x == &_y);		
	_x < _y ? _x : _y; })

該定義是取兩個相同的類型中取出較小的那個，可以接收兩個變數x和y，後面用typeof來定義變數_x和_y，也就是接收的變數x和y不管是那一種類型，例如int或是char，_x和_y都會和他們是相同類型，換句話說，不論typeof可以讓min接受任何類型的變數，而在第四行的 (void) (&_x == &_y); 其實用意是拿來檢測接收的是不是同一種類型的變數，如果指標接收的是不同類型的指標，系統就會給出警告。

除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？

首先我們必須要先了解，其實list.h是在定義所有linked list的行為，除了add和delete以外，更有像是搬移或是合併等等的功能，以下以搬移作為舉例：

搬移

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

static inline void list_move_tail(struct list_head *node,
                                  struct list_head *head)
{
    list_del(node);
    list_add_tail(node, head);
}

從原本的鏈表移動到新的鏈表並且插入新的位置，list_move(&new_sockopt.list,&nf_sockopts)會把new_sockopt它所在的鏈表上删除，並將其再放入nf_sockopts的頭。

我們如果要創造一個linked list，不管是單向或是雙向，list.h讓我們不需要重新定義結構或是結構變數，只需要使用list.h中的相關變數。

• list.h 中也定義了以下的操作：

  ​​​​​​  LIST_HEAD：宣告一個 list 並初始化
  ​​​​​​  INIT_LIST_HEAD：初始化一個空的 list
  ​​​​​​  list_add_tail：在 list 的尾端插入新節點
  ​​​​​​  list_del_init：刪除節點並將其初始化，可以避免之後錯誤的操作
  ​​​​​​  list_empty：回傳 list 是否是空的
  ​​​​​​  list_is_singular：回傳是否只有一個節點
  ​​​​​​  list_splice：把一個 list 的所有節點插入到另一個 list 開頭
  ​​​​​​  list_splice_tail：把一個 list 的所有節點插入到另一個 list 結尾
  ​​​​​​  list_splice_init：把一個 list 的所有節點插入到另一個 list 開頭，並且把第一個 list 的 head 做 INIT_LIST_HEAD
  ​​​​​​  list_cut_position：將一個 list 的開頭移到另一個 list
  ​​​​​​  list_move：把一個指定的節點移到 list 的開頭
  ​​​​​​  list_move_tail：把一個指定的節點移到 list 的尾端
  

解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

首先這在我之前作過得Functional Programming in C有使用到類似的概念，我們是使用container of來抓取結構的頭位址對其進行dereference，根據一個結構體變量中的一個成員變量的指針來獲取指向整個結構體變量的指針，打個比方，若今天有一個結構體為：

struct demo_struct {
           type1 member1;
           type2 member2;
           type3 member3;
           type4 member4;
};      

假設結構體變量 demo 在實際內存中的位置如下圖所示：
demo
±––––––+ 0xA000
| member1 |
±––––––+ 0xA004
| member2 |
±––––––+ 0xA010
| member3 |
±––––––+ 0xA018
| member4 |
±––––––+
若今天我們執行程式碼：container_of(memp, struct demo_struct, type3) 會使得出來的位址為該結構得初始位址，也就是 0xA000，而其中的offsetof是用來抓取距離頭位址所相差的結構偏移量，例如若是member2則offsetof出來的值會是4，底下提供一個之前用來測試的offsetof和container of的程式碼:

#include <stdio.h>
#include <stddef.h>
//#define offsetof(type, member) (size_t)&(((type*)0)->member) 在stddef.h就有定義了
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
//offset表示去取該結構指標（例如：type）的結構偏移量 即該變量之記憶體大小（會自動補齊）
typedef struct T {
    int member_bit :9;
    char member_char;
    long member_long;
} TYPE;

int main()
{
    printf("%zu\n", sizeof(TYPE));                        // 16, 8 (armv7l) //因為member_bit為9個位元為了對齊會補成16個位元
    printf("%zu\n", offsetof(TYPE, member_char));         //  2, 2 (armv7l) //char為2位元
    printf("%zu\n", offsetof(TYPE, member_long));         //  8, 4 (armv7l)
    // printf("%zu\n", offsetof(TYPE, member_bit));       // error

    TYPE *t;
    printf("%p, ", t);
    printf("%p, ", &t->member_char);
    printf("%p\n", (container_of(&(t->member_char), TYPE, member_char)));
    // 0x7ffff9572f00, 0x7ffff9572f08, 0x7ffff9572f00 (x86-64)
    //     0x7ea6b20c,     0x7ea6b210,     0x7ea6b20c (armv7l)
}

LIST_POISONING 這樣的設計有何意義？

其目的是用來幫助這種kernel code進行debug，在此程式碼中可以看到：

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif

當我們的 list_del 發生時，透過上述方法我們可以避免kernel的指標誤用到沒有初始話的記憶體上面，進階導致segamation fault 換言之，當如果出現程式記憶體區段出錯時，這個位址將會被更改，以此來作為我們debugger的證據。