一个简单内存管理器的实现

可能是C/C++用的多一些，看代码的时候总是习惯先看内存分配和管理部分的内容，看完之后心里才觉得踏实。之前看HTK源码的时候发现HTK中实现了一个简单的内存管理器（MemHeap），当时好奇，看了一下实现思路，非常朴素。

HTK的内存管理器提供三种内存分配方法：

• MHEAP 主要针对固定结构的内存分配，初始化的时候确定大小
• MSTAK 可以申请任意大小的内存
• CHEAP 这个基本就是对malloc的简单封装，HTKBook上也不推荐使用这种

我尝试实现了第一种。本身是想在移植的时候替换的，后来发现没必要就没有使用。

第一种的实现逻辑就是先一次性申请一大块内存区域，称为一个Block，它的大小常常是注册分配单元的整数倍。Block通过一个单向链表管理，当有申请请求到来时，找出第一个非空Block的第一个非空区域首地址返回，并标记该区域已经分配。释放的话，只需要简单的将该标记置为未分配即可。如果没有非空Block，就在链表尾部继续分配一块。因为指针本身就是无符号的地址，所以释放内存时，定位需要“释放”的空间在哪个Block里面就很简单，只要依次和当前Block的首地址比较一下地址关系即可。

Demo提供如下接口：

// init and free
Segment *NewSegment(int segLen, int eleLen);
void FreeSegment(Segment *seg);

// alloc/free items
byte* NewItem(Segment *seg);
void FreeItem(Segment *seg, byte *addr);

其中Segment定义如下

typedef unsigned char byte;

struct MemHeap
{
    int segLen;
    int eleLen;
    int newIdx;
    byte *vis;      // 采用bit标记
    byte *data;     // 空间地址
    MemHeap *next;  // next指针
};

由于分配，释放的逻辑在上面已经说明了，代码也很简单，下面直接给出简单实现了。

Segment *NewSegment(int segLen, int eleLen)
{
    Segment *seg = (Segment*)malloc(sizeof(Segment));
    seg->segLen = segLen;
    seg->eleLen = eleLen;
    seg->newIdx = 0;
    seg->vis = (byte*)malloc(segLen / 8 + 1);
    seg->data = (byte*)malloc(segLen * eleLen);
    seg->next = NULL;
    memset(seg->vis, 0, segLen / 8 + 1);
    memset(seg->data, 0, segLen * eleLen);
    return seg;
}


void FreeSegment(Segment *seg)
{
    Segment *cur, *next;
    for(cur = seg; cur != NULL; cur = next)
    {
        next = cur->next;
        if(cur->vis)
            free(cur->vis);
        if(cur->data)
            free(cur->data);
        free(cur);
    }
}

void SetSegVisited(Segment *seg, int pos)
{
    if(pos >= seg->segLen)
    {
        fprintf(stderr, "SetSegVisited: Accessed out of index: %d/%d\n", pos, seg->segLen);
        return;
    }
    seg->vis[pos >> 3] |= 1 << (7 - (pos & 7));
    return;
}

void SetSegUnvisited(Segment *seg, int pos)
{
    if(pos >= seg->segLen)
    {
        fprintf(stderr, "SetSegUnvisited: Accessed out of index: %d/%d\n", pos, seg->segLen);
        return;
    }
    seg->vis[pos >> 3] &= ~(1 << (7 - (pos & 7)));
    return;
}

bool IsSegVisited(Segment *seg, int pos)
{
    if(pos >= seg->segLen)
    {
        fprintf(stderr, "IsSegVisited: Accessed out of index: %d/%d\n", pos, seg->segLen);
        exit(-1);
    }
    return (seg->vis[pos >> 3] & (1 << (7 - (pos & 7)))) != 0;
}

bool IsSegUsedUp(Segment *seg)
{
    return seg->newIdx == seg->segLen;
}

Segment* GetNextSeg(Segment *seg)
{
    Segment *cur, *pre;
    for(cur = seg; cur != NULL; cur = cur->next)
    {
        pre = cur;
        if(!IsSegUsedUp(cur))
            break;
    }
    if(cur == NULL)
    {
        pre->next = NewSegment(pre->segLen, pre->eleLen);
        return pre->next;
    }
    return cur;
}

byte* NewItem(Segment *seg)
{
    Segment *cur = GetNextSeg(seg);

    byte *p = cur->data + cur->eleLen * cur->newIdx;
    SetSegVisited(cur, cur->newIdx);
    // update newIdx
    while(cur->newIdx < cur->segLen)
    {
        if(!IsSegVisited(cur, cur->newIdx))
            break;
        cur->newIdx++;
    }
    ShowSegUse(seg);
    return p;
}

Segment* LocateSeg(Segment *seg, byte *addr)
{
    Segment *cur;
    for(cur = seg; cur != NULL; cur = cur->next)
        if(addr - cur->data < cur->segLen * cur->eleLen)
            break;
    return cur;
}

void FreeItem(Segment *seg, byte *addr)
{
    Segment *cur = LocateSeg(seg, addr);

    int pos = (addr - cur->data) / cur->eleLen;

    SetSegUnvisited(cur, pos);
    // update newIdx
    if(pos < cur->newIdx)
        cur->newIdx = pos;
    ShowSegUse(seg);
}

我觉得这么做在某些情况下还是有较高的可用性的，比如你要（前提是用C）维护一个巨大的Hash表，二叉树，链表，有向图等这些结构的时候，在节点的分配阶段，你不需要注意太多，但是当销毁这些巨大的结构时，特别容易出现所谓的double free错误。有可能在之前动态更新结构的时候，某个节点已经被释放或者重置为NULL了，所以，每次释放，你可能都要无尽的重复着内存合法性的判断。当然，如果用的不是C语言，比如C++的话，我觉得完全没有必要，一方面，析构函数本身就可以处理内存释放的工作，其次就是，数据结构没必要从头自己实现了。