1 /*
2 * FreeRTOS Kernel V10.6.2
3 * Copyright (C) 2021 Amazon.com, Inc. or its affiliates. All Rights Reserved.
4 *
5 * SPDX-License-Identifier: MIT
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy of
8 * this software and associated documentation files (the "Software"), to deal in
9 * the Software without restriction, including without limitation the rights to
10 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
11 * the Software, and to permit persons to whom the Software is furnished to do so,
12 * subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in all
15 * copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
19 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
20 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
21 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 *
24 * https://www.FreeRTOS.org
25 * https://github.com/FreeRTOS
26 *
27 */
28
29
30 #include <stdlib.h>
31
32 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
33 * all the API functions to use the MPU wrappers. That should only be done when
34 * task.h is included from an application file. */
35 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
36
37 #include "FreeRTOS.h"
38 #include "list.h"
39
40 /* Lint e9021, e961 and e750 are suppressed as a MISRA exception justified
41 * because the MPU ports require MPU_WRAPPERS_INCLUDED_FROM_API_FILE to be
42 * defined for the header files above, but not in this file, in order to
43 * generate the correct privileged Vs unprivileged linkage and placement. */
44 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE /*lint !e961 !e750 !e9021. */
45
46 /*-----------------------------------------------------------
47 * PUBLIC LIST API documented in list.h
48 *----------------------------------------------------------*/
49
vListInitialise(List_t * const pxList)50 void vListInitialise( List_t * const pxList )
51 {
52 /* The list structure contains a list item which is used to mark the
53 * end of the list. To initialise the list the list end is inserted
54 * as the only list entry. */
55 pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
56
57 listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );
58
59 /* The list end value is the highest possible value in the list to
60 * ensure it remains at the end of the list. */
61 pxList->xListEnd.xItemValue = portMAX_DELAY;
62
63 /* The list end next and previous pointers point to itself so we know
64 * when the list is empty. */
65 pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
66 pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
67
68 /* Initialize the remaining fields of xListEnd when it is a proper ListItem_t */
69 #if ( configUSE_MINI_LIST_ITEM == 0 )
70 {
71 pxList->xListEnd.pvOwner = NULL;
72 pxList->xListEnd.pxContainer = NULL;
73 listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );
74 }
75 #endif
76
77 pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
78
79 /* Write known values into the list if
80 * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
81 listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
82 listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
83 }
84 /*-----------------------------------------------------------*/
85
vListInitialiseItem(ListItem_t * const pxItem)86 void vListInitialiseItem( ListItem_t * const pxItem )
87 {
88 /* Make sure the list item is not recorded as being on a list. */
89 pxItem->pxContainer = NULL;
90
91 /* Write known values into the list item if
92 * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
93 listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
94 listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
95 }
96 /*-----------------------------------------------------------*/
97
vListInsertEnd(List_t * const pxList,ListItem_t * const pxNewListItem)98 void vListInsertEnd( List_t * const pxList,
99 ListItem_t * const pxNewListItem )
100 {
101 ListItem_t * const pxIndex = pxList->pxIndex;
102
103 /* Only effective when configASSERT() is also defined, these tests may catch
104 * the list data structures being overwritten in memory. They will not catch
105 * data errors caused by incorrect configuration or use of FreeRTOS. */
106 listTEST_LIST_INTEGRITY( pxList );
107 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
108
109 /* Insert a new list item into pxList, but rather than sort the list,
110 * makes the new list item the last item to be removed by a call to
111 * listGET_OWNER_OF_NEXT_ENTRY(). */
112 pxNewListItem->pxNext = pxIndex;
113 pxNewListItem->pxPrevious = pxIndex->pxPrevious;
114
115 /* Only used during decision coverage testing. */
116 mtCOVERAGE_TEST_DELAY();
117
118 pxIndex->pxPrevious->pxNext = pxNewListItem;
119 pxIndex->pxPrevious = pxNewListItem;
120
121 /* Remember which list the item is in. */
122 pxNewListItem->pxContainer = pxList;
123
124 ( pxList->uxNumberOfItems )++;
125 }
126 /*-----------------------------------------------------------*/
127
vListInsert(List_t * const pxList,ListItem_t * const pxNewListItem)128 void vListInsert( List_t * const pxList,
129 ListItem_t * const pxNewListItem )
130 {
131 ListItem_t * pxIterator;
132 const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
133
134 /* Only effective when configASSERT() is also defined, these tests may catch
135 * the list data structures being overwritten in memory. They will not catch
136 * data errors caused by incorrect configuration or use of FreeRTOS. */
137 listTEST_LIST_INTEGRITY( pxList );
138 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
139
140 /* Insert the new list item into the list, sorted in xItemValue order.
141 *
142 * If the list already contains a list item with the same item value then the
143 * new list item should be placed after it. This ensures that TCBs which are
144 * stored in ready lists (all of which have the same xItemValue value) get a
145 * share of the CPU. However, if the xItemValue is the same as the back marker
146 * the iteration loop below will not end. Therefore the value is checked
147 * first, and the algorithm slightly modified if necessary. */
148 if( xValueOfInsertion == portMAX_DELAY )
149 {
150 pxIterator = pxList->xListEnd.pxPrevious;
151 }
152 else
153 {
154 /* *** NOTE ***********************************************************
155 * If you find your application is crashing here then likely causes are
156 * listed below. In addition see https://www.FreeRTOS.org/FAQHelp.html for
157 * more tips, and ensure configASSERT() is defined!
158 * https://www.FreeRTOS.org/a00110.html#configASSERT
159 *
160 * 1) Stack overflow -
161 * see https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html
162 * 2) Incorrect interrupt priority assignment, especially on Cortex-M
163 * parts where numerically high priority values denote low actual
164 * interrupt priorities, which can seem counter intuitive. See
165 * https://www.FreeRTOS.org/RTOS-Cortex-M3-M4.html and the definition
166 * of configMAX_SYSCALL_INTERRUPT_PRIORITY on
167 * https://www.FreeRTOS.org/a00110.html
168 * 3) Calling an API function from within a critical section or when
169 * the scheduler is suspended, or calling an API function that does
170 * not end in "FromISR" from an interrupt.
171 * 4) Using a queue or semaphore before it has been initialised or
172 * before the scheduler has been started (are interrupts firing
173 * before vTaskStartScheduler() has been called?).
174 * 5) If the FreeRTOS port supports interrupt nesting then ensure that
175 * the priority of the tick interrupt is at or below
176 * configMAX_SYSCALL_INTERRUPT_PRIORITY.
177 **********************************************************************/
178
179 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. */
180 {
181 /* There is nothing to do here, just iterating to the wanted
182 * insertion position. */
183 }
184 }
185
186 pxNewListItem->pxNext = pxIterator->pxNext;
187 pxNewListItem->pxNext->pxPrevious = pxNewListItem;
188 pxNewListItem->pxPrevious = pxIterator;
189 pxIterator->pxNext = pxNewListItem;
190
191 /* Remember which list the item is in. This allows fast removal of the
192 * item later. */
193 pxNewListItem->pxContainer = pxList;
194
195 ( pxList->uxNumberOfItems )++;
196 }
197 /*-----------------------------------------------------------*/
198
uxListRemove(ListItem_t * const pxItemToRemove)199 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
200 {
201 /* The list item knows which list it is in. Obtain the list from the list
202 * item. */
203 List_t * const pxList = pxItemToRemove->pxContainer;
204
205 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
206 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
207
208 /* Only used during decision coverage testing. */
209 mtCOVERAGE_TEST_DELAY();
210
211 /* Make sure the index is left pointing to a valid item. */
212 if( pxList->pxIndex == pxItemToRemove )
213 {
214 pxList->pxIndex = pxItemToRemove->pxPrevious;
215 }
216 else
217 {
218 mtCOVERAGE_TEST_MARKER();
219 }
220
221 pxItemToRemove->pxContainer = NULL;
222 ( pxList->uxNumberOfItems )--;
223
224 return pxList->uxNumberOfItems;
225 }
226 /*-----------------------------------------------------------*/
227
