stl中的空間配置器，stl空間配置器
一般我們習慣的c++內存配置如下
class Foo { ... };
Foo* pf = new Foo;
delete pf;
這裡的new實際上分為兩部分執行。首先是先用::operator new配置內存，然後執行Foo::Foo()構造對象內容。delete也一樣，先運行Foo::~Foo()析構對象，再用::operator delete釋放內存。在SGI STL中，這兩部分分別在<stl_alloc.h>和<stl_construct.h>中。本文講的便是<stl_alloc.h>中的故事。
SGI STL中將配置器分為兩級。第一級直接用malloc和free管理內存，第二級則使用內存池以避免內存碎片。這兩級都由simple_alloc包裝起來以符合stl標准。如圖
第一級由於沒有用operator new，所以要自己實現new-handler機制。我仿寫的代碼如下
1 #ifndef _MALLOC_ALLOC_H_
2 #define _MALLOC_ALLOC_H_
3
4 //定義內存不足又沒有定義相關處理函數時拋出的異常
5 #ifndef THROW_OOM
6 # include <stdio.h>
7 # include <stdlib.h>
8 # define THROW_OOM fprintf(stderr, "out of memory\n"); exit(1)
9 #endif
10
11 #include<stdlib.h>
12
13 namespace Chenstl{
14
15 //第一級空間配置器，直接用mallloc分配內存
16 //當需要分配的空間大於MAX_BYTES時使用
17 class malloc_alloc{
18 private:
19 static void *oom_malloc(size_t); //聲明時可以只寫類型啊。。現在才知道
20 static void *oom_realloc(void *,size_t);
21 static void (* malloc_oom_handler)(); //處理malloc時內存不足時的函數指針
22 public:
23 static void *allocate(size_t n);
24 static void decllocate(void *p);
25
26 static void *realloc(void *p, size_t new_sz);
27 //當內存不足時，需要客戶端設置handler
28 static void set_malloc_oom_handler(void(*f)());
29 };
30 }
31
32 #endif
![]()
1 #include "malloc_alloc.h"
2
3 using namespace Chenstl;
4 void *malloc_alloc::allocate(size_t n)
5 {
6 void *result = malloc(n);
7 if (0 == result) result = oom_malloc(n);
8 return result;
9 }
10
11 void malloc_alloc::decllocate(void *p)
12 {
13 free(p);
14 }
15
16 void * malloc_alloc::realloc(void *p, size_t new_sz)
17 {
18 void *result = realloc(p, new_sz);
19 if (0 == result) result = oom_realloc(p, new_sz);
20 return result;
21 }
22
23 //當內存不足時，需要客戶端設置handler
24 void malloc_alloc::set_malloc_oom_handler(void(*f)())
25 {
26 malloc_oom_handler = f;
27 }
28
29 void(*malloc_alloc::malloc_oom_handler)() = 0;
30
31 void *malloc_alloc::oom_malloc(size_t n)
32 {//不斷試圖獲得內存
33 void *result;
34 for (;;) //據說這樣比while(1)效果更優
35 {
36 if (0 == malloc_oom_handler) THROW_OOM;
37 (*malloc_oom_handler)();
38 result = malloc(n);
39 if (result) return result;
40 }
41 }
42
43 void *malloc_alloc::oom_realloc(void *p, size_t n)
44 {
45 void *result;
46 for (;;)
47 {
48 if (0 == malloc_oom_handler) THROW_OOM;
49 (*malloc_oom_handler)();
50 result = realloc(p, n);
51 if (result) return result;
52 }
53 }
malloc_alloc.cpp
如果需要的區塊超過128bytes則用第一級，否則用第二級的內存池管理。為了便於管理，配置器會自動將內存需求量上調到8的倍數（要求20bytes時，自動調整為24bytes）。用16個freelist管理內存池，為節省空間，使用union
union obj { //free-lists的節點構造
union obj *next;
char client[1]; //使用者可見
};
獲取內存時的代碼及步驟如下
![]()
void *default_alloc::allocate(size_t n)
{
obj *result = 0;
obj **my_free_list = 0;
if (n > MAX_BYTES)
return malloc_alloc::allocate(n);
//尋找free lists中合適的一個
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(0 == result)
{//沒有找到可用的freelist，從內存池裡取出空間
return refill(ROUND_UP(n));
}
//調整freelist
*my_free_list = result->next;
return result;
}
View Code
當free list中沒有可用區塊時，調用refill()為free list填充空間，新的空間取自內存池（由chunk_alloc()完成）。如果內存池不夠，則malloc之，如果系統heap空間也不夠，chunk_alloc()就尋找還有空閒區塊的free list並將其內存充公，如果還是不夠就調用第一級配置器。第一級配置器有實現new-handler機制，內存不夠會拋出異常。
![]()
#ifndef _DEFAULT_ALLOC_H
#define _DEFAULT_ALLOC_H
namespace Chenstl{
//使用內存池以減少碎片
class default_alloc {
private:
enum { ALIGN = 8};
enum { MAX_BYTES = 128 };
enum { NFREELISTS = 16 };
//static const int ALIGN = 8;
//static const int MAX_BYTES = 128;
//static const int NFREELISTS = 16; //MAX_BYTES/ALIGN
union obj { //free-lists的節點構造
union obj *next;
char client[1];
};
//freelist
static obj *free_list[NFREELISTS];
static char *start_free; //內存池的起始位置
static char *end_free; //內存池的終止位置
static size_t heap_size;
private:
//將bytes上調至8的倍數
static size_t ROUND_UP(size_t bytes) {
return ((bytes +ALIGN - 1) & ~(ALIGN - 1));
}
//獲取合適的區塊在freelist中的位置
static size_t FREELIST_INDEX(size_t __bytes) {
return (((__bytes)+(size_t)ALIGN - 1) / (size_t)ALIGN - 1);
}
//返回一個大小為n的對象，並可能加入大小為n的其他區塊到free-list
static void *refill(size_t n);
//配置一大塊空間，可容納nobjs個大小為size的區塊
//如果配置nobjs個區塊有所不便，nobjs可能會降低
static char *chunk_alloc(size_t size, int &nobjs);
public:
static void *allocate(size_t n);
static void deallocate(void *p, size_t n);
static void *realloc(void *p, size_t old_sz, size_t new_sz);
};
}
#endif
default_alloc.h
![]()
#include "default_alloc.h"
#include "malloc_alloc.h"
using namespace Chenstl;
default_alloc::obj *default_alloc::free_list[NFREELISTS]
= { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
char *default_alloc::start_free = 0; //內存池的起始位置
char *default_alloc::end_free = 0; //內存池的終止位置
size_t default_alloc::heap_size = 0;
void *default_alloc::allocate(size_t n)
{
obj *result = 0;
obj **my_free_list = 0;
if (n > MAX_BYTES)
return malloc_alloc::allocate(n);
//尋找free lists中合適的一個
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(0 == result)
{//沒有找到可用的freelist，從內存池裡取出空間
return refill(ROUND_UP(n));
}
//調整freelist
*my_free_list = result->next;
return result;
}
void default_alloc::deallocate(void *p, size_t n)
{
}
//返回一個大小為n的對象，並可能加入大小為n的其他區塊到freelist
//在ANSI c中，void *不允許進行加減操作，所以chunk用char *
void *default_alloc::refill(size_t n)
{
int objs = 20;
char *chunk = chunk_alloc(n, objs);
obj *next, *current;
obj *result;
obj **my_free_list;
if (1 == objs) //只取出一個區塊
return chunk;
my_free_list = free_list + FREELIST_INDEX(n);
result = (obj *)chunk; //這一塊返回給客戶端
//將freellist指向分配的區域
*my_free_list = next = (obj *)chunk + n;
for (int i = 1;; i++)
{
current = next;
next = (obj *)((char *)next + n); //這裡注意不能直接用next+n
if (i == objs - 1)
{
current->next = 0;
break;
}
else
current->next = next;
}
return result;
}
char *default_alloc::chunk_alloc(size_t size, int &nobjs)
{
char *result = 0;
size_t total_bytes = size*nobjs;
size_t bytes_left = end_free - start_free; //內存池剩余空間
if (bytes_left >= total_bytes)
{//內存池足夠提供所需內存
result = start_free;
start_free += total_bytes;
return result;
}
else if (bytes_left >= size)
{//內存池足夠供應一個以上的區塊
nobjs = bytes_left / size;
total_bytes = nobjs * size;
result = start_free;
start_free += total_bytes;
return result;
}
else
{//內存池一塊區塊也供應不了
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);;
if (bytes_left>0)
{//將內存池的零頭分配給合適的freelist
obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj *)start_free)->next = *my_free_list;
*my_free_list = (obj *)start_free;
}
start_free = (char *)malloc(bytes_to_get);
if (!start_free)
{//系統堆內存不足，尋找還未使用的freelist
obj *p = 0;
obj **my_free_list = 0;
for (int i = size; i < MAX_BYTES; ++i)
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p)
{//還有未使用的freelist
start_free = (char *)p;
*my_free_list = p->next;
end_free = start_free + i;
//遞歸調用，修正nobjs
return chunk_alloc(size, nobjs);
}
}
//沒內存可用，寄希望於第一級的new-handler或拋出異常
end_free = 0;
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return chunk_alloc(size, nobjs);//遞歸調用，修正nobjs
}
}
default_alloc.cpp
