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