ハノイの塔では、塔a, b, c があり、 初期状態で a に disk 1 から n があり、 b に移動させるという問題である。
昨日、おぎのさんに、disk n-1 を塔c に移動させてはならないという制約を加えた話があるということを聞いたので考えてみる。
簡単のために n=3 としてみる。
1 | | 2 | | 3 | | a b c
| | | 2 | | 3 | 1 a b c
| | | | | | 3 2 1 a b c
| | | | 1 | 3 2 | a b c
| | | | 1 | | 2 3 a b c
| | | | | 1 | 2 3 a b c
| | | | | 1 2 | 3 a b c
| | | 1 | | 2 | 3 a b c
| | | 1 | | 2 3 | a b c
| | | | | | 2 3 1 a b c
| | | | 2 | | 3 1 a b c
| 1 | | 2 | | 3 | a b c
ふむ。たしかに出来る。
結局、disk n を直接 b に移動するのではなく、c を経由して b に移動すればいいようだ。
% google-count ねー{う,く,す,つ,ぬ,ふ,む,ゆ,る}ーいー
0 ねーうーいー
0 ねーくーいー
1 ねーすーいー
0 ねーつーいー
0 ねーぬーいー
0 ねーふーいー
9190 ねーむーいー
0 ねーゆーいー
0 ねーるーいー
昨日、autobuild を動かしている OpenBSD が止まっていたので再起動した。
ところが今日もまた止まっていた。
調べてみると、autobuild の途中で止まっているらしい。 というか、make test-all の途中で止まっている。
さらに調べてみると、メモリを食いすぎると止まることが分かった。 OS が止まる以外に SEGV になる場合もあった。
メモリを食いすぎる原因は、昨日足したテストのひとつが失敗したときに fork したプロセスが残っていたことであった。 なので失敗したときには kill するようにしておく。
それはそれとして、プロセスじゃなくて OS が止まるというのは納得しがたいものがあるが...
% for y in {1990..2005}
google-count --words $y 'unknown node type 0'
4 1990 unknown node type 0
4 1991 unknown node type 0
3 1992 unknown node type 0
2 1993 unknown node type 0
4 1994 unknown node type 0
2 1995 unknown node type 0
3 1996 unknown node type 0
15 1997 unknown node type 0
22 1998 unknown node type 0
24 1999 unknown node type 0
46 2000 unknown node type 0
112 2001 unknown node type 0
622 2002 unknown node type 0
601 2003 unknown node type 0
894 2004 unknown node type 0
152 2005 unknown node type 0
それはそれはそれとして、プロセスグループを kill してるんだからプロセスが残っているのは変である。 というわけで調べてみると、プロセスグループを kill してるのはタイムアウトしたときだけであった。
というわけで普通に終ったときもプロセスグループを (生き残っていたら) 殺すようにする。
IA-64 での getcontext/setcontext で r32 が復元されないという話を小さなプログラムで再現することに成功したので報告しておく。
そういえば、codefest のときにもひとつ報告した。
getcontext/setcontext がだめなら unwind を使うとどうか、と思って試してみる。
rx1620% gcc -g -Wall -O2 tst2.c -lunwind
rx1620% cat tst2.c
#include <stdlib.h>
#include <stdio.h>
#define UNW_LOCAL_ONLY
#include <libunwind.h>
int flag;
unw_context_t cont;
unw_cursor_t cursor;
static void f(void)
{
int ret;
flag = 1;
fprintf(stderr, "before unw_resume\n");
ret = unw_resume(&cursor);
fprintf(stderr, "after unw_resume\n");
if (ret != 0) { fprintf(stderr, "unw_resume failed: %d\n", ret); exit(1); }
}
static void h(void)
{
int ret;
ret = unw_getcontext(&cont);
fprintf(stderr, "unw_getcontext returned\n");
if (ret != 0) { fprintf(stderr, "unw_getcontext failed: %d\n", ret); exit(1); }
ret = unw_init_local(&cursor, &cont);
if (ret != 0) { fprintf(stderr, "unw_init_local failed: %d\n", ret); exit(1); }
ret = unw_step(&cursor);
if (ret < 0) { fprintf(stderr, "unw_step failed: %d\n", ret); exit(1); }
}
static int g(void)
{
int ret;
flag = 0;
h();
ret = flag;
if (ret == 0) {
printf("first\n");
f();
printf("f returned\n");
}
else {
printf("second\n");
}
return ret;
}
int main(int argc, char **argv)
{
g();
fprintf(stderr, "g returned\n");
return 0;
}
rx1620% ./a.out
unw_getcontext returned
first
before unw_resume
zsh: segmentation fault ./a.out
rx1620% gdb a.out
GNU gdb 6.3-debian
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "ia64-linux"...Using host libthread_db library "/lib/libthread_db.so.1".
(gdb) display/i $pc
(gdb) run
Starting program: /home/akr/z/a.out
unw_getcontext returned
first
before unw_resume
Program received signal SIGSEGV, Segmentation fault.
g () at tst2.c:38
38 ret = flag;
1: x/i $pc 0x4000000000000e31 <g+65>: ld4 r32=[r32]
(gdb) disassemble
Dump of assembler code for function g:
0x4000000000000df0 <g+0>: [MMB] alloc r34=ar.pfs,5,4,0
0x4000000000000df1 <g+1>: addl r14=360,r1
0x4000000000000df2 <g+2>: nop.b 0x0
0x4000000000000e00 <g+16>: [MII] mov r35=r1
0x4000000000000e01 <g+17>: mov r33=b0;;
0x4000000000000e02 <g+18>: nop.i 0x0
0x4000000000000e10 <g+32>: [MMI] mov r32=r14;;
0x4000000000000e11 <g+33>: st4 [r32]=r0
0x4000000000000e12 <g+34>: nop.i 0x0
0x4000000000000e20 <g+48>: [MIB] nop.m 0x0
0x4000000000000e21 <g+49>: nop.i 0x0
0x4000000000000e22 <g+50>: br.call.sptk.many b0=0x4000000000000c60 <h>;;
0x4000000000000e30 <g+64>: [MMI] mov r1=r35
0x4000000000000e31 <g+65>: ld4 r32=[r32]
0x4000000000000e32 <g+66>: nop.i 0x0;;
0x4000000000000e40 <g+80>: [MII] addl r36=136,r1
0x4000000000000e41 <g+81>: addl r14=144,r1
0x4000000000000e42 <g+82>: cmp4.eq p7,p6=0,r32;;
0x4000000000000e50 <g+96>: [MIB] (p06) ld8 r36=[r36]
0x4000000000000e51 <g+97>: nop.i 0x0
0x4000000000000e52 <g+98>: (p06) br.cond.dptk.few 0x4000000000000ea0 <g+176>;;
0x4000000000000e60 <g+112>: [MIB] ld8 r36=[r14]
0x4000000000000e61 <g+113>: nop.i 0x0
0x4000000000000e62 <g+114>: br.call.sptk.many b0=0x40000000000008c0 <_init+512>;;
0x4000000000000e70 <g+128>: [MIB] mov r1=r35
0x4000000000000e71 <g+129>: nop.i 0x0
0x4000000000000e72 <g+130>: br.call.sptk.many b0=0x4000000000000b30 <f>;;
0x4000000000000e80 <g+144>: [MMI] mov r1=r35;;
0x4000000000000e81 <g+145>: addl r36=152,r1
0x4000000000000e82 <g+146>: nop.i 0x0;;
0x4000000000000e90 <g+160>: [MII] ld8 r36=[r36]
0x4000000000000e91 <g+161>: nop.i 0x0
0x4000000000000e92 <g+162>: nop.i 0x0
0x4000000000000ea0 <g+176>: [MIB] nop.m 0x0
0x4000000000000ea1 <g+177>: nop.i 0x0
0x4000000000000ea2 <g+178>: br.call.sptk.many b0=0x40000000000008c0 <_init+512>;;
0x4000000000000eb0 <g+192>: [MMI] mov r8=r32
0x4000000000000eb1 <g+193>: mov r1=r35
---Type <return> to continue, or q <return> to quit---
0x4000000000000eb2 <g+194>: mov.i ar.pfs=r34
0x4000000000000ec0 <g+208>: [MIB] nop.m 0x0
0x4000000000000ec1 <g+209>: mov b0=r33
0x4000000000000ec2 <g+210>: br.ret.sptk.many b0;;
End of assembler dump.
(gdb) break *0x4000000000000e31
Breakpoint 1 at 0x4000000000000e31: file tst2.c, line 38.
(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/akr/z/a.out
unw_getcontext returned
Breakpoint 1, g () at tst2.c:38
38 ret = flag;
1: x/i $pc 0x4000000000000e31 <g+65>: ld4 r32=[r32]
(gdb) p $r32
$1 = 6917529027641088280
(gdb) c
Continuing.
first
before unw_resume
Breakpoint 1, g () at tst2.c:38
38 ret = flag;
1: x/i $pc 0x4000000000000e31 <g+65>: ld4 r32=[r32]
(gdb) p $r32
$2 = 0
(gdb) si
Program received signal SIGSEGV, Segmentation fault.
g () at tst2.c:38
38 ret = flag;
1: x/i $pc 0x4000000000000e31 <g+65>: ld4 r32=[r32]
(gdb)
rx1620% gcc -g -Wall tst2.c -lunwind
rx1620% ./a.out
unw_getcontext returned
first
before unw_resume
second
g returned
rx1620% うぅむ。同じ症状か。
Intel(R) Itanium(R) Software Conventions & Runtime Architecture Guide によれば、 setjmp/longjmp では、r32 (以降) は保存されないのだそうだ。
とすると getcontext/setcontext もおそらく同様で、 問題はむしろ setcontext で r32 が壊れないことを仮定しているコンパイラが悪い?
とはいえ、r32 は普通の関数呼び出しでは自動的に保存されるので、 setjmp/setcontext と普通の関数が違うことを教えてやらない限りそういうコードが生成されるのは分からないでもない。 その違いを指定できればいいのだが... そういう属性は見当たらない?
gccint のほうを覗くと、
`NON_SAVING_SETJMP'
If this macro is defined and has a nonzero value, it means that
`setjmp' and related functions fail to save the registers, or that
`longjmp' fails to restore them. To compensate, the compiler
avoids putting variables in registers in functions that use
`setjmp'.
というのが見つかる。
必要なのはこれなのである。これの影響を getcontext/setcontext に及ばせられればいいのだが...
調べていくと、setjmp という名前の関数を使っているとレジスタ割り当てのやりかたが変化することが判明。 なんというか黒魔術である。
gcc のソースを眺めると、なんかそれっぽい名前の判断が入っている。 setjmp 以外にもいくつかあるようだ。 が、getcontext は入っていない。
ここに getcontext を追加してもらうのが修正としては簡単だろうか。
ただ、libunwind とかまで考えるときりがない気はするので、バグというべきかどうかは判然としない。
jargon の black magic の項を読むと、黒魔術というのは「誰も」理解していないものを指すらしい。 とすると、黒魔術というのは言いすぎか。
単なる魔術、もしくは voodoo programming あたりが妥当か。
というわけで、gcc を変えるのは今よりも邪悪にはならずに (今と同程度の邪悪さで) 近い未来において問題を解決できる方法であるようなので、とりあえずは報告しておく。
GCC Bug 21957 - IA-64 register stack is not preserved after getcontext call
(最初 w3m で submit したら改行がつぶれてしまった。)
それはそれとして、今よりも邪悪でもいいからとにかく即座に現時点で解決するにはどうするかな。
Linux Conference 抄録集第 3 巻 (2005 年)
あ、もう公開されているのか。素早くてよろしい。
そういえば、64bit は日本語でだいたいどれくらいか?
% ruby -e 'p 1 << 64' 18446744073709551616
1844京6744兆0737億0955万1616 というわけで、だいたい 千八百京 (signed なら九百京) か。
塵劫記オーバーフローはまだまだ先の話である。
debian sarge では shutdown -h が poweroff か halt かを -H, -P で選べる上、 デフォルトを /etc/default/halt で選択できることを知った。
apm というコマンドを使っていたが、acpi になって戸惑う。
FSIJ の会計をチェックして、いくつかバグを見つける。
個々の事象は理解でき問題ない。 また、最終的にまとめられた書類に載っている数値も、 加算 (まれに減算) するとその数値になるような事象の集合を見つけることが出来る。 だから、(見つけたバグは修正してもらうとして) おそらく正しい計算になっているのだと思う。
が、なんというか、地に足がついている気がしない。 表面的に現われた数値だけを操作していて、モデルを理解していないというか。 あるいは、意味に引きずられて理解をしているというか。
プログラムでいえば、TRUE という名前の式は真であると理解するというか。
あるいは「プログラムは意図したとおりではなく書いたとおりに動く」という言葉でいえば、 意図は理解できたが、書かれたものがその意図をちゃんと表現しているかどうかに確信が持てないというか。
プログラムに関してはこういう感覚を最近感じた覚えがない。 もちろん、分からないことはいろいろあるわけだが、 分からないときに頼るのはリファレンスマニュアル、規格、処理系のソースなどであって、 対象プログラム自体ではない。
だが、もしかしたら、初心者はこういう感覚でプログラムを組んでいるのだろうか。
ふと、
% od -x /dev/random
としてみると、一行毎にしか出て来ない。
なんとなく、1byte 毎に出て来るものを書いてみる。
% ruby -e '
off = 0
buf = ""
loop {
printf "%08x", off
16.times {
if buf.empty?
STDOUT.flush
buf << STDIN.readpartial(4096)
end
printf " %02x", buf[0]
buf[0,1] = ""
}
off += 16
puts
}' < /dev/random
そういえば、これも長さと終端が不明で、一気に読み出すには readpartial が必要な例だな。 このスクリプトの場合は gets, read と混用するわけではないので sysread でもいいのだが。 まぁ、sysread を使うと EINTR 対策が必要になるかもしれないというのはあるか。
一般には、/dev/random に対して gets で一行読み出す状況はちょっと想像できない。 read で固定長だけ読み出すのは考えられなくもない... が、read するとバッファリングで無駄にエントロピーを消費してしまうのであまりよろしくない。 かといって readpartial を使うと読みだしたい長さだけ読まないことがあるのでうまくない。 ふむ。その場合はすっきりした書き方はいまのところないか。
無理矢理 gets を使う例を考えてみる...
ランダムなバイト列において特定のバイトがどのような間隔で現われるかの頻度分布を調べようと思ったときには使えなくもないか。
% ruby -e 'h = Hash.new(0)
1000000.times {
len = STDIN.gets.length
h[len] += 1
}
(0..h.keys.max).each {|l|
printf "%d %s\n", l, "*" * (h[l] / 100)
}
' < /dev/urandom
BSP のとりかたを調べてみる。
% cat stack.c
#include <stdio.h>
#include <ucontext.h>
void *g()
{
void *addr;
asm (";;\n\tmov %0 = ar.bsp;;" : "=r" (addr));
return addr;
}
void f()
{
int var;
void *addr;
ucontext_t ctx;
asm (";;\n\tmov %0 = ar.bsp;;" : "=r" (addr));
getcontext(&ctx);
printf("%016x %016x %016x %016x %016x\n",
(long)&var,
(long)addr, (long)__builtin_ia64_bsp(),
(long)ctx._u._mc.sc_ar_bsp, (long)g());
f();
}
int main()
{
f();
return 0;
}
% gcc -O2 stack.c
% ./a.out|head
00000000ffffb5f0 00000000ffffe2e0 00000000ffffe2e0 00000000ffffe300 00000000ffffe300
00000000ffffab80 00000000ffffe300 00000000ffffe300 00000000ffffe320 00000000ffffe320
00000000ffffa110 00000000ffffe320 00000000ffffe320 00000000ffffe340 00000000ffffe340
00000000ffff96a0 00000000ffffe340 00000000ffffe340 00000000ffffe360 00000000ffffe360
00000000ffff8c30 00000000ffffe360 00000000ffffe360 00000000ffffe380 00000000ffffe380
00000000ffff81c0 00000000ffffe380 00000000ffffe380 00000000ffffe3a0 00000000ffffe3a0
00000000ffff7750 00000000ffffe3a0 00000000ffffe3a0 00000000ffffe3c0 00000000ffffe3c0
00000000ffff6ce0 00000000ffffe3c0 00000000ffffe3c0 00000000ffffe3e0 00000000ffffe3e0
00000000ffff6270 00000000ffffe3e0 00000000ffffe3e0 00000000ffffe408 00000000ffffe408
00000000ffff5800 00000000ffffe408 00000000ffffe408 00000000ffffe428 00000000ffffe428
これをみると、
ことがわかる。
ついでにいえば、普通のスタックが上位アドレスから下位アドレスに向けてのびていくのに対し、 register stack はそれとは逆方向に離れていく感じでのびていくことも分かる。
SPARC でも小さなプログラムで再現できたので報告しておく。
IA64 のときと違い反応があって素晴らしい。
+02:00 なところへ
目覚し時計がないことに気がつく
目覚し時計くらいプログラムすればいいではないかということに気がつく
Michael Neumann と会う。
Syn flood への対策として、Syn を受け取ったときに資源が足りないときには Syn-received な中でいちばん古いものを除去して資源を確保して受け付けるというのはあるのだろうか。
samidare での template 内の self を Presen というクラスに変える。
そして、template 内で膨らんでいたコードのひとつをそっちに移す。
template 内のコードを括り出すリファクタリングが容易なことは htree template の設計時点から考慮していたのだが、 いままで self が Hash だったので移す先として適切でなかった。
そういえば、結局目覚し時計は作らなかった。
RubyConf に出したのは accept された模様。
失敗することはそれはそれとして、 エラーメッセージが出る位置が気になる。
+ env ./ruby sample/test.rb sample/test.rb:1739: undefined method `call' for nil:NilClass (NoMethodError) assignment ok 1 ok 2 ... ok 8 ok 9 signal
エラーメッセージが最初に出て、他のメッセージが後に出ている。
おそらく、これはエラーメッセージが stderr でバッファリングされず、 他のメッセージが stdout でバッファリングされているために起きたものであろう。
これを防ぐ方法はいくつか考えられるが、 一般に、同じ対象につながっている複数の fd を認識できたと仮定すると、 どういう方針でバッファリングを制御すれば順序の入れ替わりを防げるか?
作業をしていると、突如として廊下から部屋へ風が吹き込み始めた。
べつに窓を開けたとかそういうことはなく突然である。 扉の外で風が荒れ狂っていることもないし、吹き込んだ風がどこから吹き出しているかも判然としない。
結局、管理会社に尋ねてみると、隣の部屋で排煙ボタンを押してしまったという答であった。うぅむ。
[latest]