STL里的内存池实现
STL内存分配分为一级分配器和二级分配器，一级分配器就是采用malloc分配内存，二级分配器采用内存池。

二级分配器设计的非常巧妙，分别给8k，16k,..., 128k等比较小的内存片都维持一个空闲链表，每个链表的头节点由一个数组来维护。需要分配内存时从合适大小的链表中取一块下来。假设需要分配一块10K的内存，那么就找到最小的大于等于10k的块，也就是16K，从16K的空闲链表里取出一个用于分配。释放该块内存时，将内存节点归还给链表。
如果要分配的内存大于128K则直接调用一级分配器。
为了节省维持链表的开销，采用了一个union结构体，分配器使用union里的next指针来指向下一个节点，而用户则使用union的空指针来表示该节点的地址。

 

首先我们需要明确, 内存池的目的到底是什么?  首先你要知道的是, 我们每次使用new T来初始化类型T的时候, 其实发生了两步操作, 一个叫内存分配, 这一步使用的其实不是new而是operator new(也可以认为就是C语言中的malloc), 这一步是直接和操作系统打交道的, 操作系统可能需要经过相对繁琐的过程才能将一块指向空闲内存的指针返回给用户, 所以这也是new比较耗时的一部分, 而第二步就是使用构造函数初始化该内存, 这是我们比较熟悉的. 既然内存分配耗时, 那我们很容易想到的就是一次性分配一大块内存, 然后在用户需要的时候再划分其中一部分给用户, 这样的话, 一次分配, 多次使用, 自然而然提高了效率, 而用来管理这所谓的一大块内存的数据结构, 也就是今天我们要说的内存池. 另外一个好处在于, 频繁地使用new将导致系统内存空间碎片化严重, 容易导致的后果就是很难找到一块连续的大块内存, 空间利用率低.

 

那么我们先来看看, 内存池的整体结构 :

 

该内存池可以认为由上面的一个指针数组和下面的自由链表两部分组成, 指针数组中第一个指针指向的是存放内存大小为8bytes的节点串接而成的自由链表, 之后依次是内存而16bytes, 24bytes直到128bytes, 当然在图中我只画出了一个自由链表. 所以内存池的基本思路在于 :

1. 如果用户分配的内存大于128bytes, 直接用malloc, 否则的话找出适合的自由链表, 从其上摘下一个节点将其头指针返回给用户.

2. 释放过程则正好与分配相对应, 如果用户分配的内存大于128bytes, 直接用free, 否则找出适当的自由链表, 将指针所指的该段内存重新连接到自由链表中(注意此时并不返回给操作系统, 因为之后还可以再重复利用). 

 

这一部分的所对应的代码如下图 :

private:
    static const int Align = 8;
    static const int MaxBytes = 128;
    static const int NumberOfFreeLists = MaxBytes / Align;
    static const int NumberOfAddedNodesForEachTime = 20;

    union node {
        union node *next;
        char client[1];
    };

    static obj *freeLists[NumberOfFreeLists];

为了便于理解, 我对于源代码中的所以属性名都做了相应的改动, 唯一可能存在疑问的是这个node为什么可以用联合体?  这里我们需要搞清楚这么几点, 自由链表上保存的都是一个一个并未使用的节点, 此时我们为了将所有的node串接起来, 我们当然可以独立分配空间来实现这一功能, 如下图, 比较容易想到的做法可能是这样, 用一个结构体来维护指向真正要分配给用户的内存块以及下一个结构体. 但是这样做有两个缺点 :

1.首先它的每一个node都需要额外多出一个指针的空间来保存真正要分配给用户的内存块的地址

2. 其次在将该内存块分配出去之后, 还需要再处理掉该node对应的结构体.

 

在分析分配函数的代码之前, 我们先来看看几个辅助函数 :

private:
    static size_t ROUND_UP(size_t size) {
        return ((size + Align - 1) & ~(Align - 1));
    }

    static size_t FREELIST_INDEX(size_t size) {
        return (size + Align - 1) / Align - 1;
    }

这两个函数作用很简单, 第一个返回的是大于等于输入值的8的倍数, 第二个返回的是可以容纳输入值的最小的自由链表.

 

 

接下来就是内存池对外的接口, allocate函数的实现代码.

void* alloc::allocate(size_t size) {
    if (size > MaxBytes) {
        return malloc(size);
    }

    size_t index = FREELIST_INDEX(size);
    node* theMostSuitableNode = freeLists[index];
    if (theMostSuitableNode) {
        freeLists[index] = theMostSuitableNode->next;
        return theMostSuitableNode;
    }
    else {
        return refill(ROUND_UP(size));
    }
}

1. 正如我们前面所讲的, 当用户希望得到size大小的内存空间时候, 此时我们只需要找到能够容纳size的最小的自由链表, 因为自由链表中都是还未分配出去的空间, 如果自由链表中还存在节点的话, 直接将该节点分配出去即可, 也就是这里的theMostSuitableNode不为空的情况, 但此时我们要将数组中指向该自由链表的指针指向下一个Node, 因为这个Node已经分配出去了.

2. 另一方面, 如果自由链表中并没有可用的Node(这里有两种情况会导致没有可用的Node, 第一种是曾经分配过, 但是用光了, 第二种是这是该内存池初始化以来第一次使用这个大小的自由链表, 所以还未分配过空间), 我们直接使用refill函数来填充自由链表, 之所以要用ROUND_UP使得它成为8的倍数, 是因为处于效率原因我们可能会一次性分配不止1个Node(这里是20个), 所以这里的空间必须按照Node的大小来分配.

 

 

所以我们顺蔓摸瓜, 接着来看refill的实现代码.

void* alloc::refill(size_t size) {
    size_t num = NumberOfAddedNodesForEachTime;
    char* block = blockAlloc(size, num);
    node** currentFreeList = 0;
    node *curNode = 0, *nextNode = 0;

    if (num == 1) {
        return block;
    }
    else {
        currentFreeList = freeLists + FREELIST_INDEX(size);
        *currentFreeList = nextNode = reinterpret_cast<node*>(block + size);
        for (int i = 1;; ++i) {
            curNode = nextNode;
            nextNode = reinterpret_cast<node*>(reinterpret_cast<char*>(curNode) + size);
            if (num - 1 == i) {
                curNode->next = 0;
                break;
            }
            else {
                curNode->next = nextNode;
            }
        }
        return block;
    }
}

先解释一下第二行的blockAlloc, 这个函数的作用是去内存池中寻找size * num大小的空间然后划分给当前的自由链表(也就是currentFreeList), 因为一旦调用了refill说明该自由链表已经没有了可分配的Node, 所以我们这里考虑再分配的时候就直接分配了NumberOfAddedNodesForEachTime个(也就是20个). 但是要注意的话其实这里num传进去的是引用, 为什么传引用呢? 因为还有可能会出现内存池空间不够的情况, 此时如果内存池够1个Node但是不够20个的话, 就会将num设置为1, 说明此时只分配了1个Node空间. 所以可以看到第26行的判断中, 当num为1的时候, 直接将block返回给用户即可. 如果不是1的话, 再返回之前要先将剩下个节点串接在自由链表上. 这也就是那个for循环的作用.

 

当然在接触到blockAlloc之前, 我们先来看内存池的另外另个熟悉.

1 static char *startOfPool, *endOfPool;

这两个变量分别指向内存池所分配的空间中的起点和终点, 之前说道自由链表里面如果没有node了就到内存池中取, 其实就是从startOfPool开始的位置划出所需要的空间.

 

最后直接和内存池接触的当然就是blockAlloc了, 所以我们也来看一下这个函数.

char* alloc::blockAlloc(size_t size, size_t& num) {
    char* re = 0;
    size_t bytesNeeded = size * num;
    size_t bytesLeft = endOfPool - startOfPool;

    if (bytesLeft >= bytesNeeded) {
        re = startOfPool;
        startOfPool = startOfPool + bytesNeeded;
        return re;
    }
    else if (bytesLeft > size) {
        num = bytesLeft / size;
        re = startOfPool;
        startOfPool += num * size;
        return re;
    }
    else {
        //TODO
    }
}

这里本来有三种情况：

 第一种是说如果空间足够(足够分配20个Node那么大), 就直接分配, 然后把指向内存池中空间起始位置的startOfPool移到新的位置;

 第二种是虽然不够分配20个, 但是足够分配一个, 此时使用相同的方式, 只不过需要对num进行改动(因为这里num传的是引用, 所以也没什么大问题);

 最后一种情况是说连一个Node的内存都拿不出来, 这种情况需要再向系统申请内存,我将在下面详细说明.

 

这里我们先来理一理, 目前的情况...

1. 使用allocate向内存池请求size大小的内存空间.

2. allocate根据size找到最适合的自由链表.

　　a. 如果链表不为空, 返回第一个node, 链表头改为第二个node.

　　b. 如果链表为空, 使用blockAlloc请求分配node.

　　　　x. 如果内存池中有大于一个node的空间, 分配竟可能多的node(但是最多20个), 将一个node返回, 其他的node添加到链表中.

　　　　y. 如果内存池只有一个node的空间, 直接返回给用户.

　　　　z. 若果如果连一个node都没有, 再次向操作系统请求分配内存(这就是上面代码中的TODO部分).

 

 

然后我们还能发现内存池的几个特点 :

1. 刚开始初始化内存池的时候, 其实内存池中并没有内存, 同时所有的自由链表都为空链表.

2. 只有用户第一次向内存池请求内存时, 内存池会依次执行上述过程的 1->2->b->z来完成内存池以及链表的首次填充, 而此时, 其他未使用链表仍然是空的.

 

 

有了这个整体的了解之后, 我们现在就来看一下, 内存池是如何向操作系统申请内存的 : 

char* alloc::blockAlloc(size_t size, size_t& num) {
    char* re = 0;
    size_t bytesNeeded = size * num;
    size_t bytesLeft = endOfPool - startOfPool;

    if (bytesLeft >= bytesNeeded) {
        re = startOfPool;
        startOfPool = startOfPool + bytesNeeded;
        return re;
    }
    else if (bytesLeft > size) {
        num = bytesLeft / size;
        re = startOfPool;
        startOfPool += num * size;
        return re;
    }
    else {
        // I am not sure why add ROUND_UP(poolSize >> 4)
        size_t bytesToGet = 2 * bytesNeeded + ROUND_UP(poolSize >> 4);
        if (bytesLeft > 0) {
            node** theMostSuitableList = freeLists + FREELIST_INDEX(bytesLeft);
            (reinterpret_cast<node*>(startOfPool))->next = *theMostSuitableList;
            *theMostSuitableList = reinterpret_cast<node*>(startOfPool);
        }

        startOfPool = (char*)malloc(bytesToGet);
        if (!startOfPool) {
            node** currentFreeList = 0;
            node* listHeadNode = 0;
            for (int i = size + Align; i <= MaxBytes; i += Align) {
                currentFreeList = freeLists + FREELIST_INDEX(i);
                listHeadNode = *currentFreeList;
                if (listHeadNode) {
                    *currentFreeList = listHeadNode->next;
                    startOfPool = reinterpret_cast<char*>(listHeadNode);
                    endOfPool = reinterpret_cast<char*>(listHeadNode + i);
                    return blockAlloc(size, num);
                }
            }
            //if code can run into this place, it means we can no longer get any memeory, so the best way is to throw exception...
            exit(3);
        }
        else {
            poolSize += bytesToGet;
            endOfPool = startOfPool + bytesToGet;
            return blockAlloc(size, num);
        }
    }
}

 

你会发现空间不足的时候, 首先计算了所需要的内存就是这个bytesToGet, 我在代码中也提到了我也不太清楚后面为什么要加上一个round_up(...), 然后是把当前剩余的内存(如果有剩余的话)分配给合适的节点, 因为每次分配内存都是8的倍数, 所以只要有剩余, 也肯定是8把的倍数, 所以一定能找到合适的节点. 接着就开始分配内存, 如果分配内存失败的话, 那么从size + Align开始(其实源代码好像是从size开始, 但是我感觉此时存有size大小node的自由链表显然是空的, 不然也不会调用这个函数, 所以就直接size + align 开始了), 如果能从那些位置挪出一个node的话(显然挪出来的node要更大), 那么就可以完成分配了, 如果遍历了所有比size大的节点都寻找不到这样一块node的话, 正如我代码中所说的, 运行到那个位置就应该抛异常了. 另外如果分配成功, 更新相应的变量之后, 再次调用该函数进行分配, 此时内存池中有足够的内存分配给自由链表.

 

早这里关于内存的分配的全过程就讲完了, 下面是内存的释放 :

void alloc::deallocate(void* ptr, size_t size) {
    if (size > MaxBytes) {
        free(ptr);
    }
    else {
        size_t index = FREELIST_INDEX(size);
        static_cast<node*>(ptr)->next = freeLists[index];
        freeLists[index] = static_cast<node*>(ptr);
    }
}

内存的释放很简单, 如果大于128bytes的, 直接释放(因为也是直接分配过来的), 否则把它挂到相应的链表中, 留待之后使用.

 

到这里, 内存池的实现就算全部讲完了, 但是在真正将它投入到stl的实际使用中之前, 还要进行一层封装.

public:
        typedef T            value_type;
        typedef T*            pointer;
        typedef const T*    const_pointer;
        typedef T&            reference;
        typedef const T&    const_reference;
        typedef size_t        size_type;
        typedef ptrdiff_t    difference_type;
    public:
        static T *allocate();
        static T *allocate(size_t n);
        static void deallocate(T *ptr);
        static void deallocate(T *ptr, size_t n);

        static void construct(T *ptr);
        static void construct(T *ptr, const T& value);
        static void destroy(T *ptr);
        static void destroy(T *first, T *last);
    };

    template<class T>
    T *allocator<T>::allocate(){
        return static_cast<T *>(alloc::allocate(sizeof(T)));
    }
    template<class T>
    T *allocator<T>::allocate(size_t n){
        if (n == 0) return 0;
        return static_cast<T *>(alloc::allocate(sizeof(T) * n));
    }
    template<class T>
    void allocator<T>::deallocate(T *ptr){
        alloc::deallocate(static_cast<void *>(ptr), sizeof(T));
    }
    template<class T>
    void allocator<T>::deallocate(T *ptr, size_t n){
        if (n == 0) return;
        alloc::deallocate(static_cast<void *>(ptr), sizeof(T)* n);
    }

    template<class T>
    void allocator<T>::construct(T *ptr){
        new(ptr)T();
    }
    template<class T>
    void allocator<T>::construct(T *ptr, const T& value){
        new(ptr)T(value);
    }
    template<class T>
    void allocator<T>::destroy(T *ptr){
        ptr->~T();
    }
    template<class T>
    void allocator<T>::destroy(T *first, T *last){
        for (; first != last; ++first){
            first->~T();
        }
    }
}

这也就是我们熟悉的标准库中的allocator的接口...

 

 

所以最终内存池的思路其实是这样的:

1. 使用allocate向内存池请求size大小的内存空间, 如果需要请求的内存大小大于128bytes, 直接使用malloc.

2. 如果需要的内存大小小于128bytes, allocate根据size找到最适合的自由链表.

　　a. 如果链表不为空, 返回第一个node, 链表头改为第二个node.

　　b. 如果链表为空, 使用blockAlloc请求分配node.

　　　　x. 如果内存池中有大于一个node的空间, 分配竟可能多的node(但是最多20个), 将一个node返回, 其他的node添加到链表中.

　　　　y. 如果内存池只有一个node的空间, 直接返回给用户.

　　　　z. 若果如果连一个node都没有, 再次向操作系统请求分配内存.

　　　　　　①分配成功, 再次进行b过程

　　　　　　②分配失败, 循环各个自由链表, 寻找空间

　　　　　　　　I. 找到空间, 再次进行过程b

　　　　　　　　II. 找不到空间, 抛出异常(代码中并未给出, 只是给出了注释)

3. 用户调用deallocate释放内存空间, 如果要求释放的内存空间大于128bytes, 直接调用free.

4. 否则按照其大小找到合适的自由链表, 并将其插入.

 

特点其实是这样的 :

1. 刚开始初始化内存池的时候, 其实内存池中并没有内存, 同时所有的自由链表都为空链表.

2. 只有用户第一次向内存池请求内存时, 内存池会依次执行上述过程的 1->2->b->z来完成内存池以及链表的首次填充, 而此时, 其他未使用链表仍然是空的.

3. 所有已经分配的内存在内存池中没有任何记录, 释放与否完全靠程序员自觉.

4. 释放内存时, 如果大于128bytes, 则直接free, 否则加入相应的自由链表中而不是直接返还给操作系统.

 

 

 

转载：SGI STL中内存池的实现

 

 

一、概述

        在 C/C++ 中，内存管理是一个非常棘手的问题，我们在编写一个程序的时候几乎不可避免的要遇到内存的分配逻辑，这时候随之而来的有这样一些问题：是否有足够的内存可供分配? 分配失败了怎么办? 如何管理自身的内存使用情况? 等等一系列问题。在一个高可用的软件中，如果我们仅仅单纯的向操作系统去申请内存，当出现内存不足时就退出软件，是明显不合理的。正确的思路应该是在内存不足的时，考虑如何管理并优化自身已经使用的内存，这样才能使得软件变得更加可用。本次项目我们将实现一个内存池，并使用一个栈结构来测试我们的内存池提供的分配性能。最终，我们要实现的内存池在栈结构中的性能，要远高于使用 std::allocator 和 std::vector，如下图所示：

本次实现涉及的知识点

• C++ 中的内存分配器 std::allocator
• 内存池技术
• 手动实现模板链式栈
• 链式栈和列表栈的性能比较

二、内存池简介

内存池是池化技术中的一种形式。通常我们在编写程序的时候回使用 new delete 这些关键字来向操作系统申请内存，而这样造成的后果就是每次申请内存和释放内存的时候，都需要和操作系统的系统调用打交道，从堆中分配所需的内存。如果这样的操作太过频繁，就会找成大量的内存碎片进而降低内存的分配性能，甚至出现内存分配失败的情况。

而内存池就是为了解决这个问题而产生的一种技术。从内存分配的概念上看，内存申请无非就是向内存分配方索要一个指针，当向操作系统申请内存时，操作系统需要进行复杂的内存管理调度之后，才能正确的分配出一个相应的指针。而这个分配的过程中，我们还面临着分配失败的风险。

所以，每一次进行内存分配，就会消耗一次分配内存的时间，设这个时间为 T，那么进行 n 次分配总共消耗的时间就是 nT；如果我们一开始就确定好我们可能需要多少内存，那么在最初的时候就分配好这样的一块内存区域，当我们需要内存的时候，直接从这块已经分配好的内存中使用即可，那么总共需要的分配时间仅仅只有 T。当 n 越大时，节约的时间就越多。

三、主函数设计

        我们要设计实现一个高性能的内存池，那么自然避免不了需要对比已有的内存，而比较内存池对内存的分配性能，就需要实现一个需要对内存进行动态分配的结构（比如：链表栈），为此，可以写出如下的代码：

#include <iostream>   // std::cout, std::endl
#include <cassert>    // assert()
#include <ctime>      // clock()
#include <vector>     // std::vector

#include "MemoryPool.hpp"  // MemoryPool<T>
#include "StackAlloc.hpp"  // StackAlloc<T, Alloc>

// 插入元素个数
#define ELEMS 10000000
// 重复次数
#define REPS 100

int main()
{
    clock_t start;

    // 使用 STL 默认分配器
    StackAlloc<int, std::allocator<int> > stackDefault;
    start = clock();
    for (int j = 0; j < REPS; j++) {
        assert(stackDefault.empty());
        for (int i = 0; i < ELEMS; i++)
          stackDefault.push(i);
        for (int i = 0; i < ELEMS; i++)
          stackDefault.pop();
    }
    std::cout << "Default Allocator Time: ";
    std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";

    // 使用内存池
    StackAlloc<int, MemoryPool<int> > stackPool;
    start = clock();
    for (int j = 0; j < REPS; j++) {
        assert(stackPool.empty());
        for (int i = 0; i < ELEMS; i++)
          stackPool.push(i);
        for (int i = 0; i < ELEMS; i++)
          stackPool.pop();
    }
    std::cout << "MemoryPool Allocator Time: ";
    std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";

    return 0;
}

        在上面的两段代码中，StackAlloc 是一个链表栈，接受两个模板参数，第一个参数是栈中的元素类型，第二个参数就是栈使用的内存分配器。

        因此，这个内存分配器的模板参数就是整个比较过程中唯一的变量，使用默认分配器的模板参数为 std::allocator，而使用内存池的模板参数为 MemoryPool。

        std::allocator 是 C++标准库中提供的默认分配器，他的特点就在于我们在 使用 new 来申请内存构造新对象的时候，势必要调用类对象的默认构造函数，而使用 std::allocator 则可以将内存分配和对象的构造这两部分逻辑给分离开来，使得分配的内存是原始、未构造的。

下面我们来实现这个链表栈。

3.1 模板链表栈

       栈的结构非常的简单，没有什么复杂的逻辑操作，其成员函数只需要考虑两个基本的操作：入栈、出栈。为了操作上的方便，我们可能还需要这样一些方法：判断栈是否空、清空栈、获得栈顶元素。

#include <memory>
template <typename T>
struct StackNode_
{
  T data;
  StackNode_* prev;
};
// T 为存储的对象类型, Alloc 为使用的分配器, 并默认使用 std::allocator 作为对象的分配器
template <typename T, typename Alloc = std::allocator<T> >
class StackAlloc
{
  public:
    // 使用 typedef 简化类型名
    typedef StackNode_<T> Node;
    typedef typename Alloc::template rebind<Node>::other allocator;
    // 默认构造
    StackAlloc() { head_ = 0; }
    // 默认析构
    ~StackAlloc() { clear(); }

    // 当栈中元素为空时返回 true
    bool empty() {return (head_ == 0);}

    // 释放栈中元素的所有内存
    void clear();

    // 压栈
    void push(T element);

    // 出栈
    T pop();

    // 返回栈顶元素
    T top() { return (head_->data); }

  private:
    allocator allocator_;
    Node* head_; // 栈顶
};

        简单的逻辑诸如构造、析构、判断栈是否空、返回栈顶元素的逻辑都非常简单，直接在上面的定义中实现了，下面我们来实现 clear(), push() 和 pop() 这三个重要的逻辑：

// 释放栈中元素的所有内存
void clear() {
  Node* curr = head_;
  // 依次出栈
  while (curr != 0)
  {
    Node* tmp = curr->prev;
    // 先析构, 再回收内存
    allocator_.destroy(curr);
    allocator_.deallocate(curr, 1);
    curr = tmp;
  }
  head_ = 0;
}
// 入栈
void push(T element) {
  // 为一个节点分配内存
  Node* newNode = allocator_.allocate(1);
  // 调用节点的构造函数
  allocator_.construct(newNode, Node());

  // 入栈操作
  newNode->data = element;
  newNode->prev = head_;
  head_ = newNode;
}

// 出栈
T pop() {
  // 出栈操作 返回出栈元素
  T result = head_->data;
  Node* tmp = head_->prev;
  allocator_.destroy(head_);
  allocator_.deallocate(head_, 1);
  head_ = tmp;
  return result;
}

       至此，我们完成了整个模板链表栈，现在我们可以先注释掉 main() 函数中使用内存池部分的代码来测试这个连表栈的内存分配情况，我们就能够得到这样的结果：

在使用 std::allocator 的默认内存分配器中，在下面的条件下，总共花费了近一分钟的时间。

#define ELEMS 10000000
#define REPS 100

这样我们实现了一个用于测试性能比较的模板链表栈。下面，我们开始详细实现我们的高性能内存池。

四、设计内存池

        在上面实验中，我们在模板链表栈中使用了默认构造器来管理栈操作中的元素内存，一共涉及到了 rebind::other, allocate(), dealocate(), construct(), destroy()这些关键性的接口。所以为了让代码直接可用，我们同样应该在内存池中设计同样的接口：

#ifndef MEMORY_POOL_HPP
#define MEMORY_POOL_HPP

#include <climits>
#include <cstddef>

template <typename T, size_t BlockSize = 4096>
class MemoryPool
{
  public:
    // 使用 typedef 简化类型书写
    typedef T*              pointer;

    // 定义 rebind<U>::other 接口
    template <typename U> struct rebind {
      typedef MemoryPool<U> other;
    };

    // 默认构造, 初始化所有的槽指针
    // C++11 使用了 noexcept 来显式的声明此函数不会抛出异常
    MemoryPool() noexcept {
      currentBlock_ = nullptr;
      currentSlot_ = nullptr;
      lastSlot_ = nullptr;
      freeSlots_ = nullptr;
    }

    // 销毁一个现有的内存池
    ~MemoryPool() noexcept;

    // 同一时间只能分配一个对象, n 和 hint 会被忽略
    pointer allocate(size_t n = 1, const T* hint = 0);

    // 销毁指针 p 指向的内存区块
    void deallocate(pointer p, size_t n = 1);

    // 调用构造函数
    template <typename U, typename... Args>
    void construct(U* p, Args&&... args);

    // 销毁内存池中的对象, 即调用对象的析构函数
    template <typename U>
    void destroy(U* p) {
      p->~U();
    }

  private:
    // 用于存储内存池中的对象槽, 
    // 要么被实例化为一个存放对象的槽, 
    // 要么被实例化为一个指向存放对象槽的槽指针
    union Slot_ {
      T element;
      Slot_* next;
    };

    // 数据指针
    typedef char* data_pointer_;
    // 对象槽
    typedef Slot_ slot_type_;
    // 对象槽指针
    typedef Slot_* slot_pointer_;

    // 指向当前内存区块
    slot_pointer_ currentBlock_;
    // 指向当前内存区块的一个对象槽
    slot_pointer_ currentSlot_;
    // 指向当前内存区块的最后一个对象槽
    slot_pointer_ lastSlot_;
    // 指向当前内存区块中的空闲对象槽
    slot_pointer_ freeSlots_;

    // 检查定义的内存池大小是否过小
    static_assert(BlockSize >= 2 * sizeof(slot_type_), "BlockSize too small.");
};

#endif // MEMORY_POOL_HPP

在上面的类设计中可以看到，在这个内存池中，其实是使用链表来管理整个内存池的内存区块的。内存池首先会定义固定大小的基本内存区块(Block)，然后在其中定义了一个可以实例化为存放对象内存槽的对象槽（Slot_）和对象槽指针的一个联合。然后在区块中，定义了四个关键性质的指针，它们的作用分别是：

• currentBlock_: 指向当前内存区块的指针
• currentSlot_: 指向当前内存区块中的对象槽
• lastSlot_: 指向当前内存区块中的最后一个对象槽
• freeSlots_: 指向当前内存区块中所有空闲的对象槽

梳理好整个内存池的设计结构之后，我们就可以开始实现关键性的逻辑了。
 

五、实现

5.1 MemoryPool::construct() 实现

MemoryPool::construct() 的逻辑是最简单的，我们需要实现的，仅仅只是调用信件对象的构造函数即可，因此：

// 调用构造函数, 使用 std::forward 转发变参模板
template <typename U, typename... Args>
void construct(U* p, Args&&... args) {
    new (p) U (std::forward<Args>(args)...);
}

5.2 MemoryPool::deallocate() 实现

MemoryPool::deallocate() 是在对象槽中的对象被析构后才会被调用的，主要目的是销毁内存槽。其逻辑也不复杂：

// 销毁指针 p 指向的内存区块
void deallocate(pointer p, size_t n = 1) {
  if (p != nullptr) {
    // reinterpret_cast 是强制类型转换符
    // 要访问 next 必须强制将 p 转成 slot_pointer_
    reinterpret_cast<slot_pointer_>(p)->next = freeSlots_;
    freeSlots_ = reinterpret_cast<slot_pointer_>(p);
  }
}

5.3 MemoryPool::~MemoryPool() 实现

析构函数负责销毁整个内存池，因此我们需要逐个删除掉最初向操作系统申请的内存块：

// 销毁一个现有的内存池
~MemoryPool() noexcept {
  // 循环销毁内存池中分配的内存区块
  slot_pointer_ curr = currentBlock_;
  while (curr != nullptr) {
    slot_pointer_ prev = curr->next;
    operator delete(reinterpret_cast<void*>(curr));
    curr = prev;
  }
}

5.4 MemoryPool::allocate() 实现

MemoryPool::allocate() 毫无疑问是整个内存池的关键所在，但实际上理清了整个内存池的设计之后，其实现并不复杂。具体实现如下：

// 同一时间只能分配一个对象, n 和 hint 会被忽略
pointer allocate(size_t n = 1, const T* hint = 0) {
  // 如果有空闲的对象槽，那么直接将空闲区域交付出去
  if (freeSlots_ != nullptr) {
    pointer result = reinterpret_cast<pointer>(freeSlots_);
    freeSlots_ = freeSlots_->next;
    return result;
  } else {
    // 如果对象槽不够用了，则分配一个新的内存区块
    if (currentSlot_ >= lastSlot_) {
      // 分配一个新的内存区块，并指向前一个内存区块
      data_pointer_ newBlock = reinterpret_cast<data_pointer_>(operator new(BlockSize));
      reinterpret_cast<slot_pointer_>(newBlock)->next = currentBlock_;
      currentBlock_ = reinterpret_cast<slot_pointer_>(newBlock);
      // 填补整个区块来满足元素内存区域的对齐要求
      data_pointer_ body = newBlock + sizeof(slot_pointer_);
      uintptr_t result = reinterpret_cast<uintptr_t>(body);
      size_t bodyPadding = (alignof(slot_type_) - result) % alignof(slot_type_);
      currentSlot_ = reinterpret_cast<slot_pointer_>(body + bodyPadding);
      lastSlot_ = reinterpret_cast<slot_pointer_>(newBlock + BlockSize - sizeof(slot_type_) + 1);
    }
    return reinterpret_cast<pointer>(currentSlot_++);
  }
}

六、与 std::vector 的性能对比

我们知道，对于栈来说，链栈其实并不是最好的实现方式，因为这种结构的栈不可避免的会涉及到指针相关的操作，同时，还会消耗一定量的空间来存放节点之间的指针。事实上，我们可以使用 std::vector 中的 push_back() 和 pop_back() 这两个操作来模拟一个栈，我们不妨来对比一下这个 std::vector 与我们所实现的内存池在性能上谁高谁低，我们在 主函数中加入如下代码：

// 比较内存池和 std::vector 之间的性能
    std::vector<int> stackVector;
    start = clock();
    for (int j = 0; j < REPS; j++) {
        assert(stackVector.empty());
        for (int i = 0; i < ELEMS; i++)
          stackVector.push_back(i);
        for (int i = 0; i < ELEMS; i++)
          stackVector.pop_back();
    }
    std::cout << "Vector Time: ";
    std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";

这时候，我们重新编译代码，就能够看出这里面的差距了：

        首先是使用默认分配器的链表栈速度最慢，其次是使用 std::vector 模拟的栈结构，在链表栈的基础上大幅度削减了时间。

std::vector 的实现方式其实和内存池较为类似，在 std::vector 空间不够用时，会抛弃现在的内存区域重新申请一块更大的区域，并将现在内存区域中的数据整体拷贝一份到新区域中。

最后，对于我们实现的内存池，消耗的时间最少，即内存分配性能最佳，完成了本次试验。

七、总结

我们实现了我们上节实验中未实现的内存池，完成了整个项目的目标。 这个内存池不仅精简而且高效。但是不是所有的项目都适合内存池，只是对于频繁进行内存申请与释放的情景，提升更高，更明显。

 

在程序运行过程中，可能产生一些数据，例如，串口接收的数据，ADC采集的数据。若需将数据存储在内存中，以便进一步运算、处理，则应为其分配合适的内存空间，数据处理完毕后，再释放相应的内存空间。为了便于内存的分配和释放，AWorks提供了两种内存管理工具：堆和内存池。

本文为《面向AWorks框架和接口的编程（上）》第三部分软件篇——第9章内存管理——第1~2小节：堆管理器和内存池。

本章导读

在计算机系统中，数据一般存放在内存中，只有当数据需要参与运算时，才从内存中取出，交由CPU运算，运算结束再将结果存回内存中。这就需要系统为各类数据分配合适的内存空间。

一些数据需要的内存大小在编译前可以确定。主要有两类：一类是全局变量或静态变量，这部分数据在程序的整个生命周期均有效，在编译时就为这些数据分配了固定的内存空间，后续直接使用即可，无需额外的管理；一类是局部变量，这部分数据仅在当前作用域中有效（如函数中），它们需要的内存自动从栈中分配，也无需额外的管理，但需要注意的是，由于这一部分数据的内存从栈中分配，因此，需要确保应用程序有足够的栈空间，尽量避免定义内存占用较大的局部变量（比如：一个占用数K内存的数组），以避免栈溢出，栈溢出可能破坏系统关键数据，极有可能造成系统崩溃。

一些数据需要的内存大小需要在程序运行过程中根据实际情况确定，并不能在编译前确定。例如，可能临时需要1K内存空间用于存储远端通过串口发过来的数据。这就要求系统具有对内存空间进行动态管理的能力，在用户需要一段内存空间时，向系统申请，系统选择一段合适的内存空间分配给用户，用户使用完毕后，再释放回系统，以便系统将该段内存空间回收再利用。在AWorks中，提供了两种常见的内存管理方法：堆和内存池。

9.1  堆管理器

堆管理器用于管理一段连续的内存空间，可以在满足系统资源的情况下，根据用户的需求分配任意大小的内存块，完全“按需分配”，当用户不再使用分配的内存块时，又可以将内存块释放回堆中供其它应用分配使用。类似于C标准库中的malloc()/free()函数实现的功能。

9.1.1  堆管理器的原理概述

在使用堆管理器前，首先通过一个示例对其原理作简要的介绍，以便用户更加有效的使用堆管理器。例如，使用堆管理器对1024字节的内存空间进行管理。初始时，所有内存均处于空闲状态，可以将整个内存空间看作一个大的空闲内存块。示意图详见图9.1。

图9.1 初始状态——单个空闲内存块

内存分配的策略是：当用户申请一定大小的内存空间时，堆管理器会从第一个空闲内存块开始查找，直到找到一个满足用户需求的空闲内存块（即容量不小于用户请求的内存空间大小），然后从该空闲内存块中分配出用户指定大小的内存空间。

例如，用户向该堆管理器申请100字节的内存空间，由于第一个空闲内存块的容量为1024，满足需求，因此，可以从中分配100字节的内存空间给该用户，分配后的内存示意图详见图9.2。

图9.2 分配100字节——分割为两个内存块

注：填充为阴影表示该块已被分配，否则，表示该块未被分配，处于空闲状态，数字表示该块的容量。

同理，若用户再向该堆管理器连续请求三次内存空间，每次请求的内存空间容量分别为：150、250、200字节，则分配后的内存示意图详见图9.3。

图9.3 再分配100、300、200字节内存空间——分割为五个内存块

随着分配的继续，内存块可能越来越多。若用户的请求无法满足，则会分配失败，如果在图9.3的基础上，用户再请求400字节内存空间，由于仅有的一个空闲块，且容量为324字节，无法满足需求，此时，分配会失败，用户无法得到一段有效的内存空间。

当用户申请的某一段内存不再使用时，应该将该内存块释放回堆中，以便回收再利用。

回收的策略是：当用户将某一内存块释放回堆中时，首先，将该内存块变为空闲块，若该内存块相邻的内存块也为空闲块，则将它们合并为一个大的空闲内存块。

例如，在图9.3的基础上，释放之前分配的250字节内存空间，则首先将该内存块变为空闲块，示意图详见图9.4。

图9.4 释放一个内存块——相邻块不为空闲块

由于该内存块前后均不为空闲块，因此，无需作合并操作。此时，释放了250字节的空闲空间，堆中共存在574字节的内存空间。但是，若用户此时向该堆管理器申请400字节的内存空间，由于第一个空闲块和第二个空闲块均不满足需求，因此，内存分配还是会失败。

这里暴露出了一个堆管理器的缺点。频繁的分配和释放大小不一的内存块，将产生诸多内存碎片，即图9.4中被已分配内存块打断的空闲内存块，图中容量为250字节和容量为324字节的空闲内存块被一个已分配的容量为200字节的内存块打断，使得各个空闲块在物理上不连续，无法形成一个大的空闲块。这种情况下，即使请求的内存空间大小小于当前堆的空闲空间总大小，也可能会由于没有一个大的空闲块而分配失败。

在图9.4的基础上，即使再释放掉第一次分配的100字节内存空间，使总空闲空间达到674字节，详见图9.5，同样无法满足一个400字节内存空间的分配请求。

图9.5 释放容量为100字节内存块

随着系统中大量内存块的分配和回收，内存碎片将越来越多，一些长时间不被释放的内存块，将始终分割着一些空闲内存块，造成内存碎片。这也告知用户，当不再使用某一内存块时，应尽快释放掉该内存块，以避免造成过多的内存碎片。

在图9.5中，有3个空闲块，若用户在此基础上再请求一个280字节的内存空间，根据分配策略，堆管理器首先查看第一个空闲块，其容量为100字节，无法满足需求，接着查看第二个空闲块，其容量为250字节，同样无法满足需求，接着查看第三个空闲块，其容量为324字节，最终从该块中分配一段空间给用户，分配后的内存示意图详见图9.6。

图9.6 再分配280字节内存空间

在图9.6的基础上，若用户再释放200字节的内存块，首先，将其变为空闲块，示意图详见图9.7。

图9.7 释放200字节的内存空间（1）——标记为空闲

由于其左侧大小为250的内存块同样为空闲块，因此，需要将它们合并为一个大的内存块，即合并为一个大小为450的内存块，示意图详见图9.8。

图9.8 释放200字节的内存空间（2）——与相邻空闲块合并

此时，由于存在一个大小为450的空闲块，因此，若此时用户申请400字节的内存空间，则可以申请成功。与图9.5对比可知，虽然图9.5共计有674字节的空闲空间，而图9.8只有594字节的空闲空间，但图9.8却可以满足一个大小为400字节的内存空间请求。由此可见，受内存碎片的影响，总的空闲空间大小并不能决定一个内存请求的成功与否。

申请400字节成功后的示意图详见图9.9。

图9.9 再分配400字节内存空间

在图9.9的基础上，若用户再释放280字节的内存块，同样，首先将其变为空闲块，示意图详见图9.10。

图9.10 释放280字节的内存空间（1）——标记为空闲

由于其左右两侧均为空闲块，因此，需要将它们合并为一个大的内存块，即合并为一个大小为374的内存块，示意图详见图9.11。

图9.11 释放280字节的内存空间（2）——与相邻空闲块合并

之所以要将相邻的空闲内存块合并，主要是为了避免内存块越来越多，越来越零散，如此下去，将很难再有一个大的空闲块，用户后续再申请大的内存空闲时，将无法满足需求。

通过上面一系列内存分配和释放的示例，展示了堆管理器分配和释放内存的策略，使得用户对相关的原理有了一定的了解。

实际上，在堆管理器的软件实现中，为了便于管理，各个内存块是以链表的形式组织起来的，每个内存块的首部会固定存放一些用于内存块管理的相关信息，示意图详见图9.12。

图9.12 内存块（含空闲内存块和已分配内存块）链表

图中展示了4个非常重要的信息：magic、used、p_next、p_prev。

magic被称为魔数，会被赋值为一个特殊的固定值，它表示了该内存块是堆管理器管理的内存块，可以在一定程度上检查错误的内存操作。例如，若这个区域被改写，magic的值被修改为了其它值，表明存在非法的内存操作，可能是用户内存操作越界等，应及时处理；在释放一个内存块时，堆管理器会检查magic的值，若其值不为特殊的固定值，表明这并不是堆管理器分配的内存块，该释放操作是非法的。

used用于表示该内存块是否已经被使用。若其值为0，则表示该内存块是空闲块；若其值为1，则表示该内存块已经被分配，不是空闲块。

p_next和p_prev用于将各个内存块使用双向链表的形式组织起来，以便可以方便的找到当前内存块的下一个或上一个内存块，例如，在释放一个内存块时，需要查看相邻的内存块（上一个内存块和下一个内存块）是否为空闲块，以决定是否将它们合并为一个空闲块。

此外，为了在分配内存块时，加快搜索空闲块的效率，信息中还会额外另外两个指针，用于将所有空闲块单独组织为一个双向链表。这样，在分配一个内存块时，只需要在空闲链表中查找满足需求的空闲块即可，无需依次遍历所有的内存块。示意图详见图9.13。

图9.13 空间块链表

对于用户来讲，其获得的内存空间为用户数据空间（获得的是直接指向用户数据空间的指针），存放在内存块首部的信息对用户是不可见的，用户不应该尝试访问、修改这些信息。

需要用户注意的是，由于内存块的相关信息需要占用一定的内存空间（在32位系统中，通常为24字节），因此，每个内存块占用的实际大小会大于用户请求的内存空间大小，例如，用户请求一个100字节的内存空间，实际中，为了存储内存块的相关信息，会分配一个大小为124字节的内存块。基于此，用户实际可以使用的内存空间要略小于堆的总空间。

9.1.2  堆管理器接口

AWorks提供了堆管理器，用户通过相关接口使用即可。相关函数的原型详见表9.1。

表9.1 堆管理器接口（aw_memheap.h）

1.  定义堆管理器实例

在使用堆管理器前，必须先使用aw_memheap_t类型定义堆管理器实例，该类型在aw_memheap.h中定义，具体类型的定义用户无需关心，仅需使用该类型定义堆管理器实例即可，即：

其地址即可作为初始化接口中memheap参数的实参传递。

在AWorks中，一个堆管理器用于管理一段连续的内存空间，一个系统中，可以使用多个堆管理器分别管理多段连续的内存空间。这就需要定义多个堆管理器实例，例如：

如此一来，各个应用可以定义自己的堆管理器，以管理该应用中的内存分配与释放，使得各个应用之间的内存使用互不影响。

如果所有应用使用一个堆，那么各个应用之间的内存分配将相互影响，某一应用出现内存泄漏，随着时间的推移，极有可能造成一个堆的空间被完全泄漏，这将影响所有应用程序。同时，所有应用共用一个堆，也造成在一个堆中的分配与释放更加频繁，分配的内存块大小更加不一致，更容易产生内存碎片。

2.  初始化堆管理器

定义堆管理器实例后，必须使用该接口初始化后才能使用，以指定其管理的内存空间，其函数原型为：

其中，memheap为指向堆管理器实例的指针；name为堆管理器的名字，名字为一个字符串，仅用作标识；start_addr指定了其管理的内存空间首地址；size指定了其管理的内存空间大小（字节数）。

函数的返回值为标准的错误号，返回AW_OK时，表示初始化成功；否则，表示初始化失败。

初始化函数的核心在于指定其管理的内存空间，通常情况下，这段连续的内存空间可以通过定义一个全局的数组变量获得，其大小与实际应用相关，应根据实际情况决定。例如，使用堆管理器管理1KB的内存空间，则初始化堆管理器的范例程序详见程序清单9.1。

程序清单9.1 初始化堆管理器范例程序

程序中，定义了一个大小为1024字节的数组，用于分配一个1KB的内存空间，以便使用堆管理器进行管理。

3.  分配内存

堆管理器初始化完毕后，可以使用该接口为用户分配指定大小的内存块，内存块的大小可以是满足资源需求的任意大小。分配内存块的函数原型为：

其中，heap为指向堆管理器的指针；size为内存块大小。返回值为分配内存块的首地址，特别地，若返回值为NULL，则表明分配失败。

在分配内存块时，由于堆管理器并不知道分配的内存块用来存储何种类型的数据，因此，返回值为通用的无类型指针，即void *类型，代表其指向了某一类型不确定的地址。显然，分配的内存块用以存储何种类型的数据是由用户决定的，因此，用户在使用这段内存空间时，必须将其转换为实际数据类型的指针。

例如，分配用以存储100个无符号8位数据的内存块，其范例程序详见程序清单9.2。

程序清单9.2 分配内存块的范例程序

程序中，将aw_memheap_alloc()的返回值强制转换为了指向uint8_t数据类型的指针。注意，使用aw_memheap_alloc()分配的内存中，数据的初始值是随机的，不一定为0。因此，若不对ptr指向的内存赋值，则其值可能是任意的。

4.  重新调整内存大小

有时候，需要动态调整之前分配的内存块大小，如果一开始分配了一个较小的内存块，但随着数据的增加，内存不够，此时，就可以使用该函数重新调整之前分配的内存块大小。其函数原型为：

其中，heap为指向堆管理器的指针；ptr为使用aw_memheap_alloc()函数分配的内存块首地址，即调用aw_memheap_alloc()函数的返回值；new_size为调整后的内存块大小。返回值为调整大小后的内存空间首地址，特别地，若返回值为NULL，则表明调整大小失败。

newsize指定的新的大小可以比原内存块大（扩大），也可以比原内存块小（缩小）。如果是扩大内存块，则新扩展部分的内存不会被初始化，值是随机的，但原内存块中的数据仍然保持不变。如果是缩小内存块，则超出new_size部分的内存会被释放，其中的数据被丢弃，其余数据保持不变。特别地，若newsize的值为0，则相当于不再使用ptr指向的内存块，此时，将会直接释放整个内存块，这种情况下，返回值同样为NULL。

函数返回值与ptr的值可能不同，即系统可能重新选择一块合适的内存块来满足调整大小的需求，此时，内存首地址将发生变化。例如，当新的大小比原空间大时，系统先判断原内存块后是否还有足够的连续空间满足本次扩大内存的要求，如果有，则直接扩大内存空间，内存首地址不变，同样返回原内存块的首地址，即ptr的值；如果没有，则重新按照newsize分配一个内存块，并将原有数据原封不动的拷贝到新分配的内存块中，而后自动释放原有的内存块，原内存块将不再可用，此时，返回值将是重新分配的内存块首地址，与ptr将无直接关系。

例如，首先使用aw_memheap_alloc()分配了一个100字节大小的内存块，然后重新将其调整为200字节大小的内存块。范例程序详见程序清单9.3。

程序清单9.3 重新调整内存大小

值得注意的是，重新调整内存空间的大小失败后，原内存空间还是有效的。因此，若采用程序清单9.3第9行的调用形式，若内存扩大失败，则返回值为NULL，这将会导致ptr的值被设置为NULL。此时，虽然原内存空间仍然有效，但由于指向该内存空间的指针信息丢失了，用户无法再访问到对应的内存空间，也无法释放对应的内存空间，造成内存泄漏。

在实际使用时，为了避免调整内存大小失败时将原ptr的值覆盖为NULL，应该使用一个新的指针保存函数的返回值，详见程序清单9.4。

程序清单9.4 重新调整内存大小（使用新的指针保存函数返回值）

此时，即使扩大内存空间失败，指向原内存空间的指针ptr依然有效，依旧可以使用原先分配的内存空间，避免了内存泄漏。扩大内存空间成功时，则直接将ptr的值重新赋值为new_ptr，使其指向扩展完成后的内存空间。

5.  释放内存

当用户不再使用申请的内存块时，必须释放，否则将造成内存泄漏。释放内存的函数原型为：

其中，ptr为使用aw_memheap_alloc()或aw_memheap_realloc()函数分配的内存块首地址，即调用这些函数的返回值。注意，ptr只能是上述几个函数的返回值，不能是其它地址值，例如，不能将数组首地址作为函数参数，以释放静态数组占用的内存空间。传入错误的地址值，极有可能导致系统崩溃。

当使用aw_memheap_free()将内存块释放后，相应的内存块将变为无效，用户不能再继续使用。释放内存块的范例程序详见程序清单9.5。

程序清单9.5 释放内存块的范例程序

为了避免释放内存块后再继续使用，可以养成一个良好的习惯，每当内存释放后，都将相应的ptr指针赋值为NULL。

9.1.3  系统堆管理

在AWorks中，整个内存空间首先用于满足存放一些已知占用内存空间大小的数据，比如：全局变量、静态变量、栈空间、程序代码或常量等。

全局变量和静态变量都比较好理解，其占用的内存大小通过数据的类型即可确定。需要注意的是，在介绍堆管理器时，定义一块待管理的内存空间同样使用了静态数组的方式，详见程序清单9.1的第6行：

这也属于一种静态变量，其占用的内存大小是已知的。

对于栈空间，在AWorks中，栈空间是静态分配的，类似于一个静态数组，其占用的内存空间大小由用户决定，同样是已知的。

通常情况下，程序代码和常量都存储在ROM或FLASH等只读存储器中，不会放在内存中。但在部分平台中，出于效率或芯片架构的考虑，也可能将程序代码和常量存储在内存中。例如，在i.MX28x平台中，程序代码和常量也存储在DDR内存中。程序代码和常量占用的内存空间大小在编译后即可确定，占用的内存空间大小也是已知的。

在满足这些数据的存储后，剩下的所有内存空间即作为系统堆空间，便于用户在程序运行过程中动态使用。

为了便于用户使用，需要使用某种合适的方法管理系统堆空间。在AWorks中，默认使用前文介绍的堆管理器对其进行管理。出于系统的可扩展性考虑，AWorks并没有限制必须基于AWorks提供的堆管理器管理系统堆空间，如果用户有更加适合特殊应用场合的管理方法，也可以在特定环境下使用自有方法管理系统堆空间。为了保持应用程序的统一，AWorks定义了一套动态内存管理通用接口，便于用户使用系统堆空间，而无需关心具体的管理方法。相关函数原型详见表9.2。

表9.2 动态内存管理接口（aw_mem.h）

通过前文的介绍可知，在使用堆管理器前，需要定义堆管理器实例，然后初始化该实例，以指定其管理的内存空间，初始化完成后，用户才可向其请求内存。若是使用堆管理器管理系统堆空间（默认），那么，表9.2中的接口均可基于堆管理器接口实现。此时，系统中将定义一个默认的堆管理器实例，并在系统启动时自动完成其初始化操作，指定其管理的内存空间为系统堆空间。如此一来，系统启动后，用户可以直接向系统中默认的堆管理器申请内存块。例如，aw_mem_alloc()用于分配一个内存块，其直接基于堆管理器实现，范例程序详见程序清单9.6。

程序清单9.6 aw_mem_alloc()函数实现范例

其中，__g_system_heap为系统定义的堆管理器实例，已在系统启动时完成了初始化。程序清单9.6只是aw_mem_alloc()函数实现的一个简单范例，实际中，用户可以根据具体情况，使用最为合适的方法管理系统堆空间，实现AWorks定义的动态内存管理通用接口。

下面，详细介绍各个接口的含义及使用方法。

1.  分配内存

aw_mem_alloc()用于从系统堆中分配指定大小的内存块，用法和C标准库中的malloc()相同，其函数原型为：

参数size指定内存空间的大小，单位为字节。返回值为void *类型的指针，其指向分配内存块的首地址，特别地，若返回值为NULL，则表示分配失败。

例如，申请用以存储一个int类型数据的存储空间，范例程序详见程序清单9.7。

程序清单9.7 申请内存范例程序

程序中，将aw_mem_alloc()的返回值强制转换为了指向int数据类型的指针。注意，使用aw_mem_alloc()分配的内存中，数据的初始值是随机的，不一定为0。因此，若不对ptr指向的内存赋值，则其值将是任意的。

2.  分配多个指定大小的内存块

除使用aw_mem_alloc()直接分配一个指定大小的内存块外，还可以使用aw_mem_calloc()分配多个连续的内存块，用法与C标准库中的calloc()相同，其函数原型为：

该函数用于分配nelem个大小为size的内存块，分配的内存空间总大小为：nelem×size，实际上相当于分配一个容量为nelem×size的大内存块，返回值同样为分配内存块的首地址。与aw_mem_alloc()不同的是，该函数分配的内存块会被初始化为0。例如，分配用以存储10个int类型数据的内存，则范例程序详见程序清单9.8。

程序清单9.8 分配10个用于存储int类型数据的内存块

由于分配的内存空间会被初始化为0，因此，即使不对ptr指向的内存赋值，其值也是确定的0。

3.  分配具有一定对齐要求的内存块

有时候，用户申请的内存块可能用来存储具有特殊对齐要求的数据，要求分配内存块的首地址必须按照指定的字节数对齐。此时，可以使用aw_mem_align()分配一个满足指定对齐要求的内存块。其函数原型为：

其中，size为分配的内存块大小，align表示对齐要求，其值是2的整数次幂，比如：2、4、8、16、32、64等。返回值同样为分配内存块的首地址，其值满足对齐要求，是align的整数倍。如align的值为16，则按照16字节对齐，分配内存块的首地址将是16的整数倍，地址的低4位全为0。程序范例详见程序清单9.9。

程序清单9.9 分配具有一定对齐要求的内存块范例程序

程序中，将分配的地址通过aw_kprintf()打印输出，以查看地址的具体值，实际运行可以发现，地址值是满足16字节对齐的。注意，该函数与aw_mem_alloc()分配的内存块一样，其中的数据初始值是随机的，不一定为0。

在堆管理器中，并没有类似的分配满足一定对齐要求的内存块接口，只有普通的分配内存块接口：aw_memheap_alloc()。其分配的内存块，可能是对齐的，也可能是未对齐的。为了使返回给用户的内存块能够满足对齐要求，在使用aw_memheap_alloc()分配内存块时，可以多分配align - 1字节的空间，此时，即使获得的内存块首地址不满足对齐要求，也可以返回从内存块首地址开始，顺序第一个对齐的地址给用户，以满足用户的对齐需求。

例如，要分配200字节的内存块，并要求满足8字节对齐，则首先使用aw_memheap_alloc()分配207字节（200 + 8 - 1）的内存块，假定得到的内存块地址范围为：3 ~ 209，示意图详见图9.14(a)。由于首地址3不是8的整数倍，因此其不是按8字节对齐的，此时，直接返回顺序第一个对齐的地址给用户，即：8。由于用户需要的是200字节的内存块，因此，对于用户来讲，其使用的内存块地址范围为 ：8 ~ 207，显然，其在实际使用aw_memheap_alloc()获得的内存块地址范围内，用户获得的内存块是完全有效的，示意图详见图9.14(b)。

图9.14 内存对齐的处理——多分配align-1字节的空间

为什么要多分配align - 1字节的空间呢？在获得的实际内存块不满足对齐需求时，表明内存块首地址不是align的整数倍，即其对align取余数的结果（C语言的%运算符）不为0，假定其对align取余数的结果为N（N ≥1），则只要将首地址加上align-N，得到的地址值就是align的整数倍。该值也为从首地址开始，顺序第一个对齐的地址。由于在首地址不对齐时，必然有：N ≥1，因此：align - N ≤ align – 1，即顺序第一个对齐的地址相对于起始地址的偏移不会超过align - 1。基于此，只要在分配内存块时多分配align-1字节的空间，那么就可以在向用户返回一个对齐地址的同时，依旧满足用户请求的内存块容量需求。

若不多分配align-1字节的内存空间，例如，只使用aw_memheap_alloc()分配200字节的内存块，得到的内存块地址范围为：3 ~ 203，示意图详见图9.15(a)。此时，若同样返回顺序第一个对齐的地址给用户，即：8。由于用户需要的是200字节的内存块，因此，对于用户来讲，其使用的内存块地址范围为 ：8 ~ 208，显然，204 ~ 208 这段空间并不是通过分配得到的有效内存，使得用户得到了一段非法的内存空间，一旦访问，极有可能导致应用出错。示意图详见图9.15 (b)。

图9.15 内存对齐的处理——未多分配align-1字节的空间

实际中，由于align - 1的值往往是一些比较特殊的奇数值，例如：3、7、15、31等，经常如此分配容易把内存块的首地址打乱，出现很多非对齐的地址。因此，往往会直接多分配align字节的内存空间。

同时，出于效率考虑，在AWorks中，每次分配的内存往往都按照默认的CPU自然对齐字节数对齐，例如，在32位系统中，默认分配的所有内存都按照4字节对齐，基于此，aw_mem_alloc()函数的实现可以更新为如程序清单9.10所示的程序。 

程序清单9.10 aw_mem_alloc()函数分配的内存按照4字节对齐

4.  重新调整内存大小

有时候，需要动态调整分配内存块的大小，如果一开始分配了一个较小的内存块，但随着数据的增加，内存不够，此时，则可以使用该函数重新调整之前分配的内存块大小。其函数原型为：

其中，ptr为使用aw_mem_alloc()、aw_mem_calloc()或aw_mem_align()函数分配的内存块首地址，即调用这些函数的返回值。new_size为调整后的大小。返回值为调整大小后的内存块首地址，特别地，若调整大小失败，则返回值为NULL。

例如，首先使用aw_mem_alloc()分配了存储1个int类型数据的内存块，然后重新调整内存块的大小，使其可以存储2个int类型的数据。范例程序详见程序清单9.11。

程序清单9.11 内存分配范例程序（重新调整内存大小）

5.  释放内存

前面讲解了4种分配内存块的方法，无论使用何种方式动态分配的内存块，在使用结束后，都必须释放，否则将造成内存泄漏。释放内存块的函数原型为：

其中，ptr为使用aw_mem_alloc()、aw_mem_calloc()、aw_mem_align()或aw_mem_realloc()函数分配的内存块首地址，即调用这些函数的返回值。

当使用aw_mem_free()将内存块释放后，相应的地址空间将变为无效，用户不能再继续使用。释放内存块的范例程序详见程序清单9.12。

程序清单9.12 释放内存块的范例程序

9.2  内存池

堆管理器极为灵活，可以分配任意大小的内存块，非常方便。但其也存在明显的缺点：一是分配效率不高，在每次分配时，都要依次查找所有空闲内存块，直到找到一个满足需求的空闲内存块；二是容易产生大小各异的内存碎片。

为了提高内存分配的效率，以及避免内存碎片，AWorks提供了另外一种内存管理方法：内存池（Memory Pool）。其舍弃了堆管理器中可以分配任意大小的内存块这一优点，将每次分配的内存块大小设定为固定值。

由于每次分配的内存块大小为固定值，没有空间大小的限制，因此，在用户每次申请内存块时，分配其第一个空闲内存块即可，无需任何查找过程，同理，在释放一个内存块时，也仅需将其标志为空闲即可，无需任何额外的合并操作，这极大的提高了内存分配和释放的效率。

同时，由于每次申请和释放的内存块都是同样的大小，只要存在空闲块，就可以分配成功，某几个空闲内存块不可能由于被某一已分配的内存块分割而导致无法使用。这种情况下，任一空闲块都可以被没有限制的分配使用，不再存在任何内存碎片，彻底避免了内存碎片。 

但是，将内存块大小固定，会限制其使用的灵活性，并可能造成不必要的内存空间浪费，例如，用户只需要很小的一块内存空间，但若内存池中每一块内存都很大，这就会使内存分配时不得不分配出一块很大的内存，造成了内存浪费。这就要求在定义内存池时，应尽可能将内存池中内存块的大小定义为一个合理的值，避免过多的内存浪费。

系统中可以存在多个内存池，每个内存池包含固定个数和大小的内存块。基于此，在实际应用中，为了满足不同大小的内存块需求，可以定义多种尺寸（内存池中内存块的大小）的内存池（比如：小、中、大三种），然后在实际应用中根据实际用量选择从合适的内存池中分配内存块，这样可以在一定程度上减少内存的浪费。

9.2.1  内存池原理概述

内存池用于管理一段连续的内存空间，由于各个内存块的大小固定，因此，首先将内存空间分为若干个大小相同的内存块，例如，管理1024字节的内存空间，每块大小为128字节。则共计可以分为8个内存块。初始时，所有内存块均为空闲块，示意图详见图9.16。

图9.16 初始状态——8个空闲块

在AWorks中，为便于管理，将各个空闲内存块使用单向链表的形式组织起来，示意图详见图9.17。

图9.17 以单向链表的形式组织各个空闲块

这就要求一个空闲块能够存放一个p_next指针，以便组织链表。在32位系统中，指针的大小为4个字节，因此，要求各个空闲块的大小不能低于4个字节。此外，出于对齐考虑，各个空闲块的大小必须为自然对齐字节数的正整数倍。例如，在32位系统中，块大小应该为4字节的整数倍，比如：4、8、12、6……而不能为5、7、9、13等。

基于此，当需要分配一个内存块时，只需从链表中的取出第一个空闲块即可。例如，需要在图9.17的基础上分配一个内存块，可以直接从链表中取出第一个空闲块，示意图详见图9.18。

图9.18 从链表中取出一个内存块

此时，空闲块链表中，将只剩下7个空闲块，示意图详见图9.19。

图9.19 剩余7个空闲块

值得注意的是，虽然在空闲块链表中，各个内存块中存放了一个p_next指针，占用了一定的内存空间，但是，当该内存块从空闲链表中取出，分配给用户使用时，已分配的内存块并不需要组织为一个链表，p_next的值也就没有任何意义了，因此，用户可以使用内存块中所有的内存，不存在用户不可访问的区域，不会造成额外的空间浪费。

而在堆管理器中，无论是空闲块还是已分配的内存块，头部存储的相关信息都必须保持有效，其占用的内存空间用户是不能使用的，对于用户来讲，这相当于造成了一定的内存空间浪费。

当用户不再使用一个内存块时，需要释放相应的内存块，释放时，直接将内存块重新加入空闲块链表即可。示意图详见图9.20。

图9.20 释放一个内存块

释放后，空闲链表中将新增一个内存块，示意图详见图9.21。

图9.21 释放后，新增一个内存块

由此可见，整个内存池的分配和释放操作都非常简单。分配时，从空闲链表中取出一个内存块，释放时，将内存块重新加入空闲链表中。

9.2.2  内存池接口

AWorks提供了内存池软件库，用户通过相关接口使用即可。相关函数的原型详见表9.3。

表9.3 内存池接口（aw_pool.h）

1.  定义内存池实例

在使用内存池前，必须先使用aw_pool_t类型定义内存池实例，该类型在aw_pool.h中定义，具体类型的定义用户无需关心，仅需使用该类型定义内存池实例即可，即：

其地址即可作为初始化接口中p_pool参数的实参传递。

一个内存池可以管理一段连续的内存空间，在AWorks中，可以使用多个内存池，以分别管理多段连续的内存空间。此时，就需要定义多个内存池实例，例如：

为了满足各种大小的内存块需求，可以定义多个具有不同内存块大小的内存池。例如：定义小、中、大三种尺寸的内存池，它们对应的内存块大小分别为8、64、128。用户根据实际用量选择从合适的内存池中分配内存块，以在一定程度上减少内存的浪费。

2.  初始化内存池

定义内存池实例后，必须使用该接口初始化后才能使用，以指定内存池管理的内存空间，以及内存池中各个内存块的大小。其函数原型为：

其中，p_pool指向待初始化的内存池，即使用aw_pool_t类型定义的内存池实例；p_pool_mem为该内存池管理的实际内存空间首地址；pool_size指定整个内存空间的大小；item_size指定内存池中每个内存块的大小。

函数的返回值为内存池ID，其类型aw_pool_id_t，该类型的具体定义用户无需关心，该ID可作为其它功能接口的参数，用以表示需要操作的内存池。特别地，若返回ID的值为NULL，表明初始化失败。

初始化时，系统会将pool_size大小的内存空间，分为多个大小为item_size的内存块进行管理。例如，使用内存池管理1KB的内存空间，每个内存块的大小为16字节，初始化范例程序详见程序清单9.13。

程序清单9.13 初始化内存池

程序中，将1024字节的空间分成了大小为16字节的内存块进行管理。注意，出于效率考虑，块大小并不能是任意值，只能为自然对齐字节数的正整数倍。例如，在32位系统中，块大小应该为4字节的整数倍，若不满足该条件，初始化时，将会自动向上修正为4字节的整数倍，例如，块大小的值设置为5，将被自动修正为8。用户可以通过aw_pool_item_size ()函数获得实际的内存块大小。

3.  获取内存池中实际的块大小

前面提到，初始化时，为了保证内存池的管理效率，可能会对用户传入的块大小进行适当的修正，用户可以通过该函数获取当前内存池中实际的块大小。其函数原型为：

其中，pool_id为初始化函数返回的内存池ID，其用于指定要获取信息的内存池。返回值即为内存池中实际的块大小。

例如，初始化时，将内存池的块大小设定为5，然后通过该函数获取内存池中实际的块大小。范例程序详见程序清单9.14。

程序清单9.14 获取内存池中实际的块大小

运行程序可以发现，实际内存块的大小为8。

实际应用中，为了满足不同容量内存申请的需求，可以定义多个内存池，每个内存池定义不同的块大小。如定义3种块大小尺寸的内存池，分别为8字节（小）、64字节（中）、128字节（大）。范例程序详见程序清单9.15。

程序清单9.15 定义多种不同块大小的内存池

程序中，将三种类型内存池的总容量分别定义为了512、1024、2048。实际中，应根据情况定义，例如，小型内存块需求量很大，则应该增大对应内存池的总容量。

4.  获取内存块

内存池初始化完毕后，用户可以从内存池中获取固定大小内存块，其函数原型为：

其中，pool_id为初始化函数返回的内存池ID，其用于指定内存池，表示从该内存池中获取内存块。返回值为void *类型的指针，其指向获取内存块的首地址，特别地，若返回值为NULL，则表明获取失败。从内存池中获取一个内存块的范例程序详见程序清单9.16。

程序清单9.16 获取内存块范例程序

5.  释放内存块

当获取的内存块使用完毕后，应该释放该内存块，将其返还到内存池中。其函数原型为：

其中，pool_id为初始化函数返回的内存池ID，其用于指定内存池，表示将内存块释放到该内存池中。p_item为使用aw_pool_item_get()函数获取内存块的首地址，即调用aw_pool_item_get()函数的返回值，表示要释放的内存块。

返回值为aw_err_t类型的标准错误号，若值为AW_OK，表示释放成功，否则，表示释放失败，释放失败往往是由于参数错误造成的，例如，释放一个不是由aw_pool_item_get()函数获取的内存块。注意，内存块从哪个内存池中获取，释放时，就必须释放到相应的内存池中，不可将内存块释放到其它不对应的内存池中。

当使用aw_pool_item_return()将内存块释放后，相应的内存空间将变为无效，用户不能再继续使用。释放内存块的范例程序详见程序清单9.17。

程序清单9.17 释放内存块范例程序

               </div>
            <!--<div class="side-box author-article">
                <a href="/d/user/2671042/" target="_blank">
                        <h2 class="title">
                            周立功单片机
                            技术专区</h2>
                    </a>
                    
                <ul class="txt-list">
                    <li><a href="/d/922003.html">E523.52—高集成度电机控制芯片</a></li><li><a href="/d/906380.html">智能门锁生命线！一“芯”当关，安全守护</a></li><li><a href="/d/905625.html">新一代车载T-Box集成以太网网关的控制方案解析</a></li><li><a href="/d/904695.html">电源模块的可靠性设计有何秘籍？</a></li><li><a href="/d/904646.html">ZLG72128数码管显示驱动及键盘扫描管理芯片</a></li>                    </ul>
            </div>-->

            <!-- 文章增加的调整 -->
                <iframe id="iframe_tags" data-elecfans_trackid="article_detail" data-tag="内存,数据存储,管理器" src="/static/iframe/course.html" width="100%" height="170" style="border: none; margin: 20px 0px; display: none;"></iframe>
                <div class="hudong clearfix">
                </div>
                 <div class="wx_detail">
                                    <p>原文标题：AWorks软件篇 — 内存管理</p>
                                    <p>文章出处：【微信号：Zlgmcu7890，微信公众号：周立功单片机】欢迎添加关注！文章转载请注明出处。</p>
                            </div>
        </div>