Make vfio MSI interrupt be non-threaded.
[kvmfornfv.git] / qemu / tests / libqos / malloc.c
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 "libqos/malloc.h"
14 #include "qemu-common.h"
15 #include <stdio.h>
16 #include <inttypes.h>
17 #include <glib.h>
18
19 typedef QTAILQ_HEAD(MemList, MemBlock) MemList;
20
21 typedef struct MemBlock {
22     QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
23     uint64_t size;
24     uint64_t addr;
25 } MemBlock;
26
27 struct QGuestAllocator {
28     QAllocOpts opts;
29     uint64_t start;
30     uint64_t end;
31     uint32_t page_size;
32
33     MemList *used;
34     MemList *free;
35 };
36
37 #define DEFAULT_PAGE_SIZE 4096
38
39 static 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
46 static 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
57 static 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
69 static 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
85 static inline uint64_t mlist_boundary(MemBlock *node)
86 {
87     return node->size + node->addr;
88 }
89
90 static 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
99 static 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
126 static 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
141 static 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 */
153         QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
154         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
162     mlist_sort_insert(s->used, usednode);
163     return addr;
164 }
165
166 /* To assert the correctness of the list.
167  * Used only if ALLOC_PARANOID is set. */
168 static 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
174     QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
175         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;
183     QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
184         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
191 static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
192 {
193     MemBlock *node;
194
195     node = mlist_find_space(s->free, size);
196     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
203 static void mlist_free(QGuestAllocator *s, uint64_t addr)
204 {
205     MemBlock *node;
206
207     if (addr == 0) {
208         return;
209     }
210
211     node = mlist_find_key(s->used, addr);
212     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. */
220     QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
221     mlist_sort_insert(s->free, node);
222     mlist_coalesce(s->free, node);
223 }
224
225 /*
226  * Mostly for valgrind happiness, but it does offer
227  * a chokepoint for debugging guest memory leaks, too.
228  */
229 void alloc_uninit(QGuestAllocator *allocator)
230 {
231     MemBlock *node;
232     MemBlock *tmp;
233     QAllocOpts mask;
234
235     /* Check for guest leaks, and destroy the list. */
236     QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
237         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;
251     QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
252         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
263     g_free(allocator->used);
264     g_free(allocator->free);
265     g_free(allocator);
266 }
267
268 uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
269 {
270     uint64_t rsize = size;
271     uint64_t naddr;
272
273     rsize += (allocator->page_size - 1);
274     rsize &= -allocator->page_size;
275     g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
276     g_assert_cmpint(rsize, >=, size);
277
278     naddr = mlist_alloc(allocator, rsize);
279     if (allocator->opts & ALLOC_PARANOID) {
280         mlist_check(allocator);
281     }
282
283     return naddr;
284 }
285
286 void guest_free(QGuestAllocator *allocator, uint64_t addr)
287 {
288     if (!addr) {
289         return;
290     }
291     mlist_free(allocator, addr);
292     if (allocator->opts & ALLOC_PARANOID) {
293         mlist_check(allocator);
294     }
295 }
296
297 QGuestAllocator *alloc_init(uint64_t start, uint64_t end)
298 {
299     QGuestAllocator *s = g_malloc0(sizeof(*s));
300     MemBlock *node;
301
302     s->start = start;
303     s->end = end;
304
305     s->used = g_malloc(sizeof(MemList));
306     s->free = g_malloc(sizeof(MemList));
307     QTAILQ_INIT(s->used);
308     QTAILQ_INIT(s->free);
309
310     node = mlist_new(s->start, s->end - s->start);
311     QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
312
313     s->page_size = DEFAULT_PAGE_SIZE;
314
315     return s;
316 }
317
318 QGuestAllocator *alloc_init_flags(QAllocOpts opts,
319                                   uint64_t start, uint64_t end)
320 {
321     QGuestAllocator *s = alloc_init(start, end);
322     s->opts = opts;
323     return s;
324 }
325
326 void alloc_set_page_size(QGuestAllocator *allocator, size_t page_size)
327 {
328     /* Can't alter the page_size for an allocator in-use */
329     g_assert(QTAILQ_EMPTY(allocator->used));
330
331     g_assert(is_power_of_2(page_size));
332     allocator->page_size = page_size;
333 }
334
335 void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
336 {
337     allocator->opts |= opts;
338 }
339
340 void migrate_allocator(QGuestAllocator *src,
341                        QGuestAllocator *dst)
342 {
343     MemBlock *node, *tmp;
344     MemList *tmpused, *tmpfree;
345
346     /* The general memory layout should be equivalent,
347      * though opts can differ. */
348     g_assert_cmphex(src->start, ==, dst->start);
349     g_assert_cmphex(src->end, ==, dst->end);
350
351     /* Destroy (silently, regardless of options) the dest-list: */
352     QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
353         g_free(node);
354     }
355     QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
356         g_free(node);
357     }
358
359     tmpused = dst->used;
360     tmpfree = dst->free;
361
362     /* Inherit the lists of the source allocator: */
363     dst->used = src->used;
364     dst->free = src->free;
365
366     /* Source is now re-initialized, the source memory is 'invalid' now: */
367     src->used = tmpused;
368     src->free = tmpfree;
369     QTAILQ_INIT(src->used);
370     QTAILQ_INIT(src->free);
371     node = mlist_new(src->start, src->end - src->start);
372     QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);
373     return;
374 }