linux kernelにおけるtimerについて(Timing Measurementsについて)

はじめに

user landで見えるtimerは時刻の取得やsiginfoとか、epollといったselect系など関数でのtimeoutの設定で用いられるが、kernel側でのtimerの利用はこれとは大きく異なる¹。

本記事ではkernel上でのtimer全般についてまとめている。Linux (User) Programmingの範疇のtimerの扱われ方はTLPI(The Linux Programming Interface)のch.23(TIMERS AND SLEEPING)がかなり詳しい。

timer interruptも含まれるので、interrupt自体を知っている必要があるが、今回はinterruptについて幹の部分だけ追った上で、timerに関係するコードを追いたいとおもう。timer interruptを先取りする理由は、一般論から話すよりも具体例を先に見ていったほうが良さそうという思惑から。

timerの部分は定数が多く出てくるので、用語だけでなく、数値の確認も行う。

reference

Understanding Linux Kernel ch.4 & 6 linux2.6.11をベースに扱っているので本記事でもそれに沿う。

Glossary

TSC(Timer Stamp Counter): receive the clock ticks from an external oscilator e.g) 2.4GHz rdtscでcounterを取得できる。後発にHPET(High Precision Event Timer)があるが、linux2.6.11ではdefaultで使用しないことになっているので、省略。
PIT(Programmable Interval Timer): 8254 CMOS chip timer interrupt(IRQ0)を周期的に(1msごとに)発生させるために用いる。周波数は、1193182[Hz]。こちらは、CPUごとにPITがあるわけではなく、I/O APICでredirectするcpuを決める。linux2.6wでは、timer_interruptがISR(Interrupt Service Routine)として呼ばれる。
RTC(Real Time Clock) .. IRQ8 interruptを発する(が、interrupt発生装置としては未使用)。linuxでは限られた場所でしか使われてない²
CPU local timer: local APIC timerで各cpuに一つづつある。LVT(Local Vector Table)の0x320にLVT Timer Registerがあるので、そちらで設定する(他にもLVT内のentryを設定する必要がある)。linuxでは、bus clock signal*16回ごとにcounterがdecreaseするようになっている。

他に本では、TSCのより良いとされるHPET(High Precision Event Timer)やACPI Power Management Timerも出てくるが、TSCの場合のみに絞る³。

interrupt関連の用語については、http://cstmize.hatenablog.jp/entry/2019/03/20/xv6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8Interrupt%E3%81%AE%E6%8C%99%E5%8B%95 のGlosaryを参考のこと。

Constants

いろいろ定義されているのでみていく⁴

// include/asm-i386/timex.h
// internal oscillator frequency
// // CONFIG_X86_ELAN is no set in x86
#define CLOCK_TICK_RATE 1193182

// include/asm-i386/param.h
# define HZ        1000       /* Internal kernel timer frequency */
# define USER_HZ   100        /* .. some user interfaces are in "ticks" */
# define CLOCKS_PER_SEC       (USER_HZ)   /* like times() */

// include/linux/jiffies.h
#define LATCH  ((CLOCK_TICK_RATE + HZ/2) / HZ)    /* For divider */ // => 1193

// NOM .. nominator
// DEN .. denominator
// LSH.. shift ( for resolution) (SH_DIV means "div with shift (for accuracy)")
// ((NOM / DEN) << LSH) .. (quotient) << LSH
// ((NOM % DEN) << LSH) / DEN .. [(reminder)/DEN] << LSH. Note that [(reminder)/DEN] is nearly decimal part of (double)(NOM / DEN)
// (((NOM % DEN) << LSH) + DEN / 2) / DEN ..  [(reminder)/DEN with rounding] << LSH
// SH_DIV(NOM,DEN,LSH) is almost same as the value of `(double)(NOM/DEN) << LSH`
#define SH_DIV(NOM,DEN,LSH) (   ((NOM / DEN) << LSH)                    \
                             + (((NOM % DEN) << LSH) + DEN / 2) / DEN)

// ACTHZ(actual HZ)
#define ACTHZ (SH_DIV (CLOCK_TICK_RATE, LATCH, 8)) // 1000<<8 + 39=256039

/* TICK_NSEC is the time between ticks in nsec assuming real ACTHZ */
// also, it's used in `unsigned long tick_nsec` in `kernel/timer.c`
#define TICK_NSEC (SH_DIV (1000000UL * 1000, ACTHZ, 8)) // 3905 << 8 + 168 = 999848

/* TICK_USEC is the time between ticks in usec assuming fake USER_HZ */
// also, it's used in `unsigned long tick_usec` in `kernel/timer.c`
#define TICK_USEC ((1000000UL + USER_HZ/2) / USER_HZ) // 1000050UL/100 = 10000"

/* TICK_USEC_TO_NSEC is the time between ticks in nsec assuming real ACTHZ and */
/* a value TUSEC for TICK_USEC (can be set by adjtimex)        */
#define TICK_USEC_TO_NSEC(TUSEC) (SH_DIV (TUSEC * USER_HZ * 1000, ACTHZ, 8))

各種timerの初期設定

linux2.6では、PIT, TSC, local APIC timerの設定を順に行う。(TSC, local APIC timerは最初に設定されたPITをもとにセットされる)

今回は概要だけ述べてとりあえず、timerに関する全体像を把握したいと考えている。timerのcalibrationの実装はくせがある(けど、結構面白い)ので、またの機会にまとめたい。

PIT

start_kernel -> init_IRQ -> setup_pit_timerでLATCH(=1193)をi8254にセットする。1193182[Hz]だったからinterruptが1[ms]ごとにIRQ0が発生するようにする(というよりそうなるようにLATCHを設定してる)

TSC

time_init:
  - set xtime and wall_to_monotonic global variable (xtime: `struct timespec xtime __attribute__ ((aligned (16)));`)
  - select_timer: find most preferred working timer. Initialize and take it.
    - timers[i]->init(clock_override): use timer_hpet_init or timer_pmtmr_init or `init_tsc`. In x86, `init_tsc` is selected.

time_init -> select_timer -> timers[i]->init( same as init_tsc) -> calibrate_tscでTSCの設定(クロック周波数は機種によって異なるため、動的に決める。そこで、PITを利用してTCSの設定を行う)

local APIC Timer

inuxでは、PITを用いて、init⁵ -> smp_boot_cpus -> setup_boot_APIC_clock -> calibrate_APIC_clockで周波数を算出し、setup_APIC_timer(calibration_result);で1[ms]ごとにlocal APIC timer interruptを発生するようにさせる。

timer interrupt

以下ではPITとlocal APIC timerのinterruptについて述べる。

PITのtimer interrupt

I/O APICを経由するので、Interrupt ReQuest lineとvector numberを結びつける必要がある。また、vector numberとそのcallbackのヒモ付(IDTの設定)も必要となる。

IRQ0の設定

IRQの設定の方は start_kernel -> time_init -> time_init_hook -> setup_irq(0, &irq0);で設定される。この関数は本質的には、I/O APICのInterrupt Redirection Tableに設定を書き込む。設定方法は、 (仕様書)https://pdos.csail.mit.edu/6.828/2018/readings/ia32/ioapic.pdf の3.2.4. IOREDTBL[23:0]を見ればよい。

setup_irq:
  - desc->handler->startup(irq):
    - startup_edge_ioapic(same as startup_edge_ioapic_irq):
    - __unmask_IO_APIC_irq:
      - __modify_IO_APIC_irq: disable Interrupt Mask(bit16) in Redirection Table Entry

IRQ0のInterruptをONにするために、Interrupt Maskをdisableするだけだ。ちなみに、Interrupt Redirection Tableの初期設定は、init[^init_func] -> smp_prepare_cpus -> smp_boot_cpus -> smpboot_setup_io_apic -> setup_IO_APIC -> setup_IO_APIC_irqsで行っている。この関数一見複雑に見えるが、やってることは単純で、24entryを一つづつ埋めて、最後に

// arch/i386/kernel/io_apic.c
void __init setup_IO_APIC_irqs(void) { 
  // skip
  io_apic_write(apic, 0x11+2*pin, *(((int *)&entry)+1));
  io_apic_write(apic, 0x10+2*pin, *(((int *)&entry)+0));

として、書き込む。

あと、ISR(Interrupt Service Routine)を実行するためのglobal変数irq_desc[idx=0]に必要な情報を詰める。今回の場合、

// arch/i386/mach-default/setup.c
static struct irqaction irq0  = { timer_interrupt, SA_INTERRUPT, CPU_MASK_NONE, "timer", null, null};

が引数として渡ってくる。IRQ0の場合、ISR(Interrupt Service Routine)はtimer_interruptである。SA_INTERRUPTはISRの突入時にeflags.IFがdisableのママであることを要請するflagである。ここあたりは、interruptやpreemptの回で紹介できればと思う。

IDTの設定

こちらもちょっと複雑だ。interrupt全般の設定は、start_kernel -> init_IRQにて、以下のように設定される:

// init_IRQ
    for (i = 0; i < (NR_VECTORS - FIRST_EXTERNAL_VECTOR); i++) {
        // #define FIRST_EXTERNAL_VECTOR   0x20
        int vector = FIRST_EXTERNAL_VECTOR + i;
        if (i >= NR_IRQS)
            break;
        // void set_intr_gate(unsigned int n, void *addr)
        // // _set_gate(idt_table+n,14,0,addr,__KERNEL_CS);
        if (vector != SYSCALL_VECTOR) 
            set_intr_gate(vector, interrupt[i]);
    }

初期設定では、vector32+iとinterrupt handlerのindexiが対応しているが、(Symmetric)MultiProcessorの場合は、更にこの設定が上書きされるようだ。

init[^init_func] -> smp_prepare_cpus -> smp_boot_cpus -> smpboot_setup_io_apic -> setup_IO_APIC -> check_timer -> set_intr_gate(vector, interrupt[0]);で定義されているようだ。vectorはvector = assign_irq_vector(0);の処理から、FIRST_DEVICE_VECTOR»0x31になるっぽい。linuxでは、 Vectors 0x20-0x2f are used for ISA(Industry Standard Architecture) interrupts.と有り、古い規格(ISA)で遅いので、使われていないようだ[^timer_isa]。(TODO: ここあまり自信ない..)

interruptの挙動

PITは interruptが1[ms]ごとにIRQ0が発生するように設定しているのだった。

interrupt gateなので、interrupt発生直後ではeflags.IF=OFFになっており、

interrupt->common_interrupt->do_IRQ:
  # eflags.IF=OFFのまま
  - irq_enter
  - __do_IRQ->handle_IRQ_event(irq, regs, desc->action):
    - local_irq_enable(): eflags.IF=ONに if `!(action->flags & SA_INTERRUPT)` [今回は`irq0`から条件を満たす]
    - call ISR(interrupt service routine) [IRQ0の場合、timer_interruptが実行される]
      - jiffies_64++; update_times(): system time(jiffies, `struct timespec xtime`)の更新
      - smp_local_timer_interrupt: 個別のCPUで済む処理(後述)
    - local_irq_disable(): eflags.IF=OFFに
  - irq_exit: 条件を満たせばdo_softirqが実行される

IRQ0のISR(interrupt Service Routine)の役割 : system time(jiffies, struct timespec xtime)の更新。個別のcpuで済むものはsmp_local_timer_interruptに処理を移譲する。

smp_local_timer_interruptについては、 local APIC timerのtimer interruptで出てくるので、次章で述べる。

local APIC timerのtimer interrupt

local APIC timerから発するinterruptはlocal APIC期限なので、IRQ number(I/O APICとexternal deviceを結ぶ線)はない。そのかわり、local APIC側での設定(LVTの設定)は必要である。加えて、IDTでの設定も見る。

LVTの設定

LVT(Local Vector Table)とは、local APICのregisterたちのRead/Writeができるtableのことだった。

init[^init_func] -> smp_boot_cpus -> setup_boot_APIC_clock -> setup_APIC_timer -> __setup_APIC_LVTT -> apic_write_around(APIC_LVTT, APIC_LVT_TIMER_PERIODIC | LOCAL_TIMER_VECTOR)でlocal APICのLVT timer register(320H)にLOCAL_TIMER_VECTOR(0xef=237)を紐付ける。init_IRQで初期化されたもの(vector[LOCAL_TIMER_VECTOR])をそのまま使う。

IDTの設定

こちらは、

start_kernel -> init_IRQ -> intr_init_hook -> apic_intr_init にて、

set_intr_gate(LOCAL_TIMER_VECTOR, apic_timer_interrupt); とセットされる。

interruptの挙動

local APIC timerの役割は個別のCPUのprocess switchingなどを行う役割を担っている。1[ms]ごとにlocal APIC timer interruptを発生するようにさせるのだった。local timerのinterruptが生じた直後から簡単に見ていく。

local timer interruptが生じると、IDTのLOCAL_TIMER_VECTOR番のentryのapic_timer_interruptから、smp_apic_timer_interrptをcall⁶し、以下のように遷移する。主にsmp_local_timer_interruptが呼ばれる：

smp_apic_timer_interrupt:
  - ack_APIC_irq: apic_write_around(APIC_EOI, 0)
  - irq_enter
  - smp_local_timer_interrupt:
    - profile_tick(CPU_PROFILING, regs): Profiling the kernel code
      - timer_notify: if start profiling (echo 1>/dev/oprofile/enable)
        - oprofile_add_sample: add sample for optimizer profile
      - profile_hit: Profiling the kernel code using
    - update_process_times(user_mode(regs)):
      - account_(user|system)_time: update `p->(u|s)time`; how long the current process has been running
      - run_local_timers(): invoke TIMER_SOFTIRQ handler(run_timer_softirq)
        - raise_softirq(TIMER_SOFTIRQ):
          - raise_softirq_irqoff: check pending softirq existed
            - irq_stat[smp_processor_id().__softirq_pending] << 2**nr: __raise_softirq_irqoff(nr);
            - wakeup_softirqd: if necessary(exec `wake_up_process(tsk)`)
      - rcu_check_callbacks if rcu_pending:
      - scheduler_tick: keeps the current->time_slice up-to-date (usually decrease)
  - irq_exit: 条件を満たせばdo_softirqが実行される

processの起動時間を更新したり、processのtime_slice(schedulerのためのprocessの持ち時間)の更新をしている。また、optionalでprofiling(kernelのボトルネックがどこか探すために有効に)してたりする。つまり、各CPUで定期的に確認したいことを実行している。

raise_softirq_irqoffでsoftirqをpendingにする(今回は、TIMER_SOFTIRQのbitをONにする)。

timer softirq

softirqがいつ実行されるかは、irq_exitの際にinvoke_softirq(same as do_softirq)を実行することが多い。

// kernel/softirq.c
// void irq_exit(void)
  // skip
      if (!in_interrupt() && local_softirq_pending())
      invoke_softirq(); // same as do_softirq

にて、irq_stat[smp_processor_id()].__softirq_pendingのbitが立っている場合、softirqのactionが実行される。例えば、TIMER_SOFTIRQのbitが立っている場合は、do_softirq -> __do_softirq -> h->action(h);(run_timer_softirq)が実行される:

// kernel/softirq.c
// __do_softirq
        pending = local_softirq_pending();
        // skip
    h = softirq_vec;
    do {
        if (pending & 1) {
            h->action(h);
            rcu_bh_qsctr_inc(cpu);
        }
        h++;
        pending >>= 1;
    } while (pending);

具体的には、pendingは以下のいずれかで、HI_SOFTIRQのbitが立っていたらaction(tasklet_hi_action)が実行され、次にTIMER_SOFTIRQのbitが立っていたら、action(run_timer_softirq)が実行され,...と続き、最後にTASKLET_SOFTIRQのbitが立っていたら、action(tasklet_action)となる。

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

run_timer_softirqはdynamic timersを管理し、timeoutが来たものに関しては、callbackを実行する関数だ。これに関しては、詳細はUnderstanding Linux Kennel ch.6 Dynamic Timersが詳しいので、そちらに譲る。

感想

timerに関してはだいたい全体像を掴んだが、interruptはeflags.IFのON, OFF, preempt, spinlock, re-schedule(TIF_NEED_RESCHED)が絡み合っているので、これよりも更に考えることがある。それについては、今後一つ一つ的を絞って考察していけば良いかな、と感じた。まずは一本の糸を解きほぐせたかなぁ。

次回は、interruptか各種timerのcalibrationの実装詳細をみていきたい。

補足

Understanding Linux kernel の ch.7に関して、p.232( The Linux Timekeeping Architecture )とp.241(Updating System Statistics)の部分の箇条書きがコードのどの部分に相当するのかをメモ

Update the time elapsed since system startup: handle_IRQ_event -> timer_interupt -> jiffies(tick count)
Update the time & date .. update_times
Determine, for every CPU, how long the current process has been running, and preempts it if it has exceeded the time allocated to it. ..account_(user|system)_time
update resource usage statistics
- Checking the CPU resource limit of the running processes .. update_times -> calc_load
- Updating statistics about the local CPU workload .. update_process_times
- Computing the average system load .. set nmi_watchdog parameter (entry point is NMI interrupt, do_nmi)
- Profiling the kernel code .. profile_tick
Checks whether the interval of time has elapsed
- Software Timers
  - dynamic timers: run_timer_softirq as TIMER_SOFTIRQ action.
  - interval timers(PITとは無関係): setitimer()[system call]
- Delay Functions: (u|n)delay (intenally, use TSC counter)

補足にまとめてみた↩
ch.6 The adjtimex( ) System Callを参照のこと。ちなみに、PIIX4ではMotorola* MC146818A-compatible real-time clockが使用されている。include/asm-i386/mc146818rtc.hを参照のこと。↩
実際には、start_kernel -> time_init -> select_timerで複数あるうちのどれを用いるかを決定する↩
TICK_NSECはUnderstanding Linux Kernel ch.6 のProgrammable Interval Timer (PIT)にて、On a PC, tick_nsec is initialized to 999,848 nanoseconds (yielding a clock signal frequency of about 1000.15 Hz)と書いてあるので、上記の数字であっていそう。↩
init 関数自体は、start_kernel -> rest_init -> kernel_thread(init, NULL, CLONE_FS | CLONE_SIGHAND);で駆動する。↩
ここのコードの追い方がわかりにくいが、include/asm-i386/mach-default/entry_arch.hのBUILD_INTERRUPT(apic_timer_interrupt,LOCAL_TIMER_VECTOR)のマクロが効いてる。こちらもinterruptの記事でまとめられたらなとおもう。↩

私のひらめき日記

ようこそ

linux kernelにおけるtimerについて

linux kernelにおけるtimerについて(Timing Measurementsについて)

はじめに

reference

Glossary

Constants

各種timerの初期設定

PIT

TSC

local APIC Timer

timer interrupt

PITのtimer interrupt

IRQ0の設定

IDTの設定

interruptの挙動

local APIC timerのtimer interrupt

LVTの設定

IDTの設定

interruptの挙動

timer softirq

感想

補足