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