3.5. Lists
After tasks, the most used FreeRTOS data structure is the list. FreeRTOS uses its list structure to keep track of tasks for scheduling, and also to implement queues.
Illegal HTML tag removed : _ FreeRTOS_files/freertos-figures-full-ready-list.png)
The FreeRTOS list is a standard circular doubly linked list with a couple of interesting additions. Here's a list element:
struct xLIST_ITEM { portTickType xItemValue; /* The value being listed. In most cases this is used to sort the list in descending order. */ volatile struct xLIST_ITEM * pxNext; /* Pointer to the next xListItem in the list. */ volatile struct xLIST_ITEM * pxPrevious; /* Pointer to the previous xListItem in the list. */ void * pvOwner; /* Pointer to the object (normally a TCB) that contains the list item. There is therefore a two-way link between the object containing the list item and the list item itself. */ void * pvContainer; /* Pointer to the list in which this list item is placed (if any). */ };
Each list element holds a number, xItemValue
, that is the usually the priority of the task being tracked or a timer value for event scheduling. Lists are kept in high-to-low priority order, meaning that the highest-priority xItemValue
(the largest number) is at the front of the list and the lowest priority xItemValue
(the smallest number) is at the end of the list.
The pxNext
and pxPrevious
pointers are standard linked list pointers. pvOwner
is a pointer to the owner of the list element. This is usually a pointer to a task's TCB object. pvOwner
is used to make task switching fast in vTaskSwitchContext()
: once the highest-priority task's list element is found in pxReadyTasksLists[]
, that list element's pvOwner
pointer leads us directly to the TCB needed to schedule the task.
pvContainer
points to the list that this item is in. It is used to quickly determine if a list item is in a particular list. Each list element can be put in a list, which is defined as:
typedef struct xLIST { volatile unsigned portBASE_TYPE uxNumberOfItems; volatile xListItem * pxIndex; /* Used to walk through the list. Points to the last item returned by a call to pvListGetOwnerOfNextEntry (). */ volatile xMiniListItem xListEnd; /* List item that contains the maximum possible item value, meaning it is always at the end of the list and is therefore used as a marker. */ } xList;
The size of a list at any time is stored in uxNumberOfItems
, for fast list-size operations. All new lists are initialized to contain a single element: the xListEnd
element. xListEnd.xItemValue
is a sentinel value which is equal to the largest value for the xItemValue
variable: 0xffff
when portTickType
is a 16-bit value and 0xffffffff
when portTickType
is a 32-bit value. Other list elements may also have the same value; the insertion algorithm ensures that xListEnd
is always the last item in the list.
Since lists are sorted high-to-low, the xListEnd
element is used as a marker for the start of the list. And since the list is circular, this xListEnd
element is also a marker for the end of the list.
Most "traditional" list accesses you've used probably do all of their work within a single for() loop or function call like this:
for (listPtr = listStart; listPtr != NULL; listPtr = listPtr->next) { // Do something with listPtr here... }
FreeRTOS frequently needs to access a list across multiple for() and while() loops as well as function calls, and so it uses list functions that manipulate the pxIndex
pointer to walk the list. The list function listGET_OWNER_OF_NEXT_ENTRY()
does pxIndex = pxIndex->pxNext;
and returns pxIndex
. (Of course it does the proper end-of-list-wraparound detection too.) This way the list itself is responsible for keeping track of "where you are" while walking it using pxIndex
, allowing the rest of FreeRTOS to not worry about it.
Illegal HTML tag removed : _ FreeRTOS_files/freertos-figures-full-ready-list-2.png)
The pxReadyTasksLists[]
list manipulation done in vTaskSwitchContext()
is a good example of how pxIndex
is used. Let's assume we have only one priority level, priority 0, and there are three tasks at that priority level. This is similar to the basic ready list picture we looked at earlier, but this time we'll include all of the data structures and fields.
As you can see in Figure 3.3, pxCurrentTCB
indicates that we're currently running Task B. The next time vTaskSwitchContext()
runs, it calls listGET_OWNER_OF_NEXT_ENTRY()
to get the next task to run. This function uses pxIndex->pxNext
to figure out the next task is Task C, and now pxIndex
points to Task C's list element and pxCurrentTCB
points to Task C's TCB, as shown in Figure 3.4.
Note that each struct xListItem
object is actually the xGenericListItem
object from the associated TCB.