SylixOS中的动态内存分配【3】--- 内存堆操作库接口及实现原理

简介

内存堆是内存管理的一种方式，用户可以把一块固定的物理内存交给内存堆管理。在设备驱动需要反复的申请、释放内存时，为了提高内存的利用率，用户可以申请一块物理内存作为设备驱动专有的内存堆，并可以从这块内存堆里申请。

内存堆操作库中的函数才是region接口实现的核心代码，region接口是简单套用堆内存操作函数实现的。内存堆操作库中的函数只能由内核调用，源码位于libsylixos\SylixOS\kernel\core_HeapLib.c文件中。

内存堆操作核心就是把一段连续内存合理高效的拆分成段（空闲段和使用段），每个段包括段头和分配缓存两部分，分配缓存即是动态内存分配的缓存空间。再有就是在释放段时需要合理高效的进行空闲段合并。

实现源码

为了方便理解，源码中去掉了越界检查调整，堆操作锁等非核心操作。

数据结构

堆结构体：

/*********************************************************************************************************堆类型定义 (空闲链表使用 ring 结构)
*********************************************************************************************************/typedef struct {                                                        /*  堆操作                      */LW_LIST_MONO         HEAP_monoResrcList;                            /*  空闲资源表                  */PLW_LIST_RING        HEAP_pringFreeSegment;                         /*  空闲段表                    */#if (LW_CFG_SEMB_EN > 0) && (LW_CFG_MAX_EVENTS > 0)LW_OBJECT_HANDLE     HEAP_ulLock;                                   /*  使用 semaphore 作为锁       */
#endif                                                                  /*  (LW_CFG_SEMB_EN > 0) &&     *//*  (LW_CFG_MAX_EVENTS > 0)     */PVOID                HEAP_pvStartAddress;                           /*  堆内存起始地址              */size_t               HEAP_stTotalByteSize;                          /*  堆内存总大小                */ULONG                HEAP_ulSegmentCounter;                         /*  分段数量                    */size_t               HEAP_stUsedByteSize;                           /*  使用的字节数量              */size_t               HEAP_stFreeByteSize;                           /*  空闲的字节数量              */size_t               HEAP_stMaxUsedByteSize;                        /*  最大使用的字节数量          */UINT16               HEAP_usIndex;                                  /*  堆缓冲索引                  */CHAR                 HEAP_cHeapName[LW_CFG_OBJECT_NAME_SIZE];       /*  名字                        */LW_SPINLOCK_DEFINE  (HEAP_slLock);                                  /*  自旋锁                      */
} LW_CLASS_HEAP;
typedef LW_CLASS_HEAP   *PLW_CLASS_HEAP;

堆分段结构体：

/*********************************************************************************************************堆内分段类型, 注意: 由于是否使用标志和空闲队列复用free list, 所以为了使对齐内存释放时准确判断, 判断是否空闲的标志必须在分段信息的最后一个元素.
*********************************************************************************************************/
typedef struct {LW_LIST_LINE         SEGMENT_lineManage;                            /*  左右邻居指针                */LW_LIST_RING         SEGMENT_ringFreeList;                          /*  下一个空闲分段链表          */size_t               SEGMENT_stByteSize;                            /*  分段大小                    */size_t               SEGMENT_stMagic;                               /*  分段标识                    */
} LW_CLASS_SEGMENT;
typedef LW_CLASS_SEGMENT    *PLW_CLASS_SEGMENT;

基本宏定义

堆内存对齐默认值，32位系统是8字节对齐，64位系统是16字节对齐。堆内存的最小值是16字节。

#if LW_CFG_CPU_WORD_LENGHT == 32
#define LW_CFG_HEAP_ALIGNMENT                       8                   /*  默认内存对齐关系            */
#else
#define LW_CFG_HEAP_ALIGNMENT                       16                  /*  默认内存对齐关系            */
#endif
#define LW_CFG_HEAP_SEG_MIN_SIZE                    16                  /*  分段内存最小值              *//*  必须为对齐关系整数倍        */
#define __SEGMENT_BLOCK_SIZE_ALIGN  ROUND_UP(sizeof(LW_CLASS_SEGMENT), LW_CFG_HEAP_ALIGNMENT)#define __HEAP_SEGMENT_DATA_PTR(psegment)   ((UINT8 *)(psegment) + __SEGMENT_BLOCK_SIZE_ALIGN)#define LW_SEG_MAGIC_REAL               0xffffffff

/*********************************************************************************************************allocate 新分段加入空闲链中 如果新的分段是高地址, 这里必须放在链表的最后, 使它尽量不要被使用, 这样如果使用了缺页分配机制, 则尽量节约物理页面的使用量.
*********************************************************************************************************/
#define __HEAP_ADD_NEW_SEG_TO_FREELIST(psegment, pheap)    do {                         \if (_list_line_get_next(&psegment->SEGMENT_lineManage)) {                   \_List_Ring_Add_Ahead(&psegment->SEGMENT_ringFreeList,                   \&pheap->HEAP_pringFreeSegment);                    \} else {                                                                    \_List_Ring_Add_Last(&psegment->SEGMENT_ringFreeList,                    \&pheap->HEAP_pringFreeSegment);                     \}                                                                           \} while (0)

/*********************************************************************************************************分段使用标志 (当在空闲链表中时, 分段为空闲分段, 不在空闲链表中, 则为正在使用的分段)
*********************************************************************************************************/
#define __HEAP_SEGMENT_IS_USED(psegment)    (!_list_ring_get_prev(&((psegment)->SEGMENT_ringFreeList)))
/*********************************************************************************************************分段是否有效
*********************************************************************************************************/
#define __HEAP_SEGMENT_IS_REAL(psegment)    ((psegment)->SEGMENT_stMagic == LW_SEG_MAGIC_REAL)
/*********************************************************************************************************分段数据指针
*********************************************************************************************************/
#define __HEAP_SEGMENT_DATA_PTR(psegment)   ((UINT8 *)(psegment) + __SEGMENT_BLOCK_SIZE_ALIGN)
/*********************************************************************************************************通过数据指针返回分段指针
*********************************************************************************************************/
#define __HEAP_SEGMENT_SEG_PTR(pvData)      ((PLW_CLASS_SEGMENT)((UINT8 *)(pvData) - \__SEGMENT_BLOCK_SIZE_ALIGN))
/*********************************************************************************************************理论上下一个分段地址
*********************************************************************************************************/
#define __HEAP_SEGMENT_NEXT_PTR(psegment)   ((PLW_CLASS_SEGMENT)(__HEAP_SEGMENT_DATA_PTR(psegment) + \psegment->SEGMENT_stByteSize))
/*********************************************************************************************************是否可以合并分段判断
*********************************************************************************************************/
#define __HEAP_SEGMENT_CAN_MR(psegment, psegmentRight)  \(__HEAP_SEGMENT_NEXT_PTR(psegment) == psegmentRight)
#define __HEAP_SEGMENT_CAN_ML(psegment, psegmentLeft)   \(__HEAP_SEGMENT_NEXT_PTR(psegmentLeft) == psegment)

创建堆对象

创建一个堆对象，需要输入内存地址和大小。构造一个堆（_HeapCtorEx）时可以指定是否为多操作系统内存堆，多操作系统内存堆用于AMP异构多核时多系统间共享，为容易理解，这里不考虑多操作系统的使用情况。

成员HEAP_monoResrcList是当前空闲的内存堆链表，用户可遍历链表获取空闲的内存堆的结构体指针；使用完成后，用户可以把内存堆归还给成员HEAP_monoResrcList，不需要释放内存堆。成员HEAP_monoResrcList链表可以看作一个容器链表，使用时可申请容器，不需要时可归还容器。此方式可以减少内存碎片，提高内存利用率。

成员HEAP_pringFreeSegment是当前内存堆中空闲内存空间的链表，用户从内存堆中申请字节池时，会从成员HEAP_pringFreeSegment链表中获取空闲的内存空间；用户释放字节池时，会把释放的内存空间加入到成员HEAP_pringFreeSegment链表。

/*********************************************************************************************************
** 函数名称: _HeapCreate
** 功能描述: 建立一个内存堆
** 输　入  : pvStartAddress        起始内存地址
**           stByteSize            内存堆的大小
** 输　出  : 建立好的内存堆控制块
** 全局变量: 
** 调用模块: 
*********************************************************************************************************/
PLW_CLASS_HEAP  _HeapCreate (PVOID             pvStartAddress, size_t            stByteSize)
{REGISTER PLW_CLASS_HEAP     pheapToBuild;__KERNEL_MODE_PROC(pheapToBuild = _Allocate_Heap_Object();                         /*  申请控制块                  */);if (!pheapToBuild) {                                                /*  失败                        */return  (LW_NULL);}return  (_HeapCtorEx(pheapToBuild, pvStartAddress, stByteSize, LW_FALSE));      /*  构造内存堆                  */
}

/*********************************************************************************************************
** 函数名称: _HeapCtor
** 功能描述: 构造一个内存堆
** 输　入  : pheapToBuild          需要创建的堆
**           pvStartAddress        起始内存地址
**           stByteSize            内存堆的大小
**           bIsMosHeap            是否为多操作系统内存堆
** 输　出  : 建立好的内存堆控制块
*********************************************************************************************************/
PLW_CLASS_HEAP  _HeapCtorEx (PLW_CLASS_HEAP    pheapToBuild,PVOID             pvStartAddress, size_t            stByteSize, BOOL              bIsMosHeap)
{REGISTER PLW_CLASS_SEGMENT  psegment;REGISTER addr_t             ulStart      = (addr_t)pvStartAddress;//对内存地址向上圆整，获取地址对齐的起始地址REGISTER addr_t             ulStartAlign = ROUND_UP(ulStart, LW_CFG_HEAP_ALIGNMENT);//如果对起始地址进行了调整，则内存大小要减去调整值if (ulStartAlign > ulStart) {stByteSize -= (size_t)(ulStartAlign - ulStart);                 /*  去掉前面的不对齐长度        */}//对内存大小向下圆整，获取对齐的内存大小stByteSize = ROUND_DOWN(stByteSize, LW_CFG_HEAP_ALIGNMENT);         /*  分段大小对其                *///初始化后只有一个空闲的段psegment   = (PLW_CLASS_SEGMENT)ulStartAlign;                       /*  第一个分段起始地址          */_LIST_LINE_INIT_IN_CODE(psegment->SEGMENT_lineManage);              /*  初始化第一个分段            */_LIST_RING_INIT_IN_CODE(psegment->SEGMENT_ringFreeList);/*  第一个分段的大小            */psegment->SEGMENT_stByteSize = stByteSize - ROUND_UP(sizeof(LW_CLASS_SEGMENT), LW_CFG_HEAP_ALIGNMENT);          psegment->SEGMENT_stMagic    = LW_SEG_MAGIC_REAL;pheapToBuild->HEAP_pringFreeSegment  = LW_NULL;_List_Ring_Add_Ahead(&psegment->SEGMENT_ringFreeList, &pheapToBuild->HEAP_pringFreeSegment);         /*  加入空闲表                  *///初始化堆对象各成员pheapToBuild->HEAP_pvStartAddress    = (PVOID)ulStartAlign;pheapToBuild->HEAP_ulSegmentCounter  = 1;                           /*  当前的分段数                */pheapToBuild->HEAP_stTotalByteSize   = stByteSize;                  /*  分区总大小                  */pheapToBuild->HEAP_stUsedByteSize    = ROUND_UP(sizeof(LW_CLASS_SEGMENT), LW_CFG_HEAP_ALIGNMENT);  /*  使用的字节数                */pheapToBuild->HEAP_stFreeByteSize    = stByteSize- ROUND_UP(sizeof(LW_CLASS_SEGMENT), LW_CFG_HEAP_ALIGNMENT);  /*  空闲的字节数                */pheapToBuild->HEAP_stMaxUsedByteSize = pheapToBuild->HEAP_stUsedByteSize;pheapToBuild->HEAP_ulLock = API_SemaphoreMCreate("heap_lock",LW_PRIO_DEF_CEILING,__HEAP_LOCK_OPT,LW_NULL);      /*  建立锁                      */return  (pheapToBuild);
}

从堆中分配内存

从堆中分配内存就是遍历空闲段链表，直到发现第一个段空间大小大于等于目标长度，将该段从空闲段链表上删除，如果段空间远大于目标需求，则要把尾部多余空间拆分成一个空闲段插入空闲段链表。

/*********************************************************************************************************
** 函数名称: _HeapAllocate
** 功能描述: 从堆中申请字节池 (首次适应算法)
** 输　入  : pheap              堆控制块
**           stByteSize         分配的字节数
**           pcPurpose          分配内存的用途
** 输　出  : 分配的内存地址 
*********************************************************************************************************/
PVOID  _HeapAllocate (PLW_CLASS_HEAP  pheap, size_t  stByteSize, CPCHAR  pcPurpose)
{REGISTER size_t             stSize;REGISTER size_t             stNewSegSize;REGISTER PLW_CLASS_SEGMENT  psegment;REGISTER PLW_CLASS_SEGMENT  psegmentNew;PLW_LIST_LINE      plineHeader;PLW_LIST_RING      pringFreeSegment;REGISTER ULONG              ulLockErr;//获取默认对齐的段长度，即实际分配长度肯定是大于等于目标长度的stSize = ROUND_UP(stByteSize, LW_CFG_HEAP_SEG_MIN_SIZE);            /*  获得页对齐内存大小          */if (pheap->HEAP_stFreeByteSize < stSize) {                          /*  没有空间                    */return  (LW_NULL);}//获取堆空闲链表pringFreeSegment = pheap->HEAP_pringFreeSegment;                    /*  第一个空闲分段              */if (pringFreeSegment == LW_NULL) {return  (LW_NULL);                                              /*  没有空闲分段                */}//遍历空闲链表，从中找到第一个空间足够的段用于目标内存分配，即首次适应算法do {psegment = _LIST_ENTRY(pringFreeSegment, LW_CLASS_SEGMENT, SEGMENT_ringFreeList);if (psegment->SEGMENT_stByteSize >=  stSize) {break;                                                      /*  找到分段                    */}pringFreeSegment = _list_ring_get_next(pringFreeSegment);if (pringFreeSegment == pheap->HEAP_pringFreeSegment) {         /*  遍历完毕, 没有合适的空闲分段*/return  (LW_NULL);}} while (1);//将选中的段从空闲段列表中删除_List_Ring_Del(&psegment->SEGMENT_ringFreeList, &pheap->HEAP_pringFreeSegment);                      /*  将当前分段从空闲段链中删除  *///如果选中的段空间大小，大于目标长度，则需要将该段的后半段截取为一个新的空闲段if ((psegment->SEGMENT_stByteSize - stSize) > (__SEGMENT_BLOCK_SIZE_ALIGN + LW_CFG_HEAP_SEG_MIN_SIZE)) {      /*  是否可以分出新段            */stNewSegSize = psegment->SEGMENT_stByteSize - stSize;           /*  计算新分段的总大小          */psegment->SEGMENT_stByteSize = stSize;                          /*  重新确定当前分段大小        */psegmentNew = (PLW_CLASS_SEGMENT)(__HEAP_SEGMENT_DATA_PTR(psegment)+ stSize);                                          /*  填写新分段的诸多信息        */psegmentNew->SEGMENT_stByteSize = stNewSegSize- __SEGMENT_BLOCK_SIZE_ALIGN;psegmentNew->SEGMENT_stMagic    = LW_SEG_MAGIC_REAL;plineHeader = &psegment->SEGMENT_lineManage;_List_Line_Add_Tail(&psegmentNew->SEGMENT_lineManage,&plineHeader);                              /*  将新分段链入邻居链表        */__HEAP_ADD_NEW_SEG_TO_FREELIST(psegmentNew, pheap);             /*  将新分段链接入空闲分段链表  */pheap->HEAP_ulSegmentCounter++;                                 /*  回写内存堆控制块            */pheap->HEAP_stUsedByteSize += (stSize + __SEGMENT_BLOCK_SIZE_ALIGN);pheap->HEAP_stFreeByteSize -= (stSize + __SEGMENT_BLOCK_SIZE_ALIGN);} else {pheap->HEAP_stUsedByteSize += psegment->SEGMENT_stByteSize;pheap->HEAP_stFreeByteSize -= psegment->SEGMENT_stByteSize;}return  ((PVOID)__HEAP_SEGMENT_DATA_PTR(psegment));                 /*  返回分配的内存首地址        */
}

用户在开发设备驱动时，可能会遇到特殊的需求，比如设备需要在指定内存区域申请字节对齐的内存空间，这时用户就需要通过调用函数_HeapAllocateAlign实现这一功能。当设备要求在指定内存区域申请内存空间，但没有要求字节对齐的时候，用户可以调用函数_HeapAllocate或函数_HeapZallocate实现。

对于有对齐要求的分配请求，除了要检查段大小外，还要检查段缓存对齐情况。对于对齐值要求较高的请求，需要先找到一个较大空闲段，跳过前面非对齐部分来实现对齐需求，基于此对齐地址构建目标段，则这个较大空闲段的前部后后部都可能需要构建为新的空闲段。

/*********************************************************************************************************
** 函数名称: _HeapAllocateAlign
** 功能描述: 从堆中申请字节池 (首次适应算法) (指定内存对齐关系)
** 输　入  : pheap              堆控制块
**           stByteSize         分配的字节数
**           stAlign            内存对齐关系，必须是2的幂次大小
**           pcPurpose          分配内存的用途
** 输　出  : 分配的内存地址
*********************************************************************************************************/
PVOID  _HeapAllocateAlign (PLW_CLASS_HEAP  pheap, size_t  stByteSize, size_t  stAlign, CPCHAR  pcPurpose)
{REGISTER size_t             stSize;REGISTER size_t             stNewSegSize;REGISTER PLW_CLASS_SEGMENT  psegment;REGISTER PLW_CLASS_SEGMENT  psegmentNew;PLW_CLASS_SEGMENT  psegmentAlloc = LW_NULL;                /*  避过 GCC 一个无谓的警告     */UINT8             *pcAlign;addr_t             ulAlignMask = (addr_t)(stAlign - 1);size_t             stAddedSize;                            /*  前端补齐附加数据大小        */BOOL               bLeftNewFree;                           /*  左端的内存是否可以开辟新段  */PLW_LIST_LINE      plineHeader;PLW_LIST_RING      pringFreeSegment;REGISTER ULONG              ulLockErr;stSize = ROUND_UP(stByteSize, LW_CFG_HEAP_SEG_MIN_SIZE);            /*  获得页对齐内存大小          */if (pheap->HEAP_stFreeByteSize < stSize) {                          /*  没有空间                    */return  (LW_NULL);}pringFreeSegment = pheap->HEAP_pringFreeSegment;                    /*  第一个空闲分段              */if (pringFreeSegment == LW_NULL) {return  (LW_NULL);                                              /*  没有空闲分段                */}do {psegment = _LIST_ENTRY(pringFreeSegment, LW_CLASS_SEGMENT, SEGMENT_ringFreeList);//检查内存分段地址对齐状态，如果不对齐，则向上圆整到对齐地址if (((size_t)__HEAP_SEGMENT_DATA_PTR(psegment) & ulAlignMask) == 0) {pcAlign     = __HEAP_SEGMENT_DATA_PTR(psegment);            /*  本身就满足对齐条件          */stAddedSize = 0;} else {                                                        /*  获取满则对齐条件的内存点    */pcAlign     = (UINT8 *)(((addr_t)__HEAP_SEGMENT_DATA_PTR(psegment) | ulAlignMask) + 1);stAddedSize = (size_t)(pcAlign - __HEAP_SEGMENT_DATA_PTR(psegment));}//检查内存分段大小if (psegment->SEGMENT_stByteSize >= (stSize + stAddedSize)) {if (stAddedSize >= (__SEGMENT_BLOCK_SIZE_ALIGN + LW_CFG_HEAP_SEG_MIN_SIZE)) {bLeftNewFree = LW_TRUE;                                 /*  左端可以开辟新段            */} else {bLeftNewFree = LW_FALSE;stSize += stAddedSize;                                  /*  使用整个分段                */psegmentAlloc = psegment;                               /*  记录本块内存                */}break;                                                      /*  找到分段                    */}pringFreeSegment = _list_ring_get_next(pringFreeSegment);if (pringFreeSegment == pheap->HEAP_pringFreeSegment) {         /*  遍历完毕, 没有合适的空闲分段*/return  (LW_NULL);}} while (1);//对齐保留空间大于节点最小空间，则左端可以开辟一个空闲段if (bLeftNewFree) {                                                 /*  首先将这个段拆分            */psegmentNew = (PLW_CLASS_SEGMENT)(__HEAP_SEGMENT_DATA_PTR(psegment)+ stAddedSize - __SEGMENT_BLOCK_SIZE_ALIGN);psegmentNew->SEGMENT_stByteSize = psegment->SEGMENT_stByteSize- stAddedSize;psegmentNew->SEGMENT_stMagic    = LW_SEG_MAGIC_REAL;plineHeader = &psegment->SEGMENT_lineManage;_List_Line_Add_Tail(&psegmentNew->SEGMENT_lineManage,&plineHeader);                              /*  将新分段链入邻居链表        */__HEAP_ADD_NEW_SEG_TO_FREELIST(psegmentNew, pheap);             /*  将新分段链接入空闲分段链表  */psegment->SEGMENT_stByteSize = stAddedSize - __SEGMENT_BLOCK_SIZE_ALIGN;psegment = psegmentNew;                                         /*  确定到分配的分区            */pheap->HEAP_ulSegmentCounter++;                                 /*  回写内存堆控制块            */pheap->HEAP_stUsedByteSize += __SEGMENT_BLOCK_SIZE_ALIGN;pheap->HEAP_stFreeByteSize -= __SEGMENT_BLOCK_SIZE_ALIGN;}_List_Ring_Del(&psegment->SEGMENT_ringFreeList, &pheap->HEAP_pringFreeSegment);                      /*  将当前分段从空闲段链中删除  */if ((psegment->SEGMENT_stByteSize - stSize) > (__SEGMENT_BLOCK_SIZE_ALIGN + LW_CFG_HEAP_SEG_MIN_SIZE)) {      /*  是否可以分出新段            */stNewSegSize = psegment->SEGMENT_stByteSize - stSize;           /*  计算新分段的总大小          */psegment->SEGMENT_stByteSize = stSize;                          /*  重新确定当前分段大小        */psegmentNew = (PLW_CLASS_SEGMENT)(__HEAP_SEGMENT_DATA_PTR(psegment)+ stSize);                                          /*  填写新分段的诸多信息        */psegmentNew->SEGMENT_stByteSize = stNewSegSize- __SEGMENT_BLOCK_SIZE_ALIGN;psegmentNew->SEGMENT_stMagic    = LW_SEG_MAGIC_REAL;plineHeader = &psegment->SEGMENT_lineManage;_List_Line_Add_Tail(&psegmentNew->SEGMENT_lineManage,&plineHeader);                              /*  将新分段链入邻居链表        */__HEAP_ADD_NEW_SEG_TO_FREELIST(psegmentNew, pheap);             /*  将新分段链接入空闲分段链表  */pheap->HEAP_ulSegmentCounter++;                                 /*  回写内存堆控制块            */pheap->HEAP_stUsedByteSize += (stSize + __SEGMENT_BLOCK_SIZE_ALIGN);pheap->HEAP_stFreeByteSize -= (stSize + __SEGMENT_BLOCK_SIZE_ALIGN);} else {pheap->HEAP_stUsedByteSize += psegment->SEGMENT_stByteSize;pheap->HEAP_stFreeByteSize -= psegment->SEGMENT_stByteSize;}if ((bLeftNewFree == LW_FALSE) && stAddedSize) {                    /*  左端有些内存没有使用        */PLW_CLASS_SEGMENT    psegmentFake = __HEAP_SEGMENT_SEG_PTR(pcAlign);size_t              *pstLeft      = (((size_t *)pcAlign) - 1);*pstLeft = (size_t)psegmentAlloc;                               /*  记录真正分段控制块位置      */if (pstLeft != &psegmentFake->SEGMENT_stMagic) {psegmentFake->SEGMENT_stMagic = ~LW_SEG_MAGIC_REAL;         /*  不能识别本分段头            */}}return  (pcAlign);                                                  /*  返回分配的内存首地址        */
}

释放从堆中分配的内存

释放从堆中分配的内存时，要判断其前节点和后节点是否为空闲段，如果是则要进行相应的空闲段合并操作，已避免堆中内存碎片的积累。

/*********************************************************************************************************
** 函数名称: _HeapFree
** 功能描述: 将申请的空间释放回堆, 且下一次优先被分配! (立即聚合算法)
** 输　入  : 
**           pheap              堆控制块
**           pvStartAddress     归还的地址
**           bIsNeedVerify      是否需要安全性检查
**           pcPurpose          谁释放内存
** 输　出  : 正确返回 LW_NULL 否则返回 pvStartAddress
*********************************************************************************************************/
PVOID  _HeapFree (PLW_CLASS_HEAP  pheap, PVOID  pvStartAddress, BOOL  bIsNeedVerify, CPCHAR  pcPurpose)
{REGISTER BOOL               bIsMergeOk = LW_FALSE;REGISTER size_t             stSegmentByteSizeFree;PLW_CLASS_SEGMENT  psegment;REGISTER PLW_LIST_LINE      plineLeft;REGISTER PLW_LIST_LINE      plineRight;REGISTER PLW_CLASS_SEGMENT  psegmentLeft;                           /*  左分段                      */REGISTER PLW_CLASS_SEGMENT  psegmentRight;                          /*  右分段                      */PLW_LIST_LINE      plineDummyHeader = LW_NULL;             /*  用于参数传递的头            */REGISTER BOOL               bVerifyOk;                              /*  是否检查成功                */REGISTER ULONG              ulLockErr;if (pvStartAddress == LW_NULL) {return  (pvStartAddress);}//获取当前分段psegment = __HEAP_SEGMENT_SEG_PTR(pvStartAddress);              /*  查找段控制块地址            */if (!__HEAP_SEGMENT_IS_REAL(psegment)) {                        /*  控制块地址不真实            */psegment = (PLW_CLASS_SEGMENT)(*((size_t *)pvStartAddress - 1));}if (!__HEAP_SEGMENT_IS_REAL(psegment) ||!__HEAP_SEGMENT_IS_USED(psegment)) {                        /*  段控制块无效或已经被释放    */return  (pvStartAddress);}//获取的当前分段的左右分段plineLeft  = _list_line_get_prev(&psegment->SEGMENT_lineManage);    /*  左分段                      */plineRight = _list_line_get_next(&psegment->SEGMENT_lineManage);    /*  右分段                      */if (plineLeft) {psegmentLeft  = _LIST_ENTRY(plineLeft,  LW_CLASS_SEGMENT, SEGMENT_lineManage);                /*  左分段控制块                */} else {psegmentLeft  = LW_NULL;}if (plineRight) {psegmentRight = _LIST_ENTRY(plineRight, LW_CLASS_SEGMENT, SEGMENT_lineManage);                /*  右分段控制块                */} else {psegmentRight = LW_NULL;}stSegmentByteSizeFree = psegment->SEGMENT_stByteSize;               /*  将要释放的分段内容大小      *///合并左分段  if (psegmentLeft) {if (__HEAP_SEGMENT_IS_USED(psegmentLeft) ||!__HEAP_SEGMENT_CAN_ML(psegment, psegmentLeft)) {           /*  不能聚合                    */goto    __merge_right;                                      /*  进入右段聚合                */}psegmentLeft->SEGMENT_stByteSize += (stSegmentByteSizeFree + __SEGMENT_BLOCK_SIZE_ALIGN);_List_Line_Del(&psegment->SEGMENT_lineManage, &plineDummyHeader);                              /*  从邻居链表中删除当前分段    */pheap->HEAP_ulSegmentCounter--;pheap->HEAP_stUsedByteSize -= (__SEGMENT_BLOCK_SIZE_ALIGN + stSegmentByteSizeFree);pheap->HEAP_stFreeByteSize += (__SEGMENT_BLOCK_SIZE_ALIGN + stSegmentByteSizeFree);psegment = psegmentLeft;                                        /*  当前分段变成左分段          */if (plineRight == LW_NULL) {                                    /*  最右侧分段                  */_List_Ring_Del(&psegment->SEGMENT_ringFreeList, &pheap->HEAP_pringFreeSegment);__HEAP_ADD_NEW_SEG_TO_FREELIST(psegment, pheap);            /*  重新插入适当的位置(节约内存)*/}bIsMergeOk = LW_TRUE;                                           /*  成功进行了左端合并          */}__merge_right://合并右分段if (psegmentRight) {                                                /*  右分段聚合                  */if (__HEAP_SEGMENT_IS_USED(psegmentRight) ||!__HEAP_SEGMENT_CAN_MR(psegment, psegmentRight)) {          /*  不能聚合                    */goto    __right_merge_fail;                                 /*  进入右段聚合失败            */}psegment->SEGMENT_stByteSize += (psegmentRight->SEGMENT_stByteSize + __SEGMENT_BLOCK_SIZE_ALIGN);_List_Ring_Del(&psegmentRight->SEGMENT_ringFreeList, &pheap->HEAP_pringFreeSegment);                  /*  将右分段从空闲表中删除      */_List_Line_Del(&psegmentRight->SEGMENT_lineManage, &plineDummyHeader);                              /*  将右分段从邻居链表中删除    */pheap->HEAP_ulSegmentCounter--;                                 /*  分区分段数量--              */if (bIsMergeOk == LW_FALSE) {                                   /*  当没有产生左合并时          */__HEAP_ADD_NEW_SEG_TO_FREELIST(psegment, pheap);            /*  这里插到空闲表头            */pheap->HEAP_stUsedByteSize -= (__SEGMENT_BLOCK_SIZE_ALIGN + stSegmentByteSizeFree);pheap->HEAP_stFreeByteSize += (__SEGMENT_BLOCK_SIZE_ALIGN + stSegmentByteSizeFree);} else {                                                        /*  左分段合并成功              */if (!_list_line_get_next(&psegment->SEGMENT_lineManage)) {  /*  合并后为最右侧分段          */_List_Ring_Del(&psegment->SEGMENT_ringFreeList, &pheap->HEAP_pringFreeSegment);__HEAP_ADD_NEW_SEG_TO_FREELIST(psegment, pheap);        /*  重新插入适当的位置(节约内存)*/}pheap->HEAP_stUsedByteSize -= (__SEGMENT_BLOCK_SIZE_ALIGN);pheap->HEAP_stFreeByteSize += (__SEGMENT_BLOCK_SIZE_ALIGN);}return  (LW_NULL);}__right_merge_fail:                                                     /*  右分段合并错误              */if (bIsMergeOk == LW_FALSE) {                                       /*  左分段合并失败              */__HEAP_ADD_NEW_SEG_TO_FREELIST(psegment, pheap);                /*  这里插到空闲表头            */pheap->HEAP_stUsedByteSize -= (stSegmentByteSizeFree);pheap->HEAP_stFreeByteSize += (stSegmentByteSizeFree);}return  (LW_NULL);
}

从堆中重新申请字节池

/*********************************************************************************************************
** 函数名称: _HeapRealloc
** 功能描述: 从堆中重新申请字节池
** 输　入  : pheap              堆控制块
**           pvStartAddress     原始的内存缓冲区 (可能需要释放)
**           stNewByteSize      需要新的内存大小
**           bIsNeedVerify      是否需要安全检查
**           pcPurpose          分配内存的用途
** 输　出  : 分配的内存地址
** 注  意  : 这里的 pvStartAddress 和 ulNewByteSize 必须真实有效, 这个函数是内部使用的.
*********************************************************************************************************/
PVOID  _HeapRealloc (PLW_CLASS_HEAP  pheap, PVOID           pvStartAddress, size_t          stNewByteSize,BOOL            bIsNeedVerify,CPCHAR          pcPurpose)
{REGISTER size_t             stSize;REGISTER size_t             stNewSegSize;PLW_CLASS_SEGMENT  psegment;REGISTER PLW_CLASS_SEGMENT  psegmentNew;PLW_LIST_LINE      plineHeader;REGISTER BOOL               bVerifyOk;                              /*  是否检查成功                */REGISTER ULONG              ulLockErr;//若新内存大小为0，则释放就内存if (stNewByteSize == 0) {if (pvStartAddress) {return  (_HeapFree(pheap, pvStartAddress, bIsNeedVerify, pcPurpose));              /*  释放先前分配的内存即可      */} else {return  (LW_NULL);}}//若旧内存为空，则分配新内存if (pvStartAddress == LW_NULL) {return  (_HeapAllocate(pheap, stNewByteSize, pcPurpose));       /*  仅分配新内存即可            */}//向上对齐内存大小stSize = ROUND_UP(stNewByteSize, LW_CFG_HEAP_SEG_MIN_SIZE);         /*  获得页对齐内存大小          */psegment = __HEAP_SEGMENT_SEG_PTR(pvStartAddress);              /*  查找段控制块地址            */if (!__HEAP_SEGMENT_IS_REAL(psegment)) {                        /*  控制块地址不真实            */psegment = (PLW_CLASS_SEGMENT)(*((size_t *)pvStartAddress - 1));}if (!__HEAP_SEGMENT_IS_REAL(psegment) ||!__HEAP_SEGMENT_IS_USED(psegment)) {                        /*  段控制块无效或已经被释放    */return  (LW_NULL);}//如果就内存段是特殊对齐方式分配的则不支持if (pvStartAddress != __HEAP_SEGMENT_DATA_PTR(psegment)) {          /*  realloc 不支持带有对齐特性  */return  (LW_NULL);}//如果新分配长度和就内存长度一样，则无需特殊处理if (stSize == psegment->SEGMENT_stByteSize) {                       /*  大小没有改变                */return  (pvStartAddress);}//如果新分配长度大于原有长度if (stSize > psegment->SEGMENT_stByteSize) {                        /*  希望分配到更大的空间        */REGISTER PLW_LIST_LINE      plineRight;REGISTER PLW_CLASS_SEGMENT  psegmentRight;                      /*  右分段                      */PLW_LIST_LINE      plineDummyHeader = LW_NULL;         /*  用于参数传递的头            *///如果右节点为空闲，合并后长度足够，则通过合并右节点来实现plineRight = _list_line_get_next(&psegment->SEGMENT_lineManage);/*  右分段                      */if (plineRight) {psegmentRight = _LIST_ENTRY(plineRight, LW_CLASS_SEGMENT, SEGMENT_lineManage);            /*  右分段控制块                */if (!__HEAP_SEGMENT_IS_USED(psegmentRight) &&__HEAP_SEGMENT_CAN_MR(psegment, psegmentRight)) {/*  右分段没有使用              */if ((psegmentRight->SEGMENT_stByteSize + __SEGMENT_BLOCK_SIZE_ALIGN) >=(stSize - psegment->SEGMENT_stByteSize)) {          /*  可以将右分段与本段合并      */_List_Ring_Del(&psegmentRight->SEGMENT_ringFreeList, &pheap->HEAP_pringFreeSegment);      /*  将右分段从空闲表中删除      */_List_Line_Del(&psegmentRight->SEGMENT_lineManage, &plineDummyHeader);                  /*  将右分段从邻居链表中删除    */psegment->SEGMENT_stByteSize += (psegmentRight->SEGMENT_stByteSize +__SEGMENT_BLOCK_SIZE_ALIGN);                   /*  更新本段大小                */pheap->HEAP_ulSegmentCounter--;                     /*  分区分段数量--              */pheap->HEAP_stUsedByteSize += psegmentRight->SEGMENT_stByteSize;pheap->HEAP_stFreeByteSize -= psegmentRight->SEGMENT_stByteSize;goto    __split_segment;}}}//需要先分配新段，然后拷贝数据，最后释放旧段pvStartAddress = _HeapAllocate(pheap, stSize, pcPurpose);       /*  重新开辟                    */if (pvStartAddress) {                                           /*  分配成功                    */lib_memcpy(pvStartAddress, __HEAP_SEGMENT_DATA_PTR(psegment), (UINT)psegment->SEGMENT_stByteSize);             /*  复制原始信息                */_HeapFree(pheap, __HEAP_SEGMENT_DATA_PTR(psegment), LW_FALSE, pcPurpose);                             /*  释放本块空间                */}return  (pvStartAddress);}__split_segment://如果是合并实现的，则合并后的新段长度可能远大于需求长度，所以要将断尾空间拆解为新空闲段stNewSegSize = psegment->SEGMENT_stByteSize - stSize;               /*  获取剩余的字节数            */if (stNewSegSize < (__SEGMENT_BLOCK_SIZE_ALIGN + LW_CFG_HEAP_SEG_MIN_SIZE)) {      /*  剩余空间太小, 无法分配新段  */__HEAP_UPDATA_MAX_USED(pheap);                                  /*  更新统计变量                */return  (pvStartAddress);}psegment->SEGMENT_stByteSize = stSize;                              /*  更新原始分段的大小          */psegmentNew = (PLW_CLASS_SEGMENT)(__HEAP_SEGMENT_DATA_PTR(psegment) + stSize);/*  确定新分段的地点            */psegmentNew->SEGMENT_stByteSize = stNewSegSize - __SEGMENT_BLOCK_SIZE_ALIGN;psegmentNew->SEGMENT_stMagic    = LW_SEG_MAGIC_REAL;_INIT_LIST_RING_HEAD(&psegmentNew->SEGMENT_ringFreeList);           /*  正在使用的分段              */plineHeader = &psegment->SEGMENT_lineManage;_List_Line_Add_Tail(&psegmentNew->SEGMENT_lineManage,&plineHeader);                                  /*  加入左右邻居链表连接        */pheap->HEAP_ulSegmentCounter++;                                     /*  堆中多了一个分段            */_HeapFree(pheap, __HEAP_SEGMENT_DATA_PTR(psegmentNew), LW_FALSE, pcPurpose);                                     /*  进行内存重组                */return  ((PVOID)__HEAP_SEGMENT_DATA_PTR(psegment));                 /*  返回原始内存点              */
}

删除堆对象

如果一个内存堆还在被使用时，理论上不应该被删除，当用户无法确定该堆是否正在被使用时，需要给参数bIsCheckUsed传递LW_TRUE，函数_HeapDelete会检查内存堆的使用情况：如果参数pheap所代表的内存堆没有被使用，则执行删除流程，执行成功时返回LW_NULL；执行失败则返回传入的内存堆的结构体指针。

/*********************************************************************************************************
** 函数名称: _HeapDelete
** 功能描述: 删除一个内存堆
** 输　入  : pheap             已经建立的控制块
**           bIsCheckUsed      是否检查使用情况
** 输　出  : 删除成功返回 LW_NULL
*********************************************************************************************************/
PLW_CLASS_HEAP  _HeapDelete (PLW_CLASS_HEAP  pheap, BOOL  bIsCheckUsed)
{if (_HeapDtor(pheap, bIsCheckUsed) == LW_NULL) {                    /*  必须是放完内存              */__KERNEL_MODE_PROC(_Free_Heap_Object(pheap);                                   /*  释放控制块                  */);return  (LW_NULL);} else {return  (pheap);}
}

/*********************************************************************************************************
** 函数名称: _HeapDtor
** 功能描述: 析构一个内存堆
** 输　入  : pheap             已经建立的控制块
**           bIsCheckUsed      当没有释放完时, 是否析构此堆
** 输　出  : 删除成功返回 LW_NULL
*********************************************************************************************************/
PLW_CLASS_HEAP _HeapDtor (PLW_CLASS_HEAP  pheap, BOOL  bIsCheckUsed)
{REGISTER ULONG              ulLockErr;REGISTER PLW_LIST_LINE      plineTemp;REGISTER PLW_CLASS_SEGMENT  psegment;if (bIsCheckUsed) {                                                 /*  检查分区是否空闲            */psegment = (PLW_CLASS_SEGMENT)pheap->HEAP_pvStartAddress;//遍历所有分段，如果有分段在使用中则返回堆地址for (plineTemp  = &psegment->SEGMENT_lineManage;plineTemp != LW_NULL;plineTemp  = _list_line_get_next(plineTemp)) {psegment = _LIST_ENTRY(plineTemp, LW_CLASS_SEGMENT, SEGMENT_lineManage);if (__HEAP_SEGMENT_IS_USED(psegment)) {return  (pheap);                                        /*  分区正在被使用              */}}}pheap->HEAP_stTotalByteSize = 0;                                    /*  防范互斥操作的漏洞          */pheap->HEAP_stFreeByteSize  = 0;                                    /*  将剩余的字节数置零          */                                                                        /*  解锁后不可能在进行分配      */return  (LW_NULL);
}

向一个堆添加内存

向一个堆内添加内存，即扩展堆空间，就是把一块新的内存空间构建为一个空闲段并插入到原堆链表的末尾，并插入到堆空闲段链表。

这里有个问题，刚创建的堆，会记录第一片内存的起始地址和大小，扩展后新加内存和之前的是不连续的，只是将段内存大小值修改了，新内存地址不会被记录。这样就不能确定某时刻堆是否被扩展过，扩展过几次。
从新加内存上分配段是没问题的，但是释放段时是否会由于空闲段合并，把两个不连续的内存空间合并为一个段。再有就是，可以扩展堆，但不能释放堆的扩展部分，释放堆时如何释放全部内存区域也是个问题。

当前内核中该接口调用的地方极少。

/*********************************************************************************************************
** 函数名称: _HeapAddMemory
** 功能描述: 向一个堆内添加内存
** 输　入  : pheap                 堆控制块
**           pvMemory              需要添加的内存 (必须保证对其)
**           stSize                内存大小 (必须大于一个分段大小最小值)
** 输　出  : 是否添加成功 
*********************************************************************************************************/
ULONG  _HeapAddMemory (PLW_CLASS_HEAP  pheap, PVOID  pvMemory, size_t  stSize)
{REGISTER PLW_LIST_LINE      plineTemp;REGISTER PLW_CLASS_SEGMENT  psegmentLast;REGISTER PLW_CLASS_SEGMENT  psegmentNew;REGISTER ULONG              ulLockErr;REGISTER addr_t             ulStart      = (addr_t)pvMemory;REGISTER addr_t             ulStartAlign = ROUND_UP(ulStart, LW_CFG_HEAP_ALIGNMENT);REGISTER addr_t             ulEnd, ulSeg;if (ulStartAlign > ulStart) {stSize -= (size_t)(ulStartAlign - ulStart);                     /*  去掉前面的不对齐长度        */}stSize = ROUND_DOWN(stSize, LW_CFG_HEAP_ALIGNMENT);                 /*  分段大小对其                */ulEnd  = ulStartAlign + stSize - 1;psegmentLast = (PLW_CLASS_SEGMENT)pheap->HEAP_pvStartAddress;plineTemp    = &psegmentLast->SEGMENT_lineManage;do {if (_list_line_get_next(plineTemp) == LW_NULL) {break;}/*  判断地址是否发生重叠        */psegmentLast = _LIST_ENTRY(plineTemp, LW_CLASS_SEGMENT, SEGMENT_lineManage);ulSeg = (addr_t)__HEAP_SEGMENT_DATA_PTR(psegmentLast);if ((ulStartAlign >= ulSeg) && (ulStartAlign < (ulSeg + psegmentLast->SEGMENT_stByteSize))) {return  (EFAULT);}if ((ulEnd >= ulSeg) && (ulEnd < (ulSeg + psegmentLast->SEGMENT_stByteSize))) {return  (EFAULT);}plineTemp = _list_line_get_next(plineTemp);} while (1);psegmentLast = _LIST_ENTRY(plineTemp, LW_CLASS_SEGMENT, SEGMENT_lineManage);psegmentNew = (PLW_CLASS_SEGMENT)ulStartAlign;psegmentNew->SEGMENT_stByteSize = stSize - __SEGMENT_BLOCK_SIZE_ALIGN;psegmentNew->SEGMENT_stMagic    = LW_SEG_MAGIC_REAL;_List_Line_Add_Right(&psegmentNew->SEGMENT_lineManage,&psegmentLast->SEGMENT_lineManage);__HEAP_ADD_NEW_SEG_TO_FREELIST(psegmentNew, pheap);pheap->HEAP_ulSegmentCounter++;pheap->HEAP_stTotalByteSize += stSize;pheap->HEAP_stUsedByteSize  += __SEGMENT_BLOCK_SIZE_ALIGN;pheap->HEAP_stFreeByteSize  += psegmentNew->SEGMENT_stByteSize;return  (ERROR_NONE);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！