花粉激し杉。花の粉パランのおつとめソングを聴きながら花粉日和を過ごしている今日この頃です。

さて、設定された時刻でtimeoutする必要のある大量のオブジェクトがあって、これらに自動expire機能を持たせる場合、
普通は全オブジェクトをリストにしておいて定期的に一部または全部を辿ってtimeoutしていたらdestroy、のような処理をする訳ですが、
くしゃみをしながら効率の良い実装を思いついたので基幹部分を作ってみました。

X1, X2, ..., Xn のオブジェクトがあって、timeoutメンバに生存限界時刻が格納されているとする。
X(t) が timeout=t を表すとしよう。

ここで時間別のタイムアウトテーブルを用意する。

現在時刻 = 123000

timeout[9] X98(123010) X99(123010) ...          ※あと10秒
timeout[8] X97(123009) ...                      ※あと9秒
       :
timeout[1] X4(123002) X5(123002) ...            ※あと2秒
timeout[0] X1(123001) X2(123001) X3(123001) ... ※あと1秒

こんな感じで各timeout毎にグループを作ってリストにしておく。expire のチェックは1秒間隔で行えばいいとして、次の expire チェックでは timeout[0] のリストだけをチェックすれば十分である。
その後はこのテーブルをシフトさせて、

現在時刻 = 123001

timeout[9]                                     ※あと10秒
timeout[8] X98(123010) X99(123010) ...         ※あと9秒
timeout[7] X97(123009) ...                     ※あと8秒
       :
timeout[0] X4(123002) X5(123002) ...           ※あと1秒

とさせて、以下同様にくり返せばok。

さて、任意のオブジェクトは、必要であれば timeout を延長することができる。
上の状態から X4 の timeout を5秒後に再設定する場合は、X4 を timeout[0] のリストからの削除して、timeout[4] のリストへ追加すればいい。

現在時刻 = 123001

timeout[9]                                     ※あと10秒
timeout[8] X98(123010) X99(123010) ...         ※あと9秒
timeout[7] X97(123009) ...                     ※あと8秒
       :
timeout[4] X4(123006)                          ※あと5秒
       :
timeout[0] X5(123002) ...                      ※あと1秒

ところで、timeout[] 配列は有限であり、今回は長さ10の配列で、timeout[9] が末尾となる。
X4 の timeout を今度は5秒ではなく15秒後に設定したい場合は、timeout[15] に設定したい所だが存在しないので、末尾の timeout[9] に入れなおす。

現在時刻 = 123001

timeout[9] X4(123016)                          ※あと10秒(以上)
timeout[8] X98(123010) X99(123010) ...         ※あと9秒
timeout[7] X97(123009) ...                     ※あと8秒
       :
timeout[0] X5(123002) ...                      ※あと1秒

この状態で8秒経つと8回expireチェックが走り、以下のような状態となる。

現在時刻 = 123009

timeout[9]                                 ※あと10秒
       :
timeout[1] X4(123016)                      ※あと2秒(以上)
timeout[0] X98(123010) X99(123010) ...     ※あと1秒

X98, X99 はテーブル通りの残り時間なのでいいとして、X4の寿命はまだ残り7秒ある(15秒に設定してから8秒しか経っていないので)。
さらに1秒経つと以下のようになる。

現在時刻 = 123010

timeout[9]                     ※あと10秒
timeout[8]                     ※あと9秒
       :
timeout[1]                     ※あと2秒
timeout[0] X4(123016)          ※あと1秒(以上)

よってtimeout[0]に所属するオブジェクトは、残り時間1秒であるという仮定は成り立たないため、
expireチェックでもちゃんと残り秒数を調べてからtimeout処理をしなければならない。
残り秒数が1以下でないオブジェクトは、再度残り時間に対応するtimeoutテーブルに登録することにする。

現在時刻 = 123011

timeout[9]                     ※あと10秒以上
       :
timeout[4] X4(123016)          ※あと5秒以上
       :
timeout[0]                     ※あと1秒以上

このようにexpireチェック時にtimeout[0]のオブジェクトの残り秒数を調べ、必要であればdestroyまたは再配置を行うのであれば、
timeoutを大きくする方向で設定する場合は、いちいちリストからの削除追加しなくても良くなる。(別にやってもいい)
逆にtimeoutを小さくする場合は、リストの削除追加は *必須* になる。

というわけで、上記構造を簡単に実現するためのマクロを作った。
使い方は sys/queue.h とほぼ同じインターフェイス。サンプル。

そのうち時期を見てSEILのNATとfilterのステートで使ってみるテスト。
ちなみにpfもこういう工夫はしてなかった。その代わり、毎回全ステートを調べるのではなく一定数ずつ調べることで重くなるのを防いでいた。