2 .\" ----------------------------------------------------------------------------
3 .\" "THE BEER-WARE LICENSE" (Revision 42):
4 .\" <phk@FreeBSD.org> wrote this file. As long as you retain this notice you
5 .\" can do whatever you want with this stuff. If we meet some day, and you think
6 .\" this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
7 .\" ----------------------------------------------------------------------------
15 A new malloc(3) implementation was written to meet the goals,
16 and to the extent possible to address the shortcomings listed previously.
18 The source is 1218 lines of C code, and can be found in FreeBSD 2.2
19 (and probably later versions as well) as src/lib/libc/stdlib/malloc.c.
21 The main data structure is the
25 for each page we have control over.
26 The value can be one of:
29 Another part of the code may call brk(2) to get a piece of the cake.
30 Consequently, we cannot rely on the memory we get from the kernel
31 being one consecutive piece of memory, and therefore we need a way to
32 mark such pages as "untouchable".
38 This is the first page in a (multi-)page allocation.
41 This is a subsequent page in a multi-page allocation.
46 A pointer to a structure describing a partitioned page.
48 In addition, there exists a linked list of small data structures that
49 describe the free space as runs of free pages.
51 Notice that these structures are not part of the free pages themselves,
52 but rather allocated with malloc so that the free pages themselves
53 are never referenced while they are free.
55 When a request for storage comes in, it will be treated as a ``page''
56 allocation if it is bigger than half a page.
57 The free list will be searched and the first run of free pages that
58 can satisfy the request is used. The first page gets set to
60 status. If more than that one page is needed, the rest of them get
62 status in the page-directory.
64 If there were no pages on the free list, brk(2) will be called, and
65 the pages will get added to the page-directory with status
67 and the search restarts.
69 Freeing a number of pages is done by changing their state in the
70 page directory to MALLOC_FREE, and then traversing the free-pages list to
71 find the right place for this run of pages, possibly collapsing
72 with the two neighboring runs into one run and, if possible,
73 releasing some memory back to the kernel by calling brk(2).
75 If the request is less than or equal to half of a page, its size will be
76 rounded up to the nearest power of two before being processed
77 and if the request is less than some minimum size, it is rounded up to
80 These sub-page allocations are served from pages which are split up
81 into some number of equal size chunks.
82 For each of these pages a
86 describes the size of the chunks on this page, how many there are,
87 how many are free and so on.
88 The description consist of a bitmap of used chunks, and various counters
89 and numbers used to keep track of the stuff in the page.
91 For each size of sub-page allocation, the pginfo structures for the
92 pages that have free chunks in them form a list.
93 The heads of these lists are stored in predetermined slots at
94 the beginning of the page directory to make access fast.
96 To allocate a chunk of some size, the head of the list for the
97 corresponding size is examined, and a free chunk found. The number
98 of free chunks on that page is decreased by one and, if zero, the
99 pginfo structure is unlinked from the list.
101 To free a chunk, the page is derived from the pointer, the page table
102 for that page contains a pointer to the pginfo structure, where the
103 free bit is set for the chunk, the number of free chunks increased by
104 one, and if equal to one, the pginfo structure is linked into the
105 proper place on the list for this size of chunks.
106 If the count increases to match the number of chunks on the page, the
107 pginfo structure is unlinked from the list and free(3)'ed and the
108 actual page itself is free(3)'ed too.
110 To be 100% correct performance-wise these lists should be ordered
111 according to the recent number of accesses to that page. This
112 information is not available and it would essentially mean a reordering
113 of the list on every memory reference to keep it up-to-date.
114 Instead they are ordered according to the address of the pages.
115 Interestingly enough, in practice this comes out to almost the same
116 thing performance-wise.
118 It's not that surprising after all, it's the difference between
119 following the crowd or actively directing where it can go, in both
120 ways you can end up in the middle of it all.
122 The side effect of this compromise is that it also uses less storage,
123 and the list never has to be reordered, all the ordering happens when
124 pages are added or deleted.
126 It is an interesting twist to the implementation that the
130 is allocated with malloc.
131 That is, "as with malloc" to be painfully correct.
132 The code knows the special case where the first (couple) of allocations on
133 the page is actually the pginfo structure and deals with it accordingly.
134 This avoids some silly "chicken and egg" issues.
135 .ds RH Bells and whistles.
139 brk(2) is actually not a very fast system call when you ask for storage.
140 This is mainly because of the need by the kernel to zero the pages before
141 handing them over, so therefore this implementation does not release
142 heap pages until there is a large chunk to release back to the kernel.
143 Chances are pretty good that we will need it again pretty soon anyway.
144 Since these pages are not accessed at all, they will soon be paged out
145 and don't affect anything but swap-space usage.
147 The page directory is actually kept in a mmap(2)'ed piece of
148 anonymous memory. This avoids some rather silly cases that
149 would otherwise have to be handled when the page directory
152 One particularly nice feature is that all pointers passed to free(3)
153 and realloc(3) can be checked conclusively for validity:
154 First the pointer is masked to find the page. The page directory
155 is then examined, it must contain either MALLOC_FIRST, in which
156 case the pointer must point exactly at the page, or it can contain
157 a struct pginfo*, in which case the pointer must point to one of
158 the chunks described by that structure.
159 Warnings will be printed on
161 and nothing will be done with
162 the pointer if it is found to be invalid.
164 An environment variable
166 allows the user some control over the behavior of malloc.
167 Some of the more interesting options are:
170 If malloc fails to allocate storage, core-dump the process with
171 a message rather than expect it handle this correctly.
172 It's amazing how few programs actually handle this condition correctly,
173 and consequently the havoc they can create is the more creative or
177 Writes malloc statistics to a file called ``malloc.out'' prior
178 to process termination.
181 Pass a hint to the kernel about pages we no longer need through the
182 madvise(2) system call. This can help performance on machines that
183 page heavily by eliminating unnecessary page-ins and page-outs of
187 Always do a free and malloc when realloc(3) is called.
188 For programs doing garbage collection using realloc(3), this makes the
189 heap collapse faster since malloc will reallocate from the
190 lowest available address.
192 is to leave things alone if the size of the allocation is still in
196 will explicitly fill the allocated area with a particular value
197 to try to detect if programs rely on it being zero.
200 will explicitly zero out the allocated chunk of memory, while any
201 space after the allocation in the chunk will be filled with the
202 junk value to try to catch out of the chunk references.
203 .ds RH The road not taken.
205 The road not yet taken.
207 A couple of avenues were explored that could be interesting in some
208 set of circumstances.
210 Using mmap(2) instead of brk(2) was actually slower, since brk(2)
211 knows a lot of the things that mmap has to find out first.
213 In general there is little room for further improvement of the
214 time-overhead of the malloc, further improvements will have to
215 be in the area of improving paging behavior.
217 It is still under consideration to add a feature such that
218 if realloc is called with two zero arguments, the internal
219 allocations will be reallocated to perform a garbage collect.
220 This could be used in certain types of programs to collapse
221 the memory use, but so far it doesn't seem to be worth the effort.
223 Malloc/Free can be a significant point of contention in multi-threaded
224 programs. Low-grain locking of the data-structures inside the
225 implementation should be implemented to avoid excessive spin-waiting.
projects / FreeBSD / releng / 10.0.git / blob