struct tvec_base_t -- data structures for dynamic timers

struct tvec_base_t -- data structures for dynamic timers

    Stringing together all timers in a single list would degrade system performance, because 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, because the insertion and deletion operations would also be costly.
   
    The adopted solution is based on a clever date structure that partitions the expires values into blocks of ticks and allows dynamic timers of percolate efficiently from lists with larger expires values to lists with smaller ones. Moreover, in multiprocessor systems the set of active dynamic timers is split among the various CPUs.

    The main data structure for dynamic timers is a per-CPU variable named tvec_bases: it includes NR_CPUS elements, one for each CPU in the system. Each element is a tvec_base_t structure, which include all data needed to handle the dynamic timers bound to the corresponding CPU:

struct tvec_t_base_s {
    spinlock_t        lock;
    struct timer_list *running_timer;
    unsigned long     timer_jiffies;
    tvec_root_t       tv1;
    tvec_t            tv2;
    tvec_t            tv3;
    tvec_t            tv4;
    tvec_t            tv5;
} ____cacheline_aligned_in_smp;

typedef struct tvec_t_base_s tvec_base_t;

    The tv1 field is a structure of type tvec_root_t, which includes a vec array of 256 list_head elements -- that is, lists of dynamic timers. It contains all dynamic timers, if any, that will decay within the next 2^8-1 = 255 ticks.

typedef struct tvec_root_s {
    struct list_head vec[TVR_SIZE];
} tvec_root_t;

     tv1
|----------|
|          |       timer_list        timer_list        timer_list
|----------|      |----------|      |----------|      |----------|
| -vec[i] -|<---->|entry     |<---->|entry     |<---->|entry     |
|----------|      |expires   |      |expires   |      |expires   |
|          |      |function()|      |function()|      |function()|
|          |      |data      |      |data      |      |data      |
|          |      |*base     |      |*base     |      |*base     |
|          |      |----------|      |----------|      |----------|
|          |
|          |       timer_list        timer_list
|----------|      |----------|      |----------|
| -vec[j] -|<---->|entry     |<---->|entry     |
|----------|      |expires   |      |expires   |
|          |      |function()|      |function()|
|          |      |data      |      |data      |
|          |      |*base     |      |*base     |
|          |      |----------|      |----------|
|----------|
struct tvec_root_t

    The tv2, tv3, and tv4 fields are structure of type tvec_t consisting of a vec array of 64 list_head elements. These lists contain all dynamic timers that will decay within the next 2^14-1 = 16383, 2^20-1 = 1048575, and 2^26-1 = 67108863 ticks, respectively.

typedef struct tvec_s {
    struct list_head vec[TVN_SIZE];
} tvec_t;


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

    The timer_jiffies field represents the earlist expiration time of the dynamic timers yet to be checked: if it coincides with the value of jiffies, no backlog of deferrable functions has accumulated; if it is smaller than jiffies, then lists of dynamic timers that refer to previous ticks must be dealt with. The field is set to jiffies ay system startup and is increased only by the run_timer_softirq() function. Notice that the timer_jiffies field might drop a long way bebind jiffies when the deferrable functions that handle dynamic timers are not executed for a long time -- for instance because these functions have been disabled or because a large number of interrupt handlers have been executed.

    In multiprocessor systems, the running_timer field points to the timer_list structure of the dynamic timer that is currently handled by the local CPU.