Eneboo - Documentación para desarrolladores
src/hoard/src/heaplayers/experimental/testcoalesceableheap.h
Ir a la documentación de este archivo.
00001 // -*- C++ -*-
00002 
00003 // CoalesceableHeap: manages a range of coalesceable memory.
00004 
00005 #ifndef _COALESCEABLEHEAP_H_
00006 #define _COALESCEABLEHEAP_H_
00007 
00008 #include <assert.h>
00009 #include <new.h>
00010 
00011 #define MULTIPLE_HEAP_SUPPORT 0
00012 #define USE_TOP 0
00013 
00014 template <class SuperHeap>
00015 class RequireCoalesceable : public SuperHeap {
00016 public:
00017 
00018   // Some thin wrappers over Header methods.
00019   inline static int getHeap (void * ptr)          { return Header::getHeader(ptr)->getHeap(); }
00020   inline static void setHeap (void * ptr, int h)  { Header::getHeader(ptr)->setHeap(h); }
00021   inline static int getPrevHeap (void * ptr)      { return Header::getHeader(ptr)->getPrevHeap(); }
00022   inline static void setPrevHeap (void * ptr, int h) { Header::getHeader(ptr)->setPrevHeap(h); }
00023 
00024   inline static size_t getSize (void * ptr)       { return Header::getHeader(ptr)->getSize(); }
00025 
00026   inline static void setSize (void * ptr, size_t sz) { Header::getHeader(ptr)->setSize(sz); }
00027   inline static size_t getPrevSize (void * ptr)   { return Header::getHeader(ptr)->getPrevSize(); }
00028   inline static void setPrevSize (void * ptr, size_t sz) { Header::getHeader(ptr)->setPrevSize(sz); }
00029   inline static void markFree (void * ptr)        { Header::getHeader(ptr)->markFree(); }
00030   inline static void markInUse (void * ptr)       { Header::getHeader(ptr)->markInUse(); }
00031   inline static void markPrevInUse (void * ptr)   { Header::getHeader(ptr)->markPrevInUse(); }
00032   inline static void markMmapped (void * ptr)     { Header::getHeader(ptr)->markMmapped(); }
00033   inline static int isFree (void * ptr)           { return Header::getHeader(ptr)->isFree(); }
00034   inline static int isPrevFree (void * ptr)       { return Header::getHeader(ptr)->isPrevFree(); }
00035   inline static int isMmapped (void * ptr)        { return Header::getHeader(ptr)->isMmapped(); }
00036   inline static void * getNext (void * ptr)       { return Header::getHeader(ptr)->getNext(); }
00037   inline static void * getPrev (void * ptr)       { return Header::getHeader(ptr)->getPrev(); }
00038 
00039 
00040   // The Header for every object, allocated or freed.
00041   class Header {
00042   public:
00043 
00044     // Returns the start of the object (i.e., just past the header).
00045     inline static void * makeObject (void * buf, size_t prevsz, size_t sz) {
00046       Header * h = new (buf) Header (prevsz, sz);
00047       // Record this object as in use in the next header.
00048       h->markInUse();
00049       // Record this object's size in the next header.
00050       h->getNextHeader()->setPrevSize (sz);
00051       return Header::getObject (h);
00052     }
00053 
00054 #if USE_TOP
00055     // Returns the start of the object, but without updating the next header.
00056     inline static void * makeTop (void * buf, size_t prevsz, size_t sz) {
00057       Header * h = new (buf) Header (prevsz, sz);
00058       // Pretend the previous object is in use to prevent us from
00059       // accidentally coalescing backwards with non-existent memory.
00060       h->markPrevInUse();
00061       h->markInUse();
00062       return Header::getObject (h);
00063     }
00064 #endif
00065 
00066     inline void sanityCheck (void) {
00067 #ifndef NDEBUG
00068       int headerSize = sizeof(Header);
00069       assert (headerSize <= sizeof(double));
00070       assert (getSize() == getNextHeader()->getPrevSize());
00071       assert (isFree() == getNextHeader()->isPrevFree());
00072       assert (getNextHeader()->getPrev() == getObject(this));
00073 #if 0
00074       if (isPrevFree()) {
00075         assert (getPrevSize() == getHeader(getPrev())->getSize());
00076       }
00077 #endif
00078 #endif
00079     }
00080 
00081     // Get the header for a given object.
00082     inline static Header * getHeader (const void * ptr) { return ((Header *) ptr - 1); }
00083 
00084     // Get the object for a given header.
00085     inline static void * getObject (const Header * hd)  { return (void *) (hd + 1); }
00086 
00087     inline void setPrevSize (const size_t sz){ _prevSize = sz >> SIZE_SHIFT; }
00088     inline size_t getPrevSize (void) const { return _prevSize << SIZE_SHIFT; }
00089 
00090     inline void markFree (void)        { getNextHeader()->markPrevFree(); }
00091     inline void markInUse (void)       { getNextHeader()->markPrevInUse(); }
00092     inline void markMmapped (void)     { setIsMmapped(); } // _isMmapped = IS_MMAPPED; }
00093     inline void markNotMmapped (void)  { setIsNotMmapped(); } // _isMmapped = NOT_MMAPPED; }
00094     inline int isFree (void) const     { return getNextHeader()->isPrevFree(); }
00095     inline int isNextFree (void) const { return getNextHeader()->getNextHeader()->isPrevFree(); }
00096     inline int isMmapped (void) const  { return getIsMmapped(); } // _isMmapped == IS_MMAPPED; }
00097     inline void * getPrev (void) const { return ((char *) this) - getPrevSize(); }
00098     inline void * getNext (void) const { return ((char *) (this + 2)) + getSize(); }
00099 
00100     inline void markPrevFree (void)    { setPrevIsFree(); } // _prevStatus = FREE; }
00101     inline void markPrevInUse (void)   { setPrevInUse(); } //_prevStatus = IN_USE; }
00102     inline int isPrevFree (void) const { return getPrevIsFree(); } // return _prevStatus == FREE; }
00103     inline void setSize (size_t sz) {
00104       _size = ((sz >> SIZE_SHIFT) << 2) | (_size & 3);
00105     }
00106 
00107     inline size_t getSize (void) const {
00108       return (_size >> 2) << SIZE_SHIFT;
00109     }
00110 
00111         //    inline size_t getSize (void) const { return getSize(); } // return _size << SIZE_SHIFT; }
00112 //    inline void setSize (const size_t sz)    { setSize(sz); } // _size = sz >> SIZE_SHIFT; }
00113 
00114 #if MULTIPLE_HEAP_SUPPORT
00115     inline int getHeap (void) const { return _currHeap; }
00116     inline void setHeap (int h)     { _currHeap = h; }
00117     inline int getPrevHeap (void) const { return _prevHeap; }
00118     inline void setPrevHeap (int h) { _prevHeap = h; }
00119 #else
00120     inline int getHeap (void) const { return 0; }
00121     inline void setHeap (int)       {  }
00122     inline int getPrevHeap (void) const { return 0; }
00123     inline void setPrevHeap (int)   {  }
00124 #endif
00125 
00126 
00127   private:
00128 
00129     inline Header (void) {}
00130     inline Header (size_t prevsz, size_t sz)
00131       :
00132         // Record sizes, shifting to account for "stolen bits".
00133         _prevSize (prevsz >> SIZE_SHIFT)
00134 #if 0
00135        ,_size (sz >> SIZE_SHIFT),
00136         // Assume that objects are NOT mmapped.
00137         _isMmapped (NOT_MMAPPED)
00138 #if MULTIPLE_HEAP_SUPPORT
00139         , _prevHeap (0),
00140         _currHeap (0)
00141 #endif
00142 #endif
00143       {
00144                         _size = 0;
00145         setSize (sz);
00146         setIsNotMmapped();
00147         assert (sizeof(Header) <= sizeof(double));
00148       }
00149 
00150     inline Header * getNextHeader (void) const {
00151       return ((Header *) ((char *) (this + 1) + getSize()));
00152     }
00153 
00154     // How many bits we can shift size over without losing information.
00155     //   3 = double-word alignment.
00156     enum { SIZE_SHIFT = 3 };
00157 
00158 #if !(MULTIPLE_HEAP_SUPPORT) // original
00159 
00160     inline int getIsMmapped (void) const {
00161       return _size & 1;
00162     }
00163 
00164     inline void setIsMmapped (void) {
00165       _size |= 1;
00166     }
00167 
00168     inline void setIsNotMmapped (void) {
00169       _size &= ~1;
00170     }
00171 
00172     inline int getPrevIsFree (void) const {
00173       return _size & 2;
00174     }
00175 
00176     inline void setPrevIsFree (void) {
00177       _size |= 2;
00178     }
00179 
00180     inline void setPrevInUse (void) {
00181       _size &= ~2;
00182     }
00183 
00184 
00185 #if 1
00186     // The size of the previous object.
00187     size_t _prevSize;
00188 
00189     // The size of the current object, with NOT_MMAPPED & IN_USE bits.
00190     size_t _size;
00191     
00192 #else
00193     // The size of the previous object.
00194     enum { NUM_BITS_STOLEN_FROM_PREVSIZE = 0 };
00195     size_t _prevSize : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_PREVSIZE;
00196 
00197     // The size of the current object.
00198     enum { NUM_BITS_STOLEN_FROM_SIZE = 2 };
00199     size_t _size : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_SIZE;
00200     
00201     // Is the current object mmapped?
00202     enum { NOT_MMAPPED = 0, IS_MMAPPED = 1 };
00203     unsigned int _isMmapped : 1;
00204     
00205     // Is the previous object free or in use?
00206     enum { IN_USE = 0, FREE = 1 };
00207     unsigned int _prevStatus : 1;
00208 #endif
00209 
00210 #else // new support for scalability...
00211 
00212     // Support for 2^5 = 32 heaps.
00213     enum { NUM_BITS_FOR_HEAP = 5 };
00214 
00215     enum { NUM_BITS_STOLEN_FROM_SIZE = NUM_BITS_FOR_HEAP + 1 };     // 1 for isMmapped
00216     enum { NUM_BITS_STOLEN_FROM_PREVSIZE = NUM_BITS_FOR_HEAP + 1 }; // 1 for isPrevFree
00217 
00218     // Max object size.
00219     enum { MAX_OBJECT_SIZE = 1 << (sizeof(size_t) * 8 + SIZE_SHIFT - NUM_BITS_STOLEN_FROM_SIZE) };
00220 
00222 
00223     // The size of the previous object.
00224     size_t _prevSize : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_PREVSIZE;
00225 
00226     // What's the previous heap?
00227     unsigned int _prevHeap : NUM_BITS_FOR_HEAP;
00228 
00229     // Is the previous object free or in use?
00230     enum { FREE = 0, IN_USE = 1 };
00231     unsigned int _prevStatus : 1;
00232 
00234 
00235     // The size of the current object.
00236     size_t _size : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_SIZE;
00237 
00238     // What's the current heap?
00239     unsigned int _currHeap : NUM_BITS_FOR_HEAP;
00240 
00241     // Is the current object mmapped?
00242     enum { NOT_MMAPPED = 0, IS_MMAPPED = 1 };
00243     unsigned int _isMmapped : 1;
00244 
00245 #endif
00246   };
00247 
00248 };
00249 
00250 
00251 
00252 template <class SuperHeap>
00253 class CoalesceableHeap : public RequireCoalesceable<SuperHeap> {
00254 public:
00255 
00256   CoalesceableHeap (void)
00257 #if USE_TOP
00258           : top (NULL)
00259 #endif
00260   { }
00261 
00262   inline void * malloc (size_t sz) {
00263 #if !USE_TOP
00264           void * buf = SuperHeap::malloc (sz + sizeof(Header));
00265           if (buf == NULL) {
00266                   return NULL;
00267           } else {
00268                   Header * header = (Header *) buf;
00269 
00270                   //
00271                   // Assume that everything allocated is NOT mmapped.
00272                   // It is the responsibility of a child layer
00273                   // to mark mmapped objects as such.
00274                   //
00275 
00276                   header->markNotMmapped ();
00277 
00278                   //
00279                   // Record the size of this object in the current header
00280                   // and the next.
00281                   //
00282 
00283                   header->setSize (sz);
00284                   Header * nextHeader = Header::getHeader (header->getNext());
00285                   nextHeader->setSize (0);
00286                   nextHeader->setPrevSize (sz);
00287 
00288                   //
00289                   // Mark the subsequent "object" as in use in order to prevent
00290                   // accidental coalescing.
00291                   //
00292 
00293                   nextHeader->markInUse ();
00294                   return Header::getObject (header);
00295           }
00296 #else
00297 
00298     if ((top == NULL) || (sz + sizeof(Header) > getSize(top))) {
00299       // There wasn't enough space in top. Get more memory (enough to
00300       // hold an extra header).
00301       void * buf = SuperHeap::malloc (sz + 2 * sizeof(Header));
00302       if (buf == NULL)
00303         return NULL;
00304       void * ptr = Header::makeTop (buf, 0, sz);
00305       // Is this object contiguous with top?
00306       if ((top != NULL) && (getNext(top) == ptr)) {
00307         // It is contiguous. Extend top.
00308         setSize (top, getSize(top) + 2 * sizeof(Header) + sz);
00309 
00310          // printf ("Extended top by %d\n", getSize(ptr));
00311 
00312       } else {
00313         // We got some non-contiguous memory.
00314         // For now, just abandon top.
00315 
00316          // printf ("Abandoning top.\n");
00317         setSize (ptr, sz + sizeof(Header));
00318         top = ptr;
00319       }
00320     }
00321     assert (getSize(top) >= sz + sizeof(Header));
00322     // Carve out an sz object from top and advance top.
00323     size_t oldTopSize = getSize(top);
00324     void * newObject = top;
00325     setSize (newObject, sz);
00326     top = getNext (newObject);
00327     // Set top's new header.
00328     setSize (top, oldTopSize - sz - sizeof(Header));
00329     setPrevSize (top, sz);
00330     // Mark the new top as in use to prevent it from being coalesced.
00331 
00332     markInUse (top);
00333 
00334         assert (getNext(newObject) == top);
00335     Header::getHeader(newObject)->sanityCheck();
00336         //printf ("top = %x\n", top);
00337         assert (!isFree(top));
00338     return newObject;
00339 #endif
00340   }
00341   
00342   inline void free (void * ptr) {
00343     assert (isFree(ptr));
00344 #if USE_TOP
00345     // Try to extend top if this object is right before it.
00346     if (getNext(ptr) == top) {
00347       assert (getSize(ptr) == getPrevSize(top));
00348       // Extend top backwards.
00349       setSize (ptr, getSize(ptr) + sizeof(Header) + getSize(top));
00350       top = ptr;
00351         // printf ("free: top = %x\n", top);
00352       return;
00353     }
00354 #endif
00355     SuperHeap::free (Header::getHeader(ptr));
00356   }
00357 
00358 
00359 #if USE_TOP
00360   inline void clear (void) {
00361     top = NULL;
00362     SuperHeap::clear ();
00363   }
00364 #endif
00365 
00366 private:
00367 
00368 #if USE_TOP
00369   // The top object allocated so far.
00370   void * top;
00371 #endif
00372 
00373 };
00374 
00375 
00376 #endif // _COALESCEABLEHEAP_H_
00377 
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Enumeraciones Valores de enumeraciones Propiedades Amigas 'defines'