Nucleus PLUS的动态内存管理机制研究

，，，，

(许继电气，许昌 461000)

引　言

Nucleus为抢先式多任务操作系统，Nucleus PLUS为其系统内核，具有可移植性、易用性、可配置性等特点。Nucleus PLUS提供一系列系统服务，比如：任务控制、任务通信、任务同步、内存管理、可编程的定时器、标准的输入/输出设备接口等。

Nucleus PLUS内存管理没有使用虚拟内存技术，采用的是实存储器管理技术：对内存地址的访问不需要经过MMU，直接送到地址线上输出，程序中访问的地址都是实际的物理地址[1]。这种内存管理策略虽然降低了系统的安全性，但是内存分配快速、高效，避免了虚存系统中地址转换及非常耗时的磁盘I/O操作，是许多嵌入式设备的选择。

Nucleus PLUS提供两种内存管理方式，一种是分区内存管理(Partition Memory Pools)，另一种是动态内存管理(Dynamic Memory Pools)[2]。本文针对某版本Nucleus PLUS，详细研究了其动态内存管理机制及实现细节，介绍了其测试思路和测试用例设计，最后对Nucleus PLUS动态内存管理机制进行评价,并针对该机制存在的内存访问越界时保存在内存头的内存管理信息被破坏，进而导致动态内存管理机制系统性失效的缺点,提出了改进建议及内存越界检测方法。

1　Nucleus PLUS动态内存管理机制研究

Nucleus PLUS动态内存管理组件(DM)负责所有的动态内存管理。一个动态内存池包括用户指定数目的字节,提供了从动态内存池中分配或释放可变长度内存块的服务。内存分配采用first-fit策略(首次适配策略)。

1.1　数据结构

1.1.1内存池控制块链表

内存池通过动态内存池控制块(DM_PCB，见1.1.2节)管理。所有创建的内存池的DM_PCB通过一个双向循环链表链接起来，即内存池控制块链表。全局变量DMD_Created_Pools_List为该链表的头指针。动态内存池可以动态删除和创建，每创建一个动态内存池，其DB_PCB加入到链表尾端；每删除一个动态内存池，其在链表中对应的DB_PCB节点就会从链表中删除。内存池控制块链表如图1所示。

图1　内存池控制块链表

1.1.2内存池控制块(DM_PCB)

DM_PCB用于管理内存池，它包含了内存池的状态和控制信息，属性见表1。

表1　内存池控制块主要属性

DM_PCB的dm_suspension_list链表的每个节点为一个内存池阻塞结构，其定义见DM_SUSPEND。它主要包含如下信息：

① dm_memory_pool：内存池控制块指针，指示阻塞哪个内存池上。

② dm_suspended_task：任务控制块指针，指示哪个任务被阻塞。

③ dm_request_size：任务请求内存的大小。

1.1.3内存池内存布局

内存池的内存由内存块组成，分为空闲内存块和已分配内存块。每个内存块都有一个内存头数据结构(DM_HEADER，见1.1.4节)，用以描述该内存块的基本信息以及用于链接其它内存块的指针信息，内存头与用户数据连续存在一起。内存池内存中存在两个双向链表：①“全部内存块链表”：链接了全部内存块，包括已分配内存块和空闲内存块。②“空闲内存块链表”：只链接了空闲内存块。“全部内存块链表”的头指针保存在内存池控制块的dm_start_address中，通过DM_HEADER的dm_next_memory和dm_previous_memory指针将所有内存块双向链接起来。“空闲内存块链表”的头指针保存在内存控制块的dm_memory_list中，通过DM_HEADER的dm_next_free和dm_previous指针将空闲内存块双向链接起来。图2为内存池布局图。

图2　内存池布局图

内存池刚创建后，只有一个空闲块和一个Trailer块，随着该内存池中内存的不断申请和释放，内存池便被分割成许多内存块。

1.1.4内存头数据结构(DM_HEADER)

内存头存储了内存块基本信息以及用于链接其它内存块的指针信息。主要属性如表2所列。

表2　DM_HEADER主要属性

DM_HEADER数据类型的大小为24, 但是所占内存开销的大小(见DM_OVERHEAD)却定义16，少了8个字节。原因是：对于已分配内存块，DM_HEADER中不存储dm_next_free和dm_previous_free这两个共占8个字节的指针。对于空闲内存块，dm_next_free、dm_previous_free这个指针只是暂时存储在其可用内存中，当该内存块被分配出去时，这两个指针所在的内存也在分配范围内。

DM_HEADER中并没有定义表示内存块内存大小的数据。但是内存块内存的大小是可以推算出来的。对于某个内存块(pt指针指向该内存块)，计算方法如下：

(char)pt->dm_next_memory - (char)pt - DM_OVERHEAD。

对于Trailer内存块,只包含了一个内存头，且dm_memory_free为非空闲状态。设置Trailer内存块的作用是：充当一条屏障，防止当内存池第一块内存块和最后一块内存块均空闲时而发生的内存合并(见1.2.2内存释放)。

1.2　系统函数功能

本节主要介绍了内存池创建、内存分配、内存释放等接口函数的功能和实现细节。

1.2.1内存池创建

NU_Create_Memory_Pool函数提供内存创建功能。内存池的内存由参数start_address、pool_size决定。该块内存应事先从系统内存池(Application_Initialize的mem_pool参数)中分配。内存池的创建会建立一个属性由传入参数决定的DM_PCB，并将其加入到“内存控制块链表”中。内存池创建后，其内存的初始布局为：一个空闲内存块和一个Trailer。

1.2.2内存分配

内存分配采用first-fit策略(首次适配策略)。第一个满足需求的可用内存块被分配。如果没有可用内存满足内存分配请求，任务可能被挂起。系统提供两种内存分配接口：

图5　内存分割

① NU_Allocate_Memory，此方式分配的内存首地址不要求对齐。

② NU_Allocate_Aligned_Memory，此方式分配的内存首地址要求分配的内存首地址按参数指定的值对齐。

内存分配时，可能出现下列内存分割情况：(注：下文的“最小分配空间”记为min_alloc，大小为16)

① 尾部分割(rear split)：当内存分配后尾部剩余内存-DM_OVERHEAD≥min_alloc时，会发生尾部分割，将尾部所剩内存新建一个空闲块。

图3中，大小为100字节的空闲块中分配出去68字节后，剩余32字节。32-DM_OVERHEADE(16)=16，等于“最小分配空间”，于是进行尾部分割。

图3　尾部分割

② 头部分割(front split)：对于对齐方式分配内存，如果头部用于对齐的字节数(记为：split_size)大于0，则会发生头部分割。split_size的含义如图4所示。

图4　split_size含义

根据split_size和min_alloc的关系，又可分为两种情况：

(1) split_size≥min_alloc + DM_OVERHEAD

此时预期在头部分割出一个大小为split_size的空闲块(包含内存头)。例如：对齐方式请求分配大小(size)为96、对齐字节数(align)为48的内存。内存池的#1空闲内存首次满足分配请求，该内存块的起始地址(start_addr)为N×48，可用内存大小为128。则会按图5所示发生头部分割，且内存分配起始地址(ptr)为N×48+48。

(2) split_size < min_alloc + DM_OVERHEAD

此种情况下，会在min_alloc+ DM_OVERHEAD的基础上再次对齐，计算出新的split_size，然后再进行头部分割。

1.2.3内存池内存释放

NU_Deallocate_Memory提供内存释放功能。内存释放时，将判断与被释放内存块(记为dealloc_block)物理位置相邻的内存块是否空闲，如果空闲，则将该内存块与其进行合并。另外，内存释放后会检查该内存池的阻塞链表，如果某些任务的内存请求此时可被满足，则将它们从阻塞链表中删除，并唤醒这些任务。图6为当与dealloc_block物理位置紧邻的上一块内存和下一块内存均空闲时，发生的内存合并。

图6　内存合并

1.2.4其它

动态内存管理模块还提供其它接口函数：

NU_Create_Memory_Pool: 创建内存池。

NU_Add_Memory: 向内存池中增加内存。

NU_Reallocate_Aligned_Memory:重新分配内存。

NU_Delete_Memory_Pool:删除内存池。

因篇幅所限，这些功能不做详细介绍。

2　动态内存管理模块测试

2.1　测试思路

进行内存池创建、内存分配、内存释放、内存池删除等操作后，DM_PCB、内存池内存块的布局以及任务状态均可能发生变化，检查这些变化是否正确。

DM_PCB的变化主要指的是：可用内存大小(dm_availble)和空闲块链表(dm_memory_list)首指针的变化。

内存池内存块的布局可通过“全部内存块链表”和“空闲控制块链表”(见1.1.3)来表达。

2.2　用例设计

NU_Allocate_Aligned_Memory和NU_Deallocate_Memory两个API函数最重要、使用最频繁，由于篇幅所限，只针对这两个函数介绍其测试用例设计。

(三)2012年至今，中国特色社会主义进入了新时代，中国共产党以实现中华民族伟大复兴为引领，在知识分子中深入开展“弘扬爱国奋斗精神、建功立业新时代”活动，加强政治吸纳，以最大限度凝聚共识

2.2.1NU_Allocate_Aligned_Memory用例设计

用例划分为以下几类：

① 空闲内存块链表中，首次满足内存请求的内存块在链表中的位置：第一块、中间某块、最后一块。

② 各种分割情况。

a. 尾部分割。

b. 头部分割。又分为split_size≥min_alloc + DM_OVERHEAD的情况和split_size < min_alloc+DM_OVERHEAD的情况。

c. 头部和尾部均需分割。

d. 头部和尾部均不需分割。

③ 任务的阻塞与唤醒。

a. 阻塞原因：内存池中不存在可以满足内存分配请求的空闲内存块。

b. 唤醒原因：释放内存、删除内存池、超时、内存池增加内存。

c. 唤醒顺序：先进先出、优先级。

④ 各种异常输入。

2.2.2NU_Deallocate_Memory用例设计

① 各种合并情况(下文中的被释放的内存块记为dealloc_block; 与其物理位置相邻的前一个内存块记为prev_block; 与其物理位置相邻的后一个内存块记为next_block)：

a. prev_block：不空闲，next_block：空闲。

b. prev_block：空闲，next_block：空闲。

c. prev_block：空闲，next_block：不空闲。

d. prev_block与next_block均不空闲。

e. dealloc_block：(除trailer外)最后一个内存块; 第一个内存块：空闲。

② 任务的阻塞与唤醒。

a. 内存释放后，可满足阻塞链表中某些任务的内存请求。

b. 内存释放后，仍无法满足阻塞链表中任何一个任务的内存请求。

③ 各种异常输入。

3　Nucleus PLUS动态内存管理机制评价及改进措施

从内存碎片问题和内存越界风险两方面来评价该动态内存管理机制，针对内存越界，提出了改进和检测办法。

3.1　内存碎片问题

内存碎片是指内存池中有空闲内存块，当所有的空闲内存块均小于内存请求大小时，称之为内存碎片[3]。Nucleus PLUS提供了如下措施来应对内存碎片问题：① 内存分割时使用了“最小分配内存”。② 内存释放时，与物理位置相邻的空闲块进行合并。但由于其所采用的first-fit算法的固有缺陷，随着内存池内存的不断分配与释放，内存池支离破碎，仍可能存在内存碎片问题。

3.2　内存越界风险

内存块的管理信息直接放在内存池的内存中，不需要额外的内存用作管理，且内存的合并操作非常高效[4]。但这也正是其缺点所在：内存池中内存块的管理信息(DM_HEADER)和用户数据连续存放在一起。如果用户数据写越界，DM_HEADER的信息可能被破坏，即该内存池的内存块的链接信息或内存块的空闲标志被破坏，从而导致内存池模块功能全面失效。

3.3　改进措施

针对内存写越界可能导致的系统崩溃，建议在该动态内存管理模块增加内存越界检查机制。具体方式：在内存头增加一块“越界保护内存”[5]，用于防止内存的写越界并提供写越界检测。内存块分配时，向“越界保护内存”填充特殊字符。内存块释放时，判断“越界保护内存”的特殊字符是否被破坏，从而判断是否发生内存写越界。“越界保护内存”会带来额外的内存开销，并且只有在内存释放时才能判断出来。下节介绍不改动系统代码的情况下，从应用/测试角度可实施的内存越界检测方法。

3.4　内存越界检测方法

Nucleus动态内存模块并没有提供内存池越界检查手段。但是动态内存相关数据结构的一些信息是可以相互验证的；内存写越界发生时，内存头信息被破坏进而内存块链表被破坏。基于以上两点，如果信息不能相互验证或者内存块链表的双向循环特征被破坏，则内存写越界发生。提出以下三种检测方法：

① 从start_address_list开始遍历，遍历全部内存块链表，应能再次遍历到start__address_list节点。如果在N次(可配置)循环中，或在一段时间内(可配置)没有再次遍历到start_address_list节点，则有可能内存池访问越界发生。

② 遍历全部内存块链表。如果内存块A的下一个内存块(记为内存块B)的dm_previous_memory不为内存A，则可能内存池访问越界发生。

③ 内存池控制块的可用内存(DM_PCB的dm_available)与所有空闲块的内存大小之和，应该相同。如果不

同，则可能内存池访问越界发生。

结　语

[1] 黄斌.嵌入式操作系统的内核剖析及基于ARM的移植[D].武汉:武汉理工大学,2004.

[2] Mentor Graphics Corporation.Nucleus Kernel Guide,2016.

[3] 李志军.面向嵌入式实时系统的动态内存管理方法研究[D].重庆:重庆大学,2007.

[4] 李云.专业嵌入式软件开发[M].北京:电子工业出版社,2012.

[5] 顾胜元,杨丹,黄海伦.嵌入式实时动态内存管理机制[J].计算机工程,2009,35(20):264-266.

姬希娜(工程师)，主要从事继电保护及自动化产品的测试技术研究。