tests/libqos/malloc-pc.c

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