FreeRTOS Source Code Analysis – Implementation of Linked Lists

In the previous chapter, Embedded Operating System: FreeRTOS Source Code Analysis Part Three – Task Startup and Switching, we officially started tasks. In FreeRTOS, tasks can also be referred to as threads. Next, we will introduce inter-thread synchronization mechanisms (semaphores, mutexes, event groups, etc.) and inter-thread communication mechanisms (message queues, StreamBuffer, etc.). The implementation of all these relies on two important data structures: the doubly linked list and the queue. In this section, we will look at the implementation of linked lists in FreeRTOS.

Definition of List Structure

The following code defines the core data structure used in FreeRTOS to implement a doubly linked list, primarily used to manage task lists, event queues, timers, etc. These structures form the efficient, safe, and traversable doubly linked list mechanism within FreeRTOS, which is the foundation for core functionalities such as task scheduling, delay management, and event waiting.

1. xLIST_ITEM (List Item)

Each list item represents a node in the linked list for a task or other objects:

struct xLIST_ITEM {
    TickType_t xItemValue;              // Used for sorting (usually delay time or priority)
    struct xLIST_ITEM *pxNext;          // Next node
    struct xLIST_ITEM *pxPrevious;      // Previous node
    void *pvOwner;                      // Points to the object that owns this node (usually the Task Control Block TCB)
    struct xLIST *pxContainer;          // Points to the list to which this node belongs
};

2. xMINI_LIST_ITEM (Mini List Item)

Used to mark the end of the list, does not includepvOwner and pxContainer, saving memory:

struct xMINI_LIST_ITEM {
    TickType_t xItemValue;
    struct xLIST_ITEM *pxNext;
    struct xLIST_ITEM *pxPrevious;
};

3. xLIST (The List Itself)

Represents a complete linked list:

typedef struct xLIST {
    UBaseType_t uxNumberOfItems;    // Number of nodes in the list
    ListItem_t *pxIndex;            // Current traversal pointer (for iteration)
    MiniListItem_t xListEnd;        // End marker of the list (xItemValue is the maximum value)
} List_t;

List Initialization – vListInitialise

Clears a linked list, turning it into an “empty list” and setting up an ‘end marker’, so that future insertions/deletions can be done directly without boundary checks.

void vListInitialise( List_t * const pxList )
{
    /* 1. Set the "traversal pointer" to point to the end marker of the list */
    pxList->pxIndex = ( ListItem_t *) &(pxList->xListEnd);

    /* 2. Give the end marker a "maximum value" to ensure it always stays at the end */
    pxList->xListEnd.xItemValue = portMAX_DELAY;

    /* 3. Set the "previous" and "next" pointers of the end marker to point to itself -
          This way, any node inserted before it logically closes the list,
          and checking for an empty list is simple: if a node's next/prev points to itself, it is the end. */
    pxList->xListEnd.pxNext     = (ListItem_t *) &(pxList->xListEnd);
    pxList->xListEnd.pxPrevious = (ListItem_t *) &(pxList->xListEnd);

    /* 4. Set the node count to zero */
    pxList->uxNumberOfItems = 0U;

    /* 5. If integrity checking is enabled, write a "magic number" for out-of-bounds detection */
    listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList);
    listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList);
}

The state after initialization is: only the xListEnd points to itself,pxIndex also points to it, and the count is 0, indicating an “empty list”. In the future, whether it is vListInsert or uxListRemove, there is no need to specifically check for an empty list or the end, as the “closure” already ensures algorithm uniformity.

Node Initialization – vListInitialiseItem

Initializes a single list item – informs the kernel that “it currently does not belong to any list”, preventing wild pointers and erroneous operations.

void vListInitialiseItem( ListItem_t * const pxItem )
{
    /* 1. The most critical step: clear the ownership pointer to NULL
          Future insertion functions will check this field, only NULL is allowed for insertion,
          to avoid a node being attached to two lists simultaneously. */
    pxItem->pxContainer = NULL;

    /* 2. If integrity checking is enabled, write a "magic number"
          If the magic number is found to be corrupted later, it indicates memory corruption. */
    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
    listSET_SECOND_LIST_ITEM_INTEGRITY_VALUE( pxItem );
}

Invocation Scenarios

• When creating a Task Control Block TCB, the internal xStateListItem, xEventListItem are initialized once;
• Any custom list node should also call this function before use to ensure it is “clean” before being added to the list.

Insertion at the End – vListInsertEnd

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    /* 1. Get the "traversal pointer", we will insert before it */
    ListItem_t * const pxIndex = pxList->pxIndex;

    /* 2. Integrity check (only effective when configASSERT is enabled)*/
    listTEST_LIST_INTEGRITY( pxList );
    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

    /* 3. Set the new node's previous and next pointers */
    pxNewListItem->pxNext     = pxIndex;               // New node's next points to pxIndex
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;   // New node's prev points to pxIndex's original predecessor

    /* 4. Update the pointers of the original predecessor and pxIndex to form a complete four-ring */
    pxIndex->pxPrevious->pxNext = pxNewListItem;       // Original predecessor's next points to new node
    pxIndex->pxPrevious         = pxNewListItem;       // pxIndex's prev also points to new node

    /* 5. Record the "ownership", increment node count by 1 */
    pxNewListItem->pxContainer = pxList;
    ( pxList->uxNumberOfItems )++;
}

vListInsertEnd‘s core function: directly inserts the new node to the left of the “current traversal pointerpxIndex, which is the logical end. This way, the next time listGET_OWNER_OF_NEXT_ENTRY() is called, it will be retrieved last, effectively implementing a circular queue/round-robin scheduling.

• Task Ready List: Newly ready tasks are directly inserted to the left of the “currently running task on the CPU”, ensuring that it will be scheduled next, achieving time-slice rotation.
• Delay List: If a task is awakened due to timeout, it can also be directly placed at the end without disrupting the original order based on wake-up time (because vListInsertEnd does not rely on xItemValue for sorting).

Sequential Insertion – vListInsert

Inserts the new node into the linked list in ascending order based on xItemValue; the smaller the value, the closer it is to the front; if the values are the same, it is inserted after existing nodes with the same value, ensuring that tasks of the same priority rotate in order. Assuming there is an existing linked list (in ascending order based on xItemValue):

[3] -> [5] -> [5] -> [7] -> ... -> END(portMAX_DELAY)

To insert a new node with xItemValue = 5, after insertion:

[3] -> [5] -> [5] -> [new5] -> [7] -> ... -> END

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    ListItem_t *pxIterator;
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;   // Value to be inserted

    /* Integrity check (only effective when configASSERT is enabled)*/
    listTEST_LIST_INTEGRITY( pxList );
    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

    /* Special case: if the value to be inserted is portMAX_DELAY (i.e., the value of END),
       directly insert before the "end marker" to avoid infinite loops */
    if( xValueOfInsertion == portMAX_DELAY )
    {
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        /* Start from the head and look for the first node that is greater than the insertion value;
           When the loop ends, pxIterator points to the last node that is less than or equal to the insertion value */
        for( pxIterator = (ListItem_t *)&(pxList->xListEnd);
             pxIterator->pxNext->xItemValue <= xValueOfInsertion;
             pxIterator = pxIterator->pxNext )
        {
            /* Empty loop, just moving the pointer */
        }
    }

    /* Standard four-ring insertion: insert the new node between pxIterator and pxIterator->pxNext */
    pxNewListItem->pxNext               = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious   = pxNewListItem;
    pxNewListItem->pxPrevious           = pxIterator;
    pxIterator->pxNext                  = pxNewListItem;

    /* Record ownership, increment node count by 1 */
    pxNewListItem->pxContainer = pxList;
    ( pxList->uxNumberOfItems )++;
}

Typical Usage Scenarios

1. Ready List Task priority = xItemValue, tasks of the same priority are inserted in order, and the scheduler rotates them in sequence.
2. Delay List Wake-up time = xItemValue, the system tick interrupt continuously scans the head, and when the time is up, it removes and returns to the ready list.
3. Event Waiting List Waiting timeout as xItemValue, automatically removed after timeout.

Comparison of vListInsert and vListInsertEnd

Function	Is Sorted	Insertion Position Based On	Time Complexity
vListInsert	Ascending	By xItemValue from small to large	O(n)｜
vListInsertEnd	Unordered	Fixed to the left of pxIndex	O(1)

Therefore, vListInsertEnd<code> is a fast tail insertion, commonly used for appending to the scheduler's ready list and queue tail, with very high efficiency.

Removing Nodes – uxListRemove

uxListRemove‘s core function: removes the specified node from its doubly linked list and returns the remaining number of nodes in the list. The entire process only manipulates pointers and does not free memory, so the time complexity is O(1).

Before deletion:

... <-> [A] <-> [B] <-> [C] <-> ...
           ↑
       pxItemToRemove

After deletion:

... <-> [A] <-> [C] <-> ...

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
    /* 1. Get the "owning list" pointer, which will be updated for count and traversal pointer later */
    List_t * const pxList = pxItemToRemove->pxContainer;

    /* 2. Standard doubly linked list deletion: skip the node to be deleted */
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /* 3. If the current traversal pointer is pointing to the node to be deleted, move it back one position,
          ensuring that the next call to listGET_OWNER_OF_NEXT_ENTRY() does not return a wild pointer */
    if( pxList->pxIndex == pxItemToRemove )
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }

    /* 4. Clear the node's "ownership": it no longer belongs to any list */
    pxItemToRemove->pxContainer = NULL;

    /* 5. Decrement the node count by 1 and return the remaining count */
    ( pxList->uxNumberOfItems )--;
    return pxList->uxNumberOfItems;
}

Meaning of Return Value

• 0: The list is empty, which can trigger subsequent cleanup or assertions.
• Non-zero: There are still nodes in the list, continue scheduling/traversing.

Usage Scenarios

1. Task removal from the ready list The function is called when a task is blocked, suspended, or deleted.
2. Removal from the delay list upon expiration In the timer interrupt, the xStateListItem is removed from the delay list and then inserted back into the ready list.
3. Event waiting list When a task is blocked due to failure to acquire a queue/semaphore, its xEventListItem will be attached to the waiting list for the corresponding resource; when the resource becomes available, the task node is removed and awakened using uxListRemove.

We have analyzed the function implementations in list.c in FreeRTOS. There are also some macro definitions in list.h for checking the state of the list, which are not shown here. Interested readers can check the source code themselves. The amount of code for the linked list implementation is not large, but it is used very frequently. Our task ready lists, blocked lists, etc., are all implemented based on this. Therefore, understanding linked lists is a crucial knowledge point. In the next article, we will analyze the implementation of queues. Compared to linked lists, the amount of code for queues is significantly larger, as mentioned earlier, structures like semaphores, mutexes, and message queues are all based on queue structures. My level is limited, and if there are any errors or omissions in the above content, please feel free to communicate and correct me. I hope the above content is useful to you.