跳到內容

RDM 14.2的內存分配器

介紹

RDM 14.2之前版本的內存分配器主要是為了靈活性而不是速度而設計的。在某些情況下,性能可能會急劇下降。我們從此新的內存分配器中刪除的一個功能是使用句柄分配內存,然後稍後一次釋放與同一句柄關聯的所有內存的功能。儘管此功能可以輕鬆避免硬內存洩漏(終止時不會釋放的內存),但相反,我們經常會遇到軟內存洩漏(在特定條件下不使用但最終會釋放的內存)。

在RDM 14.2中,我們設計了一個新的內存分配器,目的是解決舊內存分配器遇到的問題。這是一個全新的設計,針對速度進行了優化,但必須重寫許多需要動態分配的代碼。對於RDM 14.2,我們還重做了許多子系統,不再使用內存池,而是確保使用系統堆棧中的內存,或者使用在其他對像中靜態分配了對象的API。 

從頂級視圖看,內存分配器的主要功能是:

  1. 分配和釋放使用句柄完成
  2. 分配的內存必須顯式釋放
  3. 大多數內存分配和釋放按執行順序O(1)
  4. 有幾種替代實現
  5. 主分配器正在處理4K頁的分配
  6. 子分配器正在處理小於2K的分配
  7. 堆棧分配器
  8. 系統堆棧分配器

替代實施

我們的內存分配器具有許多可供選擇的實現,可以在編譯時進行選擇。這些實現中的一些實現在性能特徵上有所不同,而其他實現則用於調試和QA目的。

例如,我們有一個位於malloc和free之上的實現,可以與內存配置文件工具一起使用,以查找問題,包括緩衝區溢出,內存洩漏和線程問題。 Purify(Windows),Memcheck(Unix),Helgrind(Unix)和efence(Unix)都可以使用此實現。我們還有一個與我們的測試框架集成的實現,可以進行內存故障模擬。最後,還有一個可以描述分配大小的實現。本文將不再討論這三種實現。

手柄的使用

新分配器使用與舊分配器類似的句柄。最大的區別是新分配器是完全可重入的。舊的分配器的概念類似於我們的子分配器,但是沒有主分配器。舊的分配器使用某種全局狀態,在該狀態下如何設置和關閉一些不同的子系統是很麻煩的,而且不易檢查。新的分配器和對平台支持層(PSP)的重新設計使這一過程變得更加容易。

由於採用了這種新的分配器設計,現在可以將兩個RDM實例嵌入一個進程或地址空間中,而不會導致一個實例的分配影響另一個實例的分配。這兩個實例都實例化了它們自己的主分配器,並且這些句柄直接或間接用於每個後續分配。這也是我們在質量檢查測試框架中所做的事情。產品中使用了一個主分配器,而QA測試框架中使用了另一個主分配器。這樣一來,QA測試框架中可能出現的內存問題就不會影響被測產品,反之亦然,即使使用QA測試框架進行測試,也可以進行內存分析。

可以從主分配器中檢索兩種類型的分配器:子分配器和堆棧分配器。這些分配器還返回句柄,它們的實現將從主分配器獲取其內存。

穿線

新的內存分配器在設計時考慮了線程。主分配器是唯一可以在多個線程中使用的分配器。子分配器沒有內置的線程保護。通常,一次只能從一個線程使用每個子分配器。還假定內存分配及其使用是局部於一個線程的,這有助於局部性。

一個例外是當子分配器處理大於2K的分配時。在這種情況下,可以安全地同時分配多個線程並將其從多個線程中釋放出來,因為這些分配被設計為由主分配器處理。

分頁並將頁面交換到磁盤

對於具有虛擬內存的系統,重要的是要避免在不必要的內存頁面上隨機分配分配。這是通過使主分配器將內存拆分為與4K完全對齊的頁面來完成的。主分配器保留有關其單獨管理頁面的元數據。這樣,無需觸摸正在釋放的頁面。如果頁面已被調出,它將保持被調出狀態。子分配器還將獨占使用多個頁面。假定採用這種方法有助於避免過度使用虛擬內存(儘管只有一點點)。

緩存性能

主分配器將內存分配對齊為4K,子分配器具有將數據對齊為64字節的能力(取決於編譯的配置文件)。這樣可確保分配越過盡可能少的64字節高速緩存行。我們的某些算法依賴於此,因此我們可以保證最多一個高速緩存未命中。

緩解內存洩漏

如果存在內存洩漏,則在調試模式下將觸發代碼中的斷言。在釋放模式下,當子分配器,堆棧分配器或主分配器被銷毀時,將從主分配器派生的所有分配都將被釋放。

主分配者

上面概述的主分配器負責分配頁面。分配了多個頁面後,僅需要主分配器的句柄和指向內存開始的指針即可釋放頁面。

主分配器從OS請求大塊內存。這些大塊中的每一個都有一個標頭。對於每個4K頁面,標頭中都有一個相應的內存,用於管理頁面。如果頁面是分配或可用內存區域的開頭或結尾,則有關於此頁及其大小的信息。當頁面被釋放時,將使用此信息,在這裡我們可以有效地將內存區域組合成更大的區域。不變的是,永遠不會有兩個空閒的內存區域彼此相鄰,並且頭之外的所有內存都是空閒的,或者為每個首頁分配了信息,而對於每個分配的每個尾頁和分配區域都顯示了這樣的信息。頭和尾之間的所有其他頁面都標記為不是頭或尾。

標頭中的相應信息還具有用於自平衡二進制搜索樹(AVL)節點的空間,該節點用於維護按大小排序的所有可用存儲區的AVL。使用此AVL,我們可以找到一個擬合大小,其大小為O(log n),其中n是可用內存區域的數量。由於我們將空閒內存組合到區域中,並且我們始終使用適合分配的最小空閒區域,因此假定n與頁數相比較小。

分配和釋放頁面僅使用標頭中的內存,因此被認為是高速緩存,尤其是分頁有效。如果系統頻繁分配和釋放頁面,則標頭的相應部分將很熱,並且不太可能從CPU緩存中刪除或分頁。但是,如果系統相對於頁面分配變為靜態,則這些頁面可能會從CPU緩存中刪除,甚至被調出。

基於以上考慮,我們的頁面分配器被認為是非常有效的。但是,某些用例可能會導致碎片化。最好將靜態分配與動態分配分開。在定期進行分頁的虛擬內存系統上,這無關緊要,因為它只會導致某些頁面不被使用,並且最終可能會被分頁(然後再也不會分頁)。

子分配器

上面概述的子分配器負責為單個線程或任務分配和釋放內存。子分配器沒有直接與任何線程或任務關聯,但是我們確保RDM中的單獨線程使用它們自己的子分配器。

子分配器處理的分配主要有三種類型:

  1. 分配小於2K
  2. 可以由主分配器處理的分配
  3. 需要傳遞給操作系統的分配

本節的重點是上面的第一種情況。但是,讓我們首先簡要討論另外兩種情況。 

主分配器處理的分配

每個子分配器在實例化時都將與一個主分配器相關聯。如果分配大於子分配器可以處理的分配,則可以將其傳遞給主分配器。主分配器將返回許多與頁面對齊的4K頁面。由於這些分配始終與頁面對齊,因此子分配器知道此分配是由主分配器處理的,並且當以後釋放該分配時,可以將其直接傳遞給主分配器。

分配給操作系統

如果分配對於主分配器來說太大(默認情況下約為650K),則該分配將由OS處理。在這種情況下,將保留特殊的標頭。以後釋放此分配時,特殊標頭會告訴子分配器將其直接傳遞給OS。

子分配器的核心部分

現在我們準備進入子分配器的詳細信息。除了我們之前提到的之外,還有三種主要的實現。可以在編譯時選擇要使用的實際實現。首先,我們將討論這三個實現共有的一些特徵。

如上所述,子分配器是從主分配器實例化的。它將從主分配器獲取許多頁面。首次實例化時請求一個頁面。每次收到分配請求而又無法容納已存在的頁面時,都請求一個額外的頁面。從主分配器分配的頁面永遠不會返回到主分配器,除非銷毀了子分配器。

子分配器的核心部分僅處理特定大小。通常,每個2的乘方有兩個大小,請求的大小將四捨五入為最接近的支持大小。具體支持哪種大小取決於所使用的配置文件。默認情況下編譯的配置文件針對高速緩存性能進行了優化,這意味著沒有分配會超過所需的64字節邊界。

由子分配器的核心部分管理的每個頁面都保留一個特定的大小。由於每個單獨的分配都不需要報頭,因此這僅需要很少的開銷。釋放內存後,頁面標題將具有有效管理內存所需的所有信息。

固定大小的分配

我們的某些算法會執行較小的固定大小分配。我們曾經使用內存池,但是事實證明,我們的新分配器的效率與之前使用的內存池差不多。通過使用宏內聯一些代碼,我們的新內存分配器在內存池方面優於舊的實現。使用新的內存分配器還具有不需要為特定目的分配內存或需要為其保留多少內存的優點。

缺點

這種方法有兩個主要缺點。

首先,對於分配了一個大小的許多內存塊的應用程序,釋放它們,然後分配許多不同大小的內存。假定在某些使用情況下RDM在某種程度上可能是這種情況,但據信並沒有超過這種特定方法的好處。所描述的方法允許非常有效的算法。

其次,讓每個頁面僅處理特定大小的分配意味著我們將浪費一些內存。從長遠來看,僅平均分配大小各異的分配,每種支持的大小都會浪費2K。對於默認配置文件,這累計為36K。對於使用很少內存的應用程序來說可能是個問題,但是對於使用相對大量內存的應用程序來說幾乎沒有任何問題。

我們可以在每個頁面上允許不同的大小以緩解上述問題。但是,這將需要更多信息存儲在標頭中,並且可能需要為每個分配分配標頭。這也將增加空間開銷,並且據信很難提出一種與我們當前分配器一樣高效的算法,尤其是因為與舊分配器相比,空間利用率和性能都很高。

三種算法

在以下小節中將描述三種替代算法。

使用列表和位圖的子分配器

就緩存性能而言,假定此方法是最佳方法。讓我們深入研究它的工作原理。

將為可能具有可用空間的每種受支持的頁面尺寸維護一個列表。我們在這裡說“可能”,因為在頁面上分配內存時,我們不會檢查是否正在使用該頁面上的最後一個可用空間。取而代之的是,稍後我們發現無法從該頁面進行分配時,將其從列表中刪除。與始終執行此檢查並儘早刪除它相比,此方法效率更高。

每個頁面都有一個頁眉,其中包含一個位圖,該位圖告訴我們頁面的哪個部分相對於該頁面支持的實際大小是可用的。我們有一個通用算法可以在該位圖中查找,但是我們也有特定於平台的實現,這些實現可以利用硬件優化。

由於此算法不接觸正在釋放的內存,因此假定這對緩存性能最友好。但是,為了充分利用它,需要使用此算法的代碼在要釋放內存時不接觸內存。另外,我們產品的某些早期性能分析顯示了下面介紹的最後一種算法具有更好的性能。

由於我們經常從通常最近訪問過的頁面中進行分配,因此也假定此算法對分頁很有用。

帶有列表列表的子分配器

該算法與以前的算法相似,不同之處在於我們在頁面中使用列表而不是位圖。我們使用釋放的內存位置來保存指向頁面中下一個空閒位置的指針。假定此算法對於CPU緩存性能而言不是次優的,但是當位圖中沒有硬件支持查找時,該算法可能會更快。

假定該算法與第一個算法一樣好用於分頁。

具有單個列表的子分配器

這與之前的算法類似,不同之處在於,對於每個受支持的大小,我們都有一個到達所有空閒位置的列表。根據我們對RDM所做的一些早期分析,該算法似乎是最有效的算法。這是使用的默認算法。假定它不是對CPU緩存性能最好的,而對分頁來說則是最差的。由於其簡單性,該算法可能勝過其他算法。但是,這可能並非普遍如此。我們懷疑基於CPU架構或應用程序可能存在差異。如果由於過度使用虛擬內存而導致應用程序預期分頁很多,則該算法的性能會較差。

堆棧分配器

RDM有兩種類型的堆棧分配器。

其中之一主要是為了使用系統堆棧而設計的。分配是在沒有句柄的情況下完成的。此分配器僅應用於有限的大小分配,並且必須在源代碼中給出最大大小。確切的方法(包括這些分配是否實際使用系統堆棧)取決於平台。

另一個堆棧分配器是在其實現中使用子分配器的實現。該堆棧分配器使用類似於子分配器的句柄。這種類型的堆棧分配器相對於子分配器的主要優點是,它避免了管理較小的分配,並且可以通過釋放堆棧上的其他內容來釋放內存塊。