http://yk55.com/blog the place to organize and record my ideas ... Mon, 28 Jun 2010 23:11:59 +0000 http://backend.userland.com/rss092 en AWK Users JPの中で紹介されている簡易HTTPサーバをベースに少しだけ機能追加してみた。例では固定の文字列しか扱っていなかったので最低限リクエストしたパスに従いそのファイルを表示できるようにした。 ソースコード – httpd.awk http://github.com/yokawasa/any/tree/master/awk_httpd/ http://github.com/yokawasa/any/blob/master/awk_httpd/httpd.awk #! /usr/bin/gawk -f BEGIN { port = "8080"; docroot = "./"; http_service = "/inet/tcp/" port "/0/0"; RS = ORS = "\r\n"; for (;;) { if ((http_service ... http://yk55.com/blog/2010/06/29/awk_http/ 前回の投稿ではlibeventのHTTP処理機能evhttpを使ったHTTPサーバを紹介したが今回はlibeventのRPCフレームワーク evrpcを使ったC/Sプログラミング方法を紹介してみる。このevrpcはかなりマイナーな部類のフレームワークといえる。これに関するドキュメントは少なく、検索してみるとまともなページがヒットしない。ヘッダやテストコードを読まない人にとってはちょっと厳しいかもしれない。 巷にはハイパフォーマンスで使いやすく少し検索すれば豊富なドキュメントやブログ記事がわさわさと出てくるようなフレームワークがごろごろしているのでこんなに地味で愛想ないフレームワークをふつーは選ばない。 そんな人気のないevrpcだけど実際に使ってみると思ったより悪くない。 動作は安定しているしAPIはシンプルで使いやすく拡張性も考慮されていてHook関数、Callback関数を駆使すれば好きに振る舞いを制御することができる。 少々粗挽きなところは全く気にしないでこれをベースに自分なりに使いやすいフレームワークを作ってやろうくらいに思ってる人には向いているかもしれない。 RPC marshalling用コードのジェネレート - event_rpcgen.py marshallingとはRPC C/S処理で内部的に使用するデータ構造をネットワーク転送用のフォーマットに変換することで、その逆をdemarshallingと呼ぶ。厳密には意味が違うらしいがserializationとdeserializationみたいなもの。 libeventにはデータ構造をmarshalling、demarshallingするコードをジェネレートするためのスクリプトが用意されている。それがevent_rpcgen.py。RPC C/S処理で使用するデータ構造を定められたフォーマットで定義してやりそれをevent_rpcgen.pyに食わせてやることでコードが生成される。 データ構造の定義フォーマットは次のとおり。 [データ構造の定義フォーマット] struct { [optional] = ; ... } データ型 - string 文字列 - bytes uint_tベクター。 [lenght]で長さを指定。　例、bytes hoge[10] - int uint32_t - struct[structname] ... http://yk55.com/blog/2010/06/05/libevent_rpc_cs_programmin/ 3月にXPS M1210にUbuntu 9.10を入れたばかりではあるが4月末にUbuntu 10.04 LTSがリリースされて各所でその完成度の高さが謳われていたのでタイミングを見計らってアップグレードしてみた。9.10からは10.04LTSに直接アップグレードが可能。 今回はアップデートマネジャーの指示に従いポチポチボタンを押しただけ。 so easy, so goodだよ。 Ubuntu 10.04 LTSリリースノート Ubuntu 10.04 LTSへアップグレードを行うには http://yk55.com/blog/2010/06/03/upgraded_to_ubuntu1004lts/ イベント駆動型処理フレームワークの定番？であるlibevent(An event notification library)とAPR(Apache ProtableRuntime)を使ってイベント駆動型HTTPサーバを書いてみた。既にこの手の簡易HTTPサーバは書き尽くされてる感があり何ら目新しさはなく、若干車輪の再開発的なものになってしまっているのは否めないがそこは気にしないでlibeventが提供するイベント駆動型HTTP処理機能（evhttp）のサンプルの1つとして読んでいただきたく。ちなみにAPRは主にメモリプールのために使っている。 ソースコード - vs_httpd.c http://github.com/yokawasa/vs_httpd/ http://github.com/yokawasa/vs_httpd/blob/master/vs_httpd.c イベント駆動HTTP処理基本コード main @ vs_httpd.c struct evhttp *httpd; /* event driven http */ event_init(); httpd = evhttp_start(g_config->svr_addr, g_config->svr_port); evhttp_set_gencb(httpd, main_request_handler, NULL); event_dispatch(); evhttp_free(httpd); event_initでlibeventライブラリの初期化処理。event_base_new()でもOK evhttp_start(address, port)でbindするアドレス、listenするポートを指定 evhttp_set_gencbでリクエストイベントが通知される度にコールされるコールバック関数(main_request_handler)を登録。 event_dispatchでイベントループを開始しイベント通知を開始 evhttp_freeで作成されたHTTPサーバリソースを開放 [evhttp_set_gencbの定義 @ evhttp.h] /** Set a callback for all requests that are not caught by specific callbacks */ void evhttp_set_gencb(struct evhttp *, void (*)(struct evhttp_request *, void *), ... http://yk55.com/blog/2010/04/30/eventdriven_http_server_vs_httpd/ cURLのC APIマニュアルを読んでいたらCURLMOPT_PIPELININGというおもしろそうなオプションを見つけた。これはlibcurl 7.16.0 より加わった並列実行用Multiインターフェースのオプションで、設定することでHTTP Pipeliningなリクエストが送信できるようになる。HTTP Pipeliningとは個々のレスポンスを待つことなく複数のリクエストを投げることを意味するHTTP/1.1よりサポートされた通信パフォーマンス向上のためのテクニックである。 通常N個のリクエストを処理する際はN個ソケットがオープンされOPEN → REQUEST → RESPONSE → CLOSEなサイクルがN回行われる。Multiインターフェースによる並列処理の場合はOPEN → REQUEST → RESPONSE → CLOSEが並列に行われる。 またこれがkeep-aliveな接続であればOPEN → (REQUEST → RESPONSE) x N → CLOSEのようにクローズされるまで１ソケットが再利用される。 そしてHTTP Pipeliningはkeep-aliveな接続で使うテクニックであり、これが有効な場合は1ソケットオープン後にOPEN → (REQUEST x N) → (RESPONSE x N) → CLOSEのようにリクエストN個をレスポンスを待つことなく1ソケットに書き込むことができる。 まとめて送信される分パケット効率がアップし全体的なネットワークを流れるパケットの数を減らすことができ、 さらにまとめてリクエスト送信するので高レイテンシーなネットワークにおいては速度面で効果的といえる。 see also 「Mozilla HTTP/1.1 パイプライン化 FAQ」。 (1) NOT keep-alive, single ... http://yk55.com/blog/2010/04/20/curl_multi_http_pipelining_reques/ Vista on Dell XPS M1210（CeleronM,1GMEM）というサイテーに遅いOSの上でvmwareやcolinuxを通じてLinuxを動かしているとそのあまりの遅さに端末を捨ててしまいたくなる衝動にかられていた。なのでたまにTV見ながら膝上に乗せて遊んであげていたけどその遅さ故に使うことが憚られその存在は忘れがちに。 そこで試しに入れてみたUbuntu 9.10。 デュアルブートではなく男らしくフルUbuntu。 Hibernateも問題なく動作しているしサクサク動いて快適。 よみがえったよXPS M1210。 http://yk55.com/blog/2010/03/27/ubuntu910_on_my_dell_xpsm1210/ Boehm GCはガベージコレクションの標準実装がないC/C++でガベージコレクションのようなことを実現可能にしてくれるライブラリ。 一度確保されたリソースは明示的に解放処理が行われない限りメモリリークが発生してしまうけれどもBoehm GCで用意されている関数群（通常はGC_MALLOC）を使ってリソースを確保すれば不要になった段階で自動的に解放してくれる。 ソースコード全体で統一してこのライブラリを利用していればオブジェクトの寿命管理の手間は減るだろうし自分がコードの責任者であるならば難しいところを枯れたライブラリにお任せできるので安心感はあるのだろう。ちなみにこのライブラリ、以前からその存在は知ってはいたけれどスマートポインタ派の自分としてはオブジェクトの寿命管理のためにこれを使うモチベーションはいまいち感じられない。 そんなBoehm GCは「Using the Garbage Collector as Leak Detector」で紹介されているようにメモリリーク検知用ユーティリティとしても使える。ドキュメントやソースコードを覗いてみて少し工夫すれば手軽に既存のコードに殆ど手を加えること無くメモリリークの検知ができそうだったので試しにサンプルコードを書いてみた。以下、Boehm GCのインストールからC/C++コードでのメモリリーク検知について。 Boehm GCインストール まずは自分の環境(debina5.0.1"lenny")にBoehm GCをインストールしてみる。 Boehm GCライブラリをつかって開発するにはlibgc-devとlibgc1c2が必要。もし自分の環境に合うパッケージが存在しない場合は直接ここから tar.gzボールをダウンロードして例のconfigure、make、make install。 $ sudo apt-get install libgc-dev $ sudo apt-get install libgc1c2 $ dpkg --list |grep libgc ii libgc-dev ... http://yk55.com/blog/2010/03/25/boehm_gc_detect_memory_leak/ システムのオペレーションをやっているとスラッシングが原因でサーバが一時的にサービス提供不能になっていまうなんてことがたまにある。スラッシングとは、例えば大量の処理リクエストが発生してしまい利用可能な物理メモリ量を大きく超えてしまった場合に起ったりする。OSのメモリ割り当て処理（ページアウト・イン）が追いつかないため全体のパフォーマンスが極端に低下、最悪固まってしまいlsすらできなくなる。この記事のタイトルにあるページ置換アルゴリズム（Page Replacement Algorithm）はこのページ割り当てを効率的に行うためのアルゴリズム群のことでどれを選択するかによってパフォーマンスが大きく左右される。ちなみにこのアルゴリズム群はページに限らずキャッシュやメモリプールなど限られたリソースを効率的に割り当てる場合には必ずといっていいくらい登場するものなのでプログラマとしては是非とも押さえておきたいところ。 前置きが少し長くなってきたのでここらで本題に入る。ページ置換アルゴリズムを調べていたときにumassの教材として作られたであろう置換アルゴリズムのシュミレーションツールを見つけた。JavaScript版とJava Applet版の2つ。アルゴリズム学習者にとっては目で見て挙動が確認できるので便利なはず。 これ見て自分もなんとなく作ってみたくなったので勉強がてらにcで作ってみた。もちろんCUI。アルゴリズムはLRU、FIFO、OPTIMALの3つに絞った。これがc版ページ置換アルゴリズムシュミレーションツール。 http://github.com/yokawasa/any/raw/master/page_rep_algos/page_rep_algos.c 内容は、見つけたツールと同じで物理メモリのページ・フレームの数、置換アルゴリズム、そして今後メモリ割り当ての必要なページ番号の数列を指定して順番にそのページ番号に対して物理メモリの割り当てを行うといったもの。利用ページ番号が既に物理メモリの割り当てが既にされていればHit、されていなければMiss（ページフォルト発生）として過去に割り当てたページの置き換えを行い、最終的なページフォールト発生数とHit率を出力する。 以下、ツールのコンパイルとその使い方、そして各アルゴリズムの挙動をツールの実行結果とあわせて説明する。 ツールのコンパイルとその使い方 上記URLからソースコードを取得してからコンパイルを行う。 gcc -o page_rep_algos page_rep_algos.c 使い方はアルゴリズム、アクセスするページ番号の数列、ページフレーム数の3つのオプションを次のように指定。 ./page_rep_algos [options] Options are: -a LRU, FIFO または OPTIMAL -p Page # sequences in which the pages are accessed by some program ... http://yk55.com/blog/2010/03/13/page_replacement_algo_simulation/ 一度誤った投稿をしてしまいそれがGoogle Reader Cacheに保存されてしまうと削除は難しいようだ（参照 Google Reader FAQ: Deleted posts in my blog's feed）。仮にその記事を削除したとしても同じ。というわけでいきなりこの記事のタイトル「Google Reader CacheからItemを削除する方法」はできないということになる。ただ、FAQでコメントされているように、どうしてもCacheから削除したい場合、削除はできないがアップデートはできるという特性を活かしダミー記事Itemでリプレースするという方法がある。Itemはguidをキーとして認識する。よって同一guidのダミーItemを用意しそいつでリプレースをかけることで何とか取り繕うことができる。 まずは誤って投稿した記事ItemがCacheされてしまった様子。タイトル・コンテンツともに空にもかかわらずキャッシュされてしまっている。仮にこのItemのguidがhttp://yk55.com/blog/?p=200とする。この誤ってキャッシュされてしまったItemを別の何かでリプレースするためのダミー記事を用意する。もちろんその記事には同一guidを指定してやる。 [dummy] Google Reader CacheからItemを削除する方法 http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/ http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/#comments Sat, 27 Feb 2010 14:55:05 +0000 yoichi http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/ たまにc++コードのコンパイル時にエラー文言でvtableというキーワードを見たことはないだろうか？Polymorphismという有名なワードに対しこのvtableはあまりにも目立たない存在だ。とはいえPolymorphismを実現するためになくてはならない（最）重要なポジションを占めているのがvtable。別にvtableを理解しなくともPolymorphismの理解はできる。 ただし、骨太になりたいのならばPolymorphismを実現するためにどのようにvtableが使われているのかを理解しておくべきである。 UPCASTING Virtual関数との比較のためにVirtual関数を持たないクラス継承を説明する。以下のようにvirtual関数を持たないSuperClassをSubClassが継承する。 SuperClassを継承したSubClassの参照をSuperClassポインタ変数に入れた場合は、子クラスへの参照がUPCASTされ親クラスへの参照として扱われる。実行結果はSuperClassへの参照へとUPCASTされるのでSuperClassの関数の内容が表示される。 #include using std::cout; using std::endl; class SuperClass { public: void func() { cout http://yk55.com/blog/2010/02/27/dynamic-binding-vtable-concept/