| /* |
| * libqos malloc support for PC |
| * |
| * Copyright IBM, Corp. 2012-2013 |
| * |
| * Authors: |
| * Anthony Liguori <aliguori@us.ibm.com> |
| * |
| * 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-pc.h" |
| #include "libqos/fw_cfg.h" |
| |
| #define NO_QEMU_PROTOS |
| #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 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); |
| 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(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 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_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; |
| |
| ram_size = qfw_cfg_get_u64(fw_cfg, FW_CFG_RAM_SIZE); |
| |
| /* Start at 1MB */ |
| s->start = 1 << 20; |
| |
| /* Respect PCI hole */ |
| s->end = MIN(ram_size, 0xE0000000); |
| |
| /* 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); |
| } |