2011年12月30日金曜日

VMware Fusion のホストオンリーネットワークはハブのように振る舞う(スイッチではないみたい)

VMware Fusionで複数のVMをホストオンリーネットワークに接続し、VMのひとつで tcpdump を動かしてみる。そうすると、ブロードキャスト以外のパケットまで見えることに気づく。まるでリピータハブに接続したときのように。


環境

  • MacOS 10.6.8
  • VMware Fusion 4.1.1

VMを3つ作って(OSは、tcpdump や ping が使えるなら何でもよい)、それらのNICをホストオンリーネットワークにつなぐ。


ホスト(MacOS)で認識されているNICのうち、"vmnet1"がVMwareのホストオンリーネットワーク用の仮想ネットワークアダプタ。以下のように、ネットワークアドレスは"192.168.105.0"になっている。


$ ifconfig vmnet1
vmnet1: flags=8863 mtu 1500
 ether 00:50:56:c0:00:01 
 inet 192.168.105.1 netmask 0xffffff00 broadcast 192.168.105.255

なので、VMを起動するとVMのNICには"192.168.105.128/24" や "192.168.105.129/24" などが設定される。


$ ip addr show eth0
2: eth0:  mtu 1500 qdisc pfifo_fast state UP qlen 1000
    link/ether 00:0c:29:0a:48:1b brd ff:ff:ff:ff:ff:ff
    inet 192.168.105.128/24 brd 192.168.105.255 scope global eth0

準備ができたら、まず 1つのVMで "tcpdump -i eth0" を実行し、残り2つの VM間で ping をしてみる。すると tcpdump の出力に ping による通信が出てくる。

次に、プロミスキャスモードOFFの'-p'オプションをつけて tcpdump を実行して、同様に ping を実行すると、今度は出てこない。プロミスキャスモードが効く、つまり switched network には接続されていないときの動作になっている。


物理的な環境だとスイッチ(ングハブ)を常に使うから、VMware Fusionの世界もスイッチだと思い込んでいたが、違うらしい。また、VMwareのエディション等によっても挙動が変わってくる模様。


2011年12月26日月曜日

OpenSSHサーバーの鍵生成

一般的なLinuxディストリビューションでは、OpenSSHサーバーがインストールされていて、起動すればすぐに使える状態になる(はず)。

しかし、いったいサーバーの鍵はいつどこで誰が準備したのだろうか? たぶんこんなこと気にする必要は無い。でも気になった。

CentOS-6.0 について言えば、sshdの起動スクリプトの中で自動的に3種類の鍵、つまり RSA1 と RSA(SSH2対応RSA),DSAの鍵が作られるのだった。

/etc/init.d/sshd から抜粋

(略)
KEYGEN=/usr/bin/ssh-keygen
SSHD=/usr/sbin/sshd
RSA1_KEY=/etc/ssh/ssh_host_key
RSA_KEY=/etc/ssh/ssh_host_rsa_key
DSA_KEY=/etc/ssh/ssh_host_dsa_key
(略)
        if test ! -f $RSA1_KEY && $KEYGEN -q -t rsa1 -f $RSA1_KEY -C '' -N '' >&/dev/null; then
(略)
        if test ! -f $RSA_KEY && $KEYGEN -q -t rsa -f $RSA_KEY -C '' -N '' >&/dev/null; then
(略)
        if test ! -f $DSA_KEY && $KEYGEN -q -t dsa -f $DSA_KEY -C '' -N '' >&/dev/null; then
(略)

'ssh-keygen'コマンドを素直に3回実行するという流れ。

OpenSSHのStrictHostKeyChecking=xxx

OpenSSH の'StrictHostKeyChecking'オプションの振る舞いを確認してみた。

環境

ローカルホスト(SSHクライアント)
MacOS 10.6.8, OpenSSH_5.2p1, OpenSSL 0.9.8r 8 Feb 2011
リモートホスト(SSHサーバ)
CentOS-6.0 OpenSSH_5.3p1, OpenSSL 1.0.0-fips 29 Mar 2010

ちなみに OpenSSH のバージョンを調べるオプションは '-V' だった。

やったこと

OpenSSHの'StrictHostKeyChecking'オプションの値を yes, ask, no と変えながら、リモートホスト(ここでは 192.168.111.103)にユーザー user01 でログインを試みる。ただし、毎回以下のコマンドを実行してローカルホストのknown_hostsファイルがリモートホストの情報を含まない状態にしておく。

$ ssh-keygen -R 192.168.111.103

結果

yes の場合
$ ssh -o StrictHostKeyChecking=yes -l user01 192.168.111.103
No RSA host key is known for 192.168.111.103 and you have requested strict checking.
Host key verification failed.
$
認証まで進まずに、sshコマンドが終了してしまう。
ask の場合
ssh -o StrictHostKeyChecking=ask -l user01 192.168.111.103
The authenticity of host '192.168.111.103 (192.168.111.103)' can't be established.
RSA key fingerprint is 26:f9:16:77:cf:92:95:58:95:d1:55:ce:d2:9e:34:84.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '192.168.111.103' (RSA) to the list of known hosts.
user01@192.168.111.103's password:
手続きを進めるかどうか確認待ちになる。そこで yes を入力すると、パスワード入力待ちになる。
no の場合
$ ssh -o StrictHostKeyChecking=no -l user01 192.168.111.103
Warning: Permanently added '192.168.111.103' (RSA) to the list of known hosts.
user01@192.168.111.103's password:
確認無しに、パスワード入力待ちになる。

2011年12月23日金曜日

Nmap テスト用ホスト scanme.nmap.org

nmapコマンドを使ってみたい人のために、テスト用のホスト(scanme.nmap.org)が公開されている。このホストに対しては、一日あたり10数回程度という制限の範囲内で、自由にスキャンを実行してよい。

# nmap -A -T4 scanme.nmap.org

これも man や Examples に書いてあった。

Nmap の性能に関するオプション

詳しい説明が man や Timing and Performance に書いてあった。

お手軽なのは -T4 というオプション。

2011年12月19日月曜日

Tshark の Capture Filter と Read Filter のマニュアル

Tshark のフィルタは、"CAPTURE FILTER" と "READ FILTER" の二段構えになっており、それぞれが異なる文法にしたがう。

以下は、各文法を詳しく知りたいときに何を参照すればいいか、という話。


man tshark

とりあえず man tshark をする(CentOS-6.0 にて)。

CAPTURE FILTER SYNTAX
See the manual page of pcap-filter(4) or, if that doesn't exits, tcpdump(8).
READ FILTER SYNTAX
For a complte table or protocol and protocol fields that are filterable in TShark see the wireshark-filter(4) manual page.

…ということで、"pcap-filter(4)" と "wireshark-filter(4)" を参照すればいい。ちなみに CentOS-6.0 の場合 "pcap-filter(4)" は存在しなかった。代わりに "pcap-filter(7)"がみつかった。


例:SYNフラグがセットされているTCPパケットを抽出するフィルタ

キャプチャフィルタ('-f'オプション)の場合
# tshark -i eth0 -f 'tcp[tcpflags] & tcp-syn != 0'
リードフィルタ('-R'オプション)の場合
# tshark -i eth0 -R 'tcp.flags.syn == 1'

キャプチャフィルタのほうは、配列やビット演算風のローレベルな記述になっている。そして、Tshark 以外に tcpdump にも流用できる。


2011年12月18日日曜日

キャプチャデータを一定時間ごとにファイルへ保存(tshark, tcpdump)

キャプチャデータを、指定した時間間隔ごとに複数のファイルに出力するオプションを試してみた。

環境は、CentOS-6.0, libpcap-1.0.0, tshark-1.2.15, tcpdump-4.1-PRE-CVS。


tshark の場合

'-b <capture ring buffer option>' というオプションの値として 'duration:秒数' を指定する。

# tshark -i eth0 -b duration:3 -w tshark.pcap

上のコマンドを実行した場合、次のようにファイルが生成されていく。

# ls tshark*
tshark_00001_20111218215216.pcap
tshark_00001_20111218215219.pcap
tshark_00001_20111218215222.pcap

tcpdump の場合

'-G rotate_seconds' というオプションを使用する。それと同時に、

  • ファイル名('-w'オプション)に 'strftime' の書式文字列を含める必要がある
  • '-Z'オプションに 'root' を指定する必要がある(場合によってはセキュリティの問題につながるかもしれないので、一般ユーザーで sudo して '-Z user01' のようにしたほうがいいと思われる)
# tcpdump -i eth0 -G 3 -Z root -w tcpdump_%Y%m%d%H%M%S.pcap

上のコマンドを実行した場合、次のようにファイルが生成されていく。

# ls tcpdump*
tcpdump_20111218220740.pcap
tcpdump_20111218220743.pcap
tcpdump_20111218220746.pcap

sudoの設定をして、一般ユーザーで実行することもできる(たとえば user01 とする)。

$ sudo tcpdump -i eth0 -G 3 -Z user01 -w tcpdump_%Y%m%d%H%M%S.pcap
$ ls -l tcpdump*
-rw-r--r-- 1 user01 user01 480 Dec 18 23:01 tcpdump_20111218230115.pcap
-rw-r--r-- 1 user01 user01 480 Dec 18 23:01 tcpdump_20111218230118.pcap
-rw-r--r-- 1 user01 user01 480 Dec 18 23:01 tcpdump_20111218230121.pcap

2011年11月23日水曜日

Linux Control Group

リソースの割り当てを柔軟に管理するための、Linuxカーネルの機能のこと(プロセスをグループ化したものに対してもリソースを割り当てることができる)。省略して cgroup と呼ばれる。

RedHatのマニュアル:リソース管理ガイド に細かく書いてあるので、手元にある CentOS-6.0 でざっと試してみた。

1. インストール
CentOSならあらかじめインストールされているらしい。無ければ yum install libcgroup を実行。そうすると/etc/cgconfig.conf, /etc/init.d/cgconfig などができる。
2. /etc/cgconfig.conf を編集
とりあえずメモリの使用量を制限するため、/etc/cgconfig.conf に数行追加。
group test {
  memory {
    memory.limit_in_bytes = 50K;
  }
}
これでハードリミット50KBの制限を与えたことになる。ソフトリミット "memory.soft_limit_n_bytes" もあるらしい。
3. cgconfigサービスを起動
# service cgconfig start
起動すると /cgroup/memory/test というディレクトリが生成される。その中にある疑似ファイルを利用して cgroup を制御したり、情報を読み取ったりすることができる。たとえば memory.limits_in_bytesを開いてみると、上記の cgconfig.conf に記載した50KBの制限がバイト単位で指定されているのがわかる(設定ファイルで指定した値と正確には一致しない)。
# cat /cgroup/memory/test/memory.limits_in_bytes
53248
4. /etc/cgrules.conf を編集

メモリの使用量を制限したいユーザー、プロセス名(またはコマンドパス)等を指定する。ここではとりあえず /rootディレクトリに置いてある a.out と b.out というコマンドを対象にすることにして、次の2行を追加。

root:/root/a.out memory test/
root:/root/b.out memory test/
5. cgredサービスを起動
# service cgred start
6. テスト
これで準備ができたので、とりあえず "hello, world"を出力して無限ループするプログラム(hello_and_stop.c)を書く。
/* hello_and_stop.c */
#include <stdio.h>
int main(void){
    printf("hello, world\n");
    while(1){}
    return 0;
}
コンパイルしたあと、cgroup の制限を超えるまで地道に a.out と b.out をバックグラウンド実行する。
# gcc hello_and_stop.c
# cp a.out b.out
# ./a.out &
[1] 5690
hello, world
# ./b.out &
[2] 5691
hello, world
# ./a.out &
[3] 5692
hello, world
# ./b.out &
[4] 5693
Memory cgroup out of memory: kill process 5690 (a.out) score 59 or a child
Killed process 5690 (a.out) vsz:3832kB, anon-rss:16kB, file-rss:300kB
hello, world
[1] Killed             ./a.out
#

4回目の実行で制限を超えて、一番最初に実行したプロセス(PID=5690)が kill された。b.out を実行したにもかかわらず a.out が kill されたので、グループ化してリソース管理が行われているに違いない。

7. ログを確認
制限を超えたときのログは、とりあえず/var/log/messagesに記録されていた。意外と親切でたくさんの情報が残っている。
Nov 23 20:05:58 localhost kernel: b.out invoked oom-killer: gfp_mask=0xd0, order=0, oom_adj=0
Nov 23 20:05:58 localhost kernel: b.out cpuset=/ mems_allowed=0
Nov 23 20:05:58 localhost kernel: Pid: 5693, comm: b.out Not tainted 2.6.32-71.29.1.el6.x86_64 #1
Nov 23 20:05:58 localhost kernel: Call Trace:
Nov 23 20:05:58 localhost kernel: [] ? cpuset_print_task_mems_allowed+0x91/0xb0
Nov 23 20:05:58 localhost kernel: [] oom_kill_process+0xcb/0x2e0
Nov 23 20:05:58 localhost kernel: [] ? select_bad_process+0xd0/0x110
Nov 23 20:05:58 localhost kernel: [] mem_cgroup_out_of_memory+0x73/0x90
Nov 23 20:05:58 localhost kernel: [] mem_cgroup_handle_oom+0x147/0x170
Nov 23 20:05:58 localhost kernel: [] ? autoremove_wake_function+0x0/0x40
Nov 23 20:05:58 localhost kernel: [] __mem_cgroup_try_charge+0x20d/0x240
Nov 23 20:05:58 localhost kernel: [] mem_cgroup_charge_common+0x7b/0xc0
Nov 23 20:05:58 localhost kernel: [] mem_cgroup_newpage_charge+0x48/0x50
Nov 23 20:05:58 localhost kernel: [] handle_pte_fault+0x7a0/0xad0
Nov 23 20:05:58 localhost kernel: [] ? tty_ioctl+0xf7/0x950
Nov 23 20:05:58 localhost kernel: [] handle_mm_fault+0x1ed/0x2b0
Nov 23 20:05:58 localhost kernel: [] do_page_fault+0x123/0x3a0
Nov 23 20:05:58 localhost kernel: [] page_fault+0x25/0x30
Nov 23 20:05:58 localhost kernel: Task in /test killed as a result of limit of /test
Nov 23 20:05:58 localhost kernel: memory: usage 52kB, limit 52kB, failcnt 48
Nov 23 20:05:58 localhost kernel: memory+swap: usage 264kB, limit 9007199254740991kB, failcnt 0
Nov 23 20:05:58 localhost kernel: Mem-Info:
Nov 23 20:05:58 localhost kernel: Node 0 DMA per-cpu:
Nov 23 20:05:58 localhost kernel: CPU    0: hi:    0, btch:   1 usd:   0
Nov 23 20:05:58 localhost kernel: CPU    1: hi:    0, btch:   1 usd:   0
Nov 23 20:05:58 localhost kernel: Node 0 DMA32 per-cpu:
Nov 23 20:05:58 localhost kernel: CPU    0: hi:  186, btch:  31 usd:  75
Nov 23 20:05:58 localhost kernel: CPU    1: hi:  186, btch:  31 usd: 127
Nov 23 20:05:58 localhost kernel: active_anon:88921 inactive_anon:97754 isolated_anon:0
Nov 23 20:05:58 localhost kernel: active_file:11086 inactive_file:12590 isolated_file:0
Nov 23 20:05:58 localhost kernel: unevictable:0 dirty:0 writeback:0 unstable:0
Nov 23 20:05:58 localhost kernel: free:21668 slab_reclaimable:5484 slab_unreclaimable:10278
Nov 23 20:05:58 localhost kernel: mapped:2668 shmem:0 pagetables:1732 bounce:0
Nov 23 20:05:58 localhost kernel: Node 0 DMA free:4776kB min:664kB low:828kB high:996kB active_anon:3944kB inactive_anon:6172kB active_file:132kB inactive_file:596kB unevictable:0kB isolated(anon):0kB isolated(file):0kB present:15308kB mlocked:0kB dirty:0kB writeback:0kB mapped:36kB shmem:0kB slab_reclaimable:16kB slab_unreclaimable:0kB kernel_stack:0kB pagetables:64kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
Nov 23 20:05:58 localhost kernel: lowmem_reserve[]: 0 994 994 994
Nov 23 20:05:58 localhost kernel: Node 0 DMA32 free:81896kB min:44388kB low:55484kB high:66580kB active_anon:351740kB inactive_anon:384844kB active_file:44212kB inactive_file:49764kB unevictable:0kB isolated(anon):0kB isolated(file):0kB present:1017952kB mlocked:0kB dirty:0kB writeback:0kB mapped:10636kB shmem:0kB slab_reclaimable:21920kB slab_unreclaimable:41112kB kernel_stack:1576kB pagetables:6864kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
Nov 23 20:05:58 localhost kernel: lowmem_reserve[]: 0 0 0 0
Nov 23 20:05:58 localhost kernel: Node 0 DMA: 24*4kB 13*8kB 6*16kB 4*32kB 2*64kB 3*128kB 1*256kB 1*512kB 1*1024kB 1*2048kB 0*4096kB = 4776kB
Nov 23 20:05:58 localhost kernel: Node 0 DMA32: 210*4kB 419*8kB 474*16kB 365*32kB 163*64kB 41*128kB 23*256kB 24*512kB 6*1024kB 1*2048kB 4*4096kB = 81888kB
Nov 23 20:05:58 localhost kernel: 25202 total pagecache pages
Nov 23 20:05:58 localhost kernel: 1523 pages in swap cache
Nov 23 20:05:58 localhost kernel: Swap cache stats: add 238961, delete 237438, find 53952/75027
Nov 23 20:05:58 localhost kernel: Free swap  = 1904848kB
Nov 23 20:05:58 localhost kernel: Total swap = 2064376kB
Nov 23 20:05:58 localhost kernel: 262128 pages RAM
Nov 23 20:05:58 localhost kernel: 7828 pages reserved
Nov 23 20:05:58 localhost kernel: 19543 pages shared
Nov 23 20:05:58 localhost kernel: 211774 pages non-shared
Nov 23 20:05:58 localhost kernel: Memory cgroup out of memory: kill process 5690 (a.out) score 59 or a child
Nov 23 20:05:58 localhost kernel: Killed process 5690 (a.out) vsz:3832kB, anon-rss:16kB, file-rss:300kB

ちなみに /etc/cgconfig.conf, /etc/cgrules.conf を変更したときには、それぞれ # service cgconfig restart, # service cgred restart を行うと変更が反映される。

2011年11月22日火曜日

GCC最適化オプション(-O0, -O1, -O2, -O3, -funroll-loops)

「An Introduction to GCC」に載っていた例を実際に試してみた。

環境は CentOS-6.0 で、

  • 2.6.32-71.29.1.el6.x86_64 GNU/Linux
  • gcc (GCC) 4.4.4 20100726 (Red Hat 4.4.4-13)

やったこと

本に載っていた"test.c"をそのまま使い、-O0, -O1, -O2, -O3, -O3 -funroll-loops の5種類について実行ファイルのサイズとtimeコマンドの結果を求めた。

コンパイルと実行に使ったPerlスクリプトは以下のとおり。

#!/usr/bin/perl
#
# test.pl
#
@a = ('-Wall -O0', '-Wall -O1', '-Wall -O2', '-Wall -O3', '-Wall -O3 -funroll-loops');
for($i=0; $i <= $#a; $i++){
  print("\[$a[$i]\]\n");
  system("gcc $a[$i] test.c && size -B ./a.out && time ./a.out");
  print("\n\n");
}

ここで、実行ファイルのサイズを求めるにあたっては、ls -lではなくGNU Binutilssizeコマンドを使うようにした。sizeコマンドはELFファイルの中のセクションごとにサイズを調べてくれるので、.textセクションのサイズも分かる。すなわち最適化による命令の量の変化がより明らかになる。

結果

# ./test.pl > test.log 2>&1
# cat test.log
[-Wall -O0]
   text    data     bss     dec     hex filename
   1387     492      16    1895     767 ./a.out
sum = 4e+38

real 0m1.677s
user 0m1.263s
sys 0m0.002s


[-Wall -O1]
   text    data     bss     dec     hex filename
   1329     492      16    1837     72d ./a.out
sum = 4e+38

real 0m0.793s
user 0m0.735s
sys 0m0.003s


[-Wall -O2]
   text    data     bss     dec     hex filename
   1369     492      16    1877     755 ./a.out
sum = 4e+38

real 0m0.457s
user 0m0.442s
sys 0m0.005s


[-Wall -O3]
   text    data     bss     dec     hex filename
   1369     492      16    1877     755 ./a.out
sum = 4e+38

real 0m0.456s
user 0m0.444s
sys 0m0.003s


[-Wall -O3 -funroll-loops]
   text    data     bss     dec     hex filename
   1665     492      16    2173     87d ./a.out
sum = 4e+38

real 0m0.503s
user 0m0.493s
sys 0m0.002s

性能がよいのは-O2-O3で、たぶん同じコード。funroll-loopsの最適化は今回の例では逆効果だった。

サイズを最も小さくできたのは-O1

補足:-Osオプション

-Osオプションを使うとサイズの最適化を行うことができる。これも試した結果、確かにサイズが最も小さくなった。

[-Wall -Os]
   text    data     bss     dec     hex filename
   1289     492      16    1797     705 ./a.out
sum = 4e+38

real 0m0.575s
user 0m0.544s
sys 0m0.003s

-Wall -O1の場合と比較すると、.textセクションのサイズは40バイト減り、実行時間も0.2sくらい減っている。

2011年11月20日日曜日

食物連鎖(Union-FInd木を用いる問題)

プログラミングコンテストチャレンジブックに載っていた、「食物連鎖」という問題(POJ 1182)。Union-Find木を応用して解けるらしいが、文字の説明だけではすんなり理解できなかったので概念を図にした。すっきりした。

2011年11月14日月曜日

GCC でコンパイルの中間ファイルを残す

-save-temps というオプションを使う。

例: プリプロセッサの出力を調べる

マクロ "NUM" を含むソース dtestval.c
#include <stdio.h>
int main(int argc, char *argv[])
{
  printf("Value of NUM is %d\n", NUM);
  return 0;
}
-save-tempsオプションとマクロ定義を与えてコンパイルしてみる
$ gcc -save-temps -DNUM="1 + 1" dtestval.c -o dtestval
$ ls -1 dtestval*
dtestval
dtestval.c
dtestval.i
dtestval.o
dtestval.s
プリプロセスの出力ファイル dtestval.i
# 1 "dtestval.c"
# 1 ""
(省略)
# 938 "/usr/include/stdio.h" 3 4

# 2 "dtestval.c" 2

int main(int argc, char *argv[])
{
  printf("Value of NUM is %d\n", 1 + 1);
  return 0;
}
"NUM" の定義が反映されて 1 + 1 になっているのが分かる。

2011年11月13日日曜日

GDB で core を作りつつプロセスを止める

生きているプロセスのプロセスIDを調べて、GDB をそのIDに attach してから kill(GDBの kill コマンド)すると core が出てくれる(もちろんプロセスの executable file はGCCの"-g"オプション付きでコンパイルされている必要がある)。

別の言葉で言うと、シェルから kill -QUIT pid する以外にも方法がある、ということ。

2011年9月13日火曜日

mii-tool と ethtool

Linuxでネットワークインターフェースの状況を確認するときに使えるコマンド。

mii-tool

$ man mii-tool
NAME
        mii-tool - view, manipulate media-independent interface status
(略)

指定したインターフェース(et0, eth1 など)の状況を表示する。-wオプションを使うとlink status の変化を検出してくれる。たとえば、VMWareなどのゲストOS上で実験すると面白い。

仮想スイッチに接続したゲストOSで mii-tool -w を実行してみる

VMWare Fusion on Mac OS 10.6.8 にインストールしたゲストOS(CentOS-6.0)で eth1に対して mii-tool -wを実行。

仮想ネットワークの設定を開く。

「接続」のチェックボックスをオフにする。これで、仮想的にネットワークケーブルを抜いた状態になる。

すると、mii-tool の出力が変化してno linkになる。

「接続」のチェックボックスをオンに戻すと、もとに戻る。

このように mii-tool は楽しいのだが、obsoleteであるからなるべく使わないほうがよいらしい(その代わりにethtoolを使う)。

ethtool

$ man ethtool
NAME
        ethtool - Display or change ethernet card settings
(略)

ethtool は mii-tool に比べると多機能でオプションが多いので、とりあえずNICの状態を調べる。

# ethtool eth1
Settings for eth1:
 Supported ports: [ TP ]
 Supported link modes:   10baseT/Half 10baseT/Full 
                         100baseT/Half 100baseT/Full 
                         1000baseT/Full 
 Supports auto-negotiation: Yes
 Advertised link modes:  10baseT/Half 10baseT/Full 
                         100baseT/Half 100baseT/Full 
                         1000baseT/Full 
 Advertised pause frame use: No
 Advertised auto-negotiation: Yes
 Speed: 1000Mb/s
 Duplex: Full
 Port: Twisted Pair
 PHYAD: 0
 Transceiver: internal
 Auto-negotiation: on
 MDI-X: Unknown
 Supports Wake-on: d
 Wake-on: d
 Current message level: 0x00000007 (7)
 Link detected: yes

上述の mii-tool -w のようにケーブルの状態をチェックするなら、たとえば watchと組み合わせて

# watch -n 1 "ethtool eth1|grep 'Link detected'"

とすれば間に合う(下の画像のように表示される)。

2011年9月8日木曜日

yum groupinstall ほか

yumのパッケージを複数まとめたもの、つまり「パッケージグループ」をインストールするためのコマンドが yum groupinstall

メール、DNS、WWW等のサーバー用Linuxに、後になってデスクトップ環境を入れようとすると大量のパッケージを追加インストールしなければならないのだが、そういった場合に役にたつ。

そして、パッケージグループ関連のコマンドは、groupinstallのほかにも

  • grouplist
  • groupinfo
  • groupupdate
  • groupremove

…等がある。

yum grouplist の例

# yum grouplist
Loaded plugins: fastestmirror
Setting up Group Process
Loading mirror speeds from cached hostfile
 * base: mirror.khlug.org
 * extras: data.nicehosting.co.kr
 * updates: data.nicehosting.co.kr
Installed Groups:
   Additional Development
   Arabic Support
(略)
   Web Server
Available Groups:
   Afrikaans Support
   Albanian Support
(略)
   iSCSI Storage Client
Done

yum groupinfo の例

# yum groupinfo Desktop
Loaded plugins: fastestmirror
Setting up Group Process
Loading mirror speeds from cached hostfile
 * base: mirror.khlug.org
 * extras: data.nicehosting.co.kr
 * updates: data.nicehosting.co.kr

Group: Desktop
 Description: A minimal desktop that can also be used as a thin client.
 Mandatory Packages:
   NetworkManager
   NetworkManager-gnome
   alsa-plugins-pulseaudio
(略)
 Default Packages:
   eog
   gdm-plugin-fingerprint
(略)
 Optional Packages:
   control-center-extra
   sabayon-apply
   tigervnc-server
   xguest

2011年9月3日土曜日

Linux の /proc/crypto

/proc/crypto を見ると、Linuxカーネルがどのような暗号化アルゴリズム(cryptographic cipher)を使用しているかがわかる、という話


/proc/crypto の例

CentOS-6.0 で /proc/crypto を見てみた。

# cat /proc/crypto
name         : xts(aes)
driver       : xts(aes-asm)
module       : kernel
priority     : 200
refcnt       : 1
selftest     : passed
type         : givcipher
async        : no
blocksize    : 16
min keysize  : 32
max keysize  : 64
ivsize       : 16
geniv        : eseqiv
(略)

name だけ grep してみた。

# grep '^name' /proc/crypto
name         : xts(aes)
name         : xts(aes)
name         : sha256
name         : sha224
name         : cbc(aes)
name         : cbc(aes)
name         : aes
name         : aes
name         : stdrng
name         : crc32c
name         : sha1
name         : md5

暗号化モジュールをロードしてみる

カーネルが使用できる暗号を追加したい場合は、該当するモジュールをロードしてやればいい(modprobe 等のコマンドを使う)。

例:blowfish暗号を追加

# modprobe blowfish

lsmod, modinfoで、ロードされたモジュールを確認。

# lsmod |grep blowfish
blowfish                7850  0 

# modinfo blowfish
filename:       /lib/modules/2.6.32-71.29.1.el6.x86_64/kernel/crypto/blowfish.ko
description:    Blowfish Cipher Algorithm
license:        GPL
srcversion:     3D0BFB5C93D66CBA1C92FA2
depends:        
vermagic:       2.6.32-71.29.1.el6.x86_64 SMP mod_unload modversions 

/proc/crypto も確認。

cat /proc/crypto
name         : blowfish
driver       : blowfish-generic
module       : blowfish
priority     : 0
refcnt       : 1
selftest     : passed
type         : cipher
blocksize    : 8
min keysize  : 4
max keysize  : 56
(略)

dm-crypt での例

dm-crypt は、ディスク暗号化のための仕組み(a device-mapper crypto target)。dm-crypt を使用すると、/proc/crypto の内容が変化する。つまり、 dm-crypt が Linuxカーネルの暗号化モジュールを利用している、ということが分かる。

テキトーにdm-cryptを使って暗号化してみる

/dev/sdc1 を blowfish の CTRモード で暗号化して mapping01 にマップ。

# cryptsetup create -y -c blowfish-ctr-plain mapping01 /dev/sdc1

/proc/crypto を見てみる。

# cat /proc/crypto
name         : ctr(blowfish)
driver       : ctr(blowfish-generic)
module       : kernel
priority     : 0
refcnt       : 2
selftest     : passed
type         : givcipher
async        : yes
blocksize    : 1
min keysize  : 4
max keysize  : 56
ivsize       : 8
geniv        : chainiv

name         : ctr(blowfish)
driver       : ctr(blowfish-generic)
module       : ctr
priority     : 0
refcnt       : 2
selftest     : passed
type         : blkcipher
blocksize    : 1
min keysize  : 4
max keysize  : 56
ivsize       : 8
geniv        : chainiv

name         : blowfish
driver       : blowfish-generic
module       : blowfish
priority     : 0
refcnt       : 2
selftest     : passed
type         : cipher
blocksize    : 8
min keysize  : 4
max keysize  : 56
(略)

…というように、CTR とか blowfish のモジュールがロードされたのが分かる。

なお、 dm-crypt に関しては、なるべくデフォルトの暗号化アルゴリズムとモードを使ったほうがよいようだ。というのは、2011-06-28頃のメーリングリストでそのように主張されていたから(AES + CBCモード + ESSIV を使いましょう、とのこと)。


2011年9月1日木曜日

openssl の s_client -sess_out と sess_id

-sess_outsess_id が便利だったのでメモ。


openssl s_client コマンド

openssls_clientは、サーバーとのSSL通信を確認するためのコマンド。いろいろな場面で応用できる。


-sess_out オプション

-sess_out を使うと、openssl s_client の結果(SSLセッション情報)をファイルに記録することができる。

$ openssl s_client -connect smtp.gmail.com:587 -starttls smtp -sess_out sess_out.txt

上の例では、sess_out.txtに記録される(鍵の情報が含まれているので、扱いには要注意)。

$ cat sess_out.txt
-----BEGIN SSL SESSION PARAMETERS-----
MIIEdQIBAQICAwEEAgAFBCCiljn8yfXmDAlDzxlv53HgKo02ds87ncxERAAfYxf2
(略)
-----END SSL SESSION PARAMETERS-----

ただし、cat で表示してみると分かるように、PEMエンコードされているためそのままでは読めない。


openssl sess_id コマンド

SSLセッション情報を解読するためのコマンドとして、openssl sess_id が提供されている。

$ openssl sess_id -text -noout -in sess_out.txt
SSL-Session:
    Protocol  : TLSv1
    Cipher    : 0005
    Session-ID: A29639FCC9F5E60C0943CF196FE771E02A8D3676CF3B9DCC4444001F6317F68E
    Session-ID-ctx:
    Master-Key: 0FF83FC108F7A09BD6E9D76CD707804B6DFCCA3520EA13574B42EE40E21718D651432D79645AB91DAF2937D9373D1F97
    Key-Arg   : None
    Krb5 Principal: None
(略)
    Start Time: 1314886612
    Timeout   : 300 (sec)
    Verify return code: 0 (ok)

上の例のように、Protocol, Cipher, Session-ID, Master-Keyなど、SSLセッションを特徴づけるデータが分かる。

このコマンドのオプションは man sess_id で確認ができる。

2011年8月29日月曜日

Nessus on CentOS-6.0

Vulnerability Scanner(脆弱性検査ツール) の Nessus を使ってみた。

Nessus について

Nessus (software) - Wikipedia, the free encyclopedia」に概要が書いてある。

そのほかの特徴を、思いつくまま挙げた:

  • 商用利用の場合は有料ユーザー登録が必要(register to ProfessionalFeed
  • 商用でない場合も登録は必要(register to HomeFeed
  • バージョン 4.4 からWebインターフェースが提供されたため、クライアントソフト(NessusClient)のインストールが不要になった
  • コマンドラインインターフェース(CLI)もある
  • デフォルト「ポリシー」が4種類提供されている。これらをコピーして自分のポリシーを作成し、スキャンを実行する
  • 「プラグイン」を定期的に更新する必要がある(Nessus 4.4 Installation Guide によると普通は1日1回、場合によっては4時間に1回とのこと)

rpm をダウンロード

利用許諾のページ「Nessus Download Agreement | Tenable Network Security」から進んで、プラットフォームに合ったファイルをダウンロードする。今回の場合はRed Hat ES 6 (64 bits) / CentOS 6: Nessus-4.4.1-es6.x86_64.rpm をダウンロード。

インストールと設定

rpmでインストール。

# rpm -Uvh Nessus-4.4.1-es6.x86_64.rpm

あとは、Documentation のなかの Nessus 4.4 Installation Guide を読んで作業する(PDFファイル)。英語だが目次がきちんと整理されているので分かりやすい。

ポリシー作成とスキャンの実行

これも Documentation の Nessus 4.4 User Guide を読んで作業すれば難しくない。

以下は画面のキャプチャを適当に貼っていく。

ポリシーの編集画面

スキャン結果(Reports)

Severity が high のものが1個あった。

スキャン結果の詳細

Severity が high のものを掘り下げてみた。

スキャン結果の詳細

さらに掘り下げてみたところ、脆弱性に関する詳しい説明が表示された。

CVE-2011-3192と書いてあり、2011年8月19日に発見されたApacheの脆弱性のことだと分かる(脆弱性と対策は以下のリンク先に書いてある)。

対策を行ってから再度スキャンしてやると、当然ながらこの脆弱性はレポートから消えた。

tar コマンドの xattrs オプション

star

少し前の Linux(RedHat)では、SELinux や ACL の情報をもったファイルをアーカイブするときに star というコマンドを使うことになっていた。

ただし、このコマンドは圧縮のオプションが充実していなくて不便だった。

たとえば、gzip圧縮する場合には

$ star -H=exustar -xattr -c dir1 | gzip > dir1.tgz

のようにパイプやリダイレクトを行う必要があった(tar -z のような圧縮オプションが無いため)。

tar -xattrs

しかし、最近は tar が改良されて -xattrsオプションを使えばよくなったらしい(これで -j, -J, -z などの圧縮も使える)。

tar -xattrs の例

CentOS-6.0(Linux 2.6.32-71.29.1.el6.x86_64)にて確認。

準備
~/dir, ~/dir/file1, ~/dir/file2 を作って、テキトーにACLと拡張ファイル属性を設定。
$ cd
$ mkdir dir1 && touch dir1/file{1,2}
$ setfacl -R -m m:rwx dir1
$ setfattr -n 'user.test' -v 'test' dir1
$ setfattr -n 'user.test' -v 'test' dir1/file{1,2}
tar -xattrs でアーカイブ
$ tar --xattrs -cvzf dir1.tgz dir1
/tmp に展開して属性を確認
$ tar -xvzf dir1.tgz -C /tmp
$ getfacl -R /tmp/dir1
getfacl: Removing leading '/' from absolute path names
# file: tmp/dir1
# owner: useruuser
# group: useruuser
user::rwx
group::rwx
mask::rwx
other::r-x

# file: tmp/dir1/file2
# owner: useruuser
# group: useruuser
user::rwx
group::rw-
mask::rwx
other::r--

# file: tmp/dir1/file1
# owner: useruuser
# group: useruuser
user::rwx
group::rw-
mask::rwx
other::r--/

$ getfattr -d /tmp/dir1 /tmp/dir1/file*
getfattr: Removing leading '/' from absolute path names
# file: tmp/dir1
user.test="test"

# file: tmp/dir1/file1
user.test="test"

# file: tmp/dir1/file2
user.test="test"

…というわけで、tar -xattrs で拡張属性が保存されていることがわかった。

2011年8月23日火曜日

CentOS-6.0: semanage SELinux Command Not Found

CentOS-6.0 で semanage(SELinux用のコマンドラインツール)を使おうと思ったら command not found だった。

これはよくある話のようで、「RHEL 6: semanage SELinux Command Not Found」に回答を発見(厳密には RHEL6 向けの回答だが)。

要するに、# yum provides で欲しいファイルを指定すると、必要なパッケージがわかる。知らなかったので、覚えておきたい。

2011年8月22日月曜日

フェイス(face)を変えて見やすくしよう

Emacsのテキスト表示に関する属性、すなわちフォント、前景色、背景色、下線などをまとめたものを「フェイス」と呼ぶ。フェイスの概念は、テキストをちょっとカスタマイズしたいときなどに役に立つ。

例:SLIMEの slime-repl-inputed-output-face

下の画像は、Emacs で SLIME の REPL を使っているところ。式の評価結果「1.4142135」が赤で表示されていて見えにくいため、「フェイスを変更して見やすくしよう」という気分になる。

見えにくい部分のフェイスを調べる

問題のテキストに指定されているフェイスを調べることから始める(環境は GNU Emacs 22.3.1)。

具体的には、カーソルを「1.4142135」の所に移動して M-x eval-expression を実行。次いでミニバッファに以下の式を入力する。

(get-char-property (point) 'face)

すると、同じくミニバッファに slime-repl-inputed-output-face という文字が表示されるはず。これが見えにくい部分のフェイスの名前なので、メモしておく。

※毎回 eval-expression するよりも、「Meadow/Emacs memo: 基本的な設定」に紹介されているように、フェイスを調べるコマンドをあらかじめ init.el や .emacs に定義しておくほうが便利。

色の見本を参照して使いたい色を決める: list-colors-display

コマンド M-x list-colors-display を実行すると、以下のように色の名前("snow"、"GhostWhite"など)が表示される。この中から、新しい文字に使いたい色の名前をピックアップしておく。

フェイスを変える: customize-face

Emacsにはフェイスを変更するためのコマンド customize-face が用意されているので、これを利用する。

M-x customize-faceを実行して、目的のフェイスであるslime-repl-inputed-output-face を入力。すると、次のようなバッファができる。

下のほうにある"Foreground: Red"の所までカーソルを移動して、新しい文字の色を入力。入力に応じて右側の "sample" の文字色が変わるので、試行錯誤することもできる。

色を入力したら、上のほうにある "Save for Future Sessions" にカーソルを合わせて Enterキー を押す。これで変更が永続化、つまり .emacs や init.el に設定が書き込まれる。

確認

customize-face による設定はすぐに反映されるので、REPLのバッファに戻れば文字色の変化を確認できる。

さらに、設定ファイルを開いてみると、末尾にカスタマイズのためのコードが追加されていることがわかる。

(custom-set-variables
  ;; custom-set-variables was added by Custom.
  ;; If you edit it by hand, you could mess it up, so be careful.
  ;; Your init file should contain only one such instance.
  ;; If there is more than one, they won't work right.
 )
(custom-set-faces
  ;; custom-set-faces was added by Custom.
  ;; If you edit it by hand, you could mess it up, so be careful.
  ;; Your init file should contain only one such instance.
  ;; If there is more than one, they won't work right.
 '(slime-repl-inputed-output-face ((((class color) (background dark)) (:foreground "IndianRed1")))))

勝手に追加されるのが気持ち悪い場合は、custom-set-faces の式を自分で作って書き込めばいい。ただし、背景の種類に応じて (background dark) の部分を調整する必要があるはず。

2011年8月20日土曜日

Tunnelblick の WARNING

Tunnelblick というのは、Mac用のOpenVPNクライアント。

今日まで気がつかなかったが、ログを見ると次のようなWARNINGが出ていた。

2011-08-20 00:13:31 WARNING: No server certificate verification method has been enabled.  See http://openvpn.net/howto.html#mitm for more info.

バージョンは *Tunnelblick: OS X 10.6.8; Tunnelblick 3.1.7 (build 2190.2413); OpenVPN 2.1.4

よくあること?

ほかの人のブログにも同じWARNINGが出てるケースが散見されるし、OpenVPNを使ううえで問題はないので、無視してよいのかもしれない。

…が、やはり気になったので調べた。

原因と解決策

実は Tunnelblick の設定ファイル( config.ovpn )が微妙に間違っていて、証明書や秘密鍵を参照できてなかった様子。念のため絶対パスで記述したらWARNINGが出なくなった。

修正前
ca ca.crt
cert client01.crt
key client01.key
修正後
ca /Users/foo/Library/openvpn/TunnelblickVPNConfigurationClient01.tblk/Contents/Resources/ca.crt
cert /Users/foo/Library/openvpn/TunnelblickVPNConfigurationClient01.tblk/Contents/Resources/client01.crt
key /Users/foo/Library/openvpn/TunnelblickVPNConfigurationClient01.tblk/Contents/Resources/client01.key

ここで、fooTunnelblickVPNConfigurationClient01 はそれぞれ Macユーザ名と Tunnelblickの設定名称なので環境に依存する。

2011年8月19日金曜日

Node.js をビルドするときの openssl-libpath

うちのMacで久しぶりにビルドしようとしたら、makeの途中でエラーが発生した(Mac OS 10.6.8 での話)。むかしは問題なかった気もするが…

解決策

makeのメッセージを確認したところ、SSL関係の共有ライブラリ(/opt/local/lib/libssl.dylib)がおかしい。そこで configure のオプションで別のパスを指定してみたら解決した。

$ git clone --depth 1 git://github.com/joyent/node.git
$ cd node
$ git checkout v0.4.11
$ ./configure --prefix=$HOME/local/node --openssl-libpath=/usr/lib/
$ make

ちなみに、オプションを表示するには configure --help と打てばOK.

$ ./configure --help
waf [command] [options]

Main commands (example: ./waf build -j4)
  abspath  : Return an absolute path.
  build    : builds the project
  clean    : removes the build files
  configure: configures the project
  dirname  : Returns the directory component of a pathname
  dist     : makes a tarball for redistributing the sources
  distcheck: checks if the sources compile (tarball from 'dist')
(略)

それと、ここで表示される "waf" って何のことだろと思ったら、Pythonでできたビルドツールらしい。Waf - Wikipedia, the free encyclopedia … 初耳でした。

2011年8月18日木曜日

JavaScriptコードの性能比較 - jsPerf

概要はこちら「JavaScriptコードのパフォーマンス比較ができるWebサービス「jsPerf」の使い方 | Web scratch」に。

とりあえず、キャピタライズ処理のためのコードを比較してみた > Upcase first character · jsPerf

※コードは「デザインとプログラムの狭間で: javascriptでキャピタライズ(一文字目を大文字にする)」のものを利用させていただいた。

使うのはとても簡単。コードだけでなく、いろいろな環境での結果を共有できるのも面白い。

あとはどういった場面で活用するか。たとえばFirebugのプロファイラでボトルネックを特定し終わって、具体的な改善方法を模索するときとか。

2011年8月16日火曜日

自然対数の底 e の計算 in Elisp

eを計算する方法はたくさんある。ここでは二つの方法を書いておく。

1. 級数

exの x=1 におけるテイラー展開を求めてやると、次のような級数表現が得られる。

e=\sum^{\inf}_{n=0}\frac{1}{n!}=1+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\cdots

この級数表現をプログラムにすると、次のようになる。

(defun e (n)
  "級数表現にもとづいてeを計算"
  (if (< n 0) 0.0
    (+ (/ 1.0 (fact n)) (e (- n 1)))))
=> e

(defun fact (n)
  "階乗を計算"
  (if (<= n 0) 1
    (* n (fact (- n 1)))))
=> fact

(e 5)
=> 2.7166666666666663

n=1 から n=20 までの実行結果。

(2.0
2.5
2.6666666666666665
2.708333333333333
2.7166666666666663
2.7180555555555554
2.7182539682539684
2.71827876984127
2.7182815255731922
2.7182818011463845
2.718281826198493
2.718281808918177
2.7182818042763013
2.7182818091495133
2.718281802164987
2.7182817951863503
2.718281799212947
2.7182818049171673
2.7182818140377822
2.7182818360880554)

プロットしてみた。

2. 一般連分数

具体的な式は、「ネイピア数の表現 - Wikipedia」の「II. 一般連分数による表現」に書いてある。これを漸化式の形で書くと、

\begin{eqnarray}\begin{array}{rcl}f_n&=&2+\frac{1}{f_{n-1}}\\f_{n-1}&=&1+\frac{1}{f_{n-2}}\\f_{n-2}&=&2+\frac{2}{f_{n-3}}\\&\vdots&\\f_0&=&n\end{array}\end{eqnarray}

1, 2, ... と増えていく部分を i で表すと、

\begin{eqnarray}f_{n-i}=\left\{\begin{array}{l}2+\frac{1}{f_{n-1}} \ \ \ \ (i=0)\\i+\frac{i}{f_{n-i-1}}\ \ \ \ (1\leq i\leq n-1)\\n \ \ \ \ (i=n)\end{array}\end{eqnarray}

さらに、 j = n - i つまり i = n - j と変換すると、

\begin{eqnarray}f_{j}=\left\{\begin{array}{l}2+\frac{1}{f_{j-1}} \ \ \ \ (j=n)\\n-j + \frac{n-j}{f_{j-1}} \ \ \ \ (1\leq j\leq n-1)\\n \ \ \ \ (j=0)\end{array}\end{eqnarray}

これをプログラムで表現すると、

(defun e (n)
  "一般連分数による表現にもとづいてeを計算"
  (labels ((f (j)
              (cond
               ((= n j) (+ 2 (/ 1.0 (f (1- j)))))
               ((zerop j) n)
               (t (+ (- n j) (/ (float (- n j)) (f (1- j))))))))
    (f n)))
=> e

(e 5)
=> 2.7184466019417477

※浮動小数点数で計算するために、一箇所だけfloat関数を使っている。

n=1 から n=20 までの実行結果。

(3.0
2.6666666666666665
2.7272727272727275
2.7169811320754715
2.7184466019417477
2.718263331760264
2.71828369389345
2.7182816576664037
2.7182818427778273
2.7182818273518743
2.718281828538486
2.718281828453728
2.7182818284593786
2.7182818284590256
2.7182818284590464
2.718281828459045
2.7182818284590455
2.7182818284590455
2.7182818284590455
2.7182818284590455)

1の方法で求めた図に重ねてプロットしてみた(赤い点)。

2011年8月11日木曜日

Scheme の set! の読み方

"set bang" つまり「セットバン」と発音する。「The Seasoned Schemer」「Scheme修行」の注に書いてあった。

「"!"を"bang"と読むのかー、へー」と思ったが、そういえばUnixスクリプトの "#!" も「シェバン」と読むからごく自然な発想だ。

2011年8月8日月曜日

スタンフォード大のオンラインクラス - Introduction to Artificial Intelligence

Paradigms of Artificial Intelligence Programming」を書いた Peter Norvig の講義を無料で受けられる、という企画を発見した。

ここ「Introduction to Artificial Intelligence - Fall 2011」に登録フォームや動画がある。

ざっと読んだところ、宿題やテストの回答を送れば採点してくれて、最後には評価メールのようなものをくれるらしい(You will receive a letter of completion from the instructors which will include information on how well you did. と書いてあった)。期間は10週間で、リアルの講義は今年の9月末、オンライン版は10月から開始予定。

ちなみに教科書は PAIP ではなく「Amazon.co.jp: Artificial Intelligence: A Modern Approach (3rd Edition) (Prentice Hall Series in Artificial Intelligence): Stuart Russell, Peter Norvig: 洋書」という本。申し訳ないが存在すら知らなかった。PAIP と内容が似ているのだろうか、Lisp を使うのだろうか…

さらにここ「Stanford University CS 221 Introduction to Artificial Intelligence」にも情報があった。前提条件として、線形代数と確率の知識が必要とのこと。

2011年8月7日日曜日

JavaでJSONのパース/シリアライズ - Gson

久しぶりにJavaの仕事。

JSONを処理するにあたってGsonというライブラリを使ったのでメモ。

Gson

そもそもGoogle社内で開発・利用していたものを、一般に公開したとのこと。

google-gson - A Java library to convert JSON to Java objects and vice-versa - Google Project Hosting から現在の最新版である google-gson-1.7.1-release.zip をダウンロードし、コンパイル&実行に必要な gson-1.7.1.jar を抽出しておく。

JSONのパース/シリアライズ

Gsonクラスをインスタンス化して、インスタンスメソッドである fromJson(), toJson() でそれぞれパース、シリアライズを行う。

JSONオブジェクトのキーがJavaの予約語と一致してしまう場合、つまり {"try":1, "class":2} のような場合、そのままではパースができないためアノテーション @SerializedName を使って対応する必要がある。

サンプルコード

Gsonを使ってパースとシリアライズを行う。パースするJSONは {"class":999} でキーにJavaの予約語"class"を含むため、@SerializedName を使ってJavaオブジェクトのフィールド_class と対応させる。

import com.google.gson.Gson;
import com.google.gson.annotations.SerializedName;

public class Test{

    // JSONに対応するクラス。フィールド1個だけ。
    private class Myobj {
        // _classフィールド
        // 対応するJSONのキーがJava予約語(class)なのでアノテーションを付ける
        @SerializedName ("class") private int _class;

        // toString()
        public String toString() {
            return "_class: " + this._class;
        }
    }

    // main
    public static void main (String[] args) {
        // JSON
        String json = "{\"class\":999}";

        // JSONをパース
        Gson gson = new Gson();
        Myobj myo = gson.fromJson(json, Myobj.class);
        System.out.println("fromJson: " + myo);

        // Javaオブジェクトをシリアライズ
        String s = gson.toJson(myo);
        System.out.println("toJson: " + s);
    }
}

コンパイル&実行結果。ちなみに環境は Mac OS X 10.6.8 (Darwin 10.8.0 x86_64)。

$ javac -classpath gson-1.7.1.jar Test.java
$ java -classpath ./:gson-1.7.1.jar Test
fromJson: _class: 999
toJson: {"class":999}

2011年8月4日木曜日

オイラー・丸山法とPythonのMatplotlib

MatplotlibはPython向けの2次元プロットライブラリ。Wikipediaの記事「Euler-Maruyama method - Wikipedia, the free encyclopedia」(確率微分方程式の数値解法「オイラー・丸山法」)の、サンプルプログラムの中で使われていたので、インストールすることになった。

以下、Mac OS 10.6.8にMatplotlibをインストールして、Wikipediaのサンプルプログラムを実行したという話。

Matplotlibのインストール

Mac OSの場合、特にMacPortsやHomebrewなどのパッケージ管理ソフトを使っているとインストールがうまくいかないことが多いらしい。というのは、Matplotlibが最新の共有ライブラリにリンクされずに、パッケージ管理ソフトであらかじめ導入されていた別の共有ライブラリにリンクされる、といった現象が起こりやすいから。開発者の人も認識しているようで、README.osxというファイルに"Building mpl on OSX has proven to be a nightmare because of all the different types of zlib, png and freetype that may be on your system."と書いてあった(まるでナイトメアらしい)。

Mac OS X 10.6.8 (Darwin 10.8.0 x86_64) では、次の手順でインストールができた。

1. PythonとNumPyを確認

前提条件として、Python 2.5以上と、NumPyモジュール(version 1.1以上)が必要とのこと。これは以下のコマンドで確認できる。

$ python --version
Python 2.6.1
$ python -c "import numpy;print numpy.__version__"
1.2.1

自分で入れたのか最初から入っていたのか記憶が無いが、とりあえず自分の場合はすでに必要なものがインストールされていた。

2. githubからMatplotlibを取得
$ git clone https://github.com/matplotlib/matplotlib.git
3. make.osxの一部を書きかえる
$ cd matplotlib
$ vi make.osx
$ git diff make.osx
diff --git a/make.osx b/make.osx
index 4639eac..8dc60c7 100644
--- a/make.osx
+++ b/make.osx
@@ -3,6 +3,7 @@
 # make -f make.osx PREFIX=/Users/jdhunter/dev PYVERSION=2.6 fetch deps mpl_install
 # (see README.osx for more details)
 
+PREFIX=/usr/local
 MPLVERSION=1.1.0
 PYVERSION=2.6
 PYTHON=python${PYVERSION}
@@ -16,8 +17,8 @@ ARCH_FLAGS=-arch i386 -arch x86_64
 # but the download URLs are subject to change.
 
 ZLIBVERSION=1.2.5
-PNGVERSION=1.5.1
-FREETYPEVERSION=2.4.4
+PNGVERSION=1.5.4
+FREETYPEVERSION=2.4.6

変更点は3つ。第一に、共有ライブラリのインストールパスを"/usr/local/lib"にしたいので、PREFIX=/usr/local を追加。それから、libpng と freetype のバージョンを現時点で最新の番号にした。

4. makeする
$ make -f make.osx fetch deps mpl_install_std

これを実行すると、fetch, deps, mpl_install_stdという3つのターゲットが処理される。fetchがzlib等のライブラリのソースをダウンロードしてきて、depsがライブラリのコンパイルとインストールをして、最後にmpl_install_stdがMatplotlib自身のコンパイルとインストールを行う流れ。

完了したら、/usr/local/lib/Library/Python/2.6/site-packages/matplotlib を確認してみる。

$ ls -t1 /usr/local/lib/
libz.1.2.5.dylib
libz.1.dylib
(略)

$ ls -t1 /Library/Python/2.6/site-packages/matplotlib
mlab.pyc
mpl.pycf
offsetbox.pyc
(略)

$ otool -L /Library/Python/2.6/site-packages/matplotlib/_png.so
/Library/Python/2.6/site-packages/matplotlib/_png.so:
 /usr/local/lib/libpng15.15.dylib (compatibility version 20.0.0, current version 20.0.0)
 /usr/local/lib/libz.1.dylib (compatibility version 1.0.0, current version 1.2.5)
 /usr/lib/libstdc++.6.dylib (compatibility version 7.0.0, current version 7.9.0)
 /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 125.2.0)

ポイントは(1)共有ライブラリができていて、(2)matplotlibのモジュールができていて、(3)モジュール内の共有ライブラリが(1)の共有ライブラリに依存していることの3つ。

オイラー・丸山法

常微分方程式の世界における「オイラー法」に対応するのが「オイラー・丸山法」らしい。「丸山」のフルネームは丸山儀四郎。

Euler-Maruyama method - Wikipedia, the free encyclopedia のExample code(Python)をそのままコピー&実行するとグラフができる。

コードでrandomとか使ってるからあたり前だけど、「実行する度に結果が変わってOK」という考えが新鮮。これまで確定的な微分方程式の数値計算しか扱ったことが無かったので変な感じがする。

ざっと検索したところ、普通のプログラミング環境ではなくエクセルを使って計算する人もいる(そういう方向性の本が出版されている)。

Mac OS で XZ形式アーカイブを使う

今日まで知らなかったが、Mac OS標準のコマンドでは "tar xJf *.tar.xz" ができない。

大抵は gzip か bzip2 を使えば済む話だが、どうしても xz しか選択肢が無い状況なら XZ utils と GNUのtarをインストールするとよい(詳しいことは「Mac で XZ 形式を圧縮・解凍したいときの備忘録 - takkan_mのNo planな日常」に書いてあった)。

あとどうでもいいが tar のオプションは人によって揺らぐ。Jxf だったり xJf だったり -Jxf だったり… 自分の場合は xc が必ず最初に来る。コマンドを打つとき、開く(x)か閉じる(c)かが最初に頭の中で決まるから。

2011年8月3日水曜日

GoogleのBloggerに関連記事を表示する(brps - gas.js)

クリボウの Blogger Tips: Blogger で「関連記事」リストを表示する 2 つの方法 を参照して「3行コピペでできる方法」を今日試したのだが、期待どおりに動作しなかった。具体的には、関連記事のリストが表示されるべき位置に「キーを取得してください」という旨のエラーメッセージが表示されてしまった(英語だった)。

問題のJavaScriptを提供しているbrpsプロジェクトページ brps - Blogger Related Posts Service - Google Project Hosting を調べたら、「ClientGasJs」のページに違う方法が書いてあった。BRPSデータベースを使う方式から、Google AJAX Search APIを使う方式に変えた、ということらしい。

こちらの方法はうまく動作したので、メモしておく。

1. Blogger 管理画面「レイアウト > HTML の編集」ページを開く
「ウィジェットのテンプレートを展開」にチェックを入れる
2. 関連記事を表示したい場所に <div id='gas-results'/> 等を追加
  <b:if cond='data:blog.pageType == &quot;item&quot;'>
    <div>
      <h3>Related Posts</h3>
      <div id='gas-results'/>
    </div>
  </b:if>

見出しに相当するh3の部分は、利用しているテンプレートに依存する(h2h4を使うほうが適切な場合もあるだろう)。<b:if>...</b:if>で囲んでいるのは、一つの記事だけが表示される場合に限り関連記事を表示するため。トップページやアーカイブページのように複数記事が表示される場合、今回の方法はうまく動作しない(1番上にある記事しか関連記事が表示されない)。

3. </body>の前あたりにJavaScriptを追加
<b:if cond='data:blog.pageType == &quot;item&quot;'>
  <script src='http://ajax.googleapis.com/ajax/libs/jquery/1.6.2/jquery.min.js'/>
  <script>
window.brps_gas = {
//  remove_tags: ['unwanted_tag1', 'unwanted_tag2'],
//  tag_selector: 'a[rel=tag]',
  limit: 5,
//  add_sites: ['secondblog.blogspot.com', 'thirdblog.blogspot.com'],
  remove_string_regexp: /^.*?: /,
  exclude_url_regexp: /(\/search\/label\/|(archive\.html|blog\.example\.com\/|\.blogspot\.com\/)$)/,
  html_loading: '<span>Loading...</span>',
  html_no_results: '<span>Found no results.</span>'
  };
  </script>
  <script src='http://brps.appspot.com/gas.js'/>
</b:if>

jQueryをすでに利用している場合、<script src='http://ajax.googleapis.com/ajax/libs/jquery/1.6.2/jquery.min.js'/>は必要ない。動作を調整するためにremove_tags, tag_selector, limit等のオプションを指定できるので、状況に合わせて調整する。自分の場合は不要だったので//でコメントアウトしたが、

  • 関連記事を洗い出すときに無視して欲しいラベル(tag)があれば、remove_tagsの所に列挙する
  • ラベル(tag)のhtmlコードをカスタマイズしているのであれば、tag_selectorの所で変更する
  • 複数のドメインでブログを書いているのであれば、add_sitesの所に列挙する。

以上の操作を行ってレイアウトを保存すればhtmlに反映される。あとは必要に応じてCSSを調整すればOK。

2011年8月2日火曜日

コマンドを手軽にマルチプロセス実行 GNU Parallel

GNU Parallelというプログラムを今さら知ったのでメモしておく。これは、複数のプログラムを並行して実行したいときに便利。

インストール

GNU Parallelのダウンロードページから最新版の parallel-20110722.tar.bz2 をダウンロードし、configure, make, make install する。

$ wget ftp://ftp.gnu.org/gnu/parallel/parallel-20110722.tar.bz2
$ tar xvjf parallel-20110722.tar.bz2
$ cd parallel-20110722
$ ./configure
$ make
$ sudo make install

ちなみに環境は Darwin 10.8.0 x86_64。

試してみる

とりあえずPerlで簡単なプログラムを作って試す。

print_argv0.pl
#!/usr/bin/perl
sleep(1);
print "$ARGV[0]\n";
exit;
1秒間スリープして引数を表示するだけのもの。これにlsの結果を入力する処理を、prallelコマンド経由で実行してみる。
同時に実行するジョブ数 = 20 で実行した場合(-jオプション)
$ time ls|parallel -j 20 ./print_argv0.pl {}
COPYING
Makefile
Makefile.am
Makefile.in
NEWS
README
aclocal.m4
config.h
config.h.in
config.log
config.status
configure
configure.ac
install-sh
missing
print_argv0.pl
src
stamp-h1

real 0m1.396s
user 0m0.229s
sys 0m0.259s
1.396s で終了したので、確かに同時に実行されている様子。lsの結果が18行なので順番に実行すれば18秒はかかってしまうはず。
ジョブ数 = 1 で実行した場合
$ time ls|parallel -j 1 ./print_argv0.pl {}
COPYING
Makefile
Makefile.am
Makefile.in
NEWS
README
aclocal.m4
config.h
config.h.in
config.log
config.status
configure
configure.ac
install-sh
missing
print_argv0.pl
src
stamp-h1

real 0m18.517s
user 0m0.231s
sys 0m0.243s
19.517s かかった。

プロセス

ついでにプロセスの状態を調べるため、ジョブの数を3にして parallel をバックグラウンド実行した後、psコマンドを打ってみた。

$ time ls|parallel -j 3 ./print_argv0.pl {} &
[1] 5140
$ ps axl
  UID   PID  PPID CPU PRI NI      VSZ    RSS WCHAN  STAT   TT       TIME COMMAND
(略)
  501  5142  5140   0  29  0  2443672   8584 -      S      p0    0:00.18 /usr/bin/perl -w /usr/local/bin/parallel -j 3 ./print_argv0.pl {}
  501  5172  5142   0  30  0  2437344   1048 -      S      p0    0:00.01 /usr/bin/perl ./print_argv0.pl Makefile.in
  501  5173  5142   0  30  0  2437344   1048 -      S      p0    0:00.01 /usr/bin/perl ./print_argv0.pl NEWS
  501  5174  5142   0  31  0  2437344   1048 -      S      p0    0:00.01 /usr/bin/perl ./print_argv0.pl README
(略)

parallel自体もperlで書かれており、/usr/bin/perl -w により実行されている(プロセスID 5142)。中ではforkしているらしく、子プロセスが3つ生成されている(5172, 5173, 5174)。

2011年7月31日日曜日

SICP(計算機プログラムの構造と解釈)の講義ビデオ

SICP(計算機プログラムの構造と解釈)の講義ビデオがあった。G. J. Sussman 本人が講義してて楽しい。

このビデオでは、第4章の metacircular evaluator(超循環評価器)のあたりを解説している。

car, cdrだけでなくてcadarcadadrまで発音しているのが微笑ましい(これは"horrible"ですねー、とか言いながら)

最初に流れるバッハの「主よ、人の望みの喜びよ」もかっこいい。音源のトーンに時代を感じるけどかえって新鮮。エッシャーの絵「描く手」も挿入されていて無限と自己言及を暗示してる。

2011年7月29日金曜日

ネットワークのベンチマークソフト Netperf

netperf は TCP/UDP, Unix Domain Sockets などのスループットを計測できるソフトの一つ。ここで言う「スループット」は単位時間あたりのデータ転送量のこと。

これを使うためには、ネットワーク内で通信を行う両ホストにインストールしておく必要がある。インストール後は、まず一方のホストでサーバープログラム(netserver)を起動して、もう一方のホストでクライアントプログラム(netperf)を実行するという手順。デフォルト動作では、サーバーは12865番ポートをListenする模様(場合によっては通信できるよう開けておく必要がある)。

CentOS 6へのインストール

rpmforgeのレポジトリを使えば yum でインストールできる。

rpmforgeを参照するための設定は、「CentOS 6 - 初期設定 - yum用リポジトリ追加 : Server World」に詳しく書いてある。

# yum --enablerepo=rpmforge install netperf

Mac OS X へのインストール(Mac OS 10.6.8)

MacPortsでインストールできるらしいが、MacPortsをあまり使っていないので、ソースをコンパイルして入れた。

$ wget ftp://ftp.netperf.org/netperf/netperf-2.5.0.tar.bz2
$ tar xvjf netperf-2.5.0.tar.bz2
$ cd netperf-2.5.0
$ ./configure
$ make
$ make check
$ sudo make install

実行例

こんな感じで結果が出力される。

$ netperf -H 192.168.1.20
MIGRATED TCP STREAM TEST from (null) (0.0.0.0) port 0 AF_INET to (null) (192.168.1.20) port 0 AF_INET
Recv   Send    Send                          
Socket Socket  Message  Elapsed              
Size   Size    Size     Time     Throughput  
bytes  bytes   bytes    secs.    10^6bits/sec  

262140 131070 131070    10.00    14149.31

2011年7月25日月曜日

二分ヒープ in Elisp(かなり妥協)

ヒープソートで使う二分ヒープ(binary heap)。副作用を使わないリスト版を作ろうと思ったが、いいアイデアがない。

結局、よくある配列版のアルゴリズムで妥協した…

;;; すみませんがトップレベルの変数を使いますよ、と
(defvar *heap*)
=> *heap*

(defvar *n*)
=> *n*

;;; 初期化関数
(defun init-heap (N)
  (setf *heap* (make-vector N -1) *n* 0)
  N)
=> init-heap

;;; 追加する関数(最小値が根になるよう並べる)
(defun heap-push (x)
  (let ((i *n*) (i-parent))
    (incf *n*)
    ;; 親と比べながら上へ移動
    (while (and (> i 0)
                (< x (elt *heap* (setf i-parent (/ (- i 1) 2)))))
      (aset *heap* i (elt *heap* i-parent))
      (setf i i-parent))
    (aset *heap* i x)))
=> heap-push

;;; 取り出す関数
(defun heap-pop ()
  (if (zerop *n*)
      nil
    (let ((ret (elt *heap* 0))
          (i 0)
          (i-child nil)
          (v-child nil)
          (v-last (elt *heap* (1- *n*))))
      ;; 子と比べながら下へ移動
      (while (and (setf i-child (select-child-idx i))
                  (< (setf v-child (elt *heap* i-child)) v-last))
        (aset *heap* i v-child)
        (setf i i-child))
      (aset *heap* i v-last)
      (decf *n*)
      ret)))
=> heap-pop

;;; 補助関数(i番目の要素の子を求める。子が2つある場合は値が小さいほうを選ぶ)
(defun select-child-idx (i)
  (let ((cleft (+ (* 2 i) 1))
        (cright (+ (* 2 i) 2)))
    (cond ((and (< cright *n*)
                (< (elt *heap* cright) (elt *heap* cleft)))
           cright)
          ((< cleft *n*) cleft)
          (t nil))))
=> select-child-idx

やっぱりElispで配列を扱うのはめんどくさい。変数のsetf, asetが本当につらい…

続いて動作確認。

;;; 10要素のヒープを作る
(init-heap 10)
=> 10

;; 乱数10個作って push する
(mapcar 'heap-push (loop for i from 1 to 10 collect (random 100)))
=> (29 80 21 8 70 96 19 93 62 86)

;; 10回ぶん pop してみる
(loop for i from 1 to 10 collect (heap-pop))
=> (8 19 21 29 62 70 80 86 93 96)

ちゃんと小さい順に pop されているのでOKだが、もっときれいに書きたい。

Wikipediaの二分ヒープのページを見てたら「スレッド木」というキーワードが載っていたので今度調べる。あるいは "Purely Functional Data Structures" とかか。

2011年7月24日日曜日

コマンドラインで基数変換

汎用的なのは、bcコマンドを使う方法。

# 16進 -> 10進
$ echo 'obase=10;ibase=16;FF'|bc
255

# 2進 -> 10進
$ echo 'obase=10;ibase=2;11111111'|bc
255

# 16進 -> 2進
$ echo 'obase=2;ibase=16;FF'|bc
11111111

10進と16進の変換なら、printfコマンドが使える。

# 16進 -> 10進
$ printf "%d\n" 0xFF
255

# 10進 -> 16進
$ printf "%X\n" 255
FF

2011年7月19日火曜日

文字列の1文字目だけ大文字にする関数

最近、Perlにucfirstという関数があると知ったので、記録しておく。

Perlの場合
ucfirst
$ perl -le 'print ucfirst("hello")'
Hello
PHPの場合
Perlと同じく、ucfirst
$ php -r 'echo ucfirst("hello");'
Hello
Emacs Lispの場合
upcase-initials
※Perl, PHPとは仕様が少し異なる。1文字目が空白だと読み飛ばし、最初のアルファベットを大文字にする。
(upcase-initials "hello")
"Hello"
(upcase-initials " hello")
" Hello"
Common Lispの場合
string-upcase
(string-upcase "hello" :start 0 :end 1)
"Hello"

Mach-Oファイル形式と、それにまつわるツール

「Mach-O」とは Mac OS X におけるオブジェクトファイルのフォーマットのこと(LinuxにおけるELFみたいなもの)。詳しいことは apple.com のドキュメント「Mac OS X ABI Mach-O File Format Reference」にとても分かりやすく書いてある。

LinuxのELFなら readelfldd などでオブジェクトファイルを解析できる。一方、Mach-O の場合はどうすればいいのだろうか。このあたり、実際に手を動かして調べたことを記録しておく。

Mach-Oフォーマットに関する雑感

  • ELFより分かりやすい気がする(とりあえず「プログラムヘッダ」「セクションヘッダ」のような二面性がない)
  • Mach header, load commands, segments, segments の中の sections で構成されている
  • segmentは6種類だけ(__PAGEZERO, __TEXT, __DATA, __OBJC, __IMPORT, __LINKEDIT)
  • segment と sections の名前は、それぞれ大文字、小文字で表す(命名規約)

otoolコマンド

Linuxの"readelf"みたいなコマンドで、Mach-Oの情報をフォーマットして出力してくれる。オプション-vで人間向けのシンボリックな表示になる。

Machヘッダ
$ otool -hv /bin/ls
/bin/ls:
Mach header
      magic cputype cpusubtype  caps    filetype ncmds sizeofcmds      flags
MH_MAGIC_64  X86_64        ALL LIB64     EXECUTE    13       1928   NOUNDEFS DYLDLINK TWOLEVEL
__TEXTセグメントの中の __textセクション
$ otool -tv /bin/ls
/bin/ls:
(__TEXT,__text) section
0000000100001478 pushq $0x00
000000010000147a movq %rsp,%rbp
000000010000147d andq $0xf0,%rsp
(略)
__DATAセグメントの中の __dataセクション
$ otool -dv /bin/ls|head
/bin/ls:
(__DATA,__data) section
0000000100006540 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
0000000100006550 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
0000000100006560 50 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
(略)
共有ライブラリの依存関係。Linuxでの lddコマンドに相当
$ otool -Lv /bin/ls
/bin/ls:
 /usr/lib/libncurses.5.4.dylib (compatibility version 5.4.0, current version 5.4.0)
 time stamp 2 Thu Jan  1 09:00:02 1970
 /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 123.0.0)
 time stamp 2 Thu Jan  1 09:00:02 1970

sizeコマンド

セグメントのサイズを表示してくれるコマンド。オプション無しなら __TEXT, __DATA, __OBJC, その他, 全体 を表示。オプション有り(-mなど)だと、すべてのセグメントについて表示。

オプションなし
$ size /bin/ls
__TEXT __DATA __OBJC others dec hex
24576 4096 0 4294979584 4295008256 10000a000
-m オプション
$ size -m /bin/ls
Segment __PAGEZERO: 4294967296
Segment __TEXT: 24576
 Section __text: 14575
 Section __symbol_stub1: 456
 Section __stub_helper: 776
 Section __cstring: 1199
 Section __const: 56
 Section __unwind_info: 188
 Section __eh_frame: 2072
 total 19322
Segment __DATA: 4096
 Section __nl_symbol_ptr: 56
 Section __la_symbol_ptr: 608
 Section __program_vars: 40
 Section __const: 600
 Section __data: 76
 Section __bss: 228
 Section __common: 140
 total 1748
Segment __LINKEDIT: 12288
total 4295008256

nmコマンド

Linuxでおなじみのコマンドだが(GNU の binutils に入ってる)、Macにも同じ名前のコマンドがあった。U, sなどのシンボルの意味はLinuxとだいたい一緒かな。

実行ファイルの場合
$ nm /bin/ls
                 U __DefaultRuneLocale
                 U ___assert_rtn
                 U ___error
(略)
共有ライブラリの場合
$ nm /usr/lib/libSystem.B.dylib
000000000014331a s  stub helpers
000000000017a1e6 S $ld$hide$os10.4$__Unwind_Backtrace
000000000017a1d0 S $ld$hide$os10.4$__Unwind_DeleteException
(略)

2011年7月17日日曜日

Mac OS XのプロファイラSharkをコマンドラインで

MacでCプログラムを書いていて、プロファイルを調べたくなった。Linuxであればgprofを使うので、とりあえず"which gprof"してみたらMac OSにも入っていた。

しかし、実際に使ってみると期待どおりに動かない。呼出回数は計測されるが時間が計測されないらしく、次の例のように 0.0 が並んでしまった。

$ gprof foo gmon.out
(中略)
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
  0.0       0.00     0.00   200001     0.00     0.00  _main [79]
  0.0       0.00     0.00   200000     0.00     0.00  _f1 [80]
  0.0       0.00     0.00   200000     0.00     0.00  _f2 [81]
  0.0       0.00     0.00   100000     0.00     0.00  _f3 [82]
  0.0       0.00     0.00        1     0.00     0.00  __start [83]

環境は以下のとおり。

$ uname -mrs
Darwin 10.8.0 x86_64

Shark

調べたところ Mac OS で gprof の動作が不完全なのはFAQというか一般常識。代わりに"Shark"を使うのが定石らしい。

そのShark、「MacOSXではgprofが使えない→Sharkを使う - 西尾泰和のはてなダイアリー」で紹介されているように、確かにこれで間に合うのだが、GUIなのが面倒でツラい。1つのプロセスのプロファイルが欲しいのに、たくさんのプロセスを一度にプロファイリングしてその中から選ぶのも冗長な気がしてしまう。

Sharkをコマンドラインで

man shark してみたら実はコマンドラインからも使えて、テキスト形式のレポートも簡単に生成できることがわかった。

以下はfooというプログラムのプロファイルをとってレポートする例。

$ shark -1 -G -i ./foo
shark 4.7.3 (383)
* Option+Esc to start/stop a trace session
* Ctrl+c to stop sampling and quit (any pending samples are processed and saved)

* Batch mode
* Watching task exits
* Profiling limited to foo (PID #33472)

Sampling Config: Time Profile
Timed Samples & Counters
-Sampling begins immediately.
-A sample is taken every 1ms.
-Sampling ends automatically after 30s.



Ready. 

Sampling...
0    #これはプログラムfooが出力した数字

Processing samples...( Ctrl-c will cancel processing; No session will be created. )


CHUDData - Analyzing samples...

(略。WARNINGが出力される…)

sharkコマンドが終わると、カレントディレクトリにファイルが2個生成される。

一つは "session_001.mshark" で、shark的には session file と呼ばれるバイナリ。プロファイルの1セッション分の情報が記録されていると思われる。

もう一つは"session_001-report.txt" で、これがテキストのレポート。次のような内容になっている。長い。

$ cat session_001-report.txt 

================================================================================
Session
================================================================================
Authored by: dminor11th on 2011-07-17 19:13:45 +0900 (started 2011-07-17 19:13:32 +0900)
Version: Shark 4.7.3-383 (Session v0.3.0)
Host: dminor11th-MacBookPro.local
Operating System: Mac OS X 10.6.8 (10K540)
Machine Class: MacBookPro5,5
Memory: 4096 MB
Processor: 2 x 2530/1064 MHz Intel Core 2 (Penryn) v7.0
Memory Controller: Unknown
IO Controller: UnknownCHUD.framework: v4.7.3
CHUDProf.kext: v366
CHUDUtils.kext: Unknown

================================================================================
Sampling Configuration
================================================================================
Timed Samples & Counters
-Sampling begins immediately.
-A sample is taken every 1ms.
-Sampling ends automatically after 30s.


================================================================================
Module: SharkProfileAnalysis
================================================================================
REPORT:


================================================================================
Active Process Summary
================================================================================
Process [PID]                     % Total
-----------------------------------------
foo [33472]                  100.0%
-----------------------------------------
Total                              100.0%

Process [PID]                     # Total
-----------------------------------------
foo [33472]                   12107
-----------------------------------------
Total                               12107

===============================================================================================
  foo [33472]
    % Total                               Symbol                  Library      Address   Length
-----------------------------------------------------------------------------------------------
      58.4%                              strncmp /usr/lib/libSystem.B.dylib 0x7fff8833c280     0xe5
      20.0%                                  f2 /Users/dminor11th/temp/foo  0x100000863    0x14c
      18.1%                                  f3 /Users/dminor11th/temp/foo  0x100000a8d     0x81
       2.4%                    dyld_stub_strncmp /Users/dminor11th/temp/foo  0x100000dae      0x6
       0.1%                           __vfprintf /usr/lib/libSystem.B.dylib 0x7fff8834662c   0x5304
       0.1%                              __bzero /usr/lib/libSystem.B.dylib 0x7fffffe00600    0x180
       0.1%                            vsnprintf /usr/lib/libSystem.B.dylib 0x7fff8837b454    0x194
(略)

「あーあ、strncmpが58.4%か…」みたいな感じ。

以上、sharkについて。これでとりあえずは Mac OS でのプロファイラには困らないかなと。

Bash Process Substitution

シェルスクリプトには、command substitution や parameter expansion のほかにも process substitution、つまりプロセス置換という概念がある(Bash限定らしい)。

…を見て知った。

今ひとつな例だが、md5チェックサムの検証に使える。

$ diff -s <(md5 -q valgrind-3.6.1.tar.bz2) valgrind-3.6.1.md5
Files /dev/fd/63 and valgrind-3.6.1.md5 are identical

2011年7月8日金曜日

D. リッチー&K. トンプソン、日本国際賞(今さら)

この二人が来日してたなんて、初めて知った。すごい。でも四月の話だ...
あ、来日はしてなかった… 中止になったため来年(2012年)4月にあらためて招く予定らしい: 公益財団法人 国際科学技術財団

「K&R」はまず大学の図書館で日本語で読んで、そのあとAmazonで英語版を買って読みなおした。専攻が計算機じゃなかったから、計算機畑の人がどういう英語を使うのか知りたかった。
UNIXとC言語に関する功績のほかにはどういう人物かまったく知らなかったが、Youtubeに受賞者紹介があって家族の写真とかも見れた。
D. Ritchie は「新ANSI C言語辞典」の中の挿絵と顔の印象が違う。実物はかなりさわやかだ。そしてK. Thompson は子供の頃は日本に住んでいた。初耳。

1980年頃の映像もみつけた。ベル研で、Unixについて軽く説明してる。「kernel, shell, utilities の3つの部分でできている」とか。

2011年7月1日金曜日

sleep sort in Elisp

いまさらながら "sleep sort" というネタを知った。非同期処理を使ったすごい発想。

いちおうElispで書いてみた。run-at-timeなんて関数があるんですねー、と。

(defun sleep-sort (lat)
  (if (null lat) nil
    (lexical-let ((n (car lat)))
      (run-at-time n nil (lambda () (print n))))
    (sleep-sort (cdr lat))))

(sleep-sort '(3 2 1 0))

2011年6月25日土曜日

重複組み合わせ(個数に制限がある場合) in Elisp

重複組合せ」より引用:

n 種のものから r 個取り出す組合せ(並べ方)の総数を求めよ。
ただし、同種のもの同士に区別はなく、それぞれ a1、a2、a3、・・・、an 個ずつ存在し、 n=a1+a2+a3+・・・+an≧r とする。

要するに、卑近な例を挙げれば「靴下どれでも5足で1,000円。ただしどれも在庫わずか」みたいな状況における、組み合わせの数でしょうか。こういう数のことを一般的に重複組合せ(ちょうふくくみあわせ、repeated combination)と呼び、個数の制限が無い場合は nHmm+n-1Cm = m+n-1Cn-1 で計算することができるとのこと(数学で習ったかもしれないけど、nHmなんて記号は覚えていない)。

以下では、個数制限ありの場合の問題を解くプログラムを書いてみた。n種類の物が並んでいる中から、(a)先頭の物を1個取り出す場合、(b)取り出さない場合、のそれぞれについて関数を再帰的に適用して、和を取っていけばいいだけ。

;;; lat: 個数のリスト(a1, a2, ..., an)
;;; r: 取り出す数
(defun solve (lat r)
  (cond
   ((null lat) 0)                       ;リストが空なので 0
   ((zerop r) 1)                        ;最後まで取り出したので 1
   (t (+ (if (<= 1 (car lat))           ;先頭の物を取り出す場合
             (solve
              (cons (1- (car lat)) (cdr lat)) ;先頭の物を1個消費
              (1- r))                   ;あと r - 1 個取り出す必要がある
           0)                           ;在庫切れで取り出せないから 0
         (solve (cdr lat) r)))))        ;先頭の物を取り出さない場合

;;; テスト
(solve '(1) 1)
=> 1

(solve '(1 1 1) 1)
=> 3
;; 以下の3通り
;; 1 0 0 
;; 0 1 0
;; 0 0 1

(solve '(2 2 2) 3)
=> 7
;; 以下の7通り
;; 2 1 0
;; 2 0 1
;; 1 2 0
;; 1 1 1
;; 1 0 2
;; 0 2 1
;; 0 1 2

(solve '(10 10 10) 10)
=> 66

最後の 66 の信憑性に関しては、こちらのページ「重複組み合わせ」に、3種類のものが10個ずつある中から10個とる場合の数は 66 だと書いてあったので間違いないと思われる。

ここでは自然に再帰で考えたけれども、漸化式を導出して動的計画法を使うと O(n×r) で解ける。具体的な方法は「Amazon.co.jp: プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本」に書いてある。式の展開が多少面倒かもしれないが、紙と鉛筆を用意して臨めば問題ないレベルだった(数学嫌いでなければ)。

分割数 in Elisp

いわゆる「組み合わせ数学」の問題。整数 n を m 以下の整数の和で表す方法が何通りあるかを求めるというもの。考え方は「動的計画法」が参考になる。

単なる再帰で解く

(defun partition-num (n m)
  (cond
   ((or (= n 0) (= m 1)) 1)
   (t (+ (if (>= n m) (partition-num (- n m) m) 0)
         (partition-num n (1- m))))))
=> partition-num
(partition-num 3 3)
=> 3

(partition-num 4 3)
=> 4

(partition-num 9 9)
=> 30

動的計画法的に配列を使って解く

my-make-arrayという関数で多次元配列とそのアクセサみたいな関数を作っている。要するに、Emacs Lisp で多次元配列を使うのは面倒くさいということ。

;;; 多次元配列と、その要素を読み書きする関数(ref, set)を作る関数
;;; 内部的にはデータを1次元配列でもつ。クロージャと連想配列でできている。
(defun my-make-array (&rest dim)
  (lexical-let ((dim dim) (v (make-vector (apply '* dim) 0)))
    (flet ((index (args) (cond
                          ((null dim) 0)
                          (t (+ (* (apply '* (cdr dim)) (car idx))
                                (index (cdr dim) (cdr idx)))))))
      `((ref ,(lambda (&rest args) (elt v (index dim args))))
        (set ,(lambda (val &rest args) (aset v (index dim args) val)))))))
=> my-make-array

;;; 関数を適用する関数
(defun my-call (obj method &rest args)
  (apply (second (assoc method obj)) args))
=> my-call

;;; 配列を使って分割数を解く関数
(defun partition-num-dp (n m)
  (let ((dp (my-make-array (1+ n) (1+ m))))
    (loop for i from 0 to n do
          (loop for j from 1 to m do
                (my-call dp 'set i j
                         (if (or (<= j 1) (zerop i)) 1
                           (+ (my-call dp 'ref i (1- j))
                              (if (>= i j)
                                  (my-call dp 'ref (- i j) j)
                                0))))))
    (my-call dp 'ref n m)))

(partition-num-dp 4 3)
=> 4

(partition-num-dp 9 9)
=> 30