网站建设合同属于什么税目,ppt模板免费下载千图网,网络销售模式 自建网站,不收费的小说网站排名前言
空间配置器是 STL 六大组件之一#xff0c;它总是隐藏在容器的背后#xff0c;默默工作#xff0c;默默付出。本文为《STL 源码剖析》读书笔记#xff0c;主要讨论 SGI 版本空间的配置和释放#xff0c;对代码进行解读时会改变一些写法#xff0c;使其更易于阅读。…前言
空间配置器是 STL 六大组件之一它总是隐藏在容器的背后默默工作默默付出。本文为《STL 源码剖析》读书笔记主要讨论 SGI 版本空间的配置和释放对代码进行解读时会改变一些写法使其更易于阅读。
对象构造前的空间配置和对象析构后的空间释放由 stl_alloc.h 负责SGI 对此的设计哲学如下
向系统堆申请空间考虑多线程状态本文不考虑多线程情况考虑内存不足时的应变措施考虑小块内存过多造成的内存碎片问题
一级配置器
一级配置器并没有什么特殊的地方就是调用 malloc() 和 free() 申请和释放内存。
__malloc_alloc_template 源码
#if 0
# include new
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# include iostream.h
# define __THROW_BAD_ALLOC cerr out of memory endl; exit(1)
#endiftemplate int inst
class __malloc_alloc_template {private:static void *oom_malloc(size_t);static void *oom_realloc(void *, size_t);#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUGstatic void (* __malloc_alloc_oom_handler)();
#endifpublic:static void * allocate(size_t n)
{void *result malloc(n);if (0 result) result 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 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);
}};// malloc_alloc out-of-memory handling#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template int inst
void (* __malloc_alloc_templateinst::__malloc_alloc_oom_handler)() 0;
#endiftemplate int inst
void * __malloc_alloc_templateinst::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_BAD_ALLOC; }(*my_malloc_handler)();result malloc(n);if (result) return(result);}
}template int inst
void * __malloc_alloc_templateinst::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_BAD_ALLOC; }(*my_malloc_handler)();result realloc(p, n);if (result) return(result);}
}typedef __malloc_alloc_template0 malloc_alloc;oom 什么是 oomout of member 申请内存时如果没有空闲的物理内存那么内核就会开始进行回收内存的工作。如果内存回收后空闲的物理内存仍然无法满足此次物理内存的申请那么内核就会触发 OOM Out of Memory机制。
OOM 机制会根据算法选择一个占用物理内存较高的进程然后将其杀死以便释放内存资源如果物理内存依然不足OOM 会继续杀死占用物理内存较高的进程直到释放足够的内存。 SGI 中的 __malloc_alloc_oom_handler 操作又是什么 __malloc_alloc_oom_handler 指向内存不足时的处理函数是 SGI 模仿 C 的 set_new_handler因为没有使用 ::operator new 来分配内存所以不能直接使用 set_new_handler。
一个设计良好的 new_handler 函数做以下事情
让更多内存可以被使用安装另一个 new_handler卸载 new_handler抛出 bad_alloc不返回
SGI 中内存不足时调用 oom_malloc() 和 oom_realloc()在它们内部不断调用「内存不足处理函数」期望在某次调用后就得到了足够的内存然后返回。但如果「内存不足处理函数」并没有被客户端设定便会调用 __THROW_BAD_ALLOC丢出异常信息并终止进程。
内存不足时的处理操作
// 此处的条件编译一定会执行 elif 部分
// 最后尽力了也申请不到内存时就打印错误语句结束程序
#if 0
# include new
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# include iostream.h
# define __THROW_BAD_ALLOC cerr out of memory endl; exit(1)
#endif// 成员变量指向内存不足时的处理函数初始值为空
static void (* __malloc_alloc_oom_handler)();// 参数为新设置的内存不足处理函数
// 返回值为旧的内存不足处理函数
static auto set_malloc_handler(void (*f)()) - void (*)() {void (* old)() __malloc_alloc_oom_handler;__malloc_alloc_oom_handler f;return(old);
}// 该非类型模板参数没有用处
template int inst
void * __malloc_alloc_templateinst::oom_malloc(size_t n) {void (* my_malloc_handler)();void *result; // 指向申请到的内存while(true) {// 获取内存不足时的处理函数my_malloc_handler __malloc_alloc_oom_handler;if (0 my_malloc_handler) { // 如果没有设置处理函数终止进程__THROW_BAD_ALLOC; }(*my_malloc_handler)(); // 调用内存不足处理函数result malloc(n); // 再次尝试申请if (result ! nullptr) {return(result); // 申请成功返回}}
}template int inst
void * __malloc_alloc_templateinst::oom_realloc(void *p, size_t n) {void (* my_malloc_handler)();void *result;while(true) {// 获取内存不足时的处理函数my_malloc_handler __malloc_alloc_oom_handler;if (0 my_malloc_handler) { // 如果没有设置处理函数终止进程__THROW_BAD_ALLOC; }(*my_malloc_handler)(); // 调用内存不足处理函数result realloc(p, n); // 再次尝试申请if (result ! nullptr) {return(result); // 申请成功返回}}
}申请内存
一级配置器申请内存直接调用 malloc() 和 realloc() 函数。
static void * allocate(size_t n) {void *result malloc(n);if (0 result) {result oom_malloc(n); // 申请失败时调用 oom_malloc}return result;
}static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) {void * result realloc(p, new_sz);if (0 result) {result oom_realloc(p, new_sz); // 申请失败时调用 oom_realloc}return result;
}释放内存
一级配置器释放内存直接调用 free() 函数。
// 第二个参数没有作用
static void deallocate(void *p, size_t /* n */) {free(p);
}二级配置器
二级配置器就比一级配置器复杂的多大于 128 字节的申请调用一级配置器小于 128 字节的内存使用自由链表数组分配。整个二级配置器共享一个内存池内存不足时从内存池获取。提供函数从下层获取内存并向自由链表中填充内存。
自由链表如下提供以 8 为倍数的小块内存小块内存的头部 4/8 字节指向下一空闲节点。 __default_alloc_template 源码
enum {__ALIGN 8};
enum {__MAX_BYTES 128};
enum {__NFREELISTS __MAX_BYTES/__ALIGN};template bool threads, int inst
class __default_alloc_template {private:static size_t ROUND_UP(size_t bytes) {return (((bytes) __ALIGN - 1) ~(__ALIGN - 1));}
private:union obj {union obj * free_list_link;char client_data[1]; /* The client sees this. */};
private:static obj * volatile free_list[__NFREELISTS]; static size_t FREELIST_INDEX(size_t bytes) {return (((bytes) __ALIGN-1)/__ALIGN - 1);}static void *refill(size_t n);static char *chunk_alloc(size_t size, int nobjs);// Chunk allocation state.static char *start_free;static char *end_free;static size_t heap_size;public:/* n must be 0 */static void * allocate(size_t n){obj * volatile * my_free_list;obj * result;if (n (size_t) __MAX_BYTES) {return(malloc_alloc::allocate(n));}my_free_list free_list FREELIST_INDEX(n);result *my_free_list;if (result 0) {void *r refill(ROUND_UP(n));return r;}*my_free_list result - free_list_link;return (result);}/* p may not be 0 */static void deallocate(void *p, size_t n){obj *q (obj *)p;obj * volatile * my_free_list;if (n (size_t) __MAX_BYTES) {malloc_alloc::deallocate(p, n);return;}my_free_list free_list FREELIST_INDEX(n);q - free_list_link *my_free_list;*my_free_list q;}static void* reallocate(void *p, size_t old_sz, size_t new_sz){void * result;size_t copy_sz;if (old_sz (size_t) __MAX_BYTES new_sz (size_t) __MAX_BYTES) {return(realloc(p, new_sz));}if (ROUND_UP(old_sz) ROUND_UP(new_sz)) return(p);result allocate(new_sz);copy_sz new_sz old_sz? old_sz : new_sz;memcpy(result, p, copy_sz);deallocate(p, old_sz);return(result);}} ;template bool threads, int inst
char*
__default_alloc_templatethreads, inst::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 {size_t bytes_to_get 2 * total_bytes ROUND_UP(heap_size 4);// Try to make use of the left-over piece.if (bytes_left 0) {obj * __VOLATILE * my_free_list free_list FREELIST_INDEX(bytes_left);((obj *)start_free) - free_list_link *my_free_list;*my_free_list (obj *)start_free;}start_free (char *)malloc(bytes_to_get);if (0 start_free) {int i;obj * __VOLATILE * my_free_list, *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 __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;return(chunk_alloc(size, nobjs));// Any leftover piece will eventually make it to the// right free list.}}end_free 0; // In case of exception.start_free (char *)malloc_alloc::allocate(bytes_to_get);// This should either throw an// exception or remedy the situation. Thus we assume it// succeeded.}heap_size bytes_to_get;end_free start_free bytes_to_get;return(chunk_alloc(size, nobjs));}
}template bool threads, int inst
void* __default_alloc_templatethreads, inst::refill(size_t n)
{int nobjs 20;char * chunk chunk_alloc(n, nobjs);obj * volatile * my_free_list;obj * result;obj * current_obj, * next_obj;int i;if (1 nobjs) return(chunk);my_free_list free_list FREELIST_INDEX(n);/* Build free list in chunk */result (obj *)chunk;*my_free_list next_obj (obj *)(chunk n);for (i 1; ; i) {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);
}template bool threads, int inst
char *__default_alloc_templatethreads, inst::start_free 0;template bool threads, int inst
char *__default_alloc_templatethreads, inst::end_free 0;template bool threads, int inst
size_t __default_alloc_templatethreads, inst::heap_size 0;template bool threads, int inst
__default_alloc_templatethreads, inst::obj * __VOLATILE
__default_alloc_templatethreads, inst ::free_list[__NFREELISTS]
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };成员变量
enum {__ALIGN 8}; // 对齐数
enum {__MAX_BYTES 128}; // 可以申请的最大字节数
enum {__NFREELISTS __MAX_BYTES/__ALIGN}; // 自由链表个数static obj * volatile free_list[__NFREELISTS]; // 自由链表数组
static char *start_free; // 内存池空间起始位置
static char *end_free; // 内存池空间结束位置
static size_t heap_size; // 多开辟的堆大小还有一个比较特殊的成员自由链表的节点结构。
该联合体从第一个字段看它可以被视为一个指针指向下一节点。从第二个字段看它可以被视为一个指针指向实际的数据空间。
实际上该联合体并没有实际的作用只是为了便于理解。申请的一块内存在没被使用的时候可以用其头部 4/8 字节指向下一空闲节点不用维护另外的指针。
union obj {union obj * free_list_link;char client_data[1]; /* The client sees this. */
};工具部分
这部分提供内存对齐获取在自由链表数组中下标的函数。
因为自由链表中提供以 8 为倍数的小块内存因此需要将申请的内存对齐为 8 的倍数。
static size_t ROUND_UP(size_t bytes) {// (bytes) __ALIGN - 1 保证向对齐数进一位// ~(__ALIGN - 1) 去掉低位的 1return (((bytes) __ALIGN - 1) ~(__ALIGN - 1));
}同时也需要知道对应大小在自由链表数组中的下标以边获取内存和归还内存。
static size_t FREELIST_INDEX(size_t bytes) {// - 1 因为数组的下标从零开始// 等于 ROUND_UP(bytes) / _ALIGN - 1// 因为低位的数在除对齐数后没有影响return (((bytes) __ALIGN - 1) / __ALIGN - 1);
}申请内存
申请内存时首先判断大小大于 128 字节就调用一级配置器小于 128 字节就去自由链表中获取自由链表中没有内存就调用 refill() 填充内存。
static void * allocate(size_t n) {obj * volatile * my_free_list; obj * result; // 带回申请的内存// 大于 128 字节调用一级配置器if (n (size_t) __MAX_BYTES) {return(malloc_alloc::allocate(n));}// 找到对应大小的自由链表my_free_list free_list FREELIST_INDEX(n);result *my_free_list;if (result 0) {// 自由链表中没有内存可用为其填充内存void *r refill(ROUND_UP(n));return r;}// 取出一个节点调整 free_list 指向下一节点*my_free_list result - free_list_link;return (result);
}释放内存
释放时同样需要先判断内存大小大于 128 字节调用一级配置器释放小于 128 字节还给自由链表。
// p 为要释放的首地址n 为对象的大小
static void deallocate(void *p, size_t n) {obj *q (obj *)p;obj * volatile * my_free_list;// 大于 128 字节调用一级配置器if (n (size_t) __MAX_BYTES) {malloc_alloc::deallocate(p, n);return;}// 找到要插入的位置my_free_list free_list FREELIST_INDEX(n);// 将节点头插进去q - free_list_link *my_free_list;*my_free_list q;
}填充自由链表
当申请内存时发现自由链表中没有可用内存后就调用 refill()。refill() 的作用是为指定自由链表填充内存新的内存从内存池中获取默认情况下是填充 20 个节点但万一内存池中内存不足获取的节点可能小于 20 个。
template bool threads, int inst
void* __default_alloc_templatethreads, inst::refill(size_t n) {int nobjs 20; // 默认填充的个数// 从内存池获取内存nobjs 为引用传参带回实际申请到的个数char * chunk chunk_alloc(n, nobjs);obj * volatile * my_free_list;obj * result; // 返回使用的节点obj * current_obj, * next_obj;int i; // 只申请到一个节点将该节点直接返回不用向 free_list 中新增节点if (1 nobjs) {return(chunk);}// 调整 my_free_list 指向指向要添加节点的自由链表my_free_list free_list FREELIST_INDEX(n);// 需要将多余的节点插入到自由链表中// 获取第一个节点后续返回使用result (obj *)chunk;// n 指向第二个节点*my_free_list (obj *)(chunk n);next_obj (obj *)(chunk n);for (i 1; ; i) {// 分别指向当前节点、下一节点current_obj next_obj;// (char *)next_obj n 取一个节点的大小next_obj (obj *)((char *)next_obj n);// 一共申请了 nobjs 个节点需要插入 n - 1 个if (nobjs - 1 i) {// 将最后一个插入的节点置空current_obj - free_list_link 0;break;} else {// 采用尾插的方式current_obj - free_list_link next_obj;}}return(result);
}内存池
chunk_alloc() 首先检查内存池中是否有内存可用如果没有就尝试调用 malloc() 申请内存申请失败就去更大节点的自由链表中寻找内存。如果经过上述艰难的过程还是没有获取到内存的话就会调用一级配置器祈祷「内存不足处理函数」有所作用。
template bool threads, int inst
char* __default_alloc_templatethreads, inst::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; // 将 start 向后移表示内存已被使用return(result);} else if (bytes_left size) {// 内存池剩余空间不能满足要求但足够一个以上的节点nobjs bytes_left/size; // 能带回的节点个数total_bytes size * nobjs; // 申请到的字节数result start_free;start_free total_bytes; // 调整 startreturn(result);} else {// 内存池剩余空间连一个节点也不能满足// 申请成功后后取走 total_bytes 字节剩余部分留在内存池size_t bytes_to_get 2 * total_bytes ROUND_UP(heap_size 4);if (bytes_left 0) {// 内存池中还有剩余内存把它分配到合适的自由链表中// 申请是 8 的倍数使用也是 8 的倍数因此可以找到合适的位置obj * volatile * my_free_list free_list FREELIST_INDEX(bytes_left);((obj *)start_free) - free_list_link *my_free_list;*my_free_list (obj *)start_free;}// 调用 malloc 向堆申请内存start_free (char *)malloc(bytes_to_get);if (0 start_free) {// 申请内存失败int i;obj * volatile * my_free_list, *p;for (i size; i __MAX_BYTES; i __ALIGN) {// 检查配有更大节点的自由链表是否有空间可用// 例如 32 字节自由链表没有内存可用可以去 40、48 等自由链表查看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; // 调整内存池大小return(chunk_alloc(size, nobjs)); // 此时已经有内存了递归调用自己获取}}// 此时内存池没有内存malloc 失败也没有更大的可用节点// 尝试调用一级配置器看内存不足处理函数是否有办法end_free 0;start_free (char *)malloc_alloc::allocate(bytes_to_get);} // end of if (0 start_free)heap_size bytes_to_get; // 随着次数而增大不太理解含义end_free start_free bytes_to_get; // 调整内存池大小return(chunk_alloc(size, nobjs)); // 此时已经有内存了递归调用自己获取} // end of if (bytes_left total_bytes)
}
