stl分析之allocator

在STL中，Memory Allocator 處于最底層的位置，為一切的 Container 提供存儲服務，是一切其他元件的基石。對于一般使用 STL 的使用者而言，Allocator 是不可見的，如果需要對 STL 進行擴充，如編寫自定義的容器，就需要調用 Allocator 的記憶體配置設定函數進行空間配置。

在C++中，一個對象的記憶體配置和釋放一般都包含兩個步驟，對于記憶體的配置，首先是調用operator new來配置記憶體，然後調用對象的類的構造函數進行初始化；而對于記憶體釋放，首先是調用析構函數，然後調用 operator delete進行釋放。 如以下代碼：

class FooFoo* pf = new... delete pf;

Allocator 的作用相當于operator new 和operator delete的功能，隻是它考慮得更加細緻周全。SGI STL 中考慮到了記憶體配置設定失敗的異常處理，内置輕量級記憶體池（主要用于處理小塊記憶體的配置設定，應對記憶體碎片問題）實作， 多線程中的記憶體配置設定處理（主要是針對記憶體池的互斥通路）等，本文就主要分析 SGI STL 中在這三個方面是如何處理的。在介紹着三個方面之前，我們先來看看 Allocator的标準接口。

1. Allocator 的标準接口

在 SGI STL 中，Allocator的實作主要在檔案 ​

​alloc.h​

​​ 和 ​

​stl_alloc.h​

​​ 檔案中。根據 STL 規範，Allocator 需提供如下的一些接口（見 ​

​stl_alloc.h​

​ 檔案的第588行開始的class template allocator）：

// 辨別資料類型的成員變量，關于中間的6個變量的涵義見後續文章（關于Traits程式設計技巧）typedeftypedeftypedeftypedeftypedef consttypedeftypedef consttypedeftemplate <class _Tp1> structtypedef}; // 一個嵌套的class template，僅包含一個成員變量 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對象的位址_Tp* allocate(size_type __n, const void* = 0) { return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0; // 配置空間，如果申請的空間塊數不為0，那麼調用 _Alloc 也即 alloc 的 allocate 函數來配置設定記憶體，} //這裡的 alloc 在 SGI STL 中預設使用的是__default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>這個實作（見第402行）void deallocate(pointer __p, size_type __n) { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } // 釋放空間size_type max_size() const __STL_NOTHROW // max_size() 函數，傳回可成功配置的最大值return size_t(-1) / sizeof(_Tp); } //這裡沒看懂，這裡的size_t(-1)是什麼意思？void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } // 調用 new 來給新變量配置設定空間并指派void destroy(pointer __p) { __p->~_Tp(); } // 調用 _Tp 的析構函數來釋放空間

在SGI STL中設計了如下幾個空間配置設定的 class template：

template <int __inst> class __malloc_alloc_template // Malloc-based allocator. Typically slower than default alloctypedef __malloc_alloc_template<0> malloc_alloctemplate<class _Tp, class _Alloc> class simple_alloctemplate <class _Alloc> class debug_alloctemplate <bool threads, int inst> class __default_alloc_template // Default node allocator. typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloctypedef __default_alloc_template<false, 0> single_client_alloctemplate <class _Tp>class allocatortemplate<>class allocator<void> template <class _Tp, class _Alloc>struct __allocatortemplate <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​

​​ 函數的一個簡單封裝，并考慮到了配置設定失敗後的異常處理。而 ​

​__default_alloc_template​

​ 是SGI STL 的第二層配置器，在第一層配置器的基礎上還考慮了記憶體碎片的問題，通過内置一個輕量級的記憶體池。下文将先介紹第一級配置器的異常處理機制，然後介紹第二級配置器的記憶體池實作，及在多線程環境下記憶體池互斥通路的機制。

2. SGI STL 記憶體配置設定失敗的異常處理

記憶體配置設定失敗一般是由于out-of-memory(oom)，SGI STL 本身并不會去處理oom問題，而隻是提供一個 private 的函數指針成員和一個 public 的設定該函數指針的方法，讓使用者來自定義異常處理邏輯：

private: #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUGstatic void (* __malloc_alloc_oom_handler)(); // 函數指針#endifpublic: static void (* __set_malloc_handler(void (*__f)()))() // 設定函數指針的public方法 { void __malloc_alloc_oom_handler = __f; return(__old); }

如果使用者沒有調用該方法來設定異常處理函數，那麼就不做任何異常處理，僅僅是想标準錯誤流輸出一句out of memory并退出程式（對于使用new和C++特性的情況而言，則是抛出一個 ​

​std::bad_alloc()​

​​ 異常）， 因為該函數指針的預設值為0，此時對應的異常處理是 ​

​__THROW_BAD_ALLOC​

​ ：

// line 152 ~ 155#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUGtemplate <intvoid (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0; #endif// in _S_oom_malloc and _S_oom_realloc__my_malloc_handler = __malloc_alloc_oom_handler; if (0// in preprocess, line 41 ~ 50#ifndef __THROW_BAD_ALLOC# if# include <stdio.h># include <stdlib.h># define# else# include <new># define# endif#endif

SGI STL 記憶體配置失敗的異常處理機制就是這樣子了，提供一個預設的處理方法，也留有一個使用者自定義處理異常的接口。

3. SGI STL 内置輕量級記憶體池的實作

第一級配置器 ​

​__malloc_alloc_template​

​​ 僅僅隻是對 ​

​malloc​

​​ 的一層封裝，沒有考慮可能出現的記憶體碎片化問題。記憶體碎片化問題在大量申請小塊記憶體是可能非常嚴重，最終導緻碎片化的空閑記憶體無法充分利用。SGI 于是在第二級配置器​

​__default_alloc_template​

​ 中 内置了一個輕量級的記憶體池。 對于小記憶體塊的申請，從内置的記憶體池中配置設定。然後維護一些空閑記憶體塊的連結清單（簡記為空閑連結清單，free list），小塊記憶體使用完後都回收到空閑連結清單中，這樣如果新來一個小記憶體塊申請，如果對應的空閑連結清單不為空，就可以從空閑連結清單中配置設定空間給使用者。具體而言SGI預設最大的小塊記憶體大小為128bytes，并設定了128/8=16 個free list，每個list 分别維護大小為 8, 16, 24, …, 128bytes 的空間記憶體塊（均為8的整數倍），如果使用者申請的空間大小不足8的倍數，則向上取整。

SGI STL内置記憶體池的實作請看 ​

​__default_alloc_template​

​ 中被定義為 private 的這些成員變量和方法（去掉了部分預處理代碼和互斥處理的代碼）：

private: #ifenum {_ALIGN = 8}; // 對齊大小enum {_MAX_BYTES = 128}; // 最大有内置記憶體池來配置設定的記憶體大小enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN // 空閑連結清單個數# endifstatic size_t _S_round_up(size_t __bytes) // 不是8的倍數，向上取整return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); } __PRIVATE: // 空閑連結清單的每個node的定義 union _Obj* _M_free_list_link; char _M_client_data[1]; }; static _Obj* __STL_VOLATILE _S_free_list[]; // 空閑連結清單數組static size_t _S_freelist_index(size_t __bytes) { // __bytes 對應的free list的indexreturn (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1); } static void* _S_refill(size_t __n); // 從記憶體池中申請空間并建構free list，然後從free list中配置設定空間給使用者static char* _S_chunk_alloc(size_t __size, int& __nobjs); // 從記憶體池中配置設定空間static char* _S_start_free; // 記憶體池空閑部分的起始位址static char* _S_end_free; // 記憶體池結束位址static size_t _S_heap_size; // 記憶體池堆大小，主要用于配置記憶體池的大小

其中 ​

​_S_refill​

​​ 和 ​

​_S_chunk_alloc​

​​ 這兩個函數是該記憶體池機制的核心。​

​__default_alloc_template​

​​ 對外提供的 public 的接口有 ​

​allocate​

​​ ,​

​deallocate​

​​ 和 ​

​reallocate​

​​ 這三個，其中涉及記憶體配置設定的 ​

​allocate​

​​ 和​

​reallocate​

​​ 的邏輯思路是，首先看申請的size（已round up）對應的free list是否為空，如果為空，則調用 ​

​_S_refill​

​​ 來配置設定，否則直接從對應的free list中配置設定。而​

​deallocate​

​ 的邏輯是直接将空間插入到相應free list的最前面。

函數 ​

​_S_refill​

​​ 的邏輯是，先調用 ​

​_S_chunk_alloc​

​​ 從記憶體池中配置設定20塊小記憶體（而不是使用者申請的1塊），将這20塊中的第一塊傳回給使用者，而将剩下的19塊依次連結，建構一個free list。這樣下次再申請同樣大小的記憶體就不用再從記憶體池中取了。有了 ​

​_S_refill​

​​ ，使用者申請空間時，就不是直接從記憶體池中取了，而是從 free list 中取。是以 ​

​allocate​

​​ 和 ​

​reallocate​

​​ 在相應的free list為空時都隻需直接調用​

​_S_refill​

​ 就行了。

這裡預設是依次申請20塊，但如果記憶體池空間不足以配置設定20塊時，會盡量配置設定足夠多的塊，這些處理都在 ​

​_S_chunk_alloc​

​ 函數中。該函數的處理邏輯如下（源代碼這裡就不貼了）：

1) 能夠配置設定20塊

從記憶體池配置設定20塊出來，改變 ​

​_S_start_free​

​ 的值，傳回配置設定出來的記憶體的起始位址

2) 不足以配置設定20塊，但至少能配置設定一塊

配置設定經量多的塊數，改變 ​

​_S_start_free​

​ 的值，傳回配置設定出來的記憶體的起始位址

3) 一塊也配置設定不了

首先計算新記憶體池大小 ​

​size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)​

​​ 

将現在記憶體池中剩餘空間插入到适當的free list中 

調用 ​​

​malloc​

​​ 來擷取一大片空間作為新的記憶體池： 

– 如果配置設定成功，則調整 ​​

​_S_end_free​

​​ 和 ​

​_S_heap_size​

​ 的值，并重新調用自身，從新的記憶體池中給使用者配置設定空間； – 否則，配置設定失敗，考慮從比目前申請的空間大的free list中配置設定空間，如果無法找不到這樣的非空free list，則調用第一級配置器的allocate，看oom機制能否解決問題

SGI STL的輕量級記憶體池的實作就是醬紫了，其實并不複雜。

4. SGI STL 記憶體池在多線程下的互斥通路

//// in __default_alloc_template# ifdef __STL_THREADSstatic _STL_mutex_lock _S_node_allocator_lock; // 互斥鎖變量# endifclasspublic: _Lock() { __NODE_ALLOCATOR_LOCK; } ~_Lock() { __NODE_ALLOCATOR_UNLOCK; } }; //// in preprocess#ifdef __STL_THREADS# include <stl_threads.h> // stl 的線程，隻是對linux或windows線程的一個封裝# define# ifdef __STL_SGI_THREADS# define __NODE_ALLOCATOR_LOCK if// 擷取鎖# define __NODE_ALLOCATOR_UNLOCK if// 釋放鎖# else# defineif# defineif# endif#else# define# define# define#endif