Eneboo - Documentación para desarrolladores
|
00001 /* -*- C++ -*- */ 00002 00003 /* 00004 00005 Heap Layers: An Extensible Memory Allocation Infrastructure 00006 00007 Copyright (C) 2000-2003 by Emery Berger 00008 http://www.cs.umass.edu/~emery 00009 emery@cs.umass.edu 00010 00011 This program is free software; you can redistribute it and/or modify 00012 it under the terms of the GNU General Public License as published by 00013 the Free Software Foundation; either version 2 of the License, or 00014 (at your option) any later version. 00015 00016 This program is distributed in the hope that it will be useful, 00017 but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 GNU General Public License for more details. 00020 00021 You should have received a copy of the GNU General Public License 00022 along with this program; if not, write to the Free Software 00023 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00024 00025 */ 00026 00027 #ifndef _DLHEAP_H_ 00028 #define _DLHEAP_H_ 00029 00036 #include <assert.h> 00037 00038 #include "adapt.h" 00039 #include "dllist.h" 00040 #include "sllist.h" 00041 00042 #ifndef TRUE 00043 #define TRUE 1 00044 #define FALSE 0 00045 #endif 00046 00047 #include "coalesceableheap.h" 00048 00055 namespace HL { 00056 00057 template <class Mmap> 00058 class CoalesceableMmapHeap : public RequireCoalesceable<Mmap> { 00059 public: 00060 typedef RequireCoalesceable<Mmap> super; 00061 typedef typename RequireCoalesceable<Mmap>::Header Header; 00062 00063 inline void * malloc (const size_t sz) { 00064 void * buf = super::malloc (sz + sizeof(Header)); 00065 void * ptr = Header::makeObject (buf, 0, sz); 00066 super::markMmapped (ptr); 00067 super::markInUse (ptr); 00068 return ptr; 00069 } 00070 inline void free (void * ptr) { 00071 super::free (Header::getHeader (ptr)); 00072 } 00073 inline int remove (void * ptr) { 00074 return super::remove (Header::getHeader (ptr)); 00075 } 00076 }; 00077 00088 template <int ThresholdBytes, class SmallHeap, class super> 00089 class SelectMmapHeap : public super { 00090 public: 00091 inline void * malloc (const size_t sz) { 00092 void * ptr = NULL; 00093 if (sz <= ThresholdBytes) { 00094 ptr = sm.malloc (sz); 00095 } 00096 00097 // Fall-through: go ahead and try mmap if the small heap is out of memory. 00098 00099 if (ptr == NULL) { 00100 ptr = super::malloc (sz); 00101 super::markMmapped (ptr); 00102 } 00103 return ptr; 00104 } 00105 inline void free (void * ptr) { 00106 if (super::isMmapped(ptr)) { 00107 super::free (ptr); 00108 } else { 00109 sm.free (ptr); 00110 } 00111 } 00112 inline int remove (void * ptr) { 00113 if (super::isMmapped(ptr)) { 00114 return super::remove (ptr); 00115 } else { 00116 return sm.remove (ptr); 00117 } 00118 } 00119 inline void clear (void) { 00120 sm.clear(); 00121 super::clear(); 00122 } 00123 00124 private: 00125 SmallHeap sm; 00126 }; 00127 00128 00129 // LeaHeap 2.7.0-like threshold scheme 00130 // for managing a small superheap. 00131 00132 00133 // NOTE: THIS HAS BEEN CHANGED NOW! 00134 00135 template <int ThresholdBytes, class super> 00136 class Threshold : public super { 00137 public: 00138 00139 enum { MIN_LARGE_SIZE = 64 }; 00140 00141 #if 1 00142 Threshold (void) 00143 : freeAllNextMalloc (FALSE), 00144 inUse (0), 00145 maxInUse (0), 00146 threshold (0) 00147 {} 00148 00149 inline void * malloc (const size_t sz) { 00150 void * ptr = super::malloc (sz); 00151 if (ptr) { 00152 const size_t actualSize = super::getSize(ptr); 00153 inUse += actualSize; 00154 if (inUse > maxInUse) { 00155 maxInUse = inUse; 00156 threshold = 16384 + maxInUse / 2; 00157 } 00158 #if 0 00159 if (freed < 0) { 00160 freed = 0; 00161 } 00162 #endif 00163 } 00164 return ptr; 00165 } 00166 00167 00168 #if 0 00169 void * internalMalloc (const size_t sz) { 00170 if (freeAllNextMalloc || (freed > 0)) { 00171 freed = 0; 00172 super::freeAll(); 00173 freeAllNextMalloc = FALSE; 00174 } 00175 void * ptr = super::malloc (sz); 00176 if (ptr != NULL) { 00177 if (sz < MIN_LARGE_SIZE) { 00178 freed -= getSize(ptr); 00179 if (freed < 0) { 00180 freed = 0; 00181 } 00182 } 00183 } 00184 return ptr; 00185 } 00186 #endif 00187 00188 00189 inline void free (void * ptr) { 00190 const size_t sz = super::getSize(ptr); 00191 inUse -= sz; 00192 super::free (ptr); 00193 if (super::getMemoryHeld() > threshold) { 00194 super::freeAll(); 00195 } 00196 } 00197 00198 private: 00199 00201 size_t inUse; 00202 00204 size_t maxInUse; 00205 00206 size_t threshold; 00207 00208 // How many bytes have been freed (whose requests were below MIN_LARGE_SIZE). 00209 // int freed; 00210 00212 bool freeAllNextMalloc; 00213 00214 #else 00215 inline Threshold (void) 00216 {} 00217 00218 inline void * malloc (const size_t sz) { 00219 if ((getMemoryHeld() > ThresholdBytes) || 00220 ((sz >= MIN_LARGE_SIZE) && (getMemoryHeld() >= sz))) { 00221 super::freeAll(); 00222 } 00223 return super::malloc (sz); 00224 } 00225 #endif 00226 }; 00227 00228 00234 namespace DLBigHeapNS 00235 { 00236 const size_t bins[] = {8U, 16U, 24U, 32U, 40U, 48U, 56U, 64U, 72U, 80U, 88U, 00237 96U, 104U, 112U, 120U, 128U, 136U, 144U, 152U, 160U, 00238 168U, 176U, 184U, 192U, 200U, 208U, 216U, 224U, 232U, 00239 240U, 248U, 256U, 264U, 272U, 280U, 288U, 296U, 304U, 00240 312U, 320U, 328U, 336U, 344U, 352U, 360U, 368U, 376U, 00241 384U, 392U, 400U, 408U, 416U, 424U, 432U, 440U, 448U, 00242 456U, 464U, 472U, 480U, 488U, 496U, 504U, 512U, 576U, 00243 640U, 704U, 768U, 832U, 896U, 960U, 1024U, 1088U, 1152U, 00244 1216U, 1280U, 1344U, 1408U, 1472U, 1536U, 1600U, 1664U, 00245 1728U, 1792U, 1856U, 1920U, 1984U, 2048U, 2112U, 2560U, 00246 3072U, 3584U, 00247 4096U, 4608U, 5120U, 5632U, 6144U, 6656U, 7168U, 7680U, 00248 8192U, 8704U, 9216U, 9728U, 10240U, 10752U, 12288U, 00249 16384U, 20480U, 24576U, 28672U, 32768U, 36864U, 40960U, 00250 65536U, 98304U, 131072U, 163840U, 262144U, 524288U, 00251 1048576U, 2097152U, 4194304U, 8388608U, 16777216U, 00252 33554432U, 67108864U, 134217728U, 268435456U, 536870912U, 00253 1073741824U, 2147483648U }; 00254 00255 enum { NUMBINS = sizeof(bins) / sizeof(size_t) }; 00256 enum { BIG_OBJECT = 2147483648U }; 00257 00262 int log2 (const size_t sz) { 00263 int c = 0; 00264 size_t sz1 = sz; 00265 while (sz1 > 1) { 00266 sz1 >>= 1; 00267 c++; 00268 } 00269 return c; 00270 } 00271 00272 inline int getSizeClass (const size_t sz); 00273 00274 inline size_t getClassSize (const int i) { 00275 assert (i >= 0); 00276 assert (i < NUMBINS); 00277 #if 0 00278 if (i < 64) { 00279 return ((size_t) ((i+1) << 3)); 00280 } else { 00281 return 00282 (i < 89) ? ((size_t) ((i - 55) << 6)) : 00283 (i < 106) ? ((size_t) ((i - 84) << 9)) : 00284 (i < 114) ? ((size_t) ((i - 103) << 12)) : 00285 (i < 118) ? ((size_t) ((i - 112) << 15)) : 00286 (i < 120) ? ((size_t) ((i - 117) * 262144)) : 00287 (i < 122) ? ((size_t) ((i - 119) * 1048576)) : 00288 (i < 124) ? ((size_t) ((i - 121) * 4 * 1048576)) : 00289 (i < 126) ? ((size_t) ((i - 123) * 16 * 1048576)) : 00290 (i < 128) ? ((size_t) ((i - 125) * 64 * 1048576)) : 00291 (i < 130) ? ((size_t) ((i - 127) * 256 * 1048576)) : 00292 ((size_t) ((i - 129) * 1024 * 1048576)); 00293 } 00294 #else 00295 #if 0 00296 if (i < 64) { 00297 return (size_t) ((i+1) << 3); 00298 } 00299 #endif 00300 return bins[i]; 00301 #endif 00302 } 00303 00304 inline int getSizeClass (const size_t sz) { 00305 size_t sz1 = sz - 1; 00306 if (sz1 <= 513) { 00307 return sz1 >> 3; 00308 } else { 00309 #if 0 00310 // size_t sz1 = sz - 1; 00311 sz1 >>= 6; 00312 if (sz1 <= 32) { 00313 return 56 + sz1; 00314 } 00315 sz1 >>= 3; 00316 if (sz1 <= 20) { 00317 return 91 + sz1; 00318 } 00319 sz1 >>= 3; 00320 if (sz1 <= 10) { 00321 return 110 - 6 + sz1; 00322 } 00323 sz1 >>= 3; 00324 if (sz1 <= 4) { 00325 return 119 - 6 + sz1; 00326 } 00327 sz1 >>= 3; 00328 if (sz1 <= 2) { 00329 return 124 - 6 + sz1; 00330 } 00331 return 125 - 6 + log2(sz1 >> 2); 00332 #else 00333 const size_t sz1 = sz - 1; 00334 return (((sz1 >> 6) <= 32)? 56 + (sz1 >> 6): 00335 ((sz1 >> 9) <= 20)? 91 + (sz1 >> 9): 00336 ((sz1 >> 12) <= 10)? 110 - 6 + (sz1 >> 12): 00337 ((sz1 >> 15) <= 4)? 119 - 6 + (sz1 >> 15): 00338 ((sz1 >> 18) <= 2)? 124 - 6 + (sz1 >> 18): 126 - 6 + log2(sz1>>19)); 00339 #endif 00340 } 00341 } 00342 00343 } 00344 00345 00351 namespace DLSmallHeapNS { 00352 enum { NUMBINS = 8 }; 00353 inline int getSizeClass (const size_t sz) { 00354 return (int) ((sz-1) >> 3); 00355 } 00356 inline size_t getClassSize (const int i) { 00357 assert (i >= 0); 00358 assert (i < NUMBINS); 00359 return (size_t) ((i+1) << 3); 00360 } 00361 } 00362 00363 #if 0 00364 00365 #include "kingsleyheap.h" 00366 00373 template <class super> 00374 class DLBigHeapType : 00375 public 00376 CoalesceHeap<RequireCoalesceable< 00377 SegHeap<Kingsley::NUMBINS, 00378 Kingsley::size2Class, 00379 Kingsley::class2Size, 00380 AdaptHeap<DLList, NullHeap<super> >, 00381 super> > > 00382 {}; 00383 00384 #else 00385 00386 template <class super> 00387 class DLBigHeapType : 00388 public 00389 CoalesceHeap<RequireCoalesceable< 00390 SegHeap<DLBigHeapNS::NUMBINS, 00391 DLBigHeapNS::getSizeClass, 00392 DLBigHeapNS::getClassSize, 00393 AdaptHeap<DLList, NullHeap<super> >, 00394 super> > > 00395 {}; 00396 00397 #endif 00398 00405 template <class super> 00406 class DLSmallHeapType : 00407 public RequireCoalesceable< 00408 StrictSegHeap<DLSmallHeapNS::NUMBINS, 00409 DLSmallHeapNS::getSizeClass, 00410 DLSmallHeapNS::getClassSize, 00411 AdaptHeap<HL::SLList, NullHeap<super> >, 00412 super> > {}; 00413 00414 00427 template <class Sbrk, class Mmap> 00428 class LeaHeap : 00429 public 00430 SelectMmapHeap<128 * 1024, 00431 Threshold<4096, 00432 DLSmallHeapType<DLBigHeapType<CoalesceableHeap<Sbrk> > > >, 00433 CoalesceableMmapHeap<Mmap> > 00434 {}; 00435 00436 } 00437 00438 #endif