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.