Malloc

malloc is a function for allocating memory dynamically in the C programming language. Without malloc, memory allocation must be done "at once".

Explanation

If we wish to create an array of ten integers, without malloc we may say

int tbl[10];
/* statements */

Alternatively we can create a pointer to the first element of the array. The following code will allow us to use either tbl or x to access data within the array.

int tbl[10];
int *x;
x = tbl; /* tbl[i] and x[i] are now equivalent */

Now this does not seem to have gained us much, but the use of malloc allows us to create an array of any size

int *x;
/* statements */
x = malloc(sizeof(int)*10); /* x can now be used as an array of ten integers */

or, if the array size isn't known until run time:

int *x = malloc(sizeof(int)*m); /* where m is a size determined dynamically */
for (i=0;i<m;i++) x[i]=0; /* initialize elements of array */

If you later determine that the size of the array has to be changed, you can use the realloc function to do this.

x = realloc(x, m2) /* resize array to m2 elements */

If you use malloc, then when you are done with the array, you have to free it

free(x); /* release the memory */

By using malloc (or calloc, which zeros out the allocated memory) and realloc, you can implement dynamic arrays in C. A free package called ProdList that provides several types of dynamic arrays was written by Bill Pringle Wrp103 is available here (http://www.personal.psu.edu/faculty/w/r/wrp103/class/download/index.html).

Implementations

Implementation of malloc() is highly system and architecture specific. Some operating systems supply an allocator for malloc(), while others supply functions to control certain regions of data.

Note that usually, the same allocator used for malloc() is also used for the new[] keyword in C++. Hence, we will call this the allocator rather than malloc().

Heap based

Implementation of the allocator on IA-32 architectures is commonly done using the heap, or data segment. The allocator will usually expand and contract the heap to fulfill allocation requests.

The heap method suffers from a few inherent flaws, stemming entirely from fragmentation. Like any method of memory allocation, the heap will become fragmented; that is, there will be sections of used and unused memory in the allocated space on the heap. A good allocator will attempt to find an unused area of already allocated memory to use before resorting to expanding the heap.

The major problem with this method is that the heap has only two significant attributes: base, or the beginning of the heap in virtual memory space; and length, or its size. The heap requires enough system memory to fill its entire length, and its base can never change. Thus, any large areas of unused memory are wasted. The heap can get "stuck" in this position if a small used segment exists at the end of the heap, which could waste any magnitude of system RAM, from a few megabytes to a few hundred.

The glibc allocator

The GNU C library, glibc, uses both brk() and mmap() on the Linux operating system. The brk() function will change the size of the heap to be larger or smaller as needed; while the mmap() function will be called when extremely large segments are allocated. The heap method suffers the same flaws as any other, while the mmap() method may avert problems with huge buffers trapping a small allocation at the end after their expiration.

The mmap() method has its own flaws. It always allocates a segment by mapping pages. Only one set of mapped pages exists for each allocated segment. Mapping a single byte will use an entire page, usually 4096 bytes, on IA-32; however, huge pages are 4MiB, 1024 times larger, and so this method could be particularly devastating if userspace uses all huge pages. The advantage to the mmap() method is that when the segment is freed, the memory is returned to the system immediately.

Related concepts

calloc (allocate and clear, i.e. set all values to zero)
nalloc (allocate and set all values to NaN, i.e. to Not a Number)

External links

"Scalable Lock-Free Dynamic Memory Allocation (http://www.research.ibm.com/people/m/michael/pldi-2004.pdf)" by Maged M. Michael

calloc (http://www.opengroup.org/onlinepubs/009695399/functions/calloc.html)

"Inside memory management - The choices, tradeoffs, and implementations of dynamic allocation (http://www-106.ibm.com/developerworks/linux/library/l-memory/)" by Jonathan Bartlett

Retrieved from "http://www.mywiseowl.com/articles/Malloc"

This page has been accessed 107 times. This page was last modified 16:21, 17 Nov 2004. All text is available under the terms of the GNU Free Documentation License (see Copyrights for details).