Yoichi Kawasaki blog

AWK HTTPサーバ

yoichi — Mon, 28 Jun 2010 23:04:02 +0000

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 |& getline reqline) > 0) {
request_handler(http_service, reqline, docroot);
}
close(http_service);
}
}

function request_handler(http_service,reqline, docroot) {
# parse request line
if ( split(reqline, t, " ") !=3 ) {
show_error(http_service, 400, "Bad Request");
return 1;
}
req_method = t[1];
req_uri = (index(t[2], "/")==1) ? substr(t[2],2) : t[2];
if (req_method != "GET" ) {
show_error(http_service, 405, "Method Not Allowed");
return 1;
}
# set path and query string
path = docroot req_uri;
n = split(path,tt,"?");
if (n >=2 ) {
path = tt[1];
ENVIRON["QUERY_STRING"] = tt[2];
}
# path should end with "/" if it's directory.
if(dir_exists(path)) {
if (substr(path,length(path)) != "/") {
path = path "/";
}
# set default file
path = path "index.html";
}

# check if file exists
if (!file_exists(path)) {
show_error(http_service, 404, "Not Found");
return 1;
}
show_page(http_service, path);
return 0;
}

function file_exists(path) {
cmd ="if [ -f " path " ]; then echo OK; fi";
exist = 0;
if ( (cmd |getline res) > 0) {
gsub("\n","", res);
if (res == "OK") {
exist = 1;
}
}
close(cmd);
return exist;
}

function dir_exists(path) {
cmd ="if [ -d " path " ]; then echo OK; fi";
exist = 0;
if ( (cmd |getline res) > 0) {
gsub("\n","", res);
if (res == "OK") {
exist = 1;
}
}
close(cmd);
return exist;
}

function file_read(file) {
buf = "";
while (getline < file > 0) {
buf = buf $0;
}
close(file);
return buf;
}

function find_mime_type(path) {
mime_type = "application/ocet-stream"; # default mime type
n = split(path, t, "/");
if (n >=2 ) {
filename = t[n];
m = split(filename, tt, ".");
if (m >=2 ) {
ext = tolower(tt[m]);
if (ext == "html" || ext == "htm") {
mime_type = "text/html";
}else if (ext == "css" ) {
mime_type = "text/css";
}else if (ext == "txt" || ext == "text" ) {
mime_type = "text/plain";
}
}
}
return mime_type;
}

function show_page( http_service,path) {
outbuf = file_read(path);
mime_type = find_mime_type(path);
content_len = length(buf);
print_output(http_service,200,"OK",outbuf,mime_type,content_len);
}

function show_error( http_service, errcode, reason) {
outbuf = "

" reason "

";
mime_type = "text/html";
content_len = length(buf);
print_output(http_service,errcode,reason,outbuf,mime_type,content_len);
}

function print_output( http_service,code,reason,outbuf,mime_type,content_len) {
print "HTTP/1.x " code " " reason |& http_service;
print "Content-type: " mime_type |& http_service;
print "Content-Length: " content_len |& http_service;
print "" |& http_service;
print outbuf |& http_service;
}

このプログラムの肝はgawkネットワーク接続用ファイル表記/inet/～でTCP/IPネットワーク接続の利用を宣言しhttp_service変数に格納、 ‘|&’ オペレータでINPUTとOUTPUTの2方向のネットワーク接続パイプを作成し、ネットワーク接続パイプラインからのINPUT内容は” http_service |& getline’ で受けとり、 OUTPUT内容は ‘ print “書き込む内容” |& http_service’ で書き込む。これに尽きる。

あと、残念なことにAWKはバイナリーデータが扱えない。よってHTTPサーバとしては致命的ではあるが画像やその他メディアファイルの表示をすることができない。このHTTPサーバでは .htm、.html、.css、.txtファイルに対してはそれぞれMIMEタイプを’text/html’、’text/css’、’text/plain’としているがそれ以外のファイルタイプに対しては一律’application/ocet-stream’としている。

サーバ起動、サンプルページの表示

git clone でソースコードを取得する。リポジトリanyのサブディレクトリ any/awk_httpdが今回のサンプルにあたる。そして取得したhttpd.awkをgawkのファイル指定で実行する。gawkのパスが/usr/bin/gawkな場合は直接 ./httpd.awkで実行すればよい。 httpd.awkはデフォルトでポートが8080、ドキュメントルートが”./”となっている。ちなみに同一ディレクトリにポートとドキュメントルートのオプション指定ができるhttpd.igawkを用意している。これを使用するには実行環境にigawkシェルスクリプトがインストールされている必要がある。

$ git clone git@github.com:yokawasa/any.git
Initialized empty Git repository in /home/m/dev/github/t/any/.git/
remote: Counting objects: 45, done.
remote: Compressing objects: 100% (44/44), done.
remote: Total 45 (delta 11), reused 0 (delta 0)
Receiving objects: 100% (45/45), 13.99 KiB, done.
Resolving deltas: 100% (11/11), done

$ cd any/awk_httpd

$ ls -1
httpd.awk
httpd.igawk
pages

$ gawk -f ./httpd.awk

ページ表示テスト用にany/awk_httpd/pages下にhtml、cssファイルを用意してあるのでこれらを/home/awk_httpd/pages配下に配置して実際にブラウザでindex.htmlを表示させてみる。成功すると以下のようなページが表示される。

おわり。

LibeventのRPCフレームワークによるC/Sプログラミング

yoichi — Sat, 05 Jun 2010 14:49:21 +0000

前回の投稿では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] 構造体
- array typeで指定されたデータ型のベクター。 typeはstring, bytes, int, または struct[structname]

変数名
インデックス番号。フィールド番号。

[optional] typeの前にoptionalを指定するとリクエスト、レスポンス処理時にそのフィールドへのデータセットを省略することができる。

※ 定義ファイルの拡張子は.rpcである必要がある
※ との間は１半角スペースずつを開ける。そうでない場合はevent_rpcgen.pyによるジェネレートが失敗するので要注意！
× int errcode =1;
× int errcode = 1;
× int errcode=1;
○ int errcode = 1

今回のサンプルで使用するデータ構造を定義する。サンプルはユーザ情報を取得するRPCでありユーザ情報取得のためのリクエスト、レスポンス用データ構造が以下のGetUserRequest、GetUserResponse。

サンプルデータ構造の定義フォーマットファイル – simple.rpc

struct GetUserRequest {
string id = 1;
}

struct GetUserResponse {
int errcode = 1;
optional string name = 2;
optional string email = 3;
}

これを次のようにevent_rpcgen.pyを使ってデータ構造定義からコードをジェネレートする。 event_rpcgen.pyはlibeventをインストールするとデフォルトで/usr/local/bin/配下にコピーされる。

$ /usr/local/bin/event_rpcgen.py simple.rpc

Reading "./simple.rpc"
Created struct: GetUserRequest
Added entry: id
Created struct: GetUserResponse
Added entry: errcode
Added entry: name
Added entry: email
... creating "./simple.gen.h"
... creating "./simple.gen.c"

simple.gen.hとsimple.gen.cの2つのファイルがジェネレートされる。 C/S両方でこのデータ構造を使用する。

RPCサーバの実装 – simple_rpc_server.cpp

http://github.com/yokawasa/any/blob/master/libevent_rpc/simple_rpc_server.cpp

まずは利用するRPCメソッドの登録を行う。 EVRPC_HEADERでRPCコマンドのデータ構造とプロトタイプを作成してEVRPC＿GENERATEでRPCメッセージを送受信するためのコードを作成する。

#ifdef __cplusplus
extern "C" {
#endif
#include "simple.gen.h"
#ifdef __cplusplus
}
#endif
#include "evrpc.h"

/* registe RPC : GetUser */
EVRPC_HEADER(GetUser, GetUserRequest, GetUserResponse);
/* generate RPC code : GetUser */
EVRPC_GENERATE(GetUser, GetUserRequest, GetUserResponse);

RPCサーバの実装について説明する。実装は既に存在するHTTPサーバの実装をベースとする。RPCサーバの基本コードは以下の通り。

int main(int argc, char **argv) {
if (argc < 3) {
fprintf(stdout, "%s \n", argv[0]);
return 1;
}
char *svr_addr = argv[1];
short svr_port = atoi(argv[2]);

struct evhttp *ev_http = NULL;
struct evrpc_base *rpc_base = NULL;

/* initialize base event mechanism */
event_init();
ev_http = evhttp_start(svr_addr, svr_port);
/* create a base for the RPC protocol */
rpc_base = evrpc_init(ev_http);

/* register all of the handlers for all RPCs */
EVRPC_REGISTER(rpc_base, GetUser, GetUserRequest, GetUserResponse, GetUserCallback, NULL);

/* loop and dispatch events */
event_dispatch();

EVRPC_UNREGISTER(rpc_base, GetUser);
evrpc_free(rpc_base);
evhttp_free(ev_http);
return 0;
}

event_init()でlibeventライブラリ初期化。とりあえずlibeventを使う際は最初に一度実行しておく。
evhttp_start(svr_addr, svr_port)にサーバアドレス、ポートを指定してHTTPサーバ処理開始準備。
evrpc_init()でrpc処理ハンドル用ポインタを作成。
EVRPC_REGISTERで特定のRPCコマンドをサーバに登録する。ここではさきほどEVRPC_HEADERとEVRPC_GENERATEで登録されたRPCコマンドGetUser（リクエスト用データ構造GetUserRequest, レスポンス用データ構造GetUserResponse）をRPCサーバに登録する。また同時にGetUserCallbackというRPCリクエストを受け取った際に呼び出されるコールバック関数を登録する。GetUserCallbackは次で説明する。
event_dispatch()でloop開始しイベントdispatchを開始する。
後処理。サーバ処理を終えるときEVRPC_UNREGISTER、evrpc_free, evhttp_freeの順で後処理をする。

GetUserCallbackはさきほどEVRPC_REGISTERでサーバに登録されたRPCコマンドのコールバック関数。 RPCクライアントから送信されるリクエストデータからidを取得。そのidに対するnameとemailデータをレスポンスデータにセットしている。

static void
GetUserCallback(EVRPC_STRUCT(GetUser)* rpc, void *arg)
{
struct GetUserRequest* req = rpc->request;
struct GetUserResponse* res = rpc->reply;

/* get request info */
char *id;
if(!EVTAG_HAS(req, id)) {
fprintf(stderr, "failed to get request info\n");
EVTAG_ASSIGN(res, errcode, -1);
}
EVTAG_GET(req, id, &id);
fprintf(stdout, "REQUEST id = %s\n", id);

/* do somthing due to request info */
/* set response info */
EVTAG_ASSIGN(res, errcode, 0);
EVTAG_ASSIGN(res, name, "Fooo Baaar");
EVTAG_ASSIGN(res, email, "baz@foo.bar");

/* send the reply to the RPC */
EVRPC_REQUEST_DONE(rpc);
}

EVTAG_HASでリクエストデータ構造中のあるフィールドにデータがセットされているかをチェック(ここではid)してEVTAG_GETで実際にそのフィールドデータを取得。
EVTAG_ASSIGNでレスポンスデータ構造のフィールド(ここではerrcode, name, email)にデータをセット。
EVRPC_REQUEST_DONEでレスポンス送信。

RPCクライアントの実装 – simple_rpc_client.cpp

http://github.com/yokawasa/any/blob/master/libevent_rpc/simple_rpc_client.cpp

RPCクライアントの実装について説明する。RPCクライアントでもサーバと同じようにEVRPC_HEADERとEVRPC＿GENERATEとで利用するRPCメソッドの登録を行う。以下RPCクライアントの基本コード。

int main(int argc, char **argv) {
if (argc < 3) {
fprintf(stdout, "%s \n", argv[0]);
return 1;
}
char *svr_addr = argv[1];
short svr_port = atoi(argv[2]);
struct event_base *ev_base = NULL;
struct evhttp *ev_http = NULL;
struct evrpc_base *rpc_base = NULL;
struct evrpc_pool *rpc_pool = NULL;
struct GetUserRequest *req;
struct GetUserResponse *res;

/* initialize base event mechanism */
ev_base = event_init();
/* initialize http internal buffer */
ev_http = evhttp_new(ev_base);
/* create a base for the RPC protocol */
rpc_base = evrpc_init(ev_http);

rpc_pool = get_rpc_pool(ev_base, svr_addr, svr_port);
if(!rpc_pool) {
return -1;
}
/* set up request data */
req = GetUserRequest_new();
EVTAG_ASSIGN(req, id, "foobar");

/* create a response structure */
res = GetUserResponse_new();
/* set request, response, callback func */
EVRPC_MAKE_REQUEST(GetUser, rpc_pool, req, res, GetUserCallback, NULL);
/* process request and response */
event_dispatch();

GetUserRequest_free(req);
GetUserResponse_free(res);

evrpc_pool_free(rpc_pool);
evrpc_free(rpc_base);
evhttp_free(ev_http);
return 0;
}

event_init()でlibeventライブラリ初期化。
evhttp_new()でhttp処理用内部バッファーを初期化。
evrpc_init()でrpc処理ハンドル用ポインタを作成。
get_rpc_pool()よりevrpc_poolポインタを取得。get_rpc_pool()は次で説明。 evrpc_poolは内部にリクエストとして送信するための接続ポインタ(evhttp_connection)を持っている。
GetUserRequest_new()とGetUserResponse_new()によりRPCリクエストとレスポンスのためのリソース確保。
EVTAG_ASSIGNによりリクエスト用データ構造のidフィールドに値(”foobar”)を設定。
EVRPC_MAKE_REQUESTでサーバへのリクエスト送信に使うRPCコマンドとリクエスト、レスポンスオブジェクトポインタ、evrpc_poolポインタ、コールバック関数をセットする。コールバック関数GetUserCallbackは後で説明する。
event_dispatch()を呼んで実際にリクエスト送信、レスポンス受信を行う。
後処理。GetUserRequest_free()、GetUserResponse_free()でそれぞれリクエストとレスポンスのために確保されたリソースを開放。次にevrpc_pool_free、evrpc_free, evhttp_freeの順で後処理実行。

RPCリクエスト処理で使用するevrpc_poolポインタを取得するための関数。get_rpc_poolがコールされる度にサーバ接続ポインタ (evhttp_connection)を生成しevrpc_poolの接続プールに追加している。ちなみにevrpc_poolとはいわゆるコネクションプールのこと。仕組みとしては内部に接続とリクエストを管理するQUEUEを持っていてリクエストごとに接続QUEUEから空いている接続をリクエストに割り当てる。もし割り当てる接続がなければそのリクエストをリクエストQUEUEに追加する。

static struct evrpc_pool *
get_rpc_pool(struct event_base *base, const char *svr_addr, short svr_port)
{
struct evhttp_connection *ev_conn;
struct evrpc_pool *rpc_pool;
rpc_pool = evrpc_pool_new(base);
if (!rpc_pool) {
fprintf(stderr, "failed to get new rpc pool\n");
return NULL;
}
// create a connection to RPC server
ev_conn = evhttp_connection_new(svr_addr, svr_port);
if (!ev_conn) {
fprintf(stderr, "failed to get new evhttp connection: %s:%d\n",
svr_addr, svr_port);
return NULL;
}
// add request connection in the pool
evrpc_pool_add_connection(rpc_pool, ev_conn);
return (rpc_pool);
}

evrpc_pool_new()でrpcコネクションプールを作成。
evhttp_connection_newでリクエスト用接続ポインタを生成。
evrpc_pool_add_connectionでevrpc_poolの接続プールに生成されたリクエスト用接続ポインタを追加。

以下EVRPC_MAKE_REQUESTで指定するRPCリクエストを送信してサーバよりレスポンスが返ってきたときに呼ばれるコールバック関数。RPC クライアントからのリクエストに対するサーバからのレスポンス結果を表示している。

static void
GetUserCallback(struct evrpc_status *status,
struct GetUserRequest *req, struct GetUserResponse *res, void *arg)
{
uint32_t errcode;
char *name,*email;
/* check return status */
if (status->error != EVRPC_STATUS_ERR_NONE) {
goto exitloop;
}
/* get response info */
EVTAG_GET(res, errcode, &errcode);
fprintf(stdout, "RESPONSE errcode=%d\n", errcode);
if(EVTAG_HAS(res, name) ) {
EVTAG_GET(res, name, &name);
fprintf(stdout, "RESPONSE name=%s\n", name);
}
if(EVTAG_HAS(res, email) ) {
EVTAG_GET(res, email, &email);
fprintf(stdout, "RESPONSE email=%s\n", email);
}
exitloop:
event_loopexit(NULL);
}

ダウンロード、コンパイル、動作確認

git clone でソースコードを取得してmakeを行う。リポジトリanyのサブディレクトリ any/libevent_rpcが今回のサンプルにあたる。

$ git clone git@github.com:yokawasa/any.git

Initialized empty Git repository in /home/m/dev/github/any/.git/
remote: Counting objects: 33, done.
remote: Compressing objects: 100% (32/32), done.
remote: Total 33 (delta 7), reused 0 (delta 0)
Receiving objects: 100% (33/33), 11.28 KiB, done.
Resolving deltas: 100% (7/7), done.

$ cd any/libevent_rpc
$ make

g++ -I/usr/include -I/usr/local/include -Wall -g -o simple_rpc_client.o -c simple_rpc_client.cpp
gcc -I/usr/include -I/usr/local/include -Wall -g -o simple.gen.o -c simple.gen.c
g++ -L/usr/local/lib -levent -o simple_rpc_client simple_rpc_client.o simple.gen.o
g++ -I/usr/include -I/usr/local/include -Wall -g -o simple_rpc_server.o -c simple_rpc_server.cpp
g++ -L/usr/local/lib -levent -o simple_rpc_server simple_rpc_server.o simple.gen.o

これで同ディレクトリにRPCサーバsimple_rpc_server とRPCクライアントsimple_rpc_client実行ファイルのできあがり。simple_rpc_server 、simple_rpc_clientともに実行時に第一引数にサーバアドレス、第二引数にIOポートを指定する。まずサーバから立ち上げる。

$ ./simple_rpc_server localhost 8888

サーバが立ち上がったら次のようにクライアントからリクエスト送信する。

$ ./simple_rpc_client localhost 8888
RESPONSE errcode=0
RESPONSE name=Fooo Baaar
RESPONSE email=baz@foo.bar

上のような結果が出力されればOK。

おわり。

Upgraded to Ubuntu 10.04 LTS

yoichi — Thu, 03 Jun 2010 11:24:20 +0000

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へアップグレードを行うには

LibeventとAPRでイベント駆動型HTTPサーバを作成してみた

yoichi — Fri, 30 Apr 2010 01:35:25 +0000

イベント駆動型処理フレームワークの定番？である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 *), void *);

リクエスト処理用コールバック関数 main_request_handler @ vs_httpd.c

void main_request_handler(struct evhttp_request *r, void *args)
{
apr_status_t rv;
struct evbuffer *evbuf;
const char *path, *mimetype;
char *complemented_path, *extbuf, *filebuf;
int filesize = 0;

/* check reqeust type. currently only suppoert GET */
if (r->type != EVHTTP_REQ_GET) {
fprintf(stdout, "only support GET request \n");
evhttp_send_error(r, HTTP_BADREQUEST, "only support GET request");
return;
}
path = apr_psprintf(g_mem_pool, "%s%s",
g_config->doc_root, evhttp_request_uri(r));
if(g_config->verbose) {
fprintf(stderr, "req uri=%s\n", evhttp_request_uri(r) );
fprintf(stderr, "req path=%s\n", path );
}
/* file or dir existence check */
if (!exists(path, &complemented_path, &filesize)) {
evhttp_send_error(r, HTTP_NOTFOUND, "file not found");
return;
}
/* file's extension check */
mimetype = apr_pstrdup(g_mem_pool, DEFAULT_MIME_TYPE);
extbuf = strrchr(complemented_path,'.');
if (extbuf) {
++extbuf;
mimetype = find_mime_type(extbuf);
}
/* file read */
filebuf = apr_palloc(g_mem_pool, filesize + 1);
apr_file_t *file = NULL;
rv = apr_file_open(&file, complemented_path,
APR_READ|APR_BINARY, APR_OS_DEFAULT, g_mem_pool);
if (rv != APR_SUCCESS) {
evhttp_send_error(r, HTTP_SERVUNAVAIL, "failed to open file");
return;
}
apr_size_t len = filesize;
rv = apr_file_read(file, filebuf, &len);
if (rv != APR_SUCCESS) {
evhttp_send_error(r, HTTP_SERVUNAVAIL, "failed to read file");
return;
}
apr_file_close(file);

if(g_config->verbose) {
fprintf(stderr, "res mimetype=%s\n", mimetype);
fprintf(stderr, "res file size=%d\n", len);
fprintf(stderr, "res file output=%s\n", filebuf);
}

evbuf = evbuffer_new();
if (!evbuf) {
fprintf(stderr, "failed to create response buffer\n");
evhttp_send_error(r, HTTP_SERVUNAVAIL, "failed to create response buffer");
return;
}
evhttp_add_header(r->output_headers, "Content-Type",mimetype);
evhttp_add_header(r->output_headers, "Content-Length", apr_psprintf(g_mem_pool,"%d",filesize));
evbuffer_add(evbuf, filebuf, len);
evhttp_send_reply(r, HTTP_OK, "", evbuf);
evbuffer_free(evbuf);
}

GETメソッド(EVHTTP_REQ_GET)のみ処理を行う
exists()でリクエストされたuri(evhttp_request_uri(r))がファイルまたはディレクトリとして存在するかをチェック
find_mime_typeでファイル拡張子に対応するMIME TYPEを取得。拡張子がなければデフォルトMIME TYPE application/ocet-stream。この部分の処理は600 行のCでCGIをサポートする軽量WEBサーバmattowsのコードを参考、流用。
APRのファイルI/Oハンドルライブラリでファイルの読み込み。画像等バイナリファイルのためにopen時にAPR_BINARYフラグを指定している
evhttp_add_headerでレスポンス用outputヘッダに”Content-Type”と”Content-Lenght”を指定
(struct evbuffe*)evbufに読み込んだファイルデータをボディデータとして書き込む
evhttp_send_replyでクライアントにレスポンス

APRメモリプールの利用 @ vs_httpd.c
これは本題からそれるが全体的な特徴としてメモリ管理はAPRのメモリプールを利用しているのでここで軽く説明する。

static apr_pool_t *g_mem_pool = NULL;
apr_pool_create(&g_mem_pool, NULL);
...
g_config = apr_pcalloc(g_mem_pool, sizeof(httpsvr_config));
path = apr_psprintf(g_mem_pool, "%s%s", g_config->doc_root, evhttp_request_uri(r));
mimetype = apr_pstrdup(g_mem_pool, DEFAULT_MIME_TYPE);
filebuf = apr_palloc(g_mem_pool, filesize + 1);
rv = apr_file_open(&file, complemented_path, APR_READ|APR_BINARY, APR_OS_DEFAULT, g_mem_pool);
...
apr_pool_destroy(g_mem_pool);

apr_pool_createでメモリプールの作成
apr_palloc、apr_psprintf, を使用して、メモリプールからメモリを確保します
apr_pool_destroyを使用して、メモリプールを破棄

ダウンロード、コンパイル、そしてテスト

git clone でvs_httpdのコードを取得(リポジトリ複製)する。

$ git clone git@github.com:yokawasa/vs_httpd.git

Initialized empty Git repository in /home/m/dev/github/t/vs_httpd/.git/
remote: Counting objects: 11, done.
remote: Compressing objects: 100% (11/11), done.
remote: Total 11 (delta 0), reused 0 (delta 0)
Receiving objects: 100% (11/11), 8.51 KiB, done.

libeventとaprヘッダへのインクルードや両ライブラリのリンクができるようにMakefileのパス調整を行う。もちろんlibeventとaprがインストール済みであることが前提。もしまだならばまずはlibeventとaprをインストールしましょ。

$ vi Makefile
CFLAGS = -I -I LIBS = -L -levent -L -lapr-1

パス変更後にmakeを実行。これでvs_httpdバイナリの出来上がり。vs_httpdの使い方は次のとおり。

$ ./vs_httpd -h
Usage: vs_httpd [-a address] [-p port] [-d documentroot]
[-D] [-v] [-h]
Options:
-a address : define server address (default: "0.0.0.0")
-p port : define server port (default: 8080)
-d documentroot : define document root (default: "./")
-D : daemonize option 0-off,1-on (default: 0)
-v : verbose option 0-off,1-on (default: 0)
-h : list available command line options (this page)

使い方の説明にあるようにオプションを指定しない場合はデフォルトサーバアドレス”0.0.0.0″、ポート番号 8080、ドキュメントルート “./”、デーモンモードOFF、VerboseモードOFFで起動される。尚、デフォルトインデックスファイルをindex.htmlとしているので http://hostname:port/path/のようにファイル名を指定しないでアクセスした場合はvs_httpdがドキュメントルート /path/配下のindex.htmlを表示させようとする。試しにvs_httpdをポート(8888)、ドキュメントルート(/home /vs_httpd/docs)、デーモンモードON、VerboseモードONで起動させてみる。

$ ./vs_httpd -p 8888 -d /home/vs_httpd/docs -D -v
svr_addr=0.0.0.0
svr_port=8888
doc_root=/home/vs_httpd/docs
verbose=1
daemonize=1
$ ※

※ daemonized! fork成功、親プロセスからはexitで子プロセスに処理が移る

ページ表示テスト用にvs_httpd/pages下にhtml、css、jpegファイルを用意してあるのでこれらを/home/vs_httpd /docs配下に配置して実際にブラウザでindex.htmlを表示させてみる。成功すると以下のようなページが表示させる。

ベンチマーク結果

ab(apache bench)でベンチマークテストをしてみる。並列数100、リクエスト数10000。比較のためにapache2(mpm prefork)でもテストをしてみる。まずはvs_httpdのテスト結果。

$ ab -c 100 -n 10000 http://127.0.0.1:8888/

Server Software:
Server Hostname: 127.0.0.1
Server Port: 8888

Document Path: /
Document Length: 285 bytes

Concurrency Level: 100
Time taken for tests: 2.295104 seconds
Complete requests: 10000
Failed requests: 0
Write errors: 0
Total transferred: 3490440 bytes
HTML transferred: 2858550 bytes
Requests per second: 4357.10 [#/sec] (mean)
Time per request: 22.951 [ms] (mean)
Time per request: 0.230 [ms] (mean, across all concurrent requests)
Transfer rate: 1484.90 [Kbytes/sec] received

Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 5 4.2 4 27
Processing: 5 17 6.4 15 46
Waiting: 1 13 6.5 11 45
Total: 10 22 7.0 21 47

Percentage of the requests served within a certain time (ms)
50% 21
66% 24
75% 26
80% 27
90% 32
95% 37
98% 41
99% 42
100% 47 (longest request)

次にapache2(mpm prefork)でも同様のテストを行う。利用するページはvs_httpdと同じでテスト環境のprefork MPM設定値は次のとおり。

[prefork MPMの設定値]
StartServers          5
MinSpareServers       5
MaxSpareServers      10
MaxClients          150
MaxRequestsPerChild   0

以下、apache2のテスト結果。

$ ab -c 100 -n 10000 http://127.0.0.1/

Server Software: Apache/2.2.2
Server Hostname: 127.0.0.1
Server Port: 80

Document Path: /
Document Length: 285 bytes

Concurrency Level: 100
Time taken for tests: 3.580232 seconds
Complete requests: 10000
Failed requests: 0
Write errors: 0
Total transferred: 5310000 bytes
HTML transferred: 2850000 bytes
Requests per second: 2793.12 [#/sec] (mean)
Time per request: 35.802 [ms] (mean)
Time per request: 0.358 [ms] (mean, across all concurrent requests)
Transfer rate: 1448.23 [Kbytes/sec] received

Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.8 0 10
Processing: 8 35 7.4 31 66
Waiting: 2 34 7.4 31 66
Total: 12 35 7.4 31 66

Percentage of the requests served within a certain time (ms)
50% 31
66% 36
75% 40
80% 43
90% 47
95% 50
98% 53
99% 54
100% 66 (longest request)

単純すぎるベンチマークテストなのでアレなのですが、10000リクエストの処理時間だけをみるとvs_httpd(2.295104 seconds)のほうがapache2(3.580232 seconds)よりも約35%速いといえる。余計な処理はな何も行わないで静的ファイル処理に特化しているので速いのは当たり前なんだけど、うれしい。この世界、速いは美徳。

おわり。

cURL MultiインターフェースでHTTP Pipeliningリクエストの送信

yoichi — Tue, 20 Apr 2010 14:54:54 +0000

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         (OPEN → REQUEST → RESPONSE → CLOSE) x N
(2) NOT keep-alive, multi          (OPEN → REQUEST → RESPONSE → CLOSE) をN並列で行う
(3) keep-alive                     OPEN → (REQUEST → RESPONSE) x N → CLOSE
(4) keep-alive, Pipelining         OPEN → (REQUEST x N) → (RESPONSE x N) → CLOSE

というわけでいつものようにテストプログラムを作ってMultiインターフェースによる並列処理をHTTP Pipeliningありとなしで実行してみる。
(環境 libcurl-7.19.5、httpd-2.2.2 on Debian-5.0.1 )

テストツールとそのコンパイル

cURL CAPIのMultiインターフェースを使って複数URLからfetchしてくるツールを作成した。

http://github.com/yokawasa/any/blob/master/libcurl/multi_fetch.cpp

標準的なcurl Multiインターフェースを使ったコードであるがポイントは次の部分。各リクエスト用のCURLハンドルでソケットの送信待ち時間を最小限にするCURLOPT_TCP_NODELAYオプション（詳しくは「Linuxにおけるソケット機能の向上」を参照ください）と挙動把握のためにlibcurlのINFO情報を出力するCURLOPT_VERBOSEオプションを有効にしている。またHTTP Pipeliningモード指定のときにMulti用ハンドルでCURLMOPT_PIPELININGオプションを有効にしている。　以下該当箇所のコード断片。

...
for(vector<string>::iterator it=urls.begin();
it!=urls.end(); ++it) {
curl_easy_setopt(c_handles[i], CURLOPT_URL, (*it).c_str());
curl_easy_setopt(c_handles[i], CURLOPT_TCP_NODELAY, 1L);
curl_easy_setopt(c_handles[i], CURLOPT_VERBOSE, 1L);
curl_multi_add_handle(m_handle, c_handles[i]);
i++;
}
if (pipelining)
curl_multi_setopt(m_handle, CURLMOPT_PIPELINING, 1L);
...

上記URLのソースコードを取得して次のようにコンパイルを行う。

g++ multi_fetch.cpp -o multi_fetch -I/usr/include -L/usr/lib -lcurl

使い方は次のように複数URLの書かれたファイルを指定する。-pオプションを加えてやることでHTTP Pipeliningモードでリクエスト送信を行う。これはオプショナル。

Usage: ./multi_fetch
Options: -f file URL list file
-p HTTP pipelining mode (optional)

例) urls.txtに書かれた複数URLからHTTP Pipeliningモードでfetch
$ ./multi_fetch -f urls.txt -p

NON HTTP Pipelining リクエスト送信

テスト用にホストfooとWebサーバ（apache）のあるホストbarを用意する。まずはHTTP Pipeliningオプションをはずした通常のmultiインターフェースによる並列実行を行う。リクエスト用CURLハンドルでCURLOPT_VERBOSEオプションが有効になっているので実行結果にlibcurlのINFO 情報も一緒に出力される。出力内容を全てここに貼り付けるには量が多すぎるので内容を簡略化してHTTP接続部分と各リクエストとそのレスポンスの最初の一行だけに絞る。

$ cat urls.txt
http://bar.yk55.com/test1.html
http://bar.yk55.com/test2.html
http://bar.yk55.com/test3.html
http://bar.yk55.com/test4.html

$ ./multi_fetch -f urls.txt 2>&1 |tee /tmp/nonpipelined.out

[出力結果]
$ cat /tmp/nonpipelined.out

* About to connect() to bar.yk55.com port 80 (#0)
* About to connect() to bar.yk55.com port 80 (#1)
* About to connect() to bar.yk55.com port 80 (#2)
* About to connect() to bar.yk55.com port 80 (#3)
* Connected to bar.yk55.com (192.168.1.5) port 80 (#0)
* Connected to bar.yk55.com (192.168.1.5) port 80 (#1)
* Connected to bar.yk55.com (192.168.1.5) port 80 (#2)
* Connected to bar.yk55.com (192.168.1.5) port 80 (#3)
> GET /test1.html HTTP/1.1
> GET /test2.html HTTP/1.1
> GET /test3.html HTTP/1.1
> GET /test4.html HTTP/1.1
< HTTP/1.1 200 OK
* Connection #1 to host bar.yk55.com left intact
< HTTP/1.1 200 OK
* Connection #2 to host bar.yk55.com left intact
< HTTP/1.1 200 OK
* Connection #3 to host bar.yk55.com left intact
< HTTP/1.1 200 OK
* Connection #0 to host bar.yk55.com left intact

これを見ると並列にConnection #[0-3]の4つのソケットがオープンしてそれぞれにリクエスト、レスポンスが書き出され終了していることが分かる。「(2)NOT keep-alive, multi」のパターンになっているといえる。想定どおり。

HTTP Pipeliningリクエスト送信

次に前テストと同様にホストfooからホストbar(Webサーバ)の4ファイル対してにHTTP Pipeliningなリクエストを送信してみる。

$ cat urls.txt
http://bar.yk55.com/test1.html
http://bar.yk55.com/test2.html
http://bar.yk55.com/test3.html
http://bar.yk55.com/test4.html

$ ./multi_fetch -f urls.txt -p　 2>&1 |tee /tmp/pipelined.out

[出力結果]
$ cat /tmp/pipelined.out

* About to connect() to bar.yk55.com port 80 (#0)
* Re-using existing connection! (#0) with host bar.yk55.com
* Re-using existing connection! (#0) with host bar.yk55.com
* Re-using existing connection! (#0) with host bar.yk55.com
* Connected to bar.yk55.com (192.168.1.5) port 80 (#0)
> GET /test1.html HTTP/1.1
< HTTP/1.1 200 OK
> GET /test2.html HTTP/1.1
> GET /test3.html HTTP/1.1
> GET /test4.html HTTP/1.1
< HTTP/1.1 200 OK
< HTTP/1.1 200 OK
< HTTP/1.1 200 OK
* Connection #0 to host bar.yk55.com left intact

出力結果から、1つのソケットオープン(Connection #0)後に他のリクエスト達はConnectoin#0を再利用しているのが分かる。またtest1.htmlをGETするためのリクエスト送信後に「HTTP/1.1 200 OK….」とレスポンスを受け、次にtest2.html～test4.html GETの3リクエストがレスポンスを待つことなく連続で送られ、その後それらのレスポンスを受けている。「(4) keep-alive, Pipelining」のパターンになると予想していたのだが１つ目のリクエスト（REQUEST-a）だけがPipeliningではない。試しにリクエスト数を増やしてみても同じ、１つ目のリクエストがPipeliningではなく、2番目以降のリクエストはPipeliningになっている。今一理由がわからない。ひょっとして実際の処理とは別にログ出力に問題があるのではないかと思いtcpdumpで実際のTCPパケットのやりとり確認してみる。

$ sudo tcpdump -lX -s 1024 -i eth0 port 80 |tee /tmp/tcpdump.txt
$ cat /tmp/tcpdump.txt

*** SYN: Socketオープン
01:27:14.155974 IP foo.43242 > bar.http: S 3856091341:3856091341(0) win 5840
01:27:14.158135 IP bar.http > foo.43242: S 2366776094:2366776094(0) ack 3856091342 win 5792
01:27:14.158197 IP foo.43242 > bar.http: . ack 1 win 92

*** PUSH: 1stリクエスト
01:27:14.156012 IP foo.43242 > bar.http: P 1:63(62) ack 1 win 92
01:27:14.156080 IP bar.http > foo.43242: . ack 63 win 1448

*** PUSH: 1stレスポンス
01:27:14.158768 IP bar.http > foo.43242: P 1:198(197) ack 63 win 1448
01:27:14.158930 IP foo.43242 > bar.http: . ack 198 win 108

*** PUSH: 2nd, 3rd, 4thリクエスト
01:27:14.159183 IP foo.43242 > bar.http: P 63:125(62) ack 198 win 108
01:27:14.159277 IP foo.43242 > bar.http: P 125:187(62) ack 198 win 108
01:27:14.159361 IP foo.43242 > bar.http: P 187:249(62) ack 198 win 108

*** PUSH: 2nd, 3rd, 4thまとめてレスポンス
01:27:14.163514 IP bar.http > foo.43242: P 198:789(591) ack 249 win 1448

*** FIN: Socket クローズ
01:27:14.164128 IP foo.43242 > bar.http: F 249:249(0) ack 789 win 127
01:27:14.164634 IP bar.http > foo.43242: F 789:789(0) ack 250 win 1448
01:27:14.164780 IP foo.43242 > bar.http: . ack 790 win 127

tcpdumpの結果も変わらず同じ。ログを見る限りオープン処理（SYNフラグの出力部分、いわゆる3way handshake）が行われた後、１つ目のリクエスト直後にレスポンスを受け、その後2番目以降のリクエストはレスポンスを待つことなくソケット書き込み、つまりPipeliningリクエスト送受信が行われている。　どうして１つ目だけがダメで、２つ目以降からうまくいくのだろう？？ (T . T)

細かくlibcurlのコードを追えばよいのだろうがこれ以上調査する気持ちにならないので取り敢えずここで終えておく。続きはいつか。

おわり。

Ubuntu 9.10 on my Dell XPS M1210

yoichi — Sat, 27 Mar 2010 14:22:48 +0000

Vista on Dell XPS M1210（CeleronM,1GMEM）というサイテーに遅いOSの上でvmwareやcolinuxを通じてLinuxを動かしているとそのあまりの遅さに端末を捨ててしまいたくなる衝動にかられていた。なのでたまにTV見ながら膝上に乗せて遊んであげていたけどその遅さ故に使うことが憚られその存在は忘れがちに。そこで試しに入れてみたUbuntu 9.10。デュアルブートではなく男らしくフルUbuntu。 Hibernateも問題なく動作しているしサクサク動いて快適。よみがえったよXPS M1210。

簡単Boehm GCによるC/C++メモリリーク検知

yoichi — Thu, 25 Mar 2010 14:37:54 +0000

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 1:6.8-1.1 conservative garbage collector for C (develo
ii libgc1c2 1:6.8-1.1 conservative garbage collector for C and C++

**Cコードメモリリーク検知 – *alloc/freeをGC_関数に置換**

Boehm GCにはGC_MALLOC等のリソース確保系関数でリソース確保されたにもかかわらずGC_FREE等の解放系関数でリソース解放されずにリークしてしまっているオブジェクトを検知してそれらをレポートする機能がある。このメモリリーク検知レポートはGC_gcollect関数で実行される。ただしこのときメモリリーク検知レポート機能をオンにするためにはそもそもBoehm GC を-DFIND_LEAKオプションでコンパイルするか、または実行時にダイナミックにGC_find_leak=1をセットしてやる必要がある。

対象オブジェクト: GC_MALLOC等でリソース確保されたにもかかわらずGC_FREE等で解放されないオブジェクト
検知レポート実行関数： GC_gcollect
前提条件： -DFIND_LEAKオプションでコンパイルされたBoehmGC or 実行時にGC_find_leak=1をセット

「Using the Garbage Collector as Leak Detector」ではこのメモリリーク検知レポート機能を利用して実際のCコードのメモリリークを検知するために直接ヒープからメモリ確保、解放を行うための基本関数をBoehmGCの関数で置き換えるためのヘッダを用意している。

gc_detect_leaks.h

#define GC_DEBUG
#include "gc.h"
#define malloc(n) GC_MALLOC(n)
#define calloc(m,n) GC_MALLOC((m)*(n))
#define free(p) GC_FREE(p)
#define realloc(p,n) GC_REALLOC((p),(n))
#define CHECK_LEAKS() GC_gcollect()

試しにメモリリークを引き起こすコードに上記ヘッダをインクルードしたサンプルコード(t1.c)を用意してコンパイル+ 実行してみる。
サンプルコード: t1.c

#include
#include "gc_detect_leaks.h"
int main() {
GC_find_leak = 1;
char *a;
while(1){
a = (char*)malloc(100);　　// t1.c: line7
//free(a);
CHECK_LEAKS();
}
}

[コンパイルと実行結果]
$ gcc -g -Wall t1.c -o t1 -I/usr/include/gc -L/usr/lib -lgc
$ ./t1
Leaked composite object at 0x805af90 (t1.c:7, sz=100, NORMAL)
Leaked composite object at 0x805af10 (t1.c:7, sz=100, NORMAL)
Leaked composite object at 0x805af90 (t1.c:7, sz=100, NORMAL)
...

無事メモリリークを検知。メモリリークの原因となっている箇所（t1.cの７行目）も特定されているので合格。ちなみに上記ヘッダでGC_DEBUGをdefineしているは理由はgc.hで定義されているGC_MALLOCをデバック用出力にモードにするため。以下gc.hの該当部分だけを略して抜粋。

gc6.8 – /usr/local/gc/gc.h

#ifdef GC_ADD_CALLER
# define GC_EXTRAS GC_RETURN_ADDR, __FILE__, __LINE__
...略...
#else
# define GC_EXTRAS __FILE__, __LINE__
...略...
#endif

# ifdef GC_DEBUG
# define GC_MALLOC(sz) GC_debug_malloc(sz, GC_EXTRAS)
... 略...
# else
# define GC_MALLOC(sz) GC_malloc(sz)
...略...
# endif

C++ コードメモリリーク検知 – gc/gc_cleanupクラスで継承

次にC++コードのメモリリーク検知を行う。C++のデータ構造の基本はクラス（細かいことを省けば構造体もクラス）でありクラスはnewオペレーターでメモリを動的に確保する。当然のことながらデフォルトのnewオペレータでリソース確保した場合はGC回収不能であるためBoehm GCが用意しているC++用ライブラリを利用する。gc_cpp.hをみるとこれは単なるCライブラリのラップクラス。以下のようにgcやgc_cleanupクラスをベースクラスとすることでGC回収可能なオブジェクトとして扱うことができる。

サンプルコード: t2.cpp

#include
#define GC_DEBUG
#include "gc_cpp.h"
#define CHECK_LEAKS() GC_gcollect()
class Foo: public gc{};
int main() {
GC_find_leak = 1;
Foo *f;
while(1){
f =new Foo;　　　// t2.cpp: line10
// delete f;
CHECK_LEAKS();
}
}

[コンパイルと実行結果]
$ g++ -g -Wall t2.cpp -o t2 -I/usr/include/gc -L/usr/lib -lgc
$ ./t2
Leaked composite object at 0x805afe8 (/usr/include/gc/gc_cpp.h:274, sz=1, NORMAL)
Leaked composite object at 0x805afd0 (/usr/include/gc/gc_cpp.h:274, sz=1, NORMAL)
Leaked composite object at 0x805afe8 (/usr/include/gc/gc_cpp.h:274, sz=1, NORMAL)
....

これも無事メモリリーク検知はされている。ただしリーク箇所が/usr/include/gc/gc_cpp.hのL274行目を指している。これではリークの原因箇所がわからない。できればt2.cppのL10行目(f=new Foo)を指してもらいたい。さらにこの方法では単に既存のコードのメモリーリーク検知のみを行いたい場合でも、クラスをgc やgc_cleanupクラスで継承させるといったコードに手を加えていく作業が必要があるのでとても面倒でありコード量が多ければ多いほど手間がかかる。

C++コードメモリリーク検知 – new/deleteオペレータのオーバーロード

そこで既存のコードにあまり手を加えなくてもメモリリーク検知ができ、且つリークの原因箇所を特定できる方法を考えてみた。まずは既存のコードの手を加えないでメモリリーク検知する方法。クラスはリソースの確保、解放をそれぞれnew、 deleteオペレータで行うのでこれらをグローバルにオーバーロードしてやり内部のリソース確保、解放のための実装をGC関数で置き換えてやる。そしてそのヘッダを既存のコードにインクルードしてやれば既存のコードに手を加えないでメモリーリークの検知ができるのではないかと。ヘッダは以下のような感じ。

#define GC_DEBUG
#include "gc.h"
void* operator new(size_t size) {
return GC_MALLOC(size);
}
void* operator new[](size_t size) {
return GC_MALLOC(size);
}
void operator delete(void* p) {
if (p) GC_FREE(p);
}
void operator delete[](void* p) {
if (p) GC_FREE(p);
}

ただしこれだけではメモリリークの検知はできてもリークの原因箇所の特定が難しい。このままだと上記ヘッダのGC_MALLOC()コール箇所がリーク箇所としてレポートされてしまう。理想はnewオペレータをコールしている箇所がレポートされて欲しい。ということで次のように GC_debug_malloc()にnewオペレータコール箇所のファイル名と行を渡すように変更してみる。

gc_detect_leaks.h

#define GC_DEBUG
#include "gc.h"
void* operator new(size_t size, const char * s, int i) {
return GC_debug_malloc(size,s,i);
}
void* operator new[](size_t size, const char * s, int i) {
return GC_debug_malloc(size,s,i);
}
void operator delete(void* p) {
if (p) GC_debug_free(p);
}
void operator delete[](void* p) {
if (p) GC_debug_free(p);
}
# define new new(__FILE__, __LINE__)
# define CHECK_LEAKS() GC_gcollect()
int GC_find_leak = 1;

ためしにメモリリークを引き起こすC++コードに上記ヘッダをインクルードしたものを用意してコンパイル+ 実行してみる。今度はヘッダにint GC_find_leak = 1を含めているのでサンプルコードにGC_find_leak = 1をセットする必要はない。

サンプルコード: t3.cpp

#include
#include "gc_detect_leaks.h"
class Foo{};
int main() {
Foo *f;
while(1){
f =new Foo; // t3.cpp: line7
// delete f;
CHECK_LEAKS();
}
}

[コンパイルと実行結果]
$ g++ -g -Wall t3.cpp -o t3 -I/usr/include/gc -L/usr/lib -lgc
$ ./t3
Leaked composite object at 0x805afe8 (t3.cpp:7, sz=1, NORMAL)
Leaked composite object at 0x805afd0 (t3.cpp:7, sz=1, NORMAL)
Leaked composite object at 0x805afe8 (t3.cpp:7, sz=1, NORMAL)
...

見事メモリリークを検知しnewオペレータをコールしている行がレポートされた。というわけでこのヘッダをインクルードするだけで他の既存のコードに手を加えることなくメモリリークを検知することができた。

最後に、今回使ったサンプルコードとここで紹介したヘッダを少し体裁を整えてgithubにあげておきました。ちなみにgithubにあげたgc_detect_leaks.hを使う際は-DGC_DETECT_MEM_LEAKでコンパイルすることをお忘れなく。

http://github.com/yokawasa/any/tree/master/boehmgc/

おわり

ページ置換アルゴリズム(Page Replacement Algorithms)のシュミレーション

yoichi — Sat, 13 Mar 2010 00:46:33 +0000

システムのオペレーションをやっているとスラッシングが原因でサーバが一時的にサービス提供不能になっていまうなんてことがたまにある。スラッシングとは、例えば大量の処理リクエストが発生してしまい利用可能な物理メモリ量を大きく超えてしまった場合に起ったりする。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
in the order. max entry num is 100. (space between each)
-f <フレーム数> The number of page frames. max frame num is 10.
-h Display usage information (this message)

実行例:
./page_rep_algos -a LRU -p "0 1 2 3 2 1 4 3 6 0 9" -f 3

LRU（Least Recently Used）

LRUではその名のとおり「最も長く使われないページ」を置換の対象とする。なのでいつ追加されたということよりも最後にアクセスされてからどれだけ経過しているかを測り最も長いものから置換していく。例えばページフレーム数3でアクセスページ番号列を「0 1 2 3 2 1 4 1 6 0 2 1」とした場合、1つずつトレースすると次のような図になる。Faultとはページフォールト(Page Fault)のことでFaultのない場合はページHitしたことを意味する。

Page Referenceが4の時のページ置換計算を例にする。置換される前の各ページフレームPF[0]、PF[1]、PF[2]にはそれぞれページ番号3、1、2が割り当てられている。ページ番号4がアクセスされるタイミングでページ番号3、1、2がアクセスされていない期間はそれぞれ3、1、2となる。よって最も長くアクセスされていないPF[0](ページ番号3)が置換対象となる。ツールで実行してみると次のとおり。ページフォールトが9回で、Hit率25%。

[kawasaki@debian:~] $ ./page_rep_algos -a LRU -p "0 1 2 3 2 1 4 1 6 0 2 1" -f 3
0: 0 Miss
1: 0 1 Miss
2: 0 1 2 Miss
3: 3 1 2 Miss
2: 3 1 2 Hit
1: 3 1 2 Hit
4: 4 1 2 Miss
1: 4 1 2 Hit
6: 4 1 6 Miss
0: 0 1 6 Miss
2: 0 2 6 Miss
1: 0 2 1 Miss

Number of Page Frames = 3
Total Number of References = 12
Number of Hits = 3
Number of Page Fault = 9
HitRatio = 0.25

FIFO（First-In First-Out）

FIFOもその名のとおり「早く追加されたページ」を置換の対象とする。この場合はLRUと違っていつ追加されたということが重要であり最も早いものから置換していく。
LRUと同くサンプル( ページフレーム数3でアクセスページ番号列を「0 1 2 3 2 1 4 1 6 0 2 1」とした場合、1つずつトレースすると次のような図になる。

ツールで実行してみると次のとおり。ページフォールトが10回で、Hit率17%。

[kawasaki@debian:~] $ ./page_rep_algos -a FIFO -p "0 1 2 3 2 1 4 1 6 0 2 1" -f 3
0: 0 Miss
1: 0 1 Miss
2: 0 1 2 Miss
3: 3 1 2 Miss
2: 3 1 2 Hit
1: 3 1 2 Hit
4: 3 4 2 Miss
1: 3 4 1 Miss
6: 6 4 1 Miss
0: 6 0 1 Miss
2: 6 0 2 Miss
1: 1 0 2 Miss

Number of Page Frames = 3
Total Number of References = 12
Number of Hits = 2
Number of Page Fault = 10
HitRatio = 0.17

OPTIMAL

OPTIMALとは未来に対して「最も長い間使われないであろう」ページを置換の対象とする。LRUが過去に対して「最も長く使われないページ」であるのと対象的であるといえる。ただし、実行時に未来の計測をするのは不可能であり経験則でパターン分析ができているとか、今回のように予めパターンを指定する場合においてのみ有効である。理論上一番いいのはOPTIMALアルゴリズムといわれているが未来予測どうするのかといったところでしょうか。

Page Referenceが4の時のページ置換計算を例にする。置換される前の各ページフレームPF[0]、PF[1]、PF[2]にはそれぞれページ番号3、1、2が割り当てられている。ページ番号4がアクセスされるタイミングからページ番号3、1、2が未来にアクセスされるまでの期間はそれぞれ5以上、1、4となる。よって最も遠い未来までアクセスされないPF[0](ページ番号3)が置換対象となる。ツールで実行してみると次のとおり。ページフォールトが7回で、Hit率42%と最も高い。

[kawasaki@debian:~] $ ./page_rep_algos -a OPTIMAL -p "0 1 2 3 2 1 4 1 6 0 2 1" -f 3
0: 0 Miss
1: 0 1 Miss
2: 0 1 2 Miss
3: 3 1 2 Miss
2: 3 1 2 Hit
1: 3 1 2 Hit
4: 4 1 2 Miss
1: 4 1 2 Hit
6: 6 1 2 Miss
0: 0 1 2 Miss
2: 0 1 2 Hit
1: 0 1 2 Hit

Number of Page Frames = 3
Total Number of References = 12
Number of Hits = 5
Number of Page Fault = 7
HitRatio = 0.42

シュミレーションの結果、OPTIMALアルゴリズムのHit率が最も高く、これが最も置換効率がよいということになる。今回はインプットするサンプル数が少ないのでまともな結果を出すならばデータサンプルをもっと増やす必要があるのだろうけどこの辺で終わりにしておきます。

おわり。

Google Reader CacheからItemを削除する方法

yoichi — Sat, 27 Feb 2010 14:55:05 +0000

一度誤った投稿をしてしまいそれが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>
>>
>
isPermaLink="false">http://yk55.com/blog/?p=200>
>~略~>
>~略~>
>http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/feed/>
>0>
>

これを追加したRSSフィードを公開することで時間がたてばフィードがクローリングされ、さきほどの間違ったItemがダミーItemでリプレースされる。以下が見事にリプレースされた結果。

あまりにもべたなやり方だけど、どうしてもなんとかしたい場合にはこの方法で。おわり。

Dynamic Binding & VTable Concept in C++

yoichi — Sat, 27 Feb 2010 10:32:11 +0000

たまに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 << "SuperClass::func()" << endl; }
};
class SubClass : public SuperClass {
public:
void func() { cout << "SubClass::func()" << endl; }
};
int main(int argc, char **argv ) {
SubClass sub;
SuperClass *super =⊂
super->func();
return 0;
}

[実行結果]
SuperClass::func()

VIRTUAL FUNCTION, VTABLE, and VPOINTER

次にVirtual関数の例を説明する。さきほどの例ではUPCASTによりSubClassクラスではなくSuperClassクラスのfunc関数がcallされた。ここではSuperClassの関数にvirtualをつけた場合のfunc関数の振る舞いを確かめてみる。virtual関数func1、func2をもつSuperClassを継承した3つのSubClassを用意する。これら3つはそれぞれfunc1、func2両方とも、func1のみ、func2のみをoverrideしている。実行結果はSubClassでvirtual関数をoverrideした場合はその内容が、そうでない場合はSuperClassの内容が表示される。

#include
using std::cout;
using std::endl;
class SuperClass {
public:
virtual void funcA() { cout << "SuperClass::funcA()" << endl; };
virtual void funcB() { cout << "SuperClass::funcB()" << endl; };
};
class SubClass1 : public SuperClass {
public:
void funcA() { cout << "SubClass1::funcA()" << endl; }
void funcB() { cout << "SubClass1::funcB()" << endl; }
};
class SubClass2 : public SuperClass {
public:
void funcA() { cout << "SubClass2::funcA()" << endl; }
};
class SubClass3 : public SuperClass {
public:
void funcB() { cout << "SubClass2::funcB()" << endl; }
};
int main(int argc, char **argv ) {
SubClass1 sub1; SubClass2 sub2; SubClass3 sub3;
cout << "***************SubClass1***************" << endl;
SuperClass *super =&sub1;
super->funcA(); super->funcB();
cout << "***************SubClass2***************" << endl;
super =&sub2;
super->funcA(); super->funcB();
cout << "***************SubClass3***************" << endl;
super =&sub3;
super->funcA();super->funcB();
return 0;
}

[実行結果]
***************SubClass1***************
SubClass1::funcA()
SubClass1::funcB()
***************SubClass2***************
SubClass2::funcA()
SuperClass::funcB()
***************SubClass3***************
SuperClass::funcA()
SubClass2::funcB()

virtualな関数の場合はコンパイラは型ではなくてオブジェクトのポインタを見ていて実行時にどのfuncが実行されるべきかを判断する。非virtual関数の時と違いコンパイラーはコンパイル時にはどのfuncが呼ばれるのか判別できない。この実行時にどのfuncが呼ばれるのか決定することをDynamic Bindingと呼ぶ。そしてこのDynamic BindingはVirtual Function table(Vtable)と呼ばれるメカニズムによって実現される。ようやく本題。

Vtableとはvirtual関数を持っているクラスや親クラスで定義されているvirtual関数をoverrideしたクラスに対してコンパイラーが作成する（その名のとおり）仮想テーブルである。コンパイラーはvirtual関数を持っている/virtaul関数をoverrideしているクラスにのみクラスごとのVtableを作成してその中にbindすべき関数ポインターを持っている。
またこのVtableを指すポインタのことをvpointerと呼ぶ。コンパイラはVtableを持っているクラスに対してvpointerを隠しメンバー変数として追加する。さらにコンストラクタにそのvpointer変数の初期化を行うコードを追加する。よってオブジェクトが作成されるとき隠しメンバー変数vpointerは対応するVtableアドレスで初期化され、実行時の実行関数の決定は内部でvpointerを通じてVtableをlookupすることで実現される。　（参照: wikipedia:vtable implementation）

Vtableに作成される関数ポインターは、そのクラスで持っているvirtual関数のポインター、親クラスで定義されているvirtaul関数をoverrideした関数のポインター、また親クラスでvirtual定義されている関数をoverrideしない場合はその親のvirtual関数ポインタが含まれることになる。上記サンプルにあるSuperClass, SubClass[1-3]に対するオブジェクトとvpointer、vtableとそのvtableに含まれる関数ポインターの関係を図にすると以下のようになる。

上図を元にサンプル中のSubClass1::funcAのDynamic Bindingイメージを式化してみると次のような感じになる・ vptr1はSubClass1のvpointerとする。あくまでイメージであり(vptr->)は実際は見えません。

SubClass1 sub1;
SuperClass *super =&sub1;
super->vptr->funcA(); // SubClass1::funcA(),

g++ -fdump-class-hierarchのダンプ結果

最後にg++の-fdump-class-hierarchオプションによるVtableのダンプ結果を見てみる。上記サンプルファイルをvtable.cppとして次のようにコンパイルを行う。　（参考: Options for Debugging Your Program or GCC）

 g++ -fdump-class-hierarchy vtable.cc -o vtable

これでコンパイルが終わりvtable実行ファイルができあがる。また同一ディレクトリにvtable.cpp.002t.classという名前のファイルが出来上がる。このファイルにVtableのダンプ結果が出力されている。各クラスのVtable中を見るといまいち意味のわからないものはあるが上図のとおりの関数が含まれており、また各クラスにはvptrを見つけることができる。

Vtable for SubClass1
SubClass1::_ZTV9SubClass1: 4u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI9SubClass1)
8 SubClass1::funcA
12 SubClass1::funcB

Class SubClass1
size=4 align=4
base size=4 base align=4
SubClass1 (0xb7254a80) 0 nearly-empty
vptr=((& SubClass1::_ZTV9SubClass1) + 8u)
SuperClass (0xb707c1e0) 0 nearly-empty
primary-for SubClass1 (0xb7254a80)

Vtable for SubClass2
SubClass2::_ZTV9SubClass2: 4u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI9SubClass2)
8 SubClass2::funcA
12 SuperClass::funcB

Class SubClass2
size=4 align=4
base size=4 base align=4
SubClass2 (0xb7254b80) 0 nearly-empty
vptr=((& SubClass2::_ZTV9SubClass2) + 8u)
SuperClass (0xb707c3c0) 0 nearly-empty
primary-for SubClass2 (0xb7254b80)

Vtable for SubClass3
SubClass3::_ZTV9SubClass3: 4u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI9SubClass3)
8 SuperClass::funcA
12 SubClass3::funcB

Class SubClass3
size=4 align=4
base size=4 base align=4
SubClass3 (0xb7254c40) 0 nearly-empty
vptr=((& SubClass3::_ZTV9SubClass3) + 8u)
SuperClass (0xb707c528) 0 nearly-empty
primary-for SubClass3 (0xb7254c40)

おわり