该文章用作个人纪录。
简要介绍一下两种内存管理算法：
1.小内存管理算法
采用不断分割的方法对内存进行动态分配，分为初始化，分割，释放三个步骤，为了简洁起见，笔者直接放图：
1
2
3
4
5
6
|
graph LR
A(头部)-->B(初始大内存块)-->C(尾部)
|
1
2
| graph LR
A(头部)-->B(内存块)-->C(内存块)-->D(内存块)-->E(内存块)-->T(尾部)
|
这是整体思想，通过对初始内存块的不断切割，最终形成了各个不同的内存块。
四个函数，第一个init：
1
2
| graph LR
A(头部)-->B(内存块)-->C(尾部)
|
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
| /*sk
*ai
*ui
*ji
*ng
*/
void heap_init()
{
heap_node *firstnode;
//这行注释不要删除
//命名不要随便改，不然有概率导致数组最后八个字节出现segmentation fault问题
uint32_t start_heap ,end_heap;
//get start address
start_heap =(uint32_t) allheap;
/*byte aligment*/
if( (start_heap & aligment_byte) != 0){
start_heap += aligment_byte ;
start_heap &= ~aligment_byte;
theheap.allsize -= (size_t)(start_heap - (uint32_t)allheap);//byte aligment means move to high address,so sub it!
}
theheap.head.next = (heap_node *)start_heap;
theheap.head.blocksize = (size_t)0;
end_heap = ( start_heap + (uint32_t)config_heap);
/*byte aligment*/
if( (end_heap & aligment_byte) != 0){
end_heap += aligment_byte ;
end_heap &= ~aligment_byte;
theheap.allsize = (size_t)(end_heap - start_heap );
}
theheap.tail = (heap_node*)end_heap;
theheap.tail->blocksize = 0;
theheap.tail->next =NULL;
firstnode = (heap_node*)start_heap;
firstnode->next = theheap.tail;
firstnode->blocksize = theheap.allsize;
}
|
第二个malloc：
1
2
3
4
| graph LR
A(头部)--从头开始找_直到找到符合大小的内存块-->B(内存块)-->C(内存块)-->D(内存块)-->E(内存块)-->T(尾部)
|
1
2
3
| graph LR
G(链表起始)--把初始化的内存链表模型作为空闲内存块建立的链表-->F(结束)
A(prev)--在这条链表上找到符合条件的内存块-->B(use)-->C(new)
|
这条链表上就是空闲内存块链表，内存块被使用就被踢出这条链表，被释放就加入这条链表，如果内存块大于要申请的大小，就把多余的部分切割，然后加入这条内存链表。
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
103
104
105
106
107
108
109
110
111
112
|
void *heap_malloc(size_t wantsize)
{
heap_node *prevnode;
heap_node *usenode;
heap_node *newnode;
size_t aligmentrequisize;
void *xReturn = NULL;
if(wantsize <= 0 )
{
printf("Error in function: %s at line: %d\n", __func__, __LINE__); \
exit(-1);
}
wantsize += heapstructSize;
if((wantsize & aligment_byte) != 0x00)
{
aligmentrequisize = aligment_byte - (wantsize & aligment_byte);
wantsize += aligmentrequisize;
}
if((wantsize / arm_max_memory) != 0)
{
printf("Error in function: %s at line: %d\n", __func__, __LINE__); \
exit(-1);
}
//I will add the TaskSuspend function ,that make there be a atomic operation
if(theheap.tail== NULL )
{
heap_init();
}
//
prevnode = &theheap.head;
usenode = theheap.head.next;
//the next is valid ?
while((usenode->blocksize) < wantsize )
{
prevnode = usenode;
usenode = usenode ->next;
}
//
if(usenode == theheap.tail)
{
printf("Error in function: %s at line: %d\n", __func__, __LINE__); \
exit(-1);
}
xReturn = (void*)(((uint8_t*)usenode) + heapstructSize);
prevnode->next = usenode->next ;
/*apart it!*/
if( (usenode->blocksize - wantsize) > MIN_size )
{
newnode = (void*)(((uint8_t*)usenode) + wantsize);
newnode->blocksize = usenode->blocksize - wantsize;
usenode->blocksize = wantsize;
newnode->next = prevnode->next ;
prevnode->next = newnode;
}
theheap.allsize-= usenode->blocksize;
if(theheap.allsize < 0U)
{
printf("Error in function: %s at line: %d\n", __func__, __LINE__); \
exit(-1);
}
usenode->next = NULL;
// I will write the TaskResume
if(usenode > theheap.tail)
{
printf("alheap : %d ,use: %d, tail: %d\n",allheap,usenode,theheap.tail);
printf("fuck : %s at line: %d\n", __func__, __LINE__);
exit(-1);
}
return xReturn;
}
|
第三个free：
1
2
3
4
| graph LR
A(空闲内存块)-->D(空闲内存块)-->B(空闲内存块);
C(Insert)-->D(空闲内存块);
|
直接插入即可。
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
| void heap_free(void *xret)
{
uint8_t *xFree = (uint8_t*)xret;
heap_node *xlink;
if(xFree == NULL)
{
printf("Error in function: %s at line: %d\n", __func__, __LINE__); \
exit(-1);
}
xFree -= heapstructSize;
xlink = (void*)xFree;
if(xlink->next != NULL)
{
printf("Error in function: %s at line: %d\n", __func__, __LINE__); \
exit(-1);
}
// I will tasksuspend
theheap.allsize += xlink->blocksize;
InsertFreeBlock((heap_node*)xlink);
// I will TaskResume
}
|
精髓在于InsertFreeBLOCK:
1
2
3
4
5
| graph LR
A(开始)-->B(prev)-->C(next)-->D(结束);
E(Insert)-->G(?)
|
1
2
3
4
| graph LR
A(start)-->B-->C(Insert)-->D-->E-->G(end);
|
后：
1
2
3
| graph LR
A(start)--后相邻-->B-->C(Insert)-->E-->F(end);
D-->E;
|
等价于：
1
2
3
| graph LR
A(start)--后相邻-->B-->C(Insert + D)-->E-->F(end);
|
前：
1
2
3
4
| graph LR
A(start)--前相邻-->B-->D-->E-->F(end);
C(Insert)-->D;
|
等价于：
1
2
3
4
| graph LR
A(start)--前相邻-->B(B+Insert)-->D-->E-->F(end);
|
前+后：注：B直接指向E
1
2
| graph LR
A(start)--可以只考虑最终结果-->B--Insert + D-->E-->F(end);
|
等价于：
1
2
3
4
| graph LR
A(start)--可以只考虑最终结果-->B(B + Insert +D)-->E-->F(end);
|
如果前后相邻是相互独立的，那么互不影响，如果不独立，通过后，前的顺序可以得到前后都相邻的结果，因此该顺序正确。
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
| xInsertBlock->next = first_fitnode->next;
first_fitnode->next = xInsertBlock;
getaddr = (uint8_t*)xInsertBlock;
if((getaddr + xInsertBlock->blocksize) == (uint8_t*)(xInsertBlock->next))
{
if(xInsertBlock->next != theheap.tail )
{
xInsertBlock->blocksize += xInsertBlock->next->blocksize;
xInsertBlock->next = xInsertBlock->next->next;
}
else
{
xInsertBlock->next = theheap.tail;
}
}
getaddr = (uint8_t*)first_fitnode;
if((getaddr + first_fitnode->blocksize) == (uint8_t*) xInsertBlock)
{
first_fitnode->blocksize += xInsertBlock->blocksize;
first_fitnode->next = xInsertBlock->next;
}
|
