2019q1 Homework1 (list)

contributed by < tommywang0tw >

homework requirement

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

Macros vs Functions

reference: macros vs functions

Before the compiler compiles a program, the pre-processor expands all the macros in the code by simply replacing the name of macros by its value. On the other hand, the code of functions stay unchanged before compilation. Functions are implemented by storing the current address of instruction into the stack and jump to the function when a function is called. Then the address is poped and pointed by the program counter again after the function returns.

Instead of function call, we prefer to use macro when a short part of code is highly frequently used. By doing this, we don't need to keep calling a stack to store the address of current instruction so that the program can run faster and save space for the stack and pointers.

In the file linux.h, so many macros are used. For example:

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

The macro above can visit each node in the linked-list. It's a short one-line code and very simple function. I searched "list_for_each" in the linux kernel, it is used in 249 code. And it's used many times in each file(more than 10 times in some of them).

A testing program to compare the efficiency difference

to be continued…

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

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

reference: Referring to a Type with typeof

What does typeof do?

typeof can refer a type of a expression or just simply a type.

In the reference link, I don't get this:
typeof (x[0](1))
The description is:This assumes that x is an array of pointers to functions; the type described is that of the values of the functions.

For example:

    typeof (*x) y;

This declares y with the type of what x points to. If x is declared as: int * x, y will have the int type.

Another example:

• Declare y as an array of pointers to characters:

    typeof (typeof (char *)[4]) y;

The declartion above is equal to this simple one:

    char *y[4];

Why we need to use typeof?

The use of typeof can improve the compability of a code. Think about this, if we implement a function or macro, we would want it can be used for any type of input. In this case, typeof can help and make our code be reusable for many other situations.
For example, in include/linux/typecheck.h, the macro below can check if a variable x has the type of type:

#define typecheck(type,x) \
({	type __dummy; \
	typeof(x) __dummy2; \
	(void)(&__dummy == &__dummy2); \
	1; \
})

If there were no typeof, different typecheck macros would probably be needed for different types.

I don't get how exactly this code works. I can understand __dummy and __dummy2 would have the same type if x has the type of type. However, the expression in line 4 is so confusing. Here is my understanding so far:
In line 2 and 3, we declare two variables called __dummy and __dummy2. Then &__dummy is the address of operator __dummy. __dummy and __dummy2 are two variables have their own address, so their address must not be the same. In this case, the expression in line 4 will always be false. Moreover, I don't know why the parentheses are used like this ({…}), and why there is only a 1 in line 5.

check GNU extension in gcc manual

jserv

Here is another example, it's a very commonly-used macro in linux kernel called container_of.

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:    the pointer to the member.
 * @type:   the type of the container struct this is embedded in.
 * @member: the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type,member) );})

This macro is

解釋以下巨集的原理

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

LIST_POISONING 這樣的設計有何意義？

linked list 採用環狀是基於哪些考量？

什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？

list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？

for_each 風格的開發方式對程式開發者的影響為何？

程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？

tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

tests/ 目錄的 unit test 可如何持續精進和改善呢？

實作Merge sort

Basic undserstanding of this program

struct list_head

In this code, the head and nodes attached to it share the same struct type. If this list is empty, the @prev and @next of head will just point to head itself. If it's not, @prev will point to the last node and @next will point to the first one. The declartion is in list.h and is shown below:

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

struct listitem

In struct list_head, there wasn't an element to store the value of a node. I found another structure in common.h, and this declaration clarifies how the value is stored. This structure listitem has two elements, one is the value of the node, and another one is a list_head structure we just discussed. In common.h:

struct listitem {
    uint16_t i;
    struct list_head list;
};

container_of

What is __extension__?

reference: alternate keywords

-pedantic option causes warnings for many GNU C extensions. We can prevent such warnings within one expression by writing __extension__ before the expression. __extension has no effect aside from this

Why double underscores __? e.g. __inline__, __typeof__, etc.

reference: alternate keywords

When -ansi or std options are used, certain keywords in GNU C extensions are disabled. The way to solve the problem is put double underscores __ at the beginning and the end of each keyword. e.g. __asm__, __inline__.

to be continued…