C standard library (libc) |
---|
General topics |
Miscellaneous headers |
C dynamic memory allocation refers to performing manual memory management for dynamic memory allocation in the C programming language via a group of functions in the C standard library, namely malloc, realloc, calloc, aligned_alloc and free. [1] [2] [3]
The C++ programming language includes these functions; however, the operators new and delete provide similar functionality and are recommended by that language's authors. [4] Still, there are several situations in which using new
/delete
is not applicable, such as garbage collection code or performance-sensitive code, and a combination of malloc
and placement new
may be required instead of the higher-level new
operator.
Many different implementations of the actual memory allocation mechanism, used by malloc, are available. Their performance varies in both execution time and required memory.
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 must be compile-time constant (except for the case of variable-length automatic arrays [5] ). 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 can also cause 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"),[ citation needed ] 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.
The original description of C indicated that calloc
and cfree
were in the standard library, but not malloc
. Code for a simple model implementation of a storage manager for Unix was given with alloc
and free
as the user interface functions, and using the sbrk
system call to request memory from the operating system. [6] The 6th Edition Unix documentation gives alloc
and free
as the low-level memory allocation functions. [7] The malloc
and free
routines in their modern form are completely described in the 7th Edition Unix manual. [8] [9]
Some platforms provide library or intrinsic function calls which allow run-time dynamic allocation from the C stack rather than the heap (e.g. alloca()
[10] ). This memory is automatically freed when the calling function ends.
The C dynamic memory allocation functions are defined in stdlib.h
header (cstdlib
header in C++). [1]
Function | Description |
---|---|
malloc | allocates the specified number of bytes |
aligned_alloc | allocates the specified number of bytes at the specified alignment |
realloc | increases or decreases the size of the specified block of memory, moving it if necessary |
calloc | allocates the specified number of bytes and initializes them to zero |
free | releases the specified block of memory back to the system |
malloc()
and calloc()
malloc()
takes a single argument (the amount of memory to allocate in bytes), while calloc()
takes two arguments — the number of elements and the size of each element.malloc()
only allocates memory, while calloc()
allocates and sets the bytes in the allocated region to zero. [11] Creating an array of ten integers with automatic scope is straightforward in C:
intarray[10];
However, the size of the array is fixed at compile time. If one wishes to allocate a similar array dynamically without using a variable-length array, which is not guaranteed to be supported in all C11 implementations, 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).
Because 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:
int*array=malloc(10*sizeof(int));if(array==NULL){fprintf(stderr,"malloc failed\n");return-1;}
When the program no longer needs the dynamic array, it must eventually call free
to return the memory it occupies to the free store:
free(array);
The memory set aside by malloc
is not initialized and may contain cruft: the remnants of previously used and discarded data. After allocation with malloc
, elements of the array are uninitialized variables. The command calloc
will return an allocation that has already been cleared:
int*array=calloc(10,sizeof(int));
With realloc we can resize the amount of memory a pointer points to. For example, if we have a pointer acting as an array of size and we want to change it to an array of size , we can use realloc.
int*arr=malloc(2*sizeof(int));arr[0]=1;arr[1]=2;arr=realloc(arr,3*sizeof(int));arr[2]=3;
Note that realloc must be assumed to have changed the base address of the block (i.e. if it has failed to extend the size of the original block, and has therefore allocated a new larger block elsewhere and copied the old contents into it). Therefore, any pointers to addresses within the original block are also no longer valid.
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. One may "cast" (see type conversion) this pointer to a specific type:
int*ptr,*ptr2;ptr=malloc(10*sizeof(*ptr));/* without a cast */ptr2=(int*)malloc(10*sizeof(*ptr));/* with a cast */
There are advantages and disadvantages to performing such a cast.
malloc
that originally returned a char *
. [12] malloc()
call (although modern compilers and static analysers can warn on such behaviour without requiring the cast [13] ).stdlib.h
, in which the function prototype for malloc
is found. [12] [14] In the absence of a prototype for malloc
, the C90 standard requires that the C compiler assume malloc
returns an int
. If there is no cast, C90 requires a diagnostic when this integer is assigned to the pointer; however, with the cast, this diagnostic would not be produced, hiding a bug. On certain architectures and data models (such as LP64 on 64-bit systems, where long
and pointers are 64-bit and int
is 32-bit), this error can actually result in undefined behaviour, as the implicitly declared malloc
returns 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 C99 does not permit implicit declarations, so the compiler must produce a diagnostic even if it does assume int
return.malloc
is called and cast.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: [15]
free
leads to buildup 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. 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 free
twice ("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.In addition, as an interface that precedes ANSI C standardization, malloc
and its associated functions have behaviors that were intentionally left to the implementation to define for themselves. One of them is the zero-length allocation, which is more of a problem with realloc
since it is more common to resize to zero. [16] Although both POSIX and the Single Unix Specification require proper handling of 0-size allocations by either returning NULL
or something else that can be safely freed, [17] not all platforms are required to abide by these rules. Among the many double-free errors that it has led to, the 2019 WhatsApp RCE was especially prominent. [18] A way to wrap these functions to make them safer is by simply checking for 0-size allocations and turning them into those of size 1. (Returning NULL
has its own problems: it otherwise indicates an out-of-memory failure. In the case of realloc
it would have signaled that the original memory was not moved and freed, which again is not the case for size 0, leading to the double-free.) [19]
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++. [20]
Implementation of legacy allocators was commonly done using the heap segment. The allocator would usually expand and contract the heap to fulfill allocation requests.
The heap method suffers from a few inherent flaws:
Doug Lea has developed the public domain dlmalloc ("Doug Lea's Malloc") as a general-purpose allocator, starting in 1987. The GNU C library (glibc) is derived from Wolfram Gloger's ptmalloc ("pthreads malloc"), a fork of dlmalloc with threading-related improvements. [21] [22] [23] As of November 2023, the latest version of dlmalloc is version 2.8.6 from August 2012. [24]
dlmalloc is a boundary tag allocator. 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 (similar to a dope vector). Unallocated chunks also store pointers to other free chunks in the usable space area, making the minimum chunk size 16 bytes on 32-bit systems and 24/32 (depends on alignment) bytes on 64-bit systems. [22] [24] : 2.8.6, Minimum allocated size
Unallocated memory is grouped into "bins" of similar sizes, implemented by using a double-linked list of chunks (with pointers stored in the unallocated space inside the chunk). Bins are sorted by size into three classes: [22] [24] : Overlaid data structures
Game developer Adrian Stone argues that dlmalloc
, as a boundary-tag allocator, is unfriendly for console systems that have virtual memory but do not have demand paging. This is because its pool-shrinking and growing callbacks (sysmalloc
/systrim
) cannot be used to allocate and commit individual pages of virtual memory. In the absence of demand paging, fragmentation becomes a greater concern. [27]
Since FreeBSD 7.0 and NetBSD 5.0, the old malloc
implementation (phkmalloc
by Poul-Henning Kamp) 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. [28]
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
. [29] [ better source needed ] 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 GrapheneOS project initially started out by porting OpenBSD's memory allocator to Android's Bionic C Library. [30]
Hoard 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. [31]
An open-source compact general-purpose memory allocator from Microsoft Research with focus on performance. [32] The library is about 11,000 lines of code.
Every thread has a thread-local storage for small allocations. For large allocations mmap or sbrk can be used. TCMalloc, a malloc developed by Google, [33] 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. [34] [35]
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. [36] This necessitates a malloc
implementation tightly integrated with the virtual memory subsystem of the operating system kernel.
Because malloc
and its relatives can have a strong impact on the performance of a program, it is not uncommon to override the functions for a specific application by custom implementations that are optimized for application's allocation patterns. The C standard provides no way of doing this, but operating systems have found various ways to do this by exploiting dynamic linking. One way is to simply link in a different library to override the symbols. Another, employed by Unix System V.3, is to make malloc
and free
function pointers that an application can reset to custom functions. [37]
The most common form on POSIX-like systems is to set the environment variable LD_PRELOAD with the path of the allocator, so that the dynamic linker uses that version of malloc/calloc/free instead of the libc implementation.
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. In the C99 standard and later, it is available as the SIZE_MAX
constant from < stdint.h >
. Although not guaranteed by ISO C, it is usually 2^(CHAR_BIT * sizeof(size_t)) - 1
.
On glibc systems, the largest possible memory block malloc
can allocate is only half this size, namely 2^(CHAR_BIT * sizeof(ptrdiff_t) - 1) - 1
. [38]
The C library implementations shipping with various operating systems and compilers may come with alternatives and extensions to the standard malloc
interface. Notable among these is:
alloca
, which allocates a requested number of bytes on the call stack. No corresponding deallocation function exists, as typically the memory is deallocated as soon as the calling function returns. alloca
was present on Unix systems as early as 32/V (1978), but its use can be problematic in some (e.g., embedded) contexts. [39] While supported by many compilers, it is not part of the ANSI-C standard and therefore may not always be portable. It may also cause minor performance problems: it leads to variable-size stack frames, so that both stack and frame pointers need to be managed (with fixed-size stack frames, one of these is redundant). [40] Larger allocations may also increase the risk of undefined behavior due to a stack overflow. [41] C99 offered variable-length arrays as an alternative stack allocation mechanism – however, this feature was relegated to optional in the later C11 standard.posix_memalign
that allocates memory with caller-specified alignment. Its allocations are deallocated with free
, [42] so the implementation usually needs to be a part of the malloc library.In programming and information security, a buffer overflow or buffer overrun is an anomaly whereby a program writes data to a buffer beyond the buffer's allocated memory, overwriting adjacent memory locations.
C is a general-purpose programming language. It was created in the 1970s by Dennis Ritchie and remains very widely used and influential. By design, C's features cleanly reflect the capabilities of the targeted CPUs. It has found lasting use in operating systems code, device drivers, and protocol stacks, but its use in application software has been decreasing. C is commonly used on computer architectures that range from the largest supercomputers to the smallest microcontrollers and embedded systems.
Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed. This is critical to any advanced computer system where more than a single process might be underway at any time.
A Berkeley (BSD) socket is an application programming interface (API) for Internet domain sockets and Unix domain sockets, used for inter-process communication (IPC). It is commonly implemented as a library of linkable modules. It originated with the 4.2BSD Unix operating system, which was released in 1983.
A heap overflow, heap overrun, or heap smashing is a type of buffer overflow that occurs in the heap data area. Heap overflows are exploitable in a different manner to that of stack-based overflows. Memory on the heap is dynamically allocated at runtime and typically contains program data. Exploitation is performed by corrupting this data in specific ways to cause the application to overwrite internal structures such as linked list pointers. The canonical heap overflow technique overwrites dynamic memory allocation linkage and uses the resulting pointer exchange to overwrite a program function pointer.
Valgrind is a programming tool for memory debugging, memory leak detection, and profiling.
The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.
In computer science, a pointer is an object in many programming languages that stores a memory address. This can be that of another value located in computer memory, or in some cases, that of memory-mapped computer hardware. A pointer references a location in memory, and obtaining the value stored at that location is known as dereferencing the pointer. As an analogy, a page number in a book's index could be considered a pointer to the corresponding page; dereferencing such a pointer would be done by flipping to the page with the given page number and reading the text found on that page. The actual format and content of a pointer variable is dependent on the underlying computer architecture.
In computing, mmap(2)
is a POSIX-compliant Unix system call that maps files or devices into memory. It is a method of memory-mapped file I/O. It implements demand paging because file contents are not immediately read from disk and initially use no physical RAM at all. The actual reads from disk are performed after a specific location is accessed, in a lazy manner. After the mapping is no longer needed, the pointers must be unmapped with munmap(2)
. Protection information—for example, marking mapped regions as executable—can be managed using mprotect(2)
, and special treatment can be enforced using madvise(2)
.
Address space layout randomization (ASLR) is a computer security technique involved in preventing exploitation of memory corruption vulnerabilities. In order to prevent an attacker from reliably redirecting code execution to, for example, a particular exploited function in memory, ASLR randomly arranges the address space positions of key data areas of a process, including the base of the executable and the positions of the stack, heap and libraries.
In computing, a data segment is a portion of an object file or the corresponding address space of a program that contains initialized static variables, that is, global variables and static local variables. The size of this segment is determined by the size of the values in the program's source code, and does not change at run time.
Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out (LIFO) manner.
The Boehm–Demers–Weiser garbage collector, often simply known as the Boehm GC or Boehm collector, is a conservative garbage collector for C and C++ developed by Hans Boehm, Alan Demers, and Mark Weiser.
Data structure alignment is the way data is arranged and accessed in computer memory. It consists of three separate but related issues: data alignment, data structure padding, and packing.
In the C++ programming language, new and delete are a pair of language constructs that perform dynamic memory allocation, object construction and object destruction.
sizeof is a unary operator in the programming languages C and C++. It generates the storage size of an expression or a data type, measured in the number of char-sized units. Consequently, the construct sizeof (char) is guaranteed to be 1. The actual number of bits of type char is specified by the preprocessor macro CHAR_BIT, defined in the standard include file limits.h. On most modern computing platforms this is eight bits. The result of sizeof has an unsigned integer type that is usually denoted by size_t.
mtrace
is the memory debugger included in the GNU C Library.
In computer programming, a variable-length array (VLA), also called variable-sized or runtime-sized, is an array data structure whose length is determined at runtime, instead of at compile time. In the language C, the VLA is said to have a variably modified data type that depends on a value.
brk and sbrk are basic memory management system calls used in Unix and Unix-like operating systems to control the amount of memory allocated to the heap segment of the process. These functions are typically called from a higher-level memory management library function such as malloc. In the original Unix system, brk and sbrk were the only ways in which applications could acquire additional heap space; later versions allowed this to also be done using the mmap call.
qsort is a C standard library function that implements a sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm, which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort.
calloc
and cfree
, and Section 8.7 (page 173) describes an implementation for alloc
and free
.man
page for malloc
etc. is given on page 275.