]> begriffs open source - freertos/blob - portable/MemMang/heap_4.c
Add SPDX-License-Identifier: MIT to MIT licensed files.
[freertos] / portable / MemMang / heap_4.c
1 /*\r
2  * FreeRTOS Kernel <DEVELOPMENT BRANCH>\r
3  * Copyright (C) 2021 Amazon.com, Inc. or its affiliates.  All Rights Reserved.\r
4  *\r
5  * SPDX-License-Identifier: MIT
6  *
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
13  *\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
16  *\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
23  *\r
24  * https://www.FreeRTOS.org\r
25  * https://github.com/FreeRTOS\r
26  *\r
27  */\r
28 \r
29 /*\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
33  *\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
36  */\r
37 #include <stdlib.h>\r
38 \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
43 \r
44 #include "FreeRTOS.h"\r
45 #include "task.h"\r
46 \r
47 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
48 \r
49 #if ( configSUPPORT_DYNAMIC_ALLOCATION == 0 )\r
50     #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0\r
51 #endif\r
52 \r
53 /* Block sizes must not get too small. */\r
54 #define heapMINIMUM_BLOCK_SIZE    ( ( size_t ) ( xHeapStructSize << 1 ) )\r
55 \r
56 /* Assumes 8bit bytes! */\r
57 #define heapBITS_PER_BYTE         ( ( size_t ) 8 )\r
58 \r
59 /* Allocate the memory for the heap. */\r
60 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )\r
61 \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
65 #else\r
66     PRIVILEGED_DATA static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
67 #endif /* configAPPLICATION_ALLOCATED_HEAP */\r
68 \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
72 {\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
75 } BlockLink_t;\r
76 \r
77 /*-----------------------------------------------------------*/\r
78 \r
79 /*\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
84  */\r
85 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) PRIVILEGED_FUNCTION;\r
86 \r
87 /*\r
88  * Called automatically to setup the required heap structures the first time\r
89  * pvPortMalloc() is called.\r
90  */\r
91 static void prvHeapInit( void ) PRIVILEGED_FUNCTION;\r
92 \r
93 /*-----------------------------------------------------------*/\r
94 \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
98 \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
101 \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
108 \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
112  * space. */\r
113 PRIVILEGED_DATA static size_t xBlockAllocatedBit = 0;\r
114 \r
115 /*-----------------------------------------------------------*/\r
116 \r
117 void * pvPortMalloc( size_t xWantedSize )\r
118 {\r
119     BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;\r
120     void * pvReturn = NULL;\r
121 \r
122     vTaskSuspendAll();\r
123     {\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
127         {\r
128             prvHeapInit();\r
129         }\r
130         else\r
131         {\r
132             mtCOVERAGE_TEST_MARKER();\r
133         }\r
134 \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
140         {\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
145             {\r
146                 xWantedSize += xHeapStructSize;\r
147 \r
148                 /* Ensure that blocks are always aligned. */\r
149                 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )\r
150                 {\r
151                     /* Byte alignment required. Check for overflow. */\r
152                     if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) ) )\r
153                             > xWantedSize )\r
154                     {\r
155                         xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );\r
156                         configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );\r
157                     }\r
158                     else\r
159                     {\r
160                         xWantedSize = 0;\r
161                     }\r
162                 }\r
163                 else\r
164                 {\r
165                     mtCOVERAGE_TEST_MARKER();\r
166                 }\r
167             }\r
168             else\r
169             {\r
170                 xWantedSize = 0;\r
171             }\r
172 \r
173             if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )\r
174             {\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
179 \r
180                 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )\r
181                 {\r
182                     pxPreviousBlock = pxBlock;\r
183                     pxBlock = pxBlock->pxNextFreeBlock;\r
184                 }\r
185 \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
189                 {\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
193 \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
197 \r
198                     /* If the block is larger than required it can be split into\r
199                      * two. */\r
200                     if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )\r
201                     {\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
205                          * compiler. */\r
206                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );\r
207                         configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );\r
208 \r
209                         /* Calculate the sizes of two blocks split from the\r
210                          * single block. */\r
211                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;\r
212                         pxBlock->xBlockSize = xWantedSize;\r
213 \r
214                         /* Insert the new block into the list of free blocks. */\r
215                         prvInsertBlockIntoFreeList( pxNewBlockLink );\r
216                     }\r
217                     else\r
218                     {\r
219                         mtCOVERAGE_TEST_MARKER();\r
220                     }\r
221 \r
222                     xFreeBytesRemaining -= pxBlock->xBlockSize;\r
223 \r
224                     if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )\r
225                     {\r
226                         xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;\r
227                     }\r
228                     else\r
229                     {\r
230                         mtCOVERAGE_TEST_MARKER();\r
231                     }\r
232 \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
238                 }\r
239                 else\r
240                 {\r
241                     mtCOVERAGE_TEST_MARKER();\r
242                 }\r
243             }\r
244             else\r
245             {\r
246                 mtCOVERAGE_TEST_MARKER();\r
247             }\r
248         }\r
249         else\r
250         {\r
251             mtCOVERAGE_TEST_MARKER();\r
252         }\r
253 \r
254         traceMALLOC( pvReturn, xWantedSize );\r
255     }\r
256     ( void ) xTaskResumeAll();\r
257 \r
258     #if ( configUSE_MALLOC_FAILED_HOOK == 1 )\r
259         {\r
260             if( pvReturn == NULL )\r
261             {\r
262                 extern void vApplicationMallocFailedHook( void );\r
263                 vApplicationMallocFailedHook();\r
264             }\r
265             else\r
266             {\r
267                 mtCOVERAGE_TEST_MARKER();\r
268             }\r
269         }\r
270     #endif /* if ( configUSE_MALLOC_FAILED_HOOK == 1 ) */\r
271 \r
272     configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );\r
273     return pvReturn;\r
274 }\r
275 /*-----------------------------------------------------------*/\r
276 \r
277 void vPortFree( void * pv )\r
278 {\r
279     uint8_t * puc = ( uint8_t * ) pv;\r
280     BlockLink_t * pxLink;\r
281 \r
282     if( pv != NULL )\r
283     {\r
284         /* The memory being freed will have an BlockLink_t structure immediately\r
285          * before it. */\r
286         puc -= xHeapStructSize;\r
287 \r
288         /* This casting is to keep the compiler from issuing warnings. */\r
289         pxLink = ( void * ) puc;\r
290 \r
291         /* Check the block is actually allocated. */\r
292         configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );\r
293         configASSERT( pxLink->pxNextFreeBlock == NULL );\r
294 \r
295         if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )\r
296         {\r
297             if( pxLink->pxNextFreeBlock == NULL )\r
298             {\r
299                 /* The block is being returned to the heap - it is no longer\r
300                  * allocated. */\r
301                 pxLink->xBlockSize &= ~xBlockAllocatedBit;\r
302 \r
303                 vTaskSuspendAll();\r
304                 {\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
310                 }\r
311                 ( void ) xTaskResumeAll();\r
312             }\r
313             else\r
314             {\r
315                 mtCOVERAGE_TEST_MARKER();\r
316             }\r
317         }\r
318         else\r
319         {\r
320             mtCOVERAGE_TEST_MARKER();\r
321         }\r
322     }\r
323 }\r
324 /*-----------------------------------------------------------*/\r
325 \r
326 size_t xPortGetFreeHeapSize( void )\r
327 {\r
328     return xFreeBytesRemaining;\r
329 }\r
330 /*-----------------------------------------------------------*/\r
331 \r
332 size_t xPortGetMinimumEverFreeHeapSize( void )\r
333 {\r
334     return xMinimumEverFreeBytesRemaining;\r
335 }\r
336 /*-----------------------------------------------------------*/\r
337 \r
338 void vPortInitialiseBlocks( void )\r
339 {\r
340     /* This just exists to keep the linker quiet. */\r
341 }\r
342 /*-----------------------------------------------------------*/\r
343 \r
344 static void prvHeapInit( void ) /* PRIVILEGED_FUNCTION */\r
345 {\r
346     BlockLink_t * pxFirstFreeBlock;\r
347     uint8_t * pucAlignedHeap;\r
348     size_t uxAddress;\r
349     size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;\r
350 \r
351     /* Ensure the heap starts on a correctly aligned boundary. */\r
352     uxAddress = ( size_t ) ucHeap;\r
353 \r
354     if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )\r
355     {\r
356         uxAddress += ( portBYTE_ALIGNMENT - 1 );\r
357         uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
358         xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;\r
359     }\r
360 \r
361     pucAlignedHeap = ( uint8_t * ) uxAddress;\r
362 \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
367 \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
376 \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
382 \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
386 \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
389 }\r
390 /*-----------------------------------------------------------*/\r
391 \r
392 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) /* PRIVILEGED_FUNCTION */\r
393 {\r
394     BlockLink_t * pxIterator;\r
395     uint8_t * puc;\r
396 \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
400     {\r
401         /* Nothing to do here, just iterate to the right position. */\r
402     }\r
403 \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
407 \r
408     if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )\r
409     {\r
410         pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;\r
411         pxBlockToInsert = pxIterator;\r
412     }\r
413     else\r
414     {\r
415         mtCOVERAGE_TEST_MARKER();\r
416     }\r
417 \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
421 \r
422     if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )\r
423     {\r
424         if( pxIterator->pxNextFreeBlock != pxEnd )\r
425         {\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
429         }\r
430         else\r
431         {\r
432             pxBlockToInsert->pxNextFreeBlock = pxEnd;\r
433         }\r
434     }\r
435     else\r
436     {\r
437         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;\r
438     }\r
439 \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
443      * to itself. */\r
444     if( pxIterator != pxBlockToInsert )\r
445     {\r
446         pxIterator->pxNextFreeBlock = pxBlockToInsert;\r
447     }\r
448     else\r
449     {\r
450         mtCOVERAGE_TEST_MARKER();\r
451     }\r
452 }\r
453 /*-----------------------------------------------------------*/\r
454 \r
455 void vPortGetHeapStats( HeapStats_t * pxHeapStats )\r
456 {\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
459 \r
460     vTaskSuspendAll();\r
461     {\r
462         pxBlock = xStart.pxNextFreeBlock;\r
463 \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
467         {\r
468             do\r
469             {\r
470                 /* Increment the number of blocks and record the largest block seen\r
471                  * so far. */\r
472                 xBlocks++;\r
473 \r
474                 if( pxBlock->xBlockSize > xMaxSize )\r
475                 {\r
476                     xMaxSize = pxBlock->xBlockSize;\r
477                 }\r
478 \r
479                 if( pxBlock->xBlockSize < xMinSize )\r
480                 {\r
481                     xMinSize = pxBlock->xBlockSize;\r
482                 }\r
483 \r
484                 /* Move to the next block in the chain until the last block is\r
485                  * reached. */\r
486                 pxBlock = pxBlock->pxNextFreeBlock;\r
487             } while( pxBlock != pxEnd );\r
488         }\r
489     }\r
490     ( void ) xTaskResumeAll();\r
491 \r
492     pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;\r
493     pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;\r
494     pxHeapStats->xNumberOfFreeBlocks = xBlocks;\r
495 \r
496     taskENTER_CRITICAL();\r
497     {\r
498         pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;\r
499         pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;\r
500         pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;\r
501         pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;\r
502     }\r
503     taskEXIT_CRITICAL();\r
504 }\r