GNUC alloc
簡介
- 前面自行設(shè)計(jì)的分配器, 在應(yīng)用方面有比較大的局限性, GCC的編譯器有一個(gè)比較全面的分配器, 原理就是上面的實(shí)現(xiàn), 只不過內(nèi)部做了更詳細(xì)的劃分
流程(先圖形, 后文字)
36.png
37.png
39.png
40.png
41.png
42.png
43.png
44.png
45.png
46.png
47.png
- <font color=red>流程說明</font>
alloc_1(第1張圖)是一個(gè)概述圖
重要的結(jié)構(gòu):
1. alloc有16條鏈(array[16])表來管理不同的區(qū)塊的大小
2. 每個(gè)區(qū)塊是8的倍數(shù)(8, 16, 24, .... , 128)
3. 內(nèi)部維護(hù)了一個(gè) pool, 作用是可分割的內(nèi)存
基本工作流程:
如果現(xiàn)在索取的內(nèi)存大小是len
0. 根據(jù)len找到是第idx鏈表表頭head
1. 如果head有值, 則直接將head指向的空間返回出去, head指向下一個(gè)
2. 第1步不成立, 則看pool
2.1 如果pool大小為0, 向 malloc要 chunk大小(chunk_mem), head指向chunk_mem
> 然后從chunk中取一半出來按len大小切割, 做成鏈表
> 返回鏈表的head給客戶, head指向下1個(gè)
> 剩下的一半被pool記錄
2.2 如果pool大小 > len
> 取一部分出來做成鏈表, head指向鏈表
> 返回head給客戶, head指向下一個(gè)(可能為空)
> 另一部分再被pool記錄
2.3 pool 有值但 < len
> 將當(dāng)前pool空間(大小是cache,一定是8的倍數(shù))掛到cache對應(yīng)的鏈表, 此時(shí)pool大小就為0了
> 然后重復(fù)2.1
ps:
在這個(gè)過程中,在2.3中的第1小步, 是對碎片的處理, 但沒有malloc失敗的情況處理
下面開始對上面的圖做更細(xì)致的解說
變量:
pool 大小
start_free 指向pool的起始
end_free 指向pool的結(jié)束
total 已經(jīng)向malloc申請的內(nèi)存
alloc_2:
申請32字節(jié)
1. 由#3負(fù)責(zé)的鏈表
2. #3為空, 并且pool為0, 所以pool向malloc索取:
32 * 20 * 2 + RoundUp(total >> 4)(1280byte)
3. 取出一半640, 為#3做成鏈表(切割成20份, 每份32字節(jié))
3.1 #3當(dāng)前指向的空間返回給客戶, #3指向下一個(gè)
4. 另一半被pool記錄(用start_free和end_free指向pool)
ps: total:1280, pool:640
alloc_3:
申請64字節(jié)
1. 由#7負(fù)責(zé)的鏈表
2. #7為空, 但pool有值(640)
3. pool有值, 但 < 20*64
3.1 pool最多可以被切割成64的10倍, 所以做成鏈表給#7
3.2 #7指向的空間返回給客戶, #7指向下一個(gè)
ps: total:1280, pool:0
alloc_4:
申請96字節(jié)
1. 由#11負(fù)責(zé)的鏈表
2. #11為空, 并且pool為空, 所以向malloc索取 96*20*2 + RoundUp(1280 >> 4)
3. 取出 96*20 的空間做成鏈表給#11
3.1 #11指向的空間給客戶
3.2 #11指向下一個(gè)
3.3 其余的用pool記錄
ps: total:5200, pool:2000
alloc_5:
申請88字節(jié)
1. 由#10負(fù)責(zé), #10為空, 但pool有值(2000)
2. pool可以為88切割成20份:
2.1 切割為20份給#10
2.2 #10返回給客戶, #10指向下一個(gè)
2.3 剩下的由pool記錄
ps: total:5200, pool:240
alloc_6:
申請3次88字節(jié), 這個(gè)時(shí)候直接從#10取
alloc_7:
申請8個(gè)字節(jié)
1. 由#0負(fù)責(zé), #0為空, 但pool有值
2. pool中的大小足夠切割為 8*20
2.1 切割成20份給#0
2.2 #0返回給客戶, #0指向下一個(gè)
2.3 剩余的由pool記錄
ps: total:5200, pool:80
alloc_8:
申請104字節(jié)
1. 由#12負(fù)責(zé), #12為空, 但pool有值
2. pool(80) < 104, 所以:
2.1 將pool中的80的空間掛到對應(yīng)的#9
2.2 向malloc索取 104*20*2 + RoundUp(5200>>4)
2.3 取出新獲得的內(nèi)存中104*20做成鏈表給#12
2.4 #12返回給客戶, #12指向下一個(gè)
2.5 其余的由pool記錄
ps: total:9688, pool:2408
alloc_9:
申請112字節(jié)
1. #13負(fù)責(zé), #13為空, 但pool有值
2. 取出pool中112*20大小的空間,做成鏈表給#13
2.1 #13返回給客戶, #13指向下一個(gè)
2.2 其余pool記錄
ps: total:9688, pool:168
alloc_10
申請48字節(jié)
1. 由#5負(fù)責(zé), #5為空, 但pool有值
2. pool最多加被切割成3*48,做成鏈表給#5
2.1 #5返回給客戶, #5指向下一個(gè)
2.2 其余pool記錄
ps: total:9688, pool:24
alloc_11:
申請72字節(jié)
1. 由#8負(fù)責(zé), #8為空, pool有值
2. pool(24) < 72, 所以:
2.1 將pool的24大小的空間做成鏈表, 并掛到對應(yīng)的#2中
2.2 向malloc索取(72*20*2 + roundUp(9688>>4))
由于測試最邊界, 所以設(shè)置了索取最大值為10000
2.3 malloc失敗, 于是從#8往后找, 發(fā)現(xiàn)#9(80字節(jié))鏈表有值:
> 從#9取出第1塊的80字節(jié)
> #9指向下一個(gè)
> 取出的80字最多能切割成 72*1, 切好后給#8
> #8返回客戶, #8指向下一個(gè)
> 剩余的由pool記錄
ps: total:9688, pool:8
后續(xù)的過程也是如此:
1.先看對應(yīng)的鏈表
2. 再看pool, 根據(jù)情況處理碎片, malloc成功時(shí)處理, malloc失敗處理等等
代碼實(shí)現(xiàn)分3步
第1步
將16條鏈表的表頭抽象成一個(gè)線程安全的類
它的主要作用:
1. 往外給head, head指向next
2. 接收一段內(nèi)存, 封裝成鏈表
ps:取值和封裝成鏈表的過程是線程安全的
第2步
將上面圖的pool抽取出來做成1個(gè)線程安全的類
第3步
實(shí)現(xiàn)內(nèi)存池的邏輯
代碼實(shí)現(xiàn)第1步(封裝鏈表)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<atomic>
#include<thread>
using namespace std;
namespace lb {
/*
常量
*/
enum class _constant_{
CHUNK = 20,
MAX = 128,
ALIGN_MIN = 8,
MIN = 8,
LIST_SIZE = 16,
_2 = 2
};
#define C_CHUNK ((int) (_constant_::CHUNK))
#define C_MAX ((int) (_constant_::MAX))
#define C_ALIGN_MIN ((unsigned) (_constant_::ALIGN_MIN))
#define C_MIN ((int) (_constant_::MIN))
#define C_LIST_SIZE ((int) (_constant_::LIST_SIZE))
#define C_2 ((int) (_constant_::_2))
template<size_t _Offset>
struct _list_ : public _list_<_Offset - 1> {
virtual _list_<_Offset>* operator++() {
return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) + _Offset);
}
virtual _list_<_Offset>* operator--() {
return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) - _Offset);
}
};
template<>
struct _list_<0-1> {
_list_<0>* next{};
};
constexpr size_t g_offset(size_t idx) {
return (idx + 1) * C_ALIGN_MIN;
}
template<size_t _Idx, typename _Flag> struct _list_thread;
template<> struct _list_thread<0-1,true_type> {
atomic<_list_<0>*> head{};
//析構(gòu)是空的, 不可以釋放內(nèi)存
~_list_thread() {}
};
//線程安全
template<size_t _Idx>
struct _list_thread<_Idx,true_type>: public _list_thread<_Idx-1,true_type>{
//不包含end
virtual void make_list(void* begin, void* end) {
#define _MAKE_LIST // 將給過來的內(nèi)存串成鏈表
_MAKE_LIST{
_list_<0>* record = reinterpret_cast<_list_<0>*>(begin);
for (; record != end;) {
/**
必須調(diào)用 placement new, 將void*的空間初始化為對應(yīng)的 _list_<_offset>
ps: 不能調(diào)用 _list_<0>的ctor, 因?yàn)?operator++ 是1個(gè)虛函數(shù), 這里的目的是生成對應(yīng)
的_list_<_offset>*, 而不同的_list_<_offset>的虛指針是不同的
*/
new(record)_list_<g_offset(_Idx)>;
record->next = this->head.load(memory_order_acquire);
while (!this->head.compare_exchange_weak(record->next, record, memory_order_acq_rel));
record = record->operator++();
}
}
#undef _MAKE_LIST
}
virtual void* get() {
while (this->head.load()){
auto result = this->head.load();
while (!this->head.compare_exchange_weak(result, result->next, memory_order_acq_rel));
return result;
}
}
};
}
void test_main_thread() {
lb::_list_thread<0, true_type>* p_a = new lb::_list_thread<0, true_type>;
lb::_list_thread<0, true_type>* p_b = new lb::_list_thread<1, true_type>;
auto mem = ::operator new(8 * 10);
auto end = ((char*)mem) + 80;
/**
單線程不同大小 head-list 測試
*/
p_a->make_list(mem, end);
p_b->make_list(mem, end);
}
void test_multi_thread() {
lb::_list_thread<0, true_type>* p_b = new lb::_list_thread<1, true_type>;
auto lambda_ = [&p_b] {
auto start = ::operator new(320);
auto ended = ((char*)start) + 320;
ostringstream buffer(std::ios_base::app);
buffer << "thread: " << this_thread::get_id();
buffer << endl;
buffer << " malloc: \n";
buffer << "{\n";
for (char* i = (char*)start; i != ended; i += 16)
buffer << "\t" << (void*)i << "\n";
buffer << "}\n\n";
cout << buffer.str();
p_b->make_list(start, ended);
};
thread t_a(lambda_);
thread t_b(lambda_);
thread t_c(lambda_);
thread t_d(lambda_);
thread t_e(lambda_);
t_a.join();
t_b.join();
t_c.join();
t_d.join();
t_e.join();
for (auto i = p_b->head.load(); i; i = i->next)
cout << "\t" << i << endl;
cout << "\n***************test_multi_thread_get\n";
auto mem_get = [&p_b]{
ostringstream buffer(std::ios_base::app);
while (1){
auto m = p_b->get();
buffer << "thread: " << this_thread::get_id();
buffer << " ";
buffer << "get memory: " << m << endl;
cout << buffer.str();
buffer.seekp(0);
if (m == nullptr)
break;
}
};
thread f(mem_get);
thread g(mem_get);
thread h(mem_get);
thread i(mem_get);
f.join();
g.join();
h.join();
i.join();
cout << "\n***************交叉測試\n";
{
thread t_a(lambda_);
thread t_b(lambda_);
thread t_c(mem_get);
thread t_d(mem_get);
thread t_e(lambda_);
thread t_f(lambda_);
thread t_g(mem_get);
thread t_h(lambda_);
thread t_i(mem_get);
t_a.join();
t_b.join();
t_c.join();
t_d.join();
t_e.join();
t_f.join();
t_g.join();
t_h.join();
t_i.join();
}
cout << "over\n";
}
int main(int arg, char** args) {
{
cout << "********_list_大小測試**********\n";
cout << sizeof(lb::_list_<8>) << endl;
cout << sizeof(lb::_list_<16>) << endl;
cout << sizeof(lb::_list_<24>) << endl;
cout << sizeof(lb::_list_<32>) << endl;
cout << sizeof(lb::_list_<40>) << endl;
cout << "\n\n********test_main_thread**********\n";
test_main_thread();
cout << "\n\n********test_multi_thread**********\n";
test_multi_thread();
}
return 0;
}
第2步和第3步(分文件)
48.png
/**
pool_constant.h
*/
#ifndef _POOL_CONSTANT_H
#define _POOL_CONSTANT_H
namespace lb {
namespace _pool {
/*
常量
*/
enum class _constant_ {
CHUNK = 20,
MAX = 128,
ALIGN_MIN = 8,
MIN = 8,
LIST_SIZE = 16,
_2 = 2
};
#define C_CHUNK ((int) (_constant_::CHUNK))
#define C_MAX ((int) (_constant_::MAX))
#define C_ALIGN_MIN ((unsigned) (_constant_::ALIGN_MIN))
#define C_MIN ((int) (_constant_::MIN))
#define C_LIST_SIZE ((int) (_constant_::LIST_SIZE))
#define C_2 ((int) (_constant_::_2))
#define ALLOC_NO_MEMORY -1
}
}
#endif
/**
pool_func.h
*/
#ifndef _POOL_FUNC_H
#define _POOL_FUNC_H
#include"pool_constant.h"
namespace lb {
namespace _pool {
using namespace std;
inline constexpr size_t g_offset(size_t idx) {
return (idx + 1) * C_ALIGN_MIN;
}
size_t round_up(size_t len);
size_t getidx(size_t unit);
}
}
#endif // !_POOL_FUNC_H
/**
pool_func.cpp
*/
#include"pool_func.h"
namespace lb {
namespace _pool {
/**
上調(diào)為8的倍數(shù), 其實(shí)原理很簡單:
一個(gè)數(shù)N
當(dāng)N + 7的后, 結(jié)果(result)一定是 >= 8的
而在計(jì)算機(jī)中, 8的倍數(shù)的數(shù)字, 則一定是以 0b xxxx 000(3個(gè)0結(jié)尾的)
所以result想再調(diào)整為8的倍數(shù), 則result的第0,1,2的bit位應(yīng)該設(shè)置為0
但result的其他位不可以變, 則需要取一個(gè) 掩碼(0b1111 1111 1111 1111 1111 1111 1111 1000)
與result做&操作, 而掩碼的值其實(shí)就是 ~7
同理調(diào)整為16的倍數(shù), 也是一樣的道理
*/
size_t round_up(size_t len) {
return (len + C_ALIGN_MIN - 1) & ~(C_ALIGN_MIN - 1);
}
size_t getidx(size_t unit) {
return unit / C_ALIGN_MIN - 1;
}
}
}
/**
pool_head.hpp
16條鏈表的表頭對象
*/
#ifndef _POOL_HEAD_HPP
#define _POOL_HEAD_HPP
#include<atomic>
namespace lb {namespace _pool {
using namespace std;
template<size_t _Offset>struct _list_ : public _list_<_Offset - 1> {
virtual _list_<_Offset>* operator++() {
return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) + _Offset);
}
virtual _list_<_Offset>* operator--() {
return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) - _Offset);
}
};
template<>struct _list_<0 - 1> {
_list_<0>* next{};
};
template<size_t _Idx, typename _Flag> struct _list_thread;
template<> struct _list_thread<-1, true_type> {
atomic<_list_<0>*> head{};
~_list_thread() {}
};
//線程安全
template<size_t _Idx>
struct _list_thread<_Idx, true_type> : public _list_thread<_Idx - 1, true_type> {
//不包含end
virtual void make_list(void* begin, void* end) {
_list_<0>* record = reinterpret_cast<_list_<0>*>(begin);
for (; record != end;) {
new(record)_list_<g_offset(_Idx)>;
record->next = this->head.load(memory_order_acquire);
while (!this->head.compare_exchange_weak(record->next, record, memory_order_acq_rel));
record = record->operator++();
}
}
virtual void* get() {
while (this->head.load()) {
auto result = this->head.load();
while (!this->head.compare_exchange_weak(result, result->next, memory_order_acq_rel));
return result;
}
}
};
}}
#endif // !_POOL_HEAD_HPP
/**
cache.h 負(fù)責(zé)緩存的類
它不能回收外界的內(nèi)存(由safe_pool回收), 因?yàn)閏ache的記錄的內(nèi)存必須是連續(xù)的
而外界傳過來的地址可能和當(dāng)前cache中記錄的地址的邊界不是相鄰的
*/
#ifndef _POOL_CACHE_H
#define _POOL_CACHE_H
#include<thread>
#include<sstream>
#include<iostream>
#include"pool_constant.h"
#include"pool_func.h"
#include"pool_head.hpp"
namespace lb {namespace _pool {
using namespace std;
class cache{
public:
void get(size_t unit, void** head_start = nullptr, void** head_ended = nullptr);
public:
static size_t total;
//start和ended的之間的內(nèi)存必須是連續(xù)的
static atomic<void*> start;
static size_t byte;
};
}}
#endif // !_POOL_CACHE_H
/**
cache.cpp
*/
#include "cache.h"
#define _TEST_
namespace lb { namespace _pool {
size_t cache::total{};
size_t cache::byte{};
atomic<void*> cache::start{};
void cache::get(size_t unit, void** head_start, void** head_ended) {
//start指向空, 表示沒有cache
if (!start.load(memory_order_acquire)) {
static atomic<bool> alloc_flag{};
//this_thread::sleep_for()
// 這里想malloc, 雖然是多線程, 但start此時(shí)已經(jīng)指向空, 其他線程不可能在其他地方同時(shí)調(diào)整start這塊內(nèi)存
/// 但可能有多個(gè)線程來這里malloc, 只允許同一時(shí)間內(nèi)只有1個(gè)線程在malloc
while (true) {
if (alloc_flag.exchange(true, memory_order_acq_rel)) {
this_thread::yield();
continue;
}
// 后面進(jìn)來的線程判斷有沒有cache
if (start.load(memory_order_acquire)) {
alloc_flag.store(false, memory_order_release);
break;
}
size_t half = unit * C_CHUNK;
size_t count = half * C_2 + round_up(total >> 3);
void* malloc_mem = malloc(count);
#ifdef _TEST_
//測試malloc失敗的情況
if (count > 3600) {
if (malloc_mem) {
free(malloc_mem);
malloc_mem = nullptr;
}
}
#endif // _TEST_
if (malloc_mem) {
char* cache_start = (char*)malloc_mem + half;
total += count;
byte = count - half;
start.store(cache_start, memory_order_release);
alloc_flag.store(false, memory_order_release);
*head_start = malloc_mem;
*head_ended = cache_start;
#ifdef _TEST_
ostringstream str(ios_base::app);
str << "malloc {\n";
static int __count = 0;
for (char* i = (char*)malloc_mem, *end = i + count; i != end; ++i) {
++__count;
}
str << "\t" << __count << endl;
str << "}";
cout << str.str();
#endif // _TEST_
return;
}
/// malloc失敗, pool應(yīng)該到header中的head去找內(nèi)存
alloc_flag.store(false, memory_order_release);
*head_start = *head_ended = nullptr;
return;
}
return get(unit, head_start, head_ended);
}
static atomic<bool> block_flag{};
while (true) {
if (block_flag.exchange(true, memory_order_acq_rel)) {
this_thread::yield();
continue;
}
if (byte == 0) {
*head_start = nullptr;
*head_ended = nullptr;
block_flag.store(false, memory_order_release);
//再去malloc
return get(unit, head_start, head_ended);
}
//cache不夠, 應(yīng)該將內(nèi)存給pool, 掛到對應(yīng)的鏈表中
if (byte < unit) {
void* val = start;
*head_start = val;
*head_ended = (char*)val + byte;
byte = 0;
start = nullptr;
}
else {
//cache足夠, 劃出最多20塊的空間給外界的pool去處理
void* val = start;
*head_start = val;
size_t block = byte / unit;
*head_ended = (char*)val + (block > C_CHUNK ? (C_CHUNK * unit) : (block * unit));
byte -= ((char*)*head_ended - *head_start);
if (byte)
start = *head_ended;
else
start = 0;
}
block_flag.store(false, memory_order_release);
break;
}
}
}}
/**
pool.hpp
提供給外界用的類
*/
#ifndef _POOL_HPP
#define _POOL_HPP
#include"cache.h"
#define _TEST_
namespace lb {
namespace _pool {
using namespace std;
template<typename _Bool_type>class pool {};
class safe_pool : public pool<true_type> {
private:
using Header = _list_thread<0, true_type>;
using Header_p = add_pointer<Header>::type;
using Header_pp = add_pointer<Header_p>::type;
public:
void* alloc(size_t len) {
if (len > C_MAX)
return ::operator new(len);
size_t unit = round_up(len);
size_t idx = getidx(unit);
auto tar_head = header[idx];
auto result = tar_head->get();
// 從鏈表中取到(線程安全)內(nèi)存, 就直接返回
if (result) return result;
void* head_start = nullptr;
void* head_ended = nullptr;
memory.get(unit, &head_start, &head_ended);
size_t get_mem = (char*)head_ended - head_start;
// malloc失敗, 以當(dāng)前表頭(head)為準(zhǔn), 依次往后面的head中找內(nèi)存
if (!head_start) {
for (size_t i = idx, end = C_LIST_SIZE; ++i < end; ) {
auto next_head = header[i];
auto need = next_head->get();
// 找到了, 先拿unit的大小出來給外界, 余下的掛載到對應(yīng)序號的表頭上
if (need) {
auto other_head_start = (char*)need + unit;
auto other_head_ended = (char*)need + ((i+1)*C_ALIGN_MIN);
header[(getidx(other_head_ended-other_head_start))]->make_list(other_head_start, other_head_ended);
return need;
}
}
// 沒有找到, 拋異常
//throw ALLOC_NO_MEMORY;
return 0;
}else {
// 內(nèi)存不足夠, 先掛載到對應(yīng)序號的鏈表中(get_mem一定是某個(gè)表頭需要的大小), 再要內(nèi)存
if (get_mem < unit) {
header[getidx(get_mem)]->make_list(head_start, head_ended);
head_start = head_ended = nullptr;
memory.get(unit, &head_start, &head_ended);
//內(nèi)存足夠(unit的整數(shù)倍), 先掛載到自己的鏈表上
}else {
tar_head->make_list(head_start, head_ended);
head_start = head_ended = nullptr;
}
}
return tar_head->get();
}
void dealloc(void* ptr, size_t len) {
if (len > C_MAX) return ::operator delete(ptr);
if (ptr == nullptr)
return;
// 只能掛到對應(yīng)序號的鏈表上, 不能回收到cache中
size_t unit = round_up(len);
header[getidx(unit)]->make_list(ptr, (char*)ptr + unit);
}
void print() {
size_t count = 0;
for (size_t i = 0; i < C_LIST_SIZE; ++i) {
auto head = header[i];
for (auto i = head->head.load(); i; i = i->next)
count++;
}
cout << count << endl;
cout << memory.byte << endl;
cout << memory.total << endl;
}
#ifdef _TEST_
void test() {
auto mem = malloc(128);
this->header[C_LIST_SIZE - 1]->make_list(mem, (char*)mem + 128);
}
#endif // _TEST_
private:
template<size_t _idx>
static constexpr void initialize_header(Header_pp header) {
static _list_thread<_idx, true_type> head;
header[_idx] = static_cast<Header_p>(&head);
initialize_header<_idx - 1>(header);
}
template<>
static void initialize_header<0>(Header_pp header) {
static _list_thread<0, true_type> head;
header[0] = static_cast<Header_p>(&head);
}
template<size_t _count>
static constexpr Header_pp initialize_header() {
static Header_p header[_count];
initialize_header<_count - 1>(static_cast<Header_pp>(header));
return static_cast<Header_pp>(header);
}
private:
static cache memory;
static Header_pp header;
};
cache safe_pool::memory;
safe_pool::Header_pp safe_pool::header = safe_pool::initialize_header<C_LIST_SIZE>();
}
}
#endif // !_POOL_HPP
/**
main測試
*/
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<thread>
#include<future>
#include"pool.hpp"
void test_safe_pool_get() {
_pool::safe_pool tmp;
auto lambda = [&tmp](int size) {
ostringstream ostr(ios_base::app);
ostr << "\n\nthread: " << this_thread::get_id();
ostr << "\n\talloc(" << size << ") address: " << tmp.alloc(size) << "\n\n";
cout << ostr.str();
};
thread t_a(lambda, 6);
thread t_b(lambda, 72);
thread t_c(lambda, 16);
thread t_d(lambda, 30);
thread t_e(lambda, 128);
thread t_f(lambda, 13);
thread t_g(lambda, 8);
thread t_h(lambda, 8);
thread t_i(lambda, 24);
t_a.join();
t_b.join();
t_c.join();
t_d.join();
t_e.join();
t_f.join();
t_g.join();
t_h.join();
t_i.join();
tmp.print();
}
void test_safe_pool_new_delete(){
_pool::safe_pool tmp;
auto get_mem = [&tmp](int size) -> void*{
auto result = tmp.alloc(size);
printf("thread: %u\n\tget mem: %p size: %d\n",this_thread::get_id(), result,size);
return result;
};
auto del_mem =? [&tmp](future<void*>& f, size_t len) {
auto del = f.get();
printf("thread: %u\n\tdel mem: %p size: %d\n",this_thread::get_id(), del, len);
return tmp.dealloc(del, len);
};
/**
這里測試的時(shí)候, 1個(gè)task只能對應(yīng)1個(gè)thread, 如果想測試更多的線程, 則只有將循環(huán)的次數(shù)增大
*/
for (int i = -1; ++i < 10;) {
packaged_task<void* (int)> task(get_mem);
auto f = task.get_future();
srand(std::chrono::system_clock::to_time_t(std::chrono::system_clock::now()));
int n = rand() % 129;
thread t_get(std::ref(task), n);
thread t_del(del_mem,std::ref(f), n);
this_thread::sleep_for(chrono::milliseconds(100));
t_get.join();
t_del.join();
}
tmp.print();
}
int main(int arg, char** args) {
cout << "內(nèi)存池的安全獲取測試\n";
//test_safe_pool_get();
cout << "內(nèi)存池的交叉(獲取和歸還)測試\n";
test_safe_pool_new_delete();
return 0;
}
malloc
介紹
- 它是1個(gè)獨(dú)立的算法, 由于內(nèi)存在本質(zhì)上是由os管理的資源, 所以內(nèi)存事實(shí)上是由os來管理的
- os實(shí)現(xiàn)內(nèi)存的管理也借助了malloc(==在VC6以后win最明顯==), 但malloc作為跨平臺的一個(gè)c語言的算法, 是不可能依賴os的, 所以在linux中, 也有自己的malloc實(shí)現(xiàn), 也就是說各個(gè)平臺基于malloc都有自己的擴(kuò)展, 但大致來說, 實(shí)現(xiàn)的原理差不多
- malloc屬于crt[1]的一部分, 下面在MSVC(==2019==)中調(diào)試一下
CRT
- main函數(shù)啟動(dòng)前, 程序的初始化
49.png
50.png
51.png
52.png
第0張圖:
運(yùn)行可執(zhí)行文件時(shí)的調(diào)用棧(CRT)
第1張圖:
運(yùn)行可執(zhí)行文件時(shí), 內(nèi)核開始調(diào)用CRT代碼的第1步
一直到第3張, 開始CRT的初始化, 但已經(jīng)看不到源碼了
ps: 其中第2張圖的后續(xù), 會調(diào)用到 main函數(shù), 這里沒有截出來
sbh
- small block heap
ps: 前面實(shí)現(xiàn)的內(nèi)存管理(==alloc==), 是基于區(qū)塊的管理(8~128字節(jié)), 同樣的這里的small block heap也是基于小區(qū)塊(==1024==以下)
VC6的調(diào)用棧
_heap_init() _1
__sbh_heap_init(...) _2
_ioinit() _3
_malloc_dbg(...) _4
_nh_malloc_dbg(...) _5
_heap_alloc_dbg(...) _6
__sbh_alloc_block(...) _7
__sbh_alloc_new_region() _8
__sbh_alloc_new_group(...) _9
GetCommandLineA() _10
__crtGetEnvironmentStringsA() _11
_setargv()
_setenvp()
_cint()
_initterm(,,)
__initstdio()
_initterm(,,)
mian()
exit(code)
...
_heap_init
int __cdecl _heap_init( int mtflag){
if (_crtheap != 4096 [向window索取 4096 字節(jié)的空間])
失敗直接返回
if(__sbh_heap_init() == 0){
釋放_crtheap的空間
}
return 1;
/**
_crtheap是CRT提個(gè)的全局變量
后面再要內(nèi)存的時(shí)候可以從 _crtheap開始的內(nèi)存(共4096)處取內(nèi)存
*/
}
__crt_heap_init
int __cdecl __sbh_heap_init(void){
if (!(__sbh_pHeadList = 16個(gè)HEADER大小的空間))
失敗直接返回
__sbh_pHeaderDefer = NULL;
//sbh手上始終有一個(gè)區(qū)塊, 就是用這個(gè)來記錄的, 當(dāng)free的動(dòng)作造成1個(gè)區(qū)塊的完整合并
// 如果這個(gè)值不為空, 則會將合并后的塊還給os, 如果為空, 則會記錄剛合并好的塊
...
/**
這個(gè)函數(shù)是用來索取 16個(gè) HEADER大小的空間(從_crtheap中拿),
很像前面的alloc的管理機(jī)制(內(nèi)存管理在某些方面是相通的)
HEADER的結(jié)構(gòu)
*/
}
- <font color=red>HEADER的結(jié)構(gòu)</font>
typedef unsigned int BITVEC;
typedef struct tagHeader{
BITVEC bitvEntryHi;
BITVEC bitvEntryLo;
BITVEC bitvCommit;
void* pHeapData;
struct tagRegin* pRegion;
} HEADER, *PHEADER;
/**
Hi和Lo構(gòu)成了64個(gè)bit
pHeapData指向的是1MB的空間起始地址, 但每次要內(nèi)存是32kb
pRegion是用來高效管理1MB內(nèi)存, 后面說
*/
-
HEADER的圖
53.png
所以程序第1塊內(nèi)存是_crtheap(4096), 但malloc(sbh)還沒出場,因?yàn)?第0個(gè)HEADER中的 pHeapData還指向空(沒有內(nèi)存)
接下來是 crt自己需要內(nèi)存時(shí), 發(fā)現(xiàn)sbh為0, 則就要開始sbh的初始化
即 為第0個(gè)HEADER中的pHeapData分配1MB(虛空間), 并創(chuàng)建這1MB的管理(pRegion)
ps:pHeapData指向的是1MB,并且地址是連續(xù)的, 但管理這1MB的機(jī)制是分段
每次管理32kb(由pPegion的結(jié)構(gòu)決定)
_ioinit
/**
前面的2步, 已經(jīng)初始化好了第0個(gè)HEADER(但沒有內(nèi)存(pHeapData為空))
這一步就是CRT自己malloc第1塊內(nèi)存(前面的4096就不算了)
用來為io準(zhǔn)備的
*/
void __cdecl _ioinit(void){
...
if((pio = _malloc_crt(IOINFO_ARRAY_ELTS * sizeof(ioinfo))) == 0)
...
}
/**
其中 _malloc_crt是一個(gè)macro, 在debug環(huán)境下會附帶內(nèi)存相關(guān)的信息
#define _FREE_BLOCK 0
#define _NORMAL_BLOCK 1
#define _CRT_BLOCK 2
#define _IGNORE_BLOCK 3
#define _CLIENT_BLOCK 4
#define _MAX_BLOCKS 5
#ifndef _DEBUG
#define _malloc_crt malloc
#else
#define _THISFILE _FILE_
#define _malloc_crt(s) _malloc_dbg(s, _CRT_BLOCK, _THISFILE, __LINE__)
..
#endif
所以當(dāng)在debug環(huán)境下, _malloc_crt會對內(nèi)存附加:
1. 當(dāng)前哪個(gè)文件申請的內(nèi)存
2. 哪1行申請的內(nèi)存
3. 是誰申請的(_CRT_BLOCK(crt自己) 還是 _NORMAL_BLOCK(其他人))
ps: 這些值會在后面的 _heap_alloc_dbg中添加上
IOINFO_ARRAY_ELTS長度是32字節(jié)
ioinfo是8字節(jié)
typedef strcut{
long osfhnd;
char osfile;
char pipech;
} ioinfo;
所以crt的第1塊內(nèi)存是256字節(jié)(100H)
*/
_heap_alloc_dbg(==跳過了不相關(guān)的函數(shù)==)
...
// nSize是前面?zhèn)鬟f來的256字節(jié)
blockSize = sizeof(_CrtMemBlockHeader) + nSize + nNoMandsLandSize; //_code_a
..
//向sbh要內(nèi)存
pHead = (_CrtMemBlockHeader*)_heap_alloc_base(blockSize);
//_code_b
if(_pFirstBlock)
_pFirstBlock->pBlockHeaderPrev = pHead;
esle
_pLastBlock = pHead;
//對分配好的內(nèi)存填充數(shù)據(jù)
pHead->pBlockHeaderPrev = NULL;
pHead->pBlockHeaderNext = _pFirstBlock->pBlockHeaderNext;
... 后面是文件, 行號, 等信息的賦值
_pFirstBlock = pHead;
//_code_c
memset(pHead->gap, _bnoMansLandFill, nNoMansLandSize); //_code_c_a
memset(pbData(pHead), _bnoMansLandFill, nNoMansLandSize); //_code_c_b
memset(pbData(pHead), _bCleanLandFill, nsize); //_code_c_c
return pbData(pHead);
54.png
/**
_code_a是對傳遞來的256字節(jié)做附加(debug調(diào)試需要的信息)
#define nNoMandsLandSize 4
typedef struct _CrtMemBlockHeader{
struct _CrtMemBlockHeader* pBlockHeaderNext;
struct _CrtMemBlockHeader* pBlockHeaderPrev;
char* sZFileName; //文件路徑和名
int nLine; //行號
size_t nDataSize; //要用戶需要的內(nèi)存大小
int nBlockUse; //是crt在申請, 還是其他人在申請
long lRequest; //流水號
unsigned char gap[nNoMandsLandSize];//4個(gè)字節(jié)的 uchar
} _CrtMemBlockHeader; 如上圖
也就是說1塊malloc的內(nèi)存給出后(debug), 會被crt記載:
1. 指向下一個(gè)malloc的內(nèi)存
2. 指向上一個(gè)malloc的內(nèi)存
3. 當(dāng)前這塊內(nèi)存是由哪個(gè)文件發(fā)出的
4. 由哪一行發(fā)出的
5. 申請的多大
6. 由誰(crt或用戶)申請的
7. 第幾次申請(流水號)
8. 由gap來隔離userdata(如圖中的gap)
9. 用戶的數(shù)據(jù)
10.gap
ps: gap的作用是用戶數(shù)據(jù)的上下柵欄,后面在分配好內(nèi)存后會被填上 0xfd
_code_b 是說分配出來的 pHead插入到當(dāng)前_pFirstBlock前
如果_pFirstBlock 沒有值, 則記錄_pLastBlock為pHead
ps: _pFirstBlock和_pLastBlock是全局的2個(gè)變量(_CrtMemBlockHeader*), 也就是說所有的malloc出來的內(nèi)存都會被串到雙向鏈表中
_code_c 是將分配出來的內(nèi)存在 柵欄(gap)和用戶的數(shù)據(jù)區(qū)填充上值
static uchar _bNoMansLandFill = 0xFD;
static uchar _bDeadLandFill = 0xDD;
static uchar _bClearLandFill = 0xCD;
所以用戶得到的內(nèi)存pbData(pHead)的空間中填充的是0xCD, 所以在很多次
斷點(diǎn)調(diào)試中, 如果用1個(gè)char*去接收malloc時(shí), 會發(fā)現(xiàn)得到內(nèi)存中的內(nèi)容是屯
測試如下圖:
*/
55.png
ps: 上面只是在 <font color=red>調(diào)整最初的256字節(jié)(==100H==)的debug-header</font>, 真正分配內(nèi)存的是==_heap_alloc_base==函數(shù)(<font color=#800080>上面的代碼也調(diào)用了</font>), 在探究_heap_alloc_base前, 先給出一張malloc內(nèi)存的鏈表圖
56.png
每1塊內(nèi)存的2端, 是記錄malloc出去的內(nèi)存大小, 一定是16的倍數(shù), 借用第0個(gè)bit, 如果是1表示已經(jīng)借出去, 如果為0表示free還回來, ==packed==是在 <font color=red>debug后的空間的基礎(chǔ)上, 上調(diào)為16倍數(shù)需要擴(kuò)展的內(nèi)存</font>, ==mem_b, mem_c==沒有畫出其他部分的數(shù)據(jù), 懶的畫了, 可以發(fā)現(xiàn)新的malloc內(nèi)存是從==_pFirstBlock==位置插入的
heap_alloc_base
...
/**
前面函數(shù)將最初的256字節(jié)附加debug后(size),此時(shí)還沒調(diào)整為16的倍數(shù)
如果size < 1016, 則由sbh(即malloc)來分配
這里的1016是沒有加上 malloc區(qū)塊在大小(8字節(jié), 上下各1個(gè)),也就是說用戶需要的
內(nèi)存在附加debug-header后, 大于1kb, 則交給os處理
否則在當(dāng)前函數(shù)中將size調(diào)整為16的倍數(shù), 交給window給出內(nèi)存
ps: 其實(shí)os分配時(shí)可能不是16的倍數(shù), 但sbh自己會調(diào)整為16的倍數(shù)
*/
if(size <= __sbh_threshold){
pvReturn = __sbh_alloc_block(size);
if(pvReturn) return pvReturn
}
if(size == 0)
size = 1;
size = (size + 0xf) &~ (0xf); //上調(diào)為16的倍數(shù)
return HeapAlloc(_crtheap,0,size);
...
__sbh_alloc_block
- 將上面的size調(diào)整為16的倍數(shù)
- 計(jì)算最初的==256==的malloc大小
size_t mem = 256 + sizeof(_CrtMemBlockHeader)(36) + 2*(sizeof(int));
mem再上調(diào) 為16的倍數(shù)
ps: 由于是32的操作系統(tǒng), 所以上下2端的空間大小用int表示,可以存儲所有內(nèi)存(4GB[2^32])
__sbh_alloc_new_xxx
57.png
- 后面就是以圖的方式來解說 <font color=red>__sbh_alloc_new_region 和 _sbh_alloc_new_group</font>
前面所有的工作:
1. ioinit發(fā)出256字節(jié)的內(nèi)存
2. 附加debug所需的大小
3. 調(diào)整為16的倍數(shù)
已經(jīng)準(zhǔn)備完成, 但由于是向sbh要第1塊內(nèi)存, HEADER[0]中的pHeapData還是空, 所以接下來就是真正的初始化sbh
如上圖, 先在HEADER[0]中向os索取1MB內(nèi)存, 但只是登記,取32kb出來, 其余的給sbh留著
獲取到32kb后, HEADER[0]中的pRegion就接著初始化
region的相關(guān)結(jié)構(gòu)如下
struct REGION{
int indGroupUse;
char cntRegionSize[64];
BITVEC bitvGroupHi[32];
BITVEC bitvGroupLo[32]; //uint
struct tagGroup grpHeadList[32];
};
struct tagGroup{
int cntEntries;
struct tagListHead listHead[64];
};
struct tagListHead{
struct tagEntry* pEntryNext;
struct tagEntry* pEntryPrev;
};
/**
將這些結(jié)構(gòu)作成如上的圖
*/
總的來說就是1個(gè)HEADER管理1MB的內(nèi)存
每個(gè)HEADER通過 32個(gè)組(group)來管理1MB
所以每個(gè)組就管理32kb, 而group中又通過 64對雙向鏈表來管理這個(gè)組的32kb
group的64對鏈表的概念就是前面內(nèi)存池16條鏈表對應(yīng)的概念
第0條管理16字節(jié)
第1條管理32字節(jié)
...
最后1條鏈表是特殊的, 管理1kb(1024byte)以上的內(nèi)存
而group管理自己的32kb也是分段管理, 將32kb分成8段, 每段4kb(4096)
如下圖:
58.png
如上圖, 每個(gè)group將32kb分為8個(gè)page, 每個(gè)page為4kb
每個(gè)page可以看成1個(gè)沒有debug空間的malloc塊
如上圖:
每個(gè)塊4096, 看成malloc塊后 > 1024, 所以掛載在group中的第63號鏈表上
在這個(gè)塊中, 預(yù)設(shè)有:
1. 底部的0xFFFFFFFF
2. 頂部的0xFFFFFFFF
非預(yù)設(shè)但填值:
1. 底部記錄當(dāng)前malloc的區(qū)塊
2. 頂部記錄當(dāng)前malloc的區(qū)塊
3. 一個(gè)Entry*next, Entry* prev
struct Entry{
int size;
Entry* next;
Entry* prev;
};
typedef struct Entry tagEntry;
其中第1和第2是柵欄, 用來隔開數(shù)據(jù), 因?yàn)?1MB有32個(gè)32kb, 32kb中有8個(gè)4kb, 所以
1Mb有256個(gè)4kb(page), 這些page都是相連的, 所是要用上下2個(gè)0xFFFFFFFF隔開
但被視為malloc的4kb必須為16的倍數(shù), 因?yàn)榈?,2已經(jīng)消耗了8個(gè)字節(jié), 所以剩下4096-8 = 4088
調(diào)整為16的倍數(shù)就是4080
外界獲取內(nèi)存(mem)時(shí):
sbh先看當(dāng)前應(yīng)該到哪個(gè)HEADER[n]中
哪個(gè)group中
哪個(gè)鏈表
由于ioinit發(fā)出的是256字節(jié), 并且sbh發(fā)現(xiàn)是第1次, HEADER[0]的pHeadData為空
所以向os要了1MB的虛擬空間, 然后初始化sbh環(huán)境(真正取32kb)
然后創(chuàng)建region, 發(fā)現(xiàn)256(debug+調(diào)整后大小是130H), 應(yīng)該到18號鏈表中找
但18沒有, 然后就像alloc中一樣, 從18往后找, 然后在第63號中發(fā)現(xiàn)有內(nèi)存
于是從63號鏈表中next找到鏈表切割
額外說明:
前面的region中的group中, 有64對雙向鏈表, 它們的類型是Entry*
group的結(jié)構(gòu)(上上張圖)發(fā)現(xiàn)在初始化的時(shí)候:
每一對鏈表(next,prev)中的next指向上一個(gè)prev, 而prev和next指的是同一個(gè)地址
Entry的結(jié)構(gòu)是(int, Entry* next, Entry* prev)
也就是說形成了一個(gè)雙向循環(huán)鏈表, 比如上面的圖, sbh初始化后
32kb的空間掛載到了第63號鏈表中:
第63號鏈表的next指向了32kb的第0個(gè)page可用地址
32kb的8個(gè)page之間是雙向相連的
32kb的第7個(gè)page的next指向了第62號鏈表的prev,這樣解釋第7個(gè)page的next指針時(shí), 62號鏈表的prev就會被當(dāng)作int,而緊接著prev后的就是第63號鏈表的next(指向了第0個(gè)page的next)
第63號的prev又指向了第7個(gè)page的next, 這樣就形成了雙向循環(huán)鏈表
總結(jié)就是 group中的每1對鏈表在初始化后, 會指向上一個(gè)鏈表的prev,目的是借用一個(gè)int(在32位中int和void*大小相等)形成雙向循環(huán)鏈表, 這也是實(shí)現(xiàn)上的一個(gè)技巧
ps: HEADER中那些bit位以及region中的bit位, 就是用來快速定位, 提高效率
下面開始細(xì)說,內(nèi)存是怎么切割的
sbh的第1塊內(nèi)存(==vc6==)
59.png
ioinit第1塊內(nèi)存, 會從第63號鏈表中切割出130H, 并由_pFirstBloc和_pLastBlock記載
切割后的內(nèi)存被標(biāo)記為131, 最后1個(gè)bit置1是借出去
然后剩余EC0H, 大于1024, 所以繼續(xù)掛載在第63號鏈表中
并且region中的計(jì)數(shù)器cntEntries +1
sbh的第2塊內(nèi)存
60.png
和前面一樣, 先到對應(yīng)的鏈表中有沒有, 沒有一直找到后面有內(nèi)存的鏈表
注意指針的拉動(dòng)
在給內(nèi)存的過程中, 如果發(fā)現(xiàn)剩余的內(nèi)存不夠1kb, 就會掛到對應(yīng)的鏈表中
后續(xù)的就不再給圖了
free
- free的動(dòng)作就是將客戶的內(nèi)存定位到:
- HEADER[N]
- group[N]
- list[N]
- 然后定位到malloc的上區(qū)塊, 將最后1個(gè)bit位的1改為0
- 將對應(yīng)的內(nèi)存掛載到對應(yīng)的鏈表, 調(diào)整相關(guān)的指針
- 修改region的計(jì)數(shù)器-1
ps: 需要說明的是, malloc查詢N號鏈表內(nèi)存的流程和前面的alloc一樣, 只是實(shí)現(xiàn)方式不同
合并
- free的過程也會試著合并, 因?yàn)橛猩舷聟^(qū)塊的大小, 所以從理論上合并完全沒有問題
- 當(dāng)region的計(jì)數(shù)器為0時(shí), 表示32kb的內(nèi)存完全合并, 這個(gè)時(shí)候就會考慮是否還給os
要看__sbh_pHeaderDefer是有值, 如果有則會將剛完全合并的內(nèi)存還給os, 如果沒有, 則會將合并好的內(nèi)存指給__sbh_pHeaderDefer
release下的malloc
- 只記錄上下2個(gè)malloc塊大小(當(dāng)然還是16的倍數(shù)所以可能會有填充)
- malloc的實(shí)現(xiàn)遠(yuǎn)遠(yuǎn)不只這么多, 但流程基本就這樣, 像malloc可能還要查找內(nèi)存對齊等等, 都有自己高效的算法
VS2019簡單測試
int main(int arg, char** args) {
constexpr size_t s = sizeof(long);
char* tmp_a = (char*)malloc(5);
/**
測試(32位, VS2019, debug)
*/
// 用戶得到的內(nèi)存的上面4個(gè)字節(jié)(gap籬笆),(已經(jīng)不是0xfdfdfdfd了, 而是0xfffffffd)
cout << std::hex << (unsigned int)*(tmp_a - 4) << endl;
// 用戶得到的內(nèi)存的下面4個(gè)字節(jié), 和上面的結(jié)果一樣
cout << std::hex << (unsigned int)*(tmp_a + 5) << endl;
//流水號, 這個(gè)其實(shí)之前解釋的也不是很清楚, 不要管這個(gè)
cout << std::hex << (unsigned int)*(tmp_a - 8) << endl;
//這里想測試是crt申請的內(nèi)存還是用戶的, 但發(fā)現(xiàn)打印的是用戶申請的內(nèi)存大小
//用戶申請的內(nèi)存大小(這里是5, 如果上面改成malloc(11), 則這里打印就是11)
cout << std::hex << (unsigned int)*(tmp_a - 12) << endl;
//這里想打印malloc中的行號, 但發(fā)現(xiàn)打印的是1, 根據(jù)前面的分析, 這個(gè)1可能就是標(biāo)記
/// 這塊內(nèi)存是crt(2)申請的還是用戶(1)申請的, 所以代表此內(nèi)存是用戶申請的
cout << std::hex << (unsigned int)*(tmp_a - 16) << endl;
//后面找不到行號和文件, 看來現(xiàn)在的vc在實(shí)現(xiàn)方面已經(jīng)和以前有所不同了
cout << std::hex << (char*)&*(tmp_a - 28);
}
內(nèi)存泄露的正確概念
- 通過前面的 <font color=red>malloc塊的結(jié)構(gòu)</font>, 可以總結(jié)出:
- 只有當(dāng) <font color=red>main函數(shù)結(jié)束前</font>, 在 <font color=red>malloc給出的內(nèi)存鏈表中</font>, 那些 <font color=red>在debug模式下, 如果鏈表中還存在標(biāo)記為1的(用戶申請的malloc塊), 才是內(nèi)存泄露</font>, main結(jié)束后, crt會釋放自己的malloc塊, 但其實(shí)main結(jié)束, sbh也就完全銷毀了, 用戶泄露的內(nèi)存也隨著銷毀
loki
簡介
- <font color=red>loki是一個(gè)庫, 這里只是拿他的分配器來說事</font>
- 回顧前面的 <font color=red>GNUC的alloc</font>, 它的缺點(diǎn)就是 <font color=red>沒辦法將內(nèi)存還給OS</font>, 原因是設(shè)計(jì)上不允許
- 可歸還給os的內(nèi)存池, 拋開malloc那種復(fù)雜的設(shè)計(jì), 一種比較直觀的解決方案是 <font color=red>一塊malloc出來的chunk塊內(nèi)存不要在使用的過程中掛載到其他地方</font>, 也就是說 <font color=red>就只使用它</font>, 以一個(gè)簡單的demo來說明
using namespace std;
const int unit = 8;
const int chunk = 20;
char* start = NULL;
unsigned next_idx;
unsigned available;
void init(void* begin) {
for (int i = 0, j = 0; j < chunk; i += unit)
*(unsigned int*)(start + i) = ++j;
next_idx = 0;
available = chunk;
}
void* get() {
if (available == 0)
return 0;
void* result = (void*)(start + next_idx * unit);
next_idx = *(unsigned*)result;
--available;
return result;
}
void del(void* ptr) {
if (ptr == nullptr)
return;
if (ptr < start || ptr >= (start + unit * chunk))
return;
*(unsigned*)ptr = next_idx;
next_idx = ((char*)ptr - start) / unit;
++available;
}
void test_get() {
void* get_a = get();
cout << get_a << endl;
void* get_b = get();
cout << get_b << endl;
void* get_c = get();
cout << get_c << endl;
}
void test_del() {
void* get_a = get();
cout << get_a << endl;
void* get_b = get();
cout << get_b << endl;
void* get_c = get();
cout << get_c << endl;
void* get_d = get();
cout << get_d << endl;
del(get_c);
del(get_a);
void* get_e = get();
cout << get_e << endl; //獲取的是原來的get_a
void* get_f = get();
cout << get_f << endl; //獲取的是原來的get_c
void* get_g = get();
cout << get_g << endl; //獲取的是原來get_d后面的1塊內(nèi)存地址
}
int main(int arg, char** args) {
start = (char*)malloc(unit * chunk);
init(start);
//test_get();
test_del();
}
/**
00DA06A0 get_a
00DA06A8 get_b
00DA06B0 get_c
00DA06B8 get_d
00DA06A0 get_e
00DA06B0 get_f
00DA06C0 get_g
測試的是 test_del()
*/
上述小例子的原理
61.png
62.png
63.png
64.png
65.png
圖中的過程其實(shí)很清楚了
案例中核心的思想是:
沒用過的內(nèi)存, 堅(jiān)決不用, 一定要等它前面的內(nèi)存用完后, 再用后面沒有用過的
如第5塊內(nèi)存, 因?yàn)樗懊嫦群筮€了第3塊和第1塊, 所以后續(xù)再用的時(shí)候, 必須先取它前面沒用過的
為了實(shí)現(xiàn) 第5塊內(nèi)存 之前沒用過的內(nèi)存要先后用完, 所以用了next_idx來標(biāo)記 再取內(nèi)存時(shí)應(yīng)該從哪里開始
每1塊回來的內(nèi)存都會標(biāo)記 這塊內(nèi)存用完后下1塊可取的內(nèi)存序號, 所以就無形形成了1個(gè)鏈表, 形成鏈表的目的:
就是用完目前第5塊前面所有的內(nèi)存
這就是loki內(nèi)存分配器的核心, 很明顯, 這里完全可以構(gòu)造出 vector<(start, next_idx, avaiable)> 多個(gè)這樣的結(jié)構(gòu)
用來處理不同chunk, 并且根據(jù)avaiable就可以做到歸還os(avaiable為滿值時(shí))
loki分配器的3個(gè)類結(jié)構(gòu)
67.png
流程:
Chunk就是上面小例子中的實(shí)現(xiàn)機(jī)制, 用來分配內(nèi)存, 收回內(nèi)存
FixedAllotator是 多個(gè)相同 大小的chunk容器
如它的Chunk對象只負(fù)責(zé)8字節(jié)
SmallObjAllocator就是 管理不同字節(jié)大小的 FixedAllocator
對比前面的GNUC alloc:
FixedAllocator就是某個(gè)字節(jié)大小(如:8字節(jié))的鏈表, 但它是用數(shù)組的方式來管理,每次malloc的內(nèi)存有記錄,并連續(xù) 便于回收
SmallObjAllocator就是管理各個(gè)不同大小的FixedAllocator(8字節(jié), 16字節(jié), ....)
下面就依照這張圖, 來實(shí)現(xiàn)一個(gè)可收回的allocator
ps: 并不是實(shí)現(xiàn)loki, 話說本人是并不知道loki的具體實(shí)現(xiàn), 但既然loki是用 上面小案例的機(jī)制實(shí)現(xiàn)了可回收的分配器
那從道理上講, 不管是怎么實(shí)現(xiàn)的, 原理都一樣, 只是設(shè)計(jì)上會有出入
下面是一個(gè)簡單的實(shí)現(xiàn), 沒怎么細(xì)致測試
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<unordered_map>
#include<atomic>
#include<thread>
#define _TEST_
#ifdef _TEST_
#include<sstream>
#define from_print ((void*)from)
#define full_print ((void*)full)
#endif // _TEST_
using namespace std;
/**
最大管理 96字節(jié), 超過后交給::operator new
每條鏈表最多 是 96 * 16 的空間(1536)
_unit _chunk
8 192
16 96
24 64
32 48
40 38(實(shí)際是1536/40 = 38.4, 要小于1536, 所以取38)
48 32
56 27(同40的情況)
64 24
72 21
80 19
88 17
96 16
*/
namespace lb { namespace loki {
using namespace std;
constexpr size_t MAX_UNIT = 96;
constexpr size_t MIN_UNIT = 8;
constexpr size_t ARR_SIZE = 12;
constexpr size_t MAX_MEMORY = MAX_UNIT * 16;
template<size_t _unit>constexpr size_t get_chunk() {
static_assert((_unit % MIN_UNIT == 0), "必須為8的倍數(shù)");
return (size_t)(MAX_MEMORY / _unit);
}
template<>constexpr size_t get_chunk<0>() {return 0;}
template<size_t _unit, size_t _chunk> class group_chunk;
static size_t get_count;
static size_t del_count;
static size_t total;
template<>class group_chunk<0, 0> {
public:
virtual void test() { }
virtual void* alloc() { return 0; }
virtual void dealloc(void* ptr) { }
public:
template<size_t _unit, size_t _chunk>
struct _alloc : public _alloc<0,0>{
_alloc(){init();}
void init() {
start = (char*)::operator new(_unit * _chunk);
total += _chunk;
for (int i = 0, j = 0; j < _chunk; i += _unit)
*(unsigned int*)(start + i) = ++j;
idx = 0;
available = _chunk;
}
virtual void* get() {
++get_count;
if (available == 0)
return 0;
void* result = (void*)(start + idx * _unit);
idx = *(size_t*)result;
--available;
return result;
}
virtual void del(void* ptr) {
++del_count;
*(size_t*)ptr = idx;
idx = ((char*)ptr - start) / _unit;
++available;
}
virtual bool full()const {
return available == _chunk;
}
};
template<>
struct _alloc<0, 0> {
char* start;
size_t idx = 0;
size_t available = 0;
virtual void* get() { return 0; }
virtual void del(void* ptr) { }
virtual bool full()const { return false; }
// 因?yàn)楸景咐? map存放的是指針, 所以這里不給出big three, 以及移動(dòng)ctor
virtual ~_alloc(){
if (start) {
delete start;
}
}
};
protected:
unordered_map<char*, _alloc<0,0>*> map;
char* from;
char* full;
atomic<bool> lock{false};
};
template<size_t _unit, size_t _chunk = get_chunk<_unit>()>
class group_chunk : public group_chunk<0,0> {
virtual void test() {
cout << "_unit: " << _unit << endl;
cout << "_chunk: " << _chunk << endl;
cout << "map: " << &this->map << endl;
}
char* find_has() {
for (auto it = map.begin(), end = map.end(); it != end; ++it)
if (it->second->available)
return it->first;
return nullptr;
}
virtual void* alloc() override {
while (this->lock.exchange(true, memory_order_acq_rel)){
this_thread::yield();
continue;
}
if (this->from) {
auto cur_alloc = this->map[this->from];
auto result = cur_alloc->get();
if (!result) {
this->from = nullptr;
this->lock.store(false, memory_order_release);
return alloc();
}
// 如果調(diào)用前當(dāng)前的區(qū)塊已經(jīng)是全回收, 給出內(nèi)存后,full要去掉記錄
if (this->full == cur_alloc->start)
this->full = nullptr;
this->from = cur_alloc->available ? this->from : find_has();
this->lock.store(false, memory_order_release);
return result;
}
//map中沒有可用的數(shù)組, 創(chuàng)建一塊空間
_alloc<0, 0>* arr = new _alloc<_unit, _chunk>();
map.insert(make_pair(arr->start, arr));
this->from = arr->start;
this->lock.store(false, memory_order_release);
return alloc();
}
virtual void dealloc(void* ptr) override {
char* tmp_ptr = (char*)ptr;
char* record_del = 0;
while (this->lock.exchange(true, memory_order_acq_rel)) {
this_thread::yield();
continue;
}
for (auto it = map.begin(), end = map.end(); it != end; ++it) {
if (tmp_ptr >= it->first && tmp_ptr < it->first+(_chunk * _unit)) {
it->second->del(ptr);
// 當(dāng)前全回收, 并且有記錄, 則要?jiǎng)h除當(dāng)前的這個(gè)
if (it->second->full() && this->full)
record_del = it->first;
// 當(dāng)前全回收, 但沒有記錄, 則記錄下當(dāng)前這個(gè)
else if(it->second->full() && !this->full) {
this->full = it->first;
}
//還內(nèi)存了, 就意味著有可取內(nèi)存, 則看from有沒有值, 沒有就記錄當(dāng)前這個(gè)
/// 下次就根據(jù)from從當(dāng)前的空間取(from可能和full共用)
if(this->from == nullptr && !record_del)
this->from = it->first;
//from有值(指向當(dāng)前), 但當(dāng)前被刪除, 則為from尋找下一個(gè)有值的區(qū)塊
if (this->from == record_del) {
this->from = find_has();
}
break;
}
}
if (record_del) {
auto del_alloc = map.at(record_del);
// 從容器中刪除
map.erase(record_del);
delete del_alloc;
}
this->lock.store(false, memory_order_release);
}
};
class allocator {
public:
void* alloc(size_t len) {
size_t up = (len + MIN_UNIT - 1) & ~(MIN_UNIT - 1);
size_t index = up / MIN_UNIT - 1;
return groups[index]->alloc();
}
void dealloc(void* ptr, size_t len) {
size_t up = (len + MIN_UNIT - 1) & ~(MIN_UNIT - 1);
size_t index = up / MIN_UNIT - 1;
groups[index]->dealloc(ptr);
}
private:
template<size_t _idx>
static constexpr size_t round_up() {
return (_idx + 1) * MIN_UNIT;
}
template<size_t _idx>
static constexpr void initialize_header(group_chunk<0, 0>** header) {
static group_chunk<round_up<_idx>()> group;
header[_idx] = static_cast<group_chunk<0, 0>*>(&group);
initialize_header<_idx - 1>(header);
}
template<>
static void initialize_header<0>(group_chunk<0,0>** header) {
static group_chunk<8> group;
header[0] = static_cast<group_chunk<0,0>*>(&group);
}
template<size_t _count>
static constexpr group_chunk<0, 0>** initialize_header() {
static group_chunk<0, 0>* header[_count];
initialize_header<_count - 1>(static_cast<group_chunk<0, 0>**>(header));
return static_cast<group_chunk<0, 0>**>(header);
}
static group_chunk<0, 0>** groups;
};
group_chunk<0, 0>** lb::loki::allocator::groups = initialize_header<ARR_SIZE>();
}}
void test_size() {
lb::loki::group_chunk<0, 0>* ptr_8 = new lb::loki::group_chunk<8>();
lb::loki::group_chunk<0, 0>* ptr_16 = new lb::loki::group_chunk<16>();
lb::loki::group_chunk<0, 0>* ptr_24 = new lb::loki::group_chunk<24>();
lb::loki::group_chunk<0, 0>* ptr_32 = new lb::loki::group_chunk<32>();
cout << "大小:\n";
cout << sizeof(lb::loki::group_chunk<8>) << endl;
cout << sizeof(lb::loki::group_chunk<16>) << endl;
cout << sizeof(lb::loki::group_chunk<24>) << endl;
cout << sizeof(lb::loki::group_chunk<32>) << endl;
cout << sizeof(unordered_map<char*, lb::loki::group_chunk<0,0>::_alloc<0,0>*>) << endl;
}
/**
測試單獨(dú)的group_chunk
*/
void test_multi() {
using __alloc__ = lb::loki::group_chunk<96>;
lb::loki::group_chunk<0, 0>* ptr_96 = new lb::loki::group_chunk<96>();
auto mem_get = [ptr_96](bool rmv)->void {
auto mem = ptr_96->alloc();
ostringstream os;
os << "thread: " << this_thread::get_id() << endl;
os << "get mem: " << mem << endl;
cout << os.str();
ptr_96->dealloc(mem);
};
for (int i = 0; i < 10; ++i) {
thread t_a(mem_get, i%2);
thread t_b(mem_get, i%2);
thread t_c(mem_get, i%2);
thread t_d(mem_get, i%2);
thread t_e(mem_get, i%2);
thread t_f(mem_get, i%2);
t_a.join();
t_b.join();
t_c.join();
t_d.join();
t_e.join();
t_f.join();
}
cout << "over\n";
cout << lb::loki::get_count << endl;
cout << lb::loki::del_count << endl;
cout << lb::loki::total << endl;
}
void test_loki() {
lb::loki::allocator _all;
auto mem_get = [&_all](size_t len)->void {
auto mem = _all.alloc(len);
ostringstream os;
os << "thread: " << this_thread::get_id() << endl;
os << "get mem: " << mem << endl;
cout << os.str();
_all.dealloc(mem,len);
};
for (int i = 0; i < 10; ++i) {
thread t_a(mem_get, 6);
thread t_b(mem_get, 6);
thread t_c(mem_get, 6);
thread t_d(mem_get, 6);
thread t_e(mem_get, 6);
thread t_f(mem_get, 6);
t_a.join();
t_b.join();
t_c.join();
t_d.join();
t_e.join();
t_f.join();
}
cout << "over\n";
cout << lb::loki::get_count << endl;
cout << lb::loki::del_count << endl;
cout << lb::loki::total << endl;
}
int main(int arg, char** args) {
//test_size();
cout << "********************\n";
//test_multi();
cout << "********************\n";
test_loki();
}
GNUC的其他分配器
分配器的標(biāo)準(zhǔn)描述
- 分配器的意義在于 <font color=red>容器服務(wù)</font>, 原因就不說了
- 當(dāng) <font color=red>元素加入到容器中時(shí)</font>, 容器必須分配更多內(nèi)存來保存這些元素, 于是向 <font color=red>模板參數(shù)Allocator發(fā)出申請</font>
- 每個(gè)元素類型為T的容器的==Allocator==模板的==默認(rèn)參數(shù)==是 <font color=red>
allocator<T></font>, 接口大概有==20==個(gè)==public==聲明, 但最重要的2個(gè)是:T* allocate(size_type n, const void* hint = 0)void deallocate(T* p, size_type n)
ps: n是n個(gè)T, 并不是總量, 它們是通過用
::operator new獲取內(nèi)存, 但==何時(shí)調(diào)用==, 以及==調(diào)用頻率==, 沒有具體指定(即==沒有做緩存管理==)
- 最容易滿足的作法就是 <font color=red>需要時(shí)就==要==, 釋放時(shí)就==還==</font>, 就是所謂的 <font color=red>operator new和operator delete</font>,優(yōu)勢就是跨平臺
- 支持這樣作法的分配器有:
__gnu_cxx::new_allocator__gnu_cxx::malloc_allocator
ps: 第1個(gè)是調(diào)用 <font color=red>::operator new和delete</font>, 是C++的標(biāo)準(zhǔn), 支持跨平臺, 支持重載, 第2個(gè)是C的標(biāo)準(zhǔn), 內(nèi)部直接調(diào)用的malloc/free, 但不能重載
- 支持這樣作法的分配器有:
- 另一種就是使用 <font color=red>智能型</font>, 就是前面實(shí)現(xiàn)的==allocate==, 不過在GNUC中還有其他功能的內(nèi)存池
array_allocator
/**
相當(dāng)于一個(gè)static array[static size_t]
下面是在g++的環(huán)境下
*/
using namespace std;
using namespace std::tr1; //array_allocator可能引用的是TR1版本的array, 但其實(shí)和C++11的array實(shí)現(xiàn)是一樣的
using namespace __gnu_cxx; //因?yàn)椴皇菢?biāo)準(zhǔn)的分配器, 所以放在別的namespace中
int arr[20];
array_allocator<int, array<int,20>> arr_alloc(&arr);
void test(){
int* p_a = arr_alloc.allocate(1);
int* p_b = arr_alloc.allocate(3);
// 內(nèi)部并不會釋放空間, 因?yàn)槭庆o態(tài)數(shù)組
/// 先不管它是怎么實(shí)現(xiàn)的, 如果自己來實(shí)現(xiàn)復(fù)用, 那不就是可以利用上面的loki的原理
// 但其實(shí)array_allocator的deallocate什么都沒有做
arr_alloc.deallocate(p_a);
arr_alloc.deallocate(p_b);
}
<font color=red size=12>以后再回補(bǔ)充</font>
-
C運(yùn)行環(huán)境(==C runtime library,也可以理解為進(jìn)程初始化==)[圖片上傳中...(36.png-570617-1614094151878-0)] ?
