mruby/c kaigi #03

mruby/c kaigi #03 @mruby/c kaigi #03 東の発表

mruby/c kaigi #03 ● mruby/c 3.1 出しました ● このRAM使用量削減に大きな役割を果たした

mruby/c kaigi #03 メモリ管理 mruby/c のメモリ管理に関する設計と実装

mruby/c kaigi #03 メモリ管理 ● ● ● 縁の下すぎて、誰にも望まれていない（かもしれない）発表 ハマると結構面白い Ｃ言語の話です

mruby/c kaigi #03 もくじ ● メモリ管理の概要 ● TLSFアルゴリズム ● 高速化 ● RAM利用率改善（使用量削減） ● そのつぎとまとめ

mruby/c kaigi #03 メモリ管理 ● ● やっていることは、 – 必要なサイズのメモリを任意のタイミングで確保 – 使い終わった不要なメモリを返す（解放） 一般に malloc / free int main() { char *p1 = malloc( 100 ); strcpy( p1, "Hello " ); strcat( p1, "mruby/c" ); puts( p1 ); free( p1 ); return 0; } // メモリ確保 100 bytes // メモリ解放

mruby/c kaigi #03 メモリ管理 ● ● ● Rubyプログラム等、ある種のシステムでは小さいメモリブロッ クを高頻度で確保、解放する特性がある 組込システムの libc は、全体メモリサイズの観点から、高頻度 の malloc/free には向かない実装が多い（と聞いた） 独自のメモリ管理を実装することに

mruby/c kaigi #03 メモリ管理 ● メモリプールをブロックに分け、双方向リンクリストで管理する ● Boundary Tagアルゴリズム ● 各ブロックの先頭にヘッダをつけてブロックの属性を管理する used tail = 1 free = 1 size prev block free tail = 0 free = 0 size prev block used tail = 0 free = 1 size prev block tail = 0 free = 0 size prev block メモリプール全体 free flag tail flag free size prev block typedef struct USED_BLOCK { unsigned int t : 1;// flag tail unsigned int f : 1;// flag free content １ブロック USED_BLOCK / FREE_BLOCK uint32_t uint32_t } USED_BLOCK; size; prev_offset;

mruby/c kaigi #03 メモリ管理 メモリプールの先頭からリニアサーチする？ used tail = 1 free = 1 size prev block free tail = 0 free = 0 size prev block used tail = 0 free = 1 size prev block メモリプール全体 tail = 0 free = 0 size prev block ● 問題はメモリの確保時に空きブロックをどうやって探すか free typedef struct USED_BLOCK { unsigned int t : 1; // flag tail unsigned int f : 1; // flag free flag tail flag free size prev block ● content １ブロック USED_BLOCK / FREE_BLOCK uint32_t uint32_t } USED_BLOCK; size; prev_offset;

mruby/c kaigi #03 TLSFアルゴリズム ● TLSF (Two-Level Segregated Fit) Dynamic storage allocation for real-time embedded systems (M. Masmano, I. Ripoll, and A. Crespo). Real-Time Systems Symposium, Work-in-Progress Session. Cancun, Mexico, December 2003. ● ● ● 2のべき乗の分類の下に、さらに細かい分類を行うことでメモリ利 用効率を改善する 最適なサイズのブロックを即座に見つけだせる (とあるが、実際にはGood-FitでありBest-Fitはしない) どのような状況でも同じ時間で動作し、最悪時間が存在しないので リアルタイムシステムに向いている ※ Wikipediaより引用

mruby/c kaigi #03 TLSF 空きメモリ管理 ● ● 空きメモリは、ヘッダ情報に加え、空きメモリ管理用テーブル を使って管理する 空きメモリブロックを、そのサイズごとにテーブル登録 空きブロックテーブル ＼ SLI FLI ＼ 0 1 2 0 * FREE_BLOCK 0000-000F 0010-001F 0020-002F 0070-007F 1 0080-008F 0090-009F 00A0-00AF 00F0-00FF 2 0100-011F 0120-013F 0140-015F 01E0-01FF 8000-8FFF 9000-9FFF A000-AFFF F000-FFFF … 7 ・ ・ 9

mruby/c kaigi #03 メモリ確保時の動作 ● メモリ確保時は、要求するサイズを（２進数の）6bit目で分離 して計算する 15 14 13 12 11 10 9 8 7 6 5 FLI 4 3 2 1 0 ignore SLI ● ● ● First Level Index, Second Level Index FLIは、上からの何番目のビットが立っているかを調べる ⇒ 0〜9 SLIは、FLIの値に応じて左にスライドし、そこの3bitを得る ⇒ 0〜7

mruby/c kaigi #03 メモリ確保時の動作 ● FLI,SLIの値から空きブロックが検索できる 15 14 13 12 11 10 9 8 7 FLI = 0〜9 6 5 4 3 2 SLI = 0〜7 1 0 ignore ＼ SLI FLI ＼ 0 1 2 0 * FREE_BLOCK 0000-000F 0010-001F 0020-002F 0070-007F 1 0080-008F 0090-009F 00A0-00AF 00F0-00FF 2 0100-011F 0120-013F 0140-015F 01E0-01FF 8000-8FFF 9000-9FFF A000-AFFF F000-FFFF … 7 ・ ・ 9

mruby/c kaigi #03 高速化

mruby/c kaigi #03 高速化 NLZ ● FLIは、上位から何番目のビットが立っているかを計算する ● 言い換えると、上位からゼロが何個あるかを数える ● NLZ (Number of Leading Zeros) (e.g.) 0 0 1 0 0 0 0 0 0 ⇒2 0 0 0 0 0 1 0 1 0 ⇒5

mruby/c kaigi #03 高速化 NLZ ● FLIは、上位から何番目のビットが立っているかを計算する ● 1bitずつシフトしながら15bit目が1になるまでの回数を数える？ 15 14 13 12 11 10 9 8 7 6 bit shift int nlz16( uint16_t x ) { int r; for( r = 0; r < 16; r++ ) { if( (x & 0x8000) == 0x8000 ) break; x <<= 1; } return r; } ● もう少し工夫したい。 5 4 3 2 1 0

mruby/c kaigi #03 高速化 ● ● CPUが持つハードウェア – ゼロ比較器（フラグレジスタのゼロフラグとして見える） – バレルシフタ（複数ビットを1クロックでシフト） ISA（機械語）が持つ特性 – ● NLZ 大きな即値を使うと時間がかかるCPUがある アルゴリズム – ２分法

mruby/c kaigi #03 高速化 ● 2分法を使って上位から何番目のビットが立っているかを計算 15 ● ● ● NLZ 14 13 12 シフト演算による２分法 （バレルシフタ使用） ゼロ比較 （フラグレジスタに自動的 に反映される） 小さい数 11 10 9 8 7 6 5 4 3 2 1 int nlz16( uint16_t x ) { if( x == 0 ) return 16; } int n = 1; if((x >> 8) == 0 ) { n += 8; x <<= 8; } if((x >> 12) == 0 ) { n += 4; x <<= 4; } if((x >> 14) == 0 ) { n += 2; x <<= 2; } return n - (x >> 15); 0

mruby/c kaigi #03 高速化 NLZ 比較 ● 素朴な方法 ● ● ● ● 1bitずつシフト （バレルシフタ未使用） 0以外の数 0x8000と比較 （比較命令が必要） 大きな数（0x8000） 高速化 ● ● ● シフト演算による２分法 （バレルシフタ使用） ゼロ比較 （フラグレジスタに自動的 に反映される） 小さい数 int nlz16( uint16_t x ) { int r; for( r = 0; r < 16; r++ ) { if( (x & 0x8000) == 0x8000 ) break; x <<= 1; } return r; } int nlz16( uint16_t x ) { if( x == 0 ) return 16; int n = 1; if((x >> 8) == 0 ) { n += 8; x <<= 8; } if((x >> 12) == 0 ) { n += 4; x <<= 4; } if((x >> 14) == 0 ) { n += 2; x <<= 2; } return n - (x >> 15); }

mruby/c kaigi #03 高速化 ● NLZ 書籍「ハッカーのたのしみ」にも掲載されている有名なコード （私が考案したわけじゃない、昔からあるコード） ● CPUが同等の機械語を持っている場合もある ● バレルシフタを持たないCPUなら素朴なコードの方が速い ● パイプラインが深いCPUなら分岐を使わないアルゴリズム

mruby/c kaigi #03 RAM利用率改善

mruby/c kaigi #03 利用メモリの拡大に関する改善 ● 当初最大64KBまでしかサポートしていなかった ● 64KB (16bit) 以上のメモリを使いたいという要求 USED_BLOCK / FREE_BLOCK flag tail flag free size prev block １ブロック ● size項 16bit ⇒ 24bit uint16_t uint32_t ● SCSK九州 1 unsigned int unsigned int content t : 1; // flag tail f : 1; // flag free uint16_t size; uint16_t prev_offset; ビットフィールドを使って拡大 size; size : 24; 三牧氏からのプルリク 後に、ビットフィールドとマルチスレッド（排他制御）との相性の悪さから廃止

mruby/c kaigi #03 利用メモリの拡大に関する改善 ● ● ● ● 2 TLSFとFirstFitの併用 64KBを越えるメモリの確保依頼が来たら、FirstFitアルゴリズ ムに切り替える mruby/cのプログラム特性上、小さなサイズの malloc / free が たくさん発生し、大きいサイズはあまり発生しない （良い）副作用として、メモリの空きが少なくなっても、残っ た空きメモリを有効に使える可能性が増した

mruby/c kaigi #03 メモリリンクヘッダについての改善 全てのメモリブロックについていて、典型的には12バイト 12bytes ● 12bytes free tail = 0 free = 0 size prev block used tail = 0 free = 1 size prev block tail = 0 free = 0 size prev block typedef struct USED_BLOCK { unsigned int t : 1; // flag tail unsigned int f : 1; // flag free (padding 30bit) uint32_t size; uint32_t prev_offset; } USED_BLOCK; 4 bytes 4 bytes 4 bytes used 12bytes tail = 1 free = 1 size prev block ● 12bytes もったいないので、縮小できないか考える free

mruby/c kaigi #03 最後尾フラグの廃止 ● flag tailは、最後尾ブロックかを判断するフラグ ● 最後のブロックが usedからfreeになるときにのみ使用する free used size; prev_offset; tail = 1 free = 1 size prev block uint32_t uint32_t } USED_BLOCK; tail = 0 free = 0 size prev block used typedef struct USED_BLOCK { unsigned int t : 1; // flag tail unsigned int f : 1; // flag free content tail = 0 free = 1 size prev block flag tail flag free size prev block リンクリストの最後にサイズ０の決して解放されないブロック （番兵）を置けば、flag tail が不要になる tail = 0 free = 0 size prev block ● free

mruby/c kaigi #03 最後尾フラグの廃止 リンクリストの最後にサイズ０の決して解放されないブロック （番兵）を置けば、flag tail が不要になる ● サイズは、1bit しか削れない ● フラグ操作のコードが不要になる – 速度向上 free free = 0 size prev block uint32_t uint32_t } USED_BLOCK; free = 1 size prev block used typedef struct USED_BLOCK { unsigned int f : 1; // flag free used size; prev_offset; free free = 0 size = 0 prev block コードサイズ縮小 free = 0 size prev block – free = 1 size prev block ●

mruby/c kaigi #03 前ブロックサイズの追い出し 前ブロックに関する情報は以下の場合にのみ必要となる ... – 空きならばブロック同士をマージする free flag free size prev block usedブロックの解放時、前ブロックが空きブロックかを判定 flag free size prev block ... – flag free size prev block ● free used ... typedef struct USED_BLOCK { unsigned int f : 1; // flag free uint32_t uint32_t } USED_BLOCK; ... size; prev_offset;

mruby/c kaigi #03 前ブロックサイズの追い出し 前ブロックが利用中か空きかのフラグをもうけて、prev_block の情報は直前のfreeのエリアに追い出そう free prev block flag free prev in use size free flag free size prev block どうせ使ってないエリアなんだし flag free size prev block – flag free prev in use size ● used used typedef struct USED_BLOCK { unsigned int f : 1; // flag free unsigned int p : 1; // prev in use uint32_t } USED_BLOCK; size; ※ glibcからアイデア借用

mruby/c kaigi #03 フラグビットはsizeへ含める ブロックサイズは 4byte align しているので、下 2bit は必ず0 ● ならば、size の下 2bit をフラグとして使おう flag free prev in use size ● used typedef struct USED_BLOCK { unsigned int f : 1; // flag free unsigned int p : 1; // prev in use uint32_t } USED_BLOCK; size;

mruby/c kaigi #03 フラグビットはsizeへ含める ブロックサイズは 4byte align しているので、下 2bit は必ず0 ● ならば、size の下 2bit をフラグとして使おう flag free prev in use size ● used uint32_t } USED_BLOCK; 31 size (f,u) size typedef struct USED_BLOCK { unsigned int f : 1; // flag free unsigned int p : 1; // prev in use used 30 29 28 ... size; 3 2 1 free typedef struct USED_BLOCK { uint32_t size; } USED_BLOCK; 0 use

mruby/c kaigi #03 解放されることのないメモリブロック ● クラス定義などは、定義はあっても undef は無い ● つまり確保はあっても解放はされないメモリブロック (f,u) 解放用の情報そのものが要らなくない？ size ● used typedef struct USED_BLOCK { uint32_t size; } USED_BLOCK;

mruby/c kaigi #03 解放されることのないメモリブロック ● クラス定義などは、定義はあっても undef は無い ● つまり確保はあっても解放はされないメモリブロック ● 解放用の情報そのものが要らなくない？ used ● typedef struct USED_BLOCK { } USED_BLOCK; 12bytes あったヘッダが 0bytesに！

mruby/c kaigi #03 解放されることのないメモリブロック ● しかも、ここにちょうど都合良く、絶対解放されないメモリブ ロックがあるし 番兵ブロック ● used size free size used size free size size used mrbc_alloc_no_free() 関数で確保するメモリは、番兵ブロック を前方向に拡張して確保するようにする

mruby/c kaigi #03 結果（比較） flag tail flag free size prev block 一つでは微々たるものだが、大量のメモリブロックが発生する ので馬鹿にできない typedef struct USED_BLOCK { unsigned int t : 1; // flag tail unsigned int f : 1; // flag free (f,u) ● 12bytes あったヘッダを 4bytes に減らした typedef struct USED_BLOCK { uint32_t size; } USED_BLOCK; size ● uint32_t uint32_t } USED_BLOCK; size; prev_offset;

mruby/c kaigi #03 そのつぎとまとめ ● ● ● ● とあるプログラムのメモリ確保と解放のプロ ファイル 同程度のサイズの確保と解放が連続する 解放要求があってもすぐにメモリプールに入れ ずに「いましがた解放キャッシュ」をつくって 取っておくとよいかも これも既に glibc の malloc がそうなってたよ... alloc(120) alloc(36) alloc(60) alloc(52) alloc(32) free(52) alloc(52) alloc(32) ... alloc(60) alloc(60) alloc(60) free(60) alloc(60) free(60) free(60) alloc(60) free(60) free(60) alloc(60) alloc(60) free(60) ...

mruby/c kaigi #03 そのつぎとまとめ ● RealtimeOS 下で複数のVMを動かすケースに対応していない – ● alloc, free のタイミングで Lock かけて動かしてみた – ● え？ 70%の速度ダウン orz... 真面目に作るしかないね – HALの拡張がいるね – メモリもふんだんにいるね

mruby/c kaigi #03 そのつぎとまとめ ● ● ● メモリ管理モジュールを、mruby/c VM の特性に適した独自実装 とすることで、速度向上と使用率向上を達成できた 他人の知恵を拝借しまくるだけでも、けっこういける このモジュールは、VMと密結合しているわけではないので、こ れ (alloc.c) だけで別プロジェクトでも使える – ● ゲームなどでは、TLSF の alloc を自作する例があると聞いた もう少し速くなるかも？ おしまい