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

[Qemu-devel] [PATCH v2 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.


v2: use QTAILQ as a basis for the linked list implementation instead.
    Correct an error in the size of the initial node.


John Snow (2):
  libqos: add a simple first-fit memory allocator
  qtest/ide: Uninitialize PC allocator

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 | 296 +++++++++++++++++++++++++++++++++++++++++++++--
 tests/libqos/malloc-pc.h |   9 ++
 tests/libqos/malloc.h    |   2 +-
 4 files changed, 298 insertions(+), 11 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 | 296 +++++++++++++++++++++++++++++++++++++++++++++--
 tests/libqos/malloc-pc.h |   9 ++
 2 files changed, 295 insertions(+), 10 deletions(-)

diff --git a/tests/libqos/malloc-pc.c b/tests/libqos/malloc-pc.c
index 2efd095..641162d 100644
--- a/tests/libqos/malloc-pc.c
+++ b/tests/libqos/malloc-pc.c
@@ -17,45 +17,312 @@
 #include "hw/nvram/fw_cfg.h"
 
 #include "qemu-common.h"
+#include "qemu/queue.h"
 #include <glib.h>
 
 #define PAGE_SIZE (4096)
+#define bitany(X, MASK) ((X) & (MASK))
+#define bitset(X, MASK) (bitany((X), (MASK)) == (MASK))
+
+#define MLIST_ENTNAME entries
+#define MLIST_FOREACH(node, head) QTAILQ_FOREACH((node), (head), MLIST_ENTNAME)
+#define MLIST_PREV(node) QTAILQ_PREV((node), MemList, MLIST_ENTNAME);
+#define MLIST_NEXT(node) QTAILQ_NEXT((node), MLIST_ENTNAME);
+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 inline void mlist_insert(MemList *head, MemBlock *insr)
 {
-    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
-    uint64_t addr;
+    QTAILQ_INSERT_HEAD(head, insr, MLIST_ENTNAME);
+}
+
+static inline void mlist_append(MemList *head, MemBlock *node)
+{
+    QTAILQ_INSERT_TAIL(head, node, MLIST_ENTNAME);
+}
+
+static inline void mlist_unlink(MemList *head, MemBlock *rem)
+{
+    QTAILQ_REMOVE(head, rem, MLIST_ENTNAME);
+}
+
+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 void mlist_delete(MemList *list, MemBlock *node)
+{
+    g_assert(list && node);
+    mlist_unlink(list, node);
+    g_free(node);
+}
+
+static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
+{
+    MemBlock *node;
+    MLIST_FOREACH(node, head) {
+        if (node->addr == addr) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+static MemBlock *mlist_find_space(MemList *head, uint64_t size)
+{
+    MemBlock *node;
+    MLIST_FOREACH(node, head) {
+        if (node->size >= size) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
+{
+    MemBlock *node;
+    g_assert(head && insr);
+
+    MLIST_FOREACH(node, head) {
+        if (insr->addr < node->addr) {
+            QTAILQ_INSERT_BEFORE(node, insr, entries);
+            return insr;
+        }
+    }
+
+    mlist_append(head, insr);
+    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 = MLIST_PREV(node);
+        right = MLIST_NEXT(node);
 
+        /* clowns to the left of me */
+        if (left && mlist_boundary(left) == node->addr) {
+            node = mlist_join(head, left, node);
+            merge = 1;
+        }
 
-    size += (PAGE_SIZE - 1);
-    size &= -PAGE_SIZE;
+        /* jokers to the right */
+        if (right && mlist_boundary(node) == right->addr) {
+            node = mlist_join(head, node, right);
+            merge = 1;
+        }
 
-    g_assert_cmpint((s->start + size), <=, s->end);
+    } while (merge);
+}
+
+static uint64_t pc_mlist_fulfill(PCAlloc *s, MemBlock *freenode, uint64_t size)
+{
+    uint64_t addr;
+    MemBlock *usednode;
+
+    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 */
+        mlist_unlink(&s->free, freenode);
+        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;
+
+    MLIST_FOREACH(node, &s->free) {
+        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;
+    MLIST_FOREACH(node, &s->used) {
+        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. */
+    mlist_unlink(&s->used, node);
+    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;
+
+    /* Check for guest leaks, and destroy the list. */
+    QTAILQ_FOREACH_SAFE(node, &s->used, entries, 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 there are no leaks, there should be only one node
+     * here with a specific address and size. */
+    QTAILQ_FOREACH_SAFE(node, &s->free, entries, tmp) {
+        if (bitset(s->opts, PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT)) {
+            if ((node->addr != s->start) ||
+                (node->size != s->end - s->start)) {
+                fprintf(stderr, "Free list is corrupted.\n");
+                if (bitset(s->opts, PC_ALLOC_LEAK_ASSERT)) {
+                    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();
 
+    s->opts = flags;
     s->alloc.alloc = pc_alloc;
     s->alloc.free = pc_free;
 
@@ -67,5 +334,14 @@ QGuestAllocator *pc_alloc_init(void)
     /* Respect PCI hole */
     s->end = MIN(ram_size, 0xE0000000);
 
+    QTAILQ_INIT(&s->used);
+    QTAILQ_INIT(&s->free);
+    mlist_insert(&s->free, mlist_new(s->start, s->end - s->start));
+
     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: Uninitialize PC allocator

[John Snow]

Use the new call to pc_alloc_uninit
as a test for the new pathways.

The leak checking / assert pathways are
not enabled in this patch, leaving this
as an option to future test writers.

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: 3197 bytes --]

On Wed, Jul 30, 2014 at 06:28:28PM -0400, John Snow wrote:
> +#define bitany(X, MASK) ((X) & (MASK))
> +#define bitset(X, MASK) (bitany((X), (MASK)) == (MASK))

This is subjective but macros like this should be avoided.  This macro does not
encapsulate anything substantial.  It forces the reader to jump to the
definition of this macro to understand the code, making code harder to read.

IMO a cleaner solution is to drop the macros:

  PCAllocOpts mask = PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT;
  if (s->opts & mask == mask) {                                 (1)
      if ((node->addr != s->start) ||
          (node->size != s->end - s->start)) {
          fprintf(stderr, "Free list is corrupted.\n");
          if (s->opts & PC_ALLOC_LEAK_ASSERT) {                 (2)
              g_assert_not_reached();
          }
      }
  }

Now that I read the expanded code, a bug becomes exposed:

In (1) we check that PC_ALLOC_PARANOID and PC_ALLOC_LEAK_ASSERT are both set.
Then in (2) we check whether PC_ALLOC_LEAK_ASSERT is set.  But we already knew
that PC_ALLOC_LEAK_ASSERT must be set in (1), so I guess the logic should have
really been:

  if (s->opts & (PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT)) {
      if ((node->addr != s->start) ||
          (node->size != s->end - s->start)) {
          fprintf(stderr, "Free list is corrupted.\n");
          if (s->opts & PC_ALLOC_LEAK_ASSERT) {
              g_assert_not_reached();
          }
      }
  }

> +#define MLIST_ENTNAME entries
> +#define MLIST_FOREACH(node, head) QTAILQ_FOREACH((node), (head), MLIST_ENTNAME)
> +#define MLIST_PREV(node) QTAILQ_PREV((node), MemList, MLIST_ENTNAME);
> +#define MLIST_NEXT(node) QTAILQ_NEXT((node), MLIST_ENTNAME);

For the same reasons as my previous comment, please don't hide straightforward
expressions behind a macro.

> +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 inline void mlist_insert(MemList *head, MemBlock *insr)
>  {
> -    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
> -    uint64_t addr;
> +    QTAILQ_INSERT_HEAD(head, insr, MLIST_ENTNAME);
> +}
> +
> +static inline void mlist_append(MemList *head, MemBlock *node)
> +{
> +    QTAILQ_INSERT_TAIL(head, node, MLIST_ENTNAME);
> +}
> +
> +static inline void mlist_unlink(MemList *head, MemBlock *rem)
> +{
> +    QTAILQ_REMOVE(head, rem, MLIST_ENTNAME);
> +}

For the same reasons as my comments about the macros, these trivial functions
are boilerplate.  Why not use the QTAILQ macros directly?

(It would be good to hide the list implementation if this was an external API
and you want to avoid exposing the implementation details, but within this
source file there is no point in extra layers of indirection.)

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

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

[Stefan Hajnoczi]

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

On Wed, Jul 30, 2014 at 06:28:25PM -0400, John Snow wrote:
> 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.
> 
> 
> v2: use QTAILQ as a basis for the linked list implementation instead.
>     Correct an error in the size of the initial node.
> 
> 
> John Snow (2):
>   libqos: add a simple first-fit memory allocator
>   qtest/ide: Uninitialize PC allocator
> 
> 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 | 296 +++++++++++++++++++++++++++++++++++++++++++++--
>  tests/libqos/malloc-pc.h |   9 ++
>  tests/libqos/malloc.h    |   2 +-
>  4 files changed, 298 insertions(+), 11 deletions(-)

Looking pretty close, please CC Andreas Färber <afaerber@suse.de>.

Stefan

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

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

[John Snow]

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


On 07/31/2014 06:13 AM, Stefan Hajnoczi wrote:
> On Wed, Jul 30, 2014 at 06:28:28PM -0400, John Snow wrote:
>> +#define bitany(X, MASK) ((X) & (MASK))
>> +#define bitset(X, MASK) (bitany((X), (MASK)) == (MASK))
> This is subjective but macros like this should be avoided.  This macro does not
> encapsulate anything substantial.  It forces the reader to jump to the
> definition of this macro to understand the code, making code harder to read.
>
> IMO a cleaner solution is to drop the macros:
>
>    PCAllocOpts mask = PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT;
>    if (s->opts & mask == mask) {                                 (1)
>        if ((node->addr != s->start) ||
>            (node->size != s->end - s->start)) {
>            fprintf(stderr, "Free list is corrupted.\n");
>            if (s->opts & PC_ALLOC_LEAK_ASSERT) {                 (2)
>                g_assert_not_reached();
>            }
>        }
>    }
>
> Now that I read the expanded code, a bug becomes exposed:
>
> In (1) we check that PC_ALLOC_PARANOID and PC_ALLOC_LEAK_ASSERT are both set.
> Then in (2) we check whether PC_ALLOC_LEAK_ASSERT is set.  But we already knew
> that PC_ALLOC_LEAK_ASSERT must be set in (1), so I guess the logic should have
> really been:
>
>    if (s->opts & (PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT)) {
>        if ((node->addr != s->start) ||
>            (node->size != s->end - s->start)) {
>            fprintf(stderr, "Free list is corrupted.\n");
>            if (s->opts & PC_ALLOC_LEAK_ASSERT) {
>                g_assert_not_reached();
>            }
>        }
>    }
>
>> +#define MLIST_ENTNAME entries
>> +#define MLIST_FOREACH(node, head) QTAILQ_FOREACH((node), (head), MLIST_ENTNAME)
>> +#define MLIST_PREV(node) QTAILQ_PREV((node), MemList, MLIST_ENTNAME);
>> +#define MLIST_NEXT(node) QTAILQ_NEXT((node), MLIST_ENTNAME);
> For the same reasons as my previous comment, please don't hide straightforward
> expressions behind a macro.
>
>> +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 inline void mlist_insert(MemList *head, MemBlock *insr)
>>   {
>> -    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
>> -    uint64_t addr;
>> +    QTAILQ_INSERT_HEAD(head, insr, MLIST_ENTNAME);
>> +}
>> +
>> +static inline void mlist_append(MemList *head, MemBlock *node)
>> +{
>> +    QTAILQ_INSERT_TAIL(head, node, MLIST_ENTNAME);
>> +}
>> +
>> +static inline void mlist_unlink(MemList *head, MemBlock *rem)
>> +{
>> +    QTAILQ_REMOVE(head, rem, MLIST_ENTNAME);
>> +}
> For the same reasons as my comments about the macros, these trivial functions
> are boilerplate.  Why not use the QTAILQ macros directly?
For /at least/ the append and insert cases, I desired call-by-value 
semantics.
As a matter of taste, I find macros annoying for the reason that you 
cannot inline things such as:
mlist_insert(list, mlist_new(...));

but unlink is certainly superfluous, and just something I did for some 
consistency.

If there is a matter of style where in-line function call is to be 
avoided entirely, I'll just nix all of these trivial inlines.
>
> (It would be good to hide the list implementation if this was an external API
> and you want to avoid exposing the implementation details, but within this
> source file there is no point in extra layers of indirection.)
Force of habit, but you're right. I'm not exporting the interface.

[-- Attachment #2: Type: text/html, Size: 4558 bytes --]

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

[Stefan Hajnoczi]

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

On Thu, Jul 31, 2014 at 05:14:12PM -0400, John Snow wrote:
> 
> On 07/31/2014 06:13 AM, Stefan Hajnoczi wrote:
> >On Wed, Jul 30, 2014 at 06:28:28PM -0400, John Snow wrote:
> >>-static uint64_t pc_alloc(QGuestAllocator *allocator, size_t size)
> >>+static inline void mlist_insert(MemList *head, MemBlock *insr)
> >>  {
> >>-    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
> >>-    uint64_t addr;
> >>+    QTAILQ_INSERT_HEAD(head, insr, MLIST_ENTNAME);
> >>+}
> >>+
> >>+static inline void mlist_append(MemList *head, MemBlock *node)
> >>+{
> >>+    QTAILQ_INSERT_TAIL(head, node, MLIST_ENTNAME);
> >>+}
> >>+
> >>+static inline void mlist_unlink(MemList *head, MemBlock *rem)
> >>+{
> >>+    QTAILQ_REMOVE(head, rem, MLIST_ENTNAME);
> >>+}
> >For the same reasons as my comments about the macros, these trivial functions
> >are boilerplate.  Why not use the QTAILQ macros directly?
> For /at least/ the append and insert cases, I desired call-by-value
> semantics.
> As a matter of taste, I find macros annoying for the reason that you cannot
> inline things such as:
> mlist_insert(list, mlist_new(...));
> 
> but unlink is certainly superfluous, and just something I did for some
> consistency.
> 
> If there is a matter of style where in-line function call is to be avoided
> entirely, I'll just nix all of these trivial inlines.

As a reviewer I prefer to see familiar APIs rather than a convenience
layer because it's extra stuff I need to keep in mind.  Sticking to the
APIs makes it quicker for other QEMU developers to parse the code.

That said, feel free to keep the functions if you want.

Stefan

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

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

[Markus Armbruster]

Stefan Hajnoczi <stefanha@gmail.com> writes:

> On Thu, Jul 31, 2014 at 05:14:12PM -0400, John Snow wrote:
>> 
>> On 07/31/2014 06:13 AM, Stefan Hajnoczi wrote:
>> >On Wed, Jul 30, 2014 at 06:28:28PM -0400, John Snow wrote:
>> >>-static uint64_t pc_alloc(QGuestAllocator *allocator, size_t size)
>> >>+static inline void mlist_insert(MemList *head, MemBlock *insr)
>> >>  {
>> >>-    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
>> >>-    uint64_t addr;
>> >>+    QTAILQ_INSERT_HEAD(head, insr, MLIST_ENTNAME);
>> >>+}
>> >>+
>> >>+static inline void mlist_append(MemList *head, MemBlock *node)
>> >>+{
>> >>+    QTAILQ_INSERT_TAIL(head, node, MLIST_ENTNAME);
>> >>+}
>> >>+
>> >>+static inline void mlist_unlink(MemList *head, MemBlock *rem)
>> >>+{
>> >>+    QTAILQ_REMOVE(head, rem, MLIST_ENTNAME);
>> >>+}
>> >For the same reasons as my comments about the macros, these trivial functions
>> >are boilerplate.  Why not use the QTAILQ macros directly?
>> For /at least/ the append and insert cases, I desired call-by-value
>> semantics.
>> As a matter of taste, I find macros annoying for the reason that you cannot
>> inline things such as:
>> mlist_insert(list, mlist_new(...));
>> 
>> but unlink is certainly superfluous, and just something I did for some
>> consistency.
>> 
>> If there is a matter of style where in-line function call is to be avoided
>> entirely, I'll just nix all of these trivial inlines.
>
> As a reviewer I prefer to see familiar APIs rather than a convenience
> layer because it's extra stuff I need to keep in mind.  Sticking to the
> APIs makes it quicker for other QEMU developers to parse the code.

Seconded.

> That said, feel free to keep the functions if you want.

Can't say, as I haven't studied the patch in detail.

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 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