In computing,
malloc is a
subroutineIn computer science, a subroutine or subprogram is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code....
for performing
dynamic memory allocationIn computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program...
in the
CC is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
programming languages. It is part of the
standard libraryA standard library for a programming language is the library that is conventionally made available in every implementation of that language. In some cases, the library is described directly in the programming language specification; in other cases, the contents of the standard library are...
for both languages. Many implementations of
malloc are available, each of which performs differently depending on the computing hardware and how a program is written. Performance varies in both execution time and required memory. Programs must properly manage dynamic memory allocated through the use of
malloc to avoid memory leaks and memory corruption.
Rationale
The C
programming languageA programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human...
manages memory
staticallyStatic memory allocation refers to the process of allocating memory at compile-time before the associated program is executed, unlike dynamic memory allocation or automatic memory allocation where memory is allocated as required at run-time....
,
automaticallyIn computer programming, an automatic variable is a lexically-scoped variable which is allocated and de-allocated automatically when program flow enters and leaves the variable's scope...
, or
dynamicallyIn computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program...
. Static-duration variables are allocated in main (fixed) memory and persist for the lifetime of the program; automatic-duration variables are allocated on the
stackIn computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, function stack, or run-time stack, and is often shortened to just "the stack"...
and come and go as functions are called and return. For static-duration and, before
C99C99 is a modern dialect of the C programming language. It extends the previous version to better make use of available computer hardware and to better employ the latest advances in compiler technology....
(which allows variable-length automatic arrays), automatic-duration variables, the size of the allocation is required to be compile-time constant. 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 allocationIn computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program...
in which memory is more explicitly (but more flexibly) managed, typically, by allocating it from
the heapIn computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program...
, 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. glibc's
alloca,
Microsoft WindowsMicrosoft Windows is a series of software operating systems and graphical user interfaces produced by Microsoft. Microsoft first introduced an operating environment named Windows in November 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces...
CRTL's
malloca). This memory is automatically freed when the calling function ends. The need for this is lessened by changes in the
C99C99 is a modern dialect of the C programming language. It extends the previous version to better make use of available computer hardware and to better employ the latest advances in compiler technology....
standard, which added support for
variable-length arrayIn programming, a variable-length array is an array data structure of automatic storage duration whose length is determined at run time ....
s of block scope having sizes determined at runtime.
Dynamic memory allocation in C
The
malloc function is one of the functions in standard C to allocate memory. Its
function prototypeA function prototype in C or C++ is a declaration of a function that omits the function body but does specify the function's name, arity, argument types and return type...
is
void *malloc(size_t size);
which allocates
size bytes of memory. If the allocation succeeds, a pointer to the block of memory is returned, otherwise a NULL pointer is returned.
Upon successful allocation,
malloc returns a void pointer (
void *), which indicates that it is a pointer to a region of unknown data type. It need
not be explicitly cast to a more specific pointer type, since ANSI C defines an implicit conversion between the void pointer type and other pointers to objects. An explicit cast of
malloc's return value is sometimes performed because
malloc originally returned a
char *, but this cast is unnecessary in standard C code. Omitting the cast, however, creates an incompatibility with
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
, which does require it.
Memory allocated via
malloc is persistent: it will continue to exist until the program terminates or the memory is explicitly deallocated by the programmer (that is, the block is said to be "freed"). This is achieved by use of the
free function. Its prototype is
void free(void *pointer);
which releases the block of memory pointed to by
pointer.
pointer must have been previously returned by
malloc,
calloc, or
realloc and must only be passed to
free once.
Usage example
The standard method of creating an array of 10 int objects:
int array[10];
However, if one wishes to allocate a similar array dynamically, the following code could be used:
/* Allocate space for an array with ten elements of type int. */
int *ptr = malloc(10 * sizeof (int));
if (ptr NULL) {
/* Memory could not be allocated, the program should handle the error here as appropriate. */
} else {
/* Allocation succeeded. Do something. */
free(ptr); /* We are done with the int objects, and free the associated pointer. */
ptr = NULL; /* The pointer must not be used again, unless re-assigned to using malloc again. */
}
malloc returns a null pointer to indicate that no memory is available, or that some other error occurred which prevented memory being allocated.
One may sometimes see code in which the value returned by
malloc is "cast"
(see
type conversionIn computer science, type conversion or typecasting refers to changing an entity of one data type into another. This is done to take advantage of certain features of type hierarchies...
) to a specific type, as in
int *ptr = (int*)malloc(10 * sizeof (int));
But this is considered bad practice; it is redundant under the C standard, as noted above and moreover, putting in a cast may mask failure to include the header,
stdlib.h, in which the prototype for
malloc is found. In the absence of a prototype for
malloc, the C compiler will assume that
malloc returns an
int, and will issue a warning in a context such as the above, provided the error
is not masked by a cast.
A useful idiom with
malloc is shown in this example:
int *ptr = malloc(10 * sizeof *ptr);
That is, instead of writing a hard-wired type into the argument to malloc, one
uses the
sizeof operator on the content of the pointer to be allocated.
This ensures that the types on the left and right of the assignment will never get
out of sync when code is revised.
calloc
malloc returns a block of memory that is allocated for the programmer to use, but is uninitialized. The memory is usually initialized by hand if necessary—either via the
memset function, or by one or more assignment statements that dereference the pointer. An alternative is to use the
calloc function, which allocates memory and then initializes it. Its prototype is
void *calloc(size_t nelements, size_t elementSize);
which allocates a region of memory, initialized to 0, of size
nelements ×
elementSize.
realloc
It is often useful to be able to grow or shrink a block of memory. This can be done using
realloc which returns a pointer to a memory region of the specified size, which contains the same data as the old region pointed to by
pointer (truncated to the minimum of the old and new sizes). If
realloc is unable to resize the memory region in place, it allocates new storage, copies the required data, and frees the old pointer. If this allocation fails,
realloc maintains the original pointer unaltered, and returns the null pointer value. The newly allocated region of memory is uninitialized (its contents are not predictable). The function prototype is
void *realloc(void *pointer, size_t size);
realloc behaves like
malloc if the first argument is NULL:
void *p = malloc(42);
void *p = realloc(NULL, 42); /* equivalent */
In the C89 standard, realloc with length 0 is the same as a free. In the C99 standard, this is no longer the case; here, the allocated memory block is reduced in size to zero bytes and a non-NULL pointer is returned (which cannot be directly dereferenced, since it points at no allocated memory, but it can be used in future calls to realloc and free).
When using
realloc, one should always use a temporary
variable. For example
void *p = malloc(orig_size);
/* and later... */
void *tmp = realloc(p, big_size);
if (tmp != NULL) {
p = tmp; /* OK, assign new, larger storage to p */
} else {
/* handle the problem somehow */
}
If instead one did
void *p = malloc(orig_size);
/* and later... */
p = realloc(p, big_size);
and if it is not possible to obtain
big_size bytes of
memory, then p will have value NULL and we no longer have a pointer to the memory
previously allocated for p, creating a memory leak (see below).
Common errors
The improper use of
malloc and related functions can frequently be a source of bugs.
Allocation failure
malloc is not guaranteed to succeed — if there is no memory available, or if the program has exceeded the amount of memory it is allowed to reference,
malloc will return a null pointer. Many programs do not check for
malloc failure. Such a program would attempt to use the null pointer returned by
malloc as if it pointed to allocated memory, and the program would crash.
Memory leaks
When a call to
malloc,
calloc or
realloc succeeds, the return value of the call should eventually be passed to the
free function. This releases the allocated memory, allowing it to be reused to satisfy other memory allocation requests. If this is not done, the allocated memory will not be released until the process exits (and in some environments, not even then) — in other words, a
memory leakA memory leak or leakage in computer science is a particular type of memory consumption by a computer program where the program is unable to release memory it has acquired...
will occur. Typically, memory leaks are caused by losing track of pointers, for example not using a temporary pointer for the return value of
realloc, which may lead to the original pointer being overwritten with a null pointer, for example:
void *ptr;
size_t size = BUFSIZ;
ptr = malloc(size);
/* some further execution happens here... */
/* now the buffer size needs to be doubled */
if (size > SIZE_MAX / 2) {
/* handle overflow error */
/* ... */
return (1);
}
size *= 2;
ptr = realloc(ptr, size);
if (ptr NULL) {
/* the realloc failed (it returned a null pointer), but the original address in ptr has been lost
so the memory cannot be freed and a leak has occurred */
/* ... */
return 1;
}
/* ... */
Use after free
After a pointer has been passed to
free, it becomes a
dangling pointerDangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type.Dangling pointers arise when an object is deleted or deallocated, without modifying the value of the pointer, so that the pointer still points to the memory location...
: it references a region of memory with undefined content, which may not be available for use. The pointer's value cannot be accessed. For example:
int *ptr = malloc(sizeof (int));
free(ptr);
- ptr = 0; /* Undefined behavior */
Code like this has undefined behavior: its effect may vary. Even attempting to print the variable with
printfprintf functions are a class of functions typically associated with curly bracket programming languages. They accept a string parameter called the format string, which specifies a method for rendering an arbitrary number of varied data type parameter into a string...
is undefined behavior (assuming
malloc did not return a null pointer); for example:
printf("%p", (void *) ptr); /* Undefined behavior */
Commonly, the system may have reused freed memory for other purposes. Therefore, writing through a pointer to a deallocated region of memory may result in overwriting another piece of data somewhere else in the program. Depending on what data is overwritten, this may result in data corruption or cause the program to crash at a later time. A particularly bad example of this problem is if the same pointer is passed to
free twice, known as a
double free. To avoid this, some programmers set pointers to
NULL after passing them to
free:
free(NULL) is safe (it does nothing). However, this will not protect other aliases to the same pointer from being doubly freed.
Best practice is that a pointer passes out of scope immediately after being freed.
Freeing unallocated memory
Another problem is when
free is passed an address that wasn't allocated by
malloc,
realloc or
calloc. This can be caused when a pointer to a literal string or the name of a declared array is passed to
free, for example:
char *msg = "Default message";
int tbl[100];
Passing either of the above pointers to
free will result in undefined behaviour.
Implementations
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
operator new in
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
. Hence, it is referred to below as the
allocator rather than
malloc.
Heap-based
Implementation of the allocator on
IA-32IA-32 , often generically called x86, x86-32 or i386, is the instruction set architecture of Intel's most commercially successful microprocessors yet. It is a 32-bit extension, first implemented in the Intel 80386, of the earlier 16-bit Intel 8086, 80186 and 80286 processors and the common...
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
fragmentationIn computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases performance. The term is also used to denote the wasted space itself....
. 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.
dlmalloc (the glibc allocator)
Since 2.3 release
GNU C libraryThe GNU C Library, commonly known as glibc, is the C standard library released by the GNU Project. Originally written by the Free Software Foundation for the GNU operating system, the library's development has been overseen by a committee since 2001, with Ulrich Drepper from Red Hat as the lead...
(glibc) uses a
modified ptmalloc2, based on "
Doug LeaDoug Lea is a professor of computer science at State University of New York at Oswego where he specializes in concurrent programming. He is on the Executive Committee of the Java Community Process and chaired JSR 166, which added concurrency utilities to the Java programming language .He wrote...
's Malloc" (
dlmalloc).
Memory on the heap is allocated as "chunks", an 8-byte
alignedData structure alignment is the way data is arranged and accessed in computer memory. It consists of two separate but related issues: data alignment and data structure padding. When a modern computer reads from or writes to a memory address, it will do this in word sized chunks...
data structureIn computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
which contains a header and usable memory. Allocated memory contains 4 bytes 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.
Unallocated memory is grouped into "
binsIn computational geometry, the bin data structure allows efficient region queries, i.e., if there are some axis-aligned rectangles on a 2D plane, answer the question Given a query rectangle, return all rectangles intersecting it. kd-tree is another data structure that can answer this question...
" of similar sizes, implemented by using a double-linked list of chunks (with pointers stored in the unallocated space inside the chunk).
If additional memory needs to be allocated, dlmalloc often uses the
brk call to the
Linux kernelThe Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
to increase the size of the heap. Increasing the size of the heap increases the size of the top-most chunk (wilderness chunk), which is always unallocated, and is treated specially by malloc.
For requests above a threshold, the memory is allocated using the
mmap system call. The threshold is 1 megabyte by default, but can be changed using environment variables. The mmap method averts problems with huge buffers trapping a small allocation at the end after their expiration, but always allocates an entire
pageIn a context of computer virtual memory, a page, memory page, or virtual page is a fixed-length block of main memory, that is contiguous in both physical memory addressing and virtual memory addressing...
of memory, which on many architectures are 4096 bytes in size. See Sanderson, Bruce. "
RAM, Virtual Memory, Pagefile and all that stuff",
Microsoft Help and Support, 2004-12-12.
OpenBSD's malloc
OpenBSDOpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley. It was forked from NetBSD by project leader Theo de Raadt in late 1995...
'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 spaceIn computing, an address space defines a range of discrete addresses, each of which may correspond to a physical or virtual memory register, a network host, peripheral device, disk sector or other logical or physical entity...
using
munmap. This system is designed to improve security by taking advantage of the
address space layout randomizationAddress space layout randomization is a computer security technique which involves randomly arranging the positions of key data areas, usually including the base of the executable and position of libraries, heap, and stack, in a process's address space.- Benefits :Address space randomization...
and gap page features implemented as part of OpenBSD's
mmap system callIn computing, a system call is the mechanism used by an application program to request service from the operating system based on the monolithic kernel or to system servers on operating systems based on the microkernel-structure.- Background :...
, and to detect use-after-free bugs—as a large memory allocation is completely unmapped after it is freed, further use causes a
segmentation faultA segmentation fault is a particular error condition that can occur during the operation of computer software...
and termination of the program.
Hoard's malloc
The
Hoard memory allocatorThe Hoard memory allocator, or Hoard, is a memory allocator for Linux, Solaris, Microsoft Windows and other operating systems. Hoard is designed to be efficient when used by multithreaded applications on multiprocessor computers...
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.
http://www.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf
In-kernel
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
DMADirect memory access is a feature of modern computers and microprocessors that allows certain hardware subsystems within the computer to access system memory for reading and/or writing independently of the central processing unit. Many hardware systems use DMA including disk drive controllers,...
, or the memory allocation function might be called from interrupt context
http://people.netfilter.org/~rusty/unreliable-guides/kernel-hacking/routines-kmalloc.html. This necessitates a
malloc implementation tightly integrated with the
virtual memoryVirtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory , while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications...
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
28*sizeof(size_t) − 1, or the constant
SIZE_MAX in the C99 standard. For a 32 bit architecture, this is
232 - 1.
See also
- Buffer overflow
In computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a process stores data in a buffer outside the memory the programmer set aside for it. The extra data overwrites adjacent memory, which may contain other data, including program variables and program...
- Memory debugger
A memory debugger is a programming tool for finding memory leaks and buffer overflows. These are due to bugs related to the allocation and deallocation of dynamic memory. Programs written in languages that have garbage collection, such as managed code, might also need memory debuggers, e.g...
mprotectIn Unix-like operating systems, mprotect is a POSIX system call for controlling memory protections.-External links:* ***...
new (C++)- Page size
- Variable-length array
In programming, a variable-length array is an array data structure of automatic storage duration whose length is determined at run time ....
External links