Michael Spencer / Smoothie

Fork of Smoothie to port to mbed non-LPC targets.

Dependencies:   mbed

Fork of Smoothie by Stéphane Cachat

libs/MemoryPool.cpp@2:1df0b61d3b5a, 2014-02-28 (annotated)

Committer:
Michael J. Spencer
Date:
Fri Feb 28 18:52:52 2014 -0800
Revision:
2:1df0b61d3b5a
Child:
3:f151d08d335c
Update to latest Smoothie.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
Michael J. Spencer 2:1df0b61d3b5a 1 #include "MemoryPool.h"
Michael J. Spencer 2:1df0b61d3b5a 2
Michael J. Spencer 2:1df0b61d3b5a 3 #include <mri.h>
Michael J. Spencer 2:1df0b61d3b5a 4 #include <cstdio>
Michael J. Spencer 2:1df0b61d3b5a 5
Michael J. Spencer 2:1df0b61d3b5a 6 #define offset(x) (((uint8_t*) x) - ((uint8_t*) this->base))
Michael J. Spencer 2:1df0b61d3b5a 7
Michael J. Spencer 2:1df0b61d3b5a 8 typedef struct __attribute__ ((packed))
Michael J. Spencer 2:1df0b61d3b5a 9 {
Michael J. Spencer 2:1df0b61d3b5a 10 uint32_t next :31;
Michael J. Spencer 2:1df0b61d3b5a 11 uint32_t used :1;
Michael J. Spencer 2:1df0b61d3b5a 12
Michael J. Spencer 2:1df0b61d3b5a 13 uint8_t data[];
Michael J. Spencer 2:1df0b61d3b5a 14 } _poolregion;
Michael J. Spencer 2:1df0b61d3b5a 15
Michael J. Spencer 2:1df0b61d3b5a 16 MemoryPool* MemoryPool::first = NULL;
Michael J. Spencer 2:1df0b61d3b5a 17
Michael J. Spencer 2:1df0b61d3b5a 18 MemoryPool::MemoryPool(void* base, uint16_t size)
Michael J. Spencer 2:1df0b61d3b5a 19 {
Michael J. Spencer 2:1df0b61d3b5a 20 this->base = base;
Michael J. Spencer 2:1df0b61d3b5a 21 this->size = size;
Michael J. Spencer 2:1df0b61d3b5a 22
Michael J. Spencer 2:1df0b61d3b5a 23 ((_poolregion*) base)->used = 0;
Michael J. Spencer 2:1df0b61d3b5a 24 ((_poolregion*) base)->next = size;
Michael J. Spencer 2:1df0b61d3b5a 25
Michael J. Spencer 2:1df0b61d3b5a 26 // insert ourselves into head of LL
Michael J. Spencer 2:1df0b61d3b5a 27 next = first;
Michael J. Spencer 2:1df0b61d3b5a 28 first = this;
Michael J. Spencer 2:1df0b61d3b5a 29 }
Michael J. Spencer 2:1df0b61d3b5a 30
Michael J. Spencer 2:1df0b61d3b5a 31 MemoryPool::~MemoryPool()
Michael J. Spencer 2:1df0b61d3b5a 32 {
Michael J. Spencer 2:1df0b61d3b5a 33 MDEBUG("Pool %p destroyed: region %p (%d)\n", this, base, size);
Michael J. Spencer 2:1df0b61d3b5a 34
Michael J. Spencer 2:1df0b61d3b5a 35 // remove ourselves from the LL
Michael J. Spencer 2:1df0b61d3b5a 36 if (first == this)
Michael J. Spencer 2:1df0b61d3b5a 37 { // special case: we're first
Michael J. Spencer 2:1df0b61d3b5a 38 first = this->next;
Michael J. Spencer 2:1df0b61d3b5a 39 return;
Michael J. Spencer 2:1df0b61d3b5a 40 }
Michael J. Spencer 2:1df0b61d3b5a 41
Michael J. Spencer 2:1df0b61d3b5a 42 // otherwise search the LL for the previous pool
Michael J. Spencer 2:1df0b61d3b5a 43 MemoryPool* m = first;
Michael J. Spencer 2:1df0b61d3b5a 44 while (m)
Michael J. Spencer 2:1df0b61d3b5a 45 {
Michael J. Spencer 2:1df0b61d3b5a 46 if (m->next == this)
Michael J. Spencer 2:1df0b61d3b5a 47 {
Michael J. Spencer 2:1df0b61d3b5a 48 m->next = next;
Michael J. Spencer 2:1df0b61d3b5a 49 return;
Michael J. Spencer 2:1df0b61d3b5a 50 }
Michael J. Spencer 2:1df0b61d3b5a 51 m = m->next;
Michael J. Spencer 2:1df0b61d3b5a 52 }
Michael J. Spencer 2:1df0b61d3b5a 53 }
Michael J. Spencer 2:1df0b61d3b5a 54
Michael J. Spencer 2:1df0b61d3b5a 55 void* MemoryPool::alloc(size_t nbytes)
Michael J. Spencer 2:1df0b61d3b5a 56 {
Michael J. Spencer 2:1df0b61d3b5a 57 // nbytes = ceil(nbytes / 4) * 4
Michael J. Spencer 2:1df0b61d3b5a 58 if (nbytes & 3)
Michael J. Spencer 2:1df0b61d3b5a 59 nbytes += 4 - (nbytes & 3);
Michael J. Spencer 2:1df0b61d3b5a 60
Michael J. Spencer 2:1df0b61d3b5a 61 // start at the start
Michael J. Spencer 2:1df0b61d3b5a 62 _poolregion* p = ((_poolregion*) base);
Michael J. Spencer 2:1df0b61d3b5a 63
Michael J. Spencer 2:1df0b61d3b5a 64 // find the allocation size including our metadata
Michael J. Spencer 2:1df0b61d3b5a 65 uint16_t nsize = nbytes + sizeof(_poolregion);
Michael J. Spencer 2:1df0b61d3b5a 66
Michael J. Spencer 2:1df0b61d3b5a 67 MDEBUG("\tallocate %d bytes from %p\n", nsize, base);
Michael J. Spencer 2:1df0b61d3b5a 68
Michael J. Spencer 2:1df0b61d3b5a 69 // now we walk the list, looking for a sufficiently large free block
Michael J. Spencer 2:1df0b61d3b5a 70 do {
Michael J. Spencer 2:1df0b61d3b5a 71 MDEBUG("\t\tchecking %p (%s, %db)\n", p, (p->used?"used":"free"), p->next);
Michael J. Spencer 2:1df0b61d3b5a 72 if ((p->used == 0) && (p->next >= nsize))
Michael J. Spencer 2:1df0b61d3b5a 73 { // we found a free space that's big enough
Michael J. Spencer 2:1df0b61d3b5a 74 MDEBUG("\t\tFOUND free block at %p (%+d) with %d bytes\n", p, offset(p), p->next);
Michael J. Spencer 2:1df0b61d3b5a 75 // mark it as used
Michael J. Spencer 2:1df0b61d3b5a 76 p->used = 1;
Michael J. Spencer 2:1df0b61d3b5a 77
Michael J. Spencer 2:1df0b61d3b5a 78 // if there's free space at the end of this block
Michael J. Spencer 2:1df0b61d3b5a 79 if (p->next > nsize)
Michael J. Spencer 2:1df0b61d3b5a 80 {
Michael J. Spencer 2:1df0b61d3b5a 81 // q = p->next
Michael J. Spencer 2:1df0b61d3b5a 82 _poolregion* q = (_poolregion*) (((uint8_t*) p) + nsize);
Michael J. Spencer 2:1df0b61d3b5a 83
Michael J. Spencer 2:1df0b61d3b5a 84 MDEBUG("\t\twriting header to %p (%+d) (%d)\n", q, offset(q), p->next - nsize);
Michael J. Spencer 2:1df0b61d3b5a 85 // write a new block header into q
Michael J. Spencer 2:1df0b61d3b5a 86 q->used = 0;
Michael J. Spencer 2:1df0b61d3b5a 87 q->next = p->next - nsize;
Michael J. Spencer 2:1df0b61d3b5a 88
Michael J. Spencer 2:1df0b61d3b5a 89 // set our next to point to it
Michael J. Spencer 2:1df0b61d3b5a 90 p->next = nsize;
Michael J. Spencer 2:1df0b61d3b5a 91
Michael J. Spencer 2:1df0b61d3b5a 92 // sanity check
Michael J. Spencer 2:1df0b61d3b5a 93 if (offset(q) >= size)
Michael J. Spencer 2:1df0b61d3b5a 94 {
Michael J. Spencer 2:1df0b61d3b5a 95 // captain, we have a problem!
Michael J. Spencer 2:1df0b61d3b5a 96 // this can only happen if something has corrupted our heap, since we should simply fail to find a free block if it's full
Michael J. Spencer 2:1df0b61d3b5a 97 __debugbreak();
Michael J. Spencer 2:1df0b61d3b5a 98 }
Michael J. Spencer 2:1df0b61d3b5a 99 }
Michael J. Spencer 2:1df0b61d3b5a 100
Michael J. Spencer 2:1df0b61d3b5a 101 // then return the data region for the block
Michael J. Spencer 2:1df0b61d3b5a 102 return &p->data;
Michael J. Spencer 2:1df0b61d3b5a 103 }
Michael J. Spencer 2:1df0b61d3b5a 104
Michael J. Spencer 2:1df0b61d3b5a 105 // p = p->next
Michael J. Spencer 2:1df0b61d3b5a 106 p = (_poolregion*) (((uint8_t*) p) + p->next);
Michael J. Spencer 2:1df0b61d3b5a 107
Michael J. Spencer 2:1df0b61d3b5a 108 // make sure we don't walk off the end
Michael J. Spencer 2:1df0b61d3b5a 109 } while (p <= (_poolregion*) (((uint8_t*)base) + size));
Michael J. Spencer 2:1df0b61d3b5a 110
Michael J. Spencer 2:1df0b61d3b5a 111 // fell off the end of the region!
Michael J. Spencer 2:1df0b61d3b5a 112 return NULL;
Michael J. Spencer 2:1df0b61d3b5a 113 }
Michael J. Spencer 2:1df0b61d3b5a 114
Michael J. Spencer 2:1df0b61d3b5a 115 void MemoryPool::dealloc(void* d)
Michael J. Spencer 2:1df0b61d3b5a 116 {
Michael J. Spencer 2:1df0b61d3b5a 117 _poolregion* p = (_poolregion*) (((uint8_t*) d) - sizeof(_poolregion));
Michael J. Spencer 2:1df0b61d3b5a 118 p->used = 0;
Michael J. Spencer 2:1df0b61d3b5a 119
Michael J. Spencer 2:1df0b61d3b5a 120 MDEBUG("\tdeallocating %p (%+d, %db)\n", p, offset(p), p->next);
Michael J. Spencer 2:1df0b61d3b5a 121
Michael J. Spencer 2:1df0b61d3b5a 122 // combine next block if it's free
Michael J. Spencer 2:1df0b61d3b5a 123 _poolregion* q = (_poolregion*) (((uint8_t*) p) + p->next);
Michael J. Spencer 2:1df0b61d3b5a 124 if (q->used == 0)
Michael J. Spencer 2:1df0b61d3b5a 125 {
Michael J. Spencer 2:1df0b61d3b5a 126 MDEBUG("\t\tCombining with next free region at %p, new size is %d\n", q, p->next + q->next);
Michael J. Spencer 2:1df0b61d3b5a 127
Michael J. Spencer 2:1df0b61d3b5a 128 // sanity check
Michael J. Spencer 2:1df0b61d3b5a 129 if (offset(q) > size)
Michael J. Spencer 2:1df0b61d3b5a 130 {
Michael J. Spencer 2:1df0b61d3b5a 131 // captain, we have a problem!
Michael J. Spencer 2:1df0b61d3b5a 132 // this can only happen if something has corrupted our heap, since we should simply fail to find a free block if it's full
Michael J. Spencer 2:1df0b61d3b5a 133 __debugbreak();
Michael J. Spencer 2:1df0b61d3b5a 134 }
Michael J. Spencer 2:1df0b61d3b5a 135
Michael J. Spencer 2:1df0b61d3b5a 136 p->next += q->next;
Michael J. Spencer 2:1df0b61d3b5a 137 }
Michael J. Spencer 2:1df0b61d3b5a 138
Michael J. Spencer 2:1df0b61d3b5a 139 // walk the list to find previous block
Michael J. Spencer 2:1df0b61d3b5a 140 q = (_poolregion*) base;
Michael J. Spencer 2:1df0b61d3b5a 141 do {
Michael J. Spencer 2:1df0b61d3b5a 142 // check if q is the previous block
Michael J. Spencer 2:1df0b61d3b5a 143 if ((((uint8_t*) q) + q->next) == (uint8_t*) p) {
Michael J. Spencer 2:1df0b61d3b5a 144 // q is the previous block.
Michael J. Spencer 2:1df0b61d3b5a 145 if (q->used == 0)
Michael J. Spencer 2:1df0b61d3b5a 146 { // if q is free
Michael J. Spencer 2:1df0b61d3b5a 147 MDEBUG("\t\tCombining with previous free region at %p, new size is %d\n", q, p->next + q->next);
Michael J. Spencer 2:1df0b61d3b5a 148
Michael J. Spencer 2:1df0b61d3b5a 149 // combine!
Michael J. Spencer 2:1df0b61d3b5a 150 q->next += p->next;
Michael J. Spencer 2:1df0b61d3b5a 151
Michael J. Spencer 2:1df0b61d3b5a 152 // sanity check
Michael J. Spencer 2:1df0b61d3b5a 153 if ((offset(p) + p->next) >= size)
Michael J. Spencer 2:1df0b61d3b5a 154 {
Michael J. Spencer 2:1df0b61d3b5a 155 // captain, we have a problem!
Michael J. Spencer 2:1df0b61d3b5a 156 // this can only happen if something has corrupted our heap, since we should simply fail to find a free block if it's full
Michael J. Spencer 2:1df0b61d3b5a 157 __debugbreak();
Michael J. Spencer 2:1df0b61d3b5a 158 }
Michael J. Spencer 2:1df0b61d3b5a 159 }
Michael J. Spencer 2:1df0b61d3b5a 160
Michael J. Spencer 2:1df0b61d3b5a 161 // we found previous block, return
Michael J. Spencer 2:1df0b61d3b5a 162 return;
Michael J. Spencer 2:1df0b61d3b5a 163 }
Michael J. Spencer 2:1df0b61d3b5a 164
Michael J. Spencer 2:1df0b61d3b5a 165 // return if last block
Michael J. Spencer 2:1df0b61d3b5a 166 if (offset(q) + q->next >= size)
Michael J. Spencer 2:1df0b61d3b5a 167 return;
Michael J. Spencer 2:1df0b61d3b5a 168
Michael J. Spencer 2:1df0b61d3b5a 169 // q = q->next
Michael J. Spencer 2:1df0b61d3b5a 170 q = (_poolregion*) (((uint8_t*) q) + q->next);
Michael J. Spencer 2:1df0b61d3b5a 171
Michael J. Spencer 2:1df0b61d3b5a 172 // if some idiot deallocates our memory region while we're using it, strange things can happen.
Michael J. Spencer 2:1df0b61d3b5a 173 // avoid an infinite loop in that case, however we'll still leak memory and may corrupt things
Michael J. Spencer 2:1df0b61d3b5a 174 if (q->next == 0)
Michael J. Spencer 2:1df0b61d3b5a 175 return;
Michael J. Spencer 2:1df0b61d3b5a 176
Michael J. Spencer 2:1df0b61d3b5a 177 // make sure we don't walk off the end
Michael J. Spencer 2:1df0b61d3b5a 178 } while (q < (_poolregion*) (((uint8_t*) base) + size));
Michael J. Spencer 2:1df0b61d3b5a 179 }
Michael J. Spencer 2:1df0b61d3b5a 180
Michael J. Spencer 2:1df0b61d3b5a 181 void MemoryPool::debug(StreamOutput* str)
Michael J. Spencer 2:1df0b61d3b5a 182 {
Michael J. Spencer 2:1df0b61d3b5a 183 _poolregion* p = (_poolregion*) base;
Michael J. Spencer 2:1df0b61d3b5a 184 uint32_t tot = 0;
Michael J. Spencer 2:1df0b61d3b5a 185 uint32_t free = 0;
Michael J. Spencer 2:1df0b61d3b5a 186 str->printf("Start: %ub MemoryPool at %p\n", size, p);
Michael J. Spencer 2:1df0b61d3b5a 187 do {
Michael J. Spencer 2:1df0b61d3b5a 188 str->printf("\tChunk at %p (%+4d): %s, %lu bytes\n", p, offset(p), (p->used?"used":"free"), p->next);
Michael J. Spencer 2:1df0b61d3b5a 189 tot += p->next;
Michael J. Spencer 2:1df0b61d3b5a 190 if (p->used == 0)
Michael J. Spencer 2:1df0b61d3b5a 191 free += p->next;
Michael J. Spencer 2:1df0b61d3b5a 192 if ((offset(p) + p->next >= size) || (p->next <= sizeof(_poolregion)))
Michael J. Spencer 2:1df0b61d3b5a 193 {
Michael J. Spencer 2:1df0b61d3b5a 194 str->printf("End: total %lub, free: %lub\n", tot, free);
Michael J. Spencer 2:1df0b61d3b5a 195 return;
Michael J. Spencer 2:1df0b61d3b5a 196 }
Michael J. Spencer 2:1df0b61d3b5a 197 p = (_poolregion*) (((uint8_t*) p) + p->next);
Michael J. Spencer 2:1df0b61d3b5a 198 } while (1);
Michael J. Spencer 2:1df0b61d3b5a 199 }
Michael J. Spencer 2:1df0b61d3b5a 200
Michael J. Spencer 2:1df0b61d3b5a 201 bool MemoryPool::has(void* p)
Michael J. Spencer 2:1df0b61d3b5a 202 {
Michael J. Spencer 2:1df0b61d3b5a 203 return ((p >= base) && (p < (void*) (((uint8_t*) base) + size)));
Michael J. Spencer 2:1df0b61d3b5a 204 }
Michael J. Spencer 2:1df0b61d3b5a 205
Michael J. Spencer 2:1df0b61d3b5a 206 uint32_t MemoryPool::free()
Michael J. Spencer 2:1df0b61d3b5a 207 {
Michael J. Spencer 2:1df0b61d3b5a 208 uint32_t free = 0;
Michael J. Spencer 2:1df0b61d3b5a 209
Michael J. Spencer 2:1df0b61d3b5a 210 _poolregion* p = (_poolregion*) base;
Michael J. Spencer 2:1df0b61d3b5a 211
Michael J. Spencer 2:1df0b61d3b5a 212 do {
Michael J. Spencer 2:1df0b61d3b5a 213 if (p->used == 0)
Michael J. Spencer 2:1df0b61d3b5a 214 free += p->next;
Michael J. Spencer 2:1df0b61d3b5a 215 if (offset(p) + p->next >= size)
Michael J. Spencer 2:1df0b61d3b5a 216 return free;
Michael J. Spencer 2:1df0b61d3b5a 217 if (p->next <= sizeof(_poolregion))
Michael J. Spencer 2:1df0b61d3b5a 218 return free;
Michael J. Spencer 2:1df0b61d3b5a 219 p = (_poolregion*) (((uint8_t*) p) + p->next);
Michael J. Spencer 2:1df0b61d3b5a 220 } while (1);
Michael J. Spencer 2:1df0b61d3b5a 221 }