共享个简易的动态内存管理，支持智能指针，碎片整理

Pony279 · 发表于 2012-8-11 23:16:24

简单的学习了一下malloc的原理后花了几天编写和测试的，
malloc 的原理的资料大家可以看我之前发的帖子 http://www.openedv.com/posts/list/7332.htm

本来想把代码的原理也解释清楚，昨晚写了一个小时发现不好写，然后电脑突然死机也就没了，
不好写就算了，以后有时间再写详细些补上，基本原理也可以参考那个帖子里的资料。

上传的是测试代码，测试函数有 Test1 和 Test2，两个函数基本一样
函数 Test1 和 Test2 的不同之处在于局部变量数组 array 的类型不同，
另外为了突出碎片整理的优势，Test1 最后一次会申请 80 字节但是失败，而 Test2 最后一次会申请 300 字节而且成功。

测试代码会在串口里返回很多信息，也可以直接通过软件仿真来看，信息很长，大概的结构是这样的：
初始化信息...
Test1: 智能指针功能测试
申请内存...
释放部分内存...
再次申请80字节内存，结果申请失败
Test1结束，原来申请的内存全部释放
Test2: 碎片整理功能测试
申请内存...
释放部分内存...
再次申请300字节内存，结果申请成功
Test1结束，原来申请的内存全部释放
...

也有些许多不完善的地方，分配的算法和碎片整理算法效率并不高，不过对于 stm32 这样的内存不大的 MCU 我认为已经够用了。
还有一点比较致命的就是 thread-safe，也就是多线程的时候的安全性，不过反正现在不搞OS，暂时不考虑这个问题。

主要的代码在 main 文件夹下的 allocator.h 和 allocator.cpp

正点原子 · 发表于 2012-8-12 01:47:58

碎片整理不好做吧.
有些你原来申请了的,还在用的,是不能释放的.你只能把零碎的空间拼接在一起,组成一个大一点的内存区,再去分配.过程涉及到内存移动,组合.是一个复杂的过程.

Pony279 · 发表于 2012-8-12 02:22:52

是的，碎片整理确实比较麻烦。我采取的方案是设计两个封装类。
allocate 返回的对象属于第一个封装类的，这种封装类引用着用户申请的内存，所有引用着同一块内存的对象形成一个链表，这样，当我移动那块内存的时候，可以顺着链表找到所有需要修改的指针。但是由于这个特点，第一个封装类的对象不能当指针使用。只是这种封装类的对象存在时它引用的内存不能被释放，只能被移动。这个类是实现碎片整理的关键。
所以又有了第二个封装类，重载必要的操作符，直接当指针使用，理论上和直接操作指针一样高效，但是一旦这个对象存在，内存即被加锁，不能被移动。
用法就是平时持有第一个封装类的对象实现碎片整理，要用时可以方便的转为第二个封装类的对象实现高效的使用。比如文件系统的缓冲区，其中只有在调用文件系统的函数时才算是使用了指针，但是文件又一直开着，所以平常只持有第一个封装类，申请的内存里保存着必要的数据，但那块内存又允许被移动。

正点原子 · 发表于 2012-8-12 10:16:38

碎片整理,我有个不明白的地方就是,比如我有个指针P.他先用malloc申请一片内存.比如malloc返回给P的地址是0X20001234;
P一旦申请,就由一个任务使用,假定不释放.
考虑内存不足的时候,当另外一个任务需要申请一片内存X的时候,出现内存不足,假定此时内存可以通过整理碎片来腾出足够的空间给X,而且P必须移动.也就是说P的地址0X20001234,你必须要改变,这个时候,你通过什么机制让一个正在运行的任务而且不再调用与内存管理相关的函数,去改变它的地址?
在标准C的实现机制下,貌似这是个不可能的任务....
如果P的地址无法再改变,也就是碎片整理实际没有实现.

Pony279 · 发表于 2012-8-12 12:23:44

如果让用户直接持有指针，这个任务确实是没办法实现的，主要是因为内存管理模块无法得到所有需要修改的指针
但是如果不直接分配出指针，而是把指针和一个链表捆绑在一起，就可以修改指针P的内容了。
再利用C++的对象构造析构的语法，链表的结构会自动维护。

为了实现比较高速的访问内存，所以我弄了两个封装来，一个用来持有内存，另一个用来访问内存，用户在访问内存的时候那个内存块也是不可以被移动的。对于长期在堆里存在的被占用的内存，总有被用户持有但是又没有被访问的时候，就在这个时候允许移动这段内存。

记得 MFC 的一些也是类似这样的机制，好像是 CString，本来它内部是自动维护着动态内存的，当用户需要直接访问那段内存的时候，必须把那段内存加锁，得到指针，不使用时再解锁。

zenghi · 发表于 2012-8-13 22:48:13

这才是境界，连对话都看不明白。建议我们这些只懂初始化内存空间，然后malloc 以及free的可以认真仔细的看看。
先顶顶。

Pony279 · 发表于 2012-8-14 01:03:58

回复【6楼】 zenghi :
---------------------------------
呵呵，其实基本原理并不难，主要还是利用了链表以及C++的语法

-------------------------------------------------------------------------------------------

楼主位的代码还算不上是比较完整的内存管理，主要是在释放内存的时候堆上的对象不会被自动析构
在C++里面对象的析构常常是很重要的，所以就对 1 楼的代码补充和完善了一下，
楼主位的代码只是简单的测试，对于如何使用也没有做完整的说明，
这里上传的测试代码算是比较完整的了，串口打印的信息也不会像之前那个那么长...

注释还算是比较详细，怎么使用应该算是说清楚了。

charlieholy · 发表于 2013-4-20 20:02:46

回复【7楼】Pony279:
---------------------------------
恩链表确实比较灵活
操作系统的任务用链表也比较灵活

charlieholy · 发表于 2013-4-20 20:28:30

楼主的代码居然是C++架构的长见识了
终于发现MDK支持C++了

lyc374312116 · 发表于 2013-11-25 21:22:18

回复【7楼】Pony279:
---------------------------------
请教pony哥和原子哥
如果做控制类，需要学C++吗感觉很难它在单片机上有什么用？

Pony279 · 发表于 2013-11-26 19:13:49

回复【10楼】lyc374312116:
---------------------------------
    编程语言只是个工具，如果是给MCU编程，现在的主流是C，会不会C++没什么影响。如果是在PC端或者是服务器端编程，语言很多，通常C语言是必须会的，语言的选择很大程度上由和你一起工作的人以及项目历史的代码决定的，除非你很牛逼自己带领一个新项目（那个时候你就不会问这些问题了）。
    我以前基本上只会点C++，现在工作几个月，基本上Java，PHP，C/C++，Linux，DB，HTML，JS，CSS都要搞，虽然看上去很多很杂，实际上如果已经懂一门编程语言，其他语言会的学的比较快。所以你现在不必纠结编程语言，需要你学的时候自然就会，当然如果你很有空可以先学一门面向对象的语言，C++或者JAVA都行。
    如果不是做计算机研究的，不需要对一门语言有深入的理解，通常了了解个大概，自己只用一门语言的简单的一部分特性，养成自己良好的风格就足够的，业务逻辑都是直来直去的，不需要什么“牛逼”的编码就能做成，重点是专注自己的业务/目标，用你需要的东西，否则谈什么设计模式的都是扯淡。