begriffs open source - cmsis-freertos/blob - Source/portable/GCC/ARM_CM33/secure/secure_heap.c

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