C++ allocation related

Posted by chunyang on March 27, 2019
TAGS: #cpp

简介

本文主要介绍 STL 中基础的内存分配的相关知识。C/CPP 初学者对于内存分配基本就是(malloc/free, new/delete)。 这些可以解决绝大部分场景下的内存分配,但是对于频繁的内存申请和释放,小内存变量的申请,容易造成内存 的碎片,而且内存的申请和释放过于频繁也会影响到效率。STL 中的内存分配有两种策略:

  • 默认的 malloc/free allocator
  • 带 freelist 的 allocator:
    • 当内存申请超过 _MAX_BYTES 时蜕化为 mallocfree
    • 当申请小内存时,会使用 freelist 的形式来申请和管理

对外暴露主要是如下 3 个接口:

  • static void* allocate(size_t __n)
  • static void deallocate(void* __p, size_t __n)
  • static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)

默认内存分配器

  • __malloc_alloc_template
  • malloc_alloc: tempalte 模板具化
  • simple_alloc: _Tp_Alloc 模板
  • debug_alloc: _Tp_Alloc 模板
  • __malloc_alloc_oom_handler: 当出现内存不足时,程序会尝试执行,然后重新分配内存;没有定义的话, 默认行为就是退出程序(C:exit, Cpp: 抛出异常)
    • static void* _S_oom_malloc(size_t)
    • static void* _S_oom_realloc(void*, size_t)

支持 freelist

  • 默认分配内存超过 _MAX_BYTES=128 时,会直接使用 malloc/free
  • 默认使用 16 个 freelist
    • 8, 16, 32, …, 128 bytes: 16 个链表
  • 默认对齐是 byte(8 bits)

  • __default_alloc_template
  • alloc
  • single_client_alloc

freelist

freelist 是用下面这个 Union 结构管理起来的:

enum {_NFREELISTS = 16};

union _Obj {
    union _Obj* _M_free_list_link;
    char _M_client_data[1];    /* The client sees this. */
};

static _Obj* _S_free_list[_NFREELISTS];

类似一个单链表,内部会分配一个数组来管理每一个 list 的当前 free 的位置,如果没有可用的位置,那么这个 值会是 0。涉及内存分配有 2 个函数:

  • static void* _S_refill(size_t __n)
  • static char* _S_chunk_alloc(size_t __size, int& __nobjs)
    • __nobjs 是个引用,函数内部会去修改这个值

_S_refill

默认一次会调用 _S_chunk_alloc 分配 20 对象:

  • 如果空间不足,只返回了一个对象,将这部分内存直接返回
  • 如果返回超过了一个,那么会将这些 chunks 构造成一个 list

一旦空间返回给用户,这部分内存是不受链表结构控制,所以可以自由的 deallocatereallocate。但是 在 deallocate 时可以将这些内存重新放入单链表中。

_S_chunk_alloc

Chunk allocation 的状态信息:所有的初值都是 0

  • _S_start_free: 当前 heap free 的开始
  • _S_end_free: 当前 heap free 的结束
  • _S_heap_size: 当前 heap 的大小

分配内存的具体流程如下:

  • 如果 heap 中内存足够分配 20 个,则更改状态信息,返回指针
  • 如果 heap 中内存足够分配 >= 1 个,则更改状态信息,返回指针,修改 __nobjs
  • 尝试申请内存 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
    • 如果 bytes_left = _S_end_free - _S_start_free 不为0,则将他们放到对应的 freelist 中
    • 如果空间不足,尝试释放 freelist 中的内存:从 __size -> _MAX_BYTES

reallocate

reallocate 时,需要注意一些 corner case。例如在同一个链表里面,则需要 reallocate

对外接口和 type traits

对外是以 allocator 形式对外暴露。allocator 主要使用 2 个 _Alloc

  • alloc
  • simple_client_alloc

这两个默认和带 freelist 的情况会被定义为不同的东西。

/* default case */
typedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;

/* with freelist */
/* 支持多线程 */

typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

/* 不支持多线程 */
typedef __default_alloc_template<false, 0> single_client_alloc;

Allocator 定义中只使用了 typedef alloc _Alloc,所以 single_client_alloc 当前并么有启用。

暴露的接口:

  • allocate(size_type __n, const void*=0)
  • deallocate(pointer __p, size_type __n)
  • construct(pointer __p, const _Tp& __val)
  • destroy(pointer __p)

allocator traits:

typedef size_t     size_type;
typedef ptrdiff_t  difference_type;
typedef _Tp*       pointer;
typedef const _Tp* const_pointer;
typedef _Tp&       reference;
typedef const _Tp& const_reference;
typedef _Tp        value_type;

本文完