1 tab == 4 spaces!\r
*/\r
\r
-\r
/*\r
- * The simplest possible implementation of pvPortMalloc(). Note that this\r
- * implementation does NOT allow allocated memory to be freed again.\r
+ * A sample implementation of pvPortMalloc() and vPortFree() that combines\r
+ * (coalescences) adjacent memory blocks as they are freed, and in so doing\r
+ * limits memory fragmentation.\r
*\r
- * See heap_2.c, heap_3.c and heap_4.c for alternative implementations, and the\r
+ * See heap_1.c, heap_2.c and heap_3.c for alternative implementations, and the\r
* memory management pages of http://www.FreeRTOS.org for more information.\r
*/\r
#include <stdlib.h>\r
\r
#undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
\r
-/* A few bytes might be lost to byte aligning the heap start address. */\r
-#define configADJUSTED_HEAP_SIZE ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )\r
+/* Block sizes must not get too small. */\r
+#define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( xHeapStructSize << 1 ) )\r
+\r
+/* Assumes 8bit bytes! */\r
+#define heapBITS_PER_BYTE ( ( size_t ) 8 )\r
\r
/* Allocate the memory for the heap. */\r
-static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
-static size_t xNextFreeByte = ( size_t ) 0;\r
+#if( configAPPLICATION_ALLOCATED_HEAP == 1 )\r
+ /* The application writer has already defined the array used for the RTOS\r
+ heap - probably so it can be placed in a special segment or address. */\r
+ extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
+#else\r
+ static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];\r
+#endif /* configAPPLICATION_ALLOCATED_HEAP */\r
+\r
+/* Define the linked list structure. This is used to link free blocks in order\r
+of their memory address. */\r
+typedef struct A_BLOCK_LINK\r
+{\r
+ struct A_BLOCK_LINK *pxNextFreeBlock; /*<< The next free block in the list. */\r
+ size_t xBlockSize; /*<< The size of the free block. */\r
+} BlockLink_t;\r
+\r
+/*-----------------------------------------------------------*/\r
+\r
+/*\r
+ * Inserts a block of memory that is being freed into the correct position in\r
+ * the list of free memory blocks. The block being freed will be merged with\r
+ * the block in front it and/or the block behind it if the memory blocks are\r
+ * adjacent to each other.\r
+ */\r
+static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert );\r
+\r
+/*\r
+ * Called automatically to setup the required heap structures the first time\r
+ * pvPortMalloc() is called.\r
+ */\r
+static void prvHeapInit( void );\r
+\r
+/*-----------------------------------------------------------*/\r
+\r
+/* The size of the structure placed at the beginning of each allocated memory\r
+block must by correctly byte aligned. */\r
+static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
+\r
+/* Create a couple of list links to mark the start and end of the list. */\r
+static BlockLink_t xStart, *pxEnd = NULL;\r
+\r
+/* Keeps track of the number of free bytes remaining, but says nothing about\r
+fragmentation. */\r
+static size_t xFreeBytesRemaining = 0U;\r
+static size_t xMinimumEverFreeBytesRemaining = 0U;\r
+\r
+/* Gets set to the top bit of an size_t type. When this bit in the xBlockSize\r
+member of an BlockLink_t structure is set then the block belongs to the\r
+application. When the bit is free the block is still part of the free heap\r
+space. */\r
+static size_t xBlockAllocatedBit = 0;\r
\r
/*-----------------------------------------------------------*/\r
\r
void *pvPortMalloc( size_t xWantedSize )\r
{\r
+BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;\r
void *pvReturn = NULL;\r
-static uint8_t *pucAlignedHeap = NULL;\r
-\r
- /* Ensure that blocks are always aligned to the required number of bytes. */\r
- #if portBYTE_ALIGNMENT != 1\r
- if( xWantedSize & portBYTE_ALIGNMENT_MASK )\r
- {\r
- /* Byte alignment required. */\r
- xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );\r
- }\r
- #endif\r
-\r
- vTaskSuspendAll();\r
- {\r
- if( pucAlignedHeap == NULL )\r
- {\r
- /* Ensure the heap starts on a correctly aligned boundary. */\r
- pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );\r
- }\r
-\r
- /* Check there is enough room left for the allocation. */\r
- if( ( ( xNextFreeByte + xWantedSize ) < configADJUSTED_HEAP_SIZE ) &&\r
- ( ( xNextFreeByte + xWantedSize ) > xNextFreeByte ) )/* Check for overflow. */\r
- {\r
- /* Return the next free byte then increment the index past this\r
- block. */\r
- pvReturn = pucAlignedHeap + xNextFreeByte;\r
- xNextFreeByte += xWantedSize;\r
- }\r
-\r
- traceMALLOC( pvReturn, xWantedSize );\r
- }\r
- ( void ) xTaskResumeAll();\r
-\r
- #if( configUSE_MALLOC_FAILED_HOOK == 1 )\r
- {\r
- if( pvReturn == NULL )\r
- {\r
- extern void vApplicationMallocFailedHook( void );\r
- vApplicationMallocFailedHook();\r
- }\r
- }\r
- #endif\r
-\r
- return pvReturn;\r
+\r
+ vTaskSuspendAll();\r
+ {\r
+ /* If this is the first call to malloc then the heap will require\r
+ initialisation to setup the list of free blocks. */\r
+ if( pxEnd == NULL )\r
+ {\r
+ prvHeapInit();\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+\r
+ /* Check the requested block size is not so large that the top bit is\r
+ set. The top bit of the block size member of the BlockLink_t structure\r
+ is used to determine who owns the block - the application or the\r
+ kernel, so it must be free. */\r
+ if( ( xWantedSize & xBlockAllocatedBit ) == 0 )\r
+ {\r
+ /* The wanted size is increased so it can contain a BlockLink_t\r
+ structure in addition to the requested amount of bytes. */\r
+ if( xWantedSize > 0 )\r
+ {\r
+ xWantedSize += xHeapStructSize;\r
+\r
+ /* Ensure that blocks are always aligned to the required number\r
+ of bytes. */\r
+ if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )\r
+ {\r
+ /* Byte alignment required. */\r
+ xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );\r
+ configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+\r
+ if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )\r
+ {\r
+ /* Traverse the list from the start (lowest address) block until\r
+ one of adequate size is found. */\r
+ pxPreviousBlock = &xStart;\r
+ pxBlock = xStart.pxNextFreeBlock;\r
+ while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )\r
+ {\r
+ pxPreviousBlock = pxBlock;\r
+ pxBlock = pxBlock->pxNextFreeBlock;\r
+ }\r
+\r
+ /* If the end marker was reached then a block of adequate size\r
+ was not found. */\r
+ if( pxBlock != pxEnd )\r
+ {\r
+ /* Return the memory space pointed to - jumping over the\r
+ BlockLink_t structure at its start. */\r
+ pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );\r
+\r
+ /* This block is being returned for use so must be taken out\r
+ of the list of free blocks. */\r
+ pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;\r
+\r
+ /* If the block is larger than required it can be split into\r
+ two. */\r
+ if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )\r
+ {\r
+ /* This block is to be split into two. Create a new\r
+ block following the number of bytes requested. The void\r
+ cast is used to prevent byte alignment warnings from the\r
+ compiler. */\r
+ pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );\r
+ configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );\r
+\r
+ /* Calculate the sizes of two blocks split from the\r
+ single block. */\r
+ pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;\r
+ pxBlock->xBlockSize = xWantedSize;\r
+\r
+ /* Insert the new block into the list of free blocks. */\r
+ prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+\r
+ xFreeBytesRemaining -= pxBlock->xBlockSize;\r
+\r
+ if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )\r
+ {\r
+ xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+\r
+ /* The block is being returned - it is allocated and owned\r
+ by the application and has no "next" block. */\r
+ pxBlock->xBlockSize |= xBlockAllocatedBit;\r
+ pxBlock->pxNextFreeBlock = NULL;\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+\r
+ traceMALLOC( pvReturn, xWantedSize );\r
+ }\r
+ ( void ) xTaskResumeAll();\r
+\r
+ #if( configUSE_MALLOC_FAILED_HOOK == 1 )\r
+ {\r
+ if( pvReturn == NULL )\r
+ {\r
+ extern void vApplicationMallocFailedHook( void );\r
+ vApplicationMallocFailedHook();\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+ }\r
+ #endif\r
+\r
+ configASSERT( ( ( ( uint32_t ) pvReturn ) & portBYTE_ALIGNMENT_MASK ) == 0 );\r
+ return pvReturn;\r
}\r
/*-----------------------------------------------------------*/\r
\r
void vPortFree( void *pv )\r
{\r
- /* Memory cannot be freed using this scheme. See heap_2.c, heap_3.c and\r
- heap_4.c for alternative implementations, and the memory management pages of\r
- http://www.FreeRTOS.org for more information. */\r
- ( void ) pv;\r
-\r
- /* Force an assert as it is invalid to call this function. */\r
- configASSERT( pv == NULL );\r
+uint8_t *puc = ( uint8_t * ) pv;\r
+BlockLink_t *pxLink;\r
+\r
+ if( pv != NULL )\r
+ {\r
+ /* The memory being freed will have an BlockLink_t structure immediately\r
+ before it. */\r
+ puc -= xHeapStructSize;\r
+\r
+ /* This casting is to keep the compiler from issuing warnings. */\r
+ pxLink = ( void * ) puc;\r
+\r
+ /* Check the block is actually allocated. */\r
+ configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );\r
+ configASSERT( pxLink->pxNextFreeBlock == NULL );\r
+\r
+ if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )\r
+ {\r
+ if( pxLink->pxNextFreeBlock == NULL )\r
+ {\r
+ /* The block is being returned to the heap - it is no longer\r
+ allocated. */\r
+ pxLink->xBlockSize &= ~xBlockAllocatedBit;\r
+\r
+ vTaskSuspendAll();\r
+ {\r
+ /* Add this block to the list of free blocks. */\r
+ xFreeBytesRemaining += pxLink->xBlockSize;\r
+ traceFREE( pv, pxLink->xBlockSize );\r
+ prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );\r
+ }\r
+ ( void ) xTaskResumeAll();\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+ }\r
}\r
/*-----------------------------------------------------------*/\r
\r
-void vPortInitialiseBlocks( void )\r
+size_t xPortGetFreeHeapSize( void )\r
{\r
- /* Only required when static memory is not cleared. */\r
- xNextFreeByte = ( size_t ) 0;\r
+ return xFreeBytesRemaining;\r
}\r
/*-----------------------------------------------------------*/\r
\r
-size_t xPortGetFreeHeapSize( void )\r
+size_t xPortGetMinimumEverFreeHeapSize( void )\r
{\r
- return ( configADJUSTED_HEAP_SIZE - xNextFreeByte );\r
+ return xMinimumEverFreeBytesRemaining;\r
}\r
+/*-----------------------------------------------------------*/\r
\r
+void vPortInitialiseBlocks( void )\r
+{\r
+ /* This just exists to keep the linker quiet. */\r
+}\r
+/*-----------------------------------------------------------*/\r
\r
+static void prvHeapInit( void )\r
+{\r
+BlockLink_t *pxFirstFreeBlock;\r
+uint8_t *pucAlignedHeap;\r
+size_t uxAddress;\r
+size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;\r
+\r
+ /* Ensure the heap starts on a correctly aligned boundary. */\r
+ uxAddress = ( size_t ) ucHeap;\r
+\r
+ if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )\r
+ {\r
+ uxAddress += ( portBYTE_ALIGNMENT - 1 );\r
+ uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
+ xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;\r
+ }\r
+\r
+ pucAlignedHeap = ( uint8_t * ) uxAddress;\r
+\r
+ /* xStart is used to hold a pointer to the first item in the list of free\r
+ blocks. The void cast is used to prevent compiler warnings. */\r
+ xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;\r
+ xStart.xBlockSize = ( size_t ) 0;\r
+\r
+ /* pxEnd is used to mark the end of the list of free blocks and is inserted\r
+ at the end of the heap space. */\r
+ uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;\r
+ uxAddress -= xHeapStructSize;\r
+ uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );\r
+ pxEnd = ( void * ) uxAddress;\r
+ pxEnd->xBlockSize = 0;\r
+ pxEnd->pxNextFreeBlock = NULL;\r
+\r
+ /* To start with there is a single free block that is sized to take up the\r
+ entire heap space, minus the space taken by pxEnd. */\r
+ pxFirstFreeBlock = ( void * ) pucAlignedHeap;\r
+ pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;\r
+ pxFirstFreeBlock->pxNextFreeBlock = pxEnd;\r
+\r
+ /* Only one block exists - and it covers the entire usable heap space. */\r
+ xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;\r
+ xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;\r
+\r
+ /* Work out the position of the top bit in a size_t variable. */\r
+ xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );\r
+}\r
+/*-----------------------------------------------------------*/\r
\r
+static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )\r
+{\r
+BlockLink_t *pxIterator;\r
+uint8_t *puc;\r
+\r
+ /* Iterate through the list until a block is found that has a higher address\r
+ than the block being inserted. */\r
+ for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )\r
+ {\r
+ /* Nothing to do here, just iterate to the right position. */\r
+ }\r
+\r
+ /* Do the block being inserted, and the block it is being inserted after\r
+ make a contiguous block of memory? */\r
+ puc = ( uint8_t * ) pxIterator;\r
+ if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )\r
+ {\r
+ pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;\r
+ pxBlockToInsert = pxIterator;\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+\r
+ /* Do the block being inserted, and the block it is being inserted before\r
+ make a contiguous block of memory? */\r
+ puc = ( uint8_t * ) pxBlockToInsert;\r
+ if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )\r
+ {\r
+ if( pxIterator->pxNextFreeBlock != pxEnd )\r
+ {\r
+ /* Form one big block from the two blocks. */\r
+ pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;\r
+ pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;\r
+ }\r
+ else\r
+ {\r
+ pxBlockToInsert->pxNextFreeBlock = pxEnd;\r
+ }\r
+ }\r
+ else\r
+ {\r
+ pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;\r
+ }\r
+\r
+ /* If the block being inserted plugged a gab, so was merged with the block\r
+ before and the block after, then it's pxNextFreeBlock pointer will have\r
+ already been set, and should not be set here as that would make it point\r
+ to itself. */\r
+ if( pxIterator != pxBlockToInsert )\r
+ {\r
+ pxIterator->pxNextFreeBlock = pxBlockToInsert;\r
+ }\r
+ else\r
+ {\r
+ mtCOVERAGE_TEST_MARKER();\r
+ }\r
+}\r
projects / pes-rpp / rpp-lib.git / commitdiff