01. 概述
要想看懂FreeRTOS 源码并学习其原理,有一个东西绝对跑不了,那就是FreeRTOS 的列表和列表项。列表和列表项是FreeRTOS 的一个数据结构,FreeRTOS 大量使用到了列表和列表项,它是FreeRTOS 的基石。要想深入学习并理解FreeRTOS,那么列表和列表项就必须首先掌握,否则后面根本就没法进行。
列表被FreeRTOS调度器使用,用于跟踪任务,处于就绪、挂起、延时的任务,都会被挂接到各自的列表中。用户程序如果有需要,也可以使用列表。
FreeRTOS列表使用指针指向列表项。一个列表(list)下面可能有很多个列表项(list item),每个列表项都有一个指针指向列表。如下图所示。
02. 列表
列表是FreeRTOS 中的一个数据结构,概念上和链表有点类似,列表被用来跟踪FreeRTOS中的任务。与列表相关的全部东西都在文件list.c 和list.h 中。在list.h 中定义了一个叫List_t 的结构体,如下:
- typedef struct xLIST
- {
- listFIRST_LIST_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
- configLIST_VOLATILE UBaseType_t uxNumberOfItems;
- ListItem_t * configLIST_VOLATILE pxIndex; /*用于遍历列表*/
- MiniListItem_t xListEnd; /*列表项*/
- listSECOND_LIST_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
- }List_t;
复制代码
(1) 和(5) 、这两个都是用来检查列表完整性的, 需要将宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 设置为1,开启以后会向这两个地方分别添加一个变量xListIntegrityValue1 和xListIntegrityValue2,在初始化列表的时候会这两个变量中写入一个特殊的值,默认不开启这个功能。
(2)、uxNumberOfItems 用来记录列表中列表项的数量。
(3)、pxIndex 用来记录当前列表项索引号,用于遍历列表。
(4)、列表中最后一个列表项,用来表示列表结束,此变量类型为MiniListItem_t,这是一个迷你列表项。
03. 列表项
列表项就是存放在列表中的项目,FreeRTOS 提供了两种列表项:列表项和迷你列表项。这两个都在文件list.h 中有定义。
xLIST_ITEM列表项
- struct xLIST_ITEM
- {
- listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
- configLIST_VOLATILETickType_t xItemValue; /*列表项值*/
- struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*指向列表中下一个列表项*/
- struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*指向列表中上一个列表项*/
- void * pvOwner; /*指向一个任务TCB*/
- void * configLIST_VOLATILE pvContainer; /*指向包含该列表项的列表 */
- listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
- };
- typedef struct xLIST_ITEM ListItem_t;
复制代码
(1)和(7)、用法和列表一样,用来检查列表项完整性的。以后我们在学习列表项的时候不讨论这个功能!
(2)、xItemValue 为列表项值。
(3)、pxNext 指向下一个列表项。
(4)、pxPrevious 指向前一个列表项,和pxNext 配合起来实现类似双向链表的功能。
(5)、pvOwner 记录此链表项归谁拥有,通常是任务控制块。
(6)、pvContainer 用来记录此列表项归哪个列表。注意和pvOwner 的区别,在前面讲解任务控制块TCB_t 的时候说了在TCB_t 中有两个变量xStateListItem 和xEventListItem,这两个变量的类型就是ListItem_t,也就是说这两个成员变量都是列表项。以xStateListItem 为例,当创建一个任务以后xStateListItem 的pvOwner 变量就指向这个任务的任务控制块,表示xSateListItem属于此任务。当任务就绪态以后xStateListItem 的变量pvContainer 就指向就绪列表,表明此列表项在就绪列表中。举个通俗一点的例子:小王在上二年级,他的父亲是老王。如果把小王比作列表项,那么小王的pvOwner 属性值就是老王,小王的pvContainer 属性值就是二年级。
xMINI_LIST_ITEM列表项
- struct xMINI_LIST_ITEM
- {
- listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
- configLIST_VOLATILE TickType_t xItemValue;
- struct xLIST_ITEM * configLIST_VOLATILE pxNext;
- struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
- };
- typedef struct xMINI_LIST_ITEM MiniListItem_t;
复制代码
(1)、用于检查迷你列表项的完整性。
(2)、xItemValue 记录列表列表项值。
(3)、pxNext 指向下一个列表项。
(4)、pxPrevious 指向上一个列表项。
可以看出迷你列表项只是比列表项少了几个成员变量,迷你列表项有的成员变量列表项都有的,没感觉有什么本质区别啊?那为什么要弄个迷你列表项出来呢?那是因为有些情况下我们不需要列表项这么全的功能,可能只需要其中的某几个成员变量,如果此时用列表项的话会造成内存浪费!比如上面列表结构体List_t 中表示最后一个列表项的成员变量xListEnd 就是MiniListItem_t 类型的。
04. 列表相关宏
05. 列表相关函数
5.1 初始化列表
列表结构体中包含一个列表项成员,主要用于标记列表结束。初始化列表就是把这个列表项插入到列表中。
- void vListInitialise( List_t * const pxList )
- {
- /*列表索引指向列表项*/
- pxList->pxIndex = ( ListItem_t * )&( pxList->xListEnd );
- /* 设置为最大可能值 */
- pxList->xListEnd.xItemValue =portMAX_DELAY;
- /* 列表项xListEnd的pxNext和pxPrevious指针指向了它自己 */
- pxList->xListEnd.pxNext = (ListItem_t * ) &( pxList->xListEnd );
- pxList->xListEnd.pxPrevious= ( ListItem_t * ) &( pxList->xListEnd );
- pxList->uxNumberOfItems = ( UBaseType_t) 0U;
- /* 设置为已知值,用于检测列表数据是否完整*/
- listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList );
- listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList );
- }
复制代码
如果宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1,则使能列表项数据完整性检查,则宏listSET_LIST_INTEGRITY_CHECK_1_VALUE()和listSET_LIST_INTEGRITY_CHECK_2_VALUE被一个已知值代替,默认为0x5a5a(16位架构)或者0x5a5a5a5a(32位架构)。
5.2 初始化列表项
列表项的初始比较简单,只要确保列表项不在任何列表中即可。
- void vListInitialiseItem( ListItem_t * const pxItem )
- {
- pxItem->pvContainer = NULL;
- /*设置为已知值,用于检测列表项数据是否完整*/
- listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
- listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
- }
复制代码
如果宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1,则使能列表项数据完整性检查,则宏listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE和listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE会被两个已知的数值代替,默认为0x5a5a(16位架构)或者0x5a5a5a5a(32位架构)。
5.3 列表项插入函数
每个列表项对象都有一个列表项值(xItemValue),通常是一个被跟踪的任务优先级或是一个调度事件的计数器值。调用API函数vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem)可以将pxNewListItem指向的列表项插入到pxList指向的列表中,列表项在列表的位置由pxNewListItem->xItemValue决定,按照升序排列。
- void vListInsert( List_t * const pxList,
- ListItem_t * const pxNewListItem )
- {
- ListItem_t * pxIterator;
- const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
- /* 检查列表和列表项数据的完整性,仅当configASSERT()定义时有效。*/
- /* Only effective when configASSERT() is also defined, these tests may catch
- * the list data structures being overwritten in memory. They will not catch
- * data errors caused by incorrect configuration or use of FreeRTOS. */
- listTEST_LIST_INTEGRITY( pxList );
- listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
- /* Insert the new list item into the list, sorted in xItemValue order.
- *
- * If the list already contains a list item with the same item value then the
- * new list item should be placed after it. This ensures that TCBs which are
- * stored in ready lists (all of which have the same xItemValue value) get a
- * share of the CPU. However, if the xItemValue is the same as the back marker
- * the iteration loop below will not end. Therefore the value is checked
- * first, and the algorithm slightly modified if necessary. */
- /*将新的列表项插入到列表,根据xItemValue的值升序插入列表。*/
- if( xValueOfInsertion == portMAX_DELAY )
- {
- pxIterator = pxList->xListEnd.pxPrevious;
- }
- else
- {
- /* *** NOTE ***********************************************************
- * If you find your application is crashing here then likely causes are
- * listed below. In addition see <a href="https://www.FreeRTOS.org/FAQHelp.html" target="_blank">https://www.FreeRTOS.org/FAQHelp.html</a> for
- * more tips, and ensure configASSERT() is defined!
- * <a href="https://www.FreeRTOS.org/a00110.html#configASSERT" target="_blank">https://www.FreeRTOS.org/a00110.html#configASSERT</a>
- *
- * 1) Stack overflow -
- * see <a href="https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html" target="_blank">https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html</a>
- * 2) Incorrect interrupt priority assignment, especially on Cortex-M
- * parts where numerically high priority values denote low actual
- * interrupt priorities, which can seem counter intuitive. See
- * and the definition
- * of configMAX_SYSCALL_INTERRUPT_PRIORITY on
- *
- * 3) Calling an API function from within a critical section or when
- * the scheduler is suspended, or calling an API function that does
- * not end in "FromISR" from an interrupt.
- * 4) Using a queue or semaphore before it has been initialised or
- * before the scheduler has been started (are interrupts firing
- * before vTaskStartScheduler() has been called?).
- **********************************************************************/
- //xListEnd表示列表的末尾
- for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. *//*lint !e440 The iterator moves to a different value, not xValueOfInsertion. */
- {
- /* There is nothing to do here, just iterating to the wanted
- * insertion position. */
- }
- }
- pxNewListItem->pxNext = pxIterator->pxNext;
- pxNewListItem->pxNext->pxPrevious = pxNewListItem;
- pxNewListItem->pxPrevious = pxIterator;
- pxIterator->pxNext = pxNewListItem;
- /* Remember which list the item is in. This allows fast removal of the
- * item later. */
- pxNewListItem->pxContainer = pxList;
- ( pxList->uxNumberOfItems )++;
- }
复制代码
根据xItemValue的值将新的列表项插入到列表。如果列表中存在与新列表项xItemValue值相同的列表项,则新插入的列表项位于它之后。如果列表项的xItemValue值等于portMAX_DELAY(列表结束标记,我们在讲列表数据结构时,说到每个列表数据结构体中都有一个列表项成员xListEnd,用于标记列表结束。xListEnd.xItemValue被初始化为一个常数,其值与硬件架构相关,为0xFFFF或者0xFFFFFFFF。这个常数在移植层定义,即宏portMAX_DELAY),则表示到达了列表结束位置。
5.4 列表项末尾插入
API函数vListInsertEnd()是简单的将列表项插入到列表的末端。
- void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
- {
- ListItem_t* const pxIndex = pxList->pxIndex;
- /*检查列表和列表项数据的完整性,仅当configASSERT()定义时有效。*/
- listTEST_LIST_INTEGRITY( pxList );
- listTEST_LIST_ITEM_INTEGRITY(pxNewListItem );
- /*向列表中插入新的列表项*/
- pxNewListItem->pxNext = pxIndex;
- pxNewListItem->pxPrevious =pxIndex->pxPrevious;
- mtCOVERAGE_TEST_DELAY();
- pxIndex->pxPrevious->pxNext =pxNewListItem;
- pxIndex->pxPrevious = pxNewListItem;
- pxNewListItem->pvContainer = ( void* ) pxList;
- ( pxList->uxNumberOfItems )++;
- }
复制代码
5.5 列表项删除
列表项的删除只是将指定的列表项从列表中删除,并不会将这个列表项的内存给释放掉。
- UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
- {
- /* The list item knows which list it is in. Obtain the list from the list
- * item. */
- List_t * const pxList = pxItemToRemove->pxContainer;
- pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
- pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
- /* Only used during decision coverage testing. */
- mtCOVERAGE_TEST_DELAY();
- /* Make sure the index is left pointing to a valid item. */
- if( pxList->pxIndex == pxItemToRemove )
- {
- pxList->pxIndex = pxItemToRemove->pxPrevious;
- }
- else
- {
- mtCOVERAGE_TEST_MARKER();
- }
- pxItemToRemove->pxContainer = NULL;
- ( pxList->uxNumberOfItems )--;
- return pxList->uxNumberOfItems;
- }
复制代码
5.6 列表遍历
- #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \
- { \
- List_t * const pxConstList = ( pxList ); \
- /* Increment the index to the next item and return the item, ensuring */ \
- /* we don't return the marker used at the end of the list. */ \
- ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
- if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \
- { \
- ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
- } \
- ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \
- }
复制代码
|