Implement malloc() and free() — split large chunks

The previous article explored the impact of memory block reuse order on memory consumption and optimized functions to reduce waste. However, another more serious problem persists: a huge memory block may occupy multiple small blocks of space that could have been exploited. For example, allocate a large chunk of memory, and after release, allocate two smaller chunks:

 <code class="c">void *ptr1 = abmalloc(128); void *ptr2 = abmalloc(8); abfree(ptr1); void *ptr3 = abmalloc(8); void *ptr4 = abmalloc(8);</code>

At this time, the 128-byte free block cannot be utilized by the 8-byte request, resulting in the subsequent 8-byte block allocation that requires the heap to be expanded again, resulting in low memory utilization.

A highly efficient but complex way to solve this problem is to use "bins": a list of chunks grouped by size. Another simpler solution is to split the large chunks into smaller chunks. This article adopts the latter.

Code Refactoring

First, refactor the code slightly. header_new() function is responsible for allocating memory and initializing block headers, which is not conducive to the readability and maintenance of the code. We split it into two functions:

• header_plug() : Insert the initialized block between the previous and next blocks.
• header_init() : Initialize the metadata (size and availability) of the block.

They are as follows:

 <code class="c">void header_init(header *header, size_t size, bool available) { header->size = size; header->available = available; } void header_plug(header *header, header *previous, header *next) { header->previous = previous; if (previous != NULL) { previous->next = header; } header->next = next; if (next != NULL) { next->previous = header; } }</code>

header_new() function is modified as follows:

 <code class="c">header *header_new(header *previous, size_t size, bool available) { header *header = sbrk(sizeof(header) size); header_init(header, size, available); header_plug(header, previous, NULL); return header; }</code>

( last->previous->next = last; in abmalloc() function, this line can be deleted because header_plug() is now responsible for handling this logic.)

Split memory blocks

Next, implement header_split() function. Given a block header and the minimum required size, if the original block is large enough, split it into two parts:

• blocks of required size;
• The remainder and its new blocks;

First, check if the block is large enough:

 <code class="c">header *header_split(header *header, size_t size) { size_t original_size = header->size; if (original_size >= size sizeof(header)) {</code>

If large enough, split the block. First, reduce the size of the current block:

 header->size = original_size - size - sizeof(header);

Calculate the pointer to the new block:

 header *new_header = (header 1) header->size; // Corrected pointer calculation

Initialize the header of a new block:

 header_init(new_header, size, true);

Connect the new block to the linked list:

 header_plug(new_header, header, header->next);

If the original block is the last block, update last pointer:

 if (header == last) { last = new_header; }

Return to the new block:

 return new_header; } else { return header; } }

Update abmalloc()

Finally, modify the abmalloc() function, and after finding the available block, call header_split() to try to split it:

 <code class="c">if (header->available && (header->size >= size)) { header = header_split(header, size); header->available = false; return (void*)(header 1); // Cast to void* for correct return type }</code>

If the block can be split, the new block is returned; otherwise, the original block is returned.

Notes on block segmentation

It should be noted that the new block is created at the end of the original block. Although it can also be created at the beginning, creating a new block at the end can bring the new free block closer to the old block, improving the efficiency of the next abmalloc() call.

Splitting large chunks of memory is a step toward improving memory management, but it can also lead to small chunks of memory fragmentation, resulting in larger requests that require expansion of the heap. The next article will explore how to solve this problem.

The above is the detailed content of Implement malloc() and free() — split large chunks. For more information, please follow other related articles on the PHP Chinese website!