作業系統之前的 scheme

the 1st edition: 20141127 (4)
the 2nd edition: 20210327 (6)

會選擇 c++ 來開發 scheme, 最主要是因為 c++ 的標準程式庫有很多好用的 class: string, vector, map, list ... 不用為了這些基本的東西傷腦筋; 但這次要開發的是 - 在作業系統之前的 scheme (開發平台是 stm32f4discovery), 這些好東西通通派不上用場, 沒有 malloc/new, 又怎麼能用這些東西呢! 甚至連 global object 都不能用, 所以幾乎和使用 c 一樣, 不過還是能用上點 c++ 的特性。

原本程式中用到 list, vector, map 的部份, 通通要改, 全部改用 array, 不夠彈性, 但容易實作, 至於 input/output function, 需改用 uart 這部份的程式碼, 所以直接把之前搞定的 uart 程式碼複製一份過來修改。

getline 我得換成 getchar uart 的版本, cout 也要換成 myprint uart 的版本, 這之前都做過了, 把以前的努力都集合起來就可以, scanner 的作法則改為一次讀一個 byte 來轉成 token, s-express 不複雜, 但我覺得還是不容易, 沒想到花點時間竟然搞定, 感謝两周自制脚本语言的 scanner 這節提供的知識。

再來是 malloc Cell* 的部份, 由於在重寫 struct Cell 時, 我就考慮到在 stm32f4discovery 開發板上執行, 也就是沒有 os 的環境, 所以才使用了 array pool 來得到一個 Cell 的記憶體。雖然沒有彈性, 但能簡化問題, 再搭配一些人工手法, 可以減低 pool 可能會不夠用的問題。

我先在 qemu stm32 p103 emulator 上測試, 等成功了再上到 stm32f4discovery, 減少 flash 讀寫次數。也的確有必要, 光在模擬器上就測試了無數次, 減少了多次的 flash 讀寫。

在製作 p103 emulator 的版本階段, 出了一個 link 問題:

git@github.com:descent/stm32_p103_demos.git stm32_p103_demos/demos/uart_echo git commit: 6b2df2c6e62f3c48a6c6dc20c76367124c1ca447

bss_to_big

1 /home/descent/arm-cs-tools/lib/gcc/arm-none-eabi/4.7.3/../../../../arm-none-eabi/bin/ld: mymain.elf section `.bss' will not fit in region `RAM'
2 /home/descent/arm-cs-tools/lib/gcc/arm-none-eabi/4.7.3/../../../../arm-none-eabi/bin/ld: region `RAM' overflowed by 34085848 bytes
3 collect2: error: ld returned 1 exit status

我以為我已經很了解 link 的問題了, 這應該難不倒我, 就是哪個 section 太大, 整個記憶體空間不足嘛! 嚇不了我的。但隨著時間的過去, 我還是無法處理這問題, 亂 google 找問題, 我 - 開始緊張了, 原來我還有沒搞懂的東西。

當然最後還是搞定了, 原因是: bss 竟然需要 34M 的記憶體空間, 嚇壞我了, p103 只有 20K ram, 把 main.ld 的 RAM 從 20K 改成 48M 就可以編過, 但想也知道, 放入 flash 執行, 一定掛掉。

main.ld

 MEMORY {   FLASH (rx) : ORIGIN = 0x00000000, LENGTH = 128K   RAM (rwx) : ORIGIN = 0x20000000, LENGTH = 20K -> 48M } ... ...

我當然是不會用這麼蠢的改法。程式中用到相當多的 global variable (global variable 不一定佔據 bss, 得找對才行), 來把他們減少, shorten_bss L32 的效果最好,

/bin/ld: region `RAM' overflowed by 877288 bytes collect2: error: ld returned 1 exit status

從 34M 降到 877K, 效果不錯, 可是還不夠 ...

shorten_bss

 1 diff --git a/cell.h b/cell.h
 2 index d7238ea..eb36b5c 100644
 3 --- a/cell.h
 4 +++ b/cell.h
 5 @@ -11,7 +11,7 @@
 6  
 7  using namespace std;
 8  
 9 -const int MAX_POOL = 1000;
10 +const int MAX_POOL = 70;
11  
12  enum PairAttr {HEAD, FIRST, SECOND};
13  enum CellType {STRING, SYMBOL, NUMBER, PAIR, PRIMITIVE_PROC, NULL_CELL, INVALID};
14 @@ -21,7 +21,7 @@ struct Environment;
15  struct Cell;
16  typedef Cell *(*ProcType)(Cell *);
17  
18 -const int MAX_SIZE = 256;
19 +const int MAX_SIZE = 20;
20  // a variant that can hold any kind of lisp value
21  struct Cell 
22  {
23 diff --git a/s_eval.h b/s_eval.h
24 index 37048ac..2da9ae5 100644
25 --- a/s_eval.h
26 +++ b/s_eval.h
27 @@ -4,14 +4,14 @@
28  #include "cell.h"
29  #include "token_container.h"
30  
31 -const int MAX_ENVIRONMENT_POOL = 1000;
32 +const int MAX_ENVIRONMENT_POOL = 10;
33  
34  #ifdef USE_CPP_MAP
35  typedef std::map<std::string, Cell*> Frame;
36  #else
37 -const int FRAME_LEN = 128;
38 +const int FRAME_LEN = 56;
39  
40 -const int LINE_SIZE = 256;
41 +const int LINE_SIZE = 128;
42  
43  struct EnvElement
44  {
45 @@ -29,7 +29,7 @@ struct Environment
46  
47      Frame frame_;
48  
49 -    char name_[255]; // for debug
50 +    char name_[12]; // for debug
51      int free_frame_index_;
52    private:
53  };

胡亂修改後, 總算 link 成功。

機器上的記憶體有 20K, 程式本身有 19K, 載入到記憶體後, 可以正常執行的嗎? 不一定, bss 區域不會佔據程式本身, 但是會佔用載入時的記憶體位址, 所以還得加上 bss 佔用的記憶體, 若 bss 佔據了 2K, 19k+2k = 21k, 記憶體就不夠用了。

這便是 link 不過的原因。

還有問題二:

高興的將程式載入模擬器後, 準備欣賞自己的傑作, 發現:

repl 的第一個參數 prompt, 不知道為什麼會被 TokenContainer tc 所影響 (傳進來的參入位址會變成 0), 我把 TokenContainer tc 改成 global variable 才正常 (原本是 auto variable)。

我猜測是 stack 被覆蓋了, 不過沒有認真追, 也有可能是其他問題。

再來還有一些後續的小問題, 克服他們後, 就是下面影片的成果。



應該離成功不遠了 ...

真實機器篇 - stm32f4discovery

事情果然沒那麼順利, 在我將模擬器的程式移植到 stm32f4discovery 後, 沒什麼問題, 提示符號出來了, 但是打下 (+ 1 2) 之後, 程式沒有印出預期的 3, 而是停止不動。猜測是 stack 問題 (又是 stack), 將 stack 改大一點就正常執行了。在 x86 記憶體很大, 不太容易遇到 stack 太小的問題, 但在 stm32f4discovery, 記憶體不大, 只有 192k, 考驗我的程式能力。

下面影片是在 minicom 的執行結果:



後來知道了 ccm 這東西, 把 stack 移到 ccm, 成功擠出更多記憶體。

支援 backspace

這個常見的的功能還真沒那麼簡單, call library 果然比較舒服, 思考良久之後, 決定使用 deque 來完成這個功能, 我參考了 c++ 的 std::deque, 實作了一個 MyDeque, 雖然我用的是 c++, 不過作業系統之前沒有 std::deque 可以用。

MyDeque 提供以下 member function:
push_front() 給 ungetch() 用
pop_front() 在 getchar() return 時傳最前頭的 char
push_back() 把輸入的 char 存到這個 deque
pop_back() 提供了 backspace 的功能

因為這個 mydeque 需要成為一個 global variable, 所以沒有提供 ctor, 避免 compile 不過的問題 (你很疑惑為什麼吧?), 不過這不是什麼難題, 我使用了 init() 來變通, 得自己呼叫 mydeque.init(); 來作初使化的動作, 也如你預期的, 我老是忘記 call .init(), 每每在驚呼「為什麼?」之後才想到自己的疏忽。

使用了一大堆 global variable, 完全不是 c++ 哲學, 就跟你說了, 這是一個長的很像 c 的 c++ 程式。

為了支援 backspace 沒想到要多做一個 class, 這是經過深思熟慮後的想法, 也才決定用 deque (念做 deck), 這還真是個神奇的資料結構。

下面影片顯示支援 backspace 的操作:



不過這個實作還有點問題, 超過 MyDeque 的大小, 就會有問題, 所以我把 MyDeque 設到 128 個 int 大小, 暫時躲避這問題。

line edit history

20141115 我加上了 line edit history 的功能, 按下 up/down 就會把之前打過的指令取出來, 很基本的功能吧! 但要實作這個功能可花了我好大的力氣。

我寫了一個 deque 的 template 的版本, 一個 CString class 用來支援這樣的功能, 所以前面那個 MyDeque 被移除了。我第一次覺得 c++ template 這麼好用, 感動到痛哭流涕。雖然 c++ 現在複雜的不像話, 不過程式員只要選擇自己要用的部份就好了, 重點是把程式寫出來, 而不是用上什麼新特性。這個程式沒有 malloc/free 還不是照樣可以完成。

偵測 up/down key 是個小問題, 答案分別是: up: 27 '[' 'A' down: 27 '[' 'B' right: 27 '[' 'C' left: 27 '[' 'D'

要抓出 3 bytes 才能判斷是哪一個方向鍵。

而 scanner 程式整個重新改寫。辛苦完成的 MyDeque 派不上用場了, 以下影片示範這個功能:



當做出 history 功能時, 自己都覺得很酷, 這個功能真是無敵好用。

這個程式集 os 觀念和 scheme interpreter 之大成。是繼 simple os 之後的心血, 所有的東西都自己打造, 很有成就感。

這裡有篇履歷的文章: How the HR department and a programmer reads your resume? 我結合 os, interpreter, 可以加 20 分嗎?



疑, 這次怎麼沒有提供 source code, 因為這次的 souce code 分佈在 3 個地方, 太麻煩就不列了。有興趣的朋友一定會自己發問的。

寫下這篇文章很久之後, 我終於整合好所有程式碼,

source code:
https://github.com/descent/simple_scheme

可以使用 p103 這個平台編譯, 這是跑在 qemu 模擬器上。

好久沒做烘焙產品了, 該來做一個蛋糕慶祝一下, 犒賞自己。