[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PULL 20/26] libqos: add a simple first-fit memory allocato
From: |
Stefan Hajnoczi |
Subject: |
[Qemu-devel] [PULL 20/26] libqos: add a simple first-fit memory allocator |
Date: |
Fri, 5 Sep 2014 17:13:48 +0100 |
From: John Snow <address@hidden>
Implement a simple first-fit memory allocator that
attempts to keep track of leased blocks of memory
in order to be able to re-use blocks.
Additionally, allow the user to specify when
initializing the device that upon cleanup,
we would like to assert that there are no
blocks in use. This may be useful for identifying
problems in qtests that use more complicated
set-up and tear-down routines.
This functionality is used in my upcoming ahci-test v2
patch set, but I didn't see fit to enable it for any
existing tests, which will continue to operate the
same as they have prior.
Signed-off-by: John Snow <address@hidden>
Signed-off-by: Stefan Hajnoczi <address@hidden>
---
tests/libqos/malloc-pc.c | 280 +++++++++++++++++++++++++++++++++++++++++++++--
tests/libqos/malloc-pc.h | 9 ++
2 files changed, 279 insertions(+), 10 deletions(-)
diff --git a/tests/libqos/malloc-pc.c b/tests/libqos/malloc-pc.c
index be1d97f..f4218c6 100644
--- a/tests/libqos/malloc-pc.c
+++ b/tests/libqos/malloc-pc.c
@@ -17,45 +17,294 @@
#include "hw/nvram/fw_cfg.h"
#include "qemu-common.h"
+#include "qemu/queue.h"
#include <glib.h>
#define PAGE_SIZE (4096)
+#define MLIST_ENTNAME entries
+typedef QTAILQ_HEAD(MemList, MemBlock) MemList;
+typedef struct MemBlock {
+ QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
+ uint64_t size;
+ uint64_t addr;
+} MemBlock;
+
typedef struct PCAlloc
{
QGuestAllocator alloc;
-
+ PCAllocOpts opts;
uint64_t start;
uint64_t end;
+
+ MemList used;
+ MemList free;
} PCAlloc;
-static uint64_t pc_alloc(QGuestAllocator *allocator, size_t size)
+static MemBlock *mlist_new(uint64_t addr, uint64_t size)
{
- PCAlloc *s = container_of(allocator, PCAlloc, alloc);
- uint64_t addr;
+ MemBlock *block;
+
+ if (!size) {
+ return NULL;
+ }
+ block = g_malloc0(sizeof(MemBlock));
+ block->addr = addr;
+ block->size = size;
- size += (PAGE_SIZE - 1);
- size &= -PAGE_SIZE;
+ return block;
+}
+
+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 uint64_t pc_mlist_fulfill(PCAlloc *s, MemBlock *freenode, uint64_t size)
+{
+ uint64_t addr;
+ MemBlock *usednode;
- g_assert_cmpint((s->start + size), <=, s->end);
+ g_assert(freenode);
+ g_assert_cmpint(freenode->size, >=, size);
- addr = s->start;
- s->start += 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 PC_ALLOC_PARANOID is set. */
+static void pc_mlist_check(PCAlloc *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 pc_mlist_alloc(PCAlloc *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 pc_mlist_fulfill(s, node, size);
+}
+
+static void pc_mlist_free(PCAlloc *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);
+}
+
+static uint64_t pc_alloc(QGuestAllocator *allocator, size_t size)
+{
+ PCAlloc *s = container_of(allocator, PCAlloc, alloc);
+ uint64_t rsize = size;
+ uint64_t naddr;
+
+ rsize += (PAGE_SIZE - 1);
+ rsize &= -PAGE_SIZE;
+ g_assert_cmpint((s->start + rsize), <=, s->end);
+ g_assert_cmpint(rsize, >=, size);
+
+ naddr = pc_mlist_alloc(s, rsize);
+ if (s->opts & PC_ALLOC_PARANOID) {
+ pc_mlist_check(s);
+ }
+
+ return naddr;
+}
+
static void pc_free(QGuestAllocator *allocator, uint64_t addr)
{
+ PCAlloc *s = container_of(allocator, PCAlloc, alloc);
+
+ pc_mlist_free(s, addr);
+ if (s->opts & PC_ALLOC_PARANOID) {
+ pc_mlist_check(s);
+ }
+}
+
+/*
+ * Mostly for valgrind happiness, but it does offer
+ * a chokepoint for debugging guest memory leaks, too.
+ */
+void pc_alloc_uninit(QGuestAllocator *allocator)
+{
+ PCAlloc *s = container_of(allocator, PCAlloc, alloc);
+ MemBlock *node;
+ MemBlock *tmp;
+ PCAllocOpts mask;
+
+ /* Check for guest leaks, and destroy the list. */
+ QTAILQ_FOREACH_SAFE(node, &s->used, MLIST_ENTNAME, tmp) {
+ if (s->opts & (PC_ALLOC_LEAK_WARN | PC_ALLOC_LEAK_ASSERT)) {
+ fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
+ "size 0x%016" PRIx64 ".\n",
+ node->addr, node->size);
+ }
+ if (s->opts & (PC_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 = PC_ALLOC_LEAK_ASSERT | PC_ALLOC_PARANOID;
+ QTAILQ_FOREACH_SAFE(node, &s->free, MLIST_ENTNAME, tmp) {
+ if ((s->opts & mask) == mask) {
+ if ((node->addr != s->start) ||
+ (node->size != s->end - s->start)) {
+ fprintf(stderr, "Free list is corrupted.\n");
+ g_assert_not_reached();
+ }
+ }
+
+ g_free(node);
+ }
+
+ g_free(s);
}
-QGuestAllocator *pc_alloc_init(void)
+QGuestAllocator *pc_alloc_init_flags(PCAllocOpts flags)
{
PCAlloc *s = g_malloc0(sizeof(*s));
uint64_t ram_size;
QFWCFG *fw_cfg = pc_fw_cfg_init();
+ MemBlock *node;
+ s->opts = flags;
s->alloc.alloc = pc_alloc;
s->alloc.free = pc_free;
@@ -70,5 +319,16 @@ QGuestAllocator *pc_alloc_init(void)
/* clean-up */
g_free(fw_cfg);
+ 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);
+
return &s->alloc;
}
+
+inline QGuestAllocator *pc_alloc_init(void)
+{
+ return pc_alloc_init_flags(PC_ALLOC_NO_FLAGS);
+}
diff --git a/tests/libqos/malloc-pc.h b/tests/libqos/malloc-pc.h
index ff964ab..9f525e3 100644
--- a/tests/libqos/malloc-pc.h
+++ b/tests/libqos/malloc-pc.h
@@ -15,6 +15,15 @@
#include "libqos/malloc.h"
+typedef enum {
+ PC_ALLOC_NO_FLAGS = 0x00,
+ PC_ALLOC_LEAK_WARN = 0x01,
+ PC_ALLOC_LEAK_ASSERT = 0x02,
+ PC_ALLOC_PARANOID = 0x04
+} PCAllocOpts;
+
QGuestAllocator *pc_alloc_init(void);
+QGuestAllocator *pc_alloc_init_flags(PCAllocOpts flags);
+void pc_alloc_uninit(QGuestAllocator *allocator);
#endif
--
1.9.3
- [Qemu-devel] [PULL 10/26] libqos: Added test case for configuration changes in virtio-blk test, (continued)
- [Qemu-devel] [PULL 10/26] libqos: Added test case for configuration changes in virtio-blk test, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 11/26] libqos: Added MSI-X support, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 12/26] libqos: Added EVENT_IDX support, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 13/26] qemu-img: clarify src_cache option documentation, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 14/26] qemu-img: fix rebase src_cache option documentation, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 15/26] block/archipelago: Use QEMU atomic builtins, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 16/26] rename parse_enum_option to qapi_enum_parse and make it public, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 19/26] MAINTAINERS: update sheepdog maintainer, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 17/26] qemu-nbd: add option to set detect-zeroes mode, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 18/26] qemu-nbd: fix indentation and coding style, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 20/26] libqos: add a simple first-fit memory allocator,
Stefan Hajnoczi <=
- [Qemu-devel] [PULL 22/26] ide: Add wwn support to IDE-ATAPI drive, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 23/26] vmdk: fix vmdk_parse_extents() extent_file leaks, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 24/26] vmdk: fix buf leak in vmdk_parse_extents(), Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 25/26] IDE: Fill the IDENTIFY request consistently, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 26/26] ide: Add resize callback to ide/core, Stefan Hajnoczi, 2014/09/05
- [Qemu-devel] [PULL 21/26] qtest/ide: Uninitialize PC allocator, Stefan Hajnoczi, 2014/09/05
- Re: [Qemu-devel] [PULL 00/26] Block patches, Peter Maydell, 2014/09/05