首页 > 代码库 > 内存配置器
内存配置器
stl中内存配置器分为两级:第一级配置对象超过128B的内存,第二级配置对象小于128B的内存,stl默认采用第二级内存配置器,因为如果对象大于128B,则第二级内存配置器会自动调用第一级内存配置器。
第一级内存配置器简单的对malloc,realloc,free的封装
第二级内存配置器采用内存池管理内存,并用16个链表管理回收到的空闲内存块,当分配内存时,首先找到合适位置的空闲链表,若链表上有空闲内存块,则直接摘下空闲内存块供使用;否则就需要向内存池申请新的空闲内存块,若内存池都没有剩余内存了,则要向系统申请堆内存扩容内存池,再在内存池上分配内存块到空闲内存链表上。若没记错的话nginx的内存池设计和stl很相似。
重新整理了《STL源码剖析》上的代码注释,如下:
#include<iostream> #include<new> #include<cstddef> #include<climits> #include<cstdlib> #include<vector> #include<algorithm> #include<assert.h> using namespace std; /* * 将malloc,free简单封装起来的一个简易内存配置器 */ template<typename T> class Allocator{//自己封装的简单内存配置器 public: //标准接口 typedef T value_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; template<class U> struct rebind{ typedef Allocator<U> other; }; pointer allocate(size_type n,const void* hint=0){ set_new_handler(NULL); T* tmp=(T*)(::operator new((size_t)(n*sizeof(T)))); if(tmp==0){ std::cerr<<"out of memory"<<endl; exit(1); } return tmp; } void deallocate(pointer p,size_type n){ ::operator delete(p);// 简单只析构第一个元素 } void construct(pointer p,const T& value){ new(p) T(value); } void destroy(pointer p){ p->~T(); } pointer address(reference x){return (pointer)&x;} const_pointer address(const_reference x){return (const_pointer)&x;} size_type max_size() const{ return size_type(UINT_MAX/sizeof(T)); } }; /* * 第一级配置器,直接调用malloc,free */ template <int inst> class __malloc_alloc_template { private: static void *oom_malloc(size_t); static void *oom_realloc(void *, size_t); static void (* __malloc_alloc_oom_handler)(); public: static void * allocate(size_t n) { void *result = malloc(n);//第一级配置器直接使用 malloc() if (0 == result) result = oom_malloc(n); return result; } static void deallocate(void *p, size_t /* n */) { free(p);//第一级配置器直接使用 free() } static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) { void * result = realloc(p, new_sz);// 第一级配置器直接使用 realloc() if (0 == result) result = oom_realloc(p, new_sz); return result; } // 以下类似C++的 set_new_handler(). 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; //配置n字节内存 template <int inst> void * __malloc_alloc_template<inst>::oom_malloc(size_t n) { void (* my_malloc_handler)(); void *result; for (;;) { //若客户端指定了内存配置失败处理程序则不断配置内存,否则直接退出程序 my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { exit(1);//客户端未定义内存配置失败处理程序则直接退出程序 }// { __THROW_BAD_ALLOC; } (*my_malloc_handler)();//调用客户端指定的内存配置失败的处理程序 result = malloc(n);// 再次尝试分配内存 if (result) return(result); } } //realloc template <int inst> void * __malloc_alloc_template<inst>::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){ exit(1); }//{ __THROW_BAD_ALLOC; } (*my_malloc_handler)(); // 呼叫處理常式,企圖釋放記憶體。 result = realloc(p, n); // 再次嘗試配置記憶體。 if (result) return(result); } } typedef __malloc_alloc_template<0> malloc_alloc; /* *第二级配置器 */ enum {__ALIGN = 8};//内存块对齐数目 enum {__MAX_BYTES = 128};//小型内存块上限,小于__MAX_BYTES采用第二级内存配置器,大于__MAX_BYTES采用第一级内存配置器 enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//空闲链表数目 template<int inst> class default_alloc_template{ private: //内存大小向上取为__ALIGN的整数倍 static size_t ROUND_UP(size_t bytes){ return (((bytes+__ALIGN-1)&~(__ALIGN-1))); } //空闲链表的元素 union obj{//当内存块空闲的时候使用free_list_link指向下一个空闲内存块,当内存块正在使用时该字节归还给内存块 union obj* free_list_link;//当为空闲链表则指向下一个链表元素 char client_data[1];//当为客户端使用时融入内存块 }; //__NFREELISTS个空闲链表分别表示内存大小:8B,16B,24B,....128B static obj* free_list[__NFREELISTS]; //给定一个内存大小找出合适的链表位置 static size_t FREELIST_INDEX(size_t bytes){ return ((bytes+__ALIGN-1)/__ALIGN-1); } //空闲链表有位置没有空闲内存块了,分配新空间填充空闲链表 static void* refill(size_t n){ int nobjs=20; //调用chunk_alloc尝试从内存池获得nobjs个大小为n的内存块,但是不一定得到20个 char* chunk=chunk_alloc(n,nobjs); if(nobjs==1)//如果只获得一个内存块则将这块返回给使用者,空闲链表无增加 return chunk; //将多余的内存块放入适当的空闲链表位置 obj** my_free_list=free_list+FREELIST_INDEX(n); obj* result=(obj*)chunk;//第一块返回给调用者 obj* next_obj=(obj*)(chunk+n);//从此处开始的内存块放入空闲链表,每个内存块长度为n *my_free_list=next_obj; obj* current_obj; for(int i=1;;i++){//将空闲链表串接到my_free_list的尾部,注意从1开始是因为第一块内存要返回给调用者 current_obj=next_obj; next_obj=(obj*)((char*)next_obj+n); if(nobjs-1==i){ current_obj->free_list_link=0; break; } else{ current_obj->free_list_link=next_obj; } } return result; } //配置一大块内存size*objs,若内存紧张则配置的内存块数目可能少于objs,所以传递引用表示返回实际配置的内存块数目 static char* chunk_alloc(size_t size,int& nobjs){ char * result; size_t total_bytes = size * nobjs; size_t bytes_left = end_free - start_free; //内存池还有区域可以分配给空闲链表 if (bytes_left >= total_bytes) { result = start_free; start_free += total_bytes; return(result); } else if (bytes_left >= size) { //内存池不能完全满足需求量,但足够供应一个以上的内存块 nobjs = bytes_left/size; total_bytes = size * nobjs; result = start_free; start_free += total_bytes; return(result); } else { //内存池连一个内存块的剩余空间也没有了 if (bytes_left > 0) { //尝试从内存池的残余零头分配给适当位置的空闲链表 obj ** my_free_list =free_list + FREELIST_INDEX(bytes_left); ((obj *)start_free) -> free_list_link = *my_free_list; *my_free_list = (obj *)start_free; } size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);//内存池扩张的容量 //向系统申请内存补充内存池 start_free = (char *)malloc(bytes_to_get); if (0 == start_free) {//malloc失败 int i; obj ** my_free_list, *p; //尝试搜寻空闲链表中还有较大的且未被使用的内存块,将它拿出来分割为一些小的内存块救急 for (i = size; i <= __MAX_BYTES; i += __ALIGN) { my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (0 != p) { *my_free_list = p -> free_list_link; start_free = (char *)p; end_free = start_free + i; //递归以修正nobjs,内存池任何残余的零头都被编入适当位置的空闲链表中备用 return(chunk_alloc(size, nobjs)); } } //如果空闲链表中没有较大的内存块可以救急,则调用一级配置器,那里有设置new_handler end_free = 0; // In case of exception. start_free = (char *)malloc_alloc::allocate(bytes_to_get); } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; //递归修正nobjs return(chunk_alloc(size,nobjs));//经过不断努力使内存池有空间了,但是还有将空间配置到空闲链表中,所以需要递归 } } //内存池的起始位置 static char* start_free; //内存池的结束位置 static char* end_free; static size_t heap_size; public: //内存配置器 static void* allocate(size_t n){ if(n>__MAX_BYTES) { //调用第一级配置器 return malloc_alloc::allocate(n); } //寻找空闲链表中合适位置是否有空闲内存块 obj** my_free_list=free_list+FREELIST_INDEX(n); obj* result=*my_free_list; if(0==result){//没有空间内存块则需要配置空闲链表 void* r=refill(ROUND_UP(n)); return r; } *my_free_list=result->free_list_link; return result; } //空间释放函数 static void deallocate(void* p,size_t n){ if(n>__MAX_BYTES){ malloc_alloc::deallocate(p,n); return; } //寻找合适的归还位置后将内存块放回空闲链表 obj** my_free_list=free_list+FREELIST_INDEX(n); obj* q=(obj*)p; q->free_list_link=*my_free_list; *my_free_list=q; } static void* reallocate(void* p,size_t old_sz,size_t new_sz); }; template<int inst> char* default_alloc_template<inst>::start_free=0; template<int inst> char* default_alloc_template<inst>::end_free=0; template<int inst> size_t default_alloc_template<inst>::heap_size=0; template<int inst> typename default_alloc_template<inst>::obj* default_alloc_template<inst>::free_list[__NFREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; typedef default_alloc_template<0> Alloc; /* * 为了支持泛型,将第一级和第二级内存配置器封装起来 */ template<class T, class Alloc> class simple_alloc{//vector会持有一个该类型的对象,该对象的主要职责就是选用哪一级配置器 public: static T *allocate(size_t n) { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); } static T *allocate(void) { return (T*) Alloc::allocate(sizeof (T)); } static void deallocate(T *p, size_t n) { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); } static void deallocate(T *p) {Alloc::deallocate(p, sizeof (T)); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。