RT thread Kernel Implementation (V): timer

Holistic thinking

• The thread delay in the previous chapters is through threads remaining_tick Property to record the delay time , stay SysTick In interruption Scan and update each thread Of remaining_tick, If remaining_tick be equal to 0, Make the thread ready , Time complexity O(n); and Timer The strategy is , Each thread has its own timer , When a thread needs a delay , Suspend the thread first , Then start the built-in timer , And attach the timer to a global timer list maintained by the system rt_timer_list, Each node represents the timer of the thread that is delaying , Nodes are arranged in ascending order according to the delay time , So when the time base is updated Only scan the first node of the system timer list Of timeout_tick, If the first timer has not expired , Then there is no need to judge the latter , Time complexity O(1). The timer structure is as follows ,

  struct rt_timer
  {
        
      struct rt_object parent;                         /*  from  rt_object  Inherit  */
  
      rt_list_t row[RT_TIMER_SKIP_LIST_LEVEL];         /*  node ( Skip list ) */
  
      void (*timeout_func)(void *parameter);           /*  Timeout function  */
      void            *parameter;                      /*  Timeout function parameters  */
  
      rt_tick_t        init_tick;                      /*  The time that the timer actually needs to delay  */
      rt_tick_t        timeout_tick;                   /*  The number of system beats that the timer actually timed out  = rt_tick + init_tick */
  };
  typedef struct rt_timer *rt_timer_t;
  

• Structural members rt_list_t row[RT_TIMER_SKIP_LIST_LEVEL]; Is a data structure jump table (skip list) Application , A space for time search strategy , There will be a more detailed explanation later .
• Structural members void (*timeout_func)(void *parameter); Call this function after the timer times out ;
• Structural members rt_tick_t timeout_tick; Its value timeout_tick = rt_tick + init_tick,rt_tick It is the system when the timer starts tick The number , add init_tick, Indicates that the timer is timed out , System tick The numerical .
• To use a timer, you must first initialize the system timer list .rt_system_timer_init();
• Timer initialization function rt_timer_init(), Called when the thread initializes .

/** *  This function initializes a timer , Usually this function is used to initialize a static timer  * * @param timer  Static timer object  * @param name  The name of the timer  * @param timeout  Timeout function  * @param parameter  Timeout function parameters  * @param time  Timeout of timer  * @param flag  The sign of the timer  */
void rt_timer_init(rt_timer_t  timer,
                   const char *name,
                   void (*timeout)(void *parameter),
                   void       *parameter,
                   rt_tick_t   time,
                   rt_uint8_t  flag)
{
    
    /*  Timer object initialization  */
    rt_object_init((rt_object_t)timer, RT_Object_Class_Timer, name);

    /*  Timer initialization  */
    _rt_timer_init(timer, timeout, parameter, time, flag);
}

Start timer

• rt_err_t rt_timer_start(rt_timer_t timer); Here's a macro RT_TIMER_SKIP_LIST_LEVEL, Indicates the timer skip table level , The default is 1. This function will update the timer flag parent.flag And overtime timeout_tick, Then find the appropriate position in the system timer list and insert the timer node .

/** *  Start timer , And hang the timer to the timer list  * * @param timer  Timer to be started  * * @return  Operation state , RT_EOK on OK, -RT_ERROR on error */
rt_err_t rt_timer_start(rt_timer_t timer)
{
    
    unsigned int row_lvl = 0;
    rt_list_t *timer_list;
    register rt_base_t level;
    rt_list_t *row_head[RT_TIMER_SKIP_LIST_LEVEL];
    unsigned int tst_nr;
    static unsigned int random_nr;


    /*  Close the interrupt  */
    level = rt_hw_interrupt_disable();
    
    /*  Remove the timer from the system timer list  */
    _rt_timer_remove(timer);
    
    /*  Change the status of the timer to non active */
    timer->parent.flag &= ~RT_TIMER_FLAG_ACTIVATED;
    
    /*  Open the interrupt  */
    rt_hw_interrupt_enable(level);

    /*  obtain  timeout tick,  maximal timeout tick  Not greater than  RT_TICK_MAX/2 */
    timer->timeout_tick = rt_tick_get() + timer->init_tick;

    /*  Close the interrupt  */
    level = rt_hw_interrupt_disable();


    /*  Insert a timer into the timer list  */
    /*  Get the root node address of the system timer list ,rt_timer_list Is a global variable  */
    timer_list = rt_timer_list;


    /*  Get the root node address of the first linked list in the system timer list  */
    row_head[0]  = &timer_list[0];
    
    /*  because RT_TIMER_SKIP_LIST_LEVEL be equal to 1, This loop will only execute once  */
    for (row_lvl = 0; row_lvl < RT_TIMER_SKIP_LIST_LEVEL; row_lvl++)
    {
    
        /*  The list is not empty , When no timer is inserted into the system timer list , The loop does not execute  */
        /* RT_TIMER_SKIP_LIST_LEVEL = 1,  be row_lvl Always equal to 0 *  When  row_head[0]->timeout_tick < timer->timeout_tick  When the update row_head[0] Value , That is to the rear  */ 
        for (; row_head[row_lvl] != timer_list[row_lvl].prev; row_head[row_lvl]  = row_head[row_lvl]->next)
        {
    
            struct rt_timer *t;
            
            /*  Get timer list node address  */
            rt_list_t *p = row_head[row_lvl]->next;

            /*  Get the pointer of the parent structure according to the node address  */
            t = rt_list_entry(p,                 /*  Node address  */
                              struct rt_timer,   /*  The data type of the parent structure of the node  */
                              row[row_lvl]);     /*  What is a node called in the parent structure , That is, the name  */
            
            /*  Both timers have the same timeout , Then continue to find the next node in the timer list  */
            if ((t->timeout_tick - timer->timeout_tick) == 0)
            {
    
                continue;
            }
            /* uint  Subtracting the  */
            else if ((t->timeout_tick - timer->timeout_tick) < RT_TICK_MAX / 2)
            {
    
                break;
            }
            
        }
        /* RT_TIMER_SKIP_LIST_LEVEL be equal to 1 when , The conditions will not come true , Will not be executed  */
        /*  If RT_TIMER_SKIP_LIST_LEVEL It's not equal to 1, Here, update to the next level node , Keep looking backwards  */
        if (row_lvl != RT_TIMER_SKIP_LIST_LEVEL - 1)
        {
    
           row_head[row_lvl + 1] = row_head[row_lvl] + 1;	// ------------------------------ ⑴
        }            
    }

    /* random_nr It's a static variable , Used to record how many timers have been started  */
    /* Interestingly, this super simple timer insert counter works very very * well on distributing the list height uniformly. By means of "very very * well", I mean it beats the randomness of timer->timeout_tick very easily * (actually, the timeout_tick is not random and easy to be attacked). */
    random_nr++;
    tst_nr = random_nr;

    /*  Insert the timer into the system timer list  */
    /*  Suppose there is only one timer list ,row_head[0] Indicates the appropriate insertion position found above  */
    rt_list_insert_after(row_head[RT_TIMER_SKIP_LIST_LEVEL - 1],       /*  Two way list root node address  */
                         &(timer->row[RT_TIMER_SKIP_LIST_LEVEL - 1])); /*  The address of the node to be inserted  */ // ---------- ⑵
    
    /* RT_TIMER_SKIP_LIST_LEVEL  be equal to 1, The for The loop will never execute  */
    /*  Here is for random insertion of jump table  */
    for (row_lvl = 2; row_lvl <= RT_TIMER_SKIP_LIST_LEVEL; row_lvl++) 
    {
    
        if (!(tst_nr & RT_TIMER_SKIP_LIST_MASK))
            rt_list_insert_after(row_head[RT_TIMER_SKIP_LIST_LEVEL - row_lvl],
                                 &(timer->row[RT_TIMER_SKIP_LIST_LEVEL - row_lvl]));	// ----------------------------- ⑶
        else
            break;

        tst_nr >>= (RT_TIMER_SKIP_LIST_MASK + 1) >> 1;
    }

    /*  Set the timer flag bit to active  */
    timer->parent.flag |= RT_TIMER_FLAG_ACTIVATED;

    /*  Open the interrupt  */
    rt_hw_interrupt_enable(level);

    return -RT_EOK;
}

• If RT_TIMER_SKIP_LIST_LEVEL by 1,timer_list It's just an ordinary 、 Ordered double linked list .
• If RT_TIMER_SKIP_LIST_LEVEL Greater than 1, The function of the jump table in the code is reflected , quote SkipList That little thing about A picture in .
  
  Timer structure members row[RT_TIMER_SKIP_LIST_LEVEL] Indicates the vertical distribution of the node in the jump table , According to the characteristics of the jump table , The first level linked list must contain all nodes , therefore row[RT_TIMER_SKIP_LIST_LEVEL - 1] Must be hung on rt_timer_list[RT_TIMER_SKIP_LIST_LEVEL - 1] On .
• Look down from the top , First row_head[0] Update to the first node at the top of the jump table , Inside for The purpose of the loop is to find the appropriate node at the current level , And then in The first ⑴ It's about Drop vertically to the next floor , Continue to the next level of search .row_head[row_lvl] The largest node in all nodes smaller than the target value of each layer is stored in the , When the outer layer for After the loop exits ,row_head[row_lvl] Then there is the appropriate insertion position of the first level in the entire jump table , stay The first ⑵ It's about Perform the insert operation , here row_lvl = RT_TIMER_SKIP_LIST_LEVEL - 1.
• The first ⑶ It's about Your code is going up from the first level , Insert randomly . It's easy to find after .

Scan timer

• The purpose of scanning the timer is to find out which threads have timed out , According to the characteristics of the jump table , Just scan the last layer of the jump table , When current_tick >= t->timeout_tick when , This indicates that the timer has timed out , Then call invocation. Timeout function , The parameter passed in is the thread control block address of the thread , Then stop or restart the timer according to the timer flag .

/** *  This function is used to scan the system timer list , When a timeout event occurs  *  Call the corresponding timeout function  * * @note  This function is called in the operating system timer interrupt  */
void rt_timer_check(void)
{
    
    struct rt_timer *t;
    rt_tick_t current_tick;
    register rt_base_t level;

    /*  Get the system time base counter rt_tick Value  */
    current_tick = rt_tick_get();

    /*  Close the interrupt  */
    level = rt_hw_interrupt_disable();

    /*  The system timer list is not empty , Then scan the timer list  */
    while (!rt_list_isempty(&rt_timer_list[RT_TIMER_SKIP_LIST_LEVEL - 1]))
    {
    
        /*  Get the address of the first node timer  */
        t = rt_list_entry(rt_timer_list[RT_TIMER_SKIP_LIST_LEVEL - 1].next,   /*  Node address  */
                        struct rt_timer,                        /*  The data type of the parent structure of the node  */ 
                        row[RT_TIMER_SKIP_LIST_LEVEL - 1]);     /*  The member name of the node in the parent structure  */
        /* uint  If  current_tick > t->timeout_tick,  This indicates that the timer has timed out  */
        if ((current_tick - t->timeout_tick) < RT_TICK_MAX / 2)
        {
    
            /*  First remove the timer from the timer list  */
            _rt_timer_remove(t);

            /*  Call timeout function  */
            t->timeout_func(t->parameter);

            /*  Recapture  rt_tick */
            current_tick = rt_tick_get();

            /*  If t It's a cycle timer , Then reboot  */
            if ((t->parent.flag & RT_TIMER_FLAG_PERIODIC) &&
                (t->parent.flag & RT_TIMER_FLAG_ACTIVATED))
            {
    
                /*  Start timer  */
                t->parent.flag &= ~RT_TIMER_FLAG_ACTIVATED;
                rt_timer_start(t);
            }
            /*  Single timer  */
            else
            {
    
                /*  Stop timer  */
                t->parent.flag &= ~RT_TIMER_FLAG_ACTIVATED;
            }
        }
        else
            break;
    }

    /*  Open the interrupt  */
    rt_hw_interrupt_enable(level);
}

Timeout function

/** *  Thread timeout function  *  When the thread delay expires or the waiting resource is available or expires , This function will be called  * * @param parameter  Formal parameters of the timeout function  */
void rt_thread_timeout(void *parameter)
{
    
    struct rt_thread *thread;

    thread = (struct rt_thread *)parameter;

    /*  Set the error code to timeout  */
    thread->error = -RT_ETIMEOUT;

    /*  Remove the thread from the pending list , This section does not use a pending list  */
    rt_list_remove(&(thread->tlist));

    /*  Insert the thread into the ready list  */
    rt_schedule_insert_thread(thread);

    /*  System scheduling  */
    rt_schedule();
}

The time delay function

• rt_err_t rt_thread_delay(rt_tick_t tick); Suspend the thread first , Then set the timeout of the thread timer , Then start the timer , Execute system scheduling .

/*  The time delay function  */
rt_err_t rt_thread_delay(rt_tick_t tick)
{
    
    return rt_thread_sleep(tick);
}

rt_err_t rt_thread_sleep(rt_tick_t tick)
{
    
    register rt_base_t temp;
    struct rt_thread *thread;
    
    /*  Close the interrupt  */
    temp = rt_hw_interrupt_disable();
    
    /*  Get the thread control block of the current thread  */
    thread = rt_current_thread;

    /*  Hung thread  */
    rt_thread_suspend(thread);

    /*  Set the timeout of the thread timer  */
    rt_timer_control(&(thread->thread_timer), RT_TIMER_CTRL_SET_TIME, &tick);
    
    /*  Start timer  */
    rt_timer_start(&(thread->thread_timer));

    /*  Open the interrupt  */
    rt_hw_interrupt_enable(temp);

    /*  Execute system scheduling  */
    rt_schedule();

    return RT_EOK;
}

Time base update function

• stay SysTick Interrupt is called , The function entity consists of rt_timer_check() Instead of .

void rt_tick_increase(void)
{
    
    rt_tick ++;

	rt_timer_check();
}

Project code

11_timer