這幾天在研究stl的內存配置器，作用是防止零散的申請內存塊導致過多的內存碎片。

大體思路是：

維護一個freelist, 一個內存塊鏈表，就是一個鏈表，鏈表上的每一個節點都一個指針指向一塊內存塊，如果有申請內存，就直接將此鏈表上的一個內存塊分配出去；

如果在鏈表上找不到合適的內存塊，或者說大小為n的內存塊已經被分配完了，這時就需要從內存池中拿到一大塊內存，然后再將這大塊內存按照大小為n進行連接成鏈表再放入freelist中，顯然內存池中有一塊很大的內存塊，這個大內存塊已經分配好了。

但是如果內存池中的內存塊也用完了，這時才需要用malloc再申請一塊大內存塊。

一般情況下我們構建單鏈表時需要創建如下的一個結構體。

struct Obj
{
??? Obj *next;
??? Char* p;
??? Int iSize;
}

next指針指向下一個這樣的結構，p指向真正可用空間,iSize用于只是可用空間的大小，在其他的一些內存池實現中，還有更復雜的結構體，比如還包括記錄此結構體的上級結構體的指針，結構體中當前使用空間的變量等，當用戶申請空間時，把此結構體添加的用戶申請空間中去，比如用戶申請12字節的空間，可以這樣做

Obj *p = (Obj*)malloc(12+sizeof(Obj));
p->next = NULL;
p->p = (char*)p+sizeof(Obj);
p->iSize = 12;

但是，我們并沒有采用這種方式，這種方式的一個缺點就是，用戶申請小空間時，內存池加料太多了。比如用戶申請12字節時，而真實情況是內存池向內存申請了12+ sizeof(Obj)=12+12=24字節的內存空間，這樣浪費大量內存用在標記內存空間上去，并且也沒有體現索引表的優勢

如圖所示：

紅色為結點，藍色為結點指向的內存塊

在sgi中是這樣定義的：

union Obj
{
??? Obj *next;
??? char client_data[1];
}

next指向下一個內存塊，這個內存塊最開始的部分放有next, 當將這個內存塊給客戶時，也把next所占的內存給客戶，也就是說這個鏈表不占用額外的內存空間。

如圖所示：

途中一共四個內存塊，next/client_data就在各自的內存塊中。由于union的特性，如果看next，這個變量指向的是下一塊內存塊的地址；如果看client_data，就可以將其看做柔性數組進行理解，client_data是個指針，指向的是其所在內存塊的位置，就是講client_data看做一個數組。

個人認為，client_data完全沒有用途，sgi只所以還保留client_data只是為了便于理解。

所以在我個人實現的內存配置器，就省略了client_data

還有一個問題：

為什么在泛型中用到了template<int inst>, 而在之后的實現中卻沒有用到inst?

至于inst應該是為了生成不同的實例，在多線程環境下可以提高速度。舉個例子：比如你有兩個線程，A調用allocate分配8個字節，正在把這塊內存從free_list取下是時，系統調度將A停下B開始執行，恰好B也要分配8個字節，于是把分配給A的搶了過來（因為free_list沒有更新，而且整個allocate的數據都是靜態的，被整個class共享），A接著運行，他并不知道B已經拿走了這塊內存，結果同一塊內存同一時間分給了兩個線程，錯誤產生了。要避免這種錯誤就必須加鎖，細節你可以看STL原碼，速度自然變慢。解決這種問題的辦法就是利用inst，為不同的線程指定不同的inst生成不同的靜態memeber?data。不同的線程有不同的free_list，自然就不用加鎖了！

#ifndef C_ALLOC_H #define C_ALLOC_H #include <stdio.h> #include <stdlib.h>enum {ALIGN = 8};// enum {MAX_BYTES = 128}; enum {NFREELISTS = 16};#define __THROW_BAD_ALLOC std::cerr << "out of memory " <<endl; exit(1) //第一級配置器 template <int inst>//這個模板參數在單線程中沒有用，主要用于多線程。__malloc_alloc_template<0>,__malloc_alloc_template<1>就實例化出兩個不同的類，可以用于兩個不同的線程中，這樣既不用加鎖也不會減速 class __malloc_alloc_template { private://oom: out of memorystatic void * oom_malloc( size_t);static void * oom_realloc(void *, size_t);static void (* __malloc_alloc_oom_handler )();//這是個函數指針，是一個成員變量，而不是成員函數public:static void * allocate (size_t n) {void * result = malloc(n);if (0 == result) result == oom_malloc(n);return result;}static void deallocate(void *p, size_t) {free(p);}static void *reallocate(void *p, size_t /*old size*/, size_t new_sz) {void *result = realloc(p,new_sz);if (0 == result) return = oom_realloc(p, new_sz);return result;}static void (* set_malloc_handler (void (*f)())) () { //set_malloc_handler是一個函數，其參數是一個函數指針，其返回值也是一個函數指針。這地方要好好揣摩。如果將set_malloc_handler (void (*f)()) 看做p,則就是 (*p)(),set_malloc_handler的返回值就是pvoid (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler == f;return old;}};template<int inst> void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler) () = 0;template <int inst> void * __malloc_alloc_template<inst>::oom_malloc(size_t n) {void (* my_malloc_handler) ();void *result;for(;;) {my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler) {__THROW_BAD_ALLOC;}(*my_malloc_handler) ();//如果用戶自定義處理函數，則此函數會尋找可用的內存，并釋放這個內存result = malloc(n);//再重新嘗試配置內存if (result) return result;} }template <int inst> void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t) {void (* my_malloc_handler) ();void * result;for (;;) {my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler) {__THROW_BAD_ALLOC;}(*my_malloc_handler) ();result = realloc(p, n);if (result) return result;} }typedef __malloc_alloc_template<0> malloc_alloc; //第二級配置器template <bool threads, int inst> class __default_alloc_template { private://bytes上調至8的倍數static size_t ROUND_UP(size_t bytes) {return ( (bytes + ALIGN -1) & ~(ALIGN - 1));}private:union obj {union obj * free_list_link;}; private:static obj * free_list[NFREELISTS];static size_t FREELIST_INDEX(size_t bytes) {return ( (bytes + ALIGN -1)/ALIGN -1);}//當freelist中沒有大小為n個塊，調用此函數，會返回從內存池中返回若干個塊，將其中的一個返回，將剩余的放入freelist中static void *refill(size_t n);//從內存池中分配一大塊空間，大小為nobjs個大小為 size的塊，如果內存不足，nobjs會減小static char *chunk_alloc(size_t size, int &nobjs);static char *start_free;//內存池起始位置static char *end_free;//內存池結束位置static size_t heap_size;//一個不太重要的變量public:static void * allocate(size_t n) {obj ** my_free_list;obj * result;if (n > MAX_BYTES) return (malloc_alloc::allocate(n));my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result == 0) {void *r = refill(ROUND_UP(n));return r;}*my_free_list = result->free_list_link;return result;}static void deallocate(void *p, size_t n) {obj * q = (obj *) p;obj ** my_free_list;if (n >MAX_BYTES) {//對于大塊就free,對于小塊是要回收到freelist中，以備再次使用malloc_alloc::deallocate(p,n);return;}my_free_list = free_list + FREELIST_INDEX(n);q->free_list_link = *my_free_list;my_free_list->free_list_link = q;}static void * reallocate(void *p, size_t old_sz, size_t new_sz) {void * result;size_t copy_sz;if (old_sz > MAX_BYTES && new_sz > MAX_BYTES) {return (malloc_alloc::reallocate(p,old_sz, new_sz));}if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;result = allocate(new_sz);copy_sz = new_sz > old_sz ? old_sz : new_sz;memcpy(result, p , copy_sz);deallocate(p, old_sz);return result;} };template<bool threads, int inst> void * __default_alloc_template<threads,inst>::refill(size_t n) {int nobjs = 20;char *chunk = chunk_alloc(n, nobjs);obj ** my_free_list;obj * result;obj * current_obj, * next_obj;int i;if (1 == nobjs) return chunk;my_free_list = free_list + FREELIST_INDEX(n);result = (obj *)chunk;*my_free_list = next_obj = (obj *)(chunk + n);for (int i = 1;; ++i) {current_obj = next_obj;next_obj = (obj *)((char *)next_obj + n);if (i == nobjs - 1) {current_obj->free_list_link = NULL;break;}current_obj->free_list_link = next_obj;}return result; }template<bool threads, int inst> char *__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs) {char * result;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){//至少能提供一個塊result = start_free;nobjs = bytes_left / size;total_bytes = size * nobjs;start_free += total_bytes;return result;}else {size_t bytes_to_get = 2 * total_bytes +ROUND_UP(heap_size >> 4);//ROUND_UP(heap_size >> 4)作用不大if (bytes_left >0) {obj ** my_free_list = free_list + FREELIST_INDEX(bytes_left);((obj *)start_free)->free_list_link = *my_free_list;*my_free_list = (obj *)start_free;}start_free = (char *)malloc(bytes_to_get);if (0 == start_free) {//沒有多余內存，需要從freelist中找到塊int i;obj ** my_free_list, *p;for (i = size; i < MAX_BYTES; i += ALIGN) {my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (0 != p) {*my_free_list = p->free_list_link;start_free = (char *)p;end_free = start_free + i;return chunk_alloc(size,nobjs);}}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);}} }template<bool threads, int inst> char *__default_alloc_template<threads, inst>::start_free = 0;template<bool threads, int inst> char *__default_alloc_template<threads, inst>::end_free = 0;template<bool threads, int inst> size_t __default_alloc_template<threads, inst>::heap_size = 0;//注意一定要有typename告訴編譯器，這個模板類肯定有這個類型obj template<bool threads, int inst> typename __default_alloc_template<threads, inst>::obj * __default_alloc_template<threads, inst>::free_list[NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };typedef __default_alloc_template<false, 0> alloc;template<class T, class Alloc> class simple_alloc { public://返回n個T大小的內存static T *allocate(size_t n) {return 0 == N ? 0 : (T *) Alloc::allocate(N * sizeof(T));}static T *allocate() {return (T *) Alloc::allocate(sizeof(T));}static void deallocate(T *p, size_t n) {if (0 != n) {Alloc::deallocate(p, n * sizeof(T));}}static void deallocate(T *p) {Alloc::deallocate(p, sizeof(T));} };#endif
之下開始研究vector

參考：http://blog.csdn.net/yangzhongxuan/article/details/8017629

總結

以上是生活随笔為你收集整理的sgi allocate的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。