]> begriffs open source - freertos/blob - portable/MemMang/heap_4.c
[AUTO][RELEASE]: Bump file header version to "10.4.3 LTS Patch 3"
[freertos] / portable / MemMang / heap_4.c
1 /*\r
2  * FreeRTOS Kernel V10.4.3 LTS Patch 3\r
3  * Copyright (C) 2020 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.\r
14  *\r
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS\r
17  * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR\r
18  * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER\r
19  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
20  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
21  *\r
22  * https://www.FreeRTOS.org\r
23  * https://github.com/FreeRTOS\r
24  *\r
25  */\r
26 \r
27 /*\r
28  * A sample implementation of pvPortMalloc() and vPortFree() that combines\r
29  * (coalescences) adjacent memory blocks as they are freed, and in so doing\r
30  * limits memory fragmentation.\r
31  *\r
32  * See heap_1.c, heap_2.c and heap_3.c for alternative implementations, and the\r
33  * memory management pages of https://www.FreeRTOS.org for more information.\r
34  */\r
35 #include <stdlib.h>\r
36 \r
37 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining\r
38  * all the API functions to use the MPU wrappers.  That should only be done when\r
39  * task.h is included from an application file. */\r
40 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
41 \r
42 #include "FreeRTOS.h"\r
43 #include "task.h"\r
44 \r
45 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
46 \r
47 #if ( configSUPPORT_DYNAMIC_ALLOCATION == 0 )\r
48     #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0\r
49 #endif\r
50 \r
51 /* Block sizes must not get too small. */\r
52 #define heapMINIMUM_BLOCK_SIZE    ( ( size_t ) ( xHeapStructSize << 1 ) )\r
53 \r
54 /* Assumes 8bit bytes! */\r
55 #define heapBITS_PER_BYTE         ( ( size_t ) 8 )\r
56 \r
57 /* Allocate the memory for the heap. */\r
58 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )\r
59 \r
60 /* The application writer has already defined the array used for the RTOS\r
61 * heap - probably so it can be placed in a special segment or address. */\r
62     extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
63 #else\r
64     PRIVILEGED_DATA static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
65 #endif /* configAPPLICATION_ALLOCATED_HEAP */\r
66 \r
67 /* Define the linked list structure.  This is used to link free blocks in order\r
68  * of their memory address. */\r
69 typedef struct A_BLOCK_LINK\r
70 {\r
71     struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */\r
72     size_t xBlockSize;                     /*<< The size of the free block. */\r
73 } BlockLink_t;\r
74 \r
75 /*-----------------------------------------------------------*/\r
76 \r
77 /*\r
78  * Inserts a block of memory that is being freed into the correct position in\r
79  * the list of free memory blocks.  The block being freed will be merged with\r
80  * the block in front it and/or the block behind it if the memory blocks are\r
81  * adjacent to each other.\r
82  */\r
83 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) PRIVILEGED_FUNCTION;\r
84 \r
85 /*\r
86  * Called automatically to setup the required heap structures the first time\r
87  * pvPortMalloc() is called.\r
88  */\r
89 static void prvHeapInit( void ) PRIVILEGED_FUNCTION;\r
90 \r
91 /*-----------------------------------------------------------*/\r
92 \r
93 /* The size of the structure placed at the beginning of each allocated memory\r
94  * block must by correctly byte aligned. */\r
95 static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
96 \r
97 /* Create a couple of list links to mark the start and end of the list. */\r
98 PRIVILEGED_DATA static BlockLink_t xStart, * pxEnd = NULL;\r
99 \r
100 /* Keeps track of the number of calls to allocate and free memory as well as the\r
101  * number of free bytes remaining, but says nothing about fragmentation. */\r
102 PRIVILEGED_DATA static size_t xFreeBytesRemaining = 0U;\r
103 PRIVILEGED_DATA static size_t xMinimumEverFreeBytesRemaining = 0U;\r
104 PRIVILEGED_DATA static size_t xNumberOfSuccessfulAllocations = 0;\r
105 PRIVILEGED_DATA static size_t xNumberOfSuccessfulFrees = 0;\r
106 \r
107 /* Gets set to the top bit of an size_t type.  When this bit in the xBlockSize\r
108  * member of an BlockLink_t structure is set then the block belongs to the\r
109  * application.  When the bit is free the block is still part of the free heap\r
110  * space. */\r
111 PRIVILEGED_DATA static size_t xBlockAllocatedBit = 0;\r
112 \r
113 /*-----------------------------------------------------------*/\r
114 \r
115 void * pvPortMalloc( size_t xWantedSize )\r
116 {\r
117     BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;\r
118     void * pvReturn = NULL;\r
119 \r
120     vTaskSuspendAll();\r
121     {\r
122         /* If this is the first call to malloc then the heap will require\r
123          * initialisation to setup the list of free blocks. */\r
124         if( pxEnd == NULL )\r
125         {\r
126             prvHeapInit();\r
127         }\r
128         else\r
129         {\r
130             mtCOVERAGE_TEST_MARKER();\r
131         }\r
132 \r
133         /* Check the requested block size is not so large that the top bit is\r
134          * set.  The top bit of the block size member of the BlockLink_t structure\r
135          * is used to determine who owns the block - the application or the\r
136          * kernel, so it must be free. */\r
137         if( ( xWantedSize & xBlockAllocatedBit ) == 0 )\r
138         {\r
139             /* The wanted size must be increased so it can contain a BlockLink_t\r
140              * structure in addition to the requested amount of bytes. */\r
141             if( ( xWantedSize > 0 ) && \r
142                 ( ( xWantedSize + xHeapStructSize ) >  xWantedSize ) ) /* Overflow check */\r
143             {\r
144                 xWantedSize += xHeapStructSize;\r
145 \r
146                 /* Ensure that blocks are always aligned. */\r
147                 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )\r
148                 {\r
149                     /* Byte alignment required. Check for overflow. */\r
150                     if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) ) ) \r
151                             > xWantedSize )\r
152                     {\r
153                         xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );\r
154                         configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );\r
155                     }\r
156                     else\r
157                     {\r
158                         xWantedSize = 0;\r
159                     }  \r
160                 }\r
161                 else\r
162                 {\r
163                     mtCOVERAGE_TEST_MARKER();\r
164                 }\r
165             } \r
166             else \r
167             {\r
168                 xWantedSize = 0;\r
169             }\r
170 \r
171             if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )\r
172             {\r
173                 /* Traverse the list from the start     (lowest address) block until\r
174                  * one of adequate size is found. */\r
175                 pxPreviousBlock = &xStart;\r
176                 pxBlock = xStart.pxNextFreeBlock;\r
177 \r
178                 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )\r
179                 {\r
180                     pxPreviousBlock = pxBlock;\r
181                     pxBlock = pxBlock->pxNextFreeBlock;\r
182                 }\r
183 \r
184                 /* If the end marker was reached then a block of adequate size\r
185                  * was not found. */\r
186                 if( pxBlock != pxEnd )\r
187                 {\r
188                     /* Return the memory space pointed to - jumping over the\r
189                      * BlockLink_t structure at its start. */\r
190                     pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );\r
191 \r
192                     /* This block is being returned for use so must be taken out\r
193                      * of the list of free blocks. */\r
194                     pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;\r
195 \r
196                     /* If the block is larger than required it can be split into\r
197                      * two. */\r
198                     if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )\r
199                     {\r
200                         /* This block is to be split into two.  Create a new\r
201                          * block following the number of bytes requested. The void\r
202                          * cast is used to prevent byte alignment warnings from the\r
203                          * compiler. */\r
204                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );\r
205                         configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );\r
206 \r
207                         /* Calculate the sizes of two blocks split from the\r
208                          * single block. */\r
209                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;\r
210                         pxBlock->xBlockSize = xWantedSize;\r
211 \r
212                         /* Insert the new block into the list of free blocks. */\r
213                         prvInsertBlockIntoFreeList( pxNewBlockLink );\r
214                     }\r
215                     else\r
216                     {\r
217                         mtCOVERAGE_TEST_MARKER();\r
218                     }\r
219 \r
220                     xFreeBytesRemaining -= pxBlock->xBlockSize;\r
221 \r
222                     if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )\r
223                     {\r
224                         xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;\r
225                     }\r
226                     else\r
227                     {\r
228                         mtCOVERAGE_TEST_MARKER();\r
229                     }\r
230 \r
231                     /* The block is being returned - it is allocated and owned\r
232                      * by the application and has no "next" block. */\r
233                     pxBlock->xBlockSize |= xBlockAllocatedBit;\r
234                     pxBlock->pxNextFreeBlock = NULL;\r
235                     xNumberOfSuccessfulAllocations++;\r
236                 }\r
237                 else\r
238                 {\r
239                     mtCOVERAGE_TEST_MARKER();\r
240                 }\r
241             }\r
242             else\r
243             {\r
244                 mtCOVERAGE_TEST_MARKER();\r
245             }\r
246         }\r
247         else\r
248         {\r
249             mtCOVERAGE_TEST_MARKER();\r
250         }\r
251 \r
252         traceMALLOC( pvReturn, xWantedSize );\r
253     }\r
254     ( void ) xTaskResumeAll();\r
255 \r
256     #if ( configUSE_MALLOC_FAILED_HOOK == 1 )\r
257         {\r
258             if( pvReturn == NULL )\r
259             {\r
260                 extern void vApplicationMallocFailedHook( void );\r
261                 vApplicationMallocFailedHook();\r
262             }\r
263             else\r
264             {\r
265                 mtCOVERAGE_TEST_MARKER();\r
266             }\r
267         }\r
268     #endif /* if ( configUSE_MALLOC_FAILED_HOOK == 1 ) */\r
269 \r
270     configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );\r
271     return pvReturn;\r
272 }\r
273 /*-----------------------------------------------------------*/\r
274 \r
275 void vPortFree( void * pv )\r
276 {\r
277     uint8_t * puc = ( uint8_t * ) pv;\r
278     BlockLink_t * pxLink;\r
279 \r
280     if( pv != NULL )\r
281     {\r
282         /* The memory being freed will have an BlockLink_t structure immediately\r
283          * before it. */\r
284         puc -= xHeapStructSize;\r
285 \r
286         /* This casting is to keep the compiler from issuing warnings. */\r
287         pxLink = ( void * ) puc;\r
288 \r
289         /* Check the block is actually allocated. */\r
290         configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );\r
291         configASSERT( pxLink->pxNextFreeBlock == NULL );\r
292 \r
293         if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )\r
294         {\r
295             if( pxLink->pxNextFreeBlock == NULL )\r
296             {\r
297                 /* The block is being returned to the heap - it is no longer\r
298                  * allocated. */\r
299                 pxLink->xBlockSize &= ~xBlockAllocatedBit;\r
300 \r
301                 vTaskSuspendAll();\r
302                 {\r
303                     /* Add this block to the list of free blocks. */\r
304                     xFreeBytesRemaining += pxLink->xBlockSize;\r
305                     traceFREE( pv, pxLink->xBlockSize );\r
306                     prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );\r
307                     xNumberOfSuccessfulFrees++;\r
308                 }\r
309                 ( void ) xTaskResumeAll();\r
310             }\r
311             else\r
312             {\r
313                 mtCOVERAGE_TEST_MARKER();\r
314             }\r
315         }\r
316         else\r
317         {\r
318             mtCOVERAGE_TEST_MARKER();\r
319         }\r
320     }\r
321 }\r
322 /*-----------------------------------------------------------*/\r
323 \r
324 size_t xPortGetFreeHeapSize( void )\r
325 {\r
326     return xFreeBytesRemaining;\r
327 }\r
328 /*-----------------------------------------------------------*/\r
329 \r
330 size_t xPortGetMinimumEverFreeHeapSize( void )\r
331 {\r
332     return xMinimumEverFreeBytesRemaining;\r
333 }\r
334 /*-----------------------------------------------------------*/\r
335 \r
336 void vPortInitialiseBlocks( void )\r
337 {\r
338     /* This just exists to keep the linker quiet. */\r
339 }\r
340 /*-----------------------------------------------------------*/\r
341 \r
342 static void prvHeapInit( void ) /* PRIVILEGED_FUNCTION */\r
343 {\r
344     BlockLink_t * pxFirstFreeBlock;\r
345     uint8_t * pucAlignedHeap;\r
346     size_t uxAddress;\r
347     size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;\r
348 \r
349     /* Ensure the heap starts on a correctly aligned boundary. */\r
350     uxAddress = ( size_t ) ucHeap;\r
351 \r
352     if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )\r
353     {\r
354         uxAddress += ( portBYTE_ALIGNMENT - 1 );\r
355         uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
356         xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;\r
357     }\r
358 \r
359     pucAlignedHeap = ( uint8_t * ) uxAddress;\r
360 \r
361     /* xStart is used to hold a pointer to the first item in the list of free\r
362      * blocks.  The void cast is used to prevent compiler warnings. */\r
363     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;\r
364     xStart.xBlockSize = ( size_t ) 0;\r
365 \r
366     /* pxEnd is used to mark the end of the list of free blocks and is inserted\r
367      * at the end of the heap space. */\r
368     uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;\r
369     uxAddress -= xHeapStructSize;\r
370     uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
371     pxEnd = ( void * ) uxAddress;\r
372     pxEnd->xBlockSize = 0;\r
373     pxEnd->pxNextFreeBlock = NULL;\r
374 \r
375     /* To start with there is a single free block that is sized to take up the\r
376      * entire heap space, minus the space taken by pxEnd. */\r
377     pxFirstFreeBlock = ( void * ) pucAlignedHeap;\r
378     pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;\r
379     pxFirstFreeBlock->pxNextFreeBlock = pxEnd;\r
380 \r
381     /* Only one block exists - and it covers the entire usable heap space. */\r
382     xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;\r
383     xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;\r
384 \r
385     /* Work out the position of the top bit in a size_t variable. */\r
386     xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );\r
387 }\r
388 /*-----------------------------------------------------------*/\r
389 \r
390 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) /* PRIVILEGED_FUNCTION */\r
391 {\r
392     BlockLink_t * pxIterator;\r
393     uint8_t * puc;\r
394 \r
395     /* Iterate through the list until a block is found that has a higher address\r
396      * than the block being inserted. */\r
397     for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )\r
398     {\r
399         /* Nothing to do here, just iterate to the right position. */\r
400     }\r
401 \r
402     /* Do the block being inserted, and the block it is being inserted after\r
403      * make a contiguous block of memory? */\r
404     puc = ( uint8_t * ) pxIterator;\r
405 \r
406     if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )\r
407     {\r
408         pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;\r
409         pxBlockToInsert = pxIterator;\r
410     }\r
411     else\r
412     {\r
413         mtCOVERAGE_TEST_MARKER();\r
414     }\r
415 \r
416     /* Do the block being inserted, and the block it is being inserted before\r
417      * make a contiguous block of memory? */\r
418     puc = ( uint8_t * ) pxBlockToInsert;\r
419 \r
420     if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )\r
421     {\r
422         if( pxIterator->pxNextFreeBlock != pxEnd )\r
423         {\r
424             /* Form one big block from the two blocks. */\r
425             pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;\r
426             pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;\r
427         }\r
428         else\r
429         {\r
430             pxBlockToInsert->pxNextFreeBlock = pxEnd;\r
431         }\r
432     }\r
433     else\r
434     {\r
435         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;\r
436     }\r
437 \r
438     /* If the block being inserted plugged a gab, so was merged with the block\r
439      * before and the block after, then it's pxNextFreeBlock pointer will have\r
440      * already been set, and should not be set here as that would make it point\r
441      * to itself. */\r
442     if( pxIterator != pxBlockToInsert )\r
443     {\r
444         pxIterator->pxNextFreeBlock = pxBlockToInsert;\r
445     }\r
446     else\r
447     {\r
448         mtCOVERAGE_TEST_MARKER();\r
449     }\r
450 }\r
451 /*-----------------------------------------------------------*/\r
452 \r
453 void vPortGetHeapStats( HeapStats_t * pxHeapStats )\r
454 {\r
455     BlockLink_t * pxBlock;\r
456     size_t xBlocks = 0, xMaxSize = 0, xMinSize = portMAX_DELAY; /* portMAX_DELAY used as a portable way of getting the maximum value. */\r
457 \r
458     vTaskSuspendAll();\r
459     {\r
460         pxBlock = xStart.pxNextFreeBlock;\r
461 \r
462         /* pxBlock will be NULL if the heap has not been initialised.  The heap\r
463          * is initialised automatically when the first allocation is made. */\r
464         if( pxBlock != NULL )\r
465         {\r
466             do\r
467             {\r
468                 /* Increment the number of blocks and record the largest block seen\r
469                  * so far. */\r
470                 xBlocks++;\r
471 \r
472                 if( pxBlock->xBlockSize > xMaxSize )\r
473                 {\r
474                     xMaxSize = pxBlock->xBlockSize;\r
475                 }\r
476 \r
477                 if( pxBlock->xBlockSize < xMinSize )\r
478                 {\r
479                     xMinSize = pxBlock->xBlockSize;\r
480                 }\r
481 \r
482                 /* Move to the next block in the chain until the last block is\r
483                  * reached. */\r
484                 pxBlock = pxBlock->pxNextFreeBlock;\r
485             } while( pxBlock != pxEnd );\r
486         }\r
487     }\r
488     ( void ) xTaskResumeAll();\r
489 \r
490     pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;\r
491     pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;\r
492     pxHeapStats->xNumberOfFreeBlocks = xBlocks;\r
493 \r
494     taskENTER_CRITICAL();\r
495     {\r
496         pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;\r
497         pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;\r
498         pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;\r
499         pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;\r
500     }\r
501     taskEXIT_CRITICAL();\r
502 }\r