HackMD
分析紅黑樹
實驗環境
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
問題，為何兩邊數字對不上？
初步的實驗評估
統計所有樹的種類
- blockstree
- mapallmem
- memprot
- mapmem
- envmap
- rbt_dynmem
- dynamap
- db_sizes
TODO: 列出 data 在不同樹上的意義
TODO: 統計每種樹的資料範圍(如果範圍夠小看看能不能放在 LSB 或是合併在其他地方)
TODO :檢查「映射記憶體範圍為 1 bytes 的節點」的 Predecessor 和 Successor 的記憶體範圍，看是否能合併。
統計每個節點被使用的次數、壽命
- 在節點中新增變數
long cnt在新增時設為0，在rb_get,rb_get_end中將增加cnt的值，並在刪除節點時檢查cnt的值，檢查是否有建立後未被使用的節點 - 紀錄每個節點的壽命
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;
- box64 + wine chess
在建立的 54306 顆節點中，有 17886 顆完全沒有被使用到
其中：
blockstree: 0 次
db_sizes: 52 次
dynamap: 16697 次 (100%)
envmap: 1 次
mapallmem: 158 次
mapmem: 105 次
memprot: 873 次
rbt_dynmem: 0 次
- qsort
Orphan Nodes
檢查是否存在被建立後便不再使用的節點
首先要觀察紅黑樹節點所映射的記憶體片段是如何被使用的：
rb_get/rb_get_64(此機制是為了能回傳地址？是！)rb_get_end/rb_get_end_64rb_get_right/rb_get_left
接著觀察哪些結構有使用紅黑樹
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
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 、Linux 效能分析工具: Perf
比較 box64 的紅黑樹和使用 rv32emu 的紅黑樹 (box64_rb_map) 的執行結果(皆為 v0.3.5 d3d3fa25)
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
-
加入終止條件
-
RSS VSZ(Virtual Memory Siz)
-
Glibc 的記憶體分析
-
設計使紅黑樹不旋轉的輸入
-
增加測試單元
-
新增 jserv/rbtree 的測試部分
ps
問題：如何比較？ 逐個 COMMAND 比對？
比較 box64 紅黑樹執行 box64 + wine 在執行時的 RSS 和 VSZ
| USER | PID | %CPU | %MEM | VSZ | RSS | TTY | STAT | START | TIME | COMMAND |
|---|---|---|---|---|---|---|---|---|---|---|
| jkchiu | 2967 | 2.9 | 1.5 | 172836 | 61096 | pts/2 | S+ | 12:12 | 0:00 | start.exe devel/bin/wine64 chess11.exe |
| jkchiu | 2974 | 14.7 | 1.1 | 73660 | 43092 | ? | Ss | 12:12 | 0:03 | /opt/wine-devel/bin/wineserver |
| jkchiu | 2980 | 2.7 | 1.8 | 6187208 | 70784 | ? | Ssl | 12:12 | 0:00 | services.exe el/bin/wine64 C:\windows\system32\services.exe |
| jkchiu | 2984 | 6.5 | 3.5 | 6009792 | 136776 | ? | Ssl | 12:12 | 0:01 | explorer.exe el/bin/wine64 C:\windows\system32\explorer.exe /desktop |
| jkchiu | 2986 | 3.2 | 2.0 | 5877736 | 77964 | ? | Ssl | 12:12 | 0:00 | winedevice.exe /bin/wine64 C:\windows\system32\winedevice.exe |
| jkchiu | 2997 | 2.8 | 1.8 | 5801696 | 72540 | ? | Ssl | 12:12 | 0:00 | plugplay.exe el/bin/wine64 C:\windows\system32\plugplay.exe |
| jkchiu | 3005 | 1.7 | 1.5 | 5516820 | 58788 | ? | Ssl | 12:12 | 0:00 | svchost.exe vel/bin/wine64 C:\windows\system32\svchost.exe -k LocalServiceNetworkRe |
| jkchiu | 3015 | 101 | 3.4 | 6192392 | 133624 | ? | Ssl | 12:12 | 0:21 | winedevice.exe /bin/wine64 C:\windows\system32\winedevice.exe |
| jkchiu | 3031 | 2.2 | 1.6 | 5783840 | 64404 | ? | Ssl | 12:12 | 0:00 | rpcss.exe devel/bin/wine64 C:\windows\system32\rpcss.exe |
| jkchiu | 3043 | 2.6 | 1.5 | 5396784 | 59912 | ? | Ss | 12:12 | 0:00 | conhost.exe vel/bin/wine64 C:\windows\system32\conhost.exe –unix –width 80 –heig |
| jkchiu | 3045 | 87.9 | 9.4 | 6597292 | 364740 | pts/2 | Sl+ | 12:12 | 0:17 | chess11.exe vel/bin/wine64 F:\home\jkchiu\Windows\chess11.exe |
記憶體使用量分析
問題：如何測量紅黑樹操作「本身」的記憶體使用量？ 或是如何透過測試資料來換算？
相關 API 的規劃
- 捨棄
add_range_next_to，相關操作皆以add_range取代 - 將
rb_set,rb_unset等換成??_set rbtree.h中只保留紅黑樹相關操作
是否有其他方式能取代用 start 和 end ?
統計每個節點的記憶體片段長度與範圍(統計 add_range_next_to 的輸入)
列出前 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;
