C++ STL : SGI-STL空间配置器源码剖析
文章目錄
- 空間配置器的概念
- SGI-STL空間配置器
- 一級空間配置器
- 二級空間配置器
- 申請空間
- 補充內存塊
- 從內存池中索要空間
- 空間回收
- 內存碎片
- 外碎片
- 內碎片
- 空間配置器的再次封裝
空間配置器的概念
空間配置器，顧名思義就是為各個容器高效的管理空間(空間的申請與回收) 的，在默默地工作。
在之前所有模擬實現的容器中，對于空間的管理都是通過直接調用new和delete來進行的，雖然代碼可以正常運行，但是還是存在著大量的缺點。
- 空間申請與釋放需要用戶自己管理，容易造成內存泄漏
- 頻繁向系統申請小塊內存塊，容易造成內存碎片
- 頻繁向系統申請小塊內存，影響程序運行效率
- 直接使用malloc與new進行申請，每塊空間前有額外空間浪費
- 申請空間失敗怎么應對
- 代碼結構比較混亂，代碼復用率不高
- 未考慮線程安全問題
基于上述的缺點，需要設計一個高效的內存管理機制。
SGI-STL空間配置器
上面所說的缺點中，最主要的其實就是頻繁向系統申請小塊內存塊而導致的內存碎片問題。因此在SGI-STL中以128字節為分界線，超過128字節的視為大塊內存，將其交給一級空間配置器處理。小于等于128字節的視為小塊內存，將其交付給二級空間配置器處理。
為什么內核中已經有了一個類似的slab分配器來管理小塊內存，STL還需要自己弄一個空間配置器呢？
一級空間配置器
一級空間配置器主要就是對malloc和free進行了一層封裝，同時加上了對oom(內存不足）的處理方法
每當通過malloc或者realloc申請空間時，如果出現了內存不足的情況，就會調用oom來進行處理。
//直接對malloc進行封裝 static void * allocate(size_t n) {void *result = malloc(n);//申請失敗時，調用設置的回調函數來進行處理if (0 == result) result = oom_malloc(n);return result; }//free static void deallocate(void *p, size_t /* n */) {free(p); }//realloc static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) {void * result = realloc(p, new_sz);if (0 == result) result = oom_realloc(p, new_sz);return result; }//設置內存不足的處理方法 static void (* set_malloc_handler(void (*f)()))() {void (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler = f;return(old); }在oom的處理方法中可以看到，其通過一個死循環，不斷地去嘗試申請空間，他期待能夠在某次調用后能夠獲取足夠的空間并將其返回，但是如果用戶沒有設置處理內存不足的回調函數，他就會通過拋出一個BAD_ALLOC異常來強行中止程序。
template <int inst> void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; #endiftemplate <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;//如果沒有設置處理方法，則直接拋出一個BAD_ALLOC的異常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 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 = realloc(p, n);if (result) return(result);} }從上面就可以看出來，一級空間配置器主要為大塊空間進行管理，所以其操作并沒有那么細致，只是簡單的為C語言的內存管理函數malloc、realloc、free進行簡單的封裝。同時，如果出現了內存不足的情況，就會在一個死循環中不斷使用用戶提供的回調函數來進行問題的處理，期待能夠獲取足夠的空間來完成任務。但是如果用戶并沒有提供這個函數，則會直接拋出BAD_ALLOC異常來終止程序，所以設計一個內存不足的處理程序是用戶的責任。
二級空間配置器
二級空間配置器專門負責處理小于128字節的小塊內存。采用了內存池的技術來提高申請空間的速度以及減少額外空間的浪費，采用哈希桶的方式來提高用戶獲取空間的速度與高效管理。
首先申請一大塊內存，并且用類似哈希桶的結構來維護這個內存池，每一個桶中裝載一個free-list單鏈表。總共維護16個free-lists，各自管理大小以8字節為倍數，依次是8， 16， 24， 32， 40， 48， 56， 64， 72， 80， 88， 96， 104， 112， 120， 128字節。
例如：
申請空間
申請空間的方式很簡單，首先根據你要申請的空間大小，來找到對應的free-list的位置，如果沒有達到8的倍數，則會將其上調，例如申請5個字節，則會補充到8個字節，然后找到0號鏈表。
補充內存塊
如果對應位置的鏈表中有內存對象，則直接取走，如果沒有，則會從內存池中拿出20個對應大小的內存對象，取走一個后將剩下的19個掛載到鏈表上。 如果內存池空間剩余空間大于1個，小于19個，則會先將一個給使用者，剩下的全部掛載到鏈表上，之后會通過chunk_alloc來重新配置堆空間，來補充內存池。
template <bool threads, int inst> void* __default_alloc_template<threads, inst>::refill(size_t n) {int nobjs = 20;//默認獲取對象個數char * chunk = chunk_alloc(n, nobjs);//獲取nobjs個內存對象obj * __VOLATILE * 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);/* Build free list in chunk */result = (obj *)chunk;//返回一個給使用者*my_free_list = next_obj = (obj *)(chunk + n);//將內存對象插入鏈表中//從第一個開始，因為第0個已經返回給使用者for (i = 1; ; i++) {current_obj = next_obj;next_obj = (obj *)((char *)next_obj + n);if (nobjs - 1 == i) {current_obj -> free_list_link = 0;break;} else {current_obj -> free_list_link = next_obj;}}return(result); }從內存池中索要空間
template <int inst> char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs) {// 計算nobjs個size字節內存塊的總大小以及內存池中剩余空間總大小char * result;size_t total_bytes = size * nobjs;size_t bytes_left = end_free - start_free;// 如果內存池可以提供total_bytes字節，返回if (bytes_left >= total_bytes){result = start_free;start_free += total_bytes;return(result);}else if (bytes_left >= size){// nobjs塊無法提供，但是至少可以提供1塊size字節內存塊，提供后返回nobjs = bytes_left/size;total_bytes = size * nobjs;result = start_free;start_free += total_bytes;return(result);}else{// 內存池空間不足，連一塊小塊村內都不能提供// 向系統堆求助，往內存池中補充空間// 計算向內存中補充空間大小：本次空間總大小兩倍 + 向系統申請總大小/16size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);// 如果內存池有剩余空間(該空間一定是8的整數倍)，將該空間掛到對應哈希桶中if (bytes_left > 0){// 找對用哈希桶，將剩余空間掛在其上obj ** my_free_list = free_list + FREELIST_INDEX(bytes_left);((obj *)start_free) -> free_list_link = *my_free_list;*my_ree_list = (obj *)start_free;}// 通過系統堆向內存池補充空間，如果補充成功，遞歸繼續分配start_free = (char *)malloc(bytes_to_get);if (0 == start_free){// 通過系統堆補充空間失敗，在哈希桶中找是否有沒有使用的較大的內存塊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置空，因為一級空間配置器一旦拋異常就會出問題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));} }空間回收
static void deallocate(void *p, size_t n) {obj *q = (obj *)p;obj ** my_free_list;// 如果空間不是小塊內存，交給一級空間配置器回收if (n > (size_t) __MAX_BYTES){malloc_alloc::deallocate(p, n);return;}// 找到對應的哈希桶，將內存掛在哈希桶中my_free_list = free_list + FREELIST_INDEX(n);q -> free_list_link = *my_free_list;*my_free_list = q; }對于二級空間配置器，其主要管理小塊內存。通過申請一個空間作為內存池，借助哈希桶來進行內存分配與回收管理，其中以8位倍數，維護了從8到128字節的16個鏈表。當申請的內存小于等于128時，就會到哈希桶對應的鏈表中下取出內存對象。如果鏈表空間不夠，則會從池中取出20個內存對象，1個拿走另外19個繼續掛載到對應的表下。如果要歸還空間時，找到對應的鏈表后再將其掛載進去即可。
內存碎片
外碎片
外碎片問題其實就是最為常見的內存碎片問題。
例如我們有16字節的內存，我們依次申請了4個字節，8個字節，4個字節的空間
之后再釋放掉那兩個4字節的空間，此時還剩8字節的空閑空間
但是如果我們想再存入8個字節的空間，此時就會出現問題，因為我們申請釋放了太多的小空間，導致此時剩余空間不連續，雖然空間足夠，但是無法給大塊數據進行存儲。外碎片的本質其實就是大量小塊空間的申請
內碎片
SGI-STL空間配置器的核心就是為了解決外碎片的問題，所以使用了二級空間配置器來對小塊空間進行管理。但是在管理的時候，又帶來了相對來使影響較小的內碎片問題。
從前面的描述也可以看到，如果申請的小塊內存大小不到8的倍數，會將其進行提升，也就是說如果我們申請的是5字節，則分配的其實是8字節。但是這里的3字節用不上，這種多余的內存也就是內碎片。所以可以看出，SGI-STL只是將外碎片問題轉換成了相對來說影響較小的內碎片問題，本質上還是存在內存碎片。
空間配置器的再次封裝
為了方便用戶的使用SGI-STL對空間配置器進行了進一步的封裝，讓用戶可以直接根據類型來完成空間的申請
空間配置由宏__USE_MALLOC控制，默認使用二級空間配置器
#ifdef __USE_MALLOC typedef malloc_alloc alloc; typedef malloc_alloc single_client_alloc; #else// 二級空間配置器定義 #endif // 注意：該類只負責申請與歸還對象的空間，不否則空間中對象的構造與析構 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)); }// 申請一個T類型對象大小的空間static T *allocate(void){ return (T*) Alloc::allocate(sizeof (T));}// 釋放n個T類型對象大小的空間static void deallocate(T *p, size_t n){ if (0 != n) Alloc::deallocate(p, n * sizeof (T));}// 釋放一個T類型對象大小的空間static void deallocate(T *p){ Alloc::deallocate(p, sizeof (T)); } };并且考慮到不是所有類型都需要調用構造和析構函數，所以他將空間管理和構造析構給拆分開來，通過placement-new來進行構造。
// 歸還空間時，先先調用該函數將對象中資源清理掉 template <class T> inline void destroy(T* pointer) {pointer->~T(); }// 空間申請好后調用該函數：利用placement-new完成對象的構造 template <class T1, class T2> inline void construct(T1* p, const T2& value) {new (p) T1(value); }總結
以上是生活随笔為你收集整理的C++ STL : SGI-STL空间配置器源码剖析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux网络编程 | 多路复用I/O
- 下一篇： 高级数据结构与算法 | 并查集(Unio