1、这个项目要做什么

tcmalloc源代码

​ 当前项目是实现一个高并发的内存池，他的原型是 google 的一个开源项目 tcmalloc，全称为 Thread-Caching Malloc，即线程缓存的 malloc，实现了高效的多线程内存管理，用于替代系统的内存分配相关的函数（比如 malloc 和 free）。

​ 我们这个项目是把 tcmalloc 最核心的框架简化后拿出来，模拟实现出一个自己的高并发内存池，目的就是学习 tcamlloc 的精华，这种方式有点类似我们之前学习 STL 容器的方式。但是相比 STL 容器部分，tcmalloc 的代码量和复杂度上升了很多。

​ 另一方面 tcmalloc 是全球大厂 google 开源的，可以认为当时顶尖的 C++ 高手写出来的，他的知名度也是非常高的，不少公司都在用它，Go 语言直接用它做了自己内存分配器。所以很多程序员是熟悉这个项目的，那么有好处，也有坏处。好处就是把这个项目理解扎实了，会很受面试官的认可。坏处就是面试官可能也比较熟悉项目，对项目会问得比较深，比较细。如果你对项目掌握得不扎实，那么就容易碰钉子。

2、项目的要求

​ 这个项目会用到 C/C++、数据结构（链表、哈希桶）、操作系统内存管理、单例模式、多线程、互斥锁等等方面的知识。

Ⅱ. 什么是内存池

1、池化技术

​ 所谓 “池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要申请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效率。

​ 在计算机中，有很多使用“池”这种技术的地方，比如内存池、连接池、线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。

2、内存池

​ 内存池（Memory Pool）是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，而是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，而是返回内存池。当程序退出（或者特定时间）时，内存池才将之前申请的内存真正释放。

​ 内存池通常由两个部分组成：内存池管理器 和 内存块分配器，它们的作用如下所示：

1. 内存池管理器负责管理内存池的大小和内存块的分配和释放。
2. 内存块分配器则负责分配和释放内存块。

内存池的优点包括：

1. 提高内存分配效率：内存池可以减少频繁的内存分配和释放操作，从而提高内存分配效率。
2. 减少内存碎片：由于内存池中的内存块大小固定，因此不会产生内存碎片，从而减少了内存碎片的产生。
3. 提高程序性能：内存池可以减少动态内存分配和释放操作，从而减少了内存管理的开销，提高了程序性能。
4. 简化代码实现：内存池可以简化代码实现，减少了内存管理相关的代码量。

​ 尽管内存池可以提高程序性能和减少内存碎片的产生，但是它的缺点是需要预先分配一定数量的内存，因此会占用一定的内存空间。此外，如果内存池的大小预估不足，可能会导致内存不够用的情况。因此，在使用内存池时需要根据实际需求进行合理的配置。

​ 这里需要补充说明的是内存碎片分为 外碎片 和 内碎片。

• 外碎片是一些空闲的连续内存区域太小，这些内存空间不连续，以至于合计的内存足够，但是不能满足一些的内存分配申请需求；
• 内碎片 是由于一些对齐的需求，导致分配出去的空间中一些内存无法被利用。内碎片的问题，我们后面项目中就会看到。

3、malloc

​ **C/C++**中我们要动态申请内存都是通过 malloc 去申请内存，但是我们要知道，实际上并不是直接去堆中获取内存的，因为malloc 就是一个内存池。它相当于向操作系统预先申请了一块较大的内存空间，然后按需分配给程序用。当全部用完或者程序有大量的内存需求时，再根据实际需求向操作系统申请内存。

​ malloc 的实现方式有很多种，一般不同编译器平台用的都是不同的。比如 Windows 的 vs 系列用的微软自己写的一套，Linux gcc 用的 glibc 中的 ptmalloc。下面有几篇关于这块的文章，大概可以去简单看看了解一下，关于 ptmalloc，学完我们的项目以后，有兴趣大家可以去看看他的实现细节。

一文了解，Linux内存管理，malloc、free 实现原理

malloc()背后的实现原理——内存池

malloc的底层实现（ptmalloc）

Ⅲ. 设计一个定长内存池

1、定长内存池的概念

​ 我们知道申请内存使用的是 malloc，但 malloc 其实就是一个通用的大众货，什么场景下都可以用，但是什么场景下都可以用就意味着什么场景下都不会有很高的性能。下面我们就先来设计一个定长内存池做个开胃菜，当然这个定长内存池在我们后面的高并发内存池中也是有价值的，所以学习他目的有两层，先熟悉一下简单内存池是如何控制的，第二它会作为我们后面内存池的一个基础组件。

​ 定长内存池是一种内存池技术，它能够提高内存管理效率，同时避免了动态内存分配和释放造成的内存碎片问题。与传统的内存池不同，定长内存池中的内存块大小是固定的，即所有内存块的大小都相同。定长内存池 和 动态内存分配 是两种不同的内存分配方式，它们的主要区别如下：

1. 内存块大小：

   • 定长内存池中的内存块大小是固定的，而动态内存分配中的内存块大小可以是不同的。

2. 内存分配方式：

   • 定长内存池在程序启动时预先分配一定数量的内存块，并将这些内存块放入一个空闲内存块链表中。当程序需要分配内存时，从空闲内存块链表中取出一个内存块。而动态内存分配则是在程序运行时根据需要动态分配内存块。

3. 内存分配效率：

   • 由于定长内存池中的内存块大小固定，因此分配和释放内存块的效率比动态内存分配要高。动态内存分配需要进行内存分配和释放的操作，这些操作都需要耗费额外的时间和内存开销。

4. 内存碎片：

   • 由于定长内存池中的内存块大小固定，因此不存在内存碎片问题，而动态内存分配中会因为内存块大小不同，导致内存碎片的产生。

​ 总的来说，定长内存池适用于需要频繁分配和释放同种类型的内存块的场景，可以提高内存分配效率，减少内存碎片的产生，但需要预先分配一定数量的内存块。动态内存分配适用于需要灵活分配内存的场景，可以根据需要动态分配内存，但需要进行动态内存分配和释放的操作，会产生额外的时间和内存开销。

​ 它们的使用场景如下图所示：

2、实现

如何实现定长❓❓❓

​ 在实现定长内存池时要做到“定长”有很多种方法，比如我们可以使用非类型模板参数，使得在该内存池中申请到的对象的大小都是 N。

template<size_t N>
class fixed_size_pool
{};

​ 此外，定长内存池也叫做对象池，在创建对象池时，对象池可以根据传入的对象类型的大小来实现“定长”，因此我们可以通过使用模板参数来实现“定长”，比如创建定长内存池时传入的对象类型是 int，那么该内存池就只支持 4 字节大小内存的申请和释放。

template<class T>
class fixed_size_pool
{};

如何绕开 malloc 向堆直接申请空间❓❓❓

​ 既然是内存池，那么我们首先得向系统申请一块内存空间，然后对其进行管理。要想直接向堆申请内存空间，在 Windows 下，可以调用 VirtualAlloc 函数；在 Linux 下，可以调用 brk 或 mmap 函数。

  这里我们可以通过条件编译将对应平台下向堆申请内存的函数进行封装，此后我们就不必再关心当前所在平台，当我们需要直接向堆申请内存时直接调用我们封装后的 SystemAlloc 函数即可。

#ifdef _WIN32
	#include <Windows.h>
#else
	//...
#endif
 
//直接去堆上申请按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage<<13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

首先我们来思考一下，如何让一个指针在 32 位平台下解引用后能向后访问 4 个字节，在 64 位平台下解引用后能向后访问 8 个字节❓❓❓

  首先我们得知道，32 位平台下指针的大小是 4 个字节，64 位平台下指针的大小是 8 个字节。而指针指向数据的类型，决定了指针解引用后能向后访问的空间大小，因此我们这里需要的是一个指向指针的指针，这里使用二级指针就行了。

  当我们需要访问一个内存块的前 4/8 个字节时，我们可以将内存块的地址强转为二级指针，由于二级指针存储的是一级指针的地址，二级指针解引用能向后访问一个指针的大小，因此在 32 位平台下访问的就是 4 个字节，在 64 位平台下访问的就是 8 个字节，此时我们访问到了该内存块的前 4/8 个字节。

void*& get_next(void* ptr)
{
    // 函数返回值为void*&类型的引用，是因为这个函数返回的是指针的引用，即返回的是指针本身的地址，而不是指针所指向的对象的地址。
    // 这样做的好处是可以通过修改函数返回值来修改指针本身所指向的地址，从而实现对空闲链表的修改（头插和头删的需要）
    return (*(void**)ptr);
}

  需要注意的是，在释放对象时，我们应该显示调用该对象的析构函数清理该对象，因为该对象可能还管理着其他某些资源，如果不对其进行清理那么这些资源将无法被释放，就会导致内存泄漏。下面的 release() 会讲到！

下面我们设计的简易定长内存池包括以下几个方面：

1. 成员变量：

   private:
       size_t _left_size = 0;     // 定长内存池可用部分的剩余大小
       char* _memory = nullptr;   // 定长内存池可用部分的起始指针（使用char类型是为了切内存块的时候更精细方便）
       void* _freelist = nullptr; // 空闲链表的头指针

   1. _left_size：
      • 表示定长内存池可用部分的剩余大小，因为我们需要向内存池申请空间，那么内存池的空间是不断变小的，那么最后一次申请的时候，可能会出现越界的情况，所以我们可以使用一个整型变量来记录当前内存池的大小。
   2. _memory：
      • 表示定长内存池可用部分的起始指针，为什么是可用部分而不是整个内存池的起始位置呢，其实也是起始位置，但是这个起始位置是不断在变化的，这和我们下面的实现有关系，我们需要挪动 _memory 来表示申请了空间！
   3. _freelist：
   • 表示空闲链表的头指针，它用来链接未被使用的内存块，以方便我们在申请空间的时候无需向内存池拿取，并且达到反复利用的效果，提高利用率和效率！
   • 这里我们还要注意一个点，就是因为我们要使用模板，所以传进来的类型是什么我们并不知道，而 _freelist 是一个指针，32 位为 4 个字节，64 位为 8 个字节，但是如果传进来的类型是个结构体，大于我们指针可以指的范围，此时就不对了，有人可能说那么就用一个 T* 指针来指向结构体不就好了，但是我们要明白的是我们以后申请内存块，可能是不同大小的内存块，所以不一定是 T 大小结构的内存块，所以在链接自由链表的时候，我们统一规则，将内存块的开头，大小为一个指针的空间作为链接部分，所以要保证这个内存块的大小要超过 4/8 个字节，否则会出现越界，一般我们都会采取内存对其来防止这种小于 4/8 个字节的情况！连接方式如上图中所连接的方式是一样的，下面我们在讲成员函数的时候会说到！

2. 成员函数：

   • apply()

     1. 这个函数负责申请内存块，但是首先要判断一下自由链表是否有未使用的内存块，有的话直接拿来用即可；没有的话我们需要就得从内存池中拿，注意也是要先判断，判断申请的内存块是否超过了内存池的大小，当大块内存已经不足以切分出一个对象时，我们就应该调用我们封装的 SystemAlloc 函数，再次向堆申请一块内存空间，此时也要注意及时更新 _memory 指针的指向，以及 _leftbytes 的值。
     2. 若成功申请到了内存块，则使用 定位new 进行初始化，因为我们是先分配了堆空间，所以初始化一般都使用 定位new，以便将内存分配交给内存池管理器来管理。
     3. 而具体在实现如何从空闲链表中拿取这个内存块并不难，就是一个头删操作！而对于从内存池中拿取就需要配合 _memory 来移动，具体可以看下图：
     4. 另外还有一个就是当自由链表中拿取内存块的时候，我们之前规定了让内存块的前 4 个字节或前 8 个字节作为指针，存储后面内存块的起始地址。所以访问的时候需要一个二级指针或者用判断语句，这里使用二级指针的方式！

     // 向定长内存池申请一个T对象的空间
     T* apply()
     {
         T* obj = nullptr;
      
         // 1. 如果可以的话，直接从空闲链表中获取空闲的空间
         if (_freelist != nullptr)
         {
             // 就是一个链表头删的操作
             obj = (T*)_freelist;
             _freelist = get_next(_freelist);
             return obj;
         }
      
         // 2. 剩余内存不够一个对象大小时，则重新开大块空间
         int size = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T); // 防止申请空间不足一个指针的大小，要最少开辟一个指针大小的空间
         if (_left_size < size)
         {
             // 剩余内存不够一个对象大小时，则重新开大块空间
             _left_size = 128 * 1024;
             _memory = (char*)SystemAlloc(_left_size >> 13);
             if (_memory == nullptr)
                 throw std::bad_alloc(); // 申请空间失败的话就抛异常
         }
      
         // 3. 从内存池中取出一个对象的空间，然后处理一下指针和大小即可
         obj = (T*)_memory;
         _left_size -= size;
         _memory += size;
      
         // 4. 进行定位new操作调用对象的构造函数进行初始化，最后进行返回即可
         new(obj)T;
         return obj;
     }

   • release()

     1. 释放已经不想使用的内存块空间，防止内存块中一些数据的内存泄漏！

     2. 对于还回来的定长内存块，我们可以用空闲链表将其链接起来，但我们并不需要为其专门定义链式结构，我们可以让内存块的前 4 个字节或前 8 个字节作为指针，存储后面内存块的起始地址即可。因此在向空闲链表插入被释放的内存块时，先让该内存块的前 4 个字节或 8 个字节存储空闲链表中第一个内存块的地址（可存储的原因是它们已经是空闲的不被使用的，所以才能直接对它们的内存块进行操作），然后再让 _freeList 指向该内存块即可，也就是一个简单的链表头插操作。如下图所示：

     

     // 释放T对象的空间
     void release(T* obj)
     {
         // 1. 先调用对象的析构函数进行内部数据的释放
         obj->~T();
      
         // 2. 再进行空闲链表的头插操作
         get_next(obj) = _freelist;
         _freelist = obj;
     }

​ 空闲链表 FreeList 是一种常见的内存管理技术，主要用于管理动态内存分配的空闲内存块。空闲链表通常是一种链表结构，存储着当前未被使用的内存块，当需要分配内存时，可以从空闲链表中取出一个内存块进行使用，当需要释放内存时，将内存块放回空闲链表中。

​ 空闲链表的实现方式通常是在程序启动时，预先分配一定数量的内存块，并将这些内存块放入一个空闲内存块链表中。当程序需要分配内存时，从空闲内存块链表中取出一个内存块，当程序需要释放内存时，将内存块放回空闲内存块链表中。在使用空闲链表时，需要注意内存块的大小和对齐方式，以避免内存浪费和对齐问题。

优点：

1. 避免内存碎片：由于空闲链表中的内存块大小相同，因此不会产生内存碎片问题。
2. 提高内存分配效率：由于空闲链表中的内存块已经被预先分配，因此内存分配时无需再进行耗时的系统调用，可以提高内存分配效率。
3. 简单易用：空闲链表的实现相对简单，易于理解和使用。

缺点：

1. 内存浪费：由于空闲链表中的内存块大小是固定的，因此可能会出现内存浪费的问题，即内存块大小与应用程序需要的大小不匹配。
2. 内存池管理：由于空闲链表需要预先分配一定数量的内存块，因此需要对内存池进行管理，包括内存池大小、内存块大小、内存块对齐方式等。
3. 静态内存分配：空闲链表通常需要在程序启动时进行预先分配，因此不适用于需要动态分配内存的场景。

完整代码：

#pragma once
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
 
#ifdef _WIN32
#include <Windows.h>
#else
//...
#endif
 
//直接去堆上申请按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // linux下brk mmap等
#endif
    if (ptr == nullptr)
        throw std::bad_alloc();
    return ptr;
}
 
template <class T>
class fixed_size_pool
{
private:
    size_t _left_size = 0;     // 定长内存池可用部分的剩余大小
    char* _memory = nullptr;   // 定长内存池可用部分的起始指针（使用char类型是为了切内存块的时候更精细方便）
    void* _freelist = nullptr; // 空闲链表的头指针
public:
    // 向定长内存池申请一个T对象的空间
    T* apply()
    {
        T* obj = nullptr;
 
        // 1. 如果可以的话，直接从空闲链表中获取空闲的空间
        if (_freelist != nullptr)
        {
            // 就是一个链表头删的操作
            obj = (T*)_freelist;
            _freelist = get_next(_freelist);
            return obj;
        }
 
        // 2. 剩余内存不够一个对象大小时，则重新开大块空间
        int size = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T); // 防止申请空间不足一个指针的大小，要最少开辟一个指针大小的空间
        if (_left_size < size)
        {
            // 剩余内存不够一个对象大小时，则重新开大块空间
            _left_size = 128 * 1024;
            _memory = (char*)SystemAlloc(_left_size >> 13);
            if (_memory == nullptr)
                throw std::bad_alloc(); // 申请空间失败的话就抛异常
        }
 
        // 3. 从内存池中取出一个对象的空间，然后处理一下指针和大小即可
        obj = (T*)_memory;
        _left_size -= size;
        _memory += size;
 
        // 4. 进行定位new操作调用对象的构造函数进行初始化，最后进行返回即可
        new(obj)T;
        return obj;
    }
 
    // 释放T对象的空间
    void release(T* obj)
    {
        // 1. 先调用对象的析构函数进行内部数据的释放
        obj->~T();
 
        // 2. 再进行空闲链表的头插操作
        get_next(obj) = _freelist;
        _freelist = obj;
    }
 
    void*& get_next(void* ptr)
    {
        // 函数返回值为void*&类型的引用，是因为这个函数返回的是指针的引用，即返回的是指针本身的地址，而不是指针所指向的对象的地址。
        // 这样做的好处是可以通过修改函数返回值来修改指针本身所指向的地址，从而实现对空闲链表的修改（头插和头删的需要）
        return (*(void**)ptr);
    }
};

3、性能测试

// 测试数据
struct TreeNode
{
    int _val;
    TreeNode* _left;
    TreeNode* _right;
    TreeNode()
        : _val(0)
        , _left(nullptr)
        , _right(nullptr)
    {}
};
 
void TestObjectPool()
{
    // 申请释放的轮次
    const size_t Rounds = 5;
 
    // 每轮申请释放多少次
    const size_t N = 100000;
 
    // 测试new和delete的速度
    std::vector<TreeNode*> v1;
    v1.reserve(N);
    size_t begin1 = clock();
    for (size_t j = 0; j < Rounds; ++j)
    {
        for (int i = 0; i < N; ++i)
            v1.push_back(new TreeNode);
 
        for (int i = 0; i < N; ++i)
            delete v1[i];
        v1.clear();
    }
    size_t end1 = clock();
 
    // 测试我们实现的内存池的速度
    std::vector<TreeNode*> v2;
    v2.reserve(N);
    fixed_size_pool<TreeNode> TNPool;
    size_t begin2 = clock();
    for (size_t j = 0; j < Rounds; ++j)
    {
        for (int i = 0; i < N; ++i)
            v2.push_back(TNPool.apply());
 
        for (int i = 0; i < N; ++i)
            TNPool.release(v2[i]);
        v2.clear();
    }
    size_t end2 = clock();
 
    cout << "new cost time:" << end1 - begin1 << endl;
    cout << "fixed_size_pool cost time:" << end2 - begin2 << endl;
}
 
// 运行结果：
// debug下：
new cost time:149
fixed_size_pool cost time:37
    
// release下：
new cost time:31
fixed_size_pool cost time:2

  在代码中，我们先用new申请若干个 TreeNode 对象，然后再用 delete 将这些对象再释放，通过 clock 函数得到整个过程消耗的时间。（new 和 delete 底层就是封装的 malloc 和 free）

  然后再重复该过程，只不过将其中的 new 和 delete 替换为定长内存池当中的 apply 和 release，此时再通过 clock 函数得到该过程消耗的时间。

​ 可以看到在这个过程中，定长内存池消耗的时间比 malloc/free 消耗的时间要短。这就是因为 malloc 是一个通用的内存池，而定长内存池是专门针对申请定长对象而设计的，因此在这种特殊场景下定长内存池的效率更高，正所谓 “尺有所短，寸有所长”。