Linux Kernel Architecture

Chapter 15: Time Management

Each processor in the system has its own data structures for managing timers that run on it. A per-CPU

instance of the following data structure is used as the root element:

kernel/timer.c

struct tvec_t_base_s {

...

unsigned long timer_jiffies;

tvec_root_t tv1;

tvec_t tv2;

tvec_t tv3;

tvec_t tv4;

tvec_t tv5;

} ____cacheline_aligned_in_smp;

The elementstv1totv5represent the individual groups; theirfunction should be clear from the above

description. Of particular interest is thetimer_jiffieselement. It records the time (in jiffies) by which

all timers of the structure were executed. If, for example, the value of this variable is 10,500, the kernel

knows that all timers up to the jiffies value 10,499 have been executed. Usually,timer_jiffiesis equal

to or 1 less thanjiffies. The difference may be a little greater (with very high loading) if the kernel is

not able to execute timers for a certain period.

ImplementingTimerHandling

Handling of all timers is initiated inupdate_process_timesby invoking therun_local_timersfunction.

This limits itself to usingraise_softirq(TIMER_SOFTIRQ)to activate the timer management softIRQ,

which is executed at the next opportunity.^8 run_timer_softirqis used as the handler function of the

softIRQ; it selects the CPU-specific instance ofstruct tvec_t_base_sand invokes__run_timers.

__run_timersimplements the algorithm described above. However, nowhere in the data structures

shown is the urgently required index position for the individual rough categories to be found! The kernel

does not require an explicit variable because all necessary information is contained in thetimer_jiffies

member ofbase. The following macros are defined for this purpose:

kernel/timer.c

#define TVN_BITS (CONFIG_BASE_SMALL? 4 : 6)

#define TVR_BITS (CONFIG_BASE_SMALL? 6 : 8)

#define TVN_SIZE (1 << TVN_BITS)

#define TVR_SIZE (1 << TVR_BITS)

#define TVN_MASK (TVN_SIZE - 1)

#define TVR_MASK (TVR_SIZE - 1)

kernel/timer.c

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

The configuration optionBASE_SMALLcan be defined on small, usually embedded systems to save some

space by using a smaller number of slots than in the regular case. The timer implementation is otherwise

unaffected by this choice.

(^8) Because softIRQs cannot be handled directly, it can happen that the kernel does not perform any timer handling for a few jiffies.
Timers can, therefore, sometimes be activated too late but can never be activated too early.