Malloc Allocation Schemes - 【StackMirror】|c|memory|malloc

Yes, I am taking a Computer systems course. I had a few questions about the various allocation schemes to implement malloc. For explicit lists, if I implement malloc using a LIFO-like stack, what exactly is the purpose of having pointers to previous freed memory? Like why do you need doubly-linked lists? Wouldn't singly linked lists work just as well?

Malloc lecture. I found this link online, you can look at slide 7 to see what I'm talking about.

When looking at a segregated list allocation scheme, these lists are uni-directional right? And also, what exactly is the coalescing mechanism? Like for example, if 4 words are freed, would you first try and join it when the free space around you before inserting it back into the respective segregated linked list? Or would you simply insert the 4 word block in the '4 word' section of the respective segregated linked list?

Thank you.

2012-04-04 05:33
by de1337ed

Since a freed block always has room for two pointers, why not doubly-link the list? It simplifies the coalescing code so it doesn't have to maintain a trailing pointer while traversing the list. It also allows traversing the list in either direction in case there is a hint for which end of the list might be closer to begin the search. One obscure system I once looked at kept a pointer in the "middle", where the last activity occurred.

When freeing a block. There are only four possible cases:

The free block is adjacent after a free block.
The free block is adjacent before a free block.
The free block is between and adjacent to both free blocks before and after it.
The free block is not adjacent to any free block.

The purposes of coalescing adjacent free blocks are:

to reduce the length of the linked list
to accurately reflect the size of a free block without burdening the allocator to look ahead to see if two blocks are adjacent

Sorting a free block into a specific-length freelist often has benefits, but in most practical implementations, coalescing is a priority so that an alloc() request for a different size block isn't inappropriately denied when there are many differently-sized free blocks.

2012-04-04 05:54
by wallyk

I think I see what you are saying but can you elaborate more on the lack of need to maintain a trailing pointer? Also, if i call a free block B. Are we assuming that B->next->prev = B? Because if this isn't the case, I don't see how doubly linked lists would help. Also, what would be the best way to initialize the heap in a segregated list allocator? Would you partition the page in some pattern? (Like give 64 free blocks of 2 words, 64 free blocks of 4 words, 64 free blocks of 8 words ... until you hit the designated infinity category? Or is there a better way to initialize - de1337ed 2012-04-04 06:09

@de1337ed: Maybe you have not written any node list processing code? Give it a whirl: write a function which inserts a node into a linked list. Keep the list in address=sorted order. Try it with singly-linked. And then modify it for doubly-linked. (To answer your question B->next->prev is always B. If it isn't, there is a bug.) Initializing the heap is subject to policy decisions of the implementer: should there be a bunch of 512-byte blocks ready to go? Depends on the system - wallyk 2012-04-04 06:18