Dynamic Timers

Dynamic timers may be dynamically created and destroyed. No limit is placed on the number of currently active dynamic timers.

A dynamic timer is stored in the following timer_list structure:

struct timer_list {

struct list_head list; unsigned long expires;

unsigned long data;

void (*function)(unsigned long);

The function field contains the address of the function to be executed when the timer expires. The data field specifies a parameter to be passed to this timer function. Thanks to the data field, it is possible to define a single general-purpose function that handles the time-outs of several device drivers; the data field could store the device ID or other meaningful data that could be used by the function to differentiate the device.

The expires field specifies when the timer expires; the time is expressed as the number of ticks that have elapsed since the system started up. All timers that have an expires value smaller than or equal to the value of jiffies are considered to be expired or decayed.

The list field includes the links for a doubly linked circular list. There are 512 doubly linked circular lists to hold dynamic timers. Each timer is inserted into one of the lists based on the value of the expires field. The algorithm that uses this list is described later in this chapter.

To create and activate a dynamic timer, the kernel must:

1. Create a new timer_list object — for example, t. This can be done in several ways by:

o Defining a static global variable in the code.

o Defining a local variable inside a function; in this case, the object is stored on the Kernel Mode stack.

o Including the object in a dynamically allocated descriptor.

2. Initialize the object by invoking the init_timer(&t) function. This simply sets the links in the list field to null.

3. Load the function field with the address of the function to be activated when the timer decays. If required, load the data field with a parameter value to be passed to the function.

4. If the dynamic timer is not already inserted in a list, assign a proper value to the expires field. Otherwise, update the expires field by invoking the mod_timer( ) function, which also takes care of moving the object into the proper list (discussed shortly).

5. If the dynamic timer is not already inserted in a list, insert the t element in the proper list by invoking the add_timer(&t) function.

Once the timer has decayed, the kernel automatically removes the t element from its list. Sometimes, however, a process should explicitly remove a timer from its list using the del_timer( ) or del_timer_sync( ) functions. Indeed, a sleeping process may be woken up before the time-out is over; in this case, the process may choose to destroy the timer. Invoking del_timer( ) or del_timer_sync( ) on a timer already removed from a list does no harm, so removing the timer within the timer function is considered a good practice. Dynamic timers and race conditions

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:

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. Dynamic timers handling

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 tvl, tv2, tv3, tv4, and tv5 structures (see Figure 6-2).

Continue reading here: Figure 62 The groups of lists associated with dynamic timers

Was this article helpful?

0 0