tests/libqos/malloc.c

   1 /*
   2  * libqos malloc support
   3  *
   4  * Copyright (c) 2014
   5  *
   6  * Author:
   7  *  John Snow <[email protected]>
   8  *
   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.
  11  */
  12
  13 #include "qemu/osdep.h"
  14 #include "libqos/malloc.h"
  15 #include "qemu-common.h"
  16 #include "qemu/host-utils.h"
  17
  18 typedef struct MemBlock {
  19     QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
  20     uint64_t size;
  21     uint64_t addr;
  22 } MemBlock;
  23
  24 #define DEFAULT_PAGE_SIZE 4096
  25
  26 static void mlist_delete(MemList *list, MemBlock *node)
  27 {
  28     g_assert(list && node);
  29     QTAILQ_REMOVE(list, node, MLIST_ENTNAME);
  30     g_free(node);
  31 }
  32
  33 static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
  34 {
  35     MemBlock *node;
  36     QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
  37         if (node->addr == addr) {
  38             return node;
  39         }
  40     }
  41     return NULL;
  42 }
  43
  44 static MemBlock *mlist_find_space(MemList *head, uint64_t size)
  45 {
  46     MemBlock *node;
  47
  48     QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
  49         if (node->size >= size) {
  50             return node;
  51         }
  52     }
  53     return NULL;
  54 }
  55
  56 static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
  57 {
  58     MemBlock *node;
  59     g_assert(head && insr);
  60
  61     QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
  62         if (insr->addr < node->addr) {
  63             QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME);
  64             return insr;
  65         }
  66     }
  67
  68     QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME);
  69     return insr;
  70 }
  71
  72 static inline uint64_t mlist_boundary(MemBlock *node)
  73 {
  74     return node->size + node->addr;
  75 }
  76
  77 static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right)
  78 {
  79     g_assert(head && left && right);
  80
  81     left->size += right->size;
  82     mlist_delete(head, right);
  83     return left;
  84 }
  85
  86 static void mlist_coalesce(MemList *head, MemBlock *node)
  87 {
  88     g_assert(node);
  89     MemBlock *left;
  90     MemBlock *right;
  91     char merge;
  92
  93     do {
  94         merge = 0;
  95         left = QTAILQ_PREV(node, MLIST_ENTNAME);
  96         right = QTAILQ_NEXT(node, MLIST_ENTNAME);
  97
  98         /* clowns to the left of me */
  99         if (left && mlist_boundary(left) == node->addr) {
 100             node = mlist_join(head, left, node);
 101             merge = 1;
 102         }
 103
 104         /* jokers to the right */
 105         if (right && mlist_boundary(node) == right->addr) {
 106             node = mlist_join(head, node, right);
 107             merge = 1;
 108         }
 109
 110     } while (merge);
 111 }
 112
 113 static MemBlock *mlist_new(uint64_t addr, uint64_t size)
 114 {
 115     MemBlock *block;
 116
 117     if (!size) {
 118         return NULL;
 119     }
 120     block = g_new0(MemBlock, 1);
 121
 122     block->addr = addr;
 123     block->size = size;
 124
 125     return block;
 126 }
 127
 128 static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode,
 129                                                                 uint64_t size)
 130 {
 131     uint64_t addr;
 132     MemBlock *usednode;
 133
 134     g_assert(freenode);
 135     g_assert_cmpint(freenode->size, >=, size);
 136
 137     addr = freenode->addr;
 138     if (freenode->size == size) {
 139         /* re-use this freenode as our used node */
 140         QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
 141         usednode = freenode;
 142     } else {
 143         /* adjust the free node and create a new used node */
 144         freenode->addr += size;
 145         freenode->size -= size;
 146         usednode = mlist_new(addr, size);
 147     }
 148
 149     mlist_sort_insert(s->used, usednode);
 150     return addr;
 151 }
 152
 153 /* To assert the correctness of the list.
 154  * Used only if ALLOC_PARANOID is set. */
 155 static void mlist_check(QGuestAllocator *s)
 156 {
 157     MemBlock *node;
 158     uint64_t addr = s->start > 0 ? s->start - 1 : 0;
 159     uint64_t next = s->start;
 160
 161     QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
 162         g_assert_cmpint(node->addr, >, addr);
 163         g_assert_cmpint(node->addr, >=, next);
 164         addr = node->addr;
 165         next = node->addr + node->size;
 166     }
 167
 168     addr = s->start > 0 ? s->start - 1 : 0;
 169     next = s->start;
 170     QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
 171         g_assert_cmpint(node->addr, >, addr);
 172         g_assert_cmpint(node->addr, >=, next);
 173         addr = node->addr;
 174         next = node->addr + node->size;
 175     }
 176 }
 177
 178 static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
 179 {
 180     MemBlock *node;
 181
 182     node = mlist_find_space(s->free, size);
 183     if (!node) {
 184         fprintf(stderr, "Out of guest memory.\n");
 185         g_assert_not_reached();
 186     }
 187     return mlist_fulfill(s, node, size);
 188 }
 189
 190 static void mlist_free(QGuestAllocator *s, uint64_t addr)
 191 {
 192     MemBlock *node;
 193
 194     if (addr == 0) {
 195         return;
 196     }
 197
 198     node = mlist_find_key(s->used, addr);
 199     if (!node) {
 200         fprintf(stderr, "Error: no record found for an allocation at "
 201                 "0x%016" PRIx64 ".\n",
 202                 addr);
 203         g_assert_not_reached();
 204     }
 205
 206     /* Rip it out of the used list and re-insert back into the free list. */
 207     QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
 208     mlist_sort_insert(s->free, node);
 209     mlist_coalesce(s->free, node);
 210 }
 211
 212 /*
 213  * Mostly for valgrind happiness, but it does offer
 214  * a chokepoint for debugging guest memory leaks, too.
 215  */
 216 void alloc_destroy(QGuestAllocator *allocator)
 217 {
 218     MemBlock *node;
 219     MemBlock *tmp;
 220     QAllocOpts mask;
 221
 222     /* Check for guest leaks, and destroy the list. */
 223     QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
 224         if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) {
 225             fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
 226                     "size 0x%016" PRIx64 ".\n",
 227                     node->addr, node->size);
 228         }
 229         if (allocator->opts & (ALLOC_LEAK_ASSERT)) {
 230             g_assert_not_reached();
 231         }
 232         g_free(node);
 233     }
 234
 235     /* If we have previously asserted that there are no leaks, then there
 236      * should be only one node here with a specific address and size. */
 237     mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID;
 238     QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
 239         if ((allocator->opts & mask) == mask) {
 240             if ((node->addr != allocator->start) ||
 241                 (node->size != allocator->end - allocator->start)) {
 242                 fprintf(stderr, "Free list is corrupted.\n");
 243                 g_assert_not_reached();
 244             }
 245         }
 246
 247         g_free(node);
 248     }
 249
 250     g_free(allocator->used);
 251     g_free(allocator->free);
 252 }
 253
 254 uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
 255 {
 256     uint64_t rsize = size;
 257     uint64_t naddr;
 258
 259     if (!size) {
 260         return 0;
 261     }
 262
 263     rsize += (allocator->page_size - 1);
 264     rsize &= -allocator->page_size;
 265     g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
 266     g_assert_cmpint(rsize, >=, size);
 267
 268     naddr = mlist_alloc(allocator, rsize);
 269     if (allocator->opts & ALLOC_PARANOID) {
 270         mlist_check(allocator);
 271     }
 272
 273     return naddr;
 274 }
 275
 276 void guest_free(QGuestAllocator *allocator, uint64_t addr)
 277 {
 278     if (!addr) {
 279         return;
 280     }
 281     mlist_free(allocator, addr);
 282     if (allocator->opts & ALLOC_PARANOID) {
 283         mlist_check(allocator);
 284     }
 285 }
 286
 287 void alloc_init(QGuestAllocator *s, QAllocOpts opts,
 288                 uint64_t start, uint64_t end,
 289                 size_t page_size)
 290 {
 291     MemBlock *node;
 292
 293     s->opts = opts;
 294     s->start = start;
 295     s->end = end;
 296
 297     s->used = g_new(MemList, 1);
 298     s->free = g_new(MemList, 1);
 299     QTAILQ_INIT(s->used);
 300     QTAILQ_INIT(s->free);
 301
 302     node = mlist_new(s->start, s->end - s->start);
 303     QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
 304
 305     s->page_size = page_size;
 306 }
 307
 308 void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
 309 {
 310     allocator->opts |= opts;
 311 }
 312
 313 void migrate_allocator(QGuestAllocator *src,
 314                        QGuestAllocator *dst)
 315 {
 316     MemBlock *node, *tmp;
 317     MemList *tmpused, *tmpfree;
 318
 319     /* The general memory layout should be equivalent,
 320      * though opts can differ. */
 321     g_assert_cmphex(src->start, ==, dst->start);
 322     g_assert_cmphex(src->end, ==, dst->end);
 323
 324     /* Destroy (silently, regardless of options) the dest-list: */
 325     QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
 326         g_free(node);
 327     }
 328     QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
 329         g_free(node);
 330     }
 331
 332     tmpused = dst->used;
 333     tmpfree = dst->free;
 334
 335     /* Inherit the lists of the source allocator: */
 336     dst->used = src->used;
 337     dst->free = src->free;
 338
 339     /* Source is now re-initialized, the source memory is 'invalid' now: */
 340     src->used = tmpused;
 341     src->free = tmpfree;
 342     QTAILQ_INIT(src->used);
 343     QTAILQ_INIT(src->free);
 344     node = mlist_new(src->start, src->end - src->start);
 345     QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);
 346     return;
 347 }