Mastering FreeRTOS from Scratch (2): Definition of List Node

In the previous article, we completed the porting of FreeRTOS. In FreeRTOS, all functionalities are divided into tasks, which need to be mounted on a linked list. In this chapter, we will master the various types of nodes in a linked list.

Before creating tasks, we need to understand the operating mechanism of FreeRTOS. FreeRTOS is a multitasking system managed by the operating system to execute each task. All these tasks are mounted on a doubly circular linked list, and each node in the list can mount multiple tasks.

Node

Node Definition

In FreeRTOS, the definition of the linked list is implemented in list.h. The following code shows the structure definition of a linked list node.

PS: In list.h, my macro configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 0. When it is 0, the macros listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE and listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE do not represent actual values. For readability, I have removed these macros in subsequent occurrences.

struct xLIST_ITEM{ configLIST_VOLATILE TickType_t xItemValue; struct xLIST_ITEM * configLIST_VOLATILE pxNext; struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; void * pvOwner; void * configLIST_VOLATILE pvContainer; }; typedef struct xLIST_ITEM ListItem_t;

configLIST_VOLATILE TickType_t xItemValue: Here, configLIST_VOLATILE is the VOLATILE type in C language. In FreeRTOS, all data types are redefined using typedef. Similarly, TickType_t is defined as uint32_t, and all data types are defined in portmacro.h. Returning to xItemValue, this parameter serves as the node’s sequence number.

struct xLIST_ITEM * configLIST_VOLATILE pxNext: Points to the next node.

struct xLIST_ITEM * configLIST_VOLATILE pxPrevious: Points to the previous node.

void * pvOwner: Points to the data structure of this node. It is a pointer to the object that contains the list item (usually a TCB). Therefore, there is a bidirectional link between the object containing the list item and the list item itself.

In FreeRTOS, TCB (Task Control Block) is an abbreviation for the task control block. It is a data structure used to store and manage all relevant information about a task. Each task has a corresponding TCB, and FreeRTOS manages and schedules tasks through the TCB. This will be explained in other articles.

void * configLIST_VOLATILE pvContainer: Points to the linked list that this node belongs to, usually pointing to the root node of the list.

typedef struct xLIST_ITEM ListItem_t: Redefines the data type of this structure.

Node Implementation

In list.c, nodes are created by defining functions. Below is the node initialization function.

void vListInitialiseItem( ListItem_t * const pxItem ){ pxItem->pvContainer = NULL; }

Since this node has only been initialized and not inserted into the linked list, the initialized list is empty. The actual situation is shown in the following figure.

Root Node

Root Node Definition

As mentioned above, pvContainer usually points to the root node of the linked list. Below is the structure definition of the root node.

typedef struct xLIST{ volatile UBaseType_t uxNumberOfItems; ListItem_t * configLIST_VOLATILE pxIndex; MiniListItem_t xListEnd;} List_t;

uxNumberOfItems: Node counter. It indicates the number of nodes in the linked list excluding the root node.

pxIndex: Pointer to the linked list node index, used for traversing nodes.

xListEnd: The last node of the linked list. Since FreeRTOS is a doubly circular linked list, the last node is also the first node.

Simplified Node Definition

A simplified node is the data type of xListEnd in the root node, which I believe is a supplement to the node type of the root node.

struct xMINI_LIST_ITEM{ configLIST_VOLATILE TickType_t xItemValue; struct xLIST_ITEM * configLIST_VOLATILE pxNext; struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; }; typedef struct xMINI_LIST_ITEM MiniListItem_t;

From the definition, a simplified node consists of pointers to the previous and next nodes and a sequence number, with the structure members being the most basic elements that constitute a node.

Root Node Implementation

void vListInitialise( List_t * const pxList ){ pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); pxList->xListEnd.xItemValue = portMAX_DELAY; pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); pxList->uxNumberOfItems = ( UBaseType_t ) 0U; }

This root node initialization function does four things:

1. Points the index pointer to the last node.

2. Sets the sequence value to the maximum (i.e., portMAX_DELAY, which is defined in portmacro.h) to ensure that the root node is the last node of the linked list.

3. Points both the previous and next nodes of this node to itself.

4. Initializes the counter value to 0.

As shown in the figure below, this is a root node. The root node consists of a simplified node that serves as a node, along with an index pointer and a node counter. However, during initialization, both pxNext and pxPrevious point to itself.

After understanding the definitions and initializations of the above nodes, the linked list formed by combining the root node and nodes is shown in the following figure.

In the next article, we will analyze how to add nodes to the linked list.