Implementing malloc() and free() — merging small blocks

This post builds upon the previous one, addressing memory fragmentation in a custom memory allocator. The core issue is that repeatedly allocating and freeing small blocks creates many small, unusable gaps in memory, preventing larger allocations even when sufficient total free space exists. This article details a solution: merging adjacent free blocks.

The Problem: Memory Fragmentation

The author illustrates fragmentation with a code example and diagrams. Small allocations followed by deallocations leave behind fragmented free space. Subsequent larger allocations fail because no single free block is large enough, even though the combined free space exceeds the request. The diagrams visually demonstrate this problem, showing how small, freed blocks prevent efficient reuse of larger free areas.

The Solution: Merging Adjacent Free Blocks

The solution involves merging adjacent free blocks to create larger, usable chunks of memory. The author refactors the code for improved readability and reuse, introducing several helper functions:

• header_user_area(Header *header): Returns a pointer to the user-accessible memory area within a block.
• header_address_after_block(Header *header): Returns a pointer to the memory location immediately following the block.
• header_previous_available(Header *header): Checks if the previous block is free.
• header_next_available(Header *header): Checks if the next block is free.

A new function, header_merge(Header *header), is the core of the solution. It identifies adjacent free blocks and merges them, updating the size and pointers accordingly. The function handles edge cases, such as merging the last block.

Integrating the Solution into abfree()

The abfree() function is modified to call header_merge() before freeing the memory. This ensures that any adjacent free blocks are combined before the memory is released back to the system.

Conclusion and Next Steps

The improved abfree() function, along with the helper functions, significantly reduces memory fragmentation. The author notes that one final challenge remains: memory block alignment, which will be addressed in the next post. The complete, updated abfree() function and its supporting functions are provided at the end of the article.

The above is the detailed content of Implementing malloc() and free() — merging small blocks. For more information, please follow other related articles on the PHP Chinese website!