【嵌入式】给 STM32H750 的 D2 内存域设计一个动态内存分配释放器

0xAA55

给 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

#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

#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[0];
}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[0];
}

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()。

AyalaRs

用heap管理那套会不会更好一些,然后单独从一个heap里封装一套malloc

usr

我的建议是你多看看书，csapp上面的内存分配方法比你这好多了。

YY菌

好家伙，直接用死循环来处理异常

0xAA55

YY菌 发表于 2025-12-22 09:15
好家伙，直接用死循环来处理异常

这是嵌入式开发的最常见的做法，在调试器里通过看调用栈来判断是通过哪条路进入了死循环。

AyalaRs

自己管理内存，最好先对内存进行规划，最基本的大块内存和小散的内存先进行分开处理，是否需要初始化等，比如16字节的分块内存池，256字节的分块内存池，多种不同需求应对，分堆管理虽然浪费点内存，但是总比过于耗时的alloc强些

YY菌

0xAA55 发表于 2025-12-29 13:37
这是嵌入式开发的最常见的做法，在调试器里通过看调用栈来判断是通过哪条路进入了死循环。 ...

没有Sleep或者hlt指令吗？

0xAA55

YY菌 发表于 2025-12-30 08:57
没有Sleep或者hlt指令吗？

嵌入式开发比较忌讳依赖特定指令的写法，因为嵌入式开发需要考虑跨平台移植。

AyalaRs

给释放内存做个链表，申请内存的时候记录节点，查找到结尾节点，整理释放内存链表，去除重复和包含项，再从释放内存链表上查找会不会比现在好些，至少内存充足的时候效率非常高

0xAA55

AyalaRs 发表于 2026-1-1 19:02
给释放内存做个链表，申请内存的时候记录节点，查找到结尾节点，整理释放内存链表，去除重复和包含项，再从 ...

我本来想在这种简陋的内存分配的基础上，添加利用二分查找树存储特定大小内存块的方式来加速查找内存块、分配或者合并内存等。实际上感觉非常的多余，因为 288 KB 本来就非常小了，还要在这样的区域上追加东西，又要吃掉一大块。
按现在的逻辑，也就是最简陋的情况下，最坏情况也就是遍历内存一两万次，其实是可以接受的。

AyalaRs

0xAA55 发表于 2026-1-2 16:04
我本来想在这种简陋的内存分配的基础上，添加利用二分查找树存储特定大小内存块的方式来加速查找内存块、 ...

特定大小块可不算好，还不如分堆呢；分堆的可以根据情况选择阶段性释放，整体释放；如果用整体释放，就不用储存每次申请的大小，只需要堆头记录位置就好；资源操作行为不同的方法用统一的接口，除非方法本身还有二级的内存管理系统，否则会出现严重的内存碎片化，特别是长生命周期的内存块中间穿插短生命周期的内存块
... | 长生命周期内存块1 | 短生命周期内存块{1至n个} | 长生命周期内存块2 | ... 当这个释放后申请长生命周期内存块就会出现下面这个问题
... | 长生命周期内存块1 | ...|长生命周期内存块|碎片（大小取决于最小内存申请大小） | 长生命周期内存块2 | ...
如果最小内存申请大小不是1，而且就算最小内存申请大小是1，刚刚申请到碎片化位置的概率也不高，短生命周期不同内存大小属于小问题，长短生命周期内存混杂到一起就会出现这个这个严重问题，如果持续运行几十天之后就会出现无内存分配的情况

usr

0xAA55 发表于 2026-1-6 01:31
如果只是为了解决内存分配的问题，我有必要这么有病地自己造轮子吗？不论看没看过书，内存分配器本来就有 ...

/*
 * 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 MEMORY DIAGRAM]
 * +=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[FCP_PREV] *>-----------/    |
 * |-------------|            ^    |
 * | p[FCP_NEXT] *>-----------/    > 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[FCP_MAX];
} 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[FCP_PREV];
                if (ptr == pfc)
                {
                    register size_t i;

                    pfc->p[FCP_PREV]->p[FCP_NEXT] = pfc->p[FCP_NEXT];
                    pfc->p[FCP_NEXT]->p[FCP_PREV] = pfc->p[FCP_PREV];

                    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[FCP_PREV] = pfc->p[FCP_NEXT] = pfc;
    if (NULL != *ppfc)
    {
        pfc->p[FCP_NEXT] = *ppfc;
        (*ppfc)->p[FCP_PREV]->p[FCP_NEXT] = pfc;
        pfc->p[FCP_PREV] = (*ppfc)->p[FCP_PREV]->p[FCP_PREV];
        (*ppfc)->p[FCP_PREV]->p[FCP_PREV] = 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[FCP_PREV] = fc.p[FCP_NEXT] = 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[FCP_NEXT];
            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;
        }
    }
}

tlwh163

这是一个内存管理器的实现代码，具体来说是Neo Malloc库的核心源代码文件。
代码注释详细，结构清晰，遵循LGPLv3许可证，允许在开源项目中使用

0xAA55

usr 发表于 2026-1-6 13:10
我建议你看书，你也不看。AyalaRs 的建议你也不采纳，你不是有病是什么？jemalloc你也移植不来小屁孩儿。 ...

哥，告诉我书名，我这就买

usr

0xAA55 发表于 2026-1-9 18:54
哥，告诉我书名，我这就买

CSAPP 深入理解计算机系统 第三版。网上有很多pdf。整本书将近1000页。malloc和1free在9.9章587页。想要高效和缓存友好选择显式空闲链表，chunk块加头尾标记。

0xAA55

usr 发表于 2026-1-10 08:51
CSAPP 深入理解计算机系统 第三版。网上有很多pdf。整本书将近1000页。malloc和1free在9.9章587页。想要 ...

买了。感谢指路。