linux linked list

the 1st edition: 20131017
the 2nd edition: 20141112

我不確定是不是和 linux list 一樣, 這是一步步写嵌入式操作系统:ARM编程的方法与实践提到的 list 資料結構, 應該是從 linux 那個取經而來。有點複雜, 花了點腦力才搞懂。

基本原理:
以 list.c L7 struct page 來說, 只要知道 list 成員這個位址, 就可以計算出這個 struct page 的位址, 假設 unsigned int/int 佔 4 byte, list 位址是 28, 那這個 struct page 的位址是 28 - 4 * 3 = 16, 就是這麼簡單, 但是那些計算的 macro 就不簡單了。

我並不是要說明 list_entry macro, 書上解說的很詳細 (p148~154, 8 頁的說明, 我怎麼可能在 blog 解釋的比書上還好呢), 但我還是沒能理解, 寫個小範例來配合書上的說明。

如果只是要使用這個 function, 那就簡單多了, 參考 Linux kernel linked list for user space

list.c

  1 #include <stdio.h>
  2 
  3 struct list_head {
  4  struct list_head *next, *prev;
  5 };
  6 
  7 struct page {
  8  unsigned int vaddr;
  9  unsigned int flags;
 10  int order;
 11  //struct kmem_cache *cachep;
 12  struct list_head list;//to string the buddy member
 13 };
 14 
 15 
 16 static inline void INIT_LIST_HEAD(struct list_head *list)
 17 {
 18  list->next = list;
 19  list->prev = list;
 20 }
 21 
 22 static inline void __list_add(struct list_head *new_lst,
 23          struct list_head *prev,
 24          struct list_head *next)
 25 {
 26  next->prev = new_lst;
 27  new_lst->next = next;
 28  new_lst->prev = prev;
 29  prev->next = new_lst;
 30 }
 31 
 32 static inline void list_add(struct list_head *new_lst, struct list_head *head)
 33 {
 34  __list_add(new_lst, head, head->next);
 35 }
 36 
 37 static inline void list_add_tail(struct list_head *new_lst, struct list_head *head)
 38 {
 39  __list_add(new_lst, head->prev, head);
 40 }
 41 
 42 static inline void __list_del(struct list_head * prev, struct list_head * next)
 43 {
 44  next->prev = prev;
 45  prev->next = next;
 46 }
 47 
 48 static inline void list_del(struct list_head * entry)
 49 {
 50  __list_del(entry->prev,entry->next);
 51 }
 52 
 53 
 54 static inline void list_remove_chain(struct list_head *ch,struct list_head *ct){
 55  ch->prev->next=ct->next;
 56  ct->next->prev=ch->prev;
 57 }
 58 
 59 static inline void list_add_chain(struct list_head *ch,struct list_head *ct,struct list_head *head){
 60   ch->prev=head;
 61   ct->next=head->next;
 62   head->next->prev=ct;
 63   head->next=ch;
 64 }
 65 
 66 static inline void list_add_chain_tail(struct list_head *ch,struct list_head *ct,struct list_head *head){
 67   ch->prev=head->prev;
 68   head->prev->next=ch;
 69   head->prev=ct;
 70   ct->next=head;
 71 }
 72 
 73 
 74 static inline int list_empty(const struct list_head *head)
 75 {
 76  return head->next == head;
 77 }
 78 
 79 
 80 #define offsetof(TYPE, MEMBER) ((unsigned int) &((TYPE *)0)->MEMBER)
 81 
 82 
 83 #define container_of(ptr, type, member) ({   \
 84  const typeof( ((type *)0)->member ) *__mptr = (ptr); \
 85   (type *)( (char *)__mptr - offsetof(type,member) );})
 86 
 87 
 88 #define list_entry(ptr,type,member) \
 89     container_of(ptr, type, member)
 90 
 91 
 92 
 93 #define list_for_each(pos, head) \
 94  for (pos = (head)->next; pos != (head); pos = pos->next)
 95 
 96 
 97 int main(int argc, const char *argv[])
 98 {
 99   struct page p1, p2;
100 
101   p1.list.next = p2.list.prev;
102   struct list_head *lh = &p1.list;
103   //struct list_head *lh = &p1.list;
104 
105   struct page *p3=0;
106   ((struct page *)0)->list ;
107   printf("%p\n", &((struct page *)0)->list);
108   printf("%p\n", (char *)lh);
109   printf("%p\n", ( (char *)lh - ((unsigned int) &((struct page *)0)->list) ) );
110   printf("%p\n", &p1);
111         
112   //list_entry(lh,struct page,list);
113   return 0;
114 }

200   ({ const typeof( ((struct page *)0)->list ) *__mptr = (lh); 
201   (struct page *)( (char *)__mptr - ((unsigned int) &((struct page *)0)->list) );});
202   return 0;

L80 ~ L89 真是令人害怕的 macro, 還有一個不認識的 typeof, 不認識很正常, 這是 gcc 的 c extension, 很討厭這種 extension 吧, 難道沒用上 extension 就做不到同樣的事情嗎? 當然不是, 只是選擇不同。

L112 展開是 L200, L201 的結果 (還是讓人害怕, 書上用了 8 頁的說明現在你覺得有道理了吧), 我分別從 L105~110 做了單獨的測試。最主要是要補充書上沒提到的小例子, 有了這個小例子, 搭配書上的講解 (6.1.2.2 page 148~154), 應該就能了解。

我沒注意到 ({}) 這用法, 這也是 gcc extension:
http://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html
http://www.ptt.cc/bbs/C_and_CPP/M.1383271390.A.B23.html

一開始被 0 取址所迷惑, 以為這樣會 core dump, ~~不過應該是要做寫入的動作才會 core dump, 讀取位址 0 是沒問題的。~~有點問題, 在我的 linux 環境下, 就算只是讀取位址 0 的內容也是有問題的。這裡應該要這樣說: &((struct page *)0)->list) 把這個 list 的位址取出來是沒有問題的, 縱使是用 address 0 去強制轉型出來。

struct list_head addr = (((struct page *)0)->list);
有問題

struct list_head *addr = &(((struct page *)0)->list);
沒問題

一個更短的例子:

zero.c

1 int main(int argc, char *argv[])
2 {
3   unsigned int i;
4
5   i = * (volatile unsigned int *)0;
6   return 0;
7 }

這在我的 linux 下會得到 Segmentation fault。

z.disasm

144 080483cc <main>:
145  80483cc: 55                    push   %ebp
146  80483cd: 89 e5                 mov    %esp,%ebp
147  80483cf: 83 ec 10              sub    $0x10,%esp
148  80483d2: b8 00 00 00 00        mov    $0x0,%eax
149  80483d7: 8b 00                 mov    (%eax),%eax
150  80483d9: 89 45 fc              mov    %eax,-0x4(%ebp)
151  80483dc: b8 00 00 00 00        mov    $0x0,%eax
152  80483e1: c9                    leave  
153  80483e2: c3                    ret    
154  80483e3: 66 90                 xchg   %ax,%ax
155  80483e5: 66 90                 xchg   %ax,%ax
156  80483e7: 66 90                 xchg   %ax,%ax
157  80483e9: 66 90                 xchg   %ax,%ax
158  80483eb: 66 90                 xchg   %ax,%ax
159  80483ed: 66 90                 xchg   %ax,%ax
160  80483ef: 90

執行到 L149 會產生 Segmentation fault, 看來 linux 把讀取 address 0 也當作是一個 memory access exception。

descent@debian-vm:part2$ ./list 
0xc
0xbfe84500
0xbfe844f4
0xbfe844f4

真是厲害, 我看過的版本是使用 c macro, 造出類似 c++ template 的技巧; c++ 有 template, 就不用這麼轉腦袋了, 當然一樣有型別檢查, 而且和課本的內容像多了。下面的程式碼是 c++ template 的版本。

list.cpp

 1 // template linked list test in os kernel
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 #include "stm32.h"
 7 
 8 template <typename type>
 9 class List
10 {
11   public:
12     List(type *item)
13     {
14       set_item(item);
15       prev_ = next_ = 0;
16     }
17     void add_next(List *n)
18     {
19       next_ = n;
20     }
21     type *item(){return item_;}
22     void set_item(type *item)
23     {
24       item_ = item;
25     }
26     List *next(){return next_;}
27   private:
28     type *item_;
29     List *prev_;
30     List *next_;
31 };
32 
33 struct page 
34 {
35  unsigned int vaddr;
36  unsigned int flags;
37  int order;
38 };
39 
40 
41 void mymain()
42 {
43   page p1, p2;
44   List<page> node1(&p1), node2(&p2);
45   List<page> *head;
46 
47 #if 0
48   printf("%p\n", &p1);
49   printf("%p\n", &p2);
50 #endif
51 
52   //node1.set_item(p1);
53   //node2.set_item(p2);
54 
55   node1.add_next(&node2);
56   head = &node1;
57   page *cur_page = 0;
58   for (List<page> *cur=head ; cur ; cur=cur->next())
59   {
60     cur_page =  cur->item();
61     //printf("%p\n", cur->item());
62   }
63   while(1);
64 
65 #if 0
66 
67   p1.list.next = p2.list.prev;
68   struct list_head *lh = &amp;p1.list;
69   //struct list_head *lh = &amp;p1.list;
70 
71   struct page *p3=0;
72   ((struct page *)0)-&gt;list ;
73   printf("%p\n", &amp;((struct page *)0)-&gt;list);
74   printf("%p\n", (char *)lh);
75   printf("%p\n", ( (char *)lh - ((unsigned int) &amp;((struct page *)0)-&gt;list) ) );
76   printf("%p\n", &amp;p1);
77         
78   //list_entry(lh,struct page,list);
79   return 0;
80 #endif
81 }
82 
83 #if 0
84   ({ const typeof( ((struct page *)0)-&gt;list ) *__mptr = (lh); 
85   (struct page *)( (char *)__mptr - ((unsigned int) &amp;((struct page *)0)-&gt;list) );});
86   return 0;
87 #endif

跑在 os 下使用這功能沒什麼特別的, 這是要在 os 層級使用的, 來試試看能否成功。

arm-none-eabi-g++ -fno-common -O0 -g -mcpu=cortex-m3 -mthumb  -fno-exceptions -fno-rtti -std=c++11  -c list.cpp 
arm-none-eabi-g++ -Wl,-T./stm32.ld -nostartfiles -fno-common -mcpu=cortex-m3 -mthumb -o list.elf list.o
arm-none-eabi-objcopy -O binary list.elf list.bin

qemu-system-arm -M lm3s6965evb -kernel list.bin -S -gdb tcp::1234

為了簡單, 就不要出動列印功能 (不使用 printf), 直接透過 qemu/gdb 來檢視正確性, gdb 可觀察到 p1, p2 位址, 和使用 List 取出的是一樣的。藉由 template, 可以塞進各種型別, 相信 c++ template 版本看來友善多了。

gdb

 1 (gdb) target remote :1234
 2 Remote debugging using :1234
 3 ResetISR () at stm32.h:21
 4 21      {
 5 (gdb) b mymain
 6 Breakpoint 1 at 0x10e: file list.cpp, line 44.
 7 (gdb) c
 8 Continuing.
 9 
10 Breakpoint 1, mymain () at list.cpp:44
11 44        List<page> node1(&p1), node2(&p2);
12 (gdb) p &p1
13 $1 = (page *) 0x200000d0
14 (gdb) p &p2
15 $2 = (page *) 0x200000c4
16 (gdb) n
17 55        node1.add_next(&node2);
18 (gdb) n
19 56        head = &node1;
20 (gdb) n
21 57        page *cur_page = 0;
22 (gdb) n
23 58        for (List<page> *cur=head ; cur ; cur=cur->next())
24 (gdb) n
25 60          cur_page =  cur->item();
26 (gdb) p cur_page 
27 $3 = (page *) 0x0 <VectorTable>
28 (gdb) n
29 58        for (List<page> *cur=head ; cur ; cur=cur->next())
30 (gdb) p cur_page 
31 $4 = (page *) 0x200000d0
32 (gdb) n
33 60          cur_page =  cur->item();
34 (gdb) n
35 58        for (List<page> *cur=head ; cur ; cur=cur->next())
36 (gdb) p cur_page 
37 $5 = (page *) 0x200000c4
38 (gdb)

L13, L15, 是 p1, p2 的位址, L31, L37 是透過 List 取出的位址, 剛好一樣 (不一樣就慘了)。

以下的 gdb 環境為 stm32f4 discovery board, 和模擬器的值一模一樣。

gdb stm32f4 discovery board

 1 $1 = {vaddr = 3204496768, flags = 134218252, order = 536870912}
 2 (gdb) p &p1
 3 $2 = (page *) 0x200000d0
 4 (gdb) p &p2
 5 $3 = (page *) 0x200000c4
 6 (gdb) n
 7 55   node1.add_next(&node2);
 8 (gdb) n
 9 56   head = &node1;
10 (gdb) n
11 57   page *cur_page = 0;
12 (gdb) n
13 58   for (List<page> *cur=head ; cur ; cur=cur->next())
14 (gdb) n
15 p 60     cur_page =  cur->item();
16 (gdb) p cur_page
17 $4 = (page *) 0x0
18 (gdb) n
19 58   for (List<page> *cur=head ; cur ; cur=cur->next())
20 (gdb) p cur_page
21 $5 = (page *) 0x200000d0
22 (gdb) n
23 60     cur_page =  cur->item();
24 (gdb) n
25 58   for (List<page> *cur=head ; cur ; cur=cur->next())
26 (gdb) p cur_page
27 $6 = (page *) 0x200000c4
28 (gdb) n
29 63   while(1);
30 (gdb) n
31 ^Cmymain () at list.cpp:63
32 63   while(1);
33 Error while handling inferior event:
34 Quit
35 mymain () at list.cpp:63
36 63   while(1);

c macro 版本莫測高深, c++ template 版本高深莫測, 相信每個人都有自己喜歡的作法, 神的右手與魔鬼的左手同樣的強大。使用 c++, 你可選神的右手或是魔鬼的左手, 這是我喜歡 c++ 的原因之一。

大概被 llvm 嚇到了, gcc 開始接受 c++ 了。

GCC's move to C++
http://airs.com/ian/cxx-slides.pdf (google 的人做的簡報)

人體汽肛 - 風馳電掣, 人車一體

blog 文章

2014年11月12日星期三