みたのブログ

v2.6.17 (bcm43xx) で BUFFALO WLI-CB-G54S を使う

Linux カーネルに標準で備わっているドライバで動く無線 LAN カードわりと少ないようです。いろいろ検索して動作実績があるカードでも既に生産中止になっていたということも多いと思います。

BUFFALO の WLI-CB-G54S という無線 LAN カードはいまのところビックカメラなどどこでも売っていて Linux v2.6.17 から追加された bcm43xx というドライバで動作しました。

ファームウェアは bcm43xx ドライバの開発サイトで公開されている bcm43xx-fwcutter というツールで、Windows とか Mac OS 用のドライバの配布物から取り出す必要があるようです。また、ファームウェアをアップデートしたいときにも役立つかもしれないので手順を書いておきます。

まず、ファームウェアの元になる Windows とか Mac OS 用のドライバの配布物を見つける必要があります。bcm43xx-fwcutter の README にいろいろダウンロード可能な URL が載っているのでそこからダウンロードすることもできますが、ここでは BUFFALO WLI-CB-G54S 付属の CD-ROM のなかに入っているものを使うことにしました。

bcm43xx-fwcutter が対応しているファイル名と MD5SUM は -l オプションで表示されます。

# bcm43xx-fwcutter -l

...

その出力から付属の CD-ROM のなかの bcmwl5.sys が対応しているようでした。念のため -i オプションで確認します。

# bcm43xx-fwcutter -i /mnt/cdrom/driver/CBG54/WIN2000/bcmwl5.sys

bcm43xx-fwcutter can cut the firmware out of /mnt/cdrom/driver/CBG54/WIN2000/bcmwl5.sys

  filename :  bcmwl5.sys
  version  :  3.104.64.52
  MD5      :  3ccb53e4f0f5e9f4ae270cb2924cb941

ファームウェアを抽出して、所定のディレクトリに保存します。

# bcm43xx-fwcutter -w /lib/firmware/ /mnt/cdrom/driver/CBG54/WIN2000/bcmwl5.sys

カーネルに組み込まれたモジュールの場合はどうですか

サーバセレクトという雑誌の六月号のボツになった記事のつづきです。

カーネルに組み込んでビルドされたモジュールのモジュールパラメータを設定したい場合は、カーネルのブートオプションとして設定する必要があります。

例えば e100 ネットワークドライバをカーネルに組み込んでビルドし、そのモジュールパラメータ debug を 1 に設定したい場合は e1000.debug=1 というブートオプションを与えます。

つまり、以下のようにブートオプションを設定します。

<モジュール名>.<モジュールパラメータ名>=<モジュールパラメータ値>

またカーネルに組み込まれたモジュールについての情報は modinfo コマンドで表示することはできません。ただし、カーネルイメージ vmlinux があれば、つぎのようにして組み込みモジュールパラメータの一覧を知ることができます。

$ nm -n vmlinux | grep __param_str_ | \
  awk '{ print "p (char *) 0x" $1}' > list-param.cmd
$ gdb -batch -x list-param.cmd vmlinux | awk '{print $4}'

モジュールパラメータの一覧はどうやったらわかりますか

サーバセレクトという雑誌の六月号のボツになった記事の抜粋のつづきです。

モジュールについての情報を得るには modinfo コマンドを利用します。設定可能なモジュールパラメータの説明だけ表示したい場合はつぎのようにします。

# modinfo -p <モジュール名>

モジュールをロードしたあとに動的に変更できるものや、設定値を参照する価値のあるモジュールパラメータは sysfs ファイルシステムの以下のファイルから読み書きできるようになっています。

/sys/module/<モジュール名>/parameters/<パラメータ名>

ブートオプションの一覧はどうやったらわかりますか

サーバセレクトという雑誌の六月号ボツになった記事の抜粋のつづきです

Documentation/kernel-parameters にブートオプションの一覧や解説が書かれています。ただし、カーネルコンフィギュレーションによっては無効のものもありますし、このファイルには記述されていないものもあります。

もし利用しているカーネルイメージ vmlinux があればつぎのようにしてブートオプションの一覧を得ることができます。

$ nm -n vmlinux | grep __setup_str_[a-zA-Z_] | \
  awk '{ print "p (char *) 0x" $1}' > list-setup.cmd
$ gdb -batch -x list-setup.cmd vmlinux | awk '{print $4}'

ただし、vga ブートオプションや parse_cmdline_early() (arch/i386/setup.c) のなかで設定されているような一部のブートオプションは表示されません。

障害に備えて役立ちそうなブートオプションを教えてください

会社の業務の一環でサーバセレクトという雑誌の六月号に 4 ページ記事を書きました、 いま日本にもどっているので、ちょっと気になって確認してみたところページの都合上いくつかボツになっている部分があったので、それを抜粋して紹介します。

• panic=
• panic_on_oops=

kernel.panic と kernel.panic_on_oops カーネルパラメータと同じ設定をするブートオプションです。

なぜ同じような設定がカーネルパラメータとブートオプションの両方にあるかという理由は、カーネルパラメータは通常 /etc/sysctl.conf の設定ファイルに記述されたものがシステムの起動スクリプト実行中に設定されます。それ以前に パニックや Oops が起こる場合に備えて、デフォルト値 (panic=0, panic_on_oops=0) 以外に設定したい場合に利用します。

• log_buf_len=<buf_len>

ログバッファの値をバイト単位で指定します。 SysRq-t などで大量のカーネルログを出力させたとき、ログバッファが溢れてしまう場合にはこのオプションでログバッファのサイズを大きくすることができます。ログを dmesg コマンドで見る場合には -s オプションで充分大きな値を指定する必要があるかもしれません。

以下の二つのブートオプションは起動時のトラブルに役立ちます。

• initcall_debug=1

カーネルの各初期化関数または、カーネルに組み込んでビルドしたモジュールの初期化関数を実行する前にその関数名を表示します。

Calling initcall 0xc03bc72c: init_mbcache+0x0/0x16()
Calling initcall 0xc03bc742: dquot_init+0x0/0xd3()
VFS: Disk quotas dquot_6.5.1
Dquot-cache hash table entries: 1024 (order 0, 4096 bytes)
Calling initcall 0xc03bc815: dnotify_init+0x0/0x22()
...

• earlyprintk=vga vga=ask

printk() の出力を画面に表示するため機能が初期化される前の可能な限り早い段階でカーネルログが画面に表示できるようになります。ブートローダがカーネルイメージを読み込んだあと画面になにも表示されないままになってしまう場合は、これを試してみる価値があります。

• nmi_watchdog=

NMI ウォッチドッグ機能によってローカルタイマー割り込みが長時間発生していないことを検知して Oops メッセージを出力させます。コールトレースを調べれば、どこでロックアップしたか分かります。(Documentation/nmi_watchdog.txt)

 

Ext3 ファイルシステムで削除したファイルを復元について (2)

grep で削除したファイルの内容が含まれているブロックを探す際に、二つ落し穴があることが分かったので補足しておきます。

[1] ファイルに含まれている先頭の行のキーワードで検索する場合

たとえば、自作の Python スクリプトをうっかり削除してしまったものの、中身について全く記憶がない場合、とりあえず Python スクリプトの先頭ブロックをリストアップしようと、次のようにしたくなるかもしれません。

# grep -a -b '#!/usr/bin/python' /dev/hda1

しかし、たとえばそのファイルのひとつ前のブロックが何か別のファイルの末尾のブロックで次のようなレイアウトになっていたとします。

29fbf90   L   A   R   =   y  \n  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
29fbfa0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
*
29fc000   #   !   /   u   s   r   /   b   i   n   /   p   y   t   h   o

grep の -b オプションで出力されるオフセットは、マッチしたパターンが含まれている行の先頭の位置です。マッチしたパターンの先頭の文字の位置ではありませんでした。だから grep -b はひとつ前のブロックの改行の次のオフセットを表示してしまいます。

これを避ける簡単な方法をいろいろ考えたのですが、grep の代わりに次のように perl で検索するというのもいいかもしれません。

# perl -n -e 'BEGIN { undef $/; }' -e 'while (m/<パターン>/g) { printf "%d\n", pos(); }'

#!/usr/bin/perl

$block_size = 1024;
$blkno = 0;
open(FH, "< /dev/hda1") or die "can't open $!";
while (read(FH, $block, $block_size)) {
        if ($block =~ m|\#!/usr/bin/python|) {
                print "$blkno\n";
        }
        $blkno += 1;
}

[2] ファイルサイズがブロックサイズより大きくて、キーワードが二つのブロックにまたがっていて、さらにその二つが連続したブロックに割り当てられていなかった場合

これにひっかかるケースはまれかもしれませんので、検索するパターンをちょっと変えれば避けれると思います。

Ext3 ファイルシステムで削除したファイルを復元について

うっかりファイルを消してしまったりすることは、よくあると思います。

いろいろ事情があって、ext3 ファイルシステムで削除したファイルの復元について、半日ぐらい調べていました。 恥ずかしながら ext2 の場合も同じだろうと ext2 の場合の復元方法を一生懸命テストしたり、古い文書やメーリングリストの議論に惑わされたりしながら、やっと Linux ext3 FAQ のなかの ext3 の開発者のひとりの引用を読んで調査が終了しました。

Q: How can I recover (undelete) deleted files from my ext3 partition?

つまり ext2 の場合は、ファイルを削除するとき inode を "deleted" としるしをつけるだけなので、 debugfs コマンドの lsdel で削除された inode の一覧を得ることができるし、その削除された inode 番号に対して debugfs コマンドの dump でファイルの中身もだいたい復元できることが期待できます。

# debugfs -R lsdel /dev/sdb1 > /tmp/lsdel.lst
# vi /tmp/lsdel.lst <間違って削除した日時とかで該当しそうな行だけ残す>
# awk '{printf "dump <%d> /tmp/undel.%d\n", $1, $1}' /tmp/lsdel.lst > /tmp/debugfs.cmd
# debugfs -f debugfs.cmd /dev/sdb1

しかし ext3 の場合は、ファイルを削除すると、inode からデータブロックへの参照をきれいにクリアするので inode からデータブロックをたどることができません。唯一の望みは grep でファイルの断片を見つけることぐらいとのことです。

1. まず、ブロックデバイスでもディスクイメージでもいいのですが、 dumpe2fs コマンドなどでブロックサイズを調べます。 この ext3 ファイルシステムのブロックサイズは 4096 バイトでした。

# dumpe2fs /dev/sdb1
...

Block size:               4096
...

2. grep の -b オプションでキーワードがマッチしたオフセットを表示するようにして、なにかファイルに保存しておきます。

# grep -a -b 'BEGIN RSA PRIVATE KEY' /dev/sdb1 | awk -F: '{print $1}' > list

追記: この grep での検索にはいくつか落し穴があったので、こちらのエントリも参照してください。

3. キーワードが含まれているブロックをファイルに保存します。

# cat list | while read i; do
    dd if=/dev/sda1 of=$i.data bs=4096 count=1 skip=$(($i/4096))
  done

4. 見つかったブロックの中身をひとつひとつチェックして削除したファイルを地道に探します。

メールとか自分で書いたプログラムとかのユニークなキーワードをおぼえていたら削除したファイルでもなんとか復元できるかもしれません。ファイルサイズがブロックサイズより大きくても、 ext3 はなるべく近くのブロックに割り当てるようにしているのでファイルシステムがひどく断片化していなければ、その辺の連続したブロックに同じファイルの内容が保存されている可能性が高いと思います。実際、ある 50KB ほどの削除してしまったテキストファイルを多分無傷で復旧できたということだけ伝えておきます。

Hamming weight

お金を払っていないので一週間遅れでしか読めないのですが LWN.net Weekly Edition というのを毎週目を通すようにしています。

先週号を一週間遅れで見ていると、 A summary of 2.6.17 API changes と題されたリリース間近の 2.6.17 での主なカーネル API の変更点がリストアップされている記事があり、そのなかで僕が少しまえにした変更について一行ふれられていました。

* A whole set of generic bit operations (find first set, count set bits, etc.) has been added, helping to unify this code across architectures and subsystems.

パッチは Patch: generic bitops からたどってもらえると見れるのですが、ほとんどが単純で地道な作業なのでつまらないと思います。ただし、セットされているビット数を数える速い方法については見る価値はあるかもしれません。

セットされているビット数のことを "Hamming weight" とか "popcount" (population count) といった呼び方をされるようです。たとえば 32-bit の整数の hamming weight は、ひとつひとつビットをチェックして数えていくより、つぎのようにしたほうが少ないステップで計算できます。

static inline unsigned int generic_hweight32(unsigned int w)
{
        unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
        res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
        res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
        res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
        return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
}

まず 32-bit の整数は 32 個の 1-bit ビットフィールドで、それぞれのビットフィールドが 1-bit の hamming weight になっていると考えることができます。つぎに 1-bit ビットフィールドを二組づつ組み合わせて足すと 16 個の 2-bit ビットフィールドは、それぞれのビットフィールドが 2-bit の hamming weight になっています。このようにくりかえしていけば、もとの 1 個の 32-bit フィールドの hamming weight が計算できます。

n-bit の hamming weight は最大でも n で、それを二つ足しても 2 の 2*n 乗より小さいのでそれぞれのステップでオーバフローしてしまうことはないので上のような工夫したマスクをかけて計算できるのですが、もっと工夫するともうちょっと効率的に計算できます。詳しくは linux@horizon.com というひとの証明をご覧ください。

http://lkml.org/lkml/2006/1/31/152

Bisection searches

あるプログラムをバージョンアップすると、それまでちゃんと動いていたのに何か動作がおかしくなってしまうということはよくあると思います。

再現性のあるバグがあって、ちゃんと動作するバージョンと、そうでないバージョンがあってそのプログラムが適切にバージョン管理されていれば、ほとんどの場合バージョン間の二分探索することによって、そのバグがいつどの変更によって引き起こされるようになったか特定することができます。

Linux kernel は、 v2.6.12 ぐらいから git というリビジョン管理システムで管理されていて、 上記のようなバグの二分探索は git-bisect というツールでおこなえます。

http://www.kernel.org/pub/software/scm/git/docs/git-bisect.html

たとえば v2.6.16 ではちゃんと動いていたけど v2.6.17-rc5 にアップデートしたらなにかがうまく動かなくなった場合、v2.6.16 から v2.6.17-rc5 までの間の変更によって引き起こされたと考えられます。その間にコミットされたパッチの数は

$ git-rev-list v2.6.17-rc5 ^v2.6.16 | wc -l
5861

5861 個あるようです。中間のリビジョンをコンパイルして一回試すごとにバグを引き起こす可能性のあるパッチの数を半分にできるので、5861 が 2 の何乗か分かればだいたい何回ぐらい試せばバグを引き起こすパッチを特定できるのか分かると思います。

ここで高校の時の数学をがんばって思い出してみて 2 を底とする log(5861) を計算します。

$ echo 'l(5861)/l(2)' | bc -l
12.51693112199869637797

だいたい 13 回ぐらいコンパイルして試せば問題のパッチを特定できます。
カーネルのコンパイルなので時間はかかるかもしれませんが、13 回ぐらいなら大した数ではないと思います。たとえ v2.6.12 から v2.6.17-rc5 の間を bisect しても

$ git-rev-list v2.6.17-rc5 ^v2.6.12 | wc -l
25110
$ echo 'l(25110)/l(2)' | bc -l
14.61597440815886228263

15 回ぐらいです。