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

Last change on this file since 176 was 176, checked in by (none), 14 years ago
  • imported repo from "guagal"
File size: 7.7 KB
Line 
1/* -*- C++ -*- */
2
3#ifndef _AOFHEAP_H_
4#define _AOFHEAP_H_
5
6#include <new> // for placement new
7using namespace std;
8
9/*
10 
11  A very simple address-oriented first-fit heap
12  with immediate coalescing.
13
14  Because the heap is stored as a sorted doubly-linked list,
15  it's potentially quite expensive:
16
17  cost of a malloc = O(f) {# of non-contiguous freed objects}
18  cost of a free   = O(f) {# of non-contiguous freed objects}
19
20  Worst-case performance could be improved by using a balanced O(log n) dictionary
21  (like an RB-tree). Also, the free list is threaded through the objects themselves,
22  something that can cause O(f) page faults; keeping the free list data structures
23  separate from the data (and in a contiguous region of memory) would avoid this problem.
24
25*/
26
27// Freed objects of at least FreeThreshold size are freed to the super heap.
28
29template <class SuperHeap, int FreeThreshold>
30class AOFFHeap : public SuperHeap {
31public:
32
33  AOFFHeap (void)
34  {
35    freeList.setSize (0);
36    freeList.setNext (&freeList);
37    freeList.setPrev (&freeList);
38  }
39
40  ~AOFFHeap (void) {
41    return; // FIX ME FIX ME FIX ME!!!
42    // Free everything on the free list.
43    freedObject * ptr = freeList.getNext();
44    while (ptr != &freeList) {
45      freedObject * prev = ptr;
46      ptr = ptr->getNext();
47      SuperHeap::free (prev);
48    }
49  }
50
51  void * malloc (size_t sz) {
52    // printf ("aoffheap malloc sz = %d\n", sz);
53    assert (isValid());
54    assert (sz >= sizeof(freedObject) - sizeof(allocatedObject));
55    // Find the first object in the free list that fits.
56    freedObject * ptr = freeList.getNext();
57    while ((ptr != &freeList) && (ptr->getSize() < sz + sizeof(freedObject))) {
58      ptr = ptr->getNext();
59    }
60    // If there wasn't a big-enough object available on the free list,
61    // make a new one.
62    if (ptr == &freeList) {
63
64      // printf ("AOFF super malloc(%d)\n", sz + sizeof(allocatedObject));
65
66      void * buf = SuperHeap::malloc (sz + sizeof(allocatedObject));
67      if (buf == NULL) {
68        assert (isValid());
69        return NULL;
70      }
71      freedObject * newptr
72        = new (buf) freedObject (sz, NULL, NULL);
73      assert (size(newptr->getStart()) == sz);
74      assert (isValid());
75      return (void *) newptr->getStart();
76    } else {
77      assert (ptr->getSize() >= sz);
78      // Remove it from the free list.
79      freedObject * prev = ptr->getPrev();
80      freedObject * next = ptr->getNext();
81      assert (prev->isValid());
82      assert (next->isValid());
83      // If it's bigger than the request size,
84      // splice it up.
85      if (ptr->getSize() - sz >= sizeof(freedObject)) {
86                                // There's room for another object.
87                                // Splice it off.
88        size_t oldSize = ptr->getSize();
89        ptr->setSize (sz);
90        freedObject * splicedObj = new (ptr->getSuccessor())
91          freedObject (oldSize - sz - sizeof(freedObject),
92                       prev,
93                       next);
94        prev->setNext (splicedObj);
95        next->setPrev (splicedObj);
96        assert (splicedObj->isValid());
97        assert (isValid());
98        assert (size(ptr->getStart()) == sz);
99        return (void *) ptr->getStart();
100      } else {
101        assert (0);
102        abort();
103                                // It's just right.
104                                // Just remove it.
105        prev->setNext (next);
106        next->setPrev (prev);
107        assert (isValid());
108        assert (size(ptr->getStart()) == sz);
109        return (void *) ptr->getStart();
110      }
111    }
112  }
113
114  void free (void * p) {
115    assert (isValid());
116    // Put the object back in sorted order (by address).
117    freedObject * thisObject = (freedObject *) ((char *) p - sizeof(allocatedObject));
118    assert (thisObject->getStart() == p);
119    freedObject * prev = &freeList;
120    freedObject * next = freeList.getNext();
121    while ((next != &freeList) && ((char *) thisObject > (char *) next)) {
122      prev = next;
123      next = next->getNext();
124    }
125    // Check if this object is already on the free list
126    // (i.e., it was already deleted).
127    if (thisObject == next) {
128      // printf ("Bad call.\n");
129      // Ignore the bad programmer and just walk away...
130      return;
131    }
132    // Now insert this object.
133    prev->setNext (thisObject);
134    next->setPrev (thisObject);
135    thisObject = new (thisObject) freedObject (thisObject->getSize(), prev, next);
136    // See if we can coalesce.
137    if (prev->getSuccessor() == thisObject) {
138      assert (prev != &freeList);
139      coalesce (prev, thisObject);
140      thisObject = prev;
141      assert (thisObject->isValid());
142      assert (thisObject->getSize() > 0);
143      // printf ("coalesced prev with this, new size = %d\n", thisObject->getSize());
144    }
145    if (thisObject->getSuccessor() == next) {
146      coalesce (thisObject, next);
147      assert (thisObject->isValid());
148      //printf ("coalesced this with next, new size = %d\n", thisObject->getSize());
149    }
150    // If this object is big enough, free it.
151    if (thisObject->getSize() >= FreeThreshold) {
152      // printf ("freed this (size = %d)\n", thisObject->getSize());
153      freedObject * prev = thisObject->getPrev();
154      freedObject * next = thisObject->getNext();
155      prev->setNext (next);
156      next->setPrev (prev);
157      assert (thisObject->isValid());
158      SuperHeap::free (thisObject);
159    }
160    assert (isValid());
161  }
162
163  //protected:
164  inline static size_t size (void * p)
165  {
166    allocatedObject * thisObject = (allocatedObject *) p - 1;
167    assert (thisObject->isValid());
168    return thisObject->getSize();
169  }
170
171
172private:
173
174  int isValid (void) {
175    // March through the whole list and check for validity.
176    freedObject * ptr = freeList.getNext();
177    while (ptr != &freeList) {
178      freedObject * prev = ptr;
179      assert (prev->getNext()->getPrev() == prev);
180      assert (prev->isValid());
181      ptr = ptr->getNext();
182    }
183    return 1;
184  }
185
186  class freedObject;
187
188  inline void coalesce (freedObject * curr, freedObject * succ) {
189    // printf ("Coalesce %d with %d\n", curr->getSize(), succ->getSize());
190    assert (curr->getSuccessor() == succ);
191    assert (succ->getPrev() == curr);
192    assert (curr->getNext() == succ);
193    curr->setNext (succ->getNext());
194    succ->getNext()->setPrev(curr);
195    curr->setSize (curr->getSize() + succ->getSize() + sizeof(allocatedObject));
196    assert (curr->isValid());
197  }
198  inline static size_t align (int sz) {
199    return (sz + (sizeof(double) - 1)) & ~(sizeof(double) - 1);
200  }
201
202  class allocatedObject {
203  public:
204    allocatedObject (void)
205    {
206      size = 0;
207#ifndef NDEBUG
208      magic = 0xfacefade;
209#endif
210    }
211    int isValid (void) const {
212      return (size >= 0) && (magic == 0xfacefade);
213    }
214    void setSize (size_t sz) { size = sz; assert (isValid()); }
215    int getSize (void) const { assert (isValid()); return size; }
216
217    // Return the start of the next object.
218    allocatedObject * getSuccessor (void) const {
219      assert (isValid());
220      return (allocatedObject *) ((char *) (this + 1) + size);
221    }
222
223    // Return the start of the actual object (beyond the header).
224    char * getStart (void) const {
225      assert (isValid());
226      return ((char *) (this + 1));
227    }
228  private:
229    int size;
230    int magic;
231  };
232
233  class freedObject : public allocatedObject {
234  public:
235    freedObject (void)
236      : prev ((freedObject *) 0xdeadbeef),
237        next ((freedObject *) 0xdeadbeef)
238    {}
239    freedObject (size_t sz,
240                 freedObject * p,
241                 freedObject * n)
242      : prev (p),
243        next (n)
244    {
245      allocatedObject::setSize (sz);
246    }
247    int isValid (void) const {
248      return (allocatedObject::isValid());
249    }
250    freedObject * getPrev (void) const { assert (isValid()); return prev; }
251    freedObject * getNext (void) const { assert (isValid()); return next; }
252    void setPrev (freedObject * p) { assert (isValid()); prev = p; }
253    void setNext (freedObject * p) { assert (isValid()); next = p; }
254  private:
255    freedObject * prev;
256    freedObject * next;
257  };
258
259
260  freedObject freeList;
261  double _dummy; // Just to make sure that the freeList node won't ever be coalesced!
262};
263
264#endif
Note: See TracBrowser for help on using the repository browser.