目次: C言語とlibc
参考: 図を書くために使った PlantUMLのコードです。
前回の続きです。musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。バリアに到達したスレッドがNスレッド(N >= 2)あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな?
今回はインスタンスがなぜローカル変数として確保されるかを紹介します。1回目と2回目のバリアが重なるところがポイントです。
各スレッドはOwnerかLastかOthersになりますが、役割は毎回のバリア同期処理ごとに変わります。例えばバリアとバリアの間の処理時間が同じだとすると、あるバリアのOwnerは次のバリアではLastになる可能性が高いです。Ownerはバリアから最後に脱出しますので、その間に他のスレッドの処理が進んで次のバリア同期処理のOwnerになるからです。
3スレッドあって下記のように役割が変化する場合を考えてみます。
更に考えてみるとバリアとバリアの間の処理時間が非常に短い場合、1回目のバリアのOwner(スレッド1、Owner1, Last2)がバリアを脱出する前に、違うスレッドが2回目のバリアのOwner(スレッド2、Others1, Owner2)となってバリアに到達している可能性があります。シーケンス例は下記のようになります。
もしバリアのインスタンスをグローバル変数などに確保した場合、1回目のバリアのOwner(スレッド1、Owner1, Last2)によるインスタンスの破棄と、2回目のバリアのOwner(スレッド2、Others1, Owner2)のインスタンスの初期化がぶつかって、お互いに内容を壊しあうため正常に動作しません。
この問題を解決にはインスタンスをOwnerスレッド固有の領域に置くと良いです。1回目のバリアのOwnerスレッドと、2回目のバリアのOwnerスレッドがそれぞれ別の領域に置けば、お互いに壊し合うことがなくなります。
スレッドごとの固有の領域として使えるのは、
TLS(Thread Local Storage) ヒープから確保したメモリ(mallocなど) ローカル変数があります。インスタンスを各Ownerスレッド固有の領域においたとき、2回分のバリア動機処理のシーケンス例は下記のようになります。
バリアのインスタンスは複数スレッド間で共有する領域です。ローカル変数を複数スレッド間で共有すると、ローカル変数が破棄されたときに問題が発生するので、ヒープを使うことが多いでしょう。
しかし前回説明したようにバリア同期処理の場合はローカル変数の寿命をうまく制御できるため、複数スレッド間で共有しても問題が起きません。インスタンスをローカル変数に確保すると、ヒープに比較して高速なメモリ割当が可能です。
目次: C言語とlibc
前回の続きです。musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。バリアに到達したスレッドがNスレッド(N >= 2)あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな?
いっぺんに説明すると意味不明なので、順番に説明します。今回は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 = 脱出側の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です。
スレッド | -1したあとのカウント値 | a_fetch_add()の返り値 |
---|---|---|
Others 1 | 2 | 3 |
Others 2 | 1 | 2 |
Last | 0 | 1 |
ちなみにアトミックアクセス以外の方法(if文とカウント値の変更など)では正常に動作しません。判定と値変更の間に他のスレッドが処理を行う可能性があるからです。
続きはまた今度。
目次: C言語とlibc
誰得かわかりませんが、musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。このAPIはバリア同期を実現するためのAPIで、POSIXという規格の一部です。バリア同期はある地点に指定した数のスレッドが全員到達するまで、全スレッドを待機させる同期機構です。
バリアに到達したスレッドがNスレッド(N >= 2)あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな?
いっぺんに説明すると意味不明なので、順番に説明します。最初はOwnerからです。
自分がOwnerかどうか判定する条件はバリア変数の_b_instがNULLであることです。Ownerのやることはインスタンスを作成しバリア変数(pthread_barrier_t)に設定することと、バリアから一番「最後」に脱出してインスタンスを破棄することです。インスタンスはmuslの用語ですかね?それはさておいてインスタンスは1回のバリア同期に必要なパラメータがおかれた場所です。
インスタンスの必要性を簡易に説明するのは難しいですね……バリア変数は使いまわされるからです。具体例で言うと、1回目のバリアからスレッドが脱出している途中で、先に脱出した他のスレッドが2回目のバリアに到達する、というケースが発生します。もしバリアのカウンタ値などをバリア変数に置いてしまうと、1回目のバリアの処理と2回目のバリアの処理が混ざって正常に処理できなくなります。
Ownerに関連するコードは下記のとおりです。
// 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) {
struct instance new_inst = { 0 };
int spins = 200;
b->_b_inst = inst = &new_inst;
a_store(&b->_b_lock, 0);
if (b->_b_waiters) __wake(&b->_b_lock, 1, 1);
while (spins-- && !inst->finished)
a_spin();
a_inc(&inst->finished);
while (inst->finished == 1)
__syscall(SYS_futex,&inst->finished,FUTEX_WAIT|FUTEX_PRIVATE,1,0) != -ENOSYS
|| __syscall(SYS_futex,&inst->finished,FUTEX_WAIT,1,0);
return PTHREAD_BARRIER_SERIAL_THREAD;
}
//...
各所に工夫が散りばめられていて全部説明すると30分くらい説明が必要な気がしますが、細かい部分は省いてシーケンスの例を1つだけ示せば下記のようになります。
pthread_barrier_wait()のOwnerシーケンスの一例
特徴的というか個人的に感心した点は、インスタンスをローカル変数で確保していることです。変数のアドレスは一般的にはスレッドのスタック領域の一部になることが多いでしょう。ローカル変数の特徴として、
1つ目の特徴はmusl libcのバリア実装に限って言えば問題ありません。Ownerが必ず最後にバリア同期APIを脱出するように実装が工夫されていて、壊れたローカル変数に他のスレッドがアクセスする状況が発生しないからです。
2つ目の特徴はうまく活かしています。ローカル変数はバリアに一番最初にたどり着いたスレッド(= Owner)が、他スレッドと干渉せずインスタンスを確保できる簡単かつ高速な方法です。mallocのようなヒープでも目的は達成できますが、速度的に不利でしょう。面白い実装ですね。
続きはまた今度。
RISC-V用のツールチェーンを更新しているときに気づいたバグです。
現在の時刻を取得するgettimeofday()というAPIがあります。newlib-4.1.0ではSYS_gettimeofdayを使っていましたが、newlib-4.3.0ではSYS_clock_gettime64を使うように変更されました。が、これがバグっていました。
// newlib-cygwin/libgloss/riscv/sys_gettimeofday.c
/* Get the current time. Only relatively correct. */
int
_gettimeofday(struct timeval *tp, void *tzp)
{
#if __riscv_xlen == 32
struct __timespec64
{
int64_t tv_sec; /* Seconds */
# if BYTE_ORDER == BIG_ENDIAN
int32_t __padding; /* Padding */
int32_t tv_nsec; /* Nanoseconds */
# else
int32_t tv_nsec; /* Nanoseconds */
int32_t __padding; /* Padding */
# endif
};
struct __timespec64 ts64;
int rv;
rv = syscall_errno (SYS_clock_gettime64, 2, 0, (long)&ts64, 0, 0, 0, 0);
tp->tv_sec = ts64.tv_sec;
tp->tv_usec = ts64.tv_nsec * 1000; //★★計算式を間違えている、* 1000ではなく / 1000が正しい★★
return rv;
#else
return syscall_errno (SYS_gettimeofday, 1, tp, 0, 0, 0, 0, 0);
#endif
}
見ての通り、gettimeofdayは結果を秒(tv_sec)とマイクロ秒(tv_usec)のペアで返します。clock_gettime64は秒とナノ秒で結果を返してきますので、ナノ秒→マイクロ秒へ変換する必要があります。しかし悲しいことにナノ秒→マイクロ秒の変換コードがバグっており、マイクロ秒の値がかなり大きな値(本来1usなのに1msになってしまう(訂正: 1nsなのに1msになってしまう))になってしまいます。
実装変更がnewlibに入ったのは約2年前(2021年4月13日、commit id: 20d008199)でした。結構時間が経っていますね。先ほど紹介したgettimeofdayの実装はRISC-V 32bit向けの時しか使わないので、他のアーキを使っている開発者の皆様がバグに気づかなかったのだろうと思われます。
commit 20d00819984058e439cfe40818f81d7315c89201 Author: Kito Cheng <kito.cheng@sifive.com> Date: Tue Apr 13 17:33:03 2021 +0800 RISC-V: Using SYS_clock_gettime64 for rv32 libgloss. - RISC-V 32 bits linux/glibc didn't provide gettimeofday anymore after upstream, because RV32 didn't have backward compatible issue, so RV32 only support 64 bits time related system call. - So using clock_gettime64 call instead for rv32 libgloss.
このバグは既に下記のコミットで修正されています。
commit 5f15d7c5817b07a6b18cbab17342c95cb7b42be4 Author: Kuan-Wei Chiu <visitorckw@gmail.com> Date: Wed Nov 29 11:57:14 2023 +0800 RISC-V: Fix timeval conversion in _gettimeofday() Replace multiplication with division for microseconds calculation from nanoseconds in _gettimeofday function. Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
コミットの日付を見てびっくりしたのですが、なんと今日のコミットです。きっと世界のどこかで私と同じようなことを調べ、なんじゃこりゃー?!とバグを見つけて直した人が居たんでしょう。やー、奇遇ですね……。
目次: C言語とlibc
RISC-V向けglibcの実装を眺めていたところ、2.37と2.38でスレッドを作成する関数(__clone_internal関数)が使っているシステムコールが変わっていることに気づきました。
スレッドを作成するcloneシステムコールにはいくつか亜種がありますが、大抵のアーキテクチャではcloneとclone3が実装されています。cloneは引数を値で渡します。clone3は構造体へのポインタと構造体のサイズを渡します。cloneの引数は非常に多く、しかも昔より増えているような気がします……。今後の拡張も考えれば引数の個数に制限がある値渡しよりも、構造体のポインタを渡したほうが合理的ですね。
実装は全アーキテクチャ共通で、下記のような感じです。struct clone_argsがclone3に渡す構造体です。__clone3_internal()はcl_argsを直接clone3システムコールに渡します。__clone_internal_fallback()はcl_argsの各フィールドをバラバラにしてcloneシステムコールに渡します。
// glibc/sysdeps/unix/sysv/linux/clone-internal.c
int
__clone_internal (struct clone_args *cl_args,
int (*func) (void *arg), void *arg)
{
#ifdef HAVE_CLONE3_WRAPPER
int saved_errno = errno;
int ret = __clone3_internal (cl_args, func, arg); //★★SYS_clone3を呼ぶ
if (ret != -1 || errno != ENOSYS)
return ret;
/* NB: Restore errno since errno may be checked against non-zero
return value. */
__set_errno (saved_errno);
#endif
return __clone_internal_fallback (cl_args, func, arg); //★★SYS_cloneを呼ぶ
}
これまで(2.37まで)のglibcのRISC-V向け実装でclone3システムコールが使われていなかった理由は、有効/無効のスイッチが無効側に設定されていたからです。スイッチとなるマクロ定義はsysdep.hというヘッダにあります。
// glibc/sysdeps/unix/sysv/linux/riscv/sysdep.h
# define HAVE_CLONE3_WRAPPER 1
2.37まではHAVE_CLONE3_WRAPPERが未定義で、2.38ではHAVE_CLONE3_WRAPPERの定義が追加されました。以上が__clone_internal()が使っているシステムコールが変わる仕組みでした。良くできてます。
目次: 射的
JTSA Limitedの大会に参加しました。いつも使っているエアガンであるベレッタ92(東京マルイ、US M9)が大会の朝に壊れてしまい、急遽グロック17(東京マルイ、GLOCK 17 Gen.4)で参加するというトラブル付きです。にも関わらず、記録は絶好調で76.68秒の自己ベストが出ました(総合105位/135人、LM 24位/37人)。えー。
ダブルアクションのベレッタ92とシングルアクションのグロック17を比べれば、後者が有利なのはわかりますが、練習会で一度も出たことがない好タイムが大会本番の一発勝負で出るのはどういうことなんだ。うーん、普段の練習の意味とは一体……良い記録が出ただけに複雑な気分です……。
目次: Linux
OSDNがOSCHINAに売却された(「OSDN」が中国企業に買収〜日本のオープンソースプロジェクトホスティングサービス - 窓の杜)影響か、最近OSDNのWWWサーバーが応答しなくなりました。人によっては「ふーん、そうなん」で終わりですが、私は非常に困ることが1点あります。Linux JMが見えなくなったことです。
Linux JMとはLinuxのman(マニュアル、英語)を日本語訳して公開してくれている超ありがたいプロジェクトです。man形式だけでなくHTML形式も作成していて、同プロジェクトのサイトにて公開されています……いました。Linux JMおよび同サイトがOSDNでホスティングされているため、今回の騒動で見えなくなってしまいました。
私はmanpage + API名という雑な検索をしても、ほぼ一番最初に出てくるLinux JMを大変重宝しておりました。これが使えなくなるのは辛いよー……。
ソースコードリポジトリは公開されていますので、泣き言を言う暇があったら自分でHTMLに変換すれば良かろうって?全く持っておっしゃるとおりですね。やりましょう。
リポジトリのアドレスはgit://git.osdn.net/gitroot/linuxjm/jm.gitです。OSDNのシステムをよく知りませんが、GitHubなどとは異なりHTTPSでcloneできるサーバーはなさそうな気配です。リポジトリは他に3つ存在しますが、いずれも過去の履歴を保持するために残されたリポジトリです。READMEファイル以外は何も入っていません。
今回はこれらは使いませんので、リポジトリのアドレスを紹介するだけに留めます。
ビルドというほど大げさでもないですけど。apt-getなどでman2htmlをインストールした後に、下記を実行します。
$ git clone git://git.osdn.net/gitroot/linuxjm/jm.git $ cd jm $ make JMHOME=`pwd`/result MAN2HTML=/usr/bin/man2html html
成功するとJMHOMEで指定したディレクトリの下(result/htdocs/html)にHTMLファイルの入ったディレクトリが生成されます。この日記のサイトから読めるようにしておきます(一覧へのリンク)。右側のコンテンツメニューからも辿れるようにしました。
HTMLファイルだけでもマニュアルとしては十分ですが、白黒で目が痛いしデザインがそっけないです。デザインを変更するにはhtmlディレクトリと同列にjm.cssというファイルを置くと良いみたいです。リポジトリのwwwディレクトリ以下にある*.cssファイルを使うのが手っ取り早いでしょう。
いつもの見慣れたデザインになりました。黄色いデザインのイメージでしたが、デフォルトは青いみたいです。知りませんでした……。
HTMLファイルが生成されたディレクトリを見ると、ツールの名前がついたディレクトリが延々と並んでいます。JavaDocのようなIndex HTMLを出力する機能はなさそうです。
とはいえさほど複雑な構造でもありませんし、わざわざ作らずともApacheのIndexes機能を開放するだけで十分でしょう。
配置したLinux JMはとりあえず正常に読めるようになりました。Indexesも出せるようにしました。残る問題はGoogleが検索結果に出してくれるかどうかで、使い勝手という意味では割と大きい要素です。最初に紹介したように、私はmanpage + API名で検索してLinux JMが一番上に出る使い方に慣れきった軟弱者なので……他の文字を打たないと出ないなら使いにくいんです。
Googleはそのうちクロールしてくれると思うので、しばらく放置しようと思います。検索できるようになっても検索順位が低すぎるとか、どうにも使いにくかったらまた何か考えます。
目次: C言語とlibc
OSSのlibc実装の一つであるmusl libcのアトミックCAS(Compare And Swap)の実装を調べたメモです。CASはa_cas(p, t, s)関数に実装されていて、ポインタpの指す先の値がtなら、アトミックにsと入れ替える関数です。調べるのはRISC-V用の実装です。
コンパイラが提供するアトミック関数実装(stdatomic.h)は使わないみたいです。musl libc独自の実装となっています。
// musl/arch/riscv64/atomic_arch.h
#define a_cas a_cas
static inline int a_cas(volatile int *p, int t, int s)
{
int old, tmp;
__asm__ __volatile__ (
"\n1: lr.w.aqrl %0, (%2)\n"
" bne %0, %3, 1f\n"
" sc.w.aqrl %1, %4, (%2)\n"
" bnez %1, 1b\n"
"1:"
: "=&r"(old), "=&r"(tmp)
: "r"(p), "r"((long)t), "r"((long)s)
: "memory");
return old;
}
RISC-V向けの実装はLR/SC(Load and Reserve, Store Conditional)という仕組みを使い実装されています。RISC-V以外のアーキテクチャでも良く見かける機能で、見たことある方も多いと思います。LRはLL(Load Link)という名前のこともあるようです。
コードはたった4行です、1行ずついきましょう。
条件付きストアは、予約付きロードから条件付きストア間にpの指す先を誰も変更していない場合のみストアが成功します。pの指す先の値がsに変化します(tmpには0が返されます)。
もし予約付きロードから条件付きストアの間に誰かがpの指す先を変更していた場合はストアが失敗します。pの指す先の値は変化しません(tmpには0以外の値が返されます)。
< | 2023 | > | ||||
<< | < | 12 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | - | - | 1 | 2 |
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 | - | - | - | - | - | - |
合計:
本日: