SAD部屋 - Ticket-40 Diff
- Added parts are displayed like this.
- Deleted parts are displayed
like this.
! 長いリストのJoinに失敗する
:Priority:Normal
:Reporter:amorita
:Status:New
:Assigned to:?
:Version:4512
:Milestone:?
:Created:2017-01-23
!! Description
Joinは、内部的に引数列から合成されるリストをSADスタック上に展開するので、
十分に長いリストのJoinは(Range等で生成可能であっても)必ず失敗する
引数からリストの展開処理を行なう''tfgetllstkall_''にスタック境界チェックが
実装されてないため'''General::stack'''メッセージが帰ってきた時点で、
スタック境界から先の領域が破壊されている可能性がある
また、''tfgetllstkall_''を使用しているMap等では、事後のスタック境界チェックも
実装されていないため、境界違反でクラッシュする
!! Attachement files
{{attach_map('Ticket-40')}}
{{attach_form('','')}}
!! Changelog
!!!amorita (2017-01-23 (月) 14:43:40)
メモリ破壊を避けるには、''tfgetllstkall_''がスタック上に書き込む前に
十分な空き領域があることを確認する必要がある
* リスト展開前に、リスト長相当のスタックが空いていることを確認する
** リストに Null[]等が含まれて展開長が短い場合も、境界検査で弾かれる可能性がある
また、スタック境界違反を上位層に返すための戻り値が必要である
* logical型・integer型の返り値で、境界違反の有無を知らせる
** 返り値の割り当てに関しては、議論の余地がある
*** 成功を真とする真偽値を返す
*** 境界違反を真とする真偽値を返す
*** 成功時に 0、それ以外は負の整数でエラーコードを返す(libc類似の設計)
* ''irtc''引数経由で'''General::stack'''メッセージを返す
** 上位層で、fallbackを実装可能な場合、メッセージ生成処理が無駄になる
!!!amorita (2017-03-13 (月) 11:04:19)
スタック非依存のリスト結合処理の実装に必要なもの
* ヒープ上の仮コンテナ
** alloc/freeは最低限必要
** Map等の実装では、endイテレータに対するappend操作が必要
** 事前に長さを確定出来ないケースでは、reallocも必要
*** よって、格納するコンテンツは、仮コンテナのアドレスを保持してはならない
**** ハンドルからの相対アドレスなら問題ないが、Object Store内のインデックスと区別する方法が問題になる
** 後述のリストコンテナ生成を想定するとrangeイテレータかrandom accessイテレータが必要
* ヒープ上の仮コンテナからリストを生成するAPI
** コンテナをObject Reference Arrayとして実装するのであれば、range API形式？
** 機能的には、itflist, itflist0, itfcompose frontendとitfcrelistm backend相当の機能は必要
*** itfcrelistmは、type/addr arrayと rval arryaが独立して存在することを前提とするAPI設計になっている
**** これのコンテナ参照版を実装すれば、itflist, itflist0, itfcompose frontendは自然に実装できる
**** コンテナイテレータが減算可能であれば、range API形式で実装出来る
**** 設計界面の統一性的には、Headもコンテナの要素型で渡すべき？
* リストコンテナに対するイテレータもしくは仮コンテナへの展開API
** 前者の実装が可能であれば、後者は自動的に実装可能
** イテレーション自体は、''tfgetllstkall_''の内部処理そのもの
*** イテレータは現在のイテレーションの状態を保持する必要がある
*** 用途から、前進イテレータが有れば十分
*** 終端検出は必要だが、どのように実装するか？
**** イテレータに対するquery functionを実装する
**** 終端を意味するイテレータの状態を定義して、イテレータの比較で実装する
!!!amorita (2017-03-22 (水) 10:57:22)
* 用意すべき型について
** SAD Objectの参照型(SAD reference → sref)
*** 抽象型 sref_t
*** ポインタ型 sref_p
** srefの仮コンテナ(bufferが適当か？)
*** コンテナ型 sref_buf_t
**** size - 割り当てたsref_t配列の大きさ
**** length - 格納した sref_tの数(lengh =< size)
**** array - sref_t配列へのポインタ(sref_p型)
* 仮コンテナの操作APIの実装方針
** Fortranへの互換性は、考慮せずに C側のみ用意する
*** Fortran-C間の構造体とポインタ運用互換性に問題が有る
*** 構造体渡しや、構造体を返す関数の実装の標準化が怪しい
** 実装作業は、''src/sim/sad_newapi.c''当りで行う
*** パス名は、ある程度初期実装が固まった後に整理？
*** 公開APIに関しては、API本体の実装後に''src/sim/sad_api.h''側で公開
**** ヘッダーを分離するかは、後日検討する
!!!amorita (2017-03-23 (木) 16:20:23)
itflist/itflist0の違いについて
* スタック上に '''ntfoper/mtfnull''' のみが詰まれてる際に、'''itflist0'''は'''iaxnulll'''を返し、'''itflist'''は'''itaaloc(-1, 0)'''を返す
** '''iaxnulll'''の定義は、''itaaloc(0, 0)''に等しい
** 従って、'''iftlist0'''は事前生成された永続性のある空リストを返し、'''itflist'''は局所スコープな空リストを生成して返している
*** 仮に、'''itflist'''が返した空リストが破壊的操作を受けないのであれば、'''iaxnulll'''で良いのでは？
* スタックが空の時、'''itflist0'''は'''iaxnulll'''を即座に返し、'''itflist'''は''itfcrelistm''経由で'''iaxnulll'''を返す
** ''itfcrelistm(0, *, *, ntfoper, mtfleftbrace)''は、'''mtfleftbrace == mtflist'''なので、'''m .eq. 0 .and. ith .eq. ntfoper .and. iah .eq. mtflist'''が成立し '''iaxnulll'''を返す
** このケースの実装は統一してよい(itflist側での条件分岐は、自明な条件分岐とsubroutine呼び出しの削減になっている)
!!!amorita (2017-03-27 (月) 10:52:52)
Mapの実装の概要
* ''tfgetllstkall_''による引き数コンテナのアンパック・スタック展開
* アンパックされた引数コンテナ要素の関数摘要(''tfmap1_''内部のループ)
** 処理結果は、スタック上に展開
* ''tfefunref_''による処理済みコンテナ要素を'''頭部'''と接合しての評価
** 受け渡しは、スタック経由
従って、Map処理からスタック制限を廃止するには''tfgetllstkall_''だけでなく''tfefunref_''相当の処理を新しいインターフェースで実装する必要がある
既存の評価処理系からスタック渡しとなるケースも残るので、共通分の保守性を維持するためには、''tfefunref_''相当の処理を入力列参照の抽象化層と評価処理本体に分離する必要がある。
入力列参照の抽象化としては、イテレータモデルが適切か？
Fortran/Cで抽象化イテレータを扱うには、マクロ経由でイテレータ仮想関数を実装するのが現実的か？(C++であれば、テンプレート実装でコンパイル時に最適化できる)
この種のMap系関数では必要なイテレータは、前進イテレータなので引数コンテナの展開参照も動的割り当てを含む階層化イテレータを認めれば、イテレータ化できる(一般的に、再帰降下が必要なNull[]を含むデータ構造は少ないと考えられる)
!!!amorita (2017-03-27 (月) 15:11:48)
前進イテレータに必要な操作マクロ
* ITER_INC 前進
* ITER_CMP 比較(イテレータ間の一致判定/Range構文の停止条件判定に必要)
* ITER_GET 取り出し
* ITER_SET 格納(on stack・on heap array時に部分評価に伴う書き換えで必要？)
* ITER_GET_INC 取り出し+前進(後置inc演算子+参照演算子)
格納操作に関しては、SADコンテナの参照イテレータに対しては拒否するべきもの
イテレータの属性情報として持たせるか？
(C++であれば、const属性として型情報に入れられる)
!!!amorita (2017-09-29 (金) 16:44:15)
当座の処置として、問題を起こす箇所に mstk boundary checkとcall abortを挿入して、debug dumpを取れるようにする
調べるべき場所ば、isp='''foge'''でstack pointerを巻き戻しているコード群
また、function/subroutine側でstack pointer rewindするケースが有るので、
当該関数の呼び出し元も調査対象となる
!!!amorita (2017-10-04 (水) 10:44:13)
mstk側を操作するコード群
* src/itfpmat.f
* src/tfdset.f
* src/tfeeval.f
* src/tfmap.f
* src/tfpart.f
* src/tfreplace.f
!!!amorita (2017-10-04 (水) 10:58:30)
ispを操作するコード群
* src/itfcopy.f
* src/itfdepth.f
* src/itfmaloc.f
* src/itfmessage.f
* src/itfpmat.f
* src/push.f
* src/temap.f
* src/tfattr.f
* src/tfbeamline.f
* src/tfbessel.f
* src/tfcanvasclip.f
* src/tfconvstr.f
* src/tfdot.f
* src/tfdset.f
* src/tfearray.f
* src/tfeeval.f
* src/tfeexpr.f
* src/tfefun.f
* src/tfefun2.f
* src/tfefun3ep.f
* src/tfepicsconstatcb.f
* src/tfetok.f
* src/tfeval.f
* src/tfeval1.f
* src/tffindroot.f
* src/tffswake.f
* src/tfinitn.f
* src/tfloor.f
* src/tfmap.f
* src/tfmemcheck.f
* src/tfmodule.f
* src/tfpart.f
* src/tfprint.f
* src/tfprinta.f
* src/tfreplace.f
* src/tfsameq.f
* src/tfsetlist.f
* src/tfshared.f
* src/tfsolvemember.f
* src/tfsort.f
* src/tftable.f
* src/tftake.f
* src/tfTclArg.f
* src/tftwiss.f
* src/tfvars.f
* src/tfvectorize.f
* src/tfwrite.f
{{its_edit_ticket_form}}
:Priority:Normal
:Reporter:amorita
:Status:New
:Assigned to:?
:Version:4512
:Milestone:?
:Created:2017-01-23
!! Description
Joinは、内部的に引数列から合成されるリストをSADスタック上に展開するので、
十分に長いリストのJoinは(Range等で生成可能であっても)必ず失敗する
引数からリストの展開処理を行なう''tfgetllstkall_''にスタック境界チェックが
実装されてないため'''General::stack'''メッセージが帰ってきた時点で、
スタック境界から先の領域が破壊されている可能性がある
また、''tfgetllstkall_''を使用しているMap等では、事後のスタック境界チェックも
実装されていないため、境界違反でクラッシュする
!! Attachement files
{{attach_map('Ticket-40')}}
{{attach_form('','')}}
!! Changelog
!!!amorita (2017-01-23 (月) 14:43:40)
メモリ破壊を避けるには、''tfgetllstkall_''がスタック上に書き込む前に
十分な空き領域があることを確認する必要がある
* リスト展開前に、リスト長相当のスタックが空いていることを確認する
** リストに Null[]等が含まれて展開長が短い場合も、境界検査で弾かれる可能性がある
また、スタック境界違反を上位層に返すための戻り値が必要である
* logical型・integer型の返り値で、境界違反の有無を知らせる
** 返り値の割り当てに関しては、議論の余地がある
*** 成功を真とする真偽値を返す
*** 境界違反を真とする真偽値を返す
*** 成功時に 0、それ以外は負の整数でエラーコードを返す(libc類似の設計)
* ''irtc''引数経由で'''General::stack'''メッセージを返す
** 上位層で、fallbackを実装可能な場合、メッセージ生成処理が無駄になる
!!!amorita (2017-03-13 (月) 11:04:19)
スタック非依存のリスト結合処理の実装に必要なもの
* ヒープ上の仮コンテナ
** alloc/freeは最低限必要
** Map等の実装では、endイテレータに対するappend操作が必要
** 事前に長さを確定出来ないケースでは、reallocも必要
*** よって、格納するコンテンツは、仮コンテナのアドレスを保持してはならない
**** ハンドルからの相対アドレスなら問題ないが、Object Store内のインデックスと区別する方法が問題になる
** 後述のリストコンテナ生成を想定するとrangeイテレータかrandom accessイテレータが必要
* ヒープ上の仮コンテナからリストを生成するAPI
** コンテナをObject Reference Arrayとして実装するのであれば、range API形式？
** 機能的には、itflist, itflist0, itfcompose frontendとitfcrelistm backend相当の機能は必要
*** itfcrelistmは、type/addr arrayと rval arryaが独立して存在することを前提とするAPI設計になっている
**** これのコンテナ参照版を実装すれば、itflist, itflist0, itfcompose frontendは自然に実装できる
**** コンテナイテレータが減算可能であれば、range API形式で実装出来る
**** 設計界面の統一性的には、Headもコンテナの要素型で渡すべき？
* リストコンテナに対するイテレータもしくは仮コンテナへの展開API
** 前者の実装が可能であれば、後者は自動的に実装可能
** イテレーション自体は、''tfgetllstkall_''の内部処理そのもの
*** イテレータは現在のイテレーションの状態を保持する必要がある
*** 用途から、前進イテレータが有れば十分
*** 終端検出は必要だが、どのように実装するか？
**** イテレータに対するquery functionを実装する
**** 終端を意味するイテレータの状態を定義して、イテレータの比較で実装する
!!!amorita (2017-03-22 (水) 10:57:22)
* 用意すべき型について
** SAD Objectの参照型(SAD reference → sref)
*** 抽象型 sref_t
*** ポインタ型 sref_p
** srefの仮コンテナ(bufferが適当か？)
*** コンテナ型 sref_buf_t
**** size - 割り当てたsref_t配列の大きさ
**** length - 格納した sref_tの数(lengh =< size)
**** array - sref_t配列へのポインタ(sref_p型)
* 仮コンテナの操作APIの実装方針
** Fortranへの互換性は、考慮せずに C側のみ用意する
*** Fortran-C間の構造体とポインタ運用互換性に問題が有る
*** 構造体渡しや、構造体を返す関数の実装の標準化が怪しい
** 実装作業は、''src/sim/sad_newapi.c''当りで行う
*** パス名は、ある程度初期実装が固まった後に整理？
*** 公開APIに関しては、API本体の実装後に''src/sim/sad_api.h''側で公開
**** ヘッダーを分離するかは、後日検討する
!!!amorita (2017-03-23 (木) 16:20:23)
itflist/itflist0の違いについて
* スタック上に '''ntfoper/mtfnull''' のみが詰まれてる際に、'''itflist0'''は'''iaxnulll'''を返し、'''itflist'''は'''itaaloc(-1, 0)'''を返す
** '''iaxnulll'''の定義は、''itaaloc(0, 0)''に等しい
** 従って、'''iftlist0'''は事前生成された永続性のある空リストを返し、'''itflist'''は局所スコープな空リストを生成して返している
*** 仮に、'''itflist'''が返した空リストが破壊的操作を受けないのであれば、'''iaxnulll'''で良いのでは？
* スタックが空の時、'''itflist0'''は'''iaxnulll'''を即座に返し、'''itflist'''は''itfcrelistm''経由で'''iaxnulll'''を返す
** ''itfcrelistm(0, *, *, ntfoper, mtfleftbrace)''は、'''mtfleftbrace == mtflist'''なので、'''m .eq. 0 .and. ith .eq. ntfoper .and. iah .eq. mtflist'''が成立し '''iaxnulll'''を返す
** このケースの実装は統一してよい(itflist側での条件分岐は、自明な条件分岐とsubroutine呼び出しの削減になっている)
!!!amorita (2017-03-27 (月) 10:52:52)
Mapの実装の概要
* ''tfgetllstkall_''による引き数コンテナのアンパック・スタック展開
* アンパックされた引数コンテナ要素の関数摘要(''tfmap1_''内部のループ)
** 処理結果は、スタック上に展開
* ''tfefunref_''による処理済みコンテナ要素を'''頭部'''と接合しての評価
** 受け渡しは、スタック経由
従って、Map処理からスタック制限を廃止するには''tfgetllstkall_''だけでなく''tfefunref_''相当の処理を新しいインターフェースで実装する必要がある
既存の評価処理系からスタック渡しとなるケースも残るので、共通分の保守性を維持するためには、''tfefunref_''相当の処理を入力列参照の抽象化層と評価処理本体に分離する必要がある。
入力列参照の抽象化としては、イテレータモデルが適切か？
Fortran/Cで抽象化イテレータを扱うには、マクロ経由でイテレータ仮想関数を実装するのが現実的か？(C++であれば、テンプレート実装でコンパイル時に最適化できる)
この種のMap系関数では必要なイテレータは、前進イテレータなので引数コンテナの展開参照も動的割り当てを含む階層化イテレータを認めれば、イテレータ化できる(一般的に、再帰降下が必要なNull[]を含むデータ構造は少ないと考えられる)
!!!amorita (2017-03-27 (月) 15:11:48)
前進イテレータに必要な操作マクロ
* ITER_INC 前進
* ITER_CMP 比較(イテレータ間の一致判定/Range構文の停止条件判定に必要)
* ITER_GET 取り出し
* ITER_SET 格納(on stack・on heap array時に部分評価に伴う書き換えで必要？)
* ITER_GET_INC 取り出し+前進(後置inc演算子+参照演算子)
格納操作に関しては、SADコンテナの参照イテレータに対しては拒否するべきもの
イテレータの属性情報として持たせるか？
(C++であれば、const属性として型情報に入れられる)
!!!amorita (2017-09-29 (金) 16:44:15)
当座の処置として、問題を起こす箇所に mstk boundary checkとcall abortを挿入して、debug dumpを取れるようにする
調べるべき場所ば、isp='''foge'''でstack pointerを巻き戻しているコード群
また、function/subroutine側でstack pointer rewindするケースが有るので、
当該関数の呼び出し元も調査対象となる
!!!amorita (2017-10-04 (水) 10:44:13)
mstk側を操作するコード群
* src/itfpmat.f
* src/tfdset.f
* src/tfeeval.f
* src/tfmap.f
* src/tfpart.f
* src/tfreplace.f
!!!amorita (2017-10-04 (水) 10:58:30)
ispを操作するコード群
* src/itfcopy.f
* src/itfdepth.f
* src/itfmaloc.f
* src/itfmessage.f
* src/itfpmat.f
* src/push.f
* src/temap.f
* src/tfattr.f
* src/tfbeamline.f
* src/tfbessel.f
* src/tfcanvasclip.f
* src/tfconvstr.f
* src/tfdot.f
* src/tfdset.f
* src/tfearray.f
* src/tfeeval.f
* src/tfeexpr.f
* src/tfefun.f
* src/tfefun2.f
* src/tfefun3ep.f
* src/tfepicsconstatcb.f
* src/tfetok.f
* src/tfeval.f
* src/tfeval1.f
* src/tffindroot.f
* src/tffswake.f
* src/tfinitn.f
* src/tfloor.f
* src/tfmap.f
* src/tfmemcheck.f
* src/tfmodule.f
* src/tfpart.f
* src/tfprint.f
* src/tfprinta.f
* src/tfreplace.f
* src/tfsameq.f
* src/tfsetlist.f
* src/tfshared.f
* src/tfsolvemember.f
* src/tfsort.f
* src/tftable.f
* src/tftake.f
* src/tfTclArg.f
* src/tftwiss.f
* src/tfvars.f
* src/tfvectorize.f
* src/tfwrite.f
{{its_edit_ticket_form}}