Timing mechanism of LwIP

Here we mainly introduce Lwip The timing mechanism of

Lwip The design of is based on the process model , The whole protocol stack is handled by one process , It is usually said to be a task . stay Lwip No operating system related functions are used in , Instead, an operating system emulation layer is provided , The operating system simulation layer provides a unique interface to the operating system services , These services include timers , Process synchronization and message passing mechanism . Process synchronization is realized by semaphores , Messaging is implemented using mailboxes , The implementation of timer is what this part needs to introduce .

Lwip Manage the corresponding timing events by maintaining a task related timing linked list . The basic structure of the linked list is shown in the following figure .

Overall structure of scheduled events ：

As can be seen from the figure above , The system passes the global pointer threads Point to the beginning of the linked list , The left column is task related , Each task corresponds to a control block , All tasks passed next The hands are connected together , On the right is the scheduled event corresponding to the task , This structure contains the timing time , Corresponding to the parameters and addresses of the capture function , Each timing event also passes next Pointer fields linked together . therefore , adopt threads Pointer we can find each scheduled event of each task . To add a scheduled event to the task's scheduled linked list , You need to call the function in the context of the task sys_timeout, The work to be done by this function is described below ：

sys_timeout Implementation of function

@1： First, set the current scheduled event timeout Structure allocates memory and assigns values （timeout Structure ）

@2： call sys_arch_timeouts Function to get the scheduled queue of the current task （ The timing events we added are all task related , That is, the task to which the timing event belongs is certain ）

@3： If the scheduled queue of the current task is empty （ As shown in the figure above 2 And 4）, Then hang the scheduled event just allocated to the scheduled queue of the task , return

@4： Entering this step indicates that the scheduled queue of the current task is as shown in the figure above 1 and 3 Two cases . here , If the trigger time of the first scheduled event in the current task scheduled queue is greater than the trigger time of the newly generated scheduled event , Then the trigger time of the newly generated timing event is subtracted from its trigger time , And add a new scheduled event to it ; otherwise , Go to the next step （ such as , If the current timing is 7->4->2, The trigger time of the arrival timing event is 5, Then the new scheduled queue is 5->2->4->2, In this way, the new trigger time of each event is a relative value , The relative object is the trigger time value of the previous event ）

@5： Traverse the scheduled queue of the current task , Every time you enter a cycle , Do the following ：

modify A Of （A/B/C See the following description for the meaning of "etc." ）Atime, Minus Btime, If you don't get to the head of the queue and Ctime No more than Atime, Then continue the next cycle . otherwise , If the queue ends , Will directly A Add to B after , If the relative value is less than C And B Relative value of , shows Atime Between the two , Insert it between the two now , And carry on Ctime - Atime operation . Finally jump out of the loop .

（ Newly generated scheduled event ——A; The scheduled event of the task currently pointed to （ The start of the loop is the first scheduled event on the scheduled queue of the task ）——B; B Subsequent scheduled events ——C; A Trigger time of Atime; B Trigger time of Btime; C Trigger time of Ctime）

For the example given in step 4 , If Atime by 8, Then the final order is 5->2->1->3->2, If Atime by 7, Then for 5->2->2->4->2, if Atime by 6, The order is 5->1->2->4->2, If sorting by actual time value , Then the corresponding results in the three cases are ：5->7->8->11->13; 5->7->7(Atime)->11->13; 5->6->7->11->13.

As can be seen from the above results , The whole process is sorted in ascending order , But the comparison of absolute time value becomes the comparison of relative time value . here ,sys_timeout Function not only adds timing events , And there's sorting , This reduces the burden for subsequent operations . If we use absolute time , The implementation of this function can be simpler , however , Once the trigger time of the first scheduled event has arrived , You also need to traverse the queue to modify the trigger time of subsequent scheduled events , This will affect the efficiency of the whole system .

Here we introduce the structure of scheduled events and how they can be added to the scheduled queue of a task , however , There are no operations related to how the trigger time is consumed and the execution of the timing capture function as we imagined . We will explain this problem later by introducing the following three functions .

sys_mbox_fetch Function implementation and the impact on timing

The execution flow of this function is as follows ：

First , call sys_arch_timeouts Get the scheduled queue of the current task

If the current task has no scheduled queue or the scheduled queue is empty , Call sys_arch_mbox_fetch Function to get the message , here , The time parameter of this function is set to 0, That is, the system will be in a dead state , If the mailbox is empty , The system will be waiting , Until there is a message in the mailbox .

otherwise , That is, the scheduled queue of the task is not empty , All the following operations will be performed ：

If Btime（ See above for the meaning ） Greater than zero , Also call the function sys_arch_mbox_fetch Function to get the message , However, the time parameter of this function is not set to 0, It is Btime. meanwhile , Save its return value with a variable . otherwise , This indicates that the scheduled event should be triggered , Execute its corresponding capture function , therefore , We assign a value of all to the time variable F.

about sys_arch_mbox_fetch Function call , As stated earlier , If the time parameter is 0, Is to wait , If the parameter is set to Btime, The best we can do is wait Btime Time for , If the function gets the message during the time, it returns , The returned time is the actual waiting time , otherwise , Namely Btime.

By the above operation , We have finished setting the time variable , The following operations are based on the value of the time variable . If the trigger time of the scheduled event is up , Then it will be taken from the timing queue , And execute its capture function . After execution, return to the start , Continue to get messages . otherwise , Indicates that the message was obtained before the scheduled time , At this point, just put Btime Subtract the return value saved by the time variable .

You can see from the above description of getting messages from the mailbox , Only the timing of the current scheduled event has not yet arrived , And get the message from the mailbox , This function will return .

sys_sem_wait Function implementation and the impact on timing

The operation of this function is the same as sys_mbox_fetch similar , It's just that the mailbox fetching operation becomes a waiting semaphore , The operations corresponding to the underlying layer are sys_arch_mbox_fetch Turned into sys_arch_sem_wait.

sys_msleep Function implementation and the impact on timing

This function is used to make the system wait in milliseconds , At the same time, allow other tasks to have the opportunity to perform . The basic execution process is as follows ：

call sys_sem_new Create a semaphore

call sys_sem_wait_timeout Conduct sleep operation

Call function sys_sem_free Release semaphore resources created before

Following pair sys_sem_wait_timeout Function implementation for a simple description ：

First, judge the waiting time , If it's not greater than zero , Wait for the semaphore , otherwise , Add a timed event for releasing semaphores , The trigger time is sleep Time . The operation of waiting for semaphore is as follows sys_sem_wait Description of function . From the previous description, we can see that this operation will consume system time .

According to the above description , If a task is in the whole process of its execution , If you do not directly or indirectly call the above three functions or one of them , Then call... In its context sys_timeout The added scheduled event will never be executed .

in addition , The task must also be created by calling the task creation function provided by the operating system simulation layer , otherwise , The corresponding task addition function must be called to add its task id Add to lwip In the task chain of maintenance and management .