begriffs open source - freertos/blob - portable/GCC/ARM_CM55/secure/secure_heap.c

   1 /*
   2  * FreeRTOS Kernel <DEVELOPMENT BRANCH>
   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 /* Standard includes. */
  30 #include <stdint.h>
  31
  32 /* Secure context heap includes. */
  33 #include "secure_heap.h"
  34
  35 /* Secure port macros. */
  36 #include "secure_port_macros.h"
  37
  38 /**
  39  * @brief Total heap size.
  40  */
  41 #ifndef secureconfigTOTAL_HEAP_SIZE
  42     #define secureconfigTOTAL_HEAP_SIZE    ( ( ( size_t ) ( 10 * 1024 ) ) )
  43 #endif
  44
  45 /* No test marker by default. */
  46 #ifndef mtCOVERAGE_TEST_MARKER
  47     #define mtCOVERAGE_TEST_MARKER()
  48 #endif
  49
  50 /* No tracing by default. */
  51 #ifndef traceMALLOC
  52     #define traceMALLOC( pvReturn, xWantedSize )
  53 #endif
  54
  55 /* No tracing by default. */
  56 #ifndef traceFREE
  57     #define traceFREE( pv, xBlockSize )
  58 #endif
  59
  60 /* Block sizes must not get too small. */
  61 #define secureheapMINIMUM_BLOCK_SIZE    ( ( size_t ) ( xHeapStructSize << 1 ) )
  62
  63 /* Assumes 8bit bytes! */
  64 #define secureheapBITS_PER_BYTE         ( ( size_t ) 8 )
  65
  66 /* Max value that fits in a size_t type. */
  67 #define secureheapSIZE_MAX              ( ~( ( size_t ) 0 ) )
  68
  69 /* Check if adding a and b will result in overflow. */
  70 #define secureheapADD_WILL_OVERFLOW( a, b )         ( ( a ) > ( secureheapSIZE_MAX - ( b ) ) )
  71
  72 /* MSB of the xBlockSize member of an BlockLink_t structure is used to track
  73  * the allocation status of a block.  When MSB of the xBlockSize member of
  74  * an BlockLink_t structure is set then the block belongs to the application.
  75  * When the bit is free the block is still part of the free heap space. */
  76 #define secureheapBLOCK_ALLOCATED_BITMASK    ( ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * secureheapBITS_PER_BYTE ) - 1 ) )
  77 #define secureheapBLOCK_SIZE_IS_VALID( xBlockSize )    ( ( ( xBlockSize ) & secureheapBLOCK_ALLOCATED_BITMASK ) == 0 )
  78 #define secureheapBLOCK_IS_ALLOCATED( pxBlock )        ( ( ( pxBlock->xBlockSize ) & secureheapBLOCK_ALLOCATED_BITMASK ) != 0 )
  79 #define secureheapALLOCATE_BLOCK( pxBlock )            ( ( pxBlock->xBlockSize ) |= secureheapBLOCK_ALLOCATED_BITMASK )
  80 #define secureheapFREE_BLOCK( pxBlock )                ( ( pxBlock->xBlockSize ) &= ~secureheapBLOCK_ALLOCATED_BITMASK )
  81 /*-----------------------------------------------------------*/
  82
  83 /* Allocate the memory for the heap. */
  84 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )
  85
  86 /* The application writer has already defined the array used for the RTOS
  87 * heap - probably so it can be placed in a special segment or address. */
  88     extern uint8_t ucHeap[ secureconfigTOTAL_HEAP_SIZE ];
  89 #else /* configAPPLICATION_ALLOCATED_HEAP */
  90     static uint8_t ucHeap[ secureconfigTOTAL_HEAP_SIZE ];
  91 #endif /* configAPPLICATION_ALLOCATED_HEAP */
  92
  93 /**
  94  * @brief The linked list structure.
  95  *
  96  * This is used to link free blocks in order of their memory address.
  97  */
  98 typedef struct A_BLOCK_LINK
  99 {
 100     struct A_BLOCK_LINK * pxNextFreeBlock; /**< The next free block in the list. */
 101     size_t xBlockSize;                     /**< The size of the free block. */
 102 } BlockLink_t;
 103 /*-----------------------------------------------------------*/
 104
 105 /**
 106  * @brief Called automatically to setup the required heap structures the first
 107  * time pvPortMalloc() is called.
 108  */
 109 static void prvHeapInit( void );
 110
 111 /**
 112  * @brief Inserts a block of memory that is being freed into the correct
 113  * position in the list of free memory blocks.
 114  *
 115  * The block being freed will be merged with the block in front it and/or the
 116  * block behind it if the memory blocks are adjacent to each other.
 117  *
 118  * @param[in] pxBlockToInsert The block being freed.
 119  */
 120 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert );
 121 /*-----------------------------------------------------------*/
 122
 123 /**
 124  * @brief The size of the structure placed at the beginning of each allocated
 125  * memory block must by correctly byte aligned.
 126  */
 127 static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( secureportBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) secureportBYTE_ALIGNMENT_MASK );
 128
 129 /**
 130  * @brief Create a couple of list links to mark the start and end of the list.
 131  */
 132 static BlockLink_t xStart;
 133 static BlockLink_t * pxEnd = NULL;
 134
 135 /**
 136  * @brief Keeps track of the number of free bytes remaining, but says nothing
 137  * about fragmentation.
 138  */
 139 static size_t xFreeBytesRemaining = 0U;
 140 static size_t xMinimumEverFreeBytesRemaining = 0U;
 141
 142 /*-----------------------------------------------------------*/
 143
 144 static void prvHeapInit( void )
 145 {
 146     BlockLink_t * pxFirstFreeBlock;
 147     uint8_t * pucAlignedHeap;
 148     size_t uxAddress;
 149     size_t xTotalHeapSize = secureconfigTOTAL_HEAP_SIZE;
 150
 151     /* Ensure the heap starts on a correctly aligned boundary. */
 152     uxAddress = ( size_t ) ucHeap;
 153
 154     if( ( uxAddress & secureportBYTE_ALIGNMENT_MASK ) != 0 )
 155     {
 156         uxAddress += ( secureportBYTE_ALIGNMENT - 1 );
 157         uxAddress &= ~( ( size_t ) secureportBYTE_ALIGNMENT_MASK );
 158         xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
 159     }
 160
 161     pucAlignedHeap = ( uint8_t * ) uxAddress;
 162
 163     /* xStart is used to hold a pointer to the first item in the list of free
 164      * blocks.  The void cast is used to prevent compiler warnings. */
 165     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
 166     xStart.xBlockSize = ( size_t ) 0;
 167
 168     /* pxEnd is used to mark the end of the list of free blocks and is inserted
 169      * at the end of the heap space. */
 170     uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
 171     uxAddress -= xHeapStructSize;
 172     uxAddress &= ~( ( size_t ) secureportBYTE_ALIGNMENT_MASK );
 173     pxEnd = ( void * ) uxAddress;
 174     pxEnd->xBlockSize = 0;
 175     pxEnd->pxNextFreeBlock = NULL;
 176
 177     /* To start with there is a single free block that is sized to take up the
 178      * entire heap space, minus the space taken by pxEnd. */
 179     pxFirstFreeBlock = ( void * ) pucAlignedHeap;
 180     pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
 181     pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
 182
 183     /* Only one block exists - and it covers the entire usable heap space. */
 184     xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
 185     xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
 186 }
 187 /*-----------------------------------------------------------*/
 188
 189 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert )
 190 {
 191     BlockLink_t * pxIterator;
 192     uint8_t * puc;
 193
 194     /* Iterate through the list until a block is found that has a higher address
 195      * than the block being inserted. */
 196     for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
 197     {
 198         /* Nothing to do here, just iterate to the right position. */
 199     }
 200
 201     /* Do the block being inserted, and the block it is being inserted after
 202      * make a contiguous block of memory? */
 203     puc = ( uint8_t * ) pxIterator;
 204
 205     if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
 206     {
 207         pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
 208         pxBlockToInsert = pxIterator;
 209     }
 210     else
 211     {
 212         mtCOVERAGE_TEST_MARKER();
 213     }
 214
 215     /* Do the block being inserted, and the block it is being inserted before
 216      * make a contiguous block of memory? */
 217     puc = ( uint8_t * ) pxBlockToInsert;
 218
 219     if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
 220     {
 221         if( pxIterator->pxNextFreeBlock != pxEnd )
 222         {
 223             /* Form one big block from the two blocks. */
 224             pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
 225             pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
 226         }
 227         else
 228         {
 229             pxBlockToInsert->pxNextFreeBlock = pxEnd;
 230         }
 231     }
 232     else
 233     {
 234         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
 235     }
 236
 237     /* If the block being inserted plugged a gab, so was merged with the block
 238      * before and the block after, then it's pxNextFreeBlock pointer will have
 239      * already been set, and should not be set here as that would make it point
 240      * to itself. */
 241     if( pxIterator != pxBlockToInsert )
 242     {
 243         pxIterator->pxNextFreeBlock = pxBlockToInsert;
 244     }
 245     else
 246     {
 247         mtCOVERAGE_TEST_MARKER();
 248     }
 249 }
 250 /*-----------------------------------------------------------*/
 251
 252 void * pvPortMalloc( size_t xWantedSize )
 253 {
 254     BlockLink_t * pxBlock;
 255     BlockLink_t * pxPreviousBlock;
 256     BlockLink_t * pxNewBlockLink;
 257     void * pvReturn = NULL;
 258     size_t xAdditionalRequiredSize;
 259
 260     /* If this is the first call to malloc then the heap will require
 261      * initialisation to setup the list of free blocks. */
 262     if( pxEnd == NULL )
 263     {
 264         prvHeapInit();
 265     }
 266     else
 267     {
 268         mtCOVERAGE_TEST_MARKER();
 269     }
 270
 271     if( xWantedSize > 0 )
 272     {
 273         /* The wanted size must be increased so it can contain a BlockLink_t
 274          * structure in addition to the requested amount of bytes. */
 275         if( secureheapADD_WILL_OVERFLOW( xWantedSize, xHeapStructSize ) == 0 )
 276         {
 277             xWantedSize += xHeapStructSize;
 278
 279             /* Ensure that blocks are always aligned to the required number
 280              * of bytes. */
 281             if( ( xWantedSize & secureportBYTE_ALIGNMENT_MASK ) != 0x00 )
 282             {
 283                 /* Byte alignment required. */
 284                 xAdditionalRequiredSize = secureportBYTE_ALIGNMENT - ( xWantedSize & secureportBYTE_ALIGNMENT_MASK );
 285
 286                 if( secureheapADD_WILL_OVERFLOW( xWantedSize, xAdditionalRequiredSize ) == 0 )
 287                 {
 288                     xWantedSize += xAdditionalRequiredSize;
 289                 }
 290                 else
 291                 {
 292                     xWantedSize = 0;
 293                 }
 294             }
 295             else
 296             {
 297                 mtCOVERAGE_TEST_MARKER();
 298             }
 299         }
 300         else
 301         {
 302             xWantedSize = 0;
 303         }
 304     }
 305     else
 306     {
 307         mtCOVERAGE_TEST_MARKER();
 308     }
 309
 310     /* Check the requested block size is not so large that the top bit is set.
 311      * The top bit of the block size member of the BlockLink_t structure is used
 312      * to determine who owns the block - the application or the kernel, so it
 313      * must be free. */
 314     if( secureheapBLOCK_SIZE_IS_VALID( xWantedSize ) != 0 )
 315     {
 316         if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
 317         {
 318             /* Traverse the list from the start (lowest address) block until
 319              * one of adequate size is found. */
 320             pxPreviousBlock = &xStart;
 321             pxBlock = xStart.pxNextFreeBlock;
 322
 323             while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
 324             {
 325                 pxPreviousBlock = pxBlock;
 326                 pxBlock = pxBlock->pxNextFreeBlock;
 327             }
 328
 329             /* If the end marker was reached then a block of adequate size was
 330              * not found. */
 331             if( pxBlock != pxEnd )
 332             {
 333                 /* Return the memory space pointed to - jumping over the
 334                  * BlockLink_t structure at its start. */
 335                 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
 336
 337                 /* This block is being returned for use so must be taken out
 338                  * of the list of free blocks. */
 339                 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
 340
 341                 /* If the block is larger than required it can be split into
 342                  * two. */
 343                 if( ( pxBlock->xBlockSize - xWantedSize ) > secureheapMINIMUM_BLOCK_SIZE )
 344                 {
 345                     /* This block is to be split into two.  Create a new
 346                      * block following the number of bytes requested. The void
 347                      * cast is used to prevent byte alignment warnings from the
 348                      * compiler. */
 349                     pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
 350                     secureportASSERT( ( ( ( size_t ) pxNewBlockLink ) & secureportBYTE_ALIGNMENT_MASK ) == 0 );
 351
 352                     /* Calculate the sizes of two blocks split from the single
 353                      * block. */
 354                     pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
 355                     pxBlock->xBlockSize = xWantedSize;
 356
 357                     /* Insert the new block into the list of free blocks. */
 358                     pxNewBlockLink->pxNextFreeBlock = pxPreviousBlock->pxNextFreeBlock;
 359                     pxPreviousBlock->pxNextFreeBlock = pxNewBlockLink;
 360                 }
 361                 else
 362                 {
 363                     mtCOVERAGE_TEST_MARKER();
 364                 }
 365
 366                 xFreeBytesRemaining -= pxBlock->xBlockSize;
 367
 368                 if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
 369                 {
 370                     xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
 371                 }
 372                 else
 373                 {
 374                     mtCOVERAGE_TEST_MARKER();
 375                 }
 376
 377                 /* The block is being returned - it is allocated and owned by
 378                  * the application and has no "next" block. */
 379                 secureheapALLOCATE_BLOCK( pxBlock );
 380                 pxBlock->pxNextFreeBlock = NULL;
 381             }
 382             else
 383             {
 384                 mtCOVERAGE_TEST_MARKER();
 385             }
 386         }
 387         else
 388         {
 389             mtCOVERAGE_TEST_MARKER();
 390         }
 391     }
 392     else
 393     {
 394         mtCOVERAGE_TEST_MARKER();
 395     }
 396
 397     traceMALLOC( pvReturn, xWantedSize );
 398
 399     #if ( secureconfigUSE_MALLOC_FAILED_HOOK == 1 )
 400         {
 401             if( pvReturn == NULL )
 402             {
 403                 extern void vApplicationMallocFailedHook( void );
 404                 vApplicationMallocFailedHook();
 405             }
 406             else
 407             {
 408                 mtCOVERAGE_TEST_MARKER();
 409             }
 410         }
 411     #endif /* if ( secureconfigUSE_MALLOC_FAILED_HOOK == 1 ) */
 412
 413     secureportASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) secureportBYTE_ALIGNMENT_MASK ) == 0 );
 414     return pvReturn;
 415 }
 416 /*-----------------------------------------------------------*/
 417
 418 void vPortFree( void * pv )
 419 {
 420     uint8_t * puc = ( uint8_t * ) pv;
 421     BlockLink_t * pxLink;
 422
 423     if( pv != NULL )
 424     {
 425         /* The memory being freed will have an BlockLink_t structure immediately
 426          * before it. */
 427         puc -= xHeapStructSize;
 428
 429         /* This casting is to keep the compiler from issuing warnings. */
 430         pxLink = ( void * ) puc;
 431
 432         /* Check the block is actually allocated. */
 433         secureportASSERT( secureheapBLOCK_IS_ALLOCATED( pxLink ) != 0 );
 434         secureportASSERT( pxLink->pxNextFreeBlock == NULL );
 435
 436         if( secureheapBLOCK_IS_ALLOCATED( pxLink ) != 0 )
 437         {
 438             if( pxLink->pxNextFreeBlock == NULL )
 439             {
 440                 /* The block is being returned to the heap - it is no longer
 441                  * allocated. */
 442                 secureheapFREE_BLOCK( pxLink );
 443
 444                 secureportDISABLE_NON_SECURE_INTERRUPTS();
 445                 {
 446                     /* Add this block to the list of free blocks. */
 447                     xFreeBytesRemaining += pxLink->xBlockSize;
 448                     traceFREE( pv, pxLink->xBlockSize );
 449                     prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
 450                 }
 451                 secureportENABLE_NON_SECURE_INTERRUPTS();
 452             }
 453             else
 454             {
 455                 mtCOVERAGE_TEST_MARKER();
 456             }
 457         }
 458         else
 459         {
 460             mtCOVERAGE_TEST_MARKER();
 461         }
 462     }
 463 }
 464 /*-----------------------------------------------------------*/
 465
 466 size_t xPortGetFreeHeapSize( void )
 467 {
 468     return xFreeBytesRemaining;
 469 }
 470 /*-----------------------------------------------------------*/
 471
 472 size_t xPortGetMinimumEverFreeHeapSize( void )
 473 {
 474     return xMinimumEverFreeBytesRemaining;
 475 }
 476 /*-----------------------------------------------------------*/