看了一眼James的堆教程，吓得我直接Ctrl+W，代码太多，等我看完估计得到天荒地老。所以我找了一篇更简单的教程。它的堆管理讲的很清晰，只有少数几个函数，但是却实现了基本的功能。不过代码的某些功能和我的分页机制不兼容，所以我改了它的代码，实现起来更加简单。

堆设计

这个堆的设计和Linux的不同，它采用双向链表的形式。

1
2
3
4
5
6
7
8
9
/*
include/kheap.h
*/
typedef struct header{
	struct header *prev;
	struct header *next;
	u32 allocated : 1;
	u32 length : 31;
}header_t;

这是堆的头部，prev指向前面的堆，next指向后面的堆，allocated表示当前堆是否在使用，length表示当前堆的长度，就跟Linux堆中的size差不多。

堆分配

简单说一下kmalloc的流程，cur_header永远指向第一个分配的堆，之后分配的时候会通过第一个堆的next指针依次往下找，直到找到allocated为0的堆块，然后在此处创建新堆的头部，并将堆的管理区域(mem)地址返回。
这样的分配机制有性能缺陷，如果堆特别多的话找起来会非常慢，除非前面的堆被free过，不过为了简单就先凑合用。

为了方便，我保留了原作者的注释，并添加了一些新注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
heap/kheap.c
*/
void init_heap(){
	heap_first = 0;
}


void *kmalloc(u32 len){
    // 所有申请的内存长度加上管理头的长度
    // 因为在内存申请和释放的时候要通过该结构去管理
	len += sizeof(header_t);

	header_t *cur_header = heap_first;
	header_t *prev_header = 0;
	
	while (cur_header) {
     // 如果当前内存块没有被申请过而且长度大于待申请的块
		if (cur_header->allocated == 0 && cur_header->length >= len) {
        // 按照当前长度切割内存
			split_chunk(cur_header, len);
			cur_header->allocated = 1;
        // 返回的时候必须将指针挪到管理结构之后
			return (void *)((u32)cur_header + sizeof(header_t));
		}
		// 逐次推移指针
		prev_header = cur_header;
		cur_header = cur_header->next;
	}

	u32 chunk_start;
    
    
    // 第一次执行该函数则初始化内存块起始位置
    // 之后根据当前指针加上申请的长度即可
	if (prev_header) {
		chunk_start = (u32)prev_header + prev_header->length;
	} else {
		chunk_start = HEAP_START;
		heap_first = (header_t *)chunk_start;
	}


  // 创建堆的头部
	cur_header = (header_t *)chunk_start;
	cur_header->prev = prev_header;
	cur_header->next = 0;
	cur_header->allocated = 1;
	cur_header->length = len;
	
	if (prev_header) {
		prev_header->next = cur_header;
	}

    
	return (void*)(chunk_start + sizeof(header_t));	

}

堆释放

堆释放比较简单，就是将其allocated置为0，这样等到kmalloc遍历的时候会就找到这个块。glue_chunk用来合并前后已经被释放的块，相当于ptmalloc中的unlink功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
heap/kheap.c
*/
void kfree(void *p)
{
    // 指针回退到管理结构，并将已使用标记置 0
	header_t *header = (header_t*)((u32)p - sizeof(header_t));
	header->allocated = 0;

  // 合并前后被释放的堆块
	glue_chunk(header);
}


void glue_chunk(header_t *chunk)
{
// 如果该内存块的下一个内存块且未被使用则拼合
	if (chunk->next && chunk->next->allocated == 0) {
		chunk->length = chunk->length + chunk->next->length;
		if (chunk->next->next) {
			chunk->next->next->prev = chunk;
		}
		chunk->next = chunk->next->next;
	}

// 如果该内存块前一个内存块且未被使用则拼合
	if (chunk->prev && chunk->prev->allocated == 0) {
		chunk->prev->length = chunk->prev->length + chunk->length;
		chunk->prev->next = chunk->next;
		if (chunk->next) {
			chunk->next->prev = chunk->prev;
		}
		chunk = chunk->prev;
	}

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
init/kernel.c
*/
  int kmain(void){
	
	console_clear();

	init_gdt();
	init_idt();

	printk("Hello,kernel;\n");
	init_timer(200);
	//asm volatile ("sti");
	initialise_paging();

    //分配
	void *addr1 = kmalloc(50);
	printk("kmalloc 50 byte in 0x%X\n", addr1);
	void *addr2 = kmalloc(500);
	printk("kmalloc 500 byte in 0x%X\n", addr2);

    //释放
	printk("free mem in 0x%X\n", addr1);
	kfree(addr1);
	printk("free mem in 0x%X\n", addr2);
	kfree(addr2);
	return 0;

	
}

参考资料
hurlex <十一> 内核堆管理的实现