前言

相信各位Cer在使用C语言时对内存管理这一块已经相对熟悉了。但总有一些粗心马虎的时刻，松懈了对内存的管理，这样经常导致不可预料的结果。这往往也是因为内存管理的难于诊断和修复的。那么这一章节让我们来谈谈《C语言接口与实现》是如何做内存管理。

代码综述

代码主要讲以下几个函数

Mem_free ：内存释放

Mem_resize ：内存重开辟

Mem_calloc：开辟内存并清空

dalloc：开辟内存描述符，下述

Mem_alloc ：内存开辟

代码如下，这里简单讲讲代码的主要思路。

这里的内存管理主要通过2个链表来维护，这2个链表抽象地看可以理解为一个内存池。一个的空闲内存块环形表，一个是正在使用的内存块表。代码通过查找空闲内存块表来找到合适的内存，标志该内存后将其加入正在使用的内存块表中

其主要的方法就是让程序掌握足够多的信息，并有效管理这些信息来达到管理的目的，这也是我们编程常用的手段

如果嫌麻烦，各位读者可以先跳过这里的代码。直接查看下面的讲解，主要关注Mem_alloc和Mem_free这2个函数

union align {
#ifdef MAXALIGN
    char pad[MAXALIGN];
#else
    int i;
    long l;
    long *lp;
    void *p;
    void (*fp)(void);
    float f;
    double d;
    long double ld;
#endif
};
#define hash(p, t) (((unsigned long)(p)>>3) & \
    (sizeof (t)/sizeof ((t)[0])-1))
#define NDESCRIPTORS 512
#define NALLOC ((4096 + sizeof (union align) - 1)/ \
    (sizeof (union align)))*(sizeof (union align))
const Except_T Mem_Failed = { "Allocation Failed" };
static struct descriptor {
    struct descriptor *free;
    struct descriptor *link;
    const void *ptr;
    long size;
    const char *file;
    int line;
} *htab[2048];
static struct descriptor freelist = { &freelist };
static struct descriptor *find(const void *ptr) {
    struct descriptor *bp = htab[hash(ptr, htab)];
    while (bp && bp->ptr != ptr)
        bp = bp->link;
    return bp;
}
void Mem_free(void *ptr, const char *file, int line) {
    if (ptr) {
        struct descriptor *bp;
        if (((unsigned long)ptr)%(sizeof (union align)) != 0
        || (bp = find(ptr)) == NULL || bp->free)
            Except_raise(&Assert_Failed, file, line);
        bp->free = freelist.free;
        freelist.free = bp;
    }
}
void *Mem_resize(void *ptr, long nbytes,
    const char *file, int line) {
    struct descriptor *bp;
    void *newptr;
    assert(ptr);
    assert(nbytes > 0);
    if (((unsigned long)ptr)%(sizeof (union align)) != 0
    || (bp = find(ptr)) == NULL || bp->free)
        Except_raise(&Assert_Failed, file, line);
    newptr = Mem_alloc(nbytes, file, line);
    memcpy(newptr, ptr,
        nbytes < bp->size ? nbytes : bp->size);
    Mem_free(ptr, file, line);
    return newptr;
}
void *Mem_calloc(long count, long nbytes,
    const char *file, int line) {
    void *ptr;
    assert(count > 0);
    assert(nbytes > 0);
    ptr = Mem_alloc(count*nbytes, file, line);
    memset(ptr, '\0', count*nbytes);
    return ptr;
}
static struct descriptor *dalloc(void *ptr, long size,
    const char *file, int line) {
    static struct descriptor *avail;
    static int nleft;
    if (nleft <= 0) {
        avail = malloc(NDESCRIPTORS*sizeof (*avail));
        if (avail == NULL)
            return NULL;
        nleft = NDESCRIPTORS;
    }
    avail->ptr  = ptr;
    avail->size = size;
    avail->file = file;
    avail->line = line;
    avail->free = avail->link = NULL;
    nleft--;
    return avail++;
}
void *Mem_alloc(long nbytes, const char *file, int line){
    struct descriptor *bp;
    void *ptr;
    assert(nbytes > 0);
    nbytes = ((nbytes + sizeof (union align) - 1)/
        (sizeof (union align)))*(sizeof (union align));
    for (bp = freelist.free; bp; bp = bp->free) {
        if (bp->size > nbytes) {
            bp->size -= nbytes;
            ptr = (char *)bp->ptr + bp->size;
            if ((bp = dalloc(ptr, nbytes, file, line)) != NULL) {
                unsigned h = hash(ptr, htab);
                bp->link = htab[h];
                htab[h] = bp;
                return ptr;
            } else
                {
                    if (file == NULL)
                        RAISE(Mem_Failed);
                    else
                        Except_raise(&Mem_Failed, file, line);
                }
        }
        if (bp == &freelist) {
            struct descriptor *newptr;
            if ((ptr = malloc(nbytes + NALLOC)) == NULL
            ||  (newptr = dalloc(ptr, nbytes + NALLOC,
                    __FILE__, __LINE__)) == NULL)
                {
                    if (file == NULL)
                        RAISE(Mem_Failed);
                    else
                        Except_raise(&Mem_Failed, file, line);
                }
            newptr->free = freelist.free;
            freelist.free = newptr;
        }
    }
    assert(0);
    return NULL;
}

代码讲解

那我们按照书中顺序来讲解

Mem_free

代码如下

static struct descriptor {
    struct descriptor *free;
    struct descriptor *link;
    const void *ptr;
    long size;
    const char *file;
    int line;
} *htab[2048];

#define hash(p, t) (((unsigned long)(p)>>3) & \
    (sizeof (t)/sizeof ((t)[0])-1))

static struct descriptor freelist = { &freelist };

static struct descriptor *find(const void *ptr) {
    struct descriptor *bp = htab[hash(ptr, htab)];
    while (bp && bp->ptr != ptr)
        bp = bp->link;
    return bp;
}

void Mem_free(void *ptr, const char *file, int line) {
    if (ptr) {
        struct descriptor *bp;
        if (((unsigned long)ptr)%(sizeof (union align)) != 0
        || (bp = find(ptr)) == NULL || bp->free)
            Except_raise(&Assert_Failed, file, line);
        bp->free = freelist.free;
        freelist.free = bp;
    }
}

我们先看看struct descriptor *bp，它就是我们用来管理内存的结构体。其中free跟link分别就是指向不同的2张表，free是指向空闲内存块表(注意：下称F表)，link是指向正在使用的内存块表(注意：下称L表)，其中htab就是这一张L表，从命名可以看出它是一张散列表来的。

可以从下图看出他们的结构，实线是link字段建立的链表，而虚线则是free建立的链表

哈希表和链表

ptr字段就是内存指针，size就是该内存的大小

file和line我们一般不使用，主要是用存储该内存块开辟的文件和行数，有利于定位错误，我们将其称之为坐标

函数首先是通过find找到该指针所在的描述符，如果没找到则进行错误处理，我们这里是直接发生异常，我们可以有更好的处理，包括写入log，打印错误信息等，可以不必要进行异常。

find函数则是对指针进行哈希运算，这里的哈希运算很简单，只是对指针左移3为后进行取模罢，取模大小是哈希表的大小。

如果在在L表中找到了描述符，则返回该描述符。然后将该描述符描述的内存块添加入F表，表示其已经空闲

这里细心的朋友已经发现，这里是没有对内存进行回收的，直接将描述符添加到F表，这样做的坏处就是F表只增不减，笔者觉得这里有待改进，详细的我们后面再谈

Mem_resize

代码如下

void *Mem_resize(void *ptr, long nbytes,
    const char *file, int line) {
    struct descriptor *bp;
    void *newptr;
    assert(ptr);
    assert(nbytes > 0);
    if (((unsigned long)ptr)%(sizeof (union align)) != 0
    || (bp = find(ptr)) == NULL || bp->free)
        Except_raise(&Assert_Failed, file, line);
    newptr = Mem_alloc(nbytes, file, line);
    memcpy(newptr, ptr,
        nbytes < bp->size ? nbytes : bp->size);
    Mem_free(ptr, file, line);
    return newptr;
}

该函数的作用是改变内存块的大小

首先是常规的参数检查，接着就是对ptr进行一个对齐判断，这里是按照硬件平台来严格进行对齐的，对齐对于各位读者来说应该不陌生，这里不多说。有疑问的读者请留言提问吧

接着是使用find查找对应的内存块，然后在后面进行释放操作

使用Mem_alloc开辟内存，然后将内容复制到新内存，释放找到的内存块。返回新的内存指针

Mem_calloc

代码如下

比较简单，相信不用我多做解释，主要是开辟完内存后对内存进行清零

void *Mem_calloc(long count, long nbytes,
    const char *file, int line) {
    void *ptr;
    assert(count > 0);
    assert(nbytes > 0);
    ptr = Mem_alloc(count*nbytes, file, line);
    memset(ptr, '\0', count*nbytes);
    return ptr;
}

dalloc

代码如下

static struct descriptor *dalloc(void *ptr, long size,
    const char *file, int line) {
    static struct descriptor *avail;
    static int nleft;
    if (nleft <= 0) {
        avail = malloc(NDESCRIPTORS*sizeof (*avail));
        if (avail == NULL)
            return NULL;
        nleft = NDESCRIPTORS;
    }
    avail->ptr  = ptr;
    avail->size = size;
    avail->file = file;
    avail->line = line;
    avail->free = avail->link = NULL;
    nleft--;
    return avail++;
}

该函数主要用于用于分配内存描述符

我们独立分配描述符，有利于接触内存分配与描述符分配的耦合，降低描述符被破坏的可能性

这里笔者的理解就是如果将描述符和内存块分配为一个连续的空间，那么我们对内存块进行操作时如果不小心越界了，有可能对描述符的内容进行改写，从而破坏描述符

在函数中nleft是一个静态变量，它的作用就是让函数在描述符不够用时，让程序可能继续开辟描述符

函数一次性创建了NDESCRIPTORS个描述符，然后在每次调用的时候返回一个描述符，直到描述符用尽了就继续创建

注意：这里笔者觉得有些不妥，如同前面Mem_free所说，F表会一直增大。如果我们想要优化内存管理，那么我们需要的是动态的对F表进行管理，那么就涉及到对描述符的管理，当内存被回收时，描述符也应该被回收。如果仅对内存回收(这里的回收不是简单地向F表添加描述符)那么描述符占用的内存将会被泄露。这样才能有效的利用资源，不造成内存泄露。我们后面再说

Mem_alloc

全文最重要的函数，代码如下

void *Mem_alloc(long nbytes, const char *file, int line){
    struct descriptor *bp;
    void *ptr;
    assert(nbytes > 0);
    nbytes = ((nbytes + sizeof (union align) - 1)/
        (sizeof (union align)))*(sizeof (union align));
    for (bp = freelist.free; bp; bp = bp->free) {
        if (bp->size > nbytes) {
            bp->size -= nbytes;
            ptr = (char *)bp->ptr + bp->size;
            if ((bp = dalloc(ptr, nbytes, file, line)) != NULL) {
                unsigned h = hash(ptr, htab);
                bp->link = htab[h];
                htab[h] = bp;
                return ptr;
            } else
                {
                    if (file == NULL)
                        RAISE(Mem_Failed);
                    else
                        Except_raise(&Mem_Failed, file, line);
                }
        }
        if (bp == &freelist) {
            struct descriptor *newptr;
            if ((ptr = malloc(nbytes + NALLOC)) == NULL
            ||  (newptr = dalloc(ptr, nbytes + NALLOC,
                    __FILE__, __LINE__)) == NULL)
                {
                    if (file == NULL)
                        RAISE(Mem_Failed);
                    else
                        Except_raise(&Mem_Failed, file, line);
                }
            newptr->free = freelist.free;
            freelist.free = newptr;
        }
    }
    assert(0);
    return NULL;
}

首先是参数检查，接着，是对nbytes进行向上舍入，使得其返回的每个指针都能对齐，避免内存对齐的bug。

所谓的向上舍入，举个例子，比如我们想要 20 个字节(在本文这里，对齐的字节16 字节对齐)，那么距离20最近的16的倍数就是32了，那么根据算法我们得到公示(20+15)/2*16也就是35 / 2 *16 = 32，这样我们就能让内存的大小对齐了。

如果读者要问为什么要让内存对齐，这里笔者不赘述，我相信百度谷歌是最好的老师了

接着查找整个F表，如果找到符合的空闲内存，这个空闲内存的大小大于我们对齐后的大小，那么我们就在这个空闲内存中划分出一部分的内存来分配给指针。这里的算法很简单就是移动指针而已，如代码后的图所示。接着分配一个描述符来描述分配出来的内存。最后对得到内存的描述符进行哈希散列，并插入到哈希表中，然后返回该指针。当然啦，如果分配描述符失败将会进行错误处理，这里的错误处理就是发生异常

我们的F表的环形表，如果没找到合适的空闲内存，那么指针会回到表头表明没有找到合适的空闲内存。那么程序就开辟一块内存和一个新的描述符，然后将内存用描述符记录下来，最后将新的描述符插入到空闲表中。插入的位置是表头freelist的下一个，所以当我们继续循环的时候，指针就走到新的内存描述符了，然后对齐进行上面讲述的分配操作。

这里笔者有觉得有些不妥，在章节的习题中也提到了，就是通过的从大内存块中分配小内存块，然后当空闲块的大小小于sizeof union align(在此文是16字节)时，这样的空闲内存块就无法使用了

因为nbytes = ((nbytes + sizeof (union align) - 1)/(sizeof (union align)))*(sizeof (union align));会让nbytes最小为 16 字节。如果空闲内存块小于16字节，那么判断条件if (bp->size > nbytes)将不会通过。

无法使用的内存某种意义上可以说是内存泄露了

划分内存

改进

这里主要是谈谈如何改进上面我们讲到的机制。笔者尝试抛砖引玉，提出个人的思路，有不妥的地方请各位读者海涵，各位读者也可以在留言中写下自己的想法或者与笔者讨论

归纳

我们先归纳我们觉得不妥的地方再进行一一改进

1、当空闲内存块的内存小于某个对齐的字节数数，我们无法使用该内存块并且会造成内存损失。

2、我们对内存的回收并不有效，单纯地将其放置在空闲内存表中，这样会导致2个缺点，第一是空闲内存表只增不减，降低我们查找的效率。第二是空闲内存块的内存无法得到有效的合并，这一点在章节的习题中也提到。因为我们对空白内存块的记录中size只会减少不会增加，这样并不能将回收的内存块合并到原来的内存中

改进思路

笔者是想通过一些方法来减少F表的增加。因为我们主要是想避免无限的增加F表从而增加效率。

如果是这样的话，笔者的思路通过在回收内存时，分配后的内存归还到原来的F表中。比如F表有内存块A，我们从中划分出内存块B，在我们使用完内存块B后，我们将其释放，但这里的释放是将其合并到原来的内存块A中，而不是直接将内存块B添加到F表。

但这里回产生另外的一些问题，第一是描述内存块B的内存描述符怎么办，如何处理。但继续放任不管吗？那这样我们的内存回收也还不是最彻底的。第二就是如果内存块A与内存块B不是相邻的呢。举个例子，比如F表有内存块A，我们从内存块A中划分出内存块B，然后内存块A还有剩余，我们再划分内存块C。如果是这样，内存块A与内存块B中隔着内存块C，这样我们回收后的内存并不能有效合并。

如果能有效的解决这2个问题，那么这个内存管理的机制我想能够得到进一步的提升

这两个问题的解决方式让笔者想到了linux内核管理内存的一种方式，就是伙伴内存法，各位读者可以百度谷歌一下这个算法。

关于这个问题，笔者从网络上得到一些启发，这里说明一下

首先，我们需要明白一个点，举个例子，如果空闲内存块A划分出内存块B，接着划分出内存块C
那么会有以下的关系，因为空闲内存块A是从最底部开始划分内存的，如下图所示
A->ptr + A->size = C->ptr
C->ptr + C->size = B->ptr

内存划分

我们进行Mem_free的时候，我们不简单的通过直接在F表尾部插入，而是找到对应关系的位置，然后将内存块插入。比如我们将内存块C插入在内存块A的后面，内存块B插入在内存块C的后面。此为第一点

第二点就是分开管理F表和L表，同时也使用F内存描述符来描述F表的内存块，而L内存描述符来描述L表的内存块。

第三点就是dalloc不使用批量创建描述符，而是使用单个创建描述符。笔者也不清楚为何书作者要批量创建，可能是为了可以减少内存碎片。

有了上述2点我们来看看如何修改过程

首先，我们使用Mem_alloc的时候，从F表中找到符合条件的内存块(上述已经讲到)，该内存块使用F内存描述符表示，然后使用划分，我们将划分出来的内存使用L内存描述符描述

使用F内存描述符描述的内存块我们称为F内存块
使用L内存描述符描述的内存块我们称为L内存块

接着，我们使用Mem_free的时候，将L描述符中的内存使用F描述符来描述，然后将其插入对应的位置，如上所述。

最后我们使用一个函数取名为Mem_merge，我们通过遍历F表，找到满足关系的相邻块将其合并。具体过程举个例子
比如F内存块A和F内存块D，他们不相邻，关系如下。
A--->D
A中分出L内存块B和C，然后Mem_free 掉L内存块B和C，将B和C使用F内存描述符描述并插入到F表，得到F表如下
A--->C--->B--->D
我们就可以通过查找相邻2个L内存块是否符合关系，然后将其合并，释放L内存块C和B，最后得到原来的内存表
A--->D

后记

总结一下，本章节主要是通过维护一个哈希表和一个链表来进行内存管理。这两张表通过管理内存描述符来管理内存。而通过内存描述符结构体来记录内存的使用信息从而让内存的管理更加具体和精细

关于改进算法方面，笔者其实觉得并没有根本的解决问题，我们虽然提升了Mem_alloc的效率，但其实我们也降低了Mem_free的效率，因为这里需要去进行F表的操作。按道理来说只是效率的搬移而已

内存管理应该是C语言里的难点了。该书讲述的机制步进让笔者有了更好的内存管理思路，也让笔者在内存使用方面有了更深的理解。如果能够有效的掌握内存管理，对于编程能力是有大大地提升。

本文参考

《c语言接口与实现--内存管理章节理解，含实例》https://blog.csdn.net/ljd680/article/details/78952539