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_BLOCK_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---------遍歷所有已分配節點找出分配節點之間最大剩餘一個區域的位元組數，並與最後一節點后剩餘的內存比較，找出最大的剩餘一塊內存位元組數。