作业

自己实现动态内存分配

jxtxzzw · 11月4日 · 2018年 · · · · · · · 1148次已读

本文写于 2018年11月04日,距今已超过 1 年,距 2018年11月17日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


初始化

初始化必须被调用一次,且只能被调用一次:

if (initialized) {
    perror("You should call function mem_init() once and only once.\n");
    exit(-1);
}
if (initialSize <= 0) {
    perror("Positive integer expected.\n");
    m_error = E_BAD_ARGS;
    return -1;
}

划分内存,直接调用mmap()

void *mem_start = mmap(NULL, initialSize, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0);

那么mmap()的返回值,其实就是整个空闲块列表的头地址。

之后记录头地址的指针地址,然后设置大小,设置链表的next为空表示链表结束:

mem = (MEM_FREE *) mem_start;
mem->size = initialSize - sizeof(MEM_FREE);
mem->next = NULL;

事情就应该到此结束了。

但是,内存要对齐。

所以要通过页表的大小来计算我到底需要多少大小的内存:

int page_size = getpagesize();
initialSize = (initialSize + page_size - 1 + sizeof(MEM_FREE)) / page_size * page_size;

这样计算得到的,就是我最终划分出来的内存的大小。

另外,mmap()里面的文件描述符,定位到/dev/zero

int fd = open("/dev/zero", O_RDWR);
void *mem_start = mmap(NULL, initialSize, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, fd, 0);
close(fd);

除此而外,加上必要的异常处理,例如,initialSize非法值、mmap()出错……

if (initialSize <= 0) {
    perror("Positive integer expected.\n");
    m_error = E_BAD_ARGS;
    return -1;
}
if (mem_start <= 0) {
    perror("Call function mmap() error.\n");
    return -1;
}

两种维护空闲块列表的思路

类似数组的思路

定义一个头结点:

typedef struct head{
    int isFree;
    int size;
} HEAD;

其中isFree表示该块当前是空闲的还是被使用的,size表示该块的大小,该大小不包括表头。

需要记录的信息就是,mem_beginmem_end,每次从内存的初始地址开始遍历,直到内存的结束地址。

1541308606230

如图所示,假设我申请的这块内存是在 $500$ 开始的,表头是 $2$ 个int一共是 $8$ 个字节。

那么,mem_begin就是 $500$,mem_end就是 $712$。

在图示状态下,内存还有 $2$ 个空闲块,一个大小是 $20$,一个大小是 $80$。

有一个正在被使用的内存,大小是 $50$,另一个正在被使用的内存,大小是 $30$。

在这样的模型下面,分配内存就变得非常简单。

在分析的时候,我只是随便找一个空闲块来分配出去,主要是为了方便分析。

具体实现的时候,这个空闲块是通过某种策略(最优算法、最差算法、首次匹配算法、首次循环匹配算法……)来确定的。

现在要申请一个大小为 $50$ 的内存。

那就从mem_begin,即 $500$ 开始遍历,令ptr为 $500$。

先看看ptr->isFree,发现是空闲的,然后检查大小够不够,发现 $20 < 50$ 不够,那就继续。

此时ptr = ptr + sizeof(HEAD) + ptr->size,即 $500+8+20=528$。

先看看ptr->isFree,发现是在使用中的,那就继续。

此时ptr = ptr + sizeof(HEAD) + ptr->size,即 $528+8+50=586$。

用类似的方法,找到了一个放得下的空闲块。

那么怎么分配呢?

首先要把这一块标记为使用中,即设置isFreefalse,然后设置大小为 $50$。

1541309164410

这时候ptr是 $586$,那么ptr + sizeof(HEAD)就是我可以返回出去的地址,即 $586+8=594$就应该是我返回给主程序的地址。

别急着返回!

$80$ 的空间放下了 $50$,剩下的大小要更新。

首先明确了,ptr + sizeof(HEAD)就是我可以返回出去的地址,这个空闲块的结束的地方是ptr + sizeof(HEAD) + ptr->size

对于上面这种情况,就应该是 $644$ 的地方结束。

原来的大小是 $80$,分配出去了 $50$,还剩下了 $22$,因为分配出去一块,还需要多一个表头记录信息,所以不是 $30$,是 $22$。

这也意味着,之后在判断空闲块大小够不够分配的时候,要把多出来的表头的大小也一起考虑进去。

因此,在 $644$ 地方,我要令HEAD* h = (HEAD*)(644); h->isFree = false; h->size = 22;

怎么把 $644$ 地址变成一个表头结点,怎么计算 $22$,怎么维护信息,就是各自实现的问题了。

那么,最后就应该变成下面这个样子。

1541309620888

这时候全部做完了,可以把 $594$ 这个地址返回出去了,分配就结束了。

下面考虑free的事情。

这只是一个指针,不带大小的,如何确定大小,就非常简单了,因为显然,一定是给的 $536,594$ 这些位置的地址,那么给定的ptr - sizeof(HEAD)就可以定位到表头结点,然后设置isFreetrue就好了。

例如,要释放 $594$ 这个位置,那么 $594-8=586$ 就是这个内存对应的表头的位置,直接令 $586$ 的isFreetrue就好了,size都不用动的。

似乎一切都很美好,但是别忘了还有一个事情,空闲块是要合并的。

如果现在内存是 $3$ 个大小为 $10$ 的空闲块,但是我要申请 $20$,明明是够的,但是内存都碎片化了,导致我以为没有足够的空间。

因此要合并。

由于这是数组实现的,所以很显然,每次合并只有可能和自己的左边或者右边合并。

也就是说,当 $594$ 被释放的时候,我只要检查他前面那个是不是空闲的、后面那个是不是空闲的,是,就合并。

例如,$594-8=586$ 被设置成free,然后 $586+8+50=644$ 的地方发现也是空闲的,那么这两块就可以合并。

只需要令 $586$ 的size加上 $644$ 的size再加上sizeof(HEAD)就可以了。

1541310134950

那么怎么找到前面的邻居?

好像通过直接的内存加减不能完成。

但是一定是可以通过某些手段来达到的。

例如,表头增加一个字段?prevnext

可是,表头信息越多,就意味着内存实际可以用的越少,因为我需要大量的空间来记录信息。

如果不这样,至少,从头遍历是可以的,大不了从mem_begin遍历到mem_end,每次加上sizeof(HEAD)ptr->size,直到找到被回收的那个位置的地址。

但是这样似乎花费的时间代价又大了,不划算,效率低。

但是不管怎么说,问题肯定是能解决的,总归是有办法的,而且办法很多,这里就不详细展开了。

那么,用数组实现的思路就介绍清楚了。

不过,这样做还会有一些潜在的风险,下面用链表思路的分析中会指出。

类似链表的思路

内存嘛,用链表来做会更加炫酷

这个思路和上面那个思路是类似的,只是具体实现细节上面考虑的方面各不相同。

也没有孰优孰劣的分别,各有各的特色,也各有各的优点和缺点。

表头我是这样定义的:

typedef struct memory_use_header_t {
    int size;
    long long magic;
} MEM_USE;

typedef struct memory_free_node_t {
    int size;
    struct memory_free_node_t *next;
} MEM_FREE;

我把空闲的链表和使用中的链表分开了。

其中,memory_free_node_t彻底就是一个空闲块链表了,每一个链表的表头记录空闲块的大小,然后指向下一个空闲块。

memory_use_header_t是使用中的块的信息,保留了一个size记录的是使用中这块的大小是多少,以及,一个magic魔术数。

这个魔术数的作用下面会提到。

至于为什么magic我定义了long long

因为我的服务器是 $64$ 位系统的,所以一个指针的大小就是 $8$,加上一个int是 $4$,一共是 $12$,又因为操作系统做了 $8$ 字节内存对齐,所以 $12$ 个字节被对齐到了 $16$ 个字节,于是,sizeof(MEM_FREE)是 $16$。

如果我令MEM_USEint sizeint magic的话,就是 $8$ 个字节,对齐以后还是 $8$ 个字节。

这样会带来什么问题,就是回收的时候要增加很多无谓的判断。

例如,有一个size是 $3$ 的块被分配出去了,那么实际占用的内存是一个 $8$ 的MEM_USE表头加上一个 $3$ 的内存,一共用掉了 $11$。

之后我试图把这个块回收,发现回收的时候,一共只有 $11$,竟然连MEM_FREE的表头都放不下。

当然,之后的作业要求有提到,要做 $8$ 字节对齐,那么,申请size是 $3$ 的块,实际上被分配出去的是 $8$,加上MEM_USE的表头,一共是用掉了 $16$,回收的时候,至少可以放得下MEM_USE的表头,不会出现放不下的情况。

但是,这样的话,这个MEM_FREEsize就是 $0$,白白浪费了一个表头,啥事都没干,还白白要我的代码多判断很多东西。

所以我为了代码简洁,以及运行的高效(不需要各种判断),直接令MEM_USEMEM_FREE的大小是一样的就好了,那就用了一个long long

或许是我懒?

当然,还有一种方案,就是继续把MEM_FREEMEM_USE合并起来。

typedef struct memory_header_t {
    int size;
    void* magic;
} MEM_HEAD;

一个表头扮演两个角色。

当作为MEM_FREE的时候,void* magic指向的是下一个空闲块表头的地址,最后一个空闲块的void* magic指向NULL,即void* magic充当了MEM_FREE* next的角色。

当作为MEM_USE的时候,void* magic = -1,或者在合法地址区间之外的一个地址。

那么,只需要判断MEM_HEAD -> magic 是不是等于(nil)或者别的MAGIC_ADDR就可以判断这是空闲块还是使用中的块。

free = (magic == MEM_IN_USE_MAGIC)

不好,万一正好某个内存是我在用的怎么办?

用0?可以。用一个void* = -1来表示?可以。

但是强行把int当做指针,或者把地址当做int可不是什么好习惯。

void*MEM_HEAD*最好也别混起来用。

下面说说魔术数的使用。

能够由我来free的块,必须是我分配出去的,这意味着,它的地址减去表头的大小,一定是我存放表头信息的地方,且,整个地址,都在我的合法的地址区间之内。

数组实现的并不能解决这个问题——给一个ptr,减去 $8$?

那万一我给了一个:

int a = 3;
free(&a);

a的地址已经是不知道哪里的东西了,根本就不是我所管理的合法区间之内的地址,是别的地方的地址。

你这做了a的地址减去 $8$?那个地方就更不知道在哪里了,那个地方的void*被变成了HEAD*,然后在那个地址修改了free,天知道那个地方原来存的是什么数据,是int b还是某个char* s

而魔术数的出现解决了这个问题,我先减去 $8$,看看,看看那里的魔术数是不是我的魔术数,如果是,那么这就是我分配出去的,否则,就报错。

if (head->magic != MEM_IN_USE_MAGIC) {
    perror("Maybe this pointer is not allocated by my allocator, refused to free.\n");
    m_error = E_BAD_POINTER;
    return (-1);
}

1541312390233

如图所示,空闲块列表是一个链表,head指向的是第一块空闲块的表头所在的地址,这个head->size是 $40$,head->next是下一个空闲块的表头的地址。

之后的空闲块链表的结点也是类似的,记录的是自己空闲块的大小,以及下一个空闲块的地址。

最后一个空闲块的next指向的是NULL

而,使用中的块,其实只需要记录size就可以了,不需要串成链表。

1541312597676

下面就可以开始分配了。

我通过某种方法判断到了,需要分配的空闲块的地方在 $546$ 这个地方,我申请的大小是 $10$,放得下,加上表头也只有 $26$。

那么我就做如下修改。

首先,令ptr指向 $546$,然后ptr+sizeof(MEM_USE)就是我要返回的地址,即,分配以后返回的地址是 $546+16=562$。

由于上面保证了MEM_FREEMEM_USE的大小是一样的,所以这里不需要做额外的计算。

别急着返回!

还修改新的空闲块信息。

$562$ 开始的 $10$ 大小,是我要分配出去的,那么,下一个空闲块表头,应该存放在 $562+10=572$ 的地方。

这个空闲块的大小,应该是原来的 $40$,减去分配出去的 $10$ 和一个 $16$ 的表头,$40-10-16=14$。

那么在 $572$ 的地方,设置size是 $14$,更新next指针为原来的那个空闲块的next

特别的,对于空闲块列表的第一个空闲块被分配出去的时候,一定要修改空闲块列表的表头head指向的地方。

同样,对于最后一个空闲块列表分配的时候,记得next要指向NULL

中间的其他的,就如同一般的链表维护,注意指向它的指针,以及它指向的下一个的指针,就没问题了。

1541313097258

得到的应该是类似这样子的。

回收似乎会麻烦一点。

首先,给定一个地址,要回收。

先减去 $16$,看看魔术数是不是我定义的,如果是我定义的,那就可以回收,否则拒绝回收。

那么如果需要回收,是不是就简单地修改表头结点就可以了呢?

由于上面保证了,MEM_USEMEM_FREE的大小是一样的,且第一个数据域成员都是size,所以表头大小一样,意味着挂回空闲块列表的时候,表头的大小是不受影响的,也就是说size是不需要修改的。

所以,似乎只要简单地把magic换成next就好了。

事实上也确实如此。

但是,挂到哪儿呢?

最简单的,就是挂在表头,或者表的末尾。

不妨挂在表头。

那么就是简单地,令ptr->next = head,然后令head = ptr就好了。

1541313704911

如图,原来的空闲块列表是蓝色的,现在回收了一个绿色的,那么直接做一下指针的修改就可以了。

合并,也非常简单,因为自己就是表头,所以只能和自己后面的那个合并,不需要通过某种手段找到自己前面的空闲块在哪里。

如上面说的,将新的空闲块挂在了链表的表头以后,只需要做如下的计算。

首先明确,自己的开始的地址是head,自己的结束的地址是head + sizeof(HEAD) + head->size

自己的next的开始的地址是head->next,自己的next的结束的地址是head->next + head->next->size + sizeof(HEAD)

  • 如果head + sizeof(HEAD) + head->size等于head->next,说明自己后面那个块,和自己是紧紧相邻的,就在自己后面,那么这时候只需要将自己的head->size加上sizeof(HEAD)再加上自己的head->next->size就可以了,然后修改自己的head->nexthead->next->next
  • 如果head->next + head->next->size + sizeof(HEAD)等于head,类似地,只需要修改head->next->size = head->next->size + head->size + sizeof(HEAD)并修改head = head->next

注意这些操作都需要计算sizeof(HEAD)的大小。

似乎没事?但是间隔着回收就发现有问题了。

1541314286127

按照$1,3,5,2,4$的顺序回收,就会发现,根本没有可以合并的块。

回收$1$的时候,和空闲块不是相邻的,不能合并。

1541314374178

回收了$3$,也不能合并。

1541314411290

全部回收完,根本没有可以合并的块,全部是不连着的。

1541314494037

但是事实上,全部都是空闲的。

所以有没有一种机制能够检测这种情况?

当然有。

最坏的情况,遍历总是可以完成的。

对于给定的块,遍历所有的块,计算所有的块的ptrptr + sizeof(HEAD) + ptr->size,比较所有这些地址,总能找到和给定的块相邻的两个块的地址,只要他们是空闲的。

然后,就一定可以通过某种机制通过next指针的指来指去,完成相邻的块的合并。

操作也不复杂,就是链表的基本操作嘛。

然后,对于所有的块,重复执行上面的过程,在一个 $N^2$ 的遍历中,一定可以完成所有块的合并。

如果嫌烦,那就把回收回来的块,不要挂在链表头上了,直接放到指定的地方。

所谓指定的地方,就是他被分配出去的地方。

然后一经放回,就立刻和左右邻居合并。

我用的就是这个策略,我会在下面的代码实现过程中详细说明这个操作过程。

输出空闲块列表

在实现之前,先完成mem_dump()函数,要看个结果。

因为空闲块是以链表的形式保存的。

mem指向的是空闲块列表的第一个空闲块。

所以,只要遍历链表,就可以输出每一个空闲块的信息。

while (block != NULL) {
    void *beginAddr = (void *) block;
    int size = block->size;
    void *from = beginAddr + sizeof(MEM_FREE);
    void *to = from + size;
    MEM_FREE *next = block->next;
    printf("Header begin at %p, size=%d, from %p to %p, next %p.\n", beginAddr, size, from, to, next);
    block = next;
}

空闲块列表遍历的时候是不应该出现异常的,因为维护恰当的话,整个过程都是正确的,直到遍历到链表结束,正常退出。

但是需要注意一种情况,那就是没有调用mem_init()就尝试mem_dump()

这种时候是不允许进行的,所以要给出未初始化的错误提示。

if (!initialized) {
    perror("You should call function mem_init() once and only once.\n");
    exit(-1);
}

内存的分配

核心代码

如上文所言,我通过某种分配策略找到了一个可以放得下的空闲块。

得到了这个空闲块的指针block

然后,只要设置block->size为请求的大小,并返回block + sizeof(MEM_USE)的地址。

在返回之前,要维护空闲块,newFreeBlock = block + block->size + sizeof(MEM_USE)就是新的空闲块的地址,在这个新的地址上,设置newFreeBlock->size = 原block->size - 请求的size - sizeof(MEM_USE),设置newFreeBlock->next = 原block->next

代码如下:

int newSize = block->size - sizeq - sizeof(MEM_USE);
MEM_FREE *next = block->next;
MEM_USE *head = (MEM_USE *) block;
head->size = sizeq;
head->magic = MEM_IN_USE_MAGIC;
void *ptr = (void *) head + sizeof(MEM_USE);
block = (MEM_FREE *) (ptr + sizeq);
block->size = newSize;
block->next = next;
return ptr;

当然,特别的,如果分配出去的内存是第一块或者最后一块,还要注意修改空闲块列表的表头的指针。中间其他的部分,只要维护前prev和后next的指针就可以了。

if (last == NULL) {
    mem = block; // 第一块被分配出去了,修改空闲块的表头指针
} else {
    last->next = block; // 否则,block->prev->next修改为新的空闲块的地址
}

多种分配策略

三种分配策略是比较简单的,就是找到合适的内存块。

首次匹配策略,就是找到第一个放得下的。

case M_FIRSTFIT:
while (block != NULL) {
    size = block->size;
    if (sizeq + sizeof(MEM_USE) < size) {
        target = block;
        break;
    } else {
        last = block;
        block = block->next;
    }
}
break;

最优匹配,就是找放得下的里面最小的。

那就要先遍历一遍,然后找到放得下的里面最小的,顺便记录一下它的prev方便后面做事情。

case M_BESTFIT:
while (block != NULL) {
    size = block->size;
    if (sizeq + sizeof(MEM_USE) < size) {
        if (target == NULL || size < target->size) {
            prev = last;
            target = block;
        }
    }
    last = block;
    block = block->next;
}
break;

最差匹配,类似的,遍历一遍,找到最大的空闲块,然后顺便记录一下最大这个的prev

case M_WORSTFIT:
while (block != NULL) {
    size = block->size;
    if (sizeq + sizeof(MEM_USE) < size) {
        if (target == NULL || size > target->size) {
            prev = last;
            target = block;
        }
    }
    last = block;
    block = block->next;
}
break;

然后做一下异常处理,譬如,全部遍历完,发现没有放得下的空间了,就应该是返回一个错误。

if (target == NULL) {
    printf("No free space.\n");
    m_error = E_NO_SPACE;
    return NULL;
}

又例如,要做 $8$ 字节对齐。

int roundup = 8;
sizeq = ((sizeq / roundup) + 1) * roundup;

诸如其他细节,实现的时候留意一下。

内存的回收

核心代码

一些常规的异常就不提了:没有初始化、检查是不是自己分配出去的块……

下面就是回收。

如上文所提及的,我想要把回收回来的块,直接放在属于它自己的位置。

如上面说的,将新的空闲块挂在了链表的表头以后,只需要做如下的计算。

首先明确,自己的开始的地址是head,自己的结束的地址是head + sizeof(HEAD) + head->size

自己的next的开始的地址是head->next,自己的next的结束的地址是head->next + head->next->size + sizeof(HEAD)

  • 如果head + sizeof(HEAD) + head->size等于head->next,说明自己后面那个块,和自己是紧紧相邻的,就在自己后面,那么这时候只需要将自己的head->size加上sizeof(HEAD)再加上自己的head->next->size就可以了,然后修改自己的head->nexthead->next->next
  • 如果head->next + head->next->size + sizeof(HEAD)等于head,类似地,只需要修改head->next->size = head->next->size + head->size + sizeof(HEAD)并修改head = head->next

注意这些操作都需要计算sizeof(HEAD)的大小。

MEM_USE *head = (void *) (ptr - sizeof(MEM_USE));
void *blockStart = (void *) head;
void *blockEnd = ((void *) head + head->size + sizeof(MEM_USE));
MEM_FREE *location = (MEM_FREE *) mem;
MEM_FREE *last = NULL;

然后遍历,找到属于自己的位置,所谓属于自己的位置,就是,自己的开始地址,小于后一个块的开始地址,大于前一个块的开始地址。

while (location != NULL && (void *) blockStart > (void *) location) {
    last = location;
    location = location->next; 
    // 如果是这样维护的,那么空闲块一定是有序的,所以location的next一定大于当前空闲块结束的地方
}

直接把回收的块放在这里,修改前后的next指针就可以了。

回收的合并

因为内存已经放在了指定的位置,且我们遍历的时候已经留下了prevblocknext,只需要看前后两邻居是不是空闲的、且计算是不是内存地址相邻,就可以完成合并。

以往后合并为例。

先计算出空闲块的结束的地址。

lastEnd = (void *) last + last->size + sizeof(MEM_FREE);

如果地址重合,说明可以合并,修改size即可。

if (lastEnd == blockStart) {
    last->size += head->size + sizeof(MEM_USE);
    merg = 1;
}

向前合并也是类似的。

block->size = head->size + sizeof(MEM_USE) + location->size;
block->next = location->next;

但是需要特别注意的,如果这个回收回来的块,既和前面可以合并,又和后面可以合并,需要注意,它的size只能被加一次,而不能前面加一次,后面又加一次。

if (last != NULL && lastEnd == blockStart) {
    last->size += location->size + sizeof(MEM_FREE);
    last->next = location->next;
}

以及,常规问题,如果合并在了链表头或者别的什么情况,那要注意修改空闲块的头地址。

if (last == NULL) {
    mem = block;
} else {
    last->next = block;
}

在不需要合并的情况下,只要简单地修改前后指针,把他插入到链表的给定位置就可以了。

block->size = head->size;
last->next = block;
block->next = location;

特别的,当插入到表头之前,或者表尾之后,需要特别的处理。

if (merg) 
    return 0;
if (last == NULL) {
    block->next = mem;
    block->size = head->size + sizeof(MEM_USE) - sizeof(MEM_FREE);
    mem = block;
} else if (location == NULL) {
    block->next = NULL;
    last->size = head->size 
}

简单的测试

int main(int argc, const char *argv[]) {
    printf("sizeof(MEM_FREE)=%d\n", sizeof(MEM_FREE));
    printf("sizeof(MEM_USE)=%d\n", sizeof(MEM_USE));
    printf("=================\n");
    mem_init(5000);
    printf("After mem_init(5000):\n");
    mem_dump();
    printf("=================\n");
    void *a = mem_alloc(1000, M_FIRSTFIT);
    printf("After mem_alloc(1000, M_FIRSTFIT):\n");
    mem_dump();
    printf("=================\n");
    void *b = mem_alloc(500, M_BESTFIT);
    printf("After mem_alloc(500, M_BESTFIT):\n");
    mem_dump();
    printf("=================\n");
    mem_free(a);
    printf("After free a:\n");
    mem_dump();
    printf("=================\n");
    void *c = mem_alloc(200, M_BESTFIT);
    printf("After mem_alloc(200, M_BESTFIT):\n");
    mem_dump();
    printf("=================\n");
    void *d = mem_alloc(200, M_WORSTFIT);
    printf("After mem_alloc(200, M_WORSTFIT):\n");
    mem_dump();
    printf("=================\n");
    mem_free(b);
    printf("After free b:\n");
    mem_dump();
    printf("=================\n");
    mem_free(d);
    printf("After free d:\n");
    mem_dump();
    printf("=================\n");
    mem_free(c);
    printf("After free c:\n");
    mem_dump();
    return 0;
}

一切正常。

sizeof(MEM_FREE)=16
sizeof(MEM_USE)=16
=================
After mem_init(5000):
Header begin at 0x7f82ac153000, size=8176, from 0x7f82ac153010 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=8176,next=(nil)
new size=7152
next=(nil)
After mem_alloc(1000, M_FIRSTFIT):
Header begin at 0x7f82ac153400, size=7152, from 0x7f82ac153410 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=7152,next=(nil)
new size=6632
next=(nil)
After mem_alloc(500, M_BESTFIT):
Header begin at 0x7f82ac153608, size=6632, from 0x7f82ac153618 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free a:
Header begin at 0x7f82ac153000, size=1008, from 0x7f82ac153010 to 0x7f82ac153400, next 0x7f82ac153608.
Header begin at 0x7f82ac153608, size=6632, from 0x7f82ac153618 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=1008,next=0x7f82ac153608
new size=784
next=0x7f82ac153608
After mem_alloc(200, M_BESTFIT):
Header begin at 0x7f82ac1530e0, size=784, from 0x7f82ac1530f0 to 0x7f82ac153400, next 0x7f82ac153608.
Header begin at 0x7f82ac153608, size=6632, from 0x7f82ac153618 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=6632,next=(nil)
new size=6408
next=(nil)
After mem_alloc(200, M_WORSTFIT):
Header begin at 0x7f82ac1530e0, size=784, from 0x7f82ac1530f0 to 0x7f82ac153400, next 0x7f82ac1536e8.
Header begin at 0x7f82ac1536e8, size=6408, from 0x7f82ac1536f8 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free b:
Header begin at 0x7f82ac1530e0, size=1304, from 0x7f82ac1530f0 to 0x7f82ac153608, next 0x7f82ac1536e8.
Header begin at 0x7f82ac1536e8, size=6408, from 0x7f82ac1536f8 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free d:
Header begin at 0x7f82ac1530e0, size=7952, from 0x7f82ac1530f0 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free c:
Header begin at 0x7f82ac153000, size=8176, from 0x7f82ac153010 to 0x7f82ac155000, next (nil).
End of MEM_FREE.


编译成库

删掉main()函数,然后在makefile写上:

libmem: mem.c
    gcc -c -fpic mem.c
    gcc -shared -o libmem.so mem.o

1542447950994

幕后

zerol 给出了一个更简洁的写法,当然,这样的代价就是,表头浪费的空间太多了,需要 24 个字节,为此,zerol 辩解称“它页表不是 4096 吗,我才用了 24,但是写起来就很舒服,你那样写,写复杂了”。

以下是部分代码:

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdbool.h>
#include <sys/mman.h>
#include <assert.h>
#include "mem.h"

#define MEM_IN_USE_MAGIC 11235813

char buf[10000000];
typedef struct orzKBlack {
    size_t sz;
    int used;
    struct orzKBlack *pre, *nxt;
} P;
P *head = &buf;
const size_t P_SZ = sizeof(P);
int pgsz;

void try_merge(P* p) {
    if (!p) return;
    if (p->used == MEM_IN_USE_MAGIC) return;
    if (!p->nxt || p->nxt->used == MEM_IN_USE_MAGIC) return;
    p->sz += P_SZ + p->nxt->sz;
    p->nxt = p->nxt->nxt;
}

int mem_free(void* ptr) {
    P* p = ptr - P_SZ;
    if (p->used != MEM_IN_USE_MAGIC) {
        assert(0);
    }
    p->used = -1;
    try_merge(p);
    try_merge(p->pre);
    return 0;
}

void* fix(P* p, size_t sz) {
    p->used = MEM_IN_USE_MAGIC;
    void* res = (void*)p + P_SZ;
    P* pp = res + sz;
    pp->nxt = p->nxt;
    pp->pre = p;
    if (p->nxt) p->nxt->pre = pp;
    p->nxt = pp;
    pp->sz = p->sz - sz - P_SZ;
    p->sz = sz;
    return res;
}

void* mem_alloc(int _sz, int tp) {
    if (_sz <= 0) {
        assert(0);
    }
    size_t sz = _sz;
    sz = ((sz - 1) / pgsz + 1) * pgsz;
    if (tp == M_FIRSTFIT) {
        for (P* u = head; u != NULL; u = u->nxt)
            if (sz <= u->sz + P_SZ) return fix(u, sz);
    }
    assert(0);
}

void mem_dump() {
    puts("-------------");
    for (P* u = head; u != NULL; u = u->nxt) {
        printf("%p %d %lu %p %p\n", u, u->used, u->sz, u->pre, u->nxt);
    }
    puts("-------------");
}

int main() {
    head->sz = 100000 - P_SZ;
    head->pre = head->nxt = NULL;
    head->used = -1;
    pgsz = getpagesize();

    printf("sizeof p: %lu\n", P_SZ);
    printf("pgsz : %d\n", pgsz);

    mem_dump();
    void* hhh = mem_alloc(6000, M_FIRSTFIT);
    mem_dump();
    void* hhhh = mem_alloc(70000, M_FIRSTFIT);
    mem_dump();
    mem_free(hhh);
    mem_dump();
    mem_free(hhhh);
    mem_dump();
}

下载

mem.c

50 条回应
    曦枫 2019-11-25 · 7:55
    Chrome 76.0.3809.87 Windows 10

    thx

    a 2019-11-24 · 11:59
    Chrome 78.0.3904.108 Linux

    a

    123321 2019-11-11 · 10:33
    Chrome 76.0.3809.132 Windows 10

    thx

    a 2019-11-4 · 14:05
    Chrome 73.0.3683.103 Linux

    tttqqqlll

    coming again 2019-11-4 · 9:34
    Chrome 77.0.3865.120 Windows 10

    66666666

    eke 2019-11-3 · 19:20
    Firefox 70.0 Windows 10

    .

    の3 2019-11-3 · 19:03
    Edge 17.17134 Windows 10

    esfwfe

    zzjs 2019-11-3 · 16:20
    Edge 18.18362 Windows 10

    6

    tql 2019-11-3 · 14:04
    Chrome 78.0.3904.70 Windows 10

    tql

    eke 2019-11-3 · 13:30
    Edge 18.18362 Windows 10

    Tom 2019-11-2 · 22:07
    Chrome 77.0.3865.120 Windows 10

    .

    mion 2019-11-2 · 18:04
    Edge 18.18362 Windows 10

    tql

    msw 2019-11-2 · 14:46
    Chrome 78.0.3904.87 Windows 10

    66666

    zxm 2019-11-2 · 7:47
    Opera 12.14 Windows Vista

    666

    666 2019-11-1 · 20:02
    QQ浏览器 10.5.3751.400 Windows 10

    6

    666 2019-11-1 · 20:01
    QQ浏览器 10.5.3751.400 Windows 10

    1

    zxx 2019-10-31 · 20:52
    Edge 18.18362 Windows 10

    ead

    555 2019-10-31 · 19:45
    Firefox 68.0 Ubuntu Linux

    6

    zkksssq 2019-10-31 · 15:54
    Chrome 78.0.3904.70 Windows 10

    nb

    chuuu 2019-10-31 · 12:15
    Chrome 77.0.3865.120 Windows 10

    tql

    1 2019-10-30 · 16:52
    Edge 18.18362 Windows 10

    1

    违规昵称hkhweioceryfsdfsljvkdjvlfjdsliurpwiauripawr 2019-10-30 · 14:20
    Chrome 76.0.3809.132 Windows 10

    tql

    cn 2019-10-30 · 9:07
    Chrome 77.0.3865.120 Windows 10

    tql

    wanna 2019-10-29 · 21:56
    搜狗浏览器 2.X Windows 10

    tql

    555 2019-10-29 · 20:55
    Edge 17.17134 Windows 10

    %

    rr 2019-10-29 · 19:55
    Edge 18.18362 Windows 10

    tql!

    tql 2019-10-23 · 23:48
    Chrome 77.0.3865.120 Windows 10

    tql

    beautifulsoup 2019-10-23 · 19:20
    Chrome 77.0.3865.120 Windows 10

    tql

    1 2019-10-23 · 15:21
    Edge 17.17134 Windows 10

    w

    koko 2019-10-23 · 10:02
    Chrome 77.0.3865.120 Windows 10

    1

    bloodmaster 2019-10-19 · 19:05
    Firefox 69.0 Windows 10

    666

    www 2019-10-17 · 16:09
    Chrome 73.0.3683.86 Windows 10

    tttttttttql,学习一波

    zmm 2019-10-12 · 11:07
    Chrome 77.0.3865.90 Windows 10

    nb

    dfdcs 2019-10-12 · 10:56
    Chrome 77.0.3865.90 Windows 10

    tql

    griv 2019-10-12 · 10:34
    Chrome 77.0.3865.90 Windows 10

    学习了

    yhq 2019-10-12 · 10:25
    Chrome 77.0.3865.120 Windows 10

    666666666

    habuha 2019-10-12 · 10:10
    Chrome 66.0.3359.181 Windows 10

    666

    TScrooge 2019-10-12 · 10:04
    Chrome 77.0.3865.90 Windows 10

    666

    hahaha 2019-10-12 · 9:49
    Chrome 77.0.3865.90 Windows 10

    tql

    1 2019-10-11 · 21:33
    Edge 18.18362 Windows 10

    10

    ILoveChina 2019-10-11 · 21:29
    Chrome 77.0.3865.120 Windows 10

    nb

    _ 2019-10-10 · 15:13
    Chrome 77.0.3865.90 Windows 10

    tql

    222 2019-10-9 · 18:27
    Chrome 55.0.2883.87 Windows 10

    厉害

    1 2019-10-9 · 17:21
    Chrome 65.0.3325.181 Windows 10

    6

    忘了 2019-9-14 · 10:24
    Chrome 76.0.3809.132 Windows 10

    妙啊

    黑暗风暴 2018-11-19 · 12:22
    Firefox 63.0 Windows 7

    膜拜大佬

    233 2018-11-16 · 11:15
    Firefox 63.0 Ubuntu Linux

    233

      jxtxzzw 2018-11-17 · 17:58
      Chrome 70.0.3538.67 Windows 10

      感谢你的支持

    IllusionBot 2018-11-13 · 12:09
    Chrome 70.0.3538.77 Mac OS X 10_14_0

    刚刚灌水还灌错了地方。。

      jxtxzzw 2018-11-13 · 14:30
      Chrome 70.0.3538.80 Android 8.0.0 | HTC 2Q4D200

      感谢你的支持