Dynamic memory allocation under the hood

I owed you some explanations regarding dynamic memory management implementation so here they are.

Before going into any specific implementation I would like to refer to Ritchie and Kernighan’s “The C programming languagebible. I had in hands the second edition published at Prentice Hall in 2008.

Chapter 8.7 provides a storage allocator example. Few important things are outlined out there:

    calls to malloc and free may occur in any order
    malloc requests storage from the operating system as needed
    the storage used by a program can be requested by malloc, but also by other sources, so its memory blocks are basically of three types: not owned by malloc, owned by malloc which are free and which are in use, only last two categories make the subject of our discussion (let’s name those two as free and in use)
    every free block is split into three fields as shown in the picture below: a pointer to the next free block, the size (usually in bytes) of the current free block and the actual stored data

What happens when mallocfunction is called?

The “free list” is scanned until a big-enough memory block is found (big enough for current data to be stored, a first fit algorithm is used meaning that first free block which has a size larger than the one requested is taken)
There are three possibilities:

    there is no free big-enough block found, in this case program must a request another “chunk” of memory from operating system
    there is found a bigger block than the size requested, in this case only the needed space is used and residue storage is returned to the free list (in order to avoid fragmentation – this is why in previous post (link) I talked about advantages that dynamic allocation has over static allocation in terms of memory fragmentation)
    it is found a block having exactly the needed size, in this case this block is “unlinked” from the free list

What happens when free is called?

Corresponding “freed” block is added to the free list (two issues may arrive here: where is it added – whether after another free block, if it fits and the two ones are combined, whether at the end of the free list, and second issue – what does its pointer indicate? How is this correctly adjusted to point correctly to “next free block”?)

OK, that was it with Ritchie and Kernighan! I had a look also here and I decided to go through their “simple allocator implementation” line by line and to comment it. Before starting it is important to say that the implementation is part of the C standard library, and can be found in stdlib.hheader, so it is free-cost, but custom versions can also be used depending on the operating system and on the architecture. You may find here different malloc implementations.

The complete source code of this implementation that I will go through can be found here.

In the aforementioned article the functions have the following declarations:

void *malloc(long numbytes): This allocates numbytes of memory and returns a pointer to the first byte.
void free(void *firstbyte): Given a pointer that has been returned by a previous malloc, this gives the space that was allocated back to the process’s “free space.”
Let’s go line by line through this “main allocator”:

void *malloc(long numbytes)
{

Usually the argument is of type size_t. in K&R “C programming language” it is mentioned that in order to ensure that data is properly aligned the argument should be of the most-restrictive type used on a certain machine. If this type may be stored at a particular address all others may be also. Mainly the most restrictive type is long and this is why the argument is of type long.

Some initializations are done before doing the “real” stuff. Three pointers worth to discuss now:

void *current_location;

Current_location obviously points to the location that is scanned by this malloc implementation or storage allocator (tell it how do you like it)

struct mem_control_block *current_location_mcb;

current_location_mcb is almost the same thing as previous pointer but it is two integers delayed, due to the fact that size field as well as availability information has to be taken into consideration. (Remember the picture above of how a memory location used by malloc is implemented, the address returned to the user is not the very first one, but the one after the pointer and the size, this is the reason that we are complicating our lives with this struct). It has the following implementation:

struct mem_control_block {

    int is_available;
    int size;

};

Memory_location is the “bingo” location, is the value of current_location where the search for a free location has given a positive result

void *memory_location;

After used pointers were initialized it is necessary to set them at the corresponding memory location were the search must begin:

if(! has_initialized)
{

    malloc_init();

}

numbytes = numbytes + sizeof(struct mem_control_block);
memory_location = 0;

Let’s say few words about malloc_init, here it is its definition:


//those are the global variables
int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;
void malloc_init()
{

    last_valid_address = sbrk(0);
    managed_memory_start = last_valid_address;
    has_initialized = 1;

}

sbrk is used in conjunction with brk in order to request the operating system another piece of memory, if this is needed. brk defines the size of this chunk and sbrk called with an argument of 0 is used to find the location of the program break. More on this you can find here , in any case this can vary across different platforms.So, after executing malloc_init memory to be allocated is initialized. Somehow the use of initialization term can be error-prone. Maybe it could be more suitable to call this process “grabbing necessary memory slice from OS” and this part:

memory_location = 0;
current_location = managed_memory_start;

can rather be called initialization, meaning that malloc variables are set to default values and are prepared for the search algorithm that will follow.Before starting the algorithm implementation programmer must hide to malloc API user the fact that searched memory has to include size and information about if it is free or not.

numbytes = numbytes + sizeof(struct mem_control_block);//mem_control_block is defined upwards

Enough with initializations! Here is the search algorithm:

while(current_location != last_valid_address)
{
current_location_mcb =(struct mem_control_block *)current_location;
if(current_location_mcb->is_available)
{

    if(current_location_mcb->size >= numbytes)
    {
    current_location_mcb->is_available = 0;
    memory_location = current_location;
    break;
    }

}
current_location = current_location + current_location_mcb->size;
}

This was it all….?
YES, and here it is how it works:

It is needed to cast current_location pointer to mem_control_block type because the latter includes information about memory availability and size.

The loop lasts as long as the algorithm didn’t reached last valid address from the memory slice provided by the operating system.

First if condition checks whether of not this is free (the curios thing is that nowhere is specified at which value are size and is_available initialized). “If” this is the case then corresponding size is checked, “if ” the size meets the requirements then corresponding block is made as soon available

current_location_mcb->is_available = 0;

and value returned by malloc is set to corresponding location and exit while loop … and finish the algorithm also.

memory_location = current_location;
break;

If none of “if’s” are met then increment current_location and point to the next block (I mean point to the subsequent block).

As you can see this algorithm, as well as any other malloc implementation, is non-deterministic, there is no fixed time to find out the “needed block”.

In case if no location is available the program needs to ask operating system for more memory, here’s how it does it:

if(! memory_location)
{

    sbrk(numbytes);
    memory_location = last_valid_address;
    last_valid_address = last_valid_address + numbytes;
    current_location_mcb = memory_location;
    current_location_mcb->is_available = 0;
    current_location_mcb->size = numbytes;

}

After this was done the program is assured that malloc will return some value

memory_location = memory_location + sizeof(struct mem_control_block);
return memory_location;
}

This is not the same for de-allocation function, the notorious free function. Its implementation is time-independent.

void free(void *firstbyte) {

    struct mem_control_block *mcb;
    mcb = firstbyte - sizeof(struct mem_control_block);
    mcb->is_available = 1;
    return;

}

There is no need to find anything, the block to be freed is passed as an argument to the function and it is simply made available (remember: firstbyte pointer indicates where useful data is, the entire block “begins” two integers earlier )

Advertisements

One Response to Dynamic memory allocation under the hood

  1. Pingback: Memory pools or best practice in dynamic allocation in embedded systems « Bazaar 2.0

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: