C++ 物理内存分配协议：在底层固件开发中利用 C++ 实现基于伙伴系统（Buddy System）的内存管理内核

引言：物理内存管理的基石

各位技术同仁，下午好！今天，我们将深入探讨一个在底层系统开发中至关重要的主题：如何利用 C++ 在固件层面实现一个高效、可靠的物理内存管理内核——基于伙伴系统（Buddy System）的内存分配器。在嵌入式系统、操作系统内核或高性能计算领域，直接管理物理内存是常态。C++ 凭借其强大的抽象能力、零开销原则以及对底层硬件的精细控制，使其成为实现此类内存管理机制的理想选择。

在固件开发中，我们通常没有操作系统提供的虚拟内存抽象，或者需要为操作系统本身提供物理内存管理。这意味着我们必须直接与物理地址打交道，处理内存的分配、释放、对齐以及碎片化等问题。一个设计良好的物理内存分配器是系统稳定性和性能的基石。

为什么选择伙伴系统？

内存分配算法众多，如首次适应（First Fit）、最佳适应（Best Fit）、Slab 分配器等。伙伴系统之所以在底层内存管理中占有一席之地，主要有以下几个原因：

1. 减少外部碎片：伙伴系统通过严格的二的幂次（power-of-2）分配规则，使得相邻的空闲块更容易合并，从而有效缓解了外部碎片问题。
2. 高效的合并与分裂：查找伙伴块、进行合并或分裂操作都非常迅速，通常是 O(log N) 的时间复杂度，其中 N 是内存池的大小。这得益于其结构化的内存管理方式。
3. 实现相对简单：相较于某些更复杂的算法（如 Slab 分配器需要管理多种大小的对象），伙伴系统的核心逻辑更为直观，易于理解和实现。
4. 适用于多种内存请求：它能够有效地处理从非常小到非常大的内存分配请求，具有良好的通用性。

然而，伙伴系统也存在内部碎片的问题，因为即使请求一个很小的内存块，也必须分配一个不小于请求大小的最小的二的幂次块。例如，请求 7KB 内存，会分配一个 8KB 的块，造成 1KB 的内部碎片。在对内存使用极其敏感的场景，可能需要结合其他分配器（如 Slab 或定长分配器）来优化小对象的分配。但作为物理内存管理的核心，伙伴系统无疑是一个强大且实用的选择。

C++ 在底层内存管理中的优势

C++ 提供了以下关键特性，使其在实现底层内存管理时具有无可比拟的优势：

• RAII (Resource Acquisition Is Initialization)：通过构造函数获取资源，析构函数释放资源，可以有效管理内存生命周期，尽管在裸内存管理中，我们更多地是手动调用分配和释放函数。
• 模板和泛型编程：可以创建通用的数据结构和算法，提高代码复用性。
• 面向对象编程：将内存管理器封装成类，提供清晰的接口，便于维护和扩展。
• 低级内存操作：直接操作指针、进行位运算，以及对 new 和 delete 操作符的重载，使得 C++ 能够完全掌控内存。
• 性能：C++ 编译器通常能生成高度优化的机器码，且语言本身提供了对性能敏感的控制能力，如 inline 函数、const 关键字等。

今天，我们将从零开始，构建一个基于伙伴系统的 C++ 内存管理内核，涵盖其原理、数据结构、核心算法及实践中的考量。

伙伴系统核心原理剖析

伙伴系统的核心思想是将一块大的连续物理内存空间递归地分割成更小的、大小为二的幂次的块，直到满足分配请求。当一个块被释放时，它会尝试与其“伙伴”合并，形成一个更大的空闲块。

内存块的二的幂次划分

整个内存池被视为一个初始的、最大订单号（Order）的块。订单号 k 的块大小为 2^k * MIN_BLOCK_SIZE，其中 MIN_BLOCK_SIZE 是系统定义的最小可分配单元。

例如，如果 MIN_BLOCK_SIZE 是 4KB：

• 订单 0 的块大小是 4KB。
• 订单 1 的块大小是 8KB。
• 订单 2 的块大小是 16KB。
• …以此类推。

每次分配请求都会被向上舍入到不小于请求大小的最小二的幂次。例如，请求 5KB，则分配一个订单 1 的 8KB 块。

分裂与合并机制

分裂 (Split)：
当需要一个订单 k 的块，但在订单 k 的空闲链表中找不到时，系统会尝试从订单 k+1 的空闲链表中取出一个块。如果找到，这个订单 k+1 的块会被分裂成两个订单 k 的块。其中一个用于满足当前的分配请求，另一个则被添加到订单 k 的空闲链表中。这个过程可以递归进行，直到找到足够大的块并将其分裂到所需的订单。

合并 (Merge)：
当一个订单 k 的块被释放时，系统会检查其“伙伴”块的状态。一个块的伙伴是指与它大小相同、地址相邻，且地址之和是 2^(k+1) * MIN_BLOCK_SIZE 倍数的另一个块。
如果伙伴块也处于空闲状态，并且它们的订单号相同，那么这两个块就可以合并成一个订单 k+1 的块。这个合并过程同样可以递归进行，直到无法找到空闲伙伴或者达到最大订单号。

空闲链表（Free Lists）的设计

为了高效管理不同订单号的空闲块，伙伴系统通常维护一个空闲链表数组。每个数组元素 free_lists[k] 存储着所有订单 k 的空闲块的链表。

当需要分配一个订单 k 的块时：

1. 首先查找 free_lists[k]。如果非空，直接取出一个块。
2. 如果 free_lists[k] 为空，则查找 free_lists[k+1]。
3. 如果 free_lists[k+1] 非空，取出一个块，分裂成两个订单 k 的块，一个用于分配，另一个加入 free_lists[k]。
4. 如果 free_lists[k+1] 也为空，则继续向上查找 free_lists[k+2]，依此类推，直到找到一个足够大的块进行分裂，或者达到最大订单号仍未找到。

当释放一个订单 k 的块时：

1. 将该块添加到 free_lists[k]。
2. 检查其伙伴块。如果伙伴块也空闲，且在 free_lists[k] 中，则从 free_lists[k] 中移除这两个块，合并成一个订单 k+1 的块，并递归地尝试合并这个新块。

内存状态追踪：元数据管理

伙伴系统需要有效地追踪每个内存块的状态（空闲或已分配）及其订单号。这对于执行分裂、合并以及 free() 操作至关重要。常见的元数据管理策略包括：

1. 块头部 (Block Header)：在每个分配给用户的内存块之前，预留一小块空间存储元数据，如订单号、魔数（用于校验）。这种方法简单直观，但会增加每次分配的开销。
2. 位图 (Bitmap)：使用位图来标记每个最小块的状态（空闲/已分配）。结合辅助数据结构来存储已分配块的订单号。这种方法节省空间，但查找和更新可能稍复杂。
3. 外部数组：维护一个与内存池等大的数组，每个元素对应一个最小块，存储其状态和订单号。当分配一个大块时，只需标记其起始最小块的元数据，其余部分可标记为“被占用”。

在本次实现中，我们将采用一种结合块头部和侵入式链表的策略：

• 对于空闲块，它们将作为侵入式链表节点的一部分，其头部结构仅包含 next 指针。
• 对于已分配块，我们会在返回给用户的地址之前，预留一个 BlockHeader 结构。这个结构将存储该块的订单号，以便在释放时快速确定其大小和伙伴。

订单号与内存大小的对应关系

假设 MIN_BLOCK_SIZE 是 4096 字节 (4KB)，MAX_ORDER 是 10。

订单号 (k)	块大小 (字节)	块大小 (KB)
0	4096	4
1	8192	8
2	16384	16
3	32768	32
4	65536	64
5	131072	128
6	262144	256
7	524288	512
8	1048576	1024 (1MB)
9	2097152	2048 (2MB)
10	4194304	4096 (4MB)

总内存池大小：2^MAX_ORDER * MIN_BLOCK_SIZE。

C++ 实现基础架构

现在，我们开始着手实现伙伴系统。我们将定义一个 BuddyAllocator 类来封装所有逻辑。

内存池的定义与初始化

内存池是一块预先分配好的连续物理内存区域。在固件开发中，这通常是一个静态数组，或者是由引导加载程序（bootloader）传递的物理内存地址和大小。

#include <cstddef> // For size_t
#include <cstdint> // For uintptr_t, uint8_t
#include <cmath>   // For std::log2, std::ceil
#include <new>     // For placement new

// 内存分配器的配置
namespace BuddyConfig {
    // 最小块大小，必须是2的幂次，且至少足以容纳FreeListNode或BlockHeader
    // 这里设置为4KB，通常与页大小一致
    constexpr size_t MIN_BLOCK_SIZE = 4096;
    // 最大订单号。如果总内存是16MB，MIN_BLOCK_SIZE是4KB (2^12)，那么最大块是16MB (2^24)。
    // 2^k * 2^12 = 2^24 => k = 12。所以MAX_ORDER = 12。
    // 假设我们有一个128MB的内存池，MIN_BLOCK_SIZE=4KB (2^12)，
    // 128MB = 2^7 * 1MB = 2^7 * 2^20 Bytes = 2^27 Bytes。
    // 2^k * 2^12 = 2^27 => k = 15。
    // 因此，MAX_ORDER = 15 适用于 128MB 内存池。
    constexpr int MAX_ORDER = 15; // 对应 128MB (2^15 * 4KB)
    constexpr size_t TOTAL_POOL_SIZE = (1ULL << MAX_ORDER) * MIN_BLOCK_SIZE;

    // 确保最小块大小足够容纳链表节点和块头
    static_assert(MIN_BLOCK_SIZE >= sizeof(void*), "MIN_BLOCK_SIZE too small for pointers");
    // 额外的断言，如果BlockHeader包含更多内容，也要考虑
}

// 侵入式空闲链表节点
struct FreeListNode {
    FreeListNode* next;
};

// 分配块的元数据头部，放在用户内存之前
struct BlockHeader {
    uint8_t order; // 块的订单号
    // 其他可能的字段，例如魔数用于调试，或用于双向链表的prev指针
};

// BuddyAllocator 类定义
class BuddyAllocator {
public:
    // 构造函数：需要一块预先分配的物理内存区域
    BuddyAllocator(void* memory_pool_start_addr, size_t memory_pool_size);

    // 初始化分配器
    void initialize();

    // 分配指定大小的内存
    void* allocate(size_t size);

    // 释放之前分配的内存
    void free(void* ptr);

private:
    // 内存池的起始地址和大小
    uintptr_t _pool_start_addr;
    uintptr_t _pool_end_addr;
    size_t _pool_size;

    // 空闲链表数组，每个订单号一个链表
    FreeListNode* _free_lists[BuddyConfig::MAX_ORDER + 1];

    // 辅助函数：将大小转换为订单号
    int _size_to_order(size_t size);

    // 辅助函数：将订单号转换为大小
    size_t _order_to_size(int order);

    // 辅助函数：获取块的伙伴地址
    uintptr_t _get_buddy_address(uintptr_t block_addr, int order);

    // 辅助函数：检查地址是否在内存池范围内
    bool _is_address_in_pool(uintptr_t addr);

    // 辅助函数：从链表中移除指定节点
    void _remove_from_list(FreeListNode* node, int order);

    // 辅助函数：将节点添加到链表头部
    void _add_to_list(FreeListNode* node, int order);

    // 辅助函数：获取给定地址的块头部
    BlockHeader* _get_block_header(void* user_ptr);

    // 辅助函数：获取用户可用的地址 (跳过BlockHeader)
    void* _get_user_ptr(BlockHeader* header);
};

核心数据结构：BuddyAllocator 类

BuddyAllocator 类是整个内存管理器的核心。它包含了内存池的基地址和大小，以及一个 FreeListNode* 数组，用于存储不同订单号的空闲链表。

我们使用 uintptr_t 来处理内存地址，这是一种无符号整数类型，足以存储任何指针的值，便于进行地址算术运算。

空闲链表的具体实现（侵入式链表）

空闲链表采用侵入式链表（Intrusive Linked List）。这意味着链表节点本身就是内存块的一部分，而不是独立的对象。当一个内存块空闲时，它的起始地址会被视为 FreeListNode 结构，其 next 字段指向下一个空闲块。这种方式避免了为链表节点额外分配内存的开销，非常适合底层系统。

// 构造函数实现
BuddyAllocator::BuddyAllocator(void* memory_pool_start_addr, size_t memory_pool_size)
    : _pool_start_addr(reinterpret_cast<uintptr_t>(memory_pool_start_addr)),
      _pool_end_addr(_pool_start_addr + memory_pool_size),
      _pool_size(memory_pool_size)
{
    // 检查内存池大小是否符合伙伴系统要求：必须是MIN_BLOCK_SIZE的倍数，且是2的幂次
    // 更严格地说，必须是 (1ULL << MAX_ORDER) * MIN_BLOCK_SIZE 的倍数
    // 并且初始分配的内存池大小必须与TOTAL_POOL_SIZE匹配
    if (memory_pool_size != BuddyConfig::TOTAL_POOL_SIZE) {
        // 在固件中，这可能是一个致命错误，需要断言或采取其他错误处理
        // 这里简化为打印错误并终止
        // fprintf(stderr, "Error: Memory pool size %zu does not match expected %zun", memory_pool_size, BuddyConfig::TOTAL_POOL_SIZE);
        // abort();
        // 固件中更常见的是直接陷入无限循环或复位
    }

    // 初始化所有空闲链表为空
    for (int i = 0; i <= BuddyConfig::MAX_ORDER; ++i) {
        _free_lists[i] = nullptr;
    }
}

// 初始化分配器
void BuddyAllocator::initialize() {
    // 整个内存池作为一个最大的空闲块添加到对应订单的链表中
    // 确保内存池大小与MAX_ORDER匹配
    int max_order_for_pool = _size_to_order(_pool_size);
    if (max_order_for_pool != BuddyConfig::MAX_ORDER) {
        // 实际的内存池大小与配置的最大订单号不匹配
        // 这通常是一个配置错误
        // fprintf(stderr, "Error: Configured MAX_ORDER does not match actual pool size.n");
        // abort();
    }

    FreeListNode* initial_block = reinterpret_cast<FreeListNode*>(_pool_start_addr);
    initial_block->next = nullptr; // 初始块是链表中唯一的
    _free_lists[max_order_for_pool] = initial_block;
}

// 辅助函数：将大小转换为订单号
int BuddyAllocator::_size_to_order(size_t size) {
    if (size == 0) return 0; // 或者错误处理

    // 向上取整到最小的MIN_BLOCK_SIZE的倍数
    size = (size + BuddyConfig::MIN_BLOCK_SIZE - 1) & ~(BuddyConfig::MIN_BLOCK_SIZE - 1);

    // 再向上取整到最近的2的幂
    size_t aligned_size = 1;
    while (aligned_size < size) {
        aligned_size <<= 1;
    }

    // 计算订单号 k，使得 2^k * MIN_BLOCK_SIZE = aligned_size
    // 2^k = aligned_size / MIN_BLOCK_SIZE
    // k = log2(aligned_size / MIN_BLOCK_SIZE)
    int order = 0;
    if (aligned_size > BuddyConfig::MIN_BLOCK_SIZE) {
        order = static_cast<int>(std::log2(static_cast<double>(aligned_size / BuddyConfig::MIN_BLOCK_SIZE)));
    }

    // 确保订单号不超过MAX_ORDER
    if (order > BuddyConfig::MAX_ORDER) {
        return BuddyConfig::MAX_ORDER;
    }
    return order;
}

// 辅助函数：将订单号转换为大小
size_t BuddyAllocator::_order_to_size(int order) {
    if (order < 0 || order > BuddyConfig::MAX_ORDER) {
        // 错误处理，返回0或抛出异常
        return 0;
    }
    return (1ULL << order) * BuddyConfig::MIN_BLOCK_SIZE;
}

// 辅助函数：获取块的伙伴地址
uintptr_t BuddyAllocator::_get_buddy_address(uintptr_t block_addr, int order) {
    // 伙伴地址的计算：
    // block_addr XOR (1 << order) * MIN_BLOCK_SIZE
    // 这里的 (1 << order) * MIN_BLOCK_SIZE 是块的大小
    // 实际上是 block_addr XOR size
    return block_addr ^ _order_to_size(order);
}

// 辅助函数：检查地址是否在内存池范围内
bool BuddyAllocator::_is_address_in_pool(uintptr_t addr) {
    return addr >= _pool_start_addr && addr < _pool_end_addr;
}

// 辅助函数：从链表中移除指定节点
void BuddyAllocator::_remove_from_list(FreeListNode* node, int order) {
    FreeListNode** current = &_free_lists[order];
    while (*current != nullptr) {
        if (*current == node) {
            *current = node->next;
            return;
        }
        current = &((*current)->next);
    }
    // 如果到这里，说明节点不在链表中，可能是一个错误
}

// 辅助函数：将节点添加到链表头部
void BuddyAllocator::_add_to_list(FreeListNode* node, int order) {
    node->next = _free_lists[order];
    _free_lists[order] = node;
}

// 辅助函数：从用户指针获取块头部
BlockHeader* BuddyAllocator::_get_block_header(void* user_ptr) {
    // 用户指针位于 BlockHeader 之后
    return reinterpret_cast<BlockHeader*>(reinterpret_cast<uintptr_t>(user_ptr) - sizeof(BlockHeader));
}

// 辅助函数：从块头部获取用户可用的地址
void* BuddyAllocator::_get_user_ptr(BlockHeader* header) {
    return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(header) + sizeof(BlockHeader));
}

请注意，_size_to_order 函数中的 std::log2 和 std::ceil 可能在某些极度受限的固件环境中不可用或效率不高。在这种情况下，可以使用位运算来代替：

// 替代的 _size_to_order 函数，避免浮点运算
int BuddyAllocator::_size_to_order(size_t size) {
    if (size == 0) return 0; // 或者错误处理

    // 向上取整到最小的MIN_BLOCK_SIZE的倍数
    // size = (size + BuddyConfig::MIN_BLOCK_SIZE - 1) & ~(BuddyConfig::MIN_BLOCK_SIZE - 1);
    // 实际上，为了兼容BlockHeader，我们需要分配的实际空间是 size + sizeof(BlockHeader)
    size_t total_required_size = size + sizeof(BlockHeader);
    if (total_required_size < BuddyConfig::MIN_BLOCK_SIZE) {
        total_required_size = BuddyConfig::MIN_BLOCK_SIZE;
    }

    // 向上取整到最近的2的幂次
    // 这是一个常见的算法，将所有比最高位低的位都置1，然后加1
    size_t power_of_2_size = total_required_size;
    power_of_2_size--;
    power_of_2_size |= power_of_2_size >> 1;
    power_of_2_size |= power_of_2_size >> 2;
    power_of_2_size |= power_of_2_size >> 4;
    power_of_2_size |= power_of_2_size >> 8;
    power_of_2_size |= power_of_2_size >> 16;
    if (sizeof(size_t) > 4) { // For 64-bit systems
        power_of_2_size |= power_of_2_size >> 32;
    }
    power_of_2_size++;

    // 计算订单号
    int order = 0;
    size_t current_block_size = BuddyConfig::MIN_BLOCK_SIZE;
    while (current_block_size < power_of_2_size && order < BuddyConfig::MAX_ORDER) {
        current_block_size <<= 1;
        order++;
    }
    // 如果计算出来的current_block_size小于power_of_2_size，说明超过了MAX_ORDER，
    // 此时应该返回MAX_ORDER，并让allocate函数处理失败
    if (current_block_size < power_of_2_size) {
        return BuddyConfig::MAX_ORDER + 1; // 标记为超出最大限制，让allocate处理
    }
    return order;
}

这个位运算版本的 _size_to_order 更加适合资源受限的嵌入式环境。

分配操作 allocate() 的实现细节

allocate() 函数是伙伴系统的核心。它的职责是找到一个合适的空闲块，如果需要则进行分裂，然后将其标记为已分配，并返回用户可用的内存地址。

void* BuddyAllocator::allocate(size_t size) {
    // 1. 计算所需的订单号
    int requested_order = _size_to_order(size);

    // 检查请求的订单号是否超出最大限制
    if (requested_order > BuddyConfig::MAX_ORDER) {
        // 请求的内存太大，无法满足
        return nullptr;
    }

    int current_order = requested_order;
    // 2. 向上查找可用的空闲块
    while (current_order <= BuddyConfig::MAX_ORDER && _free_lists[current_order] == nullptr) {
        current_order++;
    }

    // 3. 如果找到的订单号超出了最大限制，说明没有足够的内存
    if (current_order > BuddyConfig::MAX_ORDER) {
        return nullptr; // 内存不足
    }

    // 4. 从找到的空闲链表中取出一个块
    FreeListNode* block_to_allocate = _free_lists[current_order];
    _remove_from_list(block_to_allocate, current_order);

    // 5. 进行分裂操作，直到达到所需的订单号
    while (current_order > requested_order) {
        current_order--; // 订单号减小，块大小减半

        // 分裂为两个伙伴块
        uintptr_t block_addr = reinterpret_cast<uintptr_t>(block_to_allocate);
        uintptr_t buddy_addr = _get_buddy_address(block_addr, current_order);

        // 确定哪个是左伙伴，哪个是右伙伴
        // 约定：将第一个块用于分配，第二个块（伙伴）添加到空闲链表
        FreeListNode* buddy_block = reinterpret_cast<FreeListNode*>(buddy_addr);

        // 确保这两个块是连续的并且位于内存池内
        // 这通常由_get_buddy_address保证，但可以添加断言
        // 重要的是，buddy_block_addr 必须是当前块的伙伴

        // 将伙伴块添加到空闲链表
        _add_to_list(buddy_block, current_order);

        // block_to_allocate 现在是分裂后的左半部分，继续处理它
    }

    // 6. 在块头部存储订单号
    BlockHeader* header = reinterpret_cast<BlockHeader*>(block_to_allocate);
    header->order = requested_order;

    // 7. 返回用户可用的内存地址 (跳过BlockHeader)
    return _get_user_ptr(header);
}

分配流程概览：

1. 计算订单号：根据用户请求的 size，加上 BlockHeader 的大小，并向上取整到最小的二的幂次，然后计算出对应的订单号 requested_order。
2. 向上搜索：从 requested_order 开始，向上遍历 _free_lists 数组，寻找第一个非空的空闲链表。current_order 记录找到的空闲块的订单号。
3. 内存不足判断：如果 current_order 超过 MAX_ORDER 仍然没有找到空闲块，则表示内存不足，返回 nullptr。
4. 取出块：从 _free_lists[current_order] 中取出一个空闲块 block_to_allocate，并将其从链表中移除。
5. 递归分裂：如果 current_order > requested_order，说明取出的块太大了，需要分裂。
   • 将 current_order 减 1。
   • 计算 block_to_allocate 的伙伴地址 buddy_addr。
   • 将 buddy_addr 对应的块（作为 FreeListNode）添加到 _free_lists[current_order] 中。
   • 继续对 block_to_allocate 进行分裂，直到 current_order == requested_order。
6. 存储元数据：在最终分配的块的起始位置，即 block_to_allocate，写入 BlockHeader，存储其订单号 requested_order。
7. 返回地址：返回 BlockHeader 之后的用户可用内存地址。

释放操作 free() 的实现细节

free() 函数负责将已分配的内存块归还给系统，并尝试与伙伴合并以形成更大的空闲块。

void BuddyAllocator::free(void* ptr) {
    if (ptr == nullptr) {
        return; // 释放空指针是安全的无操作
    }

    // 1. 获取块头部和订单号
    BlockHeader* header = _get_block_header(ptr);
    int order = header->order;

    // 验证订单号的合法性 (可选，但推荐用于调试)
    if (order < 0 || order > BuddyConfig::MAX_ORDER) {
        // 错误：无效的订单号，可能是内存损坏
        // fprintf(stderr, "Error: Invalid block order during free: %dn", order);
        // abort();
        return;
    }

    uintptr_t block_addr = reinterpret_cast<uintptr_t>(header);

    // 2. 尝试与伙伴合并
    while (order < BuddyConfig::MAX_ORDER) {
        uintptr_t buddy_addr = _get_buddy_address(block_addr, order);

        // 检查伙伴地址是否在内存池内
        if (!_is_address_in_pool(buddy_addr)) {
            break; // 伙伴不在内存池内，无法合并
        }

        FreeListNode* buddy_node = reinterpret_cast<FreeListNode*>(buddy_addr);

        // 遍历当前订单号的空闲链表，查找伙伴
        bool buddy_is_free = false;
        FreeListNode* current = _free_lists[order];
        while (current != nullptr) {
            if (current == buddy_node) {
                buddy_is_free = true;
                break;
            }
            current = current->next;
        }

        if (buddy_is_free) {
            // 伙伴空闲且在链表中，可以合并
            _remove_from_list(buddy_node, order); // 从链表中移除伙伴

            // 确定合并后新块的起始地址（总是两个伙伴中地址较小的那个）
            block_addr = (block_addr < buddy_addr) ? block_addr : buddy_addr;
            order++; // 订单号增加，块大小翻倍
        } else {
            // 伙伴不空闲或不在链表中，停止合并
            break;
        }
    }

    // 3. 将最终的块添加到对应订单的空闲链表
    FreeListNode* final_block = reinterpret_cast<FreeListNode*>(block_addr);
    _add_to_list(final_block, order);
}

释放流程概览：

1. 获取元数据：根据用户提供的 ptr，回溯到 BlockHeader，从中获取该块的订单号 order。
2. 递归合并：进入循环，尝试向上合并，直到达到最大订单号或无法合并为止。
   • 计算当前块的伙伴地址 buddy_addr。
   • 检查伙伴状态：遍历 _free_lists[order] 链表，检查 buddy_addr 对应的块是否是空闲的且存在于该链表中。
   • 如果可合并：
     • 从 _free_lists[order] 中移除伙伴块。
     • 更新 block_addr 为两个伙伴中地址较小的一个（这决定了合并后新块的起始地址）。
     • order 增加 1。
   • 如果不可合并：跳出循环。
3. 归还最终块：将经过合并后的最终块（由 block_addr 和 order 确定）作为 FreeListNode 添加到 _free_lists[order] 链表的头部。

元数据管理：精巧与高效

在上述实现中，我们采用了在已分配块前置 BlockHeader 的元数据管理策略。这种方式简单直观，但每次分配都会增加 sizeof(BlockHeader) 的开销。对于小块分配，这可能导致较高的内部碎片。

替代方案和优化

1. 位图 (Bitmap) 结合索引数组：

   • 一个位图 status_bitmap，每个位对应一个 MIN_BLOCK_SIZE 的块，表示其是空闲还是已分配。
   • 一个 order_array，每个元素对应 MIN_BLOCK_SIZE 的块，如果该块是某个已分配块的起始，则存储其订单号。否则存储特殊值（如 0xFF）表示其是内部块。
     这种方案可以减少每个块的元数据开销，但 allocate 和 free 中的位图操作会增加复杂性。

2. 伙伴位图 (Buddy Bitmap)：

   • 使用多层位图，每层对应一个订单号，用于标记某个订单号的块是否空闲。这种方案实现更复杂，但可以非常高效地判断伙伴状态。

对于本次讲座的伙伴系统实现，BlockHeader 方案在实现复杂度与性能开销之间取得了较好的平衡，特别是对于固件开发，它提供了一种直接且易于调试的方式来追踪块信息。

BlockHeader 的内存对齐考虑：
BlockHeader 必须足够小，并且能够被它所服务的内存块的对齐要求所容纳。如果用户请求的内存需要 16 字节对齐，那么 BlockHeader + 用户数据也必须是 16 字节对齐。为了简化，我们假设 MIN_BLOCK_SIZE 已经满足了所有可能的对齐要求，并且 sizeof(BlockHeader) 是一个合理的、通常很小的固定值（例如 1 字节或 2 字节用于订单号）。如果 BlockHeader 包含指针或更大的数据类型，那么 MIN_BLOCK_SIZE 必须至少是 sizeof(BlockHeader)。我们目前的 BlockHeader 只包含一个 uint8_t order;，所以其大小是 1 字节。为了保证指针的正确对齐，用户返回的地址必须至少与 sizeof(void*) 对齐。

// 确保BlockHeader本身以及其后的用户数据能够正确对齐
// 在allocate中，我们返回的地址是 header + sizeof(BlockHeader)
// 所以 (uintptr_t)header + sizeof(BlockHeader) 必须满足对齐要求
// 通常，最小块大小MIN_BLOCK_SIZE会保证系统所能支持的最大对齐要求
// 比如 4KB 的页对齐，足以满足 8 字节或 16 字节对齐。
// 因此，只要 BlockHeader 的大小不破坏这种对齐，就没有问题。
// 如果 BlockHeader 大小不是 MIN_BLOCK_SIZE 的因子，或者不是 2 的幂，
// 可能会导致对齐问题，需要额外填充。
// 我们的 BlockHeader 只有 uint8_t，大小为1字节，通常不会破坏对齐，
// 但为了严格，可以将其填充到 sizeof(void*) 的倍数。
struct BlockHeader {
    uint8_t order;
    // 填充以确保BlockHeader的大小是sizeof(void*)的倍数，
    // 以便其后的用户数据能够自然对齐
    uint8_t _padding[sizeof(void*) - sizeof(uint8_t)]; // 假设sizeof(void*)是4或8
};
// 确保BlockHeader的大小是sizeof(void*)的倍数
static_assert(sizeof(BlockHeader) % sizeof(void*) == 0, "BlockHeader size must be a multiple of pointer size for alignment.");

// 更新 BuddyConfig::MIN_BLOCK_SIZE 的断言
static_assert(BuddyConfig::MIN_BLOCK_SIZE >= sizeof(FreeListNode), "MIN_BLOCK_SIZE too small for FreeListNode");
static_assert(BuddyConfig::MIN_BLOCK_SIZE >= sizeof(BlockHeader), "MIN_BLOCK_SIZE too small for BlockHeader");

通过这样的 _padding，我们确保了 sizeof(BlockHeader) 是 sizeof(void*) 的倍数。当 _get_user_ptr 返回地址时，它将是 _get_block_header 返回地址加上一个 sizeof(void*) 的倍数，因此保证了用户数据起始地址的自然对齐。而 MIN_BLOCK_SIZE 已经假定足够大，可以满足更严格的对齐要求（例如 SIMD 指令要求的 16/32/64 字节对齐）。

内存对齐与边界条件

对齐的重要性

现代处理器对内存访问有严格的对齐要求。例如，一个 4 字节的整数通常要求其地址是 4 的倍数。如果访问未对齐的内存，可能会导致性能下降（处理器需要进行多次内存访问或硬件异常）。在固件开发中，未对齐访问可能直接导致程序崩溃或硬件故障。
我们的伙伴系统通过确保所有块大小都是 MIN_BLOCK_SIZE 的倍数（且 MIN_BLOCK_SIZE 通常是处理器字长或页大小的倍数），以及通过 BlockHeader 的填充来保证用户数据起始地址的对齐。

处理越界访问

伙伴系统本身不会阻止用户进行越界访问。这仍然是程序员的责任。然而，通过在 BlockHeader 中存储魔数（Magic Number）等额外信息，可以在 free() 时进行检查，从而在一定程度上检测内存损坏。

// 改进的BlockHeader，增加魔数
struct BlockHeader {
    uint8_t order;
    uint32_t magic; // 魔数，用于检测内存损坏
    // 填充以确保BlockHeader的大小是sizeof(void*)的倍数
    uint8_t _padding[sizeof(void*) - sizeof(uint8_t) - sizeof(uint32_t) % sizeof(void*)];
};
// 确保BlockHeader的大小是sizeof(void*)的倍数
static_assert(sizeof(BlockHeader) % sizeof(void*) == 0, "BlockHeader size must be a multiple of pointer size for alignment.");

// 在allocate中设置魔数
// header->magic = 0xDEADBEEF; // 一个独特的十六进制值

// 在free中检查魔数
// if (header->magic != 0xDEADBEEF) { /* 内存损坏错误 */ }

_padding 的计算需要根据 sizeof(uint8_t) 和 sizeof(uint32_t) 的和来调整，确保最终 sizeof(BlockHeader) 是 sizeof(void*) 的整数倍。

最小分配单元

MIN_BLOCK_SIZE 是伙伴系统能够分配的最小内存块。任何小于这个大小的请求都会被向上舍入到 MIN_BLOCK_SIZE。这保证了所有分配的块都能正确容纳 FreeListNode 或 BlockHeader，并满足基本的内存对齐要求。

集成与应用：让 new/delete 飞起来

在 C++ 中，我们可以通过重载全局的 operator new 和 operator delete 来将我们的 BuddyAllocator 集成到标准库的内存管理中，使得所有使用 new 和 delete 的代码都通过我们的分配器进行内存操作。

// 全局BuddyAllocator实例
// 假设我们有一个静态的内存池
static uint8_t g_memory_pool[BuddyConfig::TOTAL_POOL_SIZE];
static BuddyAllocator g_buddy_allocator(g_memory_pool, BuddyConfig::TOTAL_POOL_SIZE);

// 重载全局的 operator new
void* operator new(std::size_t size) {
    if (size == 0) { // C++17标准要求new(0)返回非空指针
        size = 1;
    }
    void* ptr = g_buddy_allocator.allocate(size);
    if (ptr == nullptr) {
        // 分配失败，根据C++标准，应抛出std::bad_alloc异常
        // 在固件中，通常没有异常处理机制，可能选择打印错误信息并终止
        // 或者返回nullptr，但这违反了new的契约（非throwing new除外）
        // 对于固件，通常会更倾向于一个致命错误处理函数，例如：
        // system_panic("Out of memory!");
        // 或者直接陷入无限循环
        // throw std::bad_alloc(); // 固件中通常禁用异常
        while(1); // 简单粗暴的固件错误处理
    }
    return ptr;
}

// 重载全局的 operator new[]
void* operator new[](std::size_t size) {
    return operator new(size);
}

// 重载全局的 operator delete
void operator delete(void* ptr) noexcept {
    g_buddy_allocator.free(ptr);
}

// 重载全局的 operator delete[]
void operator delete[](void* ptr) noexcept {
    operator delete(ptr);
}

// （可选）重载带有额外参数的new/delete，例如用于指定对齐
// void* operator new(std::size_t size, std::align_val_t align) { ... }
// void operator delete(void* ptr, std::align_val_t align) noexcept { ... }

重要提示：

1. 静态初始化顺序问题 (Static Initialization Order Fiasco)：g_buddy_allocator 和 g_memory_pool 是全局静态对象。它们的初始化顺序在不同编译单元中是不确定的。如果 g_buddy_allocator 在 main 函数之前，某个全局对象的构造函数中使用了 new，那么 g_buddy_allocator 可能尚未被 initialize()。
   解决方案：
   • 将 g_buddy_allocator 和 g_memory_pool 声明为局部静态变量，并在第一次使用时通过函数调用 get_allocator() 来初始化。
   • 在 main 函数的开头显式调用 g_buddy_allocator.initialize()。
   • 在我们的例子中，BuddyAllocator 的构造函数只是设置了地址和大小，真正的初始化（将大块内存放入空闲链表）是在 initialize() 中完成的。所以，需要在 main 函数或系统启动的早期阶段显式调用 g_buddy_allocator.initialize();。
2. 异常处理：在固件中，C++ 异常通常是禁用的（通过编译器选项 -fno-exceptions）。因此，当 allocate 失败时，不能抛出 std::bad_alloc。通常的做法是打印错误信息，然后进入一个死循环或触发系统复位。
3. 内存池的分配：g_memory_pool 是一个静态数组，这模拟了从 BSS 或数据段分配的内存。在实际固件中，这块内存可能是在链接脚本中定义的特定物理地址区域。

使用 Placement New

Placement New 允许你在已分配好的内存上构造对象，而无需再次调用 new 操作符来分配内存。这在内存池或对象池场景中非常有用。

// 假设你已经通过 BuddyAllocator 分配了一块内存
void* buffer = g_buddy_allocator.allocate(sizeof(MyObject));
if (buffer) {
    // 在这块内存上构造 MyObject 对象
    MyObject* obj = new (buffer) MyObject(arg1, arg2);

    // ... 使用 obj ...

    // 显式调用析构函数
    obj->~MyObject();

    // 释放内存
    g_buddy_allocator.free(buffer);
}

使用 Placement New 时，必须手动调用对象的析构函数，因为 delete 操作符不会自动知道对象是在 Placement New 上构造的。

高级议题与性能优化

并发安全性（互斥锁）

当前的 BuddyAllocator 是单线程安全的。在多线程或中断驱动的固件环境中，内存分配和释放操作必须是原子性的。这需要引入互斥锁（Mutex）或其他同步原语。

#include <mutex> // 假设有可用的C++标准库互斥锁，或自定义固件级互斥锁

class BuddyAllocator {
    // ... 其他成员 ...
private:
    std::mutex _mutex; // 保护内存分配器状态的互斥锁
    // ... 其他成员 ...
public:
    void* allocate(size_t size) {
        std::lock_guard<std::mutex> lock(_mutex); // 自动加锁解锁
        // ... 原来的 allocate 逻辑 ...
    }

    void free(void* ptr) {
        std::lock_guard<std::mutex> lock(_mutex); // 自动加锁解锁
        // ... 原来的 free 逻辑 ...
    }
};

在裸金属环境中，std::mutex 可能不可用。你需要实现一个简易的自旋锁（Spinlock）或基于中断禁用/启用的临界区保护机制。

碎片化分析与缓解

• 内部碎片：伙伴系统固有的问题，因为分配的块总是二的幂次。缓解方法包括：
  • 对于小对象，可以结合 Slab 分配器或定长块分配器来减少浪费。
  • 调整 MIN_BLOCK_SIZE 以适应常见的分配请求大小。
• 外部碎片：伙伴系统通过合并机制显著减少了外部碎片，但并非完全消除。如果大部分内存都被大小不一的活动块占用，仍然可能出现无法分配大块内存的情况。

性能度量与调试

• 性能度量：通过测量 allocate 和 free 函数的执行时间来评估性能。在固件中，这可能涉及使用硬件计时器。
• 调试：
  • 魔数：如前所述，在 BlockHeader 中加入魔数，可以在 free() 时检查内存是否被破坏。
  • 边界检查：在分配的块两端加入“保护区”，并在 free() 时检查这些区域是否被修改，以检测缓冲区溢出。
  • 日志/跟踪：在关键操作（分配、释放、分裂、合并）中添加日志输出，帮助理解内存分配行为。
  • 内存映射工具：开发一个简单的工具，可以遍历 BuddyAllocator 的空闲链表和已分配块，生成内存使用情况的可视化报告。

内存池的动态扩展

对于大多数固件系统，内存池通常是固定大小的。如果需要动态扩展，则意味着从更底层的系统（如操作系统或另一个内存区域）获取额外的连续内存块，并将其注册到伙伴系统中。这会增加复杂性，并且在裸金属环境中通常不常见。

代码示例：一个简化但完整的伙伴系统

现在，我们将所有部分整合，提供一个相对完整的 BuddyAllocator 实现。

#include <cstddef> // For size_t
#include <cstdint> // For uintptr_t, uint8_t
#include <cmath>   // For std::log2, std::ceil (optional, can use bitwise)
#include <new>     // For placement new
// #include <mutex> // For concurrency, if available and needed
// #include <cstdio> // For fprintf, for basic error output in a simulated environment

// 内存分配器的配置
namespace BuddyConfig {
    // 最小块大小，必须是2的幂次，且至少足以容纳FreeListNode或BlockHeader
    constexpr size_t MIN_BLOCK_SIZE = 4096; // 4KB

    // 最大订单号。决定了最大可分配块的大小。
    // 如果 MIN_BLOCK_SIZE = 4KB (2^12 Bytes)
    // MAX_ORDER = 15 => 最大块大小 = 2^15 * 4KB = 32 * 4KB = 128MB
    constexpr int MAX_ORDER = 15; 
    constexpr size_t TOTAL_POOL_SIZE = (1ULL << MAX_ORDER) * MIN_BLOCK_SIZE;

    // 确保MIN_BLOCK_SIZE是2的幂次
    static_assert((MIN_BLOCK_SIZE > 0) && ((MIN_BLOCK_SIZE & (MIN_BLOCK_SIZE - 1)) == 0), "MIN_BLOCK_SIZE must be a power of 2");
}

// 侵入式空闲链表节点
struct FreeListNode {
    FreeListNode* next;
};

// 分配块的元数据头部，放在用户内存之前
struct BlockHeader {
    uint8_t order;
    uint32_t magic; // 魔数，用于检测内存损坏，例如0xDEADBEEF
    // 填充以确保BlockHeader的大小是sizeof(void*)的倍数，
    // 以便其后的用户数据能够自然对齐
    uint8_t _padding[
        (sizeof(void*) - (sizeof(uint8_t) + sizeof(uint32_t)) % sizeof(void*)) % sizeof(void*)
    ];
};
// 确保BlockHeader的大小是sizeof(void*)的倍数
static_assert(sizeof(BlockHeader) % sizeof(void*) == 0, "BlockHeader size must be a multiple of pointer size for alignment.");
// 确保最小块大小足以容纳链表节点和块头
static_assert(BuddyConfig::MIN_BLOCK_SIZE >= sizeof(FreeListNode), "MIN_BLOCK_SIZE too small for FreeListNode");
static_assert(BuddyConfig::MIN_BLOCK_SIZE >= sizeof(BlockHeader), "MIN_BLOCK_SIZE too small for BlockHeader");

class BuddyAllocator {
public:
    BuddyAllocator(void* memory_pool_start_addr, size_t memory_pool_size);
    void initialize();
    void* allocate(size_t size);
    void free(void* ptr);

private:
    uintptr_t _pool_start_addr;
    uintptr_t _pool_end_addr;
    size_t _pool_size;
    FreeListNode* _free_lists[BuddyConfig::MAX_ORDER + 1];
    // std::mutex _mutex; // 用于并发安全

    // 辅助函数：将大小转换为订单号
    int _size_to_order(size_t size);
    // 辅助函数：将订单号转换为块实际大小
    size_t _order_to_size(int order);
    // 辅助函数：获取块的伙伴地址
    uintptr_t _get_buddy_address(uintptr_t block_addr, int order);
    // 辅助函数：检查地址是否在内存池范围内
    bool _is_address_in_pool(uintptr_t addr);
    // 辅助函数：从链表中移除指定节点
    void _remove_from_list(FreeListNode* node, int order);
    // 辅助函数：将节点添加到链表头部
    void _add_to_list(FreeListNode* node, int order);
    // 辅助函数：从用户指针获取块头部
    BlockHeader* _get_block_header(void* user_ptr);
    // 辅助函数：从块头部获取用户可用的地址
    void* _get_user_ptr(BlockHeader* header);
};

// BuddyAllocator 构造函数
BuddyAllocator::BuddyAllocator(void* memory_pool_start_addr, size_t memory_pool_size)
    : _pool_start_addr(reinterpret_cast<uintptr_t>(memory_pool_start_addr)),
      _pool_end_addr(_pool_start_addr + memory_pool_size),
      _pool_size(memory_pool_size)
{
    if (memory_pool_size != BuddyConfig::TOTAL_POOL_SIZE) {
        // 实际固件中，这可能是系统崩溃或复位
        // fprintf(stderr, "Error: Memory pool size mismatch. Configured: %zu, Actual: %zun", BuddyConfig::TOTAL_POOL_SIZE, memory_pool_size);
        // while(1); // 致命错误
    }
    for (int i = 0; i <= BuddyConfig::MAX_ORDER; ++i) {
        _free_lists[i] = nullptr;
    }
}

// BuddyAllocator 初始化
void BuddyAllocator::initialize() {
    int max_order_for_pool = _size_to_order(_pool_size); // 这里_size_to_order需要处理 TOTAL_POOL_SIZE
    // 确保 _size_to_order 返回的 order 是 MAX_ORDER 且对应的 size 是 TOTAL_POOL_SIZE
    if (_order_to_size(max_order_for_pool) != _pool_size || max_order_for_pool != BuddyConfig::MAX_ORDER) {
        // 固件中：配置错误，系统崩溃
        // fprintf(stderr, "Error: Initial pool size/order mismatch during initialize.n");
        // while(1);
    }

    FreeListNode* initial_block = reinterpret_cast<FreeListNode*>(_pool_start_addr);
    _add_to_list(initial_block, max_order_for_pool);
}

// 辅助函数：将大小转换为订单号 (使用位运算)
int BuddyAllocator::_size_to_order(size_t size) {
    if (size == 0) return 0;

    // 实际分配空间需要包含BlockHeader
    size_t total_required_size = size + sizeof(BlockHeader);
    if (total_required_size < BuddyConfig::MIN_BLOCK_SIZE) {
        total_required_size = BuddyConfig::MIN_BLOCK_SIZE;
    }

    // 向上取整到最近的2的幂次
    // 这是一个常见的算法，将所有比最高位低的位都置1，然后加1
    size_t power_of_2_size = total_required_size;
    power_of_2_size--;
    power_of_2_size |= power_of_2_size >> 1;
    power_of_2_size |= power_of_2_size >> 2;
    power_of_2_size |= power_of_2_size >> 4;
    power_of_2_size |= power_of_2_size >> 8;
    power_of_2_size |= power_of_2_size >> 16;
    if (sizeof(size_t) > 4) { // For 64-bit systems
        power_of_2_size |= power_of_2_size >> 32;
    }
    power_of_2_size++;

    // 计算订单号
    int order = 0;
    size_t current_block_size = BuddyConfig::MIN_BLOCK_SIZE;
    while (current_block_size < power_of_2_size && order < BuddyConfig::MAX_ORDER) {
        current_block_size <<= 1;
        order++;
    }

    // 如果 power_of_2_size 超过了 MAX_ORDER 对应的最大块大小，
    // 或者 current_block_size 仍然小于 power_of_2_size，返回 MAX_ORDER + 1 表示过大
    if (current_block_size < power_of_2_size || order > BuddyConfig::MAX_ORDER) {
        return BuddyConfig::MAX_ORDER + 1; 
    }
    return order;
}

// 辅助函数：将订单号转换为块实际大小
size_t BuddyAllocator::_order_to_size(int order) {
    if (order < 0 || order > BuddyConfig::MAX_ORDER) {
        // 错误处理
        return 0;
    }
    return (1ULL << order) * BuddyConfig::MIN_BLOCK_SIZE;
}

// 辅助函数：获取块的伙伴地址
uintptr_t BuddyAllocator::_get_buddy_address(uintptr_t block_addr, int order) {
    // 伙伴地址的计算：当前块地址 XOR 块大小
    return block_addr ^ _order_to_size(order);
}

// 辅助函数：检查地址是否在内存池范围内
bool BuddyAllocator::_is_address_in_pool(uintptr_t addr) {
    return addr >= _pool_start_addr && addr < _pool_end_addr;
}

// 辅助函数：从链表中移除指定节点
void BuddyAllocator::_remove_from_list(FreeListNode* node, int order) {
    FreeListNode** current = &_free_lists[order];
    while (*current != nullptr) {
        if (*current == node) {
            *current = node->next;
            return;
        }
        current = &((*current)->next);
    }
    // 错误：节点不在链表中，可能是双重释放或内存损坏
    // fprintf(stderr, "Error: Node %p not found in free list order %d during remove.n", (void*)node, order);
    // while(1);
}

// 辅助函数：将节点添加到链表头部
void BuddyAllocator::_add_to_list(FreeListNode* node, int order) {
    node->next = _free_lists[order];
    _free_lists[order] = node;
}

// 辅助函数：从用户指针获取块头部
BlockHeader* BuddyAllocator::_get_block_header(void* user_ptr) {
    return reinterpret_cast<BlockHeader*>(reinterpret_cast<uintptr_t>(user_ptr) - sizeof(BlockHeader));
}

// 辅助函数：从块头部获取用户可用的地址
void* BuddyAllocator::_get_user_ptr(BlockHeader* header) {
    return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(header) + sizeof(BlockHeader));
}

// BuddyAllocator::allocate 实现
void* BuddyAllocator::allocate(size_t size) {
    // std::lock_guard<std::mutex> lock(_mutex); // 用于并发安全

    int requested_order = _size_to_order(size);
    if (requested_order > BuddyConfig::MAX_ORDER) {
        // fprintf(stderr, "Allocation request size %zu too large. Max order: %dn", size, BuddyConfig::MAX_ORDER);
        return nullptr; // 请求的内存太大
    }

    int current_order = requested_order;
    while (current_order <= BuddyConfig::MAX_ORDER && _free_lists[current_order] == nullptr) {
        current_order++;
    }

    if (current_order > BuddyConfig::MAX_ORDER) {
        // fprintf(stderr, "Out of memory for size %zun", size);
        return nullptr; // 内存不足
    }

    FreeListNode* block_to_allocate = _free_lists[current_order];
    _remove_from_list(block_to_allocate, current_order);

    while (current_order > requested_order) {
        current_order--;
        uintptr_t block_addr = reinterpret_cast<uintptr_t>(block_to_allocate);
        uintptr_t buddy_addr = _get_buddy_address(block_addr, current_order);

        // 将伙伴块添加到空闲链表
        FreeListNode* buddy_block_node = reinterpret_cast<FreeListNode*>(buddy_addr);
        _add_to_list(buddy_block_node, current_order);
    }

    BlockHeader* header = reinterpret_cast<BlockHeader*>(block_to_allocate);
    header->order = requested_order;
    header->magic = 0xDEADBEEF; // 设置魔数

    return _get_user_ptr(header);
}

// BuddyAllocator::free 实现
void BuddyAllocator::free(void* ptr) {
    // std::lock_guard<std::mutex> lock(_mutex); // 用于并发安全

    if (ptr == nullptr) {
        return;
    }

    BlockHeader* header = _get_block_header(ptr);
    // 检查魔数，检测内存损坏
    if (header->magic != 0xDEADBEEF) {
        // fprintf(stderr, "Error: Memory corruption detected at %p (magic mismatch).n", ptr);
        // while(1); // 致命错误
        return;
    }
    // 清除魔数，防止二次释放被误认为是有效块
    header->magic = 0x0; 

    int order = header->order;
    if (order < 0 || order > BuddyConfig::MAX_ORDER) {
        // fprintf(stderr, "Error: Invalid block order %d for %p during free.n", order, ptr);
        // while(1); // 致命错误
        return;
    }

    uintptr_t block_addr = reinterpret_cast<uintptr_t>(header);

    while (order < BuddyConfig::MAX_ORDER) {
        uintptr_t buddy_addr = _get_buddy_address(block_addr, order);

        // 检查伙伴地址是否在内存池内
        if (!_is_address_in_pool(buddy_addr)) {
            break; // 伙伴不在内存池内，无法合并
        }

        // 遍历当前订单号的空闲链表，查找伙伴
        bool buddy_is_free = false;
        FreeListNode* buddy_node_in_list = nullptr;
        FreeListNode* current = _free_lists[order];
        while (current != nullptr) {
            if (reinterpret_cast<uintptr_t>(current) == buddy_addr) {
                buddy_is_free = true;
                buddy_node_in_list = current;
                break;
            }
            current = current->next;
        }

        if (buddy_is_free) {
            // 伙伴空闲且在链表中，可以合并
            _remove_from_list(buddy_node_in_list, order); // 从链表中移除伙伴

            // 确定合并后新块的起始地址（总是两个伙伴中地址较小的那个）
            block_addr = (block_addr < buddy_addr) ? block_addr : buddy_addr;
            order++; // 订单号增加，块大小翻倍
        } else {
            // 伙伴不空闲或不在链表中，停止合并
            break;
        }
    }

    FreeListNode* final_block = reinterpret_cast<FreeListNode*>(block_addr);
    _add_to_list(final_block, order);
}

// 全局内存池和分配器实例
// 注意：实际固件中，g_memory_pool 可能是一个指向特定物理地址的指针
// 并且大小由链接脚本或引导程序确定
static uint8_t g_memory_pool[BuddyConfig::TOTAL_POOL_SIZE];
static BuddyAllocator g_buddy_allocator(g_memory_pool, BuddyConfig::TOTAL_POOL_SIZE);

// 重载全局 operator new/delete
void* operator new(std::size_t size) {
    if (size == 0) size = 1; // C++17 new(0)
    void* ptr = g_buddy_allocator.allocate(size);
    if (ptr == nullptr) {
        // 固件环境通常没有异常，直接陷入错误状态
        // fprintf(stderr, "operator new: Out of memory for size %zun", size);
        while(1); 
    }
    return ptr;
}

void* operator new[](std::size_t size) {
    return operator new(size);
}

void operator delete(void* ptr) noexcept {
    g_buddy_allocator.free(ptr);
}

void operator delete[](void* ptr) noexcept {
    operator delete(ptr);
}

// ------------------- 示例使用 -------------------
#include <iostream> // 模拟环境中使用iostream

struct MyStruct {
    int a;
    char b[10];
    double c;
    MyStruct(int val = 0) : a(val) { std::cout << "MyStruct(" << val << ") constructed at " << this << std::endl; }
    ~MyStruct() { std::cout << "MyStruct(" << a << ") destructed at " << this << std::endl; }
};

int main() {
    // 初始化分配器
    g_buddy_allocator.initialize();
    std::cout << "Buddy Allocator initialized. Total pool size: " 
              << BuddyConfig::TOTAL_POOL_SIZE / (1024 * 1024) << "MB" << std::endl;

    void* p1 = new char[100];
    std::cout << "Allocated 100 bytes: " << p1 << std::endl;

    void* p2 = new int[10]; // 10 * sizeof(int) = 40 bytes
    std::cout << "Allocated 40 bytes (for int[10]): " << p2 << std::endl;

    void* p3 = new MyStruct(42); // sizeof(MyStruct)
    std::cout << "Allocated MyStruct: " << p3 << std::endl;

    void* p4 = new char[BuddyConfig::MIN_BLOCK_SIZE * 2 - sizeof(BlockHeader)]; // Should get order 1 (8KB) block
    std::cout << "Allocated ~8KB: " << p4 << std::endl;

    std::cout << "nFreeing blocks..." << std::endl;
    delete p3;
    delete[] p2;
    delete[] p1;
    delete[] p4;

    std::cout << "nRe-allocating after frees to test merging..." << std::endl;
    void* p5 = new char[BuddyConfig::MIN_BLOCK_SIZE * 3]; // Should get order 2 (16KB) block
    std::cout << "Allocated 12KB (for char[~12KB]): " << p5 << std::endl;
    delete[] p5;

    std::cout << "nTesting large allocation..." << std::endl;
    void* large_block = new char[BuddyConfig::TOTAL_POOL_SIZE / 2 - sizeof(BlockHeader)]; // Allocate half the pool
    if (large_block) {
        std::cout << "Allocated half pool: " << large_block << std::endl;
        delete[] large_block;
    } else {
        std::cout << "Failed to allocate half pool." << std::endl;
    }

    // Example of placement new
    std::cout << "nTesting placement new..." << std::endl;
    void* buffer_for_struct = g_buddy_allocator.allocate(sizeof(MyStruct));
    if (buffer_for_struct) {
        MyStruct* obj_placement = new (buffer_for_struct) MyStruct(99);
        std::cout << "Placement new MyStruct at " << obj_placement << std::endl;
        obj_placement->~MyStruct(); // Manually call destructor
        g_buddy_allocator.free(buffer_for_struct);
        std::cout << "Placement new memory freed." << std::endl;
    } else {
        std::cout << "Failed to allocate buffer for placement new." << std::endl;
    }

    std::cout << "nAll tests complete." << std::endl;

    return 0;
}

请注意，上述代码中的 std::cout 和 fprintf 等输出函数在真实固件环境中可能不可用，需要替换为串口输出或自定义的日志机制。std::mutex 也需要替换为固件平台提供的同步原语。while(1); 是一个常见的固件错误处理策略，表示系统进入不可恢复状态。

物理内存管理的未来与挑战

通过伙伴系统，我们构建了一个高效且适合底层固件的物理内存分配器。然而，内存管理是一个持续演进的领域。未来的挑战可能包括：

• 异构内存管理：在具有多种类型内存（如 SRAM、DDR、Flash）的系统中，如何统一管理它们的分配和使用。
• 安全增强：内存安全漏洞是系统安全的主要来源。如何集成硬件内存保护单元（MPU/MMU）以及更强大的运行时检查机制，以防止内存越界、Use-After-Free 等问题。
• 能效优化：在电池供电的嵌入式设备中，内存访问的能耗是一个重要考量。如何设计分配器以优化缓存利用率和减少内存唤醒次数。
• 实时性保证：对于实时操作系统（RTOS），内存分配和释放必须在确定的时间内完成。如何确保伙伴系统操作的确定性。

这些都是在固件和操作系统内核开发中需要不断探索和解决的问题。掌握伙伴系统等基础内存管理算法，是应对这些挑战的坚实基础。