begriffs open source - freertos/blob - portable/MemMang/heap_2.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 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 https://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 \r
  65 /* The application writer has already defined the array used for the RTOS\r
  66 * heap - probably so it can be placed in a special segment or address. */\r
  67     extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
  68 #else\r
  69     static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
  70 #endif /* configAPPLICATION_ALLOCATED_HEAP */\r
  71 \r
  72 \r
  73 /* Define the linked list structure.  This is used to link free blocks in order\r
  74  * of their size. */\r
  75 typedef struct A_BLOCK_LINK\r
  76 {\r
  77     struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */\r
  78     size_t xBlockSize;                     /*<< The size of the free block. */\r
  79 } BlockLink_t;\r
  80 \r
  81 \r
  82 static const uint16_t heapSTRUCT_SIZE = ( ( sizeof( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );\r
  83 #define heapMINIMUM_BLOCK_SIZE    ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )\r
  84 \r
  85 /* Create a couple of list links to mark the start and end of the list. */\r
  86 static BlockLink_t xStart, xEnd;\r
  87 \r
  88 /* Keeps track of the number of free bytes remaining, but says nothing about\r
  89  * fragmentation. */\r
  90 static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;\r
  91 \r
  92 /* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */\r
  93 \r
  94 /*\r
  95  * Insert a block into the list of free blocks - which is ordered by size of\r
  96  * the block.  Small blocks at the start of the list and large blocks at the end\r
  97  * of the list.\r
  98  */\r
  99 #define prvInsertBlockIntoFreeList( pxBlockToInsert )                                                                               \\r
 100     {                                                                                                                               \\r
 101         BlockLink_t * pxIterator;                                                                                                   \\r
 102         size_t xBlockSize;                                                                                                          \\r
 103                                                                                                                                     \\r
 104         xBlockSize = pxBlockToInsert->xBlockSize;                                                                                   \\r
 105                                                                                                                                     \\r
 106         /* Iterate through the list until a block is found that has a larger size */                                                \\r
 107         /* than the block we are inserting. */                                                                                      \\r
 108         for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \\r
 109         {                                                                                                                           \\r
 110             /* There is nothing to do here - just iterate to the correct position. */                                               \\r
 111         }                                                                                                                           \\r
 112                                                                                                                                     \\r
 113         /* Update the list to include the block being inserted in the correct */                                                    \\r
 114         /* position. */                                                                                                             \\r
 115         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;                                                             \\r
 116         pxIterator->pxNextFreeBlock = pxBlockToInsert;                                                                              \\r
 117     }\r
 118 /*-----------------------------------------------------------*/\r
 119 \r
 120 void * pvPortMalloc( size_t xWantedSize )\r
 121 {\r
 122     BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;\r
 123     static BaseType_t xHeapHasBeenInitialised = pdFALSE;\r
 124     void * pvReturn = NULL;\r
 125 \r
 126     vTaskSuspendAll();\r
 127     {\r
 128         /* If this is the first call to malloc then the heap will require\r
 129          * initialisation to setup the list of free blocks. */\r
 130         if( xHeapHasBeenInitialised == pdFALSE )\r
 131         {\r
 132             prvHeapInit();\r
 133             xHeapHasBeenInitialised = pdTRUE;\r
 134         }\r
 135 \r
 136         /* The wanted size must be increased so it can contain a BlockLink_t\r
 137          * structure in addition to the requested amount of bytes. */\r
 138         if( ( xWantedSize > 0 ) &&\r
 139             ( ( xWantedSize + heapSTRUCT_SIZE ) >  xWantedSize ) ) /* Overflow check */\r
 140         {\r
 141             xWantedSize += heapSTRUCT_SIZE;\r
 142 \r
 143             /* Byte alignment required. Check for overflow. */\r
 144             if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) ) )\r
 145                     > xWantedSize )\r
 146             {\r
 147                 xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );\r
 148                 configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );\r
 149             }\r
 150             else\r
 151             {\r
 152                 xWantedSize = 0;\r
 153             }\r
 154         }\r
 155         else\r
 156         {\r
 157             xWantedSize = 0;\r
 158         }\r
 159 \r
 160 \r
 161         if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )\r
 162         {\r
 163             /* Blocks are stored in byte order - traverse the list from the start\r
 164              * (smallest) block until one of adequate size is found. */\r
 165             pxPreviousBlock = &xStart;\r
 166             pxBlock = xStart.pxNextFreeBlock;\r
 167 \r
 168             while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )\r
 169             {\r
 170                 pxPreviousBlock = pxBlock;\r
 171                 pxBlock = pxBlock->pxNextFreeBlock;\r
 172             }\r
 173 \r
 174             /* If we found the end marker then a block of adequate size was not found. */\r
 175             if( pxBlock != &xEnd )\r
 176             {\r
 177                 /* Return the memory space - jumping over the BlockLink_t structure\r
 178                  * at its start. */\r
 179                 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );\r
 180 \r
 181                 /* This block is being returned for use so must be taken out of the\r
 182                  * list of free blocks. */\r
 183                 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;\r
 184 \r
 185                 /* If the block is larger than required it can be split into two. */\r
 186                 if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )\r
 187                 {\r
 188                     /* This block is to be split into two.  Create a new block\r
 189                      * following the number of bytes requested. The void cast is\r
 190                      * used to prevent byte alignment warnings from the compiler. */\r
 191                     pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );\r
 192 \r
 193                     /* Calculate the sizes of two blocks split from the single\r
 194                      * block. */\r
 195                     pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;\r
 196                     pxBlock->xBlockSize = xWantedSize;\r
 197 \r
 198                     /* Insert the new block into the list of free blocks. */\r
 199                     prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );\r
 200                 }\r
 201 \r
 202                 xFreeBytesRemaining -= pxBlock->xBlockSize;\r
 203             }\r
 204         }\r
 205 \r
 206         traceMALLOC( pvReturn, xWantedSize );\r
 207     }\r
 208     ( void ) xTaskResumeAll();\r
 209 \r
 210     #if ( configUSE_MALLOC_FAILED_HOOK == 1 )\r
 211         {\r
 212             if( pvReturn == NULL )\r
 213             {\r
 214                 extern void vApplicationMallocFailedHook( void );\r
 215                 vApplicationMallocFailedHook();\r
 216             }\r
 217         }\r
 218     #endif\r
 219 \r
 220     return pvReturn;\r
 221 }\r
 222 /*-----------------------------------------------------------*/\r
 223 \r
 224 void vPortFree( void * pv )\r
 225 {\r
 226     uint8_t * puc = ( uint8_t * ) pv;\r
 227     BlockLink_t * pxLink;\r
 228 \r
 229     if( pv != NULL )\r
 230     {\r
 231         /* The memory being freed will have an BlockLink_t structure immediately\r
 232          * before it. */\r
 233         puc -= heapSTRUCT_SIZE;\r
 234 \r
 235         /* This unexpected casting is to keep some compilers from issuing\r
 236          * byte alignment warnings. */\r
 237         pxLink = ( void * ) puc;\r
 238 \r
 239         vTaskSuspendAll();\r
 240         {\r
 241             /* Add this block to the list of free blocks. */\r
 242             prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );\r
 243             xFreeBytesRemaining += pxLink->xBlockSize;\r
 244             traceFREE( pv, pxLink->xBlockSize );\r
 245         }\r
 246         ( void ) xTaskResumeAll();\r
 247     }\r
 248 }\r
 249 /*-----------------------------------------------------------*/\r
 250 \r
 251 size_t xPortGetFreeHeapSize( void )\r
 252 {\r
 253     return xFreeBytesRemaining;\r
 254 }\r
 255 /*-----------------------------------------------------------*/\r
 256 \r
 257 void vPortInitialiseBlocks( void )\r
 258 {\r
 259     /* This just exists to keep the linker quiet. */\r
 260 }\r
 261 /*-----------------------------------------------------------*/\r
 262 \r
 263 static void prvHeapInit( void )\r
 264 {\r
 265     BlockLink_t * pxFirstFreeBlock;\r
 266     uint8_t * pucAlignedHeap;\r
 267 \r
 268     /* Ensure the heap starts on a correctly aligned boundary. */\r
 269     pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) & ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );\r
 270 \r
 271     /* xStart is used to hold a pointer to the first item in the list of free\r
 272      * blocks.  The void cast is used to prevent compiler warnings. */\r
 273     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;\r
 274     xStart.xBlockSize = ( size_t ) 0;\r
 275 \r
 276     /* xEnd is used to mark the end of the list of free blocks. */\r
 277     xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;\r
 278     xEnd.pxNextFreeBlock = NULL;\r
 279 \r
 280     /* To start with there is a single free block that is sized to take up the\r
 281      * entire heap space. */\r
 282     pxFirstFreeBlock = ( void * ) pucAlignedHeap;\r
 283     pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;\r
 284     pxFirstFreeBlock->pxNextFreeBlock = &xEnd;\r
 285 }\r
 286 /*-----------------------------------------------------------*/\r