Abstract ： This article will introduce LiteOS Several data structures commonly used in source code , Include : Bidirectional circular linked list LOS_DL_LIST, Priority queue Priority Queue, Sort list SortLinkList etc. .
I'm learning Huawei LiteOS When it comes to source code , We often encounter the use of some data structures . If you don't know how to use them , read LiteOS It's hard to understand the source code 、 Very laborious . This article will introduce LiteOS Several data structures commonly used in source code , Include : Bidirectional circular linked list LOS_DL_LIST, Priority queue Priority Queue, Sort list SortLinkList etc. . During the presentation , Will be combined with related drawings , Cultivate the plane imagination ability of data structure , Help to better learn and understand the usage of these data structures .
What is involved in this paper LiteOS Source code , Can be in LiteOS Open source sites https://gitee.com/LiteOS/LiteOS obtain .
Let's first look at the most used two-way circular list Doubly Linked List.
1、LOS_DL_LIST Bidirectional circular linked list
Double linked list LOS_DL_LIST The core code is kernelincludelos_list.h Header file , contain LOS_DL_LIST Structure definition 、 some inline Inline function LOS_ListXXX, There are also some macro definitions related to bidirectional linked lists LOS_DL_LIST_XXXX.
Two way linked list source code 、 Sample program code 、 The development documents are as follows ：
- kernelincludelos_list.h Two way linked list header file page access source https://gitee.com/LiteOS/Lite....
- demoskernelapilos_api_list.c Double linked list Demo Program webpage access source code https://gitee.com/LiteOS/Lite....
- Development guide two way linked list document online document https://gitee.com/LiteOS/Lite...
1.1 LOS_DL_LIST Bidirectional linked list structure
Bidirectional linked list structure LOS_DL_LIST The definition is as follows . I can see you , The structure of a two-way linked list is very simple 、 Universal 、 abstract , Include only precursors 、 The next two nodes , Responsible for connecting the two-way linked list role . The two-way linked list does not contain any business data information , Business data information is maintained in the business structure . Bidirectional linked list is used as a member of business structure , The usage examples will be explained later .
typedef struct LOS_DL_LIST { struct LOS_DL_LIST *pstPrev; /** The current node's pointer to the precursor node */ struct LOS_DL_LIST *pstNext; /** The current node's pointer to the successor node */ } LOS_DL_LIST;
Starting from any node in the double linked list , Can easily access its predecessor and successor nodes , This form of data structure makes the bidirectional linked list look up 、 Insert 、 Delete and other operations , It's very convenient for you . Because of the ring structure of the two-way linked list , The status of any node is equal . In terms of business , You can create a node as Head Head node , The linked list node of the business structure starts from HEAD The node starts to mount . from head Node in turn traverse the next node , The last one is not equal to Head Nodes of nodes are called Tail Tail node . This Tail So is the node Head The precursor of the node . from Head Look ahead , It can be found faster Tail node .
Let's see. LiteOS How to use bidirectional linked list structure in kernel code . Here's the mutex structure LosMuxCB Definition , It contains two-way linked lists LOS_DL_LIST muxList; Member variables ：
typedef struct { LOS_DL_LIST muxList; /** A bidirectional list of mutexes */ LosTaskCB *owner; /** The current task holding the lock TCB */ UINT16 muxCount; /** The number of times a mutex is held */ UINT8 muxStat; /** Mutex state OS_MUX_UNUSED, OS_MUX_USED */ UINT32 muxId; /** The mutex handler ID*/ } LosMuxCB;
Bidirectional circular list can link all mutex , The relationship between linked list and other business members is shown in the figure below ：
LiteOS The two-way linked list of provides the user with the following initialization two-way list , increase 、 Delete the linked list node , Judge whether the node is empty , Get linked list node , Get the structure of the linked list , Traversal double linked list , Traversal contains two-way list structure and other functions . Let's study in detail 、 Analyze the code .
1.2 LOS_DL_LIST Bidirectional list initialization
1.2.1 LOS_ListInit(LOS_DL_LIST *list)
LOS_DL_LIST Two members of *pstPrev and *pstNext, yes LOS_DL_LIST Pointer to struct type . You need to apply for a two-way linked list node with a length of sizeof(LOS_DL_LIST) A memory space of . After applying for memory for the linked list node , Initialization can be called LOS_ListInit(LOS_DL_LIST *list) Method , Link this node into a circular two-way list . When initializing the linked list , There is only one linked list node , The antecedent and successor nodes of this node are themselves .
The linked list node is initialized as a linked list , As shown in the figure ：
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list) { list->pstNext = list; list->pstPrev = list; }
in addition , A macro is also provided LOS_DL_LIST_HEAD, Define a bidirectional list node and initialize it as bidirectional list .
#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }
1.2.2 LOS_ListEmpty(LOS_DL_LIST *list)
This interface is used to judge whether the linked list is empty . If the precursor of a two-way list / All subsequent nodes are themselves , There is only one linked list HEAD Head node , Linked list node without service structure attached , Call the list empty .
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list) { return (BOOL)(list->pstNext == list); }
1.3 LOS_DL_LIST Two way linked list node operation
LiteOS Bidirectional linked list provides three ways to insert linked list nodes , Insert... After the specified list node LOS_ListAdd、 Tail insertion LOS_ListTailInsert、 Head insertion LOS_ListHeadInsert. Nodes inserted in the head , Starting from the head, the first traversal goes to , Nodes inserted from the tail , The last one traverses to .
1.3.1 LOS_ListAdd(LOS_DL_LIST list, LOS_DL_LIST node)
This API Interface to linked list node *list Insert a linked list node into the bidirectional linked list *node, The insertion position is in the linked list node *list Behind . As shown in the figure , After insertion ,*node The subsequent nodes of are list->pstNext,*node The preorder node of is *list.list->pstNext The preorder node of is *node,*list The follow-up is *node node .
Icon ：
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node) { node->pstNext = list->pstNext; node->pstPrev = list; list->pstNext->pstPrev = node; list->pstNext = node; }
1.3.2 LOS_ListTailInsert(LOS_DL_LIST list, LOS_DL_LIST node)
This API Interface to linked list node *list Insert a linked list node into the bidirectional linked list *node, The insertion position is in the linked list node *list In front of , stay list->pstPrev After the node .
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node) { LOS_ListAdd(list->pstPrev, node); }
1.3.3 LOS_ListHeadInsert(LOS_DL_LIST list, LOS_DL_LIST node)
This API Interface and LOS_ListAdd() The interface performs the same function , To linked list node *list Insert a linked list node into the bidirectional linked list *node, The insertion position is in the linked list node *list Behind .
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
{
LOS_ListAdd(list, node);
}
LiteOS Two way linked list provides two ways to delete linked list nodes , Specified node deletion LOS_ListDelete、 Delete and initialize to a new linked list LOS_ListDelInit.
1.3.4 LOS_ListDelete(LOS_DL_LIST *node)
This API The interface links the list nodes *node Delete from the two-way linked list where you are . After the node is deleted , May need to call Free() Function to release the memory occupied by the node . As shown in the figure ,*node The preorder of the following nodes is changed to *node Foreword to ,*node Before the node, the following node is changed to *node Subsequent to , And put *node Preorder of nodes 、 Subsequent nodes set to null.
Icon ：
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelete(LOS_DL_LIST *node) { node->pstNext->pstPrev = node->pstPrev; node->pstPrev->pstNext = node->pstNext; node->pstNext = NULL; node->pstPrev = NULL; }
1.3.5 LOS_ListDelInit(LOS_DL_LIST *list)
This API The interface links the list nodes *list Delete from the two-way linked list where you are , And reinitialize the deleted node to a new bidirectional linked list .
*list The preorder of the following nodes is changed to *list Foreword to ,*list Before the node, the following node is changed to *list Subsequent to . and LOS_ListDelete() The difference is , It's not the same *list Preorder of nodes 、 Subsequent nodes set to null, Instead, reinitialize the deleted node to a new one with *list For the head node of the two-way list .
Source code is as follows ：
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelInit(LOS_DL_LIST *list) { list->pstNext->pstPrev = list->pstPrev; list->pstPrev->pstNext = list->pstNext; LOS_ListInit(list); }
LiteOS Bidirectional linked list also provides access to linked list nodes 、 Get the address of the structure containing the linked list .
1.3.6 LOS_DL_LIST_LAST(object)
This macro definition gets the precursor node of the linked list .
Source code is as follows ：
#define LOS_DL_LIST_LAST(object) ((object)->pstPrev)
1.3.7 LOS_DL_LIST_FIRST(object)
This macro definition gets the successor node of the linked list .
Source code is as follows ：
#define LOS_DL_LIST_FIRST(object) ((object)->pstNext)
1.3.8 LOS_OFF_SET_OF(type, member)
This macro definition is based on the structure type name type And the name of the member variable in it member, obtain member Member variables relative to structs type The memory address offset of . On the application scenario , The business structure contains two-way linked lists as members , When you know the memory address of a bidirectional linked list member variable , And this offset , You can further obtain the memory address of the business structure .
Source code is as follows ：
#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)
1.3.9 LOS_DL_LIST_ENTRY(item, type, member)
According to the business structure type name type、 The name of the two-way linked list member variable member, And bidirectional linked list memory pointer variables item, Use this macro to define LOS_DL_LIST_ENTRY You can get the memory address of the business structure .
Let's demonstrate this macro with a real example LOS_DL_LIST_ENTRY How it is used . Mutually exclusive control block Structure LosMuxCB The code has been shown above , There is a member variable of a two-way linked list LOS_DL_LIST muxList. In the method of creating mutex LOS_MuxCreate() in ,⑴ The code at gets an idle bidirectional linked list node pointer address from the idle mutex linked list LOS_DL_LIST *unusedMux, Take this as the first parameter , Structure name LosMuxCB And its member variables muxList, As the second 、 The third parameter , Use macros LOS_DL_LIST_ENTRY The pointer variable address of the structure can be calculated LosMuxCB *muxCreated, see ⑵ Code .
LITE_OS_SEC_TEXT UINT32 LOS_MuxCreate(UINT32 *muxHandle) { ...... LosMuxCB *muxCreated = NULL; LOS_DL_LIST *unusedMux = NULL; ...... ⑴ unusedMux = LOS_DL_LIST_FIRST(&g_unusedMuxList); LOS_ListDelete(unusedMux); ⑵ muxCreated = LOS_DL_LIST_ENTRY(unusedMux, LosMuxCB, muxList); ...... }
From this example , It's easier to understand , This macro defines what scenarios can be used for , Readers can read more examples of using this macro , Strengthen understanding .
Source code is as follows ：
Source code implementation , Based on the memory address of bidirectional linked list node , And the address offset of the bidirectional linked list member variable in the structure , The memory address of the structure can be calculated .
#define LOS_DL_LIST_ENTRY(item, type, member) ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))
1.4 LOS_DL_LIST Double loop list traversal
LiteOS Bidirectional circular list provides two ways to traverse bidirectional list ,LOS_DL_LIST_FOR_EACH and LOS_DL_LIST_FOR_EACH_SAFE.
1.4.1 LOS_DL_LIST_FOR_EACH(item, list)
The macro definition LOS_DL_LIST_FOR_EACH Traversal double linked list , The first input parameter of the interface represents the pointer variable of the bidirectional linked list node , In the process of traversal, it points to the next linked list node in turn . The second input parameter is the starting node of the bidirectional list to traverse . This macro is a loop condition part , The user's business code is written in the code block behind the macro {} Inside .
Let's demonstrate this macro with a real example LOS_DL_LIST_FOR_EACH How it is used . stay kernelbaseschedsched_sqlos_priqueue.c In file ,UINT32 OsPriQueueSize(UINT32 priority) The fragment of the function is as follows ：
&g_priQueueList[priority] It's a two-way list we're going to traverse ,curNode Point to the linked list node in the traversal process , see ⑴ Office code . For complete code, please visit our open source site .
UINT32 OsPriQueueSize(UINT32 priority) { UINT32 itemCnt = 0; LOS_DL_LIST *curNode = NULL; ...... ⑴ LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) { ...... task = OS_TCB_FROM_PENDLIST(curNode); ...... } return itemCnt; }
Source code is as follows ：
#define LOS_DL_LIST_FOR_EACH(item, list) for (item = (list)->pstNext; (item) != (list); item = (item)->pstNext)
1.4.2 LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)
The macro definition LOS_DL_LIST_FOR_EACH_SAFE and LOS_DL_LIST_FOR_EACH The only difference is that there are multiple input parameters next, This parameter represents the next node of the traversed bidirectional list node . This macro is used to safely delete , If you delete the traversal item, Does not affect continue traversal .
Source code is as follows ：
#define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) for (item = (list)->pstNext, next = (item)->pstNext; (item) != (list); item = next, next = (item)->pstNext)
1.5 LOS_DL_LIST Traversing a structure containing a two-way list
LiteOS Bidirectional list provides three macro definitions to traverse the structure containing bidirectional list members ,LOS_DL_LIST_FOR_EACH_ENTRY、LOS_DL_LIST_FOR_EACH_ENTRY_SAFE and LOS_DL_LIST_FOR_EACH_ENTRY_HOOK.
1.5.1 LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)
The macro definition LOS_DL_LIST_FOR_EACH_ENTRY Traversal double linked list , The first input parameter of the interface represents the pointer variable of the structure containing bidirectional linked list members , The second input parameter is the starting node of the bidirectional list to traverse , The third entry parameter is the name of the structure to get , The fourth input parameter is the name of the member variable of the bidirectional linked list in the structure .
Let's demonstrate this macro with a real example LOS_DL_LIST_FOR_EACH_ENTRY How it is used . stay kernelbaseschedsched_sqlos_priqueue.c In file ,LosTaskCB *OsGetTopTask(VOID) The fragment of the function is as follows . Structure LosTaskCB Contains two-way linked list member variables pendList,&g_priQueueList[priority] Is the corresponding task priority priority Of pendList Two-way linked list . Will traverse this bidirectional list in turn &g_priQueueList[priority], According to traversal to the list node , Get the task structure in turn LosTaskCB Pointer variable for newTask, Such as ⑴ As shown in the code .
LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID) { UINT32 priority; UINT32 bitmap; LosTaskCB *newTask = NULL; ...... ⑴ LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) { ...... OsPriQueueDequeue(&newTask->pendList); ...... } ...... }
Source code is as follows ：
Source code implementation ,for Loop initialization statement item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member) A pointer variable that represents a structure that contains members of a bidirectional linked list item, Conditional test statements &(item)->member != (list) The loop condition indicates that when a two-way linked list traverses a circle to its own node , Stop the cycle . Loop UPDATE statement
item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member)) in , Use (item)->member.pstNext Traverse to the next linked list node , Then get the pointer variable of the next structure according to this node item, Until the end of traversal . #define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member); &(item)->member != (list); item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
1.5.2LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)
The macro defines and LOS_DL_LIST_FOR_EACH_ENTRY The only difference is that there are more than one participants next, This parameter represents the pointer variable of the address of the next structure traversed to . This macro is used to safely delete , If you delete the traversal item, Does not affect continue traversal .
Source code is as follows ：
#define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), next = LOS_DL_LIST_ENTRY((item)->member->pstNext, type, member); &(item)->member != (list); item = next, next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
1.5.3LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook)
The macro defines and LOS_DL_LIST_FOR_EACH_ENTRY The difference is that there are more than one input parameter hook A hook function . In every traversal loop , Call the hook function to do some customized work .
Source code is as follows ：
#define LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook) for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), hook; &(item)->member != (list); item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member), hook)
2、Priority Queue Priority queue
In the task scheduling module , Ready queue is an important data structure , Ready queues need to support initialization , In and out queue , Get the highest priority task from the queue .LiteOS The scheduling module supports a single ready queue （Single Ready Queue） And multiple ready queues （Multiple Ready Queue）, Let's talk about the single ready queue .
Priority queue Priority Queue The interface is mainly used internally , User business development does not involve , No external interface . The priority queue is actually a two-way circular list array , Provide a more convenient interface to support task scheduling based on priority .
The core code of the priority queue is in kernelbaseincludelos_priqueue_pri.h Header files and kernelbaseschedsched_sqlos_priqueue.c In the implementation file .
Let's look at the operations supported by priority queues .
2.1 Priority Queue Priority queue variable definition
LiteOS Support 32 Priority , Value range 0-31, The smaller the priority value, the higher the priority . Priority queue in kernelbaseschedsched_sqlos_priqueue.c Several variables defined in the file are as follows ,
among ⑴ Indicates that the priority is 0 Bit ,⑵ An array of two-way linked lists representing priority queues , The length of the array is 32,⑶ Represents the priority bitmap , Indicates which priority ready queues have mounted tasks .
The schematic diagram is as follows ：
Priority bitmap g_priQueueBitmap Of bit The relationship between bit and priority is bits=31-priority,g_priQueueList[priority] The content of priority array is bidirectional linked list , Mount the ready tasks of each priority .
Source code is as follows ：
#define OS_PRIORITY_QUEUE_NUM 32 ⑴ #define PRIQUEUE_PRIOR0_BIT 0x80000000U ⑵ LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL; ⑶ STATIC LITE_OS_SEC_BSS UINT32 g_priQueueBitmap;
Now let's learn about the operations supported by the priority queue .
2.2 Priority Queue Priority queue interface
2.2.1 OsPriQueueInit(VOID) initialization
Priority queue initialization is called during system initialization ：main.c:main(void)k-->kernelinitlos_init.c:OsMain(VOID)-->kernelbaselos_task.c:OsTaskInit(VOID)-->OsPriQueueInit().
As you can see from the following code ,⑴ The length of the application is 32 Two way linked list value application resident memory , During run time... Is not called Free() Interface release .⑴ Each bidirectional linked list element with array code at is initialized as bidirectional circular linked list .
Source code is as follows ：
UINT32 OsPriQueueInit(VOID) { UINT32 priority; /* System resident memory , Not during operation Free Release */ ⑴ g_priQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, (OS_PRIORITY_QUEUE_NUM * sizeof(LOS_DL_LIST))); if (g_priQueueList == NULL) { return LOS_NOK; } for (priority = 0; priority < OS_PRIORITY_QUEUE_NUM; ++priority) { ⑵ LOS_ListInit(&g_priQueueList[priority]); } return LOS_OK; }
2.2.2 OsPriQueueEnqueueHead() Insert the ready queue header
OsPriQueueEnqueueHead() Insert from the head of the ready queue , Late insertion , But in tasks of equal priority , We will be the first to dispatch . Let's take a look at the code ,⑴ First determine the specified priority priority Whether the ready queue for is empty , If it is empty , It's in ⑵ Update the priority bitmap at .⑶ Insert the task in ready state into the head of ready queue , In order to schedule first .
Source code is as follows ：
VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priqueueItem, UINT32 priority) { LOS_ASSERT(priqueueItem->pstNext == NULL); ⑴ if (LOS_ListEmpty(&g_priQueueList[priority])) { ⑵ g_priQueueBitmap |= PRIQUEUE_PRIOR0_BIT >> priority; } ⑶ LOS_ListHeadInsert(&g_priQueueList[priority], priqueueItem); }
2.2.3 OsPriQueueEnqueue() Insert the end of the ready queue
and OsPriQueueEnqueueHead() Is the difference between the , Insert the ready task into the end of the ready queue , In tasks of equal priority , Post insertion post scheduling .
2.2.4 OsPriQueueDequeue() Remove from ready queue
After the task is deleted 、 Get into suspend state , Priority adjustment, etc , You need to call the interface OsPriQueueEnqueue() Remove the task from the priority queue .
Let's look at the code ,⑴ Remove the task from the priority ready queue .⑵ Get deleted tasks TCB Information , To get the priority of the task . Just deleted a task from the priority queue ,⑶ Code to determine whether the priority queue is empty ,
If it is empty , You need to execute ⑷ Code , Put the corresponding priority in the priority bitmap bit The position is 0.
Source code is as follows ：
VOID OsPriQueueDequeue(LOS_DL_LIST *priqueueItem) { LosTaskCB *runTask = NULL; ⑴ LOS_ListDelete(priqueueItem); ⑵ runTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList); ⑶ if (LOS_ListEmpty(&g_priQueueList[runTask->priority])) { ⑷ g_priQueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runTask->priority); } }
2.2.5 LOS_DL_LIST *OsPriQueueTop(VOID) Get the highest priority list node ready
This interface can get the highest priority list node in the priority ready queue .⑴ Determine the priority bitmap at g_priQueueBitmap Is it 0, If 0, A task that does not have any ready state , return NULL. ⑵ Calculation g_priQueueBitmap It starts with binary 0 Number of , This number corresponds to
Task priority priority, then ⑶ From &g_priQueueList[priority] Get the first linked list node in the priority queue linked list .
Source code is as follows ：
LOS_DL_LIST *OsPriQueueTop(VOID) { UINT32 priority; ⑴ if (g_priQueueBitmap != 0) { ⑵ priority = CLZ(g_priQueueBitmap); ⑶ return LOS_DL_LIST_FIRST(&g_priQueueList[priority]); } return NULL; }
2.2.6 UINT32 OsPriQueueSize(UINT32 priority) Gets the number of ready tasks with the specified priority
This interface can get the number of tasks in the ready queue with the specified priority .⑴、⑶ Code representation , stay SMP In multi-core mode , Based on the current CPU Numbered cpuId, Determine whether the task belongs to the current CPU nucleus , If it doesn't belong to , No count .⑵ Code usage for Loop through the list nodes in the ready queue with the specified priority , For traversing to the new node, execute ⑷ Code , Add to the count 1 operation .
Source code is as follows ：
UINT32 OsPriQueueSize(UINT32 priority) { UINT32 itemCnt = 0; LOS_DL_LIST *curNode = NULL; #ifdef LOSCFG_KERNEL_SMP LosTaskCB *task = NULL; ⑴ UINT32 cpuId = ArchCurrCpuid(); #endif LOS_ASSERT(ArchIntLocked()); LOS_ASSERT(LOS_SpinHeld(&g_taskSpin)); ⑵ LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) { #ifdef LOSCFG_KERNEL_SMP task = OS_TCB_FROM_PENDLIST(curNode); ⑶ if (!(task->cpuAffiMask & (1U << cpuId))) { continue; } #endif ⑷ ++itemCnt; } return itemCnt; }
2.2.7 LosTaskCB *OsGetTopTask(VOID) Get the highest priority task ready
This interface or the highest priority task in the ready task queue . Let's take a look at the code ,⑴、⑷ Alignment SMP Multi core for special processing , If it's multi-core , Only the specified CPU The highest priority task of nuclear operation .⑵ Get g_priQueueBitmap The value of the priority bitmap , Assign a value to UINT32 bitmap;. What's the reason for not directly manipulating priority bitmaps ？ stay SMP Multicore time , In the high priority task ready queue, the specified in the current CPU Tasks of nuclear operation , You need to perform ⑹ Code at , Clear temporary priority bitmap bit position , Go to the lower priority ready queue to find . Only temporary priority bitmaps can be changed , Can't change g_priQueueBitmap.⑶ Place code to traverse the highest priority ready queue , If you traverse to, execute ⑸ Code out of the priority ready queue , Function returns the corresponding LosTaskCB *newTask.
Source code is as follows ：
{ UINT32 priority; UINT32 bitmap; LosTaskCB *newTask = NULL; #ifdef LOSCFG_KERNEL_SMP ⑴ UINT32 cpuid = ArchCurrCpuid(); #endif ⑵ bitmap = g_priQueueBitmap; while (bitmap) { priority = CLZ(bitmap); ⑶ LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) { #ifdef LOSCFG_KERNEL_SMP ⑷ if (newTask->cpuAffiMask & (1U << cpuid)) { #endif ⑸ OsPriQueueDequeue(&newTask->pendList); goto OUT; #ifdef LOSCFG_KERNEL_SMP } #endif } ⑹ bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1)); } OUT: return newTask; }
3、SortLinkList Sort list
SortLinkList yes LiteOS Another important data structure , It's in LOS_DL_LIST On the basis of bidirectional linked list structure , Added RollNum Scrolling number , Used in relation to the expiration of time 、 Business scenario of timeout . Whether the blocking task is due or not , Whether the timer times out , Very dependent on SortLinkList The data structure of the sorted list .LiteOS Sorted lists support a single list LOSCFG_BASE_CORE_USE_SINGLE_LIST And multi linked list LOSCFG_BASE_CORE_USE_MULTI_LIST, Can pass LiteOS Of menuconfig Tool change Sortlink Option Option to configure whether to use single linked list or multi linked list , Let's talk about the former first .
Sort list SortLinkList The interface is mainly used internally , User business development does not involve , No external interface .SortLinkList The code of the sort list is in kernelbaseincludelos_sortlink_pri.h Header files and kernelbaselos_sortlink.c In the implementation file .
3.1 SortLinkList Sort list structure definition
stay kernelbaseincludelos_sortlink_pri.h Two structures are defined in the file , As shown in the following source code .
SortLinkAttribute Structure defines the head node of the sorted list LOS_DL_LIST *sortLink, The cursor UINT16 cursor.SortLinkList The structure defines the business node of the sorted list , Except for the member variable responsible for the two-way link LOS_DL_LIST *sortLink, It also includes business information ,UINT32 idxRollNum, namely index Index and rollNum Scrolling number . In the sorted list of single linked list ,idxRollNum How long will it be due .
Let's take an example , Look at the diagram below . In the sorted list , Yes 3 List nodes , Respectively in 25 ticks、35 ticks、50 ticks Time out after expiration , Has been sorted by due date . three-node idxRollNum Respectively equal to 25 ticks、10
ticks、15 ticks. For each node idxRollNum The timeout of this node is not saved , It's from the linked list head Node to the node
Nodal idxRollNum The sum of , Is the timeout of the node . The advantage of this design is , With Tick The passage of time , Just update the timeout of the first node , You can have a good experience .
The schematic diagram is as follows ：
Source code is as follows ：
typedef struct { LOS_DL_LIST sortLinkNode; UINT32 idxRollNum; } SortLinkList; typedef struct { LOS_DL_LIST *sortLink; UINT16 cursor; UINT16 reserved; } SortLinkAttribute;
Now let's learn the operations supported by the sorted list .
3.2 SortLinkList Sort linked list interface
Before we go on, let's take a look at kernelbaseincludelos_sortlink_pri.h Some single linked list configurations in the file LOSCFG_BASE_CORE_USE_SINGLE_LIST Macro definition under , Including the maximum number of scrolls, etc , Add the number of scrolls 、 reduce 、 Reduce 1 Wait for the operation .
Source code is as follows ：
#define OS_TSK_SORTLINK_LOGLEN 0U #define OS_TSK_SORTLINK_LEN 1U #define OS_TSK_MAX_ROLLNUM 0xFFFFFFFEU #define OS_TSK_LOW_BITS_MASK 0xFFFFFFFFU #define SORTLINK_CURSOR_UPDATE(CURSOR) #define SORTLINK_LISTOBJ_GET(LISTOBJ, SORTLINK) (LISTOBJ = SORTLINK->sortLink) #define ROLLNUM_SUB(NUM1, NUM2) NUM1 = (ROLLNUM(NUM1) - ROLLNUM(NUM2)) #define ROLLNUM_ADD(NUM1, NUM2) NUM1 = (ROLLNUM(NUM1) + ROLLNUM(NUM2)) #define ROLLNUM_DEC(NUM) NUM = ((NUM) - 1) #define ROLLNUM(NUM) (NUM) #define SET_SORTLIST_VALUE(sortList, value) (((SortLinkList *)(sortList))->idxRollNum = (value))
3.2.1 UINT32 OsSortLinkInit() Sort list initialization
Software initialization at system startup , Initialization task 、 When initializing timer , It will initialize the sort list of tasks and the sort list of timers respectively .
- kernelbaselos_task.c : UINT32 OsTaskInit(VOID) function
`ret = OsSortLinkInit(&g_percpu[index].taskSortLink);` - kernelbaselos_swtmr.c : UINT32 OsSwtmrInit(VOID) function
`ret = OsSortLinkInit(&g_percpu[cpuid].swtmrSortLink);`
Let's take a look at the source code of the sort list initialization function ,⑴ Code calculation needs to apply for the number of two-way linked list memory size , For the sort list of single linked list ,OS_TSK_SORTLINK_LOGLEN by 0, For a two-way list to apply for memory size can . Then apply for memory , The memory area of initialization application is 0 etc. ,⑵ To assign the bidirectional list node of the application to sortLinkHeader The linked list node of , As the head node of the sorted list , And then call LOS_ListInit() Function is initialized as a two-way circular list .
Source code is as follows ：
LITE_OS_SEC_TEXT_INIT UINT32 OsSortLinkInit(SortLinkAttribute *sortLinkHeader) { UINT32 size; LOS_DL_LIST *listObject = NULL; ⑴ size = sizeof(LOS_DL_LIST) << OS_TSK_SORTLINK_LOGLEN; listObject = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); /* system resident resource */ if (listObject == NULL) { return LOS_NOK; } (VOID)memset_s(listObject, size, 0, size); ⑵ sortLinkHeader->sortLink = listObject; LOS_ListInit(listObject); return LOS_OK; }
3.2.2 VOID OsAdd2SortLink() Sort linked list insertion
Waiting for mutex in task 、 When the semaphore and other resources are blocked , When timer starts , These tasks need to wait for a specified time 、 Timers, etc , Will be added to the corresponding sort list .
Let's take a look at the code , contain 2 Parameters , The first parameter sortLinkHeader Used to specify the head node of the sorted list , The second parameter sortList Is the list node to be inserted , At this time, the number of scrolls of the node is equal to the timeout of the corresponding blocking task or timer .
⑴ This code deals with the scene with a large number of scrolls , If the number of scrolls is greater than OS_TSK_MAX_ROLLNUM, Set the number of scrolls equal to OS_TSK_MAX_ROLLNUM.⑵ Code , If the sort list is empty , Insert the tail of the linked list node into . If the sort list is not empty , execute ⑶ Code , Get the next node on the sorted list SortLinkList *listSorted.⑷、⑸ Code , If the number of scrolls of the node to be inserted is greater than that of the next node in the sorted list , Then subtract the number of scrolls of the next node from the number of scrolls of the node to be inserted , And continue ⑹ Code , Continue to compare with the next node . otherwise , If the number of scrolls of the node to be inserted is less than that of the next node in the sorted list , The number of scrolls of the next node minus the number of scrolls of the node to be inserted , Then jump out of the loop , Carry on ⑺ Code , Complete the insertion of the node to be inserted . Insertion process , It can be understood in combination with the schematic diagram above .
Source code is as follows ：
LITE_OS_SEC_TEXT VOID OsAdd2SortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList) { SortLinkList *listSorted = NULL; LOS_DL_LIST *listObject = NULL; ⑴ if (sortList->idxRollNum > OS_TSK_MAX_ROLLNUM) { SET_SORTLIST_VALUE(sortList, OS_TSK_MAX_ROLLNUM); } listObject = sortLinkHeader->sortLink; ⑵ if (listObject->pstNext == listObject) { LOS_ListTailInsert(listObject, &sortList->sortLinkNode); } else { ⑶ listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); do { ⑷ if (ROLLNUM(listSorted->idxRollNum) <= ROLLNUM(sortList->idxRollNum)) { ROLLNUM_SUB(sortList->idxRollNum, listSorted->idxRollNum); } else { ⑸ ROLLNUM_SUB(listSorted->idxRollNum, sortList->idxRollNum); break; } ⑹ listSorted = LOS_DL_LIST_ENTRY(listSorted->sortLinkNode.pstNext, SortLinkList, sortLinkNode); } while (&listSorted->sortLinkNode != listObject); ⑺ LOS_ListTailInsert(&listSorted->sortLinkNode, &sortList->sortLinkNode); } }
3.2.3 VOID OsDeleteSortLink() Sort linked list deletion
When task resume 、 Delete , When the timer stops , Will be removed from the corresponding sorted list .
Let's read the source code of the delete function , contain 2 Parameters , The first parameter sortLinkHeader Used to specify the head node of the sorted list , The second parameter sortList Is the list node to be deleted .
⑴ Is the first node to get the sorted list listObject,⑵ Check whether the node to be deleted is in the sorted list , Otherwise, output error information and backtracking stack information .⑶ Code to determine whether there is only one business node in the sorted list , If you only have one node , Direct execution ⑸ Delete the node in the code . If there are multiple business nodes in the sorted list , execute ⑷ Get the next node of the node to be deleted nextSortList, Add the number of scrolls of the deleted node to the number of scrolls of the next node , And then execute ⑸ Delete operation in code .
Source code is as follows ：
LITE_OS_SEC_TEXT VOID OsDeleteSortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList) { LOS_DL_LIST *listObject = NULL; SortLinkList *nextSortList = NULL; ⑴ listObject = sortLinkHeader->sortLink; ⑵ OsCheckSortLink(listObject, &sortList->sortLinkNode); ⑶ if (listObject != sortList->sortLinkNode.pstNext) { ⑷ nextSortList = LOS_DL_LIST_ENTRY(sortList->sortLinkNode.pstNext, SortLinkList, sortLinkNode); ROLLNUM_ADD(nextSortList->idxRollNum, sortList->idxRollNum); } ⑸ LOS_ListDelete(&sortList->sortLinkNode); }
3.2.4 UINT32 OsSortLinkGetNextExpireTime() Get the next timeout expiration time
stay Tickless characteristic , This method is used to get the next timeout expiration time .
Let's read the source code together , contain 1 Parameters ,sortLinkHeader Used to specify the head node of the sorted list .
⑴ Is the first node to get the sorted list listObject,⑵ Code to determine whether the sort list is empty , If the sort list is empty , Then return to OS_INVALID_VALUE. If the list is not empty ,⑶ Get the first business node of the sorted list , Then get the number of scrolls , Namely the expiration time , Go back .
Source code is as follows ：
LITE_OS_SEC_TEXT UINT32 OsSortLinkGetNextExpireTime(const SortLinkAttribute *sortLinkHeader) { UINT32 expireTime = OS_INVALID_VALUE; LOS_DL_LIST *listObject = NULL; SortLinkList *listSorted = NULL; ⑴ listObject = sortLinkHeader->sortLink; ⑵ if (!LOS_ListEmpty(listObject)) { ⑶ listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); expireTime = listSorted->idxRollNum; } return expireTime; }
3.2.5 OsSortLinkGetTargetExpireTime() Gets the timeout of the specified node
Timer gets the remaining timeout function LOS_SwtmrTimeGet() Will call functions OsSortLinkGetTargetExpireTime() Gets the timeout of the specified node .
Let's take a look at the code , contain 2 Parameters , The first parameter sortLinkHeader Used to specify the head node of the sorted list , The second parameter targetSortList Is the target list node to get the timeout .
⑴ Get the scrolling number of the target node .⑵ Get the head node of the sorted list listObject,⑶ Get the next node on the sorted list SortLinkList *listSorted.⑷ Loop code at , When the next node is not the target list node , In turn, cycle , And implement ⑸ Add the number of scrolls of each node traversed by the loop , The final result is the timeout of the target node .
Source code is as follows ：
LITE_OS_SEC_TEXT_MINOR UINT32 OsSortLinkGetTargetExpireTime(const SortLinkAttribute *sortLinkHeader, const SortLinkList *targetSortList) { SortLinkList *listSorted = NULL; LOS_DL_LIST *listObject = NULL; ⑴ UINT32 rollNum = targetSortList->idxRollNum; ⑵ listObject = sortLinkHeader->sortLink; ⑶ listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); ⑷ while (listSorted != targetSortList) { ⑸ rollNum += listSorted->idxRollNum; listSorted = LOS_DL_LIST_ENTRY((listSorted->sortLinkNode).pstNext, SortLinkList, sortLinkNode); } return rollNum; }
3.2.6 VOID OsSortLinkUpdateExpireTime() Update timeout
stay Tickless characteristic , This method is used to update the timeout .Tickless Sleep sleep when , Need to put dormant ticks The number is subtracted from the sorted list . The function that calls this method will guarantee subtraction ticks The number of scrolls is less than the number of scrolls of the node .
Let's read the source code together , contain 2 Parameters , The first parameter sleepTicks It's dormant ticks Count , The second parameter sortLinkHeader Used to specify the head node of the sorted list .
⑴ Get the head node of the sorted list at listObject,⑵ Get the next linked list node sortList, This is also the first business node of the sorted list , Then subtract... From the number of scrolls of the node sleepTicks - 1 Finish the timeout update .
Source code is as follows ：
LITE_OS_SEC_TEXT VOID OsSortLinkUpdateExpireTime(UINT32 sleepTicks, SortLinkAttribute *sortLinkHeader) { SortLinkList *sortList = NULL; LOS_DL_LIST *listObject = NULL; if (sleepTicks == 0) { return; } ⑴ listObject = sortLinkHeader->sortLink; ⑵ sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); ROLLNUM_SUB(sortList->idxRollNum, sleepTicks - 1); }
3.3 SortLinkList Sort linked list and Tick Time relation
Mission 、 After the timer is added to the sorted list , As time goes by , One tick One tick The passing of the past , How to update the number of scrolls in the sorted list ？
Let's see. Tick Interrupt handling functions VOID OsTickHandler(VOID), The function is in kernelbaselos_tick.c In the document .
When time goes by tick, The interrupt handler is called , In code snippet ⑴、⑵ The code at scan task and timer respectively , Check and update time .
LITE_OS_SEC_TEXT VOID OsTickHandler(VOID) { UINT32 intSave; TICK_LOCK(intSave); g_tickCount[ArchCurrCpuid()]++; TICK_UNLOCK(intSave); ...... ⑴ OsTaskScan(); /* task timeout scan */ #if (LOSCFG_BASE_CORE_SWTMR == YES) ⑵ OsSwtmrScan(); #endif }
We use OsTaskScan() For example , Quick understanding of the next sort of linked list and tick It's a matter of time . Function in kernelbaselos_task.c In file , The code fragment of the function is as follows ：
⑴ Get the first node of the task sort list , Then execute the next line of code to subtract the number of scrolls for that node 1.⑵ Loop through the sorted list , If the number of scrolls is 0, That is, the time has expired , Would call LOS_ListDelete() Function to remove from the sorted list , And then execute ⑶ Code , Get the corresponding taskCB, And then further business processing . Readers can see more code for themselves , The task will also be discussed in subsequent articles 、 I'll give you a special topic .
LITE_OS_SEC_TEXT VOID OsTaskScan(VOID) { SortLinkList *sortList = NULL; ...... LOS_DL_LIST *listObject = NULL; SortLinkAttribute *taskSortLink = NULL; taskSortLink = &OsPercpuGet()->taskSortLink; SORTLINK_CURSOR_UPDATE(taskSortLink->cursor); SORTLINK_LISTOBJ_GET(listObject, taskSortLink); ...... ⑴ sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); ROLLNUM_DEC(sortList->idxRollNum); ⑵ while (ROLLNUM(sortList->idxRollNum) == 0) { LOS_ListDelete(&sortList->sortLinkNode); ⑶ taskCB = LOS_DL_LIST_ENTRY(sortList, LosTaskCB, sortList); ...... sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); } ...... }
Summary
master LiteOS The bidirectional circular list of the kernel LOS_DL_LIST, Priority queue Priority Queue, Sort list SortLinkList And other important data structures , For further study 、 analysis LiteOS The source code lays the foundation , Make the follow-up study easier . More sharing articles will be launched in the future , Coming soon , Also welcome to share learning and use LiteOS What I learned , Any questions 、 Suggest , You can leave us a message ： https://gitee.com/LiteOS/Lite... . To make it easier to find LiteOS Code store , Suggest visiting https://gitee.com/LiteOS/LiteOS , Focus on Watch、 give the thumbs-up Star、 and Fork Go to your own account , Here's the picture , thank you .
This article is shared from Huawei cloud community 《LiteOS A series of kernel source code analysis Take stock of the important data structures 》, Original author ：zhushy .
Click to follow , The first time to learn about Huawei's new cloud technology ~