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

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