2 * FreeRTOS Kernel V10.4.3 LTS Patch 3
\r
3 * Copyright (C) 2020 Amazon.com, Inc. or its affiliates. All Rights Reserved.
\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
12 * The above copyright notice and this permission notice shall be included in all
\r
13 * copies or substantial portions of the Software.
\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
22 * https://www.FreeRTOS.org
\r
23 * https://github.com/FreeRTOS
\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
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
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
42 #include "FreeRTOS.h"
\r
45 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
\r
47 #if ( configSUPPORT_DYNAMIC_ALLOCATION == 0 )
\r
48 #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
\r
51 /* Block sizes must not get too small. */
\r
52 #define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( xHeapStructSize << 1 ) )
\r
54 /* Assumes 8bit bytes! */
\r
55 #define heapBITS_PER_BYTE ( ( size_t ) 8 )
\r
57 /* Allocate the memory for the heap. */
\r
58 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )
\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
64 PRIVILEGED_DATA static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
\r
65 #endif /* configAPPLICATION_ALLOCATED_HEAP */
\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
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
75 /*-----------------------------------------------------------*/
\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
83 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) PRIVILEGED_FUNCTION;
\r
86 * Called automatically to setup the required heap structures the first time
\r
87 * pvPortMalloc() is called.
\r
89 static void prvHeapInit( void ) PRIVILEGED_FUNCTION;
\r
91 /*-----------------------------------------------------------*/
\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
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
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
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
111 PRIVILEGED_DATA static size_t xBlockAllocatedBit = 0;
\r
113 /*-----------------------------------------------------------*/
\r
115 void * pvPortMalloc( size_t xWantedSize )
\r
117 BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;
\r
118 void * pvReturn = NULL;
\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
130 mtCOVERAGE_TEST_MARKER();
\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
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
144 xWantedSize += xHeapStructSize;
\r
146 /* Ensure that blocks are always aligned. */
\r
147 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
\r
149 /* Byte alignment required. Check for overflow. */
\r
150 if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) ) )
\r
153 xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
\r
154 configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
\r
163 mtCOVERAGE_TEST_MARKER();
\r
171 if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
\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
178 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
\r
180 pxPreviousBlock = pxBlock;
\r
181 pxBlock = pxBlock->pxNextFreeBlock;
\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
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
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
196 /* If the block is larger than required it can be split into
\r
198 if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
\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
204 pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
\r
205 configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );
\r
207 /* Calculate the sizes of two blocks split from the
\r
209 pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
\r
210 pxBlock->xBlockSize = xWantedSize;
\r
212 /* Insert the new block into the list of free blocks. */
\r
213 prvInsertBlockIntoFreeList( pxNewBlockLink );
\r
217 mtCOVERAGE_TEST_MARKER();
\r
220 xFreeBytesRemaining -= pxBlock->xBlockSize;
\r
222 if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
\r
224 xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
\r
228 mtCOVERAGE_TEST_MARKER();
\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
239 mtCOVERAGE_TEST_MARKER();
\r
244 mtCOVERAGE_TEST_MARKER();
\r
249 mtCOVERAGE_TEST_MARKER();
\r
252 traceMALLOC( pvReturn, xWantedSize );
\r
254 ( void ) xTaskResumeAll();
\r
256 #if ( configUSE_MALLOC_FAILED_HOOK == 1 )
\r
258 if( pvReturn == NULL )
\r
260 extern void vApplicationMallocFailedHook( void );
\r
261 vApplicationMallocFailedHook();
\r
265 mtCOVERAGE_TEST_MARKER();
\r
268 #endif /* if ( configUSE_MALLOC_FAILED_HOOK == 1 ) */
\r
270 configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
\r
273 /*-----------------------------------------------------------*/
\r
275 void vPortFree( void * pv )
\r
277 uint8_t * puc = ( uint8_t * ) pv;
\r
278 BlockLink_t * pxLink;
\r
282 /* The memory being freed will have an BlockLink_t structure immediately
\r
284 puc -= xHeapStructSize;
\r
286 /* This casting is to keep the compiler from issuing warnings. */
\r
287 pxLink = ( void * ) puc;
\r
289 /* Check the block is actually allocated. */
\r
290 configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
\r
291 configASSERT( pxLink->pxNextFreeBlock == NULL );
\r
293 if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
\r
295 if( pxLink->pxNextFreeBlock == NULL )
\r
297 /* The block is being returned to the heap - it is no longer
\r
299 pxLink->xBlockSize &= ~xBlockAllocatedBit;
\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
309 ( void ) xTaskResumeAll();
\r
313 mtCOVERAGE_TEST_MARKER();
\r
318 mtCOVERAGE_TEST_MARKER();
\r
322 /*-----------------------------------------------------------*/
\r
324 size_t xPortGetFreeHeapSize( void )
\r
326 return xFreeBytesRemaining;
\r
328 /*-----------------------------------------------------------*/
\r
330 size_t xPortGetMinimumEverFreeHeapSize( void )
\r
332 return xMinimumEverFreeBytesRemaining;
\r
334 /*-----------------------------------------------------------*/
\r
336 void vPortInitialiseBlocks( void )
\r
338 /* This just exists to keep the linker quiet. */
\r
340 /*-----------------------------------------------------------*/
\r
342 static void prvHeapInit( void ) /* PRIVILEGED_FUNCTION */
\r
344 BlockLink_t * pxFirstFreeBlock;
\r
345 uint8_t * pucAlignedHeap;
\r
347 size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
\r
349 /* Ensure the heap starts on a correctly aligned boundary. */
\r
350 uxAddress = ( size_t ) ucHeap;
\r
352 if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
\r
354 uxAddress += ( portBYTE_ALIGNMENT - 1 );
\r
355 uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
\r
356 xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
\r
359 pucAlignedHeap = ( uint8_t * ) uxAddress;
\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
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
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
381 /* Only one block exists - and it covers the entire usable heap space. */
\r
382 xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
\r
383 xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
\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
388 /*-----------------------------------------------------------*/
\r
390 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) /* PRIVILEGED_FUNCTION */
\r
392 BlockLink_t * pxIterator;
\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
399 /* Nothing to do here, just iterate to the right position. */
\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
406 if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
\r
408 pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
\r
409 pxBlockToInsert = pxIterator;
\r
413 mtCOVERAGE_TEST_MARKER();
\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
420 if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
\r
422 if( pxIterator->pxNextFreeBlock != pxEnd )
\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
430 pxBlockToInsert->pxNextFreeBlock = pxEnd;
\r
435 pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
\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
442 if( pxIterator != pxBlockToInsert )
\r
444 pxIterator->pxNextFreeBlock = pxBlockToInsert;
\r
448 mtCOVERAGE_TEST_MARKER();
\r
451 /*-----------------------------------------------------------*/
\r
453 void vPortGetHeapStats( HeapStats_t * pxHeapStats )
\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
460 pxBlock = xStart.pxNextFreeBlock;
\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
468 /* Increment the number of blocks and record the largest block seen
\r
472 if( pxBlock->xBlockSize > xMaxSize )
\r
474 xMaxSize = pxBlock->xBlockSize;
\r
477 if( pxBlock->xBlockSize < xMinSize )
\r
479 xMinSize = pxBlock->xBlockSize;
\r
482 /* Move to the next block in the chain until the last block is
\r
484 pxBlock = pxBlock->pxNextFreeBlock;
\r
485 } while( pxBlock != pxEnd );
\r
488 ( void ) xTaskResumeAll();
\r
490 pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;
\r
491 pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;
\r
492 pxHeapStats->xNumberOfFreeBlocks = xBlocks;
\r
494 taskENTER_CRITICAL();
\r
496 pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;
\r
497 pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;
\r
498 pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;
\r
499 pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;
\r
501 taskEXIT_CRITICAL();
\r