커널 타이머 관리

• 주요 개념
  • HZ와 jiffies
  • Soft IRQ 서비스
  • 커널 타이버를 이루는 자료구조
  • 동적 타이머
• HZ : 1초에 jiffies가 업데이트되는 횟수
• Soft IRQ의 타이머 서비스
  1. 타이머 인터럽트가 발생하면 TIMER_SOFTIRQ라는 Soft IRQ 서비스를 요청합니다.
  2. Soft IRQ 서비스 루틴에서 TIMER_SOFTIRQ 서비스의 아이디 핸들러인 run_timer_softirq() 함수를 호출한다.
  3. run_timer_softirq() 함수에서는 time_bases라는 전역변수에 등록된 동적 타이머를 처리합니다.
• 이외의 시간을 처리하는 기법
  • SoC(Sytem on chip)에서 제공하는 틱 디바이스, timekeeping, 고해상도 타이머(High Resolution Timer)

jiffies

• HZ가 너무 크면 시스템에 오버헤드, 너무 작으면 동적 타이머의 오차가 커짐.
• out/.config 에서 CONFIG_HZ=100 같은 구문에서 확인 가능하다.
• jiffies로 시간 흐름을 제어하는 코드 분석
  • mod_timer() ```c static timer_list dynamic_timer int timeout = 0; timeout = jiffies; timeout += 2 * HZ;

  mod_timer(&dynamic_timer, timeout);

   ```c
   extern int mod_timer(struct timer_list *timer, unsigned long expires);
  

• jffieis 와 jiffies_64 변수
  • System.map 파일

    80c03d00 D jiffies
    80c03d00 D jiffies_64
    

• do_timer

  void do_timer(unsigned long ticks)
  {
    jiffies_64 += ticks;
    calc_global_load(ticks);
  }
  

  static void tick_do_update_jiffies64(ktime_t now)
  {
  /* skip */
    if (delta >= tick_period) {
      delta = ktime_sub(delta, tick_period);
      last_jiffies_update = ktime_add(last_jiffies_update,
      /* skip */
      do_timer(++ticks);
  /* skip */
  

• msecs_to_jiffies()
  • 밀리초를 입력으로 받아 jiffies 단위 시각 정보를 반환

    static __always_inline unsigned long msecs_to_jiffies(const unsigned int m);
    

  • 사용 예제

    msecs_to_jiffies(ms);
    

  • 구현부

    static __always_inline unsigned long msecs_to_jiffies(cosnt unsigned int m)
    {
      if (__builtin_constant_p(m)) {
        if ((int)m < 0)
          return MAX_JIFFY_OFFSET;
        return _msecs_to_jiffies(m);
      } else {
        return __msecs_to_jiffies(m);
      }
    }
    

    #define MAX_JIFFY_OFFSET ((LONG_MAX >> 1)-1)
    #define LONG_MAX ((long)(~0UL>>1))
    

    static inline unsigned long _msecs_to_jiffies(const unsigned int m)
    {
      return (m + (MSEC_PER_SEC / HZ) - 1) / (MSEC_PER_SEC / HZ);
    }
    

• time_after(), time_before()

  #define time_after(a,b)    \
    (typecheck(unsigned long, a) && \
    typecheck(unsigned long, b) && \
    ((long)((b) - (a)) < 0))
  #define time_before(a,b) time_after(b,a)
  

동적 타이머 초기화

• 기본 흐름
  1. 동적 타이머 초기화 : 동적 타이머 초기화는 보통 드라이 버레벨에서 수행한다. 동적 타이머를 나타내는 timer_list 구조체의 필드 중에서 flags와 function만 바뀐다.
  2. 동적 타이머 등록 : 동적 타이머도 마찬가지로 드라이버 레벨에서 등록된다. 각 드라이버의 시나리오에 따라 동적 타이머의 만료 시간을 1/HZ 단위로 지정한 다음 add_timer() 함수를 호출한다.
  3. 동적 타이머 실행 : 동적 타이머가 지정한 만료 시각이 되면 Soft IRQ 타이머 서비스가 동적 타이머를 실행한다.
• 동적 타이머 자료구조

  struct timer_list {
    struct hlist_node    entry;
    unsigned long        expries;
    void                 (*function)(struct timer_list *);
    u32                  flags;
  
  #ifdef CONFIG_LOCKDEP
    struct lockdep_map   lockdep_map;
  #endif
  };
  

  • entry : 해시 연결리스트, timer_bases 전역변수 에동적 타이머를 등록할 때 쓰인다.
  • expires : 동적 타이머 만료시각을 나타낸다. 이 시각에 커널 타이머가 동적 타이머의 핸들러 함수를 호출한다. 이때 단위는 1/HZ
  • function : 동적 타이머 핸들러 함수의 주소를 저장하는 필드. call_tiemr_fn() 함수에 서이 필드에 접근해 동적 타이머 핸들러를 호출한다.
  • flags : 동적 타이머의 설정 필드이며 다음 값 중 하나로 설정된다.

    #define TIMER_CPUMASK      0x0003FFFF
    #define TIMER_MIGRATING    0x00040000
    #define TIMER_BASEMASK     (TIMER_CPUMASK | TIMER_MIGRATING)
    #define TIMER_DEFERRABLE   0x00080000
    #define TIMER_PINNED       0x00100000
    #define TIMER_IRQSAFE      0x00200000
    #define TIMER_ARRAYSHIFT   22
    #define TIMER_ARRAYMASK    0xFFC00000
    

• 동적 타이머 초기화 함수
  • timer_setup()

    void timer_setup(struct timer_list *timer, void *func, unsigned int flags);
    

    • timer : 동적 타이머를 나타내는 정보
    • func : 동적 타이머 핸들러 함수
    • flags : 동적 타이머 플레그
    • 커널 4.14 버전까지 동적 타이머를 초기화하려면 setup_timer() 함수나 init_timer() 함수를 써야됬다.

    #define timer_setup(timer, callback, flags)       \
        __init_timer((timer), (callback), (flags))
    
    #define __init_timer(_timer, _fn, _flags) \
      init_timer_key((_timer), (_fn), (_flags), NULL, NULL)
    

    void init_timer_key(struct timer_list *timer,
                  void (*func)(struct timer_list *), unsigned int flags,
                  const char *name, struct lock_class_key *key)
    {
      debug_init(timer);
      do_init_timer(timer, func, flags, name, key);
    }
    

    static inline void debug_init(struct timer_list *timer)
    {
      debug_timer_init(timer);
      trace_timer_init(timer);
    }
    

    static void do_init_timer(struct timer_list *timer,
                    void (*func)(struct timer_list *),
                    unsigned int flags,
                    const char *name, struct lock_class_key *key)
    {
      timer->entry.pprev = NULL;
      timer->function = func;
      timer->flags = flags | raw_smp_processor_id();
      lockdep_init_map(&timer->lockdep_map, name, key, 0);
    }
    

    동적타이머 등록

• 동적 타이머 등록 함수
  • add_timer : 동적타이머를 등록하기 위한 인터페이스

    void add_timer(struct timer_list *timer)
    {
      BUG_ON(timer_pending(timer));
      mod_timer(timer, timer->expires);
    }
    

  • mod_timer

    int mod_timer(struct timer_list *timer, unsigned long expires)
    {
      return __mod_timer(timer, expires, false);
    }
    

  • __mod_timer : 실제로 동적타이머를 등록하는 함수

    static inline int
    __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int options)
    {
      struct timer_base *base, *new_base;
      unsigned int idx = UINT_MAX;
      unsigned long clk = 0, flags;
      int ret = 0;
    
      BUG_ON(!timer->function);
    
      if (timer_pending(timer)) {
        long diff = timer->expires - expires;
    
        if (!diff)
          return 1;
        if (options & MOD_TIMER_REDUCE && diff <= 0)
          return 1;
        base = lock_timer_base(timer, &flgas);
        forward_timer_base(base);
    
        if (timer_pending(timer) && (options & MOD_TIMER_REDUCE) &&
          time_before_eq(timer->expires, expires)) {
          return = 1;
          goto out_unlock;
        }
    
        clk = base->clk;
        idx = calc_wheel_index(expires, clk);
        /* skip */
      } else {
        base = lock_timer_base(timer, &flags);
        forward_timer_base(base);
      }
    
      ret = detach_if_pending(timer, base, false);
      /* skip */
      debug_active(timer, expires);
    
      timer->expires = expires;
    
      if (idx != UINT_MAX && clk == base->clk) {
        enqueue_timer(base, timer, idx);
        trigger_dyntick_cpu(base, timer);
      } else {
        internal_add_timer(base, timer);
      }
    
    out_unlock:
      raw_spin_unlock_irqrestore(&base->lock, flags);
    
      return ret;
    }
    

    • 반복해서 동적 타이머를 등록하면 1을 반환하며 실행을 종료
    • 동적 타이머는 timer_base 타이머 해시 벡터에 등록함
• timer_pending() : 동적 타이머가 등록됬는지 확인하는 함수

  static inline int timer_pending(const struct timer_list * timer)
  {
    return timer->entry.pprev != NULL;
  }
  

  • 이미 동적 타이머를 등록했을 때 1을 반환
  • timer->entry.pprev 포인터는 percpu 타입의 timer_base 변수의 벡터 해시 테이블의 주소를 가리킨다.
• lock_timer_base()

  static struct timer_base *lock_timer_base(struct timer_list *timer,
                                        unsigned long *flags)
      __acquires(timer->base->lock)
  {
    for (;;) {
      /* skip */
      if (!(tf & TIMER_MIGRATING)) {
        base = get_timer_base(tf);
        /* skip */
  

• get_timer_base() : 타이머가 기준으로 하는 timer_bases 전역변수를 읽는다.

  static inline struct timer_base *get_timer_base(u32 tflags)
  {
    return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
  }
  

• get_timer_cpu_base()

  static inline struct timer_base *get_timer_cpu_base(u32 flags, u32 cpu)
  {
    struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_STD], cpu);
    /* skip */
    return base;
  }
  

• forward_timer_base() : timer_base의 clk 필드를 현재 시각으로 바꾼다.

  static inline void forward_timer_base(struct timer_base *base)
  {
  #ifdef CONFIG_NO_HZ_COMMON
    unsigned long jnow;
    /* skip */
    jnow = READ_ONCE(jiffies);
    /* skip */
    if (time_after(base->next_expiry, jnow))
      back->clk = jnow;
    else
      base->clk = base->next_expiry;
  #endif
  }
  

• enqueue_timer()

  static void enqueue_timer(struct timer_bae *base, struct timer_list *timer,
                      unsigned int idx)
  {
    hlist_add_head(&timer->entry, base->vectors + idx);
    __set_bit(idx, base->pending_map);
    timer_set_idx(timer, idx);
  }
  

  • base : percpu 타입의 timer_bases 전역변수에서 현재 구동중인 CPU에 해당하는 오프셋을 적용한 주소
  • timer : 등록하려는 동적 타이머의 속성 정보

동적타이머 실행

1. TIMER_SOFTIRQ 아이디로 Soft IRQ 서비스 요청
2. Soft IRQ 컨텍스트 시작
3. Soft IRQ 서비스 요청 점검
4. 등록된 동적 타이머 실행

• update_process_times()

  void update_process_times(int user_tick)
  {
    struct task_struct *p = current;
  
    account_process_tick(p, user_tick);
    run_local_timers();
    /* skip */
  }
  

• run_local_timers()

  void run_local_timers(void)
  {
    struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
  
    hrtimer_run_queues();
  
    if (time_before(jiffies, base->clk)) {
      if (!IS_ENABLED(CONFIG_NO_HZ_COMMON))
        return;
      /* CPU is awake, so check the deferrable base. */
      base++;
      if (timer_before(jiffies, base->clk))
        return;
    }
    raise_softirq(TIMER_SOFTIRQ);
  }
  

  • 지연 타이머는 deferrable 전용 타이머 베이스를 사용한다.
  • 타이머 인터럽트가 발생 -> 만료될 동적 타이머가 있는지 점검 -> 있다면 TIMER_SOFTIRQ라는 서비스로 Soft IRQ 서비스 요청
• __do_softirq()

  asmlinkage __visible void __softirq_entry(void)
  {
    unsigned long end = jiffies + MAX_SOFTIRQ_TIME;
    unsigned long old_flags = current->flags;
    struct softirq_action *h;
    /* skip */
  restart:
    set_softirq_pending(0);
  
    local_irq_enable();
  
    h = softirq_vec;
    while ((softirq_bit = ffs(pending))) {
      unsigned int vec_nr;
      int prev_count;
  
      h += softirq_bit - 1;
  
      vec_nr = h - softirq_vec;
      prev_count = preempt_count();
  
      kstat_incr_softirqs_this_cpu(vec_nr);
  
      trace_softirq_entry(vec_nr);
      h->action(h);
    /* skip */
    }
  }
  

• run_timer_softirq()
  • TIMER_SOFTIRQ 의 handler 는 run_timer_softirq 임

    static __latent_entropy void run_timer_softirq(struct softirq_action *h)
    {
    struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
    base->must_forward_clk = false;
    
    __run_timers9base);
    if (IS_ENABLED(CONFIG_NO_HZ_COMMON))
      __run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
    }
    

• __run_timers()

  static inline void __run_timers(struct timer_base *base)
  {
    struct hlist_head heads[LVLDEPTH];
    int levels;
  
    if (!timer_after_eq(jiffies, base->clk))
      return;
  
    raw_spin_lock_irq(&base->lock);
  
    while (time_after_eq(jiffies, base->clk)) {
  
      levels = collect_expired_timers(base, heads);
      base->clk++;
  
      while (levels--)
        expire_timers(base, heads + levels);
    }
    base->running_timer = NULL;
    raw_spin_unlock_irq(&base->lock);
  }
  

• __collect_expired_timers()

  static int collect_expired_timers(struct timer_base *base,
                                 struct hlist_head *heads)
  {
  /* skip */
    return __collect_expired_timers(base, heads);
  }
  

  static int __colect_expired_timers(struct timer_base *base,
                                 struct hlist_head *heads)
  {
    unsigned long clk = base->clk;
    struct hlist_head *vec;
    int i, levels = 0;
    unsigned int idx;
  
    for (i = 0; i < LVL_DEPTH; i ++) {
      idx = (clk & LVL_MASK) + i * LVL_SIZE;
  
      if (__test_and_clear_bit(idx, base->pending_map)) {
        vec = base->vectors + idx;
        hlist_move_list(vec, heads++);
        levels++;
      }
    }
    /* skip */
    return levels;
  }
  

• expire_timers()

  static void expire_timers(struct timer_base *base, struct hlist_head *head)
  {
    while (!hlist_empty(head)) {
      struct timer_list *timer;
      void (*fn)(struct tiemr_list *);
  
      timer = hlist_entry(head->first, struct timer_list, entry);
  
      base->running_timer = timer;
      detach_timer(timer, true);
  
      fn = timer->function;
  
      if (timer->flags & TIMER_IRQSAFE) {
        raw_spin_unlock(&base->lock);
        call_timer_fn(timer, fn);
        raw_spin_lock(&base->lock);
      } else {
        raw_spin_unlock_irq(&base->lock);
        call_timer_fn(timer, fn);
        raw_spin_lock_irq(&base->lock);
      }
    }
  }
  

  • list에서 timer를 꺼낸후, running_timer 로 만들어 놓고, list 에서 detach 시킨다.
  • 그 뒤 fn 에다가 timer callback 을 넣어주고, TIMER_IRQSAFE(TIMER 가 irq disabled 이고 irq handler 가 실행 중인걸 기다려야되는지)인지 확인하고, 그에 따라 lock 걸고 timer를 실행한다.
• call_timer_fn()

  static void call_timer_fn(struct timer_list *timer, void (*fn)(unsigned long),
                       unsigned long data)
  {
    int count = preempt_count();
    /* skip */
    trace_timer_expire_entry(timer);
    fn(data);
    trace_timer_expire_exit(timer);
    /* skip */
  }
  

  커널 타이머 정리

  1. 동적 타이머 등록 : mod_timer
  2. TIMER_SOFTIRQ 서비스 요청
  3. Soft IRQ 서비스 실행
  4. 동적 타이머 만료 후 타이머 핸들러 실행

• HZ : 진동수, 1초에 jiffies 가 업데이트 되는 횟수
• TIMER_SOFTIRQ 로 Soft IRQ 서비스를 요청
• msecs_to_jiffies 를 통해서 밀리초 입력을 jiffies 로 시각 정보를 반환
• 내부 시간 비교는 time_after() 와 time_before() 를 사용
• 동적타이머 등록 함수 : add_timer(), mod_timer()
• Soft IRQ 컨텍스트에서 처리되므로 실행 시간이 빨라야한다.
• ftrace 에서 동적 타이머 추적 가능 이벤트
  • timer_init, timer_start, timer_expire_entry, timer_expire_exit, timer_cancel