【嵌入式】给 STM32H750 的 D2 内存域设计一个动态内存分配释放器
# 给 STM32H750 的 D2 内存域设计一个动态内存分配释放器STM32H750 有多个不同的内存区域，按 STM32CubeMX 生成的链接器脚本，默认的数据（`.data`）和未初始化数据（`.bss` ）都被放入了 `RAM_D1` 区域。
而如果想要使用 `RAM_D2`、`RAM_D3`，就要自己想辙了。这个时候，我选择设计一款内存动态分配释放器，实现 `malloc()`、`realloc()`、`free()`，岂不是香的很？然后很多的第三方库比如 `miniz` 压缩库等需要对少量内存进行动态分配释放的时候，我们有内存分配器，就可以顺利移植这些库进来。
## 特性
* 较低的内存开销（每个内存块头部有一个 `Word` 长度的变量用于标记内存块）
* 只要 `ALLOC_MEMORY_ADDRESS` 是对齐的，那么分配出来的内存也是按 `ALLOC_MEMORY_ADDRESS` 对齐的。
* 可在中断处理过程里调用。
* 遍历堆以分配内存（O(N)复杂度，适合单片机小内存管理）
* 较为简单的代码实现。
* 有堆异常检测，有重复释放检测。
* 分配时会根据分配的空间需求来尝试合并碎片块。
* 允许调用 `DynAlloc_Alloc(0)`、`DynAlloc_Free(0)`、`DynAlloc_Realloc(0, 0)`
## 代码
废话不多说，直接提供代码。经过测试，目前没发现问题。
### dynalloc.h
```C
#ifndef INC_DYNALLOC_H_
#define INC_DYNALLOC_H_ 1
#ifndef ALLOC_MEMORY_ADDRESS
#define ALLOC_MEMORY_ADDRESS 0x30000000
#define ALLOC_MEMORY_SIZE ((128 + 128 + 32) * 1024)
#define ALLOC_MEMORY_ALIGNMENT 8
#endif
#include <stddef.h>
// This header file provides `__disable_irq()` and `__enable_irq()`
#include "stm32h7xx_hal.h"
extern void Error_Handler();
void DynAlloc_Init();
void *DynAlloc_Alloc(size_t size);
void *DynAlloc_Realloc(void *user_ptr, size_t new_size);
void DynAlloc_Free(void *addr);
#endif /* INC_DYNALLOC_H_ */
```
### dynalloc.c
```C
#include "dynalloc.h"
#include <stdint.h>
#include <string.h>
#define ALLOC_MEMORY_ADDRESS_END (ALLOC_MEMORY_ADDRESS) + (ALLOC_MEMORY_SIZE)
#define ALLOC_MEMORY_ADDRESS_MAX ((ALLOC_MEMORY_ADDRESS_END) - 1)
#if ALLOC_MEMORY_SIZE > 0x7FFFFFFF
typedef uint64_t asize_t;
static const uint64_t SizeMask = 0x7fffffffffffffff;
static const uint64_t UsageMask = 0x8000000000000000;
#define ASIZE_LEN 8
#elif ALLOC_MEMORY_SIZE > 0x7FFF
typedef uint32_t asize_t;
static const uint32_t SizeMask = 0x7fffffff;
static const uint32_t UsageMask = 0x80000000;
#define ASIZE_LEN 4
#elif ALLOC_MEMORY_SIZE > 0x7F
typedef uint16_t asize_t;
static const uint16_t SizeMask = 0x7fff;
static const uint16_t UsageMask = 0x8000;
#define ASIZE_LEN 2
#else
typedef uint8_t asize_t;
static const uint8_t SizeMask = 0x7f;
static const uint8_t UsageMask = 0x80;
#define ASIZE_LEN 1
#endif
#define ALIGN_UP(x) (((x) - 1) / (ALLOC_MEMORY_ALIGNMENT) + 1) * (ALLOC_MEMORY_ALIGNMENT)
#pragma pack(push, 1)
typedef struct MemBlockTag_s
{
// Block status
asize_t block_state;
// paddings
#if (ALLOC_MEMORY_ALIGNMENT) - ASIZE_LEN > 0
uint8_t _pad[(ALLOC_MEMORY_ALIGNMENT)-ASIZE_LEN];
#endif
// The pointer to the allocated data
uint8_t data;
}MemBlockTag_t;
#pragma pack(pop)
void HeapCorrupted()
{
Error_Handler();
}
void DoubleFree()
{
Error_Handler();
}
void BadFree()
{
Error_Handler();
}
void BadReallocPtr()
{
Error_Handler();
}
static size_t GetBlockSize(MemBlockTag_t *b)
{
return b->block_state & SizeMask;
}
static void SetBlockSize(MemBlockTag_t *b, size_t size)
{
b->block_state &= ~SizeMask;
b->block_state |= size;
}
static int GetIsInuse(MemBlockTag_t *b)
{
return b->block_state & UsageMask;
}
static void SetIsInuse(MemBlockTag_t *b, int val)
{
if (val)
b->block_state |= UsageMask;
else
b->block_state &= ~UsageMask;
}
static void SetBlockState(MemBlockTag_t *b, size_t size, int is_inuse)
{
SetBlockSize(b, size);
SetIsInuse(b, is_inuse);
}
static MemBlockTag_t *GetBlockTagFromUserPtr(void *ptr)
{
MemBlockTag_t *ret = (MemBlockTag_t *)((size_t)ptr - (sizeof * ret));
if ((size_t)ret + GetBlockSize(ret) >= ALLOC_MEMORY_ADDRESS_END) HeapCorrupted();
return ret;
}
static void *GetUserPtr(MemBlockTag_t *ptr)
{
return (void*)&ptr->data;
}
static MemBlockTag_t *NextBlock(MemBlockTag_t *cur)
{
return (MemBlockTag_t *)((size_t)cur + GetBlockSize(cur));
}
static size_t GetContinuousFreeSize(MemBlockTag_t *ptr, size_t target_size)
{
size_t sum = 0;
while (!GetIsInuse(ptr))
{
sum += GetBlockSize(ptr);
ptr = NextBlock(ptr);
if ((size_t)ptr >= ALLOC_MEMORY_ADDRESS_END) break;
if (sum >= target_size) break;
}
return sum;
}
static void MakeFreeSpace(MemBlockTag_t *ptr, size_t size)
{
SetBlockState(ptr, size, 0);
}
void DynAlloc_Init()
{
MemBlockTag_t *ptr = (MemBlockTag_t *)ALLOC_MEMORY_ADDRESS;
__disable_irq();
MakeFreeSpace(ptr, ALLOC_MEMORY_SIZE);
__enable_irq();
}
void *DynAlloc_Alloc(size_t size)
{
MemBlockTag_t *ptr = (MemBlockTag_t *)ALLOC_MEMORY_ADDRESS;
size_t block_size_to_alloc = ALIGN_UP(size + (sizeof * ptr));
__disable_irq();
while (1)
{
size_t block_size = GetBlockSize(ptr);
if (GetIsInuse(ptr))
{
ptr = NextBlock(ptr);
if ((size_t)ptr >= ALLOC_MEMORY_ADDRESS_MAX)
{
__enable_irq();
return NULL;
}
}
else
{
size_t free_space = GetContinuousFreeSize(ptr, block_size_to_alloc);
if (free_space < block_size_to_alloc)
{
MakeFreeSpace(ptr, free_space);
ptr = NextBlock(ptr);
continue;
}
else
{
MemBlockTag_t *ret = ptr;
size_t next_free_space = free_space - block_size_to_alloc;
if (next_free_space <= sizeof * ptr)
block_size_to_alloc = free_space;
SetBlockState(ret, block_size_to_alloc, 1);
if (block_size == block_size_to_alloc) return GetUserPtr(ret);
ptr = NextBlock(ret);
MakeFreeSpace(ptr, free_space - block_size_to_alloc);
__enable_irq();
return GetUserPtr(ret);
}
}
}
}
void *DynAlloc_Realloc(void *user_ptr, size_t new_size)
{
MemBlockTag_t *ptr;
size_t block_size_to_alloc;
size_t block_size;
size_t avail_space;
if (user_ptr == NULL) return DynAlloc_Alloc(new_size);
if (!new_size)
{
DynAlloc_Free(user_ptr);
return NULL;
}
if ((size_t)user_ptr < ALLOC_MEMORY_ADDRESS || (size_t)user_ptr > ALLOC_MEMORY_ADDRESS_MAX) BadReallocPtr();
__disable_irq();
ptr = GetBlockTagFromUserPtr(user_ptr);
block_size = GetBlockSize(ptr);
block_size_to_alloc = ALIGN_UP(new_size + sizeof * ptr);
if (block_size_to_alloc == block_size)
{
__enable_irq();
return user_ptr;
}
if (block_size_to_alloc > block_size)
avail_space = block_size + GetContinuousFreeSize(NextBlock(ptr), block_size_to_alloc - block_size);
else
avail_space = block_size;
if (avail_space >= block_size_to_alloc)
{
size_t tail_size = avail_space - block_size_to_alloc;
if (tail_size > sizeof * ptr)
{
SetBlockSize(ptr, block_size_to_alloc);
ptr = NextBlock(ptr);
MakeFreeSpace(ptr, tail_size);
}
__enable_irq();
return user_ptr;
}
else
{
__enable_irq();
void *new_addr = DynAlloc_Alloc(new_size);
if (!new_addr) return NULL;
memcpy(new_addr, user_ptr, GetBlockSize(ptr));
DynAlloc_Free(user_ptr);
return new_addr;
}
}
void DynAlloc_Free(void *addr)
{
MemBlockTag_t *ptr;
MemBlockTag_t *next_ptr;
if (!addr) return;
if ((size_t)addr < ALLOC_MEMORY_ADDRESS || (size_t)addr > ALLOC_MEMORY_ADDRESS_MAX)
{
BadFree();
return;
}
__disable_irq();
ptr = GetBlockTagFromUserPtr(addr);
if (!(GetIsInuse(ptr)))
{
__enable_irq();
DoubleFree();
return;
}
SetIsInuse(ptr, 0);
next_ptr = NextBlock(ptr);
if ((size_t)next_ptr <= ALLOC_MEMORY_ADDRESS_MAX && !GetIsInuse(next_ptr))
{
size_t free_space = GetBlockSize(ptr) + GetBlockSize(next_ptr);
SetBlockSize(ptr, free_space);
}
__enable_irq();
}
```
你需要提供一个函数 `Error_Handler()`，一旦出现内存管理上的错误比如堆错误或者重复释放、错误释放错误，这个函数被调用，你在调试的时候可以根据调用栈判断具体的出错原因（堆错误、重复释放、错误释放）。
```
void Error_Handler()
{
for(;;);
}
```
程序开始运行时，需要先调用 `DynAlloc_Init()` 初始化堆，然后就可以分配、释放内存了。
## 行为
每一块内存区域的开头，被一个「内存区域标记」结构体管理，其标记内存块大小，以及是否被占用。
* 调用 `DynAlloc_Init()` 时，其仅在堆起始地址加上一块内存区域标记，把整块内存标记为未使用。
* 调用 `DynAlloc_Alloc()` 分配内存时，从堆起始地址开始 **遍历堆**（时间复杂度为 O(N) 因此不能用于大片内存的分配释放管理），找到空闲内存块后，持续向后探测多个空闲内存块直到找到足够大的连续的空闲内存块，将开头的部分设置为已占用，后续的部分合并为一个空闲内存块。
* 如果后续的空闲内存长度小于「内存区域标记」结构体的大小，那就无法分割。此时，这块的空闲内存被直接合并给这次分配内存的区块里面去。
* 将「内存区域标记」后面的内存的起始地址返回给用户。
* 用户调用 `DynAlloc_Relloc()` 进行内存分配大小调整时，先检测参数。比如旧指针如果是 `NULL` 则直接返回 `DynAlloc_Alloc()` 的结果；如果`new_size` 为零则调用 `DynAlloc_Free()` 释放内存。否则，进行内存大小的调整。
* 调整时，看当前内存块与后面的空闲内存块加起来够不够大；如果够大，就把当前内存块的大小往后扩展，并重新标记后续的内存块大小；而如果不够标记（空闲内存长度低于「内存区域标记」长度），就干脆吞掉。
* 如果后续空闲内存不够，那就直接重新分配内存，拷贝数据到新内存，释放当前内存，返回新地址。
* 用户调用 `DynAlloc_Free()` 时，先会检查指针的范围是不是我们管理的内存地址的范围，不是就调用 `BadFree()`，其调用 `Error_Handler()`；然后检查内存块的标记，看是不是有重复释放，有就调用 `DoubleFree()`，其调用 `Error_Handler()`；是不是「非法内存块」（判断内存块大小是否不正确），是的话调用 `HeapCorrupted()`，其调用 `Error_Handler()`。 用heap管理那套会不会更好一些,然后单独从一个heap里封装一套malloc 我的建议是你多看看书，csapp上面的内存分配方法比你这好多了。 好家伙，直接用死循环来处理异常:funk: YY菌 发表于 2025-12-22 09:15
好家伙，直接用死循环来处理异常
这是嵌入式开发的最常见的做法，在调试器里通过看调用栈来判断是通过哪条路进入了死循环。 自己管理内存，最好先对内存进行规划，最基本的大块内存和小散的内存先进行分开处理，是否需要初始化等，比如16字节的分块内存池，256字节的分块内存池，多种不同需求应对，分堆管理虽然浪费点内存，但是总比过于耗时的alloc强些 0xAA55 发表于 2025-12-29 13:37
这是嵌入式开发的最常见的做法，在调试器里通过看调用栈来判断是通过哪条路进入了死循环。 ...
没有Sleep或者hlt指令吗？:o YY菌 发表于 2025-12-30 08:57
没有Sleep或者hlt指令吗？
嵌入式开发比较忌讳依赖特定指令的写法，因为嵌入式开发需要考虑跨平台移植。 给释放内存做个链表，申请内存的时候记录节点，查找到结尾节点，整理释放内存链表，去除重复和包含项，再从释放内存链表上查找会不会比现在好些，至少内存充足的时候效率非常高 AyalaRs 发表于 2026-1-1 19:02
给释放内存做个链表，申请内存的时候记录节点，查找到结尾节点，整理释放内存链表，去除重复和包含项，再从 ...
我本来想在这种简陋的内存分配的基础上，添加利用二分查找树存储特定大小内存块的方式来加速查找内存块、分配或者合并内存等。实际上感觉非常的多余，因为 288 KB 本来就非常小了，还要在这样的区域上追加东西，又要吃掉一大块。
按现在的逻辑，也就是最简陋的情况下，最坏情况也就是遍历内存一两万次，其实是可以接受的。 本帖最后由 AyalaRs 于 2026-1-3 12:03 编辑
0xAA55 发表于 2026-1-2 16:04
我本来想在这种简陋的内存分配的基础上，添加利用二分查找树存储特定大小内存块的方式来加速查找内存块、 ...
特定大小块可不算好，还不如分堆呢；分堆的可以根据情况选择阶段性释放，整体释放；如果用整体释放，就不用储存每次申请的大小，只需要堆头记录位置就好；资源操作行为不同的方法用统一的接口，除非方法本身还有二级的内存管理系统，否则会出现严重的内存碎片化，特别是长生命周期的内存块中间穿插短生命周期的内存块
... | 长生命周期内存块1 | 短生命周期内存块{1至n个} | 长生命周期内存块2 | ... 当这个释放后申请长生命周期内存块就会出现下面这个问题
... | 长生命周期内存块1 | ...|长生命周期内存块|碎片（大小取决于最小内存申请大小） | 长生命周期内存块2 | ...
如果最小内存申请大小不是1，而且就算最小内存申请大小是1，刚刚申请到碎片化位置的概率也不高，短生命周期不同内存大小属于小问题，长短生命周期内存混杂到一起就会出现这个这个严重问题，如果持续运行几十天之后就会出现无内存分配的情况 0xAA55 发表于 2026-1-6 01:31
如果只是为了解决内存分配的问题，我有必要这么有病地自己造轮子吗？不论看没看过书，内存分配器本来就有 ...
```C
/*
* Name: neomalloc.c
* Description: Neo malloc core function.
* Author: cosh.cage#hotmail.com
* File ID: 1207250701A1207250923L00662
* License: LGPLv3
* Copyright (C) 2025 John Cage
*
* This file is part of Neo Malloc.
*
* Neo Malloc is free software: you can redistribute it and/or modify it under
* the terms of the GNU Lesser General Public License as published by the Free Software Foundation,
* either version 3 of the License, or (at your option) any later version.
*
* Neo Malloc is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License along with StoneValley.
* If not, see <https://www.gnu.org/licenses/>.
*
*/
#include "neomalloc.h"
#include <limits.h>/* Using macro CHAR_BIT. */
#include <string.h>/* Using function memcpy, memset. */
#ifdef _MSC_VER
#include <intrin.h>/* Use function __lzcnt16, __lzcnt and __lzcnt64. */
#endif
/*
* +=HEAP_HEADER=+
* |size *===>sizeof(chunk) == head note + free chunk + data + foot note.
* |-------------|
* |hshsiz:3 |
* +=============+
* | POINTER *>-------\ Big chunks.
* |-------------| V
* | POINTER *-->NULL |
* |-------------| |
* | POINTER *-->NULL | Small chunks.
* +=============+--------|--------\
* |Head_note | V |
* +=FREE_CHUNK==+<-------/<--\ |
* | p *>-----------/ |
* |-------------| ^ |
* | p *>-----------/ > This is a free chunk.
* +=============+ |
* | DATA *==sizeof(size_t) |
* | |*4 |
* | | |
* | | |
* +=============+ /--------/
* |Foot_note | |
* +=============+--------/
*/
/* sizeof(UCHART) == 1. */
typedef unsigned char * PUCHAR;
typedef unsigned char UCHART;
/* Chunk pointer indices. */
enum en_FreeChunkPointer
{
FCP_PREV = 0,
FCP_NEXT = 1,
FCP_MAX= 2
};
/* Used and unused mark. */
#define USED false
#define FREE true
/* Free chunk linked list node. */
typedef struct st_FreeChunk
{
struct st_FreeChunk * p;
} FREE_CHUNK, * P_FREE_CHUNK;
/* Usable macros. */
#define MIN_CHUNK_SIZE (sizeof(size_t) * 2 + sizeof(FREE_CHUNK))
#define HEAP_BEGIN(ph) (sizeof(HEAP_HEADER) + (((P_HEAP_HEADER)(ph))->hshsiz * sizeof(P_HEAP_HEADER)))
#define ALIGN (sizeof(size_t) * CHAR_BIT / 4)
#define MASK (ALIGN - 1)
#define ASIZE(size) (((size) & MASK) ? ((size) + ALIGN) & ~(size_t)MASK: (size))
#define HEAD_NOTE(pfc) (*(size_t *)((PUCHAR)(pfc) - sizeof(size_t)))
#define FOOT_NOTE(pfc) (*(size_t *)((PUCHAR)(pfc) + (HEAD_NOTE(pfc) & ~(size_t)MASK)))
#define FREE_MASK ( (size_t)FREE)
#define USED_MASK (~(size_t)USED - 1)
/* File level function declarations. */
static size_t _nmCLZ (size_t n);
static P_FREE_CHUNK * _nmLocateHashTable (P_HEAP_HEADER ph, size_t i);
static void _nmUnlinkChunk (P_HEAP_HEADER ph, P_FREE_CHUNK ptr);
static void _nmRestoreEntrance (P_FREE_CHUNK * ppfc, P_FREE_CHUNK pfc);
static void * _nmSplitChunk (P_HEAP_HEADER ph, P_FREE_CHUNK pfc, size_t size);
static void _nmPutChunk (P_HEAP_HEADER ph, P_FREE_CHUNK pfc);
/* Attention: This Is An Internal Function. No Interface for Library Users.
* Function name: _nmCLZ
* Description: Count leading zero for size_t integer.
* Parameter:
* n The integer you wan to count.
* Return value:Integer of leading zeros.
*/
static size_t _nmCLZ(size_t n)
{
#ifdef __GNUC__
if (sizeof(size_t) == sizeof(long))
return __builtin_clzl(n);
else if (sizeof(size_t) == sizeof(long long))
return __builtin_clzll(n);
else
return __builtin_clz(n);
#elif defined _MSC_VER
switch (sizeof(size_t) * CHAR_BIT)
{
case 16:
return __lzcnt16((short)n);
case 32:
return __lzcnt(n);
#ifdef _M_X64
case 64:
return __lzcnt64(n);
#endif
}
#endif
register size_t i = n, j = 0;
while (i)
{
i >>= 1;
++j;
}
return sizeof(size_t) * CHAR_BIT - j;
}
/* Attention: This Is An Internal Function. No Interface for Library Users.
* Function name: _nmLocateHashTable
* Description: Locate into hash table by given index.
* Parameters:
* ph Pointer to heap header.
* i Index.
* Return value:Pointer to hash table content.
*/
static P_FREE_CHUNK * _nmLocateHashTable(P_HEAP_HEADER ph, size_t i)
{
if (ph->hshsiz > i) /* Locate into hash table directly. */
return &i[(P_FREE_CHUNK *)((PUCHAR)ph + sizeof(HEAP_HEADER))];
else /* Locate to biggest one. */
return &(ph->hshsiz - 1)[(P_FREE_CHUNK *)((PUCHAR)ph + sizeof(HEAP_HEADER))];
}
/* Attention: This Is An Internal Function. No Interface for Library Users.
* Function name: _nmUnlinkChunk
* Description: Cut chunk off from linked list.
* Parameters:
* ph Pointer to heap header.
* ptr Pointer to a free chunk.
* Return value:N/A.
*/
static void _nmUnlinkChunk(P_HEAP_HEADER ph, P_FREE_CHUNK ptr)
{
register P_FREE_CHUNK pfc = ptr, pofc = pfc;
register P_FREE_CHUNK * ppfc;
if ((_nmCLZ(HEAD_NOTE(pfc) & ~(size_t)MASK)) - _nmCLZ(ph->size) <= ph->hshsiz)
{
ppfc = _nmLocateHashTable(ph, _nmCLZ(HEAD_NOTE(pfc)) - _nmCLZ(ph->size));
if (NULL != *ppfc)
{
pfc = *ppfc;
do
{
pfc = pfc->p;
if (ptr == pfc)
{
register size_t i;
pfc->p->p = pfc->p;
pfc->p->p = pfc->p;
i = _nmCLZ(HEAD_NOTE(pfc)) - _nmCLZ(ph->size);
if (pfc == *_nmLocateHashTable(ph, i)) /* Reach at linked list header. */
*_nmLocateHashTable(ph, i) = NULL;
break;
}
} while (pfc != pofc);
}
}
}
/* Attention: This Is An Internal Function. No Interface for Library Users.
* Function name: _nmRestoreEntrance
* Description: Restore hash table entrance.
* Parameters:
* ppfc Pointer to hash table entrance.
* pfc Pointer to a free chunk.
* Return value:N/A.
*/
static void _nmRestoreEntrance(P_FREE_CHUNK * ppfc, P_FREE_CHUNK pfc)
{
pfc->p = pfc->p = pfc;
if (NULL != *ppfc)
{
pfc->p = *ppfc;
(*ppfc)->p->p = pfc;
pfc->p = (*ppfc)->p->p;
(*ppfc)->p->p = pfc;
}
*ppfc = pfc;
}
/* Attention: This Is An Internal Function. No Interface for Library Users.
* Function name: _nmSplitChunk
* Description: Split one chunk to two chunks and put back the latter one.
* Parameters:
* ph Pointer to heap header.
* pfc Pointer to a chunk to be split.
* size Size of the former chunk.
* Return value:The same chunk which is the same to pfc.
*/
static void * _nmSplitChunk(P_HEAP_HEADER ph, P_FREE_CHUNK pfc, size_t size)
{
register void * pt;
register size_t i;
i = HEAD_NOTE(pfc) - size - sizeof(size_t);
i &= ~(size_t)MASK;
HEAD_NOTE(pfc) = size;
FOOT_NOTE(pfc) = size;
pt = pfc;
pfc = (P_FREE_CHUNK)((PUCHAR)pfc + size + sizeof(size_t) * 2);
HEAD_NOTE(pfc) = i;
FOOT_NOTE(pfc) = i;
HEAD_NOTE(pfc) |= FREE_MASK;
FOOT_NOTE(pfc) |= FREE_MASK;
/* Search hash table and put new free chunk to the linked list. */
_nmRestoreEntrance(_nmLocateHashTable(ph, _nmCLZ(i) - _nmCLZ(ph->size)), pfc);
return pt;
}
/* Attention: This Is An Internal Function. No Interface for Library Users.
* Function name: _nmPutChunk
* Description: Put free chunk back to linked list.
* Parameters:
* ph Pointer to heap header.
* pfc Pointer to a free chunk.
* Return value:N/A.
*/
static void _nmPutChunk(P_HEAP_HEADER ph, P_FREE_CHUNK pfc)
{
if ((_nmCLZ(HEAD_NOTE(pfc) & ~(size_t)MASK)) - _nmCLZ(ph->size) > ph->hshsiz)
{
HEAD_NOTE(pfc) |= FREE_MASK;
FOOT_NOTE(pfc) |= FREE_MASK;
}
else
_nmRestoreEntrance(_nmLocateHashTable(ph, _nmCLZ(HEAD_NOTE(pfc)) - _nmCLZ(ph->size)), pfc);
}
/* Function name: nmCreateHeap
* Description: Create a heap from a memory buffer.
* Parameters:
* pbase Memory buffer starting address.
* size Size of the whole buffer.(Unit in byte)
* hshsiz Count of hash table entrances.
* Return value:NULL: Failed.
* Pointer to heap header(same as pbase): Succeeded.
* Tip: Parameter size must be greater than or equal to (sizeof(HEAP_HEADER) + (hshsiz * sizeof(P_FREE_CHUNK)) + MIN_CHUNK_SIZE).
*/
P_HEAP_HEADER nmCreateHeap(void * pbase, size_t size, size_t hshsiz)
{
P_FREE_CHUNK pfc;
HEAP_HEADER hh;
FREE_CHUNK fc;
size_t t;
if (NULL == pbase)
return NULL;
if (0 == hshsiz)
return NULL;
if (size < sizeof(HEAP_HEADER) + (hshsiz * sizeof(P_FREE_CHUNK)) + MIN_CHUNK_SIZE)
return NULL;
hh.size = size - (sizeof(HEAP_HEADER) + (hshsiz * sizeof(P_FREE_CHUNK)));
hh.size &= ~(size_t)MASK;
hh.hshsiz = hshsiz;
/* Set heap header. */
memcpy(pbase, &hh, sizeof(HEAP_HEADER));
/* Clear hash table. */
memset((PUCHAR)pbase + sizeof(HEAP_HEADER), 0, hshsiz * sizeof(size_t));
/* Set one free chunk. */
t = hh.size - (2 * sizeof(size_t));
if (t > ASIZE(t))
t = ASIZE(t);
else
t = t & ~(size_t)MASK;
pfc = (P_FREE_CHUNK)((PUCHAR)pbase + HEAP_BEGIN(&hh) + sizeof(size_t));
HEAD_NOTE(pfc) = t;
FOOT_NOTE(pfc) = t;
HEAD_NOTE(pfc) |= FREE_MASK;
FOOT_NOTE(pfc) |= FREE_MASK;
/* Set free chunk structure. */
fc.p = fc.p = pfc;
memcpy(pfc, &fc, sizeof(FREE_CHUNK));
/* Set hash table. */
*_nmLocateHashTable(pbase, _nmCLZ(t) - _nmCLZ(hh.size)) = pfc;
return (P_HEAP_HEADER)pbase;
}
/* Function name: nmExtendHeap
* Description: Enlarge heap.
* Parameters:
* ph Pointer to heap header.
* sizincl The incremental you want to extend.(Unit in byte)
* Return value:NULL: Failed.
* Pointer to heap header(same as ph): Succeeded.
* Tip: Parameter sizincl must be greater than or equal to (MIN_CHUNK_SIZE).
*/
P_HEAP_HEADER nmExtendHeap(P_HEAP_HEADER ph, size_t sizincl)
{
if (sizincl < MIN_CHUNK_SIZE)
return NULL;
else
{
/* Get the last chunk. */
bool bused;
size_t i;
PUCHAR phead;
P_FREE_CHUNK pfc;
phead = (PUCHAR)ph + HEAP_BEGIN(ph);
phead += ph->size - sizeof(size_t);
i = *(size_t *)phead;
bused = !!(i & (size_t)MASK);
if (FREE != bused)
{
pfc = (P_FREE_CHUNK)(phead + sizeof(size_t) * 2);
sizincl &= ~(size_t)MASK;
ph->size += sizincl;
sizincl -= sizeof(size_t) * 2;
HEAD_NOTE(pfc) = sizincl;
FOOT_NOTE(pfc) = sizincl;
HEAD_NOTE(pfc) |= FREE_MASK;
FOOT_NOTE(pfc) |= FREE_MASK;
_nmPutChunk(ph, pfc);
}
else
{
phead -= (i & ~(size_t)MASK);
pfc = (P_FREE_CHUNK)phead;
sizincl += i;
sizincl &= ~(size_t)MASK;
_nmUnlinkChunk(ph, pfc);
ph->size = sizincl;
HEAD_NOTE(pfc) = sizincl;
FOOT_NOTE(pfc) = sizincl;
HEAD_NOTE(pfc) |= FREE_MASK;
FOOT_NOTE(pfc) |= FREE_MASK;
_nmPutChunk(ph, pfc);
}
return ph;
}
}
/* Function name: nmAllocHeap
* Description: Heap allocation.
* Parameters:
* ph Pointer to heap header.
* size Size in bytes you want to allocate.
* Return value:NULL: Failed.
* Pointer to a heap address: Succeeded.
*/
void * nmAllocHeap(P_HEAP_HEADER ph, size_t size)
{
register size_t i, j, k;
register P_FREE_CHUNK pfc, * ppfc;
if (0 == size)
size = ALIGN;
size = ASIZE(size);
j = _nmCLZ(size) - _nmCLZ(ph->size);
/* Definitely cannot allocate. */
if (j > _nmCLZ(size))
return NULL;
/* Search hash table. */
ppfc = _nmLocateHashTable(ph, j);
pfc = *ppfc;
k = ppfc - (P_FREE_CHUNK *)((PUCHAR)ph + sizeof(HEAP_HEADER));
for (i = 0; i < k; ++i)
{
if (NULL != pfc)
break;
--ppfc;
pfc = *ppfc;
}
/* Search for fit chunk. */
if (NULL != pfc)
{
register P_FREE_CHUNK pofc = pfc;
do
{
if (size > (HEAD_NOTE(pfc) & ~(size_t)MASK))
pfc = pfc->p;
else
break;
} while (pfc != pofc);
}
else
return NULL; /* No available space. */
if (size > (HEAD_NOTE(pfc) & ~(size_t)MASK))
return NULL; /* Cannot find a suitable chunk. */
else /* Cut one chunk. */
{
if (size == (HEAD_NOTE(pfc) & ~(size_t)MASK) || size > (HEAD_NOTE(pfc) & ~(size_t)MASK) - MIN_CHUNK_SIZE)
{ /* No need to split. */
_nmUnlinkChunk(ph, pfc);
/* Set used. */
HEAD_NOTE(pfc) &= USED_MASK;
FOOT_NOTE(pfc) &= USED_MASK;
return pfc;
}
else
{
_nmUnlinkChunk(ph, pfc);
return _nmSplitChunk(ph, pfc, size); /* Split. */
}
}
}
/* Function name: nmFreeHeap
* Description: Heap freedom.
* Parameters:
* ph Pointer to heap header.
* ptr Pointer in heap that you want to free.
* Return value:N/A.
*/
void nmFreeHeap(P_HEAP_HEADER ph, void * ptr)
{
register P_FREE_CHUNK pfc = (P_FREE_CHUNK)ptr;
register bool bbtm = FREE, bhed = FREE;
register size_t upcolsiz, upcolcnt;
register size_t lwcolsiz, lwcolcnt;
register size_t chksiz;
register size_t i;
if (NULL == ptr)
return;
/* Get upper bound. */
if ((PUCHAR)pfc - sizeof(size_t) <= (PUCHAR)ph + HEAP_BEGIN(ph))
bhed = USED;
upcolsiz = 0;
upcolcnt = 0;
do
{
if (FREE == bhed)
{
register size_t t = *(size_t *)((PUCHAR)pfc - 2 * sizeof(size_t));
chksiz = (t & ~(size_t)MASK);
if (FREE == !!(t & (size_t)MASK))
{
pfc = (P_FREE_CHUNK)((PUCHAR)pfc - 2 * sizeof(size_t) - chksiz);
upcolsiz += chksiz;
++upcolcnt;
/* Unlink chunk. */
_nmUnlinkChunk(ph, pfc);
}
else
break;
}
else
break;
if ((PUCHAR)pfc - sizeof(size_t) <= (PUCHAR)ph + HEAP_BEGIN(ph))
bhed = USED;
} while (USED != bhed);
pfc = (P_FREE_CHUNK)ptr;
/* Get lower bound. */
chksiz = HEAD_NOTE(pfc) & ~(size_t)MASK;
if (ASIZE((PUCHAR)pfc + chksiz + sizeof(size_t) - ((PUCHAR)ph + HEAP_BEGIN(ph))) >= ph->size)
bbtm = USED;
lwcolsiz = 0;
lwcolcnt = 0;
while (FREE == bbtm && FREE == !!(*(size_t *)((PUCHAR)pfc + chksiz + sizeof(size_t)) & (size_t)MASK))
{
pfc = (P_FREE_CHUNK)((PUCHAR)pfc + chksiz + 2 * sizeof(size_t));
chksiz = HEAD_NOTE(pfc) & ~(size_t)MASK;
lwcolsiz += chksiz;
++lwcolcnt;
/* Unlink chunk. */
_nmUnlinkChunk(ph, pfc);
if (ASIZE((PUCHAR)pfc + chksiz + sizeof(size_t) - ((PUCHAR)ph + HEAP_BEGIN(ph))) >= ph->size)
bbtm = USED;
}
/* Coalesce up and downward. */
pfc = (P_FREE_CHUNK)ptr;
chksiz = HEAD_NOTE(pfc) & ~(size_t)MASK;
i = upcolsiz + sizeof(size_t) * 2 * upcolcnt;
if (upcolcnt)
pfc = (P_FREE_CHUNK)((PUCHAR)pfc - i);
chksiz += i;
chksiz += lwcolsiz + sizeof(size_t) * 2 * lwcolcnt;
HEAD_NOTE(pfc) = chksiz;
FOOT_NOTE(pfc) = chksiz;
HEAD_NOTE(pfc) |= FREE_MASK;
FOOT_NOTE(pfc) |= FREE_MASK;
/* Put free chunk back into hash table or leave it alone. */
_nmPutChunk(ph, pfc);
}
/* Function name: nmReallocHeap
* Description: Heap reallocation.
* Parameters:
* ph Pointer to heap header.
* ptr Pointer in heap that you want to reallocate.
* size New size of memory chunk.
* Return value:NULL: Reallocation failed.
* Pointer to heap memory: Succeeded.
* Tip: The return value can either be ptr or a new address or NULL.
*/
void * nmReallocHeap(P_HEAP_HEADER ph, void * ptr, size_t size)
{
register size_t i;
register size_t chksiz;
register size_t lwcolsiz, lwcolcnt;
register bool bbtm = FREE;
if (NULL == ptr)
return nmAllocHeap(ph, size);
else if (0 == size)
{
nmFreeHeap(ph, ptr);
return NULL;
}
size = ASIZE(size);
i = _nmCLZ(size) - _nmCLZ(ph->size);
/* Definitely cannot allocate. */
if (i > _nmCLZ(size))
return NULL;
if (size < HEAD_NOTE((P_FREE_CHUNK)ptr))
return _nmSplitChunk(ph, (P_FREE_CHUNK)ptr, size); /* Split. */
else if (size == HEAD_NOTE((P_FREE_CHUNK)ptr))
return ptr;
else /* Try to collect residues. */
{
register P_FREE_CHUNK pfc;
pfc = (P_FREE_CHUNK)ptr;
/* Get lower bound. */
chksiz = HEAD_NOTE(pfc) & ~(size_t)MASK;
if (ASIZE((PUCHAR)pfc + chksiz + sizeof(size_t) - ((PUCHAR)ph + HEAP_BEGIN(ph))) >= ph->size)
bbtm = USED;
lwcolsiz = 0;
lwcolcnt = 0;
while (FREE == bbtm && FREE == !!(*(size_t *)((PUCHAR)pfc + chksiz + sizeof(size_t)) & (size_t)MASK))
{
pfc = (P_FREE_CHUNK)((PUCHAR)pfc + chksiz + 2 * sizeof(size_t));
chksiz = HEAD_NOTE(pfc) & ~(size_t)MASK;
lwcolsiz += chksiz;
++lwcolcnt;
/* Unlink chunk. */
_nmUnlinkChunk(ph, pfc);
if (ASIZE((PUCHAR)pfc + chksiz + sizeof(size_t) - ((PUCHAR)ph + HEAP_BEGIN(ph))) >= ph->size)
bbtm = USED;
}
/* Coalesce downward. */
pfc = (P_FREE_CHUNK)ptr;
chksiz = HEAD_NOTE(pfc) & ~(size_t)MASK;
chksiz += lwcolsiz + sizeof(size_t) * 2 * lwcolcnt;
HEAD_NOTE(pfc) = chksiz;
FOOT_NOTE(pfc) = chksiz;
if (chksiz >= size)
{
HEAD_NOTE(pfc) &= USED_MASK;
FOOT_NOTE(pfc) &= USED_MASK;
if (chksiz - size < MIN_CHUNK_SIZE)
return pfc;
return _nmSplitChunk(ph, (P_FREE_CHUNK)pfc, size); /* Split. */
}
else
{
register void * pr;
pr = nmAllocHeap(ph, size);
if (NULL != pr)
{
memcpy(pr, pfc, sizeof(HEAD_NOTE(pfc)));
_nmPutChunk(ph, pfc);
}
return pr;
}
}
}
```
这是一个内存管理器的实现代码，具体来说是Neo Malloc库的核心源代码文件。
代码注释详细，结构清晰，遵循LGPLv3许可证，允许在开源项目中使用 usr 发表于 2026-1-6 13:10
我建议你看书，你也不看。AyalaRs 的建议你也不采纳，你不是有病是什么？jemalloc你也移植不来小屁孩儿。 ...
哥，告诉我书名，我这就买 0xAA55 发表于 2026-1-9 18:54
哥，告诉我书名，我这就买
CSAPP 深入理解计算机系统 第三版。网上有很多pdf。整本书将近1000页。malloc和1free在9.9章587页。想要高效和缓存友好选择显式空闲链表，chunk块加头尾标记。 usr 发表于 2026-1-10 08:51
CSAPP 深入理解计算机系统 第三版。网上有很多pdf。整本书将近1000页。malloc和1free在9.9章587页。想要 ...
买了。感谢指路。
页:
[1]