コグノスケ

辞書に書いてある謎の記号

辞書（家にあるのは新明解国語辞典 第四版）を引いていると、語句の漢字表記に○とか▽のような謎の記号が書いてあります。今までずっと意味がわかっていなかったのですが、三省堂が素敵な解説文をサイトに載せてくれていました。

詳細は解説（第29回 ×とか▽とか、これは何だ？ - 【 】見出し（漢字表記）についている○▽× - 三省堂 ことばのコラム）を読んでいただければと思いますが、そのなかに▽は音訓表に載っていない読みのこと、と書いてあります。音訓表とはなんぞ？

検索してみると、文化庁が作成している常用漢字の読み方（文化庁 | 国語施策・日本語教育 | 国語施策情報 | 常用漢字表の音訓索引）のことらしいです。

常用漢字の一覧（文化庁 | 国語施策・日本語教育 | 国語施策情報 | 内閣告示・内閣訓令 | 常用漢字表（平成22年内閣告示第2号））を文化庁が作成しているのは知っていたんですけど、読み方まで一覧にしてくれていたんですね。知らなかったなあ……。

fno-builtinによるlibc関数呼び出し最適化の抑制

目次: GCC

GCCはlibcの関数呼び出しを別の関数呼び出しに置き換える最適化（名前がわからないので以降「libc関数呼び出し最適化」と呼びます）を行います。例を挙げると、

• 1文字出力するprintf関数→putchar関数
• 行末に改行がある文字列を出力するprintf関数→puts関数

時には勝手にlibcの関数呼び出しを置き換えてほしくないこともあると思います。libc関数呼び出し最適化を抑えることができるコンパイラオプションfno-builtinを指定したときの挙動についてメモしておきます。

GCCのバージョンは下記のとおりです。

$ gcc --version

gcc (Debian 12.2.0-14) 12.2.0
Copyright (C) 2022 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.

テストに使うプログラムは下記の通りです。

int printf(const char *a, ...);

void _start(void)
{
        printf("\n");
}

特に何も指定しなければ、1文字出力するprintfはputchar呼び出しに置き換えられるはずです。確認のためnostdlibオプションを付けてコンパイルし、リンクエラーを見るとprintfの呼び出しがどの関数に置き換えられたかわかります。

$ gcc -O2 -g -Wall a.c -nostdlib

/usr/bin/ld: /tmp/cc1D673J.o: in function `_start':
/home/katsuhiro/share/test_gcc_no_builtin/a.c:5: undefined reference to `putchar'
collect2: error: ld returned 1 exit status

リンクエラーは「putcharがない」と出ました。printfの呼び出しがputcharの呼び出しに置き換えられたことがわかりますね。次はfno-builtinオプションを指定します。

$ gcc -O2 -g -Wall a.c -nostdlib -fno-builtin

/usr/bin/ld: /tmp/cc6JbRD2.o: in function `_start':
/home/katsuhiro/share/test_gcc_no_builtin/a.c:5: undefined reference to `printf'
collect2: error: ld returned 1 exit status

リンクエラーは「printfがない」と出ました。fno-builtinオプションによってprintfからputcharへの置き換えが抑制されたことがわかります。

fno-builtinの仕様なのか？

動作結果を見る限りfno-builtinオプションでlibc関数呼び出し最適化が抑制されましたが、この挙動がオプションの仕様か？と聞かれると正直良くわかりません。

仕様はGCCのマニュアル（Other Builtins (Using the GNU Compiler Collection (GCC))）に書かれていて、説明によれば残りのビルトイン関数（printfを含む）は最適化のために提供されている（"The remaining functions are provided for optimization purposes."）とあります。

• ビルトイン関数を無効にした
• 最適化後に呼び出すためのビルトイン関数がない
• libc関数呼び出し最適化そのものが無効になった

私はこのような動作をしているものと推測しています。正しいかどうかは知りません……。

最適化はビルトイン関数に頼る必要はありません。つまりfno-builtinオプションで抑制できないようなlibc関数呼び出し最適化があっても不思議ではありません。今のところそのような例は見つけていませんが、もしあったとすると抑制する方法はあるのでしょうか？うーん？？

musl libcのpthread_barrier_wait()の実装 その3、インスタンス

目次: C言語とlibc

参考: 図を書くために使った PlantUMLのコードです。

前回の続きです。musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。バリアに到達したスレッドがNスレッド（N >= 2）あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな？

• Owner: 最初にバリアに突入してきたスレッド（1スレッド）
• Last: 最後にバリアに突入してきたスレッド（1スレッド）
• Others: OwnerでもLastでもないスレッド全て（0〜N-2スレッド、平たく言えば3スレッド以上のバリアのときだけ存在する）

今回はインスタンスがなぜローカル変数として確保されるかを紹介します。1回目と2回目のバリアが重なるところがポイントです。

スレッドの役割は変わる

各スレッドはOwnerかLastかOthersになりますが、役割は毎回のバリア同期処理ごとに変わります。例えばバリアとバリアの間の処理時間が同じだとすると、あるバリアのOwnerは次のバリアではLastになる可能性が高いです。Ownerはバリアから最後に脱出しますので、その間に他のスレッドの処理が進んで次のバリア同期処理のOwnerになるからです。

3スレッドあって下記のように役割が変化する場合を考えてみます。

• スレッド1: Owner1, Last2: 1回目Owner、2回目Last
• スレッド2: Others1, Owner2: 1回目Others、2回目Owner
• スレッド3: Last1, Others2: 1回目Last、2回目Others

更に考えてみるとバリアとバリアの間の処理時間が非常に短い場合、1回目のバリアのOwner（スレッド1、Owner1, Last2）がバリアを脱出する前に、違うスレッドが2回目のバリアのOwner（スレッド2、Others1, Owner2）となってバリアに到達している可能性があります。シーケンス例は下記のようになります。

インスタンスが1つしかない場合のシーケンス例

もしバリアのインスタンスをグローバル変数などに確保した場合、1回目のバリアのOwner（スレッド1、Owner1, Last2）によるインスタンスの破棄と、2回目のバリアのOwner（スレッド2、Others1, Owner2）のインスタンスの初期化がぶつかって、お互いに内容を壊しあうため正常に動作しません。

この問題を解決にはインスタンスをOwnerスレッド固有の領域に置くと良いです。1回目のバリアのOwnerスレッドと、2回目のバリアのOwnerスレッドがそれぞれ別の領域に置けば、お互いに壊し合うことがなくなります。

ローカル変数はスレッド固有の領域

スレッドごとの固有の領域として使えるのは、

があります。インスタンスを各Ownerスレッド固有の領域においたとき、2回分のバリア動機処理のシーケンス例は下記のようになります。

インスタンスがスレッドごとにある場合のシーケンス例

バリアのインスタンスは複数スレッド間で共有する領域です。ローカル変数を複数スレッド間で共有すると、ローカル変数が破棄されたときに問題が発生するので、ヒープを使うことが多いでしょう。

しかし前回説明したようにバリア同期処理の場合はローカル変数の寿命をうまく制御できるため、複数スレッド間で共有しても問題が起きません。インスタンスをローカル変数に確保すると、ヒープに比較して高速なメモリ割当が可能です。

musl libcのpthread_barrier_wait()の実装 その2、LastとOthers

目次: C言語とlibc

前回の続きです。musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。バリアに到達したスレッドがNスレッド（N >= 2）あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな？

• Owner: 最初にバリアに突入してきたスレッド（1スレッド）
• Last: 最後にバリアに突入してきたスレッド（1スレッド）
• Others: OwnerでもLastでもないスレッド全て（0〜N-2スレッド、平たく言えば3スレッド以上のバリアのときだけ存在する）

いっぺんに説明すると意味不明なので、順番に説明します。今回はLastとOthersです。

LastとOthers（到達側）

自分がLastかどうか判定する条件はバリア変数の_b_instがNULL以外であり、インスタンスのカウントがバリア同期するスレッド数と一致（= 最後に到達した1スレッド）することです。Lastのやることはバリア変数（pthread_barrier_t）に設定されたインスタンスを消すことと、バリア同期を待っているOthersを起こすことです。

Lastがこの時点でb->_b_instをNULLにしていること、ローカル変数instを使っていてb->_b_instを使わないことには理由があって、次のバリア処理とのオーバーラップと関係しています。同時に説明するとややこしいので、次回ご説明しようと思います。

OwnerとLast以外は全部Othersスレッドとなります。OthersのやることはLastが来るまで待つことです。

LastとOthersの到達側に関連するコードは下記のとおりです。

// musl/src/thread/pthread_barrier_wait.c

int pthread_barrier_wait(pthread_barrier_t *b)
{
	int limit = b->_b_limit;
	struct instance *inst;

	/* Trivial case: count was set at 1 */
	if (!limit) return PTHREAD_BARRIER_SERIAL_THREAD;

	/* Process-shared barriers require a separate, inefficient wait */
	if (limit < 0) return pshared_barrier_wait(b);

	/* Otherwise we need a lock on the barrier object */
	while (a_swap(&b->_b_lock, 1))
		__wait(&b->_b_lock, &b->_b_waiters, 1, 1);
	inst = b->_b_inst;

	/* First thread to enter the barrier becomes the "instance owner" */
	if (!inst) {
		//★★Ownerのスレッドの処理は省略（その1をご覧ください）★★
	}

	/* Last thread to enter the barrier wakes all non-instance-owners */
	if (++inst->count == limit) {
		//★★Lastのスレッドはこちら★★
		b->_b_inst = 0;
		a_store(&b->_b_lock, 0);
		if (b->_b_waiters) __wake(&b->_b_lock, 1, 1);
		a_store(&inst->last, 1);
		if (inst->waiters)
			__wake(&inst->last, -1, 1);
	} else {
		//★★Othersのスレッドはこちら★★
		a_store(&b->_b_lock, 0);
		if (b->_b_waiters) __wake(&b->_b_lock, 1, 1);
		__wait(&inst->last, &inst->waiters, 0, 1);
	}

細かい部分は省いてシーケンスの例を1つだけ示せば下記のようになります。

pthread_barrier_wait()のLastとOthersの到達側シーケンスの一例

見たままなので解説することがないですね。全員でインスタンスのカウントを+1して、最後のスレッドLastだけが特殊な処理を行います。

LastとOthers（脱出側）

脱出側のやることは単純ですが役割分担が少しややこしいです。到達側と同様にLastとOthersに役割が分かれますが、到達側のLast = 脱出側のLastとは限らないからです。

脱出時のLastになる条件はインスタンスのカウント値が1であることです。到達時にLastであったかOthersであったかは無関係です。脱出時のLastのやることは、インスタンスのfinishedを+1して待機中のOwnerスレッドを再開させることです。

脱出時のOthersになる条件はLastではない、インスタンスのカウント値が1以外であることです。

LastとOthersの脱出側に関連するコードは下記のとおりです。

// musl/src/thread/pthread_barrier_wait.c

int pthread_barrier_wait(pthread_barrier_t *b)
{
	int limit = b->_b_limit;
	struct instance *inst;

	//★★略★★

	/* Last thread to exit the barrier wakes the instance owner */
	if (a_fetch_add(&inst->count,-1)==1 && a_fetch_add(&inst->finished,1))
		__wake(&inst->finished, 1, 1);

	return 0;
}

細かい部分は省いてシーケンスの例を1つだけ示せば下記のようになります。

pthread_barrier_wait()のLastとOthersの脱出側シーケンスの一例

到達側のLastスレッドの処理では待機していたOthersスレッド達を全員再開させ、Lastも処理を再開します。するとLast + Othersスレッド全てがいっぺんに脱出側の処理を開始します。先ほど説明したとおり、どのスレッドが脱出側のLastになるかは運次第です。

実装の特徴はアトミックアクセスですかね。a_fetch_add(x, -1)はポインタxの指す先をアトミックに-1して、返り値でxの以前の値を返す関数です……といわれてもわかりにくいですよね。4スレッド（Owner, Others1, Others2, Last）の場合を書きましょうか。Ownerスレッドはカウント値を+1しないので、脱出処理開始時のカウント値は4 - 1 = 3です。

ちなみにアトミックアクセス以外の方法（if文とカウント値の変更など）では正常に動作しません。判定と値変更の間に他のスレッドが処理を行う可能性があるからです。

続きはまた今度。