malloc - Not able to merge free blocks together in my simple, custom, memory allocator - Stack Overflow

admin管理员组

文章数量:1122846

I am trying to implement a simple memory allocator. Essentially trying to copy the function malloc() and free(void *ptr) in C.

I initialize a region of memory using sbrk(). In my custom malloc implementation I search the free_list for the first fit of the requested size. I did align the request to a multiple of 8.

here is my implementation of my_malloc alongside the struct to keep in my free list:

typedef struct BLOCK BLOCK;

struct BLOCK {
    size_t size;
    BLOCK *next;
    BLOCK *prev;
    int isFree;
};

static BLOCK *free_list_head = NULL;

size_t get_alignment(size_t user_size) {
    // Example: Align to the nearest 8-byte boundary
    return ((user_size + 7) & ~7); // Align to multiple of 8
}

void* my_malloc(size_t user_size) {
    // Calculate total size with alignment
    size_t alignment = get_alignment(user_size);
    size_t total_size = sizeof(BLOCK) + alignment;

    // Search for a suitable free block
    BLOCK *current = free_list_head;
    while (current != NULL) {
        if (current->size >= total_size) {
            // Found a suitable block
            if (current->size - total_size >= sizeof(BLOCK)) {
                // Split the block if necessary
                BLOCK *new_free_block = (BLOCK*)((char*)current + total_size);
                new_free_block->size = current->size - total_size;
                new_free_block->next = current->next;
                new_free_block->prev = current;
                if (new_free_block->next != NULL) {
                    new_free_block->next->prev = new_free_block;
                }
                current->size = total_size;
            }
            current->isFree = 0;
            return (void*)((char*)current + sizeof(BLOCK));
        }
        current = current->next;
    }

    // No suitable free block found - allocate from heap
    void* ptr = sbrk(total_size);
    if (ptr == (void*)-1) {
        perror("sbrk");
        return NULL;
    }

    // Initialize the BLOCK structure
    BLOCK* block = (BLOCK*)ptr;
    block->size = total_size;
    block->next = NULL;
    block->prev = NULL;
    block->isFree = 0;

    return (void*)((char*)block + sizeof(BLOCK));
}

Finally I have afree(void *ptr) function that not only sets the allocated block to free but also tries to merge adjacent free blocks

void my_free(void* ptr) {
    if (ptr == NULL) {
        return;
    }

    // Get the block header
    BLOCK* block = (BLOCK*)((char*)ptr - sizeof(BLOCK));

    // Mark the block as free
    block->isFree = 1;

    // Coalesce with previous free block
    if (block->prev != NULL && block->prev->isFree) {
        block->prev->size += block->size;
        // Update next pointer of previous block
        block->prev->next = block->next; 
        if (block->next != NULL) {
            block->next->prev = block->prev;
        }
        // No need to update block, as it's now part of the previous block
    } else {
        // If no previous free block, update the free list head if necessary
        if (free_list_head == block) {
            free_list_head = block->next;
            if (free_list_head != NULL) {
                free_list_head->prev = NULL;
            }
        }
    }

    // Coalesce with next free block
    if (block->next != NULL && block->next->isFree) {
        block->size += block->next->size;
        block->next = block->next->next;
        if (block->next != NULL) {
            block->next->prev = block;
        }
    }

    // Insert into free list (if not already part of a larger block)
    if (block->prev == NULL) { 
        // If not already part of a larger block (after coalescing)
        if (free_list_head == NULL) {
            free_list_head = block;
        } else {
            // Insert at the beginning of the list
            block->next = free_list_head;
            free_list_head->prev = block;
            free_list_head = block;
        }
    }
}

I did try and fix my alignment for the size of requested block using the get_alignment(size_t size) as I had originally not implemented it. However I am stuck. here is a sample output of when I am allocating a freeing memory after running the above function:

Initial Free List:
Free List:

Free List after freeing ptr2:
Free List:
Block at 0x733088, size: 88

Free List after freeing ptr1:
Free List:
Block at 0x733000, size: 136
Block at 0x733088, size: 88

Free List after freeing ptr3:
Free List:
Block at 0x7330e0, size: 232
Block at 0x733000, size: 136
Block at 0x733088, size: 88

This is from the main function:

int main() {
    void* ptr1 = my_malloc(100);
    void* ptr2 = my_malloc(50);
    void* ptr3 = my_malloc(200);

    printf("Initial Free List:\n");
    print_free_list();

    my_free(ptr2);

    printf("Free List after freeing ptr2:\n");
    print_free_list();

    my_free(ptr1);

    printf("Free List after freeing ptr1:\n");
    print_free_list();

    my_free(ptr3);

    printf("Free List after freeing ptr3:\n");
    print_free_list();

    return 0;
}

I believe I have the correct implementation for malloc but possibly my logic for merging any alignment for block sizes are wrong

本文标签：