Linux 內核相同頁面合併之效能探討

Abstract

KSM 是一個附加於KVM 上Linux kernel 的模組，用於合併KVM上跨虛擬機器之間所擁有相同重複的頁面，並釋放已經被合併後的頁面，節省虛擬機器所使用頁面數量，以達到最好的記憶體使用率。現行的KSM 中，必須賴以kernel thread daemon”ksmd” 循序不間斷停地在可被合併的記憶體區域中做搜尋頁面的動作，並且找出可合併的頁面加以合併，雖然可以省下記憶體使用空間，卻也增加了CPU工作量的負擔。本論文找出KSM 演算法中所佔比例較高的函式，第一為頁面比對、第二為頁面校驗和運算，我們嘗試針對這兩個函式下去最佳化。頁面比對所使用的方式是必須先將兩個頁面透過映射至實體記憶體上bit by bit 的做比對，最差情況則是當兩個頁面相同時，必須比對完整頁面的大小4KB，我們採用原先就已存在於KSM 演算法中各個頁面所算出的校驗和，使用比對頁面的校驗和的方式達到整體流程的加速。頁面的校驗和運算則是採用jhash2 此種哈希函數來算出各個頁面之校驗和，此函式是個複雜數學運算，因此會占用不少的CPU 使用量在運算上，我們使用GPGPU，SIMD (single instruction multiple data)架構之硬體加速器來輔助我們一次計算大量頁面的校驗和，但是由於KSM 是存在於kernel space 中的process，又一般GPGPU 程式語言OpenCL 或是CUDA 之Runtime API 及library 只允許在user space 中所使用，因此我們參考其他論文並使用，KGPU 一個可於kernel space 中使用GPGPU 的框架，來協助最佳化頁面的校驗和運算。

KSM which is a Linux kernel module attached to the KVM hypervisor used for merging duplicate page across different virtual machines and release merged pages in order to achieve the best memory utilization. Existing KSM must periodically scan the mergable memory area and identify the identical pages to merge via kernel thread daemon ”ksmd”. Although memory usage is reduced, CPU usage is increased. This thesis analyzed KSM and found the hotsopts of KSM algorithm. The first is page comparison and the second is page’s checksum calculation. We tried to optimize for these two functions. Page comparison may firstly map two pages onto physical memory and compare page’s content bit by bit . Comparing two identical pages is the worst situation because must compare full page of size 4KB. We use comparing page’s checksums in order to accelerate KSM algorithm. Page’s checksum calculation is computed by a hash function - jhash2. This function is a complex mathematical operation so that it takes a certain CPU usage in operation. We use GPGPU, a SIMD (single instruction multiple data) architecture of hardware accelerator to help us calculate the checksums f a large number of pages concurrently. But due to the KSM is a process in the kernel space. GPGPU programming language OpenCL or CUDA runtime API and library are support only in user space. So we reference other papers and use. KGPU, a framework for GPGPU can be used in kernel space to optimize the page’s checksum calculation.