2019q1 Homework1 (list)

contributed by < JulianATA >

自我檢查項目

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

First of all, we need know the difference between macro and function.
Macro trade space for time, on the other hand, functions trade time for space.

The cost of function call is to branch to the function part every time, making it slower than Macro.

So, using Macros in Linux will save more time than functions.

Plot(togo):

Why not using inline functions?
Julian Fang

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

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

typeof() will be replace by return the type of parameter.

instance(before compilation):

int instance;
typeof(instance) b;

For instance(after compilation):

int instance;
int b;

A useful trick I knew is using in macros, when you are not sure what your inputs actually are.

Refer to GNU [Referring to a Type with typeof:https://gcc.gnu.org/onlinedocs/gcc/Typeof.html

typeof is often useful in conjunction with statement expressions (see Statement Exprs). Here is how the two together can be used to define a safe “maximum” macro which operates on any arithmetic type and evaluates each of its arguments exactly once:

#define max(a,b) \
  ({ typeof (a) _a = (a); \
      typeof (b) _b = (b); \
    _a > _b ? _a : _b; })

解釋以下巨集的原理

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

This is a macro I knew before, its utility is to find the memery starting address with only one member in the structure.

But before we take a deep look at it, we should know macro offset().

#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

The macro offset() can calculate the offset(偏移) of the member relative to structure starting memory address.

Then we bck to container_of(), which contains two steps.

1. create a pointer __pmember which point to type of member, and give the parameter of ptr to it.
2. __pmember - offset will be the starting address.

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

• list_empty
  • encapsulating head->next == head makes it easy to understand.
• list_del_init
  • Beside list_del, the memory space of the node won't be reset or free. list_del_init will initial the deleted node.
• list_is_singular
• list_splice
• list_cut_position
  To wrap up, I thought the functions or macros in list.h are for formal checking and manipulation of the list, making it easier and more safe when manipulate list.

LIST_POISONING 這樣的設計有何意義？

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

LIST_POISONING is defined in [linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h), commented as fallowed

 These are non-NULL pointers that will result in page faults
 under normal circumstances, used to verify that nobody uses
 non-initialized list entries.

in linux/list.h

static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

When deleting node, it'll set node->prev set as LIST_POISON2, node->next as LIST_POISON1, rather than set to NULL.

When enter these two memory will cause page fault, making them cannot be traversal.

List poisoning I knew is not in linux but in mail system as introduced in [List poinsoning]: https://en.wikipedia.org/wiki/List_poisoning"

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

Do not need to consider head and tail as special condition, an equal treatment circular linked list can reduce complicated determine statement.

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

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

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

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

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

#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
	    pos = n, n = pos->next)

The difference between list_for_each and list_for_each_safe is n.
As I know, n is like a buffer of pos.

Why we need a buffer of pos?
If we delete or free pos in our manipulation, we won't lose the memory address we need to traversal next.

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

• 提示：對照其他程式語言，如 Perl 和 Python

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

@ is used in doxygen assists developer modify program.

For example:

• @return is the return value.
• @ is represnet as function parameter.

Reference

We often use symbols not frequently use developement .

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

To check if all the subtle parts work well or not.

In software architecture, uni test can ensure every modifictaion of code won't cause bug or break origin functions.
Another benefit is shortening the testing, developing, and debugging time.

Unit test is checking a single unit, which can be a function or a class, indicating that a huge software is integrate by small units.

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

tags: Cprogramming LinuxKernel