Being asynchronously activated, dynamic timers are prone to race conditions. For instance, consider a dynamic timer whose function acts on a discardable resource (e.g., a kernel module or a file data structure). Releasing the resource without stopping the timer may lead to data corruption if the timer function got activated when the resource no longer exists. Thus, a rule of thumb is to stop the timer before releasing the resource:

...
del_timer(&t);
X_Release_Resources( );
...

In multiprocessor systems, however, this code is not safe because the timer function might already be running on another CPU when del_timer( ) is invoked. As a result, resources may be released while the timer function is still acting on them. To avoid this kind of race condition, the kernel offers the del_timer_sync( ) function. It removes the timer from the list, and then it checks whether the timer function is executed on another CPU; in such a case, del_timer_sync( ) waits until the timer function terminates.

Other types of race conditions exist, of course. For instance, the right way to modify the expires field of an already activated timer consists of using mod_timer( ), rather than deleting the timer and recreating it thereafter. In the latter approach, two kernel control paths that want to modify the expires field of the same timer may mix each other up badly. The implementation of the timer functions is made SMP-safe by means of the timerlist_lock spin lock: every time the kernel must access the lists of dynamic timers, it disables the interrupts and acquires this spin lock.

Choosing the proper data structure to implement dynamic timers is not easy. Stringing together all timers in a single list would degrade system performances, since scanning a long list of timers at every tick is costly. On the other hand, maintaining a sorted list would not be much more efficient, since the insertion and deletion operations would also be costly.

The adopted solution is based on a clever data structure that partitions the expires values into blocks of ticks and allows dynamic timers to percolate efficiently from lists with larger expires values to lists with smaller ones.

The main data structure is an array called tvecs, whose elements point to five groups of lists identified by the tv1, tv2, tv3, tv4, and tv5 structures (see Figure 6-2).

Figure 6-2. The groups of lists associated with dynamic timers

The tv1 structure is of type struct timer_vec_root, which includes an index field and a vec array of 256 list_head elements — that is, lists of dynamic timers. It contains all dynamic timers that will decay within the next 255 ticks.

The index field specifies the currently scanned list; it is initialized to 0 and incremented by 1 (modulo 256) at every tick. The list referenced by index contains all dynamic timers that expired during the current tick; the next list contains all dynamic timers that will expire in the next tick; the (index+k)th list contains all dynamic timers that will expire in exactly k ticks. When index returns to 0, it signifies that all the timers in tv1 have been scanned. In this case, the list pointed to by tv2.vec[tv2.index] is used to replenish tv1.

The tv2, tv3, and tv4 structures of type struct timer_vec contain all dynamic timers that will decay within the next 2¹⁴-1, 2²⁰-1, and 2²⁶-1 ticks, respectively.

The tv5 structure is identical to the previous ones, except that the last entry of the vec array includes dynamic timers with extremely large expires fields. It never needs to be replenished from another array.

The timer_vec structure is very similar to timer_vec_root: it contains an index field and a vec array of 64 pointers to dynamic timer lists. The index field specifies the currently scanned list; it is incremented by 1 (modulo 64) every 256*64^i-2 ticks, where i, ranging between 2 and 5, is the tv i group number. As in the case of tv1, when index returns to 0, the list pointed to by tv j .vec[tv j .index] is used to replenish tv i (i ranges between 2 and 4, j is equal to i+1).

Thus, the first element of tv2 holds a list of all timers that expire in the 256 ticks following the tv1 timers; the timers in this list are sufficient to replenish the whole array tv1. The second element of tv2 holds all timers that expire in the following 256 ticks, and so on. Similarly, a single entry of tv3 is sufficient to replenish the whole array tv2.

Figure 6-2 shows how these data structures are connected.

The timer_bh( ) function associated with the TIMER_BH bottom half invokes the run_timer_list( ) auxiliary function to check for decayed dynamic timers. The function relies on a variable similar to jiffies that is called timer_jiffies. This new variable is needed because a few timer interrupts might occur before the activated TIMER_BH bottom half has a chance to run; this happens typically when several interrupts of different types are issued in a short interval of time.

The value of timer_jiffies represents the expiration time of the dynamic timer list yet to be checked: if it coincides with the value of jiffies, no backlog of bottom half functions has accumulated; if it is smaller than jiffies, then bottom half functions that refer to previous ticks must be dealt with. The variable is set to 0 at system startup and is incremented only by run_timer_list( ). Its value can never be greater than jiffies.

The run_timer_list( ) function is essentially equivalent the following C fragment:

struct list_head *head, *curr;
struct timer_list *timer;
void (*fn)(unsigned long);
unsigned long data;
  
spin_lock_irq(&timerlist_lock);
while ((long)(jiffies - timer_jiffies) >= 0) {
    if (!tv1.index) { 
        int n = 1; 
        do { 
            cascade_timers(tvecs[n]); 
        } while (tvecs[n]->index == 1 && ++n < 5)); 
    } 
    head = &tv1.vec[tv1.index];
    for (curr = head->next; curr != head; curr = head->next) {
        timer = list_entry(curr, struct timer_list, list);
        fn = timer->function;
        data= timer->data;
  
        detach_timer(timer);
        timer->list.next = timer->list.prev = NULL;
        running_timer = timer;
        spin_unlock_irq(&timerlist_lock);
        fn(data);
        spin_lock_irq(&timerlist_lock);
        running_timer = NULL;
    }
    ++timer_jiffies; 
    tv1.index = (tv1.index + 1) & 0xff;
} 
spin_unlock_irq(&timerlist_lock);

The outermost while loop ends when timer_jiffies becomes greater than the value of jiffies. Since the values of jiffies and timer_jiffies usually coincide, the outermost while cycle is often executed only once. In general, the outermost loop is executed jiffies - timer_jiffies + 1 consecutive times. Moreover, if a timer interrupt occurs while run_timer_list( ) is being executed, dynamic timers that decay at this tick occurrence are also considered, since the jiffies variable is asynchronously incremented by the PIT’s interrupt handler (see the earlier section Section 6.2.1.1).

During a single execution of the outermost while cycle, the dynamic timer functions included in the tv1.vec[tv1.index] list are executed. Before executing a dynamic timer function, the loop invokes the detach_timer( ) function to remove the dynamic timer from the list. Once the list is emptied, the value of tv1.index is incremented (modulo 256) and the value of timer_jiffies is incremented.

When tv1.index becomes equal to 0, all the lists of tv1 have been checked; in this case, it is necessary to refill the tv1 structure. This is accomplished by the cascade_timers( ) function, which transfers the dynamic timers included in tv2.vec[tv2.index] into tv1.vec, since they will necessarily decay within the next 256 ticks. If tv2.index is equal to 0, the tv2 array of lists must be refilled with the elements of tv3.vec[tv3.index].

Notice that run_timer_list( ) disables interrupts and acquires the timerlist_lock spin lock just before entering the outermost loop; interrupts are enabled and the spin lock is released right before invoking each dynamic timer function, until its termination. This ensures that the dynamic timer data structures are not corrupted by interleaved kernel control paths.

To sum up, this rather complex algorithm ensures excellent performance. To see why, assume for the sake of simplicity that the TIMER_BH bottom half is executed right after the corresponding timer interrupt occurs. Then, in 255 timer interrupt occurrences out of 256 (in 99.6% of the cases), the run_timer_list( ) function just runs the functions of the decayed timers, if any. To replenish tv1.vec periodically, it is sufficient 63 times out of 64 to partition the list pointed to by tv2.vec[tv2.index] into the 256 lists pointed to by tv1.vec. The tv2.vec array, in turn, must be replenished in 0.02 percent of the cases (that is, once every 163 seconds). Similarly, tv3 is replenished every 2 hours and 54 minutes, and tv4 is replenished every 7 days and 18 hours. tv5 doesn’t need to be replenished.