2012/01/30

SystemTapで関数の呼び出し元を取得する

SystemTapはスクリプトで気軽にLinux Kernelの動作を調査できる素敵なツールです.
この記事は,SystemTapで関数の呼び出し元を取得する方法についてのメモです.
Tapset Referenceを参考にし,Context Functionsのfunction:callerを使用します.
最も簡単なものだと,このような形になります.


probe kernel.function("schedule").return {
  printf("caller : %s", caller())
}

出力はこんな感じ.Kernel内のschedule()関数を呼び出した関数名と,アドレスが出力されます.

[eiichi@fedora]~/work/stap% sudo stap schedule.stp
caller : cpu_idle 0xffffffffc04023d0
caller : cpu_idle 0xffffffffc04023d0
caller : run_ksoftirqd 0xffffffffc04558ed
caller : cpu_idle 0xffffffffc04023d0


さて,簡単な応用として,linux/kernel/sched.cで定義されているschedule()関数を呼び出している関数Top20を表示させてみましょう.
systemtap scriptは以下のようになります.


global callers

function print_top() {
  cnt=0
  printf("%-50s\tCount\n", "Caller")
  printf("---------------------------------\n")
  foreach( [name] in callers-) {
    printf("%-50s\t%5d\n", name, callers[name])
    if (cnt++ == 20)
      break
  }
  printf("---------------------------------\n")
}

probe kernel.function("schedule").return {
  callers[caller()]++
}

probe end {
  print_top()
  delete callers
}





eiichi@fedora]~/work/stap% sudo stap schedule_caller_top.stp -c "sleep 1"
Caller                                             Count
---------------------------------
cpu_idle 0xffffffffc04023d0                          332
worker_thread 0xffffffffc0468418                     166
schedule_hrtimeout_range_clock 0xffffffffc09202e7    116
futex_wait_queue_me 0xffffffffc047ec83                52
do_nanosleep 0xffffffffc0920158                       18
work_resched 0xffffffffc0921302                       17
schedule_timeout 0xffffffffc091fa05                   12
run_ksoftirqd 0xffffffffc04558ed                       8

---------------------------------




sleep ではcpu_idleが多くなります.
ちなみに,hackbenchを動かすと,このような感じです.

[eiichi@fedora]~/work/stap% sudo stap schedule_caller_top.stp -c "hackbench 10"
Running in process mode with 10 groups using 40 file descriptors each (== 400 tasks)
Each sender will pass 100 messages of 100 bytes
Time: 0.374
Caller                                             Count
---------------------------------
schedule_timeout 0xffffffffc091fa05                 1590
work_resched 0xffffffffc0921302                      735
cpu_idle 0xffffffffc04023d0                          349
worker_thread 0xffffffffc0468418                      83
rwsem_down_failed_common 0xffffffffc0920d25           22
schedule_hrtimeout_range_clock 0xffffffffc0920375     17
do_wait 0xffffffffc0452025                            10
schedule_hrtimeout_range_clock 0xffffffffc09202e7      5
run_ksoftirqd 0xffffffffc04558ed                       5
do_nanosleep 0xffffffffc0920158                        2
futex_wait_queue_me 0xffffffffc047ec83                 1
---------------------------------
ここで,schedule()関数ではなく,他の関数でも,呼び出し元Top20を表示させる場合を考えてみましょう.いちいちstap scriptを書き換えるのも面倒です.
付け焼刃的ですが,shell scriptと組み合わせると,簡単にできます.

#!/bin/sh
func=$1
cmd=$2
stap -e 'global callers
function print_top() {
  cnt=0
  printf("%-50s\tCount\n", "Caller")
  printf("---------------------------------\n")
  foreach( [name] in callers-) {
    printf("%-50s\t%5d\n", name, callers[name])
    if (cnt++ == 20)
      break
  }
  printf("---------------------------------\n")
}
probe kernel.function("'$func'").return {
  callers[caller()]++
}
probe end {
  print_top()
  delete callers
}' -c "$cmd"

使い方はこんな感じ.
linux/kernel/sched_fair.c のupdate_curr()関数で試してみました.
[eiichi@fedora]~/work/stap% sudo sh caller_top.sh update_curr "hackbench 10"
Running in process mode with 10 groups using 40 file descriptors each (== 400 tasks)
Each sender will pass 100 messages of 100 bytes
Time: 0.469
Caller                                             Count
---------------------------------
update_cfs_shares 0xffffffffc043c777               21460
put_prev_task_fair 0xffffffffc043d062              18516
dequeue_entity 0xffffffffc043cb79                  12369
enqueue_entity 0xffffffffc043d0e1                  12363
check_preempt_wakeup 0xffffffffc043c51f             9622
task_tick_fair 0xffffffffc043c90d                   1968
task_fork_fair 0xffffffffc043c308                    400
---------------------------------


ちなみにhackbench 10 は400個のtaskを生成するので,task_fork_fairからのupdate_curr呼び出し回数がちょうど400になってますね.

参考
RedHat Tapset Reference Manual

2011/03/20

原子力発電や被曝に関する各種資料

ここ最近自分が個人的に原子力発電について調べていて、気になった施設や資料一覧です。

1. 原子力公開資料センター
財団法人原子力安全技術センターが運営する、国からの委託を受け情報を一般に公開する施設です。

2. 大型原子炉の事故の理論的可能性及ぴ公衆損害に関する試算(海賊版)
1960年に旧科学技術庁がまとめた原子炉事故被害評価試算です。当時一般に公開されませんでしたが、後に公開されました。当時の日本の国家予算1.7兆円に対し、最悪の場合損害額は3.73兆円になると試算されています。原子力公開資料センターのHPで検索すると出てきます

3. 原発事故による放射能災害 -40年前の被害試算-
京都大学原子炉実験所の今中哲二さんによる資料2のまとめと解説です。

4. 福島原発の放射能を理解する
カリフォルニア大学サンタバーバラ校のBen Monreal 教授による放射能や今回の事故に関するわかりやすい解説です。

5. 緊急被ばく医療ポケットブック
 文部科学省からの平成16年度委託「緊急時対策総合技術調査」の一環として財団法人原子力安全研究協会が作成したものです。被曝に対する処置について非常に詳しく書かれています。



2011/01/18

Twitterのリツイートの広がり具合を表現しようとしてみた

本日何気なくつぶやいた以下の発言が、リツイートによりどんどん再帰的に広まり、今のところ46人の方にリツイートして頂きました。
自分の中の言語擬人化像。 C++:ツンツン優等生, Java:メガネ委員長, JavaScript:おてんば人気者, Perl:活発八重歯, Ruby:腹黒妹, PHP:パンツ担当, Pascal:メガネ地味, Haskell:ぺろぺろ担当, Erlang:金髪ツインテール双子
リツイートというのは一旦起こると、それが多くの人の興味を引くものであった場合、再帰的に行われ、まるで連鎖反応のようにすごい勢いで広まるようです。
今回は簡単なセルオートマトンモデルを作り、その広まりの様子を視覚的に見てみましょう。
なんかキモイのでちょっと注意してください。

Threshold:





一つ一つのピクセルは一人のツイッターユーザーを表し、その近傍は8近傍とします。
あるユーザーがつぶやいたとき、その近傍のユーザーは一定確率でそのつぶやきをリツイートするものとします。ここで定める確率が、つぶやきの「面白さ」のようなものです。Thresholdの値を変えていろいろ試してみてください。大きいとあっというまに広まりますし、小さいとすぐ止まってしまいます。だいたい0.41付近が広まるか、萎むかの境目のようです。黒ピクセルがリツイートしなかったユーザー。ピンク色がリツイートしたユーザーをあらわしています。

山火事とかがこんなふうに広まるかと思うとちょっと怖いですね。

2011/01/05

Haskellでlist monadを使って完全順列を生成してみました

完全順列(撹乱順列とも)とは順列を置換と見た場合、不動点をもたない置換のことをいいます。順列の要素数を無限大にした極限をとったとき、完全順列の個数(モンモール数)とすべての順列の個数(n!)の比が1:e(eは自然対数の底)になり、世の中の物好きを惹きつけています。
前回のN-Queens問題につづいてlist monadを利用して関数型言語のHaskellで完全順列を生成するコードを書いてみましょう。
*Main> derangement ['c','o','n','s']
>>["ocsn","onsc","oscn","ncso","nsco","nsoc","scon","snco","snoc"]
こんな感じになって欲しいのです。順列を生成した後にfilterを掛けるのは非効率的なのでやめておきます。
書いてみると以下のようになりました。
import Data.List

derangement xs = drg xs xs

drg [] ys = return []
drg xs (y:ys) =
  delete y xs >>=
  \x -> map (x:) (drg (delete x xs) ys)

Monadを利用することを考えると、こんなに簡単に書けるんですね。
素晴らしきかな、Haskell、Monad!

2011/01/03

Haskellでlist monadを使ってN-Queens問題を解いてみました

N-Queens問題は8-Queens問題の一般形で、 N x N のチェスのボード上にN個のクイーンが互いに攻撃しあわないような配置を求める問題です。バックトラッキングアルゴリズムで解くと非常に効率よく解ける例として有名です。
今回はHaskellでlist monadを使って解いてみましょう。List monadを用いることで簡単に楽しく書けるという利点があります。
動機は、いろいろ調べたのですが、Haskellで単純で速そうなものが見つからなかったためです。
アルゴリズムとしては当然バックトラッキング。
クイーンの配置を表すデータ構造としては [Int] を用いましょう。[(Int, Int)]としてしまうと冗長な感があります。経験上データ構造はなるべくダイエットして必要十分に近いものが理想的だと思います。そのほうが簡単に楽しく書けます。

まずlist monadの定義を確認しましょう。List は Monad型クラスのインスタンスです。その定義はGHC.Baseに記載されています。

instance  Monad []  where
  m >>= k             = foldr ((++) . k) [] m
  m >> k              = foldr ((++) . (\ _ -> k)) [] m
  return x            = [x]
  fail _              = []

bind関数>>= がfoldrを使って書かれていますが、xs >>= f = concat (map f xs)と同じことです。
以上から書いてみると、こんな感じになりました。

import Data.List

type Queens = [Int]

nQueens :: Int -> [Queens]
nQueens n = solve [1..n] []

solve :: Queens -> Queens -> [Queens]
solve [] ys = return ys
solve xs ys = 
  xs >>= func 
  where
    func x 
      | isOK (x:ys)  = solve (delete x xs) (x:ys)
      | otherwise    = fail "failed!" 

isOK :: Queens -> Bool  
isOK []  = True
isOK (q:qs)  =  (all (/= 0) . zipWith (-) [1..(length qs)] . (map (abs . (-) q))) qs

速度計測

比較対象
LiteratePrograms.org
pi8027
上のLiteratePrograms.org(以下LPと呼称)のものは同じくバックトラッキングとリストモナドを用いたもの、下のものはしらみ潰し探索法を用いたものです。しらみつぶし探索法は一般には遅いのですが、とてもコーディングしやすいという利点があります。

計測結果(単位:sec)

NEtsukataLPpi8027
90.230.732.73
101.063.8427.33
115.4423.83--

なんで速いの?
しらみ潰し探索法よりもバックトラッキングのほうが速いのは明らかです。
LPよりも自分のものが速いのは、確かめる必要の無い組み合わせを予め省いているからです。メモリの使用量も半分以下で済みます。

もっと速くてわかりやすい書き方がある場合は是非おしえてください!

2010/12/14

JavaScriptでミステリーサークルのようなものを自動生成

フラクタル図形等を作成する際によく用いられる形式文法L-Systemを使って、ミステリーサークルのようなものを自動で生成するものをつくりました。これにより、なんかの儀式にミステリーサークル的な模様が必要になった時に簡単に模様をつくることができます。でも、自分で念を込めて模様を考えたほうが、儀式はうまくいくと思います。

例えばこんな感じの模様ができます。

 

デモ
Key :






なにをしているのか
以下のようなL-Systemを構成し、JavaScriptでCanvasに描画しています。詳しくはソースコードを御覧ください。
Grammer
  Variables : 0
  Constants : [1-9][a-f]
  Start : 0
  Rule : 0 -> md5hash
  Iterate count : 3
ここでmd5hashというのはテキストエリアに入力された文字列のMD5Hash値です。
Semantics
  0 : なにもしない
  d=[1-9] : 左に d x 10 度回転
  a : 50前に直線を描いて進む
  b : 回れ右する
  c : 半径50の円を描く
  d : 原点に戻る
  e : 32前にジャンプする
  f : 半径32の円を描く


余談
テキストエリアに入力された値が同じであれば、同じ模様が出力されます。なにか面白い模様ができたらぜひKeyをコメントしてください!
MD5Hashの計算にはサイボウズ・ラボの光成茂雄さんのライブラリを使用させていただきました。ありがとうございます。

参考
Canvasに色々描いてみた - Webと文字

2010/12/01

Webサイトのサムネイルを撮ってBase64で返すWebサービスつくりました

サーバーサイドでのWebページレンダリングについて調べていたらいつの間にかつくっていました。Base64形式でサムネイルを出力してくれるものは今のところ見当たらなかったので、便利かな。

こちらです!
※負荷がかかった場合にうまくリクエストを捌けないバグがあり、うまく動いていないかもしれません。申し訳ないです。対策中です。

こんな感じのものが撮れます。



使い方
URLをテキストボックスに入力して、Sendボタンを押してしばらく待つと、テキストエリアに何か出力されます。エラーメッセージっぽい場合は無視してください。正しそうならテキストエリアをまるごとコピーしてHPなりブログなりに貼り付けると、うまく画像が表示されるはずです。

内部仕様
使用しているブラウザ : Firefox4 beta7 (en)
フラッシュプラグイン   : Adobe Flash Player 10.2 beta

どんなことをしているか
Xvfbで仮想フレームバッファをつくり、その上でFirefoxを動かし、スクリーンショットを撮って適当に加工してサムネイル化しています。

似たようなサービス
SimpleAPI
IgWebCap
Mozshot
websnaper
2010/12/01現在、僕が試したところ、上記のサービスはあまりうまく機能していませんでした。多分リクエストが多くて負荷が高いのでしょう。
それに加えhttpsに対応していなかったり複雑なURLを送信すると、思ったとおりの結果が得られません。
上記のサービスはサーバー側で画像を一定期間保存するため、サーバーの容量への負担が大きく、また貼りつけ先からのGETリクエストにも答えなければなりません。
拙作のモノはBase64で出力するので、サーバー側で画像を貯めておく必要はありません。

余談
実はこのサービスはNode.jsでのCanvas共有アプリに、書いた絵を保存する機能を付けることを目的にしてできた副産物です。現在のCanvas共有はクライアントから送られてきたデータをそのままサーバーに保存するため、任意のpng画像がサーバーに送り込まれてしまう脆弱性が存在します。事実、公開初日に何者かによりイーノックさんの画像が送り込まれてしまいました。その脆弱性を解消するべく考案したのが、サーバーサイドでのHTMLレンダリング、というわけです。そいういわけでブラウザにはWebSocketおよびWebWorkersに対応したFirefox4betaを選びました。

ご本尊はhttp://etsukata.com/web2img/w2i.plであり、それにたいしてXHRでリクエストをおくっています。サーバーの処理能力に余裕があったらレスポンスヘッダにAccess-Control-Allow-Origin: * を追加してみなさんに使ってもらえるようにしたいと思っています。


参考
pomo123の日記
http://d.hatena.ne.jp/pomo123/20080430/1209532590
The "data" URL scheme - RFC 2397
http://tools.ietf.org/html/rfc2397