#define MAX_ORDER 11
struct zone {
    ...
struct free_area free_area[MAX_ORDER];
    ...
}
struct free_area {
struct list_head free_list;
/*該組類別塊空閑的個(gè)數(shù)*/
unsigned long nr_free;
};

static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order)
{
    unsigned long page_idx;
    int order_size = 1 << order;
    int migratetype = get_pageblock_migratetype(page);
    /*用PFN作為mem_map數(shù)組下標(biāo)就可以索引到對(duì)應(yīng)的page結(jié)構(gòu)*/
    page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
    __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);

    /*這個(gè)循環(huán)主要查看當(dāng)前釋放塊伙伴是否空閑，如果空閑則合并它們*/
    while (order < MAX_ORDER-1) { 
    unsigned long combined_idx;
    struct page *buddy;
    /*找到釋放塊的伙伴*/
    buddy = __page_find_buddy(page, page_idx, order);
    /*判斷釋放塊的伙伴是否空閑*/
    if (!page_is_buddy(page, buddy, order))
        break;
    list_del(&buddy->lru);
    zone->free_area[order].nr_free--;
    rmv_page_order(buddy);
    combined_idx = __find_combined_index(page_idx, order);
    page = page + (combined_idx - page_idx);
    page_idx = combined_idx;
    order++;

    }

    set_page_order(page, order);
    list_add(&page->lru,
    &zone->free_area[order].free_list[migratetype]);
    zone->free_area[order].nr_free++;
}

//返回申請(qǐng)到的內(nèi)存空間首頁(yè)的struct page結(jié)構(gòu)指針
static struct page *__rmqueue(struct zone *zone, unsigned int order)

{

    struct free_area * area;
    unsigned int current_order;
    struct page *page;
    /*查詢zone中從order到MAX_ORDER-1的各指數(shù)值對(duì)應(yīng)的空閑內(nèi)存區(qū)域*/
    for (current_order = order; current_order < MAX_ORDER; ++current_order) {
    /*連續(xù)2^current_order頁(yè)空閑內(nèi)存區(qū)域的描述結(jié)構(gòu)指針*/
    area = zone->free_area + current_order;
    /*如果該空閑內(nèi)存區(qū)域?yàn)榭眨瑒t繼續(xù)查看2^(current_order+1)頁(yè)空閑內(nèi)存區(qū)域*/
    if (list_empty(&area->free_list))
        continue;

    /*得到該空閑內(nèi)存區(qū)域的首頁(yè)struct page結(jié)構(gòu)指針*/
    page = list_entry(area->free_list.next, struct page, lru);
    /*將page所指的連續(xù)2^current_order頁(yè)的空閑區(qū)域從其所在的鏈表中刪除*/
    list_del(&page->lru);
    rmv_page_order(page);
    area->nr_free--;
    __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
    /*
     *如果分配的內(nèi)存比要申請(qǐng)的內(nèi)存大，則需要把大塊剩余的那一部分
     *分解并放到對(duì)應(yīng)的隊(duì)列中去
     */
    expand(zone, page, order, current_order, area);
    return page;
    }

    return NULL;
}

Node 0, zone      DMA      399    260    123     86     34     31     16     14      7      9    606
Node 0, zone    Normal    1491    1005    233     23     53     28     12     25     9

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <cmath>
#include <memory>

// 內(nèi)存塊狀態(tài)枚舉
enum class MemoryBlockStatus {
    FREE,
    ALLOCATED
};

// 內(nèi)存塊類
class MemoryBlock {
private:
    size_t size_;               // 內(nèi)存塊大小，為2的冪
    size_t address_;            // 內(nèi)存塊起始地址
    MemoryBlockStatus status_;  // 內(nèi)存塊狀態(tài)
    std::string container_id_;  // 分配給哪個(gè)容器
    std::unique_ptr<MemoryBlock> left_child_;  // 左子塊
    std::unique_ptr<MemoryBlock> right_child_; // 右子塊

public:
    // 構(gòu)造函數(shù)
    MemoryBlock(size_t size, size_t address, MemoryBlockStatus status = MemoryBlockStatus::FREE)
        : size_(size), address_(address), status_(status), container_id_("") {}

    // 檢查是否為空閑塊
    bool is_free() const {
        return status_ == MemoryBlockStatus::FREE;
    }

    // 分裂內(nèi)存塊為兩個(gè)相等的子塊
    bool split() {
        if (size_ <= 1) return false;  // 不能再分裂

        size_t half_size = size_ / 2;
        left_child_ = std::make_unique<MemoryBlock>(half_size, address_);
        right_child_ = std::make_unique<MemoryBlock>(half_size, address_ + half_size);
        return true;
    }

    // 獲取內(nèi)存塊信息字符串
    std::string to_string() const {
        std::string status_str;
        if (status_ == MemoryBlockStatus::FREE) {
            status_str = "FREE";
        } else {
            status_str = "ALLOCATED to " + container_id_;
        }
        return "Block(size=" + std::to_string(size_) + ", address=" + std::to_string(address_) + ", " + status_str + ")";
    }

    //  getter和setter方法
    size_t get_size() const { return size_; }
    size_t get_address() const { return address_; }
    MemoryBlockStatus get_status() const { return status_; }
    void set_status(MemoryBlockStatus status) { status_ = status; }
    const std::string& get_container_id() const { return container_id_; }
    void set_container_id(const std::string& id) { container_id_ = id; }
    MemoryBlock* get_left_child() const { return left_child_.get(); }
    MemoryBlock* get_right_child() const { return right_child_.get(); }
    void clear_children() {
        left_child_.reset();
        right_child_.reset();
    }
};

// 伙伴算法內(nèi)存分配器
class BuddyAllocator {
private:
    size_t total_size_;
    std::unique_ptr<MemoryBlock> root_;

    // 查找父塊
    MemoryBlock* find_parent(MemoryBlock* child, MemoryBlock* current) {
        if (!current || !current->get_left_child()) return nullptr;

        if (current->get_left_child() == child || current->get_right_child() == child) {
            return current;
        }

        MemoryBlock* parent = find_parent(child, current->get_left_child());
        if (parent) return parent;

        return find_parent(child, current->get_right_child());
    }

    // 合并內(nèi)存塊
    void merge(MemoryBlock* block) {
        if (!block) return;

        MemoryBlock* parent = find_parent(block, root_.get());
        if (!parent) return;

        MemoryBlock* sibling = (parent->get_left_child() == block) ? 
                              parent->get_right_child() : parent->get_left_child();

        // 如果兄弟塊也是空閑的且沒(méi)有子塊，則合并
        if (sibling && sibling->is_free() && 
            !sibling->get_left_child() && !sibling->get_right_child()) {
            parent->set_status(MemoryBlockStatus::FREE);
            parent->set_container_id("");
            parent->clear_children();
            merge(parent);  // 遞歸向上合并
        }
    }

    // 遞歸計(jì)算已分配內(nèi)存
    size_t count_allocated(MemoryBlock* block) {
        if (!block) return 0;

        if (block->get_status() == MemoryBlockStatus::ALLOCATED) {
            return block->get_size();
        }

        return count_allocated(block->get_left_child()) + count_allocated(block->get_right_child());
    }

    // 遞歸打印內(nèi)存布局
    void print_memory_layout(MemoryBlock* block, int indent) {
        if (!block) return;

        for (int i = 0; i < indent; ++i) {
            std::cout << "  ";
        }
        std::cout << block->to_string() << std::endl;

        print_memory_layout(block->get_left_child(), indent + 1);
        print_memory_layout(block->get_right_child(), indent + 1);
    }

public:
    // 構(gòu)造函數(shù)
    BuddyAllocator(size_t total_memory_size) {
        // 確保總內(nèi)存大小是2的冪
        total_size_ = 1;
        while (total_size_ < total_memory_size) {
            total_size_ <<= 1;
        }
        root_ = std::make_unique<MemoryBlock>(total_size_, 0);
    }

    // 查找適合大小的空閑塊
    MemoryBlock* find_free_block(size_t size, MemoryBlock* block = nullptr) {
        if (!block) block = root_.get();

        // 如果當(dāng)前塊足夠大且空閑，且沒(méi)有子塊，返回它
        if (block->is_free() && block->get_size() >= size && 
            !block->get_left_child() && !block->get_right_child()) {
            return block;
        }

        // 如果有子塊，遞歸查找
        if (block->get_left_child()) {
            MemoryBlock* left_result = find_free_block(size, block->get_left_child());
            if (left_result) return left_result;

            MemoryBlock* right_result = find_free_block(size, block->get_right_child());
            if (right_result) return right_result;
        }

        return nullptr;
    }

    // 分配內(nèi)存
    MemoryBlock* allocate(size_t size, const std::string& container_id) {
        // 計(jì)算最接近的2的冪
        size_t alloc_size = 1;
        while (alloc_size < size) {
            alloc_size <<= 1;
        }

        // 查找合適的塊
        MemoryBlock* block = find_free_block(alloc_size);
        if (!block) return nullptr;

        // 如果塊太大，分裂它
        while (block->get_size() > alloc_size) {
            block->split();
            block = block->get_left_child();  // 使用左子塊
        }

        // 標(biāo)記為已分配
        block->set_status(MemoryBlockStatus::ALLOCATED);
        block->set_container_id(container_id);
        return block;
    }

    // 釋放內(nèi)存塊
    void free(MemoryBlock* block) {
        if (!block || block->is_free()) return;

        block->set_status(MemoryBlockStatus::FREE);
        block->set_container_id("");
        merge(block);
    }

    // 獲取已分配內(nèi)存總量
    size_t get_allocated_memory() {
        return count_allocated(root_.get());
    }

    // 打印內(nèi)存布局
    void print_memory_layout() {
        print_memory_layout(root_.get(), 0);
    }

    size_t get_total_size() const { return total_size_; }
};

// 容器類，表示Kubernetes中的容器
class Container {
private:
    std::string container_id_;
    size_t mem_request_;    // 內(nèi)存請(qǐng)求
    size_t mem_limit_;      // 內(nèi)存限制
    size_t allocated_memory_;  // 當(dāng)前已分配內(nèi)存
    std::vector<MemoryBlock*> blocks_;  // 分配的內(nèi)存塊列表

public:
    // 構(gòu)造函數(shù)
    Container(const std::string& id, size_t request, size_t limit)
        : container_id_(id), mem_request_(request), mem_limit_(limit), allocated_memory_(0) {}

    // 檢查是否可以分配指定大小的內(nèi)存
    bool can_allocate(size_t size) const {
        return allocated_memory_ + size <= mem_limit_;
    }

    // 添加一個(gè)內(nèi)存塊
    void add_memory_block(MemoryBlock* block) {
        if (block) {
            blocks_.push_back(block);
            allocated_memory_ += block->get_size();
        }
    }

    // 移除一個(gè)內(nèi)存塊
    void remove_memory_block(MemoryBlock* block) {
        auto it = std::find(blocks_.begin(), blocks_.end(), block);
        if (it != blocks_.end()) {
            allocated_memory_ -= (*it)->get_size();
            blocks_.erase(it);
        }
    }

    // 獲取容器信息字符串
    std::string to_string() const {
        return "Container(id=" + container_id_ + ", request=" + std::to_string(mem_request_) + 
               ", limit=" + std::to_string(mem_limit_) + ", allocated=" + std::to_string(allocated_memory_) + ")";
    }

    // getter方法
    const std::string& get_id() const { return container_id_; }
    size_t get_mem_request() const { return mem_request_; }
    size_t get_mem_limit() const { return mem_limit_; }
    size_t get_allocated_memory() const { return allocated_memory_; }
    const std::vector<MemoryBlock*>& get_blocks() const { return blocks_; }
};

// Kubernetes內(nèi)存管理器，結(jié)合伙伴算法和Cgroups
class K8sMemoryManager {
private:
    std::unique_ptr<BuddyAllocator> buddy_allocator_;
    std::unordered_map<std::string, std::unique_ptr<Container>> containers_;
    double oom_killer_threshold_;  // OOM殺手觸發(fā)閾值

    // 嘗試為目標(biāo)容器釋放所需內(nèi)存
    bool free_memory_for_container(const std::string& target_container_id, size_t required_size) {
        size_t total_used = buddy_allocator_->get_allocated_memory();
        size_t total_memory = buddy_allocator_->get_total_size();

        // 檢查是否有足夠的空閑內(nèi)存
        if (total_memory - total_used >= required_size) {
            return true;
        }

        // 尋找可以釋放內(nèi)存的容器，優(yōu)先釋放超過(guò)其請(qǐng)求的內(nèi)存
        std::vector<std::pair<size_t, std::string>> candidates;
        for (const auto& [id, container] : containers_) {
            if (id == target_container_id) continue;

            size_t excess = container->get_allocated_memory() - container->get_mem_request();
            if (excess > 0) {
                candidates.emplace_back(excess, id);
            }
        }

        // 按可釋放的內(nèi)存量排序
        std::sort(candidates.begin(), candidates.end(), 
                 [](const auto& a, const auto& b) { return a.first > b.first; });

        // 嘗試釋放內(nèi)存
        size_t freed = 0;
        for (const auto& [excess, id] : candidates) {
            if (freed >= required_size) break;

            size_t to_free = std::min(excess, required_size - freed);
            freed += free_memory(id, to_free);
        }

        return freed >= required_size;
    }

    // 檢查是否需要觸發(fā)OOM killer
    void check_oom_conditions() {
        size_t total_used = buddy_allocator_->get_allocated_memory();
        size_t total_memory = buddy_allocator_->get_total_size();
        double usage_ratio = static_cast<double>(total_used) / total_memory;

        if (usage_ratio < oom_killer_threshold_) return;

        std::cout << "Memory usage high (" << usage_ratio * 100 << "%). Triggering OOM checks..." << std::endl;

        // 找出超出內(nèi)存限制的容器
        std::vector<std::pair<size_t, std::string>> over_limit;
        for (const auto& [id, container] : containers_) {
            if (container->get_allocated_memory() > container->get_mem_limit()) {
                size_t over = container->get_allocated_memory() - container->get_mem_limit();
                over_limit.emplace_back(over, id);
            }
        }

        // 按超出量排序，超出最多的優(yōu)先被終止
        std::sort(over_limit.begin(), over_limit.end(),
                 [](const auto& a, const auto& b) { return a.first > b.first; });

        // 終止超出限制的容器
        for (const auto& [_, id] : over_limit) {
            std::cout << "OOM killer terminating container " << id << std::endl;
            free_memory(id);
            containers_.erase(id);

            // 檢查內(nèi)存使用率是否恢復(fù)正常
            total_used = buddy_allocator_->get_allocated_memory();
            usage_ratio = static_cast<double>(total_used) / total_memory;
            if (usage_ratio < oom_killer_threshold_) break;
        }
    }

public:
    // 構(gòu)造函數(shù)
    K8sMemoryManager(size_t total_memory) 
        : buddy_allocator_(std::make_unique<BuddyAllocator>(total_memory)),
          oom_killer_threshold_(0.9) {}

    // 創(chuàng)建容器并設(shè)置內(nèi)存限制
    void create_container(const std::string& container_id, size_t mem_request, size_t mem_limit) {
        if (containers_.find(container_id) != containers_.end()) {
            throw std::invalid_argument("Container " + container_id + " already exists");
        }

        if (mem_request > mem_limit) {
            throw std::invalid_argument("Memory request cannot exceed memory limit");
        }

        containers_[container_id] = std::make_unique<Container>(container_id, mem_request, mem_limit);
    }

    // 為容器分配內(nèi)存
    bool allocate_memory(const std::string& container_id, size_t size) {
        auto it = containers_.find(container_id);
        if (it == containers_.end()) {
            throw std::invalid_argument("Container " + container_id + " does not exist");
        }

        Container* container = it->second.get();

        // 檢查是否超過(guò)容器內(nèi)存限制
        if (!container->can_allocate(size)) {
            std::cout << "Container " << container_id << " cannot allocate " << size 
                      << " bytes - exceeds memory limit" << std::endl;
            return false;
        }

        // 使用伙伴算法分配內(nèi)存
        MemoryBlock* block = buddy_allocator_->allocate(size, container_id);
        if (!block) {
            // 嘗試釋放一些內(nèi)存
            std::cout << "Memory allocation failed for " << container_id << ". Trying to free memory..." << std::endl;
            if (!free_memory_for_container(container_id, size)) {
                std::cout << "Failed to allocate " << size << " bytes for container " << container_id << std::endl;
                return false;
            }

            // 再次嘗試分配
            block = buddy_allocator_->allocate(size, container_id);
            if (!block) {
                std::cout << "Failed to allocate " << size << " bytes for container " << container_id << std::endl;
                return false;
            }
        }

        container->add_memory_block(block);
        std::cout << "Allocated " << block->get_size() << " bytes to container " << container_id << std::endl;

        // 檢查是否需要觸發(fā)OOM killer
        check_oom_conditions();
        return true;
    }

    // 釋放容器的內(nèi)存
    size_t free_memory(const std::string& container_id, size_t size = 0) {
        auto it = containers_.find(container_id);
        if (it == containers_.end()) {
            throw std::invalid_argument("Container " + container_id + " does not exist");
        }

        Container* container = it->second.get();
        const auto& blocks = container->get_blocks();

        if (blocks.empty()) {
            std::cout << "No allocated memory for container " << container_id << std::endl;
            return 0;
        }

        // 如果指定了大小，嘗試釋放相應(yīng)大小的內(nèi)存
        if (size > 0) {
            size_t freed = 0;
            std::vector<MemoryBlock*> blocks_to_free;

            for (MemoryBlock* block : blocks) {
                if (freed < size) {
                    blocks_to_free.push_back(block);
                    freed += block->get_size();
                } else {
                    break;
                }
            }

            for (MemoryBlock* block : blocks_to_free) {
                container->remove_memory_block(block);
                buddy_allocator_->free(block);
            }

            std::cout << "Freed " << freed << " bytes from container " << container_id << std::endl;
            return freed;
        } else {
            // 釋放所有內(nèi)存
            size_t total_freed = container->get_allocated_memory();
            for (MemoryBlock* block : blocks) {
                buddy_allocator_->free(block);
            }

            // 清除容器的內(nèi)存塊列表
            // 注意：C++中不能直接修改容器的私有成員，這里通過(guò)重新創(chuàng)建容器來(lái)實(shí)現(xiàn)
            containers_[container_id] = std::make_unique<Container>(
                container_id, container->get_mem_request(), container->get_mem_limit()
            );

            std::cout << "Freed all " << total_freed << " bytes from container " << container_id << std::endl;
            return total_freed;
        }
    }

    // 打印系統(tǒng)狀態(tài)
    void print_status() {
        size_t total_used = buddy_allocator_->get_allocated_memory();
        size_t total_memory = buddy_allocator_->get_total_size();

        std::cout << "\n=== System Memory Status ===" << std::endl;
        std::cout << "Total memory: " << total_memory << " bytes" << std::endl;
        std::cout << "Used memory: " << total_used << " bytes (" 
                  << (static_cast<double>(total_used) / total_memory) * 100 << "%)" << std::endl;

        std::cout << "\n=== Containers ===" << std::endl;
        for (const auto& [id, container] : containers_) {
            std::cout << container->to_string() << std::endl;
        }

        std::cout << "\n=== Memory Layout ===" << std::endl;
        buddy_allocator_->print_memory_layout();
        std::cout << "===========================\n" << std::endl;
    }
};

// 主函數(shù)，演示內(nèi)存管理功能
int main() {
    // 創(chuàng)建一個(gè)總內(nèi)存為1024字節(jié)的Kubernetes內(nèi)存管理器
    K8sMemoryManager k8s_manager(1024);

    // 創(chuàng)建幾個(gè)容器，設(shè)置不同的內(nèi)存請(qǐng)求和限制
    try {
        k8s_manager.create_container("app-1", 200, 300);
        k8s_manager.create_container("app-2", 150, 250);
        k8s_manager.create_container("app-3", 100, 200);

        // 為容器分配內(nèi)存
        k8s_manager.allocate_memory("app-1", 150);
        k8s_manager.allocate_memory("app-2", 100);
        k8s_manager.allocate_memory("app-3", 80);

        // 打印當(dāng)前狀態(tài)
        k8s_manager.print_status();

        // 嘗試分配更多內(nèi)存，導(dǎo)致內(nèi)存緊張
        k8s_manager.allocate_memory("app-1", 100);
        k8s_manager.allocate_memory("app-2", 120);

        // 打印狀態(tài)
        k8s_manager.print_status();

        // 再分配更多內(nèi)存，觸發(fā)OOM killer
        k8s_manager.allocate_memory("app-1", 100);

        // 打印最終狀態(tài)
        k8s_manager.print_status();
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}

g++ -std=c++17 k8s_memory_manager.cpp -o k8s_memory_manager

#include <cstddef>
#include <cstdint>
#include <cstring>
#include <algorithm>
#include <new>
#include <stdexcept>

// 嵌入式設(shè)備通常內(nèi)存有限，定義最大內(nèi)存塊大小（可根據(jù)實(shí)際設(shè)備調(diào)整）
const size_t MAX_MEMORY_SIZE = 65536; // 64KB，適合智能手環(huán)等設(shè)備
const size_t MIN_BLOCK_SIZE = 16;     // 最小塊大小，根據(jù)系統(tǒng)需求調(diào)整

// 內(nèi)存塊狀態(tài)
enum class BlockStatus {
    FREE,
    ALLOCATED
};

// 內(nèi)存塊元數(shù)據(jù)結(jié)構(gòu)（盡量緊湊以減少內(nèi)存開(kāi)銷(xiāo)）
struct MemoryBlock {
    size_t size;               // 塊大小（總是2的冪）
    BlockStatus status;        // 塊狀態(tài)
    MemoryBlock* prev;         // 前向指針，用于鏈表管理
    MemoryBlock* next;         // 后向指針，用于鏈表管理
    bool is_split;             // 標(biāo)記塊是否已分裂
    MemoryBlock* left_child;   // 左子塊
    MemoryBlock* right_child;  // 右子塊

    // 內(nèi)存塊頭部大小，用于計(jì)算實(shí)際可用內(nèi)存
    static constexpr size_t header_size() {
        return sizeof(MemoryBlock);
    }
};

// 嵌入式環(huán)境伙伴算法內(nèi)存管理器
class BuddyAllocator {
private:
    uint8_t* memory_pool;      // 內(nèi)存池起始地址
    size_t total_size;         // 總內(nèi)存大小
    MemoryBlock* free_lists;   // 不同大小的空閑塊鏈表數(shù)組
    size_t max_order;          // 最大階數(shù)（log2(total_size)）

    // 計(jì)算階數(shù)（log2）
    size_t get_order(size_t size) const {
        if (size == 0) return 0;
        return 31 - __builtin_clz(size);
    }

    // 找到第一個(gè)大于等于size的2的冪
    size_t round_up_to_power_of_two(size_t size) const {
        if (size <= MIN_BLOCK_SIZE) return MIN_BLOCK_SIZE;
        return 1 << (get_order(size - 1) + 1);
    }

    // 從鏈表中移除塊
    void remove_from_list(MemoryBlock* block, size_t order) {
        if (block->prev) {
            block->prev->next = block->next;
        } else {
            free_lists[order] = block->next;
        }

        if (block->next) {
            block->next->prev = block->prev;
        }
    }

    // 添加塊到鏈表
    void add_to_list(MemoryBlock* block, size_t order) {
        block->prev = nullptr;
        block->next = free_lists[order];
        if (free_lists[order]) {
            free_lists[order]->prev = block;
        }
        free_lists[order] = block;
    }

    // 分裂塊
    MemoryBlock* split_block(MemoryBlock* block, size_t target_order) {
        size_t current_order = get_order(block->size);

        // 從當(dāng)前鏈表移除
        remove_from_list(block, current_order);

        // 分裂直到達(dá)到目標(biāo)階數(shù)
        while (current_order > target_order) {
            current_order--;
            size_t half_size = 1 << current_order;

            // 計(jì)算右子塊地址
            uint8_t* right_block_ptr = reinterpret_cast<uint8_t*>(block) + half_size;
            MemoryBlock* right_block = new (right_block_ptr) MemoryBlock;
            right_block->size = half_size;
            right_block->status = BlockStatus::FREE;
            right_block->is_split = false;
            right_block->left_child = nullptr;
            right_block->right_child = nullptr;

            // 更新當(dāng)前塊作為左子塊
            block->size = half_size;
            block->is_split = true;
            block->right_child = right_block;

            // 將右子塊添加到對(duì)應(yīng)階數(shù)的空閑鏈表
            add_to_list(right_block, current_order);

            // 繼續(xù)分裂左子塊
            block = block;
        }

        // 將最終的左子塊添加到目標(biāo)階數(shù)鏈表
        add_to_list(block, target_order);
        return block;
    }

    // 合并塊
    void merge_blocks(MemoryBlock* block) {
        if (block->status != BlockStatus::FREE || block->size == total_size) {
            return; // 已分配塊或根塊不能合并
        }

        size_t order = get_order(block->size);
        size_t buddy_offset = block->size;

        // 計(jì)算伙伴塊地址
        uint8_t* block_ptr = reinterpret_cast<uint8_t*>(block);
        uint8_t* pool_start = memory_pool;
        size_t block_index = (block_ptr - pool_start) / block->size;

        MemoryBlock* buddy;
        if (block_index % 2 == 0) {
            // 當(dāng)前塊是左伙伴
            buddy = reinterpret_cast<MemoryBlock*>(block_ptr + buddy_offset);
        } else {
            // 當(dāng)前塊是右伙伴
            buddy = reinterpret_cast<MemoryBlock*>(block_ptr - buddy_offset);
        }

        // 檢查伙伴是否可以合并
        if (buddy->status == BlockStatus::FREE && 
            buddy->size == block->size && 
            !buddy->is_split) {

            // 從鏈表中移除兩個(gè)塊
            remove_from_list(block, order);
            remove_from_list(buddy, order);

            // 確定父塊（左塊）
            MemoryBlock* parent = (block_index % 2 == 0) ? block : buddy;
            parent->size *= 2;
            parent->is_split = false;
            parent->left_child = nullptr;
            parent->right_child = nullptr;

            // 添加到更高階的鏈表
            add_to_list(parent, order + 1);

            // 遞歸合并
            merge_blocks(parent);
        }
    }

public:
    // 構(gòu)造函數(shù)，使用指定內(nèi)存池
    BuddyAllocator(void* pool, size_t size) {
        // 確保內(nèi)存大小是2的冪且不超過(guò)最大值
        total_size = round_up_to_power_of_two(size);
        if (total_size > MAX_MEMORY_SIZE) {
            total_size = MAX_MEMORY_SIZE;
        }

        // 如果未提供內(nèi)存池，則在堆上分配
        if (pool == nullptr) {
            memory_pool = new uint8_t[total_size];
        } else {
            memory_pool = static_cast<uint8_t*>(pool);
        }

        // 計(jì)算最大階數(shù)
        max_order = get_order(total_size);

        // 初始化空閑鏈表數(shù)組
        free_lists = new MemoryBlock*[max_order + 1]();

        // 創(chuàng)建初始內(nèi)存塊
        MemoryBlock* initial_block = new (memory_pool) MemoryBlock;
        initial_block->size = total_size;
        initial_block->status = BlockStatus::FREE;
        initial_block->is_split = false;
        initial_block->left_child = nullptr;
        initial_block->right_child = nullptr;

        // 將初始?jí)K添加到最大階數(shù)的空閑鏈表
        add_to_list(initial_block, max_order);
    }

    // 析構(gòu)函數(shù)
    ~BuddyAllocator() {
        delete[] free_lists;
        // 只釋放自己分配的內(nèi)存池
        // 如果是外部提供的內(nèi)存池，則由用戶負(fù)責(zé)釋放
    }

    // 分配內(nèi)存
    void* allocate(size_t size) {
        if (size == 0) return nullptr;

        // 加上塊頭部大小
        size_t total_needed = size + MemoryBlock::header_size();
        if (total_needed > total_size) {
            return nullptr; // 超出總內(nèi)存
        }

        // 計(jì)算所需塊大小和階數(shù)
        size_t block_size = round_up_to_power_of_two(total_needed);
        size_t target_order = get_order(block_size);

        // 尋找合適的塊
        size_t order;
        for (order = target_order; order <= max_order; ++order) {
            if (free_lists[order] != nullptr) {
                break;
            }
        }

        if (order > max_order) {
            return nullptr; // 沒(méi)有足夠大的塊
        }

        // 如果找到的塊大于需要的塊，進(jìn)行分裂
        MemoryBlock* block = free_lists[order];
        if (order > target_order) {
            block = split_block(block, target_order);
        }

        // 從空閑鏈表移除并標(biāo)記為已分配
        remove_from_list(block, target_order);
        block->status = BlockStatus::ALLOCATED;

        // 返回可用內(nèi)存地址（跳過(guò)塊頭部）
        return reinterpret_cast<uint8_t*>(block) + MemoryBlock::header_size();
    }

    // 釋放內(nèi)存
    void deallocate(void* ptr) {
        if (ptr == nullptr) return;

        // 計(jì)算塊頭部地址
        MemoryBlock* block = reinterpret_cast<MemoryBlock*>(
            static_cast<uint8_t*>(ptr) - MemoryBlock::header_size()
        );

        // 檢查塊是否在內(nèi)存池范圍內(nèi)
        uint8_t* block_ptr = reinterpret_cast<uint8_t*>(block);
        if (block_ptr < memory_pool || block_ptr >= memory_pool + total_size) {
            throw std::invalid_argument("Invalid pointer to deallocate");
        }

        // 標(biāo)記為空閑
        block->status = BlockStatus::FREE;
        size_t order = get_order(block->size);

        // 添加到空閑鏈表
        add_to_list(block, order);

        // 嘗試合并
        merge_blocks(block);
    }

    // 獲取內(nèi)存使用統(tǒng)計(jì)
    void get_stats(size_t& total, size_t& used, size_t& free) const {
        total = total_size;

        // 計(jì)算已使用內(nèi)存
        used = 0;
        // 遍歷所有塊（簡(jiǎn)化實(shí)現(xiàn)，實(shí)際嵌入式系統(tǒng)可能需要更高效的統(tǒng)計(jì)方式）
        // 這里使用遞歸方式計(jì)算已分配內(nèi)存
        used = calculate_used(memory_pool);

        free = total - used;
    }

    // 遞歸計(jì)算已使用內(nèi)存
    size_t calculate_used(void* block_ptr) const {
        MemoryBlock* block = static_cast<MemoryBlock*>(block_ptr);

        if (block->status == BlockStatus::ALLOCATED) {
            return block->size;
        }

        if (block->is_split && block->left_child) {
            return calculate_used(block->left_child) + calculate_used(block->right_child);
        }

        return 0;
    }

    // 獲取內(nèi)存池起始地址
    const void* get_memory_pool() const {
        return memory_pool;
    }
};

// 嵌入式任務(wù)基類
class EmbeddedTask {
protected:
    BuddyAllocator& allocator;
    const char* name;
    bool running;

public:
    EmbeddedTask(BuddyAllocator& alloc, const char* task_name)
        : allocator(alloc), name(task_name), running(false) {}

    virtual ~EmbeddedTask() = default;

    virtual void start() {
        running = true;
    }

    virtual void stop() {
        running = false;
    }

    virtual void run() = 0;

    const char* get_name() const {
        return name;
    }

    bool is_running() const {
        return running;
    }
};

// 傳感器數(shù)據(jù)采集任務(wù)（模擬）
class SensorTask : public EmbeddedTask {
private:
    size_t data_buffer_size;
    uint8_t* data_buffer;

public:
    SensorTask(BuddyAllocator& alloc)
        : EmbeddedTask(alloc, "SensorTask"), data_buffer_size(512), data_buffer(nullptr) {}

    void run() override {
        if (!running) return;

        // 分配內(nèi)存用于存儲(chǔ)傳感器數(shù)據(jù)
        data_buffer = static_cast<uint8_t*>(allocator.allocate(data_buffer_size));
        if (data_buffer) {
            // 模擬采集傳感器數(shù)據(jù)
            memset(data_buffer, 0xAA, data_buffer_size);
            printf("SensorTask: Collected data into %zu bytes buffer\n", data_buffer_size);

            // 模擬數(shù)據(jù)處理延遲
            for (volatile int i = 0; i < 100000; i++);

            // 處理完成，釋放內(nèi)存
            allocator.deallocate(data_buffer);
            data_buffer = nullptr;
            printf("SensorTask: Released data buffer\n");
        } else {
            printf("SensorTask: Failed to allocate data buffer\n");
        }
    }
};

// 藍(lán)牙通信任務(wù)（模擬）
class BluetoothTask : public EmbeddedTask {
private:
    size_t packet_size;
    uint8_t* packet_buffer;

public:
    BluetoothTask(BuddyAllocator& alloc)
        : EmbeddedTask(alloc, "BluetoothTask"), packet_size(256), packet_buffer(nullptr) {}

    void run() override {
        if (!running) return;

        // 分配內(nèi)存用于藍(lán)牙數(shù)據(jù)包
        packet_buffer = static_cast<uint8_t*>(allocator.allocate(packet_size));
        if (packet_buffer) {
            // 模擬接收藍(lán)牙數(shù)據(jù)
            memset(packet_buffer, 0xBB, packet_size);
            printf("BluetoothTask: Received data into %zu bytes packet\n", packet_size);

            // 模擬數(shù)據(jù)傳輸延遲
            for (volatile int i = 0; i < 50000; i++);

            // 傳輸完成，釋放內(nèi)存
            allocator.deallocate(packet_buffer);
            packet_buffer = nullptr;
            printf("BluetoothTask: Released packet buffer\n");
        } else {
            printf("BluetoothTask: Failed to allocate packet buffer\n");
        }
    }
};

// 顯示驅(qū)動(dòng)任務(wù)（模擬）
class DisplayTask : public EmbeddedTask {
private:
    size_t frame_buffer_size;
    uint8_t* frame_buffer;

public:
    DisplayTask(BuddyAllocator& alloc)
        : EmbeddedTask(alloc, "DisplayTask"), frame_buffer_size(1024), frame_buffer(nullptr) {}

    void run() override {
        if (!running) return;

        // 分配內(nèi)存用于顯示幀緩沖
        frame_buffer = static_cast<uint8_t*>(allocator.allocate(frame_buffer_size));
        if (frame_buffer) {
            // 模擬繪制顯示內(nèi)容
            memset(frame_buffer, 0xCC, frame_buffer_size);
            printf("DisplayTask: Rendered frame into %zu bytes buffer\n", frame_buffer_size);

            // 模擬顯示刷新延遲
            for (volatile int i = 0; i < 150000; i++);

            // 顯示完成，釋放內(nèi)存
            allocator.deallocate(frame_buffer);
            frame_buffer = nullptr;
            printf("DisplayTask: Released frame buffer\n");
        } else {
            printf("DisplayTask: Failed to allocate frame buffer\n");
        }
    }
};

// 主函數(shù)，模擬嵌入式設(shè)備內(nèi)存管理
int main() {
    // 在嵌入式系統(tǒng)中，這通常是一個(gè)固定的內(nèi)存區(qū)域
    uint8_t memory_pool[MAX_MEMORY_SIZE];

    // 創(chuàng)建伙伴分配器，使用預(yù)分配的內(nèi)存池
    BuddyAllocator allocator(memory_pool, MAX_MEMORY_SIZE);
    printf("Embedded Buddy Allocator initialized with %zu bytes\n", MAX_MEMORY_SIZE);

    // 創(chuàng)建嵌入式任務(wù)
    SensorTask sensor_task(allocator);
    BluetoothTask bt_task(allocator);
    DisplayTask display_task(allocator);

    // 啟動(dòng)任務(wù)
    sensor_task.start();
    bt_task.start();
    display_task.start();

    // 模擬RTOS調(diào)度器，循環(huán)執(zhí)行任務(wù)
    for (int i = 0; i < 5; i++) {
        printf("\n--- Cycle %d ---\n", i + 1);

        // 運(yùn)行傳感器任務(wù)
        sensor_task.run();

        // 運(yùn)行藍(lán)牙任務(wù)
        bt_task.run();

        // 運(yùn)行顯示任務(wù)
        display_task.run();

        // 打印內(nèi)存使用情況
        size_t total, used, free_mem;
        allocator.get_stats(total, used, free_mem);
        printf("Memory stats - Total: %zu, Used: %zu (%.1f%%), Free: %zu (%.1f%%)\n",
               total, used, (float)used/total*100, free_mem, (float)free_mem/total*100);
    }

    // 停止任務(wù)
    sensor_task.stop();
    bt_task.stop();
    display_task.stop();

    printf("\nAll tasks completed\n");
    return 0;
}

g++ -std=c++11 -Os embedded_buddy_allocator.cpp -o embedded_allocator

#include "buddy_allocator.h"
#include <iostream>
#include <cassert>

int main() {
    try {
        // 創(chuàng)建一個(gè)總大小為1MB，最小塊大小為64字節(jié)的伙伴分配器
        BuddyAllocator allocator(1024 * 1024, 64);

        std::cout << "伙伴分配器初始化成功:" << std::endl;
        std::cout << "總內(nèi)存大小: " << allocator.getTotalSize() << " 字節(jié)" << std::endl;
        std::cout << "最小塊大小: " << allocator.getMinBlockSize() << " 字節(jié)" << std::endl;
        std::cout << "階數(shù)數(shù)量: " << allocator.getOrderCount() << std::endl;

        // 測(cè)試內(nèi)存分配和釋放
        void* ptr1 = allocator.allocate(100);
        assert(ptr1 != nullptr);
        std::cout << "\n分配 100 字節(jié)成功: " << ptr1 << std::endl;

        void* ptr2 = allocator.allocate(512);
        assert(ptr2 != nullptr);
        std::cout << "分配 512 字節(jié)成功: " << ptr2 << std::endl;

        void* ptr3 = allocator.allocate(1024);
        assert(ptr3 != nullptr);
        std::cout << "分配 1024 字節(jié)成功: " << ptr3 << std::endl;

        // 釋放內(nèi)存
        allocator.deallocate(ptr1);
        std::cout << "釋放內(nèi)存: " << ptr1 << std::endl;

        allocator.deallocate(ptr2);
        std::cout << "釋放內(nèi)存: " << ptr2 << std::endl;

        // 再次分配，應(yīng)該能重用剛才釋放的內(nèi)存
        void* ptr4 = allocator.allocate(600);
        assert(ptr4 != nullptr);
        std::cout << "再次分配 600 字節(jié)成功: " << ptr4 << std::endl;

        allocator.deallocate(ptr3);
        std::cout << "釋放內(nèi)存: " << ptr3 << std::endl;

        allocator.deallocate(ptr4);
        std::cout << "釋放內(nèi)存: " << ptr4 << std::endl;

        // 測(cè)試分配一個(gè)較大的塊
        void* ptr5 = allocator.allocate(512 * 1024);
        if (ptr5) {
            std::cout << "分配 512KB 成功: " << ptr5 << std::endl;
            allocator.deallocate(ptr5);
            std::cout << "釋放內(nèi)存: " << ptr5 << std::endl;
        } else {
            std::cout << "分配 512KB 失敗" << std::endl;
        }

        std::cout << "\n所有測(cè)試完成" << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "錯(cuò)誤: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}

#ifndef BUDDY_ALLOCATOR_H
#define BUDDY_ALLOCATOR_H

#include <cstddef>
#include <cstdint>
#include <vector>
#include <mutex>

// 伙伴內(nèi)存分配器類
class BuddyAllocator {
public:
    // 構(gòu)造函數(shù)：指定總內(nèi)存大小和最小塊大小
    BuddyAllocator(size_t totalSize, size_t minBlockSize);

    // 析構(gòu)函數(shù)
    ~BuddyAllocator();

    // 分配內(nèi)存塊
    void* allocate(size_t size);

    // 釋放內(nèi)存塊
    void deallocate(void* ptr);

    // 獲取分配器信息
    size_t getTotalSize() const { return m_totalSize; }
    size_t getMinBlockSize() const { return m_minBlockSize; }
    size_t getOrderCount() const { return m_orderCount; }

private:
    // 塊描述符結(jié)構(gòu)
    struct Block {
        bool isFree;       // 塊是否空閑
        size_t order;      // 塊的階數(shù)，塊大小 = minBlockSize * 2^order
        Block* next;       // 下一個(gè)塊（用于空閑鏈表）
        Block* prev;       // 上一個(gè)塊（用于空閑鏈表）

        Block() : isFree(true), order(0), next(nullptr), prev(nullptr) {}
    };

    // 計(jì)算塊大小
    size_t blockSize(size_t order) const { return m_minBlockSize * (1ULL << order); }

    // 計(jì)算給定大小所需的最小階數(shù)
    size_t calculateOrder(size_t size) const;

    // 找到塊的伙伴
    Block* findBuddy(Block* block);

    // 分裂塊
    void split(Block* block, size_t targetOrder);

    // 合并塊
    void merge(Block* block);

    // 從空閑鏈表中移除塊
    void removeFromFreeList(Block* block);

    // 將塊添加到空閑鏈表
    void addToFreeList(Block* block);

    // 轉(zhuǎn)換指針：從塊指針到數(shù)據(jù)指針
    void* blockToData(Block* block) const;

    // 轉(zhuǎn)換指針：從數(shù)據(jù)指針到塊指針
    Block* dataToBlock(void* ptr) const;

    // 檢查指針是否屬于此分配器管理的內(nèi)存
    bool isPointerValid(void* ptr) const;

    size_t m_totalSize;        // 總內(nèi)存大小
    size_t m_minBlockSize;     // 最小塊大小
    size_t m_orderCount;       // 階數(shù)數(shù)量
    uint8_t* m_memoryPool;     // 內(nèi)存池起始地址
    Block* m_blocks;           // 塊描述符數(shù)組
    std::vector<Block*> m_freeLists;  // 空閑塊鏈表，按階數(shù)組織

    // 互斥鎖，確保線程安全
    mutable std::mutex m_mutex;
};

#endif // BUDDY_ALLOCATOR_H

#include "buddy_allocator.h"
#include <cstring>
#include <stdexcept>
#include <iostream>

BuddyAllocator::BuddyAllocator(size_t totalSize, size_t minBlockSize) 
    : m_totalSize(totalSize), m_minBlockSize(minBlockSize) {

    // 檢查最小塊大小是否為2的冪
    if ((minBlockSize & (minBlockSize - 1)) != 0) {
        throw std::invalid_argument("最小塊大小必須是2的冪");
    }

    // 計(jì)算所需的最大階數(shù)
    size_t maxBlockSize = minBlockSize;
    m_orderCount = 0;
    while (maxBlockSize * 2 <= totalSize) {
        maxBlockSize *= 2;
        m_orderCount++;
    }
    m_orderCount++; // 包含maxBlockSize本身

    // 計(jì)算總塊數(shù)
    size_t totalBlocks = 0;
    size_t currentOrder = m_orderCount - 1;
    size_t remainingSize = totalSize;

    while (remainingSize > 0 && currentOrder >= 0) {
        size_t bs = blockSize(currentOrder);
        if (bs <= remainingSize) {
            totalBlocks++;
            remainingSize -= bs;
        } else {
            currentOrder--;
        }
    }

    if (remainingSize > 0) {
        throw std::invalid_argument("總內(nèi)存大小無(wú)法用指定的最小塊大小的2的冪次組合表示");
    }

    // 分配內(nèi)存池：數(shù)據(jù)區(qū) + 塊描述符區(qū)
    size_t descriptorSize = totalBlocks * sizeof(Block);
    m_memoryPool = new uint8_t[totalSize + descriptorSize];
    m_blocks = reinterpret_cast<Block*>(m_memoryPool + totalSize);

    // 初始化塊描述符和空閑鏈表
    m_freeLists.resize(m_orderCount, nullptr);

    // 初始化所有塊
    uint8_t* dataPtr = m_memoryPool;
    remainingSize = totalSize;
    currentOrder = m_orderCount - 1;
    size_t blockIndex = 0;

    while (remainingSize > 0 && currentOrder >= 0) {
        size_t bs = blockSize(currentOrder);
        if (bs <= remainingSize) {
            m_blocks[blockIndex].isFree = true;
            m_blocks[blockIndex].order = currentOrder;
            m_blocks[blockIndex].next = nullptr;
            m_blocks[blockIndex].prev = nullptr;

            // 將塊添加到相應(yīng)的空閑鏈表
            addToFreeList(&m_blocks[blockIndex]);

            dataPtr += bs;
            remainingSize -= bs;
            blockIndex++;
        } else {
            currentOrder--;
        }
    }
}

BuddyAllocator::~BuddyAllocator() {
    delete[] m_memoryPool;
}

void* BuddyAllocator::allocate(size_t size) {
    std::lock_guard<std::mutex> lock(m_mutex);

    // 加上塊頭的大小
    size_t requiredSize = size + sizeof(Block);

    // 計(jì)算所需的階數(shù)
    size_t order = calculateOrder(requiredSize);
    if (order >= m_orderCount) {
        return nullptr; // 無(wú)法滿足分配請(qǐng)求
    }

    // 查找合適的空閑塊
    size_t currentOrder = order;
    while (currentOrder < m_orderCount) {
        if (m_freeLists[currentOrder] != nullptr) {
            // 找到可用塊
            Block* block = m_freeLists[currentOrder];
            removeFromFreeList(block);

            // 如果當(dāng)前塊大于所需，分裂它
            while (currentOrder > order) {
                split(block, currentOrder - 1);
                currentOrder--;
            }

            block->isFree = false;
            return blockToData(block);
        }
        currentOrder++;
    }

    return nullptr; // 沒(méi)有可用塊
}

void BuddyAllocator::deallocate(void* ptr) {
    std::lock_guard<std::mutex> lock(m_mutex);

    if (!ptr || !isPointerValid(ptr)) {
        throw std::invalid_argument("無(wú)效的指針");
    }

    // 轉(zhuǎn)換為塊指針
    Block* block = dataToBlock(ptr);

    if (block->isFree) {
        throw std::invalid_argument("指針已經(jīng)被釋放");
    }

    // 標(biāo)記為空閑
    block->isFree = true;
    addToFreeList(block);

    // 嘗試合并
    merge(block);
}

size_t BuddyAllocator::calculateOrder(size_t size) const {
    if (size == 0) {
        return 0;
    }

    size_t order = 0;
    size_t currentSize = m_minBlockSize;

    while (currentSize < size && order < m_orderCount - 1) {
        currentSize *= 2;
        order++;
    }

    return order;
}

BuddyAllocator::Block* BuddyAllocator::findBuddy(Block* block) {
    // 計(jì)算塊在內(nèi)存池中的偏移量
    size_t blockSize = blockSize(block->order);
    size_t blockOffset = reinterpret_cast<uint8_t*>(blockToData(block)) - m_memoryPool;

    // 計(jì)算伙伴塊的偏移量
    size_t buddyOffset = (blockOffset ^ blockSize);

    // 檢查伙伴塊是否在內(nèi)存池范圍內(nèi)
    if (buddyOffset >= m_totalSize) {
        return nullptr;
    }

    // 查找伙伴塊的描述符
    uint8_t* buddyData = m_memoryPool + buddyOffset;
    return dataToBlock(buddyData);
}

void BuddyAllocator::split(Block* block, size_t targetOrder) {
    if (block->order <= targetOrder) {
        return; // 不需要分裂
    }

    size_t currentOrder = block->order;
    Block* first = block;

    // 找到第二個(gè)塊
    size_t halfSize = blockSize(currentOrder - 1);
    uint8_t* secondData = reinterpret_cast<uint8_t*>(blockToData(first)) + halfSize;
    Block* second = dataToBlock(secondData);

    // 更新塊信息
    first->order = currentOrder - 1;
    second->order = currentOrder - 1;
    second->isFree = true;

    // 將兩個(gè)塊添加到空閑鏈表
    addToFreeList(first);
    addToFreeList(second);
}

void BuddyAllocator::merge(Block* block) {
    size_t currentOrder = block->order;

    // 只能合并到最大階數(shù)
    while (currentOrder < m_orderCount - 1) {
        Block* buddy = findBuddy(block);

        // 檢查伙伴是否存在、空閑且同階
        if (!buddy || !buddy->isFree || buddy->order != currentOrder) {
            break;
        }

        // 從空閑鏈表中移除當(dāng)前塊和伙伴塊
        removeFromFreeList(block);
        removeFromFreeList(buddy);

        // 確定合并后的父塊
        Block* parent = block;
        size_t blockOffset = reinterpret_cast<uint8_t*>(blockToData(block)) - m_memoryPool;
        size_t buddyOffset = reinterpret_cast<uint8_t*>(blockToData(buddy)) - m_memoryPool;

        if (buddyOffset < blockOffset) {
            parent = buddy;
        }

        // 更新父塊信息
        parent->order = currentOrder + 1;
        parent->isFree = true;

        // 將父塊添加到空閑鏈表
        addToFreeList(parent);

        // 繼續(xù)嘗試合并更大的塊
        block = parent;
        currentOrder++;
    }
}

void BuddyAllocator::removeFromFreeList(Block* block) {
    size_t order = block->order;

    if (block->prev) {
        block->prev->next = block->next;
    } else {
        // 是鏈表頭
        m_freeLists[order] = block->next;
    }

    if (block->next) {
        block->next->prev = block->prev;
    }

    block->next = nullptr;
    block->prev = nullptr;
}

void BuddyAllocator::addToFreeList(Block* block) {
    size_t order = block->order;

    // 添加到鏈表頭部
    block->next = m_freeLists[order];
    block->prev = nullptr;

    if (m_freeLists[order]) {
        m_freeLists[order]->prev = block;
    }

    m_freeLists[order] = block;
}

void* BuddyAllocator::blockToData(Block* block) const {
    // 計(jì)算塊索引
    size_t blockIndex = block - m_blocks;

    // 找到該塊在內(nèi)存池中的數(shù)據(jù)區(qū)起始地址
    uint8_t* dataPtr = m_memoryPool;
    size_t remainingSize = m_totalSize;

    for (size_t i = 0; i < blockIndex; i++) {
        size_t bs = blockSize(m_blocks[i].order);
        dataPtr += bs;
        remainingSize -= bs;
    }

    return dataPtr;
}

BuddyAllocator::Block* BuddyAllocator::dataToBlock(void* ptr) const {
    uint8_t* dataPtr = reinterpret_cast<uint8_t*>(ptr);

    // 計(jì)算數(shù)據(jù)指針在內(nèi)存池中的偏移量
    size_t offset = dataPtr - m_memoryPool;
    if (offset >= m_totalSize) {
        return nullptr;
    }

    // 查找對(duì)應(yīng)的塊描述符
    uint8_t* currentPtr = m_memoryPool;
    for (size_t i = 0; ; i++) {
        size_t bs = blockSize(m_blocks[i].order);
        if (dataPtr >= currentPtr && dataPtr < currentPtr + bs) {
            return &m_blocks[i];
        }
        currentPtr += bs;
    }
}

bool BuddyAllocator::isPointerValid(void* ptr) const {
    uint8_t* dataPtr = reinterpret_cast<uint8_t*>(ptr);
    return (dataPtr >= m_memoryPool && dataPtr < m_memoryPool + m_totalSize);
}