空間配置器 · STL源碼剖析

### 前言 ? [SGI STL源碼](https://www.sgi.com/tech/stl/download.html)下載地址 ? 空間配置是為存儲數據提供可用的空間，在Standard Template Library(STL)中，空間配置是最底層的東西，為容器提供服務。在C++中，一般管理內存分配是使用new和delete進行操作，這兩個操作都需要經過兩個步驟； new操作的步驟：(1)調用::operator new配置內存；(2)調用對象的構造函數構造對象并初始化。 delete操作步驟：(1)調用對象的析構函數析構對象；(2)調用::operator delete釋放內存。例如： ~~~ class Foo { ... }; Foo* pf = new Foo; ... delete pf; ~~~ ? 而在STL中，空間配置在C++的基礎上增加了一些特性。STL allocator 將這兩個階段分開操作，內存配置操作由空間配置器stl::alloc中的alloc::allocate()，內存釋放由alloc::deallocate()負責；對象構造操作由::construct()負責，對象析構操作由::destroy()負責。SGI STL中考慮到了異常處理，內置輕量級內存池（主要用于處理小塊內存的分配，應對內存碎片問題）實現，多線程中的內存分配處理（主要是針對內存池的互斥訪問）等。 ### 空間配置器的標準接口 ? 在SGI STL中，空間配置器(Allocator)的主要實現文件是alloc.h和stl_alloc.h，標準接口位于文件stl_alloc.h的588-628行；具體如下： ~~~ /*tihs program is in the file of stl_alloc.h from line 588 to 628 */ template <class _Tp> class allocator { typedef alloc _Alloc; // The underlying allocator. public: //數據類型的成員變量在后續章節(traits編程技巧)介紹 typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef const _Tp* const_pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef _Tp value_type; template <class _Tp1> struct rebind {//嵌套一個template,且僅包含唯一成員other,是一個typedef; typedef allocator<_Tp1> other; }; //下面是成員函數 allocator() __STL_NOTHROW {} //默認構造函數,__STL_NOTHROW在 stl_config.h中定義,要么為空,要么為 throw()異常機制 allocator(const allocator&) __STL_NOTHROW {} //復制構造函數 template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {}//泛化的復制構造函數 ~allocator() __STL_NOTHROW {}//析構函數 pointer address(reference __x) const { return &__x; }//返回對象的地址 const_pointer address(const_reference __x) const { return &__x; }//返回const對象的地址 // __n is permitted to be 0. The C++ standard says nothing about what // the return value is when __n == 0. _Tp* allocate(size_type __n, const void* = 0) {// 配置空間，如果申請的空間塊數不為0，那么調用 _Alloc 也即 alloc 的 allocate 函數來分配內存， //這里的 alloc 在 SGI STL 中默認使用的是__default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>這個實現（見第402行） return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0; } // __p is not permitted to be a null pointer. void deallocate(pointer __p, size_type __n)//釋放已配置的空間 { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } size_type max_size() const __STL_NOTHROW //返回可成功配置的最大值 { return size_t(-1) / sizeof(_Tp); } void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }//構造，等同于new ((void*)p) T(x) void destroy(pointer __p) { __p->~_Tp(); }//析構，等同于p->~T() }; ~~~ ? 在SGI STL的的stl_alloc.h文件中，可以看到有以下幾種空間配置的類模板： ~~~ template <int __inst> class __malloc_alloc_template // Malloc-based allocator. Typically slower than default alloc typedef __malloc_alloc_template<0> malloc_alloc template<class _Tp, class _Alloc> class simple_alloc template <class _Alloc> class debug_alloc template <bool threads, int inst> class __default_alloc_template // Default node allocator. typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc typedef __default_alloc_template<false, 0> single_client_alloc template <class _Tp>class allocator template<>class allocator<void> template <class _Tp, class _Alloc>struct __allocator template <class _Alloc>class __allocator<void, _Alloc> ~~~ ?其中simple_alloc，debug_alloc，allocator和__allocator都是對其他適配器(如__Alloc::allocate)的一個簡單封裝。__malloc_alloc_template和__default_alloc_template這兩個配置器就是SGI STL配置器的重點。其中__malloc_alloc_template是SGI STL的第一級配置器，只是對系統的malloc，realloc，free函數的一個簡單封裝，并考慮到了分配失敗后的異常處理。而__default_alloc_template是SGI STL的第二級配置器，在第一級配置器的基礎上還考慮了內存碎片的問題，通過內置一個輕量級的內存池，及在多線程環境下內存池互斥訪問的機制。 ### 第一級配置器__malloc_alloc_template:異常處理 ? 第一級配置器內存分配失敗一般是由于內存不足out-of-memory(oom)，處理異常時，首先用戶自己設計異常處理例程，若用戶沒有定義，僅僅是打印錯誤信息并強制退出。總的來說，就是留給用戶異常處理接口和默認強制退出處理。 ~~~ //異常處理 /*tihs program is in the file of stl_alloc.h*/ //line 109 to 118 class __malloc_alloc_template { private: //內存不足異常處理 static void* _S_oom_malloc(size_t); static void* _S_oom_realloc(void*, size_t); #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG static void (* __malloc_alloc_oom_handler)(); #endif //line 141 to 146 //指定自己的異常處理 static void (* __set_malloc_handler(void (*__f)()))() { void (* __old)() = __malloc_alloc_oom_handler; __malloc_alloc_oom_handler = __f; return(__old); } //line 152 to 155 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG template <int __inst> void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0; #endif //line 41 to 50 #ifndef __THROW_BAD_ALLOC # if defined(__STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS) # include <stdio.h> # include <stdlib.h> //默認的強制退出 # define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1) # else /* Standard conforming out-of-memory handling */ # include <new> //拋出用戶設計異常處理例程 # define __THROW_BAD_ALLOC throw std::bad_alloc() # endif #endif ~~~ ### 第二級配置器__default_alloc_template ? 第二級配置器主要是利用內存池進行管理小內存分配問題，并且在多線程環境下內存池的互斥訪問問題。第一級配置器__malloc_alloc_template只是malloc對的一層封裝，沒有考慮內存碎片問題。因此，第二級配置器是在第一級配置器的基礎上考慮了內存碎片問題，對于申請**內存大于**128bytes**移交給第一級配置器__malloc_alloc_template處理。對于小內存**(小于**128bytes**)**的申請，利用內存池來管理，直接從內存池分配即可，并維護自由鏈表，自由鏈表是來分配同樣的小內存和回收小內存，即程序再次申請小內存直接從自由鏈表中分配，當小內存釋放時，自由鏈表對其進行回收。 ? 為了方便管理，SGI STL第二級配置器會主動將任何小額區塊的內存需求量上調為8的倍數，即若用戶申請的小額區塊內存不滿足8的倍數時，系統自動向上取整為8的倍數。由于SGI STL第二級配置器要求小額區塊的內存最大為128bytes，則自由鏈表的個數為16個，即128/8=16；每個鏈表分別維護區塊內存大小為[![](https://box.kancloud.cn/2016-07-12_5784b87732964.latex "(8,16,24,...,128)")](http://www.codecogs.com/eqnedit.php?latex=(8,16,24,...,128))bytes。 ? 下面給出第二級配置器處理的流程圖和源代碼： ![](https://box.kancloud.cn/2016-07-12_5784b8774bd06.jpg) ~~~ /*tihs program is in the file of stl_alloc.h from line 288 to 375 */ //第二級配置器__default_alloc_template template <bool threads, int inst> class __default_alloc_template { private: // Really we should use static const int x = N // instead of enum { x = N }, but few compilers accept the former. #if ! (defined(__SUNPRO_CC) || defined(__GNUC__)) enum {_ALIGN = 8};//小額區塊的上調邊界 enum {_MAX_BYTES = 128};//小額區塊的最大內存 enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN;自由鏈表個數 # endif static size_t _S_round_up(size_t __bytes) //函數功能：調整內存大小為8的倍數 { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); } __PRIVATE: union _Obj {//自由鏈表節點屬性 union _Obj* _M_free_list_link; char _M_client_data[1]; /* The client sees this. */ }; private: # if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC) static _Obj* __STL_VOLATILE _S_free_list[]; // Specifying a size results in duplicate def for 4.1 # else static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; # endif static size_t _S_freelist_index(size_t __bytes) {//函數功能：計算所申請區塊內存在自由鏈表中對應的號數,從0開始 return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1); } // Returns an object of size __n, and optionally adds to size __n free list. static void* _S_refill(size_t __n);//填充空間,把大小為n的內存空間加到自由鏈表 // Allocates a chunk for nobjs of size size. nobjs may be reduced // if it is inconvenient to allocate the requested number. /*從內存池中分配空間，該空間可容納__nobjs大小為__size的區塊，可能會少于__nobjs個*/ static char* _S_chunk_alloc(size_t __size, int& __nobjs); // Chunk allocation state. static char* _S_start_free;//內存池起始位置 static char* _S_end_free;//內存池結束位置 static size_t _S_heap_size; # ifdef __STL_THREADS static _STL_mutex_lock _S_node_allocator_lock; # endif // It would be nice to use _STL_auto_lock here. But we // don't need the NULL check. And we do need a test whether // threads have actually been started. class _Lock; friend class _Lock; class _Lock {//該類保證內存池在多線程環境解決互斥訪問 public: _Lock() { __NODE_ALLOCATOR_LOCK; } ~_Lock() { __NODE_ALLOCATOR_UNLOCK; } }; public: /* __n must be > 0 */ static void* allocate(size_t __n) { void* __ret = 0; if (__n > (size_t) _MAX_BYTES) { __ret = malloc_alloc::allocate(__n);//內存大于128時，采用第一級配置器處理 } else { _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); // Acquire the lock here with a constructor call. // This ensures that it is released in exit or during stack // unwinding. # ifndef _NOTHREADS /*REFERENCED*/ _Lock __lock_instance; # endif _Obj* __RESTRICT __result = *__my_free_list; if (__result == 0) __ret = _S_refill(_S_round_up(__n)); else { *__my_free_list = __result -> _M_free_list_link; __ret = __result; } } return __ret; }; //初始化操作 //line from 554 to 571 template <bool __threads, int __inst> char* __default_alloc_template<__threads, __inst>::_S_start_free = 0; template <bool __threads, int __inst> char* __default_alloc_template<__threads, __inst>::_S_end_free = 0; template <bool __threads, int __inst> size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0; template <bool __threads, int __inst> typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE __default_alloc_template<__threads, __inst> ::_S_free_list[ # if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC) _NFREELISTS # else __default_alloc_template<__threads, __inst>::_NFREELISTS # endif ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; ~~~ ### 空間配置函數allocate() 空間配置函數allocate()的具體實現步驟如下： 1. 若用戶申請的內存大于128bytes，則調用第一級配置器分配空間； 1. 若小于128bytes檢查對應的自由鏈表free_list，如果自由鏈表存在可用的區塊，則直接使用，若不存在，則調用填充函數refill()為自由鏈表重新填充空間；空間配置函數allocate()的源代碼如下： ~~~ /* __n must be > 0 */ static void* allocate(size_t __n) { void* __ret = 0; if (__n > (size_t) _MAX_BYTES) { __ret = malloc_alloc::allocate(__n);//內存大于128時，采用第一級配置器處理 } else { _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); // Acquire the lock here with a constructor call. // This ensures that it is released in exit or during stack // unwinding. # ifndef _NOTHREADS /*REFERENCED*/ _Lock __lock_instance; # endif _Obj* __RESTRICT __result = *__my_free_list; if (__result == 0)//若自由鏈表free_list不存在可用的區塊，則從內存池中填充自由鏈表 __ret = _S_refill(_S_round_up(__n)); else {//若自由鏈表free_list存在可用區塊，調整free_list *__my_free_list = __result -> _M_free_list_link; __ret = __result; } } return __ret; }; ~~~ ### 空間釋放函數deallocate() ? 首先判斷區塊的大小，大于128bytes直接調用第一級配置器，若小于128bytes，則找出相應的自由鏈表free_list，將其回收。源代碼如下： ~~~ /* __p may not be 0 */ static void deallocate(void* __p, size_t __n) { if (__n > (size_t) _MAX_BYTES)//內存大于128時，采用第一級配置器處理 malloc_alloc::deallocate(__p, __n); else {//否則，找到相應的自由鏈表位置，將其回收 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); _Obj* __q = (_Obj*)__p; // acquire lock # ifndef _NOTHREADS /*REFERENCED*/ _Lock __lock_instance; # endif /* _NOTHREADS */ __q -> _M_free_list_link = *__my_free_list; *__my_free_list = __q; // lock is released here } } ~~~ ### 重新填充函數refill() ? 重新填充函數refill()是在自由鏈表不存在可用的區塊時被調用。默認是為自由鏈表申請20個節點，第1個給客戶端，剩下19個留給自由鏈表管理。原代碼如下： ~~~ /* Returns an object of size __n, and optionally adds to size __n free list.*/ /* We assume that __n is properly aligned. */ /* We hold the allocation lock. */ template <bool __threads, int __inst> void* __default_alloc_template<__threads, __inst>::_S_refill(size_t __n) { int __nobjs = 20;//默認節點數 //調用_S_chunk_alloc，從內存池中獲得內存空間 char* __chunk = _S_chunk_alloc(__n, __nobjs); _Obj* __STL_VOLATILE* __my_free_list; _Obj* __result; _Obj* __current_obj; _Obj* __next_obj; int __i; //如果只有一個區塊，返回給客戶端，自由鏈表沒有接區塊管理 if (1 == __nobjs) return(__chunk); //調整自由鏈表free_list，準備管理新節點 __my_free_list = _S_free_list + _S_freelist_index(__n); /* Build free list in chunk */ __result = (_Obj*)__chunk;//這一塊返回給客戶端 //自由鏈表free_list指向新配置的空間 *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); for (__i = 1; ; __i++) {//這里第0個返回給客戶端，所以從1開始 __current_obj = __next_obj; __next_obj = (_Obj*)((char*)__next_obj + __n); if (__nobjs - 1 == __i) { __current_obj -> _M_free_list_link = 0; break; } else { __current_obj -> _M_free_list_link = __next_obj; } } return(__result); } ~~~ ### 內存池管理機制 ? ?chunk_alloc函數具體實現步驟如下： 1. 內存池剩余空間完全滿足20個區塊的需求量，則直接獲取對應大小的空間。 1. 內存池剩余空間不能完全滿足20個區塊的需求量，但是足夠供應一個及以上的區塊，則獲取滿足條件的區塊個數的空間。 1. 內存池剩余空間不能滿足一個區塊的大小，則： - 首先判斷內存池中是否有殘余零頭內存空間，如果有則進行回收，將其編入free_list。 - 然后向heap申請空間，補充內存池。 - heap有足夠的空間，空間分配成功。 - heap空間不足，即malloc()調用失敗。則 - 查找free_list中尚有未用區塊，調整以進行釋放，將其編入內存池。然后遞歸調用chunk_alloc函數從內存池取空間供free_list備用。 - 搜尋free_list釋放空間也未能解決問題，這時候調用第一級配置器，利用out-of-memory機制嘗試解決內存不足問題。 ?源代碼如下： ~~~ /* We allocate memory in large chunks in order to avoid fragmenting */ /* the malloc heap too much. */ /* We assume that size is properly aligned. */ /* We hold the allocation lock. */ template <bool __threads, int __inst> char* __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs) { char* __result; size_t __total_bytes = __size * __nobjs;//所需總的內存塊 size_t __bytes_left = _S_end_free - _S_start_free;//內存池剩余空間 if (__bytes_left >= __total_bytes) {//若內存池剩余空間滿足20個需求，直接分配 __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } else if (__bytes_left >= __size) { /*若內存池剩余空間不滿足20個需求，但足夠滿足一個或多個，取出能夠滿足條件區塊的個數*/ __nobjs = (int)(__bytes_left/__size); __total_bytes = __size * __nobjs; __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } else { /*內存池剩余空間連一個區塊大小都無法提供*/ size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); // Try to make use of the left-over piece. if (__bytes_left > 0) { /*判斷內存池中是否有殘余零頭內存空間，如果有則進行回收，將其編入free list*/ _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__bytes_left); ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list; *__my_free_list = (_Obj*)_S_start_free; } //配置可用的堆空間，用來補充內存池空間 _S_start_free = (char*)malloc(__bytes_to_get); if (0 == _S_start_free) {//若堆空間不足 size_t __i; _Obj* __STL_VOLATILE* __my_free_list; _Obj* __p; // Try to make do with what we have. That can't // hurt. We do not try smaller requests, since that tends // to result in disaster on multi-process machines. for (__i = __size; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) { /*搜尋適當的free list（適當的是指：尚有未用區塊，并且區塊足夠大），調整以進行釋放，將其編入內存池。 **然后遞歸調用chunk_alloc函數從內存池取空間供free list。*/ __my_free_list = _S_free_list + _S_freelist_index(__i); __p = *__my_free_list; if (0 != __p) {//自由練表中存在未被使用的區塊，調整并釋放該區塊 *__my_free_list = __p -> _M_free_list_link; _S_start_free = (char*)__p; _S_end_free = _S_start_free + __i; return(_S_chunk_alloc(__size, __nobjs)); // Any leftover piece will eventually make it to the // right free list. } } _S_end_free = 0; // In case of exception.調用第一級配置器 _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get); // This should either throw an // exception or remedy the situation. Thus we assume it // succeeded. } _S_heap_size += __bytes_to_get; _S_end_free = _S_start_free + __bytes_to_get; return(_S_chunk_alloc(__size, __nobjs)); } } ~~~ ### 多線程環境下內存池互斥訪問 ? 在第二級配置器中，存在著多線程環境的內存池管理，解決多線程環境下內存池互斥訪問，需在自由鏈表free_list中進行修改調整，我們從SGI STL第二級配置器源碼中看到，嵌套一個類class _Lock ，該類的作用是解決互斥訪問，并且只有兩個函數：構造函數和析構函數；使用構造函數對內存池進行加鎖，使用析構函數對內存池進行解鎖。關于多線程內存池互斥訪問的源代碼如下： ~~~ #ifdef __STL_THREADS # include <stl_threads.h>//包含線程文件 # define __NODE_ALLOCATOR_THREADS true # ifdef __STL_SGI_THREADS // We test whether threads are in use before locking. // Perhaps this should be moved into stl_threads.h, but that // probably makes it harder to avoid the procedure call when // it isn't needed. extern "C" { extern int __us_rsthread_malloc; } // The above is copied from malloc.h. Including <malloc.h> // would be cleaner but fails with certain levels of standard // conformance. # define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \ { _S_node_allocator_lock._M_acquire_lock(); } # define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \ { _S_node_allocator_lock._M_release_lock(); } # else /* !__STL_SGI_THREADS */ # define __NODE_ALLOCATOR_LOCK \ { if (threads) _S_node_allocator_lock._M_acquire_lock(); }//獲取鎖 # define __NODE_ALLOCATOR_UNLOCK \ { if (threads) _S_node_allocator_lock._M_release_lock(); }//釋放鎖 # endif #else // Thread-unsafe # define __NODE_ALLOCATOR_LOCK # define __NODE_ALLOCATOR_UNLOCK # define __NODE_ALLOCATOR_THREADS false #endif # ifdef __STL_THREADS static _STL_mutex_lock _S_node_allocator_lock;//互斥鎖變量 # endif // It would be nice to use _STL_auto_lock here. But we // don't need the NULL check. And we do need a test whether // threads have actually been started. class _Lock; friend class _Lock; class _Lock {//解決內存池在多線程環境下的管理 public: _Lock() { __NODE_ALLOCATOR_LOCK; } ~_Lock() { __NODE_ALLOCATOR_UNLOCK; } }; ~~~ 參考資料： http://ibillxia.github.io/blog/2014/06/13/stl-source-insight-1-memory-allocator/ http://blog.csdn.net/xiajun07061225/article/details/8807890 http://www.cnblogs.com/kanego/archive/2012/08/14/2638818.html