u-boot/common/dlmalloc.c

235     Chunks of memory are maintained using a `boundary tag' method as
238     survey of such techniques.)  Sizes of free chunks are stored both
240     consolidating fragmented chunks into bigger chunks very fast.  The
241     size fields also hold bits representing whether chunks are free or
265     Chunks always begin on even word boundries, so the mem portion
269     Free chunks are stored in circular doubly-linked lists, and look like this:
308      2. Chunks allocated via mmap, which have the second-lowest-order
313     Available chunks are kept in any of several places (all declared below):
315     * `av': An array of chunks serving as bin headers for consolidated
316        chunks. Each bin is doubly linked.  The bins are approximately
320        consolidated chunk physically borders another one. Chunks in
324        The chunks in each bin are maintained in decreasing sorted order by
326        the same-sized chunks, but facilitates best-fit allocation for
327        larger chunks. (These lists are just sequential. Keeping them in
329        fancier ordered data structures.)  Chunks of the same size are
333        consolidated with adjacent freed chunks, resulting in larger free
334        chunks and less fragmentation.
344        before other non-fitting chunks, so as to provide better
345        locality for runs of sequentially allocated chunks.
481     heads of (initially empty) doubly-linked lists of chunks, laid out
484     and chunks are the same).
486     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
504     The special chunks `top' and `last_remainder' get their own bins,
633   bins for chunks < 512 are all spaced 8 bytes apart, and hold
634   identically sized chunks. This is exploited in malloc.
794   /* ... and is surrounded by OK chunks.
795     Since more things can be checked with free chunks than inuse ones,
860   Linking chunks in bin lists.
946   /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because
1196 	 allocation strategy tends to give contiguous chunks
1222 	 units) in a way that allows chunks obtained across different
1501        4. Other chunks are consolidated as they arrive, and
1614     Chunks that were obtained via mmap cannot be extended or shrunk
2148     locked between two used chunks, so they cannot be given back to
2459       * Use best fit for very large chunks to prevent some worst-cases.
2463       * Removed footers when chunks are in use. Thanks to
2478       * Occasionally bin return list chunks in first scan
2485       * Scan 2 returns chunks (not just 1)