[Qemu-devel] [PATCH 0/4] libqos: add a simple first-fit memory allocator

[Qemu-devel] [PATCH 0/4] libqos: add a simple first-fit memory allocator

[John Snow]

This set collects two patches by Marc Marí already on the mailing list,
but goes further by adding a simple memory allocator that allows us to
track and debug freed memory, and optionally keep track of any leaks.

John Snow (2):
  libqos: add a simple first-fit memory allocator
  qtest/ide-test: add pc-alloc-uninit call

Marc Marí (2):
  libqos: Correct mask to align size to PAGE_SIZE in malloc-pc
  libqos: Change free function called in malloc

 tests/ide-test.c         |   2 +
 tests/libqos/malloc-pc.c | 321 +++++++++++++++++++++++++++++++++++++++++++++--
 tests/libqos/malloc-pc.h |   9 ++
 tests/libqos/malloc.h    |   2 +-
 4 files changed, 324 insertions(+), 10 deletions(-)

-- 
1.9.3

[Qemu-devel] [PATCH 1/4] libqos: Correct mask to align size to PAGE_SIZE in malloc-pc

[John Snow]

From: Marc Marí <marc.mari.barcelo@gmail.com>

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Marc Marí <marc.mari.barcelo@gmail.com>
Signed-off-by: John Snow <jsnow@redhat.com>
---
 tests/libqos/malloc-pc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tests/libqos/malloc-pc.c b/tests/libqos/malloc-pc.c
index db1496c..2efd095 100644
--- a/tests/libqos/malloc-pc.c
+++ b/tests/libqos/malloc-pc.c
@@ -36,7 +36,7 @@ static uint64_t pc_alloc(QGuestAllocator *allocator, size_t size)
 
 
     size += (PAGE_SIZE - 1);
-    size &= PAGE_SIZE;
+    size &= -PAGE_SIZE;
 
     g_assert_cmpint((s->start + size), <=, s->end);
 
-- 
1.9.3

[Qemu-devel] [PATCH 2/4] libqos: Change free function called in malloc

[John Snow]

From: Marc Marí <marc.mari.barcelo@gmail.com>

Signed-off-by: Marc Marí <marc.mari.barcelo@gmail.com>
Signed-off-by: John Snow <jsnow@redhat.com>
---
 tests/libqos/malloc.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tests/libqos/malloc.h b/tests/libqos/malloc.h
index 46f6000..5565381 100644
--- a/tests/libqos/malloc.h
+++ b/tests/libqos/malloc.h
@@ -32,7 +32,7 @@ static inline uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
 
 static inline void guest_free(QGuestAllocator *allocator, uint64_t addr)
 {
-    allocator->alloc(allocator, addr);
+    allocator->free(allocator, addr);
 }
 
 #endif
-- 
1.9.3

[Qemu-devel] [PATCH 3/4] libqos: add a simple first-fit memory allocator

[John Snow]

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 <jsnow@redhat.com>
---
 tests/libqos/malloc-pc.c | 321 +++++++++++++++++++++++++++++++++++++++++++++--
 tests/libqos/malloc-pc.h |   9 ++
 2 files changed, 321 insertions(+), 9 deletions(-)

diff --git a/tests/libqos/malloc-pc.c b/tests/libqos/malloc-pc.c
index 2efd095..410181d 100644
--- a/tests/libqos/malloc-pc.c
+++ b/tests/libqos/malloc-pc.c
@@ -21,41 +21,336 @@
 
 #define PAGE_SIZE (4096)
 
+typedef struct mem_block {
+    struct mem_block *prev;
+    struct mem_block *next;
+    uint64_t size;
+    uint64_t addr;
+} MemBlock;
+typedef MemBlock MemList;
+
 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)
+/** Generic List Management **/
+
+static void mlist_header_init(MemBlock *header, MemBlock *head)
+{
+    header->prev = NULL;
+    header->next = head;
+    header->size = 0;
+    header->addr = 0;
+
+    if (head) {
+        head->prev = header;
+    }
+}
+
+static MemBlock *mlist_new(uint64_t addr, uint64_t size)
+{
+    MemBlock *block = g_malloc(sizeof(MemBlock));
+
+    if (!size) {
+        return NULL;
+    }
+
+    block->prev = NULL;
+    block->next = NULL;
+    block->addr = addr;
+    block->size = size;
+
+    return block;
+}
+
+static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
+{
+    MemBlock *node = head;
+    while ((node = node->next)) {
+        if (node->addr == addr) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+static MemBlock *mlist_find_space(MemList *head, uint64_t size)
+{
+    MemBlock *node = head;
+    while ((node = node->next)) {
+        if (node->size >= size) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+static MemBlock *mlist_insert(MemBlock *node, MemBlock *insr)
+{
+    g_assert_null(insr->next);
+    g_assert_null(insr->prev);
+
+    insr->next = node;
+    insr->prev = node->prev;
+
+    node->prev = insr;
+    insr->prev->next = insr;
+
+    return insr;
+}
+
+static MemBlock *mlist_append(MemBlock *node, MemBlock *insr)
+{
+    g_assert(node);
+
+    for ( ; node->next; node = node->next) {
+        /* nihil */
+    }
+
+    node->next = insr;
+    insr->next = NULL;
+    insr->prev = node;
+
+    return insr;
+}
+
+static MemBlock *mlist_unlink(MemBlock *node)
+{
+    MemBlock *left, *right;
+    g_assert(node);
+
+    left = node->prev;
+    right = node->next;
+
+    g_assert(left);
+    left->next = right;
+
+    if (right) {
+        right->prev = left;
+    }
+
+    node->prev = NULL;
+    node->next = NULL;
+
+    return node;
+}
+
+static void mlist_delete(MemBlock *node)
+{
+    g_assert(node);
+
+    mlist_unlink(node);
+    g_free(node);
+}
+
+static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
+{
+    MemBlock *node = head;
+    g_assert(head);
+    g_assert(insr);
+
+    while ((node = node->next)) {
+        if (insr->addr < node->addr) {
+            return mlist_insert(node, insr);
+        }
+    }
+
+    return mlist_append(head, insr);
+}
+
+/** Implementation-Based List Routines **/
+
+static inline uint64_t mlist_boundary(MemBlock *node)
+{
+    return node->size + node->addr;
+}
+
+static MemBlock *mlist_join(MemBlock *left, MemBlock *right)
+{
+    g_assert(left && right);
+
+    left->size += right->size;
+    mlist_delete(right);
+    return left;
+}
+
+static void mlist_coalesce(MemBlock *node)
+{
+    g_assert(node);
+    MemBlock *left;
+    MemBlock *right;
+    char merge;
+
+    do {
+        merge = 0;
+        left = node->prev;
+        right = node->next;
+
+        /* clowns to the left of me */
+        if (left && mlist_boundary(left) == node->addr) {
+            node = mlist_join(left, node);
+            merge = 1;
+        }
+
+        /* jokers to the right */
+        if (right && mlist_boundary(node) == right->addr) {
+            node = mlist_join(node, right);
+            merge = 1;
+        }
+
+    } while (merge);
+}
+
+static uint64_t pc_mlist_fulfill(PCAlloc *s, MemBlock *freenode, uint64_t size)
 {
-    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
     uint64_t addr;
+    MemBlock *usednode;
 
+    g_assert(freenode);
+    g_assert_cmpint(freenode->size, >=, size);
 
-    size += (PAGE_SIZE - 1);
-    size &= -PAGE_SIZE;
+    addr = freenode->addr;
+    freenode->addr += size;
+    freenode->size -= size;
 
-    g_assert_cmpint((s->start + size), <=, s->end);
+    if (freenode->size == 0) {
+        mlist_delete(freenode);
+    }
 
-    addr = s->start;
-    s->start += 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 = &(s->free);
+    uint64_t addr = 0;
+    uint64_t next = 0;
+
+    while ((node = node->next)) {
+        g_assert_cmpint(node->addr, >, addr);
+        g_assert_cmpint(node->addr, >=, next);
+        addr = node->addr;
+        next = node->addr + node->size;
+    }
+
+    node = &(s->used);
+    addr = 0;
+    next = 0;
+    while ((node = node->next)) {
+        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;
+
+    node = mlist_find_key(&s->used, addr);
+    if (!node) {
+        fprintf(stderr, "Error: no record found for 0x%016lx allocation\n",
+                addr);
+        g_assert_not_reached();
+    }
+
+    /* Rip it out of the used list and re-insert back into the free list. */
+    mlist_unlink(node);
+    mlist_sort_insert(&s->free, node);
+    mlist_coalesce(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;
+
+    for (node = s->used.next; node; node = tmp) {
+        if (s->opts & (PC_ALLOC_LEAK_WARN | PC_ALLOC_LEAK_ASSERT)) {
+            fprintf(stderr, "guest malloc leak @ 0x%016lx size 0x%016lx\n",
+                    node->addr, node->size);
+        }
+        if (s->opts & PC_ALLOC_LEAK_ASSERT) {
+            g_assert_not_reached();
+        }
+        tmp = node->next;
+        g_free(node);
+    }
+
+    for (node = s->free.next; node; node = tmp) {
+        tmp = node->next;
+        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();
 
+    s->opts = flags;
     s->alloc.alloc = pc_alloc;
     s->alloc.free = pc_free;
 
@@ -67,5 +362,13 @@ QGuestAllocator *pc_alloc_init(void)
     /* Respect PCI hole */
     s->end = MIN(ram_size, 0xE0000000);
 
+    mlist_header_init(&s->used, NULL);
+    mlist_header_init(&s->free, mlist_new(s->start, s->end));
+
     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] [PATCH 4/4] qtest/ide-test: add pc-alloc-uninit call

[John Snow]

Uninitialize the allocator and cleanup residual memory.

Signed-off-by: John Snow <jsnow@redhat.com>
---
 tests/ide-test.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/tests/ide-test.c b/tests/ide-test.c
index 4a0d97f..ad32328 100644
--- a/tests/ide-test.c
+++ b/tests/ide-test.c
@@ -123,6 +123,8 @@ static void ide_test_start(const char *cmdline_fmt, ...)
 
 static void ide_test_quit(void)
 {
+    pc_alloc_uninit(guest_malloc);
+    guest_malloc = NULL;
     qtest_end();
 }
 
-- 
1.9.3

Re: [Qemu-devel] [PATCH 3/4] libqos: add a simple first-fit memory allocator

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 899 bytes --]

On Tue, Jul 29, 2014 at 05:54:43PM -0400, John Snow wrote:
> diff --git a/tests/libqos/malloc-pc.c b/tests/libqos/malloc-pc.c
> index 2efd095..410181d 100644
> --- a/tests/libqos/malloc-pc.c
> +++ b/tests/libqos/malloc-pc.c
> @@ -21,41 +21,336 @@
>  
>  #define PAGE_SIZE (4096)
>  
> +typedef struct mem_block {

QEMU generally uses CamelCase for struct tags too.  The name can be the
same as the typedef (MemBlock).

> +    struct mem_block *prev;
> +    struct mem_block *next;

Please see include/qemu/queue.h for variants of linked lists.  QTAILQ
should work, then you can drop your custom doubly-linked list code.

> +            fprintf(stderr, "guest malloc leak @ 0x%016lx size 0x%016lx\n",
> +                    node->addr, node->size);

On 32-bit hosts %lx is 32-bit but addr is uint64_t.  Please use the
PRIx64 macro here and for other instances in this patch.

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

[Qemu-devel] [PATCH 2/4] libqos: Change free function called in malloc

[John Snow]

From: Marc Marí <marc.mari.barcelo@gmail.com>

Signed-off-by: Marc Marí <marc.mari.barcelo@gmail.com>
Signed-off-by: John Snow <jsnow@redhat.com>
---
 tests/libqos/malloc.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tests/libqos/malloc.h b/tests/libqos/malloc.h
index 46f6000..5565381 100644
--- a/tests/libqos/malloc.h
+++ b/tests/libqos/malloc.h
@@ -32,7 +32,7 @@ static inline uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
 
 static inline void guest_free(QGuestAllocator *allocator, uint64_t addr)
 {
-    allocator->alloc(allocator, addr);
+    allocator->free(allocator, addr);
 }
 
 #endif
-- 
1.9.3