I. Introduction

The timer module of LWIP implements a general software timer for internal periodic event processing, such as arp and tcp timeouts, which can also be used by users. This article analyzes the implementation of this module.

2. Code Analysis

2.1 Source Code

The source code is located at

timeouts.c

timeouts.h ​

Will compile according to the following conditions

#if LWIP_TIMERS && !LWIP_TIMERS_CUSTOM

That is, LWIP_TIMERS is 1 and LWIP_TIMERS_CUSTOM is 0 for compilation, which is also the default configuration.

2.2 Data Structure

The core data structure of the timer is a one-way linked list. The nodes of the linked list are as follows

struct sys_timeo {
struct sys_timeo *next;
u32_t time;
sys_timeout_handler h;
void *arg;
#if LWIP_DEBUG_TIMERNAMES
const char* handler_name;
#endif /* LWIP_DEBUG_TIMERNAMES */
};

Next forms a singly linked list

time is the absolute time, that is, if the current absolute time lags behind this value, it means that the timer has timed out and the callback function h needs to be executed .

arg can be passed in as a parameter.

handler_name is used for debugging printing information.

2.3 Timeout comparison algorithm

The timer uses absolute time, that is, the time of the timer is compared with the current now time. If time <= now , it means that the timer has timed out and needs to be processed. Otherwise, the timer has not expired and no processing is required.

But there is a problem here, the overflow problem. If time<=now, does it mean that time is ahead of now ? Not necessarily. It may also be that the maximum value of the timer has been reached and it has wrapped around.

For example, if the timer value is 32 bits,

now is 0xFFFFFFFF , time is 0x00000001 ,

time < now , then it may be that time is ahead of now by 0xFFFFFFFE , that is, (0xFFFFFFFF-0x00000001)

It is also possible that time lags behind the time when now is 2 , which is (0x100000000-0xFFFFFFFF)+0x00000001.

We prefer the latter because the time difference is smaller and more in line with the actual situation, because our timing time is generally very small.

The implementation here is

#define LWIP_MAX_TIMEOUT 0x7fffffff

#define TIME_LESS_THAN(t, compare_to) ( (((u32_t)((t)-(compare_to))) > LWIP_MAX_TIMEOUT) ? 1 : 0 )

In fact, we use the idea we mentioned above. We prefer the smaller time difference as the actual situation.

In fact, there is a special article discussing this algorithm, which can be found online.

That is, define half of the maximum range of the timer. For example, the maximum range of 32 bits is 0~0xFFFFFFFF , a total range of 0x100000000 , and half of the range is 0x80000000 , that is, 0~0x7fffffff . As a benchmark, the maximum timer can only be set to this time. A time greater than this time is considered unreasonable, and it is actually wrapping around in the opposite direction.

Here ((u32_t)((t)-( compare_to ))) is calculated as unsigned 32 bits.

If t < compare_to

If t is 1 and compare_to is 2 , then the result of ((u32_t)((t)-(compare_to))) is 0xFFFFFFFF .

Actually it is 0x100000000-0x02 + 0x01.

If t>compare_to

t is 2 , compare_to is 1

Then the result of ((u32_t)((t)-(compare_to))) is 0x1

This expression can be understood as the time t lagging compare_to ( future time ) ,

A more vivid understanding is that ab is how much b needs to catch up to a , that is, how long compare_to takes to catch up to t , and it is possible to go back.

If the lag time is relatively large, greater than half of the total time, that is, 0x7fffffff , we believe that it is actually not a lag but an advance.

Because the tendency to have a shorter time interval is in line with the actual situation.

So if t is much larger than compare_to , greater than TIME_LESS_THAN , we also think that t is not lagging behind compare_to but ahead of compare_to , it just wraps around.

1. Summary

We can understand it from the perspective of catching up in a circle, that is , t and compare_to are racing in a circular world. At a certain moment, we don’t know who is running in front and who is running behind, because there is a possibility of " circling " . So we have an assumption that the speed difference between t and compare_to is not particularly large ( similar to the timing time of our timer is not particularly long ) , so if the distance that t catches up with compare_to is greater than half of the track, we think it is unreasonable, so we think that compare_to is catching up with t .

Therefore, the prerequisite for this algorithm to work is that the timing time cannot be greater than LWIP_MAX_TIMEOUT .

Of course, the interval for handling query timer timeout cannot be greater than LWIP_MAX_TIMEOUT , otherwise it will be impossible to distinguish due to " multiple turns " .

2.4 Built-in timer

Defines an array

const struct lwip_cyclic_timer lwip_cyclic_timers[]

Provide the necessary information to build a timer ( note that it is not the timer itself, but the timer information provided, sys_timeouts_init creates the timer based on this )

The array member structure is as follows

struct lwip_cyclic_timer {
u32_t interval_ms;
lwip_cyclic_timer_handler handler;
#if LWIP_DEBUG_TIMERNAMES
const char* handler_name;
#endif /* LWIP_DEBUG_TIMERNAMES */
};

interval_ms is the execution period of the timer. The above timer requires absolute time. Why is it interval time here? Because now + interval time is absolute time, which will be automatically set during initialization.

handler is the callback function

handler_name is the name used to print the timer.

By default, some built-in timers are defined according to macros.

For example, if LWIP_ARP is enabled , the timer is enabled, the callback function is etharp_tmr , and the interval is 1S .

Users can configure these macros to enable and periodically configure the timer.

#if LWIP_ARP

{ARP_TMR_INTERVAL, HANDLER(etharp_tmr)},

#endif /* LWIP_ARP */

#define ARP_TMR_INTERVAL 1000

Iterate over lwip_cyclic_timers when initializing sys_timeouts_init

Dynamically create a timer through sys_timeout->sys_timeout_abs , and the absolute time of the timer will automatically increase the interval (u32_t) (sys_now() + msecs) based on now ;

Here i = (LWIP_TCP ? 1 : 0), if there is LWIP_TCP , it starts from 1 , and the TCP timer at 0 is handled separately because it does not need to run all the time. If there is no TCP connection, the timer is not needed, so tcp_timer_needed() is called manually for processing.

2.5 Interface Code

sys_timeouts_sleeptime

The timer polling is analyzed later to calculate the time from the head timer in the timer list to the current time.

Returning 0 means the head timer has timed out and needs to be processed. Returning SYS_TIMEOUTS_SLEEPTIME_INFINITE means there is no timer. Other values ​​are the time intervals from the head timer to the present. Because timers are arranged from small to large, you only need to check the head timer.

sys_restart_timeouts

The first timer in the timer list is used as the benchmark and is set to the absolute time of now . Subsequent timers are set according to the deviation from the first timer.

When sys_check_timeouts is not called for a long time , the time base is reset to trigger a time scheduling.

This ensures that if the timer is not executed during a long period of time when sys_check_timeouts is not called, it can be remedied by the next execution.

sys_check_timeouts

Query the timer, starting from the head of the linked list. If the timeout is reached, execute the corresponding callback function and release the timer.

Because they are already sorted, there is no need to search to the end. The timer that finds the first timeout can be ended because the subsequent values ​​are larger and will definitely not time out.

When there is no OS , the user manually calls this function

When there is an OS , the tcpip thread is automatically called.

Note that timers are one-shot and will be deleted after one execution. They need to be recreated for periodic execution.

Personally, I think it is not a good idea to delete and release every time, especially for embedded platforms. The addition of mem and other operations will cause memory fragmentation problems ( if it is implemented using a memory pool, it will be fine, but if the heap is shared, it will have some impact, especially on resource-constrained platforms where the heap is already very small ) , and reduce efficiency.

sys_untimeout

Delete a timer from the timer list

sys_timeout- >sys_timeout_abs

Create a timer and insert it into the linked list according to the timer value from small to large

sys_timeouts_init

Initialize the built-in timer, which has been analyzed before

lwip_cyclic_timer

Built-in timer callback processing

Since timers are one-shot, periodic timers need to recreate the timer.

This callback function is set when the timer is built in

sys_timeout(lwip_cyclic_timers[i].interval_ms, lwip_cyclic_timer, LWIP_CONST_CAST(void *, &lwip_cyclic_timers[i]));

Call back specific callback functions through parameters

const struct lwip_cyclic_timer *cyclic = (const struct lwip_cyclic_timer *)arg;
cyclic->handler();

tcp_timer_needed/tcpip_tcp_timer

TCP timer is processed separately, create a TCP timer

tcpip_tcp_timer will determine whether the timer needs to be repeated based on whether there is a TCP connection.

2.6 Timer Polling

Manual cycle call without OS

sys_check_timeouts

In tcpip_thread thread when there is OS

TCPIP_MBOX_FETCH , i.e. tcpip_timeouts_mbox_fetch , will be called automatically

sys_check_timeouts .

Let's analyze tcpip_timeouts_mbox_fetch

First, sleeptime = sys_timeouts_sleeptime(); gets the time interval from the last timer that is about to time out to now, so that the time interval is used as the timeout sleeptime during mbox_fetch . If the mbox is obtained before this timeout , the message is processed and the above process is repeated in the next loop. Otherwise, wait until the timeout and call sys_check_timeouts(); to process the timer.

sys_timeouts_sleeptime first determines whether there is a timer. If next_timeout is empty, it means that there is no timer that needs to be processed, and the timeout sleeptime can be set to infinity.

If there is a timer, you only need to compare the time of the next_timeout head timer with now . Because timers are arranged from small to large, the first timer to time out must be the head timer. If the time of next_timeout is less than now , it means that the timer has timed out and is set to 0. Then sys_check_timeouts() will be called immediately for processing.

Otherwise, calculate next_timeout and get the interval time by subtracting now from time .

That is to say,

if (sleeptime == SYS_TIMEOUTS_SLEEPTIME_INFINITE) {
  UNLOCK_TCPIP_CORE();
  sys_arch_mbox_fetch(mbox, msg, 0);
  LOCK_TCPIP_CORE();
  return;
} else if (sleeptime == 0) {
  sys_check_timeouts();
  /* We try again to fetch a message from the mbox. */
  goto again;
}

If there is no timer sleeptime == SYS_TIMEOUTS_SLEEPTIME_INFINITE , then sys_arch_mbox_fetch(mbox, msg, 0); parameter 0 means infinite timeout.

It will not return until it gets the message , otherwise it will keep waiting here.

I personally think there is a BUG here. If there is no timer at the beginning and there is no message at this time, the newly created timer will not be processed after that, because it has been waiting for messages here. Although there will be timers at the beginning, so it will not enter here, but it is still not rigorous in logic. Although infinite waiting here can be beneficial to efficiency, because the thread will not be executed if there is no message, I personally think it may be safer to set a fixed timeout interval, so as to ensure that the thread will not be stuck here, and if there is no message after the time is exceeded, it will skip and re-execute, so as to ensure that the newly created timer can be executed, and the maximum error is the fixed interval that is set. This interval can be set based on the balance between the allowable error and efficiency, so as not to affect the efficiency and ensure that the timer can always be executed.

If the sleeptime timer has timed out and sleeptime == 0 , sys_check_timeouts() will be called immediately. Because there is no message, goto again; repeat, no return is needed .

If sleeptime is neither 0 nor infinite, set the timeout as needed.

res = sys_arch_mbox_fetch(mbox, msg, sleeptime);

If res returns a timeout, call sys_check_timeouts to process the timer, goto again; repeat the above process, because there is no message, there is no need to return . If there is a message, return to the upper layer to process the message.

2.7DEBUG

The LWIP_DEBUG_TIMERNAMES macro is defined in lwipopts.h to enable related debug codes .

Otherwise, it is determined by LWIP_DEBUG.

LWIP_DEBUG_TIMERNAMES is SYS_DEBUG if LWIP_DEBUG is defined , otherwise it is 0 .

SYS_DEBUG defaults to LWIP_DBG_OFF and can be changed to LWIP_DBG_ON

#ifndef LWIP_DEBUG_TIMERNAMES
#ifdef LWIP_DEBUG
#define LWIP_DEBUG_TIMERNAMES SYS_DEBUG
#else /* LWIP_DEBUG */
#define LWIP_DEBUG_TIMERNAMES 0
#endif /* LWIP_DEBUG*/
#endif

After enabling the above related debugging code , you also need to enable it in lwipopts.h

TIMERS_DEBUG

Enable as follows

#define TIMERS_DEBUG LWIP_DBG_ON
#define LWIP_DEBUG_TIMERNAMES 1

Of course, DEBUG must also be enabled

#define LWIP_DEBUG 1

and interface macros printed by LWIP_PLATFORM_DIAG .

At this point you can see the printed information as follows. You can use the printout to determine whether the timing is correct and whether the timer is working.

sct calling h=ip_reass_tmr t=0 arg=0x2001548c
tcpip: ip_reass_tmr()
sys_timeout: 0x28213e48 abs_time=6223 handler=ip_reass_tmr arg=0x2001548c
sct calling h=etharp_tmr t=0 arg=0x20015498
tcpip: etharp_tmr()
sys_timeout: 0x28213e68 abs_time=6224 handler=etharp_tmr arg=0x20015498
sct calling h=ip_reass_tmr t=0 arg=0x2001548c
tcpip: ip_reass_tmr()
sys_timeout: 0x28213e48 abs_time=7223 handler=ip_reass_tmr arg=0x2001548c
sct calling h=etharp_tmr t=0 arg=0x20015498
tcpip: etharp_tmr()
sys_timeout: 0x28213e68 abs_time=7224 handler=etharp_tmr arg=0x20015498
sct calling h=ip_reass_tmr t=0 arg=0x2001548c
tcpip: ip_reass_tmr()
sys_timeout: 0x28213e48 abs_time=8223 handler=ip_reass_tmr arg=0x2001548c
sct calling h=ip_reass_tmr t=0 arg=0x2001548c
tcpip: ip_reass_tmr()
sys_timeout: 0x28213e48 abs_time=16223 handler=ip_reass_tmr arg=0x2001548c
sct calling h=etharp_tmr t=0 arg=0x20015498
tcpip: etharp_tmr()
sys_timeout: 0x28213e68 abs_time=16224 handler=etharp_tmr arg=0x20015498

3. Summary ​

Focus on understanding the timer's timeout judgment algorithm.

Note that the timer is a one-time timer and will be deleted after each timeout. It needs to be recreated. This requires attention, and attention should be paid to the impact of frequent creation and deletion on heap management.

Understand the configuration of the timing period of the built-in timer and how to debug the timer.