C++ allocation related

• 简介
• 默认内存分配器
• 支持 freelist
• 对外接口和 type traits

简介

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

• 默认的 malloc/free allocator
• 带 freelist 的 allocator:
  • 当内存申请超过 _MAX_BYTES 时蜕化为 malloc 和 free
  • 当申请小内存时，会使用 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

一旦空间返回给用户，这部分内存是不受链表结构控制，所以可以自由的 deallocate 和 reallocate。但是 在 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;

本文完

• ← Previous Post
• Next Post →