# 2021q1 Homework2 (quiz2)
contributed by < `jasonmatobo` >
:::info
:alien: 補充
* 書本模式請使用以下連結 : [Linux 核心設計筆記(2021)](https://hackmd.io/@jasonmatobo/Linux_Kernel_Note_2021/)
:::
# 測驗 1
## container_of
舉一個實際的例子
[pcie_pme_work_fn](https://elixir.bootlin.com/linux/latest/source/drivers/pci/pcie/pme.c#L216)
```cpp
static void pcie_pme_work_fn(struct work_struct *work)
{
struct pcie_pme_service_data *data =
container_of(work, struct pcie_pme_service_data, work);
struct pci_dev *port = data->srv->port;
u32 rtsta;
```
這個 `pcie_pme_work_fn` 中傳入的參數是 `struct work_struct`
`struct work_struct` 其實是包在 `struct pcie_pme_service_data` 中的 `member`
[pcie_pme_service_data](https://elixir.bootlin.com/linux/latest/source/drivers/pci/pcie/pme.c#L41)
```cpp
struct pcie_pme_service_data {
spinlock_t lock;
struct pcie_device *srv;
struct work_struct work; ----> Here!!!
bool noirq; /* If set, keep the PME interrupt disabled. */
};
```
當你想控制` struct` 其他 `member` 時，可以使用 `container_of`
```cpp
static void pcie_pme_work_fn(struct work_struct *work)
{
// 使用 container_of
struct pcie_pme_service_data *data =
container_of(work, struct pcie_pme_service_data, work);
// 可以使用 struct 中其他的 member ---> srv
struct pci_dev *port = data->srv->port;
u32 rtsta;
```
以下是個範例程式
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct TEST_DATA{
int v1;
char v2[16];
int v3;
char v4[32];
unsigned long v5;
}*pData,sData;
void print_all(void *pMember)
{
// 透過 container_of ，可以存取其他 member
pData pB = container_of( pMember, struct TEST_DATA, v3);
printf("========================\n");
printf("B = Addr: %p \n",(void *) pB);
printf("B = Addr: %p value: %d \n",(void *) &(pB->v1),pB->v1);
printf("B = Addr: %p value: %s \n",(void *) &(pB->v2),pB->v2);
printf("B = Addr: %p value: %d \n",(void *) &(pB->v3),pB->v3);
printf("B = Addr: %p value: %s \n",(void *) &(pB->v4),pB->v4);
printf("B = Addr: %p value: %ld \n",(void *) &(pB->v5),pB->v5);
}
void main(void)
{
pData pA = (struct TEST_DATA*) malloc (sizeof(sData));
// Assign
pA->v1 = 10;
strncpy( pA->v2, "Hello", sizeof(pA->v2) );
pA->v3 = 20;
strncpy( pA->v4, "World", sizeof(pA->v4) );
pA->v5 = 30;
// Print Address & value
printf("========================\n");
printf("A = Addr: %p \n",(void *) pA);
printf("A = Addr: %p value: %d \n",(void *) &(pA->v1),pA->v1);
printf("A = Addr: %p value: %s \n",(void *) &(pA->v2),pA->v2);
printf("A = Addr: %p value: %d \n",(void *) &(pA->v3),pA->v3);
printf("A = Addr: %p value: %s \n",(void *) &(pA->v4),pA->v4);
printf("A = Addr: %p value: %ld \n",(void *) &(pA->v5),pA->v5);
// 只有傳 v3 給 function
print_all(&pA->v3);
free(pA);
}
```
執行結果如下
```shell
========================
A = Addr: 0x5555d4e4a2a0
A = Addr: 0x5555d4e4a2a0 value: 10
A = Addr: 0x5555d4e4a2a4 value: Hello
A = Addr: 0x5555d4e4a2b4 value: 20
A = Addr: 0x5555d4e4a2b8 value: World
A = Addr: 0x5555d4e4a2d8 value: 30
========================
B = Addr: 0x5555d4e4a2a0
B = Addr: 0x5555d4e4a2a0 value: 10
B = Addr: 0x5555d4e4a2a4 value: Hello
B = Addr: 0x5555d4e4a2b4 value: 20
B = Addr: 0x5555d4e4a2b8 value: World
B = Addr: 0x5555d4e4a2d8 value: 30
```
以下討論 `container_of` 作法
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
### __extension__
這個 `__extension__` 是給編譯器看的
如果你的 C 程式寫法不是標準 ANSI C 寫法，那編譯時會出現 `Warning`
加上 `__extension__` 是告訴編譯器，即使不是標準 ANSI C 寫法也不要出現`Warning`
### ({})
`container_of` 前後用 `({})` 包住，這個寫法就不是標準的 ANSI C
所以加上`__extension__` 不要出現 `Warning`
而這個 `({})` 是 GCC 編譯器支援的功能，所以是 GCC 看得懂這種寫法
可以參考 [Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)
### typeof()
`typeof` 也是 GCC 提供的功能，可以取出傳入參數的類型
可以參考 [Referring to a Type with typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
舉例：
```cpp
int a;
typeof(a) b; // 等於 int b
```
### ((type *) 0)->member
這裡 `type` & `member` 都是傳進來的參數
以上述範例來說
```cpp
container_of( pMember, struct TEST_DATA, v3);
type = struct TEST_DATA
member = v3
((type *) 0)->member ===> ((struct TEST_DATA *) 0)->v3
// 外面在加上 typeof 取類型等於取 v3 的類型 = int
// 所以 __typeof__(((type *) 0)->member) = int
```
### offsetof(struct , member)
可以算出 `member` 在 `struct` 的 `offset`，舉例:
```cpp
struct foo {
char a;
char b[10];
char c;
};
int main ()
{
printf ("offsetof(struct foo,a) is %d\n",(int)offsetof(struct foo,a));
printf ("offsetof(struct foo,b) is %d\n",(int)offsetof(struct foo,b));
printf ("offsetof(struct foo,c) is %d\n",(int)offsetof(struct foo,c));
return 0;
}
// Output:
// offsetof(struct foo,a) is 0
// offsetof(struct foo,b) is 1
// offsetof(struct foo,c) is 11
```
### container_of 結論
可以利用 `gcc -E` 來觀察 `Preprocessor` 的結果
```cpp
pData pB = __extension__({ const __typeof__(((struct TEST_DATA *) 0)->v3) *__pmember = (pMember); (struct TEST_DATA *) ((char *) __pmember - ((size_t)&(((struct TEST_DATA *)0)->v3))); });
// 簡化
pData pB =
const int *__pmember = v3; // 取得 v3 address，假設等於 0x5555d4e4a2b4
__pmember - offsetof(struct TEST_DATA, v3);
// 簡化
pData pB =
0x5555d4e4a2b4 - 0x14 = 0x5555d4e4a2a0;
// 所以 pB = 0x5555d4e4a2a0 = 此 struct 的開頭
```
## list.h 解讀
:::info
`list_head` 中有 2 個 `member`，都是指向 `list_head` 的指標
:::
```cpp
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
```graphviz
digraph list_add_node_t {
node [shape=record];
struct1 [shape=record,label="{ <f0> prev | <f1> next}"];
}
```
:::info
回傳 `list_head` 型態的變數，並且初始化 `prev` & `next` 指向自己
:::
```cpp
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
```graphviz
digraph list_add_node_t {
node [shape=record];
n_head [shape=record,style=filled,fillcolor=green,label="{ <p> [head] prev | <n> [head] next}"];
n_head:p->n_head:p;
n_head:n->n_head:p;
}
```
:::info
看 code 流程是插入 1 個 `node` 在 `prev` 和 `head` 中間
不知為什麼會取名為 `add_tail`?
:::
```cpp
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
```graphviz
digraph list_add_node_t {
node [shape=record];
n_pre [shape=record,label="{ <p> [pre] prev | <n> [pre] next}"];
n_node [shape=record,style=filled,fillcolor=green,label="{ <p> [node] prev | <n> [node] next}"];
n_head [shape=record,label="{ <p> [head] prev | <n> [head] next}"];
n_pre:n->n_node:p;
n_node:p->n_pre:p;
n_node:n->n_head:p;
n_head:p->n_node:p;
}
```
:::info
將傳入的 `node` 刪除
:::
```cpp
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
}
```
```graphviz
digraph list_add_node_t {
node [shape=record];
n_pre [shape=record,label="{ <p> [pre] prev | <n> [pre] next}"];
n_node [shape=record,style=filled,fillcolor=red,label="{ <p> del : [node] prev | <n> del : [node] next}"];
n_head [shape=record,label="{ <p> [head] prev | <n> [head] next}"];
n_pre:n->n_head:p;
n_head:p->n_pre:p;
}
```
:::info
檢查 `list_head` 是否為空，這邊判斷是如果 `next` 指向自己代表示空
:::
```cpp
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
```graphviz
digraph list_add_node_t {
node [shape=record];
n_head [shape=record,label="{ <p> [head] prev | <n> [head] next}"];
n_head:n->n_head:p;
}
```
:::info
檢查 `list_head` 是否"只"存在 1 個 `node`
:::
```cpp
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
```graphviz
digraph list_add_node_t {
node [shape=record];
n_pre [shape=record,label="{ <p> [pre] prev | <n> [pre] next}"];
n_head [shape=record,label="{ <p> [head] prev | <n> [head] next}"];
n_pre:n->n_head:p;
n_head:p->n_pre:p;
}
```
:::info
將 `list` 加到 `head` 的 `last`
:::
```cpp
static inline void list_splice_tail(struct list_head *list, struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
```
```cpp
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
```graphviz
digraph list_add_node_t {
node [shape=record];
n_1 [shape=record,label="{ <p> [head_from] prev | <n> [head_from] next}"];
n_2 [shape=record,style=filled,fillcolor=green,label="{ <p> [xxx] prev | <n> [xxx] next}"];
n_3 [shape=record,label="{ <p> [head_to] prev | <n> [head_to] next}"];
n_4 [shape=record,label="{ <p> [head_from_first] prev | <n> [head_from_first] next}"];
n_5 [shape=record,style=filled,fillcolor=salmon,label="{ <p> [node] prev | <n> [node] next}"];
n_1:n->n_2:p;
n_2:p->n_1:p;
n_2:n->n_3:p;
n_3:p->n_2:p;
n_3:n->n_4:p;
n_4:p->n_3:p;
n_5:n->n_2:p;
}
```
## 分析程式
記憶體分析 : Address Sanitizer & valgrind 沒有出現錯誤
```shell=
$ gcc -I ./. -fsanitize=address -g -o a.out main.c
$ ./a.out
$ rm a.out
$ valgrind --leak-check=full ./a.out
$ ./a.out
==12588== Memcheck, a memory error detector
==12588== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12588== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==12588== Command: ./a.out
==12588==
==12588==
==12588== HEAP SUMMARY:
==12588== in use at exit: 0 bytes in 0 blocks
==12588== total heap usage: 187,656 allocs, 187,656 frees, 4,529,436 bytes allocated
==12588==
==12588== All heap blocks were freed -- no leaks are possible
==12588==
==12588== For lists of detected and suppressed errors, rerun with: -s
==12588== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
[perf 介紹](https://tigercosmos.xyz/post/2020/08/system/perf-basic/)
```
sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"
```
## 問題解答
```
COND1 = (c) fast->next == list
COND2 = (b) fast->next->next == list
MMM = (e) &get_middle(&q->list)->list
TTT = (a) slow
```
# 測驗 2
## Linux 實作機制
[__roundup_pow_of_two](https://elixir.bootlin.com/linux/latest/source/include/linux/log2.h#L174)
# 測驗 3
# 測驗 4
###### tags `lab`
Sign in with Wallet
Connect another wallet