]> git.sur5r.net Git - freertos/blob - FreeRTOS/Source/portable/MemMang/heap_2.c
Update to MIT licensed FreeRTOS V10.0.0 - see https://www.freertos.org/History.txt
[freertos] / FreeRTOS / Source / portable / MemMang / heap_2.c
1 /*\r
2  * FreeRTOS Kernel V10.0.0\r
3  * Copyright (C) 2017 Amazon.com, Inc. or its affiliates.  All Rights Reserved.\r
4  *\r
5  * Permission is hereby granted, free of charge, to any person obtaining a copy of\r
6  * this software and associated documentation files (the "Software"), to deal in\r
7  * the Software without restriction, including without limitation the rights to\r
8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of\r
9  * the Software, and to permit persons to whom the Software is furnished to do so,\r
10  * subject to the following conditions:\r
11  *\r
12  * The above copyright notice and this permission notice shall be included in all\r
13  * copies or substantial portions of the Software. If you wish to use our Amazon\r
14  * FreeRTOS name, please do so in a fair use way that does not cause confusion.\r
15  *\r
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS\r
18  * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR\r
19  * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER\r
20  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
22  *\r
23  * http://www.FreeRTOS.org\r
24  * http://aws.amazon.com/freertos\r
25  *\r
26  * 1 tab == 4 spaces!\r
27  */\r
28 \r
29 /*\r
30  * A sample implementation of pvPortMalloc() and vPortFree() that permits\r
31  * allocated blocks to be freed, but does not combine adjacent free blocks\r
32  * into a single larger block (and so will fragment memory).  See heap_4.c for\r
33  * an equivalent that does combine adjacent blocks into single larger blocks.\r
34  *\r
35  * See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the\r
36  * memory management pages of http://www.FreeRTOS.org for more information.\r
37  */\r
38 #include <stdlib.h>\r
39 \r
40 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining\r
41 all the API functions to use the MPU wrappers.  That should only be done when\r
42 task.h is included from an application file. */\r
43 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
44 \r
45 #include "FreeRTOS.h"\r
46 #include "task.h"\r
47 \r
48 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
49 \r
50 #if( configSUPPORT_DYNAMIC_ALLOCATION == 0 )\r
51         #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0\r
52 #endif\r
53 \r
54 /* A few bytes might be lost to byte aligning the heap start address. */\r
55 #define configADJUSTED_HEAP_SIZE        ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )\r
56 \r
57 /*\r
58  * Initialises the heap structures before their first use.\r
59  */\r
60 static void prvHeapInit( void );\r
61 \r
62 /* Allocate the memory for the heap. */\r
63 #if( configAPPLICATION_ALLOCATED_HEAP == 1 )\r
64         /* The application writer has already defined the array used for the RTOS\r
65         heap - probably so it can be placed in a special segment or address. */\r
66         extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
67 #else\r
68         static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
69 #endif /* configAPPLICATION_ALLOCATED_HEAP */\r
70 \r
71 \r
72 /* Define the linked list structure.  This is used to link free blocks in order\r
73 of their size. */\r
74 typedef struct A_BLOCK_LINK\r
75 {\r
76         struct A_BLOCK_LINK *pxNextFreeBlock;   /*<< The next free block in the list. */\r
77         size_t xBlockSize;                                              /*<< The size of the free block. */\r
78 } BlockLink_t;\r
79 \r
80 \r
81 static const uint16_t heapSTRUCT_SIZE   = ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );\r
82 #define heapMINIMUM_BLOCK_SIZE  ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )\r
83 \r
84 /* Create a couple of list links to mark the start and end of the list. */\r
85 static BlockLink_t xStart, xEnd;\r
86 \r
87 /* Keeps track of the number of free bytes remaining, but says nothing about\r
88 fragmentation. */\r
89 static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;\r
90 \r
91 /* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */\r
92 \r
93 /*\r
94  * Insert a block into the list of free blocks - which is ordered by size of\r
95  * the block.  Small blocks at the start of the list and large blocks at the end\r
96  * of the list.\r
97  */\r
98 #define prvInsertBlockIntoFreeList( pxBlockToInsert )                                                           \\r
99 {                                                                                                                                                                       \\r
100 BlockLink_t *pxIterator;                                                                                                                        \\r
101 size_t xBlockSize;                                                                                                                                      \\r
102                                                                                                                                                                         \\r
103         xBlockSize = pxBlockToInsert->xBlockSize;                                                                               \\r
104                                                                                                                                                                         \\r
105         /* Iterate through the list until a block is found that has a larger size */    \\r
106         /* than the block we are inserting. */                                                                                  \\r
107         for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock )     \\r
108         {                                                                                                                                                               \\r
109                 /* There is nothing to do here - just iterate to the correct position. */       \\r
110         }                                                                                                                                                               \\r
111                                                                                                                                                                         \\r
112         /* Update the list to include the block being inserted in the correct */                \\r
113         /* position. */                                                                                                                                 \\r
114         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;                                 \\r
115         pxIterator->pxNextFreeBlock = pxBlockToInsert;                                                                  \\r
116 }\r
117 /*-----------------------------------------------------------*/\r
118 \r
119 void *pvPortMalloc( size_t xWantedSize )\r
120 {\r
121 BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;\r
122 static BaseType_t xHeapHasBeenInitialised = pdFALSE;\r
123 void *pvReturn = NULL;\r
124 \r
125         vTaskSuspendAll();\r
126         {\r
127                 /* If this is the first call to malloc then the heap will require\r
128                 initialisation to setup the list of free blocks. */\r
129                 if( xHeapHasBeenInitialised == pdFALSE )\r
130                 {\r
131                         prvHeapInit();\r
132                         xHeapHasBeenInitialised = pdTRUE;\r
133                 }\r
134 \r
135                 /* The wanted size is increased so it can contain a BlockLink_t\r
136                 structure in addition to the requested amount of bytes. */\r
137                 if( xWantedSize > 0 )\r
138                 {\r
139                         xWantedSize += heapSTRUCT_SIZE;\r
140 \r
141                         /* Ensure that blocks are always aligned to the required number of bytes. */\r
142                         if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )\r
143                         {\r
144                                 /* Byte alignment required. */\r
145                                 xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );\r
146                         }\r
147                 }\r
148 \r
149                 if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )\r
150                 {\r
151                         /* Blocks are stored in byte order - traverse the list from the start\r
152                         (smallest) block until one of adequate size is found. */\r
153                         pxPreviousBlock = &xStart;\r
154                         pxBlock = xStart.pxNextFreeBlock;\r
155                         while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )\r
156                         {\r
157                                 pxPreviousBlock = pxBlock;\r
158                                 pxBlock = pxBlock->pxNextFreeBlock;\r
159                         }\r
160 \r
161                         /* If we found the end marker then a block of adequate size was not found. */\r
162                         if( pxBlock != &xEnd )\r
163                         {\r
164                                 /* Return the memory space - jumping over the BlockLink_t structure\r
165                                 at its start. */\r
166                                 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );\r
167 \r
168                                 /* This block is being returned for use so must be taken out of the\r
169                                 list of free blocks. */\r
170                                 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;\r
171 \r
172                                 /* If the block is larger than required it can be split into two. */\r
173                                 if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )\r
174                                 {\r
175                                         /* This block is to be split into two.  Create a new block\r
176                                         following the number of bytes requested. The void cast is\r
177                                         used to prevent byte alignment warnings from the compiler. */\r
178                                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );\r
179 \r
180                                         /* Calculate the sizes of two blocks split from the single\r
181                                         block. */\r
182                                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;\r
183                                         pxBlock->xBlockSize = xWantedSize;\r
184 \r
185                                         /* Insert the new block into the list of free blocks. */\r
186                                         prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );\r
187                                 }\r
188 \r
189                                 xFreeBytesRemaining -= pxBlock->xBlockSize;\r
190                         }\r
191                 }\r
192 \r
193                 traceMALLOC( pvReturn, xWantedSize );\r
194         }\r
195         ( void ) xTaskResumeAll();\r
196 \r
197         #if( configUSE_MALLOC_FAILED_HOOK == 1 )\r
198         {\r
199                 if( pvReturn == NULL )\r
200                 {\r
201                         extern void vApplicationMallocFailedHook( void );\r
202                         vApplicationMallocFailedHook();\r
203                 }\r
204         }\r
205         #endif\r
206 \r
207         return pvReturn;\r
208 }\r
209 /*-----------------------------------------------------------*/\r
210 \r
211 void vPortFree( void *pv )\r
212 {\r
213 uint8_t *puc = ( uint8_t * ) pv;\r
214 BlockLink_t *pxLink;\r
215 \r
216         if( pv != NULL )\r
217         {\r
218                 /* The memory being freed will have an BlockLink_t structure immediately\r
219                 before it. */\r
220                 puc -= heapSTRUCT_SIZE;\r
221 \r
222                 /* This unexpected casting is to keep some compilers from issuing\r
223                 byte alignment warnings. */\r
224                 pxLink = ( void * ) puc;\r
225 \r
226                 vTaskSuspendAll();\r
227                 {\r
228                         /* Add this block to the list of free blocks. */\r
229                         prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );\r
230                         xFreeBytesRemaining += pxLink->xBlockSize;\r
231                         traceFREE( pv, pxLink->xBlockSize );\r
232                 }\r
233                 ( void ) xTaskResumeAll();\r
234         }\r
235 }\r
236 /*-----------------------------------------------------------*/\r
237 \r
238 size_t xPortGetFreeHeapSize( void )\r
239 {\r
240         return xFreeBytesRemaining;\r
241 }\r
242 /*-----------------------------------------------------------*/\r
243 \r
244 void vPortInitialiseBlocks( void )\r
245 {\r
246         /* This just exists to keep the linker quiet. */\r
247 }\r
248 /*-----------------------------------------------------------*/\r
249 \r
250 static void prvHeapInit( void )\r
251 {\r
252 BlockLink_t *pxFirstFreeBlock;\r
253 uint8_t *pucAlignedHeap;\r
254 \r
255         /* Ensure the heap starts on a correctly aligned boundary. */\r
256         pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );\r
257 \r
258         /* xStart is used to hold a pointer to the first item in the list of free\r
259         blocks.  The void cast is used to prevent compiler warnings. */\r
260         xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;\r
261         xStart.xBlockSize = ( size_t ) 0;\r
262 \r
263         /* xEnd is used to mark the end of the list of free blocks. */\r
264         xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;\r
265         xEnd.pxNextFreeBlock = NULL;\r
266 \r
267         /* To start with there is a single free block that is sized to take up the\r
268         entire heap space. */\r
269         pxFirstFreeBlock = ( void * ) pucAlignedHeap;\r
270         pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;\r
271         pxFirstFreeBlock->pxNextFreeBlock = &xEnd;\r
272 }\r
273 /*-----------------------------------------------------------*/\r