Eneboo - Documentación para desarrolladores
src/hoard/src/heaplayers/dlheap.h
Ir a la documentación de este archivo.
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
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Enumeraciones Valores de enumeraciones Propiedades Amigas 'defines'