跟我一起写操作系统
本文作者：李德强
第一节 内存申请与释放
我们在内核程序的alloc.c中实现了alloc_page()和alloc_mm()函数这些内存申请与释放函数都是为内核程序所使用的，现在我们要来实现普通程序可以使用的malloc()、free()和realloc()函数。首先来回顾一下内存分页机制中的页表结构：
页表中的第9、第10和第11位为Not Used，其中第9位我们在交换分区章节已经为其指派了是否已交换的标记。下面我们就要利用第10位和第11位来做内存页的使用状态标记：
- 10bit：0为未使用，1为已使用。
- 11bit：0为不可分块的整体内存页，1为可分块为程序分配的动态内存页。
内存申请的过程是：首先判断程序申请内存大小，如果超过4K则按整页分配；否则按动态块分配。按整页分配时，如果找到连续的与申请空间大小相等的内存页面则返回其首地址，否则失败。按动态块分配时，如果找到页内连续与申请空间大小相等的内存区域则返回其首地址，否则向下一个内存页中查找，当所有可申请内存页面均查找过之后若无与申请内存区域大小相等的地址则失败。具体流程如下：
首先实现按整页申请内存的函数：
void* palloc(s_pcb *pcb, int page)
{
u32 *p_tbl = pcb->page_tbl;
//查找内存申请地址
void *ret = NULL;
//找到空闲内存页计数
int num = 0;
//开始编号
u32 start_with = 0;
/*
* 从是从物理内存的最大值未被分配内存页的地方开始查找
*/
for (u32 i = MALLOC_START; i < MALLOC_END; i++)
{
//如果找到空闲页
if (((p_tbl[i] >> 10) & 0x1) == 0)
{
//设置可分配内存起始编号
if (start_with == 0)
{
ret = (void*) (i * MM_PAGE_SIZE);
start_with = i;
}
num++;
}
//如果没有找到空闲页
else
{
//清空变量
ret = NULL;
num = 0;
start_with = 0;
}
//找到了可分配内存页，并且找到了预期想要分配的数量
if (start_with != 0 && num >= page)
{
break;
}
}
//设置map的各个内存页的状态为已使用
for (u32 i = 0; i < page; i++)
{
//将10bit置为1,表示已使用
p_tbl[start_with + i] |= (1 << 10);
//将11bit置为0,表示非动态页
p_tbl[start_with + i] &= 0xfffff7ff;
}
return ret;
}
按动态块分配内存时有一个需要注意的地方，就是在页表中查找一个未使用或是动态分配的页面时，这个页面可能不在内存中（未分配页面或已被交换到外存）这里要直接访问它的页内位图是不对的，需要先为其执缺页申请：
void* malloc(s_pcb *pcb, int size)
{
//如果申请内存大小大于一个页大小，则按整页分配内存
if (size > (MM_PAGE_SIZE - 128))
{
//计算有多少个内存页
u32 count = (size / MM_PAGE_SIZE);
//如果有余数，说明要多分配一个页面
if (size % MM_PAGE_SIZE != 0)
{
count++;
}
//按整页分配内存
return palloc(pcb, count);
}
//得到页表
u32 *p_tbl = pcb->page_tbl;
//4字节对齐分配内存
u32 alloc_size = size / 4;
//如果有余数，说明要多分配一个4字节
if (size % 4 != 0)
{
alloc_size++;
}
//i为map下标，j为页内map下标，k为页内字节位偏移，c为查找count
int i, j, k, c = 0, break_status = 0, run_time = 0;
//is为起始map下标，js为页内起始map下标，ks为面内起始字节偏移
int is = -1, js = -1, ks = -1;
//从未被分配内存页的地方开始查找
for (u32 i = MALLOC_START; i < MALLOC_END && !break_status; i++)
{
//如果页面不在内存中，执行缺页申请
if ((p_tbl[i] & 1) == 0)
{
u32 address = i * MM_PAGE_SIZE;
page_error(6, address);
}
//如果是未使用或已使用但是动态内存
if (((p_tbl[i] >> 10) & 0x1) == 0 || (((p_tbl[i] >> 10) & 0x1) == 1 && ((p_tbl[i] >> 11) & 0x1) == 1))
{
is = -1;
js = -1;
ks = -1;
c = 0;
//取得页内位图，如果此页面不存在会触发缺页异常
u8 *mpmap = (u8 *) (p_tbl[i] & 0xfffff000);
//跳过前4个字节，并小于128个字节中查找页内位图map
//一个页面为4096字节，前128字节为页内位图，0x80 * 0x8 * 0x4 = 0x1000 = 4096
//这128个字节占用页内位图为 0x80 / 0x8 / 0x4 = 0x4字节，所以要跳过前4个字节
for (j = 4; j < 128 && !break_status; j++)
{
//字节偏移从0到7字节来查找可用内存
for (k = 0; k < 8 && !break_status; k++)
{
//如果可以使用
if (((mpmap[j] >> k) & 0x1) == 0)
{
//设置各项起始号
if (is == -1 && js == -1 && ks == -1)
{
is = i;
js = j;
ks = k;
}
//已找到数量自增
c++;
}
//如果不可用
else
{
//各项起始号清除
is = -1;
js = -1;
ks = -1;
c = 0;
}
//如果找到可分配内存数量达到预先要申请的数量
if (c >= alloc_size)
{
//跳出
break_status = 1;
}
}
}
}
//如果内存页为已使用
else
{
//各项起始号清除
is = -1;
js = -1;
ks = -1;
c = 0;
}
}
//清空分配数
c = 0;
//正式分配内存
if (break_status == 1 && is != -1 && js != -1 && ks != -1)
{
//从内存位图开始
for (i = is; i < MALLOC_END; i++)
{
//如果是可分配内存
if (((p_tbl[i] >> 10) & 0x1) == 0 || (((p_tbl[i] >> 10) & 0x1) == 1 && ((p_tbl[i] >> 11) & 0x1) == 1))
{
u8 *mpmap = (u8 *) (p_tbl[i] & 0xfffff000);
//从页内位图的第4个字节开始
for (j = 4; j < 128; j++)
{
//如果是第1次，找到起始地址
if (run_time == 0)
{
j = js;
}
//页内偏移
for (k = 0; k < 8; k++)
{
//如果是第1次，找到起始偏移
if (run_time == 0)
{
k = ks;
}
//更新页内位图
mpmap[j] |= (1 << k);
//找到数量自增
c++;
//次数加1
run_time++;
//找到预期的申请数量
if (c >= alloc_size)
{
//将此内存页设定为动态分配
p_tbl[i] |= 0xc00;
u32 ret = (is * MM_PAGE_SIZE + (js * 8 * 4) + (ks * 4));
//printf("malloc %x\n", ret);
//返回申请内存地址
return (void*) ret;
}
}
}
}
}
}
//返回空指针
return NULL;
}
实现free函数：
void free(s_pcb *pcb, void *addr, int size)
{
//如果大小大于一个内存页大小，则按整内存页释放
if (size > (MM_PAGE_SIZE - 128))
{
//计算有多少个内存页
int count = (size / MM_PAGE_SIZE);
//如果有余数说明要多释放一个页
if (size % MM_PAGE_SIZE != 0)
{
count++;
}
//释放内存页
pfree(pcb, addr, count);
return;
}
u32 *p_tbl = pcb->page_tbl;
//按4字节对齐释放
int alloc_size = size / 4;
//如果有余数则说明要多释放一个4字节空间
if (size % 4 > 0)
{
alloc_size++;
}
//释放内存起始号
int is, js, ks, run_time = 0, count = 0;
//计算位图起始号
is = (u32) addr / MM_PAGE_SIZE;
//计算页内位图起始号
js = ((u32) addr % MM_PAGE_SIZE) / (8 * 4);
//计算页内位图位偏移起始号
ks = ((u32) addr % MM_PAGE_SIZE) % (8 * 4) / 4;
//从内存页开始
for (int i = is; i < MALLOC_END; i++)
{
//取得页内偏移
u8 *mpmap = (u8 *) (p_tbl[i] & 0xfffff000);
//从页内位图中第4个开始
for (int j = 4; j < 128; j++)
{
//如果是第1次释放
if (run_time == 0)
{
j = js;
}
//从页内偏移位开始
for (int k = 0; k < 8; k++)
{
//如果是第1次释放
if (run_time == 0)
{
k = ks;
}
//设定页内位图为动态可用内存
mpmap[j] &= (~(1 << k));
//数量自增
count++;
//次数自增
run_time++;
//如果已释放了预期大小的内存
if (count >= alloc_size)
{
//完成，返回
return;
}
}
}
}
}
另外每当程序申请内存时都需要记录下pbc申请内存的地址和大小，这样在进程执行free函数时无需再指定free内存的大小，而是通过pcb中已记录的内存大小进程内存释放：
/*
* 为pcb申请内存，并记录下其申请的地址和大小
*/
void* pcb_malloc(s_pcb *pcb, int size)
{
//申请一个存放记录的节点
s_alloc_list *alloc_node = alloc_mm(sizeof(s_alloc_list));
if (alloc_node == NULL)
{
return NULL;
}
//内存申请
void *addr = malloc(pcb, size);
if (addr == NULL)
{
free_mm(alloc_node, sizeof(s_alloc_list));
return NULL;
}
//设置节点
alloc_node->next = NULL;
alloc_node->addr = addr;
alloc_node->size = size;
//保存申请记录
if (pcb->alloc_list == NULL)
{
pcb->alloc_list = alloc_node;
}
else
{
s_alloc_list *p = pcb->alloc_list;
while (p->next != NULL)
{
p = p->next;
}
p->next = alloc_node;
}
return addr;
}
/*
* 为pcb释放内存，在这里按其申请的地址到记录中查找其大小并释放内存
*/
void pcb_free(s_pcb *pcb, void *addr)
{
//得到内存释放节点
s_alloc_list *p = pcb->alloc_list;
s_alloc_list *fp = p;
while (p != NULL)
{
if (p->addr == addr)
{
if (fp == p)
{
pcb->alloc_list = p->next;
}
else
{
fp->next = p->next;
}
//释放内存
free(pcb, addr, p->size);
free_mm(p, sizeof(s_alloc_list));
break;
}
if (fp == p)
{
p = p->next;
}
else
{
p = p->next;
fp = fp->next;
}
}
}
在shell程序的stdlib.c中实现调用内存申请和释放的函数：
int random(int min, int max)
{
int ret = 0;
int params[4];
params[0] = 2;
params[1] = min;
params[2] = max;
params[3] = (int) &ret;
__asm__ volatile("int $0x83" :: "a"(params));
return ret;
}
void* malloc(int size)
{
void *ret = NULL;
int params[3];
params[0] = 0x10;
params[1] = size;
params[2] = (int) &ret;
__asm__ volatile("int $0x83" :: "a"(params));
return ret;
}
void* realloc(void *addr, int size)
{
void *new_addr = malloc(size);
if (new_addr == NULL)
{
return addr;
}
memcpy(addr, new_addr, size);
free(addr);
return new_addr;
}
void free(void *addr)
{
int params[2];
params[0] = 0x11;
params[1] = (int) addr;
__asm__ volatile("int $0x83" :: "a"(params));
}
在realloc()函数中使用一个memcpy()函数，其功能是将内存中一个区域的内容复制到另一个地方，其实现如下：
void memcpy(void *from, void *to, int n)
{
u8 *t = (u8 *) to;
u8 *f = (u8 *) from;
for (int i = 0; i < n; i++)
{
*(t + i) = *(f + i);
}
}
在system.c中申请和释放内存测试：
void *p = malloc(0x1000);
printf("%x\n", p);
void *p2 = malloc(0x1000);
printf("%x\n", p2);
free(p);
free(p2);
int num = 4;
void *ps[num];
for (int i = 0; i < num; i++)
{
ps[i] = malloc(0xe00);
printf("%x\n", ps[i]);
}
for (int i = 0; i < num; i++)
{
free(ps[i]);
}
u8 *addr = malloc(8);
printf("%x\n", addr);
for (int i = 0; i < 8; i++)
{
addr[i] = (8 - i);
}
u8 *new_addr = realloc(addr, 16);
printf("%x\n", new_addr);
for (int i = 0; i < 8; i++)
{
printf("%x ", new_addr[i]);
}
printf("\n");
free(new_addr);
编译运行并查看结果：
在很多操作系统中动态分配内存的方案并不尽相同，大多数操作系统采用的方案是为进程分配一个很大的内存连续区域，称之为“堆”。当进程想要申请内存时，内核程序为在堆中查找一处满足大小的区域，在这个区域中的前8个字节中分别存放了上一个区块的起始地址和本区块的大小，然后将前8字节后的地址返回给申请程序。当程序释放一个内存块时，内核将此地址向前移动8个字节，取得前8个字节的区块头。根据这个区块头来释放这块区域。如果此区域的前后有也是空闲区域则为将其合并为一个大的空闲区域，否则只是将此区域标记为空闲区块。
这种内存分配方案与位图标记分配方案相比查找速度更快、使用更加方便。但它实现起来相对复杂一些，有兴趣的读者可以按此方案实现内存分配。
源代码的下载地址为：
https https://github.com/magicworldos/lidqos.git git git@github.com:magicworldos/lidqos.git subverion https://github.com/magicworldos/lidqos branch v0.27
Copyright © 2015-2023 问渠网 辽ICP备15013245号