Orz日記 by Akio Morita

_ [SAD]SAD stackアクセスの抽象化

SAD stackの抽象度の低い利用例

• tfoverride - stack上に積み込んだ引数列を stack上のitastk/vstkのindexからリスト構造のiad/iav扱いでtfsortlへ引き渡す
  • vstk上の並びが、rlistから見えることを期待している
  • 素直な修正は、ad/av配列渡しにする(on stackなので両方実体が実在する)
    • tfsortl自身の用途では、Listコンテナのiad=0 or iav=0のケースがあるので、pointer渡しが望ましいが interface宣言が必要になる
• tfevalwitharg @ src/tfdset - tfsevalの呼び出しでstack上に展開したリストのiad/iavをtfsevalへ渡している
  • tfseval APIには、tfoverrideの呼び出すtfsortlと同様にiad=0/iav=0のshortcutケースが存在する

• ivstk - Real格納部のvstk側が空いている際に、ivstk経由で整数型のメモを行う

• stringbuf - on stack割当てとheap割当てをサポートし、同一のハンドルでstackとheapにアクセス出来る(ilistとitastkのアドレス空間が同一)を仮定している(2019/12/05追記)
  • 主要なバッファ操作コードは、src/tfprinta.f
  • heap割当て時は、itfaloc_globalでString型コンテナを割り当てるので、開放が必要
  • 呼び出し側はすべてon stack優先割当てを要求している
    • on stack割当ての場合は、Stringへの変換時にcopyしている

_ [SAD]module function on LLVM/flang

どうやら、module functionに割り当てられるシンボルの符号化規則はGNU Fortranとは異なるようである

従って、module functionをC側から呼び出す場合は、ISO_C_BINDINGとBIND(C)を使ってC互換ABIで関数定義するのが移植性的には正しい模様

伝統的なcommon blockのシンボル割当ては同様の模様

_ [SAD]tfsortlの書き直し

• 並べ替えるリストを配列渡しで受け取りたいので、C側で再実装する
  • エンジン部は、標準ライブラリを使う qsort(3) とか mergesort(3)とか
  • ドライバ部は標準化出来る
  • 比較関数に並べ替えるべきリストの情報を渡さねば成らない
    • 同時に走らないなら、SAD stack上にポインタを置く
    • 別解として、*sort_b(3)でblocks内の定数としてポインタを渡す
    • blocks拡張が有効な場合、__BLOCKS__マクロが定義される
    • 類似の機能に、GCCのNested Function拡張がある
      • 関数スコープ内で定義された関数を関数ポインタ扱いで渡せる(ただし、定義スコープ外では保証が無い)
  • ad/avのみのリストのSortに関しては、duplicate済みのad/av配列要素のswapで実装可能になるので、間接参照の分だけ最適化出来る
• CanonicalOrderの実装で、NaNの順序を明確にする必要がある
  • また、内部表現の異なるNaN間の順序はどうするか？
    • 同一元とみなす or 内部表現で順序を付ける(isnan + integer-castが必要)

_ [SAD]SAD stack backend

ごそごそ整理を実施

• *stk array equivalenceを配列ポインタへ置き換え
• *stk配列ポインタの有効化範囲は、スタックの有効領域に限定
  • range checkerを使えば、スタック境界越えを検知出来る
• *stk配列ポインタの割当て部とSAD stackの初期化部を分離
  • 途中からのスタック拡張を想定
  • mmap/mprotectでガード付きstack pageの割当てとSEGVハンドラによる実装を想定
  • mmap + カナリアページ/mprotectなハードフォールトでevalエンジン側でカナリアチェック(signalを使わない)実装もありか？
• 現行は後方互換な設定を採用している
  • *tastkとrlistのアドレス空間を整合
  • *tastkとvstkのイメージ距離をivstkoffsetに格納

次は、rlist回りの配列ポインタ化か？

• とりあえず、実行形式・拡張モジュールの更新が一段落するまで後方互換を維持
  • 現行のcommon変数rlistをrlist0へリネームして残す
  • 配列ポインタのアドレスイメージは、現行のrlist互換を維持する
  • src/pfalloc.fの inimemをオーバーホール
    • rlist配列ポインタの初期化
      • 第一段階 - 後方互換のため割当て済みrlist0から初期化する
      • 第二段階 - rlist0を排除して、初期ブロックをmallocで割り当てる(但し、rlistポインタのインデックスは調整する)
    • pfallocのルートノードの初期化

ivstkoffsetが現れるコード

• stringbuf系(src/tfprinta.fなど)
  • stringbufをSAD stackに割り付けるケースで、stringbufインデックスがon stackかどうかの判定に使用(2019/12/23追記 mst/ivstkoffsetではなく、vstk1のlbound/uboundで判定するように変更済み)
  • stringbufのアクセスは、rlist/tastk空間の互換性を仮定
    • on stack割付を無効化すれば、ivstkoffsetの影響はなくなる
  • stringbufのスコープが局所なら、allocatable配列を含む構造型で再実装すべきか？
    • Fortran的には変数スコープ離脱時に自動開放されることが期待出来る
    • C側からも任意に利用するならwrapper APIを設けるか、C側で実装してC_PTR渡し or ハンドラ渡しとすべき
    • allocatable配列の恩恵を受けるには変数スコープをFortran側に持たせる必要が有るため、C側でalloc/free出来ない(ポインタ・ハンドルを渡してwrapper API経由の操作は可能)

• tfsortl
  • tfreplace/tfoverride等からstack上に展開した要素列のソートをする際に、on stackな配列のrlistインデックスを渡している
  • rval_t配列のインデックス生成にivstkoffsetが必要
  • rlist/tastk空間の互換性が必要
  • 再実装するのであれば、stdlibの汎用のsortエンジンを使うか？
    • llvm/clang前提なら、sort_bでクロージャを渡せるが一般的ではない
    • qsort_r以外は、比較関数に文脈を直接渡せないのが難
    • overrideやreplace向けの同一要素の処理をどのように一般化するか？

• tfseval
  • stack上に展開した要素列をリストをして評価する際に、list containerの内部ベクトル互換なrlistに対するiad/iavインデックスで渡している
  • rval_t配列のインデックス生成にivstkoffsetが必要
  • rlist/tastk空間の互換性が必要
  • 比較的多数のstack展開演算子が相互依存している
    • Cポインタベースの実装を別途製作して、置き換えるべきか？

_ [SAD]equivalence array VS array pointer

memory allocator更新に向けて、equivalence arrayを参照しているコードを順次array pointer参照に書き換えているが、性能が下がっているっぽい

置き換え前

• 使用コンパイラ(以下同様)
  • flang 7.0g20191020
  • gfortran 9.2

*stk置き換え後

*list置き換え後

• gfortran -O2/-O3だと途中でSEGVする
  • 独立なポインタ間のメモリーイメージが重複しているが、level 2から有効になる-fstrict-aliasingオプションによって異なる型のarray pointerなので独立しているものとして最適化されている模様
  • そして、ISO Fortranには共用体は標準化されていない
    • ISO Cの共用体は言語仕様レベルで、メモリイメージが共用されることを宣言しているので、strict-aliasingルールの適用外になる
• WORKAROUND
  • -fno-strict-aliasingでコンパイルする(移植性は無い)
  • 最適化スコープ内で、同一領域に異なる型のポインタによる読み書きを避ける(コードの書き直しが必要/意図が見えにくい)
  • aliasを使わずに、TRANSFERで明示的に変換する(コードの書き直しが必要/煩雑になる)
  • setterを外部手続き・関数化して、最適化スコープを切断する
    • 対象ポインタは common block上に存在するので、呼び出した外部手続き・関数から更新可能。したがって、外部手続き・関数を跨いでarray pointer操作を最適化出来ないはず(未検証)

考察

• equivalence arrayからarray pointerへの置き換えで、Functionの性能が大きく下がっている
  • オブジェクトコンテナの参照頻度が高いベンチマークで影響が大きい
  • Fortranのarray pointerは、添字の下限・上限及びストライプ幅の概念を持つある種のスマートポインタなので、配列参照に比べて添字計算コストが高い模様(最低でも1乗算・1加算演算増える)

_ [SAD]作業アイデア

• SAD_RLIST_OFFSETのコンパイル時デフォルトの自動設定
  • mallocの繰り返しでアドレス割当てポリシーを検出して設定する
• SADスタックの環境変数による設定
  • SAD_STACK_SIZE環境変数からスタックサイズを設定可能にする
    • スクリプト外から設定できると運用上で便利
  • STACKSIZ変数(MAIN level)の初期値をどうするかが問題
    • ユースケースとして、STACKSIZ = 10 * STACKSIZなどのイディオムが実在するため、初期値に無効値を設定することが出来ない
    • 初期値からの改変を検知する形式では、明示的に初期値と同じ設定を行っているケースを識別出来ない
• mfalloc/pfalloc層の削除
  • mfalloc/freemeにより割当ては、italoc/tfreeで置換可能
  • italoc層からの割当て要求はhuge-page単位かつ、freemeで返却されないためlmallocで置き換えられる
    • italoc自体がアリーナを持っている
    • italocのアリーナ管理ブロックの割当ては、small chunk allocationに成っている
      • 初期化子でhugepageから余った部分をアリーナへ挿入する
      • italoc相当のまともなアロケータを実装する？
        • italocアリーナでのchunk管理構造体がchunk上に置かれる関係で、4word未満のchunkを収容出来ない

_ [SAD]range check

rlist pointerのrange更新コードを追加したので、添字検査を有効にして試してみたが、色々あってまともに添字検査が出来ない罠

• ilist(i, addr)系の参照でiが走るループが引っかかる
  • 領域は割付済みだが、Fortran配列の添字的には境界外なのも事実
  • ローカルにpointer参照を割り付けるのがFortran的には正しい？
• シンボル・文字列処理回りで、長さ付きcharacter・characterの配列・C_INT8_T配列を同一視して受け取るAPIが引っかかる
  • 特に別の型に複製する部分が酷いことになる
  • interface宣言付きで、コンパイル時にtype dispatchする or C_LOC経由で明示的に memcpyに渡す
    • C_LOCを使う場合、target属性が必要(面倒くさいことに)
• 無効参照(addr = 0な参照)のdereferenceを渡しているケースがある
  • 例えば、non-real typeなSAD objectに付随するrval部の参照
  • 正しくハンドルするには、参照の差し替え or type dispatchして即値渡しなので、conditional branchが増える
    • 3項演算子が無いので、コードが太る
    • C++のように、右辺値・左辺値を区別したoverloadが出来ないので、参照側で透過的な扱いが出来ない
    • 参照の生ポインタを透過的に渡すのであれば、NULLテストでおしまいなのだが…

一応、typo等に伴う無効参照等のバグが何件かかかっているので、無駄ではないがすぐに修正出来ない部分のrange checkを無効化するコストが高いのが難

_ [SAD]stack guard pageの挿入

stack over runをrange checkerではなく、MMUを使って検出するアイデア

基本的には以下の様に、3枚のguard pageで itastk及びvstk1領域を囲む

• guard pageは mprotect(2)で参照禁止とするため、stack領域をVM page sizeに丸める必要がある
• page alignmentを保証するために、stackはlmallocで直接確保する
• guard pageを挟むために、stack depthとvstk-offsetは別々に渡す必要がある
  • ivstkoffset依存のコードの一部は改訂が必要
• use_mmap時には、lmallocへのrequest sizeを調整する必要がある

実装してみた r5666

その過程で、src/track.fのバグ発見

• 初期状態 isp == isporgだと、ispはスタック外を指している
• tfmemcheckを1引数積んでる形で呼び出すが、スタック上になにも積み込んでいない(不定となっている)

_ [FreeBSD]www/firefox 71.0_4,1がbuild error

rev.520537で入ったfiles/patch-bug1556301が、includeしているmozilla/widget/mozwayland.hが見つからない(多分、Wayland環境向けのheader)

直前のnsAppRunner.hのincludeにfor IsWaylandDisabledというコメントがあるので、なんらかのifdefが必要そうな気配が…

nsAppRunner.hを調べるとIsWaylandDisabledの定義が、ifdef MOZ_WAYLANDで囲まれているので、ifdef MOZ_WAYLANDをあちこちに書く必要があるっぽぃ

_ [SAD]作業の方向性

とりあえずの優先順位

• ivtkoffset依存性の削除
  • tfsortl回り(影響範囲 Sort/Union/Override/Replace)
    • ad/av arrayをC pointer渡しで再実装する
    • BSD libcの qsort/msort/hsortをアルゴリズムに使う
    • 比較関数は、blocks拡張・Nested Function拡張を使う
    • まずは、Sort/Union系をsrc/tfSort_.cとして再実装する
    • 初期実装は、blocks拡張ベースで
  • tfseval回りのスタック展開・部分式評価コードの再実装
    • 長いリストの再帰展開に関しては、ヒープへの展開も考慮すべきか？
    • 境界トラップ無しだと、Overrun時にSEGVする(stack guardによって)
    • 再帰展開エラーを扱うには、APIの再設計が必要な可能性有り
• heap allocatorの整理
  • taloc2, taloc3等の複合allocatorの削除
  • mfalloc/freemeの置き換え
    • より高次のAPI italoc/tfreeへ置き換える
    • 一部のアライメント調整コード・部分返却コードを削除する
  • heapの部分返却コードの削除
  • heap allocatorの再実装
    • 管理領域を割当て領域から分離する
    • アリーナ管理を一元化する(large page/small page/italocの3層に分離している)
  • scope付きallocator frontendの整理
• stack indexの同一視の削除
  • stringbuf系をSAD stack上に配置するコードを削除する
    • on-heapなコードはほとんど未使用なはずなので、注意が必要
    • on-heapなbufferingコードを再実装すべきか？