嵌入式系統(tǒng)e_slab的研究與實(shí)現(xiàn)

隨著硬件技術(shù)的發(fā)展和內(nèi)存容量的擴(kuò)大，操作系統(tǒng)中內(nèi)存管理技術(shù)日趨完善。但是在嵌入式領(lǐng)域中，硬件性能和內(nèi)存容量遠(yuǎn)遠(yuǎn)落后于PC機(jī)，其內(nèi)存管理受到多種因素制約，若直接采用操作系統(tǒng)中的內(nèi)存管理技術(shù)，不僅難以達(dá)到預(yù)期效果，而且會(huì)影響嵌入式系統(tǒng)的性能。

在嵌入式系統(tǒng)內(nèi)存管理設(shè)計(jì)過(guò)程中，發(fā)現(xiàn)操作系統(tǒng)中的slab分配器雖然在PC機(jī)上有良好的性能，但是在嵌入式系統(tǒng)中不但不能發(fā)揮其優(yōu)勢(shì)，還降低了系統(tǒng)的整體性能。本文通過(guò)分析，指出了slab分配器的不足，并給出相應(yīng)的解決方案。實(shí)驗(yàn)結(jié)果表明，slab分配器經(jīng)過(guò)改進(jìn)可適用于嵌入式系統(tǒng)。

1 slab分配器分析

操作系統(tǒng)內(nèi)核運(yùn)行時(shí)會(huì)頻繁地為某些對(duì)象分配內(nèi)存空間，而這些對(duì)象往往只需要幾十或幾百KB的空間，如果直接采用頁(yè)面管理器進(jìn)行內(nèi)存分配，將產(chǎn)生很多內(nèi)存碎片，造成嚴(yán)重的內(nèi)存浪費(fèi)。slab分配器支持細(xì)粒度的內(nèi)存分配，較好地解決了此問(wèn)題。由于性能優(yōu)越，slab被Linux、FreeBSD等操作系統(tǒng)采用，是目前應(yīng)用最廣的內(nèi)核內(nèi)存管理器之一[1]。

1.1 slab分配器設(shè)計(jì)思想

基于頁(yè)面分配器[2]，將一頁(yè)或幾頁(yè)的內(nèi)存組織起來(lái)，劃分成一定數(shù)量的小塊內(nèi)存，這種連續(xù)的頁(yè)面稱之為slab。它為內(nèi)核中使用頻繁的對(duì)象建立專門的緩沖區(qū)(cache)，每種類型的對(duì)象都有自己專用的cache[2]。一個(gè)cache管理著多個(gè)slab，每個(gè)slab又管理著多個(gè)對(duì)象。slab的大小與所管理對(duì)象的大小有關(guān)。根據(jù)slab管理對(duì)象的分配情況，可將每個(gè)cache中的slab分為3類[3-4]：(1)slab管理的對(duì)象已經(jīng)完全分配，沒(méi)有空閑的對(duì)象;(2)slab管理的對(duì)象部分分配，還有部分空閑對(duì)象;(3)slab中的對(duì)象都未分配，都是空閑對(duì)象。

不同的slab分別放入不同的隊(duì)列中，即每個(gè)cache管理3個(gè)slab隊(duì)列，cache與cache之間的關(guān)系如圖1虛框①內(nèi)所示，cache與slab的關(guān)系如圖1虛框②內(nèi)所示。

當(dāng)slab分配器接收到內(nèi)存申請(qǐng)時(shí)，根據(jù)所申請(qǐng)內(nèi)存的大小找到合適的cache，從cache管理的第二類slab中分配對(duì)象，若失敗則從第三類slab中分配對(duì)象，若還不成功則說(shuō)明cache中沒(méi)有空閑對(duì)象，須為cache創(chuàng)建一個(gè)新的slab，從新的slab中分配空閑對(duì)象。

對(duì)象釋放過(guò)程中，不僅要清空對(duì)象占用的空間，而且還要調(diào)整對(duì)象所屬slab的狀態(tài)，判斷是否改變此slab在cache中的位置。

slab分配器采用著色機(jī)制將不同slab中的對(duì)象放入不同的偏移處，利用硬件高速緩存的映射機(jī)制，將頁(yè)的不同偏移映射到硬件緩存的不同地址。而每個(gè)slab的開始部分訪問(wèn)頻率最高，只要slab中起始對(duì)象的偏移不同則映射到硬件高速緩存的位置就不同，從而降低了頻繁換入換出的性能損失[4-5]。

1.2 slab分配器在嵌入式系統(tǒng)中的缺陷

slab分配器雖然能解決系統(tǒng)對(duì)小塊內(nèi)存的頻繁需求，但是管理結(jié)構(gòu)復(fù)雜，內(nèi)存分配策略開銷較大。在內(nèi)存受限的嵌入式系統(tǒng)中，slab的缺陷大大影響了系統(tǒng)的整體性能?？傊?，slab分配器存在以下三方面的缺陷：

(1)slab管理結(jié)構(gòu)和存儲(chǔ)開銷較大

每個(gè)slab由slab描述結(jié)構(gòu)、管理空閑對(duì)象的整型數(shù)組和對(duì)象三部分組成，整型數(shù)組把slab中空閑對(duì)象組成一個(gè)順序隊(duì)列，數(shù)組大小與對(duì)象數(shù)有關(guān)，每個(gè)對(duì)象對(duì)應(yīng)一個(gè)整數(shù)，如圖2所示。當(dāng)對(duì)象較小時(shí)，整型數(shù)組將造成較大的內(nèi)存開銷。

(2)cache結(jié)構(gòu)復(fù)雜而且數(shù)量較多

系統(tǒng)中存在著專用對(duì)象和通用對(duì)象。專用對(duì)象專門存儲(chǔ)特定用途的數(shù)據(jù)結(jié)構(gòu)，例如CPU、文件系統(tǒng)等，其數(shù)量與系統(tǒng)密切相關(guān);通用對(duì)象用來(lái)存儲(chǔ)一般的數(shù)據(jù)結(jié)構(gòu)，大小在幾十KB到幾千KB之間(一般為2的整次冪字節(jié))，有十多種。不管是專用對(duì)象還是通用對(duì)象，slab分配器都為其建立了一個(gè)cache結(jié)構(gòu)，眾多cache組織和管理的較大開銷是嵌入式系統(tǒng)難以承受的。

(3)復(fù)雜的隊(duì)列管理

如圖1所示，slab分配器中存在較多的隊(duì)列，每個(gè)cache管理著3個(gè)slab隊(duì)列，每個(gè)slab隊(duì)列與cache組成循環(huán)隊(duì)列。所有的cache組成雙向循環(huán)隊(duì)列。面對(duì)眾多的隊(duì)列，如何有效地管理是很困難的。

1.3 slab在嵌入式系統(tǒng)中的改進(jìn)

針對(duì)上節(jié)中slab分配器的三點(diǎn)缺陷，給出相應(yīng)的改進(jìn)方案。

(1)改進(jìn)slab結(jié)構(gòu)

針對(duì)slab中對(duì)象管理數(shù)組開銷過(guò)大的問(wèn)題，可以將多個(gè)不同的slab合并成一個(gè)slab，從而減少slab的數(shù)量，即一個(gè)slab管理對(duì)象的大小可在一個(gè)小范圍內(nèi)浮動(dòng)。由于slab中對(duì)象大小不同，無(wú)法確定slab中對(duì)象的大小、數(shù)量和位置，所以必須重新設(shè)置slab結(jié)構(gòu)。

(2)限制slab分配器管理的內(nèi)存粒度范圍

由于內(nèi)核內(nèi)存管理器主要負(fù)責(zé)細(xì)粒度的內(nèi)存管理，所以限制所管理對(duì)象的大小。對(duì)于大塊內(nèi)存的申請(qǐng)，直接由頁(yè)面分配器處理。

(3)精簡(jiǎn)隊(duì)列管理

簡(jiǎn)化cache中繁雜的隊(duì)列，將cache中的前兩個(gè)slab隊(duì)列合并成一個(gè)隊(duì)列。

本文將經(jīng)過(guò)上述三方面改進(jìn)的分配器稱之為e_slab分配器。

2 e_slab分配器設(shè)計(jì)

2.1 基本管理結(jié)構(gòu)

e_slab分配器有3個(gè)重要的基本結(jié)構(gòu)，下面分別對(duì)其作相關(guān)介紹。

(1)object_t結(jié)構(gòu)

typedef struct object {

unsigned long size;

unsigned long offset;

} object_t;

object_t是描述對(duì)象的基本結(jié)構(gòu)，每個(gè)對(duì)象對(duì)應(yīng)一個(gè)object_t結(jié)構(gòu)，它描述了對(duì)象的大小和下一個(gè)空閑對(duì)象的地址。

(2)e_slab_t結(jié)構(gòu)

typedef struct e_slab _s {

struct list_head list;

void *s_mem;

unsigned int units;

unsigned int free;

} e_slab _t;

e_slab _t是管理對(duì)象的基本結(jié)構(gòu)，它不僅描述了本結(jié)構(gòu)的頁(yè)塊起始地址，而且存儲(chǔ)了空閑對(duì)象的數(shù)量和地址等信息。

object_t、e_slab _t和對(duì)象結(jié)構(gòu)如圖3虛框②內(nèi)所示。

(3)cache結(jié)構(gòu)

typedef struct cache_s {

struct list_head next;

struct list_head slab_list;