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

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