🤖

GCCに27958段ネストした関数を食わせると死ぬ

2021/11/06に公開

GCC

tech

TL;DR

f(f(f(f(1))))のように関数をネストして呼び出す時、27958段以上ネストするとGCCが死ぬので気を付けましょう。

はじめに

最近のコンパイラは、関数のインライン展開をやってくれます。例えば

int f(int i) {
  return i;
}

という、単に引数をそのまま返す関数がある時、これを何度も呼び出す

int hoge(){
  return f(f(f(1)));
}

のような関数があると、中身をなるべく展開してくれます。コンパイルするとhogeはこうなります。

hoge:
.LFB1:
  .cfi_startproc
  endbr64
  movl  $1, %eax
  ret
  .cfi_endproc

問答無用で1を返す関数に最適化してしまっていますね。

これを見ると、多分10人中10人が「ネストを何段まで展開できるんだろう？」と思うと思います。なので調べてみましょう。こんなスクリプトを書きます。

def make_src(n)
  str = <<"EOS"
int f(int i) { return i; }
int hoge() { return #{'f('*n}f(1)#{')'*n}; }
EOS
  File.open("test.c","w") do |f|
  f.puts(str)
  end
end

make_src(ARGV[0].to_i)

これで、例えば

ruby test.rb 10

とかすると、

int f(int i) { return i; }
int hoge() { return f(f(f(f(f(f(f(f(f(f(f(1))))))))))); }

というtest.cが出てきます。コンパイルしてみましょう。

gcc -O3 -S test.c

hoge:
.LFB1:
  .cfi_startproc
  endbr64
  movl  $1, %eax
  ret
  .cfi_endproc

まだ楽勝ですね。では10万では？

$ ruby test.rb 100000;gcc -O3 -S test.c
gcc: internal compiler error: Segmentation fault signal terminated program cc1
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-9/README.Bugs> for instructions.

GCCが internal compiler errorで死にました。

関数のネストを10段展開しても死なず、100000段展開すると、死ぬ、ということはそのどこかに死ぬ境目があることになりますね。

GCCにXX段ネストした関数を食わせると死ぬ

「GCCは何段まで関数のネストを展開できるんでしょうか？これってトリビアになりませんか？」

このトリビアの種、つまりこういうことになります。

「GCCが死ぬのは関数をXX段ネストした時」

実際に、調べてみた。

環境はWSL2上のUbuntu 20.04、GCCのバージョンは

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

手抜き二分探索コードを書いてみましょう。

def make_src(n)
  str = <<"EOS"
  int f(int i) { return i; }
  int hoge() { return #{'f('*n}f(1)#{')'*n}; }
EOS
    File.open("test.c","w") do |f|
    f.puts(str)
    end
end

def check(n)
  make_src(n)
  return !system("gcc -O3 -S test.c 2> /dev/null")
end

n = (10..100000).bsearch {|n| check(n)}
puts "GCC dies by #{n+1} times nested functions."

実行してみます。

$ ruby binsearch.rb
GCC dies by 27958 times nested functions.

27958段で死ぬようです。試してみましょう。

$ ruby test.rb 27957;gcc -O3 -S test.c;echo $?
0

$ ruby test.rb 27958;gcc -O3 -S test.c;echo $?
gcc: internal compiler error: Segmentation fault signal terminated program cc1
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-9/README.Bugs> for instructions.
4

確かに27957段までは大丈夫(たまに死にますが)で、27968段では確実に死にますね(環境により揺らぐようです)。

まとめ

こうしてこの世界にまた一つ

新たなトリビアが生まれた。

「GCCに27958段ネストした関数を食わせると死ぬ」

というわけで、皆さんも関数を多段ネストしたくなった時は27000段くらいで止めておくのが良いと思います。

これまでのコンパイラいじめの記録

動画もあります。

コンパイラのいじめ方(YouTube) CPP MIXで話したもの

GitHubで編集を提案

TL;DR

はじめに

GCCにXX段ネストした関数を食わせると死ぬ

まとめ

これまでのコンパイラいじめの記録

Discussion