malloc、calloc、free 和 realloc 的实现 [已关闭]

问：

我试图实现内存分配器，但似乎我没有走在正确的轨道上。预期输出与我得到的输出之间的一些差异似乎与滥用 allignation 有关。代码相对较大，我根本找不到导致行为差异的错误

#include <stddef.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MMAP_THRESHOLD (128 * 1024) 
#define PAGE_SIZE sysconf(_SC_PAGESIZE)

#define DIE(cond, msg) if (cond) { perror(msg); exit(EXIT_FAILURE); }

// Block status
#define STATUS_ALLOCATED 1
#define STATUS_FREE 0
// Block metadata structure
struct block_meta {
    size_t size;
    int status;
    int method;
    struct block_meta *prev;
    struct block_meta *next;
} __attribute__((aligned(8)));  

struct block_meta *heap_start = NULL;
int malloc_count = 0;
void *os_malloc(size_t size);
void *os_calloc(size_t nmemb, size_t size);
void *os_realloc(void *ptr, size_t size);
void os_free(void *ptr);
void coalesce_blocks(struct block_meta *block);
struct block_meta *find_best_block(size_t size);
void split_block(struct block_meta *block, size_t size);

void *brk_malloc(size_t size) {
    struct block_meta *block;
    void *ptr;

    if (size == 0) return NULL;

    size = (size + 7) & (~7); // Align size to 8 bytes

    // Search for a suitable free block
    struct block_meta *free_block = find_best_block(size);

    // If a free block is found, use it
    if (free_block != NULL) {
        split_block(free_block, size);
        return (void *)(free_block + 1);
    }
     ptr = sbrk(size + sizeof(struct block_meta));
    DIE(ptr == (void *)-1, "sbrk");

    block = ptr;
    block->size = size;
    block->status = STATUS_ALLOCATED;

    if (heap_start == NULL) {
        block->prev = NULL;
        block->next = NULL;
        block->method = 0;
        heap_start = block;
    } else {
        block->prev = NULL;
        block->next = heap_start;
        block->method = 0;
        heap_start->prev = block;
        heap_start = block;
    }

    // Coalesce adjacent free blocks
    coalesce_blocks(block);

    return (void *)(block + 1); // Return pointer to the payload
}



// Function to allocate memory using mmap
void *mmap_malloc(size_t size) {
    struct block_meta *block;
    void *ptr;

    if (size == 0) return NULL;

    size = (size + 7) & (~7); // Align size to 8 bytes

    // Use mmap for large allocations
    ptr = mmap(NULL, size + sizeof(struct block_meta), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    DIE(ptr == MAP_FAILED, "mmap");

    block = ptr;
    block->size = size;
    block->method = 1;
    block->status = STATUS_ALLOCATED;
    block->prev = NULL;
    block->next = NULL;

    return (void *)(block + 1); // Return pointer to the payload
}

// Function to allocate memory
void *os_malloc(size_t size) {
    if (size < MMAP_THRESHOLD) {
        return brk_malloc(size);
    } else {
        return mmap_malloc(size);
    }
    malloc_count=1;
}

// Function to allocate zero-initialized memory
void *os_calloc(size_t nmemb, size_t size) {
    // Check for zero arguments
    if (nmemb == 0 || size == 0) return NULL;

    // Allocate memory using os_malloc
    void *ptr = os_malloc(nmemb * size);

    // Initialize the allocated memory to zero
    if (ptr != NULL) {
        memset(ptr, 0, nmemb * size);
    }

    return ptr;
}

// Function to coalesce adjacent free blocks
void coalesce_blocks(struct block_meta *block) {
    while (block->next != NULL && block->next->status == STATUS_FREE) {
        // Check if the next block was allocated using mmap
        if (block->next->method == 1) {
            // If it was allocated using mmap, do not coalesce
            break;
        }

        block->size += block->next->size + sizeof(struct block_meta);
        block->next = block->next->next;

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

// Function to find the best fitting free block
struct block_meta *find_best_block(size_t size) {
    struct block_meta *current = heap_start;
    struct block_meta *best_fit = NULL;

    while (current != NULL) {
    if (current->status == STATUS_FREE && current->size >= size) {
        if (best_fit == NULL || current->size < best_fit->size) {
            best_fit = current;
        }
    }
    current = current->next;
    }


    return best_fit;
}

// Function to split a block into allocated and free parts
// Function to split a block into allocated and free parts
void split_block(struct block_meta *block, size_t size) {
    if (block->size >= size + sizeof(struct block_meta) + 1) {
        // Calculate the new block size, including alignment
        size_t new_size = block->size - size - sizeof(struct block_meta);
        new_size = (new_size + 7) & (~7); // Align size to 8 bytes

        // Calculate the new block pointer, including alignment
        char *new_block_ptr = (char *)(block + 1) + size;
        new_block_ptr = (char *)(((size_t)new_block_ptr + 7) & (~7)); // Align pointer to 8 bytes

        struct block_meta *new_block = (struct block_meta *)new_block_ptr;
        new_block->size = new_size;
        new_block->status = STATUS_FREE;
        new_block->prev = block;
        new_block->next = block->next;

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

        block->size = size;
        block->next = new_block;
    }
}





// Function to reallocate memory
void *os_realloc(void *ptr, size_t size) {
    // Handle special cases
    if (ptr == NULL) return os_malloc(size);
    if (size == 0) {
        os_free(ptr);
        return NULL;
    }

    struct block_meta *block = ((struct block_meta *)ptr);

    if (block->status == STATUS_FREE) {
        return NULL; // Undefined behavior, cannot realloc a free block
    }

    if (block->size >= size) {
        split_block(block, size);
        return ptr;
    }

    struct block_meta *new_block = os_malloc(size);
    if (new_block == NULL) {
        return NULL; // Allocation failed
    }

    memcpy(new_block, ptr, block->size); // Copy data from old block to new block
    os_free(ptr); // Free the old block

    return (void *)(new_block + 1); // Return pointer to the payload of the new block
}

// Function to free allocated memory
void os_free(void *ptr) {
    if (ptr == NULL) return;
    struct block_meta *block = ((struct block_meta *)ptr)-1;

    if (block->status == STATUS_FREE) {
        return; // Double free, ignore
    }
    size_t total_size = block->size + sizeof(struct block_meta);
    if (block->method==1) {
        // This block was allocated using mmap
        munmap(block, total_size);
    } else {
        // This block was allocated using brk
        block->status = STATUS_FREE;
        coalesce_blocks(block);
    }
}