Timer -1- (Lowres Timer)

Lowres(Low Resolution) Timer

커널에서 사용하는 jifffies 기반의 타이머 tick을 소프트웨어 기법으로 구현한 타이머이다. 커널이 타이머를 요청할 때 만료 시간을 기재하는데 lowres 타이머는 정확하게 그 만료시점에 깨어나는 것을 보장하지 못한다. 대략 수 백 밀리 초 이내에 실행하는 것만을 보장한다. 그 외 특징으로 lowres 타이머는 특정 아키텍처와 무관한 구조이다.

  • 컴파일 타임에 정적으로 생성
    • DEFINE_TIMER()
  • 동적 생성, 변경 및 해제
    • add_timer()
    • mod_timer()
    • del_timer()

 

Lowres 타이머는 생성되고 삭제될 수 있으며 아래 timer_list 구조체에 저장된다.

 

timer_list 구조체

include/linux/timer.h

struct timer_list {
        /*
         * All fields that change during normal runtime grouped to the
         * same cacheline
         */
        struct list_head entry;
        unsigned long expires;
        struct tvec_base *base;

        void (*function)(unsigned long);
        unsigned long data;

        int slack;

#ifdef CONFIG_TIMER_STATS
        int start_pid;
        void *start_site;
        char start_comm[16];
#endif
#ifdef CONFIG_LOCKDEP
        struct lockdep_map lockdep_map;
#endif
};
  • entry
    • 동적 타이머들을 타이머 벡터 리스트로 연결 시 사용한다.
  • expires
    • 타이머가 만료될 미래의 jiffies 시점을 지정한다.
  • function
    • 타이머 만료 시 실행할 함수의 주소를 저장한다.
  • data
    • 타이머 함수에 전달할 인수를 지정한다.
  • base
    • tvec_base 포인터 주소가 담기며 하위 2bit는 다음의 플래그를 담을 수 있다.
      • TIMER_DEFERRABLE (0x1LU)
      • TIMER_IRQSAFE (0x2LU)
  • slack
    • expires에 slack tick 만큼을 추가한 후 변경된 상위 비트 이하로 절삭한다.
      • 예) usb-hcd 드라이버에서 slack=2(100hz, 20msec)를 사용한다.
    • slack을 주어 타이머를 정렬하면 인터럽트 횟수를 줄여 절전 및 처리 성능을 높인다.

 

per-cpu 타이머 휠 및 벡터 관리 구조

요청된 타이머의 관리를 위해 cpu 마다 타이머휠이 사용된다. 타이머 휠마다 tv1 ~ tv5까지의 5개 벡터로 나누어 관리하며, 각 벡터는 각각 256, 64, 64, 64, 64개의 리스트로 이루어진다.

  • CONFIG_BASE_SMALL 사용 시 커널 사이즈를 최소화하기 위해 리스트들은 각각 64, 16, 16, 16, 16개로 1/4로 줄어든다.

 

tvec_base, tvec_root, tvec 구조체

tvec_base의 구조는 다음과 같이 tv~tv5개의 tvec 구조체를 가지고 있다.

kernel/time/timer.c

struct tvec_base {
        spinlock_t lock;
        struct timer_list *running_timer;
        unsigned long timer_jiffies;
        unsigned long next_timer;
        unsigned long active_timers;
        unsigned long all_timers;
        int cpu;
        struct tvec_root tv1;
        struct tvec tv2;
        struct tvec tv3;
        struct tvec tv4;
        struct tvec tv5;
} ____cacheline_aligned;
  • lock
    • 타이머 벡터 리스트 조작시 사용할 lock
  • running_timer
    • 타이머가 만료되어 현재 함수를 실행중인 타이머를 가리킨다.
  • timer_jiffies
    • cpu에서 타임 tick을 얻을 때 마다 jiffies 값과 동일해질 때까지 증가된다.
      • tick 발생 시 jiffies 값이 timer_jiffies 이상인 경우, 즉 타이머를 처리할 시간이거나 초과한 경우 jiffies 값이 될때까지 timer_jiffies 값을 1씩 증가시키면서 루프를 돌며 tv1 타이머 벡터들중 해시(timer_jiffies % 256)로 선택한 타이머 벡터 리스트의 타이머들을 처리한다.
    • 타이머가 없는 경우 jiffies 값으로 갱신된다.
  • next_timer
    • 다음으로 만료될 타이머의 expire 값
  • active_timers
    • deferrable(유예) 타이머를 제외한 전체 등록된 타이머 수
  • all_timers
    • deferrable(유예) 타이머를 포함한 전체 등록된 타이머 수
  • cpu
    • 현재 타이머 벡터 관리가 동작하는 cpu id
  • tv1
    • 타이머 벡터 1
      • 256개의 타이머 벡터 리스트
      • 커널 사이즈를 최소화하기 위해 CONFIG_BASE_SMALL을 사용하는 경우 64개로 줄어든다.
  • tv2 ~ tv5
    • 타이머 벡터 2~5
      • 각 64개의 타이머 벡터 리스트
      • 커널 사이즈를 최소화하기 위해 CONFIG_BASE_SMALL을 사용하는 경우 16개로 줄어든다.

 

kernel/time/timer.c

struct tvec_root {
        struct list_head vec[TVR_SIZE];
};

tv1에서 사용하는 벡터 리스트는 tv2 ~ tv5의 4배 크기 만큼의 배열을 사용한다.

 

kernel/time/timer.c

struct tvec {
        struct list_head vec[TVN_SIZE];
};

CONFIG_BASE_SMALL 설정 여부에 따라 벡터 리스트의 배열 수가 결정된다.

  • 설정된 경우 16개 벡터 리스트 배열
  • 설정되지 않은 경우 64개 벡터 리스트 배열
    • rpi2: CONFIG_BASE_SMALL을 사용하지 않고 CONFIG_BASE_FULL을 사용한다.
  • CONFIG_BASE_SMALL & CONFIG_BASE_FULL
    • 생성되는 커널 사이즈를 조금이라도 줄여야 하는 상황에서는 SMALL을 설정하고 그렇지 않은 경우 FULL을 사용한다.
    • 초소형 커널이 필요한 경우 SMALL을 사용한다. 그 외에는 FULL을 사용한다.

 

per-cpu boot_tvec_bases

struct tvec_base boot_tvec_bases;
EXPORT_SYMBOL(boot_tvec_bases);
static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases;

tvec_base는 성능향상을 위해 per-cpu를 사용하여 관리한다.

  • 초기 부팅 시에는 컴파일 타임에 만들어진 1 개의 boot_tvec_bases 관리 구조가 사용되지만 초기화된 후에는 각 cpu별로 tvec_base 구조체를 각각 할당 받아 초기화하여 사용한다.

 

jiffies

스케쥴 틱이 발생할 때 마다 1씩 증가한다.

  • 예) 100hz 시스템인 경우 10ms 마다 1 tick이 발생하고 jiffies 값도 1씩 증가된다.

다음과 같이 32bit 시스템에서 초기값은 부트 후 약 5분이내에 overflow 될 수 있는 값을 주었다. 64비트 시스템에서는 overflow되려면 어마 어마한 시간이 흘러야 하므로 overflow될 걱정이 없다.

  • 32bit 시스템에서 빠른 overflow를 혹시 커널에 버그가 있는 경우 문제점을 진단하기 쉽게하기 위해 초기값을 0을 사용하지 않았다.
  • 초기값
    • 32bit: 0xffff_e2d3 (-300)
    • 64bit: 0x0000_0000_ffff_e2d3

 

/*
 * Have the 32 bit jiffies value wrap 5 minutes after boot
 * so jiffies wrap bugs show up earlier.
 */
#define INITIAL_JIFFIES ((unsigned long)(unsigned int) (-300*HZ))

 

시간 비교 함수

jiffies 값을 읽어 시간을 직접 비교하는 경우 jiffies overflow 되는 시점에서 시간 비교가 의도치 않는 반대의 결과를 얻을 수 있다. 따라서 다음 함수들을 사용하여야 정확한 결과를 나타내게 할 수 있으므로 절대 jiffies 시간을 직접 비교 사용하는 일이 없도록 해야 한다.

  • 2개 시간 비교 함수
    • time_before(a,b)
      • a가 b 보다 먼저 시간값이면 true
    • time_after(a,b)
      • a가 b 보다 나중 시간값이면 true
    • time_before_eq(a,b)
      • a 가 b보다 먼저이거나 같은 시간이면 true
    • time_after_eq(a,b)
      • a 가 b 보다 나중이거나 같은 시간이면 true
  • jiffies와 시간 비교 함수
    • time_is_before_jiffies(a)
      • a가 jiffies 보다 먼저 시간값이면 true
    • time_is_after_jiffies(a)
      • a가 jiffies 보다 나중 시간값이면 true
    • time_is_before_eq_jiffies(a)
      • a 가 jiffies 보다 먼저이거나 같은 시간이면 true
    • time_is_after_eq_jiffies(a)
      • a 가 jiffies 보다 나중이거나 같은 시간이면 true

 

타이머 추가

add_timer()

kernel/time/timer.c

/**
 * add_timer - start a timer
 * @timer: the timer to be added
 *
 * The kernel will do a ->function(->data) callback from the
 * timer interrupt at the ->expires point in the future. The
 * current time is 'jiffies'.
 *
 * The timer's ->expires, ->function (and if the handler uses it, ->data)
 * fields must be set prior calling this function.
 *
 * Timers with an ->expires field in the past will be executed in the next
 * timer tick.
 */
void add_timer(struct timer_list *timer)
{
        BUG_ON(timer_pending(timer));
        mod_timer(timer, timer->expires);
}
EXPORT_SYMBOL(add_timer);

동적 타이머를 요청한다.

  • mod_timer()를 호출하여 만료 시간을 변경한다.

 

다음 그림은 만료시각이 다른 각종 타이머들을 추가했을 때 타이머휠에 등록된 타이머 상태들을 보여준다.

 

타이머 변경

mod_timer()

kernel/time/timer.c

/**
 * mod_timer - modify a timer's timeout
 * @timer: the timer to be modified
 * @expires: new timeout in jiffies
 *
 * mod_timer() is a more efficient way to update the expire field of an
 * active timer (if the timer is inactive it will be activated)
 *
 * mod_timer(timer, expires) is equivalent to:
 *
 *     del_timer(timer); timer->expires = expires; add_timer(timer);
 *
 * Note that if there are multiple unserialized concurrent users of the
 * same timer, then mod_timer() is the only safe way to modify the timeout,
 * since add_timer() cannot modify an already running timer.
 *
 * The function returns whether it has modified a pending timer or not.
 * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
 * active timer returns 1.)
 */
int mod_timer(struct timer_list *timer, unsigned long expires)
{
        expires = apply_slack(timer, expires);

        /*
         * This is a common optimization triggered by the
         * networking code - if the timer is re-modified
         * to be the same thing then just return:
         */
        if (timer_pending(timer) && timer->expires == expires)
                return 1;

        return __mod_timer(timer, expires, false, TIMER_NOT_PINNED);
}
EXPORT_SYMBOL(mod_timer);

요청한 타이머를 제거하고 인수로 받은 만료 시점(timerout을 적용한 새 jiffies 시점)으로 조절하고 설정한다. 만료 시점은 약간의 여유를 더 줄 수도 있다. inactive된 타이머도 active 시킨다.

  • 코드 라인 23에서 절전과 처리 속도 향상을 위해 만료 시점에 slack(여유)을 추가하여 만료시각이 유사한 타이머들을 정렬 할 수 있게 한다.
  • 코드 라인 30~31에서 타이머 벡터 리스트에 등록되어 대기중인 타이머이고 요청한 만료 시점이 기존 설정된 만료 시점과 변동이 없는 경우 그냥 1을 반환한다.
  • 코드 라인 33에서 요청한 타이머를 제거하고 최종 결정된 만료 시점으로 타이머를 설정한 후 다시 추가 하고 active 시킨다.

 

Slack으로 만료 시간 조정

만료 시간을 조정하여 유사한 만료 시간들끼리 모아 한꺼번에 처리하도록 slack 정렬한다. 타이머 인터럽트가 조금이라도 덜 발생하도록하여 절전과 처리 성능에 도움을 준다.

apply_slack()

kernel/time/timer.c

/*
 * Decide where to put the timer while taking the slack into account
 *
 * Algorithm:
 *   1) calculate the maximum (absolute) time
 *   2) calculate the highest bit where the expires and new max are different
 *   3) use this bit to make a mask
 *   4) use the bitmask to round down the maximum time, so that all last
 *      bits are zeros
 */
static inline
unsigned long apply_slack(struct timer_list *timer, unsigned long expires)
{
        unsigned long expires_limit, mask;
        int bit;

        if (timer->slack >= 0) {
                expires_limit = expires + timer->slack;
        } else {
                long delta = expires - jiffies;

                if (delta < 256)
                        return expires;

                expires_limit = expires + delta / 256;
        }
        mask = expires ^ expires_limit;
        if (mask == 0)
                return expires;

        bit = find_last_bit(&mask, BITS_PER_LONG);

        mask = (1UL << bit) - 1;

        expires_limit = expires_limit & ~(mask);

        return expires_limit;
}

요청된 타이머의 만료 시점을 설정하기 위해 약간의 여유(slack) 시간을 고려하여 새 만료 시점을 산출한다.

  • 코드 라인 17~18에서 slack 값이 0 이상인 경우 만료 시간에 slack 값을 더한다.
  • 코드 라인 19~26에서 slack 값이 음수인 경우 delta tick을 구한 후 256 보다 작은 경우 기존 만료 시간 값을 그대로 사용하고 그렇지 않은 경우 새 만료 시간을 약 0.4% 정도 더 늘린다.
    • do_init_timer() 함수로 타이머 초기값 설정 시 slack은 -1로 설정되어 delta가 일정량 이상일 때 추가 비율을 사용하게 한다.
  • 코드 라인 27~29에서 새 만료 시간이 기존 값과 변동이 없을 정도의 영향이 거의 없으면 그냥 기존 만료 값을 반환한다.
  • 코드 라인 31에서 기존 만료 시점과 새 만료 시점의 변동 비트들 중 최상위 변동 비트를 제외한 새 만료 시점의 하위 비트들을 절삭한다.

 

아래 그림은 100hz 시스템에서 slack으로 9 tick을 준 경우와 timeout으로 2311 tick을 준 경우에 대해 만료 값이 어떻게 변화하는지를 보여준다.

 

timer_pending()

include/linux/timer.h

/**
 * timer_pending - is a timer pending?
 * @timer: the timer in question
 *
 * timer_pending will tell whether a given timer is currently pending,
 * or not. Callers must ensure serialization wrt. other operations done
 * to this timer, eg. interrupt contexts, or other CPUs on SMP.
 *              
 * return value: 1 if the timer is pending, 0 if not.
 */     
static inline int timer_pending(const struct timer_list * timer)
{       
        return timer->entry.next != NULL;
}

타이머 벡터 리스트에서 대기중인 타이머인지 여부를 반환한다.

  • 타이머 벡터 리스트는 환형 더블리스트이므로 타이머가 혼자 등록되어 있어도 head와 연결되는 구조이다.  따라서 null이 들어가 있는 경우는 환형 더블리스트에서 제거된 경우밖에 없다. 즉 리스트에  존재하면 항상 true이다.

 

__mod_timer()

kernel/time/timer.c

static inline int
__mod_timer(struct timer_list *timer, unsigned long expires,
                                                bool pending_only, int pinned)
{
        struct tvec_base *base, *new_base;
        unsigned long flags;
        int ret = 0 , cpu;

        timer_stats_timer_set_start_info(timer);
        BUG_ON(!timer->function);

        base = lock_timer_base(timer, &flags);

        ret = detach_if_pending(timer, base, false);
        if (!ret && pending_only)
                goto out_unlock;

        debug_activate(timer, expires);

        cpu = get_nohz_timer_target(pinned);
        new_base = per_cpu(tvec_bases, cpu);

        if (base != new_base) {
                /*
                 * We are trying to schedule the timer on the local CPU.
                 * However we can't change timer's base while it is running,
                 * otherwise del_timer_sync() can't detect that the timer's
                 * handler yet has not finished. This also guarantees that
                 * the timer is serialized wrt itself.
                 */
                if (likely(base->running_timer != timer)) {
                        /* See the comment in lock_timer_base() */
                        timer_set_base(timer, NULL);
                        spin_unlock(&base->lock);
                        base = new_base;
                        spin_lock(&base->lock);
                        timer_set_base(timer, base);
                }
        }

        timer->expires = expires;
        internal_add_timer(base, timer);

out_unlock:
        spin_unlock_irqrestore(&base->lock, flags);

        return ret;
}

요청한 타이머를 제거하고 최종 결정된 만료 시점으로 타이머를 설정한 후 다시 추가 하고 active 시킨다.

  • 코드 라인 9에서 타이머 통계를 enable 한 경우에 한하여 타이머 사용자를 트래킹할 수 있도록 타이머에 관련 정보를 저장한다.
  • 코드 라인 12에서 타이머 벡터 리스트를 변경할 계획이므로 tvec_base에 lock을 건다.
  • 코드 라인 14~16에서 pending된 타이머인 경우에 한해 해당 타이머 벡터 리스트에서 제거한다. 실패 시 pending only인 경우 처리를 중단하고 빠져나간다.
  • 코드 라인 18에서 디버그 목적의 정보 처리와 trace 출력을 한다.
  • 코드 라인 20에서 nohz idle 타이머를 위한 타겟 cpu를 알아온다.
    • pinned 된 경우 cpu는 반드시 현재 cpu로 사용된다.
  • 코드 라인 21에서 얻어온 cpu로 관리되는 tvec_base를 구해온다.
  • 코드 라인 23~39에서 tvec_base가 변경된 경우 높은 확률로 running_timer가 현재 timer를 처리하는 중이 아니면 타이머의 base를 변경시킨다.
  • 코드 라인 41에서 타이머의 만료 시점을 갱신하고 base의 적절한 타이머 벡터 리스트에 추가한다.

 

타이머 통계

admin 권한으로 타이머 통계를  보려고 시도하면 처음에는 통계가 disable 된 상태에 있기 때문에 아래와 같이 inactive 출력된다.

$ cat /proc/timer_stats
Timer Stats Version: v0.3
Sample period: 0.000 s
Collection: inactive
0 total events

다음과 같이 통계를 enable 시켜본다.

# echo "1" > /proc/timer_stats

그런 후 다시 통계를 살펴본다. (lowres 타이머와 hrtimer가 섞여 있다)

# cat /proc/timer_stats
Timer Stats Version: v0.3
Sample period: 4.530 s
Collection: active
  453,     0 swapper/2        hrtimer_start_range_ns (tick_sched_timer)
   38,     0 swapper/0        hrtimer_start_range_ns (tick_sched_timer)
   50,     7 rcu_preempt      rcu_gp_kthread (process_timeout)
    5,  1632 ifplugd          hrtimer_start_range_ns (hrtimer_wakeup)
   16,     0 swapper/1        hrtimer_start (tick_sched_timer)
   36,     0 swapper/0        hrtimer_start (tick_sched_timer)
    4,  3992 sshd             sk_reset_timer (tcp_write_timer)
   17,     0 swapper/1        usb_hcd_poll_rh_status (rh_timer_func)
    4,  1582 ifplugd          hrtimer_start_range_ns (hrtimer_wakeup)
    4,  2230 ntpd             hrtimer_start_range_ns (posix_timer_fn)
    4,  3467 kworker/u8:2     queue_delayed_work_on (delayed_work_timer_fn)
   10,     0 swapper/0        sk_reset_timer (tcp_delack_timer)
    3, 26686 kworker/2:1      queue_delayed_work_on (delayed_work_timer_fn)
    3,    44 kworker/0:1      queue_delayed_work_on (delayed_work_timer_fn)
    1,  2058 thd              hrtimer_start_range_ns (hrtimer_wakeup)
   25,     0 swapper/1        hrtimer_start_range_ns (tick_sched_timer)
673 total events, 148.565 events/sec

 

timer_stats_timer_set_start_info()

include/linux/timer.h

static inline void timer_stats_timer_set_start_info(struct timer_list *timer)
{
        if (likely(!timer_stats_active))
                return;
        __timer_stats_timer_set_start_info(timer, __builtin_return_address(0));
}

CONFIG_TIMER_STATS 커널 옵션이 설정되었고 “echo 1 > /proc/timer_stats”와 같이 통계를 enable 한 경우에 한하여 타이머 사용자를 트래킹할 수 있도록 타이머 정보에 호출한 함수 주소, 실행 화일명과 pid 값을  저장한다.

 

__timer_stats_timer_set_start_info()

kernel/time/timer.c

void __timer_stats_timer_set_start_info(struct timer_list *timer, void *addr)
{
        if (timer->start_site)
                return;

        timer->start_site = addr;
        memcpy(timer->start_comm, current->comm, TASK_COMM_LEN);
        timer->start_pid = current->pid;
}

타이머 사용자를 트래킹할 수 있도록 타이머 정보에 호출한 함수 주소, 실행 화일명과 pid 값을  저장한다.

 

detach_if_pending()

kernel/time/timer.c

static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
                             bool clear_pending)
{
        if (!timer_pending(timer))
                return 0;

        detach_timer(timer, clear_pending);
        if (!tbase_get_deferrable(timer->base)) {
                base->active_timers--;
                if (timer->expires == base->next_timer)
                        base->next_timer = base->timer_jiffies;
        }
        base->all_timers--;
        (void)catchup_timer_jiffies(base);
        return 1;
}

펜딩된 타이머인 경우 리스트에서 제거한다.

  • 코드 라인 4~5에서 타이머 벡터 리스트에 등록되어 대기하고 있는 타이머가 아닌 경우 이미 deactivate된 경우이므로 0을 반환한다.
  • 코드 라인 7에서 타이머를 리스트에서 제거한다. 만일 clear_pending 요청한 경우 현재 타이머가 다음 타이머를 가리키지 않도록 null을 대입한다.
  • 코드 라인 8~12에서 deferrable(유예) 타이머가 아닌 경우에 한해 active 타이머 수를 감소시킨다. 만일 제거할 타이머가 다음에 처리할 타이머 였으면 base->next_timer에 base->timer_jiffies를 대입하여 다음 것을 준비하라는 의미를 부여한다.
  • 코드 라인 13에서 base에 등록된 전체 타이머 수를 1 감소시킨다.
  • 코드 라인 14에서 base에 등록된 타이머가 하나도 없는 경우 base->timer_jiffies 값을 현재 jiffies로 갱신한다.

 

detach_timer()

kernel/time/timer.c

static inline void detach_timer(struct timer_list *timer, bool clear_pending)
{
        struct list_head *entry = &timer->entry;

        debug_deactivate(timer);

        __list_del(entry->prev, entry->next);
        if (clear_pending)
                entry->next = NULL;
        entry->prev = LIST_POISON2;
}

타이머 리스트에서 요청 타이머를 제거한다. 만일 clear pending 요청이 있는 경우 타이머 엔트리가 다음 타이머와 연결되지 않도록 분리한다.

 

tbase_get_deferrable()

kernel/time/timer.c

/* Functions below help us manage 'deferrable' flag */
static inline unsigned int tbase_get_deferrable(struct tvec_base *base)
{
        return ((unsigned int)(unsigned long)base & TIMER_DEFERRABLE);
}

tvec_base에 deferrable(유예) 플래그가 설정된 경우 true를 반환한다.

  • base 주소의 하위 2비트를 이용하여 2개의 플래그를 설정할 수 있다.
    • TIMER_DEFERRABLE 0x1LU
    • TIMER_IRQSAFE 0x2LU

 

catchup_timer_jiffies()

kernel/time/timer.c

/*
 * If the list is empty, catch up ->timer_jiffies to the current time.
 * The caller must hold the tvec_base lock.  Returns true if the list
 * was empty and therefore ->timer_jiffies was updated.
 */
static bool catchup_timer_jiffies(struct tvec_base *base)
{
        if (!base->all_timers) {
                base->timer_jiffies = jiffies;
                return true;
        }
        return false;
}

등록된 타이머가 하나도 없는 경우 timer_jiffies 값을 현재 jiffies로 갱신하고 true를 반환한다.

 

get_nohz_timer_target()

kernel/sched/core.c

/*
 * In the semi idle case, use the nearest busy cpu for migrating timers
 * from an idle cpu.  This is good for power-savings.
 *
 * We don't do similar optimization for completely idle system, as
 * selecting an idle cpu will add more delays to the timers than intended
 * (as that cpu's timer base may not be uptodate wrt jiffies etc).
 */
int get_nohz_timer_target(int pinned)
{
        int cpu = smp_processor_id();
        int i;
        struct sched_domain *sd;

        if (pinned || !get_sysctl_timer_migration() || !idle_cpu(cpu))
                return cpu;

        rcu_read_lock();
        for_each_domain(cpu, sd) {
                for_each_cpu(i, sched_domain_span(sd)) {
                        if (!idle_cpu(i)) {
                                cpu = i;
                                goto unlock;
                        }
                }
        }
unlock:
        rcu_read_unlock();
        return cpu;
}

nohz idle 타이머를 위한 타겟 cpu를 알아온다.

  • 코드 라인 15~16에서 pinned 요청이 있는 경우, “/proc/sys/kernel/timer_migration”이 설정(default=1) 해제된 경우 또는 현재 cpu가 idle 상태가 아닌 경우에 한해 현재 cpu를 nohz idle 타이머 용도로 사용하기 위해 반환한다.
  • 코드 라인 19에서 스케쥴 domain 수 만큼 루프를 돈다.
  • 코드 라인 20~25에서 해당 스케쥴 domain에 속한 cpu 만큼 루프를 돌며 idle 상태가 아닌 cpu를 반환한다.

 

timer_set_base()

kernel/time/timer.c

static inline void
timer_set_base(struct timer_list *timer, struct tvec_base *new_base)
{
        unsigned long flags = (unsigned long)timer->base & TIMER_FLAG_MASK;

        timer->base = (struct tvec_base *)((unsigned long)(new_base) | flags);
}

타이머의 base를 설정한다. 플래그 값은 그대로 유지한다.

 

internal_add_timer()

kernel/time/timer.c

static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
        (void)catchup_timer_jiffies(base);
        __internal_add_timer(base, timer);
        /*
         * Update base->active_timers and base->next_timer
         */
        if (!tbase_get_deferrable(timer->base)) {
                if (!base->active_timers++ ||
                    time_before(timer->expires, base->next_timer))
                        base->next_timer = timer->expires;
        }
        base->all_timers++;

        /*
         * Check whether the other CPU is in dynticks mode and needs
         * to be triggered to reevaluate the timer wheel.
         * We are protected against the other CPU fiddling
         * with the timer by holding the timer base lock. This also
         * makes sure that a CPU on the way to stop its tick can not
         * evaluate the timer wheel.
         *
         * Spare the IPI for deferrable timers on idle targets though.
         * The next busy ticks will take care of it. Except full dynticks
         * require special care against races with idle_cpu(), lets deal
         * with that later.
         */
        if (!tbase_get_deferrable(base) || tick_nohz_full_cpu(base->cpu))
                wake_up_nohz_cpu(base->cpu);
}

타이머를 요청한 tvec_base에 추가한다. 추가한 타이머가 가장 빨리 이용될 상황이면 base->next_time에 추가한 타이머의 expires 값으로 갱신한다.

  • 코드 라인 3에서 등록된 타이머가 하나도 없는 경우 timer_jiffies를 현재 jiffies 값으로 갱신한다.
  • 코드 라인 4에서 요청 타이머를 5개의 타이머 그룹에 있는 벡터 리스트 배열 중 하나의 적절한 리스트에 추가한다.
    • expires – jiffies 하여 산출된 tick 값에 따라 512(256+64+64+64+64)개의 리스트 중 하나가 선택된다.
  • 코드 라인 8~12에서 deferrable 설정된 타이머가 아닌 경우이면서 동작중인 타이머가 없거나 이 번에 추가할 타이머가 그 다음 expire될 타이머이면 next_timer를 요청 타이머의 expires 시간으로 갱신하고 등록된 active 타이머 수를 증가시킨다.
  • 코드 라인 13에서 등록된 전체 타이머 수를 1 증가시킨다.
  • 코드 라인 28~29에서 tvec_base에 deferrable 타이머가 등록되어 있지 않거나 요청 tvec_base의 cpu가 nohz full로 동작중인 경우 그 cpu를 깨워 idle 상태에서 벗어나게 한다.

 

__internal_add_timer()

kernel/time/timer.c

static void
__internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
        unsigned long expires = timer->expires;
        unsigned long idx = expires - base->timer_jiffies;
        struct list_head *vec;

        if (idx < TVR_SIZE) {
                int i = expires & TVR_MASK;
                vec = base->tv1.vec + i;
        } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
                int i = (expires >> TVR_BITS) & TVN_MASK;
                vec = base->tv2.vec + i;
        } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
                int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
                vec = base->tv3.vec + i;
        } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) { 
                int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
                vec = base->tv4.vec + i;
        } else if ((signed long) idx < 0) {
                /*
                 * Can happen if you add a timer with expires == jiffies,
                 * or you set a timer to go off in the past
                 */
                vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
        } else { 
                int i;
                /* If the timeout is larger than MAX_TVAL (on 64-bit
                 * architectures or with CONFIG_BASE_SMALL=1) then we
                 * use the maximum timeout.
                 */ 
                if (idx > MAX_TVAL) {
                        idx = MAX_TVAL;
                        expires = idx + base->timer_jiffies;
                }
                i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
                vec = base->tv5.vec + i;
        }
        /*
         * Timers are FIFO:
         */
        list_add_tail(&timer->entry, vec);
}

요청 타이머를 5개의 타이머 그룹에 있는 벡터 리스트 배열 중 하나의 적절한 리스트에 추가한다. 추가되는 리스트의 선택은 다음과 같이한다.

  • tv1~tv5의 선택은 만료 시각 – 현재 시각의 delta로 선택한다.
  • 그 후 어레이 인덱스는 만료 시각에서 선택한 tv에 해당하는 bit들 값으로 인덱스를 결정한다.

 

  • expires – base->timer_jiffies 하여 산출된 tick 값에 따라 512(256+64+64+64+64)개의 리스트 중 하나가 선택된다.
    • 예) timer_jiffies=100, hz=100, 7초 후에 timer가 호출되게 하려할 때 expires 값과 추가될 타이머 벡터 리스트는?
      • 7초면 700 tick이 필요하므로 expires=100+700이 대입되고 tv2.vec[32]에 추가된다.

 

타이머 삭제

del_timer()

kernel/time/timer.c

/**
 * del_timer - deactive a timer.
 * @timer: the timer to be deactivated
 *
 * del_timer() deactivates a timer - this works on both active and inactive
 * timers.
 *
 * The function returns whether it has deactivated a pending timer or not.
 * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
 * active timer returns 1.)
 */
int del_timer(struct timer_list *timer)
{
        struct tvec_base *base;
        unsigned long flags;
        int ret = 0;

        debug_assert_init(timer);

        timer_stats_timer_clear_start_info(timer);
        if (timer_pending(timer)) {
                base = lock_timer_base(timer, &flags);
                ret = detach_if_pending(timer, base, true);
                spin_unlock_irqrestore(&base->lock, flags);
        }

        return ret;
}
EXPORT_SYMBOL(del_timer);

타이머를 타이머 벡터 리스트에서 제거하여 deactivate 한다.

  • 코드 라인 20에서 타이머에서 사용자 트래킹 정보를 클리어한다.
  • 코드 라인 21~25에서 타이머 벡터 리스트에 등록되어 대기중인 타이머인 경우 그 리스트에서 제거한다.

 

기타 타이머 함수

 

setup_timer_on_stack()

include/linux/timer.h

#define setup_timer_on_stack(timer, fn, data)                           \
        __setup_timer_on_stack((timer), (fn), (data), 0)

 

__setup_timer_on_stack()

include/linux/timer.h

#define __setup_timer_on_stack(_timer, _fn, _data, _flags)              \
        do {                                                            \
                __init_timer_on_stack((_timer), (_flags));              \
                (_timer)->function = (_fn);                             \
                (_timer)->data = (_data);                               \
        } while (0)

 

__init_timer_on_stack()

include/linux/timer.h

#define __init_timer_on_stack(_timer, _flags)                           \
        init_timer_on_stack_key((_timer), (_flags), NULL, NULL)

 

init_timer_on_stack_key()

include/linux/timer.h

static inline void init_timer_on_stack_key(struct timer_list *timer,
                                           unsigned int flags, const char *name,
                                           struct lock_class_key *key)
{
        init_timer_key(timer, flags, name, key);
}

 

init_timer_key()

kernel/time/timer.c

/**
 * init_timer_key - initialize a timer
 * @timer: the timer to be initialized
 * @flags: timer flags
 * @name: name of the timer
 * @key: lockdep class key of the fake lock used for tracking timer
 *       sync lock dependencies
 *
 * init_timer_key() must be done to a timer prior calling *any* of the
 * other timer functions.
 */
void init_timer_key(struct timer_list *timer, unsigned int flags,
                    const char *name, struct lock_class_key *key)
{
        debug_init(timer);
        do_init_timer(timer, flags, name, key);
}
EXPORT_SYMBOL(init_timer_key);

 

do_init_timer()

kernel/time/timer.c

static void do_init_timer(struct timer_list *timer, unsigned int flags,
                          const char *name, struct lock_class_key *key)
{
        struct tvec_base *base = raw_cpu_read(tvec_bases);

        timer->entry.next = NULL;
        timer->base = (void *)((unsigned long)base | flags);
        timer->slack = -1;
#ifdef CONFIG_TIMER_STATS
        timer->start_site = NULL;
        timer->start_pid = -1;
        memset(timer->start_comm, 0, TASK_COMM_LEN);
#endif
        lockdep_init_map(&timer->lockdep_map, name, key, 0);
}

 

del_singleshot_timer_sync()

include/linux/timer.h

#define del_singleshot_timer_sync(t) del_timer_sync(t)

 

 

del_timer_sync()

kernel/time/timer.c – 1/2

/**
 * del_timer_sync - deactivate a timer and wait for the handler to finish.
 * @timer: the timer to be deactivated
 *
 * This function only differs from del_timer() on SMP: besides deactivating
 * the timer it also makes sure the handler has finished executing on other
 * CPUs.
 *
 * Synchronization rules: Callers must prevent restarting of the timer,
 * otherwise this function is meaningless. It must not be called from
 * interrupt contexts unless the timer is an irqsafe one. The caller must
 * not hold locks which would prevent completion of the timer's
 * handler. The timer's handler must not call add_timer_on(). Upon exit the
 * timer is not queued and the handler is not running on any CPU.
 *
 * Note: For !irqsafe timers, you must not hold locks that are held in
 *   interrupt context while calling this function. Even if the lock has
 *   nothing to do with the timer in question.  Here's why:
 *
 *    CPU0                             CPU1
 *    ----                             ----
 *                                   <SOFTIRQ>
 *                                   call_timer_fn();
 *                                     base->running_timer = mytimer;
 *  spin_lock_irq(somelock);
 *                                     <IRQ>
 *                                        spin_lock(somelock);
 *  del_timer_sync(mytimer);
 *   while (base->running_timer == mytimer);
 *
 * Now del_timer_sync() will never return and never release somelock.
 * The interrupt on the other CPU is waiting to grab somelock but
 * it has interrupted the softirq that CPU0 is waiting to finish.
 *
 * The function returns whether it has deactivated a pending timer or not.
 */

 

kernel/time/timer.c – 2/2

int del_timer_sync(struct timer_list *timer)
{
#ifdef CONFIG_LOCKDEP
        unsigned long flags;

        /*
         * If lockdep gives a backtrace here, please reference
         * the synchronization rules above.
         */
        local_irq_save(flags);
        lock_map_acquire(&timer->lockdep_map);
        lock_map_release(&timer->lockdep_map);
        local_irq_restore(flags);
#endif  
        /*
         * don't use it in hardirq context, because it
         * could lead to deadlock.
         */
        WARN_ON(in_irq() && !tbase_get_irqsafe(timer->base));
        for (;;) {
                int ret = try_to_del_timer_sync(timer);
                if (ret >= 0)
                        return ret;
                cpu_relax();
        }
}
EXPORT_SYMBOL(del_timer_sync);

 

 

SOFTIRQ – TIMER

lowres 타이머의 bottom-half로 동작하는 softirq 핸들러를 알아본다.

run_timer_softirq()

kernel/time/timer.c

/*
 * This function runs timers and the timer-tq in bottom half context.
 */
static void run_timer_softirq(struct softirq_action *h)
{
        struct tvec_base *base = __this_cpu_read(tvec_bases);

        hrtimer_run_pending();

        if (time_after_eq(jiffies, base->timer_jiffies))
                __run_timers(base);
}

cpu에 타이머 tick이 인입될 때 마다 호출되는 timer softirq에 등록한 함수이다.

  • 코드 라인 8에서 hrtimer가 초기화가 안된 경우 실행하게 하고자 매 softirq 호출마다 확인하는 fallback 코드이다.
  • 코드 라인 10~11에서 jiffies가 base->timer_jiffies 이상인 경우 __run_timers() 함수를 호출하여 만료된 타이머 들의 함수를 실행하게 한다.

 

__run_timers()

kernel/time/timer.c

/**
 * __run_timers - run all expired timers (if any) on this CPU.
 * @base: the timer vector to be processed.
 *
 * This function cascades all vectors and executes all expired timer
 * vectors.
 */
static inline void __run_timers(struct tvec_base *base)
{
        struct timer_list *timer;

        spin_lock_irq(&base->lock);
        if (catchup_timer_jiffies(base)) {
                spin_unlock_irq(&base->lock);
                return;
        }
        while (time_after_eq(jiffies, base->timer_jiffies)) {
                struct list_head work_list;
                struct list_head *head = &work_list;
                int index = base->timer_jiffies & TVR_MASK;

                /*
                 * Cascade timers:
                 */
                if (!index &&
                        (!cascade(base, &base->tv2, INDEX(0))) &&
                                (!cascade(base, &base->tv3, INDEX(1))) &&
                                        !cascade(base, &base->tv4, INDEX(2)))
                        cascade(base, &base->tv5, INDEX(3));
                ++base->timer_jiffies;
                list_replace_init(base->tv1.vec + index, head);
                while (!list_empty(head)) {
                        void (*fn)(unsigned long);
                        unsigned long data;
                        bool irqsafe;

                        timer = list_first_entry(head, struct timer_list,entry);
                        fn = timer->function;
                        data = timer->data;
                        irqsafe = tbase_get_irqsafe(timer->base);

                        timer_stats_account_timer(timer);

                        base->running_timer = timer;
                        detach_expired_timer(timer, base);

                        if (irqsafe) {
                                spin_unlock(&base->lock);
                                call_timer_fn(timer, fn, data);
                                spin_lock(&base->lock);
                        } else {
                                spin_unlock_irq(&base->lock);
                                call_timer_fn(timer, fn, data);
                                spin_lock_irq(&base->lock);
                        }
                }
        }
        base->running_timer = NULL;
        spin_unlock_irq(&base->lock);
}

만료된 타이머들의 함수를 실행하게 한다.

  • 코드 라인 12에서 irq를 disable하면서 spinlock을 획득한다.
  • 코드 라인 13~16에서 등록된 타이머가 없는 경우 base->timer_jiffies 를 jiffies 값으로 갱신한다. 갱신된 경우 함수를 빠져나간다.
  • 코드 라인 17에서  jiffies가 base->timer_jiffies 이상인 경우 루프를 돈다.
  • 코드 라인 18~19에서 임시 리스트를 준비한다.
  • 코드 라인 20에서 base->timer_jiffies 값을 사용해서 tv1용 해시 인덱스(0~255)를 산출한다.
  • 코드 라인 25~29에서 인덱스가 0인 경우즉 256분의 1 tick 마다 cascade 루틴이 동작한다. tv2 레벨을 tv1 레벨로 cascade시킨다. tv2의 cascade 결과가 0인 경우 tv3를 tv2로 cascade 시도한다. tv3의 cascade가 0인 경우 tv4를 tv3로 cascade 시도하고 tv4의 cascade 결과가 0인 경우 마지막 tv5를 tv4로 cascade 한다.
    • tv2 -> tv1 cascasde
      • 조건: 인덱스=0 (base->timer_jiffies 값의 2^8단위 마다)
      • 이동: tv2.vec[base->timer_jiffies 의 bit13:8의 6비트 값] 리스트에 등록된 타이머들을 꺼내서 다시 배치한다. 그런 경우 delta가 256 이내인 타이머들에 한해 tv1으로 이동하게 된다.
    • tv3 -> tv2 cascade
      • 조건: tv2 -> tv1 cascade의 결과가 0인 경우 (base->timer_jiffies 값의 2^14단위 마다)
      • 이동: tv3.vec[base->timer_jiffies 의 bit19:14의 6비트 값] 리스트에 등록된 타이머들을 꺼내서 다시 배치한다. 그런 경우 delta가 256*64 이내인 타이머들에 한해 tv2로 이동하게 된다.
    • tv4 -> tv3 cascade
      • 조건: tv3 -> tv2 cascade의 결과가 0인 경우 (base->timer_jiffies 값의 2^20단위 마다)
      • 이동: tv4.vec[base->timer_jiffies 의 bit25:20의 6비트 값] 리스트에 등록된 타이머들을 꺼내서 다시 배치한다. 그런 경우 delta가 256*64*64 이내인 타이머들에 한해 tv3로 이동하게 된다.
    • tv5 -> tv4 cascade
      • 조건: tv4 -> tv3 cascade의 결과가 0인 경우 (base->timer_jiffies 값의 2^26단위 마다)
      • 이동: tv5.vec[base->timer_jiffies 의 bit31:26의 6비트 값] 리스트에 등록된 타이머들을 꺼내서 다시 배치한다. 그런 경우 delta가 256*64*64*64 이내인 타이머들에 한해 tv4로 이동하게 된다.
  • 코드 라인 30~31에서 base->timer_jiffies를 1 증가시키고 이 값으로 tv1의 리스트를 선택하여 이 리스트에 연결된 타이머들을 임시 리스트에 연결한다.
  • 코드 라인 32~37에서 임시 리스트에의 타이머 수 만큼 순회한다.
  • 코드 라인 42에서 타이머에 대한 통계 정보를 업데이트 한다.
  • 코드 라인 44~45에서 base->running_timer에 현재 처리할 타이머를 지정하고 그 타이머를 관리 리스트에서 제거한다. 관련 타이머 수도 감소시킨다.
  • 코드 라인 47~55에서 spinlock을 푼 후 타이머에 지정된 함수를 호출하고 다시 spinlock을 획득한다. 이 때 delayed work queue에서 사용하는 타이머들에서와 같이 timer->base에 TIMER_IRQSAFE 플래그가 사용되는 경우 2 개 이상의 타이머들을 처리하는 중간에 irq disable 상태가 풀리지 못하게 막는 역활을 한다.
  • 코드 라인 58~59에서 처리가 완료되는 경우 base->running_timer에 null을 집어넣어 처리중인 타이머가 없다고 표시하고 spinlock을 해제한다.

 

다음 그림은 타이머 벡터 간의 cascade 조건을 보여준다.

예) base->timer_jiffies 값이 0x400_0000인 경우 tv2 -> tv1, tv3 -> tv2, tv4 -> tv3, tv5 -> tv4의 순서로 full cascade 처리된다.

 

다음 그림은 jiffies값이 35인 시점에 cpu#1에 tick이 발생하고 그 동안 tick이 발생하지 못해 처리 못했던 jiffies 들에 대한 처리를 한꺼번에 처리하도록 한다.

  • jiffies=35인 시점에 26~35까지 처리 못했던 만료된 타이머들의 함수들을 처리한다.

 

INDEX()

kernel/time/timer.c

#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)

base->timer_jiffies 값으로 요청한 tv의 인덱스 값을 반환한다. (N: 0=tv2, 1=tv3, 2=tv4, 3=tv5)

  • 예) base->timer_jiffies=550, INDEX(0) -> 2 (tv2.vec[2])

 

cascade()

kernel/time/timer.c

static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
        /* cascade all the timers from tv up one level */
        struct timer_list *timer, *tmp;
        struct list_head tv_list;

        list_replace_init(tv->vec + index, &tv_list);

        /*
         * We are removing _all_ timers from the list, so we
         * don't have to detach them individually.
         */
        list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
                BUG_ON(tbase_get_base(timer->base) != base);
                /* No accounting, while moving them */
                __internal_add_timer(base, timer);
        }

        return index;
}

요청 타이머 벡터 리스트에 있는 타이머들의 레벨을 한 단계 상승시킨다.

  • 코드 라인 7에서 지정한 tv 타이머 리스트에 연결되어 있는 타이머 들을 임시 tv_list로 옮긴다.
  • 코드 라인 13에서 tv_list에 연결되어 있는 모든 타이머들을 다시 추가하여 적절한 타이머 벡터 리스트에 들어갈 수 있게 한다.
    • base->time_jiffies 값에 따라 다시 타이머 벡터 리스트의 인덱스가 결정된다.

 

다음 그림은 tv2에 있는 두 개의 타이머가 tv1으로 cascade되는 모습을 보여준다.

 

detach_expired_timer()

kernel/time/timer.c

static inline void
detach_expired_timer(struct timer_list *timer, struct tvec_base *base)
{
        detach_timer(timer, true);
        if (!tbase_get_deferrable(timer->base))
                base->active_timers--;
        base->all_timers--;
        (void)catchup_timer_jiffies(base);
}

타이머를 리스트에서 분리하고 관련 카운터들을 갱신한다.

  • 코드 라인 4에서 타이머를 리스트에서 분리한다.
  • 코드 라인 5~6에서 deferrable 타이머가 아닌 경우 active_timers 카운터를 감소시킨다.
  • 코드 라인 7에서 전체 timer 카운터를 감소시킨다.
  • 코드 라인 8에서 등록된 타이머가 하나도 없는 경우에 한해 base->timer_jiffies를 jiffies 값으로 갱신한다.

 

call_timer_fn()

kernel/time/timer.c

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

#ifdef CONFIG_LOCKDEP
        /*
         * It is permissible to free the timer from inside the
         * function that is called from it, this we need to take into
         * account for lockdep too. To avoid bogus "held lock freed"
         * warnings as well as problems when looking into
         * timer->lockdep_map, make a copy and use that here.
         */
        struct lockdep_map lockdep_map;

        lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
#endif
        /*
         * Couple the lock chain with the lock chain at
         * del_timer_sync() by acquiring the lock_map around the fn()
         * call here and in del_timer_sync().
         */
        lock_map_acquire(&lockdep_map);

        trace_timer_expire_entry(timer);
        fn(data);
        trace_timer_expire_exit(timer);

        lock_map_release(&lockdep_map);

        if (count != preempt_count()) {
                WARN_ONCE(1, "timer: %pF preempt leak: %08x -> %08x\n",
                          fn, count, preempt_count());
                /*
                 * Restore the preempt count. That gives us a decent
                 * chance to survive and extract information. If the
                 * callback kept a lock held, bad luck, but not worse
                 * than the BUG() we had.
                 */
                preempt_count_set(count);
        }
}

인수로 받은 fn은 타이머에 설정된 함수이며 이 함수를 호출할 때 인수로 받은 data 를 넘겨준다. 디버그를 위해 trace 출력등이 사용되었다.

 

cascading 없는 타이머 휠로의 발전

lowres 타이머는 커널 v4.8-rc1 에서 새로운 변화를 보여주면서 lowres 타이머에 대한 전반적인 설계가 변경되어 non-cascading wheel의 모델이 소개되었다.

 

참고

 

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.