source: proiecte/swift/trunk/lib/hoard-371/src/heaplayers/experimental/testcoalesceableheap.h @ 176

Last change on this file since 176 was 176, checked in by (none), 14 years ago
  • imported repo from "guagal"
File size: 11.4 KB
Line 
1// -*- C++ -*-
2
3// CoalesceableHeap: manages a range of coalesceable memory.
4
5#ifndef _COALESCEABLEHEAP_H_
6#define _COALESCEABLEHEAP_H_
7
8#include <assert.h>
9#include <new.h>
10
11#define MULTIPLE_HEAP_SUPPORT 0
12#define USE_TOP 0
13
14template <class SuperHeap>
15class RequireCoalesceable : public SuperHeap {
16public:
17
18  // Some thin wrappers over Header methods.
19  inline static int getHeap (void * ptr)          { return Header::getHeader(ptr)->getHeap(); }
20  inline static void setHeap (void * ptr, int h)  { Header::getHeader(ptr)->setHeap(h); }
21  inline static int getPrevHeap (void * ptr)      { return Header::getHeader(ptr)->getPrevHeap(); }
22  inline static void setPrevHeap (void * ptr, int h) { Header::getHeader(ptr)->setPrevHeap(h); }
23
24  inline static size_t getSize (void * ptr)       { return Header::getHeader(ptr)->getSize(); }
25
26  inline static void setSize (void * ptr, size_t sz) { Header::getHeader(ptr)->setSize(sz); }
27  inline static size_t getPrevSize (void * ptr)   { return Header::getHeader(ptr)->getPrevSize(); }
28  inline static void setPrevSize (void * ptr, size_t sz) { Header::getHeader(ptr)->setPrevSize(sz); }
29  inline static void markFree (void * ptr)        { Header::getHeader(ptr)->markFree(); }
30  inline static void markInUse (void * ptr)       { Header::getHeader(ptr)->markInUse(); }
31  inline static void markPrevInUse (void * ptr)   { Header::getHeader(ptr)->markPrevInUse(); }
32  inline static void markMmapped (void * ptr)     { Header::getHeader(ptr)->markMmapped(); }
33  inline static int isFree (void * ptr)           { return Header::getHeader(ptr)->isFree(); }
34  inline static int isPrevFree (void * ptr)       { return Header::getHeader(ptr)->isPrevFree(); }
35  inline static int isMmapped (void * ptr)        { return Header::getHeader(ptr)->isMmapped(); }
36  inline static void * getNext (void * ptr)       { return Header::getHeader(ptr)->getNext(); }
37  inline static void * getPrev (void * ptr)       { return Header::getHeader(ptr)->getPrev(); }
38
39
40  // The Header for every object, allocated or freed.
41  class Header {
42  public:
43
44    // Returns the start of the object (i.e., just past the header).
45    inline static void * makeObject (void * buf, size_t prevsz, size_t sz) {
46      Header * h = new (buf) Header (prevsz, sz);
47      // Record this object as in use in the next header.
48      h->markInUse();
49      // Record this object's size in the next header.
50      h->getNextHeader()->setPrevSize (sz);
51      return Header::getObject (h);
52    }
53
54#if USE_TOP
55    // Returns the start of the object, but without updating the next header.
56    inline static void * makeTop (void * buf, size_t prevsz, size_t sz) {
57      Header * h = new (buf) Header (prevsz, sz);
58      // Pretend the previous object is in use to prevent us from
59      // accidentally coalescing backwards with non-existent memory.
60      h->markPrevInUse();
61      h->markInUse();
62      return Header::getObject (h);
63    }
64#endif
65
66    inline void sanityCheck (void) {
67#ifndef NDEBUG
68      int headerSize = sizeof(Header);
69      assert (headerSize <= sizeof(double));
70      assert (getSize() == getNextHeader()->getPrevSize());
71      assert (isFree() == getNextHeader()->isPrevFree());
72      assert (getNextHeader()->getPrev() == getObject(this));
73#if 0
74      if (isPrevFree()) {
75        assert (getPrevSize() == getHeader(getPrev())->getSize());
76      }
77#endif
78#endif
79    }
80
81    // Get the header for a given object.
82    inline static Header * getHeader (const void * ptr) { return ((Header *) ptr - 1); }
83
84    // Get the object for a given header.
85    inline static void * getObject (const Header * hd)  { return (void *) (hd + 1); }
86
87    inline void setPrevSize (const size_t sz){ _prevSize = sz >> SIZE_SHIFT; }
88    inline size_t getPrevSize (void) const { return _prevSize << SIZE_SHIFT; }
89
90    inline void markFree (void)        { getNextHeader()->markPrevFree(); }
91    inline void markInUse (void)       { getNextHeader()->markPrevInUse(); }
92    inline void markMmapped (void)     { setIsMmapped(); } // _isMmapped = IS_MMAPPED; }
93    inline void markNotMmapped (void)  { setIsNotMmapped(); } // _isMmapped = NOT_MMAPPED; }
94    inline int isFree (void) const     { return getNextHeader()->isPrevFree(); }
95    inline int isNextFree (void) const { return getNextHeader()->getNextHeader()->isPrevFree(); }
96    inline int isMmapped (void) const  { return getIsMmapped(); } // _isMmapped == IS_MMAPPED; }
97    inline void * getPrev (void) const { return ((char *) this) - getPrevSize(); }
98    inline void * getNext (void) const { return ((char *) (this + 2)) + getSize(); }
99
100    inline void markPrevFree (void)    { setPrevIsFree(); } // _prevStatus = FREE; }
101    inline void markPrevInUse (void)   { setPrevInUse(); } //_prevStatus = IN_USE; }
102    inline int isPrevFree (void) const { return getPrevIsFree(); } // return _prevStatus == FREE; }
103    inline void setSize (size_t sz) {
104      _size = ((sz >> SIZE_SHIFT) << 2) | (_size & 3);
105    }
106
107    inline size_t getSize (void) const {
108      return (_size >> 2) << SIZE_SHIFT;
109    }
110
111        //    inline size_t getSize (void) const { return getSize(); } // return _size << SIZE_SHIFT; }
112//    inline void setSize (const size_t sz)    { setSize(sz); } // _size = sz >> SIZE_SHIFT; }
113
114#if MULTIPLE_HEAP_SUPPORT
115    inline int getHeap (void) const { return _currHeap; }
116    inline void setHeap (int h)     { _currHeap = h; }
117    inline int getPrevHeap (void) const { return _prevHeap; }
118    inline void setPrevHeap (int h) { _prevHeap = h; }
119#else
120    inline int getHeap (void) const { return 0; }
121    inline void setHeap (int)       {  }
122    inline int getPrevHeap (void) const { return 0; }
123    inline void setPrevHeap (int)   {  }
124#endif
125
126
127  private:
128
129    inline Header (void) {}
130    inline Header (size_t prevsz, size_t sz)
131      :
132        // Record sizes, shifting to account for "stolen bits".
133        _prevSize (prevsz >> SIZE_SHIFT)
134#if 0
135       ,_size (sz >> SIZE_SHIFT),
136        // Assume that objects are NOT mmapped.
137        _isMmapped (NOT_MMAPPED)
138#if MULTIPLE_HEAP_SUPPORT
139        , _prevHeap (0),
140        _currHeap (0)
141#endif
142#endif
143      {
144                        _size = 0;
145        setSize (sz);
146        setIsNotMmapped();
147        assert (sizeof(Header) <= sizeof(double));
148      }
149
150    inline Header * getNextHeader (void) const {
151      return ((Header *) ((char *) (this + 1) + getSize()));
152    }
153
154    // How many bits we can shift size over without losing information.
155    //   3 = double-word alignment.
156    enum { SIZE_SHIFT = 3 };
157
158#if !(MULTIPLE_HEAP_SUPPORT) // original
159
160    inline int getIsMmapped (void) const {
161      return _size & 1;
162    }
163
164    inline void setIsMmapped (void) {
165      _size |= 1;
166    }
167
168    inline void setIsNotMmapped (void) {
169      _size &= ~1;
170    }
171
172    inline int getPrevIsFree (void) const {
173      return _size & 2;
174    }
175
176    inline void setPrevIsFree (void) {
177      _size |= 2;
178    }
179
180    inline void setPrevInUse (void) {
181      _size &= ~2;
182    }
183
184
185#if 1
186    // The size of the previous object.
187    size_t _prevSize;
188
189    // The size of the current object, with NOT_MMAPPED & IN_USE bits.
190    size_t _size;
191   
192#else
193    // The size of the previous object.
194    enum { NUM_BITS_STOLEN_FROM_PREVSIZE = 0 };
195    size_t _prevSize : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_PREVSIZE;
196
197    // The size of the current object.
198    enum { NUM_BITS_STOLEN_FROM_SIZE = 2 };
199    size_t _size : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_SIZE;
200   
201    // Is the current object mmapped?
202    enum { NOT_MMAPPED = 0, IS_MMAPPED = 1 };
203    unsigned int _isMmapped : 1;
204   
205    // Is the previous object free or in use?
206    enum { IN_USE = 0, FREE = 1 };
207    unsigned int _prevStatus : 1;
208#endif
209
210#else // new support for scalability...
211
212    // Support for 2^5 = 32 heaps.
213    enum { NUM_BITS_FOR_HEAP = 5 };
214
215    enum { NUM_BITS_STOLEN_FROM_SIZE = NUM_BITS_FOR_HEAP + 1 };     // 1 for isMmapped
216    enum { NUM_BITS_STOLEN_FROM_PREVSIZE = NUM_BITS_FOR_HEAP + 1 }; // 1 for isPrevFree
217
218    // Max object size.
219    enum { MAX_OBJECT_SIZE = 1 << (sizeof(size_t) * 8 + SIZE_SHIFT - NUM_BITS_STOLEN_FROM_SIZE) };
220
221    //// word 1 ////
222
223    // The size of the previous object.
224    size_t _prevSize : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_PREVSIZE;
225
226    // What's the previous heap?
227    unsigned int _prevHeap : NUM_BITS_FOR_HEAP;
228
229    // Is the previous object free or in use?
230    enum { FREE = 0, IN_USE = 1 };
231    unsigned int _prevStatus : 1;
232
233    //// word 2 ////
234
235    // The size of the current object.
236    size_t _size : sizeof(size_t) * 8 - NUM_BITS_STOLEN_FROM_SIZE;
237
238    // What's the current heap?
239    unsigned int _currHeap : NUM_BITS_FOR_HEAP;
240
241    // Is the current object mmapped?
242    enum { NOT_MMAPPED = 0, IS_MMAPPED = 1 };
243    unsigned int _isMmapped : 1;
244
245#endif
246  };
247
248};
249
250
251
252template <class SuperHeap>
253class CoalesceableHeap : public RequireCoalesceable<SuperHeap> {
254public:
255
256  CoalesceableHeap (void)
257#if USE_TOP
258          : top (NULL)
259#endif
260  { }
261
262  inline void * malloc (size_t sz) {
263#if !USE_TOP
264          void * buf = SuperHeap::malloc (sz + sizeof(Header));
265          if (buf == NULL) {
266                  return NULL;
267          } else {
268                  Header * header = (Header *) buf;
269
270                  //
271                  // Assume that everything allocated is NOT mmapped.
272                  // It is the responsibility of a child layer
273                  // to mark mmapped objects as such.
274                  //
275
276                  header->markNotMmapped ();
277
278                  //
279                  // Record the size of this object in the current header
280                  // and the next.
281                  //
282
283                  header->setSize (sz);
284                  Header * nextHeader = Header::getHeader (header->getNext());
285                  nextHeader->setSize (0);
286                  nextHeader->setPrevSize (sz);
287
288                  //
289                  // Mark the subsequent "object" as in use in order to prevent
290                  // accidental coalescing.
291                  //
292
293                  nextHeader->markInUse ();
294                  return Header::getObject (header);
295          }
296#else
297
298    if ((top == NULL) || (sz + sizeof(Header) > getSize(top))) {
299      // There wasn't enough space in top. Get more memory (enough to
300      // hold an extra header).
301      void * buf = SuperHeap::malloc (sz + 2 * sizeof(Header));
302      if (buf == NULL)
303        return NULL;
304      void * ptr = Header::makeTop (buf, 0, sz);
305      // Is this object contiguous with top?
306      if ((top != NULL) && (getNext(top) == ptr)) {
307        // It is contiguous. Extend top.
308        setSize (top, getSize(top) + 2 * sizeof(Header) + sz);
309
310         // printf ("Extended top by %d\n", getSize(ptr));
311
312      } else {
313        // We got some non-contiguous memory.
314        // For now, just abandon top.
315
316         // printf ("Abandoning top.\n");
317        setSize (ptr, sz + sizeof(Header));
318        top = ptr;
319      }
320    }
321    assert (getSize(top) >= sz + sizeof(Header));
322    // Carve out an sz object from top and advance top.
323    size_t oldTopSize = getSize(top);
324    void * newObject = top;
325    setSize (newObject, sz);
326    top = getNext (newObject);
327    // Set top's new header.
328    setSize (top, oldTopSize - sz - sizeof(Header));
329    setPrevSize (top, sz);
330    // Mark the new top as in use to prevent it from being coalesced.
331
332    markInUse (top);
333
334        assert (getNext(newObject) == top);
335    Header::getHeader(newObject)->sanityCheck();
336        //printf ("top = %x\n", top);
337        assert (!isFree(top));
338    return newObject;
339#endif
340  }
341 
342  inline void free (void * ptr) {
343    assert (isFree(ptr));
344#if USE_TOP
345    // Try to extend top if this object is right before it.
346    if (getNext(ptr) == top) {
347      assert (getSize(ptr) == getPrevSize(top));
348      // Extend top backwards.
349      setSize (ptr, getSize(ptr) + sizeof(Header) + getSize(top));
350      top = ptr;
351        // printf ("free: top = %x\n", top);
352      return;
353    }
354#endif
355    SuperHeap::free (Header::getHeader(ptr));
356  }
357
358
359#if USE_TOP
360  inline void clear (void) {
361    top = NULL;
362    SuperHeap::clear ();
363  }
364#endif
365
366private:
367
368#if USE_TOP
369  // The top object allocated so far.
370  void * top;
371#endif
372
373};
374
375
376#endif // _COALESCEABLEHEAP_H_
377
Note: See TracBrowser for help on using the repository browser.