史上最骚のSTL空间分配器(续)
Time: 2020-09-01 Tags: binaryLink: 史上最骚のSTL空间分配器(续)
内存池
从内存池中取空间给free list用,是chunk_alloc()的工作。
如果在内存池完全充足的情况下,chunk_alloc()会直接返回空间。
char *result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free;
if(bytes_left > total_bytes){ // memory pool is enough.
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);
}
重新调整nobjs,然后将能够返回的所有区块返回。
如果连一个区块都不能提供的话,则考虑向内存malloc一块,以补充内存池。
else{
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
并且需要malloc的size应该是total_bytes的两倍。
在开始malloc之前,先对内存池中的零头进行利用。调整free list。
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;
}
然后开始malloc。
start_free = (char *)malloc(bytes_to_get);
如果没有异常的话,可以将申请到的内存处理一下然后返回了。
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return (chunk_alloc(size, nobjs)); // adjust nobjs
如果对内存的申请不成功,即system heap已经耗尽,那么我们只能对我们现有的东西进行检视。
if (start_free == 0){
int i;
obj *volatile *my_free_list, *p;
for (i = size; i <= __MAX_BYTES;i+=__ALIGN){ // 搜寻适当的free list
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (p != 0){
*my_free_list = p->free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return (chunk_alloc(size, nobjs));
}
}
end_free = 0; // 山穷水尽
start_free = (char *)malloc_alloc::allocate(bytes_to_get); // 调用第一级配置器,赌一把。
}
代码
完整的chunk_alloc:
template <bool threads,int inst>
char *__default_alloc_template<threads,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){ // memory pool is enough.
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);
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 (start_free == 0){
int i;
obj *volatile *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 (p != 0){
*my_free_list = p->free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return (chunk_alloc(size, nobjs));
}
}
end_free = 0;
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return (chunk_alloc(size, nobjs));
}
}
测试
至此,一个史上最骚的内存池就这么诞生了。但是我们还是按照惯例来测试一下这个池子好不好使。第一次使用的时候以为是直接使用__default_alloc_template,
#include <vector>
...
vector<int,mystl::__default_alloc_template<0,0>> iv(ia,ia+5);
报错,报了一吨。而且是没法debug的那种。根本找不到错误在哪里。
后来找了个tinystl源码看了看,原来是需要给一层包装(allocator.h)才行。另外debug了一下,alloc.h有以下改动。
typedef __default_alloc_template<0, 0> alloc;
template<>
char *alloc::start_free = 0;
template<>
char *alloc::end_free = 0;
template<>
size_t alloc::heap_size = 0;
template<>
alloc::obj *volatile alloc::free_list[__NFREELISTS] =
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,};
包装用的头文件直接抄defalloc.h,然后将alloc加到模版声明中去即可。附allocator.h
#ifndef DEFALLOC_H
#define DEFALLOC_H
#include <new>
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include "alloc.h"
using namespace std;
namespace mystl{
template <class T,class Alloc = mystl::alloc>
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;
pointer allocate(size_type size){
return (pointer)Alloc::allocate((difference_type)size); // 需要将指针转换一下
}
void deallocate(pointer p){
Alloc::deallocate(p,0);
}
void deallocate(pointer p,size_type n){
Alloc::deallocate(p,n);
}
pointer address(reference x){
return (pointer) &x;
}
const_pointer const_address(const_reference x){
return (const_pointer) &x;
}
size_type init_page_size(){
return max(size_type(1),size_type(4096/sizeof(T)));
}
size_type max_size(){
return max(size_type(1),size_type(UINT_MAX/sizeof(T)));
}
}; // end of class allocator
template<>
class allocator<void>{
public:
typedef void* pointer;
};
} // end of namespace
#endif
然后就可以愉快地使用内存池啦。
// demo.cpp
#include <vector>
#include <iostream>
#include "allocator.h"
using namespace std;
int main(){
int ia[5] = {0,1,2,3,4};
unsigned int i;
unsigned int size;
vector<int,mystl::allocator<int>> iv(ia,ia+5);
size = iv.size();
for(i=0;i<size;i++){
cout<<iv[i]<<" ";
}
cout<<endl;
return 0;
}
# surager @ ubuntu in ~/MyTinySTL [9:01:25]
$ cd "/home/surager/MyTinySTL/" && g++ 'test.cpp' -o 'test' -Wall -g -O2 -static-libgcc -std=c++17 -fexec-charset=GBK && "/home/surager/MyTinySTL/"test
0 1 2 3 4
总结
对stl内存分配的学习虽然不是重点,但是对于源码的理解以及对内存分配的深入还是很有意义的。这个内存池不仅让我收获了源码的逻辑严谨性,而且让我知道了数据结构在内存中所占的比较重要的地位。
另外,这只是stl学习的第一步,还需要努力。