カーネルタイマは何故リストで管理されているのか

Linux

カーネルタイマは何故リストで管理されているのか、という理由がわかった気がするのでメモ. カーネルタイマは expires (点火する時間)で5段階に場合わけされて管理されているが、ロックはこの5段階ごとに保持されている. 何故タイマ毎にロックをしないのだろう? その方がロックの粒度が小さくなり、並列度が増すはずだ.
仮に timer_list 構造体が spinlock_t lock 持っていたとして、カーネル側の実装は以下のようにすればよさげに見える.

/* kernel side functions */
void __run_timers(void)
{
    while( timer_list_has_timers(lists) ){
        timer = get_next_timer();
        fn = timer->function;
        data = timer->data;
        ...
        spin_lock_irq( &timer->lock );
        detach_timer( timer );
        fn( data );
        spin_unlock_irq( &timer->lock );
    }
}

int add_timer( struct timer_list *timer )
{
    spin_lock_irqsave( &timer->lock, flags );
    ...
    add_timer_internal( timer );
    ...
    spin_unlock_irqsave( &timer->lock, flags );
}

int del_timer( struct timer_list *timer )
{
    spin_lock_irqsave( &timer->lock, flags );
    ...
    detach_timer( timer );
    ...
    spin_unlock_irqsave( &timer->lock, flags );
}

でもこれではダメで、Linux のタイマのコールバック関数の中には、呼び出しの契機となったタイマに対して破壊的な操作( free されても良いように！ ) 配慮されている:

/* kernel timer client side functions */
void timer_handler(unsigned long data)
{
    struct timer_list *timer = data;
    ...
    timer->expires = jiffies + 3*HZ;
    kfree( mytimer );
}

void timer_start(void)
{
    struct timer_list *timer;
    timer = kmalloc( GFP_KERNEL, sizeof(struct timer_list) );
    init_timer( timer );
    timer->function = timer_handler;
    timer->data = timer;
    timer->expires = jiffies + 3*HZ;

    add_timer( timer );
}

add_timer, del_timer などのカーネルタイマAPIは、EXPORT_SYMBOLされており、カーネルモジュールからも呼び出しを行うことができる. よって、(カーネルタイマの実装を知らない)プログラマがカーネルタイマを使ってプログラムを書くことを想定すると、「コールバック関数内ではタイマを触らないでください」という暗黙の制約はあまりよろしくない.
これをできるようにするためには、Linux カーネル側で、「一度タイマをコールバックしたらもう触らない」という風にすれば良い. すると、__run_timersを以下のように修正すればよさげである.

void __run_timers(void)
{
    while( timer_list_has_timers(lists) ){
        timer = get_next_timer();


        spin_lock_irq( &timer->lock );
        ...
        fn = timer->function;
        data = timer->data;
        detach_timer( timer );
        spin_unlock_irq( &timer->lock );
        ...
        fn ( data ) ;
        ...
    }
}

実際現在のLinuxカーネル(2.6.27.23)では「一度タイマをコールバックしたらもう触らない」ようにしている. 上記のコードとの違いは、ロックを保持しているのがタイマ毎か、点火する時間で分けた5段階のリスト毎に保持しているか、という辺りのみである*1.
さて、これはうまく動くんだろうか? 結果からいうと、ダメだ. この場合、以下のようなクリティカルセクションがロックから露出してしまっている:

  • __run_timers の spin_unlock_irq の直後にdel_timerなどタイマへのポインタを参照する関数が呼ばれた場合.

このタイミングでタイマのステートを変更されると、意図しない挙動になる可能性がある. 例えば、 (カーネルが)コールバックしたハンドラの中で行われる処理が大変重く、その途中で別のスレッドから del_timer が発行されたとしよう. del_timer を処理中に、ハンドラ内で kfree されると、del_timer へのポインタが無効になり、危険である.
この問題を解決するには、コールバックを行っている最中にロックを保持しておけばよい. が、今度は最初に述べたような問題が生じてしまう.

この問題が生じている原因と解決策

上記例で述べた問題の原因は、

  • セマンティクス(後方互換)の維持
  • カーネルタイマ1つ1つのステートが変更される可能性がある区間にロックが必要

という2つを同時に満たそうとしたために発生している.
これを解決するにはタイマ毎ではなく、もう一段大きな粒度でロックする必要がある. Linux では、これが時間で区切られた5段階のリストであった、ということらしい.

*1:そういう風に、擬似コードを書いているつもりですが、何かまずい点があったら教えてください.^^;