qemu

FORK: QEMU emulator
git clone https://git.neptards.moe/neptards/qemu.git
Log | Files | Refs | Submodules | LICENSE

libqos-malloc.c (8618B)

      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 }