git.sur5r.net Git - freertos/blob - FreeRTOS/Source/portable/MemMang/heap_2.c

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