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