Malloc Implementations

[PlayOS]

Hi all,

I am currently looking at memory management and was wondering if you guys know of any really good tutorials or other information about malloc implementations. I have searched google and found some helpful stuff, however I need something that is very descriptive, doesn't matter so much about code, just something that describes the process of how malloc/free work.

I will be able to incorporate into my OS and LIBC, I just really need to know more about the standard C inteface that is required to be compliant with the C Standard.

Maybe someone knows where a really up to date C Standard Specification is (it one exists, for free that is), something that explains everything that is required in LIBC to be compliant with the standard.

Thanks.

P.S. I wasn't sure if I should post this here, but I decided that it is specific to my OS programming, it is memory management after all. So here it is.

[elias]

dont take this word as law, but im pretty sure it all depends on how your file system is implemented.

[adeelmahmood1]

yeah i would also love to have some info on memory management which really explains something

[Pype.Clicker]

virtually every malloc/free implementations are based on a free list that is made of a small descriptor for every free zone on your system. The descriptor usually looks like

Code: Select all

struct mmFreeBlock {
     ulong magic;  // will hold a "magic" 32 bits value that can be
                           // used for quick debugging, or a magic + a checksum
     ulong size; // most important: how big is this free block
     struct mmFreeBlock *next; // next free block in the list
};

The block descriptors are placed at the first byte of the block they represent, so they don't occupy extra memory
we usually try to keep that list sorted per growing addresses (this will make sense when trying to merge contiguous zones).

Initially, we create one block that will cover the whole free memory.

Now, imagine we want to malloc(N) ... all we have to do is sweeping the free list until we find a block which size is >N (this is called the first fit algorithm. Then, we'll reduce the size of the block by N and return ((void*)block)+(old_size-N) to be the allocated zone.

Allocating the end of the block prevents us to change the list pointers after every single allocation. If size-N happens to be less than sizeof(mmFreeBlock), then the whole block has to be released (thus the previous block p will be linked to the removed block's follower -- you should better find a tutorial on linked list if this isn't obvious for you)

When freeing block B, the list is swept to find out the future "predecessor" of B. pred will be the last block so that pred < B. We will also check if (void*)pred+pred.size==B, and if this is the case, we will merge pred and B together (pred.size+=B.size; B = pred), otherwise the B block is linked behind pred with B.next = pred.next ; pred.next=B...

We will also check if B.next == (void*)B+B.size. If this is the case we can merge B with its successor ...

If it's not clear to you, just pick up a paper and a pencil and draw the previous cases: it will not block you long...

Code: Select all

[Pype.Clicker]

dont take this word as law, but im pretty sure it all depends on how your file system is implemented.

I don't see any relationship between malloc/free and the filesystem ...

Note that in addition to the above technique (first fit), there is also a possibility to pick the item in the list which size is the closest to the required size (best fit). However, it usually doubles the mean access time...

A lot of techniques can be implemented to speed up the allocation/free process such as a lookup table that keeps a list of blocks such that B.size > 2^i in its ith entry, or that will split the list into addresses ranges (so that freeing is made faster)

This will complicate a bit your code, but it will definitely give better performances.

[Schol-R-LEA]

In a addition to to First Fit and Best Fit, there is also Worst Fit, which paradoxically is often the most efficient overall. The basic mechanism - keep the free list ordered from largest to smallest, and always allocate from the largest block - involves only a little more overhead than First Fit (incured when inserting a block into the list), but it avoids the fragmentation problems that occur with Best Fit (in which there free list slowly becomes filled with tiny frgaments that are too small to for any of the memory requests).

[Tom]

There is some info on this ( or code ) I think at that Chris ( forgot his last name...geeze mabe? ) web site...I read something about a malloc....

[K.J.]

http://osdev.neopages.net/tutorials/25.alloc.pdf

K.J.

[PlayOS]

Thanks for all of your help guys.