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