[qemu.git] / tests / libqos / malloc.c

/*
 * libqos malloc support
 *
 * Copyright (c) 2014
 *
 * Author:
 *  John Snow <[email protected]>
 *
 * This work is licensed under the terms of the GNU GPL, version 2 or later.
 * See the COPYING file in the top-level directory.
 */

#include "qemu/osdep.h"
#include "libqos/malloc.h"
#include "qemu-common.h"
#include "qemu/host-utils.h"

typedef struct MemBlock {
    QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
    uint64_t size;
    uint64_t addr;
} MemBlock;

#define DEFAULT_PAGE_SIZE 4096

static void mlist_delete(MemList *list, MemBlock *node)
{
    g_assert(list && node);
    QTAILQ_REMOVE(list, node, MLIST_ENTNAME);
    g_free(node);
}

static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
{
    MemBlock *node;
    QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
        if (node->addr == addr) {
            return node;
        }
    }
    return NULL;
}

static MemBlock *mlist_find_space(MemList *head, uint64_t size)
{
    MemBlock *node;

    QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
        if (node->size >= size) {
            return node;
        }
    }
    return NULL;
}

static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
{
    MemBlock *node;
    g_assert(head && insr);

    QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
        if (insr->addr < node->addr) {
            QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME);
            return insr;
        }
    }

    QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME);
    return insr;
}

static inline uint64_t mlist_boundary(MemBlock *node)
{
    return node->size + node->addr;
}

static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right)
{
    g_assert(head && left && right);

    left->size += right->size;
    mlist_delete(head, right);
    return left;
}

static void mlist_coalesce(MemList *head, MemBlock *node)
{
    g_assert(node);
    MemBlock *left;
    MemBlock *right;
    char merge;

    do {
        merge = 0;
        left = QTAILQ_PREV(node, MLIST_ENTNAME);
        right = QTAILQ_NEXT(node, MLIST_ENTNAME);

        /* clowns to the left of me */
        if (left && mlist_boundary(left) == node->addr) {
            node = mlist_join(head, left, node);
            merge = 1;
        }

        /* jokers to the right */
        if (right && mlist_boundary(node) == right->addr) {
            node = mlist_join(head, node, right);
            merge = 1;
        }

    } while (merge);
}

static MemBlock *mlist_new(uint64_t addr, uint64_t size)
{
    MemBlock *block;

    if (!size) {
        return NULL;
    }
    block = g_new0(MemBlock, 1);

    block->addr = addr;
    block->size = size;

    return block;
}

static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode,
                                                                uint64_t size)
{
    uint64_t addr;
    MemBlock *usednode;

    g_assert(freenode);
    g_assert_cmpint(freenode->size, >=, size);

    addr = freenode->addr;
    if (freenode->size == size) {
        /* re-use this freenode as our used node */
        QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
        usednode = freenode;
    } else {
        /* adjust the free node and create a new used node */
        freenode->addr += size;
        freenode->size -= size;
        usednode = mlist_new(addr, size);
    }

    mlist_sort_insert(s->used, usednode);
    return addr;
}

/* To assert the correctness of the list.
 * Used only if ALLOC_PARANOID is set. */
static void mlist_check(QGuestAllocator *s)
{
    MemBlock *node;
    uint64_t addr = s->start > 0 ? s->start - 1 : 0;
    uint64_t next = s->start;

    QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
        g_assert_cmpint(node->addr, >, addr);
        g_assert_cmpint(node->addr, >=, next);
        addr = node->addr;
        next = node->addr + node->size;
    }

    addr = s->start > 0 ? s->start - 1 : 0;
    next = s->start;
    QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
        g_assert_cmpint(node->addr, >, addr);
        g_assert_cmpint(node->addr, >=, next);
        addr = node->addr;
        next = node->addr + node->size;
    }
}

static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
{
    MemBlock *node;

    node = mlist_find_space(s->free, size);
    if (!node) {
        fprintf(stderr, "Out of guest memory.\n");
        g_assert_not_reached();
    }
    return mlist_fulfill(s, node, size);
}

static void mlist_free(QGuestAllocator *s, uint64_t addr)
{
    MemBlock *node;

    if (addr == 0) {
        return;
    }

    node = mlist_find_key(s->used, addr);
    if (!node) {
        fprintf(stderr, "Error: no record found for an allocation at "
                "0x%016" PRIx64 ".\n",
                addr);
        g_assert_not_reached();
    }

    /* Rip it out of the used list and re-insert back into the free list. */
    QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
    mlist_sort_insert(s->free, node);
    mlist_coalesce(s->free, node);
}

/*
 * Mostly for valgrind happiness, but it does offer
 * a chokepoint for debugging guest memory leaks, too.
 */
void alloc_destroy(QGuestAllocator *allocator)
{
    MemBlock *node;
    MemBlock *tmp;
    QAllocOpts mask;

    /* Check for guest leaks, and destroy the list. */
    QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
        if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) {
            fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
                    "size 0x%016" PRIx64 ".\n",
                    node->addr, node->size);
        }
        if (allocator->opts & (ALLOC_LEAK_ASSERT)) {
            g_assert_not_reached();
        }
        g_free(node);
    }

    /* If we have previously asserted that there are no leaks, then there
     * should be only one node here with a specific address and size. */
    mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID;
    QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
        if ((allocator->opts & mask) == mask) {
            if ((node->addr != allocator->start) ||
                (node->size != allocator->end - allocator->start)) {
                fprintf(stderr, "Free list is corrupted.\n");
                g_assert_not_reached();
            }
        }

        g_free(node);
    }

    g_free(allocator->used);
    g_free(allocator->free);
}

uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
{
    uint64_t rsize = size;
    uint64_t naddr;

    if (!size) {
        return 0;
    }

    rsize += (allocator->page_size - 1);
    rsize &= -allocator->page_size;
    g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
    g_assert_cmpint(rsize, >=, size);

    naddr = mlist_alloc(allocator, rsize);
    if (allocator->opts & ALLOC_PARANOID) {
        mlist_check(allocator);
    }

    return naddr;
}

void guest_free(QGuestAllocator *allocator, uint64_t addr)
{
    if (!addr) {
        return;
    }
    mlist_free(allocator, addr);
    if (allocator->opts & ALLOC_PARANOID) {
        mlist_check(allocator);
    }
}

void alloc_init(QGuestAllocator *s, QAllocOpts opts,
                uint64_t start, uint64_t end,
                size_t page_size)
{
    MemBlock *node;

    s->opts = opts;
    s->start = start;
    s->end = end;

    s->used = g_new(MemList, 1);
    s->free = g_new(MemList, 1);
    QTAILQ_INIT(s->used);
    QTAILQ_INIT(s->free);

    node = mlist_new(s->start, s->end - s->start);
    QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);

    s->page_size = page_size;
}

void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
{
    allocator->opts |= opts;
}

void migrate_allocator(QGuestAllocator *src,
                       QGuestAllocator *dst)
{
    MemBlock *node, *tmp;
    MemList *tmpused, *tmpfree;

    /* The general memory layout should be equivalent,
     * though opts can differ. */
    g_assert_cmphex(src->start, ==, dst->start);
    g_assert_cmphex(src->end, ==, dst->end);

    /* Destroy (silently, regardless of options) the dest-list: */
    QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
        g_free(node);
    }
    QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
        g_free(node);
    }

    tmpused = dst->used;
    tmpfree = dst->free;

    /* Inherit the lists of the source allocator: */
    dst->used = src->used;
    dst->free = src->free;

    /* Source is now re-initialized, the source memory is 'invalid' now: */
    src->used = tmpused;
    src->free = tmpfree;
    QTAILQ_INIT(src->used);
    QTAILQ_INIT(src->free);
    node = mlist_new(src->start, src->end - src->start);
    QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);
    return;
}
Commit	Line	Data
292be092 MM	1	/*
	2	* libqos malloc support
	3	*
	4	* Copyright (c) 2014
	5	*
	6	* Author:
	7	* John Snow <[email protected]>
	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
681c28a3	13	#include "qemu/osdep.h"
292be092 MM	14	#include "libqos/malloc.h"
292be092 MM	15	#include "qemu-common.h"
87776ab7	16	#include "qemu/host-utils.h"
292be092	17
f6f363c1 JS	18	typedef struct MemBlock {
	19	QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
	20	uint64_t size;
	21	uint64_t addr;
	22	} MemBlock;
	23
f6f363c1 JS	24	#define DEFAULT_PAGE_SIZE 4096
f6f363c1 JS	25
292be092 MM	26	static 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
	33	static 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
	44	static 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
	56	static 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
	72	static inline uint64_t mlist_boundary(MemBlock *node)
	73	{
	74	return node->size + node->addr;
	75	}
	76
	77	static 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
	86	static 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;
eae3eb3e	95	left = QTAILQ_PREV(node, MLIST_ENTNAME);
292be092 MM	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
f6f363c1 JS	113	static MemBlock *mlist_new(uint64_t addr, uint64_t size)
	114	{
	115	MemBlock *block;
	116
	117	if (!size) {
	118	return NULL;
	119	}
790bbb97	120	block = g_new0(MemBlock, 1);
f6f363c1 JS	121
	122	block->addr = addr;
	123	block->size = size;
	124
	125	return block;
	126	}
	127
292be092 MM	128	static 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 */
085248ae	140	QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
292be092 MM	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
085248ae	149	mlist_sort_insert(s->used, usednode);
292be092 MM	150	return addr;
	151	}
	152
	153	/* To assert the correctness of the list.
	154	* Used only if ALLOC_PARANOID is set. */
	155	static 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
085248ae	161	QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
292be092 MM	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;
085248ae	170	QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
292be092 MM	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
	178	static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
	179	{
	180	MemBlock *node;
	181
085248ae	182	node = mlist_find_space(s->free, size);
292be092 MM	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
	190	static void mlist_free(QGuestAllocator *s, uint64_t addr)
	191	{
	192	MemBlock *node;
	193
	194	if (addr == 0) {
	195	return;
	196	}
	197
085248ae	198	node = mlist_find_key(s->used, addr);
292be092 MM	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. */
085248ae JS	207	QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
	208	mlist_sort_insert(s->free, node);
	209	mlist_coalesce(s->free, node);
292be092 MM	210	}
292be092 MM	211
292be092 MM	212	/*
	213	* Mostly for valgrind happiness, but it does offer
	214	* a chokepoint for debugging guest memory leaks, too.
	215	*/
eb5937ba	216	void alloc_destroy(QGuestAllocator *allocator)
292be092 MM	217	{
	218	MemBlock *node;
	219	MemBlock *tmp;
	220	QAllocOpts mask;
	221
	222	/* Check for guest leaks, and destroy the list. */
085248ae	223	QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
292be092 MM	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;
085248ae	238	QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
292be092 MM	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
085248ae JS	250	g_free(allocator->used);
085248ae JS	251	g_free(allocator->free);
292be092 MM	252	}
	253
	254	uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
	255	{
	256	uint64_t rsize = size;
	257	uint64_t naddr;
	258
b1b66c3b JS	259	if (!size) {
	260	return 0;
	261	}
	262
292be092 MM	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
	276	void guest_free(QGuestAllocator *allocator, uint64_t addr)
	277	{
28452758 FZ	278	if (!addr) {
	279	return;
	280	}
292be092 MM	281	mlist_free(allocator, addr);
	282	if (allocator->opts & ALLOC_PARANOID) {
	283	mlist_check(allocator);
	284	}
	285	}
af77f2cd	286
eb5937ba PB	287	void alloc_init(QGuestAllocator *s, QAllocOpts opts,
	288	uint64_t start, uint64_t end,
	289	size_t page_size)
af77f2cd	290	{
af77f2cd JS	291	MemBlock *node;
af77f2cd JS	292
eb5937ba	293	s->opts = opts;
af77f2cd JS	294	s->start = start;
	295	s->end = end;
	296
790bbb97 MAL	297	s->used = g_new(MemList, 1);
790bbb97 MAL	298	s->free = g_new(MemList, 1);
085248ae JS	299	QTAILQ_INIT(s->used);
085248ae JS	300	QTAILQ_INIT(s->free);
af77f2cd JS	301
af77f2cd JS	302	node = mlist_new(s->start, s->end - s->start);
085248ae	303	QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
af77f2cd	304
eb5937ba	305	s->page_size = page_size;
f6f363c1	306	}
259342d3 JS	307
	308	void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
	309	{
	310	allocator->opts \|= opts;
	311	}
085248ae JS	312
	313	void 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	}