從 STL 實現(xiàn)角度 看,
`allocator 是 STL 其他組件實現(xiàn) 的 基礎`
allocator 稱為 空間配置器, 而不是 內存配置器,
因為 空間 可以是 內存/磁盤/其他存儲介質
1 仿 SGI std::allocator 設計 1個 符合 STL規(guī)范 的 allocator
// MyAllocator.h
#ifndef _MYALLOC_
#define _MYALLOC_
#include <new> // placement new, set_new_handler()
#include <cstddef> // ptrdiff_t size_t
#include <cstdlib> // exit()
#include <climits> // UINT_MAX
#include <iostream>// ceer
namespace MY
{
//(1) 4大 global func: 分配/釋放memory 構造/析構 obj
// 用于 被 allocator class 相應 mem func 調用
template <class T>
T* _allocate(ptrdiff_t n, T*)
{
//set_new_handler(0);
T* p = (T*)(::operator new((size_t)(n * sizeof(T) ) ) );
if (p == 0)
{
std::cout << "out of memory" << std::endl;
exit(1);
}
return p;
}
template <class T>
void _deallocate(T* p)
{
::operator delete(p);
}
template <class T1, class T2>
void _construct(T1* p, const T2& value)
{
new(p) T1(value); // placement new
}
template <class T>
void _destory(T* p)
{
p->~T();
}
template <class T>
class allocator
{
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
template <typename U>
struct rebind
{
typedef allocator<U> other;
};
// 4大函數: 分配/釋放內存 構造/析構對象
pointer allocate(size_type n)
{
return _allocate( (difference_type)n, (pointer)0);
}
void deallocate(pointer p, size_type n) // n 沒用
{
_deallocate(p);
}
void construct(pointer p, const T& value)
{
_construct(p, value);
}
void destory(pointer p)
{
_destory(p);
}
pointer address(reference x)
{
return (pointer)&x;
}
const_pointer const_address(const_reference x)
{
return (const_pointer)&x;
}
size_type max_size() const
{
return size_type(UINT_MAX / sizeof(T));
}
};
} // end of namespace MY
#endif //MYAllocator
#include "MyAllocator.h"
#include <vector>
#include <iostream>
int main()
{
int a[3] = {0, 1, 2};
std::vector<int, MY::allocator<int> > vec(a, a+3);
for(int i = 0; i < vec.size(); i++)
std::cout << vec[i] << std::endl;
}
Ubuntu 下 g++ 編譯 運行正常, gdb調試
image.png
2 SGI 版本 從 標準 std::allocator 到 具有內存池設計 的 std::alloc
1. P.J. 分配器 和 gcc2.91 標準分配器, 都叫 std::allocator,
它 沒有 獨特設計, 底層都是 直接調 malloc / free
malloc 分配的內存 = 申請的內存 + 上/下 cookie
若頻繁申請 小型區(qū)塊, 比如 8Bytes,
則 cookie 就占了 一半內存
-> `空間利用率低, 且易造成 內存碎片
-> 解決: 內存池 設計
2. gcc2.91 有 標準分配器 std::allocator 卻不用,
而是用 special allocator std::alloc
其設計思維為:
(1) 多線程: 本節(jié)不討論
(2) 模擬 C++ set_new_handler, 以處理 內存不足 狀況
(3) 內存池 設計: 以應對 頻繁申請 小型區(qū)塊 時, 空間利用率低 與 內存碎片 問題
兩級 配置器:
第1級 處理 >128 Bytes 區(qū)塊: 仿 set_new_handler
第2級 處理 8*n (n = 1,...,16) <= 128 Bytes 區(qū)塊:
16 個 free-list + 內存池
3. 16 個 free-list + 內存池
申請 n <= 128 Bytes 時, 多分配若干 Bytes, 存于
兩級緩存
第 1 / 2 級放 free-list / 內存池, 使得
下次申請 ( 的 區(qū)塊大小 前面已申請過 ) 時, 可能 直接/間接 從 free-list / 內存池 中 取, 而不是 又 讓 OS 分配
// request memory block 的 process strategy:
if (memory pool 完全滿足需求: <= 20 個 區(qū)塊.
若 modify internal_req_obj_num, 則 取 < )
(1) 提供 所需
else if (memory pool 不完全滿足需求, 但能提供 n >=1 個 區(qū)塊)
(2) 提供 n 個區(qū)塊
modify internal_req_obj_num
else // memory pool 連 1個 區(qū)塊 也 提供不了
(3) 先將 memory pool 所有剩余 space 配給 相應 free_list[i]
(4) 再向 OS 申請 -> malloc 分配 heap memory: bytes_to_get
若 heap memory 不足 -> malloc 失敗
(5) 循環(huán)遍歷 free_list[i, i+1, ...] 中
larger( => 必為 req_mem_blk_size_8_align 整數倍
=> 必 在 更后面的 free_list[j>i] )
且 unused 區(qū)塊
若有
(6) 撥出 1 個 mem_blk 放 memory pool(當前已 empty)
(7) 遞歸 調 chunk_alloc 自身, 再次 從 memory pool 申請
modify internal_req_obj_num
4. free-list + 內存池 分配 的 例子
(1) 初次申請 32 Bytes
free-list[32/8 -1= 3] 和 內存池 均 empty,
-> malloc 分配 2 * 20 * 32 Bytes +
隨 分配次數增大而增大的 附加量 ( 初始 為 0 )
= 40 * 32 Bytes:
1) 第 1 個 32 Bytes return 給 client
2) 隨后 19 * 32 Bytes 放 free-list ( 第 1 級 緩存 )
3) 隨后 20 * 32 Bytes 放 內存池 ( 第 2 級 緩存 )
(2) 第 2 次 申請 64 Bytes
free-list[64/8 - 1] = free-list[7] empty
-> 嘗試 從 內存池 取, 取 20*32/64 = 10 個 64 Bytes 區(qū)塊:
第 1 個 return 給 client /
隨后 (只剩) 9 個放 free-list[7] /
內存池 become empty /
(3) 第 3 次 申請 96 Bytes
free-list[11] 和 內存池 均 empty
-> malloc 分配 2 * 20 * 96 + n (余量) Bytes:
第 1 個 96 Bytes return 給 client /
隨后 19 * 96 Bytes 放 free-list[11] /
其余放 內存池
image.png
5. 1/2 級 allocator + wrapper class template simple_alloc + vector 容器 -> framework
下圖中 第1級 配置器 type 別名 不對, 應該為 malloc_alloc
image.png
兩級 allocator 本身 均為 class template:
但無 template para, 都 只是 普通參數
inst 完全沒用 + 第 2 級 allocator 多線程參數 本節(jié)不考慮
-> 本文 source code 中 allocator name 中不帶 template
// 第 1 級 allocator
template <int inst>
class __malloc_alloc_template;
// 第 2 級 allocator
template <bool threads, int inst>
class __default_alloc_template;
別名:
__malloc_alloc / malloc_alloc
__default_alloc_template / alloc
simple_alloc<...> / data_allocator
#include <cstddef> // std::size_t
//------ 1. 第 1 級 allocator
class __malloc_alloc
{
public:
static void* allocate(size_t n)
{
//(1)
set_new_handler(handler); //<=> set_new_handler(&handler);
void* result = malloc(n);
// malloc 失敗時, 調 oom_malloc()
if (0 == result)
result = oom_malloc(n);
return result;
}
// ...
static void deallocate(void* p, size_t)
{
free(p);
}
};
typedef __malloc_alloc malloc_alloc;
//------ 2. 第 2 級 allocator
class __default_alloc
{
public
static void*
allocate(size_t req_blk_size)
{ // client 請求: req_blk_size
if( req_blk_size > (size_t)MAX_BYTE )
{
return ( malloc_alloc::allocate(req_blk_size) );
}
// ...
void *result_prev = refill( ROUND_UP(req_blk_size) );
}
void* refill(size_t req_blk_size_align)
{
//(1) req_blk_num: allocator 內部 (欲) 請求
// 1) 嘗試 向 memory pool 請求 20 個 memory block
// 放 相應 free_list:
// 2) pass by reference to chunk_alloc to be modified
int req_blk_num = 20;
//(2) request memory_block from memory pool
// 1) memory pool 能提供 幾(>= 1) 個 memory block,
// 就 分配 幾個
// 2) 若 連 1 個 也 提供不了,
// 則 剩余 space 先配給 相應 free_list[i]
// 再 向 OS 申請: malloc 分配
char* chunk =
chunk_alloc(req_blk_size_align, req_obj_num);
//(3) 將 分配的 chunk memory:
// 1) return to client
// 2) 放 相應 free_list[i]
// 3) 放 memory pool (maybe)
}
// request memory_block from memory pool
// memory_block 用 union obj 表示
char* chunk_alloc(size_t req_blk_size_align, int& req_obj_num)
{
if ( memory pool 完全滿足需求: <= 20 個 區(qū)塊. 若 modify req_obj_num, 則 取 < )
提供 所需
else if (memory pool 不完全滿足需求, 但能提供 n >=1 個 區(qū)塊)
提供 n 個區(qū)塊
modify req_obj_num
else // memory pool 連 1個 區(qū)塊 也 提供不了
{
bytes_to_get = 2 * half_blks_bytes_to_get
+ ROUND_UP(heap_size >> 4);
(4) 先將 memory pool 所有剩余 space 配給 相應 free_list[i]
(5) 再向 OS 申請 -> malloc 分配 heap memory: bytes_to_get
若 heap memory 不足 -> malloc 失敗
{
(6) 從 req_blk_size_align 相應 free_list[i]
下一 free_list 開始,
循環(huán)遍歷 后面 free_list[ j > i ]: 可能含 `unused larger 區(qū)塊`
{
若 free_list[j] 有 `unused larger 區(qū)塊(必為 req_blk_size_align 整數倍)`
{
(7) 從 free_list[j] 撥出 1 個 mem_blk
放 memory pool(當前已 empty),
即 adjust 3 個 pointer:
相應 *my_free_list 指向 原先 list 下一 obj
memory pool start/end pinter 指向 撥出的 mem_blk 首/尾
(8) return ( chunk_alloc(req_blk_size_align, req_obj_num) );
遞歸 調 chunk_alloc 自身, 再次 從 memory pool 申請,
以 modify req_obj_num
只 遞歸 1次 就結束
因為 從 相應 free_list[i]
撥到 memory pool 的 mem_blk
必然 是 req_blk_size_align 的 整數倍
}
}
(9) 若執(zhí)行到 該行 => free_list 也沒 空間了
1) memory pool 尾 pointer 先置 空: end_free = 0;
2) 調 第 1 級 allocator, 看 out-of-memory 機制 是否能 分配
star_free = (char*)malloc_alloc::allocate(bytes_to_get);
}
(8) update heap_size:
每次 向 memory pool 請求 memory 時,
若 走 case3 向 OS 請求,
則 要 增加 heap_size += byte_to_get
使得 下次 再向 OS 申請 時, 再多申請些
(10) return ( chunk_alloc(req_blk_size_align, req_obj_num) );
遞歸 調 chunk_alloc 自身, 再次 從 memory pool 申請,
}
}
};
// default value of template para in vector
typedef __default_alloc alloc;
//------ 3. wrapper class template: simple_alloc
//(1) 意義: 兩級 allocator 分配/釋放 memory 的
// interface func para 是 req_blk_size_align
// => directly call 時, 要 指定 req_blk_size_align
// 而 對 client 而言, 更方便的 interface 是
// 只指定 要 分配/釋放 的 elem_type 及 elem_num
// -> solution: 加 1 層 中介層
// 1) 據 elem_type 及 elem_num -> 求 req_blk_size_align
// 2) call allocate/deallocate
// -> implememt: wrapper class template
//(2) 分配/釋放 memory 的 strategy:
// directly call 第 2 級 allocator 的 allocate/deallocate func
// -> 據 memory size > 128 Bytes 時,
// 再 轉調 第 1 級 allocator 的 allocate/deallocate func
template<class T, class Alloc>
class simple_alloc
{
public:
static T*
allocate(size_t elem_num)
{
return 0 == elem_num ? 0 :
T * Alloc::allocate(elem_num * sizeof(T) );
}
static void
deallocate(T* p, size_t elem_num)
{
if( elem_num != 0)
Alloc::deallocate(p, elem_num * sizeof(T) );
}
};
//------ 4. 容器: 直接 用 wrapper class
// 容器 的 2 個 template para 綁定 在一起
template <class T, class Alloc = alloc >
class vector
{
// ...
protected:
typedef simple_alloc<T, Alloc> data_allocator;
iterator // T*
allocate_and_fill(size_type elem_num, const T& x)
{
iterator result = data_allocator::allocate(elem_num);
std::uninitialized_fill_n(result, elem_num, x);
return result;
}
void deallocate()
{
if(start)
data_allocator::deallocate(start,
end_of_storage - start);
}
};
//------ heap_size
請求次序 req_blk_size req_obj_num 是否向 OS 請求
1 32 20 是
2 64 20->10 否
3 96 20-> 是
請求次序 bytes_to_get heap_size
1 2*(20*32)=1280+0 0 -> += 1280 = 1280
2 不計算 不計算
3 2*(20*96)+1280>>4 -> 8倍數 1280 -> += 3920 = 5200
= 3840 + 80 = 3920
(1) client 請求的 memory block:
req_blk_size
(2) allocator 內部 欲請求 byte 數: 分 2 部分
1) 多請求 的 若干塊: internal_req_obj_num
2) 每次向 OS 請求, 會 將
allocator 內部 欲請求 byte 數
累加 到 1個 static 累加量 heap_size 中,
下次 再 OS 請求 時, 在 `多請求的 若干塊 之外`,
再 附加 該 累加量 heap_size 除 16 -> 上調到 8 的 倍數
使得 再多分配些
allocator 內部 欲請求 byte 數
= bytes_to_get
= 2 * half_blks_bytes_to_get + ROUND_UP(heap_size >> 4)
maybe 不等于 最終分配的 byte 數
half_blks_bytes_to_get
= req_blk_num_unmodified * req_blk_size_align
= 20 * req_blk_size_align = 8 的 倍數
ROUND_UP(heap_size >> 4)
= 除 16 result -> 上調到 8 的 倍數
3 第 1 級 allocator 設計
3.1 std::set_new_handler: <new>
typedef void (* new_handler)();
std::new_handler
set_new_handler (std::new_handler new_p) throw();
std::set_new_handler is called by the default allocation functions ( operator new and operator new[] ) when they fail to allocate storage
Para:
new_p: pointer to function of type std::new_handler, or null pointer
Return value:
previously-installed new handler, or a null pointer value if none was installed.
用途:
1) make more memory available
2) terminate the program (e.g. by calling std::terminate)
3) throw exception of type std::bad_alloc or ...
#include <iostream>
#include <new>
void handler()
{
std::cout << "Memory allocation failed, terminating\n";
std::set_new_handler(nullptr);
}
int main()
{
std::set_new_handler(handler);
try
{
while (true)
{
new int[100000000ul];
}
}
catch (const std::bad_alloc& e)
{
std::cout << e.what() << '\n';
}
}
3.2 第 1 級 allocator: malloc_alloc
模擬 C++ 中 std::set_new_handler, 以處理 memory 不足 的 case
// 模擬 std::set_new_handler implement
typedef void (* new_handler)();
// 2 者 等價: 用 typedef 的 別名 最 simple
new_handler set_new_handler(new_handler pf)
void (* set_new_handler( void (* pf)() ) ) ()
typedef 優(yōu)勢在此十分明顯, 清楚的指出
set_new_handler return value 為 function pointer type,
the pointed func taking no arguments and returning no value
4 第 2 級 allocator: std::alloc 設計
image.png
5 第1/2 級 allocator source code
1. std::alloc 管理 free_list 的 設計思路
(1) list node 的 pointer 域 不獨占 memory 的 設計
通常, list 的 每個 node 要設一 額外 pointer 域 next,
以 指向 the next node
節(jié)省 該 pointer 域 memory space 的 方法:
1) 第 i 條 free_list[ i = 0-15 ] 管理 最多 20 個 node
`每個 node 表示 1個 大小為 8*(i+1) Bytes 的 memory block`
2) `pointer 域 只占 4 Bytes (32 位 OS)`
3) memory block is `uninitialized`
設 node 最前面的 4 Bytes memory 的 data structure 為 1 個 名為 obj 的 union
union obj
{
union obj* next;
char client_data[1];
};
從 第 1 / 2 字段 觀之, obj is a pointer to the next obj union / the first char memory of the current memory block
the requested req_blk_num 個 mem_blk 是 連續(xù) memory
用 union 實現(xiàn) 一物二用
使得 管理 list 時, 無需 為 每個 node 單獨分配 pointer 域,
提高了 memory 空間利用率
Java 中 無法實現(xiàn) 該 技巧
(2) free_list[ FREE_LIST_NUM ] array
1) 放 private: 只 std::alloc 內部用
2) array elem: free_list[i = 0-15]
is the head pointer to the first obj of the ith list
type: obj*
3) array name: free_list
type: obj**
2. volatile
(1) volatile
tell compiler 其 修飾的 variable 隨時可變,
編譯后的 code 每次 read/write 該 variable 時,
`直接 對 variable memory read/write`
若無 volatile, 則 compiler 可能
借助 register/高速cache 優(yōu)化 read/store(write)
(2) 含義:
1) volatile `總是 與 compiler 優(yōu)化 相關`
2) volatile 字面含義是 易變的
(3) 作用:
1) 告訴 compiler 不要 cache variable 到 register/高速cache
`多任務 / 中斷` 下, variable 可能被 other program(如 thread) 改變,
compiler 無法感知到, volatile 就是 告訴 compiler
不要 在 兩個操作 之間 緩存 variable 到 register/高速cache
2) 對 volatile variable 的 read/write 不會被 優(yōu)化掉
(4) note: volatile 并不保證 對 內存操作 的 原子性
#include <iostream>
//------ 1. 第 1 級 allocator
class __malloc_alloc
{
private:
// note: func name 本身就是 func address:
// 即 func <=> &func
//(1) new_handler : 為 func pointer type
// new_handler pf : pf 為 func pointer
// void (* pf)() : pf 為 func pointer
typedef void (*new_handler)();
//(2) global handler : record the current func pointer
static new_handler global_handler;
public:
static void* allocate(size_t n)
{
//(3)
set_new_handler(handler); //<=> set_new_handler(&handler);
void* chunk = malloc(n);
// malloc 失敗時, 調 oom_malloc()
if (0 == chunk)
chunk = oom_malloc(n);
return chunk;
}
//(4) set_new_handler: 仿 std::set_new_handler
static new_handler set_new_handler(new_handler pf)
{
new_handler previous_handler = global_handler;
// update global handler to be specified func's pointer
global_handler = pf;
return previous_handler;
}
//(5) handler func
static void handler()
{ // 企圖 釋放 memory
std::cout << "make more memory available\n";
std::set_new_handler(nullptr);
}
//(6)
static void* oom_malloc(size_t n)
{
new_handler local_handler = 0;
void* mem;
// 不斷嘗試(這里限制次數) 釋放, 配置, 釋放, 配置
for (int i = 0; i < 3; i++)
{
// 1) 取 the recorded handler func pointer from global_handler
local_handler = global_handler;
if (0 == local_handler)
continue;
// 2) 調 specified handler func
(*local_handler)();
// 3) malloc again
mem = malloc(n);
if (mem)
return mem;
}
}
static void deallocate(void* p, size_t)
{
free(p);
}
};
typedef __malloc_alloc malloc_alloc;
malloc_alloc::new_handler malloc_alloc::global_handler = 0;
//------ 2. 第 2 級 allocator
//--- 3個 enum
enum
{
ALIGN = 8 // 最小 memory block
};
enum { MAX_BYTES = 128 };
enum { FREE_LIST_NUM = MAX_BYTES / ALIGN }; // 16 條 free_list
class __default_alloc
{
private:
// union 一物二用: 實現(xiàn) 節(jié)省 list node 的 pointer 域 空間
union obj
{
union obj* next;
char client_data[1];
};
// --- 4 static mem
// free_list[16] array: 16 free-list
static obj* volatile
free_list[FREE_LIST_NUM];
// memory pool management: 2 pointer
static char* start_free;
static char* end_free;
// accumulate var: request memory from OS 時,
// 用于 下次再 request from OS 時, 附加 request 的量
static size_t heap_size;
// request_mem_blk_bytes -> which free_list: free_list[i]
static size_t freelist_index(size_t request_mem_blk_bytes)
{
return (request_mem_blk_bytes + ALIGN - 1) / ALIGN - 1;
}
// request_mem_blk_bytes 上調至 8(= b1000) 的倍數:
// & 1111 1000 = & ~(ALIGN - 1)
static size_t ROUND_UP(size_t request_mem_blk_bytes)
{
return (request_mem_blk_bytes + ALIGN - 1) & ~(ALIGN - 1);
}
static void* refill(size_t n);
static char* chunk_alloc(size_t n, int& req_blk_num );
public: // 2 interface func
static void* allocate(size_t req_blk_size);
static void deallocate(void* p, size_t n);
};
typedef __default_alloc alloc;
//--- 4 static mem data initialize
alloc::obj* volatile
alloc::free_list[FREE_LIST_NUM] = { 0 };
char* alloc::start_free = 0;
char* alloc::end_free = 0;
size_t alloc::heap_size = 0;
void* alloc::allocate(size_t req_blk_size)
{ // client 請求: req_blk_size, 只 請求 1 個 memory blk
obj* volatile* my_free_list;
obj* target_free_list_pobj;
if( req_blk_size > (size_t)MAX_BYTES )
{
// 轉向 調 第 1 級 allocator
return ( malloc_alloc::allocate(req_blk_size) );
}
my_free_list = free_list + freelist_index(req_blk_size);
target_free_list_pobj = *my_free_list;
if (target_free_list_pobj == 0) // list empty
{
// request mem-blk from memory pool
void *res = refill( ROUND_UP(req_blk_size) );
return res;
}
// seperate the first mem_blk from target_free_list
*my_free_list = target_free_list_pobj->next;
// void* p = pobj => pobj implicitly converted to void*
return target_free_list_pobj;
}
void* __default_alloc::refill(size_t req_blk_size_align)
{
int req_blk_num = 20;
//(1) allocator 內部 嘗試 / 實際 request
// req_blk_num < / = 20 個 區(qū)塊 from memory pool
// req_blk_num pass by reference to be modified
char* chunk = chunk_alloc(req_blk_size_align, req_blk_num );
obj* volatile* my_free_list;
obj* return_pobj, * current_pobj, * next_pobj;
//(2) 只請求到 1 個 mem_blk
if (0 == req_blk_num || 1 == req_blk_num ) // else >= 2
return chunk;
//(3) the first mem_blk to be returned to client
return_pobj = (obj*)chunk;
//(4) other req_blk_num -1 個 mem_blks linked to free_list
my_free_list = free_list
+ freelist_index(req_blk_size_align);
*my_free_list
= next_pobj
= (obj*)(chunk + req_blk_size_align);
// 第 2th ~ req_blk_num th mem_blk linked to list
// the requested req_blk_num 個 mem_blk 是 連續(xù) memory
// loop every mem_blk:
// 1) initialize next_head point to the start
// 2) current_head point to next_head
// 3) next_head updated to point to the real next blk
// => [current_head, next_head) 為 the current blk
// 4) link
for (int i = 0; ; i++)
{
current_pobj = next_pobj;
next_pobj = (obj*)( (char*)next_pobj
+ req_blk_size_align );
// 第 2 ~ req_blk_num - 1 個 blk
if (i < req_blk_num - 2)
{
current_pobj->next = next_pobj;
}
else // 第 req_blk_num 個 blk
{
current_pobj->next = 0;
break;
}
}
return return_pobj;
}
char* __default_alloc::
chunk_alloc(size_t req_blk_size_align, int& req_blk_num )
{
char* chunk;
size_t half_blks_bytes_to_get = req_blk_num * req_blk_size_align;
size_t mem_pool_left = end_free - start_free;
//(1) mem_pool_left 夠 req_blk_num 個 blk -> 分配 req_blk_num 個
if (mem_pool_left >= half_blks_bytes_to_get)
{
chunk = start_free;
start_free += half_blks_bytes_to_get;
return chunk; // 遞歸出口
}
else if (mem_pool_left > req_blk_size_align)
{ //(2) 夠 n >=1 個 blk => 分配 n 個
req_blk_num = mem_pool_left / req_blk_size_align;
half_blks_bytes_to_get = req_blk_num * req_blk_size_align;
chunk = start_free;
start_free += half_blks_bytes_to_get;
return chunk; // 遞歸出口
}
else // (3) 不夠 1 個 blk: request from OS, molloc will allocate
{
//(4) mem_pool 余量 全 配給 適當 free_list[i]
if (mem_pool_left > 0)
{
// mem_pool 不足 1 個 req_blk:
// 必然有 剛好能 store 該 req_blk 的 某個 free_list
// 頭插法 insert into 該 free_list
obj* volatile* my_free_list
= free_list + freelist_index(mem_pool_left);
( (obj*)start_free )->next = *my_free_list;
*my_free_list = (obj*)start_free;
}
//(5) 向 OS 請求
size_t bytes_to_get = 2 * half_blks_bytes_to_get
+ ROUND_UP( heap_size>>4 );
start_free = (char*)malloc(bytes_to_get);
if (start_free == 0)
{ // heap memory 不足 -> malloc 失敗
// (6) 從 req_blk_size_align 相應 free_list[i] 下一 free_list 開始,
// 循環(huán)遍歷 后面 free_list[ j > i ]: 可能含 `unused larger 區(qū)塊`
// larger_blk 必為 req_blk_size_align 整數倍大小
// 若 有
// (7) 撥 1 個 mem_blk 放 mem_pool
// (8) 再 調 自身 chunk_alloc, 向 mem_pool 申請
obj* volatile * my_free_list, *p;
for(size_t size = req_blk_size_align;
size <= MAX_BYTES;
size+= ALIGN)
{
my_free_list
= free_list + freelist_index(mem_pool_left);
p = *my_free_list;
if(p)
{
//(7)
*my_free_list = p->next;
start_free = (char*)p;
end_free = start_free + size;
//(8)
return ( chunk_alloc(size, req_blk_num) );
}
}
//(9)
end_free = 0; // execute here => there are no memory anywhere
// 看 第 1級 allocator 的 out_of_memory 是否 有作用
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
}
//(10) update heap_size
heap_size += bytes_to_get;
//(11) update mem_pool tail
// head 在 前面已 modify
end_free = start_free + bytes_to_get;
//(12) 遞歸調自己, 以修正 req_blk_num
return chunk_alloc(req_blk_size_align, req_blk_num );
}
}
void __default_alloc::deallocate(void* p, size_t req_blk_size)
{
if (req_blk_size > (size_t)MAX_BYTES)
{
//(1) 調 第1級 allocator
malloc_alloc::deallocate(p, req_blk_size);
return;
}
obj* q = (obj*)p;
obj* volatile* my_free_list;
my_free_list = free_list
+ freelist_index(req_blk_size);
//(2) recycle the freed mem_blk to free-list
q->next = *my_free_list;
*my_free_list = q;
}
//------ 3. wrapper class template: simple_alloc
template<class T, class Alloc>
class simple_alloc
{
public:
static T*
allocate(size_t elem_num)
{
return 0 == elem_num ? 0 :
(T *) Alloc::allocate(elem_num * sizeof(T));
}
static void
deallocate(T* p, size_t elem_num)
{
if (elem_num != 0)
Alloc::deallocate(p, elem_num * sizeof(T));
}
};
// --- data
typedef struct data_32
{
char mem[32];
}Data_32;
int main()
{
typedef simple_alloc<Data_32, alloc> data_allocator;
Data_32* p1= data_allocator::allocate(1); // 32 Bytes
p1 = data_allocator::allocate(2); // 64 Bytes
p1 = data_allocator::allocate(3); // 96 Bytes
}
4. std::allocator 和 std::alloc 用法
std::vector<int, std::allocator<int> > vec;
// 容器 的 2 個 template para 綁定 在一起
std::vector<int, std::alloc > vec;
