From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34331) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YAi5f-0002td-7b for qemu-devel@nongnu.org; Mon, 12 Jan 2015 11:43:45 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YAi5b-00025u-SJ for qemu-devel@nongnu.org; Mon, 12 Jan 2015 11:43:43 -0500 Received: from mx1.redhat.com ([209.132.183.28]:42169) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YAi5b-00025g-Gq for qemu-devel@nongnu.org; Mon, 12 Jan 2015 11:43:39 -0500 From: Stefan Hajnoczi Date: Mon, 12 Jan 2015 16:40:10 +0000 Message-Id: <1421080834-14724-21-git-send-email-stefanha@redhat.com> In-Reply-To: <1421080834-14724-1-git-send-email-stefanha@redhat.com> References: <1421080834-14724-1-git-send-email-stefanha@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: [Qemu-devel] [PULL v2 20/44] libqos: Convert malloc-pc allocator to a generic allocator List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: =?UTF-8?q?Marc=20Mar=C3=AD?= , Peter Maydell , Stefan Hajnoczi From: Marc Mar=C3=AD The allocator in malloc-pc has been extracted, so it can be used in every= arch. This operation showed that both the alloc and free functions can be also generic. Because of this, the QGuestAllocator has been removed from is function to= wrap the alloc and free function, and now just contains the allocator paramete= rs. As a result, only the allocator initalizer and unitializer are arch depen= dent. Signed-off-by: Marc Mar=C3=AD Reviewed-by: Stefan Hajnoczi Reviewed-by: John Snow Signed-off-by: Stefan Hajnoczi --- tests/Makefile | 2 +- tests/libqos/malloc-pc.c | 280 +----------------------------------------= ------ tests/libqos/malloc-pc.h | 11 +- tests/libqos/malloc.c | 270 +++++++++++++++++++++++++++++++++++++++++= ++++ tests/libqos/malloc.h | 45 +++++--- 5 files changed, 309 insertions(+), 299 deletions(-) create mode 100644 tests/libqos/malloc.c diff --git a/tests/Makefile b/tests/Makefile index e4ddb6a..c2e2e52 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -298,7 +298,7 @@ tests/test-opts-visitor$(EXESUF): tests/test-opts-vis= itor.o $(test-qapi-obj-y) l tests/test-mul64$(EXESUF): tests/test-mul64.o libqemuutil.a tests/test-bitops$(EXESUF): tests/test-bitops.o libqemuutil.a =20 -libqos-obj-y =3D tests/libqos/pci.o tests/libqos/fw_cfg.o +libqos-obj-y =3D tests/libqos/pci.o tests/libqos/fw_cfg.o tests/libqos/m= alloc.o libqos-obj-y +=3D tests/libqos/i2c.o libqos-pc-obj-y =3D $(libqos-obj-y) tests/libqos/pci-pc.o libqos-pc-obj-y +=3D tests/libqos/malloc-pc.o diff --git a/tests/libqos/malloc-pc.c b/tests/libqos/malloc-pc.c index f4218c6..c9c48fd 100644 --- a/tests/libqos/malloc-pc.c +++ b/tests/libqos/malloc-pc.c @@ -17,296 +17,28 @@ #include "hw/nvram/fw_cfg.h" =20 #include "qemu-common.h" -#include "qemu/queue.h" #include =20 #define PAGE_SIZE (4096) =20 -#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 MemBlock *mlist_new(uint64_t addr, uint64_t size) -{ - MemBlock *block; - - if (!size) { - return NULL; - } - block =3D g_malloc0(sizeof(MemBlock)); - - block->addr =3D addr; - block->size =3D 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 =3D=3D 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 >=3D 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 *rig= ht) -{ - g_assert(head && left && right); - - left->size +=3D 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 =3D 0; - left =3D QTAILQ_PREV(node, MemList, MLIST_ENTNAME); - right =3D QTAILQ_NEXT(node, MLIST_ENTNAME); - - /* clowns to the left of me */ - if (left && mlist_boundary(left) =3D=3D node->addr) { - node =3D mlist_join(head, left, node); - merge =3D 1; - } - - /* jokers to the right */ - if (right && mlist_boundary(node) =3D=3D right->addr) { - node =3D mlist_join(head, node, right); - merge =3D 1; - } - - } 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, >=3D, size); - - addr =3D freenode->addr; - if (freenode->size =3D=3D size) { - /* re-use this freenode as our used node */ - QTAILQ_REMOVE(&s->free, freenode, MLIST_ENTNAME); - usednode =3D freenode; - } else { - /* adjust the free node and create a new used node */ - freenode->addr +=3D size; - freenode->size -=3D size; - usednode =3D 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 =3D s->start > 0 ? s->start - 1 : 0; - uint64_t next =3D s->start; - - QTAILQ_FOREACH(node, &s->free, MLIST_ENTNAME) { - g_assert_cmpint(node->addr, >, addr); - g_assert_cmpint(node->addr, >=3D, next); - addr =3D node->addr; - next =3D node->addr + node->size; - } - - addr =3D s->start > 0 ? s->start - 1 : 0; - next =3D s->start; - QTAILQ_FOREACH(node, &s->used, MLIST_ENTNAME) { - g_assert_cmpint(node->addr, >, addr); - g_assert_cmpint(node->addr, >=3D, next); - addr =3D node->addr; - next =3D node->addr + node->size; - } -} - -static uint64_t pc_mlist_alloc(PCAlloc *s, uint64_t size) -{ - MemBlock *node; - - node =3D 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 =3D=3D 0) { - return; - } - - node =3D 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 =3D container_of(allocator, PCAlloc, alloc); - uint64_t rsize =3D size; - uint64_t naddr; - - rsize +=3D (PAGE_SIZE - 1); - rsize &=3D -PAGE_SIZE; - g_assert_cmpint((s->start + rsize), <=3D, s->end); - g_assert_cmpint(rsize, >=3D, size); - - naddr =3D 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 =3D 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 =3D 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 ther= e - * should be only one node here with a specific address and size. */ - mask =3D PC_ALLOC_LEAK_ASSERT | PC_ALLOC_PARANOID; - QTAILQ_FOREACH_SAFE(node, &s->free, MLIST_ENTNAME, tmp) { - if ((s->opts & mask) =3D=3D mask) { - if ((node->addr !=3D s->start) || - (node->size !=3D s->end - s->start)) { - fprintf(stderr, "Free list is corrupted.\n"); - g_assert_not_reached(); - } - } - - g_free(node); - } - - g_free(s); + alloc_uninit(allocator); } =20 -QGuestAllocator *pc_alloc_init_flags(PCAllocOpts flags) +QGuestAllocator *pc_alloc_init_flags(QAllocOpts flags) { - PCAlloc *s =3D g_malloc0(sizeof(*s)); + QGuestAllocator *s =3D g_malloc0(sizeof(*s)); uint64_t ram_size; QFWCFG *fw_cfg =3D pc_fw_cfg_init(); MemBlock *node; =20 s->opts =3D flags; - s->alloc.alloc =3D pc_alloc; - s->alloc.free =3D pc_free; + s->page_size =3D PAGE_SIZE; =20 ram_size =3D qfw_cfg_get_u64(fw_cfg, FW_CFG_RAM_SIZE); =20 @@ -325,10 +57,10 @@ QGuestAllocator *pc_alloc_init_flags(PCAllocOpts fla= gs) node =3D mlist_new(s->start, s->end - s->start); QTAILQ_INSERT_HEAD(&s->free, node, MLIST_ENTNAME); =20 - return &s->alloc; + return s; } =20 inline QGuestAllocator *pc_alloc_init(void) { - return pc_alloc_init_flags(PC_ALLOC_NO_FLAGS); + return pc_alloc_init_flags(ALLOC_NO_FLAGS); } diff --git a/tests/libqos/malloc-pc.h b/tests/libqos/malloc-pc.h index 9f525e3..86ab9f0 100644 --- a/tests/libqos/malloc-pc.h +++ b/tests/libqos/malloc-pc.h @@ -15,15 +15,8 @@ =20 #include "libqos/malloc.h" =20 -typedef enum { - PC_ALLOC_NO_FLAGS =3D 0x00, - PC_ALLOC_LEAK_WARN =3D 0x01, - PC_ALLOC_LEAK_ASSERT =3D 0x02, - PC_ALLOC_PARANOID =3D 0x04 -} PCAllocOpts; - QGuestAllocator *pc_alloc_init(void); -QGuestAllocator *pc_alloc_init_flags(PCAllocOpts flags); -void pc_alloc_uninit(QGuestAllocator *allocator); +QGuestAllocator *pc_alloc_init_flags(QAllocOpts flags); +void pc_alloc_uninit(QGuestAllocator *allocator); =20 #endif diff --git a/tests/libqos/malloc.c b/tests/libqos/malloc.c new file mode 100644 index 0000000..5debf18 --- /dev/null +++ b/tests/libqos/malloc.c @@ -0,0 +1,270 @@ +/* + * libqos malloc support + * + * Copyright (c) 2014 + * + * Author: + * John Snow + * + * This work is licensed under the terms of the GNU GPL, version 2 or la= ter. + * See the COPYING file in the top-level directory. + */ + +#include "libqos/malloc.h" +#include "qemu-common.h" +#include +#include +#include + +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 =3D=3D 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 >=3D 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 *rig= ht) +{ + g_assert(head && left && right); + + left->size +=3D 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 =3D 0; + left =3D QTAILQ_PREV(node, MemList, MLIST_ENTNAME); + right =3D QTAILQ_NEXT(node, MLIST_ENTNAME); + + /* clowns to the left of me */ + if (left && mlist_boundary(left) =3D=3D node->addr) { + node =3D mlist_join(head, left, node); + merge =3D 1; + } + + /* jokers to the right */ + if (right && mlist_boundary(node) =3D=3D right->addr) { + node =3D mlist_join(head, node, right); + merge =3D 1; + } + + } while (merge); +} + +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, >=3D, size); + + addr =3D freenode->addr; + if (freenode->size =3D=3D size) { + /* re-use this freenode as our used node */ + QTAILQ_REMOVE(&s->free, freenode, MLIST_ENTNAME); + usednode =3D freenode; + } else { + /* adjust the free node and create a new used node */ + freenode->addr +=3D size; + freenode->size -=3D size; + usednode =3D 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 =3D s->start > 0 ? s->start - 1 : 0; + uint64_t next =3D s->start; + + QTAILQ_FOREACH(node, &s->free, MLIST_ENTNAME) { + g_assert_cmpint(node->addr, >, addr); + g_assert_cmpint(node->addr, >=3D, next); + addr =3D node->addr; + next =3D node->addr + node->size; + } + + addr =3D s->start > 0 ? s->start - 1 : 0; + next =3D s->start; + QTAILQ_FOREACH(node, &s->used, MLIST_ENTNAME) { + g_assert_cmpint(node->addr, >, addr); + g_assert_cmpint(node->addr, >=3D, next); + addr =3D node->addr; + next =3D node->addr + node->size; + } +} + +static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size) +{ + MemBlock *node; + + node =3D 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 =3D=3D 0) { + return; + } + + node =3D 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); +} + +MemBlock *mlist_new(uint64_t addr, uint64_t size) +{ + MemBlock *block; + + if (!size) { + return NULL; + } + block =3D g_malloc0(sizeof(MemBlock)); + + block->addr =3D addr; + block->size =3D size; + + return block; +} + +/* + * 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 ther= e + * should be only one node here with a specific address and size. */ + mask =3D ALLOC_LEAK_ASSERT | ALLOC_PARANOID; + QTAILQ_FOREACH_SAFE(node, &allocator->free, MLIST_ENTNAME, tmp) { + if ((allocator->opts & mask) =3D=3D mask) { + if ((node->addr !=3D allocator->start) || + (node->size !=3D allocator->end - allocator->start)) { + fprintf(stderr, "Free list is corrupted.\n"); + g_assert_not_reached(); + } + } + + g_free(node); + } + + g_free(allocator); +} + +uint64_t guest_alloc(QGuestAllocator *allocator, size_t size) +{ + uint64_t rsize =3D size; + uint64_t naddr; + + rsize +=3D (allocator->page_size - 1); + rsize &=3D -allocator->page_size; + g_assert_cmpint((allocator->start + rsize), <=3D, allocator->end); + g_assert_cmpint(rsize, >=3D, size); + + naddr =3D mlist_alloc(allocator, rsize); + if (allocator->opts & ALLOC_PARANOID) { + mlist_check(allocator); + } + + return naddr; +} + +void guest_free(QGuestAllocator *allocator, uint64_t addr) +{ + mlist_free(allocator, addr); + if (allocator->opts & ALLOC_PARANOID) { + mlist_check(allocator); + } +} diff --git a/tests/libqos/malloc.h b/tests/libqos/malloc.h index 5565381..465efeb 100644 --- a/tests/libqos/malloc.h +++ b/tests/libqos/malloc.h @@ -15,24 +15,39 @@ =20 #include #include +#include "qemu/queue.h" =20 -typedef struct QGuestAllocator QGuestAllocator; +#define MLIST_ENTNAME entries =20 -struct QGuestAllocator -{ - uint64_t (*alloc)(QGuestAllocator *allocator, size_t size); - void (*free)(QGuestAllocator *allocator, uint64_t addr); -}; +typedef enum { + ALLOC_NO_FLAGS =3D 0x00, + ALLOC_LEAK_WARN =3D 0x01, + ALLOC_LEAK_ASSERT =3D 0x02, + ALLOC_PARANOID =3D 0x04 +} QAllocOpts; + +typedef QTAILQ_HEAD(MemList, MemBlock) MemList; +typedef struct MemBlock { + QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME; + uint64_t size; + uint64_t addr; +} MemBlock; + +typedef struct QGuestAllocator { + QAllocOpts opts; + uint64_t start; + uint64_t end; + uint32_t page_size; + + MemList used; + MemList free; +} QGuestAllocator; + +MemBlock *mlist_new(uint64_t addr, uint64_t size); +void alloc_uninit(QGuestAllocator *allocator); =20 /* Always returns page aligned values */ -static inline uint64_t guest_alloc(QGuestAllocator *allocator, size_t si= ze) -{ - return allocator->alloc(allocator, size); -} - -static inline void guest_free(QGuestAllocator *allocator, uint64_t addr) -{ - allocator->free(allocator, addr); -} +uint64_t guest_alloc(QGuestAllocator *allocator, size_t size); +void guest_free(QGuestAllocator *allocator, uint64_t addr); =20 #endif --=20 2.1.0