begriffs open source - freertos/blob - portable/MemMang/heap_2.c

   1 /*
   2  * FreeRTOS Kernel V11.1.0
   3  * Copyright (C) 2021 Amazon.com, Inc. or its affiliates. All Rights Reserved.
   4  *
   5  * SPDX-License-Identifier: MIT
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   8  * this software and associated documentation files (the "Software"), to deal in
   9  * the Software without restriction, including without limitation the rights to
  10  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
  11  * the Software, and to permit persons to whom the Software is furnished to do so,
  12  * subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in all
  15  * copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  19  * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
  20  * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  21  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  22  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23  *
  24  * https://www.FreeRTOS.org
  25  * https://github.com/FreeRTOS
  26  *
  27  */
  28
  29 /*
  30  * A sample implementation of pvPortMalloc() and vPortFree() that permits
  31  * allocated blocks to be freed, but does not combine adjacent free blocks
  32  * into a single larger block (and so will fragment memory).  See heap_4.c for
  33  * an equivalent that does combine adjacent blocks into single larger blocks.
  34  *
  35  * See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the
  36  * memory management pages of https://www.FreeRTOS.org for more information.
  37  */
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
  42  * all the API functions to use the MPU wrappers.  That should only be done when
  43  * task.h is included from an application file. */
  44 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
  45
  46 #include "FreeRTOS.h"
  47 #include "task.h"
  48
  49 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
  50
  51 #if ( configSUPPORT_DYNAMIC_ALLOCATION == 0 )
  52     #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
  53 #endif
  54
  55 #ifndef configHEAP_CLEAR_MEMORY_ON_FREE
  56     #define configHEAP_CLEAR_MEMORY_ON_FREE    0
  57 #endif
  58
  59 /* A few bytes might be lost to byte aligning the heap start address. */
  60 #define configADJUSTED_HEAP_SIZE    ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )
  61
  62 /* Assumes 8bit bytes! */
  63 #define heapBITS_PER_BYTE           ( ( size_t ) 8 )
  64
  65 /* Max value that fits in a size_t type. */
  66 #define heapSIZE_MAX                ( ~( ( size_t ) 0 ) )
  67
  68 /* Check if multiplying a and b will result in overflow. */
  69 #define heapMULTIPLY_WILL_OVERFLOW( a, b )    ( ( ( a ) > 0 ) && ( ( b ) > ( heapSIZE_MAX / ( a ) ) ) )
  70
  71 /* Check if adding a and b will result in overflow. */
  72 #define heapADD_WILL_OVERFLOW( a, b )         ( ( a ) > ( heapSIZE_MAX - ( b ) ) )
  73
  74 /* MSB of the xBlockSize member of an BlockLink_t structure is used to track
  75  * the allocation status of a block.  When MSB of the xBlockSize member of
  76  * an BlockLink_t structure is set then the block belongs to the application.
  77  * When the bit is free the block is still part of the free heap space. */
  78 #define heapBLOCK_ALLOCATED_BITMASK    ( ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 ) )
  79 #define heapBLOCK_SIZE_IS_VALID( xBlockSize )    ( ( ( xBlockSize ) & heapBLOCK_ALLOCATED_BITMASK ) == 0 )
  80 #define heapBLOCK_IS_ALLOCATED( pxBlock )        ( ( ( pxBlock->xBlockSize ) & heapBLOCK_ALLOCATED_BITMASK ) != 0 )
  81 #define heapALLOCATE_BLOCK( pxBlock )            ( ( pxBlock->xBlockSize ) |= heapBLOCK_ALLOCATED_BITMASK )
  82 #define heapFREE_BLOCK( pxBlock )                ( ( pxBlock->xBlockSize ) &= ~heapBLOCK_ALLOCATED_BITMASK )
  83
  84 /*-----------------------------------------------------------*/
  85
  86 /* Allocate the memory for the heap. */
  87 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )
  88
  89 /* The application writer has already defined the array used for the RTOS
  90 * heap - probably so it can be placed in a special segment or address. */
  91     extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
  92 #else
  93     PRIVILEGED_DATA static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
  94 #endif /* configAPPLICATION_ALLOCATED_HEAP */
  95
  96
  97 /* Define the linked list structure.  This is used to link free blocks in order
  98  * of their size. */
  99 typedef struct A_BLOCK_LINK
 100 {
 101     struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */
 102     size_t xBlockSize;                     /*<< The size of the free block. */
 103 } BlockLink_t;
 104
 105
 106 static const size_t xHeapStructSize = ( ( sizeof( BlockLink_t ) + ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK ) );
 107 #define heapMINIMUM_BLOCK_SIZE    ( ( size_t ) ( xHeapStructSize * 2 ) )
 108
 109 /* Create a couple of list links to mark the start and end of the list. */
 110 PRIVILEGED_DATA static BlockLink_t xStart, xEnd;
 111
 112 /* Keeps track of the number of free bytes remaining, but says nothing about
 113  * fragmentation. */
 114 PRIVILEGED_DATA static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;
 115
 116 /* Indicates whether the heap has been initialised or not. */
 117 PRIVILEGED_DATA static BaseType_t xHeapHasBeenInitialised = pdFALSE;
 118
 119 /*-----------------------------------------------------------*/
 120
 121 /*
 122  * Initialises the heap structures before their first use.
 123  */
 124 static void prvHeapInit( void ) PRIVILEGED_FUNCTION;
 125
 126 /*-----------------------------------------------------------*/
 127
 128 /* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */
 129
 130 /*
 131  * Insert a block into the list of free blocks - which is ordered by size of
 132  * the block.  Small blocks at the start of the list and large blocks at the end
 133  * of the list.
 134  */
 135 #define prvInsertBlockIntoFreeList( pxBlockToInsert )                                                                               \
 136     {                                                                                                                               \
 137         BlockLink_t * pxIterator;                                                                                                   \
 138         size_t xBlockSize;                                                                                                          \
 139                                                                                                                                     \
 140         xBlockSize = pxBlockToInsert->xBlockSize;                                                                                   \
 141                                                                                                                                     \
 142         /* Iterate through the list until a block is found that has a larger size */                                                \
 143         /* than the block we are inserting. */                                                                                      \
 144         for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
 145         {                                                                                                                           \
 146             /* There is nothing to do here - just iterate to the correct position. */                                               \
 147         }                                                                                                                           \
 148                                                                                                                                     \
 149         /* Update the list to include the block being inserted in the correct */                                                    \
 150         /* position. */                                                                                                             \
 151         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;                                                             \
 152         pxIterator->pxNextFreeBlock = pxBlockToInsert;                                                                              \
 153     }
 154 /*-----------------------------------------------------------*/
 155
 156 void * pvPortMalloc( size_t xWantedSize )
 157 {
 158     BlockLink_t * pxBlock;
 159     BlockLink_t * pxPreviousBlock;
 160     BlockLink_t * pxNewBlockLink;
 161     void * pvReturn = NULL;
 162     size_t xAdditionalRequiredSize;
 163
 164     if( xWantedSize > 0 )
 165     {
 166         /* The wanted size must be increased so it can contain a BlockLink_t
 167          * structure in addition to the requested amount of bytes. */
 168         if( heapADD_WILL_OVERFLOW( xWantedSize, xHeapStructSize ) == 0 )
 169         {
 170             xWantedSize += xHeapStructSize;
 171
 172             /* Ensure that blocks are always aligned to the required number
 173              * of bytes. */
 174             if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
 175             {
 176                 /* Byte alignment required. */
 177                 xAdditionalRequiredSize = portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK );
 178
 179                 if( heapADD_WILL_OVERFLOW( xWantedSize, xAdditionalRequiredSize ) == 0 )
 180                 {
 181                     xWantedSize += xAdditionalRequiredSize;
 182                 }
 183                 else
 184                 {
 185                     xWantedSize = 0;
 186                 }
 187             }
 188             else
 189             {
 190                 mtCOVERAGE_TEST_MARKER();
 191             }
 192         }
 193         else
 194         {
 195             xWantedSize = 0;
 196         }
 197     }
 198     else
 199     {
 200         mtCOVERAGE_TEST_MARKER();
 201     }
 202
 203     vTaskSuspendAll();
 204     {
 205         /* If this is the first call to malloc then the heap will require
 206          * initialisation to setup the list of free blocks. */
 207         if( xHeapHasBeenInitialised == pdFALSE )
 208         {
 209             prvHeapInit();
 210             xHeapHasBeenInitialised = pdTRUE;
 211         }
 212
 213         /* Check the block size we are trying to allocate is not so large that the
 214          * top bit is set.  The top bit of the block size member of the BlockLink_t
 215          * structure is used to determine who owns the block - the application or
 216          * the kernel, so it must be free. */
 217         if( heapBLOCK_SIZE_IS_VALID( xWantedSize ) != 0 )
 218         {
 219             if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
 220             {
 221                 /* Blocks are stored in byte order - traverse the list from the start
 222                  * (smallest) block until one of adequate size is found. */
 223                 pxPreviousBlock = &xStart;
 224                 pxBlock = xStart.pxNextFreeBlock;
 225
 226                 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
 227                 {
 228                     pxPreviousBlock = pxBlock;
 229                     pxBlock = pxBlock->pxNextFreeBlock;
 230                 }
 231
 232                 /* If we found the end marker then a block of adequate size was not found. */
 233                 if( pxBlock != &xEnd )
 234                 {
 235                     /* Return the memory space - jumping over the BlockLink_t structure
 236                      * at its start. */
 237                     pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
 238
 239                     /* This block is being returned for use so must be taken out of the
 240                      * list of free blocks. */
 241                     pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
 242
 243                     /* If the block is larger than required it can be split into two. */
 244                     if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
 245                     {
 246                         /* This block is to be split into two.  Create a new block
 247                          * following the number of bytes requested. The void cast is
 248                          * used to prevent byte alignment warnings from the compiler. */
 249                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
 250
 251                         /* Calculate the sizes of two blocks split from the single
 252                          * block. */
 253                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
 254                         pxBlock->xBlockSize = xWantedSize;
 255
 256                         /* Insert the new block into the list of free blocks.
 257                          * The list of free blocks is sorted by their size, we have to
 258                          * iterate to find the right place to insert new block. */
 259                         prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
 260                     }
 261
 262                     xFreeBytesRemaining -= pxBlock->xBlockSize;
 263
 264                     /* The block is being returned - it is allocated and owned
 265                      * by the application and has no "next" block. */
 266                     heapALLOCATE_BLOCK( pxBlock );
 267                     pxBlock->pxNextFreeBlock = NULL;
 268                 }
 269             }
 270         }
 271
 272         traceMALLOC( pvReturn, xWantedSize );
 273     }
 274     ( void ) xTaskResumeAll();
 275
 276     #if ( configUSE_MALLOC_FAILED_HOOK == 1 )
 277     {
 278         if( pvReturn == NULL )
 279         {
 280             vApplicationMallocFailedHook();
 281         }
 282     }
 283     #endif
 284
 285     return pvReturn;
 286 }
 287 /*-----------------------------------------------------------*/
 288
 289 void vPortFree( void * pv )
 290 {
 291     uint8_t * puc = ( uint8_t * ) pv;
 292     BlockLink_t * pxLink;
 293
 294     if( pv != NULL )
 295     {
 296         /* The memory being freed will have an BlockLink_t structure immediately
 297          * before it. */
 298         puc -= xHeapStructSize;
 299
 300         /* This unexpected casting is to keep some compilers from issuing
 301          * byte alignment warnings. */
 302         pxLink = ( void * ) puc;
 303
 304         configASSERT( heapBLOCK_IS_ALLOCATED( pxLink ) != 0 );
 305         configASSERT( pxLink->pxNextFreeBlock == NULL );
 306
 307         if( heapBLOCK_IS_ALLOCATED( pxLink ) != 0 )
 308         {
 309             if( pxLink->pxNextFreeBlock == NULL )
 310             {
 311                 /* The block is being returned to the heap - it is no longer
 312                  * allocated. */
 313                 heapFREE_BLOCK( pxLink );
 314                 #if ( configHEAP_CLEAR_MEMORY_ON_FREE == 1 )
 315                 {
 316                     ( void ) memset( puc + xHeapStructSize, 0, pxLink->xBlockSize - xHeapStructSize );
 317                 }
 318                 #endif
 319
 320                 vTaskSuspendAll();
 321                 {
 322                     /* Add this block to the list of free blocks. */
 323                     prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
 324                     xFreeBytesRemaining += pxLink->xBlockSize;
 325                     traceFREE( pv, pxLink->xBlockSize );
 326                 }
 327                 ( void ) xTaskResumeAll();
 328             }
 329         }
 330     }
 331 }
 332 /*-----------------------------------------------------------*/
 333
 334 size_t xPortGetFreeHeapSize( void )
 335 {
 336     return xFreeBytesRemaining;
 337 }
 338 /*-----------------------------------------------------------*/
 339
 340 void vPortInitialiseBlocks( void )
 341 {
 342     /* This just exists to keep the linker quiet. */
 343 }
 344 /*-----------------------------------------------------------*/
 345
 346 void * pvPortCalloc( size_t xNum,
 347                      size_t xSize )
 348 {
 349     void * pv = NULL;
 350
 351     if( heapMULTIPLY_WILL_OVERFLOW( xNum, xSize ) == 0 )
 352     {
 353         pv = pvPortMalloc( xNum * xSize );
 354
 355         if( pv != NULL )
 356         {
 357             ( void ) memset( pv, 0, xNum * xSize );
 358         }
 359     }
 360
 361     return pv;
 362 }
 363 /*-----------------------------------------------------------*/
 364
 365 static void prvHeapInit( void ) /* PRIVILEGED_FUNCTION */
 366 {
 367     BlockLink_t * pxFirstFreeBlock;
 368     uint8_t * pucAlignedHeap;
 369
 370     /* Ensure the heap starts on a correctly aligned boundary. */
 371     pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) & ucHeap[ portBYTE_ALIGNMENT - 1 ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
 372
 373     /* xStart is used to hold a pointer to the first item in the list of free
 374      * blocks.  The void cast is used to prevent compiler warnings. */
 375     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
 376     xStart.xBlockSize = ( size_t ) 0;
 377
 378     /* xEnd is used to mark the end of the list of free blocks. */
 379     xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
 380     xEnd.pxNextFreeBlock = NULL;
 381
 382     /* To start with there is a single free block that is sized to take up the
 383      * entire heap space. */
 384     pxFirstFreeBlock = ( BlockLink_t * ) pucAlignedHeap;
 385     pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
 386     pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
 387 }
 388 /*-----------------------------------------------------------*/
 389
 390 /*
 391  * Reset the state in this file. This state is normally initialized at start up.
 392  * This function must be called by the application before restarting the
 393  * scheduler.
 394  */
 395 void vPortHeapResetState( void )
 396 {
 397     xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;
 398
 399     xHeapHasBeenInitialised = pdFALSE;
 400 }
 401 /*-----------------------------------------------------------*/