The Joy of
Programming Dynamic Memory Allocation in C In this column, let us try to understand the nitty-gritty of dynamic allocation using a few programming problems.
A
ssume that you are writing code to implement a text editor in C. To represent characters typed in the editor, you plan to use dynamic memory allocation for each character. In the following code segment, text is a two-dimensional array of ‘char*’s. When the user types a character, say ‘a’, in row_pos, column_pos, memory is dynamically allocated only for sizeof(char) and the character is stored as in:
text[row_pos][column_pos] = malloc(sizeof(char));
*text[row_pos][column_pos] = ‘a’;
Is this an efficient approach to store characters that are typed in the text editor? In this approach, there are many problems in the assumptions made for storing characters in a text editor. Let me point out a very significant problem. The sizeof(char) is 1. But malloc(1) does not return a memory block of size 1 byte. Why? For that we need to understand how dynamic memory allocation works. Generally, in C, dynamic memory allocation is implemented using a linked list mechanism to allocate memory blocks of different sizes. So, for each block allocated, it has to remember the size of the allocated block (so that it can be subsequently freed). Remember that malloc returns a void *. Since malloc does not know the type to which the returned block will be cast and used, it has to allocate a block that is within the maximum alignment requirements imposed by a platform. Typically, this is 4 to 8 bytes. In addition, since dynamic memory allocation is implemented using (usually) a singly linked list, at least one pointer to the next block needs to be stored. So, allocation of a block requires at least these fields: l Space to store information about the ‘size’ of the fragment l The actual memory of length ‘size’ bytes (within maximum alignment requirements) l The pointer to the next free block So, for example, if the maximum alignment requirement is 8 bytes, and an integer of 4 bytes is used to store the size of the requested block and the pointer size is 4 bytes (which is used to store the next pointer), malloc has to return a block with minimum 16 bytes for a call. In some other unusual implementation, if the maximum alignment requirement is 16, and if sizeof int and pointers are 8, it will require a minimum of 32 bytes for allocating a single block!
100
march 2008
|
LINUX For You
|
S.G. Ganesh
So, the design to store characters in the text editor by using malloc(sizeof(char)) is not a good idea. Now let us look at a problem in using dynamic allocation. The following code is for freeing a linked list. Will it work? for( ptr = head ; ptr != NULL ; ptr = ptr->next )
free(ptr);
Here, in the expression ptr = ptr->next, ptr is accessed after ptr is released using function free. This also serves as example for dangling pointers where the pointer is used even after freeing the block. So the behaviour of this code segment is undefined. However, it usually works well in practice. Why? The free function need not actually ‘release’ the memory immediately after the call to free it. Usually, C implementations implement ‘free’ by moving a memory block to a ‘free list’ without modifying the contents in the block. So, this code will work fine in many of the implementations. However, it is not recommended to write code like this with such implementation defined behaviour. For this problem, there is a simple solution—introduce a temporary variable as in: for( ptr = head ; ptr != NULL ; ptr = temp) { temp = ptr->next; free(ptr); }
The implementation for dynamic allocation outlined here uses a straightforward, simple implementation. However, real-world implementations are obviously more complex. For example, few C implementations provide a user directed Small Block Allocator (SBA) mechanism so that the programmers can tune the C dynamic memory allocator implementation for small block allocation. In Linux implementations (for example, glibc), the mmap system call is used to allocate large memory blocks (segments) with malloc. In this approach, when free is called, the large blocks (segments) can be returned to the system. There are lots of resources available on the Web about interesting implementation details—http://en.wikipedia. org/wiki/Malloc is a good place to start. S.G. Ganesh is a research engineer at Siemens (Corporate Technology). His latest book is “60 Tips on Object Oriented Programming”, published by Tata McGraw-Hill in December last year. You can reach him at
[email protected].
www.openITis.com
cmyk