heap_2.c

00001 /*
00002     FreeRTOS V8.2.1 - Copyright (C) 2015 Real Time Engineers Ltd.
00003     All rights reserved
00004 
00005     VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.
00006 
00007     This file is part of the FreeRTOS distribution.
00008 
00009     FreeRTOS is free software; you can redistribute it and/or modify it under
00010     the terms of the GNU General Public License (version 2) as published by the
00011     Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception.
00012 
00013     ***************************************************************************
00014     >>!   NOTE: The modification to the GPL is included to allow you to     !<<
00015     >>!   distribute a combined work that includes FreeRTOS without being   !<<
00016     >>!   obliged to provide the source code for proprietary components     !<<
00017     >>!   outside of the FreeRTOS kernel.                                   !<<
00018     ***************************************************************************
00019 
00020     FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
00021     WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00022     FOR A PARTICULAR PURPOSE.  Full license text is available on the following
00023     link: http://www.freertos.org/a00114.html
00024 
00025     ***************************************************************************
00026      *                                                                       *
00027      *    FreeRTOS provides completely free yet professionally developed,    *
00028      *    robust, strictly quality controlled, supported, and cross          *
00029      *    platform software that is more than just the market leader, it     *
00030      *    is the industry's de facto standard.                               *
00031      *                                                                       *
00032      *    Help yourself get started quickly while simultaneously helping     *
00033      *    to support the FreeRTOS project by purchasing a FreeRTOS           *
00034      *    tutorial book, reference manual, or both:                          *
00035      *    http://www.FreeRTOS.org/Documentation                              *
00036      *                                                                       *
00037     ***************************************************************************
00038 
00039     http://www.FreeRTOS.org/FAQHelp.html - Having a problem?  Start by reading
00040     the FAQ page "My application does not run, what could be wrong?".  Have you
00041     defined configASSERT()?
00042 
00043     http://www.FreeRTOS.org/support - In return for receiving this top quality
00044     embedded software for free we request you assist our global community by
00045     participating in the support forum.
00046 
00047     http://www.FreeRTOS.org/training - Investing in training allows your team to
00048     be as productive as possible as early as possible.  Now you can receive
00049     FreeRTOS training directly from Richard Barry, CEO of Real Time Engineers
00050     Ltd, and the world's leading authority on the world's leading RTOS.
00051 
00052     http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
00053     including FreeRTOS+Trace - an indispensable productivity tool, a DOS
00054     compatible FAT file system, and our tiny thread aware UDP/IP stack.
00055 
00056     http://www.FreeRTOS.org/labs - Where new FreeRTOS products go to incubate.
00057     Come and try FreeRTOS+TCP, our new open source TCP/IP stack for FreeRTOS.
00058 
00059     http://www.OpenRTOS.com - Real Time Engineers ltd. license FreeRTOS to High
00060     Integrity Systems ltd. to sell under the OpenRTOS brand.  Low cost OpenRTOS
00061     licenses offer ticketed support, indemnification and commercial middleware.
00062 
00063     http://www.SafeRTOS.com - High Integrity Systems also provide a safety
00064     engineered and independently SIL3 certified version for use in safety and
00065     mission critical applications that require provable dependability.
00066 
00067     1 tab == 4 spaces!
00068 */
00069 
00070 /*
00071  * A sample implementation of pvPortMalloc() and vPortFree() that permits
00072  * allocated blocks to be freed, but does not combine adjacent free blocks
00073  * into a single larger block (and so will fragment memory).  See heap_4.c for
00074  * an equivalent that does combine adjacent blocks into single larger blocks.
00075  *
00076  * See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the
00077  * memory management pages of http://www.FreeRTOS.org for more information.
00078  */
00079 #include <stdlib.h>
00080 
00081 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
00082 all the API functions to use the MPU wrappers.  That should only be done when
00083 task.h is included from an application file. */
00084 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
00085 
00086 #include "FreeRTOS.h"
00087 #include "task.h"
00088 
00089 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
00090 
00091 /* A few bytes might be lost to byte aligning the heap start address. */
00092 #define configADJUSTED_HEAP_SIZE    ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )
00093 
00094 /*
00095  * Initialises the heap structures before their first use.
00096  */
00097 static void prvHeapInit( void );
00098 
00099 /* Allocate the memory for the heap. */
00100 static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
00101 
00102 /* Define the linked list structure.  This is used to link free blocks in order
00103 of their size. */
00104 typedef struct A_BLOCK_LINK
00105 {
00106     struct A_BLOCK_LINK *pxNextFreeBlock;   /*<< The next free block in the list. */
00107     size_t xBlockSize;                      /*<< The size of the free block. */
00108 } BlockLink_t;
00109 
00110 
00111 static const uint16_t heapSTRUCT_SIZE   = ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );
00112 #define heapMINIMUM_BLOCK_SIZE  ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )
00113 
00114 /* Create a couple of list links to mark the start and end of the list. */
00115 static BlockLink_t xStart, xEnd;
00116 
00117 /* Keeps track of the number of free bytes remaining, but says nothing about
00118 fragmentation. */
00119 static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;
00120 
00121 /* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */
00122 
00123 /*
00124  * Insert a block into the list of free blocks - which is ordered by size of
00125  * the block.  Small blocks at the start of the list and large blocks at the end
00126  * of the list.
00127  */
00128 #define prvInsertBlockIntoFreeList( pxBlockToInsert )                               \
00129 {                                                                                   \
00130 BlockLink_t *pxIterator;                                                                \
00131 size_t xBlockSize;                                                                  \
00132                                                                                     \
00133     xBlockSize = pxBlockToInsert->xBlockSize;                                       \
00134                                                                                     \
00135     /* Iterate through the list until a block is found that has a larger size */    \
00136     /* than the block we are inserting. */                                          \
00137     for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
00138     {                                                                               \
00139         /* There is nothing to do here - just iterate to the correct position. */   \
00140     }                                                                               \
00141                                                                                     \
00142     /* Update the list to include the block being inserted in the correct */        \
00143     /* position. */                                                                 \
00144     pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;                 \
00145     pxIterator->pxNextFreeBlock = pxBlockToInsert;                                  \
00146 }
00147 /*-----------------------------------------------------------*/
00148 
00149 void *pvPortMalloc( size_t xWantedSize )
00150 {
00151 BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
00152 static BaseType_t xHeapHasBeenInitialised = pdFALSE;
00153 void *pvReturn = NULL;
00154 
00155     vTaskSuspendAll();
00156     {
00157         /* If this is the first call to malloc then the heap will require
00158         initialisation to setup the list of free blocks. */
00159         if( xHeapHasBeenInitialised == pdFALSE )
00160         {
00161             prvHeapInit();
00162             xHeapHasBeenInitialised = pdTRUE;
00163         }
00164 
00165         /* The wanted size is increased so it can contain a BlockLink_t
00166         structure in addition to the requested amount of bytes. */
00167         if( xWantedSize > 0 )
00168         {
00169             xWantedSize += heapSTRUCT_SIZE;
00170 
00171             /* Ensure that blocks are always aligned to the required number of bytes. */
00172             if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
00173             {
00174                 /* Byte alignment required. */
00175                 xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
00176             }
00177         }
00178 
00179         if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
00180         {
00181             /* Blocks are stored in byte order - traverse the list from the start
00182             (smallest) block until one of adequate size is found. */
00183             pxPreviousBlock = &xStart;
00184             pxBlock = xStart.pxNextFreeBlock;
00185             while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
00186             {
00187                 pxPreviousBlock = pxBlock;
00188                 pxBlock = pxBlock->pxNextFreeBlock;
00189             }
00190 
00191             /* If we found the end marker then a block of adequate size was not found. */
00192             if( pxBlock != &xEnd )
00193             {
00194                 /* Return the memory space - jumping over the BlockLink_t structure
00195                 at its start. */
00196                 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );
00197 
00198                 /* This block is being returned for use so must be taken out of the
00199                 list of free blocks. */
00200                 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
00201 
00202                 /* If the block is larger than required it can be split into two. */
00203                 if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
00204                 {
00205                     /* This block is to be split into two.  Create a new block
00206                     following the number of bytes requested. The void cast is
00207                     used to prevent byte alignment warnings from the compiler. */
00208                     pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
00209 
00210                     /* Calculate the sizes of two blocks split from the single
00211                     block. */
00212                     pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
00213                     pxBlock->xBlockSize = xWantedSize;
00214 
00215                     /* Insert the new block into the list of free blocks. */
00216                     prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
00217                 }
00218 
00219                 xFreeBytesRemaining -= pxBlock->xBlockSize;
00220             }
00221         }
00222 
00223         traceMALLOC( pvReturn, xWantedSize );
00224     }
00225     ( void ) xTaskResumeAll();
00226 
00227     #if( configUSE_MALLOC_FAILED_HOOK == 1 )
00228     {
00229         if( pvReturn == NULL )
00230         {
00231             extern void vApplicationMallocFailedHook( void );
00232             vApplicationMallocFailedHook();
00233         }
00234     }
00235     #endif
00236 
00237     return pvReturn;
00238 }
00239 /*-----------------------------------------------------------*/
00240 
00241 void vPortFree( void *pv )
00242 {
00243 uint8_t *puc = ( uint8_t * ) pv;
00244 BlockLink_t *pxLink;
00245 
00246     if( pv != NULL )
00247     {
00248         /* The memory being freed will have an BlockLink_t structure immediately
00249         before it. */
00250         puc -= heapSTRUCT_SIZE;
00251 
00252         /* This unexpected casting is to keep some compilers from issuing
00253         byte alignment warnings. */
00254         pxLink = ( void * ) puc;
00255 
00256         vTaskSuspendAll();
00257         {
00258             /* Add this block to the list of free blocks. */
00259             prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
00260             xFreeBytesRemaining += pxLink->xBlockSize;
00261             traceFREE( pv, pxLink->xBlockSize );
00262         }
00263         ( void ) xTaskResumeAll();
00264     }
00265 }
00266 /*-----------------------------------------------------------*/
00267 
00268 size_t xPortGetFreeHeapSize( void )
00269 {
00270     return xFreeBytesRemaining;
00271 }
00272 /*-----------------------------------------------------------*/
00273 
00274 void vPortInitialiseBlocks( void )
00275 {
00276     /* This just exists to keep the linker quiet. */
00277 }
00278 /*-----------------------------------------------------------*/
00279 
00280 static void prvHeapInit( void )
00281 {
00282 BlockLink_t *pxFirstFreeBlock;
00283 uint8_t *pucAlignedHeap;
00284 
00285     /* Ensure the heap starts on a correctly aligned boundary. */
00286     pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
00287 
00288     /* xStart is used to hold a pointer to the first item in the list of free
00289     blocks.  The void cast is used to prevent compiler warnings. */
00290     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
00291     xStart.xBlockSize = ( size_t ) 0;
00292 
00293     /* xEnd is used to mark the end of the list of free blocks. */
00294     xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
00295     xEnd.pxNextFreeBlock = NULL;
00296 
00297     /* To start with there is a single free block that is sized to take up the
00298     entire heap space. */
00299     pxFirstFreeBlock = ( void * ) pucAlignedHeap;
00300     pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
00301     pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
00302 }
00303 /*-----------------------------------------------------------*/
00304