基于Freelist算法的自定义内存分配器实现求助（含代码）

Let's work through refining your implementation step by step. First, let's clarify the core data structure we're using—this is the foundation of the freelist approach:

Block Structure Definition #

Every free block uses a 2-word header:

• The first word (block[0]) stores the total size of the block (in words, including the header itself)
• The second word (block[1]) is a pointer to the next free block in the list

When a block is allocated, we only keep the size header (the first word). The payload starts right after this header, which is what mymalloc returns to the user.

Fixing the mymalloc Function #

Your current implementation has issues with block traversal, size calculation, and missing block-splitting logic. Here's the corrected version with explanations:

#include <iostream>
#include <cstdint>
#include <stdexcept>
#include "pool.h"

const int HEADER_SIZE = 2; // 2 words per free block header
int64_t *freelst = pool();
int64_t *const pool_start = freelist; // Fixed pointer to pool start

// Initialize the freelist if pool() doesn't set up the first block
void init_freelist() {
    if (freelst && *freelst > 0) {
        // Convert pool size from bytes to words (each word = 8 bytes)
        int64_t total_pool_words = *freelst / sizeof(int64_t);
        *freelst = total_pool_words; // Overwrite with size in words
        *(freelst + 1) = 0; // Mark next block as null
    }
}

int64_t *mymalloc(int64_t size) {
    // Handle edge case: zero-size allocation
    if (size <= 0) {
        return 0;
    }

    // Initialize freelist on first call
    static bool initialized = false;
    if (!initialized) {
        init_freelist();
        initialized = true;
    }

    int64_t required_total_size = size + HEADER_SIZE; // Total words (header + payload)
    int64_t *current = freelst;
    int64_t *prev = nullptr;

    // First-fit traversal: find the first block large enough
    while (current != nullptr) {
        if (*current >= required_total_size) {
            break;
        }
        prev = current;
        current = reinterpret_cast<int64_t*>(*(current + 1)); // Move to next free block
    }

    // No suitable block found
    if (current == nullptr) {
        return 0;
    }

    int64_t remaining_size = *current - required_total_size;

    // Case 1: Block is exactly the size we need — remove from freelist
    if (remaining_size < HEADER_SIZE) { // Not enough space for a new free block header
        if (prev == nullptr) {
            freelst = reinterpret_cast<int64_t*>(*(current + 1));
        } else {
            *(prev + 1) = reinterpret_cast<int64_t>(*(current + 1));
        }
        return current + 1; // Return payload address (after header)
    }
    // Case 2: Split the block into allocated and free parts
    else {
        *current = required_total_size; // Shrink current block to needed size
        int64_t *new_free_block = current + required_total_size;
        *new_free_block = remaining_size;
        *(new_free_block + 1) = *(current + 1); // Link to next free block

        // Update freelist to point to the new free block
        if (prev == nullptr) {
            freelst = new_free_block;
        } else {
            *(prev + 1) = reinterpret_cast<int64_t>(new_free_block);
        }

        return current + 1; // Return payload address
    }
}

Key Fixes & Additions: #

• Proper Block Traversal: We use the next pointer (current[1]) to traverse the freelist, instead of incrementing by 1 word.
• Size Calculation: We account for the header size in the required total, so we don't under-allocate.
• Block Splitting: If the found block is larger than needed, we split it into an allocated block and a new free block (only if there's enough space for a new header).
• Freelist Initialization: We convert the pool's byte size to word size and set up the initial freelist node.
• Edge Case Handling: We handle zero-size allocations and empty freelist scenarios.

Fixing the myfree Function #

Your current free logic has incorrect adjacent block checks and flawed insertion/coalescing logic. Here's the corrected version, which properly inserts the block into the sorted freelist and merges adjacent blocks:

void myfree(int64_t *addr) {
    if (addr == nullptr) {
        return;
    }

    // Get the block header (payload address minus 1 word)
    int64_t *block_header = addr - 1;
    int64_t block_size = *block_header;

    // Step 1: Insert the block into the sorted freelist (ascending address order)
    int64_t *current = freelst;
    int64_t *prev = nullptr;

    // Find insertion position: before the first block with a higher address
    while (current != nullptr && current > block_header) {
        prev = current;
        current = reinterpret_cast<int64_t*>(*(current + 1));
    }

    // Link the new block into the list
    if (prev == nullptr) {
        // Insert at the start of the list
        *(block_header + 1) = reinterpret_cast<int64_t>(freelst);
        freelst = block_header;
    } else {
        // Insert between prev and current
        *(block_header + 1) = reinterpret_cast<int64_t>(current);
        *(prev + 1) = reinterpret_cast<int64_t>(block_header);
    }

    // Step 2: Coalesce with adjacent blocks
    // Merge with next block if adjacent
    if (current != nullptr && (block_header + block_size) == current) {
        *block_header += *current;
        *(block_header + 1) = *(current + 1);
        current = reinterpret_cast<int64_t*>(*(block_header + 1));
    }

    // Merge with previous block if adjacent
    if (prev != nullptr && (prev + *prev) == block_header) {
        *prev += *block_header;
        *(prev + 1) = *(block_header + 1);
    }
}

Key Fixes & Additions: #

• Header Retrieval: When freeing, we get back to the block header by subtracting 1 word from the payload address (since mymalloc returns current + 1).
• Sorted Insertion: We traverse the freelist to insert the freed block in ascending address order—critical for proper coalescing.
• Correct Coalescing Logic:
  • Check if the next block is adjacent (current block's end == next block's start) and merge them.
  • Check if the previous block is adjacent (previous block's end == current block's start) and merge them.
• Proper Link Updates: After coalescing, we update freelist pointers to reflect merged blocks.

Critical Testing Notes #

• Verify the pool's initial size is correctly converted from bytes to words (since pool() returns size in bytes as the first word).
• Test edge cases: allocating the entire pool, freeing blocks in random order, merging multiple adjacent blocks, and allocating after multiple frees.
• Use reinterpret_cast for pointer-to-integer casts to avoid undefined behavior.

内容的提问来源于stack exchange，提问作者user12471605