tls 解密



世の中には様々なメモリアロケータがありますが，ここでは某ゲーム開発解説サイトでも紹介されているTLSF(Two Level Segregate Fit)メモリアロケータのソースコードを読み，
メモリ上ではどのようになっているのかを図解してみたいと思います．なお，元々はCのコードですが，いちいちstructをtypedefしないなど省略している部分があります．
また，具体的な数値を出すために，ここでは64bit環境でアドレス長が8バイトである前提としています．

ソースコードはTLSFの公式サイトから2.4.6をダウンロードしてきています．

TLSFを使う場合の基本的な流れは次のようになります．

1. init_memory_poolであらかじめ確保しているメモリ(これをメモリプールと呼ぶ)にTLSF管理用のデータ構造を構築する
2. malloc_exでメモリ確保，free_exでメモリ解放を行う
3. destroy_memory_poolでメモリプールを破棄する(メモリプールそのものの解放は外部の責任となる)

最初にメモリプール上にTLSFの管理を行うデータ構造であるtlsf_tを構築します．
このあと詳しく解説しますが，tlsf_tはアドレス長が8バイトの環境では，
約6KiBのメモリを必要とするため，それよりも小さいサイズのメモリプールの場合，
初期化に失敗します．

また，メモリプールの先頭アドレスがアドレス長の倍数になっていない場合も初期化に失敗します．

この条件を満たしたら，メモリプールの先頭にtlsf_tのデータ構造が構築されます．

では，tlsf_tの構造体を見てみましょう．なお，実際のコードにある排他制御や統計のためのコードは省いてあります．

メモリプールの先頭を0番地だとすると，次のようになります．

tlsf_t

この図を書いてみて，area_headを後ろに持ってくるとパディングが消えるのでは，
とも思いましたが，他にもロックを追加できたり統計情報を追加できたりするので，
数バイトはいったん無視しても良いかなと．

ROUNDDOWN_SIZEのようにMEM_ALIGNを反転させたものとの&を取ると，
下位4ビットを削って16の倍数に切り下げることができます．
そして，ROUNDUP_SIZEのようにいったん15を足してから切り下げると
16の倍数に切り上げることができます．

では，次にGET_NEXT_BLOCKの実装を見てみましょう．これは非常に単純です．

まず，渡されたポインタをcharポインタにキャストして，渡されたオフセットバイト分進め，
そのアドレスをbhdr_t型へのポインタに変換して返します．
このbhdr_tはブロックヘッダを表す型です．この辺は時代を感じる命名ですね．

さて，初期化済みのケースが済むと，tlsf_tの部分を0クリアした上で，
tlsf_signatureにTLSF_SiGNATUREを設定します．
これ，初期化終わってから設定した方が良いのでは，という気もしましたが，
マルチスレッドとかじゃなければまぁ良いかと．

初期化済みのケースが終わったので，実際の初期化に入ります．
最初に，process_areaという関数にtlsf_tの直後のアドレス
(ROUNDUPで16の倍数になっている)と
そのアドレスからメモリプールの末端までのサイズを渡します．

process_areaの処理を見ていく前にbhdr_tの構造を見ておきます．

area_info_tについては，サイズの計算などで必要なのでここで先に出しています．

メモリ上でのそれぞれの構造体のイメージは次のような感じです．

未使用のブロックと使用中のブロックで，次のように使い分けられるわけです．

ptr.buffer[2]などのように範囲外にアクセスすることで実際のブロック部分にアクセスできるわけです．

最初のブロックはエリア情報用のブロックなので，実際に利用するためのブロックを構築します．

bはibの直後になります．次にbのサイズを計算します．

BHDR_OVERHEADは次の図の緑部分，bhdr_tの先頭部分のサイズです．

ここでちょっと気になるのが，このブロックを使用中として扱うことです．
前のブロックはibなので使用中というのは分かります．
でも，何故このブロックが使用中なのでしょう?
しかもその直後に未使用ブロックとして初期化します．

次にlb (last blockでしょうか?)を構築します．

最後に，ibのところに作る予定だったarea_info_tを構築します．

process_areaの最後ではメモリプールは次のような状態になっています．

さて，init_memory_poolの処理に戻ります．

USED_BLOCKやPREV_USEDなどのフラグがサイズに入っているので，BLOCK_SIZEでマスクするのを忘れずに．

そして，次のブロックヘッダを取得します．

ソースコードとしては，このあとのブロックが未使用の場合の処理があるのですが，
初期化の場合はlbが返ってきて，USED_BLOCKであることが分かっているので
スキップします．

この2つの数値を使うのがTLSFがTwo Levelと言う理由です．

では，MAPPING_INSERTの中を見てみましょう．

論文では，例として460をflとslに分解しています．

すると，次のような関係式が成り立ちます．

このことから，flは次のように求まります．

つまり，flはsizeを表す2進数の式で最大の

のNを得れば良い．

都合の良いことにWindowsには_BitScanReverseという最上位ビットから

最下位ビットに向かって1となっているビットを探し，

そのインデックスを最下位ビットからのインデックスで返す関数があります．

clangやgccにも似たような関数があるため，これを求めるのはたやすいことです．

次に，slを求める式を少し変形してみます．

これを展開すると，次の式になります．

2のべき乗による除算は右シフトとみなせるので，

最終的に次のようなコードが出来上がります．

ただし，下位6ビットで表せる小さいサイズのブロックは0とみなすようになっているので，

最後にFLI_OFFSETを引いています．

FLI_OFFSETを先に引いてしまうと計算が合わないので注意しましょう．

ここで，sizeが128未満の場合，slはSMALL_BLOCK / MAX_SLI == 4で割るようになっています．

とにかく，新しい未使用ブロックを追加する準備が出来たので，

次はINSERT_BLOCKというマクロを呼び出して，実際にブロックを追加します．

これで，tlsfの管理用のデータ構造に用意したブロックが登録されました．

最後にこれは不要なのですが，lbをtmp_bとして取得し，sizeに

PREV_FREEを設定し，bをlbの前のブロックとして登録する処理があります．

これは，free_exを流用しているが故の処理ですね．

init_memory_mapに戻り，最後にibに作ったarea_info_tへのポインタを

tlsfのarea_headに登録したら，ようやくメモリプールの初期化が完了です．

最終的にメモリプールは次のような状態になっています．

この図を見ていると，いくつかのprev_hdrを初期化していないので若干不安になりますが，

この後の処理を見ていくと問題無いことが分かります．

では，早速このTLSFを使ってメモリを確保してみます．

TLSFでメモリを確保するには，次のようなmalloc_ex関数を呼びます．

まず，sizeをMIN_BLOCK_SIZE(==16)以上の16の倍数に補正します．

次に，このサイズが入るべきブロックを探すため，MAPPING_SEARCHという関数を

呼び出します．

この関数を呼び出すと，flとsl以外に，sizeも変化することがあります．

具体的に処理の中を見てみます．

sizeがSMALL_BLOCKより小さい場合についてはMAPPING_INSERTで同じ処理を見たので

スキップします．

次に_tに関する部分は，次のように書くと何となくどこかで見たことがあるような気がしませんか?

そうROUNDUP_SIZEと同じです．少し具体的な数字で計算してみましょう．

128，つまり

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/2232.html