Abstract:The task sorted linked list of Hongmeng light kernel is a very important and basic data structure, which is used in business scenarios such as task delayed expiration/timeout wake-up.
This article will continue to introduce you to the important data structure in the source code of the Hongmu Light Kernel: TaskSortLinkAttr. The task sorted linked list of Hongmeng light kernel is a very important and basic data structure, which is used in business scenarios such as task delayed expiration/timeout wake-up. In this article the source involved in OpenHarmony LiteOS -m kernel, for example, can be in the open source site https://gitee.com/openharmony… To obtain.
1 task sorting linked list
Let’s first look at the data structure of the task sorting link. Task sorted list is a circular bidirectional linked list array. Task sorted list attribute structure tasksortLinkAttr, as the head node of the bidirectional linked list, points to the first element of the bidirectional linked list array. It also maintains cursor information and records the current position information. Let’s first look at the definition of the structure of a sorted list property.
1.1 Definition of task sorting linked list attribute structure
The tasksortLinkAttr structure for sorted linked list attributes is defined in the kernel\include\los_task.h header file. This structure defines LOS_DL_LIST *sortLink, the cursor UINT16 cursor, and a reserved field that is not currently used.
The source is as follows:
typedef struct {
LOS_DL_LIST *sortLink;
UINT16 cursor;
UINT16 reserved;
} TaskSortLinkAttr;In the file kernel\ SRC \los_task.c, we define a global variable of type tasksortLinkAttr, g_tasksortLink, whose member variable sortLink is the header of the sorted linked list. Reference to a circular bidirectional list array of length 32. The member variable Cursor acts as a cursor to record the current cursor position of the circular array. The source code is as follows.
LITE_OS_SEC_BSS TaskSortLinkAttr g_taskSortLink;Let’s use a diagram to illustrate it. The task sorted list is a circular bidirectional linked list array, the length is 32, each element is a bidirectional linked list, mount the task LosTaskCB linked list node timerList. The member variable idxrollNum of the task LOSTASKCB records the index and scroll number of the array. The member variable of the global variable G_TASKSORTLINK records the current cursor position. Each Tick, the cursor points to the next position. It takes 32 ticks to turn a round. When the array is run to a position where the list is not empty, the number of scrolls maintained by the first node is reduced by 1. Such a data structure is similar to the dial of a clock, also known as a time wheel.
Let’s take an example to show how a task sorting list based on a time wheel implementation can manage a task delay timeout. If the current cursor is 1, the delay of a task is 72 ticks, 72=2*32+8, the sorting index is 8, and the number of scrolls is 2. INSERT TASKS INTO ARRAY AT SORTINDEX + CURSOR =9; INSERT TASKS INTO ARRAY AT SORTINDEX + CURSOR =9; As the Tick time progresses, it takes 8 ticks from the current cursor position to the array index position 9. When running to 9, if the scroll number is greater than 0, it decreases the scroll number by 1. After 2 more rounds, 72 ticks is needed, and the task is delayed and can be removed from the sorted list. The number of rolls of the first node of the bidirectional linked list corresponding to each array element indicates how many turns are needed before the node task expires. The number of rolls of the second linked list node should be added to the number of rolls of the first node, representing the number of turns that the second node needs to turn. And so on.
The schematic diagram is as follows:
1.2 Task sorting linked list macro definition
Some macro definitions related to task sorting lists are defined in the OS_TSK_SORTLINK_LEN header. The length of the bidirectional linked list array for the delayed task is defined as 32 bits, 5 bits for the high order and 27 bits for the low order. For the timeout time of the task, take the high 27 bits as the scroll number and the low 5 bits as the array index.
The source is as follows:
#define OS_TSK_SORTLINK_LEN 32 /** * #define OS_TSK_HIGH_BITS 5 */ #define OS_TSK_HIGH_BITS 5U /** * #define OS_TSK_LOW_BITS (32u-os_tsk_high_bits) /** * Maximum number of scrolls: 0 XFFFF FFDF, 1111 0111 1111 1111 1111 1111 1101 1111 */ #define OS_TSK_MAX_ROLLNUM (0xFFFFFFFFU - OS_TSK_SORTLINK_LEN) /** * The bit width of the task delay time number: 5 */ #define OS_TSK_SORTLINK_LOGLEN 5 / #define OS_TSK_SORTLINK_LOGLEN 5 / #define OS_TSK_SORTLINK_LOGLEN 1, 0001 1111 */ #define OS_TSK_SORTLINK_MASK #define OS_TSK_HIGH_BITS_MASK (os_tsk_sortlink_len-1u) /** ** Scroll number high order mask :1111 1000 0000 0000 0000 0000 0000 0000 0000 0000 */ #define OS_TSK_HIGH_BITS_MASK (OS_TSK_HIGH_BITS_MASK (OS_TSK_SORTLINK_MASK << OS_TSK_LOW_BITS) /** * Low order mask for scroll number :0000 0111 1111 1111 1111 1111 1111 1111 */ #define OS_TSK_LOW_BITS_MASK (~OS_TSK_HIGH_BITS_MASK)Task sorting linked list operation
Let’s take a look at the operations of the task sorting list, including initialization, insertion, deletion, scroll number update, and getting the next due date.
2.1 Initialize the sorted list
During the system kernel initialization startup phase, the task sorting list is initialized in the function UINT32 OsTaskInit(VOID). C :main() –> kernel\ SRC \los_init. C :LOS_KernelInit() –> kernel\ SRC \los_task.c:OsTaskInit().
Initialize the Sort List function source code as follows:
LITE_OS_SEC_TEXT_INIT UINT32 OsTaskInit(VOID) { UINT32 size; UINT32 index; LOS_DL_LIST *listObject = NULL; . ⑴ size = sizeof(LOS_DL_LIST) * OS_TSK_SORTLINK_LEN; listObject = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); ⑵ if (listObject == NULL) {(VOID)LOS_MemFree(m_aucSysMem0, g_taskCBArray); ⑵ if (listObject == NULL) {(VOID)LOS_MemFree(m_aucSysMem0, g_taskCBArray); return LOS_ERRNO_TSK_NO_MEMORY; } ⑶ (VOID)memset_s((VOID *)listObject, size, 0, size); (4) g_taskSortLink. SortLink = listObject; g_taskSortLink.cursor = 0; for (index = 0; index < OS_TSK_SORTLINK_LEN; ⑸ los_listInit (listObject); } return LOS_OK; }(1) The code calculates the memory size of the bidirectional linked list that needs to be applied, and OS_TSK_SORTLINK_LEN is 32, that is, it needs to apply memory space for 32 bidirectional linked list nodes. Then apply for memory, and return the corresponding error code when the memory application fails at ⑵. ⑶ The memory area of the initialization application is 0, etc. (4) Assign the applied bidirectional linked list node to the linked list node of g_tasksortLink. SORTLINK, as the head node of the sorted list, cursor and cursor are initialized to 0. Then the ⑸ loop, call los_listInit () to initialize each element of the bidirectional list array as a bidirectional loop.
2.2 Insertion sort linked list
The function to insert the sorted list is ostAskAdd2TimerList (). This function is called when a task waits for resources such as mutex/semaphore to add the task to the corresponding sorted list. The function takes two input parameters, the first parameter LOSTASKCB * TASKCB to specify the task to defer, and the second parameter UINT32 TIMEOUT to specify the timeout wait.
The source is as follows:
LITE_OS_SEC_TEXT VOID OsTaskAdd2TimerList(LosTaskCB *taskCB, UINT32 timeout) { LosTaskCB *taskDelay = NULL; LOS_DL_LIST *listObject = NULL; UINT32 sortIndex; UINT32 rollNum; ⑴ sortIndex = timeout &os_tsk_sortLink_mask; rollNum = (timeout >> OS_TSK_SORTLINK_LOGLEN); ⑵ (sortIndex > 0)? 0 : (rollNum--); (3) EVALUATE_L (taskCB - > idxRollNum rollNum); ⑷ ⑷ SORTINDEX = (SORTINDEX + G_TASKSORTLINK. CURSOR); sortIndex = sortIndex & OS_TSK_SORTLINK_MASK; 5] EVALUATE_H (taskCB - > idxRollNum sortIndex); ⑹ ListObject = g_TaskSortLink.sortLink + sortIndex; ⑺ if (listObject->pstNext == listObject) {los_listTailINSERT (listObject, & taskCb-> timerList); } else {⑻ TaskDelay = LOS_DL_LIST_ENTRY((ListObject)->pstNext, lostAskCB, timerList); Do {DEGREIF (uWROLLNum (taskDelay-> idxrollNum) <= uWROLLNum (taskCB-> idxrollNum)) {uWROLLNumSub (taskCB-> idxrollNum), taskDelay->idxRollNum); } else {→ → → → → → → → → → → → → → → → → → → → → → → → → → → → → → → → → → → → break; } 11 taskDelay = LOS_DL_LIST_ENTRY(taskDelay-> timerlist.pstnext, LosTaskCB, timerList); } while (&taskDelay->timerList ! = (listObject)); ⑿ LOS_ListTailInsert (& taskDelay - > timerList, & taskCB - > timerList); }}⑴ The code calculates the low 5 bits of the wait time timeout as the array index, and the high 27 bits as the scroll number ROLLNUM. The mathematical meaning of these two lines of code is to take the quotient of the wait time at 32 as the scroll number, and the remainder as the index of the array. ⑵ code, if the remainder is 0, can be divisible, the scroll number is reduced by 1. The reason for the subtracting 1 design is that in the function VOID OstAskScan (VOID), when each tick arrives, if the scroll number is greater than 0, the scroll number is subtracted by 1 and the scroll continues for one more circle. This function VOID OstAskScan (VOID) will be examined later in the article.
(3) The code assigns the scroll number to the low 27 bits of task taskCB-> idxrollNum. (4) Add a cursor to the array index and execute ⑸ to the task taskcB-> idxrollNum (5 bits). It obtains the head node of the two-way linked list according to the array index, and ⑺ inserts the two-way linked list directly if the list is empty. If the list is not empty, the execution of the task task taskDelay to get the first linked list node, and then loop through the bidirectional linked list, the task inserted into the appropriate location. (1) If the number of rolls of taskCB is greater than or equal to the number of rolls of taskCB, subtract the number of rolls of taskCB from the number of rolls of taskCB, then fetch the next node and proceed. If the number of rolls of tasktaskcb to be inserted is less than the number of rolls of tasks of the current linked list node, subtract the number of rolls of tasktaskcb to be inserted from the number of rolls of tasks of the current linked list node, then jump out of the loop. (12) To complete the task insertion. The insertion process can be understood in combination with the schematic diagram above.
2.3 Remove from sorted linked list
The function removed from the sorted list is VOID ostimerListDelete (lostAskCB taskCB). In scenarios such as task restore/delete, you need to call this function to remove the task from the task sorting list. This function contains a single parameter, LOSTASKCB TASKCB, which specifies the task to be removed from the sorted list.
The source is as follows:
LITE_OS_SEC_TEXT VOID OsTimerListDelete(LosTaskCB *taskCB) { LOS_DL_LIST *listObject = NULL; LosTaskCB *nextTask = NULL; UINT32 sortIndex; (1) sortIndex = UWSORTINDEX (taskCB - > idxRollNum); ⑵ listObject = g_taskSortLink. SortLink + sortIndex; ⑵ listObject = g_taskSortLink + sortIndex; (3) if (listObject! = taskCb-> timerlist.pstnext) {⑷ nextTask = LOS_DL_LIST_ENTRY(taskCb-> timerlist.pstnext, lostaskCB, timerList); UWROLLNUMADD(nextTask->idxRollNum, taskCB->idxRollNum); } [5] LOS_ListDelete (& taskCB - > timerList); }(1) The code gets the numeric index of the task to be removed from the sorted list. ⑵ gets the listObject, the head node of the sorted list. ⑶ The code at (4) determines whether the node to be deleted is the last node. If not, the code at (4) obtains the task nextTask corresponding to the next node to be deleted, increases the scroll number of the node to be deleted in the scroll number of the next node, and then executes the code at (5) to execute the deletion operation. If it is the last node, simply delete it by running the code at ⑸.
2.4 Gets the expiration time of the next timeout
The function that gets the expiration time of the next timeout is ostasknextSwitchTimeGet (), and let’s examine its code.
The source is as follows:
UINT32 OsTaskNextSwitchTimeGet(VOID) { LosTaskCB *taskCB = NULL; UINT32 taskSortLinkTick = LOS_WAIT_FOREVER; LOS_DL_LIST *listObject = NULL; UINT32 tempTicks; UINT32 index; ⑴ for (index = 0; index < OS_TSK_SORTLINK_LEN; Index ++) {⑵ listObject = g_tasksortLink.sortLink + (((g_tasksortLink.index) % os_tsk_sortLink_len); (3) if (! Los_listEmpty (listObject)) {⑷ taskCB = LOS_DL_LIST_ENTRY((listObject)->pstNext, lostaskCB, timerList); ⑸ tempTicks = (index == 0)? OS_TSK_SORTLINK_LEN : index; ⑹ TempTicks += (UINT32)(UINT32)(uWrollNum ((UINT32) taskCb-bb0 idxrollNum) * os_tsk_sortLink_len); ⑺ if (tasksortLinkTick > TempTicks) {tasksortLinkTick = TempTicks; } } } return taskSortLinkTick; }(1) The code loops through the bidirectional linked list array, and the code at (2) gets the listObject, the head node of the sorted list, starting from the current cursor position. (3) The code determines whether the sorted list is empty. If the sorted list is empty, it continues to traverse the next array. If the list is not empty, then the code gets the task corresponding to the first linked list node in the sorted list. Use 32 tick count if the numeric traversal index is 0, otherwise use specific numeric index. ⑹ Obtain the number of tasks to roll, calculate the waiting time required, plus the time needed to roll one circle calculated at ⑸. Where he calculates the minimum time to wait, that is, the fastest time for the next due date.
Sort lists and Tick time
After a task is added to the sorted list, how will the number of scrolls in the sorted list be updated as time passes by tick by tick?
Each time a tick passes, the system calls the tick interrupt handler, OsTickHandler(), which is implemented in the kernel\ SRC \los_tick.c file. The following is a snippet of the function, with the timeout of each task at the ⑴.
LITE_OS_SEC_TEXT VOID OsTickHandler(VOID) { #if (LOSCFG_BASE_CORE_TICK_HW_TIME == 1) platform_tick_handler(); #endif g_ullTickCount++; #if (LOSCFG_BASE_CORE_TIMESLICE == 1) OsTimesliceCheck(); # endif (1) OsTaskScan (); // task timeout scan #if (LOSCFG_BASE_CORE_SWTMR == 1) (VOID)OsSwtmrScan(); #endif }Take a closer look at the function OstaskScan () to understand the relationship between sorted lists and tick time. The function is implemented in the kernel\base\los_task.c file. The code snippet is as follows:
LITE_OS_SEC_TEXT VOID OsTaskScan(VOID) { LosTaskCB *taskCB = NULL; BOOL needSchedule = FALSE; LOS_DL_LIST *listObject = NULL; UINT16 tempStatus; UINTPTR intSave; intSave = LOS_IntLock(); ⑴ g_tasksortlink. cursor = (g_tasksortlink. cursor + 1) % OS_TSK_SORTLINK_LEN; ⑴ g_tasksortlink. cursor = (g_tasksortlink. cursor + 1) % OS_TSK_SORTLINK_LEN; listObject = g_taskSortLink.sortLink + g_taskSortLink.cursor; ⑵ if (listObject->pstNext == listObject) {LOS_IntRestore(intSave); ⑵ if (listObject->pstNext == listObject) {LOS_IntRestore(intSave); return; } ⑶ for (taskCB = LOS_DL_LIST_ENTRY((listObject)->pstNext, LosTaskCB, timerList); &taskCB->timerList ! = (listObject);) { tempStatus = taskCB->taskStatus; ⑷ if (uWROLLNUM (taskCb-> idxrollNum) > 0) {uWROLLNumDec (taskCb-> idxrollNum); break; } [5] LOS_ListDelete (& taskCB - > timerList); ⑹ if (tempStatus & OS_TASK_STATUS_PEND) {taskCb-> taskStatus &= ~(OS_TASK_STATUS_PEND); LOS_ListDelete(&taskCB->pendList); taskCB->taskSem = NULL; taskCB->taskMux = NULL; } ⑺ else if (tempStatus & OS_TASK_STATUS_EVENT) {taskCb-> taskStatus &= ~(OS_TASK_STATUS_EVENT);} ⑺ else if (tempStatus & OS_TASK_STATUS_EVENT) {taskCb-> taskStatus &= ~(OS_TASK_STATUS_EVENT); } ⑻ else if (tempStatus & OS_TASK_STATUS_PEND_QUEUE) {los_listDelete (&taskCB->pendList); taskCB->taskStatus &= ~(OS_TASK_STATUS_PEND_QUEUE); } else { taskCB->taskStatus &= ~(OS_TASK_STATUS_DELAY); } 'levies the if (! (tempStatus & OS_TASK_STATUS_SUSPEND)) { taskCB->taskStatus |= OS_TASK_STATUS_READY; OsHookCall(LOS_HOOK_TYPE_MOVEDTASKTOREADYSTATE, taskCB); OsPriqueueEnqueue(&taskCB->pendList, taskCB->priority); needSchedule = TRUE; } if (listObject->pstNext == listObject) { break; } taskCB = LOS_DL_LIST_ENTRY(listObject->pstNext, LosTaskCB, timerList); } LOS_IntRestore(intSave); → if (needSchedule) {LOS_Schedule(); }}(1) The code updates the cursor of the global variable g_tasksortLink to point to the next position in the list array, and then fetches the listObject, the head of the list at that position. ⑵ If the list is empty, return. If the bidirectional linked list is not empty, a ⑶ loop is performed to traverse each linked list node. (4) If the scroll number of the linked list node is greater than 0, then the scroll number is reduced by 1, indicating that the task needs to wait another round. If the number of scrolls is equal to 0, the task timeout expires. Execute ⑸ to delete from the sorted list. Next, we need to deal with each task state separately. If the code is blocked, cancel the blocking state and remove it from the blocked linked list. ⑺ Unblocks the blocking state if the task is blocked in an event. If the task is blocked in the queue, remove it from the blocked linked list, cancel the blocking status. If not, cancel the delay status OS_TASK_STATUS_DELAY. If the code is in the pending state, set the task to ready state, join the task ready queue, and set the rescheduling flag. If we set the need to reschedule, call the scheduling function to trigger task scheduling.
summary
Mastery of TaskSortLinkAttr, an important data structure, will give further study, analysis of the source code of Hongmeng light kernel laid a foundation, so that the subsequent learning is easier. Subsequent will launch more share articles, please look, also welcome you to share the experience of learning, light use HongMeng kernel and if you have any questions, Suggestions, can leave a message to us: https://gitee.com/openharmony… . In order to more easily find HongMeng kernel code warehouse, suggest to https://gitee.com/openharmony… , follow Watch, thumb up Star, and Fork to your account, thank you.
Click on the attention, the first time to understand Huawei cloud fresh technology ~