C语言实现内存管理 （一）

我们都知道 c 语言申请内存释放内存是 alloc / free 。直接调用函数就行，但是某些特定的场景无法调用 c 的标准库，比如单片机，资源有限，并没有带 c 的标准库，则需要自己实现 alloc / free，基本上就是先事先在单片机里申请一块连续的内存，然后基于这一块内存实现内存管理。这里通过3种方式实现，以供参考：

因为在单片机上，内存非常有限，大概不到100k，所以能用来额外申请的内存很小，另外不考虑多线程，所以实现内存管理比较简单。多线程的可以参考微软的 minialloc
我们先讨论最简单的一种，定长的方式，单片机很多情况自身的RAM也是这样设计的，也就是不管是 char 、int 都是4个字节，这样会带来内存的一部分浪费。

1. 区块设计

image.png

如上图，需要先申请2块区域：

• 数据区：以4个字节为一块,申请的时候都是返回以块为单位
• 标识区：用来标识数据区那一块是可用的，是可用被申请的，为了节省内存，标识区用一个字节中的一位来标识数据区的一块（4个字节）的可用性。这样，假如申请64块也就是256个字节的数据区，需要8个字节的标识区。

2. 申请和释放

这里实现的是 realloc 方法，而不是 alloc ，区别就是 alloc 每次执行都是申请一块新的内存区域，而 realloc 执行的时候需要传递旧的指针，如果旧的不为空，则相当于给旧的指针扩大或缩小申请的内存。申请基本流程是：
从头遍历标记区，一位一位的查找，这里注意在常规的内存管理一般不会从头遍历，会从上一次申请的地方往下遍历，但是我们这里内存很小，从头遍历也不会影响速度。
找到第一个空闲位（为0），再查找后续的连续空的位数量是否满足申请内存的块数，如果满足，则返回指针，并把申请的所有标识位都改成 1 。比如要申请34个字节，则计算需要9个块（4k一块），则遍历找到第一组连续超过9个块都为空闲的区域返回回去。
如果要释放，也很简单，释放的时候除了把指针传递过来，还需要把释放的大小也传递过来，这样释放的时候只需要把标识区连续的区域标记为0即可。看代码很少，100来行：

////////////////////////////////////////////////////////////////////////
// 固定大小格式，每块占用4个字节（特定的单片机只支持这种方式
// 版本 20220913
//申请的内存区块个数
#define dxheap_block_count 64
//总共占用的字节数需要*4
static unsigned char dxheap[dxheap_block_count * 4];
//需要用count/8个字节来标识每个区块占用还是空闲，1个bit来表示一个区块的情况，0表示空闲，1表示占用
static unsigned char dxheap_empty_flags[dxheap_block_count / 8];

/**
 * @brief 内存块标识占用还是空闲,把一段连续的块标记成占用还是空闲
 *
 * @param tag 0表示空闲，1表示占用
 * @param start_block_index 开始的块序号，从0开始
 * @param count 连续块的个数
 */
void dxheap_flag_write(int tag, int start_block_index, int count)
{
    int index;
    for (index = start_block_index; index < start_block_index + count; index++)
    {
        if (tag)
        {
            dxheap_empty_flags[index / 8] = dxheap_empty_flags[index / 8] | (1 << (index % 8));
        }
        else
        {
            dxheap_empty_flags[index / 8] = dxheap_empty_flags[index / 8] &= ~(1 << (index % 8));
        }
    }
}
//判断第index个块是否被占用 0表示空闲，1表示占用
int dxheap_flag_read(int index)
{
    char c = dxheap_empty_flags[index / 8];
    int pos = index % 8;
    return (c & (1 << pos)) >> pos;
}
//判断从第index个块开始，连续count个块都为空则返回0，否则1
int dxheap_has_count_empty(int index, int count)
{
    int notfound = 0;
    int i = index;
    while (notfound == 0 && i < dxheap_block_count && i <= (index + count))
    {
        notfound = notfound + dxheap_flag_read(i);
        i++;
    }
    return notfound == 0;
}
void *dxheap_alloc(int size)
{
    //先计算需要的块数量
    int count;
    if (size % 4 == 0)
    {
        count = size / 4;
    }
    else
    {
        //内存可能浪费
        count = (size / 4) + 1;
    }
    if (count > dxheap_block_count)
    {
        printf("not enough memory found\n");
        return -1;
    }
    void *result;
    int i = 0;
    while (i < dxheap_block_count)
    {
        int flag = dxheap_flag_read(i);
        if (flag)
        {
            //假如不为空,则跳过到下一块
            i++;
            continue;
        }
        //判断是否能找到count个空闲块
        int isfound = dxheap_has_count_empty(i, count);
        if (isfound)
        {
            dxheap_flag_write(1, i, count);
            return dxheap + i * 4;
        }
        else
        {
            i++;
            continue;
        }
    }
    printf("not enough memory found\n");
    return -1;
}

void dxheap_free(void *ptr, int osize)
{
    //先判断ptr是否是整个数组区域内的指针
    int min = &dxheap[0];
    int max = &dxheap[dxheap_block_count * 4 - 1];
    if (ptr < min || ptr > max)
    {
        return;
    }
    //先算出ptr对应的指针指向第几块,这里index必然是可以整除4的，是块的首地址。除非乱传一个地址过来
    int index = ptr - min;
    index = index / 4;
    //后面osize个字节对应的块也需要置空
    int count = osize / 4;
    if (osize % 4 != 0)
    {
        count++;
    }
    dxheap_flag_write(0, index, count);
    memset(ptr, 0x00, count * 4);
}

void dxheap_init()
{
    //初始化，把整个数组标记为可用，
    memset(dxheap, 0x00, dxheap_block_count * 4);
}

void *dxheap_realloc(void *ptr, int osize, int size)
{
    if (!ptr)
    {
        // ptr为空表示直接alloc一块内存
        void *block = dxheap_alloc(size);
        return block;
    }
    //先判断ptr是否是整个数组区域内的指针,不是的话直接alloc
    int min = &dxheap[0];
    int max = &dxheap[dxheap_block_count * 4 - 1];
    if (ptr < min || ptr > max)
    {
        void *block = dxheap_alloc(size);
        return block;
    }
    //申请一块足够大的新快，把内容复制过去
    int index = ptr - min;
    //有可能osize比size大,这里不用math.min
    int minLength = osize;
    if (osize > size)
    {
        minLength = size;
    }
    void *newBlock = dxheap_alloc(size);
    if (newBlock == -1)
    {
        return newBlock;
    }
    memcpy(newBlock, ptr, minLength);
    //最后释放旧的区域
    dxheap_free(ptr, osize);
    return newBlock;
}

// //////////////////////////////////////////////////////////////////////////////////////

对外暴露的函数主要是 dxheap_realloc,dxheap_free。其中 dxheap_alloc是申请一块新区域，而 dxheap_realloc也是简化了过程，也就是想要扩大或缩小现有指针指向的区块，是先申请一块额外的新块区，然后释放旧块区，而不是在原有区域上操作。
完整的源码包括测试用例，参考 git

参考下一部分