1 #include "MemoryPool.h"
6 #define offset(x) (((uint8_t*) x) - ((uint8_t*) this->base))
8 typedef struct __attribute__ ((packed
))
16 MemoryPool
* MemoryPool::first
= NULL
;
18 MemoryPool::MemoryPool(void* base
, uint16_t size
)
23 ((_poolregion
*) base
)->used
= 0;
24 ((_poolregion
*) base
)->next
= size
;
26 // insert ourselves into head of LL
31 MemoryPool::~MemoryPool()
33 MDEBUG("Pool %p destroyed: region %p (%d)\n", this, base
, size
);
35 // remove ourselves from the LL
37 { // special case: we're first
42 // otherwise search the LL for the previous pool
43 MemoryPool
* m
= first
;
55 void* MemoryPool::alloc(size_t nbytes
)
57 // nbytes = ceil(nbytes / 4) * 4
59 nbytes
+= 4 - (nbytes
& 3);
62 _poolregion
* p
= ((_poolregion
*) base
);
64 // find the allocation size including our metadata
65 uint16_t nsize
= nbytes
+ sizeof(_poolregion
);
67 MDEBUG("\tallocate %d bytes from %p\n", nsize
, base
);
69 // now we walk the list, looking for a sufficiently large free block
71 MDEBUG("\t\tchecking %p (%s, %db)\n", p
, (p
->used
?"used":"free"), p
->next
);
72 if ((p
->used
== 0) && (p
->next
>= nsize
))
73 { // we found a free space that's big enough
74 MDEBUG("\t\tFOUND free block at %p (%+d) with %d bytes\n", p
, offset(p
), p
->next
);
78 // if there's free space at the end of this block
82 _poolregion
* q
= (_poolregion
*) (((uint8_t*) p
) + nsize
);
84 MDEBUG("\t\twriting header to %p (%+d) (%d)\n", q
, offset(q
), p
->next
- nsize
);
85 // write a new block header into q
87 q
->next
= p
->next
- nsize
;
89 // set our next to point to it
93 if (offset(q
) >= size
)
95 // captain, we have a problem!
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
101 // then return the data region for the block
106 p
= (_poolregion
*) (((uint8_t*) p
) + p
->next
);
108 // make sure we don't walk off the end
109 } while (p
<= (_poolregion
*) (((uint8_t*)base
) + size
));
111 // fell off the end of the region!
115 void MemoryPool::dealloc(void* d
)
117 _poolregion
* p
= (_poolregion
*) (((uint8_t*) d
) - sizeof(_poolregion
));
120 MDEBUG("\tdeallocating %p (%+d, %db)\n", p
, offset(p
), p
->next
);
122 // combine next block if it's free
123 _poolregion
* q
= (_poolregion
*) (((uint8_t*) p
) + p
->next
);
126 MDEBUG("\t\tCombining with next free region at %p, new size is %d\n", q
, p
->next
+ q
->next
);
129 if (offset(q
) > size
)
131 // captain, we have a problem!
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
139 // walk the list to find previous block
140 q
= (_poolregion
*) base
;
142 // check if q is the previous block
143 if ((((uint8_t*) q
) + q
->next
) == (uint8_t*) p
) {
144 // q is the previous block.
147 MDEBUG("\t\tCombining with previous free region at %p, new size is %d\n", q
, p
->next
+ q
->next
);
153 if ((offset(p
) + p
->next
) >= size
)
155 // captain, we have a problem!
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
161 // we found previous block, return
165 // return if last block
166 if (offset(q
) + q
->next
>= size
)
170 q
= (_poolregion
*) (((uint8_t*) q
) + q
->next
);
172 // if some idiot deallocates our memory region while we're using it, strange things can happen.
173 // avoid an infinite loop in that case, however we'll still leak memory and may corrupt things
177 // make sure we don't walk off the end
178 } while (q
< (_poolregion
*) (((uint8_t*) base
) + size
));
181 void MemoryPool::debug(StreamOutput
* str
)
183 _poolregion
* p
= (_poolregion
*) base
;
186 str
->printf("Start: %ub MemoryPool at %p\n", size
, p
);
188 str
->printf("\tChunk at %p (%+4d): %s, %lu bytes\n", p
, offset(p
), (p
->used
?"used":"free"), p
->next
);
192 if ((offset(p
) + p
->next
>= size
) || (p
->next
<= sizeof(_poolregion
)))
194 str
->printf("End: total %lub, free: %lub\n", tot
, free
);
197 p
= (_poolregion
*) (((uint8_t*) p
) + p
->next
);
201 bool MemoryPool::has(void* p
)
203 return ((p
>= base
) && (p
< (void*) (((uint8_t*) base
) + size
)));
206 uint32_t MemoryPool::free()
210 _poolregion
* p
= (_poolregion
*) base
;
215 if (offset(p
) + p
->next
>= size
)
217 if (p
->next
<= sizeof(_poolregion
))
219 p
= (_poolregion
*) (((uint8_t*) p
) + p
->next
);