link もっと前
   2020年 1月 26日 -
      2020年 1月 17日  
link もっと後

link 未来から過去へ表示(*)
link 過去から未来へ表示

日々

link permalink

link 編集する

C 言語の未定義動作と最適化

くそ長いですが、C 言語の未定義動作怖いね、printf でタイミング以外も動き変えられるよ、という話です。

環境ですが x86_64 向け Debian GNU/Linux 9.2 で実行しています。また GCC のバージョンは gcc (Debian 9.2.1-22) 9.2.1 20200104 です。

未定義動作のため、コンパイラの種類や、GCC のバージョンにより結果が変わると思われます。お家のマシンで試すならご留意ください。

1番目の実験

この日記の最後に貼ったプログラム(このプログラムをコンパイルすると、激しい警告が出ます)を gcc -Wall -O2 a.c && ./a.out のように実行すると、

1番目の実験: あれ?バッファオーバーランは…?
0: 0 0 0
1: 0 1 0
2: 0 2 0
3: 0 3 0
4: 0 4 0
...
47: 0 47 0
48: 0 48 0
49: 0 49 0
1770: 1770

こうなります。0〜59 の和は 1770 です。あってます。良かったですね。

なに?そういう問題じゃない?「なぜ array 終端を超えて guard2 にバッファオーバーランしない?」と考えた方、するどいです。しかし世の中そう単純ではありません。

2番目の実験

10行目の printf のコメントを外してローカル変数のアドレスを表示させると、

2番目の実験: 10行目の printf を有効、突然のバッファオーバーラン
0x7ffd9b348a10 0x7ffd9b348ae0 0x7ffd9b348bb0
0: 0 0 52
1: 0 1 53
2: 0 2 54
3: 0 3 55
4: 0 4 56
...
45: 0 45 0
46: 0 46 0
47: 0 47 0
48: 0 48 0
49: 0 49 0
1770: 1770

こうなります。突然オーバーランするようになりました。printf が何かしたんでしょうか、不思議ですね?

3番目の実験

どうして for ループを無意味に 2分割したのか?くっつけてみたらわかります。Segmentation Fault します。

3番目の実験: ループを 1つにするとクラッシュ
0: 0 0 0
1: 0 1 0
2: 0 2 0
3: 0 3 0
4: 0 4 0
...
45: 0 45 0
46: 0 46 0
47: 0 47 0
48: 0 48 0
49: 0 49 0
Segmentation fault

もう意味不明ですよね。何が起こっているんでしょう?

タネ明かし

この 60回の for ループは「配列の終端を超えたアクセス」が C 言語仕様上の未定義動作なので、何が起きても正しい、つまりどの結果も正しいです。

これだけだと、何言ってんのか意味不明だと思うので「printf 有効/無効」「for ループ 1つ/2つ」に着目して説明します。

1番目の実験(printf 無効、for ループ 2つ)
プログラムを見ると guard1, guard2 に対して memset 0 した後、参照のみで代入しません。コンパイラは guard1, guard2 をスタックに配置せず、配列への参照(guard1[i], guard2[i])は全て「定数の 0」に置換します。
(GIMPLE を見たら 033t.fre1 で 0 に置換されるようです)
このとき array のバッファオーバーランはスタックに退避されているレジスタ値などを書きつぶしますが、ギリギリ続行できています。
2番目の実験(printf 有効、for ループ 2つ)
1番目と変わりないと思いきや、printf が guard1, guard2 のアドレス参照をするため、定数の 0 に置換すると返せるアドレスがなくなり結果が変わってしまいます。このため、guard1, guard2 はスタックに配置されます。
このとき array のバッファーオーバーランは隣に配置された guard2 を書きつぶします。
3番目の実験(printf 無効、for ループ 1つ
いわゆる偶然の結果です。1番目と同様に guard1, guard2 はスタックに配置されず、array のバッファオーバーランによりスタックに退避したレジスタ値などが壊れます。for ループが 1つ減ったことでスタックに退避されるレジスタが 1つ減って(8バイト分余裕がなくなる)、1番目の実験でギリギリリターンアドレスを壊されずに耐えていたものが、耐えられなくなります。

3番目の実験の裏打ちとして、試しにループ回数を 80回くらいにすると for ループが 1つだろうが 2つだろうが、リターンアドレスがぶっ壊れて Segmentation Fault します。10行目の printf を有効にすると guard1, guard2 がスタックに配置されて、受け止めてくれるので、80回でも耐えます。

難解な C 言語仕様、曖昧な利用者の理解、過激なコンパイラの最適化、が招く結末

バッファオーバーランを期待していた向きには残念(?)かもしれませんが、guard1, guard2 はメモリ上に置いても置かなくても、C 言語仕様に矛盾しないなら、どっちでも良いです。もっというと C 言語仕様に矛盾しないなら、コンパイラの最適化は何をやっても OK です。

この「C 言語仕様に矛盾しないなら」はおそらくコンパイラ開発者には常識なのでしょうけども、C 言語の仕様は人間に優しくないのと、大多数の C 言語プログラマは言語仕様(特に未定義動作)を理解しておらず、何となく使っています。

難解な仕様、曖昧な理解、過激な最適化の相乗効果により、今日も世界のどこかで
「最適化で動きが変になっちゃったよ……。どうして…どうして……?」
とコンパイラとすれ違ったプログラマが泣いているでしょう。。。

参考

大したものではありませんが、ソースコードを載せておきます。

実験用ソースコード

#include <stdio.h>
#include <string.h>

int undefined()
{
	int guard1[50];
	int array[50];
	int guard2[50];
	int sum = 0, i;

	memset(guard1, 0, sizeof(guard1));
	memset(guard2, 0, sizeof(guard2));
	//printf("%p %p %p\n", &guard1[0], &array[0], &guard2[0]);

	for (i = 0; i < 60; i++) {
		array[i] = i;
	}

	for (i = 0; i < 60; i++) {
		sum += array[i];
	}

	for (i = 0; i < 50; i++) {
		printf("%2d: %d %d %d\n", i, guard1[i], array[i], guard2[i]);
	}

	return sum;
}

int main(int argc, char *argv[])
{
	int sum1 = 0, sum2 = 0, i;

	sum1 = undefined();

	for (i = 0; i < 60; i++) {
		sum2 += i;
	}

	printf("%d: %d\n", sum1, sum2);

	return 0;
}
[編集者: すずき]
[更新: 2020年 1月 26日 19:04]

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

link 編集する

glibc の memset は強かった

目次です。

先日(2020年 1月 12日の日記参照)の続きです。

あまりにも glibc フルアセンブラ版 memset の実装が速くて勝てないので、観念して実装を見たのですが、序盤(1バイト〜32バイト)が弱い理由と、以降(33バイト〜)で勝てない理由がわかりました。

他の実装と違って glibc はサイズの大きい方から条件を見ています。どうしても条件分岐命令を通る回数が増えるため、序盤に弱いです。

中盤は 96 バイトまでは NEON store x 4 と分岐で捌いていて、ループを使いません。分岐も cmp して branch ではなく、ビットセットされていたら分岐する命令(tbz, tbnz)を使っています(※)。

つまり私が書いた memset はループで処理している時点で、ほぼ勝ち目がなかったということです。

グラフでは 63バイトまでしか測っていなかったから気づかなかったのですが、ループの 2週目に入る 65バイトから、さらにボロ負けです。いやはや、これは勝てないですね……。

(※)cmp, branch の 2命令を tbz 1命令にする辺り、AArch64 アセンブラならではの実装に見えますが、実は C でも if (a & 0x10) とか書くとコンパイラが tbz 命令を使います。コンパイラ侮りがたし。

[編集者: すずき]
[更新: 2020年 1月 26日 17:19]

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

link 編集する

glibc の memset のクセ

先日 memset を書いていたとき(2020年 1月 12日の日記参照)に気づいたのですが、glibc のフルアセンブラ版 memset の性能が 2通り(遅い、速い)あることに気づきました。だいたい 1割くらい性能が変わります。

遅いときと比較すると、自作の memset の方が速いですが、速いときと比較するとボロ負けします。割と性能が迫っているためか、影響が大きいです。

何が違うんでしょうね?コードは当然同じですから、違いは memset 関数のロードされるアドレスくらいです。まさかなと思って、スタティックリンクしたら安定して速くなりました。

ダイナミックリンクだと、アプリ側は 0xaaaac4fba560 で、glibc だけ 0xffffbf2dce00 のような遠いアドレスに飛ばされます。ベンチマーク中は、アプリのコード ←→ glibc のコードを頻繁に行き来することになるので、TLB ミスヒットの影響が出ているんですかね……??

真因はわかりませんが、アドレスが関係している可能性は高いです。今後、似たようなことをやるときは、スタティックリンクで測った方が良さそうです。

[編集者: すずき]
[更新: 2020年 1月 26日 17:09]

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

link 編集する

バイトをコピーする SIMD 命令

最近、見かける SIMD 命令セット(AVX も NEON も)には、レジスタ下位 [7:0] の 1バイトを、レジスタ上位 ... [31:24] [23:16] [15:8] の各バイトに配る命令が用意されています。

  • AVX: vpbroadcastb
  • NEON: dup

この命令はどういう需要があるんだろうか……?memset の実装では超役に立ちましたが、他の使い道が良くわかりません。

Facebook で上記の話をしていたところ、

  • 8bit 行列演算: 8bit 行列演算ってそんな頻出かな、って思ったら、画像使えば 8bit なので十分有り得そう。
  • バイト暗号: ブロック毎に空間変換する時とか雑に言えばスカラとベクトルの演算。

と教えてもらいました。なるほど、スカラベクトル積のスカラ側を配るときに便利ですね。

SIMD 命令のない世界

ちなみに SIMD のない処理系はどうしているのか見てみると、


int a = (何かの数字);

としたときに、


a &= 0xff;
a *= 0x01010101;

のように and, mov, mul を使っていました。もちろん、


a &= 0xff;
a |= a << 8;
a |= a << 16;

のように and, shift, or, shift, or でもできますが、今日日のプロセッサだと整数乗算の方が速そうですね。

[編集者: すずき]
[更新: 2020年 1月 26日 16:59]

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
   2020年 1月 26日 -
      2020年 1月 17日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 3/15 02:33

カレンダー

<2020>
<<<01>>>
---1234
567891011
12131415161718
19202122232425
262728293031-

最近のコメント 5件

  • link 13年11月28日
    すずき 「ご指摘ありがとうございます。投稿の古さに...」
    (更新:03/08 17:39)
  • link 13年11月28日
    yut 「古いので、見てもらえるか不明ですので、、...」
    (更新:03/08 13:16)
  • link 13年11月28日
    yut シムズ 「古い投稿に対して、申し訳ありません。\n...」
    (更新:03/08 13:14)
  • link 19年09月01日
    すずき 「私も正直びっくりです。間違って違う製品を...」
    (更新:09/04 23:39)
  • link 19年09月01日
    hdk 「車向けの製品の中でも、車載コンピューター...」
    (更新:09/02 23:20)

最近の記事 3件

link もっとみる
  • link 20年03月10日
    すずき 「[誕生日] 37歳になりました。おめでとう俺、ありがとう俺。30代...」
    (更新:03/15 02:33)
  • link 20年03月14日
    すずき 「[GCC を調べる - その 7 - machine mode] ...」
    (更新:03/15 02:21)
  • link 20年03月06日
    すずき 「[GCC を調べる - その 6 - GCC の regist] ...」
    (更新:03/11 22:47)

こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報