Malloc 384289 224528626 2008-07-09T07:23:35Z Dampam 7440585 /* External links */ Link wasn't valid, gave HTTP 403 error. {{lowercase|title=malloc}} In [[computing]], <code>'''malloc'''</code> is a [[subroutine]] provided in the [[C (programming language)|C programming language]]'s and [[C++|C++ programming language]]'s [[standard library]] for performing [[dynamic memory allocation]]. == Rationale == The [[C Programming Language|C]] [[programming language]] manages [[memory (computers)|memory]] either ''[[Static memory allocation|statically]]'' or ''[[Automatic memory allocation|automatically]]''. Static-duration variables are allocated in main (fixed) memory and persist for the lifetime of the program; automatic-duration variables are allocated on the [[call stack|stack]] and come and go as functions are called and return. For static-duration and, until [[C99]] which allows variable-sized arrays, automatic-duration variables, the size of the allocation must be a [[compile-time]] constant. If the required size will not be known until [[run-time]] &mdash; for example, if data of arbitrary size is being read from the user or from a disk file &mdash; using fixed-size data objects is inadequate. Some platforms provide the <code>alloca</code> function,<ref>[http://www.gnu.org/software/libc/manual/html_node/Variable-Size-Automatic.html libc manual] on gnu.org accessed at [[March 9]] [[2007]]</ref> which allows run-time allocation of variable-sized automatic variables on the stack. [[C99]] supports [[variable-length array]]s of block scope having sizes determined at runtime. The lifetime of allocated memory is also a concern. Neither static- nor automatic-duration memory is adequate for all situations. Stack-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 a ''[[Dynamic memory allocation|heap]]'', an area of memory structured for this purpose. In C, one uses the library function <code>malloc</code> to allocate a block of memory on the heap. The program accesses this block of memory via a [[pointer]] which <code>malloc</code> returns. When the memory is no longer needed, the pointer is passed to <code>free</code> which deallocates the memory so that it can be used for other purposes. ==Dynamic memory allocation in C== The <code>malloc</code> function is one of the functions in standard C to allocate memory. Its [[function prototype]] is <source lang="c"> void *malloc(size_t size); </source> which allocates <code><var>size</var></code> bytes of memory. If the allocation succeeds, a pointer to the block of memory is returned, else NULL is returned. <code>malloc</code> returns a [[void pointer]] (<code>void *</code>), which indicates that it is a pointer to a region of unknown data type. Note that because <code>malloc</code> returns a void pointer, it needn't be explicitly cast to a more specific pointer type: ANSI C defines an implicit conversion between the void pointer type and other pointers to objects. An explicit cast of <code>malloc</code>'s return value is sometimes performed because <code>malloc</code> originally returned a <code>char *</code>, but this cast is unnecessary in standard C code.<ref>[http://www.c-faq.com/malloc/mallocnocast.html comp.lang.c FAQ list · Question 7.7b] on C-FAQ accessed at [[March 9]] [[2007]]</ref><ref>[http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?id=1043284351&answer=1047673478 FAQ > Explanations of... > Casting malloc] on Cprogramming.com accessed at [[March 9]] [[2007]]</ref> However, omitting the cast creates an incompatibility with [[C++]], which requires it. Memory allocated via <code>malloc</code> 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 <code>free</code> function. Its prototype is <source lang="c"> void free(void *pointer); </source> which releases the block of memory pointed to by <code>pointer</code>. <code>pointer</code> must have been previously returned by <code>malloc</code> or <code>calloc</code> or <code>realloc</code> and must only be passed to <code>free</code> once. ==Usage example== The standard method of creating an [[array]] of ten int objects: <source lang="c"> int array[10]; </source> To allocate a similar array dynamically, the following code could be used: <source lang="c"> /* 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 { /* If ptr is not NULL, allocation succeeded. */ } </source> <code>malloc<code> returns <code>NULL</code> to indicate that no memory is available, or that some other error occurred which prevented memory being allocated. Due to the fact that NULL equals to 0 which is interpreted as [[Boolean Logic|false]], the above example could be shortened to <source lang="c"> if(!ptr) { } else { } </source> == Related functions == ===calloc=== <code>malloc</code> 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 '''<code>memset</code>''' function, or by one or more assignment statements that dereference the pointer. An alternative is to use the '''<code>calloc</code>''' function, which allocates memory and then initializes it. Its prototype is <source lang="c"> void *calloc(size_t nelements, size_t bytes); </source> which allocates a region of memory large enough to hold <code>nelements</code> of size <code>bytes</code> each. The allocated region is initialized to zero. ===realloc=== It is often useful to be able to grow or shrink a block of memory. This can be done using <code>realloc</code> which returns a pointer to a memory region of the specified size, which contains the same data as the old region pointed to by <code>pointer</code> (truncated to the minimum of the old and new sizes). If <code>realloc</code> 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, <code>realloc</code> 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 <source lang="c"> void *realloc(void *pointer, size_t size); </source> <code>realloc</code> behaves like <code>malloc</code> if the first argument is NULL: <source lang="c"> void *q = malloc(42); void *p = realloc(NULL, 42); /* equivalent */ </source> Also behaves like <code>free</code> if the second argument is 0: <source lang="c"> free(p); realloc(q, 0); /* equivalent, realloc returns NULL */ </source> ===farmalloc=== A non-standard version of <code>malloc</code> that returns a [[far pointer]] in some implementations of C, useful on platforms where standard <code>malloc</code> returns a [[near pointer]]. ==Common errors== The improper use of <code>malloc</code> and related functions can frequently be a source of bugs. Note that this can be said for most functions or features in a programming language. ===Allocation failure=== <code>malloc</code> is not guaranteed to succeed &mdash; if there is no memory available, or if the program has exceeded the amount of memory it is allowed to reference, <code>malloc</code> will return a <code>NULL</code> pointer. Depending on the nature of the underlying environment, this may or may not be a likely occurrence. Many programs do not check for <code>malloc</code> failure. Such a program would attempt to use the <code>NULL</code> pointer returned by <code>malloc</code> as if it pointed to allocated memory, and the program would crash. This has traditionally been considered an incorrect design, although it remains common, as memory allocation failures only occur rarely in most situations, and the program frequently can do nothing better than to exit anyway. Checking for allocation failure is more important when implementing libraries &mdash; since the library might be used in low-memory environments, it is usually considered good practice to return memory allocation failures to the program using the library and allow it to choose whether to attempt to handle the error. ===Memory leaks=== When a call to <code>malloc</code>, <code>calloc</code> or <code>realloc</code> succeeds, the return value of the call should eventually be passed to the <code>free</code> 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 &mdash; in other words, a [[memory leak]] will occur. Typically, memory leaks are caused by losing track of pointers, for example not using a temporary pointer for the return value of <code>realloc</code>, which may lead to the original pointer being overwritten with NULL, for example: <source lang="c"> 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 NULL), but the original address in ptr has been lost so the memory cannot be freed and a leak has occurred */ /* ... */ return (1); } /* ... */ </source> ===Use after free=== After a pointer has been passed to <code>free</code>, it becomes a [[dangling pointer]]: it references a region of memory with undefined content, which may not be available for use. The pointers value can not be read. For example: <source lang="c"> int *ptr = malloc(sizeof (int)); free(ptr); *ptr = 0; /* Undefined behavior */ printf("%p", (void *)ptr); /* also undefined behavior */ </source> Code like this has undefined behavior: its effect may vary. 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 <code>free</code> twice, known as a ''double free''. To avoid this, some programmers set pointers to <code>NULL</code> after passing them to <code>free</code>: <code>free(NULL)</code> is safe (it does nothing).<ref>[http://www.opengroup.org/onlinepubs/009695399/functions/free.html The Open Group Base Specifications Issue 6] on The Open Group accessed at [[March 9]] [[2007]]</ref> However, this will not protect other aliases to the same pointer from being doubly freed. ===Freeing unallocated memory=== Another problem is when <code>free</code> is passed an address that wasn't allocated by <code>malloc</code>. This can be caused when a pointer to a literal string or the name of a declared array is passed to <code>free</code>, for example: <source lang="c"> char *msg = "Default message"; int tbl[100]; </source> passing either of the above pointers to <code>free</code> will result in undefined behaviour. Passing the NULL pointer to free is safe, and does nothing. ==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 <code>operator new</code> in [[C++]]. Hence, we will call this the '''allocator''' rather than malloc. (However, note that it is never proper for a C++ program to treat <code>malloc</code> and <code>new</code> interchangeably. For example, <code>free</code> cannot be used to release memory that was allocated with <code>new</code>.<ref>[http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.3 Can I free() pointers allocated with new? Can I delete pointers allocated with malloc()?] on C++ FAQ LITE accessed at [[March 9]] [[2007]]</ref>) ===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 (computer)|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. However, due to performance it can be impossible to use an allocator in a real time system and a [[memory pool]] must be deployed instead. 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. === The glibc allocator === The [[GNU C library]] (glibc) uses both <code>brk</code> and <code>[[mmap]]</code> on the [[Linux]] operating system. The <code>brk</code> system call will change the size of the heap to be larger or smaller as needed, while the <code>mmap</code> system call will be used 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 <code>mmap</code> method has its own flaws: it always allocates a segment by mapping entire [[Page (computing)|pages]]. Mapping even a single byte will use an entire page which is usually 4096 bytes. Although this is usually quite acceptable, many architectures provide large page support (4 MiB or 2 MiB with [[Physical Address Extension|PAE]] on IA-32). The combination of this method with large pages can potentially waste vast amounts of memory. The advantage to the <code>mmap</code> method is that when the segment is freed, the memory is returned to the system immediately. === OpenBSD's <code>malloc</code> === [[OpenBSD]]'s implementation of the <code>malloc</code> function makes use of <code>mmap</code>. For requests greater in size than one page, the entire allocation is retrieved using <code>mmap</code>; smaller sizes are assigned from memory pools maintained by <code>malloc</code> within a number of "bucket pages," also allocated with <code>mmap</code>. On a call to <code>free</code>, memory is released and unmapped from the process [[address space]] using <code>munmap</code>. 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 <code>mmap</code> [[system call]], and to detect [[#Use after free|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. === Hoard's <code>malloc</code> === The [[Hoard memory allocator]] is an allocator whose goal is scalable memory allocation performance. Like OpenBSD's allocator, Hoard uses <code>mmap</code> exclusively, but manages memory in chunks of 64K 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. ==Allocation size limits== The largest possible memory block <code>malloc</code> 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 <code>(size_t) −1</code>, or the constant <code>SIZE_MAX</code> in the C99 standard. The C standards guarantee that a certain minimum (0x7FFF in C90, 0xFFFF in C99) for at least one object can be allocated. ==See also== *[[Buffer overflow]] *[[Memory debugger]] *<code>[[mprotect]]</code> *[[new (C++)|<code>new</code> (C++)]] *[[Page size]] *[[Variable-length array]] ==References== {{reflist}} ==External links== *[http://www.opengroup.org/onlinepubs/009695399/functions/malloc.html Definition of malloc in IEEE Std 1003.1 standard] *[http://gee.cs.oswego.edu/dl/html/malloc.html The design of the basis of the glibc allocator] by [[Doug Lea]] * [http://www.osdcom.info/content/view/31/39/ Simple Memory Allocation Algorithms] on OSDEV Community *"[http://www.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf Hoard: A Scalable Memory Allocator for Multithreaded Applications]" by Emery Berger *"[http://www.research.ibm.com/people/m/michael/pldi-2004.pdf Scalable Lock-Free Dynamic Memory Allocation]" by Maged M. Michael *"[http://www-106.ibm.com/developerworks/linux/library/l-memory/ ''Inside memory management'' - The choices, tradeoffs, and implementations of dynamic allocation]" by Jonathan Bartlett *[http://live.gnome.org/MemoryReduction Memory Reduction (GNOME)] wiki page with lots of information about fixing malloc *[http://goog-perftools.sourceforge.net/doc/tcmalloc.html "TCMalloc: Thread-Caching Malloc"], a high-performance malloc developed by Google [[Category:stdlib.h]] [[Category:Memory management]] [[Category:C programming language]] [[Category:Articles with example C code]] [[fr:Malloc]] [[ja:Malloc]] [[ru:malloc]] [[sr:malloc]]