开发单片类Unix操作系统-堆（4）

在上一篇文章中，我们实现了内核系统日志。 现在是时候实现动态内存管理器了。

目录

1. 构建系统（make，gcc，gas）。 初始引导（多次引导）。 启动（qemu）。 C库（strcpy，memcpy，strext）。
2. C库（sprintf，strcpy，strcmp，strtok，va_list ...）。 以内核模式和用户应用程序模式构建库。
3. 内核系统日志。 显存 输出到终端（kprintf，kpanic，kassert）。
4. 动态内存，堆（kmalloc，kfree）。
5. 内存和中断处理的组织（GDT，IDT，PIC，syscall）。 例外情况
6. 虚拟内存（页面目录和页面表）。
7. 过程。 策划人 多任务处理。 系统调用（kill，exit，ps）。
8. 内核（initrd），elf及其内部文件系统。 系统调用（执行）。
9. 字符设备驱动程序。 系统调用（ioctl，fopen，fread，fwrite）。 C库（fopen，fclose，fprintf，fscanf）。
10. Shell作为内核的完整程序。
11. 用户保护模式（ring3）。 任务状态段（tss）。

动态内核内存。 一堆

内核堆接口将如下所示：

void *kmalloc(size_t size); void kfree(void *addr); 

由于还没有堆，因此必须存储已占用和可用内存区域的记录。
以有限的大小排列。 尺寸越小，堆容量越低
小碎片。 例如，在Linux上，许多内核结构存储在可重用的环境中
释放时不会改变大小的内存（平板）。 但是我们还差得远
因为发展是一个反复的过程。

任何打算成为通过数组组织的列表的元素的元素
需要实现一个接口。

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); 

C中没有接口，但是不需要它们。 如果此对象实际上看起来像这样，我们只需将任何对象的指针转换为struct slist_head_t *类型：

 struct my_list_entry_t { struct slist_head_t list_head; ... } 

但是，这样广义算法知道列表将存储在其中的数组的维数
以及其元素的大小，列表的第一个和最后一个元素以及其中的数组的地址
存储一个列表，操作列表的每个功能将需要另一个指针
到列表定义结构：

 struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; }; 

用于操作列表的功能如下所示：

 struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos); struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos); void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry); 

插入函数算法：
在阵列中找到一个空闲插槽。
用新元素填充它。
更正逻辑上（而非物理上）相邻列表项的指针。
将插槽标记为忙。
调整列表的开头和结尾。

从列表中删除的函数的算法：
更正逻辑上（而非物理上）相邻列表项的指针。
调整列表的开头和结尾。
将插槽标记为空闲。

动态内存由具有以下各项的列表描述：

 struct kheap_entry_t { struct slist_head_t list_head; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } attribute(packed); 

从这些记录描述动态内存的数组如下所示：

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 

定义内存区域列表如下所示：

 struct slist_definition_t kheap_list = { .head = null, .tail = null, .slot_size = sizeof(struct kheap_entry_t), .slots = KHEAP_MAX_ENTRIES, .base = (size_t)kheap_blocks}; 

因此，我们已经描述了动态内存。 所有内存在一定范围内
分为任意大小的块，每个块可以为空，
要么忙。 此外，每个块都由一个带有is_valid = true标志的数组元素描述，
这是一个列表项。

现在考虑最简单的堆分配器算法（kmalloc）：
如果没有可用块，请选择所需大小（但不超过最大堆大小）的新块。

否则，我们将浏览所有空闲块。 如果找到空闲块，请查看其大小。 如果足够，请接受。 如果有剩余，则创建一个新的剩余大小的空白块。 否则，如果不足，则扩大堆边界（但不超过最大值）。

 /* * Api - Kernel memory alloc */ extern void* kmalloc(size_t size) { struct kheap_entry_t* current_data = null; struct slist_head_t* current = null; struct slist_head_t* head = kheap_list.head; assert(size > 0); /* try to use free block */ for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } /* check size is not enough */ if (current_data->size < size) { /* try to ask contribution from free left sibling */ if (current->prev != null) { /* left sibling has found */ struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether left sibling is free */ if (!sibling_data->is_buzy) { /* ask lack from left sibling */ size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); /* whether left sibling is collapsed */ if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } /* occupy block */ current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to extend borders */ if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; /* check free memory size is enought */ if (heap_end_addr + lack < KHEAP_END_ADDR) { /* occupy block */ current_data->size += lack; current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } } else { /* occupy block */ current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; /* try to contribute free right sibling */ if (current->next != null) { /* sibling has found */ struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether sibling is free */ is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { /* give surplus to right sibling */ current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } /* try to give surplus to new right sibling */ if (current->next == null || is_sibling_bizy) { { struct slist_head_t* new_sibling; new_sibling = slist_insert_entry_after(&kheap_list, current); struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data; if (new_sibling != null) { /* give surplus to new right sibling */ assert((size_t)new_sibling == (size_t)sibling_data); current_data->size -= surplus; assert(current_data->size > 0); sibling_data->is_buzy = false; sibling_data->addr = current_data->addr + current_data->size; sibling_data->size = surplus; } } } assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to alloc new block */ size_t heap_end_addr = KHEAP_START_ADDR; /* calculate heap end address */ if (kheap_list.tail) { current = kheap_list.tail; current_data = (struct kheap_entry_t*)current->data; heap_end_addr = current_data->addr + current_data->size; } /* check free memory size is enought */ if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } /* allocate new heap memory block */ struct slist_head_t* tail = kheap_list.tail; current = slist_insert_entry_after(&kheap_list, kheap_list.tail); current_data = (struct kheap_entry_t*)current->data; assert((size_t)current == (size_t)current_data); current_data->addr = heap_end_addr; current_data->size = size; current_data->is_buzy = true; assert(current->next == null); assert(current->prev == tail); assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; } 

无内存算法将类似（kfree）：
查找一个地址以要释放的地址开头的块。 检查他是否忙。 标记为免费。

如果右边或左边有一个自由的邻居，与他团结在一起。

 /* * Api - Kernel memory free */ extern void kfree(void* addr) { struct slist_head_t* current = null; struct kheap_entry_t* current_data = null; struct slist_head_t* head = kheap_list.head; for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->addr == (size_t)addr && current_data->is_buzy) { struct slist_head_t* prev = current->prev; struct slist_head_t* next = current->next; struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null; struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null; /* free block */ current_data->is_buzy = false; /* try to merge with free left sibling */ if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } /* try to merge with free right sibling */ if (next != null && !next_data->is_buzy) { current_data->size += next_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)next); } return; } } abort("invalid address to free\n", addr); } 

仅此而已。 直到下一次！

参考文献

现在，打开视频教程
并并行观看git存储库（您需要一个lesson4分支）

参考文献

1.詹姆斯·莫洛伊（James Molloy）。 滚动自己的玩具UNIX克隆操作系统。
2.牙齿。 DOS，Windows，Unix的汇编器
3.卡拉什尼科夫。 汇编程序很简单！
4. Tanenbaum。 操作系统。 实施与开发。
5.罗伯特·洛夫（Robert Love）。 Linux内核 开发过程的描述。