dcsimg

Dynamic Memory Allocation — Part I

This month we're going to examine a topic that is probably familiar to those of you who have any experience with programming -- dynamic memory allocation. In any programs of significant heft, dynamic memory management is a necessity. You are probably experienced with the standard C functions malloc() and free(), and we'll do a brief recap of those memory allocation and deallocation functions. Following that, we will look at how memory allocation in Linux actually works.

This month we’re going to examine a topic that is probably familiar to those of you who have any experience with programming — dynamic memory allocation. In any programs of significant heft, dynamic memory management is a necessity. You are probably experienced with the standard C functions malloc() and free(), and we’ll do a brief recap of those memory allocation and deallocation functions. Following that, we will look at how memory allocation in Linux actually works.

Memory Allocation Functions

There are three standard C functions that you can use to allocate memory — malloc() , calloc() , and realloc() . Their prototypes, as defined in <stdlib.h> , are:


void* calloc (size_t nmemb, size_t size);
void* malloc (size_t size);
void* realloc (void *ptr, size_t size);

malloc() is the simplest of the allocators. It simply takes an argument specifying the size of the memory block that you wish to allocate and returns a pointer to a block of memory of that size. calloc() takes in two arguments, a number of elements ( nmemb ), and a size for each element ( size ). The total size allocated by a call to calloc() will be (nmemb * size) bytes. Also, calloc() actually sets all the memory it returns to NULL . In contrast, there are no guarantees regarding the values stored in the memory returned my malloc() .

realloc() is used to reallocate a section of memory that has been previously allocated. Notice that it takes in a pointer ( *ptr ) as its first argument. The second argument ( size ) indicates how much space the pointer should now contain. Sometimes realloc() has to move memory around to find the space for the new chunk. As a result, the pointer returned by realloc() may be different than the pointer you pass to it. The values stored in the memory passed in will be copied to the newly allocated block. You may also use realloc() to cut down the size of a block of memory by passing it a size that is smaller than the original allocated size of the block.

All three of these allocation functions return 0 on failure. Therefore, it is imperative that you check the return value of these functions before you use the pointers. Take a look at the code in the following example:


int* ptr = malloc (sizeof (int));
*ptr = 7;

It looks simple enough; it allocates enough memory for an integer and then places 7 into that memory. But what if malloc() returns NULL? The next statement will de-reference that NULL value, causing a segmentation fault.

The example above might not seem like such a big deal, but take a look at the code in Listing One (taken from the file include/linux/coda_linux.h in the 2.2 version of the Linux kernel). This code demonstrates a real memory allocation bug, proving that Linux is not actually a perfect operating system.




Listing One: A Memory Allocation Bug in Linux


if (size < 3000)
{
ptr = (cast)kmalloc((unsigned long) size, GFP_KERNEL);
CDEBUG(D_MALLOC, “kmalloced: %lx at %p.\n”, (long)size, ptr);
}
else
{
ptr = (cast)vmalloc((unsigned long) size);
CDEBUG(D_MALLOC, “vmalloced: %lx at %p .\n”, (long)size, ptr);
}
if (ptr == 0)
{
printk(“kernel malloc returns 0 at %s:%d\n”, __FILE__, __LINE__);
}
memset( ptr, 0, size );

Note that the second if statement actually does go on to check the value of ptr , which in this case represents the return value of either kmalloc() , the kernel’s internal version of malloc() in the first if statement, or vmalloc in the else statement. If ptr ‘s value is NULL , a warning is printed, printk (“kernel malloc returns 0 at %s:%d\n”, __FILE__, __LINE__); . However, even if the return value of kmalloc() were NULL , the program would be allowed to continue, and that NULL value would be passed on to the memset() function, which would attempt to assign a value to the non-existent memory, causing an immediate segmentation fault.

The important thing to remember here is that if you forget to check the return values of your memory allocations, your program has the potential to crash, even if it’s something as important as the kernel. Naturally, one of the numerous Linux kernel hackers fixed this problem for Linux 2.4.

The free() function which has a prototype of:


void free (void* ptr);

is used to deallocate memory that was previously allocated by one of the three allocators mentioned above. You simply pass it a pointer you used to reference the memory previously allocated. A block of memory may also be freed by passing it to realloc() with a size of 0. After a block of memory has been freed, it must no longer be used for any purpose. If you do use the memory again, it’s likely that your program will not crash right away, but at some later time when the effects of the wrongful use cause something to break. These types of bugs are difficult to find, so it’s crucial that you not use memory after its been freed.

Listing Two contains a simple program that implements a linked list of integers using dynamic memory allocation. The functions defined demonstrate the use of malloc() and free() in a program. Although this program is only a toy, it’s a good example of how to correctly allocate and deallocate memory.




Listing Two: Linked List Example – Part I


#include <stdio.h>
#include <stdlib.h>

struct linked_list
{
int item;
struct linked_list* next;
};

void insert (struct linked_list** head, int new_value)
{
struct linked_list* new_item;
new_item = malloc (sizeof (struct linked_list));
/* malloc failed. We must exit. */
if (new_item == NULL)
{
fprintf (stderr, “Out of memory. Exiting!\n”);
exit (1);
}
/* At this point, we know the pointer is ok, so we can
use it. */
new_item->item = new_value;
new_item->next = *head;

/* Set the head of the list to be the new element. This
inserts the element at the beginning of the list. */
*head = new_item;
}

void delete (struct linked_list** head, int to_delete)
{
struct linked_list* current_place, *previous_place;
current_place = *head;
previous_place = NULL;
while (current_place != NULL)
{
/* If we’ve found the item, break out of the loop. */
if (current_place->item == to_delete)
break;
previous_place = current_place;
current_place = current_place->next;
}

/* Did not find the item to delete. Just return. */
if (current_place == NULL)
return;

if (previous_place != NULL)
/* Set the previous item in the list to skip over
the item we are about to delete. */
previous_place->next = current_place->next;
else
/* The item to delete was the head of the list. Handle
this differently by setting the head to be the second
item since we are about to delete the first. */
*head = current_place->next;
/* Deallocate the memory associated with the item to be
deleted only after we have made sure that there are
no other references to the memory. */
free (current_place);
}

void print_list (struct linked_list* head)
{
struct linked_list* current_place = head;
while (current_place != NULL)
{
printf (“%d “, current_place->item);
current_place = current_place->next;
}
printf (“\n”);
}

int main ()
{
/* A null value for the head represents an empty list */
struct linked_list* my_head = NULL;
/* Add some items to the list. */
insert (&my_head, 1);
insert (&my_head, 4);
insert (&my_head, 2);
/* Print the list and then delete the items. */
print_list (my_head);
delete (&my_head, 2);
print_list (my_head);
delete (&my_head, 1);
print_list (my_head);
delete (&my_head, 4);
print_list (my_head);
}

Under the Hood

Now that we know what memory allocation and deallocation functions do, let’s go under the hood and examine exactly how these functions carry out their duties. Many different types of memory allocators exist. A full explanation of all of them is beyond the scope of this article. However, we will briefly discuss the three major techniques used and then dive deeply into the one used by the implementation of malloc() for Linux.

Memory allocators are categorized mainly by how they keep track of the free blocks that they can use to parcel out memory to applications. Imagine a new program that has just started. The memory allocator has a single, large block of memory that it can use for allocations. However, after many allocations and deallocations, holes can start to appear in this block. (The technical term for this phenomenon is fragmentation.) Free blocks show up in many different sizes, and the allocator must use these free blocks in an efficient way to keep total memory use to a minimum.

The first category of allocators uses a technique called “sequential-fit” to keep track of free blocks. These allocators keep all the free blocks in one doubly-linked list. When a request comes in, an allocator of this type starts looking through the list until it finds a block that it deems appropriate to satisfy the request and returns it. There are three main types of sequential-fit allocators that are worth mentioning: first-fit, next-fit, and best-fit.

In a first-fit allocator, searching always starts from the beginning of the list of free blocks (i.e., the free list), and as soon as a big enough block is found, it is split up to the size required and returned to the user. Next-fit differs from first-fit in that it starts each search where the last search ended. It does not start at the beginning of the list each time, because it is believed that starting at the same place for each search can increase fragmentation.

Best-fit allocators differ from the other two approaches in that they attempt to find the smallest block that has enough room to satisfy the request. Therefore, if you request four bytes, and two blocks of sizes 16 and 32 exist, the best-fit algorithm will choose the 16 byte block over the 32 byte block regardless of the order of the blocks in the free-list. However, best-fit allocators may suffer a performance hit if they are forced to search through the entire free-list on every allocation. This will be the case any time an exact fit is not found somewhere in the list. All three of the sequential-fit allocators coalesce free blocks that are adjacent to form one larger block in the free-list.

“Buddy-system” allocators make up the second category of algorithms. Their focus is on how free blocks are combined together. The idea is that every time a block must be split, it is split in half, and the two halves may only be coalesced once both are completely free (i.e., the two halves are buddies). As a concrete example, imagine that there exists a free block of size 4096 bytes (that’s 212). If an application requests a block of size 750 bytes, the original block will be split into two halves of 2048 bytes, then one of those blocks will be split into two halves of 1024 bytes, one of which will be returned to the application. (It cannot split again since the resulting blocks would be too small to fulfill the request.) The remaining blocks on the free-list will be one of size 1024 and one of size 2048. This method has been known to suffer from fragmentation. Notice that in our example, 1024 bytes were allocated for a block of only 750 bytes, wasting over 250 bytes of space.

The final category of allocators (and the type of allocator the standard C library in Linux uses) is those that use segregated “free-lists” or “bins.” The idea here is to keep multiple free-lists. Each free-list contains blocks for a particular range of sizes.

For example, the first free-list might contain blocks with sizes between eight bytes and 64 bytes. Another free-list might contain blocks with sizes between 1024 bytes and 2048 bytes, and so on. When a request comes in, the allocator simply starts the search in the smallest bin that can definitely fill the request and returns the first block it finds. If no blocks exist in that bin, the next larger bin is searched, and so on. This method has the benefit of getting a close approximation of the best-fit method without requiring a search through all the free blocks on each request. However, it does incur the overhead of keeping track of all the different free-lists.

The Linux Memory Allocator








figure1
Figure One: An allocated block with size tags.

The Linux allocator was originally written by Doug Lea and is sometimes referred to as dlmalloc() . The source code can be found in the glibc source within the malloc subdirectory. The main allocation is done from a file called malloc.c.

So now let’s take a closer look at this memory allocator, which uses bins to determine how to allocate free blocks of memory. The allocator keeps 128 bins of different sizes. The first half of those bins keeps exactly one size in them. These are for the smaller sizes, 16 bytes through 512 bytes (equally spaced 8 bytes apart). The other half of the bins keeps all the rest of the sizes (spaced exponentially) between 576 bytes and 231 bytes. Unlike the first half, these bins do not require exact sizes; the sizes found in a given bin will be anywhere between the previous bin size and that bin size. As of the most recent version of this allocator, all bins that contain different size blocks are sorted from smallest to largest, making the algorithm always return the best-fit for any given size.

When a block is freed, it is coalesced with either or both of its free neighbors, and the resulting block is placed in the appropriate bin. The allocator keeps track of the location of a block’s neighbors (as well as how much memory is being deallocated) by making use of a “size tag.” The size tag is four bytes of memory that is allocated along with the block requested by the application. It resides right before the beginning of the user block of memory. This size is also repeated at the end of the block so that it is easy to determine the size of the block right behind any given block as well as the block ahead of any given block.








figure2
Figure Two: A picture of a freed block with size tags and linked-list pointers.

The allocator uses these size tags to keep track of exactly how much memory is allocated where. This is why you do not need to specify a size when you free memory — the allocator can simply look back 4 bytes from the given address to determine the size of the block. The size tag at the beginning of the block also keeps a bit reserved to indicate whether the block is free or in use. See Figure One for a picture of an allocated block and its size tags. As you might have realized, the use of these two size tags adds an additional eight bytes to the size of any allocated block.

The allocator must also somehow keep the pointers for the list of free blocks for each bin. In the Linux memory allocator, each bin is a doubly-linked list of free blocks in the given size range. The allocator cleverly stores the previous and next pointers for each block in the actual user space of the block that was allocated. Since the block has been freed, that space is no longer needed and can be used for another purpose! Figure Two shows how the memory is laid out in a block once it has been freed. Of course, by storing two pointers in the freed blocks, the allocator imposes a minimum size of 8 bytes on any allocated user block. Therefore, no matter how few bytes a program allocates, a block of at least 16 bytes will be allocated.




Listing Three: A Simple Example of the Overhead of the Linux Memory Allocator


#include <stdlib.h>
#include <stdio.h>

int main ()
{
char *a, *b, *c;
a = malloc(1);
b = malloc(1);
c = malloc(1);

printf (“%d %d %d\n”, (int) (a-a), (int) (b-a), (int) (c-a));
}

As a simple example of this, look at the code in Listing Three. Notice that we only allocate 1 byte of memory for each of the three variables. However, when we print out the difference between the pointers (i.e., how far apart they are in memory), we would get the following output:


~/> ./a.out
0 16 32
~/>

The three different blocks of memory are 16 bytes apart, demonstrating the overhead incurred by the use of size tags and free block pointers.

Free to Go…

You’ve probably used dynamic memory allocation in many of your programs without ever having thought about what was actually going on each time you called malloc() and free() . Hopefully, this article has given you a new perspective on memory allocation. Next month, we’ll continue with this topic by discussing exactly how the operating system manages the memory it gives to processes and the system call that memory allocators use to get more memory from the kernel. Until then, happy allocating!



Benjamin Chelf is an author and engineer at CodeSourcery, LLC. He can be reached at chelf@codesourcery.com.

Fatal error: Call to undefined function aa_author_bios() in /opt/apache/dms/b2b/linux-mag.com/site/www/htdocs/wp-content/themes/linuxmag/single.php on line 62