内存管理

https://www.rt-thread.org/document/site/#/rt-thread-version/rt-thread-standard/programming-manual/memory/memory

初始化

1.rt_system_heap_init

  • 对堆开始地址与结束地址进行内存对齐
  • 在ART-PI中将所有剩余ROM划分给堆使用
  • 断言堆设置是否正常
  • 根据配置的内存策略 使用 _MEM_INIT
  • 初始化多线程争用锁

小内存管理算法

  • 小内存算法在分配内存的时候，随着内存碎片的增多，分配速度会越来越慢，当总的内存太大的时候，内存碎片的数量可能会更多，此时这种算法就会变得不再适用。
  • 小内存管理算法主要针对系统资源比较少，一般用于小于 2MB 内存空间的系统
  • 每个内存对象的起始12字节不可使用,设置为堆系统的配置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//这是一个掩码，用于将内存地址的最低位清零。在 RTT 的内存管理中，内存块的地址的最低位被用作标记该内存块是否被使用。

#define MEM_MASK             0xfffffffe

//这个宏用于标记内存块 _mem 为已使用。它首先使用 MEM_MASK 将 _mem 的最低位清零，然后将最低位设置为 1，表示该内存块已被使用。

#define MEM_USED(_mem)       ((((rt_base_t)(_mem)) & MEM_MASK) |0x1)

#define MEM_FREED(_mem)      ((((rt_base_t)(_mem)) & MEM_MASK) |0x0)

//这将使用 ~MEM_MASK（即 MEM_MASK 的按位取反）与 pool_ptr 进行按位与操作。由于 MEM_MASK 的最低位是 0，所以 ~MEM_MASK 的最低位是 1。这意味着这个操作将提取出 pool_ptr 的最低位，即内存块的使用状态标记。

#define MEM_ISUSED(_mem)   \

                      (((rt_base_t)(((struct rt_small_mem_item *)(_mem))->pool_ptr)) & (~MEM_MASK))

rt_smem_init

  1. 内存对齐
  2. 内存大小计算;至少需要满足两个 struct rt_small_mem_item结构体;因为堆起始与结束各有一个结构体
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

/* 初始化堆起始位置内存对象*/

struct rt_small_mem_item *mem;

mem        = (struct rt_small_mem_item *)small_mem->heap_ptr;//堆起始位置初始化

mem->pool_ptr = MEM_FREED(small_mem);//小内存堆对象地址 设置为释放

mem->next  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;//下一个内存对象设置到堆结尾内存对象

mem->prev  = 0;//上一个对象为空

//写入堆起始位置分配的内存名称

rt_smem_setname(mem, "INIT");


/* 堆大小 */

small_mem->mem_size_aligned = mem_size;

/* 指向堆的起始地址 */

small_mem->heap_ptr = (rt_uint8_t *)begin_align;

/* 初始化指向堆开始的最低空闲指针*/

small_mem->lfree = (struct rt_small_mem_item *)small_mem->heap_ptr;


//初始化堆结束内存对象性

small_mem->heap_end        = (struct rt_small_mem_item *)&small_mem->heap_ptr[mem->next];//初始化设置为堆起始地址的下一个内存对象为堆结束地址

small_mem->heap_end->pool_ptr = MEM_USED(small_mem);//设置为使用

small_mem->heap_end->next  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;//下一个设置为自身

small_mem->heap_end->prev  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;//上一个设置为自身


//写入堆结束位置分配的内存名称

rt_smem_setname(small_mem->heap_end, "INIT");

alloc分配

  • 使用_MEM_MALLOC,操作 system_heap
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
113
114

rt_size_t ptr;

//从当前的空闲内存块开始，遍历整个内存池，直到找到一个足够大的内存块或者遍历完整个内存池

for (ptr = (rt_uint8_t *)small_mem->lfree - small_mem->heap_ptr;

     ptr <= small_mem->mem_size_aligned - size;

     ptr = ((struct rt_small_mem_item *)&small_mem->heap_ptr[ptr])->next)

{

    //查找未使用的内存且满足大小的区域

    if ((!MEM_ISUSED(mem)) && (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size)

    {

        //获取当前内存块的地址。

        mem = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr];

        //* 如果当前内存块足够大，那么可以将其分割成两个部分，一个用于分配，另一个保留为新的空闲内存块 */

        if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=

                    (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))

        {

                /* 创建新的空闲内存块 */

                ptr2 = ptr + SIZEOF_STRUCT_MEM + size;

                mem2       = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr2];

                mem2->pool_ptr = MEM_FREED(small_mem);

                mem2->next = mem->next;

                mem2->prev = ptr;


                /* 更新当前内存块的next指针，使其指向新的空闲内存块 */

                mem->next = ptr2;


                /* 如果新的空闲内存块不是最后一个内存块，那么更新下一个内存块的prev指针，使其指向新的空闲内存块 */

                if (mem2->next != small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM)

                    ((struct rt_small_mem_item *)&small_mem->heap_ptr[mem2->next])->prev = ptr2;


                /* 更新已使用的内存大小和最大使用内存大小 */

                small_mem->parent.used += (size + SIZEOF_STRUCT_MEM);

                if (small_mem->parent.max < small_mem->parent.used)

                    small_mem->parent.max = small_mem->parent.used;

        }

        else

        {

            /* 更新已使用的内存大小 */

            small_mem->parent.used += mem->next - ((rt_uint8_t *)mem - small_mem->heap_ptr);

            if (small_mem->parent.max < small_mem->parent.used)

                small_mem->parent.max = small_mem->parent.used;

        }

        /* 设置当前分配内存为使用中 */

        mem->pool_ptr = MEM_USED(small_mem);

        //线程分配的设置线程名称

        if (rt_thread_self())

            rt_smem_setname(mem, rt_thread_self()->parent.name);

        else

            //中断分配设置为NONE

            rt_smem_setname(mem, "NONE");

        //如果使用的是已经分配到的最大堆地址

        if (mem == small_mem->lfree)

        {

            /* 在内存之后找到下一个空闲块并更新最低空闲指针 */

            while (MEM_ISUSED(small_mem->lfree) && small_mem->lfree != small_mem->heap_end)

                small_mem->lfree = &small_mem->heap_ptr[small_mem->lfree->next];

        }

    }

}

  1. 第一次分配内存时
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

ptr = 0;

mem = (struct rt_small_mem_item *)&small_mem->heap_ptr[0];//第一个内存对象

//* 如果当前内存块足够大，那么可以将其分割成两个部分，一个用于分配，另一个保留为新的空闲内存块 */

if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=

    (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))

{

    mem2->next = mem->next;//mem2指向堆末尾

    mem2->prev = ptr;//上一个指向堆起始

    mem->next = ptr2;//堆起始的下一个更新为mem2

  

    /* 如果新的空闲内存块不是最后一个内存块，那么更新下一个内存块的prev指针，使其指向新的空闲内存块 */

    if (mem2->next != small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM)

    {

        //堆结尾的内存对象的上一个对象设置为mem2

        ((struct rt_small_mem_item *)&small_mem->heap_ptr[mem2->next])->prev = ptr2;  

    }


}

  1. 再一次分配内存时,如果分配后剩余的内存空间不够再开辟一个内存对象时
1
2
3
4
5
6
7
8
9

/* 更新已使用的内存大小 */

small_mem->parent.used += mem->next - ((rt_uint8_t *)mem - small_mem->heap_ptr);

if (small_mem->parent.max < small_mem->parent.used)

    small_mem->parent.max = small_mem->parent.used;

realloc

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

if (newsize + SIZEOF_STRUCT_MEM + MIN_SIZE < size)//当前内存块大小满足可分配区域

{

    /*分割内存块*/

    small_mem->parent.used -= (size - newsize);


    ptr2 = ptr + SIZEOF_STRUCT_MEM + newsize;

    mem2 = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr2];

    mem2->pool_ptr = MEM_FREED(small_mem);

    mem2->next = mem->next;

    mem2->prev = ptr;

    //合并相邻的未使用内存区域

    plug_holes(small_mem, mem2);

} else {

    /*扩展内存*/

    nmem = rt_smem_alloc(&small_mem->parent, newsize);

    if (nmem != RT_NULL) /* check memory */

    {

        rt_memcpy(nmem, rmem, size < newsize ? size : newsize);

        //释放原使用内存

        rt_smem_free(rmem);

    }

}

plug_holes

  • 处理内存碎片的。它试图通过合并相邻的未使用的内存块（称为“空洞”）来减少内存碎片。这个过程被称为“填充空洞”
  • 获取前一个内存项,尝试合并;获取后一个尝试合并

free

  • 当前地址设置为未使用
  • 写入内存使用为空rt_smem_setname(mem, “ “);
  • plug_holes

slab 管理算法

  • slab 内存管理算法则主要是在系统资源比较丰富时，提供了一种近似多内存池管理算法的快速算法
1
2
3
4
5
6
7
8
9

Linux目前为其“slab”分配器提供了三种选择:

Slab是最初的，基于Bonwick的开创性论文，从Linux内核2.2版开始就可以使用。它忠实地实现了Bonwick的建议，并在Bonwick的后续论文中描述了多处理器的变化。

Slub是下一代替代内存分配器，自2.6.23以来一直是Linux内核中的默认配置。它继续使用基本的“slab”模型，但修复了slab设计中的几个缺陷，特别是在具有大量处理器的系统上。Slub比较简单

SLOB (Simple List Of Blocks)是一种内存分配器，针对内存非常少的嵌入式系统进行了优化——以兆字节为数量级。它在一个块列表上应用一个非常简单的首次拟合算法，这与旧的k&r风格的堆分配器没有什么不同。在消除内存分配器中几乎所有的溢出时，SLOB非常适合具有极端内存限制的系统，但是它不提供第1节中描述的任何好处，并且可能遭受病态碎片。

  • 1.静态内存池管理。

    2.针对小内存块的分配管理（小内存管理算法）

    3.针对大内存块的管理算法（SLAB管理算法）

    前面两篇已经把第1，2种算法看了，现在就来看看第三种算法，第三种算法主要是针对大内存使用的。第二种，小内存算法在分配内存的时候，随着内存碎片的增多，分配速度会越来越慢，当总的内存太大的时候，内存碎片的数量可能会更多，此时这种算法就会变得不再适用。

    SLAB在我看来就是前两种算法的融合。

  • https://club.rt-thread.org/ask/question/438bfc8cfd626cc2.html

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

struct rt_slab

{

    struct rt_memory            parent;                         /**< inherit from rt_memory */

    rt_ubase_t                  heap_start;                     /**< memory start address */

    rt_ubase_t                  heap_end;                       /**< memory end address */


struct rt_slab_memusage

{

    rt_uint32_t     type: 2 ;               /**< page type */

    rt_uint32_t     size: 30;               /**< pages allocated or offset from zone */

};

    struct rt_slab_memusage    *memusage;                       /*内存信息存放 类型+索引*/

    struct rt_slab_zone        *zone_array[RT_SLAB_NZONES];     /* linked list of zones NFree > 0 */

    struct rt_slab_zone        *zone_free;                      /* whole zones that have become free */

    rt_uint32_t                 zone_free_cnt;

    rt_uint32_t                 zone_size;

    rt_uint32_t                 zone_limit;

    rt_uint32_t                 zone_page_cnt;

    struct rt_slab_page        *page_list;

};


/*

 * slab page allocator

 * 页大小及分配信息

 */

struct rt_slab_page

{

    struct rt_slab_page *next;      /**< next valid page */

    rt_size_t page;                 /**< number of page  */


    /* dummy */

    chardummy[RT_MM_PAGE_SIZE - (sizeof(struct rt_slab_page *) + sizeof(rt_size_t))];

};

初始化

  • page初始化,按页释放内存

    • 开始地址的page写入所有内存的页数
    • 下一个指向页对象为NULL
    • slab->page_list指向开始地址

  • 计算zone大小:zone翻倍 比 最小数量 /1024小,则翻倍zone

1
2
3
4
5
6
7
8
9

/* calculate zone size */

slab->zone_size = ZALLOC_MIN_ZONE_SIZE;

while (slab->zone_size < ZALLOC_MAX_ZONE_SIZE && (slab->zone_size << 1) < (limsize / 1024))

    slab->zone_size <<= 1;

  • rt_slab_page_alloc 了 内存信息存放的空间 npage*内存信息结构体

页内存释放

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

voidrt_slab_page_free(rt_slab_tm, void *addr, rt_size_tnpages)

{

    struct rt_slab_page *b, *n;

    struct rt_slab_page **prev;

    struct rt_slab *slab = (struct rt_slab *)m;


    // 确保地址不为空，地址是内存页大小的倍数，且页数不为0

    RT_ASSERT(addr != RT_NULL);

    RT_ASSERT((rt_ubase_t)addr % RT_MM_PAGE_SIZE == 0);

    RT_ASSERT(npages != 0);


    // 将地址转换为rt_slab_page结构体

    n = (struct rt_slab_page *)addr;


    // 遍历slab的页面列表

    for (prev = &slab->page_list; (b = *prev) != RT_NULL; prev = &(b->next))

    {

        // 确保页面数量大于0，且当前页面在释放的页面之后或不重叠

        RT_ASSERT(b->page > 0);

        RT_ASSERT(b > n || b + b->page <= n);


        // 如果当前页面紧邻释放的页面

        if (b + b->page == n)

        {

            //如果当前页面刚好满足释放,则进行合并

            if (b + (b->page += npages) == b->next)

            {

                b->page += b->next->page;

                b->next  = b->next->next;

            }

            return;

        }


        // 如果当前页面刚好满足释放要求,则进行合并

        if (b == n + npages)

        {

            n->page = b->page + npages;

            n->next = b->next;

            *prev   = n;

            return;

        }


        // 如果当前页面比所需的内存页来的大,则退出

        if (b > n + npages)

            break;

    }


    //写入页面信息与下一个节点

    n->page = npages;

    n->next = b;

    //上一个节点指向当前页面

    *prev   = n;

}

页内存分配

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


// 遍历slab的page_list

for (prev = &slab->page_list; (b = *prev) != RT_NULL; prev = &(b->next))

{

    // 如果b的页数大于npages

    if (b->page > npages)

    {

        // 分割页面

        n       = b + npages;

        n->next = b->next;

        n->page = b->page - npages;

        *prev   = n;

        break;

    }


    // 如果b的页数等于npages

    if (b->page == npages)

    {

        // 这个节点适合，移除这个节点

        *prev = b->next;

        break;

    }

}

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

/*

 * 计算分配请求大小的区域索引，并将分配请求大小设置为该区域的块大小。

 */

rt_inline intzoneindex(rt_size_t *bytes)

{

    /* 无符号整数用于位移操作 */

    rt_ubase_t n = (rt_ubase_t)(*bytes);


    if (n < 128)

    {

        /* 对齐到8字节，并计算区域索引 */

        *bytes = n = (n + 7) & ~7;

        return (n / 8 - 1);

    }

    if (n < 256)

    {

        /* 对齐到16字节，并计算区域索引 */

        *bytes = n = (n + 15) & ~15;

        return (n / 16 + 7);

    }

    /* 对于更大的内存请求，使用更大的对齐单位，并计算相应的区域索引 */

    if (n < 8192)

    {

        /* ...省略部分代码... */

    }

    if (n < 16384)

    {

        /* 对齐到1024字节，并计算区域索引 */

        *bytes = n = (n + 1023) & ~1023;

        return (n / 1024 + 55);

    }


    /* 如果内存请求大小超出预期，打印错误信息 */

    rt_kprintf("Unexpected byte count %d", n);


    return0;

}

没有分配过或者用光了

  1. 该zone没有被使用过

    • 从页面分配一个区域,设置内存信息 memusage的类型与索引,设置zone空间信息
    • 计算块地址,链接到zone数组中

  2. 该zone被使用过

    • 直接分配,从zone_free中移除
有zone数组

  1. 分配完了,从zone数组中移除

  2. 可分配,执行分配

  3. 没有可分配空间

    • 在空闲块列表中查找(free的时候分配)
    • 从空闲块列表中删除此块

free

大内存释放

  • 直接释放,size设置为0

小内存释放

  • 将内存设置标识下一个free块节点为free块

  • 将当前free块设置为当前内存

  • 如果zone释放后可以提供分配了,添加回zone数组中

  • 如果该区域完全空闲，并且我们可以从其他区域进行分配，则将该区域移到FreeZones列表中

    -空闲区域计数和释放：每当一个区域被移动到空闲区域列表中，空闲区域的计数（slab->zone_free_cnt）就会增加。如果空闲区域的数量超过了设定的阈值（ZONE_RELEASE_THRESH），那么就会释放一个区域到页面分配器。

    -页面的释放：在释放区域到页面分配器之前，会设置每个页面的使用情况（kup->type = PAGE_TYPE_FREE; kup->size = 0;）。然后，调用 rt_slab_page_free()函数来释放这些页面。

memheap 管理算法

  • memheap 方法适用于系统存在多个内存堆的情况，它可以将多个内存 “粘贴” 在一起，形成一个大的内存堆，用户使用起来会非常方便

init

  • 计算可用大小
  • 设置信息
  • 设置链表

alloc

  • 可用分配

  • 从链表中寻找可分配的内存

    1. 寻找到可分配的内存,分割进行分配
    2. 找不到;继续从最后一个内存往后分配

free

  • 释放
  • 查找是否可以与临近的内存合并,进行合并

malloc&&realloc分配

  1. 线程中使用加锁,中断中使用不加锁
  2. _MEM_MALLOC 调用不同内存算法的malloc
  3. 解锁
  4. 调用malloc call函数

TLSF 内存管理算法

https://www.cnblogs.com/pwl999/p/15534968.html

堆初始化

  1. 创建内存池
  • 清空结构体信息
  1. 添加内存池
  • 传递给给定内存块中的 TLSF 结构的开销 tlsf_add_pool，等于空闲块的开销和哨兵块。
  • 创建主要空闲块。稍微偏移块的起点以便 prev_phys_block 字段落在池之外它永远不会被使用。

使用 const的原因有很多：提高代码的可读性：const关键字告诉读代码的人这个变量的值不会改变，这有助于理解代码的行为。防止误操作：在函数的其余部分，如果你试图改变 oldsize的值，编译器会报错，因此可以防止因误操作而导致的错误。优化性能：编译器知道 const变量的值不会改变，可能会进行一些优化。

  • 设置块的大小,并设置该块为未使用,设置下一个块为使用中
1
2
3
4
5
6
7

constsize_t oldsize = block->size;

//保留原有的oldsize使用标志不变的情况下,设置新的size

block->size = size | (oldsize & (block_header_free_bit | block_header_prev_free_bit));

  • 插入新的块
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

staticvoidmapping_insert(size_tsize, int *fli, int *sli)

{

    int fl, sl;

    if (size < SMALL_BLOCK_SIZE) // 如果大小小于小块的大小

    {

        /* Store small blocks in first list. */

        fl = 0; // 第一级索引设置为0

        sl = tlsf_cast(int, size) / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT); // 第二级索引根据大小和小块的数量进行计算

    }

    else // 如果大小大于或等于小块的大小

    {

        fl = tlsf_fls_sizet(size); // 使用位操作找到最高位的1，也就是第一级索引

        sl = tlsf_cast(int, size >> (fl - SL_INDEX_COUNT_LOG2)) ^ (1 << SL_INDEX_COUNT_LOG2); // 使用位操作计算第二级索引

        fl -= (FL_INDEX_SHIFT - 1); // 调整第一级索引，使其从0开始

    }

    *fli = fl; // 返回第一级索引

    *sli = sl; // 返回第二级索引

}

  • 分割块以创建零大小的哨兵块

添加堆

  • 根据地址添加池
  • 添加当前堆到链表中

malloc