Editing C dynamic memory allocation (section)

===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}}