MemoryPool.cpp

00001 #include "MemoryPool.h"
00002 
00003 #include <cstdio>
00004 
00005 #define offset(x) (((uint8_t*) x) - ((uint8_t*) this->base))
00006 
00007 typedef struct __attribute__ ((packed))
00008 {
00009     uint32_t next :31;
00010     uint32_t used :1;
00011 
00012     uint8_t data[];
00013 } _poolregion;
00014 
00015 MemoryPool* MemoryPool::first = NULL;
00016 
00017 MemoryPool::MemoryPool(void* base, uint16_t size)
00018 {
00019     this->base = base;
00020     this->size = size;
00021 
00022     ((_poolregion*) base)->used = 0;
00023     ((_poolregion*) base)->next = size;
00024 
00025     // insert ourselves into head of LL
00026     next = first;
00027     first = this;
00028 }
00029 
00030 MemoryPool::~MemoryPool()
00031 {
00032     MDEBUG("Pool %p destroyed: region %p (%d)\n", this, base, size);
00033 
00034     // remove ourselves from the LL
00035     if (first == this)
00036     {   // special case: we're first
00037         first = this->next;
00038         return;
00039     }
00040 
00041     // otherwise search the LL for the previous pool
00042     MemoryPool* m = first;
00043     while (m)
00044     {
00045         if (m->next == this)
00046         {
00047             m->next = next;
00048             return;
00049         }
00050         m = m->next;
00051     }
00052 }
00053 
00054 void* MemoryPool::alloc(size_t nbytes)
00055 {
00056     // nbytes = ceil(nbytes / 4) * 4
00057     if (nbytes & 3)
00058         nbytes += 4 - (nbytes & 3);
00059 
00060     // start at the start
00061     _poolregion* p = ((_poolregion*) base);
00062 
00063     // find the allocation size including our metadata
00064     uint16_t nsize = nbytes + sizeof(_poolregion);
00065 
00066     MDEBUG("\tallocate %d bytes from %p\n", nsize, base);
00067 
00068     // now we walk the list, looking for a sufficiently large free block
00069     do {
00070         MDEBUG("\t\tchecking %p (%s, %db)\n", p, (p->used?"used":"free"), p->next);
00071         if ((p->used == 0) && (p->next >= nsize))
00072         {   // we found a free space that's big enough
00073             MDEBUG("\t\tFOUND free block at %p (%+d) with %d bytes\n", p, offset(p), p->next);
00074             // mark it as used
00075             p->used = 1;
00076 
00077             // if there's free space at the end of this block
00078             if (p->next > nsize)
00079             {
00080                 // q = p->next
00081                 _poolregion* q = (_poolregion*) (((uint8_t*) p) + nsize);
00082 
00083                 MDEBUG("\t\twriting header to %p (%+d) (%d)\n", q, offset(q), p->next - nsize);
00084                 // write a new block header into q
00085                 q->used = 0;
00086                 q->next = p->next - nsize;
00087 
00088                 // set our next to point to it
00089                 p->next = nsize;
00090 
00091                 // sanity check
00092                 if (offset(q) >= size)
00093                 {
00094                     // captain, we have a problem!
00095                     // this can only happen if something has corrupted our heap, since we should simply fail to find a free block if it's full
00096                     //__debugbreak();
00097                 }
00098             }
00099 
00100             // then return the data region for the block
00101             return &p->data;
00102         }
00103 
00104         // p = p->next
00105         p = (_poolregion*) (((uint8_t*) p) + p->next);
00106 
00107         // make sure we don't walk off the end
00108     } while (p <= (_poolregion*) (((uint8_t*)base) + size));
00109 
00110     // fell off the end of the region!
00111     return NULL;
00112 }
00113 
00114 void MemoryPool::dealloc(void* d)
00115 {
00116     _poolregion* p = (_poolregion*) (((uint8_t*) d) - sizeof(_poolregion));
00117     p->used = 0;
00118 
00119     MDEBUG("\tdeallocating %p (%+d, %db)\n", p, offset(p), p->next);
00120 
00121     // combine next block if it's free
00122     _poolregion* q = (_poolregion*) (((uint8_t*) p) + p->next);
00123     if (q->used == 0)
00124     {
00125         MDEBUG("\t\tCombining with next free region at %p, new size is %d\n", q, p->next + q->next);
00126 
00127         // sanity check
00128         if (offset(q) > size)
00129         {
00130             // captain, we have a problem!
00131             // this can only happen if something has corrupted our heap, since we should simply fail to find a free block if it's full
00132             //__debugbreak();
00133         }
00134 
00135         p->next += q->next;
00136     }
00137 
00138     // walk the list to find previous block
00139     q = (_poolregion*) base;
00140     do {
00141         // check if q is the previous block
00142         if ((((uint8_t*) q) + q->next) == (uint8_t*) p) {
00143             // q is the previous block.
00144             if (q->used == 0)
00145             { // if q is free
00146                 MDEBUG("\t\tCombining with previous free region at %p, new size is %d\n", q, p->next + q->next);
00147 
00148                 // combine!
00149                 q->next += p->next;
00150 
00151                 // sanity check
00152                 if ((offset(p) + p->next) >= size)
00153                 {
00154                     // captain, we have a problem!
00155                     // this can only happen if something has corrupted our heap, since we should simply fail to find a free block if it's full
00156                     //__debugbreak();
00157                 }
00158             }
00159 
00160             // we found previous block, return
00161             return;
00162         }
00163 
00164         // return if last block
00165         if (offset(q) + q->next >= size)
00166             return;
00167 
00168         // q = q->next
00169         q = (_poolregion*) (((uint8_t*) q) + q->next);
00170 
00171         // if some idiot deallocates our memory region while we're using it, strange things can happen.
00172         // avoid an infinite loop in that case, however we'll still leak memory and may corrupt things
00173         if (q->next == 0)
00174             return;
00175 
00176         // make sure we don't walk off the end
00177     } while (q < (_poolregion*) (((uint8_t*) base) + size));
00178 }
00179 
00180 void MemoryPool::debug(StreamOutput* str)
00181 {
00182     _poolregion* p = (_poolregion*) base;
00183     uint32_t tot = 0;
00184     uint32_t free = 0;
00185     str->printf("Start: %ub MemoryPool at %p\n", size, p);
00186     do {
00187         str->printf("\tChunk at %p (%+4d): %s, %lu bytes\n", p, offset(p), (p->used?"used":"free"), p->next);
00188         tot += p->next;
00189         if (p->used == 0)
00190             free += p->next;
00191         if ((offset(p) + p->next >= size) || (p->next <= sizeof(_poolregion)))
00192         {
00193             str->printf("End: total %lub, free: %lub\n", tot, free);
00194             return;
00195         }
00196         p = (_poolregion*) (((uint8_t*) p) + p->next);
00197     } while (1);
00198 }
00199 
00200 bool MemoryPool::has(void* p)
00201 {
00202     return ((p >= base) && (p < (void*) (((uint8_t*) base) + size)));
00203 }
00204 
00205 uint32_t MemoryPool::free()
00206 {
00207     uint32_t free = 0;
00208 
00209     _poolregion* p = (_poolregion*) base;
00210 
00211     do {
00212         if (p->used == 0)
00213             free += p->next;
00214         if (offset(p) + p->next >= size)
00215             return free;
00216         if (p->next <= sizeof(_poolregion))
00217             return free;
00218         p = (_poolregion*) (((uint8_t*) p) + p->next);
00219     } while (1);
00220 }