レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ ソフトウェアタイマと遅延処理 ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

今回はソフトウェアタイマと遅延処理について見ていく。

ソフトウェアタイマと遅延処理

タイマは指定時間の経過後に指定の処理を行うソフトウェア機能で、タイマに設定した時間が経過したことをタイムアウトと呼ぶ。

Linuxには動的タイマとインターバルタイマが存在し、前者はカーネルが、後者はユーザが使用する。タイマ関数は遅延処理から呼び出されるためタイムアウトからしばらく(最大数百ミリ秒)してから実行される。

ソフトウェアタイマの他にも"遅延関数"も利用する。当該機能は指定時間の間、指定の処理を繰り返す。

動的タイマ

動的タイマの作成や終了は動的に行い、作成数の上限は設定されていない。動的タイマ用のデータ構造体は以下のように定義されている。

// include/linux/timer.h
struct tvec_t_base_s;

struct timer_list {
    struct list_head entry; // 双方向リスト
    unsigned long expires; // タイムアウト時間

    spinlock_t lock;
    unsigned long magic;

    void (*function)(unsigned long); // タイムアウト時に実行する関数アドレス
    unsigned long data; // 上記関数の引数

    struct tvec_t_base_s *base;
};

動的タイマの初期化及び追加は以下のように行われる。

// drivers/atm/lanai.c
static inline void lanai_timed_poll_start(struct lanai_dev *lanai)
{
    init_timer(&lanai->timer); // タイマの初期化
    lanai->timer.expires = jiffies + LANAI_POLL_PERIOD; // 引数設定
    lanai->timer.data = (unsigned long) lanai; // 関数を設定
    lanai->timer.function = lanai_timed_poll; // 関数で使用する引数を設定
    add_timer(&lanai->timer); // タイマを追加
}

動的タイマが既に登録されている場合には以下のようにタイムアウト値を変更する。

// drivers/atm/ambassador.c
static void do_housekeeping (unsigned long arg) {
  amb_dev * dev = (amb_dev *) arg;
  
  // could collect device-specific (not driver/atm-linux) stats here
      
  // last resort refill once every ten seconds
  fill_rx_pools (dev);
  mod_timer(&dev->housekeeping, jiffies + 10*HZ); // タイムアウトを指定し関数を再設定
  
  return;
}

初期化に使用されるinit_timer()の実装はシンプルで必要なメンバに初期値を設定しデータを保護するためにロックを取得する。`

// include/linux/timer.h
static inline void init_timer(struct timer_list * timer)
{
    timer->base = NULL;
    timer->magic = TIMER_MAGIC;
    spin_lock_init(&timer->lock);
}

次にタイマを追加するadd_timer()は以下のように定義されている。

// include/linux/timer.h
static inline void add_timer(struct timer_list * timer)
{
    __mod_timer(timer, timer->expires);
}

内部で__mod_timer()関数を呼び出しているのがわかる。

タイムアウト値を変更する場合に呼び出すmod_timer()関数の定義は以下。

int mod_timer(struct timer_list *timer, unsigned long expires)
{
    BUG_ON(!timer->function);

    check_timer(timer);

    if (timer->expires == expires && timer_pending(timer))
        return 1;

    return __mod_timer(timer, expires);
}

add_timer()同様、内部では__mod_timer()が呼び出されている。

タイマアウト時にカーネルはリストからタイマを削除するが、明示的に削除する方が良いケースもある。なぜなら休止中のプロセスがタイムアウト前に起こされタイマオブジェクトを削除する可能性があるからである。よってタイマ関数内部でタイマオブジェクトを削除することが推奨される。

動的タイマはCPUに対応しており、追加や更新を行なったCPU上で当該タイマは動作する。しかし削除の場合には他のCPUが保持しているタイマも指定できる。

動的タイマのデータ構造

tick毎にタイマリストをトラバースするのは非常にコストが高いためexpiresの値を用いてtick単位でいくつかのブロックに分割している。これによりexpiresの値毎に効率的にリストへのアクセスが可能となる。マルチプロセッサシステムではCPU毎にリストを保持している。

動的タイマの根管となるデータ構造はtvec_basesという変数でCPU毎に定義されている。

// kernel/timer.c
static DEFINE_PER_CPU(tvec_base_t, tvec_bases) = { SPIN_LOCK_UNLOCKED };

上記の変数のデータ構造はtvec_base_tと定義されている。

// kernel/timer.c
/*
 * per-CPU timer vector definitions:
 */
#define TVN_BITS 6
#define TVR_BITS 8
#define TVN_SIZE (1 << TVN_BITS)
#define TVR_SIZE (1 << TVR_BITS)

typedef struct tvec_s {
    struct list_head vec[TVN_SIZE]; // 64個
} tvec_t;

typedef struct tvec_root_s {
    struct list_head vec[TVR_SIZE]; // 256個
} tvec_root_t;
struct tvec_t_base_s {
    spinlock_t lock; // ロック変数
    unsigned long timer_jiffies; // 次に実行されるタイマ関数の実行時間
    struct timer_list *running_timer;
    tvec_root_t tv1; // 256個の要素を保持するリスト
    tvec_t tv2; // 64個の要素を保持するリスト
    tvec_t tv3; // 64個の要素を保持するリスト
    tvec_t tv4; // 64個の要素を保持するリスト
    tvec_t tv5; // 64個の要素を保持するリスト
} ____cacheline_aligned_in_smp;

typedef struct tvec_t_base_s tvec_base_t;

tv1からtv5の各要素は動的タイマのリストになっている。tvec_root_t型のtv1メンバは256個の要素を保持しており現時点から256tick以内にタイムアウトが来る全ての動的タイマをtv1に格納する。

tvec_t型のtv2からtv4のメンバは64個の要素を保持するリストで、各要素は動的タイマのリストを保持している。各メンバは現時点から16384(256 * 64)、1048576(16384 * 64)、67108864(1048576 * 64)tick以内にタイムアウトが来る全ての動的タイマを格納している。

tvec_t型のtv5は非常に大きな値でもexpiresメンバを持つ動的タイマにも対応が可能となっている。

構造体の関係は以下の図がわかりやすい。(詳解Linux Kernel)。

tv1 ~ tv5の関係は以下の図を作成した。

上記の個数はtick数を表している。tv1が保持している全てのソフトウェアタイマが実行された場合にはtv2のリスト要素からtv1を補充し、tv2はtv3から補充・・・というのを繰り返す。

timer_jiffiesは次に実行されるタイマ関数の実行時間でtimer_jiffiesjiffies以上の時にはタイマ関数は実行せず、timer_jiffiesjiffiesよりも小さくなった段階でタイマ関数を実行する。timer_jiffiesはシステム起動時にjiffiesで初期化されるが、その後はrun_timer_softirq()でのみ加算される。遅延処理の禁止や多くの割り込み発生のタイミングでtimer_jiffiesjiffiesから遅れを取る場合がある。

動的タイマのレースコンディション

動的タイマは非同期に動作するため削除可能な資源の扱いには注意する必要がある。タイマを停止する前に資源を解放すると存在しない資源に対してタイマからのアクセスが行われる可能性があり、必ずタイマを停止した後に対象の資源を解放する必要がある。

マルチプロセッサシステムにおいてdel_timer()を呼び出した時点では、タイマ関数が他のCPU上で実行中である可能性もあり解放した資源にアクセスしてしまう場合も考えられる。

// kernel/timer.c
/***
 * del_timer - deactive a timer.
 *
 * del_timer() deactivates a timer - this works on both active and inactive
 * timers.
 */
int del_timer(struct timer_list *timer)
{
    unsigned long flags;
    tvec_base_t *base;

    check_timer(timer);

repeat:
    base = timer->base;
    if (!base)
        return 0; // 停止に失敗
    spin_lock_irqsave(&base->lock, flags); // スピンロック
    if (base != timer->base) {
        spin_unlock_irqrestore(&base->lock, flags);
        goto repeat;
    }
    list_del(&timer->entry); // リストから削除
    /* Need to make sure that anybody who sees a NULL base also sees the list ops */
    smp_wmb(); // メモリバリア
    timer->base = NULL; // タイマを削除
    spin_unlock_irqrestore(&base->lock, flags); // スピンロックを解除

    return 1; // 停止に成功
}

前述の競合状態を回避するためにdel_timer_sync()を使用する。当該関数はリストからタイマを削除した後、当該タイマ関数が他のCPUで実行されていないかを確認し完了を待ち合わせる。

// kernel/timer.c
/***
 * del_timer_sync - deactivate a timer and wait for the handler to finish.
 * @timer: the timer to be deactivated
 */
int del_timer_sync(struct timer_list *timer)
{
    tvec_base_t *base;
    int i, ret = 0;

    check_timer(timer);

del_again:
    ret += del_timer(timer); // タイマを削除

    for_each_online_cpu(i) {
        base = &per_cpu(tvec_bases, i);
        if (base->running_timer == timer) { // タイマが動作中
            while (base->running_timer == timer) {
                cpu_relax(); // NOP命令の繰り返し
                preempt_check_resched(); // リスケジューリング
            }
            break;
        }
    }
    smp_rmb();
    if (timer_pending(timer)) // タイマの削除に成功しているかどうか
        goto del_again;

    return ret;
}

上記の関数は複雑で遅いためタイマ関数が再度タイマを動作させないことがわかっている場合にはdel_singleshot_timer_sync()を呼び出すことが推奨されている。

上記の他にも考えられるレースコンディションとして既に稼動状態のタイマのexpiresを変更する際に、タイマを削除して再度作成するような手順を取ると同一の処理(再作成)が複数走った時に両方のタイマ関数が混在してしてしまうと言ったことが起こる。タイマリストへのアクセスはロックを取得しSMPセーフになっているのでこのケースではmod_timer()を使用する必要がある。

動的タイマ処理

複雑なデータ構造での実装を行なっているがソフトウェアタイマ処理は高コストな処理となっておりLinux 2.6からは遅延処理(TIMER_SOFTIRQ)として実装されている。

// include/linux/interrupt.h
enum
{
    HI_SOFTIRQ=0,
    TIMER_SOFTIRQ,
    NET_TX_SOFTIRQ,
    NET_RX_SOFTIRQ,
    SCSI_SOFTIRQ,
    TASKLET_SOFTIRQ
};

run_timer_softirq()関数が遅延処理を行う。

// kernel/timer.c
static void run_timer_softirq(struct softirq_action *h)
{
    tvec_base_t *base = &__get_cpu_var(tvec_bases); // CPUに対応するtvec_base_t構造体を取得
    
    // jiffiesが次のタイムアウト時間よりも大きい(実行対象のタイマ関数が全て実行されていない)場合にはループを継続する
    if (time_after_eq(jiffies, base->timer_jiffies))
        __run_timers(base); // タイマ処理
}

// include/linux/jiffies.h
#define time_after_eq(a,b) \
   (typecheck(unsigned long, a) && \
    typecheck(unsigned long, b) && \
    ((long)(a) - (long)(b) >= 0))
#define time_before_eq(a,b)    time_after_eq(b,a)

上記で呼び出されている__run_timers()は以下のように定義されている。

// kernel/timer.c

// 指定された数値+2(N)を用いてtvNの範囲を指定する。
#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK

static inline void __run_timers(tvec_base_t *base)
{
    struct timer_list *timer;

    spin_lock_irq(&base->lock); // スピンロックの取得及びローカル割り込みの禁止
    // 実行されるべきソフトウェアタイマ処理が全て完了していない
    while (time_after_eq(jiffies, base->timer_jiffies)) {
        struct list_head work_list = LIST_HEAD_INIT(work_list);
        struct list_head *head = &work_list;
        int index = base->timer_jiffies & TVR_MASK; // 255以内
 
        /*
        * Cascade timers:
        */
        if (!index && // インデックスが0であればtv1のリストは実行完了している
            (!cascade(base, &base->tv2, INDEX(0))) && // 空ならtv2 -> tv1へ補充
                (!cascade(base, &base->tv3, INDEX(1))) && // 空ならtv3 -> tv2へ補充
                    !cascade(base, &base->tv4, INDEX(2))) // 空ならtv4 -> tv3へ補充
            cascade(base, &base->tv5, INDEX(3)); // 空ならtv5 -> tv4へ補充
        ++base->timer_jiffies; // timer_jiffiesの加算
        list_splice_init(base->tv1.vec + index, &work_list);
repeat:
        if (!list_empty(head)) { // 対象の時間に設定されたタイマが全て実行完了となるまで繰り返す
            void (*fn)(unsigned long);
            unsigned long data;

            timer = list_entry(head->next,struct timer_list,entry); // タイマを取得
            fn = timer->function; // 関数
            data = timer->data; // 引数
            list_del(&timer->entry); // エントリをリストから削除
            set_running_timer(base, timer); // タイマ関数のアドレスをrunning_timerに設定
            smp_wmb();
            timer->base = NULL;
            spin_unlock_irq(&base->lock); // ロックを解除
            {
                u32 preempt_count = preempt_count();
                fn(data); // タイマ関数の実行
                if (preempt_count != preempt_count()) {
                    printk("huh, entered %p with %08x, exited with %08x?\n", fn, preempt_count, preempt_count());
                    BUG();
                }
            }
            spin_lock_irq(&base->lock); // 再度ロックを取得及びローカル割り込みの禁止
            goto repeat; // 
        }
    }
    set_running_timer(base, NULL); // running_timerをクリア
    spin_unlock_irq(&base->lock); // ロックの解除
}

通常、jiffiestimer_jiffiesは同じタイミングで増加していくので一番外のループは一度しか実行されない。しかしrun_timer_softirq()の実行中にタイマ割り込みが発生した場合にはその割り込みでjiffiesがインクリメントされるのでそのタイミングでタイムアウトするソフトウェアタイマも考慮する必要がある。

動的タイマの使用例

nano_sleepシステムコールの実装であるsys_nanosleep()関数では動的タイマが使用されており以下のように定義されている。

// kernel/timer.c
asmlinkage long sys_nanosleep(struct timespec __user *rqtp, struct timespec __user *rmtp)
{
    struct timespec t;
    unsigned long expire;
    long ret;

    if (copy_from_user(&t, rqtp, sizeof(t))) // ユーザプロセスが定義したtimespecをカーネル空間へコピー
        return -EFAULT;

    if ((t.tv_nsec >= 1000000000L) || (t.tv_nsec < 0) || (t.tv_sec < 0))
        return -EINVAL;

    expire = timespec_to_jiffies(&t) + (t.tv_sec || t.tv_nsec); // timespecからjiffiesへ変換
    current->state = TASK_INTERRUPTIBLE; // インタラプト可能状態
    expire = schedule_timeout(expire); // リスケジューリング

    ret = 0;
    if (expire) { // まだtick数が残っている場合
        struct restart_block *restart;
        jiffies_to_timespec(expire, &t);
        if (rmtp && copy_to_user(rmtp, &t, sizeof(t)))
            return -EFAULT;
        
        // システムコールを再度実行
        restart = &current_thread_info()->restart_block;
        restart->fn = nanosleep_restart;
        restart->arg0 = jiffies + expire;
        restart->arg1 = (unsigned long) rmtp;
        ret = -ERESTART_RESTARTBLOCK;
    }
    return ret;
}

上記で呼び出されているschedule_timeout()は以下のように定義されている。

fastcall signed long __sched schedule_timeout(signed long timeout)
{
    struct timer_list timer;
    unsigned long expire;

    switch (timeout)
    {
    // スリープ可能最大時間が指定された場合
    case MAX_SCHEDULE_TIMEOUT:
        schedule();
        goto out;
    default:
        // 負の値の場合再度実行
        if (timeout < 0)
        {
            current->state = TASK_RUNNING;
            goto out;
        }
    }

    expire = timeout + jiffies; // タイムアウト値にjiffiesを加算した物をタイムアウトを設定

    // タイマの初期化及び追加
    init_timer(&timer);
    timer.expires = expire;
    timer.data = (unsigned long) current; // カレントプロセスのプロセスディスクリプタを引数に設定
    timer.function = process_timeout; // 自信を起床される関数
    add_timer(&timer);
    
    schedule(); // 再スケジューリング
    // 実行対象の関数は繰り返し実行されることはない
    del_singleshot_timer_sync(&timer);

    timeout = expire - jiffies;

 out:
    // タイマ関数で起床した場合には0、
    // 他の理由で起床した場合にはタイムアウトまでの残りのtick数を返す
    return timeout < 0 ? 0 : timeout;
}

上記でタイマ関数として設定されているprocess_timeout()は以下のように定義されている。

// kernel/timer.c
static void process_timeout(unsigned long __data)
{
    wake_up_process((task_t *)__data);
}

上記を見ると内部でwake_up_process()を用いて先ほど引数に設定したプロセスディスクリプタから、自身を起床させていることがわかる。

遅延関数

ソフトウェアタイマは数マイクロ秒以下のような短い時間スリープする場合には実用的ではない。例えばデバイスドライバではハードウェアが操作を完了するまでの数マイクロ秒待機する必要があるケースも存在し、最低でも1ミリ秒は待機する動的タイマは適切であるとは言えない。

上記の場合にカーネルudelay()またはndelay()を使用する。前者では指定マイクロ秒、後者では指定ナノ秒を引数に設定する。

// include/asm-i386/delay.h
#define udelay(n) (__builtin_constant_p(n) ? \
   ((n) > 20000 ? __bad_udelay() : __const_udelay((n) * 0x10c7ul)) : \
   __udelay(n))
    
#define ndelay(n) (__builtin_constant_p(n) ? \
   ((n) > 20000 ? __bad_ndelay() : __const_udelay((n) * 5ul)) : \
   __ndelay(n))

__builtin_constant_pマクロはコンパイルの組み込み関数で引数の値がコンパイル時に決定している時に真を返す。今回は引数がコンパイル時に決定していない場合に呼び出される__udelay()または__ndelay()を見ていく。

// arch/i386/lib/delay.c
void __udelay(unsigned long usecs)
{
    __const_udelay(usecs * 0x000010c7);  /* 2**32 / 1000000 (rounded up) */
}

void __ndelay(unsigned long nsecs)
{
    __const_udelay(nsecs * 0x00005);  /* 2**32 / 1000000000 (rounded up) */
}

上記から両者とも内部で__const_udelayを定義しているのがわかる。

// arch/i386/lib/delay.c
inline void __const_udelay(unsigned long xloops)
{
    int d0;
    xloops *= 4;
    __asm__("mull %0"
        :"=d" (xloops), "=&a" (d0)
        :"1" (xloops),"0" (cpu_data[_smp_processor_id()].loops_per_jiffy * (HZ/4)));
        __delay(++xloops);
}

loops_per_jiffyは単一のtickが何ループに相当するかを保持するメンバで、上記では指定の待ち時間をループ数に変換する。

次に上記で呼び出される__delay()の定義は以下。

// arch/i386/lib/delay.c
void __delay(unsigned long loops)
{
    cur_timer->delay(loops);
}

cur_timerは搭載しているタイマに依存しており、HPETやTSCが利用可能であれば1ループはCPUの1命令となり、両方とも利用できない場合には短い命令のループとなる。

時間管理システムコール

ユーザプロセスから日時の取得及び変更、タイマの作成を行う。

time(), gettimeofday()

time()システムコールgettimeofday()システムコールによって置き換えられたが後方互換性のための残されている。

gettimeofdayシステムコールsys_gettimeofday()関数で実装されている。

// kernel/time.c
asmlinkage long sys_gettimeofday(struct timeval __user *tv, struct timezone __user *tz)
{
    if (likely(tv != NULL)) { // 時刻用のデータ構造体が存在する
        struct timeval ktv;
        do_gettimeofday(&ktv); // 時間の取得
        if (copy_to_user(tv, &ktv, sizeof(ktv))) // ユーザ空間にコピー
            return -EFAULT;
    }
    if (unlikely(tz != NULL)) { // タイムゾーン用のデータ構造体が存在する
        if (copy_to_user(tz, &sys_tz, sizeof(sys_tz))) // ユーザ空間にコピー
            return -EFAULT;
    }
    return 0;
}

内部で時間取得に使用しているdo_gettimeofday()の定義は以下。

// arch/i386/kernel/time.c
void do_gettimeofday(struct timeval *tv)
{
    unsigned long seq;
    unsigned long usec, sec;
    unsigned long max_ntp_tick;

    do {
        unsigned long lost;

        seq = read_seqbegin(&xtime_lock);

        usec = cur_timer->get_offset(); // 前回のタイマ割り込みからの経過時間を取得
        lost = jiffies - wall_jiffies; // 失われたタイマ割り込みを取得

        sec = xtime.tv_sec; // UTCからの経過秒
        usec += (xtime.tv_nsec / 1000); // ナノ秒 -> マイクロ秒
    } while (read_seqretry(&xtime_lock, seq));

    // マイクロ秒の値が1秒以上存在する場合には秒に変換
    while (usec >= 1000000) {
        usec -= 1000000;
        sec++;
    }

    // 値をセット
    tv->tv_sec = sec;
    tv->tv_usec = usec;
}

ルート権限を保持するプロセスはsettimeofday()システムコールを使用して時刻の設定が可能で、内部ではsys_settimeofday()が呼ばれその内部ではdo_settimeofday()が呼び出されている。

// kernel/time.c
asmlinkage long sys_settimeofday(struct timeval __user *tv,
                struct timezone __user *tz)
{
    :

int do_sys_settimeofday(struct timespec *tv, struct timezone *tz)
{
    :

adjtimex()

システム時間はクロックドリフト(クロック周波数がずれる現象)により少しずつずれていく。そのズレをNTP(Network Time Protocol)などの時刻同期プロトコルを用いて定期的に実行しtickを修正する。これを行うためのユーティリティとしてadjtimex()を提供している。

asmlinkage long sys_adjtimex(struct timex __user *txc_p)
{
    struct timex txc;      /* Local copy of parameter */
    int ret;

    // ユーザ空間からデータをコピー
    if(copy_from_user(&txc, txc_p, sizeof(struct timex)))
        return -EFAULT;
    ret = do_adjtimex(&txc); // タイマを修正
    // ユーザ空間にデータをコピー
    return copy_to_user(txc_p, &txc, sizeof(struct timex)) ? -EFAULT : ret;
}

setitimer()

Linuxではインターバルタイマという特殊なタイマを提供しており、プロセスに定期的にシグナルを送信することが可能。

setitimerシステムコールの実装であるsys_setitimer()関数の定義は以下。

// kernel/itimer.c
/* SMP: Again, only we play with our itimers, and signals are SMP safe
 *      now so that is not an issue at all anymore.
 */
asmlinkage long sys_setitimer(int which,
                  struct itimerval __user *value,
                  struct itimerval __user *ovalue)
{
    struct itimerval set_buffer, get_buffer;
    int error;

    if (value) {
        if(copy_from_user(&set_buffer, value, sizeof(set_buffer)))
            return -EFAULT;
    } else
        memset((char *) &set_buffer, 0, sizeof(set_buffer));

    error = do_setitimer(which, &set_buffer, ovalue ? &get_buffer : NULL);
    if (error || !ovalue)
        return error;

    if (copy_to_user(ovalue, &get_buffer, sizeof(get_buffer)))
        return -EFAULT; 
    return 0;
}

第一引数には以下のいずれかを指定する。

// include/linux/time.h
/*
 * Names of the interval timers, and structure
 * defining a timer setting.
 */
#define    ITIMER_REAL 0 // 実経過時間。設定された時間がくるとプロセスはSIGALRMを受信する
#define    ITIMER_VIRTUAL  1 // プロセスがユーザモードで動作した時間。設定された時間がくるとプロセスはSIGVTALRMを受信する
#define    ITIMER_PROF 2 // ユーザモード及びカーネルモードで動作した時間。設定された時間が来るとプロセスはSIGVTALRMを受信する。

第二引数にはitimerval構造体をとり、it_intervalには最初の実行時間間隔、it_valueには再度タイマを自動起動する時に指定する実行時間間隔を指定する(単発の場合には0を指定)。

struct  itimerval {
    struct timeval it_interval;    /* timer interval */
    struct timeval it_value;   /* current value */
};

第三引数にもitimerval構造体をとるがこれには前回設定した値が設定される(NULLを指定することも可能)

プロセスディスクリプタの構造体であるtask_structには上記のITIMER_REALITIMER_VIRTUAL及びITIMER_PROFに対応するメンバを保持している。

// include/linux/sched.h
struct task_struct {
    volatile long state;  /* -1 unrunnable, 0 runnable, >0 stopped */
    struct thread_info *thread_info;
    atomic_t usage;
    
    :
    (省略)
    :
    
    unsigned long it_real_value, it_real_incr; // ITIMER_REAL
    cputime_t it_virt_value, it_virt_incr; // ITIMER_VIRTUAL
    cputime_t it_prof_value, it_prof_incr; // ITIMER_PROF
    struct timer_list real_timer; // ITIMER_REALのための動的タイマリスト
    :

it_***_incrはシグナルを発生間隔をtick数で保持しており、it_***_valueは次のシグナル発生までの残りtick数を保持している。

ITIMER_REALは動的タイマを用いて実現されており、real_timerITIMER_REALのための動的タイマリストを保持するメンバである。

real_timerはプロセスディスクリプタの初期化時に適切に設定される。

// include/linux/init_task.h
#define INIT_TASK(tsk) \
{                                  \
   .state      = 0,                       \
   .thread_info    = &init_thread_info,                \
   .usage      = ATOMIC_INIT(2),              \
   .flags      = 0,                       \
   .lock_depth = -1,                      \
   .prio       = MAX_PRIO-20,                 \
   .static_prio    = MAX_PRIO-20,                 \
   .policy     = SCHED_NORMAL,                 \
   .cpus_allowed   = CPU_MASK_ALL,                 \
   .mm     = NULL,                        \
   .active_mm  = &init_mm,                 \
   .run_list   = LIST_HEAD_INIT(tsk.run_list),         \
   .time_slice = HZ,                       \
   .tasks      = LIST_HEAD_INIT(tsk.tasks),            \
   .ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children),      \
   .ptrace_list    = LIST_HEAD_INIT(tsk.ptrace_list),      \
   .real_parent    = &tsk,                     \
   .parent     = &tsk,                     \
   .children   = LIST_HEAD_INIT(tsk.children),         \
   .sibling    = LIST_HEAD_INIT(tsk.sibling),          \
   .group_leader   = &tsk,                     \
   .real_timer = {                     \
       .function   = it_real_fn                \
   },                              \
   
    :
    (省略)

real_timerに設定されているit_real_fn()は以下のように定義されている。

// kernel/itimer.c
void it_real_fn(unsigned long __data)
{
    struct task_struct * p = (struct task_struct *) __data;
    unsigned long interval;

    send_group_sig_info(SIGALRM, SEND_SIG_PRIV, p); // シグナルの送信
    interval = p->it_real_incr; // インターバルを取得
    if (interval) { // インターバルが設定されている場合
        if (interval > (unsigned long) LONG_MAX)
            interval = LONG_MAX;
        p->real_timer.expires = jiffies + interval; // 期限を設定
        add_timer(&p->real_timer); // 動的タイマの追加
    }
}

ITIMER_VIRTUAL及びITIMER_PROFはプロセスの実行時間に依存しているため動的タイマは使用せず、tick毎に発生する割り込み(PITタイマ割り込み若しくはローカルタイマ割り込み)ハンドラ内部で呼び出されるupdate_process_times()で処理が行われる。

// kernel/timer.c
/*
 * Called from the timer interrupt handler to charge one tick to the current 
 * process.  user_tick is 1 if the tick is user time, 0 for system.
 */
void update_process_times(int user_tick)
{
    struct task_struct *p = current;
    int cpu = smp_processor_id();

    /* Note: this timer irq context must be accounted for as well. */
    if (user_tick)
        // ユーザモードでのCPU使用時間の計算
        account_user_time(p, jiffies_to_cputime(1));
    else
        // カーネルモードでのCPU使用時間の計算
        account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
    run_local_timers();
    if (rcu_pending(cpu))
        rcu_check_callbacks(cpu, user_tick);
    scheduler_tick();
}

jiffies_to_cputime()はtickの間隔CPU時間に変換したもので単純にtickのインターバルがCPU使用時間としてそのまま計上される。

account_user_time()の定義は以下。

/*
 * Account user cpu time to a process.
 * @p: the process that the cpu time gets accounted to
 * @hardirq_offset: the offset to subtract from hardirq_count()
 * @cputime: the cpu time spent in user space since the last update
 */
void account_user_time(struct task_struct *p, cputime_t cputime)
{
    struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
    cputime64_t tmp;

    p->utime = cputime_add(p->utime, cputime);

    /* Check for signals (SIGVTALRM, SIGPROF, SIGXCPU & SIGKILL). */
    check_rlimit(p, cputime);
    account_it_virt(p, cputime); // ユーザモードでのCPU使用時間の算出
    account_it_prof(p, cputime); // ユーザ及びカーネルモードでのCPU使用時間の算出

    /* Add user time to cpustat. */
    tmp = cputime_to_cputime64(cputime);
    if (TASK_NICE(p) > 0)
        cpustat->nice = cputime64_add(cpustat->nice, tmp);
    else
        cpustat->user = cputime64_add(cpustat->user, tmp);
}

ユーザモードでのCPU使用時間を算出しているaccount_it_virt()の定義は以下。

// kernel/sched.c
/*
 * Do the virtual cpu time signal calculations.
 * @p: the process that the cpu time gets accounted to
 * @cputime: the cpu time spent in user space since the last update
 */
static inline void account_it_virt(struct task_struct * p, cputime_t cputime)
{
    cputime_t it_virt = p->it_virt_value;

    /* タイマが設定されておりCPU使用時間が0でない場合 */
    if (cputime_gt(it_virt, cputime_zero) &&
        cputime_gt(cputime, cputime_zero)) {
        if (cputime_ge(cputime, it_virt)) { // 指定の時間が経過していた場合
            it_virt = cputime_add(it_virt, p->it_virt_incr);
            send_sig(SIGVTALRM, p, 1); // シグナルの送信
        }
        it_virt = cputime_sub(it_virt, cputime);
        p->it_virt_value = it_virt;
    }
}

上記から単純に設定した時間分の実行を既に行なっている場合にシグナルを送信しているのがわかる。

ユーザ及びカーネルモードでのCPU使用時間の算出を行なっているaccount_it_prof()の定義は以下。

// kernel/sched.c
/*
 * Do the virtual profiling signal calculations.
 * @p: the process that the cpu time gets accounted to
 * @cputime: the cpu time spent in user and kernel space since the last update
 */
static void account_it_prof(struct task_struct *p, cputime_t cputime)
{
    cputime_t it_prof = p->it_prof_value;

    /* タイマが設定されておりCPU使用時間が0でない場合 */
    if (cputime_gt(it_prof, cputime_zero) &&
        cputime_gt(cputime, cputime_zero)) {
        if (cputime_ge(cputime, it_prof)) { // 指定の時間が経過していた場合
            it_prof = cputime_add(it_prof, p->it_prof_incr);
            send_sig(SIGPROF, p, 1); // シグナルの送信
        }
        it_prof = cputime_sub(it_prof, cputime);
        p->it_prof_value = it_prof;
    }
}

参照している変数や送信するシグナルが異なるだけで先ほどのaccount_it_virt()と処理は類似している。

update_process_times()で呼び出しているaccount_system_time()では上記のaccount_it_virt()のみを呼び出しCPUの使用時間を算出及びタイマの起動を行なっている。

alarm()

alarm()システムコールITIMER_REALで見たプロセスディスクリプタが保持しているreal_timer()を使用しているためsetitimer()システムコールと併用することができない。

// kernel/timer.c
/*
 * For backwards compatibility?  This can be done in libc so Alpha
 * and all newer ports shouldn't need it.
 */
asmlinkage unsigned long sys_alarm(unsigned int seconds)
{
    struct itimerval it_new, it_old;
    unsigned int oldalarm;

    it_new.it_interval.tv_sec = it_new.it_interval.tv_usec = 0;
    it_new.it_value.tv_sec = seconds;
    it_new.it_value.tv_usec = 0;
    do_setitimer(ITIMER_REAL, &it_new, &it_old);
    oldalarm = it_old.it_value.tv_sec;
    /* ehhh.. We can't return 0 if we have an alarm pending.. */
    /* And we'd better return too much than too little anyway */
    if ((!oldalarm && it_old.it_value.tv_usec) || it_old.it_value.tv_usec >= 500000)
        oldalarm++;
    return oldalarm;
}

POSIXタイマ

POSIXタイマはユーザモードプロセス向けに導入された比較的新しいタイマで、マルチプロセスやリアルタイムプロセスに有効である。POSIXタイマはPOSIXクロックという仮想的なタイマ資源を用いており、POSIXタイマを使用する時はベースとなるPOSIXクロックを指定しタイマを生成する。

従来のタイマとの差異は以下の2点。

  • 従来のタイマではタイムアウト時に固定のシグナルをプロセスに送信することしかできなかったが、POSIXタイマでは任意のシグナルをスレッドグループまたは指定のシングルスレッドに対して送信できる。
  • 従来のタイマではタイムアウトの発生回数に関わらずプロセスがシグナルを受け取るのは未処理であるシグナルのうちの最初のシグナルのみだったが、POSIXタイマでは受け取るのは最初のシグナルだけだがタイムアウトの発生回数をtimer_getoverrun()で取得することができる。

POSIXタイマにはいくつかの種類が存在し以下のように定義されている。

// include/linux/time.h
/*
 * The IDs of the various system clocks (for POSIX.1b interval timers).
 */
#define CLOCK_REALTIME       0
#define CLOCK_MONOTONIC      1
#define CLOCK_PROCESS_CPUTIME_ID 2
#define CLOCK_THREAD_CPUTIME_ID     3
#define CLOCK_REALTIME_HR   4
#define CLOCK_MONOTONIC_HR   5

POSIXタイマは動的タイマを使用することでPOSIXタイマを実装しており、前述のITIMER_REALに類似している。

参考