OrangeOS-alloc_free
流程
以alloc为例，在测试文件中调用alloc函数分配指定大小的内存，该函数会调用alloc(u32 size)函数：
1
2
3
4
5
6
7
8
9
10
11
12
| PUBLIC void* alloc(unsigned int size)
{
MESSAGE msg;
msg.type = ALLOC;
msg.MM_SIZE = size;
send_recv(BOTH, TASK_MM, &msg);
assert(msg.type == SYSCALL_RET);
assert(msg.RETVAL == 0);
return msg.MM_ADDR;
}
|
该函数通过消息传递的方式和内核中的任务进行通信，消息类型为ALLOC，消息内容为分配内存的大小，之后将消息发送给TASK_MM，由task_mm()将消息转交给do_alloc()函数：
1
2
3
4
5
6
7
8
| task_mm(){
...
case ALLOC:
mm_msg.RETVAL = do_alloc();
break;
...
}
|
接下来，do_alloc()函数调用tree_alloc函数计算分配给该内存的地址：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
PUBLIC int do_alloc()
{
printl("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printl("Alloc 0x%x byte(s):\n", mm_msg.MM_SIZE);
mm_msg.MM_ADDR = tree_alloc(0, 0, mm_msg.MM_SIZE);
printl("Alloc at: 0x%x\n", mm_msg.MM_ADDR);
printl("Alloc Status:\n");
output(0, 0);
printl("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n");
return 0;
}
|
tree_alloc(root, depth, addr)函数使用伙伴算法对内存进行分配：
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
59
| """
递归分配内存
root: 当前根结点编号
depth: 当前结点深度
size: 所需分配大小
return: 分配地址，如果不够分配返回None
"""
def tree_alloc(root, depth, size):
cur_pg_cnt = pg_cnt(depth)
child_pg_cnt = floor(cur_pg_cnt / 2)
cur_size = cur_pg_cnt * PAGE_SIZE
child_size = child_pg_cnt * PAGE_SIZE
if root == 0 and size > cur_size:
return None
if nodes[root] == BD_OCCUPIED:
return None
elif nodes[root] == BD_FREE:
if size > child_size:
nodes[root] = BD_OCCUPIED
return base_addr(root, depth)
elif size <= child_size:
nodes[root] = BD_SPLIT
nodes[child_left(root)] = BD_FREE
nodes[child_right(root)] = BD_FREE
return tree_alloc(child_left(root), depth + 1, size)
elif nodes[root] == BD_SPLIT:
if size > child_size:
return None
elif size <= child_size:
laddr = tree_alloc(child_left(root), depth + 1, size)
if laddr != None:
return laddr
else:
raddr = tree_alloc(child_right(root), depth + 1, size)
if raddr != None:
return raddr
else:
return None
else:
assert False
|
算法说明：
定义区域0x1C00000~``0x2000000``为可分配空间，最小分配内存为4096KB，即一个页的大小，该大小是可调节的。之后定义一棵二叉树，该树的大小为$$2^{11} - 1$$，该大小取决于最大可分配空间和最小可分配空间。树的结点有以下定义方式：
SPLIT: 该结点是分支结点，有2个孩子结点，且该区域已经被划分
FREE: 该结点是孩子结点，且该区域没有被占用
OCCUPIED: 该结点是孩子结点，且该区域已经被占用
NONE: 空结点
算法执行流程见代码注释，其中，结点的基地址计算方法如下：
1
2
3
4
5
6
7
8
9
10
|
def base_addr(i, depth):
if i == 0:
return ALLOC_BASE
cur_pg_cnt = pg_cnt(depth)
if i % 2 == 1:
return base_addr(parent(i), depth - 1)
else:
return base_addr(parent(i), depth - 1) + cur_pg_cnt * PAGE_SIZE
|
内存释放使用类似的算法，代码及注释如下：
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| """
递归释放内存
root: 当前根结点编号
depth: 当前结点深度
addr: 内存的基地址
"""
def tree_free(root, depth, addr):
if addr == None:
assert False
rt_addr_low = base_addr(root, depth)
rt_addr_high = rt_addr_low + pg_cnt(depth) * PAGE_SIZE
if addr < rt_addr_low or addr >= rt_addr_high:
assert False
if nodes[root] == BD_OCCUPIED:
if rt_addr_low == addr:
nodes[root] = BD_FREE
return
else:
assert False
elif nodes[root] == BD_SPLIT:
l_addr = base_addr(child_left(root), depth + 1)
r_addr = base_addr(child_right(root), depth + 1)
if addr >= l_addr and addr < r_addr:
tree_free(child_left(root), depth + 1, addr)
if nodes[child_left(root)] == BD_FREE:
if nodes[child_right(root)] == BD_FREE:
nodes[root] = BD_FREE
nodes[child_left(root)] = BD_NONE
nodes[child_right(root)] = BD_NONE
return
else:
return
elif nodes[child_left(root)] == BD_SPLIT:
return
elif nodes[child_left(root)] == BD_OCCUPIED:
assert False
elif nodes[child_left(root)] == BD_NONE:
assert False
else:
assert False
elif addr >= r_addr:
tree_free(child_right(root), depth + 1, addr)
if nodes[child_right(root)] == BD_FREE:
if nodes[child_left(root)] == BD_FREE:
nodes[root] = BD_FREE
nodes[child_left(root)] = BD_NONE
nodes[child_right(root)] = BD_NONE
return
else:
return
elif nodes[child_right(root)] == BD_SPLIT:
return
elif nodes[child_right(root)] == BD_OCCUPIED:
assert False
elif nodes[child_right(root)] == BD_NONE:
assert False
else:
assert False
else:
assert False
elif nodes[root] == BD_FREE:
assert False
elif nodes[root] == BD_NONE:
assert False
else:
assert False
|