对RTT小内存管理算法的分析和理解

发布于 2012-09-28 03:18:44 浏览：9049 订阅该版

[tocm]

RT-Thread内存管理·小内存管理算法分析
2012年9月28日星期五

## 前言：
母语能力有限，纠结的地方海涵！

## 概述：

这篇文字和大家分享一下今晚对RT-Thread的内存管理——小内存管理算法的理解。若有不对的地方请大家丢砖。
　　
## 正文：
分析的源码文件mem.c
主要的几个函数：
- 1、rt_system_heap_init
- 2、rt_malloc
- 3、rt_free
- 4、plug_holes

Armcc编译器中的初始化内存的方式：
```c
rt_system_heap_init((void*)&Image$$RW_IRAM1$$ZI$$Limit, (void*)STM32_SRAM_END);
```

接触RTT半年以来，对这里的第一个参数是又爱又恨，爱它的神秘怪僻，恨它的怪僻神秘。
```c
extern int Image$$RW_IRAM1$$ZI$$Limit;
```

从这里可以看得出它是火星人还是地球人。不错这样的声明我们大概能知道的是仅仅只是一个变量而已。不过它的定义在何处？我纠结到昨天晚上才见到它真实的面貌（这还多亏aozima的指点）。这是一个链接器导出的符号，代表ZI段的结束，也就是程序执行区的RAM结束后的（注意这个‘的’，有点i++和++i的意思）地址，反过来也就是我们执行区的RAM未使用的区域的起始地址（其实这里有点牵强，因为这样理解往往只是一个准寻的标准，以为在RAM的使用上ZI区往往是整个程序的最末尾，也许这里我理解错了）。有关于这个符号的具体详情请见链接器文档分解，谢谢！

第二个参数就是整个RAM的结束地址。所以从这两个参数上可以知道传递进去的是内存的管理区域。

### rt_system_heap_init

这个函数是对堆进行初始的过程，堆的大小由传进来的起始地址（begin_addr）和结束地址（end_addr）决定。当然如果我们还要考虑内存对齐，这样一来，我们能使用的堆大小就不一定完全对于（end_addr - begin_addr）了。
```c
rt_uint32_t begin_align = RT_ALIGN((rt_uint32_t)begin_addr, RT_ALIGN_SIZE);
　　rt_uint32_t end_align = RT_ALIGN_DOWN((rt_uint32_t)end_addr, RT_ALIGN_SIZE);
```

这两句进一步对传递的起始地址后结束地址进行对齐操作了，有可能在起始地址上往后偏移几个字节以保持在对齐的地址上，也有可能在结束地址的基础上往前偏移几个字节以保持在对齐地址上。所以这里就有可能被扣掉一点点的内存。但是这往往是很小的一点点，通常小到几个字节，也许刚好是一个都没有被扣掉。
```
if ((end_align > (2 * SIZEOF_STRUCT_MEM)) &&
　　	((end_align - 2 * SIZEOF_STRUCT_MEM) >= begin_align))
　　{
　　	/* calculate the aligned memory size */
　　	mem_size_aligned = end_align - begin_align - 2 * SIZEOF_STRUCT_MEM;
　　}
```

这部分是计算最大可分配的内存区域，？？？？？，为什么说是最大‘可’分配的内存区域呢？
因为还将被继续扣除一部分内存，这部分被扣除的内存是用来放置内存管理算法所要用的数据结构。越精巧的算法当然是效率更高，浪费的也最少。

RTT扣掉了2个数据结构的尺寸，因为RTT有一个heap_ptr和一个heap_end这两个标记，分别表示堆的起始和结束。mem_size_aligned就是整个可操作的区域尺寸。

RTT的内存管理用到的数据结构非常的精简。
```c
struct heap_mem
　　{
　　	/* magic and used flag */
　　	rt_uint16_t magic;
　　	rt_uint16_t used;
　　
　　	rt_size_t next, prev;
　　};
```

总共占用了`2+2+2xcpu字长（8个字节）=12`个字节。其中magic字段用以标记一个合法的对内存块，used字段标记这个堆内存块是否被分配，next字段指向当前这个堆内存块的末尾后1个字节（不说成是下一个可分配块，是因为也许next指向了末尾），prev指向当前这个内存块的前一个有效内存块的数据结构起始处，否则指向自身（最前面那个内存块）。所以可以看出这个设计思路是把整个内存块用列表的形式组织在一起。当然我们使用的next和prev只是相对于其实地址heap_ptr的偏移量，而不是真正在通常列表中看到的指针。

接着标记了第一块可分配的内存块，这个内存块把`mem_size_aligned`个字节大小划分出来，留下SIZEOF_STRUCT_MEM个字节的大小用来刚好放置heap_end，在前SIZEOF_STRUCT_MEM个字节中也就是最前面的SIZEOF_STRUCT_MEM个字节用来放置heap_ptr。其中第一个可分配点就是从heap_ptr开始的，heap_prt的next指向了heap_end（也就是`mem_size_aligned + SIZEOF_STRUCT_MEM`），大致的初始时候的布局如下图所示：

最后让lfree指向当前活动的可分配的内存块，这样可以迅速找到最进被释放的内存块上。一般只要之前分配的内存块被释放后，lfree就尽量分配靠前的内存区域，因为越到后面那能使用的区域就越紧张。

### rt_malloc

首先对申请的尺寸做对齐处理，所以这个对齐操作只会有可能比实际分配的尺寸要大一点。
```c
for (ptr = (rt_uint8_t *)lfree - heap_ptr; ptr < mem_size_aligned - size;
　　	ptr = ((struct heap_mem *)&heap_ptr[ptr])->next)
```
循环查找从当前lfree所指向的区域开始查找一块能够满足区域的内存块，这个内存块有可能在之前是被分配过的，所以可以用next来索引下一块可分配点。

```c
if ((!mem->used) && (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size)
```

当这块内存区域没有被使用，且这块内存区域扣掉头部数据结构SIZEOF_STRUCT_MEM后的大小满足所需分配的大小那么就可以使用这个内存块来分配。

```c
if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >= (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))```
　　如果这个即将被分配的内存块除了能分配给当前尺寸后，还余下的有足够的空间能够组织成下一个可分配点的话，那么将对余下的部分组织成下一个可分配点。

否则把当前这个内存块标记为已分配状态used=1。如果当前被分配的内存块是lfree指向的内存块，那么调整lfree，以让其指向下一个可分配的点。
```c
if (mem == lfree)
　　{
　　	/* Find next free block after mem and update lowest free pointer */
　　	while (lfree->used && lfree != heap_end)
　　		lfree = (struct heap_mem *)&heap_ptr[lfree->next];
　　
　　	RT_ASSERT(((lfree == heap_end) || (!lfree->used)));
　　}
```

之后将得到的内存点返回，这个时候不是返回这个可分配点的其实地址，而是返回这个可分配点的其实地址偏移一个数据结构尺寸的地址，以为每个可分配的内存块都在其前面有一个用于管理内存所需用到的一个数据结构。
```c
return (rt_uint8_t *)mem + SIZEOF_STRUCT_MEM;
```

如果当前这个循环从lfree开始查找，第一次没有找到合适的内存块，那么继续往后找，循环的判断条件是只要next小于`mem_size_aligned - size`就或许能找到一个合适尺寸的内存块。否则将分配失败，返回NULL。

### rt_free

调用这个函数一般是释放由rt_malloc函数所分配的内存。所以使用rt_malloc函数返回的内存块地址如果需要释放的时候，就需要调用rt_free。由于在rt_malloc和rt_free的外面使用者来说，是不知道这个内存地址的前面有一个管理数据结构的，所以在rt_free的时候需要往前偏移SIZEOF_STRUCT_MEM个字节，用以找到数据结构的起点。
```c
　　mem = (struct heap_mem *)((rt_uint8_t *)rmem - SIZEOF_STRUCT_MEM);
```
接着讲这个内存块标记为未被分配的状态。
```c
mem->used = 0;
　　mem->magic = 0;```
如果释放的内存地址在lfree的前面，然后将lfree指向当前释放的内存块上。
```　　if (mem < lfree)
　　{
　　　　/* the newly freed struct is now the lowest */
　　　　lfree = mem;
　　}
```

之所以这样调整lfree是因为使其尽可能在下一次分配的时候从最前面的可用块上寻找合适的分配点。因为越靠近后面的话，内存分配就越紧张。

最后调用plug_holes函数进行一些附加的优化操作，这个优化操作是必不可少以及体现整个内存分配算法核心价值的地方。

### plug_holes

这个函数的作用是合并当前这个内存点的前后紧接着的已经被释放的内存块。这样一来可以解决内存碎片问题。
```c
nmem = (struct heap_mem *)&heap_ptr[mem->next];
　　if (mem != nmem && nmem->used == 0 && (rt_uint8_t *)nmem != (rt_uint8_t *)heap_end)
　　{
　　	/* if mem->next is unused and not end of heap_ptr, combine mem and mem->next */
　　	if (lfree == nmem)
　　	{
　　		lfree = mem;
　　	}
　　	mem->next = nmem->next;
　　	((struct heap_mem *)&heap_ptr[nmem->next])->prev = (rt_uint8_t *)mem - heap_ptr;
　　}
```

这是看其后面的内存点是否可以被合并，合并其后的内存块的时候只需要调整当前内存块的next值。其次还需要调整当前内存块后的内存块的下一个内存块的prev字段（这里有点绕口，其实就好比普通列表中的`p->next->next->prev`），使其指向当前本身的内存块（好比`p->next->next->prev = p`）。

```c
pmem = (struct heap_mem *)&heap_ptr[mem->prev];
　　if (pmem != mem && pmem->used == 0)
　　{
　　	/* if mem->prev is unused, combine mem and mem->prev */
　　	if (lfree == mem)
　　	{
　　		lfree = pmem;
　　	}
　　	pmem->next = mem->next;
　　	((struct heap_mem *)&heap_ptr[mem->next])->prev = (rt_uint8_t *)pmem - heap_ptr;
　　}
```

这是合并当前内存块前面的已被释放的内存块，先去的前面的内存块，然后调整前一个内存块的next指向当前内存块的next所指的地方，接着讲当前内存块的下一个内存块的prev字段指向当前内存款的前一个内存块（好比`p->next->prev = p->prev`）。

这样两大步就可以将当前释放的内存块的前后两个已经被释放的内存块给合并成一个大的内存块。从而避免了碎片问题，提高了内存分配的可靠性。

在此告一段落，欢迎对文中理解和解释不正确的地方进行指正！

3时16分46秒

7 个回答

aozima 2012-09-28

调网络不抓包，调I2C等时序不上逻辑分析仪，就像电工不用万用表！多用整理的好的文字，比截图更省流量，还能在整理过程中思考。

geniusgogo 认证专家 2012-09-29

这家伙很懒，什么也没写！

>Romeo<xpxyr@sina.com> 15:07:38
```

```
Image$$RW_IRAM1$$ZI$$Limit
```

```
表示ZI的结束，RTT的堆管理区域就是从这里开始的，
现在我有点疑问，
```
Image$$RW_IRAM1$$ZI$$Limit
```
> 开始就是堆管理的内存。那么局部变量也就是栈分配是从那里开始的？

>aozima     15:18:10
>>那么局部变量也就是栈分配是从那里开始的？
局部变量都是从栈中分配的,那么：线程的中的局部变量是从线程栈中分配的。

> 线程启动之前（main函数这）及 中断服务函数中的局部变量
是从系统栈中分配的，系统栈是在编译链接时确定的，
> 
> 其地址在
```
Image$$RW_IRAM1$$ZI$$Limit
```
之前，也就是RESET的第一条的那个名称所在。

> aozima     15:18:30
以上仅对 ARM cortex-M系列而言

> aozima     15:23:19
```
Execution Region RW_IRAM1 (Base: 0x20000000, Size: 0x00009bb0, Max: 0x00020000, ABSOLUTE, COMPRESSED[0x00000f50])
Base Addr    Size         Type   Attr      Idx    E Section Name        Object
0x200095b0   0x00000200   Zero   RW         1276    HEAP                startup_stm32f4xx.o
0x200097b0   0x00000400   Zero   RW         1275    STACK               startup_stm32f4xx.o
```

> aozima     15:23:57
这是链接后出来的MAP文件，
```
0x200097b0   0x00000400   Zero   RW         1275    STACK               startup_stm32f4xx.o
```
> 就是系统启动前和中断所用的栈

> Romeo<xpxyr@sina.com> 15:24:38
嗯 这里我能想到的是线程中的局部变量是从线程栈分配的，线程栈有两种，一种是全局的在
```
Image$$RW_IRAM1$$ZI$$Limit
```
> 之前，一种就是用rt_malloc分配的，所以这两种作为线程栈都是没有问题的，至于“线程启动之前（main函数这）及 中断服务函数中的局部变量是从系统栈中分配的，系统栈是在编译链接时确定的，”这个今之前还真想不到是怎么分配的，现在收获了，多谢。  而我在思考的是RTT的这种内存分配方式如果放在裸机中，也就是只移植RTT的内存管理功能到裸机开发中，那么就不存在线程栈了，也就是所有的局部变量都需要从 “不知名的栈”上分配（难道就是“线程启动之前（main函数这）及 中断服务函数中的局部变量
是从系统栈中分配的，系统栈是在编译链接时确定的，”？？？），

> aozima     15:26:48
> main.c
> ```c
uint32_t sys_stack[1K];
int main(void)
{
SP = sys_stack;
printf("hello world!
");
}
```

> aozima     15:26:53
你可以这样理解。

> Romeo<xpxyr@sina.com> 15:28:09
意思就是说  裸机开发的话 局部变量都是从启动文件中指定的栈上分配的？ 且和中断都是使用同一个栈？

> aozima     15:28:40
一般是这样，但并不一定是这样，都是由用户指定的。

> aozima     15:29:13
cortex-M上电后自动把0地址的  地址  做为 栈地址

> Romeo<xpxyr@sina.com> 15:29:36
嗯 这个看手册上有说

> aozima     15:29:36
所以， 启动文件里面都把分配的栈空间地址放上去

> aozima     15:29:58
然后根据模式的不同   系统栈和中断栈可以不是一个。

> aozima     15:30:18
不过上电启动是MSP   中断也是MSP，所以一般就设置成一个。

> aozima     15:30:36
而线程栈，可以使用PSP

> aozima     15:30:48
如果是ARM7 ARM9，只有一个栈，则要自己切换。

> Romeo<xpxyr@sina.com> 15:32:23
`__initial_sp`这个代表MSP的起始栈地址   而`Stack_Size`代表msp的栈空间大小

> Romeo<xpxyr@sina.com> 15:32:37
那么程序在跑的时候 如果超出了Stack_Size会怎么办？

> Romeo<xpxyr@sina.com> 15:33:09
因为如果裸机的话是没有从MSP切换到PSP的，

> aozima     15:33:10
这个么，试下就知道了。

> aozima     15:33:58
各函数用了多少栈可以从链接器的报告中查到。
然后把栈空间设置得比这个大一些。

> aozima     15:34:10
然后在运行后，检查最大深度。

> aozima     15:34:28
如果有递归，则要保证层数是可预测的。

> Romeo<xpxyr@sina.com> 15:35:31
嗯 我先实验去  多谢

> bernard(6278495) 15:49:56
栈这个，关键在于CPU的栈地址是可以设置的，所以栈地址可以换来换去，属于任务自己的私有属性

> bernard(6278495) 15:50:49
CPU刚启动时，用的是系统栈。当调度器启动后，切换到第一个任务，自然也就把这个任务的栈替换到当前的CPU栈寄存器上了

> Romeo<xpxyr@sina.com> 15:51:46
在裸机开发中 只使用了CM3的MSP， 而这个MSP的起始地址和长度是指定了的 默认在
```
Image$$RW_IRAM1$$ZI$$Limit
```
前面

> bernard(6278495) 15:52:09
这个栈是预先设定的

> bernard(6278495) 15:52:25
可以想象为一个数组，例如`char array[1024]`。

> Romeo<xpxyr@sina.com> 15:53:04
嗯 如果函数的局部变量太多了是不是可能越界？

> Romeo<xpxyr@sina.com> 15:53:13
出现内存错误？

> bernard(6278495) 15:53:19
是啊，这就是经典的栈溢出

> Romeo<xpxyr@sina.com> 15:55:22
好  那我再问  在裸机开发cm3这种处理器，MSP是从启动文件给定的，这个是明确的。   所以在开发过程中 函数的局部变量就有可能超出这个启动文件给定的栈空间，所以也就会出现你说的“经典的栈溢出”？

> Romeo<xpxyr@sina.com> 15:56:01
而不会自动从
```
Image$$RW_IRAM1$$ZI$$Limit
```
> 后面分配，  所以我如果移植RTT的内存管理功能到逻辑开发中是可行的 对吧？

> bernard(6278495) 15:56:00
en

> Romeo<xpxyr@sina.com> 15:56:32
明白了 马上去更新帖子 免得误导人啊

> bernard(6278495) 15:56:39
这个栈溢出在RTT中也会存在

> bernard(6278495) 15:56:53
内存管理功能移植到裸机中，也是可行的

> Romeo<xpxyr@sina.com> 15:56:59
就是在线程还没调度的时候？

> bernard(6278495) 15:57:16
只是需要把使用到的RTT信号量、中断相关的给屏蔽掉

> Romeo<xpxyr@sina.com> 15:57:34
哦 因为此时中断也会用MSP哦

> bernard(6278495) 15:57:37
在线程还未调度是可能出现栈溢出，在线程运行过程中也会出现栈溢出

> Romeo<xpxyr@sina.com> 15:58:10
“在线程运行过程中也会出现栈溢出” 是线程栈溢出还是MSP？

> Romeo<xpxyr@sina.com> 15:59:34
哦 一个道理  都有可能是因为中断中使用MSP而照成的溢出吧？

> bernard(6278495) 15:59:34
线程栈溢出

> Romeo<xpxyr@sina.com> 15:59:55
我们现在先不说线程栈

> Romeo<xpxyr@sina.com> 15:59:58
直说MSP

> bernard(6278495) 15:59:57
栈的空间就这么些，所以总是存在溢出的风险

> Romeo<xpxyr@sina.com> 16:00:30
MSP栈在RTT开始调度后会因为中断且套而导致MSP栈溢出？

> bernard(6278495) 16:01:36
会的

> bernard(6278495) 16:01:45
栈用多了，当然就溢出了

> bernard(6278495) 16:02:25
一个ISR中，直接来个
```c
isr()
{
char buffer[128 * 1024];
}
```
> 想不爆都不行

> Romeo<xpxyr@sina.com> 16:02:41
> 明白了 只能说是存在栈溢出的可能，  而不是必然的 哈哈  因为你们已经在发布的时候调整了一个合理的MSP

>Romeo<xpxyr@sina.com> 16:02:47

> bernard(6278495) 16:03:57
> 当前还未做MSP的栈检查，线程栈会做一定的检查，能够稍微提示出是栈溢出导致的问题

今天比较赶时间，不准备整理了，请认真阅读以上内容，谢谢！
这是写完上篇文字后自己思考总结出来的疑点，怕误导诸位，所以今天请教了大牛们。以上是和大牛们在群里对话的内容。如有相同疑问可以好好琢磨一下这段对话内容。

crystal266 2022-05-08

嵌入式

请登录后再发布评论，点击登录

追加回复

grissiom 2012-10-01

这家伙很懒，什么也没写！

bernard 2012-10-01

这家伙很懒，什么也没写！

prife 2012-10-13

这家伙很懒，什么也没写！

小ARM菜菜 2013-03-29

这家伙很懒，什么也没写！

撰写答案

关注者

被浏览

关于作者

geniusgogo

这家伙很懒，什么也没写！

提问

回答

157

被采纳

关注TA

发私信

本月文章贡献

7 篇文章 2 次点赞

3 篇文章 4 次点赞

1 篇文章 2 次点赞

1 篇文章 1 次点赞

1 篇文章 1 次点赞

回到
顶部

发布
问题

手机
浏览

扫码手机浏览

回到
底部

对RTT小内存管理算法的分析和理解

撰写答案

关于作者

geniusgogo

相关问题

热门标签

本月文章贡献

对RTT小内存管理算法的分析和理解

撰写答案

关于作者

geniusgogo

相关问题

推荐文章

最新文章

热门标签

本月问答贡献

本月文章贡献