[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 "libqos/malloc.h"
#include "qemu-common.h"
#include <stdio.h>
#include <inttypes.h>
#include <glib.h>

typedef QTAILQ_HEAD(MemList, MemBlock) MemList;

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

struct QGuestAllocator {
    QAllocOpts opts;
    uint64_t start;
    uint64_t end;
    uint32_t page_size;

    MemList *used;
    MemList *free;
};

#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, MemList, 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_malloc0(sizeof(MemBlock));

    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_uninit(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);
    g_free(allocator);
}

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

    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);
    }
}

QGuestAllocator *alloc_init(uint64_t start, uint64_t end)
{
    QGuestAllocator *s = g_malloc0(sizeof(*s));
    MemBlock *node;

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

    s->used = g_malloc(sizeof(MemList));
    s->free = g_malloc(sizeof(MemList));
    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 = DEFAULT_PAGE_SIZE;

    return s;
}

QGuestAllocator *alloc_init_flags(QAllocOpts opts,
                                  uint64_t start, uint64_t end)
{
    QGuestAllocator *s = alloc_init(start, end);
    s->opts = opts;
    return s;
}

void alloc_set_page_size(QGuestAllocator *allocator, size_t page_size)
{
    /* Can't alter the page_size for an allocator in-use */
    g_assert(QTAILQ_EMPTY(allocator->used));

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