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 /*

30 * A sample implementation of pvPortMalloc() that allows the heap to be defined

31 * across multiple non-contigous blocks and combines (coalescences) adjacent

32 * memory blocks as they are freed.

33 *

34 * See heap_1.c, heap_2.c, heap_3.c and heap_4.c for alternative

35 * implementations, and the memory management pages of https://www.FreeRTOS.org

36 * for more information.

37 *

38 * Usage notes:

39 *

40 * vPortDefineHeapRegions() ***must*** be called before pvPortMalloc().

41 * pvPortMalloc() will be called if any task objects (tasks, queues, event

42 * groups, etc.) are created, therefore vPortDefineHeapRegions() ***must*** be

43 * called before any other objects are defined.

44 *

45 * vPortDefineHeapRegions() takes a single parameter. The parameter is an array

46 * of HeapRegion_t structures. HeapRegion_t is defined in portable.h as

47 *

48 * typedef struct HeapRegion

49 * {

50 * uint8_t *pucStartAddress; << Start address of a block of memory that will be part of the heap.

51 * size_t xSizeInBytes; << Size of the block of memory.

52 * } HeapRegion_t;

53 *

54 * The array is terminated using a NULL zero sized region definition, and the

55 * memory regions defined in the array ***must*** appear in address order from

56 * low address to high address. So the following is a valid example of how

57 * to use the function.

58 *

59 * HeapRegion_t xHeapRegions[] =

60 * {

61 * { ( uint8_t * ) 0x80000000UL, 0x10000 }, << Defines a block of 0x10000 bytes starting at address 0x80000000

62 * { ( uint8_t * ) 0x90000000UL, 0xa0000 }, << Defines a block of 0xa0000 bytes starting at address of 0x90000000

63 * { NULL, 0 } << Terminates the array.

64 * };

65 *

66 * vPortDefineHeapRegions( xHeapRegions ); << Pass the array into vPortDefineHeapRegions().

67 *

68 * Note 0x80000000 is the lower address so appears in the array first.

69 *

70 */

71 #include <stdlib.h>

72 #include <string.h>

73

74 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining

75 * all the API functions to use the MPU wrappers. That should only be done when

76 * task.h is included from an application file. */

77 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

78

79 #include "FreeRTOS.h"

80 #include "task.h"

81

82 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE

83

84 #if ( configSUPPORT_DYNAMIC_ALLOCATION == 0 )

85 #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0

86 #endif

87

88 #ifndef configHEAP_CLEAR_MEMORY_ON_FREE

89 #define configHEAP_CLEAR_MEMORY_ON_FREE 0

90 #endif

91

92 /* Block sizes must not get too small. */

93 #define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( xHeapStructSize << 1 ) )

94

95 /* Assumes 8bit bytes! */

96 #define heapBITS_PER_BYTE ( ( size_t ) 8 )

97

98 /* Max value that fits in a size_t type. */

99 #define heapSIZE_MAX ( ~( ( size_t ) 0 ) )

100

101 /* Check if multiplying a and b will result in overflow. */

102 #define heapMULTIPLY_WILL_OVERFLOW( a, b ) ( ( ( a ) > 0 ) && ( ( b ) > ( heapSIZE_MAX / ( a ) ) ) )

103

104 /* Check if adding a and b will result in overflow. */

105 #define heapADD_WILL_OVERFLOW( a, b ) ( ( a ) > ( heapSIZE_MAX - ( b ) ) )

106

107 /* MSB of the xBlockSize member of an BlockLink_t structure is used to track

108 * the allocation status of a block. When MSB of the xBlockSize member of

109 * an BlockLink_t structure is set then the block belongs to the application.

110 * When the bit is free the block is still part of the free heap space. */

111 #define heapBLOCK_ALLOCATED_BITMASK ( ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 ) )

112 #define heapBLOCK_SIZE_IS_VALID( xBlockSize ) ( ( ( xBlockSize ) & heapBLOCK_ALLOCATED_BITMASK ) == 0 )

113 #define heapBLOCK_IS_ALLOCATED( pxBlock ) ( ( ( pxBlock->xBlockSize ) & heapBLOCK_ALLOCATED_BITMASK ) != 0 )

114 #define heapALLOCATE_BLOCK( pxBlock ) ( ( pxBlock->xBlockSize ) |= heapBLOCK_ALLOCATED_BITMASK )

115 #define heapFREE_BLOCK( pxBlock ) ( ( pxBlock->xBlockSize ) &= ~heapBLOCK_ALLOCATED_BITMASK )

116

117 /*-----------------------------------------------------------*/

118

119 /* Define the linked list structure. This is used to link free blocks in order

120 * of their memory address. */

121 typedef struct A_BLOCK_LINK

122 {

123 struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */

124 size_t xBlockSize; /*<< The size of the free block. */

125 } BlockLink_t;

126

127 /*-----------------------------------------------------------*/

128

129 /*

130 * Inserts a block of memory that is being freed into the correct position in

131 * the list of free memory blocks. The block being freed will be merged with

132 * the block in front it and/or the block behind it if the memory blocks are

133 * adjacent to each other.

134 */

135 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert );

136

137 /*-----------------------------------------------------------*/

138

139 /* The size of the structure placed at the beginning of each allocated memory

140 * block must by correctly byte aligned. */

141 static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );

142

143 /* Create a couple of list links to mark the start and end of the list. */

144 static BlockLink_t xStart, * pxEnd = NULL;

145

146 /* Keeps track of the number of calls to allocate and free memory as well as the

147 * number of free bytes remaining, but says nothing about fragmentation. */

148 static size_t xFreeBytesRemaining = 0U;

149 static size_t xMinimumEverFreeBytesRemaining = 0U;

150 static size_t xNumberOfSuccessfulAllocations = 0;

151 static size_t xNumberOfSuccessfulFrees = 0;

152

153 /*-----------------------------------------------------------*/

154

155 void * pvPortMalloc( size_t xWantedSize )

156 {

160

161 /* The heap must be initialised before the first call to

162 * prvPortMalloc(). */

163 configASSERT( pxEnd );

164

166 {

168 {

169 /* The wanted size must be increased so it can contain a BlockLink_t

170 * structure in addition to the requested amount of bytes. Some

171 * additional increment may also be needed for alignment. */

173

175 {

177 }

178 else

179 {

181 }

182 }

183 else

184 {

185 mtCOVERAGE_TEST_MARKER();

186 }

187

188 /* Check the block size we are trying to allocate is not so large that the

189 * top bit is set. The top bit of the block size member of the BlockLink_t

190 * structure is used to determine who owns the block - the application or

191 * the kernel, so it must be free. */

193 {

195 {

196 /* Traverse the list from the start (lowest address) block until

197 * one of adequate size is found. */

200

202 {

205 }

206

207 /* If the end marker was reached then a block of adequate size

208 * was not found. */

210 {

211 /* Return the memory space pointed to - jumping over the

212 * BlockLink_t structure at its start. */

214

215 /* This block is being returned for use so must be taken out

216 * of the list of free blocks. */

218

219 /* If the block is larger than required it can be split into

220 * two. */

222 {

223 /* This block is to be split into two. Create a new

224 * block following the number of bytes requested. The void

225 * cast is used to prevent byte alignment warnings from the

226 * compiler. */

228

229 /* Calculate the sizes of two blocks split from the

230 * single block. */

233

234 /* Insert the new block into the list of free blocks. */

236 }

237 else

238 {

239 mtCOVERAGE_TEST_MARKER();

240 }

241

243

245 {

247 }

248 else

249 {

250 mtCOVERAGE_TEST_MARKER();

251 }

252

253 /* The block is being returned - it is allocated and owned

254 * by the application and has no "next" block. */

258 }

259 else

260 {

261 mtCOVERAGE_TEST_MARKER();

262 }

263 }

264 else

265 {

266 mtCOVERAGE_TEST_MARKER();

267 }

268 }

269 else

270 {

271 mtCOVERAGE_TEST_MARKER();

272 }

273

274 traceMALLOC( pvReturn, xWantedSize );

275 }

277

278 #if ( configUSE_MALLOC_FAILED_HOOK == 1 )

279 {

280 if( pvReturn == NULL )

281 {

282 vApplicationMallocFailedHook();

283 }

284 else

285 {

286 mtCOVERAGE_TEST_MARKER();

287 }

288 }

289 #endif /* if ( configUSE_MALLOC_FAILED_HOOK == 1 ) */

290

293 /*-----------------------------------------------------------*/

294

295 void vPortFree( void * pv )

296 {

297 uint8_t * puc = ( uint8_t * ) pv;

298 BlockLink_t * pxLink;

299

300 if( pv != NULL )

301 {

302 /* The memory being freed will have an BlockLink_t structure immediately

303 * before it. */

304 puc -= xHeapStructSize;

305

306 /* This casting is to keep the compiler from issuing warnings. */

307 pxLink = ( void * ) puc;

308

309 configASSERT( heapBLOCK_IS_ALLOCATED( pxLink ) != 0 );

310 configASSERT( pxLink->pxNextFreeBlock == NULL );

311

312 if( heapBLOCK_IS_ALLOCATED( pxLink ) != 0 )

313 {

314 if( pxLink->pxNextFreeBlock == NULL )

315 {

316 /* The block is being returned to the heap - it is no longer

317 * allocated. */

318 heapFREE_BLOCK( pxLink );

319 #if ( configHEAP_CLEAR_MEMORY_ON_FREE == 1 )

320 {

321 ( void ) memset( puc + xHeapStructSize, 0, pxLink->xBlockSize - xHeapStructSize );

322 }

323 #endif

324

325 vTaskSuspendAll();

326 {

327 /* Add this block to the list of free blocks. */

328 xFreeBytesRemaining += pxLink->xBlockSize;

329 traceFREE( pv, pxLink->xBlockSize );

330 prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );

331 xNumberOfSuccessfulFrees++;

332 }

333 ( void ) xTaskResumeAll();

334 }

335 else

336 {

337 mtCOVERAGE_TEST_MARKER();

338 }

339 }

340 else

341 {

342 mtCOVERAGE_TEST_MARKER();

343 }

344 }

345 }

346 /*-----------------------------------------------------------*/

347

348 size_t xPortGetFreeHeapSize( void )

349 {

350 return xFreeBytesRemaining;

351 }

352 /*-----------------------------------------------------------*/

353

354 size_t xPortGetMinimumEverFreeHeapSize( void )

355 {

356 return xMinimumEverFreeBytesRemaining;

357 }

358 /*-----------------------------------------------------------*/

359

360 void * pvPortCalloc( size_t xNum,

361 size_t xSize )

362 {

363 void * pv = NULL;

364

365 if( heapMULTIPLY_WILL_OVERFLOW( xNum, xSize ) == 0 )

366 {

367 pv = pvPortMalloc( xNum * xSize );

368

369 if( pv != NULL )

370 {

371 ( void ) memset( pv, 0, xNum * xSize );

372 }

373 }

374

375 return pv;

376 }

377 /*-----------------------------------------------------------*/

378

379 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert )

380 {

383

384 /* Iterate through the list until a block is found that has a higher address

385 * than the block being inserted. */

387 {

388 /* Nothing to do here, just iterate to the right position. */

389 }

390

391 /* Do the block being inserted, and the block it is being inserted after

392 * make a contiguous block of memory? */

394

396 {

399 }

400 else

401 {

402 mtCOVERAGE_TEST_MARKER();

403 }

404

405 /* Do the block being inserted, and the block it is being inserted before

406 * make a contiguous block of memory? */

408

410 {

412 {

413 /* Form one big block from the two blocks. */

416 }

417 else

418 {

420 }

421 }

422 else

423 {

425 }

426

427 /* If the block being inserted plugged a gab, so was merged with the block

428 * before and the block after, then it's pxNextFreeBlock pointer will have

429 * already been set, and should not be set here as that would make it point

430 * to itself. */

432 {

434 }

435 else

436 {

437 mtCOVERAGE_TEST_MARKER();

438 }

440 /*-----------------------------------------------------------*/

441

442 void vPortDefineHeapRegions( const HeapRegion_t * const pxHeapRegions )

443 {

444 BlockLink_t * pxFirstFreeBlockInRegion = NULL, * pxPreviousFreeBlock;

445 size_t xAlignedHeap;

446 size_t xTotalRegionSize, xTotalHeapSize = 0;

447 BaseType_t xDefinedRegions = 0;

448 size_t xAddress;

449 const HeapRegion_t * pxHeapRegion;

450

451 /* Can only call once! */

452 configASSERT( pxEnd == NULL );

453

454 pxHeapRegion = &( pxHeapRegions[ xDefinedRegions ] );

455

456 while( pxHeapRegion->xSizeInBytes > 0 )

457 {

458 xTotalRegionSize = pxHeapRegion->xSizeInBytes;

459

460 /* Ensure the heap region starts on a correctly aligned boundary. */

461 xAddress = ( size_t ) pxHeapRegion->pucStartAddress;

462

463 if( ( xAddress & portBYTE_ALIGNMENT_MASK ) != 0 )

464 {

465 xAddress += ( portBYTE_ALIGNMENT - 1 );

466 xAddress &= ~portBYTE_ALIGNMENT_MASK;

467

468 /* Adjust the size for the bytes lost to alignment. */

469 xTotalRegionSize -= xAddress - ( size_t ) pxHeapRegion->pucStartAddress;

470 }

471

472 xAlignedHeap = xAddress;

473

474 /* Set xStart if it has not already been set. */

475 if( xDefinedRegions == 0 )

476 {

477 /* xStart is used to hold a pointer to the first item in the list of

478 * free blocks. The void cast is used to prevent compiler warnings. */

479 xStart.pxNextFreeBlock = ( BlockLink_t * ) xAlignedHeap;

480 xStart.xBlockSize = ( size_t ) 0;

481 }

482 else

483 {

484 /* Should only get here if one region has already been added to the

485 * heap. */

486 configASSERT( pxEnd != NULL );

487

488 /* Check blocks are passed in with increasing start addresses. */

489 configASSERT( xAddress > ( size_t ) pxEnd );

490 }

491

492 /* Remember the location of the end marker in the previous region, if

493 * any. */

494 pxPreviousFreeBlock = pxEnd;

495

496 /* pxEnd is used to mark the end of the list of free blocks and is

497 * inserted at the end of the region space. */

498 xAddress = xAlignedHeap + xTotalRegionSize;

499 xAddress -= xHeapStructSize;

500 xAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );

501 pxEnd = ( BlockLink_t * ) xAddress;

502 pxEnd->xBlockSize = 0;

503 pxEnd->pxNextFreeBlock = NULL;

504

505 /* To start with there is a single free block in this region that is

506 * sized to take up the entire heap region minus the space taken by the

507 * free block structure. */

508 pxFirstFreeBlockInRegion = ( BlockLink_t * ) xAlignedHeap;

509 pxFirstFreeBlockInRegion->xBlockSize = xAddress - ( size_t ) pxFirstFreeBlockInRegion;

510 pxFirstFreeBlockInRegion->pxNextFreeBlock = pxEnd;

511

512 /* If this is not the first region that makes up the entire heap space

513 * then link the previous region to this region. */

514 if( pxPreviousFreeBlock != NULL )

515 {

516 pxPreviousFreeBlock->pxNextFreeBlock = pxFirstFreeBlockInRegion;

517 }

518

519 xTotalHeapSize += pxFirstFreeBlockInRegion->xBlockSize;

520

521 /* Move onto the next HeapRegion_t structure. */

522 xDefinedRegions++;

523 pxHeapRegion = &( pxHeapRegions[ xDefinedRegions ] );

524 }

525

526 xMinimumEverFreeBytesRemaining = xTotalHeapSize;

527 xFreeBytesRemaining = xTotalHeapSize;

528

529 /* Check something was actually defined before it is accessed. */

530 configASSERT( xTotalHeapSize );

531 }

532 /*-----------------------------------------------------------*/

533

534 void vPortGetHeapStats( HeapStats_t * pxHeapStats )

535 {

536 BlockLink_t * pxBlock;

537 size_t xBlocks = 0, xMaxSize = 0, xMinSize = portMAX_DELAY; /* portMAX_DELAY used as a portable way of getting the maximum value. */

538

539 vTaskSuspendAll();

540 {

541 pxBlock = xStart.pxNextFreeBlock;

542

543 /* pxBlock will be NULL if the heap has not been initialised. The heap

544 * is initialised automatically when the first allocation is made. */

545 if( pxBlock != NULL )

546 {

547 do

548 {

549 /* Increment the number of blocks and record the largest block seen

550 * so far. */

551 xBlocks++;

552

553 if( pxBlock->xBlockSize > xMaxSize )

554 {

555 xMaxSize = pxBlock->xBlockSize;

556 }

557

558 /* Heap five will have a zero sized block at the end of each

559 * each region - the block is only used to link to the next

560 * heap region so it not a real block. */

561 if( pxBlock->xBlockSize != 0 )

562 {

563 if( pxBlock->xBlockSize < xMinSize )

564 {

565 xMinSize = pxBlock->xBlockSize;

566 }

567 }

568

569 /* Move to the next block in the chain until the last block is

570 * reached. */

571 pxBlock = pxBlock->pxNextFreeBlock;

572 } while( pxBlock != pxEnd );

573 }

574 }

575 ( void ) xTaskResumeAll();

576

577 pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;

578 pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;

579 pxHeapStats->xNumberOfFreeBlocks = xBlocks;

580

581 taskENTER_CRITICAL();

582 {

583 pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;

584 pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;

585 pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;

586 pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;

587 }

588 taskEXIT_CRITICAL();

589 }

590 /*-----------------------------------------------------------*/