1 | /* -*- C++ -*- */ |
---|
2 | |
---|
3 | /* |
---|
4 | |
---|
5 | Heap Layers: An Extensible Memory Allocation Infrastructure |
---|
6 | |
---|
7 | Copyright (C) 2000-2003 by Emery Berger |
---|
8 | http://www.cs.umass.edu/~emery |
---|
9 | emery@cs.umass.edu |
---|
10 | |
---|
11 | This program is free software; you can redistribute it and/or modify |
---|
12 | it under the terms of the GNU General Public License as published by |
---|
13 | the Free Software Foundation; either version 2 of the License, or |
---|
14 | (at your option) any later version. |
---|
15 | |
---|
16 | This program is distributed in the hope that it will be useful, |
---|
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
19 | GNU General Public License for more details. |
---|
20 | |
---|
21 | You should have received a copy of the GNU General Public License |
---|
22 | along with this program; if not, write to the Free Software |
---|
23 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
---|
24 | |
---|
25 | */ |
---|
26 | |
---|
27 | #ifndef _DLHEAP_H_ |
---|
28 | #define _DLHEAP_H_ |
---|
29 | |
---|
30 | /** |
---|
31 | * @file dlheap.h |
---|
32 | * @brief Contains all the classes required to approximate DLmalloc 2.7.0. |
---|
33 | * @author Emery Berger |
---|
34 | */ |
---|
35 | |
---|
36 | #include <assert.h> |
---|
37 | |
---|
38 | #include "adapt.h" |
---|
39 | #include "dllist.h" |
---|
40 | #include "sllist.h" |
---|
41 | |
---|
42 | #ifndef TRUE |
---|
43 | #define TRUE 1 |
---|
44 | #define FALSE 0 |
---|
45 | #endif |
---|
46 | |
---|
47 | #include "coalesceableheap.h" |
---|
48 | |
---|
49 | /** |
---|
50 | * @class CoalesceableMmapHeap |
---|
51 | * @brief Adds headers to mmapped objects to allow coalescing. |
---|
52 | * @author Emery Berger |
---|
53 | */ |
---|
54 | |
---|
55 | namespace HL { |
---|
56 | |
---|
57 | template <class Mmap> |
---|
58 | class CoalesceableMmapHeap : public RequireCoalesceable<Mmap> { |
---|
59 | public: |
---|
60 | typedef RequireCoalesceable<Mmap> super; |
---|
61 | typedef typename RequireCoalesceable<Mmap>::Header Header; |
---|
62 | |
---|
63 | inline void * malloc (const size_t sz) { |
---|
64 | void * buf = super::malloc (sz + sizeof(Header)); |
---|
65 | void * ptr = Header::makeObject (buf, 0, sz); |
---|
66 | super::markMmapped (ptr); |
---|
67 | super::markInUse (ptr); |
---|
68 | return ptr; |
---|
69 | } |
---|
70 | inline void free (void * ptr) { |
---|
71 | super::free (Header::getHeader (ptr)); |
---|
72 | } |
---|
73 | inline int remove (void * ptr) { |
---|
74 | return super::remove (Header::getHeader (ptr)); |
---|
75 | } |
---|
76 | }; |
---|
77 | |
---|
78 | /** |
---|
79 | * @class SelectMmapHeap |
---|
80 | * @brief Use Mmap (here the superheap) for objects above a certain size. |
---|
81 | * @author Emery Berger |
---|
82 | * |
---|
83 | * @param ThresholdBytes The maximum number of bytes managed by SmallHeap. |
---|
84 | * @param SmallHeap The heap for "small" objects. |
---|
85 | * @param super The heap for "large" objects. |
---|
86 | */ |
---|
87 | |
---|
88 | template <int ThresholdBytes, class SmallHeap, class super> |
---|
89 | class SelectMmapHeap : public super { |
---|
90 | public: |
---|
91 | inline void * malloc (const size_t sz) { |
---|
92 | void * ptr = NULL; |
---|
93 | if (sz <= ThresholdBytes) { |
---|
94 | ptr = sm.malloc (sz); |
---|
95 | } |
---|
96 | |
---|
97 | // Fall-through: go ahead and try mmap if the small heap is out of memory. |
---|
98 | |
---|
99 | if (ptr == NULL) { |
---|
100 | ptr = super::malloc (sz); |
---|
101 | super::markMmapped (ptr); |
---|
102 | } |
---|
103 | return ptr; |
---|
104 | } |
---|
105 | inline void free (void * ptr) { |
---|
106 | if (super::isMmapped(ptr)) { |
---|
107 | super::free (ptr); |
---|
108 | } else { |
---|
109 | sm.free (ptr); |
---|
110 | } |
---|
111 | } |
---|
112 | inline int remove (void * ptr) { |
---|
113 | if (super::isMmapped(ptr)) { |
---|
114 | return super::remove (ptr); |
---|
115 | } else { |
---|
116 | return sm.remove (ptr); |
---|
117 | } |
---|
118 | } |
---|
119 | inline void clear (void) { |
---|
120 | sm.clear(); |
---|
121 | super::clear(); |
---|
122 | } |
---|
123 | |
---|
124 | private: |
---|
125 | SmallHeap sm; |
---|
126 | }; |
---|
127 | |
---|
128 | |
---|
129 | // LeaHeap 2.7.0-like threshold scheme |
---|
130 | // for managing a small superheap. |
---|
131 | |
---|
132 | |
---|
133 | // NOTE: THIS HAS BEEN CHANGED NOW! |
---|
134 | |
---|
135 | template <int ThresholdBytes, class super> |
---|
136 | class Threshold : public super { |
---|
137 | public: |
---|
138 | |
---|
139 | enum { MIN_LARGE_SIZE = 64 }; |
---|
140 | |
---|
141 | #if 1 |
---|
142 | Threshold (void) |
---|
143 | : freeAllNextMalloc (FALSE), |
---|
144 | inUse (0), |
---|
145 | maxInUse (0), |
---|
146 | threshold (0) |
---|
147 | {} |
---|
148 | |
---|
149 | inline void * malloc (const size_t sz) { |
---|
150 | void * ptr = super::malloc (sz); |
---|
151 | if (ptr) { |
---|
152 | const size_t actualSize = super::getSize(ptr); |
---|
153 | inUse += actualSize; |
---|
154 | if (inUse > maxInUse) { |
---|
155 | maxInUse = inUse; |
---|
156 | threshold = 16384 + maxInUse / 2; |
---|
157 | } |
---|
158 | #if 0 |
---|
159 | if (freed < 0) { |
---|
160 | freed = 0; |
---|
161 | } |
---|
162 | #endif |
---|
163 | } |
---|
164 | return ptr; |
---|
165 | } |
---|
166 | |
---|
167 | |
---|
168 | #if 0 |
---|
169 | void * internalMalloc (const size_t sz) { |
---|
170 | if (freeAllNextMalloc || (freed > 0)) { |
---|
171 | freed = 0; |
---|
172 | super::freeAll(); |
---|
173 | freeAllNextMalloc = FALSE; |
---|
174 | } |
---|
175 | void * ptr = super::malloc (sz); |
---|
176 | if (ptr != NULL) { |
---|
177 | if (sz < MIN_LARGE_SIZE) { |
---|
178 | freed -= getSize(ptr); |
---|
179 | if (freed < 0) { |
---|
180 | freed = 0; |
---|
181 | } |
---|
182 | } |
---|
183 | } |
---|
184 | return ptr; |
---|
185 | } |
---|
186 | #endif |
---|
187 | |
---|
188 | |
---|
189 | inline void free (void * ptr) { |
---|
190 | const size_t sz = super::getSize(ptr); |
---|
191 | inUse -= sz; |
---|
192 | super::free (ptr); |
---|
193 | if (super::getMemoryHeld() > threshold) { |
---|
194 | super::freeAll(); |
---|
195 | } |
---|
196 | } |
---|
197 | |
---|
198 | private: |
---|
199 | |
---|
200 | /// The number of bytes in use. |
---|
201 | size_t inUse; |
---|
202 | |
---|
203 | /// The high-water mark of bytes in use. |
---|
204 | size_t maxInUse; |
---|
205 | |
---|
206 | size_t threshold; |
---|
207 | |
---|
208 | // How many bytes have been freed (whose requests were below MIN_LARGE_SIZE). |
---|
209 | // int freed; |
---|
210 | |
---|
211 | /// Should we free all in the superheap on the next malloc? |
---|
212 | bool freeAllNextMalloc; |
---|
213 | |
---|
214 | #else |
---|
215 | inline Threshold (void) |
---|
216 | {} |
---|
217 | |
---|
218 | inline void * malloc (const size_t sz) { |
---|
219 | if ((getMemoryHeld() > ThresholdBytes) || |
---|
220 | ((sz >= MIN_LARGE_SIZE) && (getMemoryHeld() >= sz))) { |
---|
221 | super::freeAll(); |
---|
222 | } |
---|
223 | return super::malloc (sz); |
---|
224 | } |
---|
225 | #endif |
---|
226 | }; |
---|
227 | |
---|
228 | |
---|
229 | /** |
---|
230 | * @namespace DLBigHeapNS |
---|
231 | * @brief All of the bins & size functions for the "big heap". |
---|
232 | */ |
---|
233 | |
---|
234 | namespace DLBigHeapNS |
---|
235 | { |
---|
236 | const size_t bins[] = {8U, 16U, 24U, 32U, 40U, 48U, 56U, 64U, 72U, 80U, 88U, |
---|
237 | 96U, 104U, 112U, 120U, 128U, 136U, 144U, 152U, 160U, |
---|
238 | 168U, 176U, 184U, 192U, 200U, 208U, 216U, 224U, 232U, |
---|
239 | 240U, 248U, 256U, 264U, 272U, 280U, 288U, 296U, 304U, |
---|
240 | 312U, 320U, 328U, 336U, 344U, 352U, 360U, 368U, 376U, |
---|
241 | 384U, 392U, 400U, 408U, 416U, 424U, 432U, 440U, 448U, |
---|
242 | 456U, 464U, 472U, 480U, 488U, 496U, 504U, 512U, 576U, |
---|
243 | 640U, 704U, 768U, 832U, 896U, 960U, 1024U, 1088U, 1152U, |
---|
244 | 1216U, 1280U, 1344U, 1408U, 1472U, 1536U, 1600U, 1664U, |
---|
245 | 1728U, 1792U, 1856U, 1920U, 1984U, 2048U, 2112U, 2560U, |
---|
246 | 3072U, 3584U, |
---|
247 | 4096U, 4608U, 5120U, 5632U, 6144U, 6656U, 7168U, 7680U, |
---|
248 | 8192U, 8704U, 9216U, 9728U, 10240U, 10752U, 12288U, |
---|
249 | 16384U, 20480U, 24576U, 28672U, 32768U, 36864U, 40960U, |
---|
250 | 65536U, 98304U, 131072U, 163840U, 262144U, 524288U, |
---|
251 | 1048576U, 2097152U, 4194304U, 8388608U, 16777216U, |
---|
252 | 33554432U, 67108864U, 134217728U, 268435456U, 536870912U, |
---|
253 | 1073741824U, 2147483648U }; |
---|
254 | |
---|
255 | enum { NUMBINS = sizeof(bins) / sizeof(size_t) }; |
---|
256 | enum { BIG_OBJECT = 2147483648U }; |
---|
257 | |
---|
258 | /** |
---|
259 | * @brief Compute the log base two. |
---|
260 | * @param sz The value we want the log of. |
---|
261 | */ |
---|
262 | int log2 (const size_t sz) { |
---|
263 | int c = 0; |
---|
264 | size_t sz1 = sz; |
---|
265 | while (sz1 > 1) { |
---|
266 | sz1 >>= 1; |
---|
267 | c++; |
---|
268 | } |
---|
269 | return c; |
---|
270 | } |
---|
271 | |
---|
272 | inline int getSizeClass (const size_t sz); |
---|
273 | |
---|
274 | inline size_t getClassSize (const int i) { |
---|
275 | assert (i >= 0); |
---|
276 | assert (i < NUMBINS); |
---|
277 | #if 0 |
---|
278 | if (i < 64) { |
---|
279 | return ((size_t) ((i+1) << 3)); |
---|
280 | } else { |
---|
281 | return |
---|
282 | (i < 89) ? ((size_t) ((i - 55) << 6)) : |
---|
283 | (i < 106) ? ((size_t) ((i - 84) << 9)) : |
---|
284 | (i < 114) ? ((size_t) ((i - 103) << 12)) : |
---|
285 | (i < 118) ? ((size_t) ((i - 112) << 15)) : |
---|
286 | (i < 120) ? ((size_t) ((i - 117) * 262144)) : |
---|
287 | (i < 122) ? ((size_t) ((i - 119) * 1048576)) : |
---|
288 | (i < 124) ? ((size_t) ((i - 121) * 4 * 1048576)) : |
---|
289 | (i < 126) ? ((size_t) ((i - 123) * 16 * 1048576)) : |
---|
290 | (i < 128) ? ((size_t) ((i - 125) * 64 * 1048576)) : |
---|
291 | (i < 130) ? ((size_t) ((i - 127) * 256 * 1048576)) : |
---|
292 | ((size_t) ((i - 129) * 1024 * 1048576)); |
---|
293 | } |
---|
294 | #else |
---|
295 | #if 0 |
---|
296 | if (i < 64) { |
---|
297 | return (size_t) ((i+1) << 3); |
---|
298 | } |
---|
299 | #endif |
---|
300 | return bins[i]; |
---|
301 | #endif |
---|
302 | } |
---|
303 | |
---|
304 | inline int getSizeClass (const size_t sz) { |
---|
305 | size_t sz1 = sz - 1; |
---|
306 | if (sz1 <= 513) { |
---|
307 | return sz1 >> 3; |
---|
308 | } else { |
---|
309 | #if 0 |
---|
310 | // size_t sz1 = sz - 1; |
---|
311 | sz1 >>= 6; |
---|
312 | if (sz1 <= 32) { |
---|
313 | return 56 + sz1; |
---|
314 | } |
---|
315 | sz1 >>= 3; |
---|
316 | if (sz1 <= 20) { |
---|
317 | return 91 + sz1; |
---|
318 | } |
---|
319 | sz1 >>= 3; |
---|
320 | if (sz1 <= 10) { |
---|
321 | return 110 - 6 + sz1; |
---|
322 | } |
---|
323 | sz1 >>= 3; |
---|
324 | if (sz1 <= 4) { |
---|
325 | return 119 - 6 + sz1; |
---|
326 | } |
---|
327 | sz1 >>= 3; |
---|
328 | if (sz1 <= 2) { |
---|
329 | return 124 - 6 + sz1; |
---|
330 | } |
---|
331 | return 125 - 6 + log2(sz1 >> 2); |
---|
332 | #else |
---|
333 | const size_t sz1 = sz - 1; |
---|
334 | return (((sz1 >> 6) <= 32)? 56 + (sz1 >> 6): |
---|
335 | ((sz1 >> 9) <= 20)? 91 + (sz1 >> 9): |
---|
336 | ((sz1 >> 12) <= 10)? 110 - 6 + (sz1 >> 12): |
---|
337 | ((sz1 >> 15) <= 4)? 119 - 6 + (sz1 >> 15): |
---|
338 | ((sz1 >> 18) <= 2)? 124 - 6 + (sz1 >> 18): 126 - 6 + log2(sz1>>19)); |
---|
339 | #endif |
---|
340 | } |
---|
341 | } |
---|
342 | |
---|
343 | } |
---|
344 | |
---|
345 | |
---|
346 | /** |
---|
347 | * @namespace DLSmallHeapNS |
---|
348 | * @brief The size functions for the "small" heap (fastbins). |
---|
349 | */ |
---|
350 | |
---|
351 | namespace DLSmallHeapNS { |
---|
352 | enum { NUMBINS = 8 }; |
---|
353 | inline int getSizeClass (const size_t sz) { |
---|
354 | return (int) ((sz-1) >> 3); |
---|
355 | } |
---|
356 | inline size_t getClassSize (const int i) { |
---|
357 | assert (i >= 0); |
---|
358 | assert (i < NUMBINS); |
---|
359 | return (size_t) ((i+1) << 3); |
---|
360 | } |
---|
361 | } |
---|
362 | |
---|
363 | #if 0 |
---|
364 | |
---|
365 | #include "kingsleyheap.h" |
---|
366 | |
---|
367 | /** |
---|
368 | * @class DLBigHeapType |
---|
369 | * @brief The "big heap" -- a coalescing segregated-fits allocator. |
---|
370 | * @author Emery Berger |
---|
371 | */ |
---|
372 | |
---|
373 | template <class super> |
---|
374 | class DLBigHeapType : |
---|
375 | public |
---|
376 | CoalesceHeap<RequireCoalesceable< |
---|
377 | SegHeap<Kingsley::NUMBINS, |
---|
378 | Kingsley::size2Class, |
---|
379 | Kingsley::class2Size, |
---|
380 | AdaptHeap<DLList, NullHeap<super> >, |
---|
381 | super> > > |
---|
382 | {}; |
---|
383 | |
---|
384 | #else |
---|
385 | |
---|
386 | template <class super> |
---|
387 | class DLBigHeapType : |
---|
388 | public |
---|
389 | CoalesceHeap<RequireCoalesceable< |
---|
390 | SegHeap<DLBigHeapNS::NUMBINS, |
---|
391 | DLBigHeapNS::getSizeClass, |
---|
392 | DLBigHeapNS::getClassSize, |
---|
393 | AdaptHeap<DLList, NullHeap<super> >, |
---|
394 | super> > > |
---|
395 | {}; |
---|
396 | |
---|
397 | #endif |
---|
398 | |
---|
399 | /** |
---|
400 | * @class DLSmallHeapType |
---|
401 | * @brief The "small heap" -- non-coalescing "fastbins" (quicklists). |
---|
402 | * @author Emery Berger |
---|
403 | */ |
---|
404 | |
---|
405 | template <class super> |
---|
406 | class DLSmallHeapType : |
---|
407 | public RequireCoalesceable< |
---|
408 | StrictSegHeap<DLSmallHeapNS::NUMBINS, |
---|
409 | DLSmallHeapNS::getSizeClass, |
---|
410 | DLSmallHeapNS::getClassSize, |
---|
411 | AdaptHeap<HL::SLList, NullHeap<super> >, |
---|
412 | super> > {}; |
---|
413 | |
---|
414 | |
---|
415 | /** |
---|
416 | * @class LeaHeap |
---|
417 | * @brief This heap approximates the algorithms used by DLmalloc 2.7.0. |
---|
418 | * |
---|
419 | * The whole thing. Big objects are allocated via mmap. |
---|
420 | * Other objects are first allocated from the special thresholded quicklists, |
---|
421 | * or if they're too big, they're allocated from the coalescing big heap. |
---|
422 | * |
---|
423 | * @param Sbrk An sbrk-like heap, for small object allocation. |
---|
424 | * @param Mmap An mmap-like heap, for large object allocation. |
---|
425 | */ |
---|
426 | |
---|
427 | template <class Sbrk, class Mmap> |
---|
428 | class LeaHeap : |
---|
429 | public |
---|
430 | SelectMmapHeap<128 * 1024, |
---|
431 | Threshold<4096, |
---|
432 | DLSmallHeapType<DLBigHeapType<CoalesceableHeap<Sbrk> > > >, |
---|
433 | CoalesceableMmapHeap<Mmap> > |
---|
434 | {}; |
---|
435 | |
---|
436 | } |
---|
437 | |
---|
438 | #endif |
---|