02-实现一个内存分配器¶

// mymalloc.h
#ifndef MYMALLOC_H
#define MYMALLOC_H

#include <stddef.h>
#include <stdbool.h>

// 内存块头部结构（元数据）
typedef struct block_header {
    size_t size;           // 块大小（不包括头部）
    bool is_free;          // 是否空闲
    struct block_header* next;  // 下一个块
} block_header_t;

// 对齐要求（8字节对齐）
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1))

// 块头部大小
#define BLOCK_SIZE ALIGN(sizeof(block_header_t))

// 最小分配大小（避免碎片）
#define MIN_BLOCK_SIZE 16

// 函数声明
void* my_malloc(size_t size);
void my_free(void* ptr);
void* my_calloc(size_t num, size_t size);
void* my_realloc(void* ptr, size_t size);

// 调试函数
void print_heap_status(void);
size_t get_total_allocated(void);
size_t get_total_free(void);

#endif

// mymalloc.c
#include "mymalloc.h"
#include <unistd.h>
#include <string.h>
#include <stdio.h>

// 堆起始位置（静态变量）
static block_header_t* heap_start = NULL;
static block_header_t* free_list = NULL;

// 获取块的数据指针
static void* get_block_payload(block_header_t* block) {
    return (char*)block + BLOCK_SIZE;
}

// 从数据指针获取块头部
static block_header_t* get_block_header(void* ptr) {
    return (block_header_t*)((char*)ptr - BLOCK_SIZE);
}

// 扩展堆空间
static block_header_t* extend_heap(size_t size) {
    // 使用sbrk扩展堆
    void* ptr = sbrk(0);  // 获取当前break位置

    if (sbrk(size + BLOCK_SIZE) == (void*)-1) {
        return NULL;  // sbrk失败
    }

    block_header_t* block = (block_header_t*)ptr;
    block->size = size;
    block->is_free = false;
    block->next = NULL;

    return block;
}

// 在空闲链表中查找合适的块（首次适应）
static block_header_t* find_free_block(size_t size) {
    block_header_t* current = free_list;

    while (current != NULL) {
        if (current->is_free && current->size >= size) {
            return current;
        }
        current = current->next;
    }

    return NULL;
}

// 分割块（如果块太大）
static void split_block(block_header_t* block, size_t size) {
    // 只有当剩余空间足够大时才分割
    if (block->size >= size + BLOCK_SIZE + MIN_BLOCK_SIZE) {
        // 创建新块
        block_header_t* new_block = (block_header_t*)((char*)block + BLOCK_SIZE + size);
        new_block->size = block->size - size - BLOCK_SIZE;
        new_block->is_free = true;
        new_block->next = block->next;

        // 更新原块
        block->size = size;
        block->next = new_block;
    }
}

// 合并相邻的空闲块
static void coalesce_blocks(void) {
    block_header_t* current = heap_start;

    while (current != NULL && current->next != NULL) {
        if (current->is_free && current->next->is_free) {
            // 合并两个块
            current->size += BLOCK_SIZE + current->next->size;
            current->next = current->next->next;
            // 继续检查当前块（可能还可以继续合并）
        } else {
            current = current->next;
        }
    }
}

// 初始化堆
static void init_heap(void) {
    if (heap_start == NULL) {
        // 初始分配一个较大的块
        heap_start = extend_heap(1024);
        if (heap_start != NULL) {
            heap_start->is_free = true;
            free_list = heap_start;
        }
    }
}

// malloc实现
void* my_malloc(size_t size) {
    if (size == 0) {
        return NULL;
    }

    // 对齐大小
    size = ALIGN(size);

    // 确保最小大小
    if (size < MIN_BLOCK_SIZE) {
        size = MIN_BLOCK_SIZE;
    }

    // 初始化堆（首次调用）
    if (heap_start == NULL) {
        init_heap();
    }

    // 在空闲链表中查找
    block_header_t* block = find_free_block(size);

    if (block != NULL) {
        // 找到合适的块
        block->is_free = false;
        split_block(block, size);
        return get_block_payload(block);
    }

    // 没有找到，扩展堆
    block = extend_heap(size);
    if (block == NULL) {
        return NULL;  // 内存不足
    }

    // 将新块加入链表
    block_header_t* current = heap_start;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = block;

    return get_block_payload(block);
}

// free实现
void my_free(void* ptr) {
    if (ptr == NULL) {
        return;
    }

    block_header_t* block = get_block_header(ptr);

    // 检查是否是有效的块
    if (block < heap_start) {
        fprintf(stderr, "Error: Invalid free (before heap start)\n");
        return;
    }

    // 标记为空闲
    block->is_free = true;

    // 尝试合并相邻的空闲块
    coalesce_blocks();
}

// calloc实现
void* my_calloc(size_t num, size_t size) {
    size_t total_size = num * size;
    void* ptr = my_malloc(total_size);

    if (ptr != NULL) {
        memset(ptr, 0, total_size);
    }

    return ptr;
}

// realloc实现
void* my_realloc(void* ptr, size_t size) {
    if (ptr == NULL) {
        return my_malloc(size);
    }

    if (size == 0) {
        my_free(ptr);
        return NULL;
    }

    block_header_t* block = get_block_header(ptr);

    // 如果当前块足够大，直接返回
    if (block->size >= ALIGN(size)) {
        return ptr;
    }

    // 分配新块
    void* new_ptr = my_malloc(size);
    if (new_ptr == NULL) {
        return NULL;
    }

    // 复制数据
    memcpy(new_ptr, ptr, block->size);

    // 释放旧块
    my_free(ptr);

    return new_ptr;
}

// 打印堆状态（调试用）
void print_heap_status(void) {
    printf("\n=== Heap Status ===\n");

    block_header_t* current = heap_start;
    int block_count = 0;
    size_t total_allocated = 0;
    size_t total_free = 0;

    while (current != NULL) {
        printf("Block %d: addr=%p, size=%zu, %s\n",
               block_count,
               (void*)current,
               current->size,
               current->is_free ? "FREE" : "USED");

        if (current->is_free) {
            total_free += current->size;
        } else {
            total_allocated += current->size;
        }

        current = current->next;
        block_count++;
    }

    printf("\nTotal blocks: %d\n", block_count);
    printf("Total allocated: %zu bytes\n", total_allocated);
    printf("Total free: %zu bytes\n", total_free);
    printf("===================\n\n");
}

// 获取已分配内存总量
size_t get_total_allocated(void) {
    size_t total = 0;
    block_header_t* current = heap_start;

    while (current != NULL) {
        if (!current->is_free) {
            total += current->size;
        }
        current = current->next;
    }

    return total;
}

// 获取空闲内存总量
size_t get_total_free(void) {
    size_t total = 0;
    block_header_t* current = heap_start;

    while (current != NULL) {
        if (current->is_free) {
            total += current->size;
        }
        current = current->next;
    }

    return total;
}

// test_mymalloc.c
#include "mymalloc.h"
#include <stdio.h>
#include <string.h>

int main() {
    printf("=== MyMalloc Test ===\n\n");

    // 测试1：基本分配和释放
    printf("Test 1: Basic allocation and free\n");
    void* p1 = my_malloc(100);
    printf("Allocated 100 bytes at %p\n", p1);
    print_heap_status();

    my_free(p1);
    printf("Freed p1\n");
    print_heap_status();

    // 测试2：多次分配
    printf("\nTest 2: Multiple allocations\n");
    void* p2 = my_malloc(50);
    void* p3 = my_malloc(100);
    void* p4 = my_malloc(200);
    printf("Allocated 50, 100, 200 bytes\n");
    print_heap_status();

    // 测试3：中间释放（产生碎片）
    printf("\nTest 3: Middle free (fragmentation)\n");
    my_free(p3);
    printf("Freed p3 (100 bytes)\n");
    print_heap_status();

    // 测试4：重用空闲块
    printf("\nTest 4: Reuse free block\n");
    void* p5 = my_malloc(80);
    printf("Allocated 80 bytes (should reuse p3's block)\n");
    print_heap_status();

    // 测试5：calloc
    printf("\nTest 5: Calloc\n");
    int* arr = my_calloc(10, sizeof(int));
    printf("Allocated array of 10 ints\n");
    printf("arr[0]=%d, arr[5]=%d (should be 0)\n", arr[0], arr[5]);
    print_heap_status();

    // 测试6：realloc
    printf("\nTest 6: Realloc\n");
    arr = my_realloc(arr, 20 * sizeof(int));
    printf("Reallocated array to 20 ints\n");
    print_heap_status();

    // 清理
    my_free(p2);
    my_free(p4);
    my_free(p5);
    my_free(arr);

    printf("\nFinal status:\n");
    print_heap_status();

    printf("\n=== All tests passed! ===\n");
    return 0;
}

#include <sys/mman.h>

#define MMAP_THRESHOLD (128 * 1024)  // 128KB以上使用mmap

static void* allocate_large(size_t size) {
    // 使用mmap分配大块内存
    void* ptr = mmap(NULL, size + BLOCK_SIZE,
                     PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS,
                     -1, 0);

    if (ptr == MAP_FAILED) {
        return NULL;
    }

    block_header_t* block = (block_header_t*)ptr;
    block->size = size;
    block->is_free = false;
    block->next = NULL;

    // 标记为mmap分配的块（需要特殊处理）
    // ...

    return get_block_payload(block);
}

#include <pthread.h>  // 引入头文件

static pthread_mutex_t malloc_lock = PTHREAD_MUTEX_INITIALIZER;

void* my_malloc_thread_safe(size_t size) {
    pthread_mutex_lock(&malloc_lock);
    void* ptr = my_malloc(size);
    pthread_mutex_unlock(&malloc_lock);
    return ptr;
}

void my_free_thread_safe(void* ptr) {
    pthread_mutex_lock(&malloc_lock);
    my_free(ptr);
    pthread_mutex_unlock(&malloc_lock);
}

// 在DEBUG模式下记录分配信息
#ifdef DEBUG
#define MAX_ALLOCATIONS 1000

typedef struct alloc_info {  // struct结构体：自定义复合数据类型
    void* ptr;  // 指针：存储变量的内存地址
    size_t size;
    const char* file;
    int line;
} alloc_info_t;

static alloc_info_t allocations[MAX_ALLOCATIONS];
static int alloc_count = 0;

void* my_malloc_debug(size_t size, const char* file, int line) {
    void* ptr = my_malloc(size);
    if (ptr != NULL && alloc_count < MAX_ALLOCATIONS) {
        allocations[alloc_count].ptr = ptr;
        allocations[alloc_count].size = size;
        allocations[alloc_count].file = file;
        allocations[alloc_count].line = line;
        alloc_count++;
    }
    return ptr;
}

#define my_malloc(size) my_malloc_debug(size, __FILE__, __LINE__)

// 检查内存泄漏
void check_leaks(void) {
    printf("\n=== Memory Leak Check ===\n");
    int leaks = 0;
    for (int i = 0; i < alloc_count; i++) {
        // 检查是否已释放
        block_header_t* block = get_block_header(allocations[i].ptr);
        if (!block->is_free) {
            printf("Leak: %p (%zu bytes) at %s:%d\n",
                   allocations[i].ptr,
                   allocations[i].size,
                   allocations[i].file,
                   allocations[i].line);
            leaks++;
        }
    }
    if (leaks == 0) {
        printf("No memory leaks detected!\n");
    }
    printf("========================\n");
}
#endif