（转）UCGUI的动态内存分配的原理深入分析

好东东，顶！
……………………………………………………………………………………………………………………

了解UCGUI的朋友，一定知道UCGUI中的窗口体系，窗口一般都是由程序动态创建的，那么这当中当然要用到动态的内存申请，现在我们就来就这个话题进行深入分析，了解UCGUI中的动态内存分配，是了解其窗口体系统的基础，这一点非常的重要。

先说明一下本文中用到的一些关键下词：

[内存分配信息节点]--------记录一块已分配内存块信息的tBlock结构体，可简称分配节点。

[内存分配信息节点数组]---内存分配信息节点的数组。

[内存句柄]-------------------是指分配内存块数组中的元素位置索引值。

[最小粒度对齐]-------------是指内存分配大小应该为最小粒度的整数倍。



一，打开动态分配的预定义选项。

在GUIConf.h配制文件当中，有这样一个定义。

#define GUI_ALLOC_SIZE 12500 /* Size of dynamic memory ... For WM and memory devices*/

GUI_ALLOC_SIZE定义的即是整个UCGUI中可用于动态分配的内存大小，这个大小且不能为0，也只有当这个预定义打开后，才能使用UCGUI提供的动态内存分配的功能在GUIAlloc.c文件中提供。

二，动态内存分配的基本功能。

在GUI.h中一段提供了如下一段定义，即：

/*********************************************************************

*

* Dynamic memory management

*

**********************************************************************

*/

#if !defined(GUI_ALLOC_ALLOC)

void GUI_ALLOC_Init(void);

void* GUI_ALLOC_h2p (GUI_HMEM hMem);

void GUI_ALLOC_Free (GUI_HMEM hMem);

void GUI_ALLOC_FreePtr (GUI_HMEM *phMem);

GUI_HMEM GUI_ALLOC_Alloc(int size);

/* diagnostics */

int GUI_ALLOC_GetUsed(void);

int GUI_ALLOC_GetNumFreeBytes(void);

int GUI_ALLOC_GetMaxSize(void);

/* macros */

#define GUI_ALLOC_ALLOC(size) GUI_ALLOC_Alloc(size)

#define GUI_ALLOC_H2P(h) GUI_ALLOC_h2p(h)

#define GUI_ALLOC_FREE(handle) GUI_ALLOC_Free(handle)

#define GUI_ALLOC_LOCK(handle) GUI_ALLOC_h2p(handle)

#define GUI_ALLOC_UNLOCK(handle)

#endif

总的来说，动态内存分配提供了如下几组功能：

1，动态内存初始化。

[GUI_ALLOC_Init]



2，动态内存分配、释放、加解锁；以及碎片整理。

[GUI_ALLOC_Free/GUI_ALLOC_Alloc]、[GUI_ALLOC_LOCK/GUI_ALLOC_UNLOCK]



3，动态内存使用情况统计。

[GUI_ALLOC_GetUsed]、[GUI_ALLOC_GetNumFreeBytes]、[GUI_ALLOC_GetMaxSize]

三 动态内存分配的实现原理。

1，首先介绍几个有关动态内存分配的常量及结构。

----常量

GUI_ALLOC_SIZE------------------可用于分配的大小,如开启动态内存分配，在预定义中已经规定必须大于0，否则编译无法通过。



GUI_ALLOC_AUTDEFRAG-------------是否进行碎片整理，只有在请求在内存不能满足时才须要将碎片整理，须将所有已分配内存数据前移，例 如总共大小为12500，当内配到最后剩200字节，但请求800字节，此时如果定义了碎片整理，则会将之前未用碎片整理出来，将所有已分配的内存都往前移，将碎片整到后面合成一个大的剩余空间。

GUI_BLOCK_ALIGN-----------------内存分配的对齐值，是为保证每块分配的内存均从对齐粒度开始，其值为4个字节。如要求29~31字节则实 得32字节，即(29+3)&0xfffffffc，这是在Size2LegalSize完成的。

GUI_MAXBLOCKS-------------------最多可分的内存块数，是内存分配信息记录数组的大小，它决定了将内存正好分配完时每块的最小数值， 这个最小数值为32，在后面中我们称其每一元素为[内存分配信息节点]

tALLOCINT-----------------------记录每块内存偏移内存起始点的依稀的变量类型，2字节还是4字节，GUI_ALLOC_SIZE大于32767时，要用 四字节类型。

HANDLE--------------------------内存块句柄类型，1字节还是2字节，当GUI_MAXBLOCKS大于256时要用2字节。

#if GUI_ALLOC_SIZE <32767

#define tALLOCINT I16

#else

#define tALLOCINT I32

#endif

#if GUI_MAXBLOCKS >= 256

#define HANDLE U16

#else

#define HANDLE U8

#endif

tALLOCINT，HANDLE的定义会影响到用记载每一块内存的信息结点的大小，即用于动态内存分配的开消。

----结构

记录每个内存块信息的节点结构。

typedef struct {

tALLOCINT Off; /* Offset of memory area */

tALLOCINT Size; /* usable size of allocated block */

HANDLE Next; /* next handle in linked list */

HANDLE Prev;

} tBlock;

[Off]------------------------记录此块内存相对整个内存起始点的偏移。

[Size]----------------------记录此块内存大小。

[Next]----------------------记录此块内存之一下一块内存之指针，其实为这里是指下一块内存在内存分配信息记录数组中的

第几个元素。

[Prev]----------------------记录此块内存之上一内存之指针。

[下面这个结构的定义在GUI.h当中]

typedef union {

int aintHeap[GUI_ALLOC_SIZE/4]; /* required for proper alignement */

U8 abHeap[GUI_ALLOC_SIZE];

} GUI_HEAP;

GUI_HEAP GUI_Heap; /* Public for debugging only */

static tBlock aBlock[GUI_MAXBLOCKS];

从上面，可以知道，UCGUI中的内存分配，其实质是通过一大块全局数组的空间来实现的，这个内存是在编译程序后分配的。它的大小是即是在GUIConf.h中预定义的GUI_ALLOC_SIZE个字节，但同时通过GUI_HEAP这个联合，以abHeap来访问是基于1字节，[aintHeap]则是基于4字节。

aBlock是用于记录所有内存分配块的数组，大小是GUI_MAXBLOCKS，GUI_MAXBLOCKS=(2+GUI_ALLOC_SIZE/32)，每一个元素记录一个内存分配块的信息，只要知道了内存分配块的位置就可以从数组中取出该分配块的信息。其实所有的内存分配块不光记录在这一数姐中，而且已经构成了一个双链表，这对于遍历所有已经分配的内存块非常的方便。

struct {

int NumUsedBlocks, NumFreeBlocks, NumFreeBlocksMin; /* For statistical purposes only */

tALLOCINT NumUsedBytes, NumFreeBytes, NumFreeBytesMin;

} GUI_ALLOC;

以上的结构记录每次进行内存分配后的[已用块]、[空闲块]、[最小空闲块]、[已分配字节]、[剩余字节]、[最小空闲字节]。其实最小空闲块与最小空闲字节与空闲块、剩余字节用处差不多，其值是相等的。

2，实现动态内存分配的函数详解。

-----初始化

void GUI_ALLOC_Init(void);

主要初始化GUI_ALLOC这个整体内存分配信息结构，并置已经初始化状态，初始化了第一个内存分配结点：

aBlock[0].Size = (1<<GUI_BLOCK_ALIGN); /* occupy minimum for a block */

aBlock[0].Off = 0;

aBlock[0].Next = 0;



注意这个结点其实是用于双链表的头结点，其大小为最小分配对齐粒度，偏移是0即从整个动态内存的起始。它一直存在，并不会被释放或者改变大小，总之是不会有任何变化，当所有块都分配完或是释放掉，它都是头结点。其实它的作用就是为了维护内存分配信息节点双链表的。

-----分配

GUI_HMEM GUI_ALLOC_Alloc(int size)；

这个函数，它实际是调用_Alloc进行内存分配的，这个函数主要完成以下所做的。

[1]、调用Size2LegalSize将要分配内存大小调整至最小粒度对齐。

[2]、寻找可用于记录此块分配信息的节点，在FindFreeHandle中完成。

[3]、寻找在整个内存分配空间中从低至高可满足此次分配的区域，在FindHole中完成，有几种情况，将在FindHole说明。

[4]、如果剩余字节不够分配，当预定义碎片整理时，调用CreateHole进行整理，CreateHole反回分配信息节点。

[5]、将分配所取得的内存分配信息节点加入双链表、初始化此次分配内存为0值、更新GUI_ALLOC这个整体分配结构体信息。

[Size2LegalSize]

size = (size + ((1<<GUI_BLOC

K_ALIGN)-1)) & ~((1<<GUI_BLOCK_ALIGN)-1);

此函数主要是将要分配的大小调整为最小粒度对齐, 这种对齐所用的方法很普遍，即将要调整的值加上一个值产生一个最小粒度的进位，再将余位通过与的法清除。所加之值即为最小粒度减一，所与之值即为最小料度减一求反。

[FindFreeHandle]

这个函数很简单，即从内存分配信息节点数组aBlock中找出未用的节点(即.sise为0)，注意是从节点1开始找，节点0已经使用了。如果找不到返回GUI_HMEM_NULL(0), GUI_ALLOC_Alloc检测到此值时即返回已分配内存句柄为0。GUI_ALLOC_H2P中转换此内存句句柄时，如检测到内存句柄为0，则会返回此内存句柄真内对应内存地址值为0。

[FindHole]

遍历双链表中的所有已分配节点，以找到此次要分配的内存的区域，有两种情况：

[1]、所找到的区域在已分配节之间；这种情况在最开始分配内存之时不会发生，发生这种情况是指在释放过内存之后再分配新的内存之时,查找时其实是根据后一分配结点偏移减去前一分配结点偏移加上大小之值，即 aBlock[iNext].Off- (aBlock[i].Off+aBlock[i].Size), 看后一结点与前一点之间有无间隙，且此间隙是否满足此次分配。这种间隙其实就是由释放内存块后引起的。

[2]、所找到的区域在所有已分配节点之后，在已分配节点之间找不到合适的区域，那么就只能从剩余的空间中取，取时要判断剩余空间是否足够，不够才返回-1。

FindHole找到可满足分配的区域时，其返回值是可分配区域的最邻近区域的内存句柄。即分配节点的在节点数中的位置索引。

[CreateHole]

FindHole中如果找不到合适的区域可满足分配的话，返回-1，此时我们遇到的情况是，在全部内存中没有一整块如此大的内存能满足此次分配，无法满足分配的原因可能是由于过多的小的内存分配释放后形成了碎片，这些碎版夹杂在整个内存之间，所以可采取的解决办法就是将这些碎片合在一处，形成一块大的内存，在整理碎版，CreateHole要完成如下两件事：

[1]、首先要从已分配节点中找出间隙，找出间隙的方法就是 space = aBlock[iNext].Off- (aBlock[i].Off+aBlock[i].Size), 当space小于要分配的内存大小， 经将是整理的对象。

[2]、整理的方法，要整理出碎片空间，要保证已分配内存的数据和正常访问，所以在将有间隙的两个节点的后一节点数据前移，并调整后一节点的偏移，这是注意点的地方。

[3]、最后此次内存是在所有已分配节点之后的，当 GUI_ALLOC_SIZE - (aBlock[i].Off+aBlock[i].Size) >= Size 这个条件满足，即调整碎片后所得的剩余空间满足此次分配，那么就返回i值，i值即为双链表中最后一结点；如果调整碎片后还是无法满足些次分配，那上面那个条件不成立，那么还是返回-1，即此次分配失败。

总结：关于碎片整理，是比较花时间的，这个时间也每次可以都不确定。

-----释放

释放与分配比起来，所做的工作少多了。

[GUI_ALLOC_Free]与GUI_ALLOC_FreePtr，两者完成同样功能，参数不同而已。

[1]、根据参数中指定中的内存句柄，将些内存句柄指对应分配节点size清零，对应内存清为0xcc,并将节点从双链表中清除。

[2]、更新GUI_ALLOC中记录的整体内存使用情况信息。

-----整体内存使用情况获取

这一组函数比较简单，只作简短说明，它的信息基本上从GUI_ALLOC这个结构中取得。

GUI_GetUsedMem---------------获取已用内存字节数NumUsedBytes。

GUI_ALLOC_GetNumFreeBytes----获取剩余内存字节数NumFreeBytes。

GUI_ALLOC_GetMaxSize---------遍历所有已分配节点找出分配节点之间最大剩余一个区域的字节数，并与最后一节点后剩余的内存比较，找出最大的剩余一块内存字节数。