# 分析紅黑樹

>[rbtree](https://github.com/devarajabc/box64/tree/rbtree_from_rv32emu)

實驗環境

Architecture:         	aarch64
  CPU op-mode(s):     	32-bit, 64-bit
  Byte Order:         	Little Endian
CPU(s):               	4
  On-line CPU(s) list:	0-3
Vendor ID:            	ARM
  Model name:         	Cortex-A72
	Model:            	3
	Thread(s) per core:   1
	Core(s) per cluster:  4
	Socket(s):        	-
	Cluster(s):       	1
	Stepping:         	r0p3
	CPU(s) scaling MHz:   33%
	CPU max MHz:      	1800.0000
	CPU min MHz:      	600.0000
	BogoMIPS:         	108.00
	Flags:            	fp asimd evtstrm crc32 cpuid
Caches (sum of all): 	 
  L1d:                	128 KiB (4 instances)
  L1i:                	192 KiB (4 instances)
  L2:                 	1 MiB (1 instance)
NUMA:                	 
  NUMA node(s):       	1
  NUMA node0 CPU(s):  	0-3
--skip--

檢查 cache 配置

$ getconf -a | grep CACHE
LEVEL1_ICACHE_SIZE             	0
LEVEL1_ICACHE_ASSOC            	0
LEVEL1_ICACHE_LINESIZE         	64
LEVEL1_DCACHE_SIZE             	0
LEVEL1_DCACHE_ASSOC            	0
LEVEL1_DCACHE_LINESIZE         	64
LEVEL2_CACHE_SIZE              	0
LEVEL2_CACHE_ASSOC             	0
LEVEL2_CACHE_LINESIZE          	0
LEVEL3_CACHE_SIZE              	0
LEVEL3_CACHE_ASSOC             	0
LEVEL3_CACHE_LINESIZE          	0
LEVEL4_CACHE_SIZE              	0
LEVEL4_CACHE_ASSOC             	0
LEVEL4_CACHE_LINESIZE          	0

>問題，為何兩邊數字對不上？

## 初步的實驗評估

### RSS(kbytes)

1.
|Benchmark|box64_rb_map|box64|
|---|----|---|
|aes|124968|125124|
|primes|30632|31088|
|miniz|49444|49688|
|norx|125820|126180|
|qsort|222828|230000|
|dhrystone|27772|27864|

總體來看，改進版 `box64_rb_map` 在所有測試中均有 RSS 的下降，其中 `qsort` 中降低的幅度最大，達到約 3.12%

2. box64+wine (VIRT/RES)

chess:
|Command|box64_rb_map|box64|
|---|----|---|
|wineserver|73636/42972||
|services.exe|5912M/75608||
|winedevice|5939M/85756|
|explorer|5877M/137M||
|plugplay|5665M/78252||
|svchost|5387M/59196||
|winedevice|6047M/140M||
|rpcss|5648M/68315|
|conhost|5270M/59712||
|chess|6449M/361M||

1. 測量每棵樹的節點數量變化量
-> 將每棵樹拆分
-> Add 就加一 remove 就減一 （紀錄目前為止的 Add 和 remove 數量）

#### 統計所有樹的種類
1. blockstree
2. mapallmem
3. memprot
4. mapmem
5. envmap
6. rbt_dynmem
7. dynamap
8. db_sizes

TODO: 列出 `data` 在不同樹上的意義

TODO: 統計每種樹的資料範圍(如果範圍夠小看看能不能放在 LSB 或是合併在其他地方)
TODO :檢查「映射記憶體範圍為 1 bytes 的節點」的 Predecessor 和 Successor 的記憶體範圍，看是否能合併。

### 統計每個節點被使用的次數、壽命
1. 在節點中新增變數 `long cnt` 在新增時設為 `0` ，在 `rb_get`, `rb_get_end` 中將增加 `cnt` 的值，並在刪除節點時檢查 `cnt` 的值，檢查是否有建立後未被使用的節點
2. 紀錄每個節點的壽命

typedef struct rbnode{
    struct rbnode_old *left, *right, *parent;
    uintptr_t start, end;
    uint64_t data;
+   long cnt; 
+   clock_t node_start;
+   clock_t node_end;
} rbnode;

1. box64 + wine chess
> [chss](https://docs.google.com/spreadsheets/d/1R5L-zYmJaBLCCnE-GCo56PBSVkCdqMBWw9Avlrx5J4k/edit?usp=sharing)

在建立的 54306 顆節點中，有 17886 顆完全沒有被使用到
其中：
blockstree: 0 次
db_sizes: 52 次
dynamap: 16697 次 (100%)
envmap: 1 次
mapallmem: 158 次
mapmem: 105 次
memprot: 873 次
rbt_dynmem: 0 次

## Orphan Nodes

檢查是否存在被建立後便不再使用的節點

首先要觀察紅黑樹節點所映射的記憶體片段是如何被使用的：
1. `rb_get`/ `rb_get_64`(此機制是為了能回傳地址？是！)
2. `rb_get_end`/`rb_get_end_64`
3. `rb_get_right` / `rb_get_left`

接著觀察哪些結構有使用紅黑樹
1. `box64context_t`

typedef struct box64context_s {
    // ...skip...
    uintptr_t           max_db_size;    // the biggest (in x86_64 instructions bytes) built dynablock
    rbtree_t*             db_sizes;
    // ...skip...
}box64context_t;

extern box64context_t *my_context; // global context 

2. `dynablock_t`

typedef struct dynablock_s {
    void*           block;  // block-sizeof(void*) == self
    void*           actual_block;   // the actual start of the block (so block-sizeof(void*))
    struct dynablock_s*    previous;   // a previous block that might need to be freed
    void*           x64_addr;
    uintptr_t       x64_size;
    // -- skip --
} dynablock_t;

### perf
> 參考 lab0-c 使用 [perf](https://perfwiki.github.io/main/) 、[Linux 效能分析工具: Perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)

比較 box64 的紅黑樹和使用 rv32emu 的紅黑樹 (box64_rb_map) 的執行結果(皆為 v0.3.5 d3d3fa25)
>參考 [ansibench](https://github.com/nfinit/ansibench), [rv8-bench](https://github.com/michaeljclark/rv8-bench)

#### cache-miss rate :
|Benchmark Name|box64_rb_map|box64|
|---|---|---|
|qsort|0.21%|0.27%|
|aes_x86|0.19%|0.27%|
|primes|30.88|30.91 |
|miniz|13.08%|13.50%|
|norx|0.35%|0.35%|

#### Dhrystone(1.1 -mc) :
|box64_rb_map|box64|
|----|----|
|6501|6410|

### TODO

1. 加入終止條件
2. RSS VSZ(Virtual Memory Siz)
3. Glibc 的記憶體分析

5. 設計使紅黑樹不旋轉的輸入
6. 增加測試單元
7. 新增 jserv/rbtree 的測試部分

### ps
問題：如何比較？ 逐個 COMMAND 比對？
比較 box64 紅黑樹執行 box64 + wine 在執行時的 RSS 和 VSZ

## 記憶體使用量分析
問題：如何測量紅黑樹操作「本身」的記憶體使用量？ 或是如何透過測試資料來換算？

## 相關 API 的規劃
1. 捨棄 `add_range_next_to` ，相關操作皆以 `add_range` 取代
2. 將 `rb_set`, `rb_unset` 等換成 `??_set`
3. `rbtree.h` 中只保留紅黑樹相關操作

### 是否有其他方式能取代用 `start` 和 `end` ?

統計每個節點的記憶體片段長度與範圍(統計 `add_range_next_to` 的輸入)
>[Chess](https://docs.google.com/spreadsheets/d/1YE85W67hUDpo5G4d8aSROA6lGgKxFDO3kCKfVj2ErBo/edit?usp=sharing)

列出前 5 名
|Size (bytes)| count|
|---|---|
|120|8995|
|1|3596|
|136|3270|
|128|2695|
|144|1574|

最大 4298276864 bytes

顯然用 56 bytes 去紀錄 1 bytes 的記憶體空間並不合理(佔 6.6%)
測試：如果片段長度為 1 就不加入

TODO:
追蹤邊角料 Orphan Nodes 的使用情況(找出時在用)＋bench mark

---

## Box64 的其他地方是否能用到紅黑樹

如何判斷是否能用紅黑樹？

typedef struct mapchunk_s {
    blocklist_t         chunk;
    rbtree_t*           tree;
} mapchunk_t;

typedef struct mmaplist_s 
    mapchunk_t          chunks[NCHUNK];
    mmaplist_t*         next;
} mmaplist_t;