nginx拡張モジュールをアップデートしました

先日作成しましたnginxの拡張モジュールを更新しました。
(前回の更新はこちらになります)

前回の拡張ではunixのshared memory segment上にデータを展開するようにしました。
これによって各プロセス間でユーザからのアクセス情報を共有できるといったものでした。

今回の対応では更にネットワーク上で構成された複数のnginxサーバでもデータを共有することを目的として、ネットワーク上のストレージ(今回の対応では実装としてはmemcachedを対象)に対応するようにしました。

一見ストレージとして memcached に格納できる様になっただけですが、内部的なコードはまた別の側面が改良されました。
当初は特定のストレージ、具体的にはプロセスのheap領域や前回対応したosの共有メモリセグメントにデータを置くという想定でしたが、ngxinのconfigurationファイルでストレージを指定できる方式にし、コードをほぼすべて書きなおしてあります。

これによって今現在指定できるストレージであるshmemとmemcachedに関してはソースコードが完全に分離できる形でインターフェースを切り分けています。
nginxが起動した時点でこのモジュールはconfigurationファイルを読み取り、指定されたストレージに基づいた初期化を行います。

実装としてはこのインタフェースは下記のような関数ポインタを定義した構造体として定義しており、このモジュール内部でのライフサイクルを定義しています。
例えばinit関数ポインタには各種ストレージを初期化する関数ポインタが代入されることを期待しており、update_entryでは各種ストレージ内部での更新処理を行う関数ポインタが代入されることを期待しております。

handler側ではこの構造体を元にライフサイクルを初期化〜破棄に関するまで定めており、適宜それぞれの箇所で関数を呼び出します。
ストレージ側の実装ではこれらのインタフェースを元に各種イベントにおける処理を実装することになります。

/**
 * function pointers. these behave like interface.
 */
typedef struct {
	int (*init)(ngx_cycle_t *cycle, ngx_http_access_filter_conf_t *afcf);
	void* (*get_entry)(char *key, ngx_http_access_filter_conf_t *afcf);
	storage_entry_t* (*get_data)(void *entry_p);
	void (*free_entry)(void *entry_p);
	int (*add_count)(char *key, void *data, ngx_http_access_filter_conf_t *afcf);
	int (*set_banned)(char *key, void *data, ngx_http_access_filter_conf_t *afcf);
	int (*update_entry)(char *key, void *entry_p, ngx_http_access_filter_conf_t *afcf);
	int (*create_entry)(char *key, ngx_http_access_filter_conf_t *afcf);
	int (*fin)(ngx_cycle_t *cycle, ngx_http_access_filter_conf_t *afcf);
} storage_accessor;

つまりこのnginxモジュールの中で更にストレージをモジュールとして扱い実装しており、これによりストレージは任意のものに差し替えられる拡張性を手に入れることになります。
これはすなわち、今後他のストレージを使用したいというような場合において、追加で実装したい時にはこのインタフェースで期待する関数を実装することだけで可能になります。


nginx拡張モジュールを作りました

nginxの拡張モジュールを作成してgithubにて公開しました。

DOSのような攻撃的なアクセスを制御するようなモジュールで、指定時間に指定回数のアクセスを検知すると、任意の時間403を返却するようになります。

正確に言うと以前から公開していたものなのですが、改良を加えております。以前のものはprocess固有の領域にユーザのアクセス情報を格納していたのですが、これだとworker processが増えた際にそれぞれのプロセスで処理したアクセス履歴を共有できません。
むしろ通常はworker processは複数に設定することが多いと思いますので、これはすごく大きな問題です。

なので今回ユーザからのアクセス情報をosのshared memory segmentに格納するように改良を加えました。
データ構造の変更やデータ更新時の排他制御などを付け加えた形になります。

直にメモリを操作するとか、排他制御とか、あとは開発する上でデバッガを用いたりしているので、開発過程でosの知識が身についたりして非常に嬉しい限りです。


phpの配列はどのようにして初期化され実行されるのか

概要

phpなどのLLは、記述するだけでコンパイルなしに実行されますがその中身はどうなっているのでしょうか。
今回は配列を例にとって、実際にphp処理系をおってみます。
主に字句解析、構文解析の実装について順を追って解説していきたいと思います。

zend処理系

まずはphpの処理系について全体像を軽く解説します。
ドキュメントも結構まとまっておりこの辺りなど非常に参考になります。(4年前ですがこの勉強会行きたかったな・・・)

さて、話を戻しますがphpのコアな部分はzend処理系と呼ばれる実装によって成り立っています。
zend frameworkというフレームワークが存在しますが、そちらのフレームワークとしてのzendではなくてphpの初期の発展に寄与したグループのzendです。

zend処理系ではphpのコードから実際に処理を実行するまでに下記のフェーズを実行します。

  1. 字句解析
  2. コードを字句(トークン)に分解します。トークンとは文が構成される最小単位のことです

  3. 構文解析
  4. 分解されたトークンを実際にどういった命令であるかということを解釈します

  5. OPcodeに翻訳
  6. 解釈した公文をOPcodeという中間コードに翻訳します

  7. 実行
  8. 実際にOPcodeを実行します

通常のアプリケーション開発なんかで言うとOPcodeなどは聞いたことがある方も多いのではないでしょうか。
有名どころではOPcacheなどがありますね。

OPcacheはその名の通りOPcodeをキャッシングします。
phpのコードに対して字句解析・構文解析を実行することで中間コードを生成するのですが、同じコードを毎回解析するのはかなり無駄なコストですね。
この中間コードをキャッシングすることで実行性能を上昇させることを目的とした機能です。
余談ですがこちらはphp5.5以降では標準搭載されるようになっていますね。

実際にはその前のフェーズとして字句解析・構文解析が行われます。
これらはごく普通にphpアプリケーションを開発しているだけだとあまり関わることがありません。今回はこちらについて掘り下げていきたいと思います。

字句解析

まず字句解析について。先に簡単に説明したようにコードを字句(トークン)に分解する作業です。

イメージしやすいように下記のサンプルコードを実行してみます。

<?php
$tokens = token_get_all('<?php
$hoge = array();');
foreach ($tokens as $i => $token) {
	echo is_array($token) ? token_name($token[0]) : $token;
	echo PHP_EOL;
}

echo PHP_EOL;

$tokens = token_get_all('<?php
$fuga = [];');
foreach ($tokens as $i => $token) {
	echo is_array($token) ? token_name($token[0]) : $token;
	echo PHP_EOL;
}

token_get_allはphpコードを引数として受け取り、そのコードをトークンレベルまで分解します。
またtoken_nameは分解されたトークンにzend処理系で管理している enum yytokentype を取得します。詳しくは zend_language_parser.c などを参照しましょう。

さて、サンプルコードの実行結果は下記のようになります。

T_OPEN_TAG
T_VARIABLE
T_WHITESPACE
=
T_WHITESPACE
T_ARRAY
(
)
;


T_OPEN_TAG
T_VARIABLE
T_WHITESPACE
=
T_WHITESPACE
[
]
;

T_OPEN_TAGはphpの開始タグを表すenum定数になります。またT_WHITESPACEはホワイトスペースを表すenum定数になります。
このようにphpのセンテンスをzend処理系で用意されたトークンに細かく分解していきます。

さらにここでarrayはT_ARRAYにトークン解析されていることがわかります。またそのあとのカッコについてはそのままになっていることがわかりますね。
これはそれ自体で意味を持っているメタ文字になるからです。

各種zend処理系での予約後に関してはトークン解析によってenumに置き換えられ、それ以外はメタ文字としてそのまま認識されることになります。

構文解析

続いて解析できたトークンを意味のある文として解釈します。zend処理系ではこの構文解析の実装とbisonと呼ばれるgnuツールを利用しています。bisonはBNFを基本とした亜種で文法を表現します。

bisonについてはこちらでかなり詳しく説明しておられるので参考にしてみると良いでしょう。

bisonでは終端トークン(最小単位のトークン)を組み合わせて文として認識できる構成を定義していきます。
zend処理系における実装はzend_language_parser.yに記述されておりますので確認してみてください。

例えば下記のようなコードが合った時

<?php
$a = 'str';

先に述べたようにこれらはまずトークン解析され、続いてbisonによって記述された文に一致するパターンを検索します。
もし文が適合すれば処理しますし、仮に文が解釈できないようであればパースエラーとして実行されないで終了します。
bison(およびBNF記法)の強力なところはそれぞれの文章を再帰的に表現することや、文の定義に他の文を含むことができるので非常に柔軟に文を定義できるところにあります。

arrayの文を確認する

構文解析まで理解できたところで実際にphpではarrayというセンテンスをどのように解釈して処理系が動作しているのかというところを追いかけてみます。

例えば下記のようなphpコードを対象として取り上げてみてみましょう。

$a = array();

字句解析の項目で解説したようにarrayという文字列はT_ARRAYとしてトークナイズされます。bisonの定義ファイルからこれの定義を探してみます。

%token T_ARRAY           "array (T_ARRAY)"

すると上記のような項目が見つかりました。これはトークンT_ARRAYを定義していることを表します。
続いてT_ARRAYを文として定義している箇所(=構文解析を行っていると思われる箇所)を探してみましょう。

combined_scalar:
		T_ARRAY '(' array_pair_list ')' { $$ = $3; }
	|	'[' array_pair_list ']' { $$ = $2; }
;

見つかりましたcombined_scalarという文が定義されており、トークンとしてT_ARRAYが使用されていることから、これが配列の初期化としての文であることが理解できます。

bisonではパイプで区切ることで複数の文を定義することができます。
よって二つ目の文についてはPHP5.4以降で新たに定義されたブラケット(カギカッコ)による配列の定義が確認できますね。
カギカッコの中は構文により呼び出されるc言語による実装です。$$は戻り値を示しており、$xはx番目にマッチするトークンを表しています。

さてここで先に述べたようにbison(BNF)では文を再帰的に定義できますし、文の定義に他の文の定義を含むことができます。
ここではarray_pair_listという文が定義されていることが確認できるので更に文の定義を追いかけます。

array_pair_list:
		/* empty */ { zend_do_init_array(&$$, NULL, NULL, 0 TSRMLS_CC); }
	|	non_empty_array_pair_list possible_comma	{ $$ = $1; }
;

non_empty_array_pair_list:
		non_empty_array_pair_list ',' expr T_DOUBLE_ARROW expr	{ zend_do_add_array_element(&$$, &$5, &$3, 0 TSRMLS_CC); }
	|	non_empty_array_pair_list ',' expr			{ zend_do_add_array_element(&$$, &$3, NULL, 0 TSRMLS_CC); }
	|	expr T_DOUBLE_ARROW expr	{ zend_do_init_array(&$$, &$3, &$1, 0 TSRMLS_CC); }
	|	expr 				{ zend_do_init_array(&$$, &$1, NULL, 0 TSRMLS_CC); }
	|	non_empty_array_pair_list ',' expr T_DOUBLE_ARROW '&' w_variable { zend_do_add_array_element(&$$, &$6, &$3, 1 TSRMLS_CC); }
	|	non_empty_array_pair_list ',' '&' w_variable { zend_do_add_array_element(&$$, &$4, NULL, 1 TSRMLS_CC); }
	|	expr T_DOUBLE_ARROW '&' w_variable	{ zend_do_init_array(&$$, &$4, &$1, 1 TSRMLS_CC); }
	|	'&' w_variable 			{ zend_do_init_array(&$$, &$2, NULL, 1 TSRMLS_CC); }
;

possible_comma:
		/* empty */
	|	','
;

array_pair_listの文を確認するとempty(0個のトークンで構成される)またはnot_empty_array_pair_list possible_commaで構成されることがわかります。

possible_commaの文定義を確認するとコンマもしくはなにもなし、と定義されることがわかります。PHPの配列では末尾にコンマをつけてもつけなくても認識してくれますが、それはこの文定義によるものだということが理解できますね。

さらにnot_empty_array_pair_listを確認してみます。定義がそれぞれありますがphpの多様な配列定義を文として定義しています。
例えばphpのセンテンスとして下記のようなものがありますが、それぞれがこの構文として定義されています。

<?php
$array1 = array('key' => value);
$array2 = array(1, 2);
$array3 = array();

最終的にzend_do_init_arrayというcの関数が呼び出されていることがわかります。
今回は構文解析からarrayの処理系の解釈を追うことが目的ですので、zend_do_init_arrayについては次の機会に取り上げたいと思います。

まとめ

いかがでしたでしょうか。
意外とおってみるとそんなに難しくないことがわかります。これもbisonなど先人が作り出してきた便利なツールによるものですね。


phpのcount関数の実装を見る

ご無沙汰しております。
今日は掲題のようにcount関数の実装を見て行きたいと思います。

概要

phpの開発を行ったことがある方であれば、下記のようなコード見たことあると思います。

$something = array('a', 'b', 'c');

for($i=0; $i<count($something); $i++) {
 // do something
}

また下記のようなコードも目にすることがあると思います。

$something = array('a', 'b', 'c');
$count = count($something);

for($i=0; $i<$count; $i++) {
 // do something
}

これらのコードどちらが効率的なのでしょうか。
なんとなく後者のほうが効率が良いようなことは想像に難しくないと思います。
でも、はっきり前者は悪だと断言できる方は実は少ないのではないでしょうか。

後者にしておけば困ったことにはならないでしょう。ただし、コードが一行増える。微々たるものですが。
どちらかと言うと前者のほうがコードとしてはすっきりしていると思います。

それに何より中身がどうなっているのかわからないのが気分的にすっきりしない。
今日はphpのcount関数の実装を確認してみたいと思います。

調査

php公式からソースコードをダウンロードして調査します。
バージョンは現在の最新安定版である5.6.14としました。

zval構造体

まずphpのzend構造体から確認します。
zend.hをみてみましょう。

typedef struct _zval_struct zval;
struct _zval_struct {
    /* Variable information */
    zvalue_value value;       /* value */
    zend_uint refcount__gc;
    zend_uchar type;          /* active type */
    zend_uchar is_ref__gc;
};

typedef union _zvalue_value {
    long lval;        /* long value */
    double dval;      /* double value */
    struct {
        char *val;
        int len;
    } str;
    HashTable *ht;    /* hash table value */
    zend_object_value obj;
    zend_ast *ast;
} zvalue_value;

phpでは変数はzval構造体で表されます。
zval構造体は参照カウントや、変数実体を保持するzvalue_valueという共用体を更に内部で保持します。
union構造体とは宣言された値の内どれか一つを保持する構造体のことです。

phpではlongやdoubleやstringなどの値に応じてzvalue_value共用体が保持する実体を切り替えるようになっています。
配列変数の場合はHashTable構造体を保持することになります。

Hashtable構造体

さらにzend_hash.hファイルを確認してその構造を確認してみましょう。

struct _hashtable;
typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;       /* Used for element traversal */
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
 #if ZEND_DEBUG
    int inconsistent;
 #endif
} HashTable;

hashtable構造体については詳細な説明は今回は割愛します。
いったんデータ構造を確認したら今度はcount関数の実装を見てみることにしましょう。

count関数

array.cファイルを覗いてみます。

PHP_FUNCTION(count)
{
    zval *array;
    long mode = COUNT_NORMAL;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z|l", &array, &mode) == FAILURE) {
        return;
    }

    switch (Z_TYPE_P(array)) {
        case IS_NULL:
            RETURN_LONG(0);
            break;
        case IS_ARRAY:
            RETURN_LONG (php_count_recursive (array, mode TSRMLS_CC));
            break;
        case IS_OBJECT: {
#ifdef HAVE_SPL
            zval *retval;
#endif
            /* first, we check if the handler is defined */
            if (Z_OBJ_HT_P(array)->count_elements) {
                RETVAL_LONG(1);
                if (SUCCESS == Z_OBJ_HT(*array)->count_elements(array, &Z_LVAL_P(return_value) TSRMLS_CC)) {
                    return;
                }
            }
#ifdef HAVE_SPL
            /* if not and the object implements Countable we call its count() method */
            if (Z_OBJ_HT_P(array)->get_class_entry && instanceof_function(Z_OBJCE_P(array), spl_ce_Countable TSRMLS_CC)) {
                zend_call_method_with_0_params(&array, NULL, NULL, "count", &retval);
                if (retval) {
                    convert_to_long_ex(&retval);
                    RETVAL_LONG(Z_LVAL_P(retval));
                    zval_ptr_dtor(&retval);
                }
                return;
            }
#endif
        }
        default:
            RETURN_LONG(1);
            break;
    }
}

ごちゃごちゃと記述してありますが、今回は単純な配列な値の場合を確認します。
すると対象は一行だけでphp_count_recursiveを呼び出していることがわかります。

さらにphp_count_recursiveをおってみましょう。

PHPAPI int php_count_recursive(zval *array, long mode TSRMLS_DC) /* {{{ */
{
    long cnt = 0;
    zval **element;

    if (Z_TYPE_P(array) == IS_ARRAY) {
        if (Z_ARRVAL_P(array)->nApplyCount > 1) {
            php_error_docref(NULL TSRMLS_CC, E_WARNING, "recursion detected");
            return 0;
        }

        cnt = zend_hash_num_elements(Z_ARRVAL_P(array));
        if (mode == COUNT_RECURSIVE) {
            HashPosition pos;

            for (zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(array), &pos);
                zend_hash_get_current_data_ex(Z_ARRVAL_P(array), (void **) &element, &pos) == SUCCESS;
                zend_hash_move_forward_ex(Z_ARRVAL_P(array), &pos)
            ) {
                Z_ARRVAL_P(array)->nApplyCount++;
                cnt += php_count_recursive(*element, COUNT_RECURSIVE TSRMLS_CC);
                Z_ARRVAL_P(array)->nApplyCount--;
            }
        }
    }

    return cnt;
}

ここでも型チェックや再帰的に関数を呼び出している部分がありますが、本質的な部分は一行だけです。
変数cntを代入しているzend_hash_num_elementsを見てみましょう。
実装はzend_hash.cにあります。

ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
    IS_CONSISTENT(ht);

    return ht->nNumOfElements;
}

IS_CONSISTENTマクロはハッシュテーブルが破壊されていないかどうかを確認するものです。
さてここでようやく実装が見えましたね。
count関数の行っていることはhashtable構造体のnNumOfElementsを返却しているだけなのです。

結論

冒頭で出した2つのコードのパフォーマンスの違いはそこまで大きくないでしょう、ビッグオー的に計算量で表すとどちらもO(1)になるからです。

ただ実装で言うとメソッドの呼び出しが3つほど噛まれていますので、関数スタックにガツガツと何度も積み上げられることになります。
特にパフォーマンスに気を使う部分であれば、count関数の呼び出しは一度だけに限定するほうが良いでしょう。

個人的にはfor文の中に挟み込む方式は、あまり推奨しないかな。
コードは行儀、シンプルに誰でもわかるように書きべきでしょう。