█ 1
内存管理
李 云
Blog: https://www.doczj.com/doc/e317122626.html,
你将学会
● 非固定大小内存分配管理的一种具体实现。 ● 内存分配管理为什么要注意字节对齐。 ● 什么是内存写上溢和写下溢。
● 如何设计让内存管理模块能检测出内存写上溢和写下溢。 ● 什么是内存泄漏以及检测内存泄漏的常用方法有哪些。 ● 如何设计内存管理模块让其能帮助检测出内存泄漏。 ●
固定大小内存分配管理的一种具体实现。
关键词
嵌入式
嵌入式系统
内存管理
参考资料
《驾驭Makefile 》 《错误管理》 《堆和栈》
1 引言
说到内存管理，你可能会一下子想到malloc ()和free ()这两个来自C 库的函数。内存管理是操作系统中很重要的一部分内容，这对于嵌入式系统来说也不例外。堆（heap ）和栈（stack ）是操作系统中非常重要的两个概念，通常所说的内存管理就是指堆管理，是一种按用户所需大小进行内存分配的方法（或算法）。在嵌入式系统中，除了采用类似C 库中的malloc ()和free ()这种按非固定大小进行内存分配的方法外，通常还会使用按固定大小进行内存分配的方法。对于这两种分配方式，后者的分配速度明显快且速度稳定，也不会产生内存碎片。在对于性能要求相对高的嵌入式系统模块（比如，与外设中断相关）中，采用固定大小分配内存的方法非常受欢迎。 另外，在有些嵌入式系统中根本就不存在明确的内存管理模块，而是直接采用全局数组变量的方式来分配内存的使用。当然，我们也可以将其理解成一种特殊的内存管理方式，这种方式的好处是能节省代码空间（即节省内存），因为不需要有相应的内存分配函数以及用于存放内存管理信息的数据结构。但这种方法也存在明显的问题 —— 不够灵活，进而有可能出现内存不足了，却直到程序使用了不存在的内存时才发现。
无论是哪一种内存分配方法，从程序员的角度来说，内存管理模块的实现就是提供分配和释放（堆）内存的API 。当然，在这里我们的目的不是去了解如何命名一个API ，而是希望了解这些API 背后的实现机理及设计时的考虑。在本章，我们将通过做项目的形式来分别介绍非固定大小和固定大小内存分配方法的一种实现，同时，通过改进来了解设计一个实用的内存管理模块应当考虑些什么。需要指出的是，这里所介绍的内存管理实现，其目的是让你能理解嵌入式系统中的内存管理到底是什么，而不在于为读者提供一种最优的内存管理算法。内存分配算法有很多种，你可以参照专门介绍操作系统的书籍来掌握更多的内存分配算法，或者，你可以参照一些开源软件项目去了解特定的内存管理算法。比如，通过阅读GLIBC 源代码目录结构中的malloc 子目录中的代码去了解Linux 中的堆内存管理是如何实现的，等等。
内存管理是一个比较复杂的话题，对于嵌入式系统尤为如此，因为嵌入式系统的资源往往更为有限。在设计内存管理模块时，我们不得不在速度和内存管理模块自身所占用的资源之间进行权衡。可以肯定的是，为了分配速度更快或更少的内存碎片，则需要使用更多的内存以用于增加额外的管理信息。任何嵌入式内存管理算法，最终都得在效率与管理信息所占用内存空间的大小之间进行平衡。当然，如何找到一个最佳的平衡点，这就是不同算法的区别所在。
1.1设计考虑
在讲解具体的内存管理实现时，我们需要了解内存管理设计方面的一些考虑因素。毫无疑问，效率是内存管理模块很重要的一个技术指标，这一指标随不同的算法而有所区别。除了效率之外，还有其它的因素也非常的重要，这些因素有些不仅仅是针对内存管理模块的，而是普遍适用于其它软件产品的设计。
第一个我想要说的是内存模块分配出来的内存地址必须是以一定的字节为边界对齐的，为什么呢？我们知道，从内存管理模块分配出来的内存，可以被运用于转换成任意的具体数据结构。假设用户想分配一个int变量所需的内存，且这一分配是发生在一个32位处理器上的，那么处理器最希望分配出来的内存地址是以4字节为边界对齐的，这样的话具有更高的处理速度。处理器的这种希望是借助编译器来实现了。在某些处理器上，如果内存管理模块返回的内存地址并不能真正满足字节对齐的要求，那么最终会导致程序崩溃。总而言之，内存管理模块需要考虑所分配出内存地址的对齐问题。那你可能会问，在设计内存管理模块时，到底应当以多少字节为边界对齐呢？这是我要说的第二点。
内存管理模块应当考虑的第二点是模块的灵活性或说是适应性，即能满足将来的或是特定系统的需要，从而适应更大的变化。比如，就分配出的内存应当以几个字节为边界对齐这一问题，就是一个考察内存管理模块灵活性的一个好问题。以4字节还是8字节，或是16字节为边界对齐呢？可能，针对不同的处理器，其所需字节对齐数并不相同，如果将字节对齐数当做是模块初始化时的一个参数，那么，就没有这方面的烦恼了。当然，在一定程度上会带来模块实现的复杂度，这也没有办法，要提高一个软件的适应能力，只能在设计方面做更多的考虑。采用字节对齐数参数化的方法，如果内存管理模块被运用到字节对齐数要求不同的新处理器上，并不需要对设计进行更改，而只需要使用不同的初始化参数就行了。
最后，模块的一致性也是我们需要考虑的，它包括函数命名的一致性、概念的一到致性等等。比如，如果我们取了一个名为mem_alloc ()的函数，我想大多数人可能会想：内存释放函数可能会是mem_free ()。一个好的接口命名往往与用户的猜想会是一致的，而不是打破用户的猜想！好的设计应当使得用户能很流畅的使用我们所设计的模块，而不是处处让用户觉得，此时应当这样，那时却应当那样，觉得别扭。软件模块的设计，其实是将抽象的功能，通过设计将其精化或进行更高层次的抽象，使其能被用户更加容易理解和使用。理想情况下，我们的设计要达到一旦用户理解了，就能很容易的记住和运用这他的理解。
1.2源程序目录结构
图 1.1示列了源程序的目录结构，程序的编译环境采用的是《驾驭Makefile》中的huge项目，你可以参照《驾驭Makefile》一文以了解如何设计一个实用的软件编译环境。
2 █
█ 3
mblockv1
mblockv2mblockv3mpool 算法的实现代码
存放mblock 算法第一版本的例子程序代码
存放算法的第三版本存放mblock 算法第二版本的例子程序代码
存放mblock 子程序代码
mpool
图 1.1
1.3 mblock 非固定大小内存分配算法
在这个章节，我们将看一看非固定大小内存分配算法的实现是怎样的，通过这同一算法的不同版本，你将会看出设计一个好的内存管理模块需要考虑些什么。在开始讲解它时，你可能会问一个问题：我都没有嵌入式开发环境，如何去实践呢？这是一个好问题！在此，我也不打算叫你去买一块开发板来作为你的开发环境，你不是有个人计算机吗？内存管理模块所需要的就是有一块内存让它去“管”，至于这块内存是来自于你的个人计算机，还是来自于真实的嵌入式环境，这无关紧要。那我们如何从个人计算机中得到一块让我们的内存管理模块去“管”的内存呢？采用C 库中的malloc ()从堆中分配一块内存就行了。实践的环境问题解决了，那我们就可以开始了。Here we go!
1.3.1 基本原理与实现
这里将要讲到的非固定大小内存管理算法，我给它取名为mblock 算法，你可以将mblock 理解成一个内存管理模块，也可以将其理解成一个项目。在实现这一内存管理算法时，我们并不是一步到位的，而是通过三个不同的版本使得内存管理模块更加的实用，当然也更加的复杂。三个版本分别称之为mblockv1、mblockv2和mblockv3，每一个高版本都是在前一版本的基础上做修改，从而实现更多的实用功能。
现在让我们考虑一下，从用户的角度来看，一个内存管理模块应当是什么样的。显然，“什么样
4 █
的”是通过函数来体现的，下面是对于内存管理模块函的数接口方面的一些考虑：
●在使用模块之前，需要调用模块初始化函数对其做初始化。初始化的过程，就是用户告诉
模块，字节对齐数是多少，内存的起始地址是什么。
●具有分配和释放内存的函数。这好象是费话！
●具有查看内存管理信息的函数，这样我们能“窥视”模块的行为，以便对模块进行出错诊断
或是调试。
●当模块出现错误时，能将错误通过函数的返回值告诉用户。
有了上面的考虑，定义mblock模块的接口函数就很直接了，它们分别是：
●mem_init ()，通过这一函数我们可以指定被管理内存的起始地址是什么，以及被分配出
来的内存的地址应当满足多少字节的对齐。
●当用户需要获取一块内存时，mem_alloc ()可以被调用以获得所期望大小的内存。
●mem_free ()，我想这个函数的功能不用做进一步的解释，它是mem_alloc ()的反操
作。
●mem_dump ()则用于显示内存管理信息，这些信息有利于我们掌握现在内存模块中的状态
是怎样的。另外，通过这些信息，我们可以大致的看一看模块的行为是否是正常的。
当函数出错时，我们希望它返回一个错误值。这一点对于mem_alloc ()函数有点特殊，因为这个函数被定义成返回指针。当返回指针为空时，表示出现了错误，至于具体的错误在mblockv1中我们先不管它，在mblockv3中你将看到这一问题很容易的得到了解决。
mblock模块的实现代码包括三部分：出错码定义文件errmem.h，头文件mblock.h以及代码实现文件mblock.c。errmem.h头文件中定义了内存管理模块将要使用到的所有错误代码，对于错误码的管理，请参见《错误管理》一文。mblock模块最后将被编译成libmblock.a库以被使用，由于存在三个不同的mblock实现，所以生成的库的文件名中也会加入相应的版本信息，比如mblockv1.a是这里将要讨论的实现的最终库文件名，后面我们将不具体的说明用的是mblockv1.a或是mblockv2.a，而是全部采用mblock.a进行总称，这一点相信读者很容易根据上下文以及源码明白到底是哪一个版本。
我学习一个新的软件包时有一个习惯，喜欢先尝试运行程序并观察其运行结果，然后再回过头来看代码以了解其具体的实现。有时为了更加透彻的理解，还通过修改代码并运行它来验证自己的理解。在此，也让我们先看一看mblock是如何被使用的吧，这我们需要先写一个示例程序，其代码如图 1.2所示。
os/source/samples/memory/mblockv1/main.c
00025: #include “mblock.h”
00026: #include
00027: #include
00028:
00029: #define SYSTEM_MEM_SIZE 8*1024*1024
00030: #define SYSTEM_ALIGNMENT_BITS 3
00031:
00032: int main ()
00033: {
00034: void *p_mem_alloc1, *p_mem_alloc2, *p_mem_alloc3;
00035:
00036: // allocate memory from the heap
00037: void* p_system_mem = malloc(SYSTEM_MEM_SIZE);
00038:
00039: if (0 != mem_init ((maddr_t)p_system_mem,
█ 5
00040: (maddr_t )((char *)p_system_mem + SYSTEM_MEM_SIZE ), SYSTEM_ALIGNMENT_BITS )) {
00041: printf (“mem_init () is failed!\n”); 00042: goto error ;
00043: }
00044: 00045: printf (“\n”);
00046: printf (“=========\n”);
00047: printf (“Before Test ->\n”); 00048: printf (“=========\n”); 00049: mem_dump ();
00050: 00051: printf (“======================\n”);
00052: printf (“Test Case 1): allocate 1 byte ->\n”); 00053: printf (“======================\n”); 00054: p_mem_alloc1 = mem_alloc (1);
00055: printf (“ Allocated Addr: %p\n”, p_mem_alloc1); 00056: mem_dump ();
00057: 00058: printf (“=========================\n”);
00059: printf (“Test Case 2): allocate 32K bytes ->\n”); 00060: printf (“=========================\n”); 00061: p_mem_alloc2 = mem_alloc (32*1024);
00062: printf (“ Allocated Addr: %p\n”, p_mem_alloc2); 00063: mem_dump ();
00064: 00065: printf (“=========================\n”);
00066: printf (“Test Case 3): allocate 64K bytes ->\n”); 00067: printf (“=========================\n”); 00068: p_mem_alloc3 = mem_alloc (64*1024);
00069: printf (“ Allocated Addr: %p\n”, p_mem_alloc3); 00070: mem_dump ();
00071: 00072: printf (“======================\n”);
00073: printf (“Test Case 4): free 32K bytes ->\n”); 00074: printf (“======================\n”);
00075: if (0 != mem_free (p_mem_alloc2, 32*1024)) { 00076: printf (“mem_free () is failed!\n”); 00077: }
00078: printf (“ Freed Addr: %p\n”, p_mem_alloc2); 00079: mem_dump ();
00080: 00081: printf (“==============================\n”);
00082: printf (“Test Case 5): allocate 64K bytes again ->\n”); 00083: printf (“==============================\n”); 00084: p_mem_alloc2 = mem_alloc (64*1024);
00085:
printf (“ Allocated Addr: %p\n”, p_mem_alloc2);
6 █
00086: mem_dump ();
00087:
00088: printf(“===================\n”);
00089: printf(“Test Case 6): free 1 byte ->\n”);
00090: printf(“===================\n”);
00091: if (0 != mem_free (p_mem_alloc1, 1)) {
00092: printf(“mem_free () is failed!\n”);
00093: }
00094: printf(“ Freed Addr: %p\n”, p_mem_alloc1);
00095: mem_dump ();
00096:
00097: printf(“======================\n”);
00098: printf(“Test Case 7): free 64K bytes ->\n”);
00099: printf(“======================\n”);
00100: if (0 != mem_free (p_mem_alloc2, 64*1024)) {
00101: printf(“mem_free () is failed!\n”);
00102: }
00103: printf(“ Freed Addr: %p\n”, p_mem_alloc2);
00104: mem_dump ();
00105:
00106: printf(“======================\n”);
00107: printf(“Test Case 8): free 64K bytes ->\n”);
00108: printf(“======================\n”);
00109: if (0 != mem_free (p_mem_alloc3, 64*1024)) {
00110: printf(“mem_free () is failed!\n”);
00111: }
00112: printf(“ Freed Addr: %p\n”, p_mem_alloc3);
00113: mem_dump ();
00114:
00115: free(p_system_mem);
00116: return 0;
00117: error:
00118: free(p_system_mem);
00119: return -1;
00120: }
图 1.2
图 1.3列出了例子程序的最终运行结果，接下来，我们需要对照这一运行结果来看一看mblock 模块的实现原理。
https://www.doczj.com/doc/e317122626.html,/os
$cd build
https://www.doczj.com/doc/e317122626.html,/os/build
$make
https://www.doczj.com/doc/e317122626.html,/os/build/exes
$./exes/mblockv1.exe
===========
█ 7
Before Test -> ===========
Free Block(s) -------------
Block Start Addr: b770c008, size: 800000 (8388608)
Summary -------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608) Used: 0 (0)
Free: 800000 (8388608)
============================= Test Case 1): allocate 1 byte -> ============================= Allocated Addr: 0xb770c008
Free Block(s) -------------
Block Start Addr: b770c010, size: 7ffff8 (8388600)
Summary -------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608) Used: 8 (8)
Free: 7ffff8 (8388600)
================================ Test Case 2): allocate 32K bytes -> ================================ Allocated Addr: 0xb770c010
Free Block(s) -------------
Block Start Addr: b7714010, size: 7f7ff8 (8355832)
Summary -------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608) Used: 8008 (32776)
8 █
Free: 7f7ff8 (8355832)
================================
Test Case 3): allocate 64K bytes ->
================================
Allocated Addr: 0xb7714010
Free Block(s)
-------------
Block Start Addr: b7724010, size: 7e7ff8 (8290296)
Summary
-------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608)
Used: 18008 (98312)
Free: 7e7ff8 (8290296)
============================
Test Case 4): free 32K bytes ->
============================
Freed Addr: 0xb770c010
Free Block(s)
-------------
Block Start Addr: b770c010, size: 8000 (32768)
Block Start Addr: b7724010, size: 7e7ff8 (8290296) Summary
-------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608)
Used: 10008 (65544)
Free: 7efff8 (8323064)
======================================
Test Case 5): allocate 64K bytes again ->
======================================
Allocated Addr: 0xb7724010
Free Block(s)
-------------
Block Start Addr: b770c010, size: 8000 (32768)
Block Start Addr: b7734010, size: 7d7ff8 (8224760)
█ 9 Summary
-------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608)
Used: 20008 (131080)
Free: 7dfff8 (8257528)
=========================
Test Case 6): free 1 byte ->
=========================
Freed Addr: 0xb770c008
Free Block(s)
-------------
Block Start Addr: b770c008, size: 8008 (32776)
Block Start Addr: b7734010, size: 7d7ff8 (8224760)
Summary
-------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608)
Used: 20000 (131072)
Free: 7e0000 (8257536)
============================
Test Case 7): free 64K bytes ->
============================
Freed Addr: 0xb7724010
Free Block(s)
-------------
Block Start Addr: b770c008, size: 8008 (32776)
Block Start Addr: b7724010, size: 7e7ff8 (8290296)
Summary
-------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608)
Used: 10000 (65536)
Free: 7f0000 (8323072)
============================
Test Case 8): free 64K bytes ->
============================
10 █
Freed Addr: 0xb7714010
Free Block(s)
-------------
Block Start Addr: b770c008, size: 800000 (8388608)
Summary
-------
Alignment: 8
Heap Addr: b770c008
Total: 800000 (8388608)
Used: 0 (0)
Free: 800000 (8388608)
图 1.3
1.3.1.1竞争问题
竞争问题有时也称之为多任务、多线程或代码重入（re-entrance）问题，是指公共的数据结构被多个任务同时访问而造成的数据完整性问题。通常情况下，一个嵌入式系统的功能是由多个任务协同完成的。如果要将mblock设计成一个真正实用的模块，毫无疑问，mblock模块应当考虑多任务问题。mblock模块中的mem_lock_init ()、mem_lock ()和mem_unlock ()三个函数的存在，就是为了解决竞争问题的。由于我并不打算演示多任务环境下mblock的竞争问题，所以你所看到的是，在mblock模块的实现中，这三个函数的实现是空的。这并不意味着mblock在设计上不支持多任务，相反，mblock在实现上只要需要考虑竞争问题的地方，都调用了mem_lock ()和mem_unlock ()以防止竞争问题的出现。如果你打算将mblock运用到你的嵌入式系统当中，那么你一定需要实现这三个函数。对于这三个函数的实现，你可以使用一个mutex，或者使用开、关中断的方式。采用开、关中断方式的前提是：中断的开、关并不会对系统中其它对中断响应要求很高的外部设备产生影响。顺便提及的是，在很多处理器上，mutex的实现就是最终采用开、关中断的方式。
1.3.1.2模块的初始化
mblock模块的初始化是通过调用mem_init ()来实现的，图 1.4中列出了mblock中与mem_init ()相关的实现，以及例子程序main.c中所对应的初始化部分代码。
os/source/common/inc/primitive.h
00029: typedef unsigned int uint32_t;
00030: typedef signed int int32_t;
00031: typedef unsigned short uint16_t;
00032: typedef signed short int16_t;
00033: typedef unsigned char ubyte_t;
00034: typedef signed char byte_t;
00035:
00036: typedef uint32_t maddr_t;
00037: typedef uint32_t msize_t;
00038: typedef uint32_t size_t;
00039:
00040: typedef enum {
00041: false,
█ 11
00042: true 00043: } bool ; 00044:
00045: #define UNUSED (a ) (void )a os/source/common/inc/alignment.h
00031: #define ROUND_UP (_addr , _alignment )
(((_addr ) + (_alignment - 1)) & ~(_alignment - 1))
00032: #define ROUND_DOWN (_addr , _alignment ) ((_addr ) & ~(_alignment - 1)) 00033: #define IS_ALIGNED (_addr , _alignment )
(((_addr ) & (_alignment - 1)) == 0)
00034:
00035: #define ALIGN (_addr , _alignment ) \
00036: (((_addr ) + ((_alignment ) - 1)) & ~((_alignment ) - 1)) os/source/memory/mblockv1/inc/mblock.h 00029: #include "error.h"
00030: #include "primitive.h" 00031:
00032: typedef struct 00033: {
00034: maddr_t next_; // next start address of memory block
00035: msize_t size_; // length of this block in g_alignment_bytes unit 00036: } mblock_t ;
os/source/memory/mblockv1/src/mblock.c
00072: error_t mem_init (maddr_t _addr_start , maddr_t _addr_end ,
msize_t _alignment_in_bits )
00073: {
00074: mblock_t* p_mblock ; 00075:
00076: if (g_initialized) {
00077: // has been initialized, return 0 to indicate success 00078: return 0; 00079: } 00080:
00081: if (_addr_start > _addr_end ) {
00082: return ERROR_T (ERROR_MBLOCK_INIT_INVADDR ); 00083: } 00084:
00085: g_alignment_in_bits = _alignment_in_bits ;
00086: g_alignment_bytes = (1 << g_alignment_in_bits); 00087:
00088: if (sizeof (int ) > g_alignment_bytes) {
00089: return ERROR_T (ERROR_MBLOCK_INVALIGN ); 00090: } 00091:
00092: // initialize the g_mblock_free, it holds first free block
from which can
00093: // be allocated
12 █
00094: g_mblock_free.next_ = ALIGN (_addr_start, g_alignment_bytes); 00095: // the length is in g_alignment_bytes unit
00096: g_mblock_free.size_ = (_addr_end - g_mblock_free.next_) >> g_alignment_in_bits;
00097:
00098: // initialize the free block and its size
00099: p_mblock = (mblock_t *)g_mblock_free.next_;
00100: p_mblock->next_ = 0;
00101: p_mblock->size_ = g_mblock_free.size_;
00102:
00103: // save the start and end address for later use
00104: g_heap_addr_start = g_mblock_free.next_;
00105: g_heap_addr_end = g_mblock_free.next_ +
00106: (g_mblock_free.size_ << g_alignment_in_bits);
00107: g_heap_size = g_mblock_free.size_;
00108: // minimal allocation size should be bigger than the size of mblock_t
00109: g_min_alloc_size = (sizeof (mblock_t) + g_alignment_bytes - 1) 00110: >> g_alignment_in_bits;
00111:
00112: mem_lock_init ();
00113:
00114: g_initialized = true;
00115:
00116: return 0;
00117: }
os/source/samples/memory/mblockv1/main.c
00029: #define SYSTEM_MEM_SIZE 8*1024*1024
00030: #define SYSTEM_ALIGNMENT_BITS 3
00031:
00032: int main ()
00033: {
00034: void *p_mem_alloc1, *p_mem_alloc2, *p_mem_alloc3;
00035:
00036: // allocate memory from the heap
00037: void* p_system_mem = malloc(SYSTEM_MEM_SIZE);
00038:
00039: if (0 != mem_init ((maddr_t)p_system_mem,
00040: (maddr_t)((char *)p_system_mem + SYSTEM_MEM_SIZE),
SYSTEM_ALIGNMENT_BITS)) {
00041: printf(“mem_init () is failed!\n”);
00042: goto error;
00043: }
00044:
00045: printf(“\n”);
00046: printf(“=========\n”);
00047: printf(“Before Test ->\n”);
00048: printf(“=========\n”);
00049: mem_dump ();
图 1.4
先让我们看一看mblock.c中mem_init ()的实现。从参数来看它需要三个，它们是被管理内存的起始和终止地址，以及分配出来的内存所期望的字节对齐数。对于字节对齐数，采用的是2的几次方来表示。比如，如果你希望以4字节为边界来分配内存，则_alignment_shift应当被斌值为2。类似地，如果希望分配出来的内存是以8字节为边界对齐的，则_alignment_shift 应当斌值为3。
76~79行是为了检查mblock模块是否已经初始化过了，以避免重复初始化而导致问题。81~83行则检查用户所输入的内存地址是否是合理的，显然，我们不希望内存块的结束地址比开始地址还要小。85和86则是分别对g_alignment_shift和g_alignment_bytes两个全局变量进行初始化，这两个变量在其它函数中需要被使用到，其用途不言自名，是用于处理字节对齐的。88~90是检查用户所输入的字节对齐要求是否合理，我们不希望用户所给出的对齐字节数小于int类型所占用内存的大小。比如，在一个32位处理器上，int类型的大小通常是4个字节，我们不希望用户希望mblock在内存分配时，要求以2字节为边界对齐，至少也得是4字节。94~96行则是初始化g_mblock_free全局变量，这个全局变量的类型是mblock_t，其定义可以从mblock.h的32~36行找到。结构中的next_是用于指示下一个空闲内存块的位置是在哪，而size_则用于指示当前内存块的大小是多少。需要注意的是size_的大小是以g_alignment_bytes为单位的。也就是说，如果字节对齐数期望是8字节，则size_的大小是以8字节为单位的。也就是说，最小的分配单位其实就是字节对齐数。对g_mblock_free全局变量初始化时，我们需要让next_以g_alignment_bytes所指示的大小作为边界对齐数，而size_则是以g_alignment_bytes为单位。从实现中，你可以看到字节对齐是采用ALIGN宏来做到的，这一宏被定义在alignment.h 的35行。mblock.c中的99~101行是为了初始化第一块空闲内存块所对应的mblock_t数据结构的，为了更好的理解其与g_mblock_free初始化操作的区别，你需要参照图 1.5。接着在104~107行，对其它的几个全局变量进行了初始化，这些全局变量的作用我想通过其名字你就能知道。109行对g_min_alloc_size变量进行初始化，这一变量用于记录最小的内存分配大小是多少，其单位也是g_alignment_bytes。从实现中你可以看出，最小分配单位是要保证能放下一个mblock_t数据结构，这是因为当这被分配出去的内存需要释放时，我们需要在释放的内存中存放一个mblock_t结构，以将其链入空闲内存块链g_mblock_free中。通过参照图 1.5有助于理解最小分配内存这一限制。在112行则调用mem_lock_int ()以对mblock模块所需用到的互斥锁进行初始化，如果采用的是开关中断的方式，则mem_lock_init ()函数的实现可以是空的。最后，将g_initialized设置为true，以表示这一模块已经被初始化过了。
接下来看一看例子程序中是如何调用mem_init ()的，这可以从main.c的39行看出。在之前，我们采用malloc ()函数从运行程序的真实操作系统的堆中分配出8兆字节内存，以准备将这块内存交给mblock模块进行管理。在真正的嵌入式系统中，读者可能需要通过与连接脚本相配合来指定交给mblock模块管理的内存的地址空间。另外，在这个例子程序中，我们希望mblock 模块是以8字节为边界进行内存分配的。在main.c的49行，当完成了对mblock模块进行初始化后，第一次调用mem_dump ()将mblock模块的管理信息打印出来，例子程序的输出信息可以从图 1.3获得。
图 1.5是例子程序在完成mblock模块初始化后的内存布局图示，需要提醒注意的是，其中每一个mblock_t数据结构中size_的大小是以字节为单位的，而不是以g_alignment_bytes为单位的。之所以存在这种不一致性，是因为mem_dump ()所输出的结果更多的考虑用户（可能就是读者你）阅读时的方便。
从图中可以看出，g_mblock_free其实就是空闲内存块链的链表头，后面指紧跟的是第一个
█ 13
14 █
可以使用的内存块中的mblock_t 结构。在mem_init ()函数中的p_mblock 局部变量指向的就一第一块空闲内存块。这里有一点很巧妙，mblock_t 结构是分配在空闲内存块的头部的，并在这一结构中保存其所在空闲内存块的大小以及下一个可用空闲块的开始地址。从图 1.5可以看到，由于在初始化时，只有一块大的空闲内存块，所以p_mblock 变量所指向的mblock_t 结构中的next_值为0，表示后面没有其它的可用空闲内存块了。尽管g_mblock_free 与p_mblock 都是mblock_t 类型，且初始化时其size_成员变量的值也相同，但size_成员变量的意思却完全不相同。在g_mblock_free 中的size_变量中存放的是mblock 所管理的内存总体上还有多少是空闲的，而p_mblock 中的size_变量指示的是其所在的空闲块的大小是多少。
0xb770c008
8M 字节
(0x800000)
g_mblock_free
图 1.5
1.3.1.3 内存的分配
现在，让我们查看一下mblock 模块中的mem_alloc ()是如何实现的，其对应的实现和例子代码如图 1.6所示。
os/source/memory/mblockv1/src/mblock.c 00119: void* mem_alloc (msize_t _size ) 00120: {
00121: mblock_t *p_pre , *p_next , *p_superfluous ; 00122: msize_t size_required , size_superfluous ; 00123:
00124: if (!g_initialized) {
00125: // oops! the heap isn't being initialized 00126: return 0; 00127: } 00128:
00129: if (0 == _size ) {
00130: // hey, man! never ask the size of 0 00131: return 0; 00132: } 00133:
█ 15 00134: // convert the _size into g_alignment_bytes unit
00135: size_required = ((_size + g_alignment_bytes - 1)
>> g_alignment_in_bits);
00136: if (g_min_alloc_size > size_required) {
00137: size_required = g_min_alloc_size;
00138: }
00139:
00140: mem_lock ();
00141:
00142: // check whether have enough memory for this allocation
request to fast failure
00143: if (g_mblock_free.size_ < size_required) {
00144: mem_unlock ();
00145: return 0;
00146: }
00147:
00148: p_pre = p_next = &g_mblock_free;
00149: for (;;)
00150: {
00151: p_next = (mblock_t *)p_next->next_;
00152: if (0 == p_next) {
00153: // till now we have traversed all the block and didn't
find a block
00154: // for this request
00155: mem_unlock ();
00156: return 0;
00157: }
00158:
00159: // if this block size cannot meet the request, continue
next block
00160: if (p_next->size_ < size_required) {
00161: p_pre = p_next;
00162: continue;
00163: }
00164:
00165: // block size is bigger or equal to size_required,
get the remaining
00166: // free size
00167: size_superfluous = p_next->size_ - size_required;
00168: if (size_superfluous <= g_min_alloc_size) {
00169: size_required = p_next->size_;
00170: p_superfluous = (mblock_t *)p_next->next_;
00171: break;
00172: }
00173:
00174: // put the superfluous block into the free list
00175: p_superfluous = (mblock_t *)((maddr_t)p_next +
16 █
(size_required << g_alignment_in_bits)); 00176: p_superfluous ->next_ = p_next ->next_; 00177: p_superfluous ->size_ = size_superfluous ; 00178: break ;
00179: } 00180:
00181: p_pre ->next_ = (maddr_t )p_superfluous ; 00182: g_mblock_free .size_ -= size_required ; 00183:
00184: mem_unlock (); 00185:
00186: return p_next ; 00187: }
os/source/samples/memory/mblockv1/main.c
00051: printf (“======================\n”);
00052: printf (“Test Case 1): allocate 1 byte ->\n”); 00053: printf (“======================\n”); 00054: p_mem_alloc1 = mem_alloc (1);
00055: printf (“ Allocated Addr: %p\n”, p_mem_alloc1); 00056: mem_dump (); 00057:
00058: printf (“=========================\n”);
00059: printf (“Test Case 2): allocate 32K bytes ->\n”); 00060: printf (“=========================\n”); 00061: p_mem_alloc2 = mem_alloc (32*1024);
00062: printf (“ Allocated Addr: %p\n”, p_mem_alloc2); 00063: mem_dump (); 00064:
00065: printf (“=========================\n”);
00066: printf (“Test Case 3): allocate 64K bytes ->\n”); 00067: printf (“=========================\n”); 00068: p_mem_alloc3 = mem_alloc (64*1024);
00069: printf (“ Allocated Addr: %p\n”, p_mem_alloc3); 00070: mem_dump ();
图 1.6
129~132是对输入参数做合法性检查，135行则将用户所需的内存大小转换为以g_alignment_bytes 为单位。对于这一转换，你一定发现了它会造成一部分内存的浪费。对于这一点，我们也只能这样，毕竟，要做到一定的字节对齐以提高性能，必须有所牺牲，这是一个空间换时间的问题。在140行，mem_alloc ()调用mem_lock ()以达到对内存管理数据结构的互斥访问，以防止出现竞争问题。在前面，我们提到了g_mblock_free 中的size_表示的是mblock 所管理的总的空闲内存数量，在143~146行，mem_alloc ()检查用户所请求的内存数量是否大于总的空闲内存数量，当发现没有足够的内存可被分配时，调用mem_unlock ()解锁并返回NULL 指针（即数值0）。在148~178行，mem_alloc ()遍历所有的空闲内存块，以便找到一个比用户所需数量大的块。mem_alloc ()采用的内存分配算法是，只要一找到一块空闲内存块的大小大于或等于用户所需的，则从其中为用户分配。152~157行是处理遍历到达了内存块链的末尾，这说明没有办法为用户分配内存，此时也得返回NULL 。你可能会问，前面不是检查过了，在
█ 17
g_mblock_free 中的size_变量已经表明，mblock 所管理的空闲内存大小比用户所需的大，为什么在还有可能不能为用户分配内存呢？是的，出现这种情况是因为，系统中存在大量的内存碎片，虽然所有碎片的总和大于用户所需数量，但每一个内存碎片都小于用户所需的数量。160~163行是检查当前正在遍历的空闲块的大小是否是小于用户所需的数量，如果是，则遍历下一个内存块。如果程序运行到167行，说明当前正在遍历的内存块的大小大于或等于用户所需的数量。168~172就是用于处理所找到的块的大小刚刚好满足用户需求这一情况。这里的刚好并不是严格意义上的刚好，当多余的内存比g_min_alloc_size 小时，我们也让为是刚好。试想想，当多余出来的内存小于g_min_alloc_size 时，此时并不能在其中分配出一个mblock_t 结构，即无法将其放入g_mblock_free 链表中，那到干脆将这一多余的内存一并分配给用户。在这种情况下，我们只是让p_superfluous 指向当前块的下一块，在函数的最后，会将p_superfluous 所指向的块重新链入到空闲内存块链中。175~178则是处理当前遍历的内存块大于用户所需数量这种情形，在这种情况下，我们需要从内存块的前部分中“切”一块出来，并将p_superfluous 指向内存块中多余的部分。181则是将p_superfluous 链入到内存块链中，而182则从g_mblock_free 的size_中减去分配出去的内存大小。作为结束，mem_alloc ()在返回内存给调用者之前调用mem_unlock ()解锁，这你在184行能看到，然后，返回p_next 所指向的内存地址，这一地址所指向的内存块就是属于被调用者的了。同样地，从图 1.3中你可以找到例子程序中运行测试用例1至3的结果。 例子程序在运行过了测试用例1至3后，内存布局如图 1.7所示。由于每一次分配都可以从第一块（也是唯一的一块）空闲内存块中分配到内存，所以图 1.7中的内存布局看过去非常的“清爽”。在进行多次内存分配和释放后，内存布局就会显得复杂，这在后面你将看到。
1.3.1.4 内存的释放与合并
测试用例4是第一次尝试释放一块内存，mblock 模块中的内存释放函数mem_free ()的实现如图 1.8所示。当一块内存被释放时，需要考虑将被释放内存块与其刚好相邻的前后空闲块进行合并，以减少内存碎片。
图 1.7
os/source/memory/mblockv1/src/mblock.c
00189: error_t mem_free (void* _p_buf , msize_t _size ) 00190: {
00191: maddr_t p_buf = (maddr_t )_p_buf ;
18 █
00192: mblock_t* p_pre,*p_next;
00193: msize_t size;
00194:
00195: if (!g_initialized) {
00196: // oops! the heap isn't being initialized
00197: return ERROR_T (ERROR_MBLOCK_NOTINIT);
00198: }
00199:
00200: if (_size == 0) {
00201: return ERROR_T (ERROR_MBLOCK_FREE_INVSIZE);
00202: }
00203:
00204: if (0 == p_buf || ((p_buf & (g_alignment_bytes - 1)) != 0) || 00205: p_buf < g_heap_addr_start ||
00206: p_buf > g_heap_addr_end || size > g_heap_size) {
00207: return ERROR_T (ERROR_MBLOCK_FREE_INVBUF);
00208: }
00209:
00210: size = ((_size + g_alignment_bytes - 1) >> g_alignment_in_bits); 00211: if (g_min_alloc_size > size) {
00212: size = g_min_alloc_size;
00213: }
00214:
00215: mem_lock ();
00216: g_mblock_free.size_ += size;
00217:
00218: if (0 == g_mblock_free.next_) {
00219: g_mblock_free.next_ = p_buf ;
00220: p_next = (mblock_t *)p_buf ;
00221: p_next->size_ = size;
00222: p_next->next_ = 0;
00223: mem_unlock ();
00224: return 0;
00225: }
00226: else {
00227: p_pre = &g_mblock_free;
00228: p_next = (mblock_t *)g_mblock_free.next_;
00229: }
00230:
00231: // find the right position of the list
00232: while (p_pre->next_ < p_buf ) {
00233: p_pre = p_next;
00234: p_next = (mblock_t *)p_next->next_;
00235: if (0 == p_next) {
00236: break;
00237: }
00238: }
█ 19 00239:
00240: // merge with the previously adjacent block if needed
00241: if ((((p_pre->size_ << g_alignment_in_bits) + (maddr_t)p_pre) 00242: == p_buf ) && (p_pre != &g_mblock_free)) {
00243: p_pre->size_ += size;
00244: }
00245: else {
00246: p_pre->next_ = p_buf ;
00247: p_pre = (mblock_t *)p_buf;
00248: p_pre->size_ = size;
00249: p_pre->next_ = (maddr_t)p_next;
00250: }
00251:
00252: if (p_next == 0) {
00253: // this is the last block no more mergence is needed 00254: mem_unlock ();
00255: return 0;
00256: }
00257:
00258: // merge with the following adjacent block if needed
00259: if (((p_pre->size_ << g_alignment_in_bits) + (maddr_t)p_pre) == (maddr_t)p_next) {
00260: p_pre->size_ += p_next->size_;
00261: p_pre->next_ = p_next->next_;
00262: }
00263:
00264: mem_unlock ();
00265: return 0;
00266: }
os/source/samples/memory/mblockv1/main.c
00072: printf(“======================\n”);
00073: printf(“Test Case 4): free 32K bytes ->\n”);
00074: printf(“======================\n”);
00075: if (0 != mem_free (p_mem_alloc2, 32*1024)) {
00076: printf(“mem_free () is failed!\n”);
00077: }
00078: printf(“ Freed Addr: %p\n”, p_mem_alloc2);
00079: mem_dump ();
图 1.8
200~208行是检查用户所提供的参数是否是有效的，如果不，相应的错误代码将被返回。与mem_alloc ()相类似的是，在210行将_size转换成以g_alignment_bytes为单位。在215行，由于mem_free ()需要访问全局变量，以及对内存块链进行操作，所以需要调用mem_lock ()上锁以防止出现竞争问题。216行则更新所存在的空闲内存的数量。218~225是处理所释放的内存块是空闲链中的唯一一块内存块的情形。232~238行是从内存块链中找到所释放的内存块应当放在空闲链中的什么位置。可以想象，空闲内存块链中的节点是以空闲块的开始地址由低到高进行排序的。241~244行是处理当被释放的内存块与前一个空闲内存块是相连的，相连的判断条件是前一空
20 █
闲块的开始地址加上其大小刚好与用户释放的内存块的地址是相同的。注意由于大小是以g_alignment_bytes 为单位的，而用户所给的地址是以字节为单位的，因此需要做一定的转换再比较。如果与前一空闲块是相连的，只需将被释放内存块的大小加入到前一空闲块的size_变量中就行了，而不需做链表的插入操作。245~250行则是处理所需释放的内存块与前一内存块地址并不相连这种情形。对于这种情形，需要将被释放的内存块通过其头部的mblock_t 结构将其插入到空闲块链表中。252~256行是处理被释放的内存块刚好是整个空闲内存块链中的最后一个这一情形，此时，因为是最后一块，所以并不需要考虑与后面相邻的内存块进行合并这一问题。当然mem_free ()在返回之前应当调用mem_unlock ()进行解锁操作。259~262行则是处理需要与后面相邻的内存块进行合并这一情形，其方式与处理与前一相邻内存块的合并是一样的。在mem_free ()的最后，则是解锁并返回0表示内存释放操作成功了。图 1.9是例子程序运行了测试用例4后的内存布局。
从mem_free ()的实现可以看出，内存的合并只是在相应空闲内存块的size_上加上被用户释放的内存就行了，其原理还是很简单且高效的。
测试用例5则是在前面释放了32K 字节的情形下，再向mblock 模块请求分配64K 字节的内存。此时，从图 1.9可以看出第一块空闲内存块的大小是32K （0x8000），所以只能从第二块空闲内存块中分配。例子程序运行完测试用例5后的内存布局如图 1.10所示。
接下来，例子程序中从测试用例6开始是释放所有从mblock 模块中分配出来的内存，在测试用例6中，当释放了第一次分配出来的1个字节后（实际mblock 模块分配的是8字节），内存的布局如图 1.11所示。在这次释放时，完成了一次与后继内存块的合并操作，这从图 1.11中的第一块空闲块的大小从0x8000变成了0x8008可以看出。
可以想象，当例子程序运行完了测试用例7和8以后，我们将得到一个与图 1.5完全一样的内存布局。这是显然的，因为所有的内存都被释放了，与没有进过内存分配理应是一样的。
size=0x8000
空闲内存g_mblock_free
size=0x7e7ff8
图 1.9
1.3.1.5 小结
至此，你已经知道了mblock 内存管理算法是如何帮助我们去管理内存的了。作为小结，我们需要了解这一版本的内存管理模块的优缺点是什么。同过分析优缺点，有利于我们思考如何去改进它。