Editing C dynamic memory allocation

{{Short description|Dynamic memory management in the C programming language}}
{{Redirect|Malloc|Mallock|Mallock}}
{{Use dmy dates|date=May 2021|cs1-dates=y}}
{{C Standard Library}}
'''C dynamic memory allocation''' refers to performing [[manual memory management]] for [[dynamic memory allocation]] in the [[C (programming language)|C programming language]] via a group of functions in the [[C standard library]], namely {{mono|malloc}}, {{mono|realloc}}, {{mono|calloc}}, {{mono|aligned_alloc}} and {{mono|free}}.<ref name="c99">{{cite tech report |title=7.20.3 Memory management functions |work=ISO/IEC 9899:1999 specification |page=313 |url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf }}</ref><ref>{{cite web |last=Summit |first=Steve |title=Chapter 11: Memory Allocation |work=C Programming Notes |url=http://www.eskimo.com/~scs/cclass/notes/sx11.html |access-date=11 July 2020}}</ref><ref>{{cite web|url=https://linux.die.net/man/3/aligned_alloc|title=aligned_alloc(3) - Linux man page}}</ref>

The [[C++]] programming language includes these functions; however, the operators [[new and delete (C++)|{{mono|new}} and {{mono|delete}}]] provide similar functionality and are recommended by that language's authors.<ref>{{cite book |last=Stroustrup |first=Bjarne |author-link=Bjarne Stroustrup |year=2008 |title=Programming: Principles and Practice Using C++ |publisher=Addison Wesley |isbn=978-0-321-54372-1 |page=1009}}</ref> Still, there are several situations in which using <code>new</code>/<code>delete</code> is not applicable, such as garbage collection code or performance-sensitive code, and a combination of <code>malloc</code> and placement&nbsp;<code>new</code> may be required instead of the higher-level <code>new</code> operator.

Many different implementations of the actual memory allocation mechanism, used by {{mono|malloc}}, are available. Their performance varies in both execution time and required memory.

==Rationale==
The [[C (programming language)|C programming language]] manages memory [[Static memory allocation|statically]], [[Automatic memory allocation|automatically]], or [[Dynamic memory allocation|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 [[call stack|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<ref>{{cite web |url=https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html |title=gcc manual |publisher=gnu.org |access-date=14 December 2008 }}</ref>). If the required size is not known until [[Run time (program lifecycle phase)|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 {{citation needed span|''free store'' (informally called the "heap"),|date=July 2022|reason=In my experience 'heap' is almost exclusively used in a C context. While free store is used in C++ context for the new/delete operators.}} an area of memory structured for this purpose. In C, the library function <code>malloc</code> is used to allocate a block of memory on the heap. The program accesses this block of memory via a [[pointer (computer programming)|pointer]] that <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.

The original description of C indicated that <code>calloc</code> and <code>cfree</code> were in the standard library, but not <code>malloc</code>.  Code for a simple model implementation of a storage manager for [[Unix]] was given with <code>alloc</code> and <code>free</code> as the user interface functions, and using the <code>[[sbrk]]</code> system call to request memory from the operating system.<ref>Brian W. Kernighan, Dennis M. Ritchie, ''The C Programming Language'', Prentice-Hall, 1978; Section 7.9 (page 156) describes <code>calloc</code> and <code>cfree</code>, and Section 8.7 (page 173) describes an implementation for <code>alloc</code> and <code>free</code>.</ref> The 6th Edition Unix documentation gives <code>alloc</code> and <code>free</code> as the low-level memory allocation functions.<ref>{{man|3|alloc|v6}}</ref> The <code>malloc</code> and <code>free</code> routines in their modern form are completely described in the 7th Edition Unix manual.<ref>{{man|3|malloc|v7}}</ref><ref>Anonymous, ''Unix Programmer's Manual, Vol. 1'', Holt Rinehart and Winston, 1983 (copyright held by Bell Telephone Laboratories, 1983, 1979); The <code>man</code> page for <code>malloc</code> etc. is given on page 275.</ref>

Some platforms provide library or [[intrinsic function]] calls which allow run-time dynamic allocation from the C stack rather than the heap (e.g. <code>alloca()</code><ref>{{man|3|alloca|FreeBSD}}
</ref>). This memory is automatically freed when the calling function ends.

==Overview of functions==
The C dynamic memory allocation functions are defined in <code>stdlib.h</code> header (<code>cstdlib</code> header in C++).<ref name="c99" />

{| class="wikitable"
|-
! Function
! Description
|-
| {{anchor|malloc}}{{cpp|malloc}}
| allocates the specified number of bytes
|-
| {{anchor|aligned_alloc}}{{cpp|aligned_alloc}}
| allocates the specified number of bytes at the specified alignment
|-
| {{anchor|realloc}}{{cpp|realloc}}
| increases or decreases the size of the specified block of memory, moving it if necessary
|-
| {{anchor|calloc}}{{cpp|calloc}}
| allocates the specified number of bytes and initializes them to zero
|-
| {{anchor|free}}{{cpp|free}}
| releases the specified block of memory back to the system
|}

===Differences between <code>malloc()</code> and <code>calloc()</code>===
* <code>malloc()</code> takes a single argument (the amount of memory to allocate in bytes), while <code>calloc()</code> takes two arguments &mdash; the number of elements and the size of each element.
* <code>malloc()</code> only allocates memory, while <code>calloc()</code> allocates and sets the bytes in the allocated region to zero.<ref>{{man|3|calloc|Linux}}</ref>

==Usage example==
Creating an [[Array data structure|array]] of ten integers with automatic scope is straightforward in C:
<syntaxhighlight lang="c">
int array[10];
</syntaxhighlight>
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 (C standard revision)|C11]] implementations, the following code can be used:
<syntaxhighlight lang="c">
int *array = malloc(10 * sizeof(int));
</syntaxhighlight>
This computes the number of bytes that ten integers occupy in memory, then requests that many bytes from <code>malloc</code> and assigns the result to a [[Pointer (computer programming)|pointer]] named <code>array</code> (due to C syntax, pointers and arrays can be used interchangeably in some situations).

Because <code>malloc</code> might not be able to service the request, it might return a [[null pointer]] and it is [[Coding best practices|good programming practice]] to check for this:
<syntaxhighlight lang="c">
int *array = malloc(10 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}
</syntaxhighlight>
When the program no longer needs the [[dynamic array]], it must eventually call <code>free</code> to return the memory it occupies to the free store:
<syntaxhighlight lang="c">
free(array);
</syntaxhighlight>

The memory set aside by <code>malloc</code> is not [[Initialization (programming)|initialized]] and may contain [[cruft]]: the remnants of previously used and discarded data.  After allocation with <code>malloc</code>, elements of the array are [[uninitialized variable]]s.  The command <code>calloc</code> will return an allocation that has already been cleared:
<syntaxhighlight lang="c" >
int *array = calloc(10, sizeof(int));
</syntaxhighlight>

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 <math>n</math> and we want to change it to an array of size <math>m</math>, we can use realloc.
<syntaxhighlight lang="c">
int *arr = malloc(2 * sizeof(int));
arr[0] = 1;
arr[1] = 2;
arr = realloc(arr, 3 * sizeof(int));
arr[2] = 3;
</syntaxhighlight>
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.

==Type safety==
<code>malloc</code> returns a [[void pointer]] (<code>void *</code>), 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:

<syntaxhighlight lang="c">
int *ptr, *ptr2;
ptr = malloc(10 * sizeof(*ptr)); /* without a cast */
ptr2 = (int *)malloc(10 * sizeof(*ptr)); /* with a cast */
</syntaxhighlight>

There are advantages and disadvantages to performing such a cast.

===Advantages to casting===
* Including the cast may allow a C program or function to compile as C++.
* The cast allows for [[ANSI C|pre-1989 versions]] of <code>malloc</code> that originally returned a <code>char *</code>.<ref name="Cprog_malloc">{{cite web |url=http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?id=1043284351&answer=1047673478 |title=Casting malloc |publisher=Cprogramming.com |access-date=9 March 2007 }}</ref>
* 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 <code>malloc()</code> call (although modern compilers and static analysers can warn on such behaviour without requiring the cast<ref>{{cite web|url=http://clang.llvm.org/doxygen/MallocSizeofChecker_8cpp_source.html|title=clang: lib/StaticAnalyzer/Checkers/MallocSizeofChecker.cpp Source File|website=clang.llvm.org|access-date=1 April 2018}}</ref>).

===Disadvantages to casting===
* Under the C standard, the cast is redundant.
* Adding the cast may mask failure to include the header <code>stdlib.h</code>, in which the [[function prototype]] for <code>malloc</code> is found.<ref name="Cprog_malloc" /><ref>{{cite web |url=http://www.c-faq.com/malloc/mallocnocast.html |title=comp.lang.c FAQ list · Question 7.7b |publisher=C-FAQ |access-date=9 March 2007 }}</ref> In the absence of a prototype for <code>malloc</code>, the C90 standard requires that the C compiler assume <code>malloc</code> returns an <code>int</code>. 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 <code>long</code> and pointers are 64-bit and <code>int</code> is 32-bit), this error can actually result in undefined behaviour, as the implicitly declared <code>malloc</code> 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 <code>int</code> return.
* If the type of the pointer is changed at its declaration, one may also need to change all lines where <code>malloc</code> is called and cast.

==Common errors==
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 fault]]s.

Most common errors are as follows:<ref>{{Cite book|title=Pointers on C|last=Reek|first=Kenneth|date=1997-08-04|publisher=Pearson|isbn=9780673999863|edition=1|language=en}}</ref>
;Not checking for allocation failures: Memory allocation is not guaranteed to succeed, and may instead return a null pointer. Using the returned value, without checking if the allocation is successful, invokes [[undefined behavior]]. This usually leads to crash (due to the resulting segmentation fault on the null pointer dereference), but there is no guarantee that a crash will happen so relying on that can also lead to problems.
;Memory leaks: Failure to deallocate memory using <code>free</code> 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. {{anchor|Use after free}}
;Logical errors: All allocations must follow the same pattern: allocation using <code>malloc</code>, usage to store data, deallocation using <code>free</code>. Failures to adhere to this pattern, such as memory usage after a call to <code>free</code> ([[dangling pointer]]) or before a call to <code>malloc</code> ([[wild pointer]]), calling <code>free</code> 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, {{code|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 {{code|realloc}} since it is more common to resize to zero.<ref>{{cite web |title=MEM04-C. Beware of zero-length allocations - SEI CERT C Coding Standard - Confluence |url=https://wiki.sei.cmu.edu/confluence/display/c/MEM04-C.+Beware+of+zero-length+allocations |website=wiki.sei.cmu.edu}}<!-- Note: the example is bullshit. Freeing NULL is safe because it does nothing. --></ref> Although both [[POSIX]] and the [[Single Unix Specification]] require proper handling of 0-size allocations by either returning {{code|NULL}} or something else that can be safely freed,<ref>{{cite web |title=POSIX.1-2017: malloc |url=https://pubs.opengroup.org/onlinepubs/9699919799/ |website=pubs.opengroup.org |access-date=29 November 2019}}</ref> 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.<ref>{{cite web |last1=Awakened |title=How a double-free bug in WhatsApp turns to RCE |date=2 October 2019 |url=https://awakened1712.github.io/hacking/hacking-whatsapp-gif-rce/ |access-date=29 November 2019}}</ref> 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 {{code|NULL}} has its own problems: it otherwise indicates an out-of-memory failure. In the case of {{code|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.)<ref>{{cite tweet |last1=Felker |first1=Rich |title=Wow. The WhatsApp RCE was the wrong behavior for realloc(p,0) so many implementations insist on. |user=RichFelker |number=1179701167569416192 |access-date=6 August 2022 |date=3 October 2019}}</ref>

==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 <code>malloc</code> and the operator <code>new</code> in [[C++]].<ref>{{Cite book |title=Modern C++ Design: Generic Programming and Design Patterns Applied |first=Andrei |last=Alexandrescu |publisher=Addison-Wesley |year=2001 |page=78}}</ref>

===Heap-based===
{{see also|sbrk}}
Implementation of legacy allocators was commonly done using the [[Data_segment#Heap|heap segment]].  The allocator would usually expand and contract the heap to fulfill allocation requests.

The heap method suffers from a few inherent flaws:

* A linear allocator can only shrink if the last allocation is released. Even if largely unused, the heap can get "stuck" at a very large size because of a small but long-lived allocation at its tip which could waste any amount of address space, although some allocators on some systems may be able to release entirely empty intermediate pages to the OS.
* A linear allocator is sensitive to [[fragmentation (computer)|fragmentation]]. A good allocator will attempt to track and reuse free slots through the entire heap, but as allocation sizes and lifetimes get mixed it can be difficult and expensive to find or coalesce free segments large enough to hold new allocation requests.
* A linear allocator has extremely poor concurrency characteristics, as the heap segment is per-process every thread has to synchronise on allocation, and concurrent allocations from threads which may have very different work loads amplifies the previous two issues.

{{anchor|dlmalloc}}

===dlmalloc and ptmalloc{{anchor|dlmalloc}}===
[[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.<ref>{{cite web|url=http://malloc.de/en/|title=Wolfram Gloger's malloc homepage|website=malloc.de|access-date=1 April 2018}}</ref><ref name="phrack-57-8">{{cite journal|last=Kaempf |first=Michel |year=2001 |title=Vudo malloc tricks |journal=[[Phrack]] |issue=57 |page=8 |url=http://phrack.org/issues/57/8.html |access-date=29 April 2009 |url-status=live |archive-url=https://web.archive.org/web/20090122071923/http://www.phrack.org/issues.html?issue=57&id=8&mode=txt |archive-date=22 January 2009 }}</ref><ref>{{cite web |title=Glibc: Malloc Internals |url=https://sourceware.org/glibc/wiki/MallocInternals |website=sourceware.org Trac |access-date=1 December 2019}}</ref> As of November 2023, the latest version of dlmalloc is version 2.8.6 from August 2012.<ref name="dlmalloc">{{cite web |last1=Lee |first1=Doug |title=A Memory Allocator |url=http://gee.cs.oswego.edu/dl/html/malloc.html |access-date=1 December 2019}} [http://gee.cs.oswego.edu/pub/misc/malloc.c HTTP for Source Code]</ref>

dlmalloc is a boundary tag allocator. Memory on the [[heap memory|heap]] is allocated as "chunks", an 8-byte [[data structure alignment|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.<ref name="phrack-57-8" /><ref name="dlmalloc"/>{{rp|at=2.8.6, Minimum allocated size}}

Unallocated memory is grouped into "[[bin (computational geometry)|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:<ref name="phrack-57-8" /><ref name="dlmalloc"/>{{rp|at=Overlaid data structures}}

* 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, dlmalloc since v2.8.0 use [[Trie#Bitwise tries|an in-place ''bitwise trie'' algorithm]] ("treebin"). If there is no free space left to satisfy the request, dlmalloc tries to increase the size of the heap, usually via the [[sbrk|brk]] system call. This feature was introduced way after ptmalloc was created (from v2.7.x), and as a result is not a part of glibc, which inherits the old best-fit allocator.
* For requests above the mmap threshold (a "largebin" request), the memory is always allocated using the [[mmap]] system call. The threshold is usually 128&nbsp;KB.<ref name="glibc-env">{{cite web |url=https://www.gnu.org/software/libc/manual/html_node/Malloc-Tunable-Parameters.html |title=Malloc Tunable Parameters |publisher=[[GNU]] |access-date=2 May 2009 }}</ref> The mmap method averts problems with huge buffers trapping a small allocation at the end after their expiration, but always allocates an entire [[page (computer memory)|page]] of memory, which on many architectures is 4096 bytes in size.<ref>{{cite web |last=Sanderson |first=Bruce |url=http://support.microsoft.com/kb/555223 |title=RAM, Virtual Memory, Pagefile and all that stuff |publisher=Microsoft Help and Support |date=12 December 2004 }}</ref>

Game developer Adrian Stone argues that {{code|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 ({{code|sysmalloc}}/{{code|systrim}}) cannot be used to allocate and commit individual pages of virtual memory. In the absence of demand paging, fragmentation becomes a greater concern.<ref>{{cite web |last1=Stone |first1=Adrian |title=The Hole That dlmalloc Can't Fill |url=http://gameangst.com/?p=496 |website=Game Angst |access-date=1 December 2019}}</ref>

{{anchor|jemalloc}}

===FreeBSD's and NetBSD's jemalloc===
Since [[FreeBSD]] 7.0 and [[NetBSD]] 5.0, the old <code>malloc</code> implementation ({{code|phkmalloc}} by [[Poul-Henning Kamp]]) was replaced by [http://jemalloc.net/ jemalloc], written by Jason Evans.  The main reason for this was a lack of scalability of {{code|phkmalloc}} in terms of multithreading.  In order to avoid lock contention, {{code|jemalloc}} uses separate "arenas" for each [[central processing unit|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.<ref>{{cite web |url=http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf |title=A Scalable Concurrent malloc(3) Implementation for FreeBSD |first=Jason |last=Evans |date=16 April 2006 |access-date=18 March 2012 }}</ref>

{{anchor|openbsd}}

===OpenBSD's malloc===
[[OpenBSD]]'s implementation of the <code>malloc</code> function makes use of [[mmap]]. 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>.<ref>{{cite web|url=http://bxr.su/OpenBSD/lib/libc/stdlib/malloc.c |title=libc/stdlib/malloc.c |website=BSD Cross Reference, OpenBSD src/lib/}}</ref>{{better source needed|date=November 2015}} 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 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.<ref>{{Cite web |title=History {{!}} GrapheneOS |url=https://grapheneos.org/history/ |access-date=2023-03-02 |website=grapheneos.org |language=en}}</ref>

{{anchor|hoard}}

===Hoard malloc===
{{main|Hoard memory allocator}}
Hoard 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 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.<ref>{{Cite conference | doi = 10.1145/378993.379232| title = Hoard: A Scalable Memory Allocator for Multithreaded Applications| work = Proceedings of the ninth international conference on Architectural support for programming languages and operating systems| conference = [[International Conference on Architectural Support for Programming Languages and Operating Systems|ASPLOS]]-IX| pages = 117–128| date=November 2000 | last1 = Berger | first1 = E. D. | last2 = McKinley | first2 = K. S. |author2-link = Kathryn S. McKinley| last3 = Blumofe | first3 = R. D. | last4 = Wilson | first4 = P. R. | isbn = 1-58113-317-0| url = http://www.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf| citeseerx = 10.1.1.1.4174}}</ref>

===mimalloc===
{{main|mimalloc}}
An [[open source|open-source]] compact general-purpose [[memory allocator]] from [[Microsoft Research]] with focus on performance.<ref>{{Cite web |url=https://slashdot.org/firehose.pl?op=view&id=110928452 |title=Microsoft releases optimized malloc() as open source - Slashdot |access-date=2020-07-04  |archive-date=2023-06-14  |archive-url=https://web.archive.org/web/20230614154744/https://slashdot.org/firehose.pl?op=view&id=110928452 |url-status=dead }}</ref> The library is about 11,000 [[lines of code]].

{{anchor|tcmalloc}}

===Thread-caching malloc (tcmalloc)===
Every thread has a [[thread-local storage]] for small allocations. For large allocations mmap or [[sbrk]] can be used. [https://code.google.com/p/gperftools/ TCMalloc], a ''malloc'' developed by Google,<ref>[//code.google.com/p/gperftools/ TCMalloc homepage]</ref> 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.<ref>Ghemawat, Sanjay; Menage, Paul; [http://goog-perftools.sourceforge.net/doc/tcmalloc.html ''TCMalloc : Thread-Caching Malloc'']</ref><ref>{{cite web |first=Mark |last=Callaghan |url=http://mysqlha.blogspot.com/2009/01/double-sysbench-throughput-with_18.html |title=High Availability MySQL: Double sysbench throughput with TCMalloc |work=Mysqlha.blogspot.com |date=18 January 2009 |access-date=18 September 2011 }}</ref>

===In-kernel===
Operating system [[kernel (operating system)|kernels]] need to allocate memory just as application programs do. The implementation of <code>malloc</code> 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 [[direct memory access|DMA]], or the memory allocation function might be called from interrupt context.<ref>{{cite web |url=http://people.netfilter.org/rusty/unreliable-guides/kernel-hacking/routines-kmalloc.html |title=kmalloc()/kfree() include/linux/slab.h |work=People.netfilter.org |access-date=18 September 2011 }}</ref> This necessitates a <code>malloc</code> implementation tightly integrated with the [[virtual memory]] subsystem of the operating system kernel.

==Overriding malloc==
Because  <code>malloc</code> and its relatives can have a strong impact on the performance of a program,<!--TODO: cite Bentley's Programming Pearls--> 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#SVR3|Unix System V.3]], is to make <code>malloc</code> and <code>free</code> function pointers that an application can reset to custom functions.<ref name="Levine_1999_CH9"/>

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.

==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 <code>[[size_t]]</code> 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 <code>SIZE_MAX</code> constant from <code>&lt;[[stdint.h]]&gt;</code>. Although not guaranteed by {{nowrap|ISO C}}, it is usually <code>2^(CHAR_BIT * [[sizeof]](size_t)) - 1</code>.

On glibc systems, the largest possible memory block <code>malloc</code> can allocate is only half this size, namely <code>2^(CHAR_BIT * [[sizeof]](ptrdiff_t) - 1) - 1</code>.<ref>{{cite web |url=https://sourceware.org/bugzilla/show_bug.cgi?id=23741#c2 |title=malloc: make malloc fail with requests larger than PTRDIFF_MAX |date=18 April 2019 |website=Sourceware Bugzilla |access-date=30 July 2020}}</ref>

==Extensions and alternatives==
The C library implementations shipping with various operating systems and compilers may come with alternatives and extensions to the standard <code>malloc</code> interface. Notable among these is:

* <code>[[alloca]]</code>, 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. <code>alloca</code> was present on Unix systems as early as [[UNIX/32V|32/V]] (1978), but its use can be problematic in some (e.g., embedded) contexts.<ref>{{Cite web|title = Why is the use of alloca() not considered good practice?|url = https://stackoverflow.com/questions/1018853/why-is-the-use-of-alloca-not-considered-good-practice|website = stackoverflow.com|access-date = 2016-01-05}}</ref> While supported by many compilers, it is not part of the [[ANSI C|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 [[Call stack#STACK-POINTER|stack and frame pointers]] need to be managed (with fixed-size stack frames, one of these is redundant).<ref>{{cite web |first1=Saman |last1=Amarasinghe |first2=Charles |last2=Leiserson |title=6.172 Performance Engineering of Software Systems, Lecture 10 |year=2010 |publisher=Massachusetts Institute of Technology |website=MIT OpenCourseWare |url=http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/ |access-date=27 January 2015 |archive-url=https://web.archive.org/web/20150622092347/http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/ |archive-date=22 June 2015 }}</ref> Larger allocations may also increase the risk of undefined behavior due to a [[stack overflow]].<ref>{{Cite web|title = alloca(3) - Linux manual page|url = http://man7.org/linux/man-pages/man3/alloca.3.html|website = man7.org|access-date = 2016-01-05}}</ref> C99 offered [[variable-length arrays]] as an alternative stack allocation mechanism{{snd}} however, this feature was relegated to optional in the later [[C11 (C standard revision)|C11]] standard.
* [[POSIX]] defines a function <code>posix_memalign</code> that allocates memory with caller-specified alignment. Its allocations are deallocated with <code>free</code>,<ref>{{man|sh|posix_memalign}}</ref> so the implementation usually needs to be a part of the malloc library.

==See also==
* [[Buffer overflow]]
* [[Memory debugger]]
* [[Memory protection]]
* [[Page (computer memory)|Page size]]
* [[Variable-length array]]

==References==
{{Reflist|refs=
<ref name="Levine_1999_CH9">{{cite book |author-last=Levine |author-first=John R. |author-link=John R. Levine |title=Linkers and Loaders |date=2000 |orig-date=October 1999 |edition=1 |publisher=[[Morgan Kaufmann]] |series=The Morgan Kaufmann Series in Software Engineering and Programming |location=San Francisco, USA |isbn=1-55860-496-0 |oclc=42413382 |chapter=Chapter 9: Shared libraries |chapter-url=https://archive.today/20130126001629/http://www.iecc.com/linker/linker09.html |url=https://www.iecc.com/linker/ |access-date=2020-01-12 |url-status=live |archive-url=https://archive.today/20121205032107/http://www.iecc.com/linker/ |archive-date=2012-12-05}}<!-- Chapter URL = http://www.iecc.com/linker/linker09.html | Chapter archive URL = https://web.archive.org/web/20150527025745/http://www.iecc.com/linker/linker09.html --> Code: [https://archive.today/20200114225034/https://linker.iecc.com/code.html][ftp://ftp.iecc.com/pub/linker/]{{dead link|date=May 2025|bot=medic}}{{cbignore|bot=medic}} Errata: [https://linker.iecc.com/<!-- https://archive.today/20200114224817/https://linker.iecc.com/ 2020-01-14 -->]</ref>
}}

==External links==
{{wikibooks|C Programming|C dynamic memory management|C Programming/C Reference}}
{{Wikiversity|C/Memory_Management}}
* [http://www.opengroup.org/onlinepubs/9699919799/functions/malloc.html Definition of malloc in IEEE Std 1003.1 standard]
* [[Doug Lea|Lea, Doug]]; [http://gee.cs.oswego.edu/dl/html/malloc.html ''The design of the basis of the glibc allocator'']
* Gloger, Wolfram; [http://www.malloc.de/en/ ''The ptmalloc homepage'']
* Berger, Emery; [http://www.hoard.org/ ''The Hoard homepage'']
* Douglas, Niall; [http://www.nedprod.com/programs/portable/nedmalloc/ ''The nedmalloc homepage'']
* Evans, Jason; [http://jemalloc.net/ ''The jemalloc homepage'']
* Google; [https://github.com/gperftools/gperftools/wiki ''The tcmalloc homepage'']
* [https://web.archive.org/web/20060409094110/http://www.osdcom.info/content/view/31/39/ ''Simple Memory Allocation Algorithms''] on OSDEV Community
* Michael, Maged M.; [http://www.research.ibm.com/people/m/michael/pldi-2004.pdf ''Scalable Lock-Free Dynamic Memory Allocation'']
* Bartlett, Jonathan; [http://www.ibm.com/developerworks/library/l-memory/ ''Inside memory management'' – The choices, tradeoffs, and implementations of dynamic allocation]
* [https://web.archive.org/web/20050823083743/http://live.gnome.org/MemoryReduction Memory Reduction (GNOME)] wiki page with much information about fixing malloc
* [http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf C99 standard draft, including TC1/TC2/TC3]
* [http://paste.tclers.tk/1596 Some useful references about C]
* [http://www.open-std.org/jtc1/sc22/wg14/www/standards ISO/IEC 9899 – Programming languages – C]
* [https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/ ''Understanding glibc malloc'']

{{Memory management navbox|state=expanded}}
{{CProLang|state=expanded}}

[[Category:Memory management]]
[[Category:Memory management software]]
[[Category:C standard library]]
[[Category:Articles with example C code]]
[[Category:C++]]