C++动态内存分配与allocator

  c++  
-目录-

内存分配call stack

分配内存

Foo* p = new Foo(x);
//等同于
Foo* p = (Foo*)operator new(sizeof(Foo)); //分配空间 此处可重载,使之不调用全局的::operator new
new(p) Foo(x); //placement new 创建对象(初始化内存)
//等同于
::operator new(size_t);
//等同于
malloc(size_t);

释放内存

delete p;
//等同于
p->~Foo();//析构函数
operator delete(p); //此处可重载,使之不调用全局的::operator delete 
//等同于
::operator delete(void*);
//等同于
free(void*);

重载operator new

注意：

在重载operator new，第一个参数必须是size_t形式

在重载operator delete时，第一个参数必须是void*形式

例如：

class MyClass {
public:
    //operator new(int a)//出错，第一个参数必须是size_t
    void *operator new(size_t size) {
        cout << "MyClass new" << endl;
        return malloc(size);
    }

    void *operator new(size_t size, void* ptr) {
        cout << "MyClass new" << endl;
        return malloc(size);
    }

    void operator delete(void* p) {
        cout << "MyClass delete" << endl;
        free(p);
    }
};

内存池构建思路

GNU C++ pool_allocator 内存分配器

编译器在最终使用malloc时，分配的内存会在最终需求的上下有多余块，一方面是为了内存对齐，另一方面是为了调试时追踪。如下图，只有user use才是用户申请的空间。

----------
| cookie |
----------
| debug  |
| header |
----------
| user   |
| use    |
----------
| debug  |
| tail   |
----------
| padding|
----------
| cookie |
----------

内存分配器就要做到尽量减少多余空间的占用（减少cookie），减少调用malloc的次数。

思想就是内存池，实现就是预先分配大空间，大空间分成多个对象，对象间用链表相连（为了模拟离散空间）。此外，把每个池子面向的大小固定下来，比如8 16 24 32 40这样固定的值，超过最大固定值后交给malloc直接分配带cookie的块。概念图如下。

    8     ----    16     ----    24    ----    32    ----    MAX
    |
----------    ----------
| cookie |    | cookie |    
----------    ----------
| debug  |    | debug  |
| header |    | header |
----------    ----------
| user   |    | user   |
| use    |    | use    |    
----------    ----------    
| debug  |    | debug  |    
| tail   |    | tail   |    
----------    ----------    
| padding|    | padding|    
----------    ----------    
| cookie |    | cookie |    
----------    ----------    
    |        
----------
| cookie |
----------
| debug  |
| header |
----------
| user   |
| use    |
----------
| debug  |
| tail   |
----------
| padding|
----------
| cookie |
----------

此外，因为是使用连续空间切割，然后模拟链表之间可以使用embedded pointer节省一个指针，概念图如下：

---------------------
|next  | data       |
---------------------
---------------------
|next  | data       |
---------------------
---------------------
|      data         |
---------------------

这样每次分配出去后，当前指针指向下一个可用的块。回收时，直接将回收块的embedded pointer指向当前的，然后当前指针指向回收的就好了。不必专门清除。

在分配时，会根据需求大小查找free_list试图找到空闲的，若那个大小的没有空闲的块了，就会从池子里申请。若池子不够大，则申请一个较大的数值（round_up函数）作为池子，一部分用于当前空闲块的建立，一部分用于池子。

在回收时，pool_alloctor并不会真的还给系统，只是会返还给池子，只要程序在运行，这个池子就只会增加。

VC++ CRT malloc实现：SBH

malloc和std::alloctor的调用层次。

C++ Application
|  |     |    |
|  |     |  C++ Library(std::alloctor)
|  |     |    |
|  |   C++ primitives(new delete)
|  |          |
|  C Runtime CRT(malloc/free)
|             |    
OS API(VirtualAlloc)

VC++的malloc使用栈上小区块（Small Block Heap）内存分配器。思路类似于GNU C++的 pool_alloctor但细节处不同。

分为管理的部分和实际内存部分。

每个group管理一个段（32KB），32个group恰好管理32个内存段。也就是说每个group管理8个页。一个group是有64个链表的，第0个管理16B的，下一个管理32B，直到倒数第二个管理到1024B，而倒数第一个管理1024B以上的。因此，最初分配的8个页全部挂到最后一个链表上。

在分配时，和pool_alloctor相同的分大小管理造就了类似的分配回收逻辑。每次看看需求大小对应的链表中是否有空闲块，否则就去上一级要，然后还回去的时候并不还给上级，而是自己留着。就这样，最后一个链表上面挂着的大区块被下面小区块瓜分干净。

在回收时， 小区块会合并成大区块并挂到更高的链表上。最后，如果全部回收了就回到了一开始的一段8页全部挂到最后一个链表上的状态。

GNU内存分配器类别、原理和选用

每次分配

直接分配具体大小。会因为malloc cookie问题额外占用空间。

__gnu_cxx::new_alloctor

直接调用operator new 没有任何优化。这是所有容器默认的内存分配器。

pointer allocate(size_type __n, const void* = 0)
{ 
	if (__n > this->max_size())
  		std::__throw_bad_alloc();
	return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
}
void deallocate(pointer __p, size_type)
{ ::operator delete(__p); }

__gnu_cxx::malloc_alloctor

直接调用malloc 没有任何优化。

pointer allocate(size_type __n, const void* = 0)
{
	if (__n > this->max_size())
  		std::__throw_bad_alloc();
	pointer __ret = static_cast<_Tp*>(std::malloc(__n * sizeof(_Tp)));
    if (!__ret)
      std::__throw_bad_alloc();
    return __ret;
}
void deallocate(pointer __p, size_type)
{ std::free(static_cast<void*>(__p)); }

内存池

通过预先安排大空间，减少cookie占用。

__gnu_cxx::__pool_alloc

分级池子，同上节[内存分配器思路](#GNU C++ pool_allocator 内存分配器)。使用场景：小区块频繁分配。特点：内存不会还给系统，维持在峰值空间。

__gnu_cxx::bitmap_allocator

使用bitmap直接管理每块内存，一块内存的大小和数据对象的大小相同。

一个单元内由4部分组成，64个块和64个bit用于表示状态，还有已使用的块的大小（unsigned int）和整个单元的大小。每个块的大小是固定的（是一个数据对象的大小如int），每个块被映射到一个bit上。

一个单元的分布如下图

------------------------------------------------------------------------------
|整个单元的大小|已使用的block数|bit map(64bit)|block1|block2|block3|...|block64|
------------------------------------------------------------------------------

一个单元二进制如下所示。

     524=4B+2*4B+64*obj_size(assume 8) |             used blocks 0             |    bit map 2*32bit
|00000000 00000000 00000010 00001100|00000000 00000000 00000000 00000000|00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000|data block1|data block2|...|data block64|

上述图示是第一个单元的大小，第一个单元用完后，后面会成倍增加，第二个单元是128个，第三个是256…。对应的bitmap和总大小都会变。此外，不同于pool_allocator，不同obj_type不会使用同一个bitmap_allocator。每次请求新的类型会创建新的bitmap_allocator实例。

在释放时，是以一整个单元为单位的。在整个单元释放后（使用的区块数为0），整个单元的存入一个数组，作为一个entry。最多存64个entry，这个数组根据block数从小到大维护大小，超过64个后会把最大的还给系统。在下次需要内存时优先从这个数组中找。

这种释放思路不像pool_alloc那样始终不还，也不像new_alloc那样直接归还，做了一个defer的处理。

__gnu_cxx::__mt_alloc

多线程分配器，原理上是对pool_alloc的封装。多线程使用全局内存池，然后各个线程拥有自己的分级pool，各线程到自己的pool里拿内存。当各线程的pool需要内存时需要到全局内存池拿内存，此时原子操作从全局内存池拿内存。当全局内存池不够后，线程将直接从系统中拿内存，而不是请求扩容。

其他

__gnu_cxx::array_allocator 使用数组，而无需运行时使用动态内存。亦或者使用其他已经分配好的内存进行再分配。不会回收已经使用的内存。使用场景：一次性分配。已知需要多少空间，避免扩容。

pointer allocate(size_type __n, const void* = 0)
{
    if (_M_array == 0 || _M_used + __n > _M_array->size())
        std::__throw_bad_alloc();
    pointer __ret = _M_array->begin() + _M_used;
    //使用量_M_used恒加，使用过的内存不会再次使用
    _M_used += __n;
    return __ret;
}

void deallocate(pointer, size_type)
{ 
// Does nothing.
}
© 2019 - 2023 · YuYoung's Blog