0

I have an explicit free list. Each node contains the number of blocks it manages. When you allocate, the memory manager returns the first block of the managed blocks.
In the beginning, there is only one node that manages all available blocks (minus the blocks the node requires).
Allocations split the available space, and place a new node right after the required blocks for this allocation. This node becomes the new header for the free list.
This goes on and on.

When freeing, the free memory becomes fragmented and needs to be defragmented. Freeing simply adds the header back into the freelist. which means that the nodes are logically, but not necessarily physically adjacent.

How can I (fast and hopefully easy) defragment memory blocks that are physically, but not necessarily logically adjacent?

As a side node: The memory manager is using a list of physically arranged blocks. Each allocation can use an arbitrary number of blocks. enter image description here

In the picture above, you can see that B and G are physically, but not logically adjacent.

9
  • Since you have already one big memory block, are you sure you need to defragment after freeing? Is it really worth the cost? You'll have to move and copy blocks around. What's you motivation to do so? Alignment optimization, optimized block sizes? Jul 8, 2020 at 17:41
  • Memory is limited, defragmenting is important to achieve optimal usage.
    – user315117
    Jul 8, 2020 at 17:51
  • 1
    Frequently this is done by keeping the freelist in sorted order. Another way to do it is to keep a per-block header (a word or two) that keeps the actual size of the block as well as an "in-use" bit. Then when a block is freed you inspect its neighbors to see if one (or both) are free themselves, if they are you merge them.
    – davidbak
    Jul 8, 2020 at 18:21
  • @πάνταῥεῖ I've added a picture
    – user315117
    Jul 8, 2020 at 18:42
  • "Memory is limited, defragmenting is important to achieve optimal usage." I'm still a little unclear on the goal here. You talk about defragmenting blocks that are physically adjacent but that has nothing to do with making more space available. It might relate to performance. Is that why you want to do this?
    – JimmyJames
    Jul 9, 2020 at 17:29

2 Answers 2

0

Linked List

Depends on how you structure your memory. But there are two ways to my mind of doing this.

Way 1.

Store the size of the allocation to both the left and right of the header along with a free bit. This works best if you have a max allocation size that allows you to bit pack.

A good example would be a 15 bits of allocations size. This would allow you to pack a 32bit field with:

  • the two sizes (@15bits each),
  • have 1 bit as an allocation bit for the right hand side,
  • and have a checksum bit to detect memory under/overflows.

The two sizes allow you to link list forward and backwards and then check the allocation bits. If they aren't set, then you can merge the allocations.

Way 2.

Have two external pointers one to the first allocated slot, the next to the first unallocated slot (freelist).

The header of each block contains a pointer to the previous, and a pointer to the next block. If its allocated these point to the prior/next allocated block. If its unallocated these point to the prior/next unallocated block. It also needs the size field of the allocation.

Pick an unallocated slot, the next allocated block is header+size to the right. Unlink the allocation from the freelist, link into the allocated list. If the allocation has to be split, split it first into two unallocated slots, just remember that where the next allocated block is first.

Freeing an allocated slot, scan the linked list to the right, the first header+offset != next identifies the next unallocated slot at header+offset. The header is relative to last confirmed allocated slot. Same story for scanning backwards, except the header is the prior slot. If the next/prior unallocated was the first slot checked, then the free slot is adjacent and can be merged, otherwise they aren't and need to be linked.

Depends entirely on the trade off you'd like to make.

0

Freeing simply adds the header back into the freelist.

To avoid memory fragmentation, your freeing function needs to do a bit more than just adding the header back to the free list.

If you keep the free-list sorted in ascending memory-address order, then your freeing function can relatively easily merge a newly freed block with physically adjacent blocks that are already free.

The algorithm to do so would be

  1. Walk the free list until you find the sorted insertion point (the preceding node has a lower address than the memory being freed and the next node has a higher address)
  2. Check if the next node is adjacent to the memory being freed. If so, remove that node from the list and adjust the size of the memory being freed to include the size of that node.
  3. Check if the preceding node is physically adjacent to the memory being freed. If so, adjust the size of that node to include the size of the memory being freed. Skip the next step.
  4. Insert the memory being freed as a new node in the free list immediately after the preceding node

As the algorithm tries to merge the free blocks every time a new free block would be created, the free list will never contain two nodes for physically adjacent memory, so when merging you only need to check two nodes if they can be merged with the new free block.

In the example from your image, the last two free's would result in a different free list. The free lists would be respectively

  1. G (6 blocks) <-> S (2 blocks)
  2. B (11 blocks) <-> S (2 blocks)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy