一種用於嵌入式系統的內存控制方法
2023-07-03 06:09:06
專利名稱：一種用於嵌入式系統的內存控制方法
技術領域：
本發明涉及嵌入式系統技術領域，尤其是涉及嵌入式系統的內存控制方法。
背景技術：
嵌入式系統的內存資源相當有限，故需要對其進行合理的規劃和管理。內存是系統中所有線程運行的基礎，是嵌入式系統最重要的系統資源。簡單、高效的內存組織和管理，是系統穩定、高速運行的保證。嵌入式系統對內存分配要求達到快速性、可靠性和高效性。一種常見的管理方式就是內存池方式。其實現機制是一次性將後續所有應用程式需要使用的內存全部申請下來，切割成各種固定大小的不同數量的內存塊，按照一定的數據結構形成內存池，然後按需進行二次分配。設計內存池的目的是為了保證伺服器長時間高效的運行，通過對申請空間小而申請頻繁的對象進行有效管理，減少內存碎片的產生，合理分配管理用戶內存，從而減少系統中出現有效空間足夠，而無法分配大塊內存的情況。而且內存池實現簡單，分配和回收較快。但是內存池也是存在一定缺點的，所有的進程共享同一個內存池，多個進程的多個任務都在分配釋放內存塊時會競爭同一個鎖，鎖的開銷會大大降低內存管理方式的效率。另外，內存池的控制信息和應用層的內存塊連續存放，一旦發生應用程式內存覆蓋的誤操作，往往會覆蓋內存塊的控制信息，有可能會導致包括系統崩潰在內的嚴重後果。此外，C代碼中指針的應用會帶來內存越界的隱患，經常出現某段內存的內容被修改而導致系統運行異常，可出現異常時只是犯罪現場，無法定位出是誰修改了這段內存。對這些情況，通常的做法，只能是審查代碼，憑經驗找出可能出錯的代碼，進行大量的分析試驗，才能找到真兇。
發明內容
本發明提出了一種內存控制方法，其目的在於增加內存覆蓋檢查機制，提高內存使用效率，減少應用程式內存覆蓋的概率。本發明的技術方案為一種用於嵌入式系統的內存控制方法，從作業系統中申請一塊內存，內存的一部分作為內存池，另一部分作為預留內存區域；內存池採用池式管理，為每個線程配置一個線程緩存；預留內存區域採用TLSF算法管理；
進行內存初始化操作時，執行以下步驟，
步驟I. 1，初始化內存池，包括將內存池切割成不同大小的內存塊，為同等大小的內存塊維護一個內存管理頭結構；為每個內存塊分配一個內存管理單元；
步驟I. 2，初始化預留內存區域，包括按照TLSF算法的數據結構組織預留內存區域，並維護兩個內存管理頭結構，一個用來管理小內存塊，另一個用來管理大內存塊，小內存塊和大內存塊根據預設參數劃分；·步驟I. 3，初始化各線程緩存的內存管理頭結構，為任一線程申請的內存中同等大小的內存塊維護一個內存管理頭結構；
步驟I. 4，初始化每個線程的一個內存統計鍊表，所述內存統計鍊表是用於連接任一線程申請的所有內存塊；
內存池、預留內存區域和各線程緩存的內存管理頭結構均包括空閒內存塊的個數、已使用內存塊的個數、空閒鍊表、已使用鍊表和互斥鎖；內存池和預留內存區域的各內存塊的內存管理單元的域包括內存池雙向鍊表、線程緩存鍊表、內存塊狀態、線程使用內存統計鍊表、內存管理參數和指向內存塊的指針，內存管理參數包括內存塊的大小size，所述內存池雙向鍊表為空閒鍊表或已使用鍊表；預留內存區域中，用來管理小內存塊的內存管理頭結構中已使用鍊表稱為小內存鍊表，預留內存區域中，用來管理大內存塊的內存管理頭結構中已使用鍊表稱為大內存鍊表；
進行內存分配操作時，執行以下步驟，
步驟2. 1，根據應用程式申請的內存大小，向上調整到內存池中切割內存塊的大小，記為目標size ;查看線程緩存對應大小內存塊的空閒鍊表中是否是合適的內存塊，
如果有，將內存塊從線程緩存的空閒鍊表中刪除，掛在線程緩存的已使用鍊表中，並更新該內存塊的內存管理單元的相關信息，包括狀態更新為已使用，並標記為從內存池中分配，返回內存塊的首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配；
否則，進入步驟2. 2;
步驟2. 2，查看內存池中是否有目標size的空閒內存塊，
如果有，將空閒的內存塊從內存池的空閒鍊表中移除，掛在內存池的使用鍊表中，並更新內存管理單元的相關信息，包括狀態更新為已使用，並標記為從內存池中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配；
否則，進入步驟2. 3;
步驟2. 3,查找比目標size大一個size的內存塊，
如果有，將空閒內存塊從內存池的空閒鍊表中移除，掛在內存池的使用鍊表中，並更新內存管理單元的相關信息，尤其是狀態更新為已使用，並標記為從內存池中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配；
否則，根據應用程式申請的內存大小從預留內存區域中申請內存塊，並分配相應的內存管理單元；設置內存管理單元的相關信息，包括狀態為已使用，並標記為從預留內存區域中分配；返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中；根據應用程式申請的內存大小和預設參數，確定申請的內存塊是小內存塊還是大內存塊；如果申請的是小內存塊，將申請的內存塊掛到小內存鍊表中，並更新哈希表的信息，將此內存塊插入到二級哈希結構中，完成分配；如果申請的是大內存塊，將申請的內存塊掛到大內存鍊表中；
進行內存釋放操作時，執行以下步驟，
步驟3. 1，由輸入地址找到對應的內存管理單元；
步驟3. 2，根據內存管理單元中的內存塊狀態域來判斷， 如果是從內存中的內存池申請的，轉入步驟3. 3 ；
如果是從預留內存區域分配的，將內存管理單元從預留內存區域的對應內存管理頭結構的已使用鍊表中刪除，將內存塊從線程的內存統計鍊表中刪除，如果是小內存塊則更新哈希查找結構的信息；並採用TLSF算法的free函數釋放內存塊和相應內存管理單元，完成釋放；
步驟3. 3，將內存管理單元從內存池的使用鍊表中移除，掛到線程緩存的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放；
步驟3. 4，檢查線程緩存中空閒內存塊數目與使用內存塊數目的比值，
如果小於一定閾值，則將內存管理單元從線程緩存的使用鍊表中移除，掛到線程緩存的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放；
否則，將內存管理單元從線程緩存的使用鍊表中移除，掛到內存池的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放。而且，進行內存覆蓋檢查時，對要定位的內存塊執行以下步驟，
步驟4. 1，根據輸入地址判斷該內存塊是在內存池中還是預留內存區域中，
如果是在內存池中，則先定位該內存塊位於哪個size內存塊的範圍，然後取模運行定位內存邊界；
如果是在預留內存區域中，則轉入步驟4. 2 ；
步驟4. 2，遍歷大內存鍊表查找該內存塊，
如果查找到則得到內存邊界，
否則，採用二級哈希算法來定位內存邊界。而且，內存池中，內存管理單元和內存塊分別放在不同的內存區域；預留內存區域中，內存管理單元和內存塊分別放在不同的內存區域。本發明的創新點在於
1.為每個內存塊增加一個內存管理單元，在管理單元中增加了容錯信息，記錄所有與內存分配、回收以及內存塊狀態的信息，實現內存使用狀態監控、內存洩露探測等功能；
2.將數據段和管理單元的內存分離，以防止內存小範圍越界，影響內存管理單元；
3.將內存池與線程緩存技術結合，並啟動主動回收和強制回收機制，避免大量內存碎片的同時，有效地提高了分配的效率，對多線程多進程的系統尤為適用；
4.增加了內存覆蓋檢查機制，設計了一套定位內存邊界的算法，對於非連續的內存塊，以地址為哈希key，通過二級哈希結構來定位，從源頭上杜絕內存覆蓋；
5.由於在內存管理結構中增加了狀態監控、內存洩露等探測功能，在內存申請釋放時加入了使用內存塊的統計信息，對於程序中的內存洩露，可以較快的定位出來。
圖I為本發明實施例中內存池的數據結構 圖2為本發明實施例中內存統計的數據結構 圖3為本發明實施例中內存池中內存塊狀態變化 圖4為本發明實施例中哈希查找結構的地址key劃分 圖5為本發明實施例中哈希查找結構圖。
具體實施例方式 以下結合附圖和實施例詳細說明本發明技術方案。
本發明的內存控制機制適用於共享內存，堆內存等，首先從作業系統中申請一大塊內存，一部分作為內存池，另一部分作為預留內存區域，基於內存池和預留內存區域的內存管理操作具體包括內存初始化、內存分配、內存釋放、緩存回收、內存覆蓋檢查。內存池採用池式管理，結合線程緩存技術，為每個線程建立一個緩存，避免所有線程競爭同一個鎖的情況，並增加主動回收和強制回收機制,保證內存池對其他線程的供應,此機制避免了內存碎片，並有效提高了進程間通信的效率；預留內存區域採用TLSF算法來管理，以避免內存池中空閒內存塊不足的情況，預留一段內存區域。TLSF算法具體實現為現有技術。實施例中，內存初始化操作包括
步驟I. 1，初始化內存池，內存池的數據結構如圖I所示，將此內存切割成多組固定大小的內存塊，每組內存塊字節大小是一致的，如圖I中32位元組的所有內存塊為一組，64位元組的所有內存塊為一組。實施例中每組內存塊的大小為2的冪次方字節，比如第O組內存塊的大小均為32位元組，第I組內存塊的大小均為64位元組，以此類推，第η組內存塊的大小均 為2~ (η+5)。內存區域切割成固定大小的內存塊後，同等大小的內存塊連成雙向鍊表，可採用一個空閒鍊表和一個已使用鍊表。初始化的時候所有內存塊都是掛在空閒鍊表中，已使用的內存塊改為掛在已使用鍊表中。實施例對於相同大小的內存塊，維護一個管理頭結構，記錄空閒內存塊的個數、已使用內存塊的個數、空閒鍊表和已使用鍊表。如圖I中的32位元組管理頭結構、64位元組管理頭結構、128位元組管理頭結構、256位元組管理頭結構等。其中，空閒鍊表連接所有空閒的內存塊，已使用鍊表連接所有已使用的內存塊。管理頭結構還包含一個互斥鎖(mutex域),用於在分配/釋放時，對鍊表的訪問實現多線程的互斥訪問。另外，為每個內存塊建立對應的內存管理單元，用來記錄所有與內存分配、回收相關的信息，實現內存使用狀態監控、內存洩露探測等功能。實施例的內存管理單元中的參數包括
1)內存池雙向鍊表內存池中連結同等大小的內存塊管理單元；
2)線程緩存鍊表線程緩存中連結同等大小的內存塊管理單元；
3)內存塊狀態記錄當前內存塊的使用狀態及所在的區域(內存池或TLSF預留區域)；根據內存塊狀態可知其是否被使用，即可進行重複釋放檢查；
4)內存塊大小記錄當前內存塊可使用的大小，例如圖I中32位元組管理頭結構下的內存管理單元內存塊大小均為32位元組；
5)線程使用內存統計鍊表每個線程會維護圖2的一個統計鍊表表頭，統計各線程的內存使用情況，此項參數是用來連結同一線程申請的內存管理單元，以便隨時可以查看內存使用情況，檢查是否存在內存洩露；
6)內存管理參數包括內存塊申請釋放的時間、申請內存的文件名和函數名，方便出錯時跟蹤內存使用流程；
7)指向內存塊的指針內存塊才是真正返回給應用程式使用的一段內存，在內存管理單元中維護這個指針，主要是為了根據內存管理單元較方便找到對應的內存塊。圖I中的內存塊是實際分配給應用程式使用的一段內存，理論上是按照上述32位元組、64位元組切割即可，為了防止內存越界，在各字節內存塊前後各預留一個紅燈區(Redzonel和Red zone2),保護內存塊。另外，內存塊中還維護一個指針,指向其內存管理單元，方便根據內存塊迅速定位到對應的內存管理單元。內存管理單元和內存塊分別放在內存不同的內存區域，以防止發生應用程式內存覆蓋的誤操作，覆蓋內存塊的內存管理單元，有可能會導致包括系統崩潰在內的嚴重後果。步驟I. 2,初始化預留內存區域，按照TLSF算法(Two Levels Segregate Fitmemory allocator, 二級隔離適應算法)的數據結構將預留內存區域組織起來,並初始化兩個內存管理頭結構，一個用來管理小內存塊，另一個用來管理大內存塊。為方便描述起見，用來管理小內存塊的內存管理頭結構中已使用鍊表稱為小內存鍊表，預留內存區域中，用來管理大內存塊的內存管理頭結構中已使用鍊表稱為大內存鍊表。劃分大小內存塊的預設參數用戶可根據實際需求來設置。區分大小內存塊主要是為了後續的內存覆蓋檢查，哈希查找算法只針對小內存塊，假定小於等於8192位元組的內存塊為小內存，大於8192位元組的內存塊為大內存，那麼對於大內存塊的地址，低13位(2~13=8192)是完全一樣的，如果採用哈希查找算法，哈希衝突太多，很難均勻的散列開來。因此可以初始化用於內存覆蓋檢查的哈希查找頭結構(如圖5中一級哈希桶)。 對於預留內存區域的管理，不是像內存池一樣預先分割好，也沒有緩存機制，而是在申請時從預留內存區域中根據申請需要分配相應大小的內存塊，並分配一個內存管理單元。因此具體實施時，預留內存區域的內存管理頭結構和內存管理單元具體結構與內存池的可以一致，只是空閒鍊表無需使用。預留內存區域中，內存管理單元和內存塊也分別放在不同的內存區域。步驟I. 3，初始化各線程緩存的內存管理頭結構，這個結構同內存池各組內存塊的內存管理頭結構一致，包括空閒內存塊的個數、已使用內存塊的個數、空閒鍊表和已使用鍊表、互斥鎖。線程可能申請不同大小的內存塊，每個線程針對不同字節大小分別建立內存管理頭結構，也是同等大小的內存建立一個內存管理頭結構，如32位元組有一個管理頭結構，64位元組同樣有一個管理頭結構，不同字節大小的管理頭結構用數組來組織。各線程緩存的內存管理頭結構和申請的內存塊的內存管理單元具體結構與內存池的也保持一致。步驟I. 4，初始化各線程的內存統計鍊表(即線程使用內存統計鍊表)的表頭，數據結構如圖2所示，內存統計鍊表頭包括申請的內存塊的總數目、申請的內存塊的總大小、互斥鎖和雙向鍊表。此處雙向鍊表是用來連接所有此線程申請的內存塊，具體是附圖I中的線程內存使用統計鍊表。實施例為每一個線程建立一個內存統計鍊表，用來連接所有此線程申請的內存塊，供內存洩露探測用。申請內存完畢會將內存塊掛到此內存統計鍊表中，記錄該線程申請的所有內存塊，以方便進行內存洩露排查。具體實施時，步驟I. I和步驟I. 2可以不分先後，在進程啟動開始時完成即可，步驟I. I中內存池各內存塊大小及其分布，可通過預設的配置文件來配置；步驟I. 3、步驟I. 4可以不分先後，在線程啟動開始時完成即可。內存分配/釋放操作負責為上層應用程式提供內存分配/釋放的接口，本發明改進了傳統的池式管理機制，將內存池算法與線程緩存技術結合，並預留一段內存採用TLSF算法來管理，以避免內存池中空閒內存塊不足的情況，避免了大量的內存碎片。同時，為每一個線程配置一個緩存，線程分配釋放優先從緩存池中查找，減少了所有線程競爭同一個鎖的開銷，大大提高了分配的效率。本發明分配內存塊時，先檢查線程緩存池中是否有對應固定大小的空閒內存塊，如果有則從線程緩存池中分配內存塊，並更新內存塊的狀態為已使用；如果線程緩存池中沒有對應固定大小的空閒內存塊，則從內存池的空閒鍊表中分配，並更新內存塊的狀態為已使用。如果內存池中某個固定大小的內存塊不能滿足應用程式的需求，則分配大一個size的內存塊；如果內存池中大一個size的內存塊也沒有，則從預留的內存區域中採用TLSF算法來分配內存。TLSF算法採用位圖管理，兩級索引，實現簡單，動態性較強。實施例中內存分配步驟如下
步驟2. 1，根據應用程式申請的內存大小，向上調整到內存池中內存塊的大小，即調整為2的冪次方的大小的內存塊，例如應用程式申請31位元組的內存，則從32位元組的內存塊中查找空閒塊。查看線程緩存對應大小內存塊的空閒鍊表中是否是合適的內存塊，
如果有，將內存塊從線程緩存的空閒鍊表中刪除，掛在線程緩存的已使用鍊表中，並更 新該內存塊的內存管理單元的相關信息，尤其是狀態更新為已使用，並標記為從內存池中分配，返回內存塊的首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配；否則，進入步驟2. 2 ；
步驟2. 2，查看內存池中是否有合適的空閒內存塊，
如果有，將空閒的內存塊從內存池的空閒鍊表中移除，掛在內存池的使用鍊表中，並更新內存管理單元的相關信息，尤其是狀態更新為已使用，並標記為從內存池中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配；
否則，進入步驟2.3 ;
步驟2. 3，查找大一個size的內存塊，即例如32位元組的內存塊已全部使用完，則檢查內存池中64位元組是否有空閒的內存塊，
如果有，將空閒內存塊從內存池的空閒鍊表中移除，掛在內存池的使用鍊表中，並更新內存管理單元的相關信息，尤其是狀態更新為已使用，並標記為從內存池中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配；
否則，說明此時內存池中的對應size的內存塊不夠用，根據應用程式申請的內存大小從預留內存區域中申請內存塊，並分配相應的內存管理單元，；設置內存管理單元的相關信息，包括狀態為已使用，並標記為從預留內存區域中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中。根據應用程式申請的內存大小，確定申請的是小內存塊還是大內存塊。並將申請的內存塊掛到內存管理頭結構的已使用鍊表中。即如果申請的是大內存塊，將申請的內存塊掛到大內存鍊表中；如果申請的是小內存塊，將申請的內存塊掛到小內存鍊表中。如果申請的是小內存塊，則需要更新哈希表的信息，將此內存塊插入到二級哈希結構中，完成分配。本發明釋放內存塊時，檢查線程緩存池的空閒鍊表中是否緩存的內存塊超過一定閾值，如果是，則將內存塊主動還給內存池；否則該內存塊仍緩存在線程緩存池中。實施例內存釋放的步驟如下
步驟3. 1，由輸入地址(內存塊地址)找到對應的內存管理單元；
具體實施時，可以提供內存分配/釋放的庫函數，供應用程式調用。內存釋放的時候，應用程式傳入輸入地址，以確定要釋放哪塊內存。
步驟3. 2，根據內存管理單元中的內存塊狀態域來判斷，
如果是從內存中的內存池申請的，轉入步驟3. 3 ；
如果是從預留內存區域分配的，將內存管理單元從預留內存區域的對應內存管理頭結構的已使用鍊表中刪除，即若釋放的內存塊是大內存塊則從大內存鍊表中刪除，是小內存塊則從小內存鍊表中刪除；將此內存塊從線程的內存統計鍊表中刪除，如果是小內存塊還需要更新哈希查找結構的信息；並採用TLSF算法的free函數釋放內存塊和相應內存管理單兀，完成釋放；
步驟3. 3，將內存管理單元從內存池的使用鍊表中移除，掛到線程緩存的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放；
步驟3. 4，檢查線程緩存中空閒內存塊數目與使用內存塊數目的比值，
如果小於一定閾值，則將內存管理單元從線程緩存的已使用鍊表中移除，掛到線程緩存的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放；
否則，將內存管理單元從線程緩存的已使用鍊表中移除，掛到內存池的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放。用戶可根據實際使用來情況預先設定閾值，實施例中將其設置為I ;
完成釋放即可結束流程。本發明進一步提出，緩存回收過程的實現可同時採用主動回收機制和強制回收機制，釋放內存的時候，會檢查線程緩存中空閒內存塊數目與使用內存塊數目的比值，如果超過閾值(本實施例中為I)則啟動主動回收機制,將內存歸還給內存池。同時維護一個線程專門負責強制回收，如果內存池中空閒內存塊不足，則強制回收線程緩存中的空閒內存塊。實施例中，專門維護一個線程負責強制回收，維護一個全局信號量和全局數組，全局信號量用來喚醒強制回收線程，全局數組用來通知強制回收線程哪個size的內存塊需要強制回收。每次分配內存時檢查內存池中空閒內存的數量,如果全局內存池中空閒內存塊的數量低於設計的閾值，則喚醒一個全局信號量，並將全局數組的對應元素置為1，啟動強制回收機制。強制回收線程一直等待該全局信號量，如果等到信號量，則檢查全局數組各個元素哪個被置I 了，確認哪種size的內存塊需要被強制回收。確認後依次遍歷每個線程緩存中該size的內存管理頭結構，將線程緩存空閒鍊表中的內存管理單元全部移除到相應的全局內存池的空閒鍊表中。回收完成之後，需要將全局數組的該元素清零。綜上所述，內存池中內存塊的狀態變化請參見圖3，內存池初始化完，所有的內存塊均掛在內存池的空閒鍊表下，狀態為空閒；被分配出去之後，該內存塊掛在線程緩存的已使用鍊表下，狀態為已使用；釋放的時候，如果線程緩存的內存塊未超過一定閾值，則將該內存塊移到線程緩存的空閒鍊表下,否則啟動主動回收機制,將該內存塊掛到內存池的空閒鍊表下，狀態為空閒；另外，如果內存池中空閒內存塊低於一定閾值，啟動強制回收機制，會將內存塊從線程緩存的空閒鍊表中移到內存池的空閒鍊表中，狀態為空閒。·
本發明還包含了一種內存覆蓋檢查算法，內存覆蓋檢查的難點就是根據輸入地址定位出可使用的內存塊的起始地址，即內存邊界。內存覆蓋檢查操作通過定位內存塊的起始地址，來檢查是否會出現內存覆蓋。對於內存池，由於內存池中內存塊地址是連續的，可以通過取模運算來定位內存塊的起始地址；對於預留內存區域，由於分配出去的內存地址不連續，採用兩級哈希索引結構來定位內存邊界，以內存地址作為哈希算法的key (關鍵碼)值。本方法無需改動內存管理方案，實用性較強。實施例的內存覆蓋檢查過程包括如下步驟
步驟4. 1，根據輸入地址判斷該內存塊是在內存池中還是預留內存區域中，
如果是在內存池中，則先定位該內存塊位於哪個size塊的範圍，然後取模運行即可定位出內存塊的邊界；
如果是在預留內存區域中，則轉入步驟4.2 ;
步驟4. 2，遍歷大內存鍊表查找該內存塊，
如果查找到則得到內存邊界，
否則，說明該內存塊位於小內存塊鍊表中，對這個鍊表中的內存塊，採用二級哈希算法 來定位內存邊界。本發明實施例以內存地址作為哈希關鍵碼值，將內存地址分為3段，請參見圖4 高几位作為一級哈希的關鍵碼值，中間的幾位作為二級哈希的關鍵碼值，對於一級哈希和二級哈希關鍵碼值具體取值，可依照實際工程中的情況而定，原則上是依據小內存塊的大小分布，儘量減少哈希衝突，使得不同的內存地址均勻的散列開來。本實施例中將小於等於8192位元組的內存塊定義為小內存，針對小於8192位元組的內存塊做哈希運算。由於8192=2~13，所以對於8192位元組的內存塊，其地址低13位是完全一樣的，一級哈希取內存塊地址的高19位(19+13=32)作為其哈希關鍵碼值，通過哈希運算將不同地址的內存塊散列開來。對於一級哈希衝突，採用再哈希法，取其地址的中間8位作為二級哈希關鍵碼值。經過兩級哈希之後，內存地址由於剩下的低5位相同而產生衝突，採用鍊表的方式將其連結起來，衝突鍊表的最大長度為2~5=32，不會影響查找效率。實施例的哈希結構圖請參見圖5,將一級哈希結構用哈希桶來存儲,相同的哈希值用同一個鍊表連起來，對鍊表中的每個節點，做二次哈希，同樣採用哈希桶來存儲，用鍊表來連結哈希衝突值。當然，每次申請、釋放內存塊的時候都必須更新此套哈希結構，一級哈希桶中的互斥鎖是用來保證插入、刪除和查找的同步。一級哈希桶包括一級哈希頭節點、互斥鎖，一級哈希桶的桶深由一級哈希頭節點的個數而定；一級哈希節點的參數包括哈希鍊表、二級哈希頭節點、一級哈希關鍵碼值。二級哈希桶包括二級哈希頭節點，二級哈希桶的桶深由二級哈希頭節點的個數而定；二級哈希節點的參數包括哈希鍊表、內存塊起始地址、內存塊結尾地址。本文中所描述的具體實施例僅僅是對本發明精神作舉例說明。本發明所屬技術領域的技術人員可以對所描述的具體實施例做各種各樣的修改或補充或採用類似的方式替代，但並不會偏離本發明的精神或者超越所附權利要求書所定義的範圍。
權利要求
1.一種用於嵌入式系統的內存控制方法，其特徵在於從作業系統中申請一塊內存，內存的一部分作為內存池，另一部分作為預留內存區域；內存池採用池式管理，為每個線程配置一個線程緩存；預留內存區域採用TLSF算法管理； 進行內存初始化操作時，執行以下步驟， 步驟I. 1，初始化內存池，包括將內存池切割成不同大小的內存塊，為同等大小的內存塊維護一個內存管理頭結構；為每個內存塊分配一個內存管理單元； 步驟I. 2，初始化預留內存區域，包括按照TLSF算法的數據結構組織預留內存區域，並維護兩個內存管理頭結構，一個用來管理小內存塊，另一個用來管理大內存塊，小內存塊和大內存塊根據預設參數劃分； 步驟I. 3，初始化各線程緩存的內存管理頭結構，為任一線程申請的內存中同等大小的內存塊維護一個內存管理頭結構； 步驟I. 4，初始化每個線程的一個內存統計鍊表，所述內存統計鍊表是用於連接任一線程申請的所有內存塊； 內存池、預留內存區域和各線程緩存的內存管理頭結構均包括空閒內存塊的個數、已使用內存塊的個數、空閒鍊表、已使用鍊表和互斥鎖；內存池和預留內存區域的各內存塊的內存管理單元的域包括內存池雙向鍊表、線程緩存鍊表、內存塊狀態、線程使用內存統計鍊表、內存管理參數和指向內存塊的指針，內存管理參數包括內存塊的大小size，所述內存池雙向鍊表為空閒鍊表或已使用鍊表；預留內存區域中，用來管理小內存塊的內存管理頭結構中已使用鍊表稱為小內存鍊表，預留內存區域中，用來管理大內存塊的內存管理頭結構中已使用鍊表稱為大內存鍊表； 進行內存分配操作時，執行以下步驟， 步驟2. 1，根據應用程式申請的內存大小，向上調整到內存池中切割內存塊的大小，記為目標size ;查看線程緩存對應大小內存塊的空閒鍊表中是否是合適的內存塊， 如果有，將內存塊從線程緩存的空閒鍊表中刪除，掛在線程緩存的已使用鍊表中，並更新該內存塊的內存管理單元的相關信息，包括狀態更新為已使用，並標記為從內存池中分配，返回內存塊的首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配； 否則，進入步驟2.2 ; 步驟2. 2，查看內存池中是否有目標size的空閒內存塊， 如果有，將空閒的內存塊從內存池的空閒鍊表中移除，掛在內存池的使用鍊表中，並更新內存管理單元的相關信息，包括狀態更新為已使用，並標記為從內存池中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配； 否則，進入步驟2. 3; 步驟2. 3,查找比目標size大一個size的內存塊， 如果有，將空閒內存塊從內存池的空閒鍊表中移除，掛在內存池的使用鍊表中，並更新內存管理單元的相關信息，尤其是狀態更新為已使用，並標記為從內存池中分配，返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中，完成分配； 否則，根據應用程式申請的內存大小從預留內存區域中申請內存塊，並分配相應的內存管理單元；設置內存管理單元的相關信息，包括狀態為已使用，並標記為從預留內存區域中分配；返回內存塊首地址，將此內存塊加入到線程的內存統計鍊表中；根據應用程式申請的內存大小和預設參數，確定申請的內存塊是小內存塊還是大內存塊；如果申請的是小內存塊，將申請的內存塊掛到小內存鍊表中，並更新哈希表的信息，將此內存塊插入到二級哈希結構中，完成分配；如果申請的是大內存塊，將申請的內存塊掛到大內存鍊表中； 進行內存釋放操作時，執行以下步驟， 步驟3. 1，由輸入地址找到對應的內存管理單元； 步驟3. 2，根據內存管理單元中的內存塊狀態域來判斷， 如果是從內存中的內存池申請的，轉入步驟3. 3 ； 如果是從預留內存區域分配的，將內存管理單元從預留內存區域的對應內存管理頭結構的已使用鍊表中刪除，將內存塊從線程的內存統計鍊表中刪除，如果是小內存塊則更新哈希查找結構的信息；並採用TLSF算法的free函數釋放內存塊和相應內存管理單元，完成釋放； 步驟3. 3，將內存管理單元從內存池的使用鍊表中移除，掛到線程緩存的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放； 步驟3. 4，檢查線程緩存中空閒內存塊數目與使用內存塊數目的比值， 如果小於一定閾值，則將內存管理單元從線程緩存的使用鍊表中移除，掛到線程緩存的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放； 否則，將內存管理單元從線程緩存的使用鍊表中移除，掛到內存池的空閒鍊表中，並更新狀態域為空閒狀態，將此內存塊從線程的內存統計鍊表中刪除，完成釋放。
2.根據權利要求I所述用於嵌入式系統的內存控制方法，其特徵在於進行內存覆蓋檢查時,對要定位的內存塊執行以下步驟， 步驟4. 1，根據輸入地址判斷該內存塊是在內存池中還是預留內存區域中， 如果是在內存池中，則先定位該內存塊位於哪個size內存塊的範圍，然後取模運行定位內存邊界； 如果是在預留內存區域中，則轉入步驟4. 2 ； 步驟4. 2，遍歷大內存鍊表查找該內存塊， 如果查找到則得到內存邊界， 否則，採用二級哈希算法來定位內存邊界。
3.根據權利要求I或2所述用於嵌入式系統的內存控制方法，其特徵在於內存池中，內存管理單元和內存塊分別放在不同的內存區域；預留內存區域中，內存管理單元和內存塊分別放在不同的內存區域。
全文摘要
本發明提供一種用於嵌入式系統的內存控制方法，從作業系統中申請一塊內存，內存的一部分作為內存池，另一部分作為預留內存區域；內存池採用池式管理，結合線程緩存技術，為每個線程建立一個緩存；預留內存區域採用TLSF算法管理；將該內存池切割成不同大小的內存塊，同等大小的內存塊連成雙向鍊表，為每個內存塊增加一個內存管理單元，內存管理單元和內存塊分別放在不同的內存區域；為每一個線程建立一個內存統計鍊表，用於連接所有此線程申請的內存塊，為方便內存洩露排查。另外，在不增加內存控制方法開銷的前提下，增加了內存覆蓋檢查機制。
文檔編號G06F12/02GK102915276SQ20121036025
公開日2013年2月6日 申請日期2012年9月25日 優先權日2012年9月25日
發明者陶琴, 王凌斐 申請人:武漢郵電科學研究院