dyn-ticks ってどうなってるの

目標

いまいち dyn-ticks(Tickless kernel) についてよくわかっていなかったので、コードを読みながらまとめる. カーネルのバージョンは 2.6.27.8(古くてごめんなさい) で、CPU は i686(SMP環境)としておく. 話が行ったり来たりしますが、ご了承を.

ハードウェアタイマ

まず、すべてのハードウェアタイマに2つの動作モードがある:

  1. 周期モード
  2. ワンショットモード

この2つをうまいこと使い分けるのがOSプログラマの腕の見せ所...のはずだったのだが、1世代前に流行っていたハードウェアタイマであるPIT(Programmable Interval Timer)はワンショットモードの精度が悪くて使い物にならなかったようだ.そのせいか、ちょっと古いOSになると、周期モードにしか対応していないOSがあるとか、ないとか. 周期モードを使うと、比較的OSの実装はシンプルになるだろうしね. 最近のイケてるハードウェア(後で出てくるHPETやLocal APIC Timer)を使うと、ワンショットモードも普通に(実用の範囲内で)動作するようだ.

HPET, RTC, ACPI Timer, PIT など

基本的に、ハードウェアタイマとCPUは割り込み線とIO-APICを介してつながっている.

IO-APIC は、割り込みを各CPUに配分する門番のような役割がある. タイマ割り込みに限らず、外部の割り込みは、外部ハードウェア→IO-APIC→Local APIC→CPUという順に伝わる. この割り込みは、ブロードキャストする場合と、特定のCPUにだけ伝える場合の2種類がある. x86 の場合、下位互換性の問題から、 PIT は IRQ 0 番がハードウェアタイマを結線されており、その他のハードウェアタイマが別の割り込み線を使うことが多い.

Local APIC Timer

ハードウェアタイマとCPUは、割り込み線を介してつながっていると書いた. しかし1つだけ例外がある. CPU に搭載されているLoal APIC Timer だ. Local APIC というのは、Local Advanced Programmable Interrupt Controller の略で、CPUのコア1つ1つにくっついている割り込みコントローラのことだ. こいつにタイマがくっついているのだ. 当然、周期モードとワンショットモードが存在する. CPU にくっついているだけあって、Local APIC Timer と CPU は物理メモリアドレス空間を通じてやりとりを行う.

clockevents フレームワーク

clockevents フレームワークは、アーキテクチャ依存になりがちがタイマのコードの重複をなくそうということで実装されたハードウェアタイマドライバを実装するためのフレームワークである. 特定の関数を実装して、構造体に入れておくと、そのハードウェアタイマのドライバが読み込まれた際に関数をコールバックし、タイマデバイスリストに登録する. それより上のレイヤの面倒は clockevents フレームワーク側が見てくれるという代物だ. ハードウェアタイマの節でも書いたが、ハードウェアタイマにはワンショットモードと周期モードがある. dyn-ticks kernel の実装にあたっては、前者が大きな役割を果たしてくる. clockevents フレームワークからデバイスドライバのワンショットモードを利用するには、clockevents_program_event 関数を呼ぶ.

Linuxカーネルのメインループ、cpu_idle()

Linuxカーネルは、ブート後すべての初期化が終わると、最終的には cpu_idle というアーキテクチャ固有のメインループに処理がおちつく. 今回想定している環境の場合、arch/x86/kernel/process_32.c で定義されている.

118 /*      
119  * The idle thread. There's no useful work to be
120  * done, so just try to conserve power and have a
121  * low exit latency (ie sit in a loop waiting for
122  * somebody to say that they'd like to reschedule)
123  */
124 void cpu_idle(void)
125 {
126     int cpu = smp_processor_id();
127         
128     current_thread_info()->status |= TS_POLLING;
129 
130     /* endless idle loop with no priority at all */
131     while (1) {
132         tick_nohz_stop_sched_tick(1);
133         while (!need_resched()) { 
                /* sleep ! */
144             local_irq_disable();
145             __get_cpu_var(irq_stat).idle_timestamp = jiffies;
146             /* Don't trace irqs off for idle */
147             stop_critical_timings();
148             pm_idle(); // -> acpi_processor_idle()
149             start_critical_timings();
150         }
151         tick_nohz_restart_sched_tick();
152         preempt_enable_no_resched();
153         schedule();
154         preempt_disable();
155     }
156 }

cpu_idle()の中では、

  1. tick_nohz_stop_sched_tickを呼んで、指定した時間までtick(タイマ割り込みを発生させないようにする.
  2. need_reschedマクロ(include/linux/sched.h)を使って、新たなタスクがないかチェック. なければCPUステートを休止にもっていく.
  3. tick_nohz_restart_sched_tickを呼んで、tickを再開する.

といった処理を行っている. tick_nohz_stop_sched_tick()とtick_nohz_restart_sched_tick()が今回の記事の主役だが、これについては次節で詳しく説明する.

ここでのポイントは、休止中は割り込み全般を禁止している点. どうやって復帰するんだ!と思いきや、システムコールや割り込みハンドラの処理が終わったとき、もしくはwake_up_idle_cpu()呼び出し時に更新される need_resched フラグをチェックしてループから脱出するようだ.

dyn-ticksを追う

ここまでで、dyn-ticksを追うための前提知識について述べた. ここから、 dyn-ticks の実装について述べていく.
dyn-ticks の本体・tick_nohz_stop_sched_tick()とtick_nohz_restart_sched_tick()は、kernel/time/tick-sched.c で定義される.

197 /**
198  * tick_nohz_stop_sched_tick - stop the idle tick from the idle task
199  *
200  * When the next event is more than a tick into the future, stop the idle tick
201  * Called either from the idle loop or from irq_exit() when an idle period was
202  * just interrupted by an interrupt which did not cause a reschedule.
203  */
204 void tick_nohz_stop_sched_tick(int inidle)
205 {
206     unsigned long seq, last_jiffies, next_jiffies, delta_jiffies, flags;
207     struct tick_sched *ts;
208     ktime_t last_update, expires, now;
209     struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;
210     int cpu;
211 
212     local_irq_save(flags);
213 
217 
218     /*
219      * If this cpu is offline and it is the one which updates
220      * jiffies, then give up the assignment and let it be taken by
221      * the cpu which runs the tick timer next. If we don't drop
222      * this here the jiffies might be stale and do_timer() never
223      * invoked.
224      */
225     if (unlikely(!cpu_online(cpu))) {
226         if (cpu == tick_do_timer_cpu)
227             tick_do_timer_cpu = TICK_DO_TIMER_NONE;
228     }
229 
230     if (unlikely(ts->nohz_mode == NOHZ_MODE_INACTIVE))
231         goto end;
235 
236     ts->inidle = 1;
237 
253     /* Read jiffies and the time when jiffies were updated last */
254     do {
255         seq = read_seqbegin(&xtime_lock);
256         last_update = last_jiffies_update;
257         last_jiffies = jiffies;
258     } while (read_seqretry(&xtime_lock, seq));
259 
260     /* Get the next timer wheel timer */
261     next_jiffies = get_next_timer_interrupt(last_jiffies);
262     delta_jiffies = next_jiffies - last_jiffies;
263 
264     if (rcu_needs_cpu(cpu))
265         delta_jiffies = 1;
266     /*
267      * Do not stop the tick, if we are only one off
268      * or if the cpu is required for rcu
269      */
270     if (!ts->tick_stopped && delta_jiffies == 1)
271         goto out;
272 
273     /* Schedule the tick, if we are at least one jiffie off */
274     if ((long)delta_jiffies >= 1) {
275 
276         if (delta_jiffies > 1)
277             cpu_set(cpu, nohz_cpu_mask);
278         /*
279          * nohz_stop_sched_tick can be called several times before
280          * the nohz_restart_sched_tick is called. This happens when
281          * interrupts arrive which do not cause a reschedule. In the
282          * first call we save the current tick time, so we can restart
283          * the scheduler tick in nohz_restart_sched_tick.
284          */
285         if (!ts->tick_stopped) {
286             if (select_nohz_load_balancer(1)) {
287                 /*
288                  * sched tick not stopped!
289                  */
290                 cpu_clear(cpu, nohz_cpu_mask);
291                 goto out;
292             }
293 
294             ts->idle_tick = ts->sched_timer.expires;
295             ts->tick_stopped = 1;
296             ts->idle_jiffies = last_jiffies;
297             rcu_enter_nohz();
298         }
299 
300         /*
301          * If this cpu is the one which updates jiffies, then
302          * give up the assignment and let it be taken by the
303          * cpu which runs the tick timer next, which might be
304          * this cpu as well. If we don't drop this here the
305          * jiffies might be stale and do_timer() never
306          * invoked.
307          */
308         if (cpu == tick_do_timer_cpu)
309             tick_do_timer_cpu = TICK_DO_TIMER_NONE;
310 
311         ts->idle_sleeps++;
312 
313         /*
314          * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
315          * there is no timer pending or at least extremly far
316          * into the future (12 days for HZ=1000). In this case
317          * we simply stop the tick timer:
318          */
319         if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
320             ts->idle_expires.tv64 = KTIME_MAX;
321             if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
322                 hrtimer_cancel(&ts->sched_timer);
323             goto out;
324         }
325 
326         /*
327          * calculate the expiry time for the next timer wheel
328          * timer
329          */
330         expires = ktime_add_ns(last_update, tick_period.tv64 *
331                        delta_jiffies);
332         ts->idle_expires = expires;
333 
334         if (ts->nohz_mode == NOHZ_MODE_HIGHRES) {
335             hrtimer_start(&ts->sched_timer, expires,
336                       HRTIMER_MODE_ABS);
337             /* Check, if the timer was already in the past */
338             if (hrtimer_active(&ts->sched_timer))
339                 goto out;
340         } else if (!tick_program_event(expires, 0))
341                 goto out;
342         /*
343          * We are past the event already. So we crossed a
344          * jiffie boundary. Update jiffies and raise the
345          * softirq.
346          */
347         tick_do_update_jiffies64(ktime_get());
348         cpu_clear(cpu, nohz_cpu_mask);
349     }
350     raise_softirq_irqoff(TIMER_SOFTIRQ);
351 out:
352     ts->next_jiffies = next_jiffies;
353     ts->last_jiffies = last_jiffies;
354     ts->sleep_length = ktime_sub(dev->next_event, now);
355 end:
356     local_irq_restore(flags);
357 }

ポイントは、get_next_timer_event()で得た次のタイマイベントを、hrtimer_start(), もしくは tick_program_event()へ渡しているところである.

get_next_timer_event()関数は、「次のタイマイベント=現在リストの中に存在するタイマの中で、最も近い未来に点火するタイマは、いつ点火するか」をjiffiesの値で手にいれてくるという見ていて大変楽しげな関数である(kernel/timer.c). Linuxで実装されているカーネルタイマはいずれもリストで走査できるようになっているので、割と簡単にこの値を手に入れてくることができる. ちなみに、ここで手に入る next_jiffies の値は、カーネルコンフィグで設定したHZの値よりも大きくなり得ることに注意. これによって、消費電力を抑えることができる. 利用するときになったらアップデートしよう、という遅延評価のアプローチである.

さて、ここで手にいれた値を hrtimer_start(),もしくはtick_program_event() に渡す. 後者は、内部で clockevents_program_event 関数を呼ぶ. つまり、次のタイマ割り込みがnext_jiffiesになるまで発生しないようにする. 前者はどうだろう? 実は、hrtimer_startの中では結局 tick_program_event を呼ぶ. 今回入れようとしているタイマイベントは最も小さい値であることは分かっているから、次のタイマ割り込みが発生する直前にsched_timer を点火しよう、という作戦だ.

sched_timer というのは何だろう? これは、CPU毎のワンショットタイマでグローバル割り込みをエミュレーションするためのコードだ. dyn-ticks では、グローバルタイマ割り込みが働かないため、どこかで明示的にグローバルタイマ割り込みのハンドラを呼ばないと、jiffiesやxtimeがアップデートできない. それを行うのが sched_timer で、コールバックされる関数はtick_sched_timer()だ. tick_do_update_jiffies64 は、前回sched_timerが点火した時間からの差がtick_period(カーネルコンフィグで設定したHZの値)よりも大きければ、jiffiesの更新を行う.

最後に、tick_program_event の中身を見てみよう. この関数は kernel/time/tick-oneshot.c で定義されている.
これ自体はtick_dev_program_eventを呼び出しているだけなので、そちらを見てみる.

 65 /**                                                                                           
 66  * tick_program_event                                                                         
 67  */                                                                                           
 68 int tick_program_event(ktime_t expires, int force)                                            
 69 {                                                                                             
 70     struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;                   
 71                                                                                               
 72     return tick_dev_program_event(dev, expires, force);                                       
 73 }

でた!clockevents_program_event!

 25 /**
 26  * tick_program_event internal worker function
 27  */
 28 int tick_dev_program_event(struct clock_event_device *dev, ktime_t expires,
 29                int force)
 30 {                                                                                             
 31     ktime_t now = ktime_get();                                                                
 32     int i;                                                                                    
 33                                                                                               
 34     for (i = 0;;) {                                                                           
 35         int ret = clockevents_program_event(dev, expires, now);                               
 36                                                                                               
 37         if (!ret || !force)                                                                   
 38             return ret;                                                                       
 39                                                                                               
 40         /*                                                                                    
 41          * We tried 2 times to program the device with the given                              
 42          * min_delta_ns. If that's not working then we double it                              
 43          * and emit a warning.                                                                
 44          */                                                                                   
 45         if (++i > 2) {                                                                        
 46             /* Increase the min. delta and try again */                                       
 47             if (!dev->min_delta_ns)                                                           
 48                 dev->min_delta_ns = 5000;                                                     
 49             else                                                                              
 50                 dev->min_delta_ns += dev->min_delta_ns >> 1;                                  
 51                                                                                               
 52             printk(KERN_WARNING                                                               
 53                    "CE: %s increasing min_delta_ns to %lu nsec\n",                            
 54                    dev->name ? dev->name : "?",                                               
 55                    dev->min_delta_ns << 1);                                                   
 56                                                                                               
 57             i = 0;                                                                            
 58         }                                                                                     
 59                                                                                               
 60         now = ktime_get();                                                                    
 61         expires = ktime_add_ns(now, dev->min_delta_ns);                                       
 62     }                                                                                         
 63 }                                                                                             
 64                                                                                       

まとめ

ハードウェアの話から入って、dyn-ticks の話をまとめてみました. 結構な長文になってしまいましたね :P

さて、分かってるかのように書いてますが、1つ疑問があります. cpu_idle でチェックしている、need_resched() が更新されるタイミングです. 全部のCPUがこのループに入って、誰も起こさない状態になってしまう(=デッドロックしてしまう)ことはないんだろうか...?どなたか、ご存知の方がいれば教えて頂ければと思います. ツッコミお待ちしております.