二级网站怎么建,网站不备案可以访问吗,随州网站推广哪家权威,爱站攻略手写移植SGI STL二级空间配置器内存池 项目源码
笔者建议配合这两篇博客进行学习
侯捷 | C | 内存管理 | 学习笔记#xff08;二#xff09;:第二章节 std::allocator-CSDN博客
施磊C | 项目实战 | SGI STL二级空间配置器源码剖析-CSDN博客 文章目录 手写移植SGI STL二级空…手写移植SGI STL二级空间配置器内存池 项目源码
笔者建议配合这两篇博客进行学习
侯捷 | C | 内存管理 | 学习笔记二:第二章节 std::allocator-CSDN博客
施磊C | 项目实战 | SGI STL二级空间配置器源码剖析-CSDN博客 文章目录 手写移植SGI STL二级空间配置器内存池 项目源码1.大致框架2.allocate函数3.refill函数4._S_chunk_alloc函数5.malloc_alloc::allocate函数6.deallocate函数7.reallocate8.完整版myallocator.h9.pch.h和pch.cpp10.测试 考虑的问题多线程安全
空间配置器是容器使用的而容器产生的对象是很有可能在多个线程中去操作的
1.大致框架
1.四个函数定义
2.重要的类型变量
3.两个辅助函数
4.静态成员函数初始化
#pragma once
#includemutex
//移植SGI STL二级空间配置器内存池 源码templatetypename T
class myallocator
{
public://开辟内存 __n是开辟的大小多少字节T* allocate(size_t __n);//释放内存 __n是释放的大小void deallocate(void* __p, size_t __n);//内存扩容或缩容void* reallocate(void* __P, size_t __old_sz, size_t __new_sz);//对象构造 定位new实现void construct(T *__p,const Tval){new (__p) T(val);}//对象析构void destroy(T* __p){__p-~T();}
private://自由链表是从8字节开始以8字节为对齐方式扩充到128字节//obj数组的第一个链表挂着的是8字节第二个是16字节一次类推到128字节enum { _ALIGN 8 };//内存池最大的chunk块的大小enum { _MAX_BYTES 128 };//自由链表的数量 16 128 / 8enum { _NFREELISTS 16 };// 每一个内存chunk块结点的头信息union _Obj {union _Obj* _M_free_list_link;//保存下一个结点的地址char _M_client_data[1]; };// 组织所有自由链表的数组数组的每一个元素的类型是_Obj*全部初始化为 0/*多线程环境下防止线程自己拷贝一个副本会加一个volatile关键字使得在数据段或者堆上的数据改变了每个线程都可以立马看到防止多个线程看到的数据版本不一致*/static _Obj* volatile _S_free_list[_NFREELISTS];//s_free_list存储自由链表数组的地址这是个数组名大小就是上面的16//内存池基于freelist实现需要考虑线程安全主要做互斥操作 换成C11的锁static std::mutex mtx;//已分配的内存chunk块的使用情况 初始化全为0//start~~end 分配给程序之后剩下的空闲内存起始和终止地址 heapsize 堆的大小记录的是已经分配的内存大小 除以16算出来的就是追加量static char* _S_start_free;static char* _S_end_free;static size_t _S_heap_size;/*将 __bytes 上调至最邻近的 8 的倍数 _ALIGN81-8 全都映射对齐到89-16 全都映射对齐到16*/static size_t _S_round_up(size_t __bytes){return (((__bytes)(size_t)_ALIGN - 1) ~((size_t)_ALIGN - 1));}/*返回 __bytes 大小的chunk块位于 free-list 中的编号作用就是如果申请的字节在1-8之间就挂到内存块大小为8的那个链表下面如果申请的字节在9-16之间就挂到内存块大小为16的那个链表下面*/static size_t _S_freelist_index(size_t __bytes) {return (((__bytes)(size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);}//把分配好的chunk进行连接的static void* _S_refill(size_t __n);//主要负责分配自由链表chunk块的static char* _S_chunk_alloc(size_t __size,int __nobjs);
};//静态成员变量初始化
template typename T
char* myallocatorT::_S_start_free nullptr;
template typename T
char* myallocatorT::_S_end_free nullptr;
template typename T
size_t myallocatorT::_S_heap_size 0;template typename T
//这里的typename告诉编译器这里是一个类型定义
typename myallocatorT::_Obj* volatile myallocatorT::_S_free_list[_NFREELISTS]
{nullptr,nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr};template typename T
std::mutex myallocatorT::mtx;
2.allocate函数
//开辟内存 __n是开辟的大小多少字节
T* allocate(size_t __n)
{//要传入的是字节数而容器调用传进来的1,2,3这些数字是个数不是字节数还要乘以T的大小才行__n __n * sizeof(T);void* __ret 0;//大于128字节直接mallocif (__n (size_t)_MAX_BYTES) {__ret malloc_alloc::allocate(__n);}//小于128字节else {_Obj* volatile* __my_free_list _S_free_list _S_freelist_index(__n);//线程安全std::lock_guardstd::mutex guard(mtx);_Obj* __result *__my_free_list;//内存池有chunk块就去相应大小的链表下面拿没有的话就看如何进行分配了if (__result 0)//没有相应大小chunk块下面解释如何分配__ret _S_refill(_S_round_up(__n));else {//有相应大小chunk块,就从内存池里面拿出相应的块分配给程序*__my_free_list __result-_M_free_list_link;__ret __result;}}//返回我们从内存池申请的chunk块return (T*)__ret;
}注意点
1.vector容器传入的__n是对象个数还要乘以对象类型T的大小才是我们要开辟的字节数
2.最后指针要强转
3.把线程安全换成c11的互斥锁
3.refill函数
//把分配好的chunk进行连接的
static void* _S_refill(size_t __n)
{int __nobjs 20;//chunk_alloc主要负责内存开辟char* __chunk _S_chunk_alloc(__n, __nobjs);_Obj* volatile* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;if (1 __nobjs) return(__chunk);__my_free_list _S_free_list _S_freelist_index(__n);/* Build free list in chunk *///result和chunk都指向chunk_alloc分配的内存的首地址 chunk指针用来遍历chunk块result指针指向开头的地方做一个保存__result (_Obj*)__chunk;//把头指针的位置指向下一chunk块因为当前的情形是已经要把当前自由链表头指针的位置分配出去了而头指针的后面才是剩下的空闲的chunk块再次分配是分配空闲的分配出去的就没关系了*__my_free_list __next_obj (_Obj*)(__chunk __n);for (__i 1; ; __i) {__current_obj __next_obj;//这行描述的就是遍历过程 先转成char*这样每次加减都是以字节为单位chunk指针每一次加8字节到下一个chunk块不一定是8这里只是说明具体多少要看内存块的大小反正就是到下一个chunk内存块了__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;}}//返回第一个空闲的chunk结点给容器使用return(__result);
}4._S_chunk_alloc函数 //主要负责分配自由链表chunk块的static char* _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) {__result _S_start_free;_S_start_free __total_bytes;return(__result);}else if (__bytes_left __size) {__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) {_Obj* 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 (nullptr _S_start_free) {size_t __i;_Obj* volatile* __my_free_list;_Obj* __p;// Try to make do with what we have. That cant// 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) {__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));}}5.malloc_alloc::allocate函数
最后一行typedef __malloc_alloc_template0 malloc_alloc;
这个类就是malloc_alloc
//封装了malloc和free函数可以设置OOM释放内存的回调函数
template int __inst
class __malloc_alloc_template {private:static void* _S_oom_malloc(size_t);static void* _S_oom_realloc(void*, size_t);static void (*__malloc_alloc_oom_handler)();public:static void* allocate(size_t __n){void* __result malloc(__n);if (0 __result) __result _S_oom_malloc(__n);return __result;}static void deallocate(void* __p, size_t /* __n */){free(__p);}static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz){void* __result realloc(__p, __new_sz);if (0 __result) __result _S_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);}};template int __inst
void (*__malloc_alloc_template__inst::__malloc_alloc_oom_handler)() 0;template int __inst
void*
__malloc_alloc_template__inst::_S_oom_malloc(size_t __n)
{void (*__my_malloc_handler)();void* __result;for (;;) {__my_malloc_handler __malloc_alloc_oom_handler;if (0 __my_malloc_handler) { throw std::bad_alloc(); }(*__my_malloc_handler)();__result malloc(__n);if (__result) return(__result);}
}template int __inst
void* __malloc_alloc_template__inst::_S_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 std::bad_alloc(); }(*__my_malloc_handler)();__result realloc(__p, __n);if (__result) return(__result);}
}typedef __malloc_alloc_template0 malloc_alloc;6.deallocate函数
//释放内存 __n是释放的大小
void deallocate(void* __p, size_t __n)
{//回收的过大 直接用freeif (__n (size_t)_MAX_BYTES)malloc_alloc::deallocate(__p, __n);else {//定位到要回收的chunk块的地址_Obj* volatile* __my_free_list _S_free_list _S_freelist_index(__n);_Obj* __q (_Obj*)__p;std::lock_guardstd::mutex guard(mtx);//这里就是链表的头插法//要归还的块是要插入的块要插入到头结点和头结点的next域指的节点这个节点是第一个空闲块而我们归还的这个块就接到头结点的next域然后要回收的块再接着原来的第一个空闲块成为新的第一个空闲块就类比一下链表的头插法就行__q-_M_free_list_link *__my_free_list;*__my_free_list __q;// lock is released here 出作用域锁释放}
}7.reallocate
//内存扩容或缩容
void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
{void* __result;size_t __copy_sz;//如果旧的和新的全都比128字节大那说明这就不是从我内存池里面出去的那就直接调用c的realloc函数if (__old_sz (size_t)_MAX_BYTES __new_sz (size_t)_MAX_BYTES) {return(realloc(__p, __new_sz));}//如果新的和旧的对齐以后一样那就不用扩容直接返回 比如一个12扩容到15但是这两个的round_up都是16 那就没必要扩容了if (_S_round_up(__old_sz) _S_round_up(__new_sz)) return(__p);//分配一块新的大小的内存空间__result allocate(__new_sz);//比较大小就选个比较小的__copy_sz __new_sz __old_sz ? __old_sz : __new_sz;//把内容copy到新开辟的内存空间memcpy(__result, __p, __copy_sz);//把旧的内存空间给释放掉deallocate(__p, __old_sz);//最后把新的内存地址返回return(__result);
}8.完整版myallocator.h
#pragma once
#includemutex
#includeiostream
//移植SGI STL二级空间配置器内存池 源码//封装了malloc和free函数可以设置OOM释放内存的回调函数
template int __inst
class __malloc_alloc_template {private:static void* _S_oom_malloc(size_t);static void* _S_oom_realloc(void*, size_t);static void (*__malloc_alloc_oom_handler)();public:static void* allocate(size_t __n){void* __result malloc(__n);if (0 __result) __result _S_oom_malloc(__n);return __result;}static void deallocate(void* __p, size_t /* __n */){free(__p);}static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz){void* __result realloc(__p, __new_sz);if (0 __result) __result _S_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);}};template int __inst
void (*__malloc_alloc_template__inst::__malloc_alloc_oom_handler)() 0;template int __inst
void*
__malloc_alloc_template__inst::_S_oom_malloc(size_t __n)
{void (*__my_malloc_handler)();void* __result;for (;;) {__my_malloc_handler __malloc_alloc_oom_handler;if (0 __my_malloc_handler) { throw std::bad_alloc(); }(*__my_malloc_handler)();__result malloc(__n);if (__result) return(__result);}
}template int __inst
void* __malloc_alloc_template__inst::_S_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 std::bad_alloc(); }(*__my_malloc_handler)();__result realloc(__p, __n);if (__result) return(__result);}
}typedef __malloc_alloc_template0 malloc_alloc;templatetypename T
class myallocator
{
public://vector容器里面要用的东西不写就会报错using value_type T;//模仿写vector的allocator的构造和拷贝构造 不写也会报错的constexpr myallocator() noexcept{ // construct default allocator (do nothing)}constexpr myallocator(const myallocator) noexcept default;templateclass _Otherconstexpr myallocator(const myallocator_Other) noexcept{ // construct from a related allocator (do nothing)}//开辟内存 __n是开辟的大小多少字节T* allocate(size_t __n){//要传入的是字节数而容器调用传进来的1,2,3这些数字是个数不是字节数还要乘以T的大小才行__n __n * sizeof(T);void* __ret 0;//大于128字节直接mallocif (__n (size_t)_MAX_BYTES) {__ret malloc_alloc::allocate(__n);}//小于128字节else {_Obj* volatile* __my_free_list _S_free_list _S_freelist_index(__n);//线程安全std::lock_guardstd::mutex guard(mtx);_Obj* __result *__my_free_list;//内存池有chunk块就去相应大小的链表下面拿没有的话就看如何进行分配了if (__result 0)//没有相应大小chunk块下面解释如何分配__ret _S_refill(_S_round_up(__n));else {//有相应大小chunk块,就从内存池里面拿出相应的块分配给程序*__my_free_list __result-_M_free_list_link;__ret __result;}}//返回我们从内存池申请的chunk块return (T*)__ret;}//释放内存 __n是释放的大小void deallocate(void* __p, size_t __n){//回收的过大 直接用freeif (__n (size_t)_MAX_BYTES)malloc_alloc::deallocate(__p, __n);else {//定位到要回收的chunk块的地址_Obj* volatile* __my_free_list _S_free_list _S_freelist_index(__n);_Obj* __q (_Obj*)__p;std::lock_guardstd::mutex guard(mtx);//这里就是链表的头插法//要归还的块是要插入的块要插入到头结点和头结点的next域指的节点这个节点是第一个空闲块而我们归还的这个块就接到头结点的next域然后要回收的块再接着原来的第一个空闲块成为新的第一个空闲块就类比一下链表的头插法就行__q-_M_free_list_link *__my_free_list;*__my_free_list __q;// lock is released here 出作用域锁释放}}//内存扩容或缩容void* reallocate(void* __p, size_t __old_sz, size_t __new_sz){void* __result;size_t __copy_sz;//如果旧的和新的全都比128字节大那说明这就不是从我内存池里面出去的那就直接调用c的realloc函数if (__old_sz (size_t)_MAX_BYTES __new_sz (size_t)_MAX_BYTES) {return(realloc(__p, __new_sz));}//如果新的和旧的对齐以后一样那就不用扩容直接返回 比如一个12扩容到15但是这两个的round_up都是16 那就没必要扩容了if (_S_round_up(__old_sz) _S_round_up(__new_sz)) return(__p);//分配一块新的大小的内存空间__result allocate(__new_sz);//比较大小就选个比较小的__copy_sz __new_sz __old_sz ? __old_sz : __new_sz;//把内容copy到新开辟的内存空间memcpy(__result, __p, __copy_sz);//把旧的内存空间给释放掉deallocate(__p, __old_sz);//最后把新的内存地址返回return(__result);}//对象构造 定位new实现void construct(T *__p,const Tval){new (__p) T(val);}//对象析构void destroy(T* __p){__p-~T();}
private://自由链表是从8字节开始以8字节为对齐方式扩充到128字节//obj数组的第一个链表挂着的是8字节第二个是16字节一次类推到128字节enum { _ALIGN 8 };//内存池最大的chunk块的大小enum { _MAX_BYTES 128 };//自由链表的数量 16 128 / 8enum { _NFREELISTS 16 };// 每一个内存chunk块结点的头信息union _Obj {union _Obj* _M_free_list_link;//保存下一个结点的地址char _M_client_data[1]; };// 组织所有自由链表的数组数组的每一个元素的类型是_Obj*全部初始化为 0/*多线程环境下防止线程自己拷贝一个副本会加一个volatile关键字使得在数据段或者堆上的数据改变了每个线程都可以立马看到防止多个线程看到的数据版本不一致*/static _Obj* volatile _S_free_list[_NFREELISTS];//s_free_list存储自由链表数组的地址这是个数组名大小就是上面的16//内存池基于freelist实现需要考虑线程安全主要做互斥操作static std::mutex mtx;//已分配的内存chunk块的使用情况 初始化全为0//start~~end 分配给程序之后剩下的空闲内存起始和终止地址 heapsize 堆的大小记录的是已经分配的内存大小 除以16算出来的就是追加量static char* _S_start_free;static char* _S_end_free;static size_t _S_heap_size;/*将 __bytes 上调至最邻近的 8 的倍数 _ALIGN81-8 全都映射对齐到89-16 全都映射对齐到16*/static size_t _S_round_up(size_t __bytes){return (((__bytes)(size_t)_ALIGN - 1) ~((size_t)_ALIGN - 1));}/*返回 __bytes 大小的chunk块位于 free-list 中的编号作用就是如果申请的字节在1-8之间就挂到内存块大小为8的那个链表下面如果申请的字节在9-16之间就挂到内存块大小为16的那个链表下面*/static size_t _S_freelist_index(size_t __bytes) {return (((__bytes)(size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);}//把分配好的chunk进行连接的static void* _S_refill(size_t __n){int __nobjs 20;//chunk_alloc主要负责内存开辟char* __chunk _S_chunk_alloc(__n, __nobjs);_Obj* volatile* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;if (1 __nobjs) return(__chunk);__my_free_list _S_free_list _S_freelist_index(__n);/* Build free list in chunk *///result和chunk都指向chunk_alloc分配的内存的首地址 chunk指针用来遍历chunk块result指针指向开头的地方做一个保存__result (_Obj*)__chunk;//把头指针的位置指向下一chunk块因为当前的情形是已经要把当前自由链表头指针的位置分配出去了而头指针的后面才是剩下的空闲的chunk块再次分配是分配空闲的分配出去的就没关系了*__my_free_list __next_obj (_Obj*)(__chunk __n);for (__i 1; ; __i) {__current_obj __next_obj;//这行描述的就是遍历过程 先转成char*这样每次加减都是以字节为单位chunk指针每一次加8字节到下一个chunk块不一定是8这里只是说明具体多少要看内存块的大小反正就是到下一个chunk内存块了__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;}}//返回第一个空闲的chunk结点给容器使用return(__result);}//主要负责分配自由链表chunk块的static char* _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) {__result _S_start_free;_S_start_free __total_bytes;return(__result);}else if (__bytes_left __size) {__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) {_Obj* 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 (nullptr _S_start_free) {size_t __i;_Obj* volatile* __my_free_list;_Obj* __p;// Try to make do with what we have. That cant// 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) {__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));}}};//静态成员变量初始化
template typename T
char* myallocatorT::_S_start_free nullptr;
template typename T
char* myallocatorT::_S_end_free nullptr;
template typename T
size_t myallocatorT::_S_heap_size 0;template typename T
//这里的typename告诉编译器这里是一个类型定义
typename myallocatorT::_Obj* volatile myallocatorT::_S_free_list[_NFREELISTS]
{nullptr,nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr};template typename T
std::mutex myallocatorT::mtx;
9.pch.h和pch.cpp
//.h
#pragma once
#ifndef PCH_H
#define PCH_H#endif//.cpp
#includepch.h10.测试
#include iostream
#includevector
#includepch.h
#includemyallocator.husing namespace std;int main()
{vectorint, myallocatorint v;for (int i 0; i 100; i)v.push_back(rand() % 1000);for (int val : v)cout val ;cout endl;return 0;
}总结
通过源码移植可以更加清楚内存池整个分配内存和释放的过程。
侯捷老师内存管理第二章和施磊老师的课程讲清楚了原理和流程。
施磊老师的手写移植内存池是进行实践。
