コグノスケ


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

link もっと前
2023年12月1日 >>> 2023年11月18日
link もっと後

2023年12月1日

musl libcのpthread_barrier_wait()の実装 その1、Owner

目次: C言語とlibc

誰得かわかりませんが、musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。このAPIはバリア同期を実現するためのAPIで、POSIXという規格の一部です。バリア同期はある地点に指定した数のスレッドが全員到達するまで、全スレッドを待機させる同期機構です。

バリアに到達したスレッドがNスレッド(N >= 2)あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな?

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

いっぺんに説明すると意味不明なので、順番に説明します。最初はOwnerからです。

Owner

自分がOwnerかどうか判定する条件はバリア変数の_b_instがNULLであることです。Ownerのやることはインスタンスを作成しバリア変数(pthread_barrier_t)に設定することと、バリアから一番「最後」に脱出してインスタンスを破棄することです。インスタンスはmuslの用語ですかね?それはさておいてインスタンスは1回のバリア同期に必要なパラメータがおかれた場所です。

インスタンスの必要性を簡易に説明するのは難しいですね……バリア変数は使いまわされるからです。具体例で言うと、1回目のバリアからスレッドが脱出している途中で、先に脱出した他のスレッドが2回目のバリアに到達する、というケースが発生します。もしバリアのカウンタ値などをバリア変数に置いてしまうと、1回目のバリアの処理と2回目のバリアの処理が混ざって正常に処理できなくなります。

Ownerに関連するコードは下記のとおりです。

pthread_barrier_wait()の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のようなヒープでも目的は達成できますが、速度的に不利でしょう。面白い実装ですね。

続きはまた今度。

編集者:すずき(2023/12/04 02:43)

コメント一覧

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



2023年11月29日

newlib-4.3.0 for RISC-V 32bitのバグ

目次: RISC-V
目次: C言語とlibc

RISC-V用のツールチェーンを更新しているときに気づいたバグです。

現在の時刻を取得するgettimeofday()というAPIがあります。newlib-4.1.0ではSYS_gettimeofdayを使っていましたが、newlib-4.3.0ではSYS_clock_gettime64を使うように変更されました。が、これがバグっていました。

newlib-4.3.0のgettimeofday()の実装

// 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>

コミットの日付を見てびっくりしたのですが、なんと今日のコミットです。きっと世界のどこかで私と同じようなことを調べ、なんじゃこりゃー?!とバグを見つけて直した人が居たんでしょう。やー、奇遇ですね……。

編集者:すずき(2023/12/04 00:39)

コメント一覧

  • 大山恵弘さん(2023/12/02 18:53)
    すずきさんのX(旧Twitter)へのポストを見て気づいた可能性もあるかもしれないと思っています.
    私はOSの時間管理に興味があるので時々gettimeofdayでエゴサーチをかけますが,そのエゴサーチで私はすずきさんのこのポストに気づきました.
    そして,これはすごいバグがみつかったと思っていたところでした.

    今回のfixを施したのは日本語を理解しない人かもしれませんが,当該ポストの画像を見れば何がまずいかはどの国の人にも一目瞭然だと思います.
  • すずきさん(2023/12/03 00:35)
    大山先生、お久しぶりです。コメントありがとうございます。

    gettimeofdayでエゴサーチ……!!さすがです、私はやったことがありませんでした。
    私がバグに気づいてnewlibのリポジトリをチェックしたとき、既に修正されていたので、本当にほぼ同時に気づいた(向こうの方が修正&ML投稿の時間分だけ早いですが)のだろうと思います。偶然ってすごいです。
  • hdkさん(2023/12/03 18:49)
    >(本来1usなのに1msになってしまう)

    1 nsが1 msになる、ですかね。本来の値の範囲を大幅に超えて桁溢れもおこしてしまいそうなバグですね...
  • すずきさん(2023/12/04 00:38)
    あ、そうか。1nsですね。ありがとうございます。
open/close この記事にコメントする



2023年11月28日

glibcのclone_threadが使うシステムコール

目次: 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-2.38の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というヘッダにあります。

clone3を使うか使わないかのスイッチ(RISC-V向け)

// 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()が使っているシステムコールが変わる仕組みでした。良くできてます。

編集者:すずき(2023/11/30 22:46)

コメント一覧

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



2023年11月24日

Linux JMプロジェクトとOSDNの崩壊

目次: Linux

OSDNがOSCHINAに売却された(「OSDN」が中国企業に買収〜日本のオープンソースプロジェクトホスティングサービス - 窓の杜)影響か、最近OSDNのWWWサーバーが応答しなくなりました。人によっては「ふーん、そうなん」で終わりですが、私は非常に困ることが1点あります。Linux JMが見えなくなったことです。

Linux JMとはLinuxのman(マニュアル、英語)を日本語訳して公開してくれている超ありがたいプロジェクトです。man形式だけでなくHTML形式も作成していて、同プロジェクトのサイトにて公開されています……いました。Linux JMおよび同サイトがOSDNでホスティングされているため、今回の騒動で見えなくなってしまいました。

私はmanpage + API名という雑な検索をしても、ほぼ一番最初に出てくるLinux JMを大変重宝しておりました。これが使えなくなるのは辛いよー……。

ソースコードリポジトリは公開されていますので、泣き言を言う暇があったら自分でHTMLに変換すれば良かろうって?全く持っておっしゃるとおりですね。やりましょう。

Linux JMプロジェクトのリポジトリ

リポジトリのアドレスはgit://git.osdn.net/gitroot/linuxjm/jm.gitです。OSDNのシステムをよく知りませんが、GitHubなどとは異なりHTTPSでcloneできるサーバーはなさそうな気配です。リポジトリは他に3つ存在しますが、いずれも過去の履歴を保持するために残されたリポジトリです。READMEファイル以外は何も入っていません。

  • git://git.osdn.net/gitroot/linuxjm/LDP_man-pages.git
  • git://git.osdn.net/gitroot/linuxjm/coreutils.git
  • git://git.osdn.net/gitroot/linuxjm/iptables.git

今回はこれらは使いませんので、リポジトリのアドレスを紹介するだけに留めます。

Linux JMプロジェクトのビルド

ビルドというほど大げさでもないですけど。apt-getなどでman2htmlをインストールした後に、下記を実行します。

Linux JMのビルド方法(HTMLファイルのみ)
$ 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ファイルを使うのが手っ取り早いでしょう。


CSS適用後の表示画面

いつもの見慣れたデザインになりました。黄色いデザインのイメージでしたが、デフォルトは青いみたいです。知りませんでした……。

一覧を見る方法

HTMLファイルが生成されたディレクトリを見ると、ツールの名前がついたディレクトリが延々と並んでいます。JavaDocのようなIndex HTMLを出力する機能はなさそうです。


ApacheのIndex表示でLinux JMの一覧を見る

とはいえさほど複雑な構造でもありませんし、わざわざ作らずともApacheのIndexes機能を開放するだけで十分でしょう。

検索が悩ましい

配置したLinux JMはとりあえず正常に読めるようになりました。Indexesも出せるようにしました。残る問題はGoogleが検索結果に出してくれるかどうかで、使い勝手という意味では割と大きい要素です。最初に紹介したように、私はmanpage + API名で検索してLinux JMが一番上に出る使い方に慣れきった軟弱者なので……他の文字を打たないと出ないなら使いにくいんです。

Googleはそのうちクロールしてくれると思うので、しばらく放置しようと思います。検索できるようになっても検索順位が低すぎるとか、どうにも使いにくかったらまた何か考えます。

編集者:すずき(2024/01/13 13:49)

コメント一覧

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



2023年11月21日

musl libcのアトミックCAS実装

目次: 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 libcのアトミックCAS実装

// 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行ずついきましょう。

  • 1行目: pの指す先を予約付きロードします。ロードした値は変数oldに格納されます。
  • 2行目: ロードした値がtでなければ終了します。
  • 3行目: ロードした値がtならばpの指す先にsを条件付きストアします。
  • 4行目: 条件付きストアが成功したら終了、失敗したら1行目に戻ります。

条件付きストアは、予約付きロードから条件付きストア間にpの指す先を誰も変更していない場合のみストアが成功します。pの指す先の値がsに変化します(tmpには0が返されます)。

もし予約付きロードから条件付きストアの間に誰かがpの指す先を変更していた場合はストアが失敗します。pの指す先の値は変化しません(tmpには0以外の値が返されます)。

編集者:すずき(2023/11/25 03:33)

コメント一覧

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



link もっと前
2023年12月1日 >>> 2023年11月18日
link もっと後

管理用メニュー

link 記事を新規作成

<2023>
<<<12>>>
-----12
3456789
10111213141516
17181920212223
24252627282930
31------

最近のコメント5件

  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」
  • link 24年1月24日
    すずきさん (02/13 11:48)
    「ありがとうございます。\n私のPCはもう...」
  • link 24年1月24日
    えはらさん (02/12 15:00)
    「Powershellのスクリプトは以下の...」

最近の記事3件

  • link 24年2月28日
    すずき (02/27 09:09)
    「[100万回のHello, World! - バイナリサイズを削って遊ぼう、究極編その2] 目次: ベンチマーク前回(2024...」
  • link 23年4月10日
    すずき (02/27 02:26)
    「[Linux - まとめリンク] 目次: Linuxカーネル、ドライバ関連。Linuxのstruct pageって何?Linu...」
  • link 20年6月22日
    すずき (02/27 02:26)
    「[LinuxデバイスツリーのYAMLドキュメントチェッカー] 目次: Linux最近、というほどでもないのですが、Linux ...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
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 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

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

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 02/27 09:09