| 1 | /* |
| 2 | * libqos malloc support |
| 3 | * |
| 4 | * Copyright (c) 2014 |
| 5 | * |
| 6 | * Author: |
| 7 | * John Snow <jsnow@redhat.com> |
| 8 | * |
| 9 | * This work is licensed under the terms of the GNU GPL, version 2 or later. |
| 10 | * See the COPYING file in the top-level directory. |
| 11 | */ |
| 12 | |
| 13 | #include "qemu/osdep.h" |
| 14 | #include "libqos-malloc.h" |
| 15 | #include "qemu/host-utils.h" |
| 16 | |
| 17 | typedef struct MemBlock { |
| 18 | QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME; |
| 19 | uint64_t size; |
| 20 | uint64_t addr; |
| 21 | } MemBlock; |
| 22 | |
| 23 | #define DEFAULT_PAGE_SIZE 4096 |
| 24 | |
| 25 | static void mlist_delete(MemList *list, MemBlock *node) |
| 26 | { |
| 27 | g_assert(list && node); |
| 28 | QTAILQ_REMOVE(list, node, MLIST_ENTNAME); |
| 29 | g_free(node); |
| 30 | } |
| 31 | |
| 32 | static MemBlock *mlist_find_key(MemList *head, uint64_t addr) |
| 33 | { |
| 34 | MemBlock *node; |
| 35 | QTAILQ_FOREACH(node, head, MLIST_ENTNAME) { |
| 36 | if (node->addr == addr) { |
| 37 | return node; |
| 38 | } |
| 39 | } |
| 40 | return NULL; |
| 41 | } |
| 42 | |
| 43 | static MemBlock *mlist_find_space(MemList *head, uint64_t size) |
| 44 | { |
| 45 | MemBlock *node; |
| 46 | |
| 47 | QTAILQ_FOREACH(node, head, MLIST_ENTNAME) { |
| 48 | if (node->size >= size) { |
| 49 | return node; |
| 50 | } |
| 51 | } |
| 52 | return NULL; |
| 53 | } |
| 54 | |
| 55 | static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr) |
| 56 | { |
| 57 | MemBlock *node; |
| 58 | g_assert(head && insr); |
| 59 | |
| 60 | QTAILQ_FOREACH(node, head, MLIST_ENTNAME) { |
| 61 | if (insr->addr < node->addr) { |
| 62 | QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME); |
| 63 | return insr; |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME); |
| 68 | return insr; |
| 69 | } |
| 70 | |
| 71 | static inline uint64_t mlist_boundary(MemBlock *node) |
| 72 | { |
| 73 | return node->size + node->addr; |
| 74 | } |
| 75 | |
| 76 | static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right) |
| 77 | { |
| 78 | g_assert(head && left && right); |
| 79 | |
| 80 | left->size += right->size; |
| 81 | mlist_delete(head, right); |
| 82 | return left; |
| 83 | } |
| 84 | |
| 85 | static void mlist_coalesce(MemList *head, MemBlock *node) |
| 86 | { |
| 87 | g_assert(node); |
| 88 | MemBlock *left; |
| 89 | MemBlock *right; |
| 90 | char merge; |
| 91 | |
| 92 | do { |
| 93 | merge = 0; |
| 94 | left = QTAILQ_PREV(node, MLIST_ENTNAME); |
| 95 | right = QTAILQ_NEXT(node, MLIST_ENTNAME); |
| 96 | |
| 97 | /* clowns to the left of me */ |
| 98 | if (left && mlist_boundary(left) == node->addr) { |
| 99 | node = mlist_join(head, left, node); |
| 100 | merge = 1; |
| 101 | } |
| 102 | |
| 103 | /* jokers to the right */ |
| 104 | if (right && mlist_boundary(node) == right->addr) { |
| 105 | node = mlist_join(head, node, right); |
| 106 | merge = 1; |
| 107 | } |
| 108 | |
| 109 | } while (merge); |
| 110 | } |
| 111 | |
| 112 | static MemBlock *mlist_new(uint64_t addr, uint64_t size) |
| 113 | { |
| 114 | MemBlock *block; |
| 115 | |
| 116 | if (!size) { |
| 117 | return NULL; |
| 118 | } |
| 119 | block = g_new0(MemBlock, 1); |
| 120 | |
| 121 | block->addr = addr; |
| 122 | block->size = size; |
| 123 | |
| 124 | return block; |
| 125 | } |
| 126 | |
| 127 | static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode, |
| 128 | uint64_t size) |
| 129 | { |
| 130 | uint64_t addr; |
| 131 | MemBlock *usednode; |
| 132 | |
| 133 | g_assert(freenode); |
| 134 | g_assert_cmpint(freenode->size, >=, size); |
| 135 | |
| 136 | addr = freenode->addr; |
| 137 | if (freenode->size == size) { |
| 138 | /* re-use this freenode as our used node */ |
| 139 | QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME); |
| 140 | usednode = freenode; |
| 141 | } else { |
| 142 | /* adjust the free node and create a new used node */ |
| 143 | freenode->addr += size; |
| 144 | freenode->size -= size; |
| 145 | usednode = mlist_new(addr, size); |
| 146 | } |
| 147 | |
| 148 | mlist_sort_insert(s->used, usednode); |
| 149 | return addr; |
| 150 | } |
| 151 | |
| 152 | /* To assert the correctness of the list. |
| 153 | * Used only if ALLOC_PARANOID is set. */ |
| 154 | static void mlist_check(QGuestAllocator *s) |
| 155 | { |
| 156 | MemBlock *node; |
| 157 | uint64_t addr = s->start > 0 ? s->start - 1 : 0; |
| 158 | uint64_t next = s->start; |
| 159 | |
| 160 | QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) { |
| 161 | g_assert_cmpint(node->addr, >, addr); |
| 162 | g_assert_cmpint(node->addr, >=, next); |
| 163 | addr = node->addr; |
| 164 | next = node->addr + node->size; |
| 165 | } |
| 166 | |
| 167 | addr = s->start > 0 ? s->start - 1 : 0; |
| 168 | next = s->start; |
| 169 | QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) { |
| 170 | g_assert_cmpint(node->addr, >, addr); |
| 171 | g_assert_cmpint(node->addr, >=, next); |
| 172 | addr = node->addr; |
| 173 | next = node->addr + node->size; |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size) |
| 178 | { |
| 179 | MemBlock *node; |
| 180 | |
| 181 | node = mlist_find_space(s->free, size); |
| 182 | if (!node) { |
| 183 | fprintf(stderr, "Out of guest memory.\n"); |
| 184 | g_assert_not_reached(); |
| 185 | } |
| 186 | return mlist_fulfill(s, node, size); |
| 187 | } |
| 188 | |
| 189 | static void mlist_free(QGuestAllocator *s, uint64_t addr) |
| 190 | { |
| 191 | MemBlock *node; |
| 192 | |
| 193 | if (addr == 0) { |
| 194 | return; |
| 195 | } |
| 196 | |
| 197 | node = mlist_find_key(s->used, addr); |
| 198 | if (!node) { |
| 199 | fprintf(stderr, "Error: no record found for an allocation at " |
| 200 | "0x%016" PRIx64 ".\n", |
| 201 | addr); |
| 202 | g_assert_not_reached(); |
| 203 | } |
| 204 | |
| 205 | /* Rip it out of the used list and re-insert back into the free list. */ |
| 206 | QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME); |
| 207 | mlist_sort_insert(s->free, node); |
| 208 | mlist_coalesce(s->free, node); |
| 209 | } |
| 210 | |
| 211 | /* |
| 212 | * Mostly for valgrind happiness, but it does offer |
| 213 | * a chokepoint for debugging guest memory leaks, too. |
| 214 | */ |
| 215 | void alloc_destroy(QGuestAllocator *allocator) |
| 216 | { |
| 217 | MemBlock *node; |
| 218 | MemBlock *tmp; |
| 219 | QAllocOpts mask; |
| 220 | |
| 221 | /* Check for guest leaks, and destroy the list. */ |
| 222 | QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) { |
| 223 | if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) { |
| 224 | fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; " |
| 225 | "size 0x%016" PRIx64 ".\n", |
| 226 | node->addr, node->size); |
| 227 | } |
| 228 | if (allocator->opts & (ALLOC_LEAK_ASSERT)) { |
| 229 | g_assert_not_reached(); |
| 230 | } |
| 231 | g_free(node); |
| 232 | } |
| 233 | |
| 234 | /* If we have previously asserted that there are no leaks, then there |
| 235 | * should be only one node here with a specific address and size. */ |
| 236 | mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID; |
| 237 | QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) { |
| 238 | if ((allocator->opts & mask) == mask) { |
| 239 | if ((node->addr != allocator->start) || |
| 240 | (node->size != allocator->end - allocator->start)) { |
| 241 | fprintf(stderr, "Free list is corrupted.\n"); |
| 242 | g_assert_not_reached(); |
| 243 | } |
| 244 | } |
| 245 | |
| 246 | g_free(node); |
| 247 | } |
| 248 | |
| 249 | g_free(allocator->used); |
| 250 | g_free(allocator->free); |
| 251 | } |
| 252 | |
| 253 | uint64_t guest_alloc(QGuestAllocator *allocator, size_t size) |
| 254 | { |
| 255 | uint64_t rsize = size; |
| 256 | uint64_t naddr; |
| 257 | |
| 258 | if (!size) { |
| 259 | return 0; |
| 260 | } |
| 261 | |
| 262 | rsize += (allocator->page_size - 1); |
| 263 | rsize &= -allocator->page_size; |
| 264 | g_assert_cmpint((allocator->start + rsize), <=, allocator->end); |
| 265 | g_assert_cmpint(rsize, >=, size); |
| 266 | |
| 267 | naddr = mlist_alloc(allocator, rsize); |
| 268 | if (allocator->opts & ALLOC_PARANOID) { |
| 269 | mlist_check(allocator); |
| 270 | } |
| 271 | |
| 272 | return naddr; |
| 273 | } |
| 274 | |
| 275 | void guest_free(QGuestAllocator *allocator, uint64_t addr) |
| 276 | { |
| 277 | if (!addr) { |
| 278 | return; |
| 279 | } |
| 280 | mlist_free(allocator, addr); |
| 281 | if (allocator->opts & ALLOC_PARANOID) { |
| 282 | mlist_check(allocator); |
| 283 | } |
| 284 | } |
| 285 | |
| 286 | void alloc_init(QGuestAllocator *s, QAllocOpts opts, |
| 287 | uint64_t start, uint64_t end, |
| 288 | size_t page_size) |
| 289 | { |
| 290 | MemBlock *node; |
| 291 | |
| 292 | s->opts = opts; |
| 293 | s->start = start; |
| 294 | s->end = end; |
| 295 | |
| 296 | s->used = g_new(MemList, 1); |
| 297 | s->free = g_new(MemList, 1); |
| 298 | QTAILQ_INIT(s->used); |
| 299 | QTAILQ_INIT(s->free); |
| 300 | |
| 301 | node = mlist_new(s->start, s->end - s->start); |
| 302 | QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME); |
| 303 | |
| 304 | s->page_size = page_size; |
| 305 | } |
| 306 | |
| 307 | void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts) |
| 308 | { |
| 309 | allocator->opts |= opts; |
| 310 | } |
| 311 | |
| 312 | void migrate_allocator(QGuestAllocator *src, |
| 313 | QGuestAllocator *dst) |
| 314 | { |
| 315 | MemBlock *node, *tmp; |
| 316 | MemList *tmpused, *tmpfree; |
| 317 | |
| 318 | /* The general memory layout should be equivalent, |
| 319 | * though opts can differ. */ |
| 320 | g_assert_cmphex(src->start, ==, dst->start); |
| 321 | g_assert_cmphex(src->end, ==, dst->end); |
| 322 | |
| 323 | /* Destroy (silently, regardless of options) the dest-list: */ |
| 324 | QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) { |
| 325 | g_free(node); |
| 326 | } |
| 327 | QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) { |
| 328 | g_free(node); |
| 329 | } |
| 330 | |
| 331 | tmpused = dst->used; |
| 332 | tmpfree = dst->free; |
| 333 | |
| 334 | /* Inherit the lists of the source allocator: */ |
| 335 | dst->used = src->used; |
| 336 | dst->free = src->free; |
| 337 | |
| 338 | /* Source is now re-initialized, the source memory is 'invalid' now: */ |
| 339 | src->used = tmpused; |
| 340 | src->free = tmpfree; |
| 341 | QTAILQ_INIT(src->used); |
| 342 | QTAILQ_INIT(src->free); |
| 343 | node = mlist_new(src->start, src->end - src->start); |
| 344 | QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME); |
| 345 | } |