blob: 19d05cafa67de733b68eeceb1207ef1d2b32d7d3 [file] [log] [blame]
Marc Marí292be092014-10-23 10:12:42 +02001/*
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 "libqos/malloc.h"
14#include "qemu-common.h"
15#include <stdio.h>
16#include <inttypes.h>
17#include <glib.h>
18
John Snowf6f363c2015-01-19 15:15:54 -050019typedef QTAILQ_HEAD(MemList, MemBlock) MemList;
20
21typedef struct MemBlock {
22 QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
23 uint64_t size;
24 uint64_t addr;
25} MemBlock;
26
27struct QGuestAllocator {
28 QAllocOpts opts;
29 uint64_t start;
30 uint64_t end;
31 uint32_t page_size;
32
John Snow085248a2015-05-22 14:13:43 -040033 MemList *used;
34 MemList *free;
John Snowf6f363c2015-01-19 15:15:54 -050035};
36
37#define DEFAULT_PAGE_SIZE 4096
38
Marc Marí292be092014-10-23 10:12:42 +020039static void mlist_delete(MemList *list, MemBlock *node)
40{
41 g_assert(list && node);
42 QTAILQ_REMOVE(list, node, MLIST_ENTNAME);
43 g_free(node);
44}
45
46static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
47{
48 MemBlock *node;
49 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
50 if (node->addr == addr) {
51 return node;
52 }
53 }
54 return NULL;
55}
56
57static MemBlock *mlist_find_space(MemList *head, uint64_t size)
58{
59 MemBlock *node;
60
61 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
62 if (node->size >= size) {
63 return node;
64 }
65 }
66 return NULL;
67}
68
69static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
70{
71 MemBlock *node;
72 g_assert(head && insr);
73
74 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
75 if (insr->addr < node->addr) {
76 QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME);
77 return insr;
78 }
79 }
80
81 QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME);
82 return insr;
83}
84
85static inline uint64_t mlist_boundary(MemBlock *node)
86{
87 return node->size + node->addr;
88}
89
90static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right)
91{
92 g_assert(head && left && right);
93
94 left->size += right->size;
95 mlist_delete(head, right);
96 return left;
97}
98
99static void mlist_coalesce(MemList *head, MemBlock *node)
100{
101 g_assert(node);
102 MemBlock *left;
103 MemBlock *right;
104 char merge;
105
106 do {
107 merge = 0;
108 left = QTAILQ_PREV(node, MemList, MLIST_ENTNAME);
109 right = QTAILQ_NEXT(node, MLIST_ENTNAME);
110
111 /* clowns to the left of me */
112 if (left && mlist_boundary(left) == node->addr) {
113 node = mlist_join(head, left, node);
114 merge = 1;
115 }
116
117 /* jokers to the right */
118 if (right && mlist_boundary(node) == right->addr) {
119 node = mlist_join(head, node, right);
120 merge = 1;
121 }
122
123 } while (merge);
124}
125
John Snowf6f363c2015-01-19 15:15:54 -0500126static MemBlock *mlist_new(uint64_t addr, uint64_t size)
127{
128 MemBlock *block;
129
130 if (!size) {
131 return NULL;
132 }
133 block = g_malloc0(sizeof(MemBlock));
134
135 block->addr = addr;
136 block->size = size;
137
138 return block;
139}
140
Marc Marí292be092014-10-23 10:12:42 +0200141static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode,
142 uint64_t size)
143{
144 uint64_t addr;
145 MemBlock *usednode;
146
147 g_assert(freenode);
148 g_assert_cmpint(freenode->size, >=, size);
149
150 addr = freenode->addr;
151 if (freenode->size == size) {
152 /* re-use this freenode as our used node */
John Snow085248a2015-05-22 14:13:43 -0400153 QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
Marc Marí292be092014-10-23 10:12:42 +0200154 usednode = freenode;
155 } else {
156 /* adjust the free node and create a new used node */
157 freenode->addr += size;
158 freenode->size -= size;
159 usednode = mlist_new(addr, size);
160 }
161
John Snow085248a2015-05-22 14:13:43 -0400162 mlist_sort_insert(s->used, usednode);
Marc Marí292be092014-10-23 10:12:42 +0200163 return addr;
164}
165
166/* To assert the correctness of the list.
167 * Used only if ALLOC_PARANOID is set. */
168static void mlist_check(QGuestAllocator *s)
169{
170 MemBlock *node;
171 uint64_t addr = s->start > 0 ? s->start - 1 : 0;
172 uint64_t next = s->start;
173
John Snow085248a2015-05-22 14:13:43 -0400174 QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
Marc Marí292be092014-10-23 10:12:42 +0200175 g_assert_cmpint(node->addr, >, addr);
176 g_assert_cmpint(node->addr, >=, next);
177 addr = node->addr;
178 next = node->addr + node->size;
179 }
180
181 addr = s->start > 0 ? s->start - 1 : 0;
182 next = s->start;
John Snow085248a2015-05-22 14:13:43 -0400183 QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
Marc Marí292be092014-10-23 10:12:42 +0200184 g_assert_cmpint(node->addr, >, addr);
185 g_assert_cmpint(node->addr, >=, next);
186 addr = node->addr;
187 next = node->addr + node->size;
188 }
189}
190
191static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
192{
193 MemBlock *node;
194
John Snow085248a2015-05-22 14:13:43 -0400195 node = mlist_find_space(s->free, size);
Marc Marí292be092014-10-23 10:12:42 +0200196 if (!node) {
197 fprintf(stderr, "Out of guest memory.\n");
198 g_assert_not_reached();
199 }
200 return mlist_fulfill(s, node, size);
201}
202
203static void mlist_free(QGuestAllocator *s, uint64_t addr)
204{
205 MemBlock *node;
206
207 if (addr == 0) {
208 return;
209 }
210
John Snow085248a2015-05-22 14:13:43 -0400211 node = mlist_find_key(s->used, addr);
Marc Marí292be092014-10-23 10:12:42 +0200212 if (!node) {
213 fprintf(stderr, "Error: no record found for an allocation at "
214 "0x%016" PRIx64 ".\n",
215 addr);
216 g_assert_not_reached();
217 }
218
219 /* Rip it out of the used list and re-insert back into the free list. */
John Snow085248a2015-05-22 14:13:43 -0400220 QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
221 mlist_sort_insert(s->free, node);
222 mlist_coalesce(s->free, node);
Marc Marí292be092014-10-23 10:12:42 +0200223}
224
Marc Marí292be092014-10-23 10:12:42 +0200225/*
226 * Mostly for valgrind happiness, but it does offer
227 * a chokepoint for debugging guest memory leaks, too.
228 */
229void alloc_uninit(QGuestAllocator *allocator)
230{
231 MemBlock *node;
232 MemBlock *tmp;
233 QAllocOpts mask;
234
235 /* Check for guest leaks, and destroy the list. */
John Snow085248a2015-05-22 14:13:43 -0400236 QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
Marc Marí292be092014-10-23 10:12:42 +0200237 if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) {
238 fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
239 "size 0x%016" PRIx64 ".\n",
240 node->addr, node->size);
241 }
242 if (allocator->opts & (ALLOC_LEAK_ASSERT)) {
243 g_assert_not_reached();
244 }
245 g_free(node);
246 }
247
248 /* If we have previously asserted that there are no leaks, then there
249 * should be only one node here with a specific address and size. */
250 mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID;
John Snow085248a2015-05-22 14:13:43 -0400251 QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
Marc Marí292be092014-10-23 10:12:42 +0200252 if ((allocator->opts & mask) == mask) {
253 if ((node->addr != allocator->start) ||
254 (node->size != allocator->end - allocator->start)) {
255 fprintf(stderr, "Free list is corrupted.\n");
256 g_assert_not_reached();
257 }
258 }
259
260 g_free(node);
261 }
262
John Snow085248a2015-05-22 14:13:43 -0400263 g_free(allocator->used);
264 g_free(allocator->free);
Marc Marí292be092014-10-23 10:12:42 +0200265 g_free(allocator);
266}
267
268uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
269{
270 uint64_t rsize = size;
271 uint64_t naddr;
272
John Snowb1b66c32016-01-11 14:10:43 -0500273 if (!size) {
274 return 0;
275 }
276
Marc Marí292be092014-10-23 10:12:42 +0200277 rsize += (allocator->page_size - 1);
278 rsize &= -allocator->page_size;
279 g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
280 g_assert_cmpint(rsize, >=, size);
281
282 naddr = mlist_alloc(allocator, rsize);
283 if (allocator->opts & ALLOC_PARANOID) {
284 mlist_check(allocator);
285 }
286
287 return naddr;
288}
289
290void guest_free(QGuestAllocator *allocator, uint64_t addr)
291{
Fam Zheng28452752015-04-24 19:35:17 +0800292 if (!addr) {
293 return;
294 }
Marc Marí292be092014-10-23 10:12:42 +0200295 mlist_free(allocator, addr);
296 if (allocator->opts & ALLOC_PARANOID) {
297 mlist_check(allocator);
298 }
299}
John Snowaf77f2c2015-01-19 15:15:49 -0500300
301QGuestAllocator *alloc_init(uint64_t start, uint64_t end)
302{
303 QGuestAllocator *s = g_malloc0(sizeof(*s));
304 MemBlock *node;
305
306 s->start = start;
307 s->end = end;
308
John Snow085248a2015-05-22 14:13:43 -0400309 s->used = g_malloc(sizeof(MemList));
310 s->free = g_malloc(sizeof(MemList));
311 QTAILQ_INIT(s->used);
312 QTAILQ_INIT(s->free);
John Snowaf77f2c2015-01-19 15:15:49 -0500313
314 node = mlist_new(s->start, s->end - s->start);
John Snow085248a2015-05-22 14:13:43 -0400315 QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
John Snowaf77f2c2015-01-19 15:15:49 -0500316
John Snowf6f363c2015-01-19 15:15:54 -0500317 s->page_size = DEFAULT_PAGE_SIZE;
318
John Snowaf77f2c2015-01-19 15:15:49 -0500319 return s;
320}
John Snowfa02e602015-01-19 15:15:53 -0500321
322QGuestAllocator *alloc_init_flags(QAllocOpts opts,
323 uint64_t start, uint64_t end)
324{
325 QGuestAllocator *s = alloc_init(start, end);
326 s->opts = opts;
327 return s;
328}
John Snowf6f363c2015-01-19 15:15:54 -0500329
330void alloc_set_page_size(QGuestAllocator *allocator, size_t page_size)
331{
332 /* Can't alter the page_size for an allocator in-use */
John Snow085248a2015-05-22 14:13:43 -0400333 g_assert(QTAILQ_EMPTY(allocator->used));
John Snowf6f363c2015-01-19 15:15:54 -0500334
335 g_assert(is_power_of_2(page_size));
336 allocator->page_size = page_size;
337}
John Snow259342d2015-02-05 12:41:28 -0500338
339void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
340{
341 allocator->opts |= opts;
342}
John Snow085248a2015-05-22 14:13:43 -0400343
344void migrate_allocator(QGuestAllocator *src,
345 QGuestAllocator *dst)
346{
347 MemBlock *node, *tmp;
348 MemList *tmpused, *tmpfree;
349
350 /* The general memory layout should be equivalent,
351 * though opts can differ. */
352 g_assert_cmphex(src->start, ==, dst->start);
353 g_assert_cmphex(src->end, ==, dst->end);
354
355 /* Destroy (silently, regardless of options) the dest-list: */
356 QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
357 g_free(node);
358 }
359 QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
360 g_free(node);
361 }
362
363 tmpused = dst->used;
364 tmpfree = dst->free;
365
366 /* Inherit the lists of the source allocator: */
367 dst->used = src->used;
368 dst->free = src->free;
369
370 /* Source is now re-initialized, the source memory is 'invalid' now: */
371 src->used = tmpused;
372 src->free = tmpfree;
373 QTAILQ_INIT(src->used);
374 QTAILQ_INIT(src->free);
375 node = mlist_new(src->start, src->end - src->start);
376 QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);
377 return;
378}