作業系統之前的程式 for stm32f4discovery (13) - 打造 c++ 標準程式庫

紙上得來終覺淺，絕知此事要躬行。

在完成

• simple os
• simple gui
• simple scheme

這些程式後, 覺得能寫下這些程式真是開心, 這些都是基本中的基本, 我喜歡在基本世界中打滾, 流行世界與我距離太遠。

接續的是 simple c++ 標準程式庫。我從來沒想過我會去寫標準程式庫, 這是無心插柳之作。

標準程式庫是一個演算法和系統知識的結合, 和之前偏重在系統知識的程式不同, 比較偏軟體, 我的演算法和資料結構能力太弱, 順道練習不是壞事。

不知道你有沒有和我一樣的感覺, 教科書上的演算法資料結構, 似乎在平凡人的工作上功效不大, 總是有基本程式庫打造好這些, 我們只要去用就好了, 這也造成我們很難去練習這樣的程式, 畢竟有了 std::list, 有誰能忍住誘惑不去用呢? 你說用 c 的怎麼辦, 有發現在這樣環境下的工程師大部份都用 array 嗎? 很少用上 list, map 這些資料結構。simple os 一開始也都是用 array, simple scheme 也是。

現在我迷上 bare-metal 程式, 剛好有個機會來練習這些基本功, 不是壞事, 只是能在學生時代就練習到是比較好的, 少壯不努力, 老大徒傷悲, 我是說我, 可別誤會。

在寫 simple os 時, 就已經寫了 (抄了) 不少相對應的 c function, 而在完成 simple scheme bare-metal 的版本時, 又多了一些資料結構, 再來實作 malloc 之後, 我終於有了動態配置記憶體的能力, 可以寫 c++ 的容器 (list, vector, map ...), 好用不少, 再加上實作出 exception handle, 記憶體的管理方便多了, 又在回頭改善了 c++ 容器, 讓她更像標準程式庫的行為。

這是一個累積的成果, 把之前的努力集合起來, 再加上一些程式碼, 就是 c++ 標準程式庫了。成果在這裡:

https://github.com/descent/simple_stdcpplib

目前支援 4 個平台, p103 模擬器, stm32f4discovery board, raspberry pi2, x86 16 bit mode, 所以也提供了 4 個 linker script。

要移植這個 library 有兩部份:

• 輸出/輸入 - 在這三個平台都是 uart
• c runtime - 如何從組合語言切換到 c/c++

c runtime 每個硬體平台都不同, 這便是從組合語言到 c 這段所需要最辛苦的過程, 從這裡開始就可以擺脫組合語言, 用 c 了。當然如果你喜歡用組合語言來開發程式, 就沒有這個需求。

在 p103/stm32f407 要做:

• bss init
• data section init

rpi2 要做：

• bss init
• stack register 的設定

x86 16bit 真實模式要做:

• bss init
• stack register 的設定
• 把 %ss, %ds, %cs 設到同一個值

x86 32bit 保護模式要做:

• bss init
• stack register 的設定
• 使用保護模式的 Flat memory model 還要把 %ss, %ds, %cs 設到同一個 selector

c runtime 除了和硬體相關之外還可能和你使用的 c compiler 有相關性, 我只有研究 gcc 這個 c compiler。

而 c++ runtime 則是 c runtime 做的事情, c++ 都要做, 而 c++ 有很多特性, 有些要在 c++ runtime 支援, ex:

• global object
• static object
• rtti
• exception handle - 這是難得一見的剖析 eh 文章
• Pure virtual functions
  
• 未知

目前只支援 global object, 本來不想做的, 因為覺得過於麻煩 (這個可得從 linker script 開始著手) 也怕整個 code 太大, 不過 cout 是 global object, 就做吧! 反正 c++ 就是大。

feature list:

• c runtime
• c++ runtime
• global object ctor/dtor
• exception handle (implement by setjmp/longjmp)
• printf (support float)
• malloc/free
• new/delete
• vector
• string
• map
• list

想試試的朋友可以從 stm32 p103 模擬器開始:
https://github.com/beckus/qemu_stm32.git

編譯出支援的模擬器之後, 再編譯本 library, 會有一個 mymain.bin, 執行 typescript L2 的 command, ctrl-A+X 離開 qemu。

typescript

  1 Script started on Tue 12 Jan 2016 09:38:47 AM CST
  2 descent@debian64: ~/git/qemu_stm32/arm-softmmu/qemu-system-arm -M stm32-p103 -kernel mymain.bin -nographic
  3 
  4 (process:25512): GLib-WARNING **: /build/glib2.0-VKSJTv/glib2.0-2.46.1/./glib/gmem.c:482: custom memory allocation vtable not supported
  5 STM32_UART: UART1 clock is set to 0 Hz.
  6 STM32_UART: UART1 BRR set to 0.
  7 STM32_UART: UART1 Baud is set to 0 bits per sec.
  8 STM32_UART: UART2 clock is set to 0 Hz.
  9 STM32_UART: UART2 BRR set to 0.
 10 STM32_UART: UART2 Baud is set to 0 bits per sec.
 11 STM32_UART: UART3 clock is set to 0 Hz.
 12 STM32_UART: UART3 BRR set to 0.
 13 STM32_UART: UART3 Baud is set to 0 bits per sec.
 14 STM32_UART: UART4 clock is set to 0 Hz.
 15 STM32_UART: UART4 BRR set to 0.
 16 STM32_UART: UART4 Baud is set to 0 bits per sec.
 17 STM32_UART: UART5 clock is set to 0 Hz.
 18 STM32_UART: UART5 BRR set to 0.
 19 STM32_UART: UART5 Baud is set to 0 bits per sec.
 20 STM32_UART: UART5 clock is set to 0 Hz.
 21 STM32_UART: UART5 BRR set to 0.
 22 STM32_UART: UART5 Baud is set to 0 bits per sec.
 23 STM32_UART: UART4 clock is set to 0 Hz.
 24 STM32_UART: UART4 BRR set to 0.
 25 STM32_UART: UART4 Baud is set to 0 bits per sec.
 26 STM32_UART: UART3 clock is set to 0 Hz.
 27 STM32_UART: UART3 BRR set to 0.
 28 STM32_UART: UART3 Baud is set to 0 bits per sec.
 29 STM32_UART: UART2 clock is set to 0 Hz.
 30 STM32_UART: UART2 BRR set to 0.
 31 STM32_UART: UART2 Baud is set to 0 bits per sec.
 32 STM32_UART: UART1 clock is set to 0 Hz.
 33 STM32_UART: UART1 BRR set to 0.
 34 STM32_UART: UART1 Baud is set to 0 bits per sec.
 35 LED Off
 36 CLKTREE: HSI Output Change (SrcClk:None InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 37 CLKTREE: HSI/2 Output Change (SrcClk:HSI InFreq:8000000 OutFreq:4000000 Mul:1 Div:2 Enabled:1)
 38 CLKTREE: SYSCLK Output Change (SrcClk:HSI InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 39 CLKTREE: HCLK Output Change (SrcClk:SYSCLK InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 40 STM32_RCC: Cortex SYSTICK frequency set to 8000000 Hz (scale set to 125).
 41 STM32_RCC: Cortex SYSTICK ext ref frequency set to 1000000 Hz (scale set to 1000).
 42 CLKTREE: PCLK1 Output Change (SrcClk:HCLK InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 43 CLKTREE: PCLK2 Output Change (SrcClk:HCLK InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 44 CLKTREE: GPIOA Output Change (SrcClk:PCLK2 InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 45 CLKTREE: AFIO Output Change (SrcClk:PCLK2 InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 46 CLKTREE: UART2 Output Change (SrcClk:PCLK1 InFreq:8000000 OutFreq:8000000 Mul:1 Div:1 Enabled:1)
 47 STM32_UART: UART2 clock is set to 8000000 Hz.
 48 STM32_UART: UART2 BRR set to 0.
 49 STM32_UART: UART2 Baud is set to 0 bits per sec.
 50 STM32_UART: UART2 clock is set to 8000000 Hz.
 51 STM32_UART: UART2 BRR set to 833.
 52 STM32_UART: UART2 Baud is set to 9603 bits per sec.
 53 i am cout ctor: 0
 54 ----------------
 55 free_index: 0
 56 
 57 0 0 0 0 0 0 0 0 
 58 0 0 0 0 0 0 0 0 
 59 0 0 0 0 0 0 0 0 
 60 0 0 0 0 0 0 0 0 
 61 0 0 0 0 0 0 0 0 
 62 0 0 0 0 0 0 0 0 
 63 0 0 0 0 0 0 0 0 
 64 0 0 0 0 0 0 0 0 
 65 ================
 66 fill ctor data: obj_count: 1, arg:537002040
 67 i am cout ctor: 1
 68 ----------------
 69 free_index: 0
 70 
 71 0 0 0 0 0 0 0 0 
 72 0 0 0 0 0 0 0 0 
 73 0 0 0 0 0 0 0 0 
 74 0 0 0 0 0 0 0 0 
 75 0 0 0 0 0 0 0 0 
 76 0 0 0 0 0 0 0 0 
 77 0 0 0 0 0 0 0 0 
 78 0 0 0 0 0 0 0 0 
 79 ================
 80 fill ctor data: obj_count: 2, arg:537002048
 81 i am cout ctor: 2
 82 ----------------
 83 free_index: 0
 84 
 85 0 0 0 0 0 0 0 0 
 86 0 0 0 0 0 0 0 0 
 87 0 0 0 0 0 0 0 0 
 88 0 0 0 0 0 0 0 0 
 89 0 0 0 0 0 0 0 0 
 90 0 0 0 0 0 0 0 0 
 91 0 0 0 0 0 0 0 0 
 92 0 0 0 0 0 0 0 0 
 93 ================
 94 fill ctor data: obj_count: 3, arg:537002056
 95 vector ctor
 96 abc
 97 xyz
 98 123
 99 abcdefghijk!@#$%^&*()
100 test vec iterator
101 abc
102 xyz
103 123
104 abcdefghijk!@#$%^&*()
105 vector dtor
106 vector ctor
107 map ctor
108 (111,99)
109 (abc,51)
110 (abcdefghqq,151)
111 (zxcv,5)
112 map dtor
113 vector dtor
114 i: 0
115 i: 1
116 i: 2
117 i: 3
118 i: 4
119 i: 5
120 i: 6
121 i: 7
122 i: 8
123 i: 9
124 i: 10
125 i: 11
126 i: 12
127 i: 13
128 i: 14
129 i: 15
130 i: 16
131 i: 17
132 i: 18
133 i: 19
134 i: 20
135 i: 21
136 i: 22
137 i: 23
138 i: 24
139 i: 25
140 i: 26
141 i: 27
142 i: 28
143 i: 29
144 i: 30
145 i: 31
146 i: 32
147 i: 33
148 i: 34
149 i: 35
150 i: 36
151 i: 37
152 i: 38
153 i: 39
154 i: 40
155 i: 41
156 i: 42
157 i: 43
158 i: 44
159 i: 45
160 i: 46
161 i: 47
162 i: 48
163 i: 49
164 i: 50
165 i: 51
166 i: 52
167 i: 53
168 i: 54
169 i: 55
170 i: 56
171 i: 57
172 i: 58
173 i: 59
174 i: 60
175 i: 61
176 i: 62
177 i: 63
178 no mem
179 i am cout dtor: 0
180 i am cout dtor: 1
181 i am cout dtor: 2
182 QEMU: Terminated
183  ]0;descent@debian64: /media/work/git/jserv-course/simple_stdcpplib descent@debian64:simple_stdcpplib$ exit
184 
185 Script done on Tue 12 Jan 2016 09:38:55 AM CST

mymain.cpp 是一個 bare-metal 程式, 已經和在 os 下的 c++ 程式沒什麼分別了。測試了 vector, map, exception handle, 我的記憶體分配區塊只有 64 塊, 所以 i 在分配到 63 之後, 就沒有足夠的記憶體了, 會引發 exception 然後跑到 L178 的 no mem, 這就是不用每次去 new 記憶體時都要檢查是不是有正確要到記憶體的祕密, 在一般 pc 的環境下, 你可能根本沒看過 new 要不到記憶體的情形吧!

而也是因為有了 malloc/free 加上 exception handle 才能實作出 new/delete, c++ 的 ctor/dtor 非常的厲害, 你也可以說他很邪惡, new/delete 又插了一些程式碼來喚起需要的 ctor, 反正都要呼叫的, 讓 c++ compiler 來幫我們一把不是壞事。

在 new 裡頭的 malloc 要不到記憶體的時候只要丟出一個 exception 就可以了, 不用繁複的去檢查是不是有要到記憶體, 以前都沒想到 new 這樣的設計竟然是這麼的精細, 對於記憶體的配置可以省下好大一番功夫, 重點是, 這並不需要付出很大的代價, 用 c 作一樣的事情, 一樣要寫這些程式碼。

mymain.cpp

 1 #include "myiostream.h"
 2 #include "myvec.h"
 3 #include "mymap.h"
 4 #include "mystring.h"
 5 
 6 using namespace DS;
 7 
 8 int mymain()
 9 {
10   int i=0;
11 
12 {
13   vector<string> vec;
14 
15   vec.push_back("abc");
16   vec.push_back("xyz");
17   vec.push_back("123");
18   vec.push_back("abcdefghijk!@#$%^&*()");
19 
20   for (i=0 ; i < vec.size() ; ++i)
21     cout << vec[i] << endl;
22   cout << "test vec iterator" << endl;
23   for (auto it=vec.begin() ; it!=vec.end() ; ++it)
24     cout << *it << endl;
25 }
26 
27 {
28   map<string, int> str_map;
29 
30   str_map.insert({"zxcv", 5});
31   str_map.insert({"abc", 51});
32   str_map.insert({"abcdefghqq", 151});
33   str_map.insert({"111", 99});
34 
35   for (auto it=str_map.begin() ; it!=str_map.end() ; ++it)
36     cout << "(" << it->k_ << "," << it->v_ << ")" << endl;
37 
38 }
39 
40   for (i=0 ; i < 100 ; ++i)
41   {
42     char *c = new char;
43     cout << "i: " << i << endl;
44   }
45   cout << "abc" << endl;
46 }

我沒有實作所有的 function, 只有實作我需要用到的部份, 而為了區分這是作業系統等級的程式碼, 我用了 mymain 當 c++ 程式進入點, 而不是用 main; namespace 也不是 std 而是 DS。美中不足的是 initializer_list 我看不懂, 直接抄 newlib 的程式碼, 這樣在使用 map 的時候才可以用 {}, 不用 value_type 這麼恐怖的語法。

printf 算是比較難的 function, cout 容易多了, 而支援 float 的輸出也很有成就感, 慢慢學習基本中的基本, 感覺很紮實, 不沈淪於 it 世界中更新快速的技術, 一步一步慢慢爬, 不急著囫圇吞棗。

gdeque 很類似 std::deque, 不過我這個是不會自己長大的 deque, 有大小限制的, 因為我寫的時候還沒有實作 malloc, 所以只用固定大小, 也沒什麼不好, 就沒改了。

vector 還算簡單, 不過 capacity(), max_size(), size() 這些東西你平常有注意到嗎? iterator 的實作也不算太難, 有了 iterator 真的是好用不少。

list 也算是簡單的, iterator 也不算太難, 可以憑自己的想法搞定。

map 是其中最難的部份, 我當然不是以紅黑樹實作, 而是用很一般的 binary search tree, tree 這個資料結構本身就不容易, 而其 iterator 的實作實在太難了, 我沒有實作出標準程式庫的版本。你認為 map::iterator++ 後要跑到哪一個呢? 標準程式庫有定義, 是 inorder 的那個順序, 剛好是由小到大的那個次序。網路上有人用了另外的方法實作, 而不是用 tree, iterator 就簡單多了。

為了實作 tree 的 iterator, 我找了Morris Traversal

• Inorder Tree Traversal without recursion and without stack!
• Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）

再搭配 coroutine, 的確可以完成這樣的工作, 蠻得意的, 可惜 Morris Traversal 會破壞整顆樹的結構, 所以還要想辦法還原原本的樹, 我最後沒有繼續下去, 感覺是個無底洞。標準程式庫果然不簡單。

比較麻煩的是還要提供 template 的版本, 語法看起來就很嚇人, 不熟 template 語法, 正好順道練習。

string 則不是 template 的版本, 而只是很單純的 char * 包裝而已。

而在 The C++ Programming Language國際中文版 第四版 19.3 介紹了 string class 的簡化版本, 還記得之前的 std::string 引以為傲的 reference counter, 時不我予, 在 mulit-thread 環境下有相當的問題, 新版的 std::string 幾乎都沒實作 reference counter 了。本範例使用 short string optimization 來增加短字串的效率。

我想參考 short string optimization 這個重新改寫 mystring。

cout 相當於 printf 的功能, 只不會比 printf 好寫很多, hex/dec/endl manipulators 的實作很特別, 我想了很久自己的亂實作, 後來看到 c++ 標準庫 p776 提到的作法, 讓我豁然開朗。這是 function overloading 的威力。

myiostream.h

83 ofstream& operator<<(ofstream& (*op)(ofstream &)) { return (*op)(*this); }

 94   // ref: c++ 標準庫 the 2nd p776
 95   static inline ofstream& endl(ofstream &stream)
 96   {
 97     stream << "\r\n";
 98     return stream;
 99   }

真是巧妙。

精通 linux 核心開發 the 3rd chapter 6 提到了 linux 上的四種資料結構, linked list, queue, map, rbtree, 所以開發 os kernel, 基本上只要有這些資料結構就夠用了。

目前用到組合語言的部份有:

• rpi2 start.s
• setjmp/longjmp (my_setjmp.S)

比想像中的少吧! 能儘量用 c++ 可以完成的我就儘量用 c++, 我並不熟悉組合語言, 還是別自找苦吃, 而且用 c++ 可攜性比較好, 之前 x86 c++ runtime 我用組合語言寫, 移植到 arm 就自己找麻煩了, 現在的版本移植回 x86 就簡單多了。

也許在 c 設計為主的 os 不需要這樣的介面, 不過長期使用 c++ 的我已經習慣這些用法, 我想把這些東西帶到以 c++ 完成的 os kernel (目前尚未完成, 我才剛建好目錄而已)。

本著對 c++ 的熱愛, 寫了這個 c++ 標準程式庫, 也用了部份 c++11 的語法。有機會的話應該要移植到 x86 上, 讓 simple os 也可以使用。這個 library 只支援 c++, 雖然有 printf 之類的 c 標準程式庫 function, 不過都已經是 c++ 了, 無法用 c compiler, 我沒打算支援 c compiler。

如果 c++ 標準程式庫是工業等級的程式碼, 那我這個 simple c++ 標準程式庫就是玩具等級的程式碼, 雖說只是玩具等級, 但也付出不少功夫才完成的。

能掌握所有的程式碼真的很有滿足感, 沒有黑箱, 了解所有程式的來龍去脈, 真的舒服痛快。

liux lib 的目錄下有類似的 library, ex:
linux/lib/string.c

在想不出來怎麼寫的時候, 就去偷看一下吧!