Sat, 21 Dec 2002 20:12:59 JST / hina.di
powered by tds-1.3.0
<issei@issei.org>
近所の書店が元旦から営業しているということで、出かける。
あ、LaLa DX 探すの忘れてたよ。
全7巻なのですが、書店に2巻以降が置いていなかったので1巻だけ購入。 続きが楽しみ。
帯を見て気づいたのですが「イティハーサ」は第31回星雲賞の受賞作とのこと。そういえば昨年の星雲賞を受賞した作品って調べてないな、ということで Web をめぐって 星雲賞受賞作リスト に到着。おや、「刻の静寂」の挿絵を描いている鶴田謙二氏も、第31回星雲賞アート部門で受賞されてますね。
長編部門で受賞した「グッドラック 戦闘妖精・雪風」「キリンヤガ」は、すでに読んでたので、購入予定図書への追加はなく。
CPU 設計の話題。CPU レベルでスレッド多重化を行うことで、空いている実行ユニットを有効に使い、スループットを向上させる技術。out-of-order 機能が実装された super scaler プロセッサなら、割と小さな拡張 (ダイサイズ 10% 増) で実現できるらしい。
面白い内容だったので関連論文を漁っていたら、午前中は終わり。
デーモンモードで起動している sendmail が、SMTP (もしくは ESMTP) でメールを受け取ってから、再び SMTP でメールを送り出す過程を追ったメモ。参照したソースコードは FreeBSD 4.2-RELEASE に含まれている sendmail 8.11.1。
すべては、ここから始まる。
デーモンモードで起動された場合 (sendmail -bd) には、 getrequest() @ daemon.c を呼び出して、クライアントからの接続を待つ。コメントを信じると、クライアントから接続されると fork() でプロセスを分けた上で、子プロセスだけ main() に戻る。親プロセスは getrequst() で無限ループしており、次の接続を待ち続ける。
子プロセスは main() に戻ってくると、IP アドレスの記録や特権の放棄などを行って、smtp() を呼び出す。
クライアントから送られている SMTP (Simple Mail Transfer Protocol) 形式のデータを受け取る。
典型的な SMTP によるメール送信の様子は次の通り。クライアントが出力しているメッセージは 赤、sendmail が出力しているメッセージは黒で示してある。
220 tole.issei.org ESMTP Sendmail 8.11.1/8.11.1; Wed, 3 Jan 2001 01:04:56 +0900 (JST) HELO localhost 250 tole.issei.org Hello localhost [127.0.0.1], pleased to meet you MAIL FROM: issei@issei.org 250 2.1.0 issei@issei.org... Sender ok RCPT TO: issei@issei.org 250 2.1.5 issei@issei.org... Recipient ok RCPT TO: issei@FreeBSD.org 250 2.1.5 issei@FreeBSD.org... Recipient ok DATA 354 Enter mail, end with "." on a line by itself Subject: test From: Issei Suzuki <issei@issei.org> To: issei@issei.org, issei@FreeBSD.org
Are you happy? -- Issei.- . 250 2.0.0 f02G52C00599 Message accepted for delivery QUIT
メールの送信先 (RCPT To: ...) は複数続けることが可能。ソースコードでは case CMDRCPT: の部分で処理されるが、recipient() @ recipient.c を呼び出し送信先を連結リスト e->e_sendqueue に保存している。SMTP でのメール送信は、メール本文を送る DATA コマンドで終了する。これはソースコードの case CMDATA: 部分で処理されるが、最終的に sendall() @ deliver.c を呼び出す。
ここまでが SMTP でメールを受け取るまで、ここから先はメールを送り出す処理になる。
smtp() 関数から呼ばれた場合には mode の初期値は SM_DEFAULT。
/* determine actual delivery mode */
if (mode == SM_DEFAULT)
{
mode = e->e_sendmode;
if (mode != SM_VERIFY && mode != SM_DEFER &&
shouldqueue(e->e_msgpriority, e->e_ctime))
mode = SM_QUEUE;
}
sendmail をデーモンモード (sendmail -bd) で起動していると、この部分で mode == SM_FORK となる。結局、その後のコードで double fork して、親プロセスは呼び出し元の smtp() 関数に戻り、クライアントに対して "250 2.0.0 ... Message accepted for delivery" と出力して終了する。 子プロセスは sendenvelope() @ deliver.c を呼び出す。
エラーチェックやマクロ設定、キュー処理のコードを省くと、主要部分として次の for ループが残る。
/* now run through the queue */
for (q = e->e_sendqueue; q != NULL; q = q->q_next) {
deliver(e, q);
}
つまり smtp() 関数で e->e_sendqueue に保存しておいたメール送信先の各々に対して deliver() @ deliver.c を呼び出している。
まず e->e_sendqueue のリストから、同じホスト宛のもの取り出して集める。 関連する部分のコードを抜粋して示す。
static int
deliver(e, firstto)
register ENVELOPE *e;
ADDRESS *firstto;
{
register ADDRESS *to = firstto;
tobuf[0] = '\0';
e->e_to = tobuf;
ctladdr = NULL;
firstsig = hostsignature(firstto->q_mailer, firstto->q_host);
for (; to != NULL; to = to->q_next)
{
/* avoid sending multiple recipients to dumb mailers */
if (tobuf[0] != '\0' && !bitnset(M_MUSER, m->m_flags))
break;
/* if already sent or not for this host, don't send */
if (!QS_IS_OK(to->q_state) ||
to->q_mailer != firstto->q_mailer ||
strcmp(hostsignature(to->q_mailer, to->q_host),
firstsig) != 0)
continue;
/* avoid overflowing tobuf */
/* つづく */
hostsignature() はメールの送信先ホストのリスト (sendmail では hostsignature と読んでいる) を取得する関数で、これが一致している限り、送信先は同じということになる。e->e_sendqueue の先頭にあるメールの hostsignature を firstsig に保存しておき、これと同じ hostsignature をもつメールを e->e_sendqueue から取り出して集めている（コードの上では、hostsignature が異なるものを continue でスキップする、という書き方になっている）。
この先の処理はメール送信に使うメーラによって変わってくるが、以下では SMTP メーラ (sendmail.cf では P=[IPC] となっているもの) に関して追う。
else if (strcmp(m->m_mailer, "[IPC]") == 0 ||
strcmp(m->m_mailer, "[TCP]") == 0)
{
/* (中略) */
/*
* hostsignature に含まれるホストについて優先順位の高い順に
* hostbuf に接続先ホスト、port に TCP のポート番号を格納して
*/
i = makeconnection(hostbuf, port, mci, e);
makeconnection() @ daemon.c は gethostbyname(), socket(), connect() などのネットワーク通信関連のシステムコールを順次呼び出して、接続先ホストに対して TCP コネクションを張る。コネクションが確立したら fdopen() を使って socket からファイルポインタ (FILE *) を作り、引数 mci で渡された構造体中に格納する。
makeconnection() での処理に成功して返ってきたら SMTP を使ってメールの送信を始める。
/* ** Send the MAIL FROM: protocol */ rcode = smtpmailfrom(m, mci, e); /* MAIL From: を送る */ /* 以下続く */
ざっとソースコードを追ってみましたが、これで sendmail 内蔵の SMTP メーラの特徴が分かります。
問題は後者。
DNS の検索や TCP コネクションの設定は時間がかかる処理です。平均して一件あたり計 3 秒かかると仮定すると、100 のホストにメールを送信するだけでも最低 300 秒かかります。加えて、DNS サーバが落ちていたりネットワークに不調な部分があるなどの理由でタイムアウト待ちが発生すると、所要時間はさらに延びます。
これでは、メーリングリストなどを運用する際には、メールの配送に時間がかかりすぎて辛い。で、そういう場合には sendmail に SMTPfeed を組み合わせて使うのが常套手段。
sendmail のソースコードは、何というか、ものすごいコードだ……。
近所のコメントには、Kerberos認証を使っていない場合とか、安全ではない端末を使っている場合はrootログインを拒否すると書いてある。ソースをちらと見たところでは、「Kerberosを使っていない場合」ちうのがどこで判定されているかわからんかったけど...。
おそらく、昔のコメントを修正し忘れたのでしょう。PAM (Pluggable Authentication Modules) が login に取りこまれる前のコードでは当該部分は次のようになっていましたが、これならコメントは通りのコードですよね。
ttycheck:
/*
* If trying to log in as root without Kerberos,
* but with insecure terminal, refuse the login attempt.
*/
if (pwd && !rval) {
#if defined(KERBEROS)
if (authok == 0 && rootlogin && !rootok)
#else
if (rootlogin && !rootok)
#endif
refused(NULL, "NOROOT", 0);
else /* valid password & authenticated */
break;
}
修正するように send-pr かしら。
「リチャード獅子心王？」と言ったら笑われた（←…）
NetBSD のソースを読んでいたら __predict_false() という記述を見つける。
if (__predict_false((nprocs >= maxproc - 1 && uid != 0) ||
nprocs >= maxproc)) {
tablefull("proc", "increase kern.maxproc or NPROC");
return (EAGAIN);
}
gcc 2.96 から条件分岐の際に、分岐方向に関して静的にヒントを与える __builtin_expect という組込み関数が入ったので、それを利用しているらしい。__predict_false の定義を <sys/cdefs.h> から抜粋。
#if __GNUC_PREREQ__(2, 96) #define __predict_true(exp) __builtin_expect(((exp) != 0), 1) #define __predict_false(exp) __builtin_expect(((exp) != 0), 0) #else #define __predict_true(exp) ((exp) != 0) #define __predict_false(exp) ((exp) != 0) #endif
どの程度の効果があるのかな？
gcc のソースコードは「鬼門」なので、どこまで追えるか自信なし。
gcc の info を読んで __builtin_expect(EXP, C) の仕様を調べると、これは引数を二つ取る。最初の引数 EXP は C 言語の整数値を持つ式、次の引数 C は整数定数で、戻り値は EXP そのもの。
組込み関数 (__builtin_*) の処理は builtin.c だろうとアタリをつけて、builtin.c を expect で検索してみると、expand_builtin() -> expand_builtin_expect() と呼ばれて、ここで構文木から RTX (Register Transfer languate eXpression code, struct rtx) に変換しているらしい。
builtin.c
static rtx
expand_builtin_expect (arglist, target)
tree arglist;
rtx target;
{
tree exp, c;
rtx note, rtx_c;
if (arglist == NULL_TREE
|| TREE_CHAIN (arglist) == NULL_TREE)
return const0_rtx;
exp = TREE_VALUE (arglist);
c = TREE_VALUE (TREE_CHAIN (arglist));
if (TREE_CODE (c) != INTEGER_CST)
{
error ("second arg to `__builtin_expect' must be a constant");
c = integer_zero_node;
}
target = expand_expr (exp, target, VOIDmode, EXPAND_NORMAL);
/* Don't bother with expected value notes for integral constants. */
if (GET_CODE (target) != CONST_INT)
{
/* We do need to force this into a register so that we can be
moderately sure to be able to correctly interpret the branch
condition later. */
target = force_reg (GET_MODE (target), target);
rtx_c = expand_expr (c, NULL_RTX, GET_MODE (target), EXPAND_NORMAL);
note = emit_note (NULL, NOTE_INSN_EXPECTED_VALUE);
NOTE_EXPECTED_VALUE (note) = gen_rtx_EQ (VOIDmode, target, rtx_c);
}
return target;
}
arglist から __builtin_expect() の最初の引数に対応する構文木と、次の引数に対応する構文木を取り出し、それぞれ exp, c というローカル変数に割り当てている。
c が整数定数でない場合には __builtin_expect() の使い方が間違っているということで、エラー。次に exp の構文木を expand_expr() を使って RTX に翻訳。翻訳の結果 exp が整数定数だった場合には、そのまま得られた RTX を返す。後で最適化するときに条件分岐事態を消してしまうのでしょうね。
で、本題の exp が定数でない場合。force_reg() @ explow.c を呼び出して、exp の計算結果をレジスタに読み出すように指示し、NOTE_INSN_EXPECTED_VALUE というノートを作成しておく。
このノートが、後で expected_value_to_br_prob() @ predict.c で分岐予測に使われるようですが、この先は良く分からないのでパス。
#include <stdio.h>
volatile int xport;
int
main(void)
{
if (__builtin_expect(xport, EXPECTVAL))
do_some_work();
return 0;
}
マクロ EXCECTVAL の値を 0, 1 として出力されるアセンブラコードを見てみると、次のようになる。最適化オプションは -O2。
EXPECTVAL = 0
.file "foo.c" gcc2_compiled.: .ident "GCC (c) 2.97 20001225 (experimental)" .text .align 4 .globl main .type main,@function main: pushl %ebp movl %esp, %ebp movl xport, %eax subl $8, %esp testl %eax, %eax jne .L8 .L7: xorl %eax, %eax leave ret .p2align 2 .L8: call do_some_work jmp .L7 .Lfe1: .size main,.Lfe1-main .comm xport,4,4 .ident "GCC: (GNU) 2.97 20001225 (experimental)"
EXCECTVAL = 1
.file "foo.c" gcc2_compiled.: .ident "GCC (c) 2.97 20001225 (experimental)" .text .align 4 .globl main .type main,@function main: pushl %ebp movl %esp, %ebp movl xport, %eax subl $8, %esp testl %eax, %eax je .L7 call do_some_work .L7: xorl %eax, %eax leave ret .Lfe1: .size main,.Lfe1-main .comm xport,4,4 .ident "GCC: (GNU) 2.97 20001225 (experimental)"
両者を比較すると条件分岐するための命令が jne, je と異なっている。EXCEPTVAL = 0 の場合には jne を使っているため、__builtin_prediction に与えた予想通り xport = 0 であれば分岐は発生しない。逆に EXCEPTVAL = 1 の場合には xport = 1 であれば分岐が発生しない。
これ、分岐したときと分岐しないときで、どの程度の差が出るんでしょう？
アセンブラ出力を眺めていて気づいたのですが、最近の gcc では '\n' で終わる定数文字列を引数とする printf() 呼び出しは、puts 呼び出しに置換されてますね。処理しているのは c_expand_builtin_printf() @ c-common.c 。
細かい(^_^;)
nvi-m17nに GLOBAL サポートを追加するパッチ。nvi-1.79 + nvi-1.79.m17n-19991117 からの差分です。 GLOBAL 4.01 に含まれているオリジナルの nvi-1.79 用パッチを、機械的に nvi-m17n にマージしただけです。動作がおかしかったら、ごめんなさい。
基本的な使い方は、あらかじめ gtags でタグを生成後、nvi に -G オプション をつけて起動。これで tag コマンド関連はオリジナルの ctags のタグではな く、GLOBAL のタグを参照するようになります。良く使うコマンドは control-], tag, tagn, tagp あたりかな。
rtag コマンドも追加されてますね。後で、オリジナルの nvi-1.79 と FreeBSD の /usr/src/contrib/nvi の差分もチェックしよう。
永らく FORBIDDEN になっている FreeBSD の tcsh NLS カタログ port を復活させるべく、準備。
issei@cur% llll llll: コマンドが見つかりません. issei@cur% set catalog=dejiko issei@cur% llll llll: こまんどが見つからないにょぉ〜. issei@cur% set catalog=sakura issei@cur% llll llll: ほぇ〜。コマンドが見つからないよぉ. issei@cur% set catalog=ayanami issei@cur% llll llll: コマンド 見つからない....
とりあえず、できたトコロまで置いときます。要 tcsh 6.10.00 以降ですので FreeBSD-CURRENT, -STABLE を使っていない人は注意して下さい。
アニメ「名探偵コナン」のテーマソング集。「胸がドキドキ」「Step by Step」とか初期の曲が未収録なのは……。
ここ数日「386BSD カーネルソースコードの秘密」を再読中。以前より、だいぶ読めるようになってる。
この本は CPU やアーキテクチャに依存したコードの解説から始めているのに、x86 アーキテクチャに関する解説はほとんどない。そのため x86 の詳細や基本的な UNIX アーキテクチャに関して予め知識がないと、まず読めない。またコードの引用量が限定されているため、それだけから全体像を把握することは困難。BSD の内部を解説した技術文書として、この本の価値はきわめて高いし、著者の能力の高さは疑うべくもないものの、読者の立場からは必ずしも良い本とは言いがたい *1。
Lions 先生の「Lions' commentary on UNIX」と UNIX Version 6 のソースコードは、卓越した作品なのだな、とあらためて思う。
アニメ放映時に断片的に見たものの、通してストーリーを追ったことがなかった ので、少女マンガの偉い人に借りて読みました。
ストーリーも登場人物も深みゼロですが、面白いのは確か。後で「ミントな僕ら」 も読んでみよう。
昨日から、体調不良につき寝込んでます。 一日 20 時間ぐらい眠ってますが（人間って、こんなに眠れるものなのね）熱のせいか、眠っていても夢にうなされる状態。いやはや。
明日も症状が好転しなかったら、医者に行こう。
体温、久方ぶりに平熱を回復。身体が軽い。
風邪ですが、ようやく外出できる程度に回復しました。
結局、先々週の土曜日から翌木曜日まで丸６日間は熱が下がらず、その後は微熱 になったものの日曜日までは体調が思わしくないということで、一週間以上、寝 込んでいました。これだけ長期間寝込んだのは、幼児期以来じゃないかしら？
まだ寒さの厳しい折、関東では今週再び雪も降るようですし、皆様くれぐれも健 康にご注意のほどを。
YAMAHA のルータは簡易 DNS サーバとしても働くんですが、もしかして BIND からコー ドを持ってきてる？
issei@tole% dig @192.168.0.1 CHAOS TXT VERSION.BIND ; <<>> DiG 8.3 <<>> @192.168.0.1 CHAOS TXT VERSION.BIND ; (1 server found) ;; res options: init recurs defnam dnsrch ;; got answer: ;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 6 ;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0 ;; QUERY SECTION: ;; VERSION.BIND, type = TXT, class = CHAOS ;; ANSWER SECTION: VERSION.BIND. 0S CHAOS TXT "8.2.3-T6B" ;; Total query time: 67 msec ;; FROM: tole.issei.org to SERVER: 192.168.0.1 ;; WHEN: Wed Jan 31 05:54:43 2001 ;; MSG SIZE sent: 30 rcvd: 64
合間を縫ってスレッドプログラミングのお勉強。 参考書は O'Reilly の「Pthreads プログラミング」と Solaris 8 Answer Book 2。Solaris 8 は OS やライブラリの質が高いのは言うまでもない ですが、ドキュメントが充実してる点も素晴らしい。Answer Book 2 は Solaris 8 についてきますが http://docs.sun.com/ でも公開されてます。
ドキュメントにざっと目を通したところで、実際にコードを書いてみようという ことで、手元にあるデバッグ用のメモリアロケータ (malloc, realloc, strdup, free のラッパルーチン, 600 行ぐらいの小さなコード) をリエントラ ントにしてみる。
性能を考えなければライブラリのマルチスレッド化は簡単で、外部に公開してい る関数の入り口でロックをかけて、戻る直前にアンロックすれば OK。
void *
xmalloc(size_t size)
{
void *p;
pthread_mutex_lock(&xmdb_lock); /* 追加 */
/* 従来のコード */
pthread_mutex_unlock(&xmdb_lock); /* 追加 */
return p;
}
ただし、これだとパフォーマンスがかなり悪化するので、本当に保護すべき部分 だけロックしたい。そうすると、必然的にモジュール内部にロックが分散するこ とになるので、プログラミングの難易度が ぐっ と上がる。
元のコードが小さく保護すべきデータが少ないため、排他制御が必要な部分は、 すぐに分かる。難しいのは、排他制御をプログラムに組み込む位置を決めること。
ロックの保持状態を考えながら内部関数の呼び出し順序を厳密に制御しないと、 確保済みのロックを再度確保しようと試みたり、複数ロックの確保順序をめぐっ てデッドロックが簡単に発生してしまう。特に危険なのは、共有データに関連付 けられたポインタを返す関数。あるスレッドが得たポインタを利用する前に他の スレッドが共有データを操作すると、ポインタの先にあるデータが想定したもの と違ってしまう。
そのため、既存のライブラリのマルチスレッド化には、内部関数の呼び出し系列、 ならびにデータの流れの見直しが必須。スマートな方法が思いつかなかったので、 モジュール中の関数の呼び出し系列を手作業で書き出し、どこでロックを確保し てどこで開放するか考えて、コードに手を入れていきました。
(続く…かな？)
ライブラリのスレッドセーフ化の途中でエンバグした事例。排他制御でも失敗し ましたが、それは長くなるので省略して pthread_once の件。
inline static int
xmhash_lock(int index)
{
pthread_once_t once = PTHREAD_ONCE_INIT;
assert(0 <= index && index < HASHTBLSIZE);
pthread_once(&once, xmhash_init);
return pthread_mutex_lock(&xmhash_mutex[ index ]);
}
pthread_once は第一引数として渡された変数に、初期化を完了しているかどう かの情報を記録しておくため、自動変数にしてはまずい。正しくは、こう。
inline static int
xmhash_lock(int index)
{
static pthread_once_t once = PTHREAD_ONCE_INIT;
assert(0 <= index && index < HASHTBLSIZE);
pthread_once(&once, xmhash_init);
return pthread_mutex_lock(&xmhash_mutex[ index ]);
}
xmhash_init は mutex 変数の配列 xmhash_mutex を初期化するため、このバグ の帰結として、&xmhash_mutex[ index ] で排他制御している部分で排他制御が 正常に働かなくなり、保護すべきデータが壊れます。再現性がなく、また結果か ら原因を見つけ出すのが困難なタチの悪いバグ。
Win32 API にも移植しようと思ったところ、これには pthread_once() に相当す る関数がないことが判明。Win32 の mutex は静的に初期化することができない ので、複数スレッドから呼ばれても、一度だけ初期化関数を実行するようにした いのですが、どうするか。
MSDN Library を調べると InterlockedIncrement() を発見。これを使えば pthread_once() 相当の関数が作れるかな？
InterlockedIncrement
指定された32ビット変数の値をインクリメントします（1つ増やします）。この 関数は、複数のスレッドによる同じ変数の同時使用を防ぎます。