FreeRTOS堆内存管理策略

文章目录

堆内存管理

本文中超链接的设置指向了官网的链接,方便读者更加深入的了解FreeRTOS的内部机制。

RTOS内部自带了5种内存分配方案,其中方案名称为heap1,heap2……heap5, 随着后面数字的递增,方案的复杂性逐渐激增。

下面对这五种内存分配进行概括:

  • heap1:较为简单,仅能静态分配,无法实现动态分配,适合内存一旦创建不在销毁的静态场景,一般用于很小的系统。基本被淘汰了,因为RTOS目前在其他堆管理方案种,增加对静态分配的支持。

  • heap2:基本被heap4替代,目前用的很少。

  • heap3:简单的包装了C语言的malloc和free函数,确保线程安全。

  • heap4:最常用的堆内存管理方案,并相邻的空闲块以避免碎片。包括绝对地址放置选项。

    目前作者从事智能穿戴的开发,智能穿戴行业在目前2021年基本都在使用这个方案。这个方案也是目前中小型系统最常用的方案,最具备学习价值。

  • heap5:根据 heap_4,能够跨越多个非相邻内存区域的堆。

一、 FreeRTOS内存管理简介

每次创建任务、队列、互斥锁、软件定时器、信号量或事件组时,RTOS 内核都需要 RAM。RAM 可以在 RTOS API 对象创建函数中从 RTOS 堆自动动态分配,也可以由应用程序编写者提供

如果 RTOS 对象是动态创建的,那么有时可以使用标准 C 库 malloc() 和 free() 函数来实现此目的,但是**…**

  1. 它们并不总是在嵌入式系统上可用,

  2. 它们占用了宝贵的代码空间,

  3. 它们不是线程安全的,并且

  4. 它们不是确定性的(执行函数所花费的时间会因调用而异)

**…**所以通常需要另一种内存分配实现。

一个嵌入式/实时系统可能具有与另一个非常不同的 RAM 和时序要求 - 因此单个 RAM 分配算法将只适用于应用程序的子集。

为了解决这个问题,FreeRTOS 将内存分配 API 保留在其可移植层中。可移植层位于实现核心 RTOS 功能的源文件之外,允许提供适用于正在开发的实时系统的特定于应用程序的实现。当 RTOS 内核需要 RAM 时,它不会调用 malloc(),而是调用 pvPortMalloc()。当 RAM 被释放时,RTOS 内核不会调用 free(),而是调用 vPortFree()。

FreeRTOS 提供了多种堆管理方案,其复杂性和功能各不相同。也可以提供您自己的堆实现,甚至可以同时使用两个堆实现。同时使用两个堆实现允许将任务堆栈和其他 RTOS 对象放置在快速内部 RAM 中,并将应用程序数据放置在较慢的外部 RAM 中。

二、 RTOS 源代码下载中包含的内存分配实现

FreeRTOS 下载包括五个示例内存分配实现,每个提供的实现都包含在一个单独的源文件中(分别为 heap_1.c、heap_2.c、heap_3.c、heap_4.c 和 heap_5.c),它们位于主 RTOS 源代码下载的 Source/Portable/MemMang目录中. 可以根据需要添加其他实现。这些源文件中的一个应该一次包含在一个项目中[由这些可移植层函数定义的堆将由 RTOS 内核使用,即使使用 RTOS 的应用程序选择使用自己的堆实现]。

如下:

  • heap_1 - 最简单的,不允许释放内存。
  • heap_2 - 允许释放内存,但不合并相邻的空闲块。
  • heap_3 - 简单地包装标准 malloc() 和 free() 以确保线程安全。
  • heap_4 - 合并相邻的空闲块以避免碎片。包括绝对地址放置选项。
  • heap_5 - 根据 heap_4,能够跨越多个非相邻内存区域的堆。

ps:

  • heap_1 不太有用,因为 FreeRTOS 添加了对静态分配的支持
  • heap_2 现在被认为是遗留的,因为较新的 heap_4 实现是首选。

heap1概述

heap_1.c heap_1 不太有用,因为 FreeRTOS 添加了对静态分配的支持

heap_1 是最简单的实现。它容许一旦被分配到被释放的内存。尽管如此,heap_1.c 适用于大量嵌入式应用程序。这是因为许多小型且深度嵌入的应用程序会在系统启动时创建所有所需的任务、队列、信号量等,然后在程序的生命周期内使用所有这些对象(直到应用程序再次关闭或重新启动) )。什么都不会被删除。

该实现只是在请求 RAM 时将单个阵列细分为更小的块。数组的总大小(堆的总大小)由 configTOTAL_HEAP_SIZE 设置 - 它在 FreeRTOSConfig.h 中定义。提供configAPPLICATION_ALLOCATED_HEAP FreeRTOSConfig.h 配置常量以允许将堆放置在内存中的特定地址。

xPortGetFreeHeapSize() API 函数返回未分配的堆空间总量,允许优化 configTOTAL_HEAP_SIZE 设置。

heap_1 适用场景:

  • 如果您的应用程序从不删除任务、队列、信号量、互斥锁等(实际上涵盖了使用 FreeRTOS 的大多数应用程序),则可以使用。

  • 总是确定性的(总是花费相同的时间来执行)并且不会导致内存碎片。

  • 非常简单,从静态分配的数组分配内存,这意味着它通常适用于不允许真正动态内存分配的应用程序。


heap2概述

heap_2.c heap_2 现在被认为是遗留的,因为 heap_4 是首选。

heap_2 使用最佳拟合算法,并且与方案 1 不同,它允许释放先前分配的块。它并相邻的空闲块合并成一个单一的大的块。有关执行无合并块的实现,请参见 heap_4.c。

可用堆空间的总量由 configTOTAL_HEAP_SIZE 设置 - 它在 FreeRTOSConfig.h 中定义。提供configAPPLICATION_ALLOCATED_HEAP FreeRTOSConfig.h 配置常量以允许将堆放置在内存中的特定地址。

xPortGetFreeHeapSize() API 函数返回未分配的堆空间总量(允许优化 configTOTAL_HEAP_SIZE 设置),但不提供有关如何将未分配的内存分成更小的块的信息。

适用场景:

  • 即使在应用程序重复删除任务、队列、信号量、互斥体等时也可以使用,以下关于内存碎片的警告。

  • 如果不是如果被分配和释放内存使用是随机的大小。例如:

    • 如果应用程序动态创建和删除任务,并且分配给正在创建的任务的堆栈大小始终相同,那么在大多数情况下可以使用 heap2.c。但是,如果分配给正在创建的任务的堆栈大小并不总是相同,那么可用的空闲内存可能会碎片化为许多小块,最终导致分配失败。在这种情况下,heap_4.c 将是更好的选择。

    • 如果应用程序动态创建和删除队列,并且每种情况下队列存储区都相同(队列存储区是队列项大小乘以队列长度),那么大多数情况下可以使用heap_2.c。但是,如果每种情况下的队列存储区域都不相同,那么可用的空闲内存可能会分成许多小块,最终导致分配失败。在这种情况下,heap_4.c 将是更好的选择。

    • 该应用程序直接调用 pvPortMalloc() 和 vPortFree(),而不仅仅是通过其他 FreeRTOS API 函数间接调用。

  • 如果您的应用程序以不可预测的顺序排队、任务、信号量、互斥体等,可能会导致内存碎片问题。这对于几乎所有应用程序来说都是不太可能的,但应该牢记在心。

  • 不是确定性的 - 但比大多数标准 C 库 malloc 实现更有效。

heap_2.c 适用于许多必须动态创建对象的小型实时系统。有关将空闲内存块组合成单个更大块的类似实现,请参见 heap_4。


heap3概述

heap_3.c 这为标准 C 库 malloc() 和 free() 函数实现了一个简单的包装器,在大多数情况下,您选择的编译器会提供这些函数。包装器只是使 malloc() 和 free() 函数线程安全。

这个实现:

  • 需要链接器设置堆,编译器库提供 malloc() 和 free() 实现。

  • 不是确定性的。

  • 可能会大大增加 RTOS 内核代码的大小。

请注意,当使用 heap_3 时,FreeRTOSConfig.h 中的 configTOTAL_HEAP_SIZE 设置无效。


heap4-最常用的内存分配算法

heap_4.c 该方案使用首次拟合算法,并且与方案 2 不同,它确实将相邻的空闲内存块合并为一个大块(它确实包含合并算法)。

可用堆空间的总量由 configTOTAL_HEAP_SIZE 设置 - 它在 FreeRTOSConfig.h 中定义。提供configAPPLICATION_ALLOCATED_HEAP FreeRTOSConfig.h 配置常量以允许将堆放置在内存中的特定地址。

xPortGetFreeHeapSize() API 函数返回调用该函数时未分配的堆空间总量,而 xPortGetMinimumEverFreeHeapSize() API 函数返回 FreeRTOS 应用程序启动时已存在系统的最小可用堆空间量。这两个函数都没有提供有关如何将未分配的内存分成更小的块的信息。

vPortGetHeapStats() API 函数提供附加信息。它填充 heap_t 结构的成员,如下所示。

/* vPortGetHeapStats() 函数的原型。*/ 
void vPortGetHeapStats( HeapStats_t *xHeapStats ); 

/* Heap_stats_t 结构的定义。*/ 
typedef struct xHeapStats 
{ 
	size_t xAvailableHeapSpaceInBytes;      /* 当前可用的总堆大小 - 这是所有空闲块的总和,而不是可以分配的最大块。*/ 
	size_t xSizeOfLargestFreeBlockInBytes; 	/* 调用 vPortGetHeapStats() 时堆内所有空闲块的最大大小(以字节为单位)。*/ 
	size_t xSizeOfSmallestFreeBlockInBytes; /* 调用 vPortGetHeapStats() 时堆内所有空闲块的最小大小(以字节为单位)。*/ 
	size_t xNumberOfFreeBlocks;		/* 调用 vPortGetHeapStats() 时堆内的空闲内存块数。*/ 
	size_t xMinimumEverFreeBytesRemaining;	/* 自系统启动以来堆中的最小总空闲内存量(所有空闲块的总和)。*/ 
	size_t xNumberOfSuccessfulAllocations;	/* 已返回有效内存块的 pvPortMalloc() 调用次数。*/ 
	size_t xNumberOfSuccessfulFrees;	/* 成功释放内存块的 vPortFree() 调用次数。*/ 
} HeapStats_t;

使用场景

  • 即使在应用程序重复删除任务、队列、信号量、互斥体等时也可以使用。

  • 与 heap_2 实现相比,导致堆空间严重碎片化为多个小块的可能性要小得多——即使分配和释放的内存大小是随机的。

  • 不是确定性的 - 但比大多数标准 C 库 malloc 实现更有效。

heap_4.c 对于想要在应用程序代码中直接使用可移植层内存分配方案的应用程序特别有用(而不是通过调用 API 函数本身调用 pvPortMalloc() 和 vPortFree() 间接调用)。


heap5概述

heap_5.c 该方案使用与 heap_4 相同的首次拟合和内存合并算法,并允许堆跨越多个非相邻(非连续)内存区域。

Heap_5 是通过调用 vPortDefineHeapRegions() 初始化的,并且 在 vPortDefineHeapRegions() 执行之后才能使用。创建 RTOS 对象(任务、队列、信号量等)将隐式调用 pvPortMalloc(),因此在使用 heap_5 时,必须在创建任何此类对象之前调用 vPortDefineHeapRegions()。

vPortDefineHeapRegions() 采用单个参数。该参数是一个 HeapRegion_t 结构数组。HeapRegion_t 在portable.h 中定义为

typedef struct HeapRegion 
{ 
    /* 将成为堆一部分的内存块的起始地址。*/ 
    uint8_t *pucStartAddress; 

    /* 内存块的大小。*/ 
    size_t xSizeInBytes; 
堆区域_t;

HeapRegion_t 类型定义

数组使用 NULL 零大小的区域定义终止,数组中定义的内存区域必须按地址顺序出现,从低地址到高地址。以下源代码片段提供了一个示例。的 MSVC的Win32模拟器演示 也用途heap_5所以可以被用作一个参考。

/* 分配两个 RAM 块供堆使用。第一个是
从地址 0x80000000 开始的0x10000 字节块,第二个是
从地址 0x90000000 开始的0xa0000 字节块。从
0x80000000开始的块具有较低的起始地址,因此出现在数组拳头中。*/ 
const HeapRegion_t xHeapRegions[] = 
{ 
    { ( uint8_t * ) 0x80000000UL, 0x10000 }, 
    { ( uint8_t * ) 0x90000000UL, 0xa0000 }, 
    { NULL, 0 } ./*终止数组 */ 
}; 

/* 将数组传递给 vPortDefineHeapRegions()。*/ 
vPortDefineHeapRegions( xHeapRegions );

在定义了堆要使用的内存块后初始化 heap_5

PortGetFreeHeapSize() API 函数返回调用该函数时未分配的堆空间总量,而 xPortGetMinimumEverFreeHeapSize() API 函数返回 FreeRTOS 应用程序启动时已存在系统的最小可用堆空间量。这两个函数都没有提供有关如何将未分配的内存分成更小的块的信息。

所述vPortGetHeapStats() API函数提供在堆上的状态的附加信息。

三、附录内存分配源码

heap堆内存管理主要就是做了二个工作,包装C语言的mallocfree函数。我们可见简单看一眼heap3的代码

void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn;
	// 关闭资源调度器
	vTaskSuspendAll();
	{
		pvReturn = malloc( xWantedSize );
		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 )
{
	if( pv )
	{
		vTaskSuspendAll();
		{
			free( pv );
			traceFREE( pv, 0 );
		}
		( void ) xTaskResumeAll();
	}
}

他就是实现了二个函数 pvPortMalloc and vPortFree。 但是进行了线程安全保护。

  • vTaskSuspendAll 是关闭任务调度。
  • xTaskResumeAll 是重启任务调度。

因为heap5是最复杂的实现,所以我们直接看heap5的代码就好了。

/*
 * FreeRTOS Kernel V10.3.1
 * Copyright (C) 2020 Amazon.com, Inc. or its affiliates.  All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * http://www.FreeRTOS.org
 * http://aws.amazon.com/freertos
 *
 * 1 tab == 4 spaces!
 */

/*
 * A sample implementation of pvPortMalloc() that allows the heap to be defined
 * across multiple non-contigous blocks and combines (coalescences) adjacent
 * memory blocks as they are freed.
 *
 * See heap_1.c, heap_2.c, heap_3.c and heap_4.c for alternative
 * implementations, and the memory management pages of http://www.FreeRTOS.org
 * for more information.
 *
 * Usage notes:
 *
 * vPortDefineHeapRegions() ***must*** be called before pvPortMalloc().
 * pvPortMalloc() will be called if any task objects (tasks, queues, event
 * groups, etc.) are created, therefore vPortDefineHeapRegions() ***must*** be
 * called before any other objects are defined.
 *
 * vPortDefineHeapRegions() takes a single parameter.  The parameter is an array
 * of HeapRegion_t structures.  HeapRegion_t is defined in portable.h as
 *
 * typedef struct HeapRegion
 * {
 *	uint8_t *pucStartAddress; << Start address of a block of memory that will be part of the heap.
 *	size_t xSizeInBytes;	  << Size of the block of memory.
 * } HeapRegion_t;
 *
 * The array is terminated using a NULL zero sized region definition, and the
 * memory regions defined in the array ***must*** appear in address order from
 * low address to high address.  So the following is a valid example of how
 * to use the function.
 *
 * HeapRegion_t xHeapRegions[] =
 * {
 * 	{ ( uint8_t * ) 0x80000000UL, 0x10000 }, << Defines a block of 0x10000 bytes starting at address 0x80000000
 * 	{ ( uint8_t * ) 0x90000000UL, 0xa0000 }, << Defines a block of 0xa0000 bytes starting at address of 0x90000000
 * 	{ NULL, 0 }                << Terminates the array.
 * };
 *
 * vPortDefineHeapRegions( xHeapRegions ); << Pass the array into vPortDefineHeapRegions().
 *
 * Note 0x80000000 is the lower address so appears in the array first.
 *
 */
#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

#if( configSUPPORT_DYNAMIC_ALLOCATION == 0 )
    #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
#endif

/* Block sizes must not get too small. */
#define heapMINIMUM_BLOCK_SIZE	( ( size_t ) ( xHeapStructSize << 1 ) )

/* Assumes 8bit bytes! */
#define heapBITS_PER_BYTE		( ( size_t ) 8 )

/* Define the linked list structure.  This is used to link free blocks in order
of their memory address. */
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;

/*-----------------------------------------------------------*/

/*
 * Inserts a block of memory that is being freed into the correct position in
 * the list of free memory blocks.  The block being freed will be merged with
 * the block in front it and/or the block behind it if the memory blocks are
 * adjacent to each other.
 */
static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert );

/*-----------------------------------------------------------*/

/* The size of the structure placed at the beginning of each allocated memory
block must by correctly byte aligned. */
static const size_t xHeapStructSize	= ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );

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

/* Keeps track of the number of calls to allocate and free memory as well as the
number of free bytes remaining, but says nothing about fragmentation. */
static size_t xFreeBytesRemaining = 0U;
static size_t xMinimumEverFreeBytesRemaining = 0U;
static size_t xNumberOfSuccessfulAllocations = 0;
static size_t xNumberOfSuccessfulFrees = 0;

/* Gets set to the top bit of an size_t type.  When this bit in the xBlockSize
member of an BlockLink_t structure is set then the block belongs to the
application.  When the bit is free the block is still part of the free heap
space. */
static size_t xBlockAllocatedBit = 0;

/*-----------------------------------------------------------*/

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

    /* The heap must be initialised before the first call to
    prvPortMalloc(). */
    configASSERT( pxEnd );

    vTaskSuspendAll();
    {
        /* Check the requested block size is not so large that the top bit is
        set.  The top bit of the block size member of the BlockLink_t structure
        is used to determine who owns the block - the application or the
        kernel, so it must be free. */
        if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
        {
            /* 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 += xHeapStructSize;

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

            if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
            {
                /* Traverse the list from the start	(lowest address) 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 the end marker was reached then a block of adequate size
                was	not found. */
                if( pxBlock != pxEnd )
                {
                    /* Return the memory space pointed to - jumping over the
                    BlockLink_t structure at its start. */
                    pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );

                    /* 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 ) );
                    }
                    else
                    {
                        mtCOVERAGE_TEST_MARKER();
                    }

                    xFreeBytesRemaining -= pxBlock->xBlockSize;

                    if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
                    {
                        xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
                    }
                    else
                    {
                        mtCOVERAGE_TEST_MARKER();
                    }

                    /* The block is being returned - it is allocated and owned
                    by the application and has no "next" block. */
                    pxBlock->xBlockSize |= xBlockAllocatedBit;
                    pxBlock->pxNextFreeBlock = NULL;
                    xNumberOfSuccessfulAllocations++;
                }
                else
                {
                    mtCOVERAGE_TEST_MARKER();
                }
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }

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

    #if( configUSE_MALLOC_FAILED_HOOK == 1 )
    {
        if( pvReturn == NULL )
        {
            extern void vApplicationMallocFailedHook( void );
            vApplicationMallocFailedHook();
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }
    }
    #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 -= xHeapStructSize;

        /* This casting is to keep the compiler from issuing warnings. */
        pxLink = ( void * ) puc;

        /* Check the block is actually allocated. */
        configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
        configASSERT( pxLink->pxNextFreeBlock == NULL );

        if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
        {
            if( pxLink->pxNextFreeBlock == NULL )
            {
                /* The block is being returned to the heap - it is no longer
                allocated. */
                pxLink->xBlockSize &= ~xBlockAllocatedBit;

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

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

size_t xPortGetMinimumEverFreeHeapSize( void )
{
    return xMinimumEverFreeBytesRemaining;
}
/*-----------------------------------------------------------*/

static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
BlockLink_t *pxIterator;
uint8_t *puc;

    /* Iterate through the list until a block is found that has a higher address
    than the block being inserted. */
    for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
    {
        /* Nothing to do here, just iterate to the right position. */
    }

    /* Do the block being inserted, and the block it is being inserted after
    make a contiguous block of memory? */
    puc = ( uint8_t * ) pxIterator;
    if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
    {
        pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
        pxBlockToInsert = pxIterator;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }

    /* Do the block being inserted, and the block it is being inserted before
    make a contiguous block of memory? */
    puc = ( uint8_t * ) pxBlockToInsert;
    if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
    {
        if( pxIterator->pxNextFreeBlock != pxEnd )
        {
            /* Form one big block from the two blocks. */
            pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
            pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
        }
        else
        {
            pxBlockToInsert->pxNextFreeBlock = pxEnd;
        }
    }
    else
    {
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
    }

    /* If the block being inserted plugged a gab, so was merged with the block
    before and the block after, then it's pxNextFreeBlock pointer will have
    already been set, and should not be set here as that would make it point
    to itself. */
    if( pxIterator != pxBlockToInsert )
    {
        pxIterator->pxNextFreeBlock = pxBlockToInsert;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }
}
/*-----------------------------------------------------------*/

void vPortDefineHeapRegions( const HeapRegion_t * const pxHeapRegions )
{
BlockLink_t *pxFirstFreeBlockInRegion = NULL, *pxPreviousFreeBlock;
size_t xAlignedHeap;
size_t xTotalRegionSize, xTotalHeapSize = 0;
BaseType_t xDefinedRegions = 0;
size_t xAddress;
const HeapRegion_t *pxHeapRegion;

    /* Can only call once! */
    configASSERT( pxEnd == NULL );

    pxHeapRegion = &( pxHeapRegions[ xDefinedRegions ] );

    while( pxHeapRegion->xSizeInBytes > 0 )
    {
        xTotalRegionSize = pxHeapRegion->xSizeInBytes;

        /* Ensure the heap region starts on a correctly aligned boundary. */
        xAddress = ( size_t ) pxHeapRegion->pucStartAddress;
        if( ( xAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
        {
            xAddress += ( portBYTE_ALIGNMENT - 1 );
            xAddress &= ~portBYTE_ALIGNMENT_MASK;

            /* Adjust the size for the bytes lost to alignment. */
            xTotalRegionSize -= xAddress - ( size_t ) pxHeapRegion->pucStartAddress;
        }

        xAlignedHeap = xAddress;

        /* Set xStart if it has not already been set. */
        if( xDefinedRegions == 0 )
        {
            /* 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 = ( BlockLink_t * ) xAlignedHeap;
            xStart.xBlockSize = ( size_t ) 0;
        }
        else
        {
            /* Should only get here if one region has already been added to the
            heap. */
            configASSERT( pxEnd != NULL );

            /* Check blocks are passed in with increasing start addresses. */
            configASSERT( xAddress > ( size_t ) pxEnd );
        }

        /* Remember the location of the end marker in the previous region, if
        any. */
        pxPreviousFreeBlock = pxEnd;

        /* pxEnd is used to mark the end of the list of free blocks and is
        inserted at the end of the region space. */
        xAddress = xAlignedHeap + xTotalRegionSize;
        xAddress -= xHeapStructSize;
        xAddress &= ~portBYTE_ALIGNMENT_MASK;
        pxEnd = ( BlockLink_t * ) xAddress;
        pxEnd->xBlockSize = 0;
        pxEnd->pxNextFreeBlock = NULL;

        /* To start with there is a single free block in this region that is
        sized to take up the entire heap region minus the space taken by the
        free block structure. */
        pxFirstFreeBlockInRegion = ( BlockLink_t * ) xAlignedHeap;
        pxFirstFreeBlockInRegion->xBlockSize = xAddress - ( size_t ) pxFirstFreeBlockInRegion;
        pxFirstFreeBlockInRegion->pxNextFreeBlock = pxEnd;

        /* If this is not the first region that makes up the entire heap space
        then link the previous region to this region. */
        if( pxPreviousFreeBlock != NULL )
        {
            pxPreviousFreeBlock->pxNextFreeBlock = pxFirstFreeBlockInRegion;
        }

        xTotalHeapSize += pxFirstFreeBlockInRegion->xBlockSize;

        /* Move onto the next HeapRegion_t structure. */
        xDefinedRegions++;
        pxHeapRegion = &( pxHeapRegions[ xDefinedRegions ] );
    }

    xMinimumEverFreeBytesRemaining = xTotalHeapSize;
    xFreeBytesRemaining = xTotalHeapSize;

    /* Check something was actually defined before it is accessed. */
    configASSERT( xTotalHeapSize );

    /* Work out the position of the top bit in a size_t variable. */
    xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}
/*-----------------------------------------------------------*/

void vPortGetHeapStats( HeapStats_t *pxHeapStats )
{
BlockLink_t *pxBlock;
size_t xBlocks = 0, xMaxSize = 0, xMinSize = portMAX_DELAY; /* portMAX_DELAY used as a portable way of getting the maximum value. */

    vTaskSuspendAll();
    {
        pxBlock = xStart.pxNextFreeBlock;

        /* pxBlock will be NULL if the heap has not been initialised.  The heap
        is initialised automatically when the first allocation is made. */
        if( pxBlock != NULL )
        {
            do
            {
                /* Increment the number of blocks and record the largest block seen
                so far. */
                xBlocks++;

                if( pxBlock->xBlockSize > xMaxSize )
                {
                    xMaxSize = pxBlock->xBlockSize;
                }

                /* Heap five will have a zero sized block at the end of each
                each region - the block is only used to link to the next
                heap region so it not a real block. */
                if( pxBlock->xBlockSize != 0 )
                {
                    if( pxBlock->xBlockSize < xMinSize )
                    {
                        xMinSize = pxBlock->xBlockSize;
                    }
                }

                /* Move to the next block in the chain until the last block is
                reached. */
                pxBlock = pxBlock->pxNextFreeBlock;
            } while( pxBlock != pxEnd );
        }
    }
    xTaskResumeAll();

    pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;
    pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;
    pxHeapStats->xNumberOfFreeBlocks = xBlocks;

    taskENTER_CRITICAL();
    {
        pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;
        pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;
        pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;
        pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;
    }
    taskEXIT_CRITICAL();
}


上一篇:堆排序-heap sort


下一篇:九大排序算法(C++实现)