[Linux Kernel] 시간과 타이머

이번 글에선 시간 관련 코드를 짜는 방법을 다뤄보겠다. 타이머도 다룰 건데, low resolution timer (보통 'the timer wheel'이라고 언급된다.)를 다룰 것이다. high resolution timer나 bottom-half에서 사용하는 softirq, tasklet, workqueue 등도 다루려 했으나 워낙 방대해서 천천히 글로 남겨볼 생각이다.

 

심심해서 넣는 타이머 사진(?)

시간의 측정

타이머 인터럽트와 jiffies

커널의 시간은 타이머 인터럽트를 통해 관리된다. 타이머 인터럽트는 초당 10번, 초당 1000번 처럼 정해진 빈도가 있으며, 이는 HZ로 정의되며,  HZ가 작을수록 오차가 더 줄어드므로 시간의 해상도가 높아진다. 다만 초당 인터럽트 발생 수가 높아지면 그만큼 인터럽트 처리를 위한 오버헤드가 발생한다. HZ 값은 아키텍처마다 다르다.

 

커널 내에는 시스템이 시작한 이후 타이머 인터럽트의 발생 횟수를 저장하는 "jiffies" 라는 카운터가 존재한다. (jiffies는 unsigned long volatile jiffies로 정의되어있다.) 1 jiffy = 1/HZ 초 이므로, HZ jiffy = 1초의 시간을 나타낸다. jiffies의 값이 현재 10000이고 HZ = 1000이라면, 시스템이 부팅한지 jiffies / HZ = 10초가 지났다는 것을 알 수 있다.

시간의 비교

time_after, time_before, time_after_eq, time_before_eq

이 네 함수들은 jiffies의 값을 비교하는 데 사용된다. time_after(a, b)는 a가 b보다 이후일 때 참이다. time_before(a, b)는 a가 b보다 이전일 때 참이다. time_xxxx_eq는 a == b인 경우도 포함한다.

#include <linux/jiffies.h>

/*
 *	These inlines deal with timer wrapping correctly. You are 
 *	strongly encouraged to use them
 *	1. Because people otherwise forget
 *	2. Because if the timer wrap changes in future you won't have to
 *	   alter your driver code.
 *
 * time_after(a,b) returns true if the time a is after time b.
 *
 * Do this with "<0" and ">=0" to only test the sign of the result. A
 * good compiler would generate better code (and a really good compiler
 * wouldn't care). Gcc is currently neither.
 */
#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)

#define time_after_eq(a,b)	\
	(typecheck(unsigned long, a) && \
	 typecheck(unsigned long, b) && \
	 ((long)((a) - (b)) >= 0))
#define time_before_eq(a,b)	time_after_eq(b,a)

딜레이를 주는 방법

busy waiting

위에서 살펴본 time_after, time_before, time_before_eq, time_after_eq는 두 jiffy 값을 비교하기 위한 매크로로 정의된다. time_before 매크로로 3초동안 대기하는 것을 코드로 구현하면, 다음과 같이 작성할 수 있다.

#include <linux/time.h>

void wait_in_secs(int secs)
{
	unsigned long delay;

	delay = jiffies + 3 * HZ;
	while (time_before(jiffies, delay));
}

물론 이 방법은 매우 비효율적이다. 우선 jiffies가 volatile이기 때문에 cache를 거치지 않고 메모리에서 바로 읽어온다. 그리고 busy loop을 돌기 때문에 이걸 수억번은 읽어올 텐데 듣기만 해도 끔찍하다. 그리고 참고할 점은 jiffies 값은 매 타이머 인터럽트마다 갱신되기 때문에, 인터럽트가 비활성화된 상태에서는 절대 사용해선 안된다. 영원히 busy loop에서 빠져나오지 못하게 된다.

schedule

#include <linux/time.h>

void wait_in_secs(int secs)
{
	unsigned long delay;

	delay = jiffies + 3 * HZ;
	while (time_before(jiffies, delay))
		schedule();
}

busy waiting 방식은 그동안 프로세서가 아무것도 하지 못하기 때문에 낭비이다. 대신에 schedule 함수를 호출하면 delay를 기다리는 동안 다른 프로세스를 실행하도록 할 수 있다. 하지만 이 방법도 문제가 있는데, 다른 프로세스에 프로세서를 넘기면 (특히 시스템이 매우 바쁠 때) 언제 다시 현재 프로세스로 돌아올지 알 수 없다. 다시 말해서 생각했던 시간보다 더 나중에 루프를 빠져나올 수도 있다. 그래서 schedule 후에 돌아오는 timeout을 지정해주려면 schedule_timeout 함수를 사용해야 한다.

 

ndelay, udelay, mdelay

아주 작은 단위 (nano, micro)의 실행을 지연해야 한다면 한다면 software loop로 시간을 지연해야 한다. 보통 jiffy는 1~10ms 정도마다 증가하므로, 위에서 살펴본 방법으로는 작은 단위의 실행 지연을 할 수 없다. ndelay는 나노초, udelay는 마이크로초, mdelay는 밀리초 단위로 루프를 돈다. 단, 오버플로우를 방지하기 위해 단위에 맞게 함수를 사용해야 한다.

커널 타이머

딜레이를 주는 방식은 동기적이므로 기다리는 동안 커널은 아무 일도 하지 못한다. 비동기적으로 커널에게 "10초만 있다가 이 작업을 실행해줘"라고 부탁하려면 타이머를 사용해야 한다. 주의할 점은 오차가 존재한다는 점이다. 타이머는 타이머 인터럽트가 발생할 때마다 처리되므로, 타이머 인터럽트 주기 (1/HZ) 초보다 정밀할 수 없다. ^[각주:1]

 

타이머의 특징은 다음과 같다.

- 타이머는 자기 자신을 다시 등록할 수 있다. (callback 함수에서 다시 등록하면 된다.)

- 타이머는 등록한 CPU에서 실행된다. (CPU와 CPU 사이에서 주고받지 않는다.)

struct timer_list

/* include/linux/timer.h
struct timer_list {
	/*
	 * All fields that change during normal runtime grouped to the
	 * same cacheline
	 */
	struct hlist_node	entry;
	unsigned long		expires;
	void			(*function)(struct timer_list *);
	u32			flags;

#ifdef CONFIG_LOCKDEP
	struct lockdep_map	lockdep_map;
#endif
};

expires는 타이머가 만료되는 시간으로, 보통 jiffies + @로 설정된다. 그 다음에 오는 function은 타이머가 만료되었을 때 실행되는 콜백 함수이다. flags는 타이머의 속성을 나타내는 플래그로, timer.h에 다음과 같이 설명되어있다. 

/* include/linux/timer.h */

/**
 * @TIMER_DEFERRABLE: A deferrable timer will work normally when the
 * system is busy, but will not cause a CPU to come out of idle just
 * to service it; instead, the timer will be serviced when the CPU
 * eventually wakes up with a subsequent non-deferrable timer.
 *
 * @TIMER_IRQSAFE: An irqsafe timer is executed with IRQ disabled and
 * it's safe to wait for the completion of the running instance from
 * IRQ handlers, for example, by calling del_timer_sync().
 *
 * Note: The irq disabled callback execution is a special case for
 * workqueue locking issues. It's not meant for executing random crap
 * with interrupts disabled. Abuse is monitored!
 *
 * @TIMER_PINNED: A pinned timer will not be affected by any timer
 * placement heuristics (like, NOHZ) and will always expire on the CPU
 * on which the timer was enqueued.
 *
 * Note: Because enqueuing of timers can migrate the timer from one
 * CPU to another, pinned timers are not guaranteed to stay on the
 * initialy selected CPU.  They move to the CPU on which the enqueue
 * function is invoked via mod_timer() or add_timer().  If the timer
 * should be placed on a particular CPU, then add_timer_on() has to be
 * used.
 */
#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_INIT_FLAGS	(TIMER_DEFERRABLE | TIMER_PINNED | TIMER_IRQSAFE)
#define TIMER_ARRAYSHIFT	22
#define TIMER_ARRAYMASK		0xFFC00000

근데 이상한 점이 있다. 보통 콜백함수에는 데이터를 인자로 넘겨준다. 근데 왜 데이터는 없고 timer_list*만 넘겨줄까? 궁금해서 찾아봤다 - Improving the kernel timers API (2017, lwn.net) 여기서 API를 바꾼 이유를 알려주고, stackoverflow 스레드에서 from_timer로 데이터를 가져오는 방법을 알려준다. (아래에서 다룰 예제에도 구현되어있다.)

타이머의 초기화와 등록

timer_setup

/**
 * timer_setup - prepare a timer for first use
 * @timer: the timer in question
 * @callback: the function to call when timer expires
 * @flags: any TIMER_* flags
 *
 * Regular timer initialization should use either DEFINE_TIMER() above,
 * or timer_setup(). For timers on the stack, timer_setup_on_stack() must
 * be used and must be balanced with a call to destroy_timer_on_stack().
 */
#define timer_setup(timer, callback, flags)			\
	__init_timer((timer), (callback), (flags))

#define timer_setup_on_stack(timer, callback, flags)		\
	__init_timer_on_stack((timer), (callback), (flags))

timer_list를 초기화하는 함수이다. timer_list, function, flags를 받는다.

mod_timer

타이머를 초기화했다고 끝난 건 아니다, 타이머를 커널에 등록해야 한다. 타이머 등록은 mod_timer 또는 add_timer로 수행된다. 주의할 점은 정확히 expires에 명시된 시간에 실행되지 않을 수도 있다는 것이다. 타이머는 정확하지 않을 수 있다. 하지만 최대한 expires 근처에서 실행하려고 노력할 것이다.

add_timer

/**
 * add_timer - start a timer
 * @timer: the timer to be added
 *
 * The kernel will do a ->function(@timer) callback from the
 * timer interrupt at the ->expires point in the future. The
 * current time is 'jiffies'.
 *
 * The timer's ->expires, ->function 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, MOD_TIMER_NOTPENDING);
}
EXPORT_SYMBOL(add_timer);

add_timer는 현재 등록하는 타이머가 이미 등록되지 않은 경우에만 실행해야 하며, 호출 전에 반드시 expires, function 필드가 초기화되어있음을 보장해야 한다.

/**
 * 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)
{
	return __mod_timer(timer, expires, 0);
}
EXPORT_SYMBOL(mod_timer);

mod_timer는 이미 등록한 (하지만 아직 실행되지는 않은) 타이머의 시간을 고치는 함수이다. timer_list의 포인터, 새로 갱신할 expires (jiffies 기준)를 받는다. 주석을 보면 del_timer(timer); timer->expires = expires; add_timer(timer); 와 동일하다고 나와있다. 즉, 현재 타이머(timer_list)가 기존에 등록되었다면 제거하고 등록하고, 없으면 그냥 등록한다. 이 함수는 기존에 존재하지 않는 타이머를 등록할 때도 사용할 수 있다. mod_timer로 등록한 타이머가 기존에 존재하지 않았다면 0을 리턴하고, 기존에 존재하는 타이머의 시간을 수정했다면 1을 리턴한다. 

타이머의 제거

타이머는 보통 두 가지로 나뉜다. 하나는 미래에 해야 할 작업을 수행하는 타이머와, 나머지 하나는 어떤 작업에 대한 timeout을 알려주기 위한 타이머이다. 보통 전자의 경우에는 시간이 만료되어서 function을 호출해 작업을 수행하는 경우가 많다면, 후자의 경우에는 timeout이 지나기 전에 이벤트가 발생하면 timeout을 취소해야 한다. 이처럼 타이머를 종종 취소하는 경우가 있는데, 이때는 del_timer와 del_timer_sync를 사용한다.

del_timer

/**
 * del_timer - deactivate 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 timer_base *base;
        unsigned long flags;
        int ret = 0;

        debug_assert_init(timer);

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

        return ret;
}
EXPORT_SYMBOL(del_timer);

del_timer는 등록되었지만, 아직 실행되지는 않은 타이머를 제거한다. 이미 실행된 타이머는 알아서 제거되므로 이에 대해서는 del_timer를 호출할 필요가 없다.

del_timer_sync

#if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT_RT)
/**
 * 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.
 */
int del_timer_sync(struct timer_list *timer)

del_timer_sync는 SMP 환경에서만 정의되며, 그 외에는 del_timer와 동일하다. del_timer_sync가 리턴된된 후에는 SMP 환경에서, 현재 프로세서가 아닌 다른 프로세서에서도 모두 종료되었음을 보장한다. (동기적으로 기다린다.)

timer example

간단하게 타이머를 이용해 1초마다 로그를 남기는 모듈 예제이다.

타이머가 스스로를 다시 등록하기 때문에, race condition을 막기 위해서 spinlock을 사용했다.

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/time.h>
#include <linux/spinlock.h>

#define MODULE_NAME "TIMER"
#define DELAY (1 * HZ)

struct timer_data {
        int value;
        spinlock_t lock;
        struct timer_list timer;
        bool isActive;
};

struct timer_data my_data = {};

void timer_callback(struct timer_list *timer) {
        struct timer_data *data = from_timer(data, timer, timer);

        data->value++;
        printk(KERN_INFO "[%s] value is = %d\n", __func__, data->value);
        spin_lock(&data->lock);
        if (data->isActive)
                mod_timer(timer, jiffies + DELAY);
        spin_unlock(&data->lock);
}

int __init timer_init(void) {
        printk("[%s] creating timer...\n", __func__);

        /* initialization */
        my_data.isActive = true;
        spin_lock_init(&my_data.lock);
        timer_setup(&my_data.timer, timer_callback, 0);

        /* register timer */
        mod_timer(&my_data.timer, jiffies + DELAY);
        return 0;
}

void __exit timer_exit(void) {
        int ret;

        spin_lock(&my_data.lock);
        my_data.isActive = false;
        ret = del_timer(&my_data.timer);
        spin_unlock(&my_data.lock);

        printk("[%s] deleting timer..., ret = %d\n", __func__, ret);
}

module_init(timer_init);
module_exit(timer_exit);

MODULE_LICENSE("GPL");

참고 문서

Linux Device Drivers book - Bootlin

How does linux handle overflow in jiffies?

Improving the kernel timers API [LWN.net]

Linux kernel: Why add_timer() is modifying my "expires" value?

Timers

 

1. 심지어 2015년에 에 새로 도입된 'non-cascading timer wheel'에서는 오버헤드를 줄이는 대신 나중에 실행될 타이머일 수록 오차가 더 커진다. 타이머의 구현부가 궁금하다면 Reinventing the timer wheel (2015, lwn.net)을 참고해보자. 실제 커밋은 timer: Switch to a non cascading wheel에서 확인할 수 있다. [본문으로]