FreeBSD/amd64 な環境の中に、chroot できる FreeBSD/i386 な環境を作ってみる。
たしかファイルを繋げて tar で展開すれば良かったはず、とうろおぼえな記憶を探りながら探してみるとやっぱりそうであった。
ftp://ftp.jp.freebsd.org/pub/FreeBSD/releases/i386/6.3-RELEASE/base/install.sh
install.sh を覗くと、
cat base.?? | tar --unlink -xpzf - -C ${DESTDIR:-/}
と書いてあって、あーやっぱり、ということでそうする。
あとは devfs を /dev にマウントして設定ファイルをいくつか問題がでるごとに調整。resolv.conf とか。
そんで、chroot 内で chkbuild を動かして rubyspec まで試す。
そういえば、-v で出てくるアーキテクチャは x86_64 のままである。まぁ、uname の情報が元になってるからそういうものだといえばそういうものだが。
% ./ruby -v ruby 1.8.7 (2008-06-02 patchlevel 5000) [x86_64-freebsd6.3] % uname -a FreeBSD freebsd.tky.aist.go.jp 6.3-RC1 FreeBSD 6.3-RC1 #0: Mon Nov 26 21:52:21 UTC 2007 root@palmer.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC amd64 % ./ruby -e 'p 0x40000000.class' Bignum
Bloom Filter みたいなことを最小完全ハッシュを使ってやるとどうなるだろうか。
集合の要素が n 個であるとしよう。
最小完全ハッシュは 1要素あたり 3bit でできるので、3n bit である。そして、各要素毎にハッシュ値を j bit とっておけば、1/2**j な偽陽性の確率である値がその集合の要素であるかどうかを判定できる。ここで、j をひとつ増やせば、つまり全体で n bit 増やせば、偽陽性は半分になる。
Bloom Filter での偽陽性は、ビットベクタの長さが m としたときに、最適な個数のハッシュを使用して、だいたい 0.6185**(m/n) だそうである。とすると、ビットベクタを n bit 増やすと、偽陽性はほぼ 0.6185 倍になる。
使用するメモリが同じ量だとすると、(あるていど使用メモリを大きくすれば) 最小完全ハッシュを使ったほうが偽陽性が低くなりそうだ。
あるていど、とはどのくらいか。
1要素あたりで使用するビットを x とおくと、Bloom Filter の偽陽性は 0.6185**x である。
最小完全ハッシュとハッシュ値の組み合わせなら、0.5**(x-3) である。
プロットしてて比べてみると、だいたい、10bit, 0.9% あたりで交わる。
そうすると、1要素あたり 10bit 以上使うなら、同じメモリ量でも、最小完全ハッシュのほうが偽陽性が低くなる。
あるいは、偽陽性を 0.9% よりも小さく設定するなら、同じ偽陽性でも、最小完全ハッシュのほうが小さいメモリ量で済む。
GNU/Linux で、linux32 というコマンドを使うと、特定のプロセスの子孫で uname -m の結果を変えられるようだ。
これにより、amd64 な環境内に i386 な chroot 環境を作ったとき、chroot するときに linux32 を経由しておけば、その中で作った ruby は ruby -v で i686-linux が出るようになる。
linux32 の動作は、というと、LD_PRELOAD とかでごまかしてるかと推測したらそんなことはなくて、これに関してはカーネルに機能があるようだ。
How to Design a Good API and Why it Matters, Joshua Bloch.
を眺めてみる。
Ruby 1.9 の test/unit で、ひとつのテストが2回起動されるということがあった。
原因は ObjectSpace.each_object があるオブジェクトを 2回 yield することがあったからであった。test/unit では Test::Unit::TestCase のサブクラスを ObjectSpace.each_object でかき集めるので、2回 yield されてしまうとテストが 2回行われてしまう。
修正としては
というもののどちらかをやればいい。
とりあえず前者をやってみて、ついでに後者もやってみる。
さて、ObjectSpace.each_object の問題は、ObjectSpace.each_object で heaps という配列を走査しているときに、heaps の途中に要素が挿入されてしまうのが原因であった。
heaps はおおざっぱにいえば、オブジェクトを格納するヒープ領域の情報 (位置とかサイズとか) の配列である。オブジェクトを生成する場合、ヒープのひとつにひとつの空きが必要であり、空きがなければ、GC をするか、あるいはヒープ自体をもうひとつ作って heaps に追加して空きを作る。ここで、heaps はアドレスに関する 2分探索を行うので、追加時にはヒープがアドレス順に並ぶように heaps に挿入する。
ここで、挿入される場所はヒープのアドレス次第であるから、どこに挿入されるかは分からない。ObjectSpace.each_object が走査している最中に、走査済みのところに挿入されると、それ以降がひとつずれて、次の要素にすすんだらそれは元の要素であった、という話になる。その結果として、同じオブジェクトが 2回 yield される。
ところで、Ruby 1.8 でこの問題は起きるか?
しばらく考えたが、1.8 で同様の問題を起こすのは簡単でないようだ。
まず、1.8 ではヒープは指数関数的に、1.8 倍ずつ大きくしていく。(それに対し 1.9 では定数サイズである) そのため、heaps はそれほど大きくならず、heaps に対し 2分探索も行わない。アドレスによるソートも行われず、ヒープの追加では heaps の終端に追加される。
というわけで、ObjectSpace.each_object が走査しているときに追加が起こっても、既存の要素がずれることはないので、2回 yield されることはない。
既存の要素がずれる可能性があるのは、要素の削除のときである。GC によってあるヒープのオブジェクトが全て回収された場合、Ruby はそのヒープを free で解放する。そのとき、heaps はその要素がなくなって詰めるので、それ以降の要素がずれる。
そういうずれが ObjectSpace.each_object の走査中におこると危ないかもしれない。もし問題が起こるとすれば、ずれる方向が逆なので、ひとつのオブジェクトが 2回 yield されるのではなく、生きているオブジェクトが yield されないという症状になるだろう。test/unit でいえば、テストが起動されないということになる。
しかし、試してみるとどうも起きない。
まず、Hash#to_a を使って、いくつかのヒープを配列で埋めつくす。
n = 0x10000
n.times {|i| h[i] = i }
h.to_a
(最初は (0x40000000..0x40010000).to_a として Bignum で埋めつくそうと思ったが、Enumerable#to_a が使われて、目的の bignum の他に、ブロック呼出しでひとつ、Bignum#succ でひとつ、テンポラリオブジェクトが確保されるため、2/3 は想定外のオブジェクトで埋まる。なお、Bignum#succ で bignum の 1 を毎回生成するのはどうにかしてもいいかもしれない)
そして、適当なタイミングで GC を起こす。
ObjectSpace.each_object(Array) {|o|
GC.start if ...
}
しかし、起きない。調べてみると、そもそも、あまりヒープの解放が起こらないようだ。n を増やしたり減らしたりいろいろ変えて試しても、heaps のうち、最後のひとつかふたつしか解放されない。
調べてみると、あるヒープが解放される条件は、そのヒープのオブジェクトが全て回収されたことにだけでなく、全てのヒープに対し 2割の空きがすでに確認されていた場合、という条件があって、その条件に引っかかっているのであった。
この条件が必要なのは GC でオブジェクトがひとつだけ回収されるような状況を考えれば分かる。もしオブジェクトを生成しようとして空きがなくて GC を起こしたとき、オブジェクトがひとつだけ回収されたとしたら、新しいオブジェクトをひとつ生成することはできるが、次に新しいオブジェクトを生成しようとしたときにまた GC が起こる羽目になる。そうするとオブジェクトの生成毎に GC が動くという凶悪な状況になるので、これは避けないといけない。そのために、使用しているオブジェクト数に対して一定の割合のオブジェクトの空きが必要で、その空きを確保するまではヒープを解放しないのである。(ヒープを解放しなくてもその空きができなければ、ヒープを追加して空きを作る。)
この条件により、heaps を先頭から数えていって、2割の空きが確認されるまではヒープの解放は起こらない。
ところで、先ほども述べたようにヒープは指数関数的に大きくなる。初期値は 10000 なので、最初のヒープには 10000個のオブジェクトが入る。次は 1.8倍の 18000 である。その次は 32400, 58320... という具合に増えていく。
そうすると、その総計の 2割というのはどうなるか。
10000 -> 2000 10000+18000 -> 5600 10000+18000+32400 -> 12080 10000+18000+32400+58320 -> 23744 10000+18000+32400+58320+104976 -> 44739 10000+18000+32400+58320+104976+188956 -> 82530 10000+18000+32400+58320+104976+188956+340120 -> 150554 10000+18000+32400+58320+104976+188956+340120+612216 -> 272997 10000+18000+32400+58320+104976+188956+340120+612216+1101988 -> 493395 10000+18000+32400+58320+104976+188956+340120+612216+1101988+1983578 -> 890110 ...
ここで、ヒープの先頭から数えていくので、その 2割までのヒープは解放されない。その部分を足してみよう。
10000 -> 2000 10000+18000 -> 5600 28000+32400 -> 12080 28000+32400+58320 -> 23744 60400+58320+104976 -> 44739 118720+104976+188956 -> 82530 223696+188956+340120 -> 150554 412652+340120+612216 -> 272997 752772+612216+1101988 -> 493395 1364988+1101988+1983578 -> 890110 2466976+1983578+3570440 -> 1604198 4450554+3570440+6426792 -> 2889557 8020994+6426792+11568225 -> 5203202 14447786+11568225+20822805 -> 9367763 26016011+20822805+37481049 -> 16863973 46838816+37481049+67465888 -> 30357150 84319865+67465888+121438598 -> 54644870 151785753+121438598+218589476 -> 98362765 273224351+218589476+393461056 -> 177054976 491813827+393461056+708229900 -> 318700956 ...
どうも、+ がふたつしか出てこない。最初の部分は解放されないので、解放される可能性があるのは残り 2つだけ、という話になる。
ちゃんと計算してみよう。
n 個ヒープができたときの総量は初項が10000 で公比が 1.8 の等比数列の和である。
10000+18000+...+10000*1.8**(n-1) = 10000*(1.8**n-1)/0.8 = 12500*(1.8**n-1)
この 2割が解放されないしきいとなる。
0.2 * 12500*(1.8**n-1) = 2500*(1.8**n-1)
このしきいとなるヒープが m 番めとするとそれは以下を解くことによって求められる。
12500*(1.8**m-1) = 2500*(1.8**n-1) 5*(1.8**m-1) = 1.8**n-1 1.8**m = (1.8**n-1)/5 + 1 log(1.8**m) = log((1.8**n-1)/5 + 1) m*log(1.8) = log((1.8**n-1)/5 + 1) m = log((1.8**n-1)/5 + 1) / log(1.8)
ここで、n-m が解放される可能性のあるヒープの数である。
n-m = n - log((1.8**n-1)/5 + 1) / log(1.8)
ここで、n を大きくしたときの極限を求める。
lim(n-m) = lim(n - log((1.8**n-1)/5 + 1) / log(1.8)) = lim(n - log((1.8**n)/5) / log(1.8)) = lim(n - (log(1.8**n)-log(5)) / log(1.8)) = lim(n - (n*log(1.8)-log(5)) / log(1.8)) = lim(n - n + log(5)/log(1.8)) = log(5)/log(1.8) = 2.73813274192281
というわけで、ちゃんと計算してもやっぱり 3つのヒープは解放されない。解放される可能性があるのは最後の 2つだけである。
そして、ObjectSpace.each_object で、yield 中のオブジェクトが入っているヒープはそのオブジェクトが残るので解放されないとしよう。(この仮定は怪しいが、そう保証するようにコードを直すのは難しくない) そうすると、ちょうど走査中のヒープは解放されない。
また、まだ走査していないヒープは開放されようが何が起きようが問題は起きない。
残りの可能性は走査済みのヒープが解放されるときである。ここで、解放される可能性があるヒープは最後の2つだけなので、走査済みのヒープが解放されるのは、最後のヒープの走査中に最後からひとつ手前のヒープが解放されるケースだけである。しかし、この場合、走査洩れは起きない。なんでかというと最後のヒープより後には走査しなければならないものは残っていないからである。
といわけで、問題は起きないように思う。
ただし、この結論はいくつかの仮定を使っている。
しかし、たとえば、ヒープを追加するときにメモリ確保に失敗すると、サイズを小さくしてやり直すので、等比数列からは外れる。また、ヒープの解放が起きた場合でも等比数列から外れるかもしれない。
また、ObjectSpace.each_object で yield 中にブロックが値を捨てたら、そのヒープが解放される可能性はあるかもしれない。まぁ、たとえそうなるとしてもこれは ObjectSpace.each_object 側で対処すれば済むことだが。
いずれかの仮定が成り立たない状況になれば、変なことが起こるかもしれない。
サマータイムであるが、昔 Ruby での扱いをいろいろ直したときに何が問題だったのか思い起こしてみる。
... るびまのインタビューで説明していたことに気がついた。
問題は
である。
考えてみると、どっちもサマータイムは関係ない。
サマータイムが問題になったのは、UTC から time_t に変換する関数が標準にないためで、私が手を入れる前の Ruby では mktime の (サマータイム込みの) 結果を補正してそれを実現 (しようとして失敗) していたからである。
手を入れた結果、timegm があればそれを使い、なければ gmtime を 2分探索するようになったが、もし閏秒を考えなければ、これは純粋に計算で求められる。
Ruby であればこのへんの苦労はしなくていい。また、C などでも、timegm が存在することを仮定すれば、苦労はしなくていいであろう。たとえ存在しないにしても、閏秒を考えなければ計算でやればいい。
導入された場合に問題になるのはもっと上のレイヤであろう。たとえば、1日後の時刻を求める操作とか。
実際に問題が多くでそうな操作にはどんなものがあるだろうか。そして、そういう操作を問題なく行えるような API をデザインするとしたら、どのようなものになるだろうか。
まぁ、ひとつの案は TimeSpan かな。でも、もっと実際の問題を集めたいところだ。
ふむ。サマータイムは今国会では見送りか。
うぅむ。cvs.m17n.org の cvs repository を提供している disk が壊れたようだ。
Jun 12 01:23:08 cvs kernel: sd 0:0:1:0: SCSI error: return code = 0x08000002 Jun 12 01:23:08 cvs kernel: sdb: Current: sense key: Hardware Error Jun 12 01:23:08 cvs kernel: Additional sense: No defect spare location available Jun 12 01:23:08 cvs kernel: Info fld=0x5fcc413 Jun 12 01:23:08 cvs kernel: end_request: I/O error, dev sdb, sector 100451347 Jun 12 01:23:09 cvs kernel: sd 0:0:1:0: SCSI error: return code = 0x08000002 Jun 12 01:23:09 cvs kernel: sdb: Current: sense key: Hardware Error Jun 12 01:23:09 cvs kernel: Additional sense: No defect spare location available Jun 12 01:23:09 cvs kernel: Info fld=0x5fc165a Jun 12 01:23:09 cvs kernel: end_request: I/O error, dev sdb, sector 100406874 Jun 12 01:23:11 cvs kernel: sd 0:0:1:0: SCSI error: return code = 0x08000002 Jun 12 01:23:11 cvs kernel: sdb: Current: sense key: Hardware Error Jun 12 01:23:11 cvs kernel: Additional sense: No defect spare location available Jun 12 01:23:11 cvs kernel: Info fld=0x5fd0432 Jun 12 01:23:11 cvs kernel: end_request: I/O error, dev sdb, sector 100467762 ...
とか出ていて、現在 read only mount 中。(disk が 2台ついていて web server (と、この日記) のところは問題ない)
バックアップは毎日とっていて、昨日のがあるからデータは問題ないが、disk を替えないとな。
それはそれとして、cvs や svn は read access でもテンポラリディレクトリを作るから、read only mount でもサービスできなくなるのだな。
disk を換装して、復活させた (はず)。
壊れたディスクは shred する。
が、shred は時間がかかる。
shred はデフォルトで 25回であるが、検索すると 3回とかにするというオプションの指定がよく出てくる。
この回数というのはどういう理由で決まっているのだろうか。
というわけで論文をちょっと眺めてみる。
Peter Gutmann, Secure Deletion of Data from Magnetic and Solid-State Memory
眺めてみたところ、ディスクの記録形式にはいろいろあって、そのそれぞれについて復元をやりにくくするパターンがある、ということのようだ。で、いろいろな想定に対応したパターンをひとつづつやっていく、という。
問題は回数というよりは記録形式に対応したパターンをやっているかどうかなのかもしれない。
RubyKaigi2008 で発表してきた。
あと、RejectKaigi でも発表した。
[latest]