argc = 0 でプロセスを動かす

DMDのコード内ではargcが0な環境を想定してコードが書かれているが、そういう環境は存在するのだろうか。

調べてみるとわりとすぐにstackoverflowがみつかった。

c - executing a process with argc=0 - Stack Overflow

posix_spawnを使えばできるようなので、実際に試してみる。

#include <spawn.h>
#include <stdlib.h>

int main(int argc, char** argv, char** envp)
{
    pid_t pid;
    char* zero_argv[] = {NULL};
    posix_spawn(&pid, "/home/kubo39/dlang/dmd-2.085.0/linux/bin64/dmd", NULL, NULL, zero_argv, envp);
    int status;
    waitpid(&pid, &status, NULL);
    return 0;
}

たしかにargcが0のときの処理が実行されているようだ。

$ ./a.out
Error: missing or null command line arguments                                                                                                                               
$ echo $?
0

ちなみにrustcの場合は Error: couldn't determine self executable name と表示され、goでは panic: runtime error: index out of range になった。

Isabelleちょっとやってます、という近況報告？

ここ最近Isabelleを触っている。 Coqと比べると日本語の資料が少ないのでつらい。

とりあえずいろいろわからないことが出てきたので並べてみる。

2以上の自然数を扱うと簡約できない

例としてmap関数を定義する。

fun map :: "('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list" where
  "map _ [] = []"
| "map f (x # xs) = (f x) # (map f xs)"

value "map (plus 3) (1 # 2 # [])"

そのまま自然数の3や5を命題に含めると解くことができない。

lemma test_map1: "map (\<lambda> x. plus 3 x) ((Suc 1) # 0 # (Suc 1) # []) = (5 # 3 # 5 # [])"
  sorry

(Suc (Suc 1)) みたいにすると解ける。

lemma test_map2: "map oddb (Suc 1 # 1 # Suc 1 # (Suc (Suc (Suc (Suc 1)))) # []) = (False # True # False # True # [])"
  apply (simp)
  done

もちろんこれを続けるのは限界があるので、なんか方法を見つけないといけない。

命題にforallの有無がどう影響を与えるかわかっていない

別の命題を解いてしまっているのではないかという懸念がある。 goalだけみると同じにみえるけどよくわかってない。

forallがないとうまくいかない場合

以下は Failed to apply proof method と怒られる。

lemma mult_eq_0: "n * m = 0 \<longrightarrow> n = 0 \<or> m = 0"
  apply (simp)
  done

\<forall> n m::nat. を命題に足すと No subgoals までできる。

lemma mult_eq_0: "\<forall> n m::nat. n * m = 0 \<longrightarrow> n = 0 \<or> m = 0"
  apply (simp)
  done

forallがあるとうまくいかない場合

以下は Cannot determine type b. と怒られる。

theorem not_true_is_false: "\<forall> b::bool. b \<noteq> True \<longrightarrow> b = False"
  apply (case_tac b)
   apply (simp_all)
  done

\<forall> b::bool. を命題から消すと No subgoals! までできる。

theorem not_true_is_false: "b \<noteq> True \<longrightarrow> b = False"
  apply (case_tac b)
   apply (simp_all)
  done

小ネタ: safe functionとcast function of null

おなじみ(?), safe functionを考えてみようの会です.

突然ですが, 以下のコードは合法でしょうか？

void main() @safe
{
    (cast(void function() @safe) null)();
}

結果はおおかた予想がつくとは思いますが、Segmentation Faultになります。

(dmd-2.084.0)$ rdmd safecastnull.d
zsh: segmentation fault (core dumped)  rdmd safecastnull.d

さて、合法かどうかですが, まず safe functionの定義 から照らし合わせてみると

• No casting from a pointer type to any type other than void*.
• No casting from any non-pointer type to a pointer type.
• No pointer arithmetic (including pointer indexing).
• Cannot access unions that have pointers or references overlapping with other types.
• Calling any system functions.
• No catching of exceptions that are not derived from class Exception.
• No inline assembler.
• No explicit casting of mutable objects to immutable.
• No explicit casting of immutable objects to mutable.
• No explicit casting of thread local objects to shared.
• No explicit casting of shared objects to thread local.
• No taking the address of a local variable or function parameter.
• Cannot access __gshared variables.
• Cannot use void initializers for pointers.
• Cannot use void initializers for class or interface references.

一個目と二個目が怪しいですね.

nullの定義 もみてみましょう. 最初の文はnullはポインタやら動的配列やらを表すことができる値と解釈できます.

次ですが, なんと, "it is an exact conversion to convert it to the null value for pointers, pointers to functions, delegates, etc." という文言が確認できます. 正しい変換であるとはどういうことなんなんでしょうか. 必ずsafe? また直前のnullは別の型にキャストされる前だとtypeof(null)という型が与えられるそうですが, これはpointer typeなのでしょうか, それともnon-pointer typeなのでしょうか. 少なくとも現在の仕様の状態から判別することは難しいと思います…

というわけで最初の問題の結論は, 「現時点(2019.02.07)での仕様ではどちらともとれる」でした(これはひどい)

scope parameter storage class と in parameter storage class

（2019/02/07; いくつか追記したのでそちらのほうもみてください）

現在の最新版コンパイラ(DMD 2.084.0)だと, このコードはSEGVで落ちてしまう.

auto foo(scope void delegate() @safe dg) @safe
{
    return dg;
}

auto bar(void delegate() @safe dg) @safe
{
    return foo(() => dg());
}

void main()
{
    bar((){})();
}

これは関数 bar fooがクロージャを生成しないためである. (scope parameter storage classを使わない場合は callq _d_allocmemory がコード生成される, これはクロージャのためのメモリを確保するために使われる)

(追記: たしかにscope使った場合にclosureを生成しないためなんだけど、実際には開放済のはずのスタック領域に対して不正アクセスしてるのが問題なのであり、しかもbarではなくfooのほうだった…）

0000000000032edc <_D9scopesegv3fooFNfMDFNfZvZQh>:
   32edc:       55                      push   %rbp
   32edd:       48 8b ec                mov    %rsp,%rbp
   32ee0:       48 83 ec 10             sub    $0x10,%rsp
   32ee4:       48 89 7d f0             mov    %rdi,-0x10(%rbp)
   32ee8:       48 89 75 f8             mov    %rsi,-0x8(%rbp)
   32eec:       48 8b 55 f8             mov    -0x8(%rbp),%rdx
   32ef0:       48 8b 45 f0             mov    -0x10(%rbp),%rax
   32ef4:       c9                      leaveq 
   32ef5:       c3                      retq

正直バグなのかどうか確定的に言えないが, 関数の定義において scope parameter sotrage class は ~ cannot be escaped といっているのでこれは合法的な振る舞いだと思われる. (追記: 触っちゃいけないスタック領域さわってるからアウトだな…)

この挙動がバグであるかはおいておいて, scope parameter storage classと似たようなものとして in parameter storage classがある. ただしここで scope のかわりに in を使った場合, クロージャを生成するコードがはかれてプログラムは正常終了する.

https://dlang.org/spec/function.html#param-storage によると in parameter storage class は defined as scope const. However in has not yet been properly implemented so it's current implementation is equivelent to const. ~ とある. この説明を読むと in は scope const と定義されているけど, 現状では正しく実装されていなくて const と同じ扱いだよ, なるべく使わないでかわりに scope const か const を使ってね ということだそうだ.

というわけだが, いくつか疑問なところがでてくる.

• inの現在の実装は正しくなくてconstと同じ実装だよ, と仕様に書かれている場合に段階的にscope constと同じようにコンパイラ内部の実装を変更するべきだろうか
  • constともscope constとも異なる実装になる? stableでおきなかったらいいか
  • ユーザは仕様の注釈をみて const と同じ振る舞いを期待してコードを書いているかもしれない, さすがに無視してよさそうだが...
• さらに上の問題のように, in parameter storage classの実装をscope constに近づけたことによっておきる問題が発生した場合, どのように対応すべきだろうか
  • 仮に今回のscope parameter storage classの挙動(SEGV)が正しい場合があるとして, ユーザがコードを変更してないのにコンパイラのバージョンをあげたらSEGVる, とか.
  • そもそもコンパイラのBug Fixなので正しいし, ユーザが in parameter storage class の使い方を間違えているケースと考えてることはできる.
  • とはいえわりと使われていそうなので, かなり影響がでそうだし慎重にやるべきだろうな.

とりあえず現時点で in paramter storage class は使わないほうがよさそうだ.

DMDでprofileオプションを使ったときだけスタックオーバーフローする不思議なバグの調査

なんかおもしろいコンパイラのバグに遭遇したのでめも。

もともとはpeggedを使ったプロジェクトで dub build --build=profile でビルドしたバイナリを実行するとSEGVに遭遇するんだけど・・・、という問題だった。

とりあえずgdbにかけてみると

>>> bt 10
#0  0x0000555555928ecc in trace_pro ()
#1  0x000055555580cbb8 in _D4core8internal6string__T7dstrcmpZQjFNaNbNiNeMxAaMxQeZi ()
#2  0x0000555555955b62 in trace_addsym ()
#3  0x0000555555928fee in trace_pro ()
#4  0x000055555580cbb8 in _D4core8internal6string__T7dstrcmpZQjFNaNbNiNeMxAaMxQeZi ()
#5  0x0000555555955b62 in trace_addsym ()
#6  0x0000555555928fee in trace_pro ()
#7  0x000055555580cbb8 in _D4core8internal6string__T7dstrcmpZQjFNaNbNiNeMxAaMxQeZi ()
#8  0x0000555555955b62 in trace_addsym ()
#9  0x0000555555928fee in trace_pro ()
(More stack frames follow...)

という感じでどうも相互関数呼び出しによるstack overflowをしている。 そのあとごにょごにょ回り道をしたあげく、DWARFの吐いている core.internal.string.dstrcmp のソースでは存在していないけれど、disassemble では callq trace_pro するようになっていてなんだこれ？ということでDMDのソースをみることに。 すると src/dmd/glue.d に以下のようなコードとコメントが。

        /* Doing this in semantic3() caused all kinds of problems:
         * 1. couldn't reliably get the final mangling of the function name due to fwd refs
         * 2. impact on function inlining
         * 3. what to do when writing out .di files, or other pretty printing
         */
        if (global.params.trace && !fd.isCMain() && !fd.naked)
        {
            /* The profiler requires TLS, and TLS may not be set up yet when C main()
             * gets control (i.e. OSX), leading to a crash.
             */
            /* Wrap the entire function body in:
             *   trace_pro("funcname");
             *   try
             *     body;
             *   finally
             *     _c_trace_epi();
             */
            StringExp se = StringExp.create(Loc.initial, s.Sident.ptr);
            se.type = Type.tstring;
            se.type = se.type.typeSemantic(Loc.initial, null);
            Expressions *exps = new Expressions();
            exps.push(se);
            FuncDeclaration fdpro = FuncDeclaration.genCfunc(null, Type.tvoid, "trace_pro");
            Expression ec = VarExp.create(Loc.initial, fdpro);
            Expression e = CallExp.create(Loc.initial, ec, exps);
            e.type = Type.tvoid;
            Statement sp = ExpStatement.create(fd.loc, e);

つまり dstrcmp 関数がtrace_pro を先頭で呼ぶように書き換えられた結果、 trace_pro -> trace_addsym -> dstrcmp -> trace_pro -> ... のようにひたすら関数呼び出しをし続けてstack overflowになる、ということだ。

peggedを使わない場合の再現コードをなかなか用意できなかったが文字列の大小比較 ("aaa" >= "bbb") は内部で dstrcmp を呼ぶので非常に簡単な再現コードに落とし込むことができた。 つまり文字列の大小比較のあるすべてのコードは -profile オプションを用いると同様にstack oveflowになる、ということである。だれも-profileオプションを使っていないのだろうか。

今回の話の教訓としては、「コードは書いたとおりに動くというのは嘘、コンパイラは隙があればおまえのコードを勝手に書き換える」ということですね。

■

C言語のmainでめちゃくちゃできる、ってネタみたけど別にDでもできるよな。 main is usually a function はでないけど。

extern (C) void main() pure nothrow @nogc
{
    asm pure nothrow @nogc
    {
        naked;
        db 0x31; db 0xC0;  // xor EAX, EAX;
        db 0xFF; db 0xC0;  // inc EAX;
        db 0xC3;           // retq;
    }
}

これでGNU coreutilsのfalseコマンド的な動作になる。

64bitだとxor EAX, EAX は嘘でmov RAX, 0 のほうがいいかもしれないのでみなさんはちゃんとしてください（？）

druntimeのcore.syncについて

いろいろいけてないよな。

• Mutexの実装がデフォルトでre-entrant
  • 不定な振る舞いよりはデッドロックが早期にわかるほうが100倍マシだから
• 条件変数およびセマフォのタイムアウトつきwaitがmonotonicなclockじゃなくシステムクロック
  • なので、システムの時刻変更によって予期せぬ振る舞いが起こりえる

このあたりはC++ではあたりまえに認知されている(デフォルトのmutex実装と別にrecursive mutexを用意、タイムアウトつきの待ちではstd::chrono::steady_clock使う)のと、Rustも実装では同じようになっているのになぜDは微妙な実装になってるのだろう。