フィボナッチ数列を計算する Apache モジュール
フィボナッチ数列を計算するのが流行っていると聞いて飛んできま……あれ別に流行ってないんですか。そうですか。
せっかくなので，上位の引数の結果を計算するために*1，サブリクエストという機能を使ってみました。サブリクエストというのは SSI とかの #include virtual に代表されるような，ハンドラの中から同一サーバのリクエストをもう一度投げてその結果を取得する，という機能です。
あくまで同一サーバ内でリクエストをあれこれするだけなので PHP のリモートファイル機能と違って分散処理ができるわけではないのですが*2。
通常のハンドラとして実装したので楽に出来るだろうと思ったんですが結構大変でした。
- サブリクエストはデフォルトでイニシャルリクエスト（メインリクエスト）と出力を共通とする（下記参考文献参照）
- なので output_filter を NULL でサブリクエストを投げるとそこで EOS が発生して，その内容のみ出力されてしまう
- このため出力をすべて吸い込んで後で brigade を読むことのできるダミーフィルタを登録して，それの出力結果を利用することになった
- なぜかイニシャルリクエストとサブリクエストの間で
request_configを共有できなかった- なので memoize として
server->module_configを利用することに - 副作用として，サーバを再利用する限り，計算結果を覚えています（笑
- なので memoize として
ちなみに無限ループを避けるため，サブリクエストは 500 段階くらいまでしか発行できません。httpd サーバの実装として。たしか。
実行結果は text/plain で吐きます。んでログに計算過程が出力されます。memoizing を使わないと，fib(8) が
[Mon Dec 03 18:04:54 2007] [notice] [client 127.0.0.1] main(8) invoked [Mon Dec 03 18:04:54 2007] [notice] [client 127.0.0.1] sub (6) invoked [Mon Dec 03 18:04:54 2007] [notice] [client 127.0.0.1] sub (4) invoked ... snip ... [Mon Dec 03 18:04:54 2007] [notice] [client 127.0.0.1] sub (6) = 8 [Mon Dec 03 18:04:54 2007] [notice] [client 127.0.0.1] sub (7) = 13 [Mon Dec 03 18:04:54 2007] [notice] [client 127.0.0.1] main(8) = 21
のように40行くらいの出力になりますが，memoizing すると
[Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] main(8) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (6) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (4) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (3) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (3) = 2 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (4) = 3 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (5) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (4) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (4) = 3 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (5) = 5 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (6) = 8 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (7) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (6) invoked [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (6) = 8 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] sub (7) = 13 [Mon Dec 03 18:05:29 2007] [notice] [client 127.0.0.1] main(8) = 21
のように16行で収まります*3。
参考文献
ソース
以下，ソースです。
#include "apr_general.h" #include "apr_lib.h" #include "apr_strings.h" #if APR_HAVE_STDLIB_H #include <stdlib.h> #endif #include "ap_config.h" #include "httpd.h" #include "http_config.h" #include "http_protocol.h" #include "http_log.h" #include "http_main.h" #include "http_request.h" #include "mod_core.h" #define USE_MEMOIZE 1 module AP_MODULE_DECLARE_DATA fib_module; typedef struct fib_cfg { apr_table_t *memoize; } fib_cfg; typedef struct sweeper_ctx { apr_bucket_brigade *bb; } sweeper_ctx; static ap_filter_rec_t *sweeper_filter_handle; static apr_status_t sweeper_filter(ap_filter_t *f, apr_bucket_brigade *bb) { apr_bucket *b; sweeper_ctx *ctx = (sweeper_ctx *) f->ctx; int seen_eos = 0; b = APR_BRIGADE_FIRST(bb); while (b != APR_BRIGADE_SENTINEL(bb)) { if (APR_BUCKET_IS_EOS(b)) seen_eos = 1; b = APR_BUCKET_NEXT(b); } APR_BRIGADE_CONCAT(ctx->bb, bb); if (seen_eos) { b = apr_bucket_eos_create(bb->bucket_alloc); APR_BRIGADE_INSERT_TAIL(bb, b); return ap_pass_brigade(f->next, bb); } return APR_SUCCESS; } static apr_status_t call_subreq(request_rec *req, apr_pool_t *pool, const char *base, long int arg, long int *presult) { apr_status_t r = APR_EGENERAL; const char *new_uri; request_rec *rr; sweeper_ctx *ctx; ap_filter_t *f; /* create sweeper filter */ ctx = (sweeper_ctx *) apr_palloc(pool, sizeof(sweeper_ctx)); ctx->bb = apr_brigade_create(pool, req->connection->bucket_alloc); f = ap_add_output_filter_handle(sweeper_filter_handle, ctx, req, req->connection); new_uri = apr_psprintf(pool, "%s/%ld", base, arg); rr = ap_sub_req_lookup_uri(new_uri, req, f); if (rr->status == HTTP_OK) { int status; char *output; apr_size_t len; long int result; status = ap_run_sub_req(rr); if (status != OK && ! ap_is_HTTP_SUCCESS(status)) return APR_EGENERAL; r = apr_brigade_pflatten(ctx->bb, &output, &len, pool); if (r != APR_SUCCESS) return r; result = strtol(output, NULL, 10); ap_remove_output_filter(f); *presult = result; r = APR_SUCCESS; } ap_destroy_sub_req(rr); return r; } static apr_status_t calc_fib(request_rec *req, apr_table_t *memoize, const char *base_uri, long int arg, long int *presult) { apr_status_t r; apr_pool_t *pool = req->pool; long int v; const char *sarg = NULL, *sres; char *p; if (arg <= 0L) return APR_EGENERAL; else if (arg <= 2L) { *presult = 1L; return APR_SUCCESS; } if (memoize) { sarg = apr_psprintf(pool, "%ld", arg); sres = apr_table_get(memoize, sarg); if (sres) { *presult = strtol(sres, &p, 10); if (p <= sres) return APR_EGENERAL; return APR_SUCCESS; } } ap_log_rerror(APLOG_MARK, APLOG_NOTICE, 0, req, "%s(%ld) invoked", ap_is_initial_req(req) ? "main" : "sub ", arg ); *presult = 0; r = call_subreq(req, pool, base_uri, arg - 2, &v); if (r != APR_SUCCESS) return r; *presult += v; r = call_subreq(req, pool, base_uri, arg - 1, &v); if (r != APR_SUCCESS) return r; *presult += v; if (memoize) { apr_table_setn(memoize, sarg, apr_psprintf(pool, "%ld", *presult)); } ap_log_rerror(APLOG_MARK, APLOG_NOTICE, 0, req, "%s(%ld) = %ld", ap_is_initial_req(req) ? "main" : "sub ", arg, *presult ); return APR_SUCCESS; } static apr_status_t retrieve_arg(apr_pool_t *pool, const char *uri, const char **pbase, long int *parg) { const char *p; char *pp; if (! uri) return APR_EGENERAL; p = strrchr(uri, '/'); if (! p) return APR_EGENERAL; *pbase = apr_pstrmemdup(pool, uri, p - uri); *parg = strtol(p + 1, &pp, 10); if (pp <= p + 1) return APR_EGENERAL; return APR_SUCCESS; } static int fib_handler(request_rec *req) { apr_status_t r; fib_cfg *cfg; const char *base; long int arg, result = 0; if (strcmp(req->handler, "fib")) return DECLINED; cfg = ap_get_module_config(req->server->module_config, &fib_module); r = retrieve_arg(req->pool, req->uri, &base, &arg); if (r != APR_SUCCESS) return HTTP_INTERNAL_SERVER_ERROR; r = calc_fib(req, cfg->memoize, base, arg, &result); if (r != APR_SUCCESS) return HTTP_INTERNAL_SERVER_ERROR; ap_set_content_type(req, "text/plain"); ap_rprintf(req, "%ld\n", result); return OK; } static void *create_fib_server_config(apr_pool_t *pool, server_rec *s) { fib_cfg *cfg; cfg = apr_pcalloc(pool, sizeof(fib_cfg)); #if defined(USE_MEMOIZE) && USE_MEMOIZE cfg->memoize = apr_table_make(pool, 2); #endif return cfg; } static void register_hooks(apr_pool_t *p) { sweeper_filter_handle = ap_register_output_filter("__SWEEP__", sweeper_filter, NULL, AP_FTYPE_RESOURCE); ap_hook_handler(fib_handler, NULL, NULL, APR_HOOK_MIDDLE); } module AP_MODULE_DECLARE_DATA fib_module = { STANDARD20_MODULE_STUFF, NULL, /* create per-directory config structure */ NULL, /* merge per-directory config structure */ create_fib_server_config, /* create per-server config structure */ NULL, /* merge per-server config structure */ NULL, /* command apr_table_t */ register_hooks /* register hooks */ };
