最近更新: 2007-08-25

bbslib~~pool - 以小換大的設計啟學

bbslib::pool 是一個簡單的記憶體配置功能 (源碼: bbslib-20010331.tar.gz/strexp/pool.c)。乍看之下,像是一個動態長度字串,但實際上,卻是簡單的動態記憶體管理模組。bbslib::pool 當初在設計時,是有多種考量的,例如安全性。當它要複製或銜接一個字串時,如果原先的空間不足,就會自動重配置夠大的空間去儲存,如此可避免 buffer ovewflow 的問題。而在使用效率上, bbslib::pool 是用 page 為單位向系統要求配置記憶體空間。

作業系統並不是以 bytes 為單位管理記憶體,而是以 page ;雖然 malloc() 的參數是以 bytes 為單位,但作業系統實際配置時,不足 1 page 的空間仍然是配置 1 page 記憶體空間,但標註 region ,因此無法使用超過此 region 的剩餘空間。

而 bbslib::pool 在設計時,便以小換大。與其浪費掉 page 內的剩餘空間,不如直接就要求一整塊 page 來用,然後由 bbslib::pool 自已來維護這個空間。但 bbslib::pool 不只是省下了記憶體空間,也省下了時間。在呼叫 malloc() 時,系統會進行核心的切換(從 application 切進 kernel),配置時也要做同步控制。而 bbslib::pool 僅僅需重新配置容量時會呼叫 malloc() ,除此以外的時間,都只在 application 層級動作,不需切到 kernel 。

舉個例子來說,如果要做個 link-list 的結構,其 node 如下:

typedef struct node {
    char data[120];
    struct node *prev;
    struct node *next;
} node_t;
/* sizeof(node_t) = 128 bytes */

如果有 10 個 node ,則用 malloc 的話,要呼叫 10次,一共要 10個 page 的空間 (這還不包括 kernel 維護這些 page 的記憶體空間),假設一個 page 是 1K ,至少浪費了 (1024-128)*10 的內容... 如果是用 bbslib::pool 呢? 把這個 10 個node 塞進pool,則只會呼叫 2次 malloc() 。省下了多次 kernel time 。

空間上只用了 2 page 的空間,浪費空間數是零。不是還有 (2*1024 - 128*10) 的地方沒用嗎? 是的,但那些空間仍在 bbslib::pool 的掌控下,只是還沒用到,不是用不到,所以不算是浪費了。

由此可知,如果資料是一群小資料的集合,則使用 bbslib::pool 反而較省資源,雖然 bbslib::pool 維護時會在其中留下一些 hole ,但相對於整個系統的記憶體空間來說,反而節省了許多大空間。

實作說明
struct pool
{
	string_i striobj;	// 具有 string_i 所承諾的行為的物件;

	char *content;        // pool 儲存區,Zero-end string;

	size_t length;        // Length of string, less terminating null character;

	size_t size;          // The (current) available size of content;

	size_t increment;     // 每次容量增加量,預設為 POOLBLKSIZ

	enum {
		POOL_MALLOC,
		POOL_AUTO
	} type;
};
typedef struct pool pool_t;

// _SC_PAGESIZE not part of POSIX.1

#if defined( _SC_PAGESIZE )
#define POOLBLKSIZ  sysconf(_SC_PAGESIZE)   // per block size
#else
#define POOLBLKSIZ 1024
#endif

POOLBLKSIZ 設為 1024 是因大多數的 32bit OS 是以 1024 bytes 為 1 page 。1 page 是 OS 在配置記憶體時的最小單位。我已確知的 OS 其 page 大小: OS/2: 4 KB = 1 page; Linux: 4 KB = 1 page; DOS: 16 bytes = 1 para. DOS 是以 para 為配置單位,但其意義跟 page 很像。其他的 i386 OS ,也都是以 1 KB 到 4 KB 為 1 page。

content 指向 bbslib::pool 的真正內容(通常是一個字串)。length 表示 content 目前的字串長度,即已使用的容量,但不包含字串終結字元 '\0' 所佔的容量。 size 表示目前 content 可用的大小, length 的最大值等於 size-1 。

每次以 POOLBLKSIZ 為單位來配置一個記憶體區域,以 content 指向該區域, size 表示該區域的大小( n * POOLBLKSIZ , POOLBLKSIZ的整數倍數)。將字串內容儲存在該區域中,但是因為字串不會一次剛好用完整個含量,故以 length 表示目前已使用的容量。當要儲存新的字串內容時,會自動判斷目前配置的容量,是否仍足夠儲存新的內容,如果不夠,會以 POOLBLKSIZ 為單位,再配置一塊足夠容納所有內容(原有及新增)的記憶體區域,將所有內容給儲存到該新的區域中後,才釋放掉舊的記憶體區域, content 會指向新的區域, size會指派新的容量大小。

樂多舊網址: http://blog.roodo.com/rocksaying/archives/4014249.html

樂多舊回應
未留名 (#comment-14309385)
Sat, 25 Aug 2007 22:48:14 +0800
在 i386 上, 因為 CPU 記憶體管理模型的關係, 所以 1page=4k, 不管是 windows, linux, freebsd, os/2,... 都會是 4k, 其它的 CPU 型態我沒取過不知道

至於 DOS 的話, 那算是 16bit 的, 再加上因為 real mode 神奇的記憶體模型 (Segment:Offset 對應到的真實記憶體位址為 (Segment << 4) + Offset, Segment 和 offset 都是 16bit), 所以才會有 1para = 16bytes 這種數字產生, 而配置會不會搞個配個 1byte 也是要去個 16bytes 的情況, 在那種記憶體寸 byte 寸金的時代...
--
x86 上 windows, freebsd 取得的也都是 4096:
Freebsd:
~$ uname
FreeBSD
~$ cat a.c
#include

int main() {
int sz = getpagesize();
printf("%d\n", sz);
}
~$ gcc a.c; ./a.out
4096

windows (2k):
C:\>type a.c
#include
#include

int main()
{
SYSTEM_INFO sSysInfo;

GetSystemInfo(&sSysInfo);
printf ("%d\n", sSysInfo.dwPageSize);
}


C:\>gcc a.c

C:\>a
4096
未留名 (#comment-14330037)
Tue, 28 Aug 2007 18:01:12 +0800
關於 page 的 size 。

我當時在 Linux, FreeBSD, Solaris 甚至 OS/2 上實測的數據都是 4096 bytes 。但我記得當時在 Win95/98 上,配合 MinGW32 以 sysconf(_SC_PAGESIZE) 抓出來的數據是 1024 bytes 。故我也不敢肯定地說是 1 page = 4096 bytes。

相容性: POSIX 中沒有相關規範。getpagesize() 是 BSD 規格,SYSV不支援。

《DOS 技術手冊二 徹底研究篇》:「DOS 是以 PARA (16BYTES) 為單位來配置(ALLOCATE)記憶區 (MEMORY BLOCK)的。」這本書是1993年出版,我當年學組合語言時買下的書。這一點我可以肯定地說:確實如此。
未留名 (#comment-14331061)
Tue, 28 Aug 2007 21:09:18 +0800
我也很肯定的說, 1990 年我就看過手冊二了. 出版時間應該更早.

另外, 286 或其他沒支援分頁的機器, 還是會一塊一塊配置記憶體, 跟 "分頁" 無關, 當然, para 不是 page.

http://en.wikipedia.org/wiki/Page_size
可以參考一下, x86 page 也不見得是固定 4k