C dynamic memory allocation
|C standard library|
C dynamic memory allocation refers to performing dynamic memory allocation in the C programming language via a group of functions in the C standard library, namely
Many different implementations of the actual memory allocation mechanism, used by
malloc, are available. Their performance varies in both execution time and required memory.
- 1 Rationale
- 2 Overview of functions
- 3 Usage example
- 4 Type safety
- 5 Common errors
- 6 Implementations
- 7 Allocation size limits
- 8 See also
- 9 References
- 10 External links
The C programming language manages memory statically, automatically, or dynamically. Static-duration variables are allocated in main memory, usually along with the executable code of the program, and persist for the lifetime of the program; automatic-duration variables are allocated on the stack and come and go as functions are called and return. For static-duration and automatic-duration variables, the size of the allocation is required to be compile-time constant (before C99, which allows variable-length automatic arrays). If the required size is not known until run-time (for example, if data of arbitrary size is being read from the user or from a disk file), then using fixed-size data objects is inadequate.
The lifetime of allocated memory is also a concern. Neither static- nor automatic-duration memory is adequate for all situations. Automatic-allocated data cannot persist across multiple function calls, while static data persists for the life of the program whether it is needed or not. In many situations the programmer requires greater flexibility in managing the lifetime of allocated memory.
These limitations are avoided by using dynamic memory allocation in which memory is more explicitly (but more flexibly) managed, typically, by allocating it from the free store (informally called the "heap"), an area of memory structured for this purpose. In C, the library function
malloc is used to allocate a block of memory on the heap. The program accesses this block of memory via a pointer that
malloc returns. When the memory is no longer needed, the pointer is passed to
free which deallocates the memory so that it can be used for other purposes.
Some platforms provide library calls which allow run-time dynamic allocation from the C stack rather than the heap (e.g. Unix
alloca(), Microsoft Windows CRTL's
malloca()). This memory is automatically freed when the calling function ends. The need for this is lessened by changes in the C99 standard, which added support for variable-length arrays of block scope having sizes determined at runtime.
Overview of functions
The C dynamic memory allocation functions are defined in
stdlib.h header (
cstdlib header in C++).
||allocates the specified number of bytes|
||increases or decreases the size of the specified block of memory. Reallocates it if needed|
||allocates the specified number of bytes and initializes them to zero|
||releases the specified block of memory back to the system|
There are two differences between these functions. First,
malloc() takes a single argument (the amount of memory to allocate in bytes), while
calloc() needs two arguments (the number of variables to allocate in memory, and the size in bytes of a single variable). Secondly,
malloc() does not initialize the memory allocated, while
calloc() initializes all bytes of the allocated memory block to zero.
Creating an array of ten integers with automatic scope is straightforward in C:
However, the size of the array is fixed at compile time. If one wishes to allocate a similar array dynamically, the following code can be used:
int * array = malloc(10 * sizeof(int));
This computes the number of bytes that ten integers occupy in memory, then requests that many bytes from
malloc and assigns the result to a pointer named
array (due to C syntax, pointers and arrays can be used interchangeably in some situations).
malloc might not be able to service the request, it might return a null pointer and it is good programming practice to check for this. When the program no longer needs the dynamic array, it should call
free(array); to return the memory it occupies to the free store.
malloc returns a void pointer (
void *), which indicates that it is a pointer to a region of unknown data type. The use of casting is required in C++ due to the strong type system, whereas this is not the case in C. The lack of a specific pointer type returned from
malloc is type-unsafe behaviour according to some programmers:
malloc allocates based on byte count but not on type. This is different from the C++ new operator that returns a pointer whose type relies on the operand. (See C Type Safety.)
One may "cast" (see type conversion) this pointer to a specific type:
int *ptr; ptr = malloc(10 * sizeof (*ptr)); /* without a cast */ ptr = (int *)malloc(10 * sizeof (*ptr)); /* with a cast */ ptr = reinterpret_cast<int *>(malloc(10 * sizeof (*ptr))); /* with a cast, for C++ */
There are advantages and disadvantages to performing such a cast.
Advantages to casting
- Including the cast allows a program or function to compile as C++.
- The cast allows for pre-1989 versions of
mallocthat originally returned a
- Casting can help the developer identify inconsistencies in type sizing should the destination pointer type change, particularly if the pointer is declared far from the
Disadvantages to casting
- Under the ANSI C standard, the cast is redundant.
- Adding the cast may mask failure to include the header
stdlib.h, in which the prototype for
mallocis found. In the absence of a prototype for
malloc, the standard requires that the C compiler assume
int. If there is no cast, a warning is issued when this integer is assigned to the pointer; however, with the cast, this warning is not produced, hiding a bug. On certain architectures and data models (such as LP64 on 64-bit systems, where
longand pointers are 64-bit and
intis 32-bit), this error can actually result in undefined behaviour, as the implicitly declared
mallocreturns a 32-bit value whereas the actually defined function returns a 64-bit value. Depending on calling conventions and memory layout, this may result in stack smashing. This issue is less likely to go unnoticed in modern compilers, as they uniformly produce warnings that an undeclared function has been used, so a warning will still appear. For example, GCC's default behaviour is to show a warning that reads "incompatible implicit declaration of built-in function" regardless of whether the cast is present or not.
- If the type of the pointer is changed, one must fix all code lines where
mallocwas called and cast (unless it was cast to a
The improper use of dynamic memory allocation can frequently be a source of bugs. These can include security bugs or program crashes, most often due to segmentation faults.
Most common errors are as follows:
- Not checking for allocation failures. Memory allocation is not guaranteed to succeed, and may instead return a null pointer. If there's no check for successful allocation implemented, this usually leads to a crash of the program, due to the resulting segmentation fault on the null pointer dereference.
- Memory leaks. Failure to deallocate memory using
freeleads to build up of non-reusable memory, which is no longer used by the program. This wastes memory resources and can lead to allocation failures when these resources are exhausted.
- Logical errors. All allocations must follow the same pattern: allocation using
malloc, usage to store data, deallocation using
free. Failures to adhere to this pattern, such as memory usage after a call to
free(dangling pointer) or before a call to
malloc(wild pointer), calling
freetwice ("double free"), etc., usually causes a segmentation fault and results in a crash of the program. These errors can be transient and hard to debug – for example, freed memory is usually not immediately reclaimed by the OS, and thus dangling pointers may persist for a while and appear to work.
The implementation of memory management depends greatly upon operating system and architecture. Some operating systems supply an allocator for malloc, while others supply functions to control certain regions of data. The same dynamic memory allocator is often used to implement both
malloc and the operator
new in C++ . Hence, it is referred to below as the allocator rather than
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 address space, from a few megabytes to a few hundred.
Memory on the heap is allocated as "chunks", an 8-byte aligned data structure which contains a header and usable memory. Allocated memory contains an 8 or 16 byte overhead for the size of the chunk and usage flags. Unallocated chunks also store pointers to other free chunks in the usable space area, making the minimum chunk size 24 bytes.
For requests below 256 bytes (a "smallbin" request), a simple two power best fit allocator is used. If there are no free blocks in that bin, a block from the next highest bin is split in two.
For requests of 256 bytes or above but below the mmap threshold, recent versions of dlmalloc use an in-place bitwise trie algorithm. If there is no free space left to satisfy the request, dlmalloc tries to increase the size of the heap, usually via the brk system call.
For requests above the mmap threshold (a "largebin" request), the memory is always allocated using the mmap system call. The threshold is usually 256 KB. The mmap method averts problems with huge buffers trapping a small allocation at the end after their expiration, but always allocates an entire page of memory, which on many architectures is 4096 bytes in size.
FreeBSD's and NetBSD's jemalloc
Since FreeBSD 7.0 and NetBSD 5.0, the old
malloc implementation (phkmalloc) was replaced by jemalloc, written by Jason Evans. The main reason for this was a lack of scalability of phkmalloc in terms of multithreading. In order to avoid lock contention, jemalloc uses separate "arenas" for each CPU. Experiments measuring number of allocations per second in multithreading application have shown that this makes it scale linearly with the number of threads, while for both phkmalloc and dlmalloc performance was inversely proportional to the number of threads.
OpenBSD's implementation of the
malloc function makes use of
mmap. For requests greater in size than one page, the entire allocation is retrieved using
mmap; smaller sizes are assigned from memory pools maintained by
malloc within a number of "bucket pages," also allocated with
mmap. On a call to
free, memory is released and unmapped from the process address space using
munmap. This system is designed to improve security by taking advantage of the address space layout randomization and gap page features implemented as part of OpenBSD's
mmap system call, and to detect use-after-free bugs—as a large memory allocation is completely unmapped after it is freed, further use causes a segmentation fault and termination of the program.
The Hoard memory allocator is an allocator whose goal is scalable memory allocation performance. Like OpenBSD's allocator, Hoard uses
mmap exclusively, but manages memory in chunks of 64 kilobytes called superblocks. Hoard's heap is logically divided into a single global heap and a number of per-processor heaps. In addition, there is a thread-local cache that can hold a limited number of superblocks. By allocating only from superblocks on the local per-thread or per-processor heap, and moving mostly-empty superblocks to the global heap so they can be reused by other processors, Hoard keeps fragmentation low while achieving near linear scalability with the number of threads.
Thread-caching malloc (tcmalloc)
Every thread has local storage for small allocations. For large allocations mmap or sbrk can be used. TCMalloc, a malloc developed by Google, has garbage-collection for local storage of dead threads. The TCMalloc is considered to be more than twice as fast as glibc's ptmalloc for multithreaded programs.
Operating system kernels need to allocate memory just as application programs do. The implementation of
malloc within a kernel often differs significantly from the implementations used by C libraries, however. For example, memory buffers might need to conform to special restrictions imposed by DMA, or the memory allocation function might be called from interrupt context. This necessitates a
malloc implementation tightly integrated with the virtual memory subsystem of the operating system kernel.
Allocation size limits
The largest possible memory block
malloc can allocate depends on the host system, particularly the size of physical memory and the operating system implementation. Theoretically, the largest number should be the maximum value that can be held in a
size_t type, which is an implementation-dependent unsigned integer representing the size of an area of memory. The maximum value is 2CHAR_BIT × sizeof(size_t) − 1, or the constant
SIZE_MAX in the C99 standard.
- ISO/IEC 9899:1999 specification. p. 313, § 7.20.3 "Memory management functions".
- Godse, Atul P.; Godse, Deepali A. (2008). Advanced C Programming. p. 6-28: Technical Publications. p. 400. ISBN 978-81-8431-496-0.
- Summit, Steve. "C Programming Notes - Chapter 11: Memory Allocation". Retrieved 30 October 2011.
- Stroustrup, Bjarne (2008). Programming: Principles and Practice Using C++. 1009, §27.4 Free store: Addison Wesley. p. 1236. ISBN 978-0-321-54372-1.
- "gcc manual". gnu.org. Retrieved 14 December 2008.
- "alloca". Man.freebsd.org. 5 September 2006. Retrieved 18 September 2011.
malloca()". MSDN Visual C++ Developer Center. Retrieved 12 March 2009.
- "Casting malloc". Cprogramming.com. Retrieved 9 March 2007.
- comp.lang.c "FAQ list · Question 7.7b". C-FAQ. Retrieved 9 March 2007.
- Wolfram Gloger's malloc homepage
- Kaempf, Michel (2001). "Vudo malloc tricks". Phrack (57): 8. Retrieved 29 April 2009.
- "Malloc Tunable Parameters". GNU. Retrieved 2 May 2009.
- Sanderson, Bruce (12 December 2004). "RAM, Virtual Memory, Pagefile and all that stuff". Microsoft Help and Support.
- Evans, Jason (16 April 2006). "A Scalable Concurrent malloc(3) Implementation for FreeBSD". Retrieved 18 March 2012.
- Berger, Emery D.; McKinley, Kathryn S.; Blumofe, Robert D.; Wilson, Paul R. (2000). "Hoard: A Scalable Memory Allocator for Multithreaded Applications". Retrieved 18 March 2012.
- TCMalloc homepage
- Ghemawat, Sanjay; Menage, Paul; TCMalloc : Thread-Caching Malloc
- Callaghan, Mark (18 January 2009). "High Availability MySQL: Double sysbench throughput with TCMalloc". Mysqlha.blogspot.com. Retrieved 18 September 2011.
- "kmalloc()/kfree() include/linux/slab.h". People.netfilter.org. Retrieved 18 September 2011.
|The Wikibook C Programming has a page on the topic of: C Programming/C Reference|
- Definition of malloc in IEEE Std 1003.1 standard
- Lea, Doug; The design of the basis of the glibc allocator
- Gloger, Wolfram; The ptmalloc homepage
- Berger, Emery; The Hoard homepage
- Douglas, Niall; The nedmalloc homepage
- Evans, Jason; The jemalloc homepage
- Simple Memory Allocation Algorithms on OSDEV Community
- Berger, Emery; Hoard: A Scalable Memory Allocator for Multithreaded Applications
- Michael, Maged M.; Scalable Lock-Free Dynamic Memory Allocation
- Bartlett, Jonathan; Inside memory management - The choices, tradeoffs, and implementations of dynamic allocation
- Memory Reduction (GNOME) wiki page with lots of information about fixing malloc
- C99 standard draft, including TC1/TC2/TC3
- Some useful references about C
- ISO/IEC 9899 – Programming languages – C