FreeRTOS/Source/portable/MemMang/heap_2.c - third_party/github/FreeRTOS/FreeRTOS-Kernel - Git at Google

 /*
     FreeRTOS V8.1.1 - Copyright (C) 2014 Real Time Engineers Ltd.
     All rights reserved

     VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.

     ***************************************************************************
      *                                                                       *
      *    FreeRTOS provides completely free yet professionally developed,    *
      *    robust, strictly quality controlled, supported, and cross          *
      *    platform software that has become a de facto standard.             *
      *                                                                       *
      *    Help yourself get started quickly and support the FreeRTOS         *
      *    project by purchasing a FreeRTOS tutorial book, reference          *
      *    manual, or both from: http://www.FreeRTOS.org/Documentation        *
      *                                                                       *
      *    Thank you!                                                         *
      *                                                                       *
     ***************************************************************************

     This file is part of the FreeRTOS distribution.

     FreeRTOS is free software; you can redistribute it and/or modify it under
     the terms of the GNU General Public License (version 2) as published by the
     Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception.

     >>!   NOTE: The modification to the GPL is included to allow you to     !<<
     >>!   distribute a combined work that includes FreeRTOS without being   !<<
     >>!   obliged to provide the source code for proprietary components     !<<
     >>!   outside of the FreeRTOS kernel.                                   !<<

     FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
     WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
     FOR A PARTICULAR PURPOSE.  Full license text is available from the following
     link: http://www.freertos.org/a00114.html

     1 tab == 4 spaces!

     ***************************************************************************
      *                                                                       *
      *    Having a problem?  Start by reading the FAQ "My application does   *
      *    not run, what could be wrong?"                                     *
      *                                                                       *
      *    http://www.FreeRTOS.org/FAQHelp.html                               *
      *                                                                       *
     ***************************************************************************

     http://www.FreeRTOS.org - Documentation, books, training, latest versions,
     license and Real Time Engineers Ltd. contact details.

     http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
     including FreeRTOS+Trace - an indispensable productivity tool, a DOS
     compatible FAT file system, and our tiny thread aware UDP/IP stack.

     http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High
     Integrity Systems to sell under the OpenRTOS brand.  Low cost OpenRTOS
     licenses offer ticketed support, indemnification and middleware.

     http://www.SafeRTOS.com - High Integrity Systems also provide a safety
     engineered and independently SIL3 certified version for use in safety and
     mission critical applications that require provable dependability.

     1 tab == 4 spaces!
 */

 /*
  * A sample implementation of pvPortMalloc() and vPortFree() that permits
  * allocated blocks to be freed, but does not combine adjacent free blocks
  * into a single larger block (and so will fragment memory).  See heap_4.c for
  * an equivalent that does combine adjacent blocks into single larger blocks.
  *
  * See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the
  * memory management pages of http://www.FreeRTOS.org for more information.
  */
 #include <stdlib.h>

 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
 all the API functions to use the MPU wrappers.  That should only be done when
 task.h is included from an application file. */
 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

 #include "FreeRTOS.h"
 #include "task.h"

 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE

 /* A few bytes might be lost to byte aligning the heap start address. */
 #define configADJUSTED_HEAP_SIZE	( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )

 /*
  * Initialises the heap structures before their first use.
  */
 static void prvHeapInit( void );

 /* Allocate the memory for the heap. */
 static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];

 /* Define the linked list structure.  This is used to link free blocks in order
 of their size. */
 typedef struct A_BLOCK_LINK
 {
 	struct A_BLOCK_LINK *pxNextFreeBlock;	/*<< The next free block in the list. */
 	size_t xBlockSize;						/*<< The size of the free block. */
 } BlockLink_t;


 static const uint16_t heapSTRUCT_SIZE	= ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );
 #define heapMINIMUM_BLOCK_SIZE	( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )

 /* Create a couple of list links to mark the start and end of the list. */
 static BlockLink_t xStart, xEnd;

 /* Keeps track of the number of free bytes remaining, but says nothing about
 fragmentation. */
 static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;

 /* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */

 /*
  * Insert a block into the list of free blocks - which is ordered by size of
  * the block.  Small blocks at the start of the list and large blocks at the end
  * of the list.
  */
 #define prvInsertBlockIntoFreeList( pxBlockToInsert )								\
 {																					\
 BlockLink_t *pxIterator;																\
 size_t xBlockSize;																	\
 																					\
 	xBlockSize = pxBlockToInsert->xBlockSize;										\
 																					\
 	/* Iterate through the list until a block is found that has a larger size */	\
 	/* than the block we are inserting. */											\
 	for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock )	\
 	{																				\
 		/* There is nothing to do here - just iterate to the correct position. */	\
 	}																				\
 																					\
 	/* Update the list to include the block being inserted in the correct */		\
 	/* position. */																	\
 	pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;					\
 	pxIterator->pxNextFreeBlock = pxBlockToInsert;									\
 }
 /*-----------------------------------------------------------*/

 void *pvPortMalloc( size_t xWantedSize )
 {
 BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
 static BaseType_t xHeapHasBeenInitialised = pdFALSE;
 void *pvReturn = NULL;

 	vTaskSuspendAll();
 	{
 		/* If this is the first call to malloc then the heap will require
 		initialisation to setup the list of free blocks. */
 		if( xHeapHasBeenInitialised == pdFALSE )
 		{
 			prvHeapInit();
 			xHeapHasBeenInitialised = pdTRUE;
 		}

 		/* The wanted size is increased so it can contain a BlockLink_t
 		structure in addition to the requested amount of bytes. */
 		if( xWantedSize > 0 )
 		{
 			xWantedSize += heapSTRUCT_SIZE;

 			/* Ensure that blocks are always aligned to the required number of bytes. */
 			if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
 			{
 				/* Byte alignment required. */
 				xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
 			}
 		}

 		if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
 		{
 			/* Blocks are stored in byte order - traverse the list from the start
 			(smallest) block until one of adequate size is found. */
 			pxPreviousBlock = &xStart;
 			pxBlock = xStart.pxNextFreeBlock;
 			while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
 			{
 				pxPreviousBlock = pxBlock;
 				pxBlock = pxBlock->pxNextFreeBlock;
 			}

 			/* If we found the end marker then a block of adequate size was not found. */
 			if( pxBlock != &xEnd )
 			{
 				/* Return the memory space - jumping over the BlockLink_t structure
 				at its start. */
 				pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );

 				/* This block is being returned for use so must be taken out of the
 				list of free blocks. */
 				pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

 				/* If the block is larger than required it can be split into two. */
 				if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
 				{
 					/* This block is to be split into two.  Create a new block
 					following the number of bytes requested. The void cast is
 					used to prevent byte alignment warnings from the compiler. */
 					pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );

 					/* Calculate the sizes of two blocks split from the single
 					block. */
 					pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
 					pxBlock->xBlockSize = xWantedSize;

 					/* Insert the new block into the list of free blocks. */
 					prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
 				}

 				xFreeBytesRemaining -= pxBlock->xBlockSize;
 			}
 		}

 		traceMALLOC( pvReturn, xWantedSize );
 	}
 	( void ) xTaskResumeAll();

 	#if( configUSE_MALLOC_FAILED_HOOK == 1 )
 	{
 		if( pvReturn == NULL )
 		{
 			extern void vApplicationMallocFailedHook( void );
 			vApplicationMallocFailedHook();
 		}
 	}
 	#endif

 	return pvReturn;
 }
 /*-----------------------------------------------------------*/

 void vPortFree( void *pv )
 {
 uint8_t *puc = ( uint8_t * ) pv;
 BlockLink_t *pxLink;

 	if( pv != NULL )
 	{
 		/* The memory being freed will have an BlockLink_t structure immediately
 		before it. */
 		puc -= heapSTRUCT_SIZE;

 		/* This unexpected casting is to keep some compilers from issuing
 		byte alignment warnings. */
 		pxLink = ( void * ) puc;

 		vTaskSuspendAll();
 		{
 			/* Add this block to the list of free blocks. */
 			prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
 			xFreeBytesRemaining += pxLink->xBlockSize;
 			traceFREE( pv, pxLink->xBlockSize );
 		}
 		( void ) xTaskResumeAll();
 	}
 }
 /*-----------------------------------------------------------*/

 size_t xPortGetFreeHeapSize( void )
 {
 	return xFreeBytesRemaining;
 }
 /*-----------------------------------------------------------*/

 void vPortInitialiseBlocks( void )
 {
 	/* This just exists to keep the linker quiet. */
 }
 /*-----------------------------------------------------------*/

 static void prvHeapInit( void )
 {
 BlockLink_t *pxFirstFreeBlock;
 uint8_t *pucAlignedHeap;

 	/* Ensure the heap starts on a correctly aligned boundary. */
 	pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ( portPOINTER_SIZE_TYPE ) ~portBYTE_ALIGNMENT_MASK ) );

 	/* xStart is used to hold a pointer to the first item in the list of free
 	blocks.  The void cast is used to prevent compiler warnings. */
 	xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
 	xStart.xBlockSize = ( size_t ) 0;

 	/* xEnd is used to mark the end of the list of free blocks. */
 	xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
 	xEnd.pxNextFreeBlock = NULL;

 	/* To start with there is a single free block that is sized to take up the
 	entire heap space. */
 	pxFirstFreeBlock = ( void * ) pucAlignedHeap;
 	pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
 	pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
 }
 /*-----------------------------------------------------------*/
	/*
	FreeRTOS V8.1.1 - Copyright (C) 2014 Real Time Engineers Ltd.
	All rights reserved

	VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.

	***************************************************************************
	* *
	* FreeRTOS provides completely free yet professionally developed, *
	* robust, strictly quality controlled, supported, and cross *
	* platform software that has become a de facto standard. *
	* *
	* Help yourself get started quickly and support the FreeRTOS *
	* project by purchasing a FreeRTOS tutorial book, reference *
	* manual, or both from: http://www.FreeRTOS.org/Documentation *
	* *
	* Thank you! *
	* *
	***************************************************************************

	This file is part of the FreeRTOS distribution.

	FreeRTOS is free software; you can redistribute it and/or modify it under
	the terms of the GNU General Public License (version 2) as published by the
	Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception.

	>>! NOTE: The modification to the GPL is included to allow you to !<<
	>>! distribute a combined work that includes FreeRTOS without being !<<
	>>! obliged to provide the source code for proprietary components !<<
	>>! outside of the FreeRTOS kernel. !<<

	FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
	WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	FOR A PARTICULAR PURPOSE. Full license text is available from the following
	link: http://www.freertos.org/a00114.html

	1 tab == 4 spaces!

	***************************************************************************
	* *
	* Having a problem? Start by reading the FAQ "My application does *
	* not run, what could be wrong?" *
	* *
	* http://www.FreeRTOS.org/FAQHelp.html *
	* *
	***************************************************************************

	http://www.FreeRTOS.org - Documentation, books, training, latest versions,
	license and Real Time Engineers Ltd. contact details.

	http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
	including FreeRTOS+Trace - an indispensable productivity tool, a DOS
	compatible FAT file system, and our tiny thread aware UDP/IP stack.

	http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High
	Integrity Systems to sell under the OpenRTOS brand. Low cost OpenRTOS
	licenses offer ticketed support, indemnification and middleware.

	http://www.SafeRTOS.com - High Integrity Systems also provide a safety
	engineered and independently SIL3 certified version for use in safety and
	mission critical applications that require provable dependability.

	1 tab == 4 spaces!
	*/

	/*
	* A sample implementation of pvPortMalloc() and vPortFree() that permits
	* allocated blocks to be freed, but does not combine adjacent free blocks
	* into a single larger block (and so will fragment memory). See heap_4.c for
	* an equivalent that does combine adjacent blocks into single larger blocks.
	*
	* See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the
	* memory management pages of http://www.FreeRTOS.org for more information.
	*/
	#include <stdlib.h>

	/* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
	all the API functions to use the MPU wrappers. That should only be done when
	task.h is included from an application file. */
	#define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

	#include "FreeRTOS.h"
	#include "task.h"

	#undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE

	/* A few bytes might be lost to byte aligning the heap start address. */
	#define configADJUSTED_HEAP_SIZE ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )

	/*
	* Initialises the heap structures before their first use.
	*/
	static void prvHeapInit( void );

	/* Allocate the memory for the heap. */
	static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];

	/* Define the linked list structure. This is used to link free blocks in order
	of their size. */
	typedef struct A_BLOCK_LINK
	{
	struct A_BLOCK_LINK pxNextFreeBlock; /<< The next free block in the list. */
	size_t xBlockSize; /<< The size of the free block. /
	} BlockLink_t;


	static const uint16_t heapSTRUCT_SIZE = ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );
	#define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )

	/* Create a couple of list links to mark the start and end of the list. */
	static BlockLink_t xStart, xEnd;

	/* Keeps track of the number of free bytes remaining, but says nothing about
	fragmentation. */
	static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;

	/* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */

	/*
	* Insert a block into the list of free blocks - which is ordered by size of
	* the block. Small blocks at the start of the list and large blocks at the end
	* of the list.
	*/
	#define prvInsertBlockIntoFreeList( pxBlockToInsert ) \
	{ \
	BlockLink_t *pxIterator; \
	size_t xBlockSize; \
	\
	xBlockSize = pxBlockToInsert->xBlockSize; \
	\
	/* Iterate through the list until a block is found that has a larger size */ \
	/* than the block we are inserting. */ \
	for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
	{ \
	/* There is nothing to do here - just iterate to the correct position. */ \
	} \
	\
	/* Update the list to include the block being inserted in the correct */ \
	/* position. */ \
	pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock; \
	pxIterator->pxNextFreeBlock = pxBlockToInsert; \
	}
	/-----------------------------------------------------------/

	void *pvPortMalloc( size_t xWantedSize )
	{
	BlockLink_t pxBlock, pxPreviousBlock, *pxNewBlockLink;
	static BaseType_t xHeapHasBeenInitialised = pdFALSE;
	void *pvReturn = NULL;

	vTaskSuspendAll();
	{
	/* If this is the first call to malloc then the heap will require
	initialisation to setup the list of free blocks. */
	if( xHeapHasBeenInitialised == pdFALSE )
	{
	prvHeapInit();
	xHeapHasBeenInitialised = pdTRUE;
	}

	/* The wanted size is increased so it can contain a BlockLink_t
	structure in addition to the requested amount of bytes. */
	if( xWantedSize > 0 )
	{
	xWantedSize += heapSTRUCT_SIZE;

	/* Ensure that blocks are always aligned to the required number of bytes. */
	if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
	{
	/* Byte alignment required. */
	xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
	}
	}

	if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
	{
	/* Blocks are stored in byte order - traverse the list from the start
	(smallest) block until one of adequate size is found. */
	pxPreviousBlock = &xStart;
	pxBlock = xStart.pxNextFreeBlock;
	while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
	{
	pxPreviousBlock = pxBlock;
	pxBlock = pxBlock->pxNextFreeBlock;
	}

	/* If we found the end marker then a block of adequate size was not found. */
	if( pxBlock != &xEnd )
	{
	/* Return the memory space - jumping over the BlockLink_t structure
	at its start. */
	pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );

	/* This block is being returned for use so must be taken out of the
	list of free blocks. */
	pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

	/* If the block is larger than required it can be split into two. */
	if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
	{
	/* This block is to be split into two. Create a new block
	following the number of bytes requested. The void cast is
	used to prevent byte alignment warnings from the compiler. */
	pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );

	/* Calculate the sizes of two blocks split from the single
	block. */
	pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
	pxBlock->xBlockSize = xWantedSize;

	/* Insert the new block into the list of free blocks. */
	prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
	}

	xFreeBytesRemaining -= pxBlock->xBlockSize;
	}
	}

	traceMALLOC( pvReturn, xWantedSize );
	}
	( void ) xTaskResumeAll();

	#if( configUSE_MALLOC_FAILED_HOOK == 1 )
	{
	if( pvReturn == NULL )
	{
	extern void vApplicationMallocFailedHook( void );
	vApplicationMallocFailedHook();
	}
	}
	#endif

	return pvReturn;
	}
	/-----------------------------------------------------------/

	void vPortFree( void *pv )
	{
	uint8_t puc = ( uint8_t ) pv;
	BlockLink_t *pxLink;

	if( pv != NULL )
	{
	/* The memory being freed will have an BlockLink_t structure immediately
	before it. */
	puc -= heapSTRUCT_SIZE;

	/* This unexpected casting is to keep some compilers from issuing
	byte alignment warnings. */
	pxLink = ( void * ) puc;

	vTaskSuspendAll();
	{
	/* Add this block to the list of free blocks. */
	prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
	xFreeBytesRemaining += pxLink->xBlockSize;
	traceFREE( pv, pxLink->xBlockSize );
	}
	( void ) xTaskResumeAll();
	}
	}
	/-----------------------------------------------------------/

	size_t xPortGetFreeHeapSize( void )
	{
	return xFreeBytesRemaining;
	}
	/-----------------------------------------------------------/

	void vPortInitialiseBlocks( void )
	{
	/* This just exists to keep the linker quiet. */
	}
	/-----------------------------------------------------------/

	static void prvHeapInit( void )
	{
	BlockLink_t *pxFirstFreeBlock;
	uint8_t *pucAlignedHeap;

	/* Ensure the heap starts on a correctly aligned boundary. */
	pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ( portPOINTER_SIZE_TYPE ) ~portBYTE_ALIGNMENT_MASK ) );

	/* xStart is used to hold a pointer to the first item in the list of free
	blocks. The void cast is used to prevent compiler warnings. */
	xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
	xStart.xBlockSize = ( size_t ) 0;

	/* xEnd is used to mark the end of the list of free blocks. */
	xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
	xEnd.pxNextFreeBlock = NULL;

	/* To start with there is a single free block that is sized to take up the
	entire heap space. */
	pxFirstFreeBlock = ( void * ) pucAlignedHeap;
	pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
	pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
	}
	/-----------------------------------------------------------/