2 * FreeRTOS Kernel <DEVELOPMENT BRANCH>
\r
3 * Copyright (C) 2021 Amazon.com, Inc. or its affiliates. All Rights Reserved.
\r
5 * SPDX-License-Identifier: MIT
7 * Permission is hereby granted, free of charge, to any person obtaining a copy of
\r
8 * this software and associated documentation files (the "Software"), to deal in
\r
9 * the Software without restriction, including without limitation the rights to
\r
10 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
\r
11 * the Software, and to permit persons to whom the Software is furnished to do so,
\r
12 * subject to the following conditions:
\r
14 * The above copyright notice and this permission notice shall be included in all
\r
15 * copies or substantial portions of the Software.
\r
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
\r
19 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
\r
20 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
\r
21 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
\r
22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
\r
24 * https://www.FreeRTOS.org
\r
25 * https://github.com/FreeRTOS
\r
30 * A sample implementation of pvPortMalloc() and vPortFree() that combines
\r
31 * (coalescences) adjacent memory blocks as they are freed, and in so doing
\r
32 * limits memory fragmentation.
\r
34 * See heap_1.c, heap_2.c and heap_3.c for alternative implementations, and the
\r
35 * memory management pages of https://www.FreeRTOS.org for more information.
\r
39 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
\r
40 * all the API functions to use the MPU wrappers. That should only be done when
\r
41 * task.h is included from an application file. */
\r
42 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
\r
44 #include "FreeRTOS.h"
\r
47 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
\r
49 #if ( configSUPPORT_DYNAMIC_ALLOCATION == 0 )
\r
50 #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
\r
53 /* Block sizes must not get too small. */
\r
54 #define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( xHeapStructSize << 1 ) )
\r
56 /* Assumes 8bit bytes! */
\r
57 #define heapBITS_PER_BYTE ( ( size_t ) 8 )
\r
59 /* Allocate the memory for the heap. */
\r
60 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )
\r
62 /* The application writer has already defined the array used for the RTOS
\r
63 * heap - probably so it can be placed in a special segment or address. */
\r
64 extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
\r
66 PRIVILEGED_DATA static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
\r
67 #endif /* configAPPLICATION_ALLOCATED_HEAP */
\r
69 /* Define the linked list structure. This is used to link free blocks in order
\r
70 * of their memory address. */
\r
71 typedef struct A_BLOCK_LINK
\r
73 struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */
\r
74 size_t xBlockSize; /*<< The size of the free block. */
\r
77 /*-----------------------------------------------------------*/
\r
80 * Inserts a block of memory that is being freed into the correct position in
\r
81 * the list of free memory blocks. The block being freed will be merged with
\r
82 * the block in front it and/or the block behind it if the memory blocks are
\r
83 * adjacent to each other.
\r
85 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) PRIVILEGED_FUNCTION;
\r
88 * Called automatically to setup the required heap structures the first time
\r
89 * pvPortMalloc() is called.
\r
91 static void prvHeapInit( void ) PRIVILEGED_FUNCTION;
\r
93 /*-----------------------------------------------------------*/
\r
95 /* The size of the structure placed at the beginning of each allocated memory
\r
96 * block must by correctly byte aligned. */
\r
97 static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
\r
99 /* Create a couple of list links to mark the start and end of the list. */
\r
100 PRIVILEGED_DATA static BlockLink_t xStart, * pxEnd = NULL;
\r
102 /* Keeps track of the number of calls to allocate and free memory as well as the
\r
103 * number of free bytes remaining, but says nothing about fragmentation. */
\r
104 PRIVILEGED_DATA static size_t xFreeBytesRemaining = 0U;
\r
105 PRIVILEGED_DATA static size_t xMinimumEverFreeBytesRemaining = 0U;
\r
106 PRIVILEGED_DATA static size_t xNumberOfSuccessfulAllocations = 0;
\r
107 PRIVILEGED_DATA static size_t xNumberOfSuccessfulFrees = 0;
\r
109 /* Gets set to the top bit of an size_t type. When this bit in the xBlockSize
\r
110 * member of an BlockLink_t structure is set then the block belongs to the
\r
111 * application. When the bit is free the block is still part of the free heap
\r
113 PRIVILEGED_DATA static size_t xBlockAllocatedBit = 0;
\r
115 /*-----------------------------------------------------------*/
\r
117 void * pvPortMalloc( size_t xWantedSize )
\r
119 BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;
\r
120 void * pvReturn = NULL;
\r
124 /* If this is the first call to malloc then the heap will require
\r
125 * initialisation to setup the list of free blocks. */
\r
126 if( pxEnd == NULL )
\r
132 mtCOVERAGE_TEST_MARKER();
\r
135 /* Check the requested block size is not so large that the top bit is
\r
136 * set. The top bit of the block size member of the BlockLink_t structure
\r
137 * is used to determine who owns the block - the application or the
\r
138 * kernel, so it must be free. */
\r
139 if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
\r
141 /* The wanted size must be increased so it can contain a BlockLink_t
\r
142 * structure in addition to the requested amount of bytes. */
\r
143 if( ( xWantedSize > 0 ) &&
\r
144 ( ( xWantedSize + xHeapStructSize ) > xWantedSize ) ) /* Overflow check */
\r
146 xWantedSize += xHeapStructSize;
\r
148 /* Ensure that blocks are always aligned. */
\r
149 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
\r
151 /* Byte alignment required. Check for overflow. */
\r
152 if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) ) )
\r
155 xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
\r
156 configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
\r
165 mtCOVERAGE_TEST_MARKER();
\r
173 if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
\r
175 /* Traverse the list from the start (lowest address) block until
\r
176 * one of adequate size is found. */
\r
177 pxPreviousBlock = &xStart;
\r
178 pxBlock = xStart.pxNextFreeBlock;
\r
180 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
\r
182 pxPreviousBlock = pxBlock;
\r
183 pxBlock = pxBlock->pxNextFreeBlock;
\r
186 /* If the end marker was reached then a block of adequate size
\r
187 * was not found. */
\r
188 if( pxBlock != pxEnd )
\r
190 /* Return the memory space pointed to - jumping over the
\r
191 * BlockLink_t structure at its start. */
\r
192 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
\r
194 /* This block is being returned for use so must be taken out
\r
195 * of the list of free blocks. */
\r
196 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
\r
198 /* If the block is larger than required it can be split into
\r
200 if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
\r
202 /* This block is to be split into two. Create a new
\r
203 * block following the number of bytes requested. The void
\r
204 * cast is used to prevent byte alignment warnings from the
\r
206 pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
\r
207 configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );
\r
209 /* Calculate the sizes of two blocks split from the
\r
211 pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
\r
212 pxBlock->xBlockSize = xWantedSize;
\r
214 /* Insert the new block into the list of free blocks. */
\r
215 prvInsertBlockIntoFreeList( pxNewBlockLink );
\r
219 mtCOVERAGE_TEST_MARKER();
\r
222 xFreeBytesRemaining -= pxBlock->xBlockSize;
\r
224 if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
\r
226 xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
\r
230 mtCOVERAGE_TEST_MARKER();
\r
233 /* The block is being returned - it is allocated and owned
\r
234 * by the application and has no "next" block. */
\r
235 pxBlock->xBlockSize |= xBlockAllocatedBit;
\r
236 pxBlock->pxNextFreeBlock = NULL;
\r
237 xNumberOfSuccessfulAllocations++;
\r
241 mtCOVERAGE_TEST_MARKER();
\r
246 mtCOVERAGE_TEST_MARKER();
\r
251 mtCOVERAGE_TEST_MARKER();
\r
254 traceMALLOC( pvReturn, xWantedSize );
\r
256 ( void ) xTaskResumeAll();
\r
258 #if ( configUSE_MALLOC_FAILED_HOOK == 1 )
\r
260 if( pvReturn == NULL )
\r
262 extern void vApplicationMallocFailedHook( void );
\r
263 vApplicationMallocFailedHook();
\r
267 mtCOVERAGE_TEST_MARKER();
\r
270 #endif /* if ( configUSE_MALLOC_FAILED_HOOK == 1 ) */
\r
272 configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
\r
275 /*-----------------------------------------------------------*/
\r
277 void vPortFree( void * pv )
\r
279 uint8_t * puc = ( uint8_t * ) pv;
\r
280 BlockLink_t * pxLink;
\r
284 /* The memory being freed will have an BlockLink_t structure immediately
\r
286 puc -= xHeapStructSize;
\r
288 /* This casting is to keep the compiler from issuing warnings. */
\r
289 pxLink = ( void * ) puc;
\r
291 /* Check the block is actually allocated. */
\r
292 configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
\r
293 configASSERT( pxLink->pxNextFreeBlock == NULL );
\r
295 if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
\r
297 if( pxLink->pxNextFreeBlock == NULL )
\r
299 /* The block is being returned to the heap - it is no longer
\r
301 pxLink->xBlockSize &= ~xBlockAllocatedBit;
\r
305 /* Add this block to the list of free blocks. */
\r
306 xFreeBytesRemaining += pxLink->xBlockSize;
\r
307 traceFREE( pv, pxLink->xBlockSize );
\r
308 prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
\r
309 xNumberOfSuccessfulFrees++;
\r
311 ( void ) xTaskResumeAll();
\r
315 mtCOVERAGE_TEST_MARKER();
\r
320 mtCOVERAGE_TEST_MARKER();
\r
324 /*-----------------------------------------------------------*/
\r
326 size_t xPortGetFreeHeapSize( void )
\r
328 return xFreeBytesRemaining;
\r
330 /*-----------------------------------------------------------*/
\r
332 size_t xPortGetMinimumEverFreeHeapSize( void )
\r
334 return xMinimumEverFreeBytesRemaining;
\r
336 /*-----------------------------------------------------------*/
\r
338 void vPortInitialiseBlocks( void )
\r
340 /* This just exists to keep the linker quiet. */
\r
342 /*-----------------------------------------------------------*/
\r
344 static void prvHeapInit( void ) /* PRIVILEGED_FUNCTION */
\r
346 BlockLink_t * pxFirstFreeBlock;
\r
347 uint8_t * pucAlignedHeap;
\r
349 size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
\r
351 /* Ensure the heap starts on a correctly aligned boundary. */
\r
352 uxAddress = ( size_t ) ucHeap;
\r
354 if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
\r
356 uxAddress += ( portBYTE_ALIGNMENT - 1 );
\r
357 uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
\r
358 xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
\r
361 pucAlignedHeap = ( uint8_t * ) uxAddress;
\r
363 /* xStart is used to hold a pointer to the first item in the list of free
\r
364 * blocks. The void cast is used to prevent compiler warnings. */
\r
365 xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
\r
366 xStart.xBlockSize = ( size_t ) 0;
\r
368 /* pxEnd is used to mark the end of the list of free blocks and is inserted
\r
369 * at the end of the heap space. */
\r
370 uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
\r
371 uxAddress -= xHeapStructSize;
\r
372 uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
\r
373 pxEnd = ( void * ) uxAddress;
\r
374 pxEnd->xBlockSize = 0;
\r
375 pxEnd->pxNextFreeBlock = NULL;
\r
377 /* To start with there is a single free block that is sized to take up the
\r
378 * entire heap space, minus the space taken by pxEnd. */
\r
379 pxFirstFreeBlock = ( void * ) pucAlignedHeap;
\r
380 pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
\r
381 pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
\r
383 /* Only one block exists - and it covers the entire usable heap space. */
\r
384 xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
\r
385 xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
\r
387 /* Work out the position of the top bit in a size_t variable. */
\r
388 xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
\r
390 /*-----------------------------------------------------------*/
\r
392 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) /* PRIVILEGED_FUNCTION */
\r
394 BlockLink_t * pxIterator;
\r
397 /* Iterate through the list until a block is found that has a higher address
\r
398 * than the block being inserted. */
\r
399 for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
\r
401 /* Nothing to do here, just iterate to the right position. */
\r
404 /* Do the block being inserted, and the block it is being inserted after
\r
405 * make a contiguous block of memory? */
\r
406 puc = ( uint8_t * ) pxIterator;
\r
408 if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
\r
410 pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
\r
411 pxBlockToInsert = pxIterator;
\r
415 mtCOVERAGE_TEST_MARKER();
\r
418 /* Do the block being inserted, and the block it is being inserted before
\r
419 * make a contiguous block of memory? */
\r
420 puc = ( uint8_t * ) pxBlockToInsert;
\r
422 if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
\r
424 if( pxIterator->pxNextFreeBlock != pxEnd )
\r
426 /* Form one big block from the two blocks. */
\r
427 pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
\r
428 pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
\r
432 pxBlockToInsert->pxNextFreeBlock = pxEnd;
\r
437 pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
\r
440 /* If the block being inserted plugged a gab, so was merged with the block
\r
441 * before and the block after, then it's pxNextFreeBlock pointer will have
\r
442 * already been set, and should not be set here as that would make it point
\r
444 if( pxIterator != pxBlockToInsert )
\r
446 pxIterator->pxNextFreeBlock = pxBlockToInsert;
\r
450 mtCOVERAGE_TEST_MARKER();
\r
453 /*-----------------------------------------------------------*/
\r
455 void vPortGetHeapStats( HeapStats_t * pxHeapStats )
\r
457 BlockLink_t * pxBlock;
\r
458 size_t xBlocks = 0, xMaxSize = 0, xMinSize = portMAX_DELAY; /* portMAX_DELAY used as a portable way of getting the maximum value. */
\r
462 pxBlock = xStart.pxNextFreeBlock;
\r
464 /* pxBlock will be NULL if the heap has not been initialised. The heap
\r
465 * is initialised automatically when the first allocation is made. */
\r
466 if( pxBlock != NULL )
\r
470 /* Increment the number of blocks and record the largest block seen
\r
474 if( pxBlock->xBlockSize > xMaxSize )
\r
476 xMaxSize = pxBlock->xBlockSize;
\r
479 if( pxBlock->xBlockSize < xMinSize )
\r
481 xMinSize = pxBlock->xBlockSize;
\r
484 /* Move to the next block in the chain until the last block is
\r
486 pxBlock = pxBlock->pxNextFreeBlock;
\r
487 } while( pxBlock != pxEnd );
\r
490 ( void ) xTaskResumeAll();
\r
492 pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;
\r
493 pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;
\r
494 pxHeapStats->xNumberOfFreeBlocks = xBlocks;
\r
496 taskENTER_CRITICAL();
\r
498 pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;
\r
499 pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;
\r
500 pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;
\r
501 pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;
\r
503 taskEXIT_CRITICAL();
\r