内存空间管理尝试一
尝试着写下内存分配函数,dimalloc和difree。
目标:如何使用 mmap()获取一大块匿名内存,然后使用指针,以构建一个简单的空闲列表来管理空间。采用最优匹配,也就是每次全部遍历找最合适的大小。
测试效果如下:
// main.c
#include <stdio.h>
#include "dimalloc.h"
int main()
{
char *str = (char *)dimalloc(sizeof(char)*64);
sprintf(str,"%s","hi");
printf("%s\n",str);
char *str2 = (char *)dimalloc(sizeof(char)*128);
sprintf(str2,"%s","hi2");
printf("%s\n",str2);
difree(str2);
char *str3 = (char *)dimalloc(sizeof(char)*256);
sprintf(str3,"%s","hi3");
printf("%s\n",str3);
difree(str);
difree(str3);
return 0;
}
我用freeNode来存放空闲区间。
typedef struct freeNode
{
int start;
int end;
struct freeNode *before;
struct freeNode *next;
}freeNode;
但是问题又出现了:鸡生蛋还是蛋生鸡的问题,freeNode的空间放哪,我这里就是在空闲区间里找个空闲地方放入了,但是这个策略貌似不太好,如下图最后,free node反而割裂了空闲区间,不过也是一次有趣的尝试了。
如上代码main.c里面的描述,图像化分配区间如下,灰色部分为分配区间长度,这样free(void *p)
就不用考虑长度了。
最后的空闲区间列表如下:
没仔细测试,可能仍有bug
#include "dimalloc.h"
void *baseaddr = NULL;
freeNode *head = NULL;
#define BLOCKSIZE 1024 * 1024 * 32
void *dimalloc(int sz)
{
void *ret;
// 分配32MB内存作为大内存块
if (!baseaddr)
{
baseaddr = mmap(NULL, BLOCKSIZE, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
// 内存分配之前int类型表明大小
head = baseaddr + 4;
head->start = sizeof(freeNode) + 4;
head->end = BLOCKSIZE; // 不包含
head->before = NULL;
head->next = NULL;
*(int *)(baseaddr) = sizeof(freeNode);
}
// 最优算法:便利找最合适的大小
freeNode *p = head;
freeNode *bestp = NULL;
while (p)
{
if (!bestp)
{
if ((p->end - p->start + 4) >= sz)
bestp = p;
}
else
{
if (((bestp->end - bestp->start) > (p->end - p->start)) && (p->end - p->start + 4 >= sz))
{
bestp = p;
}
}
p = p->next;
}
if (!bestp)
{
//抛出异常
}
ret = baseaddr + bestp->start + 4;
*(int *)(baseaddr + bestp->start) = sz;
if (sz == bestp->end - bestp->start + 4)
{
if (bestp->before)
{
bestp->before = bestp->next;
bestp->next->before = bestp->before->next;
}
else
{
head = bestp->next;
bestp->next->before = NULL;
}
difree(bestp);
}
else
{
bestp->start = bestp->start + 4 + sz;
}
return ret;
}
freeNode *newFreeNode(int start, int end)
{
freeNode *p = (freeNode *)dimalloc(sizeof(freeNode));
p->start = start;
p->end = end;
p->next = NULL;
p->before = NULL;
}
void difree(void *p)
{
int sz = *(int *)(p - 4);
int start = p - baseaddr - 4;
int end = start + sz + 4;
if (!head)
{
head = (freeNode *)dimalloc(sizeof(freeNode));
head->start = start;
head->end = end;
head->next = NULL;
head->before = NULL;
return;
}
freeNode *tmp = head;
freeNode *left = NULL;
freeNode *right = NULL;
while (tmp)
{
if (tmp->end <= start)
{
left = tmp;
tmp = tmp->next;
}
else
break;
}
if (left)
right = left->next;
else
right = head;
if (left && right && start == left->end && end == right->start)
{
left->end = right->end;
left->next = right->next;
difree(right);
}
else if (right && end == right->start)
right->start = start;
else if (left && start == left->end)
left->end = end;
else
{
tmp = newFreeNode(start, end);
if (!left)
{
head = tmp;
tmp->next = right;
right->before = tmp;
}
if (!right)
{
tmp->before = left;
left->next = tmp;
}
}
}