skaiuijing

上一篇笔者讲了内存分配的算法，是适合让我们一步步实现这些算法了，一共有四个函数，分别是初始化、分配、释放、插入。

初始化

初始化后的内存分布如图所示：

1
2
3
4
5
graph LR
A(theheap)--->D
A-->C
D(头部)--相邻-->B(内存块)--相邻-->C(尾部)

简单来说，就是我们要在大内存数组起始地址和终结地址分别创建两个heap_node节点，用于管理这个内存块,然后将它们使用指针连起来，还记得上一篇博客中我们定义的theheap吗？它负责记录头部和尾部。

像&= ~这些操作是字节对齐，字节对齐可以提高CPU运行速度，也可以防止error的发生

另外还要给读者介绍一点小知识：对于正整数X，Y = 2^n,X%Y 可以被X&(Y-1)代替。

举个例子，X % 16 = X &15。

证明过程看笔者博客：c程序杂谈系列（加减乘除模篇）-CSDN博客

程序如下：此时，firstnode就是头部。

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

void heap_init()
{
    heap_node *firstnode;
    uint32_t start_heap ,end_heap;
    //get start address
    start_heap =(uint32_t) allheap;
    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);
    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;
}

分配

分配的算法如下，程序使用的是first-fit算法：

1
2
3
4
5
graph LR
Aa(头部)--从头开始找_直到找到符合大小的内存块-->Ba(内存块)-->Ca(内存块)-->Da(内存块)-->Ea(内存块)-->Ta(尾部)
G(链表起始)--空闲内存块链表-->F(结束)
A(prev)--在这条链表上找到符合条件的内存块-->B(use)-->C(new)
Ap(prev)--如果分配后有剩余_就分割-->ap(分割下来的内存块)-->Cp(new)

在初始化后，空闲内存块已经形成了一条链表，这条链表被称为空闲内存块链表，内存块被使用就被踢出这条链表，被释放就加入这条链表，如果内存块大于要申请的大小，就把多余的部分切割，然后加入这条内存链表。

源码,malloc会找到合适的内存块，并且返回它的地址：

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

void *heap_malloc(size_t wantsize)
{
    heap_node *prevnode;
    heap_node *usenode;
    heap_node *newnode;
    size_t aligmentrequisize;
    void *xReturn = NULL;
    wantsize += heapstructSize;
    if((wantsize & aligment_byte) != 0x00)
    {
        aligmentrequisize = aligment_byte - (wantsize & aligment_byte);
        wantsize += aligmentrequisize;
    }
    if(theheap.tail== NULL )
    {
        heap_init();
    }
    prevnode = &theheap.head;
    usenode = theheap.head.next;
    while((usenode->blocksize) < wantsize )
    {
        prevnode = usenode;
        usenode = usenode ->next;
    }
    xReturn = (void*)( ( (uint8_t*)usenode ) + heapstructSize );
    prevnode->next = usenode->next ;
    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;
    usenode->next = NULL;
    return xReturn;
}

释放

当有内存块需要释放时，直接插入空闲内存块链表即可即可。

插入前：

1
2
3
4
graph LR
A(空闲内存块链表节点)-->D(空闲内存块链表节点)-->B(空闲内存块链表节点);

C(Insert)-->D(空闲内存块);

插入后：

1
2
3
4
graph LR
A(空闲内存块链表节点)-->C(Insert节点)-->D(空闲内存块链表节点)-->B(空闲内存块链表节点);


程序如下：

1
2
3
4
5
6
7
8
9
10
11
void heap_free(void *xret)
{
    heap_node *xlink;
    uint8_t *xFree = (uint8_t*)xret;

    xFree -= heapstructSize;
    xlink = (void*)xFree;
    theheap.allsize += xlink->blocksize;
    InsertFreeBlock((heap_node*)xlink);
}

InsertFreeBlock不仅实现插入，同时实现合并内存块

插入与合并

如果我们检测到free释放的内存块的地址与其他空闲内存块是连续的，我们会合并它们，这里是内存管理算法的精髓所在。

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
28
29
30
31
32

static void InsertFreeBlock(heap_node* xInsertBlock)
{
    heap_node *first_fitnode;
    uint8_t* getaddr;

    for(first_fitnode = &theheap.head;first_fitnode->next < xInsertBlock;first_fitnode = first_fitnode->next)
    { /*finding the fit node*/ }

    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;
    }
}

说实话，笔者在想直接上这一部分是不是有点不友好，要知道笔者当初写内存算法可是调试得死去活来，奇奇怪怪的问题不断出现。

所以为了提高大家的体验，笔者将在下一篇博客讲解如何使用gdb和keil进行调试，并且笔者将会修改内存管理算法，让它出现bug，然后用gdb去调试它，找出问题并且解决问题。

在那之后，笔者将会做一个小实验来验证我们的内存管理算法的正确性，笔者将直接替换FreeRTOS的heap4.c文件，用我们自己写的内存管理算法代替，看看FreeRTOS到底能不能跑起来！

Sparrow源码：skaiui2/SKRTOS_sparrow at source (github.com)

已经移植好的工程，包括hal库版本和标准库版本：skaiui2/SKRTOS_sparrow: Lightweight rtos inspired by SKRTOS (github.com)