内存分配器

内存分配器（Memory Allocator）负责内存分配与管理。内存分配器是所有容器的基础，它总是隐藏在容器背后工作，因此内存分配器对实现者非常重要，而对应用者几乎可以忽略。内存分配器分为两级，第一级分配器直接调用C函数分配和释放内存，第二级分配器则采用内存池来管理内存。如果申请的内存块足够大，那么启动第一级分配器，否则启动第二级分配器。这种设计的优点是可以快速分配和释放小块内存，同时避免内存碎片；缺点是内存池的生命周期比较长，并且很难显式释放。

第一级分配器只是简单的调用malloc()、realloc()和free()来分配、重新分配和释放内存。

第二级分配器需要维护16个空闲块链表和一个内存池。每个链表中的空闲块的大小都是固定的，假定默认内存齐数为n，各个链码空闲块大小则依次为n、2n、3n、4n、5n、6n、7n、8n、9n、10n、11n、12n、13n、14n、15n、16n。内存池由两个指针来描述，free_start记录起始地址，free_end记录结束地址。另外两个变量heap_size和used_size分别纪录堆的大小和已用内存大小。

图 1‑1第二级分配器

一结构定义

由于内存分配器的所有变量都被定义为静态成员变量，因此所有对象都是同一个内存分配器。为了解决某些应用场景下需要创建多个不同的内存分配器问题，借鉴了SGI STL的实现技巧，增加了一个非类型参数inst。不同inst参数的内存分配器虽然在功能上完全一样，但会被认为是不同的类型，从而达到创建多个内存分配器的目的。一个典型的应用场景就是保证标准库容器的线程安全。虽然也通过线程同步机制解决标准库容器的线程安全问题，但是使用非类型参数显然更简洁和高效。

为了维护一个链表，每一个节点都需要额外的指针来指向下一个节点。为了避免这种额外的内存开销，这里将节点定义为联合体，既可以将其视为指针也可以将其视为内存块来使用。

template <int inst>
class allocator_base
{
private:union free_chunk_node{free_chunk_node* next;char             buffer[1];};
private:static constexpr size_t align = 8;static constexpr size_t max_bytes = align << 4;static constexpr size_t free_list_size = 16;static constexpr size_t chunk_count = 16;static constexpr size_t heap_threshold = (max_bytes * chunk_count) << 5;static size_t           heap_size;static size_t           used_size;static char*            free_start;static char*            free_end;static void*            memory_list;static free_chunk_node* free_list[free_list_size];
};

二向系统申请内存

由于向系统申请内存空间是有额外负担的，并且申请的内存空间越小，这种额外负担的比例就越大。为了减少不必要的开销，内存分配器所采取的内存分配策略如下：初始阶段，每次向系统申请的内存大小为所需内存大小的两倍；当内存总容量足够大的时候，每次按照总容量的1/16递增；如果系统无法提供足够的内存时，请求空间大小减半；若仍无法申请成功，则再循环上述过程，直到无法满足所需大小，分配失败。

char* chunk_alloc(size_t align_bytes, size_t& count)
{char* result = nullptr;size_t memory_size;size_t total_bytes = align_bytes * count;if (heap_size < heap_threshold)memory_size = total_bytes << 1;elsememory_size = (heap_size >> 7) << 3;while (memory_size >= total_bytes){void* p = malloc(memory_size + sizeof(void*));// std::cout << "malloc: ";// std::cout << std::hex << std::setiosflags(std::ios::showbase);// std::cout << reinterpret_cast<size_t>(p) << std::endl;if (p != nullptr){result = reinterpret_cast<char*>(reinterpret_cast<size_t>(p) + sizeof(void*));free_start = result + total_bytes;free_end = result + memory_size;heap_size += memory_size;*reinterpret_cast<void**>(p) = memory_list;memory_list = reinterpret_cast<void**>(p);break;}memory_size >>= 1;}if (result == nullptr){for (size_t size = align_bytes; size <= max_bytes; size += align){free_chunk_node** current_list = reinterpret_cast<free_chunk_node**>(get_free_list(size));if (*current_list != nullptr){count = 1;result = (*current_list)->buffer;free_start = result + align_bytes;free_end = result + size;break;}}}return result;
}

内存池向系统申请的内存空间，在使用过程中会被划分为更小的内存块，而这些小内存块的使用和归还几乎是随机的。如果试图对这些小内存块进行合并和释放，其高昂的代价会大幅降低内存池的性能。但在内存池的已用内存大小为0时，释放内存是安全的。内存分配器维护一个指针链表，用于内存空间的统一释放。

三分配内存

当所需内存块大于16n时，使用第一级分配器进行内存分配，否则使用第二级别分配器，具体步骤如下：

申请内存的大小上调至n的倍数，根据所需内存块的大小查找对应的空闲链表；
如果空闲链表中有可用的内存块，则直接返回此空闲块，并从空闲链表中删除该块，否则继续下面的步骤；
计算内存池中所剩空间的大小，如果足以分配16个内存块，则从中取出16个内存块，调整内存池起始地址，返回第一个内存块，并将剩余的15个块并入空闲链表，否则继续下面的步骤；
如果剩余空间足以分配至少1个内存块，则从中取出尽可能多的内存块，调整内存池起始地址，返回第一个内存块，并将剩余的内存块并入空闲链表，否则继续下面的步骤；
如果内存池中还有一些内存，则将剩余空间并入其对应大小的空闲链表中；
向系统申请一个较大的内存块，如果申请成功，返回第一个内存块，调整内存池起始地址，否则继续下面的步骤；
遍历空闲链表，如果存在更大的空闲内存块，则从空闲链表中删除该块，返回该块首地址，并将剩余的部分内存交给内存池管理，否则分配失败。

void* arw_allocate(size_t size)
{if (size > max_bytes){void* result = malloc(size);if (result == nullptr)throw std::bad_alloc();return result;}else{char* result = nullptr;size_t count = chunk_count;free_chunk_node** current_list = reinterpret_cast<free_chunk_node**>(get_free_list(size));if (*current_list != nullptr){result = (*current_list)->buffer;*current_list = (*current_list)->next;}else{size_t align_bytes = round_up(size);size_t total_bytes = align_bytes * count;size_t free_bytes = free_end - free_start;if (free_bytes >= total_bytes){result = free_start;free_start += total_bytes;}else if (free_bytes >= align_bytes){count = free_bytes / align_bytes;total_bytes = align_bytes * count;result = free_start;free_start += total_bytes;}else{if (free_bytes > 0){free_chunk_node** free_list_left = reinterpret_cast<free_chunk_node**>(get_free_list(free_bytes));reinterpret_cast<free_chunk_node*>(free_start)->next = *free_list_left;*free_list_left = reinterpret_cast<free_chunk_node*>(free_start);free_start = free_end;}result = chunk_alloc(align_bytes, count);}if (result != nullptr && count > 1){char *cur, *next = result + align_bytes;*current_list = reinterpret_cast<free_chunk_node*>(next);for (size_t i = 2; i < count; ++i){cur = next;next += align_bytes;reinterpret_cast<free_chunk_node*>(cur)->next = reinterpret_cast<free_chunk_node*>(next);}reinterpret_cast<free_chunk_node*>(next)->next = nullptr;}}if (result != nullptr)used_size += size;elsethrow std::bad_alloc();return reinterpret_cast<void*>(result);}
}

四释放内存

当释放内存块大于16n时，使用free()释放内存，否则将该内存块归还给空闲块链表，供以后再次使用。

void arw_deallocate(void* p, size_t size)
{if (size > max_bytes){free(p);}else{free_chunk_node** current_list = reinterpret_cast<free_chunk_node**>(get_free_list(size));reinterpret_cast<free_chunk_node*>(p)->next = *current_list;*current_list = reinterpret_cast<free_chunk_node*>(p);used_size -= size;}
}

五重新分配内存

当所需内存块大于16n时，使用realloc()重新分配内存，否则重新分配一块新内存，并将原有数据拷贝到新内存中，并删除原内存。

void* arw_reallocate(void* p, size_t old_size, size_t new_size)
{void* result = nullptr;size_t copy_size;if (old_size > max_bytes && new_size > max_bytes){result = realloc(p, new_size);}if (round_up(old_size) == round_up(new_size)){result = p;used_size -= old_size;used_size += new_size;}else{result = arw_allocate(new_size);if (result == nullptr){copy_size = new_size > old_size ? old_size : new_size;std::memcpy(result, p, copy_size);arw_deallocate(p, old_size);}}if (result == nullptr)throw std::bad_alloc();return result;
}

六释放内存池

对于第二级分配器而言，arw_deallocate()只是将内存块归还给空闲块链表，并没有真正释放。在使用过程中，内存池大小只会增大而不会减小，这是为了追求效率所采用的内存管理机制所决定的。但在已用内存大小为0时（如：进程结束前），可以安全地释放内存池。

void release(void)
{if (used_size != 0)return;while (memory_list != nullptr){void* next = *reinterpret_cast<void**>(memory_list);// std::cout << "free: ";// std::cout << std::hex << std::setiosflags(std::ios::showbase);// std::cout << reinterpret_cast<size_t>(memory_list) << std::endl;free(memory_list);memory_list = next;}heap_size = 0;used_size = 0;
}