heap_2.c 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273
  1. /*
  2. * FreeRTOS Kernel V10.0.0
  3. * Copyright (C) 2017 Amazon.com, Inc. or its affiliates. All Rights Reserved.
  4. *
  5. * Permission is hereby granted, free of charge, to any person obtaining a copy of
  6. * this software and associated documentation files (the "Software"), to deal in
  7. * the Software without restriction, including without limitation the rights to
  8. * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
  9. * the Software, and to permit persons to whom the Software is furnished to do so,
  10. * subject to the following conditions:
  11. *
  12. * The above copyright notice and this permission notice shall be included in all
  13. * copies or substantial portions of the Software. If you wish to use our Amazon
  14. * FreeRTOS name, please do so in a fair use way that does not cause confusion.
  15. *
  16. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  18. * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
  19. * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  20. * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21. * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22. *
  23. * http://www.FreeRTOS.org
  24. * http://aws.amazon.com/freertos
  25. *
  26. * 1 tab == 4 spaces!
  27. */
  28. /*
  29. * A sample implementation of pvPortMalloc() and vPortFree() that permits
  30. * allocated blocks to be freed, but does not combine adjacent free blocks
  31. * into a single larger block (and so will fragment memory). See heap_4.c for
  32. * an equivalent that does combine adjacent blocks into single larger blocks.
  33. *
  34. * See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the
  35. * memory management pages of http://www.FreeRTOS.org for more information.
  36. */
  37. #include <stdlib.h>
  38. /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
  39. all the API functions to use the MPU wrappers. That should only be done when
  40. task.h is included from an application file. */
  41. #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
  42. #include "FreeRTOS.h"
  43. #include "task.h"
  44. #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
  45. #if( configSUPPORT_DYNAMIC_ALLOCATION == 0 )
  46. #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
  47. #endif
  48. /* A few bytes might be lost to byte aligning the heap start address. */
  49. #define configADJUSTED_HEAP_SIZE ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )
  50. /*
  51. * Initialises the heap structures before their first use.
  52. */
  53. static void prvHeapInit( void );
  54. /* Allocate the memory for the heap. */
  55. #if( configAPPLICATION_ALLOCATED_HEAP == 1 )
  56. /* The application writer has already defined the array used for the RTOS
  57. heap - probably so it can be placed in a special segment or address. */
  58. extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
  59. #else
  60. static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
  61. #endif /* configAPPLICATION_ALLOCATED_HEAP */
  62. /* Define the linked list structure. This is used to link free blocks in order
  63. of their size. */
  64. typedef struct A_BLOCK_LINK
  65. {
  66. struct A_BLOCK_LINK *pxNextFreeBlock; /*<< The next free block in the list. */
  67. size_t xBlockSize; /*<< The size of the free block. */
  68. } BlockLink_t;
  69. static const uint16_t heapSTRUCT_SIZE = ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );
  70. #define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )
  71. /* Create a couple of list links to mark the start and end of the list. */
  72. static BlockLink_t xStart, xEnd;
  73. /* Keeps track of the number of free bytes remaining, but says nothing about
  74. fragmentation. */
  75. static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;
  76. /* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */
  77. /*
  78. * Insert a block into the list of free blocks - which is ordered by size of
  79. * the block. Small blocks at the start of the list and large blocks at the end
  80. * of the list.
  81. */
  82. #define prvInsertBlockIntoFreeList( pxBlockToInsert ) \
  83. { \
  84. BlockLink_t *pxIterator; \
  85. size_t xBlockSize; \
  86. \
  87. xBlockSize = pxBlockToInsert->xBlockSize; \
  88. \
  89. /* Iterate through the list until a block is found that has a larger size */ \
  90. /* than the block we are inserting. */ \
  91. for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
  92. { \
  93. /* There is nothing to do here - just iterate to the correct position. */ \
  94. } \
  95. \
  96. /* Update the list to include the block being inserted in the correct */ \
  97. /* position. */ \
  98. pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock; \
  99. pxIterator->pxNextFreeBlock = pxBlockToInsert; \
  100. }
  101. /*-----------------------------------------------------------*/
  102. void *pvPortMalloc( size_t xWantedSize )
  103. {
  104. BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
  105. static BaseType_t xHeapHasBeenInitialised = pdFALSE;
  106. void *pvReturn = NULL;
  107. vTaskSuspendAll();
  108. {
  109. /* If this is the first call to malloc then the heap will require
  110. initialisation to setup the list of free blocks. */
  111. if( xHeapHasBeenInitialised == pdFALSE )
  112. {
  113. prvHeapInit();
  114. xHeapHasBeenInitialised = pdTRUE;
  115. }
  116. /* The wanted size is increased so it can contain a BlockLink_t
  117. structure in addition to the requested amount of bytes. */
  118. if( xWantedSize > 0 )
  119. {
  120. xWantedSize += heapSTRUCT_SIZE;
  121. /* Ensure that blocks are always aligned to the required number of bytes. */
  122. if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
  123. {
  124. /* Byte alignment required. */
  125. xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
  126. }
  127. }
  128. if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
  129. {
  130. /* Blocks are stored in byte order - traverse the list from the start
  131. (smallest) block until one of adequate size is found. */
  132. pxPreviousBlock = &xStart;
  133. pxBlock = xStart.pxNextFreeBlock;
  134. while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
  135. {
  136. pxPreviousBlock = pxBlock;
  137. pxBlock = pxBlock->pxNextFreeBlock;
  138. }
  139. /* If we found the end marker then a block of adequate size was not found. */
  140. if( pxBlock != &xEnd )
  141. {
  142. /* Return the memory space - jumping over the BlockLink_t structure
  143. at its start. */
  144. pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );
  145. /* This block is being returned for use so must be taken out of the
  146. list of free blocks. */
  147. pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
  148. /* If the block is larger than required it can be split into two. */
  149. if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
  150. {
  151. /* This block is to be split into two. Create a new block
  152. following the number of bytes requested. The void cast is
  153. used to prevent byte alignment warnings from the compiler. */
  154. pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
  155. /* Calculate the sizes of two blocks split from the single
  156. block. */
  157. pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
  158. pxBlock->xBlockSize = xWantedSize;
  159. /* Insert the new block into the list of free blocks. */
  160. prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
  161. }
  162. xFreeBytesRemaining -= pxBlock->xBlockSize;
  163. }
  164. }
  165. traceMALLOC( pvReturn, xWantedSize );
  166. }
  167. ( void ) xTaskResumeAll();
  168. #if( configUSE_MALLOC_FAILED_HOOK == 1 )
  169. {
  170. if( pvReturn == NULL )
  171. {
  172. extern void vApplicationMallocFailedHook( void );
  173. vApplicationMallocFailedHook();
  174. }
  175. }
  176. #endif
  177. return pvReturn;
  178. }
  179. /*-----------------------------------------------------------*/
  180. void vPortFree( void *pv )
  181. {
  182. uint8_t *puc = ( uint8_t * ) pv;
  183. BlockLink_t *pxLink;
  184. if( pv != NULL )
  185. {
  186. /* The memory being freed will have an BlockLink_t structure immediately
  187. before it. */
  188. puc -= heapSTRUCT_SIZE;
  189. /* This unexpected casting is to keep some compilers from issuing
  190. byte alignment warnings. */
  191. pxLink = ( void * ) puc;
  192. vTaskSuspendAll();
  193. {
  194. /* Add this block to the list of free blocks. */
  195. prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
  196. xFreeBytesRemaining += pxLink->xBlockSize;
  197. traceFREE( pv, pxLink->xBlockSize );
  198. }
  199. ( void ) xTaskResumeAll();
  200. }
  201. }
  202. /*-----------------------------------------------------------*/
  203. size_t xPortGetFreeHeapSize( void )
  204. {
  205. return xFreeBytesRemaining;
  206. }
  207. /*-----------------------------------------------------------*/
  208. void vPortInitialiseBlocks( void )
  209. {
  210. /* This just exists to keep the linker quiet. */
  211. }
  212. /*-----------------------------------------------------------*/
  213. static void prvHeapInit( void )
  214. {
  215. BlockLink_t *pxFirstFreeBlock;
  216. uint8_t *pucAlignedHeap;
  217. /* Ensure the heap starts on a correctly aligned boundary. */
  218. pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
  219. /* xStart is used to hold a pointer to the first item in the list of free
  220. blocks. The void cast is used to prevent compiler warnings. */
  221. xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
  222. xStart.xBlockSize = ( size_t ) 0;
  223. /* xEnd is used to mark the end of the list of free blocks. */
  224. xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
  225. xEnd.pxNextFreeBlock = NULL;
  226. /* To start with there is a single free block that is sized to take up the
  227. entire heap space. */
  228. pxFirstFreeBlock = ( void * ) pucAlignedHeap;
  229. pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
  230. pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
  231. }
  232. /*-----------------------------------------------------------*/