cachepc-qemu

Fork of AMDESE/qemu with changes for cachepc side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-qemu
Log | Files | Refs | Submodules | LICENSE | sfeed.txt

malloc.c (8636B)

      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 "malloc.h"
     15#include "qemu-common.h"
     16#include "qemu/host-utils.h"
     17
     18typedef 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
     26static 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
     33static 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
     44static 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
     56static 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
     72static inline uint64_t mlist_boundary(MemBlock *node)
     73{
     74    return node->size + node->addr;
     75}
     76
     77static 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
     86static 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
    113static 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
    128static 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. */
    155static 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
    178static 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
    190static 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 */
    216void 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
    254uint64_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
    276void 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
    287void 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
    308void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
    309{
    310    allocator->opts |= opts;
    311}
    312
    313void 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}