tests/qtest/libqos/libqos-malloc.c

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