2 * libqos malloc support
7 * John Snow <jsnow@redhat.com>
9 * This work is licensed under the terms of the GNU GPL, version 2 or later.
10 * See the COPYING file in the top-level directory.
13 #include "libqos/malloc.h"
14 #include "qemu-common.h"
19 typedef QTAILQ_HEAD(MemList, MemBlock) MemList;
21 typedef struct MemBlock {
22 QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
27 struct QGuestAllocator {
37 #define DEFAULT_PAGE_SIZE 4096
39 static void mlist_delete(MemList *list, MemBlock *node)
41 g_assert(list && node);
42 QTAILQ_REMOVE(list, node, MLIST_ENTNAME);
46 static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
49 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
50 if (node->addr == addr) {
57 static MemBlock *mlist_find_space(MemList *head, uint64_t size)
61 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
62 if (node->size >= size) {
69 static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
72 g_assert(head && insr);
74 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
75 if (insr->addr < node->addr) {
76 QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME);
81 QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME);
85 static inline uint64_t mlist_boundary(MemBlock *node)
87 return node->size + node->addr;
90 static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right)
92 g_assert(head && left && right);
94 left->size += right->size;
95 mlist_delete(head, right);
99 static void mlist_coalesce(MemList *head, MemBlock *node)
108 left = QTAILQ_PREV(node, MemList, MLIST_ENTNAME);
109 right = QTAILQ_NEXT(node, MLIST_ENTNAME);
111 /* clowns to the left of me */
112 if (left && mlist_boundary(left) == node->addr) {
113 node = mlist_join(head, left, node);
117 /* jokers to the right */
118 if (right && mlist_boundary(node) == right->addr) {
119 node = mlist_join(head, node, right);
126 static MemBlock *mlist_new(uint64_t addr, uint64_t size)
133 block = g_malloc0(sizeof(MemBlock));
141 static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode,
148 g_assert_cmpint(freenode->size, >=, size);
150 addr = freenode->addr;
151 if (freenode->size == size) {
152 /* re-use this freenode as our used node */
153 QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
156 /* adjust the free node and create a new used node */
157 freenode->addr += size;
158 freenode->size -= size;
159 usednode = mlist_new(addr, size);
162 mlist_sort_insert(s->used, usednode);
166 /* To assert the correctness of the list.
167 * Used only if ALLOC_PARANOID is set. */
168 static void mlist_check(QGuestAllocator *s)
171 uint64_t addr = s->start > 0 ? s->start - 1 : 0;
172 uint64_t next = s->start;
174 QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
175 g_assert_cmpint(node->addr, >, addr);
176 g_assert_cmpint(node->addr, >=, next);
178 next = node->addr + node->size;
181 addr = s->start > 0 ? s->start - 1 : 0;
183 QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
184 g_assert_cmpint(node->addr, >, addr);
185 g_assert_cmpint(node->addr, >=, next);
187 next = node->addr + node->size;
191 static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
195 node = mlist_find_space(s->free, size);
197 fprintf(stderr, "Out of guest memory.\n");
198 g_assert_not_reached();
200 return mlist_fulfill(s, node, size);
203 static void mlist_free(QGuestAllocator *s, uint64_t addr)
211 node = mlist_find_key(s->used, addr);
213 fprintf(stderr, "Error: no record found for an allocation at "
214 "0x%016" PRIx64 ".\n",
216 g_assert_not_reached();
219 /* Rip it out of the used list and re-insert back into the free list. */
220 QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
221 mlist_sort_insert(s->free, node);
222 mlist_coalesce(s->free, node);
226 * Mostly for valgrind happiness, but it does offer
227 * a chokepoint for debugging guest memory leaks, too.
229 void alloc_uninit(QGuestAllocator *allocator)
235 /* Check for guest leaks, and destroy the list. */
236 QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
237 if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) {
238 fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
239 "size 0x%016" PRIx64 ".\n",
240 node->addr, node->size);
242 if (allocator->opts & (ALLOC_LEAK_ASSERT)) {
243 g_assert_not_reached();
248 /* If we have previously asserted that there are no leaks, then there
249 * should be only one node here with a specific address and size. */
250 mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID;
251 QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
252 if ((allocator->opts & mask) == mask) {
253 if ((node->addr != allocator->start) ||
254 (node->size != allocator->end - allocator->start)) {
255 fprintf(stderr, "Free list is corrupted.\n");
256 g_assert_not_reached();
263 g_free(allocator->used);
264 g_free(allocator->free);
268 uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
270 uint64_t rsize = size;
273 rsize += (allocator->page_size - 1);
274 rsize &= -allocator->page_size;
275 g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
276 g_assert_cmpint(rsize, >=, size);
278 naddr = mlist_alloc(allocator, rsize);
279 if (allocator->opts & ALLOC_PARANOID) {
280 mlist_check(allocator);
286 void guest_free(QGuestAllocator *allocator, uint64_t addr)
291 mlist_free(allocator, addr);
292 if (allocator->opts & ALLOC_PARANOID) {
293 mlist_check(allocator);
297 QGuestAllocator *alloc_init(uint64_t start, uint64_t end)
299 QGuestAllocator *s = g_malloc0(sizeof(*s));
305 s->used = g_malloc(sizeof(MemList));
306 s->free = g_malloc(sizeof(MemList));
307 QTAILQ_INIT(s->used);
308 QTAILQ_INIT(s->free);
310 node = mlist_new(s->start, s->end - s->start);
311 QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
313 s->page_size = DEFAULT_PAGE_SIZE;
318 QGuestAllocator *alloc_init_flags(QAllocOpts opts,
319 uint64_t start, uint64_t end)
321 QGuestAllocator *s = alloc_init(start, end);
326 void alloc_set_page_size(QGuestAllocator *allocator, size_t page_size)
328 /* Can't alter the page_size for an allocator in-use */
329 g_assert(QTAILQ_EMPTY(allocator->used));
331 g_assert(is_power_of_2(page_size));
332 allocator->page_size = page_size;
335 void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
337 allocator->opts |= opts;
340 void migrate_allocator(QGuestAllocator *src,
341 QGuestAllocator *dst)
343 MemBlock *node, *tmp;
344 MemList *tmpused, *tmpfree;
346 /* The general memory layout should be equivalent,
347 * though opts can differ. */
348 g_assert_cmphex(src->start, ==, dst->start);
349 g_assert_cmphex(src->end, ==, dst->end);
351 /* Destroy (silently, regardless of options) the dest-list: */
352 QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
355 QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
362 /* Inherit the lists of the source allocator: */
363 dst->used = src->used;
364 dst->free = src->free;
366 /* Source is now re-initialized, the source memory is 'invalid' now: */
369 QTAILQ_INIT(src->used);
370 QTAILQ_INIT(src->free);
371 node = mlist_new(src->start, src->end - src->start);
372 QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);